wallet: Add output grouping

4 files changed, 94 insertions, 3 deletions

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index a403411e5b..8bc4e10b8d 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -298,3 +298,40 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<CInputCoin>& vCoins
 
     return true;
 }
+
+/******************************************************************************
+
+ OutputGroup
+
+ ******************************************************************************/
+
+void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants) {
+    m_outputs.push_back(output);
+    m_from_me &= from_me;
+    m_value += output.effective_value;
+    m_depth = std::min(m_depth, depth);
+    // m_ancestors is currently the max ancestor count for all coins in the group; however, this is
+    // not ideal, as a wallet will consider e.g. thirty 2-ancestor coins as having two ancestors,
+    // when in reality it has 60 ancestors.
+    m_ancestors = std::max(m_ancestors, ancestors);
+    // m_descendants is the count as seen from the top ancestor, not the descendants as seen from the
+    // coin itself; thus, this value is accurate
+    m_descendants = std::max(m_descendants, descendants);
+    effective_value = m_value;
+}
+
+std::vector<CInputCoin>::iterator OutputGroup::Discard(const CInputCoin& output) {
+    auto it = m_outputs.begin();
+    while (it != m_outputs.end() && it->outpoint != output.outpoint) ++it;
+    if (it == m_outputs.end()) return it;
+    m_value -= output.effective_value;
+    effective_value -= output.effective_value;
+    return m_outputs.erase(it);
+}
+
+bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const
+{
+    return m_depth >= (m_from_me ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs)
+        && m_ancestors <= eligibility_filter.max_ancestors
+        && m_descendants <= eligibility_filter.max_descendants;
+}
diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
index 218d20fb47..0211851750 100644
--- a/src/wallet/coinselection.h
+++ b/src/wallet/coinselection.h
@@ -66,8 +66,38 @@ struct CoinEligibilityFilter
     CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_descendants(max_descendants) {}
 };
 
+struct OutputGroup
+{
+    std::vector<CInputCoin> m_outputs;
+    bool m_from_me{true};
+    CAmount m_value{0};
+    int m_depth{999};
+    size_t m_ancestors{0};
+    size_t m_descendants{0};
+    CAmount effective_value{0};
+    CAmount fee{0};
+    CAmount long_term_fee{0};
+
+    OutputGroup() {}
+    OutputGroup(std::vector<CInputCoin>&& outputs, bool from_me, CAmount value, int depth, size_t ancestors, size_t descendants)
+    : m_outputs(std::move(outputs))
+    , m_from_me(from_me)
+    , m_value(value)
+    , m_depth(depth)
+    , m_ancestors(ancestors)
+    , m_descendants(descendants)
+    {}
+    OutputGroup(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants) : OutputGroup() {
+        Insert(output, depth, from_me, ancestors, descendants);
+    }
+    void Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants);
+    std::vector<CInputCoin>::iterator Discard(const CInputCoin& output);
+    bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const;
+};
+
 bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees);
 
 // Original coin selection algorithm as a fallback
 bool KnapsackSolver(const CAmount& nTargetValue, std::vector<CInputCoin>& vCoins, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet);
+
 #endif // BITCOIN_WALLET_COINSELECTION_H
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
index aeed430111..03c829357b 100644
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -4438,3 +4438,29 @@ void CWallet::LearnAllRelatedScripts(const CPubKey& key)
     LearnRelatedScripts(key, OutputType::P2SH_SEGWIT);
 }
 
+std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outputs, bool single_coin) const {
+    std::vector<OutputGroup> groups;
+    std::map<CTxDestination, OutputGroup> gmap;
+    CTxDestination dst;
+    for (const auto& output : outputs) {
+        if (output.fSpendable) {
+            CInputCoin input_coin = output.GetInputCoin();
+
+            size_t ancestors, descendants;
+            mempool.GetTransactionAncestry(output.tx->GetHash(), ancestors, descendants);
+            if (!single_coin && ExtractDestination(output.tx->tx->vout[output.i].scriptPubKey, dst)) {
+                if (gmap.count(dst) == 10) {
+                    groups.push_back(gmap[dst]);
+                    gmap.erase(dst);
+                }
+                gmap[dst].Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants);
+            } else {
+                groups.emplace_back(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants);
+            }
+        }
+    }
+    if (!single_coin) {
+        for (const auto& it : gmap) groups.push_back(it.second);
+    }
+    return groups;
+}
diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h
index b636924fe2..f3e3a78f83 100644
--- a/src/wallet/wallet.h
+++ b/src/wallet/wallet.h
@@ -534,9 +534,6 @@ public:
     }
 };
 
-
-
-
 /** Private key that includes an expiration date in case it never gets used. */
 class CWalletKey
 {
@@ -864,6 +861,7 @@ public:
         std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params, bool& bnb_used) const;
 
     bool IsSpent(const uint256& hash, unsigned int n) const;
+    std::vector<OutputGroup> GroupOutputs(const std::vector<COutput>& outputs, bool single_coin) const;
 
     bool IsLockedCoin(uint256 hash, unsigned int n) const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
     void LockCoin(const COutPoint& output) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);