Index: src/Makefile.in =================================================================== --- src/Makefile.in (revision 8dceeb78ad2ff73a75b2a0589e7539e4da01800f) +++ src/Makefile.in (revision 178e4ec86cc344917f0d9781c8bf4e520b7b2a53) @@ -210,4 +210,5 @@ ResolvExpr/driver_cfa_cpp-TypeEnvironment.$(OBJEXT) \ ResolvExpr/driver_cfa_cpp-CurrentObject.$(OBJEXT) \ + ResolvExpr/driver_cfa_cpp-ExplodedActual.$(OBJEXT) \ SymTab/driver_cfa_cpp-Indexer.$(OBJEXT) \ SymTab/driver_cfa_cpp-Mangler.$(OBJEXT) \ @@ -511,12 +512,13 @@ ResolvExpr/FindOpenVars.cc ResolvExpr/PolyCost.cc \ ResolvExpr/Occurs.cc ResolvExpr/TypeEnvironment.cc \ - ResolvExpr/CurrentObject.cc SymTab/Indexer.cc \ - SymTab/Mangler.cc SymTab/Validate.cc SymTab/FixFunction.cc \ - SymTab/ImplementationType.cc SymTab/TypeEquality.cc \ - SymTab/Autogen.cc SynTree/Type.cc SynTree/VoidType.cc \ - SynTree/BasicType.cc SynTree/PointerType.cc \ - SynTree/ArrayType.cc SynTree/ReferenceType.cc \ - SynTree/FunctionType.cc SynTree/ReferenceToType.cc \ - SynTree/TupleType.cc SynTree/TypeofType.cc SynTree/AttrType.cc \ + ResolvExpr/CurrentObject.cc ResolvExpr/ExplodedActual.cc \ + SymTab/Indexer.cc SymTab/Mangler.cc SymTab/Validate.cc \ + SymTab/FixFunction.cc SymTab/ImplementationType.cc \ + SymTab/TypeEquality.cc SymTab/Autogen.cc SynTree/Type.cc \ + SynTree/VoidType.cc SynTree/BasicType.cc \ + SynTree/PointerType.cc SynTree/ArrayType.cc \ + SynTree/ReferenceType.cc SynTree/FunctionType.cc \ + SynTree/ReferenceToType.cc SynTree/TupleType.cc \ + SynTree/TypeofType.cc SynTree/AttrType.cc \ SynTree/VarArgsType.cc SynTree/ZeroOneType.cc \ SynTree/Constant.cc SynTree/Expression.cc SynTree/TupleExpr.cc \ @@ -825,4 +827,7 @@ ResolvExpr/$(am__dirstamp) \ ResolvExpr/$(DEPDIR)/$(am__dirstamp) +ResolvExpr/driver_cfa_cpp-ExplodedActual.$(OBJEXT): \ + ResolvExpr/$(am__dirstamp) \ + ResolvExpr/$(DEPDIR)/$(am__dirstamp) SymTab/$(am__dirstamp): @$(MKDIR_P) SymTab @@ -1022,4 +1027,5 @@ @AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ConversionCost.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/driver_cfa_cpp-CurrentObject.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/driver_cfa_cpp-FindOpenVars.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/driver_cfa_cpp-Occurs.Po@am__quote@ @@ -1964,4 +1970,18 @@ @am__fastdepCXX_FALSE@ $(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o ResolvExpr/driver_cfa_cpp-CurrentObject.obj `if test -f 'ResolvExpr/CurrentObject.cc'; then $(CYGPATH_W) 'ResolvExpr/CurrentObject.cc'; else $(CYGPATH_W) '$(srcdir)/ResolvExpr/CurrentObject.cc'; fi` +ResolvExpr/driver_cfa_cpp-ExplodedActual.o: ResolvExpr/ExplodedActual.cc +@am__fastdepCXX_TRUE@ $(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT ResolvExpr/driver_cfa_cpp-ExplodedActual.o -MD -MP -MF ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Tpo -c -o ResolvExpr/driver_cfa_cpp-ExplodedActual.o `test -f 'ResolvExpr/ExplodedActual.cc' || echo '$(srcdir)/'`ResolvExpr/ExplodedActual.cc +@am__fastdepCXX_TRUE@ $(AM_V_at)$(am__mv) ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Tpo ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Po +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ $(AM_V_CXX)source='ResolvExpr/ExplodedActual.cc' object='ResolvExpr/driver_cfa_cpp-ExplodedActual.o' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCXX_FALSE@ $(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o ResolvExpr/driver_cfa_cpp-ExplodedActual.o `test -f 'ResolvExpr/ExplodedActual.cc' || echo '$(srcdir)/'`ResolvExpr/ExplodedActual.cc + +ResolvExpr/driver_cfa_cpp-ExplodedActual.obj: ResolvExpr/ExplodedActual.cc +@am__fastdepCXX_TRUE@ $(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT ResolvExpr/driver_cfa_cpp-ExplodedActual.obj -MD -MP -MF ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Tpo -c -o ResolvExpr/driver_cfa_cpp-ExplodedActual.obj `if test -f 'ResolvExpr/ExplodedActual.cc'; then $(CYGPATH_W) 'ResolvExpr/ExplodedActual.cc'; else $(CYGPATH_W) '$(srcdir)/ResolvExpr/ExplodedActual.cc'; fi` +@am__fastdepCXX_TRUE@ $(AM_V_at)$(am__mv) ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Tpo ResolvExpr/$(DEPDIR)/driver_cfa_cpp-ExplodedActual.Po +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ $(AM_V_CXX)source='ResolvExpr/ExplodedActual.cc' object='ResolvExpr/driver_cfa_cpp-ExplodedActual.obj' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCXX_FALSE@ $(AM_V_CXX@am__nodep@)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o ResolvExpr/driver_cfa_cpp-ExplodedActual.obj `if test -f 'ResolvExpr/ExplodedActual.cc'; then $(CYGPATH_W) 'ResolvExpr/ExplodedActual.cc'; else $(CYGPATH_W) '$(srcdir)/ResolvExpr/ExplodedActual.cc'; fi` + SymTab/driver_cfa_cpp-Indexer.o: SymTab/Indexer.cc @am__fastdepCXX_TRUE@ $(AM_V_CXX)$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT SymTab/driver_cfa_cpp-Indexer.o -MD -MP -MF SymTab/$(DEPDIR)/driver_cfa_cpp-Indexer.Tpo -c -o SymTab/driver_cfa_cpp-Indexer.o `test -f 'SymTab/Indexer.cc' || echo '$(srcdir)/'`SymTab/Indexer.cc Index: src/ResolvExpr/Alternative.h =================================================================== --- src/ResolvExpr/Alternative.h (revision 8dceeb78ad2ff73a75b2a0589e7539e4da01800f) +++ src/ResolvExpr/Alternative.h (revision 178e4ec86cc344917f0d9781c8bf4e520b7b2a53) @@ -37,4 +37,11 @@ void print( std::ostream &os, Indenter indent = {} ) const; + /// Returns the stored expression, but released from management of this Alternative + Expression* release_expr() { + Expression* tmp = expr; + expr = nullptr; + return tmp; + } + Cost cost; Cost cvtCost; Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision 8dceeb78ad2ff73a75b2a0589e7539e4da01800f) +++ src/ResolvExpr/AlternativeFinder.cc (revision 178e4ec86cc344917f0d9781c8bf4e520b7b2a53) @@ -30,4 +30,5 @@ #include "Common/utility.h" // for deleteAll, printAll, CodeLocation #include "Cost.h" // for Cost, Cost::zero, operator<<, Cost... +#include "ExplodedActual.h" // for ExplodedActual #include "InitTweak/InitTweak.h" // for getFunctionName #include "RenameVars.h" // for RenameVars, global_renamer @@ -590,23 +591,24 @@ unsigned nextArg; ///< Index of next argument in arguments list unsigned tupleStart; ///< Number of tuples that start at this index - // TODO fix this somehow - std::vector expls; ///< Exploded actuals left over from last match + unsigned nextExpl; ///< Index of next exploded element + unsigned explAlt; ///< Index of alternative for nextExpl > 0 ArgPack() : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0), - tupleStart(0), expls() {} + + tupleStart(0), nextExpl(0), explAlt(0) {} ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have, const OpenVarSet& openVars) : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have), - openVars(openVars), nextArg(0), tupleStart(0), expls() {} + openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {} ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg, - unsigned tupleStart = 0, Cost cost = Cost::zero, - std::vector&& expls = std::vector{} ) + unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0, + unsigned explAlt = 0 ) : parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)), have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart), - expls(move(expls)) {} + nextExpl(nextExpl), explAlt(explAlt) {} ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have, @@ -614,13 +616,13 @@ : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), cost(o.cost + added), env(move(env)), need(move(need)), have(move(have)), openVars(move(openVars)), - nextArg(nextArg), tupleStart(o.tupleStart), expls() {} - - - // ArgPack(const ArgPack& o) - // : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), env(o.env), - // need(o.need), have(o.have), openVars(o.openVars), nextArg(o.nextArg), - // tupleStart(o.tupleStart), expls(o.expls) {} - - // ArgPack(ArgPack&&) = default; + nextArg(nextArg), tupleStart(o.tupleStart), nextExpl(0), explAlt(0) {} + + /// true iff this pack is in the middle of an exploded argument + bool hasExpl() const { return nextExpl > 0; } + + /// Gets the list of exploded alternatives for this pack + const ExplodedActual& getExpl( const ExplodedArgs& args ) const { + return args[nextArg-1][explAlt]; + } /// Ends a tuple expression, consolidating the appropriate actuals @@ -644,6 +646,6 @@ /// Instantiates an argument to match a formal, returns false if no results left bool instantiateArgument( Type* formalType, Initializer* initializer, - const std::vector< AlternativeFinder >& args, std::vector& results, - std::size_t& genStart, const SymTab::Indexer& indexer, unsigned nTuples = 0 ) { + const ExplodedArgs& args, std::vector& results, std::size_t& genStart, + const SymTab::Indexer& indexer, unsigned nTuples = 0 ) { if ( TupleType* tupleType = dynamic_cast( formalType ) ) { // formalType is a TupleType - group actuals into a TupleExpr @@ -676,19 +678,20 @@ // add another argument to results for ( std::size_t i = genStart; i < genEnd; ++i ) { - // use remainder of exploded tuple if present - if ( ! results[i].expls.empty() ) { - const Alternative& actual = results[i].expls.front(); - - TypeEnvironment env = results[i].env; - OpenVarSet openVars = results[i].openVars; - - env.addActual( actual.env, openVars ); - - std::vector newExpls( - std::next( results[i].expls.begin() ), results[i].expls.end() ); + auto nextArg = results[i].nextArg; + + // use next element of exploded tuple if present + if ( results[i].hasExpl() ) { + const ExplodedActual& expl = results[i].getExpl( args ); + + unsigned nextExpl = results[i].nextExpl + 1; + if ( nextExpl == expl.exprs.size() ) { + nextExpl = 0; + } + results.emplace_back( - i, actual.expr, move(env), copy(results[i].need), - copy(results[i].have), move(openVars), results[i].nextArg, nTuples, - Cost::zero, move(newExpls) ); + i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env), + copy(results[i].need), copy(results[i].have), + copy(results[i].openVars), nextArg, nTuples, Cost::zero, nextExpl, + results[i].explAlt ); continue; @@ -696,9 +699,9 @@ // finish result when out of arguments - if ( results[i].nextArg >= args.size() ) { + if ( nextArg >= args.size() ) { ArgPack newResult{ results[i].env, results[i].need, results[i].have, results[i].openVars }; - newResult.nextArg = results[i].nextArg; + newResult.nextArg = nextArg; Type* argType; @@ -744,35 +747,27 @@ // add each possible next argument - auto j = results[i].nextArg; - for ( const Alternative& actual : args[j] ) { + for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { + const ExplodedActual& expl = args[nextArg][j]; + // fresh copies of parent parameters for this iteration TypeEnvironment env = results[i].env; OpenVarSet openVars = results[i].openVars; - env.addActual( actual.env, openVars ); - - // explode argument - std::vector exploded; - Tuples::explode( actual, indexer, back_inserter( exploded ) ); - if ( exploded.empty() ) { - // skip empty tuple arguments by (near-)cloning parent into next gen + env.addActual( expl.env, openVars ); + + // skip empty tuple arguments by (near-)cloning parent into next gen + if ( expl.exprs.empty() ) { results.emplace_back( results[i], move(env), copy(results[i].need), - copy(results[i].have), move(openVars), j + 1, actual.cost ); + copy(results[i].have), move(openVars), nextArg + 1, expl.cost ); continue; } - // trim first element from exploded - std::vector newExpls; - newExpls.reserve( exploded.size() - 1 ); - for ( std::size_t i = 1; i < exploded.size(); ++i ) { - newExpls.push_back( move(exploded[i]) ); - } // add new result results.emplace_back( - i, exploded.front().expr, move(env), copy(results[i].need), - copy(results[i].have), move(openVars), results[i].nextArg + 1, - nTuples, actual.cost, move(newExpls) ); + i, expl.exprs.front().get(), move(env), copy(results[i].need), + copy(results[i].have), move(openVars), nextArg + 1, + nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); } } @@ -793,7 +788,10 @@ std::size_t genEnd = results.size(); for ( std::size_t i = genStart; i < genEnd; ++i ) { + auto nextArg = results[i].nextArg; + // use remainder of exploded tuple if present - if ( ! results[i].expls.empty() ) { - const Alternative& actual = results[i].expls.front(); + if ( results[i].hasExpl() ) { + const ExplodedActual& expl = results[i].getExpl( args ); + Expression* expr = expl.exprs[results[i].nextExpl].get(); TypeEnvironment env = results[i].env; @@ -801,6 +799,5 @@ OpenVarSet openVars = results[i].openVars; - env.addActual( actual.env, openVars ); - Type* actualType = actual.expr->get_result(); + Type* actualType = expr->get_result(); PRINT( @@ -813,9 +810,12 @@ if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { - std::vector newExpls( - std::next( results[i].expls.begin() ), results[i].expls.end() ); + unsigned nextExpl = results[i].nextExpl + 1; + if ( nextExpl == expl.exprs.size() ) { + nextExpl = 0; + } + results.emplace_back( - i, actual.expr, move(env), move(need), move(have), move(openVars), - results[i].nextArg, nTuples, Cost::zero, move(newExpls) );; + i, expr, move(env), move(need), move(have), move(openVars), nextArg, + nTuples, Cost::zero, nextExpl, results[i].explAlt ); } @@ -824,5 +824,5 @@ // use default initializers if out of arguments - if ( results[i].nextArg >= args.size() ) { + if ( nextArg >= args.size() ) { if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) { if ( Constant* cnst = dynamic_cast( cnstExpr->get_constant() ) ) { @@ -835,5 +835,5 @@ results.emplace_back( i, cnstExpr, move(env), move(need), move(have), - move(openVars), results[i].nextArg, nTuples ); + move(openVars), nextArg, nTuples ); } } @@ -844,6 +844,7 @@ // Check each possible next argument - auto j = results[i].nextArg; - for ( const Alternative& actual : args[j] ) { + for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { + const ExplodedActual& expl = args[nextArg][j]; + // fresh copies of parent parameters for this iteration TypeEnvironment env = results[i].env; @@ -851,14 +852,11 @@ OpenVarSet openVars = results[i].openVars; - env.addActual( actual.env, openVars ); - - // explode argument - std::vector exploded; - Tuples::explode( actual, indexer, back_inserter( exploded ) ); - if ( exploded.empty() ) { - // skip empty tuple arguments by (near-)cloning parent into next gen + env.addActual( expl.env, openVars ); + + // skip empty tuple arguments by (near-)cloning parent into next gen + if ( expl.exprs.empty() ) { results.emplace_back( - results[i], move(env), move(need), move(have), move(openVars), j + 1, - actual.cost ); + results[i], move(env), move(need), move(have), move(openVars), + nextArg + 1, expl.cost ); continue; @@ -866,6 +864,6 @@ // consider only first exploded actual - const Alternative& aActual = exploded.front(); - Type* actualType = aActual.expr->get_result()->clone(); + Expression* expr = expl.exprs.front().get(); + Type* actualType = expr->get_result()->clone(); PRINT( @@ -879,14 +877,8 @@ // attempt to unify types if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { - // trim first element from exploded - std::vector newExpls; - newExpls.reserve( exploded.size() - 1 ); - for ( std::size_t i = 1; i < exploded.size(); ++i ) { - newExpls.push_back( move(exploded[i]) ); - } // add new result results.emplace_back( - i, aActual.expr, move(env), move(need), move(have), move(openVars), - j + 1, nTuples, actual.cost, move(newExpls) ); + i, expr, move(env), move(need), move(have), move(openVars), nextArg + 1, + nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); } } @@ -924,6 +916,5 @@ template void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, - FunctionType *funcType, const std::vector< AlternativeFinder > &args, - OutputIterator out ) { + FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) { OpenVarSet funcOpenVars; AssertionSet funcNeed, funcHave; @@ -964,19 +955,20 @@ // iterate results for ( std::size_t i = genStart; i < genEnd; ++i ) { + auto nextArg = results[i].nextArg; + // use remainder of exploded tuple if present - if ( ! results[i].expls.empty() ) { - const Alternative& actual = results[i].expls.front(); - - TypeEnvironment env = results[i].env; - OpenVarSet openVars = results[i].openVars; - - env.addActual( actual.env, openVars ); - - std::vector newExpls( - std::next( results[i].expls.begin() ), results[i].expls.end() ); + if ( results[i].hasExpl() ) { + const ExplodedActual& expl = results[i].getExpl( args ); + + unsigned nextExpl = results[i].nextExpl + 1; + if ( nextExpl == expl.exprs.size() ) { + nextExpl = 0; + } + results.emplace_back( - i, actual.expr, move(env), copy(results[i].need), - copy(results[i].have), move(openVars), results[i].nextArg, 0, - Cost::zero, move(newExpls) ); + i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env), + copy(results[i].need), copy(results[i].have), + copy(results[i].openVars), nextArg, 0, Cost::zero, nextExpl, + results[i].explAlt ); continue; @@ -984,5 +976,5 @@ // finish result when out of arguments - if ( results[i].nextArg >= args.size() ) { + if ( nextArg >= args.size() ) { validateFunctionAlternative( func, results[i], results, out ); @@ -991,34 +983,27 @@ // add each possible next argument - auto j = results[i].nextArg; - for ( const Alternative& actual : args[j] ) { + for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { + const ExplodedActual& expl = args[nextArg][j]; + // fresh copies of parent parameters for this iteration TypeEnvironment env = results[i].env; OpenVarSet openVars = results[i].openVars; - env.addActual( actual.env, openVars ); - - // explode argument - std::vector exploded; - Tuples::explode( actual, indexer, back_inserter( exploded ) ); - if ( exploded.empty() ) { - // skip empty tuple arguments by (near-)cloning parent into next gen + env.addActual( expl.env, openVars ); + + // skip empty tuple arguments by (near-)cloning parent into next gen + if ( expl.exprs.empty() ) { results.emplace_back( results[i], move(env), copy(results[i].need), - copy(results[i].have), move(openVars), j + 1, actual.cost ); + copy(results[i].have), move(openVars), nextArg + 1, expl.cost ); + continue; } - // trim first element from exploded - std::vector newExpls; - newExpls.reserve( exploded.size() - 1 ); - for ( std::size_t i = 1; i < exploded.size(); ++i ) { - newExpls.push_back( move(exploded[i]) ); - } // add new result results.emplace_back( - i, exploded.front().expr, move(env), copy(results[i].need), - copy(results[i].have), move(openVars), j + 1, 0, - actual.cost, move(newExpls) ); + i, expl.exprs.front().get(), move(env), copy(results[i].need), + copy(results[i].have), move(openVars), nextArg + 1, 0, + expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); } } @@ -1030,5 +1015,5 @@ for ( std::size_t i = genStart; i < results.size(); ++i ) { ArgPack& result = results[i]; - if ( result.expls.empty() && result.nextArg >= args.size() ) { + if ( ! result.hasExpl() && result.nextArg >= args.size() ) { validateFunctionAlternative( func, result, results, out ); } @@ -1060,4 +1045,18 @@ printAlts( funcOpFinder.alternatives, std::cerr, 1 ); ) + + // pre-explode arguments + ExplodedArgs argExpansions; + argExpansions.reserve( argAlternatives.size() ); + + for ( const AlternativeFinder& arg : argAlternatives ) { + argExpansions.emplace_back(); + auto& argE = argExpansions.back(); + argE.reserve( arg.alternatives.size() ); + + for ( const Alternative& actual : arg ) { + argE.emplace_back( actual, indexer ); + } + } AltList candidates; @@ -1074,5 +1073,5 @@ Alternative newFunc( *func ); referenceToRvalueConversion( newFunc.expr ); - makeFunctionAlternatives( newFunc, function, argAlternatives, + makeFunctionAlternatives( newFunc, function, argExpansions, std::back_inserter( candidates ) ); } @@ -1083,5 +1082,5 @@ Alternative newFunc( *func ); referenceToRvalueConversion( newFunc.expr ); - makeFunctionAlternatives( newFunc, function, argAlternatives, + makeFunctionAlternatives( newFunc, function, argExpansions, std::back_inserter( candidates ) ); } // if @@ -1095,6 +1094,11 @@ // try each function operator ?() with each function alternative if ( ! funcOpFinder.alternatives.empty() ) { - // add function alternatives to front of argument list - argAlternatives.insert( argAlternatives.begin(), move(funcFinder) ); + // add exploded function alternatives to front of argument list + std::vector funcE; + funcE.reserve( funcFinder.alternatives.size() ); + for ( const Alternative& actual : funcFinder ) { + funcE.emplace_back( actual, indexer ); + } + argExpansions.insert( argExpansions.begin(), move(funcE) ); for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin(); @@ -1108,5 +1112,5 @@ Alternative newFunc( *funcOp ); referenceToRvalueConversion( newFunc.expr ); - makeFunctionAlternatives( newFunc, function, argAlternatives, + makeFunctionAlternatives( newFunc, function, argExpansions, std::back_inserter( candidates ) ); } Index: src/ResolvExpr/AlternativeFinder.h =================================================================== --- src/ResolvExpr/AlternativeFinder.h (revision 8dceeb78ad2ff73a75b2a0589e7539e4da01800f) +++ src/ResolvExpr/AlternativeFinder.h (revision 178e4ec86cc344917f0d9781c8bf4e520b7b2a53) @@ -21,4 +21,5 @@ #include "Alternative.h" // for AltList, Alternative +#include "ExplodedActual.h" // for ExplodedActual #include "ResolvExpr/Cost.h" // for Cost, Cost::infinity #include "ResolvExpr/TypeEnvironment.h" // for AssertionSet, OpenVarSet @@ -32,4 +33,8 @@ namespace ResolvExpr { struct ArgPack; + + /// First index is which argument, second index is which alternative for that argument, + /// third index is which exploded element of that alternative + using ExplodedArgs = std::vector< std::vector< ExplodedActual > >; class AlternativeFinder : public Visitor { @@ -133,5 +138,5 @@ /// Finds matching alternatives for a function, given a set of arguments template - void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const std::vector< AlternativeFinder >& args, OutputIterator out ); + void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs& args, OutputIterator out ); /// Checks if assertion parameters match for a new alternative template< typename OutputIterator > Index: src/ResolvExpr/ExplodedActual.cc =================================================================== --- src/ResolvExpr/ExplodedActual.cc (revision 178e4ec86cc344917f0d9781c8bf4e520b7b2a53) +++ src/ResolvExpr/ExplodedActual.cc (revision 178e4ec86cc344917f0d9781c8bf4e520b7b2a53) @@ -0,0 +1,25 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Alternative.h -- +// +// Author : Aaron B. Moss +// Created On : Tue Nov 22 17:06:00 2017 +// Last Modified By : Aaron B. Moss +// Last Modified On : Tue Nov 22 17:06:00 2017 +// Update Count : 1 +// + +#include "ExplodedActual.h" + +#include "Tuples/Explode.h" // for Tuples::explode + +namespace ResolvExpr { + ExplodedActual::ExplodedActual( const Alternative& actual, const SymTab::Indexer& indexer ) + : env(actual.env), cost(actual.cost), exprs() { + Tuples::explode( actual, indexer, *this ); + } +} Index: src/ResolvExpr/ExplodedActual.h =================================================================== --- src/ResolvExpr/ExplodedActual.h (revision 178e4ec86cc344917f0d9781c8bf4e520b7b2a53) +++ src/ResolvExpr/ExplodedActual.h (revision 178e4ec86cc344917f0d9781c8bf4e520b7b2a53) @@ -0,0 +1,37 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Alternative.h -- +// +// Author : Aaron B. Moss +// Created On : Tue Nov 22 17:06:00 2017 +// Last Modified By : Aaron B. Moss +// Last Modified On : Tue Nov 22 17:06:00 2017 +// Update Count : 1 +// + +#pragma once + +#include +#include + +#include "Alternative.h" // for Alternative, AltList +#include "Cost.h" // for Cost +#include "TypeEnvironment.h" // for TypeEnvironment +#include "SymTab/Indexer.h" // for Indexer + +namespace ResolvExpr { + /// Pre-exploded actual + struct ExplodedActual { + TypeEnvironment env; + Cost cost; + std::vector< std::unique_ptr > exprs; + + ExplodedActual() : env(), cost(Cost::zero), exprs() {} + + ExplodedActual( const Alternative& actual, const SymTab::Indexer& indexer ); + }; +} Index: src/ResolvExpr/module.mk =================================================================== --- src/ResolvExpr/module.mk (revision 8dceeb78ad2ff73a75b2a0589e7539e4da01800f) +++ src/ResolvExpr/module.mk (revision 178e4ec86cc344917f0d9781c8bf4e520b7b2a53) @@ -32,3 +32,4 @@ ResolvExpr/Occurs.cc \ ResolvExpr/TypeEnvironment.cc \ - ResolvExpr/CurrentObject.cc + ResolvExpr/CurrentObject.cc \ + ResolvExpr/ExplodedActual.cc Index: src/Tuples/Explode.h =================================================================== --- src/Tuples/Explode.h (revision 8dceeb78ad2ff73a75b2a0589e7539e4da01800f) +++ src/Tuples/Explode.h (revision 178e4ec86cc344917f0d9781c8bf4e520b7b2a53) @@ -16,10 +16,12 @@ #pragma once -#include // for back_inserter, back_insert_iterator +#include // for back_inserter, back_insert_iterator +#include // for forward -#include "ResolvExpr/Alternative.h" // for Alternative, AltList -#include "SynTree/Expression.h" // for Expression, UniqueExpr, AddressExpr -#include "SynTree/Type.h" // for TupleType, Type -#include "Tuples.h" // for maybeImpure +#include "ResolvExpr/Alternative.h" // for Alternative, AltList +#include "ResolvExpr/ExplodedActual.h" // for ExplodedActual +#include "SynTree/Expression.h" // for Expression, UniqueExpr, AddressExpr +#include "SynTree/Type.h" // for TupleType, Type +#include "Tuples.h" // for maybeImpure namespace SymTab { @@ -39,16 +41,32 @@ } + /// Append alternative to an OutputIterator of Alternatives + template + void append( OutputIterator out, Expression* expr, const ResolvExpr::TypeEnvironment& env, + const ResolvExpr::Cost& cost, const ResolvExpr::Cost& cvtCost ) { + *out++ = ResolvExpr::Alternative{ expr, env, cost, cvtCost }; + } + + /// Append alternative to an ExplodedActual + static inline void append( ResolvExpr::ExplodedActual& ea, Expression* expr, + const ResolvExpr::TypeEnvironment&, const ResolvExpr::Cost&, const ResolvExpr::Cost& ) { + ea.exprs.emplace_back( expr ); + /// xxx -- merge environment, cost? + } + /// helper function used by explode - template< typename OutputIterator > - void explodeUnique( Expression * expr, const ResolvExpr::Alternative & alt, const SymTab::Indexer & indexer, OutputIterator out, bool isTupleAssign ) { + template< typename Output > + void explodeUnique( Expression * expr, const ResolvExpr::Alternative & alt, + const SymTab::Indexer & indexer, Output&& out, bool isTupleAssign ) { if ( isTupleAssign ) { // tuple assignment needs CastExprs to be recursively exploded to easily get at all of the components if ( CastExpr * castExpr = isReferenceCast( expr ) ) { ResolvExpr::AltList alts; - explodeUnique( castExpr->get_arg(), alt, indexer, back_inserter( alts ), isTupleAssign ); + explodeUnique( + castExpr->get_arg(), alt, indexer, back_inserter( alts ), isTupleAssign ); for ( ResolvExpr::Alternative & alt : alts ) { // distribute reference cast over all components - alt.expr = distributeReference( alt.expr ); - *out++ = alt; + append( std::forward(out), distributeReference( alt.release_expr() ), + alt.env, alt.cost, alt.cvtCost ); } // in tuple assignment, still need to handle the other cases, but only if not already handled here (don't want to output too many alternatives) @@ -61,5 +79,5 @@ // can open tuple expr and dump its exploded components for ( Expression * expr : tupleExpr->get_exprs() ) { - explodeUnique( expr, alt, indexer, out, isTupleAssign ); + explodeUnique( expr, alt, indexer, std::forward(out), isTupleAssign ); } } else { @@ -77,5 +95,5 @@ for ( unsigned int i = 0; i < tupleType->size(); i++ ) { TupleIndexExpr * idx = new TupleIndexExpr( arg->clone(), i ); - explodeUnique( idx, alt, indexer, out, isTupleAssign ); + explodeUnique( idx, alt, indexer, std::forward(out), isTupleAssign ); delete idx; } @@ -84,25 +102,28 @@ } else { // atomic (non-tuple) type - output a clone of the expression in a new alternative - *out++ = ResolvExpr::Alternative( expr->clone(), alt.env, alt.cost, alt.cvtCost ); + append( std::forward(out), expr->clone(), alt.env, alt.cost, alt.cvtCost ); } } /// expands a tuple-valued alternative into multiple alternatives, each with a non-tuple-type - template< typename OutputIterator > - void explode( const ResolvExpr::Alternative &alt, const SymTab::Indexer & indexer, OutputIterator out, bool isTupleAssign = false ) { - explodeUnique( alt.expr, alt, indexer, out, isTupleAssign ); + template< typename Output > + void explode( const ResolvExpr::Alternative &alt, const SymTab::Indexer & indexer, + Output&& out, bool isTupleAssign = false ) { + explodeUnique( alt.expr, alt, indexer, std::forward(out), isTupleAssign ); } // explode list of alternatives - template< typename AltIterator, typename OutputIterator > - void explode( AltIterator altBegin, AltIterator altEnd, const SymTab::Indexer & indexer, OutputIterator out, bool isTupleAssign = false ) { + template< typename AltIterator, typename Output > + void explode( AltIterator altBegin, AltIterator altEnd, const SymTab::Indexer & indexer, + Output&& out, bool isTupleAssign = false ) { for ( ; altBegin != altEnd; ++altBegin ) { - explode( *altBegin, indexer, out, isTupleAssign ); + explode( *altBegin, indexer, std::forward(out), isTupleAssign ); } } - template< typename OutputIterator > - void explode( const ResolvExpr::AltList & alts, const SymTab::Indexer & indexer, OutputIterator out, bool isTupleAssign = false ) { - explode( alts.begin(), alts.end(), indexer, out, isTupleAssign ); + template< typename Output > + void explode( const ResolvExpr::AltList & alts, const SymTab::Indexer & indexer, Output&& out, + bool isTupleAssign = false ) { + explode( alts.begin(), alts.end(), indexer, std::forward(out), isTupleAssign ); } } // namespace Tuples