wallet: remove fetch pre-selected-inputs responsibility from SelectCoins

so if there is an error in any of the pre-set coins, we can fail right away
without computing the wallet available coins set (calling `AvailableCoins`)
which is a slow operation as it goes through the entire wallet's txes map.

----------------------

And to make the Coin Selection flow cleared, have decoupled SelectCoins in two functions:

1) AutomaticCoinSelection.
2) SelectCoins.

1) AutomaticCoinSelection:
   Receives a set of coins and selects the best subset of them to
   cover the target amount.

2) SelectCoins
   In charge of select all the user manually selected coins first ("pre-set inputs"), and
   if coin_control 'm_allow_other_inputs=true', call 'AutomaticCoinSelection' to select a
   subset of coins owned by the wallet to cover for the target - preset_inputs.total_amount
   remaining value.

6 files changed, 71 insertions, 37 deletions

diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index 0b7cb7faa4..84c96b041f 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -568,18 +568,14 @@ std::optional<SelectionResult> ChooseSelectionResult(const CWallet& wallet, cons
     return best_result;
 }
 
-std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& available_coins, const CAmount& nTargetValue, const CCoinControl& coin_control, const CoinSelectionParams& coin_selection_params)
+std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& available_coins, const PreSelectedInputs& pre_set_inputs,
+                                           const CAmount& nTargetValue, const CCoinControl& coin_control,
+                                           const CoinSelectionParams& coin_selection_params)
 {
-    CAmount value_to_select = nTargetValue;
-
-    util::Result<PreSelectedInputs> pre_selected_inputs = FetchSelectedInputs(wallet, coin_control, coin_selection_params);
-    if (!pre_selected_inputs) return std::nullopt;
-    PreSelectedInputs inputs = *pre_selected_inputs;
-
     // If automatic coin selection was disabled, we just want to return the preset inputs result
     if (!coin_control.m_allow_other_inputs) {
         SelectionResult result(nTargetValue, SelectionAlgorithm::MANUAL);
-        result.AddInputs(inputs.coins, coin_selection_params.m_subtract_fee_outputs);
+        result.AddInputs(pre_set_inputs.coins, coin_selection_params.m_subtract_fee_outputs);
 
         if (!coin_selection_params.m_subtract_fee_outputs && result.GetSelectedEffectiveValue() < nTargetValue) {
             return std::nullopt;
@@ -591,9 +587,23 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& a
         return result;
     }
 
-    // Decrease the already selected amount
-    value_to_select -= inputs.total_amount;
+    // Decrease the selection target before start the automatic coin selection
+    CAmount selection_target = nTargetValue - pre_set_inputs.total_amount;
+    auto op_selection_result = AutomaticCoinSelection(wallet, available_coins, selection_target, coin_control, coin_selection_params);
+    if (!op_selection_result) return op_selection_result;
+
+    // Add preset inputs to the automatic coin selection result
+    SelectionResult preselected(pre_set_inputs.total_amount, SelectionAlgorithm::MANUAL);
+    preselected.AddInputs(pre_set_inputs.coins, coin_selection_params.m_subtract_fee_outputs);
+    op_selection_result->Merge(preselected);
+    if (op_selection_result->GetAlgo() == SelectionAlgorithm::MANUAL) {
+        op_selection_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
+    }
+    return op_selection_result;
+}
 
+std::optional<SelectionResult> AutomaticCoinSelection(const CWallet& wallet, CoinsResult& available_coins, const CAmount& value_to_select, const CCoinControl& coin_control, const CoinSelectionParams& coin_selection_params)
+{
     unsigned int limit_ancestor_count = 0;
     unsigned int limit_descendant_count = 0;
     wallet.chain().getPackageLimits(limit_ancestor_count, limit_descendant_count);
@@ -610,9 +620,6 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& a
         available_coins.Shuffle(coin_selection_params.rng_fast);
     }
 
-    SelectionResult preselected(inputs.total_amount, SelectionAlgorithm::MANUAL);
-    preselected.AddInputs(inputs.coins, coin_selection_params.m_subtract_fee_outputs);
-
     // 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.
@@ -669,14 +676,6 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& a
         return std::optional<SelectionResult>();
     }();
 
-    if (!res) return std::nullopt;
-
-    // Add preset inputs to result
-    res->Merge(preselected);
-    if (res->GetAlgo() == SelectionAlgorithm::MANUAL) {
-        res->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
-    }
-
     return res;
 }
 
@@ -889,6 +888,14 @@ static util::Result<CreatedTransactionResult> CreateTransactionInternal(
     const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size);
     CAmount selection_target = recipients_sum + not_input_fees;
 
+    // Fetch manually selected coins
+    PreSelectedInputs preset_inputs;
+    if (coin_control.HasSelected()) {
+        auto res_fetch_inputs = FetchSelectedInputs(wallet, coin_control, coin_selection_params);
+        if (!res_fetch_inputs) return util::Error{util::ErrorString(res_fetch_inputs)};
+        preset_inputs = *res_fetch_inputs;
+    }
+
     // Fetch wallet available coins if "other inputs" are
     // allowed (coins automatically selected by the wallet)
     CoinsResult available_coins;
@@ -903,7 +910,7 @@ static util::Result<CreatedTransactionResult> CreateTransactionInternal(
     }
 
     // Choose coins to use
-    std::optional<SelectionResult> result = SelectCoins(wallet, available_coins, /*nTargetValue=*/selection_target, coin_control, coin_selection_params);
+    std::optional<SelectionResult> result = SelectCoins(wallet, available_coins, preset_inputs, /*nTargetValue=*/selection_target, coin_control, coin_selection_params);
     if (!result) {
         return util::Error{_("Insufficient funds")};
     }
diff --git a/src/wallet/spend.h b/src/wallet/spend.h
index 39832f363f..b66bb3797c 100644
--- a/src/wallet/spend.h
+++ b/src/wallet/spend.h
@@ -142,8 +142,14 @@ struct PreSelectedInputs
 };
 
 /**
- * Select a set of coins such that nTargetValue is met and at least
- * all coins from coin_control are selected; never select unconfirmed coins if they are not ours
+ * Fetch and validate coin control selected inputs.
+ * Coins could be internal (from the wallet) or external.
+*/
+util::Result<PreSelectedInputs> FetchSelectedInputs(const CWallet& wallet, const CCoinControl& coin_control,
+                                                    const CoinSelectionParams& coin_selection_params) EXCLUSIVE_LOCKS_REQUIRED(wallet.cs_wallet);
+
+/**
+ * Select a set of coins such that nTargetValue is met; never select unconfirmed coins if they are not ours
  * param@[in]   wallet                 The wallet which provides data necessary to spend the selected coins
  * param@[in]   available_coins        The struct of coins, organized by OutputType, available for selection prior to filtering
  * param@[in]   nTargetValue           The target value
@@ -152,9 +158,17 @@ struct PreSelectedInputs
  * returns                             If successful, a SelectionResult containing the selected coins
  *                                     If failed, a nullopt.
  */
-std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& available_coins, const CAmount& nTargetValue, const CCoinControl& coin_control,
+std::optional<SelectionResult> AutomaticCoinSelection(const CWallet& wallet, CoinsResult& available_coins, const CAmount& nTargetValue, const CCoinControl& coin_control,
                  const CoinSelectionParams& coin_selection_params) EXCLUSIVE_LOCKS_REQUIRED(wallet.cs_wallet);
 
+/**
+ * Select all coins from coin_control, and if coin_control 'm_allow_other_inputs=true', call 'AutomaticCoinSelection' to
+ * select a set of coins such that nTargetValue - pre_set_inputs.total_amount is met.
+ */
+std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& available_coins, const PreSelectedInputs& pre_set_inputs,
+                                           const CAmount& nTargetValue, const CCoinControl& coin_control,
+                                           const CoinSelectionParams& coin_selection_params) EXCLUSIVE_LOCKS_REQUIRED(wallet.cs_wallet);
+
 struct CreatedTransactionResult
 {
     CTransactionRef tx;
diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
index 23f024247d..f9c8c8ee9d 100644
--- a/src/wallet/test/coinselector_tests.cpp
+++ b/src/wallet/test/coinselector_tests.cpp
@@ -338,9 +338,13 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
         add_coin(available_coins, *wallet, 2 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);
         CCoinControl coin_control;
         coin_control.m_allow_other_inputs = true;
-        coin_control.Select(available_coins.All().at(0).outpoint);
+        COutput select_coin = available_coins.All().at(0);
+        coin_control.Select(select_coin.outpoint);
+        PreSelectedInputs selected_input;
+        selected_input.Insert(select_coin, coin_selection_params_bnb.m_subtract_fee_outputs);
+        available_coins.coins[OutputType::BECH32].erase(available_coins.coins[OutputType::BECH32].begin());
         coin_selection_params_bnb.m_effective_feerate = CFeeRate(0);
-        const auto result10 = SelectCoins(*wallet, available_coins, 10 * CENT, coin_control, coin_selection_params_bnb);
+        const auto result10 = SelectCoins(*wallet, available_coins, selected_input, 10 * CENT, coin_control, coin_selection_params_bnb);
         BOOST_CHECK(result10);
     }
     {
@@ -363,7 +367,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
         expected_result.Clear();
         add_coin(10 * CENT, 2, expected_result);
         CCoinControl coin_control;
-        const auto result11 = SelectCoins(*wallet, available_coins, 10 * CENT, coin_control, coin_selection_params_bnb);
+        const auto result11 = SelectCoins(*wallet, available_coins, /*pre_set_inputs=*/{}, 10 * CENT, coin_control, coin_selection_params_bnb);
         BOOST_CHECK(EquivalentResult(expected_result, *result11));
         available_coins.Clear();
 
@@ -378,7 +382,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
         expected_result.Clear();
         add_coin(9 * CENT, 2, expected_result);
         add_coin(1 * CENT, 2, expected_result);
-        const auto result12 = SelectCoins(*wallet, available_coins, 10 * CENT, coin_control, coin_selection_params_bnb);
+        const auto result12 = SelectCoins(*wallet, available_coins, /*pre_set_inputs=*/{}, 10 * CENT, coin_control, coin_selection_params_bnb);
         BOOST_CHECK(EquivalentResult(expected_result, *result12));
         available_coins.Clear();
 
@@ -394,8 +398,12 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
         add_coin(9 * CENT, 2, expected_result);
         add_coin(1 * CENT, 2, expected_result);
         coin_control.m_allow_other_inputs = true;
-        coin_control.Select(available_coins.All().at(1).outpoint); // pre select 9 coin
-        const auto result13 = SelectCoins(*wallet, available_coins, 10 * CENT, coin_control, coin_selection_params_bnb);
+        COutput select_coin = available_coins.All().at(1); // pre select 9 coin
+        coin_control.Select(select_coin.outpoint);
+        PreSelectedInputs selected_input;
+        selected_input.Insert(select_coin, coin_selection_params_bnb.m_subtract_fee_outputs);
+        available_coins.coins[OutputType::BECH32].erase(++available_coins.coins[OutputType::BECH32].begin());
+        const auto result13 = SelectCoins(*wallet, available_coins, selected_input, 10 * CENT, coin_control, coin_selection_params_bnb);
         BOOST_CHECK(EquivalentResult(expected_result, *result13));
     }
 }
@@ -783,7 +791,7 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test)
         cs_params.m_cost_of_change = 1;
         cs_params.min_viable_change = 1;
         CCoinControl cc;
-        const auto result = SelectCoins(*wallet, available_coins, target, cc, cs_params);
+        const auto result = SelectCoins(*wallet, available_coins, /*pre_set_inputs=*/{}, target, cc, cs_params);
         BOOST_CHECK(result);
         BOOST_CHECK_GE(result->GetSelectedValue(), target);
     }
@@ -965,7 +973,10 @@ BOOST_AUTO_TEST_CASE(SelectCoins_effective_value_test)
     cc.SetInputWeight(output.outpoint, 148);
     cc.SelectExternal(output.outpoint, output.txout);
 
-    const auto result = SelectCoins(*wallet, available_coins, target, cc, cs_params);
+    const auto preset_inputs = *Assert(FetchSelectedInputs(*wallet, cc, cs_params));
+    available_coins.coins[OutputType::BECH32].erase(available_coins.coins[OutputType::BECH32].begin());
+
+    const auto result = SelectCoins(*wallet, available_coins, preset_inputs, target, cc, cs_params);
     BOOST_CHECK(!result);
 }
 
diff --git a/test/functional/rpc_fundrawtransaction.py b/test/functional/rpc_fundrawtransaction.py
index 79ff25efd9..54b42667bb 100755
--- a/test/functional/rpc_fundrawtransaction.py
+++ b/test/functional/rpc_fundrawtransaction.py
@@ -406,7 +406,9 @@ class RawTransactionsTest(BitcoinTestFramework):
 
     def test_invalid_input(self):
         self.log.info("Test fundrawtxn with an invalid vin")
-        inputs  = [ {'txid' : "1c7f966dab21119bac53213a2bc7532bff1fa844c124fd750a7d0b1332440bd1", 'vout' : 0} ] #invalid vin!
+        txid = "1c7f966dab21119bac53213a2bc7532bff1fa844c124fd750a7d0b1332440bd1"
+        vout = 0
+        inputs  = [ {'txid' : txid, 'vout' : vout} ] #invalid vin!
         outputs = { self.nodes[0].getnewaddress() : 1.0}
         rawtx   = self.nodes[2].createrawtransaction(inputs, outputs)
         assert_raises_rpc_error(-4, "Unable to find UTXO for external input", self.nodes[2].fundrawtransaction, rawtx)
@@ -1011,7 +1013,7 @@ class RawTransactionsTest(BitcoinTestFramework):
 
         # An external input without solving data should result in an error
         raw_tx = wallet.createrawtransaction([ext_utxo], {self.nodes[0].getnewaddress(): ext_utxo["amount"] / 2})
-        assert_raises_rpc_error(-4, "Insufficient funds", wallet.fundrawtransaction, raw_tx)
+        assert_raises_rpc_error(-4, "Not solvable pre-selected input COutPoint(%s, %s)" % (ext_utxo["txid"][0:10], ext_utxo["vout"]), wallet.fundrawtransaction, raw_tx)
 
         # Error conditions
         assert_raises_rpc_error(-5, "'not a pubkey' is not hex", wallet.fundrawtransaction, raw_tx, {"solving_data": {"pubkeys":["not a pubkey"]}})
diff --git a/test/functional/rpc_psbt.py b/test/functional/rpc_psbt.py
index 3b78a7d095..b79b8f5187 100755
--- a/test/functional/rpc_psbt.py
+++ b/test/functional/rpc_psbt.py
@@ -657,7 +657,7 @@ class PSBTTest(BitcoinTestFramework):
         ext_utxo = self.nodes[0].listunspent(addresses=[addr])[0]
 
         # An external input without solving data should result in an error
-        assert_raises_rpc_error(-4, "Insufficient funds", wallet.walletcreatefundedpsbt, [ext_utxo], {self.nodes[0].getnewaddress(): 15})
+        assert_raises_rpc_error(-4, "Not solvable pre-selected input COutPoint(%s, %s)" % (ext_utxo["txid"][0:10], ext_utxo["vout"]), wallet.walletcreatefundedpsbt, [ext_utxo], {self.nodes[0].getnewaddress(): 15})
 
         # But funding should work when the solving data is provided
         psbt = wallet.walletcreatefundedpsbt([ext_utxo], {self.nodes[0].getnewaddress(): 15}, 0, {"add_inputs": True, "solving_data": {"pubkeys": [addr_info['pubkey']], "scripts": [addr_info["embedded"]["scriptPubKey"], addr_info["embedded"]["embedded"]["scriptPubKey"]]}})
diff --git a/test/functional/wallet_send.py b/test/functional/wallet_send.py
index 07baa0595e..fb759c153d 100755
--- a/test/functional/wallet_send.py
+++ b/test/functional/wallet_send.py
@@ -508,7 +508,7 @@ class WalletSendTest(BitcoinTestFramework):
         ext_utxo = ext_fund.listunspent(addresses=[addr])[0]
 
         # An external input without solving data should result in an error
-        self.test_send(from_wallet=ext_wallet, to_wallet=self.nodes[0], amount=15, inputs=[ext_utxo], add_inputs=True, psbt=True, include_watching=True, expect_error=(-4, "Insufficient funds"))
+        self.test_send(from_wallet=ext_wallet, to_wallet=self.nodes[0], amount=15, inputs=[ext_utxo], add_inputs=True, psbt=True, include_watching=True, expect_error=(-4, "Not solvable pre-selected input COutPoint(%s, %s)" % (ext_utxo["txid"][0:10], ext_utxo["vout"])))
 
         # But funding should work when the solving data is provided
         res = self.test_send(from_wallet=ext_wallet, to_wallet=self.nodes[0], amount=15, inputs=[ext_utxo], add_inputs=True, psbt=True, include_watching=True, solving_data={"pubkeys": [addr_info['pubkey']], "scripts": [addr_info["embedded"]["scriptPubKey"], addr_info["embedded"]["embedded"]["scriptPubKey"]]})