pest/prec_climber.rs
1// pest. The Elegant Parser
2// Copyright (c) 2018 Dragoș Tiselice
3//
4// Licensed under the Apache License, Version 2.0
5// <LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0> or the MIT
6// license <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
7// option. All files in the project carrying such notice may not be copied,
8// modified, or distributed except according to those terms.
9
10//! Constructs useful in infix operator parsing with the precedence climbing method.
11
12use alloc::borrow::Cow;
13use alloc::boxed::Box;
14use alloc::vec::Vec;
15use core::iter::Peekable;
16use core::ops::BitOr;
17
18use crate::iterators::Pair;
19use crate::RuleType;
20
21/// Macro for more convenient const fn definition of `prec_climber::PrecClimber`.
22///
23/// # Examples
24///
25/// ```
26/// # use pest::prec_climber::{Assoc, PrecClimber};
27/// # use pest::prec_climber;
28/// # #[allow(non_camel_case_types)]
29/// # #[allow(dead_code)]
30/// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
31/// # enum Rule {
32/// # plus,
33/// # minus,
34/// # times,
35/// # divide,
36/// # power
37/// # }
38/// static CLIMBER: PrecClimber<Rule> = prec_climber![
39/// L plus | minus,
40/// L times | divide,
41/// R power,
42/// ];
43/// ```
44#[cfg(feature = "const_prec_climber")]
45#[macro_export]
46macro_rules! prec_climber {
47 (
48 $( $assoc:ident $rule:ident $( | $rules:ident )* ),+ $(,)?
49 ) => {{
50 prec_climber!(
51 @precedences { 1u32 }
52 $( [ $rule $( $rules )* ] )*
53 );
54
55 $crate::prec_climber::PrecClimber::new_const(
56 prec_climber!(
57 @array
58 $( $assoc $rule $(, $assoc $rules )* ),*
59 )
60 )
61 }};
62
63 ( @assoc L ) => { $crate::prec_climber::Assoc::Left };
64 ( @assoc R ) => { $crate::prec_climber::Assoc::Right };
65
66 (
67 @array
68 $(
69 $assoc:ident $rule:ident
70 ),*
71 ) => {
72 &[
73 $(
74 (
75 Rule::$rule,
76 $rule,
77 prec_climber!( @assoc $assoc ),
78 )
79 ),*
80 ]
81 };
82
83 (
84 @precedences { $precedence:expr }
85 ) => {};
86
87 (
88 @precedences { $precedence:expr }
89 [ $( $rule:ident )* ]
90 $( [ $( $rules:ident )* ] )*
91 ) => {
92 $(
93 #[allow(non_upper_case_globals)]
94 const $rule: u32 = $precedence;
95 )*
96 prec_climber!(
97 @precedences { 1u32 + $precedence }
98 $( [ $( $rules )* ] )*
99 );
100 };
101}
102
103/// Associativity of an [`Operator`].
104///
105/// [`Operator`]: struct.Operator.html
106#[derive(Clone, Copy, Debug, Eq, PartialEq)]
107pub enum Assoc {
108 /// Left `Operator` associativity
109 Left,
110 /// Right `Operator` associativity
111 Right,
112}
113
114/// Infix operator used in [`PrecClimber`].
115///
116/// [`PrecClimber`]: struct.PrecClimber.html
117#[derive(Debug)]
118pub struct Operator<R: RuleType> {
119 rule: R,
120 assoc: Assoc,
121 next: Option<Box<Operator<R>>>,
122}
123
124impl<R: RuleType> Operator<R> {
125 /// Creates a new `Operator` from a `Rule` and `Assoc`.
126 ///
127 /// # Examples
128 ///
129 /// ```
130 /// # use pest::prec_climber::{Assoc, Operator};
131 /// # #[allow(non_camel_case_types)]
132 /// # #[allow(dead_code)]
133 /// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
134 /// # enum Rule {
135 /// # plus,
136 /// # minus
137 /// # }
138 /// Operator::new(Rule::plus, Assoc::Left) | Operator::new(Rule::minus, Assoc::Right);
139 /// ```
140 pub fn new(rule: R, assoc: Assoc) -> Operator<R> {
141 Operator {
142 rule,
143 assoc,
144 next: None,
145 }
146 }
147}
148
149impl<R: RuleType> BitOr for Operator<R> {
150 type Output = Self;
151
152 fn bitor(mut self, rhs: Self) -> Self {
153 fn assign_next<R: RuleType>(op: &mut Operator<R>, next: Operator<R>) {
154 if let Some(ref mut child) = op.next {
155 assign_next(child, next);
156 } else {
157 op.next = Some(Box::new(next));
158 }
159 }
160
161 assign_next(&mut self, rhs);
162 self
163 }
164}
165
166/// List of operators and precedences, which can perform [precedence climbing][1] on infix
167/// expressions contained in a [`Pairs`]. The token pairs contained in the `Pairs` should start
168/// with a *primary* pair and then alternate between an *operator* and a *primary*.
169///
170/// [1]: https://en.wikipedia.org/wiki/Operator-precedence_parser#Precedence_climbing_method
171/// [`Pairs`]: ../iterators/struct.Pairs.html
172#[derive(Debug)]
173pub struct PrecClimber<R: Clone + 'static> {
174 ops: Cow<'static, [(R, u32, Assoc)]>,
175}
176
177#[cfg(feature = "const_prec_climber")]
178impl<R: Clone + 'static> PrecClimber<R> {
179 /// Creates a new `PrecClimber` directly from a static slice of
180 /// `(rule: Rule, precedence: u32, associativity: Assoc)` tuples.
181 ///
182 /// Precedence starts from `1`. Entries don't have to be ordered in any way, but it's easier to read when
183 /// sorted.
184 ///
185 /// # Examples
186 ///
187 /// ```
188 /// # use pest::prec_climber::{Assoc, PrecClimber};
189 /// # #[allow(non_camel_case_types)]
190 /// # #[allow(dead_code)]
191 /// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
192 /// # enum Rule {
193 /// # plus,
194 /// # minus,
195 /// # times,
196 /// # divide,
197 /// # power
198 /// # }
199 /// static CLIMBER: PrecClimber<Rule> = PrecClimber::new_const(&[
200 /// (Rule::plus, 1, Assoc::Left), (Rule::minus, 1, Assoc::Left),
201 /// (Rule::times, 2, Assoc::Left), (Rule::divide, 2, Assoc::Left),
202 /// (Rule::power, 3, Assoc::Right)
203 /// ]);
204 /// ```
205 pub const fn new_const(ops: &'static [(R, u32, Assoc)]) -> PrecClimber<R> {
206 PrecClimber {
207 ops: Cow::Borrowed(ops),
208 }
209 }
210}
211
212impl<R: RuleType> PrecClimber<R> {
213 // find matching operator by `rule`
214 fn get(&self, rule: &R) -> Option<(u32, Assoc)> {
215 self.ops
216 .iter()
217 .find(|(r, _, _)| r == rule)
218 .map(|(_, precedence, assoc)| (*precedence, *assoc))
219 }
220
221 /// Creates a new `PrecClimber` from the `Operator`s contained in `ops`. Every entry in the
222 /// `Vec` has precedence *index + 1*. In order to have operators with same precedence, they need
223 /// to be chained with `|` between them.
224 ///
225 /// # Examples
226 ///
227 /// ```
228 /// # use pest::prec_climber::{Assoc, Operator, PrecClimber};
229 /// # #[allow(non_camel_case_types)]
230 /// # #[allow(dead_code)]
231 /// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
232 /// # enum Rule {
233 /// # plus,
234 /// # minus,
235 /// # times,
236 /// # divide,
237 /// # power
238 /// # }
239 /// PrecClimber::new(vec![
240 /// Operator::new(Rule::plus, Assoc::Left) | Operator::new(Rule::minus, Assoc::Left),
241 /// Operator::new(Rule::times, Assoc::Left) | Operator::new(Rule::divide, Assoc::Left),
242 /// Operator::new(Rule::power, Assoc::Right)
243 /// ]);
244 /// ```
245 pub fn new(ops: Vec<Operator<R>>) -> PrecClimber<R> {
246 let ops = ops
247 .into_iter()
248 .zip(1..)
249 .fold(Vec::new(), |mut vec, (op, prec)| {
250 let mut next = Some(op);
251
252 while let Some(op) = next.take() {
253 let Operator {
254 rule,
255 assoc,
256 next: op_next,
257 } = op;
258
259 vec.push((rule, prec, assoc));
260 next = op_next.map(|op| *op);
261 }
262
263 vec
264 });
265
266 PrecClimber {
267 ops: Cow::Owned(ops),
268 }
269 }
270
271 /// Performs the precedence climbing algorithm on the `pairs` in a similar manner to map-reduce.
272 /// *Primary* pairs are mapped with `primary` and then reduced to one single result with
273 /// `infix`.
274 ///
275 /// # Panics
276 ///
277 /// Panics will occur when `pairs` is empty or when the alternating *primary*, *operator*,
278 /// *primary* order is not respected.
279 ///
280 /// # Examples
281 ///
282 /// ```ignore
283 /// let primary = |pair| {
284 /// consume(pair, climber)
285 /// };
286 /// let infix = |lhs: i32, op: Pair<Rule>, rhs: i32| {
287 /// match op.rule() {
288 /// Rule::plus => lhs + rhs,
289 /// Rule::minus => lhs - rhs,
290 /// Rule::times => lhs * rhs,
291 /// Rule::divide => lhs / rhs,
292 /// Rule::power => lhs.pow(rhs as u32),
293 /// _ => unreachable!()
294 /// }
295 /// };
296 ///
297 /// let result = climber.climb(pairs, primary, infix);
298 /// ```
299 pub fn climb<'i, P, F, G, T>(&self, mut pairs: P, mut primary: F, mut infix: G) -> T
300 where
301 P: Iterator<Item = Pair<'i, R>>,
302 F: FnMut(Pair<'i, R>) -> T,
303 G: FnMut(T, Pair<'i, R>, T) -> T,
304 {
305 let lhs = primary(
306 pairs
307 .next()
308 .expect("precedence climbing requires a non-empty Pairs"),
309 );
310 self.climb_rec(lhs, 0, &mut pairs.peekable(), &mut primary, &mut infix)
311 }
312
313 fn climb_rec<'i, P, F, G, T>(
314 &self,
315 mut lhs: T,
316 min_prec: u32,
317 pairs: &mut Peekable<P>,
318 primary: &mut F,
319 infix: &mut G,
320 ) -> T
321 where
322 P: Iterator<Item = Pair<'i, R>>,
323 F: FnMut(Pair<'i, R>) -> T,
324 G: FnMut(T, Pair<'i, R>, T) -> T,
325 {
326 while pairs.peek().is_some() {
327 let rule = pairs.peek().unwrap().as_rule();
328 if let Some((prec, _)) = self.get(&rule) {
329 if prec >= min_prec {
330 let op = pairs.next().unwrap();
331 let mut rhs = primary(pairs.next().expect(
332 "infix operator must be followed by \
333 a primary expression",
334 ));
335
336 while pairs.peek().is_some() {
337 let rule = pairs.peek().unwrap().as_rule();
338 if let Some((new_prec, assoc)) = self.get(&rule) {
339 if new_prec > prec || assoc == Assoc::Right && new_prec == prec {
340 rhs = self.climb_rec(rhs, new_prec, pairs, primary, infix);
341 } else {
342 break;
343 }
344 } else {
345 break;
346 }
347 }
348
349 lhs = infix(lhs, op, rhs);
350 } else {
351 break;
352 }
353 } else {
354 break;
355 }
356 }
357
358 lhs
359 }
360}