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