Skip to main content

Node

Enum Node 

Source
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.

Fields

§content: Vec<u8>

The leaf’s own bytes.

§

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.

Fields

§header: Vec<u8>

The branch’s own identifying bytes, hashed but never expanded further – there is nothing under header itself to recurse into.

§children: BTreeMap<String, Node>

Children, keyed by name. A BTreeMap rather than a Vec of pairs so construction cannot accidentally depend on insertion order the way a hand-sorted Vec could if a caller forgot to sort it.

Implementations§

Source§

impl Node

Source

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() {}"));
Source

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());
Source

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());
Source

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());
Source

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);
Source

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());
Source

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);
Source

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() {}")),
]);

Trait Implementations§

Source§

impl Clone for Node

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl Debug for Node

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl Eq for Node

Source§

impl PartialEq for Node

Source§

fn eq(&self, other: &Self) -> bool

Equality operator ==. Read more
1.0.0 (const: unstable) · Source§

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=. Read more
Source§

impl StructuralPartialEq for Node

Auto Trait Implementations§

§

impl Freeze for Node

§

impl RefUnwindSafe for Node

§

impl Send for Node

§

impl Sync for Node

§

impl Unpin for Node

§

impl UnsafeUnpin for Node

§

impl UnwindSafe for Node

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> Same for T

Source§

type Output = T

Should always be Self
Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.