Changeset b408364 for src/ResolvExpr

Timestamp:

Jun 18, 2019, 5:51:23 PM (5 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

898ae07

Parents:

c8e4d2f8

Message:

Correct over-aggressive assertion pruning

File:

• src/ResolvExpr/ResolveAssertions.cc (modified) (9 diffs)

src/ResolvExpr/ResolveAssertions.cc

@@ -186 +186 @@
         using InferCache = std::unordered_map< UniqueId, InferredParams >;
 
+        /// Lexicographically-ordered vector of costs
+        using CostVec = std::vector< Cost >;
+
+        int compare( const CostVec & a, const CostVec & b ) {
+                unsigned i = 0;
+                do {
+                        // lex-compare where shorter one is less
+                        if ( i == a.size() ) {
+                                return i == b.size() ? 0 : -1;
+                        }
+                        if ( i == b.size() /* && i < a.size() */ ) return 1;
+                        
+                        int c = a[i].compare( b[i] );
+                        if ( c != 0 ) return c;
+                } while ( ++i );
+                assert(!"unreachable");
+        }
+
+        bool operator< ( const CostVec & a, const CostVec & b ) { return compare( a, b ) < 0; }
+
         /// Flag for state iteration
         enum IterateFlag { IterateState };
@@ -196 +216 @@
                 DeferList deferred;        ///< Deferred matches
                 InferCache inferred;       ///< Cache of already-inferred parameters
+                CostVec costs;             ///< Costs of recursive assertion satisfaction for disambiguation
                 SymTab::Indexer& indexer;  ///< Name lookup (depends on previous assertions)
 
                 /// Initial resolution state for an alternative
                 ResnState( Alternative& a, SymTab::Indexer& indexer )
-                : alt(a), need(), newNeed(), deferred(), inferred(), indexer(indexer) {
+                : alt(a), need(), newNeed(), deferred(), inferred(), costs{ Cost::zero }, indexer(indexer) {
                         need.swap( a.need );
                 }
@@ -207 +228 @@
                 ResnState( ResnState&& o, IterateFlag )
                 : alt(std::move(o.alt)), need(o.newNeed.begin(), o.newNeed.end()), newNeed(), deferred(),
-                  inferred(std::move(o.inferred)), indexer(o.indexer) {}
+                  inferred(std::move(o.inferred)), costs(o.costs), indexer(o.indexer) {
+                        costs.emplace_back( Cost::zero );
+                }
         };
 
@@ -336 +359 @@
         };
 
-        void finalizeAssertions( Alternative& alt, InferCache& inferred, AltList& out ) {
-                PassVisitor<InferMatcher> matcher{ inferred };
-                alt.expr = alt.expr->acceptMutator( matcher );
-                out.emplace_back( alt );
+        /// Map of alternative return types to recursive assertion satisfaction costs
+        using PruneMap = std::unordered_map<std::string, CostVec>;
+
+        /// Gets the pruning key for an alternative
+        std::string pruneKey( const Alternative & alt ) {
+                Type* resType = alt.expr->result->clone();
+                alt.env.apply( resType );
+                std::string resKey = SymTab::Mangler::mangleType( resType );
+                delete resType;
+                return std::move( resKey );
+        }
+        
+        /// Replace resnSlots with inferParams and add alternative to output list, if meets pruning 
+        /// threshold.
+        void finalizeAssertions( ResnState& resn, PruneMap & pruneThresholds, AltList& out ) {
+                // prune if cheaper alternative for same key has already been generated
+                std::string resKey = pruneKey( resn.alt );
+                auto it = pruneThresholds.find( resKey );
+                if ( it != pruneThresholds.end() ) {
+                        if ( it->second < resn.costs ) return;
+                } else {
+                        pruneThresholds.emplace_hint( it, resKey, resn.costs );
+                }
+
+                // replace resolution slots with inferred params, add to output
+                PassVisitor<InferMatcher> matcher{ resn.inferred };
+                resn.alt.expr = resn.alt.expr->acceptMutator( matcher );
+                out.emplace_back( resn.alt );
         }
 
@@ -359 +406 @@
                 ResnList resns{ ResnState{ alt, root_indexer } };
                 ResnList new_resns{};
+                
+                // Pruning thresholds by result type of the output alternatives.
+                // Alternatives *should* be generated in sorted order, so no need to retroactively prune
+                PruneMap thresholds;
 
                 // resolve assertions in breadth-first-order up to a limited number of levels deep
@@ -364 +415 @@
                         // scan over all mutually-compatible resolutions
                         for ( auto& resn : resns ) {
+                                // stop this branch if already found a better option
+                                auto it = thresholds.find( pruneKey( resn.alt ) );
+                                if ( it != thresholds.end() && it->second < resn.costs ) goto nextResn;
+
                                 // make initial pass at matching assertions
                                 for ( auto& assn : resn.need ) {
@@ -383 +438 @@
                                         // either add successful match or push back next state
                                         if ( resn.newNeed.empty() ) {
-                                                finalizeAssertions( resn.alt, resn.inferred, out );
+                                                finalizeAssertions( resn, thresholds, out );
                                         } else {
                                                 new_resns.emplace_back( std::move(resn), IterateState );
@@ -420 +475 @@
                                                 goto nextResn;
                                         }
-                                        // sort by cost
+                                        // sort by cost for overall pruning
                                         CandidateCost coster{ resn.indexer };
                                         std::sort( compatible.begin(), compatible.end(), coster );
 
-                                        // keep map of detected options
-                                        std::unordered_map<std::string, Cost> found;
                                         for ( auto& compat : compatible ) {
-                                                // filter by environment-adjusted result type, keep only cheapest option
-                                                Type* resType = alt.expr->result->clone();
-                                                compat.env.apply( resType );
-                                                // skip if cheaper alternative already processed with same result type
-                                                Cost resCost = coster.get( compat );
-                                                auto it = found.emplace( SymTab::Mangler::mangleType( resType ), resCost );
-                                                delete resType;
-                                                if ( it.second == false && it.first->second < resCost ) continue;
-
-                                                // proceed with resolution step
                                                 ResnState new_resn = resn;
 
@@ -452 +495 @@
                                                 new_resn.alt.openVars = std::move(compat.openVars);
 
+                                                // mark cost of this path
+                                                new_resn.costs.back() += compat.cost;
+
                                                 // either add sucessful match or push back next state
                                                 if ( new_resn.newNeed.empty() ) {
-                                                        finalizeAssertions( new_resn.alt, new_resn.inferred, out );
+                                                        finalizeAssertions( new_resn, thresholds, out );
                                                 } else {
                                                         new_resns.emplace_back( std::move(new_resn), IterateState );