bparse 0.29.2

// The Clone & Copy super traits allow patterns to be re-used even when a function returns `impl Pattern`
/// Expresses that the implementing type may be used to match a byte slice.
pub trait Pattern: Clone + Copy {
    /// Evaluates the pattern against a byte slice.
    /// If the pattern matches, the length of matching slice should be returned.
    /// Otherwise, `None` should be returned.
    ///
    /// It is assumed that the pattern begins matching from the start of the slice.
    fn eval(&self, input: &[u8]) -> Option<usize>;

    /// Returns a new pattern that will match if `self` and `other` match in sequence.
    ///
    /// ```
    /// use bparse::Pattern;
    ///
    /// let pattern = "a".then("b");
    /// assert_eq!(pattern.eval(b"abc"), Some(2));
    /// ```
    fn then<P>(self, other: P) -> Sequence<Self, P>
    where
        Self: Sized,
        P: Pattern,
    {
        Sequence {
            pat1: self,
            pat2: other,
        }
    }

    /// Returns a new pattern that will match if either `self` or `other` match.
    ///
    /// ```
    /// use bparse::Pattern;
    ///
    /// let pattern = "a".or("b");
    /// assert_eq!(pattern.eval(b"ba"), Some(1));
    /// ```
    fn or<P>(self, other: P) -> Choice<Self, P>
    where
        Self: Sized,
        P: Pattern,
    {
        Choice {
            pat1: self,
            pat2: other,
        }
    }
}

impl<P> Pattern for &P
where
    P: Pattern,
{
    fn eval(&self, input: &[u8]) -> Option<usize> {
        (*self).eval(input)
    }
}

/// See [`Pattern::or`]
#[derive(Clone, Copy, Debug)]
pub struct Choice<C1, C2> {
    pat1: C1,
    pat2: C2,
}

impl<P1, P2> Pattern for Choice<P1, P2>
where
    P1: Pattern,
    P2: Pattern,
{
    fn eval(&self, input: &[u8]) -> Option<usize> {
        match self.pat1.eval(input) {
            Some(res) => Some(res),
            None => self.pat2.eval(input),
        }
    }
}

/// See [`Pattern::then`]
#[derive(Clone, Copy, Debug)]
pub struct Sequence<P1, P2> {
    pat1: P1,
    pat2: P2,
}

impl<P1, P2> Pattern for Sequence<P1, P2>
where
    P1: Pattern,
    P2: Pattern,
{
    fn eval(&self, input: &[u8]) -> Option<usize> {
        if let Some(a) = self.pat1.eval(input) {
            if let Some(b) = self.pat2.eval(&input[a..]) {
                return Some(a + b);
            }
        }
        None
    }
}

/// Returns a new pattern that always matches the next byte in the input if it exists.
///
/// ```
/// use bparse::{Pattern, byte};
///
/// assert_eq!(byte().eval(&[1, 2, 3]), Some(1));
/// ```
pub fn byte() -> One {
    One
}

/// See [`one`]
#[derive(Debug, Clone, Copy)]
pub struct One;

impl Pattern for One {
    fn eval(&self, input: &[u8]) -> Option<usize> {
        if input.is_empty() {
            return None;
        }

        Some(1)
    }
}

/// Returns a new pattern that matches the next utf-8 codepoint if it exists.
///
/// ```
/// use bparse::{Pattern, codepoint};
///
/// assert_eq!(codepoint().eval("👨‍👩‍👧‍👦a".as_bytes()), Some(4))
/// ```
pub fn codepoint() -> Codepoint {
    Codepoint
}

/// See [`codepoint`]
#[derive(Debug, Clone, Copy)]
pub struct Codepoint;

impl Pattern for Codepoint {
    fn eval(&self, input: &[u8]) -> Option<usize> {
        // A codepoint can be at most 4 bytes long
        let lookahead = std::cmp::min(input.len(), 4);
        let chunk = String::from_utf8_lossy(&input[..lookahead]);
        let size = match chunk.chars().next() {
            Some(c) if c == char::REPLACEMENT_CHARACTER => return None,
            None => return None,
            Some(c) => c.len_utf8(),
        };
        Some(size)
    }
}

/// Returns a new pattern that will match if `slice` is a prefix of the input.
///
/// ```
/// use bparse::{Pattern, prefix};
///
/// let pattern = prefix(&[1]);
/// assert_eq!(pattern.eval(&[1, 2, 3]), Some(1));
/// ```
///
/// As a convenience, the `Pattern` trait is implemented for slices and bytes with the same effect:
///
/// ```
/// use bparse::Pattern;
///
/// assert_eq!((&b"ab"[..]).eval(b"abc"), Some(2));
/// ```
///
/// If you are working with ascii or utf8 byte slices, consider [`utf8`]
pub fn prefix(slice: &[u8]) -> Prefix<'_> {
    Prefix(slice)
}

/// Returns a new pattern that will match the utf8 string slice `s` at the start of the input.
///
/// ```
/// use bparse::{Pattern, utf8};
///
/// let pattern = utf8("he");
/// assert_eq!(pattern.eval(b"hello"), Some(2));
/// ```
///
/// As a convenience, the `Pattern` trait is implemented for string slices with the same effect:
///
/// ```
/// use bparse::Pattern;
///
/// assert_eq!("he".eval(b"hello"), Some(2));
/// ```
pub fn utf8(s: &str) -> Prefix<'_> {
    Prefix(s.as_bytes())
}

impl Pattern for &str {
    fn eval(&self, input: &[u8]) -> Option<usize> {
        utf8(self).eval(input)
    }
}

impl Pattern for &[u8] {
    fn eval(&self, input: &[u8]) -> Option<usize> {
        Prefix(self).eval(input)
    }
}

impl Pattern for u8 {
    fn eval(&self, input: &[u8]) -> Option<usize> {
        Prefix(&[*self]).eval(input)
    }
}

/// See [`prefix`]
#[derive(Debug, Clone, Copy)]
pub struct Prefix<'p>(&'p [u8]);

impl Pattern for Prefix<'_> {
    fn eval(&self, input: &[u8]) -> Option<usize> {
        if !input.starts_with(self.0) {
            return None;
        }

        Some(self.0.len())
    }
}

/// Returns a pattern that will match any byte in `bytes` at the start of the input
///
/// ```
/// use bparse::{Pattern, oneof};
///
/// let pattern = oneof(b"?!.:");
/// assert_eq!(pattern.eval(b"hi"), None);
/// assert_eq!(pattern.eval(b"!!"), Some(1));
/// assert_eq!(pattern.eval(b":"), Some(1));
/// ```
pub fn oneof(bytes: &[u8]) -> ByteLookupTable {
    let mut set: [bool; 256] = [false; 256];

    let mut i = 0;
    while i < bytes.len() {
        set[bytes[i] as usize] = true;
        i += 1;
    }

    ByteLookupTable(set)
}

/// Inverse of [`oneof`].
pub fn noneof(bytes: &[u8]) -> ByteLookupTable {
    let mut set = oneof(bytes).0;
    let mut i = 0;
    while i < set.len() {
        set[i] = !set[i];
        i += 1;
    }

    ByteLookupTable(set)
}

/// Returns a pattern that will match any ascii digit at the start of the input
///
/// ```
/// use bparse::{Pattern, digit};
///
/// assert_eq!(digit().eval(b"a"), None);
/// assert_eq!(digit().eval(b"8"), Some(1));
/// ```
pub fn digit() -> ByteLookupTable {
    oneof(b"0123456789")
}

/// Returns a pattern that will match any ascii letter at the start of the input
///
/// ```
/// use bparse::{Pattern, alpha};
///
/// assert_eq!(alpha().eval(b"1"), None);
/// assert_eq!(alpha().eval(b"a"), Some(1));
/// ```
pub fn alpha() -> ByteLookupTable {
    oneof(b"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
}

/// Returns a pattern that will match any hexadecimal character at the start of the input
///
/// ```
/// use bparse::{Pattern, hex};
///
/// assert_eq!(hex().eval(b"z"), None);
/// assert_eq!(hex().eval(b"f"), Some(1));
/// ```
pub fn hex() -> Choice<ByteLookupTable, ByteLookupTable> {
    oneof(b"abcdefABCDEF").or(digit())
}

/// See [`oneof`]
#[derive(Debug, Clone, Copy)]
pub struct ByteLookupTable([bool; 256]);

impl Pattern for ByteLookupTable {
    fn eval<'i>(&self, input: &[u8]) -> Option<usize> {
        let first = *input.first()?;

        if self.0[first as usize] {
            return Some(1);
        }
        None
    }
}
/// Returns a new pattern that will match an element in the closed interval `[lo, hi]`
///
/// ```
/// use bparse::{Pattern, range};
///
/// let pattern = range(b'a', b'z');
/// assert_eq!(pattern.eval(b"b"), Some(1));
/// ```
pub fn range(lo: u8, hi: u8) -> ElementRange {
    ElementRange(lo, hi)
}

/// See [`range()`]
#[derive(Debug, Clone, Copy)]
pub struct ElementRange(u8, u8);

impl Pattern for ElementRange {
    fn eval(&self, input: &[u8]) -> Option<usize> {
        let first = input.first()?;

        if first >= &self.0 && first <= &self.1 {
            return Some(1);
        }

        None
    }
}

/// Returns a new pattern that matches as many repetitions as possible of the given `pattern`, including 0.
///
/// ```
/// use bparse::{Pattern, any};
///
/// assert_eq!(any("a").eval(b"aaa"), Some(3));
/// assert_eq!(any("a").eval(b"aa"), Some(2));
/// assert_eq!(any("a").eval(b""), Some(0));
/// ```
pub fn any<P>(pattern: P) -> Repetition<P>
where
    P: Pattern,
{
    Repetition {
        lo: 0,
        hi: None,
        pattern,
    }
}

/// Returns a new pattern that matches at least `n` repetitions of `pattern`.
///
/// ```
/// use bparse::{Pattern, at_least};
///
/// assert_eq!(at_least(2, "a").eval(b"a"), None);
/// assert_eq!(at_least(2, "a").eval(b"aaa"), Some(3));
/// ```
pub fn at_least<P>(n: usize, pattern: P) -> Repetition<P>
where
    P: Pattern,
{
    Repetition {
        lo: n,
        hi: None,
        pattern,
    }
}

/// Returns a new pattern that matches at most `n` repetitions of `pattern`.
///
/// ```
/// use bparse::{Pattern, at_most};
///
/// assert_eq!(at_most(2, "b").eval(b"b"), Some(1));
/// assert_eq!(at_most(2, "b").eval(b"bbbb"), Some(2));
/// assert_eq!(at_most(2, "b").eval(b"aa"), Some(0));
/// ```
pub fn at_most<P>(n: usize, pattern: P) -> Repetition<P>
where
    P: Pattern,
{
    Repetition {
        lo: 0,
        hi: Some(n),
        pattern,
    }
}

/// Returns a new pattern that matches 0 or 1 repetitions of `pattern`
///
/// This implies the new pattern always matches the input.
///
/// ```
/// use bparse::{Pattern, optional};
///
/// assert_eq!(optional("a").eval(b"b"), Some(0));
/// assert_eq!(optional("a").eval(b"a"), Some(1));
/// ```
pub fn optional<P>(pattern: P) -> Repetition<P>
where
    P: Pattern,
{
    Repetition {
        lo: 0,
        hi: Some(1),
        pattern,
    }
}

/// Returns a new pattern that matches exactly `n` repetitions of `pattern`.
///
/// ```
/// use bparse::{Pattern, count};
///
/// assert_eq!(count(2, "z").eval(b"zzz"), Some(2));
/// assert_eq!(count(2, "z").eval(b"z"), None);
/// ```
pub fn count<P>(n: usize, pattern: P) -> Repetition<P>
where
    P: Pattern,
{
    Repetition {
        lo: n,
        hi: Some(n),
        pattern,
    }
}

/// Returns a new pattern that matches between `lo` and `hi` repetitions of `pattern`.
///
/// Both bounds are inclusive.
pub fn between<P>(lo: usize, hi: usize, pattern: P) -> Repetition<P>
where
    P: Pattern,
{
    Repetition {
        lo,
        hi: Some(hi),
        pattern,
    }
}

/// Exppresses pattern repetition.
///
/// Many patterns (e.g. [`between`], [`optional`], [`at_least`]) are expressed in terms of this pattern.
#[derive(Debug, Clone, Copy)]
pub struct Repetition<P> {
    pattern: P,
    lo: usize,
    hi: Option<usize>,
}

impl<P> Pattern for Repetition<P>
where
    P: Pattern,
{
    fn eval<'i>(&self, input: &[u8]) -> Option<usize> {
        let mut match_count = 0;
        let mut offset = 0;

        if let Some(upper_bound) = self.hi {
            assert!(
                upper_bound >= self.lo,
                "upper bound should be greater than or equal to the lower bound"
            );
        };

        loop {
            // We hit the upper bound of pattern repetition
            if let Some(upper_bound) = self.hi {
                if match_count == upper_bound {
                    return Some(offset);
                }
            };

            let Some(value) = self.pattern.eval(&input[offset..]) else {
                if match_count < self.lo {
                    return None;
                }
                return Some(offset);
            };

            match_count += 1;
            offset += value;
        }
    }
}

/// Returns a new pattern that matches only if `pattern` does not match.
///
/// This pattern returns `Some(0)` if the underlying pattern did not match which makes it function as a negative lookahead.
pub fn not<P>(pattern: P) -> Not<P>
where
    P: Pattern,
{
    Not(pattern)
}

/// See [`not`]
#[derive(Debug, Clone, Copy)]
pub struct Not<P>(P);

impl<P> Pattern for Not<P>
where
    P: Pattern,
{
    fn eval<'i>(&self, input: &[u8]) -> Option<usize> {
        if self.0.eval(input).is_some() {
            return None;
        }

        Some(0)
    }
}

/// Returns a pattern that matches the end of the slice.
pub fn end() -> Eof {
    Eof
}

/// See [`end`]
#[derive(Debug, Clone, Copy)]
pub struct Eof;

impl Pattern for Eof {
    fn eval(&self, input: &[u8]) -> Option<usize> {
        input.is_empty().then_some(0)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn match_prefix() {
        // Pattern is empty, input is empty:
        assert_eq!("".eval(b""), Some(0));
        // Pattern is empty, input is not empty:
        assert_eq!("".eval(b"aa"), Some(0));
        // Pattern is not empty, input is empty:
        assert_eq!("aa".eval(b""), None);
        // Pattern is not empty, input length is less than pattern length:
        assert_eq!("aa".eval(b"a"), None);
        assert_eq!("aa".eval(b"b"), None);
        // Pattern is not empty, input length is equal to pattern length:
        assert_eq!("aa".eval(b"aa"), Some(2));
        assert_eq!("aa".eval(b"bb"), None);
        // Pattern is not empty, input length is greater than pattern length:
        assert_eq!("aa".eval(b"aaa"), Some(2));
        assert_eq!("aa".eval(b"bbb"), None);
    }

    #[test]
    fn match_codepoint() {
        assert_eq!(codepoint().eval(b"a"), Some(1));
        assert_eq!(codepoint().eval("👻".as_bytes()), Some(4));
        assert_eq!(codepoint().eval(b"\xff"), None);
    }

    #[test]
    fn match_range() {
        // Range bounds are the same, input is empty:
        assert_eq!(range(b'5', b'5').eval(b""), None);
        // Range bounds are the same, input begins with a byte identical to bounds:
        assert_eq!(range(b'5', b'5').eval(b"5"), Some(1));
        // Range bounds are the same, input begins with outside bounds:
        assert_eq!(range(b'5', b'5').eval(b"4"), None);
        assert_eq!(range(b'5', b'5').eval(b"6"), None);
        // Range bounds are different, input is empty:
        assert_eq!(range(b'3', b'5').eval(b""), None);
        // Range bounds are different, input begins with byte identical to bounds:
        assert_eq!(range(b'3', b'5').eval(b"3"), Some(1));
        assert_eq!(range(b'3', b'5').eval(b"5"), Some(1));
        // Range bounds are different, input begins with byte within bounds:
        assert_eq!(range(b'3', b'5').eval(b"4"), Some(1));
        // Range bounds are different, input begins with byte outside bounds:
        assert_eq!(range(b'3', b'5').eval(b"2"), None);
        assert_eq!(range(b'3', b'5').eval(b"6"), None);
    }

    #[test]
    fn match_oneof_noneof() {
        // Set is empty, input is empty:
        assert_eq!(oneof(b"").eval(b""), None);
        assert_eq!(noneof(b"").eval(b""), None);

        // Set is empty, input is not empty:
        assert_eq!(oneof(b"").eval(b"a"), None);
        assert_eq!(noneof(b"").eval(b"a"), Some(1));

        // Set is not empty, input is empty:
        assert_eq!(oneof(b"ab").eval(b""), None);
        assert_eq!(noneof(b"ab").eval(b""), None);

        // Set is not empty, input begins with byte in set
        assert_eq!(oneof(b"ab").eval(b"a"), Some(1));
        assert_eq!(oneof(b"ab").eval(b"b"), Some(1));

        assert_eq!(noneof(b"ab").eval(b"a"), None);
        assert_eq!(noneof(b"ab").eval(b"b"), None);

        // Set is not empty, input begins with byte not in set
        assert_eq!(oneof(b"ab").eval(b"c"), None);
        assert_eq!(noneof(b"ab").eval(b"c"), Some(1));
    }

    #[test]
    fn match_choice() {
        // left matches, right matches:
        assert_eq!("a".or("aa").eval(b"aa"), Some(1));
        assert_eq!("aa".or("a").eval(b"aa"), Some(2));
        // left matches, right does not match:
        assert_eq!("a".or("b").eval(b"a"), Some(1));

        // left does not match, right matches:
        assert_eq!("b".or("a").eval(b"a"), Some(1));
        // left does not match, right does not match:
        assert_eq!("b".or("a").eval(b"c"), None);
    }

    #[test]
    fn match_sequence() {
        // left matches, right matches:
        assert_eq!("a".then("b").eval(b"ab"), Some(2));
        // left matches, right does not match:
        assert_eq!("a".then("c").eval(b"ab"), None);

        // left does not match, right matches:
        assert_eq!("a".then("").eval(b"b"), None);
        // left does not match, right does not match:
        assert_eq!("a".then("c").eval(b"b"), None);
    }

    #[test]
    fn patterns_are_reusable() {
        let pattern = "a".then("b".or("c"));
        assert_eq!(pattern.eval(b"ac"), Some(2));
        assert_eq!(pattern.eval(b"ab"), Some(2));
    }

    #[test]
    fn repetition_patterns() {
        // repeats exactly 0 times
        assert_eq!(count(0, "a").eval(b""), Some(0));
        assert_eq!(count(0, "a").eval(b"a"), Some(0));
        assert_eq!(count(0, "a").eval(b"aa"), Some(0));

        // repeats exactly n times
        assert_eq!(count(3, "a").eval(b""), None);
        assert_eq!(count(3, "a").eval(b"aa"), None);
        assert_eq!(count(3, "a").eval(b"aaa"), Some(3));
        assert_eq!(count(3, "a").eval(b"aaaa"), Some(3));

        // repeats any number of times
        assert_eq!(any("a").eval(b""), Some(0));
        assert_eq!(any("a").eval(b"b"), Some(0));
        assert_eq!(any("a").eval(b"aa"), Some(2));
        assert_eq!(any("a").eval(b"aab"), Some(2));

        // repeats at least 0 times
        assert_eq!(at_least(0, "a").eval(b""), Some(0));
        assert_eq!(at_least(0, "a").eval(b"a"), Some(1));
        assert_eq!(at_least(0, "a").eval(b"aaaa"), Some(4));

        // repeats at least n times
        assert_eq!(at_least(3, "a").eval(b""), None);
        assert_eq!(at_least(3, "a").eval(b"aa"), None);
        assert_eq!(at_least(3, "a").eval(b"aaa"), Some(3));
        assert_eq!(at_least(3, "a").eval(b"aaaaa"), Some(5));

        // repeats at most 0 times
        assert_eq!(at_most(0, "a").eval(b""), Some(0));
        assert_eq!(at_most(0, "a").eval(b"a"), Some(0));
        assert_eq!(at_most(0, "a").eval(b"aa"), Some(0));

        // repeats at most n times
        assert_eq!(at_most(3, "a").eval(b""), Some(0));
        assert_eq!(at_most(3, "a").eval(b"b"), Some(0));
        assert_eq!(at_most(3, "a").eval(b"aa"), Some(2));
        assert_eq!(at_most(3, "a").eval(b"aaa"), Some(3));
        assert_eq!(at_most(3, "a").eval(b"aaaaa"), Some(3));

        // repeats between n & m times
        assert_eq!(between(2, 4, "a").eval(b""), None);
        assert_eq!(between(2, 4, "a").eval(b"a"), None);
        assert_eq!(between(2, 4, "a").eval(b"aa"), Some(2));
        assert_eq!(between(2, 4, "a").eval(b"aaa"), Some(3));
        assert_eq!(between(2, 4, "a").eval(b"aaaa"), Some(4));
        assert_eq!(between(2, 4, "a").eval(b"aaaaa"), Some(4));
    }
}