source: src/ResolvExpr/AlternativeFinder.cc @ 11094d9

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

Fix duplicate anonymous member alternative generation

  • Property mode set to 100644
File size: 65.6 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                // use a new list so that alternatives are not examined by addAnonConversions twice.
1010                AltList winners;
1011                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) );
1012
1013                // function may return struct or union value, in which case we need to add alternatives for implicit
1014                // conversions to each of the anonymous members, must happen after findMinCost since anon conversions
1015                // are never the cheapest expression
1016                for ( const Alternative & alt : winners ) {
1017                        addAnonConversions( alt );
1018                }
1019                alternatives.splice( alternatives.begin(), winners );
1020
1021                if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
1022                        // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
1023                        // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
1024                        //   forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
1025                        //   const char * x = "hello world";
1026                        //   unsigned char ch = x[0];
1027                        // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
1028                        // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
1029                        // fix this issue in a more robust way.
1030                        targetType = nullptr;
1031                        visit( untypedExpr );
1032                }
1033        }
1034
1035        bool isLvalue( Expression *expr ) {
1036                // xxx - recurse into tuples?
1037                return expr->result && ( expr->get_result()->get_lvalue() || dynamic_cast< ReferenceType * >( expr->get_result() ) );
1038        }
1039
1040        void AlternativeFinder::visit( AddressExpr *addressExpr ) {
1041                AlternativeFinder finder( indexer, env );
1042                finder.find( addressExpr->get_arg() );
1043                for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
1044                        if ( isLvalue( i->expr ) ) {
1045                                alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) );
1046                        } // if
1047                } // for
1048        }
1049
1050        void AlternativeFinder::visit( LabelAddressExpr * expr ) {
1051                alternatives.push_back( Alternative( expr->clone(), env, Cost::zero) );
1052        }
1053
1054        Expression * restructureCast( Expression * argExpr, Type * toType ) {
1055                if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() && ! dynamic_cast<ReferenceType *>( toType ) ) {
1056                        // Argument expression is a tuple and the target type is not void and not a reference type.
1057                        // Cast each member of the tuple to its corresponding target type, producing the tuple of those
1058                        // cast expressions. If there are more components of the tuple than components in the target type,
1059                        // then excess components do not come out in the result expression (but UniqueExprs ensure that
1060                        // side effects will still be done).
1061                        if ( Tuples::maybeImpureIgnoreUnique( argExpr ) ) {
1062                                // expressions which may contain side effects require a single unique instance of the expression.
1063                                argExpr = new UniqueExpr( argExpr );
1064                        }
1065                        std::list< Expression * > componentExprs;
1066                        for ( unsigned int i = 0; i < toType->size(); i++ ) {
1067                                // cast each component
1068                                TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
1069                                componentExprs.push_back( restructureCast( idx, toType->getComponent( i ) ) );
1070                        }
1071                        delete argExpr;
1072                        assert( componentExprs.size() > 0 );
1073                        // produce the tuple of casts
1074                        return new TupleExpr( componentExprs );
1075                } else {
1076                        // handle normally
1077                        return new CastExpr( argExpr, toType->clone() );
1078                }
1079        }
1080
1081        void AlternativeFinder::visit( CastExpr *castExpr ) {
1082                Type *& toType = castExpr->get_result();
1083                assert( toType );
1084                toType = resolveTypeof( toType, indexer );
1085                SymTab::validateType( toType, &indexer );
1086                adjustExprType( toType, env, indexer );
1087
1088                AlternativeFinder finder( indexer, env );
1089                finder.targetType = toType;
1090                finder.findWithAdjustment( castExpr->get_arg() );
1091
1092                AltList candidates;
1093                for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
1094                        AssertionSet needAssertions, haveAssertions;
1095                        OpenVarSet openVars;
1096
1097                        // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1098                        // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1099                        // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1100                        // to.
1101                        int discardedValues = i->expr->get_result()->size() - castExpr->get_result()->size();
1102                        if ( discardedValues < 0 ) continue;
1103                        // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1104                        // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1105                        // unification run for side-effects
1106                        unify( castExpr->get_result(), i->expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer );
1107                        Cost thisCost = castCost( i->expr->get_result(), castExpr->get_result(), indexer, i->env );
1108                        if ( thisCost != Cost::infinity ) {
1109                                // count one safe conversion for each value that is thrown away
1110                                thisCost.incSafe( discardedValues );
1111                                Alternative newAlt( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost );
1112                                inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
1113                        } // if
1114                } // for
1115
1116                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1117                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1118                // selects first based on argument cost, then on conversion cost.
1119                AltList minArgCost;
1120                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1121                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1122        }
1123
1124        void AlternativeFinder::visit( VirtualCastExpr * castExpr ) {
1125                assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." );
1126                AlternativeFinder finder( indexer, env );
1127                // don't prune here, since it's guaranteed all alternatives will have the same type
1128                finder.findWithoutPrune( castExpr->get_arg() );
1129                for ( Alternative & alt : finder.alternatives ) {
1130                        alternatives.push_back( Alternative(
1131                                new VirtualCastExpr( alt.expr->clone(), castExpr->get_result()->clone() ),
1132                                alt.env, alt.cost ) );
1133                }
1134        }
1135
1136        void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
1137                AlternativeFinder funcFinder( indexer, env );
1138                funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
1139                for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
1140                        // 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
1141                        std::unique_ptr<Expression> aggrExpr( agg->expr->clone() );
1142                        Type * aggrType = aggrExpr->get_result();
1143                        if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
1144                                aggrType = aggrType->stripReferences();
1145                                aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) );
1146                        }
1147                        // find member of the given type
1148                        if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
1149                                addAggMembers( structInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
1150                        } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
1151                                addAggMembers( unionInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
1152                        } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
1153                                addTupleMembers( tupleType, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
1154                        } // if
1155                } // for
1156        }
1157
1158        void AlternativeFinder::visit( MemberExpr *memberExpr ) {
1159                alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
1160        }
1161
1162        void AlternativeFinder::visit( NameExpr *nameExpr ) {
1163                std::list< DeclarationWithType* > declList;
1164                indexer.lookupId( nameExpr->get_name(), declList );
1165                PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
1166                for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
1167                        VariableExpr newExpr( *i );
1168                        alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
1169                        PRINT(
1170                                std::cerr << "decl is ";
1171                                (*i)->print( std::cerr );
1172                                std::cerr << std::endl;
1173                                std::cerr << "newExpr is ";
1174                                newExpr.print( std::cerr );
1175                                std::cerr << std::endl;
1176                        )
1177                        renameTypes( alternatives.back().expr );
1178                        addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
1179                } // for
1180        }
1181
1182        void AlternativeFinder::visit( VariableExpr *variableExpr ) {
1183                // not sufficient to clone here, because variable's type may have changed
1184                // since the VariableExpr was originally created.
1185                alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
1186        }
1187
1188        void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
1189                alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
1190        }
1191
1192        void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
1193                if ( sizeofExpr->get_isType() ) {
1194                        Type * newType = sizeofExpr->get_type()->clone();
1195                        alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1196                } else {
1197                        // find all alternatives for the argument to sizeof
1198                        AlternativeFinder finder( indexer, env );
1199                        finder.find( sizeofExpr->get_expr() );
1200                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1201                        AltList winners;
1202                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1203                        if ( winners.size() != 1 ) {
1204                                throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
1205                        } // if
1206                        // return the lowest cost alternative for the argument
1207                        Alternative &choice = winners.front();
1208                        referenceToRvalueConversion( choice.expr );
1209                        alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1210                } // if
1211        }
1212
1213        void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
1214                if ( alignofExpr->get_isType() ) {
1215                        Type * newType = alignofExpr->get_type()->clone();
1216                        alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1217                } else {
1218                        // find all alternatives for the argument to sizeof
1219                        AlternativeFinder finder( indexer, env );
1220                        finder.find( alignofExpr->get_expr() );
1221                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1222                        AltList winners;
1223                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1224                        if ( winners.size() != 1 ) {
1225                                throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
1226                        } // if
1227                        // return the lowest cost alternative for the argument
1228                        Alternative &choice = winners.front();
1229                        referenceToRvalueConversion( choice.expr );
1230                        alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1231                } // if
1232        }
1233
1234        template< typename StructOrUnionType >
1235        void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
1236                std::list< Declaration* > members;
1237                aggInst->lookup( name, members );
1238                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
1239                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
1240                                alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
1241                                renameTypes( alternatives.back().expr );
1242                        } else {
1243                                assert( false );
1244                        }
1245                }
1246        }
1247
1248        void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
1249                AlternativeFinder funcFinder( indexer, env );
1250                // xxx - resolveTypeof?
1251                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
1252                        addOffsetof( structInst, offsetofExpr->get_member() );
1253                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
1254                        addOffsetof( unionInst, offsetofExpr->get_member() );
1255                }
1256        }
1257
1258        void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
1259                alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
1260        }
1261
1262        void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
1263                alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
1264        }
1265
1266        void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) {
1267                // assume no polymorphism
1268                // assume no implicit conversions
1269                assert( function->get_parameters().size() == 1 );
1270                PRINT(
1271                        std::cerr << "resolvAttr: funcDecl is ";
1272                        funcDecl->print( std::cerr );
1273                        std::cerr << " argType is ";
1274                        argType->print( std::cerr );
1275                        std::cerr << std::endl;
1276                )
1277                if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1278                        alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
1279                        for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
1280                                alternatives.back().expr->set_result( (*i)->get_type()->clone() );
1281                        } // for
1282                } // if
1283        }
1284
1285        void AlternativeFinder::visit( AttrExpr *attrExpr ) {
1286                // assume no 'pointer-to-attribute'
1287                NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1288                assert( nameExpr );
1289                std::list< DeclarationWithType* > attrList;
1290                indexer.lookupId( nameExpr->get_name(), attrList );
1291                if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1292                        for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1293                                // check if the type is function
1294                                if ( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) {
1295                                        // assume exactly one parameter
1296                                        if ( function->get_parameters().size() == 1 ) {
1297                                                if ( attrExpr->get_isType() ) {
1298                                                        resolveAttr( *i, function, attrExpr->get_type(), env );
1299                                                } else {
1300                                                        AlternativeFinder finder( indexer, env );
1301                                                        finder.find( attrExpr->get_expr() );
1302                                                        for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1303                                                                if ( choice->expr->get_result()->size() == 1 ) {
1304                                                                        resolveAttr(*i, function, choice->expr->get_result(), choice->env );
1305                                                                } // fi
1306                                                        } // for
1307                                                } // if
1308                                        } // if
1309                                } // if
1310                        } // for
1311                } else {
1312                        for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1313                                VariableExpr newExpr( *i );
1314                                alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
1315                                renameTypes( alternatives.back().expr );
1316                        } // for
1317                } // if
1318        }
1319
1320        void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
1321                AlternativeFinder firstFinder( indexer, env );
1322                firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1323                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1324                        AlternativeFinder secondFinder( indexer, first->env );
1325                        secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1326                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1327                                LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
1328                                alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
1329                        }
1330                }
1331        }
1332
1333        void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
1334                // find alternatives for condition
1335                AlternativeFinder firstFinder( indexer, env );
1336                firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
1337                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1338                        // find alternatives for true expression
1339                        AlternativeFinder secondFinder( indexer, first->env );
1340                        secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
1341                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1342                                // find alterantives for false expression
1343                                AlternativeFinder thirdFinder( indexer, second->env );
1344                                thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
1345                                for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
1346                                        // unify true and false types, then infer parameters to produce new alternatives
1347                                        OpenVarSet openVars;
1348                                        AssertionSet needAssertions, haveAssertions;
1349                                        Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
1350                                        Type* commonType = nullptr;
1351                                        if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1352                                                ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
1353                                                newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
1354                                                // convert both options to the conditional result type
1355                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env );
1356                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
1357                                                newAlt.expr = newExpr;
1358                                                inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1359                                        } // if
1360                                } // for
1361                        } // for
1362                } // for
1363        }
1364
1365        void AlternativeFinder::visit( CommaExpr *commaExpr ) {
1366                TypeEnvironment newEnv( env );
1367                Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1368                AlternativeFinder secondFinder( indexer, newEnv );
1369                secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1370                for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
1371                        alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
1372                } // for
1373                delete newFirstArg;
1374        }
1375
1376        void AlternativeFinder::visit( RangeExpr * rangeExpr ) {
1377                // resolve low and high, accept alternatives whose low and high types unify
1378                AlternativeFinder firstFinder( indexer, env );
1379                firstFinder.findWithAdjustment( rangeExpr->get_low() );
1380                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1381                        AlternativeFinder secondFinder( indexer, first->env );
1382                        secondFinder.findWithAdjustment( rangeExpr->get_high() );
1383                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1384                                OpenVarSet openVars;
1385                                AssertionSet needAssertions, haveAssertions;
1386                                Alternative newAlt( 0, second->env, first->cost + second->cost );
1387                                Type* commonType = nullptr;
1388                                if ( unify( first->expr->get_result(), second->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1389                                        RangeExpr *newExpr = new RangeExpr( first->expr->clone(), second->expr->clone() );
1390                                        newExpr->set_result( commonType ? commonType : first->expr->get_result()->clone() );
1391                                        newAlt.expr = newExpr;
1392                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1393                                } // if
1394                        } // for
1395                } // for
1396        }
1397
1398        void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
1399                std::list< AlternativeFinder > subExprAlternatives;
1400                findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
1401                std::list< AltList > possibilities;
1402                combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
1403                for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
1404                        std::list< Expression * > exprs;
1405                        makeExprList( *i, exprs );
1406
1407                        TypeEnvironment compositeEnv;
1408                        simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
1409                        alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) );
1410                } // for
1411        }
1412
1413        void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
1414                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1415        }
1416
1417        void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1418                alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
1419        }
1420
1421        void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
1422                AlternativeFinder finder( indexer, env );
1423                // don't prune here, since it's guaranteed all alternatives will have the same type
1424                // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1425                finder.findWithoutPrune( ctorExpr->get_callExpr() );
1426                for ( Alternative & alt : finder.alternatives ) {
1427                        alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
1428                }
1429        }
1430
1431        void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
1432                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1433        }
1434
1435        void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
1436                alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
1437        }
1438
1439        void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
1440                AlternativeFinder finder( indexer, env );
1441                finder.findWithAdjustment( unqExpr->get_expr() );
1442                for ( Alternative & alt : finder.alternatives ) {
1443                        // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
1444                        UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
1445                        alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
1446                }
1447        }
1448
1449        void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
1450                StmtExpr * newStmtExpr = stmtExpr->clone();
1451                ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1452                // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1453                alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
1454        }
1455
1456        void AlternativeFinder::visit( UntypedInitExpr *initExpr ) {
1457                // handle each option like a cast
1458                AltList candidates;
1459                PRINT( std::cerr << "untyped init expr: " << initExpr << std::endl; )
1460                // O(N^2) checks of d-types with e-types
1461                for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
1462                        Type * toType = resolveTypeof( initAlt.type->clone(), indexer );
1463                        SymTab::validateType( toType, &indexer );
1464                        adjustExprType( toType, env, indexer );
1465                        // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
1466                        // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
1467                        // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
1468                        AlternativeFinder finder( indexer, env );
1469                        finder.targetType = toType;
1470                        finder.findWithAdjustment( initExpr->get_expr() );
1471                        for ( Alternative & alt : finder.get_alternatives() ) {
1472                                TypeEnvironment newEnv( alt.env );
1473                                AssertionSet needAssertions, haveAssertions;
1474                                OpenVarSet openVars;  // find things in env that don't have a "representative type" and claim those are open vars?
1475                                PRINT( std::cerr << "  @ " << toType << " " << initAlt.designation << std::endl; )
1476                                // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1477                                // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1478                                // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1479                                // to.
1480                                int discardedValues = alt.expr->get_result()->size() - toType->size();
1481                                if ( discardedValues < 0 ) continue;
1482                                // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1483                                // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1484                                // unification run for side-effects
1485                                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??
1486
1487                                Cost thisCost = castCost( alt.expr->get_result(), toType, indexer, newEnv );
1488                                if ( thisCost != Cost::infinity ) {
1489                                        // count one safe conversion for each value that is thrown away
1490                                        thisCost.incSafe( discardedValues );
1491                                        Alternative newAlt( new InitExpr( restructureCast( alt.expr->clone(), toType ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost );
1492                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
1493                                }
1494                        }
1495                }
1496
1497                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1498                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1499                // selects first based on argument cost, then on conversion cost.
1500                AltList minArgCost;
1501                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1502                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1503        }
1504} // namespace ResolvExpr
1505
1506// Local Variables: //
1507// tab-width: 4 //
1508// mode: c++ //
1509// compile-command: "make install" //
1510// End: //
Note: See TracBrowser for help on using the repository browser.