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: String, ty: RuleType, expr: OptimizedExpr } = rule;
18 let expr: OptimizedExpr = expr.map_bottom_up(|expr: OptimizedExpr| 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_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_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_hash_map(&rules)),
150 restored
151 );
152 }
153}
154