aaronrene / gabriel-muse public
merge_engine.py python
505 lines 18.0 KB
Raw
sha256:cf6265cea8c21d9228d90dec13ef6ec2dab5103d466db9cc4590681832de4bf8 docs(KD-STAGING): sync governance after KD-6b DONE Human 13 days 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 where both branches made DIVERGENT changes.
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 state/.
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 from muse._version import __version__
60 from muse.core._types import Manifest
61 from muse.core.store import write_text_atomic
62 from muse.core.validation import contain_path, validate_object_id, validate_ref_id
63
64 if TYPE_CHECKING:
65 from muse.domain import MergeResult, MuseDomainPlugin
66
67 logger = logging.getLogger(__name__)
68
69 type VectorClock = dict[str, int] # agent_id → logical clock count
70 type CRDTState = dict[str, str] # path → blob hash for CRDT metadata
71
72 _MERGE_STATE_FILENAME = "MERGE_STATE.json"
73
74
75 # ---------------------------------------------------------------------------
76 # Wire-format TypedDict
77 # ---------------------------------------------------------------------------
78
79
80 class MergeStatePayload(TypedDict, total=False):
81 """JSON-serialisable form of an in-progress merge state."""
82
83 base_commit: str
84 ours_commit: str
85 theirs_commit: str
86 conflict_paths: list[str]
87 other_branch: str
88
89
90 # ---------------------------------------------------------------------------
91 # MergeState dataclass
92 # ---------------------------------------------------------------------------
93
94
95 @dataclass(frozen=True)
96 class MergeState:
97 """Describes an in-progress merge with unresolved conflicts."""
98
99 conflict_paths: list[str] = field(default_factory=list)
100 base_commit: str | None = None
101 ours_commit: str | None = None
102 theirs_commit: str | None = None
103 other_branch: str | None = None
104
105
106 # ---------------------------------------------------------------------------
107 # Filesystem helpers
108 # ---------------------------------------------------------------------------
109
110
111 def read_merge_state(root: pathlib.Path) -> MergeState | None:
112 """Return :class:`MergeState` if a merge is in progress, otherwise ``None``."""
113 merge_state_path = root / ".muse" / _MERGE_STATE_FILENAME
114 if not merge_state_path.exists():
115 return None
116 try:
117 data = json.loads(merge_state_path.read_text())
118 except (json.JSONDecodeError, OSError) as exc:
119 logger.warning("⚠️ Failed to read %s: %s", _MERGE_STATE_FILENAME, exc)
120 return None
121
122 raw_conflicts = data.get("conflict_paths", [])
123 safe_conflict_paths: list[str] = []
124 if isinstance(raw_conflicts, list):
125 for c in raw_conflicts:
126 try:
127 contained = contain_path(root, str(c))
128 # Store as relative POSIX string for display; contain_path already validated it.
129 safe_conflict_paths.append(contained.relative_to(root.resolve()).as_posix())
130 except ValueError:
131 logger.warning(
132 "⚠️ Skipping unsafe conflict path %r from MERGE_STATE.json", c
133 )
134
135 def _validated_ref(key: str) -> str | None:
136 val = data.get(key)
137 if val is None:
138 return None
139 s = str(val)
140 try:
141 validate_ref_id(s)
142 return s
143 except ValueError:
144 logger.warning(
145 "⚠️ Invalid %s %r in MERGE_STATE.json — ignoring", key, s
146 )
147 return None
148
149 def _str_or_none(key: str) -> str | None:
150 val = data.get(key)
151 return str(val) if val is not None else None
152
153 return MergeState(
154 conflict_paths=safe_conflict_paths,
155 base_commit=_validated_ref("base_commit"),
156 ours_commit=_validated_ref("ours_commit"),
157 theirs_commit=_validated_ref("theirs_commit"),
158 other_branch=_str_or_none("other_branch"),
159 )
160
161
162 def write_merge_state(
163 root: pathlib.Path,
164 *,
165 base_commit: str,
166 ours_commit: str,
167 theirs_commit: str,
168 conflict_paths: list[str],
169 other_branch: str | None = None,
170 ) -> None:
171 """Write ``.muse/MERGE_STATE.json`` to signal an in-progress conflicted merge.
172
173 Called by the ``muse merge`` command when the merge produces at least one
174 conflict that cannot be auto-resolved. The file is read back by
175 :func:`read_merge_state` on subsequent ``muse status`` and ``muse commit``
176 invocations to surface conflict state to the user.
177
178 Args:
179 root: Repository root (parent of ``.muse/``).
180 base_commit: Commit ID of the merge base (common ancestor).
181 ours_commit: Commit ID of the current branch (HEAD) at merge time.
182 theirs_commit: Commit ID of the branch being merged in.
183 conflict_paths: Sorted list of workspace-relative POSIX paths with
184 unresolvable conflicts.
185 other_branch: Name of the branch being merged in; stored for
186 informational display but not required for resolution.
187 """
188 merge_state_path = root / ".muse" / _MERGE_STATE_FILENAME
189 payload: MergeStatePayload = {
190 "base_commit": base_commit,
191 "ours_commit": ours_commit,
192 "theirs_commit": theirs_commit,
193 "conflict_paths": sorted(conflict_paths),
194 }
195 if other_branch is not None:
196 payload["other_branch"] = other_branch
197 write_text_atomic(merge_state_path, json.dumps(payload, indent=2))
198 logger.info("✅ Wrote MERGE_STATE.json with %d conflict(s)", len(conflict_paths))
199
200
201 def clear_merge_state(root: pathlib.Path) -> None:
202 """Remove ``.muse/MERGE_STATE.json`` after a successful merge or resolution."""
203 merge_state_path = root / ".muse" / _MERGE_STATE_FILENAME
204 if merge_state_path.exists():
205 merge_state_path.unlink()
206 logger.debug("✅ Cleared MERGE_STATE.json")
207
208
209 def apply_resolution(
210 root: pathlib.Path,
211 rel_path: str,
212 object_id: str,
213 ) -> None:
214 """Restore a specific object version to the working tree at ``<rel_path>``.
215
216 Used by the ``muse merge --resolve`` workflow: after a user has chosen
217 which version of a conflicting file to keep, this function writes that
218 version into the working tree so ``muse commit`` can snapshot it.
219
220 Args:
221 root: Repository root (parent of ``.muse/``).
222 rel_path: Workspace-relative POSIX path of the conflicting file.
223 object_id: SHA-256 of the chosen resolution content in the object store.
224
225 Raises:
226 FileNotFoundError: When *object_id* is not present in the local store.
227 """
228 from muse.core.object_store import read_object
229
230 validate_object_id(object_id)
231 dest = contain_path(root, rel_path)
232
233 content = read_object(root, object_id)
234 if content is None:
235 raise FileNotFoundError(
236 f"Object {object_id[:8]} for '{rel_path}' not found in local store."
237 )
238 dest.parent.mkdir(parents=True, exist_ok=True)
239 dest.write_bytes(content)
240 logger.debug("✅ Restored '%s' from object %s", rel_path, object_id[:8])
241
242
243
244 # ---------------------------------------------------------------------------
245 # Pure merge functions (no I/O)
246 # ---------------------------------------------------------------------------
247
248
249 def diff_snapshots(
250 base_manifest: Manifest,
251 other_manifest: Manifest,
252 ) -> set[str]:
253 """Return the set of paths that differ between *base_manifest* and *other_manifest*.
254
255 A path is "different" if it was added (in *other* but not *base*), deleted
256 (in *base* but not *other*), or modified (present in both with different
257 content hashes).
258
259 Args:
260 base_manifest: Path → content-hash map for the ancestor snapshot.
261 other_manifest: Path → content-hash map for the other snapshot.
262
263 Returns:
264 Set of workspace-relative POSIX paths that differ.
265 """
266 base_paths = set(base_manifest.keys())
267 other_paths = set(other_manifest.keys())
268 added = other_paths - base_paths
269 deleted = base_paths - other_paths
270 common = base_paths & other_paths
271 modified = {p for p in common if base_manifest[p] != other_manifest[p]}
272 return added | deleted | modified
273
274
275 def detect_conflicts(
276 ours_changed: set[str],
277 theirs_changed: set[str],
278 ours_manifest: Manifest,
279 theirs_manifest: Manifest,
280 ) -> set[str]:
281 """Return paths where both branches made DIVERGENT changes since the merge base.
282
283 Two branches conflict on a path only when they both changed it AND arrived at
284 DIFFERENT results. Convergent changes — both deleted the same file, or both
285 added/modified it to the same content hash — are auto-resolved and are NOT
286 returned as conflicts.
287
288 Examples of convergent (non-conflict) changes:
289 - Both branches deleted the same file → agreed on deletion, not a conflict.
290 - Both branches independently added the same file with identical content →
291 agreed on the new content, not a conflict.
292
293 Args:
294 ours_changed: Paths changed by our branch (from :func:`diff_snapshots`).
295 theirs_changed: Paths changed by their branch.
296 ours_manifest: Path → content-hash for our branch's snapshot.
297 theirs_manifest: Path → content-hash for their branch's snapshot.
298
299 Returns:
300 Set of paths where both branches made changes that disagree on the result.
301 """
302 return {
303 path
304 for path in ours_changed & theirs_changed
305 if ours_manifest.get(path) != theirs_manifest.get(path)
306 }
307
308
309 def apply_merge(
310 base_manifest: Manifest,
311 ours_manifest: Manifest,
312 theirs_manifest: Manifest,
313 ours_changed: set[str],
314 theirs_changed: set[str],
315 conflict_paths: set[str],
316 ) -> Manifest:
317 """Build the merged snapshot manifest for a conflict-free 3-way merge.
318
319 Starts from *base_manifest* and applies non-conflicting changes from both
320 branches:
321
322 - Ours-only changes (in *ours_changed* but not *conflict_paths*) are taken
323 from *ours_manifest*. Deletions are handled by the absence of the path
324 in *ours_manifest*.
325 - Theirs-only changes (in *theirs_changed* but not *conflict_paths*) are
326 taken from *theirs_manifest* by the same logic.
327 - Paths in *conflict_paths* are excluded — callers must resolve them
328 separately before producing a final merged snapshot.
329
330 Args:
331 base_manifest: Path → content-hash for the common ancestor.
332 ours_manifest: Path → content-hash for our branch.
333 theirs_manifest: Path → content-hash for their branch.
334 ours_changed: Paths changed by our branch (from :func:`diff_snapshots`).
335 theirs_changed: Paths changed by their branch.
336 conflict_paths: Paths with concurrent changes — excluded from output.
337
338 Returns:
339 Merged path → content-hash mapping; conflict paths are absent.
340 """
341 merged: Manifest = dict(base_manifest)
342 for path in ours_changed - conflict_paths:
343 if path in ours_manifest:
344 merged[path] = ours_manifest[path]
345 else:
346 merged.pop(path, None)
347 for path in theirs_changed - conflict_paths:
348 if path in theirs_manifest:
349 merged[path] = theirs_manifest[path]
350 else:
351 merged.pop(path, None)
352 return merged
353
354
355 # ---------------------------------------------------------------------------
356 # CRDT convergent join
357 # ---------------------------------------------------------------------------
358
359
360 def crdt_join_snapshots(
361 plugin: MuseDomainPlugin,
362 a_snapshot: Manifest,
363 b_snapshot: Manifest,
364 a_vclock: VectorClock,
365 b_vclock: VectorClock,
366 a_crdt_state: CRDTState,
367 b_crdt_state: CRDTState,
368 domain: str,
369 ) -> MergeResult:
370 """Convergent CRDT merge — always succeeds, no conflicts possible.
371
372 Detects :class:`~muse.domain.CRDTPlugin` support via ``isinstance`` and
373 delegates to ``plugin.join(a, b)``. The returned :class:`~muse.domain.MergeResult`
374 always has an empty ``conflicts`` list — the defining property of CRDT joins.
375
376 This function is the CRDT entry point for the ``muse merge`` command.
377 It is only called when ``DomainSchema.merge_mode == "crdt"`` AND the plugin
378 passes the ``isinstance(plugin, CRDTPlugin)`` check.
379
380 Args:
381 plugin: The loaded domain plugin instance.
382 a_snapshot: ``files`` mapping (path → content hash) for replica A.
383 b_snapshot: ``files`` mapping (path → content hash) for replica B.
384 a_vclock: Vector clock ``{agent_id: count}`` for replica A.
385 b_vclock: Vector clock ``{agent_id: count}`` for replica B.
386 a_crdt_state: CRDT metadata hashes (path → blob hash) for replica A.
387 b_crdt_state: CRDT metadata hashes (path → blob hash) for replica B.
388 domain: Domain name string (e.g. ``"midi"``).
389
390 Returns:
391 A :class:`~muse.domain.MergeResult` with the joined snapshot and an
392 empty ``conflicts`` list.
393
394 Raises:
395 TypeError: When *plugin* does not implement the
396 :class:`~muse.domain.CRDTPlugin` protocol.
397 """
398 from muse.domain import CRDTPlugin, CRDTSnapshotManifest, MergeResult, StateSnapshot
399
400 if not isinstance(plugin, CRDTPlugin):
401 raise TypeError(
402 f"crdt_join_snapshots: plugin {type(plugin).__name__!r} does not "
403 "implement CRDTPlugin — cannot use CRDT join path."
404 )
405
406 a_crdt: CRDTSnapshotManifest = {
407 "files": a_snapshot,
408 "domain": domain,
409 "vclock": a_vclock,
410 "crdt_state": a_crdt_state,
411 "schema_version": __version__,
412 }
413 b_crdt: CRDTSnapshotManifest = {
414 "files": b_snapshot,
415 "domain": domain,
416 "vclock": b_vclock,
417 "crdt_state": b_crdt_state,
418 "schema_version": __version__,
419 }
420
421 result_crdt = plugin.join(a_crdt, b_crdt)
422 plain_snapshot: StateSnapshot = plugin.from_crdt_state(result_crdt)
423
424 return MergeResult(
425 merged=plain_snapshot,
426 conflicts=[],
427 applied_strategies={},
428 )
429
430
431 # ---------------------------------------------------------------------------
432 # File-based merge base finder
433 # ---------------------------------------------------------------------------
434
435
436 def find_merge_base(
437 repo_root: pathlib.Path,
438 commit_id_a: str,
439 commit_id_b: str,
440 ) -> str | None:
441 """Find the Lowest Common Ancestor (LCA) of two commits.
442
443 Uses simultaneous bidirectional BFS — expanding both frontiers one step
444 at a time and stopping as soon as any commit appears in both seen sets.
445 This is O(distance_to_LCA) rather than O(total_history).
446
447 Args:
448 repo_root: The repository root directory.
449 commit_id_a: First commit ID (e.g., current branch HEAD).
450 commit_id_b: Second commit ID (e.g., target branch HEAD).
451
452 Returns:
453 The LCA commit ID, or ``None`` if the commits share no common ancestor.
454 """
455 from muse.cli.config import get_limit
456 from muse.core.errors import MuseCLIError
457 from muse.core.store import read_commit
458
459 max_ancestors = get_limit("max_ancestors", repo_root)
460
461 if commit_id_a == commit_id_b:
462 return commit_id_a
463
464 seen_a: set[str] = {commit_id_a}
465 seen_b: set[str] = {commit_id_b}
466
467 frontier_a: deque[str] = deque([commit_id_a])
468 frontier_b: deque[str] = deque([commit_id_b])
469 total_visited = 0
470
471 while frontier_a or frontier_b:
472 if total_visited >= max_ancestors:
473 raise MuseCLIError(
474 f"Ancestor graph exceeds {max_ancestors:,} commits during "
475 "merge-base search — the repository history is too deep or "
476 "the DAG may be malformed. "
477 f"Raise [limits] max_ancestors in .muse/config.toml "
478 f"(current cap: {max_ancestors:,})."
479 )
480
481 if frontier_a:
482 cid = frontier_a.popleft()
483 total_visited += 1
484 commit = read_commit(repo_root, cid)
485 if commit is not None:
486 for parent in (commit.parent_commit_id, commit.parent2_commit_id):
487 if parent is not None and parent not in seen_a:
488 seen_a.add(parent)
489 if parent in seen_b:
490 return parent
491 frontier_a.append(parent)
492
493 if frontier_b:
494 cid = frontier_b.popleft()
495 total_visited += 1
496 commit = read_commit(repo_root, cid)
497 if commit is not None:
498 for parent in (commit.parent_commit_id, commit.parent2_commit_id):
499 if parent is not None and parent not in seen_b:
500 seen_b.add(parent)
501 if parent in seen_a:
502 return parent
503 frontier_b.append(parent)
504
505 return None
File History 1 commit
sha256:cf6265cea8c21d9228d90dec13ef6ec2dab5103d466db9cc4590681832de4bf8 docs(KD-STAGING): sync governance after KD-6b DONE Human 13 days ago