FA-75081 / CRDT convergence / Open access

Replicated growable array: insertion skips smaller ids instead of larger ones · case 01

Two replicas receiving the same concurrent inserts in different orders show different text.

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

ROOT CAUSE

The skip loop advances past elements with smaller ids, which is not a consistent total order with the insertion rule.

VERIFIED REPAIR

Skip following elements while their id is greater than the new id.

Unsuccessful approach: Comparing only counters leaves equal-counter inserts from different replicas in arrival order.

Case contract

A sequence of [id, char, deleted] where id = (counter, replica). ["ins", id, after, ch] finds the element with id `after` (head when None or unknown), moves one past it, then skips every following element whose id is greater than the new id before inserting. ["del", id] marks the element deleted but keeps it. Return visible text and the number of slots including tombstones.

Why this case matters

RGA orders concurrent insertions deterministically so that every causally valid delivery order yields the same text.

1 / The failure

Exit 1

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

N = 1
observations = []
def solve(ops):
    seq = []
    for op in ops:
        if op[0] == 'ins':
            nid, after, ch = tuple(op[1]), op[2], op[3]
            if after is None:
                pos = 0
            else:
                pos = next((i for i, e in enumerate(seq) if e[0] == tuple(after)), -1) + 1
            while pos < len(seq) and seq[pos][0] < nid:
                pos += 1
            seq.insert(pos, [nid, ch, False])
        else:
            for e in seq:
                if e[0] == tuple(op[1]):
                    e[2] = True
    return {'text': ''.join(e[1] for e in seq if not e[2]), 'slots': len(seq)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [1, 'a'], 'Z'], ['del', [5, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [6, 'd'], [5, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [5, 'c'], [1, 'a'], 'm'], ['ins', [6, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [3, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c']]], {'text': 'abc', 'slots': 3}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    2: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [6, 'b'], [1, 'a'], 'Z'], ['del', [6, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [7, 'd'], [6, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [6, 'c'], [1, 'a'], 'm'], ['ins', [7, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [4, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd']]], {'text': 'abcd', 'slots': 4}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    3: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [7, 'b'], [1, 'a'], 'Z'], ['del', [7, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [8, 'd'], [7, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [7, 'c'], [1, 'a'], 'm'], ['ins', [8, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [5, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e']]], {'text': 'abcde', 'slots': 5}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    4: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [8, 'b'], [1, 'a'], 'Z'], ['del', [8, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [9, 'd'], [8, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [8, 'c'], [1, 'a'], 'm'], ['ins', [9, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [6, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f']]], {'text': 'abcdef', 'slots': 6}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    5: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [9, 'b'], [1, 'a'], 'Z'], ['del', [9, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [10, 'd'], [9, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [9, 'c'], [1, 'a'], 'm'], ['ins', [10, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [7, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f'], ['ins', [7, 'a'], [6, 'a'], 'g']]], {'text': 'abcdefg', 'slots': 7}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
}[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
concurrent inserts at one position, order a	`{'slots': 4, 'text': 'HiXY'}`	`{'slots': 4, 'text': 'HiYX'}`	Failed
concurrent inserts at one position, order b	`{'slots': 4, 'text': 'HiXY'}`	`{'slots': 4, 'text': 'HiYX'}`	Failed
insert after a deleted character	`{'slots': 3, 'text': 'H!'}`	`{'slots': 3, 'text': 'H!'}`	Passed
concurrent head inserts	`{'slots': 3, 'text': 'abc'}`	`{'slots': 3, 'text': 'cba'}`	Failed
insert skips a larger concurrent subtree	`{'slots': 5, 'text': 'HiPQR'}`	`{'slots': 5, 'text': 'HiQRP'}`	Failed
skip continues past a larger tombstone	`{'slots': 5, 'text': 'HiyW'}`	`{'slots': 5, 'text': 'HWyi'}`	Failed
smaller tombstone stays after the new insert	`{'slots': 5, 'text': 'HimW'}`	`{'slots': 5, 'text': 'HmWi'}`	Failed
several larger head inserts are skipped	`{'slots': 3, 'text': 'zyx'}`	`{'slots': 3, 'text': 'xyz'}`	Failed
sequential typing	`{'slots': 3, 'text': 'abc'}`	`{'slots': 3, 'text': 'abc'}`	Passed
deleting keeps the slot	`{'slots': 2, 'text': ''}`	`{'slots': 2, 'text': ''}`	Passed

SHA-256 / 40c1794ace915856ef9197c14aba0254756f9a694a4a307eeabbb8ac53b2652e

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(ops):
    seq = []
    for op in ops:
        if op[0] == 'ins':
            nid, after, ch = tuple(op[1]), op[2], op[3]
            if after is None:
                pos = 0
            else:
                pos = next((i for i, e in enumerate(seq) if e[0] == tuple(after)), -1) + 1
            while pos < len(seq) and seq[pos][0][0] > nid[0]:
                pos += 1
            seq.insert(pos, [nid, ch, False])
        else:
            for e in seq:
                if e[0] == tuple(op[1]):
                    e[2] = True
    return {'text': ''.join(e[1] for e in seq if not e[2]), 'slots': len(seq)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [1, 'a'], 'Z'], ['del', [5, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [6, 'd'], [5, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [5, 'c'], [1, 'a'], 'm'], ['ins', [6, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [3, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c']]], {'text': 'abc', 'slots': 3}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    2: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [6, 'b'], [1, 'a'], 'Z'], ['del', [6, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [7, 'd'], [6, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [6, 'c'], [1, 'a'], 'm'], ['ins', [7, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [4, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd']]], {'text': 'abcd', 'slots': 4}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    3: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [7, 'b'], [1, 'a'], 'Z'], ['del', [7, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [8, 'd'], [7, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [7, 'c'], [1, 'a'], 'm'], ['ins', [8, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [5, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e']]], {'text': 'abcde', 'slots': 5}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    4: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [8, 'b'], [1, 'a'], 'Z'], ['del', [8, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [9, 'd'], [8, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [8, 'c'], [1, 'a'], 'm'], ['ins', [9, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [6, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f']]], {'text': 'abcdef', 'slots': 6}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    5: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [9, 'b'], [1, 'a'], 'Z'], ['del', [9, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [10, 'd'], [9, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [9, 'c'], [1, 'a'], 'm'], ['ins', [10, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [7, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f'], ['ins', [7, 'a'], [6, 'a'], 'g']]], {'text': 'abcdefg', 'slots': 7}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
}[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
concurrent inserts at one position, order a	`{'slots': 4, 'text': 'HiYX'}`	`{'slots': 4, 'text': 'HiYX'}`	Passed
concurrent inserts at one position, order b	`{'slots': 4, 'text': 'HiXY'}`	`{'slots': 4, 'text': 'HiYX'}`	Failed
insert after a deleted character	`{'slots': 3, 'text': 'H!'}`	`{'slots': 3, 'text': 'H!'}`	Passed
concurrent head inserts	`{'slots': 3, 'text': 'cab'}`	`{'slots': 3, 'text': 'cba'}`	Failed
insert skips a larger concurrent subtree	`{'slots': 5, 'text': 'HiQRP'}`	`{'slots': 5, 'text': 'HiQRP'}`	Passed
skip continues past a larger tombstone	`{'slots': 5, 'text': 'HWyi'}`	`{'slots': 5, 'text': 'HWyi'}`	Passed
smaller tombstone stays after the new insert	`{'slots': 5, 'text': 'HmWi'}`	`{'slots': 5, 'text': 'HmWi'}`	Passed
several larger head inserts are skipped	`{'slots': 3, 'text': 'xyz'}`	`{'slots': 3, 'text': 'xyz'}`	Passed
sequential typing	`{'slots': 3, 'text': 'abc'}`	`{'slots': 3, 'text': 'abc'}`	Passed
deleting keeps the slot	`{'slots': 2, 'text': ''}`	`{'slots': 2, 'text': ''}`	Passed

SHA-256 / cd92f48506d19d5367e97864182b903c5dab94eaa15778670e9b481863850002

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(ops):
    seq = []
    for op in ops:
        if op[0] == 'ins':
            nid, after, ch = tuple(op[1]), op[2], op[3]
            if after is None:
                pos = 0
            else:
                pos = next((i for i, e in enumerate(seq) if e[0] == tuple(after)), -1) + 1
            while pos < len(seq) and seq[pos][0] > nid:
                pos += 1
            seq.insert(pos, [nid, ch, False])
        else:
            for e in seq:
                if e[0] == tuple(op[1]):
                    e[2] = True
    return {'text': ''.join(e[1] for e in seq if not e[2]), 'slots': len(seq)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [1, 'a'], 'Z'], ['del', [5, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [6, 'd'], [5, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [5, 'c'], [1, 'a'], 'm'], ['ins', [6, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [3, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c']]], {'text': 'abc', 'slots': 3}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    2: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [6, 'b'], [1, 'a'], 'Z'], ['del', [6, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [7, 'd'], [6, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [6, 'c'], [1, 'a'], 'm'], ['ins', [7, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [4, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd']]], {'text': 'abcd', 'slots': 4}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    3: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [7, 'b'], [1, 'a'], 'Z'], ['del', [7, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [8, 'd'], [7, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [7, 'c'], [1, 'a'], 'm'], ['ins', [8, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [5, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e']]], {'text': 'abcde', 'slots': 5}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    4: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [8, 'b'], [1, 'a'], 'Z'], ['del', [8, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [9, 'd'], [8, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [8, 'c'], [1, 'a'], 'm'], ['ins', [9, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [6, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f']]], {'text': 'abcdef', 'slots': 6}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    5: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [9, 'b'], [1, 'a'], 'Z'], ['del', [9, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [10, 'd'], [9, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [9, 'c'], [1, 'a'], 'm'], ['ins', [10, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [7, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f'], ['ins', [7, 'a'], [6, 'a'], 'g']]], {'text': 'abcdefg', 'slots': 7}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
}[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
concurrent inserts at one position, order a	`{'slots': 4, 'text': 'HiYX'}`	`{'slots': 4, 'text': 'HiYX'}`	Passed
concurrent inserts at one position, order b	`{'slots': 4, 'text': 'HiYX'}`	`{'slots': 4, 'text': 'HiYX'}`	Passed
insert after a deleted character	`{'slots': 3, 'text': 'H!'}`	`{'slots': 3, 'text': 'H!'}`	Passed
concurrent head inserts	`{'slots': 3, 'text': 'cba'}`	`{'slots': 3, 'text': 'cba'}`	Passed
insert skips a larger concurrent subtree	`{'slots': 5, 'text': 'HiQRP'}`	`{'slots': 5, 'text': 'HiQRP'}`	Passed
skip continues past a larger tombstone	`{'slots': 5, 'text': 'HWyi'}`	`{'slots': 5, 'text': 'HWyi'}`	Passed
smaller tombstone stays after the new insert	`{'slots': 5, 'text': 'HmWi'}`	`{'slots': 5, 'text': 'HmWi'}`	Passed
several larger head inserts are skipped	`{'slots': 3, 'text': 'xyz'}`	`{'slots': 3, 'text': 'xyz'}`	Passed
sequential typing	`{'slots': 3, 'text': 'abc'}`	`{'slots': 3, 'text': 'abc'}`	Passed
deleting keeps the slot	`{'slots': 2, 'text': ''}`	`{'slots': 2, 'text': ''}`	Passed

SHA-256 / 9bcaceb515f79d002a2890ca3795a22d2b624825bd06601e6fab2342202a458b

Verification & scope

A deterministic, bounded teaching model of one replicated data type with stipulated operation and merge rules; it is not a production CRDT library and makes no claim of conformance to any specific published design. 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:02.914258+00:00.

Case digest / 4cda3056ea97913a360e50646be62253cd53ae559676032569bd52851330d17f