parser_combinator.rs

trait Source<'a> {
    fn get(&mut self) -> Option<u8>;
    fn mark(&self) -> &'a [u8];
    fn restore(&mut self, &'a [u8]);
}

struct Slice<'a>(&'a [u8]);

impl<'a> Source<'a> for Slice<'a> {
    fn get(&mut self) -> Option<u8> {
        if self.0.is_empty() {
            None
        } else {
            let r = self.0[0];

            self.0 = &self.0[1..];

            Some(r)
        }
    }
    
    fn mark(&self) -> &'a [u8] {
        self.0
    }
    
    fn restore(&mut self, m: &'a [u8]) {
        self.0 = m
    }
}

trait Parser {
    type Result;
    
    fn parse(&self, &mut Source) -> Option<Self::Result>;
}

/// Parser which succeeds on any input returning that input.
struct Any;

impl Parser for Any {
    type Result = u8;
    
    fn parse(&self, i: &mut Source) -> Option<Self::Result> {
        i.get()
    }
}

/// Parser which succeeds on a specific character, returning that character.
struct Char(u8);

impl Parser for Char {
    type Result = u8;
    
    fn parse(&self, i: &mut Source) -> Option<Self::Result> {
        i.get().and_then(|c| if c == self.0 { Some(c) } else { None })
    }
}

/// Parser which succeeds on a range of characters (inclusive), returning the matched character.
struct Range(u8, u8);

impl Parser for Range {
    type Result = u8;
    
    fn parse(&self, i: &mut Source) -> Option<Self::Result> {
        i.get().and_then(|c| if self.0 <= c && c <= self.1 { Some(c) } else { None })
    }
}

/// Parser which succeeds if the character is present in a supplied list, returning the matched character.
struct OneOf<'a>(&'a [u8]);

impl<'a> Parser for OneOf<'a> {
    type Result = u8;
    
    fn parse(&self, i: &mut Source) -> Option<Self::Result> {
        i.get().and_then(|c| if let Some(_) = self.0.iter().position(|&p| p == c) { Some(c) } else { None })
    }
}

/// Parser which fails if the nested parser succeeds, does not consume input,
/// returning ``R`` upon success.
struct Not<P, R>(P, R)
  where P: Parser,
        R: Clone + Sized;

impl<P, R> Parser for Not<P, R>
  where P: Parser, R: Clone + Sized {
    type Result = R;

    fn parse(&self, i: &mut Source) -> Option<Self::Result> {
        let m = i.mark();
        
        match self.0.parse(i) {
            Some(_) => {
                i.restore(m);

                None
            },
            None    => {
                i.restore(m);

                Some(self.1.clone())
            }
        }
    }
}

/// Parser which returns the result of the nested parser on success otherwise ``R``.
struct Maybe<P, R>(P, R)
  where P: Parser<Result=R>,
        R: Clone + Sized;

impl<P, R> Parser for Maybe<P, R>
  where P: Parser<Result=R>,
        R: Sized + Clone {
    type Result = R;

    fn parse(&self, i: &mut Source) -> Option<Self::Result> {
        let m = i.mark();
        
        match self.0.parse(i) {
            Some(r) => Some(r),
            None    => {
                i.restore(m);
                
                Some(self.1.clone())
            }
        }
    }
}

/// Parser which applies the function ``F`` on the result of the nested parser on success.
struct Apply<P, R, F, U>(P, F)
  where P: Parser<Result=R>,
        F: Fn(R) -> U;

impl<P, R, F, U> Parser for Apply<P, R, F, U>
  where P: Parser<Result=R>,
        F: Fn(R) -> U {
    type Result = U;
    
    fn parse(&self, i: &mut Source) -> Option<Self::Result> {
        self.0.parse(i).map(&self.1)
    }
}

/// Parser which attempts to parse ``P`` zero or more times, using the fold
/// function ``F`` to accumulate data into the accumulator ``A``.
struct Many<P, F, A, R>(P, F, A)
  where P: Parser<Result=R>,
        F: Fn(A, R) -> A,
        A: Clone + Sized;

impl<P, F, A, R> Parser for Many<P, F, A, R>
  where P: Parser<Result=R>,
        F: Fn(A, R) -> A,
        A: Clone + Sized {
    type Result = A;

    fn parse(&self, i: &mut Source) -> Option<Self::Result> {
        let mut r = self.2.clone();
        
        loop {
            let m = i.mark();
        
            match self.0.parse(i) {
                Some(v) => r = self.1(r, v),
                None    => {
                    i.restore(m);
                    
                    break;
                }
            }
        }

        Some(r)
    }
}

/// Parser which attempts to parse ``P`` one or more times, using the fold
/// function ``F`` to accumulate data into the accumulator ``A``.
struct Many1<P, F, A, R>(P, F, A)
  where P: Parser<Result=R>,
        F: Fn(A, R) -> A,
        A: Clone + Sized;

impl<P, F, A, R> Parser for Many1<P, F, A, R>
  where P: Parser<Result=R>,
        F: Fn(A, R) -> A,
        A: Clone + Sized {
    type Result = A;

    fn parse(&self, i: &mut Source) -> Option<Self::Result> {
        let mut n = 0;
        let mut r = self.2.clone();
        
        loop {
            let m = i.mark();
        
            match self.0.parse(i) {
                Some(v) => r = self.1(r, v),
                None    => {
                    i.restore(m);
                    
                    break;
                }
            }
            
            n = n + 1;
        }

        if n > 0 {
            Some(r)
        } else {
            None
        }
    }
}

/// Parser which attempts to parse ``P`` exactly ``usize`` times, using the fold
/// function ``F`` to accumulate data into the accumulator ``A``.
struct Count<P, F, A, R>(usize, P, F, A)
  where P: Parser<Result=R>,
        F: Fn(A, R) -> A,
        A: Clone + Sized;

impl<P, F, A, R> Parser for Count<P, F, A, R>
  where P: Parser<Result=R>,
        F: Fn(A, R) -> A,
        A: Clone + Sized {
    type Result = A;

    fn parse(&self, i: &mut Source) -> Option<Self::Result> {
        let mut n = 0;
        let mut r = self.3.clone();
        
        loop {
            let m = i.mark();
        
            match self.1.parse(i) {
                Some(v) => r = self.2(r, v),
                None    => {
                    i.restore(m);
                    
                    break;
                }
            }
            
            n = n + 1;
        }

        if n == self.0 {
            Some(r)
        } else {
            None
        }
    }
}


/// Attempts to match any of the supplied parsers in order, returning the result of the first matching parser.
struct Or<'a, P, R>(&'a [P])
  where P: Parser<Result=R> + 'a;

impl<'a, P, R> Parser for Or<'a, P, R>
  where P: Parser<Result=R> {
    type Result = R;

    fn parse(&self, i: &mut Source) -> Option<Self::Result> {
        for p in self.0 {
            let m = i.mark();
            
            if let Some(r) = p.parse(i) {
                return Some(r)
            }
            
            i.restore(m);
        }
        
        None
    }
}

fn main() {
    let d = b"123";
    let mut s = Slice(d);
    let a = Count(3, Range(b'0', b'9'), |a, x| a * 10 + (x - b'0'), 0);
    
    println!("{:?}", a.parse(&mut s));
}