Module read 

Reading a node back out of a block.

Tree builds nodes and hands out their blocks. This is the other direction, and it is the one that has to be suspicious: a node that arrives in a CAR file or a firehose frame was encoded by somebody else, and the encoding has several ways to say something that is not a node.

Everything structural is checked here, so that a Node that exists is one a tree can be walked over:

• the map is exactly l and e, and each entry exactly p, k, v and t. A spare field is a different block with a different CID, so a node that carried one and was re-encoded would change its own name.
• a prefix length that reaches past the previous key is refused, and so is one that is shorter than it could be — if the byte after the shared part matches, the encoder should have shared it. Both spellings name the same key and only one of them is the block that key belongs in.
• keys strictly ascend. A node whose entries are out of order has no defined lookup.
• every key in one node sits at the same layer, which is what a layer is. A node mixing heights is a tree no other implementation would have built.

What is deliberately not checked is anything needing another block: that a subtree is one layer down, that it holds keys in the right range, that the links resolve at all. A node is one block, and those are claims about a tree — see Store, which checks them as it walks.

Structs

Parts

A node’s contents in the form the tree algorithms want them.

Enums

NodeError

Why a block is not a Merkle search tree node.

Functions

link_or_null 🔒

Reads a field that is a link or null, and refuses anything else.

read_entry 🔒

Reads one entry, appends it to node, and answers its full key.