Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision f89a1117ebfa413600d50598186beaf567f673bf) +++ src/ResolvExpr/AlternativeFinder.cc (revision 9160cb24908f8612069017b1575e57f975dd8175) @@ -37,4 +37,5 @@ #include "ResolveTypeof.h" // for resolveTypeof #include "Resolver.h" // for resolveStmtExpr +#include "Common/FilterCombos.h" // for filterCombos #include "Common/GC.h" // for new_static_root #include "SymTab/Indexer.h" // for Indexer @@ -118,5 +119,5 @@ /// 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 ); + void inferParameters( const AssertionSet &need, AssertionSet &have, Alternative &&newAlt, OpenVarSet &openVars, OutputIterator out ); private: AlternativeFinder & altFinder; @@ -584,5 +585,5 @@ } -#if !1 +#if 1 namespace { /// Information required to defer resolution of an expression @@ -600,4 +601,24 @@ : cdata(cdata), adjType(adjType), env(std::move(env)), have(std::move(have)), need(std::move(need)), openVars(std::move(openVars)) {} + + class iterator { + friend AssertionPack; + public: + const AssertionPack& pack; + private: + AssertionSet::iterator it; + + iterator(const AssertionPack& p, AssertionSet::iterator i) : pack{p}, it{i} {} + public: + iterator& operator++ () { ++it; return *this; } + iterator operator++ (int) { iterator tmp = *this; ++it; return tmp; } + AssertionSet::value_type& operator* () { return *it; } + AssertionSet::value_type* operator-> () { return it.operator->(); } + bool operator== (const iterator& o) const { return this == &o && it == o.it; } + bool operator!= (const iterator& o) const { return !(*this == o); } + }; + + iterator begin() { return { *this, need.begin() }; } + iterator end() { return { *this, need.end() }; } }; @@ -605,25 +626,66 @@ using DeferList = std::vector; + /// Single deferred item + struct DeferElement { + const DeclarationWithType* curDecl; + const AssertionSetValue& assnInfo; + const AssertionPack& match; + }; + + /// Wrapper for the DeferList of a single assertion resolution + struct DeferItem { + DeclarationWithType* curDecl; + AssertionSetValue assnInfo; + DeferList matches; + + DeferItem(DeclarationWithType* cd, const AssertionSetValue& ai, DeferList&& m ) + : curDecl{cd}, assnInfo{ai}, matches(std::move(m)) {} + + bool empty() const { return matches.empty(); } + + DeferList::size_type size() const { return matches.size(); } + + DeferElement operator[] ( unsigned i ) const { + return { curDecl, assnInfo, matches[i] }; + } + }; + + /// Flag for state iteration + enum CopyFlag { IterateState }; + /// Intermediate state for assertion resolution struct AssertionResnState { - using DeferItem = std::tuple; - - const Alternative& alt; ///< Alternative being built from + Alternative alt; ///< Alternative being built from + AssertionSet need; ///< Assertions to find 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} {} + SymTab::Indexer& indexer; ///< Name lookup + + /// field-wise constructor (some fields defaulted) + AssertionResnState(Alternative&& alt, const AssertionSet& need, + const OpenVarSet& openVars, SymTab::Indexer& indexer ) + : alt{std::move(alt)}, need{need}, newNeed{}, openVars{openVars}, deferred{}, + indexer{indexer} {} + + /// construct iterated state object from previous state + AssertionResnState(AssertionResnState&& o, CopyFlag) + : alt{std::move(o.alt)}, need{std::move(o.newNeed)}, newNeed{}, + openVars{std::move(o.openVars)}, deferred{}, indexer{o.indexer} {} + + /// copy resn state updated with specified data + AssertionResnState(const AssertionResnState& o, const AssertionSet& need, + const OpenVarSet& openVars, TypeEnvironment& env ) + : alt{o.alt}, need{}, newNeed{o.newNeed}, openVars{openVars}, deferred{}, + indexer{o.indexer} { + newNeed.insert( need.begin(), need.end() ); + alt.env = env; + } }; /// Binds a single assertion from a compatible AssertionPack, updating resolution state /// as appropriate. - void bindAssertion( DeclarationWithType* curDecl, AssertionSetValue& assnInfo, + void bindAssertion( const DeclarationWithType* curDecl, const 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() ); @@ -631,4 +693,5 @@ resn.alt.env = std::move(match.env); + DeclarationWithType* candidate = match.cdata.id; assertf( candidate->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() ); for ( auto& a : match.need ) { @@ -664,5 +727,5 @@ // lookup candidates for this assertion std::list< SymTab::Indexer::IdData > candidates; - decls.lookupId( curDecl->name, candidates ); + resn.indexer.lookupId( curDecl->name, candidates ); // find the ones that unify with the desired type @@ -697,12 +760,44 @@ // otherwise bind current match in ongoing scope bindAssertion( curDecl, assnInfo, resn, std::move(matches.front()) ); - return true; } + + /// Combo iterator that combines interpretations into an interpretation list, merging + /// their environments. Rejects an appended interpretation if the environments cannot + /// be merged. + class InterpretationEnvMerger { + /// Current list of merged interpretations + std::vector crnt; + /// Stack of environments, to support backtracking + std::vector envs; + /// Indexer to use for environment merges + const SymTab::Indexer& indexer; + public: + /// Outputs a pair consisting of the merged environment and the list of interpretations + using OutType = std::pair>; + + InterpretationEnvMerger( const TypeEnvironment& env, const SymTab::Indexer& indexer ) + : crnt{}, envs{}, indexer{indexer} { envs.push_back( env ); } + + ComboResult append( DeferElement i ) { + TypeEnvironment env = envs.back(); + if ( ! env.combine( i.match.env, indexer ) ) return ComboResult::REJECT_THIS; + crnt.push_back( i ); + envs.push_back( env ); + return ComboResult::ACCEPT; + } + + void backtrack() { + crnt.pop_back(); + envs.pop_back(); + } + + OutType finalize() { return { envs.back(), crnt }; } + }; } #endif template< typename OutputIterator > - void AlternativeFinder::Finder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) { + void AlternativeFinder::Finder::inferParameters( const AssertionSet &need, AssertionSet &have, Alternative &&newAlt, OpenVarSet &openVars, OutputIterator out ) { // PRINT( // std::cerr << "inferParameters: assertions needed are" << std::endl; @@ -717,40 +812,63 @@ // ) addToIndexer( have, decls ); -#if !1 - AssertionResnState resn{ newAlt, openVars, indexer }; +#if 1 + using ResnList = std::vector; + ResnList resns{ AssertionResnState{ std::move(newAlt), need, openVars, decls } }; + ResnList new_resns{}; // 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; + for ( int level = 0; level < recursionLimit; ++level ) { + // scan over all mutually-compatible resolutions + for ( auto& resn : resns ) { + // make initial pass at matching assertions + for ( auto& assn : resn.need ) { + if ( ! resolveAssertion( assn.first, assn.second, resn ) ) { + // fail early if any assertion fails to resolve + goto nextResn; + } + } + + if ( ! resn.deferred.empty() ) { + // resolve deferred assertions by mutual compatibility + + std::vector compatible = filterCombos( + resn.deferred, InterpretationEnvMerger{ resn.alt.env, resn.indexer }); + + for ( auto& compat : compatible ) { + AssertionResnState new_resn = resn; + + // add compatible assertions to new resolution state + for ( DeferElement el : compat.second ) { + bindAssertion( + el.curDecl, el.assnInfo, new_resn, AssertionPack{el.match} ); + } + + // set mutual environment into resolution state + new_resn.alt.env = std::move(compat.first); + + // add successful match or push back next state + if ( new_resn.newNeed.empty() ) { + *out++ = new_resn.alt; + } else { + new_resns.emplace_back( std::move(new_resn), IterateState ); + } + } + } else { + // add successful match or push back next state + if ( resn.newNeed.empty() ) { + *out++ = resn.alt; + } else { + new_resns.emplace_back( std::move(resn), IterateState ); + } + } + nextResn:; } + + // finish or reset for next round + if ( new_resns.empty() ) return; + resns.swap( new_resns ); + new_resns.clear(); + } + // if reaches here, exceeded recursion limit + SemanticError( newAlt.expr->location, "Too many recursive assertions" ); #else @@ -1255,5 +1373,5 @@ printAssertionSet( result.need, std::cerr, 8 ); ) - inferParameters( result.need, result.have, newAlt, result.openVars, out ); + inferParameters( result.need, result.have, std::move(newAlt), result.openVars, out ); } @@ -1619,5 +1737,5 @@ Alternative newAlt( restructureCast( alt.expr->clone(), toType, castExpr->isGenerated ), alt.env, alt.cost, thisCost ); - inferParameters( needAssertions, haveAssertions, newAlt, openVars, + inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars, back_inserter( candidates ) ); } // if @@ -1900,5 +2018,5 @@ newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env ); newAlt.expr = newExpr; - inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) ); + inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars, back_inserter( alternatives ) ); } // if } // for @@ -1938,5 +2056,5 @@ newExpr->result = commonType ? commonType : first.expr->result->clone(); newAlt.expr = newExpr; - inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) ); + inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars, back_inserter( alternatives ) ); } // if } // for @@ -2045,5 +2163,5 @@ thisCost.incSafe( discardedValues ); Alternative newAlt( new InitExpr( restructureCast( alt.expr, toType, true ), initAlt.designation ), newEnv, alt.cost, thisCost ); - inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) ); + inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars, back_inserter( candidates ) ); } } Index: src/ResolvExpr/TypeEnvironment.cc =================================================================== --- src/ResolvExpr/TypeEnvironment.cc (revision f89a1117ebfa413600d50598186beaf567f673bf) +++ src/ResolvExpr/TypeEnvironment.cc (revision 9160cb24908f8612069017b1575e57f975dd8175) @@ -411,5 +411,5 @@ } - bool TypeEnvrionment::combine( const TypeEnvironment& o, const SymTab::Indexer& indexer ) { + bool TypeEnvironment::combine( const TypeEnvironment& o, const SymTab::Indexer& indexer ) { // short-circuit for empty cases if ( o.isEmpty() ) return true; @@ -479,6 +479,6 @@ case Classes::ADDTO: { // later unmerged from same class, no net change to classes - assume( nmode == Classes::REMFROM, "inconsistent mode" ); - assume( oclasses->get_root() == next->second.root, "inconsistent tree" ); + assertf( nmode == Classes::REMFROM, "inconsistent mode" ); + assertf( oclasses->get_root() == next->second.root, "inconsistent tree" ); edits.erase( next ); forKey.pop_back(); @@ -539,7 +539,7 @@ // newly seen key, mark operation if ( bmode == Bindings::REM ) { - bedits.emplace_back( it, key, BEdit{ bmode } ); + bedits.emplace_hint( it, key, BEdit{ bmode } ); } else { - bedits.emplace_back( it, key, BEdit{ bmode, bbindings->get_val() } ); + bedits.emplace_hint( it, key, BEdit{ bmode, bbindings->get_val() } ); } } else { @@ -575,5 +575,5 @@ bmode = bbindings->get_mode(); } - assume( bbindings == bindings, "bindings must be versions of same map" ); + assertf( bbindings == bindings, "bindings must be versions of same map" ); // merge typeclasses (always possible, can always merge all classes into one if the