FA-90576 / Garbage collector invariants / Open access
Conservative scan: one-past-the-end addresses pin the object · case 01
A pointer just beyond an object in a gap keeps that object pinned.
ROOT CAUSE
The containment test includes the end address.
VERIFIED REPAIR
An interior address must be strictly below start + size.
Unsuccessful approach: Testing against the heap end pins the preceding object for every gap address.
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_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 | [352] | [] | Failed |
| pointers to a free block | [] | [] | Passed |
| pointer exactly at a later object start | [416] | [416] | Passed |
| control: untagged words ignored | [] | [] | Passed |
SHA-256 / fba7b264129750f7da7ed2ebf9086e6a1c8837641a8f0f5d8d58b0c043bc76d6
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 = bisect.bisect_right(starts, a) - 1
s = starts[i]
if not alloc[s]:
continue
if a == s or (interior and a < hi):
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 | [352] | [] | Failed |
| pointers to a free block | [] | [] | Passed |
| pointer exactly at a later object start | [416] | [416] | Passed |
| control: untagged words ignored | [] | [] | Passed |
SHA-256 / 7f8bc7463ff0db7da7f678f47f7e72d867c5042b6f002d7c9bed9b2bfef2c07a
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.913028+00:00.
Case digest / c244b3ecddd9644ae8213226b3fa4436ccb0490ebaa806e6bcbae299961a55f9