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

source code of clang/unittests/Tooling/Syntax/TreeTest.cpp