wallet: Introduce SelectionResult for encapsulating a coin selection solution

achow101 commented at 11:09 pm on May 21, 2021: member

Instead of returning a set of selected coins and their total value as separate items, encapsulate both of these, and other variables, into a new SelectionResult struct. This allows us to have all of the things relevant to a coin selection solution be in a single object. SelectionResult enables us to implement the waste calculation in a cleaner way.

All of the coin selection functions (SelectCoinsBnB, KnapsackSolver, AttemptSelection, and SelectCoins) are changed to use a SelectionResult as the output parameter.

Based on #22009

DrahtBot added the label Wallet on May 21, 2021

DrahtBot commented at 3:49 am on May 22, 2021: member

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#23534 (wallet: Allow negtive effective value inputs when subtracting fee from outputs by achow101)
#23497 (Add src/node/ and src/wallet/ code to node:: and wallet:: namespaces by ryanofsky)
#23475 (wallet: add config to prioritize a solution that doesn’t create change in coin selection by brunoerg)
#23367 (Optimize coin selection by dropping BnB upper limit by S3RK)
#23202 (wallet: allow psbtbumpfee to work with txs with external inputs by achow101)
#23201 (wallet: Allow users to specify input weights when funding a transaction by achow101)
#13226 (Optimize SelectCoinsBnB by tracking the selection by index rather than by position by Empact)

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.

achow101 force-pushed on May 25, 2021

achow101 force-pushed on Jun 1, 2021

achow101 force-pushed on Jun 2, 2021

achow101 force-pushed on Jun 9, 2021

achow101 force-pushed on Jul 3, 2021

glozow commented at 3:18 pm on August 24, 2021: member

Concept ACK

achow101 force-pushed on Aug 26, 2021

achow101 force-pushed on Sep 1, 2021

achow101 marked this as ready for review on Sep 1, 2021

DrahtBot added the label Needs rebase on Sep 3, 2021

in src/wallet/test/coinselector_tests.cpp:200 in bf455047a0 outdated

196@@ -178,15 +197,15 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
197     // Select 1 Cent
198     add_coin(1 * CENT, 1, actual_selection);
199     BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT, selection, value_ret));
200-    BOOST_CHECK(equal_sets(selection, actual_selection));
201+    BOOST_CHECK(equivalent_sets(selection, actual_selection));

Xekyo commented at 8:22 pm on September 3, 2021:

Commit 80402a13e52671aa7359e3b87d85098805926a63: This may be more a comment on the commit message, but shouldn’t the result of BnB be deterministic? Are the OutputGroups unsorted, or how is this happening?

achow101 commented at 10:12 pm on September 3, 2021:

I don’t remember the specifics, but I think it had to with different txids being in utxo_pool and actual_selection

in src/wallet/coinselection.h:198 in 187a9d9285 outdated

192@@ -193,6 +193,17 @@ struct SelectionResult
193      *  hit a specific target.
194      */
195     CAmount input_fees{0};
196+    /** Whether the input values for calculations should be the the effective value (true) or normal value (false) */

Xekyo commented at 9:00 pm on September 3, 2021:

0    /** Whether the input values for calculations should be the effective value (true) or normal value (false) */

achow101 commented at 0:34 am on September 4, 2021:

Fixed

in src/wallet/coinselection.h:202 in 187a9d9285 outdated

192@@ -193,6 +193,17 @@ struct SelectionResult
193      *  hit a specific target.
194      */
195     CAmount input_fees{0};
196+    /** Whether the input values for calculations should be the the effective value (true) or normal value (false) */
197+    bool m_use_effective{true};
198+    /** The algorithm used supports making change outputs. */
199+    bool m_make_change{false};
200+    /** The cost of making a change output and spending it in the future. Since this is largely a static parameter independent of the selection, it is not cleared by Clear() */

Xekyo commented at 9:05 pm on September 3, 2021:

What do you mean with “independent of the selection”? Do you mean that it’s the same across different algorithms, independent of the inputs that get picked, or smth else? It’s definitely dependent on the selection parameters, especially the feerate.

achow101 commented at 10:16 pm on September 3, 2021:

Independent of the algorithm.

achow101 commented at 0:34 am on September 4, 2021:

Clarified the comment.

in src/wallet/test/coinselector_tests.cpp:157 in 405e780110 outdated

176@@ -177,7 +177,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
177     // Setup
178     std::vector<CInputCoin> utxo_pool;
179     CoinSet selection;
180-    CoinSet actual_selection;
181+    SelectionResult expected_result;

Xekyo commented at 9:06 pm on September 3, 2021:

Could 75672596d018f857013599b94f65efaf6446a825 perhaps be a scripted diff?

achow101 commented at 0:34 am on September 4, 2021:

Done

achow101 force-pushed on Sep 3, 2021

in src/wallet/spend.cpp:360 in b6ef0e496a outdated

356@@ -357,17 +357,15 @@ std::vector<OutputGroup> GroupOutputs(const CWallet& wallet, const std::vector<C
357     return groups_out;
358 }
359 
360-bool AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> coins,
361-                                 std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params)
362+bool AttemptSelection(const CWallet& walletconst CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> coins,

Xekyo commented at 9:28 pm on September 3, 2021:

This looks perhaps like an accidental edit

0bool AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> coins,

achow101 commented at 0:34 am on September 4, 2021:

Fixed

in src/wallet/spend.cpp:411 in 10492b60ad outdated

414-                 continue;
415-            nValueRet += out.tx->tx->vout[out.i].nValue;
416-            setCoinsRet.insert(out.GetInputCoin());
417+        for (const COutput& out : vCoins) {
418+            if (!out.fSpendable) continue;
419+            /* Set depth, from_me, ancestors, and descendants to 0 or false as don't matter for preset inputs as no actual selection is being done.

Xekyo commented at 9:31 pm on September 3, 2021:

“as don’t matter” seems to be missing a word

achow101 commented at 0:34 am on September 4, 2021:

fixed

Xekyo commented at 9:43 pm on September 3, 2021: member

Light review, concept ACK

DrahtBot removed the label Needs rebase on Sep 3, 2021

achow101 force-pushed on Sep 4, 2021

theStack commented at 2:38 pm on September 8, 2021: member

Concept ACK

DrahtBot added the label Needs rebase on Sep 9, 2021

achow101 force-pushed on Sep 9, 2021

DrahtBot removed the label Needs rebase on Sep 9, 2021

achow101 force-pushed on Sep 28, 2021

achow101 commented at 11:18 pm on September 28, 2021: member

Rebased. I’ve also made some additional changes. Notably, instead of using SelectionResult as an out parameter, all of the coin selection functions will return an std::optional<SelectionResult> instead.

achow101 force-pushed on Sep 29, 2021

laanwj added this to the "Blockers" column in a project

DrahtBot added the label Needs rebase on Oct 4, 2021

achow101 force-pushed on Oct 4, 2021

DrahtBot removed the label Needs rebase on Oct 4, 2021

S3RK commented at 7:53 am on October 7, 2021: member

Concept ACK, going to review the code

achow101 force-pushed on Oct 7, 2021

DrahtBot added the label Needs rebase on Oct 8, 2021

achow101 force-pushed on Oct 8, 2021

DrahtBot removed the label Needs rebase on Oct 8, 2021

Empact commented at 12:12 pm on October 13, 2021: member

Concept ACK.

Was troubled by the largely unused cost_of_change attr, and looked to narrow its scope. I think I’ve come up with some useful additions here: https://github.com/achow101/bitcoin/compare/selectionresult...Empact:selectionresult

test: Drop unused knapsack_result var
refactor: Move cost_of_change param from SelectionResult to #GetWaste
refactor: Calculate waste once for each result, rather than once for comparison
refactor: Move SelectionResult#Equivalent/EqualResult to test

in src/wallet/test/coinselector_tests.cpp:625 in c5da3dfe93 outdated

621@@ -602,8 +622,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
622 
623 BOOST_AUTO_TEST_CASE(ApproximateBestSubset)
624 {
625-    CoinSet setCoinsRet;
626-    CAmount nValueRet;
627+    SelectionResult knapsack_result(CAmount(0), true);

Empact commented at 12:14 pm on October 13, 2021:

This is apparently unused. https://github.com/Empact/bitcoin/commit/4719cc5aacf7531724d24a81b5b8935d2605f13f

achow101 commented at 5:29 pm on October 13, 2021: member

I’ve pulled in all of the suggested changes.

achow101 force-pushed on Oct 13, 2021

DrahtBot added the label Needs rebase on Oct 22, 2021

Fix bnb_search_test to use set equivalence for

For BnB, we only want to check that sets are equivalent with their
values, whereas in knapsack we care about the outpoints.

94d851d28c

achow101 force-pushed on Oct 22, 2021

DrahtBot removed the label Needs rebase on Oct 22, 2021

in src/wallet/spend.cpp:440 in 1036ab72f8 outdated

469+            preset_inputs.Insert(out.GetInputCoin(), 0, false, 0, 0, false);
470         }
471-        return (nValueRet >= nTargetValue);
472+        SelectionResult result(nTargetValue);
473+        result.AddInput(preset_inputs);
474+        if (result.GetSelectedValue() >= nTargetValue) return std::nullopt;

S3RK commented at 8:34 am on November 2, 2021:

0        if (result.GetSelectedValue() < nTargetValue) return std::nullopt;

achow101 commented at 4:29 pm on November 2, 2021:

Oops, fixed.

S3RK commented at 7:16 pm on November 2, 2021:

Looks like this hasn’t been caught by the tests, probably a nice to have follow up and a good first issue.

achow101 force-pushed on Nov 2, 2021

in src/wallet/test/coinselector_tests.cpp:86 in 94d851d28c outdated

82@@ -81,6 +83,23 @@ static void add_coin(std::vector<COutput>& coins, CWallet& wallet, const CAmount
83     coins.push_back(output);
84 }
85 
86+static bool equivalent_sets(CoinSet a, CoinSet b)

glozow commented at 2:58 pm on November 14, 2021:

In 94d851d28cb909a8f1f8ab795f1d9fc74bebfc7f

I think there should definitely be a comment here about the difference describing exactly what equivalent_sets checks and its difference vs equal_sets

achow101 commented at 6:51 pm on November 23, 2021:

A comment is added when these are later replaced with EquivalentResuls and EqualResults.

in src/wallet/coinselection.h:206 in fe4d2eff23 outdated

196@@ -197,6 +197,32 @@ struct OutputGroup
197  */
198 [[nodiscard]] CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, CAmount change_cost, CAmount target, bool use_effective_value = true);
199 
200+struct SelectionResult
201+{
202+    /** Set of inputs selected by the algorithm to use in the transaction */
203+    std::set<CInputCoin> m_selected_inputs;

glozow commented at 3:00 pm on November 14, 2021:

In fe4d2eff23f22ec09b71bd4f218a28c66a386f10: Should this be private? Especially since you have functions to AddInput() and GetInputVector(), nobody should have direct access to this set.

achow101 commented at 10:03 pm on November 23, 2021:

Inserted a commit which makes them private.

in src/wallet/coinselection.h:216 in fe4d2eff23 outdated

205+    const CAmount m_target;
206+    /** Whether the input values for calculations should be the effective value (true) or normal value (false) */
207+    bool m_use_effective{false};
208+
209+    explicit SelectionResult(const CAmount target)
210+        : m_target(target) {}

glozow commented at 3:01 pm on November 14, 2021:

In fe4d2eff23f22ec09b71bd4f218a28c66a386f10: delete default ctor, to make it impossible to create a SelectionResult with no specified target?

achow101 commented at 10:03 pm on November 23, 2021:

Done

in src/wallet/coinselection.cpp:411 in cb6507ca5f outdated

412@@ -418,6 +413,7 @@ void SelectionResult::Clear()
413 void SelectionResult::AddInput(const OutputGroup& group)
414 {
415     util::insert(m_selected_inputs, group.m_outputs);
416+    m_use_effective = !group.m_subtract_fee_outputs;

glozow commented at 3:05 pm on November 14, 2021:

In cb6507ca5fc2be3d88ad5764185419e0f20a175c:

This seems strange, since m_use_effective should never really change. IIRC, m_subtract_fee_outputs is known right from the start (CreateTransactionInternal()) right? It seems that SelectionResult::m_use_effective should be a const bool and set in the constructor.

glozow commented at 3:06 pm on November 14, 2021:

My expectation would be to Assume(group.m_subtract_fee_outputs != m_use_effective). Maybe I’m misunderstanding?

achow101 commented at 6:54 pm on November 23, 2021:

I did it this way because SelectionResults are constructed by the SelectCoins* functions which do not know about m_subtract_fee_outputs and didn’t feel like adding more parameters to those functions just to have m_use_effective be set in the constructor.

in src/wallet/spend.cpp:525 in c97801c398 outdated

524         // If possible, fund the transaction with confirmed UTXOs only. Prefer at least six
525         // confirmations on outputs received from other wallets and only spend confirmed change.
526-        if (AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 6, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true;
527-        if (AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 1, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true;
528+        std::optional<SelectionResult> r1 = AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 6, 0), vCoins, coin_selection_params);
529+        if (r1) return r1;

glozow commented at 3:14 pm on November 14, 2021:

I think this is cleaner, and keeps the scope of the result to this if block. There’s no reason why r1’s scope should persist through the end of the lambda.

0        if (auto r1{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 6, 0), vCoins, coin_selection_params)}) {
1            return r1.value();
2        }

glozow commented at 3:16 pm on November 14, 2021:

(same with the rest of the AttemptSelection calls)

achow101 commented at 10:03 pm on November 23, 2021:

Done here and elsewhere.

in src/wallet/coinselection.cpp:166 in c97801c398 outdated

166+            result.AddInput(utxo_pool.at(i));
167         }
168     }
169 
170-    return true;
171+    return std::make_optional(result);

glozow commented at 3:30 pm on November 14, 2021:

is there any benefit to using a std::make_optional here?

0    return result;

achow101 commented at 10:03 pm on November 23, 2021:

No, changed to just return result.

in src/wallet/spend.cpp:514 in c97801c398 outdated

514@@ -515,60 +515,60 @@ bool SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCo
515     // Coin Selection attempts to select inputs from a pool of eligible UTXOs to fund the
516     // transaction at a target feerate. If an attempt fails, more attempts may be made using a more
517     // permissive CoinEligibilityFilter.
518-    const bool res = [&] {
519+    std::optional<SelectionResult> res = [&] {
520         // Pre-selected inputs already cover the target amount.
521-        if (value_to_select <= 0) return true;
522+        if (value_to_select <= 0) return std::make_optional(SelectionResult(nTargetValue));

glozow commented at 3:31 pm on November 14, 2021:

note to self, std::make_optional makes sense here to avoid the copy of the temporary SelectionResult; it’s constructed in place

in src/wallet/spend.cpp:385 in c97801c398 outdated

393-    CAmount bnb_value;
394-    if (SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change, bnb_coins, bnb_value)) {
395-        const auto waste = GetSelectionWaste(bnb_coins, /* cost of change */ CAmount(0), nTargetValue, !coin_selection_params.m_subtract_fee_outputs);
396-        results.emplace_back(std::make_tuple(waste, std::move(bnb_coins), bnb_value));
397+    std::optional<SelectionResult> bnb_result = SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change);
398+    if (bnb_result) {

glozow commented at 3:34 pm on November 14, 2021:

0    if (auto bnb_result{SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change)}) {

achow101 commented at 10:03 pm on November 23, 2021:

Done

in src/wallet/spend.cpp:416 in c97801c398 outdated

434-    const auto& best_result = std::min_element(results.begin(), results.end(), [](const auto& a, const auto& b) {
435-        return std::get<0>(a) < std::get<0>(b) || (std::get<0>(a) == std::get<0>(b) && std::get<1>(a).size() > std::get<1>(b).size());
436+    auto [best_result, waste] = *std::min_element(results.begin(), results.end(), [](const auto& a, const auto& b){
437+        const auto [a_result, a_waste] = a;
438+        const auto [b_result, b_waste] = b;
439+        return a_waste < b_waste || (a_waste == b_waste && a_result.m_selected_inputs.size() > b_result.m_selected_inputs.size());

glozow commented at 3:35 pm on November 14, 2021:

Can this be written into a comparison operator for SelectionResult? The logic of waste and what makes one selection result better than another is inherent to the SelectionResult type; imo it fits better there than within AttemptSelection.

If you have a < operator defined, you can sort and/or just return the min element.

achow101 commented at 10:05 pm on November 23, 2021:

I didn’t want to always be computing waste every time, especially because we may not have access to information such as the cost of change. So the approach I’ve done for this is to have a function which computes and stores the waste inside of SelectionResult, and then operator< will use that when doing the comparison.

glozow commented at 3:43 pm on November 14, 2021: member

I really like the interface of returning a std::optional<SelectionResult>. My main suggestion is instead of res = Select(...); if (res) return res; declare it within the if condition like if (auto res{Select(...)}) return *res;.

in src/wallet/coinselection.cpp:422 in c97801c398 outdated

409+}
410+
411+std::vector<CInputCoin> SelectionResult::GetInputVector() const
412+{
413+    std::vector<CInputCoin> coins(m_selected_inputs.begin(), m_selected_inputs.end());
414+    Shuffle(coins.begin(), coins.end(), FastRandomContext());

laanwj commented at 6:09 pm on November 23, 2021:

I think randomizing in a Get function is very unexpected. You wouldn’t expect it to return a different value every time. I’d prefer to either rename this function to e.g. RandomizedInputVector() or, do it at the call site, or do the shuffle somewhere else.

achow101 commented at 10:05 pm on November 23, 2021:

I’ve added GetInputSet to just return m_selected_inputs and changed this to be GetShuffledInputVector.

laanwj commented at 2:14 pm on November 25, 2021:

Thanks!

in src/wallet/coinselection.cpp:362 in c97801c398 outdated

355@@ -369,6 +356,11 @@ CAmount OutputGroup::GetSelectionAmount() const
356     return m_subtract_fee_outputs ? m_value : effective_value;
357 }
358 
359+CAmount SelectionResult::GetWaste(CAmount change_cost) const
360+{
361+    return GetSelectionWaste(m_selected_inputs, change_cost, m_target, m_use_effective);
362+}

laanwj commented at 6:10 pm on November 23, 2021:

Maybe move this under the global ::GetSelectionWaste? Currently no problem but if you’d ever want to make it static.

achow101 commented at 10:05 pm on November 23, 2021:

Done

in src/wallet/test/coinselector_tests.cpp:89 in c97801c398 outdated

83@@ -81,10 +84,30 @@ static void add_coin(std::vector<COutput>& coins, CWallet& wallet, const CAmount
84     coins.push_back(output);
85 }
86 
87-static bool equal_sets(CoinSet a, CoinSet b)
88+/** Check if SelectionResult a is equivalent to SelectionResult b.
89+ * Equivalent means same input values, but maybe different inputs (i.e. same value, different prevout) */
90+bool EquivalentResult(const SelectionResult& a, const SelectionResult& b)

laanwj commented at 6:14 pm on November 23, 2021:

Local function, could be static

achow101 commented at 10:05 pm on November 23, 2021:

Done

in src/wallet/coinselection.cpp:402 in c97801c398 outdated

395+        ret += coin.txout.nValue;
396+    }
397+    return ret;
398+}
399+
400+void SelectionResult::Clear()

laanwj commented at 6:21 pm on November 23, 2021:

I don’t think this function is ever used. I think I’d prefer to remove it, in general it seems unnecessary to have a Clear function instead of replacing the structure with a new, empty one.

achow101 commented at 10:06 pm on November 23, 2021:

I had intended to use it in the tests, and with the changes to make m_selected_inputs private, it is now being used by those tests.

achow101 force-pushed on Nov 23, 2021

in src/wallet/spend.h:126 in e142d9af81 outdated

121@@ -122,8 +122,8 @@ bool AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const
122  * param@[out]  nValueRet           Total value of selected coins including pre-selected ones
123  *                                  from coin_control and Coin Selection if successful.
124  */
125-bool SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet,
126-                 const CCoinControl& coin_control, CoinSelectionParams& coin_selection_params) EXCLUSIVE_LOCKS_REQUIRED(wallet.cs_wallet);
127+std::optional<SelectionResult> SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, const CCoinControl& coin_control,
128+                 CoinSelectionParams& coin_selection_params) EXCLUSIVE_LOCKS_REQUIRED(wallet.cs_wallet);

laanwj commented at 3:13 pm on December 2, 2021:

It looks like CoinsSelectionParams& can be const
Doc comment above needs to be updated, it refers to arguments that no longer exist (applies to multiple functions)

achow101 commented at 6:49 pm on December 5, 2021:

Done both.

laanwj commented at 3:16 pm on December 2, 2021: member

Code review ACK e142d9af81c502a4694565ee6eef7b87ca1c0387 Seems pretty close to merge, found some last minute nits (sorry).

in src/wallet/coinselection.cpp:394 in 1b1ad425d6 outdated

402+}
403+
404+CAmount SelectionResult::GetWaste() const
405+{
406+    Assume(m_waste != std::nullopt);
407+    return *m_waste;

glozow commented at 4:01 pm on December 2, 2021:

In 1b1ad425d6b2ca951e0a7e6096819fc5e468af4b:

Would it be better if, when waste is nullopt, calculate it? The *m_waste would throw an exception if m_waste == std::nullopt, so the Assume doesn’t do much.

achow101 commented at 6:34 pm on December 5, 2021:

The cost of change is not known to SelectionResult so it cannot be calculated.

glozow commented at 6:41 pm on December 5, 2021:

ah right 🤦

in src/wallet/coinselection.cpp:416 in 1b1ad425d6 outdated

411+{
412+    CAmount ret = 0;
413+    for (const auto& coin : m_selected_inputs) {
414+        ret += coin.txout.nValue;
415+    }
416+    return ret;

glozow commented at 4:02 pm on December 2, 2021:

In 1b1ad425d6b2ca951e0a7e6096819fc5e468af4b

0    return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin.txout.nValue;});

achow101 commented at 6:49 pm on December 5, 2021:

Done

in src/wallet/test/coinselector_tests.cpp:122 in 22e3b5b63c outdated

120+static bool EqualResult(const SelectionResult& a, const SelectionResult& b)
121 {
122-    std::pair<CoinSet::iterator, CoinSet::iterator> ret = mismatch(a.begin(), a.end(), b.begin());
123-    return ret.first == a.end() && ret.second == b.end();
124+    std::pair<std::set<CInputCoin>::iterator, std::set<CInputCoin>::iterator> ret = std::mismatch(a.GetInputSet().begin(), a.GetInputSet().end(), b.GetInputSet().begin());
125+    return ret.first == a.GetInputSet().end() && ret.second == b.GetInputSet().end();

glozow commented at 4:15 pm on December 2, 2021:

In 22e3b5b63c46d2e2dc601a8ca061823e21ab7151: Why delete alias?

0    std::pair<CoinSet::iterator, CoinSet::iterator> ret = std::mismatch(a.GetInputSet().begin(), a.GetInputSet().end(), b.GetInputSet().begin());
1    return ret.first == a.GetInputSet().end() && ret.second == b.GetInputSet().end();

achow101 commented at 6:50 pm on December 5, 2021:

Done

in src/wallet/spend.cpp:381 in 0211023c25 outdated

377@@ -378,16 +378,14 @@ bool AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const
378 {
379     setCoinsRet.clear();
380     nValueRet = 0;
381-    // Vector of results for use with waste calculation
382-    // In order: calculated waste, selected inputs, selected input value (sum of input values)
383-    // TODO: Use a struct representing the selection result
384-    std::vector<std::tuple<CAmount, std::set<CInputCoin>, CAmount>> results;
385+    // Vector of result and waste pairs. We will choose the best one based on waste.

glozow commented at 4:21 pm on December 2, 2021:

0211023c256dd5fde9ff82e832305c8b3c981d89:

Really nice that it’s just SelectionResults instead of tuples now :D but the comment needs to be updated

achow101 commented at 6:50 pm on December 5, 2021:

Done

in src/wallet/spend.cpp:386 in 0211023c25 outdated

388     // Note that unlike KnapsackSolver, we do not include the fee for creating a change output as BnB will not create a change output.
389     std::vector<OutputGroup> positive_groups = GroupOutputs(wallet, coins, coin_selection_params, eligibility_filter, true /* positive_only */);
390     if (auto bnb_result{SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change)}) {
391         bnb_result->ComputeAndSetWaste(CAmount(0));
392-        results.emplace_back(std::make_tuple(bnb_result->GetWaste(), bnb_result->GetInputSet(), bnb_result->GetSelectedValue()));
393+        results.push_back(*bnb_result);

glozow commented at 4:28 pm on December 2, 2021:

in 0211023c256dd5fde9ff82e832305c8b3c981d89:

why not keep emplace_back?

achow101 commented at 6:42 pm on December 5, 2021:

The result is already constructed.

in src/wallet/spend.cpp:415 in 0211023c25 outdated

411@@ -414,11 +412,9 @@ bool AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const
412 
413     // Choose the result with the least waste
414     // If the waste is the same, choose the one which spends more inputs.
415-    const auto& best_result = std::min_element(results.begin(), results.end(), [](const auto& a, const auto& b) {
416-        return std::get<0>(a) < std::get<0>(b) || (std::get<0>(a) == std::get<0>(b) && std::get<1>(a).size() > std::get<1>(b).size());
417-    });
418-    setCoinsRet = std::get<1>(*best_result);
419-    nValueRet = std::get<2>(*best_result);
420+    auto best_result = *std::min_element(results.begin(), results.end());

glozow commented at 4:29 pm on December 2, 2021:

in 0211023c256dd5fde9ff82e832305c8b3c981d89: try not to make a copy of the result

achow101 commented at 6:50 pm on December 5, 2021:

Changed to auto&

in src/wallet/coinselection.cpp:397 in e142d9af81 outdated

392+{
393+    Assume(m_waste != std::nullopt);
394+    return *m_waste;
395+}
396+
397+CAmount SelectionResult::GetSelectedValue() const

glozow commented at 4:40 pm on December 2, 2021:

In 1b1ad425d6b2ca951e0a7e6096819fc5e468af4b: [[nodiscard]] the GetWaste() and GetSelectedValue() functions?

achow101 commented at 6:50 pm on December 5, 2021:

Done

in src/wallet/coinselection.cpp:406 in e142d9af81 outdated

404+}
405+
406+void SelectionResult::Clear()
407+{
408+    m_selected_inputs.clear();
409+}

glozow commented at 4:42 pm on December 2, 2021:

In 1b1ad42 Should this function also clear m_waste?

achow101 commented at 6:50 pm on December 5, 2021:

Done

glozow commented at 4:47 pm on December 2, 2021: member

utACK e142d9af81, a few suggestions/questions

Introduce SelectionResult struct

Introduces a SelectionResult struct which contains the set of selected
inputs and the total transaction fee for the transaction. This will be
used by the various SelectCoins* functions. Additionally helpers are
provided to compute the total input value and result comparisons.

9d1d86da04

scripted-diff: Use SelectionResult in coin selector tests

Replace the CoinSet actual_selection with a SelectionResult
expected_result. We don't use the SelectionResult functions yet, but
will soon.

-BEGIN VERIFY SCRIPT-
sed -i 's/CoinSet actual_selection/SelectionResult expected_result(CAmount(0))/' src/wallet/test/coinselector_tests.cpp
sed -i 's/actual_selection/expected_result.m_selected_inputs/' src/wallet/test/coinselector_tests.cpp
sed -i 's/expected_result.m_selected_inputs.clear/expected_result.Clear/' src/wallet/test/coinselector_tests.cpp
-END VERIFY SCRIPT-

cbf0b9f4ff

Make member variables of SelectionResult private a339add471

Return SelectionResult from SelectCoinsBnB

Removes coins_out and value_ret has SelectCoinsBnB return a
std::optional<SelectionResult>

60d2ca72e3

Return SelectionResult from KnapsackSolver

Returns a std::optional<SelectionResult> from KnapsackSolver instead of
using out parameters for the inputs set and selected value.

0ef6184575

Return SelectionResult from SelectCoinsSRD

Changes SelectCoinsSRD to return a SelectionResult.

51a9c00b4d

Make an OutputGroup for preset inputs

In SelectCoins, for our preset inputs, we combine all of the preset
inputs into a single OutputGroup. This allows us to combine the preset
inputs with additional selection algo results.

e8f7ae5eb3

Use SelectionResult for waste calculation bb50850a44

Use SelectionResult in AttemptSelection

Replace setCoinsRet and nValueRet with a SelectionResult in
AttemptSelection

9d9b101d20

Use SelectionResult in SelectCoins

Replace setCoinsRet and nValueRet with SelectionResult

05300c1439

achow101 force-pushed on Dec 5, 2021

laanwj commented at 4:20 pm on December 9, 2021: member

Code review ACK 05300c14392facf38330eb4fcd8e695a838b76f3

laanwj merged this on Dec 9, 2021

laanwj closed this on Dec 9, 2021

in src/wallet/spend.cpp:413 in 05300c1439

437-        return std::get<0>(a) < std::get<0>(b) || (std::get<0>(a) == std::get<0>(b) && std::get<1>(a).size() > std::get<1>(b).size());
438-    });
439-    setCoinsRet = std::get<1>(*best_result);
440-    nValueRet = std::get<2>(*best_result);
441-    return true;
442+    auto& best_result = *std::min_element(results.begin(), results.end());

glozow commented at 4:30 pm on December 9, 2021:

😗 👌

glozow commented at 4:36 pm on December 9, 2021: member

reACK 05300c14392facf38330eb4fcd8e695a838b76f3. Thanks for taking suggestions!

in src/wallet/coinselection.cpp:393 in 05300c1439

388+    m_waste = GetSelectionWaste(m_selected_inputs, change_cost, m_target, m_use_effective);
389+}
390+
391+CAmount SelectionResult::GetWaste() const
392+{
393+    Assume(m_waste != std::nullopt);

MarcoFalke commented at 5:07 pm on December 9, 2021:

This will need to be Assert, otherwise you might run into UB, no?

MarcoFalke commented at 1:49 pm on December 13, 2021:

https://github.com/bitcoin/bitcoin/pull/23762

in src/wallet/coinselection.cpp:431 in 05300c1439

426+bool SelectionResult::operator<(SelectionResult other) const
427+{
428+    Assume(m_waste != std::nullopt);
429+    Assume(other.m_waste != std::nullopt);
430+    // As this operator is only used in std::min_element, we want the result that has more inputs when waste are equal.
431+    return *m_waste < *other.m_waste || (*m_waste == *other.m_waste && m_selected_inputs.size() > other.m_selected_inputs.size());

MarcoFalke commented at 5:07 pm on December 9, 2021:

same

laanwj removed this from the "Blockers" column in a project

MarcoFalke commented at 5:16 pm on December 9, 2021: member

left some q

RandyMcMillan referenced this in commit caf667a3e1 on Dec 23, 2021

DrahtBot locked this on Dec 13, 2022

wallet: Introduce SelectionResult for encapsulating a coin selection solution #22019

Conflicts