Automaton.h Source File (original) (raw)

26#ifndef LLVM_SUPPORT_AUTOMATON_H

27#define LLVM_SUPPORT_AUTOMATON_H

33#include

34#include

35#include

37namespace llvm {

51 std::make_tuple(Other.FromDfaState, Other.ToDfaState);

52 }

53};

55namespace internal {

59private:

67 struct PathSegment {

69 PathSegment *Tail;

70 };

77 std::deque<PathSegment *> Heads;

83 PathSegment *makePathSegment(uint64_t State, PathSegment *Tail) {

84 PathSegment *P = Allocator.Allocate();

85 *P = {State, Tail};

86 return P;

87 }

94 unsigned NumHeads = Heads.size();

95 for (unsigned I = 0; I < NumHeads; ++I) {

96 PathSegment *Head = Heads[I];

101

102

103 for (; PI != PE; ++PI)

104 if (PI->FromDfaState == Head->State)

105 Heads.push_back(makePathSegment(PI->ToDfaState, Head));

106 }

107

108

109 Heads.erase(Heads.begin(), std::next(Heads.begin(), NumHeads));

110 }

111

112public:

114 : TransitionInfo(TransitionInfo) {

116 }

117

119 return TransitionInfo;

120 }

121

123 Paths.clear();

124 Heads.clear();

125 Allocator.DestroyAll();

126

127 Heads.push_back(makePathSegment(0ULL, nullptr));

128 }

129

131 unsigned EndIdx = TransitionInfoIdx;

132 while (TransitionInfo[EndIdx].ToDfaState != 0)

133 ++EndIdx;

135 EndIdx - TransitionInfoIdx);

136 transition(Pairs);

137 }

138

140 Paths.clear();

141 for (auto *Head : Heads) {

143 while (Head->State != 0) {

144 P.push_back(Head->State);

145 Head = Head->Tail;

146 }

147 std::reverse(P.begin(), P.end());

148 Paths.push_back(std::move(P));

149 }

150 return Paths;

151 }

152};

153}

154

155

156

157

158

159

161

162

163

164

165

166

167

168 using MapTy = std::map<std::pair<uint64_t, ActionT>, std::pair<uint64_t, unsigned>>;

169 std::shared_ptr M;

170

171

172 std::shared_ptrinternal::NfaTranscriber Transcriber;

173

175

176 bool Transcribe;

177

178public:

179

180

181

182

183

184

185

186

187

188

189

190 template

193 if (!TranscriptionTable.empty())

194 Transcriber =

195 std::make_sharedinternal::NfaTranscriber(TranscriptionTable);

196 Transcribe = Transcriber != nullptr;

197 M = std::make_shared();

198 for (const auto &I : Transitions)

199

200 M->emplace(std::make_pair(I.FromDfaState, I.Action),

201 std::make_pair(I.ToDfaState, I.InfoIdx));

202 }

204 : M(Other.M), State(Other.State), Transcribe(Other.Transcribe) {

205

206 if (Other.Transcriber)

207 Transcriber = std::make_sharedinternal::NfaTranscriber(

208 Other.Transcriber->getTransitionInfo());

209 }

210

211

213 State = 1;

214 if (Transcriber)

215 Transcriber->reset();

216 }

217

218

219

221 assert(Transcriber &&

222 "Transcription is only available if TranscriptionTable was provided "

223 "to the Automaton constructor");

225 }

226

227

228

229

230

231

232

233 bool add(const ActionT &A) {

234 auto I = M->find({State, A});

235 if (I == M->end())

236 return false;

237 if (Transcriber && Transcribe)

238 Transcriber->transition(I->second.second);

239 State = I->second.first;

240 return true;

241 }

242

243

245 auto I = M->find({State, A});

246 return I != M->end();

247 }

248

249

250

251

253 assert(Transcriber && Transcribe &&

254 "Can only obtain NFA paths if transcribing!");

255 return Transcriber->getPaths();

256 }

257};

258

259}

260

261#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file defines the BumpPtrAllocator interface.

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

This file defines the DenseMap class.

This file defines the SmallVector class.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

void reset()

Reset the automaton to its initial state.

Definition Automaton.h:212

bool canAdd(const ActionT &A)

Return true if the automaton can be transitioned based on input symbol A.

Definition Automaton.h:244

Automaton(const Automaton &Other)

Definition Automaton.h:203

bool add(const ActionT &A)

Transition the automaton based on input symbol A.

Definition Automaton.h:233

void enableTranscription(bool Enable=true)

Enable or disable transcription.

Definition Automaton.h:220

ArrayRef< NfaPath > getNfaPaths()

Obtain a set of possible paths through the input nondeterministic automaton that could be obtained fr...

Definition Automaton.h:252

Automaton(ArrayRef< InfoT > Transitions, ArrayRef< NfaStatePair > TranscriptionTable={})

Create an automaton.

Definition Automaton.h:191

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

A BumpPtrAllocator that allows only elements of a specific type to be allocated.

NfaTranscriber(ArrayRef< NfaStatePair > TransitionInfo)

Definition Automaton.h:113

ArrayRef< NfaPath > getPaths()

Definition Automaton.h:139

void transition(unsigned TransitionInfoIdx)

Definition Automaton.h:130

void reset()

Definition Automaton.h:122

ArrayRef< NfaStatePair > getTransitionInfo() const

Definition Automaton.h:118

@ 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...

SmallVector< uint64_t, 4 > NfaPath

Definition Automaton.h:39

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.

Definition Automaton.h:46

bool operator<(const NfaStatePair &Other) const

Definition Automaton.h:49

uint64_t FromDfaState

Definition Automaton.h:47

uint64_t ToDfaState

Definition Automaton.h:47