1 //===-- Automaton.h - Support for driving TableGen-produced DFAs ----------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements class that drive and introspect deterministic finite-
10 // state automata (DFAs) as generated by TableGen's -gen-automata backend.
12 // For a description of how to define an automaton, see
13 // include/llvm/TableGen/Automaton.td.
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
24 //===----------------------------------------------------------------------===//
26 #ifndef LLVM_SUPPORT_AUTOMATON_H
27 #define LLVM_SUPPORT_AUTOMATON_H
29 #include "llvm/ADT/ArrayRef.h"
30 #include "llvm/ADT/DenseMap.h"
31 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/Support/Allocator.h"
36 #include <unordered_map>
41 using NfaPath
= SmallVector
<uint64_t, 4>;
43 /// Forward define the pair type used by the automata transition info tables.
45 /// Experimental results with large tables have shown a significant (multiple
46 /// orders of magnitude) parsing speedup by using a custom struct here with a
47 /// trivial constructor rather than std::pair<uint64_t, uint64_t>.
49 uint64_t FromDfaState
, ToDfaState
;
51 bool operator<(const NfaStatePair
&Other
) const {
52 return std::make_tuple(FromDfaState
, ToDfaState
) <
53 std::make_tuple(Other
.FromDfaState
, Other
.ToDfaState
);
58 /// The internal class that maintains all possible paths through an NFA based
59 /// on a path through the DFA.
60 class NfaTranscriber
{
62 /// Cached transition table. This is a table of NfaStatePairs that contains
63 /// zero-terminated sequences pointed to by DFA transitions.
64 ArrayRef
<NfaStatePair
> TransitionInfo
;
66 /// A simple linked-list of traversed states that can have a shared tail. The
67 /// traversed path is stored in reverse order with the latest state as the
74 /// We allocate segment objects frequently. Allocate them upfront and dispose
75 /// at the end of a traversal rather than hammering the system allocator.
76 SpecificBumpPtrAllocator
<PathSegment
> Allocator
;
78 /// Heads of each tracked path. These are not ordered.
79 std::deque
<PathSegment
*> Heads
;
81 /// The returned paths. This is populated during getPaths.
82 SmallVector
<NfaPath
, 4> Paths
;
84 /// Create a new segment and return it.
85 PathSegment
*makePathSegment(uint64_t State
, PathSegment
*Tail
) {
86 PathSegment
*P
= Allocator
.Allocate();
91 /// Pairs defines a sequence of possible NFA transitions for a single DFA
93 void transition(ArrayRef
<NfaStatePair
> Pairs
) {
94 // Iterate over all existing heads. We will mutate the Heads deque during
96 unsigned NumHeads
= Heads
.size();
97 for (unsigned I
= 0; I
< NumHeads
; ++I
) {
98 PathSegment
*Head
= Heads
[I
];
99 // The sequence of pairs is sorted. Select the set of pairs that
100 // transition from the current head state.
101 auto PI
= lower_bound(Pairs
, NfaStatePair
{Head
->State
, 0ULL});
102 auto PE
= upper_bound(Pairs
, NfaStatePair
{Head
->State
, INT64_MAX
});
103 // For every transition from the current head state, add a new path
105 for (; PI
!= PE
; ++PI
)
106 if (PI
->FromDfaState
== Head
->State
)
107 Heads
.push_back(makePathSegment(PI
->ToDfaState
, Head
));
109 // Now we've iterated over all the initial heads and added new ones,
110 // dispose of the original heads.
111 Heads
.erase(Heads
.begin(), std::next(Heads
.begin(), NumHeads
));
115 NfaTranscriber(ArrayRef
<NfaStatePair
> TransitionInfo
)
116 : TransitionInfo(TransitionInfo
) {
123 Allocator
.DestroyAll();
124 // The initial NFA state is 0.
125 Heads
.push_back(makePathSegment(0ULL, nullptr));
128 void transition(unsigned TransitionInfoIdx
) {
129 unsigned EndIdx
= TransitionInfoIdx
;
130 while (TransitionInfo
[EndIdx
].ToDfaState
!= 0)
132 ArrayRef
<NfaStatePair
> Pairs(&TransitionInfo
[TransitionInfoIdx
],
133 EndIdx
- TransitionInfoIdx
);
137 ArrayRef
<NfaPath
> getPaths() {
139 for (auto *Head
: Heads
) {
141 while (Head
->State
!= 0) {
142 P
.push_back(Head
->State
);
145 std::reverse(P
.begin(), P
.end());
146 Paths
.push_back(std::move(P
));
151 } // namespace internal
153 /// A deterministic finite-state automaton. The automaton is defined in
154 /// TableGen; this object drives an automaton defined by tblgen-emitted tables.
156 /// An automaton accepts a sequence of input tokens ("actions"). This class is
157 /// templated on the type of these actions.
158 template <typename ActionT
> class Automaton
{
159 /// Map from {State, Action} to {NewState, TransitionInfoIdx}.
160 /// TransitionInfoIdx is used by the DfaTranscriber to analyze the transition.
161 /// FIXME: This uses a std::map because ActionT can be a pair type including
162 /// an enum. In particular DenseMapInfo<ActionT> must be defined to use
164 /// This is a shared_ptr to allow very quick copy-construction of Automata; this
165 /// state is immutable after construction so this is safe.
166 using MapTy
= std::map
<std::pair
<uint64_t, ActionT
>, std::pair
<uint64_t, unsigned>>;
167 std::shared_ptr
<MapTy
> M
;
168 /// An optional transcription object. This uses much more state than simply
169 /// traversing the DFA for acceptance, so is heap allocated.
170 std::shared_ptr
<internal::NfaTranscriber
> Transcriber
;
171 /// The initial DFA state is 1.
173 /// True if we should transcribe and false if not (even if Transcriber is defined).
177 /// Create an automaton.
178 /// \param Transitions The Transitions table as created by TableGen. Note that
179 /// because the action type differs per automaton, the
180 /// table type is templated as ArrayRef<InfoT>.
181 /// \param TranscriptionTable The TransitionInfo table as created by TableGen.
183 /// Providing the TranscriptionTable argument as non-empty will enable the
184 /// use of transcription, which analyzes the possible paths in the original
185 /// NFA taken by the DFA. NOTE: This is substantially more work than simply
186 /// driving the DFA, so unless you require the getPaths() method leave this
188 template <typename InfoT
>
189 Automaton(ArrayRef
<InfoT
> Transitions
,
190 ArrayRef
<NfaStatePair
> TranscriptionTable
= {}) {
191 if (!TranscriptionTable
.empty())
193 std::make_shared
<internal::NfaTranscriber
>(TranscriptionTable
);
194 Transcribe
= Transcriber
!= nullptr;
195 M
= std::make_shared
<MapTy
>();
196 for (const auto &I
: Transitions
)
197 // Greedily read and cache the transition table.
198 M
->emplace(std::make_pair(I
.FromDfaState
, I
.Action
),
199 std::make_pair(I
.ToDfaState
, I
.InfoIdx
));
201 Automaton(const Automaton
&) = default;
203 /// Reset the automaton to its initial state.
207 Transcriber
->reset();
210 /// Enable or disable transcription. Transcription is only available if
211 /// TranscriptionTable was provided to the constructor.
212 void enableTranscription(bool Enable
= true) {
213 assert(Transcriber
&&
214 "Transcription is only available if TranscriptionTable was provided "
215 "to the Automaton constructor");
219 /// Transition the automaton based on input symbol A. Return true if the
220 /// automaton transitioned to a valid state, false if the automaton
221 /// transitioned to an invalid state.
223 /// If this function returns false, all methods are undefined until reset() is
225 bool add(const ActionT
&A
) {
226 auto I
= M
->find({State
, A
});
229 if (Transcriber
&& Transcribe
)
230 Transcriber
->transition(I
->second
.second
);
231 State
= I
->second
.first
;
235 /// Return true if the automaton can be transitioned based on input symbol A.
236 bool canAdd(const ActionT
&A
) {
237 auto I
= M
->find({State
, A
});
238 return I
!= M
->end();
241 /// Obtain a set of possible paths through the input nondeterministic
242 /// automaton that could be obtained from the sequence of input actions
243 /// presented to this deterministic automaton.
244 ArrayRef
<NfaPath
> getNfaPaths() {
245 assert(Transcriber
&& Transcribe
&&
246 "Can only obtain NFA paths if transcribing!");
247 return Transcriber
->getPaths();
253 #endif // LLVM_SUPPORT_AUTOMATON_H