source: src/ResolvExpr/AlternativeFinder.cc @ f89a111

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

Persistent-array environment compiles

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