yaml_rt_core/
pointer.rs

1use std::collections::HashSet;
2use std::fmt;
3
4use crate::{NodeId, ResolvedScalar, SemanticKind, Span, YamlDoc, resolve_scalar};
5
6/// One decoded RFC 6901 reference token.
7#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
8pub struct ReferenceToken(String);
9
10impl ReferenceToken {
11    /// Returns the decoded token text.
12    #[must_use]
13    pub fn as_str(&self) -> &str {
14        &self.0
15    }
16}
17
18/// A parsed plain RFC 6901 JSON Pointer.
19#[derive(Debug, Clone, PartialEq, Eq)]
20pub struct JsonPointer {
21    original: String,
22    tokens: Vec<ReferenceToken>,
23}
24
25impl JsonPointer {
26    /// Parses a plain JSON Pointer. URI fragment syntax is not accepted.
27    ///
28    /// # Errors
29    ///
30    /// Returns an error when `input` is not valid RFC 6901 pointer syntax.
31    pub fn parse(input: &str) -> Result<Self, PointerError> {
32        if input.is_empty() {
33            return Ok(Self {
34                original: String::new(),
35                tokens: Vec::new(),
36            });
37        }
38        if !input.starts_with('/') {
39            return Err(PointerError::new(
40                input,
41                None,
42                PointerErrorKind::InvalidSyntax,
43                "a non-empty JSON Pointer must begin with `/`",
44            ));
45        }
46        let tokens = input[1..]
47            .split('/')
48            .enumerate()
49            .map(|(index, token)| {
50                decode_token(token).map(ReferenceToken).map_err(|escape| {
51                    PointerError::new(
52                        input,
53                        Some(index),
54                        PointerErrorKind::InvalidEscape,
55                        format!("invalid escape `{escape}`"),
56                    )
57                })
58            })
59            .collect::<Result<Vec<_>, _>>()?;
60        Ok(Self {
61            original: input.to_owned(),
62            tokens,
63        })
64    }
65
66    /// Returns the original pointer spelling.
67    #[must_use]
68    pub fn as_str(&self) -> &str {
69        &self.original
70    }
71
72    /// Returns the decoded reference tokens.
73    #[must_use]
74    pub fn tokens(&self) -> &[ReferenceToken] {
75        &self.tokens
76    }
77
78    /// Returns whether this pointer identifies the document root.
79    #[must_use]
80    pub fn is_root(&self) -> bool {
81        self.tokens.is_empty()
82    }
83
84    /// Returns whether this pointer is a proper token-prefix of `other`.
85    #[must_use]
86    pub fn is_proper_prefix_of(&self, other: &Self) -> bool {
87        self.tokens.len() < other.tokens.len() && other.tokens.starts_with(&self.tokens)
88    }
89
90    pub(crate) fn parent(&self) -> Option<(Self, &ReferenceToken)> {
91        let (last, parent) = self.tokens.split_last()?;
92        let original = encode_tokens(parent);
93        Some((
94            Self {
95                original,
96                tokens: parent.to_vec(),
97            },
98            last,
99        ))
100    }
101}
102
103impl std::str::FromStr for JsonPointer {
104    type Err = PointerError;
105
106    fn from_str(value: &str) -> Result<Self, Self::Err> {
107        Self::parse(value)
108    }
109}
110
111fn decode_token(token: &str) -> Result<String, String> {
112    let mut output = String::with_capacity(token.len());
113    let mut characters = token.chars();
114    while let Some(character) = characters.next() {
115        if character != '~' {
116            output.push(character);
117            continue;
118        }
119        match characters.next() {
120            Some('0') => output.push('~'),
121            Some('1') => output.push('/'),
122            Some(other) => return Err(format!("~{other}")),
123            None => return Err("~".to_owned()),
124        }
125    }
126    Ok(output)
127}
128
129fn encode_tokens(tokens: &[ReferenceToken]) -> String {
130    let mut pointer = String::new();
131    for token in tokens {
132        pointer.push('/');
133        pointer.push_str(&token.as_str().replace('~', "~0").replace('/', "~1"));
134    }
135    pointer
136}
137
138/// Classification of a JSON Pointer parse or resolution failure.
139#[derive(Debug, Clone, Copy, PartialEq, Eq)]
140pub enum PointerErrorKind {
141    /// The whole pointer has invalid syntax.
142    InvalidSyntax,
143    /// A reference token contains an invalid `~` escape.
144    InvalidEscape,
145    /// The selected YAML document has no root node.
146    EmptyDocument,
147    /// A mapping member or sequence item does not exist.
148    MissingValue,
149    /// A reference token was evaluated against a scalar.
150    TypeMismatch,
151    /// A sequence token is not a canonical unsigned index.
152    InvalidIndex,
153    /// A canonical sequence index is larger than the sequence.
154    IndexOutOfBounds,
155    /// The special `-` token was used outside an add destination.
156    DashNotAllowed,
157    /// A traversed YAML mapping contains a non-string key.
158    NonStringKey,
159    /// More than one mapping key matches the token.
160    AmbiguousKey,
161    /// An alias has no preceding anchor binding.
162    UnresolvedAlias,
163    /// An alias chain is cyclic.
164    AliasCycle,
165    /// A YAML semantic operation failed during resolution.
166    Semantic,
167}
168
169/// Structured JSON Pointer parse or resolution error.
170#[derive(Debug, Clone, PartialEq, Eq)]
171pub struct PointerError {
172    pointer: String,
173    token_index: Option<usize>,
174    kind: PointerErrorKind,
175    message: String,
176    source_span: Option<Span>,
177}
178
179impl PointerError {
180    pub(crate) fn new(
181        pointer: impl Into<String>,
182        token_index: Option<usize>,
183        kind: PointerErrorKind,
184        message: impl Into<String>,
185    ) -> Self {
186        Self {
187            pointer: pointer.into(),
188            token_index,
189            kind,
190            message: message.into(),
191            source_span: None,
192        }
193    }
194
195    fn with_source_span(mut self, source_span: Span) -> Self {
196        self.source_span = Some(source_span);
197        self
198    }
199
200    /// Returns the pointer associated with the failure.
201    #[must_use]
202    pub fn pointer(&self) -> &str {
203        &self.pointer
204    }
205
206    /// Returns the zero-based failing token index, when applicable.
207    #[must_use]
208    pub const fn token_index(&self) -> Option<usize> {
209        self.token_index
210    }
211
212    /// Returns the failure classification.
213    #[must_use]
214    pub const fn kind(&self) -> PointerErrorKind {
215        self.kind
216    }
217
218    /// Returns the relevant YAML source span for a resolution failure.
219    #[must_use]
220    pub const fn source_span(&self) -> Option<Span> {
221        self.source_span
222    }
223}
224
225impl fmt::Display for PointerError {
226    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
227        if self.pointer.is_empty() {
228            write!(formatter, "cannot resolve document root: {}", self.message)
229        } else {
230            write!(
231                formatter,
232                "cannot resolve JSON Pointer {:?}: {}",
233                self.pointer, self.message
234            )
235        }
236    }
237}
238
239impl std::error::Error for PointerError {}
240
241#[derive(Debug, Clone, Copy)]
242pub(crate) struct MappingMatch {
243    pub(crate) key: NodeId,
244    pub(crate) value: NodeId,
245}
246
247impl YamlDoc {
248    /// Resolves a JSON Pointer against one YAML document representation graph.
249    ///
250    /// Alias nodes are traversed when another reference token remains. A
251    /// pointer that ends on an alias returns the alias occurrence itself.
252    ///
253    /// # Errors
254    ///
255    /// Returns an error when the document, path, or selected mapping or sequence
256    /// element does not exist, or when alias traversal fails.
257    pub fn resolve_pointer(
258        &self,
259        document: usize,
260        pointer: &JsonPointer,
261    ) -> Result<NodeId, PointerError> {
262        let mut current = self
263            .document_root(document)
264            .map_err(|error| {
265                PointerError::new(
266                    pointer.as_str(),
267                    None,
268                    PointerErrorKind::Semantic,
269                    error.to_string(),
270                )
271            })?
272            .ok_or_else(|| {
273                PointerError::new(
274                    pointer.as_str(),
275                    None,
276                    PointerErrorKind::EmptyDocument,
277                    "selected YAML document has no root node",
278                )
279            })?;
280
281        for (index, token) in pointer.tokens().iter().enumerate() {
282            current = self.resolve_aliases_for_pointer(current, pointer, index)?;
283            current = match self.semantic_kind(current) {
284                Some(SemanticKind::Mapping { .. }) => {
285                    self.mapping_match(current, token, pointer, index)?
286                        .ok_or_else(|| {
287                            PointerError::new(
288                                pointer.as_str(),
289                                Some(index),
290                                PointerErrorKind::MissingValue,
291                                format!("mapping has no member {:?}", token.as_str()),
292                            )
293                        })?
294                        .value
295                }
296                Some(SemanticKind::Sequence { .. }) => {
297                    let items = self.sequence_items(current).collect::<Vec<_>>();
298                    let item_index = parse_sequence_index(token, pointer, index, false)?;
299                    *items.get(item_index).ok_or_else(|| {
300                        PointerError::new(
301                            pointer.as_str(),
302                            Some(index),
303                            PointerErrorKind::IndexOutOfBounds,
304                            format!(
305                                "sequence index {item_index} is out of bounds for length {}",
306                                items.len()
307                            ),
308                        )
309                    })?
310                }
311                Some(SemanticKind::Scalar { .. } | SemanticKind::Alias) => {
312                    return Err(PointerError::new(
313                        pointer.as_str(),
314                        Some(index),
315                        PointerErrorKind::TypeMismatch,
316                        format!(
317                            "token {:?} cannot be evaluated against a scalar",
318                            token.as_str()
319                        ),
320                    ));
321                }
322                Some(SemanticKind::Document) | None => {
323                    return Err(PointerError::new(
324                        pointer.as_str(),
325                        Some(index),
326                        PointerErrorKind::TypeMismatch,
327                        "token cannot be evaluated against this YAML node",
328                    ));
329                }
330            };
331        }
332        Ok(current)
333    }
334
335    pub(crate) fn resolve_aliases_for_pointer(
336        &self,
337        mut node: NodeId,
338        pointer: &JsonPointer,
339        token_index: usize,
340    ) -> Result<NodeId, PointerError> {
341        let mut seen = HashSet::new();
342        while matches!(self.semantic_kind(node), Some(SemanticKind::Alias)) {
343            if !seen.insert(node) {
344                let mut error = PointerError::new(
345                    pointer.as_str(),
346                    Some(token_index),
347                    PointerErrorKind::AliasCycle,
348                    "cyclic alias chain",
349                );
350                if let Some(span) = self.node(node).map(|node| node.span()) {
351                    error = error.with_source_span(span);
352                }
353                return Err(error);
354            }
355            let alias = node;
356            node = self.resolve_alias(alias).ok_or_else(|| {
357                let mut error = PointerError::new(
358                    pointer.as_str(),
359                    Some(token_index),
360                    PointerErrorKind::UnresolvedAlias,
361                    format!(
362                        "unresolved alias `*{}`",
363                        self.alias_name(alias).unwrap_or_default()
364                    ),
365                );
366                if let Some(span) = self.node(alias).map(|node| node.span()) {
367                    error = error.with_source_span(span);
368                }
369                error
370            })?;
371        }
372        Ok(node)
373    }
374
375    pub(crate) fn mapping_match(
376        &self,
377        mapping: NodeId,
378        token: &ReferenceToken,
379        pointer: &JsonPointer,
380        token_index: usize,
381    ) -> Result<Option<MappingMatch>, PointerError> {
382        let mut found = None;
383        for (key, value) in self.mapping_entries(mapping) {
384            let resolved_key = self.resolve_aliases_for_pointer(key, pointer, token_index)?;
385            let Some(SemanticKind::Scalar { style }) = self.semantic_kind(resolved_key) else {
386                return Err(non_string_key_error(pointer, token_index));
387            };
388            let scalar = self.scalar_value(resolved_key).map_err(|error| {
389                PointerError::new(
390                    pointer.as_str(),
391                    Some(token_index),
392                    PointerErrorKind::Semantic,
393                    error.to_string(),
394                )
395            })?;
396            let tag = self.resolved_tag(resolved_key).map_err(|error| {
397                PointerError::new(
398                    pointer.as_str(),
399                    Some(token_index),
400                    PointerErrorKind::Semantic,
401                    error.to_string(),
402                )
403            })?;
404            let resolved = resolve_scalar(&scalar, style, tag.as_deref())
405                .map_err(|_| non_string_key_error(pointer, token_index))?;
406            if resolved != ResolvedScalar::String {
407                return Err(non_string_key_error(pointer, token_index));
408            }
409            if scalar == token.as_str() {
410                if found.is_some() {
411                    return Err(PointerError::new(
412                        pointer.as_str(),
413                        Some(token_index),
414                        PointerErrorKind::AmbiguousKey,
415                        format!(
416                            "mapping contains multiple matching keys {:?}",
417                            token.as_str()
418                        ),
419                    ));
420                }
421                found = Some(MappingMatch { key, value });
422            }
423        }
424        Ok(found)
425    }
426}
427
428fn non_string_key_error(pointer: &JsonPointer, token_index: usize) -> PointerError {
429    PointerError::new(
430        pointer.as_str(),
431        Some(token_index),
432        PointerErrorKind::NonStringKey,
433        "cannot traverse a mapping containing non-string keys",
434    )
435}
436
437pub(crate) fn parse_sequence_index(
438    token: &ReferenceToken,
439    pointer: &JsonPointer,
440    token_index: usize,
441    allow_dash: bool,
442) -> Result<usize, PointerError> {
443    let value = token.as_str();
444    if value == "-" {
445        return if allow_dash {
446            Ok(usize::MAX)
447        } else {
448            Err(PointerError::new(
449                pointer.as_str(),
450                Some(token_index),
451                PointerErrorKind::DashNotAllowed,
452                "`-` is allowed only as the final add destination token",
453            ))
454        };
455    }
456    if value.is_empty()
457        || !value.bytes().all(|byte| byte.is_ascii_digit())
458        || value.len() > 1 && value.starts_with('0')
459    {
460        return Err(PointerError::new(
461            pointer.as_str(),
462            Some(token_index),
463            PointerErrorKind::InvalidIndex,
464            format!("{value:?} is not a canonical sequence index"),
465        ));
466    }
467    value.parse().map_err(|_| {
468        PointerError::new(
469            pointer.as_str(),
470            Some(token_index),
471            PointerErrorKind::InvalidIndex,
472            format!("sequence index {value:?} overflows this platform"),
473        )
474    })
475}
476
477#[cfg(test)]
478mod tests {
479    use super::*;
480
481    #[test]
482    fn parses_and_decodes_plain_json_pointers() {
483        for (input, expected) in [
484            ("", vec![]),
485            ("/foo/0", vec!["foo", "0"]),
486            ("/a~1b", vec!["a/b"]),
487            ("/m~0n", vec!["m~n"]),
488            ("/~01", vec!["~1"]),
489        ] {
490            let pointer = JsonPointer::parse(input).unwrap();
491            assert_eq!(
492                pointer
493                    .tokens()
494                    .iter()
495                    .map(ReferenceToken::as_str)
496                    .collect::<Vec<_>>(),
497                expected
498            );
499        }
500    }
501
502    #[test]
503    fn rejects_invalid_pointer_syntax() {
504        for input in ["foo", "/foo/~", "/foo/~2"] {
505            assert!(JsonPointer::parse(input).is_err(), "{input}");
506        }
507    }
508
509    #[test]
510    fn resolves_mappings_sequences_and_escaped_keys() {
511        let doc = YamlDoc::parse("'a/b':\n  - zero\n  - one\n'm~n': value\n").expect("valid YAML");
512        let pointer = JsonPointer::parse("/a~1b/1").unwrap();
513        let node = doc.resolve_pointer(0, &pointer).unwrap();
514        assert_eq!(doc.scalar_value(node).unwrap(), "one");
515        let pointer = JsonPointer::parse("/m~0n").unwrap();
516        assert_eq!(
517            doc.scalar_value(doc.resolve_pointer(0, &pointer).unwrap())
518                .unwrap(),
519            "value"
520        );
521    }
522
523    #[test]
524    fn traverses_aliases_but_returns_a_terminal_alias() {
525        let doc =
526            YamlDoc::parse("defaults: &defaults\n  timeout: 30\nservice:\n  config: *defaults\n")
527                .unwrap();
528        let terminal = doc
529            .resolve_pointer(0, &JsonPointer::parse("/service/config").unwrap())
530            .unwrap();
531        assert_eq!(doc.alias_name(terminal), Some("defaults"));
532        let traversed = doc
533            .resolve_pointer(0, &JsonPointer::parse("/service/config/timeout").unwrap())
534            .unwrap();
535        assert_eq!(doc.scalar_value(traversed).unwrap(), "30");
536    }
537
538    #[test]
539    fn unresolved_alias_errors_preserve_source_spans_through_edits() {
540        let doc = YamlDoc::parse("bad: *missing\n").unwrap();
541        let pointer = JsonPointer::parse("/bad/value").unwrap();
542        let error = doc.resolve_pointer(0, &pointer).unwrap_err();
543        assert_eq!(error.kind(), PointerErrorKind::UnresolvedAlias);
544        assert_eq!(error.source_span(), Some(Span::new(5, 13)));
545
546        let mut edited = doc;
547        let error = edited.remove_at(0, &pointer).unwrap_err();
548        assert_eq!(error.source_span(), Some(Span::new(5, 13)));
549    }
550
551    #[test]
552    fn rejects_noncanonical_indices_and_non_string_keys() {
553        let sequence = YamlDoc::parse("[a, b]\n").unwrap();
554        for path in ["/01", "/-1", "/+1", "/ ", "/-"] {
555            assert!(
556                sequence
557                    .resolve_pointer(0, &JsonPointer::parse(path).unwrap())
558                    .is_err(),
559                "{path}"
560            );
561        }
562        let mapping = YamlDoc::parse("1: value\n").unwrap();
563        let error = mapping
564            .resolve_pointer(0, &JsonPointer::parse("/1").unwrap())
565            .unwrap_err();
566        assert_eq!(error.kind(), PointerErrorKind::NonStringKey);
567    }
568
569    #[test]
570    fn duplicate_matching_keys_are_ambiguous() {
571        let doc = YamlDoc::parse("foo: one\nfoo: two\n").unwrap();
572        let error = doc
573            .resolve_pointer(0, &JsonPointer::parse("/foo").unwrap())
574            .unwrap_err();
575        assert_eq!(error.kind(), PointerErrorKind::AmbiguousKey);
576    }
577}
yaml_rt_core/pointer.rs

yaml_rt_core/
pointer.rs
