wallet: refactor coin selection algos to return util::Result

furszy · furszy · commit 128422369112 · 2023-03-07T09:01:57.000-03:00
so the selection processes can retrieve different errors and not
uninformative std::nullopt
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
@@ -63,7 +63,7 @@ struct {
 
 static const size_t TOTAL_TRIES = 100000;
 
-std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change)
+util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change)
 {
     SelectionResult result(selection_target, SelectionAlgorithm::BNB);
     CAmount curr_value = 0;
@@ -78,7 +78,7 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
         curr_available_value += utxo.GetSelectionAmount();
     }
     if (curr_available_value < selection_target) {
-        return std::nullopt;
+        return util::Error();
     }
 
     // Sort the utxo_pool
@@ -152,7 +152,7 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
 
     // Check for solution
     if (best_selection.empty()) {
-        return std::nullopt;
+        return util::Error();
     }
 
     // Set output set
@@ -165,7 +165,7 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
     return result;
 }
 
-std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, FastRandomContext& rng)
+util::Result<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, FastRandomContext& rng)
 {
     SelectionResult result(target_value, SelectionAlgorithm::SRD);
 
@@ -190,7 +190,7 @@ std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& ut
             return result;
         }
     }
-    return std::nullopt;
+    return util::Error();
 }
 
 /** Find a subset of the OutputGroups that is at least as large as, but as close as possible to, the
@@ -252,7 +252,7 @@ static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::v
     }
 }
 
-std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
+util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
                                               CAmount change_target, FastRandomContext& rng)
 {
     SelectionResult result(nTargetValue, SelectionAlgorithm::KNAPSACK);
@@ -286,7 +286,7 @@ std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups,
     }
 
     if (nTotalLower < nTargetValue) {
-        if (!lowest_larger) return std::nullopt;
+        if (!lowest_larger) return util::Error();
         result.AddInput(*lowest_larger);
         return result;
     }
diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
@@ -13,6 +13,7 @@
 #include <random.h>
 #include <util/system.h>
 #include <util/check.h>
+#include <util/result.h>
 
 #include <optional>
 
@@ -408,7 +409,7 @@ struct SelectionResult
     int GetWeight() const { return m_weight; }
 };
 
-std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change);
+util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change);
 
 /** Select coins by Single Random Draw. OutputGroups are selected randomly from the eligible
  * outputs until the target is satisfied
@@ -417,10 +418,10 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
  * @param[in]  target_value The target value to select for
  * @returns If successful, a SelectionResult, otherwise, std::nullopt
  */
-std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, FastRandomContext& rng);
+util::Result<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, FastRandomContext& rng);
 
 // Original coin selection algorithm as a fallback
-std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
+util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
                                               CAmount change_target, FastRandomContext& rng);
 } // namespace wallet
 
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
@@ -554,25 +554,34 @@ util::Result<SelectionResult> ChooseSelectionResult(const CAmount& nTargetValue,
 {
     // Vector of results. We will choose the best one based on waste.
     std::vector<SelectionResult> results;
+    std::vector<util::Result<SelectionResult>> errors;
+    auto append_error = [&] (const util::Result<SelectionResult>& result) {
+        // If any specific error message appears here, then something different from a simple "no selection found" happened.
+        // Let's save it, so it can be retrieved to the user if no other selection algorithm succeeded.
+        if (HasErrorMsg(result)) {
+            errors.emplace_back(result);
+        }
+    };
 
     if (auto bnb_result{SelectCoinsBnB(groups.positive_group, nTargetValue, coin_selection_params.m_cost_of_change)}) {
         results.push_back(*bnb_result);
-    }
+    } else append_error(bnb_result);
 
     // The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here.
     if (auto knapsack_result{KnapsackSolver(groups.mixed_group, nTargetValue, coin_selection_params.m_min_change_target, coin_selection_params.rng_fast)}) {
         knapsack_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
         results.push_back(*knapsack_result);
-    }
+    } else append_error(knapsack_result);
 
     if (auto srd_result{SelectCoinsSRD(groups.positive_group, nTargetValue, coin_selection_params.rng_fast)}) {
         srd_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
         results.push_back(*srd_result);
-    }
+    } else append_error(srd_result);
 
     if (results.empty()) {
-        // No solution found
-        return util::Error();
+        // No solution found, retrieve the first explicit error (if any).
+        // future: add 'severity level' to errors so the worst one can be retrieved instead of the first one.
+        return errors.empty() ? util::Error() : errors.front();
     }
 
     std::vector<SelectionResult> eligible_results;

Original file line number	Diff line number	Diff line change
`@@ -63,7 +63,7 @@ struct {`
`63`	`63`
`64`	`64`	`static const size_t TOTAL_TRIES = 100000;`
`65`	`65`
`66`		`-std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change)`
	`66`	`+util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change)`
`67`	`67`	`{`
`68`	`68`	`SelectionResult result(selection_target, SelectionAlgorithm::BNB);`
`69`	`69`	`CAmount curr_value = 0;`
`@@ -78,7 +78,7 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo`
`78`	`78`	`curr_available_value += utxo.GetSelectionAmount();`
`79`	`79`	`}`
`80`	`80`	`if (curr_available_value < selection_target) {`
`81`		`- return std::nullopt;`
	`81`	`+ return util::Error();`
`82`	`82`	`}`
`83`	`83`
`84`	`84`	`// Sort the utxo_pool`
`@@ -152,7 +152,7 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo`
`152`	`152`
`153`	`153`	`// Check for solution`
`154`	`154`	`if (best_selection.empty()) {`
`155`		`- return std::nullopt;`
	`155`	`+ return util::Error();`
`156`	`156`	`}`
`157`	`157`
`158`	`158`	`// Set output set`
`@@ -165,7 +165,7 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo`
`165`	`165`	`return result;`
`166`	`166`	`}`
`167`	`167`
`168`		`-std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, FastRandomContext& rng)`
	`168`	`+util::Result<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, FastRandomContext& rng)`
`169`	`169`	`{`
`170`	`170`	`SelectionResult result(target_value, SelectionAlgorithm::SRD);`
`171`	`171`
`@@ -190,7 +190,7 @@ std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& ut`
`190`	`190`	`return result;`
`191`	`191`	`}`
`192`	`192`	`}`
`193`		`- return std::nullopt;`
	`193`	`+ return util::Error();`
`194`	`194`	`}`
`195`	`195`
`196`	`196`	`/** Find a subset of the OutputGroups that is at least as large as, but as close as possible to, the`
`@@ -252,7 +252,7 @@ static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::v`
`252`	`252`	`}`
`253`	`253`	`}`
`254`	`254`
`255`		`-std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,`
	`255`	`+util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,`
`256`	`256`	`CAmount change_target, FastRandomContext& rng)`
`257`	`257`	`{`
`258`	`258`	`SelectionResult result(nTargetValue, SelectionAlgorithm::KNAPSACK);`
`@@ -286,7 +286,7 @@ std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups,`
`286`	`286`	`}`
`287`	`287`
`288`	`288`	`if (nTotalLower < nTargetValue) {`
`289`		`- if (!lowest_larger) return std::nullopt;`
	`289`	`+ if (!lowest_larger) return util::Error();`
`290`	`290`	`result.AddInput(*lowest_larger);`
`291`	`291`	`return result;`
`292`	`292`	`}`