FA-75246 / CRDT convergence / Open access
Replicated tree move: undoing a node's first move leaves a null parent entry · case 01
A node that has not been created yet appears in the tree with a null parent.
ROOT CAUSE
Undoing the move that first attached a node stores None as its parent instead of removing the node.
VERIFIED REPAIR
Undoing a node's first move removes the node from the parent map.
Unsuccessful approach: Restoring the node under the root invents a placement that no move requested.
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[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 | [['r', None]] | [] | Failed |
| parent whose own move was skipped is not attached | [] | [] | Passed |
| late move replays newer moves in timestamp order | [['p', 'q'], ['q', 'root'], ['r', 'q']] | [['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 | [['p', None]] | [] | Failed |
| undoing a skipped first move does not attach | [['p', None]] | [] | Failed |
| 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 / 60d47ddb354b9353afa4ea640d815c7e8b2324dc66626de31d8d1b96d4379696
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[entry[1]] = 'root'
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 | [['r', 'root']] | [] | Failed |
| parent whose own move was skipped is not attached | [] | [] | Passed |
| late move replays newer moves in timestamp order | [['p', 'q'], ['q', 'root'], ['r', 'q']] | [['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 | [['p', 'root']] | [] | Failed |
| undoing a skipped first move does not attach | [['p', 'root']] | [] | Failed |
| 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 / bbc6bed3376bb79707a4328d38943ab85ffdfba77f2d66b98f3eddfe307a2f80
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.489054+00:00.
Case digest / adfd4f5e886026caedcd4ef457bf734aabde7fbd6c0541a2b17e1e2d4cf92deb