Trait Haystack

pub unsafe trait Haystack: Deref + Sized
where
    Self::Target: Hay,
{
    // Required methods
    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>;

    // Provided method
    unsafe fn slice_unchecked(
        self,
        range: Range<<Self::Target as Hay>::Index>,
    ) -> Self { ... }
}

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

fn empty() -> Self

Creates an empty haystack.

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:

1. Before the range (self[..range.start]),
2. Inside the range (self[range]), and
3. 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]);

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)]);

Provided Methods

unsafe fn slice_unchecked( self, range: Range<<Self::Target as Hay>::Index>, ) -> Self

Subslices this haystack.

Safety

The starts and end indices of range must be valid indices for the haystack self with range.start <= range.end.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementations on Foreign Types

impl<'a, A: Hay + ?Sized + 'a> Haystack for &'a A

fn empty() -> Self

unsafe fn split_around(self, range: Range<A::Index>) -> [Self; 3]

unsafe fn slice_unchecked(self, range: Range<A::Index>) -> Self

fn restore_range( &self, _: Range<A::Index>, _: Range<A::Index>, ) -> Range<A::Index>

impl<'h> Haystack for &'h mut str

fn empty() -> &'h mut str

unsafe fn slice_unchecked(self, range: Range<usize>) -> Self

unsafe fn split_around(self, range: Range<usize>) -> [Self; 3]

fn restore_range( &self, range: Range<usize>, subrange: Range<usize>, ) -> Range<usize>

impl<'h, T: 'h> Haystack for &'h mut [T]

fn empty() -> Self

unsafe fn slice_unchecked(self, range: Range<usize>) -> Self

unsafe fn split_around(self, range: Range<usize>) -> [Self; 3]

fn restore_range( &self, range: Range<usize>, subrange: Range<usize>, ) -> Range<usize>

impl<T> Haystack for Vec<T>

fn empty() -> Self

unsafe fn slice_unchecked(self, range: Range<usize>) -> Self

unsafe fn split_around(self, range: Range<usize>) -> [Self; 3]

fn restore_range( &self, range: Range<usize>, subrange: Range<usize>, ) -> Range<usize>

Implementors