source: src/ResolvExpr/AlternativeFinder.cc @ 5af7306

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

Assorted bug fixes

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