cgcardona / muse / 986c055e / docs / architecture / supercharge-plan.md
cgcardona / muse public
supercharge-plan.md markdown
1423 lines 60.8 KB
Raw
986c055e docs: fix stale 'five interfaces' count in domain.py and music plugin; … Gabriel Cardona <gabriel@tellurstori.com> 2d ago
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 | — |
12
13 ---
14
15 ## Table of Contents
16
17 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)
26
27 ---
28
29 ## 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.
60
61 ---
62
63 ## 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.
76
77 ---
78
79 ## 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.
84
85 ### 3.1 Motivation
86
87 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
130 from_position: int
131 to_position: int
132 content_id: str
133
134 class ReplaceOp(TypedDict):
135 """An element's value changed (atomic, leaf-level)."""
136 op: Literal["replace"]
137 address: DomainAddress
138 position: int | None
139 old_content_id: str
140 new_content_id: str
141 old_summary: str
142 new_summary: str
143
144 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.
167 """
168 domain: str
169 ops: list[DomainOp]
170 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.
202 """
203 ...
204 ```
205
206 `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.
216 """
217 ...
218 ```
219
220 ### 3.4 Updated `DriftReport`
221
222 `DriftReport.delta` is now a `StructuredDelta`. This means `muse status` can display the rich summary:
223
224 ```python
225 @dataclass
226 class DriftReport:
227 has_drift: bool
228 summary: str = ""
229 delta: StateDelta = field(default_factory=lambda: StructuredDelta(
230 domain="", ops=[], summary="working tree clean",
231 ))
232 ```
233
234 ### 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:
237
238 ```python
239 @dataclass
240 class MergeResult:
241 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):
266 ops.append(InsertOp(
267 op="insert",
268 address=path,
269 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):
275 ops.append(DeleteOp(
276 op="delete",
277 address=path,
278 position=None,
279 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:
289 ops.append(PatchOp(
290 op="patch",
291 address=path,
292 child_delta=child_delta,
293 ))
294 continue
295 # Fallback: atomic replace
296 ops.append(ReplaceOp(
297 op="replace",
298 address=path,
299 position=None,
300 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
352
353 | File | Change |
354 |---|---|
355 | `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
375
376 ---
377
378 ## 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.
383
384 ### 4.1 Motivation
385
386 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.
463 """
464 name: str
465 description: str
466 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).
486 """
487 domain: str
488 description: str
489 # 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.
511 """
512 ...
513 ```
514
515 ### 4.4 Example Schema Declarations
516
517 **Music plugin:**
518
519 ```python
520 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",
528 ),
529 dimensions=[
530 DimensionSpec(
531 name="melodic",
532 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,
541 ),
542 DimensionSpec(
543 name="harmonic",
544 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,
553 ),
554 DimensionSpec(
555 name="dynamic",
556 description="Velocity and expression curves",
557 schema=TensorSchema(
558 kind="tensor",
559 dtype="float32",
560 rank=1,
561 epsilon=1.0, # velocities are integers 0–127; 1.0 tolerance
562 diff_mode="sparse",
563 ),
564 independent_merge=True,
565 ),
566 DimensionSpec(
567 name="structural",
568 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",
578 schema_version=1,
579 )
580 ```
581
582 **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", "-"],
598 ),
599 identity="by_key",
600 ),
601 dimensions=[
602 DimensionSpec(
603 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,
613 ),
614 DimensionSpec(
615 name="regulatory",
616 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,
623 ),
624 DimensionSpec(
625 name="metadata",
626 description="Annotations, quality scores, provenance",
627 schema=MapSchema(
628 kind="map",
629 key_type="annotation_key",
630 value_schema=TensorSchema(
631 kind="tensor",
632 dtype="float32",
633 rank=1,
634 epsilon=0.001,
635 diff_mode="sparse",
636 ),
637 identity="by_key",
638 ),
639 independent_merge=True,
640 ),
641 ],
642 merge_mode="three_way",
643 schema_version=1,
644 )
645 ```
646
647 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:
663
664 ```python
665 def diff_by_schema(
666 schema: ElementSchema,
667 base: SequenceData | TreeData | TensorData | SetData | MapData,
668 target: SequenceData | TreeData | TensorData | SetData | MapData,
669 *,
670 domain: str,
671 address: str = "",
672 ) -> 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`**
727
728 ```
729 # LCS / Myers
730 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
784
785 | File | Change |
786 |---|---|
787 | `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)
812
813 ---
814
815 ## 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).
820
821 ### 5.1 Motivation
822
823 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 |
832 |---|---|---|---|
833 | `InsertOp(pos=i)` | `InsertOp(pos=j)` | **Yes** | `i ≠ j` (different positions) |
834 | `InsertOp(pos=i)` | `InsertOp(pos=i)` | **No** | Same position — positional conflict |
835 | `InsertOp` | `DeleteOp` | **No** | Unless different subtrees |
836 | `DeleteOp(addr=A)` | `DeleteOp(addr=B)` | **Yes** | `A ≠ B` |
837 | `DeleteOp(addr=A)` | `DeleteOp(addr=A)` | **Yes** | Consensus delete — clean |
838 | `ReplaceOp(addr=A)` | `ReplaceOp(addr=B)` | **Yes** | `A ≠ B` |
839 | `ReplaceOp(addr=A)` | `ReplaceOp(addr=A)` | **No** | Same address — value conflict |
840 | `MoveOp(from=i)` | `MoveOp(from=j)` | **Yes** | `i ≠ j` |
841 | `MoveOp(from=i)` | `DeleteOp(pos=i)` | **No** | Move-delete conflict |
842 | `PatchOp(addr=A)` | `PatchOp(addr=B)` | **Yes** | `A ≠ B` — recurse on children |
843 | `PatchOp(addr=A)` | `PatchOp(addr=A)` | Recurse | Check child ops for conflicts |
844
845 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.
856
857 The public API is:
858
859 - ``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
866
867
868 @dataclass
869 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
889 final state.
890 """
891 ...
892
893 def merge_op_lists(
894 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.
903 """
904 ...
905 ```
906
907 ### 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):
932
933 ```python
934 def merge_ops(
935 self,
936 base: StateSnapshot,
937 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()``.
951 """
952 ...
953 ```
954
955 ### 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:
958
959 ```
960 Base: [A, B, C]
961 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
1011
1012 | File | Change |
1013 |---|---|
1014 | `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. |
1020
1021 ---
1022
1023 ## 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).
1028
1029 ### 6.1 Motivation
1030
1031 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/`**
1040
1041 ```
1042 muse/core/crdts/
1043 __init__.py
1044 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.
1100
1101 ```python
1102 class VectorClock:
1103 """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."""
1141 ...
1142
1143 def join(
1144 self,
1145 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.
1157 """
1158 ...
1159
1160 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."""
1166 ...
1167 ```
1168
1169 ### 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`**
1185
1186 ```
1187 # LWWRegister
1188 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
1227
1228 | File | Change |
1229 |---|---|
1230 | `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.** |
1241
1242 ---
1243
1244 ## 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
1264 message: str
1265 author: str
1266 committed_at: str
1267 domain: str
1268 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.
1292
1293 ---
1294
1295 ## 8. Test Strategy
1296
1297 ### 8.1 Test Pyramid
1298
1299 ```
1300 ┌─────────┐
1301 │ 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)
1306 └──────────────────┘
1307 ```
1308
1309 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.
1340
1341 ---
1342
1343 ## 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)
1361 │
1362 ▼
1363 Phase 4
1364 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
1396 - [ ] `mypy muse/` zero errors
1397 - [ ] `python tools/typing_audit.py --dirs muse/ tests/ --max-any 0` zero violations
1398 - [ ] All new test cases pass
1399
1400 **Phase 2 done when:**
1401 - [ ] `schema()` is on the `MuseDomainPlugin` protocol
1402 - [ ] Music plugin returns a complete `DomainSchema`
1403 - [ ] `diff_algorithms/` contains LCS, tree-edit, numerical, set implementations
1404 - [ ] All four algorithms have property-based tests passing
1405 - [ ] `diff_by_schema` dispatch is exhaustively typed (no `Any`, mypy verified)
1406
1407 **Phase 3 done when:**
1408 - [ ] `ops_commute()` correctly handles all 25 op-pair combinations
1409 - [ ] `transform()` passes the diamond property for all commuting pairs
1410 - [ ] Music plugin: inserting notes at non-overlapping bars never conflicts
1411 - [ ] Core merge engine uses `merge_op_lists` when `StructuredDelta` is available
1412 - [ ] Property tests verify OT correctness on randomly generated op sequences
1413
1414 **Phase 4 done when:**
1415 - [ ] All five CRDT types pass the three lattice laws (property tests via `hypothesis`)
1416 - [ ] `VectorClock` correctly identifies concurrent vs. causally-ordered events
1417 - [ ] A music plugin in CRDT mode never produces a `MergeResult.conflicts` entry
1418 - [ ] The core merge engine's CRDT path is exercised by integration tests
1419 - [ ] `CRDTPlugin` protocol is verified by a `runtime_checkable` assertion
1420
1421 ---
1422
1423 *End of plan. Implementation begins at Phase 1. Each phase produces a PR against `dev` with its own verification checklist completed.*