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

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

Remove assorted expression clones from AlternativeFinder?

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