source: src/ResolvExpr/AlternativeFinder.cc @ 09a1ae6

new-envwith_gc
Last change on this file since 09a1ae6 was 09a1ae6, checked in by Aaron Moss <a3moss@…>, 5 years ago

Fix some missing static roots -- GC'd CFA-CC now builds prelude

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