//===--- GLRTest.cpp - Test the GLR parser ----------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "clang-pseudo/GLR.h"
#include "clang-pseudo/Bracket.h"
#include "clang-pseudo/Language.h"
#include "clang-pseudo/Token.h"
#include "clang-pseudo/grammar/Grammar.h"
#include "clang/Basic/LangOptions.h"
#include "clang/Basic/TokenKinds.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/FormatVariadic.h"
#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include <memory>

namespace clang {
namespace pseudo {

llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                              const std::vector<const GSS::Node *> &Heads) {
  for (const auto *Head : Heads)
    OS << *Head << "\n";
  return OS;
}

namespace {

using StateID = LRTable::StateID;
using testing::AllOf;
using testing::ElementsAre;
using testing::IsEmpty;
using testing::UnorderedElementsAre;

MATCHER_P(state, StateID, "") { return arg->State == StateID; }
MATCHER_P(parsedSymbol, FNode, "") { return arg->Payload == FNode; }
MATCHER_P(parsedSymbolID, SID, "") { return arg->Payload->symbol() == SID; }
MATCHER_P(start, Start, "") { return arg->Payload->startTokenIndex() == Start; }

testing::Matcher<const GSS::Node *>
parents(llvm::ArrayRef<const GSS::Node *> Parents) {
  return testing::Property(&GSS::Node::parents,
                           testing::UnorderedElementsAreArray(Parents));
}

Token::Index recoverBraces(Token::Index Begin, const TokenStream &Code) {
  EXPECT_GT(Begin, 0u);
  const Token &Left = Code.tokens()[Begin - 1];
  EXPECT_EQ(Left.Kind, tok::l_brace);
  if (const auto* Right = Left.pair()) {
    EXPECT_EQ(Right->Kind, tok::r_brace);
    return Code.index(*Right);
  }
  return Token::Invalid;
}

class GLRTest : public ::testing::Test {
public:
  void build(llvm::StringRef GrammarBNF) {
    std::vector<std::string> Diags;
    TestLang.G = Grammar::parseBNF(GrammarBNF, Diags);
  }

  TokenStream emptyTokenStream() {
    TokenStream Empty;
    Empty.finalize();
    return Empty;
  }
 
  void buildGrammar(std::vector<std::string> Nonterminals,
                    std::vector<std::string> Rules) {
    Nonterminals.push_back("_");
    llvm::sort(Nonterminals);
    Nonterminals.erase(std::unique(Nonterminals.begin(), Nonterminals.end()),
                       Nonterminals.end());
    std::string FakeTestBNF;
    for (const auto &NT : Nonterminals)
      FakeTestBNF += llvm::formatv("{0} := {1}\n", "_", NT);
    FakeTestBNF += llvm::join(Rules, "\n");
    build(FakeTestBNF);
  }

  SymbolID id(llvm::StringRef Name) const {
    for (unsigned I = 0; I < NumTerminals; ++I)
      if (TestLang.G.table().Terminals[I] == Name)
        return tokenSymbol(static_cast<tok::TokenKind>(I));
    for (SymbolID ID = 0; ID < TestLang.G.table().Nonterminals.size(); ++ID)
      if (TestLang.G.table().Nonterminals[ID].Name == Name)
        return ID;
    ADD_FAILURE() << "No such symbol found: " << Name;
    return 0;
  }
  ExtensionID extensionID(llvm::StringRef AttrValueName) const {
    for (ExtensionID EID = 0; EID < TestLang.G.table().AttributeValues.size();
         ++EID)
      if (TestLang.G.table().AttributeValues[EID] == AttrValueName)
        return EID;
    ADD_FAILURE() << "No such attribute value found: " << AttrValueName;
    return 0;
  }

  RuleID ruleFor(llvm::StringRef NonterminalName) const {
    auto RuleRange =
        TestLang.G.table().Nonterminals[id(NonterminalName)].RuleRange;
    if (RuleRange.End - RuleRange.Start == 1)
      return TestLang.G.table()
          .Nonterminals[id(NonterminalName)]
          .RuleRange.Start;
    ADD_FAILURE() << "Expected a single rule for " << NonterminalName
                  << ", but it has " << RuleRange.End - RuleRange.Start
                  << " rule!\n";
    return 0;
  }

protected:
  Language TestLang;
  ForestArena Arena;
  GSS GSStack;
};

TEST_F(GLRTest, ShiftMergingHeads) {
  // Given a test case where we have two heads 1, 2, 3 in the GSS, the heads 1,
  // 2 have shift actions to reach state 4, and the head 3 has a shift action to
  // reach state 5:
  //   0--1
  //   └--2
  //   └--3
  // After the shift action, the GSS (with new heads 4, 5) is:
  //   0---1---4
  //   └---2---┘
  //   └---3---5
  auto *GSSNode0 =
      GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{});
  auto *GSSNode1 = GSStack.addNode(/*State=*/1, /*ForestNode=*/nullptr,
                                   /*Parents=*/{GSSNode0});
  auto *GSSNode2 = GSStack.addNode(/*State=*/2, /*ForestNode=*/nullptr,
                                   /*Parents=*/{GSSNode0});
  auto *GSSNode3 = GSStack.addNode(/*State=*/3, /*ForestNode=*/nullptr,
                                   /*Parents=*/{GSSNode0});

  buildGrammar({}, {}); // Create a fake empty grammar.
  LRTable::Builder B(TestLang.G);
  B.Transition[{StateID{1}, tokenSymbol(tok::semi)}] = StateID{4};
  B.Transition[{StateID{2}, tokenSymbol(tok::semi)}] = StateID{4};
  B.Transition[{StateID{3}, tokenSymbol(tok::semi)}] = StateID{5};
  TestLang.Table = std::move(B).build();

  ForestNode &SemiTerminal = Arena.createTerminal(tok::semi, 0);
  std::vector<const GSS::Node *> NewHeads;
  glrShift({GSSNode1, GSSNode2, GSSNode3}, SemiTerminal,
           {emptyTokenStream(), Arena, GSStack}, TestLang, NewHeads);

  EXPECT_THAT(NewHeads,
              UnorderedElementsAre(AllOf(state(4), parsedSymbol(&SemiTerminal),
                                         parents({GSSNode1, GSSNode2})),
                                   AllOf(state(5), parsedSymbol(&SemiTerminal),
                                         parents({GSSNode3}))))
      << NewHeads;
}

TEST_F(GLRTest, ReduceConflictsSplitting) {
  //  Before (splitting due to R/R conflict):
  //    0--1(IDENTIFIER)
  //  After reducing 1 by `class-name := IDENTIFIER` and
  //                      `enum-name := IDENTIFIER`:
  //    0--2(class-name)    // 2 is goto(0, class-name)
  //    └--3(enum-name)     // 3 is goto(0, enum-name)
  buildGrammar({"class-name", "enum-name"},
               {"class-name := IDENTIFIER", "enum-name := IDENTIFIER"});
  LRTable::Builder B(TestLang.G);
  B.Transition[{StateID{0}, id("class-name")}] = StateID{2};
  B.Transition[{StateID{0}, id("enum-name")}] = StateID{3};
  B.Reduce[StateID{1}].insert(ruleFor("class-name"));
  B.Reduce[StateID{1}].insert(ruleFor("enum-name"));
  TestLang.Table = std::move(B).build();

  const auto *GSSNode0 =
      GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{});
  const auto *GSSNode1 =
      GSStack.addNode(1, &Arena.createTerminal(tok::identifier, 0), {GSSNode0});

  std::vector<const GSS::Node *> Heads = {GSSNode1};
  glrReduce(Heads, tokenSymbol(tok::eof),
            {emptyTokenStream(), Arena, GSStack}, TestLang);
  EXPECT_THAT(Heads, UnorderedElementsAre(
                         GSSNode1,
                         AllOf(state(2), parsedSymbolID(id("class-name")),
                               parents({GSSNode0})),
                         AllOf(state(3), parsedSymbolID(id("enum-name")),
                               parents({GSSNode0}))))
      << Heads;
}

TEST_F(GLRTest, ReduceSplittingDueToMultipleBases) {
  //  Before (splitting due to multiple bases):
  //    2(class-name)--4(*)
  //    3(enum-name)---┘
  //  After reducing 4 by `ptr-operator := *`:
  //    2(class-name)--5(ptr-operator)    // 5 is goto(2, ptr-operator)
  //    3(enum-name)---6(ptr-operator)    // 6 is goto(3, ptr-operator)
  buildGrammar({"ptr-operator", "class-name", "enum-name"},
               {"ptr-operator := *"});

  auto *ClassNameNode = &Arena.createOpaque(id("class-name"), /*TokenIndex=*/0);
  auto *EnumNameNode = &Arena.createOpaque(id("enum-name"), /*TokenIndex=*/0);

  const auto *GSSNode2 =
      GSStack.addNode(/*State=*/2, /*ForestNode=*/ClassNameNode, /*Parents=*/{});
  const auto *GSSNode3 =
      GSStack.addNode(/*State=*/3, /*ForestNode=*/EnumNameNode, /*Parents=*/{});
  const auto *GSSNode4 = GSStack.addNode(
      /*State=*/4, &Arena.createTerminal(tok::star, /*TokenIndex=*/1),
      /*Parents=*/{GSSNode2, GSSNode3});

  LRTable::Builder B(TestLang.G);
  B.Transition[{StateID{2}, id("ptr-operator")}] = StateID{5};
  B.Transition[{StateID{3}, id("ptr-operator")}] = StateID{6};
  B.Reduce[StateID{4}].insert(ruleFor("ptr-operator"));
  TestLang.Table = std::move(B).build();

  std::vector<const GSS::Node *> Heads = {GSSNode4};
  glrReduce(Heads, tokenSymbol(tok::eof), {emptyTokenStream(), Arena, GSStack},
            TestLang);

  EXPECT_THAT(Heads, UnorderedElementsAre(
                         GSSNode4,
                         AllOf(state(5), parsedSymbolID(id("ptr-operator")),
                               parents({GSSNode2})),
                         AllOf(state(6), parsedSymbolID(id("ptr-operator")),
                               parents({GSSNode3}))))
      << Heads;
  // Verify that the payload of the two new heads is shared, only a single
  // ptr-operator node is created in the forest.
  EXPECT_EQ(Heads[1]->Payload, Heads[2]->Payload);
}

TEST_F(GLRTest, ReduceJoiningWithMultipleBases) {
  //  Before (joining due to same goto state, multiple bases):
  //    0--1(cv-qualifier)--3(class-name)
  //    └--2(cv-qualifier)--4(enum-name)
  //  After reducing 3 by `type-name := class-name` and
  //                 4 by `type-name := enum-name`:
  //    0--1(cv-qualifier)--5(type-name)  // 5 is goto(1, type-name) and
  //    └--2(cv-qualifier)--┘             // goto(2, type-name)
  buildGrammar({"type-name", "class-name", "enum-name", "cv-qualifier"},
               {"type-name := class-name", "type-name := enum-name"});

  auto *CVQualifierNode =
      &Arena.createOpaque(id("cv-qualifier"), /*TokenIndex=*/0);
  auto *ClassNameNode = &Arena.createOpaque(id("class-name"), /*TokenIndex=*/1);
  auto *EnumNameNode = &Arena.createOpaque(id("enum-name"), /*TokenIndex=*/1);

  const auto *GSSNode0 =
      GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{});
  const auto *GSSNode1 = GSStack.addNode(
      /*State=*/1, /*ForestNode=*/CVQualifierNode, /*Parents=*/{GSSNode0});
  const auto *GSSNode2 = GSStack.addNode(
      /*State=*/2, /*ForestNode=*/CVQualifierNode, /*Parents=*/{GSSNode0});
  const auto *GSSNode3 = GSStack.addNode(
      /*State=*/3, /*ForestNode=*/ClassNameNode,
      /*Parents=*/{GSSNode1});
  const auto *GSSNode4 =
      GSStack.addNode(/*State=*/4, /*ForestNode=*/EnumNameNode,
                      /*Parents=*/{GSSNode2});

  // FIXME: figure out a way to get rid of the hard-coded reduce RuleID!
  LRTable::Builder B(TestLang.G);
  B.Transition[{StateID{1}, id("type-name")}] = StateID{5};
  B.Transition[{StateID{2}, id("type-name")}] = StateID{5};
  B.Reduce[StateID{3}].insert(/* type-name := class-name */ RuleID{0});
  B.Reduce[StateID{4}].insert(/* type-name := enum-name */ RuleID{1});
  TestLang.Table = std::move(B).build();

  std::vector<const GSS::Node *> Heads = {GSSNode3, GSSNode4};
  glrReduce(Heads, tokenSymbol(tok::eof), {emptyTokenStream(), Arena, GSStack},
            TestLang);

  // Verify that the stack heads are joint at state 5 after reduces.
  EXPECT_THAT(Heads, UnorderedElementsAre(GSSNode3, GSSNode4,
                                          AllOf(state(5),
                                                parsedSymbolID(id("type-name")),
                                                parents({GSSNode1, GSSNode2}))))
      << Heads;
  // Verify that we create an ambiguous ForestNode of two parses of `type-name`.
  EXPECT_EQ(Heads.back()->Payload->dumpRecursive(TestLang.G),
            "[  1, end) type-name := <ambiguous>\n"
            "[  1, end) ├─type-name := class-name\n"
            "[  1, end) │ └─class-name := <opaque>\n"
            "[  1, end) └─type-name := enum-name\n"
            "[  1, end)   └─enum-name := <opaque>\n");
}

TEST_F(GLRTest, ReduceJoiningWithSameBase) {
  //  Before (joining due to same goto state, the same base):
  //    0--1(class-name)--3(*)
  //    └--2(enum-name)--4(*)
  //  After reducing 3 by `pointer := class-name *` and
  //                 2 by `pointer := enum-name *`:
  //    0--5(pointer)  // 5 is goto(0, pointer)
  buildGrammar({"pointer", "class-name", "enum-name"},
               {"pointer := class-name *", "pointer := enum-name *"});

  auto *ClassNameNode = &Arena.createOpaque(id("class-name"), /*TokenIndex=*/0);
  auto *EnumNameNode = &Arena.createOpaque(id("enum-name"), /*TokenIndex=*/0);
  auto *StartTerminal = &Arena.createTerminal(tok::star, /*TokenIndex=*/1);

  const auto *GSSNode0 =
      GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{});
  const auto *GSSNode1 =
      GSStack.addNode(/*State=*/1, /*ForestNode=*/ClassNameNode,
                      /*Parents=*/{GSSNode0});
  const auto *GSSNode2 =
      GSStack.addNode(/*State=*/2, /*ForestNode=*/EnumNameNode,
                      /*Parents=*/{GSSNode0});
  const auto *GSSNode3 =
      GSStack.addNode(/*State=*/3, /*ForestNode=*/StartTerminal,
                      /*Parents=*/{GSSNode1});
  const auto *GSSNode4 =
      GSStack.addNode(/*State=*/4, /*ForestNode=*/StartTerminal,
                      /*Parents=*/{GSSNode2});

  // FIXME: figure out a way to get rid of the hard-coded reduce RuleID!
  LRTable::Builder B(TestLang.G);
  B.Transition[{StateID{0}, id("pointer")}] = StateID{5};
  B.Reduce[StateID{3}].insert(/* pointer := class-name */ RuleID{0});
  B.Reduce[StateID{4}].insert(/* pointer := enum-name */ RuleID{1});
  TestLang.Table = std::move(B).build();

  std::vector<const GSS::Node *> Heads = {GSSNode3, GSSNode4};
  glrReduce(Heads, tokenSymbol(tok::eof),
            {emptyTokenStream(), Arena, GSStack}, TestLang);

  EXPECT_THAT(
      Heads, UnorderedElementsAre(GSSNode3, GSSNode4,
                                  AllOf(state(5), parsedSymbolID(id("pointer")),
                                        parents({GSSNode0}))))
      << Heads;
  EXPECT_EQ(Heads.back()->Payload->dumpRecursive(TestLang.G),
            "[  0, end) pointer := <ambiguous>\n"
            "[  0, end) ├─pointer := class-name *\n"
            "[  0,   1) │ ├─class-name := <opaque>\n"
            "[  1, end) │ └─* := tok[1]\n"
            "[  0, end) └─pointer := enum-name *\n"
            "[  0,   1)   ├─enum-name := <opaque>\n"
            "[  1, end)   └─* := tok[1]\n");
}

TEST_F(GLRTest, ReduceLookahead) {
  // A term can be followed by +, but not by -.
  buildGrammar({"sum", "term"}, {"expr := term + term", "term := IDENTIFIER"});
  LRTable::Builder B(TestLang.G);
  B.Transition[{StateID{0}, id("term")}] = StateID{2};
  B.Reduce[StateID{1}].insert(RuleID{0});
  TestLang.Table = std::move(B).build();

  auto *Identifier = &Arena.createTerminal(tok::identifier, /*Start=*/0);

  const auto *Root =
      GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{});
  const auto *GSSNode1 =
      GSStack.addNode(/*State=*/1, /*ForestNode=*/Identifier, {Root});

  // When the lookahead is +, reduce is performed.
  std::vector<const GSS::Node *> Heads = {GSSNode1};
  glrReduce(Heads, tokenSymbol(tok::plus), {emptyTokenStream(), Arena, GSStack},
            TestLang);
  EXPECT_THAT(Heads,
              ElementsAre(GSSNode1, AllOf(state(2), parsedSymbolID(id("term")),
                                          parents(Root))));

  // When the lookahead is -, reduce is not performed.
  Heads = {GSSNode1};
  glrReduce(Heads, tokenSymbol(tok::minus),
            {emptyTokenStream(), Arena, GSStack}, TestLang);
  EXPECT_THAT(Heads, ElementsAre(GSSNode1));
}

TEST_F(GLRTest, Recover) {
  // Recovery while parsing "word" inside braces.
  //  Before:
  //    0--1({)--2(?)
  //  After recovering a `word` at state 1:
  //    0--3(word)  // 3 is goto(1, word)
  buildGrammar({"word", "top"}, {"top := { word [recover=Braces] }"});
  LRTable::Builder B(TestLang.G);
  B.Transition[{StateID{1}, id("word")}] = StateID{3};
  B.Recoveries.push_back({StateID{1}, {extensionID("Braces"), id("word")}});
  TestLang.Table = std::move(B).build();
  TestLang.RecoveryStrategies.try_emplace(extensionID("Braces"), recoverBraces);

  auto *LBrace = &Arena.createTerminal(tok::l_brace, 0);
  auto *Question1 = &Arena.createTerminal(tok::question, 1);
  const auto *Root = GSStack.addNode(0, nullptr, {});
  const auto *OpenedBraces = GSStack.addNode(1, LBrace, {Root});
  const auto *AfterQuestion1 = GSStack.addNode(2, Question1, {OpenedBraces});

  // Need a token stream with paired braces so the strategy works.
  clang::LangOptions LOptions;
  TokenStream Tokens = cook(lex("{ ? ? ? }", LOptions), LOptions);
  pairBrackets(Tokens);
  std::vector<const GSS::Node *> NewHeads;

  unsigned TokenIndex = 2;
  glrRecover({AfterQuestion1}, TokenIndex, {Tokens, Arena, GSStack}, TestLang,
             NewHeads);
  EXPECT_EQ(TokenIndex, 4u) << "should skip ahead to matching brace";
  EXPECT_THAT(NewHeads, ElementsAre(AllOf(state(3), parsedSymbolID(id("word")),
                                          parents({OpenedBraces}), start(1u))));
  EXPECT_EQ(NewHeads.front()->Payload->kind(), ForestNode::Opaque);

  // Test recovery failure: omit closing brace so strategy fails
  TokenStream NoRBrace = cook(lex("{ ? ? ? ?", LOptions), LOptions);
  pairBrackets(NoRBrace);
  NewHeads.clear();
  TokenIndex = 2;
  glrRecover({AfterQuestion1}, TokenIndex, {NoRBrace, Arena, GSStack}, TestLang,
             NewHeads);
  EXPECT_EQ(TokenIndex, 2u) << "should not advance on failure";
  EXPECT_THAT(NewHeads, IsEmpty());
}

TEST_F(GLRTest, RecoverRightmost) {
  // In a nested block structure, we recover at the innermost possible block.
  //  Before:
  //    0--1({)--1({)--1({)
  //  After recovering a `block` at inside the second braces:
  //    0--1({)--2(body)  // 2 is goto(1, body)
  buildGrammar({"body", "top"}, {"top := { body [recover=Braces] }"});
  LRTable::Builder B(TestLang.G);
  B.Transition[{StateID{1}, id("body")}] = StateID{2};
  B.Recoveries.push_back({StateID{1}, {extensionID("Braces"), id("body")}});
  TestLang.Table = std::move(B).build();
  TestLang.RecoveryStrategies.try_emplace(extensionID("Braces"), recoverBraces);

  clang::LangOptions LOptions;
  // Innermost brace is unmatched, to test fallback to next brace.
  TokenStream Tokens = cook(lex("{ { { ? } }", LOptions), LOptions);
  Tokens.tokens()[0].Pair = 5;
  Tokens.tokens()[1].Pair = 4;
  Tokens.tokens()[4].Pair = 1;
  Tokens.tokens()[5].Pair = 0;

  auto *Brace1 = &Arena.createTerminal(tok::l_brace, 0);
  auto *Brace2 = &Arena.createTerminal(tok::l_brace, 1);
  auto *Brace3 = &Arena.createTerminal(tok::l_brace, 2);
  const auto *Root = GSStack.addNode(0, nullptr, {});
  const auto *In1 = GSStack.addNode(1, Brace1, {Root});
  const auto *In2 = GSStack.addNode(1, Brace2, {In1});
  const auto *In3 = GSStack.addNode(1, Brace3, {In2});

  unsigned TokenIndex = 3;
  std::vector<const GSS::Node *> NewHeads;
  glrRecover({In3}, TokenIndex, {Tokens, Arena, GSStack}, TestLang, NewHeads);
  EXPECT_EQ(TokenIndex, 5u);
  EXPECT_THAT(NewHeads, ElementsAre(AllOf(state(2), parsedSymbolID(id("body")),
                                          parents({In2}), start(2u))));
}

TEST_F(GLRTest, RecoverAlternatives) {
  // Recovery inside braces with multiple equally good options
  //  Before:
  //    0--1({)
  //  After recovering either `word` or `number` inside the braces:
  //    0--1({)--2(word)   // 2 is goto(1, word)
  //          └--3(number) // 3 is goto(1, number)
  buildGrammar({"number", "word", "top"},
               {
                   "top := { number [recover=Braces] }",
                   "top := { word [recover=Braces] }",
               });
  LRTable::Builder B(TestLang.G);
  B.Transition[{StateID{1}, id("number")}] = StateID{2};
  B.Transition[{StateID{1}, id("word")}] = StateID{3};
  B.Recoveries.push_back({StateID{1}, {extensionID("Braces"), id("number")}});
  B.Recoveries.push_back({StateID{1}, {extensionID("Braces"), id("word")}});
  TestLang.RecoveryStrategies.try_emplace(extensionID("Braces"), recoverBraces);
  TestLang.Table = std::move(B).build();
  auto *LBrace = &Arena.createTerminal(tok::l_brace, 0);
  const auto *Root = GSStack.addNode(0, nullptr, {});
  const auto *OpenedBraces = GSStack.addNode(1, LBrace, {Root});

  clang::LangOptions LOptions;
  TokenStream Tokens = cook(lex("{ ? }", LOptions), LOptions);
  pairBrackets(Tokens);
  std::vector<const GSS::Node *> NewHeads;
  unsigned TokenIndex = 1;

  glrRecover({OpenedBraces}, TokenIndex, {Tokens, Arena, GSStack}, TestLang,
             NewHeads);
  EXPECT_EQ(TokenIndex, 2u);
  EXPECT_THAT(NewHeads,
              UnorderedElementsAre(AllOf(state(2), parsedSymbolID(id("number")),
                                         parents({OpenedBraces}), start(1u)),
                                   AllOf(state(3), parsedSymbolID(id("word")),
                                         parents({OpenedBraces}), start(1u))));
}

TEST_F(GLRTest, PerfectForestNodeSharing) {
  // Run the GLR on a simple grammar and test that we build exactly one forest
  // node per (SymbolID, token range).

  // This is a grmammar where the original parsing-stack-based forest node
  // sharing approach will fail. In its LR0 graph, it has two states containing
  // item `expr := • IDENTIFIER`, and both have different goto states on the
  // nonterminal `expr`.
  build(R"bnf(
    _ := test EOF

    test := { expr
    test := { IDENTIFIER
    test := left-paren expr
    left-paren := {
    expr := IDENTIFIER
  )bnf");
  TestLang.Table = LRTable::buildSLR(TestLang.G);
  clang::LangOptions LOptions;
  const TokenStream &Tokens = cook(lex("{ abc", LOptions), LOptions);

  const ForestNode &Parsed =
      glrParse({Tokens, Arena, GSStack}, id("test"), TestLang);
  // Verify that there is no duplicated sequence node of `expr := IDENTIFIER`
  // in the forest, see the `#1` and `=#1` in the dump string.
  EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
            "[  0, end) test := <ambiguous>\n"
            "[  0, end) ├─test := { expr\n"
            "[  0,   1) │ ├─{ := tok[0]\n"
            "[  1, end) │ └─expr := IDENTIFIER #1\n"
            "[  1, end) │   └─IDENTIFIER := tok[1]\n"
            "[  0, end) ├─test := { IDENTIFIER\n"
            "[  0,   1) │ ├─{ := tok[0]\n"
            "[  1, end) │ └─IDENTIFIER := tok[1]\n"
            "[  0, end) └─test := left-paren expr\n"
            "[  0,   1)   ├─left-paren := {\n"
            "[  0,   1)   │ └─{ := tok[0]\n"
            "[  1, end)   └─expr =#1\n");
}

TEST_F(GLRTest, GLRReduceOrder) {
  // Given the following grammar, and the input `IDENTIFIER`, reductions should
  // be performed in the following order:
  //  1. foo := IDENTIFIER
  //  2. { test := IDENTIFIER, test := foo }
  // foo should be reduced first, so that in step 2 we have completed reduces
  // for test, and form an ambiguous forest node.
  build(R"bnf(
    _ := test EOF

    test := IDENTIFIER
    test := foo
    foo := IDENTIFIER
  )bnf");
  clang::LangOptions LOptions;
  const TokenStream &Tokens = cook(lex("IDENTIFIER", LOptions), LOptions);
  TestLang.Table = LRTable::buildSLR(TestLang.G);

  const ForestNode &Parsed =
      glrParse({Tokens, Arena, GSStack}, id("test"), TestLang);
  EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
            "[  0, end) test := <ambiguous>\n"
            "[  0, end) ├─test := IDENTIFIER\n"
            "[  0, end) │ └─IDENTIFIER := tok[0]\n"
            "[  0, end) └─test := foo\n"
            "[  0, end)   └─foo := IDENTIFIER\n"
            "[  0, end)     └─IDENTIFIER := tok[0]\n");
}

TEST_F(GLRTest, RecoveryEndToEnd) {
  // Simple example of brace-based recovery showing:
  //  - recovered region includes tokens both ahead of and behind the cursor
  //  - multiple possible recovery rules
  //  - recovery from outer scopes is rejected
  build(R"bnf(
    _ := block EOF

    block := { block [recover=Braces] }
    block := { numbers [recover=Braces] }
    numbers := NUMERIC_CONSTANT NUMERIC_CONSTANT
  )bnf");
  TestLang.Table = LRTable::buildSLR(TestLang.G);
  TestLang.RecoveryStrategies.try_emplace(extensionID("Braces"), recoverBraces);
  clang::LangOptions LOptions;
  TokenStream Tokens = cook(lex("{ { 42 ? } }", LOptions), LOptions);
  pairBrackets(Tokens);

  const ForestNode &Parsed =
      glrParse({Tokens, Arena, GSStack}, id("block"), TestLang);
  EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
            "[  0, end) block := { block [recover=Braces] }\n"
            "[  0,   1) ├─{ := tok[0]\n"
            "[  1,   5) ├─block := <ambiguous>\n"
            "[  1,   5) │ ├─block := { block [recover=Braces] }\n"
            "[  1,   2) │ │ ├─{ := tok[1]\n"
            "[  2,   4) │ │ ├─block := <opaque>\n"
            "[  4,   5) │ │ └─} := tok[4]\n"
            "[  1,   5) │ └─block := { numbers [recover=Braces] }\n"
            "[  1,   2) │   ├─{ := tok[1]\n"
            "[  2,   4) │   ├─numbers := <opaque>\n"
            "[  4,   5) │   └─} := tok[4]\n"
            "[  5, end) └─} := tok[5]\n");
}

TEST_F(GLRTest, RecoverTerminal) {
  build(R"bnf(
    _ := stmt EOF

    stmt := IDENTIFIER ; [recover=Skip]
  )bnf");
  TestLang.Table = LRTable::buildSLR(TestLang.G);
  TestLang.RecoveryStrategies.try_emplace(
      extensionID("Skip"),
      [](Token::Index Start, const TokenStream &) { return Start; });
  clang::LangOptions LOptions;
  TokenStream Tokens = cook(lex("foo", LOptions), LOptions);

  const ForestNode &Parsed =
      glrParse({Tokens, Arena, GSStack}, id("stmt"), TestLang);
  EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
            "[  0, end) stmt := IDENTIFIER ; [recover=Skip]\n"
            "[  0,   1) ├─IDENTIFIER := tok[0]\n"
            "[  1, end) └─; := <opaque>\n");
}

TEST_F(GLRTest, RecoverUnrestrictedReduce) {
  // Here, ! is not in any rule and therefore not in the follow set of `word`.
  // We would not normally reduce `word := IDENTIFIER`, but do so for recovery.

  build(R"bnf(
    _ := sentence EOF

    word := IDENTIFIER
    sentence := word word [recover=AcceptAnyTokenInstead]
  )bnf");

  clang::LangOptions LOptions;
  const TokenStream &Tokens = cook(lex("id !", LOptions), LOptions);
  TestLang.Table = LRTable::buildSLR(TestLang.G);
  TestLang.RecoveryStrategies.try_emplace(
      extensionID("AcceptAnyTokenInstead"),
      [](Token::Index Start, const TokenStream &Stream) { return Start + 1; });

  const ForestNode &Parsed =
      glrParse({Tokens, Arena, GSStack}, id("sentence"), TestLang);
  EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
            "[  0, end) sentence := word word [recover=AcceptAnyTokenInstead]\n"
            "[  0,   1) ├─word := IDENTIFIER\n"
            "[  0,   1) │ └─IDENTIFIER := tok[0]\n"
            "[  1, end) └─word := <opaque>\n");
}

TEST_F(GLRTest, RecoveryFromStartOfInput) {
  build(R"bnf(
    _ := start [recover=Fallback] EOF

    start := IDENTIFIER
  )bnf");
  TestLang.Table = LRTable::buildSLR(TestLang.G);
  bool fallback_recovered = false;
  auto fallback = [&](Token::Index Start, const TokenStream & Code) {
    fallback_recovered = true;
    return Code.tokens().size();
  };
  TestLang.RecoveryStrategies.try_emplace(
      extensionID("Fallback"),
      fallback);
  clang::LangOptions LOptions;
  TokenStream Tokens = cook(lex("?", LOptions), LOptions);

  const ForestNode &Parsed =
      glrParse({Tokens, Arena, GSStack}, id("start"), TestLang);
  EXPECT_TRUE(fallback_recovered);
  EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
            "[  0, end) start := <opaque>\n");
}

TEST_F(GLRTest, RepeatedRecovery) {
  // We require multiple steps of recovery at eof and then a reduction in order
  // to successfully parse.
  build(R"bnf(
    _ := function EOF
    # FIXME: this forces EOF to be in follow(signature).
    # Remove it once we use unconstrained reduction for recovery.
    _ := signature EOF

    function := signature body [recover=Skip]
    signature := IDENTIFIER params [recover=Skip]
    params := ( )
    body := { }
  )bnf");
  TestLang.Table = LRTable::buildSLR(TestLang.G);
  TestLang.RecoveryStrategies.try_emplace(
      extensionID("Skip"),
      [](Token::Index Start, const TokenStream &) { return Start; });
  clang::LangOptions LOptions;
  TokenStream Tokens = cook(lex("main", LOptions), LOptions);

  const ForestNode &Parsed =
      glrParse({Tokens, Arena, GSStack}, id("function"), TestLang);
  EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
            "[  0, end) function := signature body [recover=Skip]\n"
            "[  0,   1) ├─signature := IDENTIFIER params [recover=Skip]\n"
            "[  0,   1) │ ├─IDENTIFIER := tok[0]\n"
            "[  1,   1) │ └─params := <opaque>\n"
            "[  1, end) └─body := <opaque>\n");
}

TEST_F(GLRTest, NoExplicitAccept) {
  build(R"bnf(
    _ := test EOF

    test := IDENTIFIER test
    test := IDENTIFIER
  )bnf");
  clang::LangOptions LOptions;
  // Given the following input, and the grammar above, we perform two reductions
  // of the nonterminal `test` when the next token is `eof`, verify that the
  // parser stops at the right state.
  const TokenStream &Tokens = cook(lex("id id", LOptions), LOptions);
  TestLang.Table = LRTable::buildSLR(TestLang.G);

  const ForestNode &Parsed =
      glrParse({Tokens, Arena, GSStack}, id("test"), TestLang);
  EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
            "[  0, end) test := IDENTIFIER test\n"
            "[  0,   1) ├─IDENTIFIER := tok[0]\n"
            "[  1, end) └─test := IDENTIFIER\n"
            "[  1, end)   └─IDENTIFIER := tok[1]\n");
}

TEST_F(GLRTest, GuardExtension) {
  build(R"bnf(
    _ := start EOF

    start := IDENTIFIER [guard]
  )bnf");
  TestLang.Guards.try_emplace(
      ruleFor("start"), [&](const GuardParams &P) {
        assert(P.RHS.size() == 1 &&
               P.RHS.front()->symbol() ==
                   tokenSymbol(clang::tok::identifier));
        return P.Tokens.tokens()[P.RHS.front()->startTokenIndex()]
                   .text() == "test";
      });
  clang::LangOptions LOptions;
  TestLang.Table = LRTable::buildSLR(TestLang.G);

  std::string Input = "test";
  const TokenStream &Succeeded = cook(lex(Input, LOptions), LOptions);
  EXPECT_EQ(glrParse({Succeeded, Arena, GSStack}, id("start"), TestLang)
                .dumpRecursive(TestLang.G),
            "[  0, end) start := IDENTIFIER [guard]\n"
            "[  0, end) └─IDENTIFIER := tok[0]\n");

  Input = "notest";
  const TokenStream &Failed = cook(lex(Input, LOptions), LOptions);
  EXPECT_EQ(glrParse({Failed, Arena, GSStack}, id("start"), TestLang)
                .dumpRecursive(TestLang.G),
            "[  0, end) start := <opaque>\n");
}

TEST(GSSTest, GC) {
  //      ┌-A-┬-AB
  //      ├-B-┘
  // Root-+-C
  //      ├-D
  //      └-E
  GSS GSStack;
  auto *Root = GSStack.addNode(0, nullptr, {});
  auto *A = GSStack.addNode(0, nullptr, {Root});
  auto *B = GSStack.addNode(0, nullptr, {Root});
  auto *C = GSStack.addNode(0, nullptr, {Root});
  auto *D = GSStack.addNode(0, nullptr, {Root});
  auto *AB = GSStack.addNode(0, nullptr, {A, B});

  EXPECT_EQ(1u, GSStack.gc({AB, C})) << "D is destroyed";
  EXPECT_EQ(0u, GSStack.gc({AB, C})) << "D is already gone";
  auto *E = GSStack.addNode(0, nullptr, {Root});
  EXPECT_EQ(D, E) << "Storage of GCed node D is reused for E";
  EXPECT_EQ(3u, GSStack.gc({A, E})) << "Destroys B, AB, C";
  EXPECT_EQ(1u, GSStack.gc({E})) << "Destroys A";
}

} // namespace
} // namespace pseudo
} // namespace clang