1use std::fmt::{self, Write as _};
16
17use fig::Value;
18
19#[derive(Clone, Debug, PartialEq, Eq, Hash)]
22pub enum Seg {
23 Key(String),
24 Index(usize),
25}
26
27#[derive(Debug, Clone, PartialEq, Eq, Hash)]
33pub struct PathPat(pub Vec<SegPat>);
34
35#[derive(Debug, Clone, PartialEq, Eq, Hash)]
37pub enum SegPat {
38 Key(String),
40 AnyKey,
42 Index(usize),
44 EachItem,
46 AnyDepth,
50}
51
52impl PathPat {
53 pub fn key(name: impl Into<String>) -> Self {
55 PathPat(vec![SegPat::Key(name.into())])
56 }
57
58 pub fn each_item_of(name: impl Into<String>) -> Self {
61 PathPat(vec![SegPat::Key(name.into()), SegPat::EachItem])
62 }
63
64 pub fn subtree_of(name: impl Into<String>) -> Self {
67 PathPat(vec![SegPat::Key(name.into()), SegPat::AnyDepth])
68 }
69
70 pub fn matches(&self, path: &[Seg]) -> bool {
74 matches_from(&self.0, path)
75 }
76
77 pub fn parse(text: &str) -> Result<PathPat, PatternError> {
102 let mut segments = Vec::new();
103 let mut rest = text;
104 let mut offset = 0;
105 let mut key_allowed = true;
109 while !rest.is_empty() {
110 if let Some(after) = rest.strip_prefix('[') {
111 let Some(close) = after.find(']') else {
112 return Err(PatternError::UnclosedIndex { offset });
113 };
114 let inside = &after[..close];
115 segments.push(match inside {
116 "" => SegPat::EachItem,
117 digits => match digits.parse::<usize>() {
118 Ok(index) if digits.bytes().all(|b| b.is_ascii_digit()) => {
119 SegPat::Index(index)
120 }
121 _ => {
122 return Err(PatternError::IndexNotANumber {
123 offset: offset + 1,
124 text: digits.to_owned(),
125 });
126 }
127 },
128 });
129 offset += close + 2;
130 rest = &after[close + 1..];
131 key_allowed = false;
132 if let Some(after_dot) = rest.strip_prefix('.') {
133 offset += 1;
134 rest = after_dot;
135 key_allowed = true;
136 if rest.is_empty() {
137 return Err(PatternError::EmptySegment { offset });
138 }
139 }
140 continue;
141 }
142 if !key_allowed {
143 return Err(PatternError::TextAfterIndex { offset });
144 }
145 let end = rest.find(['.', '[']).unwrap_or(rest.len());
146 let key = &rest[..end];
147 if key.is_empty() {
148 return Err(PatternError::EmptySegment { offset });
149 }
150 segments.push(match key {
151 "*" => SegPat::AnyKey,
152 "**" => SegPat::AnyDepth,
153 key => SegPat::Key(key.to_owned()),
154 });
155 offset += end;
156 rest = &rest[end..];
157 if let Some(after_dot) = rest.strip_prefix('.') {
158 offset += 1;
159 rest = after_dot;
160 if rest.is_empty() {
161 return Err(PatternError::EmptySegment { offset });
162 }
163 } else {
164 key_allowed = false;
165 }
166 }
167 Ok(PathPat(segments))
168 }
169
170 pub fn concrete(&self) -> Option<Vec<Seg>> {
182 self.0
183 .iter()
184 .map(|seg| match seg {
185 SegPat::Key(k) => Some(Seg::Key(k.clone())),
186 SegPat::Index(i) => Some(Seg::Index(*i)),
187 SegPat::AnyKey | SegPat::EachItem | SegPat::AnyDepth => None,
188 })
189 .collect()
190 }
191
192 pub fn is_subsumed_by(&self, other: &PathPat) -> bool {
198 subsumes(&other.0, &self.0)
199 }
200}
201
202impl fmt::Display for PathPat {
203 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
206 let mut first = true;
207 for seg in &self.0 {
208 match seg {
209 SegPat::Key(k) => {
210 if !first {
211 f.write_str(".")?;
212 }
213 f.write_str(k)?;
214 }
215 SegPat::AnyKey => {
216 if !first {
217 f.write_str(".")?;
218 }
219 f.write_str("*")?;
220 }
221 SegPat::AnyDepth => {
222 if !first {
223 f.write_str(".")?;
224 }
225 f.write_str("**")?;
226 }
227 SegPat::Index(i) => write!(f, "[{i}]")?,
228 SegPat::EachItem => f.write_str("[]")?,
229 }
230 first = false;
231 }
232 Ok(())
233 }
234}
235
236#[derive(Debug, Clone, PartialEq, Eq)]
242#[non_exhaustive]
243pub enum PatternError {
244 EmptySegment { offset: usize },
246 UnclosedIndex { offset: usize },
248 IndexNotANumber { offset: usize, text: String },
250 TextAfterIndex { offset: usize },
252}
253
254impl fmt::Display for PatternError {
255 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
256 match self {
257 PatternError::EmptySegment { offset } => {
258 write!(f, "an empty segment at offset {offset}")
259 }
260 PatternError::UnclosedIndex { offset } => {
261 write!(f, "a `[` at offset {offset} with no `]` after it")
262 }
263 PatternError::IndexNotANumber { offset, text } => write!(
264 f,
265 "`[{text}]` at offset {offset} is neither `[]` nor an index"
266 ),
267 PatternError::TextAfterIndex { offset } => write!(
268 f,
269 "text straight after an index at offset {offset}; a `.` has to separate them"
270 ),
271 }
272 }
273}
274
275impl std::error::Error for PatternError {}
276
277pub fn value_at<'v>(value: &'v Value, path: &[Seg]) -> Option<&'v Value> {
295 path.iter().try_fold(value, |node, seg| match seg {
296 Seg::Key(k) => node.get(k.as_str()),
297 Seg::Index(i) => node.as_seq().and_then(|items| items.get(*i)),
298 })
299}
300
301pub fn render_path(path: &[Seg]) -> String {
317 let mut out = String::new();
318 for seg in path {
319 match seg {
320 Seg::Key(k) => {
321 if !out.is_empty() {
322 out.push('.');
323 }
324 out.push_str(k);
325 }
326 Seg::Index(i) => {
329 let _ = write!(out, "[{i}]");
330 }
331 }
332 }
333 out
334}
335
336fn matches_from(pats: &[SegPat], path: &[Seg]) -> bool {
340 let Some((pat, rest)) = pats.split_first() else {
341 return path.is_empty();
342 };
343 if let SegPat::AnyDepth = pat {
344 return (0..=path.len()).any(|taken| matches_from(rest, &path[taken..]));
346 }
347 match path.split_first() {
348 Some((seg, tail)) if seg_matches(pat, seg) => matches_from(rest, tail),
349 _ => false,
350 }
351}
352
353fn subsumes(wide: &[SegPat], narrow: &[SegPat]) -> bool {
359 let Some((pat, rest)) = wide.split_first() else {
360 return narrow.is_empty();
361 };
362 if let SegPat::AnyDepth = pat {
363 return (0..=narrow.len()).any(|taken| subsumes(rest, &narrow[taken..]));
364 }
365 match narrow.split_first() {
366 Some((seg, tail)) if seg_subsumes(pat, seg) => subsumes(rest, tail),
367 _ => false,
368 }
369}
370
371fn seg_subsumes(wide: &SegPat, narrow: &SegPat) -> bool {
373 match (wide, narrow) {
374 (SegPat::Key(a), SegPat::Key(b)) => a == b,
375 (SegPat::AnyKey, SegPat::Key(_) | SegPat::AnyKey) => true,
376 (SegPat::Index(a), SegPat::Index(b)) => a == b,
377 (SegPat::EachItem, SegPat::Index(_) | SegPat::EachItem) => true,
378 (SegPat::AnyDepth, _) => true,
380 _ => false,
381 }
382}
383
384fn seg_matches(pat: &SegPat, seg: &Seg) -> bool {
386 match (pat, seg) {
387 (SegPat::Key(k), Seg::Key(s)) => k == s,
388 (SegPat::AnyKey, Seg::Key(_)) => true,
389 (SegPat::Index(i), Seg::Index(j)) => i == j,
390 (SegPat::EachItem, Seg::Index(_)) => true,
391 (SegPat::AnyDepth, _) => true,
393 _ => false,
394 }
395}
396
397#[cfg(test)]
398mod tests {
399 use super::*;
400
401 fn key(k: &str) -> Seg {
402 Seg::Key(k.into())
403 }
404
405 #[test]
406 fn path_pattern_matches_keys_and_each_item() {
407 let pat = PathPat::each_item_of("audience");
408 assert!(pat.matches(&[key("audience"), Seg::Index(0)]));
409 assert!(pat.matches(&[key("audience"), Seg::Index(3)]));
410 assert!(!pat.matches(&[key("audience")]));
411 assert!(!pat.matches(&[key("tags"), Seg::Index(0)]));
412 }
413
414 #[test]
415 fn subtree_matches_the_key_itself_and_everything_under_it() {
416 let pat = PathPat::subtree_of("meta");
417 assert!(pat.matches(&[key("meta")]));
418 assert!(pat.matches(&[key("meta"), key("author")]));
419 assert!(pat.matches(&[key("meta"), key("tags"), Seg::Index(2)]));
420 assert!(!pat.matches(&[key("other")]));
421 assert!(!pat.matches(&[]));
422 }
423
424 #[test]
425 fn any_depth_matches_a_key_at_an_unknown_depth() {
426 let pat = PathPat(vec![SegPat::AnyDepth, SegPat::Key("title".into())]);
428 assert!(pat.matches(&[key("title")]));
429 assert!(pat.matches(&[key("meta"), key("title")]));
430 assert!(pat.matches(&[key("a"), Seg::Index(0), key("title")]));
431 assert!(!pat.matches(&[key("title"), key("sub")]));
432 }
433
434 #[test]
435 fn any_depth_between_two_fixed_segments() {
436 let pat = PathPat(vec![
437 SegPat::Key("a".into()),
438 SegPat::AnyDepth,
439 SegPat::Key("z".into()),
440 ]);
441 assert!(pat.matches(&[key("a"), key("z")]));
442 assert!(pat.matches(&[key("a"), key("m"), key("z")]));
443 assert!(pat.matches(&[key("a"), key("m"), Seg::Index(1), key("z")]));
444 assert!(!pat.matches(&[key("a"), key("m")]));
445 }
446
447 #[test]
448 fn a_pattern_without_any_depth_still_requires_an_exact_length() {
449 let pat = PathPat::key("meta");
450 assert!(pat.matches(&[key("meta")]));
451 assert!(!pat.matches(&[key("meta"), key("author")]));
452 }
453
454 #[test]
455 fn a_path_renders_the_way_fig_spells_one() {
456 assert_eq!(render_path(&[]), "");
457 assert_eq!(render_path(&[key("title")]), "title");
458 assert_eq!(render_path(&[key("meta"), key("author")]), "meta.author");
459 assert_eq!(
460 render_path(&[key("audience"), Seg::Index(1)]),
461 "audience[1]"
462 );
463 assert_eq!(
465 render_path(&[key("items"), Seg::Index(0), key("title")]),
466 "items[0].title"
467 );
468 assert_eq!(
469 render_path(&[key("grid"), Seg::Index(0), Seg::Index(2)]),
470 "grid[0][2]"
471 );
472 assert_eq!(render_path(&[Seg::Index(3)]), "[3]");
474 }
475
476 fn pat(text: &str) -> PathPat {
477 PathPat::parse(text).unwrap()
478 }
479
480 #[test]
481 fn the_pattern_grammar_reads_every_segment_kind() {
482 assert_eq!(pat(""), PathPat(vec![]));
483 assert_eq!(pat("audience"), PathPat::key("audience"));
484 assert_eq!(pat("audience[]"), PathPat::each_item_of("audience"));
485 assert_eq!(
486 pat("audience[0]"),
487 PathPat(vec![SegPat::Key("audience".into()), SegPat::Index(0)])
488 );
489 assert_eq!(
490 pat("meta.author"),
491 PathPat(vec![
492 SegPat::Key("meta".into()),
493 SegPat::Key("author".into())
494 ])
495 );
496 assert_eq!(
497 pat("meta.*"),
498 PathPat(vec![SegPat::Key("meta".into()), SegPat::AnyKey])
499 );
500 assert_eq!(pat("meta.**"), PathPat::subtree_of("meta"));
501 assert_eq!(
502 pat("**.title"),
503 PathPat(vec![SegPat::AnyDepth, SegPat::Key("title".into())])
504 );
505 assert_eq!(pat("**"), PathPat(vec![SegPat::AnyDepth]));
506 assert_eq!(pat("[]"), PathPat(vec![SegPat::EachItem]));
507 assert_eq!(
508 pat("grid[0][2]"),
509 PathPat(vec![
510 SegPat::Key("grid".into()),
511 SegPat::Index(0),
512 SegPat::Index(2)
513 ])
514 );
515 assert_eq!(
516 pat("items[].title"),
517 PathPat(vec![
518 SegPat::Key("items".into()),
519 SegPat::EachItem,
520 SegPat::Key("title".into())
521 ])
522 );
523 assert_eq!(pat("au*"), PathPat::key("au*"));
525 assert_eq!(pat(" a "), PathPat::key(" a "));
526 assert_eq!(pat("***"), PathPat::key("***"));
527 }
528
529 #[test]
530 fn the_pattern_grammar_refuses_what_it_cannot_read() {
531 assert_eq!(
532 PathPat::parse("a..b"),
533 Err(PatternError::EmptySegment { offset: 2 })
534 );
535 assert_eq!(
536 PathPat::parse(".a"),
537 Err(PatternError::EmptySegment { offset: 0 })
538 );
539 assert_eq!(
540 PathPat::parse("a."),
541 Err(PatternError::EmptySegment { offset: 2 })
542 );
543 assert_eq!(
544 PathPat::parse("a[0]."),
545 Err(PatternError::EmptySegment { offset: 5 })
546 );
547 assert_eq!(
548 PathPat::parse("a[0"),
549 Err(PatternError::UnclosedIndex { offset: 1 })
550 );
551 assert_eq!(
552 PathPat::parse("a[x]"),
553 Err(PatternError::IndexNotANumber {
554 offset: 2,
555 text: "x".into()
556 })
557 );
558 assert_eq!(
559 PathPat::parse("a[-1]"),
560 Err(PatternError::IndexNotANumber {
561 offset: 2,
562 text: "-1".into()
563 })
564 );
565 assert_eq!(
566 PathPat::parse("a[0]b"),
567 Err(PatternError::TextAfterIndex { offset: 4 })
568 );
569 assert!(PathPat::parse("a[$]").is_err());
572 }
573
574 #[test]
575 fn a_pattern_prints_the_way_it_was_written() {
576 for text in [
577 "",
578 "audience",
579 "audience[]",
580 "audience[0]",
581 "meta.author",
582 "meta.*",
583 "meta.**",
584 "**.title",
585 "**",
586 "[]",
587 "grid[0][2]",
588 "items[].title",
589 "[0].a",
590 ] {
591 assert_eq!(pat(text).to_string(), text);
592 }
593 let path = [key("items"), Seg::Index(0), key("title")];
595 assert_eq!(
596 render_path(&path),
597 pat("items[0].title")
598 .concrete()
599 .map(|p| render_path(&p))
600 .unwrap()
601 );
602 }
603
604 #[test]
605 fn a_concrete_path_is_a_pattern_with_no_wildcard() {
606 assert_eq!(
607 pat("meta.author").concrete(),
608 Some(vec![key("meta"), key("author")])
609 );
610 assert_eq!(pat("").concrete(), Some(vec![]));
611 assert_eq!(pat("[3]").concrete(), Some(vec![Seg::Index(3)]));
612 assert_eq!(pat("a.*").concrete(), None);
613 assert_eq!(pat("a[]").concrete(), None);
614 assert_eq!(pat("**").concrete(), None);
615 }
616
617 #[test]
618 fn subsumption_is_sound_and_catches_the_usual_shadows() {
619 let shadowed = |narrow: &str, wide: &str| pat(narrow).is_subsumed_by(&pat(wide));
620 assert!(shadowed("audience", "**"));
622 assert!(shadowed("meta.author", "**"));
623 assert!(shadowed("", "**"));
624 assert!(shadowed("audience[]", "audience[]"));
626 assert!(shadowed("audience[0]", "audience[]"));
627 assert!(shadowed("meta.author", "meta.*"));
628 assert!(shadowed("meta.author", "meta.**"));
629 assert!(shadowed("meta.a.b[0]", "meta.**"));
630 assert!(shadowed("a.**.z", "a.**"));
631 assert!(shadowed("a.**.z", "**.z"));
632 assert!(!shadowed("**", "audience"));
634 assert!(!shadowed("audience", "audience[]"));
635 assert!(!shadowed("audience[]", "audience[0]"));
636 assert!(!shadowed("meta.**", "meta.*"));
637 assert!(!shadowed("meta.**", "meta.author"));
638 assert!(!shadowed("a", "b"));
639 assert!(!shadowed("[]", "*"));
640 assert!(!shadowed("meta.*", "meta.author"));
641 }
642
643 #[test]
644 fn value_at_walks_keys_and_indexes() {
645 let document = fig::Document::parse(
646 b"items:\n - title: one\n - title: two\nk: v\n",
647 fig_yaml::format().unwrap(),
648 )
649 .unwrap()
650 .to_value()
651 .unwrap();
652 assert_eq!(
653 value_at(&document, &[key("items"), Seg::Index(1), key("title")]),
654 Some(&Value::Str("two".into()))
655 );
656 assert_eq!(
657 value_at(&document, &[key("k")]),
658 Some(&Value::Str("v".into()))
659 );
660 assert_eq!(value_at(&document, &[key("items"), Seg::Index(2)]), None);
661 assert_eq!(value_at(&document, &[key("items"), key("0")]), None);
663 assert_eq!(value_at(&document, &[Seg::Index(0)]), None);
664 assert_eq!(value_at(&document, &[]), Some(&document));
665 }
666
667 #[test]
668 fn any_key_does_not_match_an_index() {
669 let pat = PathPat(vec![SegPat::AnyKey]);
670 assert!(pat.matches(&[key("whatever")]));
671 assert!(!pat.matches(&[Seg::Index(0)]));
672 }
673}