Index: src/Parser/DeclarationNode.cc =================================================================== --- src/Parser/DeclarationNode.cc (revision 7e4c4f47da4da2c1598a50ccf667c8b9f65d572b) +++ src/Parser/DeclarationNode.cc (revision 452747a874e502a4fcc82e43921e6dc1fac67e6e) @@ -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 7e4c4f47da4da2c1598a50ccf667c8b9f65d572b) +++ src/Parser/parser.yy (revision 452747a874e502a4fcc82e43921e6dc1fac67e6e) @@ -10,6 +10,6 @@ // Created On : Sat Sep 1 20:22:55 2001 // Last Modified By : Peter A. Buhr -// Last Modified On : Fri Nov 17 11:38:57 2017 -// Update Count : 2914 +// 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 ? @@ -2401,4 +2413,5 @@ | declaration_specifier function_declarator with_clause_opt compound_statement { + rebindForall( $1, $2 ); typedefTable.addToEnclosingScope( TypedefTable::ID ); typedefTable.leaveScope(); @@ -2427,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 7e4c4f47da4da2c1598a50ccf667c8b9f65d572b) +++ src/ResolvExpr/Alternative.cc (revision 452747a874e502a4fcc82e43921e6dc1fac67e6e) @@ -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 7e4c4f47da4da2c1598a50ccf667c8b9f65d572b) +++ src/ResolvExpr/Alternative.h (revision 452747a874e502a4fcc82e43921e6dc1fac67e6e) @@ -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 7e4c4f47da4da2c1598a50ccf667c8b9f65d572b) +++ src/ResolvExpr/AlternativeFinder.cc (revision 452747a874e502a4fcc82e43921e6dc1fac67e6e) @@ -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 @@ -50,4 +51,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 +194,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 +206,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,49 +578,62 @@ /// 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) + 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 + // TODO fix this somehow + std::vector expls; ///< Exploded actuals left over from last match + + ArgPack() + : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0), + tupleStart(0), expls() {} 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), expls() {} + + 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{} ) + : 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)) {} + + 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), 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; /// 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; } }; @@ -621,98 +641,162 @@ /// 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 ) { + const std::vector< AlternativeFinder >& 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(); - } - // 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) ); - } + 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() ); + 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) ); + continue; } + // finish result when out of arguments + if ( results[i].nextArg >= args.size() ) { + ArgPack newResult{ + results[i].env, results[i].need, results[i].have, + results[i].openVars }; + newResult.nextArg = results[i].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; + auto j = results[i].nextArg; + for ( const Alternative& actual : args[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 ) ); - - // add exploded argument to tuple - for ( Alternative& aActual : exploded ) { - aResult.withArg( aActual.expr, cost ); - cost = Cost::zero; + if ( exploded.empty() ) { + // skip empty tuple arguments by (near-)cloning parent into next gen + results.emplace_back( + results[i], move(env), copy(results[i].need), + copy(results[i].have), move(openVars), j + 1, actual.cost ); + + continue; } - ++aResult.nextArg; - nextResults.push_back( std::move(aResult) ); + + // 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) ); } } // 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 ) { + // use remainder of exploded tuple if present + if ( ! results[i].expls.empty() ) { + const Alternative& actual = results[i].expls.front(); + + 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(); @@ -725,29 +809,44 @@ ) - 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 ) ) { + std::vector newExpls( + std::next( results[i].expls.begin() ), results[i].expls.end() ); + results.emplace_back( + i, actual.expr, move(env), move(need), move(have), move(openVars), + results[i].nextArg, nTuples, Cost::zero, move(newExpls) );; } continue; - } else if ( result.nextArg >= args.size() ) { - // use default initializers if out of arguments + } + + // use default initializers if out of arguments + if ( results[i].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), results[i].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 ); + auto j = results[i].nextArg; + for ( const Alternative& actual : args[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( actual.env, openVars ); // explode argument @@ -755,7 +854,9 @@ Tuples::explode( actual, indexer, back_inserter( exploded ) ); if ( exploded.empty() ) { - // skip empty tuple arguments - ++aResult.nextArg; - results.push_back( std::move(aResult) ); + // skip empty tuple arguments by (near-)cloning parent into next gen + results.emplace_back( + results[i], move(env), move(need), move(have), move(openVars), j + 1, + actual.cost ); + continue; } @@ -774,14 +875,15 @@ // 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; + 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]) ); } - nextResults.push_back( std::move(aResult) ); + // add new result + results.emplace_back( + i, aActual.expr, move(env), move(need), move(have), move(openVars), + j + 1, nTuples, actual.cost, move(newExpls) ); } } @@ -789,8 +891,30 @@ // 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 ); } @@ -818,80 +942,93 @@ // 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 ) ) + 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 ) { + // 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() ); + 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) ); + continue; } + // finish result when out of arguments + if ( results[i].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; + auto j = results[i].nextArg; + for ( const Alternative& actual : args[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 ) ); - - // add exploded argument to arg list - for ( Alternative& aActual : exploded ) { - aResult.withArg( aActual.expr, cost ); - cost = Cost::zero; + if ( exploded.empty() ) { + // skip empty tuple arguments by (near-)cloning parent into next gen + results.emplace_back( + results[i], move(env), copy(results[i].need), + copy(results[i].have), move(openVars), j + 1, actual.cost ); + continue; } - ++aResult.nextArg; - nextResults.push_back( std::move(aResult) ); + + // 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) ); } } - // 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.expls.empty() && 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 ); } } @@ -956,5 +1093,5 @@ if ( ! funcOpFinder.alternatives.empty() ) { // add function alternatives to front of argument list - argAlternatives.insert( argAlternatives.begin(), std::move(funcFinder) ); + argAlternatives.insert( argAlternatives.begin(), move(funcFinder) ); for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin(); @@ -982,9 +1119,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 +1132,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 +1147,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 +1177,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 +1186,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 +1228,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,15 +1236,17 @@ // 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 ); PRINT( std::cerr << "working on cast with result: " << castExpr->result << std::endl; - std::cerr << "and expr type: " << i->expr->result << std::endl; - std::cerr << "env: " << i->env << std::endl; + std::cerr << "and expr type: " << alt.expr->result << std::endl; + std::cerr << "env: " << alt.env << std::endl; ) if ( thisCost != Cost::infinity ) { @@ -1117,6 +1256,8 @@ // 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 @@ -1405,15 +1546,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 7e4c4f47da4da2c1598a50ccf667c8b9f65d572b) +++ src/ResolvExpr/AlternativeFinder.h (revision 452747a874e502a4fcc82e43921e6dc1fac67e6e) @@ -31,4 +31,6 @@ namespace ResolvExpr { + struct ArgPack; + class AlternativeFinder : public Visitor { public: @@ -36,14 +38,14 @@ AlternativeFinder( const AlternativeFinder& o ) - : indexer(o.indexer), alternatives(o.alternatives), env(o.env), + : indexer(o.indexer), alternatives(o.alternatives), env(o.env), targetType(o.targetType) {} - + AlternativeFinder( AlternativeFinder&& o ) - : indexer(o.indexer), alternatives(std::move(o.alternatives)), env(o.env), + : indexer(o.indexer), alternatives(std::move(o.alternatives)), env(o.env), targetType(o.targetType) {} - + AlternativeFinder& operator= ( const AlternativeFinder& o ) { if (&o == this) return *this; - + // horrific nasty hack to rebind references... alternatives.~AltList(); @@ -54,5 +56,5 @@ AlternativeFinder& operator= ( AlternativeFinder&& o ) { if (&o == this) return *this; - + // horrific nasty hack to rebind references... alternatives.~AltList(); @@ -126,6 +128,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 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 std::vector< AlternativeFinder >& 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/Resolver.cc =================================================================== --- src/ResolvExpr/Resolver.cc (revision 7e4c4f47da4da2c1598a50ccf667c8b9f65d572b) +++ src/ResolvExpr/Resolver.cc (revision 452747a874e502a4fcc82e43921e6dc1fac67e6e) @@ -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/typeops.h =================================================================== --- src/ResolvExpr/typeops.h (revision 7e4c4f47da4da2c1598a50ccf667c8b9f65d572b) +++ src/ResolvExpr/typeops.h (revision 452747a874e502a4fcc82e43921e6dc1fac67e6e) @@ -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/Tuples/TupleAssignment.cc =================================================================== --- src/Tuples/TupleAssignment.cc (revision 7e4c4f47da4da2c1598a50ccf667c8b9f65d572b) +++ src/Tuples/TupleAssignment.cc (revision 452747a874e502a4fcc82e43921e6dc1fac67e6e) @@ -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 7e4c4f47da4da2c1598a50ccf667c8b9f65d572b) +++ src/tests/.expect/castError.txt (revision 452747a874e502a4fcc82e43921e6dc1fac67e6e) @@ -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