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

Merge base selection: the oldest common ancestors are kept instead of the newest · case 01

The merge base is the root commit, so merges show every change since the beginning of history.

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

ROOT CAUSE

A common ancestor is discarded when another common ancestor is its ancestor, reversing the dominance test.

VERIFIED REPAIR

Discard a common ancestor when it is an ancestor of another common ancestor.

Unsuccessful approach: Pruning only ancestors of the two tips handles fast-forwards but keeps every older common ancestor of a real fork.

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 d in anc(c) 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	`['A']`	`['B']`	Failed
merge commit sees both parents	`['A']`	`['D']`	Failed
fast-forward: one side is an ancestor	`['A']`	`['B']`	Failed
same commit	`['A']`	`['D']`	Failed
criss-cross has two merge bases	`['R']`	`['X1', 'Y1']`	Failed
long chain against a side branch	`['c0']`	`['c1']`	Failed
second parent carries the only common ancestor	`['r']`	`['a']`	Failed
unrelated histories	`[]`	`[]`	Passed
second parent deeper in history	`['r']`	`['a']`	Failed
first commit is the ancestor	`['c0']`	`['c1']`	Failed

SHA-256 / dc03c3d279c306f1386eb43682a0479dadcdb46aa5ba083fa2fdd869cce14ff9

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 if d in (x, y))]
    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	`['A', 'B']`	`['B']`	Failed
merge commit sees both parents	`['A', 'B', 'D']`	`['D']`	Failed
fast-forward: one side is an ancestor	`['B']`	`['B']`	Passed
same commit	`['D']`	`['D']`	Passed
criss-cross has two merge bases	`['R', 'X1', 'Y1']`	`['X1', 'Y1']`	Failed
long chain against a side branch	`['c0', 'c1']`	`['c1']`	Failed
second parent carries the only common ancestor	`['a', 'r']`	`['a']`	Failed
unrelated histories	`[]`	`[]`	Passed
second parent deeper in history	`['a', 'r']`	`['a']`	Failed
first commit is the ancestor	`['c1']`	`['c1']`	Passed

SHA-256 / 019c7f42bcec5d6b20c8671df91cab36d149b7cbf2822ec1abb5218f3d148ae2

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.454263+00:00.

Case digest / 99d0ae8008cc4c6a2a03962a07cf26c605a0542bd63cb82f58141a79461c3aa3