clang-tools-extra/pseudo/lib/grammar/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-pseudo/grammar/LRGraph.h"
#include "clang-pseudo/grammar/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"

using ItemSet = std::vector<clang::pseudo::Item>;

namespace llvm {
// Support clang::pseudo::Item as DenseMap keys.
template <> struct DenseMapInfo<ItemSet> {
  static inline ItemSet getEmptyKey() {
    return {DenseMapInfo<clang::pseudo::Item>::getEmptyKey()};
  }
  static inline ItemSet getTombstoneKey() {
    return {DenseMapInfo<clang::pseudo::Item>::getTombstoneKey()};
  }
  static unsigned getHashValue(const ItemSet &I) {
    return llvm::hash_combine_range(I.begin(), I.end());
  }
  static bool isEqual(const ItemSet &LHS, const ItemSet &RHS) {
    return LHS == RHS;
  }
};
} // namespace llvm

namespace clang {
namespace pseudo {
namespace {

struct SortByNextSymbol {
  SortByNextSymbol(const Grammar &G) : G(G) {}
  bool operator()(const Item &L, const Item &R) {
    if (L.hasNext() && R.hasNext() && L.next(G) != R.next(G))
      return L.next(G) < R.next(G);
    if (L.hasNext() != R.hasNext())
      return L.hasNext() < R.hasNext(); //  a trailing dot is minimal.
    return L < R;
  }
  const Grammar &G;
};

// 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 Queue, const Grammar &G) {
  llvm::DenseSet<Item> InQueue = {Queue.begin(), Queue.end()};
  // We reuse the passed-by-value Queue as the final result, as it's already
  // initialized to the right elements.
  size_t ItIndex = 0;
  while (ItIndex < Queue.size()) {
    const Item &ExpandingItem = Queue[ItIndex];
    ++ItIndex;
    if (!ExpandingItem.hasNext())
      continue;

    SymbolID NextSym = ExpandingItem.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 = Item::start(RID, G);
      if (InQueue.insert(NewItem).second) // new
        Queue.push_back(std::move(NewItem));
    }
  }
  Queue.shrink_to_fit();
  llvm::sort(Queue, SortByNextSymbol(G));
  return {std::move(Queue)};
}

// Returns all next (with a dot advanced) kernel item sets, partitioned by the
// advanced symbol.
//
// Given
//  S = [ E := . a b, 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(I.advance());
    // sort the set to keep order determinism for hash computation.
    llvm::sort(Next);
    Results.push_back({AdvancedSymbol, std::move(Next)});
  }
  return Results;
}

std::vector<std::pair<ExtensionID, SymbolID>>
availableRecovery(const State &S, const Grammar &G) {
  std::vector<std::pair<ExtensionID, SymbolID>> Result;
  for (const Item &I : S.Items) {
    const auto &Rule = G.lookupRule(I.rule());
    if (I.dot() != Rule.RecoveryIndex)
      continue;
    Result.push_back({Rule.Recovery, Rule.seq()[Rule.RecoveryIndex]});
  }
  llvm::sort(Result);
  Result.erase(std::unique(Result.begin(), Result.end()), Result.end());
  return Result;
}

} // 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}{3}", G.symbolName(Rule.Target),
                       llvm::join(ToNames(Rule.seq().take_front(DotPos)), " "),
                       llvm::join(ToNames(Rule.seq().drop_front(DotPos)), " "),
                       Rule.RecoveryIndex == DotPos ? " [recovery]" : "")
      .str();
}

std::string State::dump(const Grammar &G, unsigned Indent) const {
  std::string Result;
  llvm::raw_string_ostream OS(Result);
  for (const auto &Item : Items)
    OS.indent(Indent) << llvm::formatv("{0}\n", 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, /*Indent*/ 4);
  }
  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 inserting to a hash map!");
      auto It = StatesIndex.find(KernelItems);
      if (It != StatesIndex.end())
        return {It->second, false};
      States.push_back(closure(KernelItems, G));
      StateID NextStateID = States.size() - 1;
      StatesIndex.insert({std::move(KernelItems), NextStateID});
      return {NextStateID, true};
    }

    void insertEdge(StateID Src, StateID Dst, SymbolID Label) {
      Edges.push_back({Src, Dst, Label});
    }

    void insertRecovery(StateID Src, ExtensionID Strategy, SymbolID Result) {
      Recoveries.push_back({Src, Strategy, Result});
    }

    // Returns a state with the given id.
    const State &find(StateID ID) const {
      assert(ID < States.size());
      return States[ID];
    }

    void addStartState(SymbolID Sym, StateID State) {
      StartStates.push_back({Sym, State});
    }

    LRGraph build() && {
      States.shrink_to_fit();
      Edges.shrink_to_fit();
      Recoveries.shrink_to_fit();
      llvm::sort(StartStates);
      StartStates.shrink_to_fit();
      return LRGraph(std::move(States), std::move(Edges), std::move(Recoveries),
                     std::move(StartStates));
    }

  private:
    // Key is the **kernel** item sets.
    llvm::DenseMap<ItemSet, /*index of States*/ size_t> StatesIndex;
    std::vector<State> States;
    std::vector<Edge> Edges;
    std::vector<Recovery> Recoveries;
    const Grammar &G;
    std::vector<std::pair<SymbolID, StateID>> StartStates;
  } Builder(G);

  std::vector<StateID> PendingStates;
  // Initialize states with the start symbol.
  auto RRange = G.table().Nonterminals[G.underscore()].RuleRange;
  for (RuleID RID = RRange.Start; RID < RRange.End; ++RID) {
    auto StartState = std::vector<Item>{Item::start(RID, G)};
    auto Result = Builder.insert(std::move(StartState));
    assert(Result.second && "State must be new");
    PendingStates.push_back(Result.first);

    const Rule &StartRule = G.lookupRule(RID);
    assert(StartRule.Size == 2 &&
           StartRule.seq().back() == tokenSymbol(tok::eof) &&
           "Start rule must be of the form `_ := start-symbol EOF`!");
    Builder.addStartState(StartRule.seq().front(), Result.first);
  }

  while (!PendingStates.empty()) {
    auto StateID = PendingStates.back();
    PendingStates.pop_back();
    for (auto Next : nextAvailableKernelItems(Builder.find(StateID), G)) {
      auto Insert = Builder.insert(Next.second);
      if (Insert.second) // new state, insert to the pending queue.
        PendingStates.push_back(Insert.first);
      Builder.insertEdge(StateID, Insert.first, Next.first);
    }
    for (auto Recovery : availableRecovery(Builder.find(StateID), G))
      Builder.insertRecovery(StateID, Recovery.first, Recovery.second);
  }
  return std::move(Builder).build();
}

} // namespace pseudo
} // namespace clang