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

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

stop eagerly copying EqvClass? on lookup

  • Property mode set to 100644
File size: 72.4 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                                        if ( const EqvClass *eqvClass = func->env.lookup( typeInst->get_name() ) ) {
1112                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass->type ) ) {
1113                                                        Alternative newFunc( *func );
1114                                                        referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1115                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
1116                                                                std::back_inserter( candidates ) );
1117                                                } // if
1118                                        } // if
1119                                }
1120                        } catch ( SemanticErrorException &e ) {
1121                                errors.append( e );
1122                        }
1123                } // for
1124
1125                // try each function operator ?() with each function alternative
1126                if ( ! funcOpFinder.alternatives.empty() ) {
1127                        // add exploded function alternatives to front of argument list
1128                        std::vector<ExplodedActual> funcE;
1129                        funcE.reserve( funcFinder.alternatives.size() );
1130                        for ( const Alternative& actual : funcFinder ) {
1131                                funcE.emplace_back( actual, indexer );
1132                        }
1133                        argExpansions.insert( argExpansions.begin(), move(funcE) );
1134
1135                        for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
1136                                        funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
1137                                try {
1138                                        // check if type is a pointer to function
1139                                        if ( PointerType* pointer = dynamic_cast<PointerType*>(
1140                                                        funcOp->expr->get_result()->stripReferences() ) ) {
1141                                                if ( FunctionType* function =
1142                                                                dynamic_cast<FunctionType*>( pointer->get_base() ) ) {
1143                                                        Alternative newFunc( *funcOp );
1144                                                        referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1145                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
1146                                                                std::back_inserter( candidates ) );
1147                                                }
1148                                        }
1149                                } catch ( SemanticErrorException &e ) {
1150                                        errors.append( e );
1151                                }
1152                        }
1153                }
1154
1155                // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
1156                if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
1157
1158                // compute conversionsion costs
1159                for ( Alternative& withFunc : candidates ) {
1160                        Cost cvtCost = computeApplicationConversionCost( withFunc, indexer );
1161
1162                        PRINT(
1163                                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr );
1164                                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
1165                                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
1166                                std::cerr << "Case +++++++++++++ " << appExpr->get_function() << std::endl;
1167                                std::cerr << "formals are:" << std::endl;
1168                                printAll( function->get_parameters(), std::cerr, 8 );
1169                                std::cerr << "actuals are:" << std::endl;
1170                                printAll( appExpr->get_args(), std::cerr, 8 );
1171                                std::cerr << "bindings are:" << std::endl;
1172                                withFunc.env.print( std::cerr, 8 );
1173                                std::cerr << "cost of conversion is:" << cvtCost << std::endl;
1174                        )
1175                        if ( cvtCost != Cost::infinity ) {
1176                                withFunc.cvtCost = cvtCost;
1177                                alternatives.push_back( withFunc );
1178                        } // if
1179                } // for
1180
1181                candidates = move(alternatives);
1182
1183                // use a new list so that alternatives are not examined by addAnonConversions twice.
1184                AltList winners;
1185                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) );
1186
1187                // function may return struct or union value, in which case we need to add alternatives
1188                // for implicitconversions to each of the anonymous members, must happen after findMinCost
1189                // since anon conversions are never the cheapest expression
1190                for ( const Alternative & alt : winners ) {
1191                        addAnonConversions( alt );
1192                }
1193                spliceBegin( alternatives, winners );
1194
1195                if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
1196                        // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
1197                        // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
1198                        //   forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
1199                        //   const char * x = "hello world";
1200                        //   unsigned char ch = x[0];
1201                        // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
1202                        // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
1203                        // fix this issue in a more robust way.
1204                        targetType = nullptr;
1205                        postvisit( untypedExpr );
1206                }
1207        }
1208
1209        bool isLvalue( Expression *expr ) {
1210                // xxx - recurse into tuples?
1211                return expr->result && ( expr->get_result()->get_lvalue() || dynamic_cast< ReferenceType * >( expr->get_result() ) );
1212        }
1213
1214        void AlternativeFinder::Finder::postvisit( AddressExpr *addressExpr ) {
1215                AlternativeFinder finder( indexer, env );
1216                finder.find( addressExpr->get_arg() );
1217                for ( Alternative& alt : finder.alternatives ) {
1218                        if ( isLvalue( alt.expr ) ) {
1219                                alternatives.push_back(
1220                                        Alternative{ new AddressExpr( alt.expr ), alt.env, alt.cost } );
1221                        } // if
1222                } // for
1223        }
1224
1225        void AlternativeFinder::Finder::postvisit( LabelAddressExpr * expr ) {
1226                alternatives.push_back( Alternative{ expr, env, Cost::zero } );
1227        }
1228
1229        Expression * restructureCast( Expression * argExpr, Type * toType, bool isGenerated ) {
1230                if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() && ! dynamic_cast<ReferenceType *>( toType ) ) {
1231                        // Argument expression is a tuple and the target type is not void and not a reference type.
1232                        // Cast each member of the tuple to its corresponding target type, producing the tuple of those
1233                        // cast expressions. If there are more components of the tuple than components in the target type,
1234                        // then excess components do not come out in the result expression (but UniqueExprs ensure that
1235                        // side effects will still be done).
1236                        if ( Tuples::maybeImpureIgnoreUnique( argExpr ) ) {
1237                                // expressions which may contain side effects require a single unique instance of the expression.
1238                                argExpr = new UniqueExpr( argExpr );
1239                        }
1240                        std::list< Expression * > componentExprs;
1241                        for ( unsigned int i = 0; i < toType->size(); i++ ) {
1242                                // cast each component
1243                                TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
1244                                componentExprs.push_back( restructureCast( idx, toType->getComponent( i ), isGenerated ) );
1245                        }
1246                        assert( componentExprs.size() > 0 );
1247                        // produce the tuple of casts
1248                        return new TupleExpr( componentExprs );
1249                } else {
1250                        // handle normally
1251                        CastExpr * ret = new CastExpr( argExpr, toType->clone() );
1252                        ret->isGenerated = isGenerated;
1253                        return ret;
1254                }
1255        }
1256
1257        void AlternativeFinder::Finder::postvisit( CastExpr *castExpr ) {
1258                Type *& toType = castExpr->get_result();
1259                assert( toType );
1260                toType = resolveTypeof( toType, indexer );
1261                SymTab::validateType( toType, &indexer );
1262                adjustExprType( toType, env, indexer );
1263
1264                AlternativeFinder finder( indexer, env );
1265                finder.targetType = toType;
1266                finder.findWithAdjustment( castExpr->arg );
1267
1268                AltList candidates;
1269                for ( Alternative & alt : finder.alternatives ) {
1270                        AssertionSet needAssertions, haveAssertions;
1271                        OpenVarSet openVars;
1272
1273                        alt.env.extractOpenVars( openVars );
1274
1275                        // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1276                        // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1277                        // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1278                        // to.
1279                        int discardedValues = alt.expr->result->size() - castExpr->result->size();
1280                        if ( discardedValues < 0 ) continue;
1281                        // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1282                        // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1283                        // unification run for side-effects
1284                        unify( castExpr->result, alt.expr->result, alt.env, needAssertions,
1285                                haveAssertions, openVars, indexer );
1286                        Cost thisCost = castCost( alt.expr->result, castExpr->result, indexer,
1287                                alt.env );
1288                        PRINT(
1289                                std::cerr << "working on cast with result: " << castExpr->result << std::endl;
1290                                std::cerr << "and expr type: " << alt.expr->result << std::endl;
1291                                std::cerr << "env: " << alt.env << std::endl;
1292                        )
1293                        if ( thisCost != Cost::infinity ) {
1294                                PRINT(
1295                                        std::cerr << "has finite cost." << std::endl;
1296                                )
1297                                // count one safe conversion for each value that is thrown away
1298                                thisCost.incSafe( discardedValues );
1299                                Alternative newAlt( restructureCast( alt.expr->clone(), toType, castExpr->isGenerated ), alt.env,
1300                                        alt.cost, thisCost );
1301                                inferParameters( needAssertions, haveAssertions, newAlt, openVars,
1302                                        back_inserter( candidates ) );
1303                        } // if
1304                } // for
1305
1306                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1307                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1308                // selects first based on argument cost, then on conversion cost.
1309                AltList minArgCost;
1310                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1311                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1312        }
1313
1314        void AlternativeFinder::Finder::postvisit( VirtualCastExpr * castExpr ) {
1315                assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." );
1316                AlternativeFinder finder( indexer, env );
1317                // don't prune here, since it's guaranteed all alternatives will have the same type
1318                finder.findWithoutPrune( castExpr->get_arg() );
1319                for ( Alternative & alt : finder.alternatives ) {
1320                        alternatives.push_back( Alternative(
1321                                new VirtualCastExpr( alt.expr, castExpr->get_result()->clone() ),
1322                                alt.env, alt.cost ) );
1323                }
1324        }
1325
1326        namespace {
1327                /// Gets name from untyped member expression (member must be NameExpr)
1328                const std::string& get_member_name( UntypedMemberExpr *memberExpr ) {
1329                        NameExpr * nameExpr = dynamic_cast< NameExpr * >( memberExpr->get_member() );
1330                        assert( nameExpr );
1331                        return nameExpr->get_name();
1332                }
1333        }
1334
1335        void AlternativeFinder::Finder::postvisit( UntypedMemberExpr *memberExpr ) {
1336                AlternativeFinder funcFinder( indexer, env );
1337                funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
1338                for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
1339                        // 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
1340                        Cost cost = agg->cost;
1341                        Expression * aggrExpr = agg->expr->clone();
1342                        referenceToRvalueConversion( aggrExpr, cost );
1343
1344                        // find member of the given type
1345                        if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
1346                                addAggMembers( structInst, aggrExpr, cost, agg->env, get_member_name(memberExpr) );
1347                        } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
1348                                addAggMembers( unionInst, aggrExpr, cost, agg->env, get_member_name(memberExpr) );
1349                        } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
1350                                addTupleMembers( tupleType, aggrExpr, cost, agg->env, memberExpr->get_member() );
1351                        } // if
1352                } // for
1353        }
1354
1355        void AlternativeFinder::Finder::postvisit( MemberExpr *memberExpr ) {
1356                alternatives.push_back( Alternative( memberExpr, env, Cost::zero ) );
1357        }
1358
1359        void AlternativeFinder::Finder::postvisit( NameExpr *nameExpr ) {
1360                std::list< SymTab::Indexer::IdData > declList;
1361                indexer.lookupId( nameExpr->name, declList );
1362                PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )
1363                for ( auto & data : declList ) {
1364                        Cost cost = Cost::zero;
1365                        Expression * newExpr = data.combine( cost );
1366                        alternatives.push_back( Alternative( newExpr, env, Cost::zero, cost ) );
1367                        PRINT(
1368                                std::cerr << "decl is ";
1369                                data.id->print( std::cerr );
1370                                std::cerr << std::endl;
1371                                std::cerr << "newExpr is ";
1372                                newExpr->print( std::cerr );
1373                                std::cerr << std::endl;
1374                        )
1375                        renameTypes( alternatives.back().expr );
1376                        addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
1377                } // for
1378        }
1379
1380        void AlternativeFinder::Finder::postvisit( VariableExpr *variableExpr ) {
1381                // not sufficient to clone here, because variable's type may have changed
1382                // since the VariableExpr was originally created.
1383                alternatives.push_back( Alternative( new VariableExpr( variableExpr->var ), env, Cost::zero ) );
1384        }
1385
1386        void AlternativeFinder::Finder::postvisit( ConstantExpr *constantExpr ) {
1387                alternatives.push_back( Alternative( constantExpr, env, Cost::zero ) );
1388        }
1389
1390        void AlternativeFinder::Finder::postvisit( SizeofExpr *sizeofExpr ) {
1391                if ( sizeofExpr->get_isType() ) {
1392                        Type * newType = sizeofExpr->get_type()->clone();
1393                        alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1394                } else {
1395                        // find all alternatives for the argument to sizeof
1396                        AlternativeFinder finder( indexer, env );
1397                        finder.find( sizeofExpr->get_expr() );
1398                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1399                        AltList winners;
1400                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1401                        if ( winners.size() != 1 ) {
1402                                SemanticError( sizeofExpr->get_expr(), "Ambiguous expression in sizeof operand: " );
1403                        } // if
1404                        // return the lowest cost alternative for the argument
1405                        Alternative &choice = winners.front();
1406                        referenceToRvalueConversion( choice.expr, choice.cost );
1407                        alternatives.push_back( Alternative( new SizeofExpr( choice.expr ), choice.env, Cost::zero ) );
1408                } // if
1409        }
1410
1411        void AlternativeFinder::Finder::postvisit( AlignofExpr *alignofExpr ) {
1412                if ( alignofExpr->get_isType() ) {
1413                        Type * newType = alignofExpr->get_type()->clone();
1414                        alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1415                } else {
1416                        // find all alternatives for the argument to sizeof
1417                        AlternativeFinder finder( indexer, env );
1418                        finder.find( alignofExpr->get_expr() );
1419                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1420                        AltList winners;
1421                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1422                        if ( winners.size() != 1 ) {
1423                                SemanticError( alignofExpr->get_expr(), "Ambiguous expression in alignof operand: " );
1424                        } // if
1425                        // return the lowest cost alternative for the argument
1426                        Alternative &choice = winners.front();
1427                        referenceToRvalueConversion( choice.expr, choice.cost );
1428                        alternatives.push_back( Alternative( new AlignofExpr( choice.expr ), choice.env, Cost::zero ) );
1429                } // if
1430        }
1431
1432        template< typename StructOrUnionType >
1433        void AlternativeFinder::Finder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
1434                std::list< Declaration* > members;
1435                aggInst->lookup( name, members );
1436                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
1437                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
1438                                alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
1439                                renameTypes( alternatives.back().expr );
1440                        } else {
1441                                assert( false );
1442                        }
1443                }
1444        }
1445
1446        void AlternativeFinder::Finder::postvisit( UntypedOffsetofExpr *offsetofExpr ) {
1447                AlternativeFinder funcFinder( indexer, env );
1448                // xxx - resolveTypeof?
1449                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
1450                        addOffsetof( structInst, offsetofExpr->member );
1451                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
1452                        addOffsetof( unionInst, offsetofExpr->member );
1453                }
1454        }
1455
1456        void AlternativeFinder::Finder::postvisit( OffsetofExpr *offsetofExpr ) {
1457                alternatives.push_back( Alternative( offsetofExpr, env, Cost::zero ) );
1458        }
1459
1460        void AlternativeFinder::Finder::postvisit( OffsetPackExpr *offsetPackExpr ) {
1461                alternatives.push_back( Alternative( offsetPackExpr, env, Cost::zero ) );
1462        }
1463
1464        namespace {
1465                void resolveAttr( SymTab::Indexer::IdData data, FunctionType *function, Type *argType, const TypeEnvironment &env, AlternativeFinder & finder ) {
1466                        // assume no polymorphism
1467                        // assume no implicit conversions
1468                        assert( function->get_parameters().size() == 1 );
1469                        PRINT(
1470                                std::cerr << "resolvAttr: funcDecl is ";
1471                                data.id->print( std::cerr );
1472                                std::cerr << " argType is ";
1473                                argType->print( std::cerr );
1474                                std::cerr << std::endl;
1475                        )
1476                        const SymTab::Indexer & indexer = finder.get_indexer();
1477                        AltList & alternatives = finder.get_alternatives();
1478                        if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1479                                Cost cost = Cost::zero;
1480                                Expression * newExpr = data.combine( cost );
1481                                alternatives.push_back( Alternative( new AttrExpr( newExpr, argType->clone() ), env, Cost::zero, cost ) );
1482                                for ( DeclarationWithType * retVal : function->returnVals ) {
1483                                        alternatives.back().expr->result = retVal->get_type()->clone();
1484                                } // for
1485                        } // if
1486                }
1487        }
1488
1489        void AlternativeFinder::Finder::postvisit( AttrExpr *attrExpr ) {
1490                // assume no 'pointer-to-attribute'
1491                NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1492                assert( nameExpr );
1493                std::list< SymTab::Indexer::IdData > attrList;
1494                indexer.lookupId( nameExpr->get_name(), attrList );
1495                if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1496                        for ( auto & data : attrList ) {
1497                                DeclarationWithType * id = data.id;
1498                                // check if the type is function
1499                                if ( FunctionType *function = dynamic_cast< FunctionType* >( id->get_type() ) ) {
1500                                        // assume exactly one parameter
1501                                        if ( function->get_parameters().size() == 1 ) {
1502                                                if ( attrExpr->get_isType() ) {
1503                                                        resolveAttr( data, function, attrExpr->get_type(), env, altFinder);
1504                                                } else {
1505                                                        AlternativeFinder finder( indexer, env );
1506                                                        finder.find( attrExpr->get_expr() );
1507                                                        for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1508                                                                if ( choice->expr->get_result()->size() == 1 ) {
1509                                                                        resolveAttr(data, function, choice->expr->get_result(), choice->env, altFinder );
1510                                                                } // fi
1511                                                        } // for
1512                                                } // if
1513                                        } // if
1514                                } // if
1515                        } // for
1516                } else {
1517                        for ( auto & data : attrList ) {
1518                                Cost cost = Cost::zero;
1519                                Expression * newExpr = data.combine( cost );
1520                                alternatives.push_back( Alternative( newExpr, env, Cost::zero, cost ) );
1521                                renameTypes( alternatives.back().expr );
1522                        } // for
1523                } // if
1524        }
1525
1526        void AlternativeFinder::Finder::postvisit( LogicalExpr *logicalExpr ) {
1527                AlternativeFinder firstFinder( indexer, env );
1528                firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1529                if ( firstFinder.alternatives.empty() ) return;
1530                AlternativeFinder secondFinder( indexer, env );
1531                secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1532                if ( secondFinder.alternatives.empty() ) return;
1533                for ( const Alternative & first : firstFinder.alternatives ) {
1534                        for ( const Alternative & second : secondFinder.alternatives ) {
1535                                TypeEnvironment compositeEnv;
1536                                compositeEnv.simpleCombine( first.env );
1537                                compositeEnv.simpleCombine( second.env );
1538
1539                                LogicalExpr *newExpr = new LogicalExpr( first.expr, second.expr, logicalExpr->get_isAnd() );
1540                                alternatives.push_back( Alternative( newExpr, compositeEnv, first.cost + second.cost ) );
1541                        }
1542                }
1543        }
1544
1545        void AlternativeFinder::Finder::postvisit( ConditionalExpr *conditionalExpr ) {
1546                // find alternatives for condition
1547                AlternativeFinder firstFinder( indexer, env );
1548                firstFinder.findWithAdjustment( conditionalExpr->arg1 );
1549                if ( firstFinder.alternatives.empty() ) return;
1550                // find alternatives for true expression
1551                AlternativeFinder secondFinder( indexer, env );
1552                secondFinder.findWithAdjustment( conditionalExpr->arg2 );
1553                if ( secondFinder.alternatives.empty() ) return;
1554                // find alterantives for false expression
1555                AlternativeFinder thirdFinder( indexer, env );
1556                thirdFinder.findWithAdjustment( conditionalExpr->arg3 );
1557                if ( thirdFinder.alternatives.empty() ) return;
1558                for ( const Alternative & first : firstFinder.alternatives ) {
1559                        for ( const Alternative & second : secondFinder.alternatives ) {
1560                                for ( const Alternative & third : thirdFinder.alternatives ) {
1561                                        TypeEnvironment compositeEnv;
1562                                        compositeEnv.simpleCombine( first.env );
1563                                        compositeEnv.simpleCombine( second.env );
1564                                        compositeEnv.simpleCombine( third.env );
1565
1566                                        // unify true and false types, then infer parameters to produce new alternatives
1567                                        OpenVarSet openVars;
1568                                        AssertionSet needAssertions, haveAssertions;
1569                                        Alternative newAlt( 0, compositeEnv, first.cost + second.cost + third.cost );
1570                                        Type* commonType = nullptr;
1571                                        if ( unify( second.expr->result, third.expr->result, newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1572                                                ConditionalExpr *newExpr = new ConditionalExpr( first.expr, second.expr, third.expr );
1573                                                newExpr->result = commonType ? commonType : second.expr->result->clone();
1574                                                // convert both options to the conditional result type
1575                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env );
1576                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
1577                                                newAlt.expr = newExpr;
1578                                                inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1579                                        } // if
1580                                } // for
1581                        } // for
1582                } // for
1583        }
1584
1585        void AlternativeFinder::Finder::postvisit( CommaExpr *commaExpr ) {
1586                TypeEnvironment newEnv( env );
1587                Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1588                AlternativeFinder secondFinder( indexer, newEnv );
1589                secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1590                for ( const Alternative & alt : secondFinder.alternatives ) {
1591                        alternatives.push_back( Alternative( new CommaExpr( newFirstArg, alt.expr ), alt.env, alt.cost ) );
1592                } // for
1593        }
1594
1595        void AlternativeFinder::Finder::postvisit( RangeExpr * rangeExpr ) {
1596                // resolve low and high, accept alternatives whose low and high types unify
1597                AlternativeFinder firstFinder( indexer, env );
1598                firstFinder.findWithAdjustment( rangeExpr->low );
1599                if ( firstFinder.alternatives.empty() ) return;
1600                AlternativeFinder secondFinder( indexer, env );
1601                secondFinder.findWithAdjustment( rangeExpr->high );
1602                if ( secondFinder.alternatives.empty() ) return;
1603                for ( const Alternative & first : firstFinder.alternatives ) {
1604                        for ( const Alternative & second : secondFinder.alternatives ) {
1605                                TypeEnvironment compositeEnv;
1606                                compositeEnv.simpleCombine( first.env );
1607                                compositeEnv.simpleCombine( second.env );
1608                                OpenVarSet openVars;
1609                                AssertionSet needAssertions, haveAssertions;
1610                                Alternative newAlt( 0, compositeEnv, first.cost + second.cost );
1611                                Type* commonType = nullptr;
1612                                if ( unify( first.expr->result, second.expr->result, newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1613                                        RangeExpr * newExpr = new RangeExpr( first.expr, second.expr );
1614                                        newExpr->result = commonType ? commonType : first.expr->result->clone();
1615                                        newAlt.expr = newExpr;
1616                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1617                                } // if
1618                        } // for
1619                } // for
1620        }
1621
1622        void AlternativeFinder::Finder::postvisit( UntypedTupleExpr *tupleExpr ) {
1623                std::vector< AlternativeFinder > subExprAlternatives;
1624                altFinder.findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(),
1625                        back_inserter( subExprAlternatives ) );
1626                std::vector< AltList > possibilities;
1627                combos( subExprAlternatives.begin(), subExprAlternatives.end(),
1628                        back_inserter( possibilities ) );
1629                for ( const AltList& alts : possibilities ) {
1630                        std::list< Expression * > exprs;
1631                        makeExprList( alts, exprs );
1632
1633                        TypeEnvironment compositeEnv;
1634                        simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
1635                        alternatives.push_back(
1636                                Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } );
1637                } // for
1638        }
1639
1640        void AlternativeFinder::Finder::postvisit( TupleExpr *tupleExpr ) {
1641                alternatives.push_back( Alternative( tupleExpr, env, Cost::zero ) );
1642        }
1643
1644        void AlternativeFinder::Finder::postvisit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1645                alternatives.push_back( Alternative( impCpCtorExpr, env, Cost::zero ) );
1646        }
1647
1648        void AlternativeFinder::Finder::postvisit( ConstructorExpr * ctorExpr ) {
1649                AlternativeFinder finder( indexer, env );
1650                // don't prune here, since it's guaranteed all alternatives will have the same type
1651                // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1652                finder.findWithoutPrune( ctorExpr->get_callExpr() );
1653                for ( Alternative & alt : finder.alternatives ) {
1654                        alternatives.push_back( Alternative( new ConstructorExpr( alt.expr ), alt.env, alt.cost ) );
1655                }
1656        }
1657
1658        void AlternativeFinder::Finder::postvisit( TupleIndexExpr *tupleExpr ) {
1659                alternatives.push_back( Alternative( tupleExpr, env, Cost::zero ) );
1660        }
1661
1662        void AlternativeFinder::Finder::postvisit( TupleAssignExpr *tupleAssignExpr ) {
1663                alternatives.push_back( Alternative( tupleAssignExpr, env, Cost::zero ) );
1664        }
1665
1666        void AlternativeFinder::Finder::postvisit( UniqueExpr *unqExpr ) {
1667                AlternativeFinder finder( indexer, env );
1668                finder.findWithAdjustment( unqExpr->get_expr() );
1669                for ( Alternative & alt : finder.alternatives ) {
1670                        // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
1671                        UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr, unqExpr->get_id() );
1672                        alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
1673                }
1674        }
1675
1676        void AlternativeFinder::Finder::postvisit( StmtExpr *stmtExpr ) {
1677                StmtExpr * newStmtExpr = stmtExpr->clone();
1678                ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1679                // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1680                alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
1681        }
1682
1683        void AlternativeFinder::Finder::postvisit( UntypedInitExpr *initExpr ) {
1684                // handle each option like a cast
1685                AltList candidates;
1686                PRINT(
1687                        std::cerr << "untyped init expr: " << initExpr << std::endl;
1688                )
1689                // O(N^2) checks of d-types with e-types
1690                for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
1691                        Type * toType = resolveTypeof( initAlt.type->clone(), indexer );
1692                        SymTab::validateType( toType, &indexer );
1693                        adjustExprType( toType, env, indexer );
1694                        // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
1695                        // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
1696                        // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
1697                        AlternativeFinder finder( indexer, env );
1698                        finder.targetType = toType;
1699                        finder.findWithAdjustment( initExpr->expr );
1700                        for ( Alternative & alt : finder.get_alternatives() ) {
1701                                TypeEnvironment newEnv( alt.env );
1702                                AssertionSet needAssertions, haveAssertions;
1703                                OpenVarSet openVars;  // find things in env that don't have a "representative type" and claim those are open vars?
1704                                PRINT(
1705                                        std::cerr << "  @ " << toType << " " << initAlt.designation << std::endl;
1706                                )
1707                                // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1708                                // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1709                                // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1710                                // to.
1711                                int discardedValues = alt.expr->result->size() - toType->size();
1712                                if ( discardedValues < 0 ) continue;
1713                                // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1714                                // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1715                                // unification run for side-effects
1716                                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??
1717
1718                                Cost thisCost = castCost( alt.expr->result, toType, indexer, newEnv );
1719                                if ( thisCost != Cost::infinity ) {
1720                                        // count one safe conversion for each value that is thrown away
1721                                        thisCost.incSafe( discardedValues );
1722                                        Alternative newAlt( new InitExpr( restructureCast( alt.expr, toType, true ), initAlt.designation ), newEnv, alt.cost, thisCost );
1723                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
1724                                }
1725                        }
1726                }
1727
1728                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1729                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1730                // selects first based on argument cost, then on conversion cost.
1731                AltList minArgCost;
1732                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1733                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1734        }
1735
1736        void AlternativeFinder::Finder::postvisit( InitExpr * ) {
1737                assertf( false, "AlternativeFinder should never see a resolved InitExpr." );
1738        }
1739
1740        void AlternativeFinder::Finder::postvisit( DeletedExpr * ) {
1741                assertf( false, "AlternativeFinder should never see a DeletedExpr." );
1742        }
1743} // namespace ResolvExpr
1744
1745// Local Variables: //
1746// tab-width: 4 //
1747// mode: c++ //
1748// compile-command: "make install" //
1749// End: //
Note: See TracBrowser for help on using the repository browser.