Avoid changeless input sets when SFFO is active #28985

1. 
   murchandamus commented at 10:41 pm on December 1, 2023: contributor

   Fixes a bunch of issues around tests for coinselection, and disables changeless solutions when building transactions with SFFO.

   Depends on #28994

2. 
   DrahtBot commented at 10:41 pm on December 1, 2023: contributor

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

   Code Coverage

   For detailed information about the code coverage, see the test coverage report.

   Reviews

   See the guideline for information on the review process. A summary of reviews will appear here.

   Conflicts

   Reviewers, this pull request conflicts with the following ones:

   • #29206 (test: Add algo assert to bnb_search_test by yancyribbens)
   • #28977 (Add Gutter Guard Selector by murchandamus)
   • #28366 (Fix waste calculation in SelectionResult by murchandamus)
   • #27877 (wallet: Add CoinGrinder coin selection algorithm 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.

3. DrahtBot added the label CI failed on Dec 2, 2023
4. murchandamus force-pushed on Dec 6, 2023
5. murchandamus force-pushed on Dec 6, 2023
6. murchandamus force-pushed on Dec 7, 2023
7. 
   murchandamus commented at 7:35 pm on December 7, 2023: contributor

   Rebased on top of #28994
8. achow101 referenced this in commit d646ca35d9 on Dec 12, 2023
9. DrahtBot added the label Needs rebase on Dec 12, 2023
10. murchandamus force-pushed on Dec 12, 2023
11. DrahtBot removed the label Needs rebase on Dec 12, 2023
12. Move first BnB test to coinselection_tests.cpp 4a95b23491
13. murchandamus force-pushed on Dec 14, 2023
14. Move BnB feerate sensitivity tests

    Originally these tests verified that at a SelectCoins level the solution
    with fewer inputs gets preferred at high feerates, and the solution with
    more inputs gets preferred at low feerates. This actually relies on the
    behavior of BnB, so these tests are moved to the BnB tests.
    
    Originally these tests relied on SFFO to work.

    446fc089e9
15. Move BnB clone skipping test f67ce3bf24
16. Remove repeated test, BnB is deterministic 2bd2a73fee
17. Move simple BnB failure tests c2139c3f98
18. Move iteration exhaustion test 87e8e8b5ce
19. Remove obsolete BnB tests

    - Testing that negative effective value filters a UTXO is a behavior of
      AvailableCoins and has nothing to do with BnB
    - Combining Preset inputs with additional inputs resulting from coin
      selection algorithms is a SelectCoins-level behavior and has nothing
      to do with BnB

    46be592821
20. Move BnB max_weight test

    Also removes `bnb_search_tests` from coinselector_tests altogether

    b27e06608f
21. Do not search for changeless Knapsack when sffo

    The behavior of test_22670 needed to be amended as we no longer are
    searching for changeless solutions with knapsack on SFFO and thus the
    trick to calculating the fee for the change output no longer worked.

    da6c0ad390
22. murchandamus force-pushed on Dec 15, 2023
23. murchandamus force-pushed on Jan 17, 2024
24. Refactor Knapsack behavior tests 34e7c541e0
25. Refactor big UTXO pool knapsack tests cd6e3e59c0
26. Improve big random UTXO pool test 7306ced6df
27. Refactor knapsack exact match test c047d0af78
28. Remove unused helpers e0b1f7e277
29. Extract TestKnapsackRandomness f37d8d3fa3
30. Move BnB SFFO restriction test e3d64b2cd9
31. Move SRD Failure tests 3a01d9a40c
32. Move SRD Success case cb97089800
33. Move CoinsResult Test 628ad6f2f5
34. Move SelectCoins_effective_value_test ea8d572ae8
35. Move effective_value_test b633bdfd4b
36. Move SelectionResult tests 433be92f2c
37. Move SelectCoins test 64a86cc018
38. Move SelectCoins max_weight test 4ce5ee6315
39. murchandamus force-pushed on Jan 17, 2024
40. DrahtBot added the label Needs rebase on Feb 9, 2024
41. 
    DrahtBot commented at 10:26 pm on February 9, 2024: contributor

    🐙 This pull request conflicts with the target branch and needs rebase.

42. 
    DrahtBot commented at 1:46 am on May 8, 2024: contributor

    ⌛ There hasn’t been much activity lately and the patch still needs rebase. What is the status here?

    • Is it still relevant? ➡️ Please solve the conflicts to make it ready for review and to ensure the CI passes.
    • Is it no longer relevant? ➡️ Please close.
    • Did the author lose interest or time to work on this? ➡️ Please close it and mark it ‘Up for grabs’ with the label, so that it can be picked up in the future.
43. 
    murchandamus commented at 5:19 pm on June 7, 2024: contributor

    Closed in favor of #29532 and #28366
44. murchandamus closed this on Jun 7, 2024

    ---

Contributors
murchandamus DrahtBot

Labels
Needs rebase CI failed