source: src/ResolvExpr/AlternativeFinder.cc @ 1e8bbac9

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 1e8bbac9 was 1e8bbac9, checked in by Rob Schluntz <rschlunt@…>, 4 years ago

Refactor printAlts into AlternativeFinder?.h

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