1use super::DecodeError;
7
8#[derive(Debug, Clone, PartialEq)]
9pub enum Node {
10 Null,
11 Bool(bool),
12 Number(String),
14 String(String),
15 Array(Vec<Node>),
16 Object(Vec<(String, Node)>),
17}
18
19impl Node {
20 pub fn is_null(&self) -> bool {
21 matches!(self, Node::Null)
22 }
23
24 pub fn member(&self, name: &str) -> Option<&Node> {
26 match self {
27 Node::Object(members) => members
28 .iter()
29 .rev()
30 .find(|(k, _)| k.eq_ignore_ascii_case(name))
31 .map(|(_, v)| v),
32 _ => None,
33 }
34 }
35
36 pub fn to_value(&self) -> Result<serde_json::Value, DecodeError> {
40 enum Open<'a> {
41 Array(std::slice::Iter<'a, Node>, Vec<serde_json::Value>),
42 Object(
43 std::slice::Iter<'a, (String, Node)>,
44 serde_json::Map<String, serde_json::Value>,
45 String,
46 ),
47 }
48 let mut stack: Vec<Open> = Vec::new();
49 let mut next = self;
50 loop {
51 let mut done = match next {
52 Node::Null => Some(serde_json::Value::Null),
53 Node::Bool(b) => Some(serde_json::Value::Bool(*b)),
54 Node::Number(n) => match parse_f64(n) {
55 Ok(f) => Some(
56 serde_json::Number::from_f64(f)
57 .map(serde_json::Value::Number)
58 .unwrap_or(serde_json::Value::Null),
59 ),
60 Err(e) => {
61 for open in stack {
62 match open {
63 Open::Array(_, out) => out.into_iter().for_each(dispose),
64 Open::Object(_, out, _) => out.into_iter().for_each(|(_, v)| dispose(v)),
65 }
66 }
67 return Err(e);
68 }
69 },
70 Node::String(s) => Some(serde_json::Value::String(s.clone())),
71 Node::Array(items) => {
72 stack.push(Open::Array(items.iter(), Vec::with_capacity(items.len())));
73 None
74 }
75 Node::Object(members) => {
76 stack.push(Open::Object(members.iter(), serde_json::Map::new(), String::new()));
77 None
78 }
79 };
80 loop {
82 if let Some(value) = done.take() {
83 match stack.last_mut() {
84 None => return Ok(value),
85 Some(Open::Array(_, out)) => out.push(value),
86 Some(Open::Object(_, out, key)) => {
87 if let Some(old) = out.insert(std::mem::take(key), value) {
89 dispose(old);
90 }
91 }
92 }
93 }
94 match stack.last_mut() {
95 None => unreachable!("an open container is pending"),
96 Some(Open::Array(items, _)) => {
97 if let Some(item) = items.next() {
98 next = item;
99 break;
100 }
101 }
102 Some(Open::Object(members, _, key)) => {
103 if let Some((k, v)) = members.next() {
104 key.clone_from(k);
105 next = v;
106 break;
107 }
108 }
109 }
110 done = Some(match stack.pop() {
111 Some(Open::Array(_, out)) => serde_json::Value::Array(out),
112 Some(Open::Object(_, out, _)) => serde_json::Value::Object(out),
113 None => unreachable!(),
114 });
115 }
116 }
117 }
118
119 pub fn to_json(&self) -> Vec<u8> {
121 enum Step<'a> {
122 Node(&'a Node),
123 Key(&'a str),
124 Byte(u8),
125 }
126 let mut out = Vec::new();
127 let mut steps = vec![Step::Node(self)];
128 while let Some(step) = steps.pop() {
129 let node = match step {
130 Step::Byte(b) => {
131 out.push(b);
132 continue;
133 }
134 Step::Key(k) => {
135 cpa_common::json::marshal_str(&mut out, k.as_bytes(), false);
136 continue;
137 }
138 Step::Node(node) => node,
139 };
140 match node {
141 Node::Null => out.extend_from_slice(b"null"),
142 Node::Bool(b) => out.extend_from_slice(if *b { b"true" } else { b"false" }),
143 Node::Number(n) => out.extend_from_slice(n.as_bytes()),
144 Node::String(s) => cpa_common::json::marshal_str(&mut out, s.as_bytes(), false),
145 Node::Array(items) => {
146 out.push(b'[');
147 steps.push(Step::Byte(b']'));
148 for (i, item) in items.iter().enumerate().rev() {
149 steps.push(Step::Node(item));
150 if i > 0 {
151 steps.push(Step::Byte(b','));
152 }
153 }
154 }
155 Node::Object(members) => {
156 out.push(b'{');
157 steps.push(Step::Byte(b'}'));
158 for (i, (k, v)) in members.iter().enumerate().rev() {
159 steps.push(Step::Node(v));
160 steps.push(Step::Byte(b':'));
161 steps.push(Step::Key(k));
162 if i > 0 {
163 steps.push(Step::Byte(b','));
164 }
165 }
166 }
167 }
168 }
169 out
170 }
171}
172
173fn dispose(value: serde_json::Value) {
176 let mut pending = vec![value];
177 while let Some(mut value) = pending.pop() {
178 match &mut value {
179 serde_json::Value::Array(items) => pending.append(items),
180 serde_json::Value::Object(members) => {
181 pending.extend(std::mem::take(members).into_iter().map(|(_, v)| v));
182 }
183 _ => {}
184 }
185 }
186}
187
188impl Drop for Node {
191 fn drop(&mut self) {
192 let mut pending: Vec<Node> = Vec::new();
193 let take = |node: &mut Node, pending: &mut Vec<Node>| match node {
194 Node::Array(items) => pending.append(items),
195 Node::Object(members) => pending.extend(members.drain(..).map(|(_, v)| v)),
196 _ => {}
197 };
198 take(self, &mut pending);
199 while let Some(mut node) = pending.pop() {
200 take(&mut node, &mut pending);
201 }
202 }
203}
204
205pub fn parse_f64(lexeme: &str) -> Result<f64, DecodeError> {
207 match lexeme.parse::<f64>() {
208 Ok(f) if f.is_finite() => Ok(f),
209 _ => Err(DecodeError(format!(
210 "json: cannot unmarshal number {lexeme} into Go value of type float64"
211 ))),
212 }
213}
214
215const MAX_DEPTH: usize = 10000;
216
217enum Frame {
218 Array(Vec<Node>),
219 Object(Vec<(String, Node)>, String),
220}
221
222struct Parser<'a> {
223 s: &'a [u8],
224 i: usize,
225}
226
227fn describe(c: u8) -> String {
228 match c {
229 b'\'' => r"'\''".to_owned(),
230 b'"' => r#"'"'"#.to_owned(),
231 c if c.is_ascii_graphic() || c == b' ' => format!("'{}'", c as char),
232 c => format!("{:?}", c as char),
233 }
234}
235
236impl Parser<'_> {
237 fn ws(&mut self) {
238 while self.i < self.s.len() && matches!(self.s[self.i], b' ' | b'\t' | b'\n' | b'\r') {
239 self.i += 1;
240 }
241 }
242
243 fn err(&self, context: &str) -> DecodeError {
244 match self.s.get(self.i) {
245 None => DecodeError("unexpected end of JSON input".into()),
246 Some(&c) => DecodeError(format!("invalid character {} {context}", describe(c))),
247 }
248 }
249
250 fn literal(&mut self, word: &[u8], node: Node) -> Result<Node, DecodeError> {
252 for &expected in word {
253 if self.s.get(self.i) != Some(&expected) {
254 return Err(self.err(&format!(
255 "in literal {} (expecting {})",
256 String::from_utf8_lossy(word),
257 describe(expected)
258 )));
259 }
260 self.i += 1;
261 }
262 Ok(node)
263 }
264
265 fn number(&mut self) -> Result<Node, DecodeError> {
266 let start = self.i;
267 let digits = |p: &mut Self| {
268 let from = p.i;
269 while p.i < p.s.len() && p.s[p.i].is_ascii_digit() {
270 p.i += 1;
271 }
272 p.i > from
273 };
274 if self.s.get(self.i) == Some(&b'-') {
275 self.i += 1;
276 }
277 match self.s.get(self.i) {
278 Some(b'0') => self.i += 1,
279 Some(b'1'..=b'9') => {
280 digits(self);
281 }
282 _ => return Err(self.err("in numeric literal")),
283 }
284 if self.s.get(self.i) == Some(&b'.') {
285 self.i += 1;
286 if !digits(self) {
287 return Err(self.err("after decimal point in numeric literal"));
288 }
289 }
290 if matches!(self.s.get(self.i), Some(b'e' | b'E')) {
291 self.i += 1;
292 if matches!(self.s.get(self.i), Some(b'+' | b'-')) {
293 self.i += 1;
294 }
295 if !digits(self) {
296 return Err(self.err("in exponent of numeric literal"));
297 }
298 }
299 Ok(Node::Number(
300 String::from_utf8_lossy(&self.s[start..self.i]).into_owned(),
301 ))
302 }
303
304 fn hex4(&self, at: usize) -> Option<u32> {
305 let hex = self.s.get(at..at + 4)?;
306 u32::from_str_radix(std::str::from_utf8(hex).ok()?, 16).ok()
307 }
308
309 fn string(&mut self) -> Result<String, DecodeError> {
311 self.i += 1;
312 let mut out = String::new();
313 loop {
314 let Some(&c) = self.s.get(self.i) else {
315 return Err(DecodeError("unexpected end of JSON input".into()));
316 };
317 match c {
318 b'"' => {
319 self.i += 1;
320 return Ok(out);
321 }
322 b'\\' => {
323 let Some(&e) = self.s.get(self.i + 1) else {
324 return Err(DecodeError("unexpected end of JSON input".into()));
325 };
326 self.i += 2;
327 match e {
328 b'"' => out.push('"'),
329 b'\\' => out.push('\\'),
330 b'/' => out.push('/'),
331 b'b' => out.push('\u{8}'),
332 b'f' => out.push('\u{c}'),
333 b'n' => out.push('\n'),
334 b'r' => out.push('\r'),
335 b't' => out.push('\t'),
336 b'u' => {
337 let Some(first) = self.hex4(self.i) else {
338 self.i += self.s[self.i..]
339 .iter()
340 .take(4)
341 .take_while(|c| c.is_ascii_hexdigit())
342 .count();
343 return Err(self.err("in \\u hexadecimal character escape"));
344 };
345 self.i += 4;
346 if (0xD800..0xDC00).contains(&first)
347 && self.s.get(self.i..self.i + 2) == Some(b"\\u")
348 && let Some(second) = self.hex4(self.i + 2)
349 && (0xDC00..0xE000).contains(&second)
350 {
351 self.i += 6;
352 let c = 0x10000 + ((first - 0xD800) << 10) + (second - 0xDC00);
353 out.push(char::from_u32(c).unwrap_or('\u{FFFD}'));
354 } else {
355 out.push(char::from_u32(first).unwrap_or('\u{FFFD}'));
356 }
357 }
358 _ => {
359 self.i -= 1;
360 return Err(self.err("in string escape code"));
361 }
362 }
363 }
364 c if c < 0x20 => return Err(self.err("in string literal")),
365 c if c < 0x80 => {
366 out.push(c as char);
367 self.i += 1;
368 }
369 _ => {
370 let (rune, size) = cpa_common::json::decode_rune(&self.s[self.i..]);
371 out.push(rune.unwrap_or('\u{FFFD}'));
372 self.i += size.max(1);
373 }
374 }
375 }
376 }
377
378 fn scalar_or_open(&mut self, stack: &mut Vec<Frame>) -> Result<Option<Node>, DecodeError> {
379 self.ws();
380 match self.s.get(self.i) {
381 Some(b'{') => {
382 self.i += 1;
383 stack.push(Frame::Object(Vec::new(), String::new()));
384 Ok(None)
385 }
386 Some(b'[') => {
387 self.i += 1;
388 stack.push(Frame::Array(Vec::new()));
389 Ok(None)
390 }
391 Some(b'"') => self.string().map(|s| Some(Node::String(s))),
392 Some(b't') => self.literal(b"true", Node::Bool(true)).map(Some),
393 Some(b'f') => self.literal(b"false", Node::Bool(false)).map(Some),
394 Some(b'n') => self.literal(b"null", Node::Null).map(Some),
395 Some(b'-' | b'0'..=b'9') => self.number().map(Some),
396 _ => Err(self.err("looking for beginning of value")),
397 }
398 }
399}
400
401pub fn parse(raw: &[u8]) -> Result<Node, DecodeError> {
403 parse_value(raw, true)
404}
405
406pub fn parse_first(raw: &[u8]) -> Result<Node, DecodeError> {
410 if raw.iter().all(|c| matches!(c, b' ' | b'\t' | b'\n' | b'\r')) {
411 return Err(DecodeError("EOF".into()));
412 }
413 parse_value(raw, false).map_err(|e| match e.0.as_str() {
414 "unexpected end of JSON input" => DecodeError("unexpected EOF".into()),
415 _ => e,
416 })
417}
418
419fn parse_value(raw: &[u8], whole: bool) -> Result<Node, DecodeError> {
421 let mut p = Parser { s: raw, i: 0 };
422 let mut stack: Vec<Frame> = Vec::new();
423 let mut value = p.scalar_or_open(&mut stack)?;
425 loop {
426 if stack.len() > MAX_DEPTH {
427 return Err(DecodeError("exceeded max depth".into()));
428 }
429 if value.is_none() {
431 match stack.last_mut() {
432 Some(Frame::Object(members, key)) => {
433 p.ws();
434 if members.is_empty() && p.s.get(p.i) == Some(&b'}') {
435 p.i += 1;
436 let Some(Frame::Object(members, _)) = stack.pop() else {
437 unreachable!()
438 };
439 value = Some(Node::Object(members));
440 } else {
441 if p.s.get(p.i) != Some(&b'"') {
442 return Err(p.err("looking for beginning of object key string"));
443 }
444 *key = p.string()?;
445 p.ws();
446 if p.s.get(p.i) != Some(&b':') {
447 return Err(p.err("after object key"));
448 }
449 p.i += 1;
450 value = p.scalar_or_open(&mut stack)?;
451 continue;
452 }
453 }
454 Some(Frame::Array(items)) => {
455 p.ws();
456 if items.is_empty() && p.s.get(p.i) == Some(&b']') {
457 p.i += 1;
458 let Some(Frame::Array(items)) = stack.pop() else {
459 unreachable!()
460 };
461 value = Some(Node::Array(items));
462 } else {
463 value = p.scalar_or_open(&mut stack)?;
464 continue;
465 }
466 }
467 None => unreachable!("a value or an open container is always pending"),
468 }
469 }
470 let done = value.take().expect("value set above");
471 match stack.last_mut() {
472 None => {
473 p.ws();
474 if whole && p.i < p.s.len() {
475 return Err(p.err("after top-level value"));
476 }
477 return Ok(done);
478 }
479 Some(Frame::Array(items)) => {
480 items.push(done);
481 p.ws();
482 match p.s.get(p.i) {
483 Some(b',') => {
484 p.i += 1;
485 value = p.scalar_or_open(&mut stack)?;
486 }
487 Some(b']') => {
488 p.i += 1;
489 let Some(Frame::Array(items)) = stack.pop() else {
490 unreachable!()
491 };
492 value = Some(Node::Array(items));
493 }
494 _ => return Err(p.err("after array element")),
495 }
496 }
497 Some(Frame::Object(members, key)) => {
498 members.push((std::mem::take(key), done));
499 p.ws();
500 match p.s.get(p.i) {
501 Some(b',') => {
502 p.i += 1;
503 p.ws();
504 if p.s.get(p.i) != Some(&b'"') {
505 return Err(p.err("looking for beginning of object key string"));
506 }
507 let k = p.string()?;
508 p.ws();
509 if p.s.get(p.i) != Some(&b':') {
510 return Err(p.err("after object key"));
511 }
512 p.i += 1;
513 if let Some(Frame::Object(_, key)) = stack.last_mut() {
514 *key = k;
515 }
516 value = p.scalar_or_open(&mut stack)?;
517 }
518 Some(b'}') => {
519 p.i += 1;
520 let Some(Frame::Object(members, _)) = stack.pop() else {
521 unreachable!()
522 };
523 value = Some(Node::Object(members));
524 }
525 _ => return Err(p.err("after object key:value pair")),
526 }
527 }
528 }
529 }
530}
531
532#[cfg(test)]
533mod tests {
534 use super::*;
535
536 #[test]
537 fn keeps_duplicates_lexemes_and_go_string_rules() {
538 let n = parse(br#" {"a":1.50,"a":[true,null,{}],"s":"\ud83d\ude00\ud800x\u00e9","e":[]} "#).unwrap();
539 let Node::Object(m) = &n else { panic!() };
540 assert_eq!(m.len(), 4);
541 assert_eq!(m[0], ("a".into(), Node::Number("1.50".into())));
542 assert_eq!(m[2].1, Node::String("😀\u{FFFD}xé".into()));
543 assert_eq!(
544 String::from_utf8(n.to_json()).unwrap(),
545 r#"{"a":1.50,"a":[true,null,{}],"s":"😀�xé","e":[]}"#
546 );
547 assert_eq!(parse(b"\"\xe2\x82\"").unwrap(), Node::String("\u{FFFD}\u{FFFD}".into()));
549 for bad in [
550 &b"{\"a\":1,}"[..],
551 b"[01]",
552 b"\"a\nb\"",
553 b"{} x",
554 b"",
555 b"[1.]",
556 b"tru",
557 b"{\"a\" 1}",
558 ] {
559 assert!(parse(bad).is_err(), "{:?}", String::from_utf8_lossy(bad));
560 }
561 let deep = format!("{}{}", "[".repeat(10001), "]".repeat(10001));
562 assert!(parse(deep.as_bytes()).is_err());
563 let ok = format!("{}{}", "[".repeat(9999), "]".repeat(9999));
564 assert!(parse(ok.as_bytes()).is_ok());
565 }
566
567 #[test]
568 fn deep_documents_convert_and_drop_without_recursion() {
569 let text = format!("{}1{}", r#"{"a":["#.repeat(4999), "]}".repeat(4999));
570 let node = parse(text.as_bytes()).unwrap();
571 assert_eq!(node.to_json(), text.as_bytes());
572 let mut value = node.to_value().unwrap();
573 for _ in 0..4999 {
574 value = value["a"][0].take();
575 }
576 assert_eq!(value, serde_json::json!(1.0));
577 let dup = parse(br#"{"k":{"x":1},"k":[2,{"y":null}]}"#).unwrap();
579 assert_eq!(dup.to_value().unwrap(), serde_json::json!({"k": [2.0, {"y": null}]}));
580 assert_eq!(dup.to_json(), br#"{"k":{"x":1},"k":[2,{"y":null}]}"#);
581 let deep = format!("{}{}", "[".repeat(9990), "]".repeat(9990));
584 let replaced = parse(format!(r#"{{"k":{deep},"k":0}}"#).as_bytes()).unwrap();
585 assert_eq!(replaced.to_value().unwrap(), serde_json::json!({"k": 0.0}));
586 let overflow = parse(format!(r#"[{deep},1e400]"#).as_bytes()).unwrap();
587 assert!(overflow.to_value().is_err());
588 }
589}