Tracking issue for RFC 2500, "Needle API (née Pattern API)"

[Centril]

This is a tracking issue for the RFC "Needle API (née Pattern API)" (rust-lang/rfcs#2500).

Feature gates:

• #![feature(needle)] (the traits and method in core::needle itself, and impl of these traits)
• #![feature(str_find_range)] (find_range, rfind_range, match_ranges and rmatch_ranges methods for str)
• #![feature(mut_str_needle_methods)] (split_mut, matches_mut, trim_mut etc for str)
• #![feature(slice_needle_methods)] (find, matches, trim_matches, replace, split etc for [T])
• #![feature(os_str_needle_methods)] (find, matches etc for OsStr)

Steps:

• Implement the RFC (cc @rust-lang/libs @kennytm @bluss -- can anyone write up mentoring instructions?)
• Stabilization PR (see instructions on forge)

Unresolved questions:

• Currently, due to Implied bounds rfcs#2089 and/or RFC: Associated type bounds of form MyTrait<AssociatedType: Bounds> rfcs#2289 not being implemented, using a Haystack in any algorithm would need to a redundant where clause.

• Naive vs. fast algorithm for T: !Ord

• Should we represent SharedHaystack using a more general concept of "cheaply cloneable"?

• With a benefit of simplified API, do we want to merge Consumer and Searcher into a single trait?

• Stabilization should require RFC 1672 (disjointness based on associated types).

[kennytm]

(Added a mention to RFC 1672 as promised)

[Avi-D-coder]

Will std::str::lines be implemented with using this API?
2500-needle.md#standard-library-changes does not explicitly state this.
I believe it would be a mostly backwards compatible change.

[SimonSapin]

Does it matter? This method only takes &self, and returns a dedicated type. Implementation detail changes that are black-box-invisible do not require RFCs. Or, by “mostly” do you mean you expect this change would be observable?

[Avi-D-coder]

Changing the internal implementation does appear to be API compatible.
What I was intending to ask, but didn't, is if it would make sense to treat std::str::lines like the other str methods being deprecated and replaced by Needle API alternatives?

[SimonSapin]

str::lines is already implemented as self.split_terminator('\n').map(LinesAnyMap), with LinesAnyMap stripping one trailing \r if any. (So equivalent to split_terminator with a "\r\n or \n" pattern.)

I think this is subtle enough to be worth a dedicated API. Even if it was as simple as split('\n'), I think this is a common enough use case.