source: src/ResolvExpr/AlternativeFinder.cc @ 452747a

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

Merge branch 'master' of plg.uwaterloo.ca:/u/cforall/software/cfa/cfa-cc

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