[pseudo] add the spurious left-and-upwads recovery case to unittest.

[sammccall]

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

711

it's not clear to me what this is testing, can you add some documentation?

(also I think "left" is spurious and "up" is correct, so why LeftAndUpwards rather than just left?)

757

this looks correct to me, what's the problem?

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

void glrRecover(llvm::ArrayRef<const GSS::Node *> OldHeads,
   //   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.
-  // FIXME: Add a test for spurious recovery once tests can define strategies.
   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;
     if (!N->Recovered) { // Don't recover the same way twice!
       for (auto Strategy : Lang.Table.getRecovery(N->State)) {
         Options.push_back(PlaceholderRecovery{

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

TEST_F(GLRTest, RepeatedRecovery) {
   EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
             "[  0, end) function := signature body [recover=Skip]\n"
             "[  0,   1) ├─signature := IDENTIFIER params [recover=Skip]\n"
             "[  0,   1) │ ├─IDENTIFIER := tok[0]\n"
             "[  1,   1) │ └─params := <opaque>\n"
             "[  1, end) └─body := <opaque>\n");
 }
 
+TEST_F(GLRTest, SpuriousRecoveryLeftAndUpwardsCase) {
+  build(R"bnf(
+    _ := compound-stmt EOF
+
+    compound-stmt := { stmt-seq [recover=Braces] }
+
+    stmt-seq := stmt
+    stmt-seq := stmt-seq stmt
+
+    stmt := compound-stmt
+    stmt := IF ( expr [recover=Parentheses] ) IDENTIFIER
+    stmt := ;
+  )bnf");
+
+  TestLang.Table = LRTable::buildSLR(TestLang.G);
+  TestLang.RecoveryStrategies.try_emplace(extensionID("Braces"), recoverBraces);
+  TestLang.RecoveryStrategies.try_emplace(
+      extensionID("Parentheses"),
+      [](Token::Index Start, const TokenStream &Code) {
+        assert(Start > 0);
+        const Token &Left = Code.tokens()[Start - 1];
+        assert(Left.Kind == tok::l_paren);
+        if (const auto *Right = Left.pair())
+          return Code.index(*Right);
+        return Token::Invalid;
+      });
+  clang::LangOptions LOptions;
+  TokenStream Tokens = cook(lex(R"cpp(
+   { ;
+     { if (id) ? }
+   }
+  )cpp", LOptions), LOptions);
+  pairBrackets(Tokens);
+
+  const ForestNode &Parsed =
+      glrParse({Tokens, Arena, GSStack}, id("compound-stmt"), TestLang);
+  EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
+            "[  0, end) compound-stmt := { stmt-seq [recover=Braces] }\n"
+            "[  0,   1) ├─{ := tok[0]\n"
+            "[  1,   9) ├─stmt-seq := stmt-seq stmt\n"
+            "[  1,   2) │ ├─stmt-seq := stmt\n"
+            "[  1,   2) │ │ └─stmt := ;\n"
+            "[  1,   2) │ │   └─; := tok[1]\n"
+            "[  2,   9) │ └─stmt := compound-stmt\n"
+            "[  2,   9) │   └─compound-stmt := { stmt-seq [recover=Braces] }\n"
+            "[  2,   3) │     ├─{ := tok[2]\n"
+            "[  3,   8) │     ├─stmt-seq := <opaque>\n"
+            "[  8,   9) │     └─} := tok[8]\n"
+            "[  9, end) └─} := tok[9]\n");
+}
+
 TEST_F(GLRTest, NoExplicitAccept) {
   build(R"bnf(
     _ := test EOF
 
     test := IDENTIFIER test
     test := IDENTIFIER
   )bnf");
   clang::LangOptions LOptions;