source: src/ResolvExpr/AlternativeFinder.cc @ 99d4584

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 99d4584 was 99d4584, checked in by Aaron Moss <a3moss@…>, 5 years ago

Further stubs for resolver port

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