Changeset 9160cb2


Ignore:
Timestamp:
Jul 25, 2018, 5:33:21 PM (6 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:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • src/ResolvExpr/AlternativeFinder.cc

    rf89a111 r9160cb2  
    3737#include "ResolveTypeof.h"         // for resolveTypeof
    3838#include "Resolver.h"              // for resolveStmtExpr
     39#include "Common/FilterCombos.h"   // for filterCombos
    3940#include "Common/GC.h"             // for new_static_root
    4041#include "SymTab/Indexer.h"        // for Indexer
     
    118119                /// Checks if assertion parameters match for a new alternative
    119120                template< typename OutputIterator >
    120                 void inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out );
     121                void inferParameters( const AssertionSet &need, AssertionSet &have, Alternative &&newAlt, OpenVarSet &openVars, OutputIterator out );
    121122        private:
    122123                AlternativeFinder & altFinder;
     
    584585        }
    585586
    586 #if !1
     587#if 1
    587588        namespace {
    588589                /// Information required to defer resolution of an expression
     
    600601                                : cdata(cdata), adjType(adjType), env(std::move(env)), have(std::move(have)),
    601602                                  need(std::move(need)), openVars(std::move(openVars)) {}
     603                       
     604                        class iterator {
     605                        friend AssertionPack;
     606                        public:
     607                                const AssertionPack& pack;
     608                        private:
     609                                AssertionSet::iterator it;
     610
     611                                iterator(const AssertionPack& p, AssertionSet::iterator i) : pack{p}, it{i} {}
     612                        public:
     613                                iterator& operator++ () { ++it; return *this; }
     614                                iterator operator++ (int) { iterator tmp = *this; ++it; return tmp; }
     615                                AssertionSet::value_type& operator* () { return *it; }
     616                                AssertionSet::value_type* operator-> () { return it.operator->(); }
     617                                bool operator== (const iterator& o) const { return this == &o && it == o.it; }
     618                                bool operator!= (const iterator& o) const { return !(*this == o); }
     619                        };
     620
     621                        iterator begin() { return { *this, need.begin() }; }
     622                        iterator end() { return { *this, need.end() }; }
    602623                };
    603624
     
    605626                using DeferList = std::vector<AssertionPack>;
    606627
     628                /// Single deferred item
     629                struct DeferElement {
     630                        const DeclarationWithType* curDecl;
     631                        const AssertionSetValue& assnInfo;
     632                        const AssertionPack& match;
     633                };
     634
     635                /// Wrapper for the DeferList of a single assertion resolution
     636                struct DeferItem {
     637                        DeclarationWithType* curDecl;
     638                        AssertionSetValue assnInfo;
     639                        DeferList matches;
     640
     641                        DeferItem(DeclarationWithType* cd, const AssertionSetValue& ai, DeferList&& m )
     642                                : curDecl{cd}, assnInfo{ai}, matches(std::move(m)) {}
     643
     644                        bool empty() const { return matches.empty(); }
     645
     646                        DeferList::size_type size() const { return matches.size(); }
     647
     648                        DeferElement operator[] ( unsigned i ) const {
     649                                return { curDecl, assnInfo, matches[i] };
     650                        }
     651                };
     652
     653                /// Flag for state iteration
     654                enum CopyFlag { IterateState };
     655
    607656                /// Intermediate state for assertion resolution
    608657                struct AssertionResnState {
    609                         using DeferItem = std::tuple<DeclarationWithType*, AssertionSetValue, DeferList>;
    610 
    611                         const Alternative& alt;           ///< Alternative being built from
     658                        Alternative alt;                  ///< Alternative being built from
     659                        AssertionSet need;                ///< Assertions to find
    612660                        AssertionSet newNeed;             ///< New assertions found from current assertions
    613661                        OpenVarSet openVars;              ///< Open variables in current context
    614662                        std::vector<DeferItem> deferred;  ///< Possible deferred assertion resolutions
    615                         const SymTab::Indexer& indexer;   ///< Name lookup
    616 
    617                         AssertionResnState(const Alternative& alt, const OpenVarSet& openVars,
    618                                 const SymTab::Indexer& indexer )
    619                                 : alt{alt}, have{}, newNeed{}, openVars{openVars}, indexer{indexer} {}
     663                        SymTab::Indexer& indexer;         ///< Name lookup
     664
     665                        /// field-wise constructor (some fields defaulted)
     666                        AssertionResnState(Alternative&& alt, const AssertionSet& need,
     667                                const OpenVarSet& openVars, SymTab::Indexer& indexer )
     668                                : alt{std::move(alt)}, need{need}, newNeed{}, openVars{openVars}, deferred{},
     669                                  indexer{indexer} {}
     670                       
     671                        /// construct iterated state object from previous state
     672                        AssertionResnState(AssertionResnState&& o, CopyFlag)
     673                                : alt{std::move(o.alt)}, need{std::move(o.newNeed)}, newNeed{},
     674                                  openVars{std::move(o.openVars)}, deferred{}, indexer{o.indexer} {}
     675                       
     676                        /// copy resn state updated with specified data
     677                        AssertionResnState(const AssertionResnState& o, const AssertionSet& need,
     678                                const OpenVarSet& openVars, TypeEnvironment& env )
     679                                : alt{o.alt}, need{}, newNeed{o.newNeed}, openVars{openVars}, deferred{},
     680                                  indexer{o.indexer} {
     681                                newNeed.insert( need.begin(), need.end() );
     682                                alt.env = env;
     683                        }
    620684                };
    621685
    622686                /// Binds a single assertion from a compatible AssertionPack, updating resolution state
    623687                /// as appropriate.
    624                 void bindAssertion( DeclarationWithType* curDecl, AssertionSetValue& assnInfo,
     688                void bindAssertion( const DeclarationWithType* curDecl, const AssertionSetValue& assnInfo,
    625689                                AssertionResnState& resn, AssertionPack&& match ) {
    626                         DeclarationWithType* candidate = match.cdata.id;
    627                        
    628690                        addToIndexer( match.have, resn.indexer );
    629691                        resn.newNeed.insert( match.need.begin(), match.need.end() );
     
    631693                        resn.alt.env = std::move(match.env);
    632694
     695                        DeclarationWithType* candidate = match.cdata.id;
    633696                        assertf( candidate->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );
    634697                        for ( auto& a : match.need ) {
     
    664727                        // lookup candidates for this assertion
    665728                        std::list< SymTab::Indexer::IdData > candidates;
    666                         decls.lookupId( curDecl->name, candidates );
     729                        resn.indexer.lookupId( curDecl->name, candidates );
    667730
    668731                        // find the ones that unify with the desired type
     
    697760                        // otherwise bind current match in ongoing scope
    698761                        bindAssertion( curDecl, assnInfo, resn, std::move(matches.front()) );
    699 
    700762                        return true;
    701763                }
     764
     765                /// Combo iterator that combines interpretations into an interpretation list, merging
     766                /// their environments. Rejects an appended interpretation if the environments cannot
     767                /// be merged.
     768                class InterpretationEnvMerger {
     769                        /// Current list of merged interpretations
     770                        std::vector<DeferElement> crnt;
     771                        /// Stack of environments, to support backtracking
     772                        std::vector<TypeEnvironment> envs;
     773                        /// Indexer to use for environment merges
     774                        const SymTab::Indexer& indexer;
     775                public:
     776                        /// Outputs a pair consisting of the merged environment and the list of interpretations
     777                        using OutType = std::pair<TypeEnvironment, std::vector<DeferElement>>;
     778
     779                        InterpretationEnvMerger( const TypeEnvironment& env, const SymTab::Indexer& indexer )
     780                                : crnt{}, envs{}, indexer{indexer} { envs.push_back( env ); }
     781
     782                        ComboResult append( DeferElement i ) {
     783                                TypeEnvironment env = envs.back();
     784                                if ( ! env.combine( i.match.env, indexer ) ) return ComboResult::REJECT_THIS;
     785                                crnt.push_back( i );
     786                                envs.push_back( env );
     787                                return ComboResult::ACCEPT;
     788                        }
     789
     790                        void backtrack() {
     791                                crnt.pop_back();
     792                                envs.pop_back();
     793                        }
     794
     795                        OutType finalize() { return { envs.back(), crnt }; }
     796                };
    702797        }
    703798#endif
    704799
    705800        template< typename OutputIterator >
    706         void AlternativeFinder::Finder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
     801        void AlternativeFinder::Finder::inferParameters( const AssertionSet &need, AssertionSet &have, Alternative &&newAlt, OpenVarSet &openVars, OutputIterator out ) {
    707802//      PRINT(
    708803//          std::cerr << "inferParameters: assertions needed are" << std::endl;
     
    717812                // )
    718813                addToIndexer( have, decls );
    719 #if !1
    720                 AssertionResnState resn{ newAlt, openVars, indexer };
     814#if 1
     815                using ResnList = std::vector<AssertionResnState>;
     816                ResnList resns{ AssertionResnState{ std::move(newAlt), need, openVars, decls } };
     817                ResnList new_resns{};
    721818
    722819                // resolve assertions in breadth-first-order up to a limited number of levels deep
    723                 int level;
    724                 for ( level = 0; level < recursionLimit; ++level ) {
    725                         // make initial pass at matching assertions
    726                         for ( auto& assn : need ) {
    727                                 if ( ! resolveAssertion( assn.first, assn.second, resn ) ) {
    728                                         // fail early if any assertion fails to resolve
    729                                         return;
    730                                 }
    731                         }
    732 
    733                         // resolve deferred assertions by mutual compatibility and min-cost
    734                         if ( ! resn.deferred.empty() ) {
    735                                 // TODO
    736                                 assert(false && "TODO: deferred assertions unimplemented");
    737 
    738                                 // reset for next round
    739                                 resn.deferred.clear();
    740                         }
    741 
    742                         // quit resolving assertions if done
    743                         if ( resn.newNeed.empty() ) break;
    744 
    745                         // otherwise start on next group of recursive assertions
    746                         need.swap( resn.newNeed );
    747                         resn.newNeed.clear();
    748                 }
    749                 if ( level >= recursionLimit ) {
    750                         SemanticError( newAlt.expr->location, "Too many recursive assertions" );
    751                 }
    752                
    753                 // add completed assertion to output
    754                 *out++ = newAlt;
     820                for ( int level = 0; level < recursionLimit; ++level ) {
     821                        // scan over all mutually-compatible resolutions
     822                        for ( auto& resn : resns ) {
     823                                // make initial pass at matching assertions
     824                                for ( auto& assn : resn.need ) {
     825                                        if ( ! resolveAssertion( assn.first, assn.second, resn ) ) {
     826                                                // fail early if any assertion fails to resolve
     827                                                goto nextResn;
     828                                        }
     829                                }
     830
     831                                if ( ! resn.deferred.empty() ) {
     832                                        // resolve deferred assertions by mutual compatibility
     833
     834                                        std::vector<InterpretationEnvMerger::OutType> compatible = filterCombos(
     835                                                resn.deferred, InterpretationEnvMerger{ resn.alt.env, resn.indexer });
     836                                       
     837                                        for ( auto& compat : compatible ) {
     838                                                AssertionResnState new_resn = resn;
     839
     840                                                // add compatible assertions to new resolution state
     841                                                for ( DeferElement el : compat.second ) {
     842                                                        bindAssertion(
     843                                                                el.curDecl, el.assnInfo, new_resn, AssertionPack{el.match} );
     844                                                }
     845
     846                                                // set mutual environment into resolution state
     847                                                new_resn.alt.env = std::move(compat.first);
     848
     849                                                // add successful match or push back next state
     850                                                if ( new_resn.newNeed.empty() ) {
     851                                                        *out++ = new_resn.alt;
     852                                                } else {
     853                                                        new_resns.emplace_back( std::move(new_resn), IterateState );
     854                                                }
     855                                        }
     856                                } else {
     857                                        // add successful match or push back next state
     858                                        if ( resn.newNeed.empty() ) {
     859                                                *out++ = resn.alt;
     860                                        } else {
     861                                                new_resns.emplace_back( std::move(resn), IterateState );
     862                                        }
     863                                }
     864                        nextResn:; }
     865                       
     866                        // finish or reset for next round
     867                        if ( new_resns.empty() ) return;
     868                        resns.swap( new_resns );
     869                        new_resns.clear();
     870                }
     871                // if reaches here, exceeded recursion limit
     872                SemanticError( newAlt.expr->location, "Too many recursive assertions" );
    755873
    756874#else           
     
    12551373                        printAssertionSet( result.need, std::cerr, 8 );
    12561374                )
    1257                 inferParameters( result.need, result.have, newAlt, result.openVars, out );
     1375                inferParameters( result.need, result.have, std::move(newAlt), result.openVars, out );
    12581376        }
    12591377
     
    16191737                                Alternative newAlt( restructureCast( alt.expr->clone(), toType, castExpr->isGenerated ), alt.env,
    16201738                                        alt.cost, thisCost );
    1621                                 inferParameters( needAssertions, haveAssertions, newAlt, openVars,
     1739                                inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars,
    16221740                                        back_inserter( candidates ) );
    16231741                        } // if
     
    19002018                                                newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
    19012019                                                newAlt.expr = newExpr;
    1902                                                 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
     2020                                                inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars, back_inserter( alternatives ) );
    19032021                                        } // if
    19042022                                } // for
     
    19382056                                        newExpr->result = commonType ? commonType : first.expr->result->clone();
    19392057                                        newAlt.expr = newExpr;
    1940                                         inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
     2058                                        inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars, back_inserter( alternatives ) );
    19412059                                } // if
    19422060                        } // for
     
    20452163                                        thisCost.incSafe( discardedValues );
    20462164                                        Alternative newAlt( new InitExpr( restructureCast( alt.expr, toType, true ), initAlt.designation ), newEnv, alt.cost, thisCost );
    2047                                         inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
     2165                                        inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars, back_inserter( candidates ) );
    20482166                                }
    20492167                        }
  • src/ResolvExpr/TypeEnvironment.cc

    rf89a111 r9160cb2  
    411411        }
    412412
    413         bool TypeEnvrionment::combine( const TypeEnvironment& o, const SymTab::Indexer& indexer ) {
     413        bool TypeEnvironment::combine( const TypeEnvironment& o, const SymTab::Indexer& indexer ) {
    414414                // short-circuit for empty cases
    415415                if ( o.isEmpty() ) return true;
     
    479479                                        case Classes::ADDTO: {
    480480                                                // later unmerged from same class, no net change to classes
    481                                                 assume( nmode == Classes::REMFROM, "inconsistent mode" );
    482                                                 assume( oclasses->get_root() == next->second.root, "inconsistent tree" );
     481                                                assertf( nmode == Classes::REMFROM, "inconsistent mode" );
     482                                                assertf( oclasses->get_root() == next->second.root, "inconsistent tree" );
    483483                                                edits.erase( next );
    484484                                                forKey.pop_back();
     
    539539                                // newly seen key, mark operation
    540540                                if ( bmode == Bindings::REM ) {
    541                                         bedits.emplace_back( it, key, BEdit{ bmode } );
     541                                        bedits.emplace_hint( it, key, BEdit{ bmode } );
    542542                                } else {
    543                                         bedits.emplace_back( it, key, BEdit{ bmode, bbindings->get_val() } );
     543                                        bedits.emplace_hint( it, key, BEdit{ bmode, bbindings->get_val() } );
    544544                                }
    545545                        } else {
     
    575575                        bmode = bbindings->get_mode();
    576576                }
    577                 assume( bbindings == bindings, "bindings must be versions of same map" );
     577                assertf( bbindings == bindings, "bindings must be versions of same map" );
    578578
    579579                // merge typeclasses (always possible, can always merge all classes into one if the
Note: See TracChangeset for help on using the changeset viewer.