1use super::value::{ObjectBuilder, RecentKeys};
2use super::{Object, Value};
3use std::fmt;
4
5#[derive(Clone, Debug, PartialEq, Eq)]
7pub struct ParseError {
8 pub message: &'static str,
9 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
21pub const MAX_DEPTH: usize = 1_500;
28
29pub const TOO_DEEP: &str = "JSON nested too deeply";
31
32pub 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
58enum Container {
60 Array(Vec<Value>),
61 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 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 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 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 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 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 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 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; let start = self.i;
272 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 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 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 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 let text = std::str::from_utf8(&self.b[start..self.i]).expect("ASCII");
412 text.parse().map_err(|_| self.error("Bad number"))
413 }
414}