source: src/ResolvExpr/AlternativeFinder.cc @ c43c171

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

Add tuple handling to iterative resolver rewrite

  • Property mode set to 100644
File size: 65.8 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, TypeEnvironment&& env, 
582                                OpenVarSet&& openVars, const Cost& cost = Cost::zero)
583                        : actuals(old.actuals), env(std::move(env)), need(old.need), have(old.have), 
584                          openVars(std::move(openVars)), nextArg(old.nextArg + 1), tupleEls(old.tupleEls) {
585                        // add new actual
586                        actuals.emplace_back( actual, this->env, cost );
587                        // count tuple elements, if applicable
588                        if ( ! tupleEls.empty() ) ++tupleEls.back();
589                }
590               
591                ArgPack(const ArgPack& old, Expression* actual, TypeEnvironment&& env, AssertionSet&& need, 
592                                AssertionSet&& have, OpenVarSet&& openVars, const Cost& cost = Cost::zero)
593                        : actuals(old.actuals), env(std::move(env)), need(std::move(need)), 
594                          have(std::move(have)), openVars(std::move(openVars)), nextArg(old.nextArg + 1), 
595                          tupleEls(old.tupleEls) {
596                        // add new actual
597                        actuals.emplace_back( actual, this->env, cost );
598                        // count tuple elements, if applicable
599                        if ( ! tupleEls.empty() ) ++tupleEls.back();
600                }
601
602                /// Starts a new tuple expression
603                void beginTuple() {
604                        if ( ! tupleEls.empty() ) ++tupleEls.back();
605                        tupleEls.push_back(0);
606                }
607
608                /// Ends a tuple expression, consolidating the appropriate actuals
609                void endTuple() {
610                        // set up new Tuple alternative
611                        std::list<Expression*> exprs;
612                        Cost cost = Cost::zero;
613
614                        // transfer elements into alternative
615                        for (unsigned i = 0; i < tupleEls.back(); ++i) {
616                                exprs.push_front( actuals.back().expr );
617                                cost += actuals.back().cost;
618                                actuals.pop_back();
619                        }
620                        tupleEls.pop_back();
621
622                        // build new alternative
623                        actuals.emplace_back( new TupleExpr( exprs ), this->env, cost );
624                }
625        };
626
627        /// Iterates a result, exploding actuals as needed.
628        /// add is a function that takes the same parameters as this (with the exception of add)
629        template<typename F>
630        void addExplodedActual( ArgPack& result, Expression* expr, Cost cost, 
631                        std::vector<ArgPack>& nextResults, F add ) {
632                Type* res = expr->get_result()->stripReferences();
633                if ( TupleType* tupleType = dynamic_cast<TupleType*>( res ) ) {
634                        if ( TupleExpr* tupleExpr = dynamic_cast<TupleExpr*>( expr ) ) {
635                                // recursively explode tuple
636                                for ( Expression* sexpr : tupleExpr->get_exprs() ) {
637                                        addExplodedActual( result, sexpr, cost, nextResults, add );
638                                        cost = Cost::zero; // reset cost so not duplicated
639                                }
640                        } else {
641                                // tuple type, but not tuple expr - recursively index into components.
642                                // if expr type is reference, convert to value type
643                                Expression* arg = expr->clone();
644                                if ( Tuples::maybeImpureIgnoreUnique( arg ) ) {
645                                        // expressions which may contain side effects require a single unique instance of the expression.
646                                        arg = new UniqueExpr( arg );
647                                }
648                                // cast reference to value type to facilitate further explosion
649                                if ( dynamic_cast<ReferenceType*>( arg->get_result() ) ) {
650                                        arg = new CastExpr( arg, tupleType->clone() );
651                                }
652                                // explode tuple by index
653                                for ( unsigned i = 0; i < tupleType->size(); ++i ) {
654                                        TupleIndexExpr* idx = new TupleIndexExpr( arg->clone(), i );
655                                        addExplodedActual( result, idx, cost, nextResults, add );
656                                        cost = Cost::zero; // reset cost so not duplicated
657                                        delete idx;
658                                }
659                                delete arg;
660                        }
661                } else {
662                        // add non-tuple results directly
663                        add( result, expr->clone(), cost, nextResults );
664                }
665        }
666
667        /// Instantiates an argument to match a formal, returns false if no results left
668        bool instantiateArgument( Type* formalType, Initializer* initializer, 
669                        const std::vector< AlternativeFinder >& args, 
670                        std::vector<ArgPack>& results, std::vector<ArgPack>& nextResults, 
671                        const SymTab::Indexer& indexer ) {
672                if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) {
673                        // formalType is a TupleType - group actuals into a TupleExpr
674                        for ( ArgPack& result : results ) { result.beginTuple(); }
675                        for ( Type* type : *tupleType ) {
676                                // xxx - dropping initializer changes behaviour from previous, but seems correct
677                                if ( ! instantiateArgument( type, nullptr, args, results, nextResults, indexer ) ) 
678                                        return false;
679                        }
680                        for ( ArgPack& result : results ) { result.endTuple(); }
681                        return true;
682                } else if ( TypeInstType* ttype = Tuples::isTtype( formalType ) ) {
683                        // formalType is a ttype, consumes all remaining arguments
684                        // xxx - mixing default arguments with variadic??
685                        std::vector<ArgPack> finalResults{};  /// list of completed tuples
686                        // start tuples
687                        for ( ArgPack& result : results ) { result.beginTuple(); }
688                        // iterate until all results completed
689                        while ( ! results.empty() ) {
690                                // add another argument to results
691                                for ( ArgPack& result : results ) {
692                                        // finish result when out of arguments
693                                        if ( result.nextArg >= args.size() ) {
694                                                Type* argType = result.actuals.back().expr->get_result();
695                                                if ( result.tupleEls.back() == 1 && Tuples::isTtype( argType ) ) {
696                                                        // the case where a ttype value is passed directly is special, e.g. for
697                                                        // argument forwarding purposes
698                                                        // xxx - what if passing multiple arguments, last of which is ttype?
699                                                        // xxx - what would happen if unify was changed so that unifying tuple
700                                                        // types flattened both before unifying lists? then pass in TupleType
701                                                        // (ttype) below.
702                                                        result.tupleEls.pop_back();
703                                                } else {
704                                                        // collapse leftover arguments into tuple
705                                                        result.endTuple();
706                                                        argType = result.actuals.back().expr->get_result();
707                                                }
708                                                // check unification for ttype before adding to final
709                                                if ( unify( ttype, argType, result.env, result.need, result.have, 
710                                                                result.openVars, indexer ) ) {
711                                                        finalResults.emplace_back( std::move(result) );
712                                                }
713                                                continue;
714                                        }
715
716                                        // add each possible next argument
717                                        for ( const Alternative& actual : args[result.nextArg] ) {
718                                                addExplodedActual( result, actual.expr, actual.cost, nextResults, 
719                                                        [&actual]( ArgPack& result, Expression* expr, Cost cost, 
720                                                                        std::vector<ArgPack>& nextResults ) {
721                                                                TypeEnvironment env{ result.env };
722                                                                OpenVarSet openVars{ result.openVars };
723                                                                env.addActual( actual.env, openVars );
724                                                                nextResults.emplace_back( result, expr, std::move(env), 
725                                                                        std::move(openVars), cost );
726                                                        } );
727                                        }
728                                }
729
730                                // reset for next round
731                                results.swap( nextResults );
732                                nextResults.clear();
733                        }
734                        results.swap( finalResults );
735                        return ! results.empty();
736                }
737               
738                // iterate each current subresult
739                for ( ArgPack& result : results ) {
740                        if ( result.nextArg >= args.size() ) {
741                                // If run out of actuals, handle default values
742                                if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
743                                        if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
744                                                TypeEnvironment resultEnv = result.env;
745                                                AssertionSet resultNeed = result.need, resultHave = result.have;
746                                                if ( unify( formalType, cnst->get_type(), 
747                                                                resultEnv, resultNeed, resultHave, result.openVars, 
748                                                                indexer ) ) {
749                                                        nextResults.emplace_back( result, cnstExpr->clone(), 
750                                                                std::move(resultEnv), std::move(resultNeed), 
751                                                                std::move(resultHave), OpenVarSet{ result.openVars } );
752                                                }
753                                        }
754                                }
755                                continue;
756                        }
757
758                        // Check each possible next argument
759                        for ( const Alternative& actual : args[result.nextArg] ) {
760                                addExplodedActual( result, actual.expr, actual.cost, nextResults, 
761                                        [formalType,&indexer,&actual]( ArgPack& result, Expression* expr, Cost cost, 
762                                                        std::vector<ArgPack>& nextResults ) {
763                                                // attempt to unify actual with parameter
764                                                TypeEnvironment resultEnv = result.env;
765                                                AssertionSet resultNeed = result.need, resultHave = result.have;
766                                                OpenVarSet resultOpenVars = result.openVars;
767                                                resultEnv.addActual( actual.env, resultOpenVars );
768                                                Type* actualType = expr->get_result();
769
770
771                                                PRINT(
772                                                        std::cerr << "formal type is ";
773                                                        formalType->print( std::cerr );
774                                                        std::cerr << std::endl << "actual type is ";
775                                                        actualType->print( std::cerr );
776                                                        std::cerr << std::endl;
777                                                )
778
779                                                if ( unify( formalType, actualType, resultEnv, resultNeed, resultHave, 
780                                                                resultOpenVars, indexer ) ) {
781                                                        nextResults.emplace_back( result, expr->clone(), 
782                                                                std::move(resultEnv), std::move(resultNeed), std::move(resultHave),
783                                                                std::move(resultOpenVars), cost );
784                                                }
785                                        } );
786                        }
787                }
788
789                // reset for next parameter
790                results.swap( nextResults );
791                nextResults.clear();
792               
793                return ! results.empty();
794        }
795
796        template<typename OutputIterator>
797        void AlternativeFinder::makeFunctionAlternatives( const Alternative& func, 
798                        FunctionType* funcType, const std::vector< AlternativeFinder >& args, 
799                        OutputIterator out ) {
800                OpenVarSet funcOpenVars;
801                AssertionSet funcNeed, funcHave;
802                TypeEnvironment funcEnv;
803                makeUnifiableVars( funcType, funcOpenVars, funcNeed );
804                // add all type variables as open variables now so that those not used in the parameter
805                // list are still considered open.
806                funcEnv.add( funcType->get_forall() );
807
808                if ( targetType && ! targetType->isVoid() && ! funcType->get_returnVals().empty() ) {
809                        // attempt to narrow based on expected target type
810                        Type* returnType = funcType->get_returnVals().front()->get_type();
811                        if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars, 
812                                        indexer ) ) {
813                                // unification failed, don't pursue this function alternative
814                                return;
815                        }
816                }
817
818                // iteratively build matches, one parameter at a time
819                std::vector<ArgPack> results{ ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } };
820                std::vector<ArgPack> nextResults{};
821                for ( DeclarationWithType* formal : funcType->get_parameters() ) {
822                        ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal );
823                        if ( ! instantiateArgument( 
824                                        obj->get_type(), obj->get_init(), args, results, nextResults, indexer ) )
825                                return;
826                }
827
828                // filter out results that don't use all the arguments, and aren't variadic
829                std::vector<ArgPack> finalResults{};
830                if ( funcType->get_isVarArgs() ) {
831                        while ( ! results.empty() ) {
832                                // build combinations for all remaining arguments
833                                for ( ArgPack& result : results ) {
834                                        // keep if used all arguments
835                                        if ( result.nextArg >= args.size() ) {
836                                                finalResults.emplace_back( std::move(result) );
837                                                continue;
838                                        }
839
840                                        // add each possible next argument
841                                        for ( const Alternative& actual : args[result.nextArg] ) {
842                                                TypeEnvironment env{ result.env };
843                                                OpenVarSet openVars{ result.openVars };
844                                                env.addActual( actual.env, openVars );
845                                                nextResults.emplace_back( result, actual.expr, std::move(env), 
846                                                        std::move(openVars), actual.cost );
847                                        }
848                                }
849
850                                // reset for next round
851                                results.swap( nextResults );
852                                nextResults.clear();
853                        }
854                } else {
855                        // filter out results that don't use all the arguments
856                        for ( ArgPack& result : results ) {
857                                if ( result.nextArg >= args.size() ) {
858                                        finalResults.emplace_back( std::move(result) );
859                                }
860                        }
861                }
862
863                // validate matching combos, add to final result list
864                for ( ArgPack& result : finalResults ) {
865                        ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
866                        Alternative newAlt( appExpr, result.env, sumCost( result.actuals ) );
867                        makeExprList( result.actuals, appExpr->get_args() );
868                        PRINT(
869                                std::cerr << "instantiate function success: " << appExpr << std::endl;
870                                std::cerr << "need assertions:" << std::endl;
871                                printAssertionSet( result.need, std::cerr, 8 );
872                        )
873                        inferParameters( result.need, result.have, newAlt, result.openVars, out );
874                }
875        }
876
877        void AlternativeFinder::visit( UntypedExpr *untypedExpr ) {
878                AlternativeFinder funcFinder( indexer, env );
879                funcFinder.findWithAdjustment( untypedExpr->get_function() );
880                // if there are no function alternatives, then proceeding is a waste of time.
881                if ( funcFinder.alternatives.empty() ) return;
882
883                std::vector< AlternativeFinder > argAlternatives;
884                findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), 
885                        back_inserter( argAlternatives ) );
886
887                // take care of possible tuple assignments
888                // if not tuple assignment, assignment is taken care of as a normal function call
889                Tuples::handleTupleAssignment( *this, untypedExpr, argAlternatives );
890
891                // find function operators
892                AlternativeFinder funcOpFinder( indexer, env );
893                NameExpr *opExpr = new NameExpr( "?()" );
894                try {
895                        funcOpFinder.findWithAdjustment( opExpr );
896                } catch( SemanticError &e ) {
897                        // it's ok if there aren't any defined function ops
898                }
899                PRINT(
900                        std::cerr << "known function ops:" << std::endl;
901                        printAlts( funcOpFinder.alternatives, std::cerr, 8 );
902                )
903
904                AltList candidates;
905                SemanticError errors;
906                for ( AltList::iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
907                        try {
908                                PRINT(
909                                        std::cerr << "working on alternative: " << std::endl;
910                                        func->print( std::cerr, 8 );
911                                )
912                                // check if the type is pointer to function
913                                if ( PointerType *pointer = dynamic_cast< PointerType* >( func->expr->get_result()->stripReferences() ) ) {
914                                        if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
915                                                Alternative newFunc( *func );
916                                                referenceToRvalueConversion( newFunc.expr );
917                                                makeFunctionAlternatives( newFunc, function, argAlternatives, 
918                                                        std::back_inserter( candidates ) );
919                                        }
920                                } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->get_result()->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
921                                        EqvClass eqvClass;
922                                        if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) {
923                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.type ) ) {
924                                                        Alternative newFunc( *func );
925                                                        referenceToRvalueConversion( newFunc.expr );
926                                                        makeFunctionAlternatives( newFunc, function, argAlternatives, 
927                                                                std::back_inserter( candidates ) );
928                                                } // if
929                                        } // if
930                                }                       
931                        } catch ( SemanticError &e ) {
932                                errors.append( e );
933                        }
934                } // for
935
936                // try each function operator ?() with each function alternative
937                if ( ! funcOpFinder.alternatives.empty() ) {
938                        // add function alternatives to front of argument list
939                        argAlternatives.insert( argAlternatives.begin(), std::move(funcFinder) );
940
941                        for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
942                                        funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
943                                try {
944                                        // check if type is a pointer to function
945                                        if ( PointerType* pointer = dynamic_cast<PointerType*>( 
946                                                        funcOp->expr->get_result()->stripReferences() ) ) {
947                                                if ( FunctionType* function = 
948                                                                dynamic_cast<FunctionType*>( pointer->get_base() ) ) {
949                                                        Alternative newFunc( *funcOp );
950                                                        referenceToRvalueConversion( newFunc.expr );
951                                                        makeFunctionAlternatives( newFunc, function, argAlternatives, 
952                                                                std::back_inserter( candidates ) );
953                                                }
954                                        }
955                                } catch ( SemanticError &e ) {
956                                        errors.append( e );
957                                }
958                        }
959                }
960
961                // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
962                if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
963
964                // compute conversionsion costs
965                for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) {
966                        Cost cvtCost = computeApplicationConversionCost( *withFunc, indexer );
967
968                        PRINT(
969                                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc->expr );
970                                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
971                                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
972                                std::cerr << "Case +++++++++++++ " << appExpr->get_function() << std::endl;
973                                std::cerr << "formals are:" << std::endl;
974                                printAll( function->get_parameters(), std::cerr, 8 );
975                                std::cerr << "actuals are:" << std::endl;
976                                printAll( appExpr->get_args(), std::cerr, 8 );
977                                std::cerr << "bindings are:" << std::endl;
978                                withFunc->env.print( std::cerr, 8 );
979                                std::cerr << "cost of conversion is:" << cvtCost << std::endl;
980                        )
981                        if ( cvtCost != Cost::infinity ) {
982                                withFunc->cvtCost = cvtCost;
983                                alternatives.push_back( *withFunc );
984                        } // if
985                } // for
986
987                candidates.clear();
988                candidates.splice( candidates.end(), alternatives );
989
990                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) );
991
992                // function may return struct or union value, in which case we need to add alternatives for implicit
993                // conversions to each of the anonymous members, must happen after findMinCost since anon conversions
994                // are never the cheapest expression
995                for ( const Alternative & alt : alternatives ) {
996                        addAnonConversions( alt );
997                }
998
999                if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
1000                        // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
1001                        // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
1002                        //   forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
1003                        //   const char * x = "hello world";
1004                        //   unsigned char ch = x[0];
1005                        // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
1006                        // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
1007                        // fix this issue in a more robust way.
1008                        targetType = nullptr;
1009                        visit( untypedExpr );
1010                }
1011        }
1012
1013        bool isLvalue( Expression *expr ) {
1014                // xxx - recurse into tuples?
1015                return expr->has_result() && ( expr->get_result()->get_lvalue() || dynamic_cast< ReferenceType * >( expr->get_result() ) );
1016        }
1017
1018        void AlternativeFinder::visit( AddressExpr *addressExpr ) {
1019                AlternativeFinder finder( indexer, env );
1020                finder.find( addressExpr->get_arg() );
1021                for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
1022                        if ( isLvalue( i->expr ) ) {
1023                                alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) );
1024                        } // if
1025                } // for
1026        }
1027
1028        void AlternativeFinder::visit( LabelAddressExpr * expr ) {
1029                alternatives.push_back( Alternative( expr->clone(), env, Cost::zero) );
1030        }
1031
1032        Expression * restructureCast( Expression * argExpr, Type * toType ) {
1033                if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() && ! dynamic_cast<ReferenceType *>( toType ) ) {
1034                        // Argument expression is a tuple and the target type is not void and not a reference type.
1035                        // Cast each member of the tuple to its corresponding target type, producing the tuple of those
1036                        // cast expressions. If there are more components of the tuple than components in the target type,
1037                        // then excess components do not come out in the result expression (but UniqueExprs ensure that
1038                        // side effects will still be done).
1039                        if ( Tuples::maybeImpureIgnoreUnique( argExpr ) ) {
1040                                // expressions which may contain side effects require a single unique instance of the expression.
1041                                argExpr = new UniqueExpr( argExpr );
1042                        }
1043                        std::list< Expression * > componentExprs;
1044                        for ( unsigned int i = 0; i < toType->size(); i++ ) {
1045                                // cast each component
1046                                TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
1047                                componentExprs.push_back( restructureCast( idx, toType->getComponent( i ) ) );
1048                        }
1049                        delete argExpr;
1050                        assert( componentExprs.size() > 0 );
1051                        // produce the tuple of casts
1052                        return new TupleExpr( componentExprs );
1053                } else {
1054                        // handle normally
1055                        return new CastExpr( argExpr, toType->clone() );
1056                }
1057        }
1058
1059        void AlternativeFinder::visit( CastExpr *castExpr ) {
1060                Type *& toType = castExpr->get_result();
1061                assert( toType );
1062                toType = resolveTypeof( toType, indexer );
1063                SymTab::validateType( toType, &indexer );
1064                adjustExprType( toType, env, indexer );
1065
1066                AlternativeFinder finder( indexer, env );
1067                finder.targetType = toType;
1068                finder.findWithAdjustment( castExpr->get_arg() );
1069
1070                AltList candidates;
1071                for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
1072                        AssertionSet needAssertions, haveAssertions;
1073                        OpenVarSet openVars;
1074
1075                        // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1076                        // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1077                        // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1078                        // to.
1079                        int discardedValues = i->expr->get_result()->size() - castExpr->get_result()->size();
1080                        if ( discardedValues < 0 ) continue;
1081                        // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1082                        // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1083                        // unification run for side-effects
1084                        unify( castExpr->get_result(), i->expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer );
1085                        Cost thisCost = castCost( i->expr->get_result(), castExpr->get_result(), indexer, i->env );
1086                        if ( thisCost != Cost::infinity ) {
1087                                // count one safe conversion for each value that is thrown away
1088                                thisCost.incSafe( discardedValues );
1089                                Alternative newAlt( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost );
1090                                // xxx - this doesn't work at the moment, since inferParameters requires an ApplicationExpr as the alternative.
1091                                // Once this works, it should be possible to infer parameters on a cast expression and specialize any function.
1092
1093                                // inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
1094                                candidates.emplace_back( std::move( newAlt ) );
1095                        } // if
1096                } // for
1097
1098                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1099                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1100                // selects first based on argument cost, then on conversion cost.
1101                AltList minArgCost;
1102                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1103                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1104        }
1105
1106        void AlternativeFinder::visit( VirtualCastExpr * castExpr ) {
1107                assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." );
1108                AlternativeFinder finder( indexer, env );
1109                // don't prune here, since it's guaranteed all alternatives will have the same type
1110                // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1111                finder.findWithAdjustment( castExpr->get_arg(), false );
1112                for ( Alternative & alt : finder.alternatives ) {
1113                        alternatives.push_back( Alternative(
1114                                new VirtualCastExpr( alt.expr->clone(), castExpr->get_result()->clone() ),
1115                                alt.env, alt.cost ) );
1116                }
1117        }
1118
1119        void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
1120                AlternativeFinder funcFinder( indexer, env );
1121                funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
1122                for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
1123                        // 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
1124                        std::unique_ptr<Expression> aggrExpr( agg->expr->clone() );
1125                        Type * aggrType = aggrExpr->get_result();
1126                        if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
1127                                aggrType = aggrType->stripReferences();
1128                                aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) );
1129                        }
1130                        // find member of the given type
1131                        if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
1132                                addAggMembers( structInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
1133                        } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
1134                                addAggMembers( unionInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
1135                        } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
1136                                addTupleMembers( tupleType, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
1137                        } // if
1138                } // for
1139        }
1140
1141        void AlternativeFinder::visit( MemberExpr *memberExpr ) {
1142                alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
1143        }
1144
1145        void AlternativeFinder::visit( NameExpr *nameExpr ) {
1146                std::list< DeclarationWithType* > declList;
1147                indexer.lookupId( nameExpr->get_name(), declList );
1148                PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
1149                for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
1150                        VariableExpr newExpr( *i, nameExpr->get_argName() );
1151                        alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
1152                        PRINT(
1153                                std::cerr << "decl is ";
1154                                (*i)->print( std::cerr );
1155                                std::cerr << std::endl;
1156                                std::cerr << "newExpr is ";
1157                                newExpr.print( std::cerr );
1158                                std::cerr << std::endl;
1159                        )
1160                        renameTypes( alternatives.back().expr );
1161                        addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
1162                } // for
1163        }
1164
1165        void AlternativeFinder::visit( VariableExpr *variableExpr ) {
1166                // not sufficient to clone here, because variable's type may have changed
1167                // since the VariableExpr was originally created.
1168                alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
1169        }
1170
1171        void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
1172                alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
1173        }
1174
1175        void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
1176                if ( sizeofExpr->get_isType() ) {
1177                        Type * newType = sizeofExpr->get_type()->clone();
1178                        alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1179                } else {
1180                        // find all alternatives for the argument to sizeof
1181                        AlternativeFinder finder( indexer, env );
1182                        finder.find( sizeofExpr->get_expr() );
1183                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1184                        AltList winners;
1185                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1186                        if ( winners.size() != 1 ) {
1187                                throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
1188                        } // if
1189                        // return the lowest cost alternative for the argument
1190                        Alternative &choice = winners.front();
1191                        referenceToRvalueConversion( choice.expr );
1192                        alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1193                } // if
1194        }
1195
1196        void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
1197                if ( alignofExpr->get_isType() ) {
1198                        Type * newType = alignofExpr->get_type()->clone();
1199                        alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1200                } else {
1201                        // find all alternatives for the argument to sizeof
1202                        AlternativeFinder finder( indexer, env );
1203                        finder.find( alignofExpr->get_expr() );
1204                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1205                        AltList winners;
1206                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1207                        if ( winners.size() != 1 ) {
1208                                throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
1209                        } // if
1210                        // return the lowest cost alternative for the argument
1211                        Alternative &choice = winners.front();
1212                        referenceToRvalueConversion( choice.expr );
1213                        alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1214                } // if
1215        }
1216
1217        template< typename StructOrUnionType >
1218        void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
1219                std::list< Declaration* > members;
1220                aggInst->lookup( name, members );
1221                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
1222                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
1223                                alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
1224                                renameTypes( alternatives.back().expr );
1225                        } else {
1226                                assert( false );
1227                        }
1228                }
1229        }
1230
1231        void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
1232                AlternativeFinder funcFinder( indexer, env );
1233                // xxx - resolveTypeof?
1234                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
1235                        addOffsetof( structInst, offsetofExpr->get_member() );
1236                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
1237                        addOffsetof( unionInst, offsetofExpr->get_member() );
1238                }
1239        }
1240
1241        void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
1242                alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
1243        }
1244
1245        void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
1246                alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
1247        }
1248
1249        void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) {
1250                // assume no polymorphism
1251                // assume no implicit conversions
1252                assert( function->get_parameters().size() == 1 );
1253                PRINT(
1254                        std::cerr << "resolvAttr: funcDecl is ";
1255                        funcDecl->print( std::cerr );
1256                        std::cerr << " argType is ";
1257                        argType->print( std::cerr );
1258                        std::cerr << std::endl;
1259                )
1260                if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1261                        alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
1262                        for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
1263                                alternatives.back().expr->set_result( (*i)->get_type()->clone() );
1264                        } // for
1265                } // if
1266        }
1267
1268        void AlternativeFinder::visit( AttrExpr *attrExpr ) {
1269                // assume no 'pointer-to-attribute'
1270                NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1271                assert( nameExpr );
1272                std::list< DeclarationWithType* > attrList;
1273                indexer.lookupId( nameExpr->get_name(), attrList );
1274                if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1275                        for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1276                                // check if the type is function
1277                                if ( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) {
1278                                        // assume exactly one parameter
1279                                        if ( function->get_parameters().size() == 1 ) {
1280                                                if ( attrExpr->get_isType() ) {
1281                                                        resolveAttr( *i, function, attrExpr->get_type(), env );
1282                                                } else {
1283                                                        AlternativeFinder finder( indexer, env );
1284                                                        finder.find( attrExpr->get_expr() );
1285                                                        for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1286                                                                if ( choice->expr->get_result()->size() == 1 ) {
1287                                                                        resolveAttr(*i, function, choice->expr->get_result(), choice->env );
1288                                                                } // fi
1289                                                        } // for
1290                                                } // if
1291                                        } // if
1292                                } // if
1293                        } // for
1294                } else {
1295                        for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1296                                VariableExpr newExpr( *i );
1297                                alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
1298                                renameTypes( alternatives.back().expr );
1299                        } // for
1300                } // if
1301        }
1302
1303        void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
1304                AlternativeFinder firstFinder( indexer, env );
1305                firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1306                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1307                        AlternativeFinder secondFinder( indexer, first->env );
1308                        secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1309                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1310                                LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
1311                                alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
1312                        }
1313                }
1314        }
1315
1316        void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
1317                // find alternatives for condition
1318                AlternativeFinder firstFinder( indexer, env );
1319                firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
1320                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1321                        // find alternatives for true expression
1322                        AlternativeFinder secondFinder( indexer, first->env );
1323                        secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
1324                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1325                                // find alterantives for false expression
1326                                AlternativeFinder thirdFinder( indexer, second->env );
1327                                thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
1328                                for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
1329                                        // unify true and false types, then infer parameters to produce new alternatives
1330                                        OpenVarSet openVars;
1331                                        AssertionSet needAssertions, haveAssertions;
1332                                        Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
1333                                        Type* commonType = nullptr;
1334                                        if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1335                                                ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
1336                                                newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
1337                                                // convert both options to the conditional result type
1338                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env );
1339                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
1340                                                newAlt.expr = newExpr;
1341                                                inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1342                                        } // if
1343                                } // for
1344                        } // for
1345                } // for
1346        }
1347
1348        void AlternativeFinder::visit( CommaExpr *commaExpr ) {
1349                TypeEnvironment newEnv( env );
1350                Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1351                AlternativeFinder secondFinder( indexer, newEnv );
1352                secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1353                for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
1354                        alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
1355                } // for
1356                delete newFirstArg;
1357        }
1358
1359        void AlternativeFinder::visit( RangeExpr * rangeExpr ) {
1360                // resolve low and high, accept alternatives whose low and high types unify
1361                AlternativeFinder firstFinder( indexer, env );
1362                firstFinder.findWithAdjustment( rangeExpr->get_low() );
1363                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1364                        AlternativeFinder secondFinder( indexer, first->env );
1365                        secondFinder.findWithAdjustment( rangeExpr->get_high() );
1366                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1367                                OpenVarSet openVars;
1368                                AssertionSet needAssertions, haveAssertions;
1369                                Alternative newAlt( 0, second->env, first->cost + second->cost );
1370                                Type* commonType = nullptr;
1371                                if ( unify( first->expr->get_result(), second->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1372                                        RangeExpr *newExpr = new RangeExpr( first->expr->clone(), second->expr->clone() );
1373                                        newExpr->set_result( commonType ? commonType : first->expr->get_result()->clone() );
1374                                        newAlt.expr = newExpr;
1375                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1376                                } // if
1377                        } // for
1378                } // for
1379        }
1380
1381        void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
1382                std::list< AlternativeFinder > subExprAlternatives;
1383                findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
1384                std::list< AltList > possibilities;
1385                // TODO re-write to use iterative method
1386                combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
1387                for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
1388                        std::list< Expression * > exprs;
1389                        makeExprList( *i, exprs );
1390
1391                        TypeEnvironment compositeEnv;
1392                        simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
1393                        alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) );
1394                } // for
1395        }
1396
1397        void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
1398                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1399        }
1400
1401        void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1402                alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
1403        }
1404
1405        void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
1406                AlternativeFinder finder( indexer, env );
1407                // don't prune here, since it's guaranteed all alternatives will have the same type
1408                // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1409                finder.findWithAdjustment( ctorExpr->get_callExpr(), false );
1410                for ( Alternative & alt : finder.alternatives ) {
1411                        alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
1412                }
1413        }
1414
1415        void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
1416                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1417        }
1418
1419        void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
1420                alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
1421        }
1422
1423        void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
1424                AlternativeFinder finder( indexer, env );
1425                finder.findWithAdjustment( unqExpr->get_expr() );
1426                for ( Alternative & alt : finder.alternatives ) {
1427                        // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
1428                        UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
1429                        alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
1430                }
1431        }
1432
1433        void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
1434                StmtExpr * newStmtExpr = stmtExpr->clone();
1435                ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1436                // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1437                alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
1438        }
1439
1440        void AlternativeFinder::visit( UntypedInitExpr *initExpr ) {
1441                // handle each option like a cast
1442                AltList candidates;
1443                PRINT( std::cerr << "untyped init expr: " << initExpr << std::endl; )
1444                // O(N^2) checks of d-types with e-types
1445                for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
1446                        Type * toType = resolveTypeof( initAlt.type, indexer );
1447                        SymTab::validateType( toType, &indexer );
1448                        adjustExprType( toType, env, indexer );
1449                        // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
1450                        // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
1451                        // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
1452                        AlternativeFinder finder( indexer, env );
1453                        finder.targetType = toType;
1454                        finder.findWithAdjustment( initExpr->get_expr() );
1455                        for ( Alternative & alt : finder.get_alternatives() ) {
1456                                TypeEnvironment newEnv( alt.env );
1457                                AssertionSet needAssertions, haveAssertions;
1458                                OpenVarSet openVars;  // find things in env that don't have a "representative type" and claim those are open vars?
1459                                PRINT( std::cerr << "  @ " << toType << " " << initAlt.designation << std::endl; )
1460                                // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1461                                // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1462                                // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1463                                // to.
1464                                int discardedValues = alt.expr->get_result()->size() - toType->size();
1465                                if ( discardedValues < 0 ) continue;
1466                                // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1467                                // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1468                                // unification run for side-effects
1469                                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??
1470
1471                                Cost thisCost = castCost( alt.expr->get_result(), toType, indexer, newEnv );
1472                                if ( thisCost != Cost::infinity ) {
1473                                        // count one safe conversion for each value that is thrown away
1474                                        thisCost.incSafe( discardedValues );
1475                                        candidates.push_back( Alternative( new InitExpr( restructureCast( alt.expr->clone(), toType ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost ) );
1476                                }
1477                        }
1478                }
1479
1480                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1481                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1482                // selects first based on argument cost, then on conversion cost.
1483                AltList minArgCost;
1484                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1485                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1486        }
1487} // namespace ResolvExpr
1488
1489// Local Variables: //
1490// tab-width: 4 //
1491// mode: c++ //
1492// compile-command: "make install" //
1493// End: //
Note: See TracBrowser for help on using the repository browser.