FA-75086 / CRDT convergence / Open access

Replicated growable array: deletes remove the slot physically · case 01

An insert that references a deleted character lands at the head of the document.

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

ROOT CAUSE

Delete removes the element, so later operations anchored to it cannot find their reference.

VERIFIED REPAIR

Keep deleted elements as tombstones and hide them only when rendering.

Unsuccessful approach: Keeping tombstones but ignoring them during reference lookup still sends inserts anchored at a deleted character to the head.

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]):
                    seq.remove(e)
                    break
    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': 2, 'text': '!H'}`	`{'slots': 3, 'text': 'H!'}`	Failed
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': 4, 'text': 'WHyi'}`	`{'slots': 5, 'text': 'HWyi'}`	Failed
smaller tombstone stays after the new insert	`{'slots': 4, 'text': 'WHmi'}`	`{'slots': 5, 'text': 'HmWi'}`	Failed
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': 0, 'text': ''}`	`{'slots': 2, 'text': ''}`	Failed

SHA-256 / 547ba70c22d386b296ebeab528ae437e5c9aaaee1bf445f92c271b1538ea4433

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) and not e[2]), -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!'}`	Failed
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': 'WHyi'}`	`{'slots': 5, 'text': 'HWyi'}`	Failed
smaller tombstone stays after the new insert	`{'slots': 5, 'text': 'WHmi'}`	`{'slots': 5, 'text': 'HmWi'}`	Failed
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 / aba86d328dc208cd9b86c0f802da965d76a109c623cd2f90b2ff4e3d17cf4a74

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

Case digest / 240333cfd21f25a3454d96bc176fcda3c0913accc1d7df65b614422220366154