merge_engine.py
file-level
1
files
1
commits
0
hotspots
0
🧊 dead
0
💥 blast risk
| 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 |