xrpld
Loading...
Searching...
No Matches
LedgerTrie.cpp
1#include <xrpl/consensus/LedgerTrie.h>
2
3#include <csf/ledgers.h>
4#include <gtest/gtest.h>
5
6#include <cstdint>
7#include <optional>
8#include <random>
9
10namespace xrpl::test {
11
20class LedgerTrieTest : public ::testing::Test
21{
22protected:
26};
27
28TEST_F(LedgerTrieTest, insert_single_entry_by_itself)
29{
31 LedgerHistoryHelper h;
32 t.insert(h["abc"]);
33 EXPECT_TRUE(t.checkInvariants());
34 EXPECT_TRUE(t.tipSupport(h["abc"]) == 1);
35 EXPECT_TRUE(t.branchSupport(h["abc"]) == 1);
36
37 t.insert(h["abc"]);
38 EXPECT_TRUE(t.checkInvariants());
39 EXPECT_TRUE(t.tipSupport(h["abc"]) == 2);
40 EXPECT_TRUE(t.branchSupport(h["abc"]) == 2);
41}
42
43TEST_F(LedgerTrieTest, insert_suffix_of_existing_extending_tree)
44{
46 LedgerHistoryHelper h;
47 t.insert(h["abc"]);
48 EXPECT_TRUE(t.checkInvariants());
49 // extend with no siblings
50 t.insert(h["abcd"]);
51 EXPECT_TRUE(t.checkInvariants());
52
53 EXPECT_TRUE(t.tipSupport(h["abc"]) == 1);
54 EXPECT_TRUE(t.branchSupport(h["abc"]) == 2);
55 EXPECT_TRUE(t.tipSupport(h["abcd"]) == 1);
56 EXPECT_TRUE(t.branchSupport(h["abcd"]) == 1);
57
58 // extend with existing sibling
59 t.insert(h["abce"]);
60 EXPECT_TRUE(t.tipSupport(h["abc"]) == 1);
61 EXPECT_TRUE(t.branchSupport(h["abc"]) == 3);
62 EXPECT_TRUE(t.tipSupport(h["abcd"]) == 1);
63 EXPECT_TRUE(t.branchSupport(h["abcd"]) == 1);
64 EXPECT_TRUE(t.tipSupport(h["abce"]) == 1);
65 EXPECT_TRUE(t.branchSupport(h["abce"]) == 1);
66}
67
68TEST_F(LedgerTrieTest, insert_uncommitted_of_existing_node)
69{
71 LedgerHistoryHelper h;
72 t.insert(h["abcd"]);
73 EXPECT_TRUE(t.checkInvariants());
74 // uncommitted with no siblings
75 t.insert(h["abcdf"]);
76 EXPECT_TRUE(t.checkInvariants());
77
78 EXPECT_TRUE(t.tipSupport(h["abcd"]) == 1);
79 EXPECT_TRUE(t.branchSupport(h["abcd"]) == 2);
80 EXPECT_TRUE(t.tipSupport(h["abcdf"]) == 1);
81 EXPECT_TRUE(t.branchSupport(h["abcdf"]) == 1);
82
83 // uncommitted with existing child
84 t.insert(h["abc"]);
85 EXPECT_TRUE(t.checkInvariants());
86
87 EXPECT_TRUE(t.tipSupport(h["abc"]) == 1);
88 EXPECT_TRUE(t.branchSupport(h["abc"]) == 3);
89 EXPECT_TRUE(t.tipSupport(h["abcd"]) == 1);
90 EXPECT_TRUE(t.branchSupport(h["abcd"]) == 2);
91 EXPECT_TRUE(t.tipSupport(h["abcdf"]) == 1);
92 EXPECT_TRUE(t.branchSupport(h["abcdf"]) == 1);
93}
94
95TEST_F(LedgerTrieTest, insert_suffix_uncommitted_of_existing_node)
96{
98 LedgerHistoryHelper h;
99 t.insert(h["abcd"]);
100 EXPECT_TRUE(t.checkInvariants());
101 t.insert(h["abce"]);
102 EXPECT_TRUE(t.checkInvariants());
103
104 EXPECT_TRUE(t.tipSupport(h["abc"]) == 0);
105 EXPECT_TRUE(t.branchSupport(h["abc"]) == 2);
106 EXPECT_TRUE(t.tipSupport(h["abcd"]) == 1);
107 EXPECT_TRUE(t.branchSupport(h["abcd"]) == 1);
108 EXPECT_TRUE(t.tipSupport(h["abce"]) == 1);
109 EXPECT_TRUE(t.branchSupport(h["abce"]) == 1);
110}
111
112TEST_F(LedgerTrieTest, insert_suffix_uncommitted_with_existing_child)
113{
114 // abcd : abcde, abcf
115
117 LedgerHistoryHelper h;
118 t.insert(h["abcd"]);
119 EXPECT_TRUE(t.checkInvariants());
120 t.insert(h["abcde"]);
121 EXPECT_TRUE(t.checkInvariants());
122 t.insert(h["abcf"]);
123 EXPECT_TRUE(t.checkInvariants());
124
125 EXPECT_TRUE(t.tipSupport(h["abc"]) == 0);
126 EXPECT_TRUE(t.branchSupport(h["abc"]) == 3);
127 EXPECT_TRUE(t.tipSupport(h["abcd"]) == 1);
128 EXPECT_TRUE(t.branchSupport(h["abcd"]) == 2);
129 EXPECT_TRUE(t.tipSupport(h["abcf"]) == 1);
130 EXPECT_TRUE(t.branchSupport(h["abcf"]) == 1);
131 EXPECT_TRUE(t.tipSupport(h["abcde"]) == 1);
132 EXPECT_TRUE(t.branchSupport(h["abcde"]) == 1);
133}
134
135TEST_F(LedgerTrieTest, insert_multiple_counts)
136{
138 LedgerHistoryHelper h;
139 t.insert(h["ab"], 4);
140 EXPECT_TRUE(t.tipSupport(h["ab"]) == 4);
141 EXPECT_TRUE(t.branchSupport(h["ab"]) == 4);
142 EXPECT_TRUE(t.tipSupport(h["a"]) == 0);
143 EXPECT_TRUE(t.branchSupport(h["a"]) == 4);
144
145 t.insert(h["abc"], 2);
146 EXPECT_TRUE(t.tipSupport(h["abc"]) == 2);
147 EXPECT_TRUE(t.branchSupport(h["abc"]) == 2);
148 EXPECT_TRUE(t.tipSupport(h["ab"]) == 4);
149 EXPECT_TRUE(t.branchSupport(h["ab"]) == 6);
150 EXPECT_TRUE(t.tipSupport(h["a"]) == 0);
151 EXPECT_TRUE(t.branchSupport(h["a"]) == 6);
152}
153
154TEST_F(LedgerTrieTest, remove_not_in_trie)
155{
157 LedgerHistoryHelper h;
158 t.insert(h["abc"]);
159
160 EXPECT_TRUE(!t.remove(h["ab"]));
161 EXPECT_TRUE(t.checkInvariants());
162 EXPECT_TRUE(!t.remove(h["a"]));
163 EXPECT_TRUE(t.checkInvariants());
164}
165
166TEST_F(LedgerTrieTest, remove_in_trie_but_with_0_tip_support)
167{
169 LedgerHistoryHelper h;
170 t.insert(h["abcd"]);
171 t.insert(h["abce"]);
172
173 EXPECT_TRUE(t.tipSupport(h["abc"]) == 0);
174 EXPECT_TRUE(t.branchSupport(h["abc"]) == 2);
175 EXPECT_TRUE(!t.remove(h["abc"]));
176 EXPECT_TRUE(t.checkInvariants());
177 EXPECT_TRUE(t.tipSupport(h["abc"]) == 0);
178 EXPECT_TRUE(t.branchSupport(h["abc"]) == 2);
179}
180
181TEST_F(LedgerTrieTest, remove_in_trie_with_multiple_tip_support)
182{
184 LedgerHistoryHelper h;
185 t.insert(h["abc"], 2);
186
187 EXPECT_TRUE(t.tipSupport(h["abc"]) == 2);
188 EXPECT_TRUE(t.remove(h["abc"]));
189 EXPECT_TRUE(t.checkInvariants());
190 EXPECT_TRUE(t.tipSupport(h["abc"]) == 1);
191
192 t.insert(h["abc"], 1);
193 EXPECT_TRUE(t.tipSupport(h["abc"]) == 2);
194 EXPECT_TRUE(t.remove(h["abc"], 2));
195 EXPECT_TRUE(t.checkInvariants());
196 EXPECT_TRUE(t.tipSupport(h["abc"]) == 0);
197
198 t.insert(h["abc"], 3);
199 EXPECT_TRUE(t.tipSupport(h["abc"]) == 3);
200 EXPECT_TRUE(t.remove(h["abc"], 300));
201 EXPECT_TRUE(t.checkInvariants());
202 EXPECT_TRUE(t.tipSupport(h["abc"]) == 0);
203}
204
205TEST_F(LedgerTrieTest, remove_in_trie_with_1_tip_support_no_children)
206{
208 LedgerHistoryHelper h;
209 t.insert(h["ab"]);
210 t.insert(h["abc"]);
211
212 EXPECT_TRUE(t.tipSupport(h["ab"]) == 1);
213 EXPECT_TRUE(t.branchSupport(h["ab"]) == 2);
214 EXPECT_TRUE(t.tipSupport(h["abc"]) == 1);
215 EXPECT_TRUE(t.branchSupport(h["abc"]) == 1);
216
217 EXPECT_TRUE(t.remove(h["abc"]));
218 EXPECT_TRUE(t.checkInvariants());
219 EXPECT_TRUE(t.tipSupport(h["ab"]) == 1);
220 EXPECT_TRUE(t.branchSupport(h["ab"]) == 1);
221 EXPECT_TRUE(t.tipSupport(h["abc"]) == 0);
222 EXPECT_TRUE(t.branchSupport(h["abc"]) == 0);
223}
224
225TEST_F(LedgerTrieTest, remove_in_trie_with_1_tip_support_1_child)
226{
228 LedgerHistoryHelper h;
229 t.insert(h["ab"]);
230 t.insert(h["abc"]);
231 t.insert(h["abcd"]);
232
233 EXPECT_TRUE(t.tipSupport(h["abc"]) == 1);
234 EXPECT_TRUE(t.branchSupport(h["abc"]) == 2);
235 EXPECT_TRUE(t.tipSupport(h["abcd"]) == 1);
236 EXPECT_TRUE(t.branchSupport(h["abcd"]) == 1);
237
238 EXPECT_TRUE(t.remove(h["abc"]));
239 EXPECT_TRUE(t.checkInvariants());
240 EXPECT_TRUE(t.tipSupport(h["abc"]) == 0);
241 EXPECT_TRUE(t.branchSupport(h["abc"]) == 1);
242 EXPECT_TRUE(t.tipSupport(h["abcd"]) == 1);
243 EXPECT_TRUE(t.branchSupport(h["abcd"]) == 1);
244}
245
246TEST_F(LedgerTrieTest, remove_in_trie_with_1_tip_support_multiple_children)
247{
249 LedgerHistoryHelper h;
250 t.insert(h["ab"]);
251 t.insert(h["abc"]);
252 t.insert(h["abcd"]);
253 t.insert(h["abce"]);
254
255 EXPECT_TRUE(t.tipSupport(h["abc"]) == 1);
256 EXPECT_TRUE(t.branchSupport(h["abc"]) == 3);
257
258 EXPECT_TRUE(t.remove(h["abc"]));
259 EXPECT_TRUE(t.checkInvariants());
260 EXPECT_TRUE(t.tipSupport(h["abc"]) == 0);
261 EXPECT_TRUE(t.branchSupport(h["abc"]) == 2);
262}
263
264TEST_F(LedgerTrieTest, remove_in_trie_with_1_tip_support_parent_compaction)
265{
267 LedgerHistoryHelper h;
268 t.insert(h["ab"]);
269 t.insert(h["abc"]);
270 t.insert(h["abd"]);
271 EXPECT_TRUE(t.checkInvariants());
272 t.remove(h["ab"]);
273 EXPECT_TRUE(t.checkInvariants());
274 EXPECT_TRUE(t.tipSupport(h["abc"]) == 1);
275 EXPECT_TRUE(t.tipSupport(h["abd"]) == 1);
276 EXPECT_TRUE(t.tipSupport(h["ab"]) == 0);
277 EXPECT_TRUE(t.branchSupport(h["ab"]) == 2);
278
279 t.remove(h["abd"]);
280 EXPECT_TRUE(t.checkInvariants());
281
282 EXPECT_TRUE(t.tipSupport(h["abc"]) == 1);
283 EXPECT_TRUE(t.branchSupport(h["ab"]) == 1);
284}
285
287{
289 LedgerHistoryHelper h;
290 EXPECT_TRUE(t.empty());
291
292 Ledger const genesis = h[""];
293 t.insert(genesis);
294 EXPECT_TRUE(!t.empty());
295 t.remove(genesis);
296 EXPECT_TRUE(t.empty());
297
298 t.insert(h["abc"]);
299 EXPECT_TRUE(!t.empty());
300 t.remove(h["abc"]);
301 EXPECT_TRUE(t.empty());
302}
303
305{
307 LedgerHistoryHelper h;
308 EXPECT_TRUE(t.tipSupport(h["a"]) == 0);
309 EXPECT_TRUE(t.tipSupport(h["axy"]) == 0);
310
311 EXPECT_TRUE(t.branchSupport(h["a"]) == 0);
312 EXPECT_TRUE(t.branchSupport(h["axy"]) == 0);
313
314 t.insert(h["abc"]);
315 EXPECT_TRUE(t.tipSupport(h["a"]) == 0);
316 EXPECT_TRUE(t.tipSupport(h["ab"]) == 0);
317 EXPECT_TRUE(t.tipSupport(h["abc"]) == 1);
318 EXPECT_TRUE(t.tipSupport(h["abcd"]) == 0);
319
320 EXPECT_TRUE(t.branchSupport(h["a"]) == 1);
321 EXPECT_TRUE(t.branchSupport(h["ab"]) == 1);
322 EXPECT_TRUE(t.branchSupport(h["abc"]) == 1);
323 EXPECT_TRUE(t.branchSupport(h["abcd"]) == 0);
324
325 t.insert(h["abe"]);
326 EXPECT_TRUE(t.tipSupport(h["a"]) == 0);
327 EXPECT_TRUE(t.tipSupport(h["ab"]) == 0);
328 EXPECT_TRUE(t.tipSupport(h["abc"]) == 1);
329 EXPECT_TRUE(t.tipSupport(h["abe"]) == 1);
330
331 EXPECT_TRUE(t.branchSupport(h["a"]) == 2);
332 EXPECT_TRUE(t.branchSupport(h["ab"]) == 2);
333 EXPECT_TRUE(t.branchSupport(h["abc"]) == 1);
334 EXPECT_TRUE(t.branchSupport(h["abe"]) == 1);
335
336 t.remove(h["abc"]);
337 EXPECT_TRUE(t.tipSupport(h["a"]) == 0);
338 EXPECT_TRUE(t.tipSupport(h["ab"]) == 0);
339 EXPECT_TRUE(t.tipSupport(h["abc"]) == 0);
340 EXPECT_TRUE(t.tipSupport(h["abe"]) == 1);
341
342 EXPECT_TRUE(t.branchSupport(h["a"]) == 1);
343 EXPECT_TRUE(t.branchSupport(h["ab"]) == 1);
344 EXPECT_TRUE(t.branchSupport(h["abc"]) == 0);
345 EXPECT_TRUE(t.branchSupport(h["abe"]) == 1);
346}
347
348TEST_F(LedgerTrieTest, preferred_empty)
349{
350 LedgerTrie<Ledger> const t;
351 EXPECT_TRUE(t.getPreferred(Seq{0}) == std::nullopt);
352 EXPECT_TRUE(t.getPreferred(Seq{2}) == std::nullopt);
353}
354
355TEST_F(LedgerTrieTest, preferred_genesis_support_is_not_empty)
356{
358 LedgerHistoryHelper h;
359 Ledger const genesis = h[""];
360 t.insert(genesis);
361
362 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
363 EXPECT_TRUE(t.getPreferred(Seq{0})->id == genesis.id());
364 EXPECT_TRUE(t.remove(genesis));
365 EXPECT_TRUE(t.getPreferred(Seq{0}) == std::nullopt);
366 EXPECT_TRUE(!t.remove(genesis));
367}
368
369TEST_F(LedgerTrieTest, preferred_single_node_no_children)
370{
372 LedgerHistoryHelper h;
373 t.insert(h["abc"]);
374
375 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
376 EXPECT_TRUE(t.getPreferred(Seq{3})->id == h["abc"].id());
377}
378
379TEST_F(LedgerTrieTest, preferred_single_node_smaller_child_support)
380{
382 LedgerHistoryHelper h;
383 t.insert(h["abc"]);
384 t.insert(h["abcd"]);
385
386 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
387 EXPECT_TRUE(t.getPreferred(Seq{3})->id == h["abc"].id());
388
389 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
390 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["abc"].id());
391}
392
393TEST_F(LedgerTrieTest, preferred_single_node_larger_child)
394{
396 LedgerHistoryHelper h;
397 t.insert(h["abc"]);
398 t.insert(h["abcd"], 2);
399
400 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
401 EXPECT_TRUE(t.getPreferred(Seq{3})->id == h["abcd"].id());
402
403 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
404 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["abcd"].id());
405}
406
407TEST_F(LedgerTrieTest, preferred_single_node_smaller_children_support)
408{
410 LedgerHistoryHelper h;
411 t.insert(h["abc"]);
412 t.insert(h["abcd"]);
413 t.insert(h["abce"]);
414
415 // NOLINTBEGIN(bugprone-unchecked-optional-access)
416 EXPECT_TRUE(t.getPreferred(Seq{3})->id == h["abc"].id());
417 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["abc"].id());
418
419 t.insert(h["abc"]);
420
421 EXPECT_TRUE(t.getPreferred(Seq{3})->id == h["abc"].id());
422 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["abc"].id());
423 // NOLINTEND(bugprone-unchecked-optional-access)
424}
425
426TEST_F(LedgerTrieTest, preferred_single_node_larger_children)
427{
429 LedgerHistoryHelper h;
430 t.insert(h["abc"]);
431 t.insert(h["abcd"], 2);
432 t.insert(h["abce"]);
433
434 // NOLINTBEGIN(bugprone-unchecked-optional-access)
435 EXPECT_TRUE(t.getPreferred(Seq{3})->id == h["abc"].id());
436 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["abc"].id());
437
438 t.insert(h["abcd"]);
439
440 EXPECT_TRUE(t.getPreferred(Seq{3})->id == h["abcd"].id());
441 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["abcd"].id());
442 // NOLINTEND(bugprone-unchecked-optional-access)
443}
444
445TEST_F(LedgerTrieTest, preferred_tie_breaker_by_id)
446{
448 LedgerHistoryHelper h;
449 t.insert(h["abcd"], 2);
450 t.insert(h["abce"], 2);
451
452 EXPECT_TRUE(h["abce"].id() > h["abcd"].id());
453
454 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
455 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["abce"].id());
456
457 t.insert(h["abcd"]);
458 EXPECT_TRUE(h["abce"].id() > h["abcd"].id());
459
460 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
461 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["abcd"].id());
462}
463
464TEST_F(LedgerTrieTest, preferred_tie_breaker_not_needed)
465{
467 LedgerHistoryHelper h;
468 t.insert(h["abc"]);
469 t.insert(h["abcd"]);
470 t.insert(h["abce"], 2);
471 // abce only has a margin of 1, but it owns the tie-breaker
472 EXPECT_TRUE(h["abce"].id() > h["abcd"].id());
473
474 // NOLINTBEGIN(bugprone-unchecked-optional-access)
475 EXPECT_TRUE(t.getPreferred(Seq{3})->id == h["abce"].id());
476 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["abce"].id());
477
478 // Switch support from abce to abcd, tie-breaker now needed
479 t.remove(h["abce"]);
480 t.insert(h["abcd"]);
481
482 EXPECT_TRUE(t.getPreferred(Seq{3})->id == h["abc"].id());
483 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["abc"].id());
484 // NOLINTEND(bugprone-unchecked-optional-access)
485}
486
487TEST_F(LedgerTrieTest, preferred_single_node_larger_grand_child)
488{
490 LedgerHistoryHelper h;
491 t.insert(h["abc"]);
492 t.insert(h["abcd"], 2);
493 t.insert(h["abcde"], 4);
494
495 // NOLINTBEGIN(bugprone-unchecked-optional-access)
496 EXPECT_TRUE(t.getPreferred(Seq{3})->id == h["abcde"].id());
497 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["abcde"].id());
498 EXPECT_TRUE(t.getPreferred(Seq{5})->id == h["abcde"].id());
499 // NOLINTEND(bugprone-unchecked-optional-access)
500}
501
502TEST_F(LedgerTrieTest, preferred_too_much_uncommitted_support_from_competing_branches)
503{
505 LedgerHistoryHelper h;
506 t.insert(h["abc"]);
507 t.insert(h["abcde"], 2);
508 t.insert(h["abcfg"], 2);
509 // 'de' and 'fg' are tied without 'abc' vote
510 // NOLINTBEGIN(bugprone-unchecked-optional-access)
511 EXPECT_TRUE(t.getPreferred(Seq{3})->id == h["abc"].id());
512 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["abc"].id());
513 EXPECT_TRUE(t.getPreferred(Seq{5})->id == h["abc"].id());
514
515 t.remove(h["abc"]);
516 t.insert(h["abcd"]);
517
518 // 'de' branch has 3 votes to 2, so earlier sequences see it as preferred
519 EXPECT_TRUE(t.getPreferred(Seq{3})->id == h["abcde"].id());
520 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["abcde"].id());
521
522 // However, if you validated a ledger with Seq 5, potentially on
523 // a different branch, you do not yet know if they chose abcd
524 // or abcf because of you, so abc remains preferred
525 EXPECT_TRUE(t.getPreferred(Seq{5})->id == h["abc"].id());
526 // NOLINTEND(bugprone-unchecked-optional-access)
527}
528
529TEST_F(LedgerTrieTest, preferred_changing_largestseq_perspective_changes_preferred_branch)
530{
544 LedgerHistoryHelper h;
545 t.insert(h["ab"]);
546 t.insert(h["ac"]);
547 t.insert(h["acf"]);
548 t.insert(h["abde"], 2);
549
550 // B has more branch support
551 // NOLINTBEGIN(bugprone-unchecked-optional-access)
552 EXPECT_TRUE(t.getPreferred(Seq{1})->id == h["ab"].id());
553 EXPECT_TRUE(t.getPreferred(Seq{2})->id == h["ab"].id());
554
555 // But if you last validated D,F or E, you do not yet know
556 // if someone used that validation to commit to B or C
557 EXPECT_TRUE(t.getPreferred(Seq{3})->id == h["a"].id());
558 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["a"].id());
559 // NOLINTEND(bugprone-unchecked-optional-access)
560
573 t.remove(h["abde"]);
574 t.insert(h["abdeg"]);
575
576 // NOLINTBEGIN(bugprone-unchecked-optional-access)
577 EXPECT_TRUE(t.getPreferred(Seq{1})->id == h["ab"].id());
578 EXPECT_TRUE(t.getPreferred(Seq{2})->id == h["ab"].id());
579 EXPECT_TRUE(t.getPreferred(Seq{3})->id == h["a"].id());
580 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["a"].id());
581 EXPECT_TRUE(t.getPreferred(Seq{5})->id == h["a"].id());
582 // NOLINTEND(bugprone-unchecked-optional-access)
583
596 t.remove(h["ac"]);
597 t.insert(h["abh"]);
598
599 // NOLINTBEGIN(bugprone-unchecked-optional-access)
600 EXPECT_TRUE(t.getPreferred(Seq{1})->id == h["ab"].id());
601 EXPECT_TRUE(t.getPreferred(Seq{2})->id == h["ab"].id());
602 EXPECT_TRUE(t.getPreferred(Seq{3})->id == h["ab"].id());
603 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["a"].id());
604 EXPECT_TRUE(t.getPreferred(Seq{5})->id == h["a"].id());
605 // NOLINTEND(bugprone-unchecked-optional-access)
606
619 t.remove(h["acf"]);
620 t.insert(h["abde"]);
621
622 // NOLINTBEGIN(bugprone-unchecked-optional-access)
623 EXPECT_TRUE(t.getPreferred(Seq{1})->id == h["abde"].id());
624 EXPECT_TRUE(t.getPreferred(Seq{2})->id == h["abde"].id());
625 EXPECT_TRUE(t.getPreferred(Seq{3})->id == h["abde"].id());
626 EXPECT_TRUE(t.getPreferred(Seq{4})->id == h["ab"].id());
627 EXPECT_TRUE(t.getPreferred(Seq{5})->id == h["ab"].id());
628 // NOLINTEND(bugprone-unchecked-optional-access)
629}
630
631TEST_F(LedgerTrieTest, root_related)
632{
633 // Since the root is a special node that breaks the no-single child
634 // invariant, do some tests that exercise it.
635
637 LedgerHistoryHelper h;
638 EXPECT_TRUE(!t.remove(h[""]));
639 EXPECT_TRUE(t.branchSupport(h[""]) == 0);
640 EXPECT_TRUE(t.tipSupport(h[""]) == 0);
641
642 t.insert(h["a"]);
643 EXPECT_TRUE(t.checkInvariants());
644 EXPECT_TRUE(t.branchSupport(h[""]) == 1);
645 EXPECT_TRUE(t.tipSupport(h[""]) == 0);
646
647 t.insert(h["e"]);
648 EXPECT_TRUE(t.checkInvariants());
649 EXPECT_TRUE(t.branchSupport(h[""]) == 2);
650 EXPECT_TRUE(t.tipSupport(h[""]) == 0);
651
652 EXPECT_TRUE(t.remove(h["e"]));
653 EXPECT_TRUE(t.checkInvariants());
654 EXPECT_TRUE(t.branchSupport(h[""]) == 1);
655 EXPECT_TRUE(t.tipSupport(h[""]) == 0);
656}
657
659{
661 LedgerHistoryHelper h;
662
663 // Test quasi-randomly add/remove supporting for different ledgers
664 // from a branching history.
665
666 // Ledgers have sequence 1,2,3,4
667 std::uint32_t const depthConst = 4;
668 // Each ledger has 4 possible children
669 std::uint32_t const width = 4;
670
671 std::uint32_t const iterations = 10000;
672
673 // Use explicit seed to have same results for CI
674 // NOLINTNEXTLINE(bugprone-random-generator-seed): fixed seed for reproducible test
675 std::mt19937 gen{42};
676 std::uniform_int_distribution<> depthDist(0, depthConst - 1);
677 std::uniform_int_distribution<> widthDist(0, width - 1);
679 for (std::uint32_t i = 0; i < iterations; ++i)
680 {
681 // pick a random ledger history
682 std::string curr;
683 char const depth = depthDist(gen);
684 char offset = 0;
685 for (char d = 0; d < depth; ++d)
686 {
687 char const a = offset + widthDist(gen);
688 curr += a;
689 offset = (a + 1) * width;
690 }
691
692 // 50-50 to add remove
693 if (flip(gen) == 0)
694 {
695 t.insert(h[curr]);
696 }
697 else
698 {
699 t.remove(h[curr]);
700 }
701 EXPECT_TRUE(t.checkInvariants());
702 if (!t.checkInvariants())
703 return;
704 }
705}
706
707} // namespace xrpl::test
Ancestry trie of ledgers.
Definition LedgerTrie.h:331
std::uint32_t tipSupport(Ledger const &ledger) const
Return count of tip support for the specific ledger.
Definition LedgerTrie.h:582
bool empty() const
Return whether the trie is tracking any ledgers.
Definition LedgerTrie.h:776
bool checkInvariants() const
Check the compressed trie and support invariants.
Definition LedgerTrie.h:808
std::uint32_t branchSupport(Ledger const &ledger) const
Return the count of branch support for the specific ledger.
Definition LedgerTrie.h:597
std::optional< SpanTip< Ledger > > getPreferred(Seq const largestIssued) const
Return the preferred ledger ID.
Definition LedgerTrie.h:672
void insert(Ledger const &ledger, std::uint32_t count=1)
Insert and/or increment the support for the given ledger.
Definition LedgerTrie.h:436
bool remove(Ledger const &ledger, std::uint32_t count=1)
Decrease support for a ledger, removing and compressing if possible.
Definition LedgerTrie.h:523
Fixture that scopes the csf names these tests use.
csf::LedgerHistoryHelper LedgerHistoryHelper
A ledger is a set of observed transactions and a sequence number identifying the ledger.
Definition ledgers.h:48
TaggedInteger< std::uint32_t, SeqTag > Seq
Definition ledgers.h:53
TEST_F(BaseUintDeathTest, from_raw_size_mismatch)
Definition base_uint.cpp:73
Helper for writing unit tests with controlled ledger histories.
Definition ledgers.h:328
Set the sequence number on a JTx.
Definition seq.h:16