source: src/ResolvExpr/AlternativeFinder.cc @ 93401f8

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 93401f8 was 93401f8, checked in by Peter A. Buhr <pabuhr@…>, 6 years ago

add space in error message

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