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

1

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

2

3

> **Status:** Active implementation — Phase 1 complete, Phase 2 in progress.

4

> No backward compatibility constraints. We own every line.

5

>

6

> | Phase | Status | Branch / PR |

7

> |-------|--------|-------------|

8

> | Phase 1 — Typed Delta Algebra | ✅ **Complete** — merged to `dev` ([PR #13](https://github.com/cgcardona/muse/pull/13)) | `feat/phase-1-typed-delta-algebra` |

9

> | Phase 2 — Domain Schema & Diff Algorithm Library | ✅ **Complete** — merged to `dev` ([PR #15](https://github.com/cgcardona/muse/pull/15)) | `feat/phase-2-domain-schema-diff-library` |

10

> | Phase 3 — Operation-Level Merge Engine | 🔄 **In progress** | `feat/phase-3-op-level-merge-engine` |

11

> | Phase 4 — CRDT Semantics | ⏳ Pending Phase 3 | — |

---

## Table of Contents

1. [Honest Assessment of Current State](#1-honest-assessment-of-current-state)

18

2. [North Star: What We're Building Toward](#2-north-star-what-were-building-toward)

19

3. [Phase 1 — Typed Delta Algebra](#3-phase-1--typed-delta-algebra)

20

4. [Phase 2 — Domain Schema & Diff Algorithm Library](#4-phase-2--domain-schema--diff-algorithm-library)

21

5. [Phase 3 — Operation-Level Merge Engine](#5-phase-3--operation-level-merge-engine)

22

6. [Phase 4 — CRDT Semantics for Convergent Multi-Agent Writes](#6-phase-4--crdt-semantics-for-convergent-multi-agent-writes)

23

7. [Cross-Cutting Concerns](#7-cross-cutting-concerns)

24

8. [Test Strategy](#8-test-strategy)

25

9. [Implementation Order and Dependencies](#9-implementation-order-and-dependencies)

---

## 1. Honest Assessment of Current State

30

31

### What is good and must be preserved

32

33

- **Content-addressed object store** — SHA-256 blobs in `.muse/objects/`. This is correct at every scale. Git proved it. Keep it forever.

34

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

35

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

36

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

37

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

38

39

### What is genuinely limited

40

41

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:

42

43

```

44

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

45

```

46

47

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

48

49

**Consequences of this ceiling:**

50

51

| Scenario | Current behavior | Correct behavior |

52

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

53

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

54

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

55

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

56

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

57

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

58

59

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

64

65

A universal multidimensional VCS where:

66

67

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.

68

69

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

70

71

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

72

73

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

74

75

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

80

81

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

82

83

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

88

89

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.

90

91

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

92

93

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

94

95

```python

96

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

97

# Atomic position types

98

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

99

100

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

101

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

102

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

103

# - Plugins define what addresses mean in their domain.

104

DomainAddress = str

105

106

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

107

# Atomic operation types

108

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

109

110

class InsertOp(TypedDict):

111

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

112

op: Literal["insert"]

113

address: DomainAddress # where in the structure

114

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

115

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

116

content_summary: str # human-readable description for display

117

118

class DeleteOp(TypedDict):

119

"""An element was removed."""

120

op: Literal["delete"]

121

address: DomainAddress

122

position: int | None

123

content_id: str # SHA-256 of removed content

124

content_summary: str

125

126

class MoveOp(TypedDict):

127

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

128

op: Literal["move"]

129

address: DomainAddress

from_position: int

to_position: int

content_id: str

class ReplaceOp(TypedDict):

135

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

136

op: Literal["replace"]

137

address: DomainAddress

position: int | None

old_content_id: str

new_content_id: str

old_summary: str

new_summary: str

class PatchOp(TypedDict):

145

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

146

op: Literal["patch"]

147

address: DomainAddress # the container being patched

148

child_delta: StructuredDelta # recursive — describes what changed inside

149

150

# The union of all operation types

151

DomainOp = InsertOp | DeleteOp | MoveOp | ReplaceOp | PatchOp

152

153

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

154

# The new StateDelta

155

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

156

157

class StructuredDelta(TypedDict):

158

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

159

160

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

161

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

162

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

163

reason over it for commutativity.

164

165

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

166

Plugins compute this because only they understand their domain semantics.

"""

domain: str

ops: list[DomainOp]

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

171

172

# StateDelta is now StructuredDelta. DeltaManifest is gone.

173

StateDelta = StructuredDelta

174

```

175

176

**Key design decisions:**

177

178

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

179

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

180

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

181

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

182

183

### 3.3 Updated Plugin Protocol

184

185

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

186

187

```python

188

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

189

"""Compute the structured delta between two snapshots.

190

191

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

192

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

193

194

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

195

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

196

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

197

is available; otherwise use deterministic synthetic IDs.

198

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

199

200

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

201

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

207

208

```python

209

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

210

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

211

212

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

213

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

214

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

215

should apply ops to disk files directly.

"""

...

```

### 3.4 Updated `DriftReport`

221

222

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

230

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

))

```

### 3.5 Updated `MergeResult`

235

236

`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

242

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

243

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

244

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

245

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

246

247

@property

248

def is_clean(self) -> bool:

249

return len(self.conflicts) == 0

250

```

251

252

### 3.6 Updated Music Plugin

253

254

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:

255

256

```python

257

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

258

base_files = base["files"]

259

target_files = target["files"]

260

base_paths = set(base_files)

261

target_paths = set(target_files)

262

263

ops: list[DomainOp] = []

264

265

for path in sorted(target_paths - base_paths):

ops.append(InsertOp(

op="insert",

address=path,

position=None, # file collection is unordered

270

content_id=target_files[path],

271

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

272

))

273

274

for path in sorted(base_paths - target_paths):

ops.append(DeleteOp(

op="delete",

address=path,

position=None,

content_id=base_files[path],

280

content_summary=f"deleted: {path}",

281

))

282

283

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

284

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

285

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

286

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

287

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

288

if child_delta is not None:

ops.append(PatchOp(

op="patch",

address=path,

child_delta=child_delta,

293

))

294

continue

295

# Fallback: atomic replace

296

ops.append(ReplaceOp(

op="replace",

address=path,

position=None,

old_content_id=base_files[path],

301

new_content_id=target_files[path],

302

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

303

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

304

))

305

306

summary = _summarise_ops(ops)

307

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

308

```

309

310

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

311

312

### 3.7 Serialisation Contract

313

314

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

315

316

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.

317

318

### 3.8 Phase 1 Test Cases

319

320

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

321

322

```

323

test_insert_op_round_trips_json

324

test_delete_op_round_trips_json

325

test_move_op_round_trips_json

326

test_replace_op_round_trips_json

327

test_patch_op_with_child_delta_round_trips_json

328

test_structured_delta_satisfies_state_delta_type

329

test_music_plugin_diff_returns_structured_delta

330

test_music_plugin_diff_file_add_produces_insert_op

331

test_music_plugin_diff_file_remove_produces_delete_op

332

test_music_plugin_diff_file_modify_produces_replace_op

333

test_music_plugin_diff_midi_modify_produces_patch_op_with_child_ops

334

test_drift_report_delta_is_structured_delta

335

test_muse_show_displays_structured_summary

336

test_muse_diff_displays_per_op_lines

337

```

338

339

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

340

341

```

342

test_midi_diff_empty_to_single_note_is_one_insert

343

test_midi_diff_single_note_to_empty_is_one_delete

344

test_midi_diff_note_velocity_change_is_replace

345

test_midi_diff_note_inserted_in_middle_identified_correctly

346

test_midi_diff_note_transposition_identified_as_replace

347

test_midi_diff_no_change_returns_empty_ops

348

test_midi_diff_summary_string_is_human_readable

349

```

350

351

### 3.9 Files Changed in Phase 1

| File | Change |

|---|---|

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

356

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

357

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

358

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

359

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

360

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

361

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

362

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

363

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

364

365

### 3.10 Phase 1 Completion Checklist

366

367

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

368

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

369

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

370

- [x] `mypy muse/` — zero errors

371

- [x] `python tools/typing_audit.py --dirs muse/ tests/ --max-any 0` — zero violations

372

- [x] All new test cases pass (38 in `test_structured_delta.py`, 29 in `test_midi_diff.py`)

373

- [x] `.muse/` added to `.gitignore` (housekeeping fix — PR #14)

374

- [x] CI trigger narrowed to PRs targeting `main` only

---

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

379

380

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

381

382

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

387

388

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.

389

390

### 4.2 Domain Schema Types

391

392

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

393

394

```python

395

"""Domain schema declaration types.

396

397

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

398

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

399

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

400

informed merge conflict messages.

401

"""

402

from __future__ import annotations

403

from typing import Literal, TypedDict

404

405

406

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

407

# Primitive element schemas

408

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

409

410

class SequenceSchema(TypedDict):

411

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

412

kind: Literal["sequence"]

413

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

414

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

415

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

416

# Optional: alphabet constraint for validation

417

alphabet: list[str] | None

418

419

class TreeSchema(TypedDict):

420

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

421

kind: Literal["tree"]

422

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

423

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

424

425

class TensorSchema(TypedDict):

426

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

427

kind: Literal["tensor"]

428

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

429

rank: int # number of dimensions

430

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

431

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

432

433

class MapSchema(TypedDict):

434

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

435

kind: Literal["map"]

436

key_type: str

437

value_schema: ElementSchema # recursive

438

identity: Literal["by_key"]

439

440

class SetSchema(TypedDict):

441

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

442

kind: Literal["set"]

443

element_type: str

444

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

445

446

# The union of all element schema types

447

ElementSchema = SequenceSchema | TreeSchema | TensorSchema | MapSchema | SetSchema

448

449

450

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

451

# Dimension spec — a named structural sub-dimension

452

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

453

454

class DimensionSpec(TypedDict):

455

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

456

457

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

458

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

459

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

460

461

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

462

The merge engine can merge dimensions independently.

"""

name: str

description: str

schema: ElementSchema

467

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

468

# or are resolved independently.

469

independent_merge: bool

470

471

472

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

473

# Top-level domain schema

474

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

475

476

class DomainSchema(TypedDict):

477

"""Complete structural declaration for a domain plugin.

478

479

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

480

once at plugin registration time and uses it to:

481

482

1. Select the correct diff algorithm for each dimension.

483

2. Generate typed delta validation.

484

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

485

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

"""

domain: str

description: str

# Dimensions that make up this domain's state.

490

# The core engine merges each independently when possible.

491

dimensions: list[DimensionSpec]

492

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

493

top_level: ElementSchema

494

# Which merge strategy to use at the top level

495

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

496

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

497

schema_version: Literal[1]

498

```

499

500

### 4.3 Schema Method Added to Plugin Protocol

501

502

```python

503

def schema(self) -> DomainSchema:

504

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

505

506

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

507

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

508

algorithm selection, delta validation, and conflict messaging.

509

510

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

"""

...

```

### 4.4 Example Schema Declarations

**Music plugin:**

```python

def schema(self) -> DomainSchema:

521

return DomainSchema(

522

domain="music",

523

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

524

top_level=SetSchema(

525

kind="set",

526

element_type="audio_file",

527

identity="by_content",

),

dimensions=[

DimensionSpec(

name="melodic",

description="Note pitches and durations over time",

533

schema=SequenceSchema(

534

kind="sequence",

535

element_type="note_event",

536

identity="by_position",

537

diff_algorithm="lcs",

538

alphabet=None,

539

),

540

independent_merge=True,

),

DimensionSpec(

name="harmonic",

description="Chord progressions and key signatures",

545

schema=SequenceSchema(

546

kind="sequence",

547

element_type="chord_event",

548

identity="by_position",

549

diff_algorithm="lcs",

550

alphabet=None,

551

),

552

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

562

diff_mode="sparse",

563

),

564

independent_merge=True,

),

DimensionSpec(

name="structural",

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

569

schema=TreeSchema(

570

kind="tree",

571

node_type="track_node",

572

diff_algorithm="zhang_shasha",

573

),

574

independent_merge=False, # structural changes block all dimensions

575

),

576

],

577

merge_mode="three_way",

schema_version=1,

)

```

**Hypothetical genomics plugin:**

583

584

```python

585

def schema(self) -> DomainSchema:

586

return DomainSchema(

587

domain="genomics",

588

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

589

top_level=MapSchema(

590

kind="map",

591

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

592

value_schema=SequenceSchema(

593

kind="sequence",

594

element_type="nucleotide",

595

identity="by_position",

596

diff_algorithm="myers",

597

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

),

identity="by_key",

),

dimensions=[

DimensionSpec(

name="coding_regions",

604

description="Exons and coding sequence",

605

schema=SequenceSchema(

606

kind="sequence",

607

element_type="nucleotide",

608

identity="by_position",

609

diff_algorithm="myers",

610

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

611

),

612

independent_merge=True,

),

DimensionSpec(

name="regulatory",

description="Promoters, enhancers, splice sites",

617

schema=SetSchema(

618

kind="set",

619

element_type="regulatory_element",

620

identity="by_id",

621

),

622

independent_merge=True,

),

DimensionSpec(

name="metadata",

description="Annotations, quality scores, provenance",

627

schema=MapSchema(

628

kind="map",

629

key_type="annotation_key",

630

value_schema=TensorSchema(

kind="tensor",

dtype="float32",

rank=1,

epsilon=0.001,

diff_mode="sparse",

),

identity="by_key",

),

independent_merge=True,

640

),

641

],

642

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.

648

649

### 4.5 Diff Algorithm Library

650

651

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

652

653

```

654

muse/core/diff_algorithms/

655

__init__.py → dispatch function

656

lcs.py → Myers / patience diff for ordered sequences

657

tree_edit.py → Zhang-Shasha tree edit distance

658

numerical.py → sparse numerical diff for tensors

659

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

660

```

661

662

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

```python

def diff_by_schema(

schema: ElementSchema,

667

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

668

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

*,

domain: str,

address: str = "",

) -> StructuredDelta:

673

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

674

match schema["kind"]:

675

case "sequence":

676

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

677

case "tree":

678

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

679

case "tensor":

680

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

681

case "set":

682

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

683

case "map":

684

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

685

```

686

687

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

688

689

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.

690

691

Key functions:

692

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

693

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

694

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

695

696

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

697

698

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

699

700

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.

701

702

Key functions:

703

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

704

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

705

706

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

707

708

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:

709

710

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

711

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

712

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

713

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

714

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

715

716

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

717

718

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.

719

720

### 4.6 Plugin Registry Gains Schema Lookup

721

722

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

723

724

### 4.7 Phase 2 Test Cases

725

726

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

```

# LCS / Myers

test_lcs_empty_to_sequence_is_all_inserts

731

test_lcs_sequence_to_empty_is_all_deletes

732

test_lcs_identical_sequences_returns_no_ops

733

test_lcs_single_insert_in_middle

734

test_lcs_single_delete_in_middle

735

test_lcs_move_detected_from_delete_plus_insert

736

test_lcs_transposition_of_two_elements

737

test_lcs_patience_mode_handles_repeated_elements

738

test_lcs_produces_valid_structured_delta

739

740

# Tree edit

741

test_tree_edit_leaf_relabel_is_replace

742

test_tree_edit_node_insert

743

test_tree_edit_node_delete

744

test_tree_edit_subtree_move

745

test_tree_edit_identical_trees_returns_no_ops

746

test_tree_edit_produces_valid_structured_delta

747

748

# Numerical

749

test_numerical_within_epsilon_returns_no_ops

750

test_numerical_outside_epsilon_returns_replace

751

test_numerical_sparse_mode_one_op_per_element

752

test_numerical_block_mode_groups_adjacent

753

test_numerical_full_mode_single_op

754

test_numerical_produces_valid_structured_delta

755

756

# Set ops

757

test_set_diff_add_returns_insert

758

test_set_diff_remove_returns_delete

759

test_set_diff_no_change_returns_empty

760

test_set_diff_produces_valid_structured_delta

761

762

# Schema dispatch

763

test_dispatch_sequence_schema_calls_lcs

764

test_dispatch_tree_schema_calls_zhang_shasha

765

test_dispatch_tensor_schema_calls_numerical

766

test_dispatch_set_schema_calls_set_ops

767

test_dispatch_map_schema_recurses

768

```

769

770

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

771

772

```

773

test_music_plugin_schema_returns_domain_schema

774

test_music_plugin_schema_has_four_dimensions

775

test_music_plugin_schema_melodic_dimension_is_sequence

776

test_music_plugin_schema_structural_dimension_is_tree

777

test_music_plugin_schema_dynamic_dimension_is_tensor

778

test_schema_round_trips_json

779

test_schema_version_is_1

780

test_plugin_registry_schema_lookup

781

```

782

783

### 4.8 Files Changed in Phase 2

| File | Change |

|---|---|

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

788

| `muse/core/diff_algorithms/__init__.py` | **New.** Schema-driven dispatch + typed input containers. |

789

| `muse/core/diff_algorithms/lcs.py` | **New.** `myers_ses()`, `detect_moves()`, `diff()` on `list[str]`. |

790

| `muse/core/diff_algorithms/tree_edit.py` | **New.** `TreeNode` dataclass + LCS-based labeled tree diff. |

791

| `muse/core/diff_algorithms/numerical.py` | **New.** Epsilon-tolerant sparse/block/full tensor diff. |

792

| `muse/core/diff_algorithms/set_ops.py` | **New.** Hash-set algebra for unordered content-ID collections. |

793

| `muse/domain.py` | Add sixth protocol method `schema() -> DomainSchema`. |

794

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

795

| `muse/plugins/music/plugin.py` | Implement `schema()` returning full four-dimension `DomainSchema`. |

796

| `muse/plugins/music/midi_diff.py` | `lcs_edit_script()` now delegates to `lcs.myers_ses()` from core; no private LCS copy. |

797

| `tests/test_diff_algorithms.py` | **New.** 54 tests across all algorithms and dispatch. |

798

| `tests/test_domain_schema.py` | **New.** 20 tests for schema structure and registry lookup. |

799

800

### 4.9 Phase 2 Completion Checklist

801

802

- [x] `schema()` is on the `MuseDomainPlugin` protocol as the sixth method

803

- [x] Music plugin returns a complete `DomainSchema` with four dimensions

804

- [x] `diff_algorithms/` contains LCS, tree-edit, numerical, set-ops implementations

805

- [x] All four algorithms tested with comprehensive unit and dispatch tests

806

- [x] `diff_by_schema` dispatch is exhaustively typed (no `Any`, mypy verified)

807

- [x] `schema_for()` added to plugin registry for schema lookup without a plugin instance

808

- [x] `midi_diff.py` delegates LCS to `lcs.myers_ses()` — music domain uses the shared library

809

- [x] `mypy muse/` — zero errors

810

- [x] `python tools/typing_audit.py --dirs muse/ tests/ --max-any 0` — zero violations

811

- [x] `pytest tests/ -v` — 530 tests green (74 new Phase 2 tests)

---

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

816

817

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

818

819

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

824

825

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.

826

827

### 5.2 Commutativity Rules

828

829

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:

830

831

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

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

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

837

838

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

839

840

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

846

847

### 5.3 Operation Transformer Functions

848

849

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

850

851

```python

852

"""Operational transformation for Muse domain operations.

853

854

Implements the commutativity rules that let the merge engine determine

855

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.

860

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

861

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

862

"""

863

from __future__ import annotations

864

from dataclasses import dataclass, field

865

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

@dataclass

class MergeOpsResult:

870

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

871

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

872

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

873

874

@property

875

def is_clean(self) -> bool:

876

return len(self.conflict_ops) == 0

877

878

879

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

880

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

881

...

882

883

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

884

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

885

886

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

887

are generated concurrently against the same base, transform returns

888

adjusted versions that can be applied sequentially to achieve the same

final state.

"""

...

def merge_op_lists(

base_ops: list[DomainOp],

895

ours_ops: list[DomainOp],

896

theirs_ops: list[DomainOp],

897

) -> MergeOpsResult:

898

"""Three-way merge at operation granularity.

899

900

Applies commutativity rules to detect which pairs of operations truly

901

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

902

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

"""

...

```

### 5.4 Updated Core Merge Engine

908

909

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

910

911

```python

912

def merge_structured(

913

base_delta: StructuredDelta,

914

ours_delta: StructuredDelta,

915

theirs_delta: StructuredDelta,

916

) -> MergeOpsResult:

917

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

918

919

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

920

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

921

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

922

"""

923

from muse.core.op_transform import merge_op_lists

924

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

925

```

926

927

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.

928

929

### 5.5 Plugin Protocol Gains `merge_ops`

930

931

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],

938

theirs_ops: list[DomainOp],

939

*,

940

repo_root: pathlib.Path | None = None,

941

) -> MergeResult:

942

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

943

944

The core engine calls this when both branches have produced

945

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

946

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

947

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

948

949

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

950

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

"""

...

```

### 5.6 Position Adjustment After Transform

956

957

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]

962

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

963

964

After transform:

965

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

966

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

967

```

968

969

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.

970

971

### 5.7 Phase 3 Test Cases

972

973

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

974

975

```

976

# Commutativity oracle

977

test_commute_inserts_at_different_positions_is_true

978

test_commute_inserts_at_same_position_is_false

979

test_commute_deletes_at_different_addresses_is_true

980

test_commute_consensus_delete_is_true

981

test_commute_replaces_at_different_addresses_is_true

982

test_commute_replaces_at_same_address_is_false

983

test_commute_move_and_delete_same_position_is_false

984

test_commute_patch_at_different_addresses_is_true

985

test_commute_patch_at_same_address_recurses_children

986

987

# OT transform function

988

test_transform_two_inserts_adjusts_positions_correctly

989

test_transform_insert_and_delete_produces_adjusted_ops

990

test_transform_identity_when_ops_commute

991

992

# Three-way merge

993

test_merge_op_lists_clean_non_overlapping

994

test_merge_op_lists_same_op_both_sides_is_idempotent

995

test_merge_op_lists_conflict_same_position_insert

996

test_merge_op_lists_conflict_same_address_replace

997

test_merge_op_lists_consensus_delete_both_sides

998

test_merge_op_lists_nested_patch_recurses

999

test_merge_op_lists_position_adjustment_cascades

1000

test_merge_op_lists_empty_one_side_applies_other

1001

test_merge_op_lists_both_empty_returns_base

1002

1003

# Integration: merge engine uses op_transform when structured deltas available

1004

test_merge_engine_uses_op_transform_for_structured_deltas

1005

test_merge_engine_falls_back_to_file_level_without_structured_deltas

1006

test_full_merge_non_overlapping_note_inserts_auto_merges

1007

test_full_merge_same_note_insert_produces_conflict

1008

```

1009

1010

### 5.8 Files Changed in Phase 3

| File | Change |

|---|---|

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

1015

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

1016

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

1017

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

1018

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

1019

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

---

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

1024

1025

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

1026

1027

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

1032

1033

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

1034

1035

This is the endgame for the multi-agent scenario.

1036

1037

### 6.2 CRDT Primitive Library

1038

1039

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

```

muse/core/crdts/

__init__.py

lww_register.py → Last-Write-Wins Register

1045

or_set.py → Observed-Remove Set

1046

rga.py → Replicated Growable Array (ordered sequences)

1047

aw_map.py → Add-Wins Map

1048

g_counter.py → Grow-only Counter

1049

vclock.py → Vector Clock (causal ordering)

1050

```

1051

1052

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

1053

1054

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.

1055

1056

```python

1057

class LWWValue(TypedDict):

1058

value: str # JSON-serialisable value

1059

timestamp: float # Unix timestamp or logical clock

1060

author: str # Agent ID for tiebreaking

1061

1062

class LWWRegister:

1063

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

1064

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

1065

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

1066

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

1067

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

1068

@classmethod

1069

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

1070

```

1071

1072

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

1073

1074

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.

1075

1076

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

1077

1078

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.

1079

1080

```python

1081

class RGAElement(TypedDict):

1082

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

1083

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

1084

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

1085

1086

class RGA:

1087

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

1088

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

1089

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

1090

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

1091

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

1092

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

1093

@classmethod

1094

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

1095

```

1096

1097

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

1098

1099

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

1104

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

1105

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

1106

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

1107

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

1108

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

1109

@classmethod

1110

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

1111

```

1112

1113

### 6.3 CRDT-Aware Snapshot Format

1114

1115

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

1116

1117

```python

1118

class CRDTSnapshotManifest(TypedDict):

1119

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

1120

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

1121

domain: str

1122

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

1123

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

1124

schema_version: Literal[1]

1125

```

1126

1127

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.

1128

1129

### 6.4 CRDTPlugin Protocol Extension

1130

1131

```python

1132

class CRDTPlugin(MuseDomainPlugin, Protocol):

1133

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

1134

1135

Plugins implementing this protocol get convergent merge semantics:

1136

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

1137

"""

1138

1139

def crdt_schema(self) -> CRDTSchema:

1140

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

...

def join(

self,

a: CRDTSnapshotManifest,

1146

b: CRDTSnapshotManifest,

1147

) -> CRDTSnapshotManifest:

1148

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

1149

1150

This operation is:

1151

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

1152

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

1153

- Idempotent: join(a, a) = a

1154

1155

These three properties guarantee convergence regardless of message

1156

order or delivery count.

"""

...

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

1161

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

1162

...

1163

1164

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

1165

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

...

```

### 6.5 When to Use CRDT Mode

1170

1171

| Scenario | Recommendation |

1172

|---|---|

1173

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

1174

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

1175

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

1176

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

1177

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

1178

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

1179

1180

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.

1181

1182

### 6.6 Phase 4 Test Cases

1183

1184

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

```

# LWWRegister

test_lww_later_timestamp_wins

1189

test_lww_same_timestamp_author_tiebreak

1190

test_lww_join_is_commutative

1191

test_lww_join_is_associative

1192

test_lww_join_is_idempotent

1193

1194

# ORSet

1195

test_or_set_add_survives_concurrent_remove

1196

test_or_set_remove_observed_element_works

1197

test_or_set_join_is_commutative

1198

test_or_set_join_is_associative

1199

test_or_set_join_is_idempotent

1200

1201

# RGA

1202

test_rga_insert_after_none_is_prepend

1203

test_rga_insert_at_end

1204

test_rga_delete_marks_tombstone

1205

test_rga_concurrent_insert_same_position_deterministic

1206

test_rga_join_is_commutative

1207

test_rga_join_is_associative

1208

test_rga_join_is_idempotent

1209

test_rga_to_sequence_excludes_tombstones

1210

test_rga_round_trip_to_from_dict

1211

1212

# VectorClock

1213

test_vclock_increment_own_agent

1214

test_vclock_merge_takes_max_per_agent

1215

test_vclock_happens_before_simple

1216

test_vclock_concurrent_with_neither_dominates

1217

test_vclock_idempotent_merge

1218

1219

# CRDTPlugin integration

1220

test_crdt_plugin_join_produces_crdt_snapshot

1221

test_crdt_plugin_join_commutes

1222

test_crdt_join_via_core_merge_engine_uses_crdt_path

1223

test_crdt_merge_never_produces_conflicts

1224

```

1225

1226

### 6.7 Files Changed in Phase 4

| File | Change |

|---|---|

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

1231

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

1232

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

1233

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

1234

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

1235

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

1236

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

1237

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

1238

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

1239

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

1240

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

---

## 7. Cross-Cutting Concerns

1245

1246

### 7.1 Content-Addressed Object Store Compatibility

1247

1248

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:

1249

1250

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

1251

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

1252

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

1253

1254

### 7.2 Commit Record Format Evolution

1255

1256

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:

1257

1258

```python

1259

class CommitRecord(TypedDict):

1260

commit_id: str

1261

snapshot_id: str

1262

parent_commit_id: str | None

1263

parent2_commit_id: str | None

message: str

author: str

committed_at: str

domain: str

structured_delta: StructuredDelta | None # Phase 1

1269

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

1270

```

1271

1272

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.

1273

1274

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

1275

1276

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.

1277

1278

### 7.4 Typing Constraints

1279

1280

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

1281

1282

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

1283

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

1284

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

1285

- All CRDT types carry concrete generic parameters.

1286

1287

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

1288

1289

### 7.5 Synchronous I/O Constraint

1290

1291

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)

1302

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

1303

│ Integration │ (medium — real components wired together)

1304

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

1305

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

1310

1311

### 8.2 Property-Based Testing for Algorithms

1312

1313

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

1314

1315

**LCS:**

1316

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

1317

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

1318

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

1319

1320

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

1321

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

1322

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

1323

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

1324

1325

**OT transform (Phase 3):**

1326

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

1327

1328

### 8.3 Regression Test Naming Convention

1329

1330

Every bug fix gets a regression test named:

1331

```

1332

test_<what_broke>_<correct_behavior>

1333

```

1334

1335

Example: `test_concurrent_note_insert_same_bar_does_not_lose_notes`

1336

1337

### 8.4 Test Isolation

1338

1339

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

1344

1345

```

1346

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

1347

│ Typed delta algebra │

1348

│ StructuredDelta replaces DeltaManifest │

1349

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

1350

│ midi_diff.py (LCS on note sequences) │

1351

│ │

1352

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

1353

│ │ diff_algorithms/ library

1354

▼ │ schema() on protocol

1355

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

1356

│ Operation-level merge engine

1357

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

1358

│ Core engine routes to op_transform when StructuredDelta available

1359

│

1360

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

│

▼

Phase 4

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

1365

CRDTPlugin protocol extension

1366

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

1367

1368

DEPENDS ON: Phase 1–3 complete

1369

```

1370

1371

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

1372

1373

**Parallel work possible within phases:**

1374

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

1375

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

1376

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

1377

1378

### 9.1 Rough Timeline

1379

1380

| Phase | Calendar estimate | Primary difficulty |

1381

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

1382

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

1383

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

1384

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

1385

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

1386

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

1387

1388

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.

1389

1390

### 9.2 Definition of Done Per Phase

1391

1392

**Phase 1 done when:**

1393

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

1394

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

1395

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