blob: 840acf9f52035fae236245bd966a66e52ab4508f [file] [log] [blame]
// Copyright 2021 The Abseil Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#include "absl/strings/internal/cord_rep_btree.h"
#include <cmath>
#include <deque>
#include <iostream>
#include <string>
#include <vector>
#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include "absl/base/config.h"
#include "absl/base/internal/raw_logging.h"
#include "absl/cleanup/cleanup.h"
#include "absl/strings/internal/cord_data_edge.h"
#include "absl/strings/internal/cord_internal.h"
#include "absl/strings/internal/cord_rep_test_util.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/string_view.h"
namespace absl {
ABSL_NAMESPACE_BEGIN
namespace cord_internal {
class CordRepBtreeTestPeer {
public:
static void SetEdge(CordRepBtree* node, size_t idx, CordRep* edge) {
node->edges_[idx] = edge;
}
static void AddEdge(CordRepBtree* node, CordRep* edge) {
node->edges_[node->fetch_add_end(1)] = edge;
}
};
namespace {
using ::absl::cordrep_testing::AutoUnref;
using ::absl::cordrep_testing::CordCollectRepsIf;
using ::absl::cordrep_testing::CordToString;
using ::absl::cordrep_testing::CordVisitReps;
using ::absl::cordrep_testing::CreateFlatsFromString;
using ::absl::cordrep_testing::CreateRandomString;
using ::absl::cordrep_testing::MakeExternal;
using ::absl::cordrep_testing::MakeFlat;
using ::absl::cordrep_testing::MakeSubstring;
using ::testing::_;
using ::testing::AllOf;
using ::testing::AnyOf;
using ::testing::Conditional;
using ::testing::ElementsAre;
using ::testing::ElementsAreArray;
using ::testing::Eq;
using ::testing::HasSubstr;
using ::testing::Le;
using ::testing::Ne;
using ::testing::Not;
using ::testing::SizeIs;
using ::testing::TypedEq;
MATCHER_P(EqFlatHolding, data, "Equals flat holding data") {
if (arg->tag < FLAT) {
*result_listener << "Expected FLAT, got tag " << static_cast<int>(arg->tag);
return false;
}
std::string actual = CordToString(arg);
if (actual != data) {
*result_listener << "Expected flat holding \"" << data
<< "\", got flat holding \"" << actual << "\"";
return false;
}
return true;
}
MATCHER_P(IsNode, height, absl::StrCat("Is a valid node of height ", height)) {
if (arg == nullptr) {
*result_listener << "Expected NODE, got nullptr";
return false;
}
if (arg->tag != BTREE) {
*result_listener << "Expected NODE, got " << static_cast<int>(arg->tag);
return false;
}
if (!CordRepBtree::IsValid(arg->btree())) {
CordRepBtree::Dump(arg->btree(), "Expected valid NODE, got:", false,
*result_listener->stream());
return false;
}
if (arg->btree()->height() != height) {
*result_listener << "Expected NODE of height " << height << ", got "
<< arg->btree()->height();
return false;
}
return true;
}
MATCHER_P2(IsSubstring, start, length,
absl::StrCat("Is a substring(start = ", start, ", length = ", length,
")")) {
if (arg == nullptr) {
*result_listener << "Expected substring, got nullptr";
return false;
}
if (arg->tag != SUBSTRING) {
*result_listener << "Expected SUBSTRING, got "
<< static_cast<int>(arg->tag);
return false;
}
const CordRepSubstring* const substr = arg->substring();
if (substr->start != start || substr->length != length) {
*result_listener << "Expected substring(" << start << ", " << length
<< "), got substring(" << substr->start << ", "
<< substr->length << ")";
return false;
}
return true;
}
MATCHER_P2(EqExtractResult, tree, rep, "Equals ExtractResult") {
if (arg.tree != tree || arg.extracted != rep) {
*result_listener << "Expected {" << static_cast<const void*>(tree) << ", "
<< static_cast<const void*>(rep) << "}, got {" << arg.tree
<< ", " << arg.extracted << "}";
return false;
}
return true;
}
// DataConsumer is a simple helper class used by tests to 'consume' string
// fragments from the provided input in forward or backward direction.
class DataConsumer {
public:
// Starts consumption of `data`. Caller must make sure `data` outlives this
// instance. Consumes data starting at the front if `forward` is true, else
// consumes data from the back.
DataConsumer(absl::string_view data, bool forward)
: data_(data), forward_(forward) {}
// Return the next `n` bytes from referenced data.
absl::string_view Next(size_t n) {
assert(n <= data_.size() - consumed_);
consumed_ += n;
return data_.substr(forward_ ? consumed_ - n : data_.size() - consumed_, n);
}
// Returns all data consumed so far.
absl::string_view Consumed() const {
return forward_ ? data_.substr(0, consumed_)
: data_.substr(data_.size() - consumed_);
}
private:
absl::string_view data_;
size_t consumed_ = 0;
bool forward_;
};
// BtreeAdd returns either CordRepBtree::Append or CordRepBtree::Prepend.
CordRepBtree* BtreeAdd(CordRepBtree* node, bool append,
absl::string_view data) {
return append ? CordRepBtree::Append(node, data)
: CordRepBtree::Prepend(node, data);
}
// Recursively collects all leaf edges from `tree` and appends them to `edges`.
void GetLeafEdges(const CordRepBtree* tree, std::vector<CordRep*>& edges) {
if (tree->height() == 0) {
for (CordRep* edge : tree->Edges()) {
edges.push_back(edge);
}
} else {
for (CordRep* edge : tree->Edges()) {
GetLeafEdges(edge->btree(), edges);
}
}
}
// Recursively collects and returns all leaf edges from `tree`.
std::vector<CordRep*> GetLeafEdges(const CordRepBtree* tree) {
std::vector<CordRep*> edges;
GetLeafEdges(tree, edges);
return edges;
}
// Creates a flat containing the hexadecimal value of `i` zero padded
// to at least 4 digits prefixed with "0x", e.g.: "0x04AC".
CordRepFlat* MakeHexFlat(size_t i) {
return MakeFlat(absl::StrCat("0x", absl::Hex(i, absl::kZeroPad4)));
}
CordRepBtree* MakeLeaf(size_t size = CordRepBtree::kMaxCapacity) {
assert(size <= CordRepBtree::kMaxCapacity);
CordRepBtree* leaf = CordRepBtree::Create(MakeHexFlat(0));
for (size_t i = 1; i < size; ++i) {
leaf = CordRepBtree::Append(leaf, MakeHexFlat(i));
}
return leaf;
}
CordRepBtree* MakeTree(size_t size, bool append = true) {
CordRepBtree* tree = CordRepBtree::Create(MakeHexFlat(0));
for (size_t i = 1; i < size; ++i) {
tree = append ? CordRepBtree::Append(tree, MakeHexFlat(i))
: CordRepBtree::Prepend(tree, MakeHexFlat(i));
}
return tree;
}
CordRepBtree* CreateTree(absl::Span<CordRep* const> reps) {
auto it = reps.begin();
CordRepBtree* tree = CordRepBtree::Create(*it);
while (++it != reps.end()) tree = CordRepBtree::Append(tree, *it);
return tree;
}
CordRepBtree* CreateTree(absl::string_view data, size_t chunk_size) {
return CreateTree(CreateFlatsFromString(data, chunk_size));
}
CordRepBtree* CreateTreeReverse(absl::string_view data, size_t chunk_size) {
std::vector<CordRep*> flats = CreateFlatsFromString(data, chunk_size);
auto rit = flats.rbegin();
CordRepBtree* tree = CordRepBtree::Create(*rit);
while (++rit != flats.rend()) tree = CordRepBtree::Prepend(tree, *rit);
return tree;
}
class CordRepBtreeTest : public testing::TestWithParam<bool> {
public:
bool shared() const { return GetParam(); }
static std::string ToString(testing::TestParamInfo<bool> param) {
return param.param ? "Shared" : "Private";
}
};
INSTANTIATE_TEST_SUITE_P(WithParam, CordRepBtreeTest, testing::Bool(),
CordRepBtreeTest::ToString);
class CordRepBtreeHeightTest : public testing::TestWithParam<int> {
public:
int height() const { return GetParam(); }
static std::string ToString(testing::TestParamInfo<int> param) {
return absl::StrCat(param.param);
}
};
INSTANTIATE_TEST_SUITE_P(WithHeights, CordRepBtreeHeightTest,
testing::Range(0, CordRepBtree::kMaxHeight),
CordRepBtreeHeightTest::ToString);
using TwoBools = testing::tuple<bool, bool>;
class CordRepBtreeDualTest : public testing::TestWithParam<TwoBools> {
public:
bool first_shared() const { return std::get<0>(GetParam()); }
bool second_shared() const { return std::get<1>(GetParam()); }
static std::string ToString(testing::TestParamInfo<TwoBools> param) {
if (std::get<0>(param.param)) {
return std::get<1>(param.param) ? "BothShared" : "FirstShared";
}
return std::get<1>(param.param) ? "SecondShared" : "Private";
}
};
INSTANTIATE_TEST_SUITE_P(WithParam, CordRepBtreeDualTest,
testing::Combine(testing::Bool(), testing::Bool()),
CordRepBtreeDualTest::ToString);
TEST(CordRepBtreeTest, SizeIsMultipleOf64) {
// Only enforce for fully 64-bit platforms.
if (sizeof(size_t) == 8 && sizeof(void*) == 8) {
EXPECT_THAT(sizeof(CordRepBtree) % 64, Eq(0u))
<< "Should be multiple of 64";
}
}
TEST(CordRepBtreeTest, NewDestroyEmptyTree) {
auto* tree = CordRepBtree::New();
EXPECT_THAT(tree->size(), Eq(0u));
EXPECT_THAT(tree->height(), Eq(0));
EXPECT_THAT(tree->Edges(), ElementsAre());
CordRepBtree::Destroy(tree);
}
TEST(CordRepBtreeTest, NewDestroyEmptyTreeAtHeight) {
auto* tree = CordRepBtree::New(3);
EXPECT_THAT(tree->size(), Eq(0u));
EXPECT_THAT(tree->height(), Eq(3));
EXPECT_THAT(tree->Edges(), ElementsAre());
CordRepBtree::Destroy(tree);
}
TEST(CordRepBtreeTest, Btree) {
CordRep* rep = CordRepBtree::New();
EXPECT_THAT(rep->btree(), Eq(rep));
EXPECT_THAT(static_cast<const CordRep*>(rep)->btree(), Eq(rep));
CordRep::Unref(rep);
#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
rep = MakeFlat("Hello world");
EXPECT_DEATH(rep->btree(), ".*");
EXPECT_DEATH(static_cast<const CordRep*>(rep)->btree(), ".*");
CordRep::Unref(rep);
#endif
}
TEST(CordRepBtreeTest, EdgeData) {
CordRepFlat* flat = MakeFlat("Hello world");
CordRepExternal* external = MakeExternal("Hello external");
CordRep* substr1 = MakeSubstring(1, 6, CordRep::Ref(flat));
CordRep* substr2 = MakeSubstring(1, 6, CordRep::Ref(external));
CordRep* bad_substr = MakeSubstring(1, 2, CordRep::Ref(substr1));
EXPECT_TRUE(IsDataEdge(flat));
EXPECT_THAT(EdgeData(flat).data(), TypedEq<const void*>(flat->Data()));
EXPECT_THAT(EdgeData(flat), Eq("Hello world"));
EXPECT_TRUE(IsDataEdge(external));
EXPECT_THAT(EdgeData(external).data(), TypedEq<const void*>(external->base));
EXPECT_THAT(EdgeData(external), Eq("Hello external"));
EXPECT_TRUE(IsDataEdge(substr1));
EXPECT_THAT(EdgeData(substr1).data(), TypedEq<const void*>(flat->Data() + 1));
EXPECT_THAT(EdgeData(substr1), Eq("ello w"));
EXPECT_TRUE(IsDataEdge(substr2));
EXPECT_THAT(EdgeData(substr2).data(),
TypedEq<const void*>(external->base + 1));
EXPECT_THAT(EdgeData(substr2), Eq("ello e"));
EXPECT_FALSE(IsDataEdge(bad_substr));
#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
EXPECT_DEATH(EdgeData(bad_substr), ".*");
#endif
CordRep::Unref(bad_substr);
CordRep::Unref(substr2);
CordRep::Unref(substr1);
CordRep::Unref(external);
CordRep::Unref(flat);
}
TEST(CordRepBtreeTest, CreateUnrefLeaf) {
auto* flat = MakeFlat("a");
auto* leaf = CordRepBtree::Create(flat);
EXPECT_THAT(leaf->size(), Eq(1u));
EXPECT_THAT(leaf->height(), Eq(0));
EXPECT_THAT(leaf->Edges(), ElementsAre(flat));
CordRepBtree::Unref(leaf);
}
TEST(CordRepBtreeTest, NewUnrefNode) {
auto* leaf = CordRepBtree::Create(MakeFlat("a"));
CordRepBtree* tree = CordRepBtree::New(leaf);
EXPECT_THAT(tree->size(), Eq(1u));
EXPECT_THAT(tree->height(), Eq(1));
EXPECT_THAT(tree->Edges(), ElementsAre(leaf));
CordRepBtree::Unref(tree);
}
TEST_P(CordRepBtreeTest, AppendToLeafToCapacity) {
AutoUnref refs;
std::vector<CordRep*> flats;
flats.push_back(MakeHexFlat(0));
auto* leaf = CordRepBtree::Create(flats.back());
for (size_t i = 1; i < CordRepBtree::kMaxCapacity; ++i) {
refs.RefIf(shared(), leaf);
flats.push_back(MakeHexFlat(i));
auto* result = CordRepBtree::Append(leaf, flats.back());
EXPECT_THAT(result->height(), Eq(0));
EXPECT_THAT(result, Conditional(shared(), Ne(leaf), Eq(leaf)));
EXPECT_THAT(result->Edges(), ElementsAreArray(flats));
leaf = result;
}
CordRep::Unref(leaf);
}
TEST_P(CordRepBtreeTest, PrependToLeafToCapacity) {
AutoUnref refs;
std::deque<CordRep*> flats;
flats.push_front(MakeHexFlat(0));
auto* leaf = CordRepBtree::Create(flats.front());
for (size_t i = 1; i < CordRepBtree::kMaxCapacity; ++i) {
refs.RefIf(shared(), leaf);
flats.push_front(MakeHexFlat(i));
auto* result = CordRepBtree::Prepend(leaf, flats.front());
EXPECT_THAT(result->height(), Eq(0));
EXPECT_THAT(result, Conditional(shared(), Ne(leaf), Eq(leaf)));
EXPECT_THAT(result->Edges(), ElementsAreArray(flats));
leaf = result;
}
CordRep::Unref(leaf);
}
// This test specifically aims at code aligning data at either the front or the
// back of the contained `edges[]` array, alternating Append and Prepend will
// move `begin()` and `end()` values as needed for each added value.
TEST_P(CordRepBtreeTest, AppendPrependToLeafToCapacity) {
AutoUnref refs;
std::deque<CordRep*> flats;
flats.push_front(MakeHexFlat(0));
auto* leaf = CordRepBtree::Create(flats.front());
for (size_t i = 1; i < CordRepBtree::kMaxCapacity; ++i) {
refs.RefIf(shared(), leaf);
CordRepBtree* result;
if (i % 2 != 0) {
flats.push_front(MakeHexFlat(i));
result = CordRepBtree::Prepend(leaf, flats.front());
} else {
flats.push_back(MakeHexFlat(i));
result = CordRepBtree::Append(leaf, flats.back());
}
EXPECT_THAT(result->height(), Eq(0));
EXPECT_THAT(result, Conditional(shared(), Ne(leaf), Eq(leaf)));
EXPECT_THAT(result->Edges(), ElementsAreArray(flats));
leaf = result;
}
CordRep::Unref(leaf);
}
TEST_P(CordRepBtreeTest, AppendToLeafBeyondCapacity) {
AutoUnref refs;
auto* leaf = MakeLeaf();
refs.RefIf(shared(), leaf);
CordRep* flat = MakeFlat("abc");
auto* result = CordRepBtree::Append(leaf, flat);
ASSERT_THAT(result, IsNode(1));
EXPECT_THAT(result, Ne(leaf));
absl::Span<CordRep* const> edges = result->Edges();
ASSERT_THAT(edges, ElementsAre(leaf, IsNode(0)));
EXPECT_THAT(edges[1]->btree()->Edges(), ElementsAre(flat));
CordRep::Unref(result);
}
TEST_P(CordRepBtreeTest, PrependToLeafBeyondCapacity) {
AutoUnref refs;
auto* leaf = MakeLeaf();
refs.RefIf(shared(), leaf);
CordRep* flat = MakeFlat("abc");
auto* result = CordRepBtree::Prepend(leaf, flat);
ASSERT_THAT(result, IsNode(1));
EXPECT_THAT(result, Ne(leaf));
absl::Span<CordRep* const> edges = result->Edges();
ASSERT_THAT(edges, ElementsAre(IsNode(0), leaf));
EXPECT_THAT(edges[0]->btree()->Edges(), ElementsAre(flat));
CordRep::Unref(result);
}
TEST_P(CordRepBtreeTest, AppendToTreeOneDeep) {
constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
AutoUnref refs;
std::vector<CordRep*> flats;
flats.push_back(MakeHexFlat(0));
CordRepBtree* tree = CordRepBtree::Create(flats.back());
for (size_t i = 1; i <= max_cap; ++i) {
flats.push_back(MakeHexFlat(i));
tree = CordRepBtree::Append(tree, flats.back());
}
ASSERT_THAT(tree, IsNode(1));
for (size_t i = max_cap + 1; i < max_cap * max_cap; ++i) {
// Ref top level tree based on param.
// Ref leaf node once every 4 iterations, which should not have an
// observable effect other than that the leaf itself is copied.
refs.RefIf(shared(), tree);
refs.RefIf(i % 4 == 0, tree->Edges().back());
flats.push_back(MakeHexFlat(i));
CordRepBtree* result = CordRepBtree::Append(tree, flats.back());
ASSERT_THAT(result, IsNode(1));
ASSERT_THAT(result, Conditional(shared(), Ne(tree), Eq(tree)));
std::vector<CordRep*> edges = GetLeafEdges(result);
ASSERT_THAT(edges, ElementsAreArray(flats));
tree = result;
}
CordRep::Unref(tree);
}
TEST_P(CordRepBtreeTest, AppendToTreeTwoDeep) {
constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
AutoUnref refs;
std::vector<CordRep*> flats;
flats.push_back(MakeHexFlat(0));
CordRepBtree* tree = CordRepBtree::Create(flats.back());
for (size_t i = 1; i <= max_cap * max_cap; ++i) {
flats.push_back(MakeHexFlat(i));
tree = CordRepBtree::Append(tree, flats.back());
}
ASSERT_THAT(tree, IsNode(2));
for (size_t i = max_cap * max_cap + 1; i < max_cap * max_cap * max_cap; ++i) {
// Ref top level tree based on param.
// Ref child node once every 16 iterations, and leaf node every 4
// iterations which which should not have an observable effect other than
// the node and/or the leaf below it being copied.
refs.RefIf(shared(), tree);
refs.RefIf(i % 16 == 0, tree->Edges().back());
refs.RefIf(i % 4 == 0, tree->Edges().back()->btree()->Edges().back());
flats.push_back(MakeHexFlat(i));
CordRepBtree* result = CordRepBtree::Append(tree, flats.back());
ASSERT_THAT(result, IsNode(2));
ASSERT_THAT(result, Conditional(shared(), Ne(tree), Eq(tree)));
std::vector<CordRep*> edges = GetLeafEdges(result);
ASSERT_THAT(edges, ElementsAreArray(flats));
tree = result;
}
CordRep::Unref(tree);
}
TEST_P(CordRepBtreeTest, PrependToTreeOneDeep) {
constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
AutoUnref refs;
std::deque<CordRep*> flats;
flats.push_back(MakeHexFlat(0));
CordRepBtree* tree = CordRepBtree::Create(flats.back());
for (size_t i = 1; i <= max_cap; ++i) {
flats.push_front(MakeHexFlat(i));
tree = CordRepBtree::Prepend(tree, flats.front());
}
ASSERT_THAT(tree, IsNode(1));
for (size_t i = max_cap + 1; i < max_cap * max_cap; ++i) {
// Ref top level tree based on param.
// Ref leaf node once every 4 iterations which should not have an observable
// effect other than than the leaf itself is copied.
refs.RefIf(shared(), tree);
refs.RefIf(i % 4 == 0, tree->Edges().back());
flats.push_front(MakeHexFlat(i));
CordRepBtree* result = CordRepBtree::Prepend(tree, flats.front());
ASSERT_THAT(result, IsNode(1));
ASSERT_THAT(result, Conditional(shared(), Ne(tree), Eq(tree)));
std::vector<CordRep*> edges = GetLeafEdges(result);
ASSERT_THAT(edges, ElementsAreArray(flats));
tree = result;
}
CordRep::Unref(tree);
}
TEST_P(CordRepBtreeTest, PrependToTreeTwoDeep) {
constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
AutoUnref refs;
std::deque<CordRep*> flats;
flats.push_back(MakeHexFlat(0));
CordRepBtree* tree = CordRepBtree::Create(flats.back());
for (size_t i = 1; i <= max_cap * max_cap; ++i) {
flats.push_front(MakeHexFlat(i));
tree = CordRepBtree::Prepend(tree, flats.front());
}
ASSERT_THAT(tree, IsNode(2));
for (size_t i = max_cap * max_cap + 1; i < max_cap * max_cap * max_cap; ++i) {
// Ref top level tree based on param.
// Ref child node once every 16 iterations, and leaf node every 4
// iterations which which should not have an observable effect other than
// the node and/or the leaf below it being copied.
refs.RefIf(shared(), tree);
refs.RefIf(i % 16 == 0, tree->Edges().back());
refs.RefIf(i % 4 == 0, tree->Edges().back()->btree()->Edges().back());
flats.push_front(MakeHexFlat(i));
CordRepBtree* result = CordRepBtree::Prepend(tree, flats.front());
ASSERT_THAT(result, IsNode(2));
ASSERT_THAT(result, Conditional(shared(), Ne(tree), Eq(tree)));
std::vector<CordRep*> edges = GetLeafEdges(result);
ASSERT_THAT(edges, ElementsAreArray(flats));
tree = result;
}
CordRep::Unref(tree);
}
TEST_P(CordRepBtreeDualTest, MergeLeafsNotExceedingCapacity) {
for (bool use_append : {false, true}) {
SCOPED_TRACE(use_append ? "Using Append" : "Using Prepend");
AutoUnref refs;
std::vector<CordRep*> flats;
// Build `left` side leaf appending all contained flats to `flats`
CordRepBtree* left = MakeLeaf(3);
GetLeafEdges(left, flats);
refs.RefIf(first_shared(), left);
// Build `right` side leaf appending all contained flats to `flats`
CordRepBtree* right = MakeLeaf(2);
GetLeafEdges(right, flats);
refs.RefIf(second_shared(), right);
CordRepBtree* tree = use_append ? CordRepBtree::Append(left, right)
: CordRepBtree::Prepend(right, left);
EXPECT_THAT(tree, IsNode(0));
// `tree` contains all flats originally belonging to `left` and `right`.
EXPECT_THAT(tree->Edges(), ElementsAreArray(flats));
CordRepBtree::Unref(tree);
}
}
TEST_P(CordRepBtreeDualTest, MergeLeafsExceedingCapacity) {
for (bool use_append : {false, true}) {
SCOPED_TRACE(use_append ? "Using Append" : "Using Prepend");
AutoUnref refs;
// Build `left` side tree appending all contained flats to `flats`
CordRepBtree* left = MakeLeaf(CordRepBtree::kMaxCapacity - 2);
refs.RefIf(first_shared(), left);
// Build `right` side tree appending all contained flats to `flats`
CordRepBtree* right = MakeLeaf(CordRepBtree::kMaxCapacity - 1);
refs.RefIf(second_shared(), right);
CordRepBtree* tree = use_append ? CordRepBtree::Append(left, right)
: CordRepBtree::Prepend(right, left);
EXPECT_THAT(tree, IsNode(1));
EXPECT_THAT(tree->Edges(), ElementsAre(left, right));
CordRepBtree::Unref(tree);
}
}
TEST_P(CordRepBtreeDualTest, MergeEqualHeightTrees) {
for (bool use_append : {false, true}) {
SCOPED_TRACE(use_append ? "Using Append" : "Using Prepend");
AutoUnref refs;
std::vector<CordRep*> flats;
// Build `left` side tree appending all contained flats to `flats`
CordRepBtree* left = MakeTree(CordRepBtree::kMaxCapacity * 3);
GetLeafEdges(left, flats);
refs.RefIf(first_shared(), left);
// Build `right` side tree appending all contained flats to `flats`
CordRepBtree* right = MakeTree(CordRepBtree::kMaxCapacity * 2);
GetLeafEdges(right, flats);
refs.RefIf(second_shared(), right);
CordRepBtree* tree = use_append ? CordRepBtree::Append(left, right)
: CordRepBtree::Prepend(right, left);
EXPECT_THAT(tree, IsNode(1));
EXPECT_THAT(tree->Edges(), SizeIs(5u));
// `tree` contains all flats originally belonging to `left` and `right`.
EXPECT_THAT(GetLeafEdges(tree), ElementsAreArray(flats));
CordRepBtree::Unref(tree);
}
}
TEST_P(CordRepBtreeDualTest, MergeLeafWithTreeNotExceedingLeafCapacity) {
for (bool use_append : {false, true}) {
SCOPED_TRACE(use_append ? "Using Append" : "Using Prepend");
AutoUnref refs;
std::vector<CordRep*> flats;
// Build `left` side tree appending all added flats to `flats`
CordRepBtree* left = MakeTree(CordRepBtree::kMaxCapacity * 2 + 2);
GetLeafEdges(left, flats);
refs.RefIf(first_shared(), left);
// Build `right` side tree appending all added flats to `flats`
CordRepBtree* right = MakeTree(3);
GetLeafEdges(right, flats);
refs.RefIf(second_shared(), right);
CordRepBtree* tree = use_append ? CordRepBtree::Append(left, right)
: CordRepBtree::Prepend(right, left);
EXPECT_THAT(tree, IsNode(1));
EXPECT_THAT(tree->Edges(), SizeIs(3u));
// `tree` contains all flats originally belonging to `left` and `right`.
EXPECT_THAT(GetLeafEdges(tree), ElementsAreArray(flats));
CordRepBtree::Unref(tree);
}
}
TEST_P(CordRepBtreeDualTest, MergeLeafWithTreeExceedingLeafCapacity) {
for (bool use_append : {false, true}) {
SCOPED_TRACE(use_append ? "Using Append" : "Using Prepend");
AutoUnref refs;
std::vector<CordRep*> flats;
// Build `left` side tree appending all added flats to `flats`
CordRepBtree* left = MakeTree(CordRepBtree::kMaxCapacity * 3 - 2);
GetLeafEdges(left, flats);
refs.RefIf(first_shared(), left);
// Build `right` side tree appending all added flats to `flats`
CordRepBtree* right = MakeTree(3);
GetLeafEdges(right, flats);
refs.RefIf(second_shared(), right);
CordRepBtree* tree = use_append ? CordRepBtree::Append(left, right)
: CordRepBtree::Prepend(right, left);
EXPECT_THAT(tree, IsNode(1));
EXPECT_THAT(tree->Edges(), SizeIs(4u));
// `tree` contains all flats originally belonging to `left` and `right`.
EXPECT_THAT(GetLeafEdges(tree), ElementsAreArray(flats));
CordRepBtree::Unref(tree);
}
}
void RefEdgesAt(size_t depth, AutoUnref& refs, CordRepBtree* tree) {
absl::Span<CordRep* const> edges = tree->Edges();
if (depth == 0) {
refs.Ref(edges.front());
refs.Ref(edges.back());
} else {
assert(tree->height() > 0);
RefEdgesAt(depth - 1, refs, edges.front()->btree());
RefEdgesAt(depth - 1, refs, edges.back()->btree());
}
}
TEST(CordRepBtreeTest, MergeFuzzTest) {
constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
std::minstd_rand rnd;
std::uniform_int_distribution<int> coin_flip(0, 1);
std::uniform_int_distribution<int> dice_throw(1, 6);
auto random_leaf_count = [&]() {
std::uniform_int_distribution<int> dist_height(0, 3);
std::uniform_int_distribution<int> dist_leaf(0, max_cap - 1);
const int height = dist_height(rnd);
return (height ? pow(max_cap, height) : 0) + dist_leaf(rnd);
};
for (int i = 0; i < 10000; ++i) {
AutoUnref refs;
std::vector<CordRep*> flats;
CordRepBtree* left = MakeTree(random_leaf_count(), coin_flip(rnd));
GetLeafEdges(left, flats);
if (dice_throw(rnd) == 1) {
std::uniform_int_distribution<size_t> dist(
0, static_cast<size_t>(left->height()));
RefEdgesAt(dist(rnd), refs, left);
}
CordRepBtree* right = MakeTree(random_leaf_count(), coin_flip(rnd));
GetLeafEdges(right, flats);
if (dice_throw(rnd) == 1) {
std::uniform_int_distribution<size_t> dist(
0, static_cast<size_t>(right->height()));
RefEdgesAt(dist(rnd), refs, right);
}
CordRepBtree* tree = CordRepBtree::Append(left, right);
EXPECT_THAT(GetLeafEdges(tree), ElementsAreArray(flats));
CordRepBtree::Unref(tree);
}
}
TEST_P(CordRepBtreeTest, RemoveSuffix) {
// Create tree of 1, 2 and 3 levels high
constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
for (size_t cap : {max_cap - 1, max_cap * 2, max_cap * max_cap * 2}) {
const std::string data = CreateRandomString(cap * 512);
{
// Verify RemoveSuffix(<all>)
AutoUnref refs;
CordRepBtree* node = refs.RefIf(shared(), CreateTree(data, 512));
EXPECT_THAT(CordRepBtree::RemoveSuffix(node, data.length()), Eq(nullptr));
// Verify RemoveSuffix(<none>)
node = refs.RefIf(shared(), CreateTree(data, 512));
EXPECT_THAT(CordRepBtree::RemoveSuffix(node, 0), Eq(node));
CordRep::Unref(node);
}
for (size_t n = 1; n < data.length(); ++n) {
AutoUnref refs;
auto flats = CreateFlatsFromString(data, 512);
CordRepBtree* node = refs.RefIf(shared(), CreateTree(flats));
CordRep* rep = refs.Add(CordRepBtree::RemoveSuffix(node, n));
EXPECT_THAT(CordToString(rep), Eq(data.substr(0, data.length() - n)));
// Collect all flats
auto is_flat = [](CordRep* rep) { return rep->tag >= FLAT; };
std::vector<CordRep*> edges = CordCollectRepsIf(is_flat, rep);
ASSERT_THAT(edges.size(), Le(flats.size()));
// Isolate last edge
CordRep* last_edge = edges.back();
edges.pop_back();
const size_t last_length = rep->length - edges.size() * 512;
// All flats except the last edge must be kept or copied 'as is'
size_t index = 0;
for (CordRep* edge : edges) {
ASSERT_THAT(edge, Eq(flats[index++]));
ASSERT_THAT(edge->length, Eq(512u));
}
// CordRepBtree may optimize small substrings to avoid waste, so only
// check for flat sharing / updates where the code should always do this.
if (last_length >= 500) {
EXPECT_THAT(last_edge, Eq(flats[index++]));
if (shared()) {
EXPECT_THAT(last_edge->length, Eq(512u));
} else {
EXPECT_TRUE(last_edge->refcount.IsOne());
EXPECT_THAT(last_edge->length, Eq(last_length));
}
}
}
}
}
TEST(CordRepBtreeTest, SubTree) {
// Create tree of at least 2 levels high
constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
const size_t n = max_cap * max_cap * 2;
const std::string data = CreateRandomString(n * 3);
std::vector<CordRep*> flats;
for (absl::string_view s = data; !s.empty(); s.remove_prefix(3)) {
flats.push_back(MakeFlat(s.substr(0, 3)));
}
CordRepBtree* node = CordRepBtree::Create(CordRep::Ref(flats[0]));
for (size_t i = 1; i < flats.size(); ++i) {
node = CordRepBtree::Append(node, CordRep::Ref(flats[i]));
}
for (size_t offset = 0; offset < data.length(); ++offset) {
for (size_t length = 1; length <= data.length() - offset; ++length) {
CordRep* rep = node->SubTree(offset, length);
EXPECT_THAT(CordToString(rep), Eq(data.substr(offset, length)));
CordRep::Unref(rep);
}
}
CordRepBtree::Unref(node);
for (CordRep* rep : flats) {
CordRep::Unref(rep);
}
}
TEST(CordRepBtreeTest, SubTreeOnExistingSubstring) {
// This test verifies that a SubTree call on a pre-existing (large) substring
// adjusts the existing substring if not shared, and else rewrites the
// existing substring.
AutoUnref refs;
std::string data = CreateRandomString(1000);
CordRepBtree* leaf = CordRepBtree::Create(MakeFlat("abc"));
CordRep* flat = MakeFlat(data);
leaf = CordRepBtree::Append(leaf, flat);
// Setup tree containing substring.
CordRep* result = leaf->SubTree(0, 3 + 990);
ASSERT_THAT(result->tag, Eq(BTREE));
CordRep::Unref(leaf);
leaf = result->btree();
ASSERT_THAT(leaf->Edges(), ElementsAre(_, IsSubstring(0u, 990u)));
EXPECT_THAT(leaf->Edges()[1]->substring()->child, Eq(flat));
// Verify substring of substring.
result = leaf->SubTree(3 + 5, 970);
ASSERT_THAT(result, IsSubstring(5u, 970u));
EXPECT_THAT(result->substring()->child, Eq(flat));
CordRep::Unref(result);
CordRep::Unref(leaf);
}
TEST_P(CordRepBtreeTest, AddDataToLeaf) {
const size_t n = CordRepBtree::kMaxCapacity;
const std::string data = CreateRandomString(n * 3);
for (bool append : {true, false}) {
AutoUnref refs;
DataConsumer consumer(data, append);
SCOPED_TRACE(append ? "Append" : "Prepend");
CordRepBtree* leaf = CordRepBtree::Create(MakeFlat(consumer.Next(3)));
for (size_t i = 1; i < n; ++i) {
refs.RefIf(shared(), leaf);
CordRepBtree* result = BtreeAdd(leaf, append, consumer.Next(3));
EXPECT_THAT(result, Conditional(shared(), Ne(leaf), Eq(leaf)));
EXPECT_THAT(CordToString(result), Eq(consumer.Consumed()));
leaf = result;
}
CordRep::Unref(leaf);
}
}
TEST_P(CordRepBtreeTest, AppendDataToTree) {
AutoUnref refs;
size_t n = CordRepBtree::kMaxCapacity + CordRepBtree::kMaxCapacity / 2;
std::string data = CreateRandomString(n * 3);
CordRepBtree* tree = refs.RefIf(shared(), CreateTree(data, 3));
CordRepBtree* leaf0 = tree->Edges()[0]->btree();
CordRepBtree* leaf1 = tree->Edges()[1]->btree();
CordRepBtree* result = CordRepBtree::Append(tree, "123456789");
EXPECT_THAT(result, Conditional(shared(), Ne(tree), Eq(tree)));
EXPECT_THAT(result->Edges(),
ElementsAre(leaf0, Conditional(shared(), Ne(leaf1), Eq(leaf1))));
EXPECT_THAT(CordToString(result), Eq(data + "123456789"));
CordRep::Unref(result);
}
TEST_P(CordRepBtreeTest, PrependDataToTree) {
AutoUnref refs;
size_t n = CordRepBtree::kMaxCapacity + CordRepBtree::kMaxCapacity / 2;
std::string data = CreateRandomString(n * 3);
CordRepBtree* tree = refs.RefIf(shared(), CreateTreeReverse(data, 3));
CordRepBtree* leaf0 = tree->Edges()[0]->btree();
CordRepBtree* leaf1 = tree->Edges()[1]->btree();
CordRepBtree* result = CordRepBtree::Prepend(tree, "123456789");
EXPECT_THAT(result, Conditional(shared(), Ne(tree), Eq(tree)));
EXPECT_THAT(result->Edges(),
ElementsAre(Conditional(shared(), Ne(leaf0), Eq(leaf0)), leaf1));
EXPECT_THAT(CordToString(result), Eq("123456789" + data));
CordRep::Unref(result);
}
TEST_P(CordRepBtreeTest, AddDataToTreeThreeLevelsDeep) {
constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
const size_t n = max_cap * max_cap * max_cap;
const std::string data = CreateRandomString(n * 3);
for (bool append : {true, false}) {
AutoUnref refs;
DataConsumer consumer(data, append);
SCOPED_TRACE(append ? "Append" : "Prepend");
// Fill leaf
CordRepBtree* tree = CordRepBtree::Create(MakeFlat(consumer.Next(3)));
for (size_t i = 1; i < max_cap; ++i) {
tree = BtreeAdd(tree, append, consumer.Next(3));
}
ASSERT_THAT(CordToString(tree), Eq(consumer.Consumed()));
// Fill to maximum at one deep
refs.RefIf(shared(), tree);
CordRepBtree* result = BtreeAdd(tree, append, consumer.Next(3));
ASSERT_THAT(result, IsNode(1));
ASSERT_THAT(result, Ne(tree));
ASSERT_THAT(CordToString(result), Eq(consumer.Consumed()));
tree = result;
for (size_t i = max_cap + 1; i < max_cap * max_cap; ++i) {
refs.RefIf(shared(), tree);
result = BtreeAdd(tree, append, consumer.Next(3));
ASSERT_THAT(result, Conditional(shared(), Ne(tree), Eq(tree)));
ASSERT_THAT(CordToString(result), Eq(consumer.Consumed()));
tree = result;
}
// Fill to maximum at two deep
refs.RefIf(shared(), tree);
result = BtreeAdd(tree, append, consumer.Next(3));
ASSERT_THAT(result, IsNode(2));
ASSERT_THAT(result, Ne(tree));
ASSERT_THAT(CordToString(result), Eq(consumer.Consumed()));
tree = result;
for (size_t i = max_cap * max_cap + 1; i < max_cap * max_cap * max_cap;
++i) {
refs.RefIf(shared(), tree);
result = BtreeAdd(tree, append, consumer.Next(3));
ASSERT_THAT(result, Conditional(shared(), Ne(tree), Eq(tree)));
ASSERT_THAT(CordToString(result), Eq(consumer.Consumed()));
tree = result;
}
CordRep::Unref(tree);
}
}
TEST_P(CordRepBtreeTest, AddLargeDataToLeaf) {
const size_t max_cap = CordRepBtree::kMaxCapacity;
const size_t n = max_cap * max_cap * max_cap * 3 + 2;
const std::string data = CreateRandomString(n * kMaxFlatLength);
for (bool append : {true, false}) {
AutoUnref refs;
SCOPED_TRACE(append ? "Append" : "Prepend");
CordRepBtree* leaf = CordRepBtree::Create(MakeFlat("abc"));
refs.RefIf(shared(), leaf);
CordRepBtree* result = BtreeAdd(leaf, append, data);
EXPECT_THAT(CordToString(result), Eq(append ? "abc" + data : data + "abc"));
CordRep::Unref(result);
}
}
TEST_P(CordRepBtreeTest, CreateFromTreeReturnsTree) {
AutoUnref refs;
CordRepBtree* leaf = CordRepBtree::Create(MakeFlat("Hello world"));
refs.RefIf(shared(), leaf);
CordRepBtree* result = CordRepBtree::Create(leaf);
EXPECT_THAT(result, Eq(leaf));
CordRep::Unref(result);
}
TEST(CordRepBtreeTest, GetCharacter) {
size_t n = CordRepBtree::kMaxCapacity * CordRepBtree::kMaxCapacity + 2;
std::string data = CreateRandomString(n * 3);
CordRepBtree* tree = CreateTree(data, 3);
// Add a substring node for good measure.
tree = tree->Append(tree, MakeSubstring(4, 5, MakeFlat("abcdefghijklm")));
data += "efghi";
for (size_t i = 0; i < data.length(); ++i) {
ASSERT_THAT(tree->GetCharacter(i), Eq(data[i]));
}
CordRep::Unref(tree);
}
TEST_P(CordRepBtreeTest, IsFlatSingleFlat) {
CordRepBtree* leaf = CordRepBtree::Create(MakeFlat("Hello world"));
absl::string_view fragment;
EXPECT_TRUE(leaf->IsFlat(nullptr));
EXPECT_TRUE(leaf->IsFlat(&fragment));
EXPECT_THAT(fragment, Eq("Hello world"));
fragment = "";
EXPECT_TRUE(leaf->IsFlat(0, 11, nullptr));
EXPECT_TRUE(leaf->IsFlat(0, 11, &fragment));
EXPECT_THAT(fragment, Eq("Hello world"));
// Arbitrary ranges must check true as well.
EXPECT_TRUE(leaf->IsFlat(1, 4, &fragment));
EXPECT_THAT(fragment, Eq("ello"));
EXPECT_TRUE(leaf->IsFlat(6, 5, &fragment));
EXPECT_THAT(fragment, Eq("world"));
CordRep::Unref(leaf);
}
TEST(CordRepBtreeTest, IsFlatMultiFlat) {
size_t n = CordRepBtree::kMaxCapacity * CordRepBtree::kMaxCapacity + 2;
std::string data = CreateRandomString(n * 3);
CordRepBtree* tree = CreateTree(data, 3);
// Add substring nodes for good measure.
tree = tree->Append(tree, MakeSubstring(4, 3, MakeFlat("abcdefghijklm")));
tree = tree->Append(tree, MakeSubstring(8, 3, MakeFlat("abcdefghijklm")));
data += "efgijk";
EXPECT_FALSE(tree->IsFlat(nullptr));
absl::string_view fragment = "Can't touch this";
EXPECT_FALSE(tree->IsFlat(&fragment));
EXPECT_THAT(fragment, Eq("Can't touch this"));
for (size_t offset = 0; offset < data.size(); offset += 3) {
EXPECT_TRUE(tree->IsFlat(offset, 3, nullptr));
EXPECT_TRUE(tree->IsFlat(offset, 3, &fragment));
EXPECT_THAT(fragment, Eq(data.substr(offset, 3)));
fragment = "Can't touch this";
if (offset > 0) {
EXPECT_FALSE(tree->IsFlat(offset - 1, 4, nullptr));
EXPECT_FALSE(tree->IsFlat(offset - 1, 4, &fragment));
EXPECT_THAT(fragment, Eq("Can't touch this"));
}
if (offset < data.size() - 4) {
EXPECT_FALSE(tree->IsFlat(offset, 4, nullptr));
EXPECT_FALSE(tree->IsFlat(offset, 4, &fragment));
EXPECT_THAT(fragment, Eq("Can't touch this"));
}
}
CordRep::Unref(tree);
}
#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
TEST_P(CordRepBtreeHeightTest, GetAppendBufferNotPrivate) {
CordRepBtree* tree = CordRepBtree::Create(MakeExternal("Foo"));
CordRepBtree::Ref(tree);
EXPECT_DEATH(tree->GetAppendBuffer(1), ".*");
CordRepBtree::Unref(tree);
CordRepBtree::Unref(tree);
}
#endif // defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
TEST_P(CordRepBtreeHeightTest, GetAppendBufferNotFlat) {
CordRepBtree* tree = CordRepBtree::Create(MakeExternal("Foo"));
for (int i = 1; i <= height(); ++i) {
tree = CordRepBtree::New(tree);
}
EXPECT_THAT(tree->GetAppendBuffer(1), SizeIs(0u));
CordRepBtree::Unref(tree);
}
TEST_P(CordRepBtreeHeightTest, GetAppendBufferFlatNotPrivate) {
CordRepFlat* flat = MakeFlat("abc");
CordRepBtree* tree = CordRepBtree::Create(CordRep::Ref(flat));
for (int i = 1; i <= height(); ++i) {
tree = CordRepBtree::New(tree);
}
EXPECT_THAT(tree->GetAppendBuffer(1), SizeIs(0u));
CordRepBtree::Unref(tree);
CordRep::Unref(flat);
}
TEST_P(CordRepBtreeHeightTest, GetAppendBufferTreeNotPrivate) {
if (height() == 0) return;
AutoUnref refs;
CordRepFlat* flat = MakeFlat("abc");
CordRepBtree* tree = CordRepBtree::Create(CordRep::Ref(flat));
for (int i = 1; i <= height(); ++i) {
if (i == (height() + 1) / 2) refs.Ref(tree);
tree = CordRepBtree::New(tree);
}
EXPECT_THAT(tree->GetAppendBuffer(1), SizeIs(0u));
CordRepBtree::Unref(tree);
CordRep::Unref(flat);
}
TEST_P(CordRepBtreeHeightTest, GetAppendBufferFlatNoCapacity) {
CordRepFlat* flat = MakeFlat("abc");
flat->length = flat->Capacity();
CordRepBtree* tree = CordRepBtree::Create(flat);
for (int i = 1; i <= height(); ++i) {
tree = CordRepBtree::New(tree);
}
EXPECT_THAT(tree->GetAppendBuffer(1), SizeIs(0u));
CordRepBtree::Unref(tree);
}
TEST_P(CordRepBtreeHeightTest, GetAppendBufferFlatWithCapacity) {
CordRepFlat* flat = MakeFlat("abc");
CordRepBtree* tree = CordRepBtree::Create(flat);
for (int i = 1; i <= height(); ++i) {
tree = CordRepBtree::New(tree);
}
absl::Span<char> span = tree->GetAppendBuffer(2);
EXPECT_THAT(span, SizeIs(2u));
EXPECT_THAT(span.data(), TypedEq<void*>(flat->Data() + 3));
EXPECT_THAT(tree->length, Eq(5u));
size_t avail = flat->Capacity() - 5;
span = tree->GetAppendBuffer(avail + 100);
EXPECT_THAT(span, SizeIs(avail));
EXPECT_THAT(span.data(), TypedEq<void*>(flat->Data() + 5));
EXPECT_THAT(tree->length, Eq(5 + avail));
CordRepBtree::Unref(tree);
}
TEST(CordRepBtreeTest, Dump) {
// Handles nullptr
std::stringstream ss;
CordRepBtree::Dump(nullptr, ss);
CordRepBtree::Dump(nullptr, "Once upon a label", ss);
CordRepBtree::Dump(nullptr, "Once upon a label", false, ss);
CordRepBtree::Dump(nullptr, "Once upon a label", true, ss);
// Cover legal edges
CordRepFlat* flat = MakeFlat("Hello world");
CordRepExternal* external = MakeExternal("Hello external");
CordRep* substr_flat = MakeSubstring(1, 6, CordRep::Ref(flat));
CordRep* substr_external = MakeSubstring(2, 7, CordRep::Ref(external));
// Build tree
CordRepBtree* tree = CordRepBtree::Create(flat);
tree = CordRepBtree::Append(tree, external);
tree = CordRepBtree::Append(tree, substr_flat);
tree = CordRepBtree::Append(tree, substr_external);
// Repeat until we have a tree
while (tree->height() == 0) {
tree = CordRepBtree::Append(tree, CordRep::Ref(flat));
tree = CordRepBtree::Append(tree, CordRep::Ref(external));
tree = CordRepBtree::Append(tree, CordRep::Ref(substr_flat));
tree = CordRepBtree::Append(tree, CordRep::Ref(substr_external));
}
for (int api = 0; api <= 3; ++api) {
absl::string_view api_scope;
std::stringstream ss;
switch (api) {
case 0:
api_scope = "Bare";
CordRepBtree::Dump(tree, ss);
break;
case 1:
api_scope = "Label only";
CordRepBtree::Dump(tree, "Once upon a label", ss);
break;
case 2:
api_scope = "Label no content";
CordRepBtree::Dump(tree, "Once upon a label", false, ss);
break;
default:
api_scope = "Label and content";
CordRepBtree::Dump(tree, "Once upon a label", true, ss);
break;
}
SCOPED_TRACE(api_scope);
std::string str = ss.str();
// Contains Node(depth) / Leaf and private / shared indicators
EXPECT_THAT(str, AllOf(HasSubstr("Node(1)"), HasSubstr("Leaf"),
HasSubstr("Private"), HasSubstr("Shared")));
// Contains length and start offset of all data edges
EXPECT_THAT(str, AllOf(HasSubstr("len = 11"), HasSubstr("len = 14"),
HasSubstr("len = 6"), HasSubstr("len = 7"),
HasSubstr("start = 1"), HasSubstr("start = 2")));
// Contains address of all data edges
EXPECT_THAT(
str, AllOf(HasSubstr(absl::StrCat("0x", absl::Hex(flat))),
HasSubstr(absl::StrCat("0x", absl::Hex(external))),
HasSubstr(absl::StrCat("0x", absl::Hex(substr_flat))),
HasSubstr(absl::StrCat("0x", absl::Hex(substr_external)))));
if (api != 0) {
// Contains label
EXPECT_THAT(str, HasSubstr("Once upon a label"));
}
if (api != 3) {
// Does not contain contents
EXPECT_THAT(str, Not(AnyOf((HasSubstr("data = \"Hello world\""),
HasSubstr("data = \"Hello external\""),
HasSubstr("data = \"ello w\""),
HasSubstr("data = \"llo ext\"")))));
} else {
// Contains contents
EXPECT_THAT(str, AllOf((HasSubstr("data = \"Hello world\""),
HasSubstr("data = \"Hello external\""),
HasSubstr("data = \"ello w\""),
HasSubstr("data = \"llo ext\""))));
}
}
CordRep::Unref(tree);
}
TEST(CordRepBtreeTest, IsValid) {
EXPECT_FALSE(CordRepBtree::IsValid(nullptr));
CordRepBtree* empty = CordRepBtree::New(0);
EXPECT_TRUE(CordRepBtree::IsValid(empty));
CordRep::Unref(empty);
for (bool as_tree : {false, true}) {
CordRepBtree* leaf = CordRepBtree::Create(MakeFlat("abc"));
CordRepBtree* tree = as_tree ? CordRepBtree::New(leaf) : nullptr;
CordRepBtree* check = as_tree ? tree : leaf;
ASSERT_TRUE(CordRepBtree::IsValid(check));
leaf->length--;
EXPECT_FALSE(CordRepBtree::IsValid(check));
leaf->length++;
ASSERT_TRUE(CordRepBtree::IsValid(check));
leaf->tag--;
EXPECT_FALSE(CordRepBtree::IsValid(check));
leaf->tag++;
// Height
ASSERT_TRUE(CordRepBtree::IsValid(check));
leaf->storage[0] = static_cast<uint8_t>(CordRepBtree::kMaxHeight + 1);
EXPECT_FALSE(CordRepBtree::IsValid(check));
leaf->storage[0] = 1;
EXPECT_FALSE(CordRepBtree::IsValid(check));
leaf->storage[0] = 0;
// Begin
ASSERT_TRUE(CordRepBtree::IsValid(check));
const uint8_t begin = leaf->storage[1];
leaf->storage[1] = static_cast<uint8_t>(CordRepBtree::kMaxCapacity);
EXPECT_FALSE(CordRepBtree::IsValid(check));
leaf->storage[1] = 2;
EXPECT_FALSE(CordRepBtree::IsValid(check));
leaf->storage[1] = begin;
// End
ASSERT_TRUE(CordRepBtree::IsValid(check));
const uint8_t end = leaf->storage[2];
leaf->storage[2] = static_cast<uint8_t>(CordRepBtree::kMaxCapacity + 1);
EXPECT_FALSE(CordRepBtree::IsValid(check));
leaf->storage[2] = end;
// DataEdge tag and value
ASSERT_TRUE(CordRepBtree::IsValid(check));
CordRep* const edge = leaf->Edges()[0];
const uint8_t tag = edge->tag;
CordRepBtreeTestPeer::SetEdge(leaf, begin, nullptr);
EXPECT_FALSE(CordRepBtree::IsValid(check));
CordRepBtreeTestPeer::SetEdge(leaf, begin, edge);
edge->tag = BTREE;
EXPECT_FALSE(CordRepBtree::IsValid(check));
edge->tag = tag;
if (as_tree) {
ASSERT_TRUE(CordRepBtree::IsValid(check));
leaf->length--;
EXPECT_FALSE(CordRepBtree::IsValid(check));
leaf->length++;
// Height
ASSERT_TRUE(CordRepBtree::IsValid(check));
tree->storage[0] = static_cast<uint8_t>(2);
EXPECT_FALSE(CordRepBtree::IsValid(check));
tree->storage[0] = 1;
// Btree edge
ASSERT_TRUE(CordRepBtree::IsValid(check));
CordRep* const edge = tree->Edges()[0];
const uint8_t tag = edge->tag;
edge->tag = FLAT;
EXPECT_FALSE(CordRepBtree::IsValid(check));
edge->tag = tag;
}
ASSERT_TRUE(CordRepBtree::IsValid(check));
CordRep::Unref(check);
}
}
TEST(CordRepBtreeTest, AssertValid) {
CordRepBtree* tree = CordRepBtree::Create(MakeFlat("abc"));
const CordRepBtree* ctree = tree;
EXPECT_THAT(CordRepBtree::AssertValid(tree), Eq(tree));
EXPECT_THAT(CordRepBtree::AssertValid(ctree), Eq(ctree));
#if defined(GTEST_HAS_DEATH_TEST)
CordRepBtree* nulltree = nullptr;
const CordRepBtree* cnulltree = nullptr;
EXPECT_DEBUG_DEATH(
EXPECT_THAT(CordRepBtree::AssertValid(nulltree), Eq(nulltree)), ".*");
EXPECT_DEBUG_DEATH(
EXPECT_THAT(CordRepBtree::AssertValid(cnulltree), Eq(cnulltree)), ".*");
tree->length--;
EXPECT_DEBUG_DEATH(EXPECT_THAT(CordRepBtree::AssertValid(tree), Eq(tree)),
".*");
EXPECT_DEBUG_DEATH(EXPECT_THAT(CordRepBtree::AssertValid(ctree), Eq(ctree)),
".*");
tree->length++;
#endif
CordRep::Unref(tree);
}
TEST(CordRepBtreeTest, CheckAssertValidShallowVsDeep) {
// Restore exhaustive validation on any exit.
const bool exhaustive_validation = IsCordBtreeExhaustiveValidationEnabled();
auto cleanup = absl::MakeCleanup([exhaustive_validation] {
SetCordBtreeExhaustiveValidation(exhaustive_validation);
});
// Create a tree of at least 2 levels, and mess with the original flat, which
// should go undetected in shallow mode as the flat is too far away, but
// should be detected in forced non-shallow mode.
CordRep* flat = MakeFlat("abc");
CordRepBtree* tree = CordRepBtree::Create(flat);
constexpr size_t max_cap = CordRepBtree::kMaxCapacity;
const size_t n = max_cap * max_cap * 2;
for (size_t i = 0; i < n; ++i) {
tree = CordRepBtree::Append(tree, MakeFlat("Hello world"));
}
flat->length = 100;
SetCordBtreeExhaustiveValidation(false);
EXPECT_FALSE(CordRepBtree::IsValid(tree));
EXPECT_TRUE(CordRepBtree::IsValid(tree, true));
EXPECT_FALSE(CordRepBtree::IsValid(tree, false));
CordRepBtree::AssertValid(tree);
CordRepBtree::AssertValid(tree, true);
#if defined(GTEST_HAS_DEATH_TEST)
EXPECT_DEBUG_DEATH(CordRepBtree::AssertValid(tree, false), ".*");
#endif
SetCordBtreeExhaustiveValidation(true);
EXPECT_FALSE(CordRepBtree::IsValid(tree));
EXPECT_FALSE(CordRepBtree::IsValid(tree, true));
EXPECT_FALSE(CordRepBtree::IsValid(tree, false));
#if defined(GTEST_HAS_DEATH_TEST)
EXPECT_DEBUG_DEATH(CordRepBtree::AssertValid(tree), ".*");
EXPECT_DEBUG_DEATH(CordRepBtree::AssertValid(tree, true), ".*");
#endif
flat->length = 3;
CordRep::Unref(tree);
}
TEST_P(CordRepBtreeTest, Rebuild) {
for (size_t size : {3u, 8u, 100u, 10000u, 1000000u}) {
SCOPED_TRACE(absl::StrCat("Rebuild @", size));
std::vector<CordRepFlat*> flats;
for (size_t i = 0; i < size; ++i) {
flats.push_back(CordRepFlat::New(2));
flats.back()->Data()[0] = 'x';
flats.back()->length = 1;
}
// Build the tree into 'right', and each so many 'split_limit' edges,
// combine 'left' + 'right' into a new 'left', and start a new 'right'.
// This guarantees we get a reasonable amount of chaos in the tree.
size_t split_count = 0;
size_t split_limit = 3;
auto it = flats.begin();
CordRepBtree* left = nullptr;
CordRepBtree* right = CordRepBtree::New(*it);
while (++it != flats.end()) {
if (++split_count >= split_limit) {
split_limit += split_limit / 16;
left = left ? CordRepBtree::Append(left, right) : right;
right = CordRepBtree::New(*it);
} else {
right = CordRepBtree::Append(right, *it);
}
}
// Finalize tree
left = left ? CordRepBtree::Append(left, right) : right;
// Rebuild
AutoUnref ref;
left = ref.Add(CordRepBtree::Rebuild(ref.RefIf(shared(), left)));
ASSERT_TRUE(CordRepBtree::IsValid(left));
// Verify we have the exact same edges in the exact same order.
bool ok = true;
it = flats.begin();
CordVisitReps(left, [&](CordRep* edge) {
if (edge->tag < FLAT) return;
ok = ok && (it != flats.end() && *it++ == edge);
});
EXPECT_TRUE(ok && it == flats.end()) << "Rebuild edges mismatch";
}
}
// Convenience helper for CordRepBtree::ExtractAppendBuffer
CordRepBtree::ExtractResult ExtractLast(CordRepBtree* input, size_t cap = 1) {
return CordRepBtree::ExtractAppendBuffer(input, cap);
}
TEST(CordRepBtreeTest, ExtractAppendBufferLeafSingleFlat) {
CordRep* flat = MakeFlat("Abc");
CordRepBtree* leaf = CordRepBtree::Create(flat);
EXPECT_THAT(ExtractLast(leaf), EqExtractResult(nullptr, flat));
CordRep::Unref(flat);
}
TEST(CordRepBtreeTest, ExtractAppendBufferNodeSingleFlat) {
CordRep* flat = MakeFlat("Abc");
CordRepBtree* leaf = CordRepBtree::Create(flat);
CordRepBtree* node = CordRepBtree::New(leaf);
EXPECT_THAT(ExtractLast(node), EqExtractResult(nullptr, flat));
CordRep::Unref(flat);
}
TEST(CordRepBtreeTest, ExtractAppendBufferLeafTwoFlats) {
std::vector<CordRep*> flats = CreateFlatsFromString("abcdef", 3);
CordRepBtree* leaf = CreateTree(flats);
EXPECT_THAT(ExtractLast(leaf), EqExtractResult(flats[0], flats[1]));
CordRep::Unref(flats[0]);
CordRep::Unref(flats[1]);
}
TEST(CordRepBtreeTest, ExtractAppendBufferNodeTwoFlats) {
std::vector<CordRep*> flats = CreateFlatsFromString("abcdef", 3);
CordRepBtree* leaf = CreateTree(flats);
CordRepBtree* node = CordRepBtree::New(leaf);
EXPECT_THAT(ExtractLast(node), EqExtractResult(flats[0], flats[1]));
CordRep::Unref(flats[0]);
CordRep::Unref(flats[1]);
}
TEST(CordRepBtreeTest, ExtractAppendBufferNodeTwoFlatsInTwoLeafs) {
std::vector<CordRep*> flats = CreateFlatsFromString("abcdef", 3);
CordRepBtree* leaf1 = CordRepBtree::Create(flats[0]);
CordRepBtree* leaf2 = CordRepBtree::Create(flats[1]);
CordRepBtree* node = CordRepBtree::New(leaf1, leaf2);
EXPECT_THAT(ExtractLast(node), EqExtractResult(flats[0], flats[1]));
CordRep::Unref(flats[0]);
CordRep::Unref(flats[1]);
}
TEST(CordRepBtreeTest, ExtractAppendBufferLeafThreeFlats) {
std::vector<CordRep*> flats = CreateFlatsFromString("abcdefghi", 3);
CordRepBtree* leaf = CreateTree(flats);
EXPECT_THAT(ExtractLast(leaf), EqExtractResult(leaf, flats[2]));
CordRep::Unref(flats[2]);
CordRep::Unref(leaf);
}
TEST(CordRepBtreeTest, ExtractAppendBufferNodeThreeFlatsRightNoFolding) {
CordRep* flat = MakeFlat("Abc");
std::vector<CordRep*> flats = CreateFlatsFromString("defghi", 3);
CordRepBtree* leaf1 = CordRepBtree::Create(flat);
CordRepBtree* leaf2 = CreateTree(flats);
CordRepBtree* node = CordRepBtree::New(leaf1, leaf2);
EXPECT_THAT(ExtractLast(node), EqExtractResult(node, flats[1]));
EXPECT_THAT(node->Edges(), ElementsAre(leaf1, leaf2));
EXPECT_THAT(leaf1->Edges(), ElementsAre(flat));
EXPECT_THAT(leaf2->Edges(), ElementsAre(flats[0]));
CordRep::Unref(node);
CordRep::Unref(flats[1]);
}
TEST(CordRepBtreeTest, ExtractAppendBufferNodeThreeFlatsRightLeafFolding) {
CordRep* flat = MakeFlat("Abc");
std::vector<CordRep*> flats = CreateFlatsFromString("defghi", 3);
CordRepBtree* leaf1 = CreateTree(flats);
CordRepBtree* leaf2 = CordRepBtree::Create(flat);
CordRepBtree* node = CordRepBtree::New(leaf1, leaf2);
EXPECT_THAT(ExtractLast(node), EqExtractResult(leaf1, flat));
EXPECT_THAT(leaf1->Edges(), ElementsAreArray(flats));
CordRep::Unref(leaf1);
CordRep::Unref(flat);
}
TEST(CordRepBtreeTest, ExtractAppendBufferNoCapacity) {
std::vector<CordRep*> flats = CreateFlatsFromString("abcdef", 3);
CordRepBtree* leaf = CreateTree(flats);
size_t avail = flats[1]->flat()->Capacity() - flats[1]->length;
EXPECT_THAT(ExtractLast(leaf, avail + 1), EqExtractResult(leaf, nullptr));
EXPECT_THAT(ExtractLast(leaf, avail), EqExtractResult(flats[0], flats[1]));
CordRep::Unref(flats[0]);
CordRep::Unref(flats[1]);
}
TEST(CordRepBtreeTest, ExtractAppendBufferNotFlat) {
std::vector<CordRep*> flats = CreateFlatsFromString("abcdef", 3);
auto substr = MakeSubstring(1, 2, flats[1]);
CordRepBtree* leaf = CreateTree({flats[0], substr});
EXPECT_THAT(ExtractLast(leaf), EqExtractResult(leaf, nullptr));
CordRep::Unref(leaf);
}
TEST(CordRepBtreeTest, ExtractAppendBufferShared) {
std::vector<CordRep*> flats = CreateFlatsFromString("abcdef", 3);
CordRepBtree* leaf = CreateTree(flats);
CordRep::Ref(flats[1]);
EXPECT_THAT(ExtractLast(leaf), EqExtractResult(leaf, nullptr));
CordRep::Unref(flats[1]);
CordRep::Ref(leaf);
EXPECT_THAT(ExtractLast(leaf), EqExtractResult(leaf, nullptr));
CordRep::Unref(leaf);
CordRepBtree* node = CordRepBtree::New(leaf);
CordRep::Ref(node);
EXPECT_THAT(ExtractLast(node), EqExtractResult(node, nullptr));
CordRep::Unref(node);
CordRep::Unref(node);
}
} // namespace
} // namespace cord_internal
ABSL_NAMESPACE_END
} // namespace absl