Comb, a regex engine that never backtracks
Comb is a regular expression engine written from an empty file. It reads JavaScript’s own pattern syntax and gives the same matches and the same groups as the browser’s RegExp, but it runs every way a pattern could match at once, in one pass over the text. A pattern that keeps the browser busy for seconds, and twice as long for each letter more, takes Comb a fraction of a millisecond. Type a pattern below, and both engines answer.
·
Comb runs in the page as you type. Your browser’s RegExp runs in a worker, so a pattern that takes it a long time cannot stop the page, and is called off after a few seconds. The verdict compares every match and every group of the two.
Every way at once
Comb compiles a pattern to a small program. Most instructions read one character: a letter, any character, a class like [a-z]. The rest decide where to go: split tries two ways, jump goes back for a loop, save notes where a group starts or ends.
A backtracking engine, the kind in every browser, follows one way through the program, and when it fails it goes back to the last split and tries the other. Comb follows every way together. Each way is a thread, and all threads read the same character before any reads the next. A thread that cannot read its character dies, and at a split it becomes two. This is the Pike VM, after Rob Pike, who wrote it for the editor sam, on an idea of Ken Thompson’s from the sixties.
The figure runs the pattern above on its text. Each row is an instruction, each column a place in the text, and each dot a thread that stood there. The darker the dot, the more the pattern prefers that thread.
The same answer as the browser
When several threads can match, a backtracking engine returns the one it found first, so its answer depends on order. In (a|ab)(c|bcd) on “abcd” it takes a before ab, and then has to take bcd: the match is the whole “abcd”, not the shorter “abc”. Comb keeps its threads in that same order. At a split the preferred way goes first, and a new attempt at the next place in the text goes behind every thread already running.
Two threads at the same instruction at the same place will do the same from there on, so Comb keeps only the first to arrive, the one the pattern prefers. That rule is why the work cannot grow past the length of the program times the length of the text. It is also why the groups come out as the browser’s do: the thread that is kept is the one a backtracking engine would have finished with.
Where JavaScript is particular
Most of the code is about details the specification sets and other engines do differently. At the start of each pass of a loop, the specification clears the groups inside it, so ((a)|b)+ on “ab” ends with the inner group empty. A loop over something that can match nothing stops when a pass moves nowhere, so (a*)* terminates. Comb compiles a mark at the start of such a pass and a check at its end. Whether a pass has moved yet is then part of what a thread is, so two threads at one instruction are only the same if they agree on it.
The web also keeps an older grammar alive. A lone { or ] is a character, \101 is an octal “A”, and [\d-z] is a class of digits, a dash and a “z”. Comb reads all of it the way the browser does.
The first run of the corpus below found a bug the hand-written tests had missed. When the first attempt died at once, as it does for a pattern that starts with $, Comb stopped instead of trying the next place in the text, so $ on its own never matched.
Held against
A seeded generator writes random patterns from every part of the grammar Comb reads: classes, escapes, groups, lazy and greedy loops, assertions, the old grammar, and patterns that are not valid at all. Each one runs on a random text with random flags, in Comb and in the browser’s RegExp, and every match and every group must be the same. A pattern the browser rejects, Comb must reject too. Run it here against your browser’s engine:
Each dot is a pattern: violet when both engines agree, red when they do not.
The same corpus runs from the command line against the in Node:
$ node web/notes/comb/corpus.mjs 200,000 random patterns against V8 12.4.254.21-node.33, in 11.8 s 199,842 answered the same, 60,225 of them with a match 158 refused: the pattern holds a backreference 0 answered differently
A refused pattern is one where the generator wrote \8 after eight groups, which makes it a backreference.
The pattern that stops a browser
^(a+)+$ on a run of a’s that ends in a b cannot match. A backtracking engine only finds that out by trying every way to split the a’s between the inner and the outer loop, and each a doubles the number of ways. Comb steps three threads for each letter, whatever the length. Press Race to time both on this device, two a’s longer at each step.
From the command line, in Node:
$ node web/notes/comb/race.mjs
/^(a+)+$/ on n a's and a b, V8 12.4.254.21-node.33
n V8 (ms) Comb (ms) Comb threads stepped
12 0.15 0.04 36
14 0.11 0.05 42
16 0.29 0.06 48
18 1.22 0.06 54
20 4.74 0.07 60
22 22 0.08 66
24 76 0.03 72
26 368 0.04 78
28 1829 0.07 84
30 6896 0.04 90
Comb on a hundred thousand a's and a b: 122 ms, 300,000 threads stepped
This is not a curiosity. A pattern like it in a web server is a denial of service: one request with a long enough string holds a thread for as long as the attacker likes. Cloudflare’s network dropped most of its traffic for about half an hour when a firewall rule with a pattern of this kind went live, and Stack Overflow went down the same way on a pattern that trimmed spaces, whose time grew with the square of the length rather than doubling.
What it does not have
Comb leaves out what needs backtracking. A backreference such as (a+)\1 asks for the same text twice, and matching with backreferences is NP-hard, so no known algorithm matches them in linear time. Lookaround such as (?=…) asks a second question at one place in the text. Comb refuses both and says why, as Go’s regexp and Rust’s regex crate do. It also reads patterns without the u and v flags only. Its tests check each refusal.
has a linear engine of its own behind a flag, --enable-experimental-regexp-engine-on-excessive-backtracks, which Node lists with its default off. It hands a pattern over after too many steps back, on the same idea as Comb.
The source is in the portfolio’s repository under web/notes/comb/: comb.js for the parser, the compiler, the machine and the corpus, corpus.mjs and race.mjs for the commands, comb.test.mjs for the tests.