| // Copyright 2017-2021 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_iterators.h" | |
| #include <cstddef> | |
| #include <iterator> | |
| #include <sstream> | |
| #include <type_traits> | |
| #include <vector> | |
| #include "absl/strings/str_join.h" | |
| #include "common/util/tree_operations.h" | |
| #include "common/util/vector_tree.h" | |
| #include "gmock/gmock.h" | |
| #include "gtest/gtest.h" | |
| namespace verible { | |
| // Iterator value printers used by Google Test | |
| template <typename TreeType> | |
| static void PrintTo(const VectorTreeLeavesIterator<TreeType>& it, | |
| std::ostream* os) { | |
| *os << "VectorTreeLeavesIterator(" << *it << ")"; | |
| } | |
| template <typename TreeType> | |
| static void PrintTo(const VectorTreePreOrderIterator<TreeType>& it, | |
| std::ostream* os) { | |
| *os << "VectorTreePreOrderIterator(" << *it << ")"; | |
| } | |
| template <typename TreeType> | |
| static void PrintTo(const VectorTreePostOrderIterator<TreeType>& it, | |
| std::ostream* os) { | |
| *os << "VectorTreePostOrderIterator(" << *it << ")"; | |
| } | |
| namespace { | |
| using Tree = verible::VectorTree<int>; | |
| template <typename Iterator, typename TreeType> | |
| void ExpectForwardIterator(TreeType* node, TreeType* next_node) { | |
| EXPECT_TRUE(std::is_default_constructible_v<Iterator>); | |
| EXPECT_TRUE(std::is_copy_constructible_v<Iterator>); | |
| EXPECT_TRUE(std::is_copy_assignable_v<Iterator>); | |
| EXPECT_TRUE(std::is_destructible_v<Iterator>); | |
| EXPECT_TRUE(std::is_swappable_v<Iterator>); | |
| Iterator node_it(node), next_node_it(next_node); | |
| Iterator node_it_2(node); | |
| // i == j | |
| EXPECT_TRUE(node_it == node_it_2); | |
| // i != j | |
| EXPECT_TRUE(node_it != next_node_it); | |
| // *i | |
| EXPECT_EQ(&(*node_it), node); | |
| EXPECT_EQ(&(*next_node_it), next_node); | |
| // i->member | |
| EXPECT_EQ(next_node_it->Value(), next_node->Value()); | |
| // ++i | |
| { | |
| auto i = node_it; | |
| EXPECT_EQ(++i, next_node_it); | |
| EXPECT_EQ(i, next_node_it); | |
| EXPECT_NE(i, node_it); | |
| } | |
| // i++ | |
| { | |
| auto i = node_it; | |
| EXPECT_EQ(i++, node_it); | |
| EXPECT_EQ(i, next_node_it); | |
| EXPECT_NE(i, node_it); | |
| } | |
| // *i++ | |
| { | |
| auto i = node_it; | |
| EXPECT_EQ(&(*i++), node); | |
| EXPECT_EQ(i, next_node_it); | |
| EXPECT_NE(i, node_it); | |
| } | |
| if constexpr (!std::is_const_v<typename Iterator::value_type>) { | |
| auto tree = Tree(0, // | |
| Tree(1), // | |
| Tree(2)); | |
| auto other_tree = Tree(200, // | |
| Tree(2001), // | |
| Tree(2002)); | |
| auto it = Iterator(&tree.Children()[1]); | |
| // *i = j | |
| *it = other_tree; | |
| EXPECT_EQ(tree.Children()[1].Value(), 200); | |
| } | |
| } | |
| TEST(VectorTreeIteratorTest, ForwardIteratorInterface) { | |
| auto tree = Tree(0, // | |
| Tree(1), // | |
| Tree(2, // | |
| Tree(21), // | |
| Tree(22), // | |
| Tree(23)), // | |
| Tree(3)); | |
| ExpectForwardIterator<VectorTreeLeavesIterator<Tree>>( | |
| &tree.Children()[0], &tree.Children()[1].Children()[0]); | |
| ExpectForwardIterator<VectorTreeLeavesIterator<const Tree>>( | |
| &tree.Children()[0], &tree.Children()[1].Children()[0]); | |
| ExpectForwardIterator<VectorTreePreOrderIterator<Tree>>(&tree.Children()[0], | |
| &tree.Children()[1]); | |
| ExpectForwardIterator<VectorTreePreOrderIterator<const Tree>>( | |
| &tree.Children()[0], &tree.Children()[1]); | |
| ExpectForwardIterator<VectorTreePostOrderIterator<Tree>>( | |
| &tree.Children()[0], &tree.Children()[1].Children()[0]); | |
| ExpectForwardIterator<VectorTreePostOrderIterator<const Tree>>( | |
| &tree.Children()[0], &tree.Children()[1].Children()[0]); | |
| } | |
| struct TestCaseData { | |
| Tree tree; | |
| // RootNodeTraversal test data | |
| struct { | |
| std::vector<int> expected_sequence_leaves; | |
| std::vector<int> expected_sequence_pre_order; | |
| std::vector<int> expected_sequence_post_order; | |
| } root_node_traversal; | |
| // SubtreeTraversal and IteratorSubtreeTraversal test data | |
| struct { | |
| std::vector<size_t> subtree_path; | |
| std::vector<int> expected_sequence_leaves; | |
| std::vector<int> expected_sequence_pre_order; | |
| std::vector<int> expected_sequence_post_order; | |
| } subtree_traversal; | |
| }; | |
| static const TestCaseData kTestCasesData[] = { | |
| { | |
| Tree(0), | |
| // RootNodeTraversal test data | |
| { | |
| {0}, | |
| {0}, | |
| {0}, | |
| }, | |
| // SubtreeTraversal and IteratorSubtreeTraversal test data (skipped) | |
| {}, | |
| }, | |
| { | |
| Tree(0, // | |
| Tree(1), // | |
| Tree(2), // | |
| Tree(3)), | |
| // RootNodeTraversal test data | |
| { | |
| {1, 2, 3}, | |
| {0, 1, 2, 3}, | |
| {1, 2, 3, 0}, | |
| }, | |
| // SubtreeTraversal and IteratorSubtreeTraversal test data | |
| { | |
| {0}, // subtree path | |
| {1}, | |
| {1}, | |
| {1}, | |
| }, | |
| }, | |
| { | |
| Tree(0, // | |
| Tree(1, // | |
| Tree(11, // | |
| Tree(111, // | |
| Tree(1111))))), | |
| // RootNodeTraversal test data | |
| { | |
| {1111}, | |
| {0, 1, 11, 111, 1111}, | |
| {1111, 111, 11, 1, 0}, | |
| }, | |
| // SubtreeTraversal and IteratorSubtreeTraversal test data | |
| { | |
| {0, 0}, // subtree path | |
| {1111}, | |
| {11, 111, 1111}, | |
| {1111, 111, 11}, | |
| }, | |
| }, | |
| { | |
| Tree(0, // | |
| Tree(1, // | |
| Tree(11, // | |
| Tree(111), // | |
| Tree(112)), // | |
| Tree(12), // | |
| Tree(13)), // | |
| Tree(2, // | |
| Tree(21), // | |
| Tree(22), // | |
| Tree(23, // | |
| Tree(231), // | |
| Tree(232))), // | |
| Tree(3)), | |
| // RootNodeTraversal test data | |
| { | |
| {111, 112, 12, 13, 21, 22, 231, 232, 3}, | |
| {0, 1, 11, 111, 112, 12, 13, 2, 21, 22, 23, 231, 232, 3}, | |
| {111, 112, 11, 12, 13, 1, 21, 22, 231, 232, 23, 2, 3, 0}, | |
| }, | |
| // SubtreeTraversal and IteratorSubtreeTraversal test data | |
| { | |
| {0}, // subtree path | |
| {111, 112, 12, 13}, | |
| {1, 11, 111, 112, 12, 13}, | |
| {111, 112, 11, 12, 13, 1}, | |
| }, | |
| }, | |
| { | |
| Tree(0, // | |
| Tree(1), // | |
| Tree(2, // | |
| Tree(21, // | |
| Tree(211), // | |
| Tree(212)), // | |
| Tree(22), // | |
| Tree(23)), // | |
| Tree(3, // | |
| Tree(31), // | |
| Tree(32), // | |
| Tree(33, // | |
| Tree(331), // | |
| Tree(332)))), | |
| // RootNodeTraversal test data | |
| { | |
| {1, 211, 212, 22, 23, 31, 32, 331, 332}, | |
| {0, 1, 2, 21, 211, 212, 22, 23, 3, 31, 32, 33, 331, 332}, | |
| {1, 211, 212, 21, 22, 23, 2, 31, 32, 331, 332, 33, 3, 0}, | |
| }, | |
| // SubtreeTraversal and IteratorSubtreeTraversal test data | |
| { | |
| {2}, // subtree path | |
| {31, 32, 331, 332}, | |
| {3, 31, 32, 33, 331, 332}, | |
| {31, 32, 331, 332, 33, 3}, | |
| }, | |
| }, | |
| }; | |
| template <typename NodesRange, typename ValuesRange> | |
| void ExpectNodesRangesValuesEq(const NodesRange& nodes, | |
| const ValuesRange& expected_values) { | |
| auto expected_it = expected_values.begin(); | |
| for (const auto& node : nodes) { | |
| EXPECT_NE(expected_it, expected_values.end()); | |
| EXPECT_EQ(node.Value(), *expected_it); | |
| ++expected_it; | |
| } | |
| EXPECT_EQ(expected_it, expected_values.end()); | |
| } | |
| TEST(VectorTreeIteratorTest, RootNodeTraversal) { | |
| for (const auto& data : kTestCasesData) { | |
| std::ostringstream trace_msg; | |
| trace_msg << "Input tree:\n" << data.tree; | |
| SCOPED_TRACE(trace_msg.str()); | |
| { | |
| SCOPED_TRACE("VectorTreeLeavesTraversal"); | |
| ExpectNodesRangesValuesEq( | |
| VectorTreeLeavesTraversal(data.tree), | |
| data.root_node_traversal.expected_sequence_leaves); | |
| } | |
| { | |
| SCOPED_TRACE("VectorTreePreOrderTraversal"); | |
| ExpectNodesRangesValuesEq( | |
| VectorTreePreOrderTraversal(data.tree), | |
| data.root_node_traversal.expected_sequence_pre_order); | |
| } | |
| { | |
| SCOPED_TRACE("VectorTreePostOrderTraversal"); | |
| ExpectNodesRangesValuesEq( | |
| VectorTreePostOrderTraversal(data.tree), | |
| data.root_node_traversal.expected_sequence_post_order); | |
| } | |
| } | |
| } | |
| TEST(VectorTreeIteratorTest, SubtreeTraversal) { | |
| for (const auto& data : kTestCasesData) { | |
| const auto subtree_path = data.subtree_traversal.subtree_path; | |
| if (subtree_path.empty()) continue; | |
| const auto& subtree = | |
| DescendPath(data.tree, subtree_path.begin(), subtree_path.end()); | |
| std::ostringstream trace_msg; | |
| trace_msg << "Input tree:\n" | |
| << data.tree | |
| << "\nSubtree path: " << absl::StrJoin(subtree_path, "."); | |
| SCOPED_TRACE(trace_msg.str()); | |
| { | |
| SCOPED_TRACE("VectorTreeLeavesTraversal"); | |
| ExpectNodesRangesValuesEq( | |
| VectorTreeLeavesTraversal(subtree), | |
| data.subtree_traversal.expected_sequence_leaves); | |
| } | |
| { | |
| SCOPED_TRACE("VectorTreePreOrderTraversal"); | |
| ExpectNodesRangesValuesEq( | |
| VectorTreePreOrderTraversal(subtree), | |
| data.subtree_traversal.expected_sequence_pre_order); | |
| } | |
| { | |
| SCOPED_TRACE("VectorTreePostOrderTraversal"); | |
| ExpectNodesRangesValuesEq( | |
| VectorTreePostOrderTraversal(subtree), | |
| data.subtree_traversal.expected_sequence_post_order); | |
| } | |
| } | |
| } | |
| TEST(VectorTreeIteratorTest, IteratorSubtreeTraversal) { | |
| for (const auto& data : kTestCasesData) { | |
| const auto subtree_path = data.subtree_traversal.subtree_path; | |
| if (subtree_path.empty()) continue; | |
| const auto& subtree = | |
| DescendPath(data.tree, subtree_path.begin(), subtree_path.end()); | |
| std::ostringstream trace_msg; | |
| trace_msg << "Input tree:\n" | |
| << data.tree | |
| << "\nSubtree path: " << absl::StrJoin(subtree_path, "."); | |
| SCOPED_TRACE(trace_msg.str()); | |
| // VectorTreeLeavesIterator doesn't support subranges | |
| { | |
| SCOPED_TRACE("VectorTreePreOrderIterator"); | |
| ExpectNodesRangesValuesEq( | |
| VectorTreePreOrderIterator(&subtree), | |
| data.subtree_traversal.expected_sequence_pre_order); | |
| } | |
| { | |
| SCOPED_TRACE("VectorTreePostOrderIterator"); | |
| ExpectNodesRangesValuesEq( | |
| VectorTreePostOrderIterator(&subtree), | |
| data.subtree_traversal.expected_sequence_post_order); | |
| } | |
| } | |
| } | |
| } // namespace | |
| } // namespace verible |