regex matches everything for empty string ("") as a pattern

[mrl5]

is it expected behavior that Regex::new("") matches any &str (notice empty string "" as a pattern)?

I've checked this docs and there is no info about such behavior there:

• https://docs.rs/regex/latest/regex/struct.Regex.html#method.is_match
• https://docs.rs/regex/latest/regex/struct.Regex.html#method.new

lets consider this code:

use regex::Regex;
use std::collections::HashSet;

fn get_matches(re_pattern: &str, feed: &[Box<str>]) -> HashSet<String> {
    let re = Regex::new(re_pattern).unwrap();
    feed.iter()
        .filter(|feed_entry| re.is_match(feed_entry))
        .map(|x| x.to_string())
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_should_ignore_empty_string_as_a_pattern() {
        let test_matches = [
            Box::from("foo"),
            Box::from("bar"),
        ];

        assert_eq!(get_matches("", &test_matches).len(), 0);
    }
}

it will result in:

failures:

---- searchers::tests::it_should_ignore_empty_string_as_a_pattern stdout ----
thread 'searchers::tests::it_should_ignore_empty_string_as_a_pattern' panicked at 'assertion failed: `(left == right)`
  left: `2`,
 right: `0`', crates/cpe-tag/src/searchers.rs:97:9

tested with regex-1.5.5:

[dependencies]
regex = "1.5.5"

[leighmcculloch]

I think it is expected behavior. Unless the regex has beginning and end markers it will partial match. This is consistent with regex matching in other ecosystems too, for example: https://go.dev/play/p/l4aoWM_sZMI.

[leighmcculloch]

The docs note that the match is in the string, and not match against the whole string:

Returns true if and only if there is a match for the regex in the string given.

Ref: https://docs.rs/regex/1.6.0/regex/struct.Regex.html#method.is_match

[mrl5]

This is consistent with regex matching in other ecosystems too

yeah.. I can confirm it also with JavaScript:

(new RegExp('')).test('foobar') ? console.log('matched') : console.log('unmatched');

[BurntSushi]

Yeah absolutely this is correct. What do you think the behavior should be?

The behavior is solidly correct on both pragmatic and theoretical fronts:

• I don't know of any regex engine that behaves differently. If you do, I would be happy to hear about it.
• From a theoretical perspective, the empty regex describes the empty language. The empty language is a sub-language of every other language. It's like how the empty set is a subset of every set.

It is possible to write a regex that is the opposite of the empty set, i.e., one that will not match anything. You could write it like so: [a&&b]. Currently though, such patterns won't compile. (I intend to lift that restriction some day.)

[mrl5]

What do you think the behavior should be?

actually idk, that's why I opened "QA discussion" instead of GitHub issue

however, that being said I had a WTF moment when I discovered the described behavior. Maybe it would be worth documenting? What do you think?

[BurntSushi]

Certainly.

[zhaojiangbin]

It is possible to write a regex that is the opposite of the empty set, i.e., one that will not match anything. You could write it like so: [a&&b]. Currently though, such patterns won't compile. (I intend to lift that restriction some day.)

A pattern that matches nothing would be nice if it is not expensive to execute.

In this program I am working on, I join a list of valid (sub)patterns with '|' to compose the final pattern to compile, i.e. Regex::new("foo|bar").unwrap(). Because the empty pattern matches anything, I have to wrap the Regex instance in Option and handle the None case whenever it is used.

[BurntSushi]

That works today. Try it. [a&&b] matches nothing.

You could also previously write a\bz which would also never match.

[zhaojiangbin]

Oh nice! I should have read the doc more carefully. It works great.

If you don't mind, how much overhead is it in terms of big O? O(m) where m is the length of haystack? Or is it possible to short-circuit and return immediately for not matching? Not that O(m) is too slow for my current case.

And thanks for all your work on Rust!

[BurntSushi]

There are no additional guarantees made specifically about the time complexity with respect to regexes that can never match. I would encourage you to develop a benchmark. If there's an optimization missing on the regex crate side, you can file an issue.