xrpld
Toggle main menu visibility
Loading...
Searching...
No Matches
tests
libxrpl
consensus
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
10
namespace
xrpl::test
{
11
20
class
LedgerTrieTest
:
public
::testing::Test
21
{
22
protected
:
23
using
Ledger
=
csf::Ledger
;
24
using
LedgerHistoryHelper
=
csf::LedgerHistoryHelper
;
25
using
Seq
=
Ledger::Seq
;
26
};
27
28
TEST_F
(
LedgerTrieTest
, insert_single_entry_by_itself)
29
{
30
LedgerTrie<Ledger>
t;
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
43
TEST_F
(
LedgerTrieTest
, insert_suffix_of_existing_extending_tree)
44
{
45
LedgerTrie<Ledger>
t;
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
68
TEST_F
(
LedgerTrieTest
, insert_uncommitted_of_existing_node)
69
{
70
LedgerTrie<Ledger>
t;
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
95
TEST_F
(
LedgerTrieTest
, insert_suffix_uncommitted_of_existing_node)
96
{
97
LedgerTrie<Ledger>
t;
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
112
TEST_F
(
LedgerTrieTest
, insert_suffix_uncommitted_with_existing_child)
113
{
114
// abcd : abcde, abcf
115
116
LedgerTrie<Ledger>
t;
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
135
TEST_F
(
LedgerTrieTest
, insert_multiple_counts)
136
{
137
LedgerTrie<Ledger>
t;
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
154
TEST_F
(
LedgerTrieTest
, remove_not_in_trie)
155
{
156
LedgerTrie<Ledger>
t;
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
166
TEST_F
(
LedgerTrieTest
, remove_in_trie_but_with_0_tip_support)
167
{
168
LedgerTrie<Ledger>
t;
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
181
TEST_F
(
LedgerTrieTest
, remove_in_trie_with_multiple_tip_support)
182
{
183
LedgerTrie<Ledger>
t;
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
205
TEST_F
(
LedgerTrieTest
, remove_in_trie_with_1_tip_support_no_children)
206
{
207
LedgerTrie<Ledger>
t;
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
225
TEST_F
(
LedgerTrieTest
, remove_in_trie_with_1_tip_support_1_child)
226
{
227
LedgerTrie<Ledger>
t;
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
246
TEST_F
(
LedgerTrieTest
, remove_in_trie_with_1_tip_support_multiple_children)
247
{
248
LedgerTrie<Ledger>
t;
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
264
TEST_F
(
LedgerTrieTest
, remove_in_trie_with_1_tip_support_parent_compaction)
265
{
266
LedgerTrie<Ledger>
t;
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
286
TEST_F
(
LedgerTrieTest
, empty)
287
{
288
LedgerTrie<Ledger>
t;
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
304
TEST_F
(
LedgerTrieTest
, support)
305
{
306
LedgerTrie<Ledger>
t;
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
348
TEST_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
355
TEST_F
(
LedgerTrieTest
, preferred_genesis_support_is_not_empty)
356
{
357
LedgerTrie<Ledger>
t;
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
369
TEST_F
(
LedgerTrieTest
, preferred_single_node_no_children)
370
{
371
LedgerTrie<Ledger>
t;
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
379
TEST_F
(
LedgerTrieTest
, preferred_single_node_smaller_child_support)
380
{
381
LedgerTrie<Ledger>
t;
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
393
TEST_F
(
LedgerTrieTest
, preferred_single_node_larger_child)
394
{
395
LedgerTrie<Ledger>
t;
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
407
TEST_F
(
LedgerTrieTest
, preferred_single_node_smaller_children_support)
408
{
409
LedgerTrie<Ledger>
t;
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
426
TEST_F
(
LedgerTrieTest
, preferred_single_node_larger_children)
427
{
428
LedgerTrie<Ledger>
t;
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
445
TEST_F
(
LedgerTrieTest
, preferred_tie_breaker_by_id)
446
{
447
LedgerTrie<Ledger>
t;
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
464
TEST_F
(
LedgerTrieTest
, preferred_tie_breaker_not_needed)
465
{
466
LedgerTrie<Ledger>
t;
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
487
TEST_F
(
LedgerTrieTest
, preferred_single_node_larger_grand_child)
488
{
489
LedgerTrie<Ledger>
t;
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
502
TEST_F
(
LedgerTrieTest
, preferred_too_much_uncommitted_support_from_competing_branches)
503
{
504
LedgerTrie<Ledger>
t;
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
529
TEST_F
(
LedgerTrieTest
, preferred_changing_largestseq_perspective_changes_preferred_branch)
530
{
543
LedgerTrie<Ledger>
t;
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
631
TEST_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
636
LedgerTrie<Ledger>
t;
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
658
TEST_F
(
LedgerTrieTest
, stress)
659
{
660
LedgerTrie<Ledger>
t;
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);
678
std::uniform_int_distribution<>
flip(0, 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
std::string
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::Ledger
Holds a ledger.
Definition
include/xrpl/ledger/Ledger.h:76
xrpl::test::LedgerTrieTest
Fixture that scopes the csf names these tests use.
Definition
LedgerTrie.cpp:21
xrpl::test::LedgerTrieTest::Seq
Ledger::Seq Seq
Definition
LedgerTrie.cpp:25
xrpl::test::LedgerTrieTest::LedgerHistoryHelper
csf::LedgerHistoryHelper LedgerHistoryHelper
Definition
LedgerTrie.cpp:24
xrpl::test::LedgerTrieTest::Ledger
csf::Ledger Ledger
Definition
LedgerTrie.cpp:23
xrpl::test::csf::Ledger
A ledger is a set of observed transactions and a sequence number identifying the ledger.
Definition
ledgers.h:48
xrpl::test::csf::Ledger::Seq
TaggedInteger< std::uint32_t, SeqTag > Seq
Definition
ledgers.h:53
cstdint
std::uint32_t
std::mt19937
xrpl::test
Definition
STLedgerEntry.h:21
xrpl::test::TEST_F
TEST_F(BaseUintDeathTest, from_raw_size_mismatch)
Definition
base_uint.cpp:73
optional
random
xrpl::test::csf::LedgerHistoryHelper
Helper for writing unit tests with controlled ledger histories.
Definition
ledgers.h:328
xrpl::test::jtx::Seq
Set the sequence number on a JTx.
Definition
seq.h:16
std::uniform_int_distribution
Generated by
1.17.0