source: src/ResolvExpr/CandidateFinder.cpp @ c8e4d2f8

arm-ehjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-expr
Last change on this file since c8e4d2f8 was c8e4d2f8, checked in by Aaron Moss <a3moss@…>, 3 years ago

Start porting CastExpr? resolution

  • Property mode set to 100644
File size: 50.3 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// CandidateFinder.cpp --
8//
9// Author           : Aaron B. Moss
10// Created On       : Wed Jun 5 14:30:00 2019
11// Last Modified By : Aaron B. Moss
12// Last Modified On : Wed Jun 5 14:30:00 2019
13// Update Count     : 1
14//
15
16#include "CandidateFinder.hpp"
17
18#include <deque>
19#include <iterator>               // for back_inserter
20#include <sstream>
21#include <string>
22#include <unordered_map>
23#include <vector>
24
25#include "Candidate.hpp"
26#include "CompilationState.h"
27#include "Cost.h"
28#include "ExplodedArg.hpp"
29#include "Resolver.h"
30#include "ResolveTypeof.h"
31#include "SatisfyAssertions.hpp"
32#include "typeops.h"              // for adjustExprType, conversionCost, polyCost, specCost
33#include "Unify.h"
34#include "AST/Expr.hpp"
35#include "AST/Node.hpp"
36#include "AST/Pass.hpp"
37#include "AST/Print.hpp"
38#include "AST/SymbolTable.hpp"
39#include "AST/Type.hpp"
40#include "SymTab/Mangler.h"
41#include "SymTab/Validate.h"      // for validateType
42#include "Tuples/Tuples.h"        // for handleTupleAssignment
43
44#define PRINT( text ) if ( resolvep ) { text }
45
46namespace ResolvExpr {
47
48using std::move;
49
50/// partner to move that copies any copyable type
51template<typename T>
52T copy( const T & x ) { return x; }
53
54const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost ) {
55        if ( expr->result.as< ast::ReferenceType >() ) {
56                // cast away reference from expr
57                cost.incReference();
58                return new ast::CastExpr{ expr->location, expr, expr->result->stripReferences() };
59        }
60       
61        return expr;
62}
63
64/// Unique identifier for matching expression resolutions to their requesting expression
65UniqueId globalResnSlot = 0;
66
67namespace {
68        /// First index is which argument, second is which alternative, third is which exploded element
69        using ExplodedArgs_new = std::deque< std::vector< ExplodedArg > >;
70
71        /// Returns a list of alternatives with the minimum cost in the given list
72        CandidateList findMinCost( const CandidateList & candidates ) {
73                CandidateList out;
74                Cost minCost = Cost::infinity;
75                for ( const CandidateRef & r : candidates ) {
76                        if ( r->cost < minCost ) {
77                                minCost = r->cost;
78                                out.clear();
79                                out.emplace_back( r );
80                        } else if ( r->cost == minCost ) {
81                                out.emplace_back( r );
82                        }
83                }
84                return out;
85        }
86
87        /// Computes conversion cost between two types
88        Cost computeConversionCost( 
89                const ast::Type * argType, const ast::Type * paramType, const ast::SymbolTable & symtab, 
90                const ast::TypeEnvironment & env
91        ) {
92                PRINT(
93                        std::cerr << std::endl << "converting ";
94                        ast::print( std::cerr, argType, 2 );
95                        std::cerr << std::endl << " to ";
96                        ast::print( std::cerr, paramType, 2 );
97                        std::cerr << std::endl << "environment is: ";
98                        ast::print( std::cerr, env, 2 );
99                        std::cerr << std::endl;
100                )
101                Cost convCost = conversionCost( argType, paramType, symtab, env );
102                PRINT(
103                        std::cerr << std::endl << "cost is " << convCost << std::endl;
104                )
105                if ( convCost == Cost::infinity ) return convCost;
106                convCost.incPoly( polyCost( paramType, symtab, env ) + polyCost( argType, symtab, env ) );
107                PRINT(
108                        std::cerr << "cost with polycost is " << convCost << std::endl;
109                )
110                return convCost;
111        }
112
113        /// Computes conversion cost for a given expression to a given type
114        const ast::Expr * computeExpressionConversionCost( 
115                const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost
116        ) {
117                Cost convCost = computeConversionCost( arg->result, paramType, symtab, env );
118                outCost += convCost;
119
120                // If there is a non-zero conversion cost, ignoring poly cost, then the expression requires
121                // conversion. Ignore poly cost for now, since this requires resolution of the cast to
122                // infer parameters and this does not currently work for the reason stated below
123                Cost tmpCost = convCost;
124                tmpCost.incPoly( -tmpCost.get_polyCost() );
125                if ( tmpCost != Cost::zero ) {
126                        ast::ptr< ast::Type > newType = paramType;
127                        env.apply( newType );
128                        return new ast::CastExpr{ arg->location, arg, newType };
129
130                        // xxx - *should* be able to resolve this cast, but at the moment pointers are not
131                        // castable to zero_t, but are implicitly convertible. This is clearly inconsistent,
132                        // once this is fixed it should be possible to resolve the cast.
133                        // xxx - this isn't working, it appears because type1 (parameter) is seen as widenable,
134                        // but it shouldn't be because this makes the conversion from DT* to DT* since
135                        // commontype(zero_t, DT*) is DT*, rather than nothing
136
137                        // CandidateFinder finder{ symtab, env };
138                        // finder.find( arg, ResolvMode::withAdjustment() );
139                        // assertf( finder.candidates.size() > 0,
140                        //      "Somehow castable expression failed to find alternatives." );
141                        // assertf( finder.candidates.size() == 1,
142                        //      "Somehow got multiple alternatives for known cast expression." );
143                        // return finder.candidates.front()->expr;
144                }
145
146                return arg;
147        }
148
149        /// Computes conversion cost for a given candidate
150        Cost computeApplicationConversionCost( 
151                CandidateRef cand, const ast::SymbolTable & symtab
152        ) {
153                auto appExpr = cand->expr.strict_as< ast::ApplicationExpr >();
154                auto pointer = appExpr->func->result.strict_as< ast::PointerType >();
155                auto function = pointer->base.strict_as< ast::FunctionType >();
156
157                Cost convCost = Cost::zero;
158                const auto & params = function->params;
159                auto param = params.begin();
160                auto & args = appExpr->args;
161
162                for ( unsigned i = 0; i < args.size(); ++i ) {
163                        const ast::Type * argType = args[i]->result;
164                        PRINT(
165                                std::cerr << "arg expression:" << std::endl;
166                                ast::print( std::cerr, args[i], 2 );
167                                std::cerr << "--- results are" << std::endl;
168                                ast::print( std::cerr, argType, 2 );
169                        )
170
171                        if ( param == params.end() ) {
172                                if ( function->isVarArgs ) {
173                                        convCost.incUnsafe();
174                                        PRINT( std::cerr << "end of params with varargs function: inc unsafe: " 
175                                                << convCost << std::endl; ; )
176                                        // convert reference-typed expressions into value-typed expressions
177                                        cand->expr = ast::mutate_field_index( 
178                                                appExpr, &ast::ApplicationExpr::args, i, 
179                                                referenceToRvalueConversion( args[i], convCost ) );
180                                        continue;
181                                } else return Cost::infinity;
182                        }
183
184                        if ( auto def = args[i].as< ast::DefaultArgExpr >() ) {
185                                // Default arguments should be free - don't include conversion cost.
186                                // Unwrap them here because they are not relevant to the rest of the system
187                                cand->expr = ast::mutate_field_index( 
188                                        appExpr, &ast::ApplicationExpr::args, i, def->expr );
189                                ++param;
190                                continue;
191                        }
192
193                        // mark conversion cost and also specialization cost of param type
194                        const ast::Type * paramType = (*param)->get_type();
195                        cand->expr = ast::mutate_field_index( 
196                                appExpr, &ast::ApplicationExpr::args, i, 
197                                computeExpressionConversionCost( 
198                                        args[i], paramType, symtab, cand->env, convCost ) );
199                        convCost.decSpec( specCost( paramType ) );
200                        ++param;  // can't be in for-loop update because of the continue
201                }
202
203                if ( param != params.end() ) return Cost::infinity;
204
205                // specialization cost of return types can't be accounted for directly, it disables
206                // otherwise-identical calls, like this example based on auto-newline in the I/O lib:
207                //
208                //   forall(otype OS) {
209                //     void ?|?(OS&, int);  // with newline
210                //     OS&  ?|?(OS&, int);  // no newline, always chosen due to more specialization
211                //   }
212
213                // mark type variable and specialization cost of forall clause
214                convCost.incVar( function->forall.size() );
215                for ( const ast::TypeDecl * td : function->forall ) {
216                        convCost.decSpec( td->assertions.size() );
217                }
218
219                return convCost;
220        }
221
222        void makeUnifiableVars( 
223                const ast::ParameterizedType * type, ast::OpenVarSet & unifiableVars, 
224                ast::AssertionSet & need
225        ) {
226                for ( const ast::TypeDecl * tyvar : type->forall ) {
227                        unifiableVars[ tyvar->name ] = ast::TypeDecl::Data{ tyvar };
228                        for ( const ast::DeclWithType * assn : tyvar->assertions ) {
229                                need[ assn ].isUsed = true;
230                        }
231                }
232        }
233
234        /// Gets a default value from an initializer, nullptr if not present
235        const ast::ConstantExpr * getDefaultValue( const ast::Init * init ) {
236                if ( auto si = dynamic_cast< const ast::SingleInit * >( init ) ) {
237                        if ( auto ce = si->value.as< ast::CastExpr >() ) {
238                                return ce->arg.as< ast::ConstantExpr >();
239                        } else {
240                                return si->value.as< ast::ConstantExpr >();
241                        }
242                }
243                return nullptr;
244        }
245
246        /// State to iteratively build a match of parameter expressions to arguments
247        struct ArgPack {
248                std::size_t parent;          ///< Index of parent pack
249                ast::ptr< ast::Expr > expr;  ///< The argument stored here
250                Cost cost;                   ///< The cost of this argument
251                ast::TypeEnvironment env;    ///< Environment for this pack
252                ast::AssertionSet need;      ///< Assertions outstanding for this pack
253                ast::AssertionSet have;      ///< Assertions found for this pack
254                ast::OpenVarSet open;        ///< Open variables for this pack
255                unsigned nextArg;            ///< Index of next argument in arguments list
256                unsigned tupleStart;         ///< Number of tuples that start at this index
257                unsigned nextExpl;           ///< Index of next exploded element
258                unsigned explAlt;            ///< Index of alternative for nextExpl > 0
259
260                ArgPack()
261                : parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ), 
262                  tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}
263               
264                ArgPack( 
265                        const ast::TypeEnvironment & env, const ast::AssertionSet & need, 
266                        const ast::AssertionSet & have, const ast::OpenVarSet & open )
267                : parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ), 
268                  open( open ), nextArg( 0 ), tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}
269               
270                ArgPack(
271                        std::size_t parent, const ast::Expr * expr, ast::TypeEnvironment && env, 
272                        ast::AssertionSet && need, ast::AssertionSet && have, ast::OpenVarSet && open, 
273                        unsigned nextArg, unsigned tupleStart = 0, Cost cost = Cost::zero, 
274                        unsigned nextExpl = 0, unsigned explAlt = 0 )
275                : parent(parent), expr( expr ), cost( cost ), env( move( env ) ), need( move( need ) ),
276                  have( move( have ) ), open( move( open ) ), nextArg( nextArg ), tupleStart( tupleStart ),
277                  nextExpl( nextExpl ), explAlt( explAlt ) {}
278               
279                ArgPack(
280                        const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need, 
281                        ast::AssertionSet && have, ast::OpenVarSet && open, unsigned nextArg, Cost added )
282                : parent( o.parent ), expr( o.expr ), cost( o.cost + added ), env( move( env ) ), 
283                  need( move( need ) ), have( move( have ) ), open( move( open ) ), nextArg( nextArg ), 
284                  tupleStart( o.tupleStart ), nextExpl( 0 ), explAlt( 0 ) {}
285               
286                /// true if this pack is in the middle of an exploded argument
287                bool hasExpl() const { return nextExpl > 0; }
288
289                /// Gets the list of exploded candidates for this pack
290                const ExplodedArg & getExpl( const ExplodedArgs_new & args ) const {
291                        return args[ nextArg-1 ][ explAlt ];
292                }
293               
294                /// Ends a tuple expression, consolidating the appropriate args
295                void endTuple( const std::vector< ArgPack > & packs ) {
296                        // add all expressions in tuple to list, summing cost
297                        std::deque< const ast::Expr * > exprs;
298                        const ArgPack * pack = this;
299                        if ( expr ) { exprs.emplace_front( expr ); }
300                        while ( pack->tupleStart == 0 ) {
301                                pack = &packs[pack->parent];
302                                exprs.emplace_front( pack->expr );
303                                cost += pack->cost;
304                        }
305                        // reset pack to appropriate tuple
306                        std::vector< ast::ptr< ast::Expr > > exprv( exprs.begin(), exprs.end() );
307                        expr = new ast::TupleExpr{ expr->location, move( exprv ) };
308                        tupleStart = pack->tupleStart - 1;
309                        parent = pack->parent;
310                }
311        };
312
313        /// Instantiates an argument to match a parameter, returns false if no matching results left
314        bool instantiateArgument( 
315                const ast::Type * paramType, const ast::Init * init, const ExplodedArgs_new & args, 
316                std::vector< ArgPack > & results, std::size_t & genStart, const ast::SymbolTable & symtab, 
317                unsigned nTuples = 0 
318        ) {
319                if ( auto tupleType = dynamic_cast< const ast::TupleType * >( paramType ) ) {
320                        // paramType is a TupleType -- group args into a TupleExpr
321                        ++nTuples;
322                        for ( const ast::Type * type : *tupleType ) {
323                                // xxx - dropping initializer changes behaviour from previous, but seems correct
324                                // ^^^ need to handle the case where a tuple has a default argument
325                                if ( ! instantiateArgument( 
326                                        type, nullptr, args, results, genStart, symtab, nTuples ) ) return false;
327                                nTuples = 0;
328                        }
329                        // re-constitute tuples for final generation
330                        for ( auto i = genStart; i < results.size(); ++i ) {
331                                results[i].endTuple( results );
332                        }
333                        return true;
334                } else if ( const ast::TypeInstType * ttype = Tuples::isTtype( paramType ) ) {
335                        // paramType is a ttype, consumes all remaining arguments
336                       
337                        // completed tuples; will be spliced to end of results to finish
338                        std::vector< ArgPack > finalResults{};
339
340                        // iterate until all results completed
341                        std::size_t genEnd;
342                        ++nTuples;
343                        do {
344                                genEnd = results.size();
345
346                                // add another argument to results
347                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
348                                        unsigned nextArg = results[i].nextArg;
349                                       
350                                        // use next element of exploded tuple if present
351                                        if ( results[i].hasExpl() ) {
352                                                const ExplodedArg & expl = results[i].getExpl( args );
353
354                                                unsigned nextExpl = results[i].nextExpl + 1;
355                                                if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
356
357                                                results.emplace_back(
358                                                        i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),
359                                                        copy( results[i].need ), copy( results[i].have ), 
360                                                        copy( results[i].open ), nextArg, nTuples, Cost::zero, nextExpl,
361                                                        results[i].explAlt );
362
363                                                continue;
364                                        }
365
366                                        // finish result when out of arguments
367                                        if ( nextArg >= args.size() ) {
368                                                ArgPack newResult{
369                                                        results[i].env, results[i].need, results[i].have, results[i].open };
370                                                newResult.nextArg = nextArg;
371                                                const ast::Type * argType = nullptr;
372
373                                                if ( nTuples > 0 || ! results[i].expr ) {
374                                                        // first iteration or no expression to clone,
375                                                        // push empty tuple expression
376                                                        newResult.parent = i;
377                                                        std::vector< ast::ptr< ast::Expr > > emptyList;
378                                                        newResult.expr = 
379                                                                new ast::TupleExpr{ CodeLocation{}, move( emptyList ) };
380                                                        argType = newResult.expr->result;
381                                                } else {
382                                                        // clone result to collect tuple
383                                                        newResult.parent = results[i].parent;
384                                                        newResult.cost = results[i].cost;
385                                                        newResult.tupleStart = results[i].tupleStart;
386                                                        newResult.expr = results[i].expr;
387                                                        argType = newResult.expr->result;
388
389                                                        if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
390                                                                // the case where a ttype value is passed directly is special,
391                                                                // e.g. for argument forwarding purposes
392                                                                // xxx - what if passing multiple arguments, last of which is
393                                                                //       ttype?
394                                                                // xxx - what would happen if unify was changed so that unifying
395                                                                //       tuple
396                                                                // types flattened both before unifying lists? then pass in
397                                                                // TupleType (ttype) below.
398                                                                --newResult.tupleStart;
399                                                        } else {
400                                                                // collapse leftover arguments into tuple
401                                                                newResult.endTuple( results );
402                                                                argType = newResult.expr->result;
403                                                        }
404                                                }
405
406                                                // check unification for ttype before adding to final
407                                                if ( 
408                                                        unify( 
409                                                                ttype, argType, newResult.env, newResult.need, newResult.have,
410                                                                newResult.open, symtab ) 
411                                                ) {
412                                                        finalResults.emplace_back( move( newResult ) );
413                                                }
414
415                                                continue;
416                                        }
417
418                                        // add each possible next argument
419                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
420                                                const ExplodedArg & expl = args[nextArg][j];
421
422                                                // fresh copies of parent parameters for this iteration
423                                                ast::TypeEnvironment env = results[i].env;
424                                                ast::OpenVarSet open = results[i].open;
425
426                                                env.addActual( expl.env, open );
427
428                                                // skip empty tuple arguments by (nearly) cloning parent into next gen
429                                                if ( expl.exprs.empty() ) {
430                                                        results.emplace_back(
431                                                                results[i], move( env ), copy( results[i].need ), 
432                                                                copy( results[i].have ), move( open ), nextArg + 1, expl.cost );
433                                                       
434                                                        continue;
435                                                }
436
437                                                // add new result
438                                                results.emplace_back(
439                                                        i, expl.exprs.front(), move( env ), copy( results[i].need ), 
440                                                        copy( results[i].have ), move( open ), nextArg + 1, nTuples, 
441                                                        expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
442                                        }
443                                }
444
445                                // reset for next round
446                                genStart = genEnd;
447                                nTuples = 0;
448                        } while ( genEnd != results.size() );
449
450                        // splice final results onto results
451                        for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
452                                results.emplace_back( move( finalResults[i] ) );
453                        }
454                        return ! finalResults.empty();
455                }
456
457                // iterate each current subresult
458                std::size_t genEnd = results.size();
459                for ( std::size_t i = genStart; i < genEnd; ++i ) {
460                        unsigned nextArg = results[i].nextArg;
461
462                        // use remainder of exploded tuple if present
463                        if ( results[i].hasExpl() ) {
464                                const ExplodedArg & expl = results[i].getExpl( args );
465                                const ast::Expr * expr = expl.exprs[ results[i].nextExpl ];
466
467                                ast::TypeEnvironment env = results[i].env;
468                                ast::AssertionSet need = results[i].need, have = results[i].have;
469                                ast::OpenVarSet open = results[i].open;
470
471                                const ast::Type * argType = expr->result;
472
473                                PRINT(
474                                        std::cerr << "param type is ";
475                                        ast::print( std::cerr, paramType );
476                                        std::cerr << std::endl << "arg type is ";
477                                        ast::print( std::cerr, argType );
478                                        std::cerr << std::endl;
479                                )
480
481                                if ( unify( paramType, argType, env, need, have, open, symtab ) ) {
482                                        unsigned nextExpl = results[i].nextExpl + 1;
483                                        if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
484
485                                        results.emplace_back(
486                                                i, expr, move( env ), move( need ), move( have ), move( open ), nextArg, 
487                                                nTuples, Cost::zero, nextExpl, results[i].explAlt );
488                                }
489
490                                continue;
491                        }
492
493                        // use default initializers if out of arguments
494                        if ( nextArg >= args.size() ) {
495                                if ( const ast::ConstantExpr * cnst = getDefaultValue( init ) ) {
496                                        ast::TypeEnvironment env = results[i].env;
497                                        ast::AssertionSet need = results[i].need, have = results[i].have;
498                                        ast::OpenVarSet open = results[i].open;
499
500                                        if ( unify( paramType, cnst->result, env, need, have, open, symtab ) ) {
501                                                results.emplace_back(
502                                                        i, new ast::DefaultArgExpr{ cnst->location, cnst }, move( env ), 
503                                                        move( need ), move( have ), move( open ), nextArg, nTuples );
504                                        }
505                                }
506
507                                continue;
508                        }
509
510                        // Check each possible next argument
511                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
512                                const ExplodedArg & expl = args[nextArg][j];
513
514                                // fresh copies of parent parameters for this iteration
515                                ast::TypeEnvironment env = results[i].env;
516                                ast::AssertionSet need = results[i].need, have = results[i].have;
517                                ast::OpenVarSet open = results[i].open;
518
519                                env.addActual( expl.env, open );
520
521                                // skip empty tuple arguments by (nearly) cloning parent into next gen
522                                if ( expl.exprs.empty() ) {
523                                        results.emplace_back(
524                                                results[i], move( env ), move( need ), move( have ), move( open ), 
525                                                nextArg + 1, expl.cost );
526                                       
527                                        continue;
528                                }
529
530                                // consider only first exploded arg
531                                const ast::Expr * expr = expl.exprs.front();
532                                const ast::Type * argType = expr->result;
533
534                                PRINT(
535                                        std::cerr << "param type is ";
536                                        ast::print( std::cerr, paramType );
537                                        std::cerr << std::endl << "arg type is ";
538                                        ast::print( std::cerr, argType );
539                                        std::cerr << std::endl;
540                                )
541
542                                // attempt to unify types
543                                if ( unify( paramType, argType, env, need, have, open, symtab ) ) {
544                                        // add new result
545                                        results.emplace_back(
546                                                i, expr, move( env ), move( need ), move( have ), move( open ), 
547                                                nextArg + 1, nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
548                                }
549                        }
550                }
551
552                // reset for next parameter
553                genStart = genEnd;
554
555                return genEnd != results.size();
556        }
557
558        /// Generate a cast expression from `arg` to `toType`
559        const ast::Expr * restructureCast( const ast::Expr * arg, const ast::Type * toType, bool isGenerated ) {
560                #warning unimplemented
561                (void)arg; (void)toType; (void)isGenerated;
562                assert(false);
563                return nullptr;
564        }
565
566        /// Actually visits expressions to find their candidate interpretations
567        struct Finder final : public ast::WithShortCircuiting {
568                CandidateFinder & selfFinder;
569                const ast::SymbolTable & symtab;
570                CandidateList & candidates;
571                const ast::TypeEnvironment & tenv;
572                ast::ptr< ast::Type > & targetType;
573
574                Finder( CandidateFinder & f )
575                : selfFinder( f ), symtab( f.symtab ), candidates( f.candidates ), tenv( f.env ), 
576                  targetType( f.targetType ) {}
577               
578                void previsit( const ast::Node * ) { visit_children = false; }
579
580                /// Convenience to add candidate to list
581                template<typename... Args>
582                void addCandidate( Args &&... args ) {
583                        candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } );
584                }
585
586                void postvisit( const ast::ApplicationExpr * applicationExpr ) {
587                        addCandidate( applicationExpr, tenv );
588                }
589
590                /// Set up candidate assertions for inference
591                void inferParameters( CandidateRef & newCand, CandidateList & out ) {
592                        // Set need bindings for any unbound assertions
593                        UniqueId crntResnSlot = 0; // matching ID for this expression's assertions
594                        for ( auto & assn : newCand->need ) {
595                                // skip already-matched assertions
596                                if ( assn.second.resnSlot != 0 ) continue;
597                                // assign slot for expression if needed
598                                if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; }
599                                // fix slot to assertion
600                                assn.second.resnSlot = crntResnSlot;
601                        }
602                        // pair slot to expression
603                        if ( crntResnSlot != 0 ) {
604                                newCand->expr.get_and_mutate()->inferred.resnSlots().emplace_back( crntResnSlot );
605                        }
606
607                        // add to output list; assertion satisfaction will occur later
608                        out.emplace_back( newCand );
609                }
610
611                /// Completes a function candidate with arguments located
612                void validateFunctionCandidate( 
613                        const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results, 
614                        CandidateList & out
615                ) {
616                        ast::ApplicationExpr * appExpr = 
617                                new ast::ApplicationExpr{ func->expr->location, func->expr };
618                        // sum cost and accumulate arguments
619                        std::deque< const ast::Expr * > args;
620                        Cost cost = func->cost;
621                        const ArgPack * pack = &result;
622                        while ( pack->expr ) {
623                                args.emplace_front( pack->expr );
624                                cost += pack->cost;
625                                pack = &results[pack->parent];
626                        }
627                        std::vector< ast::ptr< ast::Expr > > vargs( args.begin(), args.end() );
628                        appExpr->args = move( vargs );
629                        // build and validate new candidate
630                        auto newCand = 
631                                std::make_shared<Candidate>( appExpr, result.env, result.open, result.need, cost );
632                        PRINT(
633                                std::cerr << "instantiate function success: " << appExpr << std::endl;
634                                std::cerr << "need assertions:" << std::endl;
635                                ast::print( std::cerr, result.need, 2 );
636                        )
637                        inferParameters( newCand, out );
638                }
639
640                /// Builds a list of candidates for a function, storing them in out
641                void makeFunctionCandidates(
642                        const CandidateRef & func, const ast::FunctionType * funcType, 
643                        const ExplodedArgs_new & args, CandidateList & out
644                ) {
645                        ast::OpenVarSet funcOpen;
646                        ast::AssertionSet funcNeed, funcHave;
647                        ast::TypeEnvironment funcEnv{ func->env };
648                        makeUnifiableVars( funcType, funcOpen, funcNeed );
649                        // add all type variables as open variables now so that those not used in the parameter
650                        // list are still considered open
651                        funcEnv.add( funcType->forall );
652
653                        if ( targetType && ! targetType->isVoid() && ! funcType->returns.empty() ) {
654                                // attempt to narrow based on expected target type
655                                const ast::Type * returnType = funcType->returns.front()->get_type();
656                                if ( ! unify( 
657                                        returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, symtab ) 
658                                ) {
659                                        // unification failed, do not pursue this candidate
660                                        return;
661                                }
662                        }
663
664                        // iteratively build matches, one parameter at a time
665                        std::vector< ArgPack > results;
666                        results.emplace_back( funcEnv, funcNeed, funcHave, funcOpen );
667                        std::size_t genStart = 0;
668
669                        for ( const ast::DeclWithType * param : funcType->params ) {
670                                auto obj = strict_dynamic_cast< const ast::ObjectDecl * >( param );
671                                // Try adding the arguments corresponding to the current parameter to the existing
672                                // matches
673                                if ( ! instantiateArgument( 
674                                        obj->type, obj->init, args, results, genStart, symtab ) ) return;
675                        }
676
677                        if ( funcType->isVarArgs ) {
678                                // append any unused arguments to vararg pack
679                                std::size_t genEnd;
680                                do {
681                                        genEnd = results.size();
682
683                                        // iterate results
684                                        for ( std::size_t i = genStart; i < genEnd; ++i ) {
685                                                unsigned nextArg = results[i].nextArg;
686
687                                                // use remainder of exploded tuple if present
688                                                if ( results[i].hasExpl() ) {
689                                                        const ExplodedArg & expl = results[i].getExpl( args );
690
691                                                        unsigned nextExpl = results[i].nextExpl + 1;
692                                                        if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
693
694                                                        results.emplace_back(
695                                                                i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),
696                                                                copy( results[i].need ), copy( results[i].have ),
697                                                                copy( results[i].open ), nextArg, 0, Cost::zero, nextExpl,
698                                                                results[i].explAlt );
699
700                                                        continue;
701                                                }
702
703                                                // finish result when out of arguments
704                                                if ( nextArg >= args.size() ) {
705                                                        validateFunctionCandidate( func, results[i], results, out );
706
707                                                        continue;
708                                                }
709
710                                                // add each possible next argument
711                                                for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
712                                                        const ExplodedArg & expl = args[nextArg][j];
713
714                                                        // fresh copies of parent parameters for this iteration
715                                                        ast::TypeEnvironment env = results[i].env;
716                                                        ast::OpenVarSet open = results[i].open;
717
718                                                        env.addActual( expl.env, open );
719
720                                                        // skip empty tuple arguments by (nearly) cloning parent into next gen
721                                                        if ( expl.exprs.empty() ) {
722                                                                results.emplace_back(
723                                                                        results[i], move( env ), copy( results[i].need ), 
724                                                                        copy( results[i].have ), move( open ), nextArg + 1, 
725                                                                        expl.cost );
726
727                                                                continue;
728                                                        }
729
730                                                        // add new result
731                                                        results.emplace_back(
732                                                                i, expl.exprs.front(), move( env ), copy( results[i].need ),
733                                                                copy( results[i].have ), move( open ), nextArg + 1, 0, expl.cost, 
734                                                                expl.exprs.size() == 1 ? 0 : 1, j );
735                                                }
736                                        }
737
738                                        genStart = genEnd;
739                                } while( genEnd != results.size() );
740                        } else {
741                                // filter out the results that don't use all the arguments
742                                for ( std::size_t i = genStart; i < results.size(); ++i ) {
743                                        ArgPack & result = results[i];
744                                        if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
745                                                validateFunctionCandidate( func, result, results, out );
746                                        }
747                                }
748                        }
749                }
750
751                /// Adds implicit struct-conversions to the alternative list
752                void addAnonConversions( const CandidateRef & cand ) {
753                        // adds anonymous member interpretations whenever an aggregate value type is seen.
754                        // it's okay for the aggregate expression to have reference type -- cast it to the
755                        // base type to treat the aggregate as the referenced value
756                        ast::ptr< ast::Expr > aggrExpr( cand->expr );
757                        ast::ptr< ast::Type > & aggrType = aggrExpr.get_and_mutate()->result;
758                        cand->env.apply( aggrType );
759                       
760                        if ( aggrType.as< ast::ReferenceType >() ) {
761                                aggrExpr = 
762                                        new ast::CastExpr{ aggrExpr->location, aggrExpr, aggrType->stripReferences() };
763                        }
764
765                        if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) {
766                                addAggMembers( structInst, aggrExpr, cand, Cost::safe, "" );
767                        } else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) {
768                                addAggMembers( unionInst, aggrExpr, cand, Cost::safe, "" );
769                        }
770                }
771
772                /// Adds aggregate member interpretations
773                void addAggMembers( 
774                        const ast::ReferenceToType * aggrInst, const ast::Expr * expr, 
775                        const CandidateRef & cand, const Cost & addedCost, const std::string & name
776                ) {
777                        for ( const ast::Decl * decl : aggrInst->lookup( name ) ) {
778                                auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl );
779                                CandidateRef newCand = std::make_shared<Candidate>( 
780                                        *cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost );
781                                // add anonymous member interpretations whenever an aggregate value type is seen
782                                // as a member expression
783                                addAnonConversions( newCand );
784                                candidates.emplace_back( move( newCand ) );
785                        }
786                }
787
788                void postvisit( const ast::UntypedExpr * untypedExpr ) {
789                        CandidateFinder funcFinder{ symtab, tenv };
790                        funcFinder.find( untypedExpr->func, ResolvMode::withAdjustment() );
791                        // short-circuit if no candidates
792                        if ( funcFinder.candidates.empty() ) return;
793
794                        std::vector< CandidateFinder > argCandidates = 
795                                selfFinder.findSubExprs( untypedExpr->args );
796                       
797                        // take care of possible tuple assignments
798                        // if not tuple assignment, handled as normal function call
799                        Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates );
800
801                        // find function operators
802                        ast::ptr< ast::Expr > opExpr = new ast::NameExpr{ untypedExpr->location, "?()" };
803                        CandidateFinder opFinder{ symtab, tenv };
804                        // okay if there aren't any function operations
805                        opFinder.find( opExpr, ResolvMode::withoutFailFast() );
806                        PRINT(
807                                std::cerr << "known function ops:" << std::endl;
808                                print( std::cerr, opFinder.candidates, 1 );
809                        )
810
811                        // pre-explode arguments
812                        ExplodedArgs_new argExpansions;
813                        for ( const CandidateFinder & args : argCandidates ) {
814                                argExpansions.emplace_back();
815                                auto & argE = argExpansions.back();
816                                for ( const CandidateRef & arg : args ) { argE.emplace_back( *arg, symtab ); }
817                        }
818
819                        // Find function matches
820                        CandidateList found;
821                        SemanticErrorException errors;
822                        for ( CandidateRef & func : funcFinder ) {
823                                try {
824                                        PRINT(
825                                                std::cerr << "working on alternative:" << std::endl;
826                                                print( std::cerr, *func, 2 );
827                                        )
828
829                                        // check if the type is a pointer to function
830                                        const ast::Type * funcResult = func->expr->result->stripReferences();
831                                        if ( auto pointer = dynamic_cast< const ast::PointerType * >( funcResult ) ) {
832                                                if ( auto function = pointer->base.as< ast::FunctionType >() ) {
833                                                        CandidateRef newFunc{ new Candidate{ *func } };
834                                                        newFunc->expr = 
835                                                                referenceToRvalueConversion( newFunc->expr, newFunc->cost );
836                                                        makeFunctionCandidates( newFunc, function, argExpansions, found );
837                                                }
838                                        } else if ( 
839                                                auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult ) 
840                                        ) {
841                                                if ( const ast::EqvClass * clz = func->env.lookup( inst->name ) ) {
842                                                        if ( auto function = clz->bound.as< ast::FunctionType >() ) {
843                                                                CandidateRef newFunc{ new Candidate{ *func } };
844                                                                newFunc->expr = 
845                                                                        referenceToRvalueConversion( newFunc->expr, newFunc->cost );
846                                                                makeFunctionCandidates( newFunc, function, argExpansions, found );
847                                                        }
848                                                }
849                                        }
850                                } catch ( SemanticErrorException & e ) { errors.append( e ); }
851                        }
852
853                        // Find matches on function operators `?()`
854                        if ( ! opFinder.candidates.empty() ) {
855                                // add exploded function alternatives to front of argument list
856                                std::vector< ExplodedArg > funcE;
857                                funcE.reserve( funcFinder.candidates.size() );
858                                for ( const CandidateRef & func : funcFinder ) { 
859                                        funcE.emplace_back( *func, symtab );
860                                }
861                                argExpansions.emplace_front( move( funcE ) );
862
863                                for ( const CandidateRef & op : opFinder ) {
864                                        try {
865                                                // check if type is pointer-to-function
866                                                const ast::Type * opResult = op->expr->result->stripReferences();
867                                                if ( auto pointer = dynamic_cast< const ast::PointerType * >( opResult ) ) {
868                                                        if ( auto function = pointer->base.as< ast::FunctionType >() ) {
869                                                                CandidateRef newOp{ new Candidate{ *op} };
870                                                                newOp->expr = 
871                                                                        referenceToRvalueConversion( newOp->expr, newOp->cost );
872                                                                makeFunctionCandidates( newOp, function, argExpansions, found );
873                                                        }
874                                                }
875                                        } catch ( SemanticErrorException & e ) { errors.append( e ); }
876                                }
877                        }
878
879                        // Implement SFINAE; resolution errors are only errors if there aren't any non-error
880                        // candidates
881                        if ( found.empty() && ! errors.isEmpty() ) { throw errors; }
882
883                        // Compute conversion costs
884                        for ( CandidateRef & withFunc : found ) {
885                                Cost cvtCost = computeApplicationConversionCost( withFunc, symtab );
886
887                                PRINT(
888                                        auto appExpr = withFunc->expr.strict_as< ast::ApplicationExpr >();
889                                        auto pointer = appExpr->func->result.strict_as< ast::PointerType >();
890                                        auto function = pointer->base.strict_as< ast::FunctionType >();
891                                       
892                                        std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl;
893                                        std::cerr << "parameters are:" << std::endl;
894                                        ast::printAll( std::cerr, function->params, 2 );
895                                        std::cerr << "arguments are:" << std::endl;
896                                        ast::printAll( std::cerr, appExpr->args, 2 );
897                                        std::cerr << "bindings are:" << std::endl;
898                                        ast::print( std::cerr, withFunc->env, 2 );
899                                        std::cerr << "cost is: " << withFunc->cost << std::endl;
900                                        std::cerr << "cost of conversion is:" << cvtCost << std::endl;
901                                )
902
903                                if ( cvtCost != Cost::infinity ) {
904                                        withFunc->cvtCost = cvtCost;
905                                        candidates.emplace_back( move( withFunc ) );
906                                }
907                        }
908                        found = move( candidates );
909
910                        // use a new list so that candidates are not examined by addAnonConversions twice
911                        CandidateList winners = findMinCost( found );
912                        promoteCvtCost( winners );
913
914                        // function may return a struct/union value, in which case we need to add candidates
915                        // for implicit conversions to each of the anonymous members, which must happen after
916                        // `findMinCost`, since anon conversions are never the cheapest
917                        for ( const CandidateRef & c : winners ) {
918                                addAnonConversions( c );
919                        }
920                        spliceBegin( candidates, winners );
921
922                        if ( candidates.empty() && targetType && ! targetType->isVoid() ) {
923                                // If resolution is unsuccessful with a target type, try again without, since it
924                                // will sometimes succeed when it wouldn't with a target type binding.
925                                // For example:
926                                //   forall( otype T ) T & ?[]( T *, ptrdiff_t );
927                                //   const char * x = "hello world";
928                                //   unsigned char ch = x[0];
929                                // Fails with simple return type binding (xxx -- check this!) as follows:
930                                // * T is bound to unsigned char
931                                // * (x: const char *) is unified with unsigned char *, which fails
932                                // xxx -- fix this better
933                                targetType = nullptr;
934                                postvisit( untypedExpr );
935                        }
936                }
937
938                /// true if expression is an lvalue
939                static bool isLvalue( const ast::Expr * x ) {
940                        return x->result && ( x->result->is_lvalue() || x->result.as< ast::ReferenceType >() );
941                }
942
943                void postvisit( const ast::AddressExpr * addressExpr ) {
944                        CandidateFinder finder{ symtab, tenv };
945                        finder.find( addressExpr->arg );
946                        for ( CandidateRef & r : finder.candidates ) {
947                                if ( ! isLvalue( r->expr ) ) continue;
948                                addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } );
949                        }
950                }
951
952                void postvisit( const ast::LabelAddressExpr * labelExpr ) {
953                        addCandidate( labelExpr, tenv );
954                }
955
956                void postvisit( const ast::CastExpr * castExpr ) {
957                        ast::ptr< ast::Type > toType = castExpr->result;
958                        assert( toType );
959                        toType = resolveTypeof( toType, symtab );
960                        toType = SymTab::validateType( toType, symtab );
961                        toType = adjustExprType( toType, tenv, symtab );
962
963                        CandidateFinder finder{ symtab, tenv, toType };
964                        finder.find( castExpr->arg, ResolvMode::withAdjustment() );
965
966                        CandidateList matches;
967                        for ( CandidateRef & cand : finder.candidates ) {
968                                ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have;
969                                ast::OpenVarSet open( cand->open );
970
971                                cand->env.extractOpenVars( open );
972
973                                // It is possible that a cast can throw away some values in a multiply-valued
974                                // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of the
975                                // subexpression results that are cast directly. The candidate is invalid if it
976                                // has fewer results than there are types to cast to.
977                                int discardedValues = cand->expr->result->size() - toType->size();
978                                if ( discardedValues < 0 ) continue;
979
980                                // unification run for side-effects
981                                unify( toType, cand->expr->result, cand->env, need, have, open, symtab );
982                                Cost thisCost = castCost( cand->expr->result, toType, symtab, cand->env );
983                                PRINT(
984                                        std::cerr << "working on cast with result: " << toType << std::endl;
985                                        std::cerr << "and expr type: " << cand->expr->result << std::endl;
986                                        std::cerr << "env: " << cand->env << std::endl;
987                                )
988                                if ( thisCost != Cost::infinity ) {
989                                        PRINT(
990                                                std::cerr << "has finite cost." << std::endl;
991                                        )
992                                        // count one safe conversion for each value that is thrown away
993                                        thisCost.incSafe( discardedValues );
994                                        CandidateRef newCand = std::make_shared<Candidate>( 
995                                                restructureCast( cand->expr, toType, castExpr->isGenerated ), 
996                                                copy( cand->env ), move( open ), move( need ), cand->cost, 
997                                                cand->cost + thisCost );
998                                        inferParameters( newCand, matches );
999                                }
1000                        }
1001
1002                        // castExpr->result should be replaced with toType
1003                        // candidates => matches
1004
1005                        #warning unimplemented
1006                        (void)castExpr;
1007                        assert(false);
1008                }
1009
1010                void postvisit( const ast::VirtualCastExpr * castExpr ) {
1011                        assertf( castExpr->result, "Implicit virtual cast targets not yet supported." );
1012                        CandidateFinder finder{ symtab, tenv };
1013                        // don't prune here, all alternatives guaranteed to have same type
1014                        finder.find( castExpr->arg, ResolvMode::withoutPrune() );
1015                        for ( CandidateRef & r : finder.candidates ) {
1016                                addCandidate( 
1017                                        *r, 
1018                                        new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );
1019                        }
1020                }
1021
1022                void postvisit( const ast::UntypedMemberExpr * memberExpr ) {
1023                        #warning unimplemented
1024                        (void)memberExpr;
1025                        assert(false);
1026                }
1027
1028                void postvisit( const ast::MemberExpr * memberExpr ) {
1029                        addCandidate( memberExpr, tenv );
1030                }
1031
1032                void postvisit( const ast::NameExpr * variableExpr ) {
1033                        #warning unimplemented
1034                        (void)variableExpr;
1035                        assert(false);
1036                }
1037
1038                void postvisit( const ast::VariableExpr * variableExpr ) {
1039                        // not sufficient to just pass `variableExpr` here, type might have changed since
1040                        // creation
1041                        addCandidate( 
1042                                new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv );
1043                }
1044
1045                void postvisit( const ast::ConstantExpr * constantExpr ) {
1046                        addCandidate( constantExpr, tenv );
1047                }
1048
1049                void postvisit( const ast::SizeofExpr * sizeofExpr ) {
1050                        #warning unimplemented
1051                        (void)sizeofExpr;
1052                        assert(false);
1053                }
1054
1055                void postvisit( const ast::AlignofExpr * alignofExpr ) {
1056                        #warning unimplemented
1057                        (void)alignofExpr;
1058                        assert(false);
1059                }
1060
1061                void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {
1062                        #warning unimplemented
1063                        (void)offsetofExpr;
1064                        assert(false);
1065                }
1066
1067                void postvisit( const ast::OffsetofExpr * offsetofExpr ) {
1068                        addCandidate( offsetofExpr, tenv );
1069                }
1070
1071                void postvisit( const ast::OffsetPackExpr * offsetPackExpr ) {
1072                        addCandidate( offsetPackExpr, tenv );
1073                }
1074
1075                void postvisit( const ast::LogicalExpr * logicalExpr ) {
1076                        CandidateFinder finder1{ symtab, tenv };
1077                        finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() );
1078                        if ( finder1.candidates.empty() ) return;
1079
1080                        CandidateFinder finder2{ symtab, tenv };
1081                        finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() );
1082                        if ( finder2.candidates.empty() ) return;
1083
1084                        for ( const CandidateRef & r1 : finder1.candidates ) {
1085                                for ( const CandidateRef & r2 : finder2.candidates ) {
1086                                        ast::TypeEnvironment env{ r1->env };
1087                                        env.simpleCombine( r2->env );
1088                                        ast::OpenVarSet open{ r1->open };
1089                                        mergeOpenVars( open, r2->open );
1090                                        ast::AssertionSet need;
1091                                        mergeAssertionSet( need, r1->need );
1092                                        mergeAssertionSet( need, r2->need );
1093
1094                                        addCandidate(
1095                                                new ast::LogicalExpr{ 
1096                                                        logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },
1097                                                move( env ), move( open ), move( need ), r1->cost + r2->cost );
1098                                }
1099                        }
1100                }
1101
1102                void postvisit( const ast::ConditionalExpr * conditionalExpr ) {
1103                        // candidates for condition
1104                        CandidateFinder finder1{ symtab, tenv };
1105                        finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() );
1106                        if ( finder1.candidates.empty() ) return;
1107
1108                        // candidates for true result
1109                        CandidateFinder finder2{ symtab, tenv };
1110                        finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() );
1111                        if ( finder2.candidates.empty() ) return;
1112
1113                        // candidates for false result
1114                        CandidateFinder finder3{ symtab, tenv };
1115                        finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() );
1116                        if ( finder3.candidates.empty() ) return;
1117
1118                        for ( const CandidateRef & r1 : finder1.candidates ) {
1119                                for ( const CandidateRef & r2 : finder2.candidates ) {
1120                                        for ( const CandidateRef & r3 : finder3.candidates ) {
1121                                                ast::TypeEnvironment env{ r1->env };
1122                                                env.simpleCombine( r2->env );
1123                                                env.simpleCombine( r3->env );
1124                                                ast::OpenVarSet open{ r1->open };
1125                                                mergeOpenVars( open, r2->open );
1126                                                mergeOpenVars( open, r3->open );
1127                                                ast::AssertionSet need;
1128                                                mergeAssertionSet( need, r1->need );
1129                                                mergeAssertionSet( need, r2->need );
1130                                                mergeAssertionSet( need, r3->need );
1131                                                ast::AssertionSet have;
1132
1133                                                // unify true and false results, then infer parameters to produce new
1134                                                // candidates
1135                                                ast::ptr< ast::Type > common;
1136                                                if ( 
1137                                                        unify( 
1138                                                                r2->expr->result, r3->expr->result, env, need, have, open, symtab, 
1139                                                                common ) 
1140                                                ) {
1141                                                        #warning unimplemented
1142                                                        assert(false);
1143                                                }
1144                                        }
1145                                }
1146                        }
1147                }
1148
1149                void postvisit( const ast::CommaExpr * commaExpr ) {
1150                        ast::TypeEnvironment env{ tenv };
1151                        ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, symtab, env );
1152                       
1153                        CandidateFinder finder2{ symtab, env };
1154                        finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() );
1155
1156                        for ( const CandidateRef & r2 : finder2.candidates ) {
1157                                addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } );
1158                        }
1159                }
1160
1161                void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) {
1162                        addCandidate( ctorExpr, tenv );
1163                }
1164
1165                void postvisit( const ast::ConstructorExpr * ctorExpr ) {
1166                        CandidateFinder finder{ symtab, tenv };
1167                        finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() );
1168                        for ( CandidateRef & r : finder.candidates ) {
1169                                addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } );
1170                        }
1171                }
1172
1173                void postvisit( const ast::RangeExpr * rangeExpr ) {
1174                        // resolve low and high, accept candidates where low and high types unify
1175                        CandidateFinder finder1{ symtab, tenv };
1176                        finder1.find( rangeExpr->low, ResolvMode::withAdjustment() );
1177                        if ( finder1.candidates.empty() ) return;
1178
1179                        CandidateFinder finder2{ symtab, tenv };
1180                        finder2.find( rangeExpr->high, ResolvMode::withAdjustment() );
1181                        if ( finder2.candidates.empty() ) return;
1182
1183                        for ( const CandidateRef & r1 : finder1.candidates ) {
1184                                for ( const CandidateRef & r2 : finder2.candidates ) {
1185                                        ast::TypeEnvironment env{ r1->env };
1186                                        env.simpleCombine( r2->env );
1187                                        ast::OpenVarSet open{ r1->open };
1188                                        mergeOpenVars( open, r2->open );
1189                                        ast::AssertionSet need;
1190                                        mergeAssertionSet( need, r1->need );
1191                                        mergeAssertionSet( need, r2->need );
1192                                        ast::AssertionSet have;
1193
1194                                        ast::ptr< ast::Type > common;
1195                                        if ( 
1196                                                unify( 
1197                                                        r1->expr->result, r2->expr->result, env, need, have, open, symtab, 
1198                                                        common ) 
1199                                        ) {
1200                                                ast::RangeExpr * newExpr = 
1201                                                        new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };
1202                                                newExpr->result = common ? common : r1->expr->result;
1203                                               
1204                                                #warning unimplemented
1205                                                assert(false);
1206                                        }
1207                                }
1208                        }
1209                }
1210
1211                void postvisit( const ast::UntypedTupleExpr * tupleExpr ) {
1212                        std::vector< CandidateFinder > subCandidates = 
1213                                selfFinder.findSubExprs( tupleExpr->exprs );
1214                        std::vector< CandidateList > possibilities;
1215                        combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) );
1216
1217                        for ( const CandidateList & subs : possibilities ) {
1218                                std::vector< ast::ptr< ast::Expr > > exprs;
1219                                exprs.reserve( subs.size() );
1220                                for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); }
1221
1222                                ast::TypeEnvironment env;
1223                                ast::OpenVarSet open;
1224                                ast::AssertionSet need;
1225                                for ( const CandidateRef & sub : subs ) {
1226                                        env.simpleCombine( sub->env );
1227                                        mergeOpenVars( open, sub->open );
1228                                        mergeAssertionSet( need, sub->need );
1229                                }
1230
1231                                addCandidate(
1232                                        new ast::TupleExpr{ tupleExpr->location, move( exprs ) }, 
1233                                        move( env ), move( open ), move( need ), sumCost( subs ) );
1234                        }
1235                }
1236
1237                void postvisit( const ast::TupleExpr * tupleExpr ) {
1238                        addCandidate( tupleExpr, tenv );
1239                }
1240
1241                void postvisit( const ast::TupleIndexExpr * tupleExpr ) {
1242                        addCandidate( tupleExpr, tenv );
1243                }
1244
1245                void postvisit( const ast::TupleAssignExpr * tupleExpr ) {
1246                        addCandidate( tupleExpr, tenv );
1247                }
1248
1249                void postvisit( const ast::UniqueExpr * unqExpr ) {
1250                        CandidateFinder finder{ symtab, tenv };
1251                        finder.find( unqExpr->expr, ResolvMode::withAdjustment() );
1252                        for ( CandidateRef & r : finder.candidates ) {
1253                                // ensure that the the id is passed on so that the expressions are "linked"
1254                                addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } );
1255                        }
1256                }
1257
1258                void postvisit( const ast::StmtExpr * stmtExpr ) {
1259                        #warning unimplemented
1260                        (void)stmtExpr;
1261                        assert(false);
1262                }
1263
1264                void postvisit( const ast::UntypedInitExpr * initExpr ) {
1265                        #warning unimplemented
1266                        (void)initExpr;
1267                        assert(false);
1268                }
1269
1270                void postvisit( const ast::InitExpr * ) {
1271                        assertf( false, "CandidateFinder should never see a resolved InitExpr." );
1272                }
1273
1274                void postvisit( const ast::DeletedExpr * ) {
1275                        assertf( false, "CandidateFinder should never see a DeletedExpr." );
1276                }
1277
1278                void postvisit( const ast::GenericExpr * ) {
1279                        assertf( false, "_Generic is not yet supported." );
1280                }
1281        };
1282
1283        /// Prunes a list of candidates down to those that have the minimum conversion cost for a given
1284        /// return type. Skips ambiguous candidates.
1285        CandidateList pruneCandidates( CandidateList & candidates ) {
1286                struct PruneStruct {
1287                        CandidateRef candidate;
1288                        bool ambiguous;
1289
1290                        PruneStruct() = default;
1291                        PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}
1292                };
1293
1294                // find lowest-cost candidate for each type
1295                std::unordered_map< std::string, PruneStruct > selected;
1296                for ( CandidateRef & candidate : candidates ) {
1297                        std::string mangleName;
1298                        {
1299                                ast::ptr< ast::Type > newType = candidate->expr->result;
1300                                candidate->env.apply( newType );
1301                                mangleName = Mangle::mangle( newType );
1302                        }
1303
1304                        auto found = selected.find( mangleName );
1305                        if ( found != selected.end() ) {
1306                                if ( candidate->cost < found->second.candidate->cost ) {
1307                                        PRINT(
1308                                                std::cerr << "cost " << candidate->cost << " beats " 
1309                                                        << found->second.candidate->cost << std::endl;
1310                                        )
1311
1312                                        found->second = PruneStruct{ candidate };
1313                                } else if ( candidate->cost == found->second.candidate->cost ) {
1314                                        // if one of the candidates contains a deleted identifier, can pick the other,
1315                                        // since deleted expressions should not be ambiguous if there is another option
1316                                        // that is at least as good
1317                                        if ( findDeletedExpr( candidate->expr ) ) {
1318                                                // do nothing
1319                                                PRINT( std::cerr << "candidate is deleted" << std::endl; )
1320                                        } else if ( findDeletedExpr( found->second.candidate->expr ) ) {
1321                                                PRINT( std::cerr << "current is deleted" << std::endl; )
1322                                                found->second = PruneStruct{ candidate };
1323                                        } else {
1324                                                PRINT( std::cerr << "marking ambiguous" << std::endl; )
1325                                                found->second.ambiguous = true;
1326                                        }
1327                                } else {
1328                                        PRINT(
1329                                                std::cerr << "cost " << candidate->cost << " loses to " 
1330                                                        << found->second.candidate->cost << std::endl;
1331                                        )
1332                                }
1333                        } else {
1334                                selected.emplace_hint( found, mangleName, candidate );
1335                        }
1336                }
1337
1338                // report unambiguous min-cost candidates
1339                CandidateList out;
1340                for ( auto & target : selected ) {
1341                        if ( target.second.ambiguous ) continue;
1342
1343                        CandidateRef cand = target.second.candidate;
1344                       
1345                        ast::ptr< ast::Type > newResult = cand->expr->result;
1346                        cand->env.applyFree( newResult );
1347                        cand->expr = ast::mutate_field(
1348                                cand->expr.get(), &ast::Expr::result, move( newResult ) );
1349                       
1350                        out.emplace_back( cand );
1351                }
1352                return out;
1353        }
1354
1355} // anonymous namespace
1356
1357void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {
1358        // Find alternatives for expression
1359        ast::Pass<Finder> finder{ *this };
1360        expr->accept( finder );
1361
1362        if ( mode.failFast && candidates.empty() ) {
1363                SemanticError( expr, "No reasonable alternatives for expression " );
1364        }
1365
1366        if ( mode.satisfyAssns || mode.prune ) {
1367                // trim candidates to just those where the assertions are satisfiable
1368                // - necessary pre-requisite to pruning
1369                CandidateList satisfied;
1370                std::vector< std::string > errors;
1371                for ( auto & candidate : candidates ) {
1372                        satisfyAssertions( *candidate, symtab, satisfied, errors );
1373                }
1374
1375                // fail early if none such
1376                if ( mode.failFast && satisfied.empty() ) {
1377                        std::ostringstream stream;
1378                        stream << "No alternatives with satisfiable assertions for " << expr << "\n";
1379                        for ( const auto& err : errors ) {
1380                                stream << err;
1381                        }
1382                        SemanticError( expr->location, stream.str() );
1383                }
1384
1385                // reset candidates
1386                candidates = move( satisfied );
1387        }
1388
1389        if ( mode.prune ) {
1390                // trim candidates to single best one
1391                PRINT(
1392                        std::cerr << "alternatives before prune:" << std::endl;
1393                        print( std::cerr, candidates );
1394                )
1395
1396                CandidateList pruned = pruneCandidates( candidates );
1397               
1398                if ( mode.failFast && pruned.empty() ) {
1399                        std::ostringstream stream;
1400                        CandidateList winners = findMinCost( candidates );
1401                        stream << "Cannot choose between " << winners.size() << " alternatives for "
1402                                "expression\n";
1403                        ast::print( stream, expr );
1404                        stream << " Alternatives are:\n";
1405                        print( stream, winners, 1 );
1406                        SemanticError( expr->location, stream.str() );
1407                }
1408
1409                auto oldsize = candidates.size();
1410                candidates = move( pruned );
1411
1412                PRINT(
1413                        std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
1414                )
1415                PRINT(
1416                        std::cerr << "there are " << candidates.size() << " alternatives after elimination" 
1417                                << std::endl;
1418                )
1419        }
1420
1421        // adjust types after pruning so that types substituted by pruneAlternatives are correctly
1422        // adjusted
1423        if ( mode.adjust ) {
1424                for ( CandidateRef & r : candidates ) {
1425                        r->expr = ast::mutate_field( 
1426                                r->expr.get(), &ast::Expr::result, 
1427                                adjustExprType( r->expr->result, r->env, symtab ) );
1428                }
1429        }
1430
1431        // Central location to handle gcc extension keyword, etc. for all expressions
1432        for ( CandidateRef & r : candidates ) {
1433                if ( r->expr->extension != expr->extension ) {
1434                        r->expr.get_and_mutate()->extension = expr->extension;
1435                }
1436        }
1437}
1438
1439std::vector< CandidateFinder > CandidateFinder::findSubExprs( 
1440        const std::vector< ast::ptr< ast::Expr > > & xs
1441) {
1442        std::vector< CandidateFinder > out;
1443
1444        for ( const auto & x : xs ) {
1445                out.emplace_back( symtab, env );
1446                out.back().find( x, ResolvMode::withAdjustment() );
1447               
1448                PRINT(
1449                        std::cerr << "findSubExprs" << std::endl;
1450                        print( std::cerr, out.back().candidates );
1451                )
1452        }
1453
1454        return out;
1455}
1456
1457} // namespace ResolvExpr
1458
1459// Local Variables: //
1460// tab-width: 4 //
1461// mode: c++ //
1462// compile-command: "make install" //
1463// End: //
Note: See TracBrowser for help on using the repository browser.