xrpld
Loading...
Searching...
No Matches
LedgerTrie_test.cpp
1#include <test/csf/ledgers.h>
2
3#include <xrpld/consensus/LedgerTrie.h>
4
5#include <xrpl/beast/unit_test/suite.h>
6
7#include <cstdint>
8#include <optional>
9#include <random>
10
11namespace xrpl::test {
12
13class LedgerTrie_test : public beast::unit_test::Suite
14{
15 void
16 testInsert()
17 {
18 using namespace csf;
19 // Single entry by itself
20 {
21 LedgerTrie<Ledger> t;
22 LedgerHistoryHelper h;
23 t.insert(h["abc"]);
24 BEAST_EXPECT(t.checkInvariants());
25 BEAST_EXPECT(t.tipSupport(h["abc"]) == 1);
26 BEAST_EXPECT(t.branchSupport(h["abc"]) == 1);
27
28 t.insert(h["abc"]);
29 BEAST_EXPECT(t.checkInvariants());
30 BEAST_EXPECT(t.tipSupport(h["abc"]) == 2);
31 BEAST_EXPECT(t.branchSupport(h["abc"]) == 2);
32 }
33 // Suffix of existing (extending tree)
34 {
35 LedgerTrie<Ledger> t;
36 LedgerHistoryHelper h;
37 t.insert(h["abc"]);
38 BEAST_EXPECT(t.checkInvariants());
39 // extend with no siblings
40 t.insert(h["abcd"]);
41 BEAST_EXPECT(t.checkInvariants());
42
43 BEAST_EXPECT(t.tipSupport(h["abc"]) == 1);
44 BEAST_EXPECT(t.branchSupport(h["abc"]) == 2);
45 BEAST_EXPECT(t.tipSupport(h["abcd"]) == 1);
46 BEAST_EXPECT(t.branchSupport(h["abcd"]) == 1);
47
48 // extend with existing sibling
49 t.insert(h["abce"]);
50 BEAST_EXPECT(t.tipSupport(h["abc"]) == 1);
51 BEAST_EXPECT(t.branchSupport(h["abc"]) == 3);
52 BEAST_EXPECT(t.tipSupport(h["abcd"]) == 1);
53 BEAST_EXPECT(t.branchSupport(h["abcd"]) == 1);
54 BEAST_EXPECT(t.tipSupport(h["abce"]) == 1);
55 BEAST_EXPECT(t.branchSupport(h["abce"]) == 1);
56 }
57 // uncommitted of existing node
58 {
59 LedgerTrie<Ledger> t;
60 LedgerHistoryHelper h;
61 t.insert(h["abcd"]);
62 BEAST_EXPECT(t.checkInvariants());
63 // uncommitted with no siblings
64 t.insert(h["abcdf"]);
65 BEAST_EXPECT(t.checkInvariants());
66
67 BEAST_EXPECT(t.tipSupport(h["abcd"]) == 1);
68 BEAST_EXPECT(t.branchSupport(h["abcd"]) == 2);
69 BEAST_EXPECT(t.tipSupport(h["abcdf"]) == 1);
70 BEAST_EXPECT(t.branchSupport(h["abcdf"]) == 1);
71
72 // uncommitted with existing child
73 t.insert(h["abc"]);
74 BEAST_EXPECT(t.checkInvariants());
75
76 BEAST_EXPECT(t.tipSupport(h["abc"]) == 1);
77 BEAST_EXPECT(t.branchSupport(h["abc"]) == 3);
78 BEAST_EXPECT(t.tipSupport(h["abcd"]) == 1);
79 BEAST_EXPECT(t.branchSupport(h["abcd"]) == 2);
80 BEAST_EXPECT(t.tipSupport(h["abcdf"]) == 1);
81 BEAST_EXPECT(t.branchSupport(h["abcdf"]) == 1);
82 }
83 // Suffix + uncommitted of existing node
84 {
85 LedgerTrie<Ledger> t;
86 LedgerHistoryHelper h;
87 t.insert(h["abcd"]);
88 BEAST_EXPECT(t.checkInvariants());
89 t.insert(h["abce"]);
90 BEAST_EXPECT(t.checkInvariants());
91
92 BEAST_EXPECT(t.tipSupport(h["abc"]) == 0);
93 BEAST_EXPECT(t.branchSupport(h["abc"]) == 2);
94 BEAST_EXPECT(t.tipSupport(h["abcd"]) == 1);
95 BEAST_EXPECT(t.branchSupport(h["abcd"]) == 1);
96 BEAST_EXPECT(t.tipSupport(h["abce"]) == 1);
97 BEAST_EXPECT(t.branchSupport(h["abce"]) == 1);
98 }
99 // Suffix + uncommitted with existing child
100 {
101 // abcd : abcde, abcf
102
103 LedgerTrie<Ledger> t;
104 LedgerHistoryHelper h;
105 t.insert(h["abcd"]);
106 BEAST_EXPECT(t.checkInvariants());
107 t.insert(h["abcde"]);
108 BEAST_EXPECT(t.checkInvariants());
109 t.insert(h["abcf"]);
110 BEAST_EXPECT(t.checkInvariants());
111
112 BEAST_EXPECT(t.tipSupport(h["abc"]) == 0);
113 BEAST_EXPECT(t.branchSupport(h["abc"]) == 3);
114 BEAST_EXPECT(t.tipSupport(h["abcd"]) == 1);
115 BEAST_EXPECT(t.branchSupport(h["abcd"]) == 2);
116 BEAST_EXPECT(t.tipSupport(h["abcf"]) == 1);
117 BEAST_EXPECT(t.branchSupport(h["abcf"]) == 1);
118 BEAST_EXPECT(t.tipSupport(h["abcde"]) == 1);
119 BEAST_EXPECT(t.branchSupport(h["abcde"]) == 1);
120 }
121
122 // Multiple counts
123 {
124 LedgerTrie<Ledger> t;
125 LedgerHistoryHelper h;
126 t.insert(h["ab"], 4);
127 BEAST_EXPECT(t.tipSupport(h["ab"]) == 4);
128 BEAST_EXPECT(t.branchSupport(h["ab"]) == 4);
129 BEAST_EXPECT(t.tipSupport(h["a"]) == 0);
130 BEAST_EXPECT(t.branchSupport(h["a"]) == 4);
131
132 t.insert(h["abc"], 2);
133 BEAST_EXPECT(t.tipSupport(h["abc"]) == 2);
134 BEAST_EXPECT(t.branchSupport(h["abc"]) == 2);
135 BEAST_EXPECT(t.tipSupport(h["ab"]) == 4);
136 BEAST_EXPECT(t.branchSupport(h["ab"]) == 6);
137 BEAST_EXPECT(t.tipSupport(h["a"]) == 0);
138 BEAST_EXPECT(t.branchSupport(h["a"]) == 6);
139 }
140 }
141
142 void
143 testRemove()
144 {
145 using namespace csf;
146 // Not in trie
147 {
148 LedgerTrie<Ledger> t;
149 LedgerHistoryHelper h;
150 t.insert(h["abc"]);
151
152 BEAST_EXPECT(!t.remove(h["ab"]));
153 BEAST_EXPECT(t.checkInvariants());
154 BEAST_EXPECT(!t.remove(h["a"]));
155 BEAST_EXPECT(t.checkInvariants());
156 }
157 // In trie but with 0 tip support
158 {
159 LedgerTrie<Ledger> t;
160 LedgerHistoryHelper h;
161 t.insert(h["abcd"]);
162 t.insert(h["abce"]);
163
164 BEAST_EXPECT(t.tipSupport(h["abc"]) == 0);
165 BEAST_EXPECT(t.branchSupport(h["abc"]) == 2);
166 BEAST_EXPECT(!t.remove(h["abc"]));
167 BEAST_EXPECT(t.checkInvariants());
168 BEAST_EXPECT(t.tipSupport(h["abc"]) == 0);
169 BEAST_EXPECT(t.branchSupport(h["abc"]) == 2);
170 }
171 // In trie with > 1 tip support
172 {
173 LedgerTrie<Ledger> t;
174 LedgerHistoryHelper h;
175 t.insert(h["abc"], 2);
176
177 BEAST_EXPECT(t.tipSupport(h["abc"]) == 2);
178 BEAST_EXPECT(t.remove(h["abc"]));
179 BEAST_EXPECT(t.checkInvariants());
180 BEAST_EXPECT(t.tipSupport(h["abc"]) == 1);
181
182 t.insert(h["abc"], 1);
183 BEAST_EXPECT(t.tipSupport(h["abc"]) == 2);
184 BEAST_EXPECT(t.remove(h["abc"], 2));
185 BEAST_EXPECT(t.checkInvariants());
186 BEAST_EXPECT(t.tipSupport(h["abc"]) == 0);
187
188 t.insert(h["abc"], 3);
189 BEAST_EXPECT(t.tipSupport(h["abc"]) == 3);
190 BEAST_EXPECT(t.remove(h["abc"], 300));
191 BEAST_EXPECT(t.checkInvariants());
192 BEAST_EXPECT(t.tipSupport(h["abc"]) == 0);
193 }
194 // In trie with = 1 tip support, no children
195 {
196 LedgerTrie<Ledger> t;
197 LedgerHistoryHelper h;
198 t.insert(h["ab"]);
199 t.insert(h["abc"]);
200
201 BEAST_EXPECT(t.tipSupport(h["ab"]) == 1);
202 BEAST_EXPECT(t.branchSupport(h["ab"]) == 2);
203 BEAST_EXPECT(t.tipSupport(h["abc"]) == 1);
204 BEAST_EXPECT(t.branchSupport(h["abc"]) == 1);
205
206 BEAST_EXPECT(t.remove(h["abc"]));
207 BEAST_EXPECT(t.checkInvariants());
208 BEAST_EXPECT(t.tipSupport(h["ab"]) == 1);
209 BEAST_EXPECT(t.branchSupport(h["ab"]) == 1);
210 BEAST_EXPECT(t.tipSupport(h["abc"]) == 0);
211 BEAST_EXPECT(t.branchSupport(h["abc"]) == 0);
212 }
213 // In trie with = 1 tip support, 1 child
214 {
215 LedgerTrie<Ledger> t;
216 LedgerHistoryHelper h;
217 t.insert(h["ab"]);
218 t.insert(h["abc"]);
219 t.insert(h["abcd"]);
220
221 BEAST_EXPECT(t.tipSupport(h["abc"]) == 1);
222 BEAST_EXPECT(t.branchSupport(h["abc"]) == 2);
223 BEAST_EXPECT(t.tipSupport(h["abcd"]) == 1);
224 BEAST_EXPECT(t.branchSupport(h["abcd"]) == 1);
225
226 BEAST_EXPECT(t.remove(h["abc"]));
227 BEAST_EXPECT(t.checkInvariants());
228 BEAST_EXPECT(t.tipSupport(h["abc"]) == 0);
229 BEAST_EXPECT(t.branchSupport(h["abc"]) == 1);
230 BEAST_EXPECT(t.tipSupport(h["abcd"]) == 1);
231 BEAST_EXPECT(t.branchSupport(h["abcd"]) == 1);
232 }
233 // In trie with = 1 tip support, > 1 children
234 {
235 LedgerTrie<Ledger> t;
236 LedgerHistoryHelper h;
237 t.insert(h["ab"]);
238 t.insert(h["abc"]);
239 t.insert(h["abcd"]);
240 t.insert(h["abce"]);
241
242 BEAST_EXPECT(t.tipSupport(h["abc"]) == 1);
243 BEAST_EXPECT(t.branchSupport(h["abc"]) == 3);
244
245 BEAST_EXPECT(t.remove(h["abc"]));
246 BEAST_EXPECT(t.checkInvariants());
247 BEAST_EXPECT(t.tipSupport(h["abc"]) == 0);
248 BEAST_EXPECT(t.branchSupport(h["abc"]) == 2);
249 }
250
251 // In trie with = 1 tip support, parent compaction
252 {
253 LedgerTrie<Ledger> t;
254 LedgerHistoryHelper h;
255 t.insert(h["ab"]);
256 t.insert(h["abc"]);
257 t.insert(h["abd"]);
258 BEAST_EXPECT(t.checkInvariants());
259 t.remove(h["ab"]);
260 BEAST_EXPECT(t.checkInvariants());
261 BEAST_EXPECT(t.tipSupport(h["abc"]) == 1);
262 BEAST_EXPECT(t.tipSupport(h["abd"]) == 1);
263 BEAST_EXPECT(t.tipSupport(h["ab"]) == 0);
264 BEAST_EXPECT(t.branchSupport(h["ab"]) == 2);
265
266 t.remove(h["abd"]);
267 BEAST_EXPECT(t.checkInvariants());
268
269 BEAST_EXPECT(t.tipSupport(h["abc"]) == 1);
270 BEAST_EXPECT(t.branchSupport(h["ab"]) == 1);
271 }
272 }
273
274 void
275 testEmpty()
276 {
277 using namespace csf;
278 LedgerTrie<Ledger> t;
279 LedgerHistoryHelper h;
280 BEAST_EXPECT(t.empty());
281
282 Ledger const genesis = h[""];
283 t.insert(genesis);
284 BEAST_EXPECT(!t.empty());
285 t.remove(genesis);
286 BEAST_EXPECT(t.empty());
287
288 t.insert(h["abc"]);
289 BEAST_EXPECT(!t.empty());
290 t.remove(h["abc"]);
291 BEAST_EXPECT(t.empty());
292 }
293
294 void
295 testSupport()
296 {
297 using namespace csf;
298
299 LedgerTrie<Ledger> t;
300 LedgerHistoryHelper h;
301 BEAST_EXPECT(t.tipSupport(h["a"]) == 0);
302 BEAST_EXPECT(t.tipSupport(h["axy"]) == 0);
303
304 BEAST_EXPECT(t.branchSupport(h["a"]) == 0);
305 BEAST_EXPECT(t.branchSupport(h["axy"]) == 0);
306
307 t.insert(h["abc"]);
308 BEAST_EXPECT(t.tipSupport(h["a"]) == 0);
309 BEAST_EXPECT(t.tipSupport(h["ab"]) == 0);
310 BEAST_EXPECT(t.tipSupport(h["abc"]) == 1);
311 BEAST_EXPECT(t.tipSupport(h["abcd"]) == 0);
312
313 BEAST_EXPECT(t.branchSupport(h["a"]) == 1);
314 BEAST_EXPECT(t.branchSupport(h["ab"]) == 1);
315 BEAST_EXPECT(t.branchSupport(h["abc"]) == 1);
316 BEAST_EXPECT(t.branchSupport(h["abcd"]) == 0);
317
318 t.insert(h["abe"]);
319 BEAST_EXPECT(t.tipSupport(h["a"]) == 0);
320 BEAST_EXPECT(t.tipSupport(h["ab"]) == 0);
321 BEAST_EXPECT(t.tipSupport(h["abc"]) == 1);
322 BEAST_EXPECT(t.tipSupport(h["abe"]) == 1);
323
324 BEAST_EXPECT(t.branchSupport(h["a"]) == 2);
325 BEAST_EXPECT(t.branchSupport(h["ab"]) == 2);
326 BEAST_EXPECT(t.branchSupport(h["abc"]) == 1);
327 BEAST_EXPECT(t.branchSupport(h["abe"]) == 1);
328
329 t.remove(h["abc"]);
330 BEAST_EXPECT(t.tipSupport(h["a"]) == 0);
331 BEAST_EXPECT(t.tipSupport(h["ab"]) == 0);
332 BEAST_EXPECT(t.tipSupport(h["abc"]) == 0);
333 BEAST_EXPECT(t.tipSupport(h["abe"]) == 1);
334
335 BEAST_EXPECT(t.branchSupport(h["a"]) == 1);
336 BEAST_EXPECT(t.branchSupport(h["ab"]) == 1);
337 BEAST_EXPECT(t.branchSupport(h["abc"]) == 0);
338 BEAST_EXPECT(t.branchSupport(h["abe"]) == 1);
339 }
340
341 void
342 testGetPreferred()
343 {
344 using namespace csf;
345 using Seq = Ledger::Seq;
346 // Empty
347 {
348 LedgerTrie<Ledger> const t;
349 BEAST_EXPECT(t.getPreferred(Seq{0}) == std::nullopt);
350 BEAST_EXPECT(t.getPreferred(Seq{2}) == std::nullopt);
351 }
352 // Genesis support is NOT empty
353 {
354 LedgerTrie<Ledger> t;
355 LedgerHistoryHelper h;
356 Ledger const genesis = h[""];
357 t.insert(genesis);
358
359 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
360 BEAST_EXPECT(t.getPreferred(Seq{0})->id == genesis.id());
361 BEAST_EXPECT(t.remove(genesis));
362 BEAST_EXPECT(t.getPreferred(Seq{0}) == std::nullopt);
363 BEAST_EXPECT(!t.remove(genesis));
364 }
365 // Single node no children
366 {
367 LedgerTrie<Ledger> t;
368 LedgerHistoryHelper h;
369 t.insert(h["abc"]);
370
371 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
372 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abc"].id());
373 }
374 // Single node smaller child support
375 {
376 LedgerTrie<Ledger> t;
377 LedgerHistoryHelper h;
378 t.insert(h["abc"]);
379 t.insert(h["abcd"]);
380
381 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
382 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abc"].id());
383
384 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
385 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abc"].id());
386 }
387 // Single node larger child
388 {
389 LedgerTrie<Ledger> t;
390 LedgerHistoryHelper h;
391 t.insert(h["abc"]);
392 t.insert(h["abcd"], 2);
393
394 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
395 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abcd"].id());
396
397 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
398 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abcd"].id());
399 }
400 // Single node smaller children support
401 {
402 LedgerTrie<Ledger> t;
403 LedgerHistoryHelper h;
404 t.insert(h["abc"]);
405 t.insert(h["abcd"]);
406 t.insert(h["abce"]);
407
408 // NOLINTBEGIN(bugprone-unchecked-optional-access)
409 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abc"].id());
410 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abc"].id());
411
412 t.insert(h["abc"]);
413
414 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abc"].id());
415 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abc"].id());
416 // NOLINTEND(bugprone-unchecked-optional-access)
417 }
418 // Single node larger children
419 {
420 LedgerTrie<Ledger> t;
421 LedgerHistoryHelper h;
422 t.insert(h["abc"]);
423 t.insert(h["abcd"], 2);
424 t.insert(h["abce"]);
425
426 // NOLINTBEGIN(bugprone-unchecked-optional-access)
427 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abc"].id());
428 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abc"].id());
429
430 t.insert(h["abcd"]);
431
432 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abcd"].id());
433 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abcd"].id());
434 // NOLINTEND(bugprone-unchecked-optional-access)
435 }
436 // Tie-breaker by id
437 {
438 LedgerTrie<Ledger> t;
439 LedgerHistoryHelper h;
440 t.insert(h["abcd"], 2);
441 t.insert(h["abce"], 2);
442
443 BEAST_EXPECT(h["abce"].id() > h["abcd"].id());
444
445 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
446 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abce"].id());
447
448 t.insert(h["abcd"]);
449 BEAST_EXPECT(h["abce"].id() > h["abcd"].id());
450
451 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
452 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abcd"].id());
453 }
454
455 // Tie-breaker not needed
456 {
457 LedgerTrie<Ledger> t;
458 LedgerHistoryHelper h;
459 t.insert(h["abc"]);
460 t.insert(h["abcd"]);
461 t.insert(h["abce"], 2);
462 // abce only has a margin of 1, but it owns the tie-breaker
463 BEAST_EXPECT(h["abce"].id() > h["abcd"].id());
464
465 // NOLINTBEGIN(bugprone-unchecked-optional-access)
466 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abce"].id());
467 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abce"].id());
468
469 // Switch support from abce to abcd, tie-breaker now needed
470 t.remove(h["abce"]);
471 t.insert(h["abcd"]);
472
473 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abc"].id());
474 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abc"].id());
475 // NOLINTEND(bugprone-unchecked-optional-access)
476 }
477
478 // Single node larger grand child
479 {
480 LedgerTrie<Ledger> t;
481 LedgerHistoryHelper h;
482 t.insert(h["abc"]);
483 t.insert(h["abcd"], 2);
484 t.insert(h["abcde"], 4);
485
486 // NOLINTBEGIN(bugprone-unchecked-optional-access)
487 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abcde"].id());
488 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abcde"].id());
489 BEAST_EXPECT(t.getPreferred(Seq{5})->id == h["abcde"].id());
490 // NOLINTEND(bugprone-unchecked-optional-access)
491 }
492
493 // Too much uncommitted support from competing branches
494 {
495 LedgerTrie<Ledger> t;
496 LedgerHistoryHelper h;
497 t.insert(h["abc"]);
498 t.insert(h["abcde"], 2);
499 t.insert(h["abcfg"], 2);
500 // 'de' and 'fg' are tied without 'abc' vote
501 // NOLINTBEGIN(bugprone-unchecked-optional-access)
502 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abc"].id());
503 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abc"].id());
504 BEAST_EXPECT(t.getPreferred(Seq{5})->id == h["abc"].id());
505
506 t.remove(h["abc"]);
507 t.insert(h["abcd"]);
508
509 // 'de' branch has 3 votes to 2, so earlier sequences see it as preferred
510 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abcde"].id());
511 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abcde"].id());
512
513 // However, if you validated a ledger with Seq 5, potentially on
514 // a different branch, you do not yet know if they chose abcd
515 // or abcf because of you, so abc remains preferred
516 BEAST_EXPECT(t.getPreferred(Seq{5})->id == h["abc"].id());
517 // NOLINTEND(bugprone-unchecked-optional-access)
518 }
519
520 // Changing largestSeq perspective changes preferred branch
521 {
533 LedgerTrie<Ledger> t;
534 LedgerHistoryHelper h;
535 t.insert(h["ab"]);
536 t.insert(h["ac"]);
537 t.insert(h["acf"]);
538 t.insert(h["abde"], 2);
539
540 // B has more branch support
541 // NOLINTBEGIN(bugprone-unchecked-optional-access)
542 BEAST_EXPECT(t.getPreferred(Seq{1})->id == h["ab"].id());
543 BEAST_EXPECT(t.getPreferred(Seq{2})->id == h["ab"].id());
544
545 // But if you last validated D,F or E, you do not yet know
546 // if someone used that validation to commit to B or C
547 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["a"].id());
548 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["a"].id());
549 // NOLINTEND(bugprone-unchecked-optional-access)
550
562 t.remove(h["abde"]);
563 t.insert(h["abdeg"]);
564
565 // NOLINTBEGIN(bugprone-unchecked-optional-access)
566 BEAST_EXPECT(t.getPreferred(Seq{1})->id == h["ab"].id());
567 BEAST_EXPECT(t.getPreferred(Seq{2})->id == h["ab"].id());
568 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["a"].id());
569 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["a"].id());
570 BEAST_EXPECT(t.getPreferred(Seq{5})->id == h["a"].id());
571 // NOLINTEND(bugprone-unchecked-optional-access)
572
584 t.remove(h["ac"]);
585 t.insert(h["abh"]);
586
587 // NOLINTBEGIN(bugprone-unchecked-optional-access)
588 BEAST_EXPECT(t.getPreferred(Seq{1})->id == h["ab"].id());
589 BEAST_EXPECT(t.getPreferred(Seq{2})->id == h["ab"].id());
590 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["ab"].id());
591 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["a"].id());
592 BEAST_EXPECT(t.getPreferred(Seq{5})->id == h["a"].id());
593 // NOLINTEND(bugprone-unchecked-optional-access)
594
606 t.remove(h["acf"]);
607 t.insert(h["abde"]);
608
609 // NOLINTBEGIN(bugprone-unchecked-optional-access)
610 BEAST_EXPECT(t.getPreferred(Seq{1})->id == h["abde"].id());
611 BEAST_EXPECT(t.getPreferred(Seq{2})->id == h["abde"].id());
612 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abde"].id());
613 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["ab"].id());
614 BEAST_EXPECT(t.getPreferred(Seq{5})->id == h["ab"].id());
615 // NOLINTEND(bugprone-unchecked-optional-access)
616 }
617 }
618
619 void
620 testRootRelated()
621 {
622 using namespace csf;
623 // Since the root is a special node that breaks the no-single child
624 // invariant, do some tests that exercise it.
625
626 LedgerTrie<Ledger> t;
627 LedgerHistoryHelper h;
628 BEAST_EXPECT(!t.remove(h[""]));
629 BEAST_EXPECT(t.branchSupport(h[""]) == 0);
630 BEAST_EXPECT(t.tipSupport(h[""]) == 0);
631
632 t.insert(h["a"]);
633 BEAST_EXPECT(t.checkInvariants());
634 BEAST_EXPECT(t.branchSupport(h[""]) == 1);
635 BEAST_EXPECT(t.tipSupport(h[""]) == 0);
636
637 t.insert(h["e"]);
638 BEAST_EXPECT(t.checkInvariants());
639 BEAST_EXPECT(t.branchSupport(h[""]) == 2);
640 BEAST_EXPECT(t.tipSupport(h[""]) == 0);
641
642 BEAST_EXPECT(t.remove(h["e"]));
643 BEAST_EXPECT(t.checkInvariants());
644 BEAST_EXPECT(t.branchSupport(h[""]) == 1);
645 BEAST_EXPECT(t.tipSupport(h[""]) == 0);
646 }
647
648 void
649 testStress()
650 {
651 using namespace csf;
652 LedgerTrie<Ledger> t;
653 LedgerHistoryHelper h;
654
655 // Test quasi-randomly add/remove supporting for different ledgers
656 // from a branching history.
657
658 // Ledgers have sequence 1,2,3,4
659 std::uint32_t const depthConst = 4;
660 // Each ledger has 4 possible children
661 std::uint32_t const width = 4;
662
663 std::uint32_t const iterations = 10000;
664
665 // Use explicit seed to have same results for CI
666 // NOLINTNEXTLINE(bugprone-random-generator-seed): fixed seed for reproducible test
667 std::mt19937 gen{42};
668 std::uniform_int_distribution<> depthDist(0, depthConst - 1);
669 std::uniform_int_distribution<> widthDist(0, width - 1);
670 std::uniform_int_distribution<> flip(0, 1);
671 for (std::uint32_t i = 0; i < iterations; ++i)
672 {
673 // pick a random ledger history
674 std::string curr;
675 char const depth = depthDist(gen);
676 char offset = 0;
677 for (char d = 0; d < depth; ++d)
678 {
679 char const a = offset + widthDist(gen);
680 curr += a;
681 offset = (a + 1) * width;
682 }
683
684 // 50-50 to add remove
685 if (flip(gen) == 0)
686 {
687 t.insert(h[curr]);
688 }
689 else
690 {
691 t.remove(h[curr]);
692 }
693 if (!BEAST_EXPECT(t.checkInvariants()))
694 return;
695 }
696 }
697
698 void
699 run() override
700 {
701 testInsert();
702 testRemove();
703 testEmpty();
704 testSupport();
705 testGetPreferred();
706 testRootRelated();
707 testStress();
708 }
709};
710
711BEAST_DEFINE_TESTSUITE(LedgerTrie, consensus, xrpl);
712} // namespace xrpl::test
beast::unit_test::Suite
A testsuite class.
Definition suite.h:50
xrpl::LedgerTrie
Ancestry trie of ledgers.
Definition LedgerTrie.h:323
xrpl::LedgerTrie::tipSupport
std::uint32_t tipSupport(Ledger const &ledger) const
Return count of tip support for the specific ledger.
Definition LedgerTrie.h:569
xrpl::LedgerTrie::empty
bool empty() const
Return whether the trie is tracking any ledgers.
Definition LedgerTrie.h:760
xrpl::LedgerTrie::checkInvariants
bool checkInvariants() const
Check the compressed trie and support invariants.
Definition LedgerTrie.h:789
xrpl::LedgerTrie::branchSupport
std::uint32_t branchSupport(Ledger const &ledger) const
Return the count of branch support for the specific ledger.
Definition LedgerTrie.h:583
xrpl::LedgerTrie::getPreferred
std::optional< SpanTip< Ledger > > getPreferred(Seq const largestIssued) const
Return the preferred ledger ID.
Definition LedgerTrie.h:657
xrpl::LedgerTrie::insert
void insert(Ledger const &ledger, std::uint32_t count=1)
Insert and/or increment the support for the given ledger.
Definition LedgerTrie.h:425
xrpl::LedgerTrie::remove
bool remove(Ledger const &ledger, std::uint32_t count=1)
Decrease support for a ledger, removing and compressing if possible.
Definition LedgerTrie.h:511
xrpl::test::LedgerTrie_test
Definition LedgerTrie_test.cpp:14
xrpl::test::LedgerTrie_test::testSupport
void testSupport()
Definition LedgerTrie_test.cpp:295
xrpl::test::LedgerTrie_test::testGetPreferred
void testGetPreferred()
Definition LedgerTrie_test.cpp:342
xrpl::test::LedgerTrie_test::testEmpty
void testEmpty()
Definition LedgerTrie_test.cpp:275
xrpl::test::LedgerTrie_test::testInsert
void testInsert()
Definition LedgerTrie_test.cpp:16
xrpl::test::LedgerTrie_test::testStress
void testStress()
Definition LedgerTrie_test.cpp:649
xrpl::test::LedgerTrie_test::testRemove
void testRemove()
Definition LedgerTrie_test.cpp:143
xrpl::test::LedgerTrie_test::run
void run() override
Runs the suite.
Definition LedgerTrie_test.cpp:699
xrpl::test::LedgerTrie_test::testRootRelated
void testRootRelated()
Definition LedgerTrie_test.cpp:620
xrpl::test::BEAST_DEFINE_TESTSUITE
BEAST_DEFINE_TESTSUITE(AMMClawback, app, xrpl)
xrpl
Use hash_* containers for keys that do not need a cryptographically secure hashing algorithm.
Definition algorithm.h:5
xrpl::test::jtx::Seq
Set the sequence number on a JTx.
Definition seq.h:12
Generated by doxygen 1.16.1