summaryrefslogtreecommitdiffstats
path: root/vendor/pest_meta/src/optimizer
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/pest_meta/src/optimizer')
-rw-r--r--vendor/pest_meta/src/optimizer/concatenator.rs34
-rw-r--r--vendor/pest_meta/src/optimizer/factorizer.rs38
-rw-r--r--vendor/pest_meta/src/optimizer/mod.rs510
-rw-r--r--vendor/pest_meta/src/optimizer/restorer.rs157
-rw-r--r--vendor/pest_meta/src/optimizer/rotater.rs45
-rw-r--r--vendor/pest_meta/src/optimizer/skipper.rs57
-rw-r--r--vendor/pest_meta/src/optimizer/unroller.rs67
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,
+ }),
+ },
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-04 17:34:42 +0000