pest_meta_tmp/optimizer/
restorer.rs

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 optimizer::*;
12
13pub fn restore_on_err(
14    rule: OptimizedRule,
15    rules: &HashMap<String, OptimizedExpr>,
16) -> OptimizedRule {
17    match rule {
18        OptimizedRule { name, ty, expr } => {
19            let expr = expr.map_bottom_up(|expr| wrap_branching_exprs(expr, rules));
20
21            OptimizedRule { name, ty, expr }
22        }
23    }
24}
25
26fn wrap_branching_exprs(
27    expr: OptimizedExpr,
28    rules: &HashMap<String, OptimizedExpr>,
29) -> OptimizedExpr {
30    match expr {
31        OptimizedExpr::Opt(expr) => {
32            if child_modifies_state(&expr, rules, &mut HashMap::new()) {
33                OptimizedExpr::Opt(Box::new(OptimizedExpr::RestoreOnErr(expr)))
34            } else {
35                OptimizedExpr::Opt(expr)
36            }
37        }
38        OptimizedExpr::Choice(lhs, rhs) => {
39            let wrapped_lhs = if child_modifies_state(&lhs, rules, &mut HashMap::new()) {
40                Box::new(OptimizedExpr::RestoreOnErr(lhs))
41            } else {
42                lhs
43            };
44            let wrapped_rhs = if child_modifies_state(&rhs, rules, &mut HashMap::new()) {
45                Box::new(OptimizedExpr::RestoreOnErr(rhs))
46            } else {
47                rhs
48            };
49            OptimizedExpr::Choice(wrapped_lhs, wrapped_rhs)
50        }
51        OptimizedExpr::Rep(expr) => {
52            if child_modifies_state(&expr, rules, &mut HashMap::new()) {
53                OptimizedExpr::Rep(Box::new(OptimizedExpr::RestoreOnErr(expr)))
54            } else {
55                OptimizedExpr::Rep(expr)
56            }
57        }
58        _ => expr,
59    }
60}
61
62fn child_modifies_state(
63    expr: &OptimizedExpr,
64    rules: &HashMap<String, OptimizedExpr>,
65    cache: &mut HashMap<String, Option<bool>>,
66) -> bool {
67    expr.iter_top_down().any(|expr| match expr {
68        OptimizedExpr::Push(_) => true,
69        OptimizedExpr::Ident(ref name) if name == "DROP" => true,
70        OptimizedExpr::Ident(ref name) if name == "POP" => true,
71        OptimizedExpr::Ident(ref name) => match cache.get(name).cloned() {
72            Some(option) => match option {
73                Some(cached) => cached,
74                None => {
75                    cache.insert(name.to_owned(), Some(false));
76                    false
77                }
78            },
79            None => {
80                cache.insert(name.to_owned(), None);
81
82                let result = match rules.get(name) {
83                    Some(expr) => child_modifies_state(expr, rules, cache),
84                    None => false,
85                };
86
87                cache.insert(name.to_owned(), Some(result));
88
89                result
90            }
91        },
92        _ => false,
93    })
94}
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99    use optimizer::OptimizedExpr::*;
100
101    #[test]
102    fn restore_no_stack_children() {
103        let rules = vec![OptimizedRule {
104            name: "rule".to_owned(),
105            ty: RuleType::Normal,
106            expr: box_tree!(Opt(Str("a".to_string()))),
107        }];
108
109        assert_eq!(
110            restore_on_err(rules[0].clone(), &to_hash_map(&rules)),
111            rules[0].clone()
112        );
113    }
114
115    #[test]
116    fn restore_with_child_stack_ops() {
117        let rules = vec![OptimizedRule {
118            name: "rule".to_owned(),
119            ty: RuleType::Normal,
120            expr: box_tree!(Rep(Push(Str("a".to_string())))),
121        }];
122
123        let restored = OptimizedRule {
124            name: "rule".to_owned(),
125            ty: RuleType::Normal,
126            expr: box_tree!(Rep(RestoreOnErr(Push(Str("a".to_string()))))),
127        };
128
129        assert_eq!(
130            restore_on_err(rules[0].clone(), &to_hash_map(&rules)),
131            restored
132        );
133    }
134
135    #[test]
136    fn restore_choice_branch_with_and_branch_without() {
137        let rules = vec![OptimizedRule {
138            name: "rule".to_owned(),
139            ty: RuleType::Normal,
140            expr: box_tree!(Choice(Push(Str("a".to_string())), Str("a".to_string()))),
141        }];
142
143        let restored = OptimizedRule {
144            name: "rule".to_owned(),
145            ty: RuleType::Normal,
146            expr: box_tree!(Choice(
147                RestoreOnErr(Push(Str("a".to_string()))),
148                Str("a".to_string())
149            )),
150        };
151
152        assert_eq!(
153            restore_on_err(rules[0].clone(), &to_hash_map(&rules)),
154            restored
155        );
156    }
157}
pest_meta_tmp/optimizer/restorer.rs

pest_meta_tmp/optimizer/
restorer.rs
