[pseudo] Eliminate the dangling-else syntax ambiguity.

[hokein]

Summary

• the grammar ambiguity is eliminate by a guard;
• modify the guard function signatures, now all parameters are folded in to a single object, avoid a long parameter list (as we will add more parameters in the near future);

[sammccall]

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

25

passing the position in the stream would be more general, there's no reason in particular that the amount of lookahead the guard needs is the same as what we have in GLR

OTOH as long as it *is* the same this is probably faster

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

26–27

nit: I would suggest calling this conventionally P instead of Params, the bodies of these are really verbose

clang-tools-extra/pseudo/test/cxx/dangling-else.cpp

4

nit: place this all on one line so it's clear there's no indentation-based heuristics at play?

[hokein]

address comments.

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

25

+1, agree. This'd requires some non-trivial changes in the GLR because we use Lookahead in the Reduce rather than the token stream index. I think it is better to do it in a followup patch. I added a FIXME.

[hokein]

rebase

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

 #include "clang-pseudo/grammar/LRTable.h"
 
 namespace clang {
 namespace pseudo {
 class ForestNode;
 class TokenStream;
 class LRTable;
 
+struct GuardParams {
+  llvm::ArrayRef<const ForestNode *> RHS;
+  const TokenStream &Tokens;
+  // FIXME: use the index of Tokens.
+  SymbolID Lookahead;
+};
 // A guard restricts when a grammar rule can be used.
 //
 // 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(
-    llvm::ArrayRef<const ForestNode *> RHS, const TokenStream &)>;
+using RuleGuard = llvm::function_ref<bool(const GuardParams &)>;
 
 // 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.

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

public:
   }
 
 private:
   bool canReduce(const Rule &R, RuleID RID,
                  llvm::ArrayRef<const ForestNode *> RHS) const {
     if (!R.Guarded)
       return true;
     if (auto Guard = Lang.Guards.lookup(RID))
-      return Guard(RHS, Params.Code);
+      return Guard({RHS, Params.Code, Lookahead});
     LLVM_DEBUG(llvm::dbgs()
                << llvm::formatv("missing guard implementation for rule {0}\n",
                                 Lang.G.dumpRule(RID)));
     return true;
   }
   // pop walks up the parent chain(s) for a reduction from Head by to Rule.
   // Once we reach the end, record the bases and sequences.
   void pop(const GSS::Node *Head, RuleID RID, const Rule &Rule) {

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

 
 namespace clang {
 namespace pseudo {
 namespace cxx {
 namespace {
 static const char *CXXBNF =
 #include "CXXBNF.inc"
     ;
 
 // User-defined string literals look like `""suffix`.
 bool isStringUserDefined(const Token &Tok) {
   return !Tok.text().endswith("\"");
 }
 bool isCharUserDefined(const Token &Tok) { return !Tok.text().endswith("'"); }
 
 // Combinable flags describing numbers.
 // Clang has just one numeric_token kind, the grammar has 4.
 enum NumericKind {
while (true) {
     default:
       assert(false && "unhandled declarator for IsFunction");
       return IsFunction;
     }
   }
   llvm_unreachable("unreachable");
 }
 
+bool guardNextTokenNotElse(const GuardParams &P) {
+  return symbolToToken(P.Lookahead) != tok::kw_else;
+}
+
 llvm::DenseMap<ExtensionID, RuleGuard> buildGuards() {
 #define TOKEN_GUARD(kind, cond)                                                \
-  [](llvm::ArrayRef<const ForestNode *> RHS, const TokenStream &Tokens) {      \
-    const Token &Tok = onlyToken(tok::kind, RHS, Tokens);                      \
+  [](const GuardParams& P) {                                                   \
+    const Token &Tok = onlyToken(tok::kind, P.RHS, P.Tokens);                  \
     return cond;                                                               \
   }
 #define SYMBOL_GUARD(kind, cond)                                               \
-  [](llvm::ArrayRef<const ForestNode *> RHS, const TokenStream &Tokens) {      \
-    const ForestNode &N = onlySymbol((SymbolID)Symbol::kind, RHS, Tokens);     \
+  [](const GuardParams& P) {                                                   \
+    const ForestNode &N = onlySymbol((SymbolID)Symbol::kind, P.RHS, P.Tokens); \
     return cond;                                                               \
   }
   return {
       {(RuleID)Rule::function_declarator_0declarator,
        SYMBOL_GUARD(declarator, isFunctionDeclarator(&N))},
       {(RuleID)Rule::non_function_declarator_0declarator,
        SYMBOL_GUARD(declarator, !isFunctionDeclarator(&N))},
 
       {(RuleID)Rule::contextual_override_0identifier,
        TOKEN_GUARD(identifier, Tok.text() == "override")},
       {(RuleID)Rule::contextual_final_0identifier,
        TOKEN_GUARD(identifier, Tok.text() == "final")},
       {(RuleID)Rule::import_keyword_0identifier,
        TOKEN_GUARD(identifier, Tok.text() == "import")},
       {(RuleID)Rule::export_keyword_0identifier,
        TOKEN_GUARD(identifier, Tok.text() == "export")},
       {(RuleID)Rule::module_keyword_0identifier,
        TOKEN_GUARD(identifier, Tok.text() == "module")},
       {(RuleID)Rule::contextual_zero_0numeric_constant,
        TOKEN_GUARD(numeric_constant, Tok.text() == "0")},
 
+      {(RuleID)Rule::selection_statement_0if_1l_paren_2condition_3r_paren_4statement,
+        guardNextTokenNotElse},
+      {(RuleID)Rule::selection_statement_0if_1constexpr_2l_paren_3condition_4r_paren_5statement,
+        guardNextTokenNotElse},
+
       // The grammar distinguishes (only) user-defined vs plain string literals,
       // where the clang lexer distinguishes (only) encoding types.
       {(RuleID)Rule::user_defined_string_literal_chunk_0string_literal,
        TOKEN_GUARD(string_literal, isStringUserDefined(Tok))},
       {(RuleID)Rule::user_defined_string_literal_chunk_0utf8_string_literal,
        TOKEN_GUARD(utf8_string_literal, isStringUserDefined(Tok))},
       {(RuleID)Rule::user_defined_string_literal_chunk_0utf16_string_literal,
        TOKEN_GUARD(utf16_string_literal, isStringUserDefined(Tok))},

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

 condition := decl-specifier-seq declarator brace-or-equal-initializer
 labeled-statement := IDENTIFIER : statement
 labeled-statement := CASE constant-expression : statement
 labeled-statement := DEFAULT : statement
 expression-statement := expression_opt ;
 compound-statement := { statement-seq_opt [recover=Brackets] }
 statement-seq := statement
 statement-seq := statement-seq statement
-selection-statement := IF CONSTEXPR_opt ( init-statement_opt condition ) statement
+selection-statement := IF CONSTEXPR_opt ( init-statement_opt condition ) statement [guard]
 selection-statement := IF CONSTEXPR_opt ( init-statement_opt condition ) statement ELSE statement
 selection-statement := SWITCH ( init-statement_opt condition ) statement
 iteration-statement := WHILE ( condition ) statement
 iteration-statement := DO statement WHILE ( expression ) ;
 iteration-statement := FOR ( init-statement condition_opt ; expression_opt ) statement
 iteration-statement := FOR ( init-statement_opt for-range-declaration : for-range-initializer ) statement
 for-range-declaration := decl-specifier-seq declarator
 for-range-declaration := decl-specifier-seq ref-qualifier_opt [ identifier-list ]

clang-tools-extra/pseudo/test/cxx/dangling-else.cpp

+// RUN: clang-pseudo -grammar=cxx -source=%s --start-symbol=statement-seq --print-forest | FileCheck %s
+
+// Verify the else should belong to the nested if statement
+if (true) if (true) {} else {}
+
+// CHECK:      statement-seq~selection-statement := IF ( condition ) statement
+// CHECK-NEXT: ├─IF
+// CHECK-NEXT: ├─(
+// CHECK-NEXT: ├─condition~TRUE
+// CHECK-NEXT: ├─)
+// CHECK-NEXT: └─statement~selection-statement
+// CHECK-NEXT:   ├─IF
+// CHECK-NEXT:   ├─(
+// CHECK-NEXT:   ├─condition~TRUE
+// CHECK-NEXT:   ├─)
+// CHECK-NEXT:   ├─statement~compound-statement := { }
+// CHECK-NEXT:   │ ├─{
+// CHECK-NEXT:   │ └─}
+// CHECK-NEXT:   ├─ELSE
+// CHECK-NEXT:   └─statement~compound-statement := { }
+// CHECK-NEXT:     ├─{
+// CHECK-NEXT:     └─}

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

 
 TEST_F(GLRTest, GuardExtension) {
   build(R"bnf(
     _ := start
 
     start := IDENTIFIER [guard]
   )bnf");
   TestLang.Guards.try_emplace(
-      ruleFor("start"),
-      [&](llvm::ArrayRef<const ForestNode *> RHS, const TokenStream &Tokens) {
-        assert(RHS.size() == 1 &&
-               RHS.front()->symbol() == tokenSymbol(clang::tok::identifier));
-        return Tokens.tokens()[RHS.front()->startTokenIndex()].text() == "test";
+      ruleFor("start"), [&](const GuardParams &P) {
+        assert(P.RHS.size() == 1 &&
+               P.RHS.front()->symbol() ==
+                   tokenSymbol(clang::tok::identifier));
+        return P.Tokens.tokens()[P.RHS.front()->startTokenIndex()]
+                   .text() == "test";
       });
   clang::LangOptions LOptions;
   TestLang.Table = LRTable::buildSLR(TestLang.G);
 
   std::string Input = "test";
   const TokenStream &Succeeded = cook(lex(Input, LOptions), LOptions);
   EXPECT_EQ(glrParse({Succeeded, Arena, GSStack}, id("start"), TestLang)
                 .dumpRecursive(TestLang.G),