Security & networking · Python

Rex — Regex Engine

Four engines, one pattern — measure catastrophic backtracking instead of guessing.

GitHub

01 ReDoS Cost Comparison

Pattern (a+)+b against a string of a with no b. On failure, backtracking enumerates every way to split the input across the two + levels.

Input length (n)

n = 20

Backtracking

16,777,194

steps

Thompson NFA

592

steps

Backtracking

Thompson NFA

Ratio: 28,340× more work for the backtracking engine at n=20

Closed forms: backtracking = 2^(n+4) − (n+9), Thompson = 30n − 25

02 Pattern Safety Checker

A shape-based heuristic that flags nested quantifiers and ambiguous alternations inside repeats.

Pattern

03 Live Match

Try a pattern against sample input with JavaScript's RegExp — leftmost-first semantics, the same family as Python's re.

Pattern

Flags

Input

04 Engine Comparison

Measured with rex redos -m 20 --stdlib. Every extra input character multiplies backtracking work by 2.00×.

n	Backtracking	Thompson NFA	Ratio	Python re
12	65,522	352	186×	0.000s
14	262,128	412	636×	0.002s
16	1,048,558	472	2,222×	0.007s
18	4,194,284	532	7,884×	0.026s
20	16,777,194	592	28,340×	0.106s

Python's re is also a backtracking engine: 0.106s at n=20, 1.6s at n=24, 25s at n=28. rex refuses to run flagged patterns longer than 24 characters.

05 CLI Output Examples

rex match

$ rex match '(a+)+b' 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' engine result steps time backtracking GAVE UP 1,000,001 0.8020 thompson nfa False 875 0.0002 lazy dfa False 100 0.0002 python re skipped - -

rex check

$ rex check '(a+)+b' '(a|a)*b' '(a|b)*c' RISK (a+)+b nested quantifier RISK (a|a)*b ambiguous alternation ok (a|b)*c

06 What It Supports

Literals, ., character classes with ranges and negation, \d \w \s and their uppercase complements, * + ? and {n,m} in greedy and lazy forms, alternation, capturing and non-capturing groups, and ^ $ anchors.

Not supported: backreferences and lookaround — the features that force engines into backtracking. Skipping them is what buys the linear-time guarantee this project is about.

$ rex compile 'a(b|c)*d' 0 char 'a' 1 split 2, 9 2 save 2 3 split 4, 6 4 char 'b' 5 jump 7 6 char 'c' 7 save 3 8 jump 1 9 char 'd' 10 match

07 NFA / DFA State Graph

Thompson construction renders the current pattern as an automaton. Switch to DFA for subset-construction determinism — active states light up during stepping.

Pattern

animate

start accept active (stepping) ε = epsilon transition

States

Transitions

Automaton

NFA

Pattern length

08 Step-by-Step Match Visualizer

Walk the NFA one input character at a time — watch the active state set move and the input pointer advance.

Pattern

Input string

position 0 / 0

active states: — status: idle

Press Step to advance the simulation.

09 Pattern Library

24 battle-tested patterns — one click loads into the checker, live match, graph and visualizer.

10 Complexity Estimator & Export

Big-O for the current pattern across three engine families, derived from the shape analysis (nested quantifiers, ambiguous alternation).

Pattern

Run the estimator to see a breakdown.

Includes pattern, complexity, graph stats and match results.