Index: src/Makefile.in =================================================================== --- src/Makefile.in (revision 9f10d1f275f029a757920961a67b1ee9f4c4c248) +++ src/Makefile.in (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) @@ -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/Parser/DeclarationNode.cc =================================================================== --- src/Parser/DeclarationNode.cc (revision 9f10d1f275f029a757920961a67b1ee9f4c4c248) +++ src/Parser/DeclarationNode.cc (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) @@ -10,6 +10,6 @@ // Created On : Sat May 16 12:34:05 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Sat Sep 23 18:16:48 2017 -// Update Count : 1024 +// Last Modified On : Mon Nov 20 09:21:52 2017 +// Update Count : 1031 // @@ -509,16 +509,13 @@ DeclarationNode * DeclarationNode::addQualifiers( DeclarationNode * q ) { - if ( ! q ) { delete q; return this; } + if ( ! q ) { delete q; return this; } // empty qualifier checkSpecifiers( q ); copySpecifiers( q ); - if ( ! q->type ) { - delete q; - return this; - } // if + if ( ! q->type ) { delete q; return this; } if ( ! type ) { - type = q->type; // reuse this structure + type = q->type; // reuse structure q->type = nullptr; delete q; @@ -526,17 +523,21 @@ } // if - if ( q->type->forall ) { - if ( type->forall ) { - type->forall->appendList( q->type->forall ); + if ( q->type->forall ) { // forall qualifier ? + if ( type->forall ) { // polymorphic routine ? + type->forall->appendList( q->type->forall ); // augment forall qualifier } else { - if ( type->kind == TypeData::Aggregate ) { - type->aggregate.params = q->type->forall; - // change implicit typedef from TYPEDEFname to TYPEGENname - typedefTable.changeKind( *type->aggregate.name, TypedefTable::TG ); - } else { - type->forall = q->type->forall; + if ( type->kind == TypeData::Aggregate ) { // struct/union ? + if ( type->aggregate.params ) { // polymorphic ? + type->aggregate.params->appendList( q->type->forall ); // augment forall qualifier + } else { // not polymorphic + type->aggregate.params = q->type->forall; // make polymorphic type + // change implicit typedef from TYPEDEFname to TYPEGENname + typedefTable.changeKind( *type->aggregate.name, TypedefTable::TG ); + } // if + } else { // not polymorphic + type->forall = q->type->forall; // make polymorphic routine } // if } // if - q->type->forall = nullptr; + q->type->forall = nullptr; // forall qualifier moved } // if Index: src/Parser/parser.yy =================================================================== --- src/Parser/parser.yy (revision 9f10d1f275f029a757920961a67b1ee9f4c4c248) +++ src/Parser/parser.yy (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) @@ -10,6 +10,6 @@ // Created On : Sat Sep 1 20:22:55 2001 // Last Modified By : Peter A. Buhr -// Last Modified On : Wed Oct 25 12:28:54 2017 -// Update Count : 2893 +// Last Modified On : Mon Nov 20 09:45:36 2017 +// Update Count : 2945 // @@ -114,4 +114,16 @@ } // for } // distExt + +// There is an ambiguity for inline generic-routine return-types and generic routines. +// forall( otype T ) struct S { int i; } bar( T ) {} +// Does the forall bind to the struct or the routine, and how would it be possible to explicitly specify the binding. +// forall( otype T ) struct S { int T; } forall( otype W ) bar( W ) {} + +void rebindForall( DeclarationNode * declSpec, DeclarationNode * funcDecl ) { + if ( declSpec->type->kind == TypeData::Aggregate ) { // return is aggregate definition + funcDecl->type->forall = declSpec->type->aggregate.params; // move forall from aggregate to function type + declSpec->type->aggregate.params = nullptr; + } // if +} // rebindForall bool forall = false; // aggregate have one or more forall qualifiers ? @@ -348,9 +360,8 @@ -// Handle single shift/reduce conflict for dangling else by shifting the ELSE token. For example, this string -// is ambiguous: -// .---------. matches IF '(' comma_expression ')' statement . (reduce) -// if ( C ) S1 else S2 -// `-----------------' matches IF '(' comma_expression ')' statement . (shift) ELSE statement */ +// Handle shift/reduce conflict for dangling else by shifting the ELSE token. For example, this string is ambiguous: +// .---------. matches IF '(' comma_expression ')' statement . (reduce) +// if ( C ) S1 else S2 +// `-----------------' matches IF '(' comma_expression ')' statement . (shift) ELSE statement */ // Similar issues exit with the waitfor statement. @@ -361,4 +372,16 @@ %precedence TIMEOUT // token precedence for start of TIMEOUT in WAITFOR statement %precedence ELSE // token precedence for start of else clause in IF/WAITFOR statement + +// Handle shift/reduce conflict for generic type by shifting the '(' token. For example, this string is ambiguous: +// forall( otype T ) struct Foo { T v; }; +// .-----. matches pointer to function returning a generic (which is impossible without a type) +// Foo ( *fp )( int ); +// `---' matches start of TYPEGENname '(' +// Must be: +// Foo( int ) ( *fp )( int ); + +// Order of these lines matters (low-to-high precedence). +%precedence TYPEGENname +%precedence '(' %locations // support location tracking for error messages @@ -1765,5 +1788,7 @@ typegen_name: // CFA - TYPEGENname '(' ')' + TYPEGENname + { $$ = DeclarationNode::newFromTypeGen( $1, nullptr ); } + | TYPEGENname '(' ')' { $$ = DeclarationNode::newFromTypeGen( $1, nullptr ); } | TYPEGENname '(' type_list ')' @@ -1809,5 +1834,13 @@ } | aggregate_key attribute_list_opt typegen_name // CFA - { $$ = $3->addQualifiers( $2 ); } + { + // Create new generic declaration with same name as previous forward declaration, where the IDENTIFIER is + // switched to a TYPEGENname. Link any generic arguments from typegen_name to new generic declaration and + // delete newFromTypeGen. + $$ = DeclarationNode::newAggregate( $1, $3->type->symbolic.name, $3->type->symbolic.actuals, nullptr, false )->addQualifiers( $2 ); + $3->type->symbolic.name = nullptr; + $3->type->symbolic.actuals = nullptr; + delete $3; + } ; @@ -2380,4 +2413,5 @@ | declaration_specifier function_declarator with_clause_opt compound_statement { + rebindForall( $1, $2 ); typedefTable.addToEnclosingScope( TypedefTable::ID ); typedefTable.leaveScope(); @@ -2406,4 +2440,5 @@ | declaration_specifier KR_function_declarator KR_declaration_list_opt with_clause_opt compound_statement { + rebindForall( $1, $2 ); typedefTable.addToEnclosingScope( TypedefTable::ID ); typedefTable.leaveScope(); Index: src/ResolvExpr/Alternative.cc =================================================================== --- src/ResolvExpr/Alternative.cc (revision 9f10d1f275f029a757920961a67b1ee9f4c4c248) +++ src/ResolvExpr/Alternative.cc (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) @@ -18,4 +18,5 @@ #include // for operator<<, ostream, basic_o... #include // for operator<<, char_traits, string +#include // for move #include "Common/utility.h" // for maybeClone @@ -81,4 +82,18 @@ os << std::endl; } + + void splice( AltList& dst, AltList& src ) { + dst.reserve( dst.size() + src.size() ); + for ( Alternative& alt : src ) { + dst.push_back( std::move(alt) ); + } + src.clear(); + } + + void spliceBegin( AltList& dst, AltList& src ) { + splice( src, dst ); + dst.swap( src ); + } + } // namespace ResolvExpr Index: src/ResolvExpr/Alternative.h =================================================================== --- src/ResolvExpr/Alternative.h (revision 9f10d1f275f029a757920961a67b1ee9f4c4c248) +++ src/ResolvExpr/Alternative.h (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) @@ -17,5 +17,5 @@ #include // for ostream -#include // for list +#include // for vector #include "Cost.h" // for Cost @@ -25,8 +25,4 @@ namespace ResolvExpr { - struct Alternative; - - typedef std::list< Alternative > AltList; - struct Alternative { Alternative(); @@ -46,4 +42,12 @@ TypeEnvironment env; }; + + typedef std::vector< Alternative > AltList; + + /// Moves all elements from src to the end of dst + void splice( AltList& dst, AltList& src ); + + /// Moves all elements from src to the beginning of dst + void spliceBegin( AltList& dst, AltList& src ); } // namespace ResolvExpr Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision 9f10d1f275f029a757920961a67b1ee9f4c4c248) +++ src/ResolvExpr/AlternativeFinder.cc (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) @@ -16,9 +16,10 @@ #include // for copy #include // for strict_dynamic_cast, assert, assertf +#include // for size_t #include // for operator<<, cerr, ostream, endl #include // for back_insert_iterator, back_inserter #include // for _List_iterator, list, _List_const_... #include // for _Rb_tree_iterator, map, _Rb_tree_c... -#include // for allocator_traits<>::value_type +#include // for allocator_traits<>::value_type, unique_ptr #include // for pair #include // for vector @@ -29,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 @@ -50,4 +52,10 @@ #define PRINT( text ) if ( resolvep ) { text } //#define DEBUG_COST + +using std::move; + +/// copies any copyable type +template +T copy(const T& x) { return x; } namespace ResolvExpr { @@ -187,7 +195,7 @@ printAlts( alternatives, std::cerr ); ) - AltList::iterator oldBegin = alternatives.begin(); - pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ) ); - if ( failFast && alternatives.begin() == oldBegin ) { + AltList pruned; + pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned ) ); + if ( failFast && pruned.empty() ) { std::ostringstream stream; AltList winners; @@ -199,5 +207,5 @@ throw SemanticError( stream.str() ); } - alternatives.erase( oldBegin, alternatives.end() ); + alternatives = move(pruned); PRINT( std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl; @@ -571,148 +579,226 @@ /// State to iteratively build a match of parameter expressions to arguments struct ArgPack { - AltList actuals; ///< Arguments included in this pack - TypeEnvironment env; ///< Environment for this pack - AssertionSet need; ///< Assertions outstanding for this pack - AssertionSet have; ///< Assertions found for this pack - OpenVarSet openVars; ///< Open variables for this pack - unsigned nextArg; ///< Index of next argument in arguments list - std::vector expls; ///< Exploded actuals left over from last match - unsigned nextExpl; ///< Index of next exploded alternative to use - std::vector tupleEls; /// Number of elements in current tuple element(s) - - ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have, + std::size_t parent; ///< Index of parent pack + std::unique_ptr expr; ///< The argument stored here + Cost cost; ///< The cost of this argument + TypeEnvironment env; ///< Environment for this pack + AssertionSet need; ///< Assertions outstanding for this pack + AssertionSet have; ///< Assertions found for this pack + OpenVarSet openVars; ///< Open variables for this pack + unsigned nextArg; ///< Index of next argument in arguments list + unsigned tupleStart; ///< Number of tuples that start at this index + 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), nextExpl(0), explAlt(0) {} + + ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have, const OpenVarSet& openVars) - : actuals(), env(env), need(need), have(have), openVars(openVars), nextArg(0), - expls(), nextExpl(0), tupleEls() {} - - /// Starts a new tuple expression - void beginTuple() { - if ( ! tupleEls.empty() ) ++tupleEls.back(); - tupleEls.push_back(0); - } - + : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have), + 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, 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), + nextExpl(nextExpl), explAlt(explAlt) {} + + ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have, + OpenVarSet&& openVars, unsigned nextArg, Cost added ) + : 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), 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 - void endTuple() { - // set up new Tuple alternative + void endTuple( const std::vector& packs ) { + // add all expressions in tuple to list, summing cost std::list exprs; - Cost cost = Cost::zero; - - // transfer elements into alternative - for (unsigned i = 0; i < tupleEls.back(); ++i) { - exprs.push_front( actuals.back().expr ); - actuals.back().expr = nullptr; - cost += actuals.back().cost; - actuals.pop_back(); - } - tupleEls.pop_back(); - - // build new alternative - actuals.emplace_back( new TupleExpr( exprs ), this->env, cost ); - } - - /// Clones and adds an actual, returns this - ArgPack& withArg( Expression* expr, Cost cost = Cost::zero ) { - actuals.emplace_back( expr->clone(), this->env, cost ); - if ( ! tupleEls.empty() ) ++tupleEls.back(); - return *this; + const ArgPack* pack = this; + if ( expr ) { exprs.push_front( expr.release() ); } + while ( pack->tupleStart == 0 ) { + pack = &packs[pack->parent]; + exprs.push_front( pack->expr->clone() ); + cost += pack->cost; + } + // reset pack to appropriate tuple + expr.reset( new TupleExpr( exprs ) ); + tupleStart = pack->tupleStart - 1; + parent = pack->parent; } }; /// 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::vector& nextResults, - const SymTab::Indexer& indexer ) { + bool instantiateArgument( Type* formalType, Initializer* initializer, + 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 - for ( ArgPack& result : results ) { result.beginTuple(); } + ++nTuples; for ( Type* type : *tupleType ) { // xxx - dropping initializer changes behaviour from previous, but seems correct - if ( ! instantiateArgument( type, nullptr, args, results, nextResults, indexer ) ) + if ( ! instantiateArgument( + type, nullptr, args, results, genStart, indexer, nTuples ) ) return false; - } - for ( ArgPack& result : results ) { result.endTuple(); } + nTuples = 0; + } + // re-consititute tuples for final generation + for ( auto i = genStart; i < results.size(); ++i ) { + results[i].endTuple( results ); + } return true; } else if ( TypeInstType* ttype = Tuples::isTtype( formalType ) ) { // formalType is a ttype, consumes all remaining arguments // xxx - mixing default arguments with variadic?? - std::vector finalResults{}; /// list of completed tuples - // start tuples - for ( ArgPack& result : results ) { - result.beginTuple(); - - // use rest of exploded tuple if present - while ( result.nextExpl < result.expls.size() ) { - const Alternative& actual = result.expls[result.nextExpl]; - result.env.addActual( actual.env, result.openVars ); - result.withArg( actual.expr ); - ++result.nextExpl; - } - } + + // completed tuples; will be spliced to end of results to finish + std::vector finalResults{}; + // iterate until all results completed - while ( ! results.empty() ) { + std::size_t genEnd; + ++nTuples; + do { + genEnd = results.size(); + // add another argument to results - for ( ArgPack& result : results ) { - // finish result when out of arguments - if ( result.nextArg >= args.size() ) { - Type* argType = result.actuals.back().expr->get_result(); - if ( result.tupleEls.back() == 1 && Tuples::isTtype( argType ) ) { - // the case where a ttype value is passed directly is special, e.g. for - // argument forwarding purposes - // xxx - what if passing multiple arguments, last of which is ttype? - // xxx - what would happen if unify was changed so that unifying tuple - // types flattened both before unifying lists? then pass in TupleType - // (ttype) below. - result.tupleEls.pop_back(); - } else { - // collapse leftover arguments into tuple - result.endTuple(); - argType = result.actuals.back().expr->get_result(); + for ( std::size_t i = genStart; i < genEnd; ++i ) { + auto nextArg = results[i].nextArg; + + // use remainder of exploded tuple if present + if ( results[i].hasExpl() ) { + const ExplodedActual& expl = results[i].getExpl( args ); + const Alternative& actual = expl.alts[results[i].nextExpl]; + + TypeEnvironment env = results[i].env; + OpenVarSet openVars = results[i].openVars; + + env.addActual( actual.env, openVars ); + + unsigned nextExpl = results[i].nextExpl + 1; + if ( nextExpl == expl.alts.size() ) { + nextExpl = 0; } - // check unification for ttype before adding to final - if ( unify( ttype, argType, result.env, result.need, result.have, - result.openVars, indexer ) ) { - finalResults.push_back( std::move(result) ); - } + + results.emplace_back( + i, actual.expr, move(env), copy(results[i].need), + copy(results[i].have), move(openVars), nextArg, nTuples, + Cost::zero, nextExpl, results[i].explAlt ); + continue; } + + // finish result when out of arguments + if ( nextArg >= args.size() ) { + ArgPack newResult{ + results[i].env, results[i].need, results[i].have, + results[i].openVars }; + newResult.nextArg = nextArg; + Type* argType; + + if ( nTuples > 0 ) { + // first iteration, push empty tuple expression + newResult.parent = i; + std::list emptyList; + newResult.expr.reset( new TupleExpr( emptyList ) ); + argType = newResult.expr->get_result(); + } else { + // clone result to collect tuple + newResult.parent = results[i].parent; + newResult.cost = results[i].cost; + newResult.tupleStart = results[i].tupleStart; + newResult.expr.reset( results[i].expr->clone() ); + argType = newResult.expr->get_result(); + + if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) { + // the case where a ttype value is passed directly is special, + // e.g. for argument forwarding purposes + // xxx - what if passing multiple arguments, last of which is + // ttype? + // xxx - what would happen if unify was changed so that unifying + // tuple + // types flattened both before unifying lists? then pass in + // TupleType (ttype) below. + --newResult.tupleStart; + } else { + // collapse leftover arguments into tuple + newResult.endTuple( results ); + argType = newResult.expr->get_result(); + } + } + + // check unification for ttype before adding to final + if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have, + newResult.openVars, indexer ) ) { + finalResults.push_back( move(newResult) ); + } + + continue; + } // add each possible next argument - for ( const Alternative& actual : args[result.nextArg] ) { - ArgPack aResult = result; // copy to clone everything - // add details of actual to result - aResult.env.addActual( actual.env, aResult.openVars ); - Cost cost = actual.cost; - - // explode argument - std::vector exploded; - Tuples::explode( actual, indexer, back_inserter( exploded ) ); - - // add exploded argument to tuple - for ( Alternative& aActual : exploded ) { - aResult.withArg( aActual.expr, cost ); - cost = Cost::zero; + 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( expl.env, openVars ); + + // skip empty tuple arguments by (near-)cloning parent into next gen + if ( expl.alts.empty() ) { + results.emplace_back( + results[i], move(env), copy(results[i].need), + copy(results[i].have), move(openVars), nextArg + 1, expl.cost ); + + continue; } - ++aResult.nextArg; - nextResults.push_back( std::move(aResult) ); + + // add new result + results.emplace_back( + i, expl.alts.front().expr, move(env), copy(results[i].need), + copy(results[i].have), move(openVars), nextArg + 1, + nTuples, expl.cost, expl.alts.size() == 1 ? 0 : 1, j ); } } // reset for next round - results.swap( nextResults ); - nextResults.clear(); - } - results.swap( finalResults ); - return ! results.empty(); + genStart = genEnd; + nTuples = 0; + } while ( genEnd != results.size() ); + + // splice final results onto results + for ( std::size_t i = 0; i < finalResults.size(); ++i ) { + results.push_back( move(finalResults[i]) ); + } + return ! finalResults.empty(); } // iterate each current subresult - for ( unsigned iResult = 0; iResult < results.size(); ++iResult ) { - ArgPack& result = results[iResult]; - - if ( result.nextExpl < result.expls.size() ) { - // use remainder of exploded tuple if present - const Alternative& actual = result.expls[result.nextExpl]; - result.env.addActual( actual.env, result.openVars ); + 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].hasExpl() ) { + const ExplodedActual& expl = results[i].getExpl( args ); + const Alternative& actual = expl.alts[results[i].nextExpl]; + + TypeEnvironment env = results[i].env; + AssertionSet need = results[i].need, have = results[i].have; + OpenVarSet openVars = results[i].openVars; + + env.addActual( actual.env, openVars ); Type* actualType = actual.expr->get_result(); @@ -724,44 +810,62 @@ std::cerr << std::endl; ) - - if ( unify( formalType, actualType, result.env, result.need, result.have, - result.openVars, indexer ) ) { - ++result.nextExpl; - nextResults.push_back( std::move(result.withArg( actual.expr )) ); + + if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { + unsigned nextExpl = results[i].nextExpl + 1; + if ( nextExpl == expl.alts.size() ) { + nextExpl = 0; + } + + results.emplace_back( + i, actual.expr, move(env), move(need), move(have), move(openVars), + nextArg, nTuples, Cost::zero, nextExpl, results[i].explAlt ); } continue; - } else if ( result.nextArg >= args.size() ) { - // use default initializers if out of arguments + } + + // use default initializers if out of arguments + if ( nextArg >= args.size() ) { if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) { if ( Constant* cnst = dynamic_cast( cnstExpr->get_constant() ) ) { - if ( unify( formalType, cnst->get_type(), result.env, result.need, - result.have, result.openVars, indexer ) ) { - nextResults.push_back( std::move(result.withArg( cnstExpr )) ); + TypeEnvironment env = results[i].env; + AssertionSet need = results[i].need, have = results[i].have; + OpenVarSet openVars = results[i].openVars; + + if ( unify( formalType, cnst->get_type(), env, need, have, openVars, + indexer ) ) { + results.emplace_back( + i, cnstExpr, move(env), move(need), move(have), + move(openVars), nextArg, nTuples ); } } } + continue; } // Check each possible next argument - for ( const Alternative& actual : args[result.nextArg] ) { - ArgPack aResult = result; // copy to clone everything - // add details of actual to result - aResult.env.addActual( actual.env, aResult.openVars ); - - // explode argument - std::vector exploded; - Tuples::explode( actual, indexer, back_inserter( exploded ) ); - if ( exploded.empty() ) { - // skip empty tuple arguments - ++aResult.nextArg; - results.push_back( std::move(aResult) ); + 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; + AssertionSet need = results[i].need, have = results[i].have; + OpenVarSet openVars = results[i].openVars; + + env.addActual( expl.env, openVars ); + + // skip empty tuple arguments by (near-)cloning parent into next gen + if ( expl.alts.empty() ) { + results.emplace_back( + results[i], move(env), move(need), move(have), move(openVars), + nextArg + 1, expl.cost ); + continue; } // consider only first exploded actual - const Alternative& aActual = exploded.front(); - Type* actualType = aActual.expr->get_result()->clone(); + const Alternative& actual = expl.alts.front(); + Type* actualType = actual.expr->get_result()->clone(); PRINT( @@ -774,14 +878,9 @@ // attempt to unify types - if ( unify( formalType, actualType, aResult.env, aResult.need, aResult.have, aResult.openVars, indexer ) ) { - // add argument - aResult.withArg( aActual.expr, actual.cost ); - ++aResult.nextArg; - if ( exploded.size() > 1 ) { - // other parts of tuple left over - aResult.expls = std::move( exploded ); - aResult.nextExpl = 1; - } - nextResults.push_back( std::move(aResult) ); + if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { + // add new result + results.emplace_back( + i, actual.expr, move(env), move(need), move(have), move(openVars), + nextArg + 1, nTuples, expl.cost, expl.alts.size() == 1 ? 0 : 1, j ); } } @@ -789,14 +888,35 @@ // reset for next parameter - results.swap( nextResults ); - nextResults.clear(); - - return ! results.empty(); + genStart = genEnd; + + return genEnd != results.size(); + } + + template + void AlternativeFinder::validateFunctionAlternative( const Alternative &func, ArgPack& result, + const std::vector& results, OutputIterator out ) { + ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() ); + // sum cost and accumulate actuals + std::list& args = appExpr->get_args(); + Cost cost = Cost::zero; + const ArgPack* pack = &result; + while ( pack->expr ) { + args.push_front( pack->expr->clone() ); + cost += pack->cost; + pack = &results[pack->parent]; + } + // build and validate new alternative + Alternative newAlt( appExpr, result.env, cost ); + PRINT( + std::cerr << "instantiate function success: " << appExpr << std::endl; + std::cerr << "need assertions:" << std::endl; + printAssertionSet( result.need, std::cerr, 8 ); + ) + inferParameters( result.need, result.have, newAlt, result.openVars, out ); } 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; @@ -818,80 +938,92 @@ // iteratively build matches, one parameter at a time - std::vector results{ ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } }; - std::vector nextResults{}; + std::vector results; + results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } ); + std::size_t genStart = 0; + for ( DeclarationWithType* formal : funcType->get_parameters() ) { ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal ); - if ( ! instantiateArgument( - obj->get_type(), obj->get_init(), args, results, nextResults, indexer ) ) + if ( ! instantiateArgument( + obj->get_type(), obj->get_init(), args, results, genStart, indexer ) ) return; } - // filter out results that don't use all the arguments, and aren't variadic - std::vector finalResults{}; if ( funcType->get_isVarArgs() ) { - for ( ArgPack& result : results ) { - // use rest of exploded tuple if present - while ( result.nextExpl < result.expls.size() ) { - const Alternative& actual = result.expls[result.nextExpl]; - result.env.addActual( actual.env, result.openVars ); - result.withArg( actual.expr ); - ++result.nextExpl; - } - } - - while ( ! results.empty() ) { - // build combinations for all remaining arguments - for ( ArgPack& result : results ) { - // keep if used all arguments - if ( result.nextArg >= args.size() ) { - finalResults.push_back( std::move(result) ); + // append any unused arguments to vararg pack + std::size_t genEnd; + do { + genEnd = results.size(); + + // 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].hasExpl() ) { + const ExplodedActual& expl = results[i].getExpl( args ); + const Alternative& actual = expl.alts[results[i].nextExpl]; + + TypeEnvironment env = results[i].env; + OpenVarSet openVars = results[i].openVars; + + env.addActual( actual.env, openVars ); + + unsigned nextExpl = results[i].nextExpl + 1; + if ( nextExpl == expl.alts.size() ) { + nextExpl = 0; + } + + results.emplace_back( + i, actual.expr, move(env), copy(results[i].need), + copy(results[i].have), move(openVars), nextArg, 0, + Cost::zero, nextExpl, results[i].explAlt ); + continue; } + // finish result when out of arguments + if ( nextArg >= args.size() ) { + validateFunctionAlternative( func, results[i], results, out ); + + continue; + } + // add each possible next argument - for ( const Alternative& actual : args[result.nextArg] ) { - ArgPack aResult = result; // copy to clone everything - // add details of actual to result - aResult.env.addActual( actual.env, aResult.openVars ); - Cost cost = actual.cost; - - // explode argument - std::vector exploded; - Tuples::explode( actual, indexer, back_inserter( exploded ) ); - - // add exploded argument to arg list - for ( Alternative& aActual : exploded ) { - aResult.withArg( aActual.expr, cost ); - cost = Cost::zero; + 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( expl.env, openVars ); + + // skip empty tuple arguments by (near-)cloning parent into next gen + if ( expl.alts.empty() ) { + results.emplace_back( + results[i], move(env), copy(results[i].need), + copy(results[i].have), move(openVars), nextArg + 1, expl.cost ); + + continue; } - ++aResult.nextArg; - nextResults.push_back( std::move(aResult) ); + + // add new result + results.emplace_back( + i, expl.alts.front().expr, move(env), copy(results[i].need), + copy(results[i].have), move(openVars), nextArg + 1, 0, + expl.cost, expl.alts.size() == 1 ? 0 : 1, j ); } } - // reset for next round - results.swap( nextResults ); - nextResults.clear(); - } + genStart = genEnd; + } while ( genEnd != results.size() ); } else { // filter out results that don't use all the arguments - for ( ArgPack& result : results ) { - if ( result.nextExpl >= result.expls.size() && result.nextArg >= args.size() ) { - finalResults.push_back( std::move(result) ); + for ( std::size_t i = genStart; i < results.size(); ++i ) { + ArgPack& result = results[i]; + if ( ! result.hasExpl() && result.nextArg >= args.size() ) { + validateFunctionAlternative( func, result, results, out ); } } - } - - // validate matching combos, add to final result list - for ( ArgPack& result : finalResults ) { - ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() ); - Alternative newAlt( appExpr, result.env, sumCost( result.actuals ) ); - makeExprList( result.actuals, appExpr->get_args() ); - PRINT( - std::cerr << "instantiate function success: " << appExpr << std::endl; - std::cerr << "need assertions:" << std::endl; - printAssertionSet( result.need, std::cerr, 8 ); - ) - inferParameters( result.need, result.have, newAlt, result.openVars, out ); } } @@ -920,4 +1052,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; @@ -934,5 +1080,5 @@ Alternative newFunc( *func ); referenceToRvalueConversion( newFunc.expr ); - makeFunctionAlternatives( newFunc, function, argAlternatives, + makeFunctionAlternatives( newFunc, function, argExpansions, std::back_inserter( candidates ) ); } @@ -943,5 +1089,5 @@ Alternative newFunc( *func ); referenceToRvalueConversion( newFunc.expr ); - makeFunctionAlternatives( newFunc, function, argAlternatives, + makeFunctionAlternatives( newFunc, function, argExpansions, std::back_inserter( candidates ) ); } // if @@ -955,6 +1101,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(), std::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(); @@ -968,5 +1119,5 @@ Alternative newFunc( *funcOp ); referenceToRvalueConversion( newFunc.expr ); - makeFunctionAlternatives( newFunc, function, argAlternatives, + makeFunctionAlternatives( newFunc, function, argExpansions, std::back_inserter( candidates ) ); } @@ -982,9 +1133,9 @@ // compute conversionsion costs - for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) { - Cost cvtCost = computeApplicationConversionCost( *withFunc, indexer ); + for ( Alternative& withFunc : candidates ) { + Cost cvtCost = computeApplicationConversionCost( withFunc, indexer ); PRINT( - ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc->expr ); + ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr ); PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() ); FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() ); @@ -995,15 +1146,14 @@ printAll( appExpr->get_args(), std::cerr, 8 ); std::cerr << "bindings are:" << std::endl; - withFunc->env.print( std::cerr, 8 ); + withFunc.env.print( std::cerr, 8 ); std::cerr << "cost of conversion is:" << cvtCost << std::endl; ) if ( cvtCost != Cost::infinity ) { - withFunc->cvtCost = cvtCost; - alternatives.push_back( *withFunc ); + withFunc.cvtCost = cvtCost; + alternatives.push_back( withFunc ); } // if } // for - candidates.clear(); - candidates.splice( candidates.end(), alternatives ); + candidates = move(alternatives); // use a new list so that alternatives are not examined by addAnonConversions twice. @@ -1011,11 +1161,11 @@ findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) ); - // function may return struct or union value, in which case we need to add alternatives for implicit - // conversions to each of the anonymous members, must happen after findMinCost since anon conversions - // are never the cheapest expression + // function may return struct or union value, in which case we need to add alternatives + // for implicitconversions to each of the anonymous members, must happen after findMinCost + // since anon conversions are never the cheapest expression for ( const Alternative & alt : winners ) { addAnonConversions( alt ); } - alternatives.splice( alternatives.begin(), winners ); + spliceBegin( alternatives, winners ); if ( alternatives.empty() && targetType && ! targetType->isVoid() ) { @@ -1041,7 +1191,8 @@ AlternativeFinder finder( indexer, env ); finder.find( addressExpr->get_arg() ); - for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) { - if ( isLvalue( i->expr ) ) { - alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) ); + for ( Alternative& alt : finder.alternatives ) { + if ( isLvalue( alt.expr ) ) { + alternatives.push_back( + Alternative{ new AddressExpr( alt.expr->clone() ), alt.env, alt.cost } ); } // if } // for @@ -1049,5 +1200,5 @@ void AlternativeFinder::visit( LabelAddressExpr * expr ) { - alternatives.push_back( Alternative( expr->clone(), env, Cost::zero) ); + alternatives.push_back( Alternative{ expr->clone(), env, Cost::zero } ); } @@ -1091,5 +1242,5 @@ AltList candidates; - for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) { + for ( Alternative& alt : finder.alternatives ) { AssertionSet needAssertions, haveAssertions; OpenVarSet openVars; @@ -1099,16 +1250,20 @@ // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast // to. - int discardedValues = i->expr->get_result()->size() - castExpr->get_result()->size(); + int discardedValues = alt.expr->get_result()->size() - castExpr->get_result()->size(); if ( discardedValues < 0 ) continue; // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3])) // unification run for side-effects - unify( castExpr->get_result(), i->expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer ); - Cost thisCost = castCost( i->expr->get_result(), castExpr->get_result(), indexer, i->env ); + unify( castExpr->get_result(), alt.expr->get_result(), alt.env, needAssertions, + haveAssertions, openVars, indexer ); + Cost thisCost = castCost( alt.expr->get_result(), castExpr->get_result(), indexer, + alt.env ); if ( thisCost != Cost::infinity ) { // count one safe conversion for each value that is thrown away thisCost.incSafe( discardedValues ); - Alternative newAlt( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost ); - inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) ); + Alternative newAlt( restructureCast( alt.expr->clone(), toType ), alt.env, + alt.cost, thisCost ); + inferParameters( needAssertions, haveAssertions, newAlt, openVars, + back_inserter( candidates ) ); } // if } // for @@ -1397,15 +1552,18 @@ void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) { - std::list< AlternativeFinder > subExprAlternatives; - findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) ); - std::list< AltList > possibilities; - combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) ); - for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) { + std::vector< AlternativeFinder > subExprAlternatives; + findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), + back_inserter( subExprAlternatives ) ); + std::vector< AltList > possibilities; + combos( subExprAlternatives.begin(), subExprAlternatives.end(), + back_inserter( possibilities ) ); + for ( const AltList& alts : possibilities ) { std::list< Expression * > exprs; - makeExprList( *i, exprs ); + makeExprList( alts, exprs ); TypeEnvironment compositeEnv; - simpleCombineEnvironments( i->begin(), i->end(), compositeEnv ); - alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) ); + simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv ); + alternatives.push_back( + Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } ); } // for } Index: src/ResolvExpr/AlternativeFinder.h =================================================================== --- src/ResolvExpr/AlternativeFinder.h (revision 9f10d1f275f029a757920961a67b1ee9f4c4c248) +++ src/ResolvExpr/AlternativeFinder.h (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) @@ -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 @@ -31,4 +32,10 @@ namespace ResolvExpr { + class 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 { public: @@ -126,6 +133,11 @@ /// Adds alternatives for offsetof expressions, given the base type and name of the member template< typename StructOrUnionType > void addOffsetof( StructOrUnionType *aggInst, const std::string &name ); + /// Takes a final result and checks if its assertions can be satisfied template - void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const std::vector< AlternativeFinder >& args, OutputIterator out ); + void validateFunctionAlternative( const Alternative &func, ArgPack& result, const std::vector& results, OutputIterator out ); + /// Finds matching alternatives for a function, given a set of arguments + template + void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs& args, OutputIterator out ); + /// Checks if assertion parameters match for a new alternative template< typename OutputIterator > void inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ); Index: src/ResolvExpr/ExplodedActual.cc =================================================================== --- src/ResolvExpr/ExplodedActual.cc (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) +++ src/ResolvExpr/ExplodedActual.cc (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) @@ -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), alts() { + Tuples::explode( actual, indexer, back_inserter( alts ) ); + } +} Index: src/ResolvExpr/ExplodedActual.h =================================================================== --- src/ResolvExpr/ExplodedActual.h (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) +++ src/ResolvExpr/ExplodedActual.h (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) @@ -0,0 +1,34 @@ +// +// 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 "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; + AltList alts; // TODO flatten this down to vector> + + ExplodedActual() : env(), cost(Cost::zero), alts() {} + + ExplodedActual( const Alternative& actual, const SymTab::Indexer& indexer ); + }; +} Index: src/ResolvExpr/Resolver.cc =================================================================== --- src/ResolvExpr/Resolver.cc (revision 9f10d1f275f029a757920961a67b1ee9f4c4c248) +++ src/ResolvExpr/Resolver.cc (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) @@ -18,4 +18,5 @@ #include // for allocator, allocator_traits<... #include // for get +#include #include "Alternative.h" // for Alternative, AltList @@ -411,9 +412,9 @@ // Find all alternatives for all arguments in canonical form - std::list< AlternativeFinder > argAlternatives; + std::vector< AlternativeFinder > argAlternatives; funcFinder.findSubExprs( clause.target.arguments.begin(), clause.target.arguments.end(), back_inserter( argAlternatives ) ); // List all combinations of arguments - std::list< AltList > possibilities; + std::vector< AltList > possibilities; combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) ); Index: src/ResolvExpr/module.mk =================================================================== --- src/ResolvExpr/module.mk (revision 9f10d1f275f029a757920961a67b1ee9f4c4c248) +++ src/ResolvExpr/module.mk (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) @@ -32,3 +32,4 @@ ResolvExpr/Occurs.cc \ ResolvExpr/TypeEnvironment.cc \ - ResolvExpr/CurrentObject.cc + ResolvExpr/CurrentObject.cc \ + ResolvExpr/ExplodedActual.cc Index: src/ResolvExpr/typeops.h =================================================================== --- src/ResolvExpr/typeops.h (revision 9f10d1f275f029a757920961a67b1ee9f4c4c248) +++ src/ResolvExpr/typeops.h (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) @@ -16,4 +16,6 @@ #pragma once +#include + #include "SynTree/SynTree.h" #include "SynTree/Type.h" @@ -28,5 +30,5 @@ void combos( InputIterator begin, InputIterator end, OutputIterator out ) { typedef typename InputIterator::value_type SetType; - typedef typename std::list< typename SetType::value_type > ListType; + typedef typename std::vector< typename SetType::value_type > ListType; if ( begin == end ) { @@ -38,16 +40,14 @@ begin++; - std::list< ListType > recursiveResult; + std::vector< ListType > recursiveResult; combos( begin, end, back_inserter( recursiveResult ) ); - for ( typename std::list< ListType >::const_iterator i = recursiveResult.begin(); i != recursiveResult.end(); ++i ) { - for ( typename ListType::const_iterator j = current->begin(); j != current->end(); ++j ) { - ListType result; - std::back_insert_iterator< ListType > inserter = back_inserter( result ); - *inserter++ = *j; - std::copy( i->begin(), i->end(), inserter ); - *out++ = result; - } // for - } // for + for ( const auto& i : recursiveResult ) for ( const auto& j : *current ) { + ListType result; + std::back_insert_iterator< ListType > inserter = back_inserter( result ); + *inserter++ = j; + std::copy( i.begin(), i.end(), inserter ); + *out++ = result; + } } Index: src/SymTab/Validate.cc =================================================================== --- src/SymTab/Validate.cc (revision 9f10d1f275f029a757920961a67b1ee9f4c4c248) +++ src/SymTab/Validate.cc (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) @@ -423,4 +423,12 @@ } + void checkGenericParameters( ReferenceToType * inst ) { + for ( Expression * param : inst->parameters ) { + if ( ! dynamic_cast< TypeExpr * >( param ) ) { + throw SemanticError( "Expression parameters for generic types are currently unsupported: ", inst ); + } + } + } + void LinkReferenceToTypes::postvisit( StructInstType *structInst ) { StructDecl *st = local_indexer->lookupStruct( structInst->get_name() ); @@ -434,4 +442,5 @@ forwardStructs[ structInst->get_name() ].push_back( structInst ); } // if + checkGenericParameters( structInst ); } @@ -446,4 +455,5 @@ forwardUnions[ unionInst->get_name() ].push_back( unionInst ); } // if + checkGenericParameters( unionInst ); } @@ -525,5 +535,8 @@ // need to carry over the 'sized' status of each decl in the instance for ( auto p : group_iterate( traitDecl->get_parameters(), traitInst->get_parameters() ) ) { - TypeExpr * expr = strict_dynamic_cast< TypeExpr * >( std::get<1>(p) ); + TypeExpr * expr = dynamic_cast< TypeExpr * >( std::get<1>(p) ); + if ( ! expr ) { + throw SemanticError( "Expression parameters for trait instances are currently unsupported: ", std::get<1>(p) ); + } if ( TypeInstType * inst = dynamic_cast< TypeInstType * >( expr->get_type() ) ) { TypeDecl * formalDecl = std::get<0>(p); Index: src/Tuples/TupleAssignment.cc =================================================================== --- src/Tuples/TupleAssignment.cc (revision 9f10d1f275f029a757920961a67b1ee9f4c4c248) +++ src/Tuples/TupleAssignment.cc (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) @@ -251,5 +251,6 @@ // combine assignment environments into combined expression environment simpleCombineEnvironments( current.begin(), current.end(), matcher->compositeEnv ); - currentFinder.get_alternatives().push_front( ResolvExpr::Alternative( + // xxx -- was push_front + currentFinder.get_alternatives().push_back( ResolvExpr::Alternative( new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv, ResolvExpr::sumCost( current ) + matcher->baseCost ) ); Index: src/tests/.expect/castError.txt =================================================================== --- src/tests/.expect/castError.txt (revision 9f10d1f275f029a757920961a67b1ee9f4c4c248) +++ src/tests/.expect/castError.txt (revision 88ef2afbd83d6c5f558364a7e6c4c8f93104432a) @@ -5,5 +5,8 @@ charAlternatives are: Cost ( 1, 0, 0, 0 ): Cast of: - Variable Expression: f: signed int + Variable Expression: f: function + accepting unspecified arguments + ... returning nothing + ... to: char @@ -23,8 +26,5 @@ Cost ( 1, 0, 0, 0 ): Cast of: - Variable Expression: f: function - accepting unspecified arguments - ... returning nothing - + Variable Expression: f: signed int ... to: char