source: src/ResolvExpr/AlternativeFinder.cc @ 1a59641

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

Fix open var handling in BF assn resolution; memory usage reasonable again

  • Property mode set to 100644
File size: 88.5 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// AlternativeFinder.cc --
8//
9// Author           : Richard C. Bilson
10// Created On       : Sat May 16 23:52:08 2015
11// Last Modified By : 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                        for ( auto& a : match.need ) {
694                                if ( a.second.idChain.empty() ) {
695                                        a.second.idChain = assnInfo.idChain;
696                                        a.second.idChain.push_back( curDecl->get_uniqueId() );
697                                }
698                        }
699
700                        Expression* varExpr = match.cdata.combine( alt.cvtCost );
701                        varExpr->result = match.adjType;
702
703                        // follow the current assertion's ID chain to find the correct set of inferred
704                        // parameters to add the candidate o (i.e. the set of inferred parameters belonging
705                        // to the entity which requested the assertion parameter)
706                        InferredParams* inferParams = &alt.expr->inferParams;
707                        for ( UniqueId id : assnInfo.idChain ) {
708                                inferParams = (*inferParams)[ id ].inferParams.get();
709                        }
710
711                        (*inferParams)[ curDecl->get_uniqueId() ] = ParamEntry{
712                                candidate->get_uniqueId(), match.adjType, curDecl->get_type(), varExpr };
713                }
714
715                /// Resolves a single assertion, returning false if no satisfying assertion, binding it
716                /// if there is exactly one satisfying assertion, or adding to the defer-list if there
717                /// is more than one
718                bool resolveAssertion( DeclarationWithType* curDecl, AssertionSetValue& assnInfo, 
719                                AssertionResnState& resn ) {
720                        // skip unused assertions
721                        if ( ! assnInfo.isUsed ) return true;
722
723                        // lookup candidates for this assertion
724                        std::list< SymTab::Indexer::IdData > candidates;
725                        resn.indexer.lookupId( curDecl->name, candidates );
726
727                        // find the ones that unify with the desired type
728                        DeferList matches;
729                        for ( const auto& cdata : candidates ) {
730                                DeclarationWithType* candidate = cdata.id;
731
732                                // build independent unification context for candidate
733                                AssertionSet have, newNeed;
734                                TypeEnvironment newEnv{ resn.alt.env };
735                                OpenVarSet newOpenVars{ resn.openVars };
736                                Type* adjType = candidate->get_type()->clone();
737                                adjustExprType( adjType, newEnv, resn.indexer );
738                                renameTyVars( adjType );
739
740                                if ( unify( curDecl->get_type(), adjType, newEnv, 
741                                                newNeed, have, newOpenVars, resn.indexer ) ) {
742                                        matches.emplace_back( cdata, adjType, std::move(newEnv), std::move(have), 
743                                                std::move(newNeed), std::move(newOpenVars) );
744                                }
745                        }
746
747                        // Break if no suitable assertion
748                        if ( matches.empty() ) return false;
749
750                        // Defer if too many suitable assertions
751                        if ( matches.size() > 1 ) {
752                                resn.deferred.emplace_back( curDecl, assnInfo, std::move(matches) );
753                                return true;
754                        }
755
756                        // otherwise bind current match in ongoing scope
757                        AssertionPack& match = matches.front();
758                        addToIndexer( match.have, resn.indexer );
759                        resn.newNeed.insert( match.need.begin(), match.need.end() );
760                        resn.openVars = std::move(match.openVars);
761                        resn.alt.env = std::move(match.env);
762
763                        bindAssertion( curDecl, assnInfo, resn.alt, match );
764                        return true;
765                }
766
767                /// Combo iterator that combines interpretations into an interpretation list, merging
768                /// their environments. Rejects an appended interpretation if the environments cannot
769                /// be merged.
770                class InterpretationEnvMerger {
771                        /// Current list of merged interpretations
772                        std::vector<DeferElement> crnt;
773                        /// Stack of environments, to support backtracking
774                        std::vector<TypeEnvironment> envs;
775                        /// Open variables for environment combination
776                        std::vector<OpenVarSet> varSets;
777                        /// Indexer to use for environment merges
778                        const SymTab::Indexer& indexer;
779                public:
780                        /// The merged environment/open variables and the list of interpretations
781                        struct OutType {
782                                TypeEnvironment env;
783                                OpenVarSet openVars;
784                                std::vector<DeferElement> assns;
785
786                                OutType( const TypeEnvironment& env, const OpenVarSet& openVars, 
787                                        const std::vector<DeferElement>& assns )
788                                        : env(env), openVars(openVars), assns(assns) {}
789                        };
790
791                        InterpretationEnvMerger( const TypeEnvironment& env, const OpenVarSet& openVars, 
792                                const SymTab::Indexer& indexer ) : crnt{}, envs{}, varSets{}, indexer{indexer} {
793                                envs.push_back( env );
794                                varSets.push_back( openVars );
795                        }
796
797                        ComboResult append( DeferElement i ) {
798                                TypeEnvironment env = envs.back();
799                                OpenVarSet openVars = varSets.back();
800                                mergeOpenVars( openVars, i.match.openVars );
801
802                                if ( ! env.combine( i.match.env, openVars, indexer ) )
803                                        return ComboResult::REJECT_THIS;
804                               
805                                crnt.push_back( i );
806                                envs.push_back( env );
807                                varSets.push_back( openVars );
808                                return ComboResult::ACCEPT;
809                        }
810
811                        void backtrack() {
812                                crnt.pop_back();
813                                envs.pop_back();
814                                varSets.pop_back();
815                        }
816
817                        OutType finalize() { return { envs.back(), varSets.back(), crnt }; }
818                };
819        }
820#endif
821
822        template< typename OutputIterator >
823        void AlternativeFinder::Finder::inferParameters( const AssertionSet &need, AssertionSet &have, Alternative &&newAlt, OpenVarSet &openVars, OutputIterator out ) {
824//      PRINT(
825//          std::cerr << "inferParameters: assertions needed are" << std::endl;
826//          printAll( need, std::cerr, 8 );
827//          )
828                SymTab::Indexer decls( indexer );
829                // PRINT(
830                //      std::cerr << "============= original indexer" << std::endl;
831                //      indexer.print( std::cerr );
832                //      std::cerr << "============= new indexer" << std::endl;
833                //      decls.print( std::cerr );
834                // )
835                addToIndexer( have, decls );
836#if 1
837                using ResnList = std::vector<AssertionResnState>;
838                ResnList resns{ AssertionResnState{ std::move(newAlt), need, openVars, decls } };
839                ResnList new_resns{};
840
841                // resolve assertions in breadth-first-order up to a limited number of levels deep
842                for ( int level = 0; level < recursionLimit; ++level ) {
843                        // scan over all mutually-compatible resolutions
844                        for ( auto& resn : resns ) {
845                                // make initial pass at matching assertions
846                                for ( auto& assn : resn.need ) {
847                                        if ( ! resolveAssertion( assn.first, assn.second, resn ) ) {
848                                                // fail early if any assertion fails to resolve
849                                                goto nextResn;
850                                        }
851                                }
852
853                                if ( ! resn.deferred.empty() ) {
854                                        // resolve deferred assertions by mutual compatibility
855
856                                        std::vector<InterpretationEnvMerger::OutType> compatible = filterCombos( 
857                                                resn.deferred, 
858                                                InterpretationEnvMerger{ resn.alt.env, resn.openVars, resn.indexer } );
859                                       
860                                        for ( auto& compat : compatible ) {
861                                                AssertionResnState new_resn = resn;
862
863                                                // add compatible assertions to new resolution state
864                                                for ( DeferElement el : compat.assns ) {
865                                                        AssertionPack match = el.match;
866                                                        addToIndexer( match.have, new_resn.indexer );
867                                                        resn.newNeed.insert( match.need.begin(), match.need.end() );
868                                                       
869                                                        bindAssertion( el.curDecl, el.assnInfo, new_resn.alt, match );
870                                                }
871
872                                                // set mutual environment into resolution state
873                                                new_resn.alt.env = std::move(compat.env);
874                                                new_resn.openVars = std::move(compat.openVars);
875
876                                                // add successful match or push back next state
877                                                if ( new_resn.newNeed.empty() ) {
878                                                        *out++ = new_resn.alt;
879                                                } else {
880                                                        new_resns.emplace_back( std::move(new_resn), IterateState );
881                                                }
882                                        }
883                                } else {
884                                        // add successful match or push back next state
885                                        if ( resn.newNeed.empty() ) {
886                                                *out++ = resn.alt;
887                                        } else {
888                                                new_resns.emplace_back( std::move(resn), IterateState );
889                                        }
890                                }
891                        nextResn:; }
892                       
893                        // finish or reset for next round
894                        if ( new_resns.empty() ) return;
895                        resns.swap( new_resns );
896                        new_resns.clear();
897                }
898                // if reaches here, exceeded recursion limit
899                SemanticError( newAlt.expr->location, "Too many recursive assertions" );
900
901#else           
902                AssertionSet newNeed;
903                PRINT(
904                        std::cerr << "env is: " << std::endl;
905                        newAlt.env.print( std::cerr, 0 );
906                        std::cerr << std::endl;
907                )
908
909                inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, 0, indexer, out );
910//      PRINT(
911//          std::cerr << "declaration 14 is ";
912//          Declaration::declFromId
913//          *out++ = newAlt;
914//          )
915#endif
916        }
917
918        /// Gets a default value from an initializer, nullptr if not present
919        ConstantExpr* getDefaultValue( Initializer* init ) {
920                if ( SingleInit* si = dynamic_cast<SingleInit*>( init ) ) {
921                        if ( CastExpr* ce = dynamic_cast<CastExpr*>( si->value ) ) {
922                                return dynamic_cast<ConstantExpr*>( ce->arg );
923                        } else {
924                                return dynamic_cast<ConstantExpr*>( si->value );
925                        }
926                }
927                return nullptr;
928        }
929
930        /// State to iteratively build a match of parameter expressions to arguments
931        struct ArgPack {
932                std::size_t parent;                ///< Index of parent pack
933                Expression* expr;                  ///< The argument stored here
934                Cost cost;                         ///< The cost of this argument
935                TypeEnvironment env;               ///< Environment for this pack
936                AssertionSet need;                 ///< Assertions outstanding for this pack
937                AssertionSet have;                 ///< Assertions found for this pack
938                OpenVarSet openVars;               ///< Open variables for this pack
939                unsigned nextArg;                  ///< Index of next argument in arguments list
940                unsigned tupleStart;               ///< Number of tuples that start at this index
941                unsigned nextExpl;                 ///< Index of next exploded element
942                unsigned explAlt;                  ///< Index of alternative for nextExpl > 0
943
944                ArgPack()
945                        : parent(0), expr(nullptr), cost(Cost::zero), env(), need(), have(), openVars(), 
946                          nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
947
948                ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
949                                const OpenVarSet& openVars, Cost initCost = Cost::zero)
950                        : parent(0), expr(nullptr), cost(initCost), env(env), need(need), have(have),
951                          openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
952
953                ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need,
954                                AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg,
955                                unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0,
956                                unsigned explAlt = 0 )
957                        : parent(parent), expr(expr), cost(cost), env(move(env)), need(move(need)),
958                          have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart),
959                          nextExpl(nextExpl), explAlt(explAlt) {}
960
961                ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have,
962                                OpenVarSet&& openVars, unsigned nextArg, Cost added )
963                        : parent(o.parent), expr(o.expr), cost(o.cost + added), env(move(env)), 
964                          need(move(need)), have(move(have)), openVars(move(openVars)), nextArg(nextArg), 
965                          tupleStart(o.tupleStart), nextExpl(0), explAlt(0) {}
966
967                /// true iff this pack is in the middle of an exploded argument
968                bool hasExpl() const { return nextExpl > 0; }
969
970                /// Gets the list of exploded alternatives for this pack
971                const ExplodedActual& getExpl( const ExplodedArgs& args ) const {
972                        return args[nextArg-1][explAlt];
973                }
974
975                /// Ends a tuple expression, consolidating the appropriate actuals
976                void endTuple( const std::vector<ArgPack>& packs ) {
977                        // add all expressions in tuple to list, summing cost
978                        std::list<Expression*> exprs;
979                        const ArgPack* pack = this;
980                        if ( expr ) { exprs.push_front( expr ); }
981                        while ( pack->tupleStart == 0 ) {
982                                pack = &packs[pack->parent];
983                                exprs.push_front( pack->expr );
984                                cost += pack->cost;
985                        }
986                        // reset pack to appropriate tuple
987                        expr = new TupleExpr{ exprs };
988                        tupleStart = pack->tupleStart - 1;
989                        parent = pack->parent;
990                }
991        };
992
993        /// Instantiates an argument to match a formal, returns false if no results left
994        bool instantiateArgument( Type* formalType, Initializer* initializer,
995                        const ExplodedArgs& args, std::vector<ArgPack>& results, std::size_t& genStart,
996                        const SymTab::Indexer& indexer, unsigned nTuples = 0 ) {
997                if ( TupleType * tupleType = dynamic_cast<TupleType*>( formalType ) ) {
998                        // formalType is a TupleType - group actuals into a TupleExpr
999                        ++nTuples;
1000                        for ( Type* type : *tupleType ) {
1001                                // xxx - dropping initializer changes behaviour from previous, but seems correct
1002                                // ^^^ need to handle the case where a tuple has a default argument
1003                                if ( ! instantiateArgument(
1004                                                type, nullptr, args, results, genStart, indexer, nTuples ) )
1005                                        return false;
1006                                nTuples = 0;
1007                        }
1008                        // re-consititute tuples for final generation
1009                        for ( auto i = genStart; i < results.size(); ++i ) {
1010                                results[i].endTuple( results );
1011                        }
1012                        return true;
1013                } else if ( TypeInstType * ttype = Tuples::isTtype( formalType ) ) {
1014                        // formalType is a ttype, consumes all remaining arguments
1015                        // xxx - mixing default arguments with variadic??
1016
1017                        // completed tuples; will be spliced to end of results to finish
1018                        std::vector<ArgPack> finalResults{};
1019
1020                        // iterate until all results completed
1021                        std::size_t genEnd;
1022                        ++nTuples;
1023                        do {
1024                                genEnd = results.size();
1025
1026                                // add another argument to results
1027                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
1028                                        auto nextArg = results[i].nextArg;
1029
1030                                        // use next element of exploded tuple if present
1031                                        if ( results[i].hasExpl() ) {
1032                                                const ExplodedActual& expl = results[i].getExpl( args );
1033
1034                                                unsigned nextExpl = results[i].nextExpl + 1;
1035                                                if ( nextExpl == expl.exprs.size() ) {
1036                                                        nextExpl = 0;
1037                                                }
1038
1039                                                results.emplace_back(
1040                                                        i, expl.exprs[results[i].nextExpl], copy(results[i].env),
1041                                                        copy(results[i].need), copy(results[i].have),
1042                                                        copy(results[i].openVars), nextArg, nTuples, Cost::zero, nextExpl,
1043                                                        results[i].explAlt );
1044
1045                                                continue;
1046                                        }
1047
1048                                        // finish result when out of arguments
1049                                        if ( nextArg >= args.size() ) {
1050                                                ArgPack newResult{
1051                                                        results[i].env, results[i].need, results[i].have,
1052                                                        results[i].openVars };
1053                                                newResult.nextArg = nextArg;
1054                                                Type* argType;
1055
1056                                                if ( nTuples > 0 || ! results[i].expr ) {
1057                                                        // first iteration or no expression to clone,
1058                                                        // push empty tuple expression
1059                                                        newResult.parent = i;
1060                                                        std::list<Expression*> emptyList;
1061                                                        newResult.expr = new TupleExpr{ emptyList };
1062                                                        argType = newResult.expr->get_result();
1063                                                } else {
1064                                                        // clone result to collect tuple
1065                                                        newResult.parent = results[i].parent;
1066                                                        newResult.cost = results[i].cost;
1067                                                        newResult.tupleStart = results[i].tupleStart;
1068                                                        newResult.expr = results[i].expr;
1069                                                        argType = newResult.expr->get_result();
1070
1071                                                        if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
1072                                                                // the case where a ttype value is passed directly is special,
1073                                                                // e.g. for argument forwarding purposes
1074                                                                // xxx - what if passing multiple arguments, last of which is
1075                                                                //       ttype?
1076                                                                // xxx - what would happen if unify was changed so that unifying
1077                                                                //       tuple
1078                                                                // types flattened both before unifying lists? then pass in
1079                                                                // TupleType (ttype) below.
1080                                                                --newResult.tupleStart;
1081                                                        } else {
1082                                                                // collapse leftover arguments into tuple
1083                                                                newResult.endTuple( results );
1084                                                                argType = newResult.expr->get_result();
1085                                                        }
1086                                                }
1087
1088                                                // check unification for ttype before adding to final
1089                                                if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have,
1090                                                                newResult.openVars, indexer ) ) {
1091                                                        finalResults.push_back( move(newResult) );
1092                                                }
1093
1094                                                continue;
1095                                        }
1096
1097                                        // add each possible next argument
1098                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
1099                                                const ExplodedActual& expl = args[nextArg][j];
1100
1101                                                // fresh copies of parent parameters for this iteration
1102                                                TypeEnvironment env = results[i].env;
1103                                                OpenVarSet openVars = results[i].openVars;
1104
1105                                                env.addActual( expl.env, openVars );
1106
1107                                                // skip empty tuple arguments by (near-)cloning parent into next gen
1108                                                if ( expl.exprs.empty() ) {
1109                                                        results.emplace_back(
1110                                                                results[i], move(env), copy(results[i].need),
1111                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
1112
1113                                                        continue;
1114                                                }
1115
1116                                                // add new result
1117                                                results.emplace_back(
1118                                                        i, expl.exprs.front(), move(env), copy(results[i].need),
1119                                                        copy(results[i].have), move(openVars), nextArg + 1,
1120                                                        nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
1121                                        }
1122                                }
1123
1124                                // reset for next round
1125                                genStart = genEnd;
1126                                nTuples = 0;
1127                        } while ( genEnd != results.size() );
1128
1129                        // splice final results onto results
1130                        for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
1131                                results.push_back( move(finalResults[i]) );
1132                        }
1133                        return ! finalResults.empty();
1134                }
1135
1136                // iterate each current subresult
1137                std::size_t genEnd = results.size();
1138                for ( std::size_t i = genStart; i < genEnd; ++i ) {
1139                        auto nextArg = results[i].nextArg;
1140
1141                        // use remainder of exploded tuple if present
1142                        if ( results[i].hasExpl() ) {
1143                                const ExplodedActual& expl = results[i].getExpl( args );
1144                                Expression* expr = expl.exprs[results[i].nextExpl];
1145
1146                                TypeEnvironment env = results[i].env;
1147                                AssertionSet need = results[i].need, have = results[i].have;
1148                                OpenVarSet openVars = results[i].openVars;
1149
1150                                Type* actualType = expr->get_result();
1151
1152                                PRINT(
1153                                        std::cerr << "formal type is ";
1154                                        formalType->print( std::cerr );
1155                                        std::cerr << std::endl << "actual type is ";
1156                                        actualType->print( std::cerr );
1157                                        std::cerr << std::endl;
1158                                )
1159
1160                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
1161                                        unsigned nextExpl = results[i].nextExpl + 1;
1162                                        if ( nextExpl == expl.exprs.size() ) {
1163                                                nextExpl = 0;
1164                                        }
1165
1166                                        results.emplace_back(
1167                                                i, expr, move(env), move(need), move(have), move(openVars), nextArg,
1168                                                nTuples, Cost::zero, nextExpl, results[i].explAlt );
1169                                }
1170
1171                                continue;
1172                        }
1173
1174                        // use default initializers if out of arguments
1175                        if ( nextArg >= args.size() ) {
1176                                if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
1177                                        if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
1178                                                TypeEnvironment env = results[i].env;
1179                                                AssertionSet need = results[i].need, have = results[i].have;
1180                                                OpenVarSet openVars = results[i].openVars;
1181
1182                                                if ( unify( formalType, cnst->get_type(), env, need, have, openVars,
1183                                                                indexer ) ) {
1184                                                        results.emplace_back(
1185                                                                i, new DefaultArgExpr( cnstExpr ), move(env), move(need), move(have),
1186                                                                move(openVars), nextArg, nTuples );
1187                                                }
1188                                        }
1189                                }
1190
1191                                continue;
1192                        }
1193
1194                        // Check each possible next argument
1195                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
1196                                const ExplodedActual& expl = args[nextArg][j];
1197
1198                                // fresh copies of parent parameters for this iteration
1199                                TypeEnvironment env = results[i].env;
1200                                AssertionSet need = results[i].need, have = results[i].have;
1201                                OpenVarSet openVars = results[i].openVars;
1202
1203                                env.addActual( expl.env, openVars );
1204
1205                                // skip empty tuple arguments by (near-)cloning parent into next gen
1206                                if ( expl.exprs.empty() ) {
1207                                        results.emplace_back(
1208                                                results[i], move(env), move(need), move(have), move(openVars),
1209                                                nextArg + 1, expl.cost );
1210
1211                                        continue;
1212                                }
1213
1214                                // consider only first exploded actual
1215                                Expression* expr = expl.exprs.front();
1216                                Type* actualType = expr->result->clone();
1217
1218                                PRINT(
1219                                        std::cerr << "formal type is ";
1220                                        formalType->print( std::cerr );
1221                                        std::cerr << std::endl << "actual type is ";
1222                                        actualType->print( std::cerr );
1223                                        std::cerr << std::endl;
1224                                )
1225
1226                                // attempt to unify types
1227                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
1228                                        // add new result
1229                                        results.emplace_back(
1230                                                i, expr, move(env), move(need), move(have), move(openVars), nextArg + 1,
1231                                                nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
1232                                }
1233                        }
1234                }
1235
1236                // reset for next parameter
1237                genStart = genEnd;
1238
1239                return genEnd != results.size();
1240        }
1241
1242#if !1
1243        namespace {
1244
1245                struct CountSpecs : public WithVisitorRef<CountSpecs>, WithShortCircuiting {
1246
1247                        void postvisit(PointerType*) {
1248                                // mark specialization of base type
1249                                if ( count >= 0 ) ++count;
1250                        }
1251
1252                        void postvisit(ArrayType*) {
1253                                // mark specialization of base type
1254                                if ( count >= 0 ) ++count;
1255                        }
1256
1257                        void postvisit(ReferenceType*) {
1258                                // mark specialization of base type -- xxx maybe not?
1259                                if ( count >= 0 ) ++count;
1260                        }
1261
1262                private:
1263                        // takes minimum non-negative count over parameter/return list
1264                        void takeminover( int& mincount, std::list<DeclarationWithType*>& dwts ) {
1265                                for ( DeclarationWithType* dwt : dwts ) {
1266                                        count = -1;
1267                                        maybeAccept( dwt->get_type(), *visitor );
1268                                        if ( count != -1 && count < mincount ) mincount = count;
1269                                }
1270                        }
1271
1272                public:
1273                        void previsit(FunctionType*) {
1274                                // override default child visiting behaviour
1275                                visit_children = false;
1276                        }
1277
1278                        void postvisit(FunctionType* fty) {
1279                                // take minimal set value of count over ->returnVals and ->parameters
1280                                int mincount = std::numeric_limits<int>::max();
1281                                takeminover( mincount, fty->parameters );
1282                                takeminover( mincount, fty->returnVals );
1283                                // add another level to mincount if set
1284                                count = mincount < std::numeric_limits<int>::max() ? mincount + 1 : -1;
1285                        }
1286
1287                private:
1288                        // returns minimum non-negative count + 1 over type parameters (-1 if none such)
1289                        int minover( std::list<Expression*>& parms ) {
1290                                int mincount = std::numeric_limits<int>::max();
1291                                for ( Expression* parm : parms ) {
1292                                        count = -1;
1293                                        maybeAccept( parm->get_result(), *visitor );
1294                                        if ( count != -1 && count < mincount ) mincount = count;
1295                                }
1296                                return mincount < std::numeric_limits<int>::max() ? mincount + 1 : -1;
1297                        }
1298                       
1299                public:
1300                        void previsit(StructInstType*) {
1301                                // override default child behaviour
1302                                visit_children = false;
1303                        }
1304
1305                        void postvisit(StructInstType* sity) {
1306                                // look for polymorphic parameters
1307                                count = minover( sity->parameters );
1308                        }
1309
1310                        void previsit(UnionInstType*) {
1311                                // override default child behaviour
1312                                visit_children = false;
1313                        }
1314
1315                        void postvisit(UnionInstType* uity) {
1316                                // look for polymorphic parameters
1317                                count = minover( uity->parameters );
1318                        }
1319
1320                        void postvisit(TypeInstType*) {
1321                                // note polymorphic type (which may be specialized)
1322                                // xxx - maybe account for open/closed type variables
1323                                count = 0;
1324                        }
1325
1326                        void previsit(TupleType*) {
1327                                // override default child behaviour
1328                                visit_children = false;
1329                        }
1330
1331                        void postvisit(TupleType* tty) {
1332                                // take minimum non-negative count
1333                                int mincount = std::numeric_limits<int>::max();
1334                                for ( Type* ty : tty->types ) {
1335                                        count = -1;
1336                                        maybeAccept( ty, *visitor );
1337                                        if ( count != -1 && count < mincount ) mincount = count;
1338                                }
1339                                // xxx - maybe don't increment, tuple flattening doesn't necessarily specialize
1340                                count = mincount < std::numeric_limits<int>::max() ? mincount + 1: -1;
1341                        }
1342
1343                        int get_count() const { return count >= 0 ? count : 0; }
1344                private:
1345                        int count = -1;
1346                };
1347
1348                /// Counts the specializations in the types in a function parameter or return list
1349                int countSpecs( std::list<DeclarationWithType*>& dwts ) {
1350                        int k = 0;
1351                        for ( DeclarationWithType* dwt : dwts ) {
1352                                PassVisitor<CountSpecs> counter;
1353                                maybeAccept( dwt->get_type(), *counter.pass.visitor );
1354                                k += counter.pass.get_count();
1355                        }
1356                        return k;
1357                }
1358
1359                /// Calculates the inherent costs in a function declaration; varCost for the number of
1360                /// type variables and specCost for type assertions, as well as PolyType specializations
1361                /// in the parameter and return lists.
1362                Cost declCost( FunctionType* funcType ) {
1363                        Cost k = Cost::zero;
1364
1365                        // add cost of type variables
1366                        k.incVar( funcType->forall.size() );
1367
1368                        // subtract cost of type assertions
1369                        for ( TypeDecl* td : funcType->forall ) {
1370                                k.decSpec( td->assertions.size() );
1371                        }
1372
1373                        // count specialized polymorphic types in parameter/return lists
1374                        k.decSpec( countSpecs( funcType->parameters ) );
1375                        k.decSpec( countSpecs( funcType->returnVals ) );
1376
1377                        return k;
1378                }
1379        }
1380#endif
1381
1382        template<typename OutputIterator>
1383        void AlternativeFinder::Finder::validateFunctionAlternative( const Alternative &func, 
1384                        ArgPack& result, const std::vector<ArgPack>& results, OutputIterator out ) {
1385                ApplicationExpr *appExpr = new ApplicationExpr( func.expr );
1386                // sum cost and accumulate actuals
1387                std::list<Expression*>& args = appExpr->args;
1388                Cost cost = func.cost;
1389                const ArgPack* pack = &result;
1390                while ( pack->expr ) {
1391                        args.push_front( pack->expr );
1392                        cost += pack->cost;
1393                        pack = &results[pack->parent];
1394                }
1395                // build and validate new alternative
1396                Alternative newAlt( appExpr, result.env, cost );
1397                PRINT(
1398                        std::cerr << "instantiate function success: " << appExpr << std::endl;
1399                        std::cerr << "need assertions:" << std::endl;
1400                        printAssertionSet( result.need, std::cerr, 8 );
1401                )
1402                inferParameters( result.need, result.have, std::move(newAlt), result.openVars, out );
1403        }
1404
1405        template<typename OutputIterator>
1406        void AlternativeFinder::Finder::makeFunctionAlternatives( const Alternative &func,
1407                        FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) {
1408                OpenVarSet funcOpenVars;
1409                AssertionSet funcNeed, funcHave;
1410                TypeEnvironment funcEnv( func.env );
1411                makeUnifiableVars( funcType, funcOpenVars, funcNeed );
1412                // add all type variables as open variables now so that those not used in the parameter
1413                // list are still considered open.
1414                funcEnv.add( funcType->forall );
1415
1416                if ( targetType && ! targetType->isVoid() && ! funcType->returnVals.empty() ) {
1417                        // attempt to narrow based on expected target type
1418                        Type * returnType = funcType->returnVals.front()->get_type();
1419                        if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars,
1420                                        indexer ) ) {
1421                                // unification failed, don't pursue this function alternative
1422                                return;
1423                        }
1424                }
1425
1426                // calculate declaration cost of function (+vars-spec)
1427#if !1
1428                Cost funcCost = declCost( funcType );
1429#else
1430                Cost funcCost = Cost::zero;
1431#endif
1432
1433                // iteratively build matches, one parameter at a time
1434                std::vector<ArgPack> results;
1435                results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars, funcCost } );
1436                std::size_t genStart = 0;
1437
1438                for ( DeclarationWithType* formal : funcType->parameters ) {
1439                        ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal );
1440                        if ( ! instantiateArgument(
1441                                        obj->type, obj->init, args, results, genStart, indexer ) )
1442                                return;
1443                }
1444
1445                if ( funcType->get_isVarArgs() ) {
1446                        // append any unused arguments to vararg pack
1447                        std::size_t genEnd;
1448                        do {
1449                                genEnd = results.size();
1450
1451                                // iterate results
1452                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
1453                                        auto nextArg = results[i].nextArg;
1454
1455                                        // use remainder of exploded tuple if present
1456                                        if ( results[i].hasExpl() ) {
1457                                                const ExplodedActual& expl = results[i].getExpl( args );
1458
1459                                                unsigned nextExpl = results[i].nextExpl + 1;
1460                                                if ( nextExpl == expl.exprs.size() ) {
1461                                                        nextExpl = 0;
1462                                                }
1463
1464                                                results.emplace_back(
1465                                                        i, expl.exprs[results[i].nextExpl], copy(results[i].env),
1466                                                        copy(results[i].need), copy(results[i].have),
1467                                                        copy(results[i].openVars), nextArg, 0, Cost::zero, nextExpl,
1468                                                        results[i].explAlt );
1469
1470                                                continue;
1471                                        }
1472
1473                                        // finish result when out of arguments
1474                                        if ( nextArg >= args.size() ) {
1475                                                validateFunctionAlternative( func, results[i], results, out );
1476
1477                                                continue;
1478                                        }
1479
1480                                        // add each possible next argument
1481                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
1482                                                const ExplodedActual& expl = args[nextArg][j];
1483
1484                                                // fresh copies of parent parameters for this iteration
1485                                                TypeEnvironment env = results[i].env;
1486                                                OpenVarSet openVars = results[i].openVars;
1487
1488                                                env.addActual( expl.env, openVars );
1489
1490                                                // skip empty tuple arguments by (near-)cloning parent into next gen
1491                                                if ( expl.exprs.empty() ) {
1492                                                        results.emplace_back(
1493                                                                results[i], move(env), copy(results[i].need),
1494                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
1495
1496                                                        continue;
1497                                                }
1498
1499                                                // add new result
1500                                                results.emplace_back(
1501                                                        i, expl.exprs.front(), move(env), copy(results[i].need),
1502                                                        copy(results[i].have), move(openVars), nextArg + 1, 0,
1503                                                        expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
1504                                        }
1505                                }
1506
1507                                genStart = genEnd;
1508                        } while ( genEnd != results.size() );
1509                } else {
1510                        // filter out results that don't use all the arguments
1511                        for ( std::size_t i = genStart; i < results.size(); ++i ) {
1512                                ArgPack& result = results[i];
1513                                if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
1514                                        validateFunctionAlternative( func, result, results, out );
1515                                }
1516                        }
1517                }
1518        }
1519
1520        void AlternativeFinder::Finder::postvisit( UntypedExpr *untypedExpr ) {
1521                AlternativeFinder funcFinder( indexer, env );
1522                funcFinder.findWithAdjustment( untypedExpr->function );
1523                // if there are no function alternatives, then proceeding is a waste of time.
1524                // xxx - findWithAdjustment throws, so this check and others like it shouldn't be necessary.
1525                if ( funcFinder.alternatives.empty() ) return;
1526
1527                std::vector< AlternativeFinder > argAlternatives;
1528                altFinder.findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(),
1529                        back_inserter( argAlternatives ) );
1530
1531                // take care of possible tuple assignments
1532                // if not tuple assignment, assignment is taken care of as a normal function call
1533                Tuples::handleTupleAssignment( altFinder, untypedExpr, argAlternatives );
1534
1535                // find function operators
1536                static auto *opExpr = new_static_root<NameExpr>( "?()" );
1537                AlternativeFinder funcOpFinder( indexer, env );
1538                // it's ok if there aren't any defined function ops
1539                funcOpFinder.maybeFind( opExpr );
1540                PRINT(
1541                        std::cerr << "known function ops:" << std::endl;
1542                        printAlts( funcOpFinder.alternatives, std::cerr, 1 );
1543                )
1544
1545                // pre-explode arguments
1546                ExplodedArgs argExpansions;
1547                argExpansions.reserve( argAlternatives.size() );
1548
1549                for ( const AlternativeFinder& arg : argAlternatives ) {
1550                        argExpansions.emplace_back();
1551                        auto& argE = argExpansions.back();
1552                        // argE.reserve( arg.alternatives.size() );
1553
1554                        for ( const Alternative& actual : arg ) {
1555                                argE.emplace_back( actual, indexer );
1556                        }
1557                }
1558
1559                AltList candidates;
1560                SemanticErrorException errors;
1561                for ( AltList::iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
1562                        try {
1563                                PRINT(
1564                                        std::cerr << "working on alternative: " << std::endl;
1565                                        func->print( std::cerr, 8 );
1566                                )
1567                                // check if the type is pointer to function
1568                                if ( PointerType *pointer = dynamic_cast< PointerType* >( func->expr->get_result()->stripReferences() ) ) {
1569                                        if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
1570                                                Alternative newFunc( *func );
1571                                                referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1572                                                makeFunctionAlternatives( newFunc, function, argExpansions,
1573                                                        std::back_inserter( candidates ) );
1574                                        }
1575                                } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->result->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
1576                                        if ( ClassRef eqvClass = func->env.lookup( typeInst->name ) ) {
1577                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.get_bound().type ) ) {
1578                                                        Alternative newFunc( *func );
1579                                                        referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1580                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
1581                                                                std::back_inserter( candidates ) );
1582                                                } // if
1583                                        } // if
1584                                }
1585                        } catch ( SemanticErrorException &e ) {
1586                                errors.append( e );
1587                        }
1588                } // for
1589
1590                // try each function operator ?() with each function alternative
1591                if ( ! funcOpFinder.alternatives.empty() ) {
1592                        // add exploded function alternatives to front of argument list
1593                        std::vector<ExplodedActual> funcE;
1594                        funcE.reserve( funcFinder.alternatives.size() );
1595                        for ( const Alternative& actual : funcFinder ) {
1596                                funcE.emplace_back( actual, indexer );
1597                        }
1598                        argExpansions.insert( argExpansions.begin(), move(funcE) );
1599
1600                        for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
1601                                        funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
1602                                try {
1603                                        // check if type is a pointer to function
1604                                        if ( PointerType* pointer = dynamic_cast<PointerType*>(
1605                                                        funcOp->expr->get_result()->stripReferences() ) ) {
1606                                                if ( FunctionType* function =
1607                                                                dynamic_cast<FunctionType*>( pointer->get_base() ) ) {
1608                                                        Alternative newFunc( *funcOp );
1609                                                        referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1610                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
1611                                                                std::back_inserter( candidates ) );
1612                                                }
1613                                        }
1614                                } catch ( SemanticErrorException &e ) {
1615                                        errors.append( e );
1616                                }
1617                        }
1618                }
1619
1620                // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
1621                if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
1622
1623                // compute conversionsion costs
1624                for ( Alternative& withFunc : candidates ) {
1625                        Cost cvtCost = computeApplicationConversionCost( withFunc, indexer );
1626
1627                        PRINT(
1628                                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr );
1629                                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
1630                                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
1631                                std::cerr << "Case +++++++++++++ " << appExpr->get_function() << std::endl;
1632                                std::cerr << "formals are:" << std::endl;
1633                                printAll( function->get_parameters(), std::cerr, 8 );
1634                                std::cerr << "actuals are:" << std::endl;
1635                                printAll( appExpr->get_args(), std::cerr, 8 );
1636                                std::cerr << "bindings are:" << std::endl;
1637                                withFunc.env.print( std::cerr, 8 );
1638                                std::cerr << "cost of conversion is:" << cvtCost << std::endl;
1639                        )
1640                        if ( cvtCost != Cost::infinity ) {
1641                                withFunc.cvtCost = cvtCost;
1642                                alternatives.push_back( withFunc );
1643                        } // if
1644                } // for
1645
1646                candidates = move(alternatives);
1647
1648                // use a new list so that alternatives are not examined by addAnonConversions twice.
1649                AltList winners;
1650                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) );
1651
1652                // function may return struct or union value, in which case we need to add alternatives
1653                // for implicitconversions to each of the anonymous members, must happen after findMinCost
1654                // since anon conversions are never the cheapest expression
1655                for ( const Alternative & alt : winners ) {
1656                        addAnonConversions( alt );
1657                }
1658                spliceBegin( alternatives, winners );
1659
1660                if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
1661                        // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
1662                        // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
1663                        //   forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
1664                        //   const char * x = "hello world";
1665                        //   unsigned char ch = x[0];
1666                        // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
1667                        // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
1668                        // fix this issue in a more robust way.
1669                        targetType = nullptr;
1670                        postvisit( untypedExpr );
1671                }
1672        }
1673
1674        bool isLvalue( Expression *expr ) {
1675                // xxx - recurse into tuples?
1676                return expr->result && ( expr->get_result()->get_lvalue() || dynamic_cast< ReferenceType * >( expr->get_result() ) );
1677        }
1678
1679        void AlternativeFinder::Finder::postvisit( AddressExpr *addressExpr ) {
1680                AlternativeFinder finder( indexer, env );
1681                finder.find( addressExpr->get_arg() );
1682                for ( Alternative& alt : finder.alternatives ) {
1683                        if ( isLvalue( alt.expr ) ) {
1684                                alternatives.push_back(
1685                                        Alternative{ new AddressExpr( alt.expr ), alt.env, alt.cost } );
1686                        } // if
1687                } // for
1688        }
1689
1690        void AlternativeFinder::Finder::postvisit( LabelAddressExpr * expr ) {
1691                alternatives.push_back( Alternative{ expr, env, Cost::zero } );
1692        }
1693
1694        Expression * restructureCast( Expression * argExpr, Type * toType, bool isGenerated ) {
1695                if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() && ! dynamic_cast<ReferenceType *>( toType ) ) {
1696                        // Argument expression is a tuple and the target type is not void and not a reference type.
1697                        // Cast each member of the tuple to its corresponding target type, producing the tuple of those
1698                        // cast expressions. If there are more components of the tuple than components in the target type,
1699                        // then excess components do not come out in the result expression (but UniqueExprs ensure that
1700                        // side effects will still be done).
1701                        if ( Tuples::maybeImpureIgnoreUnique( argExpr ) ) {
1702                                // expressions which may contain side effects require a single unique instance of the expression.
1703                                argExpr = new UniqueExpr( argExpr );
1704                        }
1705                        std::list< Expression * > componentExprs;
1706                        for ( unsigned int i = 0; i < toType->size(); i++ ) {
1707                                // cast each component
1708                                TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
1709                                componentExprs.push_back( restructureCast( idx, toType->getComponent( i ), isGenerated ) );
1710                        }
1711                        assert( componentExprs.size() > 0 );
1712                        // produce the tuple of casts
1713                        return new TupleExpr( componentExprs );
1714                } else {
1715                        // handle normally
1716                        CastExpr * ret = new CastExpr( argExpr, toType->clone() );
1717                        ret->isGenerated = isGenerated;
1718                        return ret;
1719                }
1720        }
1721
1722        void AlternativeFinder::Finder::postvisit( CastExpr *castExpr ) {
1723                Type *& toType = castExpr->get_result();
1724                assert( toType );
1725                toType = resolveTypeof( toType, indexer );
1726                SymTab::validateType( toType, &indexer );
1727                adjustExprType( toType, env, indexer );
1728
1729                AlternativeFinder finder( indexer, env );
1730                finder.targetType = toType;
1731                finder.findWithAdjustment( castExpr->arg );
1732
1733                AltList candidates;
1734                for ( Alternative & alt : finder.alternatives ) {
1735                        AssertionSet needAssertions, haveAssertions;
1736                        OpenVarSet openVars;
1737
1738                        alt.env.extractOpenVars( openVars );
1739
1740                        // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1741                        // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1742                        // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1743                        // to.
1744                        int discardedValues = alt.expr->result->size() - castExpr->result->size();
1745                        if ( discardedValues < 0 ) continue;
1746                        // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1747                        // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1748                        // unification run for side-effects
1749                        unify( castExpr->result, alt.expr->result, alt.env, needAssertions,
1750                                haveAssertions, openVars, indexer );
1751                        Cost thisCost = castCost( alt.expr->result, castExpr->result, indexer,
1752                                alt.env );
1753                        PRINT(
1754                                std::cerr << "working on cast with result: " << castExpr->result << std::endl;
1755                                std::cerr << "and expr type: " << alt.expr->result << std::endl;
1756                                std::cerr << "env: " << alt.env << std::endl;
1757                        )
1758                        if ( thisCost != Cost::infinity ) {
1759                                PRINT(
1760                                        std::cerr << "has finite cost." << std::endl;
1761                                )
1762                                // count one safe conversion for each value that is thrown away
1763                                thisCost.incSafe( discardedValues );
1764                                Alternative newAlt( restructureCast( alt.expr->clone(), toType, castExpr->isGenerated ), alt.env,
1765                                        alt.cost, thisCost );
1766                                inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars,
1767                                        back_inserter( candidates ) );
1768                        } // if
1769                } // for
1770
1771                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1772                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1773                // selects first based on argument cost, then on conversion cost.
1774                AltList minArgCost;
1775                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1776                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1777        }
1778
1779        void AlternativeFinder::Finder::postvisit( VirtualCastExpr * castExpr ) {
1780                assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." );
1781                AlternativeFinder finder( indexer, env );
1782                // don't prune here, since it's guaranteed all alternatives will have the same type
1783                finder.findWithoutPrune( castExpr->get_arg() );
1784                for ( Alternative & alt : finder.alternatives ) {
1785                        alternatives.push_back( Alternative(
1786                                new VirtualCastExpr( alt.expr, castExpr->get_result()->clone() ),
1787                                alt.env, alt.cost ) );
1788                }
1789        }
1790
1791        namespace {
1792                /// Gets name from untyped member expression (member must be NameExpr)
1793                const std::string& get_member_name( UntypedMemberExpr *memberExpr ) {
1794                        NameExpr * nameExpr = dynamic_cast< NameExpr * >( memberExpr->get_member() );
1795                        assert( nameExpr );
1796                        return nameExpr->get_name();
1797                }
1798        }
1799
1800        void AlternativeFinder::Finder::postvisit( UntypedMemberExpr *memberExpr ) {
1801                AlternativeFinder funcFinder( indexer, env );
1802                funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
1803                for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
1804                        // 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
1805                        Cost cost = agg->cost;
1806                        Expression * aggrExpr = agg->expr->clone();
1807                        referenceToRvalueConversion( aggrExpr, cost );
1808
1809                        // find member of the given type
1810                        if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
1811                                addAggMembers( structInst, aggrExpr, cost, agg->env, get_member_name(memberExpr) );
1812                        } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
1813                                addAggMembers( unionInst, aggrExpr, cost, agg->env, get_member_name(memberExpr) );
1814                        } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
1815                                addTupleMembers( tupleType, aggrExpr, cost, agg->env, memberExpr->get_member() );
1816                        } // if
1817                } // for
1818        }
1819
1820        void AlternativeFinder::Finder::postvisit( MemberExpr *memberExpr ) {
1821                alternatives.push_back( Alternative( memberExpr, env, Cost::zero ) );
1822        }
1823
1824        void AlternativeFinder::Finder::postvisit( NameExpr *nameExpr ) {
1825                std::list< SymTab::Indexer::IdData > declList;
1826                indexer.lookupId( nameExpr->name, declList );
1827                PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )
1828                for ( auto & data : declList ) {
1829                        Cost cost = Cost::zero;
1830                        Expression * newExpr = data.combine( cost );
1831
1832                        // addAnonAlternatives uses vector::push_back, which invalidates references to existing elements, so
1833                        // can't construct in place and use vector::back
1834                        Alternative newAlt( newExpr, env, Cost::zero, cost );
1835                        PRINT(
1836                                std::cerr << "decl is ";
1837                                data.id->print( std::cerr );
1838                                std::cerr << std::endl;
1839                                std::cerr << "newExpr is ";
1840                                newExpr->print( std::cerr );
1841                                std::cerr << std::endl;
1842                        )
1843                        renameTypes( newAlt.expr );
1844                        addAnonConversions( newAlt ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
1845                        alternatives.push_back( std::move(newAlt) );
1846                } // for
1847        }
1848
1849        void AlternativeFinder::Finder::postvisit( VariableExpr *variableExpr ) {
1850                // not sufficient to clone here, because variable's type may have changed
1851                // since the VariableExpr was originally created.
1852                alternatives.push_back( Alternative( new VariableExpr( variableExpr->var ), env, Cost::zero ) );
1853        }
1854
1855        void AlternativeFinder::Finder::postvisit( ConstantExpr *constantExpr ) {
1856                alternatives.push_back( Alternative( constantExpr, env, Cost::zero ) );
1857        }
1858
1859        void AlternativeFinder::Finder::postvisit( SizeofExpr *sizeofExpr ) {
1860                if ( sizeofExpr->get_isType() ) {
1861                        Type * newType = sizeofExpr->get_type()->clone();
1862                        alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1863                } else {
1864                        // find all alternatives for the argument to sizeof
1865                        AlternativeFinder finder( indexer, env );
1866                        finder.find( sizeofExpr->get_expr() );
1867                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1868                        AltList winners;
1869                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1870                        if ( winners.size() != 1 ) {
1871                                SemanticError( sizeofExpr->get_expr(), "Ambiguous expression in sizeof operand: " );
1872                        } // if
1873                        // return the lowest cost alternative for the argument
1874                        Alternative &choice = winners.front();
1875                        referenceToRvalueConversion( choice.expr, choice.cost );
1876                        alternatives.push_back( Alternative( new SizeofExpr( choice.expr ), choice.env, Cost::zero ) );
1877                } // if
1878        }
1879
1880        void AlternativeFinder::Finder::postvisit( AlignofExpr *alignofExpr ) {
1881                if ( alignofExpr->get_isType() ) {
1882                        Type * newType = alignofExpr->get_type()->clone();
1883                        alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1884                } else {
1885                        // find all alternatives for the argument to sizeof
1886                        AlternativeFinder finder( indexer, env );
1887                        finder.find( alignofExpr->get_expr() );
1888                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1889                        AltList winners;
1890                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1891                        if ( winners.size() != 1 ) {
1892                                SemanticError( alignofExpr->get_expr(), "Ambiguous expression in alignof operand: " );
1893                        } // if
1894                        // return the lowest cost alternative for the argument
1895                        Alternative &choice = winners.front();
1896                        referenceToRvalueConversion( choice.expr, choice.cost );
1897                        alternatives.push_back( Alternative( new AlignofExpr( choice.expr ), choice.env, Cost::zero ) );
1898                } // if
1899        }
1900
1901        template< typename StructOrUnionType >
1902        void AlternativeFinder::Finder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
1903                std::list< Declaration* > members;
1904                aggInst->lookup( name, members );
1905                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
1906                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
1907                                alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
1908                                renameTypes( alternatives.back().expr );
1909                        } else {
1910                                assert( false );
1911                        }
1912                }
1913        }
1914
1915        void AlternativeFinder::Finder::postvisit( UntypedOffsetofExpr *offsetofExpr ) {
1916                AlternativeFinder funcFinder( indexer, env );
1917                // xxx - resolveTypeof?
1918                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
1919                        addOffsetof( structInst, offsetofExpr->member );
1920                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
1921                        addOffsetof( unionInst, offsetofExpr->member );
1922                }
1923        }
1924
1925        void AlternativeFinder::Finder::postvisit( OffsetofExpr *offsetofExpr ) {
1926                alternatives.push_back( Alternative( offsetofExpr, env, Cost::zero ) );
1927        }
1928
1929        void AlternativeFinder::Finder::postvisit( OffsetPackExpr *offsetPackExpr ) {
1930                alternatives.push_back( Alternative( offsetPackExpr, env, Cost::zero ) );
1931        }
1932
1933        namespace {
1934                void resolveAttr( SymTab::Indexer::IdData data, FunctionType *function, Type *argType, const TypeEnvironment &env, AlternativeFinder & finder ) {
1935                        // assume no polymorphism
1936                        // assume no implicit conversions
1937                        assert( function->get_parameters().size() == 1 );
1938                        PRINT(
1939                                std::cerr << "resolvAttr: funcDecl is ";
1940                                data.id->print( std::cerr );
1941                                std::cerr << " argType is ";
1942                                argType->print( std::cerr );
1943                                std::cerr << std::endl;
1944                        )
1945                        const SymTab::Indexer & indexer = finder.get_indexer();
1946                        AltList & alternatives = finder.get_alternatives();
1947                        if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1948                                Cost cost = Cost::zero;
1949                                Expression * newExpr = data.combine( cost );
1950                                alternatives.push_back( Alternative( new AttrExpr( newExpr, argType->clone() ), env, Cost::zero, cost ) );
1951                                for ( DeclarationWithType * retVal : function->returnVals ) {
1952                                        alternatives.back().expr->result = retVal->get_type()->clone();
1953                                } // for
1954                        } // if
1955                }
1956        }
1957
1958        void AlternativeFinder::Finder::postvisit( AttrExpr *attrExpr ) {
1959                // assume no 'pointer-to-attribute'
1960                NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1961                assert( nameExpr );
1962                std::list< SymTab::Indexer::IdData > attrList;
1963                indexer.lookupId( nameExpr->get_name(), attrList );
1964                if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1965                        for ( auto & data : attrList ) {
1966                                DeclarationWithType * id = data.id;
1967                                // check if the type is function
1968                                if ( FunctionType *function = dynamic_cast< FunctionType* >( id->get_type() ) ) {
1969                                        // assume exactly one parameter
1970                                        if ( function->get_parameters().size() == 1 ) {
1971                                                if ( attrExpr->get_isType() ) {
1972                                                        resolveAttr( data, function, attrExpr->get_type(), env, altFinder);
1973                                                } else {
1974                                                        AlternativeFinder finder( indexer, env );
1975                                                        finder.find( attrExpr->get_expr() );
1976                                                        for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1977                                                                if ( choice->expr->get_result()->size() == 1 ) {
1978                                                                        resolveAttr(data, function, choice->expr->get_result(), choice->env, altFinder );
1979                                                                } // fi
1980                                                        } // for
1981                                                } // if
1982                                        } // if
1983                                } // if
1984                        } // for
1985                } else {
1986                        for ( auto & data : attrList ) {
1987                                Cost cost = Cost::zero;
1988                                Expression * newExpr = data.combine( cost );
1989                                alternatives.push_back( Alternative( newExpr, env, Cost::zero, cost ) );
1990                                renameTypes( alternatives.back().expr );
1991                        } // for
1992                } // if
1993        }
1994
1995        void AlternativeFinder::Finder::postvisit( LogicalExpr *logicalExpr ) {
1996                AlternativeFinder firstFinder( indexer, env );
1997                firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1998                if ( firstFinder.alternatives.empty() ) return;
1999                AlternativeFinder secondFinder( indexer, env );
2000                secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
2001                if ( secondFinder.alternatives.empty() ) return;
2002                for ( const Alternative & first : firstFinder.alternatives ) {
2003                        for ( const Alternative & second : secondFinder.alternatives ) {
2004                                TypeEnvironment compositeEnv;
2005                                compositeEnv.simpleCombine( first.env );
2006                                compositeEnv.simpleCombine( second.env );
2007
2008                                LogicalExpr *newExpr = new LogicalExpr( first.expr, second.expr, logicalExpr->get_isAnd() );
2009                                alternatives.push_back( Alternative( newExpr, compositeEnv, first.cost + second.cost ) );
2010                        }
2011                }
2012        }
2013
2014        void AlternativeFinder::Finder::postvisit( ConditionalExpr *conditionalExpr ) {
2015                // find alternatives for condition
2016                AlternativeFinder firstFinder( indexer, env );
2017                firstFinder.findWithAdjustment( conditionalExpr->arg1 );
2018                if ( firstFinder.alternatives.empty() ) return;
2019                // find alternatives for true expression
2020                AlternativeFinder secondFinder( indexer, env );
2021                secondFinder.findWithAdjustment( conditionalExpr->arg2 );
2022                if ( secondFinder.alternatives.empty() ) return;
2023                // find alterantives for false expression
2024                AlternativeFinder thirdFinder( indexer, env );
2025                thirdFinder.findWithAdjustment( conditionalExpr->arg3 );
2026                if ( thirdFinder.alternatives.empty() ) return;
2027                for ( const Alternative & first : firstFinder.alternatives ) {
2028                        for ( const Alternative & second : secondFinder.alternatives ) {
2029                                for ( const Alternative & third : thirdFinder.alternatives ) {
2030                                        TypeEnvironment compositeEnv;
2031                                        compositeEnv.simpleCombine( first.env );
2032                                        compositeEnv.simpleCombine( second.env );
2033                                        compositeEnv.simpleCombine( third.env );
2034
2035                                        // unify true and false types, then infer parameters to produce new alternatives
2036                                        OpenVarSet openVars;
2037                                        AssertionSet needAssertions, haveAssertions;
2038                                        Alternative newAlt( 0, compositeEnv, first.cost + second.cost + third.cost );
2039                                        Type* commonType = nullptr;
2040                                        if ( unify( second.expr->result, third.expr->result, newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
2041                                                ConditionalExpr *newExpr = new ConditionalExpr( first.expr, second.expr, third.expr );
2042                                                newExpr->result = commonType ? commonType : second.expr->result->clone();
2043                                                // convert both options to the conditional result type
2044                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env );
2045                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
2046                                                newAlt.expr = newExpr;
2047                                                inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars, back_inserter( alternatives ) );
2048                                        } // if
2049                                } // for
2050                        } // for
2051                } // for
2052        }
2053
2054        void AlternativeFinder::Finder::postvisit( CommaExpr *commaExpr ) {
2055                TypeEnvironment newEnv( env );
2056                Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
2057                AlternativeFinder secondFinder( indexer, newEnv );
2058                secondFinder.findWithAdjustment( commaExpr->get_arg2() );
2059                for ( const Alternative & alt : secondFinder.alternatives ) {
2060                        alternatives.push_back( Alternative( new CommaExpr( newFirstArg, alt.expr ), alt.env, alt.cost ) );
2061                } // for
2062        }
2063
2064        void AlternativeFinder::Finder::postvisit( RangeExpr * rangeExpr ) {
2065                // resolve low and high, accept alternatives whose low and high types unify
2066                AlternativeFinder firstFinder( indexer, env );
2067                firstFinder.findWithAdjustment( rangeExpr->low );
2068                if ( firstFinder.alternatives.empty() ) return;
2069                AlternativeFinder secondFinder( indexer, env );
2070                secondFinder.findWithAdjustment( rangeExpr->high );
2071                if ( secondFinder.alternatives.empty() ) return;
2072                for ( const Alternative & first : firstFinder.alternatives ) {
2073                        for ( const Alternative & second : secondFinder.alternatives ) {
2074                                TypeEnvironment compositeEnv;
2075                                compositeEnv.simpleCombine( first.env );
2076                                compositeEnv.simpleCombine( second.env );
2077                                OpenVarSet openVars;
2078                                AssertionSet needAssertions, haveAssertions;
2079                                Alternative newAlt( 0, compositeEnv, first.cost + second.cost );
2080                                Type* commonType = nullptr;
2081                                if ( unify( first.expr->result, second.expr->result, newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
2082                                        RangeExpr * newExpr = new RangeExpr( first.expr, second.expr );
2083                                        newExpr->result = commonType ? commonType : first.expr->result->clone();
2084                                        newAlt.expr = newExpr;
2085                                        inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars, back_inserter( alternatives ) );
2086                                } // if
2087                        } // for
2088                } // for
2089        }
2090
2091        void AlternativeFinder::Finder::postvisit( UntypedTupleExpr *tupleExpr ) {
2092                std::vector< AlternativeFinder > subExprAlternatives;
2093                altFinder.findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(),
2094                        back_inserter( subExprAlternatives ) );
2095                std::vector< AltList > possibilities;
2096                combos( subExprAlternatives.begin(), subExprAlternatives.end(),
2097                        back_inserter( possibilities ) );
2098                for ( const AltList& alts : possibilities ) {
2099                        std::list< Expression * > exprs;
2100                        makeExprList( alts, exprs );
2101
2102                        TypeEnvironment compositeEnv;
2103                        simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
2104                        alternatives.push_back(
2105                                Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } );
2106                } // for
2107        }
2108
2109        void AlternativeFinder::Finder::postvisit( TupleExpr *tupleExpr ) {
2110                alternatives.push_back( Alternative( tupleExpr, env, Cost::zero ) );
2111        }
2112
2113        void AlternativeFinder::Finder::postvisit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
2114                alternatives.push_back( Alternative( impCpCtorExpr, env, Cost::zero ) );
2115        }
2116
2117        void AlternativeFinder::Finder::postvisit( ConstructorExpr * ctorExpr ) {
2118                AlternativeFinder finder( indexer, env );
2119                // don't prune here, since it's guaranteed all alternatives will have the same type
2120                // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
2121                finder.findWithoutPrune( ctorExpr->get_callExpr() );
2122                for ( Alternative & alt : finder.alternatives ) {
2123                        alternatives.push_back( Alternative( new ConstructorExpr( alt.expr ), alt.env, alt.cost ) );
2124                }
2125        }
2126
2127        void AlternativeFinder::Finder::postvisit( TupleIndexExpr *tupleExpr ) {
2128                alternatives.push_back( Alternative( tupleExpr, env, Cost::zero ) );
2129        }
2130
2131        void AlternativeFinder::Finder::postvisit( TupleAssignExpr *tupleAssignExpr ) {
2132                alternatives.push_back( Alternative( tupleAssignExpr, env, Cost::zero ) );
2133        }
2134
2135        void AlternativeFinder::Finder::postvisit( UniqueExpr *unqExpr ) {
2136                AlternativeFinder finder( indexer, env );
2137                finder.findWithAdjustment( unqExpr->get_expr() );
2138                for ( Alternative & alt : finder.alternatives ) {
2139                        // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
2140                        UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr, unqExpr->get_id() );
2141                        alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
2142                }
2143        }
2144
2145        void AlternativeFinder::Finder::postvisit( StmtExpr *stmtExpr ) {
2146                StmtExpr * newStmtExpr = stmtExpr->clone();
2147                ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
2148                // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
2149                alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
2150        }
2151
2152        void AlternativeFinder::Finder::postvisit( UntypedInitExpr *initExpr ) {
2153                // handle each option like a cast
2154                AltList candidates;
2155                PRINT(
2156                        std::cerr << "untyped init expr: " << initExpr << std::endl;
2157                )
2158                // O(N^2) checks of d-types with e-types
2159                for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
2160                        Type * toType = resolveTypeof( initAlt.type->clone(), indexer );
2161                        SymTab::validateType( toType, &indexer );
2162                        adjustExprType( toType, env, indexer );
2163                        // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
2164                        // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
2165                        // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
2166                        AlternativeFinder finder( indexer, env );
2167                        finder.targetType = toType;
2168                        finder.findWithAdjustment( initExpr->expr );
2169                        for ( Alternative & alt : finder.get_alternatives() ) {
2170                                TypeEnvironment newEnv( alt.env );
2171                                AssertionSet needAssertions, haveAssertions;
2172                                OpenVarSet openVars;  // find things in env that don't have a "representative type" and claim those are open vars?
2173                                PRINT(
2174                                        std::cerr << "  @ " << toType << " " << initAlt.designation << std::endl;
2175                                )
2176                                // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
2177                                // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
2178                                // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
2179                                // to.
2180                                int discardedValues = alt.expr->result->size() - toType->size();
2181                                if ( discardedValues < 0 ) continue;
2182                                // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
2183                                // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
2184                                // unification run for side-effects
2185                                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??
2186
2187                                Cost thisCost = castCost( alt.expr->result, toType, indexer, newEnv );
2188                                if ( thisCost != Cost::infinity ) {
2189                                        // count one safe conversion for each value that is thrown away
2190                                        thisCost.incSafe( discardedValues );
2191                                        Alternative newAlt( new InitExpr( restructureCast( alt.expr, toType, true ), initAlt.designation ), newEnv, alt.cost, thisCost );
2192                                        inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars, back_inserter( candidates ) );
2193                                }
2194                        }
2195                }
2196
2197                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
2198                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
2199                // selects first based on argument cost, then on conversion cost.
2200                AltList minArgCost;
2201                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
2202                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
2203        }
2204
2205        void AlternativeFinder::Finder::postvisit( InitExpr * ) {
2206                assertf( false, "AlternativeFinder should never see a resolved InitExpr." );
2207        }
2208
2209        void AlternativeFinder::Finder::postvisit( DeletedExpr * ) {
2210                assertf( false, "AlternativeFinder should never see a DeletedExpr." );
2211        }
2212
2213        void AlternativeFinder::Finder::postvisit( GenericExpr * ) {
2214                assertf( false, "_Generic is not yet supported." );
2215        }
2216} // namespace ResolvExpr
2217
2218// Local Variables: //
2219// tab-width: 4 //
2220// mode: c++ //
2221// compile-command: "make install" //
2222// End: //
Note: See TracBrowser for help on using the repository browser.