// 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_navigator.h" #include #include #include "gmock/gmock.h" #include "gtest/gtest.h" #include "absl/base/config.h" #include "absl/base/internal/raw_logging.h" #include "absl/strings/internal/cord_internal.h" #include "absl/strings/internal/cord_rep_btree.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 { namespace { using ::testing::Eq; using ::testing::Ne; using ::absl::cordrep_testing::CordRepBtreeFromFlats; using ::absl::cordrep_testing::CordToString; using ::absl::cordrep_testing::CreateFlatsFromString; using ::absl::cordrep_testing::CreateRandomString; using ::absl::cordrep_testing::MakeFlat; using ::absl::cordrep_testing::MakeSubstring; using ReadResult = CordRepBtreeNavigator::ReadResult; using Position = CordRepBtreeNavigator::Position; // CordRepBtreeNavigatorTest is a test fixture which automatically creates a // tree to test navigation logic on. The parameter `count' defines the number of // data edges in the test tree. class CordRepBtreeNavigatorTest : public testing::TestWithParam { public: using Flats = std::vector; static constexpr size_t kCharsPerFlat = 3; CordRepBtreeNavigatorTest() { data_ = CreateRandomString(count() * kCharsPerFlat); flats_ = CreateFlatsFromString(data_, kCharsPerFlat); // Turn flat 0 or 1 into a substring to cover partial reads on substrings. if (count() > 1) { CordRep::Unref(flats_[1]); flats_[1] = MakeSubstring(kCharsPerFlat, kCharsPerFlat, MakeFlat(data_)); } else { CordRep::Unref(flats_[0]); flats_[0] = MakeSubstring(0, kCharsPerFlat, MakeFlat(data_)); } tree_ = CordRepBtreeFromFlats(flats_); } ~CordRepBtreeNavigatorTest() override { CordRep::Unref(tree_); } size_t count() const { return GetParam(); } CordRepBtree* tree() { return tree_; } const std::string& data() const { return data_; } const std::vector& flats() const { return flats_; } static std::string ToString(testing::TestParamInfo param) { return absl::StrCat(param.param, "_Flats"); } private: std::string data_; Flats flats_; CordRepBtree* tree_; }; INSTANTIATE_TEST_SUITE_P( WithParam, CordRepBtreeNavigatorTest, testing::Values(1, CordRepBtree::kMaxCapacity - 1, CordRepBtree::kMaxCapacity, CordRepBtree::kMaxCapacity* CordRepBtree::kMaxCapacity - 1, CordRepBtree::kMaxCapacity* CordRepBtree::kMaxCapacity, CordRepBtree::kMaxCapacity* CordRepBtree::kMaxCapacity + 1, CordRepBtree::kMaxCapacity* CordRepBtree::kMaxCapacity * 2 + 17), CordRepBtreeNavigatorTest::ToString); TEST(CordRepBtreeNavigatorTest, Uninitialized) { CordRepBtreeNavigator nav; EXPECT_FALSE(nav); EXPECT_THAT(nav.btree(), Eq(nullptr)); #if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG) EXPECT_DEATH(nav.Current(), ".*"); #endif } TEST_P(CordRepBtreeNavigatorTest, InitFirst) { CordRepBtreeNavigator nav; CordRep* edge = nav.InitFirst(tree()); EXPECT_TRUE(nav); EXPECT_THAT(nav.btree(), Eq(tree())); EXPECT_THAT(nav.Current(), Eq(flats().front())); EXPECT_THAT(edge, Eq(flats().front())); } TEST_P(CordRepBtreeNavigatorTest, InitLast) { CordRepBtreeNavigator nav; CordRep* edge = nav.InitLast(tree()); EXPECT_TRUE(nav); EXPECT_THAT(nav.btree(), Eq(tree())); EXPECT_THAT(nav.Current(), Eq(flats().back())); EXPECT_THAT(edge, Eq(flats().back())); } TEST_P(CordRepBtreeNavigatorTest, NextPrev) { CordRepBtreeNavigator nav; nav.InitFirst(tree()); const Flats& flats = this->flats(); EXPECT_THAT(nav.Previous(), Eq(nullptr)); EXPECT_THAT(nav.Current(), Eq(flats.front())); for (size_t i = 1; i < flats.size(); ++i) { ASSERT_THAT(nav.Next(), Eq(flats[i])); EXPECT_THAT(nav.Current(), Eq(flats[i])); } EXPECT_THAT(nav.Next(), Eq(nullptr)); EXPECT_THAT(nav.Current(), Eq(flats.back())); for (size_t i = flats.size() - 1; i > 0; --i) { ASSERT_THAT(nav.Previous(), Eq(flats[i - 1])); EXPECT_THAT(nav.Current(), Eq(flats[i - 1])); } EXPECT_THAT(nav.Previous(), Eq(nullptr)); EXPECT_THAT(nav.Current(), Eq(flats.front())); } TEST_P(CordRepBtreeNavigatorTest, PrevNext) { CordRepBtreeNavigator nav; nav.InitLast(tree()); const Flats& flats = this->flats(); EXPECT_THAT(nav.Next(), Eq(nullptr)); EXPECT_THAT(nav.Current(), Eq(flats.back())); for (size_t i = flats.size() - 1; i > 0; --i) { ASSERT_THAT(nav.Previous(), Eq(flats[i - 1])); EXPECT_THAT(nav.Current(), Eq(flats[i - 1])); } EXPECT_THAT(nav.Previous(), Eq(nullptr)); EXPECT_THAT(nav.Current(), Eq(flats.front())); for (size_t i = 1; i < flats.size(); ++i) { ASSERT_THAT(nav.Next(), Eq(flats[i])); EXPECT_THAT(nav.Current(), Eq(flats[i])); } EXPECT_THAT(nav.Next(), Eq(nullptr)); EXPECT_THAT(nav.Current(), Eq(flats.back())); } TEST(CordRepBtreeNavigatorTest, Reset) { CordRepBtree* tree = CordRepBtree::Create(MakeFlat("abc")); CordRepBtreeNavigator nav; nav.InitFirst(tree); nav.Reset(); EXPECT_FALSE(nav); EXPECT_THAT(nav.btree(), Eq(nullptr)); #if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG) EXPECT_DEATH(nav.Current(), ".*"); #endif CordRep::Unref(tree); } TEST_P(CordRepBtreeNavigatorTest, Skip) { size_t count = this->count(); const Flats& flats = this->flats(); CordRepBtreeNavigator nav; nav.InitFirst(tree()); for (size_t char_offset = 0; char_offset < kCharsPerFlat; ++char_offset) { Position pos = nav.Skip(char_offset); EXPECT_THAT(pos.edge, Eq(nav.Current())); EXPECT_THAT(pos.edge, Eq(flats[0])); EXPECT_THAT(pos.offset, Eq(char_offset)); } for (size_t index1 = 0; index1 < count; ++index1) { for (size_t index2 = index1; index2 < count; ++index2) { for (size_t char_offset = 0; char_offset < kCharsPerFlat; ++char_offset) { CordRepBtreeNavigator nav; nav.InitFirst(tree()); size_t length1 = index1 * kCharsPerFlat; Position pos1 = nav.Skip(length1 + char_offset); ASSERT_THAT(pos1.edge, Eq(flats[index1])); ASSERT_THAT(pos1.edge, Eq(nav.Current())); ASSERT_THAT(pos1.offset, Eq(char_offset)); size_t length2 = index2 * kCharsPerFlat; Position pos2 = nav.Skip(length2 - length1 + char_offset); ASSERT_THAT(pos2.edge, Eq(flats[index2])); ASSERT_THAT(pos2.edge, Eq(nav.Current())); ASSERT_THAT(pos2.offset, Eq(char_offset)); } } } } TEST_P(CordRepBtreeNavigatorTest, Seek) { size_t count = this->count(); const Flats& flats = this->flats(); CordRepBtreeNavigator nav; nav.InitFirst(tree()); for (size_t char_offset = 0; char_offset < kCharsPerFlat; ++char_offset) { Position pos = nav.Seek(char_offset); EXPECT_THAT(pos.edge, Eq(nav.Current())); EXPECT_THAT(pos.edge, Eq(flats[0])); EXPECT_THAT(pos.offset, Eq(char_offset)); } for (size_t index = 0; index < count; ++index) { for (size_t char_offset = 0; char_offset < kCharsPerFlat; ++char_offset) { size_t offset = index * kCharsPerFlat + char_offset; Position pos1 = nav.Seek(offset); ASSERT_THAT(pos1.edge, Eq(flats[index])); ASSERT_THAT(pos1.edge, Eq(nav.Current())); ASSERT_THAT(pos1.offset, Eq(char_offset)); } } } TEST(CordRepBtreeNavigatorTest, InitOffset) { // Whitebox: InitOffset() is implemented in terms of Seek() which is // exhaustively tested. Only test it initializes / forwards properly.. CordRepBtree* tree = CordRepBtree::Create(MakeFlat("abc")); tree = CordRepBtree::Append(tree, MakeFlat("def")); CordRepBtreeNavigator nav; Position pos = nav.InitOffset(tree, 5); EXPECT_TRUE(nav); EXPECT_THAT(nav.btree(), Eq(tree)); EXPECT_THAT(pos.edge, Eq(tree->Edges()[1])); EXPECT_THAT(pos.edge, Eq(nav.Current())); EXPECT_THAT(pos.offset, Eq(2u)); CordRep::Unref(tree); } TEST(CordRepBtreeNavigatorTest, InitOffsetAndSeekBeyondLength) { CordRepBtree* tree1 = CordRepBtree::Create(MakeFlat("abc")); CordRepBtree* tree2 = CordRepBtree::Create(MakeFlat("def")); CordRepBtreeNavigator nav; nav.InitFirst(tree1); EXPECT_THAT(nav.Seek(3).edge, Eq(nullptr)); EXPECT_THAT(nav.Seek(100).edge, Eq(nullptr)); EXPECT_THAT(nav.btree(), Eq(tree1)); EXPECT_THAT(nav.Current(), Eq(tree1->Edges().front())); EXPECT_THAT(nav.InitOffset(tree2, 3).edge, Eq(nullptr)); EXPECT_THAT(nav.InitOffset(tree2, 100).edge, Eq(nullptr)); EXPECT_THAT(nav.btree(), Eq(tree1)); EXPECT_THAT(nav.Current(), Eq(tree1->Edges().front())); CordRep::Unref(tree1); CordRep::Unref(tree2); } TEST_P(CordRepBtreeNavigatorTest, Read) { const Flats& flats = this->flats(); const std::string& data = this->data(); for (size_t offset = 0; offset < data.size(); ++offset) { for (size_t length = 1; length <= data.size() - offset; ++length) { CordRepBtreeNavigator nav; nav.InitFirst(tree()); // Skip towards edge holding offset size_t edge_offset = nav.Skip(offset).offset; // Read node ReadResult result = nav.Read(edge_offset, length); ASSERT_THAT(result.tree, Ne(nullptr)); EXPECT_THAT(result.tree->length, Eq(length)); if (result.tree->tag == BTREE) { ASSERT_TRUE(CordRepBtree::IsValid(result.tree->btree())); } // Verify contents std::string value = CordToString(result.tree); EXPECT_THAT(value, Eq(data.substr(offset, length))); // Verify 'partial last edge' reads. size_t partial = (offset + length) % kCharsPerFlat; ASSERT_THAT(result.n, Eq(partial)); // Verify ending position if not EOF if (offset + length < data.size()) { size_t index = (offset + length) / kCharsPerFlat; EXPECT_THAT(nav.Current(), Eq(flats[index])); } CordRep::Unref(result.tree); } } } TEST_P(CordRepBtreeNavigatorTest, ReadBeyondLengthOfTree) { CordRepBtreeNavigator nav; nav.InitFirst(tree()); ReadResult result = nav.Read(2, tree()->length); ASSERT_THAT(result.tree, Eq(nullptr)); } TEST(CordRepBtreeNavigatorTest, NavigateMaximumTreeDepth) { CordRepFlat* flat1 = MakeFlat("Hello world"); CordRepFlat* flat2 = MakeFlat("World Hello"); CordRepBtree* node = CordRepBtree::Create(flat1); node = CordRepBtree::Append(node, flat2); while (node->height() < CordRepBtree::kMaxHeight) { node = CordRepBtree::New(node); } CordRepBtreeNavigator nav; CordRep* edge = nav.InitFirst(node); EXPECT_THAT(edge, Eq(flat1)); EXPECT_THAT(nav.Next(), Eq(flat2)); EXPECT_THAT(nav.Next(), Eq(nullptr)); EXPECT_THAT(nav.Previous(), Eq(flat1)); EXPECT_THAT(nav.Previous(), Eq(nullptr)); CordRep::Unref(node); } } // namespace } // namespace cord_internal ABSL_NAMESPACE_END } // namespace absl