source: src/ResolvExpr/AlternativeFinder.cc @ 3205495

new-envwith_gc
Last change on this file since 3205495 was 3205495, checked in by Aaron Moss <a3moss@…>, 5 years ago

Fix stack allocation in AlternativeFinder?

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