parser_fold.rs

mod token {
    #[derive(Clone, Copy, Debug, PartialEq)]
    pub enum Token {
        Eof,
        Lit(f64),
        LeftParen,
        RightParen,
        Minus,
        Plus,
        Times,
    }

    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
    pub struct Point {
        pub line: u32,
        pub column: u32,
    }

    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
    pub struct Span {
        start: Point,
        end: Point,
    }

    #[derive(Clone, Copy, Debug, PartialEq)]
    pub struct Context {
        pub token: Token,
        pub span: Span,
    }

    pub trait TokenIter {
        type Span;

        // A token iterator can provide its own internal representation of spans as long as they can be
        // resolved on demand to the external Span type. This allows the internal representation to be
        // very lightweight and efficient, e.g. a u32 cursor pointing to the start of the token.
        fn span(&self, span: Self::Span) -> Span;

        // Advance to the next token, returning the token and its span. At the end of the stream, the token
        // iterator must stop and keep returning Eof. The Eof span must point to the end of the stream.
        fn next(&mut self) -> (Token, Self::Span);
    }

    pub trait IntoTokenIter {
        type TokenIter: TokenIter;

        fn into_token_iter(self) -> Self::TokenIter;
    }

    impl<T: TokenIter> IntoTokenIter for T {
        type TokenIter = Self;

        fn into_token_iter(self) -> Self::TokenIter {
            self
        }
    }
}

mod fold {
    pub use crate::token::Context;

    pub trait Fold {
        type Expr;

        fn expr_lit(&mut self, f: f64) -> Self::Expr;
        fn expr_paren(&mut self, e: Self::Expr) -> Self::Expr;
        fn expr_neg(&mut self, e: Self::Expr) -> Self::Expr;
        fn expr_mul(&mut self, e1: Self::Expr, e2: Self::Expr) -> Self::Expr;
        fn expr_add(&mut self, e1: Self::Expr, e2: Self::Expr) -> Self::Expr;
        fn expr_unexpected_token(&mut self, c: Context) -> Self::Expr;
        fn expr_expected_right_paren(&mut self, e: Self::Expr, c: Context) -> Self::Expr;
    }

    // Parallel composition of folds.
    impl<A: Fold, B: Fold> Fold for (A, B) {
        type Expr = (A::Expr, B::Expr);

        fn expr_lit(&mut self, f: f64) -> Self::Expr {
            (self.0.expr_lit(f), self.1.expr_lit(f))
        }

        fn expr_paren(&mut self, e: Self::Expr) -> Self::Expr {
            (self.0.expr_paren(e.0), self.1.expr_paren(e.1))
        }

        fn expr_neg(&mut self, e: Self::Expr) -> Self::Expr {
            (self.0.expr_neg(e.0), self.1.expr_neg(e.1))
        }

        fn expr_mul(&mut self, e1: Self::Expr, e2: Self::Expr) -> Self::Expr {
            (self.0.expr_mul(e1.0, e2.0), self.1.expr_mul(e1.1, e2.1))
        }

        fn expr_add(&mut self, e1: Self::Expr, e2: Self::Expr) -> Self::Expr {
            (self.0.expr_add(e1.0, e2.0), self.1.expr_add(e1.1, e2.1))
        }

        fn expr_unexpected_token(&mut self, c: Context) -> Self::Expr {
            (self.0.expr_unexpected_token(c), self.1.expr_unexpected_token(c))
        }

        fn expr_expected_right_paren(&mut self, e: Self::Expr, c: Context) -> Self::Expr {
            (self.0.expr_expected_right_paren(e.0, c), self.1.expr_expected_right_paren(e.1, c))
        }
    }
}

mod error {
    pub use crate::token::Context;

    #[derive(Clone, Copy, Debug, PartialEq)]
    pub enum ErrorKind {
        ExprUnexpectedToken,
        ExprExpectedRightParen,
    }

    #[derive(Clone, Copy, Debug, PartialEq)]
    pub struct Error {
        pub kind: ErrorKind,
        pub context: Context,
    }

    impl Error {
        pub fn expr_unexpected_token(context: Context) -> Self {
            Error { kind: ErrorKind::ExprUnexpectedToken, context }
        }

        pub fn expr_expected_right_paren(context: Context) -> Self {
            Error { kind: ErrorKind::ExprExpectedRightParen, context }
        }
    }
}

mod parser {
    use crate::fold::Fold;
    use crate::token::Token::*;
    use crate::token::{Context, IntoTokenIter, Token, TokenIter};
    use std::mem;

    pub struct Parser<T: TokenIter, F: Fold> {
        token: Token,
        span: T::Span,
        iter: T,
        fold: F,
    }

    impl<T: TokenIter, F: Fold> Parser<T, F> {
        pub fn new(tokens: impl IntoTokenIter<TokenIter = T>, fold: F) -> Self {
            let mut iter = tokens.into_token_iter();
            let (token, span) = iter.next();
            Parser { token, span, iter, fold }
        }

        pub fn into_fold(self) -> F {
            self.fold
        }

        pub fn fold_expr(&mut self) -> F::Expr {
            self.expr()
        }

        fn next(&mut self) -> (Token, T::Span) {
            let (next_token, next_span) = self.iter.next();
            let token = mem::replace(&mut self.token, next_token);
            let span = mem::replace(&mut self.span, next_span);
            (token, span)
        }

        fn skip(&mut self) -> Context {
            let (token, span) = self.next();
            Context { token, span: self.iter.span(span) }
        }

        // expr = term ('+' term)*
        fn expr(&mut self) -> F::Expr {
            let mut e1 = self.term();
            while self.token == Plus {
                self.next();
                let e2 = self.term();
                e1 = self.fold.expr_add(e1, e2);
            }
            e1
        }

        // term = factor ('*' factor)*
        fn term(&mut self) -> F::Expr {
            let mut e1 = self.factor();
            while self.token == Times {
                self.next();
                let e2 = self.factor();
                e1 = self.fold.expr_mul(e1, e2);
            }
            e1
        }

        // factor = lit | '-' factor | '(' expr ')'
        fn factor(&mut self) -> F::Expr {
            match self.token {
                Lit(f) => {
                    self.next();
                    self.fold.expr_lit(f)
                }
                Minus => {
                    self.next();
                    let e = self.factor();
                    self.fold.expr_neg(e)
                }
                LeftParen => {
                    self.next();
                    let e = self.expr();
                    if self.token == RightParen {
                        self.next();
                        self.fold.expr_paren(e)
                    } else {
                        let c = self.skip();
                        while self.token != Eof && self.token != RightParen {
                            self.next();
                        }
                        self.fold.expr_expected_right_paren(e, c)
                    }
                }
                _ => {
                    let c = self.skip();
                    self.fold.expr_unexpected_token(c)
                }
            }
        }
    }
}

mod ast {
    use crate::fold::{Context, Fold};
    use Expr::*;

    #[derive(Clone, Debug, PartialEq)]
    pub enum Expr {
        UnexpectedToken(Box<Context>),
        ExpectedRightParen(Subexpr, Box<Context>),
        Lit(f64),
        Paren(Subexpr),
        Neg(Subexpr),
        Mul(Subexpr, Subexpr),
        Add(Subexpr, Subexpr),
    }

    pub type Subexpr = Box<Expr>;

    impl Expr {
        pub fn into_subexpr(self) -> Subexpr {
            Box::new(self)
        }

        pub fn fold_with<F: Fold>(&self, fold: &mut F) -> F::Expr {
            match self {
                UnexpectedToken(c) => fold.expr_unexpected_token(**c),
                ExpectedRightParen(e, c) => {
                    let e = e.fold_with(fold);
                    fold.expr_expected_right_paren(e, **c)
                }
                Lit(f) => fold.expr_lit(*f),
                Paren(e) => {
                    let e = e.fold_with(fold);
                    fold.expr_paren(e)
                }
                Neg(e) => {
                    let e = e.fold_with(fold);
                    fold.expr_neg(e)
                }
                Mul(e1, e2) => {
                    let e1 = e1.fold_with(fold);
                    let e2 = e2.fold_with(fold);
                    fold.expr_mul(e1, e2)
                }
                Add(e1, e2) => {
                    let e1 = e1.fold_with(fold);
                    let e2 = e2.fold_with(fold);
                    fold.expr_add(e1, e2)
                }
            }
        }
    }

    pub struct Builder;

    impl Fold for Builder {
        type Expr = Expr;

        fn expr_unexpected_token(&mut self, c: Context) -> Self::Expr {
            UnexpectedToken(Box::new(c))
        }

        fn expr_expected_right_paren(&mut self, e: Self::Expr, c: Context) -> Self::Expr {
            ExpectedRightParen(e.into_subexpr(), Box::new(c))
        }

        fn expr_lit(&mut self, f: f64) -> Self::Expr {
            Lit(f)
        }

        fn expr_paren(&mut self, e: Self::Expr) -> Self::Expr {
            Paren(e.into_subexpr())
        }

        fn expr_neg(&mut self, e: Self::Expr) -> Self::Expr {
            Neg(e.into_subexpr())
        }

        fn expr_mul(&mut self, e1: Self::Expr, e2: Self::Expr) -> Self::Expr {
            Mul(e1.into_subexpr(), e2.into_subexpr())
        }

        fn expr_add(&mut self, e1: Self::Expr, e2: Self::Expr) -> Self::Expr {
            Add(e1.into_subexpr(), e2.into_subexpr())
        }
    }
}

mod eval {
    pub use crate::error::Error;
    use crate::fold::{Context, Fold};

    pub struct Evaluator {
        pub errors: Vec<Error>,
    }

    pub type Expr = f64;

    impl Fold for Evaluator {
        type Expr = Expr;

        fn expr_unexpected_token(&mut self, c: Context) -> Self::Expr {
            self.errors.push(Error::expr_unexpected_token(c));
            f64::NAN
        }

        fn expr_lit(&mut self, f: f64) -> Self::Expr {
            f
        }

        fn expr_paren(&mut self, e: Self::Expr) -> Self::Expr {
            e
        }

        fn expr_expected_right_paren(&mut self, e: Self::Expr, c: Context) -> Self::Expr {
            self.errors.push(Error::expr_expected_right_paren(c));
            e
        }

        fn expr_neg(&mut self, e: Self::Expr) -> Self::Expr {
            -e
        }

        fn expr_mul(&mut self, e1: Self::Expr, e2: Self::Expr) -> Self::Expr {
            e1 * e2
        }

        fn expr_add(&mut self, e1: Self::Expr, e2: Self::Expr) -> Self::Expr {
            e1 + e2
        }
    }
}

mod vm {
    pub use crate::error::Error;
    use crate::fold::{Context, Fold};
    use Command::*;

    pub enum Command {
        Push(f64),
        Neg,
        Mul,
        Add,
    }

    pub struct Compiler {
        commands: Vec<Command>,
        errors: Vec<Error>,
    }

    impl Compiler {
        pub fn into_result(self) -> Result<Vec<Command>, Vec<Error>> {
            if self.errors.is_empty() {
                Ok(self.commands)
            } else {
                Err(self.errors)
            }
        }
    }

    impl Fold for Compiler {
        type Expr = ();

        fn expr_unexpected_token(&mut self, c: Context) -> Self::Expr {
            self.errors.push(Error::expr_unexpected_token(c));
        }

        fn expr_expected_right_paren(&mut self, _e: Self::Expr, c: Context) -> Self::Expr {
            self.errors.push(Error::expr_expected_right_paren(c));
        }

        fn expr_lit(&mut self, f: f64) -> Self::Expr {
            self.commands.push(Push(f));
        }

        fn expr_paren(&mut self, _e: Self::Expr) -> Self::Expr {}

        fn expr_neg(&mut self, _e: Self::Expr) -> Self::Expr {
            self.commands.push(Neg);
        }

        fn expr_mul(&mut self, _e1: Self::Expr, _e2: Self::Expr) -> Self::Expr {
            self.commands.push(Mul);
        }

        fn expr_add(&mut self, _e1: Self::Expr, _e2: Self::Expr) -> Self::Expr {
            self.commands.push(Add);
        }
    }
}

fn main() {}