Use SelectionResult in AttemptSelection

achow101 · achow101 · commit 9d9b101d2019 · 2021-12-05T13:44:09.000-05:00
Replace setCoinsRet and nValueRet with a SelectionResult in
AttemptSelection
diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp
@@ -54,12 +54,10 @@ static void CoinSelection(benchmark::Bench& bench)
                                                     /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0),
                                                     /* tx_noinputs_size= */ 0, /* avoid_partial= */ false);
     bench.run([&] {
-        std::set<CInputCoin> setCoinsRet;
-        CAmount nValueRet;
-        bool success = AttemptSelection(wallet, 1003 * COIN, filter_standard, coins, setCoinsRet, nValueRet, coin_selection_params);
-        assert(success);
-        assert(nValueRet == 1003 * COIN);
-        assert(setCoinsRet.size() == 2);
+        auto result = AttemptSelection(wallet, 1003 * COIN, filter_standard, coins, coin_selection_params);
+        assert(result);
+        assert(result->GetSelectedValue() == 1003 * COIN);
+        assert(result->GetInputSet().size() == 2);
     });
 }
 
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
@@ -373,11 +373,9 @@ std::vector<OutputGroup> GroupOutputs(const CWallet& wallet, const std::vector<C
     return groups_out;
 }
 
-bool AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> coins,
-                                 std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params)
+std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> coins,
+                               const CoinSelectionParams& coin_selection_params)
 {
-    setCoinsRet.clear();
-    nValueRet = 0;
     // Vector of results. We will choose the best one based on waste.
     std::vector<SelectionResult> results;
 
@@ -407,15 +405,13 @@ bool AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const
 
     if (results.size() == 0) {
         // No solution found
-        return false;
+        return std::nullopt;
     }
 
     // Choose the result with the least waste
     // If the waste is the same, choose the one which spends more inputs.
     auto& best_result = *std::min_element(results.begin(), results.end());
-    setCoinsRet = best_result.GetInputSet();
-    nValueRet = best_result.GetSelectedValue();
-    return true;
+    return best_result;
 }
 
 bool SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CCoinControl& coin_control, CoinSelectionParams& coin_selection_params)
@@ -438,7 +434,6 @@ bool SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCo
 
     // calculate value from preset inputs and store them
     std::set<CInputCoin> setPresetCoins;
-    CAmount nValueFromPresetInputs = 0;
     OutputGroup preset_inputs(coin_selection_params);
 
     std::vector<COutPoint> vPresetInputs;
@@ -466,7 +461,6 @@ bool SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCo
         }
 
         CInputCoin coin(outpoint, txout, input_bytes);
-        nValueFromPresetInputs += coin.txout.nValue;
         if (coin.m_input_bytes == -1) {
             return false; // Not solvable, can't estimate size for fee
         }
@@ -511,62 +505,67 @@ bool SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCo
     // Coin Selection attempts to select inputs from a pool of eligible UTXOs to fund the
     // transaction at a target feerate. If an attempt fails, more attempts may be made using a more
     // permissive CoinEligibilityFilter.
-    const bool res = [&] {
+    std::optional<SelectionResult> res = [&] {
         // Pre-selected inputs already cover the target amount.
-        if (value_to_select <= 0) return true;
+        if (value_to_select <= 0) return std::make_optional(SelectionResult(nTargetValue));
 
         // If possible, fund the transaction with confirmed UTXOs only. Prefer at least six
         // confirmations on outputs received from other wallets and only spend confirmed change.
-        if (AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 6, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true;
-        if (AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 1, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true;
+        if (auto r1{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 6, 0), vCoins, coin_selection_params)}) return r1;
+        if (auto r2{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 1, 0), vCoins, coin_selection_params)}) return r2;
 
         // Fall back to using zero confirmation change (but with as few ancestors in the mempool as
         // possible) if we cannot fund the transaction otherwise.
         if (wallet.m_spend_zero_conf_change) {
-            if (AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true;
-            if (AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)),
-                                   vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
-                return true;
+            if (auto r3{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, coin_selection_params)}) return r3;
+            if (auto r4{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)),
+                                   vCoins, coin_selection_params)}) {
+                return r4;
             }
-            if (AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2),
-                                   vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
-                return true;
+            if (auto r5{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2),
+                                   vCoins, coin_selection_params)}) {
+                return r5;
             }
             // If partial groups are allowed, relax the requirement of spending OutputGroups (groups
             // of UTXOs sent to the same address, which are obviously controlled by a single wallet)
             // in their entirety.
-            if (AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, true /* include_partial_groups */),
-                                   vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
-                return true;
+            if (auto r6{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, true /* include_partial_groups */),
+                                   vCoins, coin_selection_params)}) {
+                return r6;
             }
             // Try with unsafe inputs if they are allowed. This may spend unconfirmed outputs
             // received from other wallets.
-            if (coin_control.m_include_unsafe_inputs
-                && AttemptSelection(wallet, value_to_select,
+            if (coin_control.m_include_unsafe_inputs) {
+                if (auto r7{AttemptSelection(wallet, value_to_select,
                     CoinEligibilityFilter(0 /* conf_mine */, 0 /* conf_theirs */, max_ancestors-1, max_descendants-1, true /* include_partial_groups */),
-                    vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
-                return true;
+                    vCoins, coin_selection_params)}) {
+                    return r7;
+                }
             }
             // Try with unlimited ancestors/descendants. The transaction will still need to meet
             // mempool ancestor/descendant policy to be accepted to mempool and broadcasted, but
             // OutputGroups use heuristics that may overestimate ancestor/descendant counts.
-            if (!fRejectLongChains && AttemptSelection(wallet, value_to_select,
+            if (!fRejectLongChains) {
+                if (auto r8{AttemptSelection(wallet, value_to_select,
                                       CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max(), std::numeric_limits<uint64_t>::max(), true /* include_partial_groups */),
-                                      vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
-                return true;
+                                      vCoins, coin_selection_params)}) {
+                    return r8;
+                }
             }
         }
         // Coin Selection failed.
-        return false;
+        return std::optional<SelectionResult>();
     }();
 
-    // AttemptSelection clears setCoinsRet, so add the preset inputs from coin_control to the coinset
-    util::insert(setCoinsRet, setPresetCoins);
+    if (!res) return false;
 
-    // add preset inputs to the total value selected
-    nValueRet += nValueFromPresetInputs;
+    // Add preset inputs to result
+    res->AddInput(preset_inputs);
 
-    return res;
+    setCoinsRet = res->GetInputSet();
+    nValueRet = res->GetSelectedValue();
+
+    return true;
 }
 
 static bool IsCurrentForAntiFeeSniping(interfaces::Chain& chain, const uint256& block_hash)
diff --git a/src/wallet/spend.h b/src/wallet/spend.h
@@ -101,18 +101,20 @@ std::map<CTxDestination, std::vector<COutput>> ListCoins(const CWallet& wallet)
 std::vector<OutputGroup> GroupOutputs(const CWallet& wallet, const std::vector<COutput>& outputs, const CoinSelectionParams& coin_sel_params, const CoinEligibilityFilter& filter, bool positive_only);
 
 /**
- * Shuffle and select coins until nTargetValue is reached while avoiding
- * small change; This method is stochastic for some inputs and upon
- * completion the coin set and corresponding actual target value is
- * assembled
- * param@[in]   coins           Set of UTXOs to consider. These will be categorized into
- *                              OutputGroups and filtered using eligibility_filter before
- *                              selecting coins.
- * param@[out]  setCoinsRet     Populated with the coins selected if successful.
- * param@[out]  nValueRet       Used to return the total value of selected coins.
+ * Attempt to find a valid input set that meets the provided eligibility filter and target.
+ * Multiple coin selection algorithms will be run and the input set that produces the least waste
+ * (according to the waste metric) will be chosen.
+ *
+ * param@[in]  wallet                 The wallet which provides solving data for the coins
+ * param@[in]  nTargetValue           The target value
+ * param@[in]  eligilibity_filter     A filter containing rules for which coins are allowed to be included in this selection
+ * param@[in]  coins                  The vector of coins available for selection prior to filtering
+ * param@[in]  coin_selection_params  Parameters for the coin selection
+ * returns                            If successful, a SelectionResult containing the input set
+ *                                    If failed, a nullopt
  */
-bool AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> coins,
-                        std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params);
+std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> coins,
+                        const CoinSelectionParams& coin_selection_params);
 
 /**
  * Select a set of coins such that nValueRet >= nTargetValue and at least
