source: src/ResolvExpr/AlternativeFinder.cc @ 8d7bef2

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

First compiling build of CFA-CC with GC

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