[BUG] exec() throws RangeError: Maximum call stack size exceeded on a quantified run of ~4 MiB (V8) #137

Describe the bug

On V8 (Node, Deno, Chromium), PartialMatchRegExp.exec() throws RangeError: Maximum call stack size exceeded once a single quantified atom has to repeat about 4 million times. The native pattern handles the same input without trouble.

The cause is the shape of the compiled partial pattern. Each atom becomes (?:atom|$(?![\s\S])), so a quantifier now repeats a group that contains an alternation:

V8's irregexp runs a quantified single-character atom (\S+) as a tight loop with no per-iteration state. A quantified group with alternatives can't take that path, so it pushes a backtrack entry for every iteration.

V8's regexp backtrack stack has a fixed maximum, and around 4 million entries it's exhausted. The error is reported as a stack overflow, and --stack-size doesn't affect it.

To Reproduce

import PartialMatchRegExp from "regex-partial-match";

const input = "x".repeat(8 * 2 ** 20);

/\S+/.exec(input)[0].length;                      // 8388608
new PartialMatchRegExp(/\S+/).exec(input);         // RangeError: Maximum call stack size exceeded

The compiled form on its own reproduces it with native RegExp, so it isn't the wrapper. Single run of x, regex-partial-match 2.1.0:

• Threshold for the compiled \S+: between 4,182,016 and 4,243,456 characters. It's the same on Node 24.20.0, Node 26.11.0 and Deno 2.7.10, and unchanged by node --stack-size=8000.
• Bun 1.3.0 (JavaScriptCore) doesn't throw on any of these, up to 64 MiB.
• Any unbounded atom is affected: [^{}]* inside /\{\{[^{}]*\}\}/ overflows the same way when the input is "{{" followed by a long run with no closing braces.

Expected behaviour

exec() on the partial pattern succeeds wherever exec() on the original does, or at least doesn't overflow at a far smaller input than the original.

Additional context

Impact. Streaming consumers feed the partial pattern exactly this input: a held candidate that keeps growing. In replace-content-transformer, RegexSearchStrategy errors the stream once a pending match passes ~4 MiB with default options.

It's seen at 6–8 MiB there, because its re-scan backoff only re-evaluates when the buffer has doubled. That applies to /\S+/ over unbroken text, and to /\{\{[^{}]*\}\}/ after an unclosed {{. replace-content-transformer#100 proposes a finite buffer ceiling that keeps it clear of this, but any consumer without one is exposed.

Candidate fix: rewrite quantified single-character atoms so the alternation sits outside the loop. When the repeated atom matches exactly one character (a literal, a class, ., or an escape such as \S, \w, \p{…}), then for greedy quantifiers:

Here E is $(?![\s\S]), and lazy quantifiers keep their ? on each part. The reasoning: E is zero-width and only matches at the end of the input, so in today's form an E iteration can only come after the last X, and consumes nothing. The candidate accepts the same strings, with the same match lengths and the same greedy or lazy preference, and lets V8 use its native loop for X.

A quick differential check with native RegExp, comparing today's compiled shape with the candidate for X = [ab], found no differences in match index, match text or capture over 20,001 random inputs drawn from abcd, up to 8 characters long. It covered each of +, *, {2,}, {2,4}, +?, *? and {2,4}?, with the atom alone, followed by (?:c|E), and captured then followed by (?:c|E). That checks the rewrite rule, not the library's compiler.

Before adopting it, check that:

• the existing test suite and any differential or fuzz tests pass unchanged, including captures around the atom ((\S+)), atoms inside lookarounds, and the hitEnd and features modules if they inspect the compiled shape;
• lazy quantifiers (X+?, X*?, X{n,m}?) keep the same preference order;
• the dynamic backreference path (execDynamic) builds its per-atom partials the same way, or gets the same rewrite.

What the rewrite doesn't cover. A quantified multi-character group ((?:ab)+, (?:\w|-)+) still needs per-iteration alternation in its partial form, so it keeps the ~4 M iteration limit. That's a narrower case worth documenting under the caveats, with the limit and the V8-only scope, as a known limitation even if the single-character rewrite lands.

Reproduce the sweep:

const MiB = 2 ** 20;
const tryExec = (re, input) => {
  try { re.exec(input); return "ok"; } catch (e) { return `throws ${e.constructor.name}`; }
};
for (const re of [/\S+/, /(?:\S|$(?![\s\S]))+/, /(?:\S|y)+/, /(?:\S)+/, /(?:\S+|$(?![\s\S]))/]) {
  console.log(String(re), [4, 8, 64].map((n) => `${n} MiB ${tryExec(re, "x".repeat(n * MiB))}`).join(", "));
}

Measured on Apple M4.