A regular expression engine written from scratch in Java. No java.util.regex, no dependencies,
and no pattern that can make it hang.
Regex email = Regex.compile("[\\w.]+@[\\w]+\\.[a-z]{2,4}");
email.matches("lucca@example.com"); // true
email.find("write to lucca@example.com now"); // trueParser to AST, Thompson construction to an NFA, then parallel state-set simulation. About 700
lines, all of it in src/needle.
Backtracking engines explore one path at a time and retry on failure. For a pattern like
(a+)+b, the number of ways to split a run of a between the inner and outer + grows
exponentially, and a 30 character input can take longer than the age of the universe. That is
ReDoS, and it has caused real outages: Cloudflare's global outage in July 2019 and Stack
Overflow's in July 2016 were both a single regex.
This engine never backtracks. It advances a set of NFA states one character at a time, in lockstep. The set can never contain more states than the machine has, so the total work is bounded by O(pattern x input) for every pattern. Not most patterns. Every one.
The test suite runs (a+)+b against 50,000 characters:
50,000 chars in 6549 microseconds
20k: 641us, 80k: 2484us, 4x input cost 3.9x time
4x the input costs 3.9x the time. That is the guarantee, measured rather than asserted.
Most write-ups of this topic end with "and here is the same pattern hanging java.util.regex
forever." I wrote that test, ran it, and it failed: on JDK 24, java.util.regex finishes the
textbook ReDoS cases instantly. Modern JDKs recognise that (a+)+b requires a trailing b,
notice the input does not end in one, and refuse the work.
I probed eighteen classic catastrophic patterns and variants, including ones with no fixed literal suffix so that optimisation cannot fire:
^(a|a?)+$ len=31 -> finished 1ms
^(a*)*$ len=31 -> finished 0ms
^(\w+\s?)*$ len=29 -> finished 1ms
^([^,]*,)*$ len=29 -> finished 0ms
^(a+)+$ len=41 -> finished 0ms
None of them blew up. So the honest claim is not "the JDK hangs and this does not." It is this:
- The JDK is fast on these inputs because of heuristics that recognise particular shapes. Heuristics have edges, and a pattern that falls outside them is back to exponential.
- This engine is fast because of its structure. There is no input and no pattern for which it degrades, because backtracking is not something it can do.
Where they can be compared directly, the difference is still large. On (a+)+b against 2,000
characters, measured in the suite:
needle: 64us
java.util.regex: 19936us
312x, and both finished. The point is not the speed, it is that one of those numbers is guaranteed by construction and the other is guaranteed by a heuristic firing.
Backreferences (\1) and lookaround. Not an oversight and not a to-do. Matching a
language with backreferences is NP-hard, and both features require backtracking. Supporting them
would mean giving up the only property this project exists to have. If you need them, use
java.util.regex and audit your patterns.
| Syntax | Meaning |
|---|---|
abc |
literals |
. |
any character except newline |
a|b |
alternation |
(ab) |
grouping |
a* a+ a? |
repetition |
a{2} a{2,} a{2,4} |
counted repetition, up to 1024 |
[a-z0-9_] [^abc] |
character classes |
\d \D \w \W \s \S |
shorthand classes |
\n \t \r \. \\ |
escapes |
Counted repetition is desugared at parse time: a{2,4} becomes aa(a(a)?)?. That keeps the NFA
compiler down to five node types, and the 1024 cap means a{999999} is rejected instead of
exhausting memory building the machine.
Parse. Recursive descent, loosest binding first: alternation, then concatenation, then repetition, then atoms. Produces a sealed hierarchy of records, so the compiler checks the NFA builder handles every node type.
Compile. Each node becomes a fragment with one entry and a list of dangling exits, and fragments compose. Three state kinds only: consume a character, split into two epsilon branches, or accept.
Simulate. Track the live state set. For each input character, step every state that accepts
it. The set is de-duplicated by generation stamping rather than a HashSet: each state stores
the step number it was last added at, so membership is an int comparison and clearing the set is
just incrementing a counter.
That stamping also does something subtler. Following epsilon transitions through a pattern like
(a*)* would loop forever, and the stamp is what terminates it, since a state already added this
step is never revisited.
Requires JDK 21 or newer. The NFA compiler switches over a sealed hierarchy of records, and
pattern matching for switch was only finalised in 21. There is no Maven or Gradle to install.
javac -d out $(find src test -name '*.java')
java -cp out needle.TestsOr ./build.sh on macOS and Linux, .\build.ps1 on Windows.
All 33 tests passed.
The suite covers the grammar, the error cases, and the complexity guarantee. It asserts the things this engine promises and measures the things it does not control.
MIT. See LICENSE.