Source

`stdlib/regex/regex.cpp`

2// Original work; see ACKNOWLEDGMENTS.md for the open-source ideas we build upon.

3#include <stdexcept>

4#include "regex.hpp"

6#include <algorithm>

7#include <array>

8#include <bit>

9#include <cstdint>

10#include <cstring>

11#include <memory>

12#include <string>

13#include <string_view>

14#include <unordered_map>

15#include <vector>

17// A from-scratch, linear-time regex engine: the pattern compiles to a Thompson NFA and runs as

18// a lazy DFA (RE2-style). Matching touches only the input bytes (via string_view) and integer

19// program-counters — it NEVER allocates an intermediate string. The compiled program and its

20// DFA cache live in one heap-owned `Dfa` that a `Pattern` shares, so reuse is fast.

21namespace cheatah::regex {

23namespace {

25struct Inst {

26 enum Op : std::uint8_t { Byte, Split, Jmp, Match } op = Match;

27 std::uint64_t cls[4] = {0, 0, 0, 0}; // 256-bit accept set for Byte

28 int x = 0, y = 0; // targets

29};

31// ---- 256-bit byte class helpers ------------------------------------------------------

32void set_bit(std::uint64_t cls[4], unsigned char b) { cls[b >> 6] |= (std::uint64_t{1} << (b & 63)); }

33bool has_bit(const std::uint64_t cls[4], unsigned char b) { return (cls[b >> 6] >> (b & 63)) & 1u; }

34void set_range(std::uint64_t cls[4], unsigned lo, unsigned hi) {

35 for (unsigned c = lo; c <= hi; ++c) set_bit(cls, static_cast<unsigned char>(c));

36}

37void negate(std::uint64_t cls[4]) { for (int i = 0; i < 4; ++i) cls[i] = ~cls[i]; }

39// ---- the compiler: regex source -> NFA program (Thompson construction) ----------------

40struct Hole { int inst; int field; }; // a dangling exit: (instruction, 0=x|1=y)

41struct Frag { int start; std::vector<Hole> holes; };

43// Maximum group-nesting depth accepted by the recursive-descent parser. `(((…` recurses one

44// parse_atom→parse_alt cycle per '(', so an unbounded pattern would overflow the C++ stack before

45// it could even report "unbalanced '('". 1000 is far beyond any real pattern. Patterns are

46// developer-supplied today, but a program that compiles a regex from untrusted text (e.g. a

47// user-supplied filter) would otherwise crash on a crafted pattern.

48inline constexpr int kMaxParseDepth = 1000;

50// Maximum accepted pattern length. compile() spends O(m) memory — roughly 40 bytes of NFA

51// program per pattern byte — so an unbounded hostile pattern is a ~40x memory-amplification

52// DoS that the nesting cap above does not cover (it bounds depth, not breadth). 64 KiB is

53// orders of magnitude beyond any real pattern; longer input is rejected as malformed.

54inline constexpr std::size_t kMaxPatternLength = 64 * 1024;

56struct Compiler {

57 std::string_view src;

58 std::size_t i = 0;

59 std::vector<Inst> prog;

60 std::string err;

61 int depth = 0; // current group-nesting recursion depth (see kMaxParseDepth)

62 bool reversed = false; // emit the byte-reversed program: rev(A·B) = rev(B)·rev(A)

64 bool eof() const { return i >= src.size(); }

65 char peek() const { return i < src.size() ? src[i] : '\0'; }

66 char get() { return src[i++]; }

67 int emit(const Inst& in) { prog.push_back(in); return static_cast<int>(prog.size()) - 1; }

68 void patch(const std::vector<Hole>& holes, int target) {

69 for (const Hole& h : holes) (h.field == 0 ? prog[h.inst].x : prog[h.inst].y) = target;

70 }

72 Frag byte_frag(const std::uint64_t cls[4]) {

73 Inst in; in.op = Inst::Byte;

74 for (int k = 0; k < 4; ++k) in.cls[k] = cls[k];

75 int s = emit(in);

76 return Frag{s, {{s, 0}}};

77 }

79 bool escape_class(char c, std::uint64_t cls[4]) {

80 switch (c) {

81 case 'd': set_range(cls, '0', '9'); return true;

82 case 'w': set_range(cls, 'a', 'z'); set_range(cls, 'A', 'Z');

83 set_range(cls, '0', '9'); set_bit(cls, '_'); return true;

84 case 's': set_bit(cls, ' '); set_bit(cls, '\t'); set_bit(cls, '\n');

85 set_bit(cls, '\r'); set_bit(cls, '\f'); set_bit(cls, '\v'); return true;

86 case 'D': case 'W': case 'S': {

87 std::uint64_t base[4] = {0, 0, 0, 0};

88 escape_class(static_cast<char>(c + 32), base);

89 negate(base);

90 for (int k = 0; k < 4; ++k) cls[k] |= base[k];

91 return true;

92 }

93 default: return false;

94 }

95 }

97 Frag parse_alt() {

98 Frag left = parse_concat();

99 while (err.empty() && peek() == '|') {

100 get();

101 Frag right = parse_concat();

102 if (!err.empty()) return left;

103 Inst sp; sp.op = Inst::Split; sp.x = left.start; sp.y = right.start;

104 int s = emit(sp);

105 Frag f; f.start = s; f.holes = left.holes;

106 f.holes.insert(f.holes.end(), right.holes.begin(), right.holes.end());

107 left = f;

108 }

109 return left;

110 }

111

112 Frag parse_concat() {

113 Frag acc; acc.start = -1;

114 while (err.empty() && !eof() && peek() != '|' && peek() != ')') {

115 Frag r = parse_repeat();

116 if (!err.empty()) return acc;

117 if (acc.start == -1) acc = r;

118 else if (!reversed) { patch(acc.holes, r.start); acc.holes = r.holes; }

119 else { patch(r.holes, acc.start); acc.start = r.start; } // concatenate backwards

120 }

121 if (acc.start == -1) { // empty -> an epsilon Jmp pass-through

122 Inst j; j.op = Inst::Jmp; int s = emit(j);

123 acc.start = s; acc.holes = {{s, 0}};

124 }

125 return acc;

126 }

127

128 Frag parse_repeat() {

129 Frag a = parse_atom();

130 while (err.empty() && (peek() == '*' || peek() == '+' || peek() == '?')) {

131 char q = get();

132 Inst sp; sp.op = Inst::Split;

133 if (q == '*') {

134 sp.x = a.start; int s = emit(sp);

135 patch(a.holes, s);

136 a = Frag{s, {{s, 1}}};

137 } else if (q == '+') {

138 sp.x = a.start; int s = emit(sp);

139 patch(a.holes, s);

140 a = Frag{a.start, {{s, 1}}};

141 } else { // '?'

142 sp.x = a.start; int s = emit(sp);

143 Frag f; f.start = s; f.holes = a.holes; f.holes.push_back({s, 1});

144 a = f;

145 }

146 }

147 return a;

148 }

149

150 Frag parse_atom() {

151 char c = peek();

152 if (c == '(') {

153 get();

154 if (++depth > kMaxParseDepth) { err = "pattern nested too deeply"; return {}; }

155 Frag inner = parse_alt();

156 --depth;

157 if (!err.empty()) return inner; // keep the inner error (depth cap, bad metachar, …)

158 if (peek() != ')') { err = "unbalanced '('"; return inner; }

159 get();

160 return inner;

161 }

162 if (c == '[') return parse_class();

163 if (c == '.') { // any byte except newline

164 get();

165 std::uint64_t cls[4] = {~std::uint64_t{0}, ~std::uint64_t{0}, ~std::uint64_t{0}, ~std::uint64_t{0}};

166 cls['\n' >> 6] &= ~(std::uint64_t{1} << ('\n' & 63));

167 return byte_frag(cls);

168 }

169 if (c == '\\') {

170 get();

171 if (eof()) { err = "trailing backslash"; return {}; }

172 char e = get();

173 std::uint64_t cls[4] = {0, 0, 0, 0};

174 if (escape_class(e, cls)) return byte_frag(cls);

175 set_bit(cls, static_cast<unsigned char>(e)); // escaped literal

176 return byte_frag(cls);

177 }

178 if (c == ')' || c == '|' || c == '*' || c == '+' || c == '?') { err = "unexpected metacharacter"; return {}; }

179 get();

180 std::uint64_t cls[4] = {0, 0, 0, 0};

181 set_bit(cls, static_cast<unsigned char>(c));

182 return byte_frag(cls);

183 }

184

185 Frag parse_class() {

186 get(); // '['

187 bool neg = false;

188 if (peek() == '^') { get(); neg = true; }

189 std::uint64_t cls[4] = {0, 0, 0, 0};

190 bool first = true;

191 while (!eof() && (peek() != ']' || first)) {

192 first = false;

193 char c = get();

194 if (c == '\\' && !eof()) {

195 char e = get();

196 std::uint64_t sub[4] = {0, 0, 0, 0};

197 if (escape_class(e, sub)) { for (int k = 0; k < 4; ++k) cls[k] |= sub[k]; continue; }

198 c = e;

199 }

200 if (peek() == '-' && i + 1 < src.size() && src[i + 1] != ']') {

201 get();

202 char hi = get();

203 set_range(cls, static_cast<unsigned char>(c), static_cast<unsigned char>(hi));

204 } else {

205 set_bit(cls, static_cast<unsigned char>(c));

206 }

207 }

208 if (peek() != ']') { err = "unbalanced '['"; return {}; }

209 get();

210

        if (neg) { negate(cls); cls['\n' >> 6] &= ~(std::uint64_t{1} << ('\n' & 63)); }  // negated class excludes newline

211 return byte_frag(cls);

212 }

213};

214

215} // namespace

216

217/// The compiled Thompson-NFA program plus its lazy-DFA cache — an internal implementation type

218/// (@ref Pattern holds one by `shared_ptr`; not part of the public surface).

219struct Dfa {

220 std::vector<Inst> prog; ///< the compiled Thompson-NFA program.

221 int start_unanchored = 0; ///< program entry pc for an unanchored start.

222 int start_anchored = 0; ///< program entry pc for an anchored start.

223 bool anchored_start = false; ///< whether the pattern is anchored at the start (`^`).

224 bool anchored_end = false; ///< whether the pattern is anchored at the end (`$`).

225

226 std::unordered_map<std::string, int> intern; ///< canonical (sorted) pc-set key -> DFA state id.

227 std::vector<std::vector<int>> pcs; ///< per-state pc set.

228 std::vector<char> accepts; ///< per-state "accepting" flag.

229 std::vector<int> tflat; ///< flat transition table: @ref kRowInts ints per state (256

230 ///< packed next-state entries + the accept flag in slot

231 ///< @ref kFlagSlot); -1 = uncomputed.

232

233 std::uint64_t first[4] = {0, 0, 0, 0}; ///< bitset of bytes an anchored match can START with.

234 int first_count = 0; ///< popcount of `first` (0 = unknown / matches empty).

235 unsigned char first_byte = 0; ///< the single required first byte when `first_count == 1`.

236 bool matches_empty = false; ///< the pattern can match the empty string at any position.

237 std::array<unsigned char, 256> in_first{}; ///< byte-indexed `first` membership (the skip

238 ///< LUT), built on first use — see `in_first_ready`.

239 bool in_first_ready = false; ///< whether `in_first` has been expanded from `first` yet.

240 /// Bytes whose transition FROM the unanchored start returns the unanchored start itself —

241 /// provably free to skip in an existence scan (the tracked start-set is unchanged), even

242 /// when they're in @ref first (`(a|a)*c` over "aaaa": 'a' loops the start state forever).

243 /// Learned lazily as those transitions are first computed; unknown bytes just step.

244 std::array<unsigned char, 256> ustart_self{};

245 std::string lit; ///< the literal chain the pattern must start with (empty when shorter than 2).

246 int astart_id = -1; ///< interned DFA id of the anchored start state (-1 until first use).

247 int ustart_id = -1; ///< interned DFA id of the unanchored start state (-1 until first use).

248 std::unique_ptr<Dfa> rev; ///< the reversed program (built only for `$`-only-anchored patterns).

249

250 /// Hot-loop state values ARE their row's BYTE OFFSET into the flat transition table:

251 /// each state's row is @ref kRowInts ints — 256 transitions plus, in slot 256, the

252 /// state's accept flag. A transition is one `[table_bytes + state + byte*4]` load (the

253 /// byte-side arithmetic is off the dependent chain, so the carried latency is a single

254 /// simple load — RE2's chain, without its bytemap indirection), and the accept test is

255 /// an independent load of the row's flag slot that never extends the chain. The dead

256 /// state is id 0, so its offset is 0, its all-zero row self-loops, and the dead test

257 /// stays `state == 0`.

258 static constexpr int kRowInts = 257;

259 /// One row's size in bytes — the stride between consecutive packed state values.

260 static constexpr int kRowBytes = kRowInts * static_cast<int>(sizeof(int));

261 /// The in-row index of the accept flag (right after the 256 transition entries).

262 static constexpr int kFlagSlot = 256;

263

264 /// @param id a raw interned state id. @return the state's packed value: its row's byte

265 /// offset into @ref tflat (the accept flag lives inside the row, not in the value).

266 /// @complexity O(1). @alloc none. @test Regex.FullMatchIsAnchoredBothEnds

267 static int pack(int id) { return id * kRowBytes; }

268

269 /// The PACKED start id for program entry @p entry, cached (packed) in @p slot so the

270 /// closure walk, its allocations, AND the accept-flag pack happen once per pattern, not

271 /// once per call. The first call also seeds state id 0 as the canonical DEAD state

272 /// (empty pc set, self-looping all-zero transition row, no accept): every empty closure

273 /// interns to it for free, and the hot loops' dead test is one compare against 0.

274 /// @param entry the program entry pc. @param slot the cache slot (`astart_id`/`ustart_id`).

275 /// @return the packed start state id.

276 /// @complexity O(program size) on the first call; O(1) after.

277 /// @alloc first call only: the id-0 bookkeeping + closure scratch + interned state.

278 /// @test Regex.PatternIsReusableAndCheapToCopy

279 int cached_start(int entry, int& slot) {

280 if (slot >= 0) return slot; // the hot path — everything below runs once per pattern

281 if (pcs.empty()) {

282 intern.emplace(std::string(), 0);

283 pcs.emplace_back();

284 accepts.push_back(0);

285 tflat.assign(static_cast<std::size_t>(kRowInts), 0);

286 }

287 slot = pack(start_state(entry));

288 return slot;

289 }

290

291 /// Add the epsilon-closure of @p pc to @p out. @param pc start program counter.

292 /// @param out accumulates the reachable Byte/Match pcs. @param seen per-pc visited flags.

293 /// @complexity O(program size) — the worklist visits each pc at most once (@p seen).

294 /// @alloc the local worklist vector (the caller owns @p out / @p seen).

295 /// @test RegexE2E.SearchPresentAbsent

296 void add_closure(int pc, std::vector<int>& out, std::vector<char>& seen) const {

297 // Iterative worklist rather than recursion: a long epsilon chain (`a?`×N, nested

298 // alternations) makes the closure O(pattern length) deep, which as recursion overflowed the

299 // C++ stack on a valid pattern. The membership set `out` is sorted+de-duplicated by the

300 // caller (intern_state) and only its CONTENTS matter (state identity, accept flag, first-byte

301 // OR), so the visitation order here is irrelevant — an explicit stack is equivalent.

302 std::vector<int> work;

303 work.push_back(pc);

304 while (!work.empty()) {

305 const int p = work.back();

306 work.pop_back();

307 if (p < 0 || seen[p]) continue;

308 seen[p] = 1;

309 const Inst& in = prog[p];

310 if (in.op == Inst::Jmp) work.push_back(in.x);

311 else if (in.op == Inst::Split) { work.push_back(in.x); work.push_back(in.y); }

312 else out.push_back(p); // Byte or Match — a real state

313 }

314 }

315

316 /// Hard ceiling on distinct lazy-DFA states. Subset construction can in theory create up to

317 /// 2^(NFA states) DFA states — a ~30-`.` pattern is enough — each costing a @ref kRowInts-int

318 /// transition row (~1 KiB), so an uncapped cache is a memory-exhaustion DoS on a crafted

319 /// pattern (RE2, the model, bounds its cache and falls back). Matching TIME stays linear; this

320 /// bounds only MEMORY. 100k states (~100 MiB ceiling) is orders of magnitude beyond any real

321 /// pattern; exceeding it throws rather than OOMs, so a caller can catch a pathological pattern.

322 static constexpr std::size_t kMaxStates = 100000;

323

324 /// Intern a pc @p set into a canonical DFA state (creating it if new).

325 /// @param set the pc set for the state. @return the state id.

326 /// @complexity O(|set| log |set|) for the canonical sort, then an amortized-O(|set|)

327 /// hash lookup; throws past @ref kMaxStates instead of exhausting memory.

328 /// @alloc the canonical key string; a NEW state also stores its pc set and grows the

329 /// flat transition table by one @ref kRowInts-entry row (256 transitions + the accept

330 /// flag slot). An existing state allocates the key only.

331 /// @test RegexE2E.ReDoSNestedQuantifierReturnsFalseFast

332 int intern_state(std::vector<int> set) {

333 std::sort(set.begin(), set.end());

334 set.erase(std::unique(set.begin(), set.end()), set.end());

335 std::string key(reinterpret_cast<const char*>(set.data()), set.size() * sizeof(int));

336 auto it = intern.find(key);

337 if (it != intern.end()) return it->second;

338 if (pcs.size() >= kMaxStates)

339 throw std::runtime_error("regex: DFA state budget exceeded (pathological pattern)");

340 int id = static_cast<int>(pcs.size());

341 bool acc = false;

342 for (int pc : set) if (prog[pc].op == Inst::Match) acc = true;

343 intern.emplace(std::move(key), id);

344 pcs.push_back(std::move(set));

345 accepts.push_back(acc ? 1 : 0);

346 tflat.resize(tflat.size() + kRowInts, -1);

347 tflat[static_cast<std::size_t>(id) * kRowInts + kFlagSlot] = acc ? 1 : 0;

348 return id;

349 }

350

351 /// The start DFA state for program entry @p entry. @param entry the program entry pc.

352 /// @return the interned start state id.

353 /// @complexity O(program size) — one closure walk plus the intern.

354 /// @alloc closure scratch (the pc vector + per-pc visited flags), then whatever

355 /// @ref intern_state keeps for the state.

356 /// @test RegexE2E.Anchors

357 int start_state(int entry) {

358 std::vector<int> out;

359 std::vector<char> seen(prog.size(), 0);

360 add_closure(entry, out, seen);

361 return intern_state(std::move(out));

362 }

363

364 /// Transition from PACKED @p state on input byte @p b, lazily filling the cache.

365 /// @param state the current packed state id (its row's byte offset). @param b the input

366 /// byte. @return the next packed state id; the accept flag is read separately from the

367 /// destination row's @ref kFlagSlot, off the loop-carried chain.

368 /// @complexity O(1) on a cached transition — one table load; a cache miss pays one

369 /// O(program size) closure walk and interns the successor (this is the "lazy" in

370 /// lazy-DFA — each (state, byte) pair is computed at most once, keeping match time

371 /// linear).

372 /// @alloc none on a cache hit; a miss allocates closure scratch plus whatever

373 /// @ref intern_state keeps.

374 /// @test RegexE2E.SearchPresentAbsent

375 int step(int state, unsigned char b) {

376 const std::size_t slot = static_cast<std::size_t>(state) / sizeof(int) + b;

377 int cached = tflat[slot];

378 if (cached != -1) return cached;

379 std::vector<int> out;

380 std::vector<char> seen(prog.size(), 0);

381 for (int pc : pcs[static_cast<std::size_t>(state) / kRowBytes]) {

382 const Inst& in = prog[pc];

383 if (in.op == Inst::Byte && has_bit(in.cls, b)) add_closure(in.x, out, seen);

384 }

385 int next = pack(intern_state(std::move(out))); // may grow tflat -> index AFTER, not before

386 tflat[slot] = next;

387 return next;

388 }

389};

390

391Pattern compile(std::string_view pattern) {

392 Pattern out;

393 if (pattern.size() > kMaxPatternLength) {

394 out.error = "pattern too long";

395 return out;

396 }

397 auto dfa = std::make_shared<Dfa>();

398 if (!pattern.empty() && pattern.front() == '^') { dfa->anchored_start = true; pattern.remove_prefix(1); }

399 if (!pattern.empty() && pattern.back() == '$') { dfa->anchored_end = true; pattern.remove_suffix(1); }

400

401 Compiler c;

402 c.prog.reserve(pattern.size() + 4); // ~one instruction per pattern byte + prefix + match

403 // Slots 0..1 = the unanchored `.*?` prefix, so an unanchored search begins a match at ANY

404 // position with no per-position work: 0: Split(body, 1); 1: Byte(any) -> 0.

405 c.emit(Inst{});

406 Inst anybyte; anybyte.op = Inst::Byte;

407 for (int k = 0; k < 4; ++k) anybyte.cls[k] = ~std::uint64_t{0};

408 anybyte.x = 0;

409 c.emit(anybyte);

410 c.src = pattern;

411

412 Frag f = c.parse_alt();

413 if (c.err.empty() && c.i != c.src.size()) c.err = "unexpected trailing input";

414 if (!c.err.empty()) { out.error = c.err; return out; }

415

416 Inst m; m.op = Inst::Match;

417 int match_pc = c.emit(m);

418 c.patch(f.holes, match_pc);

419 c.prog[0].op = Inst::Split;

420 c.prog[0].x = f.start; // anchored entry: the pattern body

421 c.prog[0].y = 1;

422

423 dfa->prog = std::move(c.prog);

424 dfa->start_unanchored = 0;

425 dfa->start_anchored = f.start;

426

427 // The bytes an anchored match can begin with (its start-state closure's Byte classes) — the

428 // fast prefix scan uses this to skip over input that can't begin a match.

429 {

430 std::vector<int> sc;

431 std::vector<char> seen(dfa->prog.size(), 0);

432 dfa->add_closure(dfa->start_anchored, sc, seen);

433 for (int pc : sc) {

434 const Inst& in = dfa->prog[pc];

435 if (in.op == Inst::Byte) for (int k = 0; k < 4; ++k) dfa->first[k] |= in.cls[k];

436 if (in.op == Inst::Match) dfa->matches_empty = true; // accepts the empty string

437 }

438 int cnt = 0;

439 for (int w = 0; w < 4; ++w) cnt += std::popcount(dfa->first[w]);

440 dfa->first_count = cnt;

441 if (cnt == 1) // locate the single set bit; the byte-indexed LUT is built lazily on use

442 for (int w = 0; w < 4; ++w)

443 if (dfa->first[w]) {

444 dfa->first_byte =

445 static_cast<unsigned char>(w * 64 + std::countr_zero(dfa->first[w]));

446 break;

447 }

448 }

449

450 // The literal chain the pattern must start with: single-byte Byte instructions linked in a

451 // straight line from the anchored entry. Two or more bytes arm the front+back candidate

452 // probe (memchr the first byte, verify the last at its fixed distance) — far fewer false

453 // candidates than a first-byte scan on text where that byte is common.

454 for (int pc = dfa->start_anchored; dfa->lit.size() < 32;) {

455 const Inst& in = dfa->prog[static_cast<std::size_t>(pc)];

456 if (in.op != Inst::Byte) break;

457 const int bits = std::popcount(in.cls[0]) + std::popcount(in.cls[1]) +

458 std::popcount(in.cls[2]) + std::popcount(in.cls[3]);

459 if (bits != 1) break; // empty or multi-byte class: the chain ends here

460 for (int w = 0; w < 4; ++w)

461 if (in.cls[w]) {

462 dfa->lit += static_cast<char>(w * 64 + std::countr_zero(in.cls[w]));

463 break;

464 }

465 pc = in.x;

466 }

467 if (dfa->lit.size() < 2) dfa->lit.clear();

468

469 // `$` without `^`: every match must END at end-of-input, so matching runs BACKWARD over a

470 // reversed program — one anchored pass from the end answers existence and yields the

471 // leftmost begin, instead of forward-scanning every candidate start. Reversal only flips

472 // concatenation order (`|`/`*`/`+`/`?` are direction-symmetric, atoms are single

473 // instructions), and the source just parsed clean, so this second pass cannot fail.

474 if (dfa->anchored_end && !dfa->anchored_start) {

475 Compiler rc;

476 rc.reversed = true;

477 rc.src = pattern;

478 Frag rf = rc.parse_alt();

479 Inst rm; rm.op = Inst::Match;

480 const int rmatch = rc.emit(rm);

481 rc.patch(rf.holes, rmatch);

482 auto rev = std::make_unique<Dfa>();

483 rev->prog = std::move(rc.prog);

484 rev->start_anchored = rf.start;

485 dfa->rev = std::move(rev);

486 }

487

488 out.impl = std::move(dfa);

489 out.ok = true;

490 return out;

491}

492

493namespace {

494// The per-byte transition, structured so the scan loops keep the transition table's data

495// pointer `tf` IN A REGISTER: the cache-hit path is one load off `tf`, and only the rare

496// miss calls into `Dfa::step` (which may grow the table) and refreshes `tf`. Reading the

497// table through the member every byte would force a reload per byte — `step`'s store makes

498// the compiler assume the vector moved.

499inline int step_fast(Dfa& d, const int*& tf, int state, unsigned char b) {

500 const int cached = *reinterpret_cast<const int*>(reinterpret_cast<const char*>(tf) +

501 static_cast<std::size_t>(state) +

502 (static_cast<std::size_t>(b) << 2));

503 if (cached >= 0) return cached;

504 const int next = d.step(state, b);

505 tf = d.tflat.data();

506 return next;

507}

508

509// The accept flag of packed state `s` — an independent load of its row's flag slot. It

510// consumes the just-loaded state but never feeds the next transition's address, so it adds

511// nothing to the loop-carried chain.

512inline bool accepting(const int* tf, int state) {

513 return tf[static_cast<std::size_t>(state) / sizeof(int) + Dfa::kFlagSlot] != 0;

514}

515

516// Same-byte run skipping. When a step observes `S --c--> S` (the state just mapped a byte

517// back onto itself — the transition is cached, it was just taken) and S is non-accepting

518// (the loops return on accept before reaching the skip), then every CONSECUTIVE following

519// `c` provably leaves the machine in S with no accept missed — so the whole run can be

520// jumped in one SWAR scan (8 bytes per compare) instead of stepped byte-by-byte. Long

521// same-byte runs are a real input shape: padding, whitespace, repeated data.

522std::size_t skip_run_forward(const char* base, std::size_t p, std::size_t n, char c) {

523 std::uint64_t pat;

524 std::memset(&pat, static_cast<unsigned char>(c), sizeof pat);

525 while (p + 8 <= n) {

526 std::uint64_t w;

527 std::memcpy(&w, base + p, 8);

528 if (w != pat) break;

529 p += 8;

530 }

531 while (p < n && base[p] == c) ++p;

532 return p;

533}

534

535// The backward twin: returns the smallest q <= p with bytes [q, p) all equal to `c`.

536std::size_t skip_run_backward(const char* base, std::size_t p, char c) {

537 std::uint64_t pat;

538 std::memset(&pat, static_cast<unsigned char>(c), sizeof pat);

539 while (p >= 8) {

540 std::uint64_t w;

541 std::memcpy(&w, base + p - 8, 8);

542 if (w != pat) break;

543 p -= 8;

544 }

545 while (p > 0 && base[p - 1] == c) --p;

546 return p;

547}

548

549// The literal-chain compare, inlined: `k` is at most 32, so a plain byte loop beats a

550// libc memcmp call (which cannot inline a runtime-length compare) at every probe site.

551bool lit_eq(const char* p, const char* lp, std::size_t k) {

552 for (std::size_t j = 0; j < k; ++j)

553 if (p[j] != lp[j]) return false;

554 return true;

555}

556

557// Advance `i` to the next position that could begin a match, using the strongest precomputed

558// pruner the pattern allows: a required literal chain, a single required first byte (memchr),

559// or the first-set LUT (expanded from the bitset on first use, so patterns that never take

560// this branch never pay for it). Returns false when no candidate exists at or after `i`.

561// Callers guarantee the pattern cannot match empty (an empty match needs no first byte) and

562// that `first_count > 0`.

563bool skip_to_candidate(Dfa& d, std::string_view text, std::size_t& i) {

564 const char* base = text.data();

565 const std::size_t n = text.size();

566 if (!d.lit.empty()) {

567 // The pattern must start with the literal `lit`, so candidates are exactly its

568 // occurrences. Rare front byte: memchr sweeps at memory speed with few false hits.

569 // Front-byte storm (8 false hits inside one 1 KiB window): switch to a 32-wide

570 // branchless front+back block compare — the OR-reduction vectorizes, and the back

571 // byte at its fixed distance filters almost everything before the byte-wise verify.

572 // (The simultaneous two-byte probe is the idea behind RE2's prefix accelerator.)

573 const std::size_t k = d.lit.size();

574 const char front = d.lit[0];

575 const char back = d.lit[k - 1];

576 const char* lp = d.lit.data();

577 int false_hits = 0;

578 std::size_t window = i;

579 while (i + k <= n) {

580 const void* hit = std::memchr(base + i, front, n - k + 1 - i);

581 if (!hit) return false;

582 i = static_cast<std::size_t>(static_cast<const char*>(hit) - base);

583 if (lit_eq(base + i, lp, k)) return true;

584 ++i;

585 if (++false_hits < 8) continue;

586 if (i - window >= 1024) { false_hits = 0; window = i; continue; } // sparse: stay

587 break; // dense: block-scan

588 }

589 while (i + k + 31 <= n) { // 32 candidate positions per iteration, branch-free

590 bool any = false;

591 for (unsigned j = 0; j < 32; ++j)

592 any |= (base[i + j] == front) & (base[i + j + k - 1] == back);

593 if (!any) { i += 32; continue; }

594 const std::size_t block_end = i + 32;

595 for (; i < block_end; ++i)

596 if (base[i] == front && base[i + k - 1] == back && lit_eq(base + i, lp, k))

597 return true;

598 }

599 for (; i + k <= n; ++i) // tail

600 if (base[i] == front && base[i + k - 1] == back && lit_eq(base + i, lp, k))

601 return true;

602 return false;

603 }

604 if (d.first_count == 1) {

605 const void* hit = std::memchr(base + i, d.first_byte, n - i);

606 if (!hit) return false;

607 i = static_cast<std::size_t>(static_cast<const char*>(hit) - base);

608 return true;

609 }

610 if (!d.in_first_ready) {

611 for (int b = 0; b < 256; ++b)

612 d.in_first[static_cast<std::size_t>(b)] =

613 has_bit(d.first, static_cast<unsigned char>(b)) ? 1 : 0;

614 d.in_first_ready = true;

615 }

616 while (i < n && !d.in_first[static_cast<unsigned char>(base[i])]) ++i;

617 return i < n;

618}

619

620// Run the anchored DFA from byte offset `from`; true if it reaches an accepting state (that

621// also satisfies the end-anchor, if any). Touches only `text`'s bytes. `start` is PACKED.

622bool run_anchored(Dfa& d, std::string_view text, std::size_t from, bool need_end, int start) {

623 int state = start;

624 const int* tf = d.tflat.data();

625 for (std::size_t p = from;; ++p) {

626 if (accepting(tf, state) && (!need_end || p == text.size())) return true;

627 if (p == text.size()) return false;

628 state = step_fast(d, tf, state, static_cast<unsigned char>(text[p]));

629 if (state == 0) return false; // dead — cannot extend

630 }

631}

632

633// One forward pass from the unanchored start: the built-in `.*?` prefix keeps every possible

634// start position alive inside the DFA state itself, so an absent pattern costs exactly one

635// visit per byte — no per-candidate restarts, O(n) always. While the scan sits IN the start

636// state (no partial match alive, canonical interning makes the id compare exact), the

637// candidate skip may jump it forward; any non-starting byte re-arms it. The inner loop is one

638// packed-table load and one flag test per byte.

639bool run_unanchored(Dfa& d, std::string_view text) {

640 const int ustart = d.cached_start(d.start_unanchored, d.ustart_id);

641 int state = ustart;

642 const int* tf = d.tflat.data();

643 const bool can_skip = d.first_count > 0;

644 const char* base = text.data();

645 const std::size_t n = text.size();

646 for (std::size_t p = 0; p < n;) {

647 if (state == ustart) {

648 // Every byte the start state maps back onto itself is free to skip — including

649 // first-set bytes that only feed a self-loop (learned below). The memchr/literal

650 // pruners then jump over the rest.

651 while (p < n && d.ustart_self[static_cast<unsigned char>(base[p])]) ++p;

652 if (p == n) return false;

653 if (can_skip && !skip_to_candidate(d, text, p)) return false;

654 }

655 do {

656 const int prev = state;

657 const unsigned char b = static_cast<unsigned char>(base[p]);

658 state = step_fast(d, tf, state, b);

659 ++p;

660 if (accepting(tf, state)) return true;

661 if (state == prev) {

662 if (state == ustart) d.ustart_self[b] = 1; // learn the start self-loop

663 else p = skip_run_forward(base, p, n, static_cast<char>(b)); // S--b-->S run

664 }

665 } while (p < n && state != ustart);

666 }

667 return false;

668}

669

670// `$` without `^`: a match must end at end-of-input, so one anchored pass of the REVERSED

671// program, walking backward from the end, answers existence — and dies after a handful of

672// bytes when the tail can't match (`1274$` over a log that doesn't end in "1274").

673bool run_reverse(Dfa& rd, std::string_view text) {

674 int state = rd.cached_start(rd.start_anchored, rd.astart_id);

675 const int* tf = rd.tflat.data();

676 const char* base = text.data();

677 std::size_t p = text.size();

678 while (p > 0) {

679 const int prev = state;

680 const unsigned char b = static_cast<unsigned char>(base[--p]);

681 state = step_fast(rd, tf, state, b);

682 if (accepting(tf, state)) return true;

683 if (state == 0) return false; // dead — no longer suffix can match either

684 if (state == prev) p = skip_run_backward(base, p, static_cast<char>(b)); // S--b-->S run

685 }

686 return false;

687}

688

689bool run(const Pattern& re, std::string_view text, bool whole) {

690 if (!re.ok || !re.impl) return false;

691 Dfa& d = *re.impl;

692 const bool need_end = whole || d.anchored_end;

693 if (whole || d.anchored_start) // pinned to the start

694 return run_anchored(d, text, 0, need_end, d.cached_start(d.start_anchored, d.astart_id));

695 // A pattern that can match the empty string ALWAYS matches an unanchored search: at position 0

696 // when there is no end anchor, and at end-of-input when there is one (`a*$` over "bbb" — an

697 // empty match at n satisfies `$`). This must short-circuit BEFORE the accelerated scans below,

698 // which only propose positions holding a possible first byte (an empty match needs none).

699 if (d.matches_empty) return true;

700 if (d.rev) return run_reverse(*d.rev, text); // `$` only: one backward anchored pass

701 return run_unanchored(d, text);

702}

703} // namespace

704

705bool search(const Pattern& re, std::string_view text) { return run(re, text, false); }

706bool full_match(const Pattern& re, std::string_view text) { return run(re, text, true); }

707

708Match find(const Pattern& re, std::string_view text) {

709 Match r;

710 if (!re.ok || !re.impl) return r;

711 Dfa& d = *re.impl;

712 const std::size_t n = text.size();

713

714 // `$` without `^`: the match end is pinned at n, so the leftmost-longest match is simply

715 // the SMALLEST position whose suffix matches — one backward pass of the reversed program,

716 // tracking the leftmost accept until the reverse DFA dies. A nullable pattern (`a*$`)

717 // seeds the empty match at n, then extends leftward.

718 if (d.rev) {

719 Dfa& rd = *d.rev;

720 int state = rd.cached_start(rd.start_anchored, rd.astart_id);

721 const int* tf = rd.tflat.data();

722 const char* base = text.data();

723 long best = d.matches_empty ? static_cast<long>(n) : -1;

724 std::size_t p = n;

725 while (p > 0) {

726 const int prev = state;

727 const unsigned char b = static_cast<unsigned char>(base[--p]);

728 state = step_fast(rd, tf, state, b);

729 if (accepting(tf, state)) best = static_cast<long>(p);

730 if (state == 0) break; // dead — no earlier begin can reach the end

731 if (state == prev) {

732 // A self-looping state keeps its accept flag across the whole run: skipping

733 // it wholesale keeps `best` exact (every skipped begin was the same verdict,

734 // and leftmost wins — the run's far end).

735 p = skip_run_backward(base, p, static_cast<char>(b));

736 if (accepting(tf, state)) best = static_cast<long>(p);

737 }

738 }

739 if (best < 0) return r;

740 r.matched = true;

741 r.begin = static_cast<std::size_t>(best);

742 r.end = n;

743 r.text.assign(text.data() + r.begin, n - r.begin); // OWN a copy of the matched bytes

744 return r;

745 }

746

747 const std::size_t last_start = d.anchored_start ? 0 : n;

748 const bool can_skip = !d.anchored_start && !d.matches_empty && d.first_count > 0;

749 const int astart = d.cached_start(d.start_anchored, d.astart_id);

750 // Candidate-dense absent input would try every position; after a budget of failed

751 // candidates, ONE unanchored pass settles existence (absent input then costs O(n) total).

752 // A present match just keeps the candidate loop going — leftmost-longest needs it anyway.

753 long budget = 4096;

754 const int* tf = d.tflat.data();

755 for (std::size_t i = 0; i <= last_start; ++i) {

756 if (can_skip && !skip_to_candidate(d, text, i)) return r;

757 if (--budget == 0) {

758 if (!run_unanchored(d, text)) return r;

759 tf = d.tflat.data(); // the existence pass may have grown the table

760 }

761 int state = astart;

762 long best_end = -1;

763 for (std::size_t p = i;; ++p) {

764 if (accepting(tf, state) && (!d.anchored_end || p == n)) best_end = static_cast<long>(p);

765 if (p == n) break;

766 state = step_fast(d, tf, state, static_cast<unsigned char>(text[p]));

767 if (state == 0) break; // dead — no match can extend

768 }

769 if (best_end >= 0) {

770 r.matched = true;

771 r.begin = i;

772 r.end = static_cast<std::size_t>(best_end);

773 r.text.assign(text.data() + i, r.end - i); // OWN a copy of the matched bytes

774 return r;

775 }

776 }

777 return r;

778}

779

780} // namespace cheatah::regex