source: src/ResolvExpr/AlternativeFinder.cc @ 83882e9

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

Update debug prints in AlternativeFinder?

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