Module store 

A tree somebody else built: nodes by CID, and the walks over them.

Tree is this crate’s own tree — built from a whole leaf set, immutable, holding its own blocks. A Store is the opposite situation: a pile of blocks that arrived from elsewhere, one of which is claimed to be a root. Nothing about it is trusted, so every walk here can fail — a link may name a block that is not in the pile, and a subtree may claim a layer it is not on.

Three things are built on the walks:

• Store::leaves — what the tree says the repository holds.
• Store::find — the walk to one path, which is an inclusion proof when the path is there and an exclusion proof when it is not.
• diff — what changed between two roots, as the nodes that came and went, the records that came and went, and the blocks that prove it.

Why the walk stops early

Store::find gives up as soon as it is below the layer the path’s own height puts it on. A path can only ever be an entry at that one layer, so a walk that continued would be reading blocks that cannot hold the answer — and an exclusion proof made of them would be larger than it needs to be while proving exactly the same thing. This is the rule that decides how big proof_nodes is in the Merkle search tree conformance vectors, and getting it wrong is not a wrong answer, only a wasteful one.

Structs

Diff

What changed between two roots.

Found

What a walk to one path found, and what proves it.

RecordOp

One record that changed between two trees.

Store

Blocks that are claimed to be a Merkle search tree.

Enums

StoreError

Why a tree could not be walked.

Functions

diff

Diffs two trees held in one store.