impl some basic parsers and combinators

1 files changed, 821 insertions, 0 deletions

diff --git a/src/lib.rs b/src/lib.rs
new file mode 100644
index 0000000..fc91cb1
--- /dev/null
+++ b/src/lib.rs
@@ -0,0 +1,821 @@
+use core::{cmp::PartialEq, fmt, iter::Iterator, marker::Sized, ops::Range};
+
+use crate::{
+    input::{Character, Input, InputIter},
+    mode::{Check, Emit, Mode},
+};
+
+pub mod input;
+pub mod mode;
+
+pub type Span = Range<usize>;
+
+pub type ParserOk<I, O> = (InputIter<I>, O);
+
+pub type ParserResult<I, O, OM = Emit, EM = Emit> =
+    Result<ParserOk<I, <OM as Mode>::Output<O>>, <EM as Mode>::Output<InputIter<I>>>;
+
+pub trait Trace<I: Input> {
+    fn trace(parser: &str, input: InputIter<I>);
+}
+
+pub struct DebugTracer;
+
+impl<I> Trace<I> for DebugTracer
+where
+    I: Input + fmt::Debug,
+{
+    fn trace(parser: &str, input: InputIter<I>) {
+        eprintln!("{}:{:?}", parser, input)
+    }
+}
+
+impl<I> Trace<I> for ()
+where
+    I: Input,
+{
+    fn trace(_: &str, _: InputIter<I>) {}
+}
+
+#[derive(Debug)]
+pub enum ParserFinishedError<I: Input> {
+    Err(InputIter<I>),
+    Unfinished(InputIter<I>),
+}
+
+pub trait Parser<I: Input>: Sized {
+    type Output;
+
+    fn run<OM: Mode, EM: Mode, T: Trace<I>>(
+        &mut self,
+        it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM>;
+
+    fn parse(&mut self, it: InputIter<I>) -> ParserResult<I, Self::Output> {
+        self.run::<Emit, Emit, ()>(it)
+    }
+
+    fn check(&mut self, it: InputIter<I>) -> ParserResult<I, Self::Output, Check, Emit> {
+        self.run::<Check, Emit, ()>(it)
+    }
+
+    fn trace<T: Trace<I>>(&mut self, it: InputIter<I>) -> ParserResult<I, Self::Output> {
+        self.run::<Emit, Emit, T>(it)
+    }
+
+    fn parse_finished(&mut self, it: InputIter<I>) -> Result<Self::Output, ParserFinishedError<I>> {
+        match self.parse(it) {
+            Ok((rest, output)) if rest.is_finished() => Ok(output),
+            Ok((rest, _)) => Err(ParserFinishedError::Unfinished(rest)),
+            Err(rest) => Err(ParserFinishedError::Err(rest)),
+        }
+    }
+
+    fn check_finished(&mut self, it: InputIter<I>) -> Result<(), ParserFinishedError<I>> {
+        match self.parse(it) {
+            Ok((rest, _)) if rest.is_finished() => Ok(()),
+            Ok((rest, _)) => Err(ParserFinishedError::Unfinished(rest)),
+            Err(rest) => Err(ParserFinishedError::Err(rest)),
+        }
+    }
+
+    fn map<F, O>(self, f: F) -> impl Parser<I, Output = O>
+    where
+        F: Fn(Self::Output) -> O,
+    {
+        Map { parser: self, f }
+    }
+
+    fn and<P>(self, right: P) -> impl Parser<I, Output = (Self::Output, P::Output)>
+    where
+        P: Parser<I>,
+    {
+        And { left: self, right }
+    }
+
+    fn or<P, O>(self, right: P) -> impl Parser<I, Output = O>
+    where
+        Self: Parser<I, Output = O>,
+        P: Parser<I, Output = O>,
+    {
+        Or { left: self, right }
+    }
+
+    fn and_not<P>(self, not: P) -> impl Parser<I, Output = Self::Output>
+    where
+        P: Parser<I>,
+    {
+        AndNot { parser: self, not }
+    }
+
+    fn preceded_by<P>(self, preceded: P) -> impl Parser<I, Output = Self::Output>
+    where
+        P: Parser<I>,
+    {
+        PrecededBy {
+            parser: self,
+            preceded,
+        }
+    }
+
+    fn followed_by<P>(self, followed: P) -> impl Parser<I, Output = Self::Output>
+    where
+        P: Parser<I>,
+    {
+        FollowedBy {
+            parser: self,
+            followed,
+        }
+    }
+
+    fn delimited_by<P1, P2>(self, left: P1, right: P2) -> impl Parser<I, Output = Self::Output>
+    where
+        P1: Parser<I>,
+        P2: Parser<I>,
+    {
+        DelimitedBy {
+            parser: self,
+            left,
+            right,
+        }
+    }
+
+    fn recognize(self) -> impl Parser<I, Output = I> {
+        Recognize { parser: self }
+    }
+
+    fn separated_list<P>(self, delimiter: P) -> impl Parser<I, Output = Vec<Self::Output>>
+    where
+        P: Parser<I>,
+    {
+        SeparatedList {
+            parser: self,
+            delimiter,
+        }
+    }
+
+    fn separated_list1<P>(self, delimiter: P) -> impl Parser<I, Output = Vec<Self::Output>>
+    where
+        P: Parser<I>,
+    {
+        SeparatedList1 {
+            parser: self,
+            delimiter,
+        }
+    }
+}
+
+impl<I, O, F> Parser<I> for F
+where
+    I: Input,
+    F: Fn(InputIter<I>) -> Result<ParserOk<I, O>, InputIter<I>>,
+{
+    type Output = O;
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        Tracer::trace("fn", it.clone());
+
+        match self(it) {
+            Ok((rest, output)) => Ok((rest, OM::bind(|| output))),
+            Err(rest) => Err(EM::bind(|| rest)),
+        }
+    }
+}
+
+struct Map<P, F> {
+    parser: P,
+    f: F,
+}
+
+impl<I, P, F, O> Parser<I> for Map<P, F>
+where
+    I: Input,
+    P: Parser<I>,
+    F: Fn(P::Output) -> O,
+{
+    type Output = O;
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        match self.parser.run::<OM, EM, Tracer>(it) {
+            Ok((rest, output)) => Ok((rest, OM::map(output, |o| (self.f)(o)))),
+            Err(rest) => Err(rest),
+        }
+    }
+}
+
+struct And<P1, P2> {
+    left: P1,
+    right: P2,
+}
+
+impl<I, P1, P2> Parser<I> for And<P1, P2>
+where
+    I: Input,
+    P1: Parser<I>,
+    P2: Parser<I>,
+{
+    type Output = (P1::Output, P2::Output);
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        Tracer::trace("and", it.clone());
+
+        let (rest, o1) = match self.left.run::<OM, EM, Tracer>(it) {
+            Ok((rest, output)) => (rest, output),
+            Err(rest) => return Err(rest),
+        };
+
+        let (rest, o2) = match self.right.run::<OM, EM, Tracer>(rest) {
+            Ok((rest, output)) => (rest, output),
+            Err(rest) => return Err(rest),
+        };
+
+        Ok((rest, OM::combine(o1, o2, |o1, o2| (o1, o2))))
+    }
+}
+
+struct AndNot<P1, P2> {
+    parser: P1,
+    not: P2,
+}
+
+impl<I, P1, P2> Parser<I> for AndNot<P1, P2>
+where
+    I: Input,
+    P1: Parser<I>,
+    P2: Parser<I>,
+{
+    type Output = P1::Output;
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        Tracer::trace("andnot", it.clone());
+
+        match self.not.run::<Check, Check, Tracer>(it.clone()) {
+            Ok(_) => return Err(EM::bind(|| it.clone())),
+            _ => (),
+        };
+
+        self.parser.run::<OM, EM, Tracer>(it)
+    }
+}
+
+struct Or<P1, P2> {
+    left: P1,
+    right: P2,
+}
+
+impl<I, P1, P2, O> Parser<I> for Or<P1, P2>
+where
+    I: Input,
+    P1: Parser<I, Output = O>,
+    P2: Parser<I, Output = O>,
+{
+    type Output = O;
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        Tracer::trace("or", it.clone());
+
+        match (
+            self.left.run::<OM, EM, Tracer>(it.clone()),
+            self.right.run::<OM, EM, Tracer>(it.clone()),
+        ) {
+            (Ok((rest, output)), _) => Ok((rest, output)),
+            (_, Ok((rest, output))) => Ok((rest, output)),
+            (_, Err(rest)) => Err(rest),
+        }
+    }
+}
+
+pub struct Take {
+    amt: usize,
+}
+
+impl<I> Parser<I> for Take
+where
+    I: Input,
+{
+    type Output = I;
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        mut it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        Tracer::trace("take", it.clone());
+
+        let start = it.clone();
+
+        for _ in 0..self.amt {
+            match it.next() {
+                Some(_) => continue,
+                None => return Err(EM::bind(|| it)),
+            }
+        }
+
+        Ok((
+            it.clone(),
+            OM::bind(|| it.input.slice(start.position()..it.position())),
+        ))
+    }
+}
+
+pub fn take<I>(amt: usize) -> impl Parser<I, Output = I>
+where
+    I: Input,
+{
+    Take { amt }
+}
+
+pub struct TakeWhile<P> {
+    parser: P,
+}
+
+impl<I, P> Parser<I> for TakeWhile<P>
+where
+    I: Input,
+    P: Parser<I>,
+{
+    type Output = I;
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        mut it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        Tracer::trace("takewhile", it.clone());
+
+        let start = it.clone();
+
+        while let Ok((rest, _)) = self.parser.run::<Check, Check, Tracer>(it.clone()) {
+            it = rest;
+        }
+
+        Ok((
+            it.clone(),
+            OM::bind(|| it.input.slice(start.position()..it.position())),
+        ))
+    }
+}
+
+pub fn take_while<I, P>(parser: P) -> impl Parser<I, Output = I>
+where
+    I: Input,
+    P: Parser<I>,
+{
+    TakeWhile { parser }
+}
+
+pub struct TakeWhile1<P> {
+    parser: P,
+}
+
+impl<I, P> Parser<I> for TakeWhile1<P>
+where
+    I: Input,
+    P: Parser<I>,
+{
+    type Output = I;
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        mut it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        Tracer::trace("takewhile1", it.clone());
+
+        let start = it.clone();
+
+        while let Ok((rest, _)) = self.parser.run::<Check, Check, Tracer>(it.clone()) {
+            it = rest;
+        }
+
+        if it.position() > start.position() {
+            Ok((
+                it.clone(),
+                OM::bind(|| it.input.slice(start.position()..it.position())),
+            ))
+        } else {
+            Err(EM::bind(|| it))
+        }
+    }
+}
+
+pub fn take_while1<I, P>(parser: P) -> impl Parser<I, Output = I>
+where
+    I: Input,
+    P: Parser<I>,
+{
+    TakeWhile1 { parser }
+}
+
+pub struct OneOf<It> {
+    it: It,
+}
+
+impl<I, It> Parser<I> for OneOf<It>
+where
+    I: Input,
+    I::Item: PartialEq<It::Item>,
+    It: Iterator,
+{
+    type Output = I::Item;
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        mut it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        Tracer::trace("oneof", it.clone());
+
+        match it.next() {
+            Some((_, item)) if self.it.any(|i| item == i) => Ok((it, OM::bind(|| item))),
+            _ => Err(EM::bind(|| it)),
+        }
+    }
+}
+
+pub fn one_of<I, It>(it: It) -> impl Parser<I, Output = I::Item>
+where
+    I: Input,
+    I::Item: PartialEq<It::Item>,
+    It: Iterator,
+{
+    OneOf { it }
+}
+
+pub struct If<F> {
+    f: F,
+}
+
+impl<I, F> Parser<I> for If<F>
+where
+    I: Input,
+    F: Fn(&I::Item) -> bool,
+{
+    type Output = I::Item;
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        mut it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        Tracer::trace("if", it.clone());
+
+        match it.next() {
+            Some((_, output)) if (self.f)(&output) => Ok((it, OM::bind(|| output))),
+            _ => Err(EM::bind(|| it)),
+        }
+    }
+}
+
+pub fn r#if<I, F>(f: F) -> impl Parser<I, Output = I::Item>
+where
+    I: Input,
+    F: Fn(&I::Item) -> bool,
+{
+    If { f }
+}
+
+struct PrecededBy<P1, P2> {
+    parser: P1,
+    preceded: P2,
+}
+
+impl<I, P1, P2> Parser<I> for PrecededBy<P1, P2>
+where
+    I: Input,
+    P1: Parser<I>,
+    P2: Parser<I>,
+{
+    type Output = P1::Output;
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        Tracer::trace("preceded by", it.clone());
+
+        let rest = match self.preceded.check(it.clone()) {
+            Ok((rest, _)) => rest,
+            Err(_) => return Err(EM::bind(|| it)),
+        };
+
+        self.parser.run::<OM, EM, Tracer>(rest)
+    }
+}
+
+pub struct FollowedBy<P1, P2> {
+    parser: P1,
+    followed: P2,
+}
+
+impl<I, P1, P2> Parser<I> for FollowedBy<P1, P2>
+where
+    I: Input,
+    P1: Parser<I>,
+    P2: Parser<I>,
+{
+    type Output = P1::Output;
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        Tracer::trace("followed by", it.clone());
+
+        let (rest, output) = match self.parser.run::<OM, EM, Tracer>(it) {
+            Ok((rest, output)) => (rest, output),
+            Err(rest) => return Err(rest),
+        };
+
+        let Ok((rest, _)) = self.followed.check(rest.clone()) else {
+            return Err(EM::bind(|| rest.clone()));
+        };
+
+        Ok((rest, output))
+    }
+}
+
+struct DelimitedBy<P1, P2, P3> {
+    parser: P1,
+    left: P2,
+    right: P3,
+}
+
+impl<I, P1, P2, P3> Parser<I> for DelimitedBy<P1, P2, P3>
+where
+    I: Input,
+    P1: Parser<I>,
+    P2: Parser<I>,
+    P3: Parser<I>,
+{
+    type Output = P1::Output;
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        Tracer::trace("delimited by", it.clone());
+
+        let rest = match self.left.check(it.clone()) {
+            Ok((rest, _)) => rest,
+            Err(_) => return Err(EM::bind(|| it)),
+        };
+
+        let (rest, output) = match self.parser.run::<OM, EM, Tracer>(rest.clone()) {
+            Ok((rest, output)) => (rest, output),
+            Err(rest) => return Err(rest),
+        };
+
+        let Ok((rest, _)) = self.right.check(rest.clone()) else {
+            return Err(EM::bind(|| rest));
+        };
+
+        Ok((rest, output))
+    }
+}
+
+struct Recognize<P> {
+    parser: P,
+}
+
+impl<I, P> Parser<I> for Recognize<P>
+where
+    I: Input,
+    P: Parser<I>,
+{
+    type Output = I;
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        Tracer::trace("recognize", it.clone());
+
+        let start = it.clone();
+
+        let rest = match self.parser.check(it.clone()) {
+            Ok((rest, _)) => rest,
+            Err(_) => return Err(EM::bind(|| it)),
+        };
+
+        Ok((
+            rest.clone(),
+            OM::bind(|| it.input.slice(start.position()..rest.position())),
+        ))
+    }
+}
+
+struct Tag<T>(T);
+
+impl<I, T> Parser<I> for Tag<T>
+where
+    I: Input + PartialEq<T>,
+    T: Input,
+{
+    type Output = I;
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        Tracer::trace("tag", it.clone());
+
+        match take(self.0.len()).parse(it.clone()) {
+            Ok((rest, output)) if output == self.0 => Ok((rest, OM::bind(|| output))),
+            Ok(_) => return Err(EM::bind(|| it)),
+            Err(rest) => return Err(EM::bind(|| rest)),
+        }
+    }
+}
+
+pub fn tag<I, T>(tag: T) -> impl Parser<I, Output = I>
+where
+    I: Input + PartialEq<T>,
+    T: Input,
+{
+    Tag(tag)
+}
+
+struct SeparatedList<P1, P2> {
+    parser: P1,
+    delimiter: P2,
+}
+
+impl<I, P1, P2> Parser<I> for SeparatedList<P1, P2>
+where
+    I: Input,
+    P1: Parser<I>,
+    P2: Parser<I>,
+{
+    type Output = Vec<P1::Output>;
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        mut it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        Tracer::trace("separated list", it.clone());
+
+        let mut outputs = OM::bind(|| Vec::new());
+
+        loop {
+            it = match self.parser.run::<OM, EM, Tracer>(it.clone()) {
+                Ok((rest, output)) => {
+                    outputs = OM::combine(outputs, output, |mut acc, e| {
+                        acc.push(e);
+                        acc
+                    });
+                    rest
+                }
+                _ => break,
+            };
+
+            it = match self.delimiter.check(it.clone()) {
+                Ok((rest, _)) => rest,
+                _ => break,
+            };
+        }
+
+        Ok((it, outputs))
+    }
+}
+
+pub struct SeparatedList1<P1, P2> {
+    parser: P1,
+    delimiter: P2,
+}
+
+impl<I, P1, P2> Parser<I> for SeparatedList1<P1, P2>
+where
+    I: Input,
+    P1: Parser<I>,
+    P2: Parser<I>,
+{
+    type Output = Vec<P1::Output>;
+
+    fn run<OM: Mode, EM: Mode, Tracer: Trace<I>>(
+        &mut self,
+        mut it: InputIter<I>,
+    ) -> ParserResult<I, Self::Output, OM, EM> {
+        Tracer::trace("separated list 1", it.clone());
+
+        it = match self.delimiter.check(it.clone()) {
+            Ok((rest, _)) => rest,
+            Err(_) => it,
+        };
+
+        let mut outputs = OM::bind(|| Vec::new());
+        let mut len = 0;
+
+        loop {
+            it = match self.parser.run::<OM, EM, Tracer>(it.clone()) {
+                Ok((rest, output)) => {
+                    outputs = OM::combine(outputs, output, |mut acc, e| {
+                        acc.push(e);
+                        acc
+                    });
+                    len += 1;
+                    rest
+                }
+                _ => break,
+            };
+
+            it = match self.delimiter.check(it.clone()) {
+                Ok((rest, _)) => rest,
+                _ if len > 0 => break,
+                _ => return Err(EM::bind(|| it)),
+            };
+        }
+
+        Ok((it, outputs))
+    }
+}
+
+pub fn alpha<I>() -> impl Parser<I, Output = I>
+where
+    I: Input,
+    I::Item: Character,
+{
+    take_while(r#if(|c: &I::Item| c.is_alphabetic()))
+}
+
+pub fn alpha1<I>() -> impl Parser<I, Output = I>
+where
+    I: Input,
+    I::Item: Character,
+{
+    take_while1(r#if(|c: &I::Item| c.is_alphabetic()))
+}
+
+pub fn numeric<I>() -> impl Parser<I, Output = I>
+where
+    I: Input,
+    I::Item: Character,
+{
+    take_while(r#if(|c: &I::Item| c.is_numeric()))
+}
+
+pub fn numeric1<I>() -> impl Parser<I, Output = I>
+where
+    I: Input,
+    I::Item: Character,
+{
+    take_while1(r#if(|c: &I::Item| c.is_numeric()))
+}
+
+pub fn alphanumeric<I>() -> impl Parser<I, Output = I>
+where
+    I: Input,
+    I::Item: Character,
+{
+    take_while(r#if(|c: &I::Item| c.is_alphanumeric()))
+}
+
+pub fn alphanumeric1<I>() -> impl Parser<I, Output = I>
+where
+    I: Input,
+    I::Item: Character,
+{
+    take_while1(r#if(|c: &I::Item| c.is_alphanumeric()))
+}
+
+pub fn whitespace<I>() -> impl Parser<I, Output = I>
+where
+    I: Input,
+    I::Item: Character,
+{
+    take_while(r#if(|c: &I::Item| c.is_whitespace()))
+}
+
+pub fn whitespace1<I>() -> impl Parser<I, Output = I>
+where
+    I: Input,
+    I::Item: Character,
+{
+    take_while1(r#if(|c: &I::Item| c.is_whitespace()))
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+
+    #[test]
+    fn test_separated_list() {
+        let input = "a b c";
+        let it = InputIter::new(input);
+
+        alpha1()
+            .separated_list(whitespace())
+            .check_finished(it)
+            .unwrap();
+    }
+}