Skip to main content

zero_client/json/
parse.rs

1use super::value::{ObjectBuilder, RecentKeys};
2use super::{Object, Value};
3use std::fmt;
4
5/// Why [`parse`] rejected its input.
6#[derive(Clone, Debug, PartialEq, Eq)]
7pub struct ParseError {
8    pub message: &'static str,
9    /// The byte offset of the problem.
10    pub offset: usize,
11}
12
13impl fmt::Display for ParseError {
14    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
15        write!(f, "{} at offset {}", self.message, self.offset)
16    }
17}
18
19impl std::error::Error for ParseError {}
20
21/// Nesting deeper than this is rejected with [`TOO_DEEP`].
22///
23/// It is above the about 4,100 levels zero-cache can write, so the client
24/// takes any value the server sends. JS has no limit short of its own
25/// stack; see `rust/PARITY.md`. Parsing, cloning, comparing, and writing a
26/// value don't recurse that deep, and dropping one fits in a 2 MB thread
27/// stack (the default for spawned Rust threads) even in a debug build.
28pub const MAX_DEPTH: usize = 5_000;
29
30/// The message of the error for JSON nested deeper than [`MAX_DEPTH`].
31pub const TOO_DEEP: &str = "JSON nested too deeply";
32
33/// Parses JSON text as `JSON.parse` does.
34///
35/// Differences from JS are limited to what a Rust `String` can hold: an
36/// escaped lone surrogate (`"\ud800"`) becomes U+FFFD, and nesting is
37/// limited to [`MAX_DEPTH`].
38pub fn parse(text: &str) -> Result<Value, ParseError> {
39    let mut p = Parser {
40        b: text.as_bytes(),
41        i: 0,
42        recent: RecentKeys::default(),
43    };
44    p.skip_whitespace();
45    let value = p.parse_value()?;
46    p.skip_whitespace();
47    if p.i != p.b.len() {
48        return Err(p.error("Unexpected non-whitespace character after JSON"));
49    }
50    Ok(value)
51}
52
53struct Parser<'a> {
54    b: &'a [u8],
55    i: usize,
56    recent: RecentKeys,
57}
58
59/// An array or object that the value being parsed is in.
60enum Container {
61    Array(Vec<Value>),
62    /// An object and the key of the value being parsed: `None` for the key
63    /// the layout it follows has next (see `Parser::next_key`).
64    Object(ObjectBuilder, Option<String>),
65}
66
67impl Parser<'_> {
68    fn error(&self, message: &'static str) -> ParseError {
69        ParseError {
70            message,
71            offset: self.i,
72        }
73    }
74
75    fn peek(&self) -> Option<u8> {
76        self.b.get(self.i).copied()
77    }
78
79    fn skip_whitespace(&mut self) {
80        while let Some(b' ' | b'\t' | b'\n' | b'\r') = self.peek() {
81            self.i += 1;
82        }
83    }
84
85    /// Parses a value without recursion: the arrays and objects it is in are
86    /// on `stack`, so nesting takes heap, not stack.
87    fn parse_value(&mut self) -> Result<Value, ParseError> {
88        let mut stack: Vec<Container> = Vec::new();
89        loop {
90            let Some(c) = self.peek() else {
91                return Err(self.error("Unexpected end of JSON input"));
92            };
93            let mut value = match c {
94                b'{' | b'[' => {
95                    if stack.len() >= MAX_DEPTH {
96                        return Err(self.error(TOO_DEEP));
97                    }
98                    let is_object = c == b'{';
99                    self.i += 1;
100                    self.skip_whitespace();
101                    if self.peek() == Some(if is_object { b'}' } else { b']' }) {
102                        self.i += 1;
103                        if is_object {
104                            Value::Object(Object::new())
105                        } else {
106                            Value::Array(Vec::new())
107                        }
108                    } else {
109                        if is_object {
110                            let mut builder = ObjectBuilder::default();
111                            let key = self.next_key(&mut builder)?;
112                            stack.push(Container::Object(builder, key));
113                        } else {
114                            stack.push(Container::Array(Vec::new()));
115                        }
116                        continue;
117                    }
118                }
119                b'"' => Value::String(self.parse_string()?),
120                b't' => {
121                    self.expect_literal(b"true")?;
122                    Value::Bool(true)
123                }
124                b'f' => {
125                    self.expect_literal(b"false")?;
126                    Value::Bool(false)
127                }
128                b'n' => {
129                    self.expect_literal(b"null")?;
130                    Value::Null
131                }
132                b'-' | b'0'..=b'9' => Value::Number(self.parse_number()?),
133                _ => return Err(self.error("Unexpected token")),
134            };
135            // Adds the value to its container, closing the containers that
136            // end after it, until one has another value.
137            loop {
138                self.skip_whitespace();
139                match stack.last_mut() {
140                    None => return Ok(value),
141                    Some(Container::Array(a)) => {
142                        a.push(value);
143                        match self.peek() {
144                            None => return Err(self.error("Unexpected end of JSON input")),
145                            Some(b',') => {
146                                self.i += 1;
147                                self.skip_whitespace();
148                                break;
149                            }
150                            Some(b']') => self.i += 1,
151                            Some(_) => {
152                                return Err(self.error("Expected ',' or ']' after array element"));
153                            }
154                        }
155                    }
156                    Some(Container::Object(o, key)) => {
157                        // A repeated key keeps its first place and its last value.
158                        match key.take() {
159                            Some(k) => {
160                                o.insert(k, value);
161                            }
162                            None => o.push_expected(value),
163                        }
164                        match self.peek() {
165                            None => return Err(self.error("Unexpected end of JSON input")),
166                            Some(b',') => {
167                                self.i += 1;
168                                *key = self.next_key(o)?;
169                                break;
170                            }
171                            Some(b'}') => self.i += 1,
172                            Some(_) => {
173                                return Err(self.error("Expected ',' or '}' after property value"));
174                            }
175                        }
176                    }
177                }
178                value = match stack.pop() {
179                    Some(Container::Array(a)) => Value::Array(a),
180                    Some(Container::Object(o, _)) => {
181                        let mut o = o.build();
182                        self.recent.remember(&mut o);
183                        Value::Object(o)
184                    }
185                    None => unreachable!(),
186                };
187            }
188        }
189    }
190
191    /// A property name and its colon, and the whitespace around them.
192    fn parse_key(&mut self) -> Result<String, ParseError> {
193        self.skip_whitespace();
194        match self.peek() {
195            None => return Err(self.error("Unexpected end of JSON input")),
196            Some(b'"') => {}
197            Some(_) => return Err(self.error("Expected property name")),
198        }
199        let key = self.parse_string()?;
200        self.skip_whitespace();
201        if self.peek() != Some(b':') {
202            return Err(self.error("Expected ':' after property name"));
203        }
204        self.i += 1;
205        self.skip_whitespace();
206        Ok(key)
207    }
208
209    /// Reads `o`'s next key. When it is the next key of the layout `o`
210    /// follows, or of a recent layout with `o`'s keys before it, `o` follows
211    /// that layout and the key, which is the layout's, isn't allocated:
212    /// `None`. Otherwise the key as [`Parser::parse_key`] reads it.
213    fn next_key(&mut self, o: &mut ObjectBuilder) -> Result<Option<String>, ParseError> {
214        self.skip_whitespace();
215        let found = o.prefix().and_then(|(prefix, next)| match next {
216            Some(k) if self.is_raw_key(k) => Some((None, k.len())),
217            _ => self
218                .recent
219                .find_next(prefix, |k| self.is_raw_key(k))
220                .map(|layout| {
221                    let len = layout.names[prefix.len()].len();
222                    (Some(layout), len)
223                }),
224        });
225        let Some((layout, len)) = found else {
226            return Ok(Some(self.parse_key()?));
227        };
228        if let Some(layout) = layout {
229            o.follow(layout);
230        }
231        self.skip_raw_key(len)?;
232        Ok(None)
233    }
234
235    /// Whether the input is at `key` as a string without escapes, which then
236    /// parses as `key`.
237    fn is_raw_key(&self, key: &str) -> bool {
238        let k = key.as_bytes();
239        let start = self.i + 1;
240        self.peek() == Some(b'"')
241            && self.b.get(start..start + k.len()) == Some(k)
242            && self.b.get(start + k.len()) == Some(&b'"')
243            && k.iter().all(|&c| c >= 0x20 && c != b'"' && c != b'\\')
244    }
245
246    /// Skips a key of `len` bytes that [`Parser::is_raw_key`] accepted, and
247    /// the colon after it, as [`Parser::parse_key`] does.
248    fn skip_raw_key(&mut self, len: usize) -> Result<(), ParseError> {
249        self.i += len + 2;
250        self.skip_whitespace();
251        if self.peek() != Some(b':') {
252            return Err(self.error("Expected ':' after property name"));
253        }
254        self.i += 1;
255        self.skip_whitespace();
256        Ok(())
257    }
258
259    fn expect_literal(&mut self, literal: &[u8]) -> Result<(), ParseError> {
260        if self.b.len() - self.i < literal.len() {
261            return Err(self.error("Unexpected end of JSON input"));
262        }
263        if &self.b[self.i..self.i + literal.len()] != literal {
264            return Err(self.error("Unexpected token"));
265        }
266        self.i += literal.len();
267        Ok(())
268    }
269
270    fn parse_string(&mut self) -> Result<String, ParseError> {
271        self.i += 1; // opening quote
272        let start = self.i;
273        // Fast path: no escapes.
274        while let Some(c) = self.peek() {
275            match c {
276                b'"' => {
277                    let s = self.text(start, self.i);
278                    self.i += 1;
279                    return Ok(s);
280                }
281                b'\\' => break,
282                0..0x20 => return Err(self.error("Bad control character in string literal")),
283                _ => self.i += 1,
284            }
285        }
286        let mut out = self.text(start, self.i);
287        while let Some(c) = self.peek() {
288            match c {
289                b'"' => {
290                    self.i += 1;
291                    return Ok(out);
292                }
293                0..0x20 => return Err(self.error("Bad control character in string literal")),
294                b'\\' => {}
295                _ => {
296                    // Copies the run up to the next quote, backslash or control.
297                    let run = self.i;
298                    while let Some(c) = self.peek() {
299                        if c == b'"' || c == b'\\' || c < 0x20 {
300                            break;
301                        }
302                        self.i += 1;
303                    }
304                    out.push_str(&self.text(run, self.i));
305                    continue;
306                }
307            }
308            self.i += 1;
309            let Some(e) = self.peek() else {
310                return Err(self.error("Unterminated string"));
311            };
312            self.i += 1;
313            match e {
314                b'"' => out.push('"'),
315                b'\\' => out.push('\\'),
316                b'/' => out.push('/'),
317                b'b' => out.push('\u{8}'),
318                b'f' => out.push('\u{c}'),
319                b'n' => out.push('\n'),
320                b'r' => out.push('\r'),
321                b't' => out.push('\t'),
322                b'u' => {
323                    let unit = self.parse_hex4()?;
324                    let ch = if (0xD800..=0xDBFF).contains(&unit) {
325                        // A high surrogate; combine with a following escaped
326                        // low surrogate.
327                        if self.b[self.i..].starts_with(b"\\u") && self.b.len() - self.i >= 6 {
328                            let save = self.i;
329                            self.i += 2;
330                            let low = self.parse_hex4()?;
331                            if (0xDC00..=0xDFFF).contains(&low) {
332                                char::from_u32(0x10000 + ((unit - 0xD800) << 10) + (low - 0xDC00))
333                                    .unwrap_or('\u{FFFD}')
334                            } else {
335                                self.i = save;
336                                '\u{FFFD}'
337                            }
338                        } else {
339                            '\u{FFFD}'
340                        }
341                    } else {
342                        char::from_u32(unit).unwrap_or('\u{FFFD}')
343                    };
344                    out.push(ch);
345                }
346                _ => return Err(self.error("Bad escaped character in JSON")),
347            }
348        }
349        Err(self.error("Unterminated string in JSON"))
350    }
351
352    /// The text between two byte offsets, which are on character boundaries
353    /// because they are next to ASCII bytes.
354    fn text(&self, start: usize, end: usize) -> String {
355        String::from_utf8_lossy(&self.b[start..end]).into_owned()
356    }
357
358    fn parse_hex4(&mut self) -> Result<u32, ParseError> {
359        if self.b.len() - self.i < 4 {
360            return Err(self.error("Bad Unicode escape"));
361        }
362        let mut v = 0;
363        for _ in 0..4 {
364            let d = match self.b[self.i] {
365                c @ b'0'..=b'9' => c - b'0',
366                c @ b'a'..=b'f' => c - b'a' + 10,
367                c @ b'A'..=b'F' => c - b'A' + 10,
368                _ => return Err(self.error("Bad Unicode escape")),
369            };
370            v = v << 4 | u32::from(d);
371            self.i += 1;
372        }
373        Ok(v)
374    }
375
376    fn parse_number(&mut self) -> Result<f64, ParseError> {
377        let start = self.i;
378        let digits = |p: &mut Self| {
379            let from = p.i;
380            while p.peek().is_some_and(|c| c.is_ascii_digit()) {
381                p.i += 1;
382            }
383            p.i - from
384        };
385        if self.peek() == Some(b'-') {
386            self.i += 1;
387        }
388        match self.peek() {
389            Some(b'0') => self.i += 1,
390            Some(b'1'..=b'9') => {
391                digits(self);
392            }
393            _ => return Err(self.error("No number after minus sign")),
394        }
395        if self.peek() == Some(b'.') {
396            self.i += 1;
397            if digits(self) == 0 {
398                return Err(self.error("Unterminated fractional number"));
399            }
400        }
401        if let Some(b'e' | b'E') = self.peek() {
402            self.i += 1;
403            if let Some(b'+' | b'-') = self.peek() {
404                self.i += 1;
405            }
406            if digits(self) == 0 {
407                return Err(self.error("Exponent part is missing a number"));
408            }
409        }
410        // Rust's parse rounds correctly and overflows to infinity, as JS
411        // does, and keeps `-0` negative.
412        let text = std::str::from_utf8(&self.b[start..self.i]).expect("ASCII");
413        text.parse().map_err(|_| self.error("Bad number"))
414    }
415}