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

Hunk overlap check: an insertion is modelled as an empty range at its start line · case 01

Insertions directly before a changed range are not flagged.

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

ROOT CAUSE

A zero-length hunk becomes the empty span (start, start-1) instead of a point after the start line.

VERIFIED REPAIR

Place an insertion after line s at s + 0.5.

Unsuccessful approach: Placing the insertion on line s itself reports conflicts with changes two lines above.

Case contract

Two patches against the same base list hunks as [old_start, old_len]. A hunk with length > 0 covers lines start..start+len-1; a zero-length hunk is an insertion after line start and sits at start+0.5. Hunks conflict when their spans overlap or are adjacent (within one line). Return sorted [i, j] index pairs of conflicting hunks from the first and second patch.

Why this case matters

Cherry-picks and concurrent patch application refuse to auto-merge changes that touch or abut the same lines.

1 / The failure

Exit 1

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

N = 1
observations = []
def solve(p1, p2):
    def span(h):
        s, ln = h
        if ln == 0:
            return (s, s - 1)
        return (s, s + ln - 1)
    out = []
    for i, h1 in enumerate(p1):
        a_lo, a_hi = span(h1)
        for j, h2 in enumerate(p2):
            b_lo, b_hi = span(h2)
            if a_lo <= b_hi + 1 and b_lo <= a_hi + 1:
                out.append([i, j])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('overlapping ranges', [[[3, 4]], [[5, 2]]], [[0, 0]]), ('adjacent ranges conflict', [[[1, 3]], [[4, 2]]], [[0, 0]]), ('one line apart is clean', [[[1, 3]], [[5, 2]]], []), ('insertions at the same point', [[[5, 0]], [[5, 0]]], [[0, 0]]), ('insertion next to a range', [[[5, 0]], [[6, 3], [8, 1]]], [[0, 0]]), ('insertion inside a range', [[[2, 5]], [[4, 0]]], [[0, 0]]), ('insertion two lines above a range', [[[4, 0]], [[6, 2]]], []), ('single-line ranges touching', [[[10, 1], [20, 1]], [[11, 1], [30, 1]]], [[0, 0]]), ('far apart', [[[1, 1]], [[50, 0]]], []), ('insertion one line below a range end', [[[5, 0]], [[2, 3]]], [])],
    2: [('overlapping ranges', [[[3, 4]], [[5, 2]]], [[0, 0]]), ('adjacent ranges conflict', [[[1, 3]], [[4, 2]]], [[0, 0]]), ('one line apart is clean', [[[1, 3]], [[5, 2]]], []), ('insertions at the same point', [[[5, 0]], [[5, 0]]], [[0, 0]]), ('insertion next to a range', [[[5, 0]], [[6, 3], [9, 1]]], [[0, 0]]), ('insertion inside a range', [[[2, 5]], [[4, 0]]], [[0, 0]]), ('insertion two lines above a range', [[[4, 0]], [[6, 2]]], []), ('single-line ranges touching', [[[10, 1], [20, 1]], [[11, 1], [30, 2]]], [[0, 0]]), ('far apart', [[[1, 1]], [[50, 0]]], []), ('insertion one line below a range end', [[[5, 0]], [[2, 3]]], [])],
    3: [('overlapping ranges', [[[3, 4]], [[5, 2]]], [[0, 0]]), ('adjacent ranges conflict', [[[1, 3]], [[4, 2]]], [[0, 0]]), ('one line apart is clean', [[[1, 3]], [[5, 2]]], []), ('insertions at the same point', [[[5, 0]], [[5, 0]]], [[0, 0]]), ('insertion next to a range', [[[5, 0]], [[6, 3], [10, 1]]], [[0, 0]]), ('insertion inside a range', [[[2, 5]], [[4, 0]]], [[0, 0]]), ('insertion two lines above a range', [[[4, 0]], [[6, 2]]], []), ('single-line ranges touching', [[[10, 1], [20, 1]], [[11, 1], [30, 3]]], [[0, 0]]), ('far apart', [[[1, 1]], [[50, 0]]], []), ('insertion one line below a range end', [[[5, 0]], [[2, 3]]], [])],
    4: [('overlapping ranges', [[[3, 4]], [[5, 2]]], [[0, 0]]), ('adjacent ranges conflict', [[[1, 3]], [[4, 2]]], [[0, 0]]), ('one line apart is clean', [[[1, 3]], [[5, 2]]], []), ('insertions at the same point', [[[5, 0]], [[5, 0]]], [[0, 0]]), ('insertion next to a range', [[[5, 0]], [[6, 3], [11, 1]]], [[0, 0]]), ('insertion inside a range', [[[2, 5]], [[4, 0]]], [[0, 0]]), ('insertion two lines above a range', [[[4, 0]], [[6, 2]]], []), ('single-line ranges touching', [[[10, 1], [20, 1]], [[11, 1], [30, 4]]], [[0, 0]]), ('far apart', [[[1, 1]], [[50, 0]]], []), ('insertion one line below a range end', [[[5, 0]], [[2, 3]]], [])],
    5: [('overlapping ranges', [[[3, 4]], [[5, 2]]], [[0, 0]]), ('adjacent ranges conflict', [[[1, 3]], [[4, 2]]], [[0, 0]]), ('one line apart is clean', [[[1, 3]], [[5, 2]]], []), ('insertions at the same point', [[[5, 0]], [[5, 0]]], [[0, 0]]), ('insertion next to a range', [[[5, 0]], [[6, 3], [12, 1]]], [[0, 0]]), ('insertion inside a range', [[[2, 5]], [[4, 0]]], [[0, 0]]), ('insertion two lines above a range', [[[4, 0]], [[6, 2]]], []), ('single-line ranges touching', [[[10, 1], [20, 1]], [[11, 1], [30, 5]]], [[0, 0]]), ('far apart', [[[1, 1]], [[50, 0]]], []), ('insertion one line below a range end', [[[5, 0]], [[2, 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 fixture	Actual	Expected	Outcome
overlapping ranges	`[[0, 0]]`	`[[0, 0]]`	Passed
adjacent ranges conflict	`[[0, 0]]`	`[[0, 0]]`	Passed
one line apart is clean	`[]`	`[]`	Passed
insertions at the same point	`[[0, 0]]`	`[[0, 0]]`	Passed
insertion next to a range	`[]`	`[[0, 0]]`	Failed
insertion inside a range	`[[0, 0]]`	`[[0, 0]]`	Passed
insertion two lines above a range	`[]`	`[]`	Passed
single-line ranges touching	`[[0, 0]]`	`[[0, 0]]`	Passed
far apart	`[]`	`[]`	Passed
insertion one line below a range end	`[[0, 0]]`	`[]`	Failed

SHA-256 / 1d72a1a08367714d1b1506d0efd1198cd213c409698c6ee58b9f8f9053fb37b6

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(p1, p2):
    def span(h):
        s, ln = h
        if ln == 0:
            return (s, s)
        return (s, s + ln - 1)
    out = []
    for i, h1 in enumerate(p1):
        a_lo, a_hi = span(h1)
        for j, h2 in enumerate(p2):
            b_lo, b_hi = span(h2)
            if a_lo <= b_hi + 1 and b_lo <= a_hi + 1:
                out.append([i, j])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('overlapping ranges', [[[3, 4]], [[5, 2]]], [[0, 0]]), ('adjacent ranges conflict', [[[1, 3]], [[4, 2]]], [[0, 0]]), ('one line apart is clean', [[[1, 3]], [[5, 2]]], []), ('insertions at the same point', [[[5, 0]], [[5, 0]]], [[0, 0]]), ('insertion next to a range', [[[5, 0]], [[6, 3], [8, 1]]], [[0, 0]]), ('insertion inside a range', [[[2, 5]], [[4, 0]]], [[0, 0]]), ('insertion two lines above a range', [[[4, 0]], [[6, 2]]], []), ('single-line ranges touching', [[[10, 1], [20, 1]], [[11, 1], [30, 1]]], [[0, 0]]), ('far apart', [[[1, 1]], [[50, 0]]], []), ('insertion one line below a range end', [[[5, 0]], [[2, 3]]], [])],
    2: [('overlapping ranges', [[[3, 4]], [[5, 2]]], [[0, 0]]), ('adjacent ranges conflict', [[[1, 3]], [[4, 2]]], [[0, 0]]), ('one line apart is clean', [[[1, 3]], [[5, 2]]], []), ('insertions at the same point', [[[5, 0]], [[5, 0]]], [[0, 0]]), ('insertion next to a range', [[[5, 0]], [[6, 3], [9, 1]]], [[0, 0]]), ('insertion inside a range', [[[2, 5]], [[4, 0]]], [[0, 0]]), ('insertion two lines above a range', [[[4, 0]], [[6, 2]]], []), ('single-line ranges touching', [[[10, 1], [20, 1]], [[11, 1], [30, 2]]], [[0, 0]]), ('far apart', [[[1, 1]], [[50, 0]]], []), ('insertion one line below a range end', [[[5, 0]], [[2, 3]]], [])],
    3: [('overlapping ranges', [[[3, 4]], [[5, 2]]], [[0, 0]]), ('adjacent ranges conflict', [[[1, 3]], [[4, 2]]], [[0, 0]]), ('one line apart is clean', [[[1, 3]], [[5, 2]]], []), ('insertions at the same point', [[[5, 0]], [[5, 0]]], [[0, 0]]), ('insertion next to a range', [[[5, 0]], [[6, 3], [10, 1]]], [[0, 0]]), ('insertion inside a range', [[[2, 5]], [[4, 0]]], [[0, 0]]), ('insertion two lines above a range', [[[4, 0]], [[6, 2]]], []), ('single-line ranges touching', [[[10, 1], [20, 1]], [[11, 1], [30, 3]]], [[0, 0]]), ('far apart', [[[1, 1]], [[50, 0]]], []), ('insertion one line below a range end', [[[5, 0]], [[2, 3]]], [])],
    4: [('overlapping ranges', [[[3, 4]], [[5, 2]]], [[0, 0]]), ('adjacent ranges conflict', [[[1, 3]], [[4, 2]]], [[0, 0]]), ('one line apart is clean', [[[1, 3]], [[5, 2]]], []), ('insertions at the same point', [[[5, 0]], [[5, 0]]], [[0, 0]]), ('insertion next to a range', [[[5, 0]], [[6, 3], [11, 1]]], [[0, 0]]), ('insertion inside a range', [[[2, 5]], [[4, 0]]], [[0, 0]]), ('insertion two lines above a range', [[[4, 0]], [[6, 2]]], []), ('single-line ranges touching', [[[10, 1], [20, 1]], [[11, 1], [30, 4]]], [[0, 0]]), ('far apart', [[[1, 1]], [[50, 0]]], []), ('insertion one line below a range end', [[[5, 0]], [[2, 3]]], [])],
    5: [('overlapping ranges', [[[3, 4]], [[5, 2]]], [[0, 0]]), ('adjacent ranges conflict', [[[1, 3]], [[4, 2]]], [[0, 0]]), ('one line apart is clean', [[[1, 3]], [[5, 2]]], []), ('insertions at the same point', [[[5, 0]], [[5, 0]]], [[0, 0]]), ('insertion next to a range', [[[5, 0]], [[6, 3], [12, 1]]], [[0, 0]]), ('insertion inside a range', [[[2, 5]], [[4, 0]]], [[0, 0]]), ('insertion two lines above a range', [[[4, 0]], [[6, 2]]], []), ('single-line ranges touching', [[[10, 1], [20, 1]], [[11, 1], [30, 5]]], [[0, 0]]), ('far apart', [[[1, 1]], [[50, 0]]], []), ('insertion one line below a range end', [[[5, 0]], [[2, 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 fixture	Actual	Expected	Outcome
overlapping ranges	`[[0, 0]]`	`[[0, 0]]`	Passed
adjacent ranges conflict	`[[0, 0]]`	`[[0, 0]]`	Passed
one line apart is clean	`[]`	`[]`	Passed
insertions at the same point	`[[0, 0]]`	`[[0, 0]]`	Passed
insertion next to a range	`[[0, 0]]`	`[[0, 0]]`	Passed
insertion inside a range	`[[0, 0]]`	`[[0, 0]]`	Passed
insertion two lines above a range	`[]`	`[]`	Passed
single-line ranges touching	`[[0, 0]]`	`[[0, 0]]`	Passed
far apart	`[]`	`[]`	Passed
insertion one line below a range end	`[[0, 0]]`	`[]`	Failed

SHA-256 / 3c90638464fcdb7e816c72c2679a332f9b3d26fa9cf62c0d83ca2d14a210c93f

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(p1, p2):
    def span(h):
        s, ln = h
        if ln == 0:
            return (s + 0.5, s + 0.5)
        return (s, s + ln - 1)
    out = []
    for i, h1 in enumerate(p1):
        a_lo, a_hi = span(h1)
        for j, h2 in enumerate(p2):
            b_lo, b_hi = span(h2)
            if a_lo <= b_hi + 1 and b_lo <= a_hi + 1:
                out.append([i, j])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('overlapping ranges', [[[3, 4]], [[5, 2]]], [[0, 0]]), ('adjacent ranges conflict', [[[1, 3]], [[4, 2]]], [[0, 0]]), ('one line apart is clean', [[[1, 3]], [[5, 2]]], []), ('insertions at the same point', [[[5, 0]], [[5, 0]]], [[0, 0]]), ('insertion next to a range', [[[5, 0]], [[6, 3], [8, 1]]], [[0, 0]]), ('insertion inside a range', [[[2, 5]], [[4, 0]]], [[0, 0]]), ('insertion two lines above a range', [[[4, 0]], [[6, 2]]], []), ('single-line ranges touching', [[[10, 1], [20, 1]], [[11, 1], [30, 1]]], [[0, 0]]), ('far apart', [[[1, 1]], [[50, 0]]], []), ('insertion one line below a range end', [[[5, 0]], [[2, 3]]], [])],
    2: [('overlapping ranges', [[[3, 4]], [[5, 2]]], [[0, 0]]), ('adjacent ranges conflict', [[[1, 3]], [[4, 2]]], [[0, 0]]), ('one line apart is clean', [[[1, 3]], [[5, 2]]], []), ('insertions at the same point', [[[5, 0]], [[5, 0]]], [[0, 0]]), ('insertion next to a range', [[[5, 0]], [[6, 3], [9, 1]]], [[0, 0]]), ('insertion inside a range', [[[2, 5]], [[4, 0]]], [[0, 0]]), ('insertion two lines above a range', [[[4, 0]], [[6, 2]]], []), ('single-line ranges touching', [[[10, 1], [20, 1]], [[11, 1], [30, 2]]], [[0, 0]]), ('far apart', [[[1, 1]], [[50, 0]]], []), ('insertion one line below a range end', [[[5, 0]], [[2, 3]]], [])],
    3: [('overlapping ranges', [[[3, 4]], [[5, 2]]], [[0, 0]]), ('adjacent ranges conflict', [[[1, 3]], [[4, 2]]], [[0, 0]]), ('one line apart is clean', [[[1, 3]], [[5, 2]]], []), ('insertions at the same point', [[[5, 0]], [[5, 0]]], [[0, 0]]), ('insertion next to a range', [[[5, 0]], [[6, 3], [10, 1]]], [[0, 0]]), ('insertion inside a range', [[[2, 5]], [[4, 0]]], [[0, 0]]), ('insertion two lines above a range', [[[4, 0]], [[6, 2]]], []), ('single-line ranges touching', [[[10, 1], [20, 1]], [[11, 1], [30, 3]]], [[0, 0]]), ('far apart', [[[1, 1]], [[50, 0]]], []), ('insertion one line below a range end', [[[5, 0]], [[2, 3]]], [])],
    4: [('overlapping ranges', [[[3, 4]], [[5, 2]]], [[0, 0]]), ('adjacent ranges conflict', [[[1, 3]], [[4, 2]]], [[0, 0]]), ('one line apart is clean', [[[1, 3]], [[5, 2]]], []), ('insertions at the same point', [[[5, 0]], [[5, 0]]], [[0, 0]]), ('insertion next to a range', [[[5, 0]], [[6, 3], [11, 1]]], [[0, 0]]), ('insertion inside a range', [[[2, 5]], [[4, 0]]], [[0, 0]]), ('insertion two lines above a range', [[[4, 0]], [[6, 2]]], []), ('single-line ranges touching', [[[10, 1], [20, 1]], [[11, 1], [30, 4]]], [[0, 0]]), ('far apart', [[[1, 1]], [[50, 0]]], []), ('insertion one line below a range end', [[[5, 0]], [[2, 3]]], [])],
    5: [('overlapping ranges', [[[3, 4]], [[5, 2]]], [[0, 0]]), ('adjacent ranges conflict', [[[1, 3]], [[4, 2]]], [[0, 0]]), ('one line apart is clean', [[[1, 3]], [[5, 2]]], []), ('insertions at the same point', [[[5, 0]], [[5, 0]]], [[0, 0]]), ('insertion next to a range', [[[5, 0]], [[6, 3], [12, 1]]], [[0, 0]]), ('insertion inside a range', [[[2, 5]], [[4, 0]]], [[0, 0]]), ('insertion two lines above a range', [[[4, 0]], [[6, 2]]], []), ('single-line ranges touching', [[[10, 1], [20, 1]], [[11, 1], [30, 5]]], [[0, 0]]), ('far apart', [[[1, 1]], [[50, 0]]], []), ('insertion one line below a range end', [[[5, 0]], [[2, 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 fixture	Actual	Expected	Outcome
overlapping ranges	`[[0, 0]]`	`[[0, 0]]`	Passed
adjacent ranges conflict	`[[0, 0]]`	`[[0, 0]]`	Passed
one line apart is clean	`[]`	`[]`	Passed
insertions at the same point	`[[0, 0]]`	`[[0, 0]]`	Passed
insertion next to a range	`[[0, 0]]`	`[[0, 0]]`	Passed
insertion inside a range	`[[0, 0]]`	`[[0, 0]]`	Passed
insertion two lines above a range	`[]`	`[]`	Passed
single-line ranges touching	`[[0, 0]]`	`[[0, 0]]`	Passed
far apart	`[]`	`[]`	Passed
insertion one line below a range end	`[]`	`[]`	Passed

SHA-256 / 6bdf6061eb7d8c82fd5a83e1a1586f9de324081848b4417a3faa395d45b5aa23

Verification & scope

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

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

Case digest / d252f6daa77b9d7882ae673faf8264c8787e1f9e5a517d1cc7d52ef52598aa74