Repository navigation
Description
Problem
The unsafe trait Searcher in library/core/src/str/pattern.rs describes its safety requirement as the returned indices lying on UTF-8 character boundaries.
However, the implementation of str::split additionally assumes that the search results are within the bounds of the haystack, and that the search position never moves backwards and advances in the correct order.
Specifically, SplitInternal::next calls get_unchecked(self.start..a) using the position returned by next_match(). If a moves back before the previous search position, an invalid range may be passed.
Also, the documentation of next_match() and next_reject() only says "See next()", so it is unclear whether a custom implementation of these methods must uphold the same safety conditions as next().
Reproduction and results
I implemented a Searcher that respects UTF-8 character boundaries, but whose next_match() returns (0, 1) twice in a row, and called it from the following safe code using nightly Rust with #![feature(pattern)]:
"abc".split(Rep)Full reproduction
#![feature(pattern)]
use std::str::pattern::{Pattern, SearchStep, Searcher};
// Every index this searcher returns lies on a UTF-8 boundary of the haystack,
// and `next()` yields a valid adjacent, non-overlapping stream.
// Only the overridden `next_match` repeats an earlier match.
struct Rep;
struct RepSearcher<'a> { h: &'a str, pos: usize, calls: usize }
unsafe impl<'a> Searcher<'a> for RepSearcher<'a> {
fn haystack(&self) -> &'a str { self.h }
fn next(&mut self) -> SearchStep {
if self.pos >= self.h.len() { return SearchStep::Done; }
let p = self.pos; self.pos += 1;
SearchStep::Reject(p, p + 1)
}
fn next_match(&mut self) -> Option<(usize, usize)> {
self.calls += 1;
if self.calls <= 2 { Some((0, 1)) } else { None }
}
}
impl Pattern for Rep {
type Searcher<'a> = RepSearcher<'a>;
fn into_searcher(self, h: &str) -> RepSearcher<'_> { RepSearcher { h, pos: 0, calls: 0 } }
}
fn main() {
let parts: Vec<&str> = "abc".split(Rep).collect(); // safe code
println!("{parts:?}");
}Tested with rustc +nightly --edition 2024 -C debug-assertions=on and rustc +nightly --edition 2024 -O.
The results are as follows:
-C debug-assertions=on: an unsafe precondition violation occurs, saying that the range passed tostr::get_uncheckedis not within the string slice.-O:["", "", "bc"]is returned. Internally,get_unchecked(1..0)is executed.
In other words, even when only the documented UTF-8 boundary condition is upheld, a state leading to undefined behavior can be reached from str::split, which is a safe API.
Since Searcher is unstable (feature(pattern)), users on stable Rust are not directly affected.
This is related to the problem of passing an invalid range to get_unchecked, discussed in issue #155312.
Suggested fix
I think it would be good to state in Searcher's safety contract, including for custom implementations of next_match() and next_reject(), that search results are within the bounds of the haystack, that the start position does not exceed the end position, and that the search does not move backwards.
In addition, documenting the preconditions that are actually relied upon in the SAFETY comments of SplitInternal::next, next_back, and next_inclusive in library/core/src/str/iter.rs would make the correspondence with the implementation clearer.
Also, "no guarantee ... will overlap" in the description of next_match() seems, from the context, to be a typo for "will not overlap".
Personally, I think it would be natural to first clarify Searcher's safety contract. However, I would like to hear the maintainers' opinions on whether a documentation fix alone is sufficient, or whether split should also perform some kind of check.
Activity
Rollup merge of rust-lang#165681 - yilin0518:pattern_searcher, r=maxdexh
Rollup merge of rust-lang#165681 - yilin0518:pattern_searcher, r=maxdexh
Rollup merge of rust-lang#165681 - yilin0518:pattern_searcher, r=maxdexh
Unrolled build for #165681 in rollup 165760
Rollup merge of #165681 - yilin0518:pattern_searcher, r=maxdexh
Rollup merge of #165681 - yilin0518:pattern_searcher, r=maxdexh