[pseudo] Add recovery for declarations

[hokein]

Summary

• declaration recovery strategy: search for likely declaration boundaries
• change decl-sequence to right-recursive to simplify this
• also use for class members (already right-recursive)
• refactor recovery strategy to use struct parameter and expose cursor position

[sammccall]

This may well need refinement & more testing, interested in initial thoughts

[hokein]

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

267

I think this excludes the parameter-declaration (from the grammar spec, it is a different nonterminal).

267

The logic of implementations looks very solid. I think it would be good to have some unittests for it.

282

if I read the code correctly, the following case should work like

void foo() {}

LLVM_DISCARD int bar() {} // this is an opaque `declaration` node?

void foo2() {} // it won't work if we change void -> Foo.

291

the list looks reasonable -- I think we can lookup the Follow(declaration) set to find more.

301

maybe consider tok::identifier (if the identifier is a type specifier, it is a good indicator of a declaration starting) as well? And yeah, we're less certain about it, but since we use the indentation information, I guess it might probably work well?

352

I think we miss to check the return index >= Cursor here.

clang-tools-extra/pseudo/lib/cxx/cxx.bnf

313

Just want to spell out, this causes a performance hit :(
(a pure change of this has a ~6% slowdown, 7.17 MB/s -> 6.7MB/s on SemaCodeComplete.cpp).

left-cursive grammar is more friendly to LR-like parsers, because the parser can do the reduction earlier (after a parsed a declaration, we can perform a declaration-seq reduce); while right-cursive grammar, the reduction starts from the last declaration (this means our GSS is more deeper).

change decl-sequence to right-recursive to simplify this

I remembered we discussed this bit before, but I don't really remember the details now :(

clang-tools-extra/pseudo/test/cxx/recovery-declarations.cpp

6

nit: add some tests to cover the initializer, e.g.

auto lambda = [] xxxx () xxx {};

[hokein]

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

333

P.Tokens.tokens()[P.Begin].next() doesn't seem like correct, we should start with P.Tokens.tokens()[P.Begin], otherwise we will ignore the first token,

example:

namespace XXXX {
}
foo foo;

342

we should return index() +1

347

the same, +1.

[hokein]

I'm going to pick this up.

[hokein]

• rebase, fixed a few conflicts
• address comments
• fix some bugs
• restructure the code, moving the implementation to a separate file
• add unittests for recoveryNextDeclaration
• keep the left-recursive declaration-seq grammar rule to void performance regression

[hokein]

I think the current version should be good to review, some bits need to take care of:

• left-recursive vs right-recursive of declaration-seq rule, see my other comments about it. Currently I keep it as-is to avoid the performance regression on large files (I still don't see your point how right-recursive can simplify the error recovery, it seems to me either can work at least for this case)
• recoveryNextDeclaration will consume at least 1 token (the return token index > Cursor) to avoid the risk of running in an infinite loop
• I keep the original implementation as-is (except fixing some bugs), but IMO T->Indent == OrigIndent && LikelyStartsDeclaration(T->Kind) is too strict (see my FIXME testcases), and we should probably include the IDENTIFIER (I believe it is a common case), LikelyStartsDeclaration(T->Kind) || (T->Kind = IDENTIFIER && T->Indent == OrigIndent) might be better.

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

291

added more: kw_friend, kw_inline, kw_explicit, kw_virtual.

clang-tools-extra/pseudo/lib/cxx/cxx.bnf

313

Got more data, it does hurt the performance on large files:

SemaExpr.cpp: 9.54MB/s -> 7.98MB/s
SemaDeclCXX.cpp: 10.16MB/s -> 9.25MB/s

small/medium files doesn't seem to be affected (hypothesis: these files has less declarations than large files, thus being less affected by the right-recursive declaration-seq grammar rule)

Hover.cpp: 8MB/s -> 7.92MB/s
ASTSignals.cpp: 12.34M/s -> 12.29MB/s

[hokein]

Fix a bug caused by my change, and add test.

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

 //
 // 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(const GuardParams &)>;
 
+struct RecoveryParams {
+  // The position in the stream where the node being recovered will start.
+  Token::Index Begin;
+  // The position in the stream where the parse failed.
+  // Begin <= Cursor <= End (for a valid recovery).
+  Token::Index Cursor;
+  const TokenStream &Tokens;
+};
 // 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 &)>;
+    llvm::function_ref<Token::Index(const RecoveryParams &)>;
 
 // Specify a language that can be parsed by the pseduoparser.
 struct Language {
   Grammar G;
   LRTable Table;
 
   // Binding extension ids to corresponding implementations.
   llvm::DenseMap<RuleID, RuleGuard> Guards;

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

template <class T> void setFlag(T Mask) {
     Flags |= uint8_t{static_cast<std::underlying_type_t<T>>(Mask)};
   }
 
   /// Returns the next token in the stream. this may not be a sentinel.
   const Token &next() const {
     assert(Kind != tok::eof);
     return *(this + 1);
   }
+  /// Returns the previous token in the stream. this may not be a sentinel.
+  const Token &prev() const {
+    assert(Kind != tok::eof);
+    return *(this - 1);
+  }
   /// Returns the next token in the stream, skipping over comments.
   const Token &nextNC() const {
     const Token *T = this;
     do
       T = &T->next();
     while (T->Kind == tok::comment);
     return *T;
   }

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

 
 #define DEBUG_TYPE "GLR.cpp"
 
 namespace clang {
 namespace pseudo {
 namespace {
 
 Token::Index findRecoveryEndpoint(ExtensionID Strategy, Token::Index Begin,
+                                  Token::Index Cursor,
                                   const TokenStream &Tokens,
                                   const Language &Lang) {
   assert(Strategy != 0);
-  assert(Begin > 0);
   if (auto S = Lang.RecoveryStrategies.lookup(Strategy))
-    return S(Begin, Tokens);
+    return S({Begin, Cursor, Tokens});
   return Token::Invalid;
 }
 
 } // namespace
 
 void glrRecover(llvm::ArrayRef<const GSS::Node *> OldHeads,
                 unsigned &TokenIndex, const ParseParams &Params,
                 const Language &Lang,
void glrRecover(llvm::ArrayRef<const GSS::Node *> OldHeads,
   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.Position,
-                                    Params.Code, Lang);
+                                    TokenIndex, 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/cxx/CXX.cpp

return {
        TOKEN_GUARD(numeric_constant, numKind(Tok) == Integer)},
       {(RuleID)Rule::floating_point_literal_0numeric_constant,
        TOKEN_GUARD(numeric_constant, numKind(Tok) == Floating)},
   };
 #undef TOKEN_GUARD
 #undef SYMBOL_GUARD
 }
 
-Token::Index recoverBrackets(Token::Index Begin, const TokenStream &Tokens) {
-  assert(Begin > 0);
-  const Token &Left = Tokens.tokens()[Begin - 1];
+Token::Index recoverBrackets(const RecoveryParams &P) {
+  assert(P.Begin > 0);
+  const Token &Left = P.Tokens.tokens()[P.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 - 1);
-    return Tokens.index(*Right);
+    assert(P.Tokens.index(*Right) > P.Begin - 1);
+    return P.Tokens.index(*Right);
   }
   return Token::Invalid;
 }
 
+Token::Index recoverNextDeclaration(const RecoveryParams &P) {
+  if (P.Begin == P.Tokens.tokens().size())
+    return Token::Invalid;
+
+  // Declarations that don't end in semicolons:
+  //   function-definition
+  //   EXPORT {...}
+  //   EXTERN string-literal {...}
+  //   INLINE_opt NAMESPACE IDENTIFIER {...}
+  //   INLINE_opt NAMESPACE {...}
+  //   NAMESPACE enclosing-namespace-specifier :: INLINE_opt IDENTIFIER {...}
+  // Functions are hard to do anything about:
+  //  - if the declarator is good and the braces are present, parsing succeeds
+  //  - if the declarator is bad, it's hard to know it's a function
+  //  - if the braces are missing, we don't know where to recover
+  // So We only try to detect the others.
+  bool AcceptBraces = false;
+  auto ConsiderForBraces = [&](tok::TokenKind K) {
+    if (K == tok::kw_export || K == tok::kw_extern || K == tok::kw_namespace)
+      AcceptBraces = true;
+  };
+
+  // Some tokens are pretty good indicators of a declaration starting, when
+  // they appear at the beginning of a line.
+  auto LikelyStartsDeclaration = [&](tok::TokenKind K) -> bool {
+    switch (K) {
+    // Things you might be declaring.
+    case tok::kw_template:
+    case tok::kw_using:
+    case tok::kw_namespace:
+    case tok::kw_typedef:
+    case tok::kw_class:
+    case tok::kw_struct:
+    case tok::kw_union:
+    // Types & other decl-specifiers
+    case tok::kw_void:
+    case tok::kw_auto:
+    case tok::kw_int:
+    case tok::kw_char:
+    case tok::kw_float:
+    case tok::kw_double:
+    case tok::kw_long:
+    case tok::kw_signed:
+    case tok::kw_unsigned:
+    case tok::kw_const:
+    case tok::kw_volatile:
+    case tok::kw_static:
+    case tok::kw_extern:
+    // Modules
+    case tok::kw_import:
+    case tok::kw_export:
+    // Class protection
+    case tok::kw_public:
+    case tok::kw_private:
+    case tok::kw_protected:
+      return true;
+    default:
+      return false;
+    }
+  };
+
+  // The indentation level where the declaration started hints at where a new
+  // sibling declaration might start.
+  unsigned OrigIndent = P.Tokens.tokens()[P.Begin].Indent;
+
+  // Walk over tokens at the appropriate bracket nesting level.
+  for (const Token *T = &P.Tokens.tokens()[P.Begin].next(); T->Kind != tok::eof;
+       T = &T->next()) {
+    // Handle (paired) brackets.
+    if (const Token *B = T->pair()) {
+      // Closing bracket not paired within the recovery range.
+      if (B < T) {
+        assert(P.Tokens.index(*B) < P.Begin && "Why didn't we skip this one?");
+        assert(P.Tokens.index(*T) >= P.Cursor &&
+               "How did we parse an unmatched closing bracket?!");
+        return P.Tokens.index(*T);
+      }
+      // Opening bracket: is this a semicolonless statement?
+      if (T->Kind == tok::l_brace && AcceptBraces &&
+          P.Tokens.index(*B) >= P.Cursor)
+        return P.Tokens.index(*B);
+      // Skip over opening/closing bracket pair.
+      T = B;
+      continue;
+    }
+
+    // Semicolons terminate statements.
+    if (T->Kind == tok::semi)
+      return P.Tokens.index(*T) + 1;
+    ConsiderForBraces(T->Kind);
+
+    // Stop if it looks like a new declaration is starting on the next line.
+    if (T->Indent == OrigIndent && T->Line != T->prev().Line &&
+        LikelyStartsDeclaration(T->Kind))
+      return P.Tokens.index(*T);
+  }
+  // If we reached EOF, then assume the declaration runs right to EOF.
+  return P.Tokens.tokens().size();
+}
+
 llvm::DenseMap<ExtensionID, RecoveryStrategy> buildRecoveryStrategies() {
   return {
       {(ExtensionID)Extension::Brackets, recoverBrackets},
+      {(ExtensionID)Extension::NextDeclaration, recoverNextDeclaration},
   };
 }
 
 } // namespace
 
 const Language &getLanguage() {
   static const auto &CXXLanguage = []() -> const Language & {
     std::vector<std::string> Diags;

clang-tools-extra/pseudo/lib/cxx/cxx.bnf

 jump-statement := CONTINUE ;
 jump-statement := RETURN expr-or-braced-init-list_opt ;
 jump-statement := coroutine-return-statement
 jump-statement := GOTO IDENTIFIER ;
 coroutine-return-statement := CO_RETURN expr-or-braced-init-list_opt ;
 declaration-statement := block-declaration
 
 # gram.dcl
-declaration-seq := declaration
-declaration-seq := declaration-seq declaration
+declaration-seq := declaration [recover=NextDeclaration] declaration-seq_opt
 declaration := block-declaration
 declaration := nodeclspec-function-declaration
 declaration := function-definition
 declaration := template-declaration
 declaration := deduction-guide
 declaration := explicit-instantiation
 declaration := explicit-specialization
 declaration := export-declaration

 linkage-specification := EXTERN string-literal declaration
 
 # gram.module
 module-declaration := export-keyword_opt module-keyword module-name module-partition_opt ;
 module-name := module-name-qualifier_opt IDENTIFIER
 module-partition := : module-name-qualifier_opt IDENTIFIER
 module-name-qualifier := IDENTIFIER .
 module-name-qualifier := module-name-qualifier IDENTIFIER .
-export-declaration := EXPORT declaration
-export-declaration := EXPORT ( declaration-seq_opt )
+export-declaration := EXPORT { declaration-seq_opt }
 export-declaration := export-keyword module-import-declaration
-module-import-declaration := import-keyword module-name
-module-import-declaration := import-keyword module-partition
+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
+# 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 [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
+member-specification := member-declaration [recover=NextDeclaration] member-specification_opt
 member-specification := access-specifier : member-specification_opt
 member-declaration := decl-specifier-seq_opt member-declarator-list_opt ;
 member-declaration := function-definition
 member-declaration := using-declaration
 member-declaration := using-enum-declaration
 member-declaration := static_assert-declaration
 member-declaration := template-declaration
 member-declaration := explicit-specialization

clang-tools-extra/pseudo/test/cxx/recovery-declarations.cpp

+// RUN: clang-pseudo -grammar=cxx -source=%s --print-forest | FileCheck %s
+
+this is not a valid declaration;
+// CHECK: declaration := <opaque>
+
+int x[0];
+// CHECK:      simple-declaration := decl-specifier-seq init-declarator-list ;
+// CHECK-NEXT: ├─decl-specifier-seq~INT := tok[7]
+// CHECK-NEXT: ├─init-declarator-list~noptr-declarator := noptr-declarator [ constant-expression ]
+
+also_not_ok ??? @@@ (;
+// CHECK: declaration := <opaque>
+
+class Y{};
+// CHECK:      simple-declaration := decl-specifier-seq ;
+// CHECK-NEXT: ├─decl-specifier-seq~class-specifier := class-head { }
+
+// FIXME: support recovery of incomplete scopes
+// namespace foo {
+
+class class class class function
+// CHECK: declaration := <opaque>

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];
+Token::Index recoverBraces(const RecoveryParams &P) {
+  EXPECT_GT(P.Begin, 0u);
+  const Token &Left = P.Tokens.tokens()[P.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 P.Tokens.index(*Right);
   }
   return Token::Invalid;
 }
 
 class GLRTest : public ::testing::Test {
 public:
   void build(llvm::StringRef GrammarBNF) {
     std::vector<std::string> Diags;