Changeset 1389810


Ignore:
Timestamp:
Nov 26, 2020, 6:52:03 PM (10 months ago)
Author:
Fangren Yu <f37yu@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast-unique-expr
Children:
88a0ff6
Parents:
4702a2c
Message:

consolidate prune and satisfy assertion

Location:
src/ResolvExpr
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • src/ResolvExpr/AlternativeFinder.cc

    r4702a2c r1389810  
    251251                        SemanticError( expr, "No reasonable alternatives for expression " );
    252252                }
    253                 if ( mode.satisfyAssns || mode.prune ) {
     253                if ( mode.prune ) {
    254254                        // trim candidates just to those where the assertions resolve
    255255                        // - necessary pre-requisite to pruning
  • src/ResolvExpr/CandidateFinder.cpp

    r4702a2c r1389810  
    16451645        /// Prunes a list of candidates down to those that have the minimum conversion cost for a given
    16461646        /// return type. Skips ambiguous candidates.
    1647         CandidateList pruneCandidates( CandidateList & candidates ) {
    1648                 struct PruneStruct {
    1649                         CandidateRef candidate;
    1650                         bool ambiguous;
    1651 
    1652                         PruneStruct() = default;
    1653                         PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}
    1654                 };
    1655 
    1656                 // find lowest-cost candidate for each type
    1657                 std::unordered_map< std::string, PruneStruct > selected;
    1658                 for ( CandidateRef & candidate : candidates ) {
    1659                         std::string mangleName;
     1647
     1648} // anonymous namespace
     1649
     1650bool CandidateFinder::pruneCandidates( CandidateList & candidates, CandidateList & out, std::vector<std::string> & errors ) {
     1651        struct PruneStruct {
     1652                CandidateRef candidate;
     1653                bool ambiguous;
     1654
     1655                PruneStruct() = default;
     1656                PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}
     1657        };
     1658
     1659        // find lowest-cost candidate for each type
     1660        std::unordered_map< std::string, PruneStruct > selected;
     1661        // attempt to skip satisfyAssertions on more expensive alternatives if better options have been found
     1662        std::sort(candidates.begin(), candidates.end(), [](const CandidateRef & x, const CandidateRef & y){return x->cost < y->cost;});
     1663        for ( CandidateRef & candidate : candidates ) {
     1664                std::string mangleName;
     1665                {
     1666                        ast::ptr< ast::Type > newType = candidate->expr->result;
     1667                        assertf(candidate->expr->result, "Result of expression %p for candidate is null", candidate->expr.get());
     1668                        candidate->env.apply( newType );
     1669                        mangleName = Mangle::mangle( newType );
     1670                }
     1671
     1672                auto found = selected.find( mangleName );
     1673                if (found != selected.end() && found->second.candidate->cost < candidate->cost) {
     1674                        PRINT(
     1675                                std::cerr << "cost " << candidate->cost << " loses to "
     1676                                        << found->second.candidate->cost << std::endl;
     1677                        )
     1678                        continue;
     1679                }
     1680
     1681                // xxx - when do satisfyAssertions produce more than 1 result?
     1682                // this should only happen when initial result type contains
     1683                // unbound type parameters, then it should never be pruned by
     1684                // the previous step, since renameTyVars guarantees the mangled name
     1685                // is unique.
     1686                CandidateList satisfied;
     1687                satisfyAssertions(candidate, localSyms, satisfied, errors);
     1688
     1689                for (auto & newCand : satisfied) {
     1690                        // recomputes type key, if satisfyAssertions changed it
    16601691                        {
    1661                                 ast::ptr< ast::Type > newType = candidate->expr->result;
    1662                                 assertf(candidate->expr->result, "Result of expression %p for candidate is null", candidate->expr.get());
    1663                                 candidate->env.apply( newType );
     1692                                ast::ptr< ast::Type > newType = newCand->expr->result;
     1693                                assertf(newCand->expr->result, "Result of expression %p for candidate is null", newCand->expr.get());
     1694                                newCand->env.apply( newType );
    16641695                                mangleName = Mangle::mangle( newType );
    16651696                        }
    1666 
    16671697                        auto found = selected.find( mangleName );
    16681698                        if ( found != selected.end() ) {
    1669                                 if ( candidate->cost < found->second.candidate->cost ) {
     1699                                if ( newCand->cost < found->second.candidate->cost ) {
    16701700                                        PRINT(
    1671                                                 std::cerr << "cost " << candidate->cost << " beats "
     1701                                                std::cerr << "cost " << newCand->cost << " beats "
    16721702                                                        << found->second.candidate->cost << std::endl;
    16731703                                        )
    16741704
    1675                                         found->second = PruneStruct{ candidate };
    1676                                 } else if ( candidate->cost == found->second.candidate->cost ) {
     1705                                        found->second = PruneStruct{ newCand };
     1706                                } else if ( newCand->cost == found->second.candidate->cost ) {
    16771707                                        // if one of the candidates contains a deleted identifier, can pick the other,
    16781708                                        // since deleted expressions should not be ambiguous if there is another option
    16791709                                        // that is at least as good
    1680                                         if ( findDeletedExpr( candidate->expr ) ) {
     1710                                        if ( findDeletedExpr( newCand->expr ) ) {
    16811711                                                // do nothing
    16821712                                                PRINT( std::cerr << "candidate is deleted" << std::endl; )
    16831713                                        } else if ( findDeletedExpr( found->second.candidate->expr ) ) {
    16841714                                                PRINT( std::cerr << "current is deleted" << std::endl; )
    1685                                                 found->second = PruneStruct{ candidate };
     1715                                                found->second = PruneStruct{ newCand };
    16861716                                        } else {
    16871717                                                PRINT( std::cerr << "marking ambiguous" << std::endl; )
    16881718                                                found->second.ambiguous = true;
    16891719                                        }
    1690                                 } else {
     1720                                } else {
     1721                                        // xxx - can satisfyAssertions increase the cost?
    16911722                                        PRINT(
    1692                                                 std::cerr << "cost " << candidate->cost << " loses to "
     1723                                                std::cerr << "cost " << newCand->cost << " loses to "
    16931724                                                        << found->second.candidate->cost << std::endl;
    1694                                         )
     1725                                        )       
    16951726                                }
    16961727                        } else {
    1697                                 selected.emplace_hint( found, mangleName, candidate );
    1698                         }
    1699                 }
    1700 
    1701                 // report unambiguous min-cost candidates
    1702                 CandidateList out;
    1703                 for ( auto & target : selected ) {
    1704                         if ( target.second.ambiguous ) continue;
    1705 
    1706                         CandidateRef cand = target.second.candidate;
    1707 
    1708                         ast::ptr< ast::Type > newResult = cand->expr->result;
    1709                         cand->env.applyFree( newResult );
    1710                         cand->expr = ast::mutate_field(
    1711                                 cand->expr.get(), &ast::Expr::result, move( newResult ) );
    1712 
    1713                         out.emplace_back( cand );
    1714                 }
    1715                 return out;
     1728                                selected.emplace_hint( found, mangleName, newCand );
     1729                        }
     1730                }
    17161731        }
    17171732
    1718 } // anonymous namespace
     1733        // report unambiguous min-cost candidates
     1734        // CandidateList out;
     1735        for ( auto & target : selected ) {
     1736                if ( target.second.ambiguous ) continue;
     1737
     1738                CandidateRef cand = target.second.candidate;
     1739
     1740                ast::ptr< ast::Type > newResult = cand->expr->result;
     1741                cand->env.applyFree( newResult );
     1742                cand->expr = ast::mutate_field(
     1743                        cand->expr.get(), &ast::Expr::result, move( newResult ) );
     1744
     1745                out.emplace_back( cand );
     1746        }
     1747        // if everything is lost in satisfyAssertions, report the error
     1748        return !selected.empty();
     1749}
    17191750
    17201751void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {
     
    17391770        }
    17401771
     1772        /*
    17411773        if ( mode.satisfyAssns || mode.prune ) {
    17421774                // trim candidates to just those where the assertions are satisfiable
     
    17611793                candidates = move( satisfied );
    17621794        }
     1795        */
    17631796
    17641797        if ( mode.prune ) {
     
    17691802                )
    17701803
    1771                 CandidateList pruned = pruneCandidates( candidates );
     1804                CandidateList pruned;
     1805                std::vector<std::string> errors;
     1806                bool found = pruneCandidates( candidates, pruned, errors );
    17721807
    17731808                if ( mode.failFast && pruned.empty() ) {
    17741809                        std::ostringstream stream;
    1775                         CandidateList winners = findMinCost( candidates );
    1776                         stream << "Cannot choose between " << winners.size() << " alternatives for "
    1777                                 "expression\n";
    1778                         ast::print( stream, expr );
    1779                         stream << " Alternatives are:\n";
    1780                         print( stream, winners, 1 );
    1781                         SemanticError( expr->location, stream.str() );
     1810                        if (found) {           
     1811                                CandidateList winners = findMinCost( candidates );
     1812                                stream << "Cannot choose between " << winners.size() << " alternatives for "
     1813                                        "expression\n";
     1814                                ast::print( stream, expr );
     1815                                stream << " Alternatives are:\n";
     1816                                print( stream, winners, 1 );
     1817                                SemanticError( expr->location, stream.str() );
     1818                        }
     1819                        else {
     1820                                stream << "No alternatives with satisfiable assertions for " << expr << "\n";
     1821                                for ( const auto& err : errors ) {
     1822                                        stream << err;
     1823                                }
     1824                                SemanticError( expr->location, stream.str() );
     1825                        }
    17821826                }
    17831827
  • src/ResolvExpr/CandidateFinder.hpp

    r4702a2c r1389810  
    4040        /// Fill candidates with feasible resolutions for `expr`
    4141        void find( const ast::Expr * expr, ResolvMode mode = {} );
     42        bool pruneCandidates( CandidateList & candidates, CandidateList & out, std::vector<std::string> & errors );
    4243
    4344        /// Runs new candidate finder on each element in xs, returning the list of finders
  • src/ResolvExpr/ResolvMode.h

    r4702a2c r1389810  
    2222                const bool prune;            ///< Prune alternatives to min-cost per return type? [true]
    2323                const bool failFast;         ///< Fail on no resulting alternatives? [true]
    24                 const bool satisfyAssns;     ///< Satisfy assertions? [false]
    2524
    2625        private:
    27                 constexpr ResolvMode(bool a, bool p, bool ff, bool sa)
    28                 : adjust(a), prune(p), failFast(ff), satisfyAssns(sa) {}
     26                constexpr ResolvMode(bool a, bool p, bool ff)
     27                : adjust(a), prune(p), failFast(ff) {}
    2928
    3029        public:
    3130                /// Default settings
    32                 constexpr ResolvMode() : adjust(false), prune(true), failFast(true), satisfyAssns(false) {}
     31                constexpr ResolvMode() : adjust(false), prune(true), failFast(true) {}
    3332               
    3433                /// With adjust flag set; turns array and function types into equivalent pointers
    35                 static constexpr ResolvMode withAdjustment() { return { true, true, true, false }; }
     34                static constexpr ResolvMode withAdjustment() { return { true, true, true }; }
    3635
    3736                /// With adjust flag set but prune unset; pruning ensures there is at least one alternative
    3837                /// per result type
    39                 static constexpr ResolvMode withoutPrune() { return { true, false, true, false }; }
     38                static constexpr ResolvMode withoutPrune() { return { true, false, true }; }
    4039
    4140                /// With adjust and prune flags set but failFast unset; failFast ensures there is at least
    4241                /// one resulting alternative
    43                 static constexpr ResolvMode withoutFailFast() { return { true, true, false, false }; }
     42                static constexpr ResolvMode withoutFailFast() { return { true, true, false }; }
    4443
    4544                /// The same mode, but with satisfyAssns turned on; for top-level calls
    46                 ResolvMode atTopLevel() const { return { adjust, prune, failFast, true }; }
     45                ResolvMode atTopLevel() const { return { adjust, true, failFast }; }
    4746        };
    4847} // namespace ResolvExpr
  • src/ResolvExpr/SatisfyAssertions.hpp

    r4702a2c r1389810  
    2727namespace ResolvExpr {
    2828
    29 /// Recursively satisfies all assertions provided in a candidate; returns true if succeeds
     29/// Recursively satisfies all assertions provided in a candidate
     30/// returns true if it has been run (candidate has any assertions)
    3031void satisfyAssertions(
    3132        CandidateRef & cand, const ast::SymbolTable & symtab, CandidateList & out,
Note: See TracChangeset for help on using the changeset viewer.