| 1 | use super::{JsonPath, JsonPathToken}; |
| 2 | use crate::{Any, JsonPathEval}; |
| 3 | |
| 4 | impl JsonPathEval for Any { |
| 5 | type Iter<'a> = JsonPathIter<'a>; |
| 6 | |
| 7 | /// Evaluate JSON path on the current object. |
| 8 | /// |
| 9 | /// # Example |
| 10 | /// ```rust |
| 11 | /// use yrs::{any, Any, JsonPath, JsonPathEval}; |
| 12 | /// |
| 13 | /// let root = any!({ |
| 14 | /// "users": [ |
| 15 | /// { |
| 16 | /// "name": "Alice", |
| 17 | /// "surname": "Smith", |
| 18 | /// "age": 25, |
| 19 | /// "friends": [ |
| 20 | /// { "name": "Bob", "nick": "boreas" }, |
| 21 | /// { "nick": "crocodile91" } |
| 22 | /// ] |
| 23 | /// }, |
| 24 | /// ] |
| 25 | /// }); |
| 26 | /// |
| 27 | /// let query = JsonPath::parse("$.users..friends.*.nick").unwrap(); |
| 28 | /// let values: Vec<&Any> = root.json_path(&query).collect(); |
| 29 | /// assert_eq!(values, vec![&any!("boreas"), &any!("crocodile91")]); |
| 30 | /// ``` |
| 31 | fn json_path<'a>(&'a self, path: &'a JsonPath<'a>) -> Self::Iter<'a> { |
| 32 | JsonPathIter::new(self, path.as_ref()) |
| 33 | } |
| 34 | } |
| 35 | |
| 36 | fn slice_iter<'a>( |
| 37 | any: &'a Any, |
| 38 | from: usize, |
| 39 | to: usize, |
| 40 | by: usize, |
| 41 | ) -> Option<Box<dyn Iterator<Item = &'a Any> + 'a>> { |
| 42 | match any { |
| 43 | Any::Array(array) => { |
| 44 | let to = array.len().min(to); |
| 45 | Some(Box::new( |
| 46 | array.iter().skip(from).take(to - from).step_by(by), |
| 47 | )) |
| 48 | } |
| 49 | _ => None, |
| 50 | } |
| 51 | } |
| 52 | |
| 53 | fn member_union_iter<'a>( |
| 54 | any: &'a Any, |
| 55 | members: &'a [&'a str], |
| 56 | ) -> Option<Box<dyn Iterator<Item = &'a Any> + 'a>> { |
| 57 | match any { |
| 58 | Any::Map(map) => { |
| 59 | let iter = members.into_iter().flat_map(move |key| map.get(*key)); |
| 60 | Some(Box::new(iter)) |
| 61 | } |
| 62 | _ => None, |
| 63 | } |
| 64 | } |
| 65 | |
| 66 | fn index_union_iter<'a>( |
| 67 | any: &'a Any, |
| 68 | indices: &'a [i32], |
| 69 | ) -> Option<Box<dyn Iterator<Item = &'a Any> + 'a>> { |
| 70 | match any { |
| 71 | Any::Array(array) => { |
| 72 | let iter = indices.into_iter().flat_map(move |i| { |
| 73 | let i = if *i < 0 { |
| 74 | (array.len() as i32 + *i) as usize |
| 75 | } else { |
| 76 | *i as usize |
| 77 | }; |
| 78 | array.get(i) |
| 79 | }); |
| 80 | Some(Box::new(iter)) |
| 81 | } |
| 82 | _ => None, |
| 83 | } |
| 84 | } |
| 85 | |
| 86 | pub struct JsonPathIter<'a> { |
| 87 | root: &'a Any, |
| 88 | pattern: &'a [JsonPathToken<'a>], |
| 89 | frame: ExecutionFrame<'a>, |
| 90 | } |
| 91 | |
| 92 | impl<'a> JsonPathIter<'a> { |
| 93 | fn new(root: &'a Any, path: &'a [JsonPathToken<'a>]) -> Self { |
| 94 | Self { |
| 95 | root, |
| 96 | pattern: path.as_ref(), |
| 97 | frame: ExecutionFrame::new(root, 0, None), |
| 98 | } |
| 99 | } |
| 100 | } |
| 101 | |
| 102 | impl<'a> Iterator for JsonPathIter<'a> { |
| 103 | type Item = &'a Any; |
| 104 | |
| 105 | fn next(&mut self) -> Option<Self::Item> { |
| 106 | let frame = &mut self.frame; |
| 107 | if let Some(iter) = &mut frame.iter { |
| 108 | match iter.next() { |
| 109 | None => { |
| 110 | frame.iter = None; |
| 111 | return if frame.ascend() { self.next() } else { None }; |
| 112 | } |
| 113 | Some(curr) => { |
| 114 | frame.descend(curr); |
| 115 | } |
| 116 | } |
| 117 | } else if frame.index == self.pattern.len() { |
| 118 | return if frame.ascend() { self.next() } else { None }; |
| 119 | } |
| 120 | // early return only works if the loop after has at least one iteration |
| 121 | let mut early_return = false; |
| 122 | while frame.index < self.pattern.len() { |
| 123 | let segment = &self.pattern[frame.index]; |
| 124 | frame.index += 1; |
| 125 | match segment { |
| 126 | JsonPathToken::Root => frame.current = self.root, |
| 127 | JsonPathToken::Current => { /* do nothing */ } |
| 128 | JsonPathToken::Member(key) => { |
| 129 | if let Any::Map(map) = frame.current { |
| 130 | frame.current = match map.get(*key) { |
| 131 | Some(value) => value, |
| 132 | None => { |
| 133 | early_return = true; |
| 134 | break; |
| 135 | } |
| 136 | } |
| 137 | } else { |
| 138 | early_return = true; |
| 139 | } |
| 140 | } |
| 141 | JsonPathToken::Index(idx) => { |
| 142 | if let Any::Array(array) = frame.current { |
| 143 | let idx = if *idx < 0 { |
| 144 | array.len() as i32 + idx |
| 145 | } else { |
| 146 | *idx |
| 147 | } as usize; |
| 148 | frame.current = match array.get(idx) { |
| 149 | Some(value) => value, |
| 150 | None => { |
| 151 | early_return = true; |
| 152 | break; |
| 153 | } |
| 154 | }; |
| 155 | } else { |
| 156 | early_return = true; |
| 157 | } |
| 158 | } |
| 159 | JsonPathToken::Wildcard => { |
| 160 | if let Some(iter) = frame.current.try_iter() { |
| 161 | frame.iter = Some(Box::new(iter.map(|(_, value)| value))); |
| 162 | return self.next(); |
| 163 | } |
| 164 | early_return = true; |
| 165 | } |
| 166 | JsonPathToken::RecursiveDescend => { |
| 167 | if let Some(iter) = frame.current.try_iter() { |
| 168 | frame.iter = Some(Box::new(iter.map(|(_, value)| value))); |
| 169 | frame.is_descending = true; |
| 170 | return self.next(); |
| 171 | } |
| 172 | early_return = true; |
| 173 | } |
| 174 | JsonPathToken::Slice(from, to, by) => { |
| 175 | if let Some(iter) = |
| 176 | slice_iter(frame.current, *from as usize, *to as usize, *by as usize) |
| 177 | { |
| 178 | frame.iter = Some(iter); |
| 179 | return self.next(); |
| 180 | } |
| 181 | early_return = true; |
| 182 | } |
| 183 | JsonPathToken::MemberUnion(members) => { |
| 184 | if let Some(iter) = member_union_iter(frame.current, &members) { |
| 185 | frame.iter = Some(iter); |
| 186 | return self.next(); |
| 187 | } |
| 188 | early_return = true; |
| 189 | } |
| 190 | JsonPathToken::IndexUnion(indices) => { |
| 191 | if let Some(iter) = index_union_iter(frame.current, &indices) { |
| 192 | frame.iter = Some(iter); |
| 193 | return self.next(); |
| 194 | } |
| 195 | early_return = true; |
| 196 | } |
| 197 | } |
| 198 | |
| 199 | if early_return { |
| 200 | break; |
| 201 | } |
| 202 | } |
| 203 | |
| 204 | if !early_return { |
| 205 | return Some(frame.current); |
| 206 | } else if frame.is_descending { |
| 207 | if let Some(iter) = frame.current.try_iter() { |
| 208 | frame.iter = Some(Box::new(iter.map(|(_, value)| value))); |
| 209 | frame.is_descending = true; |
| 210 | frame.index -= 1; // '..' means we're not consuming the segment in this iteration |
| 211 | return self.next(); |
| 212 | } |
| 213 | } |
| 214 | |
| 215 | if frame.iter.is_none() && !frame.ascend() { |
| 216 | None // we got to the end of the evaluator |
| 217 | } else { |
| 218 | self.next() |
| 219 | } |
| 220 | } |
| 221 | } |
| 222 | |
| 223 | /// Scope used for recursive iteration, i.e. wildcard, descent or slice. |
| 224 | struct ExecutionFrame<'a> { |
| 225 | /// Offset to tokens array, where the current scope starts. |
| 226 | index: usize, |
| 227 | /// Whether we're in recursive descent scope. |
| 228 | is_descending: bool, |
| 229 | /// Current object this scope is iterating over. |
| 230 | current: &'a Any, |
| 231 | /// Iterator used by this scope. |
| 232 | iter: Option<ScopeIterator<'a>>, |
| 233 | /// Scopes can be nested in each other i.e. `$.people.*.friends[*]name`. In such case they |
| 234 | /// are organized in a linked list, with the first elements being the innermost scopes. |
| 235 | next: Option<Box<ExecutionFrame<'a>>>, |
| 236 | } |
| 237 | |
| 238 | impl<'a> ExecutionFrame<'a> { |
| 239 | fn new(current: &'a Any, index: usize, iter: Option<ScopeIterator<'a>>) -> Self { |
| 240 | Self { |
| 241 | index, |
| 242 | is_descending: false, |
| 243 | current, |
| 244 | iter, |
| 245 | next: None, |
| 246 | } |
| 247 | } |
| 248 | |
| 249 | /// Descent into given iterator context, moving current frame to the stack and replacing it with |
| 250 | /// a new one executing in a context of that iterator. |
| 251 | fn descend(&mut self, current: &'a Any) { |
| 252 | let new_self = ExecutionFrame { |
| 253 | index: self.index, |
| 254 | is_descending: self.is_descending, |
| 255 | current, |
| 256 | iter: None, |
| 257 | next: None, |
| 258 | }; |
| 259 | let old_frame = std::mem::replace(self, new_self); |
| 260 | self.next = Some(Box::new(old_frame)); |
| 261 | } |
| 262 | |
| 263 | /// Return from current scope, restoring previous iter frame from the stack. |
| 264 | /// If there are no more iter frames, return false. |
| 265 | fn ascend(&mut self) -> bool { |
| 266 | match self.next.take() { |
| 267 | None => false, |
| 268 | Some(next) => { |
| 269 | *self = *next; |
| 270 | true |
| 271 | } |
| 272 | } |
| 273 | } |
| 274 | } |
| 275 | |
| 276 | type ScopeIterator<'a> = Box<dyn Iterator<Item = &'a Any> + 'a>; |
| 277 | |
| 278 | #[cfg(test)] |
| 279 | mod test { |
| 280 | use crate::json_path::JsonPath; |
| 281 | use crate::{any, Any, JsonPathEval}; |
| 282 | |
| 283 | fn mixed_sample() -> Any { |
| 284 | any!({ |
| 285 | "users": [ |
| 286 | { |
| 287 | "name": "Alice", |
| 288 | "surname": "Smith", |
| 289 | "age": 25, |
| 290 | "friends": [ |
| 291 | { "name": "Bob", "nick": "boreas" }, |
| 292 | { "nick": "crocodile91" } |
| 293 | ] |
| 294 | }, |
| 295 | { |
| 296 | "name": "Bob", |
| 297 | "nick": "boreas", |
| 298 | "age": 30 |
| 299 | }, |
| 300 | { |
| 301 | "nick": "crocodile91", |
| 302 | "age": 35 |
| 303 | }, |
| 304 | { |
| 305 | "name": "Damian", |
| 306 | "surname": "Smith", |
| 307 | "age": 30 |
| 308 | }, |
| 309 | { |
| 310 | "name": "Elise", |
| 311 | "age": 35 |
| 312 | } |
| 313 | ] |
| 314 | }) |
| 315 | } |
| 316 | |
| 317 | #[test] |
| 318 | fn eval_member_partial() { |
| 319 | let any = mixed_sample(); |
| 320 | let path = JsonPath::parse("$.users").unwrap(); |
| 321 | let values: Vec<_> = any.json_path(&path).collect(); |
| 322 | let expected = any!([ |
| 323 | { |
| 324 | "name": "Alice", |
| 325 | "surname": "Smith", |
| 326 | "age": 25, |
| 327 | "friends": [ |
| 328 | { "name": "Bob", "nick": "boreas" }, |
| 329 | { "nick": "crocodile91" } |
| 330 | ] |
| 331 | }, |
| 332 | { |
| 333 | "name": "Bob", |
| 334 | "nick": "boreas", |
| 335 | "age": 30 |
| 336 | }, |
| 337 | { |
| 338 | "nick": "crocodile91", |
| 339 | "age": 35 |
| 340 | }, |
| 341 | { |
| 342 | "name": "Damian", |
| 343 | "surname": "Smith", |
| 344 | "age": 30 |
| 345 | }, |
| 346 | { |
| 347 | "name": "Elise", |
| 348 | "age": 35 |
| 349 | } |
| 350 | ]); |
| 351 | assert_eq!(values, vec![&expected]); |
| 352 | } |
| 353 | |
| 354 | #[test] |
| 355 | fn eval_member_full() { |
| 356 | let any = mixed_sample(); |
| 357 | let path = JsonPath::parse("$.users[0].name").unwrap(); |
| 358 | let values: Vec<_> = any.json_path(&path).collect(); |
| 359 | assert_eq!(values, vec![&any!("Alice")]); |
| 360 | } |
| 361 | |
| 362 | #[test] |
| 363 | fn eval_member_negative_index() { |
| 364 | let any = mixed_sample(); |
| 365 | let path = JsonPath::parse("$.users[-1].name").unwrap(); |
| 366 | let values: Vec<_> = any.json_path(&path).collect(); |
| 367 | assert_eq!(values, vec![&any!("Elise")]); |
| 368 | } |
| 369 | |
| 370 | #[test] |
| 371 | fn eval_member_wildcard_array() { |
| 372 | let any = mixed_sample(); |
| 373 | let path = JsonPath::parse("$.users[*].name").unwrap(); |
| 374 | let values: Vec<_> = any.json_path(&path).collect(); |
| 375 | assert_eq!( |
| 376 | values, |
| 377 | vec![ |
| 378 | &any!("Alice"), |
| 379 | &any!("Bob"), |
| 380 | &any!("Damian"), |
| 381 | &any!("Elise") |
| 382 | ] |
| 383 | ); |
| 384 | } |
| 385 | |
| 386 | #[test] |
| 387 | fn eval_member_slice() { |
| 388 | let any = mixed_sample(); |
| 389 | let path = JsonPath::parse("$.users[1:3].nick").unwrap(); |
| 390 | let values: Vec<_> = any.json_path(&path).collect(); |
| 391 | assert_eq!(values, vec![&any!("boreas"), &any!("crocodile91")]); |
| 392 | } |
| 393 | |
| 394 | #[test] |
| 395 | fn eval_index_union() { |
| 396 | let any = mixed_sample(); |
| 397 | let path = JsonPath::parse("$.users[1,3].name").unwrap(); |
| 398 | let values: Vec<_> = any.json_path(&path).collect(); |
| 399 | assert_eq!(values, vec![&any!("Bob"), &any!("Damian")]); |
| 400 | } |
| 401 | |
| 402 | #[test] |
| 403 | fn eval_member_union() { |
| 404 | let any = mixed_sample(); |
| 405 | let path = JsonPath::parse("$.users[0]['name','surname']").unwrap(); |
| 406 | let values: Vec<_> = any.json_path(&path).collect(); |
| 407 | assert_eq!(values, vec![&any!("Alice"), &any!("Smith")]); |
| 408 | } |
| 409 | |
| 410 | #[test] |
| 411 | fn eval_descent_flat() { |
| 412 | let any = mixed_sample(); |
| 413 | let path = JsonPath::parse("$.users..name").unwrap(); |
| 414 | let values: Vec<_> = any.json_path(&path).collect(); |
| 415 | assert_eq!( |
| 416 | values, |
| 417 | vec![ |
| 418 | &any!("Alice"), |
| 419 | &any!("Bob"), |
| 420 | &any!("Damian"), |
| 421 | &any!("Elise") |
| 422 | ] |
| 423 | ); |
| 424 | } |
| 425 | |
| 426 | #[test] |
| 427 | fn eval_descent_multi_level() { |
| 428 | let any = any!({ |
| 429 | "a": { |
| 430 | "b1": { |
| 431 | "c": { |
| 432 | "f": { |
| 433 | "name": "Alice" |
| 434 | } |
| 435 | } |
| 436 | }, |
| 437 | "b2": { |
| 438 | "d": { |
| 439 | "c": { |
| 440 | "g": { |
| 441 | "h": { |
| 442 | "name": "Bob" |
| 443 | } |
| 444 | } |
| 445 | } |
| 446 | } |
| 447 | } |
| 448 | } |
| 449 | }); |
| 450 | let path = JsonPath::parse("$..c..name").unwrap(); |
| 451 | let mut values: Vec<_> = any.json_path(&path).map(|any| any.to_string()).collect(); |
| 452 | values.sort(); |
| 453 | assert_eq!(values, vec!["Alice".to_string(), "Bob".into()]); |
| 454 | } |
| 455 | } |
| 456 | |
amadan