source: src/ResolvExpr/AlternativeFinder.cc @ d1e0979

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

Add a basic demangler that works for basic types, pointers, tuples, and functions

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