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

LCS edit script: a match extends the wrong neighbouring cell · case 01

Diffs contain more insertions and deletions than necessary around repeated lines.

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

ROOT CAUSE

A matching pair adds one to the cell below instead of the diagonal cell.

VERIFIED REPAIR

For equal lines extend the diagonal suffix: T[i][j] = T[i+1][j+1] + 1.

Unsuccessful approach: Adding one to the larger neighbour double counts a line that is already matched in that neighbour.

Case contract

Given old and new line lists, fill a suffix LCS table L[i][j] for a[i:], b[j:], then walk from the start: equal lines are kept, otherwise delete when L[i+1][j] >= L[i][j+1] and insert otherwise; flush remaining old lines as deletions and new lines as insertions. Return [tag, line] ops with tags " ", "-", "+".

Why this case matters

Line diffs are built from a longest-common-subsequence table; the walk decides how edits are ordered and presented.

1 / The failure

Exit 1

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

N = 1
observations = []
def solve(a, b):
    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):
            if a[i] == b[j]:
                T[i][j] = T[i + 1][j] + 1
            else:
                T[i][j] = max(T[i + 1][j], T[i][j + 1])
    out = []
    i = j = 0
    while i < n and j < m:
        if a[i] == b[j]:
            out.append([' ', a[i]])
            i += 1
            j += 1
        elif T[i + 1][j] >= T[i][j + 1]:
            out.append(['-', a[i]])
            i += 1
        else:
            out.append(['+', b[j]])
            j += 1
    out.extend(['-', x] for x in a[i:])
    out.extend(['+', x] for x in b[j:])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('single replaced line', [['a', 'b', 'c'], ['a', 'x', 'c']], [[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]), ('insertion at the end', [['a', 'b'], ['a', 'b', 'n0']], [[' ', 'a'], [' ', 'b'], ['+', 'n0']]), ('deletion at the end', [['a', 'b', 'c', 't1', 't2'], ['a', 'b', 'c']], [[' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 't1'], ['-', 't2']]), ('tie prefers deletion first', [['p', 'q'], ['q', 'p']], [['-', 'p'], [' ', 'q'], ['+', 'p']]), ('moved block', [['h', 'x', 'y', 'z', 't'], ['h', 'z', 'x', 'y', 't']], [[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]), ('identical sequences', [['same'], ['same']], [[' ', 'same']]), ('first lines differ', [['A', 'b', 'c', 'd'], ['B', 'b', 'c', 'd']], [['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]), ('empty old side', [[], ['k0']], [['+', 'k0']]), ('repeated line after a replaced one', [['r1', 'r1'], ['q', 'r1']], [['-', 'r1'], ['+', 'q'], [' ', 'r1']]), ('lcs longer than greedy', [['a', 'b', 'c', 'x', 'y'], ['x', 'y', 'a', 'b', 'c', 'd']], [['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']])],
    2: [('single replaced line', [['a', 'b', 'c'], ['a', 'x', 'c']], [[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]), ('insertion at the end', [['a', 'b'], ['a', 'b', 'n0', 'n1']], [[' ', 'a'], [' ', 'b'], ['+', 'n0'], ['+', 'n1']]), ('deletion at the end', [['a', 'b', 'c', 'd', 't1', 't2'], ['a', 'b', 'c', 'd']], [[' ', 'a'], [' ', 'b'], [' ', 'c'], [' ', 'd'], ['-', 't1'], ['-', 't2']]), ('tie prefers deletion first', [['p', 'q'], ['q', 'p']], [['-', 'p'], [' ', 'q'], ['+', 'p']]), ('moved block', [['h', 'x', 'y', 'z', 't'], ['h', 'z', 'x', 'y', 't']], [[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]), ('identical sequences', [['same', 'same'], ['same', 'same']], [[' ', 'same'], [' ', 'same']]), ('first lines differ', [['A', 'b', 'c', 'd'], ['B', 'b', 'c', 'd']], [['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]), ('empty old side', [[], ['k0', 'k1']], [['+', 'k0'], ['+', 'k1']]), ('repeated line after a replaced one', [['r2', 'r2'], ['q', 'r2']], [['-', 'r2'], ['+', 'q'], [' ', 'r2']]), ('lcs longer than greedy', [['a', 'b', 'c', 'x', 'y'], ['x', 'y', 'a', 'b', 'c', 'd']], [['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']])],
    3: [('single replaced line', [['a', 'b', 'c'], ['a', 'x', 'c']], [[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]), ('insertion at the end', [['a', 'b'], ['a', 'b', 'n0', 'n1', 'n2']], [[' ', 'a'], [' ', 'b'], ['+', 'n0'], ['+', 'n1'], ['+', 'n2']]), ('deletion at the end', [['a', 'b', 't1', 't2'], ['a', 'b']], [[' ', 'a'], [' ', 'b'], ['-', 't1'], ['-', 't2']]), ('tie prefers deletion first', [['p', 'q'], ['q', 'p']], [['-', 'p'], [' ', 'q'], ['+', 'p']]), ('moved block', [['h', 'x', 'y', 'z', 't'], ['h', 'z', 'x', 'y', 't']], [[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]), ('identical sequences', [['same', 'same', 'same'], ['same', 'same', 'same']], [[' ', 'same'], [' ', 'same'], [' ', 'same']]), ('first lines differ', [['A', 'b', 'c', 'd'], ['B', 'b', 'c', 'd']], [['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]), ('empty old side', [[], ['k0', 'k1', 'k2']], [['+', 'k0'], ['+', 'k1'], ['+', 'k2']]), ('repeated line after a replaced one', [['r3', 'r3'], ['q', 'r3']], [['-', 'r3'], ['+', 'q'], [' ', 'r3']]), ('lcs longer than greedy', [['a', 'b', 'c', 'x', 'y'], ['x', 'y', 'a', 'b', 'c', 'd']], [['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']])],
    4: [('single replaced line', [['a', 'b', 'c'], ['a', 'x', 'c']], [[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]), ('insertion at the end', [['a', 'b'], ['a', 'b', 'n0', 'n1', 'n2', 'n3']], [[' ', 'a'], [' ', 'b'], ['+', 'n0'], ['+', 'n1'], ['+', 'n2'], ['+', 'n3']]), ('deletion at the end', [['a', 'b', 'c', 't1', 't2'], ['a', 'b', 'c']], [[' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 't1'], ['-', 't2']]), ('tie prefers deletion first', [['p', 'q'], ['q', 'p']], [['-', 'p'], [' ', 'q'], ['+', 'p']]), ('moved block', [['h', 'x', 'y', 'z', 't'], ['h', 'z', 'x', 'y', 't']], [[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]), ('identical sequences', [['same', 'same', 'same', 'same'], ['same', 'same', 'same', 'same']], [[' ', 'same'], [' ', 'same'], [' ', 'same'], [' ', 'same']]), ('first lines differ', [['A', 'b', 'c', 'd'], ['B', 'b', 'c', 'd']], [['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]), ('empty old side', [[], ['k0', 'k1', 'k2', 'k3']], [['+', 'k0'], ['+', 'k1'], ['+', 'k2'], ['+', 'k3']]), ('repeated line after a replaced one', [['r4', 'r4'], ['q', 'r4']], [['-', 'r4'], ['+', 'q'], [' ', 'r4']]), ('lcs longer than greedy', [['a', 'b', 'c', 'x', 'y'], ['x', 'y', 'a', 'b', 'c', 'd']], [['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']])],
    5: [('single replaced line', [['a', 'b', 'c'], ['a', 'x', 'c']], [[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]), ('insertion at the end', [['a', 'b'], ['a', 'b', 'n0', 'n1', 'n2', 'n3', 'n4']], [[' ', 'a'], [' ', 'b'], ['+', 'n0'], ['+', 'n1'], ['+', 'n2'], ['+', 'n3'], ['+', 'n4']]), ('deletion at the end', [['a', 'b', 'c', 'd', 't1', 't2'], ['a', 'b', 'c', 'd']], [[' ', 'a'], [' ', 'b'], [' ', 'c'], [' ', 'd'], ['-', 't1'], ['-', 't2']]), ('tie prefers deletion first', [['p', 'q'], ['q', 'p']], [['-', 'p'], [' ', 'q'], ['+', 'p']]), ('moved block', [['h', 'x', 'y', 'z', 't'], ['h', 'z', 'x', 'y', 't']], [[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]), ('identical sequences', [['same', 'same', 'same', 'same', 'same'], ['same', 'same', 'same', 'same', 'same']], [[' ', 'same'], [' ', 'same'], [' ', 'same'], [' ', 'same'], [' ', 'same']]), ('first lines differ', [['A', 'b', 'c', 'd'], ['B', 'b', 'c', 'd']], [['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]), ('empty old side', [[], ['k0', 'k1', 'k2', 'k3', 'k4']], [['+', 'k0'], ['+', 'k1'], ['+', 'k2'], ['+', 'k3'], ['+', 'k4']]), ('repeated line after a replaced one', [['r5', 'r5'], ['q', 'r5']], [['-', 'r5'], ['+', 'q'], [' ', 'r5']]), ('lcs longer than greedy', [['a', 'b', 'c', 'x', 'y'], ['x', 'y', 'a', 'b', 'c', 'd']], [['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']])],
}[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
single replaced line	`[[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]`	`[[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]`	Passed
insertion at the end	`[[' ', 'a'], [' ', 'b'], ['+', 'n0']]`	`[[' ', 'a'], [' ', 'b'], ['+', 'n0']]`	Passed
deletion at the end	`[[' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 't1'], ['-', 't2']]`	`[[' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 't1'], ['-', 't2']]`	Passed
tie prefers deletion first	`[['-', 'p'], [' ', 'q'], ['+', 'p']]`	`[['-', 'p'], [' ', 'q'], ['+', 'p']]`	Passed
moved block	`[[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]`	`[[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]`	Passed
identical sequences	`[[' ', 'same']]`	`[[' ', 'same']]`	Passed
first lines differ	`[['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]`	`[['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]`	Passed
empty old side	`[['+', 'k0']]`	`[['+', 'k0']]`	Passed
repeated line after a replaced one	`[['+', 'q'], [' ', 'r1'], ['-', 'r1']]`	`[['-', 'r1'], ['+', 'q'], [' ', 'r1']]`	Failed
lcs longer than greedy	`[['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']]`	`[['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']]`	Passed

SHA-256 / b444272f80c79d81cc4204fe759af6d89326a476e4871891a9ce33a4168859aa

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(a, b):
    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):
            if a[i] == b[j]:
                T[i][j] = max(T[i + 1][j], T[i][j + 1]) + 1
            else:
                T[i][j] = max(T[i + 1][j], T[i][j + 1])
    out = []
    i = j = 0
    while i < n and j < m:
        if a[i] == b[j]:
            out.append([' ', a[i]])
            i += 1
            j += 1
        elif T[i + 1][j] >= T[i][j + 1]:
            out.append(['-', a[i]])
            i += 1
        else:
            out.append(['+', b[j]])
            j += 1
    out.extend(['-', x] for x in a[i:])
    out.extend(['+', x] for x in b[j:])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('single replaced line', [['a', 'b', 'c'], ['a', 'x', 'c']], [[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]), ('insertion at the end', [['a', 'b'], ['a', 'b', 'n0']], [[' ', 'a'], [' ', 'b'], ['+', 'n0']]), ('deletion at the end', [['a', 'b', 'c', 't1', 't2'], ['a', 'b', 'c']], [[' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 't1'], ['-', 't2']]), ('tie prefers deletion first', [['p', 'q'], ['q', 'p']], [['-', 'p'], [' ', 'q'], ['+', 'p']]), ('moved block', [['h', 'x', 'y', 'z', 't'], ['h', 'z', 'x', 'y', 't']], [[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]), ('identical sequences', [['same'], ['same']], [[' ', 'same']]), ('first lines differ', [['A', 'b', 'c', 'd'], ['B', 'b', 'c', 'd']], [['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]), ('empty old side', [[], ['k0']], [['+', 'k0']]), ('repeated line after a replaced one', [['r1', 'r1'], ['q', 'r1']], [['-', 'r1'], ['+', 'q'], [' ', 'r1']]), ('lcs longer than greedy', [['a', 'b', 'c', 'x', 'y'], ['x', 'y', 'a', 'b', 'c', 'd']], [['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']])],
    2: [('single replaced line', [['a', 'b', 'c'], ['a', 'x', 'c']], [[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]), ('insertion at the end', [['a', 'b'], ['a', 'b', 'n0', 'n1']], [[' ', 'a'], [' ', 'b'], ['+', 'n0'], ['+', 'n1']]), ('deletion at the end', [['a', 'b', 'c', 'd', 't1', 't2'], ['a', 'b', 'c', 'd']], [[' ', 'a'], [' ', 'b'], [' ', 'c'], [' ', 'd'], ['-', 't1'], ['-', 't2']]), ('tie prefers deletion first', [['p', 'q'], ['q', 'p']], [['-', 'p'], [' ', 'q'], ['+', 'p']]), ('moved block', [['h', 'x', 'y', 'z', 't'], ['h', 'z', 'x', 'y', 't']], [[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]), ('identical sequences', [['same', 'same'], ['same', 'same']], [[' ', 'same'], [' ', 'same']]), ('first lines differ', [['A', 'b', 'c', 'd'], ['B', 'b', 'c', 'd']], [['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]), ('empty old side', [[], ['k0', 'k1']], [['+', 'k0'], ['+', 'k1']]), ('repeated line after a replaced one', [['r2', 'r2'], ['q', 'r2']], [['-', 'r2'], ['+', 'q'], [' ', 'r2']]), ('lcs longer than greedy', [['a', 'b', 'c', 'x', 'y'], ['x', 'y', 'a', 'b', 'c', 'd']], [['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']])],
    3: [('single replaced line', [['a', 'b', 'c'], ['a', 'x', 'c']], [[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]), ('insertion at the end', [['a', 'b'], ['a', 'b', 'n0', 'n1', 'n2']], [[' ', 'a'], [' ', 'b'], ['+', 'n0'], ['+', 'n1'], ['+', 'n2']]), ('deletion at the end', [['a', 'b', 't1', 't2'], ['a', 'b']], [[' ', 'a'], [' ', 'b'], ['-', 't1'], ['-', 't2']]), ('tie prefers deletion first', [['p', 'q'], ['q', 'p']], [['-', 'p'], [' ', 'q'], ['+', 'p']]), ('moved block', [['h', 'x', 'y', 'z', 't'], ['h', 'z', 'x', 'y', 't']], [[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]), ('identical sequences', [['same', 'same', 'same'], ['same', 'same', 'same']], [[' ', 'same'], [' ', 'same'], [' ', 'same']]), ('first lines differ', [['A', 'b', 'c', 'd'], ['B', 'b', 'c', 'd']], [['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]), ('empty old side', [[], ['k0', 'k1', 'k2']], [['+', 'k0'], ['+', 'k1'], ['+', 'k2']]), ('repeated line after a replaced one', [['r3', 'r3'], ['q', 'r3']], [['-', 'r3'], ['+', 'q'], [' ', 'r3']]), ('lcs longer than greedy', [['a', 'b', 'c', 'x', 'y'], ['x', 'y', 'a', 'b', 'c', 'd']], [['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']])],
    4: [('single replaced line', [['a', 'b', 'c'], ['a', 'x', 'c']], [[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]), ('insertion at the end', [['a', 'b'], ['a', 'b', 'n0', 'n1', 'n2', 'n3']], [[' ', 'a'], [' ', 'b'], ['+', 'n0'], ['+', 'n1'], ['+', 'n2'], ['+', 'n3']]), ('deletion at the end', [['a', 'b', 'c', 't1', 't2'], ['a', 'b', 'c']], [[' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 't1'], ['-', 't2']]), ('tie prefers deletion first', [['p', 'q'], ['q', 'p']], [['-', 'p'], [' ', 'q'], ['+', 'p']]), ('moved block', [['h', 'x', 'y', 'z', 't'], ['h', 'z', 'x', 'y', 't']], [[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]), ('identical sequences', [['same', 'same', 'same', 'same'], ['same', 'same', 'same', 'same']], [[' ', 'same'], [' ', 'same'], [' ', 'same'], [' ', 'same']]), ('first lines differ', [['A', 'b', 'c', 'd'], ['B', 'b', 'c', 'd']], [['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]), ('empty old side', [[], ['k0', 'k1', 'k2', 'k3']], [['+', 'k0'], ['+', 'k1'], ['+', 'k2'], ['+', 'k3']]), ('repeated line after a replaced one', [['r4', 'r4'], ['q', 'r4']], [['-', 'r4'], ['+', 'q'], [' ', 'r4']]), ('lcs longer than greedy', [['a', 'b', 'c', 'x', 'y'], ['x', 'y', 'a', 'b', 'c', 'd']], [['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']])],
    5: [('single replaced line', [['a', 'b', 'c'], ['a', 'x', 'c']], [[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]), ('insertion at the end', [['a', 'b'], ['a', 'b', 'n0', 'n1', 'n2', 'n3', 'n4']], [[' ', 'a'], [' ', 'b'], ['+', 'n0'], ['+', 'n1'], ['+', 'n2'], ['+', 'n3'], ['+', 'n4']]), ('deletion at the end', [['a', 'b', 'c', 'd', 't1', 't2'], ['a', 'b', 'c', 'd']], [[' ', 'a'], [' ', 'b'], [' ', 'c'], [' ', 'd'], ['-', 't1'], ['-', 't2']]), ('tie prefers deletion first', [['p', 'q'], ['q', 'p']], [['-', 'p'], [' ', 'q'], ['+', 'p']]), ('moved block', [['h', 'x', 'y', 'z', 't'], ['h', 'z', 'x', 'y', 't']], [[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]), ('identical sequences', [['same', 'same', 'same', 'same', 'same'], ['same', 'same', 'same', 'same', 'same']], [[' ', 'same'], [' ', 'same'], [' ', 'same'], [' ', 'same'], [' ', 'same']]), ('first lines differ', [['A', 'b', 'c', 'd'], ['B', 'b', 'c', 'd']], [['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]), ('empty old side', [[], ['k0', 'k1', 'k2', 'k3', 'k4']], [['+', 'k0'], ['+', 'k1'], ['+', 'k2'], ['+', 'k3'], ['+', 'k4']]), ('repeated line after a replaced one', [['r5', 'r5'], ['q', 'r5']], [['-', 'r5'], ['+', 'q'], [' ', 'r5']]), ('lcs longer than greedy', [['a', 'b', 'c', 'x', 'y'], ['x', 'y', 'a', 'b', 'c', 'd']], [['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']])],
}[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
single replaced line	`[[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]`	`[[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]`	Passed
insertion at the end	`[[' ', 'a'], [' ', 'b'], ['+', 'n0']]`	`[[' ', 'a'], [' ', 'b'], ['+', 'n0']]`	Passed
deletion at the end	`[[' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 't1'], ['-', 't2']]`	`[[' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 't1'], ['-', 't2']]`	Passed
tie prefers deletion first	`[['-', 'p'], [' ', 'q'], ['+', 'p']]`	`[['-', 'p'], [' ', 'q'], ['+', 'p']]`	Passed
moved block	`[[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]`	`[[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]`	Passed
identical sequences	`[[' ', 'same']]`	`[[' ', 'same']]`	Passed
first lines differ	`[['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]`	`[['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]`	Passed
empty old side	`[['+', 'k0']]`	`[['+', 'k0']]`	Passed
repeated line after a replaced one	`[['+', 'q'], [' ', 'r1'], ['-', 'r1']]`	`[['-', 'r1'], ['+', 'q'], [' ', 'r1']]`	Failed
lcs longer than greedy	`[['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']]`	`[['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']]`	Passed

SHA-256 / 14b8b8c2ef301cbccbec3247a2ee85d9b9b4d579b9762f9f0c40050e3c605728

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(a, b):
    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):
            if a[i] == b[j]:
                T[i][j] = T[i + 1][j + 1] + 1
            else:
                T[i][j] = max(T[i + 1][j], T[i][j + 1])
    out = []
    i = j = 0
    while i < n and j < m:
        if a[i] == b[j]:
            out.append([' ', a[i]])
            i += 1
            j += 1
        elif T[i + 1][j] >= T[i][j + 1]:
            out.append(['-', a[i]])
            i += 1
        else:
            out.append(['+', b[j]])
            j += 1
    out.extend(['-', x] for x in a[i:])
    out.extend(['+', x] for x in b[j:])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('single replaced line', [['a', 'b', 'c'], ['a', 'x', 'c']], [[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]), ('insertion at the end', [['a', 'b'], ['a', 'b', 'n0']], [[' ', 'a'], [' ', 'b'], ['+', 'n0']]), ('deletion at the end', [['a', 'b', 'c', 't1', 't2'], ['a', 'b', 'c']], [[' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 't1'], ['-', 't2']]), ('tie prefers deletion first', [['p', 'q'], ['q', 'p']], [['-', 'p'], [' ', 'q'], ['+', 'p']]), ('moved block', [['h', 'x', 'y', 'z', 't'], ['h', 'z', 'x', 'y', 't']], [[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]), ('identical sequences', [['same'], ['same']], [[' ', 'same']]), ('first lines differ', [['A', 'b', 'c', 'd'], ['B', 'b', 'c', 'd']], [['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]), ('empty old side', [[], ['k0']], [['+', 'k0']]), ('repeated line after a replaced one', [['r1', 'r1'], ['q', 'r1']], [['-', 'r1'], ['+', 'q'], [' ', 'r1']]), ('lcs longer than greedy', [['a', 'b', 'c', 'x', 'y'], ['x', 'y', 'a', 'b', 'c', 'd']], [['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']])],
    2: [('single replaced line', [['a', 'b', 'c'], ['a', 'x', 'c']], [[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]), ('insertion at the end', [['a', 'b'], ['a', 'b', 'n0', 'n1']], [[' ', 'a'], [' ', 'b'], ['+', 'n0'], ['+', 'n1']]), ('deletion at the end', [['a', 'b', 'c', 'd', 't1', 't2'], ['a', 'b', 'c', 'd']], [[' ', 'a'], [' ', 'b'], [' ', 'c'], [' ', 'd'], ['-', 't1'], ['-', 't2']]), ('tie prefers deletion first', [['p', 'q'], ['q', 'p']], [['-', 'p'], [' ', 'q'], ['+', 'p']]), ('moved block', [['h', 'x', 'y', 'z', 't'], ['h', 'z', 'x', 'y', 't']], [[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]), ('identical sequences', [['same', 'same'], ['same', 'same']], [[' ', 'same'], [' ', 'same']]), ('first lines differ', [['A', 'b', 'c', 'd'], ['B', 'b', 'c', 'd']], [['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]), ('empty old side', [[], ['k0', 'k1']], [['+', 'k0'], ['+', 'k1']]), ('repeated line after a replaced one', [['r2', 'r2'], ['q', 'r2']], [['-', 'r2'], ['+', 'q'], [' ', 'r2']]), ('lcs longer than greedy', [['a', 'b', 'c', 'x', 'y'], ['x', 'y', 'a', 'b', 'c', 'd']], [['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']])],
    3: [('single replaced line', [['a', 'b', 'c'], ['a', 'x', 'c']], [[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]), ('insertion at the end', [['a', 'b'], ['a', 'b', 'n0', 'n1', 'n2']], [[' ', 'a'], [' ', 'b'], ['+', 'n0'], ['+', 'n1'], ['+', 'n2']]), ('deletion at the end', [['a', 'b', 't1', 't2'], ['a', 'b']], [[' ', 'a'], [' ', 'b'], ['-', 't1'], ['-', 't2']]), ('tie prefers deletion first', [['p', 'q'], ['q', 'p']], [['-', 'p'], [' ', 'q'], ['+', 'p']]), ('moved block', [['h', 'x', 'y', 'z', 't'], ['h', 'z', 'x', 'y', 't']], [[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]), ('identical sequences', [['same', 'same', 'same'], ['same', 'same', 'same']], [[' ', 'same'], [' ', 'same'], [' ', 'same']]), ('first lines differ', [['A', 'b', 'c', 'd'], ['B', 'b', 'c', 'd']], [['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]), ('empty old side', [[], ['k0', 'k1', 'k2']], [['+', 'k0'], ['+', 'k1'], ['+', 'k2']]), ('repeated line after a replaced one', [['r3', 'r3'], ['q', 'r3']], [['-', 'r3'], ['+', 'q'], [' ', 'r3']]), ('lcs longer than greedy', [['a', 'b', 'c', 'x', 'y'], ['x', 'y', 'a', 'b', 'c', 'd']], [['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']])],
    4: [('single replaced line', [['a', 'b', 'c'], ['a', 'x', 'c']], [[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]), ('insertion at the end', [['a', 'b'], ['a', 'b', 'n0', 'n1', 'n2', 'n3']], [[' ', 'a'], [' ', 'b'], ['+', 'n0'], ['+', 'n1'], ['+', 'n2'], ['+', 'n3']]), ('deletion at the end', [['a', 'b', 'c', 't1', 't2'], ['a', 'b', 'c']], [[' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 't1'], ['-', 't2']]), ('tie prefers deletion first', [['p', 'q'], ['q', 'p']], [['-', 'p'], [' ', 'q'], ['+', 'p']]), ('moved block', [['h', 'x', 'y', 'z', 't'], ['h', 'z', 'x', 'y', 't']], [[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]), ('identical sequences', [['same', 'same', 'same', 'same'], ['same', 'same', 'same', 'same']], [[' ', 'same'], [' ', 'same'], [' ', 'same'], [' ', 'same']]), ('first lines differ', [['A', 'b', 'c', 'd'], ['B', 'b', 'c', 'd']], [['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]), ('empty old side', [[], ['k0', 'k1', 'k2', 'k3']], [['+', 'k0'], ['+', 'k1'], ['+', 'k2'], ['+', 'k3']]), ('repeated line after a replaced one', [['r4', 'r4'], ['q', 'r4']], [['-', 'r4'], ['+', 'q'], [' ', 'r4']]), ('lcs longer than greedy', [['a', 'b', 'c', 'x', 'y'], ['x', 'y', 'a', 'b', 'c', 'd']], [['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']])],
    5: [('single replaced line', [['a', 'b', 'c'], ['a', 'x', 'c']], [[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]), ('insertion at the end', [['a', 'b'], ['a', 'b', 'n0', 'n1', 'n2', 'n3', 'n4']], [[' ', 'a'], [' ', 'b'], ['+', 'n0'], ['+', 'n1'], ['+', 'n2'], ['+', 'n3'], ['+', 'n4']]), ('deletion at the end', [['a', 'b', 'c', 'd', 't1', 't2'], ['a', 'b', 'c', 'd']], [[' ', 'a'], [' ', 'b'], [' ', 'c'], [' ', 'd'], ['-', 't1'], ['-', 't2']]), ('tie prefers deletion first', [['p', 'q'], ['q', 'p']], [['-', 'p'], [' ', 'q'], ['+', 'p']]), ('moved block', [['h', 'x', 'y', 'z', 't'], ['h', 'z', 'x', 'y', 't']], [[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]), ('identical sequences', [['same', 'same', 'same', 'same', 'same'], ['same', 'same', 'same', 'same', 'same']], [[' ', 'same'], [' ', 'same'], [' ', 'same'], [' ', 'same'], [' ', 'same']]), ('first lines differ', [['A', 'b', 'c', 'd'], ['B', 'b', 'c', 'd']], [['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]), ('empty old side', [[], ['k0', 'k1', 'k2', 'k3', 'k4']], [['+', 'k0'], ['+', 'k1'], ['+', 'k2'], ['+', 'k3'], ['+', 'k4']]), ('repeated line after a replaced one', [['r5', 'r5'], ['q', 'r5']], [['-', 'r5'], ['+', 'q'], [' ', 'r5']]), ('lcs longer than greedy', [['a', 'b', 'c', 'x', 'y'], ['x', 'y', 'a', 'b', 'c', 'd']], [['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']])],
}[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
single replaced line	`[[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]`	`[[' ', 'a'], ['-', 'b'], ['+', 'x'], [' ', 'c']]`	Passed
insertion at the end	`[[' ', 'a'], [' ', 'b'], ['+', 'n0']]`	`[[' ', 'a'], [' ', 'b'], ['+', 'n0']]`	Passed
deletion at the end	`[[' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 't1'], ['-', 't2']]`	`[[' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 't1'], ['-', 't2']]`	Passed
tie prefers deletion first	`[['-', 'p'], [' ', 'q'], ['+', 'p']]`	`[['-', 'p'], [' ', 'q'], ['+', 'p']]`	Passed
moved block	`[[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]`	`[[' ', 'h'], ['+', 'z'], [' ', 'x'], [' ', 'y'], ['-', 'z'], [' ', 't']]`	Passed
identical sequences	`[[' ', 'same']]`	`[[' ', 'same']]`	Passed
first lines differ	`[['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]`	`[['-', 'A'], ['+', 'B'], [' ', 'b'], [' ', 'c'], [' ', 'd']]`	Passed
empty old side	`[['+', 'k0']]`	`[['+', 'k0']]`	Passed
repeated line after a replaced one	`[['-', 'r1'], ['+', 'q'], [' ', 'r1']]`	`[['-', 'r1'], ['+', 'q'], [' ', 'r1']]`	Passed
lcs longer than greedy	`[['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']]`	`[['+', 'x'], ['+', 'y'], [' ', 'a'], [' ', 'b'], [' ', 'c'], ['-', 'x'], ['-', 'y'], ['+', 'd']]`	Passed

SHA-256 / 6d51e625680a20e00a1b6fbdacab4b2ea9ab2102a7becd87a6c9b5169b5a7d22

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

Case digest / fb275ebf489c4a6aee9c3a8ae18bf0811ad258c32274a75e136b332912c58335