{"abstract":"Deque compaction builds the inverse relocation table.","category":"Bounded deques","checks":6,"contract":"Compact a deque node arena using its logical live-ID chain. Preserve chain order, remap nullable stable cursors, return old-to-new relocation map, advance epoch, and identify reclaimed old storage IDs.","contract_signature":"x","evaluation_group":"s3-bounded-deques-arena-compaction","failed_approach":"The partial repair still applies the incorrect transition to an admitted boundary or multi-element case.","family":"s3-bounded-deques-arena-compaction-relocation-direction","id":"FA-47096","implementations":{"attempt":{"sha256":"4baa13abafb2d00874c64a7bdd9ff34e073962d5a9241f4b4be88d85e1ab5728","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    records,order,cursors,epoch=x\n    mapping={old:new for new,old in enumerate(order)} if len(order)<=1 else {new:old for new,old in enumerate(order)}\n    storage=[records[old] for old in order]\n    chain=list(range(len(order)))\n    updated=[mapping.get(c) if c is not None else None for c in cursors]\n    version=epoch+1\n    freed=sorted(set(range(len(records)))-set(order))\n    count=len(order)\n    return [storage,chain,updated,mapping,version,freed,count]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncheck('0', solve([[N,None,N+1,N+2],[3,0,2],[0,3,None],2]), {1: [[3, 1, 2], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 2: [[4, 2, 3], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 3: [[5, 3, 4], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 4: [[6, 4, 5], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 5: [[7, 5, 6], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3]}[N])\ncheck('1', solve([[None,N,None],[1],[1,None],0]), {1: [[1], [0], [0, None], {1: 0}, 1, [0, 2], 1], 2: [[2], [0], [0, None], {1: 0}, 1, [0, 2], 1], 3: [[3], [0], [0, None], {1: 0}, 1, [0, 2], 1], 4: [[4], [0], [0, None], {1: 0}, 1, [0, 2], 1], 5: [[5], [0], [0, None], {1: 0}, 1, [0, 2], 1]}[N])\ncheck('2', solve([[N,N+1,N+2],[2,1,0],[0,1,2],4]), {1: [[3, 2, 1], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 2: [[4, 3, 2], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 3: [[5, 4, 3], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 4: [[6, 5, 4], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 5: [[7, 6, 5], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3]}[N])\ncheck('3', solve([[],[],[None],1]), {1: [[], [], [None], {}, 2, [], 0], 2: [[], [], [None], {}, 2, [], 0], 3: [[], [], [None], {}, 2, [], 0], 4: [[], [], [None], {}, 2, [], 0], 5: [[], [], [None], {}, 2, [], 0]}[N])\ncheck('4', solve([[N,N+1],[0,1],[],3]), {1: [[1, 2], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 2: [[2, 3], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 3: [[3, 4], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 4: [[4, 5], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 5: [[5, 6], [0, 1], [], {0: 0, 1: 1}, 4, [], 2]}[N])\ncheck('5', solve([[None,N,None,N+1,None],[3,1],[3,1,None],5]), {1: [[2, 1], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 2: [[3, 2], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 3: [[4, 3], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 4: [[5, 4], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 5: [[6, 5], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2]}[N])\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"a33b233163e87df7a01419b33e5868a455e4410d9fed18f5788cdb8b5c92b200","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    records,order,cursors,epoch=x\n    mapping={new:old for new,old in enumerate(order)}\n    storage=[records[old] for old in order]\n    chain=list(range(len(order)))\n    updated=[mapping.get(c) if c is not None else None for c in cursors]\n    version=epoch+1\n    freed=sorted(set(range(len(records)))-set(order))\n    count=len(order)\n    return [storage,chain,updated,mapping,version,freed,count]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncheck('0', solve([[N,None,N+1,N+2],[3,0,2],[0,3,None],2]), {1: [[3, 1, 2], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 2: [[4, 2, 3], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 3: [[5, 3, 4], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 4: [[6, 4, 5], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 5: [[7, 5, 6], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3]}[N])\ncheck('1', solve([[None,N,None],[1],[1,None],0]), {1: [[1], [0], [0, None], {1: 0}, 1, [0, 2], 1], 2: [[2], [0], [0, None], {1: 0}, 1, [0, 2], 1], 3: [[3], [0], [0, None], {1: 0}, 1, [0, 2], 1], 4: [[4], [0], [0, None], {1: 0}, 1, [0, 2], 1], 5: [[5], [0], [0, None], {1: 0}, 1, [0, 2], 1]}[N])\ncheck('2', solve([[N,N+1,N+2],[2,1,0],[0,1,2],4]), {1: [[3, 2, 1], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 2: [[4, 3, 2], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 3: [[5, 4, 3], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 4: [[6, 5, 4], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 5: [[7, 6, 5], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3]}[N])\ncheck('3', solve([[],[],[None],1]), {1: [[], [], [None], {}, 2, [], 0], 2: [[], [], [None], {}, 2, [], 0], 3: [[], [], [None], {}, 2, [], 0], 4: [[], [], [None], {}, 2, [], 0], 5: [[], [], [None], {}, 2, [], 0]}[N])\ncheck('4', solve([[N,N+1],[0,1],[],3]), {1: [[1, 2], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 2: [[2, 3], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 3: [[3, 4], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 4: [[4, 5], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 5: [[5, 6], [0, 1], [], {0: 0, 1: 1}, 4, [], 2]}[N])\ncheck('5', solve([[None,N,None,N+1,None],[3,1],[3,1,None],5]), {1: [[2, 1], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 2: [[3, 2], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 3: [[4, 3], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 4: [[5, 4], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 5: [[6, 5], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2]}[N])\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"Offline finite deterministic model; no claim of production implementation or concurrent memory-model conformance. 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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"s3-bounded-deques-arena-compaction-relocation-direction","generated_at":"2026-09-29T14:44:38.467666+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Controlled bounded deque implementation model with explicit storage and lifecycle observations.","root_cause":"Deque compaction builds the inverse relocation table.","sha256":"f29b48d624c503b53657259ea5eb184e88062eb3fbdfb124558c8cb362d124c4","title":"Deque compaction builds the inverse relocation table · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verified":true,"visibility":"public","verification":{"attempt":{"elapsed_ms":43.796,"exit_code":1,"observations":[{"actual":[[3,1,2],[0,1,2],[3,null,null],{"0":3,"1":0,"2":2},3,[1],3],"check":"0","expected":[[3,1,2],[0,1,2],[1,0,null],{"0":1,"2":2,"3":0},3,[1],3],"passed":false},{"actual":[[1],[0],[0,null],{"1":0},1,[0,2],1],"check":"1","expected":[[1],[0],[0,null],{"1":0},1,[0,2],1],"passed":true},{"actual":[[3,2,1],[0,1,2],[2,1,0],{"0":2,"1":1,"2":0},5,[],3],"check":"2","expected":[[3,2,1],[0,1,2],[2,1,0],{"0":2,"1":1,"2":0},5,[],3],"passed":true},{"actual":[[],[],[null],{},2,[],0],"check":"3","expected":[[],[],[null],{},2,[],0],"passed":true},{"actual":[[1,2],[0,1],[],{"0":0,"1":1},4,[],2],"check":"4","expected":[[1,2],[0,1],[],{"0":0,"1":1},4,[],2],"passed":true},{"actual":[[2,1],[0,1],[null,1,null],{"0":3,"1":1},6,[0,2,4],2],"check":"5","expected":[[2,1],[0,1],[0,1,null],{"1":1,"3":0},6,[0,2,4],2],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"0\", \"actual\": [[3, 1, 2], [0, 1, 2], [3, null, null], {\"0\": 3, \"1\": 0, \"2\": 2}, 3, [1], 3], \"expected\": [[3, 1, 2], [0, 1, 2], [1, 0, null], {\"3\": 0, \"0\": 1, \"2\": 2}, 3, [1], 3], \"passed\": false}, {\"check\": \"1\", \"actual\": [[1], [0], [0, null], {\"1\": 0}, 1, [0, 2], 1], \"expected\": [[1], [0], [0, null], {\"1\": 0}, 1, [0, 2], 1], \"passed\": true}, {\"check\": \"2\", \"actual\": [[3, 2, 1], [0, 1, 2], [2, 1, 0], {\"0\": 2, \"1\": 1, \"2\": 0}, 5, [], 3], \"expected\": [[3, 2, 1], [0, 1, 2], [2, 1, 0], {\"2\": 0, \"1\": 1, \"0\": 2}, 5, [], 3], \"passed\": true}, {\"check\": \"3\", \"actual\": [[], [], [null], {}, 2, [], 0], \"expected\": [[], [], [null], {}, 2, [], 0], \"passed\": true}, {\"check\": \"4\", \"actual\": [[1, 2], [0, 1], [], {\"0\": 0, \"1\": 1}, 4, [], 2], \"expected\": [[1, 2], [0, 1], [], {\"0\": 0, \"1\": 1}, 4, [], 2], \"passed\": true}, {\"check\": \"5\", \"actual\": [[2, 1], [0, 1], [null, 1, null], {\"0\": 3, \"1\": 1}, 6, [0, 2, 4], 2], \"expected\": [[2, 1], [0, 1], [0, 1, null], {\"3\": 0, \"1\": 1}, 6, [0, 2, 4], 2], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":41.372,"exit_code":1,"observations":[{"actual":[[3,1,2],[0,1,2],[3,null,null],{"0":3,"1":0,"2":2},3,[1],3],"check":"0","expected":[[3,1,2],[0,1,2],[1,0,null],{"0":1,"2":2,"3":0},3,[1],3],"passed":false},{"actual":[[1],[0],[null,null],{"0":1},1,[0,2],1],"check":"1","expected":[[1],[0],[0,null],{"1":0},1,[0,2],1],"passed":false},{"actual":[[3,2,1],[0,1,2],[2,1,0],{"0":2,"1":1,"2":0},5,[],3],"check":"2","expected":[[3,2,1],[0,1,2],[2,1,0],{"0":2,"1":1,"2":0},5,[],3],"passed":true},{"actual":[[],[],[null],{},2,[],0],"check":"3","expected":[[],[],[null],{},2,[],0],"passed":true},{"actual":[[1,2],[0,1],[],{"0":0,"1":1},4,[],2],"check":"4","expected":[[1,2],[0,1],[],{"0":0,"1":1},4,[],2],"passed":true},{"actual":[[2,1],[0,1],[null,1,null],{"0":3,"1":1},6,[0,2,4],2],"check":"5","expected":[[2,1],[0,1],[0,1,null],{"1":1,"3":0},6,[0,2,4],2],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"0\", \"actual\": [[3, 1, 2], [0, 1, 2], [3, null, null], {\"0\": 3, \"1\": 0, \"2\": 2}, 3, [1], 3], \"expected\": [[3, 1, 2], [0, 1, 2], [1, 0, null], {\"3\": 0, \"0\": 1, \"2\": 2}, 3, [1], 3], \"passed\": false}, {\"check\": \"1\", \"actual\": [[1], [0], [null, null], {\"0\": 1}, 1, [0, 2], 1], \"expected\": [[1], [0], [0, null], {\"1\": 0}, 1, [0, 2], 1], \"passed\": false}, {\"check\": \"2\", \"actual\": [[3, 2, 1], [0, 1, 2], [2, 1, 0], {\"0\": 2, \"1\": 1, \"2\": 0}, 5, [], 3], \"expected\": [[3, 2, 1], [0, 1, 2], [2, 1, 0], {\"2\": 0, \"1\": 1, \"0\": 2}, 5, [], 3], \"passed\": true}, {\"check\": \"3\", \"actual\": [[], [], [null], {}, 2, [], 0], \"expected\": [[], [], [null], {}, 2, [], 0], \"passed\": true}, {\"check\": \"4\", \"actual\": [[1, 2], [0, 1], [], {\"0\": 0, \"1\": 1}, 4, [], 2], \"expected\": [[1, 2], [0, 1], [], {\"0\": 0, \"1\": 1}, 4, [], 2], \"passed\": true}, {\"check\": \"5\", \"actual\": [[2, 1], [0, 1], [null, 1, null], {\"0\": 3, \"1\": 1}, 6, [0, 2, 4], 2], \"expected\": [[2, 1], [0, 1], [0, 1, null], {\"3\": 0, \"1\": 1}, 6, [0, 2, 4], 2], \"passed\": false}], \"passed\": false}\n"}},"member_only":{"stages":["fixed"],"fields":["implementations.fixed","verification.fixed","harness","repair"],"note":"The verified repair, its recorded checks, the repair description, and the scoring harness are available to members."}}