source: src/ResolvExpr/AlternativeFinder.cc @ 0872c42

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 0872c42 was 0872c42, checked in by Aaron Moss <a3moss@…>, 6 years ago

Fix bug with ttype/vararg handling in resolver refactor

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