MST.Diff (mst v0.1.0)

View Source

Computes the diff between two MST.Tree instances.

A diff captures:

  • Which MST nodes were created (present in b but not a)
  • Which MST nodes were deleted (present in a but not b)
  • The per-key record operations (creates, updates, and deletes)

Algorithm

Node sets (created_nodes / deleted_nodes) are computed by collecting all reachable node CIDs from each tree root with a DFS, then taking set differences. Equal CIDs short-circuit entire subtrees (no need to recurse into subtrees both trees share).

Record ops are computed by fully materialising both trees as sorted key/value lists and performing a linear sorted-merge comparison. This is straightforward and correct at the cost of O(n) memory; it is the right tradeoff given that the diff is typically used to inspect the full changeset anyway.

Example

{:ok, diff} = MST.Diff.compute(tree_a, tree_b)
# diff.record_ops is a sorted list of MST.Diff.Op structs

Summary

Types

diff_error()
t()

Functions

compute(tree1, tree2)

Computes the diff from tree_a to tree_b.

Types

diff_error()

@type diff_error() :: {:error, atom()}

t()

@type t() :: %MST.Diff{
  created_nodes: MapSet.t(DASL.CID.t()),
  deleted_nodes: MapSet.t(DASL.CID.t()),
  record_ops: [MST.Diff.Op.t()]
}

Functions

compute(tree1, tree2)

@spec compute(MST.Tree.t(), MST.Tree.t()) :: {:ok, t()} | diff_error()

Computes the diff from tree_a to tree_b.

Both trees must use stores that have their nodes populated (e.g. loaded from CAR files). Returns {:ok, diff} or an error if a node is missing.

Examples

iex> store = MST.Store.Memory.new()
iex> ta = MST.Tree.new(store)
iex> val = DASL.CID.compute("v")
iex> {:ok, tb} = MST.Tree.put(ta, "col/a", val)
iex> {:ok, diff} = MST.Diff.compute(ta, tb)
iex> length(diff.record_ops)
1
iex> hd(diff.record_ops).key
"col/a"