FA-90586 / Garbage collector invariants / Open access
Conservative scan: exact start pointers resolve to the previous object · case 01
References to an object's first word pin the neighbouring object or nothing.
ROOT CAUSE
bisect_left places an exact start after the previous object.
VERIFIED REPAIR
Use the last object whose start is <= the address.
Unsuccessful approach: Using the insertion index directly resolves interior addresses to the next object.
Case 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.
Why this case matters
Conservative collectors must neither miss real references nor pin unrelated or free memory.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, words, interior):
starts = sorted(o[0] for o in objs)
size_of = {o[0]: o[1] for o in objs}
alloc = {o[0]: o[2] for o in objs}
lo = min(starts) if starts else 0
hi = max(s + size_of[s] for s in starts) if starts else 0
found = set()
for w in words:
if w & 7 != 3:
continue
a = w - 3
if not (lo <= a < hi):
continue
i = bisect.bisect_left(starts, a) - 1
s = starts[i]
if not alloc[s]:
continue
if a == s or (interior and a < s + size_of[s]):
found.add(s)
return sorted(found)
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: tagged start pointers only',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),
[320, 352]),
('interior pointers when allowed',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),
[320, 352, 416]),
('interior pointer rejected when not allowed',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),
[]),
('one-past-the-end pointer into a gap',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),
[]),
('pointers to a free block',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),
[]),
('pointer exactly at a later object start',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),
[416]),
('control: untagged words ignored',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),
[])],
[('regression: tagged start pointers only',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),
[576, 608]),
('interior pointers when allowed',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),
[576, 608, 672]),
('interior pointer rejected when not allowed',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),
[]),
('one-past-the-end pointer into a gap',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),
[]),
('pointers to a free block',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),
[]),
('pointer exactly at a later object start',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),
[672]),
('control: untagged words ignored',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),
[])],
[('regression: tagged start pointers only',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),
[832, 864]),
('interior pointers when allowed',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),
[832, 864, 928]),
('interior pointer rejected when not allowed',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),
[]),
('one-past-the-end pointer into a gap',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),
[]),
('pointers to a free block',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),
[]),
('pointer exactly at a later object start',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),
[928]),
('control: untagged words ignored',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),
[])],
[('regression: tagged start pointers only',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],
[1091, 1123, 1090, 1131],
False),
[1088, 1120]),
('interior pointers when allowed',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),
[1088, 1120, 1184]),
('interior pointer rejected when not allowed',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),
[]),
('one-past-the-end pointer into a gap',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),
[]),
('pointers to a free block',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),
[]),
('pointer exactly at a later object start',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),
[1184]),
('control: untagged words ignored',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),
[])],
[('regression: tagged start pointers only',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],
[1347, 1379, 1346, 1387],
False),
[1344, 1376]),
('interior pointers when allowed',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),
[1344, 1376, 1440]),
('interior pointer rejected when not allowed',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),
[]),
('one-past-the-end pointer into a gap',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),
[]),
('pointers to a free block',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),
[]),
('pointer exactly at a later object start',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),
[1440]),
('control: untagged words ignored',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),
[])]]
for label, args, expected in cases[N - 1]:
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 |
|---|---|---|---|
| regression: tagged start pointers only | [] | [320, 352] | Failed |
| interior pointers when allowed | [320, 352, 416] | [320, 352, 416] | Passed |
| interior pointer rejected when not allowed | [] | [] | Passed |
| one-past-the-end pointer into a gap | [] | [] | Passed |
| pointers to a free block | [] | [] | Passed |
| pointer exactly at a later object start | [] | [416] | Failed |
| control: untagged words ignored | [] | [] | Passed |
SHA-256 / f6bde441fa566aed097cf39430df4a9b7a1388aba1a12793505d31eb5958ac33
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, words, interior):
starts = sorted(o[0] for o in objs)
size_of = {o[0]: o[1] for o in objs}
alloc = {o[0]: o[2] for o in objs}
lo = min(starts) if starts else 0
hi = max(s + size_of[s] for s in starts) if starts else 0
found = set()
for w in words:
if w & 7 != 3:
continue
a = w - 3
if not (lo <= a < hi):
continue
i = min(bisect.bisect_left(starts, a), len(starts) - 1)
s = starts[i]
if not alloc[s]:
continue
if a == s or (interior and a < s + size_of[s]):
found.add(s)
return sorted(found)
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: tagged start pointers only',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),
[320, 352]),
('interior pointers when allowed',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),
[320, 352, 416]),
('interior pointer rejected when not allowed',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),
[]),
('one-past-the-end pointer into a gap',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),
[]),
('pointers to a free block',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),
[]),
('pointer exactly at a later object start',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),
[416]),
('control: untagged words ignored',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),
[])],
[('regression: tagged start pointers only',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),
[576, 608]),
('interior pointers when allowed',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),
[576, 608, 672]),
('interior pointer rejected when not allowed',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),
[]),
('one-past-the-end pointer into a gap',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),
[]),
('pointers to a free block',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),
[]),
('pointer exactly at a later object start',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),
[672]),
('control: untagged words ignored',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),
[])],
[('regression: tagged start pointers only',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),
[832, 864]),
('interior pointers when allowed',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),
[832, 864, 928]),
('interior pointer rejected when not allowed',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),
[]),
('one-past-the-end pointer into a gap',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),
[]),
('pointers to a free block',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),
[]),
('pointer exactly at a later object start',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),
[928]),
('control: untagged words ignored',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),
[])],
[('regression: tagged start pointers only',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],
[1091, 1123, 1090, 1131],
False),
[1088, 1120]),
('interior pointers when allowed',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),
[1088, 1120, 1184]),
('interior pointer rejected when not allowed',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),
[]),
('one-past-the-end pointer into a gap',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),
[]),
('pointers to a free block',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),
[]),
('pointer exactly at a later object start',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),
[1184]),
('control: untagged words ignored',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),
[])],
[('regression: tagged start pointers only',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],
[1347, 1379, 1346, 1387],
False),
[1344, 1376]),
('interior pointers when allowed',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),
[1344, 1376, 1440]),
('interior pointer rejected when not allowed',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),
[]),
('one-past-the-end pointer into a gap',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),
[]),
('pointers to a free block',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),
[]),
('pointer exactly at a later object start',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),
[1440]),
('control: untagged words ignored',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),
[])]]
for label, args, expected in cases[N - 1]:
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 |
|---|---|---|---|
| regression: tagged start pointers only | [320, 352] | [320, 352] | Passed |
| interior pointers when allowed | [352, 416] | [320, 352, 416] | Failed |
| interior pointer rejected when not allowed | [] | [] | Passed |
| one-past-the-end pointer into a gap | [416] | [] | Failed |
| pointers to a free block | [416] | [] | Failed |
| pointer exactly at a later object start | [416] | [416] | Passed |
| control: untagged words ignored | [] | [] | Passed |
SHA-256 / ac0dd69e61876c46ee0365bff6a274ac8af79dc0f855e0b1403804f245de04b3
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, words, interior):
starts = sorted(o[0] for o in objs)
size_of = {o[0]: o[1] for o in objs}
alloc = {o[0]: o[2] for o in objs}
lo = min(starts) if starts else 0
hi = max(s + size_of[s] for s in starts) if starts else 0
found = set()
for w in words:
if w & 7 != 3:
continue
a = w - 3
if not (lo <= a < hi):
continue
i = bisect.bisect_right(starts, a) - 1
s = starts[i]
if not alloc[s]:
continue
if a == s or (interior and a < s + size_of[s]):
found.add(s)
return sorted(found)
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: tagged start pointers only',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),
[320, 352]),
('interior pointers when allowed',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),
[320, 352, 416]),
('interior pointer rejected when not allowed',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),
[]),
('one-past-the-end pointer into a gap',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),
[]),
('pointers to a free block',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),
[]),
('pointer exactly at a later object start',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),
[416]),
('control: untagged words ignored',
([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),
[])],
[('regression: tagged start pointers only',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),
[576, 608]),
('interior pointers when allowed',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),
[576, 608, 672]),
('interior pointer rejected when not allowed',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),
[]),
('one-past-the-end pointer into a gap',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),
[]),
('pointers to a free block',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),
[]),
('pointer exactly at a later object start',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),
[672]),
('control: untagged words ignored',
([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),
[])],
[('regression: tagged start pointers only',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),
[832, 864]),
('interior pointers when allowed',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),
[832, 864, 928]),
('interior pointer rejected when not allowed',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),
[]),
('one-past-the-end pointer into a gap',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),
[]),
('pointers to a free block',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),
[]),
('pointer exactly at a later object start',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),
[928]),
('control: untagged words ignored',
([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),
[])],
[('regression: tagged start pointers only',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],
[1091, 1123, 1090, 1131],
False),
[1088, 1120]),
('interior pointers when allowed',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),
[1088, 1120, 1184]),
('interior pointer rejected when not allowed',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),
[]),
('one-past-the-end pointer into a gap',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),
[]),
('pointers to a free block',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),
[]),
('pointer exactly at a later object start',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),
[1184]),
('control: untagged words ignored',
([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),
[])],
[('regression: tagged start pointers only',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],
[1347, 1379, 1346, 1387],
False),
[1344, 1376]),
('interior pointers when allowed',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),
[1344, 1376, 1440]),
('interior pointer rejected when not allowed',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),
[]),
('one-past-the-end pointer into a gap',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),
[]),
('pointers to a free block',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),
[]),
('pointer exactly at a later object start',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),
[1440]),
('control: untagged words ignored',
([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),
[])]]
for label, args, expected in cases[N - 1]:
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 |
|---|---|---|---|
| regression: tagged start pointers only | [320, 352] | [320, 352] | Passed |
| interior pointers when allowed | [320, 352, 416] | [320, 352, 416] | Passed |
| interior pointer rejected when not allowed | [] | [] | Passed |
| one-past-the-end pointer into a gap | [] | [] | Passed |
| pointers to a free block | [] | [] | Passed |
| pointer exactly at a later object start | [416] | [416] | Passed |
| control: untagged words ignored | [] | [] | Passed |
SHA-256 / 88c624baa790711c052bb22c1a40d1cd2a55316d728faa810ff124ef93b1a39d
Verification & scope
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.
Observations recorded using Python 3.12.14 at 2026-09-29T14:51:27.972006+00:00.
Case digest / ecd13b0dc0cbd849084e650dc8a2dbb2766bfe3eb34c0496ee9c1ea76b95b1aa