source: src/ResolvExpr/CandidateFinder.cpp @ 2b01f8e

ADTast-experimental
Last change on this file since 2b01f8e was 5bf3976, checked in by Andrew Beach <ajbeach@…>, 21 months ago

Header Clean-Up: Created new headers for new AST typeops and moved declarations.

  • Property mode set to 100644
File size: 68.9 KB
RevLine 
[99d4584]1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// CandidateFinder.cpp --
8//
9// Author           : Aaron B. Moss
10// Created On       : Wed Jun 5 14:30:00 2019
[cf32116]11// Last Modified By : Andrew Beach
[39d8950]12// Last Modified On : Wed Mar 16 11:58:00 2022
13// Update Count     : 3
[99d4584]14//
15
16#include "CandidateFinder.hpp"
17
[432ce7a]18#include <deque>
[4b7cce6]19#include <iterator>               // for back_inserter
[396037d]20#include <sstream>
[d57e349]21#include <string>
22#include <unordered_map>
[432ce7a]23#include <vector>
[396037d]24
[5bf3976]25#include "AdjustExprType.hpp"
[396037d]26#include "Candidate.hpp"
[5bf3976]27#include "CastCost.hpp"           // for castCost
[396037d]28#include "CompilationState.h"
[fed6a0f]29#include "ConversionCost.h"       // for conversionCast
[d57e349]30#include "Cost.h"
[432ce7a]31#include "ExplodedArg.hpp"
[5bf3976]32#include "PolyCost.hpp"
[898ae07]33#include "RenameVars.h"           // for renameTyVars
[d57e349]34#include "Resolver.h"
[c8e4d2f8]35#include "ResolveTypeof.h"
[396037d]36#include "SatisfyAssertions.hpp"
[5bf3976]37#include "SpecCost.hpp"
38#include "typeops.h"              // for combos
[4b7cce6]39#include "Unify.h"
[99d4584]40#include "AST/Expr.hpp"
[396037d]41#include "AST/Node.hpp"
42#include "AST/Pass.hpp"
[d57e349]43#include "AST/Print.hpp"
[4b7cce6]44#include "AST/SymbolTable.hpp"
[432ce7a]45#include "AST/Type.hpp"
[c1ed2ee]46#include "Common/utility.h"       // for move, copy
[d57e349]47#include "SymTab/Mangler.h"
[432ce7a]48#include "Tuples/Tuples.h"        // for handleTupleAssignment
[e5c3811]49#include "InitTweak/InitTweak.h"  // for getPointerBase
50
51#include "Common/Stats/Counter.h"
[396037d]52
53#define PRINT( text ) if ( resolvep ) { text }
[99d4584]54
55namespace ResolvExpr {
56
[9d5089e]57const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost ) {
58        if ( expr->result.as< ast::ReferenceType >() ) {
59                // cast away reference from expr
60                cost.incReference();
[b8524ca]61                return new ast::CastExpr{ expr, expr->result->stripReferences() };
[9d5089e]62        }
[2890212]63
[9d5089e]64        return expr;
65}
66
67/// Unique identifier for matching expression resolutions to their requesting expression
68UniqueId globalResnSlot = 0;
[396037d]69
[2890212]70Cost computeConversionCost(
[cf32116]71        const ast::Type * argType, const ast::Type * paramType, bool argIsLvalue,
72        const ast::SymbolTable & symtab, const ast::TypeEnvironment & env
[b69233ac]73) {
74        PRINT(
75                std::cerr << std::endl << "converting ";
76                ast::print( std::cerr, argType, 2 );
77                std::cerr << std::endl << " to ";
78                ast::print( std::cerr, paramType, 2 );
79                std::cerr << std::endl << "environment is: ";
80                ast::print( std::cerr, env, 2 );
81                std::cerr << std::endl;
82        )
[cf32116]83        Cost convCost = conversionCost( argType, paramType, argIsLvalue, symtab, env );
[b69233ac]84        PRINT(
85                std::cerr << std::endl << "cost is " << convCost << std::endl;
86        )
87        if ( convCost == Cost::infinity ) return convCost;
88        convCost.incPoly( polyCost( paramType, symtab, env ) + polyCost( argType, symtab, env ) );
89        PRINT(
90                std::cerr << "cost with polycost is " << convCost << std::endl;
91        )
92        return convCost;
93}
94
[9d5089e]95namespace {
[432ce7a]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
[9d5089e]115        /// Computes conversion cost for a given expression to a given type
[2890212]116        const ast::Expr * computeExpressionConversionCost(
117                const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost
[9d5089e]118        ) {
[cf32116]119                Cost convCost = computeConversionCost(
120                                arg->result, paramType, arg->get_lvalue(), symtab, env );
[9d5089e]121                outCost += convCost;
122
[2890212]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
[9d5089e]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 );
[b8524ca]131                        return new ast::CastExpr{ arg, newType };
[9d5089e]132
[2890212]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,
[9d5089e]135                        // once this is fixed it should be possible to resolve the cast.
[2890212]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
[9d5089e]138                        // commontype(zero_t, DT*) is DT*, rather than nothing
139
140                        // CandidateFinder finder{ symtab, env };
141                        // finder.find( arg, ResolvMode::withAdjustment() );
[2890212]142                        // assertf( finder.candidates.size() > 0,
[9d5089e]143                        //      "Somehow castable expression failed to find alternatives." );
[2890212]144                        // assertf( finder.candidates.size() == 1,
[9d5089e]145                        //      "Somehow got multiple alternatives for known cast expression." );
146                        // return finder.candidates.front()->expr;
147                }
148
149                return arg;
150        }
151
[432ce7a]152        /// Computes conversion cost for a given candidate
[2890212]153        Cost computeApplicationConversionCost(
154                CandidateRef cand, const ast::SymbolTable & symtab
[432ce7a]155        ) {
[9d5089e]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();
[2890212]177                                        PRINT( std::cerr << "end of params with varargs function: inc unsafe: "
[9d5089e]178                                                << convCost << std::endl; ; )
179                                        // convert reference-typed expressions into value-typed expressions
[2890212]180                                        cand->expr = ast::mutate_field_index(
181                                                appExpr, &ast::ApplicationExpr::args, i,
[9d5089e]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
[2890212]190                                cand->expr = ast::mutate_field_index(
[9d5089e]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
[954c954]197                        // const ast::Type * paramType = (*param)->get_type();
[2890212]198                        cand->expr = ast::mutate_field_index(
199                                appExpr, &ast::ApplicationExpr::args, i,
200                                computeExpressionConversionCost(
[954c954]201                                        args[i], *param, symtab, cand->env, convCost ) );
202                        convCost.decSpec( specCost( *param ) );
[9d5089e]203                        ++param;  // can't be in for-loop update because of the continue
204                }
205
206                if ( param != params.end() ) return Cost::infinity;
207
[2890212]208                // specialization cost of return types can't be accounted for directly, it disables
[9d5089e]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() );
[3e5dd913]218                convCost.decSpec( function->assertions.size() );
[9d5089e]219
220                return convCost;
221        }
222
[2890212]223        void makeUnifiableVars(
[361bf01]224                const ast::FunctionType * type, ast::OpenVarSet & unifiableVars,
[2890212]225                ast::AssertionSet & need
[9d5089e]226        ) {
[3e5dd913]227                for ( auto & tyvar : type->forall ) {
[93c10de]228                        unifiableVars[ *tyvar ] = ast::TypeData{ tyvar->base };
[3e5dd913]229                }
230                for ( auto & assn : type->assertions ) {
231                        need[ assn ].isUsed = true;
[9d5089e]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()
[2890212]262                : parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ),
[9d5089e]263                  tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}
[2890212]264
265                ArgPack(
266                        const ast::TypeEnvironment & env, const ast::AssertionSet & need,
[9d5089e]267                        const ast::AssertionSet & have, const ast::OpenVarSet & open )
[2890212]268                : parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ),
[9d5089e]269                  open( open ), nextArg( 0 ), tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}
[2890212]270
[9d5089e]271                ArgPack(
[2890212]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,
[9d5089e]275                        unsigned nextExpl = 0, unsigned explAlt = 0 )
[09f34a84]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 ),
[9d5089e]278                  nextExpl( nextExpl ), explAlt( explAlt ) {}
[2890212]279
[9d5089e]280                ArgPack(
[2890212]281                        const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need,
[9d5089e]282                        ast::AssertionSet && have, ast::OpenVarSet && open, unsigned nextArg, Cost added )
[09f34a84]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 ),
[9d5089e]285                  tupleStart( o.tupleStart ), nextExpl( 0 ), explAlt( 0 ) {}
[2890212]286
[9d5089e]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                }
[2890212]294
[9d5089e]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() );
[09f34a84]308                        expr = new ast::TupleExpr{ expr->location, std::move( exprv ) };
[9d5089e]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
[2890212]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
[9d5089e]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
[2890212]326                                if ( ! instantiateArgument(
[9d5089e]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
[2890212]337
[9d5089e]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;
[2890212]350
[9d5089e]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 ),
[2890212]360                                                        copy( results[i].need ), copy( results[i].have ),
[9d5089e]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;
[417117e]378                                                        newResult.expr = new ast::TupleExpr{ CodeLocation{}, {} };
[9d5089e]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
[2890212]406                                                if (
407                                                        unify(
[9d5089e]408                                                                ttype, argType, newResult.env, newResult.need, newResult.have,
[2890212]409                                                                newResult.open, symtab )
[9d5089e]410                                                ) {
[09f34a84]411                                                        finalResults.emplace_back( std::move( newResult ) );
[9d5089e]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(
[09f34a84]430                                                                results[i], std::move( env ), copy( results[i].need ),
431                                                                copy( results[i].have ), std::move( open ), nextArg + 1, expl.cost );
[2890212]432
[9d5089e]433                                                        continue;
434                                                }
435
436                                                // add new result
437                                                results.emplace_back(
[09f34a84]438                                                        i, expl.exprs.front(), std::move( env ), copy( results[i].need ),
439                                                        copy( results[i].have ), std::move( open ), nextArg + 1, nTuples,
[9d5089e]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 ) {
[09f34a84]451                                results.emplace_back( std::move( finalResults[i] ) );
[9d5089e]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(
[09f34a84]485                                                i, expr, std::move( env ), std::move( need ), std::move( have ), std::move( open ), nextArg,
[9d5089e]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(
[09f34a84]501                                                        i, new ast::DefaultArgExpr{ cnst->location, cnst }, std::move( env ),
502                                                        std::move( need ), std::move( have ), std::move( open ), nextArg, nTuples );
[9d5089e]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(
[09f34a84]523                                                results[i], std::move( env ), std::move( need ), std::move( have ), std::move( open ),
[9d5089e]524                                                nextArg + 1, expl.cost );
[2890212]525
[9d5089e]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(
[09f34a84]545                                                i, expr, std::move( env ), std::move( need ), std::move( have ), std::move( open ),
[9d5089e]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
[e0e9a0b]554                return genEnd != results.size();  // were any new results added?
[432ce7a]555        }
556
[c8e4d2f8]557        /// Generate a cast expression from `arg` to `toType`
[2890212]558        const ast::Expr * restructureCast(
[17a0ede2]559                ast::ptr< ast::Expr > & arg, const ast::Type * toType, ast::GeneratedFlag isGenerated = ast::GeneratedCast
[898ae07]560        ) {
[2890212]561                if (
562                        arg->result->size() > 1
563                        && ! toType->isVoid()
564                        && ! dynamic_cast< const ast::ReferenceType * >( toType )
[898ae07]565                ) {
[2890212]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
[898ae07]570                        // UniqueExpr ensures that the side effects will still be produced)
571                        if ( Tuples::maybeImpureIgnoreUnique( arg ) ) {
[2890212]572                                // expressions which may contain side effects require a single unique instance of
[898ae07]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 };
[2890212]580                                components.emplace_back(
[898ae07]581                                        restructureCast( idx, toType->getComponent( i ), isGenerated ) );
582                        }
[09f34a84]583                        return new ast::TupleExpr{ arg->location, std::move( components ) };
[898ae07]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;
[c8e4d2f8]597        }
598
[396037d]599        /// Actually visits expressions to find their candidate interpretations
[9ea38de]600        class Finder final : public ast::WithShortCircuiting {
[39d8950]601                const ResolveContext & context;
[396037d]602                const ast::SymbolTable & symtab;
[9ea38de]603        public:
[943bfad]604                // static size_t traceId;
[9ea38de]605                CandidateFinder & selfFinder;
[396037d]606                CandidateList & candidates;
607                const ast::TypeEnvironment & tenv;
608                ast::ptr< ast::Type > & targetType;
609
[71d6bd8]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
[396037d]624                Finder( CandidateFinder & f )
[39d8950]625                : context( f.context ), symtab( context.symtab ), selfFinder( f ),
626                  candidates( f.candidates ), tenv( f.env ), targetType( f.targetType ) {}
[2890212]627
[4b7cce6]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 )... } );
[71d6bd8]634                        reason.code = NoReason;
[4b7cce6]635                }
636
637                void postvisit( const ast::ApplicationExpr * applicationExpr ) {
638                        addCandidate( applicationExpr, tenv );
639                }
640
[9d5089e]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
[2890212]663                void validateFunctionCandidate(
664                        const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results,
665                        CandidateList & out
[9d5089e]666                ) {
[2890212]667                        ast::ApplicationExpr * appExpr =
[9d5089e]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() );
[09f34a84]679                        appExpr->args = std::move( vargs );
[9d5089e]680                        // build and validate new candidate
[2890212]681                        auto newCand =
[9d5089e]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
[432ce7a]691                /// Builds a list of candidates for a function, storing them in out
692                void makeFunctionCandidates(
[2890212]693                        const CandidateRef & func, const ast::FunctionType * funcType,
[432ce7a]694                        const ExplodedArgs_new & args, CandidateList & out
695                ) {
[9d5089e]696                        ast::OpenVarSet funcOpen;
697                        ast::AssertionSet funcNeed, funcHave;
698                        ast::TypeEnvironment funcEnv{ func->env };
699                        makeUnifiableVars( funcType, funcOpen, funcNeed );
[2890212]700                        // add all type variables as open variables now so that those not used in the
[e0e9a0b]701                        // parameter list are still considered open
[9d5089e]702                        funcEnv.add( funcType->forall );
703
704                        if ( targetType && ! targetType->isVoid() && ! funcType->returns.empty() ) {
705                                // attempt to narrow based on expected target type
[954c954]706                                const ast::Type * returnType = funcType->returns.front();
[2890212]707                                if ( ! unify(
708                                        returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, symtab )
[9d5089e]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
[954c954]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 ) {
[2890212]736                                // Try adding the arguments corresponding to the current parameter to the existing
[9d5089e]737                                // matches
[954c954]738                                // no default args for indirect calls
[2890212]739                                if ( ! instantiateArgument(
[954c954]740                                        param, nullptr, args, results, genStart, symtab ) ) return;
[9d5089e]741                        }
742
[954c954]743                        endMatch:
[9d5089e]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(
[09f34a84]790                                                                        results[i], std::move( env ), copy( results[i].need ),
791                                                                        copy( results[i].have ), std::move( open ), nextArg + 1,
[9d5089e]792                                                                        expl.cost );
793
794                                                                continue;
795                                                        }
796
797                                                        // add new result
798                                                        results.emplace_back(
[09f34a84]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,
[9d5089e]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                        }
[4b7cce6]816                }
817
[432ce7a]818                /// Adds implicit struct-conversions to the alternative list
819                void addAnonConversions( const CandidateRef & cand ) {
[2890212]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
[c8e4d2f8]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 );
[2890212]826
[c8e4d2f8]827                        if ( aggrType.as< ast::ReferenceType >() ) {
[b8524ca]828                                aggrExpr = new ast::CastExpr{ aggrExpr, aggrType->stripReferences() };
[c8e4d2f8]829                        }
830
831                        if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) {
[898ae07]832                                addAggMembers( structInst, aggrExpr, *cand, Cost::safe, "" );
[c8e4d2f8]833                        } else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) {
[898ae07]834                                addAggMembers( unionInst, aggrExpr, *cand, Cost::safe, "" );
[c8e4d2f8]835                        }
836                }
837
838                /// Adds aggregate member interpretations
[2890212]839                void addAggMembers(
[98e8b3b]840                        const ast::BaseInstType * aggrInst, const ast::Expr * expr,
[2890212]841                        const Candidate & cand, const Cost & addedCost, const std::string & name
[c8e4d2f8]842                ) {
843                        for ( const ast::Decl * decl : aggrInst->lookup( name ) ) {
844                                auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl );
[2890212]845                                CandidateRef newCand = std::make_shared<Candidate>(
[898ae07]846                                        cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost );
[2890212]847                                // add anonymous member interpretations whenever an aggregate value type is seen
[c8e4d2f8]848                                // as a member expression
849                                addAnonConversions( newCand );
[09f34a84]850                                candidates.emplace_back( std::move( newCand ) );
[c8e4d2f8]851                        }
[432ce7a]852                }
853
[898ae07]854                /// Adds tuple member interpretations
[2890212]855                void addTupleMembers(
856                        const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand,
857                        const Cost & addedCost, const ast::Expr * member
[898ae07]858                ) {
859                        if ( auto constantExpr = dynamic_cast< const ast::ConstantExpr * >( member ) ) {
[2890212]860                                // get the value of the constant expression as an int, must be between 0 and the
[898ae07]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(
[2890212]865                                                cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val },
[898ae07]866                                                addedCost );
867                                }
868                        }
869                }
870
[432ce7a]871                void postvisit( const ast::UntypedExpr * untypedExpr ) {
[2890212]872                        std::vector< CandidateFinder > argCandidates =
[432ce7a]873                                selfFinder.findSubExprs( untypedExpr->args );
[2890212]874
[432ce7a]875                        // take care of possible tuple assignments
876                        // if not tuple assignment, handled as normal function call
877                        Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates );
878
[39d8950]879                        CandidateFinder funcFinder( context, tenv );
[e5c3811]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                                                }
[943bfad]897
[e5c3811]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
[d958834b]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                                                // }
[e5c3811]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.
[0536c03]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 );
[e5c3811]928                        // short-circuit if no candidates
929                        // if ( funcFinder.candidates.empty() ) return;
930
931                        reason.code = NoMatch;
932
[432ce7a]933                        // find function operators
[fc134a48]934                        ast::ptr< ast::Expr > opExpr = new ast::NameExpr{ untypedExpr->location, "?()" }; // ??? why not ?{}
[39d8950]935                        CandidateFinder opFinder( context, tenv );
[432ce7a]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 } };
[2890212]966                                                        newFunc->expr =
[432ce7a]967                                                                referenceToRvalueConversion( newFunc->expr, newFunc->cost );
968                                                        makeFunctionCandidates( newFunc, function, argExpansions, found );
969                                                }
[2890212]970                                        } else if (
971                                                auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult )
[432ce7a]972                                        ) {
[3e5dd913]973                                                if ( const ast::EqvClass * clz = func->env.lookup( *inst ) ) {
[432ce7a]974                                                        if ( auto function = clz->bound.as< ast::FunctionType >() ) {
975                                                                CandidateRef newFunc{ new Candidate{ *func } };
[2890212]976                                                                newFunc->expr =
[432ce7a]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() );
[2890212]990                                for ( const CandidateRef & func : funcFinder ) {
[432ce7a]991                                        funcE.emplace_back( *func, symtab );
992                                }
[09f34a84]993                                argExpansions.emplace_front( std::move( funcE ) );
[432ce7a]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} };
[2890212]1002                                                                newOp->expr =
[432ce7a]1003                                                                        referenceToRvalueConversion( newOp->expr, newOp->cost );
1004                                                                makeFunctionCandidates( newOp, function, argExpansions, found );
1005                                                        }
1006                                                }
1007                                        } catch ( SemanticErrorException & e ) { errors.append( e ); }
1008                                }
1009                        }
1010
[2890212]1011                        // Implement SFINAE; resolution errors are only errors if there aren't any non-error
[432ce7a]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 >();
[2890212]1023
[432ce7a]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;
[09f34a84]1037                                        candidates.emplace_back( std::move( withFunc ) );
[432ce7a]1038                                }
1039                        }
[09f34a84]1040                        found = std::move( candidates );
[432ce7a]1041
1042                        // use a new list so that candidates are not examined by addAnonConversions twice
1043                        CandidateList winners = findMinCost( found );
1044                        promoteCvtCost( winners );
1045
[2890212]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
[432ce7a]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() ) {
[2890212]1055                                // If resolution is unsuccessful with a target type, try again without, since it
[432ce7a]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
[4b7cce6]1070                /// true if expression is an lvalue
1071                static bool isLvalue( const ast::Expr * x ) {
[cf32116]1072                        return x->result && ( x->get_lvalue() || x->result.as< ast::ReferenceType >() );
[4b7cce6]1073                }
1074
1075                void postvisit( const ast::AddressExpr * addressExpr ) {
[39d8950]1076                        CandidateFinder finder( context, tenv );
[4b7cce6]1077                        finder.find( addressExpr->arg );
[71d6bd8]1078
1079                        if( finder.candidates.empty() ) return;
1080
1081                        reason.code = NoMatch;
1082
[4b7cce6]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 ) {
[c8e4d2f8]1094                        ast::ptr< ast::Type > toType = castExpr->result;
1095                        assert( toType );
[39d8950]1096                        toType = resolveTypeof( toType, context );
[c8e4d2f8]1097                        toType = adjustExprType( toType, tenv, symtab );
1098
[39d8950]1099                        CandidateFinder finder( context, tenv, toType );
[c8e4d2f8]1100                        finder.find( castExpr->arg, ResolvMode::withAdjustment() );
1101
[71d6bd8]1102                        if( !finder.candidates.empty() ) reason.code = NoMatch;
1103
[c8e4d2f8]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
[2890212]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
[c8e4d2f8]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 );
[943bfad]1120                                Cost thisCost =
[bb87dd0]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
[c8e4d2f8]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 );
[2890212]1136                                        CandidateRef newCand = std::make_shared<Candidate>(
1137                                                restructureCast( cand->expr, toType, castExpr->isGenerated ),
[09f34a84]1138                                                copy( cand->env ), std::move( open ), std::move( need ), cand->cost,
[c8e4d2f8]1139                                                cand->cost + thisCost );
1140                                        inferParameters( newCand, matches );
1141                                }
1142                        }
1143
[898ae07]1144                        // select first on argument cost, then conversion cost
1145                        CandidateList minArgCost = findMinCost( matches );
1146                        promoteCvtCost( minArgCost );
1147                        candidates = findMinCost( minArgCost );
[4b7cce6]1148                }
1149
1150                void postvisit( const ast::VirtualCastExpr * castExpr ) {
1151                        assertf( castExpr->result, "Implicit virtual cast targets not yet supported." );
[39d8950]1152                        CandidateFinder finder( context, tenv );
[4b7cce6]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 ) {
[2890212]1156                                addCandidate(
1157                                        *r,
[c8e4d2f8]1158                                        new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );
[4b7cce6]1159                        }
1160                }
1161
[4ef08f7]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
[39d8950]1169                        CandidateFinder finder( context, tenv );
[4ef08f7]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)) {
[3e5dd913]1181                                                auto td = cand->env.lookup(*insttype);
[4ef08f7]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 {
[7f62b708]1196                                // Attempt 1 : turn (thread&)X into (thread$&)X.__thrd
[4ef08f7]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
[7f62b708]1207                        // Fallback : turn (thread&)X into (thread$&)get_thread(X)
[4ef08f7]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
[4b7cce6]1217                void postvisit( const ast::UntypedMemberExpr * memberExpr ) {
[39d8950]1218                        CandidateFinder aggFinder( context, tenv );
[898ae07]1219                        aggFinder.find( memberExpr->aggregate, ResolvMode::withAdjustment() );
1220                        for ( CandidateRef & agg : aggFinder.candidates ) {
[2890212]1221                                // it's okay for the aggregate expression to have reference type -- cast it to the
[898ae07]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 >() ) {
[2890212]1228                                        addAggMembers(
[898ae07]1229                                                structInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );
1230                                } else if ( auto unionInst = agg->expr->result.as< ast::UnionInstType >() ) {
[2890212]1231                                        addAggMembers(
[898ae07]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                        }
[4b7cce6]1237                }
1238
1239                void postvisit( const ast::MemberExpr * memberExpr ) {
1240                        addCandidate( memberExpr, tenv );
1241                }
1242
[898ae07]1243                void postvisit( const ast::NameExpr * nameExpr ) {
[e5c3811]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                        }
[898ae07]1257                        PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )
[e5c3811]1258
[71d6bd8]1259                        if( declList.empty() ) return;
1260
1261                        reason.code = NoMatch;
1262
[898ae07]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>(
[2890212]1268                                        newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, Cost::zero,
[898ae07]1269                                        cost );
[9e23b446]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
[898ae07]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                                )
[2890212]1286                                newCand->expr = ast::mutate_field(
1287                                        newCand->expr.get(), &ast::Expr::result,
[898ae07]1288                                        renameTyVars( newCand->expr->result ) );
[2890212]1289                                // add anonymous member interpretations whenever an aggregate value type is seen
[898ae07]1290                                // as a name expression
1291                                addAnonConversions( newCand );
[09f34a84]1292                                candidates.emplace_back( std::move( newCand ) );
[898ae07]1293                        }
[4b7cce6]1294                }
1295
1296                void postvisit( const ast::VariableExpr * variableExpr ) {
1297                        // not sufficient to just pass `variableExpr` here, type might have changed since
1298                        // creation
[2890212]1299                        addCandidate(
[4b7cce6]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 ) {
[898ae07]1308                        if ( sizeofExpr->type ) {
[2890212]1309                                addCandidate(
1310                                        new ast::SizeofExpr{
[39d8950]1311                                                sizeofExpr->location, resolveTypeof( sizeofExpr->type, context ) },
[898ae07]1312                                        tenv );
1313                        } else {
1314                                // find all candidates for the argument to sizeof
[39d8950]1315                                CandidateFinder finder( context, tenv );
[898ae07]1316                                finder.find( sizeofExpr->expr );
1317                                // find the lowest-cost candidate, otherwise ambiguous
1318                                CandidateList winners = findMinCost( finder.candidates );
1319                                if ( winners.size() != 1 ) {
[2890212]1320                                        SemanticError(
[898ae07]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                        }
[4b7cce6]1329                }
1330
1331                void postvisit( const ast::AlignofExpr * alignofExpr ) {
[898ae07]1332                        if ( alignofExpr->type ) {
[2890212]1333                                addCandidate(
1334                                        new ast::AlignofExpr{
[39d8950]1335                                                alignofExpr->location, resolveTypeof( alignofExpr->type, context ) },
[898ae07]1336                                        tenv );
1337                        } else {
1338                                // find all candidates for the argument to alignof
[39d8950]1339                                CandidateFinder finder( context, tenv );
[898ae07]1340                                finder.find( alignofExpr->expr );
1341                                // find the lowest-cost candidate, otherwise ambiguous
1342                                CandidateList winners = findMinCost( finder.candidates );
1343                                if ( winners.size() != 1 ) {
[2890212]1344                                        SemanticError(
[898ae07]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;
[2890212]1351                                addCandidate(
[898ae07]1352                                        *choice, new ast::AlignofExpr{ alignofExpr->location, choice->expr } );
1353                        }
[4b7cce6]1354                }
1355
1356                void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {
[98e8b3b]1357                        const ast::BaseInstType * aggInst;
[898ae07]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 );
[2890212]1364                                addCandidate(
[898ae07]1365                                        new ast::OffsetofExpr{ offsetofExpr->location, aggInst, dwt }, tenv );
1366                        }
[4b7cce6]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 ) {
[39d8950]1378                        CandidateFinder finder1( context, tenv );
[4b7cce6]1379                        finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() );
1380                        if ( finder1.candidates.empty() ) return;
1381
[39d8950]1382                        CandidateFinder finder2( context, tenv );
[4b7cce6]1383                        finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() );
1384                        if ( finder2.candidates.empty() ) return;
1385
[71d6bd8]1386                        reason.code = NoMatch;
1387
[4b7cce6]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(
[2890212]1399                                                new ast::LogicalExpr{
[4b7cce6]1400                                                        logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },
[09f34a84]1401                                                std::move( env ), std::move( open ), std::move( need ), r1->cost + r2->cost );
[4b7cce6]1402                                }
1403                        }
1404                }
1405
1406                void postvisit( const ast::ConditionalExpr * conditionalExpr ) {
1407                        // candidates for condition
[39d8950]1408                        CandidateFinder finder1( context, tenv );
[4b7cce6]1409                        finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() );
1410                        if ( finder1.candidates.empty() ) return;
1411
1412                        // candidates for true result
[39d8950]1413                        CandidateFinder finder2( context, tenv );
[4b7cce6]1414                        finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() );
1415                        if ( finder2.candidates.empty() ) return;
1416
1417                        // candidates for false result
[39d8950]1418                        CandidateFinder finder3( context, tenv );
[4b7cce6]1419                        finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() );
1420                        if ( finder3.candidates.empty() ) return;
1421
[71d6bd8]1422                        reason.code = NoMatch;
1423
[4b7cce6]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
[2890212]1439                                                // unify true and false results, then infer parameters to produce new
[4b7cce6]1440                                                // candidates
1441                                                ast::ptr< ast::Type > common;
[2890212]1442                                                if (
1443                                                        unify(
1444                                                                r2->expr->result, r3->expr->result, env, need, have, open, symtab,
1445                                                                common )
[4b7cce6]1446                                                ) {
[898ae07]1447                                                        // generate typed expression
[2890212]1448                                                        ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{
[898ae07]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;
[2890212]1453                                                        newExpr->arg2 = computeExpressionConversionCost(
[898ae07]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>(
[09f34a84]1459                                                                newExpr, std::move( env ), std::move( open ), std::move( need ), cost );
[898ae07]1460                                                        inferParameters( newCand, candidates );
[4b7cce6]1461                                                }
1462                                        }
1463                                }
1464                        }
1465                }
1466
1467                void postvisit( const ast::CommaExpr * commaExpr ) {
1468                        ast::TypeEnvironment env{ tenv };
[39d8950]1469                        ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, context, env );
[2890212]1470
[39d8950]1471                        CandidateFinder finder2( context, env );
[4b7cce6]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 ) {
[39d8950]1484                        CandidateFinder finder( context, tenv );
[4b7cce6]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
[39d8950]1493                        CandidateFinder finder1( context, tenv );
[4b7cce6]1494                        finder1.find( rangeExpr->low, ResolvMode::withAdjustment() );
1495                        if ( finder1.candidates.empty() ) return;
1496
[39d8950]1497                        CandidateFinder finder2( context, tenv );
[4b7cce6]1498                        finder2.find( rangeExpr->high, ResolvMode::withAdjustment() );
1499                        if ( finder2.candidates.empty() ) return;
1500
[71d6bd8]1501                        reason.code = NoMatch;
1502
[4b7cce6]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;
[2890212]1515                                        if (
1516                                                unify(
1517                                                        r1->expr->result, r2->expr->result, env, need, have, open, symtab,
1518                                                        common )
[4b7cce6]1519                                        ) {
[898ae07]1520                                                // generate new expression
[2890212]1521                                                ast::RangeExpr * newExpr =
[4b7cce6]1522                                                        new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };
1523                                                newExpr->result = common ? common : r1->expr->result;
[898ae07]1524                                                // add candidate
1525                                                CandidateRef newCand = std::make_shared<Candidate>(
[09f34a84]1526                                                        newExpr, std::move( env ), std::move( open ), std::move( need ),
[898ae07]1527                                                        r1->cost + r2->cost );
1528                                                inferParameters( newCand, candidates );
[4b7cce6]1529                                        }
1530                                }
1531                        }
1532                }
1533
1534                void postvisit( const ast::UntypedTupleExpr * tupleExpr ) {
[2890212]1535                        std::vector< CandidateFinder > subCandidates =
[4b7cce6]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(
[09f34a84]1555                                        new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) },
1556                                        std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) );
[4b7cce6]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 ) {
[39d8950]1573                        CandidateFinder finder( context, tenv );
[4b7cce6]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 ) {
[39d8950]1582                        addCandidate( resolveStmtExpr( stmtExpr, context ), tenv );
[4b7cce6]1583                }
1584
1585                void postvisit( const ast::UntypedInitExpr * initExpr ) {
[17a0ede2]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
[39d8950]1594                                const ast::Type * toType = resolveTypeof( initAlt.type, context );
[17a0ede2]1595                                toType = adjustExprType( toType, tenv, symtab );
[2890212]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.
[39d8950]1599                                CandidateFinder finder( context, tenv, toType );
[17a0ede2]1600                                finder.find( initExpr->expr, ResolvMode::withAdjustment() );
1601                                for ( CandidateRef & cand : finder.candidates ) {
[71d6bd8]1602                                        if(reason.code == NotFound) reason.code = NoMatch;
1603
[17a0ede2]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
[2890212]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
[17a0ede2]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
[bb87dd0]1620                                        bool canUnify = unify( toType, cand->expr->result, env, need, have, open, symtab );
[0292aa4]1621                                        (void) canUnify;
[ef9988b]1622                                        Cost thisCost = computeConversionCost( cand->expr->result, toType, cand->expr->get_lvalue(),
[bb87dd0]1623                                                symtab, env );
1624                                        PRINT(
1625                                                Cost legacyCost = castCost( cand->expr->result, toType, cand->expr->get_lvalue(),
[cf32116]1626                                                        symtab, env );
[bb87dd0]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                                        )
[17a0ede2]1635                                        if ( thisCost != Cost::infinity ) {
1636                                                // count one safe conversion for each value that is thrown away
1637                                                thisCost.incSafe( discardedValues );
[2890212]1638                                                CandidateRef newCand = std::make_shared<Candidate>(
1639                                                        new ast::InitExpr{
1640                                                                initExpr->location, restructureCast( cand->expr, toType ),
1641                                                                initAlt.designation },
[09f34a84]1642                                                        std::move(env), std::move( open ), std::move( need ), cand->cost, thisCost );
[17a0ede2]1643                                                inferParameters( newCand, matches );
1644                                        }
1645                                }
[e5c3811]1646
[17a0ede2]1647                        }
1648
1649                        // select first on argument cost, then conversion cost
1650                        CandidateList minArgCost = findMinCost( matches );
1651                        promoteCvtCost( minArgCost );
1652                        candidates = findMinCost( minArgCost );
[4b7cce6]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                }
[396037d]1666        };
1667
[0d070ca]1668        // size_t Finder::traceId = Stats::Heap::new_stacktrace_id("Finder");
[2890212]1669        /// Prunes a list of candidates down to those that have the minimum conversion cost for a given
[396037d]1670        /// return type. Skips ambiguous candidates.
[d57e349]1671
[1389810]1672} // anonymous namespace
[d57e349]1673
[1389810]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;
[e3282fe]1711                bool needRecomputeKey = false;
1712                if (candidate->need.empty()) {
1713                        satisfied.emplace_back(candidate);
1714                }
1715                else {
[39d8950]1716                        satisfyAssertions(candidate, context.symtab, satisfied, errors);
[e3282fe]1717                        needRecomputeKey = true;
1718                }
[1389810]1719
1720                for (auto & newCand : satisfied) {
1721                        // recomputes type key, if satisfyAssertions changed it
[e3282fe]1722                        if (needRecomputeKey)
[d57e349]1723                        {
[1389810]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 );
[d57e349]1727                                mangleName = Mangle::mangle( newType );
1728                        }
1729                        auto found = selected.find( mangleName );
1730                        if ( found != selected.end() ) {
[1389810]1731                                if ( newCand->cost < found->second.candidate->cost ) {
[d57e349]1732                                        PRINT(
[1389810]1733                                                std::cerr << "cost " << newCand->cost << " beats "
[d57e349]1734                                                        << found->second.candidate->cost << std::endl;
1735                                        )
1736
[1389810]1737                                        found->second = PruneStruct{ newCand };
1738                                } else if ( newCand->cost == found->second.candidate->cost ) {
[2890212]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
[d57e349]1741                                        // that is at least as good
[1389810]1742                                        if ( findDeletedExpr( newCand->expr ) ) {
[d57e349]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; )
[1389810]1747                                                found->second = PruneStruct{ newCand };
[d57e349]1748                                        } else {
1749                                                PRINT( std::cerr << "marking ambiguous" << std::endl; )
1750                                                found->second.ambiguous = true;
1751                                        }
[943bfad]1752                                } else {
[1389810]1753                                        // xxx - can satisfyAssertions increase the cost?
[d57e349]1754                                        PRINT(
[1389810]1755                                                std::cerr << "cost " << newCand->cost << " loses to "
[d57e349]1756                                                        << found->second.candidate->cost << std::endl;
[943bfad]1757                                        )
[d57e349]1758                                }
1759                        } else {
[1389810]1760                                selected.emplace_hint( found, mangleName, newCand );
[d57e349]1761                        }
1762                }
[1389810]1763        }
[d57e349]1764
[1389810]1765        // report unambiguous min-cost candidates
1766        // CandidateList out;
1767        for ( auto & target : selected ) {
1768                if ( target.second.ambiguous ) continue;
[d57e349]1769
[1389810]1770                CandidateRef cand = target.second.candidate;
[2890212]1771
[1389810]1772                ast::ptr< ast::Type > newResult = cand->expr->result;
1773                cand->env.applyFree( newResult );
1774                cand->expr = ast::mutate_field(
[09f34a84]1775                        cand->expr.get(), &ast::Expr::result, std::move( newResult ) );
[2890212]1776
[1389810]1777                out.emplace_back( cand );
[d57e349]1778        }
[1389810]1779        // if everything is lost in satisfyAssertions, report the error
1780        return !selected.empty();
1781}
[396037d]1782
[99d4584]1783void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {
[396037d]1784        // Find alternatives for expression
1785        ast::Pass<Finder> finder{ *this };
1786        expr->accept( finder );
1787
1788        if ( mode.failFast && candidates.empty() ) {
[7ff3e522]1789                switch(finder.core.reason.code) {
[71d6bd8]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                }
[396037d]1802        }
1803
[1389810]1804        /*
[396037d]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;
[b69233ac]1810                for ( CandidateRef & candidate : candidates ) {
[9ea38de]1811                        satisfyAssertions( candidate, localSyms, satisfied, errors );
[396037d]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
[9d5089e]1825                candidates = move( satisfied );
[396037d]1826        }
[1389810]1827        */
[396037d]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
[1389810]1836                CandidateList pruned;
1837                std::vector<std::string> errors;
1838                bool found = pruneCandidates( candidates, pruned, errors );
[2890212]1839
[396037d]1840                if ( mode.failFast && pruned.empty() ) {
1841                        std::ostringstream stream;
[943bfad]1842                        if (found) {
[1389810]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                        }
[396037d]1858                }
[d57e349]1859
1860                auto oldsize = candidates.size();
[09f34a84]1861                candidates = std::move( pruned );
[d57e349]1862
1863                PRINT(
1864                        std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
1865                )
1866                PRINT(
[2890212]1867                        std::cerr << "there are " << candidates.size() << " alternatives after elimination"
[d57e349]1868                                << std::endl;
1869                )
[396037d]1870        }
1871
[2890212]1872        // adjust types after pruning so that types substituted by pruneAlternatives are correctly
[d57e349]1873        // adjusted
1874        if ( mode.adjust ) {
1875                for ( CandidateRef & r : candidates ) {
[2890212]1876                        r->expr = ast::mutate_field(
1877                                r->expr.get(), &ast::Expr::result,
[39d8950]1878                                adjustExprType( r->expr->result, r->env, context.symtab ) );
[d57e349]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        }
[99d4584]1888}
1889
[2890212]1890std::vector< CandidateFinder > CandidateFinder::findSubExprs(
1891        const std::vector< ast::ptr< ast::Expr > > & xs
[2773ab8]1892) {
1893        std::vector< CandidateFinder > out;
1894
[396037d]1895        for ( const auto & x : xs ) {
[39d8950]1896                out.emplace_back( context, env );
[396037d]1897                out.back().find( x, ResolvMode::withAdjustment() );
[2890212]1898
[396037d]1899                PRINT(
1900                        std::cerr << "findSubExprs" << std::endl;
1901                        print( std::cerr, out.back().candidates );
1902                )
1903        }
[2773ab8]1904
1905        return out;
1906}
1907
[99d4584]1908} // namespace ResolvExpr
1909
1910// Local Variables: //
1911// tab-width: 4 //
1912// mode: c++ //
1913// compile-command: "make install" //
1914// End: //
Note: See TracBrowser for help on using the repository browser.