source: src/ResolvExpr/AlternativeFinder.cc @ a8b27c6

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

Pre-explode arguments in AlternativeFinder?

  • Property mode set to 100644
File size: 70.3 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 remainder of exploded tuple if present
679                                        if ( results[i].hasExpl() ) {
680                                                const ExplodedActual& expl = results[i].getExpl( args );
681                                                const Alternative& actual = expl.alts[results[i].nextExpl];
682                                               
683                                                TypeEnvironment env = results[i].env;
684                                                OpenVarSet openVars = results[i].openVars;
685
686                                                env.addActual( actual.env, openVars );
687
688                                                unsigned nextExpl = results[i].nextExpl + 1;
689                                                if ( nextExpl == expl.alts.size() ) {
690                                                        nextExpl = 0;
691                                                }
692
693                                                results.emplace_back(
694                                                        i, actual.expr, move(env), copy(results[i].need), 
695                                                        copy(results[i].have), move(openVars), nextArg, nTuples, 
696                                                        Cost::zero, nextExpl, results[i].explAlt );
697                                               
698                                                continue;
699                                        }
700                                       
701                                        // finish result when out of arguments
702                                        if ( nextArg >= args.size() ) {
703                                                ArgPack newResult{ 
704                                                        results[i].env, results[i].need, results[i].have, 
705                                                        results[i].openVars };
706                                                newResult.nextArg = nextArg;
707                                                Type* argType;
708
709                                                if ( nTuples > 0 ) {
710                                                        // first iteration, push empty tuple expression
711                                                        newResult.parent = i;
712                                                        std::list<Expression*> emptyList;
713                                                        newResult.expr.reset( new TupleExpr( emptyList ) );
714                                                        argType = newResult.expr->get_result();
715                                                } else {
716                                                        // clone result to collect tuple
717                                                        newResult.parent = results[i].parent;
718                                                        newResult.cost = results[i].cost;
719                                                        newResult.tupleStart = results[i].tupleStart;
720                                                        newResult.expr.reset( results[i].expr->clone() );
721                                                        argType = newResult.expr->get_result();
722
723                                                        if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
724                                                                // the case where a ttype value is passed directly is special,
725                                                                // e.g. for argument forwarding purposes
726                                                                // xxx - what if passing multiple arguments, last of which is
727                                                                //       ttype?
728                                                                // xxx - what would happen if unify was changed so that unifying
729                                                                //       tuple
730                                                                // types flattened both before unifying lists? then pass in
731                                                                // TupleType (ttype) below.
732                                                                --newResult.tupleStart;
733                                                        } else {
734                                                                // collapse leftover arguments into tuple
735                                                                newResult.endTuple( results );
736                                                                argType = newResult.expr->get_result();
737                                                        }
738                                                }
739
740                                                // check unification for ttype before adding to final
741                                                if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have, 
742                                                                newResult.openVars, indexer ) ) {
743                                                        finalResults.push_back( move(newResult) );
744                                                }
745                                               
746                                                continue;
747                                        }
748
749                                        // add each possible next argument
750                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
751                                                const ExplodedActual& expl = args[nextArg][j];
752                                       
753                                                // fresh copies of parent parameters for this iteration
754                                                TypeEnvironment env = results[i].env;
755                                                OpenVarSet openVars = results[i].openVars;
756
757                                                env.addActual( expl.env, openVars );
758
759                                                // skip empty tuple arguments by (near-)cloning parent into next gen
760                                                if ( expl.alts.empty() ) {
761                                                        results.emplace_back(
762                                                                results[i], move(env), copy(results[i].need), 
763                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
764                                                       
765                                                        continue;
766                                                }
767
768                                                // add new result
769                                                results.emplace_back(
770                                                        i, expl.alts.front().expr, move(env), copy(results[i].need), 
771                                                        copy(results[i].have), move(openVars), nextArg + 1, 
772                                                        nTuples, expl.cost, expl.alts.size() == 1 ? 0 : 1, j );
773                                        }
774                                }
775
776                                // reset for next round
777                                genStart = genEnd;
778                                nTuples = 0;
779                        } while ( genEnd != results.size() );
780
781                        // splice final results onto results
782                        for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
783                                results.push_back( move(finalResults[i]) );
784                        }
785                        return ! finalResults.empty();
786                }
787
788                // iterate each current subresult
789                std::size_t genEnd = results.size();
790                for ( std::size_t i = genStart; i < genEnd; ++i ) {
791                        auto nextArg = results[i].nextArg;
792
793                        // use remainder of exploded tuple if present
794                        if ( results[i].hasExpl() ) {
795                                const ExplodedActual& expl = results[i].getExpl( args );
796                                const Alternative& actual = expl.alts[results[i].nextExpl];
797                               
798                                TypeEnvironment env = results[i].env;
799                                AssertionSet need = results[i].need, have = results[i].have;
800                                OpenVarSet openVars = results[i].openVars;
801
802                                env.addActual( actual.env, openVars );
803                                Type* actualType = actual.expr->get_result();
804
805                                PRINT(
806                                        std::cerr << "formal type is ";
807                                        formalType->print( std::cerr );
808                                        std::cerr << std::endl << "actual type is ";
809                                        actualType->print( std::cerr );
810                                        std::cerr << std::endl;
811                                )
812                               
813                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
814                                        unsigned nextExpl = results[i].nextExpl + 1;
815                                        if ( nextExpl == expl.alts.size() ) {
816                                                nextExpl = 0;
817                                        }
818                                       
819                                        results.emplace_back( 
820                                                i, actual.expr, move(env), move(need), move(have), move(openVars), 
821                                                nextArg, nTuples, Cost::zero, nextExpl, results[i].explAlt );
822                                }
823
824                                continue;
825                        }
826                       
827                        // use default initializers if out of arguments
828                        if ( nextArg >= args.size() ) {
829                                if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
830                                        if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
831                                                TypeEnvironment env = results[i].env;
832                                                AssertionSet need = results[i].need, have = results[i].have;
833                                                OpenVarSet openVars = results[i].openVars;
834
835                                                if ( unify( formalType, cnst->get_type(), env, need, have, openVars, 
836                                                                indexer ) ) {
837                                                        results.emplace_back(
838                                                                i, cnstExpr, move(env), move(need), move(have), 
839                                                                move(openVars), nextArg, nTuples );
840                                                }
841                                        }
842                                }
843
844                                continue;
845                        }
846
847                        // Check each possible next argument
848                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
849                                const ExplodedActual& expl = args[nextArg][j];
850
851                                // fresh copies of parent parameters for this iteration
852                                TypeEnvironment env = results[i].env;
853                                AssertionSet need = results[i].need, have = results[i].have;
854                                OpenVarSet openVars = results[i].openVars;
855
856                                env.addActual( expl.env, openVars );
857                               
858                                // skip empty tuple arguments by (near-)cloning parent into next gen
859                                if ( expl.alts.empty() ) {
860                                        results.emplace_back(
861                                                results[i], move(env), move(need), move(have), move(openVars), 
862                                                nextArg + 1, expl.cost );
863
864                                        continue;
865                                }
866
867                                // consider only first exploded actual
868                                const Alternative& actual = expl.alts.front();
869                                Type* actualType = actual.expr->get_result()->clone();
870
871                                PRINT(
872                                        std::cerr << "formal type is ";
873                                        formalType->print( std::cerr );
874                                        std::cerr << std::endl << "actual type is ";
875                                        actualType->print( std::cerr );
876                                        std::cerr << std::endl;
877                                )
878
879                                // attempt to unify types
880                                if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
881                                        // add new result
882                                        results.emplace_back(
883                                                i, actual.expr, move(env), move(need), move(have), move(openVars),
884                                                nextArg + 1, nTuples, expl.cost, expl.alts.size() == 1 ? 0 : 1, j );
885                                }
886                        }
887                }
888
889                // reset for next parameter
890                genStart = genEnd;
891               
892                return genEnd != results.size();
893        }
894
895        template<typename OutputIterator>
896        void AlternativeFinder::validateFunctionAlternative( const Alternative &func, ArgPack& result, 
897                        const std::vector<ArgPack>& results, OutputIterator out ) {
898                ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
899                // sum cost and accumulate actuals
900                std::list<Expression*>& args = appExpr->get_args();
901                Cost cost = Cost::zero;
902                const ArgPack* pack = &result;
903                while ( pack->expr ) {
904                        args.push_front( pack->expr->clone() );
905                        cost += pack->cost;
906                        pack = &results[pack->parent];
907                }
908                // build and validate new alternative
909                Alternative newAlt( appExpr, result.env, cost );
910                PRINT(
911                        std::cerr << "instantiate function success: " << appExpr << std::endl;
912                        std::cerr << "need assertions:" << std::endl;
913                        printAssertionSet( result.need, std::cerr, 8 );
914                )
915                inferParameters( result.need, result.have, newAlt, result.openVars, out );
916        }
917
918        template<typename OutputIterator>
919        void AlternativeFinder::makeFunctionAlternatives( const Alternative &func,
920                        FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) {
921                OpenVarSet funcOpenVars;
922                AssertionSet funcNeed, funcHave;
923                TypeEnvironment funcEnv( func.env );
924                makeUnifiableVars( funcType, funcOpenVars, funcNeed );
925                // add all type variables as open variables now so that those not used in the parameter
926                // list are still considered open.
927                funcEnv.add( funcType->get_forall() );
928
929                if ( targetType && ! targetType->isVoid() && ! funcType->get_returnVals().empty() ) {
930                        // attempt to narrow based on expected target type
931                        Type * returnType = funcType->get_returnVals().front()->get_type();
932                        if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars,
933                                        indexer ) ) {
934                                // unification failed, don't pursue this function alternative
935                                return;
936                        }
937                }
938
939                // iteratively build matches, one parameter at a time
940                std::vector<ArgPack> results;
941                results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } );
942                std::size_t genStart = 0;
943
944                for ( DeclarationWithType* formal : funcType->get_parameters() ) {
945                        ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal );
946                        if ( ! instantiateArgument( 
947                                        obj->get_type(), obj->get_init(), args, results, genStart, indexer ) )
948                                return;
949                }
950
951                if ( funcType->get_isVarArgs() ) {
952                        // append any unused arguments to vararg pack
953                        std::size_t genEnd;
954                        do {
955                                genEnd = results.size();
956
957                                // iterate results
958                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
959                                        auto nextArg = results[i].nextArg;
960
961                                        // use remainder of exploded tuple if present
962                                        if ( results[i].hasExpl() ) {
963                                                const ExplodedActual& expl = results[i].getExpl( args );
964                                                const Alternative& actual = expl.alts[results[i].nextExpl];
965                                               
966                                                TypeEnvironment env = results[i].env;
967                                                OpenVarSet openVars = results[i].openVars;
968
969                                                env.addActual( actual.env, openVars );
970
971                                                unsigned nextExpl = results[i].nextExpl + 1;
972                                                if ( nextExpl == expl.alts.size() ) {
973                                                        nextExpl = 0;
974                                                }
975
976                                                results.emplace_back(
977                                                        i, actual.expr, move(env), copy(results[i].need), 
978                                                        copy(results[i].have), move(openVars), nextArg, 0, 
979                                                        Cost::zero, nextExpl, results[i].explAlt );
980                                               
981                                                continue;
982                                        }
983
984                                        // finish result when out of arguments
985                                        if ( nextArg >= args.size() ) {
986                                                validateFunctionAlternative( func, results[i], results, out );
987
988                                                continue;
989                                        }
990
991                                        // add each possible next argument
992                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
993                                                const ExplodedActual& expl = args[nextArg][j];
994
995                                                // fresh copies of parent parameters for this iteration
996                                                TypeEnvironment env = results[i].env;
997                                                OpenVarSet openVars = results[i].openVars;
998
999                                                env.addActual( expl.env, openVars );
1000
1001                                                // skip empty tuple arguments by (near-)cloning parent into next gen
1002                                                if ( expl.alts.empty() ) {
1003                                                        results.emplace_back( 
1004                                                                results[i], move(env), copy(results[i].need), 
1005                                                                copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
1006                                                       
1007                                                        continue;
1008                                                }
1009
1010                                                // add new result
1011                                                results.emplace_back(
1012                                                        i, expl.alts.front().expr, move(env), copy(results[i].need), 
1013                                                        copy(results[i].have), move(openVars), nextArg + 1, 0, 
1014                                                        expl.cost, expl.alts.size() == 1 ? 0 : 1, j );
1015                                        }
1016                                }
1017
1018                                genStart = genEnd;
1019                        } while ( genEnd != results.size() );
1020                } else {
1021                        // filter out results that don't use all the arguments
1022                        for ( std::size_t i = genStart; i < results.size(); ++i ) {
1023                                ArgPack& result = results[i];
1024                                if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
1025                                        validateFunctionAlternative( func, result, results, out );
1026                                }
1027                        }
1028                }
1029        }
1030
1031        void AlternativeFinder::visit( UntypedExpr *untypedExpr ) {
1032                AlternativeFinder funcFinder( indexer, env );
1033                funcFinder.findWithAdjustment( untypedExpr->get_function() );
1034                // if there are no function alternatives, then proceeding is a waste of time.
1035                if ( funcFinder.alternatives.empty() ) return;
1036
1037                std::vector< AlternativeFinder > argAlternatives;
1038                findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(),
1039                        back_inserter( argAlternatives ) );
1040
1041                // take care of possible tuple assignments
1042                // if not tuple assignment, assignment is taken care of as a normal function call
1043                Tuples::handleTupleAssignment( *this, untypedExpr, argAlternatives );
1044
1045                // find function operators
1046                static NameExpr *opExpr = new NameExpr( "?()" );
1047                AlternativeFinder funcOpFinder( indexer, env );
1048                // it's ok if there aren't any defined function ops
1049                funcOpFinder.maybeFind( opExpr);
1050                PRINT(
1051                        std::cerr << "known function ops:" << std::endl;
1052                        printAlts( funcOpFinder.alternatives, std::cerr, 1 );
1053                )
1054
1055                // pre-explode arguments
1056                ExplodedArgs argExpansions;
1057                argExpansions.reserve( argAlternatives.size() );
1058
1059                for ( const AlternativeFinder& arg : argAlternatives ) {
1060                        argExpansions.emplace_back();
1061                        auto& argE = argExpansions.back();
1062                        argE.reserve( arg.alternatives.size() );
1063                       
1064                        for ( const Alternative& actual : arg ) {
1065                                argE.emplace_back( actual, indexer );
1066                        }
1067                }
1068
1069                AltList candidates;
1070                SemanticError errors;
1071                for ( AltList::iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
1072                        try {
1073                                PRINT(
1074                                        std::cerr << "working on alternative: " << std::endl;
1075                                        func->print( std::cerr, 8 );
1076                                )
1077                                // check if the type is pointer to function
1078                                if ( PointerType *pointer = dynamic_cast< PointerType* >( func->expr->get_result()->stripReferences() ) ) {
1079                                        if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
1080                                                Alternative newFunc( *func );
1081                                                referenceToRvalueConversion( newFunc.expr );
1082                                                makeFunctionAlternatives( newFunc, function, argExpansions,
1083                                                        std::back_inserter( candidates ) );
1084                                        }
1085                                } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->get_result()->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
1086                                        EqvClass eqvClass;
1087                                        if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) {
1088                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.type ) ) {
1089                                                        Alternative newFunc( *func );
1090                                                        referenceToRvalueConversion( newFunc.expr );
1091                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
1092                                                                std::back_inserter( candidates ) );
1093                                                } // if
1094                                        } // if
1095                                }
1096                        } catch ( SemanticError &e ) {
1097                                errors.append( e );
1098                        }
1099                } // for
1100
1101                // try each function operator ?() with each function alternative
1102                if ( ! funcOpFinder.alternatives.empty() ) {
1103                        // add exploded function alternatives to front of argument list
1104                        std::vector<ExplodedActual> funcE;
1105                        funcE.reserve( funcFinder.alternatives.size() );
1106                        for ( const Alternative& actual : funcFinder ) {
1107                                funcE.emplace_back( actual, indexer );
1108                        }
1109                        argExpansions.insert( argExpansions.begin(), move(funcE) );
1110
1111                        for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
1112                                        funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
1113                                try {
1114                                        // check if type is a pointer to function
1115                                        if ( PointerType* pointer = dynamic_cast<PointerType*>(
1116                                                        funcOp->expr->get_result()->stripReferences() ) ) {
1117                                                if ( FunctionType* function =
1118                                                                dynamic_cast<FunctionType*>( pointer->get_base() ) ) {
1119                                                        Alternative newFunc( *funcOp );
1120                                                        referenceToRvalueConversion( newFunc.expr );
1121                                                        makeFunctionAlternatives( newFunc, function, argExpansions,
1122                                                                std::back_inserter( candidates ) );
1123                                                }
1124                                        }
1125                                } catch ( SemanticError &e ) {
1126                                        errors.append( e );
1127                                }
1128                        }
1129                }
1130
1131                // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
1132                if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
1133
1134                // compute conversionsion costs
1135                for ( Alternative& withFunc : candidates ) {
1136                        Cost cvtCost = computeApplicationConversionCost( withFunc, indexer );
1137
1138                        PRINT(
1139                                ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr );
1140                                PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
1141                                FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
1142                                std::cerr << "Case +++++++++++++ " << appExpr->get_function() << std::endl;
1143                                std::cerr << "formals are:" << std::endl;
1144                                printAll( function->get_parameters(), std::cerr, 8 );
1145                                std::cerr << "actuals are:" << std::endl;
1146                                printAll( appExpr->get_args(), std::cerr, 8 );
1147                                std::cerr << "bindings are:" << std::endl;
1148                                withFunc.env.print( std::cerr, 8 );
1149                                std::cerr << "cost of conversion is:" << cvtCost << std::endl;
1150                        )
1151                        if ( cvtCost != Cost::infinity ) {
1152                                withFunc.cvtCost = cvtCost;
1153                                alternatives.push_back( withFunc );
1154                        } // if
1155                } // for
1156
1157                candidates = move(alternatives);
1158
1159                // use a new list so that alternatives are not examined by addAnonConversions twice.
1160                AltList winners;
1161                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) );
1162
1163                // function may return struct or union value, in which case we need to add alternatives
1164                // for implicitconversions to each of the anonymous members, must happen after findMinCost
1165                // since anon conversions are never the cheapest expression
1166                for ( const Alternative & alt : winners ) {
1167                        addAnonConversions( alt );
1168                }
1169                spliceBegin( alternatives, winners );
1170
1171                if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
1172                        // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
1173                        // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
1174                        //   forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
1175                        //   const char * x = "hello world";
1176                        //   unsigned char ch = x[0];
1177                        // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
1178                        // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
1179                        // fix this issue in a more robust way.
1180                        targetType = nullptr;
1181                        visit( untypedExpr );
1182                }
1183        }
1184
1185        bool isLvalue( Expression *expr ) {
1186                // xxx - recurse into tuples?
1187                return expr->result && ( expr->get_result()->get_lvalue() || dynamic_cast< ReferenceType * >( expr->get_result() ) );
1188        }
1189
1190        void AlternativeFinder::visit( AddressExpr *addressExpr ) {
1191                AlternativeFinder finder( indexer, env );
1192                finder.find( addressExpr->get_arg() );
1193                for ( Alternative& alt : finder.alternatives ) {
1194                        if ( isLvalue( alt.expr ) ) {
1195                                alternatives.push_back( 
1196                                        Alternative{ new AddressExpr( alt.expr->clone() ), alt.env, alt.cost } );
1197                        } // if
1198                } // for
1199        }
1200
1201        void AlternativeFinder::visit( LabelAddressExpr * expr ) {
1202                alternatives.push_back( Alternative{ expr->clone(), env, Cost::zero } );
1203        }
1204
1205        Expression * restructureCast( Expression * argExpr, Type * toType ) {
1206                if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() && ! dynamic_cast<ReferenceType *>( toType ) ) {
1207                        // Argument expression is a tuple and the target type is not void and not a reference type.
1208                        // Cast each member of the tuple to its corresponding target type, producing the tuple of those
1209                        // cast expressions. If there are more components of the tuple than components in the target type,
1210                        // then excess components do not come out in the result expression (but UniqueExprs ensure that
1211                        // side effects will still be done).
1212                        if ( Tuples::maybeImpureIgnoreUnique( argExpr ) ) {
1213                                // expressions which may contain side effects require a single unique instance of the expression.
1214                                argExpr = new UniqueExpr( argExpr );
1215                        }
1216                        std::list< Expression * > componentExprs;
1217                        for ( unsigned int i = 0; i < toType->size(); i++ ) {
1218                                // cast each component
1219                                TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
1220                                componentExprs.push_back( restructureCast( idx, toType->getComponent( i ) ) );
1221                        }
1222                        delete argExpr;
1223                        assert( componentExprs.size() > 0 );
1224                        // produce the tuple of casts
1225                        return new TupleExpr( componentExprs );
1226                } else {
1227                        // handle normally
1228                        return new CastExpr( argExpr, toType->clone() );
1229                }
1230        }
1231
1232        void AlternativeFinder::visit( CastExpr *castExpr ) {
1233                Type *& toType = castExpr->get_result();
1234                assert( toType );
1235                toType = resolveTypeof( toType, indexer );
1236                SymTab::validateType( toType, &indexer );
1237                adjustExprType( toType, env, indexer );
1238
1239                AlternativeFinder finder( indexer, env );
1240                finder.targetType = toType;
1241                finder.findWithAdjustment( castExpr->get_arg() );
1242
1243                AltList candidates;
1244                for ( Alternative& alt : finder.alternatives ) {
1245                        AssertionSet needAssertions, haveAssertions;
1246                        OpenVarSet openVars;
1247
1248                        // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1249                        // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1250                        // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1251                        // to.
1252                        int discardedValues = alt.expr->get_result()->size() - castExpr->get_result()->size();
1253                        if ( discardedValues < 0 ) continue;
1254                        // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1255                        // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1256                        // unification run for side-effects
1257                        unify( castExpr->get_result(), alt.expr->get_result(), alt.env, needAssertions, 
1258                                haveAssertions, openVars, indexer );
1259                        Cost thisCost = castCost( alt.expr->get_result(), castExpr->get_result(), indexer, 
1260                                alt.env );
1261                        if ( thisCost != Cost::infinity ) {
1262                                // count one safe conversion for each value that is thrown away
1263                                thisCost.incSafe( discardedValues );
1264                                Alternative newAlt( restructureCast( alt.expr->clone(), toType ), alt.env, 
1265                                        alt.cost, thisCost );
1266                                inferParameters( needAssertions, haveAssertions, newAlt, openVars, 
1267                                        back_inserter( candidates ) );
1268                        } // if
1269                } // for
1270
1271                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1272                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1273                // selects first based on argument cost, then on conversion cost.
1274                AltList minArgCost;
1275                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1276                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1277        }
1278
1279        void AlternativeFinder::visit( VirtualCastExpr * castExpr ) {
1280                assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." );
1281                AlternativeFinder finder( indexer, env );
1282                // don't prune here, since it's guaranteed all alternatives will have the same type
1283                finder.findWithoutPrune( castExpr->get_arg() );
1284                for ( Alternative & alt : finder.alternatives ) {
1285                        alternatives.push_back( Alternative(
1286                                new VirtualCastExpr( alt.expr->clone(), castExpr->get_result()->clone() ),
1287                                alt.env, alt.cost ) );
1288                }
1289        }
1290
1291        void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
1292                AlternativeFinder funcFinder( indexer, env );
1293                funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
1294                for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
1295                        // 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
1296                        std::unique_ptr<Expression> aggrExpr( agg->expr->clone() );
1297                        Type * aggrType = aggrExpr->get_result();
1298                        if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
1299                                aggrType = aggrType->stripReferences();
1300                                aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) );
1301                        }
1302                        // find member of the given type
1303                        if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
1304                                addAggMembers( structInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
1305                        } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
1306                                addAggMembers( unionInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
1307                        } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
1308                                addTupleMembers( tupleType, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
1309                        } // if
1310                } // for
1311        }
1312
1313        void AlternativeFinder::visit( MemberExpr *memberExpr ) {
1314                alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
1315        }
1316
1317        void AlternativeFinder::visit( NameExpr *nameExpr ) {
1318                std::list< DeclarationWithType* > declList;
1319                indexer.lookupId( nameExpr->get_name(), declList );
1320                PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
1321                for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
1322                        VariableExpr newExpr( *i );
1323                        alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
1324                        PRINT(
1325                                std::cerr << "decl is ";
1326                                (*i)->print( std::cerr );
1327                                std::cerr << std::endl;
1328                                std::cerr << "newExpr is ";
1329                                newExpr.print( std::cerr );
1330                                std::cerr << std::endl;
1331                        )
1332                        renameTypes( alternatives.back().expr );
1333                        addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
1334                } // for
1335        }
1336
1337        void AlternativeFinder::visit( VariableExpr *variableExpr ) {
1338                // not sufficient to clone here, because variable's type may have changed
1339                // since the VariableExpr was originally created.
1340                alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
1341        }
1342
1343        void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
1344                alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
1345        }
1346
1347        void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
1348                if ( sizeofExpr->get_isType() ) {
1349                        Type * newType = sizeofExpr->get_type()->clone();
1350                        alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1351                } else {
1352                        // find all alternatives for the argument to sizeof
1353                        AlternativeFinder finder( indexer, env );
1354                        finder.find( sizeofExpr->get_expr() );
1355                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1356                        AltList winners;
1357                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1358                        if ( winners.size() != 1 ) {
1359                                throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
1360                        } // if
1361                        // return the lowest cost alternative for the argument
1362                        Alternative &choice = winners.front();
1363                        referenceToRvalueConversion( choice.expr );
1364                        alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1365                } // if
1366        }
1367
1368        void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
1369                if ( alignofExpr->get_isType() ) {
1370                        Type * newType = alignofExpr->get_type()->clone();
1371                        alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1372                } else {
1373                        // find all alternatives for the argument to sizeof
1374                        AlternativeFinder finder( indexer, env );
1375                        finder.find( alignofExpr->get_expr() );
1376                        // find the lowest cost alternative among the alternatives, otherwise ambiguous
1377                        AltList winners;
1378                        findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1379                        if ( winners.size() != 1 ) {
1380                                throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
1381                        } // if
1382                        // return the lowest cost alternative for the argument
1383                        Alternative &choice = winners.front();
1384                        referenceToRvalueConversion( choice.expr );
1385                        alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1386                } // if
1387        }
1388
1389        template< typename StructOrUnionType >
1390        void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
1391                std::list< Declaration* > members;
1392                aggInst->lookup( name, members );
1393                for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
1394                        if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
1395                                alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
1396                                renameTypes( alternatives.back().expr );
1397                        } else {
1398                                assert( false );
1399                        }
1400                }
1401        }
1402
1403        void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
1404                AlternativeFinder funcFinder( indexer, env );
1405                // xxx - resolveTypeof?
1406                if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
1407                        addOffsetof( structInst, offsetofExpr->get_member() );
1408                } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
1409                        addOffsetof( unionInst, offsetofExpr->get_member() );
1410                }
1411        }
1412
1413        void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
1414                alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
1415        }
1416
1417        void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
1418                alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
1419        }
1420
1421        void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) {
1422                // assume no polymorphism
1423                // assume no implicit conversions
1424                assert( function->get_parameters().size() == 1 );
1425                PRINT(
1426                        std::cerr << "resolvAttr: funcDecl is ";
1427                        funcDecl->print( std::cerr );
1428                        std::cerr << " argType is ";
1429                        argType->print( std::cerr );
1430                        std::cerr << std::endl;
1431                )
1432                if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1433                        alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
1434                        for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
1435                                alternatives.back().expr->set_result( (*i)->get_type()->clone() );
1436                        } // for
1437                } // if
1438        }
1439
1440        void AlternativeFinder::visit( AttrExpr *attrExpr ) {
1441                // assume no 'pointer-to-attribute'
1442                NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1443                assert( nameExpr );
1444                std::list< DeclarationWithType* > attrList;
1445                indexer.lookupId( nameExpr->get_name(), attrList );
1446                if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1447                        for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1448                                // check if the type is function
1449                                if ( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) {
1450                                        // assume exactly one parameter
1451                                        if ( function->get_parameters().size() == 1 ) {
1452                                                if ( attrExpr->get_isType() ) {
1453                                                        resolveAttr( *i, function, attrExpr->get_type(), env );
1454                                                } else {
1455                                                        AlternativeFinder finder( indexer, env );
1456                                                        finder.find( attrExpr->get_expr() );
1457                                                        for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1458                                                                if ( choice->expr->get_result()->size() == 1 ) {
1459                                                                        resolveAttr(*i, function, choice->expr->get_result(), choice->env );
1460                                                                } // fi
1461                                                        } // for
1462                                                } // if
1463                                        } // if
1464                                } // if
1465                        } // for
1466                } else {
1467                        for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1468                                VariableExpr newExpr( *i );
1469                                alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
1470                                renameTypes( alternatives.back().expr );
1471                        } // for
1472                } // if
1473        }
1474
1475        void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
1476                AlternativeFinder firstFinder( indexer, env );
1477                firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1478                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1479                        AlternativeFinder secondFinder( indexer, first->env );
1480                        secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1481                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1482                                LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
1483                                alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
1484                        }
1485                }
1486        }
1487
1488        void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
1489                // find alternatives for condition
1490                AlternativeFinder firstFinder( indexer, env );
1491                firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
1492                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1493                        // find alternatives for true expression
1494                        AlternativeFinder secondFinder( indexer, first->env );
1495                        secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
1496                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1497                                // find alterantives for false expression
1498                                AlternativeFinder thirdFinder( indexer, second->env );
1499                                thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
1500                                for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
1501                                        // unify true and false types, then infer parameters to produce new alternatives
1502                                        OpenVarSet openVars;
1503                                        AssertionSet needAssertions, haveAssertions;
1504                                        Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
1505                                        Type* commonType = nullptr;
1506                                        if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1507                                                ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
1508                                                newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
1509                                                // convert both options to the conditional result type
1510                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env );
1511                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
1512                                                newAlt.expr = newExpr;
1513                                                inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1514                                        } // if
1515                                } // for
1516                        } // for
1517                } // for
1518        }
1519
1520        void AlternativeFinder::visit( CommaExpr *commaExpr ) {
1521                TypeEnvironment newEnv( env );
1522                Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1523                AlternativeFinder secondFinder( indexer, newEnv );
1524                secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1525                for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
1526                        alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
1527                } // for
1528                delete newFirstArg;
1529        }
1530
1531        void AlternativeFinder::visit( RangeExpr * rangeExpr ) {
1532                // resolve low and high, accept alternatives whose low and high types unify
1533                AlternativeFinder firstFinder( indexer, env );
1534                firstFinder.findWithAdjustment( rangeExpr->get_low() );
1535                for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1536                        AlternativeFinder secondFinder( indexer, first->env );
1537                        secondFinder.findWithAdjustment( rangeExpr->get_high() );
1538                        for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1539                                OpenVarSet openVars;
1540                                AssertionSet needAssertions, haveAssertions;
1541                                Alternative newAlt( 0, second->env, first->cost + second->cost );
1542                                Type* commonType = nullptr;
1543                                if ( unify( first->expr->get_result(), second->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1544                                        RangeExpr *newExpr = new RangeExpr( first->expr->clone(), second->expr->clone() );
1545                                        newExpr->set_result( commonType ? commonType : first->expr->get_result()->clone() );
1546                                        newAlt.expr = newExpr;
1547                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1548                                } // if
1549                        } // for
1550                } // for
1551        }
1552
1553        void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
1554                std::vector< AlternativeFinder > subExprAlternatives;
1555                findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), 
1556                        back_inserter( subExprAlternatives ) );
1557                std::vector< AltList > possibilities;
1558                combos( subExprAlternatives.begin(), subExprAlternatives.end(), 
1559                        back_inserter( possibilities ) );
1560                for ( const AltList& alts : possibilities ) {
1561                        std::list< Expression * > exprs;
1562                        makeExprList( alts, exprs );
1563
1564                        TypeEnvironment compositeEnv;
1565                        simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
1566                        alternatives.push_back( 
1567                                Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } );
1568                } // for
1569        }
1570
1571        void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
1572                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1573        }
1574
1575        void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1576                alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
1577        }
1578
1579        void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
1580                AlternativeFinder finder( indexer, env );
1581                // don't prune here, since it's guaranteed all alternatives will have the same type
1582                // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1583                finder.findWithoutPrune( ctorExpr->get_callExpr() );
1584                for ( Alternative & alt : finder.alternatives ) {
1585                        alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
1586                }
1587        }
1588
1589        void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
1590                alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1591        }
1592
1593        void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
1594                alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
1595        }
1596
1597        void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
1598                AlternativeFinder finder( indexer, env );
1599                finder.findWithAdjustment( unqExpr->get_expr() );
1600                for ( Alternative & alt : finder.alternatives ) {
1601                        // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
1602                        UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
1603                        alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
1604                }
1605        }
1606
1607        void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
1608                StmtExpr * newStmtExpr = stmtExpr->clone();
1609                ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1610                // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1611                alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
1612        }
1613
1614        void AlternativeFinder::visit( UntypedInitExpr *initExpr ) {
1615                // handle each option like a cast
1616                AltList candidates;
1617                PRINT( std::cerr << "untyped init expr: " << initExpr << std::endl; )
1618                // O(N^2) checks of d-types with e-types
1619                for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
1620                        Type * toType = resolveTypeof( initAlt.type->clone(), indexer );
1621                        SymTab::validateType( toType, &indexer );
1622                        adjustExprType( toType, env, indexer );
1623                        // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
1624                        // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
1625                        // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
1626                        AlternativeFinder finder( indexer, env );
1627                        finder.targetType = toType;
1628                        finder.findWithAdjustment( initExpr->get_expr() );
1629                        for ( Alternative & alt : finder.get_alternatives() ) {
1630                                TypeEnvironment newEnv( alt.env );
1631                                AssertionSet needAssertions, haveAssertions;
1632                                OpenVarSet openVars;  // find things in env that don't have a "representative type" and claim those are open vars?
1633                                PRINT( std::cerr << "  @ " << toType << " " << initAlt.designation << std::endl; )
1634                                // It's possible that a cast can throw away some values in a multiply-valued expression.  (An example is a
1635                                // cast-to-void, which casts from one value to zero.)  Figure out the prefix of the subexpression results
1636                                // that are cast directly.  The candidate is invalid if it has fewer results than there are types to cast
1637                                // to.
1638                                int discardedValues = alt.expr->get_result()->size() - toType->size();
1639                                if ( discardedValues < 0 ) continue;
1640                                // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1641                                // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1642                                // unification run for side-effects
1643                                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??
1644
1645                                Cost thisCost = castCost( alt.expr->get_result(), toType, indexer, newEnv );
1646                                if ( thisCost != Cost::infinity ) {
1647                                        // count one safe conversion for each value that is thrown away
1648                                        thisCost.incSafe( discardedValues );
1649                                        Alternative newAlt( new InitExpr( restructureCast( alt.expr->clone(), toType ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost );
1650                                        inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
1651                                }
1652                        }
1653                }
1654
1655                // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1656                // cvtCost member to the cost member (since the old cost is now irrelevant).  Thus, calling findMinCost twice
1657                // selects first based on argument cost, then on conversion cost.
1658                AltList minArgCost;
1659                findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1660                findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1661        }
1662} // namespace ResolvExpr
1663
1664// Local Variables: //
1665// tab-width: 4 //
1666// mode: c++ //
1667// compile-command: "make install" //
1668// End: //
Note: See TracBrowser for help on using the repository browser.