Debian Codegraph @

.cargo/vendor/nom/tests/expression_ast.rs

raw
1 use nom::{
2 branch::alt,
3 bytes::complete::tag,
4 character::complete::{alphanumeric1 as alphanumeric, digit1 as digit},
5 combinator::{map, map_res},
6 multi::separated_list0,
7 sequence::delimited,
8 IResult, Parser,
9 };
10 use nom_language::precedence::{binary_op, precedence, unary_op, Assoc, Operation};
11
12 // Elements of the abstract syntax tree (ast) that represents an expression.
13 #[derive(Debug)]
14 pub enum Expr {
15 // A number literal.
16 Num(i64),
17 // An identifier.
18 Iden(String),
19 // Arithmetic operations. Each have a left hand side (lhs) and a right hand side (rhs).
20 Add(Box<Expr>, Box<Expr>),
21 Sub(Box<Expr>, Box<Expr>),
22 Mul(Box<Expr>, Box<Expr>),
23 Div(Box<Expr>, Box<Expr>),
24 // The function call operation. Left is the expression the function is called on, right is the list of parameters.
25 Call(Box<Expr>, Vec<Expr>),
26 // The ternary operator, the expressions from left to right are: The condition, the true case, the false case.
27 Tern(Box<Expr>, Box<Expr>, Box<Expr>),
28 }
29
30 // Prefix operators.
31 enum PrefixOp {
32 Identity, // +
33 Negate, // -
34 }
35
36 // Postfix operators.
37 enum PostfixOp {
38 // The function call operator. In addition to its own representation "()" it carries additional information that we need to keep here.
39 // Specifically the vector of expressions that make up the parameters.
40 Call(Vec<Expr>), // ()
41 }
42
43 // Binary operators.
44 enum BinaryOp {
45 Addition, // +
46 Subtraction, // -
47 Multiplication, // *
48 Division, // /
49 // The ternary operator can contain a single expression.
50 Ternary(Expr), // ?:
51 }
52
53 // Parser for function calls.
54 fn function_call(i: &str) -> IResult<&str, PostfixOp> {
55 map(
56 delimited(
57 tag("("),
58 // Subexpressions are evaluated by recursing back into the expression parser.
59 separated_list0(tag(","), expression),
60 tag(")"),
61 ),
62 |v: Vec<Expr>| PostfixOp::Call(v),
63 )
64 .parse(i)
65 }
66
67 // The ternary operator is actually just a binary operator that contains another expression. So it can be
68 // handled similarly to the function call operator except its in a binary position and can only contain
69 // a single expression.
70 //
71 // For example the expression "a<b ? a : b" is handled similarly to the function call operator, the
72 // "?" is treated like an opening bracket and the ":" is treated like a closing bracket.
73 //
74 // For the outer expression the result looks like "a<b ?: b". Where "?:" is a single operator. The
75 // subexpression is contained within the operator in the same way that the function call operator
76 // contains subexpressions.
77 fn ternary_operator(i: &str) -> IResult<&str, BinaryOp> {
78 map(delimited(tag("?"), expression, tag(":")), |e: Expr| {
79 BinaryOp::Ternary(e)
80 })
81 .parse(i)
82 }
83
84 // The actual expression parser .
85 fn expression(i: &str) -> IResult<&str, Expr> {
86 precedence(
87 alt((
88 unary_op(2, map(tag("+"), |_| PrefixOp::Identity)),
89 unary_op(2, map(tag("-"), |_| PrefixOp::Negate)),
90 )),
91 // Function calls are implemented as postfix unary operators.
92 unary_op(1, function_call),
93 alt((
94 binary_op(
95 3,
96 Assoc::Left,
97 alt((
98 map(tag("*"), |_| BinaryOp::Multiplication),
99 map(tag("/"), |_| BinaryOp::Division),
100 )),
101 ),
102 binary_op(
103 4,
104 Assoc::Left,
105 alt((
106 map(tag("+"), |_| BinaryOp::Addition),
107 map(tag("-"), |_| BinaryOp::Subtraction),
108 )),
109 ),
110 // Ternary operators are just binary operators with a subexpression.
111 binary_op(5, Assoc::Right, ternary_operator),
112 )),
113 alt((
114 map_res(digit, |s: &str| match s.parse::<i64>() {
115 Ok(s) => Ok(Expr::Num(s)),
116 Err(e) => Err(e),
117 }),
118 map(alphanumeric, |s: &str| Expr::Iden(s.to_string())),
119 delimited(tag("("), expression, tag(")")),
120 )),
121 |op: Operation<PrefixOp, PostfixOp, BinaryOp, Expr>| -> Result<Expr, ()> {
122 use nom_language::precedence::Operation::*;
123 use BinaryOp::*;
124 use PostfixOp::*;
125 use PrefixOp::*;
126 match op {
127 // The identity operator (prefix +) is ignored.
128 Prefix(Identity, e) => Ok(e),
129
130 // Unary minus gets evaluated to the same representation as a multiplication with -1.
131 Prefix(Negate, e) => Ok(Expr::Mul(Expr::Num(-1).into(), e.into())),
132
133 // The list of parameters are taken from the operator and placed into the ast.
134 Postfix(e, Call(p)) => Ok(Expr::Call(e.into(), p)),
135
136 // Meaning is assigned to the expressions of the ternary operator during evaluation.
137 // The lhs becomes the condition, the contained expression is the true case, rhs the false case.
138 Binary(lhs, Ternary(e), rhs) => Ok(Expr::Tern(lhs.into(), e.into(), rhs.into())),
139
140 // Raw operators get turned into their respective ast nodes.
141 Binary(lhs, Multiplication, rhs) => Ok(Expr::Mul(lhs.into(), rhs.into())),
142 Binary(lhs, Division, rhs) => Ok(Expr::Div(lhs.into(), rhs.into())),
143 Binary(lhs, Addition, rhs) => Ok(Expr::Add(lhs.into(), rhs.into())),
144 Binary(lhs, Subtraction, rhs) => Ok(Expr::Sub(lhs.into(), rhs.into())),
145 }
146 },
147 )(i)
148 }
149
150 #[test]
151 fn expression_test() {
152 assert_eq!(
153 expression("-2*max(2,3)-2").map(|(i, x)| (i, format!("{:?}", x))),
154 Ok((
155 "",
156 String::from("Sub(Mul(Mul(Num(-1), Num(2)), Call(Iden(\"max\"), [Num(2), Num(3)])), Num(2))")
157 ))
158 );
159
160 assert_eq!(
161 expression("a?2+c:-2*2").map(|(i, x)| (i, format!("{:?}", x))),
162 Ok((
163 "",
164 String::from(
165 "Tern(Iden(\"a\"), Add(Num(2), Iden(\"c\")), Mul(Mul(Num(-1), Num(2)), Num(2)))"
166 )
167 ))
168 );
169 }