source: src/ResolvExpr/AlternativeFinder.cc @ fbecee5

aaron-thesisarm-ehcleanup-dtorsdeferred_resnjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprno_listpersistent-indexer
Last change on this file since fbecee5 was fbecee5, checked in by Aaron Moss <a3moss@…>, 3 years ago

rational.cfa passes deferred resolution pass now

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