diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:06:31 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:06:31 +0000 |
commit | 2ff14448863ac1a1dd9533461708e29aae170c2d (patch) | |
tree | 85b9fea2bbfe3f06473cfa381eed11f273b57c5c /vendor/pest_meta/src/optimizer | |
parent | Adding debian version 1.64.0+dfsg1-1. (diff) | |
download | rustc-2ff14448863ac1a1dd9533461708e29aae170c2d.tar.xz rustc-2ff14448863ac1a1dd9533461708e29aae170c2d.zip |
Adding debian version 1.65.0+dfsg1-2.debian/1.65.0+dfsg1-2
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'vendor/pest_meta/src/optimizer')
-rw-r--r-- | vendor/pest_meta/src/optimizer/concatenator.rs | 39 | ||||
-rw-r--r-- | vendor/pest_meta/src/optimizer/factorizer.rs | 61 | ||||
-rw-r--r-- | vendor/pest_meta/src/optimizer/lister.rs | 42 | ||||
-rw-r--r-- | vendor/pest_meta/src/optimizer/mod.rs | 104 | ||||
-rw-r--r-- | vendor/pest_meta/src/optimizer/restorer.rs | 14 | ||||
-rw-r--r-- | vendor/pest_meta/src/optimizer/rotater.rs | 13 | ||||
-rw-r--r-- | vendor/pest_meta/src/optimizer/skipper.rs | 39 | ||||
-rw-r--r-- | vendor/pest_meta/src/optimizer/unroller.rs | 107 |
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, + }), } } |