Summary
For the pattern [^()]*(?:\([^()]*\))?[^()]*: searched against the haystack $(:):, regex_automata::meta::Regex::find returns a match at 2..3 (just the colon between the parentheses). regex_automata::nfa::thompson::pikevm::PikeVM and regex_automata::hybrid::regex::Regex both return 0..5 (the entire string) on the same input. The PikeVM/lazy-DFA result is the leftmost match — META is picking a strictly later start position.
Repro
Cargo.toml:
[package]
name = "repro"
version = "0.0.0"
edition = "2021"
[dependencies]
regex-automata = "0.4.14"
src/main.rs:
use regex_automata::Input;
fn main() {
let pat = r"[^()]*(?:\([^()]*\))?[^()]*:";
let hay = b"$(:):";
let meta = regex_automata::meta::Regex::new(pat).unwrap().find(hay);
let pikevm = {
use regex_automata::nfa::thompson::pikevm::PikeVM;
let pv = PikeVM::new(pat).unwrap();
let mut c = pv.create_cache();
pv.find_iter(&mut c, Input::new(hay)).next()
};
let dfa = {
use regex_automata::hybrid::regex::Regex as H;
let r = H::new(pat).unwrap();
let mut c = r.create_cache();
r.find(&mut c, Input::new(hay))
};
println!("META : {:?}", meta.map(|m| (m.start(), m.end())));
println!("PikeVM: {:?}", pikevm.map(|m| (m.start(), m.end())));
println!("DFA : {:?}", dfa.map(|m| (m.start(), m.end())));
}cargo run --release output:
META : Some((2, 3))
PikeVM: Some((0, 5))
DFA : Some((0, 5))
Discussion
Standard PCRE/RE2 leftmost-first semantics on $(:): for the pattern above:
- At position 0, the pattern matches
$(:): (length 5): [^()]* → $, (?:\([^()]*\))? → (:), [^()]* → empty, : → :.
- At position 2, the pattern matches
: (length 1): both [^()]* are empty, the optional group is empty, the literal : matches.
Position 0 is strictly earlier, so it's the leftmost match. PikeVM and the lazy DFA agree on it. META picks the position-2 match.
The pattern shape is artificial-looking but I ran into it via a real-world syntect / sublime-syntax grammar; the reduction traces back to a fancy-regex seek pre-filter approximation for a Makefile rule-detection lookahead. Three properties seem to matter for triggering it:
- A negated character class (e.g.
[^()]) on both sides of an optional group.
- An optional group whose body can match at multiple offsets inside the negation gap (the
\([^()]*\) here — the \( and \) are literally outside the negated class, and [^()]* inside is permissive).
- A trailing literal (
:) that appears both inside and outside the gap.
The earliest variant I have where all three engines agree on the leftmost is when the leading negated-class run is forced to non-empty by an equality somewhere in the haystack ($(a=b): agrees across engines — there META correctly picks 0..6). It seems to be the combination of a permissively-empty leading run plus an optional group that can absorb the rest that drives META's overshoot.
I've confirmed the same shape of divergence on slightly longer patterns derived from a C++ <> template-detection lookahead (META picks the inner identifier; PikeVM picks the outer one), so the pattern above is the smallest of a small family. Happy to share the longer variants and the syntect-side context if useful, but the 5-byte haystack above should be enough to reproduce.
Versions
regex-automata = "0.4.14" (latest at time of filing — cargo update resolves to 0.4.14)- Rust 1.91.1 (release build, no LTO)
- macOS 25.4.0, aarch64
Reduced via stefanobaghino/fancy-regex@wip/diagnostic-pr249 (src/seek.rs::tests::diagnostic_*) where it surfaces as a leftmost-first disagreement between META and PikeVM on the seek over-approximation for three independent .sublime-syntax grammars. See fancy-regex/fancy-regex#249 for the downstream context.
Summary
For the pattern
[^()]*(?:\([^()]*\))?[^()]*:searched against the haystack$(:):,regex_automata::meta::Regex::findreturns a match at2..3(just the colon between the parentheses).regex_automata::nfa::thompson::pikevm::PikeVMandregex_automata::hybrid::regex::Regexboth return0..5(the entire string) on the same input. The PikeVM/lazy-DFA result is the leftmost match — META is picking a strictly later start position.Repro
Cargo.toml:src/main.rs:cargo run --releaseoutput:Discussion
Standard PCRE/RE2 leftmost-first semantics on
$(:):for the pattern above:$(:):(length 5):[^()]*→$,(?:\([^()]*\))?→(:),[^()]*→ empty,:→:.:(length 1): both[^()]*are empty, the optional group is empty, the literal:matches.Position 0 is strictly earlier, so it's the leftmost match. PikeVM and the lazy DFA agree on it. META picks the position-2 match.
The pattern shape is artificial-looking but I ran into it via a real-world syntect / sublime-syntax grammar; the reduction traces back to a fancy-regex seek pre-filter approximation for a Makefile rule-detection lookahead. Three properties seem to matter for triggering it:
[^()]) on both sides of an optional group.\([^()]*\)here — the\(and\)are literally outside the negated class, and[^()]*inside is permissive).:) that appears both inside and outside the gap.The earliest variant I have where all three engines agree on the leftmost is when the leading negated-class run is forced to non-empty by an equality somewhere in the haystack (
$(a=b):agrees across engines — there META correctly picks0..6). It seems to be the combination of a permissively-empty leading run plus an optional group that can absorb the rest that drives META's overshoot.I've confirmed the same shape of divergence on slightly longer patterns derived from a C++
<>template-detection lookahead (META picks the inner identifier; PikeVM picks the outer one), so the pattern above is the smallest of a small family. Happy to share the longer variants and the syntect-side context if useful, but the 5-byte haystack above should be enough to reproduce.Versions
regex-automata = "0.4.14"(latest at time of filing —cargo updateresolves to0.4.14)Reduced via stefanobaghino/fancy-regex@wip/diagnostic-pr249 (
src/seek.rs::tests::diagnostic_*) where it surfaces as a leftmost-first disagreement between META and PikeVM on the seek over-approximation for three independent.sublime-syntaxgrammars. See fancy-regex/fancy-regex#249 for the downstream context.