source: src/ResolvExpr/AlternativeFinder.cc @ 630bcb5

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

Fix pruneAlternatives so that deleted expressions are no longer ambiguous

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