ignition_core/deploy/
node.rs

1//! Order-preserving JSON tree and the Gson-compatible writer (DRND-05).
2//!
3//! Gateway-written JSON is Gson pretty output. Render passes files through
4//! as bytes; this module only decides whether a file *may be rewritten*
5//! (uuid injection in 21-07) and gives the secret lint (21-08) a tree to
6//! walk. A file is [`JsonClass::GatewayFormat`] when
7//! `write(parse(bytes)) == bytes`, otherwise [`JsonClass::Opaque`] and render
8//! never mutates it.
9//!
10//! ## The tree
11//!
12//! [`Node`] keeps object members in source order (never sorted: the spec's
13//! "sorted keys" is wrong, ROADMAP constraint) and keeps every number,
14//! `true`, `false` and `null` as its original lexeme ([`Node::Lit`]), so
15//! `2.50`, `1.0E10`, `-0.0` and `18446744073709551616` survive unchanged.
16//! `serde_json` runs with `raw_value` only; `preserve_order` and
17//! `arbitrary_precision` stay off.
18//!
19//! ## The writer: Gson pretty, HTML-safe
20//!
21//! 2-space indent, `": "` between key and value, one member or element per
22//! line, `{}` and `[]` for empty containers, no trailing newline. Strings
23//! and keys are escaped as Gson's `JsonWriter` does with HTML-safe on
24//! (`ESC(hhhh)` below is the six characters backslash, `u`, four lowercase
25//! hex digits):
26//!
27//! | Character | Written as |
28//! |---|---|
29//! | `"` and `\` | backslash-escaped |
30//! | TAB, BS, LF, CR, FF | backslash then `t`, `b`, `n`, `r`, `f` |
31//! | other code points below U+0020 | `ESC(00hh)` |
32//! | `<` `>` `&` `=` `'` | `ESC(003c)` `ESC(003e)` `ESC(0026)` `ESC(003d)` `ESC(0027)` |
33//! | U+2028, U+2029 | `ESC(2028)`, `ESC(2029)` |
34//! | everything else, DEL and non-ASCII included | raw UTF-8 |
35//!
36//! Raw UTF-8 for non-ASCII is decision CD4 (21-LIVE-CAPTURES.md): the 8.3.6
37//! gateway wrote `Température ✓` unescaped.
38//!
39//! Errors are `String`s carrying serde_json's line/column text or a key
40//! name, never a value (T-21-22).
41
42use std::collections::BTreeSet;
43use std::fmt;
44
45use serde::de::{Deserialize, Deserializer, MapAccess, Visitor};
46use serde_json::value::RawValue;
47
48/// Per-file size cap for a `.json` member (16 MiB). Larger files are refused
49/// before any parse (T-21-19).
50pub const JSON_MAX_BYTES: usize = 16_777_216;
51
52/// Deepest container nesting [`parse`] accepts (serde_json's own default
53/// recursion limit). Checked by a linear scan before the recursive build, so
54/// hostile nesting can neither overflow the stack nor cost
55/// O(depth x size) (T-21-19).
56pub const MAX_DEPTH: usize = 128;
57
58/// An order-preserving JSON document node.
59#[derive(Debug, Clone, PartialEq, Eq)]
60pub enum Node {
61    /// Object members in source order; keys are unique within one object.
62    Obj(Vec<(String, Node)>),
63    /// Array elements.
64    Arr(Vec<Node>),
65    /// A decoded string value.
66    Str(String),
67    /// A number, `true`, `false` or `null`, as its source lexeme.
68    Lit(String),
69}
70
71impl Node {
72    /// The value of member `key` when this is an object that has it.
73    pub fn get(&self, key: &str) -> Option<&Node> {
74        match self {
75            Node::Obj(members) => members.iter().find(|(k, _)| k == key).map(|(_, v)| v),
76            _ => None,
77        }
78    }
79
80    /// The decoded text when this is a string.
81    pub fn as_str(&self) -> Option<&str> {
82        match self {
83            Node::Str(s) => Some(s),
84            _ => None,
85        }
86    }
87}
88
89/// Whether render may rewrite a JSON file.
90#[derive(Debug, Clone, Copy, PartialEq, Eq)]
91pub enum JsonClass {
92    /// `write(parse(bytes)) == bytes`: rewritable without changing a byte.
93    GatewayFormat,
94    /// Parses, but is not in the gateway's writer format: never mutated.
95    Opaque,
96}
97
98/// Object members, refusing a repeated key (T-21-20).
99struct Members(Vec<(String, Box<RawValue>)>);
100
101impl<'de> Deserialize<'de> for Members {
102    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
103        struct V;
104        impl<'de> Visitor<'de> for V {
105            type Value = Members;
106
107            fn expecting(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
108                f.write_str("a JSON object")
109            }
110
111            fn visit_map<A: MapAccess<'de>>(self, mut map: A) -> Result<Members, A::Error> {
112                let mut seen: BTreeSet<String> = BTreeSet::new();
113                let mut out = Vec::new();
114                while let Some((key, value)) = map.next_entry::<String, Box<RawValue>>()? {
115                    if !seen.insert(key.clone()) {
116                        return Err(serde::de::Error::custom(format!(
117                            "duplicate key `{key}` in one object"
118                        )));
119                    }
120                    out.push((key, value));
121                }
122                Ok(Members(out))
123            }
124        }
125        deserializer.deserialize_map(V)
126    }
127}
128
129/// Parse one JSON document into a [`Node`].
130///
131/// The whole document is validated once (syntax and trailing content), then
132/// its nesting depth is measured with a linear scan ([`MAX_DEPTH`]) before
133/// the recursive build, so the build depth is bounded. Duplicate keys within
134/// one object are an error.
135pub fn parse(src: &str) -> Result<Node, String> {
136    let raw: Box<RawValue> = serde_json::from_str(src).map_err(|e| e.to_string())?;
137    if max_depth(raw.get().as_bytes()) > MAX_DEPTH {
138        return Err(format!("nesting deeper than {MAX_DEPTH} levels"));
139    }
140    build(raw.get())
141}
142
143/// Deepest `{`/`[` nesting of already-validated JSON text. String contents
144/// (including escaped quotes) are skipped.
145fn max_depth(bytes: &[u8]) -> usize {
146    let (mut depth, mut deepest, mut in_string, mut escaped) = (0usize, 0usize, false, false);
147    for &b in bytes {
148        if in_string {
149            if escaped {
150                escaped = false;
151            } else if b == b'\\' {
152                escaped = true;
153            } else if b == b'"' {
154                in_string = false;
155            }
156            continue;
157        }
158        match b {
159            b'"' => in_string = true,
160            b'{' | b'[' => {
161                depth += 1;
162                deepest = deepest.max(depth);
163            }
164            b'}' | b']' => depth = depth.saturating_sub(1),
165            _ => {}
166        }
167    }
168    deepest
169}
170
171fn build(text: &str) -> Result<Node, String> {
172    let t = text.trim();
173    match t.as_bytes().first() {
174        Some(b'{') => {
175            let Members(members) = serde_json::from_str(t).map_err(|e| e.to_string())?;
176            let mut out = Vec::with_capacity(members.len());
177            for (key, value) in members {
178                out.push((key, build(value.get())?));
179            }
180            Ok(Node::Obj(out))
181        }
182        Some(b'[') => {
183            let items: Vec<Box<RawValue>> = serde_json::from_str(t).map_err(|e| e.to_string())?;
184            let mut out = Vec::with_capacity(items.len());
185            for item in items {
186                out.push(build(item.get())?);
187            }
188            Ok(Node::Arr(out))
189        }
190        Some(b'"') => Ok(Node::Str(
191            serde_json::from_str::<String>(t).map_err(|e| e.to_string())?,
192        )),
193        _ => Ok(Node::Lit(t.to_string())),
194    }
195}
196
197/// Write `node` in the gateway's Gson pretty format (see the module doc).
198pub fn write(node: &Node) -> String {
199    let mut out = String::new();
200    write_node(node, 0, &mut out);
201    out
202}
203
204fn indent(depth: usize, out: &mut String) {
205    for _ in 0..depth {
206        out.push_str("  ");
207    }
208}
209
210fn write_node(node: &Node, depth: usize, out: &mut String) {
211    match node {
212        Node::Lit(lexeme) => out.push_str(lexeme),
213        Node::Str(s) => write_string(s, out),
214        Node::Obj(members) if members.is_empty() => out.push_str("{}"),
215        Node::Arr(items) if items.is_empty() => out.push_str("[]"),
216        Node::Obj(members) => {
217            out.push_str("{\n");
218            for (i, (key, value)) in members.iter().enumerate() {
219                if i > 0 {
220                    out.push_str(",\n");
221                }
222                indent(depth + 1, out);
223                write_string(key, out);
224                out.push_str(": ");
225                write_node(value, depth + 1, out);
226            }
227            out.push('\n');
228            indent(depth, out);
229            out.push('}');
230        }
231        Node::Arr(items) => {
232            out.push_str("[\n");
233            for (i, value) in items.iter().enumerate() {
234                if i > 0 {
235                    out.push_str(",\n");
236                }
237                indent(depth + 1, out);
238                write_node(value, depth + 1, out);
239            }
240            out.push('\n');
241            indent(depth, out);
242            out.push(']');
243        }
244    }
245}
246
247fn write_string(s: &str, out: &mut String) {
248    out.push('"');
249    for c in s.chars() {
250        match c {
251            '"' => out.push_str("\\\""),
252            '\\' => out.push_str("\\\\"),
253            '\t' => out.push_str("\\t"),
254            '\u{8}' => out.push_str("\\b"),
255            '\n' => out.push_str("\\n"),
256            '\r' => out.push_str("\\r"),
257            '\u{c}' => out.push_str("\\f"),
258            '<' | '>' | '&' | '=' | '\'' | '\u{2028}' | '\u{2029}' => {
259                out.push_str(&format!("\\u{:04x}", c as u32));
260            }
261            c if (c as u32) < 0x20 => out.push_str(&format!("\\u{:04x}", c as u32)),
262            c => out.push(c),
263        }
264    }
265    out.push('"');
266}
267
268/// Classify a `.json` member's bytes and return its parsed tree.
269///
270/// Refuses (as `Err`): more than [`JSON_MAX_BYTES`] bytes, invalid UTF-8, a
271/// leading byte-order mark, and anything [`parse`] refuses (syntax, trailing
272/// content, nesting beyond [`MAX_DEPTH`], a repeated key).
273pub fn classify(bytes: &[u8]) -> Result<(JsonClass, Node), String> {
274    if bytes.len() > JSON_MAX_BYTES {
275        return Err(format!(
276            "JSON file is {} bytes, over the {JSON_MAX_BYTES}-byte cap",
277            bytes.len()
278        ));
279    }
280    let text = std::str::from_utf8(bytes)
281        .map_err(|e| format!("not valid UTF-8 (valid up to byte {})", e.valid_up_to()))?;
282    if text.starts_with('\u{feff}') {
283        return Err("starts with a byte-order mark".to_string());
284    }
285    let node = parse(text)?;
286    let class = if write(&node).as_bytes() == bytes {
287        JsonClass::GatewayFormat
288    } else {
289        JsonClass::Opaque
290    };
291    Ok((class, node))
292}
293
294#[cfg(test)]
295mod tests {
296    use super::*;
297    use proptest::prelude::*;
298
299    /// ESC(hhhh): backslash, `u`, four lowercase hex digits.
300    fn esc(hex: &str) -> String {
301        format!("\\u{hex}")
302    }
303
304    #[test]
305    fn gson_escapes() {
306        let s = "<>&='\"\\\u{2028}\u{2029}\t\n\r\u{8}\u{c}\u{1}";
307        let got = write(&Node::Str(s.to_string()));
308        let want = format!(
309            "\"{}{}{}{}{}\\\"\\\\{}{}\\t\\n\\r\\b\\f{}\"",
310            esc("003c"),
311            esc("003e"),
312            esc("0026"),
313            esc("003d"),
314            esc("0027"),
315            esc("2028"),
316            esc("2029"),
317            esc("0001"),
318        );
319        assert_eq!(got, want);
320        // keys are escaped the same way
321        let key = write(&Node::Obj(vec![("a<b".into(), Node::Lit("1".into()))]));
322        assert_eq!(key, format!("{{\n  \"a{}b\": 1\n}}", esc("003c")));
323    }
324
325    #[test]
326    fn non_ascii_follows_cd4() {
327        // CD4: 8.3.6 wrote `Température ✓` as raw UTF-8
328        assert_eq!(write(&Node::Str("é✓".into())), "\"é✓\"");
329        assert_eq!(write(&Node::Str("\u{7f}".into())), "\"\u{7f}\"");
330    }
331
332    #[test]
333    fn pretty_layout() {
334        let n = parse(r#"{"a":{"b":[1,{"c":[]},{}],"d":{}},"e":[],"f":"x"}"#).unwrap();
335        let want = "{\n  \"a\": {\n    \"b\": [\n      1,\n      {\n        \"c\": []\n      },\n      {}\n    ],\n    \"d\": {}\n  },\n  \"e\": [],\n  \"f\": \"x\"\n}";
336        assert_eq!(write(&n), want);
337        assert!(!write(&n).ends_with('\n'));
338    }
339
340    #[test]
341    fn member_order_preserved() {
342        let n = parse(r#"{"b":1,"a":2}"#).unwrap();
343        assert_eq!(write(&n), "{\n  \"b\": 1,\n  \"a\": 2\n}");
344        match n {
345            Node::Obj(m) => assert_eq!(m[0].0, "b"),
346            _ => panic!("object"),
347        }
348    }
349
350    #[test]
351    fn number_lexemes_preserved() {
352        let src = "[\n  2.50,\n  1.0E10,\n  -0.0,\n  18446744073709551616\n]";
353        let n = parse(src).unwrap();
354        assert_eq!(write(&n), src);
355        let (class, _) = classify(src.as_bytes()).unwrap();
356        assert_eq!(class, JsonClass::GatewayFormat);
357    }
358
359    #[test]
360    fn duplicate_key_refused() {
361        let err = parse(r#"{"a":1,"a":2}"#).unwrap_err();
362        assert!(err.contains("duplicate key `a`"), "{err}");
363        // nested too
364        let err = parse(r#"{"x":{"k":1,"k":null}}"#).unwrap_err();
365        assert!(err.contains("`k`"), "{err}");
366    }
367
368    #[test]
369    fn classify_boundaries() {
370        let mut at_cap = b"{}".to_vec();
371        at_cap.resize(JSON_MAX_BYTES, b' ');
372        let (class, _) = classify(&at_cap).expect("exactly the cap classifies");
373        assert_eq!(class, JsonClass::Opaque);
374
375        at_cap.push(b' ');
376        let err = classify(&at_cap).unwrap_err();
377        assert!(
378            err.contains("16777217") && err.contains("16777216"),
379            "{err}"
380        );
381
382        assert!(classify(&[b'{', 0xff, b'}']).unwrap_err().contains("UTF-8"));
383        assert!(
384            classify("\u{feff}{}".as_bytes())
385                .unwrap_err()
386                .contains("byte-order mark")
387        );
388        assert!(classify(b"{} x").is_err());
389        assert!(classify(b"{\"a\":").is_err());
390        let deep = format!("{}{}", "[".repeat(200), "]".repeat(200));
391        assert!(classify(deep.as_bytes()).unwrap_err().contains("nesting"));
392        let at_limit = format!("{}{}", "[".repeat(MAX_DEPTH), "]".repeat(MAX_DEPTH));
393        assert!(classify(at_limit.as_bytes()).is_ok());
394        // brackets inside strings do not count
395        assert!(parse(&format!("[\"{}\\\"{}\"]", "[".repeat(300), "{".repeat(300))).is_ok());
396    }
397
398    #[test]
399    fn classify_trailing_newline_is_opaque() {
400        let doc = "{\n  \"a\": 1\n}";
401        assert_eq!(
402            classify(doc.as_bytes()).unwrap().0,
403            JsonClass::GatewayFormat
404        );
405        let with_nl = format!("{doc}\n");
406        assert_eq!(classify(with_nl.as_bytes()).unwrap().0, JsonClass::Opaque);
407    }
408
409    #[test]
410    fn errors_never_echo_values() {
411        let err = parse(r#"{"a":"SECRETVALUE" "b":1}"#).unwrap_err();
412        assert!(!err.contains("SECRETVALUE"), "{err}");
413    }
414
415    fn arb_string() -> impl Strategy<Value = String> {
416        prop::collection::vec(
417            prop::sample::select(vec![
418                'a', 'Z', '0', ' ', '<', '>', '&', '=', '\'', '"', '\\', '\t', '\n', 'é',
419                '\u{2028}',
420            ]),
421            0..8,
422        )
423        .prop_map(|v| v.into_iter().collect())
424    }
425
426    fn arb_node() -> impl Strategy<Value = Node> {
427        let leaf = prop_oneof![
428            arb_string().prop_map(Node::Str),
429            prop::sample::select(vec![
430                "2.50",
431                "1.0E10",
432                "-0.0",
433                "18446744073709551616",
434                "0",
435                "-1",
436                "true",
437                "false",
438                "null"
439            ])
440            .prop_map(|s| Node::Lit(s.to_string())),
441        ];
442        leaf.prop_recursive(4, 48, 4, |inner| {
443            prop_oneof![
444                prop::collection::vec(inner.clone(), 0..4).prop_map(Node::Arr),
445                prop::collection::vec((arb_string(), inner), 0..4).prop_map(|members| {
446                    let mut seen = BTreeSet::new();
447                    Node::Obj(
448                        members
449                            .into_iter()
450                            .filter(|(k, _)| seen.insert(k.clone()))
451                            .collect(),
452                    )
453                }),
454            ]
455        })
456    }
457
458    proptest! {
459        #[test]
460        fn writer_idempotence(n in arb_node()) {
461            let text = write(&n);
462            let back = parse(&text).unwrap();
463            prop_assert_eq!(&back, &n);
464            prop_assert_eq!(write(&back), text.clone());
465            prop_assert_eq!(classify(text.as_bytes()).unwrap().0, JsonClass::GatewayFormat);
466        }
467    }
468}
ignition_core/deploy/node.rs

ignition_core/deploy/
node.rs
