Skip to main content

publet_algorithms/
tree.rs

1//! Recursive Merkle trees over named, nested content -- the shape git's
2//! own tree objects use (a directory's hash commits to its entries'
3//! names and hashes, recursively), generalized past files and
4//! directories to any leaf-or-branch structure.
5//!
6//! Neither of this crate's other two trees models nesting. [`crate::membership`]
7//! is a sorted set: no entry contains another. [`crate::log`] is an
8//! append-only sequence: entries have an order, not a hierarchy. A
9//! source file's own definitions -- a method inside an `impl` block, a
10//! function nested inside a function -- are a tree, not a set or a
11//! sequence, and this is the third shape: every level of the hierarchy
12//! commits to everything beneath it, so changing one deeply nested leaf
13//! changes every ancestor's hash up to the root, the same
14//! tamper-evidence property the other two trees give at their own
15//! shape of structure.
16
17use std::collections::BTreeMap;
18
19use crate::log::{Hash, leaf_hash};
20
21/// One position in the tree: a leaf holding raw content, or a branch
22/// holding its own header bytes plus named children.
23///
24/// This enum is exhaustive on purpose, so a `match` on it needs no
25/// wildcard arm. A third kind of node would change how trees hash, which
26/// changes every root computed from one, so it could not arrive in a
27/// compatible release anyway.
28#[derive(Debug, Clone, PartialEq, Eq)]
29pub enum Node {
30    /// Content hashed directly -- a function's exact source text, say.
31    Leaf {
32        /// The leaf's own bytes.
33        content: Vec<u8>,
34    },
35    /// No content of its own beyond `header` (a signature line, a module
36    /// path -- whatever names this branch without needing its children
37    /// to render it), plus a set of named children, each itself a
38    /// [`Node`]. Two branches with the same header and the same
39    /// `(name, hash)` pairs -- regardless of child insertion order --
40    /// hash identically; that is what makes moving a method's textual
41    /// position in a file a no-op for its parent's hash.
42    Branch {
43        /// The branch's own identifying bytes, hashed but never
44        /// expanded further -- there is nothing under `header` itself
45        /// to recurse into.
46        header: Vec<u8>,
47        /// Children, keyed by name. A `BTreeMap` rather than a `Vec` of
48        /// pairs so construction cannot accidentally depend on
49        /// insertion order the way a hand-sorted `Vec` could if a
50        /// caller forgot to sort it.
51        children: BTreeMap<String, Node>,
52    },
53}
54
55/// Domain-separation tag for a branch, distinct from [`crate::log`]'s
56/// `0x00` (leaf) and `0x01` (interior binary node) so a hash from this
57/// tree can never be mistaken for one from that one.
58const BRANCH_TAG: u8 = 0x02;
59
60impl Node {
61    /// Build a leaf.
62    ///
63    /// # Example
64    ///
65    /// ```
66    /// use publet_algorithms::log::leaf_hash;
67    /// use publet_algorithms::tree::Node;
68    ///
69    /// // A leaf commits to its content exactly as a log leaf does.
70    /// assert_eq!(Node::leaf("fn main() {}").hash(), leaf_hash(b"fn main() {}"));
71    /// ```
72    #[must_use]
73    pub fn leaf(content: impl Into<Vec<u8>>) -> Self {
74        Self::Leaf {
75            content: content.into(),
76        }
77    }
78
79    /// Build a branch with no children yet.
80    ///
81    /// # Example
82    ///
83    /// ```
84    /// use publet_algorithms::tree::Node;
85    ///
86    /// let module = Node::branch("mod parser").with_child("parse", Node::leaf("fn parse() {}"));
87    /// assert!(module.is_branch());
88    /// ```
89    #[must_use]
90    pub fn branch(header: impl Into<Vec<u8>>) -> Self {
91        Self::Branch {
92            header: header.into(),
93            children: BTreeMap::new(),
94        }
95    }
96
97    /// Add or replace a named child. Returns `self` for chaining.
98    ///
99    /// # Example
100    ///
101    /// ```
102    /// use publet_algorithms::tree::Node;
103    ///
104    /// // Children are keyed by name, so the order they are added in does not matter.
105    /// let one = Node::branch("impl S")
106    ///     .with_child("a", Node::leaf("fn a() {}"))
107    ///     .with_child("b", Node::leaf("fn b() {}"));
108    /// let other = Node::branch("impl S")
109    ///     .with_child("b", Node::leaf("fn b() {}"))
110    ///     .with_child("a", Node::leaf("fn a() {}"));
111    /// assert_eq!(one.hash(), other.hash());
112    /// ```
113    #[must_use]
114    pub fn with_child(mut self, name: impl Into<String>, child: Self) -> Self {
115        if let Self::Branch { children, .. } = &mut self {
116            children.insert(name.into(), child);
117        }
118        self
119    }
120
121    /// Whether this is a branch (as opposed to a leaf).
122    ///
123    /// # Example
124    ///
125    /// ```
126    /// use publet_algorithms::tree::Node;
127    ///
128    /// assert!(Node::branch("mod m").is_branch());
129    /// assert!(!Node::leaf("const X: u8 = 1;").is_branch());
130    /// ```
131    #[must_use]
132    pub const fn is_branch(&self) -> bool {
133        matches!(self, Self::Branch { .. })
134    }
135
136    /// This node's children, if it is a branch.
137    ///
138    /// # Example
139    ///
140    /// ```
141    /// use publet_algorithms::tree::Node;
142    ///
143    /// let module = Node::branch("mod m").with_child("f", Node::leaf("fn f() {}"));
144    /// assert_eq!(module.children().map(|c| c.len()), Some(1));
145    /// assert_eq!(Node::leaf("fn f() {}").children(), None);
146    /// ```
147    #[must_use]
148    pub fn children(&self) -> Option<&BTreeMap<String, Node>> {
149        match self {
150            Self::Branch { children, .. } => Some(children),
151            Self::Leaf { .. } => None,
152        }
153    }
154
155    /// The commitment: for a leaf, the hash of its content; for a
156    /// branch, a hash of its header and every child's own `hash()`,
157    /// paired with its name and length-prefixed so no concatenation of
158    /// two different `(name, hash)` sequences can ever coincide.
159    ///
160    /// # Example
161    ///
162    /// ```
163    /// use publet_algorithms::tree::Node;
164    ///
165    /// let tree = |body: &str| {
166    ///     Node::branch("mod m").with_child("inner", Node::branch("impl S").with_child("f", Node::leaf(body)))
167    /// };
168    /// // A change to one deeply nested leaf changes the root's hash.
169    /// assert_ne!(tree("fn f() { 1 }").hash(), tree("fn f() { 2 }").hash());
170    /// ```
171    #[must_use]
172    pub fn hash(&self) -> Hash {
173        match self {
174            Self::Leaf { content } => leaf_hash(content),
175            Self::Branch { header, children } => {
176                let mut buf = vec![BRANCH_TAG];
177                buf.extend_from_slice(&(header.len() as u64).to_le_bytes());
178                buf.extend_from_slice(header);
179                // `children` is a BTreeMap, so this iterates in sorted
180                // key order already -- the same order regardless of
181                // insertion order, which is the whole point.
182                for (name, child) in children {
183                    let name_bytes = name.as_bytes();
184                    buf.extend_from_slice(&(name_bytes.len() as u64).to_le_bytes());
185                    buf.extend_from_slice(name_bytes);
186                    buf.extend_from_slice(&child.hash());
187                }
188                leaf_hash(&buf)
189            }
190        }
191    }
192
193    /// Find the node at a `/`-separated path of child names, if it
194    /// exists. `find("")` returns `self`.
195    ///
196    /// # Example
197    ///
198    /// ```
199    /// use publet_algorithms::tree::Node;
200    ///
201    /// let tree = Node::branch("mod m")
202    ///     .with_child("S", Node::branch("impl S").with_child("f", Node::leaf("fn f() {}")));
203    /// assert_eq!(tree.find("S/f"), Some(&Node::leaf("fn f() {}")));
204    /// assert_eq!(tree.find(""), Some(&tree));
205    /// assert_eq!(tree.find("S/g"), None);
206    /// ```
207    #[must_use]
208    pub fn find(&self, path: &str) -> Option<&Node> {
209        if path.is_empty() {
210            return Some(self);
211        }
212        let (head, rest) = path.split_once('/').unwrap_or((path, ""));
213        self.children()?.get(head)?.find(rest)
214    }
215
216    /// Every leaf's hash paired with its full `/`-joined path from this
217    /// node, in sorted path order.
218    ///
219    /// # Example
220    ///
221    /// ```
222    /// use publet_algorithms::log::leaf_hash;
223    /// use publet_algorithms::tree::Node;
224    ///
225    /// let tree = Node::branch("mod m")
226    ///     .with_child("b", Node::leaf("fn b() {}"))
227    ///     .with_child("a", Node::branch("impl A").with_child("f", Node::leaf("fn f() {}")));
228    /// assert_eq!(tree.leaves(), [
229    ///     ("a/f".to_string(), leaf_hash(b"fn f() {}")),
230    ///     ("b".to_string(), leaf_hash(b"fn b() {}")),
231    /// ]);
232    /// ```
233    #[must_use]
234    pub fn leaves(&self) -> Vec<(String, Hash)> {
235        let mut out = Vec::new();
236        self.collect_leaves(String::new(), &mut out);
237        out
238    }
239
240    fn collect_leaves(&self, prefix: String, out: &mut Vec<(String, Hash)>) {
241        match self {
242            Self::Leaf { .. } => out.push((prefix, self.hash())),
243            Self::Branch { children, .. } => {
244                for (name, child) in children {
245                    let path = if prefix.is_empty() {
246                        name.clone()
247                    } else {
248                        format!("{prefix}/{name}")
249                    };
250                    child.collect_leaves(path, out);
251                }
252            }
253        }
254    }
255}