Skip to main content

cpa_plugin/gojson/
node.rs

1//! A parsed JSON document as Go's decoder walks it: every object member in order
2//! (duplicates included), numbers as their literal text, strings unquoted the way
3//! `encoding/json` does (invalid UTF-8 bytes and lone surrogates become U+FFFD).
4//! Syntax follows Go's scanner; nesting is limited to 10000 levels, as in Go.
5
6use super::DecodeError;
7
8#[derive(Debug, Clone, PartialEq)]
9pub enum Node {
10    Null,
11    Bool(bool),
12    /// The number literal.
13    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    /// The last member whose key matches `name` case-insensitively.
25    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    /// Go's `any` view: numbers as float64, objects with the last duplicate winning.
37    /// Walks with an explicit stack, so the 10000 levels `parse` accepts cannot
38    /// overflow the thread stack.
39    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            // Attach finished values to their parents until a parent has another child.
81            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                            // A duplicate key replaces the earlier value, which may be deep.
88                            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    /// Compact JSON text (for `json.RawMessage` fields).
120    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
173/// Drops a `serde_json::Value` with an explicit stack; its own drop glue recurses
174/// once per nesting level.
175fn 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
188/// Frees nested containers with an explicit stack instead of the recursive
189/// drop glue, which overflows the thread stack on deeply nested documents.
190impl 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
205/// `strconv.ParseFloat(s, 64)` as `encoding/json` uses it: overflow is an error.
206pub 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    /// Go's scanner: a wrong byte names the literal and the byte it expected.
251    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    /// Go's scanner rules plus `unquote`.
310    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
401/// `json.Unmarshal`'s syntax pass and value tree.
402pub fn parse(raw: &[u8]) -> Result<Node, DecodeError> {
403    parse_value(raw, true)
404}
405
406/// `json.NewDecoder(r).Decode` over a complete reader: the first value only, with
407/// anything after it left unread; a truncated value is `unexpected EOF` and input
408/// without any value `EOF`.
409pub 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
419/// The value tree; `whole` rejects anything but whitespace after the value.
420fn 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    // Each iteration either opens a container, or produces a value and attaches it.
424    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        // Object frames need a key before each value.
430        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        // Invalid UTF-8 becomes one U+FFFD per bad byte, as Go's unquote does.
548        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        // The last duplicate wins in Go's `any` view; the text keeps both.
578        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        // A deep value replaced by a later duplicate, and deep values already built
582        // when a later number overflows, are freed without recursion.
583        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}