find_byteset (and related) should return matches for an empty set

[BurntSushi]

This code

use bstr::{B, ByteSlice};

fn main() {
    let haystack = B("abcxyz");
    println!("{:?}", haystack.find_byteset(""));
}

prints None, but it should print Some(0). Also, it seems like the empty set is part of the empty haystack, so this

use bstr::{B, ByteSlice};

fn main() {
    let haystack = B("");
    println!("{:?}", haystack.find_byteset(""));
}

should also print Some(0) I think?

This behavior is consistent with substring searches for an empty needle.

[thomcc]

Hmm... I'm not sure I agree. The semantics of find_byteset are finding the position of a byte which is a member of a set. No bytes are members of the empty set, so returning position 0 for it would be incorrect, no?

That said, I'd agree with you for find_not_byteset.

[BurntSushi]

I think I see "empty set" as equivalent to "empty string," and "empty set" matches at every position, just like "empty string" does.

[thomcc]

Actually, I'm not sure if I 100% agree for find_not_byteset — the second part:

use bstr::{B, ByteSlice};

fn main() {
    let haystack = B("");
    println!("{:?}", haystack.find_not_byteset(""));
}

This returns None, which I think is correct, since I think it's probably always incorrect if it returns an index that isn't addressable in the slice — byteset matches are always a span of at least one byte, even for find_not_byteset.

In regex terms, find_not_byteset("") is analogous to matching r"\p{Any}", and find_byteset("") is analogous to matching r"\P{Any}" (or something — the analogy doesn't 100% work, since its matching bytes and not characters). It's not analogous to matching the empty needle.

That is to say, AFAICT I don't see any bugs in find_byteset and find_not_byteset current semantics for empty sets.

[thomcc]

Also, I guess the analogy doesn't totally work because at least for Rust regex, \P{Any} tells me that "empty character classes are not allowed". Which is fair, I guess.

[BurntSushi]

I think you might have convinced me. Eventually, empty classes in regexes will be allowed, and yeah, they are supposed to be treated as "fail" instructions: they can never match anything.

[thomcc]

Anyway, the documentation of find_byteset says

Returns the index of the first occurrence of any of the bytes in the provided set.

Personally, I think this means that it shouldn't return:

1. An index that isn't in-bounds of the string.
2. An index for which, if you constructed (say) a BTreeSet containing all the bytes, set.contains(&bstr[index]) would return false.

And thus the current semantics are at least in line with the documentation.

[BurntSushi]

Yeah the reason why I wasn't immediately rejecting my idea because of the index issue is because searching for an empty needle in an empty haystack returns a starting offset. But I think the right way to look at that is that results from a substring search are not meant to be indexed, but rather, sliced. And of course &haystack[0..needle.len()] is valid when both haystack and needle are empty.

[BurntSushi]

Closing this as invalid, since I was very wrong. I am updating the docs to make sure these cases are more explicitly documented.

I've added these two lines to the find_byteset example:

    /// // The empty byteset never matches.
    /// assert_eq!(None, b"abc".find_byteset(b""));
    /// assert_eq!(None, b"".find_byteset(b""));

I've also added these two lines to the find_not_byteset example:

    /// // The negation of the empty byteset matches everything.
    /// assert_eq!(Some(0), b"abc".find_not_byteset(b""));
    /// // But an empty string never contains anything.
    /// assert_eq!(None, b"".find_not_byteset(b""));