FA-90701 / Garbage collector invariants / Open access
Block offset table: first object in the card returned even when it starts after the address · case 01
Addresses at the beginning of a card are attributed to the next object.
ROOT CAUSE
When the card's first object starts beyond the query, that object is returned instead of searching the previous card.
VERIFIED REPAIR
Move to the previous card and resolve from there.
Unsuccessful approach: Returning no owner abandons addresses that belong to an object from an earlier card.
Case contract
A contiguous heap of [start, size] objects is covered by cards of the given size. For each card the table stores the offset of the first object that starts inside the card; a card with no object start that is covered by an object from card c stores -(k - c), a direct back-skip to that card. To find the object containing address q: from q's card follow back-skips; if the card's first start lies after q, move to the previous card; then walk objects forward until one contains q (an entry that does not land on an object start yields corrupt-table). Return the table and the owner start for each query.
Why this case matters
Card scanning needs to locate object starts quickly; a stale or wrong table misparses the heap.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(objs, card, heap_end, queries):
size_of = {s: z for s, z in objs}
ncards = (heap_end + card - 1) // card
table = [None] * ncards
for start, size in sorted(objs):
c = start // card
if table[c] is None or table[c] < 0:
table[c] = start - c * card
last = (start + size - 1) // card
for k in range(c + 1, min(last, ncards - 1) + 1):
if table[k] is None:
table[k] = -(k - c)
def owner(q):
c = q // card
while c >= 0:
e = table[c]
if e is None:
return None
if e < 0:
c += e
continue
a = c * card + e
if a not in size_of:
return 'corrupt-table'
if a > q:
return a
while a + size_of[a] <= q:
a += size_of[a]
if a not in size_of:
return None
return a
return None
return {'table': table, 'owners': [owner(q) for q in queries]}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: owners across spanning objects',
([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),
{'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
('addresses just before a card-internal start',
([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
64,
472,
[47, 147, 167, 367, 391, 407]),
{'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
('first address of every card',
([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
64,
472,
[0, 64, 128, 192, 256, 320, 384, 448]),
{'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
('object ends and starts',
([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
64,
472,
[147, 148, 168, 391, 408]),
{'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
('smaller cards',
([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),
{'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
('control: single object heap',
([[0, 264]], 64, 264, [0, 100, 255]),
{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
[('regression: owners across spanning objects',
([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),
{'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
('addresses just before a card-internal start',
([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
64,
480,
[55, 155, 175, 375, 399, 415]),
{'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
('first address of every card',
([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
64,
480,
[0, 64, 128, 192, 256, 320, 384, 448]),
{'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
('object ends and starts',
([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
64,
480,
[155, 156, 176, 399, 416]),
{'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
('smaller cards',
([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),
{'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),
('control: single object heap',
([[0, 272]], 64, 272, [0, 100, 255]),
{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
[('regression: owners across spanning objects',
([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),
{'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
('addresses just before a card-internal start',
([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
64,
488,
[63, 163, 183, 383, 407, 423]),
{'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
('first address of every card',
([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
64,
488,
[0, 64, 128, 192, 256, 320, 384, 448]),
{'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
('object ends and starts',
([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
64,
488,
[163, 164, 184, 407, 424]),
{'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
('smaller cards',
([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),
{'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),
('control: single object heap',
([[0, 280]], 64, 280, [0, 100, 255]),
{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
[('regression: owners across spanning objects',
([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),
{'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
('addresses just before a card-internal start',
([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
64,
496,
[71, 171, 191, 391, 415, 431]),
{'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
('first address of every card',
([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
64,
496,
[0, 64, 128, 192, 256, 320, 384, 448]),
{'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
('object ends and starts',
([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
64,
496,
[171, 172, 192, 415, 432]),
{'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
('smaller cards',
([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),
{'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),
('control: single object heap',
([[0, 288]], 64, 288, [0, 100, 255]),
{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
[('regression: owners across spanning objects',
([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),
{'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
('addresses just before a card-internal start',
([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
64,
504,
[79, 179, 199, 399, 423, 439]),
{'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
('first address of every card',
([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
64,
504,
[0, 64, 128, 192, 256, 320, 384, 448]),
{'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
('object ends and starts',
([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
64,
504,
[179, 180, 200, 423, 440]),
{'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
('smaller cards',
([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),
{'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
('control: single object heap',
([[0, 296]], 64, 296, [0, 100, 255]),
{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]
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: owners across spanning objects | {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | Passed |
| addresses just before a card-internal start | {'owners': [0, 148, 148, 368, 392, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | Failed |
| first address of every card | {'owners': [0, 48, 148, 168, 168, 368, 392, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | Failed |
| object ends and starts | {'owners': [148, 148, 168, 392, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | Failed |
| smaller cards | {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]} | {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]} | Passed |
| control: single object heap | {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]} | {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]} | Passed |
SHA-256 / 72538ea4848a2a6da8fe02324943e7d937ff73bf7d2e30da399310b40fa5f5ba
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(objs, card, heap_end, queries):
size_of = {s: z for s, z in objs}
ncards = (heap_end + card - 1) // card
table = [None] * ncards
for start, size in sorted(objs):
c = start // card
if table[c] is None or table[c] < 0:
table[c] = start - c * card
last = (start + size - 1) // card
for k in range(c + 1, min(last, ncards - 1) + 1):
if table[k] is None:
table[k] = -(k - c)
def owner(q):
c = q // card
while c >= 0:
e = table[c]
if e is None:
return None
if e < 0:
c += e
continue
a = c * card + e
if a not in size_of:
return 'corrupt-table'
if a > q:
return None
while a + size_of[a] <= q:
a += size_of[a]
if a not in size_of:
return None
return a
return None
return {'table': table, 'owners': [owner(q) for q in queries]}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: owners across spanning objects',
([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),
{'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
('addresses just before a card-internal start',
([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
64,
472,
[47, 147, 167, 367, 391, 407]),
{'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
('first address of every card',
([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
64,
472,
[0, 64, 128, 192, 256, 320, 384, 448]),
{'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
('object ends and starts',
([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
64,
472,
[147, 148, 168, 391, 408]),
{'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
('smaller cards',
([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),
{'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
('control: single object heap',
([[0, 264]], 64, 264, [0, 100, 255]),
{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
[('regression: owners across spanning objects',
([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),
{'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
('addresses just before a card-internal start',
([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
64,
480,
[55, 155, 175, 375, 399, 415]),
{'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
('first address of every card',
([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
64,
480,
[0, 64, 128, 192, 256, 320, 384, 448]),
{'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
('object ends and starts',
([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
64,
480,
[155, 156, 176, 399, 416]),
{'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
('smaller cards',
([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),
{'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),
('control: single object heap',
([[0, 272]], 64, 272, [0, 100, 255]),
{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
[('regression: owners across spanning objects',
([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),
{'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
('addresses just before a card-internal start',
([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
64,
488,
[63, 163, 183, 383, 407, 423]),
{'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
('first address of every card',
([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
64,
488,
[0, 64, 128, 192, 256, 320, 384, 448]),
{'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
('object ends and starts',
([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
64,
488,
[163, 164, 184, 407, 424]),
{'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
('smaller cards',
([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),
{'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),
('control: single object heap',
([[0, 280]], 64, 280, [0, 100, 255]),
{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
[('regression: owners across spanning objects',
([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),
{'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
('addresses just before a card-internal start',
([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
64,
496,
[71, 171, 191, 391, 415, 431]),
{'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
('first address of every card',
([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
64,
496,
[0, 64, 128, 192, 256, 320, 384, 448]),
{'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
('object ends and starts',
([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
64,
496,
[171, 172, 192, 415, 432]),
{'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
('smaller cards',
([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),
{'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),
('control: single object heap',
([[0, 288]], 64, 288, [0, 100, 255]),
{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
[('regression: owners across spanning objects',
([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),
{'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
('addresses just before a card-internal start',
([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
64,
504,
[79, 179, 199, 399, 423, 439]),
{'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
('first address of every card',
([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
64,
504,
[0, 64, 128, 192, 256, 320, 384, 448]),
{'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
('object ends and starts',
([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
64,
504,
[179, 180, 200, 423, 440]),
{'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
('smaller cards',
([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),
{'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
('control: single object heap',
([[0, 296]], 64, 296, [0, 100, 255]),
{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]
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: owners across spanning objects | {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | Passed |
| addresses just before a card-internal start | {'owners': [0, None, 148, None, None, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | Failed |
| first address of every card | {'owners': [0, 48, None, 168, 168, None, None, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | Failed |
| object ends and starts | {'owners': [None, 148, 168, None, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | Failed |
| smaller cards | {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]} | {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]} | Passed |
| control: single object heap | {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]} | {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]} | Passed |
SHA-256 / e6a64f879561cd3723bad06479de83e63ff7276af9e6dec8ba5caaab7d05bdea
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(objs, card, heap_end, queries):
size_of = {s: z for s, z in objs}
ncards = (heap_end + card - 1) // card
table = [None] * ncards
for start, size in sorted(objs):
c = start // card
if table[c] is None or table[c] < 0:
table[c] = start - c * card
last = (start + size - 1) // card
for k in range(c + 1, min(last, ncards - 1) + 1):
if table[k] is None:
table[k] = -(k - c)
def owner(q):
c = q // card
while c >= 0:
e = table[c]
if e is None:
return None
if e < 0:
c += e
continue
a = c * card + e
if a not in size_of:
return 'corrupt-table'
if a > q:
c -= 1
continue
while a + size_of[a] <= q:
a += size_of[a]
if a not in size_of:
return None
return a
return None
return {'table': table, 'owners': [owner(q) for q in queries]}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: owners across spanning objects',
([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),
{'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
('addresses just before a card-internal start',
([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
64,
472,
[47, 147, 167, 367, 391, 407]),
{'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
('first address of every card',
([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
64,
472,
[0, 64, 128, 192, 256, 320, 384, 448]),
{'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
('object ends and starts',
([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
64,
472,
[147, 148, 168, 391, 408]),
{'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
('smaller cards',
([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),
{'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
('control: single object heap',
([[0, 264]], 64, 264, [0, 100, 255]),
{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
[('regression: owners across spanning objects',
([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),
{'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
('addresses just before a card-internal start',
([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
64,
480,
[55, 155, 175, 375, 399, 415]),
{'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
('first address of every card',
([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
64,
480,
[0, 64, 128, 192, 256, 320, 384, 448]),
{'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
('object ends and starts',
([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
64,
480,
[155, 156, 176, 399, 416]),
{'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
('smaller cards',
([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),
{'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),
('control: single object heap',
([[0, 272]], 64, 272, [0, 100, 255]),
{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
[('regression: owners across spanning objects',
([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),
{'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
('addresses just before a card-internal start',
([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
64,
488,
[63, 163, 183, 383, 407, 423]),
{'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
('first address of every card',
([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
64,
488,
[0, 64, 128, 192, 256, 320, 384, 448]),
{'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
('object ends and starts',
([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
64,
488,
[163, 164, 184, 407, 424]),
{'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
('smaller cards',
([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),
{'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),
('control: single object heap',
([[0, 280]], 64, 280, [0, 100, 255]),
{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
[('regression: owners across spanning objects',
([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),
{'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
('addresses just before a card-internal start',
([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
64,
496,
[71, 171, 191, 391, 415, 431]),
{'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
('first address of every card',
([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
64,
496,
[0, 64, 128, 192, 256, 320, 384, 448]),
{'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
('object ends and starts',
([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
64,
496,
[171, 172, 192, 415, 432]),
{'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
('smaller cards',
([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),
{'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),
('control: single object heap',
([[0, 288]], 64, 288, [0, 100, 255]),
{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
[('regression: owners across spanning objects',
([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),
{'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
('addresses just before a card-internal start',
([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
64,
504,
[79, 179, 199, 399, 423, 439]),
{'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
('first address of every card',
([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
64,
504,
[0, 64, 128, 192, 256, 320, 384, 448]),
{'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
('object ends and starts',
([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
64,
504,
[179, 180, 200, 423, 440]),
{'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
('smaller cards',
([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),
{'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
('control: single object heap',
([[0, 296]], 64, 296, [0, 100, 255]),
{'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]
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: owners across spanning objects | {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | Passed |
| addresses just before a card-internal start | {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | Passed |
| first address of every card | {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | Passed |
| object ends and starts | {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]} | Passed |
| smaller cards | {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]} | {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]} | Passed |
| control: single object heap | {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]} | {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]} | Passed |
SHA-256 / 429b796ebe6a29dc46c0d23387dc8dedec0954e5c693f7ebd64e4beef84bcdce
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:29.099090+00:00.
Case digest / 32ff2fcb98c7c7b29e3d56d8d9ddd5b390f0dcf9a5798bb7fee04dfffb92ae32