Merge #12634: [refactor] Make TransactionWithinChainLimit more flexible

f77e1d34fd5f17304ce319b5f962b8005592501a test: Add MempoolAncestryTests (Karl-Johan Alm)
a08d76bcfee6f563a268933357931abe32060668 mempool: Calculate descendant maximum thoroughly (Karl-Johan Alm)
6d3568371eb2559d65a3e2334252d36a262319e8 wallet: Switch to using ancestor/descendant limits (Karl-Johan Alm)
6888195b062c8c58dd776fd10b44b25554eb1f15 wallet: Strictly greater than for ancestor caps (Karl-Johan Alm)
322b12ac4e0a8c892e81a760ff7225619248b74f Remove deprecated TransactionWithinChainLimit (Karl-Johan Alm)
47847515473b054929af0c8de3d54b6672500cab Switch to GetTransactionAncestry() in OutputEligibleForSpending (Karl-Johan Alm)
475a385a80198a46a6d99846f99b968f04e9b470 Add GetTransactionAncestry to CTxMemPool for general purpose chain limit checking (Karl-Johan Alm)
46847d69d2c1cc908fd779daac7884e365955dbd mempool: Fix max descendants check (Karl-Johan Alm)
b9ef21dd727dde33f5bd3c33226b05d07eb12aac mempool: Add explicit max_descendants (Karl-Johan Alm)

Pull request description:

  Currently, `TransactionWithinChainLimit` is restricted to single-output use, and needs to be called every time for different limits. If it is replaced with a chain limit value calculator, that can be called once and reused, and is generally more flexible (see e.g. #12257).

  Update: this PR now corrects usage of max ancestors / max descendants, including calculating the correct max descendant value, as advertised for the two limits.

  ~~This change also makes `nMaxAncestors` signed, as the replacement method will return `-1` for "not in the mempool", which is different from "0", which means "no ancestors/descendants in mempool".~~

  ~~This is a subset of #12257.~~

Tree-SHA512: aa59c849360542362b3126c0e29d44d3d58f11898e277d38c034dc4b86a5b4500f77ac61767599ce878c876b5c446fec9c02699797eb2fa41e530ec863a00cf9

1 files changed, 28 insertions, 3 deletions

diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index 6f1fd8ce61..1c6dba0c9c 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -1055,11 +1055,36 @@ void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpends
     }
 }
 
-bool CTxMemPool::TransactionWithinChainLimit(const uint256& txid, size_t chainLimit) const {
+uint64_t CTxMemPool::CalculateDescendantMaximum(txiter entry) const {
+    // find parent with highest descendant count
+    std::vector<txiter> candidates;
+    setEntries counted;
+    candidates.push_back(entry);
+    uint64_t maximum = 0;
+    while (candidates.size()) {
+        txiter candidate = candidates.back();
+        candidates.pop_back();
+        if (!counted.insert(candidate).second) continue;
+        const setEntries& parents = GetMemPoolParents(candidate);
+        if (parents.size() == 0) {
+            maximum = std::max(maximum, candidate->GetCountWithDescendants());
+        } else {
+            for (txiter i : parents) {
+                candidates.push_back(i);
+            }
+        }
+    }
+    return maximum;
+}
+
+void CTxMemPool::GetTransactionAncestry(const uint256& txid, size_t& ancestors, size_t& descendants) const {
     LOCK(cs);
     auto it = mapTx.find(txid);
-    return it == mapTx.end() || (it->GetCountWithAncestors() < chainLimit &&
-       it->GetCountWithDescendants() < chainLimit);
+    ancestors = descendants = 0;
+    if (it != mapTx.end()) {
+        ancestors = it->GetCountWithAncestors();
+        descendants = CalculateDescendantMaximum(it);
+    }
 }
 
 SaltedTxidHasher::SaltedTxidHasher() : k0(GetRand(std::numeric_limits<uint64_t>::max())), k1(GetRand(std::numeric_limits<uint64_t>::max())) {}