[pseudo] Reimplement hardcoded error handling as a recovery strategy. NFC

[hokein]

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

89

I think there should be some documentation for the strategies here. (do you plan to add them when the above FIXME is fixed?)

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

122

nit: use the StartSymbol global variable (we might want to rename it to Underscore).

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

inline tok::TokenKind symbolToToken(SymbolID SID) {
   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 };
+enum class RecoveryStrategy : uint8_t { None, Braces, Eof };
 
 // 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.

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

 namespace clang {
 namespace pseudo {
 namespace {
 
 llvm::Optional<unsigned>
 findRecoveryEndpoint(RecoveryStrategy Strategy,
                      const GSS::Node *RecoveryNode,
                      const TokenStream &Tokens) {
-  assert(Strategy == RecoveryStrategy::Braces);
+  switch (Strategy) {
+  case 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);
     return llvm::None;
   }
+  case RecoveryStrategy::Eof:
+    return Tokens.tokens().size();
+  case RecoveryStrategy::None:
+    break;
+  }
+  llvm_unreachable("Invalid strategy");
+}
 
 } // namespace
 
 void glrRecover(llvm::ArrayRef<const GSS::Node *> OldHeads,
                 unsigned &TokenIndex, const TokenStream &Tokens,
                 const ParseParams &Params,
                 std::vector<const GSS::Node *> &NewHeads) {
   LLVM_DEBUG(llvm::dbgs() << "Recovery at token " << TokenIndex << "...\n");
LLVM_DEBUG(llvm::dbgs() << llvm::formatv(
                    G.symbolName(Terminals[I].symbol()), Terminals[I].symbol()));
     // Consume the token.
     glrShift(Heads, Terminals[I], Params, NextHeads);
 
     // If we weren't able to consume the token, try to skip over some tokens
     // so we can keep parsing.
     if (NextHeads.empty()) {
       glrRecover(Heads, I, Tokens, Params, NextHeads);
-      if (NextHeads.empty())
-        // FIXME: Ensure the `_ := start-symbol` rules have a fallback
-        // error-recovery strategy attached. Then this condition can't happen.
-        return Params.Forest.createOpaque(StartSymbol, /*Token::Index=*/0);
+      assert(!NextHeads.empty() && "No fallback recovery?!");
     } else
       ++I;
 
     // Form nonterminals containing the token we just consumed.
     SymbolID Lookahead =
         I == Terminals.size() ? tokenSymbol(tok::eof) : Terminals[I].symbol();
     Reduce(NextHeads, Lookahead);
     // Prepare for the next token.
const ForestNode &glrParse(const TokenStream &Tokens, const ParseParams &Params,
   // FIXME: this awkwardly repeats the recovery in the loop, when shift fails.
   // More elegant is to include EOF in the token stream, and make the
   // augmented rule: `_ := translation-unit EOF`. In this way recovery at EOF
   // would not be a special case: it show up as a failure to shift the EOF
   // token.
   unsigned I = Terminals.size();
   glrRecover(Heads, I, Tokens, Params, NextHeads);
   Reduce(NextHeads, tokenSymbol(tok::eof));
-  if (auto *Result = SearchForAccept(NextHeads))
-    return *Result;
-
-  // We failed to parse the input, returning an opaque forest node for recovery.
-  // FIXME: as above, we can add fallback error handling so this is impossible.
-  return Params.Forest.createOpaque(StartSymbol, /*Token::Index=*/0);
+  auto *Result = SearchForAccept(NextHeads);
+  assert(Result && "No fallback recovery?");
 }
 
 void glrReduce(std::vector<const GSS::Node *> &Heads, SymbolID Lookahead,
                const ParseParams &Params) {
   // Create a new GLRReduce each time for tests, performance doesn't matter.
   GLRReduce{Params}(Heads, Lookahead);
 }
 

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!");
+    // Infer recovery strategies.
+    for (auto &Rule : T->Rules) {
       // 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;
         }
+      // In `_ := symbol`, match symbol against the whole input on error.
+      // This ensures the overall parse never fails.
+      if (T->Nonterminals[Rule.Target].Name == "_") {
+        Rule.Recovery = RecoveryStrategy::Eof;
+        Rule.RecoveryIndex = 0;
+      }
     }
     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) {