Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 233 insertions, 0 deletions

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
+// <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 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<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: RuleType> {
+    ops: HashMap<R, (u32, Assoc)>,
+}
+
+impl<R: RuleType> PrecClimber<R> {
+    /// 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(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<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.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
+    }
+}