test: add case where `TOTAL_TRIES` is exceeded yet solution remains

yancyribbens commented at 0:30 am on October 25, 2025: contributor

Show that CoinGrider halts searching when the number of attempts exceeds TOTAL_TRIES. To do so, show that a solution is found, then add one more entry to the same set of inputs. Since the search orders by effective_value, the solution is constructed such that only values with the lowest effective_value have the least weight. Only the lowest weight values will not exceed the max_selection_weight. Therefore, CoinGrinder will not evaluate all lowest weight solutions together before exceeding TOTAL_TRIES since they are last found.

This test case was inspired by a similar test for BnB currently named bnb_test.

DrahtBot added the label Tests on Oct 25, 2025

DrahtBot commented at 0:30 am on October 25, 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/33701.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	frankomosh
Concept ACK	alvroble

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

yancyribbens commented at 0:30 am on October 25, 2025: contributor

closes https://github.com/bitcoin/bitcoin/issues/33419

in src/wallet/test/coinselector_tests.cpp:1161 in 922345de3f outdated

1156+        // #################################################################################################################
1157+        CAmount target =  8 * COIN;
1158+        int max_selection_weight = 3200; // WU
1159+        dummy_params.m_min_change_target = 0;
1160+        const auto& result_a = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) {
1161+            CoinsResult doppelgangers;

alvroble commented at 11:37 am on October 25, 2025:

Maybe it’d be better to use res_a/res_b instead of result_a/result_b and available_coins instead of doppelgangers for naming consistency.

yancyribbens commented at 1:26 pm on October 25, 2025:

Thanks for taking a look. The name doppelgangers comes from a similar test for BnB: https://github.com/bitcoin/bitcoin/blob/e744fd1249bf9577274614eaf3997bf4bbb612ff/src/wallet/test/coinselection_tests.cpp#L166.

I’m impartial on res_a vs result_a. I couldn’t name it just res because there would be multiple assignments to res which the compiler complains about.

alvroble commented at 11:42 am on October 25, 2025: none

Hey, I’m new to this project. So just learning. Ran the tests and they were not broken, and I agree with the rationale. Concept ACK.

in src/wallet/test/coinselector_tests.cpp:1180 in 922345de3f

1175+        BOOST_CHECK_MESSAGE(result_a->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, result_a->GetSelectionsEvaluated()));
1176+
1177+        // Adding one more doppelganger causes the attempt limit to be reached before finding a solution.
1178+        const auto& result_b = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) {
1179+            CoinsResult doppelgangers;
1180+            add_coin(doppelgangers, wallet, CAmount(1 * COIN + 18), CFeeRate(0), 144, false, 0, true, 114);

frankomosh commented at 2:14 pm on November 4, 2025:

Only 1 coin is created (~1 BTC), but the target is 8 BTC. So my superficial thought is that result_b might never reach the target, therefore, the resulting failure would not be because of TOTAL_TRIES being hit, but simply insufficient funds. Or might I be missing some context here?

yancyribbens commented at 8:37 pm on November 5, 2025:

Ey thanks for catching that! I updated the test so that it re-populates the doppelgangers array. It’s tricky that the api doesn’t return a different result when the TOTAL_TRIES is exceeded.

I maintain a rust version of coin-grinder, and I added a test that is the same as here: https://github.com/p2pderivatives/rust-bitcoin-coin-selection/commit/a0e033b67ba20139472075a9fc428a1a81c357e7 . You’ll notice in the rust version, one can actually assert expected_error: Some(IterationLimitReached). Would be nice if there was an implementation of this idea here as well..

frankomosh commented at 2:10 pm on November 7, 2025:

It’s tricky that the api doesn’t return a different result when the TOTAL_TRIES is exceeded.

What if you add

BOOST_CHECK(result_b->GetAlgoCompleted() == false); right after the BOOST_CHECK(!result_b);.

I guess that might prove TOTAL_TRIES has been hit, instead of failing for any other reason. It obviously doesn’t give a typed error enum(like the rust version), but I guess it is the best that can be done with the current C++ API without a larger refactor. ?

yancyribbens commented at 9:48 pm on November 9, 2025:

I like the idea, however the result returned is an error, not a result object. Therefore the error returned does not have a member GetAlgoCompleted. Here is where the error is returned.

It obviously doesn’t give a typed error enum(like the rust version), but I guess it is the best that can be done with the current C++ API without a larger refactor. ?

I’m not sure if it’s worth the effort rn, however adding an error for TOTAL_TRIES, similar to ErrorMaxWeightExceeded() ought to be straightforward.

frankomosh commented at 6:25 pm on November 10, 2025:

adding an error for TOTAL_TRIES, similar to ErrorMaxWeightExceeded() ought to be straightforward.

Would be better for a follow-up PR though?

yancyribbens commented at 7:35 pm on November 10, 2025:

Would be better for a follow-up PR though?

Well currently the only reason to add it would be to make the test nicer, which I don’t think is a good enough reason. The rust version is meant for any wallet implementation, and I could imagine a wallet maybe wanting to try a retry strategy (with less inputs) if the total tries are hit. So far, the core wallet doesn’t do anything fancy like that afaik.

in src/wallet/test/coinselector_tests.cpp:1157 in 922345de3f outdated

1148@@ -1149,6 +1149,39 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests)
1149         size_t expected_attempts = 7;
1150         BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));
1151     }
1152+
1153+    {
1154+        // #################################################################################################################
1155+        // 8) Test input set that has a solution will not find a solution before reaching the attempt limit
1156+        // #################################################################################################################
1157+        CAmount target =  8 * COIN;

frankomosh commented at 2:15 pm on November 4, 2025:

nit: I think there’s a double space after =. (maybe should be single spaced for consistency?)

yancyribbens commented at 8:23 pm on November 5, 2025:

Thanks, done.

yancyribbens force-pushed on Nov 5, 2025

test: add case where `TOTAL_TRIES` is exceeded yet solution remains

Show that `CoinGrider` halts searching when the number of attempts exceeds
`TOTAL_TRIES`.  To do so, show that a solution is found, then add one
more entry to the same set of inputs.  Since the search orders by
`effective_value`, the solution is constructed such that only values
with the lowest `effective_value` have the least weight.  Only the
lowest weight values will not exceed the `max_selection_weight`.
Therefore, `CoinGrinder` will not evaluate all lowest weight solutions
together before exceeding `TOTAL_TRIES` since they are last found.

This test case was inspired by a similar test for `BnB` currently
named `bnb_test`.

b189a34557

yancyribbens force-pushed on Nov 5, 2025

DrahtBot added the label CI failed on Nov 5, 2025

DrahtBot removed the label CI failed on Nov 5, 2025

frankomosh commented at 6:26 pm on November 10, 2025: contributor

Code review ACK b189a34

DrahtBot requested review from alvroble on Nov 11, 2025

alvroble commented at 9:33 pm on November 11, 2025: none

re-ACK

yancyribbens commented at 11:23 am on November 12, 2025: contributor

@murchandamus ; would appreciate your input on this.

test: add case where TOTAL_TRIES is exceeded yet solution remains #33701

Code Coverage & Benchmarks

Reviews

test: add case where `TOTAL_TRIES` is exceeded yet solution remains #33701