pub unsafe trait Haystack: Deref + Sizedwhere
Self::Target: Hay,{
fn empty() -> Self;
unsafe fn split_around(
self,
range: Range<<Self::Target as Hay>::Index>
) -> [Self; 3];
fn restore_range(
&self,
original: Range<<Self::Target as Hay>::Index>,
parent: Range<<Self::Target as Hay>::Index>
) -> Range<<Self::Target as Hay>::Index>;
unsafe fn slice_unchecked(
self,
range: Range<<Self::Target as Hay>::Index>
) -> Self { ... }
}
Expand description
Linear splittable structure.
A Haystack
is implemented for reference and collection types such as
&str
, &mut [T]
and Vec<T>
. Every haystack can be borrowed as an
underlying representation called a Hay
. Multiple haystacks may share the
same hay type, and thus share the same implementation of string search
algorithms.
In the other words, a Haystack
is a generalized reference to Hay
.
Safety
This trait is unsafe as there are some unchecked requirements which the implementor must uphold. Failing to meet these requirements would lead to out-of-bound access. The safety requirements are written in each member of this trait.
Required Methods§
sourceunsafe fn split_around(
self,
range: Range<<Self::Target as Hay>::Index>
) -> [Self; 3]
unsafe fn split_around(
self,
range: Range<<Self::Target as Hay>::Index>
) -> [Self; 3]
Splits the haystack into 3 slices around the given range.
This method splits self
into 3 non-overlapping parts:
- Before the range (
self[..range.start]
), - Inside the range (
self[range]
), and - After the range (
self[range.end..]
)
The returned array contains these 3 parts in order.
Safety
Caller should ensure that the starts and end indices of range
are
valid indices for the haystack self
with range.start <= range.end
.
If the haystack is a mutable reference (&mut A
), implementation must
ensure that the 3 returned haystack are truly non-overlapping in memory.
This is required to uphold the “Aliasing XOR Mutability” guarantee. If a
haystack cannot be physically split into non-overlapping parts (e.g. in
OsStr
), then &mut A
should not implement Haystack
either.
Examples
use pattern_3::Haystack;
let haystack = &mut [0, 1, 2, 3, 4, 5, 6];
let [left, middle, right] = unsafe { haystack.split_around(2..6) };
assert_eq!(left, &mut [0, 1]);
assert_eq!(middle, &mut [2, 3, 4, 5]);
assert_eq!(right, &mut [6]);
sourcefn restore_range(
&self,
original: Range<<Self::Target as Hay>::Index>,
parent: Range<<Self::Target as Hay>::Index>
) -> Range<<Self::Target as Hay>::Index>
fn restore_range(
&self,
original: Range<<Self::Target as Hay>::Index>,
parent: Range<<Self::Target as Hay>::Index>
) -> Range<<Self::Target as Hay>::Index>
Transforms the range from relative to self’s parent to the original haystack it was sliced from.
Typically this method can be simply implemented as
(original.start + parent.start)..(original.start + parent.end)
If this haystack is a SharedHaystack
, this method would never be
called.
Safety
The parent
range should be a valid range relative to a hay a, which
was used to slice out self: self == &a[parent]
.
Similarly, the original
range should be a valid range relative to
another hay b used to slice out a: a == &b[original]
.
The distance of parent
must be consistent with the length of self
.
This method should return a range which satisfies:
self == &b[parent][original] == &b[range]
Slicing can be destructive and invalidates some indices, in particular
for owned type with a pointer-like index, e.g. linked list. In this
case, one should derive an entirely new index range from self
, e.g.
returning self.start_index()..self.end_index()
.
Examples
use pattern_3::Haystack;
let hay = b"This is a sample haystack";
let this = hay[2..23][3..19].to_vec();
assert_eq!(&*this, &hay[this.restore_range(2..23, 3..19)]);