# elixir-mst

An Elixir implementation of [AT Protocol-flavoured Merkle Search Trees (MST)][spec].

## Overview

A Merkle Search Tree is a content-addressed, ordered key/value structure.
Every unique set of key/value pairs produces a unique root CID, making it
suitable for Merkle proofs, efficient diffs, and repository synchronisation.
This library implements the AT Protocol flavour: nodes are encoded as
DRISL, keys are arbitrary byte strings, values are `DASL.CID` links, and
tree depth is derived from the SHA-256 hash of each key.

[spec]: https://atproto.com/specs/repository#mst-structure

## Installation

Get elixir-mst from [hex.pm](https://hex.pm) by adding it to your `mix.exs`:

```elixir
# mix.exs
def deps do
  [
    {:mst, "~> 0.1"}
  ]
end
```

Documentation can be found on HexDocs at https://hexdocs.pm/mst.

## Quick start

```elixir
# Build a tree
tree = MST.new()

val = DASL.CID.compute("my record data")
{:ok, tree} = MST.put(tree, "app.bsky.feed.post/3jqfcqzm3ft2j", val)
{:ok, ^val} = MST.get(tree, "app.bsky.feed.post/3jqfcqzm3ft2j")

# Mutate (persistent — the original tree is unchanged)
{:ok, tree2} = MST.put(tree, "app.bsky.feed.post/3jqfcqzm3fz2j", val)
{:ok, tree2} = MST.delete(tree2, "app.bsky.feed.post/3jqfcqzm3ft2j")

# Enumerate in sorted order
{:ok, pairs} = MST.to_list(tree2)
# => [{"app.bsky.feed.post/3jqfcqzm3fz2j", val}]

# Or stream lazily
tree2 |> MST.stream() |> Enum.each(fn {key, cid} -> ... end)
```

## CAR import / export

```elixir
# Export to a CARv1 binary
{:ok, car_bytes} = MST.to_car(tree)
File.write!("repo.car", car_bytes)

# Import from a CARv1 binary
{:ok, tree} = MST.from_car(File.read!("repo.car"))
```

## Diffing two trees

```elixir
{:ok, diff} = MST.diff(tree_a, tree_b)

diff.created_nodes  # MapSet of node CIDs added in tree_b
diff.deleted_nodes  # MapSet of node CIDs removed from tree_a

for %MST.Diff.Op{key: key, old_value: old, new_value: new} <- diff.record_ops do
  case {old, new} do
    {nil, cid} -> IO.puts("create  #{key} → #{cid}")
    {cid, nil} -> IO.puts("delete  #{key} (was #{cid})")
    {old, new} -> IO.puts("update  #{key}: #{old} → #{new}")
  end
end
```

---

This project is licensed under the [MIT License](./LICENSE)