op_merge.py
python
sha256:39065bc65b1a541916c4ea32ccd53eac38bb93015db2be2e342326064e86c44f
fix: convergent-edit phantom conflicts in ops_commute + mer…
Sonnet 4.6
minor
⚠ breaking
36 days ago
| 1 | """Commutativity engine for Muse domain operations. |
| 2 | |
| 3 | This module implements the commutativity rules and position-adjustment |
| 4 | transforms that allow the merge engine to reason over ``DomainOp`` trees |
| 5 | rather than file-path sets. The result is sub-file auto-merge: two agents |
| 6 | editing non-overlapping addresses never produce a conflict. |
| 7 | |
| 8 | Theory |
| 9 | ------ |
| 10 | Muse uses **address-keyed Map merge** for the code and identity domains: each |
| 11 | operation names the symbol or entity it touches via ``address``. Two |
| 12 | operations on *different* addresses commute automatically — no transform |
| 13 | function is needed. Two operations on the *same* address surface as a |
| 14 | conflict and are routed to Harmony for resolution. |
| 15 | |
| 16 | For ordered-sequence domains (MIDI), ``InsertOp`` and ``DeleteOp`` carry a |
| 17 | ``position`` index. Concurrent insertions at *different* positions also |
| 18 | commute, but the later-applied one requires a position adjustment so the |
| 19 | final state is identical regardless of application order. This position |
| 20 | adjustment applies only to ordered-sequence ops, never to |
| 21 | :class:`~muse.domain.AddressedInsertOp` / :class:`~muse.domain.AddressedDeleteOp`. |
| 22 | |
| 23 | Public API |
| 24 | ---------- |
| 25 | - :class:`MergeOpsResult` — structured result of merging two op lists. |
| 26 | - :func:`ops_commute` — commutativity oracle for any two ``DomainOp``\\s. |
| 27 | - :func:`adjust_sequence_positions` — position-adjusted ``(a', b')`` for commuting sequence ops. |
| 28 | - :func:`merge_op_lists` — three-way merge at operation granularity. |
| 29 | |
| 30 | Commutativity rules (summary) |
| 31 | ------------------------------ |
| 32 | |
| 33 | ============================================= ===================================== |
| 34 | Op A Op B Commute? |
| 35 | ============================================= ===================================== |
| 36 | InsertOp(pos=i) InsertOp(pos=j) Yes — if i ≠ j or both None (unordered) |
| 37 | InsertOp(pos=i) InsertOp(pos=i) **No** — positional conflict |
| 38 | InsertOp(addr=A) DeleteOp(addr=B) Yes — if A ≠ B (different containers) |
| 39 | InsertOp(addr=A) DeleteOp(addr=A) **No** — same container |
| 40 | DeleteOp(addr=A) DeleteOp(addr=B) Yes — always (consensus delete is fine) |
| 41 | ReplaceOp(addr=A) ReplaceOp(addr=B) Yes — if A ≠ B |
| 42 | ReplaceOp(addr=A) ReplaceOp(addr=A) **No** — concurrent value conflict |
| 43 | MoveOp(from=i) MoveOp(from=j) Yes — if i ≠ j |
| 44 | MoveOp(from=i) DeleteOp(pos=i) **No** — move-delete conflict |
| 45 | PatchOp(addr=A) PatchOp(addr=B) Yes — if A ≠ B; recurse if A == B |
| 46 | ============================================= ===================================== |
| 47 | |
| 48 | Position adjustment |
| 49 | ------------------- |
| 50 | When two ``InsertOp``\\s at different positions commute, the later-applied one |
| 51 | must have its position adjusted. Concretely, if *a* inserts at position *i* |
| 52 | and *b* inserts at position *j* with *i < j*: |
| 53 | |
| 54 | - Applying *a* first shifts every element at position ≥ i by one; so *b* |
| 55 | must be adjusted to *j + 1*. |
| 56 | - Applying *b* first does not affect positions < j; so *a* stays at *i*. |
| 57 | |
| 58 | For *merge_op_lists*, positions are adjusted via the **counting formula**: for |
| 59 | each InsertOp in one side's exclusive additions, add the count of the other |
| 60 | side's InsertOps that have position ≤ this op's position (on the same |
| 61 | address). This is correct for any number of concurrent insertions and avoids |
| 62 | cascading adjustment errors. |
| 63 | |
| 64 | Synchronous guarantee |
| 65 | --------------------- |
| 66 | All functions are synchronous, pure, and allocation-bounded — no I/O, no |
| 67 | async, no external state. |
| 68 | """ |
| 69 | |
| 70 | import logging |
| 71 | from dataclasses import dataclass, field |
| 72 | |
| 73 | from muse.domain import ( |
| 74 | |
| 75 | DeleteOp, |
| 76 | DomainOp, |
| 77 | InsertOp, |
| 78 | MoveOp, |
| 79 | PatchOp, |
| 80 | ReplaceOp, |
| 81 | StructuredDelta, |
| 82 | ) |
| 83 | |
| 84 | type _AddrMap = dict[str, list[int]] |
| 85 | |
| 86 | logger = logging.getLogger(__name__) |
| 87 | |
| 88 | # --------------------------------------------------------------------------- |
| 89 | # Result type |
| 90 | # --------------------------------------------------------------------------- |
| 91 | |
| 92 | @dataclass |
| 93 | class MergeOpsResult: |
| 94 | """Result of a three-way operation-level merge. |
| 95 | |
| 96 | ``merged_ops`` contains the operations from both sides that can be applied |
| 97 | to the common ancestor to produce the merged state. Positions in any |
| 98 | ``InsertOp`` entries have been adjusted so that the ops can be applied in |
| 99 | ascending position order to produce a deterministic result. |
| 100 | |
| 101 | ``conflict_ops`` contains pairs ``(our_op, their_op)`` where the two |
| 102 | operations cannot be auto-merged. Each pair must be resolved manually |
| 103 | (or via ``.museattributes`` strategy) before the merge can complete. |
| 104 | |
| 105 | ``is_clean`` is ``True`` when ``conflict_ops`` is empty. |
| 106 | """ |
| 107 | |
| 108 | merged_ops: list[DomainOp] = field(default_factory=list) |
| 109 | conflict_ops: list[tuple[DomainOp, DomainOp]] = field(default_factory=list) |
| 110 | |
| 111 | @property |
| 112 | def is_clean(self) -> bool: |
| 113 | """``True`` when no conflicting operation pairs were found.""" |
| 114 | return len(self.conflict_ops) == 0 |
| 115 | |
| 116 | # --------------------------------------------------------------------------- |
| 117 | # Internal helpers |
| 118 | # --------------------------------------------------------------------------- |
| 119 | |
| 120 | def _op_key(op: DomainOp) -> tuple[str, ...]: |
| 121 | """Return a hashable key uniquely identifying *op* for set membership tests. |
| 122 | |
| 123 | The key captures all semantically significant fields so that two ops with |
| 124 | identical effect produce the same key. This is used to detect consensus |
| 125 | operations (both sides added the same op independently). |
| 126 | """ |
| 127 | if op["op"] == "insert": |
| 128 | pos = op.get("position") # type: ignore[union-attr] |
| 129 | return ("insert", op["address"], str(pos), op["content_id"]) # type: ignore[union-attr] |
| 130 | if op["op"] == "delete": |
| 131 | pos = op.get("position") # type: ignore[union-attr] |
| 132 | return ("delete", op["address"], str(pos), op["content_id"]) # type: ignore[union-attr] |
| 133 | if op["op"] == "move": |
| 134 | return ( |
| 135 | "move", |
| 136 | op["address"], |
| 137 | str(op["from_position"]), |
| 138 | str(op["to_position"]), |
| 139 | op["content_id"], |
| 140 | ) |
| 141 | if op["op"] == "replace": |
| 142 | return ( |
| 143 | "replace", |
| 144 | op["address"], |
| 145 | str(op["position"]), |
| 146 | op["old_content_id"], |
| 147 | op["new_content_id"], |
| 148 | ) |
| 149 | if op["op"] == "mutate": |
| 150 | return ("mutate", op["address"], op["entity_id"], op["old_content_id"], op["new_content_id"]) |
| 151 | if op["op"] == "rename": |
| 152 | return ("rename", op["address"], op["from_address"]) # type: ignore[union-attr] |
| 153 | # PatchOp — key on address and child_domain; child_ops are not hashed for |
| 154 | # performance reasons. Two patch ops on the same container are treated as |
| 155 | # the same "slot" for conflict detection purposes. |
| 156 | return ("patch", op["address"], op["child_domain"]) # type: ignore[index] |
| 157 | |
| 158 | # --------------------------------------------------------------------------- |
| 159 | # Commutativity oracle |
| 160 | # --------------------------------------------------------------------------- |
| 161 | |
| 162 | def ops_commute(a: DomainOp, b: DomainOp) -> bool: |
| 163 | """Return ``True`` if operations *a* and *b* commute (are auto-mergeable). |
| 164 | |
| 165 | Two operations commute when applying them in either order produces the |
| 166 | same final state. This function implements the commutativity rules table |
| 167 | for all 25 op-kind pairs. |
| 168 | |
| 169 | For ``PatchOp`` at the same address, commmutativity is determined |
| 170 | recursively by checking all child-op pairs. |
| 171 | |
| 172 | Args: |
| 173 | a: First domain operation. |
| 174 | b: Second domain operation. |
| 175 | |
| 176 | Returns: |
| 177 | ``True`` if the two operations can be safely auto-merged. |
| 178 | """ |
| 179 | # ------------------------------------------------------------------ |
| 180 | # InsertOp + * |
| 181 | # ------------------------------------------------------------------ |
| 182 | if a["op"] == "insert": |
| 183 | if b["op"] == "insert": |
| 184 | # Different containers always commute — they are completely independent. |
| 185 | if a["address"] != b["address"]: |
| 186 | return True |
| 187 | # AddressedInsertOp has no "position" key. |
| 188 | # Convergent insert: both branches inserted the same content at the |
| 189 | # same address — the result is identical regardless of order. |
| 190 | if "position" not in a or "position" not in b: |
| 191 | return a.get("content_id") == b.get("content_id") |
| 192 | a_pos, b_pos = a["position"], b["position"] |
| 193 | # InsertOp with position=None (unordered set) always commutes. |
| 194 | if a_pos is None or b_pos is None: |
| 195 | return True |
| 196 | # InsertOp with integer positions: conflict only at equal positions. |
| 197 | return a_pos != b_pos |
| 198 | if b["op"] == "delete": |
| 199 | # Conservative: inserts and deletes at the same container conflict. |
| 200 | return a["address"] != b["address"] |
| 201 | if b["op"] == "move": |
| 202 | return a["address"] != b["address"] |
| 203 | if b["op"] == "replace": |
| 204 | return a["address"] != b["address"] |
| 205 | # b is PatchOp (exhaustion of DeleteOp | MoveOp | ReplaceOp | PatchOp) |
| 206 | return a["address"] != b["address"] |
| 207 | |
| 208 | # ------------------------------------------------------------------ |
| 209 | # DeleteOp + * |
| 210 | # ------------------------------------------------------------------ |
| 211 | if a["op"] == "delete": |
| 212 | if b["op"] == "insert": |
| 213 | return a["address"] != b["address"] |
| 214 | if b["op"] == "delete": |
| 215 | # Consensus delete (same or different address) always commutes. |
| 216 | # Two branches that both removed the same element produce the same |
| 217 | # result: the element is absent. |
| 218 | return True |
| 219 | if b["op"] == "move": |
| 220 | # AddressedDeleteOp has no position key — unordered, always commutes with move. |
| 221 | if "position" not in a: |
| 222 | return True |
| 223 | a_pos = a["position"] |
| 224 | if a_pos is None: |
| 225 | return True # unordered collection: no positional conflict |
| 226 | return a_pos != b["from_position"] |
| 227 | if b["op"] == "replace": |
| 228 | return a["address"] != b["address"] |
| 229 | # b is PatchOp |
| 230 | return a["address"] != b["address"] |
| 231 | |
| 232 | # ------------------------------------------------------------------ |
| 233 | # MoveOp + * |
| 234 | # ------------------------------------------------------------------ |
| 235 | if a["op"] == "move": |
| 236 | if b["op"] == "insert": |
| 237 | return a["address"] != b["address"] |
| 238 | if b["op"] == "delete": |
| 239 | # AddressedDeleteOp has no position key — unordered, always commutes with move. |
| 240 | if "position" not in b: |
| 241 | return True |
| 242 | b_pos = b["position"] |
| 243 | if b_pos is None: |
| 244 | return True |
| 245 | return a["from_position"] != b_pos |
| 246 | if b["op"] == "move": |
| 247 | # Two moves from different source positions commute. |
| 248 | return a["from_position"] != b["from_position"] |
| 249 | if b["op"] == "replace": |
| 250 | return a["address"] != b["address"] |
| 251 | # b is PatchOp |
| 252 | return a["address"] != b["address"] |
| 253 | |
| 254 | # ------------------------------------------------------------------ |
| 255 | # ReplaceOp + * |
| 256 | # ------------------------------------------------------------------ |
| 257 | if a["op"] == "replace": |
| 258 | if b["op"] == "insert": |
| 259 | return a["address"] != b["address"] |
| 260 | if b["op"] == "delete": |
| 261 | return a["address"] != b["address"] |
| 262 | if b["op"] == "move": |
| 263 | return a["address"] != b["address"] |
| 264 | if b["op"] == "replace": |
| 265 | # Two replaces at the same address conflict unless they converge on |
| 266 | # the same new content — a convergent edit commutes regardless of |
| 267 | # which branch made it first. |
| 268 | if a["address"] != b["address"]: |
| 269 | return True |
| 270 | return a["new_content_id"] == b["new_content_id"] |
| 271 | # b is PatchOp |
| 272 | return a["address"] != b["address"] |
| 273 | |
| 274 | # ------------------------------------------------------------------ |
| 275 | # MutateOp + * (a["op"] == "mutate" commutes with everything at a |
| 276 | # different address; same-entity concurrent mutations conflict) |
| 277 | # ------------------------------------------------------------------ |
| 278 | if a["op"] == "mutate": |
| 279 | if b["op"] == "mutate": |
| 280 | return a["entity_id"] != b["entity_id"] |
| 281 | return a["address"] != b["address"] |
| 282 | |
| 283 | # ------------------------------------------------------------------ |
| 284 | # PatchOp + * (a["op"] == "patch" after all checks above) |
| 285 | # ------------------------------------------------------------------ |
| 286 | if b["op"] == "insert": |
| 287 | return a["address"] != b["address"] |
| 288 | if b["op"] == "delete": |
| 289 | return a["address"] != b["address"] |
| 290 | if b["op"] == "move": |
| 291 | return a["address"] != b["address"] |
| 292 | if b["op"] == "replace": |
| 293 | return a["address"] != b["address"] |
| 294 | if b["op"] == "mutate": |
| 295 | return a["address"] != b["address"] |
| 296 | # b is PatchOp |
| 297 | if a["address"] != b["address"]: |
| 298 | return True |
| 299 | # Same address: recurse into child ops — all child pairs must commute. |
| 300 | for child_a in a["child_ops"]: |
| 301 | for child_b in b["child_ops"]: |
| 302 | if not ops_commute(child_a, child_b): |
| 303 | return False |
| 304 | return True |
| 305 | |
| 306 | # --------------------------------------------------------------------------- |
| 307 | # Sequence position adjustment |
| 308 | # --------------------------------------------------------------------------- |
| 309 | |
| 310 | def adjust_sequence_positions(a: DomainOp, b: DomainOp) -> tuple[DomainOp, DomainOp]: |
| 311 | """Return ``(a', b')`` such that ``apply(apply(base, a), b') == apply(apply(base, b), a')``. |
| 312 | |
| 313 | Should only be called when :func:`ops_commute` has confirmed that *a* and |
| 314 | *b* commute. For all commuting pairs except ordered InsertOp+InsertOp, the |
| 315 | identity pair ``(a, b)`` is returned — the operations do not interfere with |
| 316 | each other's positions. |
| 317 | |
| 318 | For the InsertOp+InsertOp case with integer positions (the most common |
| 319 | case in practice), positions are adjusted so the diamond property holds: |
| 320 | the same final sequence is produced regardless of application order. |
| 321 | |
| 322 | Args: |
| 323 | a: First domain operation. |
| 324 | b: Second domain operation (must commute with *a*). |
| 325 | |
| 326 | Returns: |
| 327 | A tuple ``(a', b')`` where: |
| 328 | |
| 329 | - *a'* is the version of *a* to apply when *b* has already been applied. |
| 330 | - *b'* is the version of *b* to apply when *a* has already been applied. |
| 331 | """ |
| 332 | if a["op"] == "insert" and b["op"] == "insert": |
| 333 | a_pos, b_pos = a["position"], b["position"] |
| 334 | if a_pos is not None and b_pos is not None and a_pos != b_pos: |
| 335 | if a_pos < b_pos: |
| 336 | # a inserts before b's original position → b shifts up by 1. |
| 337 | b_prime = InsertOp( |
| 338 | op="insert", |
| 339 | address=b["address"], |
| 340 | position=b_pos + 1, |
| 341 | content_id=b["content_id"], |
| 342 | content_summary=b["content_summary"], |
| 343 | ) |
| 344 | return a, b_prime |
| 345 | else: |
| 346 | # b inserts before a's original position → a shifts up by 1. |
| 347 | a_prime = InsertOp( |
| 348 | op="insert", |
| 349 | address=a["address"], |
| 350 | position=a_pos + 1, |
| 351 | content_id=a["content_id"], |
| 352 | content_summary=a["content_summary"], |
| 353 | ) |
| 354 | return a_prime, b |
| 355 | |
| 356 | # All other commuting pairs: identity transform. |
| 357 | return a, b |
| 358 | |
| 359 | # --------------------------------------------------------------------------- |
| 360 | # Three-way merge at operation granularity |
| 361 | # --------------------------------------------------------------------------- |
| 362 | |
| 363 | def _adjust_insert_positions( |
| 364 | ops: list[DomainOp], |
| 365 | other_ops: list[DomainOp], |
| 366 | ) -> list[DomainOp]: |
| 367 | """Adjust ``InsertOp`` positions in *ops* to account for *other_ops*. |
| 368 | |
| 369 | For each ``InsertOp`` with a non-``None`` position in *ops*, the adjusted |
| 370 | position is ``original_position + count`` where ``count`` is the number of |
| 371 | ``InsertOp``\\s in *other_ops* that share the same ``address`` and have |
| 372 | ``position ≤ original_position``. |
| 373 | |
| 374 | This implements the *counting formula* for multi-op position adjustment. |
| 375 | It is correct for any number of concurrent insertions on each side, |
| 376 | producing the same final sequence regardless of application order. |
| 377 | |
| 378 | Non-``InsertOp`` entries and unordered inserts (``position=None``) pass |
| 379 | through unchanged. |
| 380 | |
| 381 | Args: |
| 382 | ops: The list of ops whose positions need adjustment. |
| 383 | other_ops: The concurrent operations from the other branch. |
| 384 | |
| 385 | Returns: |
| 386 | A new list with adjusted ``InsertOp``\\s; all other entries are copied |
| 387 | unchanged. |
| 388 | """ |
| 389 | # Collect other-side InsertOp positions, grouped by address. |
| 390 | other_by_addr: _AddrMap = {} |
| 391 | for op in other_ops: |
| 392 | if op["op"] == "insert" and op.get("position") is not None: # type: ignore[union-attr] |
| 393 | addr = op["address"] |
| 394 | if addr not in other_by_addr: |
| 395 | other_by_addr[addr] = [] |
| 396 | other_by_addr[addr].append(op["position"]) # type: ignore[union-attr] |
| 397 | |
| 398 | result: list[DomainOp] = [] |
| 399 | for op in ops: |
| 400 | if op["op"] == "insert" and op.get("position") is not None: # type: ignore[union-attr] |
| 401 | addr = op["address"] |
| 402 | pos = op["position"] |
| 403 | others = other_by_addr.get(addr, []) |
| 404 | shift = sum(1 for p in others if p <= pos) |
| 405 | if shift: |
| 406 | result.append( |
| 407 | InsertOp( |
| 408 | op="insert", |
| 409 | address=addr, |
| 410 | position=pos + shift, |
| 411 | content_id=op["content_id"], |
| 412 | content_summary=op["content_summary"], |
| 413 | ) |
| 414 | ) |
| 415 | else: |
| 416 | result.append(op) |
| 417 | else: |
| 418 | result.append(op) |
| 419 | |
| 420 | return result |
| 421 | |
| 422 | def merge_op_lists( |
| 423 | base_ops: list[DomainOp], |
| 424 | ours_ops: list[DomainOp], |
| 425 | theirs_ops: list[DomainOp], |
| 426 | ) -> MergeOpsResult: |
| 427 | """Three-way merge at operation granularity. |
| 428 | |
| 429 | Implements the standard three-way merge algorithm applied to typed domain |
| 430 | operations rather than file-path sets. The inputs represent: |
| 431 | |
| 432 | - *base_ops*: operations present in the common ancestor. |
| 433 | - *ours_ops*: operations present on our branch (superset of base for |
| 434 | kept ops, plus our new additions). |
| 435 | - *theirs_ops*: operations present on their branch (same structure). |
| 436 | |
| 437 | Algorithm |
| 438 | --------- |
| 439 | 1. **Kept from base** — ops in base that both sides retained are included |
| 440 | unchanged. |
| 441 | 2. **Consensus additions** — ops added independently by both sides (same |
| 442 | key) are included exactly once (idempotent). |
| 443 | 3. **Exclusive additions** — ops added by only one side enter the |
| 444 | commmutativity check: |
| 445 | |
| 446 | - Any pair (ours_exclusive, theirs_exclusive) where |
| 447 | :func:`ops_commute` returns ``False`` is recorded as a conflict. |
| 448 | - Exclusive additions not involved in any conflict are included in |
| 449 | ``merged_ops``, with ``InsertOp`` positions adjusted via |
| 450 | :func:`_adjust_insert_positions`. |
| 451 | |
| 452 | Position adjustment note |
| 453 | ------------------------ |
| 454 | The adjusted ``InsertOp`` positions in ``merged_ops`` are *absolute |
| 455 | positions in the final merged sequence* — meaning they already account for |
| 456 | all insertions from both sides. Callers applying the merged ops to the |
| 457 | base state should apply ``InsertOp``\\s in ascending position order to |
| 458 | obtain the correct final sequence. |
| 459 | |
| 460 | Args: |
| 461 | base_ops: Operations in the common ancestor delta. |
| 462 | ours_ops: Operations on our branch. |
| 463 | theirs_ops: Operations on their branch. |
| 464 | |
| 465 | Returns: |
| 466 | A :class:`MergeOpsResult` with merged and conflicting op lists. |
| 467 | """ |
| 468 | base_key_set = {_op_key(op) for op in base_ops} |
| 469 | ours_key_set = {_op_key(op) for op in ours_ops} |
| 470 | theirs_key_set = {_op_key(op) for op in theirs_ops} |
| 471 | |
| 472 | # 1. Ops both sides kept from the base. |
| 473 | kept: list[DomainOp] = [ |
| 474 | op |
| 475 | for op in base_ops |
| 476 | if _op_key(op) in ours_key_set and _op_key(op) in theirs_key_set |
| 477 | ] |
| 478 | |
| 479 | # 2. New ops — not present in base. |
| 480 | ours_new = [op for op in ours_ops if _op_key(op) not in base_key_set] |
| 481 | theirs_new = [op for op in theirs_ops if _op_key(op) not in base_key_set] |
| 482 | |
| 483 | ours_new_keys = {_op_key(op) for op in ours_new} |
| 484 | theirs_new_keys = {_op_key(op) for op in theirs_new} |
| 485 | consensus_keys = ours_new_keys & theirs_new_keys |
| 486 | |
| 487 | # Consensus additions: both sides added the same op → include once. |
| 488 | consensus: list[DomainOp] = [ |
| 489 | op for op in ours_new if _op_key(op) in consensus_keys |
| 490 | ] |
| 491 | |
| 492 | # 3. Each side's exclusive new additions. |
| 493 | ours_exclusive = [op for op in ours_new if _op_key(op) not in consensus_keys] |
| 494 | theirs_exclusive = [op for op in theirs_new if _op_key(op) not in consensus_keys] |
| 495 | |
| 496 | # Conflict detection: any pair from both sides that does not commute. |
| 497 | conflict_ops: list[tuple[DomainOp, DomainOp]] = [] |
| 498 | conflicting_ours_keys: set[tuple[str, ...]] = set() |
| 499 | conflicting_theirs_keys: set[tuple[str, ...]] = set() |
| 500 | |
| 501 | for our_op in ours_exclusive: |
| 502 | for their_op in theirs_exclusive: |
| 503 | if not ops_commute(our_op, their_op): |
| 504 | conflict_ops.append((our_op, their_op)) |
| 505 | conflicting_ours_keys.add(_op_key(our_op)) |
| 506 | conflicting_theirs_keys.add(_op_key(their_op)) |
| 507 | |
| 508 | # 4. Clean ops: not involved in any conflict. |
| 509 | clean_ours = [ |
| 510 | op for op in ours_exclusive if _op_key(op) not in conflicting_ours_keys |
| 511 | ] |
| 512 | clean_theirs = [ |
| 513 | op for op in theirs_exclusive if _op_key(op) not in conflicting_theirs_keys |
| 514 | ] |
| 515 | |
| 516 | # 5. Position adjustment using the counting formula. |
| 517 | clean_ours_adjusted = _adjust_insert_positions(clean_ours, clean_theirs) |
| 518 | clean_theirs_adjusted = _adjust_insert_positions(clean_theirs, clean_ours) |
| 519 | |
| 520 | merged_ops: list[DomainOp] = ( |
| 521 | list(kept) + list(consensus) + clean_ours_adjusted + clean_theirs_adjusted |
| 522 | ) |
| 523 | |
| 524 | logger.debug( |
| 525 | "merge_op_lists: kept=%d consensus=%d ours=%d theirs=%d conflicts=%d", |
| 526 | len(kept), |
| 527 | len(consensus), |
| 528 | len(clean_ours_adjusted), |
| 529 | len(clean_theirs_adjusted), |
| 530 | len(conflict_ops), |
| 531 | ) |
| 532 | |
| 533 | return MergeOpsResult(merged_ops=merged_ops, conflict_ops=conflict_ops) |
| 534 | |
| 535 | def merge_structured( |
| 536 | base_delta: StructuredDelta, |
| 537 | ours_delta: StructuredDelta, |
| 538 | theirs_delta: StructuredDelta, |
| 539 | ) -> MergeOpsResult: |
| 540 | """Merge two structured deltas against a common base delta. |
| 541 | |
| 542 | A convenience wrapper over :func:`merge_op_lists` that accepts |
| 543 | :class:`~muse.domain.StructuredDelta` objects directly. |
| 544 | |
| 545 | Args: |
| 546 | base_delta: Delta representing the common ancestor's operations. |
| 547 | ours_delta: Delta produced by our branch. |
| 548 | theirs_delta: Delta produced by their branch. |
| 549 | |
| 550 | Returns: |
| 551 | A :class:`MergeOpsResult` describing the merged and conflicting ops. |
| 552 | """ |
| 553 | return merge_op_lists( |
| 554 | base_delta["ops"], |
| 555 | ours_delta["ops"], |
| 556 | theirs_delta["ops"], |
| 557 | ) |
File History
2 commits
sha256:39065bc65b1a541916c4ea32ccd53eac38bb93015db2be2e342326064e86c44f
fix: convergent-edit phantom conflicts in ops_commute + mer…
Sonnet 4.6
minor
⚠
36 days ago
sha256:26e130b630b6a51f141dc4cc495ddfd11a1186ef4407b9530ed1c8ae528cd3ce
fix: ops_commute handles AddressedInsertOp/AddressedDeleteO…
Sonnet 4.6
patch
43 days ago