| 1 | """Outcome classification and merge laws. Pure functions; no I/O.
|
| 2 |
|
| 3 | Classes (every case gets exactly one; nothing passes silently):
|
| 4 |
|
| 5 | - equal-to-git: same clean/conflicted status, same conflicted path set, and
|
| 6 | identical content+mode for every non-conflicted path.
|
| 7 | - differs-but-valid: differs from git, but no change from either side is lost
|
| 8 | or fabricated at any non-conflicted path (e.g. Oak conflicts where git's
|
| 9 | rename detection resolved cleanly; git conflicts where Oak's path-level merge
|
| 10 | kept both sides). Reasons say which.
|
| 11 | - oak-wrong: a non-conflicted path loses a side's change, carries content no
|
| 12 | input or valid text merge explains, a scenario's stated expectation (e.g.
|
| 13 | "revert stays reverted") is violated, or Oak errors on a valid input.
|
| 14 | - oak-unsupported: the input cannot be represented through Oak's public
|
| 15 | surface (gitlinks, multiple git merge bases or unrelated histories for the
|
| 16 | fork+squash construction), decided before Oak runs.
|
| 17 | - harness-error: the instrument failed (fixture build, oracle, shim).
|
| 18 | """
|
| 19 | from __future__ import annotations
|
| 20 |
|
| 21 | import difflib
|
| 22 | from typing import Dict, Iterable, List, Optional, Set, Tuple
|
| 23 |
|
| 24 | CLASSES = ("equal-to-git", "differs-but-valid", "oak-wrong", "oak-unsupported", "harness-error")
|
| 25 | MARKERS = (b"<<<<<<< ", b"=======", b">>>>>>> ")
|
| 26 |
|
| 27 | Value = Tuple[str, str]
|
| 28 | Tree = Dict[str, Value]
|
| 29 |
|
| 30 |
|
| 31 | def split_tree(tree: Tree, conflicted: Iterable[str]) -> Tree:
|
| 32 | conflicted = set(conflicted)
|
| 33 | return {p: v for p, v in tree.items() if p not in conflicted}
|
| 34 |
|
| 35 |
|
| 36 | def oak_conflict_type(path: str, base: Tree, ours: Tree, theirs: Tree) -> str:
|
| 37 | """Oak's per-path conflict kind, derived from the three inputs (Oak merges path-by-path)."""
|
| 38 | b, o, t = base.get(path), ours.get(path), theirs.get(path)
|
| 39 | if o is None or t is None:
|
| 40 | return "modify/delete" if b is not None else "file/directory"
|
| 41 | if b is None:
|
| 42 | return "add/add"
|
| 43 | if o[1] == t[1] and o[0] != t[0]:
|
| 44 | return "mode"
|
| 45 | return "content"
|
| 46 |
|
| 47 |
|
| 48 | def text_preserves_sides(base: bytes, ours: bytes, theirs: bytes, merged: bytes) -> bool:
|
| 49 | """Heuristic line-level check: every block a side inserted/replaced appears in the merge,
|
| 50 | and the merge carries no conflict markers. Deletions are not checked (lines repeat)."""
|
| 51 | if any(m in merged for m in MARKERS) and not any(m in x for x in (base, ours, theirs) for m in MARKERS):
|
| 52 | return False
|
| 53 | b, m = base.splitlines(), merged.splitlines()
|
| 54 | for side in (ours.splitlines(), theirs.splitlines()):
|
| 55 | for tag, _i1, _i2, j1, j2 in difflib.SequenceMatcher(None, b, side, autojunk=False).get_opcodes():
|
| 56 | if tag in ("insert", "replace") and not _contains(m, side[j1:j2]):
|
| 57 | return False
|
| 58 | return True
|
| 59 |
|
| 60 |
|
| 61 | def _contains(haystack: List[bytes], needle: List[bytes]) -> bool:
|
| 62 | if not needle:
|
| 63 | return True
|
| 64 | n = len(needle)
|
| 65 | return any(haystack[i:i + n] == needle for i in range(len(haystack) - n + 1))
|
| 66 |
|
| 67 |
|
| 68 | def _three_way_kind(b: Optional[Value], o: Optional[Value], t: Optional[Value]) -> Optional[str]:
|
| 69 | """Expected entry kind (file/exec/symlink) of a both-sides-changed path, or None when
|
| 70 | the two sides changed the kind incompatibly (a mode conflict)."""
|
| 71 | bk, ok, tk = (b and b[0]), (o and o[0]), (t and t[0])
|
| 72 | if ok == tk:
|
| 73 | return ok
|
| 74 | if ok == bk:
|
| 75 | return tk
|
| 76 | if tk == bk:
|
| 77 | return ok
|
| 78 | return None
|
| 79 |
|
| 80 |
|
| 81 | def lacks_final_newline(ev: dict) -> bool:
|
| 82 | """True when a non-empty merge input does not end in a newline (the fb-537 trigger)."""
|
| 83 | return any(x and not x.endswith(b"\n") for x in (ev.get("base"), ev.get("ours"), ev.get("theirs")))
|
| 84 |
|
| 85 |
|
| 86 | def has_new_markers(ev: dict) -> bool:
|
| 87 | inputs = (ev.get("base") or b"", ev.get("ours") or b"", ev.get("theirs") or b"")
|
| 88 | return any(m in ev.get("merged", b"") and not any(m in x for x in inputs) for m in MARKERS)
|
| 89 |
|
| 90 |
|
| 91 | def no_lost_change(base: Tree, ours: Tree, theirs: Tree, result: Tree, conflicted: Set[str],
|
| 92 | texts: Optional[Dict[str, dict]] = None) -> Dict[str, List[str]]:
|
| 93 | """Path-level law. Returns {"lost", "mode_lost", "markers", "markers_no_final_newline",
|
| 94 | "markers_symlink", "fabricated",
|
| 95 | "text_merged"}.
|
| 96 |
|
| 97 | For every non-conflicted path: a change made by exactly one side must be
|
| 98 | present; an identical change on both sides must be present; a divergent
|
| 99 | change on both sides must have been text-merged preserving both sides'
|
| 100 | content AND the 3-way-merged entry kind/mode (checked with
|
| 101 | `texts[path] = {base, ours, theirs, merged}` bytes). Merged bytes carrying
|
| 102 | conflict markers that no input had are reported as `markers`."""
|
| 103 | lost, mode_lost, markers, markers_nofinal, markers_symlink, fabricated, merged_ok = [], [], [], [], [], [], []
|
| 104 | texts = texts or {}
|
| 105 | for path in sorted(set(base) | set(ours) | set(theirs) | set(result)):
|
| 106 | if path in conflicted:
|
| 107 | continue
|
| 108 | b, o, t, r = base.get(path), ours.get(path), theirs.get(path), result.get(path)
|
| 109 | if o == t:
|
| 110 | want = o
|
| 111 | elif o == b:
|
| 112 | want = t
|
| 113 | elif t == b:
|
| 114 | want = o
|
| 115 | else:
|
| 116 | ev = texts.get(path)
|
| 117 | kind = _three_way_kind(b, o, t)
|
| 118 | if r is not None and r in (o, t):
|
| 119 | # One side taken wholesale: the other side's change is dropped. When the dropped
|
| 120 | # side changed only the kind/mode (same content as base), call it a mode loss.
|
| 121 | other = t if r == o else o
|
| 122 | same_content = o is not None and t is not None and o[1] == t[1]
|
| 123 | mode_only = other is not None and (same_content or (
|
| 124 | b is not None and other[1] == b[1] and other[0] != b[0]))
|
| 125 | (mode_lost if mode_only else lost).append(path)
|
| 126 | elif r is None:
|
| 127 | lost.append(path)
|
| 128 | elif o is not None and t is not None and o[1] == t[1] and r[1] == o[1]:
|
| 129 | # Same content both sides, kinds differ: only the mode merge is at stake.
|
| 130 | (merged_ok if kind is not None and r[0] == kind else mode_lost).append(path)
|
| 131 | elif ev is None:
|
| 132 | fabricated.append(path)
|
| 133 | elif has_new_markers(ev):
|
| 134 | symlinky = "symlink" in (o and o[0], t and t[0], r[0])
|
| 135 | if symlinky:
|
| 136 | markers_symlink.append(path)
|
| 137 | else:
|
| 138 | (markers_nofinal if lacks_final_newline(ev) else markers).append(path)
|
| 139 | elif kind is None or r[0] != kind:
|
| 140 | mode_lost.append(path) # content merged, but a side's mode/kind change dropped
|
| 141 | elif text_preserves_sides(ev.get("base") or b"", ev["ours"], ev["theirs"], ev["merged"]):
|
| 142 | merged_ok.append(path)
|
| 143 | else:
|
| 144 | lost.append(path)
|
| 145 | continue
|
| 146 | if r != want:
|
| 147 | # Absent, or another input's value (a side's change was dropped) -> lost;
|
| 148 | # a value no input has -> fabricated.
|
| 149 | (lost if r is None or r in (b, o, t) else fabricated).append(path)
|
| 150 | return {"lost": lost, "mode_lost": mode_lost, "markers": markers, "markers_no_final_newline": markers_nofinal,
|
| 151 | "markers_symlink": markers_symlink,
|
| 152 | "fabricated": fabricated,
|
| 153 | "text_merged": merged_ok}
|
| 154 |
|
| 155 |
|
| 156 | def base_free_checks(ours: Tree, theirs: Tree, result: Tree, conflicted: Set[str],
|
| 157 | texts: Optional[Dict[str, dict]] = None) -> Dict[str, List[str]]:
|
| 158 | """The part of the no-lost-change law that needs no merge base (criss-cross rows).
|
| 159 |
|
| 160 | With several merge bases the path-level law is undefined, but two checks
|
| 161 | still hold for every non-conflicted path: a value both sides agree on must
|
| 162 | be in the result (absent -> lost, a different value -> fabricated), and a
|
| 163 | text-merged file must not carry conflict markers no side had. Same shape
|
| 164 | as no_lost_change (text_merged stays empty: preservation is unjudgeable)."""
|
| 165 | out = {"lost": [], "mode_lost": [], "markers": [], "markers_no_final_newline": [],
|
| 166 | "markers_symlink": [], "fabricated": [], "text_merged": []}
|
| 167 | texts = texts or {}
|
| 168 | for path in sorted(set(ours) | set(theirs) | set(result)):
|
| 169 | if path in conflicted:
|
| 170 | continue
|
| 171 | o, t, r = ours.get(path), theirs.get(path), result.get(path)
|
| 172 | if o == t:
|
| 173 | if r != o:
|
| 174 | if r is not None and o is not None and r[1] == o[1]:
|
| 175 | out["mode_lost"].append(path)
|
| 176 | else:
|
| 177 | out["lost" if r is None else "fabricated"].append(path)
|
| 178 | continue
|
| 179 | ev = texts.get(path)
|
| 180 | if r is not None and r not in (o, t) and ev is not None and has_new_markers(ev):
|
| 181 | if "symlink" in (o and o[0], t and t[0], r[0]):
|
| 182 | out["markers_symlink"].append(path)
|
| 183 | else:
|
| 184 | out["markers_no_final_newline" if lacks_final_newline(ev) else "markers"].append(path)
|
| 185 | return out
|
| 186 |
|
| 187 |
|
| 188 | def law_reasons(law: Dict[str, List[str]]) -> List[str]:
|
| 189 | """oak-wrong reasons for a no-lost-change law result (full or base-free)."""
|
| 190 | reasons = []
|
| 191 | for key, label in (("markers_no_final_newline", "committed_conflict_markers_no_final_newline"),
|
| 192 | ("markers_symlink", "committed_conflict_markers_symlink"),
|
| 193 | ("markers", "committed_conflict_markers"),
|
| 194 | ("lost", "lost_change"), ("mode_lost", "lost_mode_change"),
|
| 195 | ("fabricated", "fabricated_content")):
|
| 196 | if law.get(key):
|
| 197 | reasons.append(f"{label}: " + ",".join(law[key][:10]))
|
| 198 | return reasons
|
| 199 |
|
| 200 |
|
| 201 | def validate_class(value: str) -> str:
|
| 202 | if value not in CLASSES:
|
| 203 | raise ValueError(f"unknown merge-suite class {value!r}; expected one of {CLASSES}")
|
| 204 | return value
|
| 205 |
|
| 206 |
|
| 207 | def _classify(git_result: Optional[dict], oak_result: Optional[dict], base: Optional[Tree], ours: Tree,
|
| 208 | theirs: Tree, *, unsupported: Optional[str] = None, harness_error: Optional[str] = None,
|
| 209 | expect: Optional[dict] = None, texts: Optional[Dict[str, dict]] = None) -> dict:
|
| 210 | """Classify one directional case. git_result: {clean, tree, conflicts{path: [types]}}.
|
| 211 | oak_result: adapter result ({clean, tree, conflicts, error, error_kind})."""
|
| 212 | if harness_error:
|
| 213 | return {"class": "harness-error", "reasons": [harness_error]}
|
| 214 | if unsupported:
|
| 215 | return {"class": "oak-unsupported", "reasons": [unsupported]}
|
| 216 | if oak_result is None or git_result is None:
|
| 217 | return {"class": "harness-error", "reasons": ["missing result"]}
|
| 218 | if oak_result.get("error_kind") == "harness":
|
| 219 | return {"class": "harness-error", "reasons": [oak_result.get("error") or "harness"]}
|
| 220 | if oak_result.get("error_kind") == "oak-setup":
|
| 221 | # A scripted setup step (import, push, staged pull) failed before the measured merge.
|
| 222 | # That is not a merge verdict and must never be absorbed by a known merge bug.
|
| 223 | return {"class": "harness-error", "reasons": ["setup_failed: " + str(oak_result.get("error"))[:300]]}
|
| 224 | if oak_result.get("error_kind") == "oak" or oak_result.get("clean") is None:
|
| 225 | reasons = ["oak_error: " + str(oak_result.get("error"))[:300]]
|
| 226 | pf = oak_result.get("post_failure") or {}
|
| 227 | if pf.get("hazard_head_moved_worktree_stale"):
|
| 228 | reasons.append("failed_pull_moved_head_worktree_stale: head %s -> %s, %d worktree path(s) "
|
| 229 | "differ from HEAD, re-pull says %s" % (
|
| 230 | str(pf.get("head_before"))[:12], str(pf.get("head_after"))[:12],
|
| 231 | pf.get("worktree_changes_vs_head", 0), pf.get("repull_parent_sync")))
|
| 232 | if pf.get("hazard_worktree_dirty_head_unmoved"):
|
| 233 | reasons.append("failed_pull_left_worktree_dirty: HEAD unchanged, %d worktree path(s) differ "
|
| 234 | "from HEAD (e.g. %s)" % (pf.get("worktree_changes_vs_head", 0),
|
| 235 | ",".join((pf.get("worktree_changes_sample") or [])[:3])))
|
| 236 | return {"class": "oak-wrong", "reasons": reasons}
|
| 237 |
|
| 238 | oak_tree: Tree = oak_result["tree"]
|
| 239 | oak_conf: Set[str] = set(oak_result.get("conflicts") or {})
|
| 240 | git_conf: Set[str] = set(git_result.get("conflicts") or {})
|
| 241 | # base None = no unique merge base (criss-cross): the path-level law is undefined
|
| 242 | # there and stays unmeasured (null); expectations and the git oracle still apply.
|
| 243 | law = no_lost_change(base, ours, theirs, oak_tree, oak_conf, texts) if base is not None else None
|
| 244 | evidence = {"law_no_lost_change": law}
|
| 245 | if law is None:
|
| 246 | # No unique base: the full law stays unmeasured (null), but its
|
| 247 | # base-independent checks (agreed values kept, no committed markers) run.
|
| 248 | partial = base_free_checks(ours, theirs, oak_tree, oak_conf, texts)
|
| 249 | evidence["law_base_free"] = partial
|
| 250 | reasons = law_reasons(partial)
|
| 251 | else:
|
| 252 | reasons = law_reasons(law)
|
| 253 | base = base or {}
|
| 254 |
|
| 255 | if expect:
|
| 256 | violations = check_expectations(expect, oak_result, oak_tree, oak_conf)
|
| 257 | if violations:
|
| 258 | # A violated expectation is reported together with every law finding,
|
| 259 | # so a new loss on a row with a known expectation bug stays visible
|
| 260 | # (and keeps that row out of the strict all-reasons known-bug mapping).
|
| 261 | label = f"[{expect['label']}]" if expect.get("label") else ""
|
| 262 | return {"class": "oak-wrong",
|
| 263 | "reasons": [f"expectation_violated{label}: " + "; ".join(violations)] + reasons,
|
| 264 | "evidence": evidence}
|
| 265 | law = law or {"lost": [], "mode_lost": [], "markers": [], "markers_no_final_newline": [],
|
| 266 | "markers_symlink": [], "fabricated": [], "text_merged": []}
|
| 267 | if reasons:
|
| 268 | return {"class": "oak-wrong", "reasons": reasons, "evidence": evidence}
|
| 269 |
|
| 270 | git_clean_part = split_tree(git_result["tree"], git_conf)
|
| 271 | oak_clean_part = split_tree(oak_tree, oak_conf)
|
| 272 | if (bool(oak_result["clean"]) == bool(git_result["clean"]) and oak_conf == git_conf
|
| 273 | and oak_clean_part == git_clean_part):
|
| 274 | type_diff = conflict_type_differences(git_result.get("conflicts") or {}, oak_conf, base, ours, theirs)
|
| 275 | out = {"class": "equal-to-git", "reasons": [], "evidence": evidence}
|
| 276 | if type_diff:
|
| 277 | out["notes"] = ["conflict_type_differs: " + ", ".join(type_diff[:10])]
|
| 278 | return out
|
| 279 |
|
| 280 | false_conf = sorted(oak_conf - git_conf)
|
| 281 | missed = sorted(git_conf - oak_conf)
|
| 282 | if false_conf:
|
| 283 | reasons.append("oak_conflicts_where_git_clean: " + ",".join(false_conf[:10]))
|
| 284 | if missed:
|
| 285 | reasons.append("oak_clean_where_git_conflicts: " + ",".join(missed[:10]))
|
| 286 | shared = set(git_clean_part) & set(oak_clean_part)
|
| 287 | only_git = sorted(p for p in set(git_clean_part) - set(oak_clean_part) if p not in oak_conf)
|
| 288 | only_oak = sorted(p for p in set(oak_clean_part) - set(git_clean_part) if p not in git_conf)
|
| 289 | changed = sorted(p for p in shared if git_clean_part[p] != oak_clean_part[p])
|
| 290 | if only_git or only_oak or changed:
|
| 291 | reasons.append("tree_differs(all side changes preserved): git_only=%s oak_only=%s content=%s"
|
| 292 | % (only_git[:6], only_oak[:6], changed[:6]))
|
| 293 | if law["text_merged"] and changed:
|
| 294 | reasons.append("text_merge_algorithm_differs: " + ",".join(sorted(set(changed) & set(law["text_merged"]))[:6]))
|
| 295 | if not reasons:
|
| 296 | reasons.append("status_differs")
|
| 297 | evidence.update({"false_conflict_paths": false_conf, "missed_conflict_paths": missed})
|
| 298 | return {"class": "differs-but-valid", "reasons": reasons, "evidence": evidence}
|
| 299 |
|
| 300 |
|
| 301 | def conflict_type_differences(git_conflicts: Dict[str, List[str]], oak_conf: Set[str],
|
| 302 | base: Tree, ours: Tree, theirs: Tree) -> List[str]:
|
| 303 | out = []
|
| 304 | for path in sorted(oak_conf & set(git_conflicts)):
|
| 305 | oak_kind = oak_conflict_type(path, base, ours, theirs)
|
| 306 | git_kinds = git_conflicts[path]
|
| 307 | if git_kinds and oak_kind not in git_kinds and not (oak_kind == "content" and "binary" in git_kinds):
|
| 308 | out.append(f"{path}: git={'/'.join(git_kinds)} oak={oak_kind}")
|
| 309 | return out
|
| 310 |
|
| 311 |
|
| 312 | def check_expectations(expect: dict, oak_result: dict, tree: Tree, conflicts: Set[str]) -> List[str]:
|
| 313 | """expect = {"clean": bool?, "paths": {path: sha256 | None (absent)}, "conflicts": [paths]?}."""
|
| 314 | out = []
|
| 315 | if "clean" in expect and bool(oak_result.get("clean")) != expect["clean"]:
|
| 316 | out.append(f"clean={oak_result.get('clean')} expected {expect['clean']}")
|
| 317 | for path, digest in (expect.get("paths") or {}).items():
|
| 318 | got = tree.get(path)
|
| 319 | if digest is None and got is not None and path not in conflicts:
|
| 320 | out.append(f"{path} present, expected absent")
|
| 321 | elif digest is not None and (got is None or got[1] != digest):
|
| 322 | out.append(f"{path} content {'absent' if got is None else got[1][:12]} expected {digest[:12]}")
|
| 323 | if "conflicts" in expect and sorted(conflicts) != sorted(expect["conflicts"]):
|
| 324 | out.append(f"conflicts={sorted(conflicts)} expected {sorted(expect['conflicts'])}")
|
| 325 | return out
|
| 326 |
|
| 327 |
|
| 328 | def symmetry(forward: dict, reverse: dict) -> Optional[dict]:
|
| 329 | """Merge-symmetry law over two directional Oak results (None if either is unusable).
|
| 330 |
|
| 331 | merge(A,B) ≅ merge(B,A): same clean flag, same conflicted path set and the
|
| 332 | same non-conflicted content. Conflicted files are excluded (side labels and
|
| 333 | marker order legitimately differ)."""
|
| 334 | if not forward or not reverse or forward.get("clean") is None or reverse.get("clean") is None:
|
| 335 | return None
|
| 336 | fc, rc = set(forward.get("conflicts") or {}), set(reverse.get("conflicts") or {})
|
| 337 | ft, rt = split_tree(forward["tree"], fc), split_tree(reverse["tree"], rc)
|
| 338 | diffs = sorted(p for p in set(ft) | set(rt) if ft.get(p) != rt.get(p) and p not in fc | rc)
|
| 339 | ok = forward["clean"] == reverse["clean"] and fc == rc and not diffs
|
| 340 | return {"holds": ok, "conflict_sets_equal": fc == rc, "clean_equal": forward["clean"] == reverse["clean"],
|
| 341 | "content_diff_paths": diffs[:20]}
|
| 342 |
|
| 343 |
|
| 344 | def idempotence_holds(oak_result: dict) -> Optional[bool]:
|
| 345 | idem = oak_result.get("idempotence") if oak_result else None
|
| 346 | if not idem:
|
| 347 | return None
|
| 348 | return (idem.get("returncode") == 0 and idem.get("head_unchanged") is True
|
| 349 | and idem.get("tree_unchanged") is True)
|
| 350 |
|
| 351 |
|
| 352 | def classify(*args, **kwargs) -> dict:
|
| 353 | """Classify one directional case (see _classify); the class is always validated."""
|
| 354 | verdict = _classify(*args, **kwargs)
|
| 355 | validate_class(verdict["class"])
|
| 356 | return verdict
|