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, 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(TreeTests, TreeTest, 107 ::testing::ValuesIn(allTestClangConfigs()) ); 108 109 TEST_P(TreeTest, FirstLeaf) { 110 buildTree("", GetParam()); 111 std::vector<const Node *> Leafs = {createLeaf(*Arena, tok::l_paren), 112 createLeaf(*Arena, tok::r_paren)}; 113 for (const auto *Tree : generateAllTreesWithShape(Leafs, {3u})) { 114 ASSERT_TRUE(Tree->findFirstLeaf() != nullptr); 115 EXPECT_EQ(Tree->findFirstLeaf()->getToken()->kind(), tok::l_paren); 116 } 117 } 118 119 TEST_P(TreeTest, LastLeaf) { 120 buildTree("", GetParam()); 121 std::vector<const Node *> Leafs = {createLeaf(*Arena, tok::l_paren), 122 createLeaf(*Arena, tok::r_paren)}; 123 for (const auto *Tree : generateAllTreesWithShape(Leafs, {3u})) { 124 ASSERT_TRUE(Tree->findLastLeaf() != nullptr); 125 EXPECT_EQ(Tree->findLastLeaf()->getToken()->kind(), tok::r_paren); 126 } 127 } 128 129 TEST_F(TreeTest, Iterators) { 130 buildTree("", allTestClangConfigs().front()); 131 std::vector<Node *> Children = {createLeaf(*Arena, tok::identifier, "a"), 132 createLeaf(*Arena, tok::identifier, "b"), 133 createLeaf(*Arena, tok::identifier, "c")}; 134 auto *Tree = syntax::createTree(*Arena, 135 {{Children[0], NodeRole::LeftHandSide}, 136 {Children[1], NodeRole::OperatorToken}, 137 {Children[2], NodeRole::RightHandSide}}, 138 NodeKind::TranslationUnit); 139 const auto *ConstTree = Tree; 140 141 auto Range = Tree->getChildren(); 142 EXPECT_THAT(Range, ElementsAre(role(NodeRole::LeftHandSide), 143 role(NodeRole::OperatorToken), 144 role(NodeRole::RightHandSide))); 145 146 auto ConstRange = ConstTree->getChildren(); 147 EXPECT_THAT(ConstRange, ElementsAre(role(NodeRole::LeftHandSide), 148 role(NodeRole::OperatorToken), 149 role(NodeRole::RightHandSide))); 150 151 // FIXME: mutate and observe no invalidation. Mutations are private for now... 152 auto It = Range.begin(); 153 auto CIt = ConstRange.begin(); 154 static_assert(std::is_same<decltype(*It), syntax::Node &>::value, 155 "mutable range"); 156 static_assert(std::is_same<decltype(*CIt), const syntax::Node &>::value, 157 "const range"); 158 159 for (unsigned I = 0; I < 3; ++I) { 160 EXPECT_EQ(It, CIt); 161 EXPECT_TRUE(It); 162 EXPECT_TRUE(CIt); 163 EXPECT_EQ(It.asPointer(), Children[I]); 164 EXPECT_EQ(CIt.asPointer(), Children[I]); 165 EXPECT_EQ(&*It, Children[I]); 166 EXPECT_EQ(&*CIt, Children[I]); 167 ++It; 168 ++CIt; 169 } 170 EXPECT_EQ(It, CIt); 171 EXPECT_EQ(It, Tree::ChildIterator()); 172 EXPECT_EQ(CIt, Tree::ConstChildIterator()); 173 EXPECT_FALSE(It); 174 EXPECT_FALSE(CIt); 175 EXPECT_EQ(nullptr, It.asPointer()); 176 EXPECT_EQ(nullptr, CIt.asPointer()); 177 } 178 179 class ListTest : public SyntaxTreeTest { 180 private: 181 std::string dumpQuotedTokensOrNull(const Node *N) { 182 return N ? "'" + 183 StringRef(N->dumpTokens(Arena->getSourceManager())) 184 .trim() 185 .str() + 186 "'" 187 : "null"; 188 } 189 190 protected: 191 std::string 192 dumpElementsAndDelimiters(ArrayRef<List::ElementAndDelimiter<Node>> EDs) { 193 std::string Storage; 194 llvm::raw_string_ostream OS(Storage); 195 196 OS << "["; 197 198 llvm::interleaveComma( 199 EDs, OS, [&OS, this](const List::ElementAndDelimiter<Node> &ED) { 200 OS << "(" << dumpQuotedTokensOrNull(ED.element) << ", " 201 << dumpQuotedTokensOrNull(ED.delimiter) << ")"; 202 }); 203 204 OS << "]"; 205 206 return Storage; 207 } 208 209 std::string dumpNodes(ArrayRef<Node *> Nodes) { 210 std::string Storage; 211 llvm::raw_string_ostream OS(Storage); 212 213 OS << "["; 214 215 llvm::interleaveComma(Nodes, OS, [&OS, this](const Node *N) { 216 OS << dumpQuotedTokensOrNull(N); 217 }); 218 219 OS << "]"; 220 221 return Storage; 222 } 223 }; 224 225 INSTANTIATE_TEST_SUITE_P(TreeTests, ListTest, 226 ::testing::ValuesIn(allTestClangConfigs()) ); 227 228 /// "a, b, c" <=> [("a", ","), ("b", ","), ("c", null)] 229 TEST_P(ListTest, List_Separated_WellFormed) { 230 buildTree("", GetParam()); 231 232 // "a, b, c" 233 auto *List = dyn_cast<syntax::List>(syntax::createTree( 234 *Arena, 235 { 236 {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, 237 {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, 238 {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement}, 239 {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, 240 {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement}, 241 }, 242 NodeKind::CallArguments)); 243 244 EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()), 245 "[('a', ','), ('b', ','), ('c', null)]"); 246 EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']"); 247 } 248 249 /// "a, , c" <=> [("a", ","), (null, ","), ("c", null)] 250 TEST_P(ListTest, List_Separated_MissingElement) { 251 buildTree("", GetParam()); 252 253 // "a, , c" 254 auto *List = dyn_cast<syntax::List>(syntax::createTree( 255 *Arena, 256 { 257 {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, 258 {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, 259 {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, 260 {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement}, 261 }, 262 NodeKind::CallArguments)); 263 264 EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()), 265 "[('a', ','), (null, ','), ('c', null)]"); 266 EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', null, 'c']"); 267 } 268 269 /// "a, b c" <=> [("a", ","), ("b", null), ("c", null)] 270 TEST_P(ListTest, List_Separated_MissingDelimiter) { 271 buildTree("", GetParam()); 272 273 // "a, b c" 274 auto *List = dyn_cast<syntax::List>(syntax::createTree( 275 *Arena, 276 { 277 {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, 278 {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, 279 {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement}, 280 {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement}, 281 }, 282 NodeKind::CallArguments)); 283 284 EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()), 285 "[('a', ','), ('b', null), ('c', null)]"); 286 EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']"); 287 } 288 289 /// "a, b," <=> [("a", ","), ("b", ","), (null, null)] 290 TEST_P(ListTest, List_Separated_MissingLastElement) { 291 buildTree("", GetParam()); 292 293 // "a, b, c" 294 auto *List = dyn_cast<syntax::List>(syntax::createTree( 295 *Arena, 296 { 297 {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, 298 {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, 299 {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement}, 300 {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, 301 }, 302 NodeKind::CallArguments)); 303 304 EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()), 305 "[('a', ','), ('b', ','), (null, null)]"); 306 EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', null]"); 307 } 308 309 /// "a:: b:: c::" <=> [("a", "::"), ("b", "::"), ("c", "::")] 310 TEST_P(ListTest, List_Terminated_WellFormed) { 311 if (!GetParam().isCXX()) { 312 return; 313 } 314 buildTree("", GetParam()); 315 316 // "a:: b:: c::" 317 auto *List = dyn_cast<syntax::List>(syntax::createTree( 318 *Arena, 319 { 320 {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, 321 {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, 322 {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement}, 323 {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, 324 {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement}, 325 {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, 326 }, 327 NodeKind::NestedNameSpecifier)); 328 329 EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()), 330 "[('a', '::'), ('b', '::'), ('c', '::')]"); 331 EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']"); 332 } 333 334 /// "a:: :: c::" <=> [("a", "::"), (null, "::"), ("c", "::")] 335 TEST_P(ListTest, List_Terminated_MissingElement) { 336 if (!GetParam().isCXX()) { 337 return; 338 } 339 buildTree("", GetParam()); 340 341 // "a:: b:: c::" 342 auto *List = dyn_cast<syntax::List>(syntax::createTree( 343 *Arena, 344 { 345 {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, 346 {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, 347 {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, 348 {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement}, 349 {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, 350 }, 351 NodeKind::NestedNameSpecifier)); 352 353 EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()), 354 "[('a', '::'), (null, '::'), ('c', '::')]"); 355 EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', null, 'c']"); 356 } 357 358 /// "a:: b c::" <=> [("a", "::"), ("b", null), ("c", "::")] 359 TEST_P(ListTest, List_Terminated_MissingDelimiter) { 360 if (!GetParam().isCXX()) { 361 return; 362 } 363 buildTree("", GetParam()); 364 365 // "a:: b c::" 366 auto *List = dyn_cast<syntax::List>(syntax::createTree( 367 *Arena, 368 { 369 {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, 370 {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, 371 {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement}, 372 {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement}, 373 {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, 374 }, 375 NodeKind::NestedNameSpecifier)); 376 377 EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()), 378 "[('a', '::'), ('b', null), ('c', '::')]"); 379 EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']"); 380 } 381 382 /// "a:: b:: c" <=> [("a", "::"), ("b", "::"), ("c", null)] 383 TEST_P(ListTest, List_Terminated_MissingLastDelimiter) { 384 if (!GetParam().isCXX()) { 385 return; 386 } 387 buildTree("", GetParam()); 388 389 // "a:: b:: c" 390 auto *List = dyn_cast<syntax::List>(syntax::createTree( 391 *Arena, 392 { 393 {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, 394 {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, 395 {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement}, 396 {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, 397 {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement}, 398 }, 399 NodeKind::NestedNameSpecifier)); 400 401 EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()), 402 "[('a', '::'), ('b', '::'), ('c', null)]"); 403 EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']"); 404 } 405 406 } // namespace 407