Repro (ugrep 7.8.3, master 8cda03e, Linux x86_64)
ugrep -G -o '"content":"[^"]*coder[^"]\{0,300\}' /dev/nullNo input needed (/dev/null). Compilation runs ~95 s and reaches 14.3 GB max RSS before finally reporting exceeds complexity limits. Under a tighter ulimit -v it dies earlier with std::bad_alloc. -U reduces the growth ~3x (UTF-8 expansion of [^"] amplifies it) but does not prevent it.
Minimal shape: a counted repetition that overlaps a preceding repeat —
ugrep -G '[^"]*coder[^"]\{0,100\}' /dev/null # same blowup
ugrep -G 'coder[^"]\{0,300\}' /dev/null # fine without the leading [^"]*Mechanism
The DFA for this shape genuinely explodes (the automaton must track every candidate iteration count of the trailing repeat for every match start admitted by the preceding [^"]*). The existing guard vno_ > DFA::MAX_STATES (≈5.57M states) does fire — but only after minutes, because each of those states carries a positions vector with hundreds of iteration-tagged entries, i.e. memory grows ~2.5 KB per state while the limit only counts states.
Measured Σ pos.size() over all DFA states:
| Pattern |
positions |
104k-word dictionary via -f |
~1 (tree DFA) |
500-word alternation + [a-z]* suffix |
5.5k |
[0-9]{1,4096} |
8.2k |
| email/UUID/IP/base64 regexes |
37–1.5k |
| the pathological pattern above |
>32M and climbing |
Impact
Claude Code (Anthropic's agentic CLI) bundles ugrep 7.5.0 as its grep replacement, so machine-generated patterns hit this in the wild: one such pattern grew to 11 GB and pushed a 125 GB host into memory-pressure thrash, freezing sibling processes (anthropics/claude-code#83342).
Proposed fix
PR follows: track accumulated positions stored in DFA states and raise the existing exceeds complexity limits error when the total passes a DFA::MAX_POSITIONS cap (4M — ~500x above the heaviest legitimate pattern measured). The pathological pattern then fails in 0.59 s at 155 MB with the same user-visible error, and make check passes.
Repro (ugrep 7.8.3, master 8cda03e, Linux x86_64)
ugrep -G -o '"content":"[^"]*coder[^"]\{0,300\}' /dev/nullNo input needed (
/dev/null). Compilation runs ~95 s and reaches 14.3 GB max RSS before finally reportingexceeds complexity limits. Under a tighterulimit -vit dies earlier withstd::bad_alloc.-Ureduces the growth ~3x (UTF-8 expansion of[^"]amplifies it) but does not prevent it.Minimal shape: a counted repetition that overlaps a preceding repeat —
Mechanism
The DFA for this shape genuinely explodes (the automaton must track every candidate iteration count of the trailing repeat for every match start admitted by the preceding
[^"]*). The existing guardvno_ > DFA::MAX_STATES(≈5.57M states) does fire — but only after minutes, because each of those states carries a positions vector with hundreds of iteration-tagged entries, i.e. memory grows ~2.5 KB per state while the limit only counts states.Measured
Σ pos.size()over all DFA states:-f[a-z]*suffix[0-9]{1,4096}Impact
Claude Code (Anthropic's agentic CLI) bundles ugrep 7.5.0 as its
grepreplacement, so machine-generated patterns hit this in the wild: one such pattern grew to 11 GB and pushed a 125 GB host into memory-pressure thrash, freezing sibling processes (anthropics/claude-code#83342).Proposed fix
PR follows: track accumulated positions stored in DFA states and raise the existing
exceeds complexity limitserror when the total passes aDFA::MAX_POSITIONScap (4M — ~500x above the heaviest legitimate pattern measured). The pathological pattern then fails in 0.59 s at 155 MB with the same user-visible error, andmake checkpasses.