xref: /freebsd/contrib/llvm-project/llvm/include/llvm/Support/Automaton.h (revision 7fdf597e96a02165cfe22ff357b857d5fa15ed8a)
1 //===-- Automaton.h - Support for driving TableGen-produced DFAs ----------===//
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 // This file implements class that drive and introspect deterministic finite-
10 // state automata (DFAs) as generated by TableGen's -gen-automata backend.
11 //
12 // For a description of how to define an automaton, see
13 // include/llvm/TableGen/Automaton.td.
14 //
15 // One important detail is that these deterministic automata are created from
16 // (potentially) nondeterministic definitions. Therefore a unique sequence of
17 // input symbols will produce one path through the DFA but multiple paths
18 // through the original NFA. An automaton by default only returns "accepted" or
19 // "not accepted", but frequently we want to analyze what NFA path was taken.
20 // Finding a path through the NFA states that results in a DFA state can help
21 // answer *what* the solution to a problem was, not just that there exists a
22 // solution.
23 //
24 //===----------------------------------------------------------------------===//
25 
26 #ifndef LLVM_SUPPORT_AUTOMATON_H
27 #define LLVM_SUPPORT_AUTOMATON_H
28 
29 #include "llvm/ADT/ArrayRef.h"
30 #include "llvm/ADT/DenseMap.h"
31 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/Support/Allocator.h"
33 #include <deque>
34 #include <map>
35 #include <memory>
36 
37 namespace llvm {
38 
39 using NfaPath = SmallVector<uint64_t, 4>;
40 
41 /// Forward define the pair type used by the automata transition info tables.
42 ///
43 /// Experimental results with large tables have shown a significant (multiple
44 /// orders of magnitude) parsing speedup by using a custom struct here with a
45 /// trivial constructor rather than std::pair<uint64_t, uint64_t>.
46 struct NfaStatePair {
47   uint64_t FromDfaState, ToDfaState;
48 
49   bool operator<(const NfaStatePair &Other) const {
50     return std::make_tuple(FromDfaState, ToDfaState) <
51            std::make_tuple(Other.FromDfaState, Other.ToDfaState);
52   }
53 };
54 
55 namespace internal {
56 /// The internal class that maintains all possible paths through an NFA based
57 /// on a path through the DFA.
58 class NfaTranscriber {
59 private:
60   /// Cached transition table. This is a table of NfaStatePairs that contains
61   /// zero-terminated sequences pointed to by DFA transitions.
62   ArrayRef<NfaStatePair> TransitionInfo;
63 
64   /// A simple linked-list of traversed states that can have a shared tail. The
65   /// traversed path is stored in reverse order with the latest state as the
66   /// head.
67   struct PathSegment {
68     uint64_t State;
69     PathSegment *Tail;
70   };
71 
72   /// We allocate segment objects frequently. Allocate them upfront and dispose
73   /// at the end of a traversal rather than hammering the system allocator.
74   SpecificBumpPtrAllocator<PathSegment> Allocator;
75 
76   /// Heads of each tracked path. These are not ordered.
77   std::deque<PathSegment *> Heads;
78 
79   /// The returned paths. This is populated during getPaths.
80   SmallVector<NfaPath, 4> Paths;
81 
82   /// Create a new segment and return it.
83   PathSegment *makePathSegment(uint64_t State, PathSegment *Tail) {
84     PathSegment *P = Allocator.Allocate();
85     *P = {State, Tail};
86     return P;
87   }
88 
89   /// Pairs defines a sequence of possible NFA transitions for a single DFA
90   /// transition.
91   void transition(ArrayRef<NfaStatePair> Pairs) {
92     // Iterate over all existing heads. We will mutate the Heads deque during
93     // iteration.
94     unsigned NumHeads = Heads.size();
95     for (unsigned I = 0; I < NumHeads; ++I) {
96       PathSegment *Head = Heads[I];
97       // The sequence of pairs is sorted. Select the set of pairs that
98       // transition from the current head state.
99       auto PI = lower_bound(Pairs, NfaStatePair{Head->State, 0ULL});
100       auto PE = upper_bound(Pairs, NfaStatePair{Head->State, INT64_MAX});
101       // For every transition from the current head state, add a new path
102       // segment.
103       for (; PI != PE; ++PI)
104         if (PI->FromDfaState == Head->State)
105           Heads.push_back(makePathSegment(PI->ToDfaState, Head));
106     }
107     // Now we've iterated over all the initial heads and added new ones,
108     // dispose of the original heads.
109     Heads.erase(Heads.begin(), std::next(Heads.begin(), NumHeads));
110   }
111 
112 public:
113   NfaTranscriber(ArrayRef<NfaStatePair> TransitionInfo)
114       : TransitionInfo(TransitionInfo) {
115     reset();
116   }
117 
118   ArrayRef<NfaStatePair> getTransitionInfo() const {
119     return TransitionInfo;
120   }
121 
122   void reset() {
123     Paths.clear();
124     Heads.clear();
125     Allocator.DestroyAll();
126     // The initial NFA state is 0.
127     Heads.push_back(makePathSegment(0ULL, nullptr));
128   }
129 
130   void transition(unsigned TransitionInfoIdx) {
131     unsigned EndIdx = TransitionInfoIdx;
132     while (TransitionInfo[EndIdx].ToDfaState != 0)
133       ++EndIdx;
134     ArrayRef<NfaStatePair> Pairs(&TransitionInfo[TransitionInfoIdx],
135                                  EndIdx - TransitionInfoIdx);
136     transition(Pairs);
137   }
138 
139   ArrayRef<NfaPath> getPaths() {
140     Paths.clear();
141     for (auto *Head : Heads) {
142       NfaPath P;
143       while (Head->State != 0) {
144         P.push_back(Head->State);
145         Head = Head->Tail;
146       }
147       std::reverse(P.begin(), P.end());
148       Paths.push_back(std::move(P));
149     }
150     return Paths;
151   }
152 };
153 } // namespace internal
154 
155 /// A deterministic finite-state automaton. The automaton is defined in
156 /// TableGen; this object drives an automaton defined by tblgen-emitted tables.
157 ///
158 /// An automaton accepts a sequence of input tokens ("actions"). This class is
159 /// templated on the type of these actions.
160 template <typename ActionT> class Automaton {
161   /// Map from {State, Action} to {NewState, TransitionInfoIdx}.
162   /// TransitionInfoIdx is used by the DfaTranscriber to analyze the transition.
163   /// FIXME: This uses a std::map because ActionT can be a pair type including
164   /// an enum. In particular DenseMapInfo<ActionT> must be defined to use
165   /// DenseMap here.
166   /// This is a shared_ptr to allow very quick copy-construction of Automata; this
167   /// state is immutable after construction so this is safe.
168   using MapTy = std::map<std::pair<uint64_t, ActionT>, std::pair<uint64_t, unsigned>>;
169   std::shared_ptr<MapTy> M;
170   /// An optional transcription object. This uses much more state than simply
171   /// traversing the DFA for acceptance, so is heap allocated.
172   std::shared_ptr<internal::NfaTranscriber> Transcriber;
173   /// The initial DFA state is 1.
174   uint64_t State = 1;
175   /// True if we should transcribe and false if not (even if Transcriber is defined).
176   bool Transcribe;
177 
178 public:
179   /// Create an automaton.
180   /// \param Transitions The Transitions table as created by TableGen. Note that
181   ///                    because the action type differs per automaton, the
182   ///                    table type is templated as ArrayRef<InfoT>.
183   /// \param TranscriptionTable The TransitionInfo table as created by TableGen.
184   ///
185   /// Providing the TranscriptionTable argument as non-empty will enable the
186   /// use of transcription, which analyzes the possible paths in the original
187   /// NFA taken by the DFA. NOTE: This is substantially more work than simply
188   /// driving the DFA, so unless you require the getPaths() method leave this
189   /// empty.
190   template <typename InfoT>
191   Automaton(ArrayRef<InfoT> Transitions,
192             ArrayRef<NfaStatePair> TranscriptionTable = {}) {
193     if (!TranscriptionTable.empty())
194       Transcriber =
195           std::make_shared<internal::NfaTranscriber>(TranscriptionTable);
196     Transcribe = Transcriber != nullptr;
197     M = std::make_shared<MapTy>();
198     for (const auto &I : Transitions)
199       // Greedily read and cache the transition table.
200       M->emplace(std::make_pair(I.FromDfaState, I.Action),
201                  std::make_pair(I.ToDfaState, I.InfoIdx));
202   }
203   Automaton(const Automaton &Other)
204       : M(Other.M), State(Other.State), Transcribe(Other.Transcribe) {
205     // Transcriber is not thread-safe, so create a new instance on copy.
206     if (Other.Transcriber)
207       Transcriber = std::make_shared<internal::NfaTranscriber>(
208           Other.Transcriber->getTransitionInfo());
209   }
210 
211   /// Reset the automaton to its initial state.
212   void reset() {
213     State = 1;
214     if (Transcriber)
215       Transcriber->reset();
216   }
217 
218   /// Enable or disable transcription. Transcription is only available if
219   /// TranscriptionTable was provided to the constructor.
220   void enableTranscription(bool Enable = true) {
221     assert(Transcriber &&
222            "Transcription is only available if TranscriptionTable was provided "
223            "to the Automaton constructor");
224     Transcribe = Enable;
225   }
226 
227   /// Transition the automaton based on input symbol A. Return true if the
228   /// automaton transitioned to a valid state, false if the automaton
229   /// transitioned to an invalid state.
230   ///
231   /// If this function returns false, all methods are undefined until reset() is
232   /// called.
233   bool add(const ActionT &A) {
234     auto I = M->find({State, A});
235     if (I == M->end())
236       return false;
237     if (Transcriber && Transcribe)
238       Transcriber->transition(I->second.second);
239     State = I->second.first;
240     return true;
241   }
242 
243   /// Return true if the automaton can be transitioned based on input symbol A.
244   bool canAdd(const ActionT &A) {
245     auto I = M->find({State, A});
246     return I != M->end();
247   }
248 
249   /// Obtain a set of possible paths through the input nondeterministic
250   /// automaton that could be obtained from the sequence of input actions
251   /// presented to this deterministic automaton.
252   ArrayRef<NfaPath> getNfaPaths() {
253     assert(Transcriber && Transcribe &&
254            "Can only obtain NFA paths if transcribing!");
255     return Transcriber->getPaths();
256   }
257 };
258 
259 } // namespace llvm
260 
261 #endif // LLVM_SUPPORT_AUTOMATON_H
262