| // Copyright 2017-2020 The Verible 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 |
| // |
| // http://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 "common/util/vector_tree.h" |
| |
| #include <cstddef> |
| #include <iterator> |
| #include <sstream> |
| #include <string> |
| #include <utility> |
| #include <vector> |
| |
| #include "gmock/gmock.h" |
| #include "gtest/gtest.h" |
| #include "absl/strings/str_cat.h" |
| #include "absl/strings/str_join.h" |
| #include "absl/strings/string_view.h" |
| #include "common/util/vector_tree_test_util.h" |
| |
| namespace verible { |
| namespace { |
| |
| using ::testing::ElementsAre; |
| using verible::testing::MakePath; |
| using verible::testing::NamedInterval; |
| using verible::testing::VectorTreeTestType; |
| |
| template <class Tree> |
| void ExpectPath(const Tree& tree, absl::string_view expect) { |
| std::ostringstream stream; |
| stream << NodePath(tree); |
| EXPECT_EQ(stream.str(), expect); |
| } |
| |
| // Test that basic Tree construction works on a singleton node. |
| TEST(VectorTreeTest, RootOnly) { |
| const VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree()); |
| EXPECT_TRUE(tree.Children().empty()); |
| EXPECT_EQ(tree.Parent(), nullptr); |
| EXPECT_EQ(tree.NumAncestors(), 0); |
| EXPECT_EQ(tree.BirthRank(), 0); // no parent |
| EXPECT_TRUE(tree.IsFirstChild()); |
| EXPECT_TRUE(tree.IsLastChild()); |
| EXPECT_EQ(tree.Root(), &tree); |
| |
| const auto& value = tree.Value(); |
| EXPECT_EQ(value.left, 0); |
| EXPECT_EQ(value.right, 2); |
| EXPECT_EQ(value.name, "root"); |
| |
| ExpectPath(tree, "{}"); |
| } |
| |
| TEST(VectorTreeTest, RootOnlyDescendants) { |
| VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree()); |
| EXPECT_EQ(tree.LeftmostDescendant(), &tree); |
| EXPECT_EQ(tree.RightmostDescendant(), &tree); |
| { // Test const method variants. |
| const auto& ctree(tree); |
| EXPECT_EQ(ctree.LeftmostDescendant(), &ctree); |
| EXPECT_EQ(ctree.RightmostDescendant(), &ctree); |
| } |
| } |
| |
| TEST(VectorTreeTest, RootOnlyContainsAncestor) { |
| VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree()); |
| EXPECT_FALSE(tree.ContainsAncestor(nullptr)); |
| EXPECT_FALSE(tree.ContainsAncestor(&tree)); |
| |
| // Separate tree |
| VectorTreeTestType tree2(verible::testing::MakeRootOnlyExampleTree()); |
| EXPECT_FALSE(tree2.ContainsAncestor(&tree)); |
| EXPECT_FALSE(tree.ContainsAncestor(&tree2)); |
| } |
| |
| TEST(VectorTreeTest, RootOnlyLeafIteration) { |
| VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree()); |
| EXPECT_EQ(tree.NextLeaf(), nullptr); |
| EXPECT_EQ(tree.PreviousLeaf(), nullptr); |
| { // const method variants |
| const auto& ctree(tree); |
| EXPECT_EQ(ctree.NextLeaf(), nullptr); |
| EXPECT_EQ(ctree.PreviousLeaf(), nullptr); |
| } |
| } |
| |
| TEST(VectorTreeTest, RootOnlySiblingIteration) { |
| VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree()); |
| EXPECT_EQ(tree.NextSibling(), nullptr); |
| EXPECT_EQ(tree.PreviousSibling(), nullptr); |
| { // const method variants |
| const auto& ctree(tree); |
| EXPECT_EQ(ctree.NextSibling(), nullptr); |
| EXPECT_EQ(ctree.PreviousSibling(), nullptr); |
| } |
| } |
| |
| TEST(VectorTreeTest, CopyAssignEmpty) { |
| typedef VectorTree<int> tree_type; |
| const tree_type tree(1); // Root only tree. |
| const tree_type expected(1); |
| tree_type tree2(5); |
| tree2 = tree; |
| { |
| const auto result_pair = DeepEqual(tree2, expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| { // verify original copy |
| const auto result_pair = DeepEqual(tree, expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| } |
| |
| TEST(VectorTreeTest, CopyAssignDeep) { |
| typedef VectorTree<int> tree_type; |
| const tree_type tree(1, |
| tree_type(2, tree_type(3, tree_type(4, tree_type(5))))); |
| const tree_type expected( |
| 1, tree_type(2, tree_type(3, tree_type(4, tree_type(5))))); |
| tree_type tree2(6); |
| tree2 = tree; |
| { |
| const auto result_pair = DeepEqual(tree2, expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| { // verify original copy |
| const auto result_pair = DeepEqual(tree, expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| } |
| |
| TEST(VectorTreeTest, CopyInitializeEmpty) { |
| typedef VectorTree<int> tree_type; |
| const tree_type tree(1); // Root only tree. |
| const tree_type expected(1); |
| tree_type tree2 = tree; |
| { |
| const auto result_pair = DeepEqual(tree2, expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| { // verify original copy |
| const auto result_pair = DeepEqual(tree, expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| } |
| |
| TEST(VectorTreeTest, CopyInitializeDeep) { |
| typedef VectorTree<int> tree_type; |
| const tree_type tree(1, |
| tree_type(2, tree_type(3, tree_type(4, tree_type(5))))); |
| const tree_type expected( |
| 1, tree_type(2, tree_type(3, tree_type(4, tree_type(5))))); |
| tree_type tree2 = tree; |
| { |
| const auto result_pair = DeepEqual(tree2, expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| { // verify original copy |
| const auto result_pair = DeepEqual(tree, expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| } |
| |
| TEST(VectorTreeTest, MoveInitializeEmpty) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1); // Root only tree. |
| const tree_type expected(1); |
| tree_type tree2 = std::move(tree); |
| const auto result_pair = DeepEqual(tree2, expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, MoveInitializeDeep) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, tree_type(2, tree_type(3, tree_type(4, tree_type(5))))); |
| const tree_type expected( |
| 1, tree_type(2, tree_type(3, tree_type(4, tree_type(5))))); |
| tree_type tree2 = std::move(tree); |
| const auto result_pair = DeepEqual(tree2, expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, MoveAssignEmpty) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1); // Root only tree. |
| const tree_type expected(1); |
| tree_type tree2(2); |
| VLOG(4) << "about to move."; |
| tree2 = std::move(tree); |
| VLOG(4) << "done moving."; |
| const auto result_pair = DeepEqual(tree2, expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, MoveAssignDeep) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, tree_type(2, tree_type(3, tree_type(4, tree_type(5))))); |
| tree_type tree2(7, tree_type(8, tree_type(9))); |
| tree2 = std::move(tree); |
| const tree_type expected( |
| 1, tree_type(2, tree_type(3, tree_type(4, tree_type(5))))); |
| const auto result_pair = DeepEqual(tree2, expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, SwapUnrelatedRoots) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, tree_type(2, tree_type(3, tree_type(4, tree_type(5))))); |
| tree_type tree2(7, tree_type(8, tree_type(9))); |
| const tree_type t1_expected(tree2); // deep-copy |
| const tree_type t2_expected(tree); // deep-copy |
| swap(tree, tree2); // verible::swap, using ADL |
| { |
| const auto result_pair = DeepEqual(tree, t1_expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| { |
| const auto result_pair = DeepEqual(tree2, t2_expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| } |
| |
| TEST(VectorTreeTest, SwapUnrelatedSubtrees) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, tree_type(2, tree_type(3, tree_type(4, tree_type(5))))); |
| tree_type tree2(7, tree_type(8, tree_type(9, tree_type(10)))); |
| swap(tree.Children()[0], tree2.Children()[0]); |
| { |
| const tree_type expected(1, tree_type(8, tree_type(9, tree_type(10)))); |
| const auto result_pair = DeepEqual(tree, expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| { |
| const tree_type expected( |
| 7, tree_type(2, tree_type(3, tree_type(4, tree_type(5))))); |
| const auto result_pair = DeepEqual(tree2, expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| } |
| |
| TEST(VectorTreeTest, SwapSiblings) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(0), |
| tree_type(2, tree_type(3, tree_type(4, tree_type(5)))), |
| tree_type(7, tree_type(8, tree_type(9))), tree_type(11)); |
| swap(tree.Children()[2], tree.Children()[1]); |
| |
| const tree_type expected( |
| 1, // |
| tree_type(0), tree_type(7, tree_type(8, tree_type(9))), |
| tree_type(2, tree_type(3, tree_type(4, tree_type(5)))), tree_type(11)); |
| const auto result_pair = DeepEqual(tree, expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, SwapDistantCousins) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(0), |
| tree_type(2, tree_type(3, tree_type(4, tree_type(5)))), |
| tree_type(7, tree_type(8, tree_type(9))), tree_type(11)); |
| swap(tree.Children()[2], tree.Children()[1].Children()[0]); |
| |
| const tree_type expected( |
| 1, // |
| tree_type(0), tree_type(2, tree_type(7, tree_type(8, tree_type(9)))), |
| tree_type(3, tree_type(4, tree_type(5))), tree_type(11)); |
| const auto result_pair = DeepEqual(tree, expected); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, StructureEqualRootToRoot) { |
| const VectorTreeTestType ltree(verible::testing::MakeRootOnlyExampleTree()); |
| const VectorTreeTestType rtree(verible::testing::MakeRootOnlyExampleTree()); |
| const auto result_pair = StructureEqual(ltree, rtree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, StructureEqualRootToRootIgnoringValue) { |
| VectorTreeTestType ltree(verible::testing::MakeRootOnlyExampleTree()); |
| VectorTreeTestType rtree(verible::testing::MakeRootOnlyExampleTree()); |
| ltree.Value().left = 11; |
| rtree.Value().left = 34; |
| const auto result_pair = StructureEqual(ltree, rtree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, DeepEqualRootToRoot) { |
| const VectorTreeTestType ltree(verible::testing::MakeRootOnlyExampleTree()); |
| const VectorTreeTestType rtree(verible::testing::MakeRootOnlyExampleTree()); |
| const auto result_pair = DeepEqual(ltree, rtree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, DeepEqualRootToRootValueDifferent) { |
| VectorTreeTestType ltree(verible::testing::MakeRootOnlyExampleTree()); |
| VectorTreeTestType rtree(verible::testing::MakeRootOnlyExampleTree()); |
| ltree.Value().left = 11; |
| rtree.Value().left = 34; |
| const auto result_pair = DeepEqual(ltree, rtree); |
| EXPECT_EQ(result_pair.left, <ree); |
| EXPECT_EQ(result_pair.right, &rtree); |
| } |
| |
| struct NameOnly { |
| absl::string_view name; |
| |
| explicit NameOnly(const NamedInterval& v) : name(v.name) {} |
| }; |
| |
| std::ostream& operator<<(std::ostream& stream, const NameOnly& n) { |
| return stream << '(' << n.name << ")\n"; |
| } |
| |
| static NameOnly NameOnlyConverter(const VectorTreeTestType& node) { |
| return NameOnly(node.Value()); |
| } |
| |
| // Heterogeneous comparison. |
| bool operator==(const NamedInterval& left, const NameOnly& right) { |
| return left.name == right.name; |
| } |
| |
| TEST(VectorTreeTest, RootOnlyTreeTransformConstruction) { |
| const VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree()); |
| const auto other_tree = tree.Transform<NameOnly>(NameOnlyConverter); |
| EXPECT_TRUE(other_tree.Children().empty()); |
| EXPECT_EQ(other_tree.Parent(), nullptr); |
| EXPECT_EQ(other_tree.NumAncestors(), 0); |
| EXPECT_EQ(other_tree.BirthRank(), 0); // no parent |
| |
| const auto& value = other_tree.Value(); |
| EXPECT_EQ(value.name, "root"); |
| } |
| |
| TEST(VectorTreeTest, RootOnlyTreeTransformComparisonMatches) { |
| const VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree()); |
| const auto other_tree = tree.Transform<NameOnly>(NameOnlyConverter); |
| { |
| const auto result_pair = StructureEqual(tree, other_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| { |
| const auto result_pair = StructureEqual(other_tree, tree); // swapped |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| { |
| // Uses hetergeneous value comparison. |
| const auto result_pair = DeepEqual(tree, other_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| } |
| |
| TEST(VectorTreeTest, RootOnlyTreeTransformComparisonDiffer) { |
| const VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree()); |
| auto other_tree = tree.Transform<NameOnly>(NameOnlyConverter); |
| other_tree.Value().name = "groot"; |
| { |
| const auto result_pair = StructureEqual(tree, other_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| { |
| // Uses hetergeneous value comparison. |
| const auto result_pair = DeepEqual(tree, other_tree); |
| EXPECT_EQ(result_pair.left, &tree); |
| EXPECT_EQ(result_pair.right, &other_tree); |
| } |
| } |
| |
| TEST(VectorTreeTest, NewChild) { |
| VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree()); |
| { |
| auto* child = tree.NewChild(NamedInterval(1, 2, "child")); |
| EXPECT_EQ(child->Parent(), &tree); |
| EXPECT_EQ(child->Root(), &tree); |
| EXPECT_TRUE(child->Children().empty()); |
| |
| const auto& value(child->Value()); |
| EXPECT_EQ(value.left, 1); |
| EXPECT_EQ(value.right, 2); |
| EXPECT_EQ(value.name, "child"); |
| |
| ExpectPath(*child, "{0}"); |
| } |
| { |
| auto* child = tree.NewChild(NamedInterval(2, 3, "lil-bro")); |
| EXPECT_EQ(child->Parent(), &tree); |
| EXPECT_EQ(child->Root(), &tree); |
| EXPECT_TRUE(child->Children().empty()); |
| |
| const auto& value(child->Value()); |
| EXPECT_EQ(value.left, 2); |
| EXPECT_EQ(value.right, 3); |
| EXPECT_EQ(value.name, "lil-bro"); |
| // Note: first child may have moved due to realloc |
| |
| ExpectPath(*child, "{1}"); |
| } |
| } |
| |
| TEST(VectorTreeTest, NewSibling) { |
| VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree()); |
| { |
| auto* first_child = tree.NewChild(NamedInterval(1, 2, "child")); |
| ExpectPath(*first_child, "{0}"); |
| |
| auto* second_child = |
| first_child->NewSibling(NamedInterval(2, 3, "lil-bro")); |
| // Recall that NewSibling() may invalidate reference to first_child. |
| EXPECT_EQ(second_child->Parent(), &tree); |
| EXPECT_EQ(second_child->Root(), &tree); |
| EXPECT_TRUE(second_child->Children().empty()); |
| |
| const auto& value(second_child->Value()); |
| EXPECT_EQ(value.left, 2); |
| EXPECT_EQ(value.right, 3); |
| EXPECT_EQ(value.name, "lil-bro"); |
| |
| ExpectPath(*second_child, "{1}"); |
| } |
| } |
| |
| TEST(VectorTreeTest, OneChildPolicy) { |
| const auto tree = verible::testing::MakeOneChildPolicyExampleTree(); |
| EXPECT_EQ(tree.Parent(), nullptr); |
| EXPECT_FALSE(tree.Children().empty()); |
| |
| const auto& value = tree.Value(); |
| EXPECT_EQ(value.left, 0); |
| EXPECT_EQ(value.right, 3); |
| EXPECT_EQ(value.name, "root"); |
| |
| { |
| const auto& child = tree.Children().front(); |
| EXPECT_EQ(child.Parent(), &tree); |
| EXPECT_EQ(child.Root(), &tree); |
| EXPECT_FALSE(child.Children().empty()); |
| EXPECT_EQ(child.NumAncestors(), 1); |
| EXPECT_EQ(child.BirthRank(), 0); |
| EXPECT_TRUE(child.IsFirstChild()); |
| EXPECT_TRUE(child.IsLastChild()); |
| |
| const auto& cvalue = child.Value(); |
| EXPECT_EQ(cvalue.left, 0); |
| EXPECT_EQ(cvalue.right, 3); |
| EXPECT_EQ(cvalue.name, "gen1"); |
| ExpectPath(child, "{0}"); |
| |
| EXPECT_EQ(child.NextSibling(), nullptr); |
| EXPECT_EQ(child.PreviousSibling(), nullptr); |
| |
| // The invoking node need not be a leaf. |
| EXPECT_EQ(child.NextLeaf(), nullptr); |
| EXPECT_EQ(child.PreviousLeaf(), nullptr); |
| |
| { |
| const auto& grandchild = child.Children().front(); |
| EXPECT_EQ(grandchild.Parent(), &child); |
| EXPECT_EQ(grandchild.Root(), &tree); |
| EXPECT_TRUE(grandchild.Children().empty()); |
| EXPECT_EQ(grandchild.NumAncestors(), 2); |
| EXPECT_EQ(grandchild.BirthRank(), 0); |
| EXPECT_TRUE(grandchild.IsFirstChild()); |
| EXPECT_TRUE(grandchild.IsLastChild()); |
| |
| const auto& gcvalue = grandchild.Value(); |
| EXPECT_EQ(gcvalue.left, 0); |
| EXPECT_EQ(gcvalue.right, 3); |
| EXPECT_EQ(gcvalue.name, "gen2"); |
| ExpectPath(grandchild, "{0,0}"); |
| |
| // As the ancestry chain is linear, Leftmost == Rightmost. |
| EXPECT_EQ(child.LeftmostDescendant(), &grandchild); |
| EXPECT_EQ(child.RightmostDescendant(), &grandchild); |
| EXPECT_EQ(tree.LeftmostDescendant(), &grandchild); |
| EXPECT_EQ(tree.RightmostDescendant(), &grandchild); |
| |
| EXPECT_EQ(grandchild.NextSibling(), nullptr); |
| EXPECT_EQ(grandchild.PreviousSibling(), nullptr); |
| |
| // There is still only a single leaf in a one-child tree, |
| // thus next and previous do not exist. |
| EXPECT_EQ(grandchild.NextLeaf(), nullptr); |
| EXPECT_EQ(grandchild.PreviousLeaf(), nullptr); |
| } |
| } |
| } |
| |
| TEST(VectorTreeTest, OneChildPolicyContainsAncestor) { |
| const auto tree = verible::testing::MakeOneChildPolicyExampleTree(); |
| |
| { |
| const auto& child = tree.Children().front(); |
| |
| EXPECT_FALSE(tree.ContainsAncestor(&child)); |
| EXPECT_TRUE(child.ContainsAncestor(&tree)); |
| |
| { |
| const auto& grandchild = child.Children().front(); |
| |
| EXPECT_FALSE(child.ContainsAncestor(&grandchild)); |
| EXPECT_TRUE(grandchild.ContainsAncestor(&child)); |
| |
| EXPECT_FALSE(tree.ContainsAncestor(&grandchild)); |
| EXPECT_TRUE(grandchild.ContainsAncestor(&tree)); |
| } |
| } |
| } |
| |
| TEST(VectorTreeTest, StructureEqualOneChild) { |
| const VectorTreeTestType ltree( |
| verible::testing::MakeOneChildPolicyExampleTree()); |
| const VectorTreeTestType rtree( |
| verible::testing::MakeOneChildPolicyExampleTree()); |
| const auto result_pair = StructureEqual(ltree, rtree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, StructureEqualOneChildIgnoreValues) { |
| VectorTreeTestType ltree(verible::testing::MakeOneChildPolicyExampleTree()); |
| VectorTreeTestType rtree(verible::testing::MakeOneChildPolicyExampleTree()); |
| ltree.Children()[0].Value().right = 32; |
| rtree.Children()[0].Value().right = 77; |
| const auto result_pair = StructureEqual(ltree, rtree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, DeepEqualOneChild) { |
| const VectorTreeTestType ltree( |
| verible::testing::MakeOneChildPolicyExampleTree()); |
| const VectorTreeTestType rtree( |
| verible::testing::MakeOneChildPolicyExampleTree()); |
| const auto result_pair = DeepEqual(ltree, rtree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, DeepEqualOneChildDifferentChildValues) { |
| VectorTreeTestType ltree(verible::testing::MakeOneChildPolicyExampleTree()); |
| VectorTreeTestType rtree(verible::testing::MakeOneChildPolicyExampleTree()); |
| auto& lchild = ltree.Children()[0]; |
| auto& rchild = rtree.Children()[0]; |
| lchild.Value().right = 32; |
| rchild.Value().right = 77; |
| const auto result_pair = DeepEqual(ltree, rtree); |
| EXPECT_EQ(result_pair.left, &lchild); |
| EXPECT_EQ(result_pair.right, &rchild); |
| } |
| |
| TEST(VectorTreeTest, DeepEqualOneChildDifferentGrandchildValues) { |
| VectorTreeTestType ltree(verible::testing::MakeOneChildPolicyExampleTree()); |
| VectorTreeTestType rtree(verible::testing::MakeOneChildPolicyExampleTree()); |
| auto& lchild = ltree.Children()[0].Children()[0]; // only grandchild |
| auto& rchild = rtree.Children()[0].Children()[0]; // only grandchild |
| lchild.Value().right = 32; |
| rchild.Value().right = 77; |
| const auto result_pair = DeepEqual(ltree, rtree); |
| EXPECT_EQ(result_pair.left, &lchild); |
| EXPECT_EQ(result_pair.right, &rchild); |
| } |
| |
| TEST(VectorTreeTest, DeepEqualOneChildGrandchildValuesHeterogeneous) { |
| VectorTreeTestType ltree(verible::testing::MakeOneChildPolicyExampleTree()); |
| auto rtree = ltree.Transform<NameOnly>(NameOnlyConverter); |
| { // Match |
| const auto result_pair = DeepEqual(ltree, rtree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| { // Mismatch |
| const std::vector<size_t> path({0, 0}); // only grandchild |
| auto& lchild = ltree.DescendPath(path.begin(), path.end()); |
| auto& rchild = rtree.DescendPath(path.begin(), path.end()); |
| lchild.Value().name = "alex"; |
| rchild.Value().name = "james"; |
| const auto result_pair = DeepEqual(ltree, rtree); |
| EXPECT_EQ(result_pair.left, &lchild); |
| EXPECT_EQ(result_pair.right, &rchild); |
| } |
| } |
| |
| template <typename T> |
| void VerifyFamilyTree(const VectorTree<T>& tree) { |
| EXPECT_EQ(tree.Parent(), nullptr); |
| EXPECT_EQ(tree.Root(), &tree); |
| EXPECT_FALSE(tree.Children().empty()); |
| EXPECT_EQ(tree.NumAncestors(), 0); |
| EXPECT_EQ(tree.BirthRank(), 0); |
| |
| const auto tree_path = MakePath(tree); |
| EXPECT_TRUE(tree_path.empty()); |
| EXPECT_EQ(&tree.DescendPath(tree_path.begin(), tree_path.end()), &tree); |
| |
| for (int i = 0; i < 2; ++i) { |
| const auto& child = tree.Children()[i]; |
| EXPECT_EQ(child.Parent(), &tree); |
| EXPECT_EQ(child.Root(), &tree); |
| EXPECT_FALSE(child.Children().empty()); |
| EXPECT_EQ(child.NumAncestors(), 1); |
| EXPECT_EQ(child.BirthRank(), i); |
| EXPECT_EQ(child.IsFirstChild(), i == 0); |
| EXPECT_EQ(child.IsLastChild(), i == 1); |
| |
| const auto child_path = MakePath(child); |
| EXPECT_THAT(child_path, ElementsAre(i)); |
| EXPECT_EQ(&tree.DescendPath(child_path.begin(), child_path.end()), &child); |
| |
| for (int j = 0; j < 2; ++j) { |
| const auto& grandchild = child.Children()[j]; |
| EXPECT_EQ(grandchild.Parent(), &child); |
| EXPECT_EQ(grandchild.Root(), &tree); |
| EXPECT_TRUE(grandchild.Children().empty()); |
| EXPECT_EQ(grandchild.NumAncestors(), 2); |
| EXPECT_EQ(grandchild.BirthRank(), j); |
| EXPECT_EQ(grandchild.IsFirstChild(), j == 0); |
| EXPECT_EQ(grandchild.IsLastChild(), j == 1); |
| |
| const auto grandchild_path = MakePath(grandchild); |
| EXPECT_THAT(grandchild_path, ElementsAre(i, j)); |
| const auto begin = grandchild_path.begin(), end = grandchild_path.end(); |
| EXPECT_EQ(&tree.DescendPath(begin, end), &grandchild); |
| EXPECT_EQ(&child.DescendPath(begin + 1, end), &grandchild); |
| ExpectPath(grandchild, absl::StrCat("{", i, ",", j, "}")); |
| } |
| } |
| } |
| |
| // Tests internal consistency of BirthRank and Path properties. |
| TEST(VectorTreeTest, FamilyTreeMembers) { |
| const auto tree = verible::testing::MakeExampleFamilyTree(); |
| VerifyFamilyTree(tree); |
| } |
| |
| // Tests internal consistency and properties of copied tree. |
| TEST(VectorTreeTest, FamilyTreeCopiedMembers) { |
| const auto orig_tree = verible::testing::MakeExampleFamilyTree(); |
| const auto tree(orig_tree); // copied |
| VerifyFamilyTree(orig_tree); |
| VerifyFamilyTree(tree); |
| |
| const auto result_pair = DeepEqual(orig_tree, tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| // Tests internal consistency and properties of moved tree. |
| TEST(VectorTreeTest, FamilyTreeMovedMembers) { |
| auto orig_tree = verible::testing::MakeExampleFamilyTree(); |
| const auto tree(std::move(orig_tree)); // moved |
| VerifyFamilyTree(tree); |
| } |
| |
| TEST(VectorTreeTest, FamilyTreeLeftRightmostDescendants) { |
| auto tree = verible::testing::MakeExampleFamilyTree(); |
| const auto left_path = {0, 0}; |
| const auto right_path = {1, 1}; |
| { // Test mutable method variants. |
| EXPECT_EQ(tree.LeftmostDescendant(), |
| &tree.DescendPath(left_path.begin(), left_path.end())); |
| EXPECT_EQ(tree.RightmostDescendant(), |
| &tree.DescendPath(right_path.begin(), right_path.end())); |
| } |
| { // Test const method variants. |
| const auto& ctree(tree); |
| EXPECT_EQ(ctree.LeftmostDescendant(), |
| &ctree.DescendPath(left_path.begin(), left_path.end())); |
| EXPECT_EQ(ctree.RightmostDescendant(), |
| &ctree.DescendPath(right_path.begin(), right_path.end())); |
| } |
| } |
| |
| TEST(VectorTreeTest, FamilyTreeContainsAncestor) { |
| const auto tree = verible::testing::MakeExampleFamilyTree(); |
| const auto& child_0 = tree.Children()[0]; |
| const auto& child_1 = tree.Children()[1]; |
| const auto& grandchild_00 = child_0.Children()[0]; |
| const auto& grandchild_01 = child_0.Children()[1]; |
| const auto& grandchild_10 = child_1.Children()[0]; |
| const auto& grandchild_11 = child_1.Children()[1]; |
| |
| EXPECT_FALSE(tree.ContainsAncestor(&child_0)); |
| EXPECT_FALSE(tree.ContainsAncestor(&child_1)); |
| EXPECT_FALSE(tree.ContainsAncestor(&grandchild_00)); |
| EXPECT_FALSE(tree.ContainsAncestor(&grandchild_01)); |
| EXPECT_FALSE(tree.ContainsAncestor(&grandchild_10)); |
| EXPECT_FALSE(tree.ContainsAncestor(&grandchild_11)); |
| |
| EXPECT_TRUE(child_0.ContainsAncestor(&tree)); |
| EXPECT_TRUE(child_1.ContainsAncestor(&tree)); |
| EXPECT_TRUE(grandchild_00.ContainsAncestor(&tree)); |
| EXPECT_TRUE(grandchild_01.ContainsAncestor(&tree)); |
| EXPECT_TRUE(grandchild_10.ContainsAncestor(&tree)); |
| EXPECT_TRUE(grandchild_11.ContainsAncestor(&tree)); |
| |
| EXPECT_FALSE(child_0.ContainsAncestor(&child_1)); |
| EXPECT_FALSE(child_1.ContainsAncestor(&child_0)); |
| |
| EXPECT_FALSE(child_0.ContainsAncestor(&grandchild_00)); |
| EXPECT_FALSE(child_0.ContainsAncestor(&grandchild_01)); |
| EXPECT_FALSE(child_0.ContainsAncestor(&grandchild_10)); |
| EXPECT_FALSE(child_0.ContainsAncestor(&grandchild_11)); |
| EXPECT_FALSE(child_1.ContainsAncestor(&grandchild_00)); |
| EXPECT_FALSE(child_1.ContainsAncestor(&grandchild_01)); |
| EXPECT_FALSE(child_1.ContainsAncestor(&grandchild_10)); |
| EXPECT_FALSE(child_1.ContainsAncestor(&grandchild_11)); |
| |
| EXPECT_TRUE(grandchild_00.ContainsAncestor(&child_0)); |
| EXPECT_FALSE(grandchild_00.ContainsAncestor(&child_1)); |
| EXPECT_TRUE(grandchild_01.ContainsAncestor(&child_0)); |
| EXPECT_FALSE(grandchild_01.ContainsAncestor(&child_1)); |
| EXPECT_FALSE(grandchild_10.ContainsAncestor(&child_0)); |
| EXPECT_TRUE(grandchild_10.ContainsAncestor(&child_1)); |
| EXPECT_FALSE(grandchild_11.ContainsAncestor(&child_0)); |
| EXPECT_TRUE(grandchild_11.ContainsAncestor(&child_1)); |
| } |
| |
| TEST(VectorTreeTest, FamilyTreeNextPreviousSiblings) { |
| auto tree = verible::testing::MakeExampleFamilyTree(); |
| auto& child_0 = tree.Children()[0]; |
| auto& child_1 = tree.Children()[1]; |
| auto& grandchild_00 = child_0.Children()[0]; |
| auto& grandchild_01 = child_0.Children()[1]; |
| auto& grandchild_10 = child_1.Children()[0]; |
| auto& grandchild_11 = child_1.Children()[1]; |
| |
| // Verify child generation. |
| EXPECT_EQ(child_0.NextSibling(), &child_1); |
| EXPECT_EQ(child_1.NextSibling(), nullptr); |
| EXPECT_EQ(child_0.PreviousSibling(), nullptr); |
| EXPECT_EQ(child_1.PreviousSibling(), &child_0); |
| |
| // Verify grandchild generation. |
| EXPECT_EQ(grandchild_00.NextSibling(), &grandchild_01); |
| EXPECT_EQ(grandchild_01.NextSibling(), nullptr); |
| EXPECT_EQ(grandchild_10.NextSibling(), &grandchild_11); |
| EXPECT_EQ(grandchild_11.NextSibling(), nullptr); |
| EXPECT_EQ(grandchild_00.PreviousSibling(), nullptr); |
| EXPECT_EQ(grandchild_01.PreviousSibling(), &grandchild_00); |
| EXPECT_EQ(grandchild_10.PreviousSibling(), nullptr); |
| EXPECT_EQ(grandchild_11.PreviousSibling(), &grandchild_10); |
| |
| { // same but testing const method variants. |
| const auto& cchild_0(child_0); |
| const auto& cchild_1(child_1); |
| const auto& cgrandchild_00(grandchild_00); |
| const auto& cgrandchild_01(grandchild_01); |
| const auto& cgrandchild_10(grandchild_10); |
| const auto& cgrandchild_11(grandchild_11); |
| |
| // Verify child generation. |
| EXPECT_EQ(cchild_0.NextSibling(), &cchild_1); |
| EXPECT_EQ(cchild_1.NextSibling(), nullptr); |
| EXPECT_EQ(cchild_0.PreviousSibling(), nullptr); |
| EXPECT_EQ(cchild_1.PreviousSibling(), &cchild_0); |
| |
| // Verify grandchild generation. |
| EXPECT_EQ(cgrandchild_00.NextSibling(), &cgrandchild_01); |
| EXPECT_EQ(cgrandchild_01.NextSibling(), nullptr); |
| EXPECT_EQ(cgrandchild_10.NextSibling(), &cgrandchild_11); |
| EXPECT_EQ(cgrandchild_11.NextSibling(), nullptr); |
| EXPECT_EQ(cgrandchild_00.PreviousSibling(), nullptr); |
| EXPECT_EQ(cgrandchild_01.PreviousSibling(), &cgrandchild_00); |
| EXPECT_EQ(cgrandchild_10.PreviousSibling(), nullptr); |
| EXPECT_EQ(cgrandchild_11.PreviousSibling(), &cgrandchild_10); |
| } |
| } |
| |
| TEST(VectorTreeTest, FamilyTreeNextPreviousLeafChain) { |
| auto tree = verible::testing::MakeExampleFamilyTree(); |
| auto& grandchild_00 = tree.Children()[0].Children()[0]; |
| auto& grandchild_01 = tree.Children()[0].Children()[1]; |
| auto& grandchild_10 = tree.Children()[1].Children()[0]; |
| auto& grandchild_11 = tree.Children()[1].Children()[1]; |
| |
| // Verify forward links. |
| EXPECT_EQ(grandchild_00.NextLeaf(), &grandchild_01); |
| EXPECT_EQ(grandchild_01.NextLeaf(), &grandchild_10); |
| EXPECT_EQ(grandchild_10.NextLeaf(), &grandchild_11); |
| EXPECT_EQ(grandchild_11.NextLeaf(), nullptr); |
| |
| // Verify reverse links. |
| EXPECT_EQ(grandchild_00.PreviousLeaf(), nullptr); |
| EXPECT_EQ(grandchild_01.PreviousLeaf(), &grandchild_00); |
| EXPECT_EQ(grandchild_10.PreviousLeaf(), &grandchild_01); |
| EXPECT_EQ(grandchild_11.PreviousLeaf(), &grandchild_10); |
| |
| { // same but testing const method variants. |
| const auto& cgrandchild_00(grandchild_00); |
| const auto& cgrandchild_01(grandchild_01); |
| const auto& cgrandchild_10(grandchild_10); |
| const auto& cgrandchild_11(grandchild_11); |
| |
| // Verify forward links. |
| EXPECT_EQ(cgrandchild_00.NextLeaf(), &cgrandchild_01); |
| EXPECT_EQ(cgrandchild_01.NextLeaf(), &cgrandchild_10); |
| EXPECT_EQ(cgrandchild_10.NextLeaf(), &cgrandchild_11); |
| EXPECT_EQ(cgrandchild_11.NextLeaf(), nullptr); |
| |
| // Verify reverse links. |
| EXPECT_EQ(cgrandchild_00.PreviousLeaf(), nullptr); |
| EXPECT_EQ(cgrandchild_01.PreviousLeaf(), &cgrandchild_00); |
| EXPECT_EQ(cgrandchild_10.PreviousLeaf(), &cgrandchild_01); |
| EXPECT_EQ(cgrandchild_11.PreviousLeaf(), &cgrandchild_10); |
| } |
| } |
| |
| TEST(VectorTreeTest, FamilyTreeMembersTransformed) { |
| const auto orig_tree = verible::testing::MakeExampleFamilyTree(); |
| const auto tree = orig_tree.Transform<NameOnly>(NameOnlyConverter); |
| VerifyFamilyTree(orig_tree); |
| VerifyFamilyTree(tree); |
| |
| { |
| const auto result_pair = StructureEqual(orig_tree, tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| { // Converse comparison. |
| const auto result_pair = StructureEqual(tree, orig_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| { |
| // Uses hetergeneous value comparison. |
| const auto result_pair = DeepEqual(orig_tree, tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| // Mutate one grandchild at a time. |
| for (size_t i = 0; i < 2; ++i) { |
| for (size_t j = 0; j < 2; ++j) { |
| auto ltree(orig_tree); // copy |
| auto rtree(tree); // copy |
| const std::vector<size_t> path({i, j}); |
| auto& lchild = ltree.DescendPath(path.begin(), path.end()); |
| auto& rchild = rtree.DescendPath(path.begin(), path.end()); |
| |
| lchild.Value().name = "foo"; |
| rchild.Value().name = "bar"; |
| const auto result_pair = DeepEqual(ltree, rtree); |
| EXPECT_EQ(result_pair.left, &lchild); |
| EXPECT_EQ(result_pair.right, &rchild); |
| } |
| } |
| } |
| |
| TEST(VectorTreeTest, FamilyTreeMembersDifferentStructureExtraGreatGrand) { |
| // Mutate grandchildren structure. |
| for (size_t i = 0; i < 2; ++i) { |
| for (size_t j = 0; j < 2; ++j) { |
| auto ltree = verible::testing::MakeExampleFamilyTree(); |
| auto rtree = verible::testing::MakeExampleFamilyTree(); |
| const std::vector<size_t> path({i, j}); |
| auto& lchild = ltree.DescendPath(path.begin(), path.end()); |
| auto& rchild = rtree.DescendPath(path.begin(), path.end()); |
| |
| rchild.NewChild(NamedInterval(8, 9, "black-sheep")); |
| const auto result_pair = StructureEqual(ltree, rtree); |
| EXPECT_EQ(result_pair.left, &lchild); |
| EXPECT_EQ(result_pair.right, &rchild); |
| } |
| } |
| } |
| |
| TEST(VectorTreeTest, FamilyTreeMembersDifferentStructureExtraGrand) { |
| // Mutate grandchildren structure. |
| for (size_t i = 0; i < 2; ++i) { |
| for (size_t j = 0; j < 2; ++j) { |
| auto ltree = verible::testing::MakeExampleFamilyTree(); |
| auto rtree = verible::testing::MakeExampleFamilyTree(); |
| const std::vector<size_t> path({i, j}); |
| const auto& lparent = ltree.DescendPath(path.begin(), path.end() - 1); |
| const auto& rparent = rtree.DescendPath(path.begin(), path.end() - 1); |
| auto& rchild = rtree.DescendPath(path.begin(), path.end()); |
| |
| rchild.NewSibling(NamedInterval(8, 9, "black-sheep")); |
| const auto result_pair = StructureEqual(ltree, rtree); |
| EXPECT_EQ(result_pair.left, &lparent); |
| EXPECT_EQ(result_pair.right, &rparent); |
| } |
| } |
| } |
| |
| TEST(VectorTreeTest, FamilyTreeMembersDifferentStructureMissingGrand) { |
| // Remove one set of grandchildren. |
| for (size_t i = 0; i < 2; ++i) { |
| auto ltree = verible::testing::MakeExampleFamilyTree(); |
| auto rtree = verible::testing::MakeExampleFamilyTree(); |
| const std::vector<size_t> path({i}); |
| auto& lchild = ltree.DescendPath(path.begin(), path.end()); |
| auto& rchild = rtree.DescendPath(path.begin(), path.end()); |
| |
| lchild.Children().clear(); |
| const auto result_pair = StructureEqual(ltree, rtree); |
| EXPECT_EQ(result_pair.left, &lchild); |
| EXPECT_EQ(result_pair.right, &rchild); |
| } |
| } |
| |
| bool EqualNamedIntervalIgnoreName(const NamedInterval& l, |
| const NamedInterval& r) { |
| return l.left == r.left && l.right == r.right; // ignore .name |
| } |
| |
| TEST(VectorTreeTest, FamilyTreeMembersDeepEqualCustomComparator) { |
| // Mutate grandchildren structure. |
| for (size_t i = 0; i < 2; ++i) { |
| for (size_t j = 0; j < 2; ++j) { |
| auto ltree = verible::testing::MakeExampleFamilyTree(); |
| auto rtree = verible::testing::MakeExampleFamilyTree(); |
| const std::vector<size_t> path({i, j}); |
| auto& lchild = ltree.DescendPath(path.begin(), path.end()); |
| auto& rchild = rtree.DescendPath(path.begin(), path.end()); |
| lchild.Value().name = "larry"; |
| rchild.Value().name = "sergey"; |
| |
| { |
| const auto result_pair = DeepEqual(ltree, rtree); |
| EXPECT_EQ(result_pair.left, &lchild); |
| EXPECT_EQ(result_pair.right, &rchild); |
| } |
| { |
| const auto result_pair = |
| DeepEqual(ltree, rtree, EqualNamedIntervalIgnoreName); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| } |
| } |
| } |
| |
| TEST(VectorTreeTest, NearestCommonAncestorNoneMutable) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree1{0}, tree2{0}; |
| EXPECT_EQ(tree1.NearestCommonAncestor(&tree2), nullptr); |
| EXPECT_EQ(tree2.NearestCommonAncestor(&tree1), nullptr); |
| } |
| |
| TEST(VectorTreeTest, NearestCommonAncestorNoneConst) { |
| typedef VectorTree<int> tree_type; |
| const tree_type tree1{0}, tree2{0}; |
| EXPECT_EQ(tree1.NearestCommonAncestor(&tree2), nullptr); |
| EXPECT_EQ(tree2.NearestCommonAncestor(&tree1), nullptr); |
| } |
| |
| TEST(VectorTreeTest, NearestCommonAncestorSameMutable) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree{0}; |
| EXPECT_EQ(tree.NearestCommonAncestor(&tree), &tree); |
| EXPECT_EQ(tree.NearestCommonAncestor(&tree), &tree); |
| } |
| |
| TEST(VectorTreeTest, NearestCommonAncestorSameConst) { |
| typedef VectorTree<int> tree_type; |
| const tree_type tree{0}; |
| EXPECT_EQ(tree.NearestCommonAncestor(&tree), &tree); |
| EXPECT_EQ(tree.NearestCommonAncestor(&tree), &tree); |
| } |
| |
| TEST(VectorTreeTest, NearestCommonAncestorOneIsRootConst) { |
| typedef VectorTree<int> tree_type; |
| const tree_type tree(1, // |
| tree_type(2, // |
| tree_type(4), tree_type(5)), |
| tree_type(3, // |
| tree_type(6), tree_type(7))); |
| |
| for (int i = 0; i < 2; ++i) { |
| { |
| const auto path = {i}; |
| auto& child = tree.DescendPath(path.begin(), path.end()); |
| EXPECT_EQ(tree.NearestCommonAncestor(&child), &tree); |
| EXPECT_EQ(child.NearestCommonAncestor(&tree), &tree); |
| } |
| for (int j = 0; j < 2; ++j) { |
| const auto path = {i, j}; |
| auto& grandchild = tree.DescendPath(path.begin(), path.end()); |
| EXPECT_EQ(tree.NearestCommonAncestor(&grandchild), &tree); |
| EXPECT_EQ(grandchild.NearestCommonAncestor(&tree), &tree); |
| } |
| } |
| } |
| |
| TEST(VectorTreeTest, NearestCommonAncestorNeitherIsRootConst) { |
| typedef VectorTree<int> tree_type; |
| const tree_type tree(1, // |
| tree_type(2, // |
| tree_type(4), tree_type(5)), |
| tree_type(3, // |
| tree_type(6), tree_type(7))); |
| auto& left = tree.Children()[0]; |
| auto& right = tree.Children()[1]; |
| EXPECT_EQ(left.NearestCommonAncestor(&right), &tree); |
| EXPECT_EQ(right.NearestCommonAncestor(&left), &tree); |
| |
| for (int i = 0; i < 2; ++i) { |
| { |
| const auto left_path = {0, i}; |
| auto& left_grandchild = |
| tree.DescendPath(left_path.begin(), left_path.end()); |
| EXPECT_EQ(left.NearestCommonAncestor(&left_grandchild), &left); |
| EXPECT_EQ(left_grandchild.NearestCommonAncestor(&left), &left); |
| EXPECT_EQ(right.NearestCommonAncestor(&left_grandchild), &tree); |
| EXPECT_EQ(left_grandchild.NearestCommonAncestor(&right), &tree); |
| } |
| { |
| const auto right_path = {1, i}; |
| auto& right_grandchild = |
| tree.DescendPath(right_path.begin(), right_path.end()); |
| EXPECT_EQ(right.NearestCommonAncestor(&right_grandchild), &right); |
| EXPECT_EQ(right_grandchild.NearestCommonAncestor(&right), &right); |
| EXPECT_EQ(left.NearestCommonAncestor(&right_grandchild), &tree); |
| EXPECT_EQ(right_grandchild.NearestCommonAncestor(&left), &tree); |
| } |
| } |
| } |
| |
| TEST(VectorTreeTest, ApplyPreOrderPrint) { |
| const auto tree = verible::testing::MakeExampleFamilyTree(); |
| |
| std::ostringstream stream; |
| tree.ApplyPreOrder([&stream](const NamedInterval& interval) { |
| IntervalPrinter(&stream, interval); |
| }); |
| EXPECT_EQ(stream.str(), absl::StrJoin( |
| { |
| "(0, 4, grandparent)", |
| "(0, 2, parent1)", |
| "(0, 1, child1)", |
| "(1, 2, child2)", |
| "(2, 4, parent2)", |
| "(2, 3, child3)", |
| "(3, 4, child4)", |
| }, |
| "\n") + |
| "\n"); |
| } |
| |
| TEST(VectorTreeTest, ApplyPreOrderPrintTransformed) { |
| const auto orig_tree = verible::testing::MakeExampleFamilyTree(); |
| const auto tree = orig_tree.Transform<NameOnly>(NameOnlyConverter); |
| |
| std::ostringstream stream; |
| tree.ApplyPreOrder([&stream](const NameOnly& n) { stream << n; }); |
| EXPECT_EQ(stream.str(), absl::StrJoin( |
| { |
| "(grandparent)", |
| "(parent1)", |
| "(child1)", |
| "(child2)", |
| "(parent2)", |
| "(child3)", |
| "(child4)", |
| }, |
| "\n") + |
| "\n"); |
| } |
| |
| TEST(VectorTreeTest, ApplyPostOrderPrint) { |
| const auto tree = verible::testing::MakeExampleFamilyTree(); |
| |
| std::ostringstream stream; |
| tree.ApplyPostOrder([&stream](const NamedInterval& interval) { |
| IntervalPrinter(&stream, interval); |
| }); |
| EXPECT_EQ(stream.str(), absl::StrJoin( |
| { |
| "(0, 1, child1)", |
| "(1, 2, child2)", |
| "(0, 2, parent1)", |
| "(2, 3, child3)", |
| "(3, 4, child4)", |
| "(2, 4, parent2)", |
| "(0, 4, grandparent)", |
| }, |
| "\n") + |
| "\n"); |
| } |
| |
| TEST(VectorTreeTest, ApplyPreOrderVerify) { |
| const auto tree = verible::testing::MakeExampleFamilyTree(); |
| // Verify invariant at every node. |
| tree.ApplyPreOrder(verible::testing::VerifyInterval); |
| } |
| |
| TEST(VectorTreeTest, ApplyPostOrderVerify) { |
| const auto tree = verible::testing::MakeExampleFamilyTree(); |
| // Verify invariant at every node. |
| tree.ApplyPostOrder(verible::testing::VerifyInterval); |
| } |
| |
| TEST(VectorTreeTest, ApplyPreOrderTransformValue) { |
| auto tree = verible::testing::MakeExampleFamilyTree(); |
| |
| // Transform intervals. |
| std::vector<absl::string_view> visit_order; |
| const int shift = 2; |
| tree.ApplyPreOrder([=, &visit_order](NamedInterval& interval) { |
| visit_order.push_back(interval.name); |
| interval.left += shift; |
| interval.right += shift; |
| }); |
| EXPECT_THAT(visit_order, |
| ElementsAre("grandparent", "parent1", "child1", "child2", |
| "parent2", "child3", "child4")); |
| |
| // Print output for verification. |
| std::ostringstream stream; |
| tree.ApplyPreOrder([&stream](const NamedInterval& interval) { |
| IntervalPrinter(&stream, interval); |
| }); |
| EXPECT_EQ(stream.str(), absl::StrJoin( |
| { |
| "(2, 6, grandparent)", |
| "(2, 4, parent1)", |
| "(2, 3, child1)", |
| "(3, 4, child2)", |
| "(4, 6, parent2)", |
| "(4, 5, child3)", |
| "(5, 6, child4)", |
| }, |
| "\n") + |
| "\n"); |
| } |
| |
| TEST(VectorTreeTest, ApplyPreOrderTransformNode) { |
| auto tree = verible::testing::MakeExampleFamilyTree(); |
| |
| // Transform intervals. |
| std::vector<absl::string_view> visit_order; |
| const int shift = 2; |
| tree.ApplyPreOrder([=, &visit_order](VectorTreeTestType& node) { |
| auto& interval = node.Value(); |
| visit_order.push_back(interval.name); |
| interval.left += shift; |
| interval.right += shift; |
| }); |
| EXPECT_THAT(visit_order, |
| ElementsAre("grandparent", "parent1", "child1", "child2", |
| "parent2", "child3", "child4")); |
| |
| // Print output for verification. |
| std::ostringstream stream; |
| tree.ApplyPreOrder([&stream](const NamedInterval& interval) { |
| IntervalPrinter(&stream, interval); |
| }); |
| EXPECT_EQ(stream.str(), absl::StrJoin( |
| { |
| "(2, 6, grandparent)", |
| "(2, 4, parent1)", |
| "(2, 3, child1)", |
| "(3, 4, child2)", |
| "(4, 6, parent2)", |
| "(4, 5, child3)", |
| "(5, 6, child4)", |
| }, |
| "\n") + |
| "\n"); |
| } |
| |
| TEST(VectorTreeTest, ApplyPostOrderTransformValue) { |
| auto tree = verible::testing::MakeExampleFamilyTree(); |
| |
| // Transform intervals. |
| std::vector<absl::string_view> visit_order; |
| const int shift = 1; |
| tree.ApplyPostOrder([=, &visit_order](NamedInterval& interval) { |
| visit_order.push_back(interval.name); |
| interval.left += shift; |
| interval.right += shift; |
| }); |
| EXPECT_THAT(visit_order, ElementsAre("child1", "child2", "parent1", "child3", |
| "child4", "parent2", "grandparent")); |
| |
| // Print output for verification. |
| std::ostringstream stream; |
| tree.ApplyPostOrder([&stream](const NamedInterval& interval) { |
| IntervalPrinter(&stream, interval); |
| }); |
| EXPECT_EQ(stream.str(), absl::StrJoin( |
| { |
| "(1, 2, child1)", |
| "(2, 3, child2)", |
| "(1, 3, parent1)", |
| "(3, 4, child3)", |
| "(4, 5, child4)", |
| "(3, 5, parent2)", |
| "(1, 5, grandparent)", |
| }, |
| "\n") + |
| "\n"); |
| } |
| |
| TEST(VectorTreeTest, ApplyPostOrderTransformNode) { |
| auto tree = verible::testing::MakeExampleFamilyTree(); |
| |
| // Transform intervals. |
| std::vector<absl::string_view> visit_order; |
| const int shift = 1; |
| tree.ApplyPostOrder([=, &visit_order](VectorTreeTestType& node) { |
| auto& interval = node.Value(); |
| visit_order.push_back(interval.name); |
| interval.left += shift; |
| interval.right += shift; |
| }); |
| EXPECT_THAT(visit_order, ElementsAre("child1", "child2", "parent1", "child3", |
| "child4", "parent2", "grandparent")); |
| |
| // Print output for verification. |
| std::ostringstream stream; |
| tree.ApplyPostOrder([&stream](const NamedInterval& interval) { |
| IntervalPrinter(&stream, interval); |
| }); |
| EXPECT_EQ(stream.str(), absl::StrJoin( |
| { |
| "(1, 2, child1)", |
| "(2, 3, child2)", |
| "(1, 3, parent1)", |
| "(3, 4, child3)", |
| "(4, 5, child4)", |
| "(3, 5, parent2)", |
| "(1, 5, grandparent)", |
| }, |
| "\n") + |
| "\n"); |
| } |
| |
| TEST(VectorTreeTest, HoistOnlyChildRootOnly) { |
| VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree()); |
| // No children, no change. |
| EXPECT_FALSE(tree.HoistOnlyChild()); |
| |
| EXPECT_TRUE(tree.Children().empty()); |
| EXPECT_EQ(tree.Parent(), nullptr); |
| EXPECT_EQ(tree.NumAncestors(), 0); |
| EXPECT_EQ(tree.BirthRank(), 0); // no parent |
| EXPECT_EQ(tree.Root(), &tree); |
| |
| const auto& value = tree.Value(); |
| EXPECT_EQ(value.left, 0); |
| EXPECT_EQ(value.right, 2); |
| EXPECT_EQ(value.name, "root"); |
| |
| ExpectPath(tree, "{}"); |
| } |
| |
| TEST(VectorTreeTest, HoistOnlyChildOneChildTreeGreatestAncestor) { |
| VectorTreeTestType tree(verible::testing::MakeOneChildPolicyExampleTree()); |
| // effectively remove the "root" generation |
| EXPECT_TRUE(tree.HoistOnlyChild()); |
| { |
| const auto& child = tree; |
| EXPECT_EQ(child.Parent(), nullptr); |
| EXPECT_EQ(child.Root(), &tree); |
| EXPECT_FALSE(child.Children().empty()); |
| EXPECT_EQ(child.NumAncestors(), 0); |
| EXPECT_EQ(child.BirthRank(), 0); |
| |
| const auto& cvalue = child.Value(); |
| EXPECT_EQ(cvalue.left, 0); |
| EXPECT_EQ(cvalue.right, 3); |
| EXPECT_EQ(cvalue.name, "gen1"); |
| ExpectPath(child, "{}"); |
| |
| EXPECT_EQ(child.NextSibling(), nullptr); |
| EXPECT_EQ(child.PreviousSibling(), nullptr); |
| |
| // The invoking node need not be a leaf. |
| EXPECT_EQ(child.NextLeaf(), nullptr); |
| EXPECT_EQ(child.PreviousLeaf(), nullptr); |
| |
| { |
| const auto& grandchild = child.Children().front(); |
| EXPECT_EQ(grandchild.Parent(), &child); |
| EXPECT_EQ(grandchild.Root(), &tree); |
| EXPECT_TRUE(grandchild.Children().empty()); |
| EXPECT_EQ(grandchild.NumAncestors(), 1); |
| EXPECT_EQ(grandchild.BirthRank(), 0); |
| |
| const auto& gcvalue = grandchild.Value(); |
| EXPECT_EQ(gcvalue.left, 0); |
| EXPECT_EQ(gcvalue.right, 3); |
| EXPECT_EQ(gcvalue.name, "gen2"); |
| ExpectPath(grandchild, "{0}"); |
| |
| // As the ancestry chain is linear, Leftmost == Rightmost. |
| EXPECT_EQ(child.LeftmostDescendant(), &grandchild); |
| EXPECT_EQ(child.RightmostDescendant(), &grandchild); |
| EXPECT_EQ(tree.LeftmostDescendant(), &grandchild); |
| EXPECT_EQ(tree.RightmostDescendant(), &grandchild); |
| |
| EXPECT_EQ(grandchild.NextSibling(), nullptr); |
| EXPECT_EQ(grandchild.PreviousSibling(), nullptr); |
| |
| // There is still only a single leaf in a one-child tree, |
| // thus next and previous do not exist. |
| EXPECT_EQ(grandchild.NextLeaf(), nullptr); |
| EXPECT_EQ(grandchild.PreviousLeaf(), nullptr); |
| } |
| } |
| } |
| |
| TEST(VectorTreeTest, HoistOnlyChildOneChildTreeMiddleAncestor) { |
| VectorTreeTestType tree(verible::testing::MakeOneChildPolicyExampleTree()); |
| EXPECT_TRUE(tree.Children().front().HoistOnlyChild()); |
| { |
| const auto& value = tree.Value(); |
| EXPECT_EQ(value.left, 0); |
| EXPECT_EQ(value.right, 3); |
| EXPECT_EQ(value.name, "root"); |
| |
| EXPECT_EQ(tree.NextSibling(), nullptr); |
| EXPECT_EQ(tree.PreviousSibling(), nullptr); |
| |
| // The invoking node need not be a leaf. |
| EXPECT_EQ(tree.NextLeaf(), nullptr); |
| EXPECT_EQ(tree.PreviousLeaf(), nullptr); |
| |
| // The "gen1" node is removed, and now the grandchild is directly linked. |
| { |
| const auto& grandchild = tree.Children().front(); |
| EXPECT_EQ(grandchild.Parent(), &tree); |
| EXPECT_EQ(grandchild.Root(), &tree); |
| EXPECT_TRUE(grandchild.Children().empty()); |
| EXPECT_EQ(grandchild.NumAncestors(), 1); |
| EXPECT_EQ(grandchild.BirthRank(), 0); |
| |
| const auto& gcvalue = grandchild.Value(); |
| EXPECT_EQ(gcvalue.left, 0); |
| EXPECT_EQ(gcvalue.right, 3); |
| EXPECT_EQ(gcvalue.name, "gen2"); |
| ExpectPath(grandchild, "{0}"); |
| |
| // As the ancestry chain is linear, Leftmost == Rightmost. |
| EXPECT_EQ(tree.LeftmostDescendant(), &grandchild); |
| EXPECT_EQ(tree.RightmostDescendant(), &grandchild); |
| |
| EXPECT_EQ(grandchild.NextSibling(), nullptr); |
| EXPECT_EQ(grandchild.PreviousSibling(), nullptr); |
| |
| // There is still only a single leaf in a one-child tree, |
| // thus next and previous do not exist. |
| EXPECT_EQ(grandchild.NextLeaf(), nullptr); |
| EXPECT_EQ(grandchild.PreviousLeaf(), nullptr); |
| } |
| } |
| } |
| |
| TEST(VectorTreeTest, HoistOnlyChildFamilyTree) { |
| VectorTreeTestType tree(verible::testing::MakeExampleFamilyTree()); |
| // No change because each generation has more than one child. |
| EXPECT_FALSE(tree.HoistOnlyChild()); |
| } |
| |
| // Copy-extract tree values from a node's direct children only. |
| // TODO(fangism): Adapt this into a public method of VectorTree. |
| template <typename T> |
| static std::vector<typename T::value_type> NodeValues(const T& node) { |
| std::vector<typename T::value_type> result; |
| result.reserve(node.Children().size()); |
| for (const auto& child : node.Children()) { |
| result.emplace_back(child.Value()); |
| } |
| return result; |
| } |
| |
| TEST(VectorTreeTest, AdoptSubtreesFromEmptyToEmpty) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree1(1), tree2(2); // no subtrees |
| EXPECT_TRUE(tree1.Children().empty()); |
| EXPECT_TRUE(tree2.Children().empty()); |
| |
| tree1.AdoptSubtreesFrom(&tree2); |
| EXPECT_TRUE(tree1.Children().empty()); |
| EXPECT_TRUE(tree2.Children().empty()); |
| } |
| |
| TEST(VectorTreeTest, AdoptSubtreesFromEmptyToNonempty) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree1(1, tree_type(4)), tree2(2); |
| EXPECT_THAT(NodeValues(tree1), ElementsAre(4)); |
| EXPECT_THAT(NodeValues(tree2), ElementsAre()); |
| |
| tree1.AdoptSubtreesFrom(&tree2); |
| EXPECT_THAT(NodeValues(tree1), ElementsAre(4)); |
| EXPECT_THAT(NodeValues(tree2), ElementsAre()); |
| } |
| |
| TEST(VectorTreeTest, AdoptSubtreesFromNonemptyToEmpty) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree1(1), tree2(2, tree_type(5)); |
| EXPECT_THAT(NodeValues(tree1), ElementsAre()); |
| EXPECT_THAT(NodeValues(tree2), ElementsAre(5)); |
| |
| tree1.AdoptSubtreesFrom(&tree2); |
| EXPECT_THAT(NodeValues(tree1), ElementsAre(5)); |
| EXPECT_THAT(NodeValues(tree2), ElementsAre()); |
| } |
| |
| TEST(VectorTreeTest, AdoptSubtreesFromNonemptyToNonempty) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree1(1, tree_type(3), tree_type(6)), |
| tree2(2, tree_type(5), tree_type(8)); |
| EXPECT_THAT(NodeValues(tree1), ElementsAre(3, 6)); |
| EXPECT_THAT(NodeValues(tree2), ElementsAre(5, 8)); |
| |
| tree1.AdoptSubtreesFrom(&tree2); |
| EXPECT_THAT(NodeValues(tree1), ElementsAre(3, 6, 5, 8)); |
| EXPECT_THAT(NodeValues(tree2), ElementsAre()); |
| } |
| |
| TEST(VectorTreeTest, MergeConsecutiveSiblingsTooFewElements) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, tree_type(2)); |
| auto adder = [](int* left, const int& right) { *left += right; }; |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2)); |
| EXPECT_DEATH(tree.MergeConsecutiveSiblings(0, adder), ""); |
| } |
| |
| TEST(VectorTreeTest, MergeConsecutiveSiblingsOutOfBounds) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, tree_type(2), tree_type(3)); |
| auto adder = [](int* left, const int& right) { *left += right; }; |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3)); |
| EXPECT_DEATH(tree.MergeConsecutiveSiblings(1, adder), ""); |
| } |
| |
| TEST(VectorTreeTest, MergeConsecutiveSiblingsAddLeaves) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, tree_type(2), tree_type(3), tree_type(4), tree_type(5)); |
| auto adder = [](int* left, const int& right) { *left += right; }; |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5)); |
| |
| VLOG(1) << __FUNCTION__ << ": before first merge"; |
| |
| tree.MergeConsecutiveSiblings(1, adder); // combine middle two subtrees |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 7, 5)); |
| VLOG(1) << __FUNCTION__ << ": after first merge"; |
| |
| tree.MergeConsecutiveSiblings(1, adder); // combine last two subtrees |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 12)); |
| VLOG(1) << __FUNCTION__ << ": after second merge"; |
| |
| tree.MergeConsecutiveSiblings(0, adder); // combine only two subtrees |
| EXPECT_THAT(NodeValues(tree), ElementsAre(14)); |
| VLOG(1) << __FUNCTION__ << ": after third merge"; |
| } |
| |
| TEST(VectorTreeTest, MergeConsecutiveSiblingsConcatenateSubtreesOnce) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(2, // |
| tree_type(6), tree_type(7)), |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4, // |
| tree_type(10), tree_type(11)), |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| auto subtractor = [](int* left, const int& right) { *left -= right; }; |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5)); |
| |
| tree.MergeConsecutiveSiblings(1, subtractor); // combine middle two subtrees |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, /* 3 - 4 */ -1, 5)); |
| EXPECT_THAT(NodeValues(tree.Children()[1]), ElementsAre(8, 9, 10, 11)); |
| } |
| |
| TEST(VectorTreeTest, MergeConsecutiveSiblingsConcatenateSubtrees) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(2, // |
| tree_type(6), tree_type(7)), |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4, // |
| tree_type(10), tree_type(11)), |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| auto subtractor = [](int* left, const int& right) { *left -= right; }; |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5)); |
| |
| tree.MergeConsecutiveSiblings(0, subtractor); // combine first two subtrees |
| EXPECT_THAT(NodeValues(tree), ElementsAre(/* 2 - 3 */ -1, 4, 5)); |
| EXPECT_THAT(NodeValues(tree.Children()[0]), ElementsAre(6, 7, 8, 9)); |
| |
| tree.MergeConsecutiveSiblings(1, subtractor); // combine last two subtrees |
| EXPECT_THAT(NodeValues(tree), ElementsAre(-1, /* 4 - 5 */ -1)); |
| EXPECT_THAT(NodeValues(tree.Children()[1]), ElementsAre(10, 11, 12, 13)); |
| |
| tree.MergeConsecutiveSiblings(0, subtractor); // combine only two subtrees |
| EXPECT_THAT(NodeValues(tree), ElementsAre(/* -1 - -1 */ 0)); |
| EXPECT_THAT(NodeValues(tree.Children()[0]), |
| ElementsAre(6, 7, 8, 9, 10, 11, 12, 13)); |
| } |
| |
| TEST(VectorTreeTest, RemoveSelfFromParentRoot) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1); |
| EXPECT_DEATH(tree.RemoveSelfFromParent(), ""); |
| } |
| |
| TEST(VectorTreeTest, RemoveSelfFromParentFirstChild) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(2), // no grandchildren |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4), // no grandchildren |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5)); |
| |
| const tree_type expect_tree(1, // |
| // tree_type(2), // deleted |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4), // no grandchildren |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| tree.Children().front().RemoveSelfFromParent(); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, RemoveSelfFromParentMiddleChildWithGrandchildren) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(2), // no grandchildren |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4), // no grandchildren |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5)); |
| |
| const tree_type expect_tree( |
| 1, // |
| tree_type(2), // |
| // tree_type(3, tree_type(8), tree_type(9)), // deleted |
| tree_type(4), // no grandchildren |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| tree.Children()[1].RemoveSelfFromParent(); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, RemoveSelfFromParentMiddleChildWithoutGrandchildren) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(2), // no grandchildren |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4), // no grandchildren |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5)); |
| |
| const tree_type expect_tree(1, // |
| tree_type(2), // |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| // tree_type(4), // deleted |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| tree.Children()[2].RemoveSelfFromParent(); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, RemoveSelfFromParentLastChild) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(2), // no grandchildren |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4), // no grandchildren |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5)); |
| |
| const tree_type expect_tree( |
| 1, // |
| tree_type(2), // |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4) // no grandchildren |
| // tree_type(5, tree_type(12), tree_type(13)) // deleted |
| ); |
| tree.Children().back().RemoveSelfFromParent(); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, FlattenOnceNoChildren) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1); |
| EXPECT_THAT(NodeValues(tree), ElementsAre()); |
| |
| const tree_type expect_tree(1); |
| tree.FlattenOnce(); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, FlattenOnceNoGrandchildren) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // no grandchildren |
| tree_type(2), tree_type(3), tree_type(4), tree_type(5)); |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5)); |
| |
| const tree_type expect_tree(1); |
| tree.FlattenOnce(); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, FlattenOnceOneGrandchild) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, tree_type(2, tree_type(3))); |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2)); |
| |
| const tree_type expect_tree(1, tree_type(3)); |
| tree.FlattenOnce(); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, FlattenOnceMixed) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(2), // no grandchildren |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4), // no grandchildren |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5)); |
| |
| const tree_type expect_tree(1, // |
| tree_type(8), tree_type(9), tree_type(12), |
| tree_type(13)); |
| tree.FlattenOnce(); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, FlattenOnceAllNonempty) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(2, // |
| tree_type(6), tree_type(7)), |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4, // |
| tree_type(10), tree_type(11)), |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5)); |
| |
| const tree_type expect_tree(1, // |
| tree_type(6), tree_type(7), tree_type(8), |
| tree_type(9), tree_type(10), tree_type(11), |
| tree_type(12), tree_type(13)); |
| tree.FlattenOnce(); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, FlattenOnceGreatgrandchildren) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(2, // |
| tree_type(6, // |
| tree_type(7))), |
| tree_type(3, // |
| tree_type(8, // |
| tree_type(9))), |
| tree_type(4, // |
| tree_type(10, // |
| tree_type(11))), |
| tree_type(5, // |
| tree_type(12, // |
| tree_type(13)))); |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5)); |
| |
| const tree_type expect_tree(1, // |
| tree_type(6, // |
| tree_type(7)), |
| tree_type(8, // |
| tree_type(9)), |
| tree_type(10, // |
| tree_type(11)), |
| tree_type(12, // |
| tree_type(13))); |
| tree.FlattenOnce(); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenNoChildren) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1); |
| EXPECT_THAT(NodeValues(tree), ElementsAre()); |
| |
| const tree_type expect_tree(1); |
| std::vector<size_t> new_offsets; |
| tree.FlattenOnlyChildrenWithChildren(&new_offsets); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| EXPECT_TRUE(new_offsets.empty()); |
| } |
| |
| TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenNoChildrenNoOffsets) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1); |
| EXPECT_THAT(NodeValues(tree), ElementsAre()); |
| |
| const tree_type expect_tree(1); |
| tree.FlattenOnlyChildrenWithChildren(/* no offsets */); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenNoGrandchildren) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // no grandchildren |
| tree_type(2), tree_type(3), tree_type(4), tree_type(5)); |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5)); |
| |
| const tree_type expect_tree(1, // all children preserved |
| tree_type(2), tree_type(3), tree_type(4), |
| tree_type(5)); |
| std::vector<size_t> new_offsets; |
| tree.FlattenOnlyChildrenWithChildren(&new_offsets); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| EXPECT_THAT(new_offsets, ElementsAre(0, 1, 2, 3)); |
| } |
| |
| TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenOneGrandchild) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, tree_type(2, tree_type(3))); |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2)); |
| |
| const tree_type expect_tree(1, tree_type(3)); |
| std::vector<size_t> new_offsets; |
| tree.FlattenOnlyChildrenWithChildren(&new_offsets); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| EXPECT_THAT(new_offsets, ElementsAre(0)); |
| } |
| |
| TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenOneGrandchildNoOffsets) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, tree_type(2, tree_type(3))); |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2)); |
| |
| const tree_type expect_tree(1, tree_type(3)); |
| tree.FlattenOnlyChildrenWithChildren(/* no offsets */); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenTwoGrandchildren) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, tree_type(2, tree_type(3), tree_type(7))); |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2)); |
| |
| const tree_type expect_tree(1, tree_type(3), tree_type(7)); |
| std::vector<size_t> new_offsets; |
| tree.FlattenOnlyChildrenWithChildren(&new_offsets); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| EXPECT_THAT(new_offsets, ElementsAre(0)); |
| } |
| |
| TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenMixed) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(2), // no grandchildren |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4), // no grandchildren |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5)); |
| |
| const tree_type expect_tree(1, // |
| tree_type(2), // |
| tree_type(8), tree_type(9), // |
| tree_type(4), // |
| tree_type(12), tree_type(13)); |
| std::vector<size_t> new_offsets; |
| tree.FlattenOnlyChildrenWithChildren(&new_offsets); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| EXPECT_THAT(new_offsets, ElementsAre(0, 1, 3, 4)); |
| } |
| |
| TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenAllNonempty) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(2, // |
| tree_type(6), tree_type(7)), |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4, // |
| tree_type(10), tree_type(11)), |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5)); |
| |
| const tree_type expect_tree(1, // |
| tree_type(6), tree_type(7), tree_type(8), |
| tree_type(9), tree_type(10), tree_type(11), |
| tree_type(12), tree_type(13)); |
| std::vector<size_t> new_offsets; |
| tree.FlattenOnlyChildrenWithChildren(&new_offsets); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| EXPECT_THAT(new_offsets, ElementsAre(0, 2, 4, 6)); |
| } |
| |
| TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenGreatgrandchildren) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(2, // |
| tree_type(6, // |
| tree_type(7))), |
| tree_type(3, // |
| tree_type(8, // |
| tree_type(9))), |
| tree_type(4, // |
| tree_type(10, // |
| tree_type(11))), |
| tree_type(5, // |
| tree_type(12, // |
| tree_type(13)))); |
| EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5)); |
| |
| const tree_type expect_tree(1, // |
| tree_type(6, // |
| tree_type(7)), |
| tree_type(8, // |
| tree_type(9)), |
| tree_type(10, // |
| tree_type(11)), |
| tree_type(12, // |
| tree_type(13))); |
| std::vector<size_t> new_offsets; |
| tree.FlattenOnlyChildrenWithChildren(&new_offsets); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| EXPECT_THAT(new_offsets, ElementsAre(0, 1, 2, 3)); |
| } |
| |
| TEST(VectorTreeTest, FlattenOneChildEmpty) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(4); // no children |
| EXPECT_DEATH(tree.FlattenOneChild(0), ""); |
| } |
| |
| TEST(VectorTreeTest, FlattenOneChildOnlyChildNoGrandchildren) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(4, tree_type(2)); // no grandchildren |
| const tree_type expect_tree(4); |
| tree.FlattenOneChild(0); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, FlattenOneChildOnlyChildOneGrandchild) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(4, tree_type(2, tree_type(11))); // with grandchild |
| const tree_type expect_tree(4, tree_type(11)); |
| tree.FlattenOneChild(0); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, FlattenOneChildFirstChildInFamilyTree) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(2, // |
| tree_type(6), tree_type(7)), |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4, // |
| tree_type(10), tree_type(11)), |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| const tree_type expect_tree(1, // |
| tree_type(6), // |
| tree_type(7), // |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4, // |
| tree_type(10), tree_type(11)), |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| tree.FlattenOneChild(0); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, FlattenOneChildMiddleChildInFamilyTree) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(2, // |
| tree_type(6), tree_type(7)), |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4, // |
| tree_type(10), tree_type(11)), |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| const tree_type expect_tree(1, // |
| tree_type(2, // |
| tree_type(6), tree_type(7)), |
| tree_type(8), // |
| tree_type(9), // |
| tree_type(4, // |
| tree_type(10), tree_type(11)), |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| tree.FlattenOneChild(1); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, FlattenOneChildLastChildInFamilyTree) { |
| typedef VectorTree<int> tree_type; |
| tree_type tree(1, // |
| tree_type(2, // |
| tree_type(6), tree_type(7)), |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4, // |
| tree_type(10), tree_type(11)), |
| tree_type(5, // |
| tree_type(12), tree_type(13))); |
| const tree_type expect_tree(1, // |
| tree_type(2, // |
| tree_type(6), tree_type(7)), |
| tree_type(3, // |
| tree_type(8), tree_type(9)), |
| tree_type(4, // |
| tree_type(10), tree_type(11)), |
| tree_type(12), // |
| tree_type(13)); |
| tree.FlattenOneChild(3); |
| const auto result_pair = DeepEqual(tree, expect_tree); |
| EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left; |
| EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right; |
| } |
| |
| TEST(VectorTreeTest, PrintTree) { |
| const auto tree = verible::testing::MakeExampleFamilyTree(); |
| std::ostringstream stream; |
| stream << tree; |
| EXPECT_EQ(stream.str(), R"({ ((0, 4, grandparent)) |
| { ((0, 2, parent1)) |
| { ((0, 1, child1)) } |
| { ((1, 2, child2)) } |
| } |
| { ((2, 4, parent2)) |
| { ((2, 3, child3)) } |
| { ((3, 4, child4)) } |
| } |
| })"); |
| } |
| |
| } // namespace |
| } // namespace verible |
