source: src/ResolvExpr/AlternativeFinder.cc @ d807ca2

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerwith_gc
Last change on this file since d807ca2 was d807ca2, checked in by Rob Schluntz <rschlunt@…>, 4 years ago

Add AST support for _Generic, along with C codegen

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