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

Character diff cleanup merge: empty entries survive cleanup · case 01

Normalized diffs contain empty equalities that split merges and render as nothing.

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

ROOT CAUSE

Entries with empty text are not removed before merging.

VERIFIED REPAIR

Drop every entry whose text is empty before merging.

Unsuccessful approach: Keeping empty equalities splits one run of edits into two, so their deletion and insertion are never grouped.

Case contract

Normalize a character diff of [op, text] (op -1 delete, 0 equal, 1 insert): drop empty texts, merge adjacent equalities, collect each run of edits into one deletion and one insertion (deletion first), move their common prefix into the preceding equality (creating one at the start if needed) and their common suffix into the following equality (appending one at the end if needed).

Why this case matters

Character-level diff engines normalize raw edit scripts so that the same change always renders the same way.

1 / The failure

Exit 1

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

N = 1
observations = []
def solve(diffs):
    res = []
    diffs = [list(d) for d in diffs]
    i = 0
    while i < len(diffs):
        if diffs[i][0] == 0:
            if res and res[-1][0] == 0:
                res[-1][1] += diffs[i][1]
            else:
                res.append([0, diffs[i][1]])
            i += 1
            continue
        dl = ins = ''
        while i < len(diffs) and diffs[i][0] != 0:
            if diffs[i][0] == -1:
                dl += diffs[i][1]
            else:
                ins += diffs[i][1]
            i += 1
        suffix = ''
        if dl and ins:
            p = 0
            while p < min(len(dl), len(ins)) and dl[p] == ins[p]:
                p += 1
            if p:
                if res and res[-1][0] == 0:
                    res[-1][1] += dl[:p]
                else:
                    res.append([0, dl[:p]])
                dl, ins = dl[p:], ins[p:]
            s = 0
            while s < min(len(dl), len(ins)) and dl[-1 - s] == ins[-1 - s]:
                s += 1
            suffix = dl[len(dl) - s:]
            dl, ins = dl[:len(dl) - s], ins[:len(ins) - s]
        if dl:
            res.append([-1, dl])
        if ins:
            res.append([1, ins])
        if suffix:
            if i < len(diffs) and diffs[i][0] == 0:
                diffs[i] = [0, suffix + diffs[i][1]]
            else:
                res.append([0, suffix])
    return res
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz1'], [1, 'uvz1']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z1']]), ('prefix at the start of the text', [[[-1, 'prea'], [1, 'preb'], [0, 'tail']]], [[0, 'pre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab1'], [0, ''], [1, 'ac1']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '1']])],
    2: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz2'], [1, 'uvz2']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z2']]), ('prefix at the start of the text', [[[-1, 'preprea'], [1, 'prepreb'], [0, 'tail']]], [[0, 'prepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab2'], [0, ''], [1, 'ac2']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '2']])],
    3: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz3'], [1, 'uvz3']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z3']]), ('prefix at the start of the text', [[[-1, 'prepreprea'], [1, 'preprepreb'], [0, 'tail']]], [[0, 'preprepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab3'], [0, ''], [1, 'ac3']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '3']])],
    4: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz4'], [1, 'uvz4']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z4']]), ('prefix at the start of the text', [[[-1, 'preprepreprea'], [1, 'prepreprepreb'], [0, 'tail']]], [[0, 'prepreprepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab4'], [0, ''], [1, 'ac4']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '4']])],
    5: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz5'], [1, 'uvz5']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z5']]), ('prefix at the start of the text', [[[-1, 'prepreprepreprea'], [1, 'preprepreprepreb'], [0, 'tail']]], [[0, 'preprepreprepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab5'], [0, ''], [1, 'ac5']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '5']])],
}[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
adjacent equalities merge	`[[0, 'abcd']]`	`[[0, 'abcd']]`	Passed
empty entries are dropped	`[[0, 'a'], [1, 'b'], [0, '']]`	`[[0, 'a'], [1, 'b']]`	Failed
common prefix moves into the previous equality	`[[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]`	`[[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]`	Passed
common suffix moves into the next equality	`[[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]`	`[[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]`	Passed
no common affix	`[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]`	`[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]`	Passed
interleaved edits are grouped deletion first	`[[-1, 'DE'], [1, 'IJ']]`	`[[-1, 'DE'], [1, 'IJ']]`	Passed
suffix at the end of the text	`[[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z1']]`	`[[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z1']]`	Passed
prefix at the start of the text	`[[0, 'pre'], [-1, 'a'], [1, 'b'], [0, 'tail']]`	`[[0, 'pre'], [-1, 'a'], [1, 'b'], [0, 'tail']]`	Passed
insertion only	`[[0, 'a'], [1, 'b'], [0, 'c']]`	`[[0, 'a'], [1, 'b'], [0, 'c']]`	Passed
empty equality between edits	`[[0, 'k'], [-1, 'ab1'], [0, ''], [1, 'ac1']]`	`[[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '1']]`	Failed

SHA-256 / d66e9587885b3c9b68d861673fb0b6e43ff1e6a26e270c0292d59de707cfbbe0

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(diffs):
    res = []
    diffs = [list(d) for d in diffs if d[1] != '' or d[0] == 0]
    i = 0
    while i < len(diffs):
        if diffs[i][0] == 0:
            if res and res[-1][0] == 0:
                res[-1][1] += diffs[i][1]
            else:
                res.append([0, diffs[i][1]])
            i += 1
            continue
        dl = ins = ''
        while i < len(diffs) and diffs[i][0] != 0:
            if diffs[i][0] == -1:
                dl += diffs[i][1]
            else:
                ins += diffs[i][1]
            i += 1
        suffix = ''
        if dl and ins:
            p = 0
            while p < min(len(dl), len(ins)) and dl[p] == ins[p]:
                p += 1
            if p:
                if res and res[-1][0] == 0:
                    res[-1][1] += dl[:p]
                else:
                    res.append([0, dl[:p]])
                dl, ins = dl[p:], ins[p:]
            s = 0
            while s < min(len(dl), len(ins)) and dl[-1 - s] == ins[-1 - s]:
                s += 1
            suffix = dl[len(dl) - s:]
            dl, ins = dl[:len(dl) - s], ins[:len(ins) - s]
        if dl:
            res.append([-1, dl])
        if ins:
            res.append([1, ins])
        if suffix:
            if i < len(diffs) and diffs[i][0] == 0:
                diffs[i] = [0, suffix + diffs[i][1]]
            else:
                res.append([0, suffix])
    return res
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz1'], [1, 'uvz1']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z1']]), ('prefix at the start of the text', [[[-1, 'prea'], [1, 'preb'], [0, 'tail']]], [[0, 'pre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab1'], [0, ''], [1, 'ac1']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '1']])],
    2: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz2'], [1, 'uvz2']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z2']]), ('prefix at the start of the text', [[[-1, 'preprea'], [1, 'prepreb'], [0, 'tail']]], [[0, 'prepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab2'], [0, ''], [1, 'ac2']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '2']])],
    3: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz3'], [1, 'uvz3']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z3']]), ('prefix at the start of the text', [[[-1, 'prepreprea'], [1, 'preprepreb'], [0, 'tail']]], [[0, 'preprepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab3'], [0, ''], [1, 'ac3']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '3']])],
    4: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz4'], [1, 'uvz4']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z4']]), ('prefix at the start of the text', [[[-1, 'preprepreprea'], [1, 'prepreprepreb'], [0, 'tail']]], [[0, 'prepreprepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab4'], [0, ''], [1, 'ac4']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '4']])],
    5: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz5'], [1, 'uvz5']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z5']]), ('prefix at the start of the text', [[[-1, 'prepreprepreprea'], [1, 'preprepreprepreb'], [0, 'tail']]], [[0, 'preprepreprepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab5'], [0, ''], [1, 'ac5']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '5']])],
}[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
adjacent equalities merge	`[[0, 'abcd']]`	`[[0, 'abcd']]`	Passed
empty entries are dropped	`[[0, 'a'], [1, 'b'], [0, '']]`	`[[0, 'a'], [1, 'b']]`	Failed
common prefix moves into the previous equality	`[[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]`	`[[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]`	Passed
common suffix moves into the next equality	`[[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]`	`[[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]`	Passed
no common affix	`[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]`	`[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]`	Passed
interleaved edits are grouped deletion first	`[[-1, 'DE'], [1, 'IJ']]`	`[[-1, 'DE'], [1, 'IJ']]`	Passed
suffix at the end of the text	`[[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z1']]`	`[[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z1']]`	Passed
prefix at the start of the text	`[[0, 'pre'], [-1, 'a'], [1, 'b'], [0, 'tail']]`	`[[0, 'pre'], [-1, 'a'], [1, 'b'], [0, 'tail']]`	Passed
insertion only	`[[0, 'a'], [1, 'b'], [0, 'c']]`	`[[0, 'a'], [1, 'b'], [0, 'c']]`	Passed
empty equality between edits	`[[0, 'k'], [-1, 'ab1'], [0, ''], [1, 'ac1']]`	`[[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '1']]`	Failed

SHA-256 / 55882a7322cbb985b8bf58f7ac079f3e9934cf0f2833f8b2944db9accdc37b0b

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(diffs):
    res = []
    diffs = [list(d) for d in diffs if d[1] != '']
    i = 0
    while i < len(diffs):
        if diffs[i][0] == 0:
            if res and res[-1][0] == 0:
                res[-1][1] += diffs[i][1]
            else:
                res.append([0, diffs[i][1]])
            i += 1
            continue
        dl = ins = ''
        while i < len(diffs) and diffs[i][0] != 0:
            if diffs[i][0] == -1:
                dl += diffs[i][1]
            else:
                ins += diffs[i][1]
            i += 1
        suffix = ''
        if dl and ins:
            p = 0
            while p < min(len(dl), len(ins)) and dl[p] == ins[p]:
                p += 1
            if p:
                if res and res[-1][0] == 0:
                    res[-1][1] += dl[:p]
                else:
                    res.append([0, dl[:p]])
                dl, ins = dl[p:], ins[p:]
            s = 0
            while s < min(len(dl), len(ins)) and dl[-1 - s] == ins[-1 - s]:
                s += 1
            suffix = dl[len(dl) - s:]
            dl, ins = dl[:len(dl) - s], ins[:len(ins) - s]
        if dl:
            res.append([-1, dl])
        if ins:
            res.append([1, ins])
        if suffix:
            if i < len(diffs) and diffs[i][0] == 0:
                diffs[i] = [0, suffix + diffs[i][1]]
            else:
                res.append([0, suffix])
    return res
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz1'], [1, 'uvz1']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z1']]), ('prefix at the start of the text', [[[-1, 'prea'], [1, 'preb'], [0, 'tail']]], [[0, 'pre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab1'], [0, ''], [1, 'ac1']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '1']])],
    2: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz2'], [1, 'uvz2']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z2']]), ('prefix at the start of the text', [[[-1, 'preprea'], [1, 'prepreb'], [0, 'tail']]], [[0, 'prepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab2'], [0, ''], [1, 'ac2']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '2']])],
    3: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz3'], [1, 'uvz3']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z3']]), ('prefix at the start of the text', [[[-1, 'prepreprea'], [1, 'preprepreb'], [0, 'tail']]], [[0, 'preprepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab3'], [0, ''], [1, 'ac3']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '3']])],
    4: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz4'], [1, 'uvz4']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z4']]), ('prefix at the start of the text', [[[-1, 'preprepreprea'], [1, 'prepreprepreb'], [0, 'tail']]], [[0, 'prepreprepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab4'], [0, ''], [1, 'ac4']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '4']])],
    5: [('adjacent equalities merge', [[[0, 'ab'], [0, 'cd']]], [[0, 'abcd']]), ('empty entries are dropped', [[[0, 'a'], [-1, ''], [1, 'b'], [0, '']]], [[0, 'a'], [1, 'b']]), ('common prefix moves into the previous equality', [[[0, 'x'], [-1, 'abc'], [1, 'abd'], [0, 'y']]], [[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]), ('common suffix moves into the next equality', [[[0, 'p'], [-1, 'kz'], [1, 'mz'], [0, 'q']]], [[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]), ('no common affix', [[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]], [[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]), ('interleaved edits are grouped deletion first', [[[1, 'I'], [-1, 'D'], [1, 'J'], [-1, 'E']]], [[-1, 'DE'], [1, 'IJ']]), ('suffix at the end of the text', [[[0, 'st'], [-1, 'xyz5'], [1, 'uvz5']]], [[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z5']]), ('prefix at the start of the text', [[[-1, 'prepreprepreprea'], [1, 'preprepreprepreb'], [0, 'tail']]], [[0, 'preprepreprepre'], [-1, 'a'], [1, 'b'], [0, 'tail']]), ('insertion only', [[[0, 'a'], [1, 'b'], [0, 'c']]], [[0, 'a'], [1, 'b'], [0, 'c']]), ('empty equality between edits', [[[0, 'k'], [-1, 'ab5'], [0, ''], [1, 'ac5']]], [[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '5']])],
}[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
adjacent equalities merge	`[[0, 'abcd']]`	`[[0, 'abcd']]`	Passed
empty entries are dropped	`[[0, 'a'], [1, 'b']]`	`[[0, 'a'], [1, 'b']]`	Passed
common prefix moves into the previous equality	`[[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]`	`[[0, 'xab'], [-1, 'c'], [1, 'd'], [0, 'y']]`	Passed
common suffix moves into the next equality	`[[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]`	`[[0, 'p'], [-1, 'k'], [1, 'm'], [0, 'zq']]`	Passed
no common affix	`[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]`	`[[0, 'h'], [-1, 'ab'], [1, 'cd'], [0, 'e']]`	Passed
interleaved edits are grouped deletion first	`[[-1, 'DE'], [1, 'IJ']]`	`[[-1, 'DE'], [1, 'IJ']]`	Passed
suffix at the end of the text	`[[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z1']]`	`[[0, 'st'], [-1, 'xy'], [1, 'uv'], [0, 'z1']]`	Passed
prefix at the start of the text	`[[0, 'pre'], [-1, 'a'], [1, 'b'], [0, 'tail']]`	`[[0, 'pre'], [-1, 'a'], [1, 'b'], [0, 'tail']]`	Passed
insertion only	`[[0, 'a'], [1, 'b'], [0, 'c']]`	`[[0, 'a'], [1, 'b'], [0, 'c']]`	Passed
empty equality between edits	`[[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '1']]`	`[[0, 'ka'], [-1, 'b'], [1, 'c'], [0, '1']]`	Passed

SHA-256 / ef74d16deb1fb8eefd5809e2832497e8e9b4b810fb3a90fc851295b7626bdcf3

Verification & scope

A deterministic, bounded teaching model of one diff, patch or merge rule with stipulated conventions; it is not a production diff or version-control implementation and makes no claim of conformance to any specific tool. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:49:08.092796+00:00.

Case digest / 0a6f23a9cc409903649418780b6ce79b6b5bfaffcb5886cdeb482cabcd3f7694