bparse/

pattern.rs

// 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 part of a slice of bytes.
pub trait Pattern: Clone + Copy {
    /// Evaluates the pattern against a slice of bytes.
    /// If the pattern matches, the length of matching bytes should be returned.
    /// Otherwise, `None` should be returned.
    ///
    /// It is assumed that the pattern begins matching from the beining 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 both `self` and `other` match.
    ///
    /// Unlike [`Pattern::then`], `self` and `other` are evaluated against the same input.
    ///
    /// ```
    /// use bparse::{Pattern, hex, alpha};
    ///
    /// let pattern = hex().and(alpha());
    /// assert_eq!(pattern.eval(b"a"), Some(1));
    /// assert_eq!(pattern.eval(b"3"), None);
    /// ```
    fn and<P>(self, other: P) -> Composition<Self, P>
    where
        Self: Sized,
        P: Pattern,
    {
        Composition {
            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<T> Pattern for &T
where
    T: 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
    }
}

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

impl<P1, P2> Pattern for Composition<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) {
                return Some(std::cmp::max(a, b));
            }
        }
        None
    }
}

/// Returns a pattern that will match any single byte in the input
///
/// ```
/// use bparse::{Pattern, byte};
///
/// assert_eq!(byte().eval(&[1, 2, 3]), Some(1));
/// ```
///
pub fn byte() -> SingleByte {
    SingleByte
}

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

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

        Some(1)
    }
}

/// Returns a pattern that will match `slice` if it occurs at the start of the input.
///
/// ```
/// use bparse::{Pattern, bytes};
///
/// let pattern = bytes(&[1]);
/// assert_eq!(pattern.eval(&[1, 2, 3]), Some(1));
/// ```
pub fn bytes(slice: &[u8]) -> ByteSlice {
    ByteSlice(slice)
}

/// Returns a pattern that will match the 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) -> ByteSlice {
    ByteSlice(s.as_bytes())
}

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

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

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

        for (i, byte) in self.0.iter().enumerate() {
            if &input[i] != byte {
                return None;
            }
        }

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

/// Returns a pattern that will match any byte 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) -> ByteRange {
    ByteRange(lo, hi)
}

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

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

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

        None
    }
}

/// 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() -> LookupTable {
    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() -> LookupTable {
    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<LookupTable, LookupTable> {
    oneof(b"abcdefABCDEF").or(digit())
}

/// 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]) -> LookupTable {
    let mut set: [bool; 256] = [false; 256];

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

    LookupTable(set)
}

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

    LookupTable(set)
}

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

impl Pattern for LookupTable {
    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 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>(pattern: P) -> Repetition<P> {
    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: Pattern>(n: usize, pattern: P) -> Repetition<P> {
    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: Pattern>(n: usize, pattern: P) -> Repetition<P> {
    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>(pattern: P) -> Repetition<P> {
    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: Pattern>(n: usize, pattern: P) -> Repetition<P> {
    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: Pattern>(lo: usize, hi: usize, pattern: P) -> Repetition<P> {
    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 always matches exactly one byte if the underlyuing pattern did not match.
/// That is, it will always return  `Some(1)` if the inner pattern does not match.
pub fn not<P: Pattern>(pattern: P) -> Not<P> {
    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(1)
    }
}

/// Returns a pattern that matches if the input is empty.
///
/// ```
/// use bparse::{Pattern, end};
///
/// assert_eq!(end().eval(b"a"), None);
/// assert_eq!(end().eval(b""), Some(0));
/// ```
pub fn end() -> End {
    End
}

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

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

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

    #[test]
    fn match_bytes() {
        assert_eq!("".eval(b""), Some(0));
        assert_eq!("".eval(b"a1b2"), Some(0));
        assert_eq!("a".eval(b"a1"), Some(1));
        assert_eq!("a1b".eval(b"a1"), None);
        assert_eq!("١".eval(b"\xd9\xa1"), Some(2));
    }

    #[test]
    fn match_range() {
        assert_eq!(range(b'a', b'z').eval(b"d"), Some(1));
        assert_eq!(range(b'a', b'z').eval(b"0"), None);
    }

    #[test]
    fn match_oneof_noneof() {
        assert_eq!(oneof(b"abc").eval(b"a"), Some(1));
        assert_eq!(noneof(b"abc").eval(b"1"), Some(1));
        assert_eq!(oneof(b"abc").eval(b"123"), None);
    }

    #[test]
    fn match_repetition() {
        assert_eq!(between(0, 0, "a").eval(b"aabb"), Some(0));
        assert_eq!(between(1, 1, "a").eval(b"aabb"), Some(1));
        assert_eq!(between(1, 2, "a").eval(b"aabb"), Some(2));
        assert_eq!(between(1, 10, "a").eval(b"aabb"), Some(2));

        assert_eq!(at_least(0, "a").eval(b"aaaab"), Some(4));
        assert_eq!(at_least(4, "a").eval(b"aaaab"), Some(4));
        assert_eq!(at_least(10, "a").eval(b"aaaab"), None);

        assert_eq!(at_most(3, "a").eval(b"bb"), Some(0));
        assert_eq!(at_most(0, "a").eval(b"aaabb"), Some(0));
        assert_eq!(at_most(1, "a").eval(b"aaabb"), Some(1));
        assert_eq!(at_most(10, "a").eval(b"aaabb"), Some(3));

        assert_eq!(optional("a").eval(b"aa"), Some(1));
        assert_eq!(optional("a").eval(b"baa"), Some(0));

        assert_eq!(any("a").eval(b"aaa"), Some(3));
        assert_eq!(any("a").eval(b""), Some(0));
    }

    #[test]
    fn match_negative_lookahead() {
        assert_eq!(not(end()).eval(b"a"), Some(1));
        assert_eq!(not(end()).eval(b""), None);
    }

    #[test]
    fn match_choice() {
        assert_eq!("a".or("b").eval(b"b"), Some(1));
        assert_eq!("a".or("b").eval(b"a"), Some(1));
        assert_eq!("a".or("b").eval(b"c"), None);
    }

    #[test]
    fn match_sequence() {
        assert_eq!("a".then("b").eval(b"ab"), Some(2));
        assert_eq!("a".then("c").eval(b"ab"), None);
        assert_eq!("z".then("b").eval(b"ab"), 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));
    }

    fn mutable_refeence(input: &mut &[u8]) {
        *input = &input[1..]
    }

    #[test]
    fn testmut() {
        let mut input: &[u8] = &[1, 2, 3];
        mutable_refeence(&mut input);
        println!("{:?}", input);
    }
}