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:
createTree(ArrayRef<const Node * > Children)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 *>>
generateAllForests(ArrayRef<const Node * > Children,unsigned ParentCount)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 *>
generateAllTreesWithShape(ArrayRef<const Node * > Base,ArrayRef<unsigned> NodeCountPerLayer)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_CASE_P(TreeTests, TreeTest,
107 ::testing::ValuesIn(allTestClangConfigs()), );
108
TEST_P(TreeTest,FirstLeaf)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
TEST_P(TreeTest,LastLeaf)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
TEST_F(TreeTest,Iterators)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:
dumpQuotedTokensOrNull(const Node * N)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
dumpElementsAndDelimiters(ArrayRef<List::ElementAndDelimiter<Node>> EDs)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 OS.str();
207 }
208
dumpNodes(ArrayRef<Node * > Nodes)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 OS.str();
222 }
223 };
224
225 INSTANTIATE_TEST_CASE_P(TreeTests, ListTest,
226 ::testing::ValuesIn(allTestClangConfigs()), );
227
228 /// "a, b, c" <=> [("a", ","), ("b", ","), ("c", null)]
TEST_P(ListTest,List_Separated_WellFormed)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)]
TEST_P(ListTest,List_Separated_MissingElement)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)]
TEST_P(ListTest,List_Separated_MissingDelimiter)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)]
TEST_P(ListTest,List_Separated_MissingLastElement)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", "::")]
TEST_P(ListTest,List_Terminated_WellFormed)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", "::")]
TEST_P(ListTest,List_Terminated_MissingElement)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", "::")]
TEST_P(ListTest,List_Terminated_MissingDelimiter)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)]
TEST_P(ListTest,List_Terminated_MissingLastDelimiter)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