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/Tooling/Syntax/BuildTree.h"
12 #include "clang/Tooling/Syntax/Nodes.h"
13 #include "llvm/ADT/STLExtras.h"
14 #include "gtest/gtest.h"
15 
16 using namespace clang;
17 using namespace clang::syntax;
18 
19 namespace {
20 
21 class TreeTest : public SyntaxTreeTest {
22 private:
23   Tree *createTree(ArrayRef<const Node *> Children) {
24     std::vector<std::pair<Node *, NodeRole>> ChildrenWithRoles;
25     ChildrenWithRoles.reserve(Children.size());
26     for (const auto *Child : Children) {
27       ChildrenWithRoles.push_back(std::make_pair(
28           deepCopyExpandingMacros(*Arena, Child), NodeRole::Unknown));
29     }
30     return clang::syntax::createTree(*Arena, ChildrenWithRoles,
31                                      NodeKind::UnknownExpression);
32   }
33 
34   // Generate Forests by combining `Children` into `ParentCount` Trees.
35   //
36   // We do this recursively.
37   std::vector<std::vector<const Tree *>>
38   generateAllForests(ArrayRef<const Node *> Children, unsigned ParentCount) {
39     assert(ParentCount > 0);
40     // If there is only one Parent node, then combine `Children` under
41     // this Parent.
42     if (ParentCount == 1)
43       return {{createTree(Children)}};
44 
45     // Otherwise, combine `ChildrenCount` children under the last parent and
46     // solve the smaller problem without these children and this parent. Do this
47     // for every `ChildrenCount` and combine the results.
48     std::vector<std::vector<const Tree *>> AllForests;
49     for (unsigned ChildrenCount = 0; ChildrenCount <= Children.size();
50          ++ChildrenCount) {
51       auto *LastParent = createTree(Children.take_back(ChildrenCount));
52       for (auto &Forest : generateAllForests(Children.drop_back(ChildrenCount),
53                                              ParentCount - 1)) {
54         Forest.push_back(LastParent);
55         AllForests.push_back(Forest);
56       }
57     }
58     return AllForests;
59   }
60 
61 protected:
62   // Generates all trees with a `Base` of `Node`s and `NodeCountPerLayer`
63   // `Node`s per layer. An example of Tree with `Base` = {`(`, `)`} and
64   // `NodeCountPerLayer` = {2, 2}:
65   //  Tree
66   //  |-Tree
67   //  `-Tree
68   //    |-Tree
69   //    | `-'('
70   //    `-Tree
71   //      `-')'
72   std::vector<const Tree *>
73   generateAllTreesWithShape(ArrayRef<const Node *> Base,
74                             ArrayRef<unsigned> NodeCountPerLayer) {
75     // We compute the solution per layer. A layer is a collection of bases,
76     // where each base has the same number of nodes, given by
77     // `NodeCountPerLayer`.
78     auto GenerateNextLayer = [this](ArrayRef<std::vector<const Node *>> Layer,
79                                     unsigned NextLayerNodeCount) {
80       std::vector<std::vector<const Node *>> NextLayer;
81       for (const auto &Base : Layer) {
82         for (const auto &NextBase :
83              generateAllForests(Base, NextLayerNodeCount)) {
84           NextLayer.push_back(
85               std::vector<const Node *>(NextBase.begin(), NextBase.end()));
86         }
87       }
88       return NextLayer;
89     };
90 
91     std::vector<std::vector<const Node *>> Layer = {Base};
92     for (auto NodeCount : NodeCountPerLayer)
93       Layer = GenerateNextLayer(Layer, NodeCount);
94 
95     std::vector<const Tree *> AllTrees;
96     AllTrees.reserve(Layer.size());
97     for (const auto &Base : Layer)
98       AllTrees.push_back(createTree(Base));
99 
100     return AllTrees;
101   }
102 };
103 
104 INSTANTIATE_TEST_CASE_P(TreeTests, TreeTest,
105                         ::testing::ValuesIn(allTestClangConfigs()), );
106 
107 TEST_P(TreeTest, FirstLeaf) {
108   buildTree("", GetParam());
109   std::vector<const Node *> Leafs = {createLeaf(*Arena, tok::l_paren),
110                                      createLeaf(*Arena, tok::r_paren)};
111   for (const auto *Tree : generateAllTreesWithShape(Leafs, {3u})) {
112     ASSERT_TRUE(Tree->findFirstLeaf() != nullptr);
113     EXPECT_EQ(Tree->findFirstLeaf()->getToken()->kind(), tok::l_paren);
114   }
115 }
116 
117 TEST_P(TreeTest, LastLeaf) {
118   buildTree("", GetParam());
119   std::vector<const Node *> Leafs = {createLeaf(*Arena, tok::l_paren),
120                                      createLeaf(*Arena, tok::r_paren)};
121   for (const auto *Tree : generateAllTreesWithShape(Leafs, {3u})) {
122     ASSERT_TRUE(Tree->findLastLeaf() != nullptr);
123     EXPECT_EQ(Tree->findLastLeaf()->getToken()->kind(), tok::r_paren);
124   }
125 }
126 
127 class ListTest : public SyntaxTreeTest {
128 private:
129   std::string dumpQuotedTokensOrNull(const Node *N) {
130     return N ? "'" +
131                    StringRef(N->dumpTokens(Arena->getSourceManager()))
132                        .trim()
133                        .str() +
134                    "'"
135              : "null";
136   }
137 
138 protected:
139   std::string
140   dumpElementsAndDelimiters(ArrayRef<List::ElementAndDelimiter<Node>> EDs) {
141     std::string Storage;
142     llvm::raw_string_ostream OS(Storage);
143 
144     OS << "[";
145 
146     llvm::interleaveComma(
147         EDs, OS, [&OS, this](const List::ElementAndDelimiter<Node> &ED) {
148           OS << "(" << dumpQuotedTokensOrNull(ED.element) << ", "
149              << dumpQuotedTokensOrNull(ED.delimiter) << ")";
150         });
151 
152     OS << "]";
153 
154     return OS.str();
155   }
156 
157   std::string dumpNodes(ArrayRef<Node *> Nodes) {
158     std::string Storage;
159     llvm::raw_string_ostream OS(Storage);
160 
161     OS << "[";
162 
163     llvm::interleaveComma(Nodes, OS, [&OS, this](const Node *N) {
164       OS << dumpQuotedTokensOrNull(N);
165     });
166 
167     OS << "]";
168 
169     return OS.str();
170   }
171 };
172 
173 INSTANTIATE_TEST_CASE_P(TreeTests, ListTest,
174                         ::testing::ValuesIn(allTestClangConfigs()), );
175 
176 /// "a, b, c"  <=> [("a", ","), ("b", ","), ("c", null)]
177 TEST_P(ListTest, List_Separated_WellFormed) {
178   buildTree("", GetParam());
179 
180   // "a, b, c"
181   auto *List = dyn_cast<syntax::List>(syntax::createTree(
182       *Arena,
183       {
184           {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement},
185           {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter},
186           {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement},
187           {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter},
188           {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement},
189       },
190       NodeKind::CallArguments));
191 
192   EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),
193             "[('a', ','), ('b', ','), ('c', null)]");
194   EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']");
195 }
196 
197 /// "a,  , c"  <=> [("a", ","), (null, ","), ("c", null)]
198 TEST_P(ListTest, List_Separated_MissingElement) {
199   buildTree("", GetParam());
200 
201   // "a,  , c"
202   auto *List = dyn_cast<syntax::List>(syntax::createTree(
203       *Arena,
204       {
205           {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement},
206           {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter},
207           {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter},
208           {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement},
209       },
210       NodeKind::CallArguments));
211 
212   EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),
213             "[('a', ','), (null, ','), ('c', null)]");
214   EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', null, 'c']");
215 }
216 
217 /// "a, b  c"  <=> [("a", ","), ("b", null), ("c", null)]
218 TEST_P(ListTest, List_Separated_MissingDelimiter) {
219   buildTree("", GetParam());
220 
221   // "a, b  c"
222   auto *List = dyn_cast<syntax::List>(syntax::createTree(
223       *Arena,
224       {
225           {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement},
226           {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter},
227           {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement},
228           {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement},
229       },
230       NodeKind::CallArguments));
231 
232   EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),
233             "[('a', ','), ('b', null), ('c', null)]");
234   EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']");
235 }
236 
237 /// "a, b,"    <=> [("a", ","), ("b", ","), (null, null)]
238 TEST_P(ListTest, List_Separated_MissingLastElement) {
239   buildTree("", GetParam());
240 
241   // "a, b, c"
242   auto *List = dyn_cast<syntax::List>(syntax::createTree(
243       *Arena,
244       {
245           {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement},
246           {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter},
247           {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement},
248           {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter},
249       },
250       NodeKind::CallArguments));
251 
252   EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),
253             "[('a', ','), ('b', ','), (null, null)]");
254   EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', null]");
255 }
256 
257 /// "a:: b:: c::" <=> [("a", "::"), ("b", "::"), ("c", "::")]
258 TEST_P(ListTest, List_Terminated_WellFormed) {
259   if (!GetParam().isCXX()) {
260     return;
261   }
262   buildTree("", GetParam());
263 
264   // "a:: b:: c::"
265   auto *List = dyn_cast<syntax::List>(syntax::createTree(
266       *Arena,
267       {
268           {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement},
269           {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter},
270           {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement},
271           {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter},
272           {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement},
273           {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter},
274       },
275       NodeKind::NestedNameSpecifier));
276 
277   EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),
278             "[('a', '::'), ('b', '::'), ('c', '::')]");
279   EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']");
280 }
281 
282 /// "a::  :: c::" <=> [("a", "::"), (null, "::"), ("c", "::")]
283 TEST_P(ListTest, List_Terminated_MissingElement) {
284   if (!GetParam().isCXX()) {
285     return;
286   }
287   buildTree("", GetParam());
288 
289   // "a:: b:: c::"
290   auto *List = dyn_cast<syntax::List>(syntax::createTree(
291       *Arena,
292       {
293           {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement},
294           {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter},
295           {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter},
296           {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement},
297           {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter},
298       },
299       NodeKind::NestedNameSpecifier));
300 
301   EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),
302             "[('a', '::'), (null, '::'), ('c', '::')]");
303   EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', null, 'c']");
304 }
305 
306 /// "a:: b  c::" <=> [("a", "::"), ("b", null), ("c", "::")]
307 TEST_P(ListTest, List_Terminated_MissingDelimiter) {
308   if (!GetParam().isCXX()) {
309     return;
310   }
311   buildTree("", GetParam());
312 
313   // "a:: b  c::"
314   auto *List = dyn_cast<syntax::List>(syntax::createTree(
315       *Arena,
316       {
317           {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement},
318           {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter},
319           {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement},
320           {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement},
321           {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter},
322       },
323       NodeKind::NestedNameSpecifier));
324 
325   EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),
326             "[('a', '::'), ('b', null), ('c', '::')]");
327   EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']");
328 }
329 
330 /// "a:: b:: c"  <=> [("a", "::"), ("b", "::"), ("c", null)]
331 TEST_P(ListTest, List_Terminated_MissingLastDelimiter) {
332   if (!GetParam().isCXX()) {
333     return;
334   }
335   buildTree("", GetParam());
336 
337   // "a:: b:: c"
338   auto *List = dyn_cast<syntax::List>(syntax::createTree(
339       *Arena,
340       {
341           {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement},
342           {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter},
343           {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement},
344           {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter},
345           {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement},
346       },
347       NodeKind::NestedNameSpecifier));
348 
349   EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),
350             "[('a', '::'), ('b', '::'), ('c', null)]");
351   EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']");
352 }
353 
354 } // namespace
355