docs/architecture/architecture-plan.md · cgcardona/muse

- **Plugin protocol boundary** — `MuseDomainPlugin` is the right abstraction. Core engine is domain-agnostic. This must remain true through every phase.

28

- **BFS LCA merge-base finder** — mathematically correct for DAG commit graphs.

29

- **File-level three-way merge** — correct for the current granularity.

30

- **`.museattributes` strategy system** — the right place for declarative per-path merge policy.

31

32

### What is genuinely limited

33

34

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:

35

36

```

37

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

38

```

39

40

`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.

41

42

**Consequences of this ceiling:**

43

44

| Scenario | Current behavior | Correct behavior |

45

|---|---|---|

46

| Insert note at bar 12 on branch A; insert note at bar 45 on branch B | File-level conflict | Auto-merge: non-overlapping positions |

47

| Insert nucleotide at position 1000 on branch A; insert at position 5000 on branch B | File-level conflict | Auto-merge |

48

| Two agents edit different nodes in the same scene graph | File-level conflict | Auto-merge |

49

| `muse show <commit>` | "tracks/drums.mid modified" | "bar 12: C4 quarter inserted; velocity 80→90" |

50

| Every new domain plugin | Must implement its own merge engine | Gets LCS/tree-edit/numerical for free from core |

51

52

The music 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

57

58

A universal multidimensional VCS where:

59

60

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.

61

62

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

63

64

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

65

66

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

67

68

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

73

74

**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.

75

76

**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.

81

82

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.

83

84

### 3.2 New Type System in `muse/domain.py`

85

86

Replace `DeltaManifest` with a composable operation-tree type system:

87

88

```python

89

# ---------------------------------------------------------------------------

90

# Atomic position types

91

# ---------------------------------------------------------------------------

92

93

# A DomainAddress is a path within a domain's object graph.

94

# - For file-level ops: a POSIX workspace path ("tracks/drums.mid")

95

# - For sub-file ops: a JSON-pointer fragment within that file ("/notes/42")

96

# - Plugins define what addresses mean in their domain.

97

DomainAddress = str

98

99

# ---------------------------------------------------------------------------

100

# Atomic operation types

101

# ---------------------------------------------------------------------------

102

103

class InsertOp(TypedDict):

104

"""An element was inserted into an ordered or unordered collection."""

105

op: Literal["insert"]

106

address: DomainAddress # where in the structure

107

position: int | None # index for ordered sequences; None for sets

108

content_id: str # SHA-256 of inserted content (stored in object store)

109

content_summary: str # human-readable description for display

110

111

class DeleteOp(TypedDict):

112

"""An element was removed."""

113

op: Literal["delete"]

114

address: DomainAddress

115

position: int | None

116

content_id: str # SHA-256 of removed content

117

content_summary: str

118

119

class MoveOp(TypedDict):

120

"""An element was repositioned within an ordered sequence."""

121

op: Literal["move"]

122

address: DomainAddress

from_position: int

to_position: int

content_id: str

class ReplaceOp(TypedDict):

128

"""An element's value changed (atomic, leaf-level)."""

129

op: Literal["replace"]

130

address: DomainAddress

position: int | None

old_content_id: str

new_content_id: str

old_summary: str

new_summary: str

class PatchOp(TypedDict):

138

"""A nested structure was modified; carries a child StructuredDelta."""

139

op: Literal["patch"]

140

address: DomainAddress # the container being patched

141

child_delta: StructuredDelta # recursive — describes what changed inside

142

143

# The union of all operation types

144

DomainOp = InsertOp | DeleteOp | MoveOp | ReplaceOp | PatchOp

145

146

# ---------------------------------------------------------------------------

147

# The new StateDelta

148

# ---------------------------------------------------------------------------

149

150

class StructuredDelta(TypedDict):

151

"""Rich, composable delta between two domain snapshots.

152

153

``ops`` is an ordered list of operations that transforms ``base`` into

154

``target`` when applied in sequence. The core engine treats this as an

155

opaque blob for storage and display. The merge engine in Phase 3 will

156

reason over it for commutativity.

157

158

``summary`` is a precomputed human-readable string for ``muse show``.

159

Plugins compute this because only they understand their domain semantics.

"""

domain: str

ops: list[DomainOp]

summary: str # "3 notes added, 1 bar restructured"

164

165

# StateDelta is now StructuredDelta. DeltaManifest is gone.

166

StateDelta = StructuredDelta

167

```

168

169

**Key design decisions:**

170

171

- `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.

172

- `content_summary` is plugin-computed human-readable text. The core engine uses it verbatim in `muse show`. Plugins are responsible for making it meaningful.

173

- `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.

174

- `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.

175

176

### 3.3 Updated Plugin Protocol

177

178

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

179

180

```python

181

def diff(self, base: StateSnapshot, target: StateSnapshot) -> StateDelta:

182

"""Compute the structured delta between two snapshots.

183

184

Returns a ``StructuredDelta`` where ``ops`` is a minimal list of

185

operations that transforms ``base`` into ``target``. Plugins should:

186

187

1. Compute ops at the finest granularity they can interpret.

188

2. Assign meaningful ``content_summary`` strings to each op.

189

3. Store any new sub-element content in the object store if ``repo_root``

190

is available; otherwise use deterministic synthetic IDs.

191

4. Compute a human-readable ``summary`` across all ops.

192

193

The core engine stores this delta alongside the commit record so that

194

``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:

200

201

```python

202

def apply(self, delta: StateDelta, live_state: LiveState) -> LiveState:

203

"""Apply a structured delta to produce a new live state.

204

205

Plugins must implement application of all four op types. For plugins

206

where full in-memory application is impractical (e.g. large binary

207

files), ``live_state`` should be a ``pathlib.Path`` and the plugin

208

should apply ops to disk files directly.

"""

...

```

### 3.4 Updated `DriftReport`

214

215

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

```python

@dataclass

class DriftReport:

has_drift: bool

summary: str = ""

delta: StateDelta = field(default_factory=lambda: StructuredDelta(

223

domain="", ops=[], summary="working tree clean",

))

```

### 3.5 Updated `MergeResult`

228

229

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

```python

@dataclass

class MergeResult:

merged: StateSnapshot

235

conflicts: list[str] = field(default_factory=list)

236

applied_strategies: dict[str, str] = field(default_factory=dict)

237

dimension_reports: dict[str, dict[str, str]] = field(default_factory=dict)

238

op_log: list[DomainOp] = field(default_factory=list) # NEW

239

240

@property

241

def is_clean(self) -> bool:

242

return len(self.conflicts) == 0

243

```

244

245

### 3.6 Updated Music Plugin

246

247

The music 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:

248

249

```python

250

def diff(self, base: StateSnapshot, target: StateSnapshot) -> StateDelta:

251

base_files = base["files"]

252

target_files = target["files"]

253

base_paths = set(base_files)

254

target_paths = set(target_files)

255

256

ops: list[DomainOp] = []

257

258

for path in sorted(target_paths - base_paths):

ops.append(InsertOp(

op="insert",

address=path,

position=None, # file collection is unordered

263

content_id=target_files[path],

264

content_summary=f"new file: {path}",

265

))

266

267

for path in sorted(base_paths - target_paths):

ops.append(DeleteOp(

op="delete",

address=path,

position=None,

content_id=base_files[path],

273

content_summary=f"deleted: {path}",

274

))

275

276

for path in sorted(p for p in base_paths & target_paths

277

if base_files[p] != target_files[p]):

278

if path.lower().endswith(".mid"):

279

# Attempt deep MIDI diff → PatchOp with note-level child ops

280

child_delta = _diff_midi_deep(base_files[path], target_files[path])

281

if child_delta is not None:

ops.append(PatchOp(

op="patch",

address=path,

child_delta=child_delta,

286

))

287

continue

288

# Fallback: atomic replace

289

ops.append(ReplaceOp(

op="replace",

address=path,

position=None,

old_content_id=base_files[path],

294

new_content_id=target_files[path],

295

old_summary=f"{path} (prev)",

296

new_summary=f"{path} (new)",

297

))

298

299

summary = _summarise_ops(ops)

300

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

301

```

302

303

`_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.

304

305

### 3.7 Serialisation Contract

306

307

`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.

308

309

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.

310

311

### 3.8 Phase 1 Test Cases

312

313

**New test file: `tests/test_structured_delta.py`**

314

315

```

316

test_insert_op_round_trips_json

317

test_delete_op_round_trips_json

318

test_move_op_round_trips_json

319

test_replace_op_round_trips_json

320

test_patch_op_with_child_delta_round_trips_json

321

test_structured_delta_satisfies_state_delta_type

322

test_music_plugin_diff_returns_structured_delta

323

test_music_plugin_diff_file_add_produces_insert_op

324

test_music_plugin_diff_file_remove_produces_delete_op

325

test_music_plugin_diff_file_modify_produces_replace_op

326

test_music_plugin_diff_midi_modify_produces_patch_op_with_child_ops

327

test_drift_report_delta_is_structured_delta

328

test_muse_show_displays_structured_summary

329

test_muse_diff_displays_per_op_lines

330

```

331

332

**New test file: `tests/test_midi_diff.py`**

333

334

```

335

test_midi_diff_empty_to_single_note_is_one_insert

336

test_midi_diff_single_note_to_empty_is_one_delete

337

test_midi_diff_note_velocity_change_is_replace

338

test_midi_diff_note_inserted_in_middle_identified_correctly

339

test_midi_diff_note_transposition_identified_as_replace

340

test_midi_diff_no_change_returns_empty_ops

341

test_midi_diff_summary_string_is_human_readable

342

```

343

344

### 3.9 Files Changed in Phase 1

| File | Change |

|---|---|

| `muse/domain.py` | Replace `DeltaManifest`/`StateDelta` with `DomainOp` union + `StructuredDelta`. Update `DriftReport`, `MergeResult`. |

349

| `muse/core/store.py` | `CommitRecord` gains `structured_delta: StructuredDelta \| None` field. |

350

| `muse/plugins/music/plugin.py` | `diff()` returns `StructuredDelta`. `apply()` handles `StructuredDelta`. |

351

| `muse/plugins/music/midi_diff.py` | **New.** Myers LCS on MIDI note sequences → `StructuredDelta`. |

352

| `muse/cli/commands/show.py` | Display `structured_delta.summary` and per-op lines. |

353

| `muse/cli/commands/diff.py` | Display structured diff output. |

354

| `tests/test_structured_delta.py` | **New.** All Phase 1 tests. |

355

| `tests/test_midi_diff.py` | **New.** MIDI diff algorithm tests. |

356

| `tests/test_music_plugin.py` | Update to assert `StructuredDelta` return type. |

---

## 4. Phase 2 — Domain Schema & Diff Algorithm Library

361

362

**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.

363

364

**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.

369

370

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.

371

372

### 4.2 Domain Schema Types

373

374

**New file: `muse/core/schema.py`**

375

376

```python

377

"""Domain schema declaration types.

378

379

A plugin implements ``schema()`` returning a ``DomainSchema`` to declare

380

the structural shape of its data. The core engine uses this declaration

381

to drive the correct diff algorithm, validate delta types, and offer

382

informed merge conflict messages.

383

"""

384

from __future__ import annotations

385

from typing import Literal, TypedDict

386

387

388

# ---------------------------------------------------------------------------

389

# Primitive element schemas

390

# ---------------------------------------------------------------------------

391

392

class SequenceSchema(TypedDict):

393

"""Ordered sequence of homogeneous elements (LCS-diffable)."""

394

kind: Literal["sequence"]

395

element_type: str # e.g. "note", "nucleotide", "frame", "voxel"

396

identity: Literal["by_id", "by_position", "by_content"]

397

diff_algorithm: Literal["lcs", "myers", "patience"]

398

# Optional: alphabet constraint for validation

399

alphabet: list[str] | None

400

401

class TreeSchema(TypedDict):

402

"""Hierarchical tree structure (tree-edit-diffable)."""

403

kind: Literal["tree"]

404

node_type: str # e.g. "scene_node", "xml_element", "ast_node"

405

diff_algorithm: Literal["zhang_shasha", "gumtree"]

406

407

class TensorSchema(TypedDict):

408

"""N-dimensional numerical array (sparse-numerical-diffable)."""

409

kind: Literal["tensor"]

410

dtype: Literal["float32", "float64", "int8", "int16", "int32", "int64"]

411

rank: int # number of dimensions

412

epsilon: float # tolerance: |a - b| < epsilon → "unchanged"

413

diff_mode: Literal["sparse", "block", "full"]

414

415

class MapSchema(TypedDict):

416

"""Key-value map with known or dynamic keys."""

417

kind: Literal["map"]

418

key_type: str

419

value_schema: ElementSchema # recursive

420

identity: Literal["by_key"]

421

422

class SetSchema(TypedDict):

423

"""Unordered collection of unique elements (current hash-set approach)."""

424

kind: Literal["set"]

425

element_type: str

426

identity: Literal["by_content", "by_id"]

427

428

# The union of all element schema types

429

ElementSchema = SequenceSchema | TreeSchema | TensorSchema | MapSchema | SetSchema

430

431

432

# ---------------------------------------------------------------------------

433

# Dimension spec — a named structural sub-dimension

434

# ---------------------------------------------------------------------------

435

436

class DimensionSpec(TypedDict):

437

"""A named semantic sub-dimension of the domain's state.

438

439

For music: "melodic", "harmonic", "dynamic", "structural".

440

For genomics: "exons", "introns", "promoters", "metadata".

441

For 3D spatial: "geometry", "materials", "lighting", "animation".

442

443

Each dimension can use a different element schema and diff algorithm.

444

The merge engine can merge dimensions independently.

"""

name: str

description: str

schema: ElementSchema

449

# Whether conflicts in this dimension block the whole file's merge

450

# or are resolved independently.

451

independent_merge: bool

452

453

454

# ---------------------------------------------------------------------------

455

# Top-level domain schema

456

# ---------------------------------------------------------------------------

457

458

class DomainSchema(TypedDict):

459

"""Complete structural declaration for a domain plugin.

460

461

Returned by ``MuseDomainPlugin.schema()``. The core engine reads this

462

once at plugin registration time and uses it to:

463

464

1. Select the correct diff algorithm for each dimension.

465

2. Generate typed delta validation.

466

3. Provide informed conflict messages (citing dimension names).

467

4. Route to CRDT merge if ``merge_mode`` is ``"crdt"`` (Phase 4).

"""

domain: str

description: str

# Dimensions that make up this domain's state.

472

# The core engine merges each independently when possible.

473

dimensions: list[DimensionSpec]

474

# The top-level collection of domain objects (e.g. files, sequences, nodes)

475

top_level: ElementSchema

476

# Which merge strategy to use at the top level

477

merge_mode: Literal["three_way", "crdt"] # "crdt" is Phase 4

478

# Version of the schema format itself (for future migrations)

479

schema_version: Literal[1]

480

```

481

482

### 4.3 Schema Method Added to Plugin Protocol

483

484

```python

485

def schema(self) -> DomainSchema:

486

"""Declare the structural schema of this domain's state.

487

488

The core engine calls this once at startup. Plugins should return a

489

stable, deterministic ``DomainSchema``. This declaration drives diff

490

algorithm selection, delta validation, and conflict messaging.

491

492

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

"""

...

```

### 4.4 Example Schema Declarations

**Music plugin:**

```python

def schema(self) -> DomainSchema:

503

return DomainSchema(

504

domain="music",

505

description="MIDI and audio file versioning with note-level diff",

506

top_level=SetSchema(

507

kind="set",

508

element_type="audio_file",

509

identity="by_content",

),

dimensions=[

DimensionSpec(

name="melodic",

description="Note pitches and durations over time",

515

schema=SequenceSchema(

516

kind="sequence",

517

element_type="note_event",

518

identity="by_position",

519

diff_algorithm="lcs",

520

alphabet=None,

521

),

522

independent_merge=True,

),

DimensionSpec(

name="harmonic",

description="Chord progressions and key signatures",

527

schema=SequenceSchema(

528

kind="sequence",

529

element_type="chord_event",

530

identity="by_position",

531

diff_algorithm="lcs",

532

alphabet=None,

533

),

534

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

544

diff_mode="sparse",

545

),

546

independent_merge=True,

),

DimensionSpec(

name="structural",

description="Track layout, time signatures, tempo map",

551

schema=TreeSchema(

552

kind="tree",

553

node_type="track_node",

554

diff_algorithm="zhang_shasha",

555

),

556

independent_merge=False, # structural changes block all dimensions

557

),

558

],

559

merge_mode="three_way",

schema_version=1,

)

```

**Hypothetical genomics plugin:**

565

566

```python

567

def schema(self) -> DomainSchema:

568

return DomainSchema(

569

domain="genomics",

570

description="DNA/RNA sequence versioning at nucleotide resolution",

571

top_level=MapSchema(

572

kind="map",

573

key_type="sequence_id", # e.g. chromosome name

574

value_schema=SequenceSchema(

575

kind="sequence",

576

element_type="nucleotide",

577

identity="by_position",

578

diff_algorithm="myers",

579

alphabet=["A", "T", "C", "G", "U", "N", "-"],

),

identity="by_key",

),

dimensions=[

DimensionSpec(

name="coding_regions",

586

description="Exons and coding sequence",

587

schema=SequenceSchema(

588

kind="sequence",

589

element_type="nucleotide",

590

identity="by_position",

591

diff_algorithm="myers",

592

alphabet=["A", "T", "C", "G", "N"],

593

),

594

independent_merge=True,

),

DimensionSpec(

name="regulatory",

description="Promoters, enhancers, splice sites",

599

schema=SetSchema(

600

kind="set",

601

element_type="regulatory_element",

602

identity="by_id",

603

),

604

independent_merge=True,

),

DimensionSpec(

name="metadata",

description="Annotations, quality scores, provenance",

609

schema=MapSchema(

610

kind="map",

611

key_type="annotation_key",

612

value_schema=TensorSchema(

kind="tensor",

dtype="float32",

rank=1,

epsilon=0.001,

diff_mode="sparse",

),

identity="by_key",

),

independent_merge=True,

622

),

623

],

624

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.

630

631

### 4.5 Diff Algorithm Library

632

633

**New directory: `muse/core/diff_algorithms/`**

634

635

```

636

muse/core/diff_algorithms/

637

__init__.py → dispatch function

638

lcs.py → Myers / patience diff for ordered sequences

639

tree_edit.py → Zhang-Shasha tree edit distance

640

numerical.py → sparse numerical diff for tensors

641

set_ops.py → hash-set algebra (current approach, extracted)

642

```

643

644

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

```python

def diff_by_schema(

schema: ElementSchema,

649

base: SequenceData | TreeData | TensorData | SetData | MapData,

650

target: SequenceData | TreeData | TensorData | SetData | MapData,

*,

domain: str,

address: str = "",

) -> StructuredDelta:

655

"""Dispatch to the correct diff algorithm based on ``schema.kind``."""

656

match schema["kind"]:

657

case "sequence":

658

return lcs.diff(schema, base, target, domain=domain, address=address)

659

case "tree":

660

return tree_edit.diff(schema, base, target, domain=domain, address=address)

661

case "tensor":

662

return numerical.diff(schema, base, target, domain=domain, address=address)

663

case "set":

664

return set_ops.diff(schema, base, target, domain=domain, address=address)

665

case "map":

666

return _diff_map(schema, base, target, domain=domain, address=address)

667

```

668

669

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

670

671

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.

672

673

Key functions:

674

- `myers_ses(base: list[T], target: list[T]) -> list[EditOp]` — shortest edit script

675

- `detect_moves(inserts: list[InsertOp], deletes: list[DeleteOp]) -> list[MoveOp]` — post-process

676

- `diff(schema: SequenceSchema, base: list[T], target: list[T], ...) -> StructuredDelta`

677

678

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

679

680

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

681

682

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.

683

684

Key functions:

685

- `zhang_shasha(base: TreeNode, target: TreeNode) -> list[TreeEditOp]` — edit script

686

- `diff(schema: TreeSchema, base: TreeNode, target: TreeNode, ...) -> StructuredDelta`

687

688

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

689

690

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:

691

692

1. Compares element-wise with `schema.epsilon` tolerance.

693

2. Returns `ReplaceOp` only for elements where `|base[i] - target[i]| >= epsilon`.

694

3. In `"sparse"` mode: emits one `ReplaceOp` per changed element (good for sparse changes).

695

4. In `"block"` mode: groups adjacent changes into contiguous range ops (good for dense changes).

696

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).

697

698

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

699

700

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.

701

702

### 4.6 Plugin Registry Gains Schema Lookup

703

704

**`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.

705

706

### 4.7 Phase 2 Test Cases

707

708

**New test file: `tests/test_diff_algorithms.py`**

```

# LCS / Myers

test_lcs_empty_to_sequence_is_all_inserts

713

test_lcs_sequence_to_empty_is_all_deletes

714

test_lcs_identical_sequences_returns_no_ops

715

test_lcs_single_insert_in_middle

716

test_lcs_single_delete_in_middle

717

test_lcs_move_detected_from_delete_plus_insert

718

test_lcs_transposition_of_two_elements

719

test_lcs_patience_mode_handles_repeated_elements

720

test_lcs_produces_valid_structured_delta

721

722

# Tree edit

723

test_tree_edit_leaf_relabel_is_replace

724

test_tree_edit_node_insert

725

test_tree_edit_node_delete

726

test_tree_edit_subtree_move

727

test_tree_edit_identical_trees_returns_no_ops

728

test_tree_edit_produces_valid_structured_delta

729

730

# Numerical

731

test_numerical_within_epsilon_returns_no_ops

732

test_numerical_outside_epsilon_returns_replace

733

test_numerical_sparse_mode_one_op_per_element

734

test_numerical_block_mode_groups_adjacent

735

test_numerical_full_mode_single_op

736

test_numerical_produces_valid_structured_delta

737

738

# Set ops

739

test_set_diff_add_returns_insert

740

test_set_diff_remove_returns_delete

741

test_set_diff_no_change_returns_empty

742

test_set_diff_produces_valid_structured_delta

743

744

# Schema dispatch

745

test_dispatch_sequence_schema_calls_lcs

746

test_dispatch_tree_schema_calls_zhang_shasha

747

test_dispatch_tensor_schema_calls_numerical

748

test_dispatch_set_schema_calls_set_ops

749

test_dispatch_map_schema_recurses

750

```

751

752

**New test file: `tests/test_domain_schema.py`**

753

754

```

755

test_music_plugin_schema_returns_domain_schema

756

test_music_plugin_schema_has_four_dimensions

757

test_music_plugin_schema_melodic_dimension_is_sequence

758

test_music_plugin_schema_structural_dimension_is_tree

759

test_music_plugin_schema_dynamic_dimension_is_tensor

760

test_schema_round_trips_json

761

test_schema_version_is_1

762

test_plugin_registry_schema_lookup

763

```

764

765

### 4.8 Files Changed in Phase 2

| File | Change |

|---|---|

| `muse/core/schema.py` | **New.** All schema `TypedDict` types. |

770

| `muse/core/diff_algorithms/__init__.py` | **New.** Schema-driven dispatch. |

771

| `muse/core/diff_algorithms/lcs.py` | **New.** Myers + patience diff. |

772

| `muse/core/diff_algorithms/tree_edit.py` | **New.** Zhang-Shasha implementation. |

773

| `muse/core/diff_algorithms/numerical.py` | **New.** Sparse/block/full tensor diff. |

774

| `muse/core/diff_algorithms/set_ops.py` | **New.** Extracted from `merge_engine.py`. |

775

| `muse/domain.py` | Add `schema()` to `MuseDomainPlugin` protocol. |

776

| `muse/core/plugin_registry.py` | Add `schema_for(domain) -> DomainSchema \| None`. |

777

| `muse/plugins/music/plugin.py` | Implement `schema()` returning full `DomainSchema`. `diff()` dispatches through `diff_by_schema`. |

778

| `tests/test_diff_algorithms.py` | **New.** |

779

| `tests/test_domain_schema.py` | **New.** |

---

## 5. Phase 3 — Operation-Level Merge Engine

784

785

**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.

786

787

**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.

792

793

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.

794

795

### 5.2 Commutativity Rules

796

797

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:

798

799

| Op A | Op B | Commute? | Condition |

|---|---|---|---|

| `DeleteOp(addr=A)` | `DeleteOp(addr=B)` | **Yes** | `A ≠ B` |

805

806

| `ReplaceOp(addr=A)` | `ReplaceOp(addr=B)` | **Yes** | `A ≠ B` |

807

808

| `MoveOp(from=i)` | `MoveOp(from=j)` | **Yes** | `i ≠ j` |

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.

814

815

### 5.3 Operation Transformer Functions

816

817

**New file: `muse/core/op_transform.py`**

818

819

```python

820

"""Operational transformation for Muse domain operations.

821

822

Implements the commutativity rules that let the merge engine determine

823

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.

828

- ``transform(a, b)`` — Return a', b' such that applying a then b' = applying b then a'.

829

- ``merge_op_lists(base_ops, ours_ops, theirs_ops)`` → MergeOpsResult

830

"""

831

from __future__ import annotations

832

from dataclasses import dataclass, field

833

from muse.domain import DomainOp, InsertOp, DeleteOp, MoveOp, ReplaceOp, PatchOp

@dataclass

class MergeOpsResult:

838

"""Result of merging two operation lists against a common base."""

839

merged_ops: list[DomainOp] = field(default_factory=list)

840

conflict_ops: list[tuple[DomainOp, DomainOp]] = field(default_factory=list)

841

842

@property

843

def is_clean(self) -> bool:

844

return len(self.conflict_ops) == 0

845

846

847

def ops_commute(a: DomainOp, b: DomainOp) -> bool:

848

"""Return True if operations A and B commute (auto-mergeable)."""

849

...

850

851

def transform(a: DomainOp, b: DomainOp) -> tuple[DomainOp, DomainOp]:

852

"""Return (a', b') such that a ∘ b' = b ∘ a'.

853

854

This is the core OT transform function. When two operations a and b

855

are generated concurrently against the same base, transform returns

856

adjusted versions that can be applied sequentially to achieve the same

final state.

"""

...

def merge_op_lists(

base_ops: list[DomainOp],

863

ours_ops: list[DomainOp],

864

theirs_ops: list[DomainOp],

865

) -> MergeOpsResult:

866

"""Three-way merge at operation granularity.

867

868

Applies commutativity rules to detect which pairs of operations truly

869

conflict. Non-conflicting pairs are auto-merged by applying OT transform.

870

Conflicting pairs are collected in ``conflict_ops`` for plugin resolution.

"""

...

```

### 5.4 Updated Core Merge Engine

876

877

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

878

879

```python

880

def merge_structured(

881

base_delta: StructuredDelta,

882

ours_delta: StructuredDelta,

883

theirs_delta: StructuredDelta,

884

) -> MergeOpsResult:

885

"""Merge two structured deltas against a common base delta.

886

887

Uses ``op_transform.merge_op_lists`` for operation-level conflict

888

detection. Falls back to file-level path detection for ops that do

889

not carry position information (e.g. SetSchema domains).

890

"""

891

from muse.core.op_transform import merge_op_lists

892

return merge_op_lists(base_delta["ops"], ours_delta["ops"], theirs_delta["ops"])

893

```

894

895

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.

896

897

### 5.5 Plugin Protocol Gains `merge_ops`

898

899

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

```python

def merge_ops(

self,

base: StateSnapshot,

ours_ops: list[DomainOp],

906

theirs_ops: list[DomainOp],

907

*,

908

repo_root: pathlib.Path | None = None,

909

) -> MergeResult:

910

"""Merge two op lists against base, using domain-specific conflict resolution.

911

912

The core engine calls this when both branches have produced

913

``StructuredDelta`` from ``diff()``. The plugin may use

914

``muse.core.op_transform.merge_op_lists`` as the foundation and

915

add domain-specific resolution on top (e.g. checking ``.museattributes``).

916

917

If not implemented, the core engine falls back to the existing

918

three-way file-level merge via ``merge()``.

"""

...

```

### 5.6 Position Adjustment After Transform

924

925

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]

930

Theirs: insert Y at position 2 → [A, B, Y, C]

931

932

After transform:

933

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

934

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

935

```

936

937

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.

938

939

### 5.7 Phase 3 Test Cases

940

941

**New test file: `tests/test_op_transform.py`**

942

943

```

944

# Commutativity oracle

945

test_commute_inserts_at_different_positions_is_true

946

test_commute_inserts_at_same_position_is_false

947

test_commute_deletes_at_different_addresses_is_true

948

test_commute_consensus_delete_is_true

949

test_commute_replaces_at_different_addresses_is_true

950

test_commute_replaces_at_same_address_is_false

951

test_commute_move_and_delete_same_position_is_false

952

test_commute_patch_at_different_addresses_is_true

953

test_commute_patch_at_same_address_recurses_children

954

955

# OT transform function

956

test_transform_two_inserts_adjusts_positions_correctly

957

test_transform_insert_and_delete_produces_adjusted_ops

958

test_transform_identity_when_ops_commute

959

960

# Three-way merge

961

test_merge_op_lists_clean_non_overlapping

962

test_merge_op_lists_same_op_both_sides_is_idempotent

963

test_merge_op_lists_conflict_same_position_insert

964

test_merge_op_lists_conflict_same_address_replace

965

test_merge_op_lists_consensus_delete_both_sides

966

test_merge_op_lists_nested_patch_recurses

967

test_merge_op_lists_position_adjustment_cascades

968

test_merge_op_lists_empty_one_side_applies_other

969

test_merge_op_lists_both_empty_returns_base

970

971

# Integration: merge engine uses op_transform when structured deltas available

972

test_merge_engine_uses_op_transform_for_structured_deltas

973

test_merge_engine_falls_back_to_file_level_without_structured_deltas

974

test_full_merge_non_overlapping_note_inserts_auto_merges

975

test_full_merge_same_note_insert_produces_conflict

976

```

977

978

### 5.8 Files Changed in Phase 3

| File | Change |

|---|---|

| `muse/core/op_transform.py` | **New.** `ops_commute`, `transform`, `merge_op_lists`. |

983

| `muse/core/merge_engine.py` | Add `merge_structured()`. Fallback logic preserved. |

984

| `muse/domain.py` | Add optional `merge_ops()` to `MuseDomainPlugin` protocol. |

985

| `muse/plugins/music/plugin.py` | Implement `merge_ops()` using `op_transform`. |

986

| `tests/test_op_transform.py` | **New.** |

987

| `tests/test_core_merge_engine.py` | Add structured-delta merge tests. |

---

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

992

993

**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.

994

995

**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.

1000

1001

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).

1002

1003

This is the endgame for the multi-agent scenario.

1004

1005

### 6.2 CRDT Primitive Library

1006

1007

**New directory: `muse/core/crdts/`**

```

muse/core/crdts/

__init__.py

lww_register.py → Last-Write-Wins Register

1013

or_set.py → Observed-Remove Set

1014

rga.py → Replicated Growable Array (ordered sequences)

1015

aw_map.py → Add-Wins Map

1016

g_counter.py → Grow-only Counter

1017

vclock.py → Vector Clock (causal ordering)

1018

```

1019

1020

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

1021

1022

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.

1023

1024

```python

1025

class LWWValue(TypedDict):

1026

value: str # JSON-serialisable value

1027

timestamp: float # Unix timestamp or logical clock

1028

author: str # Agent ID for tiebreaking

1029

1030

class LWWRegister:

1031

"""A register where the last write (by timestamp) wins on merge."""

1032

def read(self) -> str: ...

1033

def write(self, value: str, timestamp: float, author: str) -> None: ...

1034

def join(self, other: LWWRegister) -> LWWRegister: ... # convergent merge

1035

def to_dict(self) -> LWWValue: ...

1036

@classmethod

1037

def from_dict(cls, data: LWWValue) -> LWWRegister: ...

1038

```

1039

1040

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

1041

1042

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.

1043

1044

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

1045

1046

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.

1047

1048

```python

1049

class RGAElement(TypedDict):

1050

id: str # stable unique ID: f"{timestamp}@{author}"

1051

value: str # content hash of element (references object store)

1052

deleted: bool # tombstone — never actually removed, marked deleted

1053

1054

class RGA:

1055

"""Replicated Growable Array — CRDT for ordered sequences."""

1056

def insert(self, after_id: str | None, element: RGAElement) -> None: ...

1057

def delete(self, element_id: str) -> None: ...

1058

def join(self, other: RGA) -> RGA: ... # always succeeds, no conflicts

1059

def to_sequence(self) -> list[str]: ... # materialise visible elements

1060

def to_dict(self) -> list[RGAElement]: ...

1061

@classmethod

1062

def from_dict(cls, data: list[RGAElement]) -> RGA: ...

1063

```

1064

1065

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

1066

1067

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.

```python

class VectorClock:

"""Causal clock for distributed agent writes."""

1072

def increment(self, agent_id: str) -> None: ...

1073

def merge(self, other: VectorClock) -> VectorClock: ...

1074

def happens_before(self, other: VectorClock) -> bool: ...

1075

def concurrent_with(self, other: VectorClock) -> bool: ...

1076

def to_dict(self) -> dict[str, int]: ...

1077

@classmethod

1078

def from_dict(cls, data: dict[str, int]) -> VectorClock: ...

1079

```

1080

1081

### 6.3 CRDT-Aware Snapshot Format

1082

1083

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

1084

1085

```python

1086

class CRDTSnapshotManifest(TypedDict):

1087

"""Extended snapshot for CRDT-mode plugins."""

1088

files: dict[str, str] # path → content hash (as before)

1089

domain: str

1090

vclock: dict[str, int] # vector clock at snapshot time

1091

crdt_state: dict[str, str] # path → CRDT state hash (separate from content)

1092

schema_version: Literal[1]

1093

```

1094

1095

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.

1096

1097

### 6.4 CRDTPlugin Protocol Extension

1098

1099

```python

1100

class CRDTPlugin(MuseDomainPlugin, Protocol):

1101

"""Extension of MuseDomainPlugin for CRDT-mode domains.

1102

1103

Plugins implementing this protocol get convergent merge semantics:

1104

``merge()`` is replaced by ``join()``, which always succeeds.

1105

"""

1106

1107

def crdt_schema(self) -> CRDTSchema:

1108

"""Declare the CRDT types used for each dimension."""

...

def join(

self,

a: CRDTSnapshotManifest,

1114

b: CRDTSnapshotManifest,

1115

) -> CRDTSnapshotManifest:

1116

"""Merge two snapshots by computing their lattice join.

1117

1118

This operation is:

1119

- Commutative: join(a, b) = join(b, a)

1120

- Associative: join(join(a, b), c) = join(a, join(b, c))

1121

- Idempotent: join(a, a) = a

1122

1123

These three properties guarantee convergence regardless of message

1124

order or delivery count.

"""

...

def to_crdt_state(self, snapshot: StateSnapshot) -> CRDTSnapshotManifest:

1129

"""Lift a plain snapshot into CRDT state representation."""

1130

...

1131

1132

def from_crdt_state(self, crdt: CRDTSnapshotManifest) -> StateSnapshot:

1133

"""Materialise a CRDT state back to a plain snapshot."""

...

```

### 6.5 When to Use CRDT Mode

1138

1139

| Scenario | Recommendation |

1140

|---|---|

1141

| Human-paced commits (once per hour/day) | Three-way merge (Phases 1–3) — richer conflict resolution |

1142

| Many agents writing concurrently (once per second) | CRDT mode — no coordination needed |

1143

| Mix (some slow human commits, some fast agent writes) | CRDT mode with LWW per-dimension |

1144

| Simulation state frames (sequential, one writer) | Three-way merge |

1145

| Shared genomics annotation (many simultaneous annotators) | CRDT OR-Set for annotation set |

1146

| Collaborative score editing (DAW-style) | CRDT RGA for note sequences |

1147

1148

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.

1149

1150

### 6.6 Phase 4 Test Cases

1151

1152

**New test file: `tests/test_crdts.py`**

```

# LWWRegister

test_lww_later_timestamp_wins

1157

test_lww_same_timestamp_author_tiebreak

1158

test_lww_join_is_commutative

1159

test_lww_join_is_associative

1160

test_lww_join_is_idempotent

1161

1162

# ORSet

1163

test_or_set_add_survives_concurrent_remove

1164

test_or_set_remove_observed_element_works

1165

test_or_set_join_is_commutative

1166

test_or_set_join_is_associative

1167

test_or_set_join_is_idempotent

1168

1169

# RGA

1170

test_rga_insert_after_none_is_prepend

1171

test_rga_insert_at_end

1172

test_rga_delete_marks_tombstone

1173

test_rga_concurrent_insert_same_position_deterministic

1174

test_rga_join_is_commutative

1175

test_rga_join_is_associative

1176

test_rga_join_is_idempotent

1177

test_rga_to_sequence_excludes_tombstones

1178

test_rga_round_trip_to_from_dict

1179

1180

# VectorClock

1181

test_vclock_increment_own_agent

1182

test_vclock_merge_takes_max_per_agent

1183

test_vclock_happens_before_simple

1184

test_vclock_concurrent_with_neither_dominates

1185

test_vclock_idempotent_merge

1186

1187

# CRDTPlugin integration

1188

test_crdt_plugin_join_produces_crdt_snapshot

1189

test_crdt_plugin_join_commutes

1190

test_crdt_join_via_core_merge_engine_uses_crdt_path

1191

test_crdt_merge_never_produces_conflicts

1192

```

1193

1194

### 6.7 Files Changed in Phase 4

| File | Change |

|---|---|

| `muse/core/crdts/__init__.py` | **New.** |

1199

| `muse/core/crdts/lww_register.py` | **New.** |

1200

| `muse/core/crdts/or_set.py` | **New.** |

1201

| `muse/core/crdts/rga.py` | **New.** |

1202

| `muse/core/crdts/aw_map.py` | **New.** |

1203

| `muse/core/crdts/g_counter.py` | **New.** |

1204

| `muse/core/crdts/vclock.py` | **New.** |

1205

| `muse/domain.py` | Add `CRDTPlugin` protocol, `CRDTSnapshotManifest`. |

1206

| `muse/core/schema.py` | Add `CRDTSchema`. `DomainSchema.merge_mode` supports `"crdt"`. |

1207

| `muse/core/merge_engine.py` | Route to CRDT `join` when `merge_mode == "crdt"`. |

1208

| `tests/test_crdts.py` | **New.** |

---

## 7. Cross-Cutting Concerns

1213

1214

### 7.1 Content-Addressed Object Store Compatibility

1215

1216

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:

1217

1218

- Any binary element (a note, a nucleotide block, a mesh vertex group) stored via `write_object(repo_root, sha256, bytes)` is automatically deduplicated.

1219

- The store scales to millions of fine-grained sub-elements without format changes.

1220

- Pack files (future work) can be added without changing the protocol.

1221

1222

### 7.2 Commit Record Format Evolution

1223

1224

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:

1225

1226

```python

1227

class CommitRecord(TypedDict):

1228

commit_id: str

1229

snapshot_id: str

1230

parent_commit_id: str | None

1231

parent2_commit_id: str | None

message: str

author: str

committed_at: str

domain: str

structured_delta: StructuredDelta | None # Phase 1

1237

format_version: Literal[1, 2, 3, 4] # tracks schema changes

1238

```

1239

1240

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.

1241

1242

### 7.3 Wire Format for Agent-to-Agent Communication

1243

1244

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.

1245

1246

### 7.4 Typing Constraints

1247

1248

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

1249

1250

- `DomainOp = InsertOp | DeleteOp | MoveOp | ReplaceOp | PatchOp` — exhaustive union, no `Any`.

1251

- `ElementSchema = SequenceSchema | TreeSchema | TensorSchema | MapSchema | SetSchema` — same.

1252

- `PatchOp.child_delta: StructuredDelta` — the recursive field is typed, not `dict[str, Any]`.

1253

- All CRDT types carry concrete generic parameters.

1254

1255

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

1256

1257

### 7.5 Synchronous I/O Constraint

1258

1259

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)

1270

┌─┴─────────┴─┐

1271

│ Integration │ (medium — real components wired together)

1272

┌─┴─────────────┴─┐

1273

│ 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.

1278

1279

### 8.2 Property-Based Testing for Algorithms

1280

1281

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

1282

1283

**LCS:**

1284

- Round-trip: `apply(base, diff(base, target)) == target` for all inputs

1285

- Minimality: `len(diff(a, b).ops) <= len(a) + len(b)` (LCS is minimal)

1286

- Identity: `diff(a, a).ops == []`

1287

1288

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

1289

- Commutativity: `join(a, b) == join(b, a)`

1290

- Associativity: `join(join(a, b), c) == join(a, join(b, c))`

1291

- Idempotency: `join(a, a) == a`

1292

1293

**OT transform (Phase 3):**

1294

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

1295

1296

### 8.3 Regression Test Naming Convention

1297

1298

Every bug fix gets a regression test named:

1299

```

1300

test_<what_broke>_<correct_behavior>

1301

```

1302

1303

Example: `test_concurrent_note_insert_same_bar_does_not_lose_notes`

1304

1305

### 8.4 Test Isolation

1306

1307

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

1312

1313

```

1314

Phase 1 ──────────────────────────────────────────────────────────► Phase 2

1315

│ Typed delta algebra │

1316

│ StructuredDelta replaces DeltaManifest │

1317

│ Music plugin: file→InsertOp, MIDI→PatchOp │

1318

│ midi_diff.py (LCS on note sequences) │

1319

│ │

1320

│ DEPENDS ON: nothing (self-contained) │ Domain schema declaration

1321

│ │ diff_algorithms/ library

1322

▼ │ schema() on protocol

1323

Phase 3 ◄────────────────────────────────────────────────────────────┘

1324

│ Operation-level merge engine

1325

│ ops_commute(), transform(), merge_op_lists()

1326

│ Core engine routes to op_transform when StructuredDelta available

1327

│

1328

│ DEPENDS ON: Phase 1 (needs StructuredDelta) + Phase 2 (needs position metadata)

│

▼

Phase 4

CRDT primitive library (LWWRegister, ORSet, RGA, AWMap, VectorClock)

1333

CRDTPlugin protocol extension

1334

Core merge engine: merge_mode == "crdt" → join()

1335

1336

DEPENDS ON: Phase 1–3 complete

1337

```

1338

1339

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

1340

1341

**Parallel work possible within phases:**

1342

- Phase 1: `midi_diff.py` can be implemented in parallel with the type system changes.

1343

- Phase 2: `lcs.py`, `tree_edit.py`, `numerical.py` can be implemented in parallel.

1344

- Phase 4: All CRDT types (`rga.py`, `or_set.py`, etc.) are independent and can be built in parallel.

1345

1346

### 9.1 Rough Timeline

1347

1348

| Phase | Calendar estimate | Primary difficulty |

1349

|---|---|---|

1350

| Phase 1 | 2–3 weeks | Protocol change propagation; Myers LCS for MIDI |

1351

| Phase 2 | 3–4 weeks | Zhang-Shasha implementation; schema dispatch typing |

1352

| Phase 3 | 4–6 weeks | OT transform correctness; position adjustment cascades |

1353

| Phase 4 | 6–8 weeks | CRDT correctness proofs; vector clock integration |

1354

| **Total** | **15–21 weeks** | |

1355

1356

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.

1357

1358

### 9.2 Definition of Done Per Phase

1359

1360

**Phase 1 done when:**

1361

- [ ] `DeltaManifest` is gone; `StructuredDelta` is the only `StateDelta`

1362

- [ ] Music plugin's `diff()` returns `StructuredDelta` with `PatchOp` for `.mid` files

1363

- [ ] `muse show <commit>` displays note-level diff summary