Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision 4702a2cac45f6559d5d3404ee4ce0c09192620f3) +++ src/ResolvExpr/AlternativeFinder.cc (revision 13898103d95655f9105ab4f220516ac97d1cb04e) @@ -251,5 +251,5 @@ 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 Index: src/ResolvExpr/CandidateFinder.cpp =================================================================== --- src/ResolvExpr/CandidateFinder.cpp (revision 4702a2cac45f6559d5d3404ee4ce0c09192620f3) +++ src/ResolvExpr/CandidateFinder.cpp (revision 13898103d95655f9105ab4f220516ac97d1cb04e) @@ -1645,76 +1645,107 @@ /// 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 & 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,4 +1770,5 @@ } + /* if ( mode.satisfyAssns || mode.prune ) { // trim candidates to just those where the assertions are satisfiable @@ -1761,4 +1793,5 @@ candidates = move( satisfied ); } + */ if ( mode.prune ) { @@ -1769,15 +1802,26 @@ ) - CandidateList pruned = pruneCandidates( candidates ); + CandidateList pruned; + std::vector 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() ); + } } Index: src/ResolvExpr/CandidateFinder.hpp =================================================================== --- src/ResolvExpr/CandidateFinder.hpp (revision 4702a2cac45f6559d5d3404ee4ce0c09192620f3) +++ src/ResolvExpr/CandidateFinder.hpp (revision 13898103d95655f9105ab4f220516ac97d1cb04e) @@ -40,4 +40,5 @@ /// Fill candidates with feasible resolutions for `expr` void find( const ast::Expr * expr, ResolvMode mode = {} ); + bool pruneCandidates( CandidateList & candidates, CandidateList & out, std::vector & errors ); /// Runs new candidate finder on each element in xs, returning the list of finders Index: src/ResolvExpr/ResolvMode.h =================================================================== --- src/ResolvExpr/ResolvMode.h (revision 4702a2cac45f6559d5d3404ee4ce0c09192620f3) +++ src/ResolvExpr/ResolvMode.h (revision 13898103d95655f9105ab4f220516ac97d1cb04e) @@ -22,27 +22,26 @@ 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 Index: src/ResolvExpr/SatisfyAssertions.hpp =================================================================== --- src/ResolvExpr/SatisfyAssertions.hpp (revision 4702a2cac45f6559d5d3404ee4ce0c09192620f3) +++ src/ResolvExpr/SatisfyAssertions.hpp (revision 13898103d95655f9105ab4f220516ac97d1cb04e) @@ -27,5 +27,6 @@ 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,