source: src/ResolvExpr/AlternativeFinder.cc @ 863c413

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumwith_gc
Last change on this file since 863c413 was 5de1e2c, checked in by Rob Schluntz <rschlunt@…>, 6 years ago

Fix memory error from caused by vector::push_back [fixes #90]

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