source: src/ResolvExpr/AlternativeFinder.cc @ 7e4c4f4

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

Update debug prints in AlternativeFinder?

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