Trait pattern_3::needle::Searcher

source · 
pub unsafe trait Searcher<A: Hay + ?Sized> {
    fn search(&mut self, span: Span<&A>) -> Option<Range<A::Index>>;
}
Expand description

A searcher, for searching a Needle from a Hay.

This trait provides methods for searching for non-overlapping matches of a needle starting from the front (left) of a hay.

Safety

This trait is marked unsafe because the range returned by its methods are required to lie on valid codeword boundaries in the haystack. This enables users of this trait to slice the haystack without additional runtime checks.

Examples

Implement a searcher and consumer which matches b"Aaaa" from a byte string.

extern crate pattern_3;
use pattern_3::*;
use std::ops::Range;

// The searcher for searching `b"Aaaa"`, using naive search.
// We are going to use this as a needle too.
struct Aaaa;

unsafe impl Searcher<[u8]> for Aaaa {
    // search for an `b"Aaaa"` in the middle of the string, returns its range.
    fn search(&mut self, span: Span<&[u8]>) -> Option<Range<usize>> {
        let (hay, range) = span.into_parts();

        let start = range.start;
        for (i, window) in hay[range].windows(4).enumerate() {
            if *window == b"Aaaa"[..] {
                // remember to include the range offset
                return Some((start + i)..(start + i + 4));
            }
        }

        None
    }
}

unsafe impl Consumer<[u8]> for Aaaa {
    // checks if an `b"Aaaa" is at the beginning of the string, returns the end index.
    fn consume(&mut self, span: Span<&[u8]>) -> Option<usize> {
        let (hay, range) = span.into_parts();
        let end = range.start.checked_add(4)?;
        if end <= range.end && hay[range.start..end] == b"Aaaa"[..] {
            Some(end)
        } else {
            None
        }
    }
}

impl<H: Haystack<Target = [u8]>> pattern_3::Needle<H> for Aaaa {
    type Searcher = Self;
    type Consumer = Self;
    fn into_searcher(self) -> Self { self }
    fn into_consumer(self) -> Self { self }
}

// test with some standard algorithms.
let haystack = &b"Aaaaa!!!Aaa!!!Aaaaaaaaa!!!"[..];
assert_eq!(
    ext::split(haystack, Aaaa).collect::<Vec<_>>(),
    vec![
        &b""[..],
        &b"a!!!Aaa!!!"[..],
        &b"aaaaa!!!"[..],
    ]
);
assert_eq!(
    ext::match_ranges(haystack, Aaaa).collect::<Vec<_>>(),
    vec![
        (0..4, &b"Aaaa"[..]),
        (14..18, &b"Aaaa"[..]),
    ]
);
assert_eq!(
    ext::trim_start(haystack, Aaaa),
    &b"a!!!Aaa!!!Aaaaaaaaa!!!"[..]
);

Required Methods§

Searches for the first range which the needle can be found in the span.

This method is used to support the following standard algorithms:

The hay and the restricted range for searching can be recovered by calling span.into_parts(). The range returned by this method should be relative to the hay and must be contained within the restricted range from the span.

If the needle is not found, this method should return None.

The reason this method takes a Span<&A> instead of just &A is because some needles need context information provided by the position of the current slice and the content around the slice. Regex components like the start-/end-of-text anchors ^/$ and word boundary \b are primary examples.

Examples

Search for the locations of a substring inside a string, using the searcher primitive.

extern crate pattern_3;
use pattern_3::{Searcher, Needle, Span};

let mut searcher = Needle::<&str>::into_searcher("::");
let span = Span::from("lion::tiger::leopard");
//                     ^   ^      ^        ^
// string indices:     0   4     11       20

// found the first "::".
assert_eq!(searcher.search(span.clone()), Some(4..6));

// slice the span to skip the first match.
let span = unsafe { span.slice_unchecked(6..20) };

// found the second "::".
assert_eq!(searcher.search(span.clone()), Some(11..13));

// should find nothing now.
let span = unsafe { span.slice_unchecked(13..20) };
assert_eq!(searcher.search(span.clone()), None);

Implementors§