source: src/ResolvExpr/AlternativeFinder.cc @ 3f7e12c

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 3f7e12c was 3f7e12c, checked in by Aaron Moss <a3moss@…>, 4 years ago

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

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