source: src/ResolvExpr/CandidateFinder.cpp @ 2908f08

Last change on this file since 2908f08 was 2908f08, checked in by Andrew Beach <ajbeach@…>, 7 months ago

Most of ResolvExpr? was written before the new style standard. Some files updated, focus on headers.

  • Property mode set to 100644
File size: 74.7 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// CandidateFinder.cpp --
8//
9// Author           : Aaron B. Moss
10// Created On       : Wed Jun 5 14:30:00 2019
11// Last Modified By : Andrew Beach
12// Last Modified On : Wed Mar 16 11:58:00 2022
13// Update Count     : 3
14//
15
16#include "CandidateFinder.hpp"
17
18#include <deque>
19#include <iterator>               // for back_inserter
20#include <sstream>
21#include <string>
22#include <unordered_map>
23#include <vector>
24
25#include "AdjustExprType.hpp"
26#include "Candidate.hpp"
27#include "CastCost.hpp"           // for castCost
28#include "CompilationState.h"
29#include "ConversionCost.h"       // for conversionCast
30#include "Cost.h"
31#include "ExplodedArg.hpp"
32#include "PolyCost.hpp"
33#include "RenameVars.h"           // for renameTyVars
34#include "Resolver.h"
35#include "ResolveTypeof.h"
36#include "SatisfyAssertions.hpp"
37#include "SpecCost.hpp"
38#include "typeops.h"              // for combos
39#include "Unify.h"
40#include "WidenMode.h"
41#include "AST/Expr.hpp"
42#include "AST/Node.hpp"
43#include "AST/Pass.hpp"
44#include "AST/Print.hpp"
45#include "AST/SymbolTable.hpp"
46#include "AST/Type.hpp"
47#include "Common/utility.h"       // for move, copy
48#include "SymTab/Mangler.h"
49#include "Tuples/Tuples.h"        // for handleTupleAssignment
50#include "InitTweak/InitTweak.h"  // for getPointerBase
51
52#include "Common/Stats/Counter.h"
53
54#define PRINT( text ) if ( resolvep ) { text }
55
56namespace ResolvExpr {
57
58/// Unique identifier for matching expression resolutions to their requesting expression
59ast::UniqueId globalResnSlot = 0;
60
61namespace {
62        /// First index is which argument, second is which alternative, third is which exploded element
63        using ExplodedArgs = std::deque< std::vector< ExplodedArg > >;
64
65        /// Returns a list of alternatives with the minimum cost in the given list
66        CandidateList findMinCost( const CandidateList & candidates ) {
67                CandidateList out;
68                Cost minCost = Cost::infinity;
69                for ( const CandidateRef & r : candidates ) {
70                        if ( r->cost < minCost ) {
71                                minCost = r->cost;
72                                out.clear();
73                                out.emplace_back( r );
74                        } else if ( r->cost == minCost ) {
75                                out.emplace_back( r );
76                        }
77                }
78                return out;
79        }
80
81        /// Computes conversion cost for a given expression to a given type
82        const ast::Expr * computeExpressionConversionCost(
83                const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost
84        ) {
85                Cost convCost = computeConversionCost(
86                                arg->result, paramType, arg->get_lvalue(), symtab, env );
87                outCost += convCost;
88
89                // If there is a non-zero conversion cost, ignoring poly cost, then the expression requires
90                // conversion. Ignore poly cost for now, since this requires resolution of the cast to
91                // infer parameters and this does not currently work for the reason stated below
92                Cost tmpCost = convCost;
93                tmpCost.incPoly( -tmpCost.get_polyCost() );
94                if ( tmpCost != Cost::zero ) {
95                        ast::ptr< ast::Type > newType = paramType;
96                        env.apply( newType );
97                        return new ast::CastExpr{ arg, newType };
98
99                        // xxx - *should* be able to resolve this cast, but at the moment pointers are not
100                        // castable to zero_t, but are implicitly convertible. This is clearly inconsistent,
101                        // once this is fixed it should be possible to resolve the cast.
102                        // xxx - this isn't working, it appears because type1 (parameter) is seen as widenable,
103                        // but it shouldn't be because this makes the conversion from DT* to DT* since
104                        // commontype(zero_t, DT*) is DT*, rather than nothing
105
106                        // CandidateFinder finder{ symtab, env };
107                        // finder.find( arg, ResolvMode::withAdjustment() );
108                        // assertf( finder.candidates.size() > 0,
109                        //      "Somehow castable expression failed to find alternatives." );
110                        // assertf( finder.candidates.size() == 1,
111                        //      "Somehow got multiple alternatives for known cast expression." );
112                        // return finder.candidates.front()->expr;
113                }
114
115                return arg;
116        }
117
118        /// Computes conversion cost for a given candidate
119        Cost computeApplicationConversionCost(
120                CandidateRef cand, const ast::SymbolTable & symtab
121        ) {
122                auto appExpr = cand->expr.strict_as< ast::ApplicationExpr >();
123                auto pointer = appExpr->func->result.strict_as< ast::PointerType >();
124                auto function = pointer->base.strict_as< ast::FunctionType >();
125
126                Cost convCost = Cost::zero;
127                const auto & params = function->params;
128                auto param = params.begin();
129                auto & args = appExpr->args;
130
131                for ( unsigned i = 0; i < args.size(); ++i ) {
132                        const ast::Type * argType = args[i]->result;
133                        PRINT(
134                                std::cerr << "arg expression:" << std::endl;
135                                ast::print( std::cerr, args[i], 2 );
136                                std::cerr << "--- results are" << std::endl;
137                                ast::print( std::cerr, argType, 2 );
138                        )
139
140                        if ( param == params.end() ) {
141                                if ( function->isVarArgs ) {
142                                        convCost.incUnsafe();
143                                        PRINT( std::cerr << "end of params with varargs function: inc unsafe: "
144                                                << convCost << std::endl; ; )
145                                        // convert reference-typed expressions into value-typed expressions
146                                        cand->expr = ast::mutate_field_index(
147                                                appExpr, &ast::ApplicationExpr::args, i,
148                                                referenceToRvalueConversion( args[i], convCost ) );
149                                        continue;
150                                } else return Cost::infinity;
151                        }
152
153                        if ( auto def = args[i].as< ast::DefaultArgExpr >() ) {
154                                // Default arguments should be free - don't include conversion cost.
155                                // Unwrap them here because they are not relevant to the rest of the system
156                                cand->expr = ast::mutate_field_index(
157                                        appExpr, &ast::ApplicationExpr::args, i, def->expr );
158                                ++param;
159                                continue;
160                        }
161
162                        // mark conversion cost and also specialization cost of param type
163                        // const ast::Type * paramType = (*param)->get_type();
164                        cand->expr = ast::mutate_field_index(
165                                appExpr, &ast::ApplicationExpr::args, i,
166                                computeExpressionConversionCost(
167                                        args[i], *param, symtab, cand->env, convCost ) );
168                        convCost.decSpec( specCost( *param ) );
169                        ++param;  // can't be in for-loop update because of the continue
170                }
171
172                if ( param != params.end() ) return Cost::infinity;
173
174                // specialization cost of return types can't be accounted for directly, it disables
175                // otherwise-identical calls, like this example based on auto-newline in the I/O lib:
176                //
177                //   forall(otype OS) {
178                //     void ?|?(OS&, int);  // with newline
179                //     OS&  ?|?(OS&, int);  // no newline, always chosen due to more specialization
180                //   }
181
182                // mark type variable and specialization cost of forall clause
183                convCost.incVar( function->forall.size() );
184                convCost.decSpec( function->assertions.size() );
185
186                return convCost;
187        }
188
189        void makeUnifiableVars(
190                const ast::FunctionType * type, ast::OpenVarSet & unifiableVars,
191                ast::AssertionSet & need
192        ) {
193                for ( auto & tyvar : type->forall ) {
194                        unifiableVars[ *tyvar ] = ast::TypeData{ tyvar->base };
195                }
196                for ( auto & assn : type->assertions ) {
197                        need[ assn ].isUsed = true;
198                }
199        }
200
201        /// Gets a default value from an initializer, nullptr if not present
202        const ast::ConstantExpr * getDefaultValue( const ast::Init * init ) {
203                if ( auto si = dynamic_cast< const ast::SingleInit * >( init ) ) {
204                        if ( auto ce = si->value.as< ast::CastExpr >() ) {
205                                return ce->arg.as< ast::ConstantExpr >();
206                        } else {
207                                return si->value.as< ast::ConstantExpr >();
208                        }
209                }
210                return nullptr;
211        }
212
213        /// State to iteratively build a match of parameter expressions to arguments
214        struct ArgPack {
215                std::size_t parent;          ///< Index of parent pack
216                ast::ptr< ast::Expr > expr;  ///< The argument stored here
217                Cost cost;                   ///< The cost of this argument
218                ast::TypeEnvironment env;    ///< Environment for this pack
219                ast::AssertionSet need;      ///< Assertions outstanding for this pack
220                ast::AssertionSet have;      ///< Assertions found for this pack
221                ast::OpenVarSet open;        ///< Open variables for this pack
222                unsigned nextArg;            ///< Index of next argument in arguments list
223                unsigned tupleStart;         ///< Number of tuples that start at this index
224                unsigned nextExpl;           ///< Index of next exploded element
225                unsigned explAlt;            ///< Index of alternative for nextExpl > 0
226
227                ArgPack()
228                : parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ),
229                  tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}
230
231                ArgPack(
232                        const ast::TypeEnvironment & env, const ast::AssertionSet & need,
233                        const ast::AssertionSet & have, const ast::OpenVarSet & open )
234                : parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ),
235                  open( open ), nextArg( 0 ), tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}
236
237                ArgPack(
238                        std::size_t parent, const ast::Expr * expr, ast::TypeEnvironment && env,
239                        ast::AssertionSet && need, ast::AssertionSet && have, ast::OpenVarSet && open,
240                        unsigned nextArg, unsigned tupleStart = 0, Cost cost = Cost::zero,
241                        unsigned nextExpl = 0, unsigned explAlt = 0 )
242                : parent(parent), expr( expr ), cost( cost ), env( std::move( env ) ), need( std::move( need ) ),
243                  have( std::move( have ) ), open( std::move( open ) ), nextArg( nextArg ), tupleStart( tupleStart ),
244                  nextExpl( nextExpl ), explAlt( explAlt ) {}
245
246                ArgPack(
247                        const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need,
248                        ast::AssertionSet && have, ast::OpenVarSet && open, unsigned nextArg, Cost added )
249                : parent( o.parent ), expr( o.expr ), cost( o.cost + added ), env( std::move( env ) ),
250                  need( std::move( need ) ), have( std::move( have ) ), open( std::move( open ) ), nextArg( nextArg ),
251                  tupleStart( o.tupleStart ), nextExpl( 0 ), explAlt( 0 ) {}
252
253                /// true if this pack is in the middle of an exploded argument
254                bool hasExpl() const { return nextExpl > 0; }
255
256                /// Gets the list of exploded candidates for this pack
257                const ExplodedArg & getExpl( const ExplodedArgs & args ) const {
258                        return args[ nextArg-1 ][ explAlt ];
259                }
260
261                /// Ends a tuple expression, consolidating the appropriate args
262                void endTuple( const std::vector< ArgPack > & packs ) {
263                        // add all expressions in tuple to list, summing cost
264                        std::deque< const ast::Expr * > exprs;
265                        const ArgPack * pack = this;
266                        if ( expr ) { exprs.emplace_front( expr ); }
267                        while ( pack->tupleStart == 0 ) {
268                                pack = &packs[pack->parent];
269                                exprs.emplace_front( pack->expr );
270                                cost += pack->cost;
271                        }
272                        // reset pack to appropriate tuple
273                        std::vector< ast::ptr< ast::Expr > > exprv( exprs.begin(), exprs.end() );
274                        expr = new ast::TupleExpr{ expr->location, std::move( exprv ) };
275                        tupleStart = pack->tupleStart - 1;
276                        parent = pack->parent;
277                }
278        };
279
280        /// Instantiates an argument to match a parameter, returns false if no matching results left
281        bool instantiateArgument(
282                const CodeLocation & location,
283                const ast::Type * paramType, const ast::Init * init, const ExplodedArgs & args,
284                std::vector< ArgPack > & results, std::size_t & genStart, const ast::SymbolTable & symtab,
285                unsigned nTuples = 0
286        ) {
287                if ( auto tupleType = dynamic_cast< const ast::TupleType * >( paramType ) ) {
288                        // paramType is a TupleType -- group args into a TupleExpr
289                        ++nTuples;
290                        for ( const ast::Type * type : *tupleType ) {
291                                // xxx - dropping initializer changes behaviour from previous, but seems correct
292                                // ^^^ need to handle the case where a tuple has a default argument
293                                if ( ! instantiateArgument( location,
294                                        type, nullptr, args, results, genStart, symtab, nTuples ) ) return false;
295                                nTuples = 0;
296                        }
297                        // re-constitute tuples for final generation
298                        for ( auto i = genStart; i < results.size(); ++i ) {
299                                results[i].endTuple( results );
300                        }
301                        return true;
302                } else if ( const ast::TypeInstType * ttype = Tuples::isTtype( paramType ) ) {
303                        // paramType is a ttype, consumes all remaining arguments
304
305                        // completed tuples; will be spliced to end of results to finish
306                        std::vector< ArgPack > finalResults{};
307
308                        // iterate until all results completed
309                        std::size_t genEnd;
310                        ++nTuples;
311                        do {
312                                genEnd = results.size();
313
314                                // add another argument to results
315                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
316                                        unsigned nextArg = results[i].nextArg;
317
318                                        // use next element of exploded tuple if present
319                                        if ( results[i].hasExpl() ) {
320                                                const ExplodedArg & expl = results[i].getExpl( args );
321
322                                                unsigned nextExpl = results[i].nextExpl + 1;
323                                                if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
324
325                                                results.emplace_back(
326                                                        i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),
327                                                        copy( results[i].need ), copy( results[i].have ),
328                                                        copy( results[i].open ), nextArg, nTuples, Cost::zero, nextExpl,
329                                                        results[i].explAlt );
330
331                                                continue;
332                                        }
333
334                                        // finish result when out of arguments
335                                        if ( nextArg >= args.size() ) {
336                                                ArgPack newResult{
337                                                        results[i].env, results[i].need, results[i].have, results[i].open };
338                                                newResult.nextArg = nextArg;
339                                                const ast::Type * argType = nullptr;
340
341                                                if ( nTuples > 0 || ! results[i].expr ) {
342                                                        // first iteration or no expression to clone,
343                                                        // push empty tuple expression
344                                                        newResult.parent = i;
345                                                        newResult.expr = new ast::TupleExpr( location, {} );
346                                                        argType = newResult.expr->result;
347                                                } else {
348                                                        // clone result to collect tuple
349                                                        newResult.parent = results[i].parent;
350                                                        newResult.cost = results[i].cost;
351                                                        newResult.tupleStart = results[i].tupleStart;
352                                                        newResult.expr = results[i].expr;
353                                                        argType = newResult.expr->result;
354
355                                                        if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
356                                                                // the case where a ttype value is passed directly is special,
357                                                                // e.g. for argument forwarding purposes
358                                                                // xxx - what if passing multiple arguments, last of which is
359                                                                //       ttype?
360                                                                // xxx - what would happen if unify was changed so that unifying
361                                                                //       tuple
362                                                                // types flattened both before unifying lists? then pass in
363                                                                // TupleType (ttype) below.
364                                                                --newResult.tupleStart;
365                                                        } else {
366                                                                // collapse leftover arguments into tuple
367                                                                newResult.endTuple( results );
368                                                                argType = newResult.expr->result;
369                                                        }
370                                                }
371
372                                                // check unification for ttype before adding to final
373                                                if (
374                                                        unify(
375                                                                ttype, argType, newResult.env, newResult.need, newResult.have,
376                                                                newResult.open )
377                                                ) {
378                                                        finalResults.emplace_back( std::move( newResult ) );
379                                                }
380
381                                                continue;
382                                        }
383
384                                        // add each possible next argument
385                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
386                                                const ExplodedArg & expl = args[nextArg][j];
387
388                                                // fresh copies of parent parameters for this iteration
389                                                ast::TypeEnvironment env = results[i].env;
390                                                ast::OpenVarSet open = results[i].open;
391
392                                                env.addActual( expl.env, open );
393
394                                                // skip empty tuple arguments by (nearly) cloning parent into next gen
395                                                if ( expl.exprs.empty() ) {
396                                                        results.emplace_back(
397                                                                results[i], std::move( env ), copy( results[i].need ),
398                                                                copy( results[i].have ), std::move( open ), nextArg + 1, expl.cost );
399
400                                                        continue;
401                                                }
402
403                                                // add new result
404                                                results.emplace_back(
405                                                        i, expl.exprs.front(), std::move( env ), copy( results[i].need ),
406                                                        copy( results[i].have ), std::move( open ), nextArg + 1, nTuples,
407                                                        expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
408                                        }
409                                }
410
411                                // reset for next round
412                                genStart = genEnd;
413                                nTuples = 0;
414                        } while ( genEnd != results.size() );
415
416                        // splice final results onto results
417                        for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
418                                results.emplace_back( std::move( finalResults[i] ) );
419                        }
420                        return ! finalResults.empty();
421                }
422
423                // iterate each current subresult
424                std::size_t genEnd = results.size();
425                for ( std::size_t i = genStart; i < genEnd; ++i ) {
426                        unsigned nextArg = results[i].nextArg;
427
428                        // use remainder of exploded tuple if present
429                        if ( results[i].hasExpl() ) {
430                                const ExplodedArg & expl = results[i].getExpl( args );
431                                const ast::Expr * expr = expl.exprs[ results[i].nextExpl ];
432
433                                ast::TypeEnvironment env = results[i].env;
434                                ast::AssertionSet need = results[i].need, have = results[i].have;
435                                ast::OpenVarSet open = results[i].open;
436
437                                const ast::Type * argType = expr->result;
438
439                                PRINT(
440                                        std::cerr << "param type is ";
441                                        ast::print( std::cerr, paramType );
442                                        std::cerr << std::endl << "arg type is ";
443                                        ast::print( std::cerr, argType );
444                                        std::cerr << std::endl;
445                                )
446
447                                if ( unify( paramType, argType, env, need, have, open ) ) {
448                                        unsigned nextExpl = results[i].nextExpl + 1;
449                                        if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
450
451                                        results.emplace_back(
452                                                i, expr, std::move( env ), std::move( need ), std::move( have ), std::move( open ), nextArg,
453                                                nTuples, Cost::zero, nextExpl, results[i].explAlt );
454                                }
455
456                                continue;
457                        }
458
459                        // use default initializers if out of arguments
460                        if ( nextArg >= args.size() ) {
461                                if ( const ast::ConstantExpr * cnst = getDefaultValue( init ) ) {
462                                        ast::TypeEnvironment env = results[i].env;
463                                        ast::AssertionSet need = results[i].need, have = results[i].have;
464                                        ast::OpenVarSet open = results[i].open;
465
466                                        if ( unify( paramType, cnst->result, env, need, have, open ) ) {
467                                                results.emplace_back(
468                                                        i, new ast::DefaultArgExpr{ cnst->location, cnst }, std::move( env ),
469                                                        std::move( need ), std::move( have ), std::move( open ), nextArg, nTuples );
470                                        }
471                                }
472
473                                continue;
474                        }
475
476                        // Check each possible next argument
477                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
478                                const ExplodedArg & expl = args[nextArg][j];
479
480                                // fresh copies of parent parameters for this iteration
481                                ast::TypeEnvironment env = results[i].env;
482                                ast::AssertionSet need = results[i].need, have = results[i].have;
483                                ast::OpenVarSet open = results[i].open;
484
485                                env.addActual( expl.env, open );
486
487                                // skip empty tuple arguments by (nearly) cloning parent into next gen
488                                if ( expl.exprs.empty() ) {
489                                        results.emplace_back(
490                                                results[i], std::move( env ), std::move( need ), std::move( have ), std::move( open ),
491                                                nextArg + 1, expl.cost );
492
493                                        continue;
494                                }
495
496                                // consider only first exploded arg
497                                const ast::Expr * expr = expl.exprs.front();
498                                const ast::Type * argType = expr->result;
499
500                                PRINT(
501                                        std::cerr << "param type is ";
502                                        ast::print( std::cerr, paramType );
503                                        std::cerr << std::endl << "arg type is ";
504                                        ast::print( std::cerr, argType );
505                                        std::cerr << std::endl;
506                                )
507
508                                // attempt to unify types
509                                if ( unify( paramType, argType, env, need, have, open ) ) {
510                                        // add new result
511                                        results.emplace_back(
512                                                i, expr, std::move( env ), std::move( need ), std::move( have ), std::move( open ),
513                                                nextArg + 1, nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
514                                }
515                        }
516                }
517
518                // reset for next parameter
519                genStart = genEnd;
520
521                return genEnd != results.size();  // were any new results added?
522        }
523
524        /// Generate a cast expression from `arg` to `toType`
525        const ast::Expr * restructureCast(
526                ast::ptr< ast::Expr > & arg, const ast::Type * toType, ast::GeneratedFlag isGenerated = ast::GeneratedCast
527        ) {
528                if (
529                        arg->result->size() > 1
530                        && ! toType->isVoid()
531                        && ! dynamic_cast< const ast::ReferenceType * >( toType )
532                ) {
533                        // Argument is a tuple and the target type is neither void nor a reference. Cast each
534                        // member of the tuple to its corresponding target type, producing the tuple of those
535                        // cast expressions. If there are more components of the tuple than components in the
536                        // target type, then excess components do not come out in the result expression (but
537                        // UniqueExpr ensures that the side effects will still be produced)
538                        if ( Tuples::maybeImpureIgnoreUnique( arg ) ) {
539                                // expressions which may contain side effects require a single unique instance of
540                                // the expression
541                                arg = new ast::UniqueExpr{ arg->location, arg };
542                        }
543                        std::vector< ast::ptr< ast::Expr > > components;
544                        for ( unsigned i = 0; i < toType->size(); ++i ) {
545                                // cast each component
546                                ast::ptr< ast::Expr > idx = new ast::TupleIndexExpr{ arg->location, arg, i };
547                                components.emplace_back(
548                                        restructureCast( idx, toType->getComponent( i ), isGenerated ) );
549                        }
550                        return new ast::TupleExpr{ arg->location, std::move( components ) };
551                } else {
552                        // handle normally
553                        return new ast::CastExpr{ arg->location, arg, toType, isGenerated };
554                }
555        }
556
557        /// Gets the name from an untyped member expression (must be NameExpr)
558        const std::string & getMemberName( const ast::UntypedMemberExpr * memberExpr ) {
559                if ( memberExpr->member.as< ast::ConstantExpr >() ) {
560                        SemanticError( memberExpr, "Indexed access to struct fields unsupported: " );
561                }
562
563                return memberExpr->member.strict_as< ast::NameExpr >()->name;
564        }
565
566        /// Actually visits expressions to find their candidate interpretations
567        class Finder final : public ast::WithShortCircuiting {
568                const ResolveContext & context;
569                const ast::SymbolTable & symtab;
570        public:
571                // static size_t traceId;
572                CandidateFinder & selfFinder;
573                CandidateList & candidates;
574                const ast::TypeEnvironment & tenv;
575                ast::ptr< ast::Type > & targetType;
576
577                enum Errors {
578                        NotFound,
579                        NoMatch,
580                        ArgsToFew,
581                        ArgsToMany,
582                        RetsToFew,
583                        RetsToMany,
584                        NoReason
585                };
586
587                struct {
588                        Errors code = NotFound;
589                } reason;
590
591                Finder( CandidateFinder & f )
592                : context( f.context ), symtab( context.symtab ), selfFinder( f ),
593                  candidates( f.candidates ), tenv( f.env ), targetType( f.targetType ) {}
594
595                void previsit( const ast::Node * ) { visit_children = false; }
596
597                /// Convenience to add candidate to list
598                template<typename... Args>
599                void addCandidate( Args &&... args ) {
600                        candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } );
601                        reason.code = NoReason;
602                }
603
604                void postvisit( const ast::ApplicationExpr * applicationExpr ) {
605                        addCandidate( applicationExpr, tenv );
606                }
607
608                /// Set up candidate assertions for inference
609                void inferParameters( CandidateRef & newCand, CandidateList & out );
610
611                /// Completes a function candidate with arguments located
612                void validateFunctionCandidate(
613                        const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results,
614                        CandidateList & out );
615
616                /// Builds a list of candidates for a function, storing them in out
617                void makeFunctionCandidates(
618                        const CodeLocation & location,
619                        const CandidateRef & func, const ast::FunctionType * funcType,
620                        const ExplodedArgs & args, CandidateList & out );
621
622                /// Adds implicit struct-conversions to the alternative list
623                void addAnonConversions( const CandidateRef & cand );
624
625                /// Adds aggregate member interpretations
626                void addAggMembers(
627                        const ast::BaseInstType * aggrInst, const ast::Expr * expr,
628                        const Candidate & cand, const Cost & addedCost, const std::string & name
629                );
630
631                /// Adds tuple member interpretations
632                void addTupleMembers(
633                        const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand,
634                        const Cost & addedCost, const ast::Expr * member
635                );
636
637                /// true if expression is an lvalue
638                static bool isLvalue( const ast::Expr * x ) {
639                        return x->result && ( x->get_lvalue() || x->result.as< ast::ReferenceType >() );
640                }
641
642                void postvisit( const ast::UntypedExpr * untypedExpr );
643                void postvisit( const ast::VariableExpr * variableExpr );
644                void postvisit( const ast::ConstantExpr * constantExpr );
645                void postvisit( const ast::SizeofExpr * sizeofExpr );
646                void postvisit( const ast::AlignofExpr * alignofExpr );
647                void postvisit( const ast::AddressExpr * addressExpr );
648                void postvisit( const ast::LabelAddressExpr * labelExpr );
649                void postvisit( const ast::CastExpr * castExpr );
650                void postvisit( const ast::VirtualCastExpr * castExpr );
651                void postvisit( const ast::KeywordCastExpr * castExpr );
652                void postvisit( const ast::UntypedMemberExpr * memberExpr );
653                void postvisit( const ast::MemberExpr * memberExpr );
654                void postvisit( const ast::NameExpr * nameExpr );
655                void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr );
656                void postvisit( const ast::OffsetofExpr * offsetofExpr );
657                void postvisit( const ast::OffsetPackExpr * offsetPackExpr );
658                void postvisit( const ast::LogicalExpr * logicalExpr );
659                void postvisit( const ast::ConditionalExpr * conditionalExpr );
660                void postvisit( const ast::CommaExpr * commaExpr );
661                void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr );
662                void postvisit( const ast::ConstructorExpr * ctorExpr );
663                void postvisit( const ast::RangeExpr * rangeExpr );
664                void postvisit( const ast::UntypedTupleExpr * tupleExpr );
665                void postvisit( const ast::TupleExpr * tupleExpr );
666                void postvisit( const ast::TupleIndexExpr * tupleExpr );
667                void postvisit( const ast::TupleAssignExpr * tupleExpr );
668                void postvisit( const ast::UniqueExpr * unqExpr );
669                void postvisit( const ast::StmtExpr * stmtExpr );
670                void postvisit( const ast::UntypedInitExpr * initExpr );
671
672                void postvisit( const ast::InitExpr * ) {
673                        assertf( false, "CandidateFinder should never see a resolved InitExpr." );
674                }
675
676                void postvisit( const ast::DeletedExpr * ) {
677                        assertf( false, "CandidateFinder should never see a DeletedExpr." );
678                }
679
680                void postvisit( const ast::GenericExpr * ) {
681                        assertf( false, "_Generic is not yet supported." );
682                }
683        };
684
685        /// Set up candidate assertions for inference
686        void Finder::inferParameters( CandidateRef & newCand, CandidateList & out ) {
687                // Set need bindings for any unbound assertions
688                ast::UniqueId crntResnSlot = 0; // matching ID for this expression's assertions
689                for ( auto & assn : newCand->need ) {
690                        // skip already-matched assertions
691                        if ( assn.second.resnSlot != 0 ) continue;
692                        // assign slot for expression if needed
693                        if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; }
694                        // fix slot to assertion
695                        assn.second.resnSlot = crntResnSlot;
696                }
697                // pair slot to expression
698                if ( crntResnSlot != 0 ) {
699                        newCand->expr.get_and_mutate()->inferred.resnSlots().emplace_back( crntResnSlot );
700                }
701
702                // add to output list; assertion satisfaction will occur later
703                out.emplace_back( newCand );
704        }
705
706        /// Completes a function candidate with arguments located
707        void Finder::validateFunctionCandidate(
708                const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results,
709                CandidateList & out
710        ) {
711                ast::ApplicationExpr * appExpr =
712                        new ast::ApplicationExpr{ func->expr->location, func->expr };
713                // sum cost and accumulate arguments
714                std::deque< const ast::Expr * > args;
715                Cost cost = func->cost;
716                const ArgPack * pack = &result;
717                while ( pack->expr ) {
718                        args.emplace_front( pack->expr );
719                        cost += pack->cost;
720                        pack = &results[pack->parent];
721                }
722                std::vector< ast::ptr< ast::Expr > > vargs( args.begin(), args.end() );
723                appExpr->args = std::move( vargs );
724                // build and validate new candidate
725                auto newCand =
726                        std::make_shared<Candidate>( appExpr, result.env, result.open, result.need, cost );
727                PRINT(
728                        std::cerr << "instantiate function success: " << appExpr << std::endl;
729                        std::cerr << "need assertions:" << std::endl;
730                        ast::print( std::cerr, result.need, 2 );
731                )
732                inferParameters( newCand, out );
733        }
734
735        /// Builds a list of candidates for a function, storing them in out
736        void Finder::makeFunctionCandidates(
737                const CodeLocation & location,
738                const CandidateRef & func, const ast::FunctionType * funcType,
739                const ExplodedArgs & args, CandidateList & out
740        ) {
741                ast::OpenVarSet funcOpen;
742                ast::AssertionSet funcNeed, funcHave;
743                ast::TypeEnvironment funcEnv{ func->env };
744                makeUnifiableVars( funcType, funcOpen, funcNeed );
745                // add all type variables as open variables now so that those not used in the
746                // parameter list are still considered open
747                funcEnv.add( funcType->forall );
748
749                if ( targetType && ! targetType->isVoid() && ! funcType->returns.empty() ) {
750                        // attempt to narrow based on expected target type
751                        const ast::Type * returnType = funcType->returns.front();
752                        if ( selfFinder.strictMode ) {
753                                if ( !unifyExact(
754                                        returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, noWiden() ) // xxx - is no widening correct?
755                                ) {
756                                        // unification failed, do not pursue this candidate
757                                        return;
758                                }
759                        } else {
760                                if ( !unify(
761                                        returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen )
762                                ) {
763                                        // unification failed, do not pursue this candidate
764                                        return;
765                                }
766                        }
767                }
768
769                // iteratively build matches, one parameter at a time
770                std::vector< ArgPack > results;
771                results.emplace_back( funcEnv, funcNeed, funcHave, funcOpen );
772                std::size_t genStart = 0;
773
774                // xxx - how to handle default arg after change to ftype representation?
775                if (const ast::VariableExpr * varExpr = func->expr.as<ast::VariableExpr>()) {
776                        if (const ast::FunctionDecl * funcDecl = varExpr->var.as<ast::FunctionDecl>()) {
777                                // function may have default args only if directly calling by name
778                                // must use types on candidate however, due to RenameVars substitution
779                                auto nParams = funcType->params.size();
780
781                                for (size_t i=0; i<nParams; ++i) {
782                                        auto obj = funcDecl->params[i].strict_as<ast::ObjectDecl>();
783                                        if ( !instantiateArgument( location,
784                                                funcType->params[i], obj->init, args, results, genStart, symtab)) return;
785                                }
786                                goto endMatch;
787                        }
788                }
789                for ( const auto & param : funcType->params ) {
790                        // Try adding the arguments corresponding to the current parameter to the existing
791                        // matches
792                        // no default args for indirect calls
793                        if ( !instantiateArgument( location,
794                                param, nullptr, args, results, genStart, symtab ) ) return;
795                }
796
797                endMatch:
798                if ( funcType->isVarArgs ) {
799                        // append any unused arguments to vararg pack
800                        std::size_t genEnd;
801                        do {
802                                genEnd = results.size();
803
804                                // iterate results
805                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
806                                        unsigned nextArg = results[i].nextArg;
807
808                                        // use remainder of exploded tuple if present
809                                        if ( results[i].hasExpl() ) {
810                                                const ExplodedArg & expl = results[i].getExpl( args );
811
812                                                unsigned nextExpl = results[i].nextExpl + 1;
813                                                if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
814
815                                                results.emplace_back(
816                                                        i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),
817                                                        copy( results[i].need ), copy( results[i].have ),
818                                                        copy( results[i].open ), nextArg, 0, Cost::zero, nextExpl,
819                                                        results[i].explAlt );
820
821                                                continue;
822                                        }
823
824                                        // finish result when out of arguments
825                                        if ( nextArg >= args.size() ) {
826                                                validateFunctionCandidate( func, results[i], results, out );
827
828                                                continue;
829                                        }
830
831                                        // add each possible next argument
832                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
833                                                const ExplodedArg & expl = args[nextArg][j];
834
835                                                // fresh copies of parent parameters for this iteration
836                                                ast::TypeEnvironment env = results[i].env;
837                                                ast::OpenVarSet open = results[i].open;
838
839                                                env.addActual( expl.env, open );
840
841                                                // skip empty tuple arguments by (nearly) cloning parent into next gen
842                                                if ( expl.exprs.empty() ) {
843                                                        results.emplace_back(
844                                                                results[i], std::move( env ), copy( results[i].need ),
845                                                                copy( results[i].have ), std::move( open ), nextArg + 1,
846                                                                expl.cost );
847
848                                                        continue;
849                                                }
850
851                                                // add new result
852                                                results.emplace_back(
853                                                        i, expl.exprs.front(), std::move( env ), copy( results[i].need ),
854                                                        copy( results[i].have ), std::move( open ), nextArg + 1, 0, expl.cost,
855                                                        expl.exprs.size() == 1 ? 0 : 1, j );
856                                        }
857                                }
858
859                                genStart = genEnd;
860                        } while( genEnd != results.size() );
861                } else {
862                        // filter out the results that don't use all the arguments
863                        for ( std::size_t i = genStart; i < results.size(); ++i ) {
864                                ArgPack & result = results[i];
865                                if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
866                                        validateFunctionCandidate( func, result, results, out );
867                                }
868                        }
869                }
870        }
871
872        /// Adds implicit struct-conversions to the alternative list
873        void Finder::addAnonConversions( const CandidateRef & cand ) {
874                // adds anonymous member interpretations whenever an aggregate value type is seen.
875                // it's okay for the aggregate expression to have reference type -- cast it to the
876                // base type to treat the aggregate as the referenced value
877                ast::ptr< ast::Expr > aggrExpr( cand->expr );
878                ast::ptr< ast::Type > & aggrType = aggrExpr.get_and_mutate()->result;
879                cand->env.apply( aggrType );
880
881                if ( aggrType.as< ast::ReferenceType >() ) {
882                        aggrExpr = new ast::CastExpr{ aggrExpr, aggrType->stripReferences() };
883                }
884
885                if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) {
886                        addAggMembers( structInst, aggrExpr, *cand, Cost::unsafe, "" );
887                } else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) {
888                        addAggMembers( unionInst, aggrExpr, *cand, Cost::unsafe, "" );
889                }
890        }
891
892        /// Adds aggregate member interpretations
893        void Finder::addAggMembers(
894                const ast::BaseInstType * aggrInst, const ast::Expr * expr,
895                const Candidate & cand, const Cost & addedCost, const std::string & name
896        ) {
897                for ( const ast::Decl * decl : aggrInst->lookup( name ) ) {
898                        auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl );
899                        CandidateRef newCand = std::make_shared<Candidate>(
900                                cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost );
901                        // add anonymous member interpretations whenever an aggregate value type is seen
902                        // as a member expression
903                        addAnonConversions( newCand );
904                        candidates.emplace_back( std::move( newCand ) );
905                }
906        }
907
908        /// Adds tuple member interpretations
909        void Finder::addTupleMembers(
910                const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand,
911                const Cost & addedCost, const ast::Expr * member
912        ) {
913                if ( auto constantExpr = dynamic_cast< const ast::ConstantExpr * >( member ) ) {
914                        // get the value of the constant expression as an int, must be between 0 and the
915                        // length of the tuple to have meaning
916                        long long val = constantExpr->intValue();
917                        if ( val >= 0 && (unsigned long long)val < tupleType->size() ) {
918                                addCandidate(
919                                        cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val },
920                                        addedCost );
921                        }
922                }
923        }
924
925        void Finder::postvisit( const ast::UntypedExpr * untypedExpr ) {
926                std::vector< CandidateFinder > argCandidates =
927                        selfFinder.findSubExprs( untypedExpr->args );
928
929                // take care of possible tuple assignments
930                // if not tuple assignment, handled as normal function call
931                Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates );
932
933                CandidateFinder funcFinder( context, tenv );
934                if (auto nameExpr = untypedExpr->func.as<ast::NameExpr>()) {
935                        auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name);
936                        if (kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS) {
937                                assertf(!argCandidates.empty(), "special function call without argument");
938                                for (auto & firstArgCand: argCandidates[0]) {
939                                        ast::ptr<ast::Type> argType = firstArgCand->expr->result;
940                                        firstArgCand->env.apply(argType);
941                                        // strip references
942                                        // xxx - is this correct?
943                                        while (argType.as<ast::ReferenceType>()) argType = argType.as<ast::ReferenceType>()->base;
944
945                                        // convert 1-tuple to plain type
946                                        if (auto tuple = argType.as<ast::TupleType>()) {
947                                                if (tuple->size() == 1) {
948                                                        argType = tuple->types[0];
949                                                }
950                                        }
951
952                                        // if argType is an unbound type parameter, all special functions need to be searched.
953                                        if (isUnboundType(argType)) {
954                                                funcFinder.otypeKeys.clear();
955                                                break;
956                                        }
957
958                                        if (argType.as<ast::PointerType>()) funcFinder.otypeKeys.insert(Mangle::Encoding::pointer);                                             
959                                        // else if (const ast::EnumInstType * enumInst = argType.as<ast::EnumInstType>()) {
960                                        //      const ast::EnumDecl * enumDecl = enumInst->base; // Here
961                                        //      if ( const ast::Type* enumType = enumDecl->base ) {
962                                        //              // instance of enum (T) is a instance of type (T)
963                                        //              funcFinder.otypeKeys.insert(Mangle::mangle(enumType, Mangle::NoGenericParams | Mangle::Type));
964                                        //      } else {
965                                        //              // instance of an untyped enum is techically int
966                                        //              funcFinder.otypeKeys.insert(Mangle::mangle(enumDecl, Mangle::NoGenericParams | Mangle::Type));
967                                        //      }
968                                        // }
969                                        else funcFinder.otypeKeys.insert(Mangle::mangle(argType, Mangle::NoGenericParams | Mangle::Type));
970                                }
971                        }
972                }
973                // if candidates are already produced, do not fail
974                // xxx - is it possible that handleTupleAssignment and main finder both produce candidates?
975                // this means there exists ctor/assign functions with a tuple as first parameter.
976                ResolvMode mode = {
977                        true, // adjust
978                        !untypedExpr->func.as<ast::NameExpr>(), // prune if not calling by name
979                        selfFinder.candidates.empty() // failfast if other options are not found
980                };
981                funcFinder.find( untypedExpr->func, mode );
982                // short-circuit if no candidates
983                // if ( funcFinder.candidates.empty() ) return;
984
985                reason.code = NoMatch;
986
987                // find function operators
988                ast::ptr< ast::Expr > opExpr = new ast::NameExpr{ untypedExpr->location, "?()" }; // ??? why not ?{}
989                CandidateFinder opFinder( context, tenv );
990                // okay if there aren't any function operations
991                opFinder.find( opExpr, ResolvMode::withoutFailFast() );
992                PRINT(
993                        std::cerr << "known function ops:" << std::endl;
994                        print( std::cerr, opFinder.candidates, 1 );
995                )
996
997                // pre-explode arguments
998                ExplodedArgs argExpansions;
999                for ( const CandidateFinder & args : argCandidates ) {
1000                        argExpansions.emplace_back();
1001                        auto & argE = argExpansions.back();
1002                        for ( const CandidateRef & arg : args ) { argE.emplace_back( *arg, symtab ); }
1003                }
1004
1005                // Find function matches
1006                CandidateList found;
1007                SemanticErrorException errors;
1008                for ( CandidateRef & func : funcFinder ) {
1009                        try {
1010                                PRINT(
1011                                        std::cerr << "working on alternative:" << std::endl;
1012                                        print( std::cerr, *func, 2 );
1013                                )
1014
1015                                // check if the type is a pointer to function
1016                                const ast::Type * funcResult = func->expr->result->stripReferences();
1017                                if ( auto pointer = dynamic_cast< const ast::PointerType * >( funcResult ) ) {
1018                                        if ( auto function = pointer->base.as< ast::FunctionType >() ) {
1019                                                // if (!selfFinder.allowVoid && function->returns.empty()) continue;
1020                                                CandidateRef newFunc{ new Candidate{ *func } };
1021                                                newFunc->expr =
1022                                                        referenceToRvalueConversion( newFunc->expr, newFunc->cost );
1023                                                makeFunctionCandidates( untypedExpr->location,
1024                                                        newFunc, function, argExpansions, found );
1025                                        }
1026                                } else if (
1027                                        auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult )
1028                                ) {
1029                                        if ( const ast::EqvClass * clz = func->env.lookup( *inst ) ) {
1030                                                if ( auto function = clz->bound.as< ast::FunctionType >() ) {
1031                                                        CandidateRef newFunc( new Candidate( *func ) );
1032                                                        newFunc->expr =
1033                                                                referenceToRvalueConversion( newFunc->expr, newFunc->cost );
1034                                                        makeFunctionCandidates( untypedExpr->location,
1035                                                                newFunc, function, argExpansions, found );
1036                                                }
1037                                        }
1038                                }
1039                        } catch ( SemanticErrorException & e ) { errors.append( e ); }
1040                }
1041
1042                // Find matches on function operators `?()`
1043                if ( ! opFinder.candidates.empty() ) {
1044                        // add exploded function alternatives to front of argument list
1045                        std::vector< ExplodedArg > funcE;
1046                        funcE.reserve( funcFinder.candidates.size() );
1047                        for ( const CandidateRef & func : funcFinder ) {
1048                                funcE.emplace_back( *func, symtab );
1049                        }
1050                        argExpansions.emplace_front( std::move( funcE ) );
1051
1052                        for ( const CandidateRef & op : opFinder ) {
1053                                try {
1054                                        // check if type is pointer-to-function
1055                                        const ast::Type * opResult = op->expr->result->stripReferences();
1056                                        if ( auto pointer = dynamic_cast< const ast::PointerType * >( opResult ) ) {
1057                                                if ( auto function = pointer->base.as< ast::FunctionType >() ) {
1058                                                        CandidateRef newOp{ new Candidate{ *op} };
1059                                                        newOp->expr =
1060                                                                referenceToRvalueConversion( newOp->expr, newOp->cost );
1061                                                        makeFunctionCandidates( untypedExpr->location,
1062                                                                newOp, function, argExpansions, found );
1063                                                }
1064                                        }
1065                                } catch ( SemanticErrorException & e ) { errors.append( e ); }
1066                        }
1067                }
1068
1069                // Implement SFINAE; resolution errors are only errors if there aren't any non-error
1070                // candidates
1071                if ( found.empty() && ! errors.isEmpty() ) { throw errors; }
1072
1073                // only keep the best matching intrinsic result to match C semantics (no unexpected narrowing/widening)
1074                // TODO: keep one for each set of argument candidates?
1075                Cost intrinsicCost = Cost::infinity;
1076                CandidateList intrinsicResult;
1077
1078                // Compute conversion costs
1079                for ( CandidateRef & withFunc : found ) {
1080                        Cost cvtCost = computeApplicationConversionCost( withFunc, symtab );
1081
1082                        PRINT(
1083                                auto appExpr = withFunc->expr.strict_as< ast::ApplicationExpr >();
1084                                auto pointer = appExpr->func->result.strict_as< ast::PointerType >();
1085                                auto function = pointer->base.strict_as< ast::FunctionType >();
1086
1087                                std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl;
1088                                std::cerr << "parameters are:" << std::endl;
1089                                ast::printAll( std::cerr, function->params, 2 );
1090                                std::cerr << "arguments are:" << std::endl;
1091                                ast::printAll( std::cerr, appExpr->args, 2 );
1092                                std::cerr << "bindings are:" << std::endl;
1093                                ast::print( std::cerr, withFunc->env, 2 );
1094                                std::cerr << "cost is: " << withFunc->cost << std::endl;
1095                                std::cerr << "cost of conversion is:" << cvtCost << std::endl;
1096                        )
1097
1098                        if ( cvtCost != Cost::infinity ) {
1099                                withFunc->cvtCost = cvtCost;
1100                                withFunc->cost += cvtCost;
1101                                auto func = withFunc->expr.strict_as<ast::ApplicationExpr>()->func.as<ast::VariableExpr>();
1102                                if (func && func->var->linkage == ast::Linkage::Intrinsic) {
1103                                        if (withFunc->cost < intrinsicCost) {
1104                                                intrinsicResult.clear();
1105                                                intrinsicCost = withFunc->cost;
1106                                        }
1107                                        if (withFunc->cost == intrinsicCost) {
1108                                                intrinsicResult.emplace_back(std::move(withFunc));
1109                                        }
1110                                } else {
1111                                        candidates.emplace_back( std::move( withFunc ) );
1112                                }
1113                        }
1114                }
1115                spliceBegin( candidates, intrinsicResult );
1116                found = std::move( candidates );
1117
1118                // use a new list so that candidates are not examined by addAnonConversions twice
1119                // CandidateList winners = findMinCost( found );
1120                // promoteCvtCost( winners );
1121
1122                // function may return a struct/union value, in which case we need to add candidates
1123                // for implicit conversions to each of the anonymous members, which must happen after
1124                // `findMinCost`, since anon conversions are never the cheapest
1125                for ( const CandidateRef & c : found ) {
1126                        addAnonConversions( c );
1127                }
1128                // would this be too slow when we don't check cost anymore?
1129                spliceBegin( candidates, found );
1130
1131                if ( candidates.empty() && targetType && ! targetType->isVoid() && !selfFinder.strictMode ) {
1132                        // If resolution is unsuccessful with a target type, try again without, since it
1133                        // will sometimes succeed when it wouldn't with a target type binding.
1134                        // For example:
1135                        //   forall( otype T ) T & ?[]( T *, ptrdiff_t );
1136                        //   const char * x = "hello world";
1137                        //   unsigned char ch = x[0];
1138                        // Fails with simple return type binding (xxx -- check this!) as follows:
1139                        // * T is bound to unsigned char
1140                        // * (x: const char *) is unified with unsigned char *, which fails
1141                        // xxx -- fix this better
1142                        targetType = nullptr;
1143                        postvisit( untypedExpr );
1144                }
1145        }
1146
1147        void Finder::postvisit( const ast::AddressExpr * addressExpr ) {
1148                CandidateFinder finder( context, tenv );
1149                finder.find( addressExpr->arg );
1150
1151                if ( finder.candidates.empty() ) return;
1152
1153                reason.code = NoMatch;
1154
1155                for ( CandidateRef & r : finder.candidates ) {
1156                        if ( !isLvalue( r->expr ) ) continue;
1157                        addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } );
1158                }
1159        }
1160
1161        void Finder::postvisit( const ast::LabelAddressExpr * labelExpr ) {
1162                addCandidate( labelExpr, tenv );
1163        }
1164
1165        void Finder::postvisit( const ast::CastExpr * castExpr ) {
1166                ast::ptr< ast::Type > toType = castExpr->result;
1167                assert( toType );
1168                toType = resolveTypeof( toType, context );
1169                toType = adjustExprType( toType, tenv, symtab );
1170
1171                CandidateFinder finder( context, tenv, toType );
1172                if (toType->isVoid()) {
1173                        finder.allowVoid = true;
1174                }
1175                if ( castExpr->kind == ast::CastExpr::Return ) {
1176                        finder.strictMode = true;
1177                        finder.find( castExpr->arg, ResolvMode::withAdjustment() );
1178
1179                        // return casts are eliminated (merely selecting an overload, no actual operation)
1180                        candidates = std::move(finder.candidates);
1181                }
1182                finder.find( castExpr->arg, ResolvMode::withAdjustment() );
1183
1184                if ( !finder.candidates.empty() ) reason.code = NoMatch;
1185
1186                CandidateList matches;
1187                Cost minExprCost = Cost::infinity;
1188                Cost minCastCost = Cost::infinity;
1189                for ( CandidateRef & cand : finder.candidates ) {
1190                        ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have;
1191                        ast::OpenVarSet open( cand->open );
1192
1193                        cand->env.extractOpenVars( open );
1194
1195                        // It is possible that a cast can throw away some values in a multiply-valued
1196                        // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of the
1197                        // subexpression results that are cast directly. The candidate is invalid if it
1198                        // has fewer results than there are types to cast to.
1199                        int discardedValues = cand->expr->result->size() - toType->size();
1200                        if ( discardedValues < 0 ) continue;
1201
1202                        // unification run for side-effects
1203                        unify( toType, cand->expr->result, cand->env, need, have, open );
1204                        Cost thisCost =
1205                                (castExpr->isGenerated == ast::GeneratedFlag::GeneratedCast)
1206                                        ? conversionCost( cand->expr->result, toType, cand->expr->get_lvalue(), symtab, cand->env )
1207                                        : castCost( cand->expr->result, toType, cand->expr->get_lvalue(), symtab, cand->env );
1208
1209                        PRINT(
1210                                std::cerr << "working on cast with result: " << toType << std::endl;
1211                                std::cerr << "and expr type: " << cand->expr->result << std::endl;
1212                                std::cerr << "env: " << cand->env << std::endl;
1213                        )
1214                        if ( thisCost != Cost::infinity ) {
1215                                PRINT(
1216                                        std::cerr << "has finite cost." << std::endl;
1217                                )
1218                                // count one safe conversion for each value that is thrown away
1219                                thisCost.incSafe( discardedValues );
1220                                // select first on argument cost, then conversion cost
1221                                if ( cand->cost < minExprCost || ( cand->cost == minExprCost && thisCost < minCastCost ) ) {
1222                                        minExprCost = cand->cost;
1223                                        minCastCost = thisCost;
1224                                        matches.clear();
1225
1226
1227                                }
1228                                // ambiguous case, still output candidates to print in error message
1229                                if ( cand->cost == minExprCost && thisCost == minCastCost ) {
1230                                        CandidateRef newCand = std::make_shared<Candidate>(
1231                                                restructureCast( cand->expr, toType, castExpr->isGenerated ),
1232                                                copy( cand->env ), std::move( open ), std::move( need ), cand->cost + thisCost);
1233                                        // currently assertions are always resolved immediately so this should have no effect.
1234                                        // if this somehow changes in the future (e.g. delayed by indeterminate return type)
1235                                        // we may need to revisit the logic.
1236                                        inferParameters( newCand, matches );
1237                                }
1238                                // else skip, better alternatives found
1239
1240                        }
1241                }
1242                candidates = std::move(matches);
1243
1244                //CandidateList minArgCost = findMinCost( matches );
1245                //promoteCvtCost( minArgCost );
1246                //candidates = findMinCost( minArgCost );
1247        }
1248
1249        void Finder::postvisit( const ast::VirtualCastExpr * castExpr ) {
1250                assertf( castExpr->result, "Implicit virtual cast targets not yet supported." );
1251                CandidateFinder finder( context, tenv );
1252                // don't prune here, all alternatives guaranteed to have same type
1253                finder.find( castExpr->arg, ResolvMode::withoutPrune() );
1254                for ( CandidateRef & r : finder.candidates ) {
1255                        addCandidate(
1256                                *r,
1257                                new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );
1258                }
1259        }
1260
1261        void Finder::postvisit( const ast::KeywordCastExpr * castExpr ) {
1262                const auto & loc = castExpr->location;
1263                assertf( castExpr->result, "Cast target should have been set in Validate." );
1264                auto ref = castExpr->result.strict_as<ast::ReferenceType>();
1265                auto inst = ref->base.strict_as<ast::StructInstType>();
1266                auto target = inst->base.get();
1267
1268                CandidateFinder finder( context, tenv );
1269
1270                auto pick_alternatives = [target, this](CandidateList & found, bool expect_ref) {
1271                        for (auto & cand : found) {
1272                                const ast::Type * expr = cand->expr->result.get();
1273                                if (expect_ref) {
1274                                        auto res = dynamic_cast<const ast::ReferenceType*>(expr);
1275                                        if (!res) { continue; }
1276                                        expr = res->base.get();
1277                                }
1278
1279                                if (auto insttype = dynamic_cast<const ast::TypeInstType*>(expr)) {
1280                                        auto td = cand->env.lookup(*insttype);
1281                                        if (!td) { continue; }
1282                                        expr = td->bound.get();
1283                                }
1284
1285                                if (auto base = dynamic_cast<const ast::StructInstType*>(expr)) {
1286                                        if (base->base == target) {
1287                                                candidates.push_back( std::move(cand) );
1288                                                reason.code = NoReason;
1289                                        }
1290                                }
1291                        }
1292                };
1293
1294                try {
1295                        // Attempt 1 : turn (thread&)X into (thread$&)X.__thrd
1296                        // Clone is purely for memory management
1297                        std::unique_ptr<const ast::Expr> tech1 { new ast::UntypedMemberExpr(loc, new ast::NameExpr(loc, castExpr->concrete_target.field), castExpr->arg) };
1298
1299                        // don't prune here, since it's guaranteed all alternatives will have the same type
1300                        finder.find( tech1.get(), ResolvMode::withoutPrune() );
1301                        pick_alternatives(finder.candidates, false);
1302
1303                        return;
1304                } catch(SemanticErrorException & ) {}
1305
1306                // Fallback : turn (thread&)X into (thread$&)get_thread(X)
1307                std::unique_ptr<const ast::Expr> fallback { ast::UntypedExpr::createDeref(loc,  new ast::UntypedExpr(loc, new ast::NameExpr(loc, castExpr->concrete_target.getter), { castExpr->arg })) };
1308                // don't prune here, since it's guaranteed all alternatives will have the same type
1309                finder.find( fallback.get(), ResolvMode::withoutPrune() );
1310
1311                pick_alternatives(finder.candidates, true);
1312
1313                // Whatever happens here, we have no more fallbacks
1314        }
1315
1316        void Finder::postvisit( const ast::UntypedMemberExpr * memberExpr ) {
1317                CandidateFinder aggFinder( context, tenv );
1318                aggFinder.find( memberExpr->aggregate, ResolvMode::withAdjustment() );
1319                for ( CandidateRef & agg : aggFinder.candidates ) {
1320                        // it's okay for the aggregate expression to have reference type -- cast it to the
1321                        // base type to treat the aggregate as the referenced value
1322                        Cost addedCost = Cost::zero;
1323                        agg->expr = referenceToRvalueConversion( agg->expr, addedCost );
1324
1325                        // find member of the given type
1326                        if ( auto structInst = agg->expr->result.as< ast::StructInstType >() ) {
1327                                addAggMembers(
1328                                        structInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );
1329                        } else if ( auto unionInst = agg->expr->result.as< ast::UnionInstType >() ) {
1330                                addAggMembers(
1331                                        unionInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );
1332                        } else if ( auto tupleType = agg->expr->result.as< ast::TupleType >() ) {
1333                                addTupleMembers( tupleType, agg->expr, *agg, addedCost, memberExpr->member );
1334                        }
1335                }
1336        }
1337
1338        void Finder::postvisit( const ast::MemberExpr * memberExpr ) {
1339                addCandidate( memberExpr, tenv );
1340        }
1341
1342        void Finder::postvisit( const ast::NameExpr * nameExpr ) {
1343                std::vector< ast::SymbolTable::IdData > declList;
1344                if (!selfFinder.otypeKeys.empty()) {
1345                        auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name);
1346                        assertf(kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS, "special lookup with non-special target: %s", nameExpr->name.c_str());
1347
1348                        for (auto & otypeKey: selfFinder.otypeKeys) {
1349                                auto result = symtab.specialLookupId(kind, otypeKey);
1350                                declList.insert(declList.end(), std::make_move_iterator(result.begin()), std::make_move_iterator(result.end()));
1351                        }
1352                } else {
1353                        declList = symtab.lookupId( nameExpr->name );
1354                }
1355                PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )
1356
1357                if ( declList.empty() ) return;
1358
1359                reason.code = NoMatch;
1360
1361                for ( auto & data : declList ) {
1362                        Cost cost = Cost::zero;
1363                        ast::Expr * newExpr = data.combine( nameExpr->location, cost );
1364
1365                        CandidateRef newCand = std::make_shared<Candidate>(
1366                                newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, Cost::zero,
1367                                cost );
1368
1369                        if (newCand->expr->env) {
1370                                newCand->env.add(*newCand->expr->env);
1371                                auto mutExpr = newCand->expr.get_and_mutate();
1372                                mutExpr->env  = nullptr;
1373                                newCand->expr = mutExpr;
1374                        }
1375
1376                        PRINT(
1377                                std::cerr << "decl is ";
1378                                ast::print( std::cerr, data.id );
1379                                std::cerr << std::endl;
1380                                std::cerr << "newExpr is ";
1381                                ast::print( std::cerr, newExpr );
1382                                std::cerr << std::endl;
1383                        )
1384                        newCand->expr = ast::mutate_field(
1385                                newCand->expr.get(), &ast::Expr::result,
1386                                renameTyVars( newCand->expr->result ) );
1387                        // add anonymous member interpretations whenever an aggregate value type is seen
1388                        // as a name expression
1389                        addAnonConversions( newCand );
1390                        candidates.emplace_back( std::move( newCand ) );
1391                }
1392        }
1393
1394        void Finder::postvisit( const ast::VariableExpr * variableExpr ) {
1395                // not sufficient to just pass `variableExpr` here, type might have changed since
1396                // creation
1397                addCandidate(
1398                        new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv );
1399        }
1400
1401        void Finder::postvisit( const ast::ConstantExpr * constantExpr ) {
1402                addCandidate( constantExpr, tenv );
1403        }
1404
1405        void Finder::postvisit( const ast::SizeofExpr * sizeofExpr ) {
1406                if ( sizeofExpr->type ) {
1407                        addCandidate(
1408                                new ast::SizeofExpr{
1409                                        sizeofExpr->location, resolveTypeof( sizeofExpr->type, context ) },
1410                                tenv );
1411                } else {
1412                        // find all candidates for the argument to sizeof
1413                        CandidateFinder finder( context, tenv );
1414                        finder.find( sizeofExpr->expr );
1415                        // find the lowest-cost candidate, otherwise ambiguous
1416                        CandidateList winners = findMinCost( finder.candidates );
1417                        if ( winners.size() != 1 ) {
1418                                SemanticError(
1419                                        sizeofExpr->expr.get(), "Ambiguous expression in sizeof operand: " );
1420                        }
1421                        // return the lowest-cost candidate
1422                        CandidateRef & choice = winners.front();
1423                        choice->expr = referenceToRvalueConversion( choice->expr, choice->cost );
1424                        choice->cost = Cost::zero;
1425                        addCandidate( *choice, new ast::SizeofExpr{ sizeofExpr->location, choice->expr } );
1426                }
1427        }
1428
1429        void Finder::postvisit( const ast::AlignofExpr * alignofExpr ) {
1430                if ( alignofExpr->type ) {
1431                        addCandidate(
1432                                new ast::AlignofExpr{
1433                                        alignofExpr->location, resolveTypeof( alignofExpr->type, context ) },
1434                                tenv );
1435                } else {
1436                        // find all candidates for the argument to alignof
1437                        CandidateFinder finder( context, tenv );
1438                        finder.find( alignofExpr->expr );
1439                        // find the lowest-cost candidate, otherwise ambiguous
1440                        CandidateList winners = findMinCost( finder.candidates );
1441                        if ( winners.size() != 1 ) {
1442                                SemanticError(
1443                                        alignofExpr->expr.get(), "Ambiguous expression in alignof operand: " );
1444                        }
1445                        // return the lowest-cost candidate
1446                        CandidateRef & choice = winners.front();
1447                        choice->expr = referenceToRvalueConversion( choice->expr, choice->cost );
1448                        choice->cost = Cost::zero;
1449                        addCandidate(
1450                                *choice, new ast::AlignofExpr{ alignofExpr->location, choice->expr } );
1451                }
1452        }
1453
1454        void Finder::postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {
1455                const ast::BaseInstType * aggInst;
1456                if (( aggInst = offsetofExpr->type.as< ast::StructInstType >() )) ;
1457                else if (( aggInst = offsetofExpr->type.as< ast::UnionInstType >() )) ;
1458                else return;
1459
1460                for ( const ast::Decl * member : aggInst->lookup( offsetofExpr->member ) ) {
1461                        auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( member );
1462                        addCandidate(
1463                                new ast::OffsetofExpr{ offsetofExpr->location, aggInst, dwt }, tenv );
1464                }
1465        }
1466
1467        void Finder::postvisit( const ast::OffsetofExpr * offsetofExpr ) {
1468                addCandidate( offsetofExpr, tenv );
1469        }
1470
1471        void Finder::postvisit( const ast::OffsetPackExpr * offsetPackExpr ) {
1472                addCandidate( offsetPackExpr, tenv );
1473        }
1474
1475        void Finder::postvisit( const ast::LogicalExpr * logicalExpr ) {
1476                CandidateFinder finder1( context, tenv );
1477                finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() );
1478                if ( finder1.candidates.empty() ) return;
1479
1480                CandidateFinder finder2( context, tenv );
1481                finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() );
1482                if ( finder2.candidates.empty() ) return;
1483
1484                reason.code = NoMatch;
1485
1486                for ( const CandidateRef & r1 : finder1.candidates ) {
1487                        for ( const CandidateRef & r2 : finder2.candidates ) {
1488                                ast::TypeEnvironment env{ r1->env };
1489                                env.simpleCombine( r2->env );
1490                                ast::OpenVarSet open{ r1->open };
1491                                mergeOpenVars( open, r2->open );
1492                                ast::AssertionSet need;
1493                                mergeAssertionSet( need, r1->need );
1494                                mergeAssertionSet( need, r2->need );
1495
1496                                addCandidate(
1497                                        new ast::LogicalExpr{
1498                                                logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },
1499                                        std::move( env ), std::move( open ), std::move( need ), r1->cost + r2->cost );
1500                        }
1501                }
1502        }
1503
1504        void Finder::postvisit( const ast::ConditionalExpr * conditionalExpr ) {
1505                // candidates for condition
1506                CandidateFinder finder1( context, tenv );
1507                finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() );
1508                if ( finder1.candidates.empty() ) return;
1509
1510                // candidates for true result
1511                CandidateFinder finder2( context, tenv );
1512                finder2.allowVoid = true;
1513                finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() );
1514                if ( finder2.candidates.empty() ) return;
1515
1516                // candidates for false result
1517                CandidateFinder finder3( context, tenv );
1518                finder3.allowVoid = true;
1519                finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() );
1520                if ( finder3.candidates.empty() ) return;
1521
1522                reason.code = NoMatch;
1523
1524                for ( const CandidateRef & r1 : finder1.candidates ) {
1525                        for ( const CandidateRef & r2 : finder2.candidates ) {
1526                                for ( const CandidateRef & r3 : finder3.candidates ) {
1527                                        ast::TypeEnvironment env{ r1->env };
1528                                        env.simpleCombine( r2->env );
1529                                        env.simpleCombine( r3->env );
1530                                        ast::OpenVarSet open{ r1->open };
1531                                        mergeOpenVars( open, r2->open );
1532                                        mergeOpenVars( open, r3->open );
1533                                        ast::AssertionSet need;
1534                                        mergeAssertionSet( need, r1->need );
1535                                        mergeAssertionSet( need, r2->need );
1536                                        mergeAssertionSet( need, r3->need );
1537                                        ast::AssertionSet have;
1538
1539                                        // unify true and false results, then infer parameters to produce new
1540                                        // candidates
1541                                        ast::ptr< ast::Type > common;
1542                                        if (
1543                                                unify(
1544                                                        r2->expr->result, r3->expr->result, env, need, have, open,
1545                                                        common )
1546                                        ) {
1547                                                // generate typed expression
1548                                                ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{
1549                                                        conditionalExpr->location, r1->expr, r2->expr, r3->expr };
1550                                                newExpr->result = common ? common : r2->expr->result;
1551                                                // convert both options to result type
1552                                                Cost cost = r1->cost + r2->cost + r3->cost;
1553                                                newExpr->arg2 = computeExpressionConversionCost(
1554                                                        newExpr->arg2, newExpr->result, symtab, env, cost );
1555                                                newExpr->arg3 = computeExpressionConversionCost(
1556                                                        newExpr->arg3, newExpr->result, symtab, env, cost );
1557                                                // output candidate
1558                                                CandidateRef newCand = std::make_shared<Candidate>(
1559                                                        newExpr, std::move( env ), std::move( open ), std::move( need ), cost );
1560                                                inferParameters( newCand, candidates );
1561                                        }
1562                                }
1563                        }
1564                }
1565        }
1566
1567        void Finder::postvisit( const ast::CommaExpr * commaExpr ) {
1568                ast::TypeEnvironment env{ tenv };
1569                ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, context, env );
1570
1571                CandidateFinder finder2( context, env );
1572                finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() );
1573
1574                for ( const CandidateRef & r2 : finder2.candidates ) {
1575                        addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } );
1576                }
1577        }
1578
1579        void Finder::postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) {
1580                addCandidate( ctorExpr, tenv );
1581        }
1582
1583        void Finder::postvisit( const ast::ConstructorExpr * ctorExpr ) {
1584                CandidateFinder finder( context, tenv );
1585                finder.allowVoid = true;
1586                finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() );
1587                for ( CandidateRef & r : finder.candidates ) {
1588                        addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } );
1589                }
1590        }
1591
1592        void Finder::postvisit( const ast::RangeExpr * rangeExpr ) {
1593                // resolve low and high, accept candidates where low and high types unify
1594                CandidateFinder finder1( context, tenv );
1595                finder1.find( rangeExpr->low, ResolvMode::withAdjustment() );
1596                if ( finder1.candidates.empty() ) return;
1597
1598                CandidateFinder finder2( context, tenv );
1599                finder2.find( rangeExpr->high, ResolvMode::withAdjustment() );
1600                if ( finder2.candidates.empty() ) return;
1601
1602                reason.code = NoMatch;
1603
1604                for ( const CandidateRef & r1 : finder1.candidates ) {
1605                        for ( const CandidateRef & r2 : finder2.candidates ) {
1606                                ast::TypeEnvironment env{ r1->env };
1607                                env.simpleCombine( r2->env );
1608                                ast::OpenVarSet open{ r1->open };
1609                                mergeOpenVars( open, r2->open );
1610                                ast::AssertionSet need;
1611                                mergeAssertionSet( need, r1->need );
1612                                mergeAssertionSet( need, r2->need );
1613                                ast::AssertionSet have;
1614
1615                                ast::ptr< ast::Type > common;
1616                                if (
1617                                        unify(
1618                                                r1->expr->result, r2->expr->result, env, need, have, open,
1619                                                common )
1620                                ) {
1621                                        // generate new expression
1622                                        ast::RangeExpr * newExpr =
1623                                                new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };
1624                                        newExpr->result = common ? common : r1->expr->result;
1625                                        // add candidate
1626                                        CandidateRef newCand = std::make_shared<Candidate>(
1627                                                newExpr, std::move( env ), std::move( open ), std::move( need ),
1628                                                r1->cost + r2->cost );
1629                                        inferParameters( newCand, candidates );
1630                                }
1631                        }
1632                }
1633        }
1634
1635        void Finder::postvisit( const ast::UntypedTupleExpr * tupleExpr ) {
1636                std::vector< CandidateFinder > subCandidates =
1637                        selfFinder.findSubExprs( tupleExpr->exprs );
1638                std::vector< CandidateList > possibilities;
1639                combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) );
1640
1641                for ( const CandidateList & subs : possibilities ) {
1642                        std::vector< ast::ptr< ast::Expr > > exprs;
1643                        exprs.reserve( subs.size() );
1644                        for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); }
1645
1646                        ast::TypeEnvironment env;
1647                        ast::OpenVarSet open;
1648                        ast::AssertionSet need;
1649                        for ( const CandidateRef & sub : subs ) {
1650                                env.simpleCombine( sub->env );
1651                                mergeOpenVars( open, sub->open );
1652                                mergeAssertionSet( need, sub->need );
1653                        }
1654
1655                        addCandidate(
1656                                new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) },
1657                                std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) );
1658                }
1659        }
1660
1661        void Finder::postvisit( const ast::TupleExpr * tupleExpr ) {
1662                addCandidate( tupleExpr, tenv );
1663        }
1664
1665        void Finder::postvisit( const ast::TupleIndexExpr * tupleExpr ) {
1666                addCandidate( tupleExpr, tenv );
1667        }
1668
1669        void Finder::postvisit( const ast::TupleAssignExpr * tupleExpr ) {
1670                addCandidate( tupleExpr, tenv );
1671        }
1672
1673        void Finder::postvisit( const ast::UniqueExpr * unqExpr ) {
1674                CandidateFinder finder( context, tenv );
1675                finder.find( unqExpr->expr, ResolvMode::withAdjustment() );
1676                for ( CandidateRef & r : finder.candidates ) {
1677                        // ensure that the the id is passed on so that the expressions are "linked"
1678                        addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } );
1679                }
1680        }
1681
1682        void Finder::postvisit( const ast::StmtExpr * stmtExpr ) {
1683                addCandidate( resolveStmtExpr( stmtExpr, context ), tenv );
1684        }
1685
1686        void Finder::postvisit( const ast::UntypedInitExpr * initExpr ) {
1687                // handle each option like a cast
1688                CandidateList matches;
1689                PRINT(
1690                        std::cerr << "untyped init expr: " << initExpr << std::endl;
1691                )
1692                // O(n^2) checks of d-types with e-types
1693                for ( const ast::InitAlternative & initAlt : initExpr->initAlts ) {
1694                        // calculate target type
1695                        const ast::Type * toType = resolveTypeof( initAlt.type, context );
1696                        toType = adjustExprType( toType, tenv, symtab );
1697                        // The call to find must occur inside this loop, otherwise polymorphic return
1698                        // types are not bound to the initialization type, since return type variables are
1699                        // only open for the duration of resolving the UntypedExpr.
1700                        CandidateFinder finder( context, tenv, toType );
1701                        finder.find( initExpr->expr, ResolvMode::withAdjustment() );
1702
1703                        Cost minExprCost = Cost::infinity;
1704                        Cost minCastCost = Cost::infinity;
1705                        for ( CandidateRef & cand : finder.candidates ) {
1706                                if (reason.code == NotFound) reason.code = NoMatch;
1707
1708                                ast::TypeEnvironment env{ cand->env };
1709                                ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have;
1710                                ast::OpenVarSet open{ cand->open };
1711
1712                                PRINT(
1713                                        std::cerr << "  @ " << toType << " " << initAlt.designation << std::endl;
1714                                )
1715
1716                                // It is possible that a cast can throw away some values in a multiply-valued
1717                                // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of
1718                                // the subexpression results that are cast directly. The candidate is invalid
1719                                // if it has fewer results than there are types to cast to.
1720                                int discardedValues = cand->expr->result->size() - toType->size();
1721                                if ( discardedValues < 0 ) continue;
1722
1723                                // unification run for side-effects
1724                                bool canUnify = unify( toType, cand->expr->result, env, need, have, open );
1725                                (void) canUnify;
1726                                Cost thisCost = computeConversionCost( cand->expr->result, toType, cand->expr->get_lvalue(),
1727                                        symtab, env );
1728                                PRINT(
1729                                        Cost legacyCost = castCost( cand->expr->result, toType, cand->expr->get_lvalue(),
1730                                                symtab, env );
1731                                        std::cerr << "Considering initialization:";
1732                                        std::cerr << std::endl << "  FROM: " << cand->expr->result << std::endl;
1733                                        std::cerr << std::endl << "  TO: "   << toType             << std::endl;
1734                                        std::cerr << std::endl << "  Unification " << (canUnify ? "succeeded" : "failed");
1735                                        std::cerr << std::endl << "  Legacy cost " << legacyCost;
1736                                        std::cerr << std::endl << "  New cost " << thisCost;
1737                                        std::cerr << std::endl;
1738                                )
1739                                if ( thisCost != Cost::infinity ) {
1740                                        // count one safe conversion for each value that is thrown away
1741                                        thisCost.incSafe( discardedValues );
1742                                        if ( cand->cost < minExprCost || ( cand->cost == minExprCost && thisCost < minCastCost ) ) {
1743                                                minExprCost = cand->cost;
1744                                                minCastCost = thisCost;
1745                                                matches.clear();
1746                                        }
1747                                        // ambiguous case, still output candidates to print in error message
1748                                        if ( cand->cost == minExprCost && thisCost == minCastCost ) {
1749                                                CandidateRef newCand = std::make_shared<Candidate>(
1750                                                        new ast::InitExpr{
1751                                                                initExpr->location,
1752                                                                restructureCast( cand->expr, toType ),
1753                                                                initAlt.designation },
1754                                                        std::move(env), std::move( open ), std::move( need ), cand->cost + thisCost );
1755                                                // currently assertions are always resolved immediately so this should have no effect.
1756                                                // if this somehow changes in the future (e.g. delayed by indeterminate return type)
1757                                                // we may need to revisit the logic.
1758                                                inferParameters( newCand, matches );
1759                                        }
1760                                }
1761                        }
1762                }
1763
1764                // select first on argument cost, then conversion cost
1765                // CandidateList minArgCost = findMinCost( matches );
1766                // promoteCvtCost( minArgCost );
1767                // candidates = findMinCost( minArgCost );
1768                candidates = std::move(matches);
1769        }
1770
1771        // size_t Finder::traceId = Stats::Heap::new_stacktrace_id("Finder");
1772        /// Prunes a list of candidates down to those that have the minimum conversion cost for a given
1773        /// return type. Skips ambiguous candidates.
1774
1775} // anonymous namespace
1776
1777bool CandidateFinder::pruneCandidates( CandidateList & candidates, CandidateList & out, std::vector<std::string> & errors ) {
1778        struct PruneStruct {
1779                CandidateRef candidate;
1780                bool ambiguous;
1781
1782                PruneStruct() = default;
1783                PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}
1784        };
1785
1786        // find lowest-cost candidate for each type
1787        std::unordered_map< std::string, PruneStruct > selected;
1788        // attempt to skip satisfyAssertions on more expensive alternatives if better options have been found
1789        std::sort(candidates.begin(), candidates.end(), [](const CandidateRef & x, const CandidateRef & y){return x->cost < y->cost;});
1790        for ( CandidateRef & candidate : candidates ) {
1791                std::string mangleName;
1792                {
1793                        ast::ptr< ast::Type > newType = candidate->expr->result;
1794                        assertf(candidate->expr->result, "Result of expression %p for candidate is null", candidate->expr.get());
1795                        candidate->env.apply( newType );
1796                        mangleName = Mangle::mangle( newType );
1797                }
1798
1799                auto found = selected.find( mangleName );
1800                if (found != selected.end() && found->second.candidate->cost < candidate->cost) {
1801                        PRINT(
1802                                std::cerr << "cost " << candidate->cost << " loses to "
1803                                        << found->second.candidate->cost << std::endl;
1804                        )
1805                        continue;
1806                }
1807
1808                // xxx - when do satisfyAssertions produce more than 1 result?
1809                // this should only happen when initial result type contains
1810                // unbound type parameters, then it should never be pruned by
1811                // the previous step, since renameTyVars guarantees the mangled name
1812                // is unique.
1813                CandidateList satisfied;
1814                bool needRecomputeKey = false;
1815                if (candidate->need.empty()) {
1816                        satisfied.emplace_back(candidate);
1817                }
1818                else {
1819                        satisfyAssertions(candidate, context.symtab, satisfied, errors);
1820                        needRecomputeKey = true;
1821                }
1822
1823                for (auto & newCand : satisfied) {
1824                        // recomputes type key, if satisfyAssertions changed it
1825                        if (needRecomputeKey)
1826                        {
1827                                ast::ptr< ast::Type > newType = newCand->expr->result;
1828                                assertf(newCand->expr->result, "Result of expression %p for candidate is null", newCand->expr.get());
1829                                newCand->env.apply( newType );
1830                                mangleName = Mangle::mangle( newType );
1831                        }
1832                        auto found = selected.find( mangleName );
1833                        if ( found != selected.end() ) {
1834                                // tiebreaking by picking the lower cost on CURRENT expression
1835                                // NOTE: this behavior is different from C semantics.
1836                                // Specific remediations are performed for C operators at postvisit(UntypedExpr).
1837                                // Further investigations may take place.
1838                                if ( newCand->cost < found->second.candidate->cost
1839                                        || (newCand->cost == found->second.candidate->cost && newCand->cvtCost < found->second.candidate->cvtCost) ) {
1840                                        PRINT(
1841                                                std::cerr << "cost " << newCand->cost << " beats "
1842                                                        << found->second.candidate->cost << std::endl;
1843                                        )
1844
1845                                        found->second = PruneStruct{ newCand };
1846                                } else if ( newCand->cost == found->second.candidate->cost && newCand->cvtCost == found->second.candidate->cvtCost ) {
1847                                        // if one of the candidates contains a deleted identifier, can pick the other,
1848                                        // since deleted expressions should not be ambiguous if there is another option
1849                                        // that is at least as good
1850                                        if ( findDeletedExpr( newCand->expr ) ) {
1851                                                // do nothing
1852                                                PRINT( std::cerr << "candidate is deleted" << std::endl; )
1853                                        } else if ( findDeletedExpr( found->second.candidate->expr ) ) {
1854                                                PRINT( std::cerr << "current is deleted" << std::endl; )
1855                                                found->second = PruneStruct{ newCand };
1856                                        } else {
1857                                                PRINT( std::cerr << "marking ambiguous" << std::endl; )
1858                                                found->second.ambiguous = true;
1859                                        }
1860                                } else {
1861                                        // xxx - can satisfyAssertions increase the cost?
1862                                        PRINT(
1863                                                std::cerr << "cost " << newCand->cost << " loses to "
1864                                                        << found->second.candidate->cost << std::endl;
1865                                        )
1866                                }
1867                        } else {
1868                                selected.emplace_hint( found, mangleName, newCand );
1869                        }
1870                }
1871        }
1872
1873        // report unambiguous min-cost candidates
1874        // CandidateList out;
1875        for ( auto & target : selected ) {
1876                if ( target.second.ambiguous ) continue;
1877
1878                CandidateRef cand = target.second.candidate;
1879
1880                ast::ptr< ast::Type > newResult = cand->expr->result;
1881                cand->env.applyFree( newResult );
1882                cand->expr = ast::mutate_field(
1883                        cand->expr.get(), &ast::Expr::result, std::move( newResult ) );
1884
1885                out.emplace_back( cand );
1886        }
1887        // if everything is lost in satisfyAssertions, report the error
1888        return !selected.empty();
1889}
1890
1891void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {
1892        // Find alternatives for expression
1893        ast::Pass<Finder> finder{ *this };
1894        expr->accept( finder );
1895
1896        if ( mode.failFast && candidates.empty() ) {
1897                switch(finder.core.reason.code) {
1898                case Finder::NotFound:
1899                        { SemanticError( expr, "No alternatives for expression " ); break; }
1900                case Finder::NoMatch:
1901                        { SemanticError( expr, "Invalid application of existing declaration(s) in expression " ); break; }
1902                case Finder::ArgsToFew:
1903                case Finder::ArgsToMany:
1904                case Finder::RetsToFew:
1905                case Finder::RetsToMany:
1906                case Finder::NoReason:
1907                default:
1908                        { SemanticError( expr->location, "No reasonable alternatives for expression : reasons unkown" ); }
1909                }
1910        }
1911
1912        /*
1913        if ( mode.satisfyAssns || mode.prune ) {
1914                // trim candidates to just those where the assertions are satisfiable
1915                // - necessary pre-requisite to pruning
1916                CandidateList satisfied;
1917                std::vector< std::string > errors;
1918                for ( CandidateRef & candidate : candidates ) {
1919                        satisfyAssertions( candidate, localSyms, satisfied, errors );
1920                }
1921
1922                // fail early if none such
1923                if ( mode.failFast && satisfied.empty() ) {
1924                        std::ostringstream stream;
1925                        stream << "No alternatives with satisfiable assertions for " << expr << "\n";
1926                        for ( const auto& err : errors ) {
1927                                stream << err;
1928                        }
1929                        SemanticError( expr->location, stream.str() );
1930                }
1931
1932                // reset candidates
1933                candidates = move( satisfied );
1934        }
1935        */
1936
1937        // optimization: don't prune for NameExpr since it never has cost
1938        if ( mode.prune && !dynamic_cast<const ast::NameExpr *>(expr) ) {
1939                // trim candidates to single best one
1940                PRINT(
1941                        std::cerr << "alternatives before prune:" << std::endl;
1942                        print( std::cerr, candidates );
1943                )
1944
1945                CandidateList pruned;
1946                std::vector<std::string> errors;
1947                bool found = pruneCandidates( candidates, pruned, errors );
1948
1949                if ( mode.failFast && pruned.empty() ) {
1950                        std::ostringstream stream;
1951                        if (found) {
1952                                CandidateList winners = findMinCost( candidates );
1953                                stream << "Cannot choose between " << winners.size() << " alternatives for "
1954                                        "expression\n";
1955                                ast::print( stream, expr );
1956                                stream << " Alternatives are:\n";
1957                                print( stream, winners, 1 );
1958                                SemanticError( expr->location, stream.str() );
1959                        }
1960                        else {
1961                                stream << "No alternatives with satisfiable assertions for " << expr << "\n";
1962                                for ( const auto& err : errors ) {
1963                                        stream << err;
1964                                }
1965                                SemanticError( expr->location, stream.str() );
1966                        }
1967                }
1968
1969                auto oldsize = candidates.size();
1970                candidates = std::move( pruned );
1971
1972                PRINT(
1973                        std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
1974                )
1975                PRINT(
1976                        std::cerr << "there are " << candidates.size() << " alternatives after elimination"
1977                                << std::endl;
1978                )
1979        }
1980
1981        // adjust types after pruning so that types substituted by pruneAlternatives are correctly
1982        // adjusted
1983        if ( mode.adjust ) {
1984                for ( CandidateRef & r : candidates ) {
1985                        r->expr = ast::mutate_field(
1986                                r->expr.get(), &ast::Expr::result,
1987                                adjustExprType( r->expr->result, r->env, context.symtab ) );
1988                }
1989        }
1990
1991        // Central location to handle gcc extension keyword, etc. for all expressions
1992        for ( CandidateRef & r : candidates ) {
1993                if ( r->expr->extension != expr->extension ) {
1994                        r->expr.get_and_mutate()->extension = expr->extension;
1995                }
1996        }
1997}
1998
1999std::vector< CandidateFinder > CandidateFinder::findSubExprs(
2000        const std::vector< ast::ptr< ast::Expr > > & xs
2001) {
2002        std::vector< CandidateFinder > out;
2003
2004        for ( const auto & x : xs ) {
2005                out.emplace_back( context, env );
2006                out.back().find( x, ResolvMode::withAdjustment() );
2007
2008                PRINT(
2009                        std::cerr << "findSubExprs" << std::endl;
2010                        print( std::cerr, out.back().candidates );
2011                )
2012        }
2013
2014        return out;
2015}
2016
2017const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost ) {
2018        if ( expr->result.as< ast::ReferenceType >() ) {
2019                // cast away reference from expr
2020                cost.incReference();
2021                return new ast::CastExpr{ expr, expr->result->stripReferences() };
2022        }
2023
2024        return expr;
2025}
2026
2027Cost computeConversionCost(
2028        const ast::Type * argType, const ast::Type * paramType, bool argIsLvalue,
2029        const ast::SymbolTable & symtab, const ast::TypeEnvironment & env
2030) {
2031        PRINT(
2032                std::cerr << std::endl << "converting ";
2033                ast::print( std::cerr, argType, 2 );
2034                std::cerr << std::endl << " to ";
2035                ast::print( std::cerr, paramType, 2 );
2036                std::cerr << std::endl << "environment is: ";
2037                ast::print( std::cerr, env, 2 );
2038                std::cerr << std::endl;
2039        )
2040        Cost convCost = conversionCost( argType, paramType, argIsLvalue, symtab, env );
2041        PRINT(
2042                std::cerr << std::endl << "cost is " << convCost << std::endl;
2043        )
2044        if ( convCost == Cost::infinity ) return convCost;
2045        convCost.incPoly( polyCost( paramType, symtab, env ) + polyCost( argType, symtab, env ) );
2046        PRINT(
2047                std::cerr << "cost with polycost is " << convCost << std::endl;
2048        )
2049        return convCost;
2050}
2051
2052} // namespace ResolvExpr
2053
2054// Local Variables: //
2055// tab-width: 4 //
2056// mode: c++ //
2057// compile-command: "make install" //
2058// End: //
Note: See TracBrowser for help on using the repository browser.