source: src/ResolvExpr/AlternativeFinder.cc @ fae6f21

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since fae6f21 was fae6f21, checked in by Aaron Moss <a3moss@…>, 5 years ago

Fix bugs in resolver refactor with tuples/varargs

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