This revision was automatically updated to reflect the committed changes. Closed by commit rGaf582c9b0f3a: [SyntaxTree] Test `findFirstLeaf` and `findLastLeaf` (authored by eduucaldas).
Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D87779/new/ 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,125 @@ +//===- 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 +// +//===----------------------------------------------------------------------===// + +#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 { +private: + Tree *createTree(ArrayRef<const Node *> Children) { + std::vector<std::pair<Node *, NodeRole>> ChildrenWithRoles; + 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` into `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, then combine `Children` under + // this Parent. + if (ParentCount == 1) + return {{createTree(Children)}}; + + // Otherwise, combine `ChildrenCount` children under the last parent and + // solve the smaller problem without these children and this parent. Do this + // for every `ChildrenCount` and combine the results. + std::vector<std::vector<const Tree *>> AllForests; + 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; + } + +protected: + // Generates all trees with a `Base` 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) { + // We compute the solution per layer. A layer is a collection of bases, + // where each base has the same number of nodes, given by + // `NodeCountPerLayer`. + auto GenerateNextLayer = [this](ArrayRef<std::vector<const Node *>> Layer, + unsigned NextLayerNodeCount) { + std::vector<std::vector<const Node *>> NextLayer; + for (const auto &Base : Layer) { + for (const auto &NextBase : + generateAllForests(Base, NextLayerNodeCount)) { + NextLayer.push_back( + std::vector<const Node *>(NextBase.begin(), NextBase.end())); + } + } + return NextLayer; + }; + + std::vector<std::vector<const Node *>> Layer = {Base}; + for (auto NodeCount : NodeCountPerLayer) + Layer = GenerateNextLayer(Layer, NodeCount); + + std::vector<const Tree *> AllTrees; + AllTrees.reserve(Layer.size()); + for (const auto &Base : Layer) + AllTrees.push_back(createTree(Base)); + + 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
