"""Merkle Search Tree (MST) for ATProto repositories.
Standard library only. Implements:
- 16-fanout Merkle Search Tree with deterministic layer assignment
based on leading zero hex nibbles of SHA-256(key).
- Node DAG-CBOR serialization with common prefix compaction (`p`, `k`, `v`, `t`, `l`).
- Deterministic tree operations: put, get, delete, list, diff.
- Empty tree root CID `bafyreie5737gdxlw5i64vzichcalba3z2v5n6icifvx5xytvske7mr3hpm`.
"""
from __future__ import annotations
import hashlib
from typing import Any, Mapping, Optional, Sequence
from ..conformance.errors import FleetmeshError
from ..identity.cid import CIDLink
from ..wire.cbor import CBORError, dag_cbor_decode, dag_cbor_encode
__all__ = [
'MSTError',
'leading_zeros',
'TreeEntry',
'MSTNode',
'MST',
'EMPTY_MST_ROOT',
]
[docs]class MSTError(FleetmeshError):
"""Base error for MST operations."""
[docs]def leading_zeros(key: str) -> int:
"""Calculate the MST layer of a key by counting leading zeros in SHA-256 hex digest."""
h = hashlib.sha256(key.encode('utf-8')).hexdigest()
count = 0
for ch in h:
if ch == '0':
count += 1
else:
break
return count
[docs]class TreeEntry:
"""An entry within an MST node pointing to a record value and an optional right subtree."""
__slots__ = ('key', 'val', 'tree')
[docs] def __init__(self, key: str, val: CIDLink, tree: Optional[CIDLink] = None):
self.key = key
self.val = val
self.tree = tree
def __repr__(self) -> str:
return f"TreeEntry(key={self.key!r}, val={self.val!r}, tree={self.tree!r})"
def __eq__(self, other: Any) -> bool:
if not isinstance(other, TreeEntry):
return False
return self.key == other.key and self.val == other.val and self.tree == other.tree
[docs]class MSTNode:
"""An MST node holding a left subtree pointer and an ordered list of TreeEntries."""
__slots__ = ('left', 'entries')
[docs] def __init__(self, left: Optional[CIDLink] = None, entries: Optional[Sequence[TreeEntry]] = None):
self.left = left
self.entries = list(entries or [])
[docs] def to_cbor_dict(self) -> Mapping[str, Any]:
"""Convert node to DAG-CBOR dict with prefix compaction per ATProto spec."""
e_list = []
prev_key_bytes = b""
for entry in self.entries:
key_bytes = entry.key.encode('utf-8')
p = 0
max_p = min(len(prev_key_bytes), len(key_bytes))
while p < max_p and prev_key_bytes[p] == key_bytes[p]:
p += 1
k_suffix = key_bytes[p:]
ed = {
'p': p,
'k': k_suffix,
'v': entry.val,
't': entry.tree,
}
e_list.append(ed)
prev_key_bytes = key_bytes
out = {'l': self.left, 'e': e_list}
return out
[docs] def to_cbor(self) -> tuple[CIDLink, bytes]:
"""Serialize node to canonical DAG-CBOR bytes and compute its CID."""
raw = dag_cbor_encode(self.to_cbor_dict())
cid = CIDLink.from_dag_cbor(raw)
return cid, raw
[docs] @classmethod
def from_cbor(cls, data: bytes) -> MSTNode:
"""Deserialize an MST node from DAG-CBOR bytes."""
try:
doc = dag_cbor_decode(data)
except CBORError as e:
raise MSTError(f"invalid MST node CBOR: {e}") from e
if not isinstance(doc, dict):
raise MSTError("MST node CBOR must be a map")
left = doc.get('l')
if left is not None and not isinstance(left, CIDLink):
try:
left = CIDLink.from_str(str(left))
except ValueError as e:
raise MSTError(f"invalid MST left CID: {e}") from e
raw_entries = doc.get('e', [])
if not isinstance(raw_entries, list):
raise MSTError("MST node 'e' field must be a list")
entries: list[TreeEntry] = []
prev_key_bytes = b""
for ed in raw_entries:
if not isinstance(ed, Mapping):
raise MSTError("MST tree entry must be a map")
p = ed.get('p', 0)
if isinstance(p, bool) or not isinstance(p, int) or p < 0 or p > len(prev_key_bytes):
raise MSTError(f"invalid prefix length p={p!r} in MST entry")
k_suffix = ed.get('k', b"")
if isinstance(k_suffix, str):
k_suffix = k_suffix.encode('utf-8')
elif not isinstance(k_suffix, (bytes, bytearray)):
raise MSTError("MST entry key suffix 'k' must be bytes or str")
full_key_bytes = prev_key_bytes[:p] + bytes(k_suffix)
prev_key_bytes = full_key_bytes
try:
key_str = full_key_bytes.decode('utf-8')
except UnicodeDecodeError as e:
raise MSTError(f"MST entry key is not valid UTF-8: {e}") from e
val = ed.get('v')
if not isinstance(val, CIDLink):
try:
val = CIDLink.from_str(str(val))
except ValueError as e:
raise MSTError(f"invalid MST entry value CID: {e}") from e
tree = ed.get('t')
if tree is not None and not isinstance(tree, CIDLink):
try:
tree = CIDLink.from_str(str(tree))
except ValueError as e:
raise MSTError(f"invalid MST entry subtree CID: {e}") from e
entries.append(TreeEntry(key_str, val, tree))
return cls(left=left, entries=entries)
# Precompute standard empty MST root
EMPTY_MST_NODE = MSTNode(left=None, entries=[])
EMPTY_MST_ROOT, _EMPTY_MST_BYTES = EMPTY_MST_NODE.to_cbor()
[docs]class MST:
"""Merkle Search Tree backed by an in-memory or pluggable blockstore."""
[docs] def __init__(
self,
root_cid: Optional[CIDLink] = None,
blocks: Optional[dict[CIDLink, bytes]] = None,
blockstore: Optional[dict[CIDLink, bytes]] = None,
):
target_blocks = blocks if blocks is not None else blockstore
self._blocks = target_blocks if target_blocks is not None else {}
if root_cid is None:
self._root_cid = EMPTY_MST_ROOT
self._blocks[EMPTY_MST_ROOT] = _EMPTY_MST_BYTES
else:
self._root_cid = root_cid
if self._root_cid == EMPTY_MST_ROOT and EMPTY_MST_ROOT not in self._blocks:
self._blocks[EMPTY_MST_ROOT] = _EMPTY_MST_BYTES
@property
def root_cid(self) -> CIDLink:
return self._root_cid
@property
def blocks(self) -> dict[CIDLink, bytes]:
return self._blocks
def _load_node(self, cid: CIDLink) -> MSTNode:
if cid not in self._blocks:
raise MSTError(f"missing block for MST node: {cid}")
return MSTNode.from_cbor(self._blocks[cid])
def _save_node(self, node: MSTNode) -> CIDLink:
cid, data = node.to_cbor()
self._blocks[cid] = data
return cid
def _node_layer(self, node: MSTNode) -> int:
"""Infer the layer of a non-empty node from its first entry."""
if not node.entries:
return 0
return leading_zeros(node.entries[0].key)
[docs] def get(self, key: str) -> Optional[CIDLink]:
"""Retrieve the CIDLink value stored at key, or None if not found."""
curr_cid: Optional[CIDLink] = self._root_cid
while curr_cid is not None:
node = self._load_node(curr_cid)
# Find in node.entries
found = False
for i, entry in enumerate(node.entries):
if key == entry.key:
return entry.val
if key < entry.key:
# Belongs in subtree before this entry
curr_cid = node.left if i == 0 else node.entries[i - 1].tree
found = True
break
if not found:
# Greater than all entries in this node
curr_cid = node.entries[-1].tree if node.entries else None
return None
[docs] def put(self, key: str, val: CIDLink) -> CIDLink:
"""Insert or update a key/value mapping and return the new root CID."""
key_layer = leading_zeros(key)
self._root_cid = self._put_recursive(self._root_cid, key, val, key_layer)
return self._root_cid
def _put_recursive(
self,
curr_cid: Optional[CIDLink],
key: str,
val: CIDLink,
key_layer: int,
) -> CIDLink:
if curr_cid is None or curr_cid == EMPTY_MST_ROOT:
# Create a single-entry node at key_layer
new_node = MSTNode(left=None, entries=[TreeEntry(key, val, tree=None)])
return self._save_node(new_node)
node = self._load_node(curr_cid)
node_layer = self._node_layer(node)
if key_layer > node_layer:
# Key belongs above current node: split current tree by key
left_cid, right_cid = self._split_tree(curr_cid, key)
new_node = MSTNode(
left=left_cid,
entries=[TreeEntry(key, val, tree=right_cid)],
)
return self._save_node(new_node)
if key_layer == node_layer:
# Key belongs in this node
new_entries: list[TreeEntry] = []
inserted = False
for i, entry in enumerate(node.entries):
if entry.key == key:
# Update existing key's value, preserving subtree
new_entries.append(TreeEntry(key, val, entry.tree))
new_entries.extend(node.entries[i + 1:])
inserted = True
break
elif key < entry.key:
# Insert before entry i; split the subtree between entry[i-1] and entry[i]
sub_cid = node.left if i == 0 else node.entries[i - 1].tree
sub_l, sub_r = self._split_tree(sub_cid, key) if sub_cid else (None, None)
if i > 0:
new_entries[-1].tree = sub_l
else:
node.left = sub_l
new_entries.append(TreeEntry(key, val, sub_r))
new_entries.extend(node.entries[i:])
inserted = True
break
else:
new_entries.append(TreeEntry(entry.key, entry.val, entry.tree))
if not inserted:
# Key is greater than all existing entries
sub_cid = node.entries[-1].tree if node.entries else None
sub_l, sub_r = self._split_tree(sub_cid, key) if sub_cid else (None, None)
if new_entries:
new_entries[-1].tree = sub_l
else:
node.left = sub_l
new_entries.append(TreeEntry(key, val, sub_r))
updated_node = MSTNode(left=node.left, entries=new_entries)
return self._save_node(updated_node)
# key_layer < node_layer: recurse into the child subtree
for i, entry in enumerate(node.entries):
if key < entry.key:
child_cid = node.left if i == 0 else node.entries[i - 1].tree
new_child = self._put_recursive(child_cid, key, val, key_layer)
if i == 0:
node.left = new_child
else:
node.entries[i - 1].tree = new_child
return self._save_node(node)
# Greater than all entries
child_cid = node.entries[-1].tree
new_child = self._put_recursive(child_cid, key, val, key_layer)
node.entries[-1].tree = new_child
return self._save_node(node)
[docs] def delete(self, key: str) -> CIDLink:
"""Remove a key and return the new root CID."""
self._root_cid = self._delete_recursive(self._root_cid, key)
return self._root_cid
def _delete_recursive(self, curr_cid: Optional[CIDLink], key: str) -> CIDLink:
if curr_cid is None or curr_cid == EMPTY_MST_ROOT:
return curr_cid or EMPTY_MST_ROOT
node = self._load_node(curr_cid)
# Check if key is directly in this node
for i, entry in enumerate(node.entries):
if entry.key == key:
# Found key: remove entry and merge subtrees (left of key and right of key)
left_sub = node.left if i == 0 else node.entries[i - 1].tree
right_sub = entry.tree
merged_sub = self._merge_trees(left_sub, right_sub)
if i == 0:
node.left = merged_sub
else:
node.entries[i - 1].tree = merged_sub
node.entries.pop(i)
if not node.entries:
# If this node has no entries left, return its merged subtree
return node.left or EMPTY_MST_ROOT
return self._save_node(node)
if key < entry.key:
# Recurse into left child
child_cid = node.left if i == 0 else node.entries[i - 1].tree
new_child = self._delete_recursive(child_cid, key)
if i == 0:
node.left = new_child if new_child != EMPTY_MST_ROOT else None
else:
node.entries[i - 1].tree = new_child if new_child != EMPTY_MST_ROOT else None
return self._save_node(node)
# Greater than all entries: recurse into last subtree
if node.entries:
child_cid = node.entries[-1].tree
new_child = self._delete_recursive(child_cid, key)
node.entries[-1].tree = new_child if new_child != EMPTY_MST_ROOT else None
return self._save_node(node)
return curr_cid
def _split_tree(
self,
tree_cid: Optional[CIDLink],
pivot: str,
) -> tuple[Optional[CIDLink], Optional[CIDLink]]:
"""Split tree rooted at tree_cid into (keys < pivot, keys > pivot)."""
if tree_cid is None or tree_cid == EMPTY_MST_ROOT:
return None, None
node = self._load_node(tree_cid)
left_entries: list[TreeEntry] = []
right_entries: list[TreeEntry] = []
left_left = node.left
right_left: Optional[CIDLink] = None
split_done = False
for i, entry in enumerate(node.entries):
if entry.key < pivot:
left_entries.append(TreeEntry(entry.key, entry.val, entry.tree))
elif entry.key > pivot:
if not split_done:
# Split the subtree immediately preceding this entry
sub = node.left if i == 0 else node.entries[i - 1].tree
sub_l, sub_r = self._split_tree(sub, pivot)
if left_entries:
left_entries[-1].tree = sub_l
else:
left_left = sub_l
right_left = sub_r
split_done = True
right_entries.append(TreeEntry(entry.key, entry.val, entry.tree))
else:
# entry.key == pivot
sub = node.left if i == 0 else node.entries[i - 1].tree
sub_l, _ = self._split_tree(sub, pivot)
if left_entries:
left_entries[-1].tree = sub_l
else:
left_left = sub_l
right_left = entry.tree
split_done = True
if not split_done:
# Pivot is greater than all entries in this node
sub = node.entries[-1].tree if node.entries else None
sub_l, sub_r = self._split_tree(sub, pivot)
if left_entries:
left_entries[-1].tree = sub_l
else:
left_left = sub_l
right_left = sub_r
left_node_cid: Optional[CIDLink] = None
if left_entries or left_left is not None:
left_node_cid = self._save_node(MSTNode(left=left_left, entries=left_entries))
right_node_cid: Optional[CIDLink] = None
if right_entries or right_left is not None:
right_node_cid = self._save_node(MSTNode(left=right_left, entries=right_entries))
return left_node_cid, right_node_cid
def _merge_trees(
self,
left_cid: Optional[CIDLink],
right_cid: Optional[CIDLink],
) -> Optional[CIDLink]:
"""Merge two disjoint trees where all keys in left_cid < all keys in right_cid."""
if left_cid is None:
return right_cid
if right_cid is None:
return left_cid
left_node = self._load_node(left_cid)
right_node = self._load_node(right_cid)
l_layer = self._node_layer(left_node)
r_layer = self._node_layer(right_node)
if l_layer > r_layer:
# Attach right tree into the rightmost subtree of left_node
new_tree = self._merge_trees(left_node.entries[-1].tree, right_cid)
left_node.entries[-1].tree = new_tree
return self._save_node(left_node)
elif r_layer > l_layer:
# Attach left tree into the leftmost subtree of right_node
new_left = self._merge_trees(left_cid, right_node.left)
right_node.left = new_left
return self._save_node(right_node)
else:
# Same layer: merge their rightmost / leftmost gap and combine entries
middle = self._merge_trees(left_node.entries[-1].tree, right_node.left)
combined_entries = list(left_node.entries)
combined_entries[-1].tree = middle
combined_entries.extend(right_node.entries)
merged = MSTNode(left=left_node.left, entries=combined_entries)
return self._save_node(merged)
[docs] def items(self, prefix: str = "") -> list[tuple[str, CIDLink]]:
"""Return all (key, val) pairs in alphabetical order, optionally filtered by prefix."""
out: list[tuple[str, CIDLink]] = []
def walk(cid: Optional[CIDLink]) -> None:
if cid is None or cid == EMPTY_MST_ROOT:
return
node = self._load_node(cid)
walk(node.left)
for entry in node.entries:
if not prefix or entry.key.startswith(prefix):
out.append((entry.key, entry.val))
walk(entry.tree)
walk(self._root_cid)
return out
[docs] def keys(self, prefix: str = "") -> list[str]:
return [k for k, _ in self.items(prefix=prefix)]
[docs] def diff(
self,
other: MST,
) -> tuple[list[tuple[str, CIDLink]], list[tuple[str, CIDLink]], list[str]]:
"""Compute difference between this MST and another MST.
Returns (created, updated, deleted):
- created: keys in other not in self [(key, val), ...]
- updated: keys in both with different vals [(key, val), ...]
- deleted: keys in self not in other [key, ...]
"""
self_items = dict(self.items())
other_items = dict(other.items())
created = [(k, v) for k, v in other_items.items() if k not in self_items]
updated = [(k, v) for k, v in other_items.items() if k in self_items and self_items[k] != v]
deleted = [k for k in self_items if k not in other_items]
return created, updated, deleted