source: src/ResolvExpr/AlternativeFinder.cc @ 0b00df0

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

First draft of deferred expression resolution; DOES NOT BUILD

  • Property mode set to 100644
File size: 76.2 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                /// Sets up parameter inference for an output alternative
117                template< typename OutputIterator >
118                void inferParameters( Alternative &newAlt, 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->inferParams.begin(); assert != appExpr->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->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        /// Unique identifier for matching expression resolutions to their requesting expression
611        UniqueId globalResnSlot = 0;
612
613        template< typename OutputIterator >
614        void AlternativeFinder::Finder::inferParameters( Alternative &newAlt, OutputIterator out ) {
615                // SymTab::Indexer decls( indexer );
616                // addToIndexer( have, decls );
617                // AssertionSet newNeed;
618                // PRINT(
619                //      std::cerr << "env is: " << std::endl;
620                //      newAlt.env.print( std::cerr, 0 );
621                //      std::cerr << std::endl;
622                // )
623
624                // inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, 0, indexer, out );
625
626                // Set need bindings for any unbound assertions
627                UniqueId crntResnSlot = 0;  // matching ID for this expression's assertions
628                for ( auto& assn : newAlt.need ) {
629                        // skip already-matched assertions
630                        if ( assn.info.resnSlot != 0 ) continue;
631                        // assign slot for expression if needed
632                        if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; }
633                        // fix slot to assertion
634                        assn.info.resnSlot = crntResnSlot;
635                }
636                // pair slot to expression
637                if ( crntResnSlot != 0 ) { newAlt.expr->resnSlots.push_back( crntResnSlot ); }
638
639                // add to output list, assertion resolution is deferred
640                *out++ = newAlt;
641        }
642
643        /// Gets a default value from an initializer, nullptr if not present
644        ConstantExpr* getDefaultValue( Initializer* init ) {
645                if ( SingleInit* si = dynamic_cast<SingleInit*>( init ) ) {
646                        if ( CastExpr* ce = dynamic_cast<CastExpr*>( si->value ) ) {
647                                return dynamic_cast<ConstantExpr*>( ce->arg );
648                        } else {
649                                return dynamic_cast<ConstantExpr*>( si->value );
650                        }
651                }
652                return nullptr;
653        }
654
655        /// State to iteratively build a match of parameter expressions to arguments
656        struct ArgPack {
657                std::size_t parent;                ///< Index of parent pack
658                std::unique_ptr<Expression> expr;  ///< The argument stored here
659                Cost cost;                         ///< The cost of this argument
660                TypeEnvironment env;               ///< Environment for this pack
661                AssertionSet need;                 ///< Assertions outstanding for this pack
662                AssertionSet have;                 ///< Assertions found for this pack
663                OpenVarSet openVars;               ///< Open variables for this pack
664                unsigned nextArg;                  ///< Index of next argument in arguments list
665                unsigned tupleStart;               ///< Number of tuples that start at this index
666                unsigned nextExpl;                 ///< Index of next exploded element
667                unsigned explAlt;                  ///< Index of alternative for nextExpl > 0
668
669                ArgPack()
670                        : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0),
671                          tupleStart(0), nextExpl(0), explAlt(0) {}
672
673                ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
674                                const OpenVarSet& openVars)
675                        : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have),
676                          openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
677
678                ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need,
679                                AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg,
680                                unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0,
681                                unsigned explAlt = 0 )
682                        : parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)),
683                          have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart),
684                          nextExpl(nextExpl), explAlt(explAlt) {}
685
686                ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have,
687                                OpenVarSet&& openVars, unsigned nextArg, Cost added )
688                        : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), cost(o.cost + added),
689                          env(move(env)), need(move(need)), have(move(have)), openVars(move(openVars)),
690                          nextArg(nextArg), tupleStart(o.tupleStart), nextExpl(0), explAlt(0) {}
691
692                /// true iff this pack is in the middle of an exploded argument
693                bool hasExpl() const { return nextExpl > 0; }
694
695                /// Gets the list of exploded alternatives for this pack
696                const ExplodedActual& getExpl( const ExplodedArgs& args ) const {
697                        return args[nextArg-1][explAlt];
698                }
699
700                /// Ends a tuple expression, consolidating the appropriate actuals
701                void endTuple( const std::vector<ArgPack>& packs ) {
702                        // add all expressions in tuple to list, summing cost
703                        std::list<Expression*> exprs;
704                        const ArgPack* pack = this;
705                        if ( expr ) { exprs.push_front( expr.release() ); }
706                        while ( pack->tupleStart == 0 ) {
707                                pack = &packs[pack->parent];
708                                exprs.push_front( pack->expr->clone() );
709                                cost += pack->cost;
710                        }
711                        // reset pack to appropriate tuple
712                        expr.reset( new TupleExpr( exprs ) );
713                        tupleStart = pack->tupleStart - 1;
714                        parent = pack->parent;
715                }
716        };
717
718        /// Instantiates an argument to match a formal, returns false if no results left
719        bool instantiateArgument( Type* formalType, Initializer* initializer,
720                        const ExplodedArgs& args, std::vector<ArgPack>& results, std::size_t& genStart,
721                        const SymTab::Indexer& indexer, unsigned nTuples = 0 ) {
722                if ( TupleType * tupleType = dynamic_cast<TupleType*>( formalType ) ) {
723                        // formalType is a TupleType - group actuals into a TupleExpr
724                        ++nTuples;
725                        for ( Type* type : *tupleType ) {
726                                // xxx - dropping initializer changes behaviour from previous, but seems correct
727                                // ^^^ need to handle the case where a tuple has a default argument
728                                if ( ! instantiateArgument(
729                                                type, nullptr, args, results, genStart, indexer, nTuples ) )
730                                        return false;
731                                nTuples = 0;
732                        }
733                        // re-consititute tuples for final generation
734                        for ( auto i = genStart; i < results.size(); ++i ) {
735                                results[i].endTuple( results );
736                        }
737                        return true;
738                } else if ( TypeInstType * ttype = Tuples::isTtype( formalType ) ) {
739                        // formalType is a ttype, consumes all remaining arguments
740                        // xxx - mixing default arguments with variadic??
741
742                        // completed tuples; will be spliced to end of results to finish
743                        std::vector<ArgPack> finalResults{};
744
745                        // iterate until all results completed
746                        std::size_t genEnd;
747                        ++nTuples;
748                        do {
749                                genEnd = results.size();
750
751                                // add another argument to results
752                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
753                                        auto nextArg = results[i].nextArg;
754
755                                        // use next element of exploded tuple if present
756                                        if ( results[i].hasExpl() ) {
757                                                const ExplodedActual& expl = results[i].getExpl( args );
758
759                                                unsigned nextExpl = results[i].nextExpl + 1;
760                                                if ( nextExpl == expl.exprs.size() ) {
761                                                        nextExpl = 0;
762                                                }
763
764                                                results.emplace_back(
765                                                        i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env),
766                                                        copy(results[i].need), copy(results[i].have),
767                                                        copy(results[i].openVars), nextArg, nTuples, Cost::zero, nextExpl,
768                                                        results[i].explAlt );
769
770                                                continue;
771                                        }
772
773                                        // finish result when out of arguments
774                                        if ( nextArg >= args.size() ) {
775                                                ArgPack newResult{
776                                                        results[i].env, results[i].need, results[i].have,
777                                                        results[i].openVars };
778                                                newResult.nextArg = nextArg;
779                                                Type* argType;
780
781                                                if ( nTuples > 0 || ! results[i].expr ) {
782                                                        // first iteration or no expression to clone,
783                                                        // push empty tuple expression
784                                                        newResult.parent = i;
785                                                        std::list<Expression*> emptyList;
786                                                        newResult.expr.reset( new TupleExpr( emptyList ) );
787                                                        argType = newResult.expr->get_result();
788                                                } else {
789                                                        // clone result to collect tuple
790                                                        newResult.parent = results[i].parent;
791                                                        newResult.cost = results[i].cost;
792                                                        newResult.tupleStart = results[i].tupleStart;
793                                                        newResult.expr.reset( results[i].expr->clone() );
794                                                        argType = newResult.expr->get_result();
795
796                                                        if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
797                                                                // the case where a ttype value is passed directly is special,
798                                                                // e.g. for argument forwarding purposes
799                                                                // xxx - what if passing multiple arguments, last of which is
800                                                                //       ttype?
801                                                                // xxx - what would happen if unify was changed so that unifying
802                                                                //       tuple
803                                                                // types flattened both before unifying lists? then pass in
804                                                                // TupleType (ttype) below.
805                                                                --newResult.tupleStart;
806                                                        } else {
807                                                                // collapse leftover arguments into tuple
808                                                                newResult.endTuple( results );
809                                                                argType = newResult.expr->get_result();
810                                                        }
811                                                }
812
813                                                // check unification for ttype before adding to final
814                                                if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have,
815                                                                newResult.openVars, indexer ) ) {
816                                                        finalResults.push_back( move(newResult) );
817                                                }
818
819                                                continue;
820                                        }
821
822                                        // add each possible next argument
823                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
824                                                const ExplodedActual& expl = args[nextArg][j];
825
826                                                // fresh copies of parent parameters for this iteration
827                                                TypeEnvironment env = results[i].env;
828                                                OpenVarSet openVars = results[i].openVars;
829
830                                                env.addActual( expl.env, openVars );
831
832                                                // skip empty tuple arguments by (near-)cloning parent into next gen
833                                                if ( expl.exprs.empty() ) {
834                                                        results.emplace_back(
835                                                                results[i], move(env), copy(results[i].need),
836                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
837
838                                                        continue;
839                                                }
840
841                                                // add new result
842                                                results.emplace_back(
843                                                        i, expl.exprs.front().get(), move(env), copy(results[i].need),
844                                                        copy(results[i].have), move(openVars), nextArg + 1,
845                                                        nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
846                                        }
847                                }
848
849                                // reset for next round
850                                genStart = genEnd;
851                                nTuples = 0;
852                        } while ( genEnd != results.size() );
853
854                        // splice final results onto results
855                        for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
856                                results.push_back( move(finalResults[i]) );
857                        }
858                        return ! finalResults.empty();
859                }
860
861                // iterate each current subresult
862                std::size_t genEnd = results.size();
863                for ( std::size_t i = genStart; i < genEnd; ++i ) {
864                        auto nextArg = results[i].nextArg;
865
866                        // use remainder of exploded tuple if present
867                        if ( results[i].hasExpl() ) {
868                                const ExplodedActual& expl = results[i].getExpl( args );
869                                Expression* expr = expl.exprs[results[i].nextExpl].get();
870
871                                TypeEnvironment env = results[i].env;
872                                AssertionSet need = results[i].need, have = results[i].have;
873                                OpenVarSet openVars = results[i].openVars;
874
875                                Type* actualType = expr->get_result();
876
877                                PRINT(
878                                        std::cerr << "formal type is ";
879                                        formalType->print( std::cerr );
880                                        std::cerr << std::endl << "actual type is ";
881                                        actualType->print( std::cerr );
882                                        std::cerr << std::endl;
883                                )
884
885                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
886                                        unsigned nextExpl = results[i].nextExpl + 1;
887                                        if ( nextExpl == expl.exprs.size() ) {
888                                                nextExpl = 0;
889                                        }
890
891                                        results.emplace_back(
892                                                i, expr, move(env), move(need), move(have), move(openVars), nextArg,
893                                                nTuples, Cost::zero, nextExpl, results[i].explAlt );
894                                }
895
896                                continue;
897                        }
898
899                        // use default initializers if out of arguments
900                        if ( nextArg >= args.size() ) {
901                                if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
902                                        if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
903                                                TypeEnvironment env = results[i].env;
904                                                AssertionSet need = results[i].need, have = results[i].have;
905                                                OpenVarSet openVars = results[i].openVars;
906
907                                                if ( unify( formalType, cnst->get_type(), env, need, have, openVars,
908                                                                indexer ) ) {
909                                                        results.emplace_back(
910                                                                i, new DefaultArgExpr( cnstExpr ), move(env), move(need), move(have),
911                                                                move(openVars), nextArg, nTuples );
912                                                }
913                                        }
914                                }
915
916                                continue;
917                        }
918
919                        // Check each possible next argument
920                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
921                                const ExplodedActual& expl = args[nextArg][j];
922
923                                // fresh copies of parent parameters for this iteration
924                                TypeEnvironment env = results[i].env;
925                                AssertionSet need = results[i].need, have = results[i].have;
926                                OpenVarSet openVars = results[i].openVars;
927
928                                env.addActual( expl.env, openVars );
929
930                                // skip empty tuple arguments by (near-)cloning parent into next gen
931                                if ( expl.exprs.empty() ) {
932                                        results.emplace_back(
933                                                results[i], move(env), move(need), move(have), move(openVars),
934                                                nextArg + 1, expl.cost );
935
936                                        continue;
937                                }
938
939                                // consider only first exploded actual
940                                Expression* expr = expl.exprs.front().get();
941                                Type* actualType = expr->result->clone();
942
943                                PRINT(
944                                        std::cerr << "formal type is ";
945                                        formalType->print( std::cerr );
946                                        std::cerr << std::endl << "actual type is ";
947                                        actualType->print( std::cerr );
948                                        std::cerr << std::endl;
949                                )
950
951                                // attempt to unify types
952                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
953                                        // add new result
954                                        results.emplace_back(
955                                                i, expr, move(env), move(need), move(have), move(openVars), nextArg + 1,
956                                                nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
957                                }
958                        }
959                }
960
961                // reset for next parameter
962                genStart = genEnd;
963
964                return genEnd != results.size();
965        }
966
967        template<typename OutputIterator>
968        void AlternativeFinder::Finder::validateFunctionAlternative( const Alternative &func, ArgPack& result,
969                        const std::vector<ArgPack>& results, OutputIterator out ) {
970                ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
971                // sum cost and accumulate actuals
972                std::list<Expression*>& args = appExpr->args;
973                Cost cost = func.cost;
974                const ArgPack* pack = &result;
975                while ( pack->expr ) {
976                        args.push_front( pack->expr->clone() );
977                        cost += pack->cost;
978                        pack = &results[pack->parent];
979                }
980                // build and validate new alternative
981                Alternative newAlt{ appExpr, result.env, result.openVars, result.need, cost };
982                PRINT(
983                        std::cerr << "instantiate function success: " << appExpr << std::endl;
984                        std::cerr << "need assertions:" << std::endl;
985                        printAssertionSet( result.need, std::cerr, 8 );
986                )
987                inferParameters( newAlt, out );
988        }
989
990        template<typename OutputIterator>
991        void AlternativeFinder::Finder::makeFunctionAlternatives( const Alternative &func,
992                        FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) {
993                OpenVarSet funcOpenVars;
994                AssertionSet funcNeed, funcHave;
995                TypeEnvironment funcEnv( func.env );
996                makeUnifiableVars( funcType, funcOpenVars, funcNeed );
997                // add all type variables as open variables now so that those not used in the parameter
998                // list are still considered open.
999                funcEnv.add( funcType->forall );
1000
1001                if ( targetType && ! targetType->isVoid() && ! funcType->returnVals.empty() ) {
1002                        // attempt to narrow based on expected target type
1003                        Type * returnType = funcType->returnVals.front()->get_type();
1004                        if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars,
1005                                        indexer ) ) {
1006                                // unification failed, don't pursue this function alternative
1007                                return;
1008                        }
1009                }
1010
1011                // iteratively build matches, one parameter at a time
1012                std::vector<ArgPack> results;
1013                results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } );
1014                std::size_t genStart = 0;
1015
1016                for ( DeclarationWithType* formal : funcType->parameters ) {
1017                        ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal );
1018                        if ( ! instantiateArgument(
1019                                        obj->type, obj->init, args, results, genStart, indexer ) )
1020                                return;
1021                }
1022
1023                if ( funcType->get_isVarArgs() ) {
1024                        // append any unused arguments to vararg pack
1025                        std::size_t genEnd;
1026                        do {
1027                                genEnd = results.size();
1028
1029                                // iterate results
1030                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
1031                                        auto nextArg = results[i].nextArg;
1032
1033                                        // use remainder of exploded tuple if present
1034                                        if ( results[i].hasExpl() ) {
1035                                                const ExplodedActual& expl = results[i].getExpl( args );
1036
1037                                                unsigned nextExpl = results[i].nextExpl + 1;
1038                                                if ( nextExpl == expl.exprs.size() ) {
1039                                                        nextExpl = 0;
1040                                                }
1041
1042                                                results.emplace_back(
1043                                                        i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env),
1044                                                        copy(results[i].need), copy(results[i].have),
1045                                                        copy(results[i].openVars), nextArg, 0, Cost::zero, nextExpl,
1046                                                        results[i].explAlt );
1047
1048                                                continue;
1049                                        }
1050
1051                                        // finish result when out of arguments
1052                                        if ( nextArg >= args.size() ) {
1053                                                validateFunctionAlternative( func, results[i], results, out );
1054
1055                                                continue;
1056                                        }
1057
1058                                        // add each possible next argument
1059                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
1060                                                const ExplodedActual& expl = args[nextArg][j];
1061
1062                                                // fresh copies of parent parameters for this iteration
1063                                                TypeEnvironment env = results[i].env;
1064                                                OpenVarSet openVars = results[i].openVars;
1065
1066                                                env.addActual( expl.env, openVars );
1067
1068                                                // skip empty tuple arguments by (near-)cloning parent into next gen
1069                                                if ( expl.exprs.empty() ) {
1070                                                        results.emplace_back(
1071                                                                results[i], move(env), copy(results[i].need),
1072                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
1073
1074                                                        continue;
1075                                                }
1076
1077                                                // add new result
1078                                                results.emplace_back(
1079                                                        i, expl.exprs.front().get(), move(env), copy(results[i].need),
1080                                                        copy(results[i].have), move(openVars), nextArg + 1, 0,
1081                                                        expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
1082                                        }
1083                                }
1084
1085                                genStart = genEnd;
1086                        } while ( genEnd != results.size() );
1087                } else {
1088                        // filter out results that don't use all the arguments
1089                        for ( std::size_t i = genStart; i < results.size(); ++i ) {
1090                                ArgPack& result = results[i];
1091                                if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
1092                                        validateFunctionAlternative( func, result, results, out );
1093                                }
1094                        }
1095                }
1096        }
1097
1098        void AlternativeFinder::Finder::postvisit( UntypedExpr *untypedExpr ) {
1099                AlternativeFinder funcFinder( indexer, env );
1100                funcFinder.findWithAdjustment( untypedExpr->function );
1101                // if there are no function alternatives, then proceeding is a waste of time.
1102                // xxx - findWithAdjustment throws, so this check and others like it shouldn't be necessary.
1103                if ( funcFinder.alternatives.empty() ) return;
1104
1105                std::vector< AlternativeFinder > argAlternatives;
1106                altFinder.findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(),
1107                        back_inserter( argAlternatives ) );
1108
1109                // take care of possible tuple assignments
1110                // if not tuple assignment, assignment is taken care of as a normal function call
1111                Tuples::handleTupleAssignment( altFinder, untypedExpr, argAlternatives );
1112
1113                // find function operators
1114                static NameExpr *opExpr = new NameExpr( "?()" );
1115                AlternativeFinder funcOpFinder( indexer, env );
1116                // it's ok if there aren't any defined function ops
1117                funcOpFinder.maybeFind( opExpr );
1118                PRINT(
1119                        std::cerr << "known function ops:" << std::endl;
1120                        printAlts( funcOpFinder.alternatives, std::cerr, 1 );
1121                )
1122
1123                // pre-explode arguments
1124                ExplodedArgs argExpansions;
1125                argExpansions.reserve( argAlternatives.size() );
1126
1127                for ( const AlternativeFinder& arg : argAlternatives ) {
1128                        argExpansions.emplace_back();
1129                        auto& argE = argExpansions.back();
1130                        // argE.reserve( arg.alternatives.size() );
1131
1132                        for ( const Alternative& actual : arg ) {
1133                                argE.emplace_back( actual, indexer );
1134                        }
1135                }
1136
1137                AltList candidates;
1138                SemanticErrorException errors;
1139                for ( AltList::iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
1140                        try {
1141                                PRINT(
1142                                        std::cerr << "working on alternative: " << std::endl;
1143                                        func->print( std::cerr, 8 );
1144                                )
1145                                // check if the type is pointer to function
1146                                if ( PointerType *pointer = dynamic_cast< PointerType* >( func->expr->result->stripReferences() ) ) {
1147                                        if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->base ) ) {
1148                                                Alternative newFunc( *func );
1149                                                referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1150                                                makeFunctionAlternatives( newFunc, function, argExpansions,
1151                                                        std::back_inserter( candidates ) );
1152                                        }
1153                                } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->result->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
1154                                        if ( const EqvClass *eqvClass = func->env.lookup( typeInst->name ) ) {
1155                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass->type ) ) {
1156                                                        Alternative newFunc( *func );
1157                                                        referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1158                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
1159                                                                std::back_inserter( candidates ) );
1160                                                } // if
1161                                        } // if
1162                                }
1163                        } catch ( SemanticErrorException &e ) {
1164                                errors.append( e );
1165                        }
1166                } // for
1167
1168                // try each function operator ?() with each function alternative
1169                if ( ! funcOpFinder.alternatives.empty() ) {
1170                        // add exploded function alternatives to front of argument list
1171                        std::vector<ExplodedActual> funcE;
1172                        funcE.reserve( funcFinder.alternatives.size() );
1173                        for ( const Alternative& actual : funcFinder ) {
1174                                funcE.emplace_back( actual, indexer );
1175                        }
1176                        argExpansions.insert( argExpansions.begin(), move(funcE) );
1177
1178                        for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
1179                                        funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
1180                                try {
1181                                        // check if type is a pointer to function
1182                                        if ( PointerType* pointer = dynamic_cast<PointerType*>(
1183                                                        funcOp->expr->result->stripReferences() ) ) {
1184                                                if ( FunctionType* function =
1185                                                                dynamic_cast<FunctionType*>( pointer->base ) ) {
1186                                                        Alternative newFunc( *funcOp );
1187                                                        referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1188                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
1189                                                                std::back_inserter( candidates ) );
1190                                                }
1191                                        }
1192                                } catch ( SemanticErrorException &e ) {
1193                                        errors.append( e );
1194                                }
1195                        }
1196                }
1197
1198                // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
1199                if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
1200
1201                // compute conversionsion costs
1202                for ( Alternative& withFunc : candidates ) {
1203                        Cost cvtCost = computeApplicationConversionCost( withFunc, indexer );
1204
1205                        PRINT(
1206                                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr );
1207                                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->function->result );
1208                                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->base );
1209                                std::cerr << "Case +++++++++++++ " << appExpr->function << std::endl;
1210                                std::cerr << "formals are:" << std::endl;
1211                                printAll( function->parameters, std::cerr, 8 );
1212                                std::cerr << "actuals are:" << std::endl;
1213                                printAll( appExpr->args, std::cerr, 8 );
1214                                std::cerr << "bindings are:" << std::endl;
1215                                withFunc.env.print( std::cerr, 8 );
1216                                std::cerr << "cost is: " << withFunc.cost << std::endl;
1217                                std::cerr << "cost of conversion is:" << cvtCost << std::endl;
1218                        )
1219                        if ( cvtCost != Cost::infinity ) {
1220                                withFunc.cvtCost = cvtCost;
1221                                alternatives.push_back( withFunc );
1222                        } // if
1223                } // for
1224
1225                candidates = move(alternatives);
1226
1227                // use a new list so that alternatives are not examined by addAnonConversions twice.
1228                AltList winners;
1229                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) );
1230
1231                // function may return struct or union value, in which case we need to add alternatives
1232                // for implicitconversions to each of the anonymous members, must happen after findMinCost
1233                // since anon conversions are never the cheapest expression
1234                for ( const Alternative & alt : winners ) {
1235                        addAnonConversions( alt );
1236                }
1237                spliceBegin( alternatives, winners );
1238
1239                if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
1240                        // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
1241                        // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
1242                        //   forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
1243                        //   const char * x = "hello world";
1244                        //   unsigned char ch = x[0];
1245                        // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
1246                        // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
1247                        // fix this issue in a more robust way.
1248                        targetType = nullptr;
1249                        postvisit( untypedExpr );
1250                }
1251        }
1252
1253        bool isLvalue( Expression *expr ) {
1254                // xxx - recurse into tuples?
1255                return expr->result && ( expr->result->get_lvalue() || dynamic_cast< ReferenceType * >( expr->result ) );
1256        }
1257
1258        void AlternativeFinder::Finder::postvisit( AddressExpr *addressExpr ) {
1259                AlternativeFinder finder( indexer, env );
1260                finder.find( addressExpr->get_arg() );
1261                for ( Alternative& alt : finder.alternatives ) {
1262                        if ( isLvalue( alt.expr ) ) {
1263                                alternatives.push_back(
1264                                        Alternative{ alt, new AddressExpr( alt.expr->clone() ), alt.cost } );
1265                        } // if
1266                } // for
1267        }
1268
1269        void AlternativeFinder::Finder::postvisit( LabelAddressExpr * expr ) {
1270                alternatives.push_back( Alternative{ expr->clone(), env } );
1271        }
1272
1273        Expression * restructureCast( Expression * argExpr, Type * toType, bool isGenerated ) {
1274                if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() && ! dynamic_cast<ReferenceType *>( toType ) ) {
1275                        // Argument expression is a tuple and the target type is not void and not a reference type.
1276                        // Cast each member of the tuple to its corresponding target type, producing the tuple of those
1277                        // cast expressions. If there are more components of the tuple than components in the target type,
1278                        // then excess components do not come out in the result expression (but UniqueExprs ensure that
1279                        // side effects will still be done).
1280                        if ( Tuples::maybeImpureIgnoreUnique( argExpr ) ) {
1281                                // expressions which may contain side effects require a single unique instance of the expression.
1282                                argExpr = new UniqueExpr( argExpr );
1283                        }
1284                        std::list< Expression * > componentExprs;
1285                        for ( unsigned int i = 0; i < toType->size(); i++ ) {
1286                                // cast each component
1287                                TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
1288                                componentExprs.push_back( restructureCast( idx, toType->getComponent( i ), isGenerated ) );
1289                        }
1290                        delete argExpr;
1291                        assert( componentExprs.size() > 0 );
1292                        // produce the tuple of casts
1293                        return new TupleExpr( componentExprs );
1294                } else {
1295                        // handle normally
1296                        CastExpr * ret = new CastExpr( argExpr, toType->clone() );
1297                        ret->isGenerated = isGenerated;
1298                        return ret;
1299                }
1300        }
1301
1302        void AlternativeFinder::Finder::postvisit( CastExpr *castExpr ) {
1303                Type *& toType = castExpr->get_result();
1304                assert( toType );
1305                toType = resolveTypeof( toType, indexer );
1306                SymTab::validateType( toType, &indexer );
1307                adjustExprType( toType, env, indexer );
1308
1309                AlternativeFinder finder( indexer, env );
1310                finder.targetType = toType;
1311                finder.findWithAdjustment( castExpr->arg );
1312
1313                AltList candidates;
1314                for ( Alternative & alt : finder.alternatives ) {
1315                        AssertionSet needAssertions( alt.need.begin(), alt.need.end() );
1316                        AssertionSet haveAssertions;
1317                        OpenVarSet openVars{ alt.openVars };
1318
1319                        alt.env.extractOpenVars( openVars );
1320
1321                        // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1322                        // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1323                        // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1324                        // to.
1325                        int discardedValues = alt.expr->result->size() - castExpr->result->size();
1326                        if ( discardedValues < 0 ) continue;
1327                        // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1328                        // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1329                        // unification run for side-effects
1330                        unify( castExpr->result, alt.expr->result, alt.env, needAssertions,
1331                                haveAssertions, openVars, indexer );
1332                        Cost thisCost = castCost( alt.expr->result, castExpr->result, indexer,
1333                                alt.env );
1334                        PRINT(
1335                                std::cerr << "working on cast with result: " << castExpr->result << std::endl;
1336                                std::cerr << "and expr type: " << alt.expr->result << std::endl;
1337                                std::cerr << "env: " << alt.env << std::endl;
1338                        )
1339                        if ( thisCost != Cost::infinity ) {
1340                                PRINT(
1341                                        std::cerr << "has finite cost." << std::endl;
1342                                )
1343                                // count one safe conversion for each value that is thrown away
1344                                thisCost.incSafe( discardedValues );
1345                                Alternative newAlt{ 
1346                                        restructureCast( alt.expr->clone(), toType, castExpr->isGenerated ), 
1347                                        alt.env, openVars, needAssertions, alt.cost, thisCost };
1348                                inferParameters( newAlt, back_inserter( candidates ) );
1349                        } // if
1350                } // for
1351
1352                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1353                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1354                // selects first based on argument cost, then on conversion cost.
1355                AltList minArgCost;
1356                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1357                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1358        }
1359
1360        void AlternativeFinder::Finder::postvisit( VirtualCastExpr * castExpr ) {
1361                assertf( castExpr->get_result(), "Implicit virtual cast targets not yet supported." );
1362                AlternativeFinder finder( indexer, env );
1363                // don't prune here, since it's guaranteed all alternatives will have the same type
1364                finder.findWithoutPrune( castExpr->get_arg() );
1365                for ( Alternative & alt : finder.alternatives ) {
1366                        alternatives.push_back( Alternative{
1367                                alt, new VirtualCastExpr{ alt.expr->clone(), castExpr->get_result()->clone() },
1368                                alt.cost } );
1369                }
1370        }
1371
1372        namespace {
1373                /// Gets name from untyped member expression (member must be NameExpr)
1374                const std::string& get_member_name( UntypedMemberExpr *memberExpr ) {
1375                        NameExpr * nameExpr = dynamic_cast< NameExpr * >( memberExpr->get_member() );
1376                        assert( nameExpr );
1377                        return nameExpr->get_name();
1378                }
1379        }
1380
1381        void AlternativeFinder::Finder::postvisit( UntypedMemberExpr *memberExpr ) {
1382                AlternativeFinder funcFinder( indexer, env );
1383                funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
1384                for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
1385                        // 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
1386                        Cost cost = agg->cost;
1387                        Expression * aggrExpr = agg->expr->clone();
1388                        referenceToRvalueConversion( aggrExpr, cost );
1389                        std::unique_ptr<Expression> guard( aggrExpr );
1390
1391                        // find member of the given type
1392                        if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
1393                                addAggMembers( structInst, aggrExpr, *agg, cost, get_member_name(memberExpr) );
1394                        } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
1395                                addAggMembers( unionInst, aggrExpr, *agg, cost, get_member_name(memberExpr) );
1396                        } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
1397                                addTupleMembers( tupleType, aggrExpr, *agg, cost, memberExpr->get_member() );
1398                        } // if
1399                } // for
1400        }
1401
1402        void AlternativeFinder::Finder::postvisit( MemberExpr *memberExpr ) {
1403                alternatives.push_back( Alternative{ memberExpr->clone(), env } );
1404        }
1405
1406        void AlternativeFinder::Finder::postvisit( NameExpr *nameExpr ) {
1407                std::list< SymTab::Indexer::IdData > declList;
1408                indexer.lookupId( nameExpr->name, declList );
1409                PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )
1410                for ( auto & data : declList ) {
1411                        Cost cost = Cost::zero;
1412                        Expression * newExpr = data.combine( cost );
1413
1414                        // addAnonAlternatives uses vector::push_back, which invalidates references to existing elements, so
1415                        // can't construct in place and use vector::back
1416                        Alternative newAlt{ newExpr, env, OpenVarSet{}, AssertionList{}, Cost::zero, cost };
1417                        PRINT(
1418                                std::cerr << "decl is ";
1419                                data.id->print( std::cerr );
1420                                std::cerr << std::endl;
1421                                std::cerr << "newExpr is ";
1422                                newExpr->print( std::cerr );
1423                                std::cerr << std::endl;
1424                        )
1425                        renameTypes( newAlt.expr );
1426                        addAnonConversions( newAlt ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
1427                        alternatives.push_back( std::move(newAlt) );
1428                } // for
1429        }
1430
1431        void AlternativeFinder::Finder::postvisit( VariableExpr *variableExpr ) {
1432                // not sufficient to clone here, because variable's type may have changed
1433                // since the VariableExpr was originally created.
1434                alternatives.push_back( Alternative{ new VariableExpr{ variableExpr->var }, env } );
1435        }
1436
1437        void AlternativeFinder::Finder::postvisit( ConstantExpr *constantExpr ) {
1438                alternatives.push_back( Alternative{ constantExpr->clone(), env } );
1439        }
1440
1441        void AlternativeFinder::Finder::postvisit( SizeofExpr *sizeofExpr ) {
1442                if ( sizeofExpr->get_isType() ) {
1443                        Type * newType = sizeofExpr->get_type()->clone();
1444                        alternatives.push_back( Alternative{ 
1445                                new SizeofExpr{ resolveTypeof( newType, indexer ) }, env } );
1446                } else {
1447                        // find all alternatives for the argument to sizeof
1448                        AlternativeFinder finder( indexer, env );
1449                        finder.find( sizeofExpr->get_expr() );
1450                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1451                        AltList winners;
1452                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1453                        if ( winners.size() != 1 ) {
1454                                SemanticError( sizeofExpr->get_expr(), "Ambiguous expression in sizeof operand: " );
1455                        } // if
1456                        // return the lowest cost alternative for the argument
1457                        Alternative &choice = winners.front();
1458                        referenceToRvalueConversion( choice.expr, choice.cost );
1459                        alternatives.push_back( Alternative{ 
1460                                choice, new SizeofExpr( choice.expr->clone() ), Cost::zero } );
1461                } // if
1462        }
1463
1464        void AlternativeFinder::Finder::postvisit( AlignofExpr *alignofExpr ) {
1465                if ( alignofExpr->get_isType() ) {
1466                        Type * newType = alignofExpr->get_type()->clone();
1467                        alternatives.push_back( Alternative{ 
1468                                new AlignofExpr{ resolveTypeof( newType, indexer ) }, env } );
1469                } else {
1470                        // find all alternatives for the argument to sizeof
1471                        AlternativeFinder finder( indexer, env );
1472                        finder.find( alignofExpr->get_expr() );
1473                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1474                        AltList winners;
1475                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1476                        if ( winners.size() != 1 ) {
1477                                SemanticError( alignofExpr->get_expr(), "Ambiguous expression in alignof operand: " );
1478                        } // if
1479                        // return the lowest cost alternative for the argument
1480                        Alternative &choice = winners.front();
1481                        referenceToRvalueConversion( choice.expr, choice.cost );
1482                        alternatives.push_back( Alternative{ 
1483                                choice, new AlignofExpr{ choice.expr->clone() }, Cost::zero } );
1484                } // if
1485        }
1486
1487        template< typename StructOrUnionType >
1488        void AlternativeFinder::Finder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
1489                std::list< Declaration* > members;
1490                aggInst->lookup( name, members );
1491                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
1492                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
1493                                alternatives.push_back( Alternative{ 
1494                                        new OffsetofExpr{ aggInst->clone(), dwt }, env } );
1495                                renameTypes( alternatives.back().expr );
1496                        } else {
1497                                assert( false );
1498                        }
1499                }
1500        }
1501
1502        void AlternativeFinder::Finder::postvisit( UntypedOffsetofExpr *offsetofExpr ) {
1503                AlternativeFinder funcFinder( indexer, env );
1504                // xxx - resolveTypeof?
1505                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
1506                        addOffsetof( structInst, offsetofExpr->member );
1507                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
1508                        addOffsetof( unionInst, offsetofExpr->member );
1509                }
1510        }
1511
1512        void AlternativeFinder::Finder::postvisit( OffsetofExpr *offsetofExpr ) {
1513                alternatives.push_back( Alternative{ offsetofExpr->clone(), env } );
1514        }
1515
1516        void AlternativeFinder::Finder::postvisit( OffsetPackExpr *offsetPackExpr ) {
1517                alternatives.push_back( Alternative{ offsetPackExpr->clone(), env } );
1518        }
1519
1520        namespace {
1521                void resolveAttr( SymTab::Indexer::IdData data, FunctionType *function, Type *argType, const TypeEnvironment &env, AlternativeFinder & finder ) {
1522                        // assume no polymorphism
1523                        // assume no implicit conversions
1524                        assert( function->get_parameters().size() == 1 );
1525                        PRINT(
1526                                std::cerr << "resolvAttr: funcDecl is ";
1527                                data.id->print( std::cerr );
1528                                std::cerr << " argType is ";
1529                                argType->print( std::cerr );
1530                                std::cerr << std::endl;
1531                        )
1532                        const SymTab::Indexer & indexer = finder.get_indexer();
1533                        AltList & alternatives = finder.get_alternatives();
1534                        if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1535                                Cost cost = Cost::zero;
1536                                Expression * newExpr = data.combine( cost );
1537                                alternatives.push_back( Alternative{ 
1538                                        new AttrExpr{ newExpr, argType->clone() }, env, OpenVarSet{}, 
1539                                        AssertionList{}, Cost::zero, cost } );
1540                                for ( DeclarationWithType * retVal : function->returnVals ) {
1541                                        alternatives.back().expr->result = retVal->get_type()->clone();
1542                                } // for
1543                        } // if
1544                }
1545        }
1546
1547        void AlternativeFinder::Finder::postvisit( AttrExpr *attrExpr ) {
1548                // assume no 'pointer-to-attribute'
1549                NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1550                assert( nameExpr );
1551                std::list< SymTab::Indexer::IdData > attrList;
1552                indexer.lookupId( nameExpr->get_name(), attrList );
1553                if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1554                        for ( auto & data : attrList ) {
1555                                DeclarationWithType * id = data.id;
1556                                // check if the type is function
1557                                if ( FunctionType *function = dynamic_cast< FunctionType* >( id->get_type() ) ) {
1558                                        // assume exactly one parameter
1559                                        if ( function->get_parameters().size() == 1 ) {
1560                                                if ( attrExpr->get_isType() ) {
1561                                                        resolveAttr( data, function, attrExpr->get_type(), env, altFinder);
1562                                                } else {
1563                                                        AlternativeFinder finder( indexer, env );
1564                                                        finder.find( attrExpr->get_expr() );
1565                                                        for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1566                                                                if ( choice->expr->get_result()->size() == 1 ) {
1567                                                                        resolveAttr(data, function, choice->expr->get_result(), choice->env, altFinder );
1568                                                                } // fi
1569                                                        } // for
1570                                                } // if
1571                                        } // if
1572                                } // if
1573                        } // for
1574                } else {
1575                        for ( auto & data : attrList ) {
1576                                Cost cost = Cost::zero;
1577                                Expression * newExpr = data.combine( cost );
1578                                alternatives.push_back( Alternative{ 
1579                                        newExpr, env, OpenVarSet{}, AssertionList{}, Cost::zero, cost } );
1580                                renameTypes( alternatives.back().expr );
1581                        } // for
1582                } // if
1583        }
1584
1585        void AlternativeFinder::Finder::postvisit( LogicalExpr *logicalExpr ) {
1586                AlternativeFinder firstFinder( indexer, env );
1587                firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1588                if ( firstFinder.alternatives.empty() ) return;
1589                AlternativeFinder secondFinder( indexer, env );
1590                secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1591                if ( secondFinder.alternatives.empty() ) return;
1592                for ( const Alternative & first : firstFinder.alternatives ) {
1593                        for ( const Alternative & second : secondFinder.alternatives ) {
1594                                TypeEnvironment compositeEnv{ first.env };
1595                                compositeEnv.simpleCombine( second.env );
1596                                OpenVarSet openVars{ first.openVars };
1597                                mergeOpenVars( openVars, second.openVars );
1598                                AssertionSet need;
1599                                cloneAll( first.need, need );
1600                                cloneAll( second.need, need );
1601
1602                                LogicalExpr *newExpr = new LogicalExpr{ 
1603                                        first.expr->clone(), second.expr->clone(), logicalExpr->get_isAnd() };
1604                                alternatives.push_back( Alternative{ 
1605                                        newExpr, std::move(compositeEnv), std::move(openVars), 
1606                                        AssertionList( need.begin(), need.end() ), first.cost + second.cost } );
1607                        }
1608                }
1609        }
1610
1611        void AlternativeFinder::Finder::postvisit( ConditionalExpr *conditionalExpr ) {
1612                // find alternatives for condition
1613                AlternativeFinder firstFinder( indexer, env );
1614                firstFinder.findWithAdjustment( conditionalExpr->arg1 );
1615                if ( firstFinder.alternatives.empty() ) return;
1616                // find alternatives for true expression
1617                AlternativeFinder secondFinder( indexer, env );
1618                secondFinder.findWithAdjustment( conditionalExpr->arg2 );
1619                if ( secondFinder.alternatives.empty() ) return;
1620                // find alterantives for false expression
1621                AlternativeFinder thirdFinder( indexer, env );
1622                thirdFinder.findWithAdjustment( conditionalExpr->arg3 );
1623                if ( thirdFinder.alternatives.empty() ) return;
1624                for ( const Alternative & first : firstFinder.alternatives ) {
1625                        for ( const Alternative & second : secondFinder.alternatives ) {
1626                                for ( const Alternative & third : thirdFinder.alternatives ) {
1627                                        TypeEnvironment compositeEnv{ first.env };
1628                                        compositeEnv.simpleCombine( second.env );
1629                                        compositeEnv.simpleCombine( third.env );
1630                                        OpenVarSet openVars{ first.openVars };
1631                                        mergeOpenVars( openVars, second.openVars );
1632                                        mergeOpenVars( openVars, third.openVars );
1633                                        AssertionSet need;
1634                                        cloneAll( first.need, need );
1635                                        cloneAll( second.need, need );
1636                                        cloneAll( third.need, need );
1637                                        AssertionSet have;
1638                                       
1639                                        // unify true and false types, then infer parameters to produce new alternatives
1640                                        Type* commonType = nullptr;
1641                                        if ( unify( second.expr->result, third.expr->result, compositeEnv, 
1642                                                        need, have, openVars, indexer, commonType ) ) {
1643                                                ConditionalExpr *newExpr = new ConditionalExpr{ 
1644                                                        first.expr->clone(), second.expr->clone(), third.expr->clone() };
1645                                                newExpr->result = commonType ? commonType : second.expr->result->clone();
1646                                                // convert both options to the conditional result type
1647                                                Cost cost = first.cost + second.cost + third.cost;
1648                                                cost += computeExpressionConversionCost( 
1649                                                        newExpr->arg2, newExpr->result, indexer, compositeEnv );
1650                                                cost += computeExpressionConversionCost( 
1651                                                        newExpr->arg3, newExpr->result, indexer, compositeEnv );
1652                                                // output alternative
1653                                                Alternative newAlt{ 
1654                                                        newExpr, std::move(compositeEnv), std::move(openVars), 
1655                                                        AssertionList( need.begin(), need.end() ), cost };
1656                                                inferParameters( newAlt, back_inserter( alternatives ) );
1657                                        } // if
1658                                } // for
1659                        } // for
1660                } // for
1661        }
1662
1663        void AlternativeFinder::Finder::postvisit( CommaExpr *commaExpr ) {
1664                TypeEnvironment newEnv( env );
1665                Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1666                AlternativeFinder secondFinder( indexer, newEnv );
1667                secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1668                for ( const Alternative & alt : secondFinder.alternatives ) {
1669                        alternatives.push_back( Alternative{ 
1670                                alt, new CommaExpr{ newFirstArg->clone(), alt.expr->clone() }, alt.cost } );
1671                } // for
1672                delete newFirstArg;
1673        }
1674
1675        void AlternativeFinder::Finder::postvisit( RangeExpr * rangeExpr ) {
1676                // resolve low and high, accept alternatives whose low and high types unify
1677                AlternativeFinder firstFinder( indexer, env );
1678                firstFinder.findWithAdjustment( rangeExpr->low );
1679                if ( firstFinder.alternatives.empty() ) return;
1680                AlternativeFinder secondFinder( indexer, env );
1681                secondFinder.findWithAdjustment( rangeExpr->high );
1682                if ( secondFinder.alternatives.empty() ) return;
1683                for ( const Alternative & first : firstFinder.alternatives ) {
1684                        for ( const Alternative & second : secondFinder.alternatives ) {
1685                                TypeEnvironment compositeEnv{ first.env };
1686                                compositeEnv.simpleCombine( second.env );
1687                                OpenVarSet openVars{ first.openVars };
1688                                mergeOpenVars( openVars, second.openVars );
1689                                AssertionSet need;
1690                                cloneAll( first.need, need );
1691                                cloneAll( second.need, need );
1692                                AssertionSet have;
1693
1694                                Type* commonType = nullptr;
1695                                if ( unify( first.expr->result, second.expr->result, compositeEnv, need, have, 
1696                                                openVars, indexer, commonType ) ) {
1697                                        RangeExpr * newExpr = 
1698                                                new RangeExpr{ first.expr->clone(), second.expr->clone() };
1699                                        newExpr->result = commonType ? commonType : first.expr->result->clone();
1700                                        Alternative newAlt{ 
1701                                                newExpr, std::move(compositeEnv), std::move(openVars), 
1702                                                AssertionList( need.begin(), need.end() ), first.cost + second.cost };
1703                                        inferParameters( newAlt, back_inserter( alternatives ) );
1704                                } // if
1705                        } // for
1706                } // for
1707        }
1708
1709        void AlternativeFinder::Finder::postvisit( UntypedTupleExpr *tupleExpr ) {
1710                std::vector< AlternativeFinder > subExprAlternatives;
1711                altFinder.findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(),
1712                        back_inserter( subExprAlternatives ) );
1713                std::vector< AltList > possibilities;
1714                combos( subExprAlternatives.begin(), subExprAlternatives.end(),
1715                        back_inserter( possibilities ) );
1716                for ( const AltList& alts : possibilities ) {
1717                        std::list< Expression * > exprs;
1718                        makeExprList( alts, exprs );
1719
1720                        TypeEnvironment compositeEnv;
1721                        OpenVarSet openVars;
1722                        AssertionSet need;
1723                        for ( const Alternative& alt : alts ) {
1724                                compositeEnv.simpleCombine( alt.env );
1725                                mergeOpenVars( openVars, alt.openVars );
1726                                cloneAll( alt.need, need );
1727                        }
1728                       
1729                        alternatives.push_back( Alternative{ 
1730                                new TupleExpr{ exprs }, std::move(compositeEnv), std::move(openVars), 
1731                                AssertionList( need.begin(), need.end() ), sumCost( alts ) } );
1732                } // for
1733        }
1734
1735        void AlternativeFinder::Finder::postvisit( TupleExpr *tupleExpr ) {
1736                alternatives.push_back( Alternative{ tupleExpr->clone(), env } );
1737        }
1738
1739        void AlternativeFinder::Finder::postvisit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1740                alternatives.push_back( Alternative{ impCpCtorExpr->clone(), env } );
1741        }
1742
1743        void AlternativeFinder::Finder::postvisit( ConstructorExpr * ctorExpr ) {
1744                AlternativeFinder finder( indexer, env );
1745                // don't prune here, since it's guaranteed all alternatives will have the same type
1746                // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1747                finder.findWithoutPrune( ctorExpr->get_callExpr() );
1748                for ( Alternative & alt : finder.alternatives ) {
1749                        alternatives.push_back( Alternative{ 
1750                                alt, new ConstructorExpr( alt.expr->clone() ), alt.cost } );
1751                }
1752        }
1753
1754        void AlternativeFinder::Finder::postvisit( TupleIndexExpr *tupleExpr ) {
1755                alternatives.push_back( Alternative{ tupleExpr->clone(), env } );
1756        }
1757
1758        void AlternativeFinder::Finder::postvisit( TupleAssignExpr *tupleAssignExpr ) {
1759                alternatives.push_back( Alternative{ tupleAssignExpr->clone(), env } );
1760        }
1761
1762        void AlternativeFinder::Finder::postvisit( UniqueExpr *unqExpr ) {
1763                AlternativeFinder finder( indexer, env );
1764                finder.findWithAdjustment( unqExpr->get_expr() );
1765                for ( Alternative & alt : finder.alternatives ) {
1766                        // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
1767                        UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
1768                        alternatives.push_back( Alternative{ alt, newUnqExpr, alt.cost } );
1769                }
1770        }
1771
1772        void AlternativeFinder::Finder::postvisit( StmtExpr *stmtExpr ) {
1773                StmtExpr * newStmtExpr = stmtExpr->clone();
1774                ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1775                // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1776                alternatives.push_back( Alternative{ newStmtExpr, env } );
1777        }
1778
1779        void AlternativeFinder::Finder::postvisit( UntypedInitExpr *initExpr ) {
1780                // handle each option like a cast
1781                AltList candidates;
1782                PRINT(
1783                        std::cerr << "untyped init expr: " << initExpr << std::endl;
1784                )
1785                // O(N^2) checks of d-types with e-types
1786                for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
1787                        Type * toType = resolveTypeof( initAlt.type->clone(), indexer );
1788                        SymTab::validateType( toType, &indexer );
1789                        adjustExprType( toType, env, indexer );
1790                        // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
1791                        // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
1792                        // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
1793                        AlternativeFinder finder( indexer, env );
1794                        finder.targetType = toType;
1795                        finder.findWithAdjustment( initExpr->expr );
1796                        for ( Alternative & alt : finder.get_alternatives() ) {
1797                                TypeEnvironment newEnv( alt.env );
1798                                AssertionSet need;
1799                                cloneAll( alt.need, need );
1800                                AssertionSet have;
1801                                OpenVarSet openVars( alt.openVars ); 
1802                                // xxx - find things in env that don't have a "representative type" and claim
1803                                // those are open vars?
1804                                PRINT(
1805                                        std::cerr << "  @ " << toType << " " << initAlt.designation << std::endl;
1806                                )
1807                                // It's possible that a cast can throw away some values in a multiply-valued
1808                                // expression. (An example is a cast-to-void, which casts from one value to
1809                                // zero.)  Figure out the prefix of the subexpression results that are cast
1810                                // directly.  The candidate is invalid if it has fewer results than there are
1811                                // types to cast to.
1812                                int discardedValues = alt.expr->result->size() - toType->size();
1813                                if ( discardedValues < 0 ) continue;
1814                                // xxx - may need to go into tuple types and extract relevant types and use
1815                                // unifyList. Note that currently, this does not allow casting a tuple to an
1816                                // atomic type (e.g. (int)([1, 2, 3]))
1817                               
1818                                // unification run for side-effects
1819                                unify( toType, alt.expr->result, newEnv, need, have, openVars, indexer );
1820                                // xxx - do some inspecting on this line... why isn't result bound to initAlt.type?
1821
1822                                Cost thisCost = castCost( alt.expr->result, toType, indexer, newEnv );
1823                                if ( thisCost != Cost::infinity ) {
1824                                        // count one safe conversion for each value that is thrown away
1825                                        thisCost.incSafe( discardedValues );
1826                                        Alternative newAlt{ 
1827                                                new InitExpr{ 
1828                                                        restructureCast( alt.expr->clone(), toType, true ), initAlt.designation->clone() }, 
1829                                                std::move(newEnv), std::move(openVars), 
1830                                                AssertionList( need.begin(), need.end() ), alt.cost, thisCost };
1831                                        inferParameters( newAlt, back_inserter( candidates ) );
1832                                }
1833                        }
1834                }
1835
1836                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1837                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1838                // selects first based on argument cost, then on conversion cost.
1839                AltList minArgCost;
1840                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1841                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1842        }
1843
1844        void AlternativeFinder::Finder::postvisit( InitExpr * ) {
1845                assertf( false, "AlternativeFinder should never see a resolved InitExpr." );
1846        }
1847
1848        void AlternativeFinder::Finder::postvisit( DeletedExpr * ) {
1849                assertf( false, "AlternativeFinder should never see a DeletedExpr." );
1850        }
1851
1852        void AlternativeFinder::Finder::postvisit( GenericExpr * ) {
1853                assertf( false, "_Generic is not yet supported." );
1854        }
1855} // namespace ResolvExpr
1856
1857// Local Variables: //
1858// tab-width: 4 //
1859// mode: c++ //
1860// compile-command: "make install" //
1861// End: //
Note: See TracBrowser for help on using the repository browser.