source: src/ResolvExpr/AlternativeFinder.cc @ 59cf83b

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resnenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprno_listpersistent-indexerpthread-emulationqualifiedEnum
Last change on this file since 59cf83b was 59cf83b, checked in by Aaron Moss <a3moss@…>, 6 years ago

Switch resolution flags to packed struct

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