source: src/ResolvExpr/AlternativeFinder.cc @ 54043f4

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 54043f4 was 54043f4, checked in by Rob Schluntz <rschlunt@…>, 4 years ago

Add with expression cost into conversion cost

  • Property mode set to 100644
File size: 73.8 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// AlternativeFinder.cc --
8//
9// Author           : Richard C. Bilson
10// Created On       : Sat May 16 23:52:08 2015
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Sat Feb 17 11:19:39 2018
13// Update Count     : 33
14//
15
16#include <algorithm>               // for copy
17#include <cassert>                 // for strict_dynamic_cast, assert, assertf
18#include <cstddef>                 // for size_t
19#include <iostream>                // for operator<<, cerr, ostream, endl
20#include <iterator>                // for back_insert_iterator, back_inserter
21#include <list>                    // for _List_iterator, list, _List_const_...
22#include <map>                     // for _Rb_tree_iterator, map, _Rb_tree_c...
23#include <memory>                  // for allocator_traits<>::value_type, unique_ptr
24#include <utility>                 // for pair
25#include <vector>                  // for vector
26
27#include "Alternative.h"           // for AltList, Alternative
28#include "AlternativeFinder.h"
29#include "Common/SemanticError.h"  // for SemanticError
30#include "Common/utility.h"        // for deleteAll, printAll, CodeLocation
31#include "Cost.h"                  // for Cost, Cost::zero, operator<<, Cost...
32#include "ExplodedActual.h"        // for ExplodedActual
33#include "InitTweak/InitTweak.h"   // for getFunctionName
34#include "RenameVars.h"            // for RenameVars, global_renamer
35#include "ResolveTypeof.h"         // for resolveTypeof
36#include "Resolver.h"              // for resolveStmtExpr
37#include "SymTab/Indexer.h"        // for Indexer
38#include "SymTab/Mangler.h"        // for Mangler
39#include "SymTab/Validate.h"       // for validateType
40#include "SynTree/Constant.h"      // for Constant
41#include "SynTree/Declaration.h"   // for DeclarationWithType, TypeDecl, Dec...
42#include "SynTree/Expression.h"    // for Expression, CastExpr, NameExpr
43#include "SynTree/Initializer.h"   // for SingleInit, operator<<, Designation
44#include "SynTree/SynTree.h"       // for UniqueId
45#include "SynTree/Type.h"          // for Type, FunctionType, PointerType
46#include "Tuples/Explode.h"        // for explode
47#include "Tuples/Tuples.h"         // for isTtype, handleTupleAssignment
48#include "Unify.h"                 // for unify
49#include "typeops.h"               // for adjustExprType, polyCost, castCost
50
51extern bool resolvep;
52#define PRINT( text ) if ( resolvep ) { text }
53//#define DEBUG_COST
54
55using std::move;
56
57/// copies any copyable type
58template<typename T>
59T copy(const T& x) { return x; }
60
61namespace ResolvExpr {
62        struct AlternativeFinder::Finder : public WithShortCircuiting {
63                Finder( AlternativeFinder & altFinder ) : altFinder( altFinder ), indexer( altFinder.indexer ), alternatives( altFinder.alternatives ), env( altFinder.env ), targetType( altFinder.targetType )  {}
64
65                void previsit( BaseSyntaxNode * ) { visit_children = false; }
66
67                void postvisit( ApplicationExpr * applicationExpr );
68                void postvisit( UntypedExpr * untypedExpr );
69                void postvisit( AddressExpr * addressExpr );
70                void postvisit( LabelAddressExpr * labelExpr );
71                void postvisit( CastExpr * castExpr );
72                void postvisit( VirtualCastExpr * castExpr );
73                void postvisit( UntypedMemberExpr * memberExpr );
74                void postvisit( MemberExpr * memberExpr );
75                void postvisit( NameExpr * variableExpr );
76                void postvisit( VariableExpr * variableExpr );
77                void postvisit( ConstantExpr * constantExpr );
78                void postvisit( SizeofExpr * sizeofExpr );
79                void postvisit( AlignofExpr * alignofExpr );
80                void postvisit( UntypedOffsetofExpr * offsetofExpr );
81                void postvisit( OffsetofExpr * offsetofExpr );
82                void postvisit( OffsetPackExpr * offsetPackExpr );
83                void postvisit( AttrExpr * attrExpr );
84                void postvisit( LogicalExpr * logicalExpr );
85                void postvisit( ConditionalExpr * conditionalExpr );
86                void postvisit( CommaExpr * commaExpr );
87                void postvisit( ImplicitCopyCtorExpr  * impCpCtorExpr );
88                void postvisit( ConstructorExpr  * ctorExpr );
89                void postvisit( RangeExpr  * rangeExpr );
90                void postvisit( UntypedTupleExpr * tupleExpr );
91                void postvisit( TupleExpr * tupleExpr );
92                void postvisit( TupleIndexExpr * tupleExpr );
93                void postvisit( TupleAssignExpr * tupleExpr );
94                void postvisit( UniqueExpr * unqExpr );
95                void postvisit( StmtExpr * stmtExpr );
96                void postvisit( UntypedInitExpr * initExpr );
97                void postvisit( InitExpr * initExpr );
98                void postvisit( DeletedExpr * delExpr );
99
100                /// Adds alternatives for anonymous members
101                void addAnonConversions( const Alternative & alt );
102                /// Adds alternatives for member expressions, given the aggregate, conversion cost for that aggregate, and name of the member
103                template< typename StructOrUnionType > void addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member );
104                /// Adds alternatives for member expressions where the left side has tuple type
105                void addTupleMembers( TupleType * tupleType, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member );
106                /// Adds alternatives for offsetof expressions, given the base type and name of the member
107                template< typename StructOrUnionType > void addOffsetof( StructOrUnionType *aggInst, const std::string &name );
108                /// Takes a final result and checks if its assertions can be satisfied
109                template<typename OutputIterator>
110                void validateFunctionAlternative( const Alternative &func, ArgPack& result, const std::vector<ArgPack>& results, OutputIterator out );
111                /// Finds matching alternatives for a function, given a set of arguments
112                template<typename OutputIterator>
113                void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs& args, OutputIterator out );
114                /// Checks if assertion parameters match for a new alternative
115                template< typename OutputIterator >
116                void inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out );
117        private:
118                AlternativeFinder & altFinder;
119                const SymTab::Indexer &indexer;
120                AltList & alternatives;
121                const TypeEnvironment &env;
122                Type *& targetType;
123        };
124
125        Cost sumCost( const AltList &in ) {
126                Cost total = Cost::zero;
127                for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
128                        total += i->cost;
129                }
130                return total;
131        }
132
133        void printAlts( const AltList &list, std::ostream &os, unsigned int indentAmt ) {
134                Indenter indent = { Indenter::tabsize, indentAmt };
135                for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) {
136                        i->print( os, indent );
137                        os << std::endl;
138                }
139        }
140
141        namespace {
142                void makeExprList( const AltList &in, std::list< Expression* > &out ) {
143                        for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
144                                out.push_back( i->expr->clone() );
145                        }
146                }
147
148                struct PruneStruct {
149                        bool isAmbiguous;
150                        AltList::iterator candidate;
151                        PruneStruct() {}
152                        PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {}
153                };
154
155                /// Prunes a list of alternatives down to those that have the minimum conversion cost for a given return type; skips ambiguous interpretations
156                template< typename InputIterator, typename OutputIterator >
157                void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out ) {
158                        // select the alternatives that have the minimum conversion cost for a particular set of result types
159                        std::map< std::string, PruneStruct > selected;
160                        for ( AltList::iterator candidate = begin; candidate != end; ++candidate ) {
161                                PruneStruct current( candidate );
162                                std::string mangleName;
163                                {
164                                        Type * newType = candidate->expr->get_result()->clone();
165                                        candidate->env.apply( newType );
166                                        mangleName = SymTab::Mangler::mangle( newType );
167                                        delete newType;
168                                }
169                                std::map< std::string, PruneStruct >::iterator mapPlace = selected.find( mangleName );
170                                if ( mapPlace != selected.end() ) {
171                                        if ( candidate->cost < mapPlace->second.candidate->cost ) {
172                                                PRINT(
173                                                        std::cerr << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl;
174                                                )
175                                                selected[ mangleName ] = current;
176                                        } else if ( candidate->cost == mapPlace->second.candidate->cost ) {
177                                                PRINT(
178                                                        std::cerr << "marking ambiguous" << std::endl;
179                                                )
180                                                mapPlace->second.isAmbiguous = true;
181                                        } else {
182                                                PRINT(
183                                                        std::cerr << "cost " << candidate->cost << " loses to " << mapPlace->second.candidate->cost << std::endl;
184                                                )
185                                        }
186                                } else {
187                                        selected[ mangleName ] = current;
188                                }
189                        }
190
191                        // accept the alternatives that were unambiguous
192                        for ( std::map< std::string, PruneStruct >::iterator target = selected.begin(); target != selected.end(); ++target ) {
193                                if ( ! target->second.isAmbiguous ) {
194                                        Alternative &alt = *target->second.candidate;
195                                        alt.env.applyFree( alt.expr->get_result() );
196                                        *out++ = alt;
197                                }
198                        }
199                }
200
201                void renameTypes( Expression *expr ) {
202                        renameTyVars( expr->result );
203                }
204        } // namespace
205
206        void referenceToRvalueConversion( Expression *& expr, Cost & cost ) {
207                if ( dynamic_cast< ReferenceType * >( expr->get_result() ) ) {
208                        // cast away reference from expr
209                        expr = new CastExpr( expr, expr->get_result()->stripReferences()->clone() );
210                        cost.incReference();
211                }
212        }
213
214        template< typename InputIterator, typename OutputIterator >
215        void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) {
216                while ( begin != end ) {
217                        AlternativeFinder finder( indexer, env );
218                        finder.findWithAdjustment( *begin );
219                        // XXX  either this
220                        //Designators::fixDesignations( finder, (*begin++)->get_argName() );
221                        // or XXX this
222                        begin++;
223                        PRINT(
224                                std::cerr << "findSubExprs" << std::endl;
225                                printAlts( finder.alternatives, std::cerr );
226                        )
227                        *out++ = finder;
228                }
229        }
230
231        AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env )
232                : indexer( indexer ), env( env ) {
233        }
234
235        void AlternativeFinder::find( Expression *expr, bool adjust, bool prune, bool failFast ) {
236                PassVisitor<Finder> finder( *this );
237                expr->accept( finder );
238                if ( failFast && alternatives.empty() ) {
239                        PRINT(
240                                std::cerr << "No reasonable alternatives for expression " << expr << std::endl;
241                        )
242                        throw SemanticError( expr, "No reasonable alternatives for expression " );
243                }
244                if ( prune ) {
245                        auto oldsize = alternatives.size();
246                        PRINT(
247                                std::cerr << "alternatives before prune:" << std::endl;
248                                printAlts( alternatives, std::cerr );
249                        )
250                        AltList pruned;
251                        pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned ) );
252                        if ( failFast && pruned.empty() ) {
253                                std::ostringstream stream;
254                                AltList winners;
255                                findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) );
256                                stream << "Cannot choose between " << winners.size() << " alternatives for expression\n";
257                                expr->print( stream );
258                                stream << " Alternatives are:\n";
259                                printAlts( winners, stream, 1 );
260                                throw SemanticError( expr->location, stream.str() );
261                        }
262                        alternatives = move(pruned);
263                        PRINT(
264                                std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
265                        )
266                        PRINT(
267                                std::cerr << "there are " << alternatives.size() << " alternatives after elimination" << std::endl;
268                        )
269                }
270                // adjust types after pruning so that types substituted by pruneAlternatives are correctly adjusted
271                for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) {
272                        if ( adjust ) {
273                                adjustExprType( i->expr->get_result(), i->env, indexer );
274                        }
275                }
276
277                // Central location to handle gcc extension keyword, etc. for all expression types.
278                for ( Alternative &iter: alternatives ) {
279                        iter.expr->set_extension( expr->get_extension() );
280                        iter.expr->location = expr->location;
281                } // for
282        }
283
284        void AlternativeFinder::findWithAdjustment( Expression *expr ) {
285                find( expr, true );
286        }
287
288        void AlternativeFinder::findWithoutPrune( Expression * expr ) {
289                find( expr, true, false );
290        }
291
292        void AlternativeFinder::maybeFind( Expression * expr ) {
293                find( expr, true, true, false );
294        }
295
296        void AlternativeFinder::Finder::addAnonConversions( const Alternative & alt ) {
297                // adds anonymous member interpretations whenever an aggregate value type is seen.
298                // it's okay for the aggregate expression to have reference type -- cast it to the base type to treat the aggregate as the referenced value
299                std::unique_ptr<Expression> aggrExpr( alt.expr->clone() );
300                alt.env.apply( aggrExpr->get_result() );
301                Type * aggrType = aggrExpr->get_result();
302                if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
303                        aggrType = aggrType->stripReferences();
304                        aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) );
305                }
306
307                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
308                        NameExpr nameExpr( "" );
309                        addAggMembers( structInst, aggrExpr.get(), alt.cost+Cost::safe, alt.env, &nameExpr );
310                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
311                        NameExpr nameExpr( "" );
312                        addAggMembers( unionInst, aggrExpr.get(), alt.cost+Cost::safe, alt.env, &nameExpr );
313                } // if
314        }
315
316        template< typename StructOrUnionType >
317        void AlternativeFinder::Finder::addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
318                // by this point, member must be a name expr
319                NameExpr * nameExpr = dynamic_cast< NameExpr * >( member );
320                if ( ! nameExpr ) return;
321                const std::string & name = nameExpr->get_name();
322                std::list< Declaration* > members;
323                aggInst->lookup( name, members );
324
325                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
326                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
327                                alternatives.push_back( Alternative( new MemberExpr( dwt, expr->clone() ), env, newCost ) );
328                                renameTypes( alternatives.back().expr );
329                                addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a member expression.
330                        } else {
331                                assert( false );
332                        }
333                }
334        }
335
336        void AlternativeFinder::Finder::addTupleMembers( TupleType * tupleType, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
337                if ( ConstantExpr * constantExpr = dynamic_cast< ConstantExpr * >( member ) ) {
338                        // get the value of the constant expression as an int, must be between 0 and the length of the tuple type to have meaning
339                        // xxx - this should be improved by memoizing the value of constant exprs
340                        // during parsing and reusing that information here.
341                        std::stringstream ss( constantExpr->get_constant()->get_value() );
342                        int val = 0;
343                        std::string tmp;
344                        if ( ss >> val && ! (ss >> tmp) ) {
345                                if ( val >= 0 && (unsigned int)val < tupleType->size() ) {
346                                        alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
347                                } // if
348                        } // if
349                } else if ( NameExpr * nameExpr = dynamic_cast< NameExpr * >( member ) ) {
350                        // xxx - temporary hack until 0/1 are int constants
351                        if ( nameExpr->get_name() == "0" || nameExpr->get_name() == "1" ) {
352                                std::stringstream ss( nameExpr->get_name() );
353                                int val;
354                                ss >> val;
355                                alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
356                        }
357                } // if
358        }
359
360        void AlternativeFinder::Finder::postvisit( ApplicationExpr *applicationExpr ) {
361                alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) );
362        }
363
364        Cost computeConversionCost( Type * actualType, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
365                PRINT(
366                        std::cerr << std::endl << "converting ";
367                        actualType->print( std::cerr, 8 );
368                        std::cerr << std::endl << " to ";
369                        formalType->print( std::cerr, 8 );
370                        std::cerr << std::endl << "environment is: ";
371                        env.print( std::cerr, 8 );
372                        std::cerr << std::endl;
373                )
374                Cost convCost = conversionCost( actualType, formalType, indexer, env );
375                PRINT(
376                        std::cerr << std::endl << "cost is " << convCost << std::endl;
377                )
378                if ( convCost == Cost::infinity ) {
379                        return convCost;
380                }
381                convCost.incPoly( polyCost( formalType, env, indexer ) + polyCost( actualType, env, indexer ) );
382                PRINT(
383                        std::cerr << "cost with polycost is " << convCost << std::endl;
384                )
385                return convCost;
386        }
387
388        Cost computeExpressionConversionCost( Expression *& actualExpr, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
389                Cost convCost = computeConversionCost( actualExpr->result, formalType, indexer, env );
390
391                // if there is a non-zero conversion cost, ignoring poly cost, then the expression requires conversion.
392                // ignore poly cost for now, since this requires resolution of the cast to infer parameters and this
393                // does not currently work for the reason stated below.
394                Cost tmpCost = convCost;
395                tmpCost.incPoly( -tmpCost.get_polyCost() );
396                if ( tmpCost != Cost::zero ) {
397                        Type *newType = formalType->clone();
398                        env.apply( newType );
399                        actualExpr = new CastExpr( actualExpr, newType );
400                        // xxx - SHOULD be able to resolve this cast, but at the moment pointers are not castable to zero_t, but are implicitly convertible. This is clearly
401                        // inconsistent, once this is fixed it should be possible to resolve the cast.
402                        // xxx - this isn't working, it appears because type1 (the formal type) is seen as widenable, but it shouldn't be, because this makes the conversion from DT* to DT* since commontype(zero_t, DT*) is DT*, rather than just nothing.
403
404                        // AlternativeFinder finder( indexer, env );
405                        // finder.findWithAdjustment( actualExpr );
406                        // assertf( finder.get_alternatives().size() > 0, "Somehow castable expression failed to find alternatives." );
407                        // assertf( finder.get_alternatives().size() == 1, "Somehow got multiple alternatives for known cast expression." );
408                        // Alternative & alt = finder.get_alternatives().front();
409                        // delete actualExpr;
410                        // actualExpr = alt.expr->clone();
411                }
412                return convCost;
413        }
414
415        Cost computeApplicationConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) {
416                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( alt.expr );
417                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
418                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
419
420                Cost convCost = Cost::zero;
421                std::list< DeclarationWithType* >& formals = function->get_parameters();
422                std::list< DeclarationWithType* >::iterator formal = formals.begin();
423                std::list< Expression* >& actuals = appExpr->get_args();
424
425                for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
426                        Type * actualType = (*actualExpr)->get_result();
427                        PRINT(
428                                std::cerr << "actual expression:" << std::endl;
429                                (*actualExpr)->print( std::cerr, 8 );
430                                std::cerr << "--- results are" << std::endl;
431                                actualType->print( std::cerr, 8 );
432                        )
433                        if ( formal == formals.end() ) {
434                                if ( function->get_isVarArgs() ) {
435                                        convCost.incUnsafe();
436                                        PRINT( std::cerr << "end of formals with varargs function: inc unsafe: " << convCost << std::endl; ; )
437                                        // convert reference-typed expressions to value-typed expressions
438                                        referenceToRvalueConversion( *actualExpr, convCost );
439                                        continue;
440                                } else {
441                                        return Cost::infinity;
442                                }
443                        }
444                        Type * formalType = (*formal)->get_type();
445                        convCost += computeExpressionConversionCost( *actualExpr, formalType, indexer, alt.env );
446                        ++formal; // can't be in for-loop update because of the continue
447                }
448                if ( formal != formals.end() ) {
449                        return Cost::infinity;
450                }
451
452                for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
453                        convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
454                }
455
456                return convCost;
457        }
458
459        /// Adds type variables to the open variable set and marks their assertions
460        void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) {
461                for ( Type::ForallList::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
462                        unifiableVars[ (*tyvar)->get_name() ] = TypeDecl::Data{ *tyvar };
463                        for ( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) {
464                                needAssertions[ *assert ].isUsed = true;
465                        }
466///     needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() );
467                }
468        }
469
470        // /// Map of declaration uniqueIds (intended to be the assertions in an AssertionSet) to their parents and the number of times they've been included
471        //typedef std::unordered_map< UniqueId, std::unordered_map< UniqueId, unsigned > > AssertionParentSet;
472
473        static const int recursionLimit = /*10*/ 4;  ///< Limit to depth of recursion satisfaction
474        //static const unsigned recursionParentLimit = 1;  ///< Limit to the number of times an assertion can recursively use itself
475
476        void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
477                for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
478                        if ( i->second.isUsed ) {
479                                indexer.addId( i->first );
480                        }
481                }
482        }
483
484        template< typename ForwardIterator, typename OutputIterator >
485        void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, /*const AssertionParentSet &needParents,*/
486                                                 int level, const SymTab::Indexer &indexer, OutputIterator out ) {
487                if ( begin == end ) {
488                        if ( newNeed.empty() ) {
489                                PRINT(
490                                        std::cerr << "all assertions satisfied, output alternative: ";
491                                        newAlt.print( std::cerr );
492                                        std::cerr << std::endl;
493                                );
494                                *out++ = newAlt;
495                                return;
496                        } else if ( level >= recursionLimit ) {
497                                throw SemanticError( newAlt.expr->location, "Too many recursive assertions" );
498                        } else {
499                                AssertionSet newerNeed;
500                                PRINT(
501                                        std::cerr << "recursing with new set:" << std::endl;
502                                        printAssertionSet( newNeed, std::cerr, 8 );
503                                )
504                                inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, /*needParents,*/ level+1, indexer, out );
505                                return;
506                        }
507                }
508
509                ForwardIterator cur = begin++;
510                if ( ! cur->second.isUsed ) {
511                        inferRecursive( begin, end, newAlt, openVars, decls, newNeed, /*needParents,*/ level, indexer, out );
512                        return; // xxx - should this continue? previously this wasn't here, and it looks like it should be
513                }
514                DeclarationWithType *curDecl = cur->first;
515
516                PRINT(
517                        std::cerr << "inferRecursive: assertion is ";
518                        curDecl->print( std::cerr );
519                        std::cerr << std::endl;
520                )
521                std::list< SymTab::Indexer::IdData > candidates;
522                decls.lookupId( curDecl->get_name(), candidates );
523///   if ( candidates.empty() ) { std::cerr << "no candidates!" << std::endl; }
524                for ( const auto & data : candidates ) {
525                        DeclarationWithType * candidate = data.id;
526                        PRINT(
527                                std::cerr << "inferRecursive: candidate is ";
528                                candidate->print( std::cerr );
529                                std::cerr << std::endl;
530                        )
531
532                        AssertionSet newHave, newerNeed( newNeed );
533                        TypeEnvironment newEnv( newAlt.env );
534                        OpenVarSet newOpenVars( openVars );
535                        Type *adjType = candidate->get_type()->clone();
536                        adjustExprType( adjType, newEnv, indexer );
537                        renameTyVars( adjType );
538                        PRINT(
539                                std::cerr << "unifying ";
540                                curDecl->get_type()->print( std::cerr );
541                                std::cerr << " with ";
542                                adjType->print( std::cerr );
543                                std::cerr << std::endl;
544                        )
545                        if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) {
546                                PRINT(
547                                        std::cerr << "success!" << std::endl;
548                                )
549                                SymTab::Indexer newDecls( decls );
550                                addToIndexer( newHave, newDecls );
551                                Alternative newerAlt( newAlt );
552                                newerAlt.env = newEnv;
553                                assertf( candidate->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );
554
555                                // everything with an empty idChain was pulled in by the current assertion.
556                                // add current assertion's idChain + current assertion's ID so that the correct inferParameters can be found.
557                                for ( auto & a : newerNeed ) {
558                                        if ( a.second.idChain.empty() ) {
559                                                a.second.idChain = cur->second.idChain;
560                                                a.second.idChain.push_back( curDecl->get_uniqueId() );
561                                        }
562                                }
563
564                                //AssertionParentSet newNeedParents( needParents );
565                                // skip repeatingly-self-recursive assertion satisfaction
566                                // DOESN'T WORK: grandchild nodes conflict with their cousins
567                                //if ( newNeedParents[ curDecl->get_uniqueId() ][ candDecl->get_uniqueId() ]++ > recursionParentLimit ) continue;
568
569                                Expression *varExpr = data.combine( newerAlt.cvtCost );
570                                delete varExpr->get_result();
571                                varExpr->set_result( adjType->clone() );
572                                PRINT(
573                                        std::cerr << "satisfying assertion " << curDecl->get_uniqueId() << " ";
574                                        curDecl->print( std::cerr );
575                                        std::cerr << " with declaration " << candidate->get_uniqueId() << " ";
576                                        candidate->print( std::cerr );
577                                        std::cerr << std::endl;
578                                )
579                                // follow the current assertion's ID chain to find the correct set of inferred parameters to add the candidate to (i.e. the set of inferred parameters belonging to the entity which requested the assertion parameter).
580                                InferredParams * inferParameters = &newerAlt.expr->get_inferParams();
581                                for ( UniqueId id : cur->second.idChain ) {
582                                        inferParameters = (*inferParameters)[ id ].inferParams.get();
583                                }
584                                // XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions
585                                (*inferParameters)[ curDecl->get_uniqueId() ] = ParamEntry( candidate->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );
586                                inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, /*newNeedParents,*/ level, indexer, out );
587                        } else {
588                                delete adjType;
589                        }
590                }
591        }
592
593        template< typename OutputIterator >
594        void AlternativeFinder::Finder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
595//      PRINT(
596//          std::cerr << "inferParameters: assertions needed are" << std::endl;
597//          printAll( need, std::cerr, 8 );
598//          )
599                SymTab::Indexer decls( indexer );
600                // PRINT(
601                //      std::cerr << "============= original indexer" << std::endl;
602                //      indexer.print( std::cerr );
603                //      std::cerr << "============= new indexer" << std::endl;
604                //      decls.print( std::cerr );
605                // )
606                addToIndexer( have, decls );
607                AssertionSet newNeed;
608                //AssertionParentSet needParents;
609                PRINT(
610                        std::cerr << "env is: " << std::endl;
611                        newAlt.env.print( std::cerr, 0 );
612                        std::cerr << std::endl;
613                )
614
615                inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, /*needParents,*/ 0, indexer, out );
616//      PRINT(
617//          std::cerr << "declaration 14 is ";
618//          Declaration::declFromId
619//          *out++ = newAlt;
620//          )
621        }
622
623        /// Gets a default value from an initializer, nullptr if not present
624        ConstantExpr* getDefaultValue( Initializer* init ) {
625                if ( SingleInit* si = dynamic_cast<SingleInit*>( init ) ) {
626                        if ( CastExpr* ce = dynamic_cast<CastExpr*>( si->get_value() ) ) {
627                                return dynamic_cast<ConstantExpr*>( ce->get_arg() );
628                        }
629                }
630                return nullptr;
631        }
632
633        /// State to iteratively build a match of parameter expressions to arguments
634        struct ArgPack {
635                std::size_t parent;                ///< Index of parent pack
636                std::unique_ptr<Expression> expr;  ///< The argument stored here
637                Cost cost;                         ///< The cost of this argument
638                TypeEnvironment env;               ///< Environment for this pack
639                AssertionSet need;                 ///< Assertions outstanding for this pack
640                AssertionSet have;                 ///< Assertions found for this pack
641                OpenVarSet openVars;               ///< Open variables for this pack
642                unsigned nextArg;                  ///< Index of next argument in arguments list
643                unsigned tupleStart;               ///< Number of tuples that start at this index
644                unsigned nextExpl;                 ///< Index of next exploded element
645                unsigned explAlt;                  ///< Index of alternative for nextExpl > 0
646
647                ArgPack()
648                        : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0),
649                          tupleStart(0), nextExpl(0), explAlt(0) {}
650
651                ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
652                                const OpenVarSet& openVars)
653                        : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have),
654                          openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
655
656                ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need,
657                                AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg,
658                                unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0,
659                                unsigned explAlt = 0 )
660                        : parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)),
661                          have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart),
662                          nextExpl(nextExpl), explAlt(explAlt) {}
663
664                ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have,
665                                OpenVarSet&& openVars, unsigned nextArg, Cost added )
666                        : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), cost(o.cost + added),
667                          env(move(env)), need(move(need)), have(move(have)), openVars(move(openVars)),
668                          nextArg(nextArg), tupleStart(o.tupleStart), nextExpl(0), explAlt(0) {}
669
670                /// true iff this pack is in the middle of an exploded argument
671                bool hasExpl() const { return nextExpl > 0; }
672
673                /// Gets the list of exploded alternatives for this pack
674                const ExplodedActual& getExpl( const ExplodedArgs& args ) const {
675                        return args[nextArg-1][explAlt];
676                }
677
678                /// Ends a tuple expression, consolidating the appropriate actuals
679                void endTuple( const std::vector<ArgPack>& packs ) {
680                        // add all expressions in tuple to list, summing cost
681                        std::list<Expression*> exprs;
682                        const ArgPack* pack = this;
683                        if ( expr ) { exprs.push_front( expr.release() ); }
684                        while ( pack->tupleStart == 0 ) {
685                                pack = &packs[pack->parent];
686                                exprs.push_front( pack->expr->clone() );
687                                cost += pack->cost;
688                        }
689                        // reset pack to appropriate tuple
690                        expr.reset( new TupleExpr( exprs ) );
691                        tupleStart = pack->tupleStart - 1;
692                        parent = pack->parent;
693                }
694        };
695
696        /// Instantiates an argument to match a formal, returns false if no results left
697        bool instantiateArgument( Type* formalType, Initializer* initializer,
698                        const ExplodedArgs& args, std::vector<ArgPack>& results, std::size_t& genStart,
699                        const SymTab::Indexer& indexer, unsigned nTuples = 0 ) {
700                if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) {
701                        // formalType is a TupleType - group actuals into a TupleExpr
702                        ++nTuples;
703                        for ( Type* type : *tupleType ) {
704                                // xxx - dropping initializer changes behaviour from previous, but seems correct
705                                if ( ! instantiateArgument(
706                                                type, nullptr, args, results, genStart, indexer, nTuples ) )
707                                        return false;
708                                nTuples = 0;
709                        }
710                        // re-consititute tuples for final generation
711                        for ( auto i = genStart; i < results.size(); ++i ) {
712                                results[i].endTuple( results );
713                        }
714                        return true;
715                } else if ( TypeInstType* ttype = Tuples::isTtype( formalType ) ) {
716                        // formalType is a ttype, consumes all remaining arguments
717                        // xxx - mixing default arguments with variadic??
718
719                        // completed tuples; will be spliced to end of results to finish
720                        std::vector<ArgPack> finalResults{};
721
722                        // iterate until all results completed
723                        std::size_t genEnd;
724                        ++nTuples;
725                        do {
726                                genEnd = results.size();
727
728                                // add another argument to results
729                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
730                                        auto nextArg = results[i].nextArg;
731
732                                        // use next element of exploded tuple if present
733                                        if ( results[i].hasExpl() ) {
734                                                const ExplodedActual& expl = results[i].getExpl( args );
735
736                                                unsigned nextExpl = results[i].nextExpl + 1;
737                                                if ( nextExpl == expl.exprs.size() ) {
738                                                        nextExpl = 0;
739                                                }
740
741                                                results.emplace_back(
742                                                        i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env),
743                                                        copy(results[i].need), copy(results[i].have),
744                                                        copy(results[i].openVars), nextArg, nTuples, Cost::zero, nextExpl,
745                                                        results[i].explAlt );
746
747                                                continue;
748                                        }
749
750                                        // finish result when out of arguments
751                                        if ( nextArg >= args.size() ) {
752                                                ArgPack newResult{
753                                                        results[i].env, results[i].need, results[i].have,
754                                                        results[i].openVars };
755                                                newResult.nextArg = nextArg;
756                                                Type* argType;
757
758                                                if ( nTuples > 0 || ! results[i].expr ) {
759                                                        // first iteration or no expression to clone,
760                                                        // push empty tuple expression
761                                                        newResult.parent = i;
762                                                        std::list<Expression*> emptyList;
763                                                        newResult.expr.reset( new TupleExpr( emptyList ) );
764                                                        argType = newResult.expr->get_result();
765                                                } else {
766                                                        // clone result to collect tuple
767                                                        newResult.parent = results[i].parent;
768                                                        newResult.cost = results[i].cost;
769                                                        newResult.tupleStart = results[i].tupleStart;
770                                                        newResult.expr.reset( results[i].expr->clone() );
771                                                        argType = newResult.expr->get_result();
772
773                                                        if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
774                                                                // the case where a ttype value is passed directly is special,
775                                                                // e.g. for argument forwarding purposes
776                                                                // xxx - what if passing multiple arguments, last of which is
777                                                                //       ttype?
778                                                                // xxx - what would happen if unify was changed so that unifying
779                                                                //       tuple
780                                                                // types flattened both before unifying lists? then pass in
781                                                                // TupleType (ttype) below.
782                                                                --newResult.tupleStart;
783                                                        } else {
784                                                                // collapse leftover arguments into tuple
785                                                                newResult.endTuple( results );
786                                                                argType = newResult.expr->get_result();
787                                                        }
788                                                }
789
790                                                // check unification for ttype before adding to final
791                                                if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have,
792                                                                newResult.openVars, indexer ) ) {
793                                                        finalResults.push_back( move(newResult) );
794                                                }
795
796                                                continue;
797                                        }
798
799                                        // add each possible next argument
800                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
801                                                const ExplodedActual& expl = args[nextArg][j];
802
803                                                // fresh copies of parent parameters for this iteration
804                                                TypeEnvironment env = results[i].env;
805                                                OpenVarSet openVars = results[i].openVars;
806
807                                                env.addActual( expl.env, openVars );
808
809                                                // skip empty tuple arguments by (near-)cloning parent into next gen
810                                                if ( expl.exprs.empty() ) {
811                                                        results.emplace_back(
812                                                                results[i], move(env), copy(results[i].need),
813                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
814
815                                                        continue;
816                                                }
817
818                                                // add new result
819                                                results.emplace_back(
820                                                        i, expl.exprs.front().get(), move(env), copy(results[i].need),
821                                                        copy(results[i].have), move(openVars), nextArg + 1,
822                                                        nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
823                                        }
824                                }
825
826                                // reset for next round
827                                genStart = genEnd;
828                                nTuples = 0;
829                        } while ( genEnd != results.size() );
830
831                        // splice final results onto results
832                        for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
833                                results.push_back( move(finalResults[i]) );
834                        }
835                        return ! finalResults.empty();
836                }
837
838                // iterate each current subresult
839                std::size_t genEnd = results.size();
840                for ( std::size_t i = genStart; i < genEnd; ++i ) {
841                        auto nextArg = results[i].nextArg;
842
843                        // use remainder of exploded tuple if present
844                        if ( results[i].hasExpl() ) {
845                                const ExplodedActual& expl = results[i].getExpl( args );
846                                Expression* expr = expl.exprs[results[i].nextExpl].get();
847
848                                TypeEnvironment env = results[i].env;
849                                AssertionSet need = results[i].need, have = results[i].have;
850                                OpenVarSet openVars = results[i].openVars;
851
852                                Type* actualType = expr->get_result();
853
854                                PRINT(
855                                        std::cerr << "formal type is ";
856                                        formalType->print( std::cerr );
857                                        std::cerr << std::endl << "actual type is ";
858                                        actualType->print( std::cerr );
859                                        std::cerr << std::endl;
860                                )
861
862                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
863                                        unsigned nextExpl = results[i].nextExpl + 1;
864                                        if ( nextExpl == expl.exprs.size() ) {
865                                                nextExpl = 0;
866                                        }
867
868                                        results.emplace_back(
869                                                i, expr, move(env), move(need), move(have), move(openVars), nextArg,
870                                                nTuples, Cost::zero, nextExpl, results[i].explAlt );
871                                }
872
873                                continue;
874                        }
875
876                        // use default initializers if out of arguments
877                        if ( nextArg >= args.size() ) {
878                                if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
879                                        if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
880                                                TypeEnvironment env = results[i].env;
881                                                AssertionSet need = results[i].need, have = results[i].have;
882                                                OpenVarSet openVars = results[i].openVars;
883
884                                                if ( unify( formalType, cnst->get_type(), env, need, have, openVars,
885                                                                indexer ) ) {
886                                                        results.emplace_back(
887                                                                i, cnstExpr, move(env), move(need), move(have),
888                                                                move(openVars), nextArg, nTuples );
889                                                }
890                                        }
891                                }
892
893                                continue;
894                        }
895
896                        // Check each possible next argument
897                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
898                                const ExplodedActual& expl = args[nextArg][j];
899
900                                // fresh copies of parent parameters for this iteration
901                                TypeEnvironment env = results[i].env;
902                                AssertionSet need = results[i].need, have = results[i].have;
903                                OpenVarSet openVars = results[i].openVars;
904
905                                env.addActual( expl.env, openVars );
906
907                                // skip empty tuple arguments by (near-)cloning parent into next gen
908                                if ( expl.exprs.empty() ) {
909                                        results.emplace_back(
910                                                results[i], move(env), move(need), move(have), move(openVars),
911                                                nextArg + 1, expl.cost );
912
913                                        continue;
914                                }
915
916                                // consider only first exploded actual
917                                Expression* expr = expl.exprs.front().get();
918                                Type* actualType = expr->get_result()->clone();
919
920                                PRINT(
921                                        std::cerr << "formal type is ";
922                                        formalType->print( std::cerr );
923                                        std::cerr << std::endl << "actual type is ";
924                                        actualType->print( std::cerr );
925                                        std::cerr << std::endl;
926                                )
927
928                                // attempt to unify types
929                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
930                                        // add new result
931                                        results.emplace_back(
932                                                i, expr, move(env), move(need), move(have), move(openVars), nextArg + 1,
933                                                nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
934                                }
935                        }
936                }
937
938                // reset for next parameter
939                genStart = genEnd;
940
941                return genEnd != results.size();
942        }
943
944        template<typename OutputIterator>
945        void AlternativeFinder::Finder::validateFunctionAlternative( const Alternative &func, ArgPack& result,
946                        const std::vector<ArgPack>& results, OutputIterator out ) {
947                ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
948                // sum cost and accumulate actuals
949                std::list<Expression*>& args = appExpr->get_args();
950                Cost cost = func.cost;
951                const ArgPack* pack = &result;
952                while ( pack->expr ) {
953                        args.push_front( pack->expr->clone() );
954                        cost += pack->cost;
955                        pack = &results[pack->parent];
956                }
957                // build and validate new alternative
958                Alternative newAlt( appExpr, result.env, cost );
959                PRINT(
960                        std::cerr << "instantiate function success: " << appExpr << std::endl;
961                        std::cerr << "need assertions:" << std::endl;
962                        printAssertionSet( result.need, std::cerr, 8 );
963                )
964                inferParameters( result.need, result.have, newAlt, result.openVars, out );
965        }
966
967        template<typename OutputIterator>
968        void AlternativeFinder::Finder::makeFunctionAlternatives( const Alternative &func,
969                        FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) {
970                OpenVarSet funcOpenVars;
971                AssertionSet funcNeed, funcHave;
972                TypeEnvironment funcEnv( func.env );
973                makeUnifiableVars( funcType, funcOpenVars, funcNeed );
974                // add all type variables as open variables now so that those not used in the parameter
975                // list are still considered open.
976                funcEnv.add( funcType->get_forall() );
977
978                if ( targetType && ! targetType->isVoid() && ! funcType->get_returnVals().empty() ) {
979                        // attempt to narrow based on expected target type
980                        Type * returnType = funcType->get_returnVals().front()->get_type();
981                        if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars,
982                                        indexer ) ) {
983                                // unification failed, don't pursue this function alternative
984                                return;
985                        }
986                }
987
988                // iteratively build matches, one parameter at a time
989                std::vector<ArgPack> results;
990                results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } );
991                std::size_t genStart = 0;
992
993                for ( DeclarationWithType* formal : funcType->get_parameters() ) {
994                        ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal );
995                        if ( ! instantiateArgument(
996                                        obj->get_type(), obj->get_init(), args, results, genStart, indexer ) )
997                                return;
998                }
999
1000                if ( funcType->get_isVarArgs() ) {
1001                        // append any unused arguments to vararg pack
1002                        std::size_t genEnd;
1003                        do {
1004                                genEnd = results.size();
1005
1006                                // iterate results
1007                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
1008                                        auto nextArg = results[i].nextArg;
1009
1010                                        // use remainder of exploded tuple if present
1011                                        if ( results[i].hasExpl() ) {
1012                                                const ExplodedActual& expl = results[i].getExpl( args );
1013
1014                                                unsigned nextExpl = results[i].nextExpl + 1;
1015                                                if ( nextExpl == expl.exprs.size() ) {
1016                                                        nextExpl = 0;
1017                                                }
1018
1019                                                results.emplace_back(
1020                                                        i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env),
1021                                                        copy(results[i].need), copy(results[i].have),
1022                                                        copy(results[i].openVars), nextArg, 0, Cost::zero, nextExpl,
1023                                                        results[i].explAlt );
1024
1025                                                continue;
1026                                        }
1027
1028                                        // finish result when out of arguments
1029                                        if ( nextArg >= args.size() ) {
1030                                                validateFunctionAlternative( func, results[i], results, out );
1031
1032                                                continue;
1033                                        }
1034
1035                                        // add each possible next argument
1036                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
1037                                                const ExplodedActual& expl = args[nextArg][j];
1038
1039                                                // fresh copies of parent parameters for this iteration
1040                                                TypeEnvironment env = results[i].env;
1041                                                OpenVarSet openVars = results[i].openVars;
1042
1043                                                env.addActual( expl.env, openVars );
1044
1045                                                // skip empty tuple arguments by (near-)cloning parent into next gen
1046                                                if ( expl.exprs.empty() ) {
1047                                                        results.emplace_back(
1048                                                                results[i], move(env), copy(results[i].need),
1049                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
1050
1051                                                        continue;
1052                                                }
1053
1054                                                // add new result
1055                                                results.emplace_back(
1056                                                        i, expl.exprs.front().get(), move(env), copy(results[i].need),
1057                                                        copy(results[i].have), move(openVars), nextArg + 1, 0,
1058                                                        expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
1059                                        }
1060                                }
1061
1062                                genStart = genEnd;
1063                        } while ( genEnd != results.size() );
1064                } else {
1065                        // filter out results that don't use all the arguments
1066                        for ( std::size_t i = genStart; i < results.size(); ++i ) {
1067                                ArgPack& result = results[i];
1068                                if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
1069                                        validateFunctionAlternative( func, result, results, out );
1070                                }
1071                        }
1072                }
1073        }
1074
1075        void AlternativeFinder::Finder::postvisit( UntypedExpr *untypedExpr ) {
1076                AlternativeFinder funcFinder( indexer, env );
1077                funcFinder.findWithAdjustment( untypedExpr->get_function() );
1078                // if there are no function alternatives, then proceeding is a waste of time.
1079                if ( funcFinder.alternatives.empty() ) return;
1080
1081                std::vector< AlternativeFinder > argAlternatives;
1082                altFinder.findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(),
1083                        back_inserter( argAlternatives ) );
1084
1085                // take care of possible tuple assignments
1086                // if not tuple assignment, assignment is taken care of as a normal function call
1087                Tuples::handleTupleAssignment( altFinder, untypedExpr, argAlternatives );
1088
1089                // find function operators
1090                static NameExpr *opExpr = new NameExpr( "?()" );
1091                AlternativeFinder funcOpFinder( indexer, env );
1092                // it's ok if there aren't any defined function ops
1093                funcOpFinder.maybeFind( opExpr);
1094                PRINT(
1095                        std::cerr << "known function ops:" << std::endl;
1096                        printAlts( funcOpFinder.alternatives, std::cerr, 1 );
1097                )
1098
1099                // pre-explode arguments
1100                ExplodedArgs argExpansions;
1101                argExpansions.reserve( argAlternatives.size() );
1102
1103                for ( const AlternativeFinder& arg : argAlternatives ) {
1104                        argExpansions.emplace_back();
1105                        auto& argE = argExpansions.back();
1106                        argE.reserve( arg.alternatives.size() );
1107
1108                        for ( const Alternative& actual : arg ) {
1109                                argE.emplace_back( actual, indexer );
1110                        }
1111                }
1112
1113                AltList candidates;
1114                SemanticError errors;
1115                for ( AltList::iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
1116                        try {
1117                                PRINT(
1118                                        std::cerr << "working on alternative: " << std::endl;
1119                                        func->print( std::cerr, 8 );
1120                                )
1121                                // check if the type is pointer to function
1122                                if ( PointerType *pointer = dynamic_cast< PointerType* >( func->expr->get_result()->stripReferences() ) ) {
1123                                        if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
1124                                                Alternative newFunc( *func );
1125                                                referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1126                                                makeFunctionAlternatives( newFunc, function, argExpansions,
1127                                                        std::back_inserter( candidates ) );
1128                                        }
1129                                } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->get_result()->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
1130                                        EqvClass eqvClass;
1131                                        if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) {
1132                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.type ) ) {
1133                                                        Alternative newFunc( *func );
1134                                                        referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1135                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
1136                                                                std::back_inserter( candidates ) );
1137                                                } // if
1138                                        } // if
1139                                }
1140                        } catch ( SemanticError &e ) {
1141                                errors.append( e );
1142                        }
1143                } // for
1144
1145                // try each function operator ?() with each function alternative
1146                if ( ! funcOpFinder.alternatives.empty() ) {
1147                        // add exploded function alternatives to front of argument list
1148                        std::vector<ExplodedActual> funcE;
1149                        funcE.reserve( funcFinder.alternatives.size() );
1150                        for ( const Alternative& actual : funcFinder ) {
1151                                funcE.emplace_back( actual, indexer );
1152                        }
1153                        argExpansions.insert( argExpansions.begin(), move(funcE) );
1154
1155                        for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
1156                                        funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
1157                                try {
1158                                        // check if type is a pointer to function
1159                                        if ( PointerType* pointer = dynamic_cast<PointerType*>(
1160                                                        funcOp->expr->get_result()->stripReferences() ) ) {
1161                                                if ( FunctionType* function =
1162                                                                dynamic_cast<FunctionType*>( pointer->get_base() ) ) {
1163                                                        Alternative newFunc( *funcOp );
1164                                                        referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1165                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
1166                                                                std::back_inserter( candidates ) );
1167                                                }
1168                                        }
1169                                } catch ( SemanticError &e ) {
1170                                        errors.append( e );
1171                                }
1172                        }
1173                }
1174
1175                // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
1176                if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
1177
1178                // compute conversionsion costs
1179                for ( Alternative& withFunc : candidates ) {
1180                        Cost cvtCost = computeApplicationConversionCost( withFunc, indexer );
1181
1182                        PRINT(
1183                                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr );
1184                                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
1185                                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
1186                                std::cerr << "Case +++++++++++++ " << appExpr->get_function() << std::endl;
1187                                std::cerr << "formals are:" << std::endl;
1188                                printAll( function->get_parameters(), std::cerr, 8 );
1189                                std::cerr << "actuals are:" << std::endl;
1190                                printAll( appExpr->get_args(), std::cerr, 8 );
1191                                std::cerr << "bindings are:" << std::endl;
1192                                withFunc.env.print( std::cerr, 8 );
1193                                std::cerr << "cost of conversion is:" << cvtCost << std::endl;
1194                        )
1195                        if ( cvtCost != Cost::infinity ) {
1196                                withFunc.cvtCost = cvtCost;
1197                                alternatives.push_back( withFunc );
1198                        } // if
1199                } // for
1200
1201                candidates = move(alternatives);
1202
1203                // use a new list so that alternatives are not examined by addAnonConversions twice.
1204                AltList winners;
1205                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) );
1206
1207                // function may return struct or union value, in which case we need to add alternatives
1208                // for implicitconversions to each of the anonymous members, must happen after findMinCost
1209                // since anon conversions are never the cheapest expression
1210                for ( const Alternative & alt : winners ) {
1211                        addAnonConversions( alt );
1212                }
1213                spliceBegin( alternatives, winners );
1214
1215                if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
1216                        // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
1217                        // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
1218                        //   forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
1219                        //   const char * x = "hello world";
1220                        //   unsigned char ch = x[0];
1221                        // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
1222                        // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
1223                        // fix this issue in a more robust way.
1224                        targetType = nullptr;
1225                        postvisit( untypedExpr );
1226                }
1227        }
1228
1229        bool isLvalue( Expression *expr ) {
1230                // xxx - recurse into tuples?
1231                return expr->result && ( expr->get_result()->get_lvalue() || dynamic_cast< ReferenceType * >( expr->get_result() ) );
1232        }
1233
1234        void AlternativeFinder::Finder::postvisit( AddressExpr *addressExpr ) {
1235                AlternativeFinder finder( indexer, env );
1236                finder.find( addressExpr->get_arg() );
1237                for ( Alternative& alt : finder.alternatives ) {
1238                        if ( isLvalue( alt.expr ) ) {
1239                                alternatives.push_back(
1240                                        Alternative{ new AddressExpr( alt.expr->clone() ), alt.env, alt.cost } );
1241                        } // if
1242                } // for
1243        }
1244
1245        void AlternativeFinder::Finder::postvisit( LabelAddressExpr * expr ) {
1246                alternatives.push_back( Alternative{ expr->clone(), env, Cost::zero } );
1247        }
1248
1249        Expression * restructureCast( Expression * argExpr, Type * toType ) {
1250                if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() && ! dynamic_cast<ReferenceType *>( toType ) ) {
1251                        // Argument expression is a tuple and the target type is not void and not a reference type.
1252                        // Cast each member of the tuple to its corresponding target type, producing the tuple of those
1253                        // cast expressions. If there are more components of the tuple than components in the target type,
1254                        // then excess components do not come out in the result expression (but UniqueExprs ensure that
1255                        // side effects will still be done).
1256                        if ( Tuples::maybeImpureIgnoreUnique( argExpr ) ) {
1257                                // expressions which may contain side effects require a single unique instance of the expression.
1258                                argExpr = new UniqueExpr( argExpr );
1259                        }
1260                        std::list< Expression * > componentExprs;
1261                        for ( unsigned int i = 0; i < toType->size(); i++ ) {
1262                                // cast each component
1263                                TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
1264                                componentExprs.push_back( restructureCast( idx, toType->getComponent( i ) ) );
1265                        }
1266                        delete argExpr;
1267                        assert( componentExprs.size() > 0 );
1268                        // produce the tuple of casts
1269                        return new TupleExpr( componentExprs );
1270                } else {
1271                        // handle normally
1272                        return new CastExpr( argExpr, toType->clone() );
1273                }
1274        }
1275
1276        void AlternativeFinder::Finder::postvisit( CastExpr *castExpr ) {
1277                Type *& toType = castExpr->get_result();
1278                assert( toType );
1279                toType = resolveTypeof( toType, indexer );
1280                SymTab::validateType( toType, &indexer );
1281                adjustExprType( toType, env, indexer );
1282
1283                AlternativeFinder finder( indexer, env );
1284                finder.targetType = toType;
1285                finder.findWithAdjustment( castExpr->get_arg() );
1286
1287                AltList candidates;
1288                for ( Alternative & alt : finder.alternatives ) {
1289                        AssertionSet needAssertions, haveAssertions;
1290                        OpenVarSet openVars;
1291
1292                        // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1293                        // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1294                        // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1295                        // to.
1296                        int discardedValues = alt.expr->get_result()->size() - castExpr->get_result()->size();
1297                        if ( discardedValues < 0 ) continue;
1298                        // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1299                        // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1300                        // unification run for side-effects
1301                        unify( castExpr->get_result(), alt.expr->get_result(), alt.env, needAssertions,
1302                                haveAssertions, openVars, indexer );
1303                        Cost thisCost = castCost( alt.expr->get_result(), castExpr->get_result(), indexer,
1304                                alt.env );
1305                        PRINT(
1306                                std::cerr << "working on cast with result: " << castExpr->result << std::endl;
1307                                std::cerr << "and expr type: " << alt.expr->result << std::endl;
1308                                std::cerr << "env: " << alt.env << std::endl;
1309                        )
1310                        if ( thisCost != Cost::infinity ) {
1311                                PRINT(
1312                                        std::cerr << "has finite cost." << std::endl;
1313                                )
1314                                // count one safe conversion for each value that is thrown away
1315                                thisCost.incSafe( discardedValues );
1316                                Alternative newAlt( restructureCast( alt.expr->clone(), toType ), alt.env,
1317                                        alt.cost, thisCost );
1318                                inferParameters( needAssertions, haveAssertions, newAlt, openVars,
1319                                        back_inserter( candidates ) );
1320                        } // if
1321                } // for
1322
1323                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1324                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1325                // selects first based on argument cost, then on conversion cost.
1326                AltList minArgCost;
1327                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1328                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1329        }
1330
1331        void AlternativeFinder::Finder::postvisit( VirtualCastExpr * castExpr ) {
1332                assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." );
1333                AlternativeFinder finder( indexer, env );
1334                // don't prune here, since it's guaranteed all alternatives will have the same type
1335                finder.findWithoutPrune( castExpr->get_arg() );
1336                for ( Alternative & alt : finder.alternatives ) {
1337                        alternatives.push_back( Alternative(
1338                                new VirtualCastExpr( alt.expr->clone(), castExpr->get_result()->clone() ),
1339                                alt.env, alt.cost ) );
1340                }
1341        }
1342
1343        void AlternativeFinder::Finder::postvisit( UntypedMemberExpr *memberExpr ) {
1344                AlternativeFinder funcFinder( indexer, env );
1345                funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
1346                for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
1347                        // it's okay for the aggregate expression to have reference type -- cast it to the base type to treat the aggregate as the referenced value
1348                        Cost cost = agg->cost;
1349                        Expression * aggrExpr = agg->expr->clone();
1350                        referenceToRvalueConversion( aggrExpr, cost );
1351                        std::unique_ptr<Expression> guard( aggrExpr );
1352
1353                        // find member of the given type
1354                        if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
1355                                addAggMembers( structInst, aggrExpr, cost, agg->env, memberExpr->get_member() );
1356                        } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
1357                                addAggMembers( unionInst, aggrExpr, cost, agg->env, memberExpr->get_member() );
1358                        } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
1359                                addTupleMembers( tupleType, aggrExpr, cost, agg->env, memberExpr->get_member() );
1360                        } // if
1361                } // for
1362        }
1363
1364        void AlternativeFinder::Finder::postvisit( MemberExpr *memberExpr ) {
1365                alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
1366        }
1367
1368        void AlternativeFinder::Finder::postvisit( NameExpr *nameExpr ) {
1369                std::list< SymTab::Indexer::IdData > declList;
1370                indexer.lookupId( nameExpr->name, declList );
1371                PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )
1372                for ( auto & data : declList ) {
1373                        Cost cost = Cost::zero;
1374                        Expression * newExpr = data.combine( cost );
1375                        alternatives.push_back( Alternative( newExpr, env, Cost::zero, cost ) );
1376                        PRINT(
1377                                std::cerr << "decl is ";
1378                                data.id->print( std::cerr );
1379                                std::cerr << std::endl;
1380                                std::cerr << "newExpr is ";
1381                                newExpr->print( std::cerr );
1382                                std::cerr << std::endl;
1383                        )
1384                        renameTypes( alternatives.back().expr );
1385                        addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
1386                } // for
1387        }
1388
1389        void AlternativeFinder::Finder::postvisit( VariableExpr *variableExpr ) {
1390                // not sufficient to clone here, because variable's type may have changed
1391                // since the VariableExpr was originally created.
1392                alternatives.push_back( Alternative( new VariableExpr( variableExpr->var ), env, Cost::zero ) );
1393        }
1394
1395        void AlternativeFinder::Finder::postvisit( ConstantExpr *constantExpr ) {
1396                alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
1397        }
1398
1399        void AlternativeFinder::Finder::postvisit( SizeofExpr *sizeofExpr ) {
1400                if ( sizeofExpr->get_isType() ) {
1401                        Type * newType = sizeofExpr->get_type()->clone();
1402                        alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1403                } else {
1404                        // find all alternatives for the argument to sizeof
1405                        AlternativeFinder finder( indexer, env );
1406                        finder.find( sizeofExpr->get_expr() );
1407                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1408                        AltList winners;
1409                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1410                        if ( winners.size() != 1 ) {
1411                                throw SemanticError( sizeofExpr->get_expr(), "Ambiguous expression in sizeof operand: " );
1412                        } // if
1413                        // return the lowest cost alternative for the argument
1414                        Alternative &choice = winners.front();
1415                        referenceToRvalueConversion( choice.expr, choice.cost );
1416                        alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1417                } // if
1418        }
1419
1420        void AlternativeFinder::Finder::postvisit( AlignofExpr *alignofExpr ) {
1421                if ( alignofExpr->get_isType() ) {
1422                        Type * newType = alignofExpr->get_type()->clone();
1423                        alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1424                } else {
1425                        // find all alternatives for the argument to sizeof
1426                        AlternativeFinder finder( indexer, env );
1427                        finder.find( alignofExpr->get_expr() );
1428                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1429                        AltList winners;
1430                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1431                        if ( winners.size() != 1 ) {
1432                                throw SemanticError( alignofExpr->get_expr(), "Ambiguous expression in alignof operand: " );
1433                        } // if
1434                        // return the lowest cost alternative for the argument
1435                        Alternative &choice = winners.front();
1436                        referenceToRvalueConversion( choice.expr, choice.cost );
1437                        alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1438                } // if
1439        }
1440
1441        template< typename StructOrUnionType >
1442        void AlternativeFinder::Finder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
1443                std::list< Declaration* > members;
1444                aggInst->lookup( name, members );
1445                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
1446                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
1447                                alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
1448                                renameTypes( alternatives.back().expr );
1449                        } else {
1450                                assert( false );
1451                        }
1452                }
1453        }
1454
1455        void AlternativeFinder::Finder::postvisit( UntypedOffsetofExpr *offsetofExpr ) {
1456                AlternativeFinder funcFinder( indexer, env );
1457                // xxx - resolveTypeof?
1458                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
1459                        addOffsetof( structInst, offsetofExpr->member );
1460                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
1461                        addOffsetof( unionInst, offsetofExpr->member );
1462                }
1463        }
1464
1465        void AlternativeFinder::Finder::postvisit( OffsetofExpr *offsetofExpr ) {
1466                alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
1467        }
1468
1469        void AlternativeFinder::Finder::postvisit( OffsetPackExpr *offsetPackExpr ) {
1470                alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
1471        }
1472
1473        namespace {
1474                void resolveAttr( SymTab::Indexer::IdData data, FunctionType *function, Type *argType, const TypeEnvironment &env, AlternativeFinder & finder ) {
1475                        // assume no polymorphism
1476                        // assume no implicit conversions
1477                        assert( function->get_parameters().size() == 1 );
1478                        PRINT(
1479                                std::cerr << "resolvAttr: funcDecl is ";
1480                                data.id->print( std::cerr );
1481                                std::cerr << " argType is ";
1482                                argType->print( std::cerr );
1483                                std::cerr << std::endl;
1484                        )
1485                        const SymTab::Indexer & indexer = finder.get_indexer();
1486                        AltList & alternatives = finder.get_alternatives();
1487                        if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1488                                Cost cost = Cost::zero;
1489                                Expression * newExpr = data.combine( cost );
1490                                alternatives.push_back( Alternative( new AttrExpr( newExpr, argType->clone() ), env, Cost::zero, cost ) );
1491                                for ( DeclarationWithType * retVal : function->returnVals ) {
1492                                        alternatives.back().expr->result = retVal->get_type()->clone();
1493                                } // for
1494                        } // if
1495                }
1496        }
1497
1498        void AlternativeFinder::Finder::postvisit( AttrExpr *attrExpr ) {
1499                // assume no 'pointer-to-attribute'
1500                NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1501                assert( nameExpr );
1502                std::list< SymTab::Indexer::IdData > attrList;
1503                indexer.lookupId( nameExpr->get_name(), attrList );
1504                if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1505                        for ( auto & data : attrList ) {
1506                                DeclarationWithType * id = data.id;
1507                                // check if the type is function
1508                                if ( FunctionType *function = dynamic_cast< FunctionType* >( id->get_type() ) ) {
1509                                        // assume exactly one parameter
1510                                        if ( function->get_parameters().size() == 1 ) {
1511                                                if ( attrExpr->get_isType() ) {
1512                                                        resolveAttr( data, function, attrExpr->get_type(), env, altFinder);
1513                                                } else {
1514                                                        AlternativeFinder finder( indexer, env );
1515                                                        finder.find( attrExpr->get_expr() );
1516                                                        for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1517                                                                if ( choice->expr->get_result()->size() == 1 ) {
1518                                                                        resolveAttr(data, function, choice->expr->get_result(), choice->env, altFinder );
1519                                                                } // fi
1520                                                        } // for
1521                                                } // if
1522                                        } // if
1523                                } // if
1524                        } // for
1525                } else {
1526                        for ( auto & data : attrList ) {
1527                                Cost cost = Cost::zero;
1528                                Expression * newExpr = data.combine( cost );
1529                                alternatives.push_back( Alternative( newExpr, env, Cost::zero, cost ) );
1530                                renameTypes( alternatives.back().expr );
1531                        } // for
1532                } // if
1533        }
1534
1535        void AlternativeFinder::Finder::postvisit( LogicalExpr *logicalExpr ) {
1536                AlternativeFinder firstFinder( indexer, env );
1537                firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1538                if ( firstFinder.alternatives.empty() ) return;
1539                AlternativeFinder secondFinder( indexer, env );
1540                secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1541                if ( secondFinder.alternatives.empty() ) return;
1542                for ( const Alternative & first : firstFinder.alternatives ) {
1543                        for ( const Alternative & second : secondFinder.alternatives ) {
1544                                TypeEnvironment compositeEnv;
1545                                compositeEnv.simpleCombine( first.env );
1546                                compositeEnv.simpleCombine( second.env );
1547
1548                                LogicalExpr *newExpr = new LogicalExpr( first.expr->clone(), second.expr->clone(), logicalExpr->get_isAnd() );
1549                                alternatives.push_back( Alternative( newExpr, compositeEnv, first.cost + second.cost ) );
1550                        }
1551                }
1552        }
1553
1554        void AlternativeFinder::Finder::postvisit( ConditionalExpr *conditionalExpr ) {
1555                // find alternatives for condition
1556                AlternativeFinder firstFinder( indexer, env );
1557                firstFinder.findWithAdjustment( conditionalExpr->arg1 );
1558                if ( firstFinder.alternatives.empty() ) return;
1559                // find alternatives for true expression
1560                AlternativeFinder secondFinder( indexer, env );
1561                secondFinder.findWithAdjustment( conditionalExpr->arg2 );
1562                if ( secondFinder.alternatives.empty() ) return;
1563                // find alterantives for false expression
1564                AlternativeFinder thirdFinder( indexer, env );
1565                thirdFinder.findWithAdjustment( conditionalExpr->arg3 );
1566                if ( thirdFinder.alternatives.empty() ) return;
1567                for ( const Alternative & first : firstFinder.alternatives ) {
1568                        for ( const Alternative & second : secondFinder.alternatives ) {
1569                                for ( const Alternative & third : thirdFinder.alternatives ) {
1570                                        TypeEnvironment compositeEnv;
1571                                        compositeEnv.simpleCombine( first.env );
1572                                        compositeEnv.simpleCombine( second.env );
1573                                        compositeEnv.simpleCombine( third.env );
1574
1575                                        // unify true and false types, then infer parameters to produce new alternatives
1576                                        OpenVarSet openVars;
1577                                        AssertionSet needAssertions, haveAssertions;
1578                                        Alternative newAlt( 0, compositeEnv, first.cost + second.cost + third.cost );
1579                                        Type* commonType = nullptr;
1580                                        if ( unify( second.expr->result, third.expr->result, newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1581                                                ConditionalExpr *newExpr = new ConditionalExpr( first.expr->clone(), second.expr->clone(), third.expr->clone() );
1582                                                newExpr->result = commonType ? commonType : second.expr->result->clone();
1583                                                // convert both options to the conditional result type
1584                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env );
1585                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
1586                                                newAlt.expr = newExpr;
1587                                                inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1588                                        } // if
1589                                } // for
1590                        } // for
1591                } // for
1592        }
1593
1594        void AlternativeFinder::Finder::postvisit( CommaExpr *commaExpr ) {
1595                TypeEnvironment newEnv( env );
1596                Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1597                AlternativeFinder secondFinder( indexer, newEnv );
1598                secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1599                for ( const Alternative & alt : secondFinder.alternatives ) {
1600                        alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt.expr->clone() ), alt.env, alt.cost ) );
1601                } // for
1602                delete newFirstArg;
1603        }
1604
1605        void AlternativeFinder::Finder::postvisit( RangeExpr * rangeExpr ) {
1606                // resolve low and high, accept alternatives whose low and high types unify
1607                AlternativeFinder firstFinder( indexer, env );
1608                firstFinder.findWithAdjustment( rangeExpr->low );
1609                if ( firstFinder.alternatives.empty() ) return;
1610                AlternativeFinder secondFinder( indexer, env );
1611                secondFinder.findWithAdjustment( rangeExpr->high );
1612                if ( secondFinder.alternatives.empty() ) return;
1613                for ( const Alternative & first : firstFinder.alternatives ) {
1614                        for ( const Alternative & second : secondFinder.alternatives ) {
1615                                TypeEnvironment compositeEnv;
1616                                compositeEnv.simpleCombine( first.env );
1617                                compositeEnv.simpleCombine( second.env );
1618                                OpenVarSet openVars;
1619                                AssertionSet needAssertions, haveAssertions;
1620                                Alternative newAlt( 0, compositeEnv, first.cost + second.cost );
1621                                Type* commonType = nullptr;
1622                                if ( unify( first.expr->result, second.expr->result, newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1623                                        RangeExpr * newExpr = new RangeExpr( first.expr->clone(), second.expr->clone() );
1624                                        newExpr->result = commonType ? commonType : first.expr->result->clone();
1625                                        newAlt.expr = newExpr;
1626                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1627                                } // if
1628                        } // for
1629                } // for
1630        }
1631
1632        void AlternativeFinder::Finder::postvisit( UntypedTupleExpr *tupleExpr ) {
1633                std::vector< AlternativeFinder > subExprAlternatives;
1634                altFinder.findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(),
1635                        back_inserter( subExprAlternatives ) );
1636                std::vector< AltList > possibilities;
1637                combos( subExprAlternatives.begin(), subExprAlternatives.end(),
1638                        back_inserter( possibilities ) );
1639                for ( const AltList& alts : possibilities ) {
1640                        std::list< Expression * > exprs;
1641                        makeExprList( alts, exprs );
1642
1643                        TypeEnvironment compositeEnv;
1644                        simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
1645                        alternatives.push_back(
1646                                Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } );
1647                } // for
1648        }
1649
1650        void AlternativeFinder::Finder::postvisit( TupleExpr *tupleExpr ) {
1651                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1652        }
1653
1654        void AlternativeFinder::Finder::postvisit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1655                alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
1656        }
1657
1658        void AlternativeFinder::Finder::postvisit( ConstructorExpr * ctorExpr ) {
1659                AlternativeFinder finder( indexer, env );
1660                // don't prune here, since it's guaranteed all alternatives will have the same type
1661                // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1662                finder.findWithoutPrune( ctorExpr->get_callExpr() );
1663                for ( Alternative & alt : finder.alternatives ) {
1664                        alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
1665                }
1666        }
1667
1668        void AlternativeFinder::Finder::postvisit( TupleIndexExpr *tupleExpr ) {
1669                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1670        }
1671
1672        void AlternativeFinder::Finder::postvisit( TupleAssignExpr *tupleAssignExpr ) {
1673                alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
1674        }
1675
1676        void AlternativeFinder::Finder::postvisit( UniqueExpr *unqExpr ) {
1677                AlternativeFinder finder( indexer, env );
1678                finder.findWithAdjustment( unqExpr->get_expr() );
1679                for ( Alternative & alt : finder.alternatives ) {
1680                        // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
1681                        UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
1682                        alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
1683                }
1684        }
1685
1686        void AlternativeFinder::Finder::postvisit( StmtExpr *stmtExpr ) {
1687                StmtExpr * newStmtExpr = stmtExpr->clone();
1688                ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1689                // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1690                alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
1691        }
1692
1693        void AlternativeFinder::Finder::postvisit( UntypedInitExpr *initExpr ) {
1694                // handle each option like a cast
1695                AltList candidates;
1696                PRINT(
1697                        std::cerr << "untyped init expr: " << initExpr << std::endl;
1698                )
1699                // O(N^2) checks of d-types with e-types
1700                for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
1701                        Type * toType = resolveTypeof( initAlt.type->clone(), indexer );
1702                        SymTab::validateType( toType, &indexer );
1703                        adjustExprType( toType, env, indexer );
1704                        // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
1705                        // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
1706                        // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
1707                        AlternativeFinder finder( indexer, env );
1708                        finder.targetType = toType;
1709                        finder.findWithAdjustment( initExpr->get_expr() );
1710                        for ( Alternative & alt : finder.get_alternatives() ) {
1711                                TypeEnvironment newEnv( alt.env );
1712                                AssertionSet needAssertions, haveAssertions;
1713                                OpenVarSet openVars;  // find things in env that don't have a "representative type" and claim those are open vars?
1714                                PRINT(
1715                                        std::cerr << "  @ " << toType << " " << initAlt.designation << std::endl;
1716                                 )
1717                                // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1718                                // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1719                                // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1720                                // to.
1721                                int discardedValues = alt.expr->get_result()->size() - toType->size();
1722                                if ( discardedValues < 0 ) continue;
1723                                // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1724                                // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1725                                // unification run for side-effects
1726                                unify( toType, alt.expr->get_result(), newEnv, needAssertions, haveAssertions, openVars, indexer ); // xxx - do some inspecting on this line... why isn't result bound to initAlt.type??
1727
1728                                Cost thisCost = castCost( alt.expr->get_result(), toType, indexer, newEnv );
1729                                if ( thisCost != Cost::infinity ) {
1730                                        // count one safe conversion for each value that is thrown away
1731                                        thisCost.incSafe( discardedValues );
1732                                        Alternative newAlt( new InitExpr( restructureCast( alt.expr->clone(), toType ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost );
1733                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
1734                                }
1735                        }
1736                }
1737
1738                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1739                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1740                // selects first based on argument cost, then on conversion cost.
1741                AltList minArgCost;
1742                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1743                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1744        }
1745
1746        void AlternativeFinder::Finder::postvisit( InitExpr * ) {
1747                assertf( false, "AlternativeFinder should never see a resolved InitExpr." );
1748        }
1749
1750        void AlternativeFinder::Finder::postvisit( DeletedExpr * ) {
1751                assertf( false, "AlternativeFinder should never see a DeletedExpr." );
1752        }
1753} // namespace ResolvExpr
1754
1755// Local Variables: //
1756// tab-width: 4 //
1757// mode: c++ //
1758// compile-command: "make install" //
1759// End: //
Note: See TracBrowser for help on using the repository browser.