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

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumwith_gc
Last change on this file since 0f79853 was 0f79853, checked in by Rob Schluntz <rschlunt@…>, 6 years ago

Remove conversion cost for default arguments

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