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).