pest_meta/optimizer/
restorer.rs

Help
1// pest. The Elegant Parser
2// Copyright (c) 2018 Dragoș Tiselice
3//
4// Licensed under the Apache License, Version 2.0
5// <LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0> or the MIT
6// license <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
7// option. All files in the project carrying such notice may not be copied,
8// modified, or distributed except according to those terms.
9use std::collections::HashMap;
10
11use crate::optimizer::*;
12
13pub fn restore_on_err(
14    rule: OptimizedRule,
15    rules: &HashMap<String, OptimizedExpr>,
16) -> OptimizedRule {
17    let OptimizedRule { name, ty, expr } = rule;
18    let expr = expr.map_bottom_up(|expr| wrap_branching_exprs(expr, rules));
19    OptimizedRule { name, ty, expr }
20}
21
22fn wrap_branching_exprs(
23    expr: OptimizedExpr,
24    rules: &HashMap<String, OptimizedExpr>,
25) -> OptimizedExpr {
26    match expr {
27        OptimizedExpr::Opt(expr) => {
28            if child_modifies_state(&expr, rules, &mut HashMap::new()) {
29                OptimizedExpr::Opt(Box::new(OptimizedExpr::RestoreOnErr(expr)))
30            } else {
31                OptimizedExpr::Opt(expr)
32            }
33        }
34        OptimizedExpr::Choice(lhs, rhs) => {
35            let wrapped_lhs = if child_modifies_state(&lhs, rules, &mut HashMap::new()) {
36                Box::new(OptimizedExpr::RestoreOnErr(lhs))
37            } else {
38                lhs
39            };
40            let wrapped_rhs = if child_modifies_state(&rhs, rules, &mut HashMap::new()) {
41                Box::new(OptimizedExpr::RestoreOnErr(rhs))
42            } else {
43                rhs
44            };
45            OptimizedExpr::Choice(wrapped_lhs, wrapped_rhs)
46        }
47        OptimizedExpr::Rep(expr) => {
48            if child_modifies_state(&expr, rules, &mut HashMap::new()) {
49                OptimizedExpr::Rep(Box::new(OptimizedExpr::RestoreOnErr(expr)))
50            } else {
51                OptimizedExpr::Rep(expr)
52            }
53        }
54        _ => expr,
55    }
56}
57
58fn child_modifies_state(
59    expr: &OptimizedExpr,
60    rules: &HashMap<String, OptimizedExpr>,
61    cache: &mut HashMap<String, Option<bool>>,
62) -> bool {
63    expr.iter_top_down().any(|expr| match expr {
64        OptimizedExpr::Push(_) => true,
65        OptimizedExpr::Ident(ref name) if name == "DROP" => true,
66        OptimizedExpr::Ident(ref name) if name == "POP" => true,
67        OptimizedExpr::Ident(ref name) => match cache.get(name).cloned() {
68            Some(option) => match option {
69                Some(cached) => cached,
70                None => {
71                    cache.insert(name.to_owned(), Some(false));
72                    false
73                }
74            },
75            None => {
76                cache.insert(name.to_owned(), None);
77
78                let result = match rules.get(name) {
79                    Some(expr) => child_modifies_state(expr, rules, cache),
80                    None => false,
81                };
82
83                cache.insert(name.to_owned(), Some(result));
84
85                result
86            }
87        },
88        _ => false,
89    })
90}
91
92#[cfg(test)]
93mod tests {
94    use super::*;
95    use crate::optimizer::OptimizedExpr::*;
96
97    #[test]
98    fn restore_no_stack_children() {
99        let rules = vec![OptimizedRule {
100            name: "rule".to_owned(),
101            ty: RuleType::Normal,
102            expr: box_tree!(Opt(Str("a".to_string()))),
103        }];
104
105        assert_eq!(
106            restore_on_err(rules[0].clone(), &to_optimized_hash_map(&rules)),
107            rules[0].clone()
108        );
109    }
110
111    #[test]
112    fn restore_with_child_stack_ops() {
113        let rules = vec![OptimizedRule {
114            name: "rule".to_owned(),
115            ty: RuleType::Normal,
116            expr: box_tree!(Rep(Push(Str("a".to_string())))),
117        }];
118
119        let restored = OptimizedRule {
120            name: "rule".to_owned(),
121            ty: RuleType::Normal,
122            expr: box_tree!(Rep(RestoreOnErr(Push(Str("a".to_string()))))),
123        };
124
125        assert_eq!(
126            restore_on_err(rules[0].clone(), &to_optimized_hash_map(&rules)),
127            restored
128        );
129    }
130
131    #[test]
132    fn restore_choice_branch_with_and_branch_without() {
133        let rules = vec![OptimizedRule {
134            name: "rule".to_owned(),
135            ty: RuleType::Normal,
136            expr: box_tree!(Choice(Push(Str("a".to_string())), Str("a".to_string()))),
137        }];
138
139        let restored = OptimizedRule {
140            name: "rule".to_owned(),
141            ty: RuleType::Normal,
142            expr: box_tree!(Choice(
143                RestoreOnErr(Push(Str("a".to_string()))),
144                Str("a".to_string())
145            )),
146        };
147
148        assert_eq!(
149            restore_on_err(rules[0].clone(), &to_optimized_hash_map(&rules)),
150            restored
151        );
152    }
153}
pest_meta/optimizer/restorer.rs

pest_meta/optimizer/
restorer.rs
