source: src/ResolvExpr/AlternativeFinder.cc @ 2c187378

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

Fix memory bugs in deferred resolution

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