Changes in src/ResolvExpr/ResolveAssertions.cc [b408364:462a7c7]

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 };
@@ -216 +196 @@
                 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(), costs{ Cost::zero }, indexer(indexer) {
+                : alt(a), need(), newNeed(), deferred(), inferred(), indexer(indexer) {
                         need.swap( a.need );
                 }
@@ -228 +207 @@
                 ResnState( ResnState&& o, IterateFlag )
                 : alt(std::move(o.alt)), need(o.newNeed.begin(), o.newNeed.end()), newNeed(), deferred(),
-                  inferred(std::move(o.inferred)), costs(o.costs), indexer(o.indexer) {
-                        costs.emplace_back( Cost::zero );
-                }
+                  inferred(std::move(o.inferred)), indexer(o.indexer) {}
         };
 
@@ -359 +336 @@
         };
 
-        /// 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 );
+        void finalizeAssertions( Alternative& alt, InferCache& inferred, AltList& out ) {
+                PassVisitor<InferMatcher> matcher{ inferred };
+                alt.expr = alt.expr->acceptMutator( matcher );
+                out.emplace_back( alt );
         }
 
@@ -406 +359 @@
                 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
@@ -415 +364 @@
                         // 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 ) {
@@ -438 +383 @@
                                         // either add successful match or push back next state
                                         if ( resn.newNeed.empty() ) {
-                                                finalizeAssertions( resn, thresholds, out );
+                                                finalizeAssertions( resn.alt, resn.inferred, out );
                                         } else {
                                                 new_resns.emplace_back( std::move(resn), IterateState );
@@ -475 +420 @@
                                                 goto nextResn;
                                         }
-                                        // sort by cost for overall pruning
+                                        // sort by cost
                                         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;
 
@@ -495 +452 @@
                                                 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, thresholds, out );
+                                                        finalizeAssertions( new_resn.alt, new_resn.inferred, out );
                                                 } else {
                                                         new_resns.emplace_back( std::move(new_resn), IterateState );