1. The Three-Stage Thompson Regex Pipeline
To compile a raw regex string $R$ of length $M$ into a linear-time automaton with zero pointer chasing, we execute three linear passes:
- Explicit Concatenation & Shunting-Yard (
re2post): Standard regex syntax omits the concatenation operator (writingabinstead ofa·b). An explicit concatenation operatorCONCATmust be inserted between token $T_1$ and token $T_2$ whenever $T_1$ can end a subexpression (a literal,.,),*,+, or?) AND $T_2$ can begin a subexpression (a literal,., or(). We then run Shunting-Yard with operator precedence $\{*, +, ?\} > \text{CONCAT} > |$. - Fragment Stack Compilation (
post2nfa): Each item on the compiler stack is aFrag { int start; std::vectorwhere each integer inout_patches; } out_patchesencodes(state_idx << 1) | which_arrowidentifying an unpatched outgoing slot (outorout1) in our contiguousstd::vectorarena. - Generation-Stamped Lockstep Simulation (
match): At each text byte, we step all active states inclistintonlistusinglast_step[u] == step_idto deduplicate $\varepsilon$-closures in $O(1)$ time.
| Compiler / VM Stage | Time Complexity | Space Complexity | Key Invariant |
|---|---|---|---|
to_postfix(pattern) |
$O(M)$ | $O(M)$ | Precedence: Unary (*,+,?) $3$ > Concat $2$ > Alt (|) $1$ |
compile_postfix(post) |
$O(M)$ | $\le 2M$ NFA states | Every Frag patches dangling arrows into contiguous arena |
full_match(text) |
$O(N \cdot M)$ worst-case | $O(M)$ (clist, nlist) |
Immune to ReDoS on (a+)+b, (a|a)*b, etc. |
Fragment Dangling-Arrow Patching Invariant
Every compiled subexpression fragment $F$ has a single entry state F.start and a list of dangling outgoing arrow slots F.dangling that are reached when $F$ finishes matching. Calling patch(F.dangling, target_state) wires every exit path of $F$ directly to target_state. Because each postfix operator creates at most $1$ new SPLIT or CHAR state and merges at most two dangling lists, the total number of states and patched arrows is bounded by $2M$.
Encoding Dangling Pointers as Packed Arena Indices
In C, Russ Cox's reference implementation represents dangling arrows as Ptrlist* unions overlaid inside State* pointers—a trick that triggers strict-aliasing UB in modern C++ and breaks if states live in a resizable std::vector<State>. Packing a dangling slot as (state_id << 1) | is_out1 (int32_t) is 100% standards-compliant, survives std::vector reallocation, and keeps the entire NFA inside a single cache-hot array.
2. Visual Trace: Thompson NFA Fragments (CONCAT, |, *, +, ?)
flowchart LR
A["Infix Regex: a(b|c)*d"] --> B["Insert Explicit CONCAT: a·(b|c)*·d"]
B --> C["Shunting-Yard Postfix: a b c | * · d ·"]
C --> D["Fragment Stack Compiler -> NFA Arena"]
D --> E["Lockstep Subset Simulator O(N * M)"]
Burrows-Wheeler Transform (BWT) Rotation Matrix, FM-Index LF-Mapping & Thompson NFA
O(|P|) FM-Index Backward Search · O(NM) Thompson NFA
Trace the sorted cyclic rotation matrix of "banana$", LF-mapping rank queries shrinking [sp, ep] backward for P = "ana", and Ken Thompson’s lockstep NFA state-set simulation O(NM) vs O(2^N) backtracking ReDoS.
Step 1 / 9
Timeline
Invariant & State
BWT(banana$) = L = "annb$aa" (runs of "nn" and "aa" compress via RLE/MTF!). Backward search starts at P[2]='a': C['a']=1, range [sp, ep] = [1, 3].
📊 Live Magnitude & Pointer Stage — Burrows-Wheeler Transform (BWT) Rotation Matrix, FM-Index LF-Mapping & Thompson NFA
Active
Pivot
Match/Sorted
[0]0: $banan [a]
[1]1: a$bana [n]
[2]2: ana$ba [n]
[3]3: anana$ [b]
[4]4: banana [$]
[5]5: na$ban [a]
[6]6: nana$b [a]
BWT Last Column L
"annb$aa"
Matched Suffix of P
"a" (P[2])
SA Interval [sp, ep]
[0, 6] (7 rows)
Query Time
O(|P|) Backward Steps
[Step 1] Step 1 (char 'a'): C['a'] = 1, Occ('a', 7) = 3 -> all suffixes starting with "a" sit in SA range [1..3].
3. Complete Build Implementation: End-to-End Thompson Regex Engine
#include <cstdint>
#include <string>
#include <string_view>
#include <vector>
class ReDoSProofRegex {
public:
static constexpr char OP_CONCAT = '';
explicit ReDoSProofRegex(std::string_view pattern) {
std::string post = to_postfix(pattern);
compile_postfix(post);
}
bool full_match(std::string_view text) const {
if (start_ < 0) return false;
const int m = static_cast<int>(states_.size());
std::vector<int> clist, nlist, last_step(m, 0);
int step_id = 1;
add_state(start_, clist, last_step, step_id);
for (char c : text) {
++step_id;
nlist.clear();
for (int u : clist) {
if (states_[u].op == CHAR && (states_[u].ch == c || states_[u].ch == '.')) {
add_state(states_[u].out, nlist, last_step, step_id);
}
}
clist.swap(nlist);
if (clist.empty()) return false;
}
for (int u : clist) {
if (states_[u].op == MATCH) return true;
}
return false;
}
private:
enum Op { CHAR, SPLIT, MATCH };
struct State {
Op op;
char ch = 0;
int out = -1;
int out1 = -1;
};
struct Frag {
int start;
std::vector<int> dangling; // Packed: (state_idx << 1) | is_out1
};
std::vector<State> states_;
int start_ = -1;
static int precedence(char op) {
if (op == '*' || op == '+' || op == '?') return 3;
if (op == OP_CONCAT) return 2;
if (op == '|') return 1;
return 0;
}
static std::string to_postfix(std::string_view re) {
// 1. Insert explicit concatenation OP_CONCAT ('')
std::string exp;
bool prev_can_end = false;
for (char c : re) {
bool cur_can_start = (c != '|' && c != ')' && c != '*' && c != '+' && c != '?');
if (prev_can_end && cur_can_start) exp.push_back(OP_CONCAT);
exp.push_back(c);
prev_can_end = (c != '|' && c != '(');
}
// 2. Dijkstra's Shunting-Yard to Postfix
std::string post, ops;
for (char c : exp) {
if (c == '(') {
ops.push_back(c);
} else if (c == ')') {
while (!ops.empty() && ops.back() != '(') {
post.push_back(ops.back());
ops.pop_back();
}
if (!ops.empty()) ops.pop_back();
} else if (c == '|' || c == OP_CONCAT || c == '*' || c == '+' || c == '?') {
while (!ops.empty() && ops.back() != '(' &&
precedence(ops.back()) >= precedence(c)) {
post.push_back(ops.back());
ops.pop_back();
}
ops.push_back(c);
} else {
post.push_back(c);
}
}
while (!ops.empty()) {
post.push_back(ops.back());
ops.pop_back();
}
return post;
}
int add_nfa_state(Op op, char ch, int out, int out1) {
states_.push_back({op, ch, out, out1});
return static_cast<int>(states_.size()) - 1;
}
void patch(const std::vector<int>& list, int target) {
for (int p : list) {
int idx = p >> 1;
if (p & 1) states_[idx].out1 = target;
else states_[idx].out = target;
}
}
static std::vector<int> append(std::vector<int> a, const std::vector<int>& b) {
a.insert(a.end(), b.begin(), b.end());
return a;
}
void compile_postfix(std::string_view post) {
std::vector<Frag> st;
for (char c : post) {
if (c == OP_CONCAT) {
Frag e2 = std::move(st.back()); st.pop_back();
Frag e1 = std::move(st.back()); st.pop_back();
patch(e1.dangling, e2.start);
st.push_back({e1.start, std::move(e2.dangling)});
} else if (c == '|') {
Frag e2 = std::move(st.back()); st.pop_back();
Frag e1 = std::move(st.back()); st.pop_back();
int s = add_nfa_state(SPLIT, 0, e1.start, e2.start);
st.push_back({s, append(std::move(e1.dangling), e2.dangling)});
} else if (c == '?') {
Frag e = std::move(st.back()); st.pop_back();
int s = add_nfa_state(SPLIT, 0, e.start, -1);
e.dangling.push_back((s << 1) | 1);
st.push_back({s, std::move(e.dangling)});
} else if (c == '*') {
Frag e = std::move(st.back()); st.pop_back();
int s = add_nfa_state(SPLIT, 0, e.start, -1);
patch(e.dangling, s);
st.push_back({s, {(s << 1) | 1}});
} else if (c == '+') {
Frag e = std::move(st.back()); st.pop_back();
int s = add_nfa_state(SPLIT, 0, e.start, -1);
patch(e.dangling, s);
st.push_back({e.start, {(s << 1) | 1}});
} else {
int s = add_nfa_state(CHAR, c, -1, -1);
st.push_back({s, {(s << 1) | 0}});
}
}
if (st.empty()) {
start_ = add_nfa_state(MATCH, 0, -1, -1);
return;
}
Frag root = std::move(st.back());
int match_state = add_nfa_state(MATCH, 0, -1, -1);
patch(root.dangling, match_state);
start_ = root.start;
}
void add_state(int u, std::vector<int>& list,
std::vector<int>& last_step, int step_id) const {
if (u < 0 || last_step[u] == step_id) return;
last_step[u] = step_id;
if (states_[u].op == SPLIT) {
add_state(states_[u].out, list, last_step, step_id);
add_state(states_[u].out1, list, last_step, step_id);
return;
}
list.push_back(u);
}
};Empty-Loop Cycles (
(a*)*) and Why last_step[u] == step_id Saves add_stateConsider compiling (a*)* or (|a)*. The two nested SPLIT nodes form a directed cycle of $\varepsilon$-transitions! If add_state set last_step[u] = step_id after recursing on SPLIT children (or only set it for CHAR states), an $\varepsilon$-cycle would cause infinite recursion and a stack overflow on the very first character! Setting last_step[u] = step_id at the very top of add_state before recursing on SPLIT breaks every $\varepsilon$-cycle in $O(1)$ time.