source: src/ResolvExpr/AlternativeFinder.cc @ 624b722

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

Minor code cleanup

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