Index: src/ResolvExpr/ConversionCost.cc =================================================================== --- src/ResolvExpr/ConversionCost.cc (revision b7b573cc074351e18b2a4a947682b7218166e2c7) +++ src/ResolvExpr/ConversionCost.cc (revision 5fb17f16502a3ec147bf5fe2feec39570ad82aff) @@ -10,6 +10,6 @@ // Created On : Sun May 17 07:06:19 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Feb 14 17:04:31 2019 -// Update Count : 23 +// Last Modified On : Fri Apr 26 16:33:04 2019 +// Update Count : 24 // @@ -28,4 +28,5 @@ namespace ResolvExpr { +#if 0 const Cost Cost::zero = Cost{ 0, 0, 0, 0, 0, 0, 0 }; const Cost Cost::infinity = Cost{ -1, -1, -1, -1, -1, 1, -1 }; @@ -37,4 +38,5 @@ const Cost Cost::spec = Cost{ 0, 0, 0, 0, 0, -1, 0 }; const Cost Cost::reference = Cost{ 0, 0, 0, 0, 0, 0, 1 }; +#endif #if 0 Index: src/ResolvExpr/Cost.h =================================================================== --- src/ResolvExpr/Cost.h (revision b7b573cc074351e18b2a4a947682b7218166e2c7) +++ src/ResolvExpr/Cost.h (revision 5fb17f16502a3ec147bf5fe2feec39570ad82aff) @@ -7,9 +7,9 @@ // Cost.h -- // -// Author : Richard C. Bilson +// Author : Peter Buhr and Aaron Moss // Created On : Sun May 17 09:39:50 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Feb 7 20:54:29 2019 -// Update Count : 8 +// Last Modified On : Sun Apr 28 18:26:36 2019 +// Update Count : 29 // @@ -17,10 +17,15 @@ #include +#include namespace ResolvExpr { +#if 0 + + //*************************** OLD *************************** + class Cost { private: Cost( int unsafeCost, int polyCost, int safeCost, int signCost, - int varCost, int specCost, int referenceCost ); + int varCost, int specCost, int referenceCost ); public: Cost & incUnsafe( int inc = 1 ); @@ -71,5 +76,5 @@ inline Cost::Cost( int unsafeCost, int polyCost, int safeCost, int signCost, - int varCost, int specCost, int referenceCost ) + int varCost, int specCost, int referenceCost ) : unsafeCost( unsafeCost ), polyCost( polyCost ), safeCost( safeCost ), signCost( signCost ), varCost( varCost ), specCost( specCost ), referenceCost( referenceCost ) {} @@ -121,6 +126,6 @@ return Cost{ unsafeCost + other.unsafeCost, polyCost + other.polyCost, safeCost + other.safeCost, - signCost + other.signCost, varCost + other.varCost, specCost + other.specCost, - referenceCost + other.referenceCost }; + signCost + other.signCost, varCost + other.varCost, specCost + other.specCost, + referenceCost + other.referenceCost }; } @@ -211,4 +216,149 @@ << cost.referenceCost << " )"; } +#endif // 0 + + //*************************** NEW *************************** + + class Cost { + union { + struct { + #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ + // Little-endian => first value is low priority and last is high priority. + unsigned char padding; ///< unused + unsigned char referenceCost; ///< reference conversions + unsigned char specCost; ///< Polymorphic type specializations (type assertions), negative cost + unsigned char varCost; ///< Count of polymorphic type variables + unsigned char signCost; ///< Count of safe sign conversions + unsigned char safeCost; ///< Safe (widening) conversions + unsigned char polyCost; ///< Count of parameters and return values bound to some poly type + unsigned char unsafeCost; ///< Unsafe (narrowing) conversions + #else + #error BIG_ENDIAN unsupported + #endif + } v; + uint64_t all; + }; + public: + // Compiler adjusts constants for correct endian. + enum : uint64_t { + zero = 0x00'00'00'00'00'ff'00'00, + infinity = 0xff'ff'ff'ff'ff'00'ff'ff, + correction = 0x00'00'00'00'00'ff'00'00, // correct for negative spec cost + unsafe = 0x01'00'00'00'00'ff'00'00, + poly = 0x00'01'00'00'00'ff'00'00, + safe = 0x00'00'01'00'00'ff'00'00, + sign = 0x00'00'00'01'00'ff'00'00, + var = 0x00'00'00'00'01'ff'00'00, + spec = 0x00'00'00'00'00'fe'00'00, + reference = 0x00'00'00'00'00'ff'01'00, + }; // + + Cost( uint64_t all ) { Cost::all = all; } + Cost( int unsafeCost, int polyCost, int safeCost, int signCost, int varCost, int specCost, int referenceCost ) { + // Assume little-endian => first value is low priority and last is high priority. + v = { + (unsigned char)0, // padding + (unsigned char)referenceCost, + (unsigned char)(specCost + 0xff ), // correct for signedness + (unsigned char)varCost, + (unsigned char)signCost, + (unsigned char)safeCost, + (unsigned char)polyCost, + (unsigned char)unsafeCost, + }; + } + + int get_unsafeCost() const { return v.unsafeCost; } + int get_polyCost() const { return v.polyCost; } + int get_safeCost() const { return v.safeCost; } + int get_signCost() const { return v.signCost; } + int get_varCost() const { return v.varCost; } + int get_specCost() const { return -(0xff - v.specCost); } + int get_referenceCost() const { return v.referenceCost; } + + friend bool operator==( const Cost, const Cost ); + friend bool operator!=( const Cost lhs, const Cost rhs ); + // returns negative for *this < rhs, 0 for *this == rhs, positive for *this > rhs + int compare( const Cost rhs ) const { + if ( all == infinity ) return 1; + if ( rhs.all == infinity ) return -1; + return all > rhs.all ? 1 : all == rhs.all ? 0 : -1; + } + friend bool operator<( const Cost lhs, const Cost rhs ); + + friend Cost operator+( const Cost lhs, const Cost rhs ); + + Cost operator+=( const Cost rhs ) { + if ( all == infinity ) return *this; + if ( rhs.all == infinity ) { + all = infinity; + return *this; + } + all += rhs.all - correction; // correct for negative spec cost + return *this; + } + + Cost incUnsafe( int inc = 1 ) { + if ( all != infinity ) { assert( v.unsafeCost + inc < 256 ); v.unsafeCost += inc; } + return *this; + } + + Cost incPoly( int inc = 1 ) { + if ( all != infinity ) { assert( v.polyCost + inc < 256 ); v.polyCost += inc; } + return *this; + } + + Cost incSafe( int inc = 1 ) { + if ( all != infinity ) { assert( v.safeCost + inc < 256 ); v.safeCost += inc; } + return *this; + } + + Cost incSign( int inc = 1 ) { + if ( all != infinity ) { assert( v.signCost + inc < 256 ); v.signCost += inc; } + return *this; + } + + Cost incVar( int inc = 1 ) { + if ( all != infinity ) { assert( v.varCost + inc < 256 ); v.varCost += inc; } + return *this; + } + + Cost decSpec( int dec = 1 ) { + if ( all != infinity ) { v.specCost -= dec; } + return *this; + } + + Cost incReference( int inc = 1 ) { + if ( all != infinity ) { assert( v.referenceCost + inc < 256 ); v.referenceCost += inc; } + return *this; + } + + friend std::ostream & operator<<( std::ostream & os, const Cost cost ); + }; + + inline bool operator==( const Cost lhs, const Cost rhs ) { + return lhs.all == rhs.all; + } + + inline bool operator!=( const Cost lhs, const Cost rhs ) { + return !( lhs.all == rhs.all ); + } + + inline bool operator<( const Cost lhs, const Cost rhs ) { + if ( lhs.all == Cost::infinity ) return false; + if ( rhs.all == Cost::infinity ) return true; + return lhs.all < rhs.all; + } + + inline Cost operator+( const Cost lhs, const Cost rhs ) { + if ( lhs.all == Cost::infinity || rhs.all == Cost::infinity ) return Cost{ Cost::infinity }; + return Cost{ lhs.all + rhs.all - Cost::correction }; // correct for negative spec cost + } + + inline std::ostream & operator<<( std::ostream & os, const Cost cost ) { + return os << "( " << cost.get_unsafeCost() << ", " << cost.get_polyCost() << ", " << cost.get_safeCost() + << ", " << cost.get_signCost() << ", " << cost.get_varCost() << ", " << cost.get_specCost() + << ", " << cost.get_referenceCost() << " )"; + } } // namespace ResolvExpr Index: src/ResolvExpr/ResolveAssertions.cc =================================================================== --- src/ResolvExpr/ResolveAssertions.cc (revision b7b573cc074351e18b2a4a947682b7218166e2c7) +++ src/ResolvExpr/ResolveAssertions.cc (revision 5fb17f16502a3ec147bf5fe2feec39570ad82aff) @@ -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 b7b573cc074351e18b2a4a947682b7218166e2c7) +++ src/SymTab/Mangler.cc (revision 5fb17f16502a3ec147bf5fe2feec39570ad82aff) @@ -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 b7b573cc074351e18b2a4a947682b7218166e2c7) +++ src/SymTab/Mangler.h (revision 5fb17f16502a3ec147bf5fe2feec39570ad82aff) @@ -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 {