{"abstract":"References to an object's first word pin the neighbouring object or nothing.","category":"Garbage collector invariants","checks":7,"contract":"Conservative scanning of machine words. A word whose low three bits are 011 is a tagged heap pointer to address word - 3; all other words are immediates. objs are [start, size, allocated] in any order. A candidate address pins the allocated object whose start equals it, or, when interior pointers are enabled, the allocated object whose [start, start+size) contains it; addresses in gaps, in free blocks or outside the heap pin nothing. Return the sorted starts of pinned objects.","contract_signature":"objs, words, interior","evaluation_group":"w2-garbage-collector-invariants-conservative-root-scan","failed_approach":"Using the insertion index directly resolves interior addresses to the next object.","family":"w2-garbage-collector-invariants-conservative-root-scan-containing-object-search","id":"FA-90586","implementations":{"attempt":{"sha256":"ac0dd69e61876c46ee0365bff6a274ac8af79dc0f855e0b1403804f245de04b3","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport bisect\nN = 1\nobservations = []\ndef solve(objs, words, interior):\n    starts = sorted(o[0] for o in objs)\n    size_of = {o[0]: o[1] for o in objs}\n    alloc = {o[0]: o[2] for o in objs}\n    lo = min(starts) if starts else 0\n    hi = max(s + size_of[s] for s in starts) if starts else 0\n    found = set()\n    for w in words:\n        if w & 7 != 3:\n            continue\n        a = w - 3\n        if not (lo <= a < hi):\n            continue\n        i = min(bisect.bisect_left(starts, a), len(starts) - 1)\n        s = starts[i]\n        if not alloc[s]:\n            continue\n        if a == s or (interior and a < s + size_of[s]):\n            found.add(s)\n    return sorted(found)\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: tagged start pointers only',\n   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),\n   [320, 352]),\n  ('interior pointers when allowed',\n   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),\n   [320, 352, 416]),\n  ('interior pointer rejected when not allowed',\n   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),\n   []),\n  ('one-past-the-end pointer into a gap',\n   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),\n   []),\n  ('pointers to a free block',\n   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),\n   []),\n  ('pointer exactly at a later object start',\n   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),\n   [416]),\n  ('control: untagged words ignored',\n   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),\n   [])],\n [('regression: tagged start pointers only',\n   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),\n   [576, 608]),\n  ('interior pointers when allowed',\n   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),\n   [576, 608, 672]),\n  ('interior pointer rejected when not allowed',\n   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),\n   []),\n  ('one-past-the-end pointer into a gap',\n   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),\n   []),\n  ('pointers to a free block',\n   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),\n   []),\n  ('pointer exactly at a later object start',\n   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),\n   [672]),\n  ('control: untagged words ignored',\n   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),\n   [])],\n [('regression: tagged start pointers only',\n   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),\n   [832, 864]),\n  ('interior pointers when allowed',\n   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),\n   [832, 864, 928]),\n  ('interior pointer rejected when not allowed',\n   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),\n   []),\n  ('one-past-the-end pointer into a gap',\n   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),\n   []),\n  ('pointers to a free block',\n   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),\n   []),\n  ('pointer exactly at a later object start',\n   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),\n   [928]),\n  ('control: untagged words ignored',\n   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),\n   [])],\n [('regression: tagged start pointers only',\n   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],\n    [1091, 1123, 1090, 1131],\n    False),\n   [1088, 1120]),\n  ('interior pointers when allowed',\n   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),\n   [1088, 1120, 1184]),\n  ('interior pointer rejected when not allowed',\n   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),\n   []),\n  ('one-past-the-end pointer into a gap',\n   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),\n   []),\n  ('pointers to a free block',\n   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),\n   []),\n  ('pointer exactly at a later object start',\n   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),\n   [1184]),\n  ('control: untagged words ignored',\n   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),\n   [])],\n [('regression: tagged start pointers only',\n   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],\n    [1347, 1379, 1346, 1387],\n    False),\n   [1344, 1376]),\n  ('interior pointers when allowed',\n   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),\n   [1344, 1376, 1440]),\n  ('interior pointer rejected when not allowed',\n   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),\n   []),\n  ('one-past-the-end pointer into a gap',\n   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),\n   []),\n  ('pointers to a free block',\n   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),\n   []),\n  ('pointer exactly at a later object start',\n   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),\n   [1440]),\n  ('control: untagged words ignored',\n   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),\n   [])]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(*args), expected)\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":"f6bde441fa566aed097cf39430df4a9b7a1388aba1a12793505d31eb5958ac33","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport bisect\nN = 1\nobservations = []\ndef solve(objs, words, interior):\n    starts = sorted(o[0] for o in objs)\n    size_of = {o[0]: o[1] for o in objs}\n    alloc = {o[0]: o[2] for o in objs}\n    lo = min(starts) if starts else 0\n    hi = max(s + size_of[s] for s in starts) if starts else 0\n    found = set()\n    for w in words:\n        if w & 7 != 3:\n            continue\n        a = w - 3\n        if not (lo <= a < hi):\n            continue\n        i = bisect.bisect_left(starts, a) - 1\n        s = starts[i]\n        if not alloc[s]:\n            continue\n        if a == s or (interior and a < s + size_of[s]):\n            found.add(s)\n    return sorted(found)\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: tagged start pointers only',\n   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),\n   [320, 352]),\n  ('interior pointers when allowed',\n   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),\n   [320, 352, 416]),\n  ('interior pointer rejected when not allowed',\n   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),\n   []),\n  ('one-past-the-end pointer into a gap',\n   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),\n   []),\n  ('pointers to a free block',\n   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),\n   []),\n  ('pointer exactly at a later object start',\n   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),\n   [416]),\n  ('control: untagged words ignored',\n   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),\n   [])],\n [('regression: tagged start pointers only',\n   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),\n   [576, 608]),\n  ('interior pointers when allowed',\n   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),\n   [576, 608, 672]),\n  ('interior pointer rejected when not allowed',\n   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),\n   []),\n  ('one-past-the-end pointer into a gap',\n   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),\n   []),\n  ('pointers to a free block',\n   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),\n   []),\n  ('pointer exactly at a later object start',\n   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),\n   [672]),\n  ('control: untagged words ignored',\n   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),\n   [])],\n [('regression: tagged start pointers only',\n   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),\n   [832, 864]),\n  ('interior pointers when allowed',\n   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),\n   [832, 864, 928]),\n  ('interior pointer rejected when not allowed',\n   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),\n   []),\n  ('one-past-the-end pointer into a gap',\n   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),\n   []),\n  ('pointers to a free block',\n   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),\n   []),\n  ('pointer exactly at a later object start',\n   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),\n   [928]),\n  ('control: untagged words ignored',\n   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),\n   [])],\n [('regression: tagged start pointers only',\n   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],\n    [1091, 1123, 1090, 1131],\n    False),\n   [1088, 1120]),\n  ('interior pointers when allowed',\n   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),\n   [1088, 1120, 1184]),\n  ('interior pointer rejected when not allowed',\n   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),\n   []),\n  ('one-past-the-end pointer into a gap',\n   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),\n   []),\n  ('pointers to a free block',\n   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),\n   []),\n  ('pointer exactly at a later object start',\n   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),\n   [1184]),\n  ('control: untagged words ignored',\n   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),\n   [])],\n [('regression: tagged start pointers only',\n   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],\n    [1347, 1379, 1346, 1387],\n    False),\n   [1344, 1376]),\n  ('interior pointers when allowed',\n   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),\n   [1344, 1376, 1440]),\n  ('interior pointer rejected when not allowed',\n   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),\n   []),\n  ('one-past-the-end pointer into a gap',\n   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),\n   []),\n  ('pointers to a free block',\n   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),\n   []),\n  ('pointer exactly at a later object start',\n   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),\n   [1440]),\n  ('control: untagged words ignored',\n   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),\n   [])]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(*args), expected)\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":"A deterministic, bounded teaching model of one garbage-collector mechanism with stipulated rules; it is not a production collector and claims no conformance to any particular runtime. 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":"w2-garbage-collector-invariants-conservative-root-scan-containing-object-search","generated_at":"2026-09-29T14:51:28.144674+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Conservative collectors must neither miss real references nor pin unrelated or free memory.","root_cause":"bisect_left places an exact start after the previous object.","sha256":"61fde96b1c44592f70a2fbdad6018e30787f4ed355be6928ec514e59d90be658","title":"Conservative scan: exact start pointers resolve to the previous object · 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":42.254,"exit_code":1,"observations":[{"actual":[320,352],"check":"regression: tagged start pointers only","expected":[320,352],"passed":true},{"actual":[352,416],"check":"interior pointers when allowed","expected":[320,352,416],"passed":false},{"actual":[],"check":"interior pointer rejected when not allowed","expected":[],"passed":true},{"actual":[416],"check":"one-past-the-end pointer into a gap","expected":[],"passed":false},{"actual":[416],"check":"pointers to a free block","expected":[],"passed":false},{"actual":[416],"check":"pointer exactly at a later object start","expected":[416],"passed":true},{"actual":[],"check":"control: untagged words ignored","expected":[],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: tagged start pointers only\", \"actual\": [320, 352], \"expected\": [320, 352], \"passed\": true}, {\"check\": \"interior pointers when allowed\", \"actual\": [352, 416], \"expected\": [320, 352, 416], \"passed\": false}, {\"check\": \"interior pointer rejected when not allowed\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"one-past-the-end pointer into a gap\", \"actual\": [416], \"expected\": [], \"passed\": false}, {\"check\": \"pointers to a free block\", \"actual\": [416], \"expected\": [], \"passed\": false}, {\"check\": \"pointer exactly at a later object start\", \"actual\": [416], \"expected\": [416], \"passed\": true}, {\"check\": \"control: untagged words ignored\", \"actual\": [], \"expected\": [], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":38.783,"exit_code":1,"observations":[{"actual":[],"check":"regression: tagged start pointers only","expected":[320,352],"passed":false},{"actual":[320,352,416],"check":"interior pointers when allowed","expected":[320,352,416],"passed":true},{"actual":[],"check":"interior pointer rejected when not allowed","expected":[],"passed":true},{"actual":[],"check":"one-past-the-end pointer into a gap","expected":[],"passed":true},{"actual":[],"check":"pointers to a free block","expected":[],"passed":true},{"actual":[],"check":"pointer exactly at a later object start","expected":[416],"passed":false},{"actual":[],"check":"control: untagged words ignored","expected":[],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: tagged start pointers only\", \"actual\": [], \"expected\": [320, 352], \"passed\": false}, {\"check\": \"interior pointers when allowed\", \"actual\": [320, 352, 416], \"expected\": [320, 352, 416], \"passed\": true}, {\"check\": \"interior pointer rejected when not allowed\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"one-past-the-end pointer into a gap\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"pointers to a free block\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"pointer exactly at a later object start\", \"actual\": [], \"expected\": [416], \"passed\": false}, {\"check\": \"control: untagged words ignored\", \"actual\": [], \"expected\": [], \"passed\": true}], \"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."}}