1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
//===- TreeTest.cpp ---------------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "clang/Tooling/Syntax/Tree.h"
#include "TreeTestBase.h"
#include "clang/Tooling/Syntax/BuildTree.h"
#include "gtest/gtest.h"
using namespace clang;
using namespace clang::syntax;
namespace {
class TreeTest : public SyntaxTreeTest {
private:
Tree *createTree(ArrayRef<const Node *> Children) {
std::vector<std::pair<Node *, NodeRole>> ChildrenWithRoles;
ChildrenWithRoles.reserve(Children.size());
for (const auto *Child : Children) {
ChildrenWithRoles.push_back(
std::make_pair(deepCopy(*Arena, Child), NodeRole::Unknown));
}
return clang::syntax::createTree(*Arena, ChildrenWithRoles,
NodeKind::UnknownExpression);
}
// Generate Forests by combining `Children` into `ParentCount` Trees.
//
// We do this recursively.
std::vector<std::vector<const Tree *>>
generateAllForests(ArrayRef<const Node *> Children, unsigned ParentCount) {
assert(ParentCount > 0);
// If there is only one Parent node, then combine `Children` under
// this Parent.
if (ParentCount == 1)
return {{createTree(Children)}};
// Otherwise, combine `ChildrenCount` children under the last parent and
// solve the smaller problem without these children and this parent. Do this
// for every `ChildrenCount` and combine the results.
std::vector<std::vector<const Tree *>> AllForests;
for (unsigned ChildrenCount = 0; ChildrenCount <= Children.size();
++ChildrenCount) {
auto *LastParent = createTree(Children.take_back(ChildrenCount));
for (auto &Forest : generateAllForests(Children.drop_back(ChildrenCount),
ParentCount - 1)) {
Forest.push_back(LastParent);
AllForests.push_back(Forest);
}
}
return AllForests;
}
protected:
// Generates all trees with a `Base` of `Node`s and `NodeCountPerLayer`
// `Node`s per layer. An example of Tree with `Base` = {`(`, `)`} and
// `NodeCountPerLayer` = {2, 2}:
// Tree
// |-Tree
// `-Tree
// |-Tree
// | `-'('
// `-Tree
// `-')'
std::vector<const Tree *>
generateAllTreesWithShape(ArrayRef<const Node *> Base,
ArrayRef<unsigned> NodeCountPerLayer) {
// We compute the solution per layer. A layer is a collection of bases,
// where each base has the same number of nodes, given by
// `NodeCountPerLayer`.
auto GenerateNextLayer = [this](ArrayRef<std::vector<const Node *>> Layer,
unsigned NextLayerNodeCount) {
std::vector<std::vector<const Node *>> NextLayer;
for (const auto &Base : Layer) {
for (const auto &NextBase :
generateAllForests(Base, NextLayerNodeCount)) {
NextLayer.push_back(
std::vector<const Node *>(NextBase.begin(), NextBase.end()));
}
}
return NextLayer;
};
std::vector<std::vector<const Node *>> Layer = {Base};
for (auto NodeCount : NodeCountPerLayer)
Layer = GenerateNextLayer(Layer, NodeCount);
std::vector<const Tree *> AllTrees;
AllTrees.reserve(Layer.size());
for (const auto &Base : Layer)
AllTrees.push_back(createTree(Base));
return AllTrees;
}
};
INSTANTIATE_TEST_CASE_P(TreeTests, TreeTest,
::testing::ValuesIn(allTestClangConfigs()), );
TEST_P(TreeTest, FirstLeaf) {
buildTree("", GetParam());
std::vector<const Node *> Leafs = {createLeaf(*Arena, tok::l_paren),
createLeaf(*Arena, tok::r_paren)};
for (const auto *Tree : generateAllTreesWithShape(Leafs, {3u})) {
ASSERT_TRUE(Tree->findFirstLeaf() != nullptr);
EXPECT_EQ(Tree->findFirstLeaf()->getToken()->kind(), tok::l_paren);
}
}
TEST_P(TreeTest, LastLeaf) {
buildTree("", GetParam());
std::vector<const Node *> Leafs = {createLeaf(*Arena, tok::l_paren),
createLeaf(*Arena, tok::r_paren)};
for (const auto *Tree : generateAllTreesWithShape(Leafs, {3u})) {
ASSERT_TRUE(Tree->findLastLeaf() != nullptr);
EXPECT_EQ(Tree->findLastLeaf()->getToken()->kind(), tok::r_paren);
}
}
} // namespace
|
