source: src/ResolvExpr/AlternativeFinder.cc @ ad51cc2

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since ad51cc2 was ad51cc2, checked in by Rob Schluntz <rschlunt@…>, 6 years ago

Convert RenameVars? to PassVisitor?

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