• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright 2021 The Abseil Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 //     https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 #include "absl/strings/internal/cord_rep_btree.h"
16 
17 #include <cmath>
18 #include <deque>
19 #include <iostream>
20 #include <string>
21 #include <vector>
22 
23 #include "gmock/gmock.h"
24 #include "gtest/gtest.h"
25 #include "absl/base/config.h"
26 #include "absl/base/internal/raw_logging.h"
27 #include "absl/cleanup/cleanup.h"
28 #include "absl/strings/internal/cord_internal.h"
29 #include "absl/strings/internal/cord_rep_test_util.h"
30 #include "absl/strings/str_cat.h"
31 #include "absl/strings/string_view.h"
32 
33 namespace absl {
34 ABSL_NAMESPACE_BEGIN
35 namespace cord_internal {
36 
37 class CordRepBtreeTestPeer {
38  public:
SetEdge(CordRepBtree * node,size_t idx,CordRep * edge)39   static void SetEdge(CordRepBtree* node, size_t idx, CordRep* edge) {
40     node->edges_[idx] = edge;
41   }
AddEdge(CordRepBtree * node,CordRep * edge)42   static void AddEdge(CordRepBtree* node, CordRep* edge) {
43     node->edges_[node->fetch_add_end(1)] = edge;
44   }
45 };
46 
47 namespace {
48 
49 using ::absl::cordrep_testing::AutoUnref;
50 using ::absl::cordrep_testing::CordToString;
51 using ::absl::cordrep_testing::CreateFlatsFromString;
52 using ::absl::cordrep_testing::CreateRandomString;
53 using ::absl::cordrep_testing::MakeConcat;
54 using ::absl::cordrep_testing::MakeExternal;
55 using ::absl::cordrep_testing::MakeFlat;
56 using ::absl::cordrep_testing::MakeSubstring;
57 using ::testing::_;
58 using ::testing::AllOf;
59 using ::testing::AnyOf;
60 using ::testing::Conditional;
61 using ::testing::ElementsAre;
62 using ::testing::ElementsAreArray;
63 using ::testing::Eq;
64 using ::testing::HasSubstr;
65 using ::testing::Ne;
66 using ::testing::Not;
67 using ::testing::SizeIs;
68 using ::testing::TypedEq;
69 
70 MATCHER_P(EqFlatHolding, data, "Equals flat holding data") {
71   if (arg->tag < FLAT) {
72     *result_listener << "Expected FLAT, got tag " << static_cast<int>(arg->tag);
73     return false;
74   }
75   std::string actual = CordToString(arg);
76   if (actual != data) {
77     *result_listener << "Expected flat holding \"" << data
78                      << "\", got flat holding \"" << actual << "\"";
79     return false;
80   }
81   return true;
82 }
83 
84 MATCHER_P(IsNode, height, absl::StrCat("Is a valid node of height ", height)) {
85   if (arg == nullptr) {
86     *result_listener << "Expected NODE, got nullptr";
87     return false;
88   }
89   if (arg->tag != BTREE) {
90     *result_listener << "Expected NODE, got " << static_cast<int>(arg->tag);
91     return false;
92   }
93   if (!CordRepBtree::IsValid(arg->btree())) {
94     CordRepBtree::Dump(arg->btree(), "Expected valid NODE, got:", false,
95                        *result_listener->stream());
96     return false;
97   }
98   if (arg->btree()->height() != height) {
99     *result_listener << "Expected NODE of height " << height << ", got "
100                      << arg->btree()->height();
101     return false;
102   }
103   return true;
104 }
105 
106 MATCHER_P2(IsSubstring, start, length,
107            absl::StrCat("Is a substring(start = ", start, ", length = ", length,
108                         ")")) {
109   if (arg == nullptr) {
110     *result_listener << "Expected substring, got nullptr";
111     return false;
112   }
113   if (arg->tag != SUBSTRING) {
114     *result_listener << "Expected SUBSTRING, got "
115                      << static_cast<int>(arg->tag);
116     return false;
117   }
118   const CordRepSubstring* const substr = arg->substring();
119   if (substr->start != start || substr->length != length) {
120     *result_listener << "Expected substring(" << start << ", " << length
121                      << "), got substring(" << substr->start << ", "
122                      << substr->length << ")";
123     return false;
124   }
125   return true;
126 }
127 
128 // DataConsumer is a simple helper class used by tests to 'consume' string
129 // fragments from the provided input in forward or backward direction.
130 class DataConsumer {
131  public:
132   // Starts consumption of `data`. Caller must make sure `data` outlives this
133   // instance. Consumes data starting at the front if `forward` is true, else
134   // consumes data from the back.
DataConsumer(absl::string_view data,bool forward)135   DataConsumer(absl::string_view data, bool forward)
136       : data_(data), forward_(forward) {}
137 
138   // Return the next `n` bytes from referenced data.
Next(size_t n)139   absl::string_view Next(size_t n) {
140     assert(n <= data_.size() - consumed_);
141     consumed_ += n;
142     return data_.substr(forward_ ? consumed_ - n : data_.size() - consumed_, n);
143   }
144 
145   // Returns all data consumed so far.
Consumed() const146   absl::string_view Consumed() const {
147     return forward_ ? data_.substr(0, consumed_)
148                     : data_.substr(data_.size() - consumed_);
149   }
150 
151  private:
152   absl::string_view data_;
153   size_t consumed_ = 0;
154   bool forward_;
155 };
156 
157 // BtreeAdd returns either CordRepBtree::Append or CordRepBtree::Prepend.
BtreeAdd(CordRepBtree * node,bool append,absl::string_view data)158 CordRepBtree* BtreeAdd(CordRepBtree* node, bool append,
159                        absl::string_view data) {
160   return append ? CordRepBtree::Append(node, data)
161                 : CordRepBtree::Prepend(node, data);
162 }
163 
164 // Recursively collects all leaf edges from `tree` and appends them to `edges`.
GetLeafEdges(const CordRepBtree * tree,std::vector<CordRep * > & edges)165 void GetLeafEdges(const CordRepBtree* tree, std::vector<CordRep*>& edges) {
166   if (tree->height() == 0) {
167     for (CordRep* edge : tree->Edges()) {
168       edges.push_back(edge);
169     }
170   } else {
171     for (CordRep* edge : tree->Edges()) {
172       GetLeafEdges(edge->btree(), edges);
173     }
174   }
175 }
176 
177 // Recursively collects and returns all leaf edges from `tree`.
GetLeafEdges(const CordRepBtree * tree)178 std::vector<CordRep*> GetLeafEdges(const CordRepBtree* tree) {
179   std::vector<CordRep*> edges;
180   GetLeafEdges(tree, edges);
181   return edges;
182 }
183 
184 // Creates a flat containing the hexadecimal value of `i` zero padded
185 // to at least 4 digits prefixed with "0x", e.g.: "0x04AC".
MakeHexFlat(size_t i)186 CordRepFlat* MakeHexFlat(size_t i) {
187   return MakeFlat(absl::StrCat("0x", absl::Hex(i, absl::kZeroPad4)));
188 }
189 
MakeLeaf(size_t size=CordRepBtree::kMaxCapacity)190 CordRepBtree* MakeLeaf(size_t size = CordRepBtree::kMaxCapacity) {
191   assert(size <= CordRepBtree::kMaxCapacity);
192   CordRepBtree* leaf = CordRepBtree::Create(MakeHexFlat(0));
193   for (size_t i = 1; i < size; ++i) {
194     leaf = CordRepBtree::Append(leaf, MakeHexFlat(i));
195   }
196   return leaf;
197 }
198 
MakeTree(size_t size,bool append=true)199 CordRepBtree* MakeTree(size_t size, bool append = true) {
200   CordRepBtree* tree = CordRepBtree::Create(MakeHexFlat(0));
201   for (size_t i = 1; i < size; ++i) {
202     tree = append ? CordRepBtree::Append(tree, MakeHexFlat(i))
203                   : CordRepBtree::Prepend(tree, MakeHexFlat(i));
204   }
205   return tree;
206 }
207 
CreateTree(absl::string_view data,size_t chunk_size)208 CordRepBtree* CreateTree(absl::string_view data, size_t chunk_size) {
209   std::vector<CordRep*> flats = CreateFlatsFromString(data, chunk_size);
210   auto it = flats.begin();
211   CordRepBtree* tree = CordRepBtree::Create(*it);
212   while (++it != flats.end()) tree = CordRepBtree::Append(tree, *it);
213   return tree;
214 }
215 
CreateTreeReverse(absl::string_view data,size_t chunk_size)216 CordRepBtree* CreateTreeReverse(absl::string_view data, size_t chunk_size) {
217   std::vector<CordRep*> flats = CreateFlatsFromString(data, chunk_size);
218   auto rit = flats.rbegin();
219   CordRepBtree* tree = CordRepBtree::Create(*rit);
220   while (++rit != flats.rend()) tree = CordRepBtree::Prepend(tree, *rit);
221   return tree;
222 }
223 
224 class CordRepBtreeTest : public testing::TestWithParam<bool> {
225  public:
shared() const226   bool shared() const { return GetParam(); }
227 
ToString(testing::TestParamInfo<bool> param)228   static std::string ToString(testing::TestParamInfo<bool> param) {
229     return param.param ? "Shared" : "Private";
230   }
231 };
232 
233 INSTANTIATE_TEST_SUITE_P(WithParam, CordRepBtreeTest, testing::Bool(),
234                          CordRepBtreeTest::ToString);
235 
236 class CordRepBtreeHeightTest : public testing::TestWithParam<int> {
237  public:
height() const238   int height() const { return GetParam(); }
239 
ToString(testing::TestParamInfo<int> param)240   static std::string ToString(testing::TestParamInfo<int> param) {
241     return absl::StrCat(param.param);
242   }
243 };
244 
245 INSTANTIATE_TEST_SUITE_P(WithHeights, CordRepBtreeHeightTest,
246                          testing::Range(0, CordRepBtree::kMaxHeight),
247                          CordRepBtreeHeightTest::ToString);
248 
249 using TwoBools = testing::tuple<bool, bool>;
250 
251 class CordRepBtreeDualTest : public testing::TestWithParam<TwoBools> {
252  public:
first_shared() const253   bool first_shared() const { return std::get<0>(GetParam()); }
second_shared() const254   bool second_shared() const { return std::get<1>(GetParam()); }
255 
ToString(testing::TestParamInfo<TwoBools> param)256   static std::string ToString(testing::TestParamInfo<TwoBools> param) {
257     if (std::get<0>(param.param)) {
258       return std::get<1>(param.param) ? "BothShared" : "FirstShared";
259     }
260     return std::get<1>(param.param) ? "SecondShared" : "Private";
261   }
262 };
263 
264 INSTANTIATE_TEST_SUITE_P(WithParam, CordRepBtreeDualTest,
265                          testing::Combine(testing::Bool(), testing::Bool()),
266                          CordRepBtreeDualTest::ToString);
267 
TEST(CordRepBtreeTest,SizeIsMultipleOf64)268 TEST(CordRepBtreeTest, SizeIsMultipleOf64) {
269   // Only enforce for fully 64-bit platforms.
270   if (sizeof(size_t) == 8 && sizeof(void*) == 8) {
271     EXPECT_THAT(sizeof(CordRepBtree) % 64, Eq(0)) << "Should be multiple of 64";
272   }
273 }
274 
TEST(CordRepBtreeTest,NewDestroyEmptyTree)275 TEST(CordRepBtreeTest, NewDestroyEmptyTree) {
276   auto* tree = CordRepBtree::New();
277   EXPECT_THAT(tree->size(), Eq(0));
278   EXPECT_THAT(tree->height(), Eq(0));
279   EXPECT_THAT(tree->Edges(), ElementsAre());
280   CordRepBtree::Destroy(tree);
281 }
282 
TEST(CordRepBtreeTest,NewDestroyEmptyTreeAtHeight)283 TEST(CordRepBtreeTest, NewDestroyEmptyTreeAtHeight) {
284   auto* tree = CordRepBtree::New(3);
285   EXPECT_THAT(tree->size(), Eq(0));
286   EXPECT_THAT(tree->height(), Eq(3));
287   EXPECT_THAT(tree->Edges(), ElementsAre());
288   CordRepBtree::Destroy(tree);
289 }
290 
TEST(CordRepBtreeTest,Btree)291 TEST(CordRepBtreeTest, Btree) {
292   CordRep* rep = CordRepBtree::New();
293   EXPECT_THAT(rep->btree(), Eq(rep));
294   EXPECT_THAT(static_cast<const CordRep*>(rep)->btree(), Eq(rep));
295   CordRep::Unref(rep);
296 #if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
297   rep = MakeFlat("Hello world");
298   EXPECT_DEATH(rep->btree(), ".*");
299   EXPECT_DEATH(static_cast<const CordRep*>(rep)->btree(), ".*");
300   CordRep::Unref(rep);
301 #endif
302 }
303 
TEST(CordRepBtreeTest,EdgeData)304 TEST(CordRepBtreeTest, EdgeData) {
305   CordRepFlat* flat = MakeFlat("Hello world");
306   CordRepExternal* external = MakeExternal("Hello external");
307   CordRep* substr1 = MakeSubstring(1, 6, CordRep::Ref(flat));
308   CordRep* substr2 = MakeSubstring(1, 6, CordRep::Ref(external));
309   CordRep* concat = MakeConcat(CordRep::Ref(flat), CordRep::Ref(external));
310   CordRep* bad_substr = MakeSubstring(1, 2, CordRep::Ref(substr1));
311 
312   EXPECT_TRUE(CordRepBtree::IsDataEdge(flat));
313   EXPECT_THAT(CordRepBtree::EdgeDataPtr(flat),
314               TypedEq<const void*>(flat->Data()));
315   EXPECT_THAT(CordRepBtree::EdgeData(flat), Eq("Hello world"));
316 
317   EXPECT_TRUE(CordRepBtree::IsDataEdge(external));
318   EXPECT_THAT(CordRepBtree::EdgeDataPtr(external),
319               TypedEq<const void*>(external->base));
320   EXPECT_THAT(CordRepBtree::EdgeData(external), Eq("Hello external"));
321 
322   EXPECT_TRUE(CordRepBtree::IsDataEdge(substr1));
323   EXPECT_THAT(CordRepBtree::EdgeDataPtr(substr1),
324               TypedEq<const void*>(flat->Data() + 1));
325   EXPECT_THAT(CordRepBtree::EdgeData(substr1), Eq("ello w"));
326 
327   EXPECT_TRUE(CordRepBtree::IsDataEdge(substr2));
328   EXPECT_THAT(CordRepBtree::EdgeDataPtr(substr2),
329               TypedEq<const void*>(external->base + 1));
330   EXPECT_THAT(CordRepBtree::EdgeData(substr2), Eq("ello e"));
331 
332   EXPECT_FALSE(CordRepBtree::IsDataEdge(concat));
333   EXPECT_FALSE(CordRepBtree::IsDataEdge(bad_substr));
334 #if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
335   EXPECT_DEATH(CordRepBtree::EdgeData(concat), ".*");
336   EXPECT_DEATH(CordRepBtree::EdgeDataPtr(concat), ".*");
337   EXPECT_DEATH(CordRepBtree::EdgeData(bad_substr), ".*");
338   EXPECT_DEATH(CordRepBtree::EdgeDataPtr(bad_substr), ".*");
339 #endif
340 
341   CordRep::Unref(bad_substr);
342   CordRep::Unref(concat);
343   CordRep::Unref(substr2);
344   CordRep::Unref(substr1);
345   CordRep::Unref(external);
346   CordRep::Unref(flat);
347 }
348 
TEST(CordRepBtreeTest,CreateUnrefLeaf)349 TEST(CordRepBtreeTest, CreateUnrefLeaf) {
350   auto* flat = MakeFlat("a");
351   auto* leaf = CordRepBtree::Create(flat);
352   EXPECT_THAT(leaf->size(), Eq(1));
353   EXPECT_THAT(leaf->height(), Eq(0));
354   EXPECT_THAT(leaf->Edges(), ElementsAre(flat));
355   CordRepBtree::Unref(leaf);
356 }
357 
TEST(CordRepBtreeTest,NewUnrefNode)358 TEST(CordRepBtreeTest, NewUnrefNode) {
359   auto* leaf = CordRepBtree::Create(MakeFlat("a"));
360   CordRepBtree* tree = CordRepBtree::New(leaf);
361   EXPECT_THAT(tree->size(), Eq(1));
362   EXPECT_THAT(tree->height(), Eq(1));
363   EXPECT_THAT(tree->Edges(), ElementsAre(leaf));
364   CordRepBtree::Unref(tree);
365 }
366 
TEST_P(CordRepBtreeTest,AppendToLeafToCapacity)367 TEST_P(CordRepBtreeTest, AppendToLeafToCapacity) {
368   AutoUnref refs;
369   std::vector<CordRep*> flats;
370   flats.push_back(MakeHexFlat(0));
371   auto* leaf = CordRepBtree::Create(flats.back());
372 
373   for (size_t i = 1; i < CordRepBtree::kMaxCapacity; ++i) {
374     refs.RefIf(shared(), leaf);
375     flats.push_back(MakeHexFlat(i));
376     auto* result = CordRepBtree::Append(leaf, flats.back());
377     EXPECT_THAT(result->height(), Eq(0));
378     EXPECT_THAT(result, Conditional(shared(), Ne(leaf), Eq(leaf)));
379     EXPECT_THAT(result->Edges(), ElementsAreArray(flats));
380     leaf = result;
381   }
382   CordRep::Unref(leaf);
383 }
384 
TEST_P(CordRepBtreeTest,PrependToLeafToCapacity)385 TEST_P(CordRepBtreeTest, PrependToLeafToCapacity) {
386   AutoUnref refs;
387   std::deque<CordRep*> flats;
388   flats.push_front(MakeHexFlat(0));
389   auto* leaf = CordRepBtree::Create(flats.front());
390 
391   for (size_t i = 1; i < CordRepBtree::kMaxCapacity; ++i) {
392     refs.RefIf(shared(), leaf);
393     flats.push_front(MakeHexFlat(i));
394     auto* result = CordRepBtree::Prepend(leaf, flats.front());
395     EXPECT_THAT(result->height(), Eq(0));
396     EXPECT_THAT(result, Conditional(shared(), Ne(leaf), Eq(leaf)));
397     EXPECT_THAT(result->Edges(), ElementsAreArray(flats));
398     leaf = result;
399   }
400   CordRep::Unref(leaf);
401 }
402 
403 // This test specifically aims at code aligning data at either the front or the
404 // back of the contained `edges[]` array, alternating Append and Prepend will
405 // move `begin()` and `end()` values as needed for each added value.
TEST_P(CordRepBtreeTest,AppendPrependToLeafToCapacity)406 TEST_P(CordRepBtreeTest, AppendPrependToLeafToCapacity) {
407   AutoUnref refs;
408   std::deque<CordRep*> flats;
409   flats.push_front(MakeHexFlat(0));
410   auto* leaf = CordRepBtree::Create(flats.front());
411 
412   for (size_t i = 1; i < CordRepBtree::kMaxCapacity; ++i) {
413     refs.RefIf(shared(), leaf);
414     CordRepBtree* result;
415     if (i % 2 != 0) {
416       flats.push_front(MakeHexFlat(i));
417       result = CordRepBtree::Prepend(leaf, flats.front());
418     } else {
419       flats.push_back(MakeHexFlat(i));
420       result = CordRepBtree::Append(leaf, flats.back());
421     }
422     EXPECT_THAT(result->height(), Eq(0));
423     EXPECT_THAT(result, Conditional(shared(), Ne(leaf), Eq(leaf)));
424     EXPECT_THAT(result->Edges(), ElementsAreArray(flats));
425     leaf = result;
426   }
427   CordRep::Unref(leaf);
428 }
429 
TEST_P(CordRepBtreeTest,AppendToLeafBeyondCapacity)430 TEST_P(CordRepBtreeTest, AppendToLeafBeyondCapacity) {
431   AutoUnref refs;
432   auto* leaf = MakeLeaf();
433   refs.RefIf(shared(), leaf);
434   CordRep* flat = MakeFlat("abc");
435   auto* result = CordRepBtree::Append(leaf, flat);
436   ASSERT_THAT(result, IsNode(1));
437   EXPECT_THAT(result, Ne(leaf));
438   absl::Span<CordRep* const> edges = result->Edges();
439   ASSERT_THAT(edges, ElementsAre(leaf, IsNode(0)));
440   EXPECT_THAT(edges[1]->btree()->Edges(), ElementsAre(flat));
441   CordRep::Unref(result);
442 }
443 
TEST_P(CordRepBtreeTest,PrependToLeafBeyondCapacity)444 TEST_P(CordRepBtreeTest, PrependToLeafBeyondCapacity) {
445   AutoUnref refs;
446   auto* leaf = MakeLeaf();
447   refs.RefIf(shared(), leaf);
448   CordRep* flat = MakeFlat("abc");
449   auto* result = CordRepBtree::Prepend(leaf, flat);
450   ASSERT_THAT(result, IsNode(1));
451   EXPECT_THAT(result, Ne(leaf));
452   absl::Span<CordRep* const> edges = result->Edges();
453   ASSERT_THAT(edges, ElementsAre(IsNode(0), leaf));
454   EXPECT_THAT(edges[0]->btree()->Edges(), ElementsAre(flat));
455   CordRep::Unref(result);
456 }
457 
TEST_P(CordRepBtreeTest,AppendToTreeOneDeep)458 TEST_P(CordRepBtreeTest, AppendToTreeOneDeep) {
459   constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
460   AutoUnref refs;
461   std::vector<CordRep*> flats;
462   flats.push_back(MakeHexFlat(0));
463   CordRepBtree* tree = CordRepBtree::Create(flats.back());
464   for (size_t i = 1; i <= max_cap; ++i) {
465     flats.push_back(MakeHexFlat(i));
466     tree = CordRepBtree::Append(tree, flats.back());
467   }
468   ASSERT_THAT(tree, IsNode(1));
469 
470   for (size_t i = max_cap + 1; i < max_cap * max_cap; ++i) {
471     // Ref top level tree based on param.
472     // Ref leaf node once every 4 iterations, which should not have an
473     // observable effect other than that the leaf itself is copied.
474     refs.RefIf(shared(), tree);
475     refs.RefIf(i % 4 == 0, tree->Edges().back());
476 
477     flats.push_back(MakeHexFlat(i));
478     CordRepBtree* result = CordRepBtree::Append(tree, flats.back());
479     ASSERT_THAT(result, IsNode(1));
480     ASSERT_THAT(result, Conditional(shared(), Ne(tree), Eq(tree)));
481     std::vector<CordRep*> edges = GetLeafEdges(result);
482     ASSERT_THAT(edges, ElementsAreArray(flats));
483     tree = result;
484   }
485   CordRep::Unref(tree);
486 }
487 
TEST_P(CordRepBtreeTest,AppendToTreeTwoDeep)488 TEST_P(CordRepBtreeTest, AppendToTreeTwoDeep) {
489   constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
490   AutoUnref refs;
491   std::vector<CordRep*> flats;
492   flats.push_back(MakeHexFlat(0));
493   CordRepBtree* tree = CordRepBtree::Create(flats.back());
494   for (size_t i = 1; i <= max_cap * max_cap; ++i) {
495     flats.push_back(MakeHexFlat(i));
496     tree = CordRepBtree::Append(tree, flats.back());
497   }
498   ASSERT_THAT(tree, IsNode(2));
499   for (size_t i = max_cap * max_cap + 1; i < max_cap * max_cap * max_cap; ++i) {
500     // Ref top level tree based on param.
501     // Ref child node once every 16 iterations, and leaf node every 4
502     // iterrations which  which should not have an observable effect other than
503     //  the node and/or the leaf below it being copied.
504     refs.RefIf(shared(), tree);
505     refs.RefIf(i % 16 == 0, tree->Edges().back());
506     refs.RefIf(i % 4 == 0, tree->Edges().back()->btree()->Edges().back());
507 
508     flats.push_back(MakeHexFlat(i));
509     CordRepBtree* result = CordRepBtree::Append(tree, flats.back());
510     ASSERT_THAT(result, IsNode(2));
511     ASSERT_THAT(result, Conditional(shared(), Ne(tree), Eq(tree)));
512     std::vector<CordRep*> edges = GetLeafEdges(result);
513     ASSERT_THAT(edges, ElementsAreArray(flats));
514     tree = result;
515   }
516   CordRep::Unref(tree);
517 }
518 
TEST_P(CordRepBtreeTest,PrependToTreeOneDeep)519 TEST_P(CordRepBtreeTest, PrependToTreeOneDeep) {
520   constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
521   AutoUnref refs;
522   std::deque<CordRep*> flats;
523   flats.push_back(MakeHexFlat(0));
524   CordRepBtree* tree = CordRepBtree::Create(flats.back());
525   for (size_t i = 1; i <= max_cap; ++i) {
526     flats.push_front(MakeHexFlat(i));
527     tree = CordRepBtree::Prepend(tree, flats.front());
528   }
529   ASSERT_THAT(tree, IsNode(1));
530 
531   for (size_t i = max_cap + 1; i < max_cap * max_cap; ++i) {
532     // Ref top level tree based on param.
533     // Ref leaf node once every 4 iterations which should not have an observable
534     // effect other than than the leaf itself is copied.
535     refs.RefIf(shared(), tree);
536     refs.RefIf(i % 4 == 0, tree->Edges().back());
537 
538     flats.push_front(MakeHexFlat(i));
539     CordRepBtree* result = CordRepBtree::Prepend(tree, flats.front());
540     ASSERT_THAT(result, IsNode(1));
541     ASSERT_THAT(result, Conditional(shared(), Ne(tree), Eq(tree)));
542     std::vector<CordRep*> edges = GetLeafEdges(result);
543     ASSERT_THAT(edges, ElementsAreArray(flats));
544     tree = result;
545   }
546   CordRep::Unref(tree);
547 }
548 
TEST_P(CordRepBtreeTest,PrependToTreeTwoDeep)549 TEST_P(CordRepBtreeTest, PrependToTreeTwoDeep) {
550   constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
551   AutoUnref refs;
552   std::deque<CordRep*> flats;
553   flats.push_back(MakeHexFlat(0));
554   CordRepBtree* tree = CordRepBtree::Create(flats.back());
555   for (size_t i = 1; i <= max_cap * max_cap; ++i) {
556     flats.push_front(MakeHexFlat(i));
557     tree = CordRepBtree::Prepend(tree, flats.front());
558   }
559   ASSERT_THAT(tree, IsNode(2));
560   for (size_t i = max_cap * max_cap + 1; i < max_cap * max_cap * max_cap; ++i) {
561     // Ref top level tree based on param.
562     // Ref child node once every 16 iterations, and leaf node every 4
563     // iterrations which  which should not have an observable effect other than
564     //  the node and/or the leaf below it being copied.
565     refs.RefIf(shared(), tree);
566     refs.RefIf(i % 16 == 0, tree->Edges().back());
567     refs.RefIf(i % 4 == 0, tree->Edges().back()->btree()->Edges().back());
568 
569     flats.push_front(MakeHexFlat(i));
570     CordRepBtree* result = CordRepBtree::Prepend(tree, flats.front());
571     ASSERT_THAT(result, IsNode(2));
572     ASSERT_THAT(result, Conditional(shared(), Ne(tree), Eq(tree)));
573     std::vector<CordRep*> edges = GetLeafEdges(result);
574     ASSERT_THAT(edges, ElementsAreArray(flats));
575     tree = result;
576   }
577   CordRep::Unref(tree);
578 }
579 
TEST_P(CordRepBtreeDualTest,MergeLeafsNotExceedingCapacity)580 TEST_P(CordRepBtreeDualTest, MergeLeafsNotExceedingCapacity) {
581   for (bool use_append : {false, true}) {
582     SCOPED_TRACE(use_append ? "Using Append" : "Using Prepend");
583 
584     AutoUnref refs;
585     std::vector<CordRep*> flats;
586 
587     // Build `left` side leaf appending all contained flats to `flats`
588     CordRepBtree* left = MakeLeaf(3);
589     GetLeafEdges(left, flats);
590     refs.RefIf(first_shared(), left);
591 
592     // Build `right` side leaf appending all contained flats to `flats`
593     CordRepBtree* right = MakeLeaf(2);
594     GetLeafEdges(right, flats);
595     refs.RefIf(second_shared(), right);
596 
597     CordRepBtree* tree = use_append ? CordRepBtree::Append(left, right)
598                                     : CordRepBtree::Prepend(right, left);
599     EXPECT_THAT(tree, IsNode(0));
600 
601     // `tree` contains all flats originally belonging to `left` and `right`.
602     EXPECT_THAT(tree->Edges(), ElementsAreArray(flats));
603     CordRepBtree::Unref(tree);
604   }
605 }
606 
TEST_P(CordRepBtreeDualTest,MergeLeafsExceedingCapacity)607 TEST_P(CordRepBtreeDualTest, MergeLeafsExceedingCapacity) {
608   for (bool use_append : {false, true}) {
609     SCOPED_TRACE(use_append ? "Using Append" : "Using Prepend");
610 
611     AutoUnref refs;
612 
613     // Build `left` side tree appending all contained flats to `flats`
614     CordRepBtree* left = MakeLeaf(CordRepBtree::kMaxCapacity - 2);
615     refs.RefIf(first_shared(), left);
616 
617     // Build `right` side tree appending all contained flats to `flats`
618     CordRepBtree* right = MakeLeaf(CordRepBtree::kMaxCapacity - 1);
619     refs.RefIf(second_shared(), right);
620 
621     CordRepBtree* tree = use_append ? CordRepBtree::Append(left, right)
622                                     : CordRepBtree::Prepend(right, left);
623     EXPECT_THAT(tree, IsNode(1));
624     EXPECT_THAT(tree->Edges(), ElementsAre(left, right));
625     CordRepBtree::Unref(tree);
626   }
627 }
628 
TEST_P(CordRepBtreeDualTest,MergeEqualHeightTrees)629 TEST_P(CordRepBtreeDualTest, MergeEqualHeightTrees) {
630   for (bool use_append : {false, true}) {
631     SCOPED_TRACE(use_append ? "Using Append" : "Using Prepend");
632 
633     AutoUnref refs;
634     std::vector<CordRep*> flats;
635 
636     // Build `left` side tree appending all contained flats to `flats`
637     CordRepBtree* left = MakeTree(CordRepBtree::kMaxCapacity * 3);
638     GetLeafEdges(left, flats);
639     refs.RefIf(first_shared(), left);
640 
641     // Build `right` side tree appending all contained flats to `flats`
642     CordRepBtree* right = MakeTree(CordRepBtree::kMaxCapacity * 2);
643     GetLeafEdges(right, flats);
644     refs.RefIf(second_shared(), right);
645 
646     CordRepBtree* tree = use_append ? CordRepBtree::Append(left, right)
647                                     : CordRepBtree::Prepend(right, left);
648     EXPECT_THAT(tree, IsNode(1));
649     EXPECT_THAT(tree->Edges(), SizeIs(5));
650 
651     // `tree` contains all flats originally belonging to `left` and `right`.
652     EXPECT_THAT(GetLeafEdges(tree), ElementsAreArray(flats));
653     CordRepBtree::Unref(tree);
654   }
655 }
656 
TEST_P(CordRepBtreeDualTest,MergeLeafWithTreeNotExceedingLeafCapacity)657 TEST_P(CordRepBtreeDualTest, MergeLeafWithTreeNotExceedingLeafCapacity) {
658   for (bool use_append : {false, true}) {
659     SCOPED_TRACE(use_append ? "Using Append" : "Using Prepend");
660 
661     AutoUnref refs;
662     std::vector<CordRep*> flats;
663 
664     // Build `left` side tree appending all added flats to `flats`
665     CordRepBtree* left = MakeTree(CordRepBtree::kMaxCapacity * 2 + 2);
666     GetLeafEdges(left, flats);
667     refs.RefIf(first_shared(), left);
668 
669     // Build `right` side tree appending all added flats to `flats`
670     CordRepBtree* right = MakeTree(3);
671     GetLeafEdges(right, flats);
672     refs.RefIf(second_shared(), right);
673 
674     CordRepBtree* tree = use_append ? CordRepBtree::Append(left, right)
675                                     : CordRepBtree::Prepend(right, left);
676     EXPECT_THAT(tree, IsNode(1));
677     EXPECT_THAT(tree->Edges(), SizeIs(3));
678 
679     // `tree` contains all flats originally belonging to `left` and `right`.
680     EXPECT_THAT(GetLeafEdges(tree), ElementsAreArray(flats));
681     CordRepBtree::Unref(tree);
682   }
683 }
684 
TEST_P(CordRepBtreeDualTest,MergeLeafWithTreeExceedingLeafCapacity)685 TEST_P(CordRepBtreeDualTest, MergeLeafWithTreeExceedingLeafCapacity) {
686   for (bool use_append : {false, true}) {
687     SCOPED_TRACE(use_append ? "Using Append" : "Using Prepend");
688 
689     AutoUnref refs;
690     std::vector<CordRep*> flats;
691 
692     // Build `left` side tree appending all added flats to `flats`
693     CordRepBtree* left = MakeTree(CordRepBtree::kMaxCapacity * 3 - 2);
694     GetLeafEdges(left, flats);
695     refs.RefIf(first_shared(), left);
696 
697     // Build `right` side tree appending all added flats to `flats`
698     CordRepBtree* right = MakeTree(3);
699     GetLeafEdges(right, flats);
700     refs.RefIf(second_shared(), right);
701 
702     CordRepBtree* tree = use_append ? CordRepBtree::Append(left, right)
703                                     : CordRepBtree::Prepend(right, left);
704     EXPECT_THAT(tree, IsNode(1));
705     EXPECT_THAT(tree->Edges(), SizeIs(4));
706 
707     // `tree` contains all flats originally belonging to `left` and `right`.
708     EXPECT_THAT(GetLeafEdges(tree), ElementsAreArray(flats));
709     CordRepBtree::Unref(tree);
710   }
711 }
712 
RefEdgesAt(size_t depth,AutoUnref & refs,CordRepBtree * tree)713 void RefEdgesAt(size_t depth, AutoUnref& refs, CordRepBtree* tree) {
714   absl::Span<CordRep* const> edges = tree->Edges();
715   if (depth == 0) {
716     refs.Ref(edges.front());
717     refs.Ref(edges.back());
718   } else {
719     assert(tree->height() > 0);
720     RefEdgesAt(depth - 1, refs, edges.front()->btree());
721     RefEdgesAt(depth - 1, refs, edges.back()->btree());
722   }
723 }
724 
TEST(CordRepBtreeTest,MergeFuzzTest)725 TEST(CordRepBtreeTest, MergeFuzzTest) {
726   constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
727   std::minstd_rand rnd;
728   std::uniform_int_distribution<int> coin_flip(0, 1);
729   std::uniform_int_distribution<int> dice_throw(1, 6);
730 
731   auto random_leaf_count = [&]() {
732     std::uniform_int_distribution<int> dist_height(0, 3);
733     std::uniform_int_distribution<int> dist_leaf(0, max_cap - 1);
734     const size_t height = dist_height(rnd);
735     return (height ? pow(max_cap, height) : 0) + dist_leaf(rnd);
736   };
737 
738   for (int i = 0; i < 10000; ++i) {
739     AutoUnref refs;
740     std::vector<CordRep*> flats;
741 
742     CordRepBtree* left = MakeTree(random_leaf_count(), coin_flip(rnd));
743     GetLeafEdges(left, flats);
744     if (dice_throw(rnd) == 1) {
745       std::uniform_int_distribution<int> dist(0, left->height());
746       RefEdgesAt(dist(rnd), refs, left);
747     }
748 
749     CordRepBtree* right = MakeTree(random_leaf_count(), coin_flip(rnd));
750     GetLeafEdges(right, flats);
751     if (dice_throw(rnd) == 1) {
752       std::uniform_int_distribution<int> dist(0, right->height());
753       RefEdgesAt(dist(rnd), refs, right);
754     }
755 
756     CordRepBtree* tree = CordRepBtree::Append(left, right);
757     EXPECT_THAT(GetLeafEdges(tree), ElementsAreArray(flats));
758     CordRepBtree::Unref(tree);
759   }
760 }
761 
TEST(CordRepBtreeTest,SubTree)762 TEST(CordRepBtreeTest, SubTree) {
763   // Create tree of at least 2 levels high
764   constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
765   const size_t n = max_cap * max_cap * 2;
766   const std::string data = CreateRandomString(n * 3);
767   std::vector<CordRep*> flats;
768   for (absl::string_view s = data; !s.empty(); s.remove_prefix(3)) {
769     flats.push_back(MakeFlat(s.substr(0, 3)));
770   }
771   CordRepBtree* node = CordRepBtree::Create(CordRep::Ref(flats[0]));
772   for (size_t i = 1; i < flats.size(); ++i) {
773     node = CordRepBtree::Append(node, CordRep::Ref(flats[i]));
774   }
775 
776   for (int offset = 0; offset < data.length(); ++offset) {
777     for (int length = 1; length <= data.length() - offset; ++length) {
778       CordRep* rep = node->SubTree(offset, length);
779       EXPECT_THAT(CordToString(rep), Eq(data.substr(offset, length)));
780       CordRep::Unref(rep);
781     }
782   }
783   CordRepBtree::Unref(node);
784   for (CordRep* rep : flats) {
785     CordRep::Unref(rep);
786   }
787 }
788 
TEST(CordRepBtreeTest,SubTreeOnExistingSubstring)789 TEST(CordRepBtreeTest, SubTreeOnExistingSubstring) {
790   // This test verifies that a SubTree call on a pre-existing (large) substring
791   // adjusts the existing substring if not shared, and else rewrites the
792   // existing substring.
793   AutoUnref refs;
794   std::string data = CreateRandomString(1000);
795   CordRepBtree* leaf = CordRepBtree::Create(MakeFlat("abc"));
796   CordRep* flat = MakeFlat(data);
797   leaf = CordRepBtree::Append(leaf, flat);
798 
799   // Setup tree containing substring.
800   CordRep* result = leaf->SubTree(0, 3 + 990);
801   ASSERT_THAT(result->tag, Eq(BTREE));
802   CordRep::Unref(leaf);
803   leaf = result->btree();
804   ASSERT_THAT(leaf->Edges(), ElementsAre(_, IsSubstring(0, 990)));
805   EXPECT_THAT(leaf->Edges()[1]->substring()->child, Eq(flat));
806 
807   // Verify substring of substring.
808   result = leaf->SubTree(3 + 5, 970);
809   ASSERT_THAT(result, IsSubstring(5, 970));
810   EXPECT_THAT(result->substring()->child, Eq(flat));
811   CordRep::Unref(result);
812 
813   CordRep::Unref(leaf);
814 }
815 
TEST_P(CordRepBtreeTest,AddDataToLeaf)816 TEST_P(CordRepBtreeTest, AddDataToLeaf) {
817   const size_t n = CordRepBtree::kMaxCapacity;
818   const std::string data = CreateRandomString(n * 3);
819 
820   for (bool append : {true, false}) {
821     AutoUnref refs;
822     DataConsumer consumer(data, append);
823     SCOPED_TRACE(append ? "Append" : "Prepend");
824 
825     CordRepBtree* leaf = CordRepBtree::Create(MakeFlat(consumer.Next(3)));
826     for (size_t i = 1; i < n; ++i) {
827       refs.RefIf(shared(), leaf);
828       CordRepBtree* result = BtreeAdd(leaf, append, consumer.Next(3));
829       EXPECT_THAT(result, Conditional(shared(), Ne(leaf), Eq(leaf)));
830       EXPECT_THAT(CordToString(result), Eq(consumer.Consumed()));
831       leaf = result;
832     }
833     CordRep::Unref(leaf);
834   }
835 }
836 
TEST_P(CordRepBtreeTest,AppendDataToTree)837 TEST_P(CordRepBtreeTest, AppendDataToTree) {
838   AutoUnref refs;
839   size_t n = CordRepBtree::kMaxCapacity + CordRepBtree::kMaxCapacity / 2;
840   std::string data = CreateRandomString(n * 3);
841   CordRepBtree* tree = refs.RefIf(shared(), CreateTree(data, 3));
842   CordRepBtree* leaf0 = tree->Edges()[0]->btree();
843   CordRepBtree* leaf1 = tree->Edges()[1]->btree();
844   CordRepBtree* result = CordRepBtree::Append(tree, "123456789");
845   EXPECT_THAT(result, Conditional(shared(), Ne(tree), Eq(tree)));
846   EXPECT_THAT(result->Edges(),
847               ElementsAre(leaf0, Conditional(shared(), Ne(leaf1), Eq(leaf1))));
848   EXPECT_THAT(CordToString(result), Eq(data + "123456789"));
849   CordRep::Unref(result);
850 }
851 
TEST_P(CordRepBtreeTest,PrependDataToTree)852 TEST_P(CordRepBtreeTest, PrependDataToTree) {
853   AutoUnref refs;
854   size_t n = CordRepBtree::kMaxCapacity + CordRepBtree::kMaxCapacity / 2;
855   std::string data = CreateRandomString(n * 3);
856   CordRepBtree* tree = refs.RefIf(shared(), CreateTreeReverse(data, 3));
857   CordRepBtree* leaf0 = tree->Edges()[0]->btree();
858   CordRepBtree* leaf1 = tree->Edges()[1]->btree();
859   CordRepBtree* result = CordRepBtree::Prepend(tree, "123456789");
860   EXPECT_THAT(result, Conditional(shared(), Ne(tree), Eq(tree)));
861   EXPECT_THAT(result->Edges(),
862               ElementsAre(Conditional(shared(), Ne(leaf0), Eq(leaf0)), leaf1));
863   EXPECT_THAT(CordToString(result), Eq("123456789" + data));
864   CordRep::Unref(result);
865 }
866 
TEST_P(CordRepBtreeTest,AddDataToTreeThreeLevelsDeep)867 TEST_P(CordRepBtreeTest, AddDataToTreeThreeLevelsDeep) {
868   constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
869   const size_t n = max_cap * max_cap * max_cap;
870   const std::string data = CreateRandomString(n * 3);
871 
872   for (bool append : {true, false}) {
873     AutoUnref refs;
874     DataConsumer consumer(data, append);
875     SCOPED_TRACE(append ? "Append" : "Prepend");
876 
877     // Fill leaf
878     CordRepBtree* tree = CordRepBtree::Create(MakeFlat(consumer.Next(3)));
879     for (size_t i = 1; i < max_cap; ++i) {
880       tree = BtreeAdd(tree, append, consumer.Next(3));
881     }
882     ASSERT_THAT(CordToString(tree), Eq(consumer.Consumed()));
883 
884     // Fill to maximum at one deep
885     refs.RefIf(shared(), tree);
886     CordRepBtree* result = BtreeAdd(tree, append, consumer.Next(3));
887     ASSERT_THAT(result, IsNode(1));
888     ASSERT_THAT(result, Ne(tree));
889     ASSERT_THAT(CordToString(result), Eq(consumer.Consumed()));
890     tree = result;
891     for (size_t i = max_cap + 1; i < max_cap * max_cap; ++i) {
892       refs.RefIf(shared(), tree);
893       result = BtreeAdd(tree, append, consumer.Next(3));
894       ASSERT_THAT(result, Conditional(shared(), Ne(tree), Eq(tree)));
895       ASSERT_THAT(CordToString(result), Eq(consumer.Consumed()));
896       tree = result;
897     }
898 
899     // Fill to maximum at two deep
900     refs.RefIf(shared(), tree);
901     result = BtreeAdd(tree, append, consumer.Next(3));
902     ASSERT_THAT(result, IsNode(2));
903     ASSERT_THAT(result, Ne(tree));
904     ASSERT_THAT(CordToString(result), Eq(consumer.Consumed()));
905     tree = result;
906     for (size_t i = max_cap * max_cap + 1; i < max_cap * max_cap * max_cap;
907          ++i) {
908       refs.RefIf(shared(), tree);
909       result = BtreeAdd(tree, append, consumer.Next(3));
910       ASSERT_THAT(result, Conditional(shared(), Ne(tree), Eq(tree)));
911       ASSERT_THAT(CordToString(result), Eq(consumer.Consumed()));
912       tree = result;
913     }
914 
915     CordRep::Unref(tree);
916   }
917 }
918 
TEST_P(CordRepBtreeTest,AddLargeDataToLeaf)919 TEST_P(CordRepBtreeTest, AddLargeDataToLeaf) {
920   const size_t max_cap = CordRepBtree::kMaxCapacity;
921   const size_t n = max_cap * max_cap * max_cap * 3 + 2;
922   const std::string data = CreateRandomString(n * kMaxFlatLength);
923 
924   for (bool append : {true, false}) {
925     AutoUnref refs;
926     SCOPED_TRACE(append ? "Append" : "Prepend");
927 
928     CordRepBtree* leaf = CordRepBtree::Create(MakeFlat("abc"));
929     refs.RefIf(shared(), leaf);
930     CordRepBtree* result = BtreeAdd(leaf, append, data);
931     EXPECT_THAT(CordToString(result), Eq(append ? "abc" + data : data + "abc"));
932     CordRep::Unref(result);
933   }
934 }
935 
TEST_P(CordRepBtreeDualTest,CreateFromConcat)936 TEST_P(CordRepBtreeDualTest, CreateFromConcat) {
937   AutoUnref refs;
938   CordRep* flats[] = {MakeFlat("abcdefgh"), MakeFlat("ijklm"),
939                       MakeFlat("nopqrstuv"), MakeFlat("wxyz")};
940   auto* left = MakeConcat(flats[0], flats[1]);
941   auto* right = MakeConcat(flats[2], refs.RefIf(first_shared(), flats[3]));
942   auto* concat = refs.RefIf(second_shared(), MakeConcat(left, right));
943   CordRepBtree* result = CordRepBtree::Create(concat);
944   ASSERT_TRUE(CordRepBtree::IsValid(result));
945   EXPECT_THAT(result->length, Eq(26));
946   EXPECT_THAT(CordToString(result), Eq("abcdefghijklmnopqrstuvwxyz"));
947   CordRep::Unref(result);
948 }
949 
TEST_P(CordRepBtreeDualTest,AppendConcat)950 TEST_P(CordRepBtreeDualTest, AppendConcat) {
951   AutoUnref refs;
952   CordRep* flats[] = {MakeFlat("defgh"), MakeFlat("ijklm"),
953                       MakeFlat("nopqrstuv"), MakeFlat("wxyz")};
954   auto* left = MakeConcat(flats[0], flats[1]);
955   auto* right = MakeConcat(flats[2], refs.RefIf(first_shared(), flats[3]));
956   auto* concat = refs.RefIf(second_shared(), MakeConcat(left, right));
957   CordRepBtree* result = CordRepBtree::Create(MakeFlat("abc"));
958   result = CordRepBtree::Append(result, concat);
959   ASSERT_TRUE(CordRepBtree::IsValid(result));
960   EXPECT_THAT(result->length, Eq(26));
961   EXPECT_THAT(CordToString(result), Eq("abcdefghijklmnopqrstuvwxyz"));
962   CordRep::Unref(result);
963 }
964 
TEST_P(CordRepBtreeDualTest,PrependConcat)965 TEST_P(CordRepBtreeDualTest, PrependConcat) {
966   AutoUnref refs;
967   CordRep* flats[] = {MakeFlat("abcdefgh"), MakeFlat("ijklm"),
968                       MakeFlat("nopqrstuv"), MakeFlat("wx")};
969   auto* left = MakeConcat(flats[0], flats[1]);
970   auto* right = MakeConcat(flats[2], refs.RefIf(first_shared(), flats[3]));
971   auto* concat = refs.RefIf(second_shared(), MakeConcat(left, right));
972   CordRepBtree* result = CordRepBtree::Create(MakeFlat("yz"));
973   result = CordRepBtree::Prepend(result, concat);
974   ASSERT_TRUE(CordRepBtree::IsValid(result));
975   EXPECT_THAT(result->length, Eq(26));
976   EXPECT_THAT(CordToString(result), Eq("abcdefghijklmnopqrstuvwxyz"));
977   CordRep::Unref(result);
978 }
979 
TEST_P(CordRepBtreeTest,CreateFromTreeReturnsTree)980 TEST_P(CordRepBtreeTest, CreateFromTreeReturnsTree) {
981   AutoUnref refs;
982   CordRepBtree* leaf = CordRepBtree::Create(MakeFlat("Hello world"));
983   refs.RefIf(shared(), leaf);
984   CordRepBtree* result = CordRepBtree::Create(leaf);
985   EXPECT_THAT(result, Eq(leaf));
986   CordRep::Unref(result);
987 }
988 
TEST_P(CordRepBtreeTest,ExceedMaxHeight)989 TEST_P(CordRepBtreeTest, ExceedMaxHeight) {
990   AutoUnref refs;
991   CordRepBtree* tree = MakeLeaf();
992   for (int h = 1; h <= CordRepBtree::kMaxHeight; ++h) {
993     CordRepBtree* newtree = CordRepBtree::New(tree);
994     for (size_t i = 1; i < CordRepBtree::kMaxCapacity; ++i) {
995       newtree = CordRepBtree::Append(newtree, CordRep::Ref(tree));
996     }
997     tree = newtree;
998   }
999   refs.RefIf(shared(), tree);
1000 #if defined(GTEST_HAS_DEATH_TEST)
1001   EXPECT_DEATH(tree = CordRepBtree::Append(tree, MakeFlat("Boom")), ".*");
1002 #endif
1003   CordRep::Unref(tree);
1004 }
1005 
TEST(CordRepBtreeTest,GetCharacter)1006 TEST(CordRepBtreeTest, GetCharacter) {
1007   size_t n = CordRepBtree::kMaxCapacity * CordRepBtree::kMaxCapacity + 2;
1008   std::string data = CreateRandomString(n * 3);
1009   CordRepBtree* tree = CreateTree(data, 3);
1010   // Add a substring node for good measure.
1011   tree = tree->Append(tree, MakeSubstring(4, 5, MakeFlat("abcdefghijklm")));
1012   data += "efghi";
1013   for (size_t i = 0; i < data.length(); ++i) {
1014     ASSERT_THAT(tree->GetCharacter(i), Eq(data[i]));
1015   }
1016   CordRep::Unref(tree);
1017 }
1018 
TEST_P(CordRepBtreeTest,IsFlatSingleFlat)1019 TEST_P(CordRepBtreeTest, IsFlatSingleFlat) {
1020   CordRepBtree* leaf = CordRepBtree::Create(MakeFlat("Hello world"));
1021 
1022   absl::string_view fragment;
1023   EXPECT_TRUE(leaf->IsFlat(nullptr));
1024   EXPECT_TRUE(leaf->IsFlat(&fragment));
1025   EXPECT_THAT(fragment, Eq("Hello world"));
1026   fragment = "";
1027   EXPECT_TRUE(leaf->IsFlat(0, 11, nullptr));
1028   EXPECT_TRUE(leaf->IsFlat(0, 11, &fragment));
1029   EXPECT_THAT(fragment, Eq("Hello world"));
1030 
1031   // Arbitrary ranges must check true as well.
1032   EXPECT_TRUE(leaf->IsFlat(1, 4, &fragment));
1033   EXPECT_THAT(fragment, Eq("ello"));
1034   EXPECT_TRUE(leaf->IsFlat(6, 5, &fragment));
1035   EXPECT_THAT(fragment, Eq("world"));
1036 
1037   CordRep::Unref(leaf);
1038 }
1039 
TEST(CordRepBtreeTest,IsFlatMultiFlat)1040 TEST(CordRepBtreeTest, IsFlatMultiFlat) {
1041   size_t n = CordRepBtree::kMaxCapacity * CordRepBtree::kMaxCapacity + 2;
1042   std::string data = CreateRandomString(n * 3);
1043   CordRepBtree* tree = CreateTree(data, 3);
1044   // Add substring nodes for good measure.
1045   tree = tree->Append(tree, MakeSubstring(4, 3, MakeFlat("abcdefghijklm")));
1046   tree = tree->Append(tree, MakeSubstring(8, 3, MakeFlat("abcdefghijklm")));
1047   data += "efgijk";
1048 
1049   EXPECT_FALSE(tree->IsFlat(nullptr));
1050   absl::string_view fragment = "Can't touch this";
1051   EXPECT_FALSE(tree->IsFlat(&fragment));
1052   EXPECT_THAT(fragment, Eq("Can't touch this"));
1053 
1054   for (size_t offset = 0; offset < data.size(); offset += 3) {
1055     EXPECT_TRUE(tree->IsFlat(offset, 3, nullptr));
1056     EXPECT_TRUE(tree->IsFlat(offset, 3, &fragment));
1057     EXPECT_THAT(fragment, Eq(data.substr(offset, 3)));
1058 
1059     fragment = "Can't touch this";
1060     if (offset > 0) {
1061       EXPECT_FALSE(tree->IsFlat(offset - 1, 4, nullptr));
1062       EXPECT_FALSE(tree->IsFlat(offset - 1, 4, &fragment));
1063       EXPECT_THAT(fragment, Eq("Can't touch this"));
1064     }
1065     if (offset < data.size() - 4) {
1066       EXPECT_FALSE(tree->IsFlat(offset, 4, nullptr));
1067       EXPECT_FALSE(tree->IsFlat(offset, 4, &fragment));
1068       EXPECT_THAT(fragment, Eq("Can't touch this"));
1069     }
1070   }
1071 
1072   CordRep::Unref(tree);
1073 }
1074 
1075 #if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
1076 
TEST_P(CordRepBtreeHeightTest,GetAppendBufferNotPrivate)1077 TEST_P(CordRepBtreeHeightTest, GetAppendBufferNotPrivate) {
1078   CordRepBtree* tree = CordRepBtree::Create(MakeExternal("Foo"));
1079   CordRepBtree::Ref(tree);
1080   EXPECT_DEATH(tree->GetAppendBuffer(1), ".*");
1081   CordRepBtree::Unref(tree);
1082   CordRepBtree::Unref(tree);
1083 }
1084 
1085 #endif  // defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
1086 
TEST_P(CordRepBtreeHeightTest,GetAppendBufferNotFlat)1087 TEST_P(CordRepBtreeHeightTest, GetAppendBufferNotFlat) {
1088   CordRepBtree* tree = CordRepBtree::Create(MakeExternal("Foo"));
1089   for (int i = 1; i <= height(); ++i) {
1090     tree = CordRepBtree::New(tree);
1091   }
1092   EXPECT_THAT(tree->GetAppendBuffer(1), SizeIs(0));
1093   CordRepBtree::Unref(tree);
1094 }
1095 
TEST_P(CordRepBtreeHeightTest,GetAppendBufferFlatNotPrivate)1096 TEST_P(CordRepBtreeHeightTest, GetAppendBufferFlatNotPrivate) {
1097   CordRepFlat* flat = MakeFlat("abc");
1098   CordRepBtree* tree = CordRepBtree::Create(CordRep::Ref(flat));
1099   for (int i = 1; i <= height(); ++i) {
1100     tree = CordRepBtree::New(tree);
1101   }
1102   EXPECT_THAT(tree->GetAppendBuffer(1), SizeIs(0));
1103   CordRepBtree::Unref(tree);
1104   CordRep::Unref(flat);
1105 }
1106 
TEST_P(CordRepBtreeHeightTest,GetAppendBufferTreeNotPrivate)1107 TEST_P(CordRepBtreeHeightTest, GetAppendBufferTreeNotPrivate) {
1108   if (height() == 0) return;
1109   AutoUnref refs;
1110   CordRepFlat* flat = MakeFlat("abc");
1111   CordRepBtree* tree = CordRepBtree::Create(CordRep::Ref(flat));
1112   for (int i = 1; i <= height(); ++i) {
1113     if (i == (height() + 1) / 2) refs.Ref(tree);
1114     tree = CordRepBtree::New(tree);
1115   }
1116   EXPECT_THAT(tree->GetAppendBuffer(1), SizeIs(0));
1117   CordRepBtree::Unref(tree);
1118   CordRep::Unref(flat);
1119 }
1120 
TEST_P(CordRepBtreeHeightTest,GetAppendBufferFlatNoCapacity)1121 TEST_P(CordRepBtreeHeightTest, GetAppendBufferFlatNoCapacity) {
1122   CordRepFlat* flat = MakeFlat("abc");
1123   flat->length = flat->Capacity();
1124   CordRepBtree* tree = CordRepBtree::Create(flat);
1125   for (int i = 1; i <= height(); ++i) {
1126     tree = CordRepBtree::New(tree);
1127   }
1128   EXPECT_THAT(tree->GetAppendBuffer(1), SizeIs(0));
1129   CordRepBtree::Unref(tree);
1130 }
1131 
TEST_P(CordRepBtreeHeightTest,GetAppendBufferFlatWithCapacity)1132 TEST_P(CordRepBtreeHeightTest, GetAppendBufferFlatWithCapacity) {
1133   CordRepFlat* flat = MakeFlat("abc");
1134   CordRepBtree* tree = CordRepBtree::Create(flat);
1135   for (int i = 1; i <= height(); ++i) {
1136     tree = CordRepBtree::New(tree);
1137   }
1138   absl::Span<char> span = tree->GetAppendBuffer(2);
1139   EXPECT_THAT(span, SizeIs(2));
1140   EXPECT_THAT(span.data(), TypedEq<void*>(flat->Data() + 3));
1141   EXPECT_THAT(tree->length, Eq(5));
1142 
1143   size_t avail = flat->Capacity() - 5;
1144   span = tree->GetAppendBuffer(avail + 100);
1145   EXPECT_THAT(span, SizeIs(avail));
1146   EXPECT_THAT(span.data(), TypedEq<void*>(flat->Data() + 5));
1147   EXPECT_THAT(tree->length, Eq(5 + avail));
1148 
1149   CordRepBtree::Unref(tree);
1150 }
1151 
TEST(CordRepBtreeTest,Dump)1152 TEST(CordRepBtreeTest, Dump) {
1153   // Handles nullptr
1154   std::stringstream ss;
1155   CordRepBtree::Dump(nullptr, ss);
1156   CordRepBtree::Dump(nullptr, "Once upon a label", ss);
1157   CordRepBtree::Dump(nullptr, "Once upon a label", false, ss);
1158   CordRepBtree::Dump(nullptr, "Once upon a label", true, ss);
1159 
1160   // Cover legal edges
1161   CordRepFlat* flat = MakeFlat("Hello world");
1162   CordRepExternal* external = MakeExternal("Hello external");
1163   CordRep* substr_flat = MakeSubstring(1, 6, CordRep::Ref(flat));
1164   CordRep* substr_external = MakeSubstring(2, 7, CordRep::Ref(external));
1165 
1166   // Build tree
1167   CordRepBtree* tree = CordRepBtree::Create(flat);
1168   tree = CordRepBtree::Append(tree, external);
1169   tree = CordRepBtree::Append(tree, substr_flat);
1170   tree = CordRepBtree::Append(tree, substr_external);
1171 
1172   // Repeat until we have a tree
1173   while (tree->height() == 0) {
1174     tree = CordRepBtree::Append(tree, CordRep::Ref(flat));
1175     tree = CordRepBtree::Append(tree, CordRep::Ref(external));
1176     tree = CordRepBtree::Append(tree, CordRep::Ref(substr_flat));
1177     tree = CordRepBtree::Append(tree, CordRep::Ref(substr_external));
1178   }
1179 
1180   for (int api = 0; api <= 3; ++api) {
1181     absl::string_view api_scope;
1182     std::stringstream ss;
1183     switch (api) {
1184       case 0:
1185         api_scope = "Bare";
1186         CordRepBtree::Dump(tree, ss);
1187         break;
1188       case 1:
1189         api_scope = "Label only";
1190         CordRepBtree::Dump(tree, "Once upon a label", ss);
1191         break;
1192       case 2:
1193         api_scope = "Label no content";
1194         CordRepBtree::Dump(tree, "Once upon a label", false, ss);
1195         break;
1196       default:
1197         api_scope = "Label and content";
1198         CordRepBtree::Dump(tree, "Once upon a label", true, ss);
1199         break;
1200     }
1201     SCOPED_TRACE(api_scope);
1202     std::string str = ss.str();
1203 
1204     // Contains Node(depth) / Leaf and private / shared indicators
1205     EXPECT_THAT(str, AllOf(HasSubstr("Node(1)"), HasSubstr("Leaf"),
1206                            HasSubstr("Private"), HasSubstr("Shared")));
1207 
1208     // Contains length and start offset of all data edges
1209     EXPECT_THAT(str, AllOf(HasSubstr("len = 11"), HasSubstr("len = 14"),
1210                            HasSubstr("len = 6"), HasSubstr("len = 7"),
1211                            HasSubstr("start = 1"), HasSubstr("start = 2")));
1212 
1213     // Contains address of all data edges
1214     EXPECT_THAT(
1215         str, AllOf(HasSubstr(absl::StrCat("0x", absl::Hex(flat))),
1216                    HasSubstr(absl::StrCat("0x", absl::Hex(external))),
1217                    HasSubstr(absl::StrCat("0x", absl::Hex(substr_flat))),
1218                    HasSubstr(absl::StrCat("0x", absl::Hex(substr_external)))));
1219 
1220     if (api != 0) {
1221       // Contains label
1222       EXPECT_THAT(str, HasSubstr("Once upon a label"));
1223     }
1224 
1225     if (api != 3) {
1226       // Does not contain contents
1227       EXPECT_THAT(str, Not(AnyOf((HasSubstr("data = \"Hello world\""),
1228                                   HasSubstr("data = \"Hello external\""),
1229                                   HasSubstr("data = \"ello w\""),
1230                                   HasSubstr("data = \"llo ext\"")))));
1231     } else {
1232       // Contains contents
1233       EXPECT_THAT(str, AllOf((HasSubstr("data = \"Hello world\""),
1234                               HasSubstr("data = \"Hello external\""),
1235                               HasSubstr("data = \"ello w\""),
1236                               HasSubstr("data = \"llo ext\""))));
1237     }
1238   }
1239 
1240   CordRep::Unref(tree);
1241 }
1242 
TEST(CordRepBtreeTest,IsValid)1243 TEST(CordRepBtreeTest, IsValid) {
1244   EXPECT_FALSE(CordRepBtree::IsValid(nullptr));
1245 
1246   CordRepBtree* empty = CordRepBtree::New(0);
1247   EXPECT_TRUE(CordRepBtree::IsValid(empty));
1248   CordRep::Unref(empty);
1249 
1250   for (bool as_tree : {false, true}) {
1251     CordRepBtree* leaf = CordRepBtree::Create(MakeFlat("abc"));
1252     CordRepBtree* tree = as_tree ? CordRepBtree::New(leaf) : nullptr;
1253     CordRepBtree* check = as_tree ? tree : leaf;
1254 
1255     ASSERT_TRUE(CordRepBtree::IsValid(check));
1256     leaf->length--;
1257     EXPECT_FALSE(CordRepBtree::IsValid(check));
1258     leaf->length++;
1259 
1260     ASSERT_TRUE(CordRepBtree::IsValid(check));
1261     leaf->tag--;
1262     EXPECT_FALSE(CordRepBtree::IsValid(check));
1263     leaf->tag++;
1264 
1265     // Height
1266     ASSERT_TRUE(CordRepBtree::IsValid(check));
1267     leaf->storage[0] = static_cast<uint8_t>(CordRepBtree::kMaxHeight + 1);
1268     EXPECT_FALSE(CordRepBtree::IsValid(check));
1269     leaf->storage[0] = 1;
1270     EXPECT_FALSE(CordRepBtree::IsValid(check));
1271     leaf->storage[0] = 0;
1272 
1273     // Begin
1274     ASSERT_TRUE(CordRepBtree::IsValid(check));
1275     const uint8_t begin = leaf->storage[1];
1276     leaf->storage[1] = static_cast<uint8_t>(CordRepBtree::kMaxCapacity);
1277     EXPECT_FALSE(CordRepBtree::IsValid(check));
1278     leaf->storage[1] = 2;
1279     EXPECT_FALSE(CordRepBtree::IsValid(check));
1280     leaf->storage[1] = begin;
1281 
1282     // End
1283     ASSERT_TRUE(CordRepBtree::IsValid(check));
1284     const uint8_t end = leaf->storage[2];
1285     leaf->storage[2] = static_cast<uint8_t>(CordRepBtree::kMaxCapacity + 1);
1286     EXPECT_FALSE(CordRepBtree::IsValid(check));
1287     leaf->storage[2] = end;
1288 
1289     // DataEdge tag and value
1290     ASSERT_TRUE(CordRepBtree::IsValid(check));
1291     CordRep* const edge = leaf->Edges()[0];
1292     const uint8_t tag = edge->tag;
1293     CordRepBtreeTestPeer::SetEdge(leaf, begin, nullptr);
1294     EXPECT_FALSE(CordRepBtree::IsValid(check));
1295     CordRepBtreeTestPeer::SetEdge(leaf, begin, edge);
1296     edge->tag = BTREE;
1297     EXPECT_FALSE(CordRepBtree::IsValid(check));
1298     edge->tag = tag;
1299 
1300     if (as_tree) {
1301       ASSERT_TRUE(CordRepBtree::IsValid(check));
1302       leaf->length--;
1303       EXPECT_FALSE(CordRepBtree::IsValid(check));
1304       leaf->length++;
1305 
1306       // Height
1307       ASSERT_TRUE(CordRepBtree::IsValid(check));
1308       tree->storage[0] = static_cast<uint8_t>(2);
1309       EXPECT_FALSE(CordRepBtree::IsValid(check));
1310       tree->storage[0] = 1;
1311 
1312       // Btree edge
1313       ASSERT_TRUE(CordRepBtree::IsValid(check));
1314       CordRep* const edge = tree->Edges()[0];
1315       const uint8_t tag = edge->tag;
1316       edge->tag = FLAT;
1317       EXPECT_FALSE(CordRepBtree::IsValid(check));
1318       edge->tag = tag;
1319     }
1320 
1321     ASSERT_TRUE(CordRepBtree::IsValid(check));
1322     CordRep::Unref(check);
1323   }
1324 }
1325 
TEST(CordRepBtreeTest,AssertValid)1326 TEST(CordRepBtreeTest, AssertValid) {
1327   CordRepBtree* tree = CordRepBtree::Create(MakeFlat("abc"));
1328   const CordRepBtree* ctree = tree;
1329   EXPECT_THAT(CordRepBtree::AssertValid(tree), Eq(tree));
1330   EXPECT_THAT(CordRepBtree::AssertValid(ctree), Eq(ctree));
1331 
1332 #if defined(GTEST_HAS_DEATH_TEST)
1333   CordRepBtree* nulltree = nullptr;
1334   const CordRepBtree* cnulltree = nullptr;
1335   EXPECT_DEBUG_DEATH(
1336       EXPECT_THAT(CordRepBtree::AssertValid(nulltree), Eq(nulltree)), ".*");
1337   EXPECT_DEBUG_DEATH(
1338       EXPECT_THAT(CordRepBtree::AssertValid(cnulltree), Eq(cnulltree)), ".*");
1339 
1340   tree->length--;
1341   EXPECT_DEBUG_DEATH(EXPECT_THAT(CordRepBtree::AssertValid(tree), Eq(tree)),
1342                      ".*");
1343   EXPECT_DEBUG_DEATH(EXPECT_THAT(CordRepBtree::AssertValid(ctree), Eq(ctree)),
1344                      ".*");
1345   tree->length++;
1346 #endif
1347   CordRep::Unref(tree);
1348 }
1349 
TEST(CordRepBtreeTest,CheckAssertValidShallowVsDeep)1350 TEST(CordRepBtreeTest, CheckAssertValidShallowVsDeep) {
1351   // Restore exhaustive validation on any exit.
1352   const bool exhaustive_validation = cord_btree_exhaustive_validation.load();
1353   auto cleanup = absl::MakeCleanup([exhaustive_validation] {
1354     cord_btree_exhaustive_validation.store(exhaustive_validation);
1355   });
1356 
1357   // Create a tree of at least 2 levels, and mess with the original flat, which
1358   // should go undetected in shallow mode as the flat is too far away, but
1359   // should be detected in forced non-shallow mode.
1360   CordRep* flat = MakeFlat("abc");
1361   CordRepBtree* tree = CordRepBtree::Create(flat);
1362   constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
1363   const size_t n = max_cap * max_cap * 2;
1364   for (size_t i = 0; i < n; ++i) {
1365     tree = CordRepBtree::Append(tree, MakeFlat("Hello world"));
1366   }
1367   flat->length = 100;
1368 
1369   cord_btree_exhaustive_validation.store(false);
1370   EXPECT_FALSE(CordRepBtree::IsValid(tree));
1371   EXPECT_TRUE(CordRepBtree::IsValid(tree, true));
1372   EXPECT_FALSE(CordRepBtree::IsValid(tree, false));
1373   CordRepBtree::AssertValid(tree);
1374   CordRepBtree::AssertValid(tree, true);
1375 #if defined(GTEST_HAS_DEATH_TEST)
1376   EXPECT_DEBUG_DEATH(CordRepBtree::AssertValid(tree, false), ".*");
1377 #endif
1378 
1379   cord_btree_exhaustive_validation.store(true);
1380   EXPECT_FALSE(CordRepBtree::IsValid(tree));
1381   EXPECT_FALSE(CordRepBtree::IsValid(tree, true));
1382   EXPECT_FALSE(CordRepBtree::IsValid(tree, false));
1383 #if defined(GTEST_HAS_DEATH_TEST)
1384   EXPECT_DEBUG_DEATH(CordRepBtree::AssertValid(tree), ".*");
1385   EXPECT_DEBUG_DEATH(CordRepBtree::AssertValid(tree, true), ".*");
1386 #endif
1387 
1388   flat->length = 3;
1389   CordRep::Unref(tree);
1390 }
1391 
1392 }  // namespace
1393 }  // namespace cord_internal
1394 ABSL_NAMESPACE_END
1395 }  // namespace absl
1396