Trait Hay

pub unsafe trait Hay {
    type Index: Copy + Debug + Eq;

    // Required methods
    fn empty<'a>() -> &'a Self;
    fn start_index(&self) -> Self::Index;
    fn end_index(&self) -> Self::Index;
    unsafe fn next_index(&self, index: Self::Index) -> Self::Index;
    unsafe fn prev_index(&self, index: Self::Index) -> Self::Index;
    unsafe fn slice_unchecked(&self, range: Range<Self::Index>) -> &Self;
}

Borrowed Haystack.

Every Haystack type can be borrowed as references to Hay types. This allows multiple similar types to share the same implementation (e.g. the haystacks &[T], &mut [T] and Vec<T> all have the same corresponding hay type [T]).

In the other words, a Haystack is a generalized reference to Hay. Hays are typically implemented on unsized slice types like str and [T].

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 Associated Types

type Index: Copy + Debug + Eq

The index type of the haystack. Typically a usize.

Splitting a hay must be sublinear using this index type. For instance, if we implement Hay for a linked list, the index should not be an integer offset (usize) as this would require O(n) time to chase the pointer and find the split point. Instead, for a linked list we should directly use the node pointer as the index.

Safety

Valid indices of a single hay have a total order, even this type does not require an Ord bound — for instance, to order two linked list cursors, we need to chase the links and see if they meet; this is slow and not suitable for implementing Ord, but conceptually an ordering can be defined on linked list cursors.

Required Methods

fn empty<'a>() -> &'a Self

Creates an empty hay.

Safety

An empty hay’s start and end indices must be the same, e.g.

extern crate pattern_3;
use pattern_3::Hay;

let empty = <str>::empty();
assert_eq!(empty.start_index(), empty.end_index());

This also suggests that there is exactly one valid index for an empty hay.

There is no guarantee that two separate calls to .empty() will produce the same hay reference.

fn start_index(&self) -> Self::Index

Obtains the index to the start of the hay.

Usually this method returns 0.

Safety

Implementation must ensure that the start index of hay is the first valid index, i.e. for all valid indices i of self, we have self.start_index() <= i.

fn end_index(&self) -> Self::Index

Obtains the index to the end of the hay.

Usually this method returns the length of the hay.

Safety

Implementation must ensure that the end index of hay is the last valid index, i.e. for all valid indices i of self, we have i <= self.end_index().

unsafe fn next_index(&self, index: Self::Index) -> Self::Index

Returns the next immediate index in this haystack.

Safety

The index must be a valid index, and also must not equal to self.end_index().

Implementation must ensure that if j = self.next_index(i), then j is also a valid index satisfying j > i.

Examples

use pattern_3::Hay;

let sample = "A→😀";
unsafe {
    assert_eq!(sample.next_index(0), 1);
    assert_eq!(sample.next_index(1), 4);
    assert_eq!(sample.next_index(4), 8);
}

unsafe fn prev_index(&self, index: Self::Index) -> Self::Index

Returns the previous immediate index in this haystack.

Safety

The index must be a valid index, and also must not equal to self.start_index().

Implementation must ensure that if j = self.prev_index(i), then j is also a valid index satisfying j < i.

Examples

use pattern_3::Hay;

let sample = "A→😀";
unsafe {
    assert_eq!(sample.prev_index(8), 4);
    assert_eq!(sample.prev_index(4), 1);
    assert_eq!(sample.prev_index(1), 0);
}

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

Obtains a child hay by slicing self.

Safety

The two ends of the range must be valid indices. The start of the range must be before the end of the range (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 Hay for str

type Index = usize

fn empty<'a>() -> &'a Self

fn start_index(&self) -> usize

fn end_index(&self) -> usize

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

unsafe fn next_index(&self, index: Self::Index) -> Self::Index

unsafe fn prev_index(&self, index: Self::Index) -> Self::Index

impl<T> Hay for [T]

type Index = usize

fn empty<'a>() -> &'a Self

fn start_index(&self) -> usize

fn end_index(&self) -> usize

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

unsafe fn next_index(&self, index: Self::Index) -> Self::Index

unsafe fn prev_index(&self, index: Self::Index) -> Self::Index

Implementors

impl Hay for Wtf8

type Index = usize