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