mst

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