source: src/ResolvExpr/AlternativeFinder.cc @ 00ac42e

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerwith_gc
Last change on this file since 00ac42e was 00ac42e, checked in by Aaron Moss <a3moss@…>, 4 years ago

stop eagerly copying EqvClass? on lookup

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