microkelvin

Library for creating and searching through annotated merkle trees.

Built on the canonical serialization and FFI library.

Compound trait

/// A type that can recursively contain itself and leaves.
pub trait Compound<A>: Sized + Canon {
    /// The leaf type of the Compound collection
    type Leaf;

    /// Returns a reference to a possible child at specified offset
    fn child(&self, ofs: usize) -> Child<Self, A>
    where
        A: Annotation<Self::Leaf>;

    /// Returns a mutable reference to a possible child at specified offset
    fn child_mut(&mut self, ofs: usize) -> ChildMut<Self, A>
    where
        A: Annotation<Self::Leaf>;

The Compound trait defines a type as a collection type. This means that it can be searched and have branches constructed pointing to its elements.

Annotation/Combine trait

/// The trait defining an annotation type over a leaf
pub trait Annotation<Leaf>: Default + Clone {
    /// Creates an annotation from the leaf type
    fn from_leaf(leaf: &Leaf) -> Self;
}

/// Trait for defining how to combine Annotations
pub trait Combine<C, A>: Annotation<C::Leaf>
where
    C: Compound<A>,
{
    /// Combines multiple annotations
    fn combine(node: &C) -> Self;
}

The annotation and combine traits keep an automatically updated annotation of subtrees, for example total leaf amount (Cardinality in reference implementation), or which leaf compares the greatest (Max in reference implementation)

Branch walking

This is ane example of walking a recursive structure to yield a branch pointing at the nth leaf of the collection, if any.

It is automatically implemented on all types implementing Compound whose annotation can be borrowed as Cardinality. Giving this capability to any such structure.

impl<'a, C, A> Nth<'a, A> for C
where
    C: Compound<A> + Clone,
    A: Annotation<Self::Leaf> + Borrow<Cardinality>,
{
    fn nth(
        &'a self,
        mut remainder: u64,
    ) -> Result<Option<Branch<'a, Self, A>>, CanonError> {
        // Return the first that satisfies the walk
        Branch::<_, A>::walk(self, |w| nth(w, &mut remainder))
    }

    fn nth_mut(
        &'a mut self,
        mut remainder: u64,
    ) -> Result<Option<BranchMut<'a, Self, A>>, CanonError> {
        // Return the first mutable branch that satisfies the walk
        BranchMut::<_, A>::walk(self, |w| nth(w, &mut remainder))
    }
}

usage

Please check out the nstack implementation of a stack/vector type for a more advanced example.