DFAEmitter.h revision 358399 
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
27namespace llvm {
28
29class 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.
41class DfaEmitter {
42public:
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
54protected:
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
60private:
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(const DfaState &DS);
103};
104
105} // namespace llvm
106
107#endif
108