Six months ago I published "Go's Regexp is Slow. So I Built My Own". The project grew, got contributors, beat Rust on several patterns. Tested on Go 1.27, go.mod requires 1.27+.
Then I commissioned an independent code review — a full differential fuzz against stdlib plus manual audit of the engine internals.
6% of random pattern/input pairs gave wrong answers.
Not edge cases. Not theoretical. (?i)привет didn't match "привет" — its own literal. \pL+ on a 50KB file returned no matches while MatchString returned true. A 15-character pattern OOM'd the process at compile time.
This is the story of what broke, why 65,000 lines of tests missed it, and what it took to fix.
The bug that would have broken every HTTP router
Issue #166 from @vmihailenco — sat open for six weeks because I missed the notification buried in email noise, and only caught it reviewing the repo:
coregex.MustCompile(`^x(a|bc)`).MatchString("xbc") // false
That's a false on a pattern that obviously matches. When I dug in, it wasn't one bug — it was an entire strategy producing wrong answers:
^x(a|bc) "xbc" → false (prefix ignored)
^HTTP/(1\.0|1\.1|2) "HTTP/2" → false (every HTTP version check)
^/api/(users|posts) "/api/users" → false (every API router)
^(GET|POST) / "GET x" → true (false positive!)
The BranchDispatch optimization dispatched by first byte, then verified the match with a simple matcher that couldn't handle real AST shapes. It was a mini-engine — one that said "yes" without being a real engine.
Lesson: An optimization that answers "yes" independently must be a full engine. Otherwise it's a bug generator. Safe optimizations only say "no" quickly (prefilters, first-byte reject) and delegate "yes" to the real engine. Rust regex doesn't need branch dispatch — the lazy DFA transition table already is a dispatch table at every state.
Solution: deleted the entire strategy. -1077 lines. Anchored alternations now go through BoundedBacktracker with O(1) first-byte reject. 13 ns → 66 ns on short strings — still 1.5× faster than stdlib. The speed gap is a known issue; once the capture path is fixed (#177), anchored one-pass patterns can route through it.
Case-insensitive Cyrillic didn't match its own literal
The NFA compiler had this:
if foldCase && isASCIILetter(r) {
// create alternation: upper + lower
}
Non-ASCII runes with case-insensitive flag were compiled as exact uppercase match. syntax.Parse uppercases Cyrillic (к → К), so the NFA only matched К, never к.
But here's the weird part: (?i)кот (3 Cyrillic runes) worked fine. (?i)привет (6 runes) didn't. Same code path — how?
Two different engines, one hiding the bug. For 2-4 rune patterns, the cross-product of case variants fit within the Teddy prefilter's literal limit. Teddy matched all variants by exact bytes, bypassing the broken NFA entirely. For 1 rune and 5+ runes, the cross-product exceeded the limit → fell back to NFA → bug.
The test suite had (?i)кот — green. The real-world (?i)привет — broken. A test that passes on a specific length doesn't test the code path you think it tests.
Fix: unicode.SimpleFold orbit for every rune, compiled as a split tree:
func foldOrbit(r rune) []rune {
orbit := []rune{r}
for f := unicode.SimpleFold(r); f != r; f = unicode.SimpleFold(f) {
orbit = append(orbit, f)
}
return orbit
}
// Σ → [Σ, σ, ς] (Greek sigma, three forms)
// K → [K, k, K] (ASCII K, ASCII k, Kelvin sign)
Silent wrong results on large input
\pL+ (match Unicode letters) on a 50KB file: MatchString returned true, but FindAllStringIndex returned zero or one match instead of thousands.
Root cause: \pL compiles to 5842 NFA states (stdlib uses 3 instructions). On input over ~10KB, the BoundedBacktracker's visited table overflows and falls back to bidirectional DFA search. The forward DFA found the match end correctly, but the reverse DFA overflowed too — and its fallback ran the reverse NFA's PikeVM forward on forward data. Reverse NFA expects reversed UTF-8 byte sequences; running it forward produces no matches.
Fix: when the reverse DFA fails, fall back to the forward PikeVM's SearchBetween instead. Correct on all input sizes now.
The cost: \pL+ on large inputs uses PikeVM fallback at ~50 μs/byte (8.4s on 120KB vs stdlib's 9ms). Correct, but impractical. The real fix is DFA cache clear-and-continue (as Rust does) plus compact UTF-8 range-trie compilation for Unicode classes. Both are tracked.
Empty matches that produced invalid UTF-8
re := coregex.MustCompile(`a*`)
result := re.ReplaceAllString("日", "-")
// Expected: "-日-"
// Got: invalid UTF-8 — rune sliced at byte boundaries
After an empty match, the position advanced by one byte instead of one rune. "日" is 3 bytes (E6 97 A5), so instead of two empty matches (before and after the rune), we got four — one at each byte boundary, slicing the rune apart.
26 call sites across 9 functions. One helper fixed them all:
func advanceAfterEmpty(b []byte, pos int) int {
if pos < len(b) {
_, w := utf8.DecodeRune(b[pos:])
return pos + w
}
return pos + 1
}
The 15-character DoS
coregex.Compile(`.(?:ac*d|ac)xy*`)
// 15 characters → >3 GB heap, >15 seconds, OOM kill
// stdlib: ~7 μs
cloneRegexp in the literal extractor cloned both Sub and Sub0 arrays. In syntax.Regexp, Sub usually aliases Sub0[:1] — so every node with one child got cloned twice. Size grew as 2^depth.
Fix: delete the Sub0 loop. One loop removed, compile time back to microseconds.
For a library that claims "no ReDoS" — any service compiling user-supplied patterns was vulnerable to a 15-character denial of service.
What the fuzz found (and didn't)
The test suite had hasUTF8CodepointDifference — a whitelist function that skipped exactly the patterns where bugs lived. The fuzz harness compared each API against stdlib but filtered out multibyte input. We were testing the correct code paths and skipping the broken ones.
After fixes, differential fuzz against stdlib: 6.0% → 0.75% divergence on random pattern/input pairs. The remaining 0.75% decomposes into three classes, each with its own issue:
| Class | Example | Issue |
|---|---|---|
| Negated classes match bytes |
\S{2} on "К" → false positive |
#174 |
| Lazy quantifiers = greedy |
\d+? on "11" → [0 2]
|
#175 |
| Leftmost priority divergence |
FindAllIndex ≠ FindAllSubmatchIndex
|
#176 |
The benchmarks after fixes
All 16 bugs from the audit are fixed; three pre-existing classes are tracked in #178. No benchmark regressions — verified on AMD EPYC via regex-bench CI (Go stdlib, coregex, and Rust regex on identical 6 MB workloads):
| Pattern | vs stdlib | vs Rust |
|---|---|---|
.*keyword.* (inner literal) |
527× | 27× faster |
.*\.txt (suffix) |
143× | 7.3× faster |
| IPv4 octet alternation | 236× | 5.6× faster |
[\w]+ (char class) |
11× | 1.2× faster |
(?m)^/.*\.php (multiline) |
154× | ~same |
What I'd do differently
1. Fuzz first, optimize second. I had 65K lines of tests. A ~150-line differential harness found most of the bugs — random pattern × random input × compare with stdlib. Should have been day one.
2. Never whitelist what you can't explain. hasUTF8CodepointDifference was a flag that said "we know this is different." It should have been a bug count that said "we have N bugs to fix."
3. Optimizations that say "yes" are engines. Prefilters, rejectors, first-byte checks — they say "no" quickly. Safe. The moment your optimization says "yes, this matches" without delegating to the real engine, you've built a second engine with half the test coverage.
4. Real users find real bugs. vmihailenco's one-line repro exposed a class of bugs that 65K lines of tests missed. Every regex library should have a "give me your pattern, I'll diff it against stdlib" command.
What's next
Three correctness classes to close before v1.0 (#178). FindSubmatch is 3-10× slower than stdlib with 6-9 allocations per call — that's the primary API for log parsing and the most user-visible gap.
The strategy architecture is sound; the bugs were in the NFA compiler's Unicode handling and in shortcuts around the engines.
Contributions welcome. Especially on negated character classes — it's the biggest remaining divergence from stdlib, and the fix follows a pattern we've already applied for ..
coregex: github.com/coregx/coregex
go get github.com/coregx/coregex@v0.12.27
import regexp "github.com/coregx/coregex"
re := regexp.MustCompile(`(?i)привет`)
re.MatchString("Привет") // true (fixed in v0.12.26)
Top comments (1)
The audit findings are the most interesting part — compile-time DoS in a regex parser is a nasty class of bug because it hits before you even match input, and it's often overlooked in fuzzing since most tools focus on runtime matching. The 3-3000x speedup range also tells me the benchmarks likely hit pathological backtracking cases in stdlib where RE2's guaranteed linear-time matching shines, but I'd want to see p99 latency on real-world patterns (email validation, log parsing, UUID extraction) rather than synthetic worst-cases.
Unicode correctness is the silent killer here. Go's stdlib uses a modified RE2 with custom Unicode tables, and subtle differences in grapheme cluster handling or property escapes (
\p{Script=Han}etc.) cause silent data corruption in production. The fact that 3 bug classes are still "tracked" not "fixed" suggests fundamental architectural decisions around Unicode version pinning or normalization forms that can't be patched without breaking semver.For anyone evaluating this: run your existing test suite against coregex first. The drop-in claim only holds if you're not relying on stdlib-specific quirks like
\C(single byte) or the exact capture group numbering on nested alternations (site: labagent .tech)