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