Source code for fleetmesh_core.storage.mst

"""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