source: src/ResolvExpr/AlternativeFinder.cc @ aeb75b1

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

First draft of iterative bottom-up resolver [BROKEN]

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