firefox/third_party/rust/winnow/examples/arithmetic/parser_lexer.rs

use std::fmt;
use std::fmt::{Debug, Display, Formatter};

use winnow::prelude::*;
use winnow::Result;
use winnow::{
    ascii::{digit1 as digits, multispace0 as multispaces},
    combinator::alt,
    combinator::dispatch,
    combinator::eof,
    combinator::fail,
    combinator::opt,
    combinator::peek,
    combinator::repeat,
    combinator::{delimited, preceded, terminated},
    error::ContextError,
    stream::TokenSlice,
    token::any,
    token::literal,
    token::one_of,
    token::take_till,
};

/// Lex and parse
#[allow(dead_code)]
pub(crate) fn expr2(i: &mut &str) -> Result<Expr> {
    let tokens = tokens.parse_next(i)?;
    let mut tokens = Tokens::new(&tokens);
    expr.parse_next(&mut tokens)
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Token<'s> {
    kind: TokenKind,
    raw: &'s str,
}

impl PartialEq<TokenKind> for Token<'_> {
    fn eq(&self, other: &TokenKind) -> bool {
        self.kind == *other
    }
}

#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub(crate) enum TokenKind {
    Value,
    Oper(Oper),
    OpenParen,
    CloseParen,
    Unknown,
    Eof,
}

impl<'i> Parser<Tokens<'i>, &'i Token<'i>, ContextError> for TokenKind {
    fn parse_next(&mut self, input: &mut Tokens<'i>) -> Result<&'i Token<'i>> {
        literal(*self).parse_next(input).map(|t| &t[0])
    }
}

#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub(crate) enum Oper {
    Add,
    Sub,
    Mul,
    Div,
}

impl winnow::stream::ContainsToken<&'_ Token<'_>> for TokenKind {
    #[inline(always)]
    fn contains_token(&self, token: &'_ Token<'_>) -> bool {
        *self == token.kind
    }
}

impl winnow::stream::ContainsToken<&'_ Token<'_>> for &'_ [TokenKind] {
    #[inline]
    fn contains_token(&self, token: &'_ Token<'_>) -> bool {
        self.iter().any(|t| *t == token.kind)
    }
}

impl<const LEN: usize> winnow::stream::ContainsToken<&'_ Token<'_>> for &'_ [TokenKind; LEN] {
    #[inline]
    fn contains_token(&self, token: &'_ Token<'_>) -> bool {
        self.iter().any(|t| *t == token.kind)
    }
}

impl<const LEN: usize> winnow::stream::ContainsToken<&'_ Token<'_>> for [TokenKind; LEN] {
    #[inline]
    fn contains_token(&self, token: &'_ Token<'_>) -> bool {
        self.iter().any(|t| *t == token.kind)
    }
}

/// Lex tokens
///
/// See [`expr`] to parse the tokens
pub(crate) fn tokens<'s>(i: &mut &'s str) -> Result<Vec<Token<'s>>> {
    let mut tokens: Vec<_> =
        preceded(multispaces, repeat(1.., terminated(token, multispaces))).parse_next(i)?;
    if let Some(eof) = opt(eof.map(|raw| Token {
        kind: TokenKind::Eof,
        raw,
    }))
    .parse_next(i)?
    {
        tokens.push(eof);
    }
    Ok(tokens)
}

fn token<'s>(i: &mut &'s str) -> Result<Token<'s>> {
    dispatch! {peek(any);
        '0'..='9' => digits.value(TokenKind::Value),
        '(' => '('.value(TokenKind::OpenParen),
        ')' => ')'.value(TokenKind::CloseParen),
        '+' => '+'.value(TokenKind::Oper(Oper::Add)),
        '-' => '-'.value(TokenKind::Oper(Oper::Sub)),
        '*' => '*'.value(TokenKind::Oper(Oper::Mul)),
        '/' => '/'.value(TokenKind::Oper(Oper::Div)),
        ' '| '\t'| '\r'| '\n' => fail,
        _ => take_till(.., ('0'..='9', '(', ')', '+', '-', '*', '/')).value(TokenKind::Unknown),
    }
    .with_taken()
    .map(|(kind, raw)| Token { kind, raw })
    .parse_next(i)
}

#[derive(Debug, Clone)]
pub(crate) enum Expr {
    Value(i64),
    Add(Box<Expr>, Box<Expr>),
    Sub(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
    Div(Box<Expr>, Box<Expr>),
    Paren(Box<Expr>),
}

impl Expr {
    pub(crate) fn eval(&self) -> i64 {
        match self {
            Self::Value(v) => *v,
            Self::Add(lhs, rhs) => lhs.eval() + rhs.eval(),
            Self::Sub(lhs, rhs) => lhs.eval() - rhs.eval(),
            Self::Mul(lhs, rhs) => lhs.eval() * rhs.eval(),
            Self::Div(lhs, rhs) => lhs.eval() / rhs.eval(),
            Self::Paren(expr) => expr.eval(),
        }
    }
}

impl Display for Expr {
    fn fmt(&self, format: &mut Formatter<'_>) -> fmt::Result {
        use Expr::{Add, Div, Mul, Paren, Sub, Value};
        match *self {
            Value(val) => write!(format, "{val}"),
            Add(ref left, ref right) => write!(format, "{left} + {right}"),
            Sub(ref left, ref right) => write!(format, "{left} - {right}"),
            Mul(ref left, ref right) => write!(format, "{left} * {right}"),
            Div(ref left, ref right) => write!(format, "{left} / {right}"),
            Paren(ref expr) => write!(format, "({expr})"),
        }
    }
}

pub(crate) type Tokens<'i> = TokenSlice<'i, Token<'i>>;

/// Parse the tokens lexed in [`tokens`]
pub(crate) fn expr(i: &mut Tokens<'_>) -> Result<Expr> {
    let init = term.parse_next(i)?;

    let expr = repeat(
        0..,
        (
            one_of([TokenKind::Oper(Oper::Add), TokenKind::Oper(Oper::Sub)]),
            term,
        ),
    )
    .fold(
        move || init.clone(),
        |acc, (op, val): (&Token<'_>, Expr)| {
            if op.kind == TokenKind::Oper(Oper::Add) {
                Expr::Add(Box::new(acc), Box::new(val))
            } else {
                Expr::Sub(Box::new(acc), Box::new(val))
            }
        },
    )
    .parse_next(i)?;

    opt(TokenKind::Eof).parse_next(i)?;

    Ok(expr)
}

pub(crate) fn term(i: &mut Tokens<'_>) -> Result<Expr> {
    let init = factor.parse_next(i)?;

    repeat(
        0..,
        (
            one_of([TokenKind::Oper(Oper::Mul), TokenKind::Oper(Oper::Div)]),
            factor,
        ),
    )
    .fold(
        move || init.clone(),
        |acc, (op, val): (&Token<'_>, Expr)| {
            if op.kind == TokenKind::Oper(Oper::Mul) {
                Expr::Mul(Box::new(acc), Box::new(val))
            } else {
                Expr::Div(Box::new(acc), Box::new(val))
            }
        },
    )
    .parse_next(i)
}

pub(crate) fn factor(i: &mut Tokens<'_>) -> Result<Expr> {
    alt((
        TokenKind::Value.try_map(|t: &Token<'_>| t.raw.parse::<i64>().map(Expr::Value)),
        parens,
    ))
    .parse_next(i)
}

fn parens(i: &mut Tokens<'_>) -> Result<Expr> {
    delimited(TokenKind::OpenParen, expr, TokenKind::CloseParen)
        .map(|e| Expr::Paren(Box::new(e)))
        .parse_next(i)
}