Can `memchr` be an optional dependency?

[sffc]

I'd like to use bstr, but I don't need the search functions like find_byte and find_byteset that require the memchr dependency. It seems that those functions could be feature-gated, especially since ByteSlice is a sealed trait.

Would you accept a pull request making memchr an optional, default dependency?

[BurntSushi]

It's not just find_byte. It's also find too. It seems a little weird to make substring search---a fundamental operation of a byte string library---optional. Although I do grant that it is probably possible?

What is causing the hesitancy to depend on memchr? It is pretty ubiquitous and likely to end up in your dependency tree by some other means anyway.

[sffc]

Our use case is primarily to get the trait impls like serde (and others, see #183), and we try to keep icu4x's recursive dependency tree as thin as possible. I verified that memchr is already in the dependency tree, however, via regex-automata which we use in icu_list. We're also considering making our own crate that just has the trait impls without additional functionality, but it would be nice to stick with a single ecosystem type for a "potentially ill-formed UTF-8 byte string". See unicode-org/icu4x#3546

[BurntSushi]

Yeah I see. That is a conundrum indeed. If the optional dependency on memchr is the only thing holding y'all up, I think I'd be fine with it. It doesn't really cost much and I am generally a fan of slimming down dependency trees. So doing what I can to help there is good I think. So I think my overall answer here is "yes."

[lopopolo]

I presume this would require adding a new default feature for memchr and the find APIs? This would be a breaking change to bstr for dependents that declare bstr in Cargo.toml with default-features = false.

[BurntSushi]

Ug right. Sigh. That's frustrating. I didn't consider that when I released bstr 1.0 either. I should have.

The only other alternative would be to provide "naive" implementations of things that use memchr today whenever memchr isn't disabled. I believe this would ultimately be a breaking change though.

On the one hand, you might look at it as a compatible change that introduces a potentially severe performance footgun. For example, users of bstr with default-features = false might expect ByteSlice::find_byte to be an optimized routine that is "fast." But if it all of a sudden gets swapped out with haystack.position(|&b| b == needle), then they're likely (and justifiably so) to feel hoodwinked. But, it's probably not strictly speaking a breaking change.

On the other hand, ByteSlice::find provides a time complexity bound of O(needle.len() + haystack.len()). That is not easy to accomplish using naive means without dynamic memory allocation (which is the case when default-features = false). AFAIK, it requires something non-naive. I can't even think of something that would work other than Two-Way. And I don't think I could swallow the pill of copying Two-Way from memchr into bstr just for the case when memchr isn't enabled. Some very minor simplifications could be made to it (e.g., removing prefilter optimizations), but the nuts and bolts of it are rather complex.

Unfortunately, I'm not sure I see a way around this. I could put out bstr 2.0, but I don't think dropping memchr is worth doing that. In particular, I do think that memchr is ubiquitous and very likely to end up in any given dependency tree anyway.