ec6c3ce92db81aa74ca509af499f203d278d681b
Some suggested unit tests, seems like a good target for some tests. Probably would be easy to adapt to a fuzz target?
diff --git a/src/test/mempool_tests.cpp b/src/test/mempool_tests.cpp
index 77024c3edc..8069bf3540 100644
--- a/src/test/mempool_tests.cpp
+++ b/src/test/mempool_tests.cpp
@@ -13,4 +13,5 @@
#include <boost/test/unit_test.hpp>
+#include <algorithm>
#include <vector>
@@ -501,3 +502,151 @@ BOOST_AUTO_TEST_CASE(MempoolAncestryTestsDiamond)
}
+// Create static size tx with no ancestors
+static CTransactionRef MakeRelayTx(uint32_t nonce)
+{
+ CMutableTransaction tx;
+ tx.vin.resize(1);
+ tx.vin[0].prevout = COutPoint(Txid::FromUint256(uint256{1}), nonce);
+ tx.vin[0].scriptSig = CScript() << OP_11;
+ tx.vout.resize(1);
+ tx.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
+ tx.vout[0].nValue = 10 * COIN;
+ return MakeTransactionRef(tx);
+}
+
+// Add tx to the pool with the given total fee
+static Wtxid AddRelayTx(CTxMemPool& pool, TestMemPoolEntryHelper& entry, uint32_t nonce, CAmount fee)
+{
+ const auto tx_ref{MakeRelayTx(nonce)};
+ TryAddToMempool(pool, entry.Fee(fee).FromTx(tx_ref));
+ return tx_ref->GetWitnessHash();
+}
+
+// Run ExtractBestByMiningScoreWithTopology and translate the returned iterators
+// back into wtxids
+static std::vector<Wtxid> ExtractBest(CTxMemPool& pool, std::vector<Wtxid>& wtxids, size_t n_to_sort)
+{
+ LOCK(pool.cs);
+ std::vector<Wtxid> out;
+ for (const auto it : pool.ExtractBestByMiningScoreWithTopology(wtxids, n_to_sort)) {
+ out.push_back(it->GetTx().GetWitnessHash());
+ }
+ return out;
+}
+
+BOOST_AUTO_TEST_CASE(MempoolExtractBestByMiningScore)
+{
+ CTxMemPool& pool = *Assert(m_node.mempool);
+ TestMemPoolEntryHelper entry;
+
+ // Build 6 independent txs with strictly distinct, descending feerates.
+ std::vector<Wtxid> best;
+ for (uint32_t i = 0; i < 6; ++i) {
+ best.push_back(AddRelayTx(pool, entry, i + 1, (10 - i) * 1000));
+ }
+
+ // 1) Full sort: n_to_sort >= size returns everything, best-to-worst, and
+ // fully drains the input vector.
+ {
+ std::vector<Wtxid> in{best};
+ std::shuffle(in.begin(), in.end(), m_rng); // order does not matter
+ auto res = ExtractBest(pool, in, in.size());
+ BOOST_CHECK(in.empty());
+ BOOST_CHECK(res == best);
+ }
+
+ // 2) wtxids not in the mempool are silently dropped (and don't appear in
+ // the result), while the rest still sort correctly.
+ {
+ std::vector<Wtxid> in{best[2], MakeRelayTx(99991)->GetWitnessHash(), best[0],
+ MakeRelayTx(99992)->GetWitnessHash(), best[4]};
+ std::shuffle(in.begin(), in.end(), m_rng); // order does not matter
+ // *All* out-of-mempool deletions happen if n_to_sort is non-0
+ auto res = ExtractBest(pool, in, 3);
+ BOOST_CHECK(in.empty());
+ const std::vector<Wtxid> expected{best[0], best[2], best[4]};
+ BOOST_CHECK(res == expected);
+ }
+
+ // 3) All out of mempool txs are wiped, regardless of n_to_sort argument,
+ // as long as non-0
+ {
+ std::vector<Wtxid> in{MakeRelayTx(99991)->GetWitnessHash(),
+ MakeRelayTx(99992)->GetWitnessHash(),
+ MakeRelayTx(99993)->GetWitnessHash(),
+ MakeRelayTx(99994)->GetWitnessHash(),
+ MakeRelayTx(99995)->GetWitnessHash()};
+ std::shuffle(in.begin(), in.end(), m_rng); // order does not matter
+ auto res = ExtractBest(pool, in, /*n_to_sort=*/1);
+ BOOST_CHECK(in.empty());
+ BOOST_CHECK(res.empty());
+ }
+
+
+ // 4) Duplicate wtxids are deduplicated in a single (full-sort) pass.
+ {
+ std::vector<Wtxid> in{best[3], best[1], best[3], best[1], best[3]};
+ std::shuffle(in.begin(), in.end(), m_rng); // order does not matter
+ auto res = ExtractBest(pool, in, 100);
+ BOOST_CHECK(in.empty());
+ const std::vector<Wtxid> expected{best[1], best[3]};
+ BOOST_CHECK(res == expected);
+ }
+
+ // 5) The docstring example: with 2*n_to_sort + 1 copies of a single tx and
+ // n_to_sort == 2, the first two passes return nothing (each removing 2
+ // duplicates), and only the third pass yields the tx exactly once.
+ {
+ std::vector<Wtxid> in(5, best[0]);
+ auto p1 = ExtractBest(pool, in, 2);
+ BOOST_CHECK(p1.empty());
+ BOOST_CHECK_EQUAL(in.size(), 3U);
+ auto p2 = ExtractBest(pool, in, 2);
+ BOOST_CHECK(p2.empty());
+ BOOST_CHECK_EQUAL(in.size(), 1U);
+ auto p3 = ExtractBest(pool, in, 2);
+ BOOST_CHECK(in.empty());
+ const std::vector<Wtxid> expected{best[0]};
+ BOOST_CHECK(p3 == expected);
+ }
+
+ // 6) Draining in small batches (partial-sort path) across many passes,
+ // with duplicates mixed in, yields every distinct tx exactly once, in
+ // global best-to-worst order, and never returns something still queued.
+ {
+ std::vector<Wtxid> in;
+ for (const auto& w : best) { in.push_back(w); in.push_back(w); } // each twice
+ std::shuffle(in.begin(), in.end(), m_rng); // order does not matter
+ std::vector<Wtxid> drained;
+ const uint32_t n_to_sort{2};
+ size_t max_passes{in.size()};
+ while (!in.empty()) {
+ BOOST_REQUIRE(max_passes-- > 0);
+ const auto in_size_pre{in.size()};
+ auto res = ExtractBest(pool, in, n_to_sort);
+ if (in_size_pre >= n_to_sort) {
+ BOOST_CHECK_EQUAL(in.size(), in_size_pre - n_to_sort);
+ } else {
+ BOOST_CHECK(in.empty());
+ }
+
+ // Nothing returned this pass may still be sitting in the queue.
+ for (const auto& r : res) {
+ BOOST_CHECK(std::find(in.begin(), in.end(), r) == in.end());
+ }
+ drained.insert(drained.end(), res.begin(), res.end());
+ }
+ BOOST_CHECK(drained == best); // every tx once, global order preserved
+ }
+
+ // 7) n_to_sort == 0 is a no-op: nothing is returned and the input vector is
+ // left untouched
+ {
+ std::vector<Wtxid> in{best[0], best[1]};
+ auto res = ExtractBest(pool, in, 0);
+ BOOST_CHECK(res.empty());
+ BOOST_CHECK_EQUAL(in.size(), 2U);
+ }
+}
+
BOOST_AUTO_TEST_SUITE_END()
