Trait pattern_3::haystack::Haystack

source · 
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§

Creates an empty haystack.

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

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§

Subslices this haystack.

Safety

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

Implementations on Foreign Types§

Implementors§