aho_corasick/packed/teddy/

generic.rs

use core::fmt::Debug;

use alloc::{
    boxed::Box, collections::BTreeMap, format, sync::Arc, vec, vec::Vec,
};

use crate::{
    packed::{
        ext::Pointer,
        pattern::Patterns,
        vector::{FatVector, Vector},
    },
    util::int::U32,
    PatternID,
};

/// A match type specialized to the Teddy implementations below.
///
/// Essentially, instead of representing a match at byte offsets, we use
/// raw pointers. This is because the implementations below operate on raw
/// pointers, and so this is a more natural return type based on how the
/// implementation works.
///
/// Also, the `PatternID` used here is a `u16`.
#[derive(Clone, Copy, Debug)]
pub(crate) struct Match {
    pid: PatternID,
    start: *const u8,
    end: *const u8,
}

impl Match {
    /// Returns the ID of the pattern that matched.
    pub(crate) fn pattern(&self) -> PatternID {
        self.pid
    }

    /// Returns a pointer into the haystack at which the match starts.
    pub(crate) fn start(&self) -> *const u8 {
        self.start
    }

    /// Returns a pointer into the haystack at which the match ends.
    pub(crate) fn end(&self) -> *const u8 {
        self.end
    }
}

/// A "slim" Teddy implementation that is generic over both the vector type
/// and the minimum length of the patterns being searched for.
///
/// Only 1, 2, 3 and 4 bytes are supported as minimum lengths.
#[derive(Clone, Debug)]
pub(crate) struct Slim<V, const BYTES: usize> {
    /// A generic data structure for doing "slim" Teddy verification.
    teddy: Teddy<8>,
    /// The masks used as inputs to the shuffle operation to generate
    /// candidates (which are fed into the verification routines).
    masks: [Mask<V>; BYTES],
}

impl<V: Vector, const BYTES: usize> Slim<V, BYTES> {
    /// Create a new "slim" Teddy searcher for the given patterns.
    ///
    /// # Panics
    ///
    /// This panics when `BYTES` is any value other than 1, 2, 3 or 4.
    ///
    /// # Safety
    ///
    /// Callers must ensure that this is okay to call in the current target for
    /// the current CPU.
    #[inline(always)]
    pub(crate) unsafe fn new(patterns: Arc<Patterns>) -> Slim<V, BYTES> {
        assert!(
            1 <= BYTES && BYTES <= 4,
            "only 1, 2, 3 or 4 bytes are supported"
        );
        let teddy = Teddy::new(patterns);
        let masks = SlimMaskBuilder::from_teddy(&teddy);
        Slim { teddy, masks }
    }

    /// Returns the approximate total amount of heap used by this type, in
    /// units of bytes.
    #[inline(always)]
    pub(crate) fn memory_usage(&self) -> usize {
        self.teddy.memory_usage()
    }

    /// Returns the minimum length, in bytes, that a haystack must be in order
    /// to use it with this searcher.
    #[inline(always)]
    pub(crate) fn minimum_len(&self) -> usize {
        V::BYTES + (BYTES - 1)
    }
}

impl<V: Vector> Slim<V, 1> {
    /// Look for an occurrences of the patterns in this finder in the haystack
    /// given by the `start` and `end` pointers.
    ///
    /// If no match could be found, then `None` is returned.
    ///
    /// # Safety
    ///
    /// The given pointers representing the haystack must be valid to read
    /// from. They must also point to a region of memory that is at least the
    /// minimum length required by this searcher.
    ///
    /// Callers must ensure that this is okay to call in the current target for
    /// the current CPU.
    #[inline(always)]
    pub(crate) unsafe fn find(
        &self,
        start: *const u8,
        end: *const u8,
    ) -> Option<Match> {
        let len = end.distance(start);
        debug_assert!(len >= self.minimum_len());
        let mut cur = start;
        while cur <= end.sub(V::BYTES) {
            if let Some(m) = self.find_one(cur, end) {
                return Some(m);
            }
            cur = cur.add(V::BYTES);
        }
        if cur < end {
            cur = end.sub(V::BYTES);
            if let Some(m) = self.find_one(cur, end) {
                return Some(m);
            }
        }
        None
    }

    /// Look for a match starting at the `V::BYTES` at and after `cur`. If
    /// there isn't one, then `None` is returned.
    ///
    /// # Safety
    ///
    /// The given pointers representing the haystack must be valid to read
    /// from. They must also point to a region of memory that is at least the
    /// minimum length required by this searcher.
    ///
    /// Callers must ensure that this is okay to call in the current target for
    /// the current CPU.
    #[inline(always)]
    unsafe fn find_one(
        &self,
        cur: *const u8,
        end: *const u8,
    ) -> Option<Match> {
        let c = self.candidate(cur);
        if !c.is_zero() {
            if let Some(m) = self.teddy.verify(cur, end, c) {
                return Some(m);
            }
        }
        None
    }

    /// Look for a candidate match (represented as a vector) starting at the
    /// `V::BYTES` at and after `cur`. If there isn't one, then a vector with
    /// all bits set to zero is returned.
    ///
    /// # Safety
    ///
    /// The given pointer representing the haystack must be valid to read
    /// from.
    ///
    /// Callers must ensure that this is okay to call in the current target for
    /// the current CPU.
    #[inline(always)]
    unsafe fn candidate(&self, cur: *const u8) -> V {
        let chunk = V::load_unaligned(cur);
        Mask::members1(chunk, self.masks)
    }
}

impl<V: Vector> Slim<V, 2> {
    /// See Slim<V, 1>::find.
    #[inline(always)]
    pub(crate) unsafe fn find(
        &self,
        start: *const u8,
        end: *const u8,
    ) -> Option<Match> {
        let len = end.distance(start);
        debug_assert!(len >= self.minimum_len());
        let mut cur = start.add(1);
        let mut prev0 = V::splat(0xFF);
        while cur <= end.sub(V::BYTES) {
            if let Some(m) = self.find_one(cur, end, &mut prev0) {
                return Some(m);
            }
            cur = cur.add(V::BYTES);
        }
        if cur < end {
            cur = end.sub(V::BYTES);
            prev0 = V::splat(0xFF);
            if let Some(m) = self.find_one(cur, end, &mut prev0) {
                return Some(m);
            }
        }
        None
    }

    /// See Slim<V, 1>::find_one.
    #[inline(always)]
    unsafe fn find_one(
        &self,
        cur: *const u8,
        end: *const u8,
        prev0: &mut V,
    ) -> Option<Match> {
        let c = self.candidate(cur, prev0);
        if !c.is_zero() {
            if let Some(m) = self.teddy.verify(cur.sub(1), end, c) {
                return Some(m);
            }
        }
        None
    }

    /// See Slim<V, 1>::candidate.
    #[inline(always)]
    unsafe fn candidate(&self, cur: *const u8, prev0: &mut V) -> V {
        let chunk = V::load_unaligned(cur);
        let (res0, res1) = Mask::members2(chunk, self.masks);
        let res0prev0 = res0.shift_in_one_byte(*prev0);
        let res = res0prev0.and(res1);
        *prev0 = res0;
        res
    }
}

impl<V: Vector> Slim<V, 3> {
    /// See Slim<V, 1>::find.
    #[inline(always)]
    pub(crate) unsafe fn find(
        &self,
        start: *const u8,
        end: *const u8,
    ) -> Option<Match> {
        let len = end.distance(start);
        debug_assert!(len >= self.minimum_len());
        let mut cur = start.add(2);
        let mut prev0 = V::splat(0xFF);
        let mut prev1 = V::splat(0xFF);
        while cur <= end.sub(V::BYTES) {
            if let Some(m) = self.find_one(cur, end, &mut prev0, &mut prev1) {
                return Some(m);
            }
            cur = cur.add(V::BYTES);
        }
        if cur < end {
            cur = end.sub(V::BYTES);
            prev0 = V::splat(0xFF);
            prev1 = V::splat(0xFF);
            if let Some(m) = self.find_one(cur, end, &mut prev0, &mut prev1) {
                return Some(m);
            }
        }
        None
    }

    /// See Slim<V, 1>::find_one.
    #[inline(always)]
    unsafe fn find_one(
        &self,
        cur: *const u8,
        end: *const u8,
        prev0: &mut V,
        prev1: &mut V,
    ) -> Option<Match> {
        let c = self.candidate(cur, prev0, prev1);
        if !c.is_zero() {
            if let Some(m) = self.teddy.verify(cur.sub(2), end, c) {
                return Some(m);
            }
        }
        None
    }

    /// See Slim<V, 1>::candidate.
    #[inline(always)]
    unsafe fn candidate(
        &self,
        cur: *const u8,
        prev0: &mut V,
        prev1: &mut V,
    ) -> V {
        let chunk = V::load_unaligned(cur);
        let (res0, res1, res2) = Mask::members3(chunk, self.masks);
        let res0prev0 = res0.shift_in_two_bytes(*prev0);
        let res1prev1 = res1.shift_in_one_byte(*prev1);
        let res = res0prev0.and(res1prev1).and(res2);
        *prev0 = res0;
        *prev1 = res1;
        res
    }
}

impl<V: Vector> Slim<V, 4> {
    /// See Slim<V, 1>::find.
    #[inline(always)]
    pub(crate) unsafe fn find(
        &self,
        start: *const u8,
        end: *const u8,
    ) -> Option<Match> {
        let len = end.distance(start);
        debug_assert!(len >= self.minimum_len());
        let mut cur = start.add(3);
        let mut prev0 = V::splat(0xFF);
        let mut prev1 = V::splat(0xFF);
        let mut prev2 = V::splat(0xFF);
        while cur <= end.sub(V::BYTES) {
            if let Some(m) =
                self.find_one(cur, end, &mut prev0, &mut prev1, &mut prev2)
            {
                return Some(m);
            }
            cur = cur.add(V::BYTES);
        }
        if cur < end {
            cur = end.sub(V::BYTES);
            prev0 = V::splat(0xFF);
            prev1 = V::splat(0xFF);
            prev2 = V::splat(0xFF);
            if let Some(m) =
                self.find_one(cur, end, &mut prev0, &mut prev1, &mut prev2)
            {
                return Some(m);
            }
        }
        None
    }

    /// See Slim<V, 1>::find_one.
    #[inline(always)]
    unsafe fn find_one(
        &self,
        cur: *const u8,
        end: *const u8,
        prev0: &mut V,
        prev1: &mut V,
        prev2: &mut V,
    ) -> Option<Match> {
        let c = self.candidate(cur, prev0, prev1, prev2);
        if !c.is_zero() {
            if let Some(m) = self.teddy.verify(cur.sub(3), end, c) {
                return Some(m);
            }
        }
        None
    }

    /// See Slim<V, 1>::candidate.
    #[inline(always)]
    unsafe fn candidate(
        &self,
        cur: *const u8,
        prev0: &mut V,
        prev1: &mut V,
        prev2: &mut V,
    ) -> V {
        let chunk = V::load_unaligned(cur);
        let (res0, res1, res2, res3) = Mask::members4(chunk, self.masks);
        let res0prev0 = res0.shift_in_three_bytes(*prev0);
        let res1prev1 = res1.shift_in_two_bytes(*prev1);
        let res2prev2 = res2.shift_in_one_byte(*prev2);
        let res = res0prev0.and(res1prev1).and(res2prev2).and(res3);
        *prev0 = res0;
        *prev1 = res1;
        *prev2 = res2;
        res
    }
}

/// A "fat" Teddy implementation that is generic over both the vector type
/// and the minimum length of the patterns being searched for.
///
/// Only 1, 2, 3 and 4 bytes are supported as minimum lengths.
#[derive(Clone, Debug)]
pub(crate) struct Fat<V, const BYTES: usize> {
    /// A generic data structure for doing "fat" Teddy verification.
    teddy: Teddy<16>,
    /// The masks used as inputs to the shuffle operation to generate
    /// candidates (which are fed into the verification routines).
    masks: [Mask<V>; BYTES],
}

impl<V: FatVector, const BYTES: usize> Fat<V, BYTES> {
    /// Create a new "fat" Teddy searcher for the given patterns.
    ///
    /// # Panics
    ///
    /// This panics when `BYTES` is any value other than 1, 2, 3 or 4.
    ///
    /// # Safety
    ///
    /// Callers must ensure that this is okay to call in the current target for
    /// the current CPU.
    #[inline(always)]
    pub(crate) unsafe fn new(patterns: Arc<Patterns>) -> Fat<V, BYTES> {
        assert!(
            1 <= BYTES && BYTES <= 4,
            "only 1, 2, 3 or 4 bytes are supported"
        );
        let teddy = Teddy::new(patterns);
        let masks = FatMaskBuilder::from_teddy(&teddy);
        Fat { teddy, masks }
    }

    /// Returns the approximate total amount of heap used by this type, in
    /// units of bytes.
    #[inline(always)]
    pub(crate) fn memory_usage(&self) -> usize {
        self.teddy.memory_usage()
    }

    /// Returns the minimum length, in bytes, that a haystack must be in order
    /// to use it with this searcher.
    #[inline(always)]
    pub(crate) fn minimum_len(&self) -> usize {
        V::Half::BYTES + (BYTES - 1)
    }
}

impl<V: FatVector> Fat<V, 1> {
    /// Look for an occurrences of the patterns in this finder in the haystack
    /// given by the `start` and `end` pointers.
    ///
    /// If no match could be found, then `None` is returned.
    ///
    /// # Safety
    ///
    /// The given pointers representing the haystack must be valid to read
    /// from. They must also point to a region of memory that is at least the
    /// minimum length required by this searcher.
    ///
    /// Callers must ensure that this is okay to call in the current target for
    /// the current CPU.
    #[inline(always)]
    pub(crate) unsafe fn find(
        &self,
        start: *const u8,
        end: *const u8,
    ) -> Option<Match> {
        let len = end.distance(start);
        debug_assert!(len >= self.minimum_len());
        let mut cur = start;
        while cur <= end.sub(V::Half::BYTES) {
            if let Some(m) = self.find_one(cur, end) {
                return Some(m);
            }
            cur = cur.add(V::Half::BYTES);
        }
        if cur < end {
            cur = end.sub(V::Half::BYTES);
            if let Some(m) = self.find_one(cur, end) {
                return Some(m);
            }
        }
        None
    }

    /// Look for a match starting at the `V::BYTES` at and after `cur`. If
    /// there isn't one, then `None` is returned.
    ///
    /// # Safety
    ///
    /// The given pointers representing the haystack must be valid to read
    /// from. They must also point to a region of memory that is at least the
    /// minimum length required by this searcher.
    ///
    /// Callers must ensure that this is okay to call in the current target for
    /// the current CPU.
    #[inline(always)]
    unsafe fn find_one(
        &self,
        cur: *const u8,
        end: *const u8,
    ) -> Option<Match> {
        let c = self.candidate(cur);
        if !c.is_zero() {
            if let Some(m) = self.teddy.verify(cur, end, c) {
                return Some(m);
            }
        }
        None
    }

    /// Look for a candidate match (represented as a vector) starting at the
    /// `V::BYTES` at and after `cur`. If there isn't one, then a vector with
    /// all bits set to zero is returned.
    ///
    /// # Safety
    ///
    /// The given pointer representing the haystack must be valid to read
    /// from.
    ///
    /// Callers must ensure that this is okay to call in the current target for
    /// the current CPU.
    #[inline(always)]
    unsafe fn candidate(&self, cur: *const u8) -> V {
        let chunk = V::load_half_unaligned(cur);
        Mask::members1(chunk, self.masks)
    }
}

impl<V: FatVector> Fat<V, 2> {
    /// See `Fat<V, 1>::find`.
    #[inline(always)]
    pub(crate) unsafe fn find(
        &self,
        start: *const u8,
        end: *const u8,
    ) -> Option<Match> {
        let len = end.distance(start);
        debug_assert!(len >= self.minimum_len());
        let mut cur = start.add(1);
        let mut prev0 = V::splat(0xFF);
        while cur <= end.sub(V::Half::BYTES) {
            if let Some(m) = self.find_one(cur, end, &mut prev0) {
                return Some(m);
            }
            cur = cur.add(V::Half::BYTES);
        }
        if cur < end {
            cur = end.sub(V::Half::BYTES);
            prev0 = V::splat(0xFF);
            if let Some(m) = self.find_one(cur, end, &mut prev0) {
                return Some(m);
            }
        }
        None
    }

    /// See `Fat<V, 1>::find_one`.
    #[inline(always)]
    unsafe fn find_one(
        &self,
        cur: *const u8,
        end: *const u8,
        prev0: &mut V,
    ) -> Option<Match> {
        let c = self.candidate(cur, prev0);
        if !c.is_zero() {
            if let Some(m) = self.teddy.verify(cur.sub(1), end, c) {
                return Some(m);
            }
        }
        None
    }

    /// See `Fat<V, 1>::candidate`.
    #[inline(always)]
    unsafe fn candidate(&self, cur: *const u8, prev0: &mut V) -> V {
        let chunk = V::load_half_unaligned(cur);
        let (res0, res1) = Mask::members2(chunk, self.masks);
        let res0prev0 = res0.half_shift_in_one_byte(*prev0);
        let res = res0prev0.and(res1);
        *prev0 = res0;
        res
    }
}

impl<V: FatVector> Fat<V, 3> {
    /// See `Fat<V, 1>::find`.
    #[inline(always)]
    pub(crate) unsafe fn find(
        &self,
        start: *const u8,
        end: *const u8,
    ) -> Option<Match> {
        let len = end.distance(start);
        debug_assert!(len >= self.minimum_len());
        let mut cur = start.add(2);
        let mut prev0 = V::splat(0xFF);
        let mut prev1 = V::splat(0xFF);
        while cur <= end.sub(V::Half::BYTES) {
            if let Some(m) = self.find_one(cur, end, &mut prev0, &mut prev1) {
                return Some(m);
            }
            cur = cur.add(V::Half::BYTES);
        }
        if cur < end {
            cur = end.sub(V::Half::BYTES);
            prev0 = V::splat(0xFF);
            prev1 = V::splat(0xFF);
            if let Some(m) = self.find_one(cur, end, &mut prev0, &mut prev1) {
                return Some(m);
            }
        }
        None
    }

    /// See `Fat<V, 1>::find_one`.
    #[inline(always)]
    unsafe fn find_one(
        &self,
        cur: *const u8,
        end: *const u8,
        prev0: &mut V,
        prev1: &mut V,
    ) -> Option<Match> {
        let c = self.candidate(cur, prev0, prev1);
        if !c.is_zero() {
            if let Some(m) = self.teddy.verify(cur.sub(2), end, c) {
                return Some(m);
            }
        }
        None
    }

    /// See `Fat<V, 1>::candidate`.
    #[inline(always)]
    unsafe fn candidate(
        &self,
        cur: *const u8,
        prev0: &mut V,
        prev1: &mut V,
    ) -> V {
        let chunk = V::load_half_unaligned(cur);
        let (res0, res1, res2) = Mask::members3(chunk, self.masks);
        let res0prev0 = res0.half_shift_in_two_bytes(*prev0);
        let res1prev1 = res1.half_shift_in_one_byte(*prev1);
        let res = res0prev0.and(res1prev1).and(res2);
        *prev0 = res0;
        *prev1 = res1;
        res
    }
}

impl<V: FatVector> Fat<V, 4> {
    /// See `Fat<V, 1>::find`.
    #[inline(always)]
    pub(crate) unsafe fn find(
        &self,
        start: *const u8,
        end: *const u8,
    ) -> Option<Match> {
        let len = end.distance(start);
        debug_assert!(len >= self.minimum_len());
        let mut cur = start.add(3);
        let mut prev0 = V::splat(0xFF);
        let mut prev1 = V::splat(0xFF);
        let mut prev2 = V::splat(0xFF);
        while cur <= end.sub(V::Half::BYTES) {
            if let Some(m) =
                self.find_one(cur, end, &mut prev0, &mut prev1, &mut prev2)
            {
                return Some(m);
            }
            cur = cur.add(V::Half::BYTES);
        }
        if cur < end {
            cur = end.sub(V::Half::BYTES);
            prev0 = V::splat(0xFF);
            prev1 = V::splat(0xFF);
            prev2 = V::splat(0xFF);
            if let Some(m) =
                self.find_one(cur, end, &mut prev0, &mut prev1, &mut prev2)
            {
                return Some(m);
            }
        }
        None
    }

    /// See `Fat<V, 1>::find_one`.
    #[inline(always)]
    unsafe fn find_one(
        &self,
        cur: *const u8,
        end: *const u8,
        prev0: &mut V,
        prev1: &mut V,
        prev2: &mut V,
    ) -> Option<Match> {
        let c = self.candidate(cur, prev0, prev1, prev2);
        if !c.is_zero() {
            if let Some(m) = self.teddy.verify(cur.sub(3), end, c) {
                return Some(m);
            }
        }
        None
    }

    /// See `Fat<V, 1>::candidate`.
    #[inline(always)]
    unsafe fn candidate(
        &self,
        cur: *const u8,
        prev0: &mut V,
        prev1: &mut V,
        prev2: &mut V,
    ) -> V {
        let chunk = V::load_half_unaligned(cur);
        let (res0, res1, res2, res3) = Mask::members4(chunk, self.masks);
        let res0prev0 = res0.half_shift_in_three_bytes(*prev0);
        let res1prev1 = res1.half_shift_in_two_bytes(*prev1);
        let res2prev2 = res2.half_shift_in_one_byte(*prev2);
        let res = res0prev0.and(res1prev1).and(res2prev2).and(res3);
        *prev0 = res0;
        *prev1 = res1;
        *prev2 = res2;
        res
    }
}

/// The common elements of all "slim" and "fat" Teddy search implementations.
///
/// Essentially, this contains the patterns and the buckets. Namely, it
/// contains enough to implement the verification step after candidates are
/// identified via the shuffle masks.
///
/// It is generic over the number of buckets used. In general, the number of
/// buckets is either 8 (for "slim" Teddy) or 16 (for "fat" Teddy). The generic
/// parameter isn't really meant to be instantiated for any value other than
/// 8 or 16, although it is technically possible. The main hiccup is that there
/// is some bit-shifting done in the critical part of verification that could
/// be quite expensive if `N` is not a multiple of 2.
#[derive(Clone, Debug)]
struct Teddy<const BUCKETS: usize> {
    /// The patterns we are searching for.
    ///
    /// A pattern string can be found by its `PatternID`.
    patterns: Arc<Patterns>,
    /// The allocation of patterns in buckets. This only contains the IDs of
    /// patterns. In order to do full verification, callers must provide the
    /// actual patterns when using Teddy.
    buckets: [Vec<PatternID>; BUCKETS],
    // N.B. The above representation is very simple, but it definitely results
    // in ping-ponging between different allocations during verification. I've
    // tried experimenting with other representations that flatten the pattern
    // strings into a single allocation, but it doesn't seem to help much.
    // Probably everything is small enough to fit into cache anyway, and so the
    // pointer chasing isn't a big deal?
    //
    // One other avenue I haven't explored is some kind of hashing trick
    // that let's us do another high-confidence check before launching into
    // `memcmp`.
}

impl<const BUCKETS: usize> Teddy<BUCKETS> {
    /// Create a new generic data structure for Teddy verification.
    fn new(patterns: Arc<Patterns>) -> Teddy<BUCKETS> {
        assert_ne!(0, patterns.len(), "Teddy requires at least one pattern");
        assert_ne!(
            0,
            patterns.minimum_len(),
            "Teddy does not support zero-length patterns"
        );
        assert!(
            BUCKETS == 8 || BUCKETS == 16,
            "Teddy only supports 8 or 16 buckets"
        );
        // MSRV(1.63): Use core::array::from_fn below instead of allocating a
        // superfluous outer Vec. Not a big deal (especially given the BTreeMap
        // allocation below), but nice to not do it.
        let buckets =
            <[Vec<PatternID>; BUCKETS]>::try_from(vec![vec![]; BUCKETS])
                .unwrap();
        let mut t = Teddy { patterns, buckets };

        let mut map: BTreeMap<Box<[u8]>, usize> = BTreeMap::new();
        for (id, pattern) in t.patterns.iter() {
            // We try to be slightly clever in how we assign patterns into
            // buckets. Generally speaking, we want patterns with the same
            // prefix to be in the same bucket, since it minimizes the amount
            // of time we spend churning through buckets in the verification
            // step.
            //
            // So we could assign patterns with the same N-prefix (where N is
            // the size of the mask, which is one of {1, 2, 3}) to the same
            // bucket. However, case insensitive searches are fairly common, so
            // we'd for example, ideally want to treat `abc` and `ABC` as if
            // they shared the same prefix. ASCII has the nice property that
            // the lower 4 bits of A and a are the same, so we therefore group
            // patterns with the same low-nybble-N-prefix into the same bucket.
            //
            // MOREOVER, this is actually necessary for correctness! In
            // particular, by grouping patterns with the same prefix into the
            // same bucket, we ensure that we preserve correct leftmost-first
            // and leftmost-longest match semantics. In addition to the fact
            // that `patterns.iter()` iterates in the correct order, this
            // guarantees that all possible ambiguous matches will occur in
            // the same bucket. The verification routine could be adjusted to
            // support correct leftmost match semantics regardless of bucket
            // allocation, but that results in a performance hit. It's much
            // nicer to be able to just stop as soon as a match is found.
            let lonybs = pattern.low_nybbles(t.mask_len());
            if let Some(&bucket) = map.get(&lonybs) {
                t.buckets[bucket].push(id);
            } else {
                // N.B. We assign buckets in reverse because it shouldn't have
                // any influence on performance, but it does make it harder to
                // get leftmost match semantics accidentally correct.
                let bucket = (BUCKETS - 1) - (id.as_usize() % BUCKETS);
                t.buckets[bucket].push(id);
                map.insert(lonybs, bucket);
            }
        }
        t
    }

    /// Verify whether there are any matches starting at or after `cur` in the
    /// haystack. The candidate chunk given should correspond to 8-bit bitsets
    /// for N buckets.
    ///
    /// # Safety
    ///
    /// The given pointers representing the haystack must be valid to read
    /// from.
    #[inline(always)]
    unsafe fn verify64(
        &self,
        cur: *const u8,
        end: *const u8,
        mut candidate_chunk: u64,
    ) -> Option<Match> {
        while candidate_chunk != 0 {
            let bit = candidate_chunk.trailing_zeros().as_usize();
            candidate_chunk &= !(1 << bit);

            let cur = cur.add(bit / BUCKETS);
            let bucket = bit % BUCKETS;
            if let Some(m) = self.verify_bucket(cur, end, bucket) {
                return Some(m);
            }
        }
        None
    }

    /// Verify whether there are any matches starting at `at` in the given
    /// `haystack` corresponding only to patterns in the given bucket.
    ///
    /// # Safety
    ///
    /// The given pointers representing the haystack must be valid to read
    /// from.
    ///
    /// The bucket index must be less than or equal to `self.buckets.len()`.
    #[inline(always)]
    unsafe fn verify_bucket(
        &self,
        cur: *const u8,
        end: *const u8,
        bucket: usize,
    ) -> Option<Match> {
        debug_assert!(bucket < self.buckets.len());
        // SAFETY: The caller must ensure that the bucket index is correct.
        for pid in self.buckets.get_unchecked(bucket).iter().copied() {
            // SAFETY: This is safe because we are guaranteed that every
            // index in a Teddy bucket is a valid index into `pats`, by
            // construction.
            debug_assert!(pid.as_usize() < self.patterns.len());
            let pat = self.patterns.get_unchecked(pid);
            if pat.is_prefix_raw(cur, end) {
                let start = cur;
                let end = start.add(pat.len());
                return Some(Match { pid, start, end });
            }
        }
        None
    }

    /// Returns the total number of masks required by the patterns in this
    /// Teddy searcher.
    ///
    /// Basically, the mask length corresponds to the type of Teddy searcher
    /// to use: a 1-byte, 2-byte, 3-byte or 4-byte searcher. The bigger the
    /// better, typically, since searching for longer substrings usually
    /// decreases the rate of false positives. Therefore, the number of masks
    /// needed is the length of the shortest pattern in this searcher. If the
    /// length of the shortest pattern (in bytes) is bigger than 4, then the
    /// mask length is 4 since there are no Teddy searchers for more than 4
    /// bytes.
    fn mask_len(&self) -> usize {
        core::cmp::min(4, self.patterns.minimum_len())
    }

    /// Returns the approximate total amount of heap used by this type, in
    /// units of bytes.
    fn memory_usage(&self) -> usize {
        // This is an upper bound rather than a precise accounting. No
        // particular reason, other than it's probably very close to actual
        // memory usage in practice.
        self.patterns.len() * core::mem::size_of::<PatternID>()
    }
}

impl Teddy<8> {
    /// Runs the verification routine for "slim" Teddy.
    ///
    /// The candidate given should be a collection of 8-bit bitsets (one bitset
    /// per lane), where the ith bit is set in the jth lane if and only if the
    /// byte occurring at `at + j` in `cur` is in the bucket `i`.
    ///
    /// # Safety
    ///
    /// Callers must ensure that this is okay to call in the current target for
    /// the current CPU.
    ///
    /// The given pointers must be valid to read from.
    #[inline(always)]
    unsafe fn verify<V: Vector>(
        &self,
        mut cur: *const u8,
        end: *const u8,
        candidate: V,
    ) -> Option<Match> {
        debug_assert!(!candidate.is_zero());
        // Convert the candidate into 64-bit chunks, and then verify each of
        // those chunks.
        candidate.for_each_64bit_lane(
            #[inline(always)]
            |_, chunk| {
                let result = self.verify64(cur, end, chunk);
                cur = cur.add(8);
                result
            },
        )
    }
}

impl Teddy<16> {
    /// Runs the verification routine for "fat" Teddy.
    ///
    /// The candidate given should be a collection of 8-bit bitsets (one bitset
    /// per lane), where the ith bit is set in the jth lane if and only if the
    /// byte occurring at `at + (j < 16 ? j : j - 16)` in `cur` is in the
    /// bucket `j < 16 ? i : i + 8`.
    ///
    /// # Safety
    ///
    /// Callers must ensure that this is okay to call in the current target for
    /// the current CPU.
    ///
    /// The given pointers must be valid to read from.
    #[inline(always)]
    unsafe fn verify<V: FatVector>(
        &self,
        mut cur: *const u8,
        end: *const u8,
        candidate: V,
    ) -> Option<Match> {
        // This is a bit tricky, but we basically want to convert our
        // candidate, which looks like this (assuming a 256-bit vector):
        //
        //     a31 a30 ... a17 a16 a15 a14 ... a01 a00
        //
        // where each a(i) is an 8-bit bitset corresponding to the activated
        // buckets, to this
        //
        //     a31 a15 a30 a14 a29 a13 ... a18 a02 a17 a01 a16 a00
        //
        // Namely, for Fat Teddy, the high 128-bits of the candidate correspond
        // to the same bytes in the haystack in the low 128-bits (so we only
        // scan 16 bytes at a time), but are for buckets 8-15 instead of 0-7.
        //
        // The verification routine wants to look at all potentially matching
        // buckets before moving on to the next lane. So for example, both
        // a16 and a00 both correspond to the first byte in our window; a00
        // contains buckets 0-7 and a16 contains buckets 8-15. Specifically,
        // a16 should be checked before a01. So the transformation shown above
        // allows us to use our normal verification procedure with one small
        // change: we treat each bitset as 16 bits instead of 8 bits.
        debug_assert!(!candidate.is_zero());

        // Swap the 128-bit lanes in the candidate vector.
        let swapped = candidate.swap_halves();
        // Interleave the bytes from the low 128-bit lanes, starting with
        // cand first.
        let r1 = candidate.interleave_low_8bit_lanes(swapped);
        // Interleave the bytes from the high 128-bit lanes, starting with
        // cand first.
        let r2 = candidate.interleave_high_8bit_lanes(swapped);
        // Now just take the 2 low 64-bit integers from both r1 and r2. We
        // can drop the high 64-bit integers because they are a mirror image
        // of the low 64-bit integers. All we care about are the low 128-bit
        // lanes of r1 and r2. Combined, they contain all our 16-bit bitsets
        // laid out in the desired order, as described above.
        r1.for_each_low_64bit_lane(
            r2,
            #[inline(always)]
            |_, chunk| {
                let result = self.verify64(cur, end, chunk);
                cur = cur.add(4);
                result
            },
        )
    }
}

/// A vector generic mask for the low and high nybbles in a set of patterns.
/// Each 8-bit lane `j` in a vector corresponds to a bitset where the `i`th bit
/// is set if and only if the nybble `j` is in the bucket `i` at a particular
/// position.
///
/// This is slightly tweaked dependending on whether Slim or Fat Teddy is being
/// used. For Slim Teddy, the bitsets in the lower half are the same as the
/// bitsets in the higher half, so that we can search `V::BYTES` bytes at a
/// time. (Remember, the nybbles in the haystack are used as indices into these
/// masks, and 256-bit shuffles only operate on 128-bit lanes.)
///
/// For Fat Teddy, the bitsets are not repeated, but instead, the high half
/// bits correspond to an addition 8 buckets. So that a bitset `00100010` has
/// buckets 1 and 5 set if it's in the lower half, but has buckets 9 and 13 set
/// if it's in the higher half.
#[derive(Clone, Copy, Debug)]
struct Mask<V> {
    lo: V,
    hi: V,
}

impl<V: Vector> Mask<V> {
    /// Return a candidate for Teddy (fat or slim) that is searching for 1-byte
    /// candidates.
    ///
    /// If a candidate is returned, it will be a collection of 8-bit bitsets
    /// (one bitset per lane), where the ith bit is set in the jth lane if and
    /// only if the byte occurring at the jth lane in `chunk` is in the bucket
    /// `i`. If no candidate is found, then the vector returned will have all
    /// lanes set to zero.
    ///
    /// `chunk` should correspond to a `V::BYTES` window of the haystack (where
    /// the least significant byte corresponds to the start of the window). For
    /// fat Teddy, the haystack window length should be `V::BYTES / 2`, with
    /// the window repeated in each half of the vector.
    ///
    /// `mask1` should correspond to a low/high mask for the first byte of all
    /// patterns that are being searched.
    #[inline(always)]
    unsafe fn members1(chunk: V, masks: [Mask<V>; 1]) -> V {
        let lomask = V::splat(0xF);
        let hlo = chunk.and(lomask);
        let hhi = chunk.shift_8bit_lane_right::<4>().and(lomask);
        let locand = masks[0].lo.shuffle_bytes(hlo);
        let hicand = masks[0].hi.shuffle_bytes(hhi);
        locand.and(hicand)
    }

    /// Return a candidate for Teddy (fat or slim) that is searching for 2-byte
    /// candidates.
    ///
    /// If candidates are returned, each will be a collection of 8-bit bitsets
    /// (one bitset per lane), where the ith bit is set in the jth lane if and
    /// only if the byte occurring at the jth lane in `chunk` is in the bucket
    /// `i`. Each candidate returned corresponds to the first and second bytes
    /// of the patterns being searched. If no candidate is found, then all of
    /// the lanes will be set to zero in at least one of the vectors returned.
    ///
    /// `chunk` should correspond to a `V::BYTES` window of the haystack (where
    /// the least significant byte corresponds to the start of the window). For
    /// fat Teddy, the haystack window length should be `V::BYTES / 2`, with
    /// the window repeated in each half of the vector.
    ///
    /// The masks should correspond to the masks computed for the first and
    /// second bytes of all patterns that are being searched.
    #[inline(always)]
    unsafe fn members2(chunk: V, masks: [Mask<V>; 2]) -> (V, V) {
        let lomask = V::splat(0xF);
        let hlo = chunk.and(lomask);
        let hhi = chunk.shift_8bit_lane_right::<4>().and(lomask);

        let locand1 = masks[0].lo.shuffle_bytes(hlo);
        let hicand1 = masks[0].hi.shuffle_bytes(hhi);
        let cand1 = locand1.and(hicand1);

        let locand2 = masks[1].lo.shuffle_bytes(hlo);
        let hicand2 = masks[1].hi.shuffle_bytes(hhi);
        let cand2 = locand2.and(hicand2);

        (cand1, cand2)
    }

    /// Return a candidate for Teddy (fat or slim) that is searching for 3-byte
    /// candidates.
    ///
    /// If candidates are returned, each will be a collection of 8-bit bitsets
    /// (one bitset per lane), where the ith bit is set in the jth lane if and
    /// only if the byte occurring at the jth lane in `chunk` is in the bucket
    /// `i`. Each candidate returned corresponds to the first, second and third
    /// bytes of the patterns being searched. If no candidate is found, then
    /// all of the lanes will be set to zero in at least one of the vectors
    /// returned.
    ///
    /// `chunk` should correspond to a `V::BYTES` window of the haystack (where
    /// the least significant byte corresponds to the start of the window). For
    /// fat Teddy, the haystack window length should be `V::BYTES / 2`, with
    /// the window repeated in each half of the vector.
    ///
    /// The masks should correspond to the masks computed for the first, second
    /// and third bytes of all patterns that are being searched.
    #[inline(always)]
    unsafe fn members3(chunk: V, masks: [Mask<V>; 3]) -> (V, V, V) {
        let lomask = V::splat(0xF);
        let hlo = chunk.and(lomask);
        let hhi = chunk.shift_8bit_lane_right::<4>().and(lomask);

        let locand1 = masks[0].lo.shuffle_bytes(hlo);
        let hicand1 = masks[0].hi.shuffle_bytes(hhi);
        let cand1 = locand1.and(hicand1);

        let locand2 = masks[1].lo.shuffle_bytes(hlo);
        let hicand2 = masks[1].hi.shuffle_bytes(hhi);
        let cand2 = locand2.and(hicand2);

        let locand3 = masks[2].lo.shuffle_bytes(hlo);
        let hicand3 = masks[2].hi.shuffle_bytes(hhi);
        let cand3 = locand3.and(hicand3);

        (cand1, cand2, cand3)
    }

    /// Return a candidate for Teddy (fat or slim) that is searching for 4-byte
    /// candidates.
    ///
    /// If candidates are returned, each will be a collection of 8-bit bitsets
    /// (one bitset per lane), where the ith bit is set in the jth lane if and
    /// only if the byte occurring at the jth lane in `chunk` is in the bucket
    /// `i`. Each candidate returned corresponds to the first, second, third
    /// and fourth bytes of the patterns being searched. If no candidate is
    /// found, then all of the lanes will be set to zero in at least one of the
    /// vectors returned.
    ///
    /// `chunk` should correspond to a `V::BYTES` window of the haystack (where
    /// the least significant byte corresponds to the start of the window). For
    /// fat Teddy, the haystack window length should be `V::BYTES / 2`, with
    /// the window repeated in each half of the vector.
    ///
    /// The masks should correspond to the masks computed for the first,
    /// second, third and fourth bytes of all patterns that are being searched.
    #[inline(always)]
    unsafe fn members4(chunk: V, masks: [Mask<V>; 4]) -> (V, V, V, V) {
        let lomask = V::splat(0xF);
        let hlo = chunk.and(lomask);
        let hhi = chunk.shift_8bit_lane_right::<4>().and(lomask);

        let locand1 = masks[0].lo.shuffle_bytes(hlo);
        let hicand1 = masks[0].hi.shuffle_bytes(hhi);
        let cand1 = locand1.and(hicand1);

        let locand2 = masks[1].lo.shuffle_bytes(hlo);
        let hicand2 = masks[1].hi.shuffle_bytes(hhi);
        let cand2 = locand2.and(hicand2);

        let locand3 = masks[2].lo.shuffle_bytes(hlo);
        let hicand3 = masks[2].hi.shuffle_bytes(hhi);
        let cand3 = locand3.and(hicand3);

        let locand4 = masks[3].lo.shuffle_bytes(hlo);
        let hicand4 = masks[3].hi.shuffle_bytes(hhi);
        let cand4 = locand4.and(hicand4);

        (cand1, cand2, cand3, cand4)
    }
}

/// Represents the low and high nybble masks that will be used during
/// search. Each mask is 32 bytes wide, although only the first 16 bytes are
/// used for 128-bit vectors.
///
/// Each byte in the mask corresponds to a 8-bit bitset, where bit `i` is set
/// if and only if the corresponding nybble is in the ith bucket. The index of
/// the byte (0-15, inclusive) corresponds to the nybble.
///
/// Each mask is used as the target of a shuffle, where the indices for the
/// shuffle are taken from the haystack. AND'ing the shuffles for both the
/// low and high masks together also results in 8-bit bitsets, but where bit
/// `i` is set if and only if the correspond *byte* is in the ith bucket.
#[derive(Clone, Default)]
struct SlimMaskBuilder {
    lo: [u8; 32],
    hi: [u8; 32],
}

impl SlimMaskBuilder {
    /// Update this mask by adding the given byte to the given bucket. The
    /// given bucket must be in the range 0-7.
    ///
    /// # Panics
    ///
    /// When `bucket >= 8`.
    fn add(&mut self, bucket: usize, byte: u8) {
        assert!(bucket < 8);

        let bucket = u8::try_from(bucket).unwrap();
        let byte_lo = usize::from(byte & 0xF);
        let byte_hi = usize::from((byte >> 4) & 0xF);
        // When using 256-bit vectors, we need to set this bucket assignment in
        // the low and high 128-bit portions of the mask. This allows us to
        // process 32 bytes at a time. Namely, AVX2 shuffles operate on each
        // of the 128-bit lanes, rather than the full 256-bit vector at once.
        self.lo[byte_lo] |= 1 << bucket;
        self.lo[byte_lo + 16] |= 1 << bucket;
        self.hi[byte_hi] |= 1 << bucket;
        self.hi[byte_hi + 16] |= 1 << bucket;
    }

    /// Turn this builder into a vector mask.
    ///
    /// # Panics
    ///
    /// When `V` represents a vector bigger than what `MaskBytes` can contain.
    ///
    /// # Safety
    ///
    /// Callers must ensure that this is okay to call in the current target for
    /// the current CPU.
    #[inline(always)]
    unsafe fn build<V: Vector>(&self) -> Mask<V> {
        assert!(V::BYTES <= self.lo.len());
        assert!(V::BYTES <= self.hi.len());
        Mask {
            lo: V::load_unaligned(self.lo[..].as_ptr()),
            hi: V::load_unaligned(self.hi[..].as_ptr()),
        }
    }

    /// A convenience function for building `N` vector masks from a slim
    /// `Teddy` value.
    ///
    /// # Panics
    ///
    /// When `V` represents a vector bigger than what `MaskBytes` can contain.
    ///
    /// # Safety
    ///
    /// Callers must ensure that this is okay to call in the current target for
    /// the current CPU.
    #[inline(always)]
    unsafe fn from_teddy<const BYTES: usize, V: Vector>(
        teddy: &Teddy<8>,
    ) -> [Mask<V>; BYTES] {
        // MSRV(1.63): Use core::array::from_fn to just build the array here
        // instead of creating a vector and turning it into an array.
        let mut mask_builders = vec![SlimMaskBuilder::default(); BYTES];
        for (bucket_index, bucket) in teddy.buckets.iter().enumerate() {
            for pid in bucket.iter().copied() {
                let pat = teddy.patterns.get(pid);
                for (i, builder) in mask_builders.iter_mut().enumerate() {
                    builder.add(bucket_index, pat.bytes()[i]);
                }
            }
        }
        let array =
            <[SlimMaskBuilder; BYTES]>::try_from(mask_builders).unwrap();
        array.map(|builder| builder.build())
    }
}

impl Debug for SlimMaskBuilder {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        let (mut parts_lo, mut parts_hi) = (vec![], vec![]);
        for i in 0..32 {
            parts_lo.push(format!("{:02}: {:08b}", i, self.lo[i]));
            parts_hi.push(format!("{:02}: {:08b}", i, self.hi[i]));
        }
        f.debug_struct("SlimMaskBuilder")
            .field("lo", &parts_lo)
            .field("hi", &parts_hi)
            .finish()
    }
}

/// Represents the low and high nybble masks that will be used during "fat"
/// Teddy search.
///
/// Each mask is 32 bytes wide, and at the time of writing, only 256-bit vectors
/// support fat Teddy.
///
/// A fat Teddy mask is like a slim Teddy mask, except that instead of
/// repeating the bitsets in the high and low 128-bits in 256-bit vectors, the
/// high and low 128-bit halves each represent distinct buckets. (Bringing the
/// total to 16 instead of 8.) This permits spreading the patterns out a bit
/// more and thus putting less pressure on verification to be fast.
///
/// Each byte in the mask corresponds to a 8-bit bitset, where bit `i` is set
/// if and only if the corresponding nybble is in the ith bucket. The index of
/// the byte (0-15, inclusive) corresponds to the nybble.
#[derive(Clone, Copy, Default)]
struct FatMaskBuilder {
    lo: [u8; 32],
    hi: [u8; 32],
}

impl FatMaskBuilder {
    /// Update this mask by adding the given byte to the given bucket. The
    /// given bucket must be in the range 0-15.
    ///
    /// # Panics
    ///
    /// When `bucket >= 16`.
    fn add(&mut self, bucket: usize, byte: u8) {
        assert!(bucket < 16);

        let bucket = u8::try_from(bucket).unwrap();
        let byte_lo = usize::from(byte & 0xF);
        let byte_hi = usize::from((byte >> 4) & 0xF);
        // Unlike slim teddy, fat teddy only works with AVX2. For fat teddy,
        // the high 128 bits of our mask correspond to buckets 8-15, while the
        // low 128 bits correspond to buckets 0-7.
        if bucket < 8 {
            self.lo[byte_lo] |= 1 << bucket;
            self.hi[byte_hi] |= 1 << bucket;
        } else {
            self.lo[byte_lo + 16] |= 1 << (bucket % 8);
            self.hi[byte_hi + 16] |= 1 << (bucket % 8);
        }
    }

    /// Turn this builder into a vector mask.
    ///
    /// # Panics
    ///
    /// When `V` represents a vector bigger than what `MaskBytes` can contain.
    ///
    /// # Safety
    ///
    /// Callers must ensure that this is okay to call in the current target for
    /// the current CPU.
    #[inline(always)]
    unsafe fn build<V: Vector>(&self) -> Mask<V> {
        assert!(V::BYTES <= self.lo.len());
        assert!(V::BYTES <= self.hi.len());
        Mask {
            lo: V::load_unaligned(self.lo[..].as_ptr()),
            hi: V::load_unaligned(self.hi[..].as_ptr()),
        }
    }

    /// A convenience function for building `N` vector masks from a fat
    /// `Teddy` value.
    ///
    /// # Panics
    ///
    /// When `V` represents a vector bigger than what `MaskBytes` can contain.
    ///
    /// # Safety
    ///
    /// Callers must ensure that this is okay to call in the current target for
    /// the current CPU.
    #[inline(always)]
    unsafe fn from_teddy<const BYTES: usize, V: Vector>(
        teddy: &Teddy<16>,
    ) -> [Mask<V>; BYTES] {
        // MSRV(1.63): Use core::array::from_fn to just build the array here
        // instead of creating a vector and turning it into an array.
        let mut mask_builders = vec![FatMaskBuilder::default(); BYTES];
        for (bucket_index, bucket) in teddy.buckets.iter().enumerate() {
            for pid in bucket.iter().copied() {
                let pat = teddy.patterns.get(pid);
                for (i, builder) in mask_builders.iter_mut().enumerate() {
                    builder.add(bucket_index, pat.bytes()[i]);
                }
            }
        }
        let array =
            <[FatMaskBuilder; BYTES]>::try_from(mask_builders).unwrap();
        array.map(|builder| builder.build())
    }
}

impl Debug for FatMaskBuilder {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        let (mut parts_lo, mut parts_hi) = (vec![], vec![]);
        for i in 0..32 {
            parts_lo.push(format!("{:02}: {:08b}", i, self.lo[i]));
            parts_hi.push(format!("{:02}: {:08b}", i, self.hi[i]));
        }
        f.debug_struct("FatMaskBuilder")
            .field("lo", &parts_lo)
            .field("hi", &parts_hi)
            .finish()
    }
}