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 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> 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 genesis = h[""];
356 t.insert(genesis);
357 BEAST_EXPECT(t.getPreferred(Seq{0})->id == genesis.id());
358 BEAST_EXPECT(t.remove(genesis));
359 BEAST_EXPECT(t.getPreferred(Seq{0}) == std::nullopt);
360 BEAST_EXPECT(!t.remove(genesis));
361 }
362 // Single node no children
363 {
364 LedgerTrie<Ledger> t;
365 LedgerHistoryHelper h;
366 t.insert(h["abc"]);
367 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abc"].id());
368 }
369 // Single node smaller child support
370 {
371 LedgerTrie<Ledger> t;
372 LedgerHistoryHelper h;
373 t.insert(h["abc"]);
374 t.insert(h["abcd"]);
375 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abc"].id());
376 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abc"].id());
377 }
378 // Single node larger child
379 {
380 LedgerTrie<Ledger> t;
381 LedgerHistoryHelper h;
382 t.insert(h["abc"]);
383 t.insert(h["abcd"], 2);
384 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abcd"].id());
385 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abcd"].id());
386 }
387 // Single node smaller children support
388 {
389 LedgerTrie<Ledger> t;
390 LedgerHistoryHelper h;
391 t.insert(h["abc"]);
392 t.insert(h["abcd"]);
393 t.insert(h["abce"]);
394 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abc"].id());
395 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abc"].id());
396
397 t.insert(h["abc"]);
398 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abc"].id());
399 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abc"].id());
400 }
401 // Single node larger children
402 {
403 LedgerTrie<Ledger> t;
404 LedgerHistoryHelper h;
405 t.insert(h["abc"]);
406 t.insert(h["abcd"], 2);
407 t.insert(h["abce"]);
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["abcd"]);
412 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abcd"].id());
413 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abcd"].id());
414 }
415 // Tie-breaker by id
416 {
417 LedgerTrie<Ledger> t;
418 LedgerHistoryHelper h;
419 t.insert(h["abcd"], 2);
420 t.insert(h["abce"], 2);
421
422 BEAST_EXPECT(h["abce"].id() > h["abcd"].id());
423 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abce"].id());
424
425 t.insert(h["abcd"]);
426 BEAST_EXPECT(h["abce"].id() > h["abcd"].id());
427 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abcd"].id());
428 }
429
430 // Tie-breaker not needed
431 {
432 LedgerTrie<Ledger> t;
433 LedgerHistoryHelper h;
434 t.insert(h["abc"]);
435 t.insert(h["abcd"]);
436 t.insert(h["abce"], 2);
437 // abce only has a margin of 1, but it owns the tie-breaker
438 BEAST_EXPECT(h["abce"].id() > h["abcd"].id());
439 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abce"].id());
440 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abce"].id());
441
442 // Switch support from abce to abcd, tie-breaker now needed
443 t.remove(h["abce"]);
444 t.insert(h["abcd"]);
445 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abc"].id());
446 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abc"].id());
447 }
448
449 // Single node larger grand child
450 {
451 LedgerTrie<Ledger> t;
452 LedgerHistoryHelper h;
453 t.insert(h["abc"]);
454 t.insert(h["abcd"], 2);
455 t.insert(h["abcde"], 4);
456 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abcde"].id());
457 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abcde"].id());
458 BEAST_EXPECT(t.getPreferred(Seq{5})->id == h["abcde"].id());
459 }
460
461 // Too much uncommitted support from competing branches
462 {
463 LedgerTrie<Ledger> t;
464 LedgerHistoryHelper h;
465 t.insert(h["abc"]);
466 t.insert(h["abcde"], 2);
467 t.insert(h["abcfg"], 2);
468 // 'de' and 'fg' are tied without 'abc' vote
469 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abc"].id());
470 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abc"].id());
471 BEAST_EXPECT(t.getPreferred(Seq{5})->id == h["abc"].id());
472
473 t.remove(h["abc"]);
474 t.insert(h["abcd"]);
475
476 // 'de' branch has 3 votes to 2, so earlier sequences see it as
477 // preferred
478 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abcde"].id());
479 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["abcde"].id());
480
481 // However, if you validated a ledger with Seq 5, potentially on
482 // a different branch, you do not yet know if they chose abcd
483 // or abcf because of you, so abc remains preferred
484 BEAST_EXPECT(t.getPreferred(Seq{5})->id == h["abc"].id());
485 }
486
487 // Changing largestSeq perspective changes preferred branch
488 {
500 LedgerTrie<Ledger> t;
501 LedgerHistoryHelper h;
502 t.insert(h["ab"]);
503 t.insert(h["ac"]);
504 t.insert(h["acf"]);
505 t.insert(h["abde"], 2);
506
507 // B has more branch support
508 BEAST_EXPECT(t.getPreferred(Seq{1})->id == h["ab"].id());
509 BEAST_EXPECT(t.getPreferred(Seq{2})->id == h["ab"].id());
510 // But if you last validated D,F or E, you do not yet know
511 // if someone used that validation to commit to B or C
512 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["a"].id());
513 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["a"].id());
514
526 t.remove(h["abde"]);
527 t.insert(h["abdeg"]);
528
529 BEAST_EXPECT(t.getPreferred(Seq{1})->id == h["ab"].id());
530 BEAST_EXPECT(t.getPreferred(Seq{2})->id == h["ab"].id());
531 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["a"].id());
532 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["a"].id());
533 BEAST_EXPECT(t.getPreferred(Seq{5})->id == h["a"].id());
534
546 t.remove(h["ac"]);
547 t.insert(h["abh"]);
548 BEAST_EXPECT(t.getPreferred(Seq{1})->id == h["ab"].id());
549 BEAST_EXPECT(t.getPreferred(Seq{2})->id == h["ab"].id());
550 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["ab"].id());
551 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["a"].id());
552 BEAST_EXPECT(t.getPreferred(Seq{5})->id == h["a"].id());
553
565 t.remove(h["acf"]);
566 t.insert(h["abde"]);
567 BEAST_EXPECT(t.getPreferred(Seq{1})->id == h["abde"].id());
568 BEAST_EXPECT(t.getPreferred(Seq{2})->id == h["abde"].id());
569 BEAST_EXPECT(t.getPreferred(Seq{3})->id == h["abde"].id());
570 BEAST_EXPECT(t.getPreferred(Seq{4})->id == h["ab"].id());
571 BEAST_EXPECT(t.getPreferred(Seq{5})->id == h["ab"].id());
572 }
573 }
574
575 void
576 testRootRelated()
577 {
578 using namespace csf;
579 // Since the root is a special node that breaks the no-single child
580 // invariant, do some tests that exercise it.
581
582 LedgerTrie<Ledger> t;
583 LedgerHistoryHelper h;
584 BEAST_EXPECT(!t.remove(h[""]));
585 BEAST_EXPECT(t.branchSupport(h[""]) == 0);
586 BEAST_EXPECT(t.tipSupport(h[""]) == 0);
587
588 t.insert(h["a"]);
589 BEAST_EXPECT(t.checkInvariants());
590 BEAST_EXPECT(t.branchSupport(h[""]) == 1);
591 BEAST_EXPECT(t.tipSupport(h[""]) == 0);
592
593 t.insert(h["e"]);
594 BEAST_EXPECT(t.checkInvariants());
595 BEAST_EXPECT(t.branchSupport(h[""]) == 2);
596 BEAST_EXPECT(t.tipSupport(h[""]) == 0);
597
598 BEAST_EXPECT(t.remove(h["e"]));
599 BEAST_EXPECT(t.checkInvariants());
600 BEAST_EXPECT(t.branchSupport(h[""]) == 1);
601 BEAST_EXPECT(t.tipSupport(h[""]) == 0);
602 }
603
604 void
605 testStress()
606 {
607 using namespace csf;
608 LedgerTrie<Ledger> t;
609 LedgerHistoryHelper h;
610
611 // Test quasi-randomly add/remove supporting for different ledgers
612 // from a branching history.
613
614 // Ledgers have sequence 1,2,3,4
615 std::uint32_t const depthConst = 4;
616 // Each ledger has 4 possible children
617 std::uint32_t const width = 4;
618
619 std::uint32_t const iterations = 10000;
620
621 // Use explicit seed to have same results for CI
622 std::mt19937 gen{42};
623 std::uniform_int_distribution<> depthDist(0, depthConst - 1);
624 std::uniform_int_distribution<> widthDist(0, width - 1);
625 std::uniform_int_distribution<> flip(0, 1);
626 for (std::uint32_t i = 0; i < iterations; ++i)
627 {
628 // pick a random ledger history
629 std::string curr = "";
630 char depth = depthDist(gen);
631 char offset = 0;
632 for (char d = 0; d < depth; ++d)
633 {
634 char a = offset + widthDist(gen);
635 curr += a;
636 offset = (a + 1) * width;
637 }
638
639 // 50-50 to add remove
640 if (flip(gen) == 0)
641 t.insert(h[curr]);
642 else
643 t.remove(h[curr]);
644 if (!BEAST_EXPECT(t.checkInvariants()))
645 return;
646 }
647 }
648
649 void
650 run() override
651 {
652 testInsert();
653 testRemove();
654 testEmpty();
655 testSupport();
656 testGetPreferred();
657 testRootRelated();
658 testStress();
659 }
660};
661
662BEAST_DEFINE_TESTSUITE(LedgerTrie, consensus, xrpl);
663} // namespace test
664} // namespace xrpl
beast::unit_test::suite
A testsuite class.
Definition suite.h:52
xrpl::LedgerTrie
Ancestry trie of ledgers.
Definition LedgerTrie.h:332
xrpl::LedgerTrie::tipSupport
std::uint32_t tipSupport(Ledger const &ledger) const
Return count of tip support for the specific ledger.
Definition LedgerTrie.h:578
xrpl::LedgerTrie::empty
bool empty() const
Return whether the trie is tracking any ledgers.
Definition LedgerTrie.h:764
xrpl::LedgerTrie::checkInvariants
bool checkInvariants() const
Check the compressed trie and support invariants.
Definition LedgerTrie.h:793
xrpl::LedgerTrie::branchSupport
std::uint32_t branchSupport(Ledger const &ledger) const
Return the count of branch support for the specific ledger.
Definition LedgerTrie.h:592
xrpl::LedgerTrie::getPreferred
std::optional< SpanTip< Ledger > > getPreferred(Seq const largestIssued) const
Return the preferred ledger ID.
Definition LedgerTrie.h:666
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:434
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:522
xrpl::Ledger
Holds a ledger.
Definition Ledger.h:61
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:605
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:650
xrpl::test::LedgerTrie_test::testRootRelated
void testRootRelated()
Definition LedgerTrie_test.cpp:576
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:6
Generated by doxygen 1.9.8