clang/unittests/Tooling/Syntax/TreeTest.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-exception
   6 //
   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
  17 using namespace clang;
  18 using namespace clang::syntax;
  19
  20 namespace {
  21 using testing::ElementsAre;
  22
  23 class TreeTest : public SyntaxTreeTest {
  24 private:
  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` under
  43     // this Parent.
  44     if (ParentCount == 1)
  45       return {{createTree(Children)}};
  46
  47     // Otherwise, combine `ChildrenCount` children under the last parent and
  48     // solve the smaller problem without these children and this parent. Do this
  49     // 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
  63 protected:
  64   // Generates all trees with a `Base` of `Node`s and `NodeCountPerLayer`
  65   // `Node`s per layer. An example of Tree with `Base` = {`(`, `)`} and
  66   // `NodeCountPerLayer` = {2, 2}:
  67   //  Tree
  68   //  |-Tree
  69   //  `-Tree
  70   //    |-Tree
  71   //    | `-'('
  72   //    `-Tree
  73   //      `-')'
  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 by
  79     // `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
 106 INSTANTIATE_TEST_SUITE_P(
 107     TreeTests, TreeTest, ::testing::ValuesIn(allTestClangConfigs()),
 108     [](const testing::TestParamInfo<TestClangConfig> &Info) {
 109       return Info.param.toShortString();
 110     });
 111
 112 TEST_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
 122 TEST_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
 132 TEST_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
 181 class ListTest : public SyntaxTreeTest {
 182 private:
 183   std::string dumpQuotedTokensOrNull(const Node *N) {
 184     return N ? "'" +
 185                    StringRef(N->dumpTokens(*TM))
 186                        .trim()
 187                        .str() +
 188                    "'"
 189              : "null";
 190   }
 191
 192 protected:
 193   std::string
 194   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
 227 INSTANTIATE_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)]
 234 TEST_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)]
 255 TEST_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)]
 275 TEST_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)]
 295 TEST_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", "::")]
 315 TEST_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", "::")]
 340 TEST_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", "::")]
 364 TEST_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)]
 388 TEST_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 } // namespace