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