text: //===--- LRTable.h - Define LR Parsing Table ---------------------*- 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
  //
  //===----------------------------------------------------------------------===//
  //
  //  The LRTable (referred as LR parsing table in the LR literature) is the core
  //  component in LR parsers, it drives the LR parsers by specifying an action to
  //  take given the current state on the top of the stack and the current
  //  lookahead token.
  //
  //  The LRTable can be described as a matrix where the rows represent
  //  the states of the LR graph, the columns represent the symbols of the
  //  grammar, and each entry of the matrix (called action) represents a
  //  state transition in the graph.
  //
  //  Typically, based on the category of the grammar symbol, the LRTable is
  //  broken into two logically separate tables:
  //    - ACTION table with terminals as columns -- e.g ACTION[S, a] specifies
  //      next action (shift/reduce/accept/error) on state S under a lookahead
  //      terminal a
  //    - GOTO table with nonterminals as columns -- e.g. GOTO[S, X] specify
  //      the state which we transist to from the state S with the nonterminal X
  //
  //  LRTable is *performance-critial* as it is consulted frequently during a
  //  parse. In general, LRTable is very sparse (most of the entries are empty).
  //  For example, for the C++ language, the SLR table has ~1500 states and 650
  //  symbols which results in a matrix having 975K entries, ~90% of entries are
  //  empty.
  //
  //  This file implements a speed-and-space-efficient LRTable.
  //
  //===----------------------------------------------------------------------===//
  
  #ifndef CLANG_PSEUDO_LRTABLE_H
  #define CLANG_PSEUDO_LRTABLE_H
  
  #include "clang-pseudo/Grammar.h"
  #include "llvm/ADT/ArrayRef.h"
  #include <cstdint>
  #include <vector>
  
  namespace clang {
  namespace pseudo {
  
  // Represents the LR parsing table, which can efficiently the question "what is
  // the next step given the lookahead token and current state on top of the
  // stack?".
  //
  // This is a dense implementation, which only takes an amount of space that is
  // proportional to the number of non-empty entries in the table.
  //
  // Unlike the typical LR parsing table which allows at most one available action
  // per entry, conflicted actions are allowed in LRTable. The LRTable is designed
  // to be used in nondeterministic LR parsers (e.g. GLR).
  class LRTable {
  public:
    // StateID is only 13 bits wide.
    using StateID = uint16_t;
    static constexpr unsigned StateBits = 13;
  
    // Action represents the terminal and nonterminal actions, it combines the
    // entry of the ACTION and GOTO tables from the LR literature.
    class Action {
    public:
      enum Kind : uint8_t {
        Sentinel = 0,
        // Terminal actions, corresponding to entries of ACTION table.
  
        // Shift to state n: move forward with the lookahead, and push state n
        // onto the state stack.
        // A shift is a forward transition, and the value n is the next state that
        // the parser is to enter.
        Shift,
        // Reduce by a rule: pop the state stack.
        Reduce,
        // Signals that we have parsed the input successfully.
        Accept,
  
        // Nonterminal actions, corresponding to entry of GOTO table.
  
        // Go to state n: push state n onto the state stack.
        // Similar to Shift, but it is a nonterminal forward transition.
        GoTo,
      };
  
      static Action accept(RuleID RID) { return Action(Accept, RID); }
      static Action goTo(StateID S) { return Action(GoTo, S); }
      static Action shift(StateID S) { return Action(Shift, S); }
      static Action reduce(RuleID RID) { return Action(Reduce, RID); }
      static Action sentinel() { return Action(Sentinel, 0); }
  
      StateID getShiftState() const {
        assert(kind() == Shift);
        return Value;
      }
      StateID getGoToState() const {
        assert(kind() == GoTo);
        return Value;
      }
      RuleID getReduceRule() const {
        assert(kind() == Reduce);
        return Value;
      }
      Kind kind() const { return static_cast<Kind>(K); }
  
      bool operator==(const Action &L) const { return opaque() == L.opaque(); }
      uint16_t opaque() const { return K << ValueBits | Value; };
  
    private:
      Action(Kind K1, unsigned Value) : K(K1), Value(Value) {}
      static constexpr unsigned ValueBits = StateBits;
      static constexpr unsigned KindBits = 3;
      static_assert(ValueBits >= RuleBits, "Value must be able to store RuleID");
      static_assert(KindBits + ValueBits <= 16,
                    "Must be able to store kind and value efficiently");
      uint16_t K : KindBits;
      // Either StateID or RuleID, depending on the Kind.
      uint16_t Value : ValueBits;
    };
  
    // Returns all available actions for the given state on a terminal.
    // Expected to be called by LR parsers.
    llvm::ArrayRef<Action> getActions(StateID State, SymbolID Terminal) const;
    // Returns the state after we reduce a nonterminal.
    // Expected to be called by LR parsers.
    StateID getGoToState(StateID State, SymbolID Nonterminal) const;
  
    // Looks up available actions.
    // Returns empty if no available actions in the table.
    llvm::ArrayRef<Action> find(StateID State, SymbolID Symbol) const;
  
    size_t bytes() const {
      return sizeof(*this) + Actions.capacity() * sizeof(Action) +
             States.capacity() * sizeof(StateID) +
             NontermOffset.capacity() * sizeof(uint32_t) +
             TerminalOffset.capacity() * sizeof(uint32_t);
    }
  
    std::string dumpStatistics() const;
    std::string dumpForTests(const Grammar &G) const;
  
    // Build a SLR(1) parsing table.
    static LRTable buildSLR(const Grammar &G);
  
    class Builder;
    // Represents an entry in the table, used for building the LRTable.
    struct Entry {
      StateID State;
      SymbolID Symbol;
      Action Act;
    };
    // Build a specifid table for testing purposes.
    static LRTable buildForTests(const GrammarTable &, llvm::ArrayRef<Entry>);
  
  private:
    // Conceptually the LR table is a multimap from (State, SymbolID) => Action.
    // Our physical representation is quite different for compactness.
  
    // Index is nonterminal SymbolID, value is the offset into States/Actions
    // where the entries for this nonterminal begin.
    // Give a non-terminal id, the corresponding half-open range of StateIdx is
    // [NontermIdx[id], NontermIdx[id+1]).
    std::vector<uint32_t> NontermOffset;
    // Similar to NontermOffset, but for terminals, index is tok::TokenKind.
    std::vector<uint32_t> TerminalOffset;
    // Parallel to Actions, the value is State (rows of the matrix).
    // Grouped by the SymbolID, and only subranges are sorted.
    std::vector<StateID> States;
    // A flat list of available actions, sorted by (SymbolID, State).
    std::vector<Action> Actions;
  };
  llvm::raw_ostream &operator<<(llvm::raw_ostream &, const LRTable::Action &);
  
  } // namespace pseudo
  } // namespace clang
  
  #endif // LLVM_CLANG_TOOLING_SYNTAX_PSEUDO_LRTABLE_H
  