why is Python's behavior with empty matches inconsistent with the regex crate's handling of empty matches?

[rootCircle]

What version of regex are you using?

v1.10.3

Describe the bug at a high level.

replace_all in the regex crate replaces empty strings before non-matching characters differently than Python's standard library regex engine. (Rust version of regex doesn't consider empty strings before non-matching characters as valid matches.)

What are the steps to reproduce the behavior?

1. Create a Regex object with the pattern r"x*" (matches zero or more "x"s).
2. Apply replace_all to the string "abxd" with a hyphen as the replacement string.
3. Observed output (Rust): "-a-b-d-"
4. Expected output (Python): "-a-b--d-"

Rust Code

use regex::Regex;

fn main() {
    let re = Regex::new(r"x*").unwrap();
    let hay = "abxd";

    println!("{:?}", re.replace_all(hay, "-"));
}

Equivalent Python Code:

import re

regex = r"x*"
test_str = "abxd"
subst = "-"

result = re.sub(regex, subst, test_str, 0, re.MULTILINE)

if result:
    print (result)

What is the actual behavior?

replace_all only replaces the empty string before "b" in Rust, not the one before "d".

What is the expected behavior?

Both empty strings should be replaced, resulting in "-a-b--d-".

By the way, I am not sure, if this is an intentional difference or a potential bug?

[BurntSushi]

Note that the pattern in your prose does not match the pattern in your programs. This was confusing to me. I've edited your prose to match your code. I've also converted this to a discussion because this isn't a bug, but is a good question.

But no, this is correct behavior. If anything, it's Python's behavior that is somewhat confounding here, because Python's behavior implies it is using an approach that reports overlapping matches. Despite the fact that Python's documentation for re.sub (and re.findall and re.finditer) claims that it reports non-overlapping matches. More generally, there is no specific goal for this crate to match the behavior of any other regex engine. So the existence of a difference does not imply a bug.

Since both re.sub and Regex::replace_all both utilize an iterator of purportedly non-overlapping matches, it makes more sense to focus on that then on the replacement routine. Looking at replacements is just looking at a downstream effect of differences in match semantics. So here's a Rust program that just prints the match offsets:

use regex::Regex;

fn main() {
    let re = Regex::new(r"x*").unwrap();
    let hay = "abxd";

    for m in re.find_iter(hay) {
        println!("{:?}", (m.start(), m.end()));
    }
}

And a Python program that does the same:

import re

regex = r"x*"
test_str = "abxd"
subst = "-"

for m in re.finditer(regex, test_str):
    print(m.span())

And now the Rust program's output:

$ cargo run -q
(0, 0)
(1, 1)
(2, 3)
(4, 4)

And Python:

$ python main.py
(0, 0)
(1, 1)
(2, 3)
(3, 3)
(4, 4)

This crate very specifically and very intentionally does not report the (3, 3) matches because it overlaps with the match at (2, 3). The Python folks think that this is a bug (see the links below), so they actually changed the behavior to what they have today.

The reason why regex engines differ here is because empty matches are somewhat of a strange beast. Namely, if you don't handle them specially during iteration over matches, an empty match won't advance the start position of the next search. And thus, it would result in an infinite loop. Therefore, if your regex engine provides iteration over all matches (not all do! but most do), then you must choose how to handle the case of empty matches. This crate does the thing that most other regex engines do: it treats non-empty matches immediately before or immediately after an empty match as overlapping, and thus does not permit those non-empty matches to be reported. Python's regex engine, however, allows such matches.

Fun fact: before Python 3.7, re.sub/re.finditer/re.findall behaved differently with respect to empty matches than they do today. See:

• Replace empty matches adjacent to a previous non-empty match in re.sub() python/cpython#76489 (also https://bugs.python.org/issue32308)
• https://bugs.python.org/issue25054 in particular suggests that searching ^|a in a and having that report only a match at 0..0 is a bug. But I'd disagree with that personally, since matches at 0..0 and 0..1 are overlapping.

If you read the above issues, there is a claim that Python is now more consistent with other engines, but as far as I can tell, this isn't generally true. While it does seem that Python now matches Perl's behavior, it specifically does not match the behavior of at least the following engines: .NET, D, Go, ICU, Java, Javascript (v8 and regress), RE2 and, of course, this crate. There is also PCRE2 to consider, but PCRE2 doesn't really define an iteration protocol, so it's hard to say whether Python is "consistent" with it or not.

[rootCircle]

Thank you for the detailed explanation! I understand now that the difference in behavior between the regex crate and Python's standard library is not a bug, but rather a deliberate design choice. It's helpful to see the different approaches and the reasons behind them. The additional references and insights you provided are valuable, and I'll definitely check them out if I want to delve deeper.

While I was initially confused, your explanation has been very informative and has helped me grasp the nuances involved. Thanks again for taking the time to clarify!