source: src/ResolvExpr/AlternativeFinder.cc @ 97397a26

new-env
Last change on this file since 97397a26 was 97397a26, checked in by Aaron Moss <a3moss@…>, 5 years ago

Merge branch 'with_gc' into new-env

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