gabriel / muse public
cohen_transform.py python
597 lines 22.6 KB
Raw
sha256:b636f72dcba9e190afb980bece906fa5b717fbde014b76ef023df8cb96e01eb9 docs: expand cache plan with all seven testing tiers and do… Sonnet 4.6 136 days ago
1 """cohen_transform.py — Three-way line-level merge with Manyana-style action labels.
2
3 Named in honour of Bram Cohen (creator of BitTorrent, inventor of the Manyana
4 CRDT weave algorithm), whose conflict-presentation insight is the direct
5 inspiration for this module.
6
7 The Cohen Transform observation
8 --------------------------------
9 Traditional VCS tools display a merge conflict as two opaque blobs — "ours"
10 and "theirs" — and leave the user to reconstruct *what each side actually did*.
11 Bram Cohen's Manyana project labels every conflict hunk with the action and the
12 side that performed it:
13
14 <<<<<<< ours [deleted]
15 def calculate(x):
16 a = x * 2
17 ||||||| base
18 def calculate(x):
19 a = x * 2
20 b = a + 1
21 return b
22 ======= theirs [inserted]
23 logger.debug(f"a={a}")
24 >>>>>>> end conflict
25
26 You can immediately see: ours deleted a function, theirs inserted a line into
27 the middle of it. That is a structurally different level of information from
28 two unlabelled blobs.
29
30 Public API
31 ----------
32 three_way_merge_lines(base, ours, theirs, ...)
33 Core merge function. Returns (merged_lines, has_conflict).
34
35 MergeRegion
36 Dataclass representing one segment of the three-way analysis.
37
38 classify_action(base_lines, other_lines)
39 Classify a change as 'inserted', 'deleted', or 'modified'.
40
41 annotate_hunk_action(hunk_lines, side_label)
42 Post-process a unified-diff hunk list, rewriting @@ headers with
43 action labels for use in ``muse diff --conflict`` output.
44
45 format_conflict_diff(path, root, base_manifest, ours_manifest, theirs_manifest,
46 read_object_fn, *, use_color, ours_label, theirs_label)
47 Render a Manyana-style two-sided labeled diff for a single conflicting file.
48 Used by ``muse diff --conflict``.
49
50 References
51 ----------
52 - Bram Cohen, Manyana: https://github.com/bramcohen/manyana
53 - Bram Cohen's blog: https://bramcohen.com/
54 """
55
56 from __future__ import annotations
57
58 import difflib
59 import pathlib
60 from dataclasses import dataclass, field
61 from typing import Callable, Sequence
62
63 type _ManifestMap = dict[str, str]
64
65 # ── Public constants ──────────────────────────────────────────────────────────
66
67 #: Separator used between the two sides of a conflict-aware diff header.
68 CONFLICT_SEPARATOR = "═" * 54
69
70 #: Marker tokens — match git's diff3 style so editors recognise them, but
71 #: the action label suffix (e.g. ``[deleted]``) is the Cohen extension.
72 _MARKER_OURS_PREFIX = "<<<<<<< "
73 _MARKER_BASE = "||||||| base"
74 _MARKER_SEP_PREFIX = "======= "
75 _MARKER_END = ">>>>>>> end conflict"
76
77
78 # ── Data classes ──────────────────────────────────────────────────────────────
79
80
81 @dataclass
82 class MergeRegion:
83 """One segment of a three-way merge analysis.
84
85 Attributes:
86 kind:
87 ``'stable'`` — identical in all three versions; output base.
88 ``'ours_only'`` — only ours changed from base; output ours.
89 ``'theirs_only'`` — only theirs changed from base; output theirs.
90 ``'both_same'`` — both sides made the same change; output either.
91 ``'conflict'`` — both sides changed differently; needs markers.
92 base_lines: Lines from the common ancestor for this segment.
93 ours_lines: Lines from the ours version for this segment.
94 theirs_lines: Lines from the theirs version for this segment.
95 """
96
97 kind: str
98 base_lines: list[str] = field(default_factory=list)
99 ours_lines: list[str] = field(default_factory=list)
100 theirs_lines: list[str] = field(default_factory=list)
101
102
103 # ── Core algorithm ────────────────────────────────────────────────────────────
104
105
106 def _find_sync_regions(
107 base: Sequence[str],
108 ours: Sequence[str],
109 theirs: Sequence[str],
110 ) -> list[tuple[int, int, int, int, int, int]]:
111 """Return maximal regions identical in all three sequences.
112
113 Each entry is ``(base_s, base_e, ours_s, ours_e, theirs_s, theirs_e)``
114 representing a contiguous block where
115 ``base[base_s:base_e] == ours[ours_s:ours_e] == theirs[theirs_s:theirs_e]``.
116
117 The algorithm finds base positions matched in BOTH ``base→ours`` and
118 ``base→theirs`` LCS runs, then groups them into maximal consecutive
119 triples (consecutive in base, ours, *and* theirs simultaneously).
120 """
121 sm_a = difflib.SequenceMatcher(None, base, ours, autojunk=False)
122 sm_b = difflib.SequenceMatcher(None, base, theirs, autojunk=False)
123
124 a_map: dict[int, int] = {} # base_pos → ours_pos
125 b_map: dict[int, int] = {} # base_pos → theirs_pos
126
127 for bi, ai, n in sm_a.get_matching_blocks():
128 for k in range(n):
129 a_map[bi + k] = ai + k
130
131 for bi, ti, n in sm_b.get_matching_blocks():
132 for k in range(n):
133 b_map[bi + k] = ti + k
134
135 stable = sorted(set(a_map) & set(b_map))
136 if not stable:
137 return []
138
139 sync_regions: list[tuple[int, int, int, int, int, int]] = []
140 run_bp = run_ap = run_tp = -1
141 # Use -2 so that the first stable element (bp=0) does not falsely satisfy
142 # ``bp == prev_bp + 1`` (which would be ``0 == -1 + 1 == 0``) and skip
143 # initialising the run variables, causing the entire sync region to be lost.
144 prev_bp = prev_ap = prev_tp = -2
145
146 for bp in stable:
147 ap = a_map[bp]
148 tp = b_map[bp]
149
150 if bp == prev_bp + 1 and ap == prev_ap + 1 and tp == prev_tp + 1:
151 # Extend current run.
152 prev_bp, prev_ap, prev_tp = bp, ap, tp
153 else:
154 # Flush previous run (if any) and start a new one.
155 if run_bp >= 0:
156 sync_regions.append((
157 run_bp, prev_bp + 1,
158 run_ap, prev_ap + 1,
159 run_tp, prev_tp + 1,
160 ))
161 run_bp, run_ap, run_tp = bp, ap, tp
162 prev_bp, prev_ap, prev_tp = bp, ap, tp
163
164 # Flush final run.
165 if run_bp >= 0:
166 sync_regions.append((
167 run_bp, prev_bp + 1,
168 run_ap, prev_ap + 1,
169 run_tp, prev_tp + 1,
170 ))
171
172 return sync_regions
173
174
175 def compute_regions(
176 base: Sequence[str],
177 ours: Sequence[str],
178 theirs: Sequence[str],
179 ) -> list[MergeRegion]:
180 """Decompose three sequences into a list of :class:`MergeRegion` objects.
181
182 Uses the sync-region algorithm: finds maximal blocks identical in all
183 three sequences (the "stable skeleton"), then classifies each gap between
184 stable blocks as one of:
185
186 - ``ours_only`` — only ours changed from base.
187 - ``theirs_only`` — only theirs changed from base.
188 - ``both_same`` — both changed to the same content (clean).
189 - ``conflict`` — both changed to different content.
190
191 Handles pure insertions (both sides insert different content at the same
192 base position) as conflicts with an empty base section.
193
194 Args:
195 base: Common ancestor lines (each ending with ``\\n`` or empty).
196 ours: Working-tree / our-branch lines.
197 theirs: Target-branch / their-branch lines.
198
199 Returns:
200 Ordered list of :class:`MergeRegion` objects covering the entire
201 three-way merge.
202 """
203 base = list(base)
204 ours = list(ours)
205 theirs = list(theirs)
206
207 sync_regions = _find_sync_regions(base, ours, theirs)
208
209 # Sentinel at each end so the loop below handles the leading and trailing
210 # unstable regions uniformly without special-casing.
211 sentinels: list[tuple[int, int, int, int, int, int]] = [
212 (0, 0, 0, 0, 0, 0),
213 *sync_regions,
214 (len(base), len(base), len(ours), len(ours), len(theirs), len(theirs)),
215 ]
216
217 regions: list[MergeRegion] = []
218
219 for idx in range(len(sentinels) - 1):
220 cur = sentinels[idx]
221 nxt = sentinels[idx + 1]
222
223 # ── Stable block (the sync region itself) ─────────────────────────
224 bs, be, as_, ae, ts, te = cur
225 if idx > 0 and be > bs:
226 regions.append(MergeRegion(
227 kind="stable",
228 base_lines=list(base[bs:be]),
229 ours_lines=list(ours[as_:ae]),
230 theirs_lines=list(theirs[ts:te]),
231 ))
232
233 # ── Unstable gap between this sync region and the next ────────────
234 nbs, nbe, nas, nae, nts, nte = nxt
235 b_chunk = list(base[be:nbs])
236 a_chunk = list(ours[ae:nas])
237 t_chunk = list(theirs[te:nts])
238
239 if not b_chunk and not a_chunk and not t_chunk:
240 continue
241
242 if a_chunk == b_chunk and t_chunk == b_chunk:
243 # All three identical — degenerate stable region (shouldn't
244 # normally occur given sync detection, but guard it).
245 regions.append(MergeRegion("stable", b_chunk, a_chunk, t_chunk))
246 elif a_chunk == b_chunk:
247 # Only theirs changed.
248 regions.append(MergeRegion("theirs_only", b_chunk, b_chunk, t_chunk))
249 elif t_chunk == b_chunk:
250 # Only ours changed.
251 regions.append(MergeRegion("ours_only", b_chunk, a_chunk, b_chunk))
252 elif a_chunk == t_chunk:
253 # Both sides made the same change — clean (take either).
254 regions.append(MergeRegion("both_same", b_chunk, a_chunk, t_chunk))
255 else:
256 # True conflict — both sides changed differently.
257 regions.append(MergeRegion("conflict", b_chunk, a_chunk, t_chunk))
258
259 return regions
260
261
262 # ── Action classification ─────────────────────────────────────────────────────
263
264
265 def classify_action(base_lines: list[str], other_lines: list[str]) -> str:
266 """Classify the action performed from *base_lines* to *other_lines*.
267
268 Returns one of:
269 - ``'inserted'`` — *other_lines* is non-empty, *base_lines* is empty.
270 - ``'deleted'`` — *base_lines* is non-empty, *other_lines* is empty.
271 - ``'modified'`` — both are non-empty but differ.
272
273 Used to annotate conflict markers with the Cohen-transform action label,
274 e.g. ``<<<<<<< ours [deleted]``.
275 """
276 if not base_lines and other_lines:
277 return "inserted"
278 if base_lines and not other_lines:
279 return "deleted"
280 return "modified"
281
282
283 def annotate_hunk_action(hunk_lines: list[str], side_label: str) -> list[str]:
284 """Rewrite ``@@`` hunk headers with a Manyana-style action annotation.
285
286 Scans the ``+``/``-`` lines in each hunk to classify the dominant action
287 on *side_label* (``'ours'`` or ``'theirs'``), then rewrites each ``@@``
288 header line from::
289
290 @@ -12,4 +12,4 @@
291
292 to::
293
294 @@ -12,4 +12,4 @@ [ours: deleted]
295 @@ -12,4 +12,4 @@ [theirs: inserted]
296 @@ -12,4 +12,4 @@ [ours: modified]
297
298 This is the direct translation of Bram Cohen's ``begin deleted left`` /
299 ``begin added right`` labeling into unified-diff format.
300
301 Args:
302 hunk_lines: Lines produced by :func:`difflib.unified_diff`, including
303 the ``---``/``+++`` header and all ``@@`` blocks.
304 side_label: Human-readable side identifier, e.g. ``'ours'`` or
305 ``'theirs'``.
306
307 Returns:
308 Annotated copy of *hunk_lines* with ``@@`` lines rewritten.
309 """
310 result: list[str] = []
311 # Collect lines in the current @@ block to classify when we see the next @@.
312 current_hunk_body: list[str] = []
313 pending_at: str | None = None # the @@ line waiting to be annotated
314
315 def _flush(body: list[str]) -> str:
316 """Classify and return the annotated @@ line."""
317 assert pending_at is not None
318 adds = sum(1 for ln in body if ln.startswith("+") and not ln.startswith("+++"))
319 dels = sum(1 for ln in body if ln.startswith("-") and not ln.startswith("---"))
320 if adds > 0 and dels == 0:
321 action = "inserted"
322 elif dels > 0 and adds == 0:
323 action = "deleted"
324 else:
325 action = "modified"
326 base_at = pending_at.rstrip()
327 # Remove any trailing existing annotation before appending a new one.
328 if " [" in base_at:
329 base_at = base_at[: base_at.rfind(" [")]
330 return f"{base_at} [{side_label}: {action}]"
331
332 for line in hunk_lines:
333 if line.startswith("@@"):
334 if pending_at is not None:
335 result.append(_flush(current_hunk_body))
336 result.extend(current_hunk_body)
337 current_hunk_body = []
338 pending_at = line
339 elif pending_at is not None:
340 current_hunk_body.append(line)
341 else:
342 result.append(line)
343
344 # Flush the final hunk.
345 if pending_at is not None:
346 result.append(_flush(current_hunk_body))
347 result.extend(current_hunk_body)
348
349 return result
350
351
352 # ── High-level merge function ─────────────────────────────────────────────────
353
354
355 def three_way_merge_lines(
356 base: Sequence[str],
357 ours: Sequence[str],
358 theirs: Sequence[str],
359 *,
360 label_ours: str = "ours",
361 label_base: str = "base",
362 label_theirs: str = "theirs",
363 ) -> tuple[list[str], bool]:
364 """Three-way line merge with Manyana-style labeled conflict markers.
365
366 Implements the Cohen Transform: conflict markers include an action label
367 (``[inserted]``, ``[deleted]``, or ``[modified]``) so the reader
368 immediately sees *what each side did*, not just *that they conflicted*.
369
370 Marker format (diff3 style with Cohen extensions)::
371
372 <<<<<<< ours [deleted]
373 [lines from ours — what ours changed base to]
374 ||||||| base
375 [lines from common ancestor — the original context]
376 ======= theirs [inserted]
377 [lines from theirs — what theirs changed base to]
378 >>>>>>> end conflict
379
380 The ``||||||| base`` section is always included (diff3 style) because it
381 gives both humans and agents the context needed to understand *why* each
382 side made its change.
383
384 Clean merge rules:
385 - Stable (no change on either side): output base unchanged.
386 - Ours-only change: output ours version.
387 - Theirs-only change: output theirs version.
388 - Both changed to the same content: output that content once.
389 - Both changed differently: emit conflict markers.
390
391 Args:
392 base: Lines from the common ancestor.
393 ours: Lines from our version (working tree or our branch).
394 theirs: Lines from their version (target branch).
395 label_ours: Label shown in the ``<<<<<<<`` marker. Defaults to
396 ``'ours'``.
397 label_base: Label shown in the ``|||||||`` marker. Defaults to
398 ``'base'``.
399 label_theirs: Label shown in the ``=======`` marker. Defaults to
400 ``'theirs'``.
401
402 Returns:
403 A ``(merged_lines, has_conflict)`` tuple. *merged_lines* is the
404 fully merged sequence; *has_conflict* is ``True`` when at least one
405 conflict block was written.
406 """
407 regions = compute_regions(base, ours, theirs)
408 merged: list[str] = []
409 has_conflict = False
410
411 for region in regions:
412 if region.kind == "stable":
413 merged.extend(region.base_lines)
414
415 elif region.kind == "ours_only":
416 merged.extend(region.ours_lines)
417
418 elif region.kind == "theirs_only":
419 merged.extend(region.theirs_lines)
420
421 elif region.kind == "both_same":
422 merged.extend(region.ours_lines)
423
424 else: # conflict
425 has_conflict = True
426 ours_action = classify_action(region.base_lines, region.ours_lines)
427 theirs_action = classify_action(region.base_lines, region.theirs_lines)
428
429 merged.append(f"{_MARKER_OURS_PREFIX}{label_ours} [{ours_action}]\n")
430 merged.extend(region.ours_lines)
431 merged.append(f"||||||| {label_base}\n")
432 merged.extend(region.base_lines)
433 merged.append(f"{_MARKER_SEP_PREFIX}{label_theirs} [{theirs_action}]\n")
434 merged.extend(region.theirs_lines)
435 merged.append(f"{_MARKER_END}\n")
436
437 return merged, has_conflict
438
439
440 # ── Conflict-diff renderer (for muse diff --conflict) ────────────────────────
441
442
443 def format_conflict_diff(
444 path: str,
445 root: pathlib.Path,
446 base_manifest: dict[str, str],
447 ours_manifest: dict[str, str],
448 theirs_manifest: dict[str, str],
449 read_object_fn: Callable[[pathlib.Path, str], bytes | None],
450 *,
451 use_color: bool = False,
452 ours_label: str = "ours",
453 theirs_label: str = "theirs",
454 ) -> list[str]:
455 """Render a labeled two-sided diff for a single conflicting file.
456
457 Produces a Cohen-transform conflict view: two separate unified diffs
458 (``base→ours`` and ``base→theirs``), each with hunk headers annotated
459 with the action performed by that side. This replaces the opaque
460 ``<<<<<<< / ======= / >>>>>>>`` blob with a clear narrative of *what
461 each side did*.
462
463 Example output::
464
465 ══════════════════════════════════════════════════════
466 CONFLICT src/utils.py
467 ══════════════════════════════════════════════════════
468 [ours] what ours changed from base
469 --- base/src/utils.py
470 +++ ours/src/utils.py
471 @@ -12,4 +12,4 @@ [ours: deleted]
472 - def calculate(x):
473 - return x * 2
474 + def compute(x):
475 + return x * 3
476
477 [theirs] what theirs changed from base
478 --- base/src/utils.py
479 +++ theirs/src/utils.py
480 @@ -12,4 +12,4 @@ [theirs: modified]
481 def calculate(x):
482 - return x * 2
483 + return x * 4
484
485 Args:
486 path: Workspace-relative POSIX path of the conflicting file.
487 root: Repository root (used to read objects from the store).
488 base_manifest: Manifest of the merge-base commit.
489 ours_manifest: Manifest of our branch at merge time.
490 theirs_manifest: Manifest of their branch.
491 read_object_fn: Callable ``(root, object_id) → bytes | None``.
492 use_color: When ``True``, emit ANSI colour escapes.
493 ours_label: Human-readable label for the ours side (e.g. the
494 branch name).
495 theirs_label: Human-readable label for the theirs side.
496
497 Returns:
498 A list of text lines (each *without* a trailing newline) ready to
499 print. Returns an empty list when no diff exists for this path.
500 """
501 def _read_lines(manifest: _ManifestMap, fallback_disk: bool = False) -> list[str]:
502 oid = manifest.get(path)
503 if oid:
504 raw = read_object_fn(root, oid)
505 if raw is not None:
506 text = raw.decode("utf-8", errors="replace")
507 return text.splitlines(keepends=True)
508 if fallback_disk:
509 disk = root / path
510 if disk.is_file():
511 return disk.read_text(encoding="utf-8", errors="replace").splitlines(keepends=True)
512 return []
513
514 safe_path = path.replace("\x1b", "?") # sanitize ANSI injection
515 base_lines = _read_lines(base_manifest)
516 ours_lines = _read_lines(ours_manifest, fallback_disk=True)
517 theirs_lines = _read_lines(theirs_manifest)
518
519 # ── ANSI colour helpers ───────────────────────────────────────────────────
520 def _c(code: str, text: str) -> str:
521 return f"\x1b[{code}m{text}\x1b[0m" if use_color else text
522
523 def _bold(t: str) -> str:
524 return _c("1", t)
525
526 def _cyan(t: str) -> str:
527 return _c("36", t)
528
529 def _green(t: str) -> str:
530 return _c("32", t)
531
532 def _red(t: str) -> str:
533 return _c("31", t)
534
535 def _yellow(t: str) -> str:
536 return _c("33", t)
537
538 # ── Header ────────────────────────────────────────────────────────────────
539 output: list[str] = []
540 output.append(_bold(CONFLICT_SEPARATOR))
541 output.append(_bold(f"CONFLICT {safe_path}"))
542 output.append(_bold(CONFLICT_SEPARATOR))
543
544 # ── Ours diff (base → ours) ───────────────────────────────────────────────
545 ours_hunks = list(difflib.unified_diff(
546 base_lines, ours_lines,
547 fromfile=f"base/{safe_path}",
548 tofile=f"{ours_label}/{safe_path}",
549 lineterm="",
550 ))
551 annotated_ours = annotate_hunk_action(ours_hunks, ours_label)
552
553 output.append("")
554 output.append(_yellow(f"[{ours_label}] what {ours_label} changed from base"))
555 if annotated_ours:
556 for line in annotated_ours:
557 if line.startswith("---") or line.startswith("+++"):
558 output.append(_bold(line))
559 elif line.startswith("@@"):
560 output.append(_cyan(line))
561 elif line.startswith("+"):
562 output.append(_green(line))
563 elif line.startswith("-"):
564 output.append(_red(line))
565 else:
566 output.append(line)
567 else:
568 output.append(" (no changes from base on this side)")
569
570 # ── Theirs diff (base → theirs) ───────────────────────────────────────────
571 theirs_hunks = list(difflib.unified_diff(
572 base_lines, theirs_lines,
573 fromfile=f"base/{safe_path}",
574 tofile=f"{theirs_label}/{safe_path}",
575 lineterm="",
576 ))
577 annotated_theirs = annotate_hunk_action(theirs_hunks, theirs_label)
578
579 output.append("")
580 output.append(_yellow(f"[{theirs_label}] what {theirs_label} changed from base"))
581 if annotated_theirs:
582 for line in annotated_theirs:
583 if line.startswith("---") or line.startswith("+++"):
584 output.append(_bold(line))
585 elif line.startswith("@@"):
586 output.append(_cyan(line))
587 elif line.startswith("+"):
588 output.append(_green(line))
589 elif line.startswith("-"):
590 output.append(_red(line))
591 else:
592 output.append(line)
593 else:
594 output.append(" (no changes from base on this side)")
595
596 output.append("")
597 return output
File History 3 commits
sha256:b636f72dcba9e190afb980bece906fa5b717fbde014b76ef023df8cb96e01eb9 docs: expand cache plan with all seven testing tiers and do… Sonnet 4.6 136 days ago
sha256:7f9e2ef5286aedad9c1e6011b4c46ca27f39dbdad6e3409357e36b26e46b3b7c docs: docstring sprint for-each-ref→hotspots — idiomatic ru… Sonnet 4.6 patch 142 days ago
sha256:a09b1b4f6838754495547f200aa0ce88e2f56ffc5b20b900f6f0cff2c3cdede9 fix(cursorignore): remove git-ism (.git/worktrees) Human minor ⚠ 145 days ago