1 //===--- GLRTest.cpp - Test the GLR parser ----------------------*- 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/GLR.h" 10 #include "clang-pseudo/Bracket.h" 11 #include "clang-pseudo/Language.h" 12 #include "clang-pseudo/Token.h" 13 #include "clang-pseudo/grammar/Grammar.h" 14 #include "clang/Basic/LangOptions.h" 15 #include "clang/Basic/TokenKinds.h" 16 #include "llvm/ADT/StringExtras.h" 17 #include "llvm/Support/FormatVariadic.h" 18 #include "gmock/gmock.h" 19 #include "gtest/gtest.h" 20 #include <memory> 21 22 namespace clang { 23 namespace pseudo { 24 25 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, 26 const std::vector<const GSS::Node *> &Heads) { 27 for (const auto *Head : Heads) 28 OS << *Head << "\n"; 29 return OS; 30 } 31 32 namespace { 33 34 using StateID = LRTable::StateID; 35 using testing::AllOf; 36 using testing::ElementsAre; 37 using testing::IsEmpty; 38 using testing::UnorderedElementsAre; 39 40 MATCHER_P(state, StateID, "") { return arg->State == StateID; } 41 MATCHER_P(parsedSymbol, FNode, "") { return arg->Payload == FNode; } 42 MATCHER_P(parsedSymbolID, SID, "") { return arg->Payload->symbol() == SID; } 43 MATCHER_P(start, Start, "") { return arg->Payload->startTokenIndex() == Start; } 44 45 testing::Matcher<const GSS::Node *> 46 parents(llvm::ArrayRef<const GSS::Node *> Parents) { 47 return testing::Property(&GSS::Node::parents, 48 testing::UnorderedElementsAreArray(Parents)); 49 } 50 51 Token::Index recoverBraces(Token::Index Begin, const TokenStream &Code) { 52 EXPECT_GT(Begin, 0u); 53 const Token &Left = Code.tokens()[Begin - 1]; 54 EXPECT_EQ(Left.Kind, tok::l_brace); 55 if (const auto* Right = Left.pair()) { 56 EXPECT_EQ(Right->Kind, tok::r_brace); 57 return Code.index(*Right); 58 } 59 return Token::Invalid; 60 } 61 62 class GLRTest : public ::testing::Test { 63 public: 64 void build(llvm::StringRef GrammarBNF) { 65 std::vector<std::string> Diags; 66 TestLang.G = Grammar::parseBNF(GrammarBNF, Diags); 67 } 68 69 TokenStream emptyTokenStream() { 70 TokenStream Empty; 71 Empty.finalize(); 72 return Empty; 73 } 74 75 void buildGrammar(std::vector<std::string> Nonterminals, 76 std::vector<std::string> Rules) { 77 Nonterminals.push_back("_"); 78 llvm::sort(Nonterminals); 79 Nonterminals.erase(std::unique(Nonterminals.begin(), Nonterminals.end()), 80 Nonterminals.end()); 81 std::string FakeTestBNF; 82 for (const auto &NT : Nonterminals) 83 FakeTestBNF += llvm::formatv("{0} := {1}\n", "_", NT); 84 FakeTestBNF += llvm::join(Rules, "\n"); 85 build(FakeTestBNF); 86 } 87 88 SymbolID id(llvm::StringRef Name) const { 89 for (unsigned I = 0; I < NumTerminals; ++I) 90 if (TestLang.G.table().Terminals[I] == Name) 91 return tokenSymbol(static_cast<tok::TokenKind>(I)); 92 for (SymbolID ID = 0; ID < TestLang.G.table().Nonterminals.size(); ++ID) 93 if (TestLang.G.table().Nonterminals[ID].Name == Name) 94 return ID; 95 ADD_FAILURE() << "No such symbol found: " << Name; 96 return 0; 97 } 98 ExtensionID extensionID(llvm::StringRef AttrValueName) const { 99 for (ExtensionID EID = 0; EID < TestLang.G.table().AttributeValues.size(); 100 ++EID) 101 if (TestLang.G.table().AttributeValues[EID] == AttrValueName) 102 return EID; 103 ADD_FAILURE() << "No such attribute value found: " << AttrValueName; 104 return 0; 105 } 106 107 RuleID ruleFor(llvm::StringRef NonterminalName) const { 108 auto RuleRange = 109 TestLang.G.table().Nonterminals[id(NonterminalName)].RuleRange; 110 if (RuleRange.End - RuleRange.Start == 1) 111 return TestLang.G.table() 112 .Nonterminals[id(NonterminalName)] 113 .RuleRange.Start; 114 ADD_FAILURE() << "Expected a single rule for " << NonterminalName 115 << ", but it has " << RuleRange.End - RuleRange.Start 116 << " rule!\n"; 117 return 0; 118 } 119 120 protected: 121 Language TestLang; 122 ForestArena Arena; 123 GSS GSStack; 124 }; 125 126 TEST_F(GLRTest, ShiftMergingHeads) { 127 // Given a test case where we have two heads 1, 2, 3 in the GSS, the heads 1, 128 // 2 have shift actions to reach state 4, and the head 3 has a shift action to 129 // reach state 5: 130 // 0--1 131 // └--2 132 // └--3 133 // After the shift action, the GSS (with new heads 4, 5) is: 134 // 0---1---4 135 // └---2---┘ 136 // └---3---5 137 auto *GSSNode0 = 138 GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{}); 139 auto *GSSNode1 = GSStack.addNode(/*State=*/1, /*ForestNode=*/nullptr, 140 /*Parents=*/{GSSNode0}); 141 auto *GSSNode2 = GSStack.addNode(/*State=*/2, /*ForestNode=*/nullptr, 142 /*Parents=*/{GSSNode0}); 143 auto *GSSNode3 = GSStack.addNode(/*State=*/3, /*ForestNode=*/nullptr, 144 /*Parents=*/{GSSNode0}); 145 146 buildGrammar({}, {}); // Create a fake empty grammar. 147 LRTable::Builder B(TestLang.G); 148 B.Transition[{StateID{1}, tokenSymbol(tok::semi)}] = StateID{4}; 149 B.Transition[{StateID{2}, tokenSymbol(tok::semi)}] = StateID{4}; 150 B.Transition[{StateID{3}, tokenSymbol(tok::semi)}] = StateID{5}; 151 TestLang.Table = std::move(B).build(); 152 153 ForestNode &SemiTerminal = Arena.createTerminal(tok::semi, 0); 154 std::vector<const GSS::Node *> NewHeads; 155 glrShift({GSSNode1, GSSNode2, GSSNode3}, SemiTerminal, 156 {emptyTokenStream(), Arena, GSStack}, TestLang, NewHeads); 157 158 EXPECT_THAT(NewHeads, 159 UnorderedElementsAre(AllOf(state(4), parsedSymbol(&SemiTerminal), 160 parents({GSSNode1, GSSNode2})), 161 AllOf(state(5), parsedSymbol(&SemiTerminal), 162 parents({GSSNode3})))) 163 << NewHeads; 164 } 165 166 TEST_F(GLRTest, ReduceConflictsSplitting) { 167 // Before (splitting due to R/R conflict): 168 // 0--1(IDENTIFIER) 169 // After reducing 1 by `class-name := IDENTIFIER` and 170 // `enum-name := IDENTIFIER`: 171 // 0--2(class-name) // 2 is goto(0, class-name) 172 // └--3(enum-name) // 3 is goto(0, enum-name) 173 buildGrammar({"class-name", "enum-name"}, 174 {"class-name := IDENTIFIER", "enum-name := IDENTIFIER"}); 175 LRTable::Builder B(TestLang.G); 176 B.Transition[{StateID{0}, id("class-name")}] = StateID{2}; 177 B.Transition[{StateID{0}, id("enum-name")}] = StateID{3}; 178 B.Reduce[StateID{1}].insert(ruleFor("class-name")); 179 B.Reduce[StateID{1}].insert(ruleFor("enum-name")); 180 TestLang.Table = std::move(B).build(); 181 182 const auto *GSSNode0 = 183 GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{}); 184 const auto *GSSNode1 = 185 GSStack.addNode(1, &Arena.createTerminal(tok::identifier, 0), {GSSNode0}); 186 187 std::vector<const GSS::Node *> Heads = {GSSNode1}; 188 glrReduce(Heads, tokenSymbol(tok::eof), 189 {emptyTokenStream(), Arena, GSStack}, TestLang); 190 EXPECT_THAT(Heads, UnorderedElementsAre( 191 GSSNode1, 192 AllOf(state(2), parsedSymbolID(id("class-name")), 193 parents({GSSNode0})), 194 AllOf(state(3), parsedSymbolID(id("enum-name")), 195 parents({GSSNode0})))) 196 << Heads; 197 } 198 199 TEST_F(GLRTest, ReduceSplittingDueToMultipleBases) { 200 // Before (splitting due to multiple bases): 201 // 2(class-name)--4(*) 202 // 3(enum-name)---┘ 203 // After reducing 4 by `ptr-operator := *`: 204 // 2(class-name)--5(ptr-operator) // 5 is goto(2, ptr-operator) 205 // 3(enum-name)---6(ptr-operator) // 6 is goto(3, ptr-operator) 206 buildGrammar({"ptr-operator", "class-name", "enum-name"}, 207 {"ptr-operator := *"}); 208 209 auto *ClassNameNode = &Arena.createOpaque(id("class-name"), /*TokenIndex=*/0); 210 auto *EnumNameNode = &Arena.createOpaque(id("enum-name"), /*TokenIndex=*/0); 211 212 const auto *GSSNode2 = 213 GSStack.addNode(/*State=*/2, /*ForestNode=*/ClassNameNode, /*Parents=*/{}); 214 const auto *GSSNode3 = 215 GSStack.addNode(/*State=*/3, /*ForestNode=*/EnumNameNode, /*Parents=*/{}); 216 const auto *GSSNode4 = GSStack.addNode( 217 /*State=*/4, &Arena.createTerminal(tok::star, /*TokenIndex=*/1), 218 /*Parents=*/{GSSNode2, GSSNode3}); 219 220 LRTable::Builder B(TestLang.G); 221 B.Transition[{StateID{2}, id("ptr-operator")}] = StateID{5}; 222 B.Transition[{StateID{3}, id("ptr-operator")}] = StateID{6}; 223 B.Reduce[StateID{4}].insert(ruleFor("ptr-operator")); 224 TestLang.Table = std::move(B).build(); 225 226 std::vector<const GSS::Node *> Heads = {GSSNode4}; 227 glrReduce(Heads, tokenSymbol(tok::eof), {emptyTokenStream(), Arena, GSStack}, 228 TestLang); 229 230 EXPECT_THAT(Heads, UnorderedElementsAre( 231 GSSNode4, 232 AllOf(state(5), parsedSymbolID(id("ptr-operator")), 233 parents({GSSNode2})), 234 AllOf(state(6), parsedSymbolID(id("ptr-operator")), 235 parents({GSSNode3})))) 236 << Heads; 237 // Verify that the payload of the two new heads is shared, only a single 238 // ptr-operator node is created in the forest. 239 EXPECT_EQ(Heads[1]->Payload, Heads[2]->Payload); 240 } 241 242 TEST_F(GLRTest, ReduceJoiningWithMultipleBases) { 243 // Before (joining due to same goto state, multiple bases): 244 // 0--1(cv-qualifier)--3(class-name) 245 // └--2(cv-qualifier)--4(enum-name) 246 // After reducing 3 by `type-name := class-name` and 247 // 4 by `type-name := enum-name`: 248 // 0--1(cv-qualifier)--5(type-name) // 5 is goto(1, type-name) and 249 // └--2(cv-qualifier)--┘ // goto(2, type-name) 250 buildGrammar({"type-name", "class-name", "enum-name", "cv-qualifier"}, 251 {"type-name := class-name", "type-name := enum-name"}); 252 253 auto *CVQualifierNode = 254 &Arena.createOpaque(id("cv-qualifier"), /*TokenIndex=*/0); 255 auto *ClassNameNode = &Arena.createOpaque(id("class-name"), /*TokenIndex=*/1); 256 auto *EnumNameNode = &Arena.createOpaque(id("enum-name"), /*TokenIndex=*/1); 257 258 const auto *GSSNode0 = 259 GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{}); 260 const auto *GSSNode1 = GSStack.addNode( 261 /*State=*/1, /*ForestNode=*/CVQualifierNode, /*Parents=*/{GSSNode0}); 262 const auto *GSSNode2 = GSStack.addNode( 263 /*State=*/2, /*ForestNode=*/CVQualifierNode, /*Parents=*/{GSSNode0}); 264 const auto *GSSNode3 = GSStack.addNode( 265 /*State=*/3, /*ForestNode=*/ClassNameNode, 266 /*Parents=*/{GSSNode1}); 267 const auto *GSSNode4 = 268 GSStack.addNode(/*State=*/4, /*ForestNode=*/EnumNameNode, 269 /*Parents=*/{GSSNode2}); 270 271 // FIXME: figure out a way to get rid of the hard-coded reduce RuleID! 272 LRTable::Builder B(TestLang.G); 273 B.Transition[{StateID{1}, id("type-name")}] = StateID{5}; 274 B.Transition[{StateID{2}, id("type-name")}] = StateID{5}; 275 B.Reduce[StateID{3}].insert(/* type-name := class-name */ RuleID{0}); 276 B.Reduce[StateID{4}].insert(/* type-name := enum-name */ RuleID{1}); 277 TestLang.Table = std::move(B).build(); 278 279 std::vector<const GSS::Node *> Heads = {GSSNode3, GSSNode4}; 280 glrReduce(Heads, tokenSymbol(tok::eof), {emptyTokenStream(), Arena, GSStack}, 281 TestLang); 282 283 // Verify that the stack heads are joint at state 5 after reduces. 284 EXPECT_THAT(Heads, UnorderedElementsAre(GSSNode3, GSSNode4, 285 AllOf(state(5), 286 parsedSymbolID(id("type-name")), 287 parents({GSSNode1, GSSNode2})))) 288 << Heads; 289 // Verify that we create an ambiguous ForestNode of two parses of `type-name`. 290 EXPECT_EQ(Heads.back()->Payload->dumpRecursive(TestLang.G), 291 "[ 1, end) type-name := <ambiguous>\n" 292 "[ 1, end) ├─type-name := class-name\n" 293 "[ 1, end) │ └─class-name := <opaque>\n" 294 "[ 1, end) └─type-name := enum-name\n" 295 "[ 1, end) └─enum-name := <opaque>\n"); 296 } 297 298 TEST_F(GLRTest, ReduceJoiningWithSameBase) { 299 // Before (joining due to same goto state, the same base): 300 // 0--1(class-name)--3(*) 301 // └--2(enum-name)--4(*) 302 // After reducing 3 by `pointer := class-name *` and 303 // 2 by `pointer := enum-name *`: 304 // 0--5(pointer) // 5 is goto(0, pointer) 305 buildGrammar({"pointer", "class-name", "enum-name"}, 306 {"pointer := class-name *", "pointer := enum-name *"}); 307 308 auto *ClassNameNode = &Arena.createOpaque(id("class-name"), /*TokenIndex=*/0); 309 auto *EnumNameNode = &Arena.createOpaque(id("enum-name"), /*TokenIndex=*/0); 310 auto *StartTerminal = &Arena.createTerminal(tok::star, /*TokenIndex=*/1); 311 312 const auto *GSSNode0 = 313 GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{}); 314 const auto *GSSNode1 = 315 GSStack.addNode(/*State=*/1, /*ForestNode=*/ClassNameNode, 316 /*Parents=*/{GSSNode0}); 317 const auto *GSSNode2 = 318 GSStack.addNode(/*State=*/2, /*ForestNode=*/EnumNameNode, 319 /*Parents=*/{GSSNode0}); 320 const auto *GSSNode3 = 321 GSStack.addNode(/*State=*/3, /*ForestNode=*/StartTerminal, 322 /*Parents=*/{GSSNode1}); 323 const auto *GSSNode4 = 324 GSStack.addNode(/*State=*/4, /*ForestNode=*/StartTerminal, 325 /*Parents=*/{GSSNode2}); 326 327 // FIXME: figure out a way to get rid of the hard-coded reduce RuleID! 328 LRTable::Builder B(TestLang.G); 329 B.Transition[{StateID{0}, id("pointer")}] = StateID{5}; 330 B.Reduce[StateID{3}].insert(/* pointer := class-name */ RuleID{0}); 331 B.Reduce[StateID{4}].insert(/* pointer := enum-name */ RuleID{1}); 332 TestLang.Table = std::move(B).build(); 333 334 std::vector<const GSS::Node *> Heads = {GSSNode3, GSSNode4}; 335 glrReduce(Heads, tokenSymbol(tok::eof), 336 {emptyTokenStream(), Arena, GSStack}, TestLang); 337 338 EXPECT_THAT( 339 Heads, UnorderedElementsAre(GSSNode3, GSSNode4, 340 AllOf(state(5), parsedSymbolID(id("pointer")), 341 parents({GSSNode0})))) 342 << Heads; 343 EXPECT_EQ(Heads.back()->Payload->dumpRecursive(TestLang.G), 344 "[ 0, end) pointer := <ambiguous>\n" 345 "[ 0, end) ├─pointer := class-name *\n" 346 "[ 0, 1) │ ├─class-name := <opaque>\n" 347 "[ 1, end) │ └─* := tok[1]\n" 348 "[ 0, end) └─pointer := enum-name *\n" 349 "[ 0, 1) ├─enum-name := <opaque>\n" 350 "[ 1, end) └─* := tok[1]\n"); 351 } 352 353 TEST_F(GLRTest, ReduceLookahead) { 354 // A term can be followed by +, but not by -. 355 buildGrammar({"sum", "term"}, {"expr := term + term", "term := IDENTIFIER"}); 356 LRTable::Builder B(TestLang.G); 357 B.Transition[{StateID{0}, id("term")}] = StateID{2}; 358 B.Reduce[StateID{1}].insert(RuleID{0}); 359 TestLang.Table = std::move(B).build(); 360 361 auto *Identifier = &Arena.createTerminal(tok::identifier, /*Start=*/0); 362 363 const auto *Root = 364 GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{}); 365 const auto *GSSNode1 = 366 GSStack.addNode(/*State=*/1, /*ForestNode=*/Identifier, {Root}); 367 368 // When the lookahead is +, reduce is performed. 369 std::vector<const GSS::Node *> Heads = {GSSNode1}; 370 glrReduce(Heads, tokenSymbol(tok::plus), {emptyTokenStream(), Arena, GSStack}, 371 TestLang); 372 EXPECT_THAT(Heads, 373 ElementsAre(GSSNode1, AllOf(state(2), parsedSymbolID(id("term")), 374 parents(Root)))); 375 376 // When the lookahead is -, reduce is not performed. 377 Heads = {GSSNode1}; 378 glrReduce(Heads, tokenSymbol(tok::minus), 379 {emptyTokenStream(), Arena, GSStack}, TestLang); 380 EXPECT_THAT(Heads, ElementsAre(GSSNode1)); 381 } 382 383 TEST_F(GLRTest, Recover) { 384 // Recovery while parsing "word" inside braces. 385 // Before: 386 // 0--1({)--2(?) 387 // After recovering a `word` at state 1: 388 // 0--3(word) // 3 is goto(1, word) 389 buildGrammar({"word", "top"}, {"top := { word [recover=Braces] }"}); 390 LRTable::Builder B(TestLang.G); 391 B.Transition[{StateID{1}, id("word")}] = StateID{3}; 392 B.Recoveries.push_back({StateID{1}, {extensionID("Braces"), id("word")}}); 393 TestLang.Table = std::move(B).build(); 394 TestLang.RecoveryStrategies.try_emplace(extensionID("Braces"), recoverBraces); 395 396 auto *LBrace = &Arena.createTerminal(tok::l_brace, 0); 397 auto *Question1 = &Arena.createTerminal(tok::question, 1); 398 const auto *Root = GSStack.addNode(0, nullptr, {}); 399 const auto *OpenedBraces = GSStack.addNode(1, LBrace, {Root}); 400 const auto *AfterQuestion1 = GSStack.addNode(2, Question1, {OpenedBraces}); 401 402 // Need a token stream with paired braces so the strategy works. 403 clang::LangOptions LOptions; 404 TokenStream Tokens = cook(lex("{ ? ? ? }", LOptions), LOptions); 405 pairBrackets(Tokens); 406 std::vector<const GSS::Node *> NewHeads; 407 408 unsigned TokenIndex = 2; 409 glrRecover({AfterQuestion1}, TokenIndex, {Tokens, Arena, GSStack}, TestLang, 410 NewHeads); 411 EXPECT_EQ(TokenIndex, 4u) << "should skip ahead to matching brace"; 412 EXPECT_THAT(NewHeads, ElementsAre(AllOf(state(3), parsedSymbolID(id("word")), 413 parents({OpenedBraces}), start(1u)))); 414 EXPECT_EQ(NewHeads.front()->Payload->kind(), ForestNode::Opaque); 415 416 // Test recovery failure: omit closing brace so strategy fails 417 TokenStream NoRBrace = cook(lex("{ ? ? ? ?", LOptions), LOptions); 418 pairBrackets(NoRBrace); 419 NewHeads.clear(); 420 TokenIndex = 2; 421 glrRecover({AfterQuestion1}, TokenIndex, {NoRBrace, Arena, GSStack}, TestLang, 422 NewHeads); 423 EXPECT_EQ(TokenIndex, 2u) << "should not advance on failure"; 424 EXPECT_THAT(NewHeads, IsEmpty()); 425 } 426 427 TEST_F(GLRTest, RecoverRightmost) { 428 // In a nested block structure, we recover at the innermost possible block. 429 // Before: 430 // 0--1({)--1({)--1({) 431 // After recovering a `block` at inside the second braces: 432 // 0--1({)--2(body) // 2 is goto(1, body) 433 buildGrammar({"body", "top"}, {"top := { body [recover=Braces] }"}); 434 LRTable::Builder B(TestLang.G); 435 B.Transition[{StateID{1}, id("body")}] = StateID{2}; 436 B.Recoveries.push_back({StateID{1}, {extensionID("Braces"), id("body")}}); 437 TestLang.Table = std::move(B).build(); 438 TestLang.RecoveryStrategies.try_emplace(extensionID("Braces"), recoverBraces); 439 440 clang::LangOptions LOptions; 441 // Innermost brace is unmatched, to test fallback to next brace. 442 TokenStream Tokens = cook(lex("{ { { ? } }", LOptions), LOptions); 443 Tokens.tokens()[0].Pair = 5; 444 Tokens.tokens()[1].Pair = 4; 445 Tokens.tokens()[4].Pair = 1; 446 Tokens.tokens()[5].Pair = 0; 447 448 auto *Brace1 = &Arena.createTerminal(tok::l_brace, 0); 449 auto *Brace2 = &Arena.createTerminal(tok::l_brace, 1); 450 auto *Brace3 = &Arena.createTerminal(tok::l_brace, 2); 451 const auto *Root = GSStack.addNode(0, nullptr, {}); 452 const auto *In1 = GSStack.addNode(1, Brace1, {Root}); 453 const auto *In2 = GSStack.addNode(1, Brace2, {In1}); 454 const auto *In3 = GSStack.addNode(1, Brace3, {In2}); 455 456 unsigned TokenIndex = 3; 457 std::vector<const GSS::Node *> NewHeads; 458 glrRecover({In3}, TokenIndex, {Tokens, Arena, GSStack}, TestLang, NewHeads); 459 EXPECT_EQ(TokenIndex, 5u); 460 EXPECT_THAT(NewHeads, ElementsAre(AllOf(state(2), parsedSymbolID(id("body")), 461 parents({In2}), start(2u)))); 462 } 463 464 TEST_F(GLRTest, RecoverAlternatives) { 465 // Recovery inside braces with multiple equally good options 466 // Before: 467 // 0--1({) 468 // After recovering either `word` or `number` inside the braces: 469 // 0--1({)--2(word) // 2 is goto(1, word) 470 // └--3(number) // 3 is goto(1, number) 471 buildGrammar({"number", "word", "top"}, 472 { 473 "top := { number [recover=Braces] }", 474 "top := { word [recover=Braces] }", 475 }); 476 LRTable::Builder B(TestLang.G); 477 B.Transition[{StateID{1}, id("number")}] = StateID{2}; 478 B.Transition[{StateID{1}, id("word")}] = StateID{3}; 479 B.Recoveries.push_back({StateID{1}, {extensionID("Braces"), id("number")}}); 480 B.Recoveries.push_back({StateID{1}, {extensionID("Braces"), id("word")}}); 481 TestLang.RecoveryStrategies.try_emplace(extensionID("Braces"), recoverBraces); 482 TestLang.Table = std::move(B).build(); 483 auto *LBrace = &Arena.createTerminal(tok::l_brace, 0); 484 const auto *Root = GSStack.addNode(0, nullptr, {}); 485 const auto *OpenedBraces = GSStack.addNode(1, LBrace, {Root}); 486 487 clang::LangOptions LOptions; 488 TokenStream Tokens = cook(lex("{ ? }", LOptions), LOptions); 489 pairBrackets(Tokens); 490 std::vector<const GSS::Node *> NewHeads; 491 unsigned TokenIndex = 1; 492 493 glrRecover({OpenedBraces}, TokenIndex, {Tokens, Arena, GSStack}, TestLang, 494 NewHeads); 495 EXPECT_EQ(TokenIndex, 2u); 496 EXPECT_THAT(NewHeads, 497 UnorderedElementsAre(AllOf(state(2), parsedSymbolID(id("number")), 498 parents({OpenedBraces}), start(1u)), 499 AllOf(state(3), parsedSymbolID(id("word")), 500 parents({OpenedBraces}), start(1u)))); 501 } 502 503 TEST_F(GLRTest, PerfectForestNodeSharing) { 504 // Run the GLR on a simple grammar and test that we build exactly one forest 505 // node per (SymbolID, token range). 506 507 // This is a grmammar where the original parsing-stack-based forest node 508 // sharing approach will fail. In its LR0 graph, it has two states containing 509 // item `expr := • IDENTIFIER`, and both have different goto states on the 510 // nonterminal `expr`. 511 build(R"bnf( 512 _ := test 513 514 test := { expr 515 test := { IDENTIFIER 516 test := left-paren expr 517 left-paren := { 518 expr := IDENTIFIER 519 )bnf"); 520 TestLang.Table = LRTable::buildSLR(TestLang.G); 521 clang::LangOptions LOptions; 522 const TokenStream &Tokens = cook(lex("{ abc", LOptions), LOptions); 523 524 const ForestNode &Parsed = 525 glrParse({Tokens, Arena, GSStack}, id("test"), TestLang); 526 // Verify that there is no duplicated sequence node of `expr := IDENTIFIER` 527 // in the forest, see the `#1` and `=#1` in the dump string. 528 EXPECT_EQ(Parsed.dumpRecursive(TestLang.G), 529 "[ 0, end) test := <ambiguous>\n" 530 "[ 0, end) ├─test := { expr\n" 531 "[ 0, 1) │ ├─{ := tok[0]\n" 532 "[ 1, end) │ └─expr := IDENTIFIER #1\n" 533 "[ 1, end) │ └─IDENTIFIER := tok[1]\n" 534 "[ 0, end) ├─test := { IDENTIFIER\n" 535 "[ 0, 1) │ ├─{ := tok[0]\n" 536 "[ 1, end) │ └─IDENTIFIER := tok[1]\n" 537 "[ 0, end) └─test := left-paren expr\n" 538 "[ 0, 1) ├─left-paren := {\n" 539 "[ 0, 1) │ └─{ := tok[0]\n" 540 "[ 1, end) └─expr =#1\n"); 541 } 542 543 TEST_F(GLRTest, GLRReduceOrder) { 544 // Given the following grammar, and the input `IDENTIFIER`, reductions should 545 // be performed in the following order: 546 // 1. foo := IDENTIFIER 547 // 2. { test := IDENTIFIER, test := foo } 548 // foo should be reduced first, so that in step 2 we have completed reduces 549 // for test, and form an ambiguous forest node. 550 build(R"bnf( 551 _ := test 552 553 test := IDENTIFIER 554 test := foo 555 foo := IDENTIFIER 556 )bnf"); 557 clang::LangOptions LOptions; 558 const TokenStream &Tokens = cook(lex("IDENTIFIER", LOptions), LOptions); 559 TestLang.Table = LRTable::buildSLR(TestLang.G); 560 561 const ForestNode &Parsed = 562 glrParse({Tokens, Arena, GSStack}, id("test"), TestLang); 563 EXPECT_EQ(Parsed.dumpRecursive(TestLang.G), 564 "[ 0, end) test := <ambiguous>\n" 565 "[ 0, end) ├─test := IDENTIFIER\n" 566 "[ 0, end) │ └─IDENTIFIER := tok[0]\n" 567 "[ 0, end) └─test := foo\n" 568 "[ 0, end) └─foo := IDENTIFIER\n" 569 "[ 0, end) └─IDENTIFIER := tok[0]\n"); 570 } 571 572 TEST_F(GLRTest, RecoveryEndToEnd) { 573 // Simple example of brace-based recovery showing: 574 // - recovered region includes tokens both ahead of and behind the cursor 575 // - multiple possible recovery rules 576 // - recovery from outer scopes is rejected 577 build(R"bnf( 578 _ := block 579 580 block := { block [recover=Braces] } 581 block := { numbers [recover=Braces] } 582 numbers := NUMERIC_CONSTANT NUMERIC_CONSTANT 583 )bnf"); 584 TestLang.Table = LRTable::buildSLR(TestLang.G); 585 TestLang.RecoveryStrategies.try_emplace(extensionID("Braces"), recoverBraces); 586 clang::LangOptions LOptions; 587 TokenStream Tokens = cook(lex("{ { 42 ? } }", LOptions), LOptions); 588 pairBrackets(Tokens); 589 590 const ForestNode &Parsed = 591 glrParse({Tokens, Arena, GSStack}, id("block"), TestLang); 592 EXPECT_EQ(Parsed.dumpRecursive(TestLang.G), 593 "[ 0, end) block := { block [recover=Braces] }\n" 594 "[ 0, 1) ├─{ := tok[0]\n" 595 "[ 1, 5) ├─block := <ambiguous>\n" 596 "[ 1, 5) │ ├─block := { block [recover=Braces] }\n" 597 "[ 1, 2) │ │ ├─{ := tok[1]\n" 598 "[ 2, 4) │ │ ├─block := <opaque>\n" 599 "[ 4, 5) │ │ └─} := tok[4]\n" 600 "[ 1, 5) │ └─block := { numbers [recover=Braces] }\n" 601 "[ 1, 2) │ ├─{ := tok[1]\n" 602 "[ 2, 4) │ ├─numbers := <opaque>\n" 603 "[ 4, 5) │ └─} := tok[4]\n" 604 "[ 5, end) └─} := tok[5]\n"); 605 } 606 607 TEST_F(GLRTest, NoExplicitAccept) { 608 build(R"bnf( 609 _ := test 610 611 test := IDENTIFIER test 612 test := IDENTIFIER 613 )bnf"); 614 clang::LangOptions LOptions; 615 // Given the following input, and the grammar above, we perform two reductions 616 // of the nonterminal `test` when the next token is `eof`, verify that the 617 // parser stops at the right state. 618 const TokenStream &Tokens = cook(lex("id id", LOptions), LOptions); 619 TestLang.Table = LRTable::buildSLR(TestLang.G); 620 621 const ForestNode &Parsed = 622 glrParse({Tokens, Arena, GSStack}, id("test"), TestLang); 623 EXPECT_EQ(Parsed.dumpRecursive(TestLang.G), 624 "[ 0, end) test := IDENTIFIER test\n" 625 "[ 0, 1) ├─IDENTIFIER := tok[0]\n" 626 "[ 1, end) └─test := IDENTIFIER\n" 627 "[ 1, end) └─IDENTIFIER := tok[1]\n"); 628 } 629 630 TEST_F(GLRTest, GuardExtension) { 631 build(R"bnf( 632 _ := start 633 634 start := IDENTIFIER [guard=TestOnly] 635 )bnf"); 636 TestLang.Guards.try_emplace( 637 extensionID("TestOnly"), 638 [&](llvm::ArrayRef<const ForestNode *> RHS, const TokenStream &Tokens) { 639 assert(RHS.size() == 1 && 640 RHS.front()->symbol() == tokenSymbol(clang::tok::identifier)); 641 return Tokens.tokens()[RHS.front()->startTokenIndex()].text() == "test"; 642 }); 643 clang::LangOptions LOptions; 644 TestLang.Table = LRTable::buildSLR(TestLang.G); 645 646 std::string Input = "test"; 647 const TokenStream &Succeeded = cook(lex(Input, LOptions), LOptions); 648 EXPECT_EQ(glrParse({Succeeded, Arena, GSStack}, id("start"), TestLang) 649 .dumpRecursive(TestLang.G), 650 "[ 0, end) start := IDENTIFIER [guard=TestOnly]\n" 651 "[ 0, end) └─IDENTIFIER := tok[0]\n"); 652 653 Input = "notest"; 654 const TokenStream &Failed = cook(lex(Input, LOptions), LOptions); 655 EXPECT_EQ(glrParse({Failed, Arena, GSStack}, id("start"), TestLang) 656 .dumpRecursive(TestLang.G), 657 "[ 0, end) start := <opaque>\n"); 658 } 659 660 TEST(GSSTest, GC) { 661 // ┌-A-┬-AB 662 // ├-B-┘ 663 // Root-+-C 664 // ├-D 665 // └-E 666 GSS GSStack; 667 auto *Root = GSStack.addNode(0, nullptr, {}); 668 auto *A = GSStack.addNode(0, nullptr, {Root}); 669 auto *B = GSStack.addNode(0, nullptr, {Root}); 670 auto *C = GSStack.addNode(0, nullptr, {Root}); 671 auto *D = GSStack.addNode(0, nullptr, {Root}); 672 auto *AB = GSStack.addNode(0, nullptr, {A, B}); 673 674 EXPECT_EQ(1u, GSStack.gc({AB, C})) << "D is destroyed"; 675 EXPECT_EQ(0u, GSStack.gc({AB, C})) << "D is already gone"; 676 auto *E = GSStack.addNode(0, nullptr, {Root}); 677 EXPECT_EQ(D, E) << "Storage of GCed node D is reused for E"; 678 EXPECT_EQ(3u, GSStack.gc({A, E})) << "Destroys B, AB, C"; 679 EXPECT_EQ(1u, GSStack.gc({E})) << "Destroys A"; 680 } 681 682 } // namespace 683 } // namespace pseudo 684 } // namespace clang 685