1 //===--- ForestTest.cpp - Test Forest dump ----------------------*- 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-pseudo/Forest.h"
10 #include "clang-pseudo/Token.h"
11 #include "clang/Basic/LangOptions.h"
12 #include "llvm/ADT/StringRef.h"
13 #include "gmock/gmock.h"
14 #include "gtest/gtest.h"
15 #include <vector>
16 
17 namespace clang {
18 namespace pseudo {
19 namespace {
20 
21 // FIXME: extract to a TestGrammar class to allow code sharing among tests.
22 class ForestTest : public ::testing::Test {
23 public:
24   void build(llvm::StringRef BNF) {
25     Diags.clear();
26     G = Grammar::parseBNF(BNF, Diags);
27   }
28 
29   SymbolID symbol(llvm::StringRef Name) const {
30     for (unsigned I = 0; I < NumTerminals; ++I)
31       if (G.table().Terminals[I] == Name)
32         return tokenSymbol(static_cast<tok::TokenKind>(I));
33     for (SymbolID ID = 0; ID < G.table().Nonterminals.size(); ++ID)
34       if (G.table().Nonterminals[ID].Name == Name)
35         return ID;
36     ADD_FAILURE() << "No such symbol found: " << Name;
37     return 0;
38   }
39 
40   RuleID ruleFor(llvm::StringRef NonterminalName) const {
41     auto RuleRange = G.table().Nonterminals[symbol(NonterminalName)].RuleRange;
42     if (RuleRange.End - RuleRange.Start == 1)
43       return G.table().Nonterminals[symbol(NonterminalName)].RuleRange.Start;
44     ADD_FAILURE() << "Expected a single rule for " << NonterminalName
45                   << ", but it has " << RuleRange.End - RuleRange.Start
46                   << " rule!\n";
47     return 0;
48   }
49 
50 protected:
51   Grammar G;
52   std::vector<std::string> Diags;
53 };
54 
55 TEST_F(ForestTest, DumpBasic) {
56   build(R"cpp(
57     _ := add-expression
58     add-expression := id-expression + id-expression
59     id-expression := IDENTIFIER
60   )cpp");
61   ASSERT_TRUE(Diags.empty());
62   ForestArena Arena;
63   const auto &TS =
64       cook(lex("a + b", clang::LangOptions()), clang::LangOptions());
65 
66   auto T = Arena.createTerminals(TS);
67   ASSERT_EQ(T.size(), 3u);
68   const auto *Left = &Arena.createSequence(
69       symbol("id-expression"), ruleFor("id-expression"), {&T.front()});
70   const auto *Right = &Arena.createSequence(symbol("id-expression"),
71                                             ruleFor("id-expression"), {&T[2]});
72 
73   const auto *Add =
74       &Arena.createSequence(symbol("add-expression"), ruleFor("add-expression"),
75                             {Left, &T[1], Right});
76   EXPECT_EQ(Add->dumpRecursive(G, true),
77             "[  0, end) add-expression := id-expression + id-expression\n"
78             "[  0,   1) ├─id-expression~IDENTIFIER := tok[0]\n"
79             "[  1,   2) ├─+ := tok[1]\n"
80             "[  2, end) └─id-expression~IDENTIFIER := tok[2]\n");
81   EXPECT_EQ(Add->dumpRecursive(G, false),
82             "[  0, end) add-expression := id-expression + id-expression\n"
83             "[  0,   1) ├─id-expression := IDENTIFIER\n"
84             "[  0,   1) │ └─IDENTIFIER := tok[0]\n"
85             "[  1,   2) ├─+ := tok[1]\n"
86             "[  2, end) └─id-expression := IDENTIFIER\n"
87             "[  2, end)   └─IDENTIFIER := tok[2]\n");
88 }
89 
90 TEST_F(ForestTest, DumpAmbiguousAndRefs) {
91   build(R"cpp(
92     _ := type
93     type := class-type # rule 3
94     type := enum-type # rule 4
95     class-type := shared-type
96     enum-type := shared-type
97     shared-type := IDENTIFIER)cpp");
98   ASSERT_TRUE(Diags.empty());
99   ForestArena Arena;
100   const auto &TS = cook(lex("abc", clang::LangOptions()), clang::LangOptions());
101 
102   auto Terminals = Arena.createTerminals(TS);
103   ASSERT_EQ(Terminals.size(), 1u);
104 
105   const auto *SharedType = &Arena.createSequence(
106       symbol("shared-type"), ruleFor("shared-type"), {Terminals.begin()});
107   const auto *ClassType = &Arena.createSequence(
108       symbol("class-type"), ruleFor("class-type"), {SharedType});
109   const auto *EnumType = &Arena.createSequence(
110       symbol("enum-type"), ruleFor("enum-type"), {SharedType});
111   const auto *Alternative1 =
112       &Arena.createSequence(symbol("type"), /*RuleID=*/3, {ClassType});
113   const auto *Alternative2 =
114       &Arena.createSequence(symbol("type"), /*RuleID=*/4, {EnumType});
115   const auto *Type =
116       &Arena.createAmbiguous(symbol("type"), {Alternative1, Alternative2});
117   EXPECT_EQ(Type->dumpRecursive(G),
118             "[  0, end) type := <ambiguous>\n"
119             "[  0, end) ├─type := class-type\n"
120             "[  0, end) │ └─class-type := shared-type\n"
121             "[  0, end) │   └─shared-type := IDENTIFIER #1\n"
122             "[  0, end) │     └─IDENTIFIER := tok[0]\n"
123             "[  0, end) └─type := enum-type\n"
124             "[  0, end)   └─enum-type := shared-type\n"
125             "[  0, end)     └─shared-type =#1\n");
126 }
127 
128 TEST_F(ForestTest, DumpAbbreviatedShared) {
129   build(R"cpp(
130     _ := A
131     A := B
132     B := *
133   )cpp");
134 
135   ForestArena Arena;
136   const auto *Star = &Arena.createTerminal(tok::star, 0);
137 
138   const auto *B = &Arena.createSequence(symbol("B"), ruleFor("B"), {Star});
139   // We have two identical (but distinct) A nodes.
140   // The GLR parser would never produce this, but it makes the example simpler.
141   const auto *A1 = &Arena.createSequence(symbol("A"), ruleFor("A"), {B});
142   const auto *A2 = &Arena.createSequence(symbol("A"), ruleFor("A"), {B});
143   const auto *A = &Arena.createAmbiguous(symbol("A"), {A1, A2});
144 
145   // We must not abbreviate away shared nodes: if we show A~* there's no way to
146   // show that the intermediate B node is shared between A1 and A2.
147   EXPECT_EQ(A->dumpRecursive(G, /*Abbreviate=*/true),
148             "[  0, end) A := <ambiguous>\n"
149             "[  0, end) ├─A~B := * #1\n"
150             "[  0, end) │ └─* := tok[0]\n"
151             "[  0, end) └─A~B =#1\n");
152 }
153 
154 TEST_F(ForestTest, Iteration) {
155   //   Z
156   //  / \
157   //  X Y
158   //  |\|
159   //  A B
160   ForestArena Arena;
161   const auto *A = &Arena.createTerminal(tok::identifier, 0);
162   const auto *B = &Arena.createOpaque(1, 0);
163   const auto *X = &Arena.createSequence(2, 1, {A, B});
164   const auto *Y = &Arena.createSequence(2, 2, {B});
165   const auto *Z = &Arena.createAmbiguous(2, {X, Y});
166 
167   std::vector<const ForestNode *> Nodes;
168   for (const ForestNode &N : Z->descendants())
169     Nodes.push_back(&N);
170   EXPECT_THAT(Nodes, testing::UnorderedElementsAre(A, B, X, Y, Z));
171 
172   Nodes.clear();
173   for (const ForestNode &N : X->descendants())
174     Nodes.push_back(&N);
175   EXPECT_THAT(Nodes, testing::UnorderedElementsAre(X, A, B));
176 }
177 
178 } // namespace
179 } // namespace pseudo
180 } // namespace clang
181