source: src/ResolvExpr/AlternativeFinder.cc @ 62194cb

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 62194cb was 62194cb, checked in by Aaron Moss <a3moss@…>, 5 years ago

Reduce duplication of cost/env in ExplodedActual?

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