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(
107 TreeTests, TreeTest, ::testing::ValuesIn(allTestClangConfigs()),
108 [](const testing::TestParamInfo<TestClangConfig> &Info) {
109 return Info.param.toShortString();
110 });
111
112TEST_P(TreeTest, FirstLeaf) {
113 buildTree("", GetParam());
114 std::vector<const Node *> Leafs = {createLeaf(A&: *Arena, TBTM&: *TM, K: tok::l_paren),
115 createLeaf(A&: *Arena, TBTM&: *TM, K: tok::r_paren)};
116 for (const auto *Tree : generateAllTreesWithShape(Base: Leafs, NodeCountPerLayer: {3u})) {
117 ASSERT_TRUE(Tree->findFirstLeaf() != nullptr);
118 EXPECT_EQ(TM->getToken(Tree->findFirstLeaf()->getTokenKey())->kind(), tok::l_paren);
119 }
120}
121
122TEST_P(TreeTest, LastLeaf) {
123 buildTree("", GetParam());
124 std::vector<const Node *> Leafs = {createLeaf(A&: *Arena, TBTM&: *TM, K: tok::l_paren),
125 createLeaf(A&: *Arena, TBTM&: *TM, K: tok::r_paren)};
126 for (const auto *Tree : generateAllTreesWithShape(Base: Leafs, NodeCountPerLayer: {3u})) {
127 ASSERT_TRUE(Tree->findLastLeaf() != nullptr);
128 EXPECT_EQ(TM->getToken(Tree->findLastLeaf()->getTokenKey())->kind(), tok::r_paren);
129 }
130}
131
132TEST_F(TreeTest, Iterators) {
133 buildTree("", allTestClangConfigs().front());
134 std::vector<Node *> Children = {createLeaf(A&: *Arena, TBTM&: *TM, K: tok::identifier, Spelling: "a"),
135 createLeaf(A&: *Arena, TBTM&: *TM, K: tok::identifier, Spelling: "b"),
136 createLeaf(A&: *Arena, TBTM&: *TM, K: tok::identifier, Spelling: "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
181class ListTest : public SyntaxTreeTest {
182private:
183 std::string dumpQuotedTokensOrNull(const Node *N) {
184 return N ? "'" +
185 StringRef(N->dumpTokens(SM: *TM))
186 .trim()
187 .str() +
188 "'"
189 : "null";
190 }
191
192protected:
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 c: EDs, os&: OS, each_fn: [&OS, this](const List::ElementAndDelimiter<Node> &ED) {
202 OS << "(" << dumpQuotedTokensOrNull(N: ED.element) << ", "
203 << dumpQuotedTokensOrNull(N: 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(c: Nodes, os&: OS, each_fn: [&OS, this](const Node *N) {
218 OS << dumpQuotedTokensOrNull(N);
219 });
220
221 OS << "]";
222
223 return Storage;
224 }
225};
226
227INSTANTIATE_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)]
234TEST_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)]
255TEST_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)]
275TEST_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)]
295TEST_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", "::")]
315TEST_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", "::")]
340TEST_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", "::")]
364TEST_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)]
388TEST_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

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