rippled
SHAMap_test.cpp
1 //------------------------------------------------------------------------------
2 /*
3  This file is part of rippled: https://github.com/ripple/rippled
4  Copyright (c) 2012, 2013 Ripple Labs Inc.
5 
6  Permission to use, copy, modify, and/or distribute this software for any
7  purpose with or without fee is hereby granted, provided that the above
8  copyright notice and this permission notice appear in all copies.
9 
10  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13  ANY SPECIAL , DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18 //==============================================================================
19 
20 #include <ripple/basics/Blob.h>
21 #include <ripple/basics/Buffer.h>
22 #include <ripple/beast/unit_test.h>
23 #include <ripple/beast/utility/Journal.h>
24 #include <ripple/shamap/SHAMap.h>
25 #include <test/shamap/common.h>
26 #include <test/unit_test/SuiteJournal.h>
27 
28 namespace ripple {
29 namespace tests {
30 
31 #ifndef __INTELLISENSE__
32 static_assert(std::is_nothrow_destructible<SHAMap>{}, "");
33 static_assert(!std::is_default_constructible<SHAMap>{}, "");
34 static_assert(!std::is_copy_constructible<SHAMap>{}, "");
35 static_assert(!std::is_copy_assignable<SHAMap>{}, "");
36 static_assert(!std::is_move_constructible<SHAMap>{}, "");
37 static_assert(!std::is_move_assignable<SHAMap>{}, "");
38 
39 static_assert(std::is_nothrow_destructible<SHAMap::const_iterator>{}, "");
40 static_assert(std::is_copy_constructible<SHAMap::const_iterator>{}, "");
41 static_assert(std::is_copy_assignable<SHAMap::const_iterator>{}, "");
42 static_assert(std::is_move_constructible<SHAMap::const_iterator>{}, "");
43 static_assert(std::is_move_assignable<SHAMap::const_iterator>{}, "");
44 
45 static_assert(std::is_nothrow_destructible<SHAMapItem>{}, "");
46 static_assert(!std::is_default_constructible<SHAMapItem>{}, "");
47 static_assert(!std::is_copy_constructible<SHAMapItem>{}, "");
48 
49 static_assert(std::is_nothrow_destructible<SHAMapNodeID>{}, "");
50 static_assert(std::is_default_constructible<SHAMapNodeID>{}, "");
51 static_assert(std::is_copy_constructible<SHAMapNodeID>{}, "");
52 static_assert(std::is_copy_assignable<SHAMapNodeID>{}, "");
53 static_assert(std::is_move_constructible<SHAMapNodeID>{}, "");
54 static_assert(std::is_move_assignable<SHAMapNodeID>{}, "");
55 
56 static_assert(std::is_nothrow_destructible<SHAMapHash>{}, "");
57 static_assert(std::is_default_constructible<SHAMapHash>{}, "");
58 static_assert(std::is_copy_constructible<SHAMapHash>{}, "");
59 static_assert(std::is_copy_assignable<SHAMapHash>{}, "");
60 static_assert(std::is_move_constructible<SHAMapHash>{}, "");
61 static_assert(std::is_move_assignable<SHAMapHash>{}, "");
62 
63 static_assert(std::is_nothrow_destructible<SHAMapTreeNode>{}, "");
64 static_assert(!std::is_default_constructible<SHAMapTreeNode>{}, "");
65 static_assert(!std::is_copy_constructible<SHAMapTreeNode>{}, "");
66 static_assert(!std::is_copy_assignable<SHAMapTreeNode>{}, "");
67 static_assert(!std::is_move_constructible<SHAMapTreeNode>{}, "");
68 static_assert(!std::is_move_assignable<SHAMapTreeNode>{}, "");
69 
70 static_assert(std::is_nothrow_destructible<SHAMapInnerNode>{}, "");
71 static_assert(!std::is_default_constructible<SHAMapInnerNode>{}, "");
72 static_assert(!std::is_copy_constructible<SHAMapInnerNode>{}, "");
73 static_assert(!std::is_copy_assignable<SHAMapInnerNode>{}, "");
74 static_assert(!std::is_move_constructible<SHAMapInnerNode>{}, "");
75 static_assert(!std::is_move_assignable<SHAMapInnerNode>{}, "");
76 
77 static_assert(std::is_nothrow_destructible<SHAMapLeafNode>{}, "");
78 static_assert(!std::is_default_constructible<SHAMapLeafNode>{}, "");
79 static_assert(!std::is_copy_constructible<SHAMapLeafNode>{}, "");
80 static_assert(!std::is_copy_assignable<SHAMapLeafNode>{}, "");
81 static_assert(!std::is_move_constructible<SHAMapLeafNode>{}, "");
82 static_assert(!std::is_move_assignable<SHAMapLeafNode>{}, "");
83 #endif
84 
85 inline bool
86 operator==(SHAMapItem const& a, SHAMapItem const& b)
87 {
88  return a.key() == b.key();
89 }
90 inline bool
91 operator!=(SHAMapItem const& a, SHAMapItem const& b)
92 {
93  return a.key() != b.key();
94 }
95 inline bool
96 operator==(SHAMapItem const& a, uint256 const& b)
97 {
98  return a.key() == b;
99 }
100 inline bool
101 operator!=(SHAMapItem const& a, uint256 const& b)
102 {
103  return a.key() != b;
104 }
105 
106 class SHAMap_test : public beast::unit_test::suite
107 {
108 public:
109  static Buffer
110  IntToVUC(int v)
111  {
112  Buffer vuc(32);
113  std::fill_n(vuc.data(), vuc.size(), static_cast<std::uint8_t>(v));
114  return vuc;
115  }
116 
117  void
118  run() override
119  {
120  using namespace beast::severities;
121  test::SuiteJournal journal("SHAMap_test", *this);
122 
123  run(true, journal);
124  run(false, journal);
125  }
126 
127  void
128  run(bool backed, beast::Journal const& journal)
129  {
130  if (backed)
131  testcase("add/traverse backed");
132  else
133  testcase("add/traverse unbacked");
134 
135  tests::TestNodeFamily f(journal);
136 
137  // h3 and h4 differ only in the leaf, same terminal node (level 19)
138  constexpr uint256 h1(
139  "092891fe4ef6cee585fdc6fda0e09eb4d386363158ec3321b8123e5a772c6ca7");
140  constexpr uint256 h2(
141  "436ccbac3347baa1f1e53baeef1f43334da88f1f6d70d963b833afd6dfa289fe");
142  constexpr uint256 h3(
143  "b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e5a772c6ca8");
144  constexpr uint256 h4(
145  "b92891fe4ef6cee585fdc6fda2e09eb4d386363158ec3321b8123e5a772c6ca8");
146  constexpr uint256 h5(
147  "a92891fe4ef6cee585fdc6fda0e09eb4d386363158ec3321b8123e5a772c6ca7");
148 
149  SHAMap sMap(SHAMapType::FREE, f);
150  sMap.invariants();
151  if (!backed)
152  sMap.setUnbacked();
153 
154  auto i1 = make_shamapitem(h1, IntToVUC(1));
155  auto i2 = make_shamapitem(h2, IntToVUC(2));
156  auto i3 = make_shamapitem(h3, IntToVUC(3));
157  auto i4 = make_shamapitem(h4, IntToVUC(4));
158  auto i5 = make_shamapitem(h5, IntToVUC(5));
159 
160  unexpected(
161  !sMap.addItem(
162  SHAMapNodeType::tnTRANSACTION_NM, make_shamapitem(*i2)),
163  "no add");
164  sMap.invariants();
165  unexpected(
166  !sMap.addItem(
167  SHAMapNodeType::tnTRANSACTION_NM, make_shamapitem(*i1)),
168  "no add");
169  sMap.invariants();
170 
171  auto i = sMap.begin();
172  auto e = sMap.end();
173  unexpected(i == e || (*i != *i1), "bad traverse");
174  ++i;
175  unexpected(i == e || (*i != *i2), "bad traverse");
176  ++i;
177  unexpected(i != e, "bad traverse");
178  sMap.addItem(SHAMapNodeType::tnTRANSACTION_NM, make_shamapitem(*i4));
179  sMap.invariants();
180  sMap.delItem(i2->key());
181  sMap.invariants();
182  sMap.addItem(SHAMapNodeType::tnTRANSACTION_NM, make_shamapitem(*i3));
183  sMap.invariants();
184  i = sMap.begin();
185  e = sMap.end();
186  unexpected(i == e || (*i != *i1), "bad traverse");
187  ++i;
188  unexpected(i == e || (*i != *i3), "bad traverse");
189  ++i;
190  unexpected(i == e || (*i != *i4), "bad traverse");
191  ++i;
192  unexpected(i != e, "bad traverse");
193 
194  if (backed)
195  testcase("snapshot backed");
196  else
197  testcase("snapshot unbacked");
198 
199  SHAMapHash mapHash = sMap.getHash();
200  std::shared_ptr<SHAMap> map2 = sMap.snapShot(false);
201  map2->invariants();
202  unexpected(sMap.getHash() != mapHash, "bad snapshot");
203  unexpected(map2->getHash() != mapHash, "bad snapshot");
204 
205  SHAMap::Delta delta;
206  BEAST_EXPECT(sMap.compare(*map2, delta, 100));
207  BEAST_EXPECT(delta.empty());
208 
209  unexpected(!sMap.delItem(sMap.begin()->key()), "bad mod");
210  sMap.invariants();
211  unexpected(sMap.getHash() == mapHash, "bad snapshot");
212  unexpected(map2->getHash() != mapHash, "bad snapshot");
213 
214  BEAST_EXPECT(sMap.compare(*map2, delta, 100));
215  BEAST_EXPECT(delta.size() == 1);
216  BEAST_EXPECT(delta.begin()->first == h1);
217  BEAST_EXPECT(delta.begin()->second.first == nullptr);
218  BEAST_EXPECT(delta.begin()->second.second->key() == h1);
219 
220  sMap.dump();
221 
222  if (backed)
223  testcase("build/tear backed");
224  else
225  testcase("build/tear unbacked");
226  {
227  constexpr std::array keys{
228  uint256("b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
229  "5a772c6ca8"),
230  uint256("b92881fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
231  "5a772c6ca8"),
232  uint256("b92691fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
233  "5a772c6ca8"),
234  uint256("b92791fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
235  "5a772c6ca8"),
236  uint256("b91891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
237  "5a772c6ca8"),
238  uint256("b99891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
239  "5a772c6ca8"),
240  uint256("f22891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
241  "5a772c6ca8"),
242  uint256("292891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
243  "5a772c6ca8")};
244 
245  constexpr std::array hashes{
246  uint256("B7387CFEA0465759ADC718E8C42B52D2309D179B326E239EB5075C"
247  "64B6281F7F"),
248  uint256("FBC195A9592A54AB44010274163CB6BA95F497EC5BA0A883184546"
249  "7FB2ECE266"),
250  uint256("4E7D2684B65DFD48937FFB775E20175C43AF0C94066F7D5679F51A"
251  "E756795B75"),
252  uint256("7A2F312EB203695FFD164E038E281839EEF06A1B99BFC263F3CECC"
253  "6C74F93E07"),
254  uint256("395A6691A372387A703FB0F2C6D2C405DAF307D0817F8F0E207596"
255  "462B0E3A3E"),
256  uint256("D044C0A696DE3169CC70AE216A1564D69DE96582865796142CE7D9"
257  "8A84D9DDE4"),
258  uint256("76DCC77C4027309B5A91AD164083264D70B77B5E43E08AEDA5EBF9"
259  "4361143615"),
260  uint256("DF4220E93ADC6F5569063A01B4DC79F8DB9553B6A3222ADE23DEA0"
261  "2BBE7230E5")};
262 
263  SHAMap map(SHAMapType::FREE, f);
264  if (!backed)
265  map.setUnbacked();
266 
267  BEAST_EXPECT(map.getHash() == beast::zero);
268  for (int k = 0; k < keys.size(); ++k)
269  {
270  BEAST_EXPECT(map.addItem(
271  SHAMapNodeType::tnTRANSACTION_NM,
272  make_shamapitem(keys[k], IntToVUC(k))));
273  BEAST_EXPECT(map.getHash().as_uint256() == hashes[k]);
274  map.invariants();
275  }
276  for (int k = keys.size() - 1; k >= 0; --k)
277  {
278  BEAST_EXPECT(map.getHash().as_uint256() == hashes[k]);
279  BEAST_EXPECT(map.delItem(keys[k]));
280  map.invariants();
281  }
282  BEAST_EXPECT(map.getHash() == beast::zero);
283  }
284 
285  if (backed)
286  testcase("iterate backed");
287  else
288  testcase("iterate unbacked");
289 
290  {
291  constexpr std::array keys{
292  uint256("f22891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
293  "5a772c6ca8"),
294  uint256("b99891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
295  "5a772c6ca8"),
296  uint256("b92891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
297  "5a772c6ca8"),
298  uint256("b92881fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
299  "5a772c6ca8"),
300  uint256("b92791fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
301  "5a772c6ca8"),
302  uint256("b92691fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
303  "5a772c6ca8"),
304  uint256("b91891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
305  "5a772c6ca8"),
306  uint256("292891fe4ef6cee585fdc6fda1e09eb4d386363158ec3321b8123e"
307  "5a772c6ca8")};
308 
309  tests::TestNodeFamily tf{journal};
310  SHAMap map{SHAMapType::FREE, tf};
311  if (!backed)
312  map.setUnbacked();
313  for (auto const& k : keys)
314  {
315  map.addItem(
316  SHAMapNodeType::tnTRANSACTION_NM,
317  make_shamapitem(k, IntToVUC(0)));
318  map.invariants();
319  }
320 
321  int h = 7;
322  for (auto const& k : map)
323  {
324  BEAST_EXPECT(k.key() == keys[h]);
325  --h;
326  }
327  }
328  }
329 };
330 
331 class SHAMapPathProof_test : public beast::unit_test::suite
332 {
333  void
334  run() override
335  {
336  test::SuiteJournal journal("SHAMapPathProof_test", *this);
337 
338  tests::TestNodeFamily tf{journal};
339  SHAMap map{SHAMapType::FREE, tf};
340  map.setUnbacked();
341 
342  uint256 key;
343  uint256 rootHash;
344  std::vector<Blob> goodPath;
345 
346  for (unsigned char c = 1; c < 100; ++c)
347  {
348  uint256 k(c);
349  map.addItem(
350  SHAMapNodeType::tnACCOUNT_STATE,
351  make_shamapitem(k, Slice{k.data(), k.size()}));
352  map.invariants();
353 
354  auto root = map.getHash().as_uint256();
355  auto path = map.getProofPath(k);
356  BEAST_EXPECT(path);
357  if (!path)
358  break;
359  BEAST_EXPECT(map.verifyProofPath(root, k, *path));
360  if (c == 1)
361  {
362  // extra node
363  path->insert(path->begin(), path->front());
364  BEAST_EXPECT(!map.verifyProofPath(root, k, *path));
365  // wrong key
366  uint256 wrongKey(c + 1);
367  BEAST_EXPECT(!map.getProofPath(wrongKey));
368  }
369  if (c == 99)
370  {
371  key = k;
372  rootHash = root;
373  goodPath = std::move(*path);
374  }
375  }
376 
377  // still good
378  BEAST_EXPECT(map.verifyProofPath(rootHash, key, goodPath));
379  // empty path
380  std::vector<Blob> badPath;
381  BEAST_EXPECT(!map.verifyProofPath(rootHash, key, badPath));
382  // too long
383  badPath = goodPath;
384  badPath.push_back(goodPath.back());
385  BEAST_EXPECT(!map.verifyProofPath(rootHash, key, badPath));
386  // bad node
387  badPath.clear();
388  badPath.emplace_back(100, 100);
389  BEAST_EXPECT(!map.verifyProofPath(rootHash, key, badPath));
390  // bad node type
391  badPath.clear();
392  badPath.push_back(goodPath.front());
393  badPath.front().back()--; // change node type
394  BEAST_EXPECT(!map.verifyProofPath(rootHash, key, badPath));
395  // all inner
396  badPath.clear();
397  badPath = goodPath;
398  badPath.erase(badPath.begin());
399  BEAST_EXPECT(!map.verifyProofPath(rootHash, key, badPath));
400  }
401 };
402 
403 BEAST_DEFINE_TESTSUITE(SHAMap, ripple_app, ripple);
404 BEAST_DEFINE_TESTSUITE(SHAMapPathProof, ripple_app, ripple);
405 } // namespace tests
406 } // namespace ripple
ripple::tests::SHAMap_test
Definition: SHAMap_test.cpp:106
ripple::SHAMap::invariants
void invariants() const
Definition: SHAMap.cpp:1188
std::shared_ptr
STL class.
ripple::SHAMap::getHash
SHAMapHash getHash() const
Definition: SHAMap.cpp:852
std::is_nothrow_destructible
ripple::Slice
An immutable linear range of bytes.
Definition: Slice.h:44
ripple::SHAMapNodeType::tnACCOUNT_STATE
@ tnACCOUNT_STATE
ripple::tests::SHAMap_test::run
void run(bool backed, beast::Journal const &journal)
Definition: SHAMap_test.cpp:128
ripple::make_shamapitem
boost::intrusive_ptr< SHAMapItem > make_shamapitem(uint256 const &tag, Slice data)
Definition: SHAMapItem.h:160
ripple::SHAMap::dump
void dump(bool withHashes=false) const
Definition: SHAMap.cpp:1124
std::vector
STL class.
std::map::size
T size(T... args)
ripple::tests::TestNodeFamily
Definition: common.h:32
std::is_default_constructible
beast::severities
A namespace for easy access to logging severity values.
Definition: Journal.h:29
ripple::Buffer
Like std::vector<char> but better.
Definition: Buffer.h:35
ripple::SHAMap::begin
const_iterator begin() const
Definition: SHAMap.h:746
std::vector::back
T back(T... args)
ripple::tests::BEAST_DEFINE_TESTSUITE
BEAST_DEFINE_TESTSUITE(cluster, overlay, ripple)
ripple::SHAMap::snapShot
std::shared_ptr< SHAMap > snapShot(bool isMutable) const
Definition: SHAMap.cpp:88
ripple::tests::SHAMapPathProof_test::run
void run() override
Definition: SHAMap_test.cpp:334
ripple::tests::operator!=
bool operator!=(SHAMapItem const &a, SHAMapItem const &b)
Definition: SHAMap_test.cpp:91
std::vector::front
T front(T... args)
std::is_move_constructible
ripple::SHAMap::addItem
bool addItem(SHAMapNodeType type, boost::intrusive_ptr< SHAMapItem const > item)
Definition: SHAMap.cpp:844
ripple::base_uint::data
pointer data()
Definition: base_uint.h:122
ripple::SHAMapHash
Definition: SHAMapHash.h:32
ripple::tests::SHAMapPathProof_test
Definition: SHAMap_test.cpp:331
ripple::SHAMapNodeType::tnTRANSACTION_NM
@ tnTRANSACTION_NM
std::vector::clear
T clear(T... args)
ripple::base_uint::size
constexpr static std::size_t size()
Definition: base_uint.h:519
ripple::SHAMapItem::key
uint256 const & key() const
Definition: SHAMapItem.h:87
ripple::uint256
base_uint< 256 > uint256
Definition: base_uint.h:550
std::vector::push_back
T push_back(T... args)
ripple::base_uint
Integers of any length that is a multiple of 32-bits.
Definition: base_uint.h:82
ripple::SHAMapItem
Definition: SHAMapItem.h:34
ripple::SHAMap
A SHAMap is both a radix tree with a fan-out of 16 and a Merkle tree.
Definition: SHAMap.h:95
ripple::tests::SHAMap_test::IntToVUC
static Buffer IntToVUC(int v)
Definition: SHAMap_test.cpp:110
std::array
STL class.
ripple::Buffer::size
std::size_t size() const noexcept
Returns the number of bytes in the buffer.
Definition: Buffer.h:126
std::vector::erase
T erase(T... args)
ripple::Buffer::data
std::uint8_t const * data() const noexcept
Return a pointer to beginning of the storage.
Definition: Buffer.h:150
beast::Journal
A generic endpoint for log messages.
Definition: Journal.h:58
std::uint8_t
std::map
STL class.
ripple::tests::operator==
bool operator==(SHAMapItem const &a, SHAMapItem const &b)
Definition: SHAMap_test.cpp:86
ripple::test::SuiteJournal
Definition: SuiteJournal.h:88
std::is_copy_constructible
std::is_move_assignable
std::vector::emplace_back
T emplace_back(T... args)
ripple
Use hash_* containers for keys that do not need a cryptographically secure hashing algorithm.
Definition: RCLCensorshipDetector.h:29
ripple::SHAMap::setUnbacked
void setUnbacked()
Definition: SHAMap.h:631
std::map::begin
T begin(T... args)
ripple::SHAMap::end
const_iterator end() const
Definition: SHAMap.h:752
ripple::tests::SHAMap_test::run
void run() override
Definition: SHAMap_test.cpp:118
std::map::empty
T empty(T... args)
ripple::SHAMap::compare
bool compare(SHAMap const &otherMap, Delta &differences, int maxCount) const
Definition: SHAMapDelta.cpp:124
ripple::SHAMapType::FREE
@ FREE
std::is_copy_assignable
ripple::SHAMapHash::as_uint256
uint256 const & as_uint256() const
Definition: SHAMapHash.h:43
std::fill_n
T fill_n(T... args)
ripple::SHAMap::delItem
bool delItem(uint256 const &id)
Definition: SHAMap.cpp:696
ripple::root
Number root(Number f, unsigned d)
Definition: Number.cpp:624
Generated by   doxygen 1.8.17