FAILURE MAP
← Case archive

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

Myers greedy edit distance: only one equal element is followed on each diagonal · case 01

Runs of equal lines count as edits and the distance is overstated.

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

ROOT CAUSE

The snake advances at most one step instead of following all equal elements.

VERIFIED REPAIR

Follow the snake while both sequences continue with equal elements.

Unsuccessful approach: Stopping the snake before the last element of a still counts a trailing equal line as an edit.

Case contract

Compute the minimum number of line insertions plus deletions between a and b using the greedy furthest-reaching diagonal method: for d = 0..min(max_d, n+m), for k = -d..d step 2 choose the start x from diagonal k+1 when k == -d or (k != d and V[k-1] < V[k+1]), else V[k-1]+1; follow the snake of equal elements; return d once x >= n and y >= m. Return None when the distance exceeds max_d.

Why this case matters

Diff engines use Myers' O(ND) algorithm with a cap on D to bound work on very different files.

1 / The failure

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

N = 1
observations = []
def solve(a, b, max_d):
    n, m = len(a), len(b)
    off = n + m + 1
    v = [0] * (2 * off + 2)
    for d in range(0, min(max_d, n + m) + 1):
        for k in range(-d, d + 1, 2):
            if k == -d or (k != d and v[off + k - 1] < v[off + k + 1]):
                x = v[off + k + 1]
            else:
                x = v[off + k - 1] + 1
            y = x - k
            if x < n and y < m and a[x] == b[y]:
                x += 1
                y += 1
            v[off + k] = x
            if x >= n and y >= m:
                return d
    return None
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x'], ['x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 4], None), ('one side empty', [[], ['q'], 2], 1), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g'], 9], 2), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],
    2: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x'], ['x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 3], None), ('one side empty', [[], ['q', 'q'], 3], 2), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g', 'h'], 9], 1), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],
    3: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x', 'x'], ['x', 'x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 4], None), ('one side empty', [[], ['q', 'q', 'q'], 4], 3), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g'], 9], 2), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],
    4: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x', 'x', 'x'], ['x', 'x', 'x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 3], None), ('one side empty', [[], ['q', 'q', 'q', 'q'], 5], 4), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g', 'h'], 9], 1), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],
    5: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x', 'x', 'x', 'x'], ['x', 'x', 'x', 'x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 4], None), ('one side empty', [[], ['q', 'q', 'q', 'q', 'q'], 6], 5), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g'], 9], 2), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],
}[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 fixtureActualExpectedOutcome
classic example75Failed
identical00Passed
all different44Passed
cap equal to distanceNone2Failed
cap below distanceNoneNonePassed
one side empty11Passed
insert in the middle31Failed
long snakes82Failed
distance exactly the total length55Passed
single edits scattered73Failed

SHA-256 / 54b7b6043473a0d5fe0f09d2c975bed4576dcf0d742b46ccaae9ae7f8ab770ba

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(a, b, max_d):
    n, m = len(a), len(b)
    off = n + m + 1
    v = [0] * (2 * off + 2)
    for d in range(0, min(max_d, n + m) + 1):
        for k in range(-d, d + 1, 2):
            if k == -d or (k != d and v[off + k - 1] < v[off + k + 1]):
                x = v[off + k + 1]
            else:
                x = v[off + k - 1] + 1
            y = x - k
            while x < n and y < m and a[x] == b[y] and x - k == y and x < n - 1:
                x += 1
                y += 1
            v[off + k] = x
            if x >= n and y >= m:
                return d
    return None
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x'], ['x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 4], None), ('one side empty', [[], ['q'], 2], 1), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g'], 9], 2), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],
    2: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x'], ['x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 3], None), ('one side empty', [[], ['q', 'q'], 3], 2), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g', 'h'], 9], 1), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],
    3: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x', 'x'], ['x', 'x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 4], None), ('one side empty', [[], ['q', 'q', 'q'], 4], 3), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g'], 9], 2), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],
    4: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x', 'x', 'x'], ['x', 'x', 'x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 3], None), ('one side empty', [[], ['q', 'q', 'q', 'q'], 5], 4), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g', 'h'], 9], 1), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],
    5: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x', 'x', 'x', 'x'], ['x', 'x', 'x', 'x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 4], None), ('one side empty', [[], ['q', 'q', 'q', 'q', 'q'], 6], 5), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g'], 9], 2), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],
}[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 fixtureActualExpectedOutcome
classic example75Failed
identical20Failed
all different44Passed
cap equal to distance22Passed
cap below distanceNoneNonePassed
one side empty11Passed
insert in the middle31Failed
long snakes22Passed
distance exactly the total length55Passed
single edits scattered53Failed

SHA-256 / a7741d2ff5dbb1a1af2892af8b73b0b0c3b23ed4f7e4fc924b175900e42c88fe

3 / The verified repair

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

N = 1
observations = []
def solve(a, b, max_d):
    n, m = len(a), len(b)
    off = n + m + 1
    v = [0] * (2 * off + 2)
    for d in range(0, min(max_d, n + m) + 1):
        for k in range(-d, d + 1, 2):
            if k == -d or (k != d and v[off + k - 1] < v[off + k + 1]):
                x = v[off + k + 1]
            else:
                x = v[off + k - 1] + 1
            y = x - k
            while x < n and y < m and a[x] == b[y]:
                x += 1
                y += 1
            v[off + k] = x
            if x >= n and y >= m:
                return d
    return None
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x'], ['x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 4], None), ('one side empty', [[], ['q'], 2], 1), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g'], 9], 2), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],
    2: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x'], ['x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 3], None), ('one side empty', [[], ['q', 'q'], 3], 2), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g', 'h'], 9], 1), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],
    3: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x', 'x'], ['x', 'x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 4], None), ('one side empty', [[], ['q', 'q', 'q'], 4], 3), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g'], 9], 2), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],
    4: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x', 'x', 'x'], ['x', 'x', 'x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 3], None), ('one side empty', [[], ['q', 'q', 'q', 'q'], 5], 4), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g', 'h'], 9], 1), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],
    5: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x', 'x', 'x', 'x'], ['x', 'x', 'x', 'x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 4], None), ('one side empty', [[], ['q', 'q', 'q', 'q', 'q'], 6], 5), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g'], 9], 2), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],
}[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 fixtureActualExpectedOutcome
classic example55Passed
identical00Passed
all different44Passed
cap equal to distance22Passed
cap below distanceNoneNonePassed
one side empty11Passed
insert in the middle11Passed
long snakes22Passed
distance exactly the total length55Passed
single edits scattered33Passed

SHA-256 / 8bad4b44c7b60425a70c4a5ba911234e10e344687ab380b3a903f77cb79e203a

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

Case digest / 6d7c1c16b88056464c2c07772a10cc20339397b43a7e7567e308d3ba4002fda3