yaml_rt_core/
pointer.rs

1use std::collections::HashSet;
2use std::fmt;
3
4use crate::{NodeId, ResolvedScalar, SemanticKind, 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}
177
178impl PointerError {
179    pub(crate) fn new(
180        pointer: impl Into<String>,
181        token_index: Option<usize>,
182        kind: PointerErrorKind,
183        message: impl Into<String>,
184    ) -> Self {
185        Self {
186            pointer: pointer.into(),
187            token_index,
188            kind,
189            message: message.into(),
190        }
191    }
192
193    /// Returns the pointer associated with the failure.
194    #[must_use]
195    pub fn pointer(&self) -> &str {
196        &self.pointer
197    }
198
199    /// Returns the zero-based failing token index, when applicable.
200    #[must_use]
201    pub const fn token_index(&self) -> Option<usize> {
202        self.token_index
203    }
204
205    /// Returns the failure classification.
206    #[must_use]
207    pub const fn kind(&self) -> PointerErrorKind {
208        self.kind
209    }
210}
211
212impl fmt::Display for PointerError {
213    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
214        if self.pointer.is_empty() {
215            write!(formatter, "cannot resolve document root: {}", self.message)
216        } else {
217            write!(
218                formatter,
219                "cannot resolve JSON Pointer {:?}: {}",
220                self.pointer, self.message
221            )
222        }
223    }
224}
225
226impl std::error::Error for PointerError {}
227
228#[derive(Debug, Clone, Copy)]
229pub(crate) struct MappingMatch {
230    pub(crate) key: NodeId,
231    pub(crate) value: NodeId,
232}
233
234impl YamlDoc {
235    /// Resolves a JSON Pointer against one YAML document representation graph.
236    ///
237    /// Alias nodes are traversed when another reference token remains. A
238    /// pointer that ends on an alias returns the alias occurrence itself.
239    ///
240    /// # Errors
241    ///
242    /// Returns an error when the document, path, or selected mapping or sequence
243    /// element does not exist, or when alias traversal fails.
244    pub fn resolve_pointer(
245        &self,
246        document: usize,
247        pointer: &JsonPointer,
248    ) -> Result<NodeId, PointerError> {
249        let mut current = self
250            .document_root(document)
251            .map_err(|error| {
252                PointerError::new(
253                    pointer.as_str(),
254                    None,
255                    PointerErrorKind::Semantic,
256                    error.to_string(),
257                )
258            })?
259            .ok_or_else(|| {
260                PointerError::new(
261                    pointer.as_str(),
262                    None,
263                    PointerErrorKind::EmptyDocument,
264                    "selected YAML document has no root node",
265                )
266            })?;
267
268        for (index, token) in pointer.tokens().iter().enumerate() {
269            current = self.resolve_aliases_for_pointer(current, pointer, index)?;
270            current = match self.semantic_kind(current) {
271                Some(SemanticKind::Mapping { .. }) => {
272                    self.mapping_match(current, token, pointer, index)?
273                        .ok_or_else(|| {
274                            PointerError::new(
275                                pointer.as_str(),
276                                Some(index),
277                                PointerErrorKind::MissingValue,
278                                format!("mapping has no member {:?}", token.as_str()),
279                            )
280                        })?
281                        .value
282                }
283                Some(SemanticKind::Sequence { .. }) => {
284                    let items = self.sequence_items(current).collect::<Vec<_>>();
285                    let item_index = parse_sequence_index(token, pointer, index, false)?;
286                    *items.get(item_index).ok_or_else(|| {
287                        PointerError::new(
288                            pointer.as_str(),
289                            Some(index),
290                            PointerErrorKind::IndexOutOfBounds,
291                            format!(
292                                "sequence index {item_index} is out of bounds for length {}",
293                                items.len()
294                            ),
295                        )
296                    })?
297                }
298                Some(SemanticKind::Scalar { .. } | SemanticKind::Alias) => {
299                    return Err(PointerError::new(
300                        pointer.as_str(),
301                        Some(index),
302                        PointerErrorKind::TypeMismatch,
303                        format!(
304                            "token {:?} cannot be evaluated against a scalar",
305                            token.as_str()
306                        ),
307                    ));
308                }
309                Some(SemanticKind::Document) | None => {
310                    return Err(PointerError::new(
311                        pointer.as_str(),
312                        Some(index),
313                        PointerErrorKind::TypeMismatch,
314                        "token cannot be evaluated against this YAML node",
315                    ));
316                }
317            };
318        }
319        Ok(current)
320    }
321
322    pub(crate) fn resolve_aliases_for_pointer(
323        &self,
324        mut node: NodeId,
325        pointer: &JsonPointer,
326        token_index: usize,
327    ) -> Result<NodeId, PointerError> {
328        let mut seen = HashSet::new();
329        while matches!(self.semantic_kind(node), Some(SemanticKind::Alias)) {
330            if !seen.insert(node) {
331                return Err(PointerError::new(
332                    pointer.as_str(),
333                    Some(token_index),
334                    PointerErrorKind::AliasCycle,
335                    "cyclic alias chain",
336                ));
337            }
338            node = self.resolve_alias(node).ok_or_else(|| {
339                PointerError::new(
340                    pointer.as_str(),
341                    Some(token_index),
342                    PointerErrorKind::UnresolvedAlias,
343                    format!(
344                        "unresolved alias `*{}`",
345                        self.alias_name(node).unwrap_or_default()
346                    ),
347                )
348            })?;
349        }
350        Ok(node)
351    }
352
353    pub(crate) fn mapping_match(
354        &self,
355        mapping: NodeId,
356        token: &ReferenceToken,
357        pointer: &JsonPointer,
358        token_index: usize,
359    ) -> Result<Option<MappingMatch>, PointerError> {
360        let mut found = None;
361        for (key, value) in self.mapping_entries(mapping) {
362            let resolved_key = self.resolve_aliases_for_pointer(key, pointer, token_index)?;
363            let Some(SemanticKind::Scalar { style }) = self.semantic_kind(resolved_key) else {
364                return Err(non_string_key_error(pointer, token_index));
365            };
366            let scalar = self.scalar_value(resolved_key).map_err(|error| {
367                PointerError::new(
368                    pointer.as_str(),
369                    Some(token_index),
370                    PointerErrorKind::Semantic,
371                    error.to_string(),
372                )
373            })?;
374            let tag = self.resolved_tag(resolved_key).map_err(|error| {
375                PointerError::new(
376                    pointer.as_str(),
377                    Some(token_index),
378                    PointerErrorKind::Semantic,
379                    error.to_string(),
380                )
381            })?;
382            let resolved = resolve_scalar(&scalar, style, tag.as_deref())
383                .map_err(|_| non_string_key_error(pointer, token_index))?;
384            if resolved != ResolvedScalar::String {
385                return Err(non_string_key_error(pointer, token_index));
386            }
387            if scalar == token.as_str() {
388                if found.is_some() {
389                    return Err(PointerError::new(
390                        pointer.as_str(),
391                        Some(token_index),
392                        PointerErrorKind::AmbiguousKey,
393                        format!(
394                            "mapping contains multiple matching keys {:?}",
395                            token.as_str()
396                        ),
397                    ));
398                }
399                found = Some(MappingMatch { key, value });
400            }
401        }
402        Ok(found)
403    }
404}
405
406fn non_string_key_error(pointer: &JsonPointer, token_index: usize) -> PointerError {
407    PointerError::new(
408        pointer.as_str(),
409        Some(token_index),
410        PointerErrorKind::NonStringKey,
411        "cannot traverse a mapping containing non-string keys",
412    )
413}
414
415pub(crate) fn parse_sequence_index(
416    token: &ReferenceToken,
417    pointer: &JsonPointer,
418    token_index: usize,
419    allow_dash: bool,
420) -> Result<usize, PointerError> {
421    let value = token.as_str();
422    if value == "-" {
423        return if allow_dash {
424            Ok(usize::MAX)
425        } else {
426            Err(PointerError::new(
427                pointer.as_str(),
428                Some(token_index),
429                PointerErrorKind::DashNotAllowed,
430                "`-` is allowed only as the final add destination token",
431            ))
432        };
433    }
434    if value.is_empty()
435        || !value.bytes().all(|byte| byte.is_ascii_digit())
436        || value.len() > 1 && value.starts_with('0')
437    {
438        return Err(PointerError::new(
439            pointer.as_str(),
440            Some(token_index),
441            PointerErrorKind::InvalidIndex,
442            format!("{value:?} is not a canonical sequence index"),
443        ));
444    }
445    value.parse().map_err(|_| {
446        PointerError::new(
447            pointer.as_str(),
448            Some(token_index),
449            PointerErrorKind::InvalidIndex,
450            format!("sequence index {value:?} overflows this platform"),
451        )
452    })
453}
454
455#[cfg(test)]
456mod tests {
457    use super::*;
458
459    #[test]
460    fn parses_and_decodes_plain_json_pointers() {
461        for (input, expected) in [
462            ("", vec![]),
463            ("/foo/0", vec!["foo", "0"]),
464            ("/a~1b", vec!["a/b"]),
465            ("/m~0n", vec!["m~n"]),
466            ("/~01", vec!["~1"]),
467        ] {
468            let pointer = JsonPointer::parse(input).unwrap();
469            assert_eq!(
470                pointer
471                    .tokens()
472                    .iter()
473                    .map(ReferenceToken::as_str)
474                    .collect::<Vec<_>>(),
475                expected
476            );
477        }
478    }
479
480    #[test]
481    fn rejects_invalid_pointer_syntax() {
482        for input in ["foo", "/foo/~", "/foo/~2"] {
483            assert!(JsonPointer::parse(input).is_err(), "{input}");
484        }
485    }
486
487    #[test]
488    fn resolves_mappings_sequences_and_escaped_keys() {
489        let doc = YamlDoc::parse("'a/b':\n  - zero\n  - one\n'm~n': value\n").expect("valid YAML");
490        let pointer = JsonPointer::parse("/a~1b/1").unwrap();
491        let node = doc.resolve_pointer(0, &pointer).unwrap();
492        assert_eq!(doc.scalar_value(node).unwrap(), "one");
493        let pointer = JsonPointer::parse("/m~0n").unwrap();
494        assert_eq!(
495            doc.scalar_value(doc.resolve_pointer(0, &pointer).unwrap())
496                .unwrap(),
497            "value"
498        );
499    }
500
501    #[test]
502    fn traverses_aliases_but_returns_a_terminal_alias() {
503        let doc =
504            YamlDoc::parse("defaults: &defaults\n  timeout: 30\nservice:\n  config: *defaults\n")
505                .unwrap();
506        let terminal = doc
507            .resolve_pointer(0, &JsonPointer::parse("/service/config").unwrap())
508            .unwrap();
509        assert_eq!(doc.alias_name(terminal), Some("defaults"));
510        let traversed = doc
511            .resolve_pointer(0, &JsonPointer::parse("/service/config/timeout").unwrap())
512            .unwrap();
513        assert_eq!(doc.scalar_value(traversed).unwrap(), "30");
514    }
515
516    #[test]
517    fn rejects_noncanonical_indices_and_non_string_keys() {
518        let sequence = YamlDoc::parse("[a, b]\n").unwrap();
519        for path in ["/01", "/-1", "/+1", "/ ", "/-"] {
520            assert!(
521                sequence
522                    .resolve_pointer(0, &JsonPointer::parse(path).unwrap())
523                    .is_err(),
524                "{path}"
525            );
526        }
527        let mapping = YamlDoc::parse("1: value\n").unwrap();
528        let error = mapping
529            .resolve_pointer(0, &JsonPointer::parse("/1").unwrap())
530            .unwrap_err();
531        assert_eq!(error.kind(), PointerErrorKind::NonStringKey);
532    }
533
534    #[test]
535    fn duplicate_matching_keys_are_ambiguous() {
536        let doc = YamlDoc::parse("foo: one\nfoo: two\n").unwrap();
537        let error = doc
538            .resolve_pointer(0, &JsonPointer::parse("/foo").unwrap())
539            .unwrap_err();
540        assert_eq!(error.kind(), PointerErrorKind::AmbiguousKey);
541    }
542}
yaml_rt_core/pointer.rs

yaml_rt_core/
pointer.rs
