Index: src/ResolvExpr/ResolveAssertions.cc =================================================================== --- src/ResolvExpr/ResolveAssertions.cc (revision bd405fa5a47462483423c39d874053d41ec0a699) +++ src/ResolvExpr/ResolveAssertions.cc (revision 052cd7138ff5b8149b63ee8fba41fa31770761c4) @@ -35,5 +35,5 @@ #include "SynTree/Expression.h" // for InferredParams #include "TypeEnvironment.h" // for TypeEnvironment, etc. -#include "typeops.h" // for adjustExprType +#include "typeops.h" // for adjustExprType, specCost #include "Unify.h" // for unify @@ -58,26 +58,8 @@ using CandidateList = std::vector; - /// Unique identifier for a yet-to-be-resolved assertion - struct AssnId { - DeclarationWithType* decl; ///< Declaration of assertion - AssertionSetValue info; ///< Information about assertion - - AssnId(DeclarationWithType* decl, const AssertionSetValue& info) : decl(decl), info(info) {} - }; - - /// Cached assertion items - struct AssnCacheItem { - CandidateList matches; ///< Possible matches for this assertion - std::vector deferIds; ///< Deferred assertions which resolve to this item - - AssnCacheItem( CandidateList&& m ) : matches(std::move(m)), deferIds() {} - }; - - /// Cache of resolved assertions - using AssnCache = std::unordered_map; - /// Reference to single deferred item struct DeferRef { - const AssnCacheItem& item; + const DeclarationWithType* decl; + const AssertionSetValue& info; const AssnCandidate& match; }; @@ -86,25 +68,16 @@ /// Acts like indexed list of DeferRef struct DeferItem { - const AssnCache* cache; ///< Cache storing assertion item - std::string key; ///< Key into cache - - DeferItem( const AssnCache& cache, const std::string& key ) : cache(&cache), key(key) {} - - bool empty() const { return cache->at(key).matches.empty(); } - - CandidateList::size_type size() const { return cache->at(key).matches.size(); } - - DeferRef operator[] ( unsigned i ) const { - const AssnCacheItem& item = cache->at(key); - return { item, item.matches[i] }; - } - - const DeclarationWithType* get_decl() const { return cache->at(key).deferIds[0].decl; } - - // sortable by key - // TODO look into optimizing combination process with other sort orders (e.g. by number - // of matches in candidate) - bool operator< ( const DeferItem& o ) const { return key < o.key; } - bool operator== ( const DeferItem& o ) const { return key == o.key; } + const DeclarationWithType* decl; + const AssertionSetValue& info; + CandidateList matches; + + DeferItem( DeclarationWithType* decl, const AssertionSetValue& info, CandidateList&& matches ) + : decl(decl), info(info), matches(std::move(matches)) {} + + bool empty() const { return matches.empty(); } + + CandidateList::size_type size() const { return matches.size(); } + + DeferRef operator[] ( unsigned i ) const { return { decl, info, matches[i] }; } }; @@ -181,6 +154,5 @@ for ( const auto& assn : x.assns ) { k += computeConversionCost( - assn.match.adjType, assn.item.deferIds[0].decl->get_type(), indexer, - x.env ); + assn.match.adjType, assn.decl->get_type(), indexer, x.env ); } it = cache.emplace_hint( it, &x, k ); @@ -253,54 +225,43 @@ /// Resolve a single assertion, in context - bool resolveAssertion( AssertionItem& assn, ResnState& resn, AssnCache& cache ) { + bool resolveAssertion( AssertionItem& assn, ResnState& resn ) { // skip unused assertions if ( ! assn.info.isUsed ) return true; - // check cache for this assertion - std::string assnKey = SymTab::Mangler::mangleAssnKey( assn.decl, resn.alt.env ); - auto it = cache.find( assnKey ); - - // attempt to resolve assertion if this is the first time seen - if ( it == cache.end() ) { - // lookup candidates for this assertion - std::list< SymTab::Indexer::IdData > candidates; - resn.indexer.lookupId( assn.decl->name, candidates ); - - // find the candidates that unify with the desired type - CandidateList 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.alt.openVars }; - Type* adjType = candidate->get_type()->clone(); - adjustExprType( adjType, newEnv, resn.indexer ); - renameTyVars( adjType ); - - // keep unifying candidates - if ( unify( assn.decl->get_type(), adjType, newEnv, newNeed, have, newOpenVars, - resn.indexer ) ) { - // set up binding slot for recursive assertions - UniqueId crntResnSlot = 0; - if ( ! newNeed.empty() ) { - crntResnSlot = ++globalResnSlot; - for ( auto& a : newNeed ) { - a.second.resnSlot = crntResnSlot; - } + // lookup candidates for this assertion + std::list< SymTab::Indexer::IdData > candidates; + resn.indexer.lookupId( assn.decl->name, candidates ); + + // find the candidates that unify with the desired type + CandidateList 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.alt.openVars }; + Type* adjType = candidate->get_type()->clone(); + adjustExprType( adjType, newEnv, resn.indexer ); + renameTyVars( adjType ); + + // keep unifying candidates + if ( unify( assn.decl->get_type(), adjType, newEnv, newNeed, have, newOpenVars, + resn.indexer ) ) { + // set up binding slot for recursive assertions + UniqueId crntResnSlot = 0; + if ( ! newNeed.empty() ) { + crntResnSlot = ++globalResnSlot; + for ( auto& a : newNeed ) { + a.second.resnSlot = crntResnSlot; } - - matches.emplace_back( cdata, adjType, std::move(newEnv), std::move(have), - std::move(newNeed), std::move(newOpenVars), crntResnSlot ); - } else { - delete adjType; - } + } + + matches.emplace_back( cdata, adjType, std::move(newEnv), std::move(have), + std::move(newNeed), std::move(newOpenVars), crntResnSlot ); + } else { + delete adjType; } - - it = cache.emplace_hint( it, assnKey, AssnCacheItem{ std::move(matches) } ); - } - - CandidateList& matches = it->second.matches; + } // break if no suitable assertion @@ -309,6 +270,5 @@ // defer if too many suitable assertions if ( matches.size() > 1 ) { - it->second.deferIds.emplace_back( assn.decl, assn.info ); - resn.deferred.emplace_back( cache, assnKey ); + resn.deferred.emplace_back( assn.decl, assn.info, std::move(matches) ); return true; } @@ -318,6 +278,6 @@ addToIndexer( match.have, resn.indexer ); resn.newNeed.insert( match.need.begin(), match.need.end() ); - resn.alt.env = match.env; - resn.alt.openVars = match.openVars; + resn.alt.env = std::move(match.env); + resn.alt.openVars = std::move(match.openVars); bindAssertion( assn.decl, assn.info, resn.alt, match, resn.inferred ); @@ -380,5 +340,4 @@ ResnList resns{ ResnState{ alt, root_indexer } }; ResnList new_resns{}; - AssnCache assnCache; // resolve assertions in breadth-first-order up to a limited number of levels deep @@ -389,5 +348,5 @@ for ( auto& assn : resn.need ) { // fail early if any assertion is not resolvable - if ( ! resolveAssertion( assn, resn, assnCache ) ) { + if ( ! resolveAssertion( assn, resn ) ) { Indenter tabs{ Indenter::tabsize, 3 }; std::ostringstream ss; @@ -410,8 +369,4 @@ } } else { - // only resolve each deferred assertion once - std::sort( resn.deferred.begin(), resn.deferred.end() ); - auto last = std::unique( resn.deferred.begin(), resn.deferred.end() ); - resn.deferred.erase( last, resn.deferred.end() ); // resolve deferred assertions by mutual compatibility std::vector compatible = filterCombos( @@ -427,5 +382,5 @@ ++tabs; for ( const auto& d : resn.deferred ) { - d.get_decl()->print( ss, tabs ); + d.decl->print( ss, tabs ); } @@ -458,9 +413,5 @@ new_resn.newNeed.insert( match.need.begin(), match.need.end() ); - // for each deferred assertion with the same form - for ( AssnId id : r.item.deferIds ) { - bindAssertion( - id.decl, id.info, new_resn.alt, match, new_resn.inferred ); - } + bindAssertion( r.decl, r.info, new_resn.alt, match, new_resn.inferred ); } Index: src/SymTab/Mangler.cc =================================================================== --- src/SymTab/Mangler.cc (revision bd405fa5a47462483423c39d874053d41ec0a699) +++ src/SymTab/Mangler.cc (revision 052cd7138ff5b8149b63ee8fba41fa31770761c4) @@ -38,5 +38,4 @@ struct Mangler : public WithShortCircuiting, public WithVisitorRef, public WithGuards { Mangler( bool mangleOverridable, bool typeMode, bool mangleGenericParams ); - Mangler( const ResolvExpr::TypeEnvironment& env ); Mangler( const Mangler & ) = delete; @@ -67,8 +66,7 @@ private: std::ostringstream mangleName; ///< Mangled name being constructed - typedef std::map< std::string, std::pair< std::string, int > > VarMapType; + typedef std::map< std::string, std::pair< int, int > > VarMapType; VarMapType varNums; ///< Map of type variables to indices int nextVarNum; ///< Next type variable index - const ResolvExpr::TypeEnvironment* env; ///< optional environment for substitutions bool isTopLevel; ///< Is the Mangler at the top level bool mangleOverridable; ///< Specially mangle overridable built-in methods @@ -80,6 +78,5 @@ public: Mangler( bool mangleOverridable, bool typeMode, bool mangleGenericParams, - int nextVarNum, const ResolvExpr::TypeEnvironment* env, - const VarMapType& varNums ); + int nextVarNum, const VarMapType& varNums ); private: @@ -109,25 +106,13 @@ } - std::string mangleAssnKey( DeclarationWithType* decl, - const ResolvExpr::TypeEnvironment& env ) { - PassVisitor mangler( env ); - maybeAccept( decl, mangler ); - return mangler.pass.get_mangleName(); - } - namespace { Mangler::Mangler( bool mangleOverridable, bool typeMode, bool mangleGenericParams ) - : nextVarNum( 0 ), env(nullptr), isTopLevel( true ), + : nextVarNum( 0 ), isTopLevel( true ), mangleOverridable( mangleOverridable ), typeMode( typeMode ), mangleGenericParams( mangleGenericParams ) {} - Mangler::Mangler( const ResolvExpr::TypeEnvironment& env ) - : nextVarNum( 0 ), env( &env ), isTopLevel( true ), mangleOverridable( false ), - typeMode( false ), mangleGenericParams( true ) {} - Mangler::Mangler( bool mangleOverridable, bool typeMode, bool mangleGenericParams, - int nextVarNum, const ResolvExpr::TypeEnvironment* env, - const VarMapType& varNums ) - : varNums( varNums ), nextVarNum( nextVarNum ), env( env ), isTopLevel( false ), + int nextVarNum, const VarMapType& varNums ) + : varNums( varNums ), nextVarNum( nextVarNum ), isTopLevel( false ), mangleOverridable( mangleOverridable ), typeMode( typeMode ), mangleGenericParams( mangleGenericParams ) {} @@ -358,25 +343,8 @@ assert( false ); } // switch - std::string varName; - // replace type with substitution name if environment is available and bound - if ( env ) { - const ResolvExpr::EqvClass* varClass = env->lookup( (*i)->name ); - if ( varClass && varClass->type ) { - PassVisitor sub_mangler( - mangleOverridable, typeMode, mangleGenericParams, nextVarNum, - env, varNums ); - varClass->type->accept( sub_mangler ); - varName = std::string{"%"} + sub_mangler.pass.get_mangleName(); - } - } - // otherwise just give type numeric name - if ( varName.empty() ) { - varName = std::to_string( nextVarNum++ ); - } - varNums[ (*i)->name ] = std::make_pair( varName, (int)(*i)->get_kind() ); + varNums[ (*i)->name ] = std::make_pair( nextVarNum, (int)(*i)->get_kind() ); for ( std::list< DeclarationWithType* >::iterator assert = (*i)->assertions.begin(); assert != (*i)->assertions.end(); ++assert ) { PassVisitor sub_mangler( - mangleOverridable, typeMode, mangleGenericParams, nextVarNum, env, - varNums ); + mangleOverridable, typeMode, mangleGenericParams, nextVarNum, varNums ); (*assert)->accept( sub_mangler ); assertionNames.push_back( sub_mangler.pass.get_mangleName() ); Index: src/SymTab/Mangler.h =================================================================== --- src/SymTab/Mangler.h (revision bd405fa5a47462483423c39d874053d41ec0a699) +++ src/SymTab/Mangler.h (revision 052cd7138ff5b8149b63ee8fba41fa31770761c4) @@ -44,7 +44,4 @@ /// Mangle ignoring generic type parameters std::string mangleConcrete( Type* ty ); - /// Mangle for assertion key - std::string mangleAssnKey( DeclarationWithType* decl, - const ResolvExpr::TypeEnvironment& env ); namespace Encoding {