xrpld
Loading...
Searching...
No Matches
tests/libxrpl/shamap/SHAMap.cpp
1#include <xrpl/shamap/SHAMap.h>
2
3#include <xrpl/basics/Blob.h>
4#include <xrpl/basics/Buffer.h>
5#include <xrpl/basics/SHAMapHash.h>
6#include <xrpl/basics/Slice.h>
7#include <xrpl/basics/base_uint.h>
8#include <xrpl/beast/utility/Journal.h>
9#include <xrpl/beast/utility/Zero.h>
10#include <xrpl/protocol/Serializer.h>
11#include <xrpl/shamap/SHAMapInnerNode.h>
12#include <xrpl/shamap/SHAMapItem.h>
13#include <xrpl/shamap/SHAMapLeafNode.h>
14#include <xrpl/shamap/SHAMapMissingNode.h>
15#include <xrpl/shamap/SHAMapNodeID.h>
16#include <xrpl/shamap/SHAMapTreeNode.h>
17
18#include <gtest/gtest.h>
19#include <helpers/TestSink.h>
20#include <shamap/common.h>
21
22#include <algorithm>
23#include <array>
24#include <cstddef>
25#include <cstdint>
26#include <format>
27#include <memory>
28#include <string>
29#include <string_view>
30#include <type_traits>
31#include <utility>
32#include <vector>
33
34namespace xrpl::tests {
35
36#ifndef __INTELLISENSE__
37static_assert(std::is_nothrow_destructible<SHAMap>{});
38static_assert(!std::is_default_constructible<SHAMap>{});
39static_assert(!std::is_copy_constructible<SHAMap>{});
40static_assert(!std::is_copy_assignable<SHAMap>{});
41static_assert(!std::is_move_constructible<SHAMap>{});
42static_assert(!std::is_move_assignable<SHAMap>{});
43
44static_assert(std::is_nothrow_destructible<SHAMap::ConstIterator>{});
45static_assert(std::is_copy_constructible<SHAMap::ConstIterator>{});
46static_assert(std::is_copy_assignable<SHAMap::ConstIterator>{});
47static_assert(std::is_move_constructible<SHAMap::ConstIterator>{});
48static_assert(std::is_move_assignable<SHAMap::ConstIterator>{});
49
50static_assert(std::is_nothrow_destructible<SHAMapItem>{});
51static_assert(!std::is_default_constructible<SHAMapItem>{});
52static_assert(!std::is_copy_constructible<SHAMapItem>{});
53
54static_assert(std::is_nothrow_destructible<SHAMapNodeID>{});
55static_assert(std::is_default_constructible<SHAMapNodeID>{});
56static_assert(std::is_copy_constructible<SHAMapNodeID>{});
57static_assert(std::is_copy_assignable<SHAMapNodeID>{});
58static_assert(std::is_move_constructible<SHAMapNodeID>{});
59static_assert(std::is_move_assignable<SHAMapNodeID>{});
60
61static_assert(std::is_nothrow_destructible<SHAMapHash>{});
62static_assert(std::is_default_constructible<SHAMapHash>{});
63static_assert(std::is_copy_constructible<SHAMapHash>{});
64static_assert(std::is_copy_assignable<SHAMapHash>{});
65static_assert(std::is_move_constructible<SHAMapHash>{});
66static_assert(std::is_move_assignable<SHAMapHash>{});
67
68static_assert(std::is_nothrow_destructible<SHAMapTreeNode>{});
69static_assert(!std::is_default_constructible<SHAMapTreeNode>{});
70static_assert(!std::is_copy_constructible<SHAMapTreeNode>{});
71static_assert(!std::is_copy_assignable<SHAMapTreeNode>{});
72static_assert(!std::is_move_constructible<SHAMapTreeNode>{});
73static_assert(!std::is_move_assignable<SHAMapTreeNode>{});
74
75static_assert(std::is_nothrow_destructible<SHAMapInnerNode>{});
76static_assert(!std::is_default_constructible<SHAMapInnerNode>{});
77static_assert(!std::is_copy_constructible<SHAMapInnerNode>{});
78static_assert(!std::is_copy_assignable<SHAMapInnerNode>{});
79static_assert(!std::is_move_constructible<SHAMapInnerNode>{});
80static_assert(!std::is_move_assignable<SHAMapInnerNode>{});
81
82static_assert(std::is_nothrow_destructible<SHAMapLeafNode>{});
83static_assert(!std::is_default_constructible<SHAMapLeafNode>{});
84static_assert(!std::is_copy_constructible<SHAMapLeafNode>{});
85static_assert(!std::is_copy_assignable<SHAMapLeafNode>{});
86static_assert(!std::is_move_constructible<SHAMapLeafNode>{});
87static_assert(!std::is_move_assignable<SHAMapLeafNode>{});
88#endif
89
90inline bool
91operator!=(SHAMapItem const& a, SHAMapItem const& b)
92{
93 return a.key() != b.key();
94}
95
101
102constexpr SHAMapBackingMode kBackedMode{.backed = true, .testName = "backed"};
103constexpr SHAMapBackingMode kUnbackedMode{.backed = false, .testName = "unbacked"};
104
105[[nodiscard]] std::string
106shamapBackingModeName(::testing::TestParamInfo<SHAMapBackingMode> const& info)
107{
108 return std::string{info.param.testName};
109}
110
111class SHAMapTest : public ::testing::TestWithParam<SHAMapBackingMode>
112{
113protected:
115
116 [[nodiscard]] static Buffer
118 {
119 Buffer vuc{32};
120 vuc.fill(v);
121 return vuc;
122 }
123
124 // kH3 and kH4 differ only in the leaf, same terminal node (level 19)
125 static constexpr UInt256 kH1{
126 "092891fe4ef6cee585fdc6fda0e09eb4d386363158ec3321b8123e5a772c6ca7"};
127 static constexpr UInt256 kH2{
128 "436ccbac3347baa1f1e53baeef1f43334da88f1f6d70d963b833afd6dfa289fe"};
129 static constexpr UInt256 kH3{
130 "b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"};
131 static constexpr UInt256 kH4{
132 "b92891fe4ef6cee585fdc6fda2e09eb4d386363158ec3321b8123e5a772c6ca8"};
133
134 // SHAMap is neither copyable nor movable, so the map is configured in
135 // place rather than returned.
136 static void
138 {
139 map.invariants();
140 if (!GetParam().backed)
141 map.setUnbacked();
142 }
143
144 // Leaves the map holding kH1, kH3 and kH4, reached by deleting kH2 (which
145 // collapses an inner node) before kH3 is added.
146 static void
158};
159
160TEST_P(SHAMapTest, add_and_traverse_in_key_order)
161{
163 SHAMap sMap{SHAMapType::FREE, f};
164 applyBackingMode(sMap);
165
166 auto const i1 = makeShamapitem(kH1, intToVuc(1));
167 auto const i2 = makeShamapitem(kH2, intToVuc(2));
168
169 EXPECT_TRUE(sMap.addItem(SHAMapNodeType::TnTransactionNm, makeShamapitem(*i2))) << "no add";
170 sMap.invariants();
171 EXPECT_TRUE(sMap.addItem(SHAMapNodeType::TnTransactionNm, makeShamapitem(*i1))) << "no add";
172 sMap.invariants();
173
174 auto i = sMap.begin();
175 auto const e = sMap.end();
176 EXPECT_FALSE(i == e || (*i != *i1)) << "bad traverse";
177 ++i;
178 EXPECT_FALSE(i == e || (*i != *i2)) << "bad traverse";
179 ++i;
180 EXPECT_EQ(i, e) << "bad traverse";
181}
182
183TEST_P(SHAMapTest, traverse_after_add_and_delete)
184{
186 SHAMap sMap{SHAMapType::FREE, f};
187 applyBackingMode(sMap);
188
189 auto const i1 = makeShamapitem(kH1, intToVuc(1));
190 auto const i3 = makeShamapitem(kH3, intToVuc(3));
191 auto const i4 = makeShamapitem(kH4, intToVuc(4));
192
193 addThenDeleteAndReAdd(sMap);
194
195 auto i = sMap.begin();
196 auto const e = sMap.end();
197 EXPECT_FALSE(i == e || (*i != *i1)) << "bad traverse";
198 ++i;
199 EXPECT_FALSE(i == e || (*i != *i3)) << "bad traverse";
200 ++i;
201 EXPECT_FALSE(i == e || (*i != *i4)) << "bad traverse";
202 ++i;
203 EXPECT_EQ(i, e) << "bad traverse";
204}
205
206TEST_P(SHAMapTest, a_snapshot_is_unaffected_by_later_edits)
207{
209 SHAMap sMap{SHAMapType::FREE, f};
210 applyBackingMode(sMap);
211 addThenDeleteAndReAdd(sMap);
212
213 SHAMapHash const mapHash = sMap.getHash();
214 std::shared_ptr<SHAMap> const map2 = sMap.snapShot(false);
215 map2->invariants();
216 EXPECT_EQ(sMap.getHash(), mapHash) << "bad snapshot";
217 EXPECT_EQ(map2->getHash(), mapHash) << "bad snapshot";
218
219 SHAMap::Delta delta;
220 ASSERT_TRUE(sMap.compare(*map2, delta, 100));
221 EXPECT_TRUE(delta.empty());
222
223 EXPECT_TRUE(sMap.delItem(sMap.begin()->key())) << "bad mod";
224 sMap.invariants();
225 EXPECT_NE(sMap.getHash(), mapHash) << "bad snapshot";
226 EXPECT_EQ(map2->getHash(), mapHash) << "bad snapshot";
227
228 ASSERT_TRUE(sMap.compare(*map2, delta, 100));
229 ASSERT_EQ(delta.size(), 1);
230 EXPECT_EQ(delta.begin()->first, kH1);
231 EXPECT_EQ(delta.begin()->second.first, nullptr);
232 ASSERT_NE(delta.begin()->second.second, nullptr);
233 EXPECT_EQ(delta.begin()->second.second->key(), kH1);
234
235 sMap.dump();
236}
237
238TEST_P(SHAMapTest, the_hash_after_each_add_is_undone_by_the_matching_delete)
239{
240 constexpr std::array kKeys{
241 UInt256{"b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
242 UInt256{"b92881fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
243 UInt256{"b92691fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
244 UInt256{"b92791fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
245 UInt256{"b91891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
246 UInt256{"b99891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
247 UInt256{"f22891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
248 UInt256{"292891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
249 };
250
251 constexpr std::array kHashes{
252 UInt256{"B7387CFEA0465759ADC718E8C42B52D2309D179B326E239EB5075C64B6281F7F"},
253 UInt256{"FBC195A9592A54AB44010274163CB6BA95F497EC5BA0A8831845467FB2ECE266"},
254 UInt256{"4E7D2684B65DFD48937FFB775E20175C43AF0C94066F7D5679F51AE756795B75"},
255 UInt256{"7A2F312EB203695FFD164E038E281839EEF06A1B99BFC263F3CECC6C74F93E07"},
256 UInt256{"395A6691A372387A703FB0F2C6D2C405DAF307D0817F8F0E207596462B0E3A3E"},
257 UInt256{"D044C0A696DE3169CC70AE216A1564D69DE96582865796142CE7D98A84D9DDE4"},
258 UInt256{"76DCC77C4027309B5A91AD164083264D70B77B5E43E08AEDA5EBF94361143615"},
259 UInt256{"DF4220E93ADC6F5569063A01B4DC79F8DB9553B6A3222ADE23DEA02BBE7230E5"},
260 };
261
263 SHAMap map{SHAMapType::FREE, f};
264 applyBackingMode(map);
265
266 EXPECT_EQ(map.getHash(), beast::kZero);
267 for (std::size_t k = 0; k < kKeys.size(); ++k)
268 {
269 EXPECT_TRUE(map.addItem(
271 makeShamapitem(kKeys[k], intToVuc(static_cast<std::uint8_t>(k)))));
272 EXPECT_EQ(map.getHash().asUInt256(), kHashes[k]);
273 map.invariants();
274 }
275
276 // Removing the items in reverse must walk back through the same hashes.
277 for (std::size_t k = kKeys.size(); k-- > 0;)
278 {
279 EXPECT_EQ(map.getHash().asUInt256(), kHashes[k]);
280 EXPECT_TRUE(map.delItem(kKeys[k]));
281 map.invariants();
282 }
283 EXPECT_EQ(map.getHash(), beast::kZero);
284}
285
286TEST_P(SHAMapTest, iteration_yields_keys_in_ascending_order)
287{
288 // Listed in descending order, so iteration must reverse them.
289 constexpr std::array kKeys{
290 UInt256{"f22891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
291 UInt256{"b99891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
292 UInt256{"b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
293 UInt256{"b92881fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
294 UInt256{"b92791fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
295 UInt256{"b92691fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
296 UInt256{"b91891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
297 UInt256{"292891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
298 };
299
301 SHAMap map{SHAMapType::FREE, tf};
302 applyBackingMode(map);
303 for (auto const& k : kKeys)
304 {
306 map.invariants();
307 }
308
309 auto keyIndex = kKeys.size();
310 for (auto const& k : map)
311 EXPECT_EQ(k.key(), kKeys[--keyIndex]);
312}
313
315 BackingMode,
317 ::testing::Values(kBackedMode, kUnbackedMode),
319
320// Exercises the traversal stacks built by belowHelper. Each stack entry pairs a node with the ID
321// naming its position, and SHAMap asserts that pairing on every push, so these traversals fail
322// loudly in a Debug build if a node ID is ever derived from the wrong branch.
323class SHAMapTraversal : public ::testing::Test
324{
325protected:
327
328 // Keys that share a long prefix and then fan out across distinct branches, so the deeper inner
329 // nodes have several children and traversal must descend many levels.
330 [[nodiscard]] static std::vector<UInt256>
332 {
334 for (unsigned int branch = 0; branch < SHAMap::kBranchFactor; ++branch)
335 {
336 // Vary the 6th nibble, keeping the first five identical.
337 auto text = std::format("abcde{}", "0123456789abcdef"[branch]);
338 text.append(64 - text.size(), '7');
339 keys.emplace_back(std::string_view{text});
340 }
341 return keys;
342 }
343
344 // Keys that share all 63 leading nibbles and fan out only at the last one, so the tree is a
345 // chain of single-child inner nodes down to depth 63 with the leaves as siblings at depth 64.
346 // This exercises kLeafDepth directly, unlike deepFanOutKeys() above, whose fan-out at the 6th
347 // nibble keeps the tree only about 6 levels deep.
348 [[nodiscard]] static std::vector<UInt256>
350 {
352 for (unsigned int branch = 0; branch < SHAMap::kBranchFactor; ++branch)
353 {
354 auto const text = std::format("{}{}", std::string(63, 'a'), "0123456789abcdef"[branch]);
355 keys.emplace_back(std::string_view{text});
356 }
357 return keys;
358 }
359
360 static void
362 {
363 map.setUnbacked();
364 for (auto const& k : keys)
365 {
366 Buffer vuc{32};
367 std::fill_n(vuc.data(), vuc.size(), std::uint8_t{1});
368 EXPECT_TRUE(
369 map.addItem(SHAMapNodeType::TnAccountState, makeShamapitem(k, std::move(vuc))));
370 map.invariants();
371 }
372 }
373};
374
375TEST_F(SHAMapTraversal, forward_iteration_visits_every_key_in_order)
376{
378 auto keys = deepFanOutKeys();
379 SHAMap map{SHAMapType::FREE, f};
380 fillMap(map, keys);
381
382 std::ranges::sort(keys);
383 std::vector<UInt256> visited;
384 for (auto const& item : map)
385 visited.push_back(item.key());
386
387 EXPECT_EQ(visited, keys);
388}
389
390TEST_F(SHAMapTraversal, upper_bound_walks_the_whole_map)
391{
393 auto keys = deepFanOutKeys();
394 SHAMap map{SHAMapType::FREE, f};
395 fillMap(map, keys);
396 std::ranges::sort(keys);
397
398 // upperBound from each key must land on its successor, driving belowHelper across every
399 // subtree.
400 for (std::size_t k = 0; k + 1 < keys.size(); ++k)
401 {
402 auto const it = map.upperBound(keys[k]);
403 ASSERT_NE(it, map.end()) << "no successor for key " << k;
404 EXPECT_EQ(it->key(), keys[k + 1]) << "wrong successor for key " << k;
405 }
406 EXPECT_EQ(map.upperBound(keys.back()), map.end());
407}
408
409TEST_F(SHAMapTraversal, lower_bound_walks_the_whole_map)
410{
412 auto keys = deepFanOutKeys();
413 SHAMap map{SHAMapType::FREE, f};
414 fillMap(map, keys);
415 std::ranges::sort(keys);
416
417 // lowerBound is the reverse direction: belowHelper descends to the greatest key below a
418 // subtree.
419 for (std::size_t k = 1; k < keys.size(); ++k)
420 {
421 auto const it = map.lowerBound(keys[k]);
422 ASSERT_NE(it, map.end()) << "no predecessor for key " << k;
423 EXPECT_EQ(it->key(), keys[k - 1]) << "wrong predecessor for key " << k;
424 }
425 EXPECT_EQ(map.lowerBound(keys.front()), map.end());
426}
427
428TEST_F(SHAMapTraversal, bounds_agree_with_iteration_for_absent_keys)
429{
431 auto keys = deepFanOutKeys();
432 SHAMap map{SHAMapType::FREE, f};
433 fillMap(map, keys);
434 std::ranges::sort(keys);
435
436 // Probe keys that are not in the map, so the traversal starts mid-tree rather than at a leaf.
437 for (unsigned char const c : {0x00, 0x40, 0x80, 0xc0, 0xff})
438 {
439 UInt256 probe;
440 std::fill_n(probe.begin(), probe.size(), c);
441
442 auto const expectedUpper = std::ranges::upper_bound(keys, probe);
443 auto const upper = map.upperBound(probe);
444 if (expectedUpper == keys.end())
445 {
446 EXPECT_EQ(upper, map.end()) << "probe " << static_cast<unsigned>(c);
447 }
448 else
449 {
450 ASSERT_NE(upper, map.end()) << "probe " << static_cast<unsigned>(c);
451 EXPECT_EQ(upper->key(), *expectedUpper) << "probe " << static_cast<unsigned>(c);
452 }
453
454 auto const lowerCount = std::ranges::lower_bound(keys, probe) - keys.begin();
455 auto const lower = map.lowerBound(probe);
456 if (lowerCount == 0)
457 {
458 EXPECT_EQ(lower, map.end()) << "probe " << static_cast<unsigned>(c);
459 }
460 else
461 {
462 ASSERT_NE(lower, map.end()) << "probe " << static_cast<unsigned>(c);
463 EXPECT_EQ(lower->key(), keys[lowerCount - 1]) << "probe " << static_cast<unsigned>(c);
464 }
465 }
466
467 // Probe keys that land on a leaf and require the leaf-pop-and-resume case. Keys share
468 // "abcde" as a prefix and vary the 6th nibble, so a probe that shares the full prefix
469 // but differs in the padding hits a leaf from either side: '0' padded with '0' lands below
470 // the first key, and 'f' padded with 'f' lands above the last.
471 for (char const nibble : {'0', 'f'})
472 {
473 auto text = std::format("abcde{}", nibble);
474 text.append(64 - text.size(), nibble);
475 UInt256 const probe{std::string_view{text}};
476
477 auto const expectedUpper = std::ranges::upper_bound(keys, probe);
478 auto const upper = map.upperBound(probe);
479 if (expectedUpper == keys.end())
480 {
481 EXPECT_EQ(upper, map.end()) << "nibble " << nibble;
482 }
483 else
484 {
485 ASSERT_NE(upper, map.end()) << "nibble " << nibble;
486 EXPECT_EQ(upper->key(), *expectedUpper) << "nibble " << nibble;
487 }
488
489 auto const lowerCount = std::ranges::lower_bound(keys, probe) - keys.begin();
490 auto const lower = map.lowerBound(probe);
491 if (lowerCount == 0)
492 {
493 EXPECT_EQ(lower, map.end()) << "nibble " << nibble;
494 }
495 else
496 {
497 ASSERT_NE(lower, map.end()) << "nibble " << nibble;
498 EXPECT_EQ(lower->key(), keys[lowerCount - 1]) << "nibble " << nibble;
499 }
500 }
501}
502
503TEST_F(SHAMapTraversal, bounds_on_empty_map_return_end)
504{
506 SHAMap map{SHAMapType::FREE, f};
507 map.setUnbacked();
508
509 // The root is a childless inner node, so boundHelper's inner-node branch scans every branch on
510 // the requested side of the one id selects, finds them all empty, and falls through to end()
511 // rather than dereference a child.
512 EXPECT_EQ(map.upperBound(UInt256{}), map.end());
513 EXPECT_EQ(map.lowerBound(UInt256{}), map.end());
514
515 UInt256 probe;
516 std::fill_n(probe.begin(), probe.size(), std::uint8_t{0xff});
517 EXPECT_EQ(map.upperBound(probe), map.end());
518 EXPECT_EQ(map.lowerBound(probe), map.end());
519}
520
521TEST_F(SHAMapTraversal, bounds_on_single_item_map_use_the_leaf_below_the_root)
522{
524 SHAMap map{SHAMapType::FREE, f};
525
526 auto const key = deepFanOutKeys().front();
527 fillMap(map, {key});
528
529 // fillMap adds items in-process, so root_ stays an inner node with the single leaf below it.
530 // The stack holds both, so boundHelper examines the leaf first.
531 UInt256 below = key;
532 --below;
533 UInt256 above = key;
534 ++above;
535
536 auto const upper = map.upperBound(below);
537 ASSERT_NE(upper, map.end());
538 EXPECT_EQ(upper->key(), key);
539 EXPECT_EQ(map.upperBound(key), map.end());
540 EXPECT_EQ(map.upperBound(above), map.end());
541
542 auto const lower = map.lowerBound(above);
543 ASSERT_NE(lower, map.end());
544 EXPECT_EQ(lower->key(), key);
545 EXPECT_EQ(map.lowerBound(key), map.end());
546 EXPECT_EQ(map.lowerBound(below), map.end());
547}
548
549TEST_F(SHAMapTraversal, iteration_survives_deletions)
550{
552 auto keys = deepFanOutKeys();
553 SHAMap map{SHAMapType::FREE, f};
554 fillMap(map, keys);
555 std::ranges::sort(keys);
556
557 // Deleting every other key drops the fan-out node's branch count from 16 to 8, never the 1
558 // that would make delItem collapse it into a leaf. So this pins that iteration survives
559 // deletions that reshape the map without collapsing any inner node; the case that does
560 // collapse one is iteration_survives_a_collapsed_inner_node below.
561 for (std::size_t k = 0; k < keys.size(); k += 2)
562 {
563 ASSERT_TRUE(map.delItem(keys[k]));
564 map.invariants();
565 }
566
567 std::vector<UInt256> expected;
568 for (std::size_t k = 1; k < keys.size(); k += 2)
569 expected.push_back(keys[k]);
570
571 std::vector<UInt256> visited;
572 for (auto const& item : map)
573 visited.push_back(item.key());
574 EXPECT_EQ(visited, expected);
575
576 for (std::size_t k = 0; k + 1 < expected.size(); ++k)
577 {
578 auto const it = map.upperBound(expected[k]);
579 ASSERT_NE(it, map.end());
580 EXPECT_EQ(it->key(), expected[k + 1]);
581 }
582}
583
584TEST_F(SHAMapTraversal, iteration_survives_a_collapsed_inner_node)
585{
587 SHAMap map{SHAMapType::FREE, f};
588
589 // One key in a separate subtree, diverging from the fan-out group at the very first nibble, so
590 // it survives untouched while the fan-out group below is collapsed.
591 auto const sentinel = UInt256{std::string_view{std::string(64, '0')}};
592
593 auto fanOutKeys = deepFanOutKeysAtLeafDepth();
594 fillMap(map, fanOutKeys);
595 Buffer vuc{32};
596 std::fill_n(vuc.data(), vuc.size(), std::uint8_t{1});
597 ASSERT_TRUE(
598 map.addItem(SHAMapNodeType::TnAccountState, makeShamapitem(sentinel, std::move(vuc))));
599 map.invariants();
600
601 std::ranges::sort(fanOutKeys);
602
603 // Delete all but the last fan-out key. The fan-out node's branch count drops to 1 on the final
604 // delete, which delItem collapses by pulling the sole remaining leaf up in its place; every
605 // ancestor above it has exactly one child by construction, so each of those also drops to
606 // branch count 1 and collapses in turn, all the way up to (but not including) the root. That
607 // final delete replaces the entire 63-level chain with the root pointing straight at the one
608 // remaining leaf, so the surviving traversal stack is rebuilt over a drastically different tree
609 // shape, not just missing one inner node.
610 for (std::size_t k = 0; k + 1 < fanOutKeys.size(); ++k)
611 {
612 ASSERT_TRUE(map.delItem(fanOutKeys[k]));
613 map.invariants();
614 }
615
616 std::vector<UInt256> const expected{sentinel, fanOutKeys.back()};
617 std::vector<UInt256> visited;
618 for (auto const& item : map)
619 visited.push_back(item.key());
620 EXPECT_EQ(visited, expected);
621
622 auto const it = map.upperBound(sentinel);
623 ASSERT_NE(it, map.end());
624 EXPECT_EQ(it->key(), fanOutKeys.back());
625 EXPECT_EQ(map.upperBound(fanOutKeys.back()), map.end());
626}
627
628// The tests below mirror the ones above but use deepFanOutKeysAtLeafDepth(), whose keys share all
629// 63 leading nibbles and fan out only at the last one. That puts the leaves at depth
630// SHAMap::kLeafDepth, so these traversals walk a chain of single-child inner nodes all the way down
631// and exercise the kLeafDepth guards that deepFanOutKeys() alone (fanning out at the 6th nibble)
632// never reaches.
633
634TEST_F(SHAMapTraversal, forward_iteration_visits_every_key_in_order_at_leaf_depth)
635{
637 auto keys = deepFanOutKeysAtLeafDepth();
638 SHAMap map{SHAMapType::FREE, f};
639 fillMap(map, keys);
640
641 std::ranges::sort(keys);
642 std::vector<UInt256> visited;
643 for (auto const& item : map)
644 visited.push_back(item.key());
645
646 EXPECT_EQ(visited, keys);
647}
648
649TEST_F(SHAMapTraversal, upper_bound_walks_the_whole_map_at_leaf_depth)
650{
652 auto keys = deepFanOutKeysAtLeafDepth();
653 SHAMap map{SHAMapType::FREE, f};
654 fillMap(map, keys);
655 std::ranges::sort(keys);
656
657 // upperBound from each key must land on its successor, driving belowHelper down to depth
658 // kLeafDepth for every subtree.
659 for (std::size_t k = 0; k + 1 < keys.size(); ++k)
660 {
661 auto const it = map.upperBound(keys[k]);
662 ASSERT_NE(it, map.end()) << "no successor for key " << k;
663 EXPECT_EQ(it->key(), keys[k + 1]) << "wrong successor for key " << k;
664 }
665 EXPECT_EQ(map.upperBound(keys.back()), map.end());
666}
667
668TEST_F(SHAMapTraversal, lower_bound_walks_the_whole_map_at_leaf_depth)
669{
671 auto keys = deepFanOutKeysAtLeafDepth();
672 SHAMap map{SHAMapType::FREE, f};
673 fillMap(map, keys);
674 std::ranges::sort(keys);
675
676 // lowerBound is the reverse direction: belowHelper descends to depth kLeafDepth to find the
677 // greatest key below a subtree.
678 for (std::size_t k = 1; k < keys.size(); ++k)
679 {
680 auto const it = map.lowerBound(keys[k]);
681 ASSERT_NE(it, map.end()) << "no predecessor for key " << k;
682 EXPECT_EQ(it->key(), keys[k - 1]) << "wrong predecessor for key " << k;
683 }
684 EXPECT_EQ(map.lowerBound(keys.front()), map.end());
685}
686
687TEST_F(SHAMapTraversal, bounds_agree_with_iteration_for_absent_keys_at_leaf_depth)
688{
690 auto keys = deepFanOutKeysAtLeafDepth();
691 SHAMap map{SHAMapType::FREE, f};
692 fillMap(map, keys);
693 std::ranges::sort(keys);
694
695 // The keys fill all 16 branches of the last nibble, so an absent key must diverge from the
696 // shared 'a' prefix earlier than that. Diverging at increasingly deep nibbles forces
697 // walkTowardsKey to descend through more single-child inner nodes before it finds the empty
698 // branch, right up to the one just above kLeafDepth.
699 for (unsigned int const divergeAt : {0u, 31u, 61u, 62u})
700 {
701 // '9' sorts below the shared 'a' prefix and 'b' above it, so the probe lands under or
702 // over the whole key block -- driving belowHelper's First and Last descents respectively.
703 for (char const nibble : {'9', 'b'})
704 {
705 auto text = std::format("{}{}", std::string(divergeAt, 'a'), nibble);
706 text.append(64 - text.size(), '0');
707 UInt256 const probe{std::string_view{text}};
708
709 auto const expectedUpper = std::ranges::upper_bound(keys, probe);
710 auto const upper = map.upperBound(probe);
711 if (expectedUpper == keys.end())
712 {
713 EXPECT_EQ(upper, map.end()) << "divergeAt " << divergeAt << " nibble " << nibble;
714 }
715 else
716 {
717 ASSERT_NE(upper, map.end()) << "divergeAt " << divergeAt << " nibble " << nibble;
718 EXPECT_EQ(upper->key(), *expectedUpper)
719 << "divergeAt " << divergeAt << " nibble " << nibble;
720 }
721
722 auto const lowerCount = std::ranges::lower_bound(keys, probe) - keys.begin();
723 auto const lower = map.lowerBound(probe);
724 if (lowerCount == 0)
725 {
726 EXPECT_EQ(lower, map.end()) << "divergeAt " << divergeAt << " nibble " << nibble;
727 }
728 else
729 {
730 ASSERT_NE(lower, map.end()) << "divergeAt " << divergeAt << " nibble " << nibble;
731 EXPECT_EQ(lower->key(), keys[lowerCount - 1])
732 << "divergeAt " << divergeAt << " nibble " << nibble;
733 }
734 }
735 }
736}
737
738TEST_F(SHAMapTraversal, iteration_survives_deletions_at_leaf_depth)
739{
741 auto keys = deepFanOutKeysAtLeafDepth();
742 SHAMap map{SHAMapType::FREE, f};
743 fillMap(map, keys);
744 std::ranges::sort(keys);
745
746 // Deleting every other key drops the fan-out node's branch count from 16 to 8, the same
747 // non-collapsing case as iteration_survives_deletions above, but reached by descending through
748 // a chain of single-child inner nodes down to kLeafDepth instead of a shallow one.
749 for (std::size_t k = 0; k < keys.size(); k += 2)
750 {
751 ASSERT_TRUE(map.delItem(keys[k]));
752 map.invariants();
753 }
754
755 std::vector<UInt256> expected;
756 for (std::size_t k = 1; k < keys.size(); k += 2)
757 expected.push_back(keys[k]);
758
759 std::vector<UInt256> visited;
760 for (auto const& item : map)
761 visited.push_back(item.key());
762 EXPECT_EQ(visited, expected);
763
764 for (std::size_t k = 0; k + 1 < expected.size(); ++k)
765 {
766 auto const it = map.upperBound(expected[k]);
767 ASSERT_NE(it, map.end());
768 EXPECT_EQ(it->key(), expected[k + 1]);
769 }
770}
771
772class SHAMapPathProof : public ::testing::Test
773{
774protected:
776};
777
778TEST_F(SHAMapPathProof, verify_proof_path)
779{
781 SHAMap map{SHAMapType::FREE, tf};
782 map.setUnbacked();
783
784 UInt256 key;
785 UInt256 rootHash;
786 std::vector<Blob> goodPath;
787
788 static constexpr unsigned char kFirstKey = 1;
789 static constexpr unsigned char kKeyCount = 100;
790 static constexpr unsigned char kLastKey = kKeyCount - 1;
791
792 for (unsigned char c = kFirstKey; c < kKeyCount; ++c)
793 {
794 UInt256 k(c);
796 map.invariants();
797
798 auto const root = map.getHash().asUInt256();
799 auto path = map.getProofPath(k);
800 if (!path)
801 {
802 ADD_FAILURE() << "Missing proof path";
803 return;
804 }
805 auto& proofPath = *path;
806
807 EXPECT_TRUE(map.verifyProofPath(root, k, proofPath));
808 if (c == kFirstKey)
809 {
810 // extra node
811 proofPath.insert(proofPath.begin(), proofPath.front());
812 EXPECT_FALSE(map.verifyProofPath(root, k, proofPath));
813 // wrong key
814 UInt256 const wrongKey(c + 1);
815 EXPECT_FALSE(map.getProofPath(wrongKey));
816 }
817 if (c == kLastKey)
818 {
819 key = k;
820 rootHash = root;
821 goodPath = std::move(proofPath);
822 }
823 }
824
825 // still good
826 EXPECT_TRUE(map.verifyProofPath(rootHash, key, goodPath));
827 // empty path
828 std::vector<Blob> badPath;
829 EXPECT_FALSE(map.verifyProofPath(rootHash, key, badPath));
830 // too long
831 badPath = goodPath;
832 badPath.push_back(goodPath.back());
833 EXPECT_FALSE(map.verifyProofPath(rootHash, key, badPath));
834 // bad node
835 badPath.clear();
836 badPath.emplace_back(100, 100);
837 EXPECT_FALSE(map.verifyProofPath(rootHash, key, badPath));
838 // bad node type
839 badPath.clear();
840 badPath.push_back(goodPath.front());
841 badPath.front().back()--; // change node type
842 EXPECT_FALSE(map.verifyProofPath(rootHash, key, badPath));
843 // all inner
844 badPath.clear();
845 badPath = goodPath;
846 badPath.erase(badPath.begin());
847 EXPECT_FALSE(map.verifyProofPath(rootHash, key, badPath));
848}
849
850// A legitimate proof path for two keys sharing all 63 leading nibbles is 65 elements: inner nodes
851// at depths 0..63 plus the leaf at depth 64. This pins that the 65 bound is real, so the fix for
852// the forged-path case below must not simply tighten the length limit.
853TEST_F(SHAMapPathProof, legitimate_deep_path_is_sixty_five_elements)
854{
856 SHAMap map{SHAMapType::FREE, f};
857 map.setUnbacked();
858
859 auto const kA = UInt256{std::string_view{std::format("{}1", std::string(63, 'a'))}};
860 auto const kB = UInt256{std::string_view{std::format("{}2", std::string(63, 'a'))}};
861
862 for (auto const& k : {kA, kB})
863 {
864 Buffer vuc{32};
865 std::fill_n(vuc.data(), vuc.size(), std::uint8_t{1});
866 ASSERT_TRUE(map.addItem(SHAMapNodeType::TnAccountState, makeShamapitem(k, std::move(vuc))));
867 }
868 map.invariants();
869
870 auto const pathA = map.getProofPath(kA);
871 ASSERT_TRUE(pathA.has_value());
872 // NOLINTBEGIN(bugprone-unchecked-optional-access) has_value() checked above
873 EXPECT_EQ(pathA->size(), 65u);
874 EXPECT_TRUE(SHAMap::verifyProofPath(map.getHash().asUInt256(), kA, *pathA));
875 // NOLINTEND(bugprone-unchecked-optional-access)
876
877 auto const pathB = map.getProofPath(kB);
878 ASSERT_TRUE(pathB.has_value());
879 // NOLINTBEGIN(bugprone-unchecked-optional-access) has_value() checked above
880 EXPECT_EQ(pathB->size(), 65u);
881 EXPECT_TRUE(SHAMap::verifyProofPath(map.getHash().asUInt256(), kB, *pathB));
882 // NOLINTEND(bugprone-unchecked-optional-access)
883}
884
885// A forged path of 65 hash-chained inner nodes reaches depth kLeafDepth, where only the leaf
886// terminating the path may sit. Such a path must be rejected.
887TEST_F(SHAMapPathProof, all_inner_path_at_leaf_depth_is_rejected)
888{
889 // An arbitrary well-formed key; the test does not care about its specific value.
890 constexpr UInt256 kTestKey("b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8");
891
892 // Build upwards from the deepest node so each parent's selected branch carries its child's hash
893 // and the hash chain validates at every level.
895 SHAMapHash childHash{UInt256{1}};
896
897 for (auto depth = SHAMap::kLeafDepth + 1u; depth-- > 0;)
898 {
899 auto const id = SHAMapNodeID::createID(std::min(depth, SHAMap::kLeafDepth - 1u), kTestKey);
900 auto const branch = selectBranch(id, kTestKey);
901
902 Serializer s;
903 for (auto i = 0u; i < SHAMap::kBranchFactor; ++i)
904 s.addBitString(i == branch ? childHash.asUInt256() : UInt256{});
906 path.push_back(s.getData());
907
908 auto const node = SHAMapTreeNode::makeFromWire(makeSlice(path.back()));
909 ASSERT_TRUE(node);
910 node->updateHash();
911 childHash = node->getHash();
912 }
913
914 ASSERT_EQ(path.size(), 65u);
915 EXPECT_FALSE(SHAMap::verifyProofPath(childHash.asUInt256(), kTestKey, path));
916}
917
929[[nodiscard]] static std::pair<std::vector<Blob>, UInt256>
930forgeRootOverLeaf(Blob const& leafBlob, UInt256 const& key)
931{
932 auto const leaf = SHAMapTreeNode::makeFromWire(makeSlice(leafBlob));
933 if (!leaf || !leaf->isLeaf())
934 return {};
935 leaf->updateHash();
936
937 auto const branch = selectBranch(SHAMapNodeID::createID(0, key), key);
938 Serializer s;
939 for (auto i = 0u; i < SHAMap::kBranchFactor; ++i)
940 s.addBitString(i == branch ? leaf->getHash().asUInt256() : UInt256{});
942
944 if (!root)
945 return {};
946 root->updateHash();
947
948 return {std::vector<Blob>{leafBlob, s.getData()}, root->getHash().asUInt256()};
949}
950
951// The hash chain above a leaf proves nothing about which key that leaf holds, so a peer can graft a
952// genuine leaf from elsewhere in the map onto a path forged for another key. Comparing the terminal
953// leaf's own key against the key being proved is what rejects it.
954TEST_F(SHAMapPathProof, substituted_leaf_for_other_key_is_rejected)
955{
957 SHAMap map{SHAMapType::FREE, f};
958 map.setUnbacked();
959
960 // Two arbitrary keys differing in their first nibble, so each leaf hangs off the root directly.
961 constexpr UInt256 kKey("1c8cec8e5e9b0e5e0e0f5b3e2c9f7a1d6b4e8c2a0d7f3b9e5c1a8d4f2b6e0c93");
962 constexpr UInt256 kOtherKey("e3f1a7d5b9c2e8f406a1d3b5c7e9f2a4d6b8c0e2f4a6d8b0c2e4f6a8d0b2c4e6");
963
964 for (auto const& k : {kKey, kOtherKey})
965 {
966 ASSERT_TRUE(map.addItem(
967 SHAMapNodeType::TnAccountState, makeShamapitem(k, Slice{k.data(), k.size()})));
968 }
969 map.invariants();
970
971 auto const ownPath = map.getProofPath(kKey);
972 auto const otherPath = map.getProofPath(kOtherKey);
973 ASSERT_TRUE(ownPath.has_value());
974 ASSERT_TRUE(otherPath.has_value());
975
976 // NOLINTBEGIN(bugprone-unchecked-optional-access) has_value() checked above
977 // The genuine leaf blobs, deepest element first.
978 auto const& ownLeaf = ownPath->front();
979 auto const& otherLeaf = otherPath->front();
980 // NOLINTEND(bugprone-unchecked-optional-access)
981
982 // Control: the forged root is accepted when the leaf below it really is kKey's leaf, so the
983 // rejection below can only come from the leaf key comparison.
984 auto const [goodPath, goodRoot] = forgeRootOverLeaf(ownLeaf, kKey);
985 ASSERT_EQ(goodPath.size(), 2u);
986 EXPECT_TRUE(SHAMap::verifyProofPath(goodRoot, kKey, goodPath));
987
988 // Same forged root, but kOtherKey's leaf substituted at the bottom: the hash chain still
989 // validates, yet the path does not prove anything about kKey.
990 auto const [badPath, badRoot] = forgeRootOverLeaf(otherLeaf, kKey);
991 ASSERT_EQ(badPath.size(), 2u);
992 EXPECT_FALSE(SHAMap::verifyProofPath(badRoot, kKey, badPath));
993}
994
995} // namespace xrpl::tests
T back(T... args)
T begin(T... args)
A generic endpoint for log messages.
Definition Journal.h:44
pointer data()
Definition base_uint.h:117
iterator begin()
Definition base_uint.h:128
static constexpr std::size_t size()
Definition base_uint.h:549
Like std::vector<char> but better.
Definition Buffer.h:19
std::size_t size() const noexcept
Returns the number of bytes in the buffer.
Definition Buffer.h:123
std::uint8_t const * data() const noexcept
Return a pointer to beginning of the storage.
Definition Buffer.h:148
void fill(std::uint8_t value) noexcept
Set every byte in the buffer to the given value.
Definition Buffer.h:168
UInt256 const & asUInt256() const
Definition SHAMapHash.h:26
UInt256 const & key() const
Definition SHAMapItem.h:74
static SHAMapNodeID createID(unsigned int depth, UInt256 const &key)
Create a SHAMapNodeID of a node with the depth of the node and the key of a leaf.
static SHAMapTreeNodePtr makeFromWire(Slice rawNode)
bool addItem(SHAMapNodeType type, boost::intrusive_ptr< SHAMapItem const > item)
ConstIterator upperBound(UInt256 const &id) const
Find the first item after the given item.
static constexpr unsigned int kLeafDepth
The depth of the hash map: data is only present in the leaves.
Definition SHAMap.h:172
static constexpr unsigned int kBranchFactor
Number of children each non-leaf node has (the 'radix tree' part of the map).
Definition SHAMap.h:167
void setUnbacked()
Definition SHAMap.h:1007
void dump(bool withHashes=false) const
std::map< UInt256, DeltaItem > Delta
Definition SHAMap.h:176
bool compare(SHAMap const &otherMap, Delta &differences, int maxCount) const
std::shared_ptr< SHAMap > snapShot(bool isMutable) const
Return a new map that is a snapshot of this one.
bool delItem(UInt256 const &id)
ConstIterator end() const
Definition SHAMap.h:1125
ConstIterator lowerBound(UInt256 const &id) const
Find the object with the greatest object id smaller than the input id.
SHAMapHash getHash() const
ConstIterator begin() const
Definition SHAMap.h:1119
std::optional< std::vector< Blob > > getProofPath(UInt256 const &key) const
Get the proof path of the key.
static bool verifyProofPath(UInt256 const &rootHash, UInt256 const &key, std::vector< Blob > const &path)
Verify the proof path.
Blob const & peekData() const
Definition Serializer.h:273
int addBitString(BaseUInt< Bits, Tag > const &v)
Definition Serializer.h:202
int add8(unsigned char byteValue)
Blob getData() const
Definition Serializer.h:278
An immutable linear range of bytes.
Definition Slice.h:28
static TestSink & instance()
Definition TestSink.h:12
static void applyBackingMode(SHAMap &map)
static Buffer intToVuc(std::uint8_t v)
static void addThenDeleteAndReAdd(SHAMap &map)
static std::vector< UInt256 > deepFanOutKeysAtLeafDepth()
static std::vector< UInt256 > deepFanOutKeys()
static void fillMap(SHAMap &map, std::vector< UInt256 > const &keys)
T clear(T... args)
T emplace_back(T... args)
T empty(T... args)
T erase(T... args)
T fill_n(T... args)
T format(T... args)
T front(T... args)
T lower_bound(T... args)
T min(T... args)
constexpr Zero kZero
Definition Zero.h:30
constexpr SHAMapBackingMode kUnbackedMode
TEST_P(SHAMapTest, add_and_traverse_in_key_order)
constexpr SHAMapBackingMode kBackedMode
TEST_F(HashRouterTest, clear_flags_clears_only_the_named_flags)
constexpr UInt256 kTestKey("b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8")
bool operator!=(SHAMapItem const &a, SHAMapItem const &b)
static std::pair< std::vector< Blob >, UInt256 > forgeRootOverLeaf(Blob const &leafBlob, UInt256 const &key)
Wrap a leaf blob in a forged root inner node whose branch for key carries that leaf's hash.
std::string shamapBackingModeName(::testing::TestParamInfo< SHAMapBackingMode > const &info)
INSTANTIATE_TEST_SUITE_P(BackingMode, SHAMapTest, ::testing::Values(kBackedMode, kUnbackedMode), shamapBackingModeName)
Number root(Number f, unsigned d)
Slice makeSlice(std::array< T, N > const &a)
Definition Slice.h:228
BaseUInt< 256 > UInt256
Definition base_uint.h:581
boost::intrusive_ptr< SHAMapItem > makeShamapitem(UInt256 const &tag, Slice data)
Definition SHAMapItem.h:148
unsigned int selectBranch(SHAMapNodeID const &id, UInt256 const &hash)
Returns the branch that would contain the given hash.
std::vector< unsigned char > Blob
Storage for linear binary data.
Definition Blob.h:11
static constexpr unsigned char const kWireTypeInner
T push_back(T... args)
T size(T... args)
T sort(T... args)
T upper_bound(T... args)