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. 9 10 #[derive(Clone, Debug, Eq, PartialEq)] 11 pub struct Rule { 12 pub name: String, 13 pub ty: RuleType, 14 pub expr: Expr, 15 } 16 17 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 18 pub enum RuleType { 19 Normal, 20 Silent, 21 Atomic, 22 CompoundAtomic, 23 NonAtomic, 24 } 25 26 #[derive(Clone, Debug, Eq, PartialEq)] 27 pub enum Expr { 28 /// Matches an exact string, e.g. `"a"` 29 Str(String), 30 /// Matches an exact string, case insensitively (ASCII only), e.g. `^"a"` 31 Insens(String), 32 /// Matches one character in the range, e.g. `'a'..'z'` 33 Range(String, String), 34 /// Matches the rule with the given name, e.g. `a` 35 Ident(String), 36 /// Matches a custom part of the stack, e.g. `PEEK[..]` 37 PeekSlice(i32, Option<i32>), 38 /// Positive lookahead; matches expression without making progress, e.g. `&e` 39 PosPred(Box<Expr>), 40 /// Negative lookahead; matches if expression doesn't match, without making progress, e.g. `!e` 41 NegPred(Box<Expr>), 42 /// Matches a sequence of two expressions, e.g. `e1 ~ e2` 43 Seq(Box<Expr>, Box<Expr>), 44 /// Matches either of two expressions, e.g. `e1 | e2` 45 Choice(Box<Expr>, Box<Expr>), 46 /// Optionally matches an expression, e.g. `e?` 47 Opt(Box<Expr>), 48 /// Matches an expression zero or more times, e.g. `e*` 49 Rep(Box<Expr>), 50 /// Matches an expression one or more times, e.g. `e+` 51 RepOnce(Box<Expr>), 52 /// Matches an expression an exact number of times, e.g. `e{n}` 53 RepExact(Box<Expr>, u32), 54 /// Matches an expression at least a number of times, e.g. `e{n,}` 55 RepMin(Box<Expr>, u32), 56 /// Matches an expression at most a number of times, e.g. `e{,n}` 57 RepMax(Box<Expr>, u32), 58 /// Matches an expression a number of times within a range, e.g. `e{m, n}` 59 RepMinMax(Box<Expr>, u32, u32), 60 /// Continues to match expressions until one of the strings in the `Vec` is found 61 Skip(Vec<String>), 62 /// Matches an expression and pushes it to the stack, e.g. `push(e)` 63 Push(Box<Expr>), 64 } 65 66 impl Expr { iter_top_down(&self) -> ExprTopDownIterator67 pub fn iter_top_down(&self) -> ExprTopDownIterator { 68 ExprTopDownIterator::new(self) 69 } 70 map_top_down<F>(self, mut f: F) -> Expr where F: FnMut(Expr) -> Expr,71 pub fn map_top_down<F>(self, mut f: F) -> Expr 72 where 73 F: FnMut(Expr) -> Expr, 74 { 75 fn map_internal<F>(expr: Expr, f: &mut F) -> Expr 76 where 77 F: FnMut(Expr) -> Expr, 78 { 79 let expr = f(expr); 80 81 match expr { 82 // TODO: Use box syntax when it gets stabilized. 83 Expr::PosPred(expr) => { 84 let mapped = Box::new(map_internal(*expr, f)); 85 Expr::PosPred(mapped) 86 } 87 Expr::NegPred(expr) => { 88 let mapped = Box::new(map_internal(*expr, f)); 89 Expr::NegPred(mapped) 90 } 91 Expr::Seq(lhs, rhs) => { 92 let mapped_lhs = Box::new(map_internal(*lhs, f)); 93 let mapped_rhs = Box::new(map_internal(*rhs, f)); 94 Expr::Seq(mapped_lhs, mapped_rhs) 95 } 96 Expr::Choice(lhs, rhs) => { 97 let mapped_lhs = Box::new(map_internal(*lhs, f)); 98 let mapped_rhs = Box::new(map_internal(*rhs, f)); 99 Expr::Choice(mapped_lhs, mapped_rhs) 100 } 101 Expr::Rep(expr) => { 102 let mapped = Box::new(map_internal(*expr, f)); 103 Expr::Rep(mapped) 104 } 105 Expr::RepOnce(expr) => { 106 let mapped = Box::new(map_internal(*expr, f)); 107 Expr::RepOnce(mapped) 108 } 109 Expr::RepExact(expr, max) => { 110 let mapped = Box::new(map_internal(*expr, f)); 111 Expr::RepExact(mapped, max) 112 } 113 Expr::RepMin(expr, num) => { 114 let mapped = Box::new(map_internal(*expr, f)); 115 Expr::RepMin(mapped, num) 116 } 117 Expr::RepMax(expr, num) => { 118 let mapped = Box::new(map_internal(*expr, f)); 119 Expr::RepMax(mapped, num) 120 } 121 Expr::RepMinMax(expr, min, max) => { 122 let mapped = Box::new(map_internal(*expr, f)); 123 Expr::RepMinMax(mapped, min, max) 124 } 125 Expr::Opt(expr) => { 126 let mapped = Box::new(map_internal(*expr, f)); 127 Expr::Opt(mapped) 128 } 129 Expr::Push(expr) => { 130 let mapped = Box::new(map_internal(*expr, f)); 131 Expr::Push(mapped) 132 } 133 expr => expr, 134 } 135 } 136 137 map_internal(self, &mut f) 138 } 139 map_bottom_up<F>(self, mut f: F) -> Expr where F: FnMut(Expr) -> Expr,140 pub fn map_bottom_up<F>(self, mut f: F) -> Expr 141 where 142 F: FnMut(Expr) -> Expr, 143 { 144 fn map_internal<F>(expr: Expr, f: &mut F) -> Expr 145 where 146 F: FnMut(Expr) -> Expr, 147 { 148 let mapped = match expr { 149 Expr::PosPred(expr) => { 150 // TODO: Use box syntax when it gets stabilized. 151 let mapped = Box::new(map_internal(*expr, f)); 152 Expr::PosPred(mapped) 153 } 154 Expr::NegPred(expr) => { 155 let mapped = Box::new(map_internal(*expr, f)); 156 Expr::NegPred(mapped) 157 } 158 Expr::Seq(lhs, rhs) => { 159 let mapped_lhs = Box::new(map_internal(*lhs, f)); 160 let mapped_rhs = Box::new(map_internal(*rhs, f)); 161 Expr::Seq(mapped_lhs, mapped_rhs) 162 } 163 Expr::Choice(lhs, rhs) => { 164 let mapped_lhs = Box::new(map_internal(*lhs, f)); 165 let mapped_rhs = Box::new(map_internal(*rhs, f)); 166 Expr::Choice(mapped_lhs, mapped_rhs) 167 } 168 Expr::Rep(expr) => { 169 let mapped = Box::new(map_internal(*expr, f)); 170 Expr::Rep(mapped) 171 } 172 Expr::RepOnce(expr) => { 173 let mapped = Box::new(map_internal(*expr, f)); 174 Expr::RepOnce(mapped) 175 } 176 Expr::RepExact(expr, num) => { 177 let mapped = Box::new(map_internal(*expr, f)); 178 Expr::RepExact(mapped, num) 179 } 180 Expr::RepMin(expr, max) => { 181 let mapped = Box::new(map_internal(*expr, f)); 182 Expr::RepMin(mapped, max) 183 } 184 Expr::RepMax(expr, max) => { 185 let mapped = Box::new(map_internal(*expr, f)); 186 Expr::RepMax(mapped, max) 187 } 188 Expr::RepMinMax(expr, min, max) => { 189 let mapped = Box::new(map_internal(*expr, f)); 190 Expr::RepMinMax(mapped, min, max) 191 } 192 Expr::Opt(expr) => { 193 let mapped = Box::new(map_internal(*expr, f)); 194 Expr::Opt(mapped) 195 } 196 Expr::Push(expr) => { 197 let mapped = Box::new(map_internal(*expr, f)); 198 Expr::Push(mapped) 199 } 200 expr => expr, 201 }; 202 203 f(mapped) 204 } 205 206 map_internal(self, &mut f) 207 } 208 } 209 210 pub struct ExprTopDownIterator { 211 current: Option<Expr>, 212 next: Option<Expr>, 213 right_branches: Vec<Expr>, 214 } 215 216 impl ExprTopDownIterator { new(expr: &Expr) -> Self217 pub fn new(expr: &Expr) -> Self { 218 let mut iter = ExprTopDownIterator { 219 current: None, 220 next: None, 221 right_branches: vec![], 222 }; 223 iter.iterate_expr(expr.clone()); 224 iter 225 } 226 iterate_expr(&mut self, expr: Expr)227 fn iterate_expr(&mut self, expr: Expr) { 228 self.current = Some(expr.clone()); 229 match expr { 230 Expr::Seq(lhs, rhs) => { 231 self.right_branches.push(*rhs); 232 self.next = Some(*lhs); 233 } 234 Expr::Choice(lhs, rhs) => { 235 self.right_branches.push(*rhs); 236 self.next = Some(*lhs); 237 } 238 Expr::PosPred(expr) 239 | Expr::NegPred(expr) 240 | Expr::Rep(expr) 241 | Expr::RepOnce(expr) 242 | Expr::RepExact(expr, _) 243 | Expr::RepMin(expr, _) 244 | Expr::RepMax(expr, _) 245 | Expr::RepMinMax(expr, ..) 246 | Expr::Opt(expr) 247 | Expr::Push(expr) => { 248 self.next = Some(*expr); 249 } 250 _ => { 251 self.next = None; 252 } 253 } 254 } 255 } 256 257 impl Iterator for ExprTopDownIterator { 258 type Item = Expr; 259 next(&mut self) -> Option<Self::Item>260 fn next(&mut self) -> Option<Self::Item> { 261 let result = self.current.take(); 262 263 if let Some(expr) = self.next.take() { 264 self.iterate_expr(expr); 265 } else if let Some(expr) = self.right_branches.pop() { 266 self.iterate_expr(expr); 267 } 268 269 result 270 } 271 } 272 273 #[cfg(test)] 274 mod tests { 275 use super::*; 276 277 #[test] top_down_iterator()278 fn top_down_iterator() { 279 let expr = Expr::Choice( 280 Box::new(Expr::Str(String::from("a"))), 281 Box::new(Expr::Str(String::from("b"))), 282 ); 283 let mut top_down = expr.clone().iter_top_down(); 284 assert_eq!(top_down.next(), Some(expr)); 285 assert_eq!(top_down.next(), Some(Expr::Str(String::from("a")))); 286 assert_eq!(top_down.next(), Some(Expr::Str(String::from("b")))); 287 assert_eq!(top_down.next(), None); 288 } 289 290 #[test] identity()291 fn identity() { 292 let expr = Expr::Choice( 293 Box::new(Expr::Seq( 294 Box::new(Expr::Ident("a".to_owned())), 295 Box::new(Expr::Str("b".to_owned())), 296 )), 297 Box::new(Expr::PosPred(Box::new(Expr::NegPred(Box::new(Expr::Rep( 298 Box::new(Expr::RepOnce(Box::new(Expr::Opt(Box::new(Expr::Choice( 299 Box::new(Expr::Insens("c".to_owned())), 300 Box::new(Expr::Push(Box::new(Expr::Range( 301 "'d'".to_owned(), 302 "'e'".to_owned(), 303 )))), 304 )))))), 305 )))))), 306 ); 307 308 assert_eq!( 309 expr.clone() 310 .map_bottom_up(|expr| expr) 311 .map_top_down(|expr| expr), 312 expr 313 ); 314 } 315 } 316