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 | |
12 | use alloc::borrow::Cow; |
13 | use alloc::boxed::Box; |
14 | use alloc::vec::Vec; |
15 | use core::iter::Peekable; |
16 | use core::ops::BitOr; |
17 | |
18 | use crate::iterators::Pair; |
19 | use 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 ] |
46 | macro_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)] |
107 | pub 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)] |
118 | pub struct Operator<R: RuleType> { |
119 | rule: R, |
120 | assoc: Assoc, |
121 | next: Option<Box<Operator<R>>>, |
122 | } |
123 | |
124 | impl<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 | |
149 | impl<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: &mut Box>) = op.next { |
155 | assign_next(op:child, next); |
156 | } else { |
157 | op.next = Some(Box::new(next)); |
158 | } |
159 | } |
160 | |
161 | assign_next(&mut self, next: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)] |
173 | pub struct PrecClimber<R: Clone + 'static> { |
174 | ops: Cow<'static, [(R, u32, Assoc)]>, |
175 | } |
176 | |
177 | #[cfg (feature = "const_prec_climber" )] |
178 | impl<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 | |
212 | impl<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 | } |
361 | |