{"abstract":"Deque merge restarts the right suffix at the beginning.","category":"Bounded deques","checks":6,"contract":"Merge sorted deque runs by key, placing equal keys from the left run first and preserving each run order. Split the merged stream at output capacity.","evaluation_group":"s3-bounded-deques-merge-runs","failed_approach":"The partial repair still applies the incorrect transition to an admitted boundary or multi-element case.","family":"s3-bounded-deques-merge-runs-right-tail","id":"FA-46251","implementations":{"attempt":{"sha256":"606ddd52696d454dd39aed84318202b3336315219baa381ab1d29184595afbc3","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    a,b,cap=x\n    out=[]\n    i=j=0\n    while i<len(a) and j<len(b):\n        if a[i][0]<=b[j][0]:\n            out.append(a[i]);i+=1\n        else:\n            out.append(b[j]);j+=1\n    out.extend(a[i:])\n    out.extend(b[j:] if i==0 else b)\n    return [out[:cap],out[cap:]]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncheck('0', solve([[[1,N],[2,N+1]],[[1,N+2],[3,N+3]],3]), {1: [[[1, 1], [1, 3], [2, 2]], [[3, 4]]], 2: [[[1, 2], [1, 4], [2, 3]], [[3, 5]]], 3: [[[1, 3], [1, 5], [2, 4]], [[3, 6]]], 4: [[[1, 4], [1, 6], [2, 5]], [[3, 7]]], 5: [[[1, 5], [1, 7], [2, 6]], [[3, 8]]]}[N])\ncheck('1', solve([[[1,N]],[],2]), {1: [[[1, 1]], []], 2: [[[1, 2]], []], 3: [[[1, 3]], []], 4: [[[1, 4]], []], 5: [[[1, 5]], []]}[N])\ncheck('2', solve([[],[[1,N]],0]), {1: [[], [[1, 1]]], 2: [[], [[1, 2]]], 3: [[], [[1, 3]]], 4: [[], [[1, 4]]], 5: [[], [[1, 5]]]}[N])\ncheck('3', solve([[[1,N],[1,N+1]],[[1,N+2]],3]), {1: [[[1, 1], [1, 2], [1, 3]], []], 2: [[[1, 2], [1, 3], [1, 4]], []], 3: [[[1, 3], [1, 4], [1, 5]], []], 4: [[[1, 4], [1, 5], [1, 6]], []], 5: [[[1, 5], [1, 6], [1, 7]], []]}[N])\ncheck('4', solve([[[4,N]],[[1,N+1],[2,N+2]],4]), {1: [[[1, 2], [2, 3], [4, 1]], []], 2: [[[1, 3], [2, 4], [4, 2]], []], 3: [[[1, 4], [2, 5], [4, 3]], []], 4: [[[1, 5], [2, 6], [4, 4]], []], 5: [[[1, 6], [2, 7], [4, 5]], []]}[N])\ncheck('5', solve([[],[],2]), {1: [[], []], 2: [[], []], 3: [[], []], 4: [[], []], 5: [[], []]}[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":"b9e27e9ca0c0aaf92b22fd9db8a1e6faeb130e64a560a911403d0d52216e42c7","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    a,b,cap=x\n    out=[]\n    i=j=0\n    while i<len(a) and j<len(b):\n        if a[i][0]<=b[j][0]:\n            out.append(a[i]);i+=1\n        else:\n            out.append(b[j]);j+=1\n    out.extend(a[i:])\n    out.extend(b)\n    return [out[:cap],out[cap:]]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncheck('0', solve([[[1,N],[2,N+1]],[[1,N+2],[3,N+3]],3]), {1: [[[1, 1], [1, 3], [2, 2]], [[3, 4]]], 2: [[[1, 2], [1, 4], [2, 3]], [[3, 5]]], 3: [[[1, 3], [1, 5], [2, 4]], [[3, 6]]], 4: [[[1, 4], [1, 6], [2, 5]], [[3, 7]]], 5: [[[1, 5], [1, 7], [2, 6]], [[3, 8]]]}[N])\ncheck('1', solve([[[1,N]],[],2]), {1: [[[1, 1]], []], 2: [[[1, 2]], []], 3: [[[1, 3]], []], 4: [[[1, 4]], []], 5: [[[1, 5]], []]}[N])\ncheck('2', solve([[],[[1,N]],0]), {1: [[], [[1, 1]]], 2: [[], [[1, 2]]], 3: [[], [[1, 3]]], 4: [[], [[1, 4]]], 5: [[], [[1, 5]]]}[N])\ncheck('3', solve([[[1,N],[1,N+1]],[[1,N+2]],3]), {1: [[[1, 1], [1, 2], [1, 3]], []], 2: [[[1, 2], [1, 3], [1, 4]], []], 3: [[[1, 3], [1, 4], [1, 5]], []], 4: [[[1, 4], [1, 5], [1, 6]], []], 5: [[[1, 5], [1, 6], [1, 7]], []]}[N])\ncheck('4', solve([[[4,N]],[[1,N+1],[2,N+2]],4]), {1: [[[1, 2], [2, 3], [4, 1]], []], 2: [[[1, 3], [2, 4], [4, 2]], []], 3: [[[1, 4], [2, 5], [4, 3]], []], 4: [[[1, 5], [2, 6], [4, 4]], []], 5: [[[1, 6], [2, 7], [4, 5]], []]}[N])\ncheck('5', solve([[],[],2]), {1: [[], []], 2: [[], []], 3: [[], []], 4: [[], []], 5: [[], []]}[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"},"fixed":{"sha256":"29c5f698168933d5a694c57753f86162759032454083f9ea1c95002fa7e116db","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    a,b,cap=x\n    out=[]\n    i=j=0\n    while i<len(a) and j<len(b):\n        if a[i][0]<=b[j][0]:\n            out.append(a[i]);i+=1\n        else:\n            out.append(b[j]);j+=1\n    out.extend(a[i:])\n    out.extend(b[j:])\n    return [out[:cap],out[cap:]]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncheck('0', solve([[[1,N],[2,N+1]],[[1,N+2],[3,N+3]],3]), {1: [[[1, 1], [1, 3], [2, 2]], [[3, 4]]], 2: [[[1, 2], [1, 4], [2, 3]], [[3, 5]]], 3: [[[1, 3], [1, 5], [2, 4]], [[3, 6]]], 4: [[[1, 4], [1, 6], [2, 5]], [[3, 7]]], 5: [[[1, 5], [1, 7], [2, 6]], [[3, 8]]]}[N])\ncheck('1', solve([[[1,N]],[],2]), {1: [[[1, 1]], []], 2: [[[1, 2]], []], 3: [[[1, 3]], []], 4: [[[1, 4]], []], 5: [[[1, 5]], []]}[N])\ncheck('2', solve([[],[[1,N]],0]), {1: [[], [[1, 1]]], 2: [[], [[1, 2]]], 3: [[], [[1, 3]]], 4: [[], [[1, 4]]], 5: [[], [[1, 5]]]}[N])\ncheck('3', solve([[[1,N],[1,N+1]],[[1,N+2]],3]), {1: [[[1, 1], [1, 2], [1, 3]], []], 2: [[[1, 2], [1, 3], [1, 4]], []], 3: [[[1, 3], [1, 4], [1, 5]], []], 4: [[[1, 4], [1, 5], [1, 6]], []], 5: [[[1, 5], [1, 6], [1, 7]], []]}[N])\ncheck('4', solve([[[4,N]],[[1,N+1],[2,N+2]],4]), {1: [[[1, 2], [2, 3], [4, 1]], []], 2: [[[1, 3], [2, 4], [4, 2]], []], 3: [[[1, 4], [2, 5], [4, 3]], []], 4: [[[1, 5], [2, 6], [4, 4]], []], 5: [[[1, 6], [2, 7], [4, 5]], []]}[N])\ncheck('5', solve([[],[],2]), {1: [[], []], 2: [[], []], 3: [[], []], 4: [[], []], 5: [[], []]}[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-merge-runs-right-tail","generated_at":"2026-09-29T14:44:30.287663+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.","repair":"Restore the documented right tail invariant in merge-runs.","root_cause":"Deque merge restarts the right suffix at the beginning.","sha256":"7c582b014c196139588abe5f1cf5db06eef2a9df3c57fa1334c8ab014f24c144","title":"Deque merge restarts the right suffix at the beginning · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":40.692,"exit_code":1,"observations":[{"actual":[[[1,1],[1,3],[2,2]],[[1,3],[3,4]]],"check":"0","expected":[[[1,1],[1,3],[2,2]],[[3,4]]],"passed":false},{"actual":[[[1,1]],[]],"check":"1","expected":[[[1,1]],[]],"passed":true},{"actual":[[],[[1,1]]],"check":"2","expected":[[],[[1,1]]],"passed":true},{"actual":[[[1,1],[1,2],[1,3]],[]],"check":"3","expected":[[[1,1],[1,2],[1,3]],[]],"passed":true},{"actual":[[[1,2],[2,3],[4,1]],[]],"check":"4","expected":[[[1,2],[2,3],[4,1]],[]],"passed":true},{"actual":[[],[]],"check":"5","expected":[[],[]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"0\", \"actual\": [[[1, 1], [1, 3], [2, 2]], [[1, 3], [3, 4]]], \"expected\": [[[1, 1], [1, 3], [2, 2]], [[3, 4]]], \"passed\": false}, {\"check\": \"1\", \"actual\": [[[1, 1]], []], \"expected\": [[[1, 1]], []], \"passed\": true}, {\"check\": \"2\", \"actual\": [[], [[1, 1]]], \"expected\": [[], [[1, 1]]], \"passed\": true}, {\"check\": \"3\", \"actual\": [[[1, 1], [1, 2], [1, 3]], []], \"expected\": [[[1, 1], [1, 2], [1, 3]], []], \"passed\": true}, {\"check\": \"4\", \"actual\": [[[1, 2], [2, 3], [4, 1]], []], \"expected\": [[[1, 2], [2, 3], [4, 1]], []], \"passed\": true}, {\"check\": \"5\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":39.743,"exit_code":1,"observations":[{"actual":[[[1,1],[1,3],[2,2]],[[1,3],[3,4]]],"check":"0","expected":[[[1,1],[1,3],[2,2]],[[3,4]]],"passed":false},{"actual":[[[1,1]],[]],"check":"1","expected":[[[1,1]],[]],"passed":true},{"actual":[[],[[1,1]]],"check":"2","expected":[[],[[1,1]]],"passed":true},{"actual":[[[1,1],[1,2],[1,3]],[]],"check":"3","expected":[[[1,1],[1,2],[1,3]],[]],"passed":true},{"actual":[[[1,2],[2,3],[4,1],[1,2]],[[2,3]]],"check":"4","expected":[[[1,2],[2,3],[4,1]],[]],"passed":false},{"actual":[[],[]],"check":"5","expected":[[],[]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"0\", \"actual\": [[[1, 1], [1, 3], [2, 2]], [[1, 3], [3, 4]]], \"expected\": [[[1, 1], [1, 3], [2, 2]], [[3, 4]]], \"passed\": false}, {\"check\": \"1\", \"actual\": [[[1, 1]], []], \"expected\": [[[1, 1]], []], \"passed\": true}, {\"check\": \"2\", \"actual\": [[], [[1, 1]]], \"expected\": [[], [[1, 1]]], \"passed\": true}, {\"check\": \"3\", \"actual\": [[[1, 1], [1, 2], [1, 3]], []], \"expected\": [[[1, 1], [1, 2], [1, 3]], []], \"passed\": true}, {\"check\": \"4\", \"actual\": [[[1, 2], [2, 3], [4, 1], [1, 2]], [[2, 3]]], \"expected\": [[[1, 2], [2, 3], [4, 1]], []], \"passed\": false}, {\"check\": \"5\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":40.416,"exit_code":0,"observations":[{"actual":[[[1,1],[1,3],[2,2]],[[3,4]]],"check":"0","expected":[[[1,1],[1,3],[2,2]],[[3,4]]],"passed":true},{"actual":[[[1,1]],[]],"check":"1","expected":[[[1,1]],[]],"passed":true},{"actual":[[],[[1,1]]],"check":"2","expected":[[],[[1,1]]],"passed":true},{"actual":[[[1,1],[1,2],[1,3]],[]],"check":"3","expected":[[[1,1],[1,2],[1,3]],[]],"passed":true},{"actual":[[[1,2],[2,3],[4,1]],[]],"check":"4","expected":[[[1,2],[2,3],[4,1]],[]],"passed":true},{"actual":[[],[]],"check":"5","expected":[[],[]],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"0\", \"actual\": [[[1, 1], [1, 3], [2, 2]], [[3, 4]]], \"expected\": [[[1, 1], [1, 3], [2, 2]], [[3, 4]]], \"passed\": true}, {\"check\": \"1\", \"actual\": [[[1, 1]], []], \"expected\": [[[1, 1]], []], \"passed\": true}, {\"check\": \"2\", \"actual\": [[], [[1, 1]]], \"expected\": [[], [[1, 1]]], \"passed\": true}, {\"check\": \"3\", \"actual\": [[[1, 1], [1, 2], [1, 3]], []], \"expected\": [[[1, 1], [1, 2], [1, 3]], []], \"passed\": true}, {\"check\": \"4\", \"actual\": [[[1, 2], [2, 3], [4, 1]], []], \"expected\": [[[1, 2], [2, 3], [4, 1]], []], \"passed\": true}, {\"check\": \"5\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}