vendor/pest/src/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 //! A `mod` containing constructs useful in infix operator parsing with the precedence climbing
  11 //! method.
  12
  13 use std::collections::HashMap;
  14 use std::iter::Peekable;
  15 use std::ops::BitOr;
  16
  17 use RuleType;
  18 use iterators::Pair;
  19
  20 /// An `enum` describing an `Operator`'s associativity.
  21 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
  22 pub enum Assoc {
  23     /// Left `Operator` associativity
  24     Left,
  25     /// Right `Operator` associativity
  26     Right
  27 }
  28
  29 /// A `struct` defining an infix operator used in [`PrecClimber`](struct.PrecClimber.html).
  30 #[derive(Debug)]
  31 pub struct Operator<R: RuleType> {
  32     rule: R,
  33     assoc: Assoc,
  34     next: Option<Box<Operator<R>>>
  35 }
  36
  37 impl<R: RuleType> Operator<R> {
  38     /// Creates a new `Operator` from a `Rule` and `Assoc`.
  39     ///
  40     /// # Examples
  41     ///
  42     /// ```
  43     /// # use pest::prec_climber::{Assoc, Operator};
  44     /// # #[allow(non_camel_case_types)]
  45     /// # #[allow(dead_code)]
  46     /// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
  47     /// # enum Rule {
  48     /// #     plus,
  49     /// #     minus
  50     /// # }
  51     /// Operator::new(Rule::plus, Assoc::Left) | Operator::new(Rule::minus, Assoc::Right);
  52     /// ```
  53     pub fn new(rule: R, assoc: Assoc) -> Operator<R> {
  54         Operator {
  55             rule,
  56             assoc,
  57             next: None
  58         }
  59     }
  60 }
  61
  62 impl<R: RuleType> BitOr for Operator<R> {
  63     type Output = Self;
  64
  65     fn bitor(mut self, rhs: Self) -> Self {
  66         fn assign_next<R: RuleType>(op: &mut Operator<R>, next: Operator<R>) {
  67             if let Some(ref mut child) = op.next {
  68                 assign_next(child, next);
  69             } else {
  70                 op.next = Some(Box::new(next));
  71             }
  72         }
  73
  74         assign_next(&mut self, rhs);
  75         self
  76     }
  77 }
  78
  79 /// A `struct` useful in order to perform [precedence climbing][1] on infix expressions contained in
  80 /// a [`Pairs`](../iterators/struct.Pairs.html). The token pairs contained in the `Pairs` should
  81 /// start with a *primary* pair and then alternate between an *operator* and a *primary*.
  82 ///
  83 /// [1]: https://en.wikipedia.org/wiki/Operator-precedence_parser#Precedence_climbing_method
  84 #[derive(Debug)]
  85 pub struct PrecClimber<R: RuleType> {
  86     ops: HashMap<R, (u32, Assoc)>
  87 }
  88
  89 impl<R: RuleType> PrecClimber<R> {
  90     /// Creates a new `PrecClimber` from the `Operator`s contained in `ops`. Every entry in the
  91     /// `Vec` has precedence *index + 1*. In order to have operators with same precedence, they need
  92     /// to be chained with `|` between them.
  93     ///
  94     /// # Examples
  95     ///
  96     /// ```
  97     /// # use pest::prec_climber::{Assoc, Operator, PrecClimber};
  98     /// # #[allow(non_camel_case_types)]
  99     /// # #[allow(dead_code)]
 100     /// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
 101     /// # enum Rule {
 102     /// #     plus,
 103     /// #     minus,
 104     /// #     times,
 105     /// #     divide,
 106     /// #     power
 107     /// # }
 108     /// PrecClimber::new(vec![
 109     ///     Operator::new(Rule::plus, Assoc::Left) | Operator::new(Rule::minus, Assoc::Left),
 110     ///     Operator::new(Rule::times, Assoc::Left) | Operator::new(Rule::divide, Assoc::Left),
 111     ///     Operator::new(Rule::power, Assoc::Right)
 112     /// ]);
 113     /// ```
 114     pub fn new(ops: Vec<Operator<R>>) -> PrecClimber<R> {
 115         let ops = ops.into_iter()
 116             .zip(1..)
 117             .fold(HashMap::new(), |mut map, (op, prec)| {
 118                 let mut next = Some(op);
 119
 120                 while let Some(op) = next.take() {
 121                     match op {
 122                         Operator {
 123                             rule,
 124                             assoc,
 125                             next: op_next
 126                         } => {
 127                             map.insert(rule, (prec, assoc));
 128                             next = op_next.map(|op| *op);
 129                         }
 130                     }
 131                 }
 132
 133                 map
 134             });
 135
 136         PrecClimber { ops }
 137     }
 138
 139     /// Performs the precedence climbing algorithm on the `pairs` in a similar manner to map-reduce.
 140     /// *Primary* pairs are mapped with `primary` and then reduced to one single result with
 141     /// `infix`.
 142     ///
 143     /// # Panics
 144     ///
 145     /// Panics will occur when `pairs` is empty or when the alternating *primary*, *operator*,
 146     /// *primary* order is not respected.
 147     ///
 148     /// # Examples
 149     ///
 150     /// ```ignore
 151     /// let primary = |pair| {
 152     ///     consume(pair, climber)
 153     /// };
 154     /// let infix = |lhs: i32, op: Pair<Rule>, rhs: i32| {
 155     ///     match op.rule() {
 156     ///         Rule::plus => lhs + rhs,
 157     ///         Rule::minus => lhs - rhs,
 158     ///         Rule::times => lhs * rhs,
 159     ///         Rule::divide => lhs / rhs,
 160     ///         Rule::power => lhs.pow(rhs as u32),
 161     ///         _ => unreachable!()
 162     ///     }
 163     /// };
 164     ///
 165     /// let result = climber.climb(pairs, primary, infix);
 166     /// ```
 167     pub fn climb<'i, P, F, G, T>(&self, mut pairs: P, mut primary: F, mut infix: G) -> T
 168     where
 169         P: Iterator<Item = Pair<'i, R>>,
 170         F: FnMut(Pair<'i, R>) -> T,
 171         G: FnMut(T, Pair<'i, R>, T) -> T
 172     {
 173         let lhs = primary(
 174             pairs
 175                 .next()
 176                 .expect("precedence climbing requires a non-empty Pairs")
 177         );
 178         self.climb_rec(lhs, 0, &mut pairs.peekable(), &mut primary, &mut infix)
 179     }
 180
 181     fn climb_rec<'i, P, F, G, T>(
 182         &self,
 183         mut lhs: T,
 184         min_prec: u32,
 185         pairs: &mut Peekable<P>,
 186         primary: &mut F,
 187         infix: &mut G
 188     ) -> T
 189     where
 190         P: Iterator<Item = Pair<'i, R>>,
 191         F: FnMut(Pair<'i, R>) -> T,
 192         G: FnMut(T, Pair<'i, R>, T) -> T
 193     {
 194         while pairs.peek().is_some() {
 195             let rule = pairs.peek().unwrap().as_rule();
 196             if let Some(&(prec, _)) = self.ops.get(&rule) {
 197                 if prec >= min_prec {
 198                     let op = pairs.next().unwrap();
 199                     let mut rhs = primary(pairs.next().expect(
 200                         "infix operator must be followed by \
 201                          a primary expression"
 202                     ));
 203
 204                     while pairs.peek().is_some() {
 205                         let rule = pairs.peek().unwrap().as_rule();
 206                         if let Some(&(new_prec, assoc)) = self.ops.get(&rule) {
 207                             if new_prec > prec || assoc == Assoc::Right && new_prec == prec {
 208                                 rhs = self.climb_rec(rhs, new_prec, pairs, primary, infix);
 209                             } else {
 210                                 break;
 211                             }
 212                         } else {
 213                             break;
 214                         }
 215                     }
 216
 217                     lhs = infix(lhs, op, rhs);
 218                 } else {
 219                     break;
 220                 }
 221             } else {
 222                 break;
 223             }
 224         }
 225
 226         lhs
 227     }
 228 }