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; }
Sequence(T...IDs)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:
build(llvm::StringRef BNF)31   void build(llvm::StringRef BNF) {
32     Diags.clear();
33     G = Grammar::parseBNF(BNF, Diags);
34   }
35 
id(llvm::StringRef Name) const36   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 
ruleFor(llvm::StringRef NonterminalName) const47   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 
TEST_F(GrammarTest,Basic)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 
TEST_F(GrammarTest,EliminatedOptional)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 
TEST_F(GrammarTest,RuleIDSorted)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 
TEST_F(GrammarTest,Annotation)102 TEST_F(GrammarTest, Annotation) {
103   build(R"bnf(
104     _ := x
105     x := IDENTIFIER [guard]
106   )bnf");
107   ASSERT_THAT(Diags, IsEmpty());
108   EXPECT_FALSE(G.lookupRule(ruleFor("_")).Guarded);
109   EXPECT_TRUE(G.lookupRule(ruleFor("x")).Guarded);
110 }
111 
TEST_F(GrammarTest,MangleName)112 TEST_F(GrammarTest, MangleName) {
113   build(R"bnf(
114     _ := declaration
115 
116     declaration := ptr-declarator ;
117     ptr-declarator := * IDENTIFIER
118 
119   )bnf");
120   ASSERT_TRUE(Diags.empty());
121   EXPECT_EQ(G.mangleRule(ruleFor("declaration")),
122             "declaration_0ptr_declarator_1semi");
123   EXPECT_EQ(G.mangleRule(ruleFor("ptr-declarator")),
124             "ptr_declarator_0star_1identifier");
125 }
126 
TEST_F(GrammarTest,Diagnostics)127 TEST_F(GrammarTest, Diagnostics) {
128   build(R"cpp(
129     _ := ,_opt
130     _ := undefined-sym
131     null :=
132     _ := IDENFIFIE # a typo of the terminal IDENFITIER
133 
134     invalid
135     # cycle
136     a := b
137     b := a
138 
139     _ := IDENTIFIER [unknown=value]
140   )cpp");
141 
142   EXPECT_EQ(G.underscore(), id("_"));
143   EXPECT_THAT(Diags, UnorderedElementsAre(
144                          "Rule '_ := ,_opt' has a nullable RHS",
145                          "Rule 'null := ' has a nullable RHS",
146                          "No rules for nonterminal: undefined-sym",
147                          "Failed to parse 'invalid': no separator :=",
148                          "Token-like name IDENFIFIE is used as a nonterminal",
149                          "No rules for nonterminal: IDENFIFIE",
150                          "The grammar contains a cycle involving symbol a",
151                          "Unknown attribute 'unknown'"));
152 }
153 
TEST_F(GrammarTest,FirstAndFollowSets)154 TEST_F(GrammarTest, FirstAndFollowSets) {
155   build(
156       R"bnf(
157 _ := expr
158 expr := expr - term
159 expr := term
160 term := IDENTIFIER
161 term := ( expr )
162 )bnf");
163   ASSERT_TRUE(Diags.empty());
164   auto ToPairs = [](std::vector<llvm::DenseSet<SymbolID>> Input) {
165     std::vector<std::pair<SymbolID, llvm::DenseSet<SymbolID>>> Sets;
166     for (SymbolID ID = 0; ID < Input.size(); ++ID)
167       Sets.emplace_back(ID, std::move(Input[ID]));
168     return Sets;
169   };
170 
171   EXPECT_THAT(
172       ToPairs(firstSets(G)),
173       UnorderedElementsAre(
174           Pair(id("_"), UnorderedElementsAre(id("IDENTIFIER"), id("("))),
175           Pair(id("expr"), UnorderedElementsAre(id("IDENTIFIER"), id("("))),
176           Pair(id("term"), UnorderedElementsAre(id("IDENTIFIER"), id("(")))));
177   EXPECT_THAT(
178       ToPairs(followSets(G)),
179       UnorderedElementsAre(
180           Pair(id("_"), UnorderedElementsAre(id("EOF"))),
181           Pair(id("expr"), UnorderedElementsAre(id("-"), id("EOF"), id(")"))),
182           Pair(id("term"), UnorderedElementsAre(id("-"), id("EOF"), id(")")))));
183 
184   build(R"bnf(
185 # A simplfied C++ decl-specifier-seq.
186 _ := decl-specifier-seq
187 decl-specifier-seq := decl-specifier decl-specifier-seq
188 decl-specifier-seq := decl-specifier
189 decl-specifier := simple-type-specifier
190 decl-specifier := INLINE
191 simple-type-specifier := INT
192    )bnf");
193   ASSERT_TRUE(Diags.empty());
194   EXPECT_THAT(
195       ToPairs(firstSets(G)),
196       UnorderedElementsAre(
197           Pair(id("_"), UnorderedElementsAre(id("INLINE"), id("INT"))),
198           Pair(id("decl-specifier-seq"),
199                UnorderedElementsAre(id("INLINE"), id("INT"))),
200           Pair(id("simple-type-specifier"), UnorderedElementsAre(id("INT"))),
201           Pair(id("decl-specifier"),
202                UnorderedElementsAre(id("INLINE"), id("INT")))));
203   EXPECT_THAT(
204       ToPairs(followSets(G)),
205       UnorderedElementsAre(
206           Pair(id("_"), UnorderedElementsAre(id("EOF"))),
207           Pair(id("decl-specifier-seq"), UnorderedElementsAre(id("EOF"))),
208           Pair(id("decl-specifier"),
209                UnorderedElementsAre(id("INLINE"), id("INT"), id("EOF"))),
210           Pair(id("simple-type-specifier"),
211                UnorderedElementsAre(id("INLINE"), id("INT"), id("EOF")))));
212 }
213 
214 } // namespace
215 } // namespace pseudo
216 } // namespace clang
217