[pseudo] Sort nonterminals based on their reduction order.

[hokein]

Summary

Reductions need to be performed in a careful order in GLR parser, to
make sure we gather all alternatives before creating an ambigous forest
node.

This patch encodes the nonterminal order into the rule id, so that we
can efficiently to determinal ordering of reductions in GLR parser.

This patch also abstracts to a TestGrammar, which is shared among tests.

This is a part of the GLR parser, https://reviews.llvm.org/D121368,
https://reviews.llvm.org/D121150

[hokein]

some tweaks.

[sammccall]

I think my main suggestion is to sort the symbols, not just the rules.
Having the rules in blocks grouped by the symbol they produce, but not in symbol order, seems confusing to reason about.

The extraction of TestGrammar seems unrelated to the rest of the patch and it *isn't* actually shared between tests yet, which makes it a bit hard to review.

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

167–168

I think it's easier to understand if we sort the *symbols* and leave this comment as-is.
It feels a bit strange to sort the symbols alphabetically but sort the rules by some other property of the symbols.

It's also important to describe what relation we're sorting by!

I'd say "The symbols are topologically sorted: if S := T then S has a higher SymbolID than T."

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

56

You could identify dependencies here, and then use them to sort the uniquenonterminals before allocating SymbolIDs

122

The map seems unneccesary - just a vector<pair<SymbolID, SymbolID>> Dependencies, and sort them?

135

(is a vector of symbol id, or of states?)

clang-tools-extra/pseudo/unittests/TestGrammar.h

18 ↗

(On Diff #417567)

doc

26 ↗

(On Diff #417567)

I think this puts too much to much emphasis on the "single" and breaks the symmetry with "symbol" - i'd prefer just "ruleFor".

(The failure mode here is just that the test crashes 100% of the time, so the risk seems low)

28 ↗

(On Diff #417567)

shouldn't these be private, or have better names, and docs when they're set etc?

[sammccall]

In D122303#3402375, @sammccall wrote:

I think my main suggestion is to sort the symbols, not just the rules.
Having the rules in blocks grouped by the symbol they produce, but not in symbol order, seems confusing to reason about.

We discussed this offline - having alphabetical symbol IDs is certainly nice, and there's no hard technical reason to give rules and symbols the same order.

I've come around to the (surprising!) approach in this patch, and just think we should document it so it's less surprising.

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

167–168

Revised suggestion:

RuleID is an index into this array of rule definitions.

Rules with the same target symbol (LHS) are grouped into a single range.
The relative order of different target symbols is *not* by SymbolID, but
rather a topological sort: if S := T then the rules producing T have lower
RuleIDs than rules producing S.
(This strange order simplifies the LR parser: for a given token range, if
we reduce in increasing RuleID order then we need never backtrack -
prerequisite reductions are reached before dependent ones).

[hokein]

address comments, remove the extraction of TestGrammar.

[hokein]

In D122303#3402375, @sammccall wrote:

The extraction of TestGrammar seems unrelated to the rest of the patch and it *isn't* actually shared between tests yet, which makes it a bit hard to review.

It is used in our previous Forest patch (not landed yet), but you're probably right. I have removed the extraction code in this patch, will send out a followup patch for the extraction afterwards.

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

56

not sure I get the your point -- we could move the topological sort here, but it doesn't seem to be significantly better compared with the current solution.

135

oops, it should be the enum State

[sammccall]

Nice!

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

56

(This related to the suggestion of sorting *symbols*, in which case you want to do it based on the specs, before assigning symbol IDs. It's obsolete now)

92–97

I'd call the variable SymbolOrder - once we've computed the order and decided to use it for symbols, it's no longer locally relevant that it's topological

105

You don't need TopologicalOrder[] wrapping both, just compare symbol IDs?

119

This explanation is a bit confusing, because it refers to a second array doesn't exist and never will.

Maybe "This function returns the sort key for each symbol, the array is indexed by SymbolID."

(I think we're actually returning the inverse of the chosen permutation, but that's not a helpful explanation :-)

142

The grammar contains a cycle involving symbol {0}?

147

this is more tersely llvm::lower_bound(Dependencies, {SID, 0}), making use of the fact that std::less will do what we want

And with the inline lambda is gone, it seems more idiomatic as a for loop:

for (auto It = llvm::lower_bound(...); It != Dependencies.end() && It->first == SID; ++It)
  DFS(It->second);

156

Instead of building up the permutation array and then inverting it afterwards, maybe directly Result[SID] = NextKey++; here?

(Having pre-sized the vector)

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

51

nit: maybe "ruleFor() expected a single rule..." to make it clear this isn't a real grammar requirement

53

nit: rule -> rules

[hokein]

address comments.

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

147

thanks, this is a nice suggestion.

156

this is a smart suggestion, but it seems too smart, I find the current way is easier to understand (we first build the top order, and revert it secondly).

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

struct Nonterminal {
     std::string Name;
     // Corresponding rules that construct the nonterminal, it is a [Start, End)
     // index range of the Rules table.
     struct {
       RuleID Start;
       RuleID End;
     } RuleRange;
   };
 
-  // The rules are sorted (and thus grouped) by target symbol.
-  // RuleID is the index of the vector.
+  // RuleID is an index into this table of rule definitions.
+  //
+  // Rules with the same target symbol (LHS) are grouped into a single range.
+  // The relative order of different target symbols is *not* by SymbolID, but
+  // rather a topological sort: if S := T then the rules producing T have lower
+  // RuleIDs than rules producing S.
+  // (This strange order simplifies the GLR parser: for a given token range, if
+  // we reduce in increasing RuleID order then we need never backtrack --
+  // prerequisite reductions are reached before dependent ones).
   std::vector<Rule> Rules;
   // A table of terminals (aka tokens). It corresponds to the clang::Token.
   // clang::tok::TokenKind is the index of the table.
   llvm::ArrayRef<std::string> Terminals;
   // A table of nonterminals, sorted by name.
   // SymbolID is the index of the table.
   std::vector<Nonterminal> Nonterminals;
 };
 
 } // namespace pseudo
 } // namespace clang
 
 #endif // CLANG_PSEUDO_GRAMMAR_H

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

 //===--- GrammarBNF.cpp - build grammar from BNF files  ----------*- 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.h"
 #include "clang/Basic/TokenKinds.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/FormatVariadic.h"
 #include <memory>
+#include <utility>
 
 namespace clang {
 namespace pseudo {
 
 namespace {
 static const llvm::StringRef OptSuffix = "_opt";
 static const llvm::StringRef StartSymbol = "_";
 
std::unique_ptr<Grammar> build(llvm::StringRef BNF) {
     llvm::DenseSet<llvm::StringRef> UniqueNonterminals;
     llvm::DenseMap<llvm::StringRef, SymbolID> SymbolIds;
     for (uint16_t I = 0; I < NumTerminals; ++I)
       SymbolIds.try_emplace(T->Terminals[I], tokenSymbol(tok::TokenKind(I)));
     auto Consider = [&](llvm::StringRef Name) {
       if (!SymbolIds.count(Name))
         UniqueNonterminals.insert(Name);
     };
     for (const auto &Spec : Specs) {
       Consider(Spec.Target);
       for (const RuleSpec::Element &Elt : Spec.Sequence)
         Consider(Elt.Symbol);
     }
     llvm::for_each(UniqueNonterminals, [&T](llvm::StringRef Name) {
       T->Nonterminals.emplace_back();
       T->Nonterminals.back().Name = Name.str();
     });
for (const auto &Spec : Specs) {
       assert(Spec.Sequence.size() <= Rule::MaxElements);
       Symbols.clear();
       for (const RuleSpec::Element &Elt : Spec.Sequence)
         Symbols.push_back(Lookup(Elt.Symbol));
       T->Rules.push_back(Rule(Lookup(Spec.Target), Symbols));
     }
     assert(T->Rules.size() < (1 << RuleBits) &&
            "Too many rules to fit in RuleID bits!");
-    llvm::sort(T->Rules, [](const Rule &Left, const Rule &Right) {
-      // Sorted by the Target.
-      return std::tie(Left.Target, Left.Size) <
-             std::tie(Right.Target, Right.Size);
+    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];
         });
-    RuleID RulePos = 0;
     for (SymbolID SID = 0; SID < T->Nonterminals.size(); ++SID) {
-      RuleID Start = RulePos;
-      while (RulePos < T->Rules.size() && T->Rules[RulePos].Target == SID)
-        ++RulePos;
-      T->Nonterminals[SID].RuleRange = {Start, RulePos};
+      auto StartIt = llvm::partition_point(T->Rules, [&](const Rule &R) {
+        return SymbolOrder[R.Target] < SymbolOrder[SID];
+      });
+      RuleID Start = StartIt - T->Rules.begin();
+      RuleID End = Start;
+      while (End < T->Rules.size() && T->Rules[End].Target == SID)
+        ++End;
+      T->Nonterminals[SID].RuleRange = {Start, End};
     }
     auto G = std::make_unique<Grammar>(std::move(T));
     diagnoseGrammar(*G);
     return G;
   }
 
+  // Gets topological order for nonterminal symbols.
+  //
+  // The topological order is defined as: if a *single* nonterminal A produces
+  // (or transitively) a nonterminal B (that said, there is a production rule
+  // B := A), then A is less than B.
+  //
+  // It returns the sort key for each symbol, the array is indexed by SymbolID.
+  std::vector<unsigned> getTopologicalOrder(GrammarTable *T) {
+    std::vector<std::pair<SymbolID, SymbolID>> Dependencies;
+    for (const auto &Rule : T->Rules) {
+      // if A := B, A depends on B.
+      if (Rule.Size == 1 && pseudo::isNonterminal(Rule.Sequence[0]))
+        Dependencies.push_back({Rule.Target, Rule.Sequence[0]});
+    }
+    llvm::sort(Dependencies);
+    std::vector<SymbolID> Order;
+    // Each nonterminal state flows: NotVisited -> Visiting -> Visited.
+    enum State {
+      NotVisited,
+      Visiting,
+      Visited,
+    };
+    std::vector<State> VisitStates(T->Nonterminals.size(), NotVisited);
+    std::function<void(SymbolID)> DFS = [&](SymbolID SID) -> void {
+      if (VisitStates[SID] == Visited)
+        return;
+      if (VisitStates[SID] == Visiting) {
+        Diagnostics.push_back(
+            llvm::formatv("The grammar contains a cycle involving symbol {0}",
+                          T->Nonterminals[SID].Name));
+        return;
+      }
+      VisitStates[SID] = Visiting;
+      for (auto It = llvm::lower_bound(Dependencies,
+                                       std::pair<SymbolID, SymbolID>{SID, 0});
+           It != Dependencies.end() && It->first == SID; ++It)
+        DFS(It->second);
+      VisitStates[SID] = Visited;
+      Order.push_back(SID);
+    };
+    for (SymbolID ID = 0; ID != T->Nonterminals.size(); ++ID)
+      DFS(ID);
+    std::vector<unsigned> Result(T->Nonterminals.size(), 0);
+    for (size_t I = 0; I < Order.size(); ++I)
+      Result[Order[I]] = I;
+    return Result;
+  }
+
 private:
   // Text representation of a BNF grammar rule.
   struct RuleSpec {
     llvm::StringRef Target;
     struct Element {
       llvm::StringRef Symbol; // Name of the symbol
     };
     std::vector<Element> Sequence;

clang-tools-extra/pseudo/test/lr-build-basic.test

 # TABLE-NEXT:     'IDENTIFIER': shift state 3
 # TABLE-NEXT:     'expr': go to state 1
 # TABLE-NEXT:     'id': go to state 2
 # TABLE-NEXT: State 1
 # TABLE-NEXT:     'EOF': accept
 # TABLE-NEXT: State 2
 # TABLE-NEXT:     'EOF': reduce by rule 1 'expr := id'
 # TABLE-NEXT: State 3
-# TABLE-NEXT:     'EOF': reduce by rule 2 'id := IDENTIFIER'
+# TABLE-NEXT:     'EOF': reduce by rule 0 'id := IDENTIFIER'

clang-tools-extra/pseudo/test/lr-build-conflicts.test

 _ := expr
 expr := expr - expr  # S/R conflict at state 4 on '-' token
 expr := IDENTIFIER
 
 # RUN: clang-pseudo -grammar %s -print-graph | FileCheck %s --check-prefix=GRAPH
 #      GRAPH: States
 # GRAPH-NEXT: State 0
-# GRAPH-NEXT:     _ :=  • expr
 # GRAPH-NEXT:     expr :=  • expr - expr
+# GRAPH-NEXT:     _ :=  • expr
 # GRAPH-NEXT:     expr :=  • IDENTIFIER
 # GRAPH-NEXT: State 1
 # GRAPH-NEXT:     _ := expr • 
 # GRAPH-NEXT:     expr := expr • - expr
 # GRAPH-NEXT: State 2
 # GRAPH-NEXT:     expr := IDENTIFIER • 
 # GRAPH-NEXT: State 3
 # GRAPH-NEXT:     expr :=  • expr - expr

 # TABLE-NEXT:     '-': shift state 3
 # TABLE-NEXT: State 2
 # TABLE-NEXT:     'EOF': reduce by rule 1 'expr := IDENTIFIER'
 # TABLE-NEXT:     '-': reduce by rule 1 'expr := IDENTIFIER'
 # TABLE-NEXT: State 3
 # TABLE-NEXT:     'IDENTIFIER': shift state 2
 # TABLE-NEXT:     'expr': go to state 4
 # TABLE-NEXT: State 4
-# TABLE-NEXT:     'EOF': reduce by rule 2 'expr := expr - expr'
+# TABLE-NEXT:     'EOF': reduce by rule 0 'expr := expr - expr'
 # TABLE-NEXT:     '-': shift state 3
-# TABLE-NEXT:     '-': reduce by rule 2 'expr := expr - expr'
+# TABLE-NEXT:     '-': reduce by rule 0 'expr := expr - expr'

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

for (unsigned I = 0; I < NumTerminals; ++I)
         return tokenSymbol(static_cast<tok::TokenKind>(I));
     for (SymbolID ID = 0; ID < G->table().Nonterminals.size(); ++ID)
       if (G->table().Nonterminals[ID].Name == Name)
         return ID;
     ADD_FAILURE() << "No such symbol found: " << Name;
     return 0;
   }
 
+  RuleID ruleFor(llvm::StringRef NonterminalName) const {
+    auto RuleRange = G->table().Nonterminals[id(NonterminalName)].RuleRange;
+    if (RuleRange.End - RuleRange.Start == 1)
+      return G->table().Nonterminals[id(NonterminalName)].RuleRange.Start;
+    ADD_FAILURE() << "Expected a single rule for " << NonterminalName
+                  << ", but it has " << RuleRange.End - RuleRange.Start
+                  << " rule!\n";
+    return 0;
+  }
+
 protected:
   std::unique_ptr<Grammar> G;
   std::vector<std::string> Diags;
 };
 
 TEST_F(GrammarTest, Basic) {
   build("_ := IDENTIFIER + _ # comment");
   EXPECT_THAT(Diags, IsEmpty());
TEST_F(GrammarTest, EliminatedOptional) {
   EXPECT_THAT(Diags, IsEmpty());
   EXPECT_THAT(G->table().Rules,
               UnorderedElementsAre(Sequence(id("INT")),
                                    Sequence(id("CONST"), id("INT")),
                                    Sequence(id("CONST"), id("INT"), id(";")),
                                    Sequence(id("INT"), id(";"))));
 }
 
+TEST_F(GrammarTest, RuleIDSorted) {
+  build(R"bnf(
+    _ := x
+
+    x := y
+    y := z
+    z := IDENTIFIER
+  )bnf");
+  ASSERT_TRUE(Diags.empty());
+
+  EXPECT_LT(ruleFor("z"), ruleFor("y"));
+  EXPECT_LT(ruleFor("y"), ruleFor("x"));
+  EXPECT_LT(ruleFor("x"), ruleFor("_"));
+}
+
 TEST_F(GrammarTest, Diagnostics) {
   build(R"cpp(
     _ := ,_opt
     _ := undefined-sym
     null :=
     _ := IDENFIFIE # a typo of the terminal IDENFITIER
 
     invalid
+    # cycle
+    a := b
+    b := a
   )cpp");
 
   EXPECT_EQ(G->startSymbol(), id("_"));
   EXPECT_THAT(Diags, UnorderedElementsAre(
                          "Rule '_ := ,_opt' has a nullable RHS",
                          "Rule 'null := ' has a nullable RHS",
                          "No rules for nonterminal: undefined-sym",
                          "Failed to parse 'invalid': no separator :=",
                          "Token-like name IDENFIFIE is used as a nonterminal",
-                         "No rules for nonterminal: IDENFIFIE"));
+                         "No rules for nonterminal: IDENFIFIE",
+                         "The grammar contains a cycle involving symbol a"));
 }
 
 TEST_F(GrammarTest, FirstAndFollowSets) {
   build(
       R"bnf(
 _ := expr
 expr := expr - term
 expr := term