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

yaml_rt_core/
pointer.rs
