1#include <xrpl/shamap/SHAMap.h>
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>
18#include <gtest/gtest.h>
19#include <helpers/TestSink.h>
20#include <shamap/common.h>
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>{});
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>{});
50static_assert(std::is_nothrow_destructible<SHAMapItem>{});
51static_assert(!std::is_default_constructible<SHAMapItem>{});
52static_assert(!std::is_copy_constructible<SHAMapItem>{});
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>{});
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>{});
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>{});
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>{});
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>{});
111class SHAMapTest :
public ::testing::TestWithParam<SHAMapBackingMode>
116 [[nodiscard]]
static Buffer
126 "092891fe4ef6cee585fdc6fda0e09eb4d386363158ec3321b8123e5a772c6ca7"};
128 "436ccbac3347baa1f1e53baeef1f43334da88f1f6d70d963b833afd6dfa289fe"};
130 "b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"};
132 "b92891fe4ef6cee585fdc6fda2e09eb4d386363158ec3321b8123e5a772c6ca8"};
140 if (!GetParam().backed)
164 applyBackingMode(sMap);
174 auto i = sMap.
begin();
175 auto const e = sMap.
end();
176 EXPECT_FALSE(i == e || (*i != *i1)) <<
"bad traverse";
178 EXPECT_FALSE(i == e || (*i != *i2)) <<
"bad traverse";
180 EXPECT_EQ(i, e) <<
"bad traverse";
187 applyBackingMode(sMap);
193 addThenDeleteAndReAdd(sMap);
195 auto i = sMap.
begin();
196 auto const e = sMap.
end();
197 EXPECT_FALSE(i == e || (*i != *i1)) <<
"bad traverse";
199 EXPECT_FALSE(i == e || (*i != *i3)) <<
"bad traverse";
201 EXPECT_FALSE(i == e || (*i != *i4)) <<
"bad traverse";
203 EXPECT_EQ(i, e) <<
"bad traverse";
210 applyBackingMode(sMap);
211 addThenDeleteAndReAdd(sMap);
216 EXPECT_EQ(sMap.
getHash(), mapHash) <<
"bad snapshot";
217 EXPECT_EQ(map2->getHash(), mapHash) <<
"bad snapshot";
220 ASSERT_TRUE(sMap.
compare(*map2, delta, 100));
221 EXPECT_TRUE(delta.
empty());
223 EXPECT_TRUE(sMap.
delItem(sMap.
begin()->key())) <<
"bad mod";
225 EXPECT_NE(sMap.
getHash(), mapHash) <<
"bad snapshot";
226 EXPECT_EQ(map2->getHash(), mapHash) <<
"bad snapshot";
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);
241 UInt256{
"b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
242 UInt256{
"b92881fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
243 UInt256{
"b92691fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
244 UInt256{
"b92791fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
245 UInt256{
"b91891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
246 UInt256{
"b99891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
247 UInt256{
"f22891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
248 UInt256{
"292891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
252 UInt256{
"B7387CFEA0465759ADC718E8C42B52D2309D179B326E239EB5075C64B6281F7F"},
253 UInt256{
"FBC195A9592A54AB44010274163CB6BA95F497EC5BA0A8831845467FB2ECE266"},
254 UInt256{
"4E7D2684B65DFD48937FFB775E20175C43AF0C94066F7D5679F51AE756795B75"},
255 UInt256{
"7A2F312EB203695FFD164E038E281839EEF06A1B99BFC263F3CECC6C74F93E07"},
256 UInt256{
"395A6691A372387A703FB0F2C6D2C405DAF307D0817F8F0E207596462B0E3A3E"},
257 UInt256{
"D044C0A696DE3169CC70AE216A1564D69DE96582865796142CE7D98A84D9DDE4"},
258 UInt256{
"76DCC77C4027309B5A91AD164083264D70B77B5E43E08AEDA5EBF94361143615"},
259 UInt256{
"DF4220E93ADC6F5569063A01B4DC79F8DB9553B6A3222ADE23DEA02BBE7230E5"},
264 applyBackingMode(map);
280 EXPECT_TRUE(map.
delItem(kKeys[k]));
290 UInt256{
"f22891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
291 UInt256{
"b99891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
292 UInt256{
"b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
293 UInt256{
"b92881fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
294 UInt256{
"b92791fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
295 UInt256{
"b92691fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
296 UInt256{
"b91891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
297 UInt256{
"292891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8"},
302 applyBackingMode(map);
303 for (
auto const& k : kKeys)
309 auto keyIndex = kKeys.
size();
310 for (
auto const& k : map)
311 EXPECT_EQ(k.key(), kKeys[--keyIndex]);
337 auto text =
std::format(
"abcde{}",
"0123456789abcdef"[branch]);
338 text.append(64 - text.size(),
'7');
364 for (
auto const& k : keys)
378 auto keys = deepFanOutKeys();
384 for (
auto const& item : map)
387 EXPECT_EQ(visited, keys);
393 auto keys = deepFanOutKeys();
403 ASSERT_NE(it, map.
end()) <<
"no successor for key " << k;
404 EXPECT_EQ(it->key(), keys[k + 1]) <<
"wrong successor for key " << k;
412 auto keys = deepFanOutKeys();
422 ASSERT_NE(it, map.
end()) <<
"no predecessor for key " << k;
423 EXPECT_EQ(it->key(), keys[k - 1]) <<
"wrong predecessor for key " << k;
431 auto keys = deepFanOutKeys();
437 for (
unsigned char const c : {0x00, 0x40, 0x80, 0xc0, 0xff})
444 if (expectedUpper == keys.end())
446 EXPECT_EQ(upper, map.
end()) <<
"probe " <<
static_cast<unsigned>(c);
450 ASSERT_NE(upper, map.
end()) <<
"probe " <<
static_cast<unsigned>(c);
451 EXPECT_EQ(upper->key(), *expectedUpper) <<
"probe " <<
static_cast<unsigned>(c);
458 EXPECT_EQ(lower, map.
end()) <<
"probe " <<
static_cast<unsigned>(c);
462 ASSERT_NE(lower, map.
end()) <<
"probe " <<
static_cast<unsigned>(c);
463 EXPECT_EQ(lower->key(), keys[lowerCount - 1]) <<
"probe " <<
static_cast<unsigned>(c);
471 for (
char const nibble : {
'0',
'f'})
474 text.append(64 - text.size(), nibble);
479 if (expectedUpper == keys.end())
481 EXPECT_EQ(upper, map.
end()) <<
"nibble " << nibble;
485 ASSERT_NE(upper, map.
end()) <<
"nibble " << nibble;
486 EXPECT_EQ(upper->key(), *expectedUpper) <<
"nibble " << nibble;
493 EXPECT_EQ(lower, map.
end()) <<
"nibble " << nibble;
497 ASSERT_NE(lower, map.
end()) <<
"nibble " << nibble;
498 EXPECT_EQ(lower->key(), keys[lowerCount - 1]) <<
"nibble " << nibble;
526 auto const key = deepFanOutKeys().front();
537 ASSERT_NE(upper, map.
end());
538 EXPECT_EQ(upper->key(), key);
543 ASSERT_NE(lower, map.
end());
544 EXPECT_EQ(lower->key(), key);
552 auto keys = deepFanOutKeys();
563 ASSERT_TRUE(map.
delItem(keys[k]));
572 for (
auto const& item : map)
574 EXPECT_EQ(visited, expected);
579 ASSERT_NE(it, map.
end());
580 EXPECT_EQ(it->key(), expected[k + 1]);
593 auto fanOutKeys = deepFanOutKeysAtLeafDepth();
594 fillMap(map, fanOutKeys);
610 for (
std::size_t k = 0; k + 1 < fanOutKeys.size(); ++k)
612 ASSERT_TRUE(map.
delItem(fanOutKeys[k]));
618 for (
auto const& item : map)
620 EXPECT_EQ(visited, expected);
623 ASSERT_NE(it, map.
end());
624 EXPECT_EQ(it->key(), fanOutKeys.back());
637 auto keys = deepFanOutKeysAtLeafDepth();
643 for (
auto const& item : map)
646 EXPECT_EQ(visited, keys);
652 auto keys = deepFanOutKeysAtLeafDepth();
662 ASSERT_NE(it, map.
end()) <<
"no successor for key " << k;
663 EXPECT_EQ(it->key(), keys[k + 1]) <<
"wrong successor for key " << k;
671 auto keys = deepFanOutKeysAtLeafDepth();
681 ASSERT_NE(it, map.
end()) <<
"no predecessor for key " << k;
682 EXPECT_EQ(it->key(), keys[k - 1]) <<
"wrong predecessor for key " << k;
690 auto keys = deepFanOutKeysAtLeafDepth();
699 for (
unsigned int const divergeAt : {0u, 31u, 61u, 62u})
703 for (
char const nibble : {
'9',
'b'})
706 text.append(64 - text.size(),
'0');
711 if (expectedUpper == keys.end())
713 EXPECT_EQ(upper, map.
end()) <<
"divergeAt " << divergeAt <<
" nibble " << nibble;
717 ASSERT_NE(upper, map.
end()) <<
"divergeAt " << divergeAt <<
" nibble " << nibble;
718 EXPECT_EQ(upper->key(), *expectedUpper)
719 <<
"divergeAt " << divergeAt <<
" nibble " << nibble;
726 EXPECT_EQ(lower, map.
end()) <<
"divergeAt " << divergeAt <<
" nibble " << nibble;
730 ASSERT_NE(lower, map.
end()) <<
"divergeAt " << divergeAt <<
" nibble " << nibble;
731 EXPECT_EQ(lower->key(), keys[lowerCount - 1])
732 <<
"divergeAt " << divergeAt <<
" nibble " << nibble;
741 auto keys = deepFanOutKeysAtLeafDepth();
751 ASSERT_TRUE(map.
delItem(keys[k]));
760 for (
auto const& item : map)
762 EXPECT_EQ(visited, expected);
767 ASSERT_NE(it, map.
end());
768 EXPECT_EQ(it->key(), expected[k + 1]);
788 static constexpr unsigned char kFirstKey = 1;
789 static constexpr unsigned char kKeyCount = 100;
790 static constexpr unsigned char kLastKey = kKeyCount - 1;
792 for (
unsigned char c = kFirstKey; c < kKeyCount; ++c)
802 ADD_FAILURE() <<
"Missing proof path";
805 auto& proofPath = *
path;
811 proofPath.insert(proofPath.begin(), proofPath.front());
821 goodPath = std::move(proofPath);
841 badPath.
front().back()--;
862 for (
auto const& k : {kA, kB})
871 ASSERT_TRUE(pathA.has_value());
873 EXPECT_EQ(pathA->size(), 65u);
878 ASSERT_TRUE(pathB.has_value());
880 EXPECT_EQ(pathB->size(), 65u);
890 constexpr UInt256 kTestKey(
"b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8");
911 childHash = node->getHash();
914 ASSERT_EQ(
path.size(), 65u);
933 if (!leaf || !leaf->isLeaf())
961 constexpr UInt256 kKey(
"1c8cec8e5e9b0e5e0e0f5b3e2c9f7a1d6b4e8c2a0d7f3b9e5c1a8d4f2b6e0c93");
962 constexpr UInt256 kOtherKey(
"e3f1a7d5b9c2e8f406a1d3b5c7e9f2a4d6b8c0e2f4a6d8b0c2e4f6a8d0b2c4e6");
964 for (
auto const& k : {kKey, kOtherKey})
973 ASSERT_TRUE(ownPath.has_value());
974 ASSERT_TRUE(otherPath.has_value());
978 auto const& ownLeaf = ownPath->front();
979 auto const& otherLeaf = otherPath->front();
985 ASSERT_EQ(goodPath.size(), 2u);
991 ASSERT_EQ(badPath.size(), 2u);
A generic endpoint for log messages.
static constexpr std::size_t size()
Like std::vector<char> but better.
std::size_t size() const noexcept
Returns the number of bytes in the buffer.
std::uint8_t const * data() const noexcept
Return a pointer to beginning of the storage.
void fill(std::uint8_t value) noexcept
Set every byte in the buffer to the given value.
UInt256 const & asUInt256() const
UInt256 const & key() const
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.
static constexpr unsigned int kBranchFactor
Number of children each non-leaf node has (the 'radix tree' part of the map).
void dump(bool withHashes=false) const
std::map< UInt256, DeltaItem > Delta
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
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
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
int addBitString(BaseUInt< Bits, Tag > const &v)
int add8(unsigned char byteValue)
An immutable linear range of bytes.
static TestSink & instance()
static void applyBackingMode(SHAMap &map)
static Buffer intToVuc(std::uint8_t v)
static constexpr UInt256 kH2
static void addThenDeleteAndReAdd(SHAMap &map)
static constexpr UInt256 kH1
static constexpr UInt256 kH3
static constexpr UInt256 kH4
static std::vector< UInt256 > deepFanOutKeysAtLeafDepth()
static std::vector< UInt256 > deepFanOutKeys()
static void fillMap(SHAMap &map, std::vector< UInt256 > const &keys)
T emplace_back(T... args)
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)
boost::intrusive_ptr< SHAMapItem > makeShamapitem(UInt256 const &tag, Slice data)
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.
static constexpr unsigned char const kWireTypeInner
std::string_view testName