source: src/ResolvExpr/AlternativeFinder.cc @ 6fa409e

new-env
Last change on this file since 6fa409e was 6fa409e, checked in by Aaron Moss <a3moss@…>, 3 years ago

Fixed bug in breadth-first order, build exceeds local memory, can't test

  • Property mode set to 100644
File size: 88.7 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 : Aaron B. Moss
12// Last Modified On : Mon Jun 11 16:40:00 2018
13// Update Count     : 34
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 <limits>                  // for numeric_limits<int>::max()
22#include <list>                    // for _List_iterator, list, _List_const_...
23#include <map>                     // for _Rb_tree_iterator, map, _Rb_tree_c...
24#include <memory>                  // for allocator_traits<>::value_type
25#include <tuple>                   // for tuple
26#include <utility>                 // for pair
27#include <vector>                  // for vector
28
29#include "Alternative.h"           // for AltList, Alternative
30#include "AlternativeFinder.h"
31#include "Common/SemanticError.h"  // for SemanticError
32#include "Common/utility.h"        // for deleteAll, printAll, CodeLocation
33#include "Cost.h"                  // for Cost, Cost::zero, operator<<, Cost...
34#include "ExplodedActual.h"        // for ExplodedActual
35#include "InitTweak/InitTweak.h"   // for getFunctionName
36#include "RenameVars.h"            // for RenameVars, global_renamer
37#include "ResolveTypeof.h"         // for resolveTypeof
38#include "Resolver.h"              // for resolveStmtExpr
39#include "Common/FilterCombos.h"   // for filterCombos
40#include "Common/GC.h"             // for new_static_root
41#include "SymTab/Indexer.h"        // for Indexer
42#include "SymTab/Mangler.h"        // for Mangler
43#include "SymTab/Validate.h"       // for validateType
44#include "SynTree/Constant.h"      // for Constant
45#include "SynTree/Declaration.h"   // for DeclarationWithType, TypeDecl, Dec...
46#include "SynTree/Expression.h"    // for Expression, CastExpr, NameExpr
47#include "SynTree/Initializer.h"   // for SingleInit, operator<<, Designation
48#include "SynTree/SynTree.h"       // for UniqueId
49#include "SynTree/Type.h"          // for Type, FunctionType, PointerType
50#include "Tuples/Explode.h"        // for explode
51#include "Tuples/Tuples.h"         // for isTtype, handleTupleAssignment
52#include "Unify.h"                 // for unify
53#include "typeops.h"               // for adjustExprType, polyCost, castCost
54
55extern bool resolvep;
56#define PRINT( text ) if ( resolvep ) { text }
57//#define DEBUG_COST
58
59using std::move;
60
61/// copies any copyable type
62template<typename T>
63T copy(const T& x) { return x; }
64
65namespace ResolvExpr {
66        struct AlternativeFinder::Finder : public WithShortCircuiting {
67                Finder( AlternativeFinder & altFinder ) : altFinder( altFinder ), indexer( altFinder.indexer ), alternatives( altFinder.alternatives ), env( altFinder.env ), targetType( altFinder.targetType )  {}
68
69                void previsit( BaseSyntaxNode * ) { visit_children = false; }
70
71                void postvisit( ApplicationExpr * applicationExpr );
72                void postvisit( UntypedExpr * untypedExpr );
73                void postvisit( AddressExpr * addressExpr );
74                void postvisit( LabelAddressExpr * labelExpr );
75                void postvisit( CastExpr * castExpr );
76                void postvisit( VirtualCastExpr * castExpr );
77                void postvisit( UntypedMemberExpr * memberExpr );
78                void postvisit( MemberExpr * memberExpr );
79                void postvisit( NameExpr * variableExpr );
80                void postvisit( VariableExpr * variableExpr );
81                void postvisit( ConstantExpr * constantExpr );
82                void postvisit( SizeofExpr * sizeofExpr );
83                void postvisit( AlignofExpr * alignofExpr );
84                void postvisit( UntypedOffsetofExpr * offsetofExpr );
85                void postvisit( OffsetofExpr * offsetofExpr );
86                void postvisit( OffsetPackExpr * offsetPackExpr );
87                void postvisit( AttrExpr * attrExpr );
88                void postvisit( LogicalExpr * logicalExpr );
89                void postvisit( ConditionalExpr * conditionalExpr );
90                void postvisit( CommaExpr * commaExpr );
91                void postvisit( ImplicitCopyCtorExpr  * impCpCtorExpr );
92                void postvisit( ConstructorExpr  * ctorExpr );
93                void postvisit( RangeExpr  * rangeExpr );
94                void postvisit( UntypedTupleExpr * tupleExpr );
95                void postvisit( TupleExpr * tupleExpr );
96                void postvisit( TupleIndexExpr * tupleExpr );
97                void postvisit( TupleAssignExpr * tupleExpr );
98                void postvisit( UniqueExpr * unqExpr );
99                void postvisit( StmtExpr * stmtExpr );
100                void postvisit( UntypedInitExpr * initExpr );
101                void postvisit( InitExpr * initExpr );
102                void postvisit( DeletedExpr * delExpr );
103                void postvisit( GenericExpr * genExpr );
104
105                /// Adds alternatives for anonymous members
106                void addAnonConversions( const Alternative & alt );
107                /// Adds alternatives for member expressions, given the aggregate, conversion cost for that aggregate, and name of the member
108                template< typename StructOrUnionType > void addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, const std::string & name );
109                /// Adds alternatives for member expressions where the left side has tuple type
110                void addTupleMembers( TupleType * tupleType, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member );
111                /// Adds alternatives for offsetof expressions, given the base type and name of the member
112                template< typename StructOrUnionType > void addOffsetof( StructOrUnionType *aggInst, const std::string &name );
113                /// Takes a final result and checks if its assertions can be satisfied
114                template<typename OutputIterator>
115                void validateFunctionAlternative( const Alternative &func, ArgPack& result, const std::vector<ArgPack>& results, OutputIterator out );
116                /// Finds matching alternatives for a function, given a set of arguments
117                template<typename OutputIterator>
118                void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs& args, OutputIterator out );
119                /// Checks if assertion parameters match for a new alternative
120                template< typename OutputIterator >
121                void inferParameters( const AssertionSet &need, AssertionSet &have, Alternative &&newAlt, OpenVarSet &openVars, OutputIterator out );
122        private:
123                AlternativeFinder & altFinder;
124                const SymTab::Indexer &indexer;
125                AltList & alternatives;
126                const TypeEnvironment &env;
127                Type *& targetType;
128        };
129
130        Cost sumCost( const AltList &in ) {
131                Cost total = Cost::zero;
132                for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
133                        total += i->cost;
134                }
135                return total;
136        }
137
138        void printAlts( const AltList &list, std::ostream &os, unsigned int indentAmt ) {
139                Indenter indent = { Indenter::tabsize, indentAmt };
140                for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) {
141                        i->print( os, indent );
142                        os << std::endl;
143                }
144        }
145
146        namespace {
147                void makeExprList( const AltList &in, std::list< Expression* > &out ) {
148                        for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
149                                out.push_back( i->expr->clone() );
150                        }
151                }
152
153                struct PruneStruct {
154                        bool isAmbiguous;
155                        AltList::iterator candidate;
156                        PruneStruct() {}
157                        PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {}
158                };
159
160                /// Prunes a list of alternatives down to those that have the minimum conversion cost for a given return type; skips ambiguous interpretations
161                template< typename InputIterator, typename OutputIterator >
162                void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out ) {
163                        // select the alternatives that have the minimum conversion cost for a particular set of result types
164                        std::map< std::string, PruneStruct > selected;
165                        for ( AltList::iterator candidate = begin; candidate != end; ++candidate ) {
166                                PruneStruct current( candidate );
167                                std::string mangleName;
168                                {
169                                        Type * newType = candidate->expr->get_result()->clone();
170                                        candidate->env.apply( newType );
171                                        mangleName = SymTab::Mangler::mangle( newType );
172                                }
173                                std::map< std::string, PruneStruct >::iterator mapPlace = selected.find( mangleName );
174                                if ( mapPlace != selected.end() ) {
175                                        if ( candidate->cost < mapPlace->second.candidate->cost ) {
176                                                PRINT(
177                                                        std::cerr << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl;
178                                                )
179                                                selected[ mangleName ] = current;
180                                        } else if ( candidate->cost == mapPlace->second.candidate->cost ) {
181                                                // if one of the candidates contains a deleted identifier, can pick the other, since
182                                                // deleted expressions should not be ambiguous if there is another option that is at least as good
183                                                if ( findDeletedExpr( candidate->expr ) ) {
184                                                        // do nothing
185                                                        PRINT( std::cerr << "candidate is deleted" << std::endl; )
186                                                } else if ( findDeletedExpr( mapPlace->second.candidate->expr ) ) {
187                                                        PRINT( std::cerr << "current is deleted" << std::endl; )
188                                                        selected[ mangleName ] = current;
189                                                } else {
190                                                        PRINT(
191                                                                std::cerr << "marking ambiguous" << std::endl;
192                                                        )
193                                                        mapPlace->second.isAmbiguous = true;
194                                                }
195                                        } else {
196                                                PRINT(
197                                                        std::cerr << "cost " << candidate->cost << " loses to " << mapPlace->second.candidate->cost << std::endl;
198                                                )
199                                        }
200                                } else {
201                                        selected[ mangleName ] = current;
202                                }
203                        }
204
205                        // accept the alternatives that were unambiguous
206                        for ( std::map< std::string, PruneStruct >::iterator target = selected.begin(); target != selected.end(); ++target ) {
207                                if ( ! target->second.isAmbiguous ) {
208                                        Alternative &alt = *target->second.candidate;
209                                        alt.env.applyFree( alt.expr->get_result() );
210                                        *out++ = alt;
211                                }
212                        }
213                }
214
215                void renameTypes( Expression *expr ) {
216                        renameTyVars( expr->result );
217                }
218        } // namespace
219
220        void referenceToRvalueConversion( Expression *& expr, Cost & cost ) {
221                if ( dynamic_cast< ReferenceType * >( expr->get_result() ) ) {
222                        // cast away reference from expr
223                        expr = new CastExpr( expr, expr->get_result()->stripReferences()->clone() );
224                        cost.incReference();
225                }
226        }
227
228        template< typename InputIterator, typename OutputIterator >
229        void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) {
230                while ( begin != end ) {
231                        AlternativeFinder finder( indexer, env );
232                        finder.findWithAdjustment( *begin );
233                        // XXX  either this
234                        //Designators::fixDesignations( finder, (*begin++)->get_argName() );
235                        // or XXX this
236                        begin++;
237                        PRINT(
238                                std::cerr << "findSubExprs" << std::endl;
239                                printAlts( finder.alternatives, std::cerr );
240                        )
241                        *out++ = finder;
242                }
243        }
244
245        AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env )
246                : indexer( indexer ), env( env ) {
247        }
248
249        void AlternativeFinder::find( Expression *expr, ResolvMode mode ) {
250                PassVisitor<Finder> finder( *this );
251                expr->accept( finder );
252                if ( mode.failFast && alternatives.empty() ) {
253                        PRINT(
254                                std::cerr << "No reasonable alternatives for expression " << expr << std::endl;
255                        )
256                        SemanticError( expr, "No reasonable alternatives for expression " );
257                }
258                if ( mode.prune ) {
259                        auto oldsize = alternatives.size();
260                        PRINT(
261                                std::cerr << "alternatives before prune:" << std::endl;
262                                printAlts( alternatives, std::cerr );
263                        )
264                        AltList pruned;
265                        pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned ) );
266                        if ( mode.failFast && pruned.empty() ) {
267                                std::ostringstream stream;
268                                AltList winners;
269                                findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) );
270                                stream << "Cannot choose between " << winners.size() << " alternatives for expression\n";
271                                expr->print( stream );
272                                stream << " Alternatives are:\n";
273                                printAlts( winners, stream, 1 );
274                                SemanticError( expr->location, stream.str() );
275                        }
276                        alternatives = move(pruned);
277                        PRINT(
278                                std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
279                        )
280                        PRINT(
281                                std::cerr << "there are " << alternatives.size() << " alternatives after elimination" << std::endl;
282                        )
283                }
284                // adjust types after pruning so that types substituted by pruneAlternatives are correctly adjusted
285                if ( mode.adjust ) {
286                        for ( Alternative& i : alternatives ) {
287                                adjustExprType( i.expr->result, i.env, indexer );
288                        }
289                }
290
291                // Central location to handle gcc extension keyword, etc. for all expression types.
292                for ( Alternative &iter: alternatives ) {
293                        iter.expr->set_extension( expr->get_extension() );
294                        iter.expr->location = expr->location;
295                } // for
296        }
297
298        void AlternativeFinder::findWithAdjustment( Expression *expr ) {
299                find( expr, ResolvMode::withAdjustment() );
300        }
301
302        void AlternativeFinder::findWithoutPrune( Expression * expr ) {
303                find( expr, ResolvMode::withoutPrune() );
304        }
305
306        void AlternativeFinder::maybeFind( Expression * expr ) {
307                find( expr, ResolvMode::withoutFailFast() );
308        }
309
310        void AlternativeFinder::Finder::addAnonConversions( const Alternative & alt ) {
311                // adds anonymous member interpretations whenever an aggregate value type is seen.
312                // 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
313                Expression* aggrExpr = alt.expr->clone();
314                alt.env.apply( aggrExpr->result );
315                Type * aggrType = aggrExpr->result;
316                if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
317                        aggrType = aggrType->stripReferences();
318                        aggrExpr = new CastExpr{ aggrExpr, aggrType->clone() };
319                }
320
321                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->result ) ) {
322                        addAggMembers( structInst, aggrExpr, alt.cost+Cost::safe, alt.env, "" );
323                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->result ) ) {
324                        addAggMembers( unionInst, aggrExpr, alt.cost+Cost::safe, alt.env, "" );
325                } // if
326        }
327
328        template< typename StructOrUnionType >
329        void AlternativeFinder::Finder::addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, const std::string & name ) {
330                std::list< Declaration* > members;
331                aggInst->lookup( name, members );
332
333                for ( Declaration * decl : members ) {
334                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( decl ) ) {
335                                // addAnonAlternatives uses vector::push_back, which invalidates references to existing elements, so
336                                // can't construct in place and use vector::back
337                                Alternative newAlt( new MemberExpr( dwt, expr->clone() ), env, newCost );
338                                renameTypes( newAlt.expr );
339                                addAnonConversions( newAlt ); // add anonymous member interpretations whenever an aggregate value type is seen as a member expression.
340                                alternatives.push_back( std::move(newAlt) );
341                        } else {
342                                assert( false );
343                        }
344                }
345        }
346
347        void AlternativeFinder::Finder::addTupleMembers( TupleType * tupleType, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
348                if ( ConstantExpr * constantExpr = dynamic_cast< ConstantExpr * >( member ) ) {
349                        // get the value of the constant expression as an int, must be between 0 and the length of the tuple type to have meaning
350                        auto val = constantExpr->intValue();
351                        std::string tmp;
352                        if ( val >= 0 && (unsigned long long)val < tupleType->size() ) {
353                                alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
354                        } // if
355                } // if
356        }
357
358        void AlternativeFinder::Finder::postvisit( ApplicationExpr *applicationExpr ) {
359                alternatives.push_back( Alternative( applicationExpr, env, Cost::zero ) );
360        }
361
362        Cost computeConversionCost( Type * actualType, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
363                PRINT(
364                        std::cerr << std::endl << "converting ";
365                        actualType->print( std::cerr, 8 );
366                        std::cerr << std::endl << " to ";
367                        formalType->print( std::cerr, 8 );
368                        std::cerr << std::endl << "environment is: ";
369                        env.print( std::cerr, 8 );
370                        std::cerr << std::endl;
371                )
372                Cost convCost = conversionCost( actualType, formalType, indexer, env );
373                PRINT(
374                        std::cerr << std::endl << "cost is " << convCost << std::endl;
375                )
376                if ( convCost == Cost::infinity ) {
377                        return convCost;
378                }
379                convCost.incPoly( polyCost( formalType, env, indexer ) + polyCost( actualType, env, indexer ) );
380                PRINT(
381                        std::cerr << "cost with polycost is " << convCost << std::endl;
382                )
383                return convCost;
384        }
385
386        Cost computeExpressionConversionCost( Expression *& actualExpr, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
387                Cost convCost = computeConversionCost( actualExpr->result, formalType, indexer, env );
388
389                // if there is a non-zero conversion cost, ignoring poly cost, then the expression requires conversion.
390                // ignore poly cost for now, since this requires resolution of the cast to infer parameters and this
391                // does not currently work for the reason stated below.
392                Cost tmpCost = convCost;
393                tmpCost.incPoly( -tmpCost.get_polyCost() );
394                if ( tmpCost != Cost::zero ) {
395                        Type *newType = formalType->clone();
396                        env.apply( newType );
397                        actualExpr = new CastExpr( actualExpr, newType );
398                        // 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
399                        // inconsistent, once this is fixed it should be possible to resolve the cast.
400                        // 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.
401
402                        // AlternativeFinder finder( indexer, env );
403                        // finder.findWithAdjustment( actualExpr );
404                        // assertf( finder.get_alternatives().size() > 0, "Somehow castable expression failed to find alternatives." );
405                        // assertf( finder.get_alternatives().size() == 1, "Somehow got multiple alternatives for known cast expression." );
406                        // Alternative & alt = finder.get_alternatives().front();
407                        // delete actualExpr;
408                        // actualExpr = alt.expr->clone();
409                }
410                return convCost;
411        }
412
413        Cost computeApplicationConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) {
414                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( alt.expr );
415                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
416                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
417
418                Cost convCost = Cost::zero;
419                std::list< DeclarationWithType* >& formals = function->get_parameters();
420                std::list< DeclarationWithType* >::iterator formal = formals.begin();
421                std::list< Expression* >& actuals = appExpr->get_args();
422
423                for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
424                        Type * actualType = (*actualExpr)->get_result();
425                        PRINT(
426                                std::cerr << "actual expression:" << std::endl;
427                                (*actualExpr)->print( std::cerr, 8 );
428                                std::cerr << "--- results are" << std::endl;
429                                actualType->print( std::cerr, 8 );
430                        )
431                        if ( formal == formals.end() ) {
432                                if ( function->get_isVarArgs() ) {
433                                        convCost.incUnsafe();
434                                        PRINT( std::cerr << "end of formals with varargs function: inc unsafe: " << convCost << std::endl; ; )
435                                        // convert reference-typed expressions to value-typed expressions
436                                        referenceToRvalueConversion( *actualExpr, convCost );
437                                        continue;
438                                } else {
439                                        return Cost::infinity;
440                                }
441                        }
442                        if ( DefaultArgExpr * def = dynamic_cast< DefaultArgExpr * >( *actualExpr ) ) {
443                                // default arguments should be free - don't include conversion cost.
444                                // Unwrap them here because they are not relevant to the rest of the system.
445                                *actualExpr = def->expr;
446                                ++formal;
447                                continue;
448                        }
449                        Type * formalType = (*formal)->get_type();
450                        convCost += computeExpressionConversionCost( *actualExpr, formalType, indexer, alt.env );
451                        ++formal; // can't be in for-loop update because of the continue
452                }
453                if ( formal != formals.end() ) {
454                        return Cost::infinity;
455                }
456
457                #if 1 // cost of assertions accounted for in function creation
458                for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
459                        convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
460                }
461                #endif
462
463                return convCost;
464        }
465
466        /// Adds type variables to the open variable set and marks their assertions
467        void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) {
468                for ( Type::ForallList::const_iterator tyvar = type->forall.begin(); tyvar != type->forall.end(); ++tyvar ) {
469                        unifiableVars[ (*tyvar)->get_name() ] = TypeDecl::Data{ *tyvar };
470                        for ( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->assertions.begin(); assert != (*tyvar)->assertions.end(); ++assert ) {
471                                needAssertions[ *assert ].isUsed = true;
472                        }
473///     needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() );
474                }
475        }
476
477        static const int recursionLimit = /*10*/ 4;  ///< Limit to depth of recursion satisfaction
478
479        void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
480                for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
481                        if ( i->second.isUsed ) {
482                                indexer.addId( i->first );
483                        }
484                }
485        }
486
487        template< typename ForwardIterator, typename OutputIterator >
488        void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, int level, const SymTab::Indexer &indexer, OutputIterator out ) {
489                if ( begin == end ) {
490                        if ( newNeed.empty() ) {
491                                PRINT(
492                                        std::cerr << "all assertions satisfied, output alternative: ";
493                                        newAlt.print( std::cerr );
494                                        std::cerr << std::endl;
495                                );
496                                *out++ = newAlt;
497                                return;
498                        } else if ( level >= recursionLimit ) {
499                                SemanticError( newAlt.expr->location, "Too many recursive assertions" );
500                        } else {
501                                AssertionSet newerNeed;
502                                PRINT(
503                                        std::cerr << "recursing with new set:" << std::endl;
504                                        printAssertionSet( newNeed, std::cerr, 8 );
505                                )
506                                inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, level+1, indexer, out );
507                                return;
508                        }
509                }
510
511                ForwardIterator cur = begin++;
512                if ( ! cur->second.isUsed ) {
513                        inferRecursive( begin, end, newAlt, openVars, decls, newNeed, level, indexer, out );
514                        return; // xxx - should this continue? previously this wasn't here, and it looks like it should be
515                }
516                DeclarationWithType *curDecl = cur->first;
517
518                PRINT(
519                        std::cerr << "inferRecursive: assertion is ";
520                        curDecl->print( std::cerr );
521                        std::cerr << std::endl;
522                )
523                std::list< SymTab::Indexer::IdData > candidates;
524                decls.lookupId( curDecl->get_name(), candidates );
525///   if ( candidates.empty() ) { std::cerr << "no candidates!" << std::endl; }
526                for ( const auto & data : candidates ) {
527                        DeclarationWithType * candidate = data.id;
528                        PRINT(
529                                std::cerr << "inferRecursive: candidate is ";
530                                candidate->print( std::cerr );
531                                std::cerr << std::endl;
532                        )
533
534                        AssertionSet newHave, newerNeed( newNeed );
535                        TypeEnvironment newEnv( newAlt.env );
536                        OpenVarSet newOpenVars( openVars );
537                        Type *adjType = candidate->get_type()->clone();
538                        adjustExprType( adjType, newEnv, indexer );
539                        renameTyVars( adjType );
540                        PRINT(
541                                std::cerr << "unifying ";
542                                curDecl->get_type()->print( std::cerr );
543                                std::cerr << " with ";
544                                adjType->print( std::cerr );
545                                std::cerr << std::endl;
546                        )
547                        if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) {
548                                PRINT(
549                                        std::cerr << "success!" << std::endl;
550                                )
551                                SymTab::Indexer newDecls( decls );
552                                addToIndexer( newHave, newDecls );
553                                Alternative newerAlt( newAlt );
554                                newerAlt.env = newEnv;
555                                assertf( candidate->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );
556
557                                // everything with an empty idChain was pulled in by the current assertion.
558                                // add current assertion's idChain + current assertion's ID so that the correct inferParameters can be found.
559                                for ( auto & a : newerNeed ) {
560                                        if ( a.second.idChain.empty() ) {
561                                                a.second.idChain = cur->second.idChain;
562                                                a.second.idChain.push_back( curDecl->get_uniqueId() );
563                                        }
564                                }
565
566                                Expression *varExpr = data.combine( newerAlt.cvtCost );
567                                varExpr->set_result( adjType->clone() );
568                                PRINT(
569                                        std::cerr << "satisfying assertion " << curDecl->get_uniqueId() << " ";
570                                        curDecl->print( std::cerr );
571                                        std::cerr << " with declaration " << candidate->get_uniqueId() << " ";
572                                        candidate->print( std::cerr );
573                                        std::cerr << std::endl;
574                                )
575                                // 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).
576                                InferredParams * inferParameters = &newerAlt.expr->get_inferParams();
577                                for ( UniqueId id : cur->second.idChain ) {
578                                        inferParameters = (*inferParameters)[ id ].inferParams.get();
579                                }
580                               
581                                (*inferParameters)[ curDecl->get_uniqueId() ] = ParamEntry( candidate->get_uniqueId(), adjType, curDecl->get_type(), varExpr );
582                                inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, level, indexer, out );
583                        }
584                }
585        }
586
587#if 1
588        namespace {
589                /// Information required to defer resolution of an expression
590                struct AssertionPack {
591                        SymTab::Indexer::IdData cdata;  ///< Satisfying declaration
592                        Type* adjType;                  ///< Satisfying type
593                        TypeEnvironment env;            ///< Post-unification environment
594                        AssertionSet have;              ///< Post-unification have-set
595                        AssertionSet need;              ///< Post-unification need-set
596                        OpenVarSet openVars;            ///< Post-unification open-var set
597
598                        AssertionPack( const SymTab::Indexer::IdData& cdata, Type* adjType, 
599                                        TypeEnvironment&& env, AssertionSet&& have, AssertionSet&& need, 
600                                        OpenVarSet&& openVars ) 
601                                : cdata(cdata), adjType(adjType), env(std::move(env)), have(std::move(have)), 
602                                  need(std::move(need)), openVars(std::move(openVars)) {}
603                       
604                        class iterator {
605                        friend AssertionPack;
606                        public:
607                                const AssertionPack& pack;
608                        private:
609                                AssertionSet::iterator it;
610
611                                iterator(const AssertionPack& p, AssertionSet::iterator i) : pack{p}, it{i} {}
612                        public:
613                                iterator& operator++ () { ++it; return *this; }
614                                iterator operator++ (int) { iterator tmp = *this; ++it; return tmp; }
615                                AssertionSet::value_type& operator* () { return *it; }
616                                AssertionSet::value_type* operator-> () { return it.operator->(); }
617                                bool operator== (const iterator& o) const { return this == &o && it == o.it; }
618                                bool operator!= (const iterator& o) const { return !(*this == o); }
619                        };
620
621                        iterator begin() { return { *this, need.begin() }; }
622                        iterator end() { return { *this, need.end() }; }
623                };
624
625                /// List of deferred assertion resolutions for the same type
626                using DeferList = std::vector<AssertionPack>;
627
628                /// Single deferred item
629                struct DeferElement {
630                        const DeclarationWithType* curDecl;
631                        const AssertionSetValue& assnInfo;
632                        const AssertionPack& match;
633                };
634
635                /// Wrapper for the DeferList of a single assertion resolution
636                struct DeferItem {
637                        DeclarationWithType* curDecl;
638                        AssertionSetValue assnInfo;
639                        DeferList matches;
640
641                        DeferItem(DeclarationWithType* cd, const AssertionSetValue& ai, DeferList&& m )
642                                : curDecl{cd}, assnInfo{ai}, matches(std::move(m)) {}
643
644                        bool empty() const { return matches.empty(); }
645
646                        DeferList::size_type size() const { return matches.size(); }
647
648                        DeferElement operator[] ( unsigned i ) const {
649                                return { curDecl, assnInfo, matches[i] };
650                        }
651                };
652
653                /// Flag for state iteration
654                enum CopyFlag { IterateState };
655
656                /// Intermediate state for assertion resolution
657                struct AssertionResnState {
658                        Alternative alt;                  ///< Alternative being built from
659                        AssertionSet need;                ///< Assertions to find
660                        AssertionSet newNeed;             ///< New assertions found from current assertions
661                        OpenVarSet openVars;              ///< Open variables in current context
662                        std::vector<DeferItem> deferred;  ///< Possible deferred assertion resolutions
663                        SymTab::Indexer& indexer;         ///< Name lookup
664
665                        /// field-wise constructor (some fields defaulted)
666                        AssertionResnState(Alternative&& alt, const AssertionSet& need, 
667                                const OpenVarSet& openVars, SymTab::Indexer& indexer ) 
668                                : alt{std::move(alt)}, need{need}, newNeed{}, openVars{openVars}, deferred{}, 
669                                  indexer{indexer} {}
670                       
671                        /// construct iterated state object from previous state
672                        AssertionResnState(AssertionResnState&& o, CopyFlag) 
673                                : alt{std::move(o.alt)}, need{std::move(o.newNeed)}, newNeed{}, 
674                                  openVars{std::move(o.openVars)}, deferred{}, indexer{o.indexer} {}
675                       
676                        /// copy resn state updated with specified data
677                        AssertionResnState(const AssertionResnState& o, const AssertionSet& need, 
678                                const OpenVarSet& openVars, TypeEnvironment& env )
679                                : alt{o.alt}, need{}, newNeed{o.newNeed}, openVars{openVars}, deferred{},
680                                  indexer{o.indexer} {
681                                newNeed.insert( need.begin(), need.end() );
682                                alt.env = env;
683                        }
684                };
685
686                /// Binds a single assertion from a compatible AssertionPack, updating resolution state
687                /// as appropriate.
688                void bindAssertion( const DeclarationWithType* curDecl, const AssertionSetValue& assnInfo, 
689                                Alternative& alt, AssertionPack& match ) {
690
691                        DeclarationWithType* candidate = match.cdata.id;
692                        assertf( candidate->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );
693                       
694                        // everything with an empty idChain was pulled in by the current assertion.
695                        // add current assertion's idChain + current assertion's ID so that the correct
696                        // inferParameters can be found.
697                        for ( auto& a : match.need ) {
698                                if ( a.second.idChain.empty() ) {
699                                        a.second.idChain = assnInfo.idChain;
700                                        a.second.idChain.push_back( curDecl->get_uniqueId() );
701                                }
702                        }
703
704                        Expression* varExpr = match.cdata.combine( alt.cvtCost );
705                        varExpr->result = match.adjType;
706
707                        // follow the current assertion's ID chain to find the correct set of inferred
708                        // parameters to add the candidate o (i.e. the set of inferred parameters belonging
709                        // to the entity which requested the assertion parameter)
710                        InferredParams* inferParams = &alt.expr->inferParams;
711                        for ( UniqueId id : assnInfo.idChain ) {
712                                inferParams = (*inferParams)[ id ].inferParams.get();
713                        }
714
715                        (*inferParams)[ curDecl->get_uniqueId() ] = ParamEntry{
716                                candidate->get_uniqueId(), match.adjType, curDecl->get_type(), varExpr };
717                }
718
719                /// Resolves a single assertion, returning false if no satisfying assertion, binding it
720                /// if there is exactly one satisfying assertion, or adding to the defer-list if there
721                /// is more than one
722                bool resolveAssertion( DeclarationWithType* curDecl, AssertionSetValue& assnInfo, 
723                                AssertionResnState& resn ) {
724                        // skip unused assertions
725                        if ( ! assnInfo.isUsed ) return true;
726
727                        // lookup candidates for this assertion
728                        std::list< SymTab::Indexer::IdData > candidates;
729                        resn.indexer.lookupId( curDecl->name, candidates );
730
731                        // find the ones that unify with the desired type
732                        DeferList matches;
733                        for ( const auto& cdata : candidates ) {
734                                DeclarationWithType* candidate = cdata.id;
735
736                                // build independent unification context for candidate
737                                AssertionSet have, newNeed;
738                                TypeEnvironment newEnv{ resn.alt.env };
739                                OpenVarSet newOpenVars{ resn.openVars };
740                                Type* adjType = candidate->get_type()->clone();
741                                adjustExprType( adjType, newEnv, resn.indexer );
742                                renameTyVars( adjType );
743
744                                if ( unify( curDecl->get_type(), adjType, newEnv, 
745                                                newNeed, have, newOpenVars, resn.indexer ) ) {
746                                        matches.emplace_back( cdata, adjType, std::move(newEnv), std::move(have), 
747                                                std::move(newNeed), std::move(newOpenVars) );
748                                }
749                        }
750
751                        // Break if no suitable assertion
752                        if ( matches.empty() ) return false;
753
754                        // Defer if too many suitable assertions
755                        if ( matches.size() > 1 ) {
756                                resn.deferred.emplace_back( curDecl, assnInfo, std::move(matches) );
757                                return true;
758                        }
759
760                        // otherwise bind current match in ongoing scope
761                        AssertionPack& match = matches.front();
762                        addToIndexer( match.have, resn.indexer );
763                        resn.newNeed.insert( match.need.begin(), match.need.end() );
764                        resn.alt.env = std::move(match.env);
765                        resn.openVars = std::move(match.openVars);
766
767                        bindAssertion( curDecl, assnInfo, resn.alt, match );
768                        return true;
769                }
770
771                /// Combo iterator that combines interpretations into an interpretation list, merging
772                /// their environments. Rejects an appended interpretation if the environments cannot
773                /// be merged.
774                class InterpretationEnvMerger {
775                        /// Current list of merged interpretations
776                        std::vector<DeferElement> crnt;
777                        /// Stack of environments, to support backtracking
778                        std::vector<TypeEnvironment> envs;
779                        /// Open variables for environment combination
780                        std::vector<OpenVarSet> varSets;
781                        /// Indexer to use for environment merges
782                        const SymTab::Indexer& indexer;
783                public:
784                        /// The merged environment/open variables and the list of interpretations
785                        struct OutType {
786                                TypeEnvironment env;
787                                OpenVarSet openVars;
788                                std::vector<DeferElement> assns;
789
790                                OutType( const TypeEnvironment& env, const OpenVarSet& openVars, 
791                                        const std::vector<DeferElement>& assns )
792                                        : env(env), openVars(openVars), assns(assns) {}
793                        };
794
795                        InterpretationEnvMerger( const TypeEnvironment& env, const OpenVarSet& openVars, 
796                                const SymTab::Indexer& indexer ) : crnt{}, envs{}, varSets{}, indexer{indexer} {
797                                envs.push_back( env );
798                                varSets.push_back( openVars );
799                        }
800
801                        ComboResult append( DeferElement i ) {
802                                TypeEnvironment env = envs.back();
803                                OpenVarSet openVars = varSets.back();
804                                mergeOpenVars( openVars, i.match.openVars );
805
806                                if ( ! env.combine( i.match.env, openVars, indexer ) )
807                                        return ComboResult::REJECT_THIS;
808                               
809                                crnt.push_back( i );
810                                envs.push_back( env );
811                                varSets.push_back( openVars );
812                                return ComboResult::ACCEPT;
813                        }
814
815                        void backtrack() {
816                                crnt.pop_back();
817                                envs.pop_back();
818                                varSets.pop_back();
819                        }
820
821                        OutType finalize() { return { envs.back(), varSets.back(), crnt }; }
822                };
823        }
824#endif
825
826        template< typename OutputIterator >
827        void AlternativeFinder::Finder::inferParameters( const AssertionSet &need, AssertionSet &have, Alternative &&newAlt, OpenVarSet &openVars, OutputIterator out ) {
828//      PRINT(
829//          std::cerr << "inferParameters: assertions needed are" << std::endl;
830//          printAll( need, std::cerr, 8 );
831//          )
832                SymTab::Indexer decls( indexer );
833                // PRINT(
834                //      std::cerr << "============= original indexer" << std::endl;
835                //      indexer.print( std::cerr );
836                //      std::cerr << "============= new indexer" << std::endl;
837                //      decls.print( std::cerr );
838                // )
839                addToIndexer( have, decls );
840#if 1
841                using ResnList = std::vector<AssertionResnState>;
842                ResnList resns{ AssertionResnState{ std::move(newAlt), need, openVars, decls } };
843                ResnList new_resns{};
844
845                // resolve assertions in breadth-first-order up to a limited number of levels deep
846                for ( int level = 0; level < recursionLimit; ++level ) {
847                        // scan over all mutually-compatible resolutions
848                        for ( auto& resn : resns ) {
849                                // make initial pass at matching assertions
850                                for ( auto& assn : resn.need ) {
851                                        if ( ! resolveAssertion( assn.first, assn.second, resn ) ) {
852                                                // fail early if any assertion fails to resolve
853                                                goto nextResn;
854                                        }
855                                }
856
857                                if ( ! resn.deferred.empty() ) {
858                                        // resolve deferred assertions by mutual compatibility
859
860                                        std::vector<InterpretationEnvMerger::OutType> compatible = filterCombos( 
861                                                resn.deferred, 
862                                                InterpretationEnvMerger{ resn.alt.env, resn.openVars, resn.indexer } );
863                                       
864                                        for ( auto& compat : compatible ) {
865                                                AssertionResnState new_resn = resn;
866
867                                                // add compatible assertions to new resolution state
868                                                for ( DeferElement el : compat.assns ) {
869                                                        AssertionPack match = el.match;
870                                                        addToIndexer( match.have, new_resn.indexer );
871                                                        new_resn.newNeed.insert( match.need.begin(), match.need.end() );
872                                                       
873                                                        bindAssertion( el.curDecl, el.assnInfo, new_resn.alt, match );
874                                                }
875
876                                                // set mutual environment into resolution state
877                                                new_resn.alt.env = std::move(compat.env);
878                                                new_resn.openVars = std::move(compat.openVars);
879
880                                                // add successful match or push back next state
881                                                if ( new_resn.newNeed.empty() ) {
882                                                        *out++ = new_resn.alt;
883                                                } else {
884                                                        new_resns.emplace_back( std::move(new_resn), IterateState );
885                                                }
886                                        }
887                                } else {
888                                        // add successful match or push back next state
889                                        if ( resn.newNeed.empty() ) {
890                                                *out++ = resn.alt;
891                                        } else {
892                                                new_resns.emplace_back( std::move(resn), IterateState );
893                                        }
894                                }
895                        nextResn:; }
896                       
897                        // finish or reset for next round
898                        if ( new_resns.empty() ) return;
899                        resns.swap( new_resns );
900                        new_resns.clear();
901                }
902                // if reaches here, exceeded recursion limit
903                SemanticError( newAlt.expr->location, "Too many recursive assertions" );
904
905#else           
906                AssertionSet newNeed;
907                PRINT(
908                        std::cerr << "env is: " << std::endl;
909                        newAlt.env.print( std::cerr, 0 );
910                        std::cerr << std::endl;
911                )
912
913                inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, 0, indexer, out );
914//      PRINT(
915//          std::cerr << "declaration 14 is ";
916//          Declaration::declFromId
917//          *out++ = newAlt;
918//          )
919#endif
920        }
921
922        /// Gets a default value from an initializer, nullptr if not present
923        ConstantExpr* getDefaultValue( Initializer* init ) {
924                if ( SingleInit* si = dynamic_cast<SingleInit*>( init ) ) {
925                        if ( CastExpr* ce = dynamic_cast<CastExpr*>( si->value ) ) {
926                                return dynamic_cast<ConstantExpr*>( ce->arg );
927                        } else {
928                                return dynamic_cast<ConstantExpr*>( si->value );
929                        }
930                }
931                return nullptr;
932        }
933
934        /// State to iteratively build a match of parameter expressions to arguments
935        struct ArgPack {
936                std::size_t parent;                ///< Index of parent pack
937                Expression* expr;                  ///< The argument stored here
938                Cost cost;                         ///< The cost of this argument
939                TypeEnvironment env;               ///< Environment for this pack
940                AssertionSet need;                 ///< Assertions outstanding for this pack
941                AssertionSet have;                 ///< Assertions found for this pack
942                OpenVarSet openVars;               ///< Open variables for this pack
943                unsigned nextArg;                  ///< Index of next argument in arguments list
944                unsigned tupleStart;               ///< Number of tuples that start at this index
945                unsigned nextExpl;                 ///< Index of next exploded element
946                unsigned explAlt;                  ///< Index of alternative for nextExpl > 0
947
948                ArgPack()
949                        : parent(0), expr(nullptr), cost(Cost::zero), env(), need(), have(), openVars(), 
950                          nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
951
952                ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
953                                const OpenVarSet& openVars, Cost initCost = Cost::zero)
954                        : parent(0), expr(nullptr), cost(initCost), env(env), need(need), have(have),
955                          openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
956
957                ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need,
958                                AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg,
959                                unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0,
960                                unsigned explAlt = 0 )
961                        : parent(parent), expr(expr), cost(cost), env(move(env)), need(move(need)),
962                          have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart),
963                          nextExpl(nextExpl), explAlt(explAlt) {}
964
965                ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have,
966                                OpenVarSet&& openVars, unsigned nextArg, Cost added )
967                        : parent(o.parent), expr(o.expr), cost(o.cost + added), env(move(env)), 
968                          need(move(need)), have(move(have)), openVars(move(openVars)), nextArg(nextArg), 
969                          tupleStart(o.tupleStart), nextExpl(0), explAlt(0) {}
970
971                /// true iff this pack is in the middle of an exploded argument
972                bool hasExpl() const { return nextExpl > 0; }
973
974                /// Gets the list of exploded alternatives for this pack
975                const ExplodedActual& getExpl( const ExplodedArgs& args ) const {
976                        return args[nextArg-1][explAlt];
977                }
978
979                /// Ends a tuple expression, consolidating the appropriate actuals
980                void endTuple( const std::vector<ArgPack>& packs ) {
981                        // add all expressions in tuple to list, summing cost
982                        std::list<Expression*> exprs;
983                        const ArgPack* pack = this;
984                        if ( expr ) { exprs.push_front( expr ); }
985                        while ( pack->tupleStart == 0 ) {
986                                pack = &packs[pack->parent];
987                                exprs.push_front( pack->expr );
988                                cost += pack->cost;
989                        }
990                        // reset pack to appropriate tuple
991                        expr = new TupleExpr{ exprs };
992                        tupleStart = pack->tupleStart - 1;
993                        parent = pack->parent;
994                }
995        };
996
997        /// Instantiates an argument to match a formal, returns false if no results left
998        bool instantiateArgument( Type* formalType, Initializer* initializer,
999                        const ExplodedArgs& args, std::vector<ArgPack>& results, std::size_t& genStart,
1000                        const SymTab::Indexer& indexer, unsigned nTuples = 0 ) {
1001                if ( TupleType * tupleType = dynamic_cast<TupleType*>( formalType ) ) {
1002                        // formalType is a TupleType - group actuals into a TupleExpr
1003                        ++nTuples;
1004                        for ( Type* type : *tupleType ) {
1005                                // xxx - dropping initializer changes behaviour from previous, but seems correct
1006                                // ^^^ need to handle the case where a tuple has a default argument
1007                                if ( ! instantiateArgument(
1008                                                type, nullptr, args, results, genStart, indexer, nTuples ) )
1009                                        return false;
1010                                nTuples = 0;
1011                        }
1012                        // re-consititute tuples for final generation
1013                        for ( auto i = genStart; i < results.size(); ++i ) {
1014                                results[i].endTuple( results );
1015                        }
1016                        return true;
1017                } else if ( TypeInstType * ttype = Tuples::isTtype( formalType ) ) {
1018                        // formalType is a ttype, consumes all remaining arguments
1019                        // xxx - mixing default arguments with variadic??
1020
1021                        // completed tuples; will be spliced to end of results to finish
1022                        std::vector<ArgPack> finalResults{};
1023
1024                        // iterate until all results completed
1025                        std::size_t genEnd;
1026                        ++nTuples;
1027                        do {
1028                                genEnd = results.size();
1029
1030                                // add another argument to results
1031                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
1032                                        auto nextArg = results[i].nextArg;
1033
1034                                        // use next element of exploded tuple if present
1035                                        if ( results[i].hasExpl() ) {
1036                                                const ExplodedActual& expl = results[i].getExpl( args );
1037
1038                                                unsigned nextExpl = results[i].nextExpl + 1;
1039                                                if ( nextExpl == expl.exprs.size() ) {
1040                                                        nextExpl = 0;
1041                                                }
1042
1043                                                results.emplace_back(
1044                                                        i, expl.exprs[results[i].nextExpl], copy(results[i].env),
1045                                                        copy(results[i].need), copy(results[i].have),
1046                                                        copy(results[i].openVars), nextArg, nTuples, Cost::zero, nextExpl,
1047                                                        results[i].explAlt );
1048
1049                                                continue;
1050                                        }
1051
1052                                        // finish result when out of arguments
1053                                        if ( nextArg >= args.size() ) {
1054                                                ArgPack newResult{
1055                                                        results[i].env, results[i].need, results[i].have,
1056                                                        results[i].openVars };
1057                                                newResult.nextArg = nextArg;
1058                                                Type* argType;
1059
1060                                                if ( nTuples > 0 || ! results[i].expr ) {
1061                                                        // first iteration or no expression to clone,
1062                                                        // push empty tuple expression
1063                                                        newResult.parent = i;
1064                                                        std::list<Expression*> emptyList;
1065                                                        newResult.expr = new TupleExpr{ emptyList };
1066                                                        argType = newResult.expr->get_result();
1067                                                } else {
1068                                                        // clone result to collect tuple
1069                                                        newResult.parent = results[i].parent;
1070                                                        newResult.cost = results[i].cost;
1071                                                        newResult.tupleStart = results[i].tupleStart;
1072                                                        newResult.expr = results[i].expr;
1073                                                        argType = newResult.expr->get_result();
1074
1075                                                        if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
1076                                                                // the case where a ttype value is passed directly is special,
1077                                                                // e.g. for argument forwarding purposes
1078                                                                // xxx - what if passing multiple arguments, last of which is
1079                                                                //       ttype?
1080                                                                // xxx - what would happen if unify was changed so that unifying
1081                                                                //       tuple
1082                                                                // types flattened both before unifying lists? then pass in
1083                                                                // TupleType (ttype) below.
1084                                                                --newResult.tupleStart;
1085                                                        } else {
1086                                                                // collapse leftover arguments into tuple
1087                                                                newResult.endTuple( results );
1088                                                                argType = newResult.expr->get_result();
1089                                                        }
1090                                                }
1091
1092                                                // check unification for ttype before adding to final
1093                                                if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have,
1094                                                                newResult.openVars, indexer ) ) {
1095                                                        finalResults.push_back( move(newResult) );
1096                                                }
1097
1098                                                continue;
1099                                        }
1100
1101                                        // add each possible next argument
1102                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
1103                                                const ExplodedActual& expl = args[nextArg][j];
1104
1105                                                // fresh copies of parent parameters for this iteration
1106                                                TypeEnvironment env = results[i].env;
1107                                                OpenVarSet openVars = results[i].openVars;
1108
1109                                                env.addActual( expl.env, openVars );
1110
1111                                                // skip empty tuple arguments by (near-)cloning parent into next gen
1112                                                if ( expl.exprs.empty() ) {
1113                                                        results.emplace_back(
1114                                                                results[i], move(env), copy(results[i].need),
1115                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
1116
1117                                                        continue;
1118                                                }
1119
1120                                                // add new result
1121                                                results.emplace_back(
1122                                                        i, expl.exprs.front(), move(env), copy(results[i].need),
1123                                                        copy(results[i].have), move(openVars), nextArg + 1,
1124                                                        nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
1125                                        }
1126                                }
1127
1128                                // reset for next round
1129                                genStart = genEnd;
1130                                nTuples = 0;
1131                        } while ( genEnd != results.size() );
1132
1133                        // splice final results onto results
1134                        for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
1135                                results.push_back( move(finalResults[i]) );
1136                        }
1137                        return ! finalResults.empty();
1138                }
1139
1140                // iterate each current subresult
1141                std::size_t genEnd = results.size();
1142                for ( std::size_t i = genStart; i < genEnd; ++i ) {
1143                        auto nextArg = results[i].nextArg;
1144
1145                        // use remainder of exploded tuple if present
1146                        if ( results[i].hasExpl() ) {
1147                                const ExplodedActual& expl = results[i].getExpl( args );
1148                                Expression* expr = expl.exprs[results[i].nextExpl];
1149
1150                                TypeEnvironment env = results[i].env;
1151                                AssertionSet need = results[i].need, have = results[i].have;
1152                                OpenVarSet openVars = results[i].openVars;
1153
1154                                Type* actualType = expr->get_result();
1155
1156                                PRINT(
1157                                        std::cerr << "formal type is ";
1158                                        formalType->print( std::cerr );
1159                                        std::cerr << std::endl << "actual type is ";
1160                                        actualType->print( std::cerr );
1161                                        std::cerr << std::endl;
1162                                )
1163
1164                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
1165                                        unsigned nextExpl = results[i].nextExpl + 1;
1166                                        if ( nextExpl == expl.exprs.size() ) {
1167                                                nextExpl = 0;
1168                                        }
1169
1170                                        results.emplace_back(
1171                                                i, expr, move(env), move(need), move(have), move(openVars), nextArg,
1172                                                nTuples, Cost::zero, nextExpl, results[i].explAlt );
1173                                }
1174
1175                                continue;
1176                        }
1177
1178                        // use default initializers if out of arguments
1179                        if ( nextArg >= args.size() ) {
1180                                if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
1181                                        if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
1182                                                TypeEnvironment env = results[i].env;
1183                                                AssertionSet need = results[i].need, have = results[i].have;
1184                                                OpenVarSet openVars = results[i].openVars;
1185
1186                                                if ( unify( formalType, cnst->get_type(), env, need, have, openVars,
1187                                                                indexer ) ) {
1188                                                        results.emplace_back(
1189                                                                i, new DefaultArgExpr( cnstExpr ), move(env), move(need), move(have),
1190                                                                move(openVars), nextArg, nTuples );
1191                                                }
1192                                        }
1193                                }
1194
1195                                continue;
1196                        }
1197
1198                        // Check each possible next argument
1199                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
1200                                const ExplodedActual& expl = args[nextArg][j];
1201
1202                                // fresh copies of parent parameters for this iteration
1203                                TypeEnvironment env = results[i].env;
1204                                AssertionSet need = results[i].need, have = results[i].have;
1205                                OpenVarSet openVars = results[i].openVars;
1206
1207                                env.addActual( expl.env, openVars );
1208
1209                                // skip empty tuple arguments by (near-)cloning parent into next gen
1210                                if ( expl.exprs.empty() ) {
1211                                        results.emplace_back(
1212                                                results[i], move(env), move(need), move(have), move(openVars),
1213                                                nextArg + 1, expl.cost );
1214
1215                                        continue;
1216                                }
1217
1218                                // consider only first exploded actual
1219                                Expression* expr = expl.exprs.front();
1220                                Type* actualType = expr->result->clone();
1221
1222                                PRINT(
1223                                        std::cerr << "formal type is ";
1224                                        formalType->print( std::cerr );
1225                                        std::cerr << std::endl << "actual type is ";
1226                                        actualType->print( std::cerr );
1227                                        std::cerr << std::endl;
1228                                )
1229
1230                                // attempt to unify types
1231                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
1232                                        // add new result
1233                                        results.emplace_back(
1234                                                i, expr, move(env), move(need), move(have), move(openVars), nextArg + 1,
1235                                                nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
1236                                }
1237                        }
1238                }
1239
1240                // reset for next parameter
1241                genStart = genEnd;
1242
1243                return genEnd != results.size();
1244        }
1245
1246#if !1
1247        namespace {
1248
1249                struct CountSpecs : public WithVisitorRef<CountSpecs>, WithShortCircuiting {
1250
1251                        void postvisit(PointerType*) {
1252                                // mark specialization of base type
1253                                if ( count >= 0 ) ++count;
1254                        }
1255
1256                        void postvisit(ArrayType*) {
1257                                // mark specialization of base type
1258                                if ( count >= 0 ) ++count;
1259                        }
1260
1261                        void postvisit(ReferenceType*) {
1262                                // mark specialization of base type -- xxx maybe not?
1263                                if ( count >= 0 ) ++count;
1264                        }
1265
1266                private:
1267                        // takes minimum non-negative count over parameter/return list
1268                        void takeminover( int& mincount, std::list<DeclarationWithType*>& dwts ) {
1269                                for ( DeclarationWithType* dwt : dwts ) {
1270                                        count = -1;
1271                                        maybeAccept( dwt->get_type(), *visitor );
1272                                        if ( count != -1 && count < mincount ) mincount = count;
1273                                }
1274                        }
1275
1276                public:
1277                        void previsit(FunctionType*) {
1278                                // override default child visiting behaviour
1279                                visit_children = false;
1280                        }
1281
1282                        void postvisit(FunctionType* fty) {
1283                                // take minimal set value of count over ->returnVals and ->parameters
1284                                int mincount = std::numeric_limits<int>::max();
1285                                takeminover( mincount, fty->parameters );
1286                                takeminover( mincount, fty->returnVals );
1287                                // add another level to mincount if set
1288                                count = mincount < std::numeric_limits<int>::max() ? mincount + 1 : -1;
1289                        }
1290
1291                private:
1292                        // returns minimum non-negative count + 1 over type parameters (-1 if none such)
1293                        int minover( std::list<Expression*>& parms ) {
1294                                int mincount = std::numeric_limits<int>::max();
1295                                for ( Expression* parm : parms ) {
1296                                        count = -1;
1297                                        maybeAccept( parm->get_result(), *visitor );
1298                                        if ( count != -1 && count < mincount ) mincount = count;
1299                                }
1300                                return mincount < std::numeric_limits<int>::max() ? mincount + 1 : -1;
1301                        }
1302                       
1303                public:
1304                        void previsit(StructInstType*) {
1305                                // override default child behaviour
1306                                visit_children = false;
1307                        }
1308
1309                        void postvisit(StructInstType* sity) {
1310                                // look for polymorphic parameters
1311                                count = minover( sity->parameters );
1312                        }
1313
1314                        void previsit(UnionInstType*) {
1315                                // override default child behaviour
1316                                visit_children = false;
1317                        }
1318
1319                        void postvisit(UnionInstType* uity) {
1320                                // look for polymorphic parameters
1321                                count = minover( uity->parameters );
1322                        }
1323
1324                        void postvisit(TypeInstType*) {
1325                                // note polymorphic type (which may be specialized)
1326                                // xxx - maybe account for open/closed type variables
1327                                count = 0;
1328                        }
1329
1330                        void previsit(TupleType*) {
1331                                // override default child behaviour
1332                                visit_children = false;
1333                        }
1334
1335                        void postvisit(TupleType* tty) {
1336                                // take minimum non-negative count
1337                                int mincount = std::numeric_limits<int>::max();
1338                                for ( Type* ty : tty->types ) {
1339                                        count = -1;
1340                                        maybeAccept( ty, *visitor );
1341                                        if ( count != -1 && count < mincount ) mincount = count;
1342                                }
1343                                // xxx - maybe don't increment, tuple flattening doesn't necessarily specialize
1344                                count = mincount < std::numeric_limits<int>::max() ? mincount + 1: -1;
1345                        }
1346
1347                        int get_count() const { return count >= 0 ? count : 0; }
1348                private:
1349                        int count = -1;
1350                };
1351
1352                /// Counts the specializations in the types in a function parameter or return list
1353                int countSpecs( std::list<DeclarationWithType*>& dwts ) {
1354                        int k = 0;
1355                        for ( DeclarationWithType* dwt : dwts ) {
1356                                PassVisitor<CountSpecs> counter;
1357                                maybeAccept( dwt->get_type(), *counter.pass.visitor );
1358                                k += counter.pass.get_count();
1359                        }
1360                        return k;
1361                }
1362
1363                /// Calculates the inherent costs in a function declaration; varCost for the number of
1364                /// type variables and specCost for type assertions, as well as PolyType specializations
1365                /// in the parameter and return lists.
1366                Cost declCost( FunctionType* funcType ) {
1367                        Cost k = Cost::zero;
1368
1369                        // add cost of type variables
1370                        k.incVar( funcType->forall.size() );
1371
1372                        // subtract cost of type assertions
1373                        for ( TypeDecl* td : funcType->forall ) {
1374                                k.decSpec( td->assertions.size() );
1375                        }
1376
1377                        // count specialized polymorphic types in parameter/return lists
1378                        k.decSpec( countSpecs( funcType->parameters ) );
1379                        k.decSpec( countSpecs( funcType->returnVals ) );
1380
1381                        return k;
1382                }
1383        }
1384#endif
1385
1386        template<typename OutputIterator>
1387        void AlternativeFinder::Finder::validateFunctionAlternative( const Alternative &func, 
1388                        ArgPack& result, const std::vector<ArgPack>& results, OutputIterator out ) {
1389                ApplicationExpr *appExpr = new ApplicationExpr( func.expr );
1390                // sum cost and accumulate actuals
1391                std::list<Expression*>& args = appExpr->args;
1392                Cost cost = func.cost;
1393                const ArgPack* pack = &result;
1394                while ( pack->expr ) {
1395                        args.push_front( pack->expr );
1396                        cost += pack->cost;
1397                        pack = &results[pack->parent];
1398                }
1399                // build and validate new alternative
1400                Alternative newAlt( appExpr, result.env, cost );
1401                PRINT(
1402                        std::cerr << "instantiate function success: " << appExpr << std::endl;
1403                        std::cerr << "need assertions:" << std::endl;
1404                        printAssertionSet( result.need, std::cerr, 8 );
1405                )
1406                inferParameters( result.need, result.have, std::move(newAlt), result.openVars, out );
1407        }
1408
1409        template<typename OutputIterator>
1410        void AlternativeFinder::Finder::makeFunctionAlternatives( const Alternative &func,
1411                        FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) {
1412                OpenVarSet funcOpenVars;
1413                AssertionSet funcNeed, funcHave;
1414                TypeEnvironment funcEnv( func.env );
1415                makeUnifiableVars( funcType, funcOpenVars, funcNeed );
1416                // add all type variables as open variables now so that those not used in the parameter
1417                // list are still considered open.
1418                funcEnv.add( funcType->forall );
1419
1420                if ( targetType && ! targetType->isVoid() && ! funcType->returnVals.empty() ) {
1421                        // attempt to narrow based on expected target type
1422                        Type * returnType = funcType->returnVals.front()->get_type();
1423                        if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars,
1424                                        indexer ) ) {
1425                                // unification failed, don't pursue this function alternative
1426                                return;
1427                        }
1428                }
1429
1430                // calculate declaration cost of function (+vars-spec)
1431#if !1
1432                Cost funcCost = declCost( funcType );
1433#else
1434                Cost funcCost = Cost::zero;
1435#endif
1436
1437                // iteratively build matches, one parameter at a time
1438                std::vector<ArgPack> results;
1439                results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars, funcCost } );
1440                std::size_t genStart = 0;
1441
1442                for ( DeclarationWithType* formal : funcType->parameters ) {
1443                        ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal );
1444                        if ( ! instantiateArgument(
1445                                        obj->type, obj->init, args, results, genStart, indexer ) )
1446                                return;
1447                }
1448
1449                if ( funcType->get_isVarArgs() ) {
1450                        // append any unused arguments to vararg pack
1451                        std::size_t genEnd;
1452                        do {
1453                                genEnd = results.size();
1454
1455                                // iterate results
1456                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
1457                                        auto nextArg = results[i].nextArg;
1458
1459                                        // use remainder of exploded tuple if present
1460                                        if ( results[i].hasExpl() ) {
1461                                                const ExplodedActual& expl = results[i].getExpl( args );
1462
1463                                                unsigned nextExpl = results[i].nextExpl + 1;
1464                                                if ( nextExpl == expl.exprs.size() ) {
1465                                                        nextExpl = 0;
1466                                                }
1467
1468                                                results.emplace_back(
1469                                                        i, expl.exprs[results[i].nextExpl], copy(results[i].env),
1470                                                        copy(results[i].need), copy(results[i].have),
1471                                                        copy(results[i].openVars), nextArg, 0, Cost::zero, nextExpl,
1472                                                        results[i].explAlt );
1473
1474                                                continue;
1475                                        }
1476
1477                                        // finish result when out of arguments
1478                                        if ( nextArg >= args.size() ) {
1479                                                validateFunctionAlternative( func, results[i], results, out );
1480
1481                                                continue;
1482                                        }
1483
1484                                        // add each possible next argument
1485                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
1486                                                const ExplodedActual& expl = args[nextArg][j];
1487
1488                                                // fresh copies of parent parameters for this iteration
1489                                                TypeEnvironment env = results[i].env;
1490                                                OpenVarSet openVars = results[i].openVars;
1491
1492                                                env.addActual( expl.env, openVars );
1493
1494                                                // skip empty tuple arguments by (near-)cloning parent into next gen
1495                                                if ( expl.exprs.empty() ) {
1496                                                        results.emplace_back(
1497                                                                results[i], move(env), copy(results[i].need),
1498                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
1499
1500                                                        continue;
1501                                                }
1502
1503                                                // add new result
1504                                                results.emplace_back(
1505                                                        i, expl.exprs.front(), move(env), copy(results[i].need),
1506                                                        copy(results[i].have), move(openVars), nextArg + 1, 0,
1507                                                        expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
1508                                        }
1509                                }
1510
1511                                genStart = genEnd;
1512                        } while ( genEnd != results.size() );
1513                } else {
1514                        // filter out results that don't use all the arguments
1515                        for ( std::size_t i = genStart; i < results.size(); ++i ) {
1516                                ArgPack& result = results[i];
1517                                if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
1518                                        validateFunctionAlternative( func, result, results, out );
1519                                }
1520                        }
1521                }
1522        }
1523
1524        void AlternativeFinder::Finder::postvisit( UntypedExpr *untypedExpr ) {
1525                AlternativeFinder funcFinder( indexer, env );
1526                funcFinder.findWithAdjustment( untypedExpr->function );
1527                // if there are no function alternatives, then proceeding is a waste of time.
1528                // xxx - findWithAdjustment throws, so this check and others like it shouldn't be necessary.
1529                if ( funcFinder.alternatives.empty() ) return;
1530
1531                std::vector< AlternativeFinder > argAlternatives;
1532                altFinder.findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(),
1533                        back_inserter( argAlternatives ) );
1534
1535                // take care of possible tuple assignments
1536                // if not tuple assignment, assignment is taken care of as a normal function call
1537                Tuples::handleTupleAssignment( altFinder, untypedExpr, argAlternatives );
1538
1539                // find function operators
1540                static auto *opExpr = new_static_root<NameExpr>( "?()" );
1541                AlternativeFinder funcOpFinder( indexer, env );
1542                // it's ok if there aren't any defined function ops
1543                funcOpFinder.maybeFind( opExpr );
1544                PRINT(
1545                        std::cerr << "known function ops:" << std::endl;
1546                        printAlts( funcOpFinder.alternatives, std::cerr, 1 );
1547                )
1548
1549                // pre-explode arguments
1550                ExplodedArgs argExpansions;
1551                argExpansions.reserve( argAlternatives.size() );
1552
1553                for ( const AlternativeFinder& arg : argAlternatives ) {
1554                        argExpansions.emplace_back();
1555                        auto& argE = argExpansions.back();
1556                        // argE.reserve( arg.alternatives.size() );
1557
1558                        for ( const Alternative& actual : arg ) {
1559                                argE.emplace_back( actual, indexer );
1560                        }
1561                }
1562
1563                AltList candidates;
1564                SemanticErrorException errors;
1565                for ( AltList::iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
1566                        try {
1567                                PRINT(
1568                                        std::cerr << "working on alternative: " << std::endl;
1569                                        func->print( std::cerr, 8 );
1570                                )
1571                                // check if the type is pointer to function
1572                                if ( PointerType *pointer = dynamic_cast< PointerType* >( func->expr->get_result()->stripReferences() ) ) {
1573                                        if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
1574                                                Alternative newFunc( *func );
1575                                                referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1576                                                makeFunctionAlternatives( newFunc, function, argExpansions,
1577                                                        std::back_inserter( candidates ) );
1578                                        }
1579                                } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->result->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
1580                                        if ( ClassRef eqvClass = func->env.lookup( typeInst->name ) ) {
1581                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.get_bound().type ) ) {
1582                                                        Alternative newFunc( *func );
1583                                                        referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1584                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
1585                                                                std::back_inserter( candidates ) );
1586                                                } // if
1587                                        } // if
1588                                }
1589                        } catch ( SemanticErrorException &e ) {
1590                                errors.append( e );
1591                        }
1592                } // for
1593
1594                // try each function operator ?() with each function alternative
1595                if ( ! funcOpFinder.alternatives.empty() ) {
1596                        // add exploded function alternatives to front of argument list
1597                        std::vector<ExplodedActual> funcE;
1598                        funcE.reserve( funcFinder.alternatives.size() );
1599                        for ( const Alternative& actual : funcFinder ) {
1600                                funcE.emplace_back( actual, indexer );
1601                        }
1602                        argExpansions.insert( argExpansions.begin(), move(funcE) );
1603
1604                        for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
1605                                        funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
1606                                try {
1607                                        // check if type is a pointer to function
1608                                        if ( PointerType* pointer = dynamic_cast<PointerType*>(
1609                                                        funcOp->expr->get_result()->stripReferences() ) ) {
1610                                                if ( FunctionType* function =
1611                                                                dynamic_cast<FunctionType*>( pointer->get_base() ) ) {
1612                                                        Alternative newFunc( *funcOp );
1613                                                        referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1614                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
1615                                                                std::back_inserter( candidates ) );
1616                                                }
1617                                        }
1618                                } catch ( SemanticErrorException &e ) {
1619                                        errors.append( e );
1620                                }
1621                        }
1622                }
1623
1624                // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
1625                if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
1626
1627                // compute conversionsion costs
1628                for ( Alternative& withFunc : candidates ) {
1629                        Cost cvtCost = computeApplicationConversionCost( withFunc, indexer );
1630
1631                        PRINT(
1632                                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr );
1633                                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
1634                                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
1635                                std::cerr << "Case +++++++++++++ " << appExpr->get_function() << std::endl;
1636                                std::cerr << "formals are:" << std::endl;
1637                                printAll( function->get_parameters(), std::cerr, 8 );
1638                                std::cerr << "actuals are:" << std::endl;
1639                                printAll( appExpr->get_args(), std::cerr, 8 );
1640                                std::cerr << "bindings are:" << std::endl;
1641                                withFunc.env.print( std::cerr, 8 );
1642                                std::cerr << "cost of conversion is:" << cvtCost << std::endl;
1643                        )
1644                        if ( cvtCost != Cost::infinity ) {
1645                                withFunc.cvtCost = cvtCost;
1646                                alternatives.push_back( withFunc );
1647                        } // if
1648                } // for
1649
1650                candidates = move(alternatives);
1651
1652                // use a new list so that alternatives are not examined by addAnonConversions twice.
1653                AltList winners;
1654                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) );
1655
1656                // function may return struct or union value, in which case we need to add alternatives
1657                // for implicitconversions to each of the anonymous members, must happen after findMinCost
1658                // since anon conversions are never the cheapest expression
1659                for ( const Alternative & alt : winners ) {
1660                        addAnonConversions( alt );
1661                }
1662                spliceBegin( alternatives, winners );
1663
1664                if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
1665                        // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
1666                        // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
1667                        //   forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
1668                        //   const char * x = "hello world";
1669                        //   unsigned char ch = x[0];
1670                        // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
1671                        // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
1672                        // fix this issue in a more robust way.
1673                        targetType = nullptr;
1674                        postvisit( untypedExpr );
1675                }
1676        }
1677
1678        bool isLvalue( Expression *expr ) {
1679                // xxx - recurse into tuples?
1680                return expr->result && ( expr->get_result()->get_lvalue() || dynamic_cast< ReferenceType * >( expr->get_result() ) );
1681        }
1682
1683        void AlternativeFinder::Finder::postvisit( AddressExpr *addressExpr ) {
1684                AlternativeFinder finder( indexer, env );
1685                finder.find( addressExpr->get_arg() );
1686                for ( Alternative& alt : finder.alternatives ) {
1687                        if ( isLvalue( alt.expr ) ) {
1688                                alternatives.push_back(
1689                                        Alternative{ new AddressExpr( alt.expr ), alt.env, alt.cost } );
1690                        } // if
1691                } // for
1692        }
1693
1694        void AlternativeFinder::Finder::postvisit( LabelAddressExpr * expr ) {
1695                alternatives.push_back( Alternative{ expr, env, Cost::zero } );
1696        }
1697
1698        Expression * restructureCast( Expression * argExpr, Type * toType, bool isGenerated ) {
1699                if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() && ! dynamic_cast<ReferenceType *>( toType ) ) {
1700                        // Argument expression is a tuple and the target type is not void and not a reference type.
1701                        // Cast each member of the tuple to its corresponding target type, producing the tuple of those
1702                        // cast expressions. If there are more components of the tuple than components in the target type,
1703                        // then excess components do not come out in the result expression (but UniqueExprs ensure that
1704                        // side effects will still be done).
1705                        if ( Tuples::maybeImpureIgnoreUnique( argExpr ) ) {
1706                                // expressions which may contain side effects require a single unique instance of the expression.
1707                                argExpr = new UniqueExpr( argExpr );
1708                        }
1709                        std::list< Expression * > componentExprs;
1710                        for ( unsigned int i = 0; i < toType->size(); i++ ) {
1711                                // cast each component
1712                                TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
1713                                componentExprs.push_back( restructureCast( idx, toType->getComponent( i ), isGenerated ) );
1714                        }
1715                        assert( componentExprs.size() > 0 );
1716                        // produce the tuple of casts
1717                        return new TupleExpr( componentExprs );
1718                } else {
1719                        // handle normally
1720                        CastExpr * ret = new CastExpr( argExpr, toType->clone() );
1721                        ret->isGenerated = isGenerated;
1722                        return ret;
1723                }
1724        }
1725
1726        void AlternativeFinder::Finder::postvisit( CastExpr *castExpr ) {
1727                Type *& toType = castExpr->get_result();
1728                assert( toType );
1729                toType = resolveTypeof( toType, indexer );
1730                SymTab::validateType( toType, &indexer );
1731                adjustExprType( toType, env, indexer );
1732
1733                AlternativeFinder finder( indexer, env );
1734                finder.targetType = toType;
1735                finder.findWithAdjustment( castExpr->arg );
1736
1737                AltList candidates;
1738                for ( Alternative & alt : finder.alternatives ) {
1739                        AssertionSet needAssertions, haveAssertions;
1740                        OpenVarSet openVars;
1741
1742                        alt.env.extractOpenVars( openVars );
1743
1744                        // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1745                        // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1746                        // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1747                        // to.
1748                        int discardedValues = alt.expr->result->size() - castExpr->result->size();
1749                        if ( discardedValues < 0 ) continue;
1750                        // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1751                        // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1752                        // unification run for side-effects
1753                        unify( castExpr->result, alt.expr->result, alt.env, needAssertions,
1754                                haveAssertions, openVars, indexer );
1755                        Cost thisCost = castCost( alt.expr->result, castExpr->result, indexer,
1756                                alt.env );
1757                        PRINT(
1758                                std::cerr << "working on cast with result: " << castExpr->result << std::endl;
1759                                std::cerr << "and expr type: " << alt.expr->result << std::endl;
1760                                std::cerr << "env: " << alt.env << std::endl;
1761                        )
1762                        if ( thisCost != Cost::infinity ) {
1763                                PRINT(
1764                                        std::cerr << "has finite cost." << std::endl;
1765                                )
1766                                // count one safe conversion for each value that is thrown away
1767                                thisCost.incSafe( discardedValues );
1768                                Alternative newAlt( restructureCast( alt.expr->clone(), toType, castExpr->isGenerated ), alt.env,
1769                                        alt.cost, thisCost );
1770                                inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars,
1771                                        back_inserter( candidates ) );
1772                        } // if
1773                } // for
1774
1775                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1776                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1777                // selects first based on argument cost, then on conversion cost.
1778                AltList minArgCost;
1779                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1780                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1781        }
1782
1783        void AlternativeFinder::Finder::postvisit( VirtualCastExpr * castExpr ) {
1784                assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." );
1785                AlternativeFinder finder( indexer, env );
1786                // don't prune here, since it's guaranteed all alternatives will have the same type
1787                finder.findWithoutPrune( castExpr->get_arg() );
1788                for ( Alternative & alt : finder.alternatives ) {
1789                        alternatives.push_back( Alternative(
1790                                new VirtualCastExpr( alt.expr, castExpr->get_result()->clone() ),
1791                                alt.env, alt.cost ) );
1792                }
1793        }
1794
1795        namespace {
1796                /// Gets name from untyped member expression (member must be NameExpr)
1797                const std::string& get_member_name( UntypedMemberExpr *memberExpr ) {
1798                        NameExpr * nameExpr = dynamic_cast< NameExpr * >( memberExpr->get_member() );
1799                        assert( nameExpr );
1800                        return nameExpr->get_name();
1801                }
1802        }
1803
1804        void AlternativeFinder::Finder::postvisit( UntypedMemberExpr *memberExpr ) {
1805                AlternativeFinder funcFinder( indexer, env );
1806                funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
1807                for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
1808                        // 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
1809                        Cost cost = agg->cost;
1810                        Expression * aggrExpr = agg->expr->clone();
1811                        referenceToRvalueConversion( aggrExpr, cost );
1812
1813                        // find member of the given type
1814                        if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
1815                                addAggMembers( structInst, aggrExpr, cost, agg->env, get_member_name(memberExpr) );
1816                        } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
1817                                addAggMembers( unionInst, aggrExpr, cost, agg->env, get_member_name(memberExpr) );
1818                        } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
1819                                addTupleMembers( tupleType, aggrExpr, cost, agg->env, memberExpr->get_member() );
1820                        } // if
1821                } // for
1822        }
1823
1824        void AlternativeFinder::Finder::postvisit( MemberExpr *memberExpr ) {
1825                alternatives.push_back( Alternative( memberExpr, env, Cost::zero ) );
1826        }
1827
1828        void AlternativeFinder::Finder::postvisit( NameExpr *nameExpr ) {
1829                std::list< SymTab::Indexer::IdData > declList;
1830                indexer.lookupId( nameExpr->name, declList );
1831                PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )
1832                for ( auto & data : declList ) {
1833                        Cost cost = Cost::zero;
1834                        Expression * newExpr = data.combine( cost );
1835
1836                        // addAnonAlternatives uses vector::push_back, which invalidates references to existing elements, so
1837                        // can't construct in place and use vector::back
1838                        Alternative newAlt( newExpr, env, Cost::zero, cost );
1839                        PRINT(
1840                                std::cerr << "decl is ";
1841                                data.id->print( std::cerr );
1842                                std::cerr << std::endl;
1843                                std::cerr << "newExpr is ";
1844                                newExpr->print( std::cerr );
1845                                std::cerr << std::endl;
1846                        )
1847                        renameTypes( newAlt.expr );
1848                        addAnonConversions( newAlt ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
1849                        alternatives.push_back( std::move(newAlt) );
1850                } // for
1851        }
1852
1853        void AlternativeFinder::Finder::postvisit( VariableExpr *variableExpr ) {
1854                // not sufficient to clone here, because variable's type may have changed
1855                // since the VariableExpr was originally created.
1856                alternatives.push_back( Alternative( new VariableExpr( variableExpr->var ), env, Cost::zero ) );
1857        }
1858
1859        void AlternativeFinder::Finder::postvisit( ConstantExpr *constantExpr ) {
1860                alternatives.push_back( Alternative( constantExpr, env, Cost::zero ) );
1861        }
1862
1863        void AlternativeFinder::Finder::postvisit( SizeofExpr *sizeofExpr ) {
1864                if ( sizeofExpr->get_isType() ) {
1865                        Type * newType = sizeofExpr->get_type()->clone();
1866                        alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1867                } else {
1868                        // find all alternatives for the argument to sizeof
1869                        AlternativeFinder finder( indexer, env );
1870                        finder.find( sizeofExpr->get_expr() );
1871                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1872                        AltList winners;
1873                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1874                        if ( winners.size() != 1 ) {
1875                                SemanticError( sizeofExpr->get_expr(), "Ambiguous expression in sizeof operand: " );
1876                        } // if
1877                        // return the lowest cost alternative for the argument
1878                        Alternative &choice = winners.front();
1879                        referenceToRvalueConversion( choice.expr, choice.cost );
1880                        alternatives.push_back( Alternative( new SizeofExpr( choice.expr ), choice.env, Cost::zero ) );
1881                } // if
1882        }
1883
1884        void AlternativeFinder::Finder::postvisit( AlignofExpr *alignofExpr ) {
1885                if ( alignofExpr->get_isType() ) {
1886                        Type * newType = alignofExpr->get_type()->clone();
1887                        alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1888                } else {
1889                        // find all alternatives for the argument to sizeof
1890                        AlternativeFinder finder( indexer, env );
1891                        finder.find( alignofExpr->get_expr() );
1892                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1893                        AltList winners;
1894                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1895                        if ( winners.size() != 1 ) {
1896                                SemanticError( alignofExpr->get_expr(), "Ambiguous expression in alignof operand: " );
1897                        } // if
1898                        // return the lowest cost alternative for the argument
1899                        Alternative &choice = winners.front();
1900                        referenceToRvalueConversion( choice.expr, choice.cost );
1901                        alternatives.push_back( Alternative( new AlignofExpr( choice.expr ), choice.env, Cost::zero ) );
1902                } // if
1903        }
1904
1905        template< typename StructOrUnionType >
1906        void AlternativeFinder::Finder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
1907                std::list< Declaration* > members;
1908                aggInst->lookup( name, members );
1909                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
1910                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
1911                                alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
1912                                renameTypes( alternatives.back().expr );
1913                        } else {
1914                                assert( false );
1915                        }
1916                }
1917        }
1918
1919        void AlternativeFinder::Finder::postvisit( UntypedOffsetofExpr *offsetofExpr ) {
1920                AlternativeFinder funcFinder( indexer, env );
1921                // xxx - resolveTypeof?
1922                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
1923                        addOffsetof( structInst, offsetofExpr->member );
1924                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
1925                        addOffsetof( unionInst, offsetofExpr->member );
1926                }
1927        }
1928
1929        void AlternativeFinder::Finder::postvisit( OffsetofExpr *offsetofExpr ) {
1930                alternatives.push_back( Alternative( offsetofExpr, env, Cost::zero ) );
1931        }
1932
1933        void AlternativeFinder::Finder::postvisit( OffsetPackExpr *offsetPackExpr ) {
1934                alternatives.push_back( Alternative( offsetPackExpr, env, Cost::zero ) );
1935        }
1936
1937        namespace {
1938                void resolveAttr( SymTab::Indexer::IdData data, FunctionType *function, Type *argType, const TypeEnvironment &env, AlternativeFinder & finder ) {
1939                        // assume no polymorphism
1940                        // assume no implicit conversions
1941                        assert( function->get_parameters().size() == 1 );
1942                        PRINT(
1943                                std::cerr << "resolvAttr: funcDecl is ";
1944                                data.id->print( std::cerr );
1945                                std::cerr << " argType is ";
1946                                argType->print( std::cerr );
1947                                std::cerr << std::endl;
1948                        )
1949                        const SymTab::Indexer & indexer = finder.get_indexer();
1950                        AltList & alternatives = finder.get_alternatives();
1951                        if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1952                                Cost cost = Cost::zero;
1953                                Expression * newExpr = data.combine( cost );
1954                                alternatives.push_back( Alternative( new AttrExpr( newExpr, argType->clone() ), env, Cost::zero, cost ) );
1955                                for ( DeclarationWithType * retVal : function->returnVals ) {
1956                                        alternatives.back().expr->result = retVal->get_type()->clone();
1957                                } // for
1958                        } // if
1959                }
1960        }
1961
1962        void AlternativeFinder::Finder::postvisit( AttrExpr *attrExpr ) {
1963                // assume no 'pointer-to-attribute'
1964                NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1965                assert( nameExpr );
1966                std::list< SymTab::Indexer::IdData > attrList;
1967                indexer.lookupId( nameExpr->get_name(), attrList );
1968                if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1969                        for ( auto & data : attrList ) {
1970                                DeclarationWithType * id = data.id;
1971                                // check if the type is function
1972                                if ( FunctionType *function = dynamic_cast< FunctionType* >( id->get_type() ) ) {
1973                                        // assume exactly one parameter
1974                                        if ( function->get_parameters().size() == 1 ) {
1975                                                if ( attrExpr->get_isType() ) {
1976                                                        resolveAttr( data, function, attrExpr->get_type(), env, altFinder);
1977                                                } else {
1978                                                        AlternativeFinder finder( indexer, env );
1979                                                        finder.find( attrExpr->get_expr() );
1980                                                        for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1981                                                                if ( choice->expr->get_result()->size() == 1 ) {
1982                                                                        resolveAttr(data, function, choice->expr->get_result(), choice->env, altFinder );
1983                                                                } // fi
1984                                                        } // for
1985                                                } // if
1986                                        } // if
1987                                } // if
1988                        } // for
1989                } else {
1990                        for ( auto & data : attrList ) {
1991                                Cost cost = Cost::zero;
1992                                Expression * newExpr = data.combine( cost );
1993                                alternatives.push_back( Alternative( newExpr, env, Cost::zero, cost ) );
1994                                renameTypes( alternatives.back().expr );
1995                        } // for
1996                } // if
1997        }
1998
1999        void AlternativeFinder::Finder::postvisit( LogicalExpr *logicalExpr ) {
2000                AlternativeFinder firstFinder( indexer, env );
2001                firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
2002                if ( firstFinder.alternatives.empty() ) return;
2003                AlternativeFinder secondFinder( indexer, env );
2004                secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
2005                if ( secondFinder.alternatives.empty() ) return;
2006                for ( const Alternative & first : firstFinder.alternatives ) {
2007                        for ( const Alternative & second : secondFinder.alternatives ) {
2008                                TypeEnvironment compositeEnv;
2009                                compositeEnv.simpleCombine( first.env );
2010                                compositeEnv.simpleCombine( second.env );
2011
2012                                LogicalExpr *newExpr = new LogicalExpr( first.expr, second.expr, logicalExpr->get_isAnd() );
2013                                alternatives.push_back( Alternative( newExpr, compositeEnv, first.cost + second.cost ) );
2014                        }
2015                }
2016        }
2017
2018        void AlternativeFinder::Finder::postvisit( ConditionalExpr *conditionalExpr ) {
2019                // find alternatives for condition
2020                AlternativeFinder firstFinder( indexer, env );
2021                firstFinder.findWithAdjustment( conditionalExpr->arg1 );
2022                if ( firstFinder.alternatives.empty() ) return;
2023                // find alternatives for true expression
2024                AlternativeFinder secondFinder( indexer, env );
2025                secondFinder.findWithAdjustment( conditionalExpr->arg2 );
2026                if ( secondFinder.alternatives.empty() ) return;
2027                // find alterantives for false expression
2028                AlternativeFinder thirdFinder( indexer, env );
2029                thirdFinder.findWithAdjustment( conditionalExpr->arg3 );
2030                if ( thirdFinder.alternatives.empty() ) return;
2031                for ( const Alternative & first : firstFinder.alternatives ) {
2032                        for ( const Alternative & second : secondFinder.alternatives ) {
2033                                for ( const Alternative & third : thirdFinder.alternatives ) {
2034                                        TypeEnvironment compositeEnv;
2035                                        compositeEnv.simpleCombine( first.env );
2036                                        compositeEnv.simpleCombine( second.env );
2037                                        compositeEnv.simpleCombine( third.env );
2038
2039                                        // unify true and false types, then infer parameters to produce new alternatives
2040                                        OpenVarSet openVars;
2041                                        AssertionSet needAssertions, haveAssertions;
2042                                        Alternative newAlt( 0, compositeEnv, first.cost + second.cost + third.cost );
2043                                        Type* commonType = nullptr;
2044                                        if ( unify( second.expr->result, third.expr->result, newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
2045                                                ConditionalExpr *newExpr = new ConditionalExpr( first.expr, second.expr, third.expr );
2046                                                newExpr->result = commonType ? commonType : second.expr->result->clone();
2047                                                // convert both options to the conditional result type
2048                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env );
2049                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
2050                                                newAlt.expr = newExpr;
2051                                                inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars, back_inserter( alternatives ) );
2052                                        } // if
2053                                } // for
2054                        } // for
2055                } // for
2056        }
2057
2058        void AlternativeFinder::Finder::postvisit( CommaExpr *commaExpr ) {
2059                TypeEnvironment newEnv( env );
2060                Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
2061                AlternativeFinder secondFinder( indexer, newEnv );
2062                secondFinder.findWithAdjustment( commaExpr->get_arg2() );
2063                for ( const Alternative & alt : secondFinder.alternatives ) {
2064                        alternatives.push_back( Alternative( new CommaExpr( newFirstArg, alt.expr ), alt.env, alt.cost ) );
2065                } // for
2066        }
2067
2068        void AlternativeFinder::Finder::postvisit( RangeExpr * rangeExpr ) {
2069                // resolve low and high, accept alternatives whose low and high types unify
2070                AlternativeFinder firstFinder( indexer, env );
2071                firstFinder.findWithAdjustment( rangeExpr->low );
2072                if ( firstFinder.alternatives.empty() ) return;
2073                AlternativeFinder secondFinder( indexer, env );
2074                secondFinder.findWithAdjustment( rangeExpr->high );
2075                if ( secondFinder.alternatives.empty() ) return;
2076                for ( const Alternative & first : firstFinder.alternatives ) {
2077                        for ( const Alternative & second : secondFinder.alternatives ) {
2078                                TypeEnvironment compositeEnv;
2079                                compositeEnv.simpleCombine( first.env );
2080                                compositeEnv.simpleCombine( second.env );
2081                                OpenVarSet openVars;
2082                                AssertionSet needAssertions, haveAssertions;
2083                                Alternative newAlt( 0, compositeEnv, first.cost + second.cost );
2084                                Type* commonType = nullptr;
2085                                if ( unify( first.expr->result, second.expr->result, newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
2086                                        RangeExpr * newExpr = new RangeExpr( first.expr, second.expr );
2087                                        newExpr->result = commonType ? commonType : first.expr->result->clone();
2088                                        newAlt.expr = newExpr;
2089                                        inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars, back_inserter( alternatives ) );
2090                                } // if
2091                        } // for
2092                } // for
2093        }
2094
2095        void AlternativeFinder::Finder::postvisit( UntypedTupleExpr *tupleExpr ) {
2096                std::vector< AlternativeFinder > subExprAlternatives;
2097                altFinder.findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(),
2098                        back_inserter( subExprAlternatives ) );
2099                std::vector< AltList > possibilities;
2100                combos( subExprAlternatives.begin(), subExprAlternatives.end(),
2101                        back_inserter( possibilities ) );
2102                for ( const AltList& alts : possibilities ) {
2103                        std::list< Expression * > exprs;
2104                        makeExprList( alts, exprs );
2105
2106                        TypeEnvironment compositeEnv;
2107                        simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
2108                        alternatives.push_back(
2109                                Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } );
2110                } // for
2111        }
2112
2113        void AlternativeFinder::Finder::postvisit( TupleExpr *tupleExpr ) {
2114                alternatives.push_back( Alternative( tupleExpr, env, Cost::zero ) );
2115        }
2116
2117        void AlternativeFinder::Finder::postvisit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
2118                alternatives.push_back( Alternative( impCpCtorExpr, env, Cost::zero ) );
2119        }
2120
2121        void AlternativeFinder::Finder::postvisit( ConstructorExpr * ctorExpr ) {
2122                AlternativeFinder finder( indexer, env );
2123                // don't prune here, since it's guaranteed all alternatives will have the same type
2124                // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
2125                finder.findWithoutPrune( ctorExpr->get_callExpr() );
2126                for ( Alternative & alt : finder.alternatives ) {
2127                        alternatives.push_back( Alternative( new ConstructorExpr( alt.expr ), alt.env, alt.cost ) );
2128                }
2129        }
2130
2131        void AlternativeFinder::Finder::postvisit( TupleIndexExpr *tupleExpr ) {
2132                alternatives.push_back( Alternative( tupleExpr, env, Cost::zero ) );
2133        }
2134
2135        void AlternativeFinder::Finder::postvisit( TupleAssignExpr *tupleAssignExpr ) {
2136                alternatives.push_back( Alternative( tupleAssignExpr, env, Cost::zero ) );
2137        }
2138
2139        void AlternativeFinder::Finder::postvisit( UniqueExpr *unqExpr ) {
2140                AlternativeFinder finder( indexer, env );
2141                finder.findWithAdjustment( unqExpr->get_expr() );
2142                for ( Alternative & alt : finder.alternatives ) {
2143                        // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
2144                        UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr, unqExpr->get_id() );
2145                        alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
2146                }
2147        }
2148
2149        void AlternativeFinder::Finder::postvisit( StmtExpr *stmtExpr ) {
2150                StmtExpr * newStmtExpr = stmtExpr->clone();
2151                ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
2152                // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
2153                alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
2154        }
2155
2156        void AlternativeFinder::Finder::postvisit( UntypedInitExpr *initExpr ) {
2157                // handle each option like a cast
2158                AltList candidates;
2159                PRINT(
2160                        std::cerr << "untyped init expr: " << initExpr << std::endl;
2161                )
2162                // O(N^2) checks of d-types with e-types
2163                for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
2164                        Type * toType = resolveTypeof( initAlt.type->clone(), indexer );
2165                        SymTab::validateType( toType, &indexer );
2166                        adjustExprType( toType, env, indexer );
2167                        // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
2168                        // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
2169                        // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
2170                        AlternativeFinder finder( indexer, env );
2171                        finder.targetType = toType;
2172                        finder.findWithAdjustment( initExpr->expr );
2173                        for ( Alternative & alt : finder.get_alternatives() ) {
2174                                TypeEnvironment newEnv( alt.env );
2175                                AssertionSet needAssertions, haveAssertions;
2176                                OpenVarSet openVars;  // find things in env that don't have a "representative type" and claim those are open vars?
2177                                PRINT(
2178                                        std::cerr << "  @ " << toType << " " << initAlt.designation << std::endl;
2179                                )
2180                                // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
2181                                // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
2182                                // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
2183                                // to.
2184                                int discardedValues = alt.expr->result->size() - toType->size();
2185                                if ( discardedValues < 0 ) continue;
2186                                // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
2187                                // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
2188                                // unification run for side-effects
2189                                unify( toType, alt.expr->result, newEnv, needAssertions, haveAssertions, openVars, indexer ); // xxx - do some inspecting on this line... why isn't result bound to initAlt.type??
2190
2191                                Cost thisCost = castCost( alt.expr->result, toType, indexer, newEnv );
2192                                if ( thisCost != Cost::infinity ) {
2193                                        // count one safe conversion for each value that is thrown away
2194                                        thisCost.incSafe( discardedValues );
2195                                        Alternative newAlt( new InitExpr( restructureCast( alt.expr, toType, true ), initAlt.designation ), newEnv, alt.cost, thisCost );
2196                                        inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars, back_inserter( candidates ) );
2197                                }
2198                        }
2199                }
2200
2201                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
2202                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
2203                // selects first based on argument cost, then on conversion cost.
2204                AltList minArgCost;
2205                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
2206                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
2207        }
2208
2209        void AlternativeFinder::Finder::postvisit( InitExpr * ) {
2210                assertf( false, "AlternativeFinder should never see a resolved InitExpr." );
2211        }
2212
2213        void AlternativeFinder::Finder::postvisit( DeletedExpr * ) {
2214                assertf( false, "AlternativeFinder should never see a DeletedExpr." );
2215        }
2216
2217        void AlternativeFinder::Finder::postvisit( GenericExpr * ) {
2218                assertf( false, "_Generic is not yet supported." );
2219        }
2220} // namespace ResolvExpr
2221
2222// Local Variables: //
2223// tab-width: 4 //
2224// mode: c++ //
2225// compile-command: "make install" //
2226// End: //
Note: See TracBrowser for help on using the repository browser.