source: src/ResolvExpr/AlternativeFinder.cc @ 9160cb2

new-env
Last change on this file since 9160cb2 was 9160cb2, checked in by Aaron Moss <a3moss@…>, 6 years ago

Breadth-first assertion resolution builds, eats all the memory

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