aleph_syntax_tree/
hash.rs

1use crate::syntax::AlephTree;
2
3/// A `blake3` digest identifying an `AlephTree` node by structural content,
4/// not by name or position. See `content_hash`.
5pub type NodeHash = [u8; 32];
6
7/// Deterministic content hash of an `AlephTree` node. Two structurally
8/// identical trees — same shape, same field values, regardless of how or
9/// where they were constructed — always hash to the same value; this is
10/// the identity Aleph-Next's content-addressed storage keys definitions by,
11/// not their name or their position in a file.
12///
13/// Deliberately not stored as a field on any `AlephTree` node: hashing a
14/// node that contains its own hash would be self-referential. Callers that
15/// need a "this definition, with its hash" pairing should keep the hash
16/// alongside the tree (e.g. `(NodeHash, AlephTree)`) rather than inside it.
17pub fn content_hash(node: &AlephTree) -> NodeHash {
18    let canonical = serde_json::to_vec(node).expect("AlephTree always serializes");
19    *blake3::hash(&canonical).as_bytes()
20}
21
22/// Hex-encoded form of [`content_hash`] — 64 lowercase hex characters.
23pub fn content_hash_hex(node: &AlephTree) -> String {
24    blake3::Hash::from(content_hash(node)).to_hex().to_string()
25}
26
27#[cfg(test)]
28mod tests {
29    use super::*;
30    use crate::syntax::AlephTree;
31
32    fn sample() -> AlephTree {
33        AlephTree::LetRec {
34            name: "square".to_string(),
35            args: vec![Box::new(AlephTree::Ident { value: "n".to_string() })],
36            body: Box::new(AlephTree::Mul {
37                number_expr1: Box::new(AlephTree::Ident { value: "n".to_string() }),
38                number_expr2: Box::new(AlephTree::Ident { value: "n".to_string() }),
39            }),
40        }
41    }
42
43    #[test]
44    fn same_structural_tree_hashes_identically() {
45        assert_eq!(content_hash(&sample()), content_hash(&sample()));
46    }
47
48    #[test]
49    fn different_tree_hashes_differently() {
50        let other = match sample() {
51            AlephTree::LetRec { args, body, .. } => AlephTree::LetRec {
52                name: "cube".to_string(),
53                args,
54                body,
55            },
56            _ => unreachable!(),
57        };
58        assert_ne!(content_hash(&sample()), content_hash(&other));
59    }
60
61    #[test]
62    fn hash_is_32_bytes() {
63        assert_eq!(content_hash(&sample()).len(), 32);
64    }
65
66    #[test]
67    fn hex_form_is_64_lowercase_hex_chars() {
68        let hex = content_hash_hex(&sample());
69        assert_eq!(hex.len(), 64);
70        assert!(hex.chars().all(|c| c.is_ascii_hexdigit() && !c.is_ascii_uppercase()));
71    }
72
73    #[test]
74    fn tree_with_extra_arg_hashes_differently() {
75        let with_extra_arg = AlephTree::LetRec {
76            name: "square".to_string(),
77            args: vec![
78                Box::new(AlephTree::Ident { value: "n".to_string() }),
79                Box::new(AlephTree::Ident { value: "unused".to_string() }),
80            ],
81            body: Box::new(AlephTree::Mul {
82                number_expr1: Box::new(AlephTree::Ident { value: "n".to_string() }),
83                number_expr2: Box::new(AlephTree::Ident { value: "n".to_string() }),
84            }),
85        };
86        assert_ne!(content_hash(&sample()), content_hash(&with_extra_arg));
87    }
88
89    #[test]
90    fn with_effects_hash_is_independent_of_effect_insertion_order() {
91        use crate::effects::{Effect, EffectSet};
92
93        let a = AlephTree::WithEffects {
94            inner: Box::new(sample()),
95            effects: EffectSet::from([Effect::Io, Effect::Net]),
96        };
97        let b = AlephTree::WithEffects {
98            inner: Box::new(sample()),
99            effects: EffectSet::from([Effect::Net, Effect::Io]),
100        };
101        assert_eq!(content_hash(&a), content_hash(&b));
102    }
103
104    #[test]
105    fn known_input_hashes_to_a_pinned_value() {
106        // Run this once, read the actual output, and hardcode it here — this
107        // is a regression guard: if this test ever needs to change, that's a
108        // signal the hash algorithm or the canonical serialization changed,
109        // which for a content-addressing primitive should never happen silently.
110        assert_eq!(
111            content_hash_hex(&sample()),
112            "1c5065803a4fbd2950297d8a3aa98b16f4dfc878e96a1492d462b6fee7f3c257"
113        );
114    }
115}
aleph_syntax_tree/hash.rs

aleph_syntax_tree/
hash.rs
