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 = 5_000;
29
30pub const TOO_DEEP: &str = "JSON nested too deeply";
32
33pub 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
59enum Container {
61 Array(Vec<Value>),
62 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 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 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 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 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 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 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 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; let start = self.i;
273 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 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 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 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 let text = std::str::from_utf8(&self.b[start..self.i]).expect("ASCII");
413 text.parse().map_err(|_| self.error("Bad number"))
414 }
415}