MST.Node (mst v0.1.0)

Wire-format representation of a single MST node, plus encode/decode.

An MST node holds an optional left subtree CID (left) and an ordered list of MST.Node.Entry values, each carrying a key suffix, a value CID, and an optional right subtree CID. This maps exactly to the AT Protocol node schema:

{ l: CID | null, e: [ { p, k, v, t } ] }

Keys inside a node are prefix-compressed: each entry's key_suffix is the portion of the full key that follows the bytes it shares with the previous entry's full key. The first entry always has prefix_len: 0 and carries its full key in key_suffix. Prefix compression is mandatory — the serialised form must be deterministic across implementations.

Spec: https://atproto.com/specs/repository#mst-structure

Summary

Types

decode_error()

encode_error()

t()

Functions

cid(node)

Computes the :drisl-codec CID for this node.

compress_entries(triples)

Compresses a list of {full_key, value_cid, right_cid | nil} tuples into a list of MST.Node.Entry structs using the key prefix-compression scheme.

decode(bytes)

Decodes DRISL CBOR bytes into an MST.Node.

empty()

Returns an empty MST node — the only valid representation of an empty tree.

encode(node)

Encodes an MST.Node to DRISL CBOR bytes.

keys(node)

Reconstructs the full keys for all entries in the node.

Types

decode_error()

@type decode_error() :: {:error, :decode, atom()}

encode_error()

@type encode_error() :: {:error, :encode, atom()}

t()

@type t() :: %MST.Node{entries: [MST.Node.Entry.t()], left: DASL.CID.t() | nil}

Functions

cid(node)

@spec cid(t()) :: {:ok, DASL.CID.t()} | encode_error()

Computes the :drisl-codec CID for this node.

Encodes the node to DRISL CBOR bytes and hashes them. Returns an error tuple if encoding fails.

Examples

iex> {:ok, cid} = MST.Node.cid(MST.Node.empty())
iex> cid.codec
:drisl

compress_entries(triples)

@spec compress_entries([{binary(), DASL.CID.t(), DASL.CID.t() | nil}]) :: [
  MST.Node.Entry.t()
]

Compresses a list of {full_key, value_cid, right_cid | nil} tuples into a list of MST.Node.Entry structs using the key prefix-compression scheme.

The first entry always has prefix_len: 0. Each subsequent entry computes how many leading bytes it shares with the previous full key.

Examples

iex> cid = DASL.CID.compute("x")
iex> entries = MST.Node.compress_entries([{"abc/def", cid, nil}, {"abc/ghi", cid, nil}])
iex> hd(tl(entries)).prefix_len
4

decode(bytes)

@spec decode(binary()) :: {:ok, t()} | decode_error()

Decodes DRISL CBOR bytes into an MST.Node.

Examples

iex> {:ok, bytes} = MST.Node.encode(MST.Node.empty())
iex> {:ok, node} = MST.Node.decode(bytes)
iex> node.entries
[]
iex> node.left
nil

empty()

@spec empty() :: t()

Returns an empty MST node — the only valid representation of an empty tree.

Examples

iex> MST.Node.empty()
%MST.Node{left: nil, entries: []}

encode(node)

@spec encode(t()) :: {:ok, binary()} | encode_error()

Encodes an MST.Node to DRISL CBOR bytes.

nil subtree links are serialised as explicit CBOR null — this is mandatory for cross-implementation CID compatibility: skipping a key vs. writing null produces different bytes and therefore a different CID.

Examples

iex> {:ok, bytes} = MST.Node.encode(MST.Node.empty())
iex> is_binary(bytes)
true

keys(node)

@spec keys(t()) :: [binary()]

Reconstructs the full keys for all entries in the node.

Each entry stores only the suffix of its key relative to the previous entry. This function walks the entry list and accumulates the full key for each.

Examples

iex> cid = DASL.CID.compute("a")
iex> entries = [
...>   %MST.Node.Entry{prefix_len: 0, key_suffix: "foo/bar", value: cid, right: nil},
...>   %MST.Node.Entry{prefix_len: 4, key_suffix: "baz", value: cid, right: nil},
...> ]
iex> MST.Node.keys(%MST.Node{left: nil, entries: entries})
["foo/bar", "foo/baz"]