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