omgbase_store/
tree.rs

1//! Canonical encodings (`spec/store/README.md` §4.1): tree-node entries,
2//! canonical attrs JSON and the Merkle node hash.
3
4use omgbase_format::Attrs;
5use omgbase_format::hash::{hex, sha256};
6use omgbase_format::json::attrs_to_json;
7use serde_json::Value;
8
9use crate::error::{Error, Result};
10
11/// One entry of a tree node: the six-element array of §4.1.
12#[derive(Clone, Debug, PartialEq)]
13pub struct TreeEntry {
14    pub block_id: String,
15    /// `sha256(raw)`, lowercase hex.
16    pub raw_hash_hex: String,
17    /// The children's node hash, or `None` for a leaf.
18    pub child_tree_hash_hex: Option<String>,
19    /// The spec/format §3 kind name.
20    pub kind: String,
21    /// The block's attrs as a JSON object.
22    pub attrs: Value,
23    /// The trailing trivia blob's hash, or `None` when the trivia is empty.
24    pub trivia_hash_hex: Option<String>,
25}
26
27/// JSON with object keys sorted bytewise ascending (recursively) and no
28/// whitespace — the reference's `canonicalAttrs`/`canonicalValue`. Scalars
29/// print as `serde_json` prints them (booleans, integers and strings agree
30/// with `JSON.stringify`; attrs never carry floats).
31#[must_use]
32pub fn canonical_json(v: &Value) -> String {
33    let mut out = String::new();
34    write_canonical(v, &mut out);
35    out
36}
37
38fn write_canonical(v: &Value, out: &mut String) {
39    match v {
40        Value::Object(map) => {
41            let mut keys: Vec<&String> = map.keys().collect();
42            keys.sort_unstable_by(|a, b| a.as_bytes().cmp(b.as_bytes()));
43            out.push('{');
44            for (i, k) in keys.iter().enumerate() {
45                if i > 0 {
46                    out.push(',');
47                }
48                out.push_str(&Value::String((*k).clone()).to_string());
49                out.push(':');
50                write_canonical(&map[*k], out);
51            }
52            out.push('}');
53        }
54        Value::Array(items) => {
55            out.push('[');
56            for (i, item) in items.iter().enumerate() {
57                if i > 0 {
58                    out.push(',');
59                }
60                write_canonical(item, out);
61            }
62            out.push(']');
63        }
64        scalar => out.push_str(&scalar.to_string()),
65    }
66}
67
68/// A block's attrs as canonical JSON (§4.1 `attrs_canonical`; also what this
69/// crate writes to `blocks.attrs`).
70#[must_use]
71pub fn canonical_attrs(attrs: &Attrs) -> String {
72    canonical_json(&attrs_to_json(attrs))
73}
74
75/// The canonical entries serialization: an array of six-element arrays, no
76/// whitespace, `null` for a missing child tree or trivia.
77#[must_use]
78pub fn serialize_tree_entries(entries: &[TreeEntry]) -> String {
79    let mut out = String::from("[");
80    for (i, e) in entries.iter().enumerate() {
81        if i > 0 {
82            out.push(',');
83        }
84        out.push('[');
85        out.push_str(&Value::String(e.block_id.clone()).to_string());
86        out.push(',');
87        out.push_str(&Value::String(e.raw_hash_hex.clone()).to_string());
88        out.push(',');
89        match &e.child_tree_hash_hex {
90            Some(h) => out.push_str(&Value::String(h.clone()).to_string()),
91            None => out.push_str("null"),
92        }
93        out.push(',');
94        out.push_str(&Value::String(e.kind.clone()).to_string());
95        out.push(',');
96        out.push_str(&canonical_json(&e.attrs));
97        out.push(',');
98        match &e.trivia_hash_hex {
99            Some(h) => out.push_str(&Value::String(h.clone()).to_string()),
100            None => out.push_str("null"),
101        }
102        out.push(']');
103    }
104    out.push(']');
105    out
106}
107
108/// `sha256(serialize_tree_entries(entries))`.
109#[must_use]
110pub fn tree_hash(entries: &[TreeEntry]) -> [u8; 32] {
111    sha256(serialize_tree_entries(entries).as_bytes())
112}
113
114/// Parse a stored `tree_nodes.entries` text back into entries.
115pub fn parse_tree_entries(text: &str) -> Result<Vec<TreeEntry>> {
116    let rows: Vec<Value> = serde_json::from_str(text)?;
117    rows.into_iter()
118        .map(|row| {
119            let arr = row
120                .as_array()
121                .filter(|a| a.len() == 6)
122                .ok_or_else(|| Error::Other("tree entry is not a six-element array".to_owned()))?;
123            let string = |i: usize| -> Result<String> {
124                arr[i]
125                    .as_str()
126                    .map(str::to_owned)
127                    .ok_or_else(|| Error::Other(format!("tree entry field {i} is not a string")))
128            };
129            let optional = |i: usize| -> Result<Option<String>> {
130                match &arr[i] {
131                    Value::Null => Ok(None),
132                    Value::String(s) => Ok(Some(s.clone())),
133                    _ => Err(Error::Other(format!(
134                        "tree entry field {i} is neither a string nor null"
135                    ))),
136                }
137            };
138            if !arr[4].is_object() {
139                return Err(Error::Other("tree entry attrs is not an object".to_owned()));
140            }
141            Ok(TreeEntry {
142                block_id: string(0)?,
143                raw_hash_hex: string(1)?,
144                child_tree_hash_hex: optional(2)?,
145                kind: string(3)?,
146                attrs: arr[4].clone(),
147                trivia_hash_hex: optional(5)?,
148            })
149        })
150        .collect()
151}
152
153/// Hex of a 32-byte hash (re-exported convenience).
154#[must_use]
155pub fn hash_hex(hash: &[u8]) -> String {
156    hex(hash)
157}
158
159/// Decode lowercase or uppercase hex into bytes.
160pub fn from_hex(s: &str) -> Result<Vec<u8>> {
161    if s.len() % 2 != 0 {
162        return Err(Error::Other(format!("odd-length hex {s:?}")));
163    }
164    (0..s.len())
165        .step_by(2)
166        .map(|i| {
167            u8::from_str_radix(&s[i..i + 2], 16)
168                .map_err(|_| Error::Other(format!("invalid hex {s:?}")))
169        })
170        .collect()
171}
172
173#[cfg(test)]
174mod tests {
175    use super::*;
176    use omgbase_format::AttrValue;
177    use serde_json::json;
178
179    fn entry() -> TreeEntry {
180        TreeEntry {
181            block_id: "b_k7z2p9q".to_owned(),
182            raw_hash_hex: "deadbeef".to_owned(),
183            child_tree_hash_hex: None,
184            kind: "paragraph".to_owned(),
185            attrs: json!({}),
186            trivia_hash_hex: None,
187        }
188    }
189
190    #[test]
191    fn canonical_attrs_sorts_keys_without_whitespace() {
192        assert_eq!(
193            canonical_json(&json!({ "b": 1, "a": 2 })),
194            r#"{"a":2,"b":1}"#
195        );
196        assert_eq!(canonical_json(&json!({})), "{}");
197        assert_eq!(
198            canonical_json(&json!({ "z": [3, 1], "a": { "y": 1, "x": 2 } })),
199            r#"{"a":{"x":2,"y":1},"z":[3,1]}"#
200        );
201        let mut attrs = Attrs::new();
202        attrs.insert("level".to_owned(), AttrValue::Int(2));
203        attrs.insert("checked".to_owned(), AttrValue::Bool(true));
204        attrs.insert("lang".to_owned(), AttrValue::Str("a \"q\" \n".to_owned()));
205        assert_eq!(
206            canonical_attrs(&attrs),
207            r#"{"checked":true,"lang":"a \"q\" \n","level":2}"#
208        );
209        // Bytewise: uppercase sorts before lowercase, as JavaScript's sort().
210        assert_eq!(
211            canonical_json(&json!({ "b": 1, "B": 2 })),
212            r#"{"B":2,"b":1}"#
213        );
214    }
215
216    #[test]
217    fn serializes_positional_entries_canonically() {
218        assert_eq!(
219            serialize_tree_entries(&[entry()]),
220            r#"[["b_k7z2p9q","deadbeef",null,"paragraph",{},null]]"#
221        );
222        let mut two = entry();
223        two.child_tree_hash_hex = Some("aa".to_owned());
224        two.trivia_hash_hex = Some("bb".to_owned());
225        two.attrs = json!({ "ordered": true, "level": 1 });
226        assert_eq!(
227            serialize_tree_entries(&[entry(), two]),
228            r#"[["b_k7z2p9q","deadbeef",null,"paragraph",{},null],["b_k7z2p9q","deadbeef","aa","paragraph",{"level":1,"ordered":true},"bb"]]"#
229        );
230        assert_eq!(serialize_tree_entries(&[]), "[]");
231    }
232
233    #[test]
234    fn tree_hash_matches_the_reference_golden_vector() {
235        assert_eq!(
236            hex(&tree_hash(&[entry()])),
237            "1d1679899502cbd6996749f2eb8f2ebdc4f786fbb144edd4bec82a3dbd4cd4c1"
238        );
239        assert_eq!(tree_hash(&[entry()]), tree_hash(&[entry().clone()]));
240    }
241
242    #[test]
243    fn parses_what_it_serializes() {
244        let mut two = entry();
245        two.child_tree_hash_hex = Some("aa".to_owned());
246        two.attrs = json!({ "level": 1 });
247        let text = serialize_tree_entries(&[entry(), two.clone()]);
248        let parsed = parse_tree_entries(&text).unwrap();
249        assert_eq!(parsed, vec![entry(), two]);
250        assert!(parse_tree_entries("[[1,2]]").is_err());
251        assert!(parse_tree_entries("not json").is_err());
252        assert!(parse_tree_entries(r#"[["b","h",null,"paragraph",[],null]]"#).is_err());
253    }
254
255    #[test]
256    fn hex_round_trip() {
257        assert_eq!(from_hex("00ff1a").unwrap(), vec![0x00, 0xff, 0x1a]);
258        assert_eq!(hash_hex(&[0x00, 0xff, 0x1a]), "00ff1a");
259        assert!(from_hex("abc").is_err());
260        assert!(from_hex("zz").is_err());
261    }
262}
omgbase_store/tree.rs

omgbase_store/
tree.rs
