Struct Store

Source

pub struct Store {
    nodes: BTreeMap<Cid, Node>,
    blocks: BTreeMap<Cid, Vec<u8>>,
}

Expand description

Blocks that are claimed to be a Merkle search tree.

Nodes are held decoded, because every operation reads them and decoding is where the structural checks live. The blocks are held too: a proof is answered as a set of CIDs, and whatever sends it needs the bytes.

Fields§

§nodes: BTreeMap<Cid, Node>

Every node, by the CID it was filed under.

§blocks: BTreeMap<Cid, Vec<u8>>

The blocks those nodes were decoded from.

Implementations§

Source §

impl Store

Source

pub fn load( blocks: impl IntoIterator<Item = (Cid, Vec<u8>)>, ) -> Result<Self, (Box<Cid>, NodeError)>

Builds a store over blocks that are all claimed to be nodes.

Every block is decoded here rather than lazily, so a malformed node is a failure to load a tree rather than a failure part-way through answering a query about it. A CAR file that also holds records is not what this takes; see Store::insert for adding them one at a time.

Source

pub fn insert(&mut self, cid: &Cid, block: Vec<u8>) -> Result<(), NodeError>

Decodes one block and files it under cid.

The CID is taken on trust: whether the block hashes to it is a question about a container — see didbot_repo::car::read, which checks it — and re-hashing here would make every store pay for it twice.

Source

pub fn put(&mut self, node: Node) -> Cid

Files a node that was built rather than decoded.

Used by anything that writes a tree into a store — a rewrite, a proof being replayed — where the node is already in hand and encoding it only to decode it again would prove nothing.

Source

pub fn node(&self, cid: &Cid) -> Result<&Node, StoreError>

The node under cid, or the error naming what is missing.

Source

pub fn block(&self, cid: &Cid) -> Option<&[u8]>

The block under cid, if the store holds it.

Source

pub fn len(&self) -> usize

How many nodes the store holds.

Source

pub fn is_empty(&self) -> bool

Whether the store holds nothing at all.

Source

pub fn root_layer(&self, root: &Cid) -> Result<usize, StoreError>

Which layer a root is on, which is the one thing a walk needs before it starts.

Source

pub fn nodes_under(&self, root: &Cid) -> Result<BTreeSet<Cid>, StoreError>

Every node reachable from root, itself included.

This is what a tree is, as a set of blocks, and the two directions of diff are the two differences of these sets. Subtree layers are checked on the way down: a node claiming the wrong one is a tree that two implementations would walk differently.

Source

pub fn leaves(&self, root: &Cid) -> Result<BTreeMap<String, Cid>, StoreError>

Every path in the tree and the record it names, in key order.

Source

fn collect( &self, cid: &Cid, layer: usize, leaves: &mut BTreeMap<String, Cid>, ) -> Result<(), StoreError>

Appends every path under one node.

The descent is an explicit stack, as Store::nodes_under’s is, and for the same reason: the depth of a tree that arrived from elsewhere is whatever its blocks say. A chain of empty nodes is a few bytes per link and is walked clean, so recursing once per link would let a small pile of blocks end the process.

Source

fn check_layer( &self, cid: &Cid, node: &Node, expected: usize, ) -> Result<(), StoreError>

Refuses a subtree that is not on the layer its parent puts it on.

An empty intermediate has no layer of its own and is skipped: it exists precisely to carry a pointer down a layer nothing sits on.

Source

pub fn find(&self, root: &Cid, path: &str) -> Result<Found, StoreError>

Walks to one path, and hands back the walk as well as the answer.

The walk is the proof: a verifier holding these blocks and the root CID can repeat it, and reach the same answer or find that the blocks do not hash to what they were named. That is true of a path that is not in the tree as well — the walk ends where the path would have to be, and its absence there is its absence everywhere.

The descent stops as soon as it is below the path’s own layer; see the module documentation for why that is not merely an optimisation.