Skip to main content

yaml_rt_rfc9535/
lib.rs

1//! Native RFC 9535 `JSONPath` queries over yaml-rt semantic documents.
2//!
3//! Queries are parsed once and can be evaluated repeatedly without converting
4//! YAML into an intermediate JSON value tree.
5//!
6//! ```
7//! use yaml_rt_core::YamlDoc;
8//! use yaml_rt_rfc9535::JsonPath;
9//!
10//! # fn main() -> Result<(), Box<dyn std::error::Error>> {
11//! let doc = YamlDoc::parse("users: [{name: Ada}, {name: Linus}]\n")?;
12//! let path = JsonPath::parse("$.users[*].name")?;
13//! let matches = path.query(&doc, 0)?;
14//! let pointers = matches
15//!     .iter()
16//!     .map(|matched| matched.pointer().as_str())
17//!     .collect::<Vec<_>>();
18//! assert_eq!(pointers, ["/users/0/name", "/users/1/name"]);
19//! # Ok(())
20//! # }
21//! ```
22
23use std::cmp::Ordering;
24use std::collections::HashSet;
25use std::fmt;
26
27use regex::Regex;
28use yaml_rt_core::{
29    JsonPointer, NodeId, ResolvedScalar, SemanticKind, Span, YamlDoc, YamlNumber, YamlScalarStyle,
30    resolve_scalar, semantically_equal,
31};
32
33const MAX_QUERY_DEPTH: usize = 128;
34const MAP_TAG: &str = "tag:yaml.org,2002:map";
35const SEQ_TAG: &str = "tag:yaml.org,2002:seq";
36
37/// Classification of a `JSONPath` parse or evaluation failure.
38#[derive(Debug, Clone, Copy, PartialEq, Eq)]
39pub enum ErrorKind {
40    /// Invalid RFC 9535 syntax.
41    Syntax,
42    /// Invalid regular expression used by `match()` or `search()`.
43    Regex,
44    /// An ill-typed function or comparison expression.
45    Type,
46    /// The selected YAML value is outside the JSON data model.
47    DataModel,
48    /// An alias is unresolved, cyclic, or recursively expands a collection.
49    Alias,
50    /// A parser, traversal, nesting, or expansion limit was exceeded.
51    Limit,
52    /// The requested YAML document does not exist.
53    Document,
54    /// Another YAML semantic operation failed.
55    Semantic,
56}
57
58/// A structured `JSONPath` parse or evaluation error.
59#[derive(Debug, Clone, PartialEq, Eq)]
60pub struct Error {
61    kind: ErrorKind,
62    byte_offset: Option<usize>,
63    message: String,
64    source_span: Option<Span>,
65}
66
67impl Error {
68    fn new(message: impl Into<String>) -> Self {
69        Self::with_kind(ErrorKind::Semantic, None, message)
70    }
71
72    fn display(error: impl fmt::Display) -> Self {
73        Self::new(error.to_string())
74    }
75
76    fn with_kind(kind: ErrorKind, byte_offset: Option<usize>, message: impl Into<String>) -> Self {
77        Self {
78            kind,
79            byte_offset,
80            message: message.into(),
81            source_span: None,
82        }
83    }
84
85    fn with_source_span(mut self, source_span: Span) -> Self {
86        self.source_span = Some(source_span);
87        self
88    }
89
90    /// Returns the broad failure classification.
91    #[must_use]
92    pub const fn kind(&self) -> ErrorKind {
93        self.kind
94    }
95
96    /// Returns the failing byte offset in the query, when applicable.
97    #[must_use]
98    pub const fn byte_offset(&self) -> Option<usize> {
99        self.byte_offset
100    }
101
102    /// Returns the relevant YAML source span for an evaluation failure.
103    #[must_use]
104    pub const fn source_span(&self) -> Option<Span> {
105        self.source_span
106    }
107}
108
109impl fmt::Display for Error {
110    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
111        formatter.write_str(&self.message)
112    }
113}
114
115impl std::error::Error for Error {}
116
117type QueryError = Error;
118
119/// A parsed and reusable RFC 9535 `JSONPath` query.
120#[derive(Debug, Clone)]
121pub struct JsonPath {
122    segments: Vec<Segment>,
123}
124
125impl JsonPath {
126    /// Parses and type-checks one RFC 9535 query.
127    ///
128    /// # Errors
129    ///
130    /// Returns an error when the query has invalid syntax, exceeds a parser
131    /// limit, or contains an ill-typed expression.
132    pub fn parse(source: &str) -> Result<Self, Error> {
133        Parser::new(source).parse()
134    }
135
136    /// Evaluates this query against one selected YAML document.
137    ///
138    /// The complete document is first validated against the JSON-compatible
139    /// data model. Result order and duplicate matches follow RFC 9535 nodelist
140    /// semantics.
141    ///
142    /// # Errors
143    ///
144    /// Returns an error when the document does not exist, is outside the JSON
145    /// data model, contains invalid alias structure, or evaluation fails.
146    pub fn query(&self, doc: &YamlDoc, document: usize) -> Result<QueryMatches, Error> {
147        let root = Candidate {
148            node: doc
149                .document_root(document)
150                .map_err(|error| Error::with_kind(ErrorKind::Document, None, error.to_string()))?,
151            path: Vec::new(),
152        };
153        let budget = doc.source().limits().max_expanded_nodes;
154        let mut validator = Validator::new(doc, budget);
155        validator.validate_candidate(&root)?;
156
157        let mut evaluator = Evaluator::new(doc, root.clone(), budget);
158        let matches = evaluator.apply_segments(vec![root], &self.segments)?;
159        let matches = matches
160            .into_iter()
161            .map(|matched| {
162                let pointer =
163                    JsonPointer::parse(&json_pointer(&matched.path)).map_err(Error::display)?;
164                Ok(QueryMatch {
165                    pointer,
166                    node: matched.node,
167                })
168            })
169            .collect::<Result<Vec<_>, Error>>()?;
170        Ok(QueryMatches { matches })
171    }
172}
173
174impl std::str::FromStr for JsonPath {
175    type Err = Error;
176
177    fn from_str(source: &str) -> Result<Self, Self::Err> {
178        Self::parse(source)
179    }
180}
181
182/// One located `JSONPath` match.
183#[derive(Debug, Clone, PartialEq, Eq)]
184pub struct QueryMatch {
185    pointer: JsonPointer,
186    node: Option<NodeId>,
187}
188
189impl QueryMatch {
190    /// Returns the RFC 6901 pointer for this logical match location.
191    #[must_use]
192    pub const fn pointer(&self) -> &JsonPointer {
193        &self.pointer
194    }
195
196    /// Returns the matching semantic node, or `None` for an empty document.
197    #[must_use]
198    pub const fn node(&self) -> Option<NodeId> {
199        self.node
200    }
201}
202
203/// Ordered `JSONPath` query results.
204#[derive(Debug, Clone, Default, PartialEq, Eq)]
205pub struct QueryMatches {
206    matches: Vec<QueryMatch>,
207}
208
209impl QueryMatches {
210    /// Returns the number of matches, including duplicates.
211    #[must_use]
212    pub const fn len(&self) -> usize {
213        self.matches.len()
214    }
215
216    /// Returns whether the nodelist is empty.
217    #[must_use]
218    pub const fn is_empty(&self) -> bool {
219        self.matches.is_empty()
220    }
221
222    /// Iterates over matches in nodelist order.
223    pub fn iter(&self) -> std::slice::Iter<'_, QueryMatch> {
224        self.matches.iter()
225    }
226}
227
228impl IntoIterator for QueryMatches {
229    type Item = QueryMatch;
230    type IntoIter = std::vec::IntoIter<QueryMatch>;
231
232    fn into_iter(self) -> Self::IntoIter {
233        self.matches.into_iter()
234    }
235}
236
237impl<'a> IntoIterator for &'a QueryMatches {
238    type Item = &'a QueryMatch;
239    type IntoIter = std::slice::Iter<'a, QueryMatch>;
240
241    fn into_iter(self) -> Self::IntoIter {
242        self.iter()
243    }
244}
245
246#[derive(Debug, Clone)]
247struct Segment {
248    descendant: bool,
249    selectors: Vec<Selector>,
250}
251
252#[derive(Debug, Clone)]
253enum Selector {
254    Name(String),
255    Wildcard,
256    Index(i64),
257    Slice {
258        start: Option<i64>,
259        end: Option<i64>,
260        step: Option<i64>,
261    },
262    Filter(Expr),
263}
264
265#[derive(Debug, Clone)]
266enum Expr {
267    Or(Box<Self>, Box<Self>),
268    And(Box<Self>, Box<Self>),
269    Not(Box<Self>),
270    Compare(ValueExpr, CompareOp, ValueExpr),
271    Exists(PathExpr),
272    Regex {
273        value: ValueExpr,
274        pattern: RegexPattern,
275    },
276}
277
278#[derive(Debug, Clone)]
279enum RegexPattern {
280    Compiled(Regex),
281    Dynamic { value: ValueExpr, full: bool },
282}
283
284#[derive(Debug, Clone, Copy)]
285enum CompareOp {
286    Equal,
287    NotEqual,
288    Less,
289    LessEqual,
290    Greater,
291    GreaterEqual,
292}
293
294#[derive(Debug, Clone)]
295enum ValueExpr {
296    Literal(Literal),
297    Singular(PathExpr),
298    Length(Box<Self>),
299    Count(PathExpr),
300    Value(PathExpr),
301}
302
303#[derive(Debug, Clone)]
304enum Literal {
305    Null,
306    Bool(bool),
307    Number(YamlNumber),
308    String(String),
309}
310
311#[derive(Debug, Clone)]
312struct PathExpr {
313    root: PathRoot,
314    segments: Vec<Segment>,
315}
316
317#[derive(Debug, Clone, Copy)]
318enum PathRoot {
319    Root,
320    Current,
321}
322
323struct Parser<'a> {
324    input: &'a str,
325    offset: usize,
326    depth: usize,
327}
328
329impl<'a> Parser<'a> {
330    fn new(input: &'a str) -> Self {
331        Self {
332            input,
333            offset: 0,
334            depth: 0,
335        }
336    }
337
338    fn parse(mut self) -> Result<JsonPath, QueryError> {
339        if !self.consume_char('$') {
340            return self.error("a JSONPath query must begin with `$`");
341        }
342        let segments = self.parse_segments()?;
343        self.skip_ws();
344        if !self.is_end() {
345            return self.error("unexpected trailing JSONPath input");
346        }
347        Ok(JsonPath { segments })
348    }
349
350    fn parse_segments(&mut self) -> Result<Vec<Segment>, QueryError> {
351        let mut segments = Vec::new();
352        loop {
353            if self.consume("..") {
354                segments.push(self.parse_segment_tail(true)?);
355            } else if self.consume_char('.') {
356                segments.push(self.parse_segment_tail(false)?);
357            } else if self.peek_char() == Some('[') {
358                segments.push(self.parse_bracket_segment(false)?);
359            } else {
360                break;
361            }
362        }
363        Ok(segments)
364    }
365
366    fn parse_segment_tail(&mut self, descendant: bool) -> Result<Segment, QueryError> {
367        if self.peek_char() == Some('[') {
368            return self.parse_bracket_segment(descendant);
369        }
370        if self.consume_char('*') {
371            return Ok(Segment {
372                descendant,
373                selectors: vec![Selector::Wildcard],
374            });
375        }
376        let name = self.parse_shorthand_name()?;
377        Ok(Segment {
378            descendant,
379            selectors: vec![Selector::Name(name)],
380        })
381    }
382
383    fn parse_bracket_segment(&mut self, descendant: bool) -> Result<Segment, QueryError> {
384        self.expect_char('[')?;
385        self.enter()?;
386        self.skip_ws();
387        let mut selectors = Vec::new();
388        loop {
389            selectors.push(self.parse_selector()?);
390            self.skip_ws();
391            if self.consume_char(',') {
392                self.skip_ws();
393                continue;
394            }
395            self.expect_char(']')?;
396            break;
397        }
398        self.leave();
399        Ok(Segment {
400            descendant,
401            selectors,
402        })
403    }
404
405    fn parse_selector(&mut self) -> Result<Selector, QueryError> {
406        if self.consume_char('*') {
407            return Ok(Selector::Wildcard);
408        }
409        if self.consume_char('?') {
410            self.skip_ws();
411            return self.parse_expr().map(Selector::Filter);
412        }
413        if matches!(self.peek_char(), Some('\'' | '"')) {
414            return self.parse_string().map(Selector::Name);
415        }
416
417        let start = self.parse_optional_integer()?;
418        self.skip_ws();
419        if self.consume_char(':') {
420            self.skip_ws();
421            let end = self.parse_optional_integer()?;
422            self.skip_ws();
423            let step = if self.consume_char(':') {
424                self.skip_ws();
425                self.parse_optional_integer()?
426            } else {
427                None
428            };
429            if step == Some(0) {
430                return self.error("a JSONPath slice step must not be zero");
431            }
432            return Ok(Selector::Slice { start, end, step });
433        }
434        start
435            .map(Selector::Index)
436            .ok_or_else(|| self.error_value("expected a JSONPath selector"))
437    }
438
439    fn parse_expr(&mut self) -> Result<Expr, QueryError> {
440        self.parse_or()
441    }
442
443    fn parse_or(&mut self) -> Result<Expr, QueryError> {
444        let mut expression = self.parse_and()?;
445        loop {
446            self.skip_ws();
447            if !self.consume("||") {
448                break;
449            }
450            self.skip_ws();
451            expression = Expr::Or(Box::new(expression), Box::new(self.parse_and()?));
452        }
453        Ok(expression)
454    }
455
456    fn parse_and(&mut self) -> Result<Expr, QueryError> {
457        let mut expression = self.parse_unary()?;
458        loop {
459            self.skip_ws();
460            if !self.consume("&&") {
461                break;
462            }
463            self.skip_ws();
464            expression = Expr::And(Box::new(expression), Box::new(self.parse_unary()?));
465        }
466        Ok(expression)
467    }
468
469    fn parse_unary(&mut self) -> Result<Expr, QueryError> {
470        self.skip_ws();
471        if self.consume_char('!') && self.peek_char() != Some('=') {
472            self.enter()?;
473            let expression = self.parse_unary()?;
474            self.leave();
475            return Ok(Expr::Not(Box::new(expression)));
476        }
477        if self.consume_char('(') {
478            self.enter()?;
479            let expression = self.parse_expr()?;
480            self.skip_ws();
481            self.expect_char(')')?;
482            self.leave();
483            return Ok(expression);
484        }
485        if self.starts_identifier("match") || self.starts_identifier("search") {
486            return self.parse_regex_function();
487        }
488
489        if matches!(self.peek_char(), Some('$' | '@')) {
490            let path = self.parse_path_expr()?;
491            self.skip_ws();
492            if let Some(operator) = self.parse_compare_operator() {
493                if !is_singular(&path) {
494                    return self.type_error("a comparison query must be singular");
495                }
496                self.skip_ws();
497                return Ok(Expr::Compare(
498                    ValueExpr::Singular(path),
499                    operator,
500                    self.parse_value_expr()?,
501                ));
502            }
503            return Ok(Expr::Exists(path));
504        }
505
506        let left = self.parse_value_expr()?;
507        self.skip_ws();
508        if let Some(operator) = self.parse_compare_operator() {
509            self.skip_ws();
510            return Ok(Expr::Compare(left, operator, self.parse_value_expr()?));
511        }
512        self.type_error("a filter value must be compared or used as a logical expression")
513    }
514
515    fn parse_regex_function(&mut self) -> Result<Expr, QueryError> {
516        let name = self.parse_identifier()?;
517        self.skip_ws();
518        self.expect_char('(')?;
519        self.enter()?;
520        self.skip_ws();
521        let value = self.parse_value_expr()?;
522        self.skip_ws();
523        self.expect_char(',')?;
524        self.skip_ws();
525        let pattern = self.parse_value_expr()?;
526        self.skip_ws();
527        self.expect_char(')')?;
528        self.leave();
529        let full = name == "match";
530        let pattern = match pattern {
531            ValueExpr::Literal(Literal::String(pattern)) => {
532                RegexPattern::Compiled(compile_regex(&name, &pattern, full)?)
533            }
534            value => RegexPattern::Dynamic { value, full },
535        };
536        Ok(Expr::Regex { value, pattern })
537    }
538
539    fn parse_value_expr(&mut self) -> Result<ValueExpr, QueryError> {
540        self.skip_ws();
541        match self.peek_char() {
542            Some('\'' | '"') => {
543                return self
544                    .parse_string()
545                    .map(Literal::String)
546                    .map(ValueExpr::Literal);
547            }
548            Some('$' | '@') => {
549                let path = self.parse_path_expr()?;
550                if !is_singular(&path) {
551                    return self.type_error("a comparison query must be singular");
552                }
553                return Ok(ValueExpr::Singular(path));
554            }
555            Some('-' | '0'..='9') => return self.parse_number_literal(),
556            _ => {}
557        }
558        if self.consume_keyword("true") {
559            return Ok(ValueExpr::Literal(Literal::Bool(true)));
560        }
561        if self.consume_keyword("false") {
562            return Ok(ValueExpr::Literal(Literal::Bool(false)));
563        }
564        if self.consume_keyword("null") {
565            return Ok(ValueExpr::Literal(Literal::Null));
566        }
567        if self.starts_identifier("length")
568            || self.starts_identifier("count")
569            || self.starts_identifier("value")
570        {
571            return self.parse_value_function();
572        }
573        self.error("expected a JSONPath filter value")
574    }
575
576    fn parse_value_function(&mut self) -> Result<ValueExpr, QueryError> {
577        let name = self.parse_identifier()?;
578        self.skip_ws();
579        self.expect_char('(')?;
580        self.enter()?;
581        self.skip_ws();
582        let result = match name.as_str() {
583            "length" => ValueExpr::Length(Box::new(self.parse_value_expr()?)),
584            "count" | "value" => {
585                let path = self.parse_path_expr()?;
586                if name == "count" {
587                    ValueExpr::Count(path)
588                } else {
589                    ValueExpr::Value(path)
590                }
591            }
592            _ => return self.type_error(format!("unknown JSONPath function `{name}`")),
593        };
594        self.skip_ws();
595        if self.consume_char(',') {
596            return self.type_error(format!("{name}() accepts exactly one argument"));
597        }
598        self.expect_char(')')?;
599        self.leave();
600        Ok(result)
601    }
602
603    fn parse_path_expr(&mut self) -> Result<PathExpr, QueryError> {
604        let root = match self.next_char() {
605            Some('$') => PathRoot::Root,
606            Some('@') => PathRoot::Current,
607            _ => return self.error("expected a root or current-node query"),
608        };
609        Ok(PathExpr {
610            root,
611            segments: self.parse_segments()?,
612        })
613    }
614
615    fn parse_compare_operator(&mut self) -> Option<CompareOp> {
616        for (text, operator) in [
617            ("==", CompareOp::Equal),
618            ("!=", CompareOp::NotEqual),
619            ("<=", CompareOp::LessEqual),
620            (">=", CompareOp::GreaterEqual),
621            ("<", CompareOp::Less),
622            (">", CompareOp::Greater),
623        ] {
624            if self.consume(text) {
625                return Some(operator);
626            }
627        }
628        None
629    }
630
631    fn parse_number_literal(&mut self) -> Result<ValueExpr, QueryError> {
632        let start = self.offset;
633        self.consume_char('-');
634        match self.peek_char() {
635            Some('0') => {
636                self.next_char();
637                if self
638                    .peek_char()
639                    .is_some_and(|character| character.is_ascii_digit())
640                {
641                    return self.error("a JSONPath number must not contain a leading zero");
642                }
643            }
644            Some('1'..='9') => {
645                self.take_while(|character| character.is_ascii_digit());
646            }
647            _ => return self.error("invalid JSONPath number"),
648        }
649        if self.consume_char('.') {
650            if !self
651                .peek_char()
652                .is_some_and(|character| character.is_ascii_digit())
653            {
654                return self.error("a JSONPath fraction requires at least one digit");
655            }
656            self.take_while(|character| character.is_ascii_digit());
657        }
658        if self
659            .peek_char()
660            .is_some_and(|character| matches!(character, 'e' | 'E'))
661        {
662            self.next_char();
663            if self
664                .peek_char()
665                .is_some_and(|character| matches!(character, '+' | '-'))
666            {
667                self.next_char();
668            }
669            if !self
670                .peek_char()
671                .is_some_and(|character| character.is_ascii_digit())
672            {
673                return self.error("a JSONPath exponent requires at least one digit");
674            }
675            self.take_while(|character| character.is_ascii_digit());
676        }
677        let text = &self.input[start..self.offset];
678        let ResolvedScalar::Number(number) =
679            resolve_scalar(text, YamlScalarStyle::Plain, None).map_err(QueryError::display)?
680        else {
681            return self.error("invalid JSONPath number");
682        };
683        Ok(ValueExpr::Literal(Literal::Number(number)))
684    }
685
686    fn parse_optional_integer(&mut self) -> Result<Option<i64>, QueryError> {
687        let start = self.offset;
688        self.consume_char('-');
689        let digits = self.take_while(|character| character.is_ascii_digit());
690        if digits == 0 {
691            self.offset = start;
692            return Ok(None);
693        }
694        self.input[start..self.offset]
695            .parse::<i64>()
696            .map(Some)
697            .map_err(|_| self.error_value("JSONPath integer is out of range"))
698    }
699
700    fn parse_string(&mut self) -> Result<String, QueryError> {
701        let quote = self
702            .next_char()
703            .filter(|character| matches!(character, '\'' | '"'))
704            .ok_or_else(|| self.error_value("expected a quoted JSONPath string"))?;
705        let mut output = String::new();
706        loop {
707            let Some(character) = self.next_char() else {
708                return self.error("unterminated JSONPath string");
709            };
710            if character == quote {
711                return Ok(output);
712            }
713            if character == '\\' {
714                let escaped = self
715                    .next_char()
716                    .ok_or_else(|| self.error_value("unterminated JSONPath escape"))?;
717                match escaped {
718                    'b' => output.push('\u{0008}'),
719                    'f' => output.push('\u{000c}'),
720                    'n' => output.push('\n'),
721                    'r' => output.push('\r'),
722                    't' => output.push('\t'),
723                    '/' => output.push('/'),
724                    '\\' => output.push('\\'),
725                    '\'' if quote == '\'' => output.push('\''),
726                    '"' if quote == '"' => output.push('"'),
727                    'u' => output.push(self.parse_unicode_escape()?),
728                    _ => return self.error(format!("invalid JSONPath escape `\\{escaped}`")),
729                }
730            } else if character.is_control() {
731                return self.error("unescaped control character in JSONPath string");
732            } else {
733                output.push(character);
734            }
735        }
736    }
737
738    fn parse_unicode_escape(&mut self) -> Result<char, QueryError> {
739        let first = self.parse_hex_quad()?;
740        if (0xd800..=0xdbff).contains(&first) {
741            if !self.consume("\\u") {
742                return self.error("a high surrogate must be followed by a low surrogate");
743            }
744            let second = self.parse_hex_quad()?;
745            if !(0xdc00..=0xdfff).contains(&second) {
746                return self.error("invalid low surrogate in JSONPath string");
747            }
748            let scalar = 0x10000 + ((u32::from(first) - 0xd800) << 10) + u32::from(second) - 0xdc00;
749            char::from_u32(scalar).ok_or_else(|| self.error_value("invalid Unicode escape"))
750        } else if (0xdc00..=0xdfff).contains(&first) {
751            self.error("unexpected low surrogate in JSONPath string")
752        } else {
753            char::from_u32(u32::from(first))
754                .ok_or_else(|| self.error_value("invalid Unicode escape"))
755        }
756    }
757
758    fn parse_hex_quad(&mut self) -> Result<u16, QueryError> {
759        let start = self.offset;
760        for _ in 0..4 {
761            if !self
762                .peek_char()
763                .is_some_and(|character| character.is_ascii_hexdigit())
764            {
765                return self.error("a Unicode escape requires four hexadecimal digits");
766            }
767            self.next_char();
768        }
769        u16::from_str_radix(&self.input[start..self.offset], 16).map_err(QueryError::display)
770    }
771
772    fn parse_shorthand_name(&mut self) -> Result<String, QueryError> {
773        let start = self.offset;
774        let Some(first) = self.peek_char() else {
775            return self.error("expected a name after `.`");
776        };
777        if !(first == '_' || first.is_alphabetic() || !first.is_ascii()) {
778            return self.error("invalid shorthand JSONPath name");
779        }
780        self.next_char();
781        while self.peek_char().is_some_and(|character| {
782            character == '_' || character.is_alphanumeric() || !character.is_ascii()
783        }) {
784            self.next_char();
785        }
786        Ok(self.input[start..self.offset].to_owned())
787    }
788
789    fn parse_identifier(&mut self) -> Result<String, QueryError> {
790        let start = self.offset;
791        if !self
792            .peek_char()
793            .is_some_and(|character| character.is_ascii_alphabetic())
794        {
795            return self.error("expected a function name");
796        }
797        self.take_while(|character| character.is_ascii_alphanumeric() || character == '_');
798        Ok(self.input[start..self.offset].to_owned())
799    }
800
801    fn starts_identifier(&self, identifier: &str) -> bool {
802        self.input[self.offset..].starts_with(identifier)
803            && self.input[self.offset + identifier.len()..]
804                .chars()
805                .next()
806                .is_none_or(|character| !character.is_ascii_alphanumeric() && character != '_')
807    }
808
809    fn consume_keyword(&mut self, keyword: &str) -> bool {
810        if self.starts_identifier(keyword) {
811            self.offset += keyword.len();
812            true
813        } else {
814            false
815        }
816    }
817
818    fn enter(&mut self) -> Result<(), QueryError> {
819        self.depth += 1;
820        if self.depth > MAX_QUERY_DEPTH {
821            return Err(Error::with_kind(
822                ErrorKind::Limit,
823                Some(self.offset),
824                format!(
825                    "invalid JSONPath at byte {}: JSONPath nesting limit exceeded",
826                    self.offset
827                ),
828            ));
829        }
830        Ok(())
831    }
832
833    fn leave(&mut self) {
834        self.depth = self.depth.saturating_sub(1);
835    }
836
837    fn skip_ws(&mut self) {
838        self.take_while(char::is_whitespace);
839    }
840
841    fn take_while(&mut self, predicate: impl Fn(char) -> bool) -> usize {
842        let start = self.offset;
843        while self.peek_char().is_some_and(&predicate) {
844            self.next_char();
845        }
846        self.offset - start
847    }
848
849    fn expect_char(&mut self, expected: char) -> Result<(), QueryError> {
850        if self.consume_char(expected) {
851            Ok(())
852        } else {
853            self.error(format!("expected `{expected}`"))
854        }
855    }
856
857    fn consume(&mut self, expected: &str) -> bool {
858        if self.input[self.offset..].starts_with(expected) {
859            self.offset += expected.len();
860            true
861        } else {
862            false
863        }
864    }
865
866    fn consume_char(&mut self, expected: char) -> bool {
867        if self.peek_char() == Some(expected) {
868            self.next_char();
869            true
870        } else {
871            false
872        }
873    }
874
875    fn next_char(&mut self) -> Option<char> {
876        let character = self.peek_char()?;
877        self.offset += character.len_utf8();
878        Some(character)
879    }
880
881    fn peek_char(&self) -> Option<char> {
882        self.input[self.offset..].chars().next()
883    }
884
885    fn is_end(&self) -> bool {
886        self.offset == self.input.len()
887    }
888
889    fn error<T>(&self, message: impl Into<String>) -> Result<T, QueryError> {
890        Err(self.error_value(message))
891    }
892
893    fn error_value(&self, message: impl Into<String>) -> QueryError {
894        Error::with_kind(
895            ErrorKind::Syntax,
896            Some(self.offset),
897            format!(
898                "invalid JSONPath at byte {}: {}",
899                self.offset,
900                message.into()
901            ),
902        )
903    }
904
905    fn type_error<T>(&self, message: impl Into<String>) -> Result<T, QueryError> {
906        Err(Error::with_kind(
907            ErrorKind::Type,
908            Some(self.offset),
909            format!(
910                "invalid JSONPath at byte {}: {}",
911                self.offset,
912                message.into()
913            ),
914        ))
915    }
916}
917
918fn is_singular(path: &PathExpr) -> bool {
919    path.segments.iter().all(|segment| {
920        !segment.descendant
921            && segment.selectors.len() == 1
922            && matches!(segment.selectors[0], Selector::Name(_) | Selector::Index(_))
923    })
924}
925
926fn compile_regex(name: &str, pattern: &str, full: bool) -> Result<Regex, QueryError> {
927    let expression = if full {
928        format!(r"\A(?:{pattern})\z")
929    } else {
930        pattern.to_owned()
931    };
932    Regex::new(&expression).map_err(|error| {
933        Error::with_kind(
934            ErrorKind::Regex,
935            None,
936            format!("invalid {name}() regex: {error}"),
937        )
938    })
939}
940
941#[derive(Debug, Clone)]
942struct Candidate {
943    node: Option<NodeId>,
944    path: Vec<String>,
945}
946
947struct Evaluator<'a> {
948    doc: &'a YamlDoc,
949    root: Candidate,
950    remaining: usize,
951}
952
953impl<'a> Evaluator<'a> {
954    fn new(doc: &'a YamlDoc, root: Candidate, budget: usize) -> Self {
955        Self {
956            doc,
957            root,
958            remaining: budget,
959        }
960    }
961
962    fn apply_segments(
963        &mut self,
964        mut input: Vec<Candidate>,
965        segments: &[Segment],
966    ) -> Result<Vec<Candidate>, QueryError> {
967        for segment in segments {
968            let mut output = Vec::new();
969            for candidate in input {
970                if segment.descendant {
971                    for descendant in self.descendants(candidate)? {
972                        self.apply_selectors(&descendant, &segment.selectors, &mut output)?;
973                    }
974                } else {
975                    self.apply_selectors(&candidate, &segment.selectors, &mut output)?;
976                }
977            }
978            input = output;
979        }
980        Ok(input)
981    }
982
983    fn descendants(&mut self, root: Candidate) -> Result<Vec<Candidate>, QueryError> {
984        let mut result = Vec::new();
985        let mut pending = vec![root];
986        while let Some(candidate) = pending.pop() {
987            self.spend()?;
988            let children = self.children(&candidate)?;
989            pending.extend(children.into_iter().rev());
990            result.push(candidate);
991        }
992        Ok(result)
993    }
994
995    fn apply_selectors(
996        &mut self,
997        input: &Candidate,
998        selectors: &[Selector],
999        output: &mut Vec<Candidate>,
1000    ) -> Result<(), QueryError> {
1001        for selector in selectors {
1002            match selector {
1003                Selector::Name(name) => {
1004                    if let Some(candidate) = self.member(input, name)? {
1005                        output.push(candidate);
1006                    }
1007                }
1008                Selector::Wildcard => output.extend(self.children(input)?),
1009                Selector::Index(index) => {
1010                    if let Some(candidate) = self.index(input, *index)? {
1011                        output.push(candidate);
1012                    }
1013                }
1014                Selector::Slice { start, end, step } => {
1015                    output.extend(self.slice(input, *start, *end, step.unwrap_or(1))?);
1016                }
1017                Selector::Filter(expression) => {
1018                    for child in self.children(input)? {
1019                        if self.eval_expr(expression, &child)? {
1020                            output.push(child);
1021                        }
1022                    }
1023                }
1024            }
1025        }
1026        Ok(())
1027    }
1028
1029    fn children(&mut self, candidate: &Candidate) -> Result<Vec<Candidate>, QueryError> {
1030        self.spend()?;
1031        let Some(node) = self.resolve(candidate.node)? else {
1032            return Ok(Vec::new());
1033        };
1034        match self.doc.semantic_kind(node) {
1035            Some(SemanticKind::Sequence { .. }) => Ok(self
1036                .doc
1037                .sequence_items(node)
1038                .enumerate()
1039                .map(|(index, node)| Candidate {
1040                    node: Some(node),
1041                    path: appended(&candidate.path, index.to_string()),
1042                })
1043                .collect()),
1044            Some(SemanticKind::Mapping { .. }) => {
1045                let mut output = Vec::new();
1046                for (key, value) in self.doc.mapping_entries(node) {
1047                    output.push(Candidate {
1048                        node: Some(value),
1049                        path: appended(&candidate.path, self.string_key(key)?),
1050                    });
1051                }
1052                Ok(output)
1053            }
1054            _ => Ok(Vec::new()),
1055        }
1056    }
1057
1058    fn member(
1059        &mut self,
1060        candidate: &Candidate,
1061        name: &str,
1062    ) -> Result<Option<Candidate>, QueryError> {
1063        let Some(node) = self.resolve(candidate.node)? else {
1064            return Ok(None);
1065        };
1066        if !matches!(
1067            self.doc.semantic_kind(node),
1068            Some(SemanticKind::Mapping { .. })
1069        ) {
1070            return Ok(None);
1071        }
1072        for (key, value) in self.doc.mapping_entries(node) {
1073            if self.string_key(key)? == name {
1074                return Ok(Some(Candidate {
1075                    node: Some(value),
1076                    path: appended(&candidate.path, name.to_owned()),
1077                }));
1078            }
1079        }
1080        Ok(None)
1081    }
1082
1083    fn index(
1084        &mut self,
1085        candidate: &Candidate,
1086        index: i64,
1087    ) -> Result<Option<Candidate>, QueryError> {
1088        let Some(node) = self.resolve(candidate.node)? else {
1089            return Ok(None);
1090        };
1091        if !matches!(
1092            self.doc.semantic_kind(node),
1093            Some(SemanticKind::Sequence { .. })
1094        ) {
1095            return Ok(None);
1096        }
1097        let items = self.doc.sequence_items(node).collect::<Vec<_>>();
1098        let Some(index) = normalized_index(index, items.len()) else {
1099            return Ok(None);
1100        };
1101        Ok(Some(Candidate {
1102            node: Some(items[index]),
1103            path: appended(&candidate.path, index.to_string()),
1104        }))
1105    }
1106
1107    fn slice(
1108        &mut self,
1109        candidate: &Candidate,
1110        start: Option<i64>,
1111        end: Option<i64>,
1112        step: i64,
1113    ) -> Result<Vec<Candidate>, QueryError> {
1114        let Some(node) = self.resolve(candidate.node)? else {
1115            return Ok(Vec::new());
1116        };
1117        if !matches!(
1118            self.doc.semantic_kind(node),
1119            Some(SemanticKind::Sequence { .. })
1120        ) {
1121            return Ok(Vec::new());
1122        }
1123        let items = self.doc.sequence_items(node).collect::<Vec<_>>();
1124        let indices = slice_indices(items.len(), start, end, step);
1125        Ok(indices
1126            .into_iter()
1127            .map(|index| Candidate {
1128                node: Some(items[index]),
1129                path: appended(&candidate.path, index.to_string()),
1130            })
1131            .collect())
1132    }
1133
1134    fn eval_expr(&mut self, expression: &Expr, current: &Candidate) -> Result<bool, QueryError> {
1135        match expression {
1136            Expr::Or(left, right) => {
1137                Ok(self.eval_expr(left, current)? || self.eval_expr(right, current)?)
1138            }
1139            Expr::And(left, right) => {
1140                Ok(self.eval_expr(left, current)? && self.eval_expr(right, current)?)
1141            }
1142            Expr::Not(expression) => Ok(!self.eval_expr(expression, current)?),
1143            Expr::Exists(path) => Ok(!self.eval_path(path, current)?.is_empty()),
1144            Expr::Regex { value, pattern } => {
1145                let Atom::String(value) = self.eval_value(value, current)? else {
1146                    return Ok(false);
1147                };
1148                match pattern {
1149                    RegexPattern::Compiled(regex) => Ok(regex.is_match(&value)),
1150                    RegexPattern::Dynamic {
1151                        value: pattern,
1152                        full,
1153                    } => {
1154                        let Atom::String(pattern) = self.eval_value(pattern, current)? else {
1155                            return Ok(false);
1156                        };
1157                        Ok(
1158                            compile_regex(if *full { "match" } else { "search" }, &pattern, *full)?
1159                                .is_match(&value),
1160                        )
1161                    }
1162                }
1163            }
1164            Expr::Compare(left, operator, right) => {
1165                let left = self.eval_value(left, current)?;
1166                let right = self.eval_value(right, current)?;
1167                self.compare(left, *operator, right)
1168            }
1169        }
1170    }
1171
1172    fn eval_value(
1173        &mut self,
1174        expression: &ValueExpr,
1175        current: &Candidate,
1176    ) -> Result<Atom, QueryError> {
1177        match expression {
1178            ValueExpr::Literal(literal) => Ok(Atom::from_literal(literal)),
1179            ValueExpr::Singular(path) | ValueExpr::Value(path) => {
1180                let values = self.eval_path(path, current)?;
1181                if values.len() == 1 {
1182                    self.atom(&values[0])
1183                } else {
1184                    Ok(Atom::Nothing)
1185                }
1186            }
1187            ValueExpr::Count(path) => Ok(Atom::number(self.eval_path(path, current)?.len())),
1188            ValueExpr::Length(value) => match self.eval_value(value, current)? {
1189                Atom::String(value) => Ok(Atom::number(value.chars().count())),
1190                Atom::Node(node) => match self.doc.semantic_kind(node) {
1191                    Some(SemanticKind::Sequence { .. }) => {
1192                        Ok(Atom::number(self.doc.sequence_items(node).count()))
1193                    }
1194                    Some(SemanticKind::Mapping { .. }) => {
1195                        Ok(Atom::number(self.doc.mapping_entries(node).count()))
1196                    }
1197                    _ => Ok(Atom::Nothing),
1198                },
1199                _ => Ok(Atom::Nothing),
1200            },
1201        }
1202    }
1203
1204    fn eval_path(
1205        &mut self,
1206        path: &PathExpr,
1207        current: &Candidate,
1208    ) -> Result<Vec<Candidate>, QueryError> {
1209        let start = match path.root {
1210            PathRoot::Root => self.root.clone(),
1211            PathRoot::Current => current.clone(),
1212        };
1213        self.apply_segments(vec![start], &path.segments)
1214    }
1215
1216    fn atom(&self, candidate: &Candidate) -> Result<Atom, QueryError> {
1217        let Some(node) = self.resolve(candidate.node)? else {
1218            return Ok(Atom::Null);
1219        };
1220        match self.doc.semantic_kind(node) {
1221            Some(SemanticKind::Scalar { style }) => {
1222                let value = self.doc.scalar_value(node).map_err(QueryError::display)?;
1223                let tag = self.doc.resolved_tag(node).map_err(QueryError::display)?;
1224                match resolve_scalar(&value, style, tag.as_deref()).map_err(|error| {
1225                    Error::with_kind(ErrorKind::DataModel, None, error.to_string())
1226                })? {
1227                    ResolvedScalar::Null => Ok(Atom::Null),
1228                    ResolvedScalar::Bool(value) => Ok(Atom::Bool(value)),
1229                    ResolvedScalar::Number(value) => Ok(Atom::Number(value)),
1230                    ResolvedScalar::String => Ok(Atom::String(value.into_owned())),
1231                    ResolvedScalar::NonFinite(_) => Err(Error::with_kind(
1232                        ErrorKind::DataModel,
1233                        None,
1234                        "non-finite YAML numbers are not JSON-compatible",
1235                    )),
1236                }
1237            }
1238            Some(SemanticKind::Mapping { .. } | SemanticKind::Sequence { .. }) => {
1239                Ok(Atom::Node(node))
1240            }
1241            _ => Err(QueryError::new("unknown semantic YAML node")),
1242        }
1243    }
1244
1245    fn compare(&self, left: Atom, operator: CompareOp, right: Atom) -> Result<bool, QueryError> {
1246        let equal = match (&left, &right) {
1247            (Atom::Nothing, Atom::Nothing) | (Atom::Null, Atom::Null) => true,
1248            (Atom::Bool(left), Atom::Bool(right)) => left == right,
1249            (Atom::Number(left), Atom::Number(right)) => left == right,
1250            (Atom::String(left), Atom::String(right)) => left == right,
1251            (Atom::Node(left), Atom::Node(right)) => {
1252                semantically_equal(self.doc, *left, self.doc, *right).map_err(|error| {
1253                    Error::with_kind(ErrorKind::DataModel, None, error.to_string())
1254                })?
1255            }
1256            _ => false,
1257        };
1258        match operator {
1259            CompareOp::Equal => Ok(equal),
1260            CompareOp::NotEqual => Ok(!equal),
1261            _ => {
1262                let ordering = match (left, right) {
1263                    (Atom::Number(left), Atom::Number(right)) => Some(left.cmp(&right)),
1264                    (Atom::String(left), Atom::String(right)) => Some(left.cmp(&right)),
1265                    _ => None,
1266                };
1267                Ok(matches!(
1268                    (operator, ordering),
1269                    (CompareOp::Less, Some(Ordering::Less))
1270                        | (CompareOp::LessEqual, Some(Ordering::Less | Ordering::Equal))
1271                        | (CompareOp::Greater, Some(Ordering::Greater))
1272                        | (
1273                            CompareOp::GreaterEqual,
1274                            Some(Ordering::Greater | Ordering::Equal)
1275                        )
1276                ))
1277            }
1278        }
1279    }
1280
1281    fn string_key(&self, node: NodeId) -> Result<String, QueryError> {
1282        let node = self.resolve(Some(node))?.ok_or_else(|| {
1283            Error::with_kind(ErrorKind::DataModel, None, "mapping contains an empty key")
1284        })?;
1285        let Some(SemanticKind::Scalar { style }) = self.doc.semantic_kind(node) else {
1286            return Err(Error::with_kind(
1287                ErrorKind::DataModel,
1288                None,
1289                "mapping contains a non-string key",
1290            ));
1291        };
1292        let value = self.doc.scalar_value(node).map_err(QueryError::display)?;
1293        let tag = self.doc.resolved_tag(node).map_err(QueryError::display)?;
1294        if resolve_scalar(&value, style, tag.as_deref())
1295            .map_err(|error| Error::with_kind(ErrorKind::DataModel, None, error.to_string()))?
1296            != ResolvedScalar::String
1297        {
1298            return Err(Error::with_kind(
1299                ErrorKind::DataModel,
1300                None,
1301                "mapping contains a non-string key",
1302            ));
1303        }
1304        Ok(value.into_owned())
1305    }
1306
1307    fn resolve(&self, mut node: Option<NodeId>) -> Result<Option<NodeId>, QueryError> {
1308        let mut seen = HashSet::new();
1309        while let Some(current) = node {
1310            if !matches!(self.doc.semantic_kind(current), Some(SemanticKind::Alias)) {
1311                break;
1312            }
1313            if !seen.insert(current) {
1314                let mut error = Error::with_kind(ErrorKind::Alias, None, "cyclic YAML alias chain");
1315                if let Some(span) = self.doc.node(current).map(|node| node.span()) {
1316                    error = error.with_source_span(span);
1317                }
1318                return Err(error);
1319            }
1320            if seen.len() > self.doc.source().limits().max_alias_chain {
1321                return Err(Error::with_kind(
1322                    ErrorKind::Limit,
1323                    None,
1324                    "YAML alias chain limit exceeded",
1325                ));
1326            }
1327            node = self.doc.resolve_alias(current);
1328            if node.is_none() {
1329                let mut error = Error::with_kind(
1330                    ErrorKind::Alias,
1331                    None,
1332                    format!(
1333                        "unresolved YAML alias `*{}`",
1334                        self.doc.alias_name(current).unwrap_or_default()
1335                    ),
1336                );
1337                if let Some(span) = self.doc.node(current).map(|node| node.span()) {
1338                    error = error.with_source_span(span);
1339                }
1340                return Err(error);
1341            }
1342        }
1343        Ok(node)
1344    }
1345
1346    fn spend(&mut self) -> Result<(), QueryError> {
1347        self.remaining = self.remaining.checked_sub(1).ok_or_else(|| {
1348            Error::with_kind(ErrorKind::Limit, None, "JSONPath traversal limit exceeded")
1349        })?;
1350        Ok(())
1351    }
1352}
1353
1354#[derive(Debug)]
1355enum Atom {
1356    Nothing,
1357    Null,
1358    Bool(bool),
1359    Number(YamlNumber),
1360    String(String),
1361    Node(NodeId),
1362}
1363
1364impl Atom {
1365    fn from_literal(literal: &Literal) -> Self {
1366        match literal {
1367            Literal::Null => Self::Null,
1368            Literal::Bool(value) => Self::Bool(*value),
1369            Literal::Number(value) => Self::Number(value.clone()),
1370            Literal::String(value) => Self::String(value.clone()),
1371        }
1372    }
1373
1374    fn number(value: usize) -> Self {
1375        let ResolvedScalar::Number(number) =
1376            resolve_scalar(&value.to_string(), YamlScalarStyle::Plain, None)
1377                .expect("usize is a YAML number")
1378        else {
1379            unreachable!();
1380        };
1381        Self::Number(number)
1382    }
1383}
1384
1385struct Validator<'a> {
1386    doc: &'a YamlDoc,
1387    remaining: usize,
1388    depth_limit: usize,
1389    alias_chain_limit: usize,
1390    active: HashSet<NodeId>,
1391}
1392
1393impl<'a> Validator<'a> {
1394    fn new(doc: &'a YamlDoc, budget: usize) -> Self {
1395        Self {
1396            doc,
1397            remaining: budget,
1398            depth_limit: doc.source().limits().max_collection_depth,
1399            alias_chain_limit: doc.source().limits().max_alias_chain,
1400            active: HashSet::new(),
1401        }
1402    }
1403
1404    fn validate_candidate(&mut self, candidate: &Candidate) -> Result<(), QueryError> {
1405        self.validate_node(candidate.node, 0)
1406    }
1407
1408    fn validate_node(&mut self, node: Option<NodeId>, depth: usize) -> Result<(), QueryError> {
1409        if depth > self.depth_limit {
1410            return Err(Error::with_kind(
1411                ErrorKind::Limit,
1412                None,
1413                "JSON-compatible value nesting limit exceeded",
1414            ));
1415        }
1416        self.remaining = self.remaining.checked_sub(1).ok_or_else(|| {
1417            Error::with_kind(
1418                ErrorKind::Limit,
1419                None,
1420                "YAML alias expansion limit exceeded",
1421            )
1422        })?;
1423        let Some(mut node) = node else {
1424            return Ok(());
1425        };
1426        let mut aliases = HashSet::new();
1427        while matches!(self.doc.semantic_kind(node), Some(SemanticKind::Alias)) {
1428            if !aliases.insert(node) {
1429                let mut error = Error::with_kind(ErrorKind::Alias, None, "cyclic YAML alias chain");
1430                if let Some(span) = self.doc.node(node).map(|node| node.span()) {
1431                    error = error.with_source_span(span);
1432                }
1433                return Err(error);
1434            }
1435            if aliases.len() > self.alias_chain_limit {
1436                return Err(Error::with_kind(
1437                    ErrorKind::Limit,
1438                    None,
1439                    "YAML alias chain limit exceeded",
1440                ));
1441            }
1442            self.spend_alias()?;
1443            let alias = node;
1444            node = self.doc.resolve_alias(alias).ok_or_else(|| {
1445                let mut error = Error::with_kind(
1446                    ErrorKind::Alias,
1447                    None,
1448                    format!(
1449                        "unresolved YAML alias `*{}`",
1450                        self.doc.alias_name(alias).unwrap_or_default()
1451                    ),
1452                );
1453                if let Some(span) = self.doc.node(alias).map(|node| node.span()) {
1454                    error = error.with_source_span(span);
1455                }
1456                error
1457            })?;
1458        }
1459        match self.doc.semantic_kind(node) {
1460            Some(SemanticKind::Scalar { style }) => self.validate_scalar(node, style),
1461            Some(SemanticKind::Sequence { .. }) => {
1462                self.validate_collection_tag(node, SEQ_TAG)?;
1463                if !self.active.insert(node) {
1464                    return Err(Error::with_kind(
1465                        ErrorKind::Alias,
1466                        None,
1467                        "recursive YAML alias graph is not JSON-compatible",
1468                    ));
1469                }
1470                for item in self.doc.sequence_items(node) {
1471                    self.validate_node(Some(item), depth + 1)?;
1472                }
1473                self.active.remove(&node);
1474                Ok(())
1475            }
1476            Some(SemanticKind::Mapping { .. }) => {
1477                self.validate_collection_tag(node, MAP_TAG)?;
1478                if !self.active.insert(node) {
1479                    return Err(Error::with_kind(
1480                        ErrorKind::Alias,
1481                        None,
1482                        "recursive YAML alias graph is not JSON-compatible",
1483                    ));
1484                }
1485                let mut keys = HashSet::new();
1486                for (key, value) in self.doc.mapping_entries(node) {
1487                    let key = self.string_key(key)?;
1488                    if !keys.insert(key.clone()) {
1489                        return Err(Error::with_kind(
1490                            ErrorKind::DataModel,
1491                            None,
1492                            format!("mapping contains duplicate key `{key}`"),
1493                        ));
1494                    }
1495                    self.validate_node(Some(value), depth + 1)?;
1496                }
1497                self.active.remove(&node);
1498                Ok(())
1499            }
1500            _ => Err(QueryError::new("unknown semantic YAML node")),
1501        }
1502    }
1503
1504    fn validate_scalar(&self, node: NodeId, style: YamlScalarStyle) -> Result<(), QueryError> {
1505        let value = self.doc.scalar_value(node).map_err(QueryError::display)?;
1506        let tag = self.doc.resolved_tag(node).map_err(QueryError::display)?;
1507        match resolve_scalar(&value, style, tag.as_deref())
1508            .map_err(|error| Error::with_kind(ErrorKind::DataModel, None, error.to_string()))?
1509        {
1510            ResolvedScalar::NonFinite(_) => Err(Error::with_kind(
1511                ErrorKind::DataModel,
1512                None,
1513                "non-finite YAML numbers are not JSON-compatible",
1514            )),
1515            _ => Ok(()),
1516        }
1517    }
1518
1519    fn string_key(&mut self, node: NodeId) -> Result<String, QueryError> {
1520        let mut node = node;
1521        let mut seen = HashSet::new();
1522        while matches!(self.doc.semantic_kind(node), Some(SemanticKind::Alias)) {
1523            if !seen.insert(node) {
1524                let mut error = Error::with_kind(ErrorKind::Alias, None, "cyclic YAML alias key");
1525                if let Some(span) = self.doc.node(node).map(|node| node.span()) {
1526                    error = error.with_source_span(span);
1527                }
1528                return Err(error);
1529            }
1530            if seen.len() > self.alias_chain_limit {
1531                return Err(Error::with_kind(
1532                    ErrorKind::Limit,
1533                    None,
1534                    "YAML alias chain limit exceeded",
1535                ));
1536            }
1537            self.spend_alias()?;
1538            let alias = node;
1539            node = self.doc.resolve_alias(alias).ok_or_else(|| {
1540                let mut error =
1541                    Error::with_kind(ErrorKind::Alias, None, "unresolved YAML alias key");
1542                if let Some(span) = self.doc.node(alias).map(|node| node.span()) {
1543                    error = error.with_source_span(span);
1544                }
1545                error
1546            })?;
1547        }
1548        let Some(SemanticKind::Scalar { style }) = self.doc.semantic_kind(node) else {
1549            return Err(Error::with_kind(
1550                ErrorKind::DataModel,
1551                None,
1552                "mapping contains a non-string key",
1553            ));
1554        };
1555        let value = self.doc.scalar_value(node).map_err(QueryError::display)?;
1556        let tag = self.doc.resolved_tag(node).map_err(QueryError::display)?;
1557        if resolve_scalar(&value, style, tag.as_deref())
1558            .map_err(|error| Error::with_kind(ErrorKind::DataModel, None, error.to_string()))?
1559            != ResolvedScalar::String
1560        {
1561            return Err(Error::with_kind(
1562                ErrorKind::DataModel,
1563                None,
1564                "mapping contains a non-string key",
1565            ));
1566        }
1567        Ok(value.into_owned())
1568    }
1569
1570    fn spend_alias(&mut self) -> Result<(), QueryError> {
1571        self.remaining = self.remaining.checked_sub(1).ok_or_else(|| {
1572            Error::with_kind(
1573                ErrorKind::Limit,
1574                None,
1575                "YAML alias expansion limit exceeded",
1576            )
1577        })?;
1578        Ok(())
1579    }
1580
1581    fn validate_collection_tag(&self, node: NodeId, expected: &str) -> Result<(), QueryError> {
1582        let tag = self.doc.resolved_tag(node).map_err(QueryError::display)?;
1583        if tag.as_deref().is_some_and(|tag| tag != expected) {
1584            return Err(Error::with_kind(
1585                ErrorKind::DataModel,
1586                None,
1587                format!(
1588                    "custom-tagged collection `{}` is not JSON-compatible",
1589                    tag.as_deref().unwrap_or_default()
1590                ),
1591            ));
1592        }
1593        Ok(())
1594    }
1595}
1596
1597fn json_pointer(tokens: &[String]) -> String {
1598    let mut pointer = String::new();
1599    for token in tokens {
1600        pointer.push('/');
1601        pointer.push_str(&token.replace('~', "~0").replace('/', "~1"));
1602    }
1603    pointer
1604}
1605
1606fn appended(path: &[String], token: String) -> Vec<String> {
1607    let mut result = Vec::with_capacity(path.len() + 1);
1608    result.extend_from_slice(path);
1609    result.push(token);
1610    result
1611}
1612
1613fn normalized_index(index: i64, length: usize) -> Option<usize> {
1614    let length = i128::try_from(length).ok()?;
1615    let index = i128::from(index);
1616    let index = if index < 0 { length + index } else { index };
1617    (0..length)
1618        .contains(&index)
1619        .then(|| usize::try_from(index).ok())
1620        .flatten()
1621}
1622
1623fn slice_indices(length: usize, start: Option<i64>, end: Option<i64>, step: i64) -> Vec<usize> {
1624    let length = i128::try_from(length).unwrap_or(i128::MAX);
1625    let step = i128::from(step);
1626    let normalize = |value: i64| {
1627        let value = i128::from(value);
1628        if value < 0 { length + value } else { value }
1629    };
1630    let (mut index, limit) = if step > 0 {
1631        (
1632            start.map_or(0, normalize).clamp(0, length),
1633            end.map_or(length, normalize).clamp(0, length),
1634        )
1635    } else {
1636        (
1637            start.map_or(length - 1, normalize).clamp(-1, length - 1),
1638            end.map_or(-1, normalize).clamp(-1, length - 1),
1639        )
1640    };
1641    let mut result = Vec::new();
1642    while if step > 0 {
1643        index < limit
1644    } else {
1645        index > limit
1646    } {
1647        if let Ok(index) = usize::try_from(index) {
1648            result.push(index);
1649        }
1650        index += step;
1651    }
1652    result
1653}
1654
1655#[cfg(test)]
1656mod tests {
1657    use super::*;
1658    use yaml_rt_core::ResourceLimits;
1659
1660    fn pointers(path: &str, yaml: &str) -> Result<Vec<String>, Error> {
1661        let doc = YamlDoc::parse(yaml).unwrap();
1662        Ok(JsonPath::parse(path)?
1663            .query(&doc, 0)?
1664            .iter()
1665            .map(|matched| matched.pointer().as_str().to_owned())
1666            .collect())
1667    }
1668
1669    #[test]
1670    fn selects_names_wildcards_unions_descendants_and_slices() {
1671        let yaml = "users:\n  - {name: Ada, age: 37}\n  - {name: Linus, age: 55}\n";
1672        assert_eq!(
1673            pointers("$.users[*].name", yaml).unwrap(),
1674            ["/users/0/name", "/users/1/name"]
1675        );
1676        assert_eq!(
1677            pointers("$..age", yaml).unwrap(),
1678            ["/users/0/age", "/users/1/age"]
1679        );
1680        assert_eq!(
1681            pointers("$.users[1,0].name", yaml).unwrap(),
1682            ["/users/1/name", "/users/0/name"]
1683        );
1684        assert_eq!(
1685            pointers("$.users[::-1].name", yaml).unwrap(),
1686            ["/users/1/name", "/users/0/name"]
1687        );
1688    }
1689
1690    #[test]
1691    fn filters_and_standard_functions_work() {
1692        let yaml =
1693            "users:\n  - {name: Ada, tags: [rust, yaml]}\n  - {name: linus, tags: [kernel]}\n";
1694        assert_eq!(
1695            pointers("$.users[?length(@.tags) > 1].name", yaml).unwrap(),
1696            ["/users/0/name"]
1697        );
1698        assert_eq!(
1699            pointers(r#"$.users[?match(@.name, "[A-Z].*")].name"#, yaml).unwrap(),
1700            ["/users/0/name"]
1701        );
1702        assert_eq!(
1703            pointers(r#"$.users[?search(@.name, "inu")].name"#, yaml).unwrap(),
1704            ["/users/1/name"]
1705        );
1706        assert_eq!(
1707            pointers(
1708                "$.users[?match(@.name, @.pattern)].name",
1709                "users: [{name: Ada, pattern: '[A-Z].*'}]\n",
1710            )
1711            .unwrap(),
1712            ["/users/0/name"]
1713        );
1714        assert_eq!(
1715            pointers("$.users[?count(@.tags[*]) == 1].name", yaml).unwrap(),
1716            ["/users/1/name"]
1717        );
1718        assert_eq!(
1719            pointers("$.users[?@.tags[*] && !@.missing].name", yaml).unwrap(),
1720            ["/users/0/name", "/users/1/name"]
1721        );
1722        assert_eq!(
1723            pointers(r#"$.users[?value(@.name) == "Ada"].name"#, yaml).unwrap(),
1724            ["/users/0/name"]
1725        );
1726        let error = JsonPath::parse(r#"$[?match(@, "[")]"#).unwrap_err();
1727        assert_eq!(error.kind(), ErrorKind::Regex);
1728    }
1729
1730    #[test]
1731    fn exposes_escaped_pointers_empty_roots_and_duplicate_matches() {
1732        assert_eq!(
1733            pointers("$['a/b~c']", "'a/b~c': value\n").unwrap(),
1734            ["/a~1b~0c"]
1735        );
1736
1737        let doc = YamlDoc::parse("---\n").unwrap();
1738        let matches = JsonPath::parse("$").unwrap().query(&doc, 0).unwrap();
1739        assert_eq!(matches.len(), 1);
1740        assert_eq!(matches.iter().next().unwrap().pointer().as_str(), "");
1741        assert_eq!(matches.iter().next().unwrap().node(), None);
1742
1743        assert_eq!(pointers("$['a','a']", "a: 1\n").unwrap(), ["/a", "/a"]);
1744    }
1745
1746    #[test]
1747    fn rejects_values_outside_the_json_data_model() {
1748        for yaml in [
1749            "1: value\n",
1750            "{a: 1, a: 2}\n",
1751            "value: .inf\n",
1752            "!custom value\n",
1753        ] {
1754            let doc = YamlDoc::parse(yaml).unwrap();
1755            let error = JsonPath::parse("$").unwrap().query(&doc, 0).unwrap_err();
1756            assert_eq!(error.kind(), ErrorKind::DataModel, "{error}");
1757        }
1758
1759        let doc = YamlDoc::parse("&root [*root]\n").unwrap();
1760        let error = JsonPath::parse("$").unwrap().query(&doc, 0).unwrap_err();
1761        assert_eq!(error.kind(), ErrorKind::Alias);
1762
1763        let doc = YamlDoc::parse("copy: *missing\n").unwrap();
1764        let error = JsonPath::parse("$").unwrap().query(&doc, 0).unwrap_err();
1765        assert_eq!(error.kind(), ErrorKind::Alias);
1766        assert_eq!(error.source_span(), Some(Span::new(6, 14)));
1767    }
1768
1769    #[test]
1770    fn preserves_alias_occurrence_paths_and_compares_large_numbers_exactly() {
1771        let yaml = "base: &base {name: Ada}\ncopy: *base\n";
1772        assert_eq!(
1773            pointers("$.*.name", yaml).unwrap(),
1774            ["/base/name", "/copy/name"]
1775        );
1776
1777        assert_eq!(
1778            pointers("$[?@ > 9e999]", "[9e999, 1e1000]\n").unwrap(),
1779            ["/1"]
1780        );
1781    }
1782
1783    #[test]
1784    fn from_str_and_structured_syntax_errors_are_public() {
1785        let parsed = "$.value".parse::<JsonPath>().unwrap();
1786        let doc = YamlDoc::parse("value: 1\n").unwrap();
1787        assert_eq!(parsed.query(&doc, 0).unwrap().len(), 1);
1788
1789        let error = JsonPath::parse("value").unwrap_err();
1790        assert_eq!(error.kind(), ErrorKind::Syntax);
1791        assert_eq!(error.byte_offset(), Some(0));
1792        assert_eq!(error.source_span(), None);
1793    }
1794
1795    #[test]
1796    fn document_limits_bound_jsonpath_validation_and_aliases() {
1797        let expansion_limits = ResourceLimits {
1798            max_expanded_nodes: 3,
1799            ..ResourceLimits::default()
1800        };
1801        let doc =
1802            YamlDoc::parse_with_limits("items: [one, two, three]\n", expansion_limits).unwrap();
1803        let error = JsonPath::parse("$").unwrap().query(&doc, 0).unwrap_err();
1804        assert_eq!(error.kind(), ErrorKind::Limit);
1805        assert!(error.to_string().contains("expansion limit"));
1806
1807        let alias_limits = ResourceLimits {
1808            max_alias_chain: 0,
1809            ..ResourceLimits::default()
1810        };
1811        let doc = YamlDoc::parse_with_limits("source: &source one\ncopy: *source\n", alias_limits)
1812            .unwrap();
1813        let error = JsonPath::parse("$").unwrap().query(&doc, 0).unwrap_err();
1814        assert_eq!(error.kind(), ErrorKind::Limit);
1815        assert!(error.to_string().contains("alias chain limit"));
1816    }
1817}