FA-75241 / CRDT convergence / Open access
Replicated tree move: undone moves are redone newest first · case 01
After a late move, redone moves apply in reverse timestamp order and a stale move wins.
ROOT CAUSE
The redo list is replayed in the order it was popped, which is descending by timestamp.
VERIFIED REPAIR
Redo undone moves in ascending timestamp order.
Unsuccessful approach: Redoing in node-name order is deterministic but not timestamp order.
Case contract
Moves [[counter, replica], node, parent] arrive in any order. The replica keeps a log sorted by timestamp. On arrival it undoes every logged move with a larger timestamp (restoring the old parent, or detaching a node that had none), applies the new move, then redoes the undone moves in timestamp order. A move is skipped (logged, tree unchanged) when the parent is neither "root" nor attached, or when the node is the parent or one of its ancestors. Return sorted [node, parent] pairs.
Why this case matters
Tree CRDTs must reject moves that create cycles, and must reach the same tree regardless of delivery order.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ops):
parent = {}
log = []
MISSING = '<missing>'
def is_anc(a, x):
for _ in range(len(parent) + 2):
if x is None:
return False
if x == a:
return True
x = parent.get(x)
return True
def do(ts, node, par):
old = parent.get(node, MISSING)
if (par == 'root' or par in parent) and not is_anc(node, par):
parent[node] = par
log.append([ts, node, par, old])
def undo(entry):
if entry[3] == MISSING:
parent.pop(entry[1], None)
else:
parent[entry[1]] = entry[3]
for op in ops:
ts = tuple(op[0])
redo = []
while log and log[-1][0] > ts:
entry = log.pop()
undo(entry)
redo.append(entry)
do(ts, op[1], op[2])
for entry in redo:
do(entry[0], entry[1], entry[2])
return sorted([k, v] for k, v in parent.items())
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[4, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[3, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[6, 'a'], 'm', 'k'], [[5, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[6, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[6, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[3, 'a'], 'q', 'root'], [[5, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[5, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[4, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[5, 'b'], 'p', 'q'], [[4, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[6, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[3, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
2: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[5, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[4, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[7, 'a'], 'm', 'k'], [[6, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[7, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[7, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[4, 'a'], 'q', 'root'], [[6, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[6, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[5, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[6, 'b'], 'p', 'q'], [[5, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[7, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[4, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
3: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[6, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[5, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[8, 'a'], 'm', 'k'], [[7, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[8, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[8, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[5, 'a'], 'q', 'root'], [[7, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[7, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[6, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[7, 'b'], 'p', 'q'], [[6, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[8, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[5, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
4: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[7, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[6, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[9, 'a'], 'm', 'k'], [[8, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[9, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[9, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[6, 'a'], 'q', 'root'], [[8, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[8, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[7, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[8, 'b'], 'p', 'q'], [[7, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[9, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[6, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
5: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[8, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[7, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[10, 'a'], 'm', 'k'], [[9, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[10, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[10, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[7, 'a'], 'q', 'root'], [[9, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[9, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[8, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[9, 'b'], 'p', 'q'], [[8, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[10, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[7, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
}[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 |
|---|---|---|---|
| moves arriving in order | [['x', 'root'], ['y', 'x'], ['z', 'y']] | [['x', 'root'], ['y', 'x'], ['z', 'y']] | Passed |
| late earlier move is replayed underneath | [['x', 'y'], ['y', 'root']] | [['x', 'y'], ['y', 'root']] | Passed |
| concurrent moves that would form a cycle | [['p', 'q'], ['q', 'root']] | [['p', 'q'], ['q', 'root']] | Passed |
| same cycle in the other arrival order | [['p', 'q'], ['q', 'root']] | [['p', 'q'], ['q', 'root']] | Passed |
| moving a node under its grandchild is skipped | [['g', 'root'], ['h', 'g'], ['i', 'h']] | [['g', 'root'], ['h', 'g'], ['i', 'h']] | Passed |
| move to a parent that does not exist yet | [['c', 'ghost'], ['ghost', 'root']] | [['c', 'ghost'], ['ghost', 'root']] | Passed |
| moving under the current grandparent is allowed | [['u', 'root'], ['v', 'u'], ['w', 'root']] | [['u', 'root'], ['v', 'u'], ['w', 'root']] | Passed |
| several late moves replay in timestamp order | [['j', 'root'], ['k', 'root'], ['m', 'k']] | [['j', 'root'], ['k', 'root'], ['m', 'k']] | Passed |
| late creation undone and redone | [['r', 'root'], ['s', 'r']] | [['r', 'root'], ['s', 'r']] | Passed |
| move under an unattached parent is skipped | [] | [] | Passed |
| parent whose own move was skipped is not attached | [] | [] | Passed |
| late move replays newer moves in timestamp order | [['q', 'root']] | [['p', 'q'], ['q', 'root']] | Failed |
| late move before a child creation | [['p', 'root'], ['q', 'p']] | [['p', 'root']] | Failed |
| undoing a skipped first move leaves no entry | [] | [] | Passed |
| undoing a skipped first move does not attach | [] | [] | Passed |
| two newer moves undone for one late move | [['q', 'r'], ['r', 'root']] | [['p', 'q'], ['q', 'r'], ['r', 'root']] | Failed |
| skipped move leaves the node in place | [['p', 'root'], ['r', 'p']] | [['p', 'root'], ['r', 'p']] | Passed |
SHA-256 / 297ab33a6aebefaae241b27c9ece63104fc89caa7e2e7d17c7c66bc38e1aee96
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ops):
parent = {}
log = []
MISSING = '<missing>'
def is_anc(a, x):
for _ in range(len(parent) + 2):
if x is None:
return False
if x == a:
return True
x = parent.get(x)
return True
def do(ts, node, par):
old = parent.get(node, MISSING)
if (par == 'root' or par in parent) and not is_anc(node, par):
parent[node] = par
log.append([ts, node, par, old])
def undo(entry):
if entry[3] == MISSING:
parent.pop(entry[1], None)
else:
parent[entry[1]] = entry[3]
for op in ops:
ts = tuple(op[0])
redo = []
while log and log[-1][0] > ts:
entry = log.pop()
undo(entry)
redo.append(entry)
do(ts, op[1], op[2])
for entry in sorted(redo, key=lambda e: e[1]):
do(entry[0], entry[1], entry[2])
return sorted([k, v] for k, v in parent.items())
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[4, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[3, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[6, 'a'], 'm', 'k'], [[5, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[6, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[6, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[3, 'a'], 'q', 'root'], [[5, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[5, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[4, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[5, 'b'], 'p', 'q'], [[4, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[6, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[3, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
2: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[5, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[4, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[7, 'a'], 'm', 'k'], [[6, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[7, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[7, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[4, 'a'], 'q', 'root'], [[6, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[6, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[5, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[6, 'b'], 'p', 'q'], [[5, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[7, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[4, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
3: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[6, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[5, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[8, 'a'], 'm', 'k'], [[7, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[8, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[8, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[5, 'a'], 'q', 'root'], [[7, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[7, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[6, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[7, 'b'], 'p', 'q'], [[6, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[8, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[5, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
4: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[7, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[6, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[9, 'a'], 'm', 'k'], [[8, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[9, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[9, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[6, 'a'], 'q', 'root'], [[8, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[8, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[7, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[8, 'b'], 'p', 'q'], [[7, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[9, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[6, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
5: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[8, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[7, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[10, 'a'], 'm', 'k'], [[9, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[10, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[10, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[7, 'a'], 'q', 'root'], [[9, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[9, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[8, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[9, 'b'], 'p', 'q'], [[8, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[10, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[7, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
}[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 |
|---|---|---|---|
| moves arriving in order | [['x', 'root'], ['y', 'x'], ['z', 'y']] | [['x', 'root'], ['y', 'x'], ['z', 'y']] | Passed |
| late earlier move is replayed underneath | [['x', 'y'], ['y', 'root']] | [['x', 'y'], ['y', 'root']] | Passed |
| concurrent moves that would form a cycle | [['p', 'q'], ['q', 'root']] | [['p', 'q'], ['q', 'root']] | Passed |
| same cycle in the other arrival order | [['p', 'q'], ['q', 'root']] | [['p', 'q'], ['q', 'root']] | Passed |
| moving a node under its grandchild is skipped | [['g', 'root'], ['h', 'g'], ['i', 'h']] | [['g', 'root'], ['h', 'g'], ['i', 'h']] | Passed |
| move to a parent that does not exist yet | [['c', 'ghost'], ['ghost', 'root']] | [['c', 'ghost'], ['ghost', 'root']] | Passed |
| moving under the current grandparent is allowed | [['u', 'root'], ['v', 'u'], ['w', 'root']] | [['u', 'root'], ['v', 'u'], ['w', 'root']] | Passed |
| several late moves replay in timestamp order | [['j', 'root'], ['k', 'root'], ['m', 'k']] | [['j', 'root'], ['k', 'root'], ['m', 'k']] | Passed |
| late creation undone and redone | [['r', 'root'], ['s', 'r']] | [['r', 'root'], ['s', 'r']] | Passed |
| move under an unattached parent is skipped | [] | [] | Passed |
| parent whose own move was skipped is not attached | [] | [] | Passed |
| late move replays newer moves in timestamp order | [['q', 'root']] | [['p', 'q'], ['q', 'root']] | Failed |
| late move before a child creation | [['p', 'root'], ['q', 'p']] | [['p', 'root']] | Failed |
| undoing a skipped first move leaves no entry | [] | [] | Passed |
| undoing a skipped first move does not attach | [] | [] | Passed |
| two newer moves undone for one late move | [['q', 'r'], ['r', 'root']] | [['p', 'q'], ['q', 'r'], ['r', 'root']] | Failed |
| skipped move leaves the node in place | [['p', 'root'], ['r', 'p']] | [['p', 'root'], ['r', 'p']] | Passed |
SHA-256 / afe7bf8116c57da0f54a716ac80f8fa710980333e400fdd50cb708a9bdf90af9
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ops):
parent = {}
log = []
MISSING = '<missing>'
def is_anc(a, x):
for _ in range(len(parent) + 2):
if x is None:
return False
if x == a:
return True
x = parent.get(x)
return True
def do(ts, node, par):
old = parent.get(node, MISSING)
if (par == 'root' or par in parent) and not is_anc(node, par):
parent[node] = par
log.append([ts, node, par, old])
def undo(entry):
if entry[3] == MISSING:
parent.pop(entry[1], None)
else:
parent[entry[1]] = entry[3]
for op in ops:
ts = tuple(op[0])
redo = []
while log and log[-1][0] > ts:
entry = log.pop()
undo(entry)
redo.append(entry)
do(ts, op[1], op[2])
for entry in reversed(redo):
do(entry[0], entry[1], entry[2])
return sorted([k, v] for k, v in parent.items())
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[4, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[3, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[6, 'a'], 'm', 'k'], [[5, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[6, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[6, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[3, 'a'], 'q', 'root'], [[5, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[5, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[4, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[5, 'b'], 'p', 'q'], [[4, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[6, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[3, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
2: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[5, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[4, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[7, 'a'], 'm', 'k'], [[6, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[7, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[7, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[4, 'a'], 'q', 'root'], [[6, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[6, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[5, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[6, 'b'], 'p', 'q'], [[5, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[7, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[4, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
3: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[6, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[5, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[8, 'a'], 'm', 'k'], [[7, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[8, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[8, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[5, 'a'], 'q', 'root'], [[7, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[7, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[6, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[7, 'b'], 'p', 'q'], [[6, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[8, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[5, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
4: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[7, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[6, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[9, 'a'], 'm', 'k'], [[8, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[9, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[9, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[6, 'a'], 'q', 'root'], [[8, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[8, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[7, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[8, 'b'], 'p', 'q'], [[7, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[9, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[6, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
5: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[8, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[7, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[10, 'a'], 'm', 'k'], [[9, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[10, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[10, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[7, 'a'], 'q', 'root'], [[9, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[9, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[8, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[9, 'b'], 'p', 'q'], [[8, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[10, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[7, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
}[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 |
|---|---|---|---|
| moves arriving in order | [['x', 'root'], ['y', 'x'], ['z', 'y']] | [['x', 'root'], ['y', 'x'], ['z', 'y']] | Passed |
| late earlier move is replayed underneath | [['x', 'y'], ['y', 'root']] | [['x', 'y'], ['y', 'root']] | Passed |
| concurrent moves that would form a cycle | [['p', 'q'], ['q', 'root']] | [['p', 'q'], ['q', 'root']] | Passed |
| same cycle in the other arrival order | [['p', 'q'], ['q', 'root']] | [['p', 'q'], ['q', 'root']] | Passed |
| moving a node under its grandchild is skipped | [['g', 'root'], ['h', 'g'], ['i', 'h']] | [['g', 'root'], ['h', 'g'], ['i', 'h']] | Passed |
| move to a parent that does not exist yet | [['c', 'ghost'], ['ghost', 'root']] | [['c', 'ghost'], ['ghost', 'root']] | Passed |
| moving under the current grandparent is allowed | [['u', 'root'], ['v', 'u'], ['w', 'root']] | [['u', 'root'], ['v', 'u'], ['w', 'root']] | Passed |
| several late moves replay in timestamp order | [['j', 'root'], ['k', 'root'], ['m', 'k']] | [['j', 'root'], ['k', 'root'], ['m', 'k']] | Passed |
| late creation undone and redone | [['r', 'root'], ['s', 'r']] | [['r', 'root'], ['s', 'r']] | Passed |
| move under an unattached parent is skipped | [] | [] | Passed |
| parent whose own move was skipped is not attached | [] | [] | Passed |
| late move replays newer moves in timestamp order | [['p', 'q'], ['q', 'root']] | [['p', 'q'], ['q', 'root']] | Passed |
| late move before a child creation | [['p', 'root']] | [['p', 'root']] | Passed |
| undoing a skipped first move leaves no entry | [] | [] | Passed |
| undoing a skipped first move does not attach | [] | [] | Passed |
| two newer moves undone for one late move | [['p', 'q'], ['q', 'r'], ['r', 'root']] | [['p', 'q'], ['q', 'r'], ['r', 'root']] | Passed |
| skipped move leaves the node in place | [['p', 'root'], ['r', 'p']] | [['p', 'root'], ['r', 'p']] | Passed |
SHA-256 / a80aff39dd6d97777fe16d063be0c42572ba2c18eb07fb2e7fa13e30336da252
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:04.467301+00:00.
Case digest / bd8903132cf1dcb4d69a32e987c35e80e02da1bd3b4985d73d7831802e5dc705