- Timestamp:
- Nov 26, 2020, 6:52:03 PM (4 years ago)
- 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
- Location:
- src/ResolvExpr
- Files:
-
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/AlternativeFinder.cc
r4702a2c r1389810 251 251 SemanticError( expr, "No reasonable alternatives for expression " ); 252 252 } 253 if ( mode. satisfyAssns || mode.prune ) {253 if ( mode.prune ) { 254 254 // trim candidates just to those where the assertions resolve 255 255 // - necessary pre-requisite to pruning -
src/ResolvExpr/CandidateFinder.cpp
r4702a2c r1389810 1645 1645 /// Prunes a list of candidates down to those that have the minimum conversion cost for a given 1646 1646 /// 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 1650 bool 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 1660 1691 { 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 ); 1664 1695 mangleName = Mangle::mangle( newType ); 1665 1696 } 1666 1667 1697 auto found = selected.find( mangleName ); 1668 1698 if ( found != selected.end() ) { 1669 if ( candidate->cost < found->second.candidate->cost ) {1699 if ( newCand->cost < found->second.candidate->cost ) { 1670 1700 PRINT( 1671 std::cerr << "cost " << candidate->cost << " beats "1701 std::cerr << "cost " << newCand->cost << " beats " 1672 1702 << found->second.candidate->cost << std::endl; 1673 1703 ) 1674 1704 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 ) { 1677 1707 // if one of the candidates contains a deleted identifier, can pick the other, 1678 1708 // since deleted expressions should not be ambiguous if there is another option 1679 1709 // that is at least as good 1680 if ( findDeletedExpr( candidate->expr ) ) {1710 if ( findDeletedExpr( newCand->expr ) ) { 1681 1711 // do nothing 1682 1712 PRINT( std::cerr << "candidate is deleted" << std::endl; ) 1683 1713 } else if ( findDeletedExpr( found->second.candidate->expr ) ) { 1684 1714 PRINT( std::cerr << "current is deleted" << std::endl; ) 1685 found->second = PruneStruct{ candidate};1715 found->second = PruneStruct{ newCand }; 1686 1716 } else { 1687 1717 PRINT( std::cerr << "marking ambiguous" << std::endl; ) 1688 1718 found->second.ambiguous = true; 1689 1719 } 1690 } else { 1720 } else { 1721 // xxx - can satisfyAssertions increase the cost? 1691 1722 PRINT( 1692 std::cerr << "cost " << candidate->cost << " loses to "1723 std::cerr << "cost " << newCand->cost << " loses to " 1693 1724 << found->second.candidate->cost << std::endl; 1694 ) 1725 ) 1695 1726 } 1696 1727 } 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 } 1716 1731 } 1717 1732 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 } 1719 1750 1720 1751 void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) { … … 1739 1770 } 1740 1771 1772 /* 1741 1773 if ( mode.satisfyAssns || mode.prune ) { 1742 1774 // trim candidates to just those where the assertions are satisfiable … … 1761 1793 candidates = move( satisfied ); 1762 1794 } 1795 */ 1763 1796 1764 1797 if ( mode.prune ) { … … 1769 1802 ) 1770 1803 1771 CandidateList pruned = pruneCandidates( candidates ); 1804 CandidateList pruned; 1805 std::vector<std::string> errors; 1806 bool found = pruneCandidates( candidates, pruned, errors ); 1772 1807 1773 1808 if ( mode.failFast && pruned.empty() ) { 1774 1809 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 } 1782 1826 } 1783 1827 -
src/ResolvExpr/CandidateFinder.hpp
r4702a2c r1389810 40 40 /// Fill candidates with feasible resolutions for `expr` 41 41 void find( const ast::Expr * expr, ResolvMode mode = {} ); 42 bool pruneCandidates( CandidateList & candidates, CandidateList & out, std::vector<std::string> & errors ); 42 43 43 44 /// Runs new candidate finder on each element in xs, returning the list of finders -
src/ResolvExpr/ResolvMode.h
r4702a2c r1389810 22 22 const bool prune; ///< Prune alternatives to min-cost per return type? [true] 23 23 const bool failFast; ///< Fail on no resulting alternatives? [true] 24 const bool satisfyAssns; ///< Satisfy assertions? [false]25 24 26 25 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) {} 29 28 30 29 public: 31 30 /// Default settings 32 constexpr ResolvMode() : adjust(false), prune(true), failFast(true) , satisfyAssns(false){}31 constexpr ResolvMode() : adjust(false), prune(true), failFast(true) {} 33 32 34 33 /// 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 }; } 36 35 37 36 /// With adjust flag set but prune unset; pruning ensures there is at least one alternative 38 37 /// per result type 39 static constexpr ResolvMode withoutPrune() { return { true, false, true , false}; }38 static constexpr ResolvMode withoutPrune() { return { true, false, true }; } 40 39 41 40 /// With adjust and prune flags set but failFast unset; failFast ensures there is at least 42 41 /// one resulting alternative 43 static constexpr ResolvMode withoutFailFast() { return { true, true, false , false}; }42 static constexpr ResolvMode withoutFailFast() { return { true, true, false }; } 44 43 45 44 /// 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 }; } 47 46 }; 48 47 } // namespace ResolvExpr -
src/ResolvExpr/SatisfyAssertions.hpp
r4702a2c r1389810 27 27 namespace ResolvExpr { 28 28 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) 30 31 void satisfyAssertions( 31 32 CandidateRef & cand, const ast::SymbolTable & symtab, CandidateList & out,
Note: See TracChangeset
for help on using the changeset viewer.