cgcardona / muse / bda49bdb / muse / core / merge_engine.py
cgcardona / muse public
merge_engine.py python
439 lines 15.3 KB
Raw
bda49bdb feat: redesign .museignore as TOML with domain-scoped sections (#100) Gabriel Cardona <cgcardona@gmail.com> 1d ago
1 """Muse VCS merge engine — fast-forward, 3-way, op-level, and CRDT merge.
2
3 Public API
4 ----------
5 Pure functions (no I/O):
6
7 - :func:`diff_snapshots` — paths that changed between two snapshot manifests.
8 - :func:`detect_conflicts` — paths changed on *both* branches since the base.
9 - :func:`apply_merge` — build merged manifest for a conflict-free 3-way merge.
10 - :func:`crdt_join_snapshots` — convergent CRDT join; always succeeds.
11
12 Operational Transformation (operation-level) merge:
13
14 - :mod:`muse.core.op_transform` — ``ops_commute``, ``transform``, ``merge_op_lists``,
15 ``merge_structured``, and :class:`~muse.core.op_transform.MergeOpsResult`.
16 Plugins that implement :class:`~muse.domain.StructuredMergePlugin` use these
17 functions to auto-merge non-conflicting ``DomainOp`` lists.
18
19 CRDT convergent merge:
20
21 - :func:`crdt_join_snapshots` — detects :class:`~muse.domain.CRDTPlugin` at
22 runtime and delegates to ``plugin.join(a, b)``. Returns a
23 :class:`~muse.domain.MergeResult` with an empty ``conflicts`` list; CRDT
24 joins never fail.
25
26 File-based helpers:
27
28 - :func:`find_merge_base` — lowest common ancestor (LCA) of two commits.
29 - :func:`read_merge_state` — detect and load an in-progress merge.
30 - :func:`write_merge_state` — persist conflict state before exiting.
31 - :func:`clear_merge_state` — remove MERGE_STATE.json after resolution.
32 - :func:`apply_resolution` — restore a specific object version to muse-work/.
33
34 ``MERGE_STATE.json`` schema
35 ---------------------------
36
37 .. code-block:: json
38
39 {
40 "base_commit": "abc123...",
41 "ours_commit": "def456...",
42 "theirs_commit": "789abc...",
43 "conflict_paths": ["beat.mid", "lead.mp3"],
44 "other_branch": "feature/experiment"
45 }
46
47 ``other_branch`` is optional; all other fields are required when conflicts exist.
48 """
49
50 from __future__ import annotations
51
52 import json
53 import logging
54 import pathlib
55 from collections import deque
56 from dataclasses import dataclass, field
57 from typing import TYPE_CHECKING, TypedDict
58
59 if TYPE_CHECKING:
60 from muse.domain import MergeResult, MuseDomainPlugin
61
62 logger = logging.getLogger(__name__)
63
64 _MERGE_STATE_FILENAME = "MERGE_STATE.json"
65
66
67 # ---------------------------------------------------------------------------
68 # Wire-format TypedDict
69 # ---------------------------------------------------------------------------
70
71
72 class MergeStatePayload(TypedDict, total=False):
73 """JSON-serialisable form of an in-progress merge state."""
74
75 base_commit: str
76 ours_commit: str
77 theirs_commit: str
78 conflict_paths: list[str]
79 other_branch: str
80
81
82 # ---------------------------------------------------------------------------
83 # MergeState dataclass
84 # ---------------------------------------------------------------------------
85
86
87 @dataclass(frozen=True)
88 class MergeState:
89 """Describes an in-progress merge with unresolved conflicts."""
90
91 conflict_paths: list[str] = field(default_factory=list)
92 base_commit: str | None = None
93 ours_commit: str | None = None
94 theirs_commit: str | None = None
95 other_branch: str | None = None
96
97
98 # ---------------------------------------------------------------------------
99 # Filesystem helpers
100 # ---------------------------------------------------------------------------
101
102
103 def read_merge_state(root: pathlib.Path) -> MergeState | None:
104 """Return :class:`MergeState` if a merge is in progress, otherwise ``None``."""
105 merge_state_path = root / ".muse" / _MERGE_STATE_FILENAME
106 if not merge_state_path.exists():
107 return None
108 try:
109 data = json.loads(merge_state_path.read_text())
110 except (json.JSONDecodeError, OSError) as exc:
111 logger.warning("⚠️ Failed to read %s: %s", _MERGE_STATE_FILENAME, exc)
112 return None
113
114 raw_conflicts = data.get("conflict_paths", [])
115 conflict_paths: list[str] = (
116 [str(c) for c in raw_conflicts] if isinstance(raw_conflicts, list) else []
117 )
118
119 def _str_or_none(key: str) -> str | None:
120 val = data.get(key)
121 return str(val) if val is not None else None
122
123 return MergeState(
124 conflict_paths=conflict_paths,
125 base_commit=_str_or_none("base_commit"),
126 ours_commit=_str_or_none("ours_commit"),
127 theirs_commit=_str_or_none("theirs_commit"),
128 other_branch=_str_or_none("other_branch"),
129 )
130
131
132 def write_merge_state(
133 root: pathlib.Path,
134 *,
135 base_commit: str,
136 ours_commit: str,
137 theirs_commit: str,
138 conflict_paths: list[str],
139 other_branch: str | None = None,
140 ) -> None:
141 """Write ``.muse/MERGE_STATE.json`` to signal an in-progress conflicted merge.
142
143 Called by the ``muse merge`` command when the merge produces at least one
144 conflict that cannot be auto-resolved. The file is read back by
145 :func:`read_merge_state` on subsequent ``muse status`` and ``muse commit``
146 invocations to surface conflict state to the user.
147
148 Args:
149 root: Repository root (parent of ``.muse/``).
150 base_commit: Commit ID of the merge base (common ancestor).
151 ours_commit: Commit ID of the current branch (HEAD) at merge time.
152 theirs_commit: Commit ID of the branch being merged in.
153 conflict_paths: Sorted list of workspace-relative POSIX paths with
154 unresolvable conflicts.
155 other_branch: Name of the branch being merged in; stored for
156 informational display but not required for resolution.
157 """
158 merge_state_path = root / ".muse" / _MERGE_STATE_FILENAME
159 payload: MergeStatePayload = {
160 "base_commit": base_commit,
161 "ours_commit": ours_commit,
162 "theirs_commit": theirs_commit,
163 "conflict_paths": sorted(conflict_paths),
164 }
165 if other_branch is not None:
166 payload["other_branch"] = other_branch
167 merge_state_path.write_text(json.dumps(payload, indent=2))
168 logger.info("✅ Wrote MERGE_STATE.json with %d conflict(s)", len(conflict_paths))
169
170
171 def clear_merge_state(root: pathlib.Path) -> None:
172 """Remove ``.muse/MERGE_STATE.json`` after a successful merge or resolution."""
173 merge_state_path = root / ".muse" / _MERGE_STATE_FILENAME
174 if merge_state_path.exists():
175 merge_state_path.unlink()
176 logger.debug("✅ Cleared MERGE_STATE.json")
177
178
179 def apply_resolution(
180 root: pathlib.Path,
181 rel_path: str,
182 object_id: str,
183 ) -> None:
184 """Restore a specific object version to ``muse-work/<rel_path>``.
185
186 Used by the ``muse merge --resolve`` workflow: after a user has chosen
187 which version of a conflicting file to keep, this function writes that
188 version into the working directory so ``muse commit`` can snapshot it.
189
190 Args:
191 root: Repository root (parent of ``.muse/``).
192 rel_path: Workspace-relative POSIX path of the conflicting file.
193 object_id: SHA-256 of the chosen resolution content in the object store.
194
195 Raises:
196 FileNotFoundError: When *object_id* is not present in the local store.
197 """
198 from muse.core.object_store import read_object
199
200 content = read_object(root, object_id)
201 if content is None:
202 raise FileNotFoundError(
203 f"Object {object_id[:8]} for '{rel_path}' not found in local store."
204 )
205 dest = root / "muse-work" / rel_path
206 dest.parent.mkdir(parents=True, exist_ok=True)
207 dest.write_bytes(content)
208 logger.debug("✅ Restored '%s' from object %s", rel_path, object_id[:8])
209
210
211 def is_conflict_resolved(merge_state: MergeState, rel_path: str) -> bool:
212 """Return ``True`` if *rel_path* is NOT listed as a conflict in *merge_state*."""
213 return rel_path not in merge_state.conflict_paths
214
215
216 # ---------------------------------------------------------------------------
217 # Pure merge functions (no I/O)
218 # ---------------------------------------------------------------------------
219
220
221 def diff_snapshots(
222 base_manifest: dict[str, str],
223 other_manifest: dict[str, str],
224 ) -> set[str]:
225 """Return the set of paths that differ between *base_manifest* and *other_manifest*.
226
227 A path is "different" if it was added (in *other* but not *base*), deleted
228 (in *base* but not *other*), or modified (present in both with different
229 content hashes).
230
231 Args:
232 base_manifest: Path → content-hash map for the ancestor snapshot.
233 other_manifest: Path → content-hash map for the other snapshot.
234
235 Returns:
236 Set of workspace-relative POSIX paths that differ.
237 """
238 base_paths = set(base_manifest.keys())
239 other_paths = set(other_manifest.keys())
240 added = other_paths - base_paths
241 deleted = base_paths - other_paths
242 common = base_paths & other_paths
243 modified = {p for p in common if base_manifest[p] != other_manifest[p]}
244 return added | deleted | modified
245
246
247 def detect_conflicts(
248 ours_changed: set[str],
249 theirs_changed: set[str],
250 ) -> set[str]:
251 """Return paths changed on *both* branches since the merge base."""
252 return ours_changed & theirs_changed
253
254
255 def apply_merge(
256 base_manifest: dict[str, str],
257 ours_manifest: dict[str, str],
258 theirs_manifest: dict[str, str],
259 ours_changed: set[str],
260 theirs_changed: set[str],
261 conflict_paths: set[str],
262 ) -> dict[str, str]:
263 """Build the merged snapshot manifest for a conflict-free 3-way merge.
264
265 Starts from *base_manifest* and applies non-conflicting changes from both
266 branches:
267
268 - Ours-only changes (in *ours_changed* but not *conflict_paths*) are taken
269 from *ours_manifest*. Deletions are handled by the absence of the path
270 in *ours_manifest*.
271 - Theirs-only changes (in *theirs_changed* but not *conflict_paths*) are
272 taken from *theirs_manifest* by the same logic.
273 - Paths in *conflict_paths* are excluded — callers must resolve them
274 separately before producing a final merged snapshot.
275
276 Args:
277 base_manifest: Path → content-hash for the common ancestor.
278 ours_manifest: Path → content-hash for our branch.
279 theirs_manifest: Path → content-hash for their branch.
280 ours_changed: Paths changed by our branch (from :func:`diff_snapshots`).
281 theirs_changed: Paths changed by their branch.
282 conflict_paths: Paths with concurrent changes — excluded from output.
283
284 Returns:
285 Merged path → content-hash mapping; conflict paths are absent.
286 """
287 merged: dict[str, str] = dict(base_manifest)
288 for path in ours_changed - conflict_paths:
289 if path in ours_manifest:
290 merged[path] = ours_manifest[path]
291 else:
292 merged.pop(path, None)
293 for path in theirs_changed - conflict_paths:
294 if path in theirs_manifest:
295 merged[path] = theirs_manifest[path]
296 else:
297 merged.pop(path, None)
298 return merged
299
300
301 # ---------------------------------------------------------------------------
302 # CRDT convergent join
303 # ---------------------------------------------------------------------------
304
305
306 def crdt_join_snapshots(
307 plugin: MuseDomainPlugin,
308 a_snapshot: dict[str, str],
309 b_snapshot: dict[str, str],
310 a_vclock: dict[str, int],
311 b_vclock: dict[str, int],
312 a_crdt_state: dict[str, str],
313 b_crdt_state: dict[str, str],
314 domain: str,
315 ) -> MergeResult:
316 """Convergent CRDT merge — always succeeds, no conflicts possible.
317
318 Detects :class:`~muse.domain.CRDTPlugin` support via ``isinstance`` and
319 delegates to ``plugin.join(a, b)``. The returned :class:`~muse.domain.MergeResult`
320 always has an empty ``conflicts`` list — the defining property of CRDT joins.
321
322 This function is the CRDT entry point for the ``muse merge`` command.
323 It is only called when ``DomainSchema.merge_mode == "crdt"`` AND the plugin
324 passes the ``isinstance(plugin, CRDTPlugin)`` check.
325
326 Args:
327 plugin: The loaded domain plugin instance.
328 a_snapshot: ``files`` mapping (path → content hash) for replica A.
329 b_snapshot: ``files`` mapping (path → content hash) for replica B.
330 a_vclock: Vector clock ``{agent_id: count}`` for replica A.
331 b_vclock: Vector clock ``{agent_id: count}`` for replica B.
332 a_crdt_state: CRDT metadata hashes (path → blob hash) for replica A.
333 b_crdt_state: CRDT metadata hashes (path → blob hash) for replica B.
334 domain: Domain name string (e.g. ``"midi"``).
335
336 Returns:
337 A :class:`~muse.domain.MergeResult` with the joined snapshot and an
338 empty ``conflicts`` list.
339
340 Raises:
341 TypeError: When *plugin* does not implement the
342 :class:`~muse.domain.CRDTPlugin` protocol.
343 """
344 from muse.domain import CRDTPlugin, CRDTSnapshotManifest, MergeResult, StateSnapshot
345
346 if not isinstance(plugin, CRDTPlugin):
347 raise TypeError(
348 f"crdt_join_snapshots: plugin {type(plugin).__name__!r} does not "
349 "implement CRDTPlugin — cannot use CRDT join path."
350 )
351
352 a_crdt: CRDTSnapshotManifest = {
353 "files": a_snapshot,
354 "domain": domain,
355 "vclock": a_vclock,
356 "crdt_state": a_crdt_state,
357 "schema_version": 1,
358 }
359 b_crdt: CRDTSnapshotManifest = {
360 "files": b_snapshot,
361 "domain": domain,
362 "vclock": b_vclock,
363 "crdt_state": b_crdt_state,
364 "schema_version": 1,
365 }
366
367 result_crdt = plugin.join(a_crdt, b_crdt)
368 plain_snapshot: StateSnapshot = plugin.from_crdt_state(result_crdt)
369
370 return MergeResult(
371 merged=plain_snapshot,
372 conflicts=[],
373 applied_strategies={},
374 )
375
376
377 # ---------------------------------------------------------------------------
378 # File-based merge base finder
379 # ---------------------------------------------------------------------------
380
381
382 def find_merge_base(
383 repo_root: pathlib.Path,
384 commit_id_a: str,
385 commit_id_b: str,
386 ) -> str | None:
387 """Find the Lowest Common Ancestor (LCA) of two commits.
388
389 Uses BFS to collect all ancestors of *commit_id_a* (inclusive), then
390 walks *commit_id_b*'s ancestor graph (BFS) until the first node found
391 in *a*'s ancestor set is reached.
392
393 Args:
394 repo_root: The repository root directory.
395 commit_id_a: First commit ID (e.g., current branch HEAD).
396 commit_id_b: Second commit ID (e.g., target branch HEAD).
397
398 Returns:
399 The LCA commit ID, or ``None`` if the commits share no common ancestor.
400 """
401 from muse.core.store import read_commit
402
403 def _all_ancestors(start: str) -> set[str]:
404 visited: set[str] = set()
405 queue: deque[str] = deque([start])
406 while queue:
407 cid = queue.popleft()
408 if cid in visited:
409 continue
410 visited.add(cid)
411 commit = read_commit(repo_root, cid)
412 if commit is None:
413 continue
414 if commit.parent_commit_id:
415 queue.append(commit.parent_commit_id)
416 if commit.parent2_commit_id:
417 queue.append(commit.parent2_commit_id)
418 return visited
419
420 a_ancestors = _all_ancestors(commit_id_a)
421
422 visited_b: set[str] = set()
423 queue_b: deque[str] = deque([commit_id_b])
424 while queue_b:
425 cid = queue_b.popleft()
426 if cid in visited_b:
427 continue
428 visited_b.add(cid)
429 if cid in a_ancestors:
430 return cid
431 commit = read_commit(repo_root, cid)
432 if commit is None:
433 continue
434 if commit.parent_commit_id:
435 queue_b.append(commit.parent_commit_id)
436 if commit.parent2_commit_id:
437 queue_b.append(commit.parent2_commit_id)
438
439 return None