utils/TableGen/DFAEmitter.h

   1 //===--------------------- DfaEmitter.h -----------------------------------===//
   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 // Defines a generic automaton builder. This takes a set of transitions and
   9 // states that represent a nondeterministic finite state automaton (NFA) and
  10 // emits a determinized DFA in a form that include/llvm/Support/Automaton.h can
  11 // drive.
  12 //
  13 // See file llvm/TableGen/Automaton.td for the TableGen API definition.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #ifndef LLVM_UTILS_TABLEGEN_DFAEMITTER_H
  18 #define LLVM_UTILS_TABLEGEN_DFAEMITTER_H
  19
  20 #include "llvm/ADT/StringRef.h"
  21 #include "llvm/ADT/UniqueVector.h"
  22 #include "llvm/Support/raw_ostream.h"
  23 #include "llvm/TableGen/Record.h"
  24 #include <set>
  25 #include <unordered_map>
  26
  27 namespace llvm {
  28
  29 class raw_ostream;
  30 /// Construct a deterministic finite state automaton from possible
  31 /// nondeterministic state and transition data.
  32 ///
  33 /// The state type is a 64-bit unsigned integer. The generated automaton is
  34 /// invariant to the sparsity of the state representation - its size is only
  35 /// a function of the cardinality of the set of states.
  36 ///
  37 /// The inputs to this emitter are considered to define a nondeterministic
  38 /// finite state automaton (NFA). This is then converted to a DFA during
  39 /// emission. The emitted tables can be used to by
  40 /// include/llvm/Support/Automaton.h.
  41 class DfaEmitter {
  42 public:
  43   // The type of an NFA state. The initial state is always zero.
  44   using state_type = uint64_t;
  45   // The type of an action.
  46   using action_type = uint64_t;
  47
  48   DfaEmitter() = default;
  49   virtual ~DfaEmitter() = default;
  50
  51   void addTransition(state_type From, state_type To, action_type A);
  52   void emit(StringRef Name, raw_ostream &OS);
  53
  54 protected:
  55   /// Emit the C++ type of an action to OS.
  56   virtual void printActionType(raw_ostream &OS);
  57   /// Emit the C++ value of an action A to OS.
  58   virtual void printActionValue(action_type A, raw_ostream &OS);
  59
  60 private:
  61   /// The state type of deterministic states. These are only used internally to
  62   /// this class. This is an ID into the DfaStates UniqueVector.
  63   using dfa_state_type = unsigned;
  64
  65   /// The actual representation of a DFA state, which is a union of one or more
  66   /// NFA states.
  67   using DfaState = SmallVector<state_type, 4>;
  68
  69   /// A DFA transition consists of a set of NFA states transitioning to a
  70   /// new set of NFA states. The DfaTransitionInfo tracks, for every
  71   /// transitioned-from NFA state, a set of valid transitioned-to states.
  72   ///
  73   /// Emission of this transition relation allows algorithmic determination of
  74   /// the possible candidate NFA paths taken under a given input sequence to
  75   /// reach a given DFA state.
  76   using DfaTransitionInfo = SmallVector<std::pair<state_type, state_type>, 4>;
  77
  78   /// The set of all possible actions.
  79   std::set<action_type> Actions;
  80
  81   /// The set of nondeterministic transitions. A state-action pair can
  82   /// transition to multiple target states.
  83   std::map<std::pair<state_type, action_type>, std::vector<state_type>>
  84       NfaTransitions;
  85   std::set<state_type> NfaStates;
  86   unsigned NumNfaTransitions = 0;
  87
  88   /// The set of deterministic states. DfaStates.getId(DfaState) returns an ID,
  89   /// which is dfa_state_type. Note that because UniqueVector reserves state
  90   /// zero, the initial DFA state is always 1.
  91   UniqueVector<DfaState> DfaStates;
  92   /// The set of deterministic transitions. A state-action pair has only a
  93   /// single target state.
  94   std::map<std::pair<dfa_state_type, action_type>,
  95            std::pair<dfa_state_type, DfaTransitionInfo>>
  96       DfaTransitions;
  97
  98   /// Visit all NFA states and construct the DFA.
  99   void constructDfa();
 100   /// Visit a single DFA state and construct all possible transitions to new DFA
 101   /// states.
 102   void visitDfaState(DfaState DS);
 103 };
 104
 105 } // namespace llvm
 106
 107 #endif