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

Merge base selection: a commit is not treated as its own ancestor · case 01

When one branch contains the other, the merge base is reported as an older commit instead of the branch tip.

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

ROOT CAUSE

Ancestor traversal starts from the parents, excluding the starting commit.

VERIFIED REPAIR

Include the starting commit in its own ancestor set.

Unsuccessful approach: Adding the first commit back on one side only fails when the second commit is the ancestor.

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 = list(parents.get(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	`['A']`	`['B']`	Failed
same commit	`['B']`	`['D']`	Failed
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	`['c0']`	`['c1']`	Failed

SHA-256 / 41ae1c8b4ce7e02fe2aadc1f76874813d8787c193954b0c68445db9487f49d18

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 = list(parents.get(c, []))
        while stack:
            k = stack.pop()
            if k in seen:
                continue
            seen.add(k)
            stack.extend(parents.get(k, []))
        return seen
    common = (anc(x) | {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	`['B']`	`['D']`	Failed
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 / 6d6d06f151e17f21df0bfe755dd58e0bfcedfc5203c92fbc8bf09832bee2f411

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

Case digest / 5fd016477fef3e77938a40a9766f36a0f73996d74312e2aeef3cbe8009f45216