yo_doc/
path.rs

1//! Reaching one field of a document without decoding the rest of it.
2//!
3//! `$.a.b[3].c` is four steps, and each step is a header read, a binary search
4//! or an index, and a seek. A ten kilobyte document with a four level path is
5//! four cache lines and no allocation, which is the whole reason the encoding
6//! is shaped the way it is.
7//!
8//! ```
9//! use yo_doc::{Builder, Value};
10//!
11//! let mut b = Builder::new();
12//! b.begin_object().unwrap();
13//! b.key(b"user").unwrap();
14//! b.begin_object().unwrap();
15//! b.key(b"tags").unwrap();
16//! b.begin_array().unwrap();
17//! b.text("a").unwrap();
18//! b.text("b").unwrap();
19//! b.end_array().unwrap();
20//! b.end_object().unwrap();
21//! b.end_object().unwrap();
22//! let bytes = b.finish().unwrap();
23//!
24//! let v = Value::new(&bytes).unwrap();
25//! assert_eq!(v.path("$.user.tags[1]").unwrap().unwrap().as_text(), Some("b"));
26//! assert_eq!(v.path("$.user.tags[-1]").unwrap().unwrap().as_text(), Some("b"));
27//! assert!(v.path("$.user.missing").unwrap().is_none());
28//! ```
29//!
30//! # What this grammar is
31//!
32//! The part of JSONPath that names exactly one place: a root, member access by
33//! name, and element access by index counting from either end. The parts that
34//! name a set of places, `[*]` and `..` and a slice and a union, are in
35//! [`query`](crate::query), because they answer a list and everything here
36//! answers at most one value.
37//!
38//! Both grammars read the same path the same way where they overlap, so a
39//! caller that knows it wants one field uses this and pays no allocation, and
40//! one that has taken a path from a client parses it with
41//! [`Path`](crate::Path) and finds out from
42//! [`is_definite`](crate::Path::is_definite) whether it named one place.
43
44use yo_common::{Code, Error, Result};
45
46use crate::head::Kind;
47use crate::read::Value;
48
49/// One step of a path.
50#[derive(Debug, Clone, Copy, PartialEq, Eq)]
51pub enum Step<'a> {
52    /// A member of an object, by name.
53    Key(&'a [u8]),
54    /// An element of an array. Negative counts back from the end, so -1 is the
55    /// last element.
56    Index(i64),
57}
58
59/// The steps of a path, parsed as they are walked.
60///
61/// Nothing is collected, so a path costs no allocation and a path that turns
62/// out to be nonsense costs only as much of itself as was read before the
63/// nonsense.
64#[derive(Debug, Clone)]
65pub struct Steps<'a> {
66    rest: &'a [u8],
67}
68
69impl<'a> Steps<'a> {
70    /// The steps of `path`.
71    ///
72    /// A leading `$` is the root and is optional, so both `$.a.b` and `a.b`
73    /// parse to the same two steps.
74    #[must_use]
75    pub fn new(path: &'a [u8]) -> Steps<'a> {
76        let rest = path.strip_prefix(b"$").unwrap_or(path);
77        Steps { rest }
78    }
79}
80
81impl<'a> Iterator for Steps<'a> {
82    type Item = Result<Step<'a>>;
83
84    fn next(&mut self) -> Option<Result<Step<'a>>> {
85        if self.rest.is_empty() {
86            return None;
87        }
88        Some(self.step())
89    }
90}
91
92impl<'a> Steps<'a> {
93    fn step(&mut self) -> Result<Step<'a>> {
94        match self.rest[0] {
95            b'.' => {
96                self.rest = &self.rest[1..];
97                if self.rest.first() == Some(&b'.') {
98                    return Err(bad(
99                        "a descent, `..`, names more than one place, so it is read by `Path` and not here",
100                    ));
101                }
102                let end = self
103                    .rest
104                    .iter()
105                    .position(|&c| c == b'.' || c == b'[')
106                    .unwrap_or(self.rest.len());
107                if end == 0 {
108                    return Err(bad("a `.` with no name after it"));
109                }
110                let (name, rest) = self.rest.split_at(end);
111                self.rest = rest;
112                Ok(Step::Key(name))
113            }
114            b'[' => self.bracket(),
115            _ => {
116                // A path may start with a bare name, so that `a.b` and `$.a.b`
117                // both work. Anywhere else this is a missing separator.
118                let end = self
119                    .rest
120                    .iter()
121                    .position(|&c| c == b'.' || c == b'[')
122                    .unwrap_or(self.rest.len());
123                let (name, rest) = self.rest.split_at(end);
124                self.rest = rest;
125                Ok(Step::Key(name))
126            }
127        }
128    }
129
130    fn bracket(&mut self) -> Result<Step<'a>> {
131        let body = &self.rest[1..];
132        let Some(close) = body.iter().position(|&c| c == b']') else {
133            return Err(bad("a `[` with no `]` after it"));
134        };
135        let inner = &body[..close];
136        self.rest = &body[close + 1..];
137        if inner == b"*" {
138            return Err(bad(
139                "a wildcard, `[*]`, names more than one place, so it is read by `Path` and not here",
140            ));
141        }
142        if let Some(quoted) = quoted(inner) {
143            return Ok(Step::Key(quoted));
144        }
145        let text = core::str::from_utf8(inner).map_err(|_| bad("an index that is not a number"))?;
146        let i: i64 = text
147            .parse()
148            .map_err(|_| bad("an index that is not a number"))?;
149        Ok(Step::Index(i))
150    }
151}
152
153/// The bytes inside `"..."` or `'...'`, if that is what this is.
154fn quoted(inner: &[u8]) -> Option<&[u8]> {
155    if inner.len() >= 2 {
156        let (first, last) = (inner[0], inner[inner.len() - 1]);
157        if (first == b'"' || first == b'\'') && last == first {
158            return Some(&inner[1..inner.len() - 1]);
159        }
160    }
161    None
162}
163
164impl<'a> Value<'a> {
165    /// The value at `path`, if there is one there.
166    ///
167    /// `Ok(None)` is a path that is well formed and names nothing, which is a
168    /// normal answer and not a failure. `Err` is a path that does not parse.
169    pub fn path(&self, path: &str) -> Result<Option<Value<'a>>> {
170        self.path_bytes(path.as_bytes())
171    }
172
173    /// [`Value::path`] over bytes, for the RESP side where a path arrives as a
174    /// bulk string.
175    pub fn path_bytes(&self, path: &[u8]) -> Result<Option<Value<'a>>> {
176        let mut at = *self;
177        for step in Steps::new(path) {
178            let Some(next) = at.step(step?) else {
179                return Ok(None);
180            };
181            at = next;
182        }
183        Ok(Some(at))
184    }
185
186    /// One step down from here.
187    #[must_use]
188    pub fn step(&self, step: Step<'_>) -> Option<Value<'a>> {
189        match step {
190            Step::Key(k) => self.get(k),
191            Step::Index(i) => {
192                if self.kind() != Kind::Array {
193                    return None;
194                }
195                let n = self.len();
196                let at = if i < 0 {
197                    n.checked_sub(i.unsigned_abs() as usize)?
198                } else {
199                    i as usize
200                };
201                self.at(at)
202            }
203        }
204    }
205}
206
207fn bad(what: &str) -> Error {
208    Error::new(Code::Invalid, what)
209}
210
211#[cfg(test)]
212mod tests {
213    use super::*;
214    use crate::Builder;
215
216    /// `{"a": {"b": [10, 20, {"c": "deep"}]}, "empty": {}}`
217    fn doc() -> Vec<u8> {
218        let mut b = Builder::new();
219        b.begin_object().expect("open");
220        b.key(b"a").expect("key");
221        b.begin_object().expect("open");
222        b.key(b"b").expect("key");
223        b.begin_array().expect("open");
224        b.int(10).expect("value");
225        b.int(20).expect("value");
226        b.begin_object().expect("open");
227        b.key(b"c").expect("key");
228        b.text("deep").expect("value");
229        b.end_object().expect("close");
230        b.end_array().expect("close");
231        b.end_object().expect("close");
232        b.key(b"empty").expect("key");
233        b.begin_object().expect("open");
234        b.end_object().expect("close");
235        b.end_object().expect("close");
236        b.finish().expect("finished").to_vec()
237    }
238
239    #[test]
240    fn a_path_reaches_what_it_names() {
241        let bytes = doc();
242        let v = Value::new(&bytes).expect("readable");
243        let at = |p: &str| v.path(p).expect("the path parses");
244        assert_eq!(at("$.a.b[0]").expect("there").as_int(), Some(10));
245        assert_eq!(at("$.a.b[2].c").expect("there").as_text(), Some("deep"));
246        assert_eq!(at("$.a.b[-1].c").expect("there").as_text(), Some("deep"));
247        assert_eq!(at("$.a.b[-3]").expect("there").as_int(), Some(10));
248        assert_eq!(at("$").expect("there").len(), 2);
249        assert_eq!(at("").expect("there").len(), 2);
250        // The three ways of writing the same step.
251        assert_eq!(at("$.a.b[0]").expect("there").as_int(), Some(10));
252        assert_eq!(at("$[\"a\"][\"b\"][0]").expect("there").as_int(), Some(10));
253        assert_eq!(at("a.b[0]").expect("there").as_int(), Some(10));
254        assert_eq!(at("$['a'].b[0]").expect("there").as_int(), Some(10));
255    }
256
257    #[test]
258    fn a_path_that_names_nothing_is_an_answer_and_not_a_failure() {
259        let bytes = doc();
260        let v = Value::new(&bytes).expect("readable");
261        let at = |p: &str| v.path(p).expect("the path parses");
262        assert!(at("$.nope").is_none());
263        assert!(at("$.a.nope.deeper").is_none());
264        assert!(at("$.a.b[3]").is_none(), "past the end");
265        assert!(at("$.a.b[-4]").is_none(), "past the start");
266        assert!(at("$.empty.anything").is_none());
267        assert!(at("$.a.b.c").is_none(), "a name into an array");
268        assert!(at("$.a[0]").is_none(), "an index into an object");
269        assert!(at("$.a.b[0][0]").is_none(), "an index into a number");
270    }
271
272    #[test]
273    fn a_path_that_does_not_parse_says_so() {
274        let bytes = doc();
275        let v = Value::new(&bytes).expect("readable");
276        let why = |p: &str| v.path(p).unwrap_err().message().to_string();
277        assert!(why("$.a[").contains("no `]`"));
278        assert!(why("$.a[x]").contains("not a number"));
279        assert!(why("$..a").contains("more than one place"));
280        assert!(why("$.a[*]").contains("more than one place"));
281        assert!(why("$.a.").contains("no name after it"));
282    }
283
284    #[test]
285    fn the_steps_of_a_path_are_what_they_look_like() {
286        let steps: Vec<Step<'_>> = Steps::new(b"$.a[3].bb[-1][\"c c\"]")
287            .map(|s| s.expect("parses"))
288            .collect();
289        assert_eq!(
290            steps,
291            [
292                Step::Key(b"a"),
293                Step::Index(3),
294                Step::Key(b"bb"),
295                Step::Index(-1),
296                Step::Key(b"c c"),
297            ]
298        );
299    }
300
301    #[test]
302    fn a_path_over_bytes_reads_the_same_as_a_path_over_text() {
303        let bytes = doc();
304        let v = Value::new(&bytes).expect("readable");
305        let one = v.path("$.a.b[1]").expect("parses").expect("there");
306        let two = v.path_bytes(b"$.a.b[1]").expect("parses").expect("there");
307        assert_eq!(one.as_int(), two.as_int());
308    }
309}
yo_doc/path.rs

yo_doc/
path.rs
