FA-75496 / Text diff and three-way merge / Open access
End-of-file newline diff: lines differing only in the final newline compare equal · case 01
Adding or removing the final newline produces an empty diff.
ROOT CAUSE
Token equality compares only line text, ignoring the terminator flag.
VERIFIED REPAIR
Two tokens are equal only when both text and terminator flag match.
Unsuccessful approach: Allowing a terminated line to match an unterminated one still hides one direction of the change.
Case contract
Split each text on "\n" into [line, terminated] tokens; a final empty piece produces no token, a final non-empty piece is an unterminated token. Diff the token lists with an LCS walk (tokens equal only if text and terminator flag both match, deletions before insertions on ties) and render each op as tag + text, followed by "\ No newline at end of file" after any unterminated token.
Why this case matters
Unified diffs must show a change that only adds or removes the final newline, and mark which side lacks it.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(old, new):
def toks(s):
parts = s.split('\n')
res = [[p, True] for p in parts[:-1]]
if parts[-1] != '':
res.append([parts[-1], False])
return res
def same(x, y):
return x[0] == y[0]
A, B = toks(old), toks(new)
n, m = len(A), len(B)
T = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
T[i][j] = T[i + 1][j + 1] + 1 if same(A[i], B[j]) else max(T[i + 1][j], T[i][j + 1])
ops = []
i = j = 0
while i < n or j < m:
if i < n and j < m and same(A[i], B[j]):
ops.append((' ', A[i])); i += 1; j += 1
elif i < n and (j >= m or T[i + 1][j] >= T[i][j + 1]):
ops.append(('-', A[i])); i += 1
else:
ops.append(('+', B[j])); j += 1
out = []
for tag, (text, nl) in ops:
out.append(tag + text)
if not nl:
out.append('\\ No newline at end of file')
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('newline added at end of file', ['a\nb', 'a\nb\n'], [' a', '-b', '\\ No newline at end of file', '+b']), ('newline removed at end of file', ['a\nb\n', 'a\nb'], [' a', '-b', '+b', '\\ No newline at end of file']), ('unchanged last line without newline', ['x\ny', 'X\ny'], ['-x', '+X', ' y', '\\ No newline at end of file']), ('both terminated', ['p\nq\n', 'p\nr\n'], [' p', '-q', '+r']), ('empty to one unterminated line', ['', 'only1'], ['+only1', '\\ No newline at end of file']), ('last line changed and unterminated', ['k\nold', 'k\nnew'], [' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file']), ('trailing blank line', ['a\n\n', 'a\n'], [' a', '-']), ('identical texts', ['s\nt\n', 's\nt\n'], [' s', ' t'])],
2: [('newline added at end of file', ['a\nb', 'a\nb\n'], [' a', '-b', '\\ No newline at end of file', '+b']), ('newline removed at end of file', ['a\nb\n', 'a\nb'], [' a', '-b', '+b', '\\ No newline at end of file']), ('unchanged last line without newline', ['x\ny', 'X\ny'], ['-x', '+X', ' y', '\\ No newline at end of file']), ('both terminated', ['p\nq\n', 'p\nr\n'], [' p', '-q', '+r']), ('empty to one unterminated line', ['', 'only2'], ['+only2', '\\ No newline at end of file']), ('last line changed and unterminated', ['k\nk\nold', 'k\nk\nnew'], [' k', ' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file']), ('trailing blank line', ['a\n\n', 'a\n'], [' a', '-']), ('identical texts', ['s\nt\n', 's\nt\n'], [' s', ' t'])],
3: [('newline added at end of file', ['a\nb', 'a\nb\n'], [' a', '-b', '\\ No newline at end of file', '+b']), ('newline removed at end of file', ['a\nb\n', 'a\nb'], [' a', '-b', '+b', '\\ No newline at end of file']), ('unchanged last line without newline', ['x\ny', 'X\ny'], ['-x', '+X', ' y', '\\ No newline at end of file']), ('both terminated', ['p\nq\n', 'p\nr\n'], [' p', '-q', '+r']), ('empty to one unterminated line', ['', 'only3'], ['+only3', '\\ No newline at end of file']), ('last line changed and unterminated', ['k\nk\nk\nold', 'k\nk\nk\nnew'], [' k', ' k', ' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file']), ('trailing blank line', ['a\n\n', 'a\n'], [' a', '-']), ('identical texts', ['s\nt\n', 's\nt\n'], [' s', ' t'])],
4: [('newline added at end of file', ['a\nb', 'a\nb\n'], [' a', '-b', '\\ No newline at end of file', '+b']), ('newline removed at end of file', ['a\nb\n', 'a\nb'], [' a', '-b', '+b', '\\ No newline at end of file']), ('unchanged last line without newline', ['x\ny', 'X\ny'], ['-x', '+X', ' y', '\\ No newline at end of file']), ('both terminated', ['p\nq\n', 'p\nr\n'], [' p', '-q', '+r']), ('empty to one unterminated line', ['', 'only4'], ['+only4', '\\ No newline at end of file']), ('last line changed and unterminated', ['k\nk\nk\nk\nold', 'k\nk\nk\nk\nnew'], [' k', ' k', ' k', ' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file']), ('trailing blank line', ['a\n\n', 'a\n'], [' a', '-']), ('identical texts', ['s\nt\n', 's\nt\n'], [' s', ' t'])],
5: [('newline added at end of file', ['a\nb', 'a\nb\n'], [' a', '-b', '\\ No newline at end of file', '+b']), ('newline removed at end of file', ['a\nb\n', 'a\nb'], [' a', '-b', '+b', '\\ No newline at end of file']), ('unchanged last line without newline', ['x\ny', 'X\ny'], ['-x', '+X', ' y', '\\ No newline at end of file']), ('both terminated', ['p\nq\n', 'p\nr\n'], [' p', '-q', '+r']), ('empty to one unterminated line', ['', 'only5'], ['+only5', '\\ No newline at end of file']), ('last line changed and unterminated', ['k\nk\nk\nk\nk\nold', 'k\nk\nk\nk\nk\nnew'], [' k', ' k', ' k', ' k', ' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file']), ('trailing blank line', ['a\n\n', 'a\n'], [' a', '-']), ('identical texts', ['s\nt\n', 's\nt\n'], [' s', ' t'])],
}[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 |
|---|---|---|---|
| newline added at end of file | [' a', ' b', '\\ No newline at end of file'] | [' a', '-b', '\\ No newline at end of file', '+b'] | Failed |
| newline removed at end of file | [' a', ' b'] | [' a', '-b', '+b', '\\ No newline at end of file'] | Failed |
| unchanged last line without newline | ['-x', '+X', ' y', '\\ No newline at end of file'] | ['-x', '+X', ' y', '\\ No newline at end of file'] | Passed |
| both terminated | [' p', '-q', '+r'] | [' p', '-q', '+r'] | Passed |
| empty to one unterminated line | ['+only1', '\\ No newline at end of file'] | ['+only1', '\\ No newline at end of file'] | Passed |
| last line changed and unterminated | [' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file'] | [' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file'] | Passed |
| trailing blank line | [' a', '-'] | [' a', '-'] | Passed |
| identical texts | [' s', ' t'] | [' s', ' t'] | Passed |
SHA-256 / b1dc83dcd11262acb75f7c1c43d976e6a1ae36c3b44dbde9f6188ff3d058c4e4
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(old, new):
def toks(s):
parts = s.split('\n')
res = [[p, True] for p in parts[:-1]]
if parts[-1] != '':
res.append([parts[-1], False])
return res
def same(x, y):
return x[0] == y[0] and x[1] >= y[1]
A, B = toks(old), toks(new)
n, m = len(A), len(B)
T = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
T[i][j] = T[i + 1][j + 1] + 1 if same(A[i], B[j]) else max(T[i + 1][j], T[i][j + 1])
ops = []
i = j = 0
while i < n or j < m:
if i < n and j < m and same(A[i], B[j]):
ops.append((' ', A[i])); i += 1; j += 1
elif i < n and (j >= m or T[i + 1][j] >= T[i][j + 1]):
ops.append(('-', A[i])); i += 1
else:
ops.append(('+', B[j])); j += 1
out = []
for tag, (text, nl) in ops:
out.append(tag + text)
if not nl:
out.append('\\ No newline at end of file')
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('newline added at end of file', ['a\nb', 'a\nb\n'], [' a', '-b', '\\ No newline at end of file', '+b']), ('newline removed at end of file', ['a\nb\n', 'a\nb'], [' a', '-b', '+b', '\\ No newline at end of file']), ('unchanged last line without newline', ['x\ny', 'X\ny'], ['-x', '+X', ' y', '\\ No newline at end of file']), ('both terminated', ['p\nq\n', 'p\nr\n'], [' p', '-q', '+r']), ('empty to one unterminated line', ['', 'only1'], ['+only1', '\\ No newline at end of file']), ('last line changed and unterminated', ['k\nold', 'k\nnew'], [' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file']), ('trailing blank line', ['a\n\n', 'a\n'], [' a', '-']), ('identical texts', ['s\nt\n', 's\nt\n'], [' s', ' t'])],
2: [('newline added at end of file', ['a\nb', 'a\nb\n'], [' a', '-b', '\\ No newline at end of file', '+b']), ('newline removed at end of file', ['a\nb\n', 'a\nb'], [' a', '-b', '+b', '\\ No newline at end of file']), ('unchanged last line without newline', ['x\ny', 'X\ny'], ['-x', '+X', ' y', '\\ No newline at end of file']), ('both terminated', ['p\nq\n', 'p\nr\n'], [' p', '-q', '+r']), ('empty to one unterminated line', ['', 'only2'], ['+only2', '\\ No newline at end of file']), ('last line changed and unterminated', ['k\nk\nold', 'k\nk\nnew'], [' k', ' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file']), ('trailing blank line', ['a\n\n', 'a\n'], [' a', '-']), ('identical texts', ['s\nt\n', 's\nt\n'], [' s', ' t'])],
3: [('newline added at end of file', ['a\nb', 'a\nb\n'], [' a', '-b', '\\ No newline at end of file', '+b']), ('newline removed at end of file', ['a\nb\n', 'a\nb'], [' a', '-b', '+b', '\\ No newline at end of file']), ('unchanged last line without newline', ['x\ny', 'X\ny'], ['-x', '+X', ' y', '\\ No newline at end of file']), ('both terminated', ['p\nq\n', 'p\nr\n'], [' p', '-q', '+r']), ('empty to one unterminated line', ['', 'only3'], ['+only3', '\\ No newline at end of file']), ('last line changed and unterminated', ['k\nk\nk\nold', 'k\nk\nk\nnew'], [' k', ' k', ' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file']), ('trailing blank line', ['a\n\n', 'a\n'], [' a', '-']), ('identical texts', ['s\nt\n', 's\nt\n'], [' s', ' t'])],
4: [('newline added at end of file', ['a\nb', 'a\nb\n'], [' a', '-b', '\\ No newline at end of file', '+b']), ('newline removed at end of file', ['a\nb\n', 'a\nb'], [' a', '-b', '+b', '\\ No newline at end of file']), ('unchanged last line without newline', ['x\ny', 'X\ny'], ['-x', '+X', ' y', '\\ No newline at end of file']), ('both terminated', ['p\nq\n', 'p\nr\n'], [' p', '-q', '+r']), ('empty to one unterminated line', ['', 'only4'], ['+only4', '\\ No newline at end of file']), ('last line changed and unterminated', ['k\nk\nk\nk\nold', 'k\nk\nk\nk\nnew'], [' k', ' k', ' k', ' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file']), ('trailing blank line', ['a\n\n', 'a\n'], [' a', '-']), ('identical texts', ['s\nt\n', 's\nt\n'], [' s', ' t'])],
5: [('newline added at end of file', ['a\nb', 'a\nb\n'], [' a', '-b', '\\ No newline at end of file', '+b']), ('newline removed at end of file', ['a\nb\n', 'a\nb'], [' a', '-b', '+b', '\\ No newline at end of file']), ('unchanged last line without newline', ['x\ny', 'X\ny'], ['-x', '+X', ' y', '\\ No newline at end of file']), ('both terminated', ['p\nq\n', 'p\nr\n'], [' p', '-q', '+r']), ('empty to one unterminated line', ['', 'only5'], ['+only5', '\\ No newline at end of file']), ('last line changed and unterminated', ['k\nk\nk\nk\nk\nold', 'k\nk\nk\nk\nk\nnew'], [' k', ' k', ' k', ' k', ' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file']), ('trailing blank line', ['a\n\n', 'a\n'], [' a', '-']), ('identical texts', ['s\nt\n', 's\nt\n'], [' s', ' t'])],
}[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 |
|---|---|---|---|
| newline added at end of file | [' a', '-b', '\\ No newline at end of file', '+b'] | [' a', '-b', '\\ No newline at end of file', '+b'] | Passed |
| newline removed at end of file | [' a', ' b'] | [' a', '-b', '+b', '\\ No newline at end of file'] | Failed |
| unchanged last line without newline | ['-x', '+X', ' y', '\\ No newline at end of file'] | ['-x', '+X', ' y', '\\ No newline at end of file'] | Passed |
| both terminated | [' p', '-q', '+r'] | [' p', '-q', '+r'] | Passed |
| empty to one unterminated line | ['+only1', '\\ No newline at end of file'] | ['+only1', '\\ No newline at end of file'] | Passed |
| last line changed and unterminated | [' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file'] | [' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file'] | Passed |
| trailing blank line | [' a', '-'] | [' a', '-'] | Passed |
| identical texts | [' s', ' t'] | [' s', ' t'] | Passed |
SHA-256 / 953aee2c7d0dde918d69cacfc9a3969b787a5643119d3f14cbfcd9c0efbe1a32
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(old, new):
def toks(s):
parts = s.split('\n')
res = [[p, True] for p in parts[:-1]]
if parts[-1] != '':
res.append([parts[-1], False])
return res
def same(x, y):
return x == y
A, B = toks(old), toks(new)
n, m = len(A), len(B)
T = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
T[i][j] = T[i + 1][j + 1] + 1 if same(A[i], B[j]) else max(T[i + 1][j], T[i][j + 1])
ops = []
i = j = 0
while i < n or j < m:
if i < n and j < m and same(A[i], B[j]):
ops.append((' ', A[i])); i += 1; j += 1
elif i < n and (j >= m or T[i + 1][j] >= T[i][j + 1]):
ops.append(('-', A[i])); i += 1
else:
ops.append(('+', B[j])); j += 1
out = []
for tag, (text, nl) in ops:
out.append(tag + text)
if not nl:
out.append('\\ No newline at end of file')
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('newline added at end of file', ['a\nb', 'a\nb\n'], [' a', '-b', '\\ No newline at end of file', '+b']), ('newline removed at end of file', ['a\nb\n', 'a\nb'], [' a', '-b', '+b', '\\ No newline at end of file']), ('unchanged last line without newline', ['x\ny', 'X\ny'], ['-x', '+X', ' y', '\\ No newline at end of file']), ('both terminated', ['p\nq\n', 'p\nr\n'], [' p', '-q', '+r']), ('empty to one unterminated line', ['', 'only1'], ['+only1', '\\ No newline at end of file']), ('last line changed and unterminated', ['k\nold', 'k\nnew'], [' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file']), ('trailing blank line', ['a\n\n', 'a\n'], [' a', '-']), ('identical texts', ['s\nt\n', 's\nt\n'], [' s', ' t'])],
2: [('newline added at end of file', ['a\nb', 'a\nb\n'], [' a', '-b', '\\ No newline at end of file', '+b']), ('newline removed at end of file', ['a\nb\n', 'a\nb'], [' a', '-b', '+b', '\\ No newline at end of file']), ('unchanged last line without newline', ['x\ny', 'X\ny'], ['-x', '+X', ' y', '\\ No newline at end of file']), ('both terminated', ['p\nq\n', 'p\nr\n'], [' p', '-q', '+r']), ('empty to one unterminated line', ['', 'only2'], ['+only2', '\\ No newline at end of file']), ('last line changed and unterminated', ['k\nk\nold', 'k\nk\nnew'], [' k', ' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file']), ('trailing blank line', ['a\n\n', 'a\n'], [' a', '-']), ('identical texts', ['s\nt\n', 's\nt\n'], [' s', ' t'])],
3: [('newline added at end of file', ['a\nb', 'a\nb\n'], [' a', '-b', '\\ No newline at end of file', '+b']), ('newline removed at end of file', ['a\nb\n', 'a\nb'], [' a', '-b', '+b', '\\ No newline at end of file']), ('unchanged last line without newline', ['x\ny', 'X\ny'], ['-x', '+X', ' y', '\\ No newline at end of file']), ('both terminated', ['p\nq\n', 'p\nr\n'], [' p', '-q', '+r']), ('empty to one unterminated line', ['', 'only3'], ['+only3', '\\ No newline at end of file']), ('last line changed and unterminated', ['k\nk\nk\nold', 'k\nk\nk\nnew'], [' k', ' k', ' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file']), ('trailing blank line', ['a\n\n', 'a\n'], [' a', '-']), ('identical texts', ['s\nt\n', 's\nt\n'], [' s', ' t'])],
4: [('newline added at end of file', ['a\nb', 'a\nb\n'], [' a', '-b', '\\ No newline at end of file', '+b']), ('newline removed at end of file', ['a\nb\n', 'a\nb'], [' a', '-b', '+b', '\\ No newline at end of file']), ('unchanged last line without newline', ['x\ny', 'X\ny'], ['-x', '+X', ' y', '\\ No newline at end of file']), ('both terminated', ['p\nq\n', 'p\nr\n'], [' p', '-q', '+r']), ('empty to one unterminated line', ['', 'only4'], ['+only4', '\\ No newline at end of file']), ('last line changed and unterminated', ['k\nk\nk\nk\nold', 'k\nk\nk\nk\nnew'], [' k', ' k', ' k', ' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file']), ('trailing blank line', ['a\n\n', 'a\n'], [' a', '-']), ('identical texts', ['s\nt\n', 's\nt\n'], [' s', ' t'])],
5: [('newline added at end of file', ['a\nb', 'a\nb\n'], [' a', '-b', '\\ No newline at end of file', '+b']), ('newline removed at end of file', ['a\nb\n', 'a\nb'], [' a', '-b', '+b', '\\ No newline at end of file']), ('unchanged last line without newline', ['x\ny', 'X\ny'], ['-x', '+X', ' y', '\\ No newline at end of file']), ('both terminated', ['p\nq\n', 'p\nr\n'], [' p', '-q', '+r']), ('empty to one unterminated line', ['', 'only5'], ['+only5', '\\ No newline at end of file']), ('last line changed and unterminated', ['k\nk\nk\nk\nk\nold', 'k\nk\nk\nk\nk\nnew'], [' k', ' k', ' k', ' k', ' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file']), ('trailing blank line', ['a\n\n', 'a\n'], [' a', '-']), ('identical texts', ['s\nt\n', 's\nt\n'], [' s', ' t'])],
}[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 |
|---|---|---|---|
| newline added at end of file | [' a', '-b', '\\ No newline at end of file', '+b'] | [' a', '-b', '\\ No newline at end of file', '+b'] | Passed |
| newline removed at end of file | [' a', '-b', '+b', '\\ No newline at end of file'] | [' a', '-b', '+b', '\\ No newline at end of file'] | Passed |
| unchanged last line without newline | ['-x', '+X', ' y', '\\ No newline at end of file'] | ['-x', '+X', ' y', '\\ No newline at end of file'] | Passed |
| both terminated | [' p', '-q', '+r'] | [' p', '-q', '+r'] | Passed |
| empty to one unterminated line | ['+only1', '\\ No newline at end of file'] | ['+only1', '\\ No newline at end of file'] | Passed |
| last line changed and unterminated | [' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file'] | [' k', '-old', '\\ No newline at end of file', '+new', '\\ No newline at end of file'] | Passed |
| trailing blank line | [' a', '-'] | [' a', '-'] | Passed |
| identical texts | [' s', ' t'] | [' s', ' t'] | Passed |
SHA-256 / 3a8d8a863b6d5480c8e26c56d9572c3e18ed3e622d909e232de99c8798f60f72
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:07.184148+00:00.
Case digest / 10cde0ef0d3618e7379cc5492ffd5210f52a286dd34b74ddad30636e5bfbdb9c