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

Tree listing diff: directories are ordered by bare name · case 01

A file replaced by a same-named directory is reported as a type change, and entries around directories are misordered.

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

ROOT CAUSE

The sort key ignores the implicit trailing slash of directory names.

VERIFIED REPAIR

Order directories as if their name ended in "/".

Unsuccessful approach: Appending a slash to every name keeps files and directories with the same name equal.

Case contract

Compare two tree listings of [name, mode, hash]. Entries are ordered by name, with directories (mode 040000) compared as name + "/". Walk both in that order: entries only in the old tree are "D", only in the new tree "A". Entries matched by sort key report "T" when the mode type (first two digits) differs, else "M" when the hash or mode differs. Return [status, name] rows.

Why this case matters

Tree diffs drive status, rename detection and checkout; their ordering and type-change rules follow the object-store conventions.

1 / The failure

Exit 1

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

N = 1
observations = []
def solve(old, new):
    def key(x):
        return x[0]
    A = sorted(old, key=key)
    B = sorted(new, key=key)
    i = j = 0
    out = []
    while i < len(A) or j < len(B):
        if j >= len(B) or (i < len(A) and key(A[i]) < key(B[j])):
            out.append(['D', A[i][0]])
            i += 1
        elif i >= len(A) or key(B[j]) < key(A[i]):
            out.append(['A', B[j][0]])
            j += 1
        else:
            a, b = A[i], B[j]
            if a[1][:2] != b[1][:2]:
                out.append(['T', a[0]])
            elif a[2] != b[2] or a[1] != b[1]:
                out.append(['M', a[0]])
            i += 1
            j += 1
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('modified blob', [[['a.txt', '100644', 'h1']], [['a.txt', '100644', 'h2']]], [['M', 'a.txt']]), ('exec bit change is a modification', [[['run.sh', '100644', 'h']], [['run.sh', '100755', 'h']]], [['M', 'run.sh']]), ('file becomes a symlink', [[['lnk', '100644', 'h']], [['lnk', '120000', 'h']]], [['T', 'lnk']]), ('file replaced by a directory of the same name', [[['x', '100644', 'h']], [['x', '040000', 't']]], [['D', 'x'], ['A', 'x']]), ('directory sorts as name plus slash', [[['a.b', '100644', 'h'], ['a', '040000', 't1']], [['a.b', '100644', 'h'], ['a', '040000', 't2'], ['a-c', '100644', 'q']]], [['A', 'a-c'], ['M', 'a']]), ('trailing additions and deletions', [[['b', '100644', '1']], [['b', '100644', '1'], ['z0', '100644', 'n']]], [['A', 'z0']]), ('only deletions at the end', [[['m', '100644', '1'], ['y', '100644', '2']], [['m', '100644', '1']]], [['D', 'y']]), ('hashes sharing a long prefix', [[['k', '100644', 'abcdef0123']], [['k', '100644', 'abcdef0999']]], [['M', 'k']]), ('added then removed around a common entry', [[['a', '100644', '1'], ['c', '100644', '3']], [['b', '100644', '2'], ['c', '100644', '3']]], [['D', 'a'], ['A', 'b']])],
    2: [('modified blob', [[['a.txt', '100644', 'h1']], [['a.txt', '100644', 'h2']]], [['M', 'a.txt']]), ('exec bit change is a modification', [[['run.sh', '100644', 'h']], [['run.sh', '100755', 'h']]], [['M', 'run.sh']]), ('file becomes a symlink', [[['lnk', '100644', 'h']], [['lnk', '120000', 'h']]], [['T', 'lnk']]), ('file replaced by a directory of the same name', [[['x', '100644', 'h']], [['x', '040000', 't']]], [['D', 'x'], ['A', 'x']]), ('directory sorts as name plus slash', [[['a.b', '100644', 'h'], ['a', '040000', 't1']], [['a.b', '100644', 'h'], ['a', '040000', 't2'], ['a-c', '100644', 'q']]], [['A', 'a-c'], ['M', 'a']]), ('trailing additions and deletions', [[['b', '100644', '1']], [['b', '100644', '1'], ['z0', '100644', 'n'], ['z1', '100644', 'n']]], [['A', 'z0'], ['A', 'z1']]), ('only deletions at the end', [[['m', '100644', '1'], ['y', '100644', '2']], [['m', '100644', '1']]], [['D', 'y']]), ('hashes sharing a long prefix', [[['k', '100644', 'abcdef0123']], [['k', '100644', 'abcdef0999']]], [['M', 'k']]), ('added then removed around a common entry', [[['a', '100644', '1'], ['c', '100644', '3']], [['b', '100644', '2'], ['c', '100644', '3']]], [['D', 'a'], ['A', 'b']])],
    3: [('modified blob', [[['a.txt', '100644', 'h1']], [['a.txt', '100644', 'h2']]], [['M', 'a.txt']]), ('exec bit change is a modification', [[['run.sh', '100644', 'h']], [['run.sh', '100755', 'h']]], [['M', 'run.sh']]), ('file becomes a symlink', [[['lnk', '100644', 'h']], [['lnk', '120000', 'h']]], [['T', 'lnk']]), ('file replaced by a directory of the same name', [[['x', '100644', 'h']], [['x', '040000', 't']]], [['D', 'x'], ['A', 'x']]), ('directory sorts as name plus slash', [[['a.b', '100644', 'h'], ['a', '040000', 't1']], [['a.b', '100644', 'h'], ['a', '040000', 't2'], ['a-c', '100644', 'q']]], [['A', 'a-c'], ['M', 'a']]), ('trailing additions and deletions', [[['b', '100644', '1']], [['b', '100644', '1'], ['z0', '100644', 'n'], ['z1', '100644', 'n'], ['z2', '100644', 'n']]], [['A', 'z0'], ['A', 'z1'], ['A', 'z2']]), ('only deletions at the end', [[['m', '100644', '1'], ['y', '100644', '2']], [['m', '100644', '1']]], [['D', 'y']]), ('hashes sharing a long prefix', [[['k', '100644', 'abcdef0123']], [['k', '100644', 'abcdef0999']]], [['M', 'k']]), ('added then removed around a common entry', [[['a', '100644', '1'], ['c', '100644', '3']], [['b', '100644', '2'], ['c', '100644', '3']]], [['D', 'a'], ['A', 'b']])],
    4: [('modified blob', [[['a.txt', '100644', 'h1']], [['a.txt', '100644', 'h2']]], [['M', 'a.txt']]), ('exec bit change is a modification', [[['run.sh', '100644', 'h']], [['run.sh', '100755', 'h']]], [['M', 'run.sh']]), ('file becomes a symlink', [[['lnk', '100644', 'h']], [['lnk', '120000', 'h']]], [['T', 'lnk']]), ('file replaced by a directory of the same name', [[['x', '100644', 'h']], [['x', '040000', 't']]], [['D', 'x'], ['A', 'x']]), ('directory sorts as name plus slash', [[['a.b', '100644', 'h'], ['a', '040000', 't1']], [['a.b', '100644', 'h'], ['a', '040000', 't2'], ['a-c', '100644', 'q']]], [['A', 'a-c'], ['M', 'a']]), ('trailing additions and deletions', [[['b', '100644', '1']], [['b', '100644', '1'], ['z0', '100644', 'n'], ['z1', '100644', 'n'], ['z2', '100644', 'n'], ['z3', '100644', 'n']]], [['A', 'z0'], ['A', 'z1'], ['A', 'z2'], ['A', 'z3']]), ('only deletions at the end', [[['m', '100644', '1'], ['y', '100644', '2']], [['m', '100644', '1']]], [['D', 'y']]), ('hashes sharing a long prefix', [[['k', '100644', 'abcdef0123']], [['k', '100644', 'abcdef0999']]], [['M', 'k']]), ('added then removed around a common entry', [[['a', '100644', '1'], ['c', '100644', '3']], [['b', '100644', '2'], ['c', '100644', '3']]], [['D', 'a'], ['A', 'b']])],
    5: [('modified blob', [[['a.txt', '100644', 'h1']], [['a.txt', '100644', 'h2']]], [['M', 'a.txt']]), ('exec bit change is a modification', [[['run.sh', '100644', 'h']], [['run.sh', '100755', 'h']]], [['M', 'run.sh']]), ('file becomes a symlink', [[['lnk', '100644', 'h']], [['lnk', '120000', 'h']]], [['T', 'lnk']]), ('file replaced by a directory of the same name', [[['x', '100644', 'h']], [['x', '040000', 't']]], [['D', 'x'], ['A', 'x']]), ('directory sorts as name plus slash', [[['a.b', '100644', 'h'], ['a', '040000', 't1']], [['a.b', '100644', 'h'], ['a', '040000', 't2'], ['a-c', '100644', 'q']]], [['A', 'a-c'], ['M', 'a']]), ('trailing additions and deletions', [[['b', '100644', '1']], [['b', '100644', '1'], ['z0', '100644', 'n'], ['z1', '100644', 'n'], ['z2', '100644', 'n'], ['z3', '100644', 'n'], ['z4', '100644', 'n']]], [['A', 'z0'], ['A', 'z1'], ['A', 'z2'], ['A', 'z3'], ['A', 'z4']]), ('only deletions at the end', [[['m', '100644', '1'], ['y', '100644', '2']], [['m', '100644', '1']]], [['D', 'y']]), ('hashes sharing a long prefix', [[['k', '100644', 'abcdef0123']], [['k', '100644', 'abcdef0999']]], [['M', 'k']]), ('added then removed around a common entry', [[['a', '100644', '1'], ['c', '100644', '3']], [['b', '100644', '2'], ['c', '100644', '3']]], [['D', 'a'], ['A', 'b']])],
}[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
modified blob	`[['M', 'a.txt']]`	`[['M', 'a.txt']]`	Passed
exec bit change is a modification	`[['M', 'run.sh']]`	`[['M', 'run.sh']]`	Passed
file becomes a symlink	`[['T', 'lnk']]`	`[['T', 'lnk']]`	Passed
file replaced by a directory of the same name	`[['T', 'x']]`	`[['D', 'x'], ['A', 'x']]`	Failed
directory sorts as name plus slash	`[['M', 'a'], ['A', 'a-c']]`	`[['A', 'a-c'], ['M', 'a']]`	Failed
trailing additions and deletions	`[['A', 'z0']]`	`[['A', 'z0']]`	Passed
only deletions at the end	`[['D', 'y']]`	`[['D', 'y']]`	Passed
hashes sharing a long prefix	`[['M', 'k']]`	`[['M', 'k']]`	Passed
added then removed around a common entry	`[['D', 'a'], ['A', 'b']]`	`[['D', 'a'], ['A', 'b']]`	Passed

SHA-256 / f2eef743dc977794fa55b1dac50650055ef7d4333bbb90dc9d4f614b0808721f

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(old, new):
    def key(x):
        return x[0] + '/'
    A = sorted(old, key=key)
    B = sorted(new, key=key)
    i = j = 0
    out = []
    while i < len(A) or j < len(B):
        if j >= len(B) or (i < len(A) and key(A[i]) < key(B[j])):
            out.append(['D', A[i][0]])
            i += 1
        elif i >= len(A) or key(B[j]) < key(A[i]):
            out.append(['A', B[j][0]])
            j += 1
        else:
            a, b = A[i], B[j]
            if a[1][:2] != b[1][:2]:
                out.append(['T', a[0]])
            elif a[2] != b[2] or a[1] != b[1]:
                out.append(['M', a[0]])
            i += 1
            j += 1
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('modified blob', [[['a.txt', '100644', 'h1']], [['a.txt', '100644', 'h2']]], [['M', 'a.txt']]), ('exec bit change is a modification', [[['run.sh', '100644', 'h']], [['run.sh', '100755', 'h']]], [['M', 'run.sh']]), ('file becomes a symlink', [[['lnk', '100644', 'h']], [['lnk', '120000', 'h']]], [['T', 'lnk']]), ('file replaced by a directory of the same name', [[['x', '100644', 'h']], [['x', '040000', 't']]], [['D', 'x'], ['A', 'x']]), ('directory sorts as name plus slash', [[['a.b', '100644', 'h'], ['a', '040000', 't1']], [['a.b', '100644', 'h'], ['a', '040000', 't2'], ['a-c', '100644', 'q']]], [['A', 'a-c'], ['M', 'a']]), ('trailing additions and deletions', [[['b', '100644', '1']], [['b', '100644', '1'], ['z0', '100644', 'n']]], [['A', 'z0']]), ('only deletions at the end', [[['m', '100644', '1'], ['y', '100644', '2']], [['m', '100644', '1']]], [['D', 'y']]), ('hashes sharing a long prefix', [[['k', '100644', 'abcdef0123']], [['k', '100644', 'abcdef0999']]], [['M', 'k']]), ('added then removed around a common entry', [[['a', '100644', '1'], ['c', '100644', '3']], [['b', '100644', '2'], ['c', '100644', '3']]], [['D', 'a'], ['A', 'b']])],
    2: [('modified blob', [[['a.txt', '100644', 'h1']], [['a.txt', '100644', 'h2']]], [['M', 'a.txt']]), ('exec bit change is a modification', [[['run.sh', '100644', 'h']], [['run.sh', '100755', 'h']]], [['M', 'run.sh']]), ('file becomes a symlink', [[['lnk', '100644', 'h']], [['lnk', '120000', 'h']]], [['T', 'lnk']]), ('file replaced by a directory of the same name', [[['x', '100644', 'h']], [['x', '040000', 't']]], [['D', 'x'], ['A', 'x']]), ('directory sorts as name plus slash', [[['a.b', '100644', 'h'], ['a', '040000', 't1']], [['a.b', '100644', 'h'], ['a', '040000', 't2'], ['a-c', '100644', 'q']]], [['A', 'a-c'], ['M', 'a']]), ('trailing additions and deletions', [[['b', '100644', '1']], [['b', '100644', '1'], ['z0', '100644', 'n'], ['z1', '100644', 'n']]], [['A', 'z0'], ['A', 'z1']]), ('only deletions at the end', [[['m', '100644', '1'], ['y', '100644', '2']], [['m', '100644', '1']]], [['D', 'y']]), ('hashes sharing a long prefix', [[['k', '100644', 'abcdef0123']], [['k', '100644', 'abcdef0999']]], [['M', 'k']]), ('added then removed around a common entry', [[['a', '100644', '1'], ['c', '100644', '3']], [['b', '100644', '2'], ['c', '100644', '3']]], [['D', 'a'], ['A', 'b']])],
    3: [('modified blob', [[['a.txt', '100644', 'h1']], [['a.txt', '100644', 'h2']]], [['M', 'a.txt']]), ('exec bit change is a modification', [[['run.sh', '100644', 'h']], [['run.sh', '100755', 'h']]], [['M', 'run.sh']]), ('file becomes a symlink', [[['lnk', '100644', 'h']], [['lnk', '120000', 'h']]], [['T', 'lnk']]), ('file replaced by a directory of the same name', [[['x', '100644', 'h']], [['x', '040000', 't']]], [['D', 'x'], ['A', 'x']]), ('directory sorts as name plus slash', [[['a.b', '100644', 'h'], ['a', '040000', 't1']], [['a.b', '100644', 'h'], ['a', '040000', 't2'], ['a-c', '100644', 'q']]], [['A', 'a-c'], ['M', 'a']]), ('trailing additions and deletions', [[['b', '100644', '1']], [['b', '100644', '1'], ['z0', '100644', 'n'], ['z1', '100644', 'n'], ['z2', '100644', 'n']]], [['A', 'z0'], ['A', 'z1'], ['A', 'z2']]), ('only deletions at the end', [[['m', '100644', '1'], ['y', '100644', '2']], [['m', '100644', '1']]], [['D', 'y']]), ('hashes sharing a long prefix', [[['k', '100644', 'abcdef0123']], [['k', '100644', 'abcdef0999']]], [['M', 'k']]), ('added then removed around a common entry', [[['a', '100644', '1'], ['c', '100644', '3']], [['b', '100644', '2'], ['c', '100644', '3']]], [['D', 'a'], ['A', 'b']])],
    4: [('modified blob', [[['a.txt', '100644', 'h1']], [['a.txt', '100644', 'h2']]], [['M', 'a.txt']]), ('exec bit change is a modification', [[['run.sh', '100644', 'h']], [['run.sh', '100755', 'h']]], [['M', 'run.sh']]), ('file becomes a symlink', [[['lnk', '100644', 'h']], [['lnk', '120000', 'h']]], [['T', 'lnk']]), ('file replaced by a directory of the same name', [[['x', '100644', 'h']], [['x', '040000', 't']]], [['D', 'x'], ['A', 'x']]), ('directory sorts as name plus slash', [[['a.b', '100644', 'h'], ['a', '040000', 't1']], [['a.b', '100644', 'h'], ['a', '040000', 't2'], ['a-c', '100644', 'q']]], [['A', 'a-c'], ['M', 'a']]), ('trailing additions and deletions', [[['b', '100644', '1']], [['b', '100644', '1'], ['z0', '100644', 'n'], ['z1', '100644', 'n'], ['z2', '100644', 'n'], ['z3', '100644', 'n']]], [['A', 'z0'], ['A', 'z1'], ['A', 'z2'], ['A', 'z3']]), ('only deletions at the end', [[['m', '100644', '1'], ['y', '100644', '2']], [['m', '100644', '1']]], [['D', 'y']]), ('hashes sharing a long prefix', [[['k', '100644', 'abcdef0123']], [['k', '100644', 'abcdef0999']]], [['M', 'k']]), ('added then removed around a common entry', [[['a', '100644', '1'], ['c', '100644', '3']], [['b', '100644', '2'], ['c', '100644', '3']]], [['D', 'a'], ['A', 'b']])],
    5: [('modified blob', [[['a.txt', '100644', 'h1']], [['a.txt', '100644', 'h2']]], [['M', 'a.txt']]), ('exec bit change is a modification', [[['run.sh', '100644', 'h']], [['run.sh', '100755', 'h']]], [['M', 'run.sh']]), ('file becomes a symlink', [[['lnk', '100644', 'h']], [['lnk', '120000', 'h']]], [['T', 'lnk']]), ('file replaced by a directory of the same name', [[['x', '100644', 'h']], [['x', '040000', 't']]], [['D', 'x'], ['A', 'x']]), ('directory sorts as name plus slash', [[['a.b', '100644', 'h'], ['a', '040000', 't1']], [['a.b', '100644', 'h'], ['a', '040000', 't2'], ['a-c', '100644', 'q']]], [['A', 'a-c'], ['M', 'a']]), ('trailing additions and deletions', [[['b', '100644', '1']], [['b', '100644', '1'], ['z0', '100644', 'n'], ['z1', '100644', 'n'], ['z2', '100644', 'n'], ['z3', '100644', 'n'], ['z4', '100644', 'n']]], [['A', 'z0'], ['A', 'z1'], ['A', 'z2'], ['A', 'z3'], ['A', 'z4']]), ('only deletions at the end', [[['m', '100644', '1'], ['y', '100644', '2']], [['m', '100644', '1']]], [['D', 'y']]), ('hashes sharing a long prefix', [[['k', '100644', 'abcdef0123']], [['k', '100644', 'abcdef0999']]], [['M', 'k']]), ('added then removed around a common entry', [[['a', '100644', '1'], ['c', '100644', '3']], [['b', '100644', '2'], ['c', '100644', '3']]], [['D', 'a'], ['A', 'b']])],
}[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
modified blob	`[['M', 'a.txt']]`	`[['M', 'a.txt']]`	Passed
exec bit change is a modification	`[['M', 'run.sh']]`	`[['M', 'run.sh']]`	Passed
file becomes a symlink	`[['T', 'lnk']]`	`[['T', 'lnk']]`	Passed
file replaced by a directory of the same name	`[['T', 'x']]`	`[['D', 'x'], ['A', 'x']]`	Failed
directory sorts as name plus slash	`[['A', 'a-c'], ['M', 'a']]`	`[['A', 'a-c'], ['M', 'a']]`	Passed
trailing additions and deletions	`[['A', 'z0']]`	`[['A', 'z0']]`	Passed
only deletions at the end	`[['D', 'y']]`	`[['D', 'y']]`	Passed
hashes sharing a long prefix	`[['M', 'k']]`	`[['M', 'k']]`	Passed
added then removed around a common entry	`[['D', 'a'], ['A', 'b']]`	`[['D', 'a'], ['A', 'b']]`	Passed

SHA-256 / 2211c7e7ea9ffb0d4a2d62a9f8ecd6e2034fdc8a55f5d10361745fe4e0fbb37a

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(old, new):
    def key(x):
        return x[0] + '/' if x[1] == '040000' else x[0]
    A = sorted(old, key=key)
    B = sorted(new, key=key)
    i = j = 0
    out = []
    while i < len(A) or j < len(B):
        if j >= len(B) or (i < len(A) and key(A[i]) < key(B[j])):
            out.append(['D', A[i][0]])
            i += 1
        elif i >= len(A) or key(B[j]) < key(A[i]):
            out.append(['A', B[j][0]])
            j += 1
        else:
            a, b = A[i], B[j]
            if a[1][:2] != b[1][:2]:
                out.append(['T', a[0]])
            elif a[2] != b[2] or a[1] != b[1]:
                out.append(['M', a[0]])
            i += 1
            j += 1
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('modified blob', [[['a.txt', '100644', 'h1']], [['a.txt', '100644', 'h2']]], [['M', 'a.txt']]), ('exec bit change is a modification', [[['run.sh', '100644', 'h']], [['run.sh', '100755', 'h']]], [['M', 'run.sh']]), ('file becomes a symlink', [[['lnk', '100644', 'h']], [['lnk', '120000', 'h']]], [['T', 'lnk']]), ('file replaced by a directory of the same name', [[['x', '100644', 'h']], [['x', '040000', 't']]], [['D', 'x'], ['A', 'x']]), ('directory sorts as name plus slash', [[['a.b', '100644', 'h'], ['a', '040000', 't1']], [['a.b', '100644', 'h'], ['a', '040000', 't2'], ['a-c', '100644', 'q']]], [['A', 'a-c'], ['M', 'a']]), ('trailing additions and deletions', [[['b', '100644', '1']], [['b', '100644', '1'], ['z0', '100644', 'n']]], [['A', 'z0']]), ('only deletions at the end', [[['m', '100644', '1'], ['y', '100644', '2']], [['m', '100644', '1']]], [['D', 'y']]), ('hashes sharing a long prefix', [[['k', '100644', 'abcdef0123']], [['k', '100644', 'abcdef0999']]], [['M', 'k']]), ('added then removed around a common entry', [[['a', '100644', '1'], ['c', '100644', '3']], [['b', '100644', '2'], ['c', '100644', '3']]], [['D', 'a'], ['A', 'b']])],
    2: [('modified blob', [[['a.txt', '100644', 'h1']], [['a.txt', '100644', 'h2']]], [['M', 'a.txt']]), ('exec bit change is a modification', [[['run.sh', '100644', 'h']], [['run.sh', '100755', 'h']]], [['M', 'run.sh']]), ('file becomes a symlink', [[['lnk', '100644', 'h']], [['lnk', '120000', 'h']]], [['T', 'lnk']]), ('file replaced by a directory of the same name', [[['x', '100644', 'h']], [['x', '040000', 't']]], [['D', 'x'], ['A', 'x']]), ('directory sorts as name plus slash', [[['a.b', '100644', 'h'], ['a', '040000', 't1']], [['a.b', '100644', 'h'], ['a', '040000', 't2'], ['a-c', '100644', 'q']]], [['A', 'a-c'], ['M', 'a']]), ('trailing additions and deletions', [[['b', '100644', '1']], [['b', '100644', '1'], ['z0', '100644', 'n'], ['z1', '100644', 'n']]], [['A', 'z0'], ['A', 'z1']]), ('only deletions at the end', [[['m', '100644', '1'], ['y', '100644', '2']], [['m', '100644', '1']]], [['D', 'y']]), ('hashes sharing a long prefix', [[['k', '100644', 'abcdef0123']], [['k', '100644', 'abcdef0999']]], [['M', 'k']]), ('added then removed around a common entry', [[['a', '100644', '1'], ['c', '100644', '3']], [['b', '100644', '2'], ['c', '100644', '3']]], [['D', 'a'], ['A', 'b']])],
    3: [('modified blob', [[['a.txt', '100644', 'h1']], [['a.txt', '100644', 'h2']]], [['M', 'a.txt']]), ('exec bit change is a modification', [[['run.sh', '100644', 'h']], [['run.sh', '100755', 'h']]], [['M', 'run.sh']]), ('file becomes a symlink', [[['lnk', '100644', 'h']], [['lnk', '120000', 'h']]], [['T', 'lnk']]), ('file replaced by a directory of the same name', [[['x', '100644', 'h']], [['x', '040000', 't']]], [['D', 'x'], ['A', 'x']]), ('directory sorts as name plus slash', [[['a.b', '100644', 'h'], ['a', '040000', 't1']], [['a.b', '100644', 'h'], ['a', '040000', 't2'], ['a-c', '100644', 'q']]], [['A', 'a-c'], ['M', 'a']]), ('trailing additions and deletions', [[['b', '100644', '1']], [['b', '100644', '1'], ['z0', '100644', 'n'], ['z1', '100644', 'n'], ['z2', '100644', 'n']]], [['A', 'z0'], ['A', 'z1'], ['A', 'z2']]), ('only deletions at the end', [[['m', '100644', '1'], ['y', '100644', '2']], [['m', '100644', '1']]], [['D', 'y']]), ('hashes sharing a long prefix', [[['k', '100644', 'abcdef0123']], [['k', '100644', 'abcdef0999']]], [['M', 'k']]), ('added then removed around a common entry', [[['a', '100644', '1'], ['c', '100644', '3']], [['b', '100644', '2'], ['c', '100644', '3']]], [['D', 'a'], ['A', 'b']])],
    4: [('modified blob', [[['a.txt', '100644', 'h1']], [['a.txt', '100644', 'h2']]], [['M', 'a.txt']]), ('exec bit change is a modification', [[['run.sh', '100644', 'h']], [['run.sh', '100755', 'h']]], [['M', 'run.sh']]), ('file becomes a symlink', [[['lnk', '100644', 'h']], [['lnk', '120000', 'h']]], [['T', 'lnk']]), ('file replaced by a directory of the same name', [[['x', '100644', 'h']], [['x', '040000', 't']]], [['D', 'x'], ['A', 'x']]), ('directory sorts as name plus slash', [[['a.b', '100644', 'h'], ['a', '040000', 't1']], [['a.b', '100644', 'h'], ['a', '040000', 't2'], ['a-c', '100644', 'q']]], [['A', 'a-c'], ['M', 'a']]), ('trailing additions and deletions', [[['b', '100644', '1']], [['b', '100644', '1'], ['z0', '100644', 'n'], ['z1', '100644', 'n'], ['z2', '100644', 'n'], ['z3', '100644', 'n']]], [['A', 'z0'], ['A', 'z1'], ['A', 'z2'], ['A', 'z3']]), ('only deletions at the end', [[['m', '100644', '1'], ['y', '100644', '2']], [['m', '100644', '1']]], [['D', 'y']]), ('hashes sharing a long prefix', [[['k', '100644', 'abcdef0123']], [['k', '100644', 'abcdef0999']]], [['M', 'k']]), ('added then removed around a common entry', [[['a', '100644', '1'], ['c', '100644', '3']], [['b', '100644', '2'], ['c', '100644', '3']]], [['D', 'a'], ['A', 'b']])],
    5: [('modified blob', [[['a.txt', '100644', 'h1']], [['a.txt', '100644', 'h2']]], [['M', 'a.txt']]), ('exec bit change is a modification', [[['run.sh', '100644', 'h']], [['run.sh', '100755', 'h']]], [['M', 'run.sh']]), ('file becomes a symlink', [[['lnk', '100644', 'h']], [['lnk', '120000', 'h']]], [['T', 'lnk']]), ('file replaced by a directory of the same name', [[['x', '100644', 'h']], [['x', '040000', 't']]], [['D', 'x'], ['A', 'x']]), ('directory sorts as name plus slash', [[['a.b', '100644', 'h'], ['a', '040000', 't1']], [['a.b', '100644', 'h'], ['a', '040000', 't2'], ['a-c', '100644', 'q']]], [['A', 'a-c'], ['M', 'a']]), ('trailing additions and deletions', [[['b', '100644', '1']], [['b', '100644', '1'], ['z0', '100644', 'n'], ['z1', '100644', 'n'], ['z2', '100644', 'n'], ['z3', '100644', 'n'], ['z4', '100644', 'n']]], [['A', 'z0'], ['A', 'z1'], ['A', 'z2'], ['A', 'z3'], ['A', 'z4']]), ('only deletions at the end', [[['m', '100644', '1'], ['y', '100644', '2']], [['m', '100644', '1']]], [['D', 'y']]), ('hashes sharing a long prefix', [[['k', '100644', 'abcdef0123']], [['k', '100644', 'abcdef0999']]], [['M', 'k']]), ('added then removed around a common entry', [[['a', '100644', '1'], ['c', '100644', '3']], [['b', '100644', '2'], ['c', '100644', '3']]], [['D', 'a'], ['A', 'b']])],
}[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
modified blob	`[['M', 'a.txt']]`	`[['M', 'a.txt']]`	Passed
exec bit change is a modification	`[['M', 'run.sh']]`	`[['M', 'run.sh']]`	Passed
file becomes a symlink	`[['T', 'lnk']]`	`[['T', 'lnk']]`	Passed
file replaced by a directory of the same name	`[['D', 'x'], ['A', 'x']]`	`[['D', 'x'], ['A', 'x']]`	Passed
directory sorts as name plus slash	`[['A', 'a-c'], ['M', 'a']]`	`[['A', 'a-c'], ['M', 'a']]`	Passed
trailing additions and deletions	`[['A', 'z0']]`	`[['A', 'z0']]`	Passed
only deletions at the end	`[['D', 'y']]`	`[['D', 'y']]`	Passed
hashes sharing a long prefix	`[['M', 'k']]`	`[['M', 'k']]`	Passed
added then removed around a common entry	`[['D', 'a'], ['A', 'b']]`	`[['D', 'a'], ['A', 'b']]`	Passed

SHA-256 / 65a54a854bdf51e007e9d36898821d1d01b1febc67a2764e097b92defbe15097

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

Case digest / 433c85aa961526d2776baff31b70b0590684641ac7d2757703432274b29cb8fa