1 //===--- LRTable.cpp - Parsing table for LR parsers --------------*- C++-*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "clang-pseudo/grammar/LRTable.h"
10 #include "clang-pseudo/grammar/Grammar.h"
11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/ADT/STLExtras.h"
13 #include "llvm/ADT/StringExtras.h"
14 #include "llvm/Support/ErrorHandling.h"
15 #include "llvm/Support/FormatVariadic.h"
16 #include "llvm/Support/raw_ostream.h"
17 
18 namespace clang {
19 namespace pseudo {
20 
21 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const LRTable::Action &A) {
22   switch (A.kind()) {
23   case LRTable::Action::Shift:
24     return OS << llvm::formatv("shift state {0}", A.getShiftState());
25   case LRTable::Action::GoTo:
26     return OS << llvm::formatv("go to state {0}", A.getGoToState());
27   case LRTable::Action::Sentinel:
28     llvm_unreachable("unexpected Sentinel action kind!");
29   }
30   llvm_unreachable("unexpected action kind!");
31 }
32 
33 std::string LRTable::dumpStatistics() const {
34   return llvm::formatv(R"(
35 Statistics of the LR parsing table:
36     number of states: {0}
37     number of actions: {1}
38     number of reduces: {2}
39     size of the table (bytes): {3}
40 )",
41                        StateOffset.size() - 1, Actions.size(), Reduces.size(),
42                        bytes())
43       .str();
44 }
45 
46 std::string LRTable::dumpForTests(const Grammar &G) const {
47   std::string Result;
48   llvm::raw_string_ostream OS(Result);
49   OS << "LRTable:\n";
50   for (StateID S = 0; S < StateOffset.size() - 1; ++S) {
51     OS << llvm::formatv("State {0}\n", S);
52     for (uint16_t Terminal = 0; Terminal < NumTerminals; ++Terminal) {
53       SymbolID TokID = tokenSymbol(static_cast<tok::TokenKind>(Terminal));
54       for (auto A : find(S, TokID)) {
55         if (A.kind() == LRTable::Action::Shift)
56           OS.indent(4) << llvm::formatv("{0}: shift state {1}\n",
57                                         G.symbolName(TokID), A.getShiftState());
58       }
59     }
60     for (RuleID R : getReduceRules(S)) {
61       SymbolID Target = G.lookupRule(R).Target;
62       std::vector<llvm::StringRef> Terminals;
63       for (unsigned Terminal = 0; Terminal < NumTerminals; ++Terminal) {
64         SymbolID TokID = tokenSymbol(static_cast<tok::TokenKind>(Terminal));
65         if (canFollow(Target, TokID))
66           Terminals.push_back(G.symbolName(TokID));
67       }
68       OS.indent(4) << llvm::formatv("{0}: reduce by rule {1} '{2}'\n",
69                                     llvm::join(Terminals, " "), R,
70                                     G.dumpRule(R));
71     }
72     for (SymbolID NontermID = 0; NontermID < G.table().Nonterminals.size();
73          ++NontermID) {
74       if (find(S, NontermID).empty())
75         continue;
76       OS.indent(4) << llvm::formatv("{0}: go to state {1}\n",
77                                     G.symbolName(NontermID),
78                                     getGoToState(S, NontermID));
79     }
80   }
81   return OS.str();
82 }
83 
84 llvm::Optional<LRTable::StateID>
85 LRTable::getShiftState(StateID State, SymbolID Terminal) const {
86   // FIXME: we spend a significant amount of time on misses here.
87   // We could consider storing a std::bitset for a cheaper test?
88   assert(pseudo::isToken(Terminal) && "expected terminal symbol!");
89   for (const auto &Result : find(State, Terminal))
90     if (Result.kind() == Action::Shift)
91       return Result.getShiftState(); // unique: no shift/shift conflicts.
92   return llvm::None;
93 }
94 
95 LRTable::StateID LRTable::getGoToState(StateID State,
96                                        SymbolID Nonterminal) const {
97   assert(pseudo::isNonterminal(Nonterminal) && "expected nonterminal symbol!");
98   auto Result = find(State, Nonterminal);
99   assert(Result.size() == 1 && Result.front().kind() == Action::GoTo);
100   return Result.front().getGoToState();
101 }
102 
103 llvm::ArrayRef<LRTable::Action> LRTable::find(StateID Src, SymbolID ID) const {
104   assert(Src + 1u < StateOffset.size());
105   std::pair<size_t, size_t> Range =
106       std::make_pair(StateOffset[Src], StateOffset[Src + 1]);
107   auto SymbolRange = llvm::makeArrayRef(Symbols.data() + Range.first,
108                                         Symbols.data() + Range.second);
109 
110   assert(llvm::is_sorted(SymbolRange) &&
111          "subrange of the Symbols should be sorted!");
112   const LRTable::StateID *Start =
113       llvm::partition_point(SymbolRange, [&ID](SymbolID S) { return S < ID; });
114   if (Start == SymbolRange.end())
115     return {};
116   const LRTable::StateID *End = Start;
117   while (End != SymbolRange.end() && *End == ID)
118     ++End;
119   return llvm::makeArrayRef(&Actions[Start - Symbols.data()],
120                             /*length=*/End - Start);
121 }
122 
123 LRTable::StateID LRTable::getStartState(SymbolID Target) const {
124   assert(llvm::is_sorted(StartStates) && "StartStates must be sorted!");
125   auto It = llvm::partition_point(
126       StartStates, [Target](const std::pair<SymbolID, StateID> &X) {
127         return X.first < Target;
128       });
129   assert(It != StartStates.end() && It->first == Target &&
130          "target symbol doesn't have a start state!");
131   return It->second;
132 }
133 
134 } // namespace pseudo
135 } // namespace clang
136