bparse/

pattern.rs

pub mod byte;

// 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 slice with elements of type `T`.
pub trait Pattern<T>: Clone + Copy {
    /// Evaluates the pattern against a slice of `T`s.
    /// 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: &[T]) -> 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<T>,
    {
        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<T>,
    {
        Choice {
            pat1: self,
            pat2: other,
        }
    }
}

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

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

impl<P1, P2, T> Pattern<T> for Choice<P1, P2>
where
    P1: Pattern<T>,
    P2: Pattern<T>,
{
    fn eval(&self, input: &[T]) -> 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, T> Pattern<T> for Sequence<P1, P2>
where
    P1: Pattern<T>,
    P2: Pattern<T>,
{
    fn eval(&self, input: &[T]) -> 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 element in the input if it exists.
///
/// ```
/// use bparse::{Pattern, one};
///
/// assert_eq!(one().eval(&[1, 2, 3]), Some(1));
/// ```
pub fn one() -> One {
    One
}

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

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

        Some(1)
    }
}

/// 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));
/// ```
pub fn prefix<T>(slice: &[T]) -> Prefix<T>
where
    T: PartialEq,
    T: Copy,
{
    Prefix(slice)
}

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

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

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

/// 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<T>(lo: T, hi: T) -> ElementRange<T>
where
    T: PartialOrd,
    T: Copy,
{
    ElementRange(lo, hi)
}

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

impl<T> Pattern<T> for ElementRange<T>
where
    T: PartialOrd,
    T: Copy,
{
    fn eval(&self, input: &[T]) -> 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<T, P>(pattern: P) -> Repetition<P>
where
    P: Pattern<T>,
{
    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<T, P>(n: usize, pattern: P) -> Repetition<P>
where
    P: Pattern<T>,
{
    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<T, P>(n: usize, pattern: P) -> Repetition<P>
where
    P: Pattern<T>,
{
    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<T, P>(pattern: P) -> Repetition<P>
where
    P: Pattern<T>,
{
    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<T, P>(n: usize, pattern: P) -> Repetition<P>
where
    P: Pattern<T>,
{
    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<T, P>(lo: usize, hi: usize, pattern: P) -> Repetition<P>
where
    P: Pattern<T>,
{
    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<T, P> Pattern<T> for Repetition<P>
where
    P: Pattern<T>,
{
    fn eval<'i>(&self, input: &[T]) -> 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<T, P>(pattern: P) -> Not<P>
where
    P: Pattern<T>,
{
    Not(pattern)
}

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

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

        Some(0)
    }
}

#[cfg(test)]
mod tests {
    use super::byte::*;
    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("b").eval(b"a"), Some(0));
        assert_eq!(not("a").eval(b"a"), 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));
    }
}