regex and regex_lite disagree on lazy empty matches

[orlp]

What version of regex are you using?

regex == 1.12.3
regex_lite == 0.1.9

Describe the bug at a high level.

An empty lazy (??) match has different behavior between the two engines.

What are the steps to reproduce the behavior?

let pattern = "b??a|b??a?";
let haystack = "bba";
dbg!(regex::Regex::new(pattern).unwrap().find_iter(haystack).collect::<Vec<_>>());
dbg!(regex_lite::Regex::new(pattern).unwrap().find_iter(haystack).collect::<Vec<_>>());

What is the actual behavior?

[src/main.rs:8:5] regex::Regex::new(pattern).unwrap().find_iter(haystack).collect::<Vec<_>>() = [
    Match {
        start: 0,
        end: 0,
        string: "",
    },
    Match {
        start: 1,
        end: 1,
        string: "",
    },
    Match {
        start: 2,
        end: 3,
        string: "a",
    },
]
[src/main.rs:9:5] regex_lite::Regex::new(pattern).unwrap().find_iter(haystack).collect::<Vec<_>>() = [
    Match {
        start: 0,
        end: 0,
        string: "",
    },
    Match {
        start: 1,
        end: 3,
        string: "ba",
    },
]

What is the expected behavior?

I don't know, but the same behavior for both. I found it through fuzzing.

[orlp]

Note that this reproduces on the branch which claims to fix the ReverseSuffix bug (#1355), so I think it's a different bug.

[BurntSushi]

Interesting. Via regex-cli:

[andrew@duff master]$ cargo r -qp regex-cli -- find match lite --no-table -p 'b??a|b??a?' -y 'bba'
0:0:0:
0:1:3:ba
[andrew@duff master]$ cargo r -qp regex-cli -- find match pikevm --no-table -p 'b??a|b??a?' -y 'bba'
0:0:0:
0:1:1:
0:2:3:a
[andrew@duff master]$ cargo r -qp regex-cli -- find match backtrack --no-table -p 'b??a|b??a?' -y 'bba'
0:0:0:
0:1:1:
0:2:3:a
[andrew@duff master]$ cargo r -qp regex-cli -- find match hybrid --no-table -p 'b??a|b??a?' -y 'bba'
0:0:0:
0:1:1:
0:2:3:a
[andrew@duff master]$ cargo r -qp regex-cli -- find match meta --no-table -p 'b??a|b??a?' -y 'bba'
0:0:0:
0:1:1:
0:2:3:a

I also added this to a new file in benchmarks/definitions/scratch.toml in rebar:

[[bench]]
model = 'count'
name = 'empty-regex-non-greedy-test'
regex = 'b??a|b??a?'
haystack = { contents = 'bba' }
count = 3
engines = [
  'd/dmd/std-regex',
  'dotnet',
  'dotnet/compiled',
  'dotnet/nobacktrack',
  'go/regexp',
  'icu',
  'java/hotspot',
  'javascript/v8',
  'pcre2',
  'pcre2/jit',
  'perl',
  'python/re',
  'python/regex',
  're2',
  'regress',
  'rust/regex',
  'rust/regex/lite',
]

Then running it I get:

$ rebar measure -t -f scratch/empty-regex-non-greedy-test
scratch/empty-regex-non-greedy-test,count,d/dmd/std-regex,2.112,"count mismatch, expected 3, got 2"
scratch/empty-regex-non-greedy-test,count,dotnet,10.0.4,OK
scratch/empty-regex-non-greedy-test,count,dotnet/compiled,10.0.4,OK
scratch/empty-regex-non-greedy-test,count,dotnet/nobacktrack,10.0.4,OK
scratch/empty-regex-non-greedy-test,count,go/regexp,1.26.3,"count mismatch, expected 3, got 2"
scratch/empty-regex-non-greedy-test,count,icu,72.1.0,OK
scratch/empty-regex-non-greedy-test,count,java/hotspot,26+35-2893,OK
scratch/empty-regex-non-greedy-test,count,javascript/v8,26.1.0,OK
scratch/empty-regex-non-greedy-test,count,pcre2,10.47 2025-10-21,"count mismatch, expected 3, got 2"
scratch/empty-regex-non-greedy-test,count,pcre2/jit,10.47 2025-10-21,"count mismatch, expected 3, got 2"
scratch/empty-regex-non-greedy-test,count,perl,5.42.2,"count mismatch, expected 3, got 4"
scratch/empty-regex-non-greedy-test,count,python/re,3.14.5,"count mismatch, expected 3, got 4"
scratch/empty-regex-non-greedy-test,count,python/regex,2026.5.9,"count mismatch, expected 3, got 4"
scratch/empty-regex-non-greedy-test,count,re2,2025-11-05,"count mismatch, expected 3, got 2"
scratch/empty-regex-non-greedy-test,count,regress,0.9.1,OK
scratch/empty-regex-non-greedy-test,count,rust/regex,1.12.2,OK
scratch/empty-regex-non-greedy-test,count,rust/regex/lite,0.1.8,"count mismatch, expected 3, got 2"

Which means that for this regex, engine behavior is all over the place. Some engines get 2 matches, others get 3 and some get 4. Empty matches are always kind of a wildcard.

With that said, unless there's a good reason to do otherwise, we should match re2 and go/regexp. So this will need some investigation.

[BurntSushi]

At the very least, regex-lite should match regex here. So on that basis alone, this is a bug.

[orlp]

After looking at it some more, I believe regex-lite and re2 are correct here, with "" and "ba" as matches respectively.

In order for regex to produce the empty match starting at position 1 it must use the second part of the alternation, b??a?. But the first alternation b??a does actually match at that position (with ba), so it violates the "first matching alternation" semantics.