pub unsafe trait Automaton: private::Sealed {
    /// Returns the starting state for the given anchor mode.
    ///
    /// Upon success, the state ID returned is guaranteed to be valid for
    /// this automaton.
    ///
    /// # Errors
    ///
    /// This returns an error when the given search configuration is not
    /// supported by the underlying automaton. For example, if the underlying
    /// automaton only supports unanchored searches but the given configuration
    /// was set to an anchored search, then this must return an error.
    fn start_state(&self, anchored: Anchored) -> Result<StateID, MatchError>;

    #[inline(always)]
    fn next_state(
        &self,
        _anchored: Anchored,
        sid: StateID,
        byte: u8,
    ) -> StateID {
        let class = self.byte_classes.get(byte);
        self.trans[(sid.as_u32() + u32::from(class)).as_usize()]
    }

unsafe fn is_equal_raw(mut x: *const u8, mut y: *const u8, n: usize) -> bool {
    // If we don't have enough bytes to do 4-byte at a time loads, then
    // handle each possible length specially. Note that I used to have a
    // byte-at-a-time loop here and that turned out to be quite a bit slower
    // for the memmem/pathological/defeat-simple-vector-alphabet benchmark.
    if n < 4 {
        return match n {
            0 => true,
            1 => x.read() == y.read(),
            2 => {
                x.cast::<u16>().read_unaligned()
                    == y.cast::<u16>().read_unaligned()
            }
            // I also tried copy_nonoverlapping here and it looks like the
            // codegen is the same.
            3 => x.cast::<[u8; 3]>().read() == y.cast::<[u8; 3]>().read(),
            _ => unreachable!(),
        };
    }
    // When we have 4 or more bytes to compare, then proceed in chunks of 4 at
    // a time using unaligned loads.
    //
    // Also, why do 4 byte loads instead of, say, 8 byte loads? The reason is
    // that this particular version of memcmp is likely to be called with tiny
    // needles. That means that if we do 8 byte loads, then a higher proportion
    // of memcmp calls will use the slower variant above. With that said, this
    // is a hypothesis and is only loosely supported by benchmarks. There's
    // likely some improvement that could be made here. The main thing here
    // though is to optimize for latency, not throughput.

    // SAFETY: The caller is responsible for ensuring the pointers we get are
    // valid and readable for at least `n` bytes. We also do unaligned loads,
    // so there's no need to ensure we're aligned. (This is justified by this
    // routine being specifically for short strings.)
    let xend = x.add(n.wrapping_sub(4));
    let yend = y.add(n.wrapping_sub(4));
    while x < xend {
        let vx = x.cast::<u32>().read_unaligned();
        let vy = y.cast::<u32>().read_unaligned();
        if vx != vy {
            return false;
        }
        x = x.add(4);
        y = y.add(4);
    }
    let vx = xend.cast::<u32>().read_unaligned();
    let vy = yend.cast::<u32>().read_unaligned();
    vx == vy
}

    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

    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
    }