FA-75631 / Text diff and three-way merge / Open access

Merge base selection: only one of several merge bases is returned · case 01

Criss-cross merges pick an arbitrary base and can report spurious conflicts or silently revert changes.

Verified by executionVariant 1 · 10 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The result is truncated to the first merge base.

VERIFIED REPAIR

Return every best common ancestor.

Unsuccessful approach: Choosing the base with the longest history still discards the other equally good base.

Case contract

Given a commit graph (commit -> parent list) and two commits, ancestors include the commit itself and all commits reachable through any parent. The merge bases are the common ancestors that are not ancestors of another common ancestor. Return them sorted.

Why this case matters

A three-way merge is only as good as its base; criss-cross histories legitimately have several best common ancestors.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(parents, x, y):
    def anc(c):
        seen = set()
        stack = [c]
        while stack:
            k = stack.pop()
            if k in seen:
                continue
            seen.add(k)
            stack.extend(parents.get(k, []))
        return seen
    common = anc(x) & anc(y)
    best = [c for c in common if not any(c != d and c in anc(d) for d in common)]
    return sorted(best)[:1]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c3', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c1', 'c2'], ['c1'])],
    2: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c4', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c1', 'c3'], ['c1'])],
    3: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c5', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c1', 'c4'], ['c1'])],
    4: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c6', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c1', 'c5'], ['c1'])],
    5: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c7', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c1', 'c6'], ['c1'])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
simple fork	`['B']`	`['B']`	Passed
merge commit sees both parents	`['D']`	`['D']`	Passed
fast-forward: one side is an ancestor	`['B']`	`['B']`	Passed
same commit	`['D']`	`['D']`	Passed
criss-cross has two merge bases	`['X1']`	`['X1', 'Y1']`	Failed
long chain against a side branch	`['c1']`	`['c1']`	Passed
second parent carries the only common ancestor	`['a']`	`['a']`	Passed
unrelated histories	`[]`	`[]`	Passed
second parent deeper in history	`['a']`	`['a']`	Passed
first commit is the ancestor	`['c1']`	`['c1']`	Passed

SHA-256 / 7872cfb83f63e68943201fcee76b3ae9cc311a4a20571535d7eec9a4cd2564b8

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(parents, x, y):
    def anc(c):
        seen = set()
        stack = [c]
        while stack:
            k = stack.pop()
            if k in seen:
                continue
            seen.add(k)
            stack.extend(parents.get(k, []))
        return seen
    common = anc(x) & anc(y)
    best = [c for c in common if not any(c != d and c in anc(d) for d in common)]
    return [max(best, key=lambda c: (len(anc(c)), c))] if best else []
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c3', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c1', 'c2'], ['c1'])],
    2: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c4', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c1', 'c3'], ['c1'])],
    3: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c5', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c1', 'c4'], ['c1'])],
    4: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c6', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c1', 'c5'], ['c1'])],
    5: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c7', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c1', 'c6'], ['c1'])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
simple fork	`['B']`	`['B']`	Passed
merge commit sees both parents	`['D']`	`['D']`	Passed
fast-forward: one side is an ancestor	`['B']`	`['B']`	Passed
same commit	`['D']`	`['D']`	Passed
criss-cross has two merge bases	`['Y1']`	`['X1', 'Y1']`	Failed
long chain against a side branch	`['c1']`	`['c1']`	Passed
second parent carries the only common ancestor	`['a']`	`['a']`	Passed
unrelated histories	`[]`	`[]`	Passed
second parent deeper in history	`['a']`	`['a']`	Passed
first commit is the ancestor	`['c1']`	`['c1']`	Passed

SHA-256 / 31527d5f8c0bafab5d065b41f5eda16e5063b8579bd6fbddd1e30bf2d74b3d49

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(parents, x, y):
    def anc(c):
        seen = set()
        stack = [c]
        while stack:
            k = stack.pop()
            if k in seen:
                continue
            seen.add(k)
            stack.extend(parents.get(k, []))
        return seen
    common = anc(x) & anc(y)
    best = [c for c in common if not any(c != d and c in anc(d) for d in common)]
    return sorted(best)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c3', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'side': ['c1']}, 'c1', 'c2'], ['c1'])],
    2: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c4', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'side': ['c1']}, 'c1', 'c3'], ['c1'])],
    3: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c5', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'side': ['c1']}, 'c1', 'c4'], ['c1'])],
    4: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c6', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'side': ['c1']}, 'c1', 'c5'], ['c1'])],
    5: [('simple fork', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'C', 'F'], ['B']), ('merge commit sees both parents', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'E', 'F'], ['D']), ('fast-forward: one side is an ancestor', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'B', 'E'], ['B']), ('same commit', [{'A': [], 'B': ['A'], 'C': ['B'], 'D': ['B'], 'E': ['C', 'D'], 'F': ['D']}, 'D', 'D'], ['D']), ('criss-cross has two merge bases', [{'R': [], 'X1': ['R'], 'Y1': ['R'], 'X2': ['X1', 'Y1'], 'Y2': ['Y1', 'X1']}, 'X2', 'Y2'], ['X1', 'Y1']), ('long chain against a side branch', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c7', 'side'], ['c1']), ('second parent carries the only common ancestor', [{'r': [], 'a': ['r'], 'm': ['z', 'a'], 'z': [], 'b': ['a']}, 'm', 'b'], ['a']), ('unrelated histories', [{'p': [], 'q': []}, 'p', 'q'], []), ('second parent deeper in history', [{'r': [], 'a': ['r'], 'z': [], 'm': ['z', 'a'], 'top': ['m'], 'b': ['a']}, 'top', 'b'], ['a']), ('first commit is the ancestor', [{'c0': [], 'c1': ['c0'], 'c2': ['c1'], 'c3': ['c2'], 'c4': ['c3'], 'c5': ['c4'], 'c6': ['c5'], 'c7': ['c6'], 'side': ['c1']}, 'c1', 'c6'], ['c1'])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
simple fork	`['B']`	`['B']`	Passed
merge commit sees both parents	`['D']`	`['D']`	Passed
fast-forward: one side is an ancestor	`['B']`	`['B']`	Passed
same commit	`['D']`	`['D']`	Passed
criss-cross has two merge bases	`['X1', 'Y1']`	`['X1', 'Y1']`	Passed
long chain against a side branch	`['c1']`	`['c1']`	Passed
second parent carries the only common ancestor	`['a']`	`['a']`	Passed
unrelated histories	`[]`	`[]`	Passed
second parent deeper in history	`['a']`	`['a']`	Passed
first commit is the ancestor	`['c1']`	`['c1']`	Passed

SHA-256 / e02aef2250ef4ee9767bcf2b96f3e4a1adb36390d46fec1e5197f568f906194e

Verification & scope

A deterministic, bounded teaching model of one diff, patch or merge rule with stipulated conventions; it is not a production diff or version-control implementation and makes no claim of conformance to any specific tool. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:49:08.608331+00:00.

Case digest / cd3440b1e0632990315262f529dada85c55263d4d339c4bc9232a46378d02e30