| //===- 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/Basic/SourceManager.h" |
| #include "clang/Tooling/Syntax/BuildTree.h" |
| #include "clang/Tooling/Syntax/Nodes.h" |
| #include "llvm/ADT/STLExtras.h" |
| #include "gtest/gtest.h" |
| |
| using namespace clang; |
| using namespace clang::syntax; |
| |
| namespace { |
| using testing::ElementsAre; |
| |
| 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( |
| deepCopyExpandingMacros(*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_SUITE_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); |
| } |
| } |
| |
| TEST_F(TreeTest, Iterators) { |
| buildTree("", allTestClangConfigs().front()); |
| std::vector<Node *> Children = {createLeaf(*Arena, tok::identifier, "a"), |
| createLeaf(*Arena, tok::identifier, "b"), |
| createLeaf(*Arena, tok::identifier, "c")}; |
| auto *Tree = syntax::createTree(*Arena, |
| {{Children[0], NodeRole::LeftHandSide}, |
| {Children[1], NodeRole::OperatorToken}, |
| {Children[2], NodeRole::RightHandSide}}, |
| NodeKind::TranslationUnit); |
| const auto *ConstTree = Tree; |
| |
| auto Range = Tree->getChildren(); |
| EXPECT_THAT(Range, ElementsAre(role(NodeRole::LeftHandSide), |
| role(NodeRole::OperatorToken), |
| role(NodeRole::RightHandSide))); |
| |
| auto ConstRange = ConstTree->getChildren(); |
| EXPECT_THAT(ConstRange, ElementsAre(role(NodeRole::LeftHandSide), |
| role(NodeRole::OperatorToken), |
| role(NodeRole::RightHandSide))); |
| |
| // FIXME: mutate and observe no invalidation. Mutations are private for now... |
| auto It = Range.begin(); |
| auto CIt = ConstRange.begin(); |
| static_assert(std::is_same<decltype(*It), syntax::Node &>::value, |
| "mutable range"); |
| static_assert(std::is_same<decltype(*CIt), const syntax::Node &>::value, |
| "const range"); |
| |
| for (unsigned I = 0; I < 3; ++I) { |
| EXPECT_EQ(It, CIt); |
| EXPECT_TRUE(It); |
| EXPECT_TRUE(CIt); |
| EXPECT_EQ(It.asPointer(), Children[I]); |
| EXPECT_EQ(CIt.asPointer(), Children[I]); |
| EXPECT_EQ(&*It, Children[I]); |
| EXPECT_EQ(&*CIt, Children[I]); |
| ++It; |
| ++CIt; |
| } |
| EXPECT_EQ(It, CIt); |
| EXPECT_EQ(It, Tree::ChildIterator()); |
| EXPECT_EQ(CIt, Tree::ConstChildIterator()); |
| EXPECT_FALSE(It); |
| EXPECT_FALSE(CIt); |
| EXPECT_EQ(nullptr, It.asPointer()); |
| EXPECT_EQ(nullptr, CIt.asPointer()); |
| } |
| |
| class ListTest : public SyntaxTreeTest { |
| private: |
| std::string dumpQuotedTokensOrNull(const Node *N) { |
| return N ? "'" + |
| StringRef(N->dumpTokens(Arena->getSourceManager())) |
| .trim() |
| .str() + |
| "'" |
| : "null"; |
| } |
| |
| protected: |
| std::string |
| dumpElementsAndDelimiters(ArrayRef<List::ElementAndDelimiter<Node>> EDs) { |
| std::string Storage; |
| llvm::raw_string_ostream OS(Storage); |
| |
| OS << "["; |
| |
| llvm::interleaveComma( |
| EDs, OS, [&OS, this](const List::ElementAndDelimiter<Node> &ED) { |
| OS << "(" << dumpQuotedTokensOrNull(ED.element) << ", " |
| << dumpQuotedTokensOrNull(ED.delimiter) << ")"; |
| }); |
| |
| OS << "]"; |
| |
| return OS.str(); |
| } |
| |
| std::string dumpNodes(ArrayRef<Node *> Nodes) { |
| std::string Storage; |
| llvm::raw_string_ostream OS(Storage); |
| |
| OS << "["; |
| |
| llvm::interleaveComma(Nodes, OS, [&OS, this](const Node *N) { |
| OS << dumpQuotedTokensOrNull(N); |
| }); |
| |
| OS << "]"; |
| |
| return OS.str(); |
| } |
| }; |
| |
| INSTANTIATE_TEST_SUITE_P(TreeTests, ListTest, |
| ::testing::ValuesIn(allTestClangConfigs()) ); |
| |
| /// "a, b, c" <=> [("a", ","), ("b", ","), ("c", null)] |
| TEST_P(ListTest, List_Separated_WellFormed) { |
| buildTree("", GetParam()); |
| |
| // "a, b, c" |
| auto *List = dyn_cast<syntax::List>(syntax::createTree( |
| *Arena, |
| { |
| {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, |
| {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, |
| {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement}, |
| }, |
| NodeKind::CallArguments)); |
| |
| EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()), |
| "[('a', ','), ('b', ','), ('c', null)]"); |
| EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']"); |
| } |
| |
| /// "a, , c" <=> [("a", ","), (null, ","), ("c", null)] |
| TEST_P(ListTest, List_Separated_MissingElement) { |
| buildTree("", GetParam()); |
| |
| // "a, , c" |
| auto *List = dyn_cast<syntax::List>(syntax::createTree( |
| *Arena, |
| { |
| {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, |
| {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, |
| {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement}, |
| }, |
| NodeKind::CallArguments)); |
| |
| EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()), |
| "[('a', ','), (null, ','), ('c', null)]"); |
| EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', null, 'c']"); |
| } |
| |
| /// "a, b c" <=> [("a", ","), ("b", null), ("c", null)] |
| TEST_P(ListTest, List_Separated_MissingDelimiter) { |
| buildTree("", GetParam()); |
| |
| // "a, b c" |
| auto *List = dyn_cast<syntax::List>(syntax::createTree( |
| *Arena, |
| { |
| {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, |
| {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement}, |
| }, |
| NodeKind::CallArguments)); |
| |
| EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()), |
| "[('a', ','), ('b', null), ('c', null)]"); |
| EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']"); |
| } |
| |
| /// "a, b," <=> [("a", ","), ("b", ","), (null, null)] |
| TEST_P(ListTest, List_Separated_MissingLastElement) { |
| buildTree("", GetParam()); |
| |
| // "a, b, c" |
| auto *List = dyn_cast<syntax::List>(syntax::createTree( |
| *Arena, |
| { |
| {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, |
| {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, |
| }, |
| NodeKind::CallArguments)); |
| |
| EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()), |
| "[('a', ','), ('b', ','), (null, null)]"); |
| EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', null]"); |
| } |
| |
| /// "a:: b:: c::" <=> [("a", "::"), ("b", "::"), ("c", "::")] |
| TEST_P(ListTest, List_Terminated_WellFormed) { |
| if (!GetParam().isCXX()) { |
| return; |
| } |
| buildTree("", GetParam()); |
| |
| // "a:: b:: c::" |
| auto *List = dyn_cast<syntax::List>(syntax::createTree( |
| *Arena, |
| { |
| {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, |
| {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, |
| {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, |
| }, |
| NodeKind::NestedNameSpecifier)); |
| |
| EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()), |
| "[('a', '::'), ('b', '::'), ('c', '::')]"); |
| EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']"); |
| } |
| |
| /// "a:: :: c::" <=> [("a", "::"), (null, "::"), ("c", "::")] |
| TEST_P(ListTest, List_Terminated_MissingElement) { |
| if (!GetParam().isCXX()) { |
| return; |
| } |
| buildTree("", GetParam()); |
| |
| // "a:: b:: c::" |
| auto *List = dyn_cast<syntax::List>(syntax::createTree( |
| *Arena, |
| { |
| {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, |
| {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, |
| {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, |
| }, |
| NodeKind::NestedNameSpecifier)); |
| |
| EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()), |
| "[('a', '::'), (null, '::'), ('c', '::')]"); |
| EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', null, 'c']"); |
| } |
| |
| /// "a:: b c::" <=> [("a", "::"), ("b", null), ("c", "::")] |
| TEST_P(ListTest, List_Terminated_MissingDelimiter) { |
| if (!GetParam().isCXX()) { |
| return; |
| } |
| buildTree("", GetParam()); |
| |
| // "a:: b c::" |
| auto *List = dyn_cast<syntax::List>(syntax::createTree( |
| *Arena, |
| { |
| {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, |
| {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, |
| }, |
| NodeKind::NestedNameSpecifier)); |
| |
| EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()), |
| "[('a', '::'), ('b', null), ('c', '::')]"); |
| EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']"); |
| } |
| |
| /// "a:: b:: c" <=> [("a", "::"), ("b", "::"), ("c", null)] |
| TEST_P(ListTest, List_Terminated_MissingLastDelimiter) { |
| if (!GetParam().isCXX()) { |
| return; |
| } |
| buildTree("", GetParam()); |
| |
| // "a:: b:: c" |
| auto *List = dyn_cast<syntax::List>(syntax::createTree( |
| *Arena, |
| { |
| {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, |
| {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement}, |
| {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, |
| {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement}, |
| }, |
| NodeKind::NestedNameSpecifier)); |
| |
| EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()), |
| "[('a', '::'), ('b', '::'), ('c', null)]"); |
| EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']"); |
| } |
| |
| } // namespace |