Merging upstream version 1.76.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

5 files changed, 519 insertions, 148 deletions

diff --git a/vendor/winnow/examples/arithmetic/bench.rs b/vendor/winnow/examples/arithmetic/bench.rs
index 6504454c4..692ac22c9 100644
--- a/vendor/winnow/examples/arithmetic/bench.rs
+++ b/vendor/winnow/examples/arithmetic/bench.rs
@@ -1,19 +1,31 @@
 mod parser;
+mod parser_ast;
+mod parser_lexer;
 
 use winnow::prelude::*;
 
-use parser::expr;
-
 #[allow(clippy::eq_op, clippy::erasing_op)]
 fn arithmetic(c: &mut criterion::Criterion) {
-    let data = "  2*2 / ( 5 - 1) + 3 / 4 * (2 - 7 + 567 *12 /2) + 3*(1+2*( 45 /2));";
+    let data = "  2*2 / ( 5 - 1) + 3 / 4 * (2 - 7 + 567 *12 /2) + 3*(1+2*( 45 /2))";
+    let expected = 2 * 2 / (5 - 1) + 3 * (1 + 2 * (45 / 2));
 
+    assert_eq!(parser::expr.parse(data), Ok(expected));
+    assert_eq!(
+        parser_ast::expr.parse(data).map(|ast| ast.eval()),
+        Ok(expected)
+    );
     assert_eq!(
-        expr.parse_peek(data),
-        Ok((";", 2 * 2 / (5 - 1) + 3 * (1 + 2 * (45 / 2)),))
+        parser_lexer::expr2.parse(data).map(|ast| ast.eval()),
+        Ok(expected)
     );
-    c.bench_function("arithmetic", |b| {
-        b.iter(|| expr.parse_peek(data).unwrap());
+    c.bench_function("direct", |b| {
+        b.iter(|| parser::expr.parse(data).unwrap());
+    });
+    c.bench_function("ast", |b| {
+        b.iter(|| parser_ast::expr.parse(data).unwrap().eval());
+    });
+    c.bench_function("lexer", |b| {
+        b.iter(|| parser_lexer::expr2.parse_peek(data).unwrap());
     });
 }
 
diff --git a/vendor/winnow/examples/arithmetic/main.rs b/vendor/winnow/examples/arithmetic/main.rs
index 94a17d85d..e46cf2f44 100644
--- a/vendor/winnow/examples/arithmetic/main.rs
+++ b/vendor/winnow/examples/arithmetic/main.rs
@@ -2,32 +2,41 @@ use winnow::prelude::*;
 
 mod parser;
 mod parser_ast;
+mod parser_lexer;
 
 fn main() -> Result<(), lexopt::Error> {
     let args = Args::parse()?;
 
     let input = args.input.as_deref().unwrap_or("1 + 1");
+    if let Err(err) = calc(input, args.implementation) {
+        println!("FAILED");
+        println!("{}", err);
+    }
+
+    Ok(())
+}
 
+fn calc(
+    input: &str,
+    imp: Impl,
+) -> Result<(), winnow::error::ParseError<&str, winnow::error::ContextError>> {
     println!("{} =", input);
-    match args.implementation {
-        Impl::Eval => match parser::expr.parse(input) {
-            Ok(result) => {
-                println!("  {}", result);
-            }
-            Err(err) => {
-                println!("  {}", err);
-            }
-        },
-        Impl::Ast => match parser_ast::expr.parse(input) {
-            Ok(result) => {
-                println!("  {:#?}", result);
-            }
-            Err(err) => {
-                println!("  {}", err);
-            }
-        },
+    match imp {
+        Impl::Eval => {
+            let result = parser::expr.parse(input)?;
+            println!("  {}", result);
+        }
+        Impl::Ast => {
+            let result = parser_ast::expr.parse(input)?;
+            println!("  {:#?}={}", result, result.eval());
+        }
+        Impl::Lexer => {
+            let tokens = parser_lexer::lex.parse(input)?;
+            println!("  {:#?}", tokens);
+            let result = parser_lexer::expr.parse(tokens.as_slice()).unwrap();
+            println!("  {:#?}={}", result, result.eval());
+        }
     }
-
     Ok(())
 }
 
@@ -40,6 +49,7 @@ struct Args {
 enum Impl {
     Eval,
     Ast,
+    Lexer,
 }
 
 impl Default for Impl {
@@ -61,6 +71,7 @@ impl Args {
                     res.implementation = args.value()?.parse_with(|s| match s {
                         "eval" => Ok(Impl::Eval),
                         "ast" => Ok(Impl::Ast),
+                        "lexer" => Ok(Impl::Lexer),
                         _ => Err("expected `eval`, `ast`"),
                     })?;
                 }
diff --git a/vendor/winnow/examples/arithmetic/parser.rs b/vendor/winnow/examples/arithmetic/parser.rs
index 50ffbdbbb..165727515 100644
--- a/vendor/winnow/examples/arithmetic/parser.rs
+++ b/vendor/winnow/examples/arithmetic/parser.rs
@@ -2,7 +2,7 @@ use std::str::FromStr;
 
 use winnow::prelude::*;
 use winnow::{
-    ascii::{digit1 as digits, space0 as spaces},
+    ascii::{digit1 as digits, multispace0 as multispaces},
     combinator::alt,
     combinator::delimited,
     combinator::fold_repeat,
@@ -50,53 +50,88 @@ fn term(i: &mut &str) -> PResult<i64> {
     .parse_next(i)
 }
 
-// We transform an integer string into a i64, ignoring surrounding whitespaces
+// We transform an integer string into a i64, ignoring surrounding whitespace
 // We look for a digit suite, and try to convert it.
 // If either str::from_utf8 or FromStr::from_str fail,
 // we fallback to the parens parser defined above
 fn factor(i: &mut &str) -> PResult<i64> {
     delimited(
-        spaces,
-        alt((
-            digits.try_map(FromStr::from_str),
-            delimited('(', expr, ')'),
-            parens,
-        )),
-        spaces,
+        multispaces,
+        alt((digits.try_map(FromStr::from_str), parens)),
+        multispaces,
     )
     .parse_next(i)
 }
 
-// We parse any expr surrounded by parens, ignoring all whitespaces around those
+// We parse any expr surrounded by parens, ignoring all whitespace around those
 fn parens(i: &mut &str) -> PResult<i64> {
     delimited('(', expr, ')').parse_next(i)
 }
 
 #[test]
 fn factor_test() {
-    assert_eq!(factor.parse_peek("3"), Ok(("", 3)));
-    assert_eq!(factor.parse_peek(" 12"), Ok(("", 12)));
-    assert_eq!(factor.parse_peek("537  "), Ok(("", 537)));
-    assert_eq!(factor.parse_peek("  24   "), Ok(("", 24)));
+    let input = "3";
+    let expected = Ok(("", 3));
+    assert_eq!(factor.parse_peek(input), expected);
+
+    let input = " 12";
+    let expected = Ok(("", 12));
+    assert_eq!(factor.parse_peek(input), expected);
+
+    let input = "537 ";
+    let expected = Ok(("", 537));
+    assert_eq!(factor.parse_peek(input), expected);
+
+    let input = "  24     ";
+    let expected = Ok(("", 24));
+    assert_eq!(factor.parse_peek(input), expected);
 }
 
 #[test]
 fn term_test() {
-    assert_eq!(term.parse_peek(" 12 *2 /  3"), Ok(("", 8)));
-    assert_eq!(term.parse_peek(" 2* 3  *2 *2 /  3"), Ok(("", 8)));
-    assert_eq!(term.parse_peek(" 48 /  3/2"), Ok(("", 8)));
+    let input = " 12 *2 /  3";
+    let expected = Ok(("", 8));
+    assert_eq!(term.parse_peek(input), expected);
+
+    let input = " 12 *2 /  3";
+    let expected = Ok(("", 8));
+    assert_eq!(term.parse_peek(input), expected);
+
+    let input = " 2* 3  *2 *2 /  3";
+    let expected = Ok(("", 8));
+    assert_eq!(term.parse_peek(input), expected);
+
+    let input = " 48 /  3/2";
+    let expected = Ok(("", 8));
+    assert_eq!(term.parse_peek(input), expected);
 }
 
 #[test]
 fn expr_test() {
-    assert_eq!(expr.parse_peek(" 1 +  2 "), Ok(("", 3)));
-    assert_eq!(expr.parse_peek(" 12 + 6 - 4+  3"), Ok(("", 17)));
-    assert_eq!(expr.parse_peek(" 1 + 2*3 + 4"), Ok(("", 11)));
+    let input = " 1 +  2 ";
+    let expected = Ok(("", 3));
+    assert_eq!(expr.parse_peek(input), expected);
+
+    let input = " 12 + 6 - 4+  3";
+    let expected = Ok(("", 17));
+    assert_eq!(expr.parse_peek(input), expected);
+
+    let input = " 1 + 2*3 + 4";
+    let expected = Ok(("", 11));
+    assert_eq!(expr.parse_peek(input), expected);
 }
 
 #[test]
 fn parens_test() {
-    assert_eq!(expr.parse_peek(" (  2 )"), Ok(("", 2)));
-    assert_eq!(expr.parse_peek(" 2* (  3 + 4 ) "), Ok(("", 14)));
-    assert_eq!(expr.parse_peek("  2*2 / ( 5 - 1) + 3"), Ok(("", 4)));
+    let input = " (  2 )";
+    let expected = Ok(("", 2));
+    assert_eq!(expr.parse_peek(input), expected);
+
+    let input = " 2* (  3 + 4 ) ";
+    let expected = Ok(("", 14));
+    assert_eq!(expr.parse_peek(input), expected);
+
+    let input = "  2*2 / ( 5 - 1) + 3";
+    let expected = Ok(("", 4));
+    assert_eq!(expr.parse_peek(input), expected);
 }
diff --git a/vendor/winnow/examples/arithmetic/parser_ast.rs b/vendor/winnow/examples/arithmetic/parser_ast.rs
index 5fb9847c0..0ca153487 100644
--- a/vendor/winnow/examples/arithmetic/parser_ast.rs
+++ b/vendor/winnow/examples/arithmetic/parser_ast.rs
@@ -5,13 +5,14 @@ use std::str::FromStr;
 
 use winnow::prelude::*;
 use winnow::{
-    ascii::{digit1 as digit, multispace0 as multispace},
+    ascii::{digit1 as digits, multispace0 as multispaces},
     combinator::alt,
-    combinator::repeat,
-    combinator::{delimited, preceded},
+    combinator::delimited,
+    combinator::fold_repeat,
+    token::one_of,
 };
 
-#[derive(Debug)]
+#[derive(Debug, Clone)]
 pub enum Expr {
     Value(i64),
     Add(Box<Expr>, Box<Expr>),
@@ -21,12 +22,17 @@ pub enum Expr {
     Paren(Box<Expr>),
 }
 
-#[derive(Debug)]
-pub enum Oper {
-    Add,
-    Sub,
-    Mul,
-    Div,
+impl Expr {
+    pub 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 {
@@ -44,125 +50,135 @@ impl Display for Expr {
 }
 
 pub fn expr(i: &mut &str) -> PResult<Expr> {
-    let initial = term(i)?;
-    let remainder = repeat(
+    let init = term.parse_next(i)?;
+
+    fold_repeat(
         0..,
-        alt((
-            |i: &mut &str| {
-                let add = preceded("+", term).parse_next(i)?;
-                Ok((Oper::Add, add))
-            },
-            |i: &mut &str| {
-                let sub = preceded("-", term).parse_next(i)?;
-                Ok((Oper::Sub, sub))
-            },
-        )),
+        (one_of(['+', '-']), term),
+        move || init.clone(),
+        |acc, (op, val): (char, Expr)| {
+            if op == '+' {
+                Expr::Add(Box::new(acc), Box::new(val))
+            } else {
+                Expr::Sub(Box::new(acc), Box::new(val))
+            }
+        },
     )
-    .parse_next(i)?;
-
-    Ok(fold_exprs(initial, remainder))
+    .parse_next(i)
 }
 
 fn term(i: &mut &str) -> PResult<Expr> {
-    let initial = factor(i)?;
-    let remainder = repeat(
+    let init = factor.parse_next(i)?;
+
+    fold_repeat(
         0..,
-        alt((
-            |i: &mut &str| {
-                let mul = preceded("*", factor).parse_next(i)?;
-                Ok((Oper::Mul, mul))
-            },
-            |i: &mut &str| {
-                let div = preceded("/", factor).parse_next(i)?;
-                Ok((Oper::Div, div))
-            },
-        )),
+        (one_of(['*', '/']), factor),
+        move || init.clone(),
+        |acc, (op, val): (char, Expr)| {
+            if op == '*' {
+                Expr::Mul(Box::new(acc), Box::new(val))
+            } else {
+                Expr::Div(Box::new(acc), Box::new(val))
+            }
+        },
     )
-    .parse_next(i)?;
-
-    Ok(fold_exprs(initial, remainder))
-}
-
-fn factor(i: &mut &str) -> PResult<Expr> {
-    alt((
-        delimited(multispace, digit, multispace)
-            .try_map(FromStr::from_str)
-            .map(Expr::Value),
-        parens,
-    ))
     .parse_next(i)
 }
 
-fn parens(i: &mut &str) -> PResult<Expr> {
+fn factor(i: &mut &str) -> PResult<Expr> {
     delimited(
-        multispace,
-        delimited("(", expr.map(|e| Expr::Paren(Box::new(e))), ")"),
-        multispace,
+        multispaces,
+        alt((digits.try_map(FromStr::from_str).map(Expr::Value), parens)),
+        multispaces,
     )
     .parse_next(i)
 }
 
-fn fold_exprs(initial: Expr, remainder: Vec<(Oper, Expr)>) -> Expr {
-    remainder.into_iter().fold(initial, |acc, pair| {
-        let (oper, expr) = pair;
-        match oper {
-            Oper::Add => Expr::Add(Box::new(acc), Box::new(expr)),
-            Oper::Sub => Expr::Sub(Box::new(acc), Box::new(expr)),
-            Oper::Mul => Expr::Mul(Box::new(acc), Box::new(expr)),
-            Oper::Div => Expr::Div(Box::new(acc), Box::new(expr)),
-        }
-    })
+fn parens(i: &mut &str) -> PResult<Expr> {
+    delimited("(", expr, ")")
+        .map(|e| Expr::Paren(Box::new(e)))
+        .parse_next(i)
 }
 
 #[test]
 fn factor_test() {
-    assert_eq!(
-        factor
-            .parse_peek("  3  ")
-            .map(|(i, x)| (i, format!("{:?}", x))),
-        Ok(("", String::from("Value(3)")))
-    );
+    let input = "3";
+    let expected = Ok(("", String::from("Value(3)")));
+    assert_eq!(factor.map(|e| format!("{e:?}")).parse_peek(input), expected);
+
+    let input = " 12";
+    let expected = Ok(("", String::from("Value(12)")));
+    assert_eq!(factor.map(|e| format!("{e:?}")).parse_peek(input), expected);
+
+    let input = "537 ";
+    let expected = Ok(("", String::from("Value(537)")));
+    assert_eq!(factor.map(|e| format!("{e:?}")).parse_peek(input), expected);
+
+    let input = "  24     ";
+    let expected = Ok(("", String::from("Value(24)")));
+    assert_eq!(factor.map(|e| format!("{e:?}")).parse_peek(input), expected);
 }
 
 #[test]
 fn term_test() {
-    assert_eq!(
-        term.parse_peek(" 3 *  5   ")
-            .map(|(i, x)| (i, format!("{:?}", x))),
-        Ok(("", String::from("Mul(Value(3), Value(5))")))
-    );
+    let input = " 12 *2 /  3";
+    let expected = Ok(("", String::from("Div(Mul(Value(12), Value(2)), Value(3))")));
+    assert_eq!(term.map(|e| format!("{e:?}")).parse_peek(input), expected);
+
+    let input = " 12 *2 /  3";
+    let expected = Ok(("", String::from("Div(Mul(Value(12), Value(2)), Value(3))")));
+    assert_eq!(term.map(|e| format!("{e:?}")).parse_peek(input), expected);
+
+    let input = " 2* 3  *2 *2 /  3";
+    let expected = Ok((
+        "",
+        String::from("Div(Mul(Mul(Mul(Value(2), Value(3)), Value(2)), Value(2)), Value(3))"),
+    ));
+    assert_eq!(term.map(|e| format!("{e:?}")).parse_peek(input), expected);
+
+    let input = " 48 /  3/2";
+    let expected = Ok(("", String::from("Div(Div(Value(48), Value(3)), Value(2))")));
+    assert_eq!(term.map(|e| format!("{e:?}")).parse_peek(input), expected);
 }
 
 #[test]
 fn expr_test() {
-    assert_eq!(
-        expr.parse_peek(" 1 + 2 *  3 ")
-            .map(|(i, x)| (i, format!("{:?}", x))),
-        Ok(("", String::from("Add(Value(1), Mul(Value(2), Value(3)))")))
-    );
-    assert_eq!(
-        expr.parse_peek(" 1 + 2 *  3 / 4 - 5 ")
-            .map(|(i, x)| (i, format!("{:?}", x))),
-        Ok((
-            "",
-            String::from("Sub(Add(Value(1), Div(Mul(Value(2), Value(3)), Value(4))), Value(5))")
-        ))
-    );
-    assert_eq!(
-        expr.parse_peek(" 72 / 2 / 3 ")
-            .map(|(i, x)| (i, format!("{:?}", x))),
-        Ok(("", String::from("Div(Div(Value(72), Value(2)), Value(3))")))
-    );
+    let input = " 1 +  2 ";
+    let expected = Ok(("", String::from("Add(Value(1), Value(2))")));
+    assert_eq!(expr.map(|e| format!("{e:?}")).parse_peek(input), expected);
+
+    let input = " 12 + 6 - 4+  3";
+    let expected = Ok((
+        "",
+        String::from("Add(Sub(Add(Value(12), Value(6)), Value(4)), Value(3))"),
+    ));
+    assert_eq!(expr.map(|e| format!("{e:?}")).parse_peek(input), expected);
+
+    let input = " 1 + 2*3 + 4";
+    let expected = Ok((
+        "",
+        String::from("Add(Add(Value(1), Mul(Value(2), Value(3))), Value(4))"),
+    ));
+    assert_eq!(expr.map(|e| format!("{e:?}")).parse_peek(input), expected);
 }
 
 #[test]
 fn parens_test() {
-    assert_eq!(
-        expr.parse_peek(" ( 1 + 2 ) *  3 ")
-            .map(|(i, x)| (i, format!("{:?}", x))),
-        Ok((
-            "",
-            String::from("Mul(Paren(Add(Value(1), Value(2))), Value(3))")
-        ))
-    );
+    let input = " (  2 )";
+    let expected = Ok(("", String::from("Paren(Value(2))")));
+    assert_eq!(expr.map(|e| format!("{e:?}")).parse_peek(input), expected);
+
+    let input = " 2* (  3 + 4 ) ";
+    let expected = Ok((
+        "",
+        String::from("Mul(Value(2), Paren(Add(Value(3), Value(4))))"),
+    ));
+    assert_eq!(expr.map(|e| format!("{e:?}")).parse_peek(input), expected);
+
+    let input = "  2*2 / ( 5 - 1) + 3";
+    let expected = Ok((
+        "",
+        String::from("Add(Div(Mul(Value(2), Value(2)), Paren(Sub(Value(5), Value(1)))), Value(3))"),
+    ));
+    assert_eq!(expr.map(|e| format!("{e:?}")).parse_peek(input), expected);
 }
diff --git a/vendor/winnow/examples/arithmetic/parser_lexer.rs b/vendor/winnow/examples/arithmetic/parser_lexer.rs
new file mode 100644
index 000000000..f49566d38
--- /dev/null
+++ b/vendor/winnow/examples/arithmetic/parser_lexer.rs
@@ -0,0 +1,297 @@
+use std::fmt;
+use std::fmt::{Debug, Display, Formatter};
+
+use std::str::FromStr;
+
+use winnow::prelude::*;
+use winnow::{
+    ascii::{digit1 as digits, multispace0 as multispaces},
+    combinator::alt,
+    combinator::dispatch,
+    combinator::fail,
+    combinator::fold_repeat,
+    combinator::peek,
+    combinator::repeat,
+    combinator::{delimited, preceded, terminated},
+    token::any,
+    token::one_of,
+};
+
+#[derive(Debug, Clone)]
+pub 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 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),
+        }
+    }
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub enum Token {
+    Value(i64),
+    Oper(Oper),
+    OpenParen,
+    CloseParen,
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub enum Oper {
+    Add,
+    Sub,
+    Mul,
+    Div,
+}
+
+impl winnow::stream::ContainsToken<Token> for Token {
+    #[inline(always)]
+    fn contains_token(&self, token: Token) -> bool {
+        *self == token
+    }
+}
+
+impl winnow::stream::ContainsToken<Token> for &'_ [Token] {
+    #[inline]
+    fn contains_token(&self, token: Token) -> bool {
+        self.iter().any(|t| *t == token)
+    }
+}
+
+impl<const LEN: usize> winnow::stream::ContainsToken<Token> for &'_ [Token; LEN] {
+    #[inline]
+    fn contains_token(&self, token: Token) -> bool {
+        self.iter().any(|t| *t == token)
+    }
+}
+
+impl<const LEN: usize> winnow::stream::ContainsToken<Token> for [Token; LEN] {
+    #[inline]
+    fn contains_token(&self, token: Token) -> bool {
+        self.iter().any(|t| *t == token)
+    }
+}
+
+#[allow(dead_code)]
+pub fn expr2(i: &mut &str) -> PResult<Expr> {
+    let tokens = lex.parse_next(i)?;
+    expr.parse_next(&mut tokens.as_slice())
+}
+
+pub fn lex(i: &mut &str) -> PResult<Vec<Token>> {
+    preceded(multispaces, repeat(1.., terminated(token, multispaces))).parse_next(i)
+}
+
+fn token(i: &mut &str) -> PResult<Token> {
+    dispatch! {peek(any);
+        '0'..='9' => digits.try_map(FromStr::from_str).map(Token::Value),
+        '(' => '('.value(Token::OpenParen),
+        ')' => ')'.value(Token::CloseParen),
+        '+' => '+'.value(Token::Oper(Oper::Add)),
+        '-' => '-'.value(Token::Oper(Oper::Sub)),
+        '*' => '*'.value(Token::Oper(Oper::Mul)),
+        '/' => '/'.value(Token::Oper(Oper::Div)),
+        _ => fail,
+    }
+    .parse_next(i)
+}
+
+pub fn expr(i: &mut &[Token]) -> PResult<Expr> {
+    let init = term.parse_next(i)?;
+
+    fold_repeat(
+        0..,
+        (
+            one_of([Token::Oper(Oper::Add), Token::Oper(Oper::Sub)]),
+            term,
+        ),
+        move || init.clone(),
+        |acc, (op, val): (Token, Expr)| {
+            if op == Token::Oper(Oper::Add) {
+                Expr::Add(Box::new(acc), Box::new(val))
+            } else {
+                Expr::Sub(Box::new(acc), Box::new(val))
+            }
+        },
+    )
+    .parse_next(i)
+}
+
+fn term(i: &mut &[Token]) -> PResult<Expr> {
+    let init = factor.parse_next(i)?;
+
+    fold_repeat(
+        0..,
+        (
+            one_of([Token::Oper(Oper::Mul), Token::Oper(Oper::Div)]),
+            factor,
+        ),
+        move || init.clone(),
+        |acc, (op, val): (Token, Expr)| {
+            if op == Token::Oper(Oper::Mul) {
+                Expr::Mul(Box::new(acc), Box::new(val))
+            } else {
+                Expr::Div(Box::new(acc), Box::new(val))
+            }
+        },
+    )
+    .parse_next(i)
+}
+
+fn factor(i: &mut &[Token]) -> PResult<Expr> {
+    alt((
+        one_of(|t| matches!(t, Token::Value(_))).map(|t| match t {
+            Token::Value(v) => Expr::Value(v),
+            _ => unreachable!(),
+        }),
+        parens,
+    ))
+    .parse_next(i)
+}
+
+fn parens(i: &mut &[Token]) -> PResult<Expr> {
+    delimited(one_of(Token::OpenParen), expr, one_of(Token::CloseParen))
+        .map(|e| Expr::Paren(Box::new(e)))
+        .parse_next(i)
+}
+
+#[test]
+fn lex_test() {
+    let input = "3";
+    let expected = Ok(String::from(r#"("", [Value(3)])"#));
+    assert_eq!(lex.parse_peek(input).map(|e| format!("{e:?}")), expected);
+
+    let input = "  24     ";
+    let expected = Ok(String::from(r#"("", [Value(24)])"#));
+    assert_eq!(lex.parse_peek(input).map(|e| format!("{e:?}")), expected);
+
+    let input = " 12 *2 /  3";
+    let expected = Ok(String::from(
+        r#"("", [Value(12), Oper(Mul), Value(2), Oper(Div), Value(3)])"#,
+    ));
+    assert_eq!(lex.parse_peek(input).map(|e| format!("{e:?}")), expected);
+
+    let input = "  2*2 / ( 5 - 1) + 3";
+    let expected = Ok(String::from(
+        r#"("", [Value(2), Oper(Mul), Value(2), Oper(Div), OpenParen, Value(5), Oper(Sub), Value(1), CloseParen, Oper(Add), Value(3)])"#,
+    ));
+    assert_eq!(lex.parse_peek(input).map(|e| format!("{e:?}")), expected);
+}
+
+#[test]
+fn factor_test() {
+    let input = "3";
+    let expected = Ok(String::from("Value(3)"));
+    let input = lex.parse(input).unwrap();
+    assert_eq!(factor.map(|e| format!("{e:?}")).parse(&input), expected);
+
+    let input = " 12";
+    let expected = Ok(String::from("Value(12)"));
+    let input = lex.parse(input).unwrap();
+    assert_eq!(factor.map(|e| format!("{e:?}")).parse(&input), expected);
+
+    let input = "537 ";
+    let expected = Ok(String::from("Value(537)"));
+    let input = lex.parse(input).unwrap();
+    assert_eq!(factor.map(|e| format!("{e:?}")).parse(&input), expected);
+
+    let input = "  24     ";
+    let expected = Ok(String::from("Value(24)"));
+    let input = lex.parse(input).unwrap();
+    assert_eq!(factor.map(|e| format!("{e:?}")).parse(&input), expected);
+}
+
+#[test]
+fn term_test() {
+    let input = " 12 *2 /  3";
+    let expected = Ok(String::from("Div(Mul(Value(12), Value(2)), Value(3))"));
+    let input = lex.parse(input).unwrap();
+    assert_eq!(term.map(|e| format!("{e:?}")).parse(&input), expected);
+
+    let input = " 12 *2 /  3";
+    let expected = Ok(String::from("Div(Mul(Value(12), Value(2)), Value(3))"));
+    let input = lex.parse(input).unwrap();
+    assert_eq!(term.map(|e| format!("{e:?}")).parse(&input), expected);
+
+    let input = " 2* 3  *2 *2 /  3";
+    let expected = Ok(String::from(
+        "Div(Mul(Mul(Mul(Value(2), Value(3)), Value(2)), Value(2)), Value(3))",
+    ));
+    let input = lex.parse(input).unwrap();
+    assert_eq!(term.map(|e| format!("{e:?}")).parse(&input), expected);
+
+    let input = " 48 /  3/2";
+    let expected = Ok(String::from("Div(Div(Value(48), Value(3)), Value(2))"));
+    let input = lex.parse(input).unwrap();
+    assert_eq!(term.map(|e| format!("{e:?}")).parse(&input), expected);
+}
+
+#[test]
+fn expr_test() {
+    let input = " 1 +  2 ";
+    let expected = Ok(String::from("Add(Value(1), Value(2))"));
+    let input = lex.parse(input).unwrap();
+    assert_eq!(expr.map(|e| format!("{e:?}")).parse(&input), expected);
+
+    let input = " 12 + 6 - 4+  3";
+    let expected = Ok(String::from(
+        "Add(Sub(Add(Value(12), Value(6)), Value(4)), Value(3))",
+    ));
+    let input = lex.parse(input).unwrap();
+    assert_eq!(expr.map(|e| format!("{e:?}")).parse(&input), expected);
+
+    let input = " 1 + 2*3 + 4";
+    let expected = Ok(String::from(
+        "Add(Add(Value(1), Mul(Value(2), Value(3))), Value(4))",
+    ));
+    let input = lex.parse(input).unwrap();
+    assert_eq!(expr.map(|e| format!("{e:?}")).parse(&input), expected);
+}
+
+#[test]
+fn parens_test() {
+    let input = " (  2 )";
+    let expected = Ok(String::from("Paren(Value(2))"));
+    let input = lex.parse(input).unwrap();
+    assert_eq!(expr.map(|e| format!("{e:?}")).parse(&input), expected);
+
+    let input = " 2* (  3 + 4 ) ";
+    let expected = Ok(String::from(
+        "Mul(Value(2), Paren(Add(Value(3), Value(4))))",
+    ));
+    let input = lex.parse(input).unwrap();
+    assert_eq!(expr.map(|e| format!("{e:?}")).parse(&input), expected);
+
+    let input = "  2*2 / ( 5 - 1) + 3";
+    let expected = Ok(String::from(
+        "Add(Div(Mul(Value(2), Value(2)), Paren(Sub(Value(5), Value(1)))), Value(3))",
+    ));
+    let input = lex.parse(input).unwrap();
+    assert_eq!(expr.map(|e| format!("{e:?}")).parse(&input), expected);
+}