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 412