xrpld
Loading...
Searching...
No Matches
SHAMap_test.cpp
1#include <test/shamap/common.h>
2#include <test/unit_test/SuiteJournal.h>
3
4#include <xrpl/basics/Blob.h>
5#include <xrpl/basics/Buffer.h>
6#include <xrpl/basics/SHAMapHash.h>
7#include <xrpl/basics/base_uint.h>
8#include <xrpl/beast/unit_test/suite.h>
9#include <xrpl/beast/utility/Journal.h>
10#include <xrpl/beast/utility/Zero.h>
11#include <xrpl/shamap/SHAMap.h>
12#include <xrpl/shamap/SHAMapInnerNode.h>
13#include <xrpl/shamap/SHAMapItem.h>
14#include <xrpl/shamap/SHAMapLeafNode.h>
15#include <xrpl/shamap/SHAMapMissingNode.h>
16#include <xrpl/shamap/SHAMapTreeNode.h>
17
18#include <algorithm>
19#include <array>
20#include <cstdint>
21#include <memory>
22#include <type_traits>
23#include <utility>
24#include <vector>
25
26namespace xrpl::tests {
27
28#ifndef __INTELLISENSE__
29static_assert(std::is_nothrow_destructible<SHAMap>{}, "");
30static_assert(!std::is_default_constructible<SHAMap>{}, "");
31static_assert(!std::is_copy_constructible<SHAMap>{}, "");
32static_assert(!std::is_copy_assignable<SHAMap>{}, "");
33static_assert(!std::is_move_constructible<SHAMap>{}, "");
34static_assert(!std::is_move_assignable<SHAMap>{}, "");
35
36static_assert(std::is_nothrow_destructible<SHAMap::ConstIterator>{}, "");
37static_assert(std::is_copy_constructible<SHAMap::ConstIterator>{}, "");
38static_assert(std::is_copy_assignable<SHAMap::ConstIterator>{}, "");
39static_assert(std::is_move_constructible<SHAMap::ConstIterator>{}, "");
40static_assert(std::is_move_assignable<SHAMap::ConstIterator>{}, "");
41
42static_assert(std::is_nothrow_destructible<SHAMapItem>{}, "");
43static_assert(!std::is_default_constructible<SHAMapItem>{}, "");
44static_assert(!std::is_copy_constructible<SHAMapItem>{}, "");
45
46static_assert(std::is_nothrow_destructible<SHAMapNodeID>{}, "");
47static_assert(std::is_default_constructible<SHAMapNodeID>{}, "");
48static_assert(std::is_copy_constructible<SHAMapNodeID>{}, "");
49static_assert(std::is_copy_assignable<SHAMapNodeID>{}, "");
50static_assert(std::is_move_constructible<SHAMapNodeID>{}, "");
51static_assert(std::is_move_assignable<SHAMapNodeID>{}, "");
52
53static_assert(std::is_nothrow_destructible<SHAMapHash>{}, "");
54static_assert(std::is_default_constructible<SHAMapHash>{}, "");
55static_assert(std::is_copy_constructible<SHAMapHash>{}, "");
56static_assert(std::is_copy_assignable<SHAMapHash>{}, "");
57static_assert(std::is_move_constructible<SHAMapHash>{}, "");
58static_assert(std::is_move_assignable<SHAMapHash>{}, "");
59
60static_assert(std::is_nothrow_destructible<SHAMapTreeNode>{}, "");
61static_assert(!std::is_default_constructible<SHAMapTreeNode>{}, "");
62static_assert(!std::is_copy_constructible<SHAMapTreeNode>{}, "");
63static_assert(!std::is_copy_assignable<SHAMapTreeNode>{}, "");
64static_assert(!std::is_move_constructible<SHAMapTreeNode>{}, "");
65static_assert(!std::is_move_assignable<SHAMapTreeNode>{}, "");
66
67static_assert(std::is_nothrow_destructible<SHAMapInnerNode>{}, "");
68static_assert(!std::is_default_constructible<SHAMapInnerNode>{}, "");
69static_assert(!std::is_copy_constructible<SHAMapInnerNode>{}, "");
70static_assert(!std::is_copy_assignable<SHAMapInnerNode>{}, "");
71static_assert(!std::is_move_constructible<SHAMapInnerNode>{}, "");
72static_assert(!std::is_move_assignable<SHAMapInnerNode>{}, "");
73
74static_assert(std::is_nothrow_destructible<SHAMapLeafNode>{}, "");
75static_assert(!std::is_default_constructible<SHAMapLeafNode>{}, "");
76static_assert(!std::is_copy_constructible<SHAMapLeafNode>{}, "");
77static_assert(!std::is_copy_assignable<SHAMapLeafNode>{}, "");
78static_assert(!std::is_move_constructible<SHAMapLeafNode>{}, "");
79static_assert(!std::is_move_assignable<SHAMapLeafNode>{}, "");
80#endif
81
82inline bool
83operator==(SHAMapItem const& a, SHAMapItem const& b)
84{
85 return a.key() == b.key();
86}
87inline bool
88operator!=(SHAMapItem const& a, SHAMapItem const& b)
89{
90 return a.key() != b.key();
91}
92inline bool
93operator==(SHAMapItem const& a, uint256 const& b)
94{
95 return a.key() == b;
96}
97inline bool
98operator!=(SHAMapItem const& a, uint256 const& b)
99{
100 return a.key() != b;
101}
102
103class SHAMap_test : public beast::unit_test::Suite
104{
105public:
106 static Buffer
107 intToVuc(int v)
108 {
109 Buffer vuc(32);
110 std::fill_n(vuc.data(), vuc.size(), static_cast<std::uint8_t>(v));
111 return vuc;
112 }
113
114 void
115 run() override
116 {
117 using beast::Severity;
118 test::SuiteJournal journal("SHAMap_test", *this);
119
120 run(true, journal);
121 run(false, journal);
122 }
123
124 void
125 run(bool backed, beast::Journal const& journal)
126 {
127 if (backed)
128 {
129 testcase("add/traverse backed");
130 }
131 else
132 {
133 testcase("add/traverse unbacked");
134 }
135
136 tests::TestNodeFamily f(journal);
137
138 // h3 and h4 differ only in the leaf, same terminal node (level 19)
139 constexpr uint256 kH1("092891fe4ef6cee585fdc6fda0e09eb4d386363158ec3321b8123e5a772c6ca7");
140 constexpr uint256 kH2("436ccbac3347baa1f1e53baeef1f43334da88f1f6d70d963b833afd6dfa289fe");
141 constexpr uint256 kH3("b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8");
142 constexpr uint256 kH4("b92891fe4ef6cee585fdc6fda2e09eb4d386363158ec3321b8123e5a772c6ca8");
143 constexpr uint256 kH5("a92891fe4ef6cee585fdc6fda0e09eb4d386363158ec3321b8123e5a772c6ca7");
144
145 SHAMap sMap(SHAMapType::FREE, f);
146 sMap.invariants();
147 if (!backed)
148 sMap.setUnbacked();
149
150 auto i1 = makeShamapitem(kH1, intToVuc(1));
151 auto i2 = makeShamapitem(kH2, intToVuc(2));
152 auto i3 = makeShamapitem(kH3, intToVuc(3));
153 auto i4 = makeShamapitem(kH4, intToVuc(4));
154 auto i5 = makeShamapitem(kH5, intToVuc(5));
155
156 unexpected(!sMap.addItem(SHAMapNodeType::TnTransactionNm, makeShamapitem(*i2)), "no add");
157 sMap.invariants();
158 unexpected(!sMap.addItem(SHAMapNodeType::TnTransactionNm, makeShamapitem(*i1)), "no add");
159 sMap.invariants();
160
161 auto i = sMap.begin();
162 auto e = sMap.end();
163 unexpected(i == e || (*i != *i1), "bad traverse");
164 ++i;
165 unexpected(i == e || (*i != *i2), "bad traverse");
166 ++i;
167 unexpected(i != e, "bad traverse");
168 sMap.addItem(SHAMapNodeType::TnTransactionNm, makeShamapitem(*i4));
169 sMap.invariants();
170 sMap.delItem(i2->key());
171 sMap.invariants();
172 sMap.addItem(SHAMapNodeType::TnTransactionNm, makeShamapitem(*i3));
173 sMap.invariants();
174 i = sMap.begin();
175 e = sMap.end();
176 unexpected(i == e || (*i != *i1), "bad traverse");
177 ++i;
178 unexpected(i == e || (*i != *i3), "bad traverse");
179 ++i;
180 unexpected(i == e || (*i != *i4), "bad traverse");
181 ++i;
182 unexpected(i != e, "bad traverse");
183
184 if (backed)
185 {
186 testcase("snapshot backed");
187 }
188 else
189 {
190 testcase("snapshot unbacked");
191 }
192
193 SHAMapHash const mapHash = sMap.getHash();
194 std::shared_ptr<SHAMap> const map2 = sMap.snapShot(false);
195 map2->invariants();
196 unexpected(sMap.getHash() != mapHash, "bad snapshot");
197 unexpected(map2->getHash() != mapHash, "bad snapshot");
198
199 SHAMap::Delta delta;
200 BEAST_EXPECT(sMap.compare(*map2, delta, 100));
201 BEAST_EXPECT(delta.empty());
202
203 unexpected(!sMap.delItem(sMap.begin()->key()), "bad mod");
204 sMap.invariants();
205 unexpected(sMap.getHash() == mapHash, "bad snapshot");
206 unexpected(map2->getHash() != mapHash, "bad snapshot");
207
208 BEAST_EXPECT(sMap.compare(*map2, delta, 100));
209 BEAST_EXPECT(delta.size() == 1);
210 BEAST_EXPECT(delta.begin()->first == kH1);
211 BEAST_EXPECT(delta.begin()->second.first == nullptr);
212 BEAST_EXPECT(delta.begin()->second.second->key() == kH1);
213
214 sMap.dump();
215
216 if (backed)
217 {
218 testcase("build/tear backed");
219 }
220 else
221 {
222 testcase("build/tear unbacked");
223 }
224 {
225 static constexpr std::array keys{
226 uint256(
227 "b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
228 "5a772c6ca8"),
229 uint256(
230 "b92881fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
231 "5a772c6ca8"),
232 uint256(
233 "b92691fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
234 "5a772c6ca8"),
235 uint256(
236 "b92791fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
237 "5a772c6ca8"),
238 uint256(
239 "b91891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
240 "5a772c6ca8"),
241 uint256(
242 "b99891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
243 "5a772c6ca8"),
244 uint256(
245 "f22891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
246 "5a772c6ca8"),
247 uint256(
248 "292891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
249 "5a772c6ca8")};
250
251 static constexpr std::array kHashes{
252 uint256(
253 "B7387CFEA0465759ADC718E8C42B52D2309D179B326E239EB5075C"
254 "64B6281F7F"),
255 uint256(
256 "FBC195A9592A54AB44010274163CB6BA95F497EC5BA0A883184546"
257 "7FB2ECE266"),
258 uint256(
259 "4E7D2684B65DFD48937FFB775E20175C43AF0C94066F7D5679F51A"
260 "E756795B75"),
261 uint256(
262 "7A2F312EB203695FFD164E038E281839EEF06A1B99BFC263F3CECC"
263 "6C74F93E07"),
264 uint256(
265 "395A6691A372387A703FB0F2C6D2C405DAF307D0817F8F0E207596"
266 "462B0E3A3E"),
267 uint256(
268 "D044C0A696DE3169CC70AE216A1564D69DE96582865796142CE7D9"
269 "8A84D9DDE4"),
270 uint256(
271 "76DCC77C4027309B5A91AD164083264D70B77B5E43E08AEDA5EBF9"
272 "4361143615"),
273 uint256(
274 "DF4220E93ADC6F5569063A01B4DC79F8DB9553B6A3222ADE23DEA0"
275 "2BBE7230E5")};
276
277 SHAMap map(SHAMapType::FREE, f);
278 if (!backed)
279 map.setUnbacked();
280
281 BEAST_EXPECT(map.getHash() == beast::kZero);
282 for (int k = 0; k < keys.size(); ++k)
283 {
284 BEAST_EXPECT(map.addItem(
285 SHAMapNodeType::TnTransactionNm, makeShamapitem(keys[k], intToVuc(k))));
286 BEAST_EXPECT(map.getHash().asUInt256() == kHashes[k]);
287 map.invariants();
288 }
289 for (int k = keys.size() - 1; k >= 0; --k)
290 {
291 BEAST_EXPECT(map.getHash().asUInt256() == kHashes[k]);
292 BEAST_EXPECT(map.delItem(keys[k]));
293 map.invariants();
294 }
295 BEAST_EXPECT(map.getHash() == beast::kZero);
296 }
297
298 if (backed)
299 {
300 testcase("iterate backed");
301 }
302 else
303 {
304 testcase("iterate unbacked");
305 }
306
307 {
308 static constexpr std::array keys{
309 uint256(
310 "f22891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
311 "5a772c6ca8"),
312 uint256(
313 "b99891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
314 "5a772c6ca8"),
315 uint256(
316 "b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
317 "5a772c6ca8"),
318 uint256(
319 "b92881fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
320 "5a772c6ca8"),
321 uint256(
322 "b92791fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
323 "5a772c6ca8"),
324 uint256(
325 "b92691fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
326 "5a772c6ca8"),
327 uint256(
328 "b91891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
329 "5a772c6ca8"),
330 uint256(
331 "292891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
332 "5a772c6ca8")};
333
334 tests::TestNodeFamily tf{journal};
335 SHAMap map{SHAMapType::FREE, tf};
336 if (!backed)
337 map.setUnbacked();
338 for (auto const& k : keys)
339 {
340 map.addItem(SHAMapNodeType::TnTransactionNm, makeShamapitem(k, intToVuc(0)));
341 map.invariants();
342 }
343
344 int h = 7;
345 for (auto const& k : map)
346 {
347 BEAST_EXPECT(k.key() == keys[h]);
348 --h;
349 }
350 }
351 }
352};
353
354class SHAMapPathProof_test : public beast::unit_test::Suite
355{
356 void
357 run() override
358 {
359 test::SuiteJournal journal("SHAMapPathProof_test", *this);
360
361 tests::TestNodeFamily tf{journal};
362 SHAMap map{SHAMapType::FREE, tf};
363 map.setUnbacked();
364
365 uint256 key;
366 uint256 rootHash;
367 std::vector<Blob> goodPath;
368
369 for (unsigned char c = 1; c < 100; ++c)
370 {
371 uint256 k(c);
372 map.addItem(
373 SHAMapNodeType::TnAccountState, makeShamapitem(k, Slice{k.data(), k.size()}));
374 map.invariants();
375
376 auto root = map.getHash().asUInt256();
377 auto path = map.getProofPath(k);
378 BEAST_EXPECT(path);
379 if (!path)
380 break;
381 BEAST_EXPECT(map.verifyProofPath(root, k, *path));
382 if (c == 1)
383 {
384 // extra node
385 path->insert(path->begin(), path->front());
386 BEAST_EXPECT(!map.verifyProofPath(root, k, *path));
387 // wrong key
388 uint256 const wrongKey(c + 1);
389 BEAST_EXPECT(!map.getProofPath(wrongKey));
390 }
391 if (c == 99)
392 {
393 key = k;
394 rootHash = root;
395 goodPath = std::move(*path);
396 }
397 }
398
399 // still good
400 BEAST_EXPECT(map.verifyProofPath(rootHash, key, goodPath));
401 // empty path
402 std::vector<Blob> badPath;
403 BEAST_EXPECT(!map.verifyProofPath(rootHash, key, badPath));
404 // too long
405 badPath = goodPath;
406 badPath.push_back(goodPath.back());
407 BEAST_EXPECT(!map.verifyProofPath(rootHash, key, badPath));
408 // bad node
409 badPath.clear();
410 badPath.emplace_back(100, 100);
411 BEAST_EXPECT(!map.verifyProofPath(rootHash, key, badPath));
412 // bad node type
413 badPath.clear();
414 badPath.push_back(goodPath.front());
415 badPath.front().back()--; // change node type
416 BEAST_EXPECT(!map.verifyProofPath(rootHash, key, badPath));
417 // all inner
418 badPath.clear();
419 badPath = goodPath;
420 badPath.erase(badPath.begin());
421 BEAST_EXPECT(!map.verifyProofPath(rootHash, key, badPath));
422 }
423};
424
425BEAST_DEFINE_TESTSUITE(SHAMap, shamap, xrpl);
426BEAST_DEFINE_TESTSUITE(SHAMapPathProof, shamap, xrpl);
427} // namespace xrpl::tests
std::vector::back
T back(T... args)
std::map::begin
T begin(T... args)
beast::Journal
A generic endpoint for log messages.
Definition Journal.h:38
beast::unit_test::Suite
A testsuite class.
Definition suite.h:50
beast::unit_test::Suite::unexpected
bool unexpected(Condition shouldBeFalse, String const &reason)
Definition suite.h:484
beast::unit_test::Suite::testcase
TestcaseT testcase
Memberspace for declaring test cases.
Definition suite.h:149
xrpl::BaseUInt::data
pointer data()
Definition base_uint.h:106
xrpl::BaseUInt::size
static constexpr std::size_t size()
Definition base_uint.h:530
xrpl::Buffer
Like std::vector<char> but better.
Definition Buffer.h:16
xrpl::Buffer::size
std::size_t size() const noexcept
Returns the number of bytes in the buffer.
Definition Buffer.h:105
xrpl::Buffer::data
std::uint8_t const * data() const noexcept
Return a pointer to beginning of the storage.
Definition Buffer.h:129
xrpl::SHAMapHash::asUInt256
uint256 const & asUInt256() const
Definition SHAMapHash.h:24
xrpl::SHAMapItem::key
uint256 const & key() const
Definition SHAMapItem.h:66
xrpl::SHAMap
A SHAMap is both a radix tree with a fan-out of 16 and a Merkle tree.
Definition SHAMap.h:77
xrpl::SHAMap::addItem
bool addItem(SHAMapNodeType type, boost::intrusive_ptr< SHAMapItem const > item)
Definition SHAMap.cpp:830
xrpl::SHAMap::verifyProofPath
static bool verifyProofPath(uint256 const &rootHash, uint256 const &key, std::vector< Blob > const &path)
Verify the proof path.
Definition SHAMapSync.cpp:808
xrpl::SHAMap::getProofPath
std::optional< std::vector< Blob > > getProofPath(uint256 const &key) const
Get the proof path of the key.
Definition SHAMapSync.cpp:775
xrpl::SHAMap::Delta
std::map< uint256, DeltaItem > Delta
Definition SHAMap.h:104
xrpl::SHAMap::setUnbacked
void setUnbacked()
Definition SHAMap.h:570
xrpl::SHAMap::dump
void dump(bool withHashes=false) const
Definition SHAMap.cpp:1105
xrpl::SHAMap::compare
bool compare(SHAMap const &otherMap, Delta &differences, int maxCount) const
Definition SHAMapDelta.cpp:130
xrpl::SHAMap::snapShot
std::shared_ptr< SHAMap > snapShot(bool isMutable) const
Definition SHAMap.cpp:94
xrpl::SHAMap::invariants
void invariants() const
Definition SHAMap.cpp:1170
xrpl::SHAMap::end
ConstIterator end() const
Definition SHAMap.h:697
xrpl::SHAMap::getHash
SHAMapHash getHash() const
Definition SHAMap.cpp:836
xrpl::SHAMap::begin
ConstIterator begin() const
Definition SHAMap.h:691
xrpl::SHAMap::delItem
bool delItem(uint256 const &id)
Definition SHAMap.cpp:678
xrpl::Slice
An immutable linear range of bytes.
Definition Slice.h:26
xrpl::tests::SHAMapPathProof_test
Definition SHAMap_test.cpp:355
xrpl::tests::SHAMapPathProof_test::run
void run() override
Runs the suite.
Definition SHAMap_test.cpp:357
xrpl::tests::SHAMap_test
Definition SHAMap_test.cpp:104
xrpl::tests::SHAMap_test::run
void run() override
Runs the suite.
Definition SHAMap_test.cpp:115
xrpl::tests::SHAMap_test::run
void run(bool backed, beast::Journal const &journal)
Definition SHAMap_test.cpp:125
xrpl::tests::SHAMap_test::intToVuc
static Buffer intToVuc(int v)
Definition SHAMap_test.cpp:107
std::vector::clear
T clear(T... args)
std::vector::emplace_back
T emplace_back(T... args)
std::map::empty
T empty(T... args)
std::vector::erase
T erase(T... args)
std::fill_n
T fill_n(T... args)
std::vector::front
T front(T... args)
beast::Severity
Severity
Severity level / threshold of a Journal message.
Definition Journal.h:11
xrpl::tests::operator==
bool operator==(SHAMapItem const &a, SHAMapItem const &b)
Definition SHAMap_test.cpp:83
xrpl::tests::operator!=
bool operator!=(SHAMapItem const &a, SHAMapItem const &b)
Definition SHAMap_test.cpp:88
xrpl::tests::BEAST_DEFINE_TESTSUITE
BEAST_DEFINE_TESTSUITE(IntrusiveShared, basics, xrpl)
xrpl
Use hash_* containers for keys that do not need a cryptographically secure hashing algorithm.
Definition algorithm.h:5
xrpl::root
Number root(Number f, unsigned d)
Definition Number.cpp:1201
xrpl::makeShamapitem
boost::intrusive_ptr< SHAMapItem > makeShamapitem(uint256 const &tag, Slice data)
Definition SHAMapItem.h:139
xrpl::uint256
BaseUInt< 256 > uint256
Definition base_uint.h:562
std::vector::push_back
T push_back(T... args)
std::map::size
T size(T... args)
Generated by doxygen 1.16.1