Ignore:
Timestamp:
Nov 27, 2020, 9:08:28 AM (4 years ago)
Author:
Peter A. Buhr <pabuhr@…>
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.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/ResolvExpr/CandidateFinder.cpp

    r1f9a4d0 r4432b52  
    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                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)
    16601699                        {
    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 );
    16641703                                mangleName = Mangle::mangle( newType );
    16651704                        }
    1666 
    16671705                        auto found = selected.find( mangleName );
    16681706                        if ( found != selected.end() ) {
    1669                                 if ( candidate->cost < found->second.candidate->cost ) {
     1707                                if ( newCand->cost < found->second.candidate->cost ) {
    16701708                                        PRINT(
    1671                                                 std::cerr << "cost " << candidate->cost << " beats "
     1709                                                std::cerr << "cost " << newCand->cost << " beats "
    16721710                                                        << found->second.candidate->cost << std::endl;
    16731711                                        )
    16741712
    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 ) {
    16771715                                        // if one of the candidates contains a deleted identifier, can pick the other,
    16781716                                        // since deleted expressions should not be ambiguous if there is another option
    16791717                                        // that is at least as good
    1680                                         if ( findDeletedExpr( candidate->expr ) ) {
     1718                                        if ( findDeletedExpr( newCand->expr ) ) {
    16811719                                                // do nothing
    16821720                                                PRINT( std::cerr << "candidate is deleted" << std::endl; )
    16831721                                        } else if ( findDeletedExpr( found->second.candidate->expr ) ) {
    16841722                                                PRINT( std::cerr << "current is deleted" << std::endl; )
    1685                                                 found->second = PruneStruct{ candidate };
     1723                                                found->second = PruneStruct{ newCand };
    16861724                                        } else {
    16871725                                                PRINT( std::cerr << "marking ambiguous" << std::endl; )
    16881726                                                found->second.ambiguous = true;
    16891727                                        }
    1690                                 } else {
     1728                                } else {
     1729                                        // xxx - can satisfyAssertions increase the cost?
    16911730                                        PRINT(
    1692                                                 std::cerr << "cost " << candidate->cost << " loses to "
     1731                                                std::cerr << "cost " << newCand->cost << " loses to "
    16931732                                                        << found->second.candidate->cost << std::endl;
    1694                                         )
     1733                                        )       
    16951734                                }
    16961735                        } 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                }
    17161739        }
    17171740
    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}
    17191758
    17201759void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {
     
    17391778        }
    17401779
     1780        /*
    17411781        if ( mode.satisfyAssns || mode.prune ) {
    17421782                // trim candidates to just those where the assertions are satisfiable
     
    17611801                candidates = move( satisfied );
    17621802        }
     1803        */
    17631804
    17641805        if ( mode.prune ) {
     
    17691810                )
    17701811
    1771                 CandidateList pruned = pruneCandidates( candidates );
     1812                CandidateList pruned;
     1813                std::vector<std::string> errors;
     1814                bool found = pruneCandidates( candidates, pruned, errors );
    17721815
    17731816                if ( mode.failFast && pruned.empty() ) {
    17741817                        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                        }
    17821834                }
    17831835
Note: See TracChangeset for help on using the changeset viewer.