eduucaldas created this revision. Herald added subscribers: cfe-commits, mgorny. Herald added a project: clang. eduucaldas requested review of this revision.
- Introduce `TreeTest.cpp` to unit test `Tree.h` - Add `generateAllTreesWithShape` to generating test cases - Add tests for `findFirstLeaf` and `findLastLeaf` - Fix implementations of `findFirstLeaf` and `findLastLeaf` that had been broken when empty `Tree` were present. Repository: rG LLVM Github Monorepo https://reviews.llvm.org/D87779 Files: clang/lib/Tooling/Syntax/Tree.cpp clang/unittests/Tooling/Syntax/CMakeLists.txt clang/unittests/Tooling/Syntax/TreeTest.cpp
Index: clang/unittests/Tooling/Syntax/TreeTest.cpp =================================================================== --- /dev/null +++ clang/unittests/Tooling/Syntax/TreeTest.cpp @@ -0,0 +1,141 @@ +//===- TreeTest.cpp ---------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file tests the Syntax Tree base API. +// +//===----------------------------------------------------------------------===// + +#include "clang/Tooling/Syntax/Tree.h" +#include "TreeTestBase.h" +#include "clang/Tooling/Syntax/BuildTree.h" +#include "gtest/gtest.h" + +using namespace clang; +using namespace clang::syntax; + +namespace { + +class TreeTest : public SyntaxTreeTest { +protected: + ::testing::AssertionResult treeDumpEqual(const syntax::Node *Root, + StringRef Dump) { + if (!Root) + return ::testing::AssertionFailure() + << "Root was not built successfully."; + + auto Actual = StringRef(Root->dump(Arena->getSourceManager())).trim().str(); + auto Expected = Dump.trim().str(); + // EXPECT_EQ shows the diff between the two strings if they are different. + EXPECT_EQ(Expected, Actual); + if (Actual != Expected) { + return ::testing::AssertionFailure(); + } + return ::testing::AssertionSuccess(); + } + + Tree *createTree(ArrayRef<const Node *> Children) { + auto ChildrenWithRoles = std::vector<std::pair<Node *, NodeRole>>(); + ChildrenWithRoles.reserve(Children.size()); + for (const auto *Child : Children) { + ChildrenWithRoles.push_back( + std::make_pair(deepCopy(*Arena, Child), NodeRole::Unknown)); + } + return clang::syntax::createTree(*Arena, ChildrenWithRoles, + NodeKind::UnknownExpression); + } + + // Generate Forests by combining `Children` under `ParentCount` Trees. + // + // We do this recursively. + std::vector<std::vector<const Tree *>> + generateAllForests(ArrayRef<const Node *> Children, unsigned ParentCount) { + assert(ParentCount > 0); + // If there is only one Parent node, we need to combine `Children` under + // this Parent. + if (ParentCount == 1) + return {{createTree(Children)}}; + + // Otherwise, we combine `ChildrenCount` children under the last parent and + // solve the smaller problem without these children and this parent. Finally + // we combine the results for every possible `ChildrenCount`. + auto AllForests = std::vector<std::vector<const Tree *>>(); + for (unsigned ChildrenCount = 0; ChildrenCount <= Children.size(); + ++ChildrenCount) { + auto *LastParent = createTree(Children.take_back(ChildrenCount)); + for (auto &Forest : generateAllForests(Children.drop_back(ChildrenCount), + ParentCount - 1)) { + Forest.push_back(LastParent); + AllForests.push_back(Forest); + } + } + return AllForests; + } + + // Generates all trees with a `Base` layer of `Node`s and `NodeCountPerLayer` + // `Node`s per layer. An example of Tree with `Base` = {`(`, `)`} and + // `NodeCountPerLayer` = {2, 2}: + // Tree + // |-Tree + // `-Tree + // |-Tree + // | `-'(' + // `-Tree + // `-')' + std::vector<const Tree *> + generateAllTreesWithShape(ArrayRef<const Node *> Base, + ArrayRef<unsigned> NodeCountPerLayer) { + auto GenerateNextLayers = [this](ArrayRef<std::vector<const Node *>> Bases, + unsigned NodeCount) { + auto NextLayers = std::vector<std::vector<const Node *>>(); + for (const auto &Base : Bases) { + for (const auto &NextLayer : generateAllForests(Base, NodeCount)) { + NextLayers.push_back( + std::vector<const Node *>(NextLayer.begin(), NextLayer.end())); + } + } + return NextLayers; + }; + + auto Layers = std::vector<std::vector<const Node *>>({Base}); + for (auto NodeCount : NodeCountPerLayer) { + Layers = GenerateNextLayers(Layers, NodeCount); + } + + auto AllTrees = std::vector<const Tree *>(); + AllTrees.reserve(Layers.size()); + for (const auto &Layer : Layers) { + AllTrees.push_back(createTree(Layer)); + } + return AllTrees; + } +}; + +INSTANTIATE_TEST_CASE_P(TreeTests, TreeTest, + ::testing::ValuesIn(allTestClangConfigs()), ); + +TEST_P(TreeTest, FirstLeaf) { + buildTree("", GetParam()); + std::vector<const Node *> Leafs = {createLeaf(*Arena, tok::l_paren), + createLeaf(*Arena, tok::r_paren)}; + for (const auto *Tree : generateAllTreesWithShape(Leafs, {3u})) { + ASSERT_TRUE(Tree->findFirstLeaf() != nullptr); + EXPECT_EQ(Tree->findFirstLeaf()->getToken()->kind(), tok::l_paren); + } +} + +TEST_P(TreeTest, LastLeaf) { + buildTree("", GetParam()); + std::vector<const Node *> Leafs = {createLeaf(*Arena, tok::l_paren), + createLeaf(*Arena, tok::r_paren)}; + for (const auto *Tree : generateAllTreesWithShape(Leafs, {3u})) { + ASSERT_TRUE(Tree->findLastLeaf() != nullptr); + EXPECT_EQ(Tree->findLastLeaf()->getToken()->kind(), tok::r_paren); + } +} + +} // namespace Index: clang/unittests/Tooling/Syntax/CMakeLists.txt =================================================================== --- clang/unittests/Tooling/Syntax/CMakeLists.txt +++ clang/unittests/Tooling/Syntax/CMakeLists.txt @@ -7,6 +7,7 @@ BuildTreeTest.cpp MutationsTest.cpp SynthesisTest.cpp + TreeTest.cpp TokensTest.cpp ) Index: clang/lib/Tooling/Syntax/Tree.cpp =================================================================== --- clang/lib/Tooling/Syntax/Tree.cpp +++ clang/lib/Tooling/Syntax/Tree.cpp @@ -255,27 +255,24 @@ } syntax::Leaf *syntax::Tree::findFirstLeaf() { - auto *T = this; - while (auto *C = T->getFirstChild()) { + for (auto *C = getFirstChild(); C; C = C->getNextSibling()) { if (auto *L = dyn_cast<syntax::Leaf>(C)) return L; - T = cast<syntax::Tree>(C); + if (auto *L = cast<syntax::Tree>(C)->findFirstLeaf()) + return L; } return nullptr; } syntax::Leaf *syntax::Tree::findLastLeaf() { - auto *T = this; - while (auto *C = T->getFirstChild()) { - // Find the last child. - while (auto *Next = C->getNextSibling()) - C = Next; - + syntax::Leaf *Last = nullptr; + for (auto *C = getFirstChild(); C; C = C->getNextSibling()) { if (auto *L = dyn_cast<syntax::Leaf>(C)) - return L; - T = cast<syntax::Tree>(C); + Last = L; + else if (auto *L = cast<syntax::Tree>(C)->findLastLeaf()) + Last = L; } - return nullptr; + return Last; } syntax::Node *syntax::Tree::findChild(NodeRole R) {
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
