Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) +++ src/ResolvExpr/AlternativeFinder.cc (revision 97397a26b44bae1c0120193fd3d160297ec1db7a) @@ -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/ConversionCost.cc =================================================================== --- src/ResolvExpr/ConversionCost.cc (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) +++ src/ResolvExpr/ConversionCost.cc (revision 97397a26b44bae1c0120193fd3d160297ec1db7a) @@ -29,10 +29,12 @@ namespace ResolvExpr { - const Cost Cost::zero = Cost( 0, 0, 0, 0 ); - const Cost Cost::infinity = Cost( -1, -1, -1, -1 ); - const Cost Cost::unsafe = Cost( 1, 0, 0, 0 ); - const Cost Cost::poly = Cost( 0, 1, 0, 0 ); - const Cost Cost::safe = Cost( 0, 0, 1, 0 ); - const Cost Cost::reference = Cost( 0, 0, 0, 1 ); + const Cost Cost::zero = Cost{ 0, 0, 0, 0, 0, 0 }; + const Cost Cost::infinity = Cost{ -1, -1, -1, 1, -1, -1 }; + const Cost Cost::unsafe = Cost{ 1, 0, 0, 0, 0, 0 }; + const Cost Cost::poly = Cost{ 0, 1, 0, 0, 0, 0 }; + const Cost Cost::var = Cost{ 0, 0, 1, 0, 0, 0 }; + const Cost Cost::spec = Cost{ 0, 0, 0, -1, 0, 0 }; + const Cost Cost::safe = Cost{ 0, 0, 0, 0, 1, 0 }; + const Cost Cost::reference = Cost{ 0, 0, 0, 0, 0, 1 }; #if 0 Index: src/ResolvExpr/Cost.h =================================================================== --- src/ResolvExpr/Cost.h (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) +++ src/ResolvExpr/Cost.h (revision 97397a26b44bae1c0120193fd3d160297ec1db7a) @@ -9,7 +9,7 @@ // Author : Richard C. Bilson // Created On : Sun May 17 09:39:50 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sat Jul 22 09:35:55 2017 -// Update Count : 5 +// Last Modified By : Aaron B. Moss +// Last Modified On : Mon Jun 11 16:04:00 2018 +// Update Count : 6 // @@ -21,9 +21,11 @@ class Cost { private: - Cost( int unsafeCost, int polyCost, int safeCost, int referenceCost ); + Cost( int unsafeCost, int polyCost, int varCost, int specCost, int safeCost, int referenceCost ); public: Cost & incUnsafe( int inc = 1 ); Cost & incPoly( int inc = 1 ); + Cost & incVar( int inc = 1 ); + Cost & decSpec( int dec = 1 ); Cost & incSafe( int inc = 1 ); Cost & incReference( int inc = 1 ); @@ -31,4 +33,6 @@ int get_unsafeCost() const { return unsafeCost; } int get_polyCost() const { return polyCost; } + int get_varCost() const { return varCost; } + int get_specCost() const { return specCost; } int get_safeCost() const { return safeCost; } int get_referenceCost() const { return referenceCost; } @@ -47,16 +51,21 @@ static const Cost unsafe; static const Cost poly; + static const Cost var; + static const Cost spec; static const Cost safe; static const Cost reference; private: - int compare( const Cost &other ) const; - int unsafeCost; - int polyCost; - int safeCost; - int referenceCost; + int unsafeCost; ///< Unsafe (narrowing) conversions + int polyCost; ///< Count of parameters and return values bound to some poly type + int varCost; ///< Count of polymorphic type variables + int specCost; ///< Polymorphic type specializations (type assertions), negative cost + int safeCost; ///< Safe (widening) conversions + int referenceCost; ///< reference conversions }; - inline Cost::Cost( int unsafeCost, int polyCost, int safeCost, int referenceCost ) : unsafeCost( unsafeCost ), polyCost( polyCost ), safeCost( safeCost ), referenceCost( referenceCost ) {} + inline Cost::Cost( + int unsafeCost, int polyCost, int varCost, int specCost, int safeCost, int referenceCost ) : unsafeCost( unsafeCost ), polyCost( polyCost ), varCost( varCost ), specCost( specCost ), + safeCost( safeCost ), referenceCost( referenceCost ) {} inline Cost & Cost::incUnsafe( int inc ) { @@ -69,4 +78,16 @@ if ( *this == infinity ) return *this; polyCost += inc; + return *this; + } + + inline Cost & Cost::incVar( int inc ) { + if ( *this == infinity ) return *this; + varCost += inc; + return *this; + } + + inline Cost& Cost::decSpec( int dec ) { + if ( *this == infinity ) return *this; + specCost -= dec; return *this; } @@ -86,10 +107,16 @@ inline Cost Cost::operator+( const Cost &other ) const { if ( *this == infinity || other == infinity ) return infinity; - return Cost( unsafeCost + other.unsafeCost, polyCost + other.polyCost, safeCost + other.safeCost, referenceCost + other.referenceCost ); + return Cost( + unsafeCost + other.unsafeCost, polyCost + other.polyCost, + varCost + other.varCost, specCost + other.specCost, + safeCost + other.safeCost, referenceCost + other.referenceCost ); } inline Cost Cost::operator-( const Cost &other ) const { if ( *this == infinity || other == infinity ) return infinity; - return Cost( unsafeCost - other.unsafeCost, polyCost - other.polyCost, safeCost - other.safeCost, referenceCost - other.referenceCost ); + return Cost( + unsafeCost - other.unsafeCost, polyCost - other.polyCost, + varCost + other.varCost, specCost + other.specCost, + safeCost - other.safeCost, referenceCost - other.referenceCost ); } @@ -102,4 +129,6 @@ unsafeCost += other.unsafeCost; polyCost += other.polyCost; + varCost += other.varCost; + specCost += other.specCost; safeCost += other.safeCost; referenceCost += other.referenceCost; @@ -119,4 +148,12 @@ } else if ( polyCost < other.polyCost ) { return true; + } else if ( varCost > other.varCost ) { + return false; + } else if ( varCost < other.varCost ) { + return true; + } else if ( specCost > other.specCost ) { + return false; + } else if ( specCost < other.specCost ) { + return true; } else if ( safeCost > other.safeCost ) { return false; @@ -135,4 +172,6 @@ return unsafeCost == other.unsafeCost && polyCost == other.polyCost + && varCost == other.varCost + && specCost == other.specCost && safeCost == other.safeCost && referenceCost == other.referenceCost; @@ -144,6 +183,7 @@ inline std::ostream &operator<<( std::ostream &os, const Cost &cost ) { - os << "( " << cost.unsafeCost << ", " << cost.polyCost << ", " << cost.safeCost << ", " << cost.referenceCost << " )"; - return os; + return os << "( " << cost.unsafeCost << ", " << cost.polyCost << ", " + << cost.varCost << ", " << cost.specCost << ", " + << cost.safeCost << ", " << cost.referenceCost << " )"; } } // namespace ResolvExpr Index: src/ResolvExpr/Resolver.cc =================================================================== --- src/ResolvExpr/Resolver.cc (revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9) +++ src/ResolvExpr/Resolver.cc (revision 97397a26b44bae1c0120193fd3d160297ec1db7a) @@ -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 ); }