defmodule MST do @moduledoc """ AT Protocol-flavoured Merkle Search Tree (MST) for Elixir. An MST is a content-addressed, deterministic key/value tree where keys are byte arrays and values are `DASL.CID` links. The tree structure is fully determined by the current set of key/value pairs — equal content always produces the same root CID, making it suitable for Merkle proofs and efficient diffs. This library implements the AT Protocol MST specification but is designed to be generic: it makes no assumptions about repository structure, commit objects, or AT-URI paths. ## Quick start store = MST.Store.Memory.new() tree = MST.new(store) val = DASL.CID.compute("my record") {:ok, tree} = MST.put(tree, "collection/key", val) {:ok, ^val} = MST.get(tree, "collection/key") {:ok, tree} = MST.delete(tree, "collection/key") ## Loading from a CAR file {:ok, tree} = MST.from_car(File.read!("repo.car")) {:ok, binary} = MST.to_car(tree) ## Diffing two trees {:ok, diff} = MST.diff(tree_a, tree_b) # diff.record_ops — sorted list of MST.Diff.Op structs ## Key depth The MST height of a key is derived by SHA-256 hashing it and counting leading zero bits divided by 2 (floor), giving a fanout of 4. 0 = MST.key_height("2653ae71") 1 = MST.key_height("blue") Spec: https://atproto.com/specs/repository#mst-structure """ alias MST.{CAR, Diff, Store, Tree} alias DASL.CID # --------------------------------------------------------------------------- # Construction # --------------------------------------------------------------------------- @doc """ Returns a new empty tree backed by an `MST.Store.Memory`. Pass an explicit store to use a different backend: tree = MST.new(MST.Store.Memory.new()) ## Examples iex> tree = MST.new() iex> tree.root nil """ @spec new() :: Tree.t() def new, do: Tree.new(Store.Memory.new()) @doc """ Returns a new empty tree backed by the given store. ## Examples iex> tree = MST.new(MST.Store.Memory.new()) iex> tree.root nil """ @spec new(Store.t()) :: Tree.t() def new(store), do: Tree.new(store) # --------------------------------------------------------------------------- # Lookup / mutation # --------------------------------------------------------------------------- @doc """ Looks up `key` in the tree. ## Examples iex> tree = MST.new() iex> MST.get(tree, "col/k") {:error, :not_found} """ @spec get(Tree.t(), binary()) :: {:ok, CID.t()} | {:error, :not_found} | {:error, atom()} defdelegate get(tree, key), to: Tree @doc """ Inserts or updates `key` → `value`. Returns `{:ok, new_tree}`. ## Examples iex> tree = MST.new() iex> val = DASL.CID.compute("data") iex> {:ok, tree} = MST.put(tree, "col/k", val) iex> MST.get(tree, "col/k") {:ok, val} """ @spec put(Tree.t(), binary(), CID.t()) :: {:ok, Tree.t()} | {:error, atom()} defdelegate put(tree, key, value), to: Tree @doc """ Removes `key` from the tree. Returns `{:ok, new_tree}` or `{:error, :not_found}`. ## Examples iex> tree = MST.new() iex> val = DASL.CID.compute("data") iex> {:ok, tree} = MST.put(tree, "col/k", val) iex> {:ok, tree} = MST.delete(tree, "col/k") iex> MST.get(tree, "col/k") {:error, :not_found} """ @spec delete(Tree.t(), binary()) :: {:ok, Tree.t()} | {:error, :not_found | atom()} defdelegate delete(tree, key), to: Tree @doc """ Returns all key-value pairs in sorted order. """ @spec to_list(Tree.t()) :: {:ok, [{binary(), CID.t()}]} | {:error, atom()} defdelegate to_list(tree), to: Tree @doc """ Returns a lazy stream of `{key, value_cid}` pairs in sorted order. """ @spec stream(Tree.t()) :: Enumerable.t() defdelegate stream(tree), to: Tree @doc """ Returns the number of key-value pairs in the tree. """ @spec length(Tree.t()) :: {:ok, non_neg_integer()} | {:error, atom()} defdelegate length(tree), to: Tree # --------------------------------------------------------------------------- # CAR I/O # --------------------------------------------------------------------------- @doc """ Loads an MST from a CAR-encoded binary or an already-decoded `DASL.CAR` struct. When given a binary, it is decoded via `DASL.CAR.decode/2` first. When given a `%DASL.CAR{}` struct the decoding step is skipped entirely, which avoids a redundant encode/decode cycle when you already hold the struct in memory. Accepts the same options as `DASL.CAR.decode/2` (`verify: boolean`) when called with a binary; options are ignored for the struct variant. ## Examples iex> tree = MST.new() iex> val = DASL.CID.compute("x") iex> {:ok, tree} = MST.put(tree, "col/a", val) iex> {:ok, bin} = MST.to_car(tree) iex> {:ok, tree2} = MST.from_car(bin) iex> MST.get(tree2, "col/a") {:ok, val} iex> tree = MST.new() iex> val = DASL.CID.compute("x") iex> {:ok, tree} = MST.put(tree, "col/a", val) iex> {:ok, bin} = MST.to_car(tree) iex> {:ok, car} = DASL.CAR.decode(bin) iex> {:ok, tree2} = MST.from_car(car) iex> MST.get(tree2, "col/a") {:ok, val} """ @spec from_car(binary() | DASL.CAR.t(), keyword()) :: {:ok, Tree.t()} | {:error, atom()} def from_car(input, opts \\ []) def from_car(%DASL.CAR{} = car, _opts), do: CAR.from_car(car) def from_car(binary, opts) when is_binary(binary), do: CAR.from_binary(binary, opts) @doc """ Serialises an `MST.Tree` to a CAR-encoded binary. """ @spec to_car(Tree.t(), keyword()) :: {:ok, binary()} | {:error, atom()} defdelegate to_car(tree, opts \\ []), to: CAR, as: :to_binary # --------------------------------------------------------------------------- # Diff # --------------------------------------------------------------------------- @doc """ Computes the diff from `tree_a` to `tree_b`. Returns an `MST.Diff` with `created_nodes`, `deleted_nodes`, and `record_ops` sorted by key. ## Examples iex> tree_a = MST.new() iex> val = DASL.CID.compute("v") iex> {:ok, tree_b} = MST.put(tree_a, "col/a", val) iex> {:ok, diff} = MST.diff(tree_a, tree_b) iex> length(diff.record_ops) 1 """ @spec diff(Tree.t(), Tree.t()) :: {:ok, Diff.t()} | {:error, atom()} defdelegate diff(tree_a, tree_b), to: Diff, as: :compute # --------------------------------------------------------------------------- # Utilities # --------------------------------------------------------------------------- @doc """ Returns the MST depth for a key. SHA-256 hashes `key` and counts leading zero bits divided by 2 (floor). ## Examples iex> MST.key_height("2653ae71") 0 iex> MST.key_height("blue") 1 """ @spec key_height(binary()) :: non_neg_integer() defdelegate key_height(key), to: MST.Height, as: :for_key end