Google Git Google Git
Sign in
foss-fpga-tools/third_party/verible/63fe1d16dc81347eb05d26d7ee0a039d12faea95/./common/util/vector_tree_test.cc
blob: 81eb916f457dd08cf729d9475ee1960a89294676 [file]
// 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 "absl/strings/str_cat.h"
#include "absl/strings/str_join.h"
#include "absl/strings/string_view.h"
#include "common/util/tree_operations.h"
#include "common/util/vector_tree_test_util.h"
#include "gmock/gmock.h"
#include "gtest/gtest.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(is_leaf(tree));
EXPECT_EQ(tree.Parent(), nullptr);
EXPECT_EQ(NumAncestors(tree), 0);
EXPECT_EQ(BirthRank(tree), 0); // no parent
EXPECT_TRUE(IsFirstChild(tree));
EXPECT_TRUE(IsLastChild(tree));
EXPECT_EQ(&Root(tree), &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(&LeftmostDescendant(tree), &tree);
EXPECT_EQ(&RightmostDescendant(tree), &tree);
{ // Test const method variants.
const auto& ctree(tree);
EXPECT_EQ(&LeftmostDescendant(ctree), &ctree);
EXPECT_EQ(&RightmostDescendant(ctree), &ctree);
}
}
TEST(VectorTreeTest, RootOnlyHasAncestor) {
VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree());
EXPECT_FALSE(HasAncestor(tree, nullptr));
EXPECT_FALSE(HasAncestor(tree, &tree));
// Separate tree
VectorTreeTestType tree2(verible::testing::MakeRootOnlyExampleTree());
EXPECT_FALSE(HasAncestor(tree2, &tree));
EXPECT_FALSE(HasAncestor(tree, &tree2));
}
TEST(VectorTreeTest, RootOnlyLeafIteration) {
VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree());
EXPECT_EQ(NextLeaf(tree), nullptr);
EXPECT_EQ(PreviousLeaf(tree), nullptr);
{ // const method variants
const auto& ctree(tree);
EXPECT_EQ(NextLeaf(ctree), nullptr);
EXPECT_EQ(PreviousLeaf(ctree), nullptr);
}
}
TEST(VectorTreeTest, RootOnlySiblingIteration) {
VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree());
EXPECT_EQ(verible::NextSibling(tree), nullptr);
EXPECT_EQ(verible::PreviousSibling(tree), nullptr);
{ // const method variants
const auto& ctree(tree);
EXPECT_EQ(verible::NextSibling(ctree), nullptr);
EXPECT_EQ(verible::PreviousSibling(ctree), 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, &ltree);
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 =
Transform<VectorTree<NameOnly>>(tree, NameOnlyConverter);
EXPECT_TRUE(is_leaf(other_tree));
EXPECT_EQ(other_tree.Parent(), nullptr);
EXPECT_EQ(NumAncestors(other_tree), 0);
EXPECT_EQ(BirthRank(other_tree), 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 =
Transform<VectorTree<NameOnly>>(tree, 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 = Transform<VectorTree<NameOnly>>(tree, 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());
{
tree.Children().emplace_back(NamedInterval(1, 2, "child"));
auto* child = &tree.Children().back();
EXPECT_EQ(child->Parent(), &tree);
EXPECT_EQ(&Root(*child), &tree);
EXPECT_TRUE(verible::is_leaf(*child));
const auto& value(child->Value());
EXPECT_EQ(value.left, 1);
EXPECT_EQ(value.right, 2);
EXPECT_EQ(value.name, "child");
ExpectPath(*child, "{0}");
}
{
tree.Children().emplace_back(NamedInterval(2, 3, "lil-bro"));
auto* child = &tree.Children().back();
EXPECT_EQ(child->Parent(), &tree);
EXPECT_EQ(&Root(*child), &tree);
EXPECT_TRUE(verible::is_leaf(*child));
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());
{
tree.Children().emplace_back(NamedInterval(1, 2, "child"));
auto* first_child = &tree.Children().back();
ExpectPath(*first_child, "{0}");
auto& siblings = first_child->Parent()->Children();
siblings.emplace_back(NamedInterval(2, 3, "lil-bro"));
auto* second_child = &siblings.back();
// Recall that emplace_back() may invalidate reference to first_child.
EXPECT_EQ(second_child->Parent(), &tree);
EXPECT_EQ(&Root(*second_child), &tree);
EXPECT_TRUE(verible::is_leaf(*second_child));
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(is_leaf(tree));
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(&Root(child), &tree);
EXPECT_FALSE(is_leaf(child));
EXPECT_EQ(NumAncestors(child), 1);
EXPECT_EQ(BirthRank(child), 0);
EXPECT_TRUE(IsFirstChild(child));
EXPECT_TRUE(IsLastChild(child));
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(verible::NextSibling(child), nullptr);
EXPECT_EQ(verible::PreviousSibling(child), nullptr);
// The invoking node need not be a leaf.
EXPECT_EQ(NextLeaf(child), nullptr);
EXPECT_EQ(PreviousLeaf(child), nullptr);
{
const auto& grandchild = child.Children().front();
EXPECT_EQ(grandchild.Parent(), &child);
EXPECT_EQ(&Root(grandchild), &tree);
EXPECT_TRUE(is_leaf(grandchild));
EXPECT_EQ(NumAncestors(grandchild), 2);
EXPECT_EQ(BirthRank(grandchild), 0);
EXPECT_TRUE(IsFirstChild(grandchild));
EXPECT_TRUE(IsLastChild(grandchild));
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(&LeftmostDescendant(child), &grandchild);
EXPECT_EQ(&RightmostDescendant(child), &grandchild);
EXPECT_EQ(&LeftmostDescendant(tree), &grandchild);
EXPECT_EQ(&RightmostDescendant(tree), &grandchild);
EXPECT_EQ(verible::NextSibling(grandchild), nullptr);
EXPECT_EQ(verible::PreviousSibling(grandchild), nullptr);
// There is still only a single leaf in a one-child tree,
// thus next and previous do not exist.
EXPECT_EQ(NextLeaf(grandchild), nullptr);
EXPECT_EQ(PreviousLeaf(grandchild), nullptr);
}
}
}
TEST(VectorTreeTest, OneChildPolicyHasAncestor) {
const auto tree = verible::testing::MakeOneChildPolicyExampleTree();
{
const auto& child = tree.Children().front();
EXPECT_FALSE(HasAncestor(tree, &child));
EXPECT_TRUE(HasAncestor(child, &tree));
{
const auto& grandchild = child.Children().front();
EXPECT_FALSE(HasAncestor(child, &grandchild));
EXPECT_TRUE(HasAncestor(grandchild, &child));
EXPECT_FALSE(HasAncestor(tree, &grandchild));
EXPECT_TRUE(HasAncestor(grandchild, &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 = Transform<VectorTree<NameOnly>>(ltree, 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 = DescendPath(ltree, path.begin(), path.end());
auto& rchild = DescendPath(rtree, 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(&Root(tree), &tree);
EXPECT_FALSE(is_leaf(tree));
EXPECT_EQ(NumAncestors(tree), 0);
EXPECT_EQ(BirthRank(tree), 0);
const auto tree_path = MakePath(tree);
EXPECT_TRUE(tree_path.empty());
EXPECT_EQ(&DescendPath(tree, 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(&Root(child), &tree);
EXPECT_FALSE(is_leaf(child));
EXPECT_EQ(NumAncestors(child), 1);
EXPECT_EQ(BirthRank(child), i);
EXPECT_EQ(IsFirstChild(child), i == 0);
EXPECT_EQ(IsLastChild(child), i == 1);
const auto child_path = MakePath(child);
EXPECT_THAT(child_path, ElementsAre(i));
EXPECT_EQ(&DescendPath(tree, 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(&Root(grandchild), &tree);
EXPECT_TRUE(is_leaf(grandchild));
EXPECT_EQ(NumAncestors(grandchild), 2);
EXPECT_EQ(BirthRank(grandchild), j);
EXPECT_EQ(IsFirstChild(grandchild), j == 0);
EXPECT_EQ(IsLastChild(grandchild), 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(&DescendPath(tree, begin, end), &grandchild);
EXPECT_EQ(&DescendPath(child, 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(&LeftmostDescendant(tree),
&DescendPath(tree, left_path.begin(), left_path.end()));
EXPECT_EQ(&RightmostDescendant(tree),
&DescendPath(tree, right_path.begin(), right_path.end()));
}
{ // Test const method variants.
const auto& ctree(tree);
EXPECT_EQ(&LeftmostDescendant(ctree),
&DescendPath(ctree, left_path.begin(), left_path.end()));
EXPECT_EQ(&RightmostDescendant(ctree),
&DescendPath(ctree, right_path.begin(), right_path.end()));
}
}
TEST(VectorTreeTest, FamilyTreeHasAncestor) {
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(HasAncestor(tree, &child_0));
EXPECT_FALSE(HasAncestor(tree, &child_1));
EXPECT_FALSE(HasAncestor(tree, &grandchild_00));
EXPECT_FALSE(HasAncestor(tree, &grandchild_01));
EXPECT_FALSE(HasAncestor(tree, &grandchild_10));
EXPECT_FALSE(HasAncestor(tree, &grandchild_11));
EXPECT_TRUE(HasAncestor(child_0, &tree));
EXPECT_TRUE(HasAncestor(child_1, &tree));
EXPECT_TRUE(HasAncestor(grandchild_00, &tree));
EXPECT_TRUE(HasAncestor(grandchild_01, &tree));
EXPECT_TRUE(HasAncestor(grandchild_10, &tree));
EXPECT_TRUE(HasAncestor(grandchild_11, &tree));
EXPECT_FALSE(HasAncestor(child_0, &child_1));
EXPECT_FALSE(HasAncestor(child_1, &child_0));
EXPECT_FALSE(HasAncestor(child_0, &grandchild_00));
EXPECT_FALSE(HasAncestor(child_0, &grandchild_01));
EXPECT_FALSE(HasAncestor(child_0, &grandchild_10));
EXPECT_FALSE(HasAncestor(child_0, &grandchild_11));
EXPECT_FALSE(HasAncestor(child_1, &grandchild_00));
EXPECT_FALSE(HasAncestor(child_1, &grandchild_01));
EXPECT_FALSE(HasAncestor(child_1, &grandchild_10));
EXPECT_FALSE(HasAncestor(child_1, &grandchild_11));
EXPECT_TRUE(HasAncestor(grandchild_00, &child_0));
EXPECT_FALSE(HasAncestor(grandchild_00, &child_1));
EXPECT_TRUE(HasAncestor(grandchild_01, &child_0));
EXPECT_FALSE(HasAncestor(grandchild_01, &child_1));
EXPECT_FALSE(HasAncestor(grandchild_10, &child_0));
EXPECT_TRUE(HasAncestor(grandchild_10, &child_1));
EXPECT_FALSE(HasAncestor(grandchild_11, &child_0));
EXPECT_TRUE(HasAncestor(grandchild_11, &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(verible::NextSibling(child_0), &child_1);
EXPECT_EQ(verible::NextSibling(child_1), nullptr);
EXPECT_EQ(verible::PreviousSibling(child_0), nullptr);
EXPECT_EQ(verible::PreviousSibling(child_1), &child_0);
// Verify grandchild generation.
EXPECT_EQ(verible::NextSibling(grandchild_00), &grandchild_01);
EXPECT_EQ(verible::NextSibling(grandchild_01), nullptr);
EXPECT_EQ(verible::NextSibling(grandchild_10), &grandchild_11);
EXPECT_EQ(verible::NextSibling(grandchild_11), nullptr);
EXPECT_EQ(verible::PreviousSibling(grandchild_00), nullptr);
EXPECT_EQ(verible::PreviousSibling(grandchild_01), &grandchild_00);
EXPECT_EQ(verible::PreviousSibling(grandchild_10), nullptr);
EXPECT_EQ(verible::PreviousSibling(grandchild_11), &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(verible::NextSibling(cchild_0), &cchild_1);
EXPECT_EQ(verible::NextSibling(cchild_1), nullptr);
EXPECT_EQ(verible::PreviousSibling(cchild_0), nullptr);
EXPECT_EQ(verible::PreviousSibling(cchild_1), &cchild_0);
// Verify grandchild generation.
EXPECT_EQ(verible::NextSibling(cgrandchild_00), &cgrandchild_01);
EXPECT_EQ(verible::NextSibling(cgrandchild_01), nullptr);
EXPECT_EQ(verible::NextSibling(cgrandchild_10), &cgrandchild_11);
EXPECT_EQ(verible::NextSibling(cgrandchild_11), nullptr);
EXPECT_EQ(verible::PreviousSibling(cgrandchild_00), nullptr);
EXPECT_EQ(verible::PreviousSibling(cgrandchild_01), &cgrandchild_00);
EXPECT_EQ(verible::PreviousSibling(cgrandchild_10), nullptr);
EXPECT_EQ(verible::PreviousSibling(cgrandchild_11), &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(NextLeaf(grandchild_00), &grandchild_01);
EXPECT_EQ(NextLeaf(grandchild_01), &grandchild_10);
EXPECT_EQ(NextLeaf(grandchild_10), &grandchild_11);
EXPECT_EQ(NextLeaf(grandchild_11), nullptr);
// Verify reverse links.
EXPECT_EQ(PreviousLeaf(grandchild_00), nullptr);
EXPECT_EQ(PreviousLeaf(grandchild_01), &grandchild_00);
EXPECT_EQ(PreviousLeaf(grandchild_10), &grandchild_01);
EXPECT_EQ(PreviousLeaf(grandchild_11), &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(NextLeaf(cgrandchild_00), &cgrandchild_01);
EXPECT_EQ(NextLeaf(cgrandchild_01), &cgrandchild_10);
EXPECT_EQ(NextLeaf(cgrandchild_10), &cgrandchild_11);
EXPECT_EQ(NextLeaf(cgrandchild_11), nullptr);
// Verify reverse links.
EXPECT_EQ(PreviousLeaf(cgrandchild_00), nullptr);
EXPECT_EQ(PreviousLeaf(cgrandchild_01), &cgrandchild_00);
EXPECT_EQ(PreviousLeaf(cgrandchild_10), &cgrandchild_01);
EXPECT_EQ(PreviousLeaf(cgrandchild_11), &cgrandchild_10);
}
}
TEST(VectorTreeTest, FamilyTreeMembersTransformed) {
const auto orig_tree = verible::testing::MakeExampleFamilyTree();
const auto tree =
Transform<VectorTree<NameOnly>>(orig_tree, 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 = DescendPath(ltree, path.begin(), path.end());
auto& rchild = DescendPath(rtree, 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 = DescendPath(ltree, path.begin(), path.end());
auto& rchild = DescendPath(rtree, path.begin(), path.end());
rchild.Children().emplace_back(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 = DescendPath(ltree, path.begin(), path.end() - 1);
const auto& rparent = DescendPath(rtree, path.begin(), path.end() - 1);
auto& rchild = DescendPath(rtree, path.begin(), path.end());
rchild.Parent()->Children().emplace_back(
NamedInterval(8, 9, "black-sheep"));
// Note: `rchild` may have been moved and invalidated due to realloc.
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 = DescendPath(ltree, path.begin(), path.end());
auto& rchild = DescendPath(rtree, 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 = DescendPath(ltree, path.begin(), path.end());
auto& rchild = DescendPath(rtree, 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(NearestCommonAncestor(tree1, tree2), nullptr);
EXPECT_EQ(NearestCommonAncestor(tree2, tree1), nullptr);
}
TEST(VectorTreeTest, NearestCommonAncestorNoneConst) {
typedef VectorTree<int> tree_type;
const tree_type tree1{0}, tree2{0};
EXPECT_EQ(NearestCommonAncestor(tree1, tree2), nullptr);
EXPECT_EQ(NearestCommonAncestor(tree2, tree1), nullptr);
}
TEST(VectorTreeTest, NearestCommonAncestorSameMutable) {
typedef VectorTree<int> tree_type;
tree_type tree{0};
EXPECT_EQ(NearestCommonAncestor(tree, tree), &tree);
EXPECT_EQ(NearestCommonAncestor(tree, tree), &tree);
}
TEST(VectorTreeTest, NearestCommonAncestorSameConst) {
typedef VectorTree<int> tree_type;
const tree_type tree{0};
EXPECT_EQ(NearestCommonAncestor(tree, tree), &tree);
EXPECT_EQ(NearestCommonAncestor(tree, 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 = DescendPath(tree, path.begin(), path.end());
EXPECT_EQ(NearestCommonAncestor(tree, child), &tree);
EXPECT_EQ(NearestCommonAncestor(child, tree), &tree);
}
for (int j = 0; j < 2; ++j) {
const auto path = {i, j};
auto& grandchild = DescendPath(tree, path.begin(), path.end());
EXPECT_EQ(NearestCommonAncestor(tree, grandchild), &tree);
EXPECT_EQ(NearestCommonAncestor(grandchild, 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(NearestCommonAncestor(left, right), &tree);
EXPECT_EQ(NearestCommonAncestor(right, left), &tree);
for (int i = 0; i < 2; ++i) {
{
const auto left_path = {0, i};
auto& left_grandchild =
DescendPath(tree, left_path.begin(), left_path.end());
EXPECT_EQ(NearestCommonAncestor(left, left_grandchild), &left);
EXPECT_EQ(NearestCommonAncestor(left_grandchild, left), &left);
EXPECT_EQ(NearestCommonAncestor(right, left_grandchild), &tree);
EXPECT_EQ(NearestCommonAncestor(left_grandchild, right), &tree);
}
{
const auto right_path = {1, i};
auto& right_grandchild =
DescendPath(tree, right_path.begin(), right_path.end());
EXPECT_EQ(NearestCommonAncestor(right, right_grandchild), &right);
EXPECT_EQ(NearestCommonAncestor(right_grandchild, right), &right);
EXPECT_EQ(NearestCommonAncestor(left, right_grandchild), &tree);
EXPECT_EQ(NearestCommonAncestor(right_grandchild, left), &tree);
}
}
}
TEST(VectorTreeTest, ApplyPreOrderPrint) {
const auto tree = verible::testing::MakeExampleFamilyTree();
std::ostringstream stream;
ApplyPreOrder(tree, [&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 =
Transform<VectorTree<NameOnly>>(orig_tree, NameOnlyConverter);
std::ostringstream stream;
ApplyPreOrder(tree, [&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;
ApplyPostOrder(tree, [&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.
ApplyPreOrder(tree, verible::testing::VerifyInterval);
}
TEST(VectorTreeTest, ApplyPostOrderVerify) {
const auto tree = verible::testing::MakeExampleFamilyTree();
// Verify invariant at every node.
ApplyPostOrder(tree, verible::testing::VerifyInterval);
}
TEST(VectorTreeTest, ApplyPreOrderTransformValue) {
auto tree = verible::testing::MakeExampleFamilyTree();
// Transform intervals.
std::vector<absl::string_view> visit_order;
const int shift = 2;
ApplyPreOrder(tree, [=, &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;
ApplyPreOrder(tree, [&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;
ApplyPreOrder(tree, [=, &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;
ApplyPreOrder(tree, [&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;
ApplyPostOrder(tree, [=, &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;
ApplyPostOrder(tree, [&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;
ApplyPostOrder(tree, [=, &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;
ApplyPostOrder(tree, [&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(HoistOnlyChild(tree));
EXPECT_TRUE(is_leaf(tree));
EXPECT_EQ(tree.Parent(), nullptr);
EXPECT_EQ(NumAncestors(tree), 0);
EXPECT_EQ(BirthRank(tree), 0); // no parent
EXPECT_EQ(&Root(tree), &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(HoistOnlyChild(tree));
{
const auto& child = tree;
EXPECT_EQ(child.Parent(), nullptr);
EXPECT_EQ(&Root(child), &tree);
EXPECT_FALSE(is_leaf(child));
EXPECT_EQ(NumAncestors(child), 0);
EXPECT_EQ(BirthRank(child), 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(verible::NextSibling(child), nullptr);
EXPECT_EQ(verible::PreviousSibling(child), nullptr);
// The invoking node need not be a leaf.
EXPECT_EQ(NextLeaf(child), nullptr);
EXPECT_EQ(PreviousLeaf(child), nullptr);
{
const auto& grandchild = child.Children().front();
EXPECT_EQ(grandchild.Parent(), &child);
EXPECT_EQ(&Root(grandchild), &tree);
EXPECT_TRUE(is_leaf(grandchild));
EXPECT_EQ(NumAncestors(grandchild), 1);
EXPECT_EQ(BirthRank(grandchild), 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(&LeftmostDescendant(child), &grandchild);
EXPECT_EQ(&RightmostDescendant(child), &grandchild);
EXPECT_EQ(&LeftmostDescendant(tree), &grandchild);
EXPECT_EQ(&RightmostDescendant(tree), &grandchild);
EXPECT_EQ(verible::NextSibling(grandchild), nullptr);
EXPECT_EQ(verible::PreviousSibling(grandchild), nullptr);
// There is still only a single leaf in a one-child tree,
// thus next and previous do not exist.
EXPECT_EQ(NextLeaf(grandchild), nullptr);
EXPECT_EQ(PreviousLeaf(grandchild), nullptr);
}
}
}
TEST(VectorTreeTest, HoistOnlyChildOneChildTreeMiddleAncestor) {
VectorTreeTestType tree(verible::testing::MakeOneChildPolicyExampleTree());
EXPECT_TRUE(HoistOnlyChild(tree.Children().front()));
{
const auto& value = tree.Value();
EXPECT_EQ(value.left, 0);
EXPECT_EQ(value.right, 3);
EXPECT_EQ(value.name, "root");
EXPECT_EQ(verible::NextSibling(tree), nullptr);
EXPECT_EQ(verible::PreviousSibling(tree), nullptr);
// The invoking node need not be a leaf.
EXPECT_EQ(NextLeaf(tree), nullptr);
EXPECT_EQ(PreviousLeaf(tree), 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(&Root(grandchild), &tree);
EXPECT_TRUE(is_leaf(grandchild));
EXPECT_EQ(NumAncestors(grandchild), 1);
EXPECT_EQ(BirthRank(grandchild), 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(&LeftmostDescendant(tree), &grandchild);
EXPECT_EQ(&RightmostDescendant(tree), &grandchild);
EXPECT_EQ(verible::NextSibling(grandchild), nullptr);
EXPECT_EQ(verible::PreviousSibling(grandchild), nullptr);
// There is still only a single leaf in a one-child tree,
// thus next and previous do not exist.
EXPECT_EQ(NextLeaf(grandchild), nullptr);
EXPECT_EQ(PreviousLeaf(grandchild), nullptr);
}
}
}
TEST(VectorTreeTest, HoistOnlyChildFamilyTree) {
VectorTreeTestType tree(verible::testing::MakeExampleFamilyTree());
// No change because each generation has more than one child.
EXPECT_FALSE(HoistOnlyChild(tree));
}
// 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(is_leaf(tree1));
EXPECT_TRUE(is_leaf(tree2));
AdoptSubtreesFrom(tree1, &tree2);
EXPECT_TRUE(is_leaf(tree1));
EXPECT_TRUE(is_leaf(tree2));
}
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());
AdoptSubtreesFrom(tree1, &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));
AdoptSubtreesFrom(tree1, &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));
AdoptSubtreesFrom(tree1, &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(MergeConsecutiveSiblings(tree, 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(MergeConsecutiveSiblings(tree, 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";
MergeConsecutiveSiblings(tree, 1, adder); // combine middle two subtrees
EXPECT_THAT(NodeValues(tree), ElementsAre(2, 7, 5));
VLOG(1) << __FUNCTION__ << ": after first merge";
MergeConsecutiveSiblings(tree, 1, adder); // combine last two subtrees
EXPECT_THAT(NodeValues(tree), ElementsAre(2, 12));
VLOG(1) << __FUNCTION__ << ": after second merge";
MergeConsecutiveSiblings(tree, 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));
MergeConsecutiveSiblings(tree, 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));
MergeConsecutiveSiblings(tree, 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));
MergeConsecutiveSiblings(tree, 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));
MergeConsecutiveSiblings(tree, 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(RemoveSelfFromParent(tree), "");
}
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)));
RemoveSelfFromParent(tree.Children().front());
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)));
RemoveSelfFromParent(tree.Children()[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, 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)));
RemoveSelfFromParent(tree.Children()[2]);
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
);
RemoveSelfFromParent(tree.Children().back());
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);
FlattenOnce(tree);
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);
FlattenOnce(tree);
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));
FlattenOnce(tree);
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));
FlattenOnce(tree);
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));
FlattenOnce(tree);
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)));
FlattenOnce(tree);
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;
FlattenOnlyChildrenWithChildren(tree, &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);
FlattenOnlyChildrenWithChildren(tree /* 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;
FlattenOnlyChildrenWithChildren(tree, &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;
FlattenOnlyChildrenWithChildren(tree, &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));
FlattenOnlyChildrenWithChildren(tree /* 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;
FlattenOnlyChildrenWithChildren(tree, &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;
FlattenOnlyChildrenWithChildren(tree, &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;
FlattenOnlyChildrenWithChildren(tree, &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;
FlattenOnlyChildrenWithChildren(tree, &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(FlattenOneChild(tree, 0), "");
}
TEST(VectorTreeTest, FlattenOneChildOnlyChildNoGrandchildren) {
typedef VectorTree<int> tree_type;
tree_type tree(4, tree_type(2)); // no grandchildren
const tree_type expect_tree(4);
FlattenOneChild(tree, 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));
FlattenOneChild(tree, 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)));
FlattenOneChild(tree, 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)));
FlattenOneChild(tree, 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));
FlattenOneChild(tree, 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)) }
}
})");
}
TEST(VectorTreeTest, PrintTreeCustom) {
const auto tree = verible::testing::MakeExampleFamilyTree();
std::ostringstream stream;
PrintTree(tree, &stream,
[](std::ostream& s,
const decltype(tree)::value_type& value) -> std::ostream& {
return s << value.name; // print only the name field
});
EXPECT_EQ(stream.str(), R"({ (grandparent)
{ (parent1)
{ (child1) }
{ (child2) }
}
{ (parent2)
{ (child3) }
{ (child4) }
}
})");
}
TEST(VectorTreeTest, ChildrenManipulation) {
VectorTreeTestType tree(verible::testing::MakeExampleFamilyTree());
auto& children_gp = tree.Children();
children_gp.push_back(VectorTreeTestType(NamedInterval(4, 6, "parent3")));
EXPECT_EQ(tree.Children().size(), 3);
EXPECT_EQ(tree.Children().back().Value(), NamedInterval(4, 6, "parent3"));
EXPECT_EQ(tree.Children().back().Parent(), &tree);
auto& p3 = tree.Children().back();
auto& children_p3 = p3.Children();
children_p3.push_back(VectorTreeTestType(NamedInterval(4, 5, "child5")));
children_p3.emplace_back(NamedInterval(5, 6, "child6"));
EXPECT_EQ(p3.Children().size(), 2);
EXPECT_EQ(p3.Children().at(0).Value(), NamedInterval(4, 5, "child5"));
EXPECT_EQ(p3.Children().at(0).Parent(), &p3);
EXPECT_EQ(p3.Children().at(1).Value(), NamedInterval(5, 6, "child6"));
EXPECT_EQ(p3.Children().at(1).Parent(), &p3);
auto& p2 = tree.Children().at(1);
const NamedInterval original_p2_children[] = {
p2.Children().at(0).Value(),
p2.Children().at(1).Value(),
};
children_p3.insert(children_p3.begin(), p2.Children().begin(),
p2.Children().end());
EXPECT_EQ(p3.Children().size(), 4);
EXPECT_EQ(p3.Children().at(0).Value(), original_p2_children[0]);
EXPECT_EQ(p3.Children().at(0).Parent(), &p3);
EXPECT_EQ(p3.Children().at(1).Value(), original_p2_children[1]);
EXPECT_EQ(p3.Children().at(1).Parent(), &p3);
EXPECT_EQ(p3.Children().at(2).Value(), NamedInterval(4, 5, "child5"));
EXPECT_EQ(p3.Children().at(2).Parent(), &p3);
EXPECT_EQ(p3.Children().at(3).Value(), NamedInterval(5, 6, "child6"));
EXPECT_EQ(p3.Children().at(3).Parent(), &p3);
EXPECT_EQ(p2.Children().size(), 2);
EXPECT_EQ(p2.Children().at(0).Value(), original_p2_children[0]);
EXPECT_EQ(p2.Children().at(0).Parent(), &p2);
EXPECT_EQ(p2.Children().at(1).Value(), original_p2_children[1]);
EXPECT_EQ(p2.Children().at(1).Parent(), &p2);
p2.Children().clear();
EXPECT_EQ(p2.Children().size(), 0);
p2.Children().assign({
VectorTreeTestType(NamedInterval(0, 1, "foo")),
VectorTreeTestType(NamedInterval(1, 2, "bar")),
VectorTreeTestType(NamedInterval(2, 3, "baz")),
});
EXPECT_EQ(p2.Children().size(), 3);
EXPECT_EQ(p2.Children().at(0).Value(), NamedInterval(0, 1, "foo"));
EXPECT_EQ(p2.Children().at(0).Parent(), &p2);
EXPECT_EQ(p2.Children().at(1).Value(), NamedInterval(1, 2, "bar"));
EXPECT_EQ(p2.Children().at(1).Parent(), &p2);
EXPECT_EQ(p2.Children().at(2).Value(), NamedInterval(2, 3, "baz"));
EXPECT_EQ(p2.Children().at(2).Parent(), &p2);
tree.Children().clear();
EXPECT_TRUE(tree.Children().empty());
}
} // namespace
} // namespace verible