[pseudo] Implement LRGraph

[hokein]

Summary

LRGraph is the key component of the clang pseudo parser, it is a
deterministic handle-finding finite-state machine, which is used to
generated the LR parsing table.

Separate from https://reviews.llvm.org/D118196.

[sammccall]

LG, thank you!
Bunch of nits, up to you what you want to do with them.

clang/include/clang/Tooling/Syntax/Pseudo/LRGraph.h

10

I think it'd be useful to be a little more concrete here than "find"...

and collect the right-hand side of a production rule (called handle) on top
of the stack, then replace (reduce) the handle with the nonterminal defined
by the production rule.

42

The lack of spaces on the RHS is inconsistent with the debug output, and any examples with real grammars (since we need spaces to split up words).

Can we use A := x y instead?
Or possibly A := X Y which makes the boundaries more obvious when it appears in-line with text.

(I don't have an opinion about A := X . Y vs A := X.Y (dot *replaces* space), but again we should pick one consistent with the debug output.

52

I think the calls to these constructors could be a little clearer as factories that describe their purpose:

e.g.

static Item start(RuleID ID, const Grammar &G);
static Item sentinel(uint8_t ID);
Item Item::advance() const;

I think that would cover everything?

85

this alias is used only once in the header, for Items - it doesn't really introduce a new public concept that's distinct from that field.

I think it would be clearer to write it as std::vector<Item> there, and move the alias to the implementation file.

101

call this "SortByNextSymbol"? or something?

As it is it's hard at a glance to understand why we have operator< and LessItem

101

This comparator is pure implementation detail, and can go in the cpp file.
(Still fine to reference in the comment, but I think "in a canonical order" is enough)

110

this seems to compare items equal if both are dot-at-the-end.

In general the cascade/priority/completeness of comparisons isn't really easy to spot. Consider structuring like:

if (L.hasNext() && R.hasNext() && R.Lnext(G) != R.next(G))
  return L.next(G) < R.next(G);
if (L.hasNext() != R.hasNext())
  return L.hasNext() < R.hasNext(); // trailing dot is minimum
return L < R;

131

IIUC the data structure used here is inherently LR0, rather than the choice of how we build it.
(Vs in the LRTable where we could come up with data representing a full LR(1) parser without changing the structure).

So I think this function doesn't need LR0 in its name (but the class could be LR0Graph if you like)?

clang/lib/Tooling/Syntax/Pseudo/LRGraph.cpp

36

This took me a while to understand: you're reusing the ItemSet (passed by value) as the work queue (well, stack) and it's already initialized to the right elements.

This is clever, but please add a comment. Maybe even rename IS->Queue

37

nit: auto -> Item?
(Generally if the types aren't hard to write or read, it seems nice to include them)

44

nit: I find the spacing (blank lines) here a bit confusing: this seems part of the previous "paragraph" rather than the following one.

Could use a comment like "Is there a nonterminal next() to expand?"

53

You still have the IS array sitting there, you could reuse that again and avoid the allocation if you didn't expand the set too much :-)

84

Maybe call this Item.advance(), to avoid exposing the constructor

102

Since this is a single-line output, it seems more flexible to put the caller in charge of adding a newline if they want one?

(This would be inconsistent with State::dump of course, but I think that's OK. Maybe we should work out a naming convention at some point)

112

Hardcoding the indentation seems a bit special-purpose. Make the indent level an optional parameter to State::dump() and use OS.indent()?

126

nit: more spaces would make this more readable

{0} ->[{1}] {2}
or even
{0} --[{1}]-> {2}?

168

This really feels like a dubious optimization to me as it's *incorrect* if we ever get a hash collision, and the kernel ItemSet is much smaller than States which we're already storing. This seems like it must only save 20% or something of overall size?

In the other review thread you compared the size of DenseMap<hash_code, size_t> vs DenseMap<ItemSet, size_t>, but really the total size including States seems like a more useful comparison.

[hokein]

address review comments.

clang/include/clang/Tooling/Syntax/Pseudo/LRGraph.h

131

At the moment we build an LR0, but the LRGraph itself is a generic data-structure, which could be used to model the LR(1) automaton (it is a matter how we define the states/nodes in the graph). Let's say in the future, we want to build a full LR(1), then we could easily add another method LRGraph::buildLR(1), so the current names seem more reasonable to me.

clang/lib/Tooling/Syntax/Pseudo/LRGraph.cpp

168

ok, changed to DenseMap<ItemSet, size_t> instead. The size of States is ~215KB, so 15% DenseMap<hash_code> vs 28% for DenseMap<ItemSet>, not huge.

[alextsao1999]

clang/include/clang/Tooling/Syntax/Pseudo/LRGraph.h

97

Can we add LookaheadSymbol here to implement LR(1)?

[hokein]

clang/include/clang/Tooling/Syntax/Pseudo/LRGraph.h

97

we could do that. However, we don't have a plan to implement an LR(1) yet, we use SLR(1). (though LR(1) is more powerful than SLR(1), the typical deterministic LR(1) parser cannot handle the C++ grammar, we need a "general" parser GLR which can be able to handle arbitrary context-free grammars).

[alextsao1999]

clang/include/clang/Tooling/Syntax/Pseudo/LRGraph.h

97

Thanks for your answering! Oh, I know some GLR parsers are based on LR(1) or LALR, so I think our GLR parser is based on LR(1) as well. I'm trying to keep up with your train of thought :)

[sammccall]

clang/include/clang/Tooling/Syntax/Pseudo/LRGraph.h

97

Yeah, GLR changes the tradeoff between more sophisticated and simpler parsers (LR(1) > LALR > SLR(1) > LR(0)).

Normally the sophisticated parsers are able to handle grammars/languages that the simple ones can't, by avoiding action conflicts. So the value is very high.

However with GLR we can handle action conflicts by branching, so the value is "only" avoiding the performance hit of chasing branches that don't go anywhere.

So it didn't really seem worth the extra implementation complexity (or extra size of the in-memory grammar tables!) to use a more powerful parser than SLR(1). Maybe we should even have given LR(0) more thought :-)

[alextsao1999]

clang/include/clang/Tooling/Syntax/Pseudo/LRGraph.h

97

Yes, agree. SLR can reduce memory usage, but it can't handle operator precedence. With the help of GLR, we can resolve the problem of operator precedence by chosing one branch. Thanks, I got it!

clang/include/clang/Tooling/Syntax/Pseudo/LRGraph.h

+//===--- LRGraph.h - Build an LR automaton  ------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+//  LR parsers are bottom-up parsers -- they scan the input from left to right,
+//  and find the right-hand side of a production rule (called handle), and
+//  replace the handle with the nonterminal defined by the production rule.
+//
+//  This file defines LRGraph, a deterministic handle-finding finite-state
+//  automaton, which is a key component in LR parsers to recognize any of
+//  handles in the grammar efficiently. We build the LR table (ACTION and GOTO
+//  Table) based on the LRGraph.
+//
+//  LRGraph can be constructed for any context-free grammars.
+//  Even for a LR-ambiguous grammar, we can construct a deterministic FSA, but
+//  interpretation of the FSA is nondeterminsitic -- we might in a state where
+//  we can continue searching an handle and identify a handle (called
+//  shift/reduce conflicts), or identify more than one handle (callled
+//  reduce/reduce conflicts).
+//
+//  LRGraph is a common model for all variants of LR automatons, from the most
+//  basic one LR(0), the powerful SLR(1), LR(1) which uses a one-token lookahead
+//  in making decisions.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLING_SYNTAX_PSEUDO_LRGRAPH_H
+#define LLVM_CLANG_TOOLING_SYNTAX_PSEUDO_LRGRAPH_H
+
+#include "clang/Tooling/Syntax/Pseudo/Grammar.h"
+#include "llvm/ADT/Hashing.h"
+#include <vector>
+
+namespace clang {
+namespace syntax {
+namespace pseudo {
+
+// An LR item -- a grammar rule with a dot at some position of the body.
+// e.g. a production rule A := xy yields 3 items:
+//   A := .xy
+//   A := x.y
+//   A := xy.
+// An item indicates how much of a production rule has been recognized at a
+// position (described by dot), for example, A := x.y indicates that we have
+// recognized the x part from the input, and we hope next to see the input
+// derivable from y.
+class Item {
+public:
+  Item(RuleID ID, uint8_t DotPos, uint8_t RuleLength)
+      : RID(ID), DotPos(DotPos), RuleLength(RuleLength) {}
+  Item(RuleID ID, uint8_t DotPos, const Grammar &G)
+      : RID(ID), DotPos(DotPos), RuleLength(G.lookupRule(ID).Size) {
+    assert(DotPos <= RuleLength);
+  }
+
+  RuleID rule() const { return RID; }
+  uint8_t dot() const { return DotPos; }
+
+  bool hasNext() const { return DotPos < RuleLength; }
+  SymbolID next(const Grammar &G) const {
+    assert(hasNext());
+    return G.lookupRule(RID).Sequence[DotPos];
+  }
+
+  std::string dump(const Grammar &G) const;
+
+  bool operator==(const Item &I) const {
+    return DotPos == I.DotPos && RID == I.RID;
+  }
+  bool operator<(const Item &I) const {
+    return std::tie(RID, DotPos) < std::tie(I.RID, I.DotPos);
+  }
+  friend llvm::hash_code hash_value(const Item &I) {
+    return llvm::hash_combine(I.RID, I.DotPos);
+  }
+
+private:
+  RuleID RID = 0;
+  uint8_t DotPos = 0;
+  uint8_t RuleLength = 0; // the length of rule body.
+};
+using ItemSet = std::vector<Item>;
+
+// A state represents a node in the LR automaton graph. It is an item set, which
+// contains all possible rules that the LR parser may be parsing in that state.
+//
+// Conceptually, If we knew in advance what we're parsing, at any point we're
+// partway through parsing a production, sitting on a stack of partially parsed
+// productions. But because we don't know, there could be *several* productions
+// we're partway through. The set of possibilities is the parser state, and we
+// precompute all the transitions between these states.
+struct State {
+  // A full set of items (including non-kernel items) representing the state,
+  // sorted by LessItem.
+  ItemSet Items;
+
+  std::string dump(const Grammar &G) const;
+  struct LessItem {
+    LessItem(const Grammar &G) : G(G) {}
+    bool operator()(const Item &L, const Item &R) {
+      if (L.hasNext() && R.hasNext()) {
+        if (L.next(G) == R.next(G))
+          return L < R;
+        return L.next(G) < R.next(G);
+      }
+      // Item with a trailing dot is considered minimal.
+      return L.hasNext() < R.hasNext();
+    }
+    const Grammar &G;
+  };
+};
+
+// LRGraph is a deterministic finite state automaton for LR parsing.
+//
+// Intuitively, an LR automaton is a transition graph. The graph has a
+// collection of nodes, called States. Each state corresponds to a particular
+// item set, which represents a condition that could occur duing the process of
+// parsing a production. Edges are directed from one state to another. Each edge
+// is labeled by a grammar symbol (terminal or nonterminal).
+//
+// LRGraph is used to construct the LR parsing table which is a core
+// data-structure driving the LR parser.
+class LRGraph {
+public:
+  // StateID is the index in States table.
+  using StateID = uint16_t;
+
+  // Constructs an LR(0) automaton.
+  static LRGraph buildLR0(const Grammar &);
+
+  // 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;
+  };
+
+  llvm::ArrayRef<State> states() const { return States; }
+  llvm::ArrayRef<Edge> edges() const { return Edges; }
+
+  std::string dumpForTests(const Grammar &) const;
+
+private:
+  LRGraph(std::vector<State> States, std::vector<Edge> Edges)
+      : States(std::move(States)), Edges(std::move(Edges)) {}
+
+  std::vector<State> States;
+  std::vector<Edge> Edges;
+};
+
+} // namespace pseudo
+} // namespace syntax
+} // namespace clang
+
+namespace llvm {
+// Support clang::syntax::pseudo::Item as DenseMap keys.
+template <> struct DenseMapInfo<clang::syntax::pseudo::Item> {
+  static inline clang::syntax::pseudo::Item getEmptyKey() {
+    static clang::syntax::pseudo::Item EmptyKey(-1, 0, 0);
+    return EmptyKey;
+  }
+  static inline clang::syntax::pseudo::Item getTombstoneKey() {
+    static clang::syntax::pseudo::Item TombstoneKey(-2, 0, 0);
+    return TombstoneKey;
+  }
+  static unsigned getHashValue(const clang::syntax::pseudo::Item &I) {
+    return hash_value(I);
+  }
+  static bool isEqual(const clang::syntax::pseudo::Item &LHS,
+                      const clang::syntax::pseudo::Item &RHS) {
+    return LHS == RHS;
+  }
+};
+} // namespace llvm
+
+#endif // LLVM_CLANG_TOOLING_SYNTAX_PSEUDO_LRGRAPH_H

clang/lib/Tooling/Syntax/Pseudo/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS Support)
 
 add_clang_library(clangToolingSyntaxPseudo
   Grammar.cpp
   GrammarBNF.cpp
+  LRGraph.cpp
   
   LINK_LIBS
   clangBasic
   clangLex
   )

clang/lib/Tooling/Syntax/Pseudo/LRGraph.cpp

+//===--- LRGraph.cpp - -------------------------------------------*- 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/Tooling/Syntax/Pseudo/LRGraph.h"
+#include "clang/Tooling/Syntax/Pseudo/Grammar.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/Hashing.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/raw_ostream.h"
+#include <tuple>
+
+namespace clang {
+namespace syntax {
+namespace pseudo {
+
+namespace {
+
+// Computes a closure of the given item set S:
+//  - extends the given S to contain all options for parsing next token;
+//  - nonterminals after a dot are recursively expanded into the begin-state
+//    of all production rules that produce that nonterminal;
+//
+// Given
+//   Grammar rules = [ _ := E, E := E-T, E := T, T := n, T := (E) ]
+//   Input = [ E := .T ]
+// returns [ E := .T, T := .n, T := .(E) ]
+State closure(ItemSet IS, const Grammar &G) {
+  llvm::DenseSet<Item> Closure = {IS.begin(), IS.end()};
+  while (!IS.empty()) {
+    auto ProcessingItem = std::move(IS.back());
+    IS.pop_back();
+
+    if (!ProcessingItem.hasNext())
+      continue;
+    SymbolID NextSym = ProcessingItem.next(G);
+
+    if (pseudo::isToken(NextSym))
+      continue;
+    auto RRange = G.table().Nonterminals[NextSym].RuleRange;
+    for (RuleID RID = RRange.start; RID < RRange.end; ++RID) {
+      Item NewItem(RID, /*dot*/ 0, G);
+      if (Closure.insert(NewItem).second) // new
+        IS.push_back(std::move(NewItem));
+    }
+  }
+  ItemSet Sorted = {Closure.begin(), Closure.end()};
+  llvm::sort(Sorted, State::LessItem(G));
+  return {std::move(Sorted)};
+}
+
+// Returns all next (with a dot advanced) kernel item sets, partitioned by the
+// advanced symbol.
+//
+// Given
+//  S = [ E := .ab, E := E.-T ]
+// returns [
+//   {id(a), [ E := a.b ]},
+//   {id(-), [ E := E-.T]}
+// ]
+std::vector<std::pair<SymbolID, ItemSet>>
+nextAvailableKernelItems(const State &S, const Grammar &G) {
+  std::vector<std::pair<SymbolID, ItemSet>> Results;
+  llvm::ArrayRef<Item> AllItems = S.Items;
+  AllItems = AllItems.drop_while([](const Item &I) { return !I.hasNext(); });
+  while (!AllItems.empty()) {
+    SymbolID AdvancedSymbol = AllItems.front().next(G);
+    auto Batch = AllItems.take_while([AdvancedSymbol, &G](const Item &I) {
+      assert(I.hasNext());
+      return I.next(G) == AdvancedSymbol;
+    });
+    assert(!Batch.empty());
+    AllItems = AllItems.drop_front(Batch.size());
+
+    // Advance a dot over the Symbol.
+    ItemSet Next;
+    for (const Item &I : Batch)
+      Next.push_back(Item(I.rule(), I.dot() + 1, G));
+    // sort the set to keep order determinism for hash computation.
+    llvm::sort(Next);
+    Results.push_back({AdvancedSymbol, std::move(Next)});
+  }
+  return Results;
+}
+
+} // 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}\n", G.symbolName(Rule.Target),
+                       llvm::join(ToNames(Rule.seq().take_front(DotPos)), " "),
+                       llvm::join(ToNames(Rule.seq().drop_front(DotPos)), " "))
+      .str();
+}
+
+std::string State::dump(const Grammar &G) const {
+  std::string Result;
+  llvm::raw_string_ostream OS(Result);
+  for (const auto &Item : Items)
+    OS << llvm::formatv("    {0}", Item.dump(G));
+  return OS.str();
+}
+
+std::string LRGraph::dumpForTests(const Grammar &G) const {
+  std::string Result;
+  llvm::raw_string_ostream OS(Result);
+
+  OS << "States:\n";
+  for (StateID ID = 0; ID < States.size(); ++ID) {
+    OS << llvm::formatv("State {0}\n", ID);
+    OS << States[ID].dump(G);
+  }
+  for (const auto &E : Edges) {
+    OS << llvm::formatv("{0}->[{1}]{2}\n", E.Src, G.symbolName(E.Label), E.Dst);
+  }
+  return OS.str();
+}
+
+LRGraph LRGraph::buildLR0(const Grammar &G) {
+  class Builder {
+  public:
+    Builder(const Grammar &G) : G(G) {}
+
+    // Adds a given state if not existed.
+    std::pair<StateID, /*inserted*/ bool> insert(ItemSet KernelItems) {
+      assert(llvm::is_sorted(KernelItems) &&
+             "Item must be sorted before calculating its hash value!");
+      llvm::hash_code Hash =
+          llvm::hash_combine_range(KernelItems.begin(), KernelItems.end());
+      auto It = StatesIndex.find(Hash);
+      if (It != StatesIndex.end())
+        return {It->second, false};
+      States.push_back(closure(std::move(KernelItems), G));
+      StateID NextStateID = States.size() - 1;
+      StatesIndex.insert({Hash, NextStateID});
+      return {NextStateID, true};
+    }
+
+    void insertEdge(StateID Src, StateID Dst, SymbolID Label) {
+      Edges.push_back({Src, Dst, Label});
+    }
+
+    // Returns a state with the given id.
+    const State &find(StateID ID) const {
+      assert(ID < States.size());
+      return States[ID];
+    }
+
+    LRGraph build() && {
+      States.resize(States.size());
+      Edges.resize(Edges.size());
+      return LRGraph(std::move(States), std::move(Edges));
+    }
+
+  private:
+    // We store the hash codes, as collisions is rare and ItemSet is heavy.
+    // key is the hash value of **kernel** item sets.
+    llvm::DenseMap<llvm::hash_code, /*index of States*/ size_t> StatesIndex;
+    std::vector<State> States;
+    std::vector<Edge> Edges;
+    const Grammar &G;
+  } Builder(G);
+
+  std::vector<StateID> PendingStates;
+  // Initialize states with the start symbol.
+  auto RRange = G.table().Nonterminals[G.startSymbol()].RuleRange;
+  for (RuleID RID = RRange.start; RID < RRange.end; ++RID) {
+    auto StartState = std::vector<Item>{Item(RID, 0, G)};
+    auto Result = Builder.insert(std::move(StartState));
+    assert(Result.second && "State must be new");
+    PendingStates.push_back(Result.first);
+  }
+
+  while (!PendingStates.empty()) {
+    auto CurrentStateID = PendingStates.back();
+    PendingStates.pop_back();
+    for (auto Next :
+         nextAvailableKernelItems(Builder.find(CurrentStateID), 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);
+    }
+  }
+  return std::move(Builder).build();
+}
+
+} // namespace pseudo
+} // namespace syntax
+} // namespace clang

clang/unittests/Tooling/Syntax/Pseudo/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_clang_unittest(ClangPseudoTests
   GrammarTest.cpp
+  LRGraphTest.cpp
 )
 
 clang_target_link_libraries(ClangPseudoTests
   PRIVATE
   clangBasic
   clangLex
   clangToolingSyntaxPseudo
   clangTesting
   )
 
 target_link_libraries(ClangPseudoTests
   PRIVATE
   LLVMTestingSupport
   )

clang/unittests/Tooling/Syntax/Pseudo/LRGraphTest.cpp

+//===--- LRGraphTest.cpp - LRGraph tests -------------------------*- 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/Tooling/Syntax/Pseudo/LRGraph.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <memory>
+
+namespace clang {
+namespace syntax {
+namespace pseudo {
+namespace {
+
+TEST(LRGraph, Build) {
+  struct TestCase {
+    llvm::StringRef BNF;
+    llvm::StringRef ExpectedStates;
+  };
+
+  TestCase Cases[] = {{
+                          R"bnf(
+_ := expr
+expr := IDENTIFIER
+      )bnf",
+                          R"(States:
+State 0
+    _ :=  • expr
+    expr :=  • IDENTIFIER
+State 1
+    _ := expr • 
+State 2
+    expr := IDENTIFIER • 
+0->[expr]1
+0->[IDENTIFIER]2
+)"},
+                      {// A grammar with a S/R conflict in SLR table:
+                       // (id-id)-id, or id-(id-id).
+                       R"bnf(
+_ := expr
+expr := expr - expr  # S/R conflict at state 4 on '-' token
+expr := IDENTIFIER
+      )bnf",
+                       R"(States:
+State 0
+    _ :=  • expr
+    expr :=  • expr - expr
+    expr :=  • IDENTIFIER
+State 1
+    _ := expr • 
+    expr := expr • - expr
+State 2
+    expr := IDENTIFIER • 
+State 3
+    expr :=  • expr - expr
+    expr := expr - • expr
+    expr :=  • IDENTIFIER
+State 4
+    expr := expr - expr • 
+    expr := expr • - expr
+0->[expr]1
+0->[IDENTIFIER]2
+1->[-]3
+3->[expr]4
+3->[IDENTIFIER]2
+4->[-]3
+)"}};
+  for (const auto &C : Cases) {
+    std::vector<std::string> Diags;
+    auto G = Grammar::parseBNF(C.BNF, Diags);
+    ASSERT_THAT(Diags, testing::IsEmpty());
+    auto LR0 = LRGraph::buildLR0(*G);
+    EXPECT_EQ(LR0.dumpForTests(*G), C.ExpectedStates);
+  }
+}
+
+} // namespace
+} // namespace pseudo
+} // namespace syntax
+} // namespace clang