rejit

A regular-expression engine built from scratch that matches in guaranteed linear time — so it cannot be ReDoS'd.

Most regex engines, Python's re included, match by backtracking. On a pattern like (a+)+$ that can be catastrophic: the engine tries exponentially many ways to split the input, and a short string can hang the process. rejit takes the other classic approach — it compiles the pattern to a small instruction program and simulates the NFA breadth-first (a Pike VM), visiting each state at most once per input position. Matching is O(text × pattern), always.

The difference is not subtle. Both engines, same pattern (a+)+$, against a run of as followed by a character that makes the match fail:

input length	Python re	rejit
20	49 ms	0.23 ms
24	838 ms	0.21 ms
28	13 807 ms	0.23 ms
40 000	(≈ 2⁴⁰⁰⁰⁰ steps — never finishes)	259 ms

Read the columns, not the cells. Every four characters of input multiply re's work by ~16; rejit doesn't move at all. At length 28 that is already a ~60 000× gap, and it keeps doubling with every further character while rejit stays flat.

Absolute times depend on the machine — these are from an i7-8550U, and a faster CPU shifts both columns without changing the shape. The exponent is the claim, not the milliseconds, and python -m rejit redos 40000 reproduces it on yours.

$ python -m rejit redos 40000
pattern '(a+)+$' against 40000 'a's followed by a non-match:
  n=  10000    ~69.15 ms
  n=  20000   ~149.96 ms
  n=  40000   ~268.32 ms
Time grows linearly. A backtracking engine (including Python's re)
would take exponential time on this input.

No dependencies — only the Python standard library.

How I know it's correct

A regex engine is only interesting if it's right, and "right" here has an oracle: Python's own re module. The test suite generates random patterns from exactly the syntax rejit supports, pairs each with random strings, and checks that rejit and re agree on four things:

1. Membership — does the whole string match (fullmatch)?
2. Search — does the pattern occur anywhere?
3. Span and captures — where does it match, and what do the groups capture?
4. finditer — the full sequence of non-overlapping matches, including the fiddly empty-match rules Python changed in 3.7.

On every CI run the committed suite generates 10 000 random pattern/text pairs from a fixed seed and cross-checks each one against re on the three questions above — 30 013 assertions in total, with zero disagreements.

That distinction matters, and this paragraph used to blur it: it said "30 013 generated cases", which reads as thirty thousand different inputs. It is ten thousand inputs, each interrogated three ways. Both numbers are real and the suite prints them:

$ python -m pytest -q
42 passed, 30013 subtests passed in ...

Locally I've pushed the same generator to 90 000 pairs across several seeds, also with zero disagreements — but that is not what CI runs, so it is not the number this page leads with. Because the generator only ever emits supported syntax, any divergence is a real bug, which is what makes re a trustworthy oracle.

Finding this was itself a nice demonstration: the fuzzer turned up patterns like ((?:()*|(.{1,3}^|)?.{0,2}(){0,2})+)*0{1,3} on which re.fullmatch hangs (catastrophic backtracking) while rejit answers in under a millisecond. Those patterns can't be oracle-checked for value — re never returns — so they're covered instead by the deterministic linear-time tests, and the fuzzer avoids generating nested quantifiers over nullable subexpressions so the oracle stays usable.

Character-class escapes (\d, \w, \s, …) use ASCII semantics, so rejit corresponds precisely to re compiled with the re.ASCII flag — that is the exact oracle the tests compare against.

One honest caveat surfaced by cross-version CI: whether \B matches the empty string changed in CPython itself (older re said no; 3.14 says yes, since position 0 of "" is not a word boundary). rejit follows the modern, logically consistent behaviour on every Python version, so the random fuzzer does not use \B as an oracle case — it is covered by deterministic tests instead.

Use it

Requires Python 3.10+ (any platform — this is pure Python, no machine-specific code) and pulls in no dependencies. There is nothing to install; the whole engine is four small modules:

$ git clone https://github.com/Wasserpuncher/rejit && cd rejit

From Python, the API mirrors the part of re it reproduces:

import rejit

rejit.fullmatch(r"\d{4}-\d\d-\d\d", "2026-07-09")      # -> <rejit.Match ...>
rejit.search(r"[a-z]+", "  hello  ").span()            # -> (2, 7)
rejit.fullmatch(r"(\d+)\.(\d+)", "3.14").groups()      # -> ('3', '14')
[m.group() for m in rejit.compile(r"\w+").finditer("a bc")]   # -> ['a', 'bc']

From the command line:

$ python -m rejit fullmatch '(\d+)\.(\d+)' 3.14
fullmatch: span=(0, 4) match='3.14'
  group 1: span=(0, 1) value='3'
  group 2: span=(2, 4) value='14'

$ python -m rejit findall '[a-z]+' 'ab cd ef'
(0, 2)	'ab'
(3, 5)	'cd'
(6, 8)	'ef'

$ python -m rejit dump 'a|b'        # inspect the compiled program
$ python -m rejit redos 40000       # watch matching stay linear

How it works

Four small stages, each in its own module:

1. parser.py — a recursive-descent parser turns the pattern into an AST. Operator precedence (alternation < concatenation < quantifier < atom) is the shape of the grammar.
2. program.py — the AST is lowered into a flat instruction program: CHAR/CLASS consume a character, SPLIT forks into two ordered threads, JMP branches, SAVE records a capture position, ASSERT handles anchors, MATCH accepts. SPLIT's ordering is how greedy vs. lazy is expressed.
3. vm.py — the Pike VM. It keeps a priority-ordered set of live threads and advances them one character at a time. A per-position seen set guarantees each instruction is visited at most once, which is the whole ballgame: it is why the engine is linear and why nested quantifiers can't blow up.
4. engine.py — the public Regex/Match objects and the module-level match/search/fullmatch/finditer/findall helpers.

The linear-time / priority-thread design follows Russ Cox's articles on regular expression matching (https://swtch.com/~rsc/regexp/).

Supported syntax

Literals and .; character classes [...], [^...] with ranges and class escapes; the escapes \d \D \w \W \s \S (ASCII) and \b \B; anchors ^ $ \A \Z; grouping (...) and (?:...); alternation |; and the quantifiers * + ?, {m}, {m,}, {m,n}, each optionally lazy with a trailing ?.

Limitations

By design — a linear-time engine matches the regular languages, and some re features are deliberately outside that:

• No backreferences (\1) and no lookaround ((?=...), (?<=...)). These make a language non-regular; a Pike VM fundamentally cannot express them, and that is the price of the linear-time guarantee.
• No named groups, inline flags (?i), or the re.MULTILINE/DOTALL variations of ^ $ . — only the default (ASCII, single-line) semantics.
• ASCII class semantics, matching re.ASCII, not Unicode \d/\w.
• Bounded repetitions are expanded inline, so {m,n} counts are capped (1000) to keep the program finite.
• Not tuned for raw throughput on trivial patterns; the point is the worst-case guarantee, not beating a C engine on abc.

License

MIT — see LICENSE.