[pseudo] Perform unconstrained recovery prior to completion.

[sammccall]

Summary

Our GLR uses lookahead: only perform reductions that might be consumed by the
shift immediately following. However when shift fails and so reduce is followed
by recovery instead, this restriction is incorrect and leads to missing heads.

In turn this means certain recovery strategies can't be made to work. e.g.

ns := NAMESPACE { namespace-body } [recover=Skip]
ns-body := namespace_opt

When namespace { namespace { is parsed, we can recover the inner ns (using
the Skip strategy to ignore the missing }). However this namespace will
not be reduced to a namespace-body as EOF is not in the follow-set, and so we
are unable to recover the outer ns.

This patch fixes this by tracking which heads were produced by constrained
reduce, and discarding and rebuilding them before performing recovery.

This is a prerequisite for the Skip strategy mentioned above, though there are
some other limitations we need to address too.

[sammccall]

restore removed debug

[sammccall]

Apart from this patch, the main other things we need to allow missing brackets to be inferred:

• allow recovery to trigger subsequent recovery, even at EOF. (Simplest way is to address the FIXME at 660, it's pretty involved)
• allow opaque nodes to represent terminals

I have a prototype of all this working together locally, it seems to work...

[hokein]

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

109

this if doesn't make sense, and is not needed, I think.

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

625

I think we can move the Line634 Heads.resize(HeadsPartition) before the glrShift() as we only do shift on the nearly-created heads, we might gain some performance back.

653

Can we have some comments on GLRReduce::operator() on how does parameter Head get modified (new heads are appended to it)?

[hokein]

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

625

oops, my previous comment is incorrect, here we want the second part of the partition; while on recovery, we want the first part of partition.

we can pass llvm::ArrayRef<const GSS::Node *>(Heads).drop_front(HeadsPartition); as the Heads to glrShift.

[sammccall]

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

625

As discussed offline, shifting onto a head that was produced by shift should be allowed.

given grammar

foo := [ ]
bar := [
baz := bar ]

and input [], after [ we have Heads={ [, bar} } with the former shifted and the latter reduced.
If we applied your suggestion here, we would fail to parse foo (but would succeed in parsing baz).

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

llvm::ArrayRef<RuleID> getReduceRules(StateID State) const {
     assert(State + 1u < ReduceOffset.size());
     return llvm::makeArrayRef(Reduces.data() + ReduceOffset[State],
                               Reduces.data() + ReduceOffset[State+1]);
   }
   // Returns whether Terminal can follow Nonterminal in a valid source file.
   bool canFollow(SymbolID Nonterminal, SymbolID Terminal) const {
     assert(isToken(Terminal));
     assert(isNonterminal(Nonterminal));
-    return FollowSets.test(tok::NUM_TOKENS * Nonterminal +
+    // tok::unknown is a sentinel value used in recovery: can follow anything.
+    if (tok::unknown)
+      return true;
+    return Terminal == tokenSymbol(tok::unknown) ||
+           FollowSets.test(tok::NUM_TOKENS * Nonterminal +
                            symbolToToken(Terminal));
   }
 
   // Looks up available recovery actions if we stopped parsing in this state.
   llvm::ArrayRef<Recovery> getRecovery(StateID State) const {
     return llvm::makeArrayRef(Recoveries.data() + RecoveryOffset[State],
                               Recoveries.data() + RecoveryOffset[State + 1]);
   }

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

const ForestNode &glrParse(const ParseParams &Params, SymbolID StartSymbol,
   llvm::ArrayRef<ForestNode> Terminals = Params.Forest.createTerminals(Params.Code);
   auto &GSS = Params.GSStack;
 
   StateID StartState = Lang.Table.getStartState(StartSymbol);
   // Heads correspond to the parse of tokens [0, I), NextHeads to [0, I+1).
   std::vector<const GSS::Node *> Heads = {GSS.addNode(/*State=*/StartState,
                                                       /*ForestNode=*/nullptr,
                                                       {})};
+  // Invariant: Heads is partitioned by source: {shifted | reduced}.
+  // HeadsPartition is the index of the first head formed by reduction.
+  // We use this to discard and recreate the reduced heads during recovery.
+  unsigned HeadsPartition = 0;
   std::vector<const GSS::Node *> NextHeads;
   auto MaybeGC = [&, Roots(std::vector<const GSS::Node *>{}), I(0u)]() mutable {
     assert(NextHeads.empty() && "Running GC at the wrong time!");
     if (++I != 20) // Run periodically to balance CPU and memory usage.
       return;
     I = 0;
 
     // We need to copy the list: Roots is consumed by the GC.
     Roots = Heads;
     GSS.gc(std::move(Roots));
   };
   // Each iteration fully processes a single token.
   for (unsigned I = 0; I < Terminals.size();) {
     LLVM_DEBUG(llvm::dbgs() << llvm::formatv(
                    "Next token {0} (id={1})\n",
                   Lang.G.symbolName(Terminals[I].symbol()), Terminals[I].symbol()));
     // Consume the token.
     glrShift(Heads, Terminals[I], Params, Lang, NextHeads);
 
     // If we weren't able to consume the token, try to skip over some tokens
     // so we can keep parsing.
     if (NextHeads.empty()) {
-      // FIXME: Heads may not be fully reduced, because our reductions were
-      // constrained by lookahead (but lookahead is meaningless to recovery).
+      // The reduction in the previous round was constrained by lookahead.
+      // On valid code this only rejects dead ends, but on broken code we should
+      // consider all possibilities.
+      //
+      // We discard all heads formed by reduction, and recreate them without
+      // this constraint. This may duplicate some nodes, but it's rare.
+      LLVM_DEBUG(llvm::dbgs() << "Shift failed, will attempt recovery. "
+                                 "Re-reducing without lookahead.");
+      Heads.resize(HeadsPartition);
+      Reduce(Heads, /*allow all reductions*/ tokenSymbol(tok::unknown));
+
       glrRecover(Heads, I, Params, Lang, 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);
     } else
       ++I;
 
     // Form nonterminals containing the token we just consumed.
     SymbolID Lookahead =
         I == Terminals.size() ? tokenSymbol(tok::eof) : Terminals[I].symbol();
+    HeadsPartition = NextHeads.size();
     Reduce(NextHeads, Lookahead);
     // Prepare for the next token.
     std::swap(Heads, NextHeads);
     NextHeads.clear();
     MaybeGC();
   }
   LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Reached eof\n"));
 
   // The parse was successful if we're in state `_ := start-symbol .`

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

TEST_F(GLRTest, RecoverTerminal) {
   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
+
+    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, NoExplicitAccept) {
   build(R"bnf(
     _ := test
 
     test := IDENTIFIER test
     test := IDENTIFIER
   )bnf");