FA-75231 / CRDT convergence / Open access
Replicated tree move: a skipped move detaches the node · case 01
A rejected cyclic move makes the node and its subtree disappear from the tree.
ROOT CAUSE
When a move is skipped the node is removed from the parent map instead of staying where it was.
VERIFIED REPAIR
A skipped move leaves the tree unchanged; only the log records it.
Unsuccessful approach: Re-attaching the node to the root on a skip still moves it, differently on each replica.
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
else:
parent.pop(node, None)
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']] | [['p', 'q'], ['q', 'root']] | Failed |
| same cycle in the other arrival order | [['p', 'q']] | [['p', 'q'], ['q', 'root']] | Failed |
| moving a node under its grandchild is skipped | [['h', 'g'], ['i', 'h']] | [['g', 'root'], ['h', 'g'], ['i', 'h']] | Failed |
| 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']] | [['p', 'root'], ['r', 'p']] | Failed |
SHA-256 / 300da9a7ec9f52dd28b4c8066c4f5dc73f5b4ca1f423e5680050b4c43de40973
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
elif node in parent:
parent[node] = 'root'
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', 'root']] | [['p', 'root'], ['r', 'p']] | Failed |
SHA-256 / eb609e20f8b7a5919b736654bdfa037496cdb25c6aeba64519acac99833d72e9
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.459432+00:00.
Case digest / a5278a2da6658dbbfe11e08505ae15ac288044b283d254a135d694fd144a9c14