Struct Tree 

pub struct Tree {
    pub(super) root: Cid,
    pub(super) layer: usize,
    pub(super) blocks: BTreeMap<Cid, Vec<u8>>,
    pub(super) nodes: BTreeMap<Cid, Node>,
}

A built Merkle search tree: a root CID and every block under it.

Built from a leaf set in one pass, then changed one key at a time by Tree::insert and Tree::remove, which leave it exactly the tree Tree::build makes from the new leaf set. The blocks are handed back rather than written anywhere, because what wants them differs — a CAR export wants all of them, a proof wants the ones on one key’s path — and a tree that also owned a block store would have to be told which.

Fields

root: Cid

layer: usize

The layer the root sits on: the height of the tallest key, or zero.

blocks: BTreeMap<Cid, Vec<u8>>

nodes: BTreeMap<Cid, Node>

The same nodes, still as nodes.

Kept alongside the encoded blocks rather than instead of them because Tree::path has to read a node to say which way to go, and this crate has no DAG-CBOR decoder to read one back out of its block. The duplication is bounded by the tree’s node count, which is a small fraction of its record count.

Implementations

impl Tree

pub fn insert(&mut self, key: &str, value: Cid) -> Rewritten

Points key at value, adding the key if the tree does not hold it.

The tree afterwards is the one Tree::build makes from the new leaf set, node for node. Setting a key to the value it already names changes nothing and answers an empty Rewritten.

pub fn remove(&mut self, key: &str) -> Rewritten

Takes key out of the tree, if the tree holds it.

The tree afterwards is the one Tree::build makes from the leaf set without the key. A key the tree does not hold changes nothing and answers an empty Rewritten.

fn apply(&mut self, staged: Staged) -> Rewritten

Writes an edit’s nodes into the tree and takes its removed ones out.

impl Tree

pub fn build(leaves: &BTreeMap<String, Cid>) -> Self

Builds the tree over a leaf set.

The keys are the repository’s, which atproto writes as <collection>/<rkey>, and the values are the CIDs of the records they name. A BTreeMap<String, _> is already in the order the tree needs: str compares bytewise, and bytewise over the keys is exactly the ordering a node’s entries are in.

An empty repository is not an absent tree. It is one node holding no entries and no left pointer, and it has a CID like any other, which is what an account’s first commit signs.

use std::collections::BTreeMap;
use didbot_data::{mst::Tree, Cid};

let empty = Tree::build(&BTreeMap::new());
assert_eq!(
    empty.root().to_string(),
    "bafyreie5737gdxlw5i64vzichcalba3z2v5n6icifvx5xytvske7mr3hpm"
);
assert_eq!(empty.blocks().len(), 1);

pub fn path(&self, key: &str) -> Path

The path through the tree to key, whether or not it is there.

This is what an inclusion proof is made of, and what makes it a proof rather than an export: the nodes on one root-to-key walk and nothing else. A repository of ten thousand records proves any one of them with a handful of blocks, and a verifier that is handed the whole repository instead has been given an export with a different name.

A key the tree does not hold gets the same walk with no value. That is the exclusion proof: the last node on it is the one the key would have to be in, and a verifier that reaches it and does not find the key has been shown the key is not in the tree at all.

pub fn keys(&self) -> Vec<String>

Every key in the tree, in the order the tree holds them.

Reconstructed from the nodes rather than remembered from the leaf set, so it says what the tree is rather than what it was built from. A node stores each key as a shared prefix length and a suffix, and the prefix is counted against the previous entry in that node, so the walk has to rebuild the keys node by node rather than across the whole tree.

fn walk_keys(&self, node: &Cid, found: &mut Vec<String>)

Appends every key under one node, in order.

pub fn covering_proof(&self, key: &str) -> BTreeMap<Cid, Vec<u8>>

The blocks a consumer needs to verify one key changing.

atproto calls this a covering proof, and it is what a firehose commit carries so that a subscriber can check an operation without holding the repository. It is more than Tree::path: adding or removing a key can split a node or merge two, so the nodes that move are the ones on the key’s own walk and on the walks to the keys either side of it. A proof of the key alone verifies the lookup and cannot reproduce the root the operation started from.

The neighbours are found by listing the keys, which is a walk of the whole tree. A caller that already keeps the keys in order finds them itself and calls Tree::covering_proof_between.

pub fn covering_proof_between( &self, key: &str, before: Option<&str>, after: Option<&str>, ) -> BTreeMap<Cid, Vec<u8>>

Tree::covering_proof, given the keys either side of key.

before and after are the nearest keys the tree holds below and above key, or None where there is none.

pub fn root(&self) -> &Cid

The CID a commit signs over.

pub fn blocks(&self) -> &BTreeMap<Cid, Vec<u8>>

Every node block in the tree, keyed by its CID.

pub fn nodes(&self) -> &BTreeMap<Cid, Node>

The nodes, still as nodes, keyed by CID.

pub fn len(&self) -> usize

How many nodes the tree has.

pub fn is_empty(&self) -> bool

Never true: a tree always has at least its root node.

Present because len without is_empty is a lint, and answering it honestly is better than suppressing the lint — an empty repository still has a root, which is the whole reason a first commit can be signed.

Trait Implementations

impl Clone for Tree

fn clone(&self) -> Tree

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Tree

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

Formats the value using the given formatter.