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_meta/src/optimizer/concatenator.rs | 34 ++ vendor/pest_meta/src/optimizer/factorizer.rs | 38 ++ vendor/pest_meta/src/optimizer/mod.rs | 510 +++++++++++++++++++++++++ vendor/pest_meta/src/optimizer/restorer.rs | 157 ++++++++ vendor/pest_meta/src/optimizer/rotater.rs | 45 +++ vendor/pest_meta/src/optimizer/skipper.rs | 57 +++ vendor/pest_meta/src/optimizer/unroller.rs | 67 ++++ 7 files changed, 908 insertions(+) create mode 100644 vendor/pest_meta/src/optimizer/concatenator.rs create mode 100644 vendor/pest_meta/src/optimizer/factorizer.rs create mode 100644 vendor/pest_meta/src/optimizer/mod.rs create mode 100644 vendor/pest_meta/src/optimizer/restorer.rs create mode 100644 vendor/pest_meta/src/optimizer/rotater.rs create mode 100644 vendor/pest_meta/src/optimizer/skipper.rs create mode 100644 vendor/pest_meta/src/optimizer/unroller.rs (limited to 'vendor/pest_meta/src/optimizer') 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 +// 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. + +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 +// 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. + +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 +// 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. + +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) -> Vec { + let optimized: Vec = 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 { + 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), + PosPred(Box), + NegPred(Box), + Seq(Box, Box), + Choice(Box, Box), + Opt(Box), + Rep(Box), + Skip(Vec), + Push(Box), + RestoreOnErr(Box), +} + +impl OptimizedExpr { + pub fn iter_top_down(&self) -> OptimizedExprTopDownIterator { + OptimizedExprTopDownIterator::new(self) + } + + pub fn map_top_down(self, mut f: F) -> OptimizedExpr + where + F: FnMut(OptimizedExpr) -> OptimizedExpr, + { + fn map_internal(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(self, mut f: F) -> OptimizedExpr + where + F: FnMut(OptimizedExpr) -> OptimizedExpr, + { + fn map_internal(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, + next: Option, + right_branches: Vec, +} + +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 { + 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 +// 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. +use std::collections::HashMap; + +use optimizer::*; + +pub fn restore_on_err( + rule: OptimizedRule, + rules: &HashMap, +) -> 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, +) -> 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, + cache: &mut HashMap>, +) -> 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 +// 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. + +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 +// 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. + +use ast::*; + +pub fn skip(rule: Rule) -> Rule { + fn populate_choices(expr: Expr, mut choices: Vec) -> Option { + 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 +// 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. + +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, + }), + }, + } +} -- cgit v1.2.3