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}