Changeset 9160cb2

Timestamp:

Jul 25, 2018, 5:33:21 PM (7 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

new-env

Children:

5a3e1f1

Parents:

f89a111

git-author:

Aaron Moss <a3moss@…> (07/25/18 13:49:26)

git-committer:

Aaron Moss <a3moss@…> (07/25/18 17:33:21)

Message:

Breadth-first assertion resolution builds, eats all the memory

Location:

src

Files:

• Common/FilterCombos.h (added)
• ResolvExpr/AlternativeFinder.cc (modified) (14 diffs)
• ResolvExpr/TypeEnvironment.cc (modified) (4 diffs)

src/ResolvExpr/AlternativeFinder.cc

@@ -37 +37 @@
 #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 +119 @@
                 /// 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 +585 @@
         }
 
-#if !1
+#if 1
         namespace {
                 /// Information required to defer resolution of an expression
@@ -600 +601 @@
                                 : 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 +626 @@
                 using DeferList = std::vector<AssertionPack>;
 
+                /// 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<DeclarationWithType*, AssertionSetValue, DeferList>;
-
-                        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<DeferItem> 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 +693 @@
                         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 +727 @@
                         // 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 +760 @@
                         // 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<DeferElement> crnt;
+                        /// Stack of environments, to support backtracking
+                        std::vector<TypeEnvironment> 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<TypeEnvironment, std::vector<DeferElement>>;
+
+                        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 +812 @@
                 // )
                 addToIndexer( have, decls );
-#if !1
-                AssertionResnState resn{ newAlt, openVars, indexer };
+#if 1
+                using ResnList = std::vector<AssertionResnState>;
+                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<InterpretationEnvMerger::OutType> 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 +1373 @@
                         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 +1737 @@
                                 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 +2018 @@
                                                 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 +2056 @@
                                         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 +2163 @@
                                         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 ) );
                                 }
                         }

src/ResolvExpr/TypeEnvironment.cc

@@ -411 +411 @@
         }
 
-        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 +479 @@
                                         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 +539 @@
                                 // 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 +575 @@
                         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