[pseudo] Add recovery for declarations

[hokein]

Summary

• declaration recovery strategy: search for likely declaration boundaries
• change decl-sequence to right-recursive to simplify this
• also use for class members (already right-recursive)
• refactor recovery strategy to use struct parameter and expose cursor position

[sammccall]

This may well need refinement & more testing, interested in initial thoughts

[hokein]

clang-tools-extra/pseudo/lib/cxx/CXX.cpp

426

I think this excludes the parameter-declaration (from the grammar spec, it is a different nonterminal).

426

The logic of implementations looks very solid. I think it would be good to have some unittests for it.

441

if I read the code correctly, the following case should work like

void foo() {}

LLVM_DISCARD int bar() {} // this is an opaque `declaration` node?

void foo2() {} // it won't work if we change void -> Foo.

450

the list looks reasonable -- I think we can lookup the Follow(declaration) set to find more.

460

maybe consider tok::identifier (if the identifier is a type specifier, it is a good indicator of a declaration starting) as well? And yeah, we're less certain about it, but since we use the indentation information, I guess it might probably work well?

511

I think we miss to check the return index >= Cursor here.

clang-tools-extra/pseudo/lib/cxx/cxx.bnf

308

Just want to spell out, this causes a performance hit :(
(a pure change of this has a ~6% slowdown, 7.17 MB/s -> 6.7MB/s on SemaCodeComplete.cpp).

left-cursive grammar is more friendly to LR-like parsers, because the parser can do the reduction earlier (after a parsed a declaration, we can perform a declaration-seq reduce); while right-cursive grammar, the reduction starts from the last declaration (this means our GSS is more deeper).

change decl-sequence to right-recursive to simplify this

I remembered we discussed this bit before, but I don't really remember the details now :(

clang-tools-extra/pseudo/test/cxx/recovery-declarations.cpp

7

nit: add some tests to cover the initializer, e.g.

auto lambda = [] xxxx () xxx {};

[hokein]

clang-tools-extra/pseudo/lib/cxx/CXX.cpp

492

P.Tokens.tokens()[P.Begin].next() doesn't seem like correct, we should start with P.Tokens.tokens()[P.Begin], otherwise we will ignore the first token,

example:

namespace XXXX {
}
foo foo;

501

we should return index() +1

506

the same, +1.

[hokein]

I'm going to pick this up.

[hokein]

• rebase, fixed a few conflicts
• address comments
• fix some bugs
• restructure the code, moving the implementation to a separate file
• add unittests for recoveryNextDeclaration
• keep the left-recursive declaration-seq grammar rule to void performance regression

[hokein]

I think the current version should be good to review, some bits need to take care of:

• left-recursive vs right-recursive of declaration-seq rule, see my other comments about it. Currently I keep it as-is to avoid the performance regression on large files (I still don't see your point how right-recursive can simplify the error recovery, it seems to me either can work at least for this case)
• recoveryNextDeclaration will consume at least 1 token (the return token index > Cursor) to avoid the risk of running in an infinite loop
• I keep the original implementation as-is (except fixing some bugs), but IMO T->Indent == OrigIndent && LikelyStartsDeclaration(T->Kind) is too strict (see my FIXME testcases), and we should probably include the IDENTIFIER (I believe it is a common case), LikelyStartsDeclaration(T->Kind) || (T->Kind = IDENTIFIER && T->Indent == OrigIndent) might be better.

clang-tools-extra/pseudo/lib/cxx/CXX.cpp

450

added more: kw_friend, kw_inline, kw_explicit, kw_virtual.

clang-tools-extra/pseudo/lib/cxx/cxx.bnf

308

Got more data, it does hurt the performance on large files:

SemaExpr.cpp: 9.54MB/s -> 7.98MB/s
SemaDeclCXX.cpp: 10.16MB/s -> 9.25MB/s

small/medium files doesn't seem to be affected (hypothesis: these files has less declarations than large files, thus being less affected by the right-recursive declaration-seq grammar rule)

Hover.cpp: 8MB/s -> 7.92MB/s
ASTSignals.cpp: 12.34M/s -> 12.29MB/s

[hokein]

Fix a bug caused by my change, and add test.

clang-tools-extra/pseudo/include/clang-pseudo/Language.h

 //
 // The GLR parser will use the guard to determine whether a rule reduction will
 // be conducted. For example, e.g. a guard may allow the rule
 // `virt-specifier := IDENTIFIER` only if the identifier's text is 'override`.
 //
 // Return true if the guard is satisfied.
 using RuleGuard = llvm::function_ref<bool(const GuardParams &)>;
 
+struct RecoveryParams {
+  // The position in the stream where the node being recovered will start.
+  Token::Index Begin;
+  // The position in the stream where the parse failed.
+  // Begin <= Cursor <= End (for a valid recovery).
+  Token::Index Cursor;
+  const TokenStream &Tokens;
+};
 // A recovery strategy determines a region of code to skip when parsing fails.
 //
 // For example, given `class-def := CLASS IDENT { body [recover=Brackets] }`,
 // if parsing fails while attempting to parse `body`, we may skip up to the
 // matching `}` and assume everything between was a `body`.
 //
 // The provided index is the token where the skipped region begins.
 // Returns the (excluded) end of the range, or Token::Invalid for no recovery.
 using RecoveryStrategy =
-    llvm::function_ref<Token::Index(Token::Index Start, const TokenStream &)>;
+    llvm::function_ref<Token::Index(const RecoveryParams &)>;
 
 // Specify a language that can be parsed by the pseduoparser.
 struct Language {
   Grammar G;
   LRTable Table;
 
   // Binding extension ids to corresponding implementations.
   llvm::DenseMap<RuleID, RuleGuard> Guards;

clang-tools-extra/pseudo/include/clang-pseudo/cxx/Recovery.h

+//===--- Recovery.h - C++ specific recovery heuristics ------*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef CLANG_PSEUDO_CXX_RECOVERY_H
+#define CLANG_PSEUDO_CXX_RECOVERY_H
+
+#include "clang-pseudo/Language.h"
+
+namespace clang::pseudo::cxx {
+
+// Heuristically finds the end of range of a declaration if parsing fails while
+// attempting to parse a declaration.
+//
+// Returns an *excluded* end of token range. Given the broken code below,
+//
+//    int a = ? garbage ?;
+//    double;
+//
+// We failed to parse the first declaration, the function returns the index of
+// `double` token. We skip up to the first `;` token and assume tokens in
+// [P.Begin, recoverNextDeclaration(P)) range was a declaration.
+//
+// Returns Token::Invalid if we can't find an end point.
+Token::Index recoverNextDeclaration(const RecoveryParams &P);
+
+} // namespace clang::pseudo::cxx
+
+#endif // CLANG_PSEUDO_CXX_RECOVERY_H

clang-tools-extra/pseudo/lib/GLR.cpp

 
 #define DEBUG_TYPE "GLR.cpp"
 
 namespace clang {
 namespace pseudo {
 namespace {
 
 Token::Index findRecoveryEndpoint(ExtensionID Strategy, Token::Index Begin,
+                                  Token::Index Cursor,
                                   const TokenStream &Tokens,
                                   const Language &Lang) {
   assert(Strategy != 0);
   if (auto S = Lang.RecoveryStrategies.lookup(Strategy))
-    return S(Begin, Tokens);
+    return S({Begin, Cursor, Tokens});
   return Token::Invalid;
 }
 
 } // namespace
 
 void glrRecover(llvm::ArrayRef<const GSS::Node *> OldHeads,
                 unsigned &TokenIndex, const ParseParams &Params,
                 const Language &Lang,
void glrRecover(llvm::ArrayRef<const GSS::Node *> OldHeads,
   std::vector<const PlaceholderRecovery *> BestOptions;
   for (const PlaceholderRecovery &Option : Options) {
     // If this starts further left than options we've already found, then
     // we'll never find anything better. Skip computing End for the rest.
     if (RecoveryRange && Option.Position < RecoveryRange->Begin)
       break;
 
     auto End = findRecoveryEndpoint(Option.Strategy, Option.Position,
-                                    Params.Code, Lang);
+                                    TokenIndex, Params.Code, Lang);
     // Recovery may not take the parse backwards.
     if (End == Token::Invalid || End < TokenIndex)
       continue;
     if (RecoveryRange) {
       // If this is worse than our previous options, ignore it.
       if (RecoveryRange->End < End)
         continue;
       // If this is an improvement over our previous options, then drop them.

clang-tools-extra/pseudo/lib/cxx/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_clang_library(clangPseudoCXX
   CXX.cpp
+  Recovery.cpp
 
   DEPENDS
   cxx_gen
 
   LINK_LIBS
   clangBasic
   clangPseudo
   clangPseudoGrammar
   )

clang-tools-extra/pseudo/lib/cxx/CXX.cpp

 //===--- CXX.cpp - Define public interfaces for C++ grammar ---------------===//
 //
 // 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/cxx/CXX.h"
 #include "clang-pseudo/Forest.h"
 #include "clang-pseudo/Language.h"
+#include "clang-pseudo/cxx/Recovery.h"
 #include "clang-pseudo/grammar/Grammar.h"
 #include "clang-pseudo/grammar/LRTable.h"
 #include "clang/Basic/CharInfo.h"
 #include "clang/Basic/TokenKinds.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/Debug.h"
 #include <utility>
 #define DEBUG_TYPE "CXX.cpp"
return {
        TOKEN_GUARD(numeric_constant, numKind(Tok) == Integer)},
       {rule::floating_point_literal::NUMERIC_CONSTANT,
        TOKEN_GUARD(numeric_constant, numKind(Tok) == Floating)},
   };
 #undef TOKEN_GUARD
 #undef SYMBOL_GUARD
 }
 
-Token::Index recoverBrackets(Token::Index Begin, const TokenStream &Tokens) {
-  assert(Begin > 0);
-  const Token &Left = Tokens.tokens()[Begin - 1];
+Token::Index recoverBrackets(const RecoveryParams &P) {
+  assert(P.Begin > 0);
+  const Token &Left = P.Tokens.tokens()[P.Begin - 1];
   assert(Left.Kind == tok::l_brace || Left.Kind == tok::l_paren ||
          Left.Kind == tok::l_square);
   if (const Token *Right = Left.pair()) {
-    assert(Tokens.index(*Right) > Begin - 1);
-    return Tokens.index(*Right);
+    assert(P.Tokens.index(*Right) > P.Begin - 1);
+    return P.Tokens.index(*Right);
   }
   return Token::Invalid;
 }
 
 llvm::DenseMap<ExtensionID, RecoveryStrategy> buildRecoveryStrategies() {
   return {
       {Extension::Brackets, recoverBrackets},
+      {Extension::NextDeclaration, recoverNextDeclaration},
   };
 }
 
 } // namespace
 
 const Language &getLanguage() {
   static const auto &CXXLanguage = []() -> const Language & {
     std::vector<std::string> Diags;
     auto G = Grammar::parseBNF(CXXBNF, Diags);
     assert(Diags.empty());
     LRTable Table = LRTable::buildSLR(G);
     const Language *PL = new Language{
         std::move(G),
         std::move(Table),
         buildGuards(),
         buildRecoveryStrategies(),
     };
     return *PL;
   }();
   return CXXLanguage;
 }
 
 } // namespace cxx
 } // namespace pseudo
 } // namespace clang

clang-tools-extra/pseudo/lib/cxx/Recovery.cpp

+//===--- Recovery.cpp - ---------------------------------------------------===//
+//
+// 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/cxx/Recovery.h"
+#include "clang-pseudo/Language.h"
+#include "clang/Basic/TokenKinds.h"
+
+namespace clang::pseudo::cxx {
+
+Token::Index recoverNextDeclaration(const RecoveryParams &P) {
+  if (P.Begin == P.Tokens.tokens().size())
+    return Token::Invalid;
+  // Declarations that don't end in semicolons:
+  //   function-definition
+  //   EXPORT {...}
+  //   EXTERN string-literal {...}
+  //   INLINE_opt NAMESPACE IDENTIFIER {...}
+  //   INLINE_opt NAMESPACE {...}
+  //   NAMESPACE enclosing-namespace-specifier :: INLINE_opt IDENTIFIER {...}
+  // Functions are hard to do anything about:
+  //  - if the declarator is good and the braces are present, parsing succeeds
+  //  - if the declarator is bad, it's hard to know it's a function
+  //  - if the braces are missing, we don't know where to recover
+  // So we only try to detect the others.
+  bool AcceptBraces = false;
+  auto ConsiderForBraces = [&](tok::TokenKind K) {
+    if (K == tok::kw_export || K == tok::kw_extern || K == tok::kw_namespace)
+      AcceptBraces = true;
+  };
+
+  // Some tokens are pretty good indicators of a declaration starting, when
+  // they appear at the beginning of a line.
+  auto LikelyStartsDeclaration = [&](tok::TokenKind K) -> bool {
+    switch (K) {
+    // Things you might be declaring.
+    case tok::kw_template:
+    case tok::kw_using:
+    case tok::kw_namespace:
+    case tok::kw_typedef:
+    case tok::kw_class:
+    case tok::kw_struct:
+    case tok::kw_union:
+    case tok::kw_friend:
+    // Types & other decl-specifiers
+    // FIXME: consider IDENTIFIER
+    case tok::kw_void:
+    case tok::kw_auto:
+    case tok::kw_int:
+    case tok::kw_char:
+    case tok::kw_float:
+    case tok::kw_double:
+    case tok::kw_long:
+    case tok::kw_signed:
+    case tok::kw_unsigned:
+    case tok::kw_const:
+    case tok::kw_volatile:
+    case tok::kw_static:
+    case tok::kw_extern:
+    case tok::kw_inline:
+    case tok::kw_explicit:
+    case tok::kw_virtual:
+    // Modules
+    case tok::kw_import:
+    case tok::kw_export:
+    // Class protection
+    case tok::kw_public:
+    case tok::kw_private:
+    case tok::kw_protected:
+      return true;
+    default:
+      return false;
+    }
+  };
+
+  // The indentation level where the declaration started hints at where a new
+  // sibling declaration might start.
+  unsigned OrigIndent = P.Tokens.tokens()[P.Begin].Indent;
+
+  // Walk over tokens at the appropriate bracket nesting level.
+  for (const Token *T = &P.Tokens.tokens()[P.Begin]; T->Kind != tok::eof;
+       T = &T->next()) {
+    auto TIndex = P.Tokens.index(*T);
+    // Handle (paired) brackets.
+    if (const Token *PairedT = T->pair()) {
+      // Closing bracket not paired within the recovery range.
+      auto PairedTIndex = P.Tokens.index(*PairedT);
+      if (PairedT < T) {
+        assert(PairedTIndex < P.Begin && "Why didn't we skip this one?");
+        assert(TIndex >= P.Cursor &&
+               "How did we parse an unmatched closing bracket?!");
+        return TIndex + 1;
+      }
+      // Opening bracket: is this a semicolonless statement?
+      if (T->Kind == tok::l_brace && AcceptBraces && PairedTIndex >= P.Cursor)
+        return PairedTIndex + 1;
+      // Skip over opening/closing bracket pair.
+      T = PairedT;
+      continue;
+    }
+    ConsiderForBraces(T->Kind);
+
+    // Semicolons terminate statements.
+    if (T->Kind == tok::semi && TIndex >= P.Cursor)
+      return TIndex + 1;
+
+    // Stop if it looks like a new declaration is starting on the next line.
+    if (TIndex > P.Cursor // ensure cursor is moving forward after recovery
+        && (TIndex > 0 && T->Line != T->prev().Line) // start on the next line.
+        && T->Indent == OrigIndent && LikelyStartsDeclaration(T->Kind))
+      return TIndex;
+  }
+  // If we reached EOF, then assume the declaration runs right to EOF.
+  return P.Tokens.tokens().size();
+}
+
+} // namespace clang::pseudo::cxx

clang-tools-extra/pseudo/lib/cxx/cxx.bnf

 jump-statement := CONTINUE ;
 jump-statement := RETURN expr-or-braced-init-list_opt ;
 jump-statement := coroutine-return-statement
 jump-statement := GOTO IDENTIFIER ;
 coroutine-return-statement := CO_RETURN expr-or-braced-init-list_opt ;
 declaration-statement := block-declaration
 
 # gram.dcl
-declaration-seq := declaration
-declaration-seq := declaration-seq declaration
+declaration-seq := declaration [recover=NextDeclaration]
+declaration-seq := declaration-seq declaration [recover=NextDeclaration]
 declaration := block-declaration
 declaration := nodeclspec-function-declaration
 declaration := function-definition
 declaration := template-declaration
 declaration := deduction-guide
 declaration := explicit-instantiation
 declaration := explicit-specialization
 declaration := export-declaration

 class-specifier := class-head { member-specification_opt [recover=Brackets] }
 class-head := class-key class-head-name class-virt-specifier_opt base-clause_opt
 class-head := class-key base-clause_opt
 class-head-name := nested-name-specifier_opt type-name
 class-virt-specifier := contextual-final
 class-key := CLASS
 class-key := STRUCT
 class-key := UNION
-member-specification := member-declaration member-specification_opt
+member-specification := member-declaration [recover=NextDeclaration] member-specification_opt
 member-specification := access-specifier : member-specification_opt
 member-declaration := decl-specifier-seq member-declarator-list_opt ;
 member-declaration := member-declarator-list ;
 member-declaration := function-definition
 member-declaration := using-declaration
 member-declaration := using-enum-declaration
 member-declaration := static_assert-declaration
 member-declaration := template-declaration

clang-tools-extra/pseudo/test/cxx/recovery-declarations.cpp

+// RUN: clang-pseudo -grammar=cxx -source=%s --print-forest | FileCheck %s
+
+this is not a valid declaration;
+// CHECK: declaration := <opaque>
+
+int x[0];
+// CHECK:      simple-declaration := decl-specifier-seq init-declarator-list ;
+// CHECK-NEXT: ├─decl-specifier-seq~INT := tok[7]
+// CHECK-NEXT: ├─init-declarator-list~noptr-declarator := noptr-declarator [ constant-expression ]
+
+also_not_ok ??? @@@ (;
+// CHECK: declaration := <opaque>
+
+class Y{};
+// CHECK:      simple-declaration := decl-specifier-seq ;
+// CHECK-NEXT: ├─decl-specifier-seq~class-specifier := class-head { }
+
+// FIXME: support recovery of incomplete scopes
+// namespace foo {
+
+class class class class function
+// CHECK: declaration := <opaque>

clang-tools-extra/pseudo/unittests/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_custom_target(ClangPseudoUnitTests)
 add_unittest(ClangPseudoUnitTests ClangPseudoTests
   BracketTest.cpp
+  CXXRecoveryTest.cpp
   CXXTest.cpp
   DirectiveTreeTest.cpp
   DisambiguateTest.cpp
   ForestTest.cpp
   GLRTest.cpp
   GrammarTest.cpp
   LRTableTest.cpp
   TokenTest.cpp

clang-tools-extra/pseudo/unittests/CXXRecoveryTest.cpp

+//===--- CXXRecoveryTest.cpp - ----------------------------------*- 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/Bracket.h"
+#include "clang-pseudo/Language.h"
+#include "clang-pseudo/Token.h"
+#include "clang-pseudo/cxx/Recovery.h"
+
+#include "clang/Basic/LangOptions.h"
+#include "llvm/Testing/Support/Annotations.h"
+#include "gtest/gtest.h"
+
+namespace clang::pseudo {
+
+namespace {
+
+std::pair<RecoveryParams, /*Expected End*/ Token::Index>
+extract(const llvm::Annotations &Test) {
+  assert(Test.points().size() == 2 && "Expect two ^s in the test annotations");
+  LangOptions Opts = clang::pseudo::genericLangOpts();
+  std::string Code = Test.code().str();
+  TokenStream Cook = cook(lex(Code, Opts), Opts);
+  pairBrackets(Cook);
+
+  RecoveryParams P{0, Token::Invalid, Cook};
+  auto StartOffset = [&](const Token &T) -> size_t {
+    return T.Data - Code.data();
+  };
+  for (const auto &T : Cook.tokens()) {
+    if (StartOffset(T) == Test.points().front()) {
+      P.Cursor = Cook.index(T);
+      break;
+    }
+  }
+  assert(P.Cursor != Token::Invalid && "no cursor position provided");
+  Token::Index Expect = Token::Invalid;
+  if (Test.points().back() > StartOffset(Cook.tokens().back()))
+    Expect = Cook.tokens().size(); // EOF
+  else {
+    for (const auto &T : Cook.tokens()) {
+      if (StartOffset(T) == Test.points().back()) {
+        Expect = Cook.index(T);
+      }
+    }
+    assert(Expect != Token::Invalid);
+  }
+  return {P, Expect};
+}
+
+TEST(CXXRecoveryTest, Declaration) {
+  // We have 3 different positions in the TokenStream:
+  //   - Begin: where we start to parse the code (always 0 in the test)
+  //   - Cursor: where the parse failed (specified by the first ^)
+  //   - End: expected ends of the range (specified by the second ^)
+  const char *Tests[] = {
+      R"cpp(
+        namespace ^??? { }
+        ^Foo foo;
+      )cpp",
+      R"cpp(
+        auto lambda = [] ^xxx () xxx {} ;
+        ^Foo foo;
+      )cpp",
+      R"cpp(
+        LLVM_DISCARD int ^bar() {}
+        ^int;
+      )cpp",
+      // Recovery should at least consume 1 token.
+      R"cpp(
+        int
+        ^int
+        ^
+      )cpp",
+      // FIXME: we skip too much, Foo is a better end point.
+      R"cpp(
+        LLVM_DISCARD int ^bar() {}
+        Foo foo();
+        ^int;
+      )cpp",
+      R"cpp(
+        void Foo::AcquireLease() ^LOCKS_EXCLUDED(mutex_) {}
+
+        Foo abc();
+        ^
+      )cpp",
+      // FIXME: skipp too much, we should end at private.
+      R"cpp(
+        class Foo {
+        public:
+          void abc() ^ERRROR
+        private:
+          int a;
+        };
+        ^
+      )cpp",
+  };
+  for (const auto *T : Tests) {
+    llvm::Annotations Code(T);
+    const auto &[RP, ExpectedEnd] = extract(Code);
+    EXPECT_EQ(pseudo::cxx::recoverNextDeclaration(RP), ExpectedEnd)
+        << Code.code();
+  }
+}
+} // namespace
+} // namespace clang::pseudo

clang-tools-extra/pseudo/unittests/GLRTest.cpp

 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];
+Token::Index recoverBraces(const RecoveryParams &P) {
+  EXPECT_GT(P.Begin, 0u);
+  const Token &Left = P.Tokens.tokens()[P.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 P.Tokens.index(*Right);
   }
   return Token::Invalid;
 }
 
 class GLRTest : public ::testing::Test {
 public:
   void build(llvm::StringRef GrammarBNF) {
     std::vector<std::string> Diags;
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; });
+      [](const RecoveryParams& P) { return P.Begin; });
   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"
build(R"bnf(
     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 RecoveryParams& P) { return P.Begin + 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) {
+  auto fallback = [&](const RecoveryParams& P) {
     fallback_recovered = true;
-    return Code.tokens().size();
+    return P.Tokens.tokens().size();
   };
   TestLang.RecoveryStrategies.try_emplace(
       extensionID("Fallback"),
       fallback);
   clang::LangOptions LOptions;
   TokenStream Tokens = cook(lex("?", LOptions), LOptions);
 
   const ForestNode &Parsed =
build(R"bnf(
     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; });
+      [](const RecoveryParams& P) { return P.Begin; });
   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"