atmst.mst package

Submodules

atmst.mst.diff module

class atmst.mst.diff.DeltaType(value, names=None, *, module=None, qualname=None, type=None, start=1, boundary=None)

Bases: Enum

CREATED = 1

UPDATED = 2

DELETED = 3

class atmst.mst.diff.RecordDelta(delta_type: atmst.mst.diff.DeltaType, key: str, prior_value: cbrrr.CID | None, later_value: cbrrr.CID | None)

Bases: object

delta_type: DeltaType

key: str

prior_value: CID | None

later_value: CID | None

atmst.mst.diff.record_diff(ns: NodeStore, created: set[CID], deleted: set[CID]) → Iterable[RecordDelta]: Given two sets of MST nodes (for example, the result of mst_diff()), this returns an iterator of record changes.

atmst.mst.diff.very_slow_mst_diff(ns: NodeStore, root_a: CID, root_b: CID)

This should return the same result as mst_diff(), but it gets there in a slow but much more obvious way (enumerating all nodes), so it’s useful for testing.

It’s actually faster for smaller trees, but it chokes on trees with thousands of nodes (especially if the NodeStore is slow).

atmst.mst.diff.mst_diff(ns: NodeStore, root_a: CID, root_b: CID) → Tuple[Set[CID], Set[CID]]

XXX: This implementation is not yet ready for prime-time!

Given two MST root node CIDs, efficiently compute the difference between the two trees. The result is two sets, holding the created and deleted MST nodes respectively (referenced by CIDs).

atmst.mst.node module

class atmst.mst.node.MSTNode(keys: Tuple[str], vals: Tuple[CID], subtrees: Tuple[CID | None])

Bases: object

k/v pairs are interleaved between subtrees like so:

keys:          (0,    1,    2,    3)
vals:          (0,    1,    2,    3)
subtrees:   (0,    1,    2,    3,    4)

If a method is implemented in this class, it’s because it’s a function/property of a single node, as opposed to a whole tree

keys: Tuple[str]

vals: Tuple[CID]

subtrees: Tuple[CID | None]

classmethod empty_root() → Self

static key_height(key: str) → int

property cid: CID

property serialised: bytes

classmethod deserialise(data: bytes) → Self

is_empty() → bool

property height: int

gte_index(key: str) → int: find the index of the first key greater than or equal to the specified key if all keys are smaller, it returns len(keys)

atmst.mst.node_store module

class atmst.mst.node_store.NodeStore(bs: BlockStore)

Bases: object

NodeStore wraps a BlockStore to provide a more ergonomic interface for loading and storing MSTNodes

bs: BlockStore

cache: Dict[CID | None, MSTNode]

get_node(cid: CID | None) → MSTNode

stored_node(node: MSTNode) → MSTNode

pretty(node_cid: CID | None) → str

atmst.mst.node_walker module

class atmst.mst.node_walker.NodeWalker(ns: NodeStore, root_cid: CID | None, lpath: str | None = '', rpath: str | None = 'ÿ')

Bases: object

NodeWalker makes implementing tree diffing and other MST query ops more convenient (but it does not, itself, implement them).

A NodeWalker starts off at the root of a tree, and can walk along or recurse down into subtrees.

Walking “off the end” of a subtree brings you back up to its next non-empty parent.

Recall MSTNode layout:

keys:  (lpath)  (0,    1,    2,    3)  (rpath)
vals:           (0,    1,    2,    3)
subtrees:    (0,    1,    2,    3,    4)

PATH_MIN = ''

PATH_MAX = 'ÿ'

class StackFrame(node: atmst.mst.node.MSTNode, lpath: str, rpath: str, idx: int)

Bases: object

node: MSTNode

lpath: str

rpath: str

idx: int

ns: NodeStore

stack: List[StackFrame]

subtree_walker() → Self

property frame: StackFrame

property lpath: str

property lval: CID | None

property subtree: CID | None

property rpath: str

property rval: CID | None

property is_final: bool

right() → None

down() → None

next_kv() → Tuple[str, CID]

iter_kv() → Iterable[Tuple[str, CID]]

iter_nodes() → Iterable[MSTNode]

iter_node_cids() → Iterable[CID]

iter_kv_range(start: str, end: str, end_inclusive: bool = False) → Iterable[Tuple[str, CID]]

find_value(key: str) → CID | None

atmst.mst.node_wrangler module

class atmst.mst.node_wrangler.NodeWrangler(ns: NodeStore)

Bases: object

NodeWrangler is where core MST transformation ops are implemented, backed by a NodeStore

The external APIs take a CID (the MST root) and return a CID (the new root), while storing any newly created nodes in the NodeStore.

Neither method should ever fail - deleting a node that doesn’t exist is a nop, and adding the same node twice with the same value is also a nop. Callers can detect these cases by seeing if the initial and final CIDs changed.

ns: NodeStore

put_record(root_cid: CID, key: str, val: CID) → CID

del_record(root_cid: CID, key: str) → CID

atmst.mst package

Submodules

atmst.mst.diff module

atmst.mst.node module

atmst.mst.node_store module

atmst.mst.node_walker module

atmst.mst.node_wrangler module

Module contents