412 lines · cpp
1//===- TreeTest.cpp ---------------------------------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "clang/Tooling/Syntax/Tree.h"10#include "TreeTestBase.h"11#include "clang/Basic/SourceManager.h"12#include "clang/Tooling/Syntax/BuildTree.h"13#include "clang/Tooling/Syntax/Nodes.h"14#include "llvm/ADT/STLExtras.h"15#include "gtest/gtest.h"16 17using namespace clang;18using namespace clang::syntax;19 20namespace {21using testing::ElementsAre;22 23class TreeTest : public SyntaxTreeTest {24private:25 Tree *createTree(ArrayRef<const Node *> Children) {26 std::vector<std::pair<Node *, NodeRole>> ChildrenWithRoles;27 ChildrenWithRoles.reserve(Children.size());28 for (const auto *Child : Children) {29 ChildrenWithRoles.push_back(std::make_pair(30 deepCopyExpandingMacros(*Arena, *TM, Child), NodeRole::Unknown));31 }32 return clang::syntax::createTree(*Arena, ChildrenWithRoles,33 NodeKind::UnknownExpression);34 }35 36 // Generate Forests by combining `Children` into `ParentCount` Trees.37 //38 // We do this recursively.39 std::vector<std::vector<const Tree *>>40 generateAllForests(ArrayRef<const Node *> Children, unsigned ParentCount) {41 assert(ParentCount > 0);42 // If there is only one Parent node, then combine `Children` under43 // this Parent.44 if (ParentCount == 1)45 return {{createTree(Children)}};46 47 // Otherwise, combine `ChildrenCount` children under the last parent and48 // solve the smaller problem without these children and this parent. Do this49 // for every `ChildrenCount` and combine the results.50 std::vector<std::vector<const Tree *>> AllForests;51 for (unsigned ChildrenCount = 0; ChildrenCount <= Children.size();52 ++ChildrenCount) {53 auto *LastParent = createTree(Children.take_back(ChildrenCount));54 for (auto &Forest : generateAllForests(Children.drop_back(ChildrenCount),55 ParentCount - 1)) {56 Forest.push_back(LastParent);57 AllForests.push_back(Forest);58 }59 }60 return AllForests;61 }62 63protected:64 // Generates all trees with a `Base` of `Node`s and `NodeCountPerLayer`65 // `Node`s per layer. An example of Tree with `Base` = {`(`, `)`} and66 // `NodeCountPerLayer` = {2, 2}:67 // Tree68 // |-Tree69 // `-Tree70 // |-Tree71 // | `-'('72 // `-Tree73 // `-')'74 std::vector<const Tree *>75 generateAllTreesWithShape(ArrayRef<const Node *> Base,76 ArrayRef<unsigned> NodeCountPerLayer) {77 // We compute the solution per layer. A layer is a collection of bases,78 // where each base has the same number of nodes, given by79 // `NodeCountPerLayer`.80 auto GenerateNextLayer = [this](ArrayRef<std::vector<const Node *>> Layer,81 unsigned NextLayerNodeCount) {82 std::vector<std::vector<const Node *>> NextLayer;83 for (const auto &Base : Layer) {84 for (const auto &NextBase :85 generateAllForests(Base, NextLayerNodeCount)) {86 NextLayer.push_back(87 std::vector<const Node *>(NextBase.begin(), NextBase.end()));88 }89 }90 return NextLayer;91 };92 93 std::vector<std::vector<const Node *>> Layer = {Base};94 for (auto NodeCount : NodeCountPerLayer)95 Layer = GenerateNextLayer(Layer, NodeCount);96 97 std::vector<const Tree *> AllTrees;98 AllTrees.reserve(Layer.size());99 for (const auto &Base : Layer)100 AllTrees.push_back(createTree(Base));101 102 return AllTrees;103 }104};105 106INSTANTIATE_TEST_SUITE_P(107 TreeTests, TreeTest, ::testing::ValuesIn(allTestClangConfigs()),108 [](const testing::TestParamInfo<TestClangConfig> &Info) {109 return Info.param.toShortString();110 });111 112TEST_P(TreeTest, FirstLeaf) {113 buildTree("", GetParam());114 std::vector<const Node *> Leafs = {createLeaf(*Arena, *TM, tok::l_paren),115 createLeaf(*Arena, *TM, tok::r_paren)};116 for (const auto *Tree : generateAllTreesWithShape(Leafs, {3u})) {117 ASSERT_TRUE(Tree->findFirstLeaf() != nullptr);118 EXPECT_EQ(TM->getToken(Tree->findFirstLeaf()->getTokenKey())->kind(), tok::l_paren);119 }120}121 122TEST_P(TreeTest, LastLeaf) {123 buildTree("", GetParam());124 std::vector<const Node *> Leafs = {createLeaf(*Arena, *TM, tok::l_paren),125 createLeaf(*Arena, *TM, tok::r_paren)};126 for (const auto *Tree : generateAllTreesWithShape(Leafs, {3u})) {127 ASSERT_TRUE(Tree->findLastLeaf() != nullptr);128 EXPECT_EQ(TM->getToken(Tree->findLastLeaf()->getTokenKey())->kind(), tok::r_paren);129 }130}131 132TEST_F(TreeTest, Iterators) {133 buildTree("", allTestClangConfigs().front());134 std::vector<Node *> Children = {createLeaf(*Arena, *TM, tok::identifier, "a"),135 createLeaf(*Arena, *TM, tok::identifier, "b"),136 createLeaf(*Arena, *TM, tok::identifier, "c")};137 auto *Tree = syntax::createTree(*Arena,138 {{Children[0], NodeRole::LeftHandSide},139 {Children[1], NodeRole::OperatorToken},140 {Children[2], NodeRole::RightHandSide}},141 NodeKind::TranslationUnit);142 const auto *ConstTree = Tree;143 144 auto Range = Tree->getChildren();145 EXPECT_THAT(Range, ElementsAre(role(NodeRole::LeftHandSide),146 role(NodeRole::OperatorToken),147 role(NodeRole::RightHandSide)));148 149 auto ConstRange = ConstTree->getChildren();150 EXPECT_THAT(ConstRange, ElementsAre(role(NodeRole::LeftHandSide),151 role(NodeRole::OperatorToken),152 role(NodeRole::RightHandSide)));153 154 // FIXME: mutate and observe no invalidation. Mutations are private for now...155 auto It = Range.begin();156 auto CIt = ConstRange.begin();157 static_assert(std::is_same_v<decltype(*It), syntax::Node &>, "mutable range");158 static_assert(std::is_same_v<decltype(*CIt), const syntax::Node &>,159 "const range");160 161 for (unsigned I = 0; I < 3; ++I) {162 EXPECT_EQ(It, CIt);163 EXPECT_TRUE(It);164 EXPECT_TRUE(CIt);165 EXPECT_EQ(It.asPointer(), Children[I]);166 EXPECT_EQ(CIt.asPointer(), Children[I]);167 EXPECT_EQ(&*It, Children[I]);168 EXPECT_EQ(&*CIt, Children[I]);169 ++It;170 ++CIt;171 }172 EXPECT_EQ(It, CIt);173 EXPECT_EQ(It, Tree::ChildIterator());174 EXPECT_EQ(CIt, Tree::ConstChildIterator());175 EXPECT_FALSE(It);176 EXPECT_FALSE(CIt);177 EXPECT_EQ(nullptr, It.asPointer());178 EXPECT_EQ(nullptr, CIt.asPointer());179}180 181class ListTest : public SyntaxTreeTest {182private:183 std::string dumpQuotedTokensOrNull(const Node *N) {184 return N ? "'" +185 StringRef(N->dumpTokens(*TM))186 .trim()187 .str() +188 "'"189 : "null";190 }191 192protected:193 std::string194 dumpElementsAndDelimiters(ArrayRef<List::ElementAndDelimiter<Node>> EDs) {195 std::string Storage;196 llvm::raw_string_ostream OS(Storage);197 198 OS << "[";199 200 llvm::interleaveComma(201 EDs, OS, [&OS, this](const List::ElementAndDelimiter<Node> &ED) {202 OS << "(" << dumpQuotedTokensOrNull(ED.element) << ", "203 << dumpQuotedTokensOrNull(ED.delimiter) << ")";204 });205 206 OS << "]";207 208 return Storage;209 }210 211 std::string dumpNodes(ArrayRef<Node *> Nodes) {212 std::string Storage;213 llvm::raw_string_ostream OS(Storage);214 215 OS << "[";216 217 llvm::interleaveComma(Nodes, OS, [&OS, this](const Node *N) {218 OS << dumpQuotedTokensOrNull(N);219 });220 221 OS << "]";222 223 return Storage;224 }225};226 227INSTANTIATE_TEST_SUITE_P(228 TreeTests, ListTest, ::testing::ValuesIn(allTestClangConfigs()),229 [](const testing::TestParamInfo<TestClangConfig> &Info) {230 return Info.param.toShortString();231 });232 233/// "a, b, c" <=> [("a", ","), ("b", ","), ("c", null)]234TEST_P(ListTest, List_Separated_WellFormed) {235 buildTree("", GetParam());236 237 // "a, b, c"238 auto *List = dyn_cast<syntax::List>(syntax::createTree(239 *Arena,240 {241 {createLeaf(*Arena, *TM, tok::identifier, "a"), NodeRole::ListElement},242 {createLeaf(*Arena, *TM, tok::comma), NodeRole::ListDelimiter},243 {createLeaf(*Arena, *TM, tok::identifier, "b"), NodeRole::ListElement},244 {createLeaf(*Arena, *TM, tok::comma), NodeRole::ListDelimiter},245 {createLeaf(*Arena, *TM, tok::identifier, "c"), NodeRole::ListElement},246 },247 NodeKind::CallArguments));248 249 EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),250 "[('a', ','), ('b', ','), ('c', null)]");251 EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']");252}253 254/// "a, , c" <=> [("a", ","), (null, ","), ("c", null)]255TEST_P(ListTest, List_Separated_MissingElement) {256 buildTree("", GetParam());257 258 // "a, , c"259 auto *List = dyn_cast<syntax::List>(syntax::createTree(260 *Arena,261 {262 {createLeaf(*Arena, *TM, tok::identifier, "a"), NodeRole::ListElement},263 {createLeaf(*Arena, *TM, tok::comma), NodeRole::ListDelimiter},264 {createLeaf(*Arena, *TM, tok::comma), NodeRole::ListDelimiter},265 {createLeaf(*Arena, *TM, tok::identifier, "c"), NodeRole::ListElement},266 },267 NodeKind::CallArguments));268 269 EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),270 "[('a', ','), (null, ','), ('c', null)]");271 EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', null, 'c']");272}273 274/// "a, b c" <=> [("a", ","), ("b", null), ("c", null)]275TEST_P(ListTest, List_Separated_MissingDelimiter) {276 buildTree("", GetParam());277 278 // "a, b c"279 auto *List = dyn_cast<syntax::List>(syntax::createTree(280 *Arena,281 {282 {createLeaf(*Arena, *TM, tok::identifier, "a"), NodeRole::ListElement},283 {createLeaf(*Arena, *TM, tok::comma), NodeRole::ListDelimiter},284 {createLeaf(*Arena, *TM, tok::identifier, "b"), NodeRole::ListElement},285 {createLeaf(*Arena, *TM, tok::identifier, "c"), NodeRole::ListElement},286 },287 NodeKind::CallArguments));288 289 EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),290 "[('a', ','), ('b', null), ('c', null)]");291 EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']");292}293 294/// "a, b," <=> [("a", ","), ("b", ","), (null, null)]295TEST_P(ListTest, List_Separated_MissingLastElement) {296 buildTree("", GetParam());297 298 // "a, b, c"299 auto *List = dyn_cast<syntax::List>(syntax::createTree(300 *Arena,301 {302 {createLeaf(*Arena, *TM, tok::identifier, "a"), NodeRole::ListElement},303 {createLeaf(*Arena, *TM, tok::comma), NodeRole::ListDelimiter},304 {createLeaf(*Arena, *TM, tok::identifier, "b"), NodeRole::ListElement},305 {createLeaf(*Arena, *TM, tok::comma), NodeRole::ListDelimiter},306 },307 NodeKind::CallArguments));308 309 EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),310 "[('a', ','), ('b', ','), (null, null)]");311 EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', null]");312}313 314/// "a:: b:: c::" <=> [("a", "::"), ("b", "::"), ("c", "::")]315TEST_P(ListTest, List_Terminated_WellFormed) {316 if (!GetParam().isCXX()) {317 return;318 }319 buildTree("", GetParam());320 321 // "a:: b:: c::"322 auto *List = dyn_cast<syntax::List>(syntax::createTree(323 *Arena,324 {325 {createLeaf(*Arena, *TM, tok::identifier, "a"), NodeRole::ListElement},326 {createLeaf(*Arena, *TM, tok::coloncolon), NodeRole::ListDelimiter},327 {createLeaf(*Arena, *TM, tok::identifier, "b"), NodeRole::ListElement},328 {createLeaf(*Arena, *TM, tok::coloncolon), NodeRole::ListDelimiter},329 {createLeaf(*Arena, *TM, tok::identifier, "c"), NodeRole::ListElement},330 {createLeaf(*Arena, *TM, tok::coloncolon), NodeRole::ListDelimiter},331 },332 NodeKind::NestedNameSpecifier));333 334 EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),335 "[('a', '::'), ('b', '::'), ('c', '::')]");336 EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']");337}338 339/// "a:: :: c::" <=> [("a", "::"), (null, "::"), ("c", "::")]340TEST_P(ListTest, List_Terminated_MissingElement) {341 if (!GetParam().isCXX()) {342 return;343 }344 buildTree("", GetParam());345 346 // "a:: b:: c::"347 auto *List = dyn_cast<syntax::List>(syntax::createTree(348 *Arena,349 {350 {createLeaf(*Arena, *TM, tok::identifier, "a"), NodeRole::ListElement},351 {createLeaf(*Arena, *TM, tok::coloncolon), NodeRole::ListDelimiter},352 {createLeaf(*Arena, *TM, tok::coloncolon), NodeRole::ListDelimiter},353 {createLeaf(*Arena, *TM, tok::identifier, "c"), NodeRole::ListElement},354 {createLeaf(*Arena, *TM, tok::coloncolon), NodeRole::ListDelimiter},355 },356 NodeKind::NestedNameSpecifier));357 358 EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),359 "[('a', '::'), (null, '::'), ('c', '::')]");360 EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', null, 'c']");361}362 363/// "a:: b c::" <=> [("a", "::"), ("b", null), ("c", "::")]364TEST_P(ListTest, List_Terminated_MissingDelimiter) {365 if (!GetParam().isCXX()) {366 return;367 }368 buildTree("", GetParam());369 370 // "a:: b c::"371 auto *List = dyn_cast<syntax::List>(syntax::createTree(372 *Arena,373 {374 {createLeaf(*Arena, *TM, tok::identifier, "a"), NodeRole::ListElement},375 {createLeaf(*Arena, *TM, tok::coloncolon), NodeRole::ListDelimiter},376 {createLeaf(*Arena, *TM, tok::identifier, "b"), NodeRole::ListElement},377 {createLeaf(*Arena, *TM, tok::identifier, "c"), NodeRole::ListElement},378 {createLeaf(*Arena, *TM, tok::coloncolon), NodeRole::ListDelimiter},379 },380 NodeKind::NestedNameSpecifier));381 382 EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),383 "[('a', '::'), ('b', null), ('c', '::')]");384 EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']");385}386 387/// "a:: b:: c" <=> [("a", "::"), ("b", "::"), ("c", null)]388TEST_P(ListTest, List_Terminated_MissingLastDelimiter) {389 if (!GetParam().isCXX()) {390 return;391 }392 buildTree("", GetParam());393 394 // "a:: b:: c"395 auto *List = dyn_cast<syntax::List>(syntax::createTree(396 *Arena,397 {398 {createLeaf(*Arena, *TM, tok::identifier, "a"), NodeRole::ListElement},399 {createLeaf(*Arena, *TM, tok::coloncolon), NodeRole::ListDelimiter},400 {createLeaf(*Arena, *TM, tok::identifier, "b"), NodeRole::ListElement},401 {createLeaf(*Arena, *TM, tok::coloncolon), NodeRole::ListDelimiter},402 {createLeaf(*Arena, *TM, tok::identifier, "c"), NodeRole::ListElement},403 },404 NodeKind::NestedNameSpecifier));405 406 EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),407 "[('a', '::'), ('b', '::'), ('c', null)]");408 EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']");409}410 411} // namespace412