[pseudo] Define recovery strategy as grammar extension.

[hokein]

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

46

nit: assert Left is a left bracket?

54

btw, it is annoying to write an explicit ExtensionID<=>Extension conversion. To avoid that, what do you think of making the Symbol&Extension as an enum rather than enum class, and we still keep the qualified name usage Extension::Brackets.

[sammccall]

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

54

I don't find it particularly annoying FWIW.
I think I'd rather deal with this (which only appears in these tables, which are regular) than implicit conversion and also polluting the namespace (even if you only *use* Extension::Brackets, cxx::Brackets still exists, ends up in code completion, can conflict with other symbols etc)

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

 //===--- Language.h -------------------------------------------- -*- 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_GRAMMAR_LANGUAGE_H
 #define CLANG_PSEUDO_GRAMMAR_LANGUAGE_H
 
+#include "clang-pseudo/Token.h"
 #include "clang-pseudo/grammar/Grammar.h"
 #include "clang-pseudo/grammar/LRTable.h"
 
 namespace clang {
 namespace pseudo {
 class ForestNode;
 class TokenStream;
 class LRTable;
 
 // A guard restricts when a grammar rule can be used.
 //
 // 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(
     llvm::ArrayRef<const ForestNode *> RHS, const TokenStream &)>;
 
+// 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 &)>;
+
 // Specify a language that can be parsed by the pseduoparser.
 struct Language {
   Grammar G;
   LRTable Table;
 
-  // Binding "guard" extension id to a piece of C++ code.
+  // Binding extension ids to corresponding implementations.
   llvm::DenseMap<ExtensionID, RuleGuard> Guards;
+  llvm::DenseMap<ExtensionID, RecoveryStrategy> RecoveryStrategies;
 
   // FIXME: add clang::LangOptions.
   // FIXME: add default start symbols.
 };
 
 } // namespace pseudo
 } // namespace clang
 
 #endif // CLANG_PSEUDO_GRAMMAR_LANGUAGE_H

clang-tools-extra/pseudo/include/clang-pseudo/grammar/Grammar.h

inline tok::TokenKind symbolToToken(SymbolID SID) {
   assert(isToken(SID));
   SID &= ~TokenFlag;
   assert(SID < NumTerminals);
   return static_cast<tok::TokenKind>(SID);
 }
 inline constexpr SymbolID tokenSymbol(tok::TokenKind TK) {
   return TokenFlag | static_cast<SymbolID>(TK);
 }
-// Error recovery strategies.
-// FIXME: these should be provided as extensions instead.
-enum class RecoveryStrategy : uint8_t { None, Braces };
 
 // An extension is a piece of native code specific to a grammar that modifies
 // the behavior of annotated rules. One ExtensionID is assigned for each unique
 // attribute value (all attributes share a namespace).
 using ExtensionID = uint16_t;
 
 // A RuleID uniquely identifies a production rule in a grammar.
 // It is an index into a table of rules.
struct Rule {
   ExtensionID Guard = 0;
 
   // Specifies the index within Sequence eligible for error recovery.
   // Given stmt := { stmt-seq_opt }, if we fail to parse the stmt-seq then we
   // should recover by finding the matching brace, and forcing stmt-seq to match
   // everything between braces.
   // For now, only a single strategy at a single point is possible.
   uint8_t RecoveryIndex = -1;
-  RecoveryStrategy Recovery = RecoveryStrategy::None;
+  ExtensionID Recovery = 0;
 
   llvm::ArrayRef<SymbolID> seq() const {
     return llvm::ArrayRef<SymbolID>(Sequence, Size);
   }
   friend bool operator==(const Rule &L, const Rule &R) {
     return L.Target == R.Target && L.seq() == R.seq() && L.Guard == R.Guard;
   }
 };

clang-tools-extra/pseudo/include/clang-pseudo/grammar/LRGraph.h

public:
 
   // A possible error recovery: choose to match some tokens against a symbol.
   //
   // e.g. a state that contains
   //   stmt := { . stmt-seq [recover=braces] }
   // has a Recovery { Src = S, Strategy=braces, Result=stmt-seq }.
   struct Recovery {
     StateID Src; // The state we are in when encountering the error.
-    RecoveryStrategy Strategy; // Heuristic choosing the tokens to match.
+    ExtensionID Strategy;      // Heuristic choosing the tokens to match.
     SymbolID Result;           // The symbol that is produced.
   };
 
   llvm::ArrayRef<State> states() const { return States; }
   llvm::ArrayRef<Edge> edges() const { return Edges; }
   llvm::ArrayRef<Recovery> recoveries() const { return Recoveries; }
   llvm::ArrayRef<std::pair<SymbolID, StateID>> startStates() const {
     return StartStates;

clang-tools-extra/pseudo/include/clang-pseudo/grammar/LRTable.h

 // after parsing completes: is the state goto(StartState, StartSymbol)?
 class LRTable {
 public:
   // StateID is only 13 bits wide.
   using StateID = uint16_t;
   static constexpr unsigned StateBits = 13;
 
   struct Recovery {
-    RecoveryStrategy Strategy;
+    ExtensionID Strategy;
     SymbolID Result;
   };
 
   // Returns the state after we reduce a nonterminal.
   // Expected to be called by LR parsers.
   // If the nonterminal is invalid here, returns None.
   llvm::Optional<StateID> getGoToState(StateID State,
                                        SymbolID Nonterminal) const {

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

 #include <queue>
 
 #define DEBUG_TYPE "GLR.cpp"
 
 namespace clang {
 namespace pseudo {
 namespace {
 
-Token::Index findRecoveryEndpoint(RecoveryStrategy Strategy,
-                                  const GSS::Node *RecoveryNode,
-                                  const TokenStream &Tokens) {
-  assert(Strategy == RecoveryStrategy::Braces);
-  const ForestNode *LBrace = RecoveryNode->Payload;
-  assert(LBrace->kind() == ForestNode::Terminal &&
-         LBrace->symbol() == tokenSymbol(tok::l_brace));
-  if (const Token *RBrace = Tokens.tokens()[LBrace->startTokenIndex()].pair())
-    return Tokens.index(*RBrace);
+Token::Index findRecoveryEndpoint(ExtensionID Strategy, Token::Index Begin,
+                                  const TokenStream &Tokens,
+                                  const Language &Lang) {
+  assert(Strategy != 0);
+  assert(Begin > 0);
+  if (auto S = Lang.RecoveryStrategies.lookup(Strategy))
+    return S(Begin, Tokens);
   return Token::Invalid;
 }
 
 } // namespace
 
 void glrRecover(llvm::ArrayRef<const GSS::Node *> OldHeads,
                 unsigned &TokenIndex, const ParseParams &Params,
                 const Language &Lang,
                 std::vector<const GSS::Node *> &NewHeads) {
   LLVM_DEBUG(llvm::dbgs() << "Recovery at token " << TokenIndex << "...\n");
   // Describes a possibility to recover by forcibly interpreting a range of
   // tokens around the cursor as a nonterminal that we expected to see.
   struct PlaceholderRecovery {
     // The token prior to the nonterminal which is being recovered.
     // This starts of the region we're skipping, so higher Position is better.
     Token::Index Position;
     // The nonterminal which will be created in order to recover.
     SymbolID Symbol;
     // The heuristic used to choose the bounds of the nonterminal to recover.
-    RecoveryStrategy Strategy;
+    ExtensionID Strategy;
 
     // The GSS head where we are expecting the recovered nonterminal.
     const GSS::Node *RecoveryNode;
     // Payload of nodes on the way back from the OldHead to the recovery node.
     // These represent the partial parse that is being discarded.
     // They should become the children of the opaque recovery node.
     // FIXME: internal structure of opaque nodes is not implemented.
     //
void glrRecover(llvm::ArrayRef<const GSS::Node *> OldHeads,
   llvm::Optional<Token::Range> RecoveryRange;
   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.RecoveryNode, Params.Code);
+    auto End = findRecoveryEndpoint(Option.Strategy, Option.Position,
+                                    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/cli/CLI.cpp

if (std::error_code EC = GrammarText.getError()) {
                    << "': " << EC.message() << "\n";
       std::exit(1);
     }
     std::vector<std::string> Diags;
     auto G = Grammar::parseBNF(GrammarText->get()->getBuffer(), Diags);
     for (const auto &Diag : Diags)
       llvm::errs() << Diag << "\n";
     auto Table = LRTable::buildSLR(G);
-    return new Language{std::move(G), std::move(Table),
-                        llvm::DenseMap<ExtensionID, RuleGuard>()};
+    return new Language{
+        std::move(G),
+        std::move(Table),
+        llvm::DenseMap<ExtensionID, RuleGuard>(),
+        llvm::DenseMap<ExtensionID, RecoveryStrategy>(),
+    };
   }();
   return *Lang;
 }
 
 } // namespace pseudo
 } // namespace clang

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

 bool guardFinal(llvm::ArrayRef<const ForestNode *> RHS,
                 const TokenStream &Tokens) {
   assert(RHS.size() == 1 &&
          RHS.front()->symbol() == tokenSymbol(clang::tok::identifier));
   return Tokens.tokens()[RHS.front()->startTokenIndex()].text() == "final";
 }
 
 llvm::DenseMap<ExtensionID, RuleGuard> buildGuards() {
-  return llvm::DenseMap<ExtensionID, RuleGuard>(
-      {{(ExtensionID)Extension::Override, guardOverride},
-       {(ExtensionID)Extension::Final, guardFinal}});
+  return {
+      {(ExtensionID)Extension::Override, guardOverride},
+      {(ExtensionID)Extension::Final, guardFinal},
+  };
+}
+
+Token::Index recoverBrackets(Token::Index Begin, const TokenStream &Tokens) {
+  assert(Begin > 0);
+  const Token &Left = Tokens.tokens()[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);
+    return Tokens.index(*Right);
+  }
+  return Token::Invalid;
+}
+
+llvm::DenseMap<ExtensionID, RecoveryStrategy> buildRecoveryStrategies() {
+  return {
+      {(ExtensionID)Extension::Brackets, recoverBrackets},
+  };
 }
 
 } // 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()};
+    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/cxx.bnf

 init-statement := expression-statement
 init-statement := simple-declaration
 condition := expression
 condition := decl-specifier-seq declarator brace-or-equal-initializer
 labeled-statement := IDENTIFIER : statement
 labeled-statement := CASE constant-expression : statement
 labeled-statement := DEFAULT : statement
 expression-statement := expression_opt ;
-compound-statement := { statement-seq_opt }
+compound-statement := { statement-seq_opt [recover=Brackets] }
 statement-seq := statement
 statement-seq := statement-seq statement
 selection-statement := IF CONSTEXPR_opt ( init-statement_opt condition ) statement
 selection-statement := IF CONSTEXPR_opt ( init-statement_opt condition ) statement ELSE statement
 selection-statement := SWITCH ( init-statement_opt condition ) statement
 iteration-statement := WHILE ( condition ) statement
 iteration-statement := DO statement WHILE ( expression ) ;
 iteration-statement := FOR ( init-statement condition_opt ; expression_opt ) statement

 initializer := brace-or-equal-initializer
 initializer := ( expression-list )
 brace-or-equal-initializer := = initializer-clause
 brace-or-equal-initializer := braced-init-list
 initializer-clause := assignment-expression
 initializer-clause := braced-init-list
 #! Allow mixed designated/non-designated init-list.
 # This is standard C, and accepted by clang and others as an extension.
-braced-init-list := { initializer-list ,_opt }
+# FIXME: Decouple recovery from is-there-a-trailing-comma!
+braced-init-list := { initializer-list [recover=Brackets] }
+braced-init-list := { initializer-list , }
 braced-init-list := { }
 initializer-list := initializer-list-item
 initializer-list := initializer-list , initializer-list-item
 initializer-list-item := initializer-clause ..._opt
 initializer-list-item := designator brace-or-equal-initializer ..._opt
 designator := . IDENTIFIER
 #! Array designators are legal in C, and a common extension in C++.
 designator := [ expression ]

 module-import-declaration := import-keyword module-name
 module-import-declaration := import-keyword module-partition
 # FIXME: we don't have header-name in the grammar. Handle these in PP?
 # module-import-declaration := import-keyword header-name
 global-module-fragment := module-keyword ; declaration-seq_opt
 private-module-fragment := module-keyword : PRIVATE ; declaration-seq_opt
 
 # gram.class
-class-specifier := class-head { member-specification_opt }
+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 class-name
 class-virt-specifier := contextual-final
 class-key := CLASS
 class-key := STRUCT
 class-key := UNION
 member-specification := member-declaration member-specification_opt

clang-tools-extra/pseudo/lib/grammar/Grammar.cpp

 std::string Grammar::dumpRule(RuleID RID) const {
   std::string Result;
   llvm::raw_string_ostream OS(Result);
   const Rule &R = T->Rules[RID];
   OS << symbolName(R.Target) << " :=";
   for (unsigned I = 0; I < R.Size; ++I) {
     OS << " " << symbolName(R.Sequence[I]);
     if (R.RecoveryIndex == I)
-      OS << " [recover=" << static_cast<unsigned>(R.Recovery) << "]";
+      OS << " [recover=" << T->AttributeValues[R.Recovery] << "]";
   }
   if (R.Guard)
     OS << " [guard=" << T->AttributeValues[R.Guard] << "]";
   return Result;
 }
 
 std::string Grammar::dumpRules(SymbolID SID) const {
   assert(isNonterminal(SID));

clang-tools-extra/pseudo/lib/grammar/GrammarBNF.cpp

for (const auto &Spec : Specs) {
       for (const RuleSpec::Element &Elt : Spec.Sequence)
         Symbols.push_back(Lookup(Elt.Symbol));
       T->Rules.push_back(Rule(Lookup(Spec.Target), Symbols));
       applyAttributes(Spec, *T, T->Rules.back());
     }
 
     assert(T->Rules.size() < (1 << RuleBits) &&
            "Too many rules to fit in RuleID bits!");
-    // Wherever RHS contains { foo }, mark foo for brace-recovery.
-    // FIXME: this should be grammar annotations instead.
-    for (auto &Rule : T->Rules) {
-      for (unsigned I = 2; I < Rule.Size; ++I)
-        if (Rule.Sequence[I] == tokenSymbol(tok::r_brace) &&
-            Rule.Sequence[I - 2] == tokenSymbol(tok::l_brace) &&
-            !isToken(Rule.Sequence[I - 1])) {
-          Rule.Recovery = RecoveryStrategy::Braces;
-          Rule.RecoveryIndex = I - 1;
-        }
-    }
     const auto &SymbolOrder = getTopologicalOrder(T.get());
     llvm::stable_sort(
         T->Rules, [&SymbolOrder](const Rule &Left, const Rule &Right) {
           // Sorted by the topological order of the nonterminal Target.
           return SymbolOrder[Left.Target] < SymbolOrder[Right.Target];
         });
     for (SymbolID SID = 0; SID < T->Nonterminals.size(); ++SID) {
       auto StartIt = llvm::partition_point(T->Rules, [&](const Rule &R) {
private:
   void applyAttributes(const RuleSpec& Spec, const GrammarTable& T, Rule& R) {
     auto LookupExtensionID = [&T](llvm::StringRef Name) {
       const auto It = llvm::partition_point(
           T.AttributeValues, [&](llvm::StringRef X) { return X < Name; });
       assert(It != T.AttributeValues.end() && *It == Name &&
              "Didn't find the attribute in AttrValues!");
       return It - T.AttributeValues.begin();
     };
-    for (const auto &KV : Spec.Sequence.back().Attributes) {
+    for (unsigned I = 0; I < Spec.Sequence.size(); ++I) {
+      for (const auto &KV : Spec.Sequence[I].Attributes) {
         if (KV.first == "guard") {
           R.Guard = LookupExtensionID(KV.second);
-        continue;
-      }
+        } else if (KV.first == "recover") {
+          R.Recovery = LookupExtensionID(KV.second);
+          R.RecoveryIndex = I;
+        } else {
           Diagnostics.push_back(
               llvm::formatv("Unknown attribute '{0}'", KV.first).str());
         }
       }
+    }
+  }
 
   // Inlines all _opt symbols.
   // For example, a rule E := id +_opt id, after elimination, we have two
   // equivalent rules:
   //   1) E := id + id
   //   2) E := id id
   std::vector<RuleSpec> eliminateOptional(llvm::ArrayRef<RuleSpec> Input) {
     std::vector<RuleSpec> Results;

clang-tools-extra/pseudo/lib/grammar/LRGraph.cpp

for (const Item &I : Batch)
       Next.push_back(I.advance());
     // sort the set to keep order determinism for hash computation.
     llvm::sort(Next);
     Results.push_back({AdvancedSymbol, std::move(Next)});
   }
   return Results;
 }
 
-std::vector<std::pair<RecoveryStrategy, SymbolID>>
+std::vector<std::pair<ExtensionID, SymbolID>>
 availableRecovery(const State &S, const Grammar &G) {
-  std::vector<std::pair<RecoveryStrategy, SymbolID>> Result;
+  std::vector<std::pair<ExtensionID, SymbolID>> Result;
   for (const Item &I : S.Items) {
     const auto &Rule = G.lookupRule(I.rule());
     if (I.dot() != Rule.RecoveryIndex)
       continue;
     Result.push_back({Rule.Recovery, Rule.seq()[Rule.RecoveryIndex]});
   }
   llvm::sort(Result);
   Result.erase(std::unique(Result.begin(), Result.end()), Result.end());
std::pair<StateID, /*inserted*/ bool> insert(ItemSet KernelItems) {
       StatesIndex.insert({std::move(KernelItems), NextStateID});
       return {NextStateID, true};
     }
 
     void insertEdge(StateID Src, StateID Dst, SymbolID Label) {
       Edges.push_back({Src, Dst, Label});
     }
 
-    void insertRecovery(StateID Src, RecoveryStrategy Strategy,
-                        SymbolID Result) {
+    void insertRecovery(StateID Src, ExtensionID Strategy, SymbolID Result) {
       Recoveries.push_back({Src, Strategy, Result});
     }
 
     // Returns a state with the given id.
     const State &find(StateID ID) const {
       assert(ID < States.size());
       return States[ID];
     }

clang-tools-extra/pseudo/test/cxx/empty-member-spec.cpp

 // RUN: clang-pseudo -grammar=cxx -source=%s --print-forest | FileCheck %s
 class Foo {
 public:
 };
-// CHECK:      decl-specifier-seq~class-specifier := class-head { member-specification [recover=1] }
+// CHECK:      decl-specifier-seq~class-specifier := class-head { member-specification [recover=Brackets] }
 // CHECK-NEXT: ├─class-head := class-key class-head-name
 // CHECK-NEXT: │ ├─class-key~CLASS := tok[0]
 // CHECK-NEXT: │ └─class-head-name~IDENTIFIER := tok[1]
 // CHECK-NEXT: ├─{ := tok[2]
 // CHECK-NEXT: ├─member-specification := access-specifier :
 // CHECK-NEXT: │ ├─access-specifier~PUBLIC := tok[3]
 // CHECK-NEXT: │ └─: := tok[4]
 // CHECK-NEXT: └─} := tok[5]

clang-tools-extra/pseudo/test/cxx/recovery-init-list.cpp

-// RUN: clang-pseudo -grammar=%cxx-bnf-file -source=%s --print-forest | FileCheck %s
+// RUN: clang-pseudo -grammar=cxx -source=%s --print-forest | FileCheck %s
 auto x = { complete garbage };
 // CHECK:      translation-unit~simple-declaration
 // CHECK-NEXT: ├─decl-specifier-seq~AUTO := tok[0]
 // CHECK-NEXT: ├─init-declarator-list~init-declarator
 // CHECK-NEXT: │ ├─declarator~IDENTIFIER := tok[1]
 // CHECK-NEXT: │ └─initializer~brace-or-equal-initializer
 // CHECK-NEXT: │   ├─= := tok[2]
 // CHECK-NEXT: │   └─initializer-clause~braced-init-list
 // CHECK-NEXT: │     ├─{ := tok[3]
 // CHECK-NEXT: │     ├─initializer-list := <opaque>
 // CHECK-NEXT: │     └─} := tok[6]
 // CHECK-NEXT: └─; := tok[7]

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];
+  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() {

 }
 
 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"}, {});
+  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}, {RecoveryStrategy::Braces, id("word")}});
+  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.

 }
 
 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"}, {});
+  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}, {RecoveryStrategy::Braces, id("body")}});
+  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;

 
 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"}, {});
+  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}, {RecoveryStrategy::Braces, id("number")}});
-  B.Recoveries.push_back({StateID{1}, {RecoveryStrategy::Braces, id("word")}});
+  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);

 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
 
-    block := { block }
-    block := { numbers }
+    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=1] }\n"
+            "[  0, end) block := { block [recover=Braces] }\n"
             "[  0,   1) ├─{ := tok[0]\n"
             "[  1,   5) ├─block := <ambiguous>\n"
-            "[  1,   5) │ ├─block := { block [recover=1] }\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=1] }\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, NoExplicitAccept) {
   build(R"bnf(