test: Slay BnB Mutants

murchandamus commented at 11:02 pm on July 24, 2025: contributor

I tested all of the reported surviving mutants that @brunoerg reported in https://gist.github.com/brunoerg/834063398d5002f738506d741513e310.

I found that all Mutants except for 12, 14, 17, 37, and 39 were now being caught by one of the existing tests. This fixes Mutants 14, 37, and 39.

Mutant 17 is not fixed, because I consider it acceptable that running BnB for 100,001 instead of 100,000 comparisons doesn’t cause an issue, and Mutant 12 is not yet fixed, because at fee = long_term_fee, the waste of inputs is 0 and only excess matters, and I haven’t evaluated yet, whether it needs to be fixed.

DrahtBot commented at 11:02 pm on July 24, 2025: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/33060.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	achow101, jlest01, brunoerg
Concept ACK	w0xlt, yancyribbens

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#32150 (coinselection: Optimize BnB exploration by murchandamus)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

LLM Linter (✨ experimental)

Possible typos and grammar issues:

“The inputs size exceeds the maximum weight” → “The input size exceeds the maximum weight” [plural “inputs” here is incorrect]

drahtbot_id_4_m

achow101 marked this as a draft on Jul 24, 2025

w0xlt commented at 11:31 pm on July 24, 2025: contributor

Concept ACK

yancyribbens commented at 12:47 pm on July 25, 2025: contributor

Concept ACK. I recently found some of these by accident working on max-weight related projects.

test: Check max_weight_exceeded error

This slays the mutants 14 and 39 Bruno reported via
https://gist.github.com/brunoerg/834063398d5002f738506d741513e310,
that changing the intial or subsequent value of
`max_tx_weight_exceeded` in BnB would not fail any tests:

diff --git a/src/wallet/coinselection.cpp b/muts/coinselection.mutant.14.cpp
index cee558088f..947bf7b642 100644
--- a/src/wallet/coinselection.cpp
+++ b/muts/coinselection.mutant.14.cpp
@@ -118,7 +118,7 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool
     CAmount best_waste = MAX_MONEY;

     bool is_feerate_high = utxo_pool.at(0).fee > utxo_pool.at(0).long_term_fee;
-    bool max_tx_weight_exceeded = false;
+    bool max_tx_weight_exceeded = true;

     // 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) {

diff --git a/src/wallet/coinselection.cpp b/muts/coinselection.mutant.39.cpp
index cee558088f..bbfdc23889 100644
--- a/src/wallet/coinselection.cpp
+++ b/muts/coinselection.mutant.39.cpp
@@ -129,7 +129,7 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool
             (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
+            max_tx_weight_exceeded = false; // 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

57fe8acc8a

test: Test max_selection_weight edge cases

Slays Mutant 37 from Bruno’s report:
https://gist.github.com/brunoerg/834063398d5002f738506d741513e310

diff --git a/src/wallet/coinselection.cpp b/muts/coinselection.mutant.37.cpp
index cee558088f..9747cd26c9 100644
--- a/src/wallet/coinselection.cpp
+++ b/muts/coinselection.mutant.37.cpp
@@ -128,7 +128,7 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool
             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
+        } 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

a3cf623364

murchandamus force-pushed on Jul 25, 2025

murchandamus marked this as ready for review on Jul 25, 2025

murchandamus renamed this:
~~Slay BnB Mutants~~
test: Slay BnB Mutants
on Jul 25, 2025

DrahtBot added the label Tests on Jul 25, 2025