Changeset 4432b52 for src/ResolvExpr/CandidateFinder.cpp
- Timestamp:
- Nov 27, 2020, 9:08:28 AM (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:
- 4f0c520
- Parents:
- 1f9a4d0 (diff), e3282fe (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)
links above to see all the changes relative to each parent. - File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/CandidateFinder.cpp
r1f9a4d0 r4432b52 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 bool needRecomputeKey = false; 1688 if (candidate->need.empty()) { 1689 satisfied.emplace_back(candidate); 1690 } 1691 else { 1692 satisfyAssertions(candidate, localSyms, satisfied, errors); 1693 needRecomputeKey = true; 1694 } 1695 1696 for (auto & newCand : satisfied) { 1697 // recomputes type key, if satisfyAssertions changed it 1698 if (needRecomputeKey) 1660 1699 { 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 );1700 ast::ptr< ast::Type > newType = newCand->expr->result; 1701 assertf(newCand->expr->result, "Result of expression %p for candidate is null", newCand->expr.get()); 1702 newCand->env.apply( newType ); 1664 1703 mangleName = Mangle::mangle( newType ); 1665 1704 } 1666 1667 1705 auto found = selected.find( mangleName ); 1668 1706 if ( found != selected.end() ) { 1669 if ( candidate->cost < found->second.candidate->cost ) {1707 if ( newCand->cost < found->second.candidate->cost ) { 1670 1708 PRINT( 1671 std::cerr << "cost " << candidate->cost << " beats "1709 std::cerr << "cost " << newCand->cost << " beats " 1672 1710 << found->second.candidate->cost << std::endl; 1673 1711 ) 1674 1712 1675 found->second = PruneStruct{ candidate};1676 } else if ( candidate->cost == found->second.candidate->cost ) {1713 found->second = PruneStruct{ newCand }; 1714 } else if ( newCand->cost == found->second.candidate->cost ) { 1677 1715 // if one of the candidates contains a deleted identifier, can pick the other, 1678 1716 // since deleted expressions should not be ambiguous if there is another option 1679 1717 // that is at least as good 1680 if ( findDeletedExpr( candidate->expr ) ) {1718 if ( findDeletedExpr( newCand->expr ) ) { 1681 1719 // do nothing 1682 1720 PRINT( std::cerr << "candidate is deleted" << std::endl; ) 1683 1721 } else if ( findDeletedExpr( found->second.candidate->expr ) ) { 1684 1722 PRINT( std::cerr << "current is deleted" << std::endl; ) 1685 found->second = PruneStruct{ candidate};1723 found->second = PruneStruct{ newCand }; 1686 1724 } else { 1687 1725 PRINT( std::cerr << "marking ambiguous" << std::endl; ) 1688 1726 found->second.ambiguous = true; 1689 1727 } 1690 } else { 1728 } else { 1729 // xxx - can satisfyAssertions increase the cost? 1691 1730 PRINT( 1692 std::cerr << "cost " << candidate->cost << " loses to "1731 std::cerr << "cost " << newCand->cost << " loses to " 1693 1732 << found->second.candidate->cost << std::endl; 1694 ) 1733 ) 1695 1734 } 1696 1735 } 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; 1736 selected.emplace_hint( found, mangleName, newCand ); 1737 } 1738 } 1716 1739 } 1717 1740 1718 } // anonymous namespace 1741 // report unambiguous min-cost candidates 1742 // CandidateList out; 1743 for ( auto & target : selected ) { 1744 if ( target.second.ambiguous ) continue; 1745 1746 CandidateRef cand = target.second.candidate; 1747 1748 ast::ptr< ast::Type > newResult = cand->expr->result; 1749 cand->env.applyFree( newResult ); 1750 cand->expr = ast::mutate_field( 1751 cand->expr.get(), &ast::Expr::result, move( newResult ) ); 1752 1753 out.emplace_back( cand ); 1754 } 1755 // if everything is lost in satisfyAssertions, report the error 1756 return !selected.empty(); 1757 } 1719 1758 1720 1759 void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) { … … 1739 1778 } 1740 1779 1780 /* 1741 1781 if ( mode.satisfyAssns || mode.prune ) { 1742 1782 // trim candidates to just those where the assertions are satisfiable … … 1761 1801 candidates = move( satisfied ); 1762 1802 } 1803 */ 1763 1804 1764 1805 if ( mode.prune ) { … … 1769 1810 ) 1770 1811 1771 CandidateList pruned = pruneCandidates( candidates ); 1812 CandidateList pruned; 1813 std::vector<std::string> errors; 1814 bool found = pruneCandidates( candidates, pruned, errors ); 1772 1815 1773 1816 if ( mode.failFast && pruned.empty() ) { 1774 1817 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() ); 1818 if (found) { 1819 CandidateList winners = findMinCost( candidates ); 1820 stream << "Cannot choose between " << winners.size() << " alternatives for " 1821 "expression\n"; 1822 ast::print( stream, expr ); 1823 stream << " Alternatives are:\n"; 1824 print( stream, winners, 1 ); 1825 SemanticError( expr->location, stream.str() ); 1826 } 1827 else { 1828 stream << "No alternatives with satisfiable assertions for " << expr << "\n"; 1829 for ( const auto& err : errors ) { 1830 stream << err; 1831 } 1832 SemanticError( expr->location, stream.str() ); 1833 } 1782 1834 } 1783 1835
Note: See TracChangeset
for help on using the changeset viewer.