Skip to main content

zero_client/json/
parse.rs

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