18bcb0991SDimitry Andric //===- DFAEmitter.cpp - Finite state automaton emitter --------------------===// 28bcb0991SDimitry Andric // 38bcb0991SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 48bcb0991SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 58bcb0991SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 68bcb0991SDimitry Andric // 78bcb0991SDimitry Andric //===----------------------------------------------------------------------===// 88bcb0991SDimitry Andric // 98bcb0991SDimitry Andric // This class can produce a generic deterministic finite state automaton (DFA), 108bcb0991SDimitry Andric // given a set of possible states and transitions. 118bcb0991SDimitry Andric // 128bcb0991SDimitry Andric // The input transitions can be nondeterministic - this class will produce the 138bcb0991SDimitry Andric // deterministic equivalent state machine. 148bcb0991SDimitry Andric // 158bcb0991SDimitry Andric // The generated code can run the DFA and produce an accepted / not accepted 168bcb0991SDimitry Andric // state and also produce, given a sequence of transitions that results in an 178bcb0991SDimitry Andric // accepted state, the sequence of intermediate states. This is useful if the 188bcb0991SDimitry Andric // initial automaton was nondeterministic - it allows mapping back from the DFA 198bcb0991SDimitry Andric // to the NFA. 208bcb0991SDimitry Andric // 218bcb0991SDimitry Andric //===----------------------------------------------------------------------===// 228bcb0991SDimitry Andric 238bcb0991SDimitry Andric #include "DFAEmitter.h" 248bcb0991SDimitry Andric #include "SequenceToOffsetTable.h" 258bcb0991SDimitry Andric #include "TableGenBackends.h" 268bcb0991SDimitry Andric #include "llvm/ADT/SmallVector.h" 278bcb0991SDimitry Andric #include "llvm/ADT/StringExtras.h" 288bcb0991SDimitry Andric #include "llvm/ADT/UniqueVector.h" 298bcb0991SDimitry Andric #include "llvm/Support/Debug.h" 308bcb0991SDimitry Andric #include "llvm/Support/raw_ostream.h" 318bcb0991SDimitry Andric #include "llvm/TableGen/Record.h" 328bcb0991SDimitry Andric #include <cassert> 338bcb0991SDimitry Andric #include <cstdint> 3481ad6265SDimitry Andric #include <deque> 358bcb0991SDimitry Andric #include <map> 368bcb0991SDimitry Andric #include <set> 378bcb0991SDimitry Andric #include <string> 38*bdd1243dSDimitry Andric #include <variant> 398bcb0991SDimitry Andric #include <vector> 408bcb0991SDimitry Andric 41fe6060f1SDimitry Andric #define DEBUG_TYPE "dfa-emitter" 42fe6060f1SDimitry Andric 438bcb0991SDimitry Andric using namespace llvm; 448bcb0991SDimitry Andric 458bcb0991SDimitry Andric //===----------------------------------------------------------------------===// 468bcb0991SDimitry Andric // DfaEmitter implementation. This is independent of the GenAutomaton backend. 478bcb0991SDimitry Andric //===----------------------------------------------------------------------===// 488bcb0991SDimitry Andric 498bcb0991SDimitry Andric void DfaEmitter::addTransition(state_type From, state_type To, action_type A) { 508bcb0991SDimitry Andric Actions.insert(A); 518bcb0991SDimitry Andric NfaStates.insert(From); 528bcb0991SDimitry Andric NfaStates.insert(To); 538bcb0991SDimitry Andric NfaTransitions[{From, A}].push_back(To); 548bcb0991SDimitry Andric ++NumNfaTransitions; 558bcb0991SDimitry Andric } 568bcb0991SDimitry Andric 5747395794SDimitry Andric void DfaEmitter::visitDfaState(const DfaState &DS) { 588bcb0991SDimitry Andric // For every possible action... 598bcb0991SDimitry Andric auto FromId = DfaStates.idFor(DS); 608bcb0991SDimitry Andric for (action_type A : Actions) { 618bcb0991SDimitry Andric DfaState NewStates; 628bcb0991SDimitry Andric DfaTransitionInfo TI; 638bcb0991SDimitry Andric // For every represented state, word pair in the original NFA... 6447395794SDimitry Andric for (state_type FromState : DS) { 658bcb0991SDimitry Andric // If this action is possible from this state add the transitioned-to 668bcb0991SDimitry Andric // states to NewStates. 678bcb0991SDimitry Andric auto I = NfaTransitions.find({FromState, A}); 688bcb0991SDimitry Andric if (I == NfaTransitions.end()) 698bcb0991SDimitry Andric continue; 708bcb0991SDimitry Andric for (state_type &ToState : I->second) { 718bcb0991SDimitry Andric NewStates.push_back(ToState); 728bcb0991SDimitry Andric TI.emplace_back(FromState, ToState); 738bcb0991SDimitry Andric } 748bcb0991SDimitry Andric } 758bcb0991SDimitry Andric if (NewStates.empty()) 768bcb0991SDimitry Andric continue; 778bcb0991SDimitry Andric // Sort and unique. 788bcb0991SDimitry Andric sort(NewStates); 798bcb0991SDimitry Andric NewStates.erase(std::unique(NewStates.begin(), NewStates.end()), 808bcb0991SDimitry Andric NewStates.end()); 818bcb0991SDimitry Andric sort(TI); 828bcb0991SDimitry Andric TI.erase(std::unique(TI.begin(), TI.end()), TI.end()); 838bcb0991SDimitry Andric unsigned ToId = DfaStates.insert(NewStates); 848bcb0991SDimitry Andric DfaTransitions.emplace(std::make_pair(FromId, A), std::make_pair(ToId, TI)); 858bcb0991SDimitry Andric } 868bcb0991SDimitry Andric } 878bcb0991SDimitry Andric 888bcb0991SDimitry Andric void DfaEmitter::constructDfa() { 898bcb0991SDimitry Andric DfaState Initial(1, /*NFA initial state=*/0); 908bcb0991SDimitry Andric DfaStates.insert(Initial); 918bcb0991SDimitry Andric 928bcb0991SDimitry Andric // Note that UniqueVector starts indices at 1, not zero. 938bcb0991SDimitry Andric unsigned DfaStateId = 1; 9447395794SDimitry Andric while (DfaStateId <= DfaStates.size()) { 9547395794SDimitry Andric DfaState S = DfaStates[DfaStateId]; 9647395794SDimitry Andric visitDfaState(S); 9747395794SDimitry Andric DfaStateId++; 9847395794SDimitry Andric } 998bcb0991SDimitry Andric } 1008bcb0991SDimitry Andric 1018bcb0991SDimitry Andric void DfaEmitter::emit(StringRef Name, raw_ostream &OS) { 1028bcb0991SDimitry Andric constructDfa(); 1038bcb0991SDimitry Andric 1048bcb0991SDimitry Andric OS << "// Input NFA has " << NfaStates.size() << " states with " 1058bcb0991SDimitry Andric << NumNfaTransitions << " transitions.\n"; 1068bcb0991SDimitry Andric OS << "// Generated DFA has " << DfaStates.size() << " states with " 1078bcb0991SDimitry Andric << DfaTransitions.size() << " transitions.\n\n"; 1088bcb0991SDimitry Andric 1098bcb0991SDimitry Andric // Implementation note: We don't bake a simple std::pair<> here as it requires 1108bcb0991SDimitry Andric // significantly more effort to parse. A simple test with a large array of 1118bcb0991SDimitry Andric // struct-pairs (N=100000) took clang-10 6s to parse. The same array of 1128bcb0991SDimitry Andric // std::pair<uint64_t, uint64_t> took 242s. Instead we allow the user to 1138bcb0991SDimitry Andric // define the pair type. 1148bcb0991SDimitry Andric // 1158bcb0991SDimitry Andric // FIXME: It may make sense to emit these as ULEB sequences instead of 1168bcb0991SDimitry Andric // pairs of uint64_t. 1178bcb0991SDimitry Andric OS << "// A zero-terminated sequence of NFA state transitions. Every DFA\n"; 1188bcb0991SDimitry Andric OS << "// transition implies a set of NFA transitions. These are referred\n"; 1198bcb0991SDimitry Andric OS << "// to by index in " << Name << "Transitions[].\n"; 1208bcb0991SDimitry Andric 1218bcb0991SDimitry Andric SequenceToOffsetTable<DfaTransitionInfo> Table; 1228bcb0991SDimitry Andric std::map<DfaTransitionInfo, unsigned> EmittedIndices; 1238bcb0991SDimitry Andric for (auto &T : DfaTransitions) 1248bcb0991SDimitry Andric Table.add(T.second.second); 1258bcb0991SDimitry Andric Table.layout(); 1265ffd83dbSDimitry Andric OS << "const std::array<NfaStatePair, " << Table.size() << "> " << Name 1278bcb0991SDimitry Andric << "TransitionInfo = {{\n"; 1288bcb0991SDimitry Andric Table.emit( 1298bcb0991SDimitry Andric OS, 1308bcb0991SDimitry Andric [](raw_ostream &OS, std::pair<uint64_t, uint64_t> P) { 1318bcb0991SDimitry Andric OS << "{" << P.first << ", " << P.second << "}"; 1328bcb0991SDimitry Andric }, 1338bcb0991SDimitry Andric "{0ULL, 0ULL}"); 1348bcb0991SDimitry Andric 1358bcb0991SDimitry Andric OS << "}};\n\n"; 1368bcb0991SDimitry Andric 1378bcb0991SDimitry Andric OS << "// A transition in the generated " << Name << " DFA.\n"; 1388bcb0991SDimitry Andric OS << "struct " << Name << "Transition {\n"; 1398bcb0991SDimitry Andric OS << " unsigned FromDfaState; // The transitioned-from DFA state.\n"; 1408bcb0991SDimitry Andric OS << " "; 1418bcb0991SDimitry Andric printActionType(OS); 1428bcb0991SDimitry Andric OS << " Action; // The input symbol that causes this transition.\n"; 1438bcb0991SDimitry Andric OS << " unsigned ToDfaState; // The transitioned-to DFA state.\n"; 1448bcb0991SDimitry Andric OS << " unsigned InfoIdx; // Start index into " << Name 1458bcb0991SDimitry Andric << "TransitionInfo.\n"; 1468bcb0991SDimitry Andric OS << "};\n\n"; 1478bcb0991SDimitry Andric 1488bcb0991SDimitry Andric OS << "// A table of DFA transitions, ordered by {FromDfaState, Action}.\n"; 1498bcb0991SDimitry Andric OS << "// The initial state is 1, not zero.\n"; 1505ffd83dbSDimitry Andric OS << "const std::array<" << Name << "Transition, " 1515ffd83dbSDimitry Andric << DfaTransitions.size() << "> " << Name << "Transitions = {{\n"; 1528bcb0991SDimitry Andric for (auto &KV : DfaTransitions) { 1538bcb0991SDimitry Andric dfa_state_type From = KV.first.first; 1548bcb0991SDimitry Andric dfa_state_type To = KV.second.first; 1558bcb0991SDimitry Andric action_type A = KV.first.second; 1568bcb0991SDimitry Andric unsigned InfoIdx = Table.get(KV.second.second); 1578bcb0991SDimitry Andric OS << " {" << From << ", "; 1588bcb0991SDimitry Andric printActionValue(A, OS); 1598bcb0991SDimitry Andric OS << ", " << To << ", " << InfoIdx << "},\n"; 1608bcb0991SDimitry Andric } 1618bcb0991SDimitry Andric OS << "\n}};\n\n"; 1628bcb0991SDimitry Andric } 1638bcb0991SDimitry Andric 1648bcb0991SDimitry Andric void DfaEmitter::printActionType(raw_ostream &OS) { OS << "uint64_t"; } 1658bcb0991SDimitry Andric 1668bcb0991SDimitry Andric void DfaEmitter::printActionValue(action_type A, raw_ostream &OS) { OS << A; } 1678bcb0991SDimitry Andric 1688bcb0991SDimitry Andric //===----------------------------------------------------------------------===// 1698bcb0991SDimitry Andric // AutomatonEmitter implementation 1708bcb0991SDimitry Andric //===----------------------------------------------------------------------===// 1718bcb0991SDimitry Andric 1728bcb0991SDimitry Andric namespace { 1738bcb0991SDimitry Andric 174*bdd1243dSDimitry Andric using Action = std::variant<Record *, unsigned, std::string>; 1758bcb0991SDimitry Andric using ActionTuple = std::vector<Action>; 1768bcb0991SDimitry Andric class Automaton; 1778bcb0991SDimitry Andric 1788bcb0991SDimitry Andric class Transition { 1798bcb0991SDimitry Andric uint64_t NewState; 1808bcb0991SDimitry Andric // The tuple of actions that causes this transition. 1818bcb0991SDimitry Andric ActionTuple Actions; 1828bcb0991SDimitry Andric // The types of the actions; this is the same across all transitions. 1838bcb0991SDimitry Andric SmallVector<std::string, 4> Types; 1848bcb0991SDimitry Andric 1858bcb0991SDimitry Andric public: 1868bcb0991SDimitry Andric Transition(Record *R, Automaton *Parent); 1878bcb0991SDimitry Andric const ActionTuple &getActions() { return Actions; } 1888bcb0991SDimitry Andric SmallVector<std::string, 4> getTypes() { return Types; } 1898bcb0991SDimitry Andric 1908bcb0991SDimitry Andric bool canTransitionFrom(uint64_t State); 1918bcb0991SDimitry Andric uint64_t transitionFrom(uint64_t State); 1928bcb0991SDimitry Andric }; 1938bcb0991SDimitry Andric 1948bcb0991SDimitry Andric class Automaton { 1958bcb0991SDimitry Andric RecordKeeper &Records; 1968bcb0991SDimitry Andric Record *R; 1978bcb0991SDimitry Andric std::vector<Transition> Transitions; 1988bcb0991SDimitry Andric /// All possible action tuples, uniqued. 1998bcb0991SDimitry Andric UniqueVector<ActionTuple> Actions; 2008bcb0991SDimitry Andric /// The fields within each Transition object to find the action symbols. 2018bcb0991SDimitry Andric std::vector<StringRef> ActionSymbolFields; 2028bcb0991SDimitry Andric 2038bcb0991SDimitry Andric public: 2048bcb0991SDimitry Andric Automaton(RecordKeeper &Records, Record *R); 2058bcb0991SDimitry Andric void emit(raw_ostream &OS); 2068bcb0991SDimitry Andric 2078bcb0991SDimitry Andric ArrayRef<StringRef> getActionSymbolFields() { return ActionSymbolFields; } 2088bcb0991SDimitry Andric /// If the type of action A has been overridden (there exists a field 2098bcb0991SDimitry Andric /// "TypeOf_A") return that, otherwise return the empty string. 2108bcb0991SDimitry Andric StringRef getActionSymbolType(StringRef A); 2118bcb0991SDimitry Andric }; 2128bcb0991SDimitry Andric 2138bcb0991SDimitry Andric class AutomatonEmitter { 2148bcb0991SDimitry Andric RecordKeeper &Records; 2158bcb0991SDimitry Andric 2168bcb0991SDimitry Andric public: 2178bcb0991SDimitry Andric AutomatonEmitter(RecordKeeper &R) : Records(R) {} 2188bcb0991SDimitry Andric void run(raw_ostream &OS); 2198bcb0991SDimitry Andric }; 2208bcb0991SDimitry Andric 2218bcb0991SDimitry Andric /// A DfaEmitter implementation that can print our variant action type. 2228bcb0991SDimitry Andric class CustomDfaEmitter : public DfaEmitter { 2238bcb0991SDimitry Andric const UniqueVector<ActionTuple> &Actions; 2248bcb0991SDimitry Andric std::string TypeName; 2258bcb0991SDimitry Andric 2268bcb0991SDimitry Andric public: 2278bcb0991SDimitry Andric CustomDfaEmitter(const UniqueVector<ActionTuple> &Actions, StringRef TypeName) 2288bcb0991SDimitry Andric : Actions(Actions), TypeName(TypeName) {} 2298bcb0991SDimitry Andric 2308bcb0991SDimitry Andric void printActionType(raw_ostream &OS) override; 2318bcb0991SDimitry Andric void printActionValue(action_type A, raw_ostream &OS) override; 2328bcb0991SDimitry Andric }; 2338bcb0991SDimitry Andric } // namespace 2348bcb0991SDimitry Andric 2358bcb0991SDimitry Andric void AutomatonEmitter::run(raw_ostream &OS) { 2368bcb0991SDimitry Andric for (Record *R : Records.getAllDerivedDefinitions("GenericAutomaton")) { 2378bcb0991SDimitry Andric Automaton A(Records, R); 2388bcb0991SDimitry Andric OS << "#ifdef GET_" << R->getName() << "_DECL\n"; 2398bcb0991SDimitry Andric A.emit(OS); 2408bcb0991SDimitry Andric OS << "#endif // GET_" << R->getName() << "_DECL\n"; 2418bcb0991SDimitry Andric } 2428bcb0991SDimitry Andric } 2438bcb0991SDimitry Andric 2448bcb0991SDimitry Andric Automaton::Automaton(RecordKeeper &Records, Record *R) 2458bcb0991SDimitry Andric : Records(Records), R(R) { 2468bcb0991SDimitry Andric LLVM_DEBUG(dbgs() << "Emitting automaton for " << R->getName() << "\n"); 2478bcb0991SDimitry Andric ActionSymbolFields = R->getValueAsListOfStrings("SymbolFields"); 2488bcb0991SDimitry Andric } 2498bcb0991SDimitry Andric 2508bcb0991SDimitry Andric void Automaton::emit(raw_ostream &OS) { 2518bcb0991SDimitry Andric StringRef TransitionClass = R->getValueAsString("TransitionClass"); 2528bcb0991SDimitry Andric for (Record *T : Records.getAllDerivedDefinitions(TransitionClass)) { 2538bcb0991SDimitry Andric assert(T->isSubClassOf("Transition")); 2548bcb0991SDimitry Andric Transitions.emplace_back(T, this); 2558bcb0991SDimitry Andric Actions.insert(Transitions.back().getActions()); 2568bcb0991SDimitry Andric } 2578bcb0991SDimitry Andric 2588bcb0991SDimitry Andric LLVM_DEBUG(dbgs() << " Action alphabet cardinality: " << Actions.size() 2598bcb0991SDimitry Andric << "\n"); 2608bcb0991SDimitry Andric LLVM_DEBUG(dbgs() << " Each state has " << Transitions.size() 2618bcb0991SDimitry Andric << " potential transitions.\n"); 2628bcb0991SDimitry Andric 2638bcb0991SDimitry Andric StringRef Name = R->getName(); 2648bcb0991SDimitry Andric 2658bcb0991SDimitry Andric CustomDfaEmitter Emitter(Actions, std::string(Name) + "Action"); 2668bcb0991SDimitry Andric // Starting from the initial state, build up a list of possible states and 2678bcb0991SDimitry Andric // transitions. 2688bcb0991SDimitry Andric std::deque<uint64_t> Worklist(1, 0); 2698bcb0991SDimitry Andric std::set<uint64_t> SeenStates; 2708bcb0991SDimitry Andric unsigned NumTransitions = 0; 2718bcb0991SDimitry Andric SeenStates.insert(Worklist.front()); 2728bcb0991SDimitry Andric while (!Worklist.empty()) { 2738bcb0991SDimitry Andric uint64_t State = Worklist.front(); 2748bcb0991SDimitry Andric Worklist.pop_front(); 2758bcb0991SDimitry Andric for (Transition &T : Transitions) { 2768bcb0991SDimitry Andric if (!T.canTransitionFrom(State)) 2778bcb0991SDimitry Andric continue; 2788bcb0991SDimitry Andric uint64_t NewState = T.transitionFrom(State); 2798bcb0991SDimitry Andric if (SeenStates.emplace(NewState).second) 2808bcb0991SDimitry Andric Worklist.emplace_back(NewState); 2818bcb0991SDimitry Andric ++NumTransitions; 2828bcb0991SDimitry Andric Emitter.addTransition(State, NewState, Actions.idFor(T.getActions())); 2838bcb0991SDimitry Andric } 2848bcb0991SDimitry Andric } 2858bcb0991SDimitry Andric LLVM_DEBUG(dbgs() << " NFA automaton has " << SeenStates.size() 2868bcb0991SDimitry Andric << " states with " << NumTransitions << " transitions.\n"); 28781ad6265SDimitry Andric (void) NumTransitions; 2888bcb0991SDimitry Andric 2898bcb0991SDimitry Andric const auto &ActionTypes = Transitions.back().getTypes(); 2908bcb0991SDimitry Andric OS << "// The type of an action in the " << Name << " automaton.\n"; 2918bcb0991SDimitry Andric if (ActionTypes.size() == 1) { 2928bcb0991SDimitry Andric OS << "using " << Name << "Action = " << ActionTypes[0] << ";\n"; 2938bcb0991SDimitry Andric } else { 2948bcb0991SDimitry Andric OS << "using " << Name << "Action = std::tuple<" << join(ActionTypes, ", ") 2958bcb0991SDimitry Andric << ">;\n"; 2968bcb0991SDimitry Andric } 2978bcb0991SDimitry Andric OS << "\n"; 2988bcb0991SDimitry Andric 2998bcb0991SDimitry Andric Emitter.emit(Name, OS); 3008bcb0991SDimitry Andric } 3018bcb0991SDimitry Andric 3028bcb0991SDimitry Andric StringRef Automaton::getActionSymbolType(StringRef A) { 3038bcb0991SDimitry Andric Twine Ty = "TypeOf_" + A; 3048bcb0991SDimitry Andric if (!R->getValue(Ty.str())) 3058bcb0991SDimitry Andric return ""; 3068bcb0991SDimitry Andric return R->getValueAsString(Ty.str()); 3078bcb0991SDimitry Andric } 3088bcb0991SDimitry Andric 3098bcb0991SDimitry Andric Transition::Transition(Record *R, Automaton *Parent) { 3108bcb0991SDimitry Andric BitsInit *NewStateInit = R->getValueAsBitsInit("NewState"); 3118bcb0991SDimitry Andric NewState = 0; 3128bcb0991SDimitry Andric assert(NewStateInit->getNumBits() <= sizeof(uint64_t) * 8 && 3138bcb0991SDimitry Andric "State cannot be represented in 64 bits!"); 3148bcb0991SDimitry Andric for (unsigned I = 0; I < NewStateInit->getNumBits(); ++I) { 3158bcb0991SDimitry Andric if (auto *Bit = dyn_cast<BitInit>(NewStateInit->getBit(I))) { 3168bcb0991SDimitry Andric if (Bit->getValue()) 3178bcb0991SDimitry Andric NewState |= 1ULL << I; 3188bcb0991SDimitry Andric } 3198bcb0991SDimitry Andric } 3208bcb0991SDimitry Andric 3218bcb0991SDimitry Andric for (StringRef A : Parent->getActionSymbolFields()) { 3228bcb0991SDimitry Andric RecordVal *SymbolV = R->getValue(A); 3238bcb0991SDimitry Andric if (auto *Ty = dyn_cast<RecordRecTy>(SymbolV->getType())) { 324*bdd1243dSDimitry Andric Actions.emplace_back(R->getValueAsDef(A)); 3258bcb0991SDimitry Andric Types.emplace_back(Ty->getAsString()); 3268bcb0991SDimitry Andric } else if (isa<IntRecTy>(SymbolV->getType())) { 327*bdd1243dSDimitry Andric Actions.emplace_back(static_cast<unsigned>(R->getValueAsInt(A))); 3288bcb0991SDimitry Andric Types.emplace_back("unsigned"); 329e8d8bef9SDimitry Andric } else if (isa<StringRecTy>(SymbolV->getType())) { 330*bdd1243dSDimitry Andric Actions.emplace_back(std::string(R->getValueAsString(A))); 3318bcb0991SDimitry Andric Types.emplace_back("std::string"); 3328bcb0991SDimitry Andric } else { 3338bcb0991SDimitry Andric report_fatal_error("Unhandled symbol type!"); 3348bcb0991SDimitry Andric } 3358bcb0991SDimitry Andric 3368bcb0991SDimitry Andric StringRef TypeOverride = Parent->getActionSymbolType(A); 3378bcb0991SDimitry Andric if (!TypeOverride.empty()) 3385ffd83dbSDimitry Andric Types.back() = std::string(TypeOverride); 3398bcb0991SDimitry Andric } 3408bcb0991SDimitry Andric } 3418bcb0991SDimitry Andric 3428bcb0991SDimitry Andric bool Transition::canTransitionFrom(uint64_t State) { 3438bcb0991SDimitry Andric if ((State & NewState) == 0) 3448bcb0991SDimitry Andric // The bits we want to set are not set; 3458bcb0991SDimitry Andric return true; 3468bcb0991SDimitry Andric return false; 3478bcb0991SDimitry Andric } 3488bcb0991SDimitry Andric 3498bcb0991SDimitry Andric uint64_t Transition::transitionFrom(uint64_t State) { 3508bcb0991SDimitry Andric return State | NewState; 3518bcb0991SDimitry Andric } 3528bcb0991SDimitry Andric 3538bcb0991SDimitry Andric void CustomDfaEmitter::printActionType(raw_ostream &OS) { OS << TypeName; } 3548bcb0991SDimitry Andric 3558bcb0991SDimitry Andric void CustomDfaEmitter::printActionValue(action_type A, raw_ostream &OS) { 3568bcb0991SDimitry Andric const ActionTuple &AT = Actions[A]; 3578bcb0991SDimitry Andric if (AT.size() > 1) 3588bcb0991SDimitry Andric OS << "std::make_tuple("; 359fe6060f1SDimitry Andric ListSeparator LS; 3608bcb0991SDimitry Andric for (const auto &SingleAction : AT) { 361fe6060f1SDimitry Andric OS << LS; 362*bdd1243dSDimitry Andric if (const auto *R = std::get_if<Record *>(&SingleAction)) 363*bdd1243dSDimitry Andric OS << (*R)->getName(); 364*bdd1243dSDimitry Andric else if (const auto *S = std::get_if<std::string>(&SingleAction)) 365*bdd1243dSDimitry Andric OS << '"' << *S << '"'; 366*bdd1243dSDimitry Andric else 367*bdd1243dSDimitry Andric OS << std::get<unsigned>(SingleAction); 3688bcb0991SDimitry Andric } 3698bcb0991SDimitry Andric if (AT.size() > 1) 3708bcb0991SDimitry Andric OS << ")"; 3718bcb0991SDimitry Andric } 3728bcb0991SDimitry Andric 3738bcb0991SDimitry Andric namespace llvm { 3748bcb0991SDimitry Andric 3758bcb0991SDimitry Andric void EmitAutomata(RecordKeeper &RK, raw_ostream &OS) { 3768bcb0991SDimitry Andric AutomatonEmitter(RK).run(OS); 3778bcb0991SDimitry Andric } 3788bcb0991SDimitry Andric 3798bcb0991SDimitry Andric } // namespace llvm 380