[pseudo] Add error-recovery framework & brace-based recovery

[sammccall]

Summary

The idea is:

• a parse failure is detected when all heads die when trying to shift the next token
• we can recover by choosing a nonterminal we're partway through parsing, and determining where it ends through nonlocal means (e.g. matching brackets)
• we can find candidates by walking up the stack from the (ex-)heads
• the token range is defined using heuristics attached to grammar rules
• the unparsed region is represented in the forest by an Opaque node

This patch has the core GLR functionality.
It does not allow recovery heuristics to be attached as extensions to
the grammar, but rather infers a brace-based heuristic.

Expected followups:

• make recovery heuristics grammar extensions (depends on D127448)
• add recover to our grammar for bracketed constructs and sequence nodes
• change the structure of our augmented _ := start rules to eliminate some special-cases in glrParse.
• (if I can work out how): avoid some spurious recovery cases described in comments
• grammar changes to eliminate the hard distinction between init-list and designated-init-list shown in the recovery-init-list.cpp testcase

[sammccall]

add tests, clean up

[sammccall]

reduce after final recovery
comments

[sammccall]

revert format changes

[sammccall]

update testcase

[sammccall]

rebase

[sammccall]

Sorry, I committed this by mistake when working on another change.
Reverted and this is ready for review.

[hokein]

the patch looks a good start to me, some initial comments (mostly around the recovery part).

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

150

If I read it correctly, consuming zero token is consider failure of the function, right?

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

134

So each rule will have at most 1 recovery-strategy (it is fine for the initial version), but I think in the future we want more (probably we need to change the Sequence to an array of {SymbolID, RevoeryStrategy}).

selection-statement := IF CONSTEXPR_opt ( init-statement_opt condition ) statement ELSE statement

We might want different recoveries in ( . init-statement_opt condition ) (init-statement_opt condition) . statement, ELSE . statement.

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

248

I see the motivation of the OffsetTable structure now, this would come as a follow-up to simplify the ReduceOffset and RecoveryOffset, right?

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

29

nit: unsigned => Token::Index

44

The GLR.cpp file is growing significantly, I think the recovery part is large enough to be lived in a separate file GLRRecovery.cpp, but the declaration can still be in the GLR.h.

64

this is not implemented, right? Add a FIXME?

68

nit: maybe name it Parses or PartialParses. Path make me think this is a patch of GSS nodes.

83

I think you're right -- I thought the first GSS node with a recovery state we encounter during the Walkup state is the node we want.

This example is a little confusing (it still matches our previous mental model), I didn't get it until we discussed offline. I think the following example is clearer

parsing the text `if (true) else ?`

IfStmt := if (stmt) else . stmt - which we're currently parsing
IfStmt := if (.stmt) else stmt  - (left) the first recovery GSS node, should not recover from this
IfStmt := . if (stmt) else stmt - (up), we should recover from this

I also think it is worth to add it into the test.

88

I can't think of a better solution other than a search-based one (would like to think more about it).

Currently, we find all recovery options by traversing the whole GSS, and do a post-filter (based on the Start, and End). I might do both in the DFS (which will save some cost of traversing), the DFS will give us the best recovery options, and then we build the GSS node, and forest node. But up to you.

91

nit: Walkup seems a bit clearer than DFS.

111

any particular reason why we iterate the OldHeads in a reversed order?

130

nit: might be clearer to move the assertion to the beginning of the function.

133

further right should be further left, right?

149

If we find a better recovery option, we're throwing all the newly-built heads and forest nodes, this seems wasteful. I think we can avoid it by first finding the best solutions and creating new heads and gss nodes for them.

150

The Line135-Line150 code looks like a good candidate for an evaluateOption function.

174

Advancing the TokenIndex here seems a little surprising and doesn't match what the comment says ( On failure, NewHeads is empty and TokenIndex is unchanged.). I think this should be done in caller side.

600

currently, it is fine for bracket-based recovery. In the future, we will need to run a force reduction for Heads regardless of the lookahead token before running the glrRecover, add a FIXME?

601

If the glrRecover returns a bool indicating whether we're able to recover, then the code is simpler:

if (NextHeads.empty() && !glrRecover(...))
  return Params.Forest.createOpaque(...);

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

382

nit: for GSS nodes, I will name them like GSSNode<StateID>, it is less describable, but it can be easily distinguished from other forest nodes, and match the GSS described in the comment, which I think it is clearer.

425

I suppose there is an extra ? in the string literal, the index of the brackets (4, 5) used below doesn't match the string literal here.

[sammccall]

address comments

[sammccall]

address comments

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

150

Consuming zero tokens + producing heads is success, consuming zero tokens + not producing heads is failure.
Tweaked this comment a bit.

(Also fixed a bit of logic that ignored recovery that didn't advance TokenIndex!)

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

134

Added a comment to call out this limitation.
There are several ways to deal with this, e.g. we could split up the grammar into multiple rules, each with one recovery. (But the approach you describe makes sense too)

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

248

Yes. Though I'm on the fence about whether it's worth it with one case (it's a bit awkward to generalize the building IIRC).

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

44

This is interesting, recover/shift/reduce/parse are (vertically) self-contained enough that it didn't seem like a big problem yet...

If the concern is file length, maybe we'd thather start with reduce; if it's relatedness, GSS?

My line count is:

• recover: 156
• shift: 47
• reduce: 319
• parse: 87
• GSS: 66

68

Renamed to DiscardedParse, does that work for you?

83

Fair enough, a couple of problems with that example though:

• dropping the "then" clause from the grammar of an if statement is confusing (but adding it back in makes the example complicated)
• using a non-kernel item for the last fails to show the "up" edge clearly (but there's not enough context to show a kernel item)

Came up with another one that hopefully works.

I didn't manage to write a reasonable test showing it - it basically can't happen with bracket recovery. In order to demonstrate it we need { in the "wrong" recovery construct to be paired with a } after the cursor... which makes it look *very* much like a correct recovery.

Added a FIXME to add a testcase once we can define new recovery strategies instead.

88

I'm not sure what you mean by a search-based one, can you elaborate?

Currently, we find all recovery options by traversing the whole GSS, and do a post-filter (based on the Start, and End). I might do both in the DFS (which will save some cost of traversing)

This replaces a relatively simple traversal of GSS nodes (which there aren't that many of) with running the recovery strategy more times - this is (usually) a more complicated algorithm running over tokens, which is (usually) a larger data set. It seems likely to be a bad trade performance-wise.

In any case, performance isn't terribly critical here, and mixing the discovery & evaluation of options seems harder to read & debug (we lose the nice documented data structures we can debug, predictable -debug dumping of not-taken recovery options, etc).

111

Not that I can remember, and the unit tests don't seem to care, so removed

130

The purpose of the assertion is to make it obvious that NewHeads.clear() only discards items added during the loop below.
An assertion at the top of the function would be less useful for this, both because it's not on the screen when reading NewHeads.clear() and because it's much less locally obvious that nothing has been pushed onto NewHeads at some prior point in the function.

150

What would the signature of such a function look like?
There are many different possible outcomes:

• replace the set with this option (BestOptions.clear)
• add this option to the set (BestOptions.push_back)
• discard this option (continue)
• discard this option and all future options (break)
• update recovery range or not

Access to control flow (break/continue) and read/write access to RecoveryRange and BestOptions seem like the natural way to express this, so it's not clear what a function could abstract away.

174

Oops, this shouldn't be done at all - originally I had a different contract for glrRecover().

(In fact, if NewHeads is empty after glrRecover() we never look at TokenIndex again, but let's not rely on that)

600

Done. This impacts the internal structure of the recovered node much more than it does which recoveries are available, so I think we can defer this for a fair while.

601

I had this initially, but:
a) it's redundant, and makes it less locally obvious that we've repopulated NewHeads
b) soon recovery will always succeed, so !NewHeads.empty() becomes an assertion

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

382

Yeah, I found those testcases difficult to read :-(
I did work out that the numbers might be state numbers rather than node numbers, but I found it hard to a) remember that, since it's often GSSNode0, GSSNode1 etc and b) remember which state is which.
It doesn't generalize, e.g. the RecoverRightmost case has 3 nodes with the same state.

425

Oops, yes!
Originally this testcase was meant to test more things, and apparently I didn't finish simplifying it...

[hokein]

Looks great, let's ship it! feel free to land it in any form you think it is suitable.

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

150

nit: remove the duplicated consumes.

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

148

nit: mention the Result must be a nonterminal.

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

131

nit: unrelated method?

248

A motivating bit is that it is tricky to implement a correct get method (we both made the same out-of-bound issue). I'm fine with the current form, we can revisit it afterwards.

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

44

Yeah, indeed these pieces can be split, my main concern is not file length -- I would prefer keeping shift/reduce/parse into a single file, as they form a complete GLR algorithm (splitting them would make it harder to read and follow).

Recovery seems like a different thing, I would image this part of code will grow more in the future

• the GLR algorithm has the core recovery mechanism framework with some fallback recovery strategies (eof, brackets)
• we have different recovery strategies implemented (some of them might be cxx-specific, probably be part of pseudoCXX library);

68

It is better than the original name. The DiscardedParse is a bit weird when we start to put it under the opaque node, in that sense, they are not discarded, IMO

83

oops, your example makes more sense -- I didn't notice that I missed the if-body stmt.

88

I'm not sure what you mean by a search-based one, can you elaborate?

The search-based one refers to the current one -- basically we perform a brute-force search for all available recoveries and get the best one.

In any case, performance isn't terribly critical here, and mixing the discovery & evaluation of options seems harder to read & debug (we lose the nice documented data structures we can debug, predictable -debug dumping of not-taken recovery options, etc).

That's fair enough.

130

Yeah, but I'd treat it as a contract of the API (the NewHeads argument passed to glrRecover must be empty).

btw, the empty assertion is missing in the latest version.

178

should we worry about the case where we create a duplicated forest node? e.g. we have two best options and both recover to the same nonterminal.

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

487

nit: I'd probably move this to the comment mentioned in glrRecovery(), which is more discoverable.

558

nit: not sure the intention having the RecoveryEndToEnd separated from the above recover-related tests, why not grouping them together?

[sammccall]

Thanks in particular for flagging the issue with duplicate forest nodes, you've found a hole in the model.
That said, I've left a big FIXME and I think we should patch it later.

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

148

Hmm, I don't think it has to be?

(To deduce a brace recovery rule we require it, but that doesn't mean it needs to be true in general)

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

44

It's hard to tell yet, but I guess I don't really see why it's going to be easier to reason about shift/recover in isolation vs shift/reduce. Let's see how this goes past the initial patch (in particular once we move stuff into extensions)

130

Yes, I think this is obsolete - the latest version of glrRecover no longer requires NewHeads to be empty at all, as it doesn't use it as scratch space.

178

Oh no, you're right... we also have all the options for the GSS node being either the same/different in that case.

And it gets worse, what if we have one recovery -> X, and another recovery -> Y, and a rule X := Y. The following glrReduce will produce a duplicate X, instead of an AmbiguousX{ OpaqueX, SequenceX{ OpaqueY } }.

As much as I hate this, I think we should slap a FIXME on it and move on. I don't think multiple tied recoveries is common, and the solution here is just as likely to break the tie as it is to fix this with fancy algorithms.
However I don't think we have enough data to make a decision on exactly what to do yet.

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

558

this tests glrParse, and it's grouped with the other glrParse tests consistent with this file (e.g. GLRReduceOrder is with the glrParse tests, not with the glrReduce tests)

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

void glrShift(llvm::ArrayRef<const GSS::Node *> OldHeads,
               const ForestNode &NextTok, const ParseParams &Params,
               std::vector<const GSS::Node *> &NewHeads);
 // Applies available reductions on Heads, appending resulting heads to the list.
 //
 // Exposed for testing only.
 void glrReduce(std::vector<const GSS::Node *> &Heads, SymbolID Lookahead,
                const ParseParams &Params);
 
+// Heuristically recover from a state where no further parsing is possible.
+//
+// OldHeads is the parse state at TokenIndex.
+// This function consumes consumes zero or more tokens by advancing TokenIndex,
+// and places any recovery states created in NewHeads.
+//
+// On failure, NewHeads is empty and TokenIndex is unchanged.
+//
+// WARNING: glrRecover acts as a "fallback shift". If it consumes no tokens,
+// there is a risk of the parser falling into an infinite loop, creating an
+// endless sequence of recovery nodes.
+// Generally it is safe for recovery to match 0 tokens against sequence symbols
+// like `statement-seq`, as the grammar won't permit another statement-seq
+// immediately afterwards. However recovery strategies for `statement` should
+// consume at least one token, as statements may be adjacent in the input.
+void glrRecover(llvm::ArrayRef<const GSS::Node *> OldHeads,
+                unsigned &TokenIndex, const TokenStream &Tokens,
+                const ParseParams &Params,
+                std::vector<const GSS::Node *> &NewHeads);
+
 } // namespace pseudo
 } // namespace clang
 
 #endif // CLANG_PSEUDO_GLR_H

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

 inline bool isNonterminal(SymbolID ID) { return !isToken(ID); }
 // The terminals are always the clang tok::TokenKind (not all are used).
 inline tok::TokenKind symbolToToken(SymbolID SID) {
   assert(isToken(SID));
   SID &= ~TokenFlag;
   assert(SID < NumTerminals);
   return static_cast<tok::TokenKind>(SID);
 }
-inline SymbolID tokenSymbol(tok::TokenKind TK) {
+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.
 using RuleID = uint16_t;
 // There are maximum 2^12 rules.
 static constexpr unsigned RuleBits = 12;
 
 // Represent a production rule in the grammar, e.g.
 //   expression := a b c
 //   ^Target       ^Sequence
 struct Rule {
   Rule(SymbolID Target, llvm::ArrayRef<SymbolID> Seq);
 
   // We occupy 4 bits for the sequence, in theory, it can be at most 2^4 tokens
   // long, however, we're stricter in order to reduce the size, we limit the max
   // length to 9 (this is the longest sequence in cxx grammar).
   static constexpr unsigned SizeBits = 4;
   static constexpr unsigned MaxElements = 9;
-  static_assert(MaxElements <= (1 << SizeBits), "Exceeds the maximum limit");
+  static_assert(MaxElements < (1 << SizeBits), "Exceeds the maximum limit");
   static_assert(SizeBits + SymbolBits <= 16,
                 "Must be able to store symbol ID + size efficiently");
 
   // 16 bits for target symbol and size of sequence:
   // SymbolID : 12 | Size : 4
   SymbolID Target : SymbolBits;
   uint8_t Size : SizeBits; // Size of the Sequence
   SymbolID Sequence[MaxElements];
 
   // A guard extension controls whether a reduction of a rule will be conducted
   // by the GLR parser.
   // 0 is sentinel unset extension ID, indicating there is no guard extension
   // being set for this 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;
+
   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:
   // An edge in the LR graph, it represents a transition in the LR automaton.
   // If the parser is at state Src, with a lookahead Label, then it
   // transits to state Dst.
   struct Edge {
     StateID Src, Dst;
     SymbolID Label;
   };
 
+  // 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.
+    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;
   }
 
   std::string dumpForTests(const Grammar &) const;
 
 private:
   LRGraph(std::vector<State> States, std::vector<Edge> Edges,
+          std::vector<Recovery> Recoveries,
           std::vector<std::pair<SymbolID, StateID>> StartStates)
       : States(std::move(States)), Edges(std::move(Edges)),
-        StartStates(std::move(StartStates)) {}
+        Recoveries(std::move(Recoveries)), StartStates(std::move(StartStates)) {
+  }
 
   std::vector<State> States;
   std::vector<Edge> Edges;
+  std::vector<Recovery> Recoveries;
   std::vector<std::pair<SymbolID, StateID>> StartStates;
 };
 
 } // namespace pseudo
 } // namespace clang
 
 namespace llvm {
 // Support clang::pseudo::Item as DenseMap keys.

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

private:
     static_assert(ValueBits >= RuleBits, "Value must be able to store RuleID");
     static_assert(KindBits + ValueBits <= 16,
                   "Must be able to store kind and value efficiently");
     uint16_t K : KindBits;
     // Either StateID or RuleID, depending on the Kind.
     uint16_t Value : ValueBits;
   };
 
+  struct Recovery {
+    RecoveryStrategy Strategy;
+    SymbolID Result;
+  };
+
+  // Returns all available actions for the given state on a terminal.
+  // Expected to be called by LR parsers.
+  llvm::ArrayRef<Action> getActions(StateID State, SymbolID Terminal) const;
   // Returns the state after we reduce a nonterminal.
   // Expected to be called by LR parsers.
   // REQUIRES: Nonterminal is valid here.
   StateID getGoToState(StateID State, SymbolID Nonterminal) const;
   // Returns the state after we shift a terminal.
   // Expected to be called by LR parsers.
   // If the terminal is invalid here, returns None.
   llvm::Optional<StateID> getShiftState(StateID State, SymbolID Terminal) const;
public:
   // 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 +
                            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]);
+  }
+
   // Returns the state from which the LR parser should start to parse the input
   // tokens as the given StartSymbol.
   //
   // In LR parsing, the start state of `translation-unit` corresponds to
   // `_ := • translation-unit`.
   //
   // Each start state responds to **a** single grammar rule like `_ := start`.
   // REQUIRE: The given StartSymbol must exist in the grammar (in a form of
struct Entry {
     StateID State;
     SymbolID Symbol;
     Action Act;
   };
   struct ReduceEntry {
     StateID State;
     RuleID Rule;
   };
-  // Build a specifid table for testing purposes.
-  static LRTable buildForTests(const Grammar &G, llvm::ArrayRef<Entry>,
-                               llvm::ArrayRef<ReduceEntry>);
+  struct RecoveryEntry {
+    StateID State;
+    RecoveryStrategy Strategy;
+    SymbolID Result;
+  };
+  // Build a specified table for testing purposes.
+  static LRTable buildForTests(const Grammar &, llvm::ArrayRef<Entry>,
+                               llvm::ArrayRef<ReduceEntry>,
+                               llvm::ArrayRef<RecoveryEntry> = {});
 
 private:
   // Looks up actions stored in the generic table.
   llvm::ArrayRef<Action> find(StateID State, SymbolID Symbol) const;
 
   // Conceptually the LR table is a multimap from (State, SymbolID) => Action.
   // Our physical representation is quite different for compactness.
 
private:
   std::vector<uint32_t> ReduceOffset;
   std::vector<RuleID> Reduces;
   // Conceptually this is a bool[SymbolID][Token], each entry describing whether
   // the grammar allows the (nonterminal) symbol to be followed by the token.
   //
   // This is flattened by encoding the (SymbolID Nonterminal, tok::Kind Token)
   // as an index: Nonterminal * NUM_TOKENS + Token.
   llvm::BitVector FollowSets;
+
+  // Recovery stores all recovery actions from all states.
+  // A given state has [RecoveryOffset[S], RecoveryOffset[S+1]).
+  std::vector<uint32_t> RecoveryOffset;
+  std::vector<Recovery> Recoveries;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const LRTable::Action &);
 
 } // namespace pseudo
 } // namespace clang
 
 #endif // CLANG_PSEUDO_GRAMMAR_LRTABLE_H

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

 #include <algorithm>
 #include <memory>
 #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);
+  return Token::Invalid;
+}
+
+} // 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");
+  // 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;
+
+    // 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.
+    //
+    // There may be multiple paths leading to the same recovery node, we choose
+    // one arbitrarily.
+    std::vector<const ForestNode *> DiscardedParse;
+  };
+  std::vector<PlaceholderRecovery> Options;
+
+  // Find recovery options by walking up the stack.
+  //
+  // This is similar to exception handling: we walk up the "frames" of nested
+  // rules being parsed until we find one that has a "handler" which allows us
+  // to determine the node bounds without parsing it.
+  //
+  // Unfortunately there's a significant difference: the stack contains both
+  // "upward" nodes (ancestor parses) and "leftward" ones.
+  // e.g. when parsing `{ if (1) ? }` as compound-stmt, the stack contains:
+  //   stmt := IF ( expr ) . stmt      - current state, we should recover here!
+  //   stmt := IF ( expr . ) stmt      - (left, no recovery here)
+  //   stmt := IF ( . expr ) stmt      - left, we should NOT recover here!
+  //   stmt := IF . ( expr ) stmt      - (left, no recovery here)
+  //   stmt-seq := . stmt              - up, we might recover here
+  //   compound-stmt := { . stmt-seq } - up, we should recover here!
+  //
+  // It's not obvious how to avoid collecting "leftward" recovery options.
+  // I think the distinction is ill-defined after merging items into states.
+  // For now, we have to take this into account when defining recovery rules.
+  // (e.g. in the expr recovery above, stay inside the parentheses).
+  // FIXME: find a more satisfying way to avoid such false recovery.
+  std::vector<const ForestNode *> Path;
+  llvm::DenseSet<const GSS::Node *> Seen;
+  auto WalkUp = [&](const GSS::Node *N, Token::Index NextTok, auto &WalkUp) {
+    if (!Seen.insert(N).second)
+      return;
+    for (auto Strategy : Params.Table.getRecovery(N->State)) {
+      Options.push_back(PlaceholderRecovery{
+          NextTok,
+          Strategy.Result,
+          Strategy.Strategy,
+          N,
+          Path,
+      });
+      LLVM_DEBUG(llvm::dbgs()
+                 << "Option: recover " << Params.G.symbolName(Strategy.Result)
+                 << " at token " << NextTok << "\n");
+    }
+    Path.push_back(N->Payload);
+    for (const GSS::Node *Parent : N->parents())
+      WalkUp(Parent, N->Payload->startTokenIndex(), WalkUp);
+    Path.pop_back();
+  };
+  for (auto *N : OldHeads)
+    WalkUp(N, TokenIndex, WalkUp);
+
+  // Now we select the option(s) we will use to recover.
+  //
+  // We prefer options starting further right, as these discard less code
+  // (e.g. we prefer to recover inner scopes rather than outer ones).
+  // The options also need to agree on an endpoint, so the parser has a
+  // consistent position afterwards.
+  //
+  // So conceptually we're sorting by the tuple (start, end), though we avoid
+  // computing `end` for options that can't be winners.
+
+  // Consider options starting further right first.
+  // Don't drop the others yet though, we may still use them if preferred fails.
+  llvm::stable_sort(Options, [&](const auto &L, const auto &R) {
+    return L.Position > R.Position;
+  });
+
+  // We may find multiple winners, but they will have the same range.
+  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, Tokens);
+    // 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.
+      if (RecoveryRange->End > End)
+        BestOptions.clear();
+    }
+    // Create recovery nodes and heads for them in the GSS. These may be
+    // discarded if a better recovery is later found, but this path isn't hot.
+    RecoveryRange = {Option.Position, End};
+    BestOptions.push_back(&Option);
+  }
+
+  if (BestOptions.empty()) {
+    LLVM_DEBUG(llvm::dbgs() << "Recovery failed after trying " << Options.size()
+                            << " strategies\n");
+    return;
+  }
+
+  // We've settled on a set of recovery options, so create their nodes and
+  // advance the cursor.
+  LLVM_DEBUG({
+    llvm::dbgs() << "Recovered range=" << *RecoveryRange << ":";
+    for (const auto *Option : BestOptions)
+      llvm::dbgs() << " " << Params.G.symbolName(Option->Symbol);
+    llvm::dbgs() << "\n";
+  });
+  for (const PlaceholderRecovery *Option : BestOptions) {
+    const ForestNode &Placeholder =
+        Params.Forest.createOpaque(Option->Symbol, Option->Position);
+    const GSS::Node *NewHead = Params.GSStack.addNode(
+        Params.Table.getGoToState(Option->RecoveryNode->State, Option->Symbol),
+        &Placeholder, {Option->RecoveryNode});
+    NewHeads.push_back(NewHead);
+  }
+  TokenIndex = RecoveryRange->End;
+}
 
 using StateID = LRTable::StateID;
 
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const GSS::Node &N) {
   std::vector<std::string> ParentStates;
   for (const auto *Parent : N.parents())
     ParentStates.push_back(llvm::formatv("{0}", Parent->State));
-  OS << llvm::formatv("state {0}, parsed symbol {1}, parents {2}", N.State,
-                      N.Payload->symbol(), llvm::join(ParentStates, ", "));
+  OS << llvm::formatv("state {0}, parsed symbol {1}, parents {3}", N.State,
+                      N.Payload ? N.Payload->symbol() : 0,
+                      llvm::join(ParentStates, ", "));
   return OS;
 }
 
 // Apply all pending shift actions.
 // In theory, LR parsing doesn't have shift/shift conflicts on a single head.
 // But we may have multiple active heads, and each head has a shift action.
 //
 // We merge the stack -- if multiple heads will reach the same state after
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(); ++I) {
+  for (unsigned I = 0; I < Terminals.size();) {
     LLVM_DEBUG(llvm::dbgs() << llvm::formatv(
                    "Next token {0} (id={1})\n",
                    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()) {
+      // FIXME: Heads may not be fully reduced, because our reductions were
+      // constrained by lookahead (but lookahead is meaningless to recovery).
+      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);
+    } else
+      ++I;
+
     // Form nonterminals containing the token we just consumed.
-    SymbolID Lookahead = I + 1 == Terminals.size() ? tokenSymbol(tok::eof)
-                                                   : Terminals[I + 1].symbol();
+    SymbolID Lookahead =
+        I == Terminals.size() ? tokenSymbol(tok::eof) : Terminals[I].symbol();
     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 .`
   StateID AcceptState = Params.Table.getGoToState(StartState, StartSymbol);
+  auto SearchForAccept = [&](llvm::ArrayRef<const GSS::Node *> Heads) {
     const ForestNode *Result = nullptr;
     for (const auto *Head : Heads) {
       if (Head->State == AcceptState) {
         assert(Head->Payload->symbol() == StartSymbol);
         assert(Result == nullptr && "multiple results!");
         Result = Head->Payload;
       }
     }
-  if (Result)
+    return Result;
+  };
+  if (auto *Result = SearchForAccept(Heads))
+    return *Result;
+  // Failed to parse the input, attempt to run recovery.
+  // 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: We will need to invoke our generic error-recovery handlers when we
-  // reach EOF without reaching accept state, and involving the eof
-  // token in the above main for-loopmay be the best way to reuse the code).
+  // FIXME: as above, we can add fallback error handling so this is impossible.
   return Params.Forest.createOpaque(StartSymbol, /*Token::Index=*/0);
 }
 
 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);
 }
 
 const GSS::Node *GSS::addNode(LRTable::StateID State, const ForestNode *Symbol,
+
                               llvm::ArrayRef<const Node *> Parents) {
   Node *Result = new (allocate(Parents.size()))
-      Node({State, GCParity, static_cast<unsigned>(Parents.size())});
+      Node({State, GCParity, static_cast<uint16_t>(Parents.size())});
   Alive.push_back(Result);
   ++NodesCreated;
   Result->Payload = Symbol;
   if (!Parents.empty())
     llvm::copy(Parents, reinterpret_cast<const Node **>(Result + 1));
   return Result;
 }
 

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

llvm::Optional<SymbolID> Grammar::findNonterminal(llvm::StringRef Name) const {
   return llvm::None;
 }
 
 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 (SymbolID SID : R.seq())
-    OS << " " << symbolName(SID);
+  for (unsigned I = 0; I < R.Size; ++I) {
+    OS << " " << symbolName(R.Sequence[I]);
+    if (R.RecoveryIndex == I)
+      OS << " [recover=" << static_cast<unsigned>(R.Recovery) << "]";
+  }
   if (R.Guard)
     OS << " [guard=" << T->AttributeValues[R.Guard] << "]";
   return Result;
 }
 
 std::string Grammar::dumpRules(SymbolID SID) const {
   assert(isNonterminal(SID));
   std::string Result;

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) {

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>>
+availableRecovery(const State &S, const Grammar &G) {
+  std::vector<std::pair<RecoveryStrategy, 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());
+  return Result;
+}
+
 } // namespace
 
 std::string Item::dump(const Grammar &G) const {
   const auto &Rule = G.lookupRule(RID);
   auto ToNames = [&](llvm::ArrayRef<SymbolID> Syms) {
     std::vector<llvm::StringRef> Results;
     for (auto SID : Syms)
       Results.push_back(G.symbolName(SID));
     return Results;
   };
-  return llvm::formatv("{0} := {1} • {2}", G.symbolName(Rule.Target),
+  return llvm::formatv("{0} := {1} • {2}{3}", G.symbolName(Rule.Target),
                        llvm::join(ToNames(Rule.seq().take_front(DotPos)), " "),
-                       llvm::join(ToNames(Rule.seq().drop_front(DotPos)), " "))
+                       llvm::join(ToNames(Rule.seq().drop_front(DotPos)), " "),
+                       Rule.RecoveryIndex == DotPos ? " [recovery]" : "")
       .str();
 }
 
 std::string State::dump(const Grammar &G, unsigned Indent) const {
   std::string Result;
   llvm::raw_string_ostream OS(Result);
   for (const auto &Item : Items)
     OS.indent(Indent) << llvm::formatv("{0}\n", Item.dump(G));
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) {
+      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];
     }
 
     void addStartState(SymbolID Sym, StateID State) {
       StartStates.push_back({Sym, State});
     }
 
     LRGraph build() && {
       States.shrink_to_fit();
       Edges.shrink_to_fit();
+      Recoveries.shrink_to_fit();
       llvm::sort(StartStates);
       StartStates.shrink_to_fit();
-      return LRGraph(std::move(States), std::move(Edges),
+      return LRGraph(std::move(States), std::move(Edges), std::move(Recoveries),
                      std::move(StartStates));
     }
 
   private:
     // Key is the **kernel** item sets.
     llvm::DenseMap<ItemSet, /*index of States*/ size_t> StatesIndex;
     std::vector<State> States;
     std::vector<Edge> Edges;
+    std::vector<Recovery> Recoveries;
     const Grammar &G;
     std::vector<std::pair<SymbolID, StateID>> StartStates;
   } Builder(G);
 
   std::vector<StateID> PendingStates;
   // Initialize states with the start symbol.
   auto RRange = G.table().Nonterminals[G.underscore()].RuleRange;
   for (RuleID RID = RRange.Start; RID < RRange.End; ++RID) {
     auto StartState = std::vector<Item>{Item::start(RID, G)};
     auto Result = Builder.insert(std::move(StartState));
     assert(Result.second && "State must be new");
     PendingStates.push_back(Result.first);
 
     const Rule &StartRule = G.lookupRule(RID);
     assert(StartRule.Size == 1 &&
            "Start rule must have exactly one symbol in its body!");
     Builder.addStartState(StartRule.seq().front(), Result.first);
   }
 
   while (!PendingStates.empty()) {
-    auto CurrentStateID = PendingStates.back();
+    auto StateID = PendingStates.back();
     PendingStates.pop_back();
-    for (auto Next :
-         nextAvailableKernelItems(Builder.find(CurrentStateID), G)) {
+    for (auto Next : nextAvailableKernelItems(Builder.find(StateID), G)) {
       auto Insert = Builder.insert(Next.second);
       if (Insert.second) // new state, insert to the pending queue.
         PendingStates.push_back(Insert.first);
-      Builder.insertEdge(CurrentStateID, Insert.first, Next.first);
+      Builder.insertEdge(StateID, Insert.first, Next.first);
     }
+    for (auto Recovery : availableRecovery(Builder.find(StateID), G))
+      Builder.insertRecovery(StateID, Recovery.first, Recovery.second);
   }
   return std::move(Builder).build();
 }
 
 } // namespace pseudo
 } // namespace clang

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

 //===--- LRTableBuild.cpp - Build a LRTable from LRGraph ---------*- 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/grammar/Grammar.h"
 #include "clang-pseudo/grammar/LRGraph.h"
 #include "clang-pseudo/grammar/LRTable.h"
 #include "clang/Basic/TokenKinds.h"
 #include "llvm/ADT/SmallSet.h"
+#include "llvm/Support/raw_ostream.h"
 #include <cstdint>
 
 namespace llvm {
 template <> struct DenseMapInfo<clang::pseudo::LRTable::Entry> {
   using Entry = clang::pseudo::LRTable::Entry;
   static inline Entry getEmptyKey() {
     static Entry E{static_cast<clang::pseudo::SymbolID>(-1), 0,
                    clang::pseudo::LRTable::Action::sentinel()};

 namespace clang {
 namespace pseudo {
 
 struct LRTable::Builder {
   std::vector<std::pair<SymbolID, StateID>> StartStates;
   llvm::DenseSet<Entry> Entries;
   llvm::DenseMap<StateID, llvm::SmallSet<RuleID, 4>> Reduces;
   std::vector<llvm::DenseSet<SymbolID>> FollowSets;
+  std::vector<LRGraph::Recovery> Recoveries;
 
   LRTable build(unsigned NumStates) && {
     // E.g. given the following parsing table with 3 states and 3 terminals:
     //
     //            a    b     c
     // +-------+----+-------+-+
     // |state0 |    | s0,r0 | |
     // |state1 | acc|       | |
LRTable build(unsigned NumStates) && {
     size_t SortedIndex = 0;
     for (StateID State = 0; State < Table.StateOffset.size(); ++State) {
       Table.StateOffset[State] = SortedIndex;
       while (SortedIndex < Sorted.size() && Sorted[SortedIndex].State == State)
         ++SortedIndex;
     }
     Table.StartStates = std::move(StartStates);
 
+    // Error recovery entries: sort (no dups already), and build offset lookup.
+    llvm::sort(Recoveries,
+               [&](const LRGraph::Recovery &L, const LRGraph::Recovery &R) {
+                 return std::tie(L.Src, L.Result, L.Strategy) <
+                        std::tie(R.Src, R.Result, R.Strategy);
+               });
+    Table.Recoveries.reserve(Recoveries.size());
+    for (const auto &R : Recoveries)
+      Table.Recoveries.push_back({R.Strategy, R.Result});
+    Table.RecoveryOffset = std::vector<uint32_t>(NumStates + 1, 0);
+    SortedIndex = 0;
+    for (StateID State = 0; State < NumStates; ++State) {
+      Table.RecoveryOffset[State] = SortedIndex;
+      while (SortedIndex < Recoveries.size() &&
+             Recoveries[SortedIndex].Src == State)
+        SortedIndex++;
+    }
+    Table.RecoveryOffset[NumStates] = SortedIndex;
+    assert(SortedIndex == Recoveries.size());
+
     // Compile the follow sets into a bitmap.
     Table.FollowSets.resize(tok::NUM_TOKENS * FollowSets.size());
     for (SymbolID NT = 0; NT < FollowSets.size(); ++NT)
       for (SymbolID Follow : FollowSets[NT])
         Table.FollowSets.set(NT * tok::NUM_TOKENS + symbolToToken(Follow));
 
     // Store the reduce actions in a vector partitioned by state.
     Table.ReduceOffset.reserve(NumStates + 1);
LRTable build(unsigned NumStates) && {
     }
     Table.ReduceOffset.push_back(Table.Reduces.size());
 
     return Table;
   }
 };
 
 LRTable LRTable::buildForTests(const Grammar &G, llvm::ArrayRef<Entry> Entries,
-                               llvm::ArrayRef<ReduceEntry> Reduces) {
+                               llvm::ArrayRef<ReduceEntry> Reduces,
+                               llvm::ArrayRef<RecoveryEntry> Recoveries) {
   StateID MaxState = 0;
   for (const auto &Entry : Entries) {
     MaxState = std::max(MaxState, Entry.State);
     if (Entry.Act.kind() == LRTable::Action::Shift)
       MaxState = std::max(MaxState, Entry.Act.getShiftState());
     if (Entry.Act.kind() == LRTable::Action::GoTo)
       MaxState = std::max(MaxState, Entry.Act.getGoToState());
   }
   Builder Build;
   Build.Entries.insert(Entries.begin(), Entries.end());
   for (const ReduceEntry &E : Reduces)
     Build.Reduces[E.State].insert(E.Rule);
   Build.FollowSets = followSets(G);
+  for (const auto &R : Recoveries)
+    Build.Recoveries.push_back({R.State, R.Strategy, R.Result});
   return std::move(Build).build(/*NumStates=*/MaxState + 1);
 }
 
 LRTable LRTable::buildSLR(const Grammar &G) {
   auto Graph = LRGraph::buildLR0(G);
   Builder Build;
   Build.StartStates = Graph.startStates();
+  Build.Recoveries = Graph.recoveries();
   for (const auto &T : Graph.edges()) {
     Action Act = isToken(T.Label) ? Action::shift(T.Dst) : Action::goTo(T.Dst);
     Build.Entries.insert({T.Src, T.Label, Act});
   }
   Build.FollowSets = followSets(G);
   assert(Graph.states().size() <= (1 << StateBits) &&
          "Graph states execceds the maximum limit!");
   // Add reduce actions.

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

 // RUN: clang-pseudo -grammar=%cxx-bnf-file -source=%s --print-forest | FileCheck %s
 class Foo {
 public:
 };
-// CHECK:      decl-specifier-seq~class-specifier := class-head { member-specification }
+// CHECK:      decl-specifier-seq~class-specifier := class-head { member-specification [recover=1] }
 // 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
+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

 //===--- 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/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"
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
   return OS;
 }
 
 namespace {
 
 using Action = LRTable::Action;
 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));
 }
 
 class GLRTest : public ::testing::Test {
TEST_F(GLRTest, ReduceJoiningWithMultipleBases) {
   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 *GSSNode3 = GSStack.addNode(
+      /*State=*/3, /*ForestNode=*/ClassNameNode,
   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 Table = LRTable::buildForTests(
       G,
       {
EXPECT_THAT(Heads,
                                           parents(Root))));
 
   // When the lookahead is -, reduce is not performed.
   Heads = {GSSNode1};
   glrReduce(Heads, tokenSymbol(tok::minus), {G, Table, Arena, GSStack});
   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"}, {});
+  LRTable Table = LRTable::buildForTests(
+      G, {{/*State=*/1, id("word"), Action::goTo(3)}}, /*Reduce=*/{},
+      /*Recovery=*/{{/*State=*/1, RecoveryStrategy::Braces, id("word")}});
+
+  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, {G, Table, Arena, GSStack},
+             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,
+             {G, Table, Arena, GSStack}, 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"}, {});
+  LRTable Table = LRTable::buildForTests(
+      G, {{/*State=*/1, id("body"), Action::goTo(2)}}, /*Reduce=*/{},
+      /*Recovery=*/{{/*State=*/1, RecoveryStrategy::Braces, id("body")}});
+
+  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, {G, Table, Arena, GSStack}, 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"}, {});
+  LRTable Table = LRTable::buildForTests(
+      G,
+      {
+          {/*State=*/1, id("number"), Action::goTo(2)},
+          {/*State=*/1, id("word"), Action::goTo(3)},
+      },
+      /*Reduce=*/{},
+      /*Recovery=*/
+      {
+          {/*State=*/1, RecoveryStrategy::Braces, id("number")},
+          {/*State=*/1, RecoveryStrategy::Braces, id("word")},
+      });
+  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, {G, Table, Arena, GSStack},
+             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))));
+}
+
+// FIXME: Add a test for the spurious recovery mentioned in glrRecovery()
+// once we can extend the recovery strategies to do so.
+
 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`.
TEST_F(GLRTest, GLRReduceOrder) {
   EXPECT_EQ(Parsed.dumpRecursive(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
+
+    block := { block }
+    block := { numbers }
+    numbers := NUMERIC_CONSTANT NUMERIC_CONSTANT
+  )bnf");
+  auto LRTable = LRTable::buildSLR(G);
+  clang::LangOptions LOptions;
+  TokenStream Tokens = cook(lex("{ { 42 ? } }", LOptions), LOptions);
+  pairBrackets(Tokens);
+
+  const ForestNode &Parsed =
+      glrParse(Tokens, {G, LRTable, Arena, GSStack}, id("block"));
+  EXPECT_EQ(Parsed.dumpRecursive(G),
+            "[  0, end) block := { block [recover=1] }\n"
+            "[  0,   1) ├─{ := tok[0]\n"
+            "[  1,   5) ├─block := <ambiguous>\n"
+            "[  1,   5) │ ├─block := { block [recover=1] }\n"
+            "[  1,   2) │ │ ├─{ := tok[1]\n"
+            "[  2,   4) │ │ ├─block := <opaque>\n"
+            "[  4,   5) │ │ └─} := tok[4]\n"
+            "[  1,   5) │ └─block := { numbers [recover=1] }\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(
     _ := test
 
     test := IDENTIFIER test
     test := IDENTIFIER
   )bnf");
   clang::LangOptions LOptions;