source: src/ResolvExpr/AlternativeFinder.cc @ a8706fc

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumwith_gc
Last change on this file since a8706fc was a8706fc, checked in by Rob Schluntz <rschlunt@…>, 5 years ago

Extract open variables from cast expression arguments

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