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.rs39
-rw-r--r--vendor/pest_meta/src/optimizer/factorizer.rs61
-rw-r--r--vendor/pest_meta/src/optimizer/lister.rs42
-rw-r--r--vendor/pest_meta/src/optimizer/mod.rs104
-rw-r--r--vendor/pest_meta/src/optimizer/restorer.rs14
-rw-r--r--vendor/pest_meta/src/optimizer/rotater.rs13
-rw-r--r--vendor/pest_meta/src/optimizer/skipper.rs39
-rw-r--r--vendor/pest_meta/src/optimizer/unroller.rs107
8 files changed, 273 insertions, 146 deletions
diff --git a/vendor/pest_meta/src/optimizer/concatenator.rs b/vendor/pest_meta/src/optimizer/concatenator.rs
index e0aab7bc1..31d3aa531 100644
--- a/vendor/pest_meta/src/optimizer/concatenator.rs
+++ b/vendor/pest_meta/src/optimizer/concatenator.rs
@@ -7,28 +7,27 @@
// option. All files in the project carrying such notice may not be copied,
// modified, or distributed except according to those terms.
-use ast::*;
+use crate::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
+ let Rule { name, ty, expr } = rule;
+ 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
index 236289e14..5481870bf 100644
--- a/vendor/pest_meta/src/optimizer/factorizer.rs
+++ b/vendor/pest_meta/src/optimizer/factorizer.rs
@@ -7,32 +7,45 @@
// option. All files in the project carrying such notice may not be copied,
// modified, or distributed except according to those terms.
-use ast::*;
+use crate::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)),
- )
- }
+ let Rule { name, ty, expr } = rule;
+ 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,
- }
- }),
- },
+ }
+ // Converts `(rule ~ rest) | rule` to `rule ~ rest?`, avoiding trying to match `rule` twice.
+ (Expr::Seq(l1, l2), r) => {
+ if *l1 == r {
+ Expr::Seq(l1, Box::new(Expr::Opt(l2)))
+ } else {
+ Expr::Choice(Box::new(Expr::Seq(l1, l2)), Box::new(r))
+ }
+ }
+ // Converts `rule | (rule ~ rest)` to `rule` since `(rule ~ rest)`
+ // will never match if `rule` didn't.
+ (l, Expr::Seq(r1, r2)) => {
+ if l == *r1 {
+ l
+ } else {
+ Expr::Choice(Box::new(l), Box::new(Expr::Seq(r1, r2)))
+ }
+ }
+ (lhs, rhs) => Expr::Choice(Box::new(lhs), Box::new(rhs)),
+ },
+ expr => expr,
+ }
+ }),
}
}
diff --git a/vendor/pest_meta/src/optimizer/lister.rs b/vendor/pest_meta/src/optimizer/lister.rs
new file mode 100644
index 000000000..e19885032
--- /dev/null
+++ b/vendor/pest_meta/src/optimizer/lister.rs
@@ -0,0 +1,42 @@
+// 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 crate::ast::*;
+
+pub fn list(rule: Rule) -> Rule {
+ let Rule { name, ty, expr } = rule;
+ Rule {
+ name,
+ ty,
+ expr: expr.map_bottom_up(|expr| {
+ // TODO: Use box syntax when it gets stabilized.
+ match expr {
+ Expr::Seq(l, r) => match *l {
+ Expr::Rep(l) => {
+ let l = *l;
+ match l {
+ Expr::Seq(l1, l2) => {
+ // Converts `(rule ~ rest)* ~ rule` to `rule ~ (rest ~ rule)*`,
+ // avoiding matching the last `rule` twice.
+ if l1 == r {
+ Expr::Seq(l1, Box::new(Expr::Rep(Box::new(Expr::Seq(l2, r)))))
+ } else {
+ Expr::Seq(Box::new(Expr::Rep(Box::new(Expr::Seq(l1, l2)))), r)
+ }
+ }
+ expr => Expr::Seq(Box::new(Expr::Rep(Box::new(expr))), r),
+ }
+ }
+ expr => Expr::Seq(Box::new(expr), r),
+ },
+ expr => expr,
+ }
+ }),
+ }
+}
diff --git a/vendor/pest_meta/src/optimizer/mod.rs b/vendor/pest_meta/src/optimizer/mod.rs
index 7013c43f9..e0cbdb0de 100644
--- a/vendor/pest_meta/src/optimizer/mod.rs
+++ b/vendor/pest_meta/src/optimizer/mod.rs
@@ -7,7 +7,7 @@
// option. All files in the project carrying such notice may not be copied,
// modified, or distributed except according to those terms.
-use ast::*;
+use crate::ast::*;
use std::collections::HashMap;
#[cfg(test)]
@@ -20,6 +20,7 @@ macro_rules! box_tree {
mod concatenator;
mod factorizer;
+mod lister;
mod restorer;
mod rotater;
mod skipper;
@@ -33,6 +34,7 @@ pub fn optimize(rules: Vec<Rule>) -> Vec<OptimizedRule> {
.map(unroller::unroll)
.map(concatenator::concatenate)
.map(factorizer::factor)
+ .map(lister::list)
.map(rule_to_optimized_rule)
.collect();
@@ -279,7 +281,7 @@ mod tests {
#[test]
fn rotate() {
let rules = {
- use ast::Expr::*;
+ use crate::ast::Expr::*;
vec![Rule {
name: "rule".to_owned(),
ty: RuleType::Normal,
@@ -293,7 +295,7 @@ mod tests {
}]
};
let rotated = {
- use optimizer::OptimizedExpr::*;
+ use crate::optimizer::OptimizedExpr::*;
vec![OptimizedRule {
name: "rule".to_owned(),
ty: RuleType::Normal,
@@ -313,7 +315,7 @@ mod tests {
#[test]
fn skip() {
let rules = {
- use ast::Expr::*;
+ use crate::ast::Expr::*;
vec![Rule {
name: "rule".to_owned(),
ty: RuleType::Atomic,
@@ -335,7 +337,7 @@ mod tests {
#[test]
fn concat_strings() {
let rules = {
- use ast::Expr::*;
+ use crate::ast::Expr::*;
vec![Rule {
name: "rule".to_owned(),
ty: RuleType::Atomic,
@@ -362,7 +364,7 @@ mod tests {
expr: Expr::RepExact(Box::new(Expr::Ident(String::from("a"))), 3),
}];
let unrolled = {
- use optimizer::OptimizedExpr::*;
+ use crate::optimizer::OptimizedExpr::*;
vec![OptimizedRule {
name: "rule".to_owned(),
ty: RuleType::Atomic,
@@ -384,7 +386,7 @@ mod tests {
expr: Expr::RepMax(Box::new(Expr::Str("a".to_owned())), 3),
}];
let unrolled = {
- use optimizer::OptimizedExpr::*;
+ use crate::optimizer::OptimizedExpr::*;
vec![OptimizedRule {
name: "rule".to_owned(),
ty: RuleType::Atomic,
@@ -406,7 +408,7 @@ mod tests {
expr: Expr::RepMin(Box::new(Expr::Str("a".to_owned())), 2),
}];
let unrolled = {
- use optimizer::OptimizedExpr::*;
+ use crate::optimizer::OptimizedExpr::*;
vec![OptimizedRule {
name: "rule".to_owned(),
ty: RuleType::Atomic,
@@ -428,7 +430,7 @@ mod tests {
expr: Expr::RepMinMax(Box::new(Expr::Str("a".to_owned())), 2, 3),
}];
let unrolled = {
- use optimizer::OptimizedExpr::*;
+ use crate::optimizer::OptimizedExpr::*;
vec![OptimizedRule {
name: "rule".to_owned(),
ty: RuleType::Atomic,
@@ -452,7 +454,7 @@ mod tests {
#[test]
fn concat_insensitive_strings() {
let rules = {
- use ast::Expr::*;
+ use crate::ast::Expr::*;
vec![Rule {
name: "rule".to_owned(),
ty: RuleType::Atomic,
@@ -474,7 +476,7 @@ mod tests {
#[test]
fn long_common_sequence() {
let rules = {
- use ast::Expr::*;
+ use crate::ast::Expr::*;
vec![Rule {
name: "rule".to_owned(),
ty: RuleType::Silent,
@@ -491,7 +493,7 @@ mod tests {
}]
};
let optimized = {
- use optimizer::OptimizedExpr::*;
+ use crate::optimizer::OptimizedExpr::*;
vec![OptimizedRule {
name: "rule".to_owned(),
ty: RuleType::Silent,
@@ -507,4 +509,82 @@ mod tests {
assert_eq!(optimize(rules), optimized);
}
+
+ #[test]
+ fn short_common_sequence() {
+ let rules = {
+ use crate::ast::Expr::*;
+ vec![Rule {
+ name: "rule".to_owned(),
+ ty: RuleType::Silent,
+ expr: box_tree!(Choice(
+ Seq(Ident(String::from("a")), Ident(String::from("b"))),
+ Ident(String::from("a"))
+ )),
+ }]
+ };
+ let optimized = {
+ use crate::optimizer::OptimizedExpr::*;
+ vec![OptimizedRule {
+ name: "rule".to_owned(),
+ ty: RuleType::Silent,
+ expr: box_tree!(Seq(Ident(String::from("a")), Opt(Ident(String::from("b"))))),
+ }]
+ };
+
+ assert_eq!(optimize(rules), optimized);
+ }
+
+ #[test]
+ fn impossible_common_sequence() {
+ let rules = {
+ use crate::ast::Expr::*;
+ vec![Rule {
+ name: "rule".to_owned(),
+ ty: RuleType::Silent,
+ expr: box_tree!(Choice(
+ Ident(String::from("a")),
+ Seq(Ident(String::from("a")), Ident(String::from("b")))
+ )),
+ }]
+ };
+ let optimized = {
+ use crate::optimizer::OptimizedExpr::*;
+ vec![OptimizedRule {
+ name: "rule".to_owned(),
+ ty: RuleType::Silent,
+ expr: box_tree!(Ident(String::from("a"))),
+ }]
+ };
+
+ assert_eq!(optimize(rules), optimized);
+ }
+
+ #[test]
+ fn lister() {
+ let rules = {
+ use crate::ast::Expr::*;
+ vec![Rule {
+ name: "rule".to_owned(),
+ ty: RuleType::Silent,
+ expr: box_tree!(Seq(
+ Rep(Seq(Ident(String::from("a")), Ident(String::from("b")))),
+ Ident(String::from("a"))
+ )),
+ }]
+ };
+ let optimized = {
+ use crate::optimizer::OptimizedExpr::*;
+ vec![OptimizedRule {
+ name: "rule".to_owned(),
+ ty: RuleType::Silent,
+ expr: box_tree!(Seq(
+ Ident(String::from("a")),
+ Rep(Seq(Ident(String::from("b")), Ident(String::from("a"))))
+ )),
+ }]
+ };
+
+ assert_eq!(optimize(rules), optimized);
+ }
}
diff --git a/vendor/pest_meta/src/optimizer/restorer.rs b/vendor/pest_meta/src/optimizer/restorer.rs
index 34a710eab..e128e03f1 100644
--- a/vendor/pest_meta/src/optimizer/restorer.rs
+++ b/vendor/pest_meta/src/optimizer/restorer.rs
@@ -8,19 +8,15 @@
// modified, or distributed except according to those terms.
use std::collections::HashMap;
-use optimizer::*;
+use crate::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 }
- }
- }
+ let OptimizedRule { name, ty, expr } = rule;
+ let expr = expr.map_bottom_up(|expr| wrap_branching_exprs(expr, rules));
+ OptimizedRule { name, ty, expr }
}
fn wrap_branching_exprs(
@@ -96,7 +92,7 @@ fn child_modifies_state(
#[cfg(test)]
mod tests {
use super::*;
- use optimizer::OptimizedExpr::*;
+ use crate::optimizer::OptimizedExpr::*;
#[test]
fn restore_no_stack_children() {
diff --git a/vendor/pest_meta/src/optimizer/rotater.rs b/vendor/pest_meta/src/optimizer/rotater.rs
index 3588738ad..7a7d8fba4 100644
--- a/vendor/pest_meta/src/optimizer/rotater.rs
+++ b/vendor/pest_meta/src/optimizer/rotater.rs
@@ -7,7 +7,7 @@
// option. All files in the project carrying such notice may not be copied,
// modified, or distributed except according to those terms.
-use ast::*;
+use crate::ast::*;
pub fn rotate(rule: Rule) -> Rule {
fn rotate_internal(expr: Expr) -> Expr {
@@ -35,11 +35,10 @@ pub fn rotate(rule: Rule) -> Rule {
}
}
- match rule {
- Rule { name, ty, expr } => Rule {
- name,
- ty,
- expr: expr.map_top_down(rotate_internal),
- },
+ let Rule { name, ty, expr } = rule;
+ 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
index f55edc06f..40bc5a16f 100644
--- a/vendor/pest_meta/src/optimizer/skipper.rs
+++ b/vendor/pest_meta/src/optimizer/skipper.rs
@@ -7,7 +7,7 @@
// option. All files in the project carrying such notice may not be copied,
// modified, or distributed except according to those terms.
-use ast::*;
+use crate::ast::*;
pub fn skip(rule: Rule) -> Rule {
fn populate_choices(expr: Expr, mut choices: Vec<String>) -> Option<Expr> {
@@ -28,30 +28,29 @@ pub fn skip(rule: Rule) -> Rule {
}
}
- 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;
- }
+ let Rule { name, ty, expr } = rule;
+ 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 {
+ 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
- },
+ })
+ } else {
+ expr
},
}
}
diff --git a/vendor/pest_meta/src/optimizer/unroller.rs b/vendor/pest_meta/src/optimizer/unroller.rs
index fff17336d..e3c360d90 100644
--- a/vendor/pest_meta/src/optimizer/unroller.rs
+++ b/vendor/pest_meta/src/optimizer/unroller.rs
@@ -7,61 +7,60 @@
// option. All files in the project carrying such notice may not be copied,
// modified, or distributed except according to those terms.
-use ast::*;
+use crate::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,
- }),
- },
+ let Rule { name, ty, expr } = rule;
+ 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-06-16 23:36:11 +0000