26#ifndef LLVM_SUPPORT_AUTOMATON_H
27#define LLVM_SUPPORT_AUTOMATON_H
36#include <unordered_map>
53 std::make_tuple(
Other.FromDfaState,
Other.ToDfaState);
79 std::deque<PathSegment *> Heads;
85 PathSegment *makePathSegment(
uint64_t State, PathSegment *
Tail) {
96 unsigned NumHeads = Heads.size();
97 for (
unsigned I = 0;
I < NumHeads; ++
I) {
98 PathSegment *Head = Heads[
I];
105 for (; PI != PE; ++PI)
106 if (PI->FromDfaState == Head->State)
107 Heads.push_back(makePathSegment(PI->ToDfaState, Head));
111 Heads.erase(Heads.begin(), std::next(Heads.begin(), NumHeads));
116 : TransitionInfo(TransitionInfo) {
121 return TransitionInfo;
129 Heads.push_back(makePathSegment(0ULL,
nullptr));
133 unsigned EndIdx = TransitionInfoIdx;
134 while (TransitionInfo[EndIdx].ToDfaState != 0)
137 EndIdx - TransitionInfoIdx);
143 for (
auto *Head : Heads) {
145 while (Head->State != 0) {
146 P.push_back(Head->State);
149 std::reverse(
P.begin(),
P.end());
170 using MapTy = std::map<std::pair<uint64_t, ActionT>, std::pair<uint64_t, unsigned>>;
171 std::shared_ptr<MapTy> M;
174 std::shared_ptr<internal::NfaTranscriber> Transcriber;
192 template <
typename InfoT>
195 if (!TranscriptionTable.empty())
197 std::make_shared<internal::NfaTranscriber>(TranscriptionTable);
198 Transcribe = Transcriber !=
nullptr;
199 M = std::make_shared<MapTy>();
200 for (
const auto &
I : Transitions)
202 M->emplace(std::make_pair(
I.FromDfaState,
I.Action),
203 std::make_pair(
I.ToDfaState,
I.InfoIdx));
208 if (
Other.Transcriber)
209 Transcriber = std::make_shared<internal::NfaTranscriber>(
210 Other.Transcriber->getTransitionInfo());
217 Transcriber->reset();
224 "Transcription is only available if TranscriptionTable was provided "
225 "to the Automaton constructor");
236 auto I = M->find({State,
A});
239 if (Transcriber && Transcribe)
240 Transcriber->transition(
I->second.second);
241 State =
I->second.first;
247 auto I = M->find({State,
A});
248 return I != M->end();
255 assert(Transcriber && Transcribe &&
256 "Can only obtain NFA paths if transcribing!");
257 return Transcriber->getPaths();
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file defines the DenseMap class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
A deterministic finite-state automaton.
void reset()
Reset the automaton to its initial state.
bool canAdd(const ActionT &A)
Return true if the automaton can be transitioned based on input symbol A.
Automaton(const Automaton &Other)
bool add(const ActionT &A)
Transition the automaton based on input symbol A.
void enableTranscription(bool Enable=true)
Enable or disable transcription.
ArrayRef< NfaPath > getNfaPaths()
Obtain a set of possible paths through the input nondeterministic automaton that could be obtained fr...
Automaton(ArrayRef< InfoT > Transitions, ArrayRef< NfaStatePair > TranscriptionTable={})
Create an automaton.
void push_back(const T &Elt)
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
The internal class that maintains all possible paths through an NFA based on a path through the DFA.
NfaTranscriber(ArrayRef< NfaStatePair > TransitionInfo)
ArrayRef< NfaPath > getPaths()
void transition(unsigned TransitionInfoIdx)
ArrayRef< NfaStatePair > getTransitionInfo() const
@ Tail
Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...
This is an optimization pass for GlobalISel generic memory operations.
auto upper_bound(R &&Range, T &&Value)
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Forward define the pair type used by the automata transition info tables.
bool operator<(const NfaStatePair &Other) const