Branch data Line data Source code
1 : : // Copyright (c) 2023-present The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or https://opensource.org/license/mit/.
4 : :
5 : : #include <txgraph.h>
6 : :
7 : : #include <random.h>
8 : :
9 : : #include <boost/test/unit_test.hpp>
10 : :
11 : : #include <memory>
12 : : #include <vector>
13 : :
14 : : BOOST_AUTO_TEST_SUITE(txgraph_tests)
15 : :
16 : : namespace {
17 : :
18 : : /** The number used as acceptable_iters argument in these tests. High enough that everything
19 : : * should be optimal, always. */
20 : : constexpr uint64_t NUM_ACCEPTABLE_ITERS = 100'000'000;
21 : :
22 : 37 : std::strong_ordering PointerComparator(const TxGraph::Ref& a, const TxGraph::Ref& b) noexcept
23 : : {
24 [ + - + + ]: 37 : return (&a) <=> (&b);
25 : : }
26 : :
27 : : } // namespace
28 : :
29 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(txgraph_trim_zigzag)
+ - + - -
+ + - + -
+ - + - +
- - + + -
+ - + - +
- + - - +
+ - + - +
- + - + -
- + + - +
- + - + -
+ - - + +
- ]
30 : : {
31 : : // T T T T T T T T T T T T T T (50 T's)
32 : : // \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
33 : : // \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
34 : : // B B B B B B B B B B B B B (49 B's)
35 : : //
36 : : /** The maximum cluster count used in this test. */
37 : 1 : static constexpr int MAX_CLUSTER_COUNT = 50;
38 : : /** The number of "bottom" transactions, which are in the mempool already. */
39 : 1 : static constexpr int NUM_BOTTOM_TX = 49;
40 : : /** The number of "top" transactions, which come from disconnected blocks. These are re-added
41 : : * to the mempool and, while connecting them to the already-in-mempool transactions, we
42 : : * discover the resulting cluster is oversized. */
43 : 1 : static constexpr int NUM_TOP_TX = 50;
44 : : /** The total number of transactions in the test. */
45 : 1 : static constexpr int NUM_TOTAL_TX = NUM_BOTTOM_TX + NUM_TOP_TX;
46 : 1 : static_assert(NUM_TOTAL_TX > MAX_CLUSTER_COUNT);
47 : : /** Set a very large cluster size limit so that only the count limit is triggered. */
48 : 1 : static constexpr int32_t MAX_CLUSTER_SIZE = 100'000 * 100;
49 : :
50 : : // Create a new graph for the test.
51 : 1 : auto graph = MakeTxGraph(MAX_CLUSTER_COUNT, MAX_CLUSTER_SIZE, NUM_ACCEPTABLE_ITERS, PointerComparator);
52 : :
53 : : // Add all transactions and store their Refs.
54 : 1 : std::vector<TxGraph::Ref> refs;
55 [ + - ]: 1 : refs.reserve(NUM_TOTAL_TX);
56 : : // First all bottom transactions: the i'th bottom transaction is at position i.
57 [ + + ]: 50 : for (unsigned int i = 0; i < NUM_BOTTOM_TX; ++i) {
58 [ + - ]: 49 : graph->AddTransaction(refs.emplace_back(), FeePerWeight{200 - i, 100});
59 : : }
60 : : // Then all top transactions: the i'th top transaction is at position NUM_BOTTOM_TX + i.
61 [ + + ]: 51 : for (unsigned int i = 0; i < NUM_TOP_TX; ++i) {
62 [ + - ]: 50 : graph->AddTransaction(refs.emplace_back(), FeePerWeight{100 - i, 100});
63 : : }
64 : :
65 : : // Create the zigzag dependency structure.
66 : : // Each transaction in the bottom row depends on two adjacent transactions from the top row.
67 [ + - ]: 1 : graph->SanityCheck();
68 [ + + ]: 50 : for (unsigned int i = 0; i < NUM_BOTTOM_TX; ++i) {
69 : 49 : graph->AddDependency(/*parent=*/refs[NUM_BOTTOM_TX + i], /*child=*/refs[i]);
70 : 49 : graph->AddDependency(/*parent=*/refs[NUM_BOTTOM_TX + i + 1], /*child=*/refs[i]);
71 : : }
72 : :
73 : : // Check that the graph is now oversized. This also forces the graph to
74 : : // group clusters and compute the oversized status.
75 [ + - ]: 1 : graph->SanityCheck();
76 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), NUM_TOTAL_TX);
77 [ + - + - ]: 2 : BOOST_CHECK(graph->IsOversized(TxGraph::Level::TOP));
78 : :
79 : : // Call Trim() to remove transactions and bring the cluster back within limits.
80 : 1 : auto removed_refs = graph->Trim();
81 [ + - ]: 1 : graph->SanityCheck();
82 [ + - + - : 2 : BOOST_CHECK(!graph->IsOversized(TxGraph::Level::TOP));
+ - ]
83 : :
84 : : // We only need to trim the middle bottom transaction to end up with 2 clusters each within cluster limits.
85 [ + - - + : 1 : BOOST_CHECK_EQUAL(removed_refs.size(), 1);
+ - ]
86 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), MAX_CLUSTER_COUNT * 2 - 2);
87 [ - + + + ]: 100 : for (unsigned int i = 0; i < refs.size(); ++i) {
88 [ + - + - ]: 99 : BOOST_CHECK_EQUAL(graph->Exists(refs[i], TxGraph::Level::TOP), i != (NUM_BOTTOM_TX / 2));
89 : : }
90 : 1 : }
91 : :
92 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(txgraph_trim_flower)
+ - + - -
+ + - + -
+ - + - +
- - + + -
+ - + - +
- + - - +
+ - + - +
- + - + -
- + + - +
- + - + -
+ - - + +
- ]
93 : : {
94 : : // We will build an oversized flower-shaped graph: all transactions are spent by 1 descendant.
95 : : //
96 : : // T T T T T T T T (100 T's)
97 : : // | | | | | | | |
98 : : // | | | | | | | |
99 : : // \---+---+---+-+-+---+---+---/
100 : : // |
101 : : // B (1 B)
102 : : //
103 : : /** The maximum cluster count used in this test. */
104 : 1 : static constexpr int MAX_CLUSTER_COUNT = 50;
105 : : /** The number of "top" transactions, which come from disconnected blocks. These are re-added
106 : : * to the mempool and, connecting them to the already-in-mempool transactions, we discover the
107 : : * resulting cluster is oversized. */
108 : 1 : static constexpr int NUM_TOP_TX = MAX_CLUSTER_COUNT * 2;
109 : : /** The total number of transactions in this test. */
110 : 1 : static constexpr int NUM_TOTAL_TX = NUM_TOP_TX + 1;
111 : : /** Set a very large cluster size limit so that only the count limit is triggered. */
112 : 1 : static constexpr int32_t MAX_CLUSTER_SIZE = 100'000 * 100;
113 : :
114 : 1 : auto graph = MakeTxGraph(MAX_CLUSTER_COUNT, MAX_CLUSTER_SIZE, NUM_ACCEPTABLE_ITERS, PointerComparator);
115 : :
116 : : // Add all transactions and store their Refs.
117 : 1 : std::vector<TxGraph::Ref> refs;
118 [ + - ]: 1 : refs.reserve(NUM_TOTAL_TX);
119 : :
120 : : // Add all transactions. They are in individual clusters.
121 [ + - ]: 1 : graph->AddTransaction(refs.emplace_back(), {1, 100});
122 [ + + ]: 101 : for (unsigned int i = 0; i < NUM_TOP_TX; ++i) {
123 [ + - ]: 100 : graph->AddTransaction(refs.emplace_back(), FeePerWeight{500 + i, 100});
124 : : }
125 [ + - ]: 1 : graph->SanityCheck();
126 : :
127 : : // The 0th transaction spends all the top transactions.
128 [ + + ]: 101 : for (unsigned int i = 1; i < NUM_TOTAL_TX; ++i) {
129 : 100 : graph->AddDependency(/*parent=*/refs[i], /*child=*/refs[0]);
130 : : }
131 [ + - ]: 1 : graph->SanityCheck();
132 : :
133 : : // Check that the graph is now oversized. This also forces the graph to
134 : : // group clusters and compute the oversized status.
135 [ + - + - ]: 2 : BOOST_CHECK(graph->IsOversized(TxGraph::Level::TOP));
136 : :
137 : : // Call Trim() to remove transactions and bring the cluster back within limits.
138 : 1 : auto removed_refs = graph->Trim();
139 [ + - ]: 1 : graph->SanityCheck();
140 [ + - + - : 2 : BOOST_CHECK(!graph->IsOversized(TxGraph::Level::TOP));
+ - ]
141 : :
142 : : // Since only the bottom transaction connects these clusters, we only need to remove it.
143 [ + - - + : 1 : BOOST_CHECK_EQUAL(removed_refs.size(), 1);
+ - ]
144 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), MAX_CLUSTER_COUNT * 2);
145 [ + - + - ]: 2 : BOOST_CHECK(!graph->Exists(refs[0], TxGraph::Level::TOP));
146 [ - + + + ]: 101 : for (unsigned int i = 1; i < refs.size(); ++i) {
147 [ + - + - ]: 200 : BOOST_CHECK(graph->Exists(refs[i], TxGraph::Level::TOP));
148 : : }
149 : 1 : }
150 : :
151 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(txgraph_trim_huge)
+ - + - -
+ + - + -
+ - + - +
- - + + -
+ - + - +
- + - - +
+ - + - +
- + - + -
- + + - +
- + - + -
+ - - + +
- ]
152 : : {
153 : : // The from-block transactions consist of 1000 fully linear clusters, each with 64
154 : : // transactions. The mempool contains 11 transactions that together merge all of these into
155 : : // a single cluster.
156 : : //
157 : : // (1000 chains of 64 transactions, 64000 T's total)
158 : : //
159 : : // T T T T T T T T
160 : : // | | | | | | | |
161 : : // T T T T T T T T
162 : : // | | | | | | | |
163 : : // T T T T T T T T
164 : : // | | | | | | | |
165 : : // T T T T T T T T
166 : : // (64 long) (64 long) (64 long) (64 long) (64 long) (64 long) (64 long) (64 long)
167 : : // | | | | | | | |
168 : : // | | / \ | / \ | | /
169 : : // \----------+--------/ \--------+--------/ \--------+-----+----+--------/
170 : : // | | |
171 : : // B B B
172 : : //
173 : : // (11 B's, each attaching to up to 100 chains of 64 T's)
174 : : //
175 : : /** The maximum cluster count used in this test. */
176 : 1 : static constexpr int MAX_CLUSTER_COUNT = 64;
177 : : /** The number of "top" (from-block) chains of transactions. */
178 : 1 : static constexpr int NUM_TOP_CHAINS = 1000;
179 : : /** The number of transactions per top chain. */
180 : 1 : static constexpr int NUM_TX_PER_TOP_CHAIN = MAX_CLUSTER_COUNT;
181 : : /** The (maximum) number of dependencies per bottom transaction. */
182 : 1 : static constexpr int NUM_DEPS_PER_BOTTOM_TX = 100;
183 : : /** The number of bottom transactions that are expected to be created. */
184 : 1 : static constexpr int NUM_BOTTOM_TX = (NUM_TOP_CHAINS - 1 + (NUM_DEPS_PER_BOTTOM_TX - 2)) / (NUM_DEPS_PER_BOTTOM_TX - 1);
185 : : /** The total number of transactions created in this test. */
186 : 1 : static constexpr int NUM_TOTAL_TX = NUM_TOP_CHAINS * NUM_TX_PER_TOP_CHAIN + NUM_BOTTOM_TX;
187 : : /** Set a very large cluster size limit so that only the count limit is triggered. */
188 : 1 : static constexpr int32_t MAX_CLUSTER_SIZE = 100'000 * 100;
189 : :
190 : : /** Refs to all top transactions. */
191 : 1 : std::vector<TxGraph::Ref> top_refs;
192 : : /** Refs to all bottom transactions. */
193 : 1 : std::vector<TxGraph::Ref> bottom_refs;
194 : : /** Indexes into top_refs for some transaction of each component, in arbitrary order.
195 : : * Initially these are the last transactions in each chains, but as bottom transactions are
196 : : * added, entries will be removed when they get merged, and randomized. */
197 : 1 : std::vector<size_t> top_components;
198 : :
199 : 1 : FastRandomContext rng;
200 : 1 : auto graph = MakeTxGraph(MAX_CLUSTER_COUNT, MAX_CLUSTER_SIZE, NUM_ACCEPTABLE_ITERS, PointerComparator);
201 : :
202 : : // Construct the top chains.
203 [ + + ]: 1001 : for (int chain = 0; chain < NUM_TOP_CHAINS; ++chain) {
204 [ + + ]: 65000 : for (int chaintx = 0; chaintx < NUM_TX_PER_TOP_CHAIN; ++chaintx) {
205 : : // Use random fees, size 1.
206 : 64000 : int64_t fee = rng.randbits<27>() + 100;
207 [ + - ]: 64000 : FeePerWeight feerate{fee, 1};
208 [ + - ]: 64000 : graph->AddTransaction(top_refs.emplace_back(), feerate);
209 : : // Add internal dependencies linking the chain transactions together.
210 [ + + ]: 64000 : if (chaintx > 0) {
211 : 63000 : graph->AddDependency(*(top_refs.rbegin()), *(top_refs.rbegin() + 1));
212 : : }
213 : : }
214 : : // Remember the last transaction in each chain, to attach the bottom transactions to.
215 [ - + + - ]: 1000 : top_components.push_back(top_refs.size() - 1);
216 : : }
217 [ + - ]: 1 : graph->SanityCheck();
218 : :
219 : : // Not oversized so far (just 1000 clusters of 64).
220 [ + - + - ]: 2 : BOOST_CHECK(!graph->IsOversized(TxGraph::Level::TOP));
221 : :
222 : : // Construct the bottom transactions, and dependencies to the top chains.
223 [ - + + + ]: 12 : while (top_components.size() > 1) {
224 : : // Construct the transaction.
225 : 11 : int64_t fee = rng.randbits<27>() + 100;
226 : 11 : FeePerWeight feerate{fee, 1};
227 : 11 : TxGraph::Ref bottom_tx;
228 : 11 : graph->AddTransaction(bottom_tx, feerate);
229 : : // Determine the number of dependencies this transaction will have.
230 [ - + + + ]: 11 : int deps = std::min<int>(NUM_DEPS_PER_BOTTOM_TX, top_components.size());
231 [ + + ]: 1021 : for (int dep = 0; dep < deps; ++dep) {
232 : : // Pick an transaction in top_components to attach to.
233 [ - + ]: 1010 : auto idx = rng.randrange(top_components.size());
234 : : // Add dependency.
235 : 1010 : graph->AddDependency(/*parent=*/top_refs[top_components[idx]], /*child=*/bottom_tx);
236 : : // Unless this is the last dependency being added, remove from top_components, as
237 : : // the component will be merged with that one.
238 [ + + ]: 1010 : if (dep < deps - 1) {
239 : : // Move entry top the back.
240 [ - + + + ]: 999 : if (idx != top_components.size() - 1) std::swap(top_components.back(), top_components[idx]);
241 : : // And pop it.
242 : 999 : top_components.pop_back();
243 : : }
244 : : }
245 [ + - ]: 11 : bottom_refs.push_back(std::move(bottom_tx));
246 : 11 : }
247 [ + - ]: 1 : graph->SanityCheck();
248 : :
249 : : // Now we are oversized (one cluster of 64011).
250 [ + - + - ]: 2 : BOOST_CHECK(graph->IsOversized(TxGraph::Level::TOP));
251 : 1 : const auto total_tx_count = graph->GetTransactionCount(TxGraph::Level::TOP);
252 [ + - - + : 2 : BOOST_CHECK(total_tx_count == top_refs.size() + bottom_refs.size());
- + + - +
- ]
253 [ + - + - ]: 2 : BOOST_CHECK(total_tx_count == NUM_TOTAL_TX);
254 : :
255 : : // Call Trim() to remove transactions and bring the cluster back within limits.
256 : 1 : auto removed_refs = graph->Trim();
257 [ + - + - : 2 : BOOST_CHECK(!graph->IsOversized(TxGraph::Level::TOP));
+ - ]
258 [ + - - + : 2 : BOOST_CHECK(removed_refs.size() == total_tx_count - graph->GetTransactionCount(TxGraph::Level::TOP));
+ - + - ]
259 [ + - ]: 1 : graph->SanityCheck();
260 : :
261 : : // At least 99% of chains must survive.
262 [ + - + - ]: 2 : BOOST_CHECK(graph->GetTransactionCount(TxGraph::Level::TOP) >= (NUM_TOP_CHAINS * NUM_TX_PER_TOP_CHAIN * 99) / 100);
263 : 1 : }
264 : :
265 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(txgraph_trim_big_singletons)
+ - + - -
+ + - + -
+ - + - +
- - + + -
+ - + - +
- + - - +
+ - + - +
- + - + -
- + + - +
- + - + -
+ - - + +
- ]
266 : : {
267 : : // Mempool consists of 100 singleton clusters; there are no dependencies. Some are oversized. Trim() should remove all of the oversized ones.
268 : 1 : static constexpr int MAX_CLUSTER_COUNT = 64;
269 : 1 : static constexpr int32_t MAX_CLUSTER_SIZE = 100'000;
270 : 1 : static constexpr int NUM_TOTAL_TX = 100;
271 : :
272 : : // Create a new graph for the test.
273 : 1 : auto graph = MakeTxGraph(MAX_CLUSTER_COUNT, MAX_CLUSTER_SIZE, NUM_ACCEPTABLE_ITERS, PointerComparator);
274 : :
275 : : // Add all transactions and store their Refs.
276 : 1 : std::vector<TxGraph::Ref> refs;
277 [ + - ]: 1 : refs.reserve(NUM_TOTAL_TX);
278 : :
279 : : // Add all transactions. They are in individual clusters.
280 [ + + ]: 101 : for (unsigned int i = 0; i < NUM_TOTAL_TX; ++i) {
281 : : // The 88th transaction is oversized.
282 : : // Every 20th transaction is oversized.
283 [ + + + + ]: 100 : const FeePerWeight feerate{500 + i, (i == 88 || i % 20 == 0) ? MAX_CLUSTER_SIZE + 1 : 100};
284 [ + - ]: 100 : graph->AddTransaction(refs.emplace_back(), feerate);
285 : : }
286 [ + - ]: 1 : graph->SanityCheck();
287 : :
288 : : // Check that the graph is now oversized. This also forces the graph to
289 : : // group clusters and compute the oversized status.
290 [ + - + - ]: 2 : BOOST_CHECK(graph->IsOversized(TxGraph::Level::TOP));
291 : :
292 : : // Call Trim() to remove transactions and bring the cluster back within limits.
293 : 1 : auto removed_refs = graph->Trim();
294 [ + - ]: 1 : graph->SanityCheck();
295 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), NUM_TOTAL_TX - 6);
296 [ + - + - ]: 2 : BOOST_CHECK(!graph->IsOversized(TxGraph::Level::TOP));
297 : :
298 : : // Check that all the oversized transactions were removed.
299 [ - + + + ]: 101 : for (unsigned int i = 0; i < refs.size(); ++i) {
300 [ + - + + : 106 : BOOST_CHECK_EQUAL(graph->Exists(refs[i], TxGraph::Level::TOP), i != 88 && i % 20 != 0);
+ + + - ]
301 : : }
302 : 1 : }
303 : :
304 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(txgraph_chunk_chain)
+ - + - -
+ + - + -
+ - + - +
- - + + -
+ - + - +
- + - - +
+ - + - +
- + - + -
- + + - +
- + - + -
+ - - + +
- ]
305 : : {
306 : : // Create a new graph for the test.
307 : 1 : auto graph = MakeTxGraph(50, 1000, NUM_ACCEPTABLE_ITERS, PointerComparator);
308 : :
309 : 6 : auto block_builder_checker = [&graph](std::vector<std::vector<TxGraph::Ref*>> expected_chunks) {
310 : 5 : std::vector<std::vector<TxGraph::Ref*>> chunks;
311 : 5 : auto builder = graph->GetBlockBuilder();
312 : 5 : FeePerWeight last_chunk_feerate;
313 [ + + ]: 19 : while (auto chunk = builder->GetCurrentChunk()) {
314 : 7 : FeePerWeight sum;
315 [ + + ]: 18 : for (TxGraph::Ref* ref : chunk->first) {
316 : : // The reported chunk feerate must match the chunk feerate obtained by asking
317 : : // it for each of the chunk's transactions individually.
318 [ + - + - : 33 : BOOST_CHECK(graph->GetMainChunkFeerate(*ref) == chunk->second);
+ - ]
319 : : // Verify the chunk feerate matches the sum of the reported individual feerates.
320 : 11 : sum += graph->GetIndividualFeerate(*ref);
321 : : }
322 [ + - + - : 21 : BOOST_CHECK(sum == chunk->second);
+ - + - ]
323 [ + - ]: 7 : chunks.push_back(std::move(chunk->first));
324 : 7 : last_chunk_feerate = chunk->second;
325 : 7 : builder->Include();
326 : 7 : }
327 : :
328 [ + - + - ]: 10 : BOOST_CHECK(chunks == expected_chunks);
329 : 5 : auto& last_chunk = chunks.back();
330 : : // The last chunk returned by the BlockBuilder must match GetWorstMainChunk, in reverse.
331 : 5 : std::reverse(last_chunk.begin(), last_chunk.end());
332 [ + - ]: 5 : auto [worst_chunk, worst_chunk_feerate] = graph->GetWorstMainChunk();
333 [ + - + - : 10 : BOOST_CHECK(last_chunk == worst_chunk);
+ - ]
334 [ + - + - : 15 : BOOST_CHECK(last_chunk_feerate == worst_chunk_feerate);
+ - ]
335 : 6 : };
336 : :
337 : 1 : std::vector<TxGraph::Ref> refs;
338 [ + - ]: 1 : refs.reserve(4);
339 : :
340 : 1 : FeePerWeight feerateA{2, 10};
341 : 1 : FeePerWeight feerateB{1, 10};
342 : 1 : FeePerWeight feerateC{2, 10};
343 : 1 : FeePerWeight feerateD{4, 10};
344 : :
345 : : // everytime adding a transaction, test the chunk status
346 : : // [A]
347 [ + - ]: 1 : graph->AddTransaction(refs.emplace_back(), feerateA);
348 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 1);
349 [ + - + - : 2 : block_builder_checker({{&refs[0]}});
+ + - - ]
350 : : // [A, B]
351 [ + - ]: 1 : graph->AddTransaction(refs.emplace_back(), feerateB);
352 : 1 : graph->AddDependency(/*parent=*/refs[0], /*child=*/refs[1]);
353 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 2);
354 [ + - + - : 3 : block_builder_checker({{&refs[0]}, {&refs[1]}});
+ - + + -
- ]
355 : :
356 : : // [A, BC]
357 [ + - ]: 1 : graph->AddTransaction(refs.emplace_back(), feerateC);
358 : 1 : graph->AddDependency(/*parent=*/refs[1], /*child=*/refs[2]);
359 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 3);
360 [ + - + - : 3 : block_builder_checker({{&refs[0]}, {&refs[1], &refs[2]}});
+ - + + -
- ]
361 : :
362 : : // [ABCD]
363 [ + - ]: 1 : graph->AddTransaction(refs.emplace_back(), feerateD);
364 : 1 : graph->AddDependency(/*parent=*/refs[2], /*child=*/refs[3]);
365 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 4);
366 [ + - + - : 2 : block_builder_checker({{&refs[0], &refs[1], &refs[2], &refs[3]}});
+ + - - ]
367 : :
368 [ + - ]: 1 : graph->SanityCheck();
369 : :
370 : : // D->C->A
371 : 1 : graph->RemoveTransaction(refs[1]);
372 : : // txgraph is not responsible for removing the descendants or ancestors
373 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 3);
374 : : // only A remains there
375 : 1 : graph->RemoveTransaction(refs[2]);
376 : 1 : graph->RemoveTransaction(refs[3]);
377 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 1);
378 [ + - + - : 2 : block_builder_checker({{&refs[0]}});
+ + - - ]
379 [ + - + - : 6 : }
+ - + - +
- + - + -
- - - - ]
380 : :
381 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(txgraph_staging)
+ - + - -
+ + - + -
+ - + - +
- - + + -
+ - + - +
- + - - +
+ - + - +
- + - + -
- + + - +
- + - + -
+ - - + +
- ]
382 : : {
383 : : /* Create a new graph for the test.
384 : : * The parameters are max_cluster_count, max_cluster_size, acceptable_iters
385 : : */
386 : 1 : auto graph = MakeTxGraph(10, 1000, NUM_ACCEPTABLE_ITERS, PointerComparator);
387 : :
388 : 1 : std::vector<TxGraph::Ref> refs;
389 [ + - ]: 1 : refs.reserve(2);
390 : :
391 : 1 : FeePerWeight feerateA{2, 10};
392 : 1 : FeePerWeight feerateB{1, 10};
393 : :
394 : : // everytime adding a transaction, test the chunk status
395 : : // [A]
396 [ + - ]: 1 : graph->AddTransaction(refs.emplace_back(), feerateA);
397 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->HaveStaging(), false);
398 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 1);
399 : :
400 : 1 : graph->StartStaging();
401 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->HaveStaging(), true);
402 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 1);
403 : :
404 : : // [A, B]
405 [ + - ]: 1 : graph->AddTransaction(refs.emplace_back(), feerateB);
406 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::MAIN), 1);
407 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 2);
408 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->Exists(refs[0], TxGraph::Level::TOP), true);
409 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->Exists(refs[1], TxGraph::Level::TOP), true);
410 : :
411 : 1 : graph->AddDependency(/*parent=*/refs[0], /*child=*/refs[1]);
412 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::MAIN), 1);
413 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 2);
414 : :
415 : 1 : graph->CommitStaging();
416 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->HaveStaging(), false);
417 : :
418 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::MAIN), 2);
419 : :
420 : 1 : graph->StartStaging();
421 : :
422 : : // [A]
423 : 1 : graph->RemoveTransaction(refs[1]);
424 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::MAIN), 2);
425 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 1);
426 : :
427 : 1 : graph->CommitStaging();
428 : :
429 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::MAIN), 1);
430 : :
431 [ + - ]: 1 : graph->SanityCheck();
432 : 1 : }
433 : :
434 : : BOOST_AUTO_TEST_SUITE_END()
|
