coinselection: rewrite BnB in CoinGrinder-style

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 0d7b6603..6755376f 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -55,25 +55,19 @@ struct {
  * cost of creating and spending a change output. The algorithm uses a depth-first search on a binary
  * tree. In the binary tree, each node corresponds to the inclusion or the omission of a UTXO. UTXOs
  * are sorted by their effective values and the tree is explored deterministically per the inclusion
- * branch first. At each node, the algorithm checks whether the selection is within the target range.
+ * branch first. For each new input set candidate, the algorithm checks whether the selection is within the target range.
  * While the selection has not reached the target range, more UTXOs are included. When a selection's
  * value exceeds the target range, the complete subtree deriving from this selection can be omitted.
  * At that point, the last included UTXO is deselected and the corresponding omission branch explored
- * instead. The search ends after the complete tree has been searched or after a limited number of tries.
+ * instead starting by adding the subsequent UTXO. The search ends after the complete tree has been searched or after a limited number of tries.
  *
- * The search continues to search for better solutions after one solution has been found. The best
+ * The algorithm continues to search for better solutions after one solution has been found. The best
  * solution is chosen by minimizing the waste metric. The waste metric is defined as the cost to
  * spend the current inputs at the given fee rate minus the long term expected cost to spend the
  * inputs, plus the amount by which the selection exceeds the spending target:
  *
  * waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)
  *
- * The algorithm uses two additional optimizations. A lookahead keeps track of the total value of
- * the unexplored UTXOs. A subtree is not explored if the lookahead indicates that the target range
- * cannot be reached. Further, it is unnecessary to test equivalent combinations. This allows us
- * to skip testing the inclusion of UTXOs that match the effective value and waste of an omitted
- * predecessor.
- *
  * The Branch and Bound algorithm is described in detail in Murch's Master Thesis:
  * https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf
  *
@@ -93,114 +87,127 @@ static const size_t TOTAL_TRIES = 100000;
 util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change,
                                              int max_selection_weight)
 {
-    SelectionResult result(selection_target, SelectionAlgorithm::BNB);
-    CAmount curr_value = 0;
-    std::vector<size_t> curr_selection; // selected utxo indexes
-    int curr_selection_weight = 0; // sum of selected utxo weight
-
-    // Calculate curr_available_value
-    CAmount curr_available_value = 0;
+    // Check that there are sufficient funds
+    CAmount total_available = 0;
     for (const OutputGroup& utxo : utxo_pool) {
-        // Assert that this utxo is not negative. It should never be negative,
-        // effective value calculation should have removed it
-        assert(utxo.GetSelectionAmount() > 0);
-        curr_available_value += utxo.GetSelectionAmount();
+        // Assert UTXOs with non-positive effective value have been filtered
+        Assume(utxo.GetSelectionAmount() > 0);
+        total_available += utxo.GetSelectionAmount();
     }
-    if (curr_available_value < selection_target) {
+
+    if (total_available < selection_target) {
+        // Insufficient funds
         return util::Error();
     }
 
-    // Sort the utxo_pool
     std::sort(utxo_pool.begin(), utxo_pool.end(), descending);
 
-    CAmount curr_waste = 0;
+    // The current selection and the best input set found so far, stored as the utxo_pool indices of the UTXOs forming them
+    std::vector<size_t> curr_selection;
     std::vector<size_t> best_selection;
+
+    // The currently selected effective amount
+    CAmount curr_amount = 0;
+
+    // The waste score of the current selection, and the best waste score so far
+    CAmount curr_selection_waste = 0;
     CAmount best_waste = MAX_MONEY;
 
-    bool is_feerate_high = utxo_pool.at(0).fee > utxo_pool.at(0).long_term_fee;
+    // The weight of the currently selected input set
+    int curr_weight = 0;
+
+    // Whether the input sets generated during this search have exceeded the maximum transaction weight at any point
     bool max_tx_weight_exceeded = false;
 
-    // Depth First search loop for choosing the UTXOs
-    for (size_t curr_try = 0, utxo_pool_index = 0; curr_try < TOTAL_TRIES; ++curr_try, ++utxo_pool_index) {
-        result.SetSelectionsEvaluated(curr_try);
-        // Conditions for starting a backtrack
-        bool backtrack = false;
-        if (curr_value + curr_available_value < selection_target || // Cannot possibly reach target with the amount remaining in the curr_available_value.
-            curr_value > selection_target + cost_of_change || // Selected value is out of range, go back and try other branch
-            (curr_waste > best_waste && is_feerate_high)) { // Don't select things which we know will be more wasteful if the waste is increasing
-            backtrack = true;
-        } else if (curr_selection_weight > max_selection_weight) { // Selected UTXOs weight exceeds the maximum weight allowed, cannot find more solutions by adding more inputs
-            max_tx_weight_exceeded = true; // at least one selection attempt exceeded the max weight
-            backtrack = true;
-        } else if (curr_value >= selection_target) {       // Selected value is within range
-            curr_waste += (curr_value - selection_target); // This is the excess value which is added to the waste for the below comparison
-            // Adding another UTXO after this check could bring the waste down if the long term fee is higher than the current fee.
-            // However we are not going to explore that because this optimization for the waste is only done when we have hit our target
-            // value. Adding any more UTXOs will be just burning the UTXO; it will go entirely to fees. Thus we aren't going to
-            // explore any more UTXOs to avoid burning money like that.
+    // Index of the next UTXO to consider in utxo_pool
+    size_t next_utxo = 0;
+
+    auto deselect_last = [&]() {
+        OutputGroup& utxo = utxo_pool[curr_selection.back()];
+        curr_amount -= utxo.GetSelectionAmount();
+        curr_weight -= utxo.m_weight;
+        curr_selection_waste -= utxo.fee - utxo.long_term_fee;
+        curr_selection.pop_back();
+    };
+
+    size_t curr_try = 0;
+    while (true) {
+        bool should_shift{false}, should_cut{false};
+        // Select `next_utxo`
+        OutputGroup& utxo = utxo_pool[next_utxo];
+        curr_amount += utxo.GetSelectionAmount();
+        curr_weight += utxo.m_weight;
+        curr_selection_waste += utxo.fee - utxo.long_term_fee;
+        curr_selection.push_back(next_utxo);
+        ++next_utxo;
+        ++curr_try;
+
+        // EVALUATE current selection: check for solutions and see whether we can CUT or SHIFT before EXPLORING further
+        if (curr_weight > max_selection_weight) {
+            // max_weight exceeded: SHIFT
+            max_tx_weight_exceeded = true;
+            should_shift = true;
+        } else if (curr_amount > selection_target + cost_of_change) {
+            // Overshot target range: SHIFT
+            should_shift = true;
+        } else if (curr_amount >= selection_target) {
+            // Selection is within target window: potential solution
+            // Adding more UTXOs only increases fees and cannot be better: SHIFT
+            should_shift = true;
+            // The amount exceeding the selection_target (the "excess"), would be dropped to the fees: it is waste.
+            CAmount curr_excess = curr_amount - selection_target;
+            CAmount curr_waste = curr_selection_waste + curr_excess;
             if (curr_waste <= best_waste) {
+                // New best solution
                 best_selection = curr_selection;
                 best_waste = curr_waste;
             }
-            curr_waste -= (curr_value - selection_target); // Remove the excess value as we will be selecting different coins now
-            backtrack = true;
         }
 
-        if (backtrack) { // Backtracking, moving backwards
-            if (curr_selection.empty()) { // We have walked back to the first utxo and no branch is untraversed. All solutions searched
-                break;
-            }
+        if (curr_try >= TOTAL_TRIES) {
+            // Solution is not guaranteed to be optimal if `curr_try` hit TOTAL_TRIES
+            break;
+        }
 
-            // Add omitted UTXOs back to lookahead before traversing the omission branch of last included UTXO.
-            for (--utxo_pool_index; utxo_pool_index > curr_selection.back(); --utxo_pool_index) {
-                curr_available_value += utxo_pool.at(utxo_pool_index).GetSelectionAmount();
-            }
+        if (next_utxo == utxo_pool.size()) {
+            // Last added UTXO was end of UTXO pool, nothing left to add on inclusion or omission branch: CUT
+            should_cut = true;
+        }
 
-            // Output was included on previous iterations, try excluding now.
-            assert(utxo_pool_index == curr_selection.back());
-            OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
-            curr_value -= utxo.GetSelectionAmount();
-            curr_waste -= utxo.fee - utxo.long_term_fee;
-            curr_selection_weight -= utxo.m_weight;
-            curr_selection.pop_back();
-        } else { // Moving forwards, continuing down this branch
-            OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
-
-            // Remove this utxo from the curr_available_value utxo amount
-            curr_available_value -= utxo.GetSelectionAmount();
-
-            if (curr_selection.empty() ||
-                // The previous index is included and therefore not relevant for exclusion shortcut
-                (utxo_pool_index - 1) == curr_selection.back() ||
-                // Avoid searching a branch if the previous UTXO has the same value and same waste and was excluded.
-                // Since the ratio of fee to long term fee is the same, we only need to check if one of those values match in order to know that the waste is the same.
-                utxo.GetSelectionAmount() != utxo_pool.at(utxo_pool_index - 1).GetSelectionAmount() ||
-                utxo.fee != utxo_pool.at(utxo_pool_index - 1).fee)
-            {
-                // Inclusion branch first (Largest First Exploration)
-                curr_selection.push_back(utxo_pool_index);
-                curr_value += utxo.GetSelectionAmount();
-                curr_waste += utxo.fee - utxo.long_term_fee;
-                curr_selection_weight += utxo.m_weight;
+        if (should_cut) {
+            // Neither adding to the current selection nor exploring the omission branch of the last selected UTXO can
+            // find any solutions. Redirect to exploring the Omission branch of the penultimate selected UTXO (i.e.
+            // set `next_utxo` to one after the penultimate selected, then deselect the last two selected UTXOs)
+            deselect_last();
+            should_shift = true;
+        }
+
+        if (should_shift) {
+            if (curr_selection.empty()) {
+                // Exhausted search space before running into attempt limit
+                break;
             }
+            // Set `next_utxo` to one after last selected, then deselect last selected UTXO
+            next_utxo = curr_selection.back() + 1;
+            deselect_last();
         }
     }
 
-    // Check for solution
+    SelectionResult result(selection_target, SelectionAlgorithm::BNB);
+    result.SetSelectionsEvaluated(curr_try);
+
     if (best_selection.empty()) {
         return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();
     }
 
-    // Set output set
     for (const size_t& i : best_selection) {
         result.AddInput(utxo_pool.at(i));
     }
-    result.RecalculateWaste(cost_of_change, cost_of_change, CAmount{0});
-    assert(best_waste == result.GetWaste());
 
     return result;
 }
 
+
 /*
  * TL;DR: Coin Grinder is a DFS-based algorithm that deterministically searches for the minimum-weight input set to fund
  * the transaction. The algorithm is similar to the Branch and Bound algorithm, but will produce a transaction _with_ a
diff --git a/src/wallet/test/coinselection_tests.cpp b/src/wallet/test/coinselection_tests.cpp
index 2f982b74..05e36167 100644
--- a/src/wallet/test/coinselection_tests.cpp
+++ b/src/wallet/test/coinselection_tests.cpp
@@ -150,19 +150,19 @@ BOOST_AUTO_TEST_CASE(bnb_test)
         AddCoins(utxo_pool, {1 * CENT, 3 * CENT, 5 * CENT}, cs_params);
 
         // Simple success cases
-        TestBnBSuccess("Select smallest UTXO", utxo_pool, /*selection_target=*/1 * CENT, /*expected_input_amounts=*/{1 * CENT}, /*expected_attempts=*/6, cs_params);
-        TestBnBSuccess("Select middle UTXO", utxo_pool, /*selection_target=*/3 * CENT, /*expected_input_amounts=*/{3 * CENT}, /*expected_attempts=*/4, cs_params);
-        TestBnBSuccess("Select biggest UTXO", utxo_pool, /*selection_target=*/5 * CENT, /*expected_input_amounts=*/{5 * CENT}, /*expected_attempts=*/2, cs_params);
-        TestBnBSuccess("Select two UTXOs", utxo_pool, /*selection_target=*/4 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT}, /*expected_attempts=*/6, cs_params);
-        TestBnBSuccess("Select all UTXOs", utxo_pool, /*selection_target=*/9 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT, 5 * CENT}, /*expected_attempts=*/6, cs_params);
+        TestBnBSuccess("Select smallest UTXO", utxo_pool, /*selection_target=*/1 * CENT, /*expected_input_amounts=*/{1 * CENT}, /*expected_attempts=*/3, cs_params);
+        TestBnBSuccess("Select middle UTXO", utxo_pool, /*selection_target=*/3 * CENT, /*expected_input_amounts=*/{3 * CENT}, /*expected_attempts=*/3, cs_params);
+        TestBnBSuccess("Select biggest UTXO", utxo_pool, /*selection_target=*/5 * CENT, /*expected_input_amounts=*/{5 * CENT}, /*expected_attempts=*/4, cs_params);
+        TestBnBSuccess("Select two UTXOs", utxo_pool, /*selection_target=*/4 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT}, /*expected_attempts=*/4, cs_params);
+        TestBnBSuccess("Select all UTXOs", utxo_pool, /*selection_target=*/9 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT, 5 * CENT}, /*expected_attempts=*/7, cs_params);
 
         // BnB finds changeless solution while overshooting by up to cost_of_change
-        TestBnBSuccess("Select upper bound", utxo_pool, /*selection_target=*/4 * CENT - cs_params.m_cost_of_change, /*expected_input_amounts=*/{1 * CENT, 3 * CENT}, /*expected_attempts=*/6, cs_params);
+        TestBnBSuccess("Select upper bound", utxo_pool, /*selection_target=*/4 * CENT - cs_params.m_cost_of_change, /*expected_input_amounts=*/{1 * CENT, 3 * CENT}, /*expected_attempts=*/4, cs_params);
 
         // BnB fails to find changeless solution when overshooting by cost_of_change + 1 sat
         TestBnBFail("Overshoot upper bound", utxo_pool, /*selection_target=*/4 * CENT - cs_params.m_cost_of_change - 1, cs_params);
 
-        TestBnBSuccess("Select max weight", utxo_pool, /*selection_target=*/4 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT}, /*expected_attempts=*/6, cs_params, /*custom_spending_vsize=*/P2WPKH_INPUT_VSIZE, /*max_selection_weight=*/4 * 2 * P2WPKH_INPUT_VSIZE);
+        TestBnBSuccess("Select max weight", utxo_pool, /*selection_target=*/4 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT}, /*expected_attempts=*/4, cs_params, /*custom_spending_vsize=*/P2WPKH_INPUT_VSIZE, /*max_selection_weight=*/4 * 2 * P2WPKH_INPUT_VSIZE);
 
         TestBnBFail("Exceed max weight", utxo_pool, /*selection_target=*/4 * CENT, cs_params, /*max_selection_weight=*/4 * 2 * P2WPKH_INPUT_VSIZE - 1, /*expect_max_weight_exceeded=*/true);
 
@@ -175,7 +175,7 @@ BOOST_AUTO_TEST_CASE(bnb_test)
         std::vector<OutputGroup> clone_pool;
         AddCoins(clone_pool, {2 * CENT, 7 * CENT, 7 * CENT}, cs_params);
         AddDuplicateCoins(clone_pool, /*count=*/50'000, /*amount=*/5 * CENT, cs_params);
-        TestBnBSuccess("Skip equivalent input sets", clone_pool, /*selection_target=*/16 * CENT, /*expected_input_amounts=*/{2 * CENT, 7 * CENT, 7 * CENT}, /*expected_attempts=*/99'999, cs_params);
+        TestBnBSuccess("Skip equivalent input sets", clone_pool, /*selection_target=*/16 * CENT, /*expected_input_amounts=*/{2 * CENT, 7 * CENT, 7 * CENT}, /*expected_attempts=*/100'000, cs_params);
 
         /* Test BnB attempt limit (`TOTAL_TRIES`)
          *
@@ -208,7 +208,7 @@ BOOST_AUTO_TEST_CASE(bnb_test)
         }
         AddCoins(doppelganger_pool, doppelgangers, cs_params);
         // Among up to 17 unique UTXOs of similar effective value we will find a solution composed of the eight smallest UTXOs
-        TestBnBSuccess("Combine smallest 8 of 17 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT, /*expected_input_amounts=*/expected_inputs, /*expected_attempts=*/87'514, cs_params);
+        TestBnBSuccess("Combine smallest 8 of 17 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT, /*expected_input_amounts=*/expected_inputs, /*expected_attempts=*/65'535, cs_params);
 
         // Starting with 18 unique UTXOs of similar effective value we will not find the solution due to exceeding the attempt limit
         AddCoins(doppelganger_pool, {1 * CENT + cs_params.m_cost_of_change + 17}, cs_params);
@@ -226,7 +226,7 @@ BOOST_AUTO_TEST_CASE(bnb_feerate_sensitivity_test)
     const CoinSelectionParams high_feerate_params = init_cs_params(/*eff_feerate=*/25'000);
     std::vector<OutputGroup> high_feerate_pool; // 25 sat/vB (greater than long_term_feerate of 10 sat/vB)
     AddCoins(high_feerate_pool, {2 * CENT, 3 * CENT, 5 * CENT, 10 * CENT}, high_feerate_params);
-    TestBnBSuccess("Select one input at high feerates", high_feerate_pool, /*selection_target=*/10 * CENT, /*expected_input_amounts=*/{10 * CENT}, /*expected_attempts=*/6, high_feerate_params);
+    TestBnBSuccess("Select one input at high feerates", high_feerate_pool, /*selection_target=*/10 * CENT, /*expected_input_amounts=*/{10 * CENT}, /*expected_attempts=*/8, high_feerate_params);
 
     // Add heavy inputs {6, 7} to existing {2, 3, 5, 10}
     low_feerate_pool.push_back(MakeCoin(6 * CENT, true, default_cs_params, /*custom_spending_vsize=*/500));
@@ -235,7 +235,7 @@ BOOST_AUTO_TEST_CASE(bnb_feerate_sensitivity_test)
 
     high_feerate_pool.push_back(MakeCoin(6 * CENT, true, high_feerate_params, /*custom_spending_vsize=*/500));
     high_feerate_pool.push_back(MakeCoin(7 * CENT, true, high_feerate_params, /*custom_spending_vsize=*/500));
-    TestBnBSuccess("Prefer two light inputs over two heavy inputs at high feerates", high_feerate_pool, /*selection_target=*/13 * CENT, /*expected_input_amounts=*/{3 * CENT, 10 * CENT}, /*expected_attempts=*/14, high_feerate_params);
+    TestBnBSuccess("Prefer two light inputs over two heavy inputs at high feerates", high_feerate_pool, /*selection_target=*/13 * CENT, /*expected_input_amounts=*/{3 * CENT, 10 * CENT}, /*expected_attempts=*/28, high_feerate_params);
 }
 
 static void TestSRDSuccess(std::string test_title, std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CoinSelectionParams& cs_params = default_cs_params, const int max_selection_weight = MAX_STANDARD_TX_WEIGHT)
diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
index 2b8150c6..f393b473 100644
--- a/src/wallet/test/coinselector_tests.cpp
+++ b/src/wallet/test/coinselector_tests.cpp
@@ -209,7 +209,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
         const auto result9 = SelectCoinsBnB(GroupCoins(available_coins.All()), 1 * CENT, coin_selection_params_bnb.m_cost_of_change);
         BOOST_CHECK(result9);
         BOOST_CHECK_EQUAL(result9->GetSelectedValue(), 1 * CENT);
-        expected_attempts = 2;
+        expected_attempts = 1;
         BOOST_CHECK_MESSAGE(result9->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, result9->GetSelectionsEvaluated()));
     }
 
@@ -233,7 +233,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
         LOCK(wallet->cs_wallet);
         const auto result10 = SelectCoins(*wallet, available_coins, selected_input, 10 * CENT, coin_control, coin_selection_params_bnb);
         BOOST_CHECK(result10);
-        expected_attempts = 4;
+        expected_attempts = 3;
         BOOST_CHECK_MESSAGE(result10->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, result10->GetSelectionsEvaluated()));
     }
     {
@@ -264,7 +264,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
         available_coins.Erase({(++available_coins.coins[OutputType::BECH32].begin())->outpoint});
         const auto result13 = SelectCoins(*wallet, available_coins, selected_input, 10 * CENT, coin_control, coin_selection_params_bnb);
         BOOST_CHECK(EquivalentResult(expected_result, *result13));
-        expected_attempts = 4;
+        expected_attempts = 2;
         BOOST_CHECK_MESSAGE(result13->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, result13->GetSelectionsEvaluated()));
     }
 
@@ -297,7 +297,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
         add_coin(5 * CENT, 2, expected_result);
         add_coin(3 * CENT, 2, expected_result);
         BOOST_CHECK(EquivalentResult(expected_result, *res));
-        expected_attempts = 38;
+        expected_attempts = 39;
         BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));
     }
 }