Tracking issue for string patterns

[alexcrichton]

(Link to original RFC: rust-lang/rfcs#528)

This is a tracking issue for the unstable pattern feature in the standard library. We have many APIs which support the ability to search with any number of patterns generically within a string (e.g. substrings, characters, closures, etc), but implementing your own pattern (e.g. a regex) is not stable. It would be nice if these implementations could indeed be stable!

Some open questions are:

• Have these APIs been audited for naming and consistency?
• Are we sure these APIs are as conservative as they need to be?
• Are we sure that these APIs are as performant as they can be?
• Are we sure that these APIs can be used to implement all the necessary forms of searching?

cc @Kimundi

[bluss]

String Patterns RFC tracking issue: #22477

Stabilization not only impacts implementing the pattern traits, but also of course detailed use of the Searcher trait, .next_match(), .next_reject() and so on.

[jneem]

I'm having trouble seeing the purpose of the next() method; in all the examples I look at, it's faster and cleaner to just implement next_match() and next_reject() individually. For example, these two functions can be implemented for CharEqSearcher as one-liners using Iterator::find. Moreover, if you want an optimized implementation of Searcher for an ASCII char then in implementing next() you need to choose between an implementation that returns rejections quickly and an implementation that skips quickly over the input (e.g. using SIMD) in order to quickly find a match.

[bluss]

@jneem the StrSearcher uses the same code for next() and next_match(), but specialized for each case, so that the next_match() case is much faster. It works well.

[jneem]

@bluss I think that helps make my point: AFAICT, all the users of Searcher only call next_match() and next_reject(). Therefore, the only purpose of next() AFAICT is to make implementing Searcher easier -- you only need to implement one function instead of two. But that benefit isn't born out in practice. StrSearcher implements two methods anyway, and it would be simpler to implement next_reject() instead of next(). CharEqSearcher implements next() only, but it would be simpler and cleaner to optimize if it implemented next_match() and next_reject() instead.

[jneem]

Oops, I missed one: Pattern uses Searcher::next() for the default implementation of is_prefix_of.

[mkpankov]

This is useful, I'd like to use it on stable.

[bluss]

cc @BurntSushi, Regex is the major pattern user and it would be great for everyone if it was stable because of that.

[bluss]

@BurntSushi Are the Pattern traits sufficient for Regex? Any design issues?

[BurntSushi]

I wrote the impl for Regex a while back, which does indeed only implement next: https://github.com/rust-lang-nursery/regex/blob/master/src/re.rs#L1104 I seem to recall that it was tricky to get the corner cases right, but that isn't too surprising. I otherwise found it pretty straight forward.

One thing that I don't think is representable with the Pattern API is fast retrieval of all matches from a suffix table. In particular, matches are reported as part of lexicographically sorted suffixes rather than order of occurrence in the string, so it can't satisfy the contract of Searcher without an additional cost. (I've already talked to @Kimundi about this, and I don't think it's a major issue. Suffix tables are a pretty niche data structure.)

[aturon]

Nominating for discussion. Not sure whether this is ready for stabilization, but I'd like for the team to dig into it a bit.

[alexcrichton]

Unfortunately the libs team didn't get a chance to talk about this in terms of stabilization for 1.8, but I'm going to leave the nominated tag as I think we should chat about this regardless.

[Kimundi]

Today I investigated a bit what would need to be done to generalize the Pattern API to arbitrary slice types. As part of that I also took a more pragmatic route to the involved types and interfaces based on these assumptions:

• Generally, the API should suit the std library, with more complex scenarios being handled by external libraries.
• Thus, providing the same feature set for libstd slice types like str, [T] or OsStr is more important than having a API that can accommodate the most general kind of "slice type".
• Having an more simple to maintain API suitable for the existing consumers like find, split and match_indices is a higher priority than having a more complicated API that could accommodate exotic consumers.
• Being able to reuse the API for mutable slices is worth a moderate increase in API verbosity and unsafety-based interface surfaces.

A very rough sketch of the result can be seen below. Note that this is only the Pattern traits itself, without actual integration in the std lib or comprehensive re implementation of the existing types.

https://github.com/Kimundi/pattern_api_sketch/blob/master/src/v5.rs

The core changes are:

• The Pattern trait now has an input parameter for the slice type. This turns Pattern<'a> into Pattern<&'a str> and allows for Pattern<&'a mut [T]>.
• next() got removed, leaving only next_{match/reject}(). This has been done because none of the existing types could make use of the return value of next(), and none of the existing implementations benefited from needing to implement it.
  • As part of that change, the Pattern::is_{prefix/suffix}_of() methods are no longer default-implemented. But seeing how the manual implementation for a given pattern-slice combination is usually simple and straight forward, this does not appear to be a problem.
• In order to allow for mutable slices and shared code of general iterators like match_indices between slice types,
  the return values of next_*() are now associated types of the slice type.
  They have an API that allows them to be used as abstract raw pointer types, which means generic code can use them relatively freely to create slices at or between matches, at the cost of requiring unsafe code and needing to follow aliasing rules.

---

Changes in regard to the open questions:

• In addition to the existing interface, the new SearchPtrs trait has gained new ad-hoc named elements which would require additional name audition. Also, Pattern continues to be a confusing name in a language with pattern matching...
• The sketched API change is somewhat more conservative by getting rid of the next() methods,
  concentrating instead on the pure search loops.
• The prior point should also make the performance aspect more validateable.
  However, should the existing slice type-specific iterators types like split() be replaced by shared, generic ones there might be some regressions due to optimizations possibly not carrying over. This is optional though.
• We should probably specify the Pattern API more closely as only being intended for iterator-like linear search operations.