Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/ResolvExpr/CandidateFinder.cpp

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