//===-- Automaton.h - Support for driving TableGen-produced DFAs ----------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This file implements class that drive and introspect deterministic finite-
// state automata (DFAs) as generated by TableGen's -gen-automata backend.
//
// For a description of how to define an automaton, see
// include/llvm/TableGen/Automaton.td.
//
// One important detail is that these deterministic automata are created from
// (potentially) nondeterministic definitions. Therefore a unique sequence of
// input symbols will produce one path through the DFA but multiple paths
// through the original NFA. An automaton by default only returns "accepted" or
// "not accepted", but frequently we want to analyze what NFA path was taken.
// Finding a path through the NFA states that results in a DFA state can help
// answer *what* the solution to a problem was, not just that there exists a
// solution.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_SUPPORT_AUTOMATON_H
#define LLVM_SUPPORT_AUTOMATON_H
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Allocator.h"
#include <deque>
#include <map>
#include <memory>
#include <unordered_map>
#include <vector>
namespace llvm {
using NfaPath = SmallVector<uint64_t, 4>;
/// Forward define the pair type used by the automata transition info tables.
///
/// Experimental results with large tables have shown a significant (multiple
/// orders of magnitude) parsing speedup by using a custom struct here with a
/// trivial constructor rather than std::pair<uint64_t, uint64_t>.
struct NfaStatePair {
uint64_t FromDfaState, ToDfaState;
bool operator<(const NfaStatePair &Other) const {
return std::make_tuple(FromDfaState, ToDfaState) <
std::make_tuple(Other.FromDfaState, Other.ToDfaState);
}
};
namespace internal {
/// The internal class that maintains all possible paths through an NFA based
/// on a path through the DFA.
class NfaTranscriber {
private:
/// Cached transition table. This is a table of NfaStatePairs that contains
/// zero-terminated sequences pointed to by DFA transitions.
ArrayRef<NfaStatePair> TransitionInfo;
/// A simple linked-list of traversed states that can have a shared tail. The
/// traversed path is stored in reverse order with the latest state as the
/// head.
struct PathSegment {
uint64_t State;
PathSegment *Tail;
};
/// We allocate segment objects frequently. Allocate them upfront and dispose
/// at the end of a traversal rather than hammering the system allocator.
SpecificBumpPtrAllocator<PathSegment> Allocator;
/// Heads of each tracked path. These are not ordered.
std::deque<PathSegment *> Heads;
/// The returned paths. This is populated during getPaths.
SmallVector<NfaPath, 4> Paths;
/// Create a new segment and return it.
PathSegment *makePathSegment(uint64_t State, PathSegment *Tail) {
PathSegment *P = Allocator.Allocate();
*P = {State, Tail};
return P;
}
/// Pairs defines a sequence of possible NFA transitions for a single DFA
/// transition.
void transition(ArrayRef<NfaStatePair> Pairs) {
// Iterate over all existing heads. We will mutate the Heads deque during
// iteration.
unsigned NumHeads = Heads.size();
for (unsigned I = 0; I < NumHeads; ++I) {
PathSegment *Head = Heads[I];
// The sequence of pairs is sorted. Select the set of pairs that
// transition from the current head state.
auto PI = lower_bound(Pairs, NfaStatePair{Head->State, 0ULL});
auto PE = upper_bound(Pairs, NfaStatePair{Head->State, INT64_MAX});
// For every transition from the current head state, add a new path
// segment.
for (; PI != PE; ++PI)
if (PI->FromDfaState == Head->State)
Heads.push_back(makePathSegment(PI->ToDfaState, Head));
}
// Now we've iterated over all the initial heads and added new ones,
// dispose of the original heads.
Heads.erase(Heads.begin(), std::next(Heads.begin(), NumHeads));
}
public:
NfaTranscriber(ArrayRef<NfaStatePair> TransitionInfo)
: TransitionInfo(TransitionInfo) {
reset();
}
ArrayRef<NfaStatePair> getTransitionInfo() const {
return TransitionInfo;
}
void reset() {
Paths.clear();
Heads.clear();
Allocator.DestroyAll();
// The initial NFA state is 0.
Heads.push_back(makePathSegment(0ULL, nullptr));
}
void transition(unsigned TransitionInfoIdx) {
unsigned EndIdx = TransitionInfoIdx;
while (TransitionInfo[EndIdx].ToDfaState != 0)
++EndIdx;
ArrayRef<NfaStatePair> Pairs(&TransitionInfo[TransitionInfoIdx],
EndIdx - TransitionInfoIdx);
transition(Pairs);
}
ArrayRef<NfaPath> getPaths() {
Paths.clear();
for (auto *Head : Heads) {
NfaPath P;
while (Head->State != 0) {
P.push_back(Head->State);
Head = Head->Tail;
}
std::reverse(P.begin(), P.end());
Paths.push_back(std::move(P));
}
return Paths;
}
};
} // namespace internal
/// A deterministic finite-state automaton. The automaton is defined in
/// TableGen; this object drives an automaton defined by tblgen-emitted tables.
///
/// An automaton accepts a sequence of input tokens ("actions"). This class is
/// templated on the type of these actions.
template <typename ActionT> class Automaton {
/// Map from {State, Action} to {NewState, TransitionInfoIdx}.
/// TransitionInfoIdx is used by the DfaTranscriber to analyze the transition.
/// FIXME: This uses a std::map because ActionT can be a pair type including
/// an enum. In particular DenseMapInfo<ActionT> must be defined to use
/// DenseMap here.
/// This is a shared_ptr to allow very quick copy-construction of Automata; this
/// state is immutable after construction so this is safe.
using MapTy = std::map<std::pair<uint64_t, ActionT>, std::pair<uint64_t, unsigned>>;
std::shared_ptr<MapTy> M;
/// An optional transcription object. This uses much more state than simply
/// traversing the DFA for acceptance, so is heap allocated.
std::shared_ptr<internal::NfaTranscriber> Transcriber;
/// The initial DFA state is 1.
uint64_t State = 1;
/// True if we should transcribe and false if not (even if Transcriber is defined).
bool Transcribe;
public:
/// Create an automaton.
/// \param Transitions The Transitions table as created by TableGen. Note that
/// because the action type differs per automaton, the
/// table type is templated as ArrayRef<InfoT>.
/// \param TranscriptionTable The TransitionInfo table as created by TableGen.
///
/// Providing the TranscriptionTable argument as non-empty will enable the
/// use of transcription, which analyzes the possible paths in the original
/// NFA taken by the DFA. NOTE: This is substantially more work than simply
/// driving the DFA, so unless you require the getPaths() method leave this
/// empty.
template <typename InfoT>
Automaton(ArrayRef<InfoT> Transitions,
ArrayRef<NfaStatePair> TranscriptionTable = {}) {
if (!TranscriptionTable.empty())
Transcriber =
std::make_shared<internal::NfaTranscriber>(TranscriptionTable);
Transcribe = Transcriber != nullptr;
M = std::make_shared<MapTy>();
for (const auto &I : Transitions)
// Greedily read and cache the transition table.
M->emplace(std::make_pair(I.FromDfaState, I.Action),
std::make_pair(I.ToDfaState, I.InfoIdx));
}
Automaton(const Automaton &Other)
: M(Other.M), State(Other.State), Transcribe(Other.Transcribe) {
// Transcriber is not thread-safe, so create a new instance on copy.
if (Other.Transcriber)
Transcriber = std::make_shared<internal::NfaTranscriber>(
Other.Transcriber->getTransitionInfo());
}
/// Reset the automaton to its initial state.
void reset() {
State = 1;
if (Transcriber)
Transcriber->reset();
}
/// Enable or disable transcription. Transcription is only available if
/// TranscriptionTable was provided to the constructor.
void enableTranscription(bool Enable = true) {
assert(Transcriber &&
"Transcription is only available if TranscriptionTable was provided "
"to the Automaton constructor");
Transcribe = Enable;
}
/// Transition the automaton based on input symbol A. Return true if the
/// automaton transitioned to a valid state, false if the automaton
/// transitioned to an invalid state.
///
/// If this function returns false, all methods are undefined until reset() is
/// called.
bool add(const ActionT &A) {
auto I = M->find({State, A});
if (I == M->end())
return false;
if (Transcriber && Transcribe)
Transcriber->transition(I->second.second);
State = I->second.first;
return true;
}
/// Return true if the automaton can be transitioned based on input symbol A.
bool canAdd(const ActionT &A) {
auto I = M->find({State, A});
return I != M->end();
}
/// Obtain a set of possible paths through the input nondeterministic
/// automaton that could be obtained from the sequence of input actions
/// presented to this deterministic automaton.
ArrayRef<NfaPath> getNfaPaths() {
assert(Transcriber && Transcribe &&
"Can only obtain NFA paths if transcribing!");
return Transcriber->getPaths();
}
};
} // namespace llvm
#endif // LLVM_SUPPORT_AUTOMATON_H