Muse — Architecture Plan: From File-Hash MVP to Universal Multidimensional VCS

Status: Working document — pre-implementation spec. No backward compatibility constraints. We own every line.

---

Table of Contents

1. Honest Assessment of Current State
2. North Star: What We're Building Toward
3. Phase 1 — Typed Delta Algebra
4. Phase 2 — Domain Schema & Diff Algorithm Library
5. Phase 3 — Operation-Level Merge Engine
6. Phase 4 — CRDT Semantics for Convergent Multi-Agent Writes
7. Cross-Cutting Concerns
8. Test Strategy
9. Implementation Order and Dependencies

---

1. Honest Assessment of Current State

What is good and must be preserved

• Content-addressed object store — SHA-256 blobs in .muse/objects/. This is correct at every scale. Git proved it. Keep it forever.
• Plugin protocol boundary — MuseDomainPlugin is the right abstraction. Core engine is domain-agnostic. This must remain true through every phase.
• BFS LCA merge-base finder — mathematically correct for DAG commit graphs.
• File-level three-way merge — correct for the current granularity.
• .museattributes strategy system — the right place for declarative per-path merge policy.

What is genuinely limited

The entire system operates at a single fixed level of abstraction: the file-path level. The only thing the core engine ever asks about a domain is:

{added: [path, ...], removed: [path, ...], modified: [path, ...]}

modified is completely opaque. The engine knows that a file changed (SHA-256 differs), but not what changed inside it, where, how, or whether the change commutes with the other branch's changes.

Consequences of this ceiling:

Scenario	Current behavior	Correct behavior
Insert note at bar 12 on branch A; insert note at bar 45 on branch B	File-level conflict	Auto-merge: non-overlapping positions
Insert nucleotide at position 1000 on branch A; insert at position 5000 on branch B	File-level conflict	Auto-merge
Two agents edit different nodes in the same scene graph	File-level conflict	Auto-merge
muse show <commit>	"tracks/drums.mid modified"	"bar 12: C4 quarter inserted; velocity 80→90"
Every new domain plugin	Must implement its own merge engine	Gets LCS/tree-edit/numerical for free from core

The MIDI plugin works around this by implementing MIDI dimension-merge inside the plugin. But that means every new domain has to re-invent sub-file merge from scratch, in isolation, with no shared vocabulary or algorithm library. At thousands of domains and millions of agents, that's impossible.

---

2. North Star: What We're Building Toward

A universal multidimensional VCS where:

1. Any domain can declare its data structure schema (sequence, tree, graph, tensor, map, or composites) and immediately get the right diff and merge algorithm for free — without implementing one.

2. Diffs are meaningful, not just path lists. muse show displays "note C4 inserted at beat 3.5" or "gene BRCA1 exon 7 deleted" or "mesh vertex 42 moved (3.2, 0.0, -1.1)".

3. Conflicts are detected at operation granularity, not file granularity. Two agents editing non-overlapping parts of the same sequence never conflict.

4. Millions of agents can converge without explicit conflict resolution, by opting into CRDT semantics where merge is a mathematical join on a lattice.

5. The core engine never changes when new domains are added. Every improvement to the diff algorithm library automatically benefits all existing plugins.

---

3. Phase 1 — Typed Delta Algebra

Goal: Replace the opaque {added, removed, modified} delta with a rich, composable operation vocabulary. Plugins return structured deltas. The core engine stores them and displays them. No core engine conflict logic changes yet — that comes in Phase 3.

Estimated scope: 2–3 weeks of implementation, 1 week of test writing.

3.1 Motivation

Today DeltaManifest.modified is a list[str] of paths. It tells you nothing about what happened inside those files. This makes muse show, muse diff, and any programmatic consumer completely blind to intra-file changes.

Phase 1 fixes this without touching the merge engine. The protocol gets richer return types; the core engine stores and forwards them opaquely; plugins can now express sub-file changes precisely.

3.2 New Type System in muse/domain.py

Replace DeltaManifest with a composable operation-tree type system:

# ---------------------------------------------------------------------------
# Atomic position types
# ---------------------------------------------------------------------------

# A DomainAddress is a path within a domain's object graph.
# - For file-level ops: a POSIX workspace path ("tracks/drums.mid")
# - For sub-file ops:   a JSON-pointer fragment within that file ("/notes/42")
# - Plugins define what addresses mean in their domain.
DomainAddress = str

# ---------------------------------------------------------------------------
# Atomic operation types
# ---------------------------------------------------------------------------

class InsertOp(TypedDict):
    """An element was inserted into an ordered or unordered collection."""
    op: Literal["insert"]
    address: DomainAddress        # where in the structure
    position: int | None          # index for ordered sequences; None for sets
    content_id: str               # SHA-256 of inserted content (stored in object store)
    content_summary: str          # human-readable description for display

class DeleteOp(TypedDict):
    """An element was removed."""
    op: Literal["delete"]
    address: DomainAddress
    position: int | None
    content_id: str               # SHA-256 of removed content
    content_summary: str

class MoveOp(TypedDict):
    """An element was repositioned within an ordered sequence."""
    op: Literal["move"]
    address: DomainAddress
    from_position: int
    to_position: int
    content_id: str

class ReplaceOp(TypedDict):
    """An element's value changed (atomic, leaf-level)."""
    op: Literal["replace"]
    address: DomainAddress
    position: int | None
    old_content_id: str
    new_content_id: str
    old_summary: str
    new_summary: str

class PatchOp(TypedDict):
    """A nested structure was modified; carries a child StructuredDelta."""
    op: Literal["patch"]
    address: DomainAddress        # the container being patched
    child_delta: StructuredDelta  # recursive — describes what changed inside

# The union of all operation types
DomainOp = InsertOp | DeleteOp | MoveOp | ReplaceOp | PatchOp

# ---------------------------------------------------------------------------
# The new StateDelta
# ---------------------------------------------------------------------------

class StructuredDelta(TypedDict):
    """Rich, composable delta between two domain snapshots.

    ``ops`` is an ordered list of operations that transforms ``base`` into
    ``target`` when applied in sequence. The core engine treats this as an
    opaque blob for storage and display. The merge engine in Phase 3 will
    reason over it for commutativity.

    ``summary`` is a precomputed human-readable string for ``muse show``.
    Plugins compute this because only they understand their domain semantics.
    """
    domain: str
    ops: list[DomainOp]
    summary: str                  # "3 notes added, 1 bar restructured"

# StateDelta is now StructuredDelta. DeltaManifest is gone.
StateDelta = StructuredDelta

Key design decisions:

• content_id references the object store (.muse/objects/). This means inserted/deleted/replaced sub-elements are content-addressed and retrievable. No bloat in the delta itself.
• content_summary is plugin-computed human-readable text. The core engine uses it verbatim in muse show. Plugins are responsible for making it meaningful.
• PatchOp is recursive. A MIDI file modification is a PatchOp whose child_delta contains InsertOp/DeleteOp/MoveOp on individual notes. A genomics sequence modification is a PatchOp whose child delta contains nucleotide-level ops.
• position: int | None — None signals an unordered collection (set semantics). The merge engine in Phase 3 uses this to determine commutativity: two inserts into the same unordered collection always commute; two inserts at the same position in an ordered sequence may conflict.

3.3 Updated Plugin Protocol

The diff method signature stays the same (base: StateSnapshot, target: StateSnapshot) -> StateDelta), but StateDelta is now StructuredDelta. The protocol docstring must document the expectation:

def diff(self, base: StateSnapshot, target: StateSnapshot) -> StateDelta:
    """Compute the structured delta between two snapshots.

    Returns a ``StructuredDelta`` where ``ops`` is a minimal list of
    operations that transforms ``base`` into ``target``. Plugins should:

    1. Compute ops at the finest granularity they can interpret.
    2. Assign meaningful ``content_summary`` strings to each op.
    3. Store any new sub-element content in the object store if ``repo_root``
       is available; otherwise use deterministic synthetic IDs.
    4. Compute a human-readable ``summary`` across all ops.

    The core engine stores this delta alongside the commit record so that
    ``muse show`` and ``muse diff`` can display it without reloading blobs.
    """
    ...

apply also changes — it now receives a StructuredDelta and must apply its ops list:

def apply(self, delta: StateDelta, live_state: LiveState) -> LiveState:
    """Apply a structured delta to produce a new live state.

    Plugins must implement application of all four op types. For plugins
    where full in-memory application is impractical (e.g. large binary
    files), ``live_state`` should be a ``pathlib.Path`` and the plugin
    should apply ops to disk files directly.
    """
    ...

3.4 Updated DriftReport

DriftReport.delta is now a StructuredDelta. This means muse status can display the rich summary:

@dataclass
class DriftReport:
    has_drift: bool
    summary: str = ""
    delta: StateDelta = field(default_factory=lambda: StructuredDelta(
        domain="", ops=[], summary="working tree clean",
    ))

3.5 Updated MergeResult

MergeResult adds an op_log — the ordered list of operations that produced the merged snapshot, useful for audit and replay:

@dataclass
class MergeResult:
    merged: StateSnapshot
    conflicts: list[str] = field(default_factory=list)
    applied_strategies: dict[str, str] = field(default_factory=dict)
    dimension_reports: dict[str, dict[str, str]] = field(default_factory=dict)
    op_log: list[DomainOp] = field(default_factory=list)  # NEW

    @property
    def is_clean(self) -> bool:
        return len(self.conflicts) == 0

3.6 Updated Music Plugin

The MIDI plugin's diff method must now return a StructuredDelta. File-level ops are the minimum bar. The MIDI dimension merge already has the machinery to go deeper — it should produce PatchOp entries for modified .mid files:

def diff(self, base: StateSnapshot, target: StateSnapshot) -> StateDelta:
    base_files = base["files"]
    target_files = target["files"]
    base_paths = set(base_files)
    target_paths = set(target_files)

    ops: list[DomainOp] = []

    for path in sorted(target_paths - base_paths):
        ops.append(InsertOp(
            op="insert",
            address=path,
            position=None,           # file collection is unordered
            content_id=target_files[path],
            content_summary=f"new file: {path}",
        ))

    for path in sorted(base_paths - target_paths):
        ops.append(DeleteOp(
            op="delete",
            address=path,
            position=None,
            content_id=base_files[path],
            content_summary=f"deleted: {path}",
        ))

    for path in sorted(p for p in base_paths & target_paths
                       if base_files[p] != target_files[p]):
        if path.lower().endswith(".mid"):
            # Attempt deep MIDI diff → PatchOp with note-level child ops
            child_delta = _diff_midi_deep(base_files[path], target_files[path])
            if child_delta is not None:
                ops.append(PatchOp(
                    op="patch",
                    address=path,
                    child_delta=child_delta,
                ))
                continue
        # Fallback: atomic replace
        ops.append(ReplaceOp(
            op="replace",
            address=path,
            position=None,
            old_content_id=base_files[path],
            new_content_id=target_files[path],
            old_summary=f"{path} (prev)",
            new_summary=f"{path} (new)",
        ))

    summary = _summarise_ops(ops)
    return StructuredDelta(domain=_DOMAIN_TAG, ops=ops, summary=summary)

_diff_midi_deep calls into a new midi_diff.py module (sibling of midi_merge.py) that runs the Myers LCS algorithm on the MIDI note sequence and returns a StructuredDelta with note-level InsertOp/DeleteOp/MoveOp entries.

3.7 Serialisation Contract

StructuredDelta must remain JSON-serialisable (the core engine stores it in commit records). The recursive PatchOp.child_delta is also a StructuredDelta, so it serialises naturally. All content_id references are SHA-256 hex strings pointing to objects already in the store — no embedded binary.

The commit record format (CommitRecord) must add a structured_delta field alongside (or replacing) the existing delta storage. This is a commit format change — acceptable since we have no backwards compat requirement.

3.8 Phase 1 Test Cases

New test file: tests/test_structured_delta.py

test_insert_op_round_trips_json
test_delete_op_round_trips_json
test_move_op_round_trips_json
test_replace_op_round_trips_json
test_patch_op_with_child_delta_round_trips_json
test_structured_delta_satisfies_state_delta_type
test_midi_plugin_diff_returns_structured_delta
test_midi_plugin_diff_file_add_produces_insert_op
test_midi_plugin_diff_file_remove_produces_delete_op
test_midi_plugin_diff_file_modify_produces_replace_op
test_midi_plugin_diff_midi_modify_produces_patch_op_with_child_ops
test_drift_report_delta_is_structured_delta
test_muse_show_displays_structured_summary
test_muse_diff_displays_per_op_lines

New test file: tests/test_midi_diff.py

test_midi_diff_empty_to_single_note_is_one_insert
test_midi_diff_single_note_to_empty_is_one_delete
test_midi_diff_note_velocity_change_is_replace
test_midi_diff_note_inserted_in_middle_identified_correctly
test_midi_diff_note_transposition_identified_as_replace
test_midi_diff_no_change_returns_empty_ops
test_midi_diff_summary_string_is_human_readable

3.9 Files Changed in Phase 1

File	Change
muse/domain.py	Replace DeltaManifest/StateDelta with DomainOp union + StructuredDelta. Update DriftReport, MergeResult.
muse/core/store.py	CommitRecord gains structured_delta: StructuredDelta \| None field.
muse/plugins/music/plugin.py	diff() returns StructuredDelta. apply() handles StructuredDelta.
muse/plugins/music/midi_diff.py	New. Myers LCS on MIDI note sequences → StructuredDelta.
muse/cli/commands/show.py	Display structured_delta.summary and per-op lines.
muse/cli/commands/diff.py	Display structured diff output.
tests/test_structured_delta.py	New. All Phase 1 tests.
tests/test_midi_diff.py	New. MIDI diff algorithm tests.
tests/test_midi_plugin.py	Update to assert StructuredDelta return type.

---

4. Phase 2 — Domain Schema & Diff Algorithm Library

Goal: Plugins declare their data structure schema. The core engine dispatches to the right diff algorithm automatically. New plugin authors get LCS, tree-edit, and numerical diff for free — no algorithm implementation required.

Estimated scope: 3–4 weeks of implementation, 1 week of test writing.

4.1 Motivation

After Phase 1, every plugin must still implement its own diff algorithm. A genomics plugin author has to implement Myers LCS to get note-level (nucleotide-level) diffs. A 3D plugin author has to implement tree-edit distance. This is a PhD-level prerequisite for every new domain.

Phase 2 inverts this: the plugin declares its data structure, and the core engine drives the right algorithm. The genomics plugin says "my data is an ordered sequence of nucleotides, use LCS" and gets exactly that — for free.

4.2 Domain Schema Types

New file: muse/core/schema.py

"""Domain schema declaration types.

A plugin implements ``schema()`` returning a ``DomainSchema`` to declare
the structural shape of its data. The core engine uses this declaration
to drive the correct diff algorithm, validate delta types, and offer
informed merge conflict messages.
"""
from __future__ import annotations
from typing import Literal, TypedDict


# ---------------------------------------------------------------------------
# Primitive element schemas
# ---------------------------------------------------------------------------

class SequenceSchema(TypedDict):
    """Ordered sequence of homogeneous elements (LCS-diffable)."""
    kind: Literal["sequence"]
    element_type: str              # e.g. "note", "nucleotide", "frame", "voxel"
    identity: Literal["by_id", "by_position", "by_content"]
    diff_algorithm: Literal["lcs", "myers", "patience"]
    # Optional: alphabet constraint for validation
    alphabet: list[str] | None

class TreeSchema(TypedDict):
    """Hierarchical tree structure (tree-edit-diffable)."""
    kind: Literal["tree"]
    node_type: str                 # e.g. "scene_node", "xml_element", "ast_node"
    diff_algorithm: Literal["zhang_shasha", "gumtree"]

class TensorSchema(TypedDict):
    """N-dimensional numerical array (sparse-numerical-diffable)."""
    kind: Literal["tensor"]
    dtype: Literal["float32", "float64", "int8", "int16", "int32", "int64"]
    rank: int                      # number of dimensions
    epsilon: float                 # tolerance: |a - b| < epsilon → "unchanged"
    diff_mode: Literal["sparse", "block", "full"]

class MapSchema(TypedDict):
    """Key-value map with known or dynamic keys."""
    kind: Literal["map"]
    key_type: str
    value_schema: ElementSchema    # recursive
    identity: Literal["by_key"]

class SetSchema(TypedDict):
    """Unordered collection of unique elements (current hash-set approach)."""
    kind: Literal["set"]
    element_type: str
    identity: Literal["by_content", "by_id"]

# The union of all element schema types
ElementSchema = SequenceSchema | TreeSchema | TensorSchema | MapSchema | SetSchema


# ---------------------------------------------------------------------------
# Dimension spec — a named structural sub-dimension
# ---------------------------------------------------------------------------

class DimensionSpec(TypedDict):
    """A named semantic sub-dimension of the domain's state.

    For music: "melodic", "harmonic", "dynamic", "structural".
    For genomics: "exons", "introns", "promoters", "metadata".
    For 3D spatial: "geometry", "materials", "lighting", "animation".

    Each dimension can use a different element schema and diff algorithm.
    The merge engine can merge dimensions independently.
    """
    name: str
    description: str
    schema: ElementSchema
    # Whether conflicts in this dimension block the whole file's merge
    # or are resolved independently.
    independent_merge: bool


# ---------------------------------------------------------------------------
# Top-level domain schema
# ---------------------------------------------------------------------------

class DomainSchema(TypedDict):
    """Complete structural declaration for a domain plugin.

    Returned by ``MuseDomainPlugin.schema()``. The core engine reads this
    once at plugin registration time and uses it to:

    1. Select the correct diff algorithm for each dimension.
    2. Generate typed delta validation.
    3. Provide informed conflict messages (citing dimension names).
    4. Route to CRDT merge if ``merge_mode`` is ``"crdt"`` (Phase 4).
    """
    domain: str
    description: str
    # Dimensions that make up this domain's state.
    # The core engine merges each independently when possible.
    dimensions: list[DimensionSpec]
    # The top-level collection of domain objects (e.g. files, sequences, nodes)
    top_level: ElementSchema
    # Which merge strategy to use at the top level
    merge_mode: Literal["three_way", "crdt"]   # "crdt" is Phase 4
    # Version of the schema format itself (for future migrations)
    schema_version: Literal[1]

4.3 Schema Method Added to Plugin Protocol

def schema(self) -> DomainSchema:
    """Declare the structural schema of this domain's state.

    The core engine calls this once at startup. Plugins should return a
    stable, deterministic ``DomainSchema``. This declaration drives diff
    algorithm selection, delta validation, and conflict messaging.

    See ``muse.core.schema`` for all available element schema types.
    """
    ...

4.4 Example Schema Declarations

Music plugin:

def schema(self) -> DomainSchema:
    return DomainSchema(
        domain="midi",
        description="MIDI and audio file versioning with note-level diff",
        top_level=SetSchema(
            kind="set",
            element_type="audio_file",
            identity="by_content",
        ),
        dimensions=[
            DimensionSpec(
                name="melodic",
                description="Note pitches and durations over time",
                schema=SequenceSchema(
                    kind="sequence",
                    element_type="note_event",
                    identity="by_position",
                    diff_algorithm="lcs",
                    alphabet=None,
                ),
                independent_merge=True,
            ),
            DimensionSpec(
                name="harmonic",
                description="Chord progressions and key signatures",
                schema=SequenceSchema(
                    kind="sequence",
                    element_type="chord_event",
                    identity="by_position",
                    diff_algorithm="lcs",
                    alphabet=None,
                ),
                independent_merge=True,
            ),
            DimensionSpec(
                name="dynamic",
                description="Velocity and expression curves",
                schema=TensorSchema(
                    kind="tensor",
                    dtype="float32",
                    rank=1,
                    epsilon=1.0,     # velocities are integers 0–127; 1.0 tolerance
                    diff_mode="sparse",
                ),
                independent_merge=True,
            ),
            DimensionSpec(
                name="structural",
                description="Track layout, time signatures, tempo map",
                schema=TreeSchema(
                    kind="tree",
                    node_type="track_node",
                    diff_algorithm="zhang_shasha",
                ),
                independent_merge=False,   # structural changes block all dimensions
            ),
        ],
        merge_mode="three_way",
        schema_version=1,
    )

Hypothetical genomics plugin:

def schema(self) -> DomainSchema:
    return DomainSchema(
        domain="genomics",
        description="DNA/RNA sequence versioning at nucleotide resolution",
        top_level=MapSchema(
            kind="map",
            key_type="sequence_id",   # e.g. chromosome name
            value_schema=SequenceSchema(
                kind="sequence",
                element_type="nucleotide",
                identity="by_position",
                diff_algorithm="myers",
                alphabet=["A", "T", "C", "G", "U", "N", "-"],
            ),
            identity="by_key",
        ),
        dimensions=[
            DimensionSpec(
                name="coding_regions",
                description="Exons and coding sequence",
                schema=SequenceSchema(
                    kind="sequence",
                    element_type="nucleotide",
                    identity="by_position",
                    diff_algorithm="myers",
                    alphabet=["A", "T", "C", "G", "N"],
                ),
                independent_merge=True,
            ),
            DimensionSpec(
                name="regulatory",
                description="Promoters, enhancers, splice sites",
                schema=SetSchema(
                    kind="set",
                    element_type="regulatory_element",
                    identity="by_id",
                ),
                independent_merge=True,
            ),
            DimensionSpec(
                name="metadata",
                description="Annotations, quality scores, provenance",
                schema=MapSchema(
                    kind="map",
                    key_type="annotation_key",
                    value_schema=TensorSchema(
                        kind="tensor",
                        dtype="float32",
                        rank=1,
                        epsilon=0.001,
                        diff_mode="sparse",
                    ),
                    identity="by_key",
                ),
                independent_merge=True,
            ),
        ],
        merge_mode="three_way",
        schema_version=1,
    )

These declarations are roughly 30 lines each and require zero algorithm knowledge from the plugin author. The core engine does the rest.

4.5 Diff Algorithm Library

New directory: muse/core/diff_algorithms/

muse/core/diff_algorithms/
    __init__.py        → dispatch function
    lcs.py             → Myers / patience diff for ordered sequences
    tree_edit.py       → Zhang-Shasha tree edit distance
    numerical.py       → sparse numerical diff for tensors
    set_ops.py         → hash-set algebra (current approach, extracted)

muse/core/diff_algorithms/__init__.py — schema-driven dispatch:

def diff_by_schema(
    schema: ElementSchema,
    base: SequenceData | TreeData | TensorData | SetData | MapData,
    target: SequenceData | TreeData | TensorData | SetData | MapData,
    *,
    domain: str,
    address: str = "",
) -> StructuredDelta:
    """Dispatch to the correct diff algorithm based on ``schema.kind``."""
    match schema["kind"]:
        case "sequence":
            return lcs.diff(schema, base, target, domain=domain, address=address)
        case "tree":
            return tree_edit.diff(schema, base, target, domain=domain, address=address)
        case "tensor":
            return numerical.diff(schema, base, target, domain=domain, address=address)
        case "set":
            return set_ops.diff(schema, base, target, domain=domain, address=address)
        case "map":
            return _diff_map(schema, base, target, domain=domain, address=address)

muse/core/diff_algorithms/lcs.py — Myers diff algorithm:

The Myers diff algorithm (the same one Git uses) finds the shortest edit script between two sequences. For ordered sequences, it gives minimal inserts and deletes. For moves, a post-processing pass detects delete+insert pairs of the same element.

Key functions:

• myers_ses(base: list[T], target: list[T]) -> list[EditOp] — shortest edit script
• detect_moves(inserts: list[InsertOp], deletes: list[DeleteOp]) -> list[MoveOp] — post-process
• diff(schema: SequenceSchema, base: list[T], target: list[T], ...) -> StructuredDelta

The patience diff variant (used by some Git backends) gives better results when sequences have many repeated elements — expose it as an option.

muse/core/diff_algorithms/tree_edit.py — Zhang-Shasha:

Zhang-Shasha computes the minimum edit distance between two labeled ordered trees. Operations: relabel (→ ReplaceOp), insert, delete. The algorithm is O(n²m) where n, m are tree sizes — acceptable for domain objects up to ~10k nodes.

Key functions:

• zhang_shasha(base: TreeNode, target: TreeNode) -> list[TreeEditOp] — edit script
• diff(schema: TreeSchema, base: TreeNode, target: TreeNode, ...) -> StructuredDelta

muse/core/diff_algorithms/numerical.py — sparse tensor diff:

For numerical arrays (simulation state, velocity curves, weight matrices), exact byte comparison is wrong — floating-point drift doesn't constitute a meaningful change. The numerical diff:

1. Compares element-wise with schema.epsilon tolerance.
2. Returns ReplaceOp only for elements where |base[i] - target[i]| >= epsilon.
3. In "sparse" mode: emits one ReplaceOp per changed element (good for sparse changes).
4. In "block" mode: groups adjacent changes into contiguous range ops (good for dense changes).
5. In "full" mode: emits a single ReplaceOp for the entire array if anything changed (fallback for very large tensors where element-wise ops are too expensive).

muse/core/diff_algorithms/set_ops.py — extracted from current code:

The current hash-set algebra pulled into a pure function that returns a StructuredDelta. No algorithmic change — this is refactoring to put existing logic into the new common library.

4.6 Plugin Registry Gains Schema Lookup

muse/core/plugin_registry.py gains a schema_for(domain: str) -> DomainSchema | None function. This allows the CLI and merge engine to look up a domain's schema without having a plugin instance.

4.7 Phase 2 Test Cases

New test file: tests/test_diff_algorithms.py

# LCS / Myers
test_lcs_empty_to_sequence_is_all_inserts
test_lcs_sequence_to_empty_is_all_deletes
test_lcs_identical_sequences_returns_no_ops
test_lcs_single_insert_in_middle
test_lcs_single_delete_in_middle
test_lcs_move_detected_from_delete_plus_insert
test_lcs_transposition_of_two_elements
test_lcs_patience_mode_handles_repeated_elements
test_lcs_produces_valid_structured_delta

# Tree edit
test_tree_edit_leaf_relabel_is_replace
test_tree_edit_node_insert
test_tree_edit_node_delete
test_tree_edit_subtree_move
test_tree_edit_identical_trees_returns_no_ops
test_tree_edit_produces_valid_structured_delta

# Numerical
test_numerical_within_epsilon_returns_no_ops
test_numerical_outside_epsilon_returns_replace
test_numerical_sparse_mode_one_op_per_element
test_numerical_block_mode_groups_adjacent
test_numerical_full_mode_single_op
test_numerical_produces_valid_structured_delta

# Set ops
test_set_diff_add_returns_insert
test_set_diff_remove_returns_delete
test_set_diff_no_change_returns_empty
test_set_diff_produces_valid_structured_delta

# Schema dispatch
test_dispatch_sequence_schema_calls_lcs
test_dispatch_tree_schema_calls_zhang_shasha
test_dispatch_tensor_schema_calls_numerical
test_dispatch_set_schema_calls_set_ops
test_dispatch_map_schema_recurses

New test file: tests/test_domain_schema.py

test_midi_plugin_schema_returns_domain_schema
test_midi_plugin_schema_has_four_dimensions
test_midi_plugin_schema_melodic_dimension_is_sequence
test_midi_plugin_schema_structural_dimension_is_tree
test_midi_plugin_schema_dynamic_dimension_is_tensor
test_schema_round_trips_json
test_schema_version_is_1
test_plugin_registry_schema_lookup

4.8 Files Changed in Phase 2

File	Change
muse/core/schema.py	New. All schema TypedDict types.
muse/core/diff_algorithms/__init__.py	New. Schema-driven dispatch.
muse/core/diff_algorithms/lcs.py	New. Myers + patience diff.
muse/core/diff_algorithms/tree_edit.py	New. Zhang-Shasha implementation.
muse/core/diff_algorithms/numerical.py	New. Sparse/block/full tensor diff.
muse/core/diff_algorithms/set_ops.py	New. Extracted from merge_engine.py.
muse/domain.py	Add schema() to MuseDomainPlugin protocol.
muse/core/plugin_registry.py	Add schema_for(domain) -> DomainSchema \| None.
muse/plugins/music/plugin.py	Implement schema() returning full DomainSchema. diff() dispatches through diff_by_schema.
tests/test_diff_algorithms.py	New.
tests/test_domain_schema.py	New.

---

5. Phase 3 — Operation-Level Merge Engine

Goal: The core merge engine reasons over DomainOp trees, not just path sets. Two operations that touch non-overlapping positions auto-merge without conflict. The commutativity rules are uniform across all domains.

Estimated scope: 4–6 weeks (this is the hardest phase).

5.1 Motivation

After Phase 2, we can produce rich structured deltas and display them beautifully. But the merge engine still detects conflicts at file-path granularity. Two agents inserting notes at bar 12 and bar 45 respectively still produce a "conflict" even though their changes commute perfectly.

Phase 3 fixes this by making the merge engine reason over operations directly. This is operational transformation (OT) — the theory behind Google Docs' real-time collaborative editing, applied to version-controlled multidimensional state.

5.2 Commutativity Rules

Two operations A and B commute (can be auto-merged) if and only if applying them in any order produces the same result. The rules are:

Op A	Op B	Commute?	Condition
InsertOp(pos=i)	InsertOp(pos=j)	Yes	i ≠ j (different positions)
InsertOp(pos=i)	InsertOp(pos=i)	No	Same position — positional conflict
InsertOp	DeleteOp	No	Unless different subtrees
DeleteOp(addr=A)	DeleteOp(addr=B)	Yes	A ≠ B
DeleteOp(addr=A)	DeleteOp(addr=A)	Yes	Consensus delete — clean
ReplaceOp(addr=A)	ReplaceOp(addr=B)	Yes	A ≠ B
ReplaceOp(addr=A)	ReplaceOp(addr=A)	No	Same address — value conflict
MoveOp(from=i)	MoveOp(from=j)	Yes	i ≠ j
MoveOp(from=i)	DeleteOp(pos=i)	No	Move-delete conflict
PatchOp(addr=A)	PatchOp(addr=B)	Yes	A ≠ B — recurse on children
PatchOp(addr=A)	PatchOp(addr=A)	Recurse	Check child ops for conflicts

For unordered collections (position=None), inserts always commute with other inserts. For ordered sequences, inserts at the same position do NOT commute — this is a genuine conflict that requires resolution.

5.3 Operation Transformer Functions

New file: muse/core/op_transform.py

"""Operational transformation for Muse domain operations.

Implements the commutativity rules that let the merge engine determine
which operation pairs can be auto-merged and which are true conflicts.

The public API is:

- ``ops_commute(a, b)`` — True if ops A and B can be applied in any order.
- ``transform(a, b)`` — Return a', b' such that applying a then b' = applying b then a'.
- ``merge_op_lists(base_ops, ours_ops, theirs_ops)`` → MergeOpsResult
"""
from __future__ import annotations
from dataclasses import dataclass, field
from muse.domain import DomainOp, InsertOp, DeleteOp, MoveOp, ReplaceOp, PatchOp


@dataclass
class MergeOpsResult:
    """Result of merging two operation lists against a common base."""
    merged_ops: list[DomainOp] = field(default_factory=list)
    conflict_ops: list[tuple[DomainOp, DomainOp]] = field(default_factory=list)

    @property
    def is_clean(self) -> bool:
        return len(self.conflict_ops) == 0


def ops_commute(a: DomainOp, b: DomainOp) -> bool:
    """Return True if operations A and B commute (auto-mergeable)."""
    ...

def transform(a: DomainOp, b: DomainOp) -> tuple[DomainOp, DomainOp]:
    """Return (a', b') such that a ∘ b' = b ∘ a'.

    This is the core OT transform function. When two operations a and b
    are generated concurrently against the same base, transform returns
    adjusted versions that can be applied sequentially to achieve the same
    final state.
    """
    ...

def merge_op_lists(
    base_ops: list[DomainOp],
    ours_ops: list[DomainOp],
    theirs_ops: list[DomainOp],
) -> MergeOpsResult:
    """Three-way merge at operation granularity.

    Applies commutativity rules to detect which pairs of operations truly
    conflict. Non-conflicting pairs are auto-merged by applying OT transform.
    Conflicting pairs are collected in ``conflict_ops`` for plugin resolution.
    """
    ...

5.4 Updated Core Merge Engine

muse/core/merge_engine.py gains a new entry point:

def merge_structured(
    base_delta: StructuredDelta,
    ours_delta: StructuredDelta,
    theirs_delta: StructuredDelta,
) -> MergeOpsResult:
    """Merge two structured deltas against a common base delta.

    Uses ``op_transform.merge_op_lists`` for operation-level conflict
    detection. Falls back to file-level path detection for ops that do
    not carry position information (e.g. SetSchema domains).
    """
    from muse.core.op_transform import merge_op_lists
    return merge_op_lists(base_delta["ops"], ours_delta["ops"], theirs_delta["ops"])

The existing diff_snapshots / detect_conflicts / apply_merge functions remain for plugins that have not yet produced StructuredDelta from diff() — they serve as the fallback.

5.5 Plugin Protocol Gains merge_ops

A new optional method on the protocol (not required — the core engine falls back to file-level merge if absent):

def merge_ops(
    self,
    base: StateSnapshot,
    ours_ops: list[DomainOp],
    theirs_ops: list[DomainOp],
    *,
    repo_root: pathlib.Path | None = None,
) -> MergeResult:
    """Merge two op lists against base, using domain-specific conflict resolution.

    The core engine calls this when both branches have produced
    ``StructuredDelta`` from ``diff()``. The plugin may use
    ``muse.core.op_transform.merge_op_lists`` as the foundation and
    add domain-specific resolution on top (e.g. checking ``.museattributes``).

    If not implemented, the core engine falls back to the existing
    three-way file-level merge via ``merge()``.
    """
    ...

5.6 Position Adjustment After Transform

A critical detail: when two inserts commute because they're at different positions, the positions of later-applied operations must be adjusted. This is the "index shifting" problem in OT:

Base: [A, B, C]
Ours: insert X at position 1 → [A, X, B, C]
Theirs: insert Y at position 2 → [A, B, Y, C]

After transform:
  ours' (applied after theirs): insert X at position 1 → [A, X, B, Y, C]  ✓
  theirs' (applied after ours): insert Y at position 3 → [A, X, B, Y, C]  ✓

The transform function must adjust positions for all sequence operations. This is well-understood in OT literature but requires care in implementation, particularly for interleaved inserts and deletes.

5.7 Phase 3 Test Cases

New test file: tests/test_op_transform.py

# Commutativity oracle
test_commute_inserts_at_different_positions_is_true
test_commute_inserts_at_same_position_is_false
test_commute_deletes_at_different_addresses_is_true
test_commute_consensus_delete_is_true
test_commute_replaces_at_different_addresses_is_true
test_commute_replaces_at_same_address_is_false
test_commute_move_and_delete_same_position_is_false
test_commute_patch_at_different_addresses_is_true
test_commute_patch_at_same_address_recurses_children

# OT transform function
test_transform_two_inserts_adjusts_positions_correctly
test_transform_insert_and_delete_produces_adjusted_ops
test_transform_identity_when_ops_commute

# Three-way merge
test_merge_op_lists_clean_non_overlapping
test_merge_op_lists_same_op_both_sides_is_idempotent
test_merge_op_lists_conflict_same_position_insert
test_merge_op_lists_conflict_same_address_replace
test_merge_op_lists_consensus_delete_both_sides
test_merge_op_lists_nested_patch_recurses
test_merge_op_lists_position_adjustment_cascades
test_merge_op_lists_empty_one_side_applies_other
test_merge_op_lists_both_empty_returns_base

# Integration: merge engine uses op_transform when structured deltas available
test_merge_engine_uses_op_transform_for_structured_deltas
test_merge_engine_falls_back_to_file_level_without_structured_deltas
test_full_merge_non_overlapping_note_inserts_auto_merges
test_full_merge_same_note_insert_produces_conflict

5.8 Files Changed in Phase 3

File	Change
muse/core/op_transform.py	New. ops_commute, transform, merge_op_lists.
muse/core/merge_engine.py	Add merge_structured(). Fallback logic preserved.
muse/domain.py	Add optional merge_ops() to MuseDomainPlugin protocol.
muse/plugins/music/plugin.py	Implement merge_ops() using op_transform.
tests/test_op_transform.py	New.
tests/test_core_merge_engine.py	Add structured-delta merge tests.

---

6. Phase 4 — CRDT Semantics for Convergent Multi-Agent Writes

Goal: Plugin authors can opt into CRDT (Conflict-free Replicated Data Type) semantics. Merge becomes a mathematical join on a lattice. No conflict state ever exists. Millions of agents can write concurrently and always converge.

Estimated scope: 6–8 weeks (significant distributed systems work).

6.1 Motivation

Phases 1–3 give you an extremely powerful three-way merge system. But three-way merge has a fundamental limit: it requires a common ancestor (merge base). In a world of millions of concurrent agents writing to shared state across unreliable networks, finding and coordinating around a merge base is expensive and sometimes impossible.

CRDTs eliminate this: given any two replicas of a CRDT data structure, the join operation produces a deterministic merged state — no base required, no conflicts possible, no coordination needed. This is mathematically guaranteed by the lattice laws (commutativity, associativity, idempotency of join).

This is the endgame for the multi-agent scenario.

6.2 CRDT Primitive Library

New directory: muse/core/crdts/

muse/core/crdts/
    __init__.py
    lww_register.py    → Last-Write-Wins Register
    or_set.py          → Observed-Remove Set
    rga.py             → Replicated Growable Array (ordered sequences)
    aw_map.py          → Add-Wins Map
    g_counter.py       → Grow-only Counter
    vclock.py          → Vector Clock (causal ordering)

muse/core/crdts/lww_register.py — Last-Write-Wins Register:

Stores a single value with a timestamp. join takes the value with the higher timestamp. Appropriate for scalar config values, metadata, labels. Requires a reliable wall clock or logical clock for correct behavior.

class LWWValue(TypedDict):
    value: str          # JSON-serialisable value
    timestamp: float    # Unix timestamp or logical clock
    author: str         # Agent ID for tiebreaking

class LWWRegister:
    """A register where the last write (by timestamp) wins on merge."""
    def read(self) -> str: ...
    def write(self, value: str, timestamp: float, author: str) -> None: ...
    def join(self, other: LWWRegister) -> LWWRegister: ...  # convergent merge
    def to_dict(self) -> LWWValue: ...
    @classmethod
    def from_dict(cls, data: LWWValue) -> LWWRegister: ...

muse/core/crdts/or_set.py — Observed-Remove Set:

An unordered set where adds always win over concurrent removes (the "add-wins" property). Each element carries a unique tag set; removing requires knowing the tags of the current observed value. Safe for sets of domain objects.

muse/core/crdts/rga.py — Replicated Growable Array:

The RGA (Replicated Growable Array) is a CRDT for ordered sequences — the mathematical foundation of collaborative text editing. Each element carries a unique identifier (timestamp + author). Concurrent inserts at the same position are resolved deterministically by author ID. This gives you Google Docs-style collaborative editing semantics for any ordered sequence domain.

class RGAElement(TypedDict):
    id: str             # stable unique ID: f"{timestamp}@{author}"
    value: str          # content hash of element (references object store)
    deleted: bool       # tombstone — never actually removed, marked deleted

class RGA:
    """Replicated Growable Array — CRDT for ordered sequences."""
    def insert(self, after_id: str | None, element: RGAElement) -> None: ...
    def delete(self, element_id: str) -> None: ...
    def join(self, other: RGA) -> RGA: ...  # always succeeds, no conflicts
    def to_sequence(self) -> list[str]: ...  # materialise visible elements
    def to_dict(self) -> list[RGAElement]: ...
    @classmethod
    def from_dict(cls, data: list[RGAElement]) -> RGA: ...

muse/core/crdts/vclock.py — Vector Clock:

Required for causal ordering in distributed multi-agent scenarios. A vector clock tracks how many events each agent has seen, enabling detection of concurrent vs. causally-ordered writes. Necessary for correct LWW behavior and for RGA tie-breaking.

class VectorClock:
    """Causal clock for distributed agent writes."""
    def increment(self, agent_id: str) -> None: ...
    def merge(self, other: VectorClock) -> VectorClock: ...
    def happens_before(self, other: VectorClock) -> bool: ...
    def concurrent_with(self, other: VectorClock) -> bool: ...
    def to_dict(self) -> dict[str, int]: ...
    @classmethod
    def from_dict(cls, data: dict[str, int]) -> VectorClock: ...

6.3 CRDT-Aware Snapshot Format

When a plugin uses CRDT semantics, the SnapshotManifest carries additional metadata:

class CRDTSnapshotManifest(TypedDict):
    """Extended snapshot for CRDT-mode plugins."""
    files: dict[str, str]          # path → content hash (as before)
    domain: str
    vclock: dict[str, int]         # vector clock at snapshot time
    crdt_state: dict[str, str]     # path → CRDT state hash (separate from content)
    schema_version: Literal[1]

The crdt_state stores the CRDT metadata (tombstones, element IDs, timestamps) separately from the content hashes. This keeps the content-addressed object store valid while allowing CRDT state to accumulate.

6.4 CRDTPlugin Protocol Extension

class CRDTPlugin(MuseDomainPlugin, Protocol):
    """Extension of MuseDomainPlugin for CRDT-mode domains.

    Plugins implementing this protocol get convergent merge semantics:
    ``merge()`` is replaced by ``join()``, which always succeeds.
    """

    def crdt_schema(self) -> CRDTSchema:
        """Declare the CRDT types used for each dimension."""
        ...

    def join(
        self,
        a: CRDTSnapshotManifest,
        b: CRDTSnapshotManifest,
    ) -> CRDTSnapshotManifest:
        """Merge two snapshots by computing their lattice join.

        This operation is:
        - Commutative: join(a, b) = join(b, a)
        - Associative: join(join(a, b), c) = join(a, join(b, c))
        - Idempotent: join(a, a) = a

        These three properties guarantee convergence regardless of message
        order or delivery count.
        """
        ...

    def to_crdt_state(self, snapshot: StateSnapshot) -> CRDTSnapshotManifest:
        """Lift a plain snapshot into CRDT state representation."""
        ...

    def from_crdt_state(self, crdt: CRDTSnapshotManifest) -> StateSnapshot:
        """Materialise a CRDT state back to a plain snapshot."""
        ...

6.5 When to Use CRDT Mode

Scenario	Recommendation
Human-paced commits (once per hour/day)	Three-way merge (Phases 1–3) — richer conflict resolution
Many agents writing concurrently (once per second)	CRDT mode — no coordination needed
Mix (some slow human commits, some fast agent writes)	CRDT mode with LWW per-dimension
Simulation state frames (sequential, one writer)	Three-way merge
Shared genomics annotation (many simultaneous annotators)	CRDT OR-Set for annotation set
Collaborative score editing (DAW-style)	CRDT RGA for note sequences

The DomainSchema.merge_mode field controls which path the core engine takes. A plugin can declare merge_mode: "crdt" for some dimensions and fall back to "three_way" for others.

6.6 Phase 4 Test Cases

New test file: tests/test_crdts.py

# LWWRegister
test_lww_later_timestamp_wins
test_lww_same_timestamp_author_tiebreak
test_lww_join_is_commutative
test_lww_join_is_associative
test_lww_join_is_idempotent

# ORSet
test_or_set_add_survives_concurrent_remove
test_or_set_remove_observed_element_works
test_or_set_join_is_commutative
test_or_set_join_is_associative
test_or_set_join_is_idempotent

# RGA
test_rga_insert_after_none_is_prepend
test_rga_insert_at_end
test_rga_delete_marks_tombstone
test_rga_concurrent_insert_same_position_deterministic
test_rga_join_is_commutative
test_rga_join_is_associative
test_rga_join_is_idempotent
test_rga_to_sequence_excludes_tombstones
test_rga_round_trip_to_from_dict

# VectorClock
test_vclock_increment_own_agent
test_vclock_merge_takes_max_per_agent
test_vclock_happens_before_simple
test_vclock_concurrent_with_neither_dominates
test_vclock_idempotent_merge

# CRDTPlugin integration
test_crdt_plugin_join_produces_crdt_snapshot
test_crdt_plugin_join_commutes
test_crdt_join_via_core_merge_engine_uses_crdt_path
test_crdt_merge_never_produces_conflicts

6.7 Files Changed in Phase 4

File	Change
muse/core/crdts/__init__.py	New.
muse/core/crdts/lww_register.py	New.
muse/core/crdts/or_set.py	New.
muse/core/crdts/rga.py	New.
muse/core/crdts/aw_map.py	New.
muse/core/crdts/g_counter.py	New.
muse/core/crdts/vclock.py	New.
muse/domain.py	Add CRDTPlugin protocol, CRDTSnapshotManifest.
muse/core/schema.py	Add CRDTSchema. DomainSchema.merge_mode supports "crdt".
muse/core/merge_engine.py	Route to CRDT join when merge_mode == "crdt".
tests/test_crdts.py	New.

---

7. Cross-Cutting Concerns

7.1 Content-Addressed Object Store Compatibility

The object store (.muse/objects/SHA-256) requires no changes through all four phases. Phase 1's sub-element content_id fields in operation types reference objects already in the store. This means:

• Any binary element (a note, a nucleotide block, a mesh vertex group) stored via write_object(repo_root, sha256, bytes) is automatically deduplicated.
• The store scales to millions of fine-grained sub-elements without format changes.
• Pack files (future work) can be added without changing the protocol.

7.2 Commit Record Format Evolution

Each phase adds fields to CommitRecord. The commit record must carry a format_version field so future readers can understand what they're looking at:

class CommitRecord(TypedDict):
    commit_id: str
    snapshot_id: str
    parent_commit_id: str | None
    parent2_commit_id: str | None
    message: str
    author: str
    committed_at: str
    domain: str
    structured_delta: StructuredDelta | None    # Phase 1
    format_version: Literal[1, 2, 3, 4]        # tracks schema changes

Since we have no backwards compat requirement, format_version starts at 1 and each phase that changes the record bumps it. Old records without new fields are read with None defaults.

7.3 Wire Format for Agent-to-Agent Communication

Phase 4 introduces the scenario of multiple agents writing concurrently. This requires a wire format for exchanging operations and CRDT state. All types used (StructuredDelta, CRDTSnapshotManifest, VectorClock) are TypedDict and JSON-serialisable by design — this was deliberate. Any transport (HTTP, message queue, filesystem sync) can carry them without additional serialisation work.

7.4 Typing Constraints

All new types must satisfy the zero-Any constraint enforced by tools/typing_audit.py. Key design decisions that ensure this:

• DomainOp = InsertOp | DeleteOp | MoveOp | ReplaceOp | PatchOp — exhaustive union, no Any.
• ElementSchema = SequenceSchema | TreeSchema | TensorSchema | MapSchema | SetSchema — same.
• PatchOp.child_delta: StructuredDelta — the recursive field is typed, not dict[str, Any].
• All CRDT types carry concrete generic parameters.

The match statement in diff_by_schema uses exhaustive case matching on schema["kind"] literals — mypy can verify exhaustiveness.

7.5 Synchronous I/O Constraint

All algorithm implementations must remain synchronous. The LCS, tree-edit, and CRDT algorithms are all CPU-bound and complete in bounded time for bounded input sizes. No async, no await, no asyncio anywhere. If a domain's data is too large to diff synchronously, the plugin should chunk it — this is a domain concern, not a core engine concern.

---

8. Test Strategy

8.1 Test Pyramid

                    ┌─────────┐
                    │  E2E CLI │  (slow, few — cover user-visible behaviors)
                  ┌─┴─────────┴─┐
                  │ Integration  │  (medium — real components wired together)
                ┌─┴─────────────┴─┐
                │      Unit        │  (fast, many — every function in isolation)
                └──────────────────┘

Every new function gets a unit test before implementation (TDD). Every new interaction between two modules gets an integration test. Every new CLI behavior gets an E2E test.

8.2 Property-Based Testing for Algorithms

Correctness of LCS, tree-edit, and CRDTs is best verified with property-based tests (using hypothesis). Key properties:

LCS:

• Round-trip: apply(base, diff(base, target)) == target for all inputs
• Minimality: len(diff(a, b).ops) <= len(a) + len(b) (LCS is minimal)
• Identity: diff(a, a).ops == []

CRDT lattice laws (all must hold for all inputs):

• Commutativity: join(a, b) == join(b, a)
• Associativity: join(join(a, b), c) == join(a, join(b, c))
• Idempotency: join(a, a) == a

OT transform (Phase 3):

• Diamond property: apply(apply(base, a), transform(a, b)[1]) == apply(apply(base, b), transform(a, b)[0])

8.3 Regression Test Naming Convention

Every bug fix gets a regression test named:

test_<what_broke>_<correct_behavior>

Example: test_concurrent_note_insert_same_bar_does_not_lose_notes

8.4 Test Isolation

All tests must be hermetic — no shared mutable state, no real filesystem without tmp_path fixture. Algorithm tests (LCS, tree-edit, CRDT) are purely in-memory and have no filesystem dependencies at all.

---

9. Implementation Order and Dependencies

Phase 1 ──────────────────────────────────────────────────────────► Phase 2
  │  Typed delta algebra                                               │
  │  StructuredDelta replaces DeltaManifest                           │
  │  Music plugin: file→InsertOp, MIDI→PatchOp                        │
  │  midi_diff.py (LCS on note sequences)                             │
  │                                                                    │
  │  DEPENDS ON: nothing (self-contained)                             │  Domain schema declaration
  │                                                                    │  diff_algorithms/ library
  ▼                                                                    │  schema() on protocol
Phase 3 ◄────────────────────────────────────────────────────────────┘
  │  Operation-level merge engine
  │  ops_commute(), transform(), merge_op_lists()
  │  Core engine routes to op_transform when StructuredDelta available
  │
  │  DEPENDS ON: Phase 1 (needs StructuredDelta) + Phase 2 (needs position metadata)
  │
  ▼
Phase 4
  CRDT primitive library (LWWRegister, ORSet, RGA, AWMap, VectorClock)
  CRDTPlugin protocol extension
  Core merge engine: merge_mode == "crdt" → join()

  DEPENDS ON: Phase 1–3 complete

Critical path: Phase 1 → Phase 2 → Phase 3 → Phase 4. Each phase requires the previous. Do not skip phases or reorder.

Parallel work possible within phases:

• Phase 1: midi_diff.py can be implemented in parallel with the type system changes.
• Phase 2: lcs.py, tree_edit.py, numerical.py can be implemented in parallel.
• Phase 4: All CRDT types (rga.py, or_set.py, etc.) are independent and can be built in parallel.

9.1 Rough Timeline

Phase	Calendar estimate	Primary difficulty
Phase 1	2–3 weeks	Protocol change propagation; Myers LCS for MIDI
Phase 2	3–4 weeks	Zhang-Shasha implementation; schema dispatch typing
Phase 3	4–6 weeks	OT transform correctness; position adjustment cascades
Phase 4	6–8 weeks	CRDT correctness proofs; vector clock integration
Total	15–21 weeks

Phase 3 is the hardest. The OT transform correctness for all op-pair combinations is subtle and requires exhaustive property testing with hypothesis. Budget extra time there.

9.2 Definition of Done Per Phase

Phase 1 done when:

• [ ] DeltaManifest is gone; StructuredDelta is the only StateDelta
• [ ] Music plugin's diff() returns StructuredDelta with PatchOp for .mid files
• [ ] muse show <commit> displays note-level diff summary
• [ ] mypy muse/ zero errors
• [ ] python tools/typing_audit.py --dirs muse/ tests/ --max-any 0 zero violations
• [ ] All new test cases pass

Phase 2 done when:

• [ ] schema() is on the MuseDomainPlugin protocol
• [ ] Music plugin returns a complete DomainSchema
• [ ] diff_algorithms/ contains LCS, tree-edit, numerical, set implementations
• [ ] All four algorithms have property-based tests passing
• [ ] diff_by_schema dispatch is exhaustively typed (no Any, mypy verified)

Phase 3 done when:

• [ ] ops_commute() correctly handles all 25 op-pair combinations
• [ ] transform() passes the diamond property for all commuting pairs
• [ ] Music plugin: inserting notes at non-overlapping bars never conflicts
• [ ] Core merge engine uses merge_op_lists when StructuredDelta is available
• [ ] Property tests verify OT correctness on randomly generated op sequences

Phase 4 done when:

• [ ] All five CRDT types pass the three lattice laws (property tests via hypothesis)
• [ ] VectorClock correctly identifies concurrent vs. causally-ordered events
• [ ] A MIDI plugin in CRDT mode never produces a MergeResult.conflicts entry
• [ ] The core merge engine's CRDT path is exercised by integration tests
• [ ] CRDTPlugin protocol is verified by a runtime_checkable assertion

---

End of plan. Implementation begins at Phase 1. Each phase produces a proposal against dev with its own verification checklist completed.