/rust/registry/src/index.crates.io-6f17d22bba15001f/pest-2.7.15/src/prec_climber.rs

Source (jump to first uncovered line)
// pest. The Elegant Parser
// Copyright (c) 2018 Dragoș Tiselice
//
// Licensed under the Apache License, Version 2.0
// <LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0> or the MIT
// license <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. All files in the project carrying such notice may not be copied,
// modified, or distributed except according to those terms.

//! Constructs useful in infix operator parsing with the precedence climbing method.

use alloc::borrow::Cow;
use alloc::boxed::Box;
use alloc::vec::Vec;
use core::iter::Peekable;
use core::ops::BitOr;

use crate::iterators::Pair;
use crate::RuleType;

/// Macro for more convenient const fn definition of `prec_climber::PrecClimber`.
///
/// # Examples
///
/// ```
/// # use pest::prec_climber::{Assoc, PrecClimber};
/// # use pest::prec_climber;
/// # #[allow(non_camel_case_types)]
/// # #[allow(dead_code)]
/// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
/// # enum Rule {
/// #     plus,
/// #     minus,
/// #     times,
/// #     divide,
/// #     power
/// # }
/// static CLIMBER: PrecClimber<Rule> = prec_climber![
///     L   plus | minus,
///     L   times | divide,
///     R   power,
/// ];
/// ```
#[cfg(feature = "const_prec_climber")]
#[macro_export]
macro_rules! prec_climber {
    (
        $( $assoc:ident $rule:ident $( | $rules:ident )* ),+ $(,)?
    ) => {{
        prec_climber!(
            @precedences { 1u32 }
            $( [ $rule $( $rules )* ] )*
        );

        $crate::prec_climber::PrecClimber::new_const(
            prec_climber!(
                @array
                $( $assoc $rule $(, $assoc $rules )* ),*
            )
        )
    }};

    ( @assoc L ) => { $crate::prec_climber::Assoc::Left };
    ( @assoc R ) => { $crate::prec_climber::Assoc::Right };

    (
        @array
        $(
            $assoc:ident $rule:ident
        ),*
    ) => {
        &[
            $(
                (
                    Rule::$rule,
                    $rule,
                    prec_climber!( @assoc $assoc ),
                )
            ),*
        ]
    };

    (
        @precedences { $precedence:expr }
    ) => {};

    (
        @precedences { $precedence:expr }
        [ $( $rule:ident )* ]
        $( [ $( $rules:ident )* ] )*
    ) => {
        $(
            #[allow(non_upper_case_globals)]
            const $rule: u32 = $precedence;
        )*
        prec_climber!(
            @precedences { 1u32 + $precedence }
            $( [ $( $rules )* ] )*
        );
    };
}

/// Associativity of an [`Operator`].
///
/// [`Operator`]: struct.Operator.html
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum Assoc {
    /// Left `Operator` associativity
    Left,
    /// Right `Operator` associativity
    Right,
}

/// Infix operator used in [`PrecClimber`].
///
/// [`PrecClimber`]: struct.PrecClimber.html
#[derive(Debug)]
pub struct Operator<R: RuleType> {
    rule: R,
    assoc: Assoc,
    next: Option<Box<Operator<R>>>,
}

impl<R: RuleType> Operator<R> {
    /// Creates a new `Operator` from a `Rule` and `Assoc`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use pest::prec_climber::{Assoc, Operator};
    /// # #[allow(non_camel_case_types)]
    /// # #[allow(dead_code)]
    /// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
    /// # enum Rule {
    /// #     plus,
    /// #     minus
    /// # }
    /// Operator::new(Rule::plus, Assoc::Left) | Operator::new(Rule::minus, Assoc::Right);
    /// ```
    pub fn new(rule: R, assoc: Assoc) -> Operator<R> {
        Operator {
            rule,
            assoc,
            next: None,
        }
    }
}

impl<R: RuleType> BitOr for Operator<R> {
    type Output = Self;

    fn bitor(mut self, rhs: Self) -> Self {
        fn assign_next<R: RuleType>(op: &mut Operator<R>, next: Operator<R>) {
            if let Some(ref mut child) = op.next {
                assign_next(child, next);
            } else {
                op.next = Some(Box::new(next));
            }
        }

        assign_next(&mut self, rhs);
        self
    }
}

/// List of operators and precedences, which can perform [precedence climbing][1] on infix
/// expressions contained in a [`Pairs`]. The token pairs contained in the `Pairs` should start
/// with a *primary* pair and then alternate between an *operator* and a *primary*.
///
/// [1]: https://en.wikipedia.org/wiki/Operator-precedence_parser#Precedence_climbing_method
/// [`Pairs`]: ../iterators/struct.Pairs.html
#[derive(Debug)]
pub struct PrecClimber<R: Clone + 'static> {
    ops: Cow<'static, [(R, u32, Assoc)]>,
}

#[cfg(feature = "const_prec_climber")]
impl<R: Clone + 'static> PrecClimber<R> {
    /// Creates a new `PrecClimber` directly from a static slice of
    /// `(rule: Rule, precedence: u32, associativity: Assoc)` tuples.
    ///
    /// Precedence starts from `1`.  Entries don't have to be ordered in any way, but it's easier to read when
    /// sorted.
    ///
    /// # Examples
    ///
    /// ```
    /// # use pest::prec_climber::{Assoc, PrecClimber};
    /// # #[allow(non_camel_case_types)]
    /// # #[allow(dead_code)]
    /// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
    /// # enum Rule {
    /// #     plus,
    /// #     minus,
    /// #     times,
    /// #     divide,
    /// #     power
    /// # }
    /// static CLIMBER: PrecClimber<Rule> = PrecClimber::new_const(&[
    ///     (Rule::plus, 1, Assoc::Left), (Rule::minus, 1, Assoc::Left),
    ///     (Rule::times, 2, Assoc::Left), (Rule::divide, 2, Assoc::Left),
    ///     (Rule::power, 3, Assoc::Right)
    /// ]);
    /// ```
    pub const fn new_const(ops: &'static [(R, u32, Assoc)]) -> PrecClimber<R> {
        PrecClimber {
            ops: Cow::Borrowed(ops),
        }
    }
}

impl<R: RuleType> PrecClimber<R> {
    // find matching operator by `rule`
    fn get(&self, rule: &R) -> Option<(u32, Assoc)> {
        self.ops
            .iter()
            .find(|(r, _, _)| r == rule)
            .map(|(_, precedence, assoc)| (*precedence, *assoc))
    }

    /// Creates a new `PrecClimber` from the `Operator`s contained in `ops`. Every entry in the
    /// `Vec` has precedence *index + 1*. In order to have operators with same precedence, they need
    /// to be chained with `|` between them.
    ///
    /// # Examples
    ///
    /// ```
    /// # use pest::prec_climber::{Assoc, Operator, PrecClimber};
    /// # #[allow(non_camel_case_types)]
    /// # #[allow(dead_code)]
    /// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
    /// # enum Rule {
    /// #     plus,
    /// #     minus,
    /// #     times,
    /// #     divide,
    /// #     power
    /// # }
    /// PrecClimber::new(vec![
    ///     Operator::new(Rule::plus, Assoc::Left) | Operator::new(Rule::minus, Assoc::Left),
    ///     Operator::new(Rule::times, Assoc::Left) | Operator::new(Rule::divide, Assoc::Left),
    ///     Operator::new(Rule::power, Assoc::Right)
    /// ]);
    /// ```
    pub fn new(ops: Vec<Operator<R>>) -> PrecClimber<R> {
        let ops = ops
            .into_iter()
            .zip(1..)
            .fold(Vec::new(), |mut vec, (op, prec)| {
                let mut next = Some(op);

                while let Some(op) = next.take() {
                    let Operator {
                        rule,
                        assoc,
                        next: op_next,
                    } = op;

                    vec.push((rule, prec, assoc));
                    next = op_next.map(|op| *op);
                }

                vec
            });

        PrecClimber {
            ops: Cow::Owned(ops),
        }
    }

    /// Performs the precedence climbing algorithm on the `pairs` in a similar manner to map-reduce.
    /// *Primary* pairs are mapped with `primary` and then reduced to one single result with
    /// `infix`.
    ///
    /// # Panics
    ///
    /// Panics will occur when `pairs` is empty or when the alternating *primary*, *operator*,
    /// *primary* order is not respected.
    ///
    /// # Examples
    ///
    /// ```ignore
    /// let primary = |pair| {
    ///     consume(pair, climber)
    /// };
    /// let infix = |lhs: i32, op: Pair<Rule>, rhs: i32| {
    ///     match op.rule() {
    ///         Rule::plus => lhs + rhs,
    ///         Rule::minus => lhs - rhs,
    ///         Rule::times => lhs * rhs,
    ///         Rule::divide => lhs / rhs,
    ///         Rule::power => lhs.pow(rhs as u32),
    ///         _ => unreachable!()
    ///     }
    /// };
    ///
    /// let result = climber.climb(pairs, primary, infix);
    /// ```
    pub fn climb<'i, P, F, G, T>(&self, mut pairs: P, mut primary: F, mut infix: G) -> T
    where
        P: Iterator<Item = Pair<'i, R>>,
        F: FnMut(Pair<'i, R>) -> T,
        G: FnMut(T, Pair<'i, R>, T) -> T,
    {
        let lhs = primary(
            pairs
                .next()
                .expect("precedence climbing requires a non-empty Pairs"),
        );
        self.climb_rec(lhs, 0, &mut pairs.peekable(), &mut primary, &mut infix)
    }

    fn climb_rec<'i, P, F, G, T>(
        &self,
        mut lhs: T,
        min_prec: u32,
        pairs: &mut Peekable<P>,
        primary: &mut F,
        infix: &mut G,
    ) -> T
    where
        P: Iterator<Item = Pair<'i, R>>,
        F: FnMut(Pair<'i, R>) -> T,
        G: FnMut(T, Pair<'i, R>, T) -> T,
    {
        while pairs.peek().is_some() {
            let rule = pairs.peek().unwrap().as_rule();
            if let Some((prec, _)) = self.get(&rule) {
                if prec >= min_prec {
                    let op = pairs.next().unwrap();
                    let mut rhs = primary(pairs.next().expect(
                        "infix operator must be followed by \
                         a primary expression",
                    ));

                    while pairs.peek().is_some() {
                        let rule = pairs.peek().unwrap().as_rule();
                        if let Some((new_prec, assoc)) = self.get(&rule) {
                            if new_prec > prec || assoc == Assoc::Right && new_prec == prec {
                                rhs = self.climb_rec(rhs, new_prec, pairs, primary, infix);
                            } else {
                                break;
                            }
                        } else {
                            break;
                        }
                    }

                    lhs = infix(lhs, op, rhs);
                } else {
                    break;
                }
            } else {
                break;
            }
        }

        lhs
    }
}

Coverage Report

Created: 2025-02-21 07:11

Line	Count	Source (jump to first uncovered line)
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	0	pub fn new(rule: R, assoc: Assoc) -> Operator<R> {
141	0	Operator {
142	0	rule,
143	0	assoc,
144	0	next: None,
145	0	}
146	0	}
147		}
148
149		impl<R: RuleType> BitOr for Operator<R> {
150		type Output = Self;
151
152	0	fn bitor(mut self, rhs: Self) -> Self {
153	0	fn assign_next<R: RuleType>(op: &mut Operator<R>, next: Operator<R>) {
154	0	if let Some(ref mut child) = op.next {
155	0	assign_next(child, next);
156	0	} else {
157	0	op.next = Some(Box::new(next));
158	0	}
159	0	}
160
161	0	assign_next(&mut self, rhs);
162	0	self
163	0	}
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	0	fn get(&self, rule: &R) -> Option<(u32, Assoc)> {
215	0	self.ops
216	0	.iter()
217	0	.find(\|(r, _, _)\| r == rule)
218	0	.map(\|(_, precedence, assoc)\| (precedence, assoc))
219	0	}
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	0	pub fn new(ops: Vec<Operator<R>>) -> PrecClimber<R> {
246	0	let ops = ops
247	0	.into_iter()
248	0	.zip(1..)
249	0	.fold(Vec::new(), \|mut vec, (op, prec)\| {
250	0	let mut next = Some(op);
251
252	0	while let Some(op) = next.take() {
253	0	let Operator {
254	0	rule,
255	0	assoc,
256	0	next: op_next,
257	0	} = op;
258	0
259	0	vec.push((rule, prec, assoc));
260	0	next = op_next.map(\|op\| *op);
261		}
262
263	0	vec
264	0	});
265	0
266	0	PrecClimber {
267	0	ops: Cow::Owned(ops),
268	0	}
269	0	}
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	0	pub fn climb<'i, P, F, G, T>(&self, mut pairs: P, mut primary: F, mut infix: G) -> T
300	0	where
301	0	P: Iterator<Item = Pair<'i, R>>,
302	0	F: FnMut(Pair<'i, R>) -> T,
303	0	G: FnMut(T, Pair<'i, R>, T) -> T,
304	0	{
305	0	let lhs = primary(
306	0	pairs
307	0	.next()
308	0	.expect("precedence climbing requires a non-empty Pairs"),
309	0	);
310	0	self.climb_rec(lhs, 0, &mut pairs.peekable(), &mut primary, &mut infix)
311	0	}
312
313	0	fn climb_rec<'i, P, F, G, T>(
314	0	&self,
315	0	mut lhs: T,
316	0	min_prec: u32,
317	0	pairs: &mut Peekable<P>,
318	0	primary: &mut F,
319	0	infix: &mut G,
320	0	) -> T
321	0	where
322	0	P: Iterator<Item = Pair<'i, R>>,
323	0	F: FnMut(Pair<'i, R>) -> T,
324	0	G: FnMut(T, Pair<'i, R>, T) -> T,
325	0	{
326	0	while pairs.peek().is_some() {
327	0	let rule = pairs.peek().unwrap().as_rule();
328	0	if let Some((prec, _)) = self.get(&rule) {
329	0	if prec >= min_prec {
330	0	let op = pairs.next().unwrap();
331	0	let mut rhs = primary(pairs.next().expect(
332	0	"infix operator must be followed by \
333	0	a primary expression",
334	0	));
335
336	0	while pairs.peek().is_some() {
337	0	let rule = pairs.peek().unwrap().as_rule();
338	0	if let Some((new_prec, assoc)) = self.get(&rule) {
339	0	if new_prec > prec \|\| assoc == Assoc::Right && new_prec == prec {
340	0	rhs = self.climb_rec(rhs, new_prec, pairs, primary, infix);
341	0	} else {
342	0	break;
343		}
344		} else {
345	0	break;
346		}
347		}
348
349	0	lhs = infix(lhs, op, rhs);
350		} else {
351	0	break;
352		}
353		} else {
354	0	break;
355		}
356		}
357
358	0	lhs
359	0	}
360		}