1 //===--- GrammarTest.cpp - grammar tests  -----------------------*- 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/grammar/Grammar.h"
10 #include "gmock/gmock.h"
11 #include "gtest/gtest.h"
12 #include <memory>
13 
14 namespace clang {
15 namespace pseudo {
16 namespace {
17 
18 using testing::AllOf;
19 using testing::ElementsAre;
20 using testing::IsEmpty;
21 using testing::Pair;
22 using testing::UnorderedElementsAre;
23 
24 MATCHER_P(TargetID, SID, "") { return arg.Target == SID; }
25 template <typename... T> testing::Matcher<const Rule &> Sequence(T... IDs) {
26   return testing::Property(&Rule::seq, ElementsAre(IDs...));
27 }
28 
29 class GrammarTest : public ::testing::Test {
30 public:
31   void build(llvm::StringRef BNF) {
32     Diags.clear();
33     G = Grammar::parseBNF(BNF, Diags);
34   }
35 
36   SymbolID id(llvm::StringRef Name) const {
37     for (unsigned I = 0; I < NumTerminals; ++I)
38       if (G.table().Terminals[I] == Name)
39         return tokenSymbol(static_cast<tok::TokenKind>(I));
40     for (SymbolID ID = 0; ID < G.table().Nonterminals.size(); ++ID)
41       if (G.table().Nonterminals[ID].Name == Name)
42         return ID;
43     ADD_FAILURE() << "No such symbol found: " << Name;
44     return 0;
45   }
46 
47   RuleID ruleFor(llvm::StringRef NonterminalName) const {
48     auto RuleRange = G.table().Nonterminals[id(NonterminalName)].RuleRange;
49     if (RuleRange.End - RuleRange.Start == 1)
50       return G.table().Nonterminals[id(NonterminalName)].RuleRange.Start;
51     ADD_FAILURE() << "Expected a single rule for " << NonterminalName
52                   << ", but it has " << RuleRange.End - RuleRange.Start
53                   << " rule!\n";
54     return 0;
55   }
56 
57 protected:
58   Grammar G;
59   std::vector<std::string> Diags;
60 };
61 
62 TEST_F(GrammarTest, Basic) {
63   build("_ := IDENTIFIER + _ # comment");
64   EXPECT_THAT(Diags, IsEmpty());
65 
66   auto ExpectedRule =
67       AllOf(TargetID(id("_")), Sequence(id("IDENTIFIER"), id("+"), id("_")));
68   EXPECT_EQ(G.symbolName(id("_")), "_");
69   EXPECT_THAT(G.rulesFor(id("_")), UnorderedElementsAre(ExpectedRule));
70   const auto &Rule = G.lookupRule(/*RID=*/0);
71   EXPECT_THAT(Rule, ExpectedRule);
72   EXPECT_THAT(G.symbolName(Rule.seq()[0]), "IDENTIFIER");
73   EXPECT_THAT(G.symbolName(Rule.seq()[1]), "+");
74   EXPECT_THAT(G.symbolName(Rule.seq()[2]), "_");
75 }
76 
77 TEST_F(GrammarTest, EliminatedOptional) {
78   build("_ := CONST_opt INT ;_opt");
79   EXPECT_THAT(Diags, IsEmpty());
80   EXPECT_THAT(G.table().Rules,
81               UnorderedElementsAre(Sequence(id("INT")),
82                                    Sequence(id("CONST"), id("INT")),
83                                    Sequence(id("CONST"), id("INT"), id(";")),
84                                    Sequence(id("INT"), id(";"))));
85 }
86 
87 TEST_F(GrammarTest, RuleIDSorted) {
88   build(R"bnf(
89     _ := x
90 
91     x := y
92     y := z
93     z := IDENTIFIER
94   )bnf");
95   ASSERT_TRUE(Diags.empty());
96 
97   EXPECT_LT(ruleFor("z"), ruleFor("y"));
98   EXPECT_LT(ruleFor("y"), ruleFor("x"));
99   EXPECT_LT(ruleFor("x"), ruleFor("_"));
100 }
101 
102 TEST_F(GrammarTest, Annotation) {
103   build(R"bnf(
104     _ := x
105 
106     x := y [guard=value]
107     y := IDENTIFIER [guard=final]
108 
109   )bnf");
110   ASSERT_TRUE(Diags.empty());
111   EXPECT_EQ(G.lookupRule(ruleFor("_")).Guard, 0);
112   EXPECT_GT(G.lookupRule(ruleFor("x")).Guard, 0);
113   EXPECT_GT(G.lookupRule(ruleFor("y")).Guard, 0);
114   EXPECT_NE(G.lookupRule(ruleFor("x")).Guard, G.lookupRule(ruleFor("y")).Guard);
115 }
116 
117 TEST_F(GrammarTest, MangleName) {
118   build(R"bnf(
119     _ := declaration
120 
121     declaration := ptr-declarator ;
122     ptr-declarator := * IDENTIFIER
123 
124   )bnf");
125   ASSERT_TRUE(Diags.empty());
126   EXPECT_EQ(G.mangleRule(ruleFor("declaration")),
127             "declaration_0ptr_declarator_1semi");
128   EXPECT_EQ(G.mangleRule(ruleFor("ptr-declarator")),
129             "ptr_declarator_0star_1identifier");
130 }
131 
132 TEST_F(GrammarTest, Diagnostics) {
133   build(R"cpp(
134     _ := ,_opt
135     _ := undefined-sym
136     null :=
137     _ := IDENFIFIE # a typo of the terminal IDENFITIER
138 
139     invalid
140     # cycle
141     a := b
142     b := a
143 
144     _ := IDENTIFIER [unknown=value]
145   )cpp");
146 
147   EXPECT_EQ(G.underscore(), id("_"));
148   EXPECT_THAT(Diags, UnorderedElementsAre(
149                          "Rule '_ := ,_opt' has a nullable RHS",
150                          "Rule 'null := ' has a nullable RHS",
151                          "No rules for nonterminal: undefined-sym",
152                          "Failed to parse 'invalid': no separator :=",
153                          "Token-like name IDENFIFIE is used as a nonterminal",
154                          "No rules for nonterminal: IDENFIFIE",
155                          "The grammar contains a cycle involving symbol a",
156                          "Unknown attribute 'unknown'"));
157 }
158 
159 TEST_F(GrammarTest, FirstAndFollowSets) {
160   build(
161       R"bnf(
162 _ := expr
163 expr := expr - term
164 expr := term
165 term := IDENTIFIER
166 term := ( expr )
167 )bnf");
168   ASSERT_TRUE(Diags.empty());
169   auto ToPairs = [](std::vector<llvm::DenseSet<SymbolID>> Input) {
170     std::vector<std::pair<SymbolID, llvm::DenseSet<SymbolID>>> Sets;
171     for (SymbolID ID = 0; ID < Input.size(); ++ID)
172       Sets.emplace_back(ID, std::move(Input[ID]));
173     return Sets;
174   };
175 
176   EXPECT_THAT(
177       ToPairs(firstSets(G)),
178       UnorderedElementsAre(
179           Pair(id("_"), UnorderedElementsAre(id("IDENTIFIER"), id("("))),
180           Pair(id("expr"), UnorderedElementsAre(id("IDENTIFIER"), id("("))),
181           Pair(id("term"), UnorderedElementsAre(id("IDENTIFIER"), id("(")))));
182   EXPECT_THAT(
183       ToPairs(followSets(G)),
184       UnorderedElementsAre(
185           Pair(id("_"), UnorderedElementsAre(id("EOF"))),
186           Pair(id("expr"), UnorderedElementsAre(id("-"), id("EOF"), id(")"))),
187           Pair(id("term"), UnorderedElementsAre(id("-"), id("EOF"), id(")")))));
188 
189   build(R"bnf(
190 # A simplfied C++ decl-specifier-seq.
191 _ := decl-specifier-seq
192 decl-specifier-seq := decl-specifier decl-specifier-seq
193 decl-specifier-seq := decl-specifier
194 decl-specifier := simple-type-specifier
195 decl-specifier := INLINE
196 simple-type-specifier := INT
197    )bnf");
198   ASSERT_TRUE(Diags.empty());
199   EXPECT_THAT(
200       ToPairs(firstSets(G)),
201       UnorderedElementsAre(
202           Pair(id("_"), UnorderedElementsAre(id("INLINE"), id("INT"))),
203           Pair(id("decl-specifier-seq"),
204                UnorderedElementsAre(id("INLINE"), id("INT"))),
205           Pair(id("simple-type-specifier"), UnorderedElementsAre(id("INT"))),
206           Pair(id("decl-specifier"),
207                UnorderedElementsAre(id("INLINE"), id("INT")))));
208   EXPECT_THAT(
209       ToPairs(followSets(G)),
210       UnorderedElementsAre(
211           Pair(id("_"), UnorderedElementsAre(id("EOF"))),
212           Pair(id("decl-specifier-seq"), UnorderedElementsAre(id("EOF"))),
213           Pair(id("decl-specifier"),
214                UnorderedElementsAre(id("INLINE"), id("INT"), id("EOF"))),
215           Pair(id("simple-type-specifier"),
216                UnorderedElementsAre(id("INLINE"), id("INT"), id("EOF")))));
217 }
218 
219 } // namespace
220 } // namespace pseudo
221 } // namespace clang
222