Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision 6d53e7792be19347d037650ff7afc2ca3778c35e) +++ src/ResolvExpr/AlternativeFinder.cc (revision b60f9d92fada1c082566f537486f627897855b9c) @@ -9,7 +9,7 @@ // Author : Richard C. Bilson // Created On : Sat May 16 23:52:08 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sat Feb 17 11:19:39 2018 -// Update Count : 33 +// Last Modified By : Aaron B. Moss +// Last Modified On : Mon Jun 11 16:40:00 2018 +// Update Count : 34 // @@ -19,7 +19,9 @@ #include // for operator<<, cerr, ostream, endl #include // for back_insert_iterator, back_inserter +#include // for numeric_limits::max() #include // for _List_iterator, list, _List_const_... #include // for _Rb_tree_iterator, map, _Rb_tree_c... #include // for allocator_traits<>::value_type +#include // for tuple #include // for pair #include // for vector @@ -444,7 +446,9 @@ } + #if 0 // cost of assertions accounted for in function creation for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) { convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env ); } + #endif return convCost; @@ -572,4 +576,121 @@ } + namespace { + /// Information required to defer resolution of an expression + struct AssertionPack { + SymTab::Indexer::IdData cdata; ///< Satisfying declaration + Type* adjType; ///< Satisfying type + TypeEnvironment env; ///< Post-unification environment + AssertionSet have; ///< Post-unification have-set + AssertionSet need; ///< Post-unification need-set + OpenVarSet openVars; ///< Post-unification open-var set + + AssertionPack( const SymTab::Indexer::IdData& cdata, Type* adjType, + TypeEnvironment&& env, AssertionSet&& have, AssertionSet&& need, + OpenVarSet&& openVars ) + : cdata(cdata), adjType(adjType), env(std::move(env)), have(std::move(have)), + need(std::move(need)), openVars(std::move(openVars)) {} + }; + + /// List of deferred assertion resolutions for the same type + using DeferList = std::vector; + + /// Intermediate state for assertion resolution + struct AssertionResnState { + using DeferItem = std::tuple; + + const Alternative& alt; ///< Alternative being built from + AssertionSet newNeed; ///< New assertions found from current assertions + OpenVarSet openVars; ///< Open variables in current context + std::vector deferred; ///< Possible deferred assertion resolutions + const SymTab::Indexer& indexer; ///< Name lookup + + AssertionResnState(const Alternative& alt, const OpenVarSet& openVars, + const SymTab::Indexer& indexer ) + : alt{alt}, have{}, newNeed{}, openVars{openVars}, indexer{indexer} {} + }; + + /// Binds a single assertion from a compatible AssertionPack, updating resolution state + /// as appropriate. + void bindAssertion( DeclarationWithType* curDecl, AssertionSetValue& assnInfo, + AssertionResnState& resn, AssertionPack&& match ) { + DeclarationWithType* candidate = match.cdata.id; + + addToIndexer( match.have, resn.indexer ); + resn.newNeed.insert( match.need.begin(), match.need.end() ); + resn.openVars = std::move(match.openVars); + resn.alt.env = std::move(match.env); + + assertf( candidate->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() ); + for ( auto& a : match.need ) { + if ( a.second.idChain.empty() ) { + a.second.idChain = assnInfo.idChain; + a.second.idChain.push_back( curDecl->get_uniqueId() ); + } + } + + Expression* varExpr = match.cdata.combine( resn.alt.cvtCost ); + varExpr->result = match.adjType; + + // follow the current assertion's ID chain to find the correct set of inferred + // parameters to add the candidate o (i.e. the set of inferred parameters belonging + // to the entity which requested the assertion parameter) + InferredParams* inferParams = &resn.alt.expr->inferParams; + for ( UniqueId id : assnInfo.idChain ) { + inferParams = (*inferParams)[ id ].inferParams.get(); + } + + (*inferParams)[ curDecl->get_uniqueId() ] = ParamEntry{ + candidate->get_uniqueId(), match.adjType, curDecl->get_type(), varExpr }; + } + + /// Resolves a single assertion, returning false if no satisfying assertion, binding it + /// if there is exactly one satisfying assertion, or adding to the defer-list if there + /// is more than one + bool resolveAssertion( DeclarationWithType* curDecl, AssertionSetValue& assnInfo, + AssertionResnState& resn ) { + // skip unused assertions + if ( ! assnInfo.isUsed ) return true; + + // lookup candidates for this assertion + std::list< SymTab::Indexer::IdData > candidates; + decls.lookupId( curDecl->name, candidates ); + + // find the ones that unify with the desired type + DeferList matches; + for ( const auto& cdata : candidates ) { + DeclarationWithType* candidate = cdata.id; + + // build independent unification context for candidate + AssertionSet have, newNeed; + TypeEnvironment newEnv{ resn.alt.env }; + OpenVarSet newOpenVars{ resn.openVars }; + Type* adjType = candidate->get_type()->clone(); + adjustExprType( adjType, newEnv, resn.indexer ); + renameTyVars( adjType ); + + if ( unify( curDecl->get_type(), adjType, newEnv, + newNeed, have, newOpenVars, resn.indexer ) ) { + matches.emplace_back( cdata, adjType, std::move(newEnv), std::move(have), + std::move(newNeed), std::move(newOpenVars) ); + } + } + + // Break if no suitable assertion + if ( matches.empty() ) return false; + + // Defer if too many suitable assertions + if ( matches.size() > 1 ) { + resn.deferred.emplace_back( curDecl, assnInfo, std::move(matches) ); + return true; + } + + // otherwise bind current match in ongoing scope + bindAssertion( curDecl, assnInfo, resn, std::move(matches.front()) ); + + return true; + } + } + template< typename OutputIterator > void AlternativeFinder::Finder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) { @@ -586,4 +707,42 @@ // ) addToIndexer( have, decls ); + + AssertionResnState resn{ newAlt, openVars, indexer }; + + // resolve assertions in breadth-first-order up to a limited number of levels deep + int level; + for ( level = 0; level < recursionLimit; ++level ) { + // make initial pass at matching assertions + for ( auto& assn : need ) { + if ( ! resolveAssertion( assn.first, assn.second, resn ) ) { + // fail early if any assertion fails to resolve + return; + } + } + + // resolve deferred assertions by mutual compatibility and min-cost + if ( ! resn.deferred.empty() ) { + // TODO + assert(false && "TODO: deferred assertions unimplemented"); + + // reset for next round + resn.deferred.clear(); + } + + // quit resolving assertions if done + if ( resn.newNeed.empty() ) break; + + // otherwise start on next group of recursive assertions + need.swap( resn.newNeed ); + resn.newNeed.clear(); + } + if ( level >= recursionLimit ) { + SemanticError( newAlt.expr->location, "Too many recursive assertions" ); + } + + // add completed assertion to output + *out++ = newAlt; + +#if 0 AssertionSet newNeed; PRINT( @@ -599,4 +758,5 @@ // *out++ = newAlt; // ) +#endif } @@ -630,6 +790,6 @@ ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have, - const OpenVarSet& openVars) - : parent(0), expr(nullptr), cost(Cost::zero), env(env), need(need), have(have), + const OpenVarSet& openVars, Cost initCost = Cost::zero) + : parent(0), expr(nullptr), cost(initCost), env(env), need(need), have(have), openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {} @@ -923,4 +1083,142 @@ } + namespace { + + struct CountSpecs : public WithVisitorRef, WithShortCircuiting { + + void postvisit(PointerType*) { + // mark specialization of base type + if ( count >= 0 ) ++count; + } + + void postvisit(ArrayType*) { + // mark specialization of base type + if ( count >= 0 ) ++count; + } + + void postvisit(ReferenceType*) { + // mark specialization of base type -- xxx maybe not? + if ( count >= 0 ) ++count; + } + + private: + // takes minimum non-negative count over parameter/return list + void takeminover( int& mincount, std::list& dwts ) { + for ( DeclarationWithType* dwt : dwts ) { + count = -1; + maybeAccept( dwt->get_type(), *visitor ); + if ( count != -1 && count < mincount ) mincount = count; + } + } + + public: + void previsit(FunctionType*) { + // override default child visiting behaviour + visit_children = false; + } + + void postvisit(FunctionType* fty) { + // take minimal set value of count over ->returnVals and ->parameters + int mincount = std::numeric_limits::max(); + takeminover( mincount, fty->parameters ); + takeminover( mincount, fty->returnVals ); + // add another level to mincount if set + count = mincount < std::numeric_limits::max() ? mincount + 1 : -1; + } + + private: + // returns minimum non-negative count + 1 over type parameters (-1 if none such) + int minover( std::list& parms ) { + int mincount = std::numeric_limits::max(); + for ( Expression* parm : parms ) { + count = -1; + maybeAccept( parm->get_result(), *visitor ); + if ( count != -1 && count < mincount ) mincount = count; + } + return mincount < std::numeric_limits::max() ? mincount + 1 : -1; + } + + public: + void previsit(StructInstType*) { + // override default child behaviour + visit_children = false; + } + + void postvisit(StructInstType* sity) { + // look for polymorphic parameters + count = minover( sity->parameters ); + } + + void previsit(UnionInstType*) { + // override default child behaviour + visit_children = false; + } + + void postvisit(UnionInstType* uity) { + // look for polymorphic parameters + count = minover( uity->parameters ); + } + + void postvisit(TypeInstType*) { + // note polymorphic type (which may be specialized) + // xxx - maybe account for open/closed type variables + count = 0; + } + + void previsit(TupleType*) { + // override default child behaviour + visit_children = false; + } + + void postvisit(TupleType* tty) { + // take minimum non-negative count + int mincount = std::numeric_limits::max(); + for ( Type* ty : tty->types ) { + count = -1; + maybeAccept( ty, *visitor ); + if ( count != -1 && count < mincount ) mincount = count; + } + // xxx - maybe don't increment, tuple flattening doesn't necessarily specialize + count = mincount < std::numeric_limits::max() ? mincount + 1: -1; + } + + int get_count() const { return count >= 0 ? count : 0; } + private: + int count = -1; + }; + + /// Counts the specializations in the types in a function parameter or return list + int countSpecs( std::list& dwts ) { + int k = 0; + for ( DeclarationWithType* dwt : dwts ) { + PassVisitor counter; + maybeAccept( dwt->get_type(), *counter.pass.visitor ); + k += counter.pass.get_count(); + } + return k; + } + + /// Calculates the inherent costs in a function declaration; varCost for the number of + /// type variables and specCost for type assertions, as well as PolyType specializations + /// in the parameter and return lists. + Cost declCost( FunctionType* funcType ) { + Cost k = Cost::zero; + + // add cost of type variables + k.incVar( funcType->forall.size() ); + + // subtract cost of type assertions + for ( TypeDecl* td : funcType->forall ) { + k.decSpec( td->assertions.size() ); + } + + // count specialized polymorphic types in parameter/return lists + k.decSpec( countSpecs( funcType->parameters ) ); + k.decSpec( countSpecs( funcType->returnVals ) ); + + return k; + } + } + template void AlternativeFinder::Finder::validateFunctionAlternative( const Alternative &func, @@ -967,7 +1265,10 @@ } + // calculate declaration cost of function (+vars-spec) + Cost funcCost = declCost( funcType ); + // iteratively build matches, one parameter at a time std::vector results; - results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } ); + results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars, funcCost } ); std::size_t genStart = 0; Index: src/ResolvExpr/Resolver.cc =================================================================== --- src/ResolvExpr/Resolver.cc (revision 6d53e7792be19347d037650ff7afc2ca3778c35e) +++ src/ResolvExpr/Resolver.cc (revision b60f9d92fada1c082566f537486f627897855b9c) @@ -51,4 +51,7 @@ namespace ResolvExpr { struct Resolver final : public WithIndexer, public WithGuards, public WithVisitorRef, public WithShortCircuiting, public WithStmtsToAdd { + + friend void resolve( std::list ); + Resolver() {} Resolver( const SymTab::Indexer & other ) { @@ -96,8 +99,10 @@ CurrentObject currentObject = nullptr; bool inEnumDecl = false; + bool atTopLevel = false; ///< Was this resolver set up at the top level of resolution }; void resolve( std::list< Declaration * > translationUnit ) { PassVisitor resolver; + resolver.pass.atTopLevel = true; // mark resolver as top-level acceptAll( translationUnit, resolver ); }