pub enum Node {
Leaf {
content: Vec<u8>,
},
Branch {
header: Vec<u8>,
children: BTreeMap<String, Node>,
},
}Expand description
One position in the tree: a leaf holding raw content, or a branch holding its own header bytes plus named children.
This enum is exhaustive on purpose, so a match on it needs no
wildcard arm. A third kind of node would change how trees hash, which
changes every root computed from one, so it could not arrive in a
compatible release anyway.
Variants§
Leaf
Content hashed directly – a function’s exact source text, say.
Branch
No content of its own beyond header (a signature line, a module
path – whatever names this branch without needing its children
to render it), plus a set of named children, each itself a
Node. Two branches with the same header and the same
(name, hash) pairs – regardless of child insertion order –
hash identically; that is what makes moving a method’s textual
position in a file a no-op for its parent’s hash.
Implementations§
Source§impl Node
impl Node
Sourcepub fn leaf(content: impl Into<Vec<u8>>) -> Self
pub fn leaf(content: impl Into<Vec<u8>>) -> Self
Build a leaf.
§Example
use publet_algorithms::log::leaf_hash;
use publet_algorithms::tree::Node;
// A leaf commits to its content exactly as a log leaf does.
assert_eq!(Node::leaf("fn main() {}").hash(), leaf_hash(b"fn main() {}"));Sourcepub fn branch(header: impl Into<Vec<u8>>) -> Self
pub fn branch(header: impl Into<Vec<u8>>) -> Self
Build a branch with no children yet.
§Example
use publet_algorithms::tree::Node;
let module = Node::branch("mod parser").with_child("parse", Node::leaf("fn parse() {}"));
assert!(module.is_branch());Sourcepub fn with_child(self, name: impl Into<String>, child: Self) -> Self
pub fn with_child(self, name: impl Into<String>, child: Self) -> Self
Add or replace a named child. Returns self for chaining.
§Example
use publet_algorithms::tree::Node;
// Children are keyed by name, so the order they are added in does not matter.
let one = Node::branch("impl S")
.with_child("a", Node::leaf("fn a() {}"))
.with_child("b", Node::leaf("fn b() {}"));
let other = Node::branch("impl S")
.with_child("b", Node::leaf("fn b() {}"))
.with_child("a", Node::leaf("fn a() {}"));
assert_eq!(one.hash(), other.hash());Sourcepub const fn is_branch(&self) -> bool
pub const fn is_branch(&self) -> bool
Whether this is a branch (as opposed to a leaf).
§Example
use publet_algorithms::tree::Node;
assert!(Node::branch("mod m").is_branch());
assert!(!Node::leaf("const X: u8 = 1;").is_branch());Sourcepub fn children(&self) -> Option<&BTreeMap<String, Node>>
pub fn children(&self) -> Option<&BTreeMap<String, Node>>
This node’s children, if it is a branch.
§Example
use publet_algorithms::tree::Node;
let module = Node::branch("mod m").with_child("f", Node::leaf("fn f() {}"));
assert_eq!(module.children().map(|c| c.len()), Some(1));
assert_eq!(Node::leaf("fn f() {}").children(), None);Sourcepub fn hash(&self) -> Hash
pub fn hash(&self) -> Hash
The commitment: for a leaf, the hash of its content; for a
branch, a hash of its header and every child’s own hash(),
paired with its name and length-prefixed so no concatenation of
two different (name, hash) sequences can ever coincide.
§Example
use publet_algorithms::tree::Node;
let tree = |body: &str| {
Node::branch("mod m").with_child("inner", Node::branch("impl S").with_child("f", Node::leaf(body)))
};
// A change to one deeply nested leaf changes the root's hash.
assert_ne!(tree("fn f() { 1 }").hash(), tree("fn f() { 2 }").hash());Sourcepub fn find(&self, path: &str) -> Option<&Node>
pub fn find(&self, path: &str) -> Option<&Node>
Find the node at a /-separated path of child names, if it
exists. find("") returns self.
§Example
use publet_algorithms::tree::Node;
let tree = Node::branch("mod m")
.with_child("S", Node::branch("impl S").with_child("f", Node::leaf("fn f() {}")));
assert_eq!(tree.find("S/f"), Some(&Node::leaf("fn f() {}")));
assert_eq!(tree.find(""), Some(&tree));
assert_eq!(tree.find("S/g"), None);Sourcepub fn leaves(&self) -> Vec<(String, Hash)>
pub fn leaves(&self) -> Vec<(String, Hash)>
Every leaf’s hash paired with its full /-joined path from this
node, in sorted path order.
§Example
use publet_algorithms::log::leaf_hash;
use publet_algorithms::tree::Node;
let tree = Node::branch("mod m")
.with_child("b", Node::leaf("fn b() {}"))
.with_child("a", Node::branch("impl A").with_child("f", Node::leaf("fn f() {}")));
assert_eq!(tree.leaves(), [
("a/f".to_string(), leaf_hash(b"fn f() {}")),
("b".to_string(), leaf_hash(b"fn b() {}")),
]);