Changeset 1389810

Timestamp:

Nov 26, 2020, 6:52:03 PM (4 years ago)

Author:

Fangren Yu <f37yu@…>

Branches:

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

Children:

88a0ff6

Parents:

4702a2c

Message:

consolidate prune and satisfy assertion

Location:

src/ResolvExpr

Files:

• AlternativeFinder.cc (modified) (1 diff)
• CandidateFinder.cpp (modified) (4 diffs)
• CandidateFinder.hpp (modified) (1 diff)
• ResolvMode.h (modified) (1 diff)
• SatisfyAssertions.hpp (modified) (1 diff)

src/ResolvExpr/AlternativeFinder.cc

@@ -251 +251 @@
                         SemanticError( expr, "No reasonable alternatives for expression " );
                 }
-                if ( mode.satisfyAssns || mode.prune ) {
+                if ( mode.prune ) {
                         // trim candidates just to those where the assertions resolve
                         // - necessary pre-requisite to pruning

src/ResolvExpr/CandidateFinder.cpp

@@ -1645 +1645 @@
         /// Prunes a list of candidates down to those that have the minimum conversion cost for a given
         /// return type. Skips ambiguous candidates.
-        CandidateList pruneCandidates( CandidateList & candidates ) {
-                struct PruneStruct {
-                        CandidateRef candidate;
-                        bool ambiguous;
-
-                        PruneStruct() = default;
-                        PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}
-                };
-
-                // find lowest-cost candidate for each type
-                std::unordered_map< std::string, PruneStruct > selected;
-                for ( CandidateRef & candidate : candidates ) {
-                        std::string mangleName;
+
+} // anonymous namespace
+
+bool CandidateFinder::pruneCandidates( CandidateList & candidates, CandidateList & out, std::vector<std::string> & errors ) {
+        struct PruneStruct {
+                CandidateRef candidate;
+                bool ambiguous;
+
+                PruneStruct() = default;
+                PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}
+        };
+
+        // find lowest-cost candidate for each type
+        std::unordered_map< std::string, PruneStruct > selected;
+        // attempt to skip satisfyAssertions on more expensive alternatives if better options have been found
+        std::sort(candidates.begin(), candidates.end(), [](const CandidateRef & x, const CandidateRef & y){return x->cost < y->cost;});
+        for ( CandidateRef & candidate : candidates ) {
+                std::string mangleName;
+                {
+                        ast::ptr< ast::Type > newType = candidate->expr->result;
+                        assertf(candidate->expr->result, "Result of expression %p for candidate is null", candidate->expr.get());
+                        candidate->env.apply( newType );
+                        mangleName = Mangle::mangle( newType );
+                }
+
+                auto found = selected.find( mangleName );
+                if (found != selected.end() && found->second.candidate->cost < candidate->cost) {
+                        PRINT(
+                                std::cerr << "cost " << candidate->cost << " loses to "
+                                        << found->second.candidate->cost << std::endl;
+                        )
+                        continue;
+                }
+
+                // xxx - when do satisfyAssertions produce more than 1 result?
+                // this should only happen when initial result type contains
+                // unbound type parameters, then it should never be pruned by
+                // the previous step, since renameTyVars guarantees the mangled name
+                // is unique.
+                CandidateList satisfied;
+                satisfyAssertions(candidate, localSyms, satisfied, errors);
+
+                for (auto & newCand : satisfied) {
+                        // recomputes type key, if satisfyAssertions changed it
                         {
-                                ast::ptr< ast::Type > newType = candidate->expr->result;
-                                assertf(candidate->expr->result, "Result of expression %p for candidate is null", candidate->expr.get());
-                                candidate->env.apply( newType );
+                                ast::ptr< ast::Type > newType = newCand->expr->result;
+                                assertf(newCand->expr->result, "Result of expression %p for candidate is null", newCand->expr.get());
+                                newCand->env.apply( newType );
                                 mangleName = Mangle::mangle( newType );
                         }
-
                         auto found = selected.find( mangleName );
                         if ( found != selected.end() ) {
-                                if ( candidate->cost < found->second.candidate->cost ) {
+                                if ( newCand->cost < found->second.candidate->cost ) {
                                         PRINT(
-                                                std::cerr << "cost " << candidate->cost << " beats "
+                                                std::cerr << "cost " << newCand->cost << " beats "
                                                         << found->second.candidate->cost << std::endl;
                                         )
 
-                                        found->second = PruneStruct{ candidate };
-                                } else if ( candidate->cost == found->second.candidate->cost ) {
+                                        found->second = PruneStruct{ newCand };
+                                } else if ( newCand->cost == found->second.candidate->cost ) {
                                         // if one of the candidates contains a deleted identifier, can pick the other,
                                         // since deleted expressions should not be ambiguous if there is another option
                                         // that is at least as good
-                                        if ( findDeletedExpr( candidate->expr ) ) {
+                                        if ( findDeletedExpr( newCand->expr ) ) {
                                                 // do nothing
                                                 PRINT( std::cerr << "candidate is deleted" << std::endl; )
                                         } else if ( findDeletedExpr( found->second.candidate->expr ) ) {
                                                 PRINT( std::cerr << "current is deleted" << std::endl; )
-                                                found->second = PruneStruct{ candidate };
+                                                found->second = PruneStruct{ newCand };
                                         } else {
                                                 PRINT( std::cerr << "marking ambiguous" << std::endl; )
                                                 found->second.ambiguous = true;
                                         }
-                                } else {
+                                } else { 
+                                        // xxx - can satisfyAssertions increase the cost?
                                         PRINT(
-                                                std::cerr << "cost " << candidate->cost << " loses to "
+                                                std::cerr << "cost " << newCand->cost << " loses to "
                                                         << found->second.candidate->cost << std::endl;
-                                        )
+                                        )       
                                 }
                         } else {
-                                selected.emplace_hint( found, mangleName, candidate );
-                        }
-                }
-
-                // report unambiguous min-cost candidates
-                CandidateList out;
-                for ( auto & target : selected ) {
-                        if ( target.second.ambiguous ) continue;
-
-                        CandidateRef cand = target.second.candidate;
-
-                        ast::ptr< ast::Type > newResult = cand->expr->result;
-                        cand->env.applyFree( newResult );
-                        cand->expr = ast::mutate_field(
-                                cand->expr.get(), &ast::Expr::result, move( newResult ) );
-
-                        out.emplace_back( cand );
-                }
-                return out;
+                                selected.emplace_hint( found, mangleName, newCand );
+                        }
+                }
         }
 
-} // anonymous namespace
+        // report unambiguous min-cost candidates
+        // CandidateList out;
+        for ( auto & target : selected ) {
+                if ( target.second.ambiguous ) continue;
+
+                CandidateRef cand = target.second.candidate;
+
+                ast::ptr< ast::Type > newResult = cand->expr->result;
+                cand->env.applyFree( newResult );
+                cand->expr = ast::mutate_field(
+                        cand->expr.get(), &ast::Expr::result, move( newResult ) );
+
+                out.emplace_back( cand );
+        }
+        // if everything is lost in satisfyAssertions, report the error
+        return !selected.empty();
+}
 
 void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {
@@ -1739 +1770 @@
         }
 
+        /*
         if ( mode.satisfyAssns || mode.prune ) {
                 // trim candidates to just those where the assertions are satisfiable
@@ -1761 +1793 @@
                 candidates = move( satisfied );
         }
+        */
 
         if ( mode.prune ) {
@@ -1769 +1802 @@
                 )
 
-                CandidateList pruned = pruneCandidates( candidates );
+                CandidateList pruned;
+                std::vector<std::string> errors;
+                bool found = pruneCandidates( candidates, pruned, errors );
 
                 if ( mode.failFast && pruned.empty() ) {
                         std::ostringstream stream;
-                        CandidateList winners = findMinCost( candidates );
-                        stream << "Cannot choose between " << winners.size() << " alternatives for "
-                                "expression\n";
-                        ast::print( stream, expr );
-                        stream << " Alternatives are:\n";
-                        print( stream, winners, 1 );
-                        SemanticError( expr->location, stream.str() );
+                        if (found) {            
+                                CandidateList winners = findMinCost( candidates );
+                                stream << "Cannot choose between " << winners.size() << " alternatives for "
+                                        "expression\n";
+                                ast::print( stream, expr );
+                                stream << " Alternatives are:\n";
+                                print( stream, winners, 1 );
+                                SemanticError( expr->location, stream.str() );
+                        }
+                        else {
+                                stream << "No alternatives with satisfiable assertions for " << expr << "\n";
+                                for ( const auto& err : errors ) {
+                                        stream << err;
+                                }
+                                SemanticError( expr->location, stream.str() );
+                        }
                 }
 

src/ResolvExpr/CandidateFinder.hpp

@@ -40 +40 @@
         /// Fill candidates with feasible resolutions for `expr`
         void find( const ast::Expr * expr, ResolvMode mode = {} );
+        bool pruneCandidates( CandidateList & candidates, CandidateList & out, std::vector<std::string> & errors );
 
         /// Runs new candidate finder on each element in xs, returning the list of finders

src/ResolvExpr/ResolvMode.h

@@ -22 +22 @@
                 const bool prune;            ///< Prune alternatives to min-cost per return type? [true]
                 const bool failFast;         ///< Fail on no resulting alternatives? [true]
-                const bool satisfyAssns;     ///< Satisfy assertions? [false]
 
         private:
-                constexpr ResolvMode(bool a, bool p, bool ff, bool sa) 
-                : adjust(a), prune(p), failFast(ff), satisfyAssns(sa) {}
+                constexpr ResolvMode(bool a, bool p, bool ff) 
+                : adjust(a), prune(p), failFast(ff) {}
 
         public:
                 /// Default settings
-                constexpr ResolvMode() : adjust(false), prune(true), failFast(true), satisfyAssns(false) {}
+                constexpr ResolvMode() : adjust(false), prune(true), failFast(true) {}
                 
                 /// With adjust flag set; turns array and function types into equivalent pointers
-                static constexpr ResolvMode withAdjustment() { return { true, true, true, false }; }
+                static constexpr ResolvMode withAdjustment() { return { true, true, true }; }
 
                 /// With adjust flag set but prune unset; pruning ensures there is at least one alternative 
                 /// per result type
-                static constexpr ResolvMode withoutPrune() { return { true, false, true, false }; }
+                static constexpr ResolvMode withoutPrune() { return { true, false, true }; }
 
                 /// With adjust and prune flags set but failFast unset; failFast ensures there is at least 
                 /// one resulting alternative
-                static constexpr ResolvMode withoutFailFast() { return { true, true, false, false }; }
+                static constexpr ResolvMode withoutFailFast() { return { true, true, false }; }
 
                 /// The same mode, but with satisfyAssns turned on; for top-level calls
-                ResolvMode atTopLevel() const { return { adjust, prune, failFast, true }; }
+                ResolvMode atTopLevel() const { return { adjust, true, failFast }; }
         };
 } // namespace ResolvExpr

src/ResolvExpr/SatisfyAssertions.hpp

@@ -27 +27 @@
 namespace ResolvExpr {
 
-/// Recursively satisfies all assertions provided in a candidate; returns true if succeeds
+/// Recursively satisfies all assertions provided in a candidate
+/// returns true if it has been run (candidate has any assertions)
 void satisfyAssertions(
         CandidateRef & cand, const ast::SymbolTable & symtab, CandidateList & out,