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

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

7 files changed, 908 insertions, 0 deletions

diff --git a/vendor/pest_meta/src/optimizer/concatenator.rs b/vendor/pest_meta/src/optimizer/concatenator.rs
new file mode 100644
index 000000000..e0aab7bc1
--- /dev/null
+++ b/vendor/pest_meta/src/optimizer/concatenator.rs
@@ -0,0 +1,34 @@
+// 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.
+
+use ast::*;
+
+pub fn concatenate(rule: Rule) -> Rule {
+    match rule {
+        Rule { name, ty, expr } => Rule {
+            name,
+            ty,
+            expr: expr.map_bottom_up(|expr| {
+                if ty == RuleType::Atomic {
+                    // TODO: Use box syntax when it gets stabilized.
+                    match expr {
+                        Expr::Seq(lhs, rhs) => match (*lhs, *rhs) {
+                            (Expr::Str(lhs), Expr::Str(rhs)) => Expr::Str(lhs + &rhs),
+                            (Expr::Insens(lhs), Expr::Insens(rhs)) => Expr::Insens(lhs + &rhs),
+                            (lhs, rhs) => Expr::Seq(Box::new(lhs), Box::new(rhs)),
+                        },
+                        expr => expr,
+                    }
+                } else {
+                    expr
+                }
+            }),
+        },
+    }
+}
diff --git a/vendor/pest_meta/src/optimizer/factorizer.rs b/vendor/pest_meta/src/optimizer/factorizer.rs
new file mode 100644
index 000000000..236289e14
--- /dev/null
+++ b/vendor/pest_meta/src/optimizer/factorizer.rs
@@ -0,0 +1,38 @@
+// 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.
+
+use ast::*;
+
+pub fn factor(rule: Rule) -> Rule {
+    match rule {
+        Rule { name, ty, expr } => Rule {
+            name,
+            ty,
+            expr: expr.map_top_down(|expr| {
+                // TODO: Use box syntax when it gets stabilized.
+                match expr {
+                    Expr::Choice(lhs, rhs) => match (*lhs, *rhs) {
+                        (Expr::Seq(l1, r1), Expr::Seq(l2, r2)) => {
+                            if l1 == l2 {
+                                Expr::Seq(l1, Box::new(Expr::Choice(r1, r2)))
+                            } else {
+                                Expr::Choice(
+                                    Box::new(Expr::Seq(l1, r1)),
+                                    Box::new(Expr::Seq(l2, r2)),
+                                )
+                            }
+                        }
+                        (lhs, rhs) => Expr::Choice(Box::new(lhs), Box::new(rhs)),
+                    },
+                    expr => expr,
+                }
+            }),
+        },
+    }
+}
diff --git a/vendor/pest_meta/src/optimizer/mod.rs b/vendor/pest_meta/src/optimizer/mod.rs
new file mode 100644
index 000000000..7013c43f9
--- /dev/null
+++ b/vendor/pest_meta/src/optimizer/mod.rs
@@ -0,0 +1,510 @@
+// 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.
+
+use ast::*;
+use std::collections::HashMap;
+
+#[cfg(test)]
+macro_rules! box_tree {
+    ( $node:ident( $(                      $child:ident( $($args:tt)* )     ),+ ) ) => (
+      $node      ( $( Box::new( box_tree!( $child      ( $($args   )* ) ) ) ),+ )
+    );
+    ($expr:expr) => ($expr);
+}
+
+mod concatenator;
+mod factorizer;
+mod restorer;
+mod rotater;
+mod skipper;
+mod unroller;
+
+pub fn optimize(rules: Vec<Rule>) -> Vec<OptimizedRule> {
+    let optimized: Vec<OptimizedRule> = rules
+        .into_iter()
+        .map(rotater::rotate)
+        .map(skipper::skip)
+        .map(unroller::unroll)
+        .map(concatenator::concatenate)
+        .map(factorizer::factor)
+        .map(rule_to_optimized_rule)
+        .collect();
+
+    let rules = to_hash_map(&optimized);
+    optimized
+        .into_iter()
+        .map(|rule| restorer::restore_on_err(rule, &rules))
+        .collect()
+}
+
+fn rule_to_optimized_rule(rule: Rule) -> OptimizedRule {
+    fn to_optimized(expr: Expr) -> OptimizedExpr {
+        match expr {
+            Expr::Str(string) => OptimizedExpr::Str(string),
+            Expr::Insens(string) => OptimizedExpr::Insens(string),
+            Expr::Range(start, end) => OptimizedExpr::Range(start, end),
+            Expr::Ident(ident) => OptimizedExpr::Ident(ident),
+            Expr::PeekSlice(start, end) => OptimizedExpr::PeekSlice(start, end),
+            Expr::PosPred(expr) => OptimizedExpr::PosPred(Box::new(to_optimized(*expr))),
+            Expr::NegPred(expr) => OptimizedExpr::NegPred(Box::new(to_optimized(*expr))),
+            Expr::Seq(lhs, rhs) => {
+                OptimizedExpr::Seq(Box::new(to_optimized(*lhs)), Box::new(to_optimized(*rhs)))
+            }
+            Expr::Choice(lhs, rhs) => {
+                OptimizedExpr::Choice(Box::new(to_optimized(*lhs)), Box::new(to_optimized(*rhs)))
+            }
+            Expr::Opt(expr) => OptimizedExpr::Opt(Box::new(to_optimized(*expr))),
+            Expr::Rep(expr) => OptimizedExpr::Rep(Box::new(to_optimized(*expr))),
+            Expr::Skip(strings) => OptimizedExpr::Skip(strings),
+            Expr::Push(expr) => OptimizedExpr::Push(Box::new(to_optimized(*expr))),
+            Expr::RepOnce(_)
+            | Expr::RepExact(..)
+            | Expr::RepMin(..)
+            | Expr::RepMax(..)
+            | Expr::RepMinMax(..) => unreachable!("No valid transformation to OptimizedRule"),
+        }
+    }
+
+    OptimizedRule {
+        name: rule.name,
+        ty: rule.ty,
+        expr: to_optimized(rule.expr),
+    }
+}
+
+fn to_hash_map(rules: &[OptimizedRule]) -> HashMap<String, OptimizedExpr> {
+    rules
+        .iter()
+        .map(|r| (r.name.clone(), r.expr.clone()))
+        .collect()
+}
+
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct OptimizedRule {
+    pub name: String,
+    pub ty: RuleType,
+    pub expr: OptimizedExpr,
+}
+
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum OptimizedExpr {
+    Str(String),
+    Insens(String),
+    Range(String, String),
+    Ident(String),
+    PeekSlice(i32, Option<i32>),
+    PosPred(Box<OptimizedExpr>),
+    NegPred(Box<OptimizedExpr>),
+    Seq(Box<OptimizedExpr>, Box<OptimizedExpr>),
+    Choice(Box<OptimizedExpr>, Box<OptimizedExpr>),
+    Opt(Box<OptimizedExpr>),
+    Rep(Box<OptimizedExpr>),
+    Skip(Vec<String>),
+    Push(Box<OptimizedExpr>),
+    RestoreOnErr(Box<OptimizedExpr>),
+}
+
+impl OptimizedExpr {
+    pub fn iter_top_down(&self) -> OptimizedExprTopDownIterator {
+        OptimizedExprTopDownIterator::new(self)
+    }
+
+    pub fn map_top_down<F>(self, mut f: F) -> OptimizedExpr
+    where
+        F: FnMut(OptimizedExpr) -> OptimizedExpr,
+    {
+        fn map_internal<F>(expr: OptimizedExpr, f: &mut F) -> OptimizedExpr
+        where
+            F: FnMut(OptimizedExpr) -> OptimizedExpr,
+        {
+            let expr = f(expr);
+
+            match expr {
+                // TODO: Use box syntax when it gets stabilized.
+                OptimizedExpr::PosPred(expr) => {
+                    let mapped = Box::new(map_internal(*expr, f));
+                    OptimizedExpr::PosPred(mapped)
+                }
+                OptimizedExpr::NegPred(expr) => {
+                    let mapped = Box::new(map_internal(*expr, f));
+                    OptimizedExpr::NegPred(mapped)
+                }
+                OptimizedExpr::Seq(lhs, rhs) => {
+                    let mapped_lhs = Box::new(map_internal(*lhs, f));
+                    let mapped_rhs = Box::new(map_internal(*rhs, f));
+                    OptimizedExpr::Seq(mapped_lhs, mapped_rhs)
+                }
+                OptimizedExpr::Choice(lhs, rhs) => {
+                    let mapped_lhs = Box::new(map_internal(*lhs, f));
+                    let mapped_rhs = Box::new(map_internal(*rhs, f));
+                    OptimizedExpr::Choice(mapped_lhs, mapped_rhs)
+                }
+                OptimizedExpr::Rep(expr) => {
+                    let mapped = Box::new(map_internal(*expr, f));
+                    OptimizedExpr::Rep(mapped)
+                }
+                OptimizedExpr::Opt(expr) => {
+                    let mapped = Box::new(map_internal(*expr, f));
+                    OptimizedExpr::Opt(mapped)
+                }
+                OptimizedExpr::Push(expr) => {
+                    let mapped = Box::new(map_internal(*expr, f));
+                    OptimizedExpr::Push(mapped)
+                }
+                expr => expr,
+            }
+        }
+
+        map_internal(self, &mut f)
+    }
+
+    pub fn map_bottom_up<F>(self, mut f: F) -> OptimizedExpr
+    where
+        F: FnMut(OptimizedExpr) -> OptimizedExpr,
+    {
+        fn map_internal<F>(expr: OptimizedExpr, f: &mut F) -> OptimizedExpr
+        where
+            F: FnMut(OptimizedExpr) -> OptimizedExpr,
+        {
+            let mapped = match expr {
+                OptimizedExpr::PosPred(expr) => {
+                    // TODO: Use box syntax when it gets stabilized.
+                    let mapped = Box::new(map_internal(*expr, f));
+                    OptimizedExpr::PosPred(mapped)
+                }
+                OptimizedExpr::NegPred(expr) => {
+                    let mapped = Box::new(map_internal(*expr, f));
+                    OptimizedExpr::NegPred(mapped)
+                }
+                OptimizedExpr::Seq(lhs, rhs) => {
+                    let mapped_lhs = Box::new(map_internal(*lhs, f));
+                    let mapped_rhs = Box::new(map_internal(*rhs, f));
+                    OptimizedExpr::Seq(mapped_lhs, mapped_rhs)
+                }
+                OptimizedExpr::Choice(lhs, rhs) => {
+                    let mapped_lhs = Box::new(map_internal(*lhs, f));
+                    let mapped_rhs = Box::new(map_internal(*rhs, f));
+                    OptimizedExpr::Choice(mapped_lhs, mapped_rhs)
+                }
+                OptimizedExpr::Rep(expr) => {
+                    let mapped = Box::new(map_internal(*expr, f));
+                    OptimizedExpr::Rep(mapped)
+                }
+                OptimizedExpr::Opt(expr) => {
+                    let mapped = Box::new(map_internal(*expr, f));
+                    OptimizedExpr::Opt(mapped)
+                }
+                OptimizedExpr::Push(expr) => {
+                    let mapped = Box::new(map_internal(*expr, f));
+                    OptimizedExpr::Push(mapped)
+                }
+                expr => expr,
+            };
+
+            f(mapped)
+        }
+
+        map_internal(self, &mut f)
+    }
+}
+
+pub struct OptimizedExprTopDownIterator {
+    current: Option<OptimizedExpr>,
+    next: Option<OptimizedExpr>,
+    right_branches: Vec<OptimizedExpr>,
+}
+
+impl OptimizedExprTopDownIterator {
+    pub fn new(expr: &OptimizedExpr) -> Self {
+        let mut iter = OptimizedExprTopDownIterator {
+            current: None,
+            next: None,
+            right_branches: vec![],
+        };
+        iter.iterate_expr(expr.clone());
+        iter
+    }
+
+    fn iterate_expr(&mut self, expr: OptimizedExpr) {
+        self.current = Some(expr.clone());
+        match expr {
+            OptimizedExpr::Seq(lhs, rhs) => {
+                self.right_branches.push(*rhs);
+                self.next = Some(*lhs);
+            }
+            OptimizedExpr::Choice(lhs, rhs) => {
+                self.right_branches.push(*rhs);
+                self.next = Some(*lhs);
+            }
+            OptimizedExpr::PosPred(expr)
+            | OptimizedExpr::NegPred(expr)
+            | OptimizedExpr::Rep(expr)
+            | OptimizedExpr::Opt(expr)
+            | OptimizedExpr::Push(expr) => {
+                self.next = Some(*expr);
+            }
+            _ => {
+                self.next = None;
+            }
+        }
+    }
+}
+
+impl Iterator for OptimizedExprTopDownIterator {
+    type Item = OptimizedExpr;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let result = self.current.take();
+
+        if let Some(expr) = self.next.take() {
+            self.iterate_expr(expr);
+        } else if let Some(expr) = self.right_branches.pop() {
+            self.iterate_expr(expr);
+        }
+
+        result
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn rotate() {
+        let rules = {
+            use ast::Expr::*;
+            vec![Rule {
+                name: "rule".to_owned(),
+                ty: RuleType::Normal,
+                expr: box_tree!(Choice(
+                    Choice(
+                        Choice(Str(String::from("a")), Str(String::from("b"))),
+                        Str(String::from("c"))
+                    ),
+                    Str(String::from("d"))
+                )),
+            }]
+        };
+        let rotated = {
+            use optimizer::OptimizedExpr::*;
+            vec![OptimizedRule {
+                name: "rule".to_owned(),
+                ty: RuleType::Normal,
+                expr: box_tree!(Choice(
+                    Str(String::from("a")),
+                    Choice(
+                        Str(String::from("b")),
+                        Choice(Str(String::from("c")), Str(String::from("d")))
+                    )
+                )),
+            }]
+        };
+
+        assert_eq!(optimize(rules), rotated);
+    }
+
+    #[test]
+    fn skip() {
+        let rules = {
+            use ast::Expr::*;
+            vec![Rule {
+                name: "rule".to_owned(),
+                ty: RuleType::Atomic,
+                expr: box_tree!(Rep(Seq(
+                    NegPred(Choice(Str(String::from("a")), Str(String::from("b")))),
+                    Ident(String::from("ANY"))
+                ))),
+            }]
+        };
+        let skipped = vec![OptimizedRule {
+            name: "rule".to_owned(),
+            ty: RuleType::Atomic,
+            expr: OptimizedExpr::Skip(vec![String::from("a"), String::from("b")]),
+        }];
+
+        assert_eq!(optimize(rules), skipped);
+    }
+
+    #[test]
+    fn concat_strings() {
+        let rules = {
+            use ast::Expr::*;
+            vec![Rule {
+                name: "rule".to_owned(),
+                ty: RuleType::Atomic,
+                expr: box_tree!(Seq(
+                    Seq(Str(String::from("a")), Str(String::from("b"))),
+                    Seq(Str(String::from("c")), Str(String::from("d")))
+                )),
+            }]
+        };
+        let concatenated = vec![OptimizedRule {
+            name: "rule".to_owned(),
+            ty: RuleType::Atomic,
+            expr: OptimizedExpr::Str(String::from("abcd")),
+        }];
+
+        assert_eq!(optimize(rules), concatenated);
+    }
+
+    #[test]
+    fn unroll_loop_exact() {
+        let rules = vec![Rule {
+            name: "rule".to_owned(),
+            ty: RuleType::Atomic,
+            expr: Expr::RepExact(Box::new(Expr::Ident(String::from("a"))), 3),
+        }];
+        let unrolled = {
+            use optimizer::OptimizedExpr::*;
+            vec![OptimizedRule {
+                name: "rule".to_owned(),
+                ty: RuleType::Atomic,
+                expr: box_tree!(Seq(
+                    Ident(String::from("a")),
+                    Seq(Ident(String::from("a")), Ident(String::from("a")))
+                )),
+            }]
+        };
+
+        assert_eq!(optimize(rules), unrolled);
+    }
+
+    #[test]
+    fn unroll_loop_max() {
+        let rules = vec![Rule {
+            name: "rule".to_owned(),
+            ty: RuleType::Atomic,
+            expr: Expr::RepMax(Box::new(Expr::Str("a".to_owned())), 3),
+        }];
+        let unrolled = {
+            use optimizer::OptimizedExpr::*;
+            vec![OptimizedRule {
+                name: "rule".to_owned(),
+                ty: RuleType::Atomic,
+                expr: box_tree!(Seq(
+                    Opt(Str(String::from("a"))),
+                    Seq(Opt(Str(String::from("a"))), Opt(Str(String::from("a"))))
+                )),
+            }]
+        };
+
+        assert_eq!(optimize(rules), unrolled);
+    }
+
+    #[test]
+    fn unroll_loop_min() {
+        let rules = vec![Rule {
+            name: "rule".to_owned(),
+            ty: RuleType::Atomic,
+            expr: Expr::RepMin(Box::new(Expr::Str("a".to_owned())), 2),
+        }];
+        let unrolled = {
+            use optimizer::OptimizedExpr::*;
+            vec![OptimizedRule {
+                name: "rule".to_owned(),
+                ty: RuleType::Atomic,
+                expr: box_tree!(Seq(
+                    Str(String::from("a")),
+                    Seq(Str(String::from("a")), Rep(Str(String::from("a"))))
+                )),
+            }]
+        };
+
+        assert_eq!(optimize(rules), unrolled);
+    }
+
+    #[test]
+    fn unroll_loop_min_max() {
+        let rules = vec![Rule {
+            name: "rule".to_owned(),
+            ty: RuleType::Atomic,
+            expr: Expr::RepMinMax(Box::new(Expr::Str("a".to_owned())), 2, 3),
+        }];
+        let unrolled = {
+            use optimizer::OptimizedExpr::*;
+            vec![OptimizedRule {
+                name: "rule".to_owned(),
+                ty: RuleType::Atomic,
+                /* TODO possible room for improvement here:
+                 * if the sequences were rolled out in the opposite
+                 * order, we could further optimize the strings
+                 * in cases like this.
+                Str(String::from(("aa")),
+                Opt(Str(String::from("a")))
+                */
+                expr: box_tree!(Seq(
+                    Str(String::from("a")),
+                    Seq(Str(String::from("a")), Opt(Str(String::from("a"))))
+                )),
+            }]
+        };
+
+        assert_eq!(optimize(rules), unrolled);
+    }
+
+    #[test]
+    fn concat_insensitive_strings() {
+        let rules = {
+            use ast::Expr::*;
+            vec![Rule {
+                name: "rule".to_owned(),
+                ty: RuleType::Atomic,
+                expr: box_tree!(Seq(
+                    Seq(Insens(String::from("a")), Insens(String::from("b"))),
+                    Seq(Insens(String::from("c")), Insens(String::from("d")))
+                )),
+            }]
+        };
+        let concatenated = vec![OptimizedRule {
+            name: "rule".to_owned(),
+            ty: RuleType::Atomic,
+            expr: OptimizedExpr::Insens(String::from("abcd")),
+        }];
+
+        assert_eq!(optimize(rules), concatenated);
+    }
+
+    #[test]
+    fn long_common_sequence() {
+        let rules = {
+            use ast::Expr::*;
+            vec![Rule {
+                name: "rule".to_owned(),
+                ty: RuleType::Silent,
+                expr: box_tree!(Choice(
+                    Seq(
+                        Ident(String::from("a")),
+                        Seq(Ident(String::from("b")), Ident(String::from("c")))
+                    ),
+                    Seq(
+                        Seq(Ident(String::from("a")), Ident(String::from("b"))),
+                        Ident(String::from("d"))
+                    )
+                )),
+            }]
+        };
+        let optimized = {
+            use optimizer::OptimizedExpr::*;
+            vec![OptimizedRule {
+                name: "rule".to_owned(),
+                ty: RuleType::Silent,
+                expr: box_tree!(Seq(
+                    Ident(String::from("a")),
+                    Seq(
+                        Ident(String::from("b")),
+                        Choice(Ident(String::from("c")), Ident(String::from("d")))
+                    )
+                )),
+            }]
+        };
+
+        assert_eq!(optimize(rules), optimized);
+    }
+}
diff --git a/vendor/pest_meta/src/optimizer/restorer.rs b/vendor/pest_meta/src/optimizer/restorer.rs
new file mode 100644
index 000000000..34a710eab
--- /dev/null
+++ b/vendor/pest_meta/src/optimizer/restorer.rs
@@ -0,0 +1,157 @@
+// 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.
+use std::collections::HashMap;
+
+use optimizer::*;
+
+pub fn restore_on_err(
+    rule: OptimizedRule,
+    rules: &HashMap<String, OptimizedExpr>,
+) -> OptimizedRule {
+    match rule {
+        OptimizedRule { name, ty, expr } => {
+            let expr = expr.map_bottom_up(|expr| wrap_branching_exprs(expr, rules));
+
+            OptimizedRule { name, ty, expr }
+        }
+    }
+}
+
+fn wrap_branching_exprs(
+    expr: OptimizedExpr,
+    rules: &HashMap<String, OptimizedExpr>,
+) -> OptimizedExpr {
+    match expr {
+        OptimizedExpr::Opt(expr) => {
+            if child_modifies_state(&expr, rules, &mut HashMap::new()) {
+                OptimizedExpr::Opt(Box::new(OptimizedExpr::RestoreOnErr(expr)))
+            } else {
+                OptimizedExpr::Opt(expr)
+            }
+        }
+        OptimizedExpr::Choice(lhs, rhs) => {
+            let wrapped_lhs = if child_modifies_state(&lhs, rules, &mut HashMap::new()) {
+                Box::new(OptimizedExpr::RestoreOnErr(lhs))
+            } else {
+                lhs
+            };
+            let wrapped_rhs = if child_modifies_state(&rhs, rules, &mut HashMap::new()) {
+                Box::new(OptimizedExpr::RestoreOnErr(rhs))
+            } else {
+                rhs
+            };
+            OptimizedExpr::Choice(wrapped_lhs, wrapped_rhs)
+        }
+        OptimizedExpr::Rep(expr) => {
+            if child_modifies_state(&expr, rules, &mut HashMap::new()) {
+                OptimizedExpr::Rep(Box::new(OptimizedExpr::RestoreOnErr(expr)))
+            } else {
+                OptimizedExpr::Rep(expr)
+            }
+        }
+        _ => expr,
+    }
+}
+
+fn child_modifies_state(
+    expr: &OptimizedExpr,
+    rules: &HashMap<String, OptimizedExpr>,
+    cache: &mut HashMap<String, Option<bool>>,
+) -> bool {
+    expr.iter_top_down().any(|expr| match expr {
+        OptimizedExpr::Push(_) => true,
+        OptimizedExpr::Ident(ref name) if name == "DROP" => true,
+        OptimizedExpr::Ident(ref name) if name == "POP" => true,
+        OptimizedExpr::Ident(ref name) => match cache.get(name).cloned() {
+            Some(option) => match option {
+                Some(cached) => cached,
+                None => {
+                    cache.insert(name.to_owned(), Some(false));
+                    false
+                }
+            },
+            None => {
+                cache.insert(name.to_owned(), None);
+
+                let result = match rules.get(name) {
+                    Some(expr) => child_modifies_state(expr, rules, cache),
+                    None => false,
+                };
+
+                cache.insert(name.to_owned(), Some(result));
+
+                result
+            }
+        },
+        _ => false,
+    })
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use optimizer::OptimizedExpr::*;
+
+    #[test]
+    fn restore_no_stack_children() {
+        let rules = vec![OptimizedRule {
+            name: "rule".to_owned(),
+            ty: RuleType::Normal,
+            expr: box_tree!(Opt(Str("a".to_string()))),
+        }];
+
+        assert_eq!(
+            restore_on_err(rules[0].clone(), &to_hash_map(&rules)),
+            rules[0].clone()
+        );
+    }
+
+    #[test]
+    fn restore_with_child_stack_ops() {
+        let rules = vec![OptimizedRule {
+            name: "rule".to_owned(),
+            ty: RuleType::Normal,
+            expr: box_tree!(Rep(Push(Str("a".to_string())))),
+        }];
+
+        let restored = OptimizedRule {
+            name: "rule".to_owned(),
+            ty: RuleType::Normal,
+            expr: box_tree!(Rep(RestoreOnErr(Push(Str("a".to_string()))))),
+        };
+
+        assert_eq!(
+            restore_on_err(rules[0].clone(), &to_hash_map(&rules)),
+            restored
+        );
+    }
+
+    #[test]
+    fn restore_choice_branch_with_and_branch_without() {
+        let rules = vec![OptimizedRule {
+            name: "rule".to_owned(),
+            ty: RuleType::Normal,
+            expr: box_tree!(Choice(Push(Str("a".to_string())), Str("a".to_string()))),
+        }];
+
+        let restored = OptimizedRule {
+            name: "rule".to_owned(),
+            ty: RuleType::Normal,
+            expr: box_tree!(Choice(
+                RestoreOnErr(Push(Str("a".to_string()))),
+                Str("a".to_string())
+            )),
+        };
+
+        assert_eq!(
+            restore_on_err(rules[0].clone(), &to_hash_map(&rules)),
+            restored
+        );
+    }
+}
diff --git a/vendor/pest_meta/src/optimizer/rotater.rs b/vendor/pest_meta/src/optimizer/rotater.rs
new file mode 100644
index 000000000..3588738ad
--- /dev/null
+++ b/vendor/pest_meta/src/optimizer/rotater.rs
@@ -0,0 +1,45 @@
+// 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.
+
+use ast::*;
+
+pub fn rotate(rule: Rule) -> Rule {
+    fn rotate_internal(expr: Expr) -> Expr {
+        match expr {
+            // TODO: Use box syntax when it gets stabilized.
+            Expr::Seq(lhs, rhs) => {
+                let lhs = *lhs;
+                match lhs {
+                    Expr::Seq(ll, lr) => {
+                        rotate_internal(Expr::Seq(ll, Box::new(Expr::Seq(lr, rhs))))
+                    }
+                    lhs => Expr::Seq(Box::new(lhs), rhs),
+                }
+            }
+            Expr::Choice(lhs, rhs) => {
+                let lhs = *lhs;
+                match lhs {
+                    Expr::Choice(ll, lr) => {
+                        rotate_internal(Expr::Choice(ll, Box::new(Expr::Choice(lr, rhs))))
+                    }
+                    lhs => Expr::Choice(Box::new(lhs), rhs),
+                }
+            }
+            expr => expr,
+        }
+    }
+
+    match rule {
+        Rule { name, ty, expr } => Rule {
+            name,
+            ty,
+            expr: expr.map_top_down(rotate_internal),
+        },
+    }
+}
diff --git a/vendor/pest_meta/src/optimizer/skipper.rs b/vendor/pest_meta/src/optimizer/skipper.rs
new file mode 100644
index 000000000..f55edc06f
--- /dev/null
+++ b/vendor/pest_meta/src/optimizer/skipper.rs
@@ -0,0 +1,57 @@
+// 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.
+
+use ast::*;
+
+pub fn skip(rule: Rule) -> Rule {
+    fn populate_choices(expr: Expr, mut choices: Vec<String>) -> Option<Expr> {
+        match expr {
+            Expr::Choice(lhs, rhs) => {
+                if let Expr::Str(string) = *lhs {
+                    choices.push(string);
+                    populate_choices(*rhs, choices)
+                } else {
+                    None
+                }
+            }
+            Expr::Str(string) => {
+                choices.push(string);
+                Some(Expr::Skip(choices))
+            }
+            _ => None,
+        }
+    }
+
+    match rule {
+        Rule { name, ty, expr } => Rule {
+            name,
+            ty,
+            expr: if ty == RuleType::Atomic {
+                expr.map_top_down(|expr| {
+                    // TODO: Use box syntax when it gets stabilized.
+                    if let Expr::Rep(expr) = expr.clone() {
+                        if let Expr::Seq(lhs, rhs) = *expr.clone() {
+                            if let (Expr::NegPred(expr), Expr::Ident(ident)) = (*lhs, *rhs) {
+                                if ident == "ANY" {
+                                    if let Some(expr) = populate_choices(*expr, vec![]) {
+                                        return expr;
+                                    }
+                                }
+                            }
+                        }
+                    };
+
+                    expr
+                })
+            } else {
+                expr
+            },
+        },
+    }
+}
diff --git a/vendor/pest_meta/src/optimizer/unroller.rs b/vendor/pest_meta/src/optimizer/unroller.rs
new file mode 100644
index 000000000..fff17336d
--- /dev/null
+++ b/vendor/pest_meta/src/optimizer/unroller.rs
@@ -0,0 +1,67 @@
+// 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.
+
+use ast::*;
+
+pub fn unroll(rule: Rule) -> Rule {
+    match rule {
+        Rule { name, ty, expr } => Rule {
+            name,
+            ty,
+            expr: expr.map_bottom_up(|expr| match expr {
+                Expr::RepOnce(expr) => Expr::Seq(expr.clone(), Box::new(Expr::Rep(expr))),
+                Expr::RepExact(expr, num) => (1..num + 1)
+                    .map(|_| *expr.clone())
+                    .rev()
+                    .fold(None, |rep, expr| match rep {
+                        None => Some(expr),
+                        Some(rep) => Some(Expr::Seq(Box::new(expr), Box::new(rep))),
+                    })
+                    .unwrap(),
+                Expr::RepMin(expr, min) => (1..min + 2)
+                    .map(|i| {
+                        if i <= min {
+                            *expr.clone()
+                        } else {
+                            Expr::Rep(expr.clone())
+                        }
+                    })
+                    .rev()
+                    .fold(None, |rep, expr| match rep {
+                        None => Some(expr),
+                        Some(rep) => Some(Expr::Seq(Box::new(expr), Box::new(rep))),
+                    })
+                    .unwrap(),
+                Expr::RepMax(expr, max) => (1..max + 1)
+                    .map(|_| Expr::Opt(expr.clone()))
+                    .rev()
+                    .fold(None, |rep, expr| match rep {
+                        None => Some(expr),
+                        Some(rep) => Some(Expr::Seq(Box::new(expr), Box::new(rep))),
+                    })
+                    .unwrap(),
+                Expr::RepMinMax(expr, min, max) => (1..max + 1)
+                    .map(|i| {
+                        if i <= min {
+                            *expr.clone()
+                        } else {
+                            Expr::Opt(expr.clone())
+                        }
+                    })
+                    .rev()
+                    .fold(None, |rep, expr| match rep {
+                        None => Some(expr),
+                        Some(rep) => Some(Expr::Seq(Box::new(expr), Box::new(rep))),
+                    })
+                    .unwrap(),
+                expr => expr,
+            }),
+        },
+    }
+}