From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/pest/src/prec_climber.rs | 233 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 233 insertions(+) create mode 100644 vendor/pest/src/prec_climber.rs (limited to 'vendor/pest/src/prec_climber.rs') diff --git a/vendor/pest/src/prec_climber.rs b/vendor/pest/src/prec_climber.rs new file mode 100644 index 000000000..d8bf0a08a --- /dev/null +++ b/vendor/pest/src/prec_climber.rs @@ -0,0 +1,233 @@ +// pest. The Elegant Parser +// Copyright (c) 2018 Dragoș Tiselice +// +// Licensed under the Apache License, Version 2.0 +// or the MIT +// license , 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 std::collections::HashMap; +use std::iter::Peekable; +use std::ops::BitOr; + +use iterators::Pair; +use RuleType; + +/// 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 { + rule: R, + assoc: Assoc, + next: Option>>, +} + +impl Operator { + /// 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 { + Operator { + rule, + assoc, + next: None, + } + } +} + +impl BitOr for Operator { + type Output = Self; + + fn bitor(mut self, rhs: Self) -> Self { + fn assign_next(op: &mut Operator, next: Operator) { + 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 { + ops: HashMap, +} + +impl PrecClimber { + /// 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>) -> PrecClimber { + let ops = ops + .into_iter() + .zip(1..) + .fold(HashMap::new(), |mut map, (op, prec)| { + let mut next = Some(op); + + while let Some(op) = next.take() { + match op { + Operator { + rule, + assoc, + next: op_next, + } => { + map.insert(rule, (prec, assoc)); + next = op_next.map(|op| *op); + } + } + } + + map + }); + + PrecClimber { 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, 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>, + 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

, + primary: &mut F, + infix: &mut G, + ) -> T + where + P: Iterator>, + 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.ops.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.ops.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 + } +} -- cgit v1.2.3