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