FA-90676 / Garbage collector invariants / Open access
Mark parity: live objects marked with the previous epoch's parity · case 01
Every object reported live is swept as dead.
ROOT CAUSE
Marking uses the parity of the epoch that just ended.
VERIFIED REPAIR
Mark live objects with the parity of the new epoch.
Unsuccessful approach: A constant mark of 1 only works in odd epochs.
Case contract
Mark bits flip meaning every cycle: an object is live when its mark equals epoch % 2. Initially every object has mark 0 at epoch 0. gc live_ids: finish sweeping every unswept page, advance the epoch, set the mark of each listed live object to the new parity, and mark all pages unswept. alloc id page: sweep the page first if it is unswept, then create the object with the current parity. finish sweeps the remaining pages. Sweeping a page removes objects whose mark differs from the current parity and logs [page, removed]. Return the sweep log and surviving objects per page.
Why this case matters
Flipping mark polarity avoids clearing mark bits but makes sweep ordering and allocation colour critical.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(pages, events):
pages = {p: dict(v) for p, v in pages.items()}
epoch = 0
unswept = []
log = []
def sweep(p):
parity = epoch % 2
dead = sorted(o for o, m in pages[p].items() if m != parity)
for o in dead:
del pages[p][o]
log.append([p, dead])
unswept.remove(p)
for ev in events:
if ev[0] == 'gc':
while unswept:
sweep(unswept[0])
epoch += 1
for p in pages:
for o in pages[p]:
if o in ev[1]:
pages[p][o] = (epoch - 1) % 2
unswept = sorted(pages)
elif ev[0] == 'alloc':
if ev[2] in unswept:
sweep(ev[2])
pages[ev[2]][ev[1]] = epoch % 2
else:
while unswept:
sweep(unswept[0])
return {'log': log, 'pages': {str(p): sorted(v) for p, v in sorted(pages.items())}}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: lazy sweep before allocation',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['finish']]),
{'log': [[1, ['b1', 'c1']], [2, ['e1']]], 'pages': {'1': ['a1', 'x1'], '2': ['d1']}}),
('second cycle with an unswept page',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['gc', ['a1']], ['finish']]),
{'log': [[1, ['b1', 'c1']], [2, ['e1']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': []}}),
('allocation after sweeping dies next cycle',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['a1']], ['finish'], ['alloc', 'y1', 2], ['gc', ['a1']], ['finish']]),
{'log': [[1, ['b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, ['y1']]], 'pages': {'1': ['a1'], '2': []}}),
('allocation into an unswept page mid-cycle',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['b1', 'e1']], ['alloc', 'y1', 2], ['alloc', 'x1', 1], ['gc', ['x1', 'y1']], ['finish']]),
{'log': [[2, ['d1']], [1, ['a1', 'c1']], [1, ['b1']], [2, ['e1']]], 'pages': {'1': ['x1'], '2': ['y1']}}),
('three cycles',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['a1', 'b1', 'd1']], ['gc', ['a1', 'd1']], ['gc', ['d1']], ['finish']]),
{'log': [[1, ['c1']], [2, ['e1']], [1, ['b1']], [2, []], [1, ['a1']], [2, []]],
'pages': {'1': [], '2': ['d1']}}),
('control: everything live',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['a1', 'b1', 'c1', 'd1', 'e1']], ['finish']]),
{'log': [[1, []], [2, []]], 'pages': {'1': ['a1', 'b1', 'c1'], '2': ['d1', 'e1']}})],
[('regression: lazy sweep before allocation',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['finish']]),
{'log': [[1, ['b2', 'c2']], [2, ['e2']]], 'pages': {'1': ['a2', 'x2'], '2': ['d2']}}),
('second cycle with an unswept page',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['gc', ['a2']], ['finish']]),
{'log': [[1, ['b2', 'c2']], [2, ['e2']], [1, ['x2']], [2, ['d2']]], 'pages': {'1': ['a2'], '2': []}}),
('allocation after sweeping dies next cycle',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['a2']], ['finish'], ['alloc', 'y2', 2], ['gc', ['a2']], ['finish']]),
{'log': [[1, ['b2', 'c2']], [2, ['d2', 'e2']], [1, []], [2, ['y2']]], 'pages': {'1': ['a2'], '2': []}}),
('allocation into an unswept page mid-cycle',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['b2', 'e2']], ['alloc', 'y2', 2], ['alloc', 'x2', 1], ['gc', ['x2', 'y2']], ['finish']]),
{'log': [[2, ['d2']], [1, ['a2', 'c2']], [1, ['b2']], [2, ['e2']]], 'pages': {'1': ['x2'], '2': ['y2']}}),
('three cycles',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['a2', 'b2', 'd2']], ['gc', ['a2', 'd2']], ['gc', ['d2']], ['finish']]),
{'log': [[1, ['c2']], [2, ['e2']], [1, ['b2']], [2, []], [1, ['a2']], [2, []]],
'pages': {'1': [], '2': ['d2']}}),
('control: everything live',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['a2', 'b2', 'c2', 'd2', 'e2']], ['finish']]),
{'log': [[1, []], [2, []]], 'pages': {'1': ['a2', 'b2', 'c2'], '2': ['d2', 'e2']}})],
[('regression: lazy sweep before allocation',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['finish']]),
{'log': [[1, ['b3', 'c3']], [2, ['e3']]], 'pages': {'1': ['a3', 'x3'], '2': ['d3']}}),
('second cycle with an unswept page',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['gc', ['a3']], ['finish']]),
{'log': [[1, ['b3', 'c3']], [2, ['e3']], [1, ['x3']], [2, ['d3']]], 'pages': {'1': ['a3'], '2': []}}),
('allocation after sweeping dies next cycle',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['a3']], ['finish'], ['alloc', 'y3', 2], ['gc', ['a3']], ['finish']]),
{'log': [[1, ['b3', 'c3']], [2, ['d3', 'e3']], [1, []], [2, ['y3']]], 'pages': {'1': ['a3'], '2': []}}),
('allocation into an unswept page mid-cycle',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['b3', 'e3']], ['alloc', 'y3', 2], ['alloc', 'x3', 1], ['gc', ['x3', 'y3']], ['finish']]),
{'log': [[2, ['d3']], [1, ['a3', 'c3']], [1, ['b3']], [2, ['e3']]], 'pages': {'1': ['x3'], '2': ['y3']}}),
('three cycles',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['a3', 'b3', 'd3']], ['gc', ['a3', 'd3']], ['gc', ['d3']], ['finish']]),
{'log': [[1, ['c3']], [2, ['e3']], [1, ['b3']], [2, []], [1, ['a3']], [2, []]],
'pages': {'1': [], '2': ['d3']}}),
('control: everything live',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['a3', 'b3', 'c3', 'd3', 'e3']], ['finish']]),
{'log': [[1, []], [2, []]], 'pages': {'1': ['a3', 'b3', 'c3'], '2': ['d3', 'e3']}})],
[('regression: lazy sweep before allocation',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['finish']]),
{'log': [[1, ['b4', 'c4']], [2, ['e4']]], 'pages': {'1': ['a4', 'x4'], '2': ['d4']}}),
('second cycle with an unswept page',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['gc', ['a4']], ['finish']]),
{'log': [[1, ['b4', 'c4']], [2, ['e4']], [1, ['x4']], [2, ['d4']]], 'pages': {'1': ['a4'], '2': []}}),
('allocation after sweeping dies next cycle',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['a4']], ['finish'], ['alloc', 'y4', 2], ['gc', ['a4']], ['finish']]),
{'log': [[1, ['b4', 'c4']], [2, ['d4', 'e4']], [1, []], [2, ['y4']]], 'pages': {'1': ['a4'], '2': []}}),
('allocation into an unswept page mid-cycle',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['b4', 'e4']], ['alloc', 'y4', 2], ['alloc', 'x4', 1], ['gc', ['x4', 'y4']], ['finish']]),
{'log': [[2, ['d4']], [1, ['a4', 'c4']], [1, ['b4']], [2, ['e4']]], 'pages': {'1': ['x4'], '2': ['y4']}}),
('three cycles',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['a4', 'b4', 'd4']], ['gc', ['a4', 'd4']], ['gc', ['d4']], ['finish']]),
{'log': [[1, ['c4']], [2, ['e4']], [1, ['b4']], [2, []], [1, ['a4']], [2, []]],
'pages': {'1': [], '2': ['d4']}}),
('control: everything live',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['a4', 'b4', 'c4', 'd4', 'e4']], ['finish']]),
{'log': [[1, []], [2, []]], 'pages': {'1': ['a4', 'b4', 'c4'], '2': ['d4', 'e4']}})],
[('regression: lazy sweep before allocation',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['finish']]),
{'log': [[1, ['b5', 'c5']], [2, ['e5']]], 'pages': {'1': ['a5', 'x5'], '2': ['d5']}}),
('second cycle with an unswept page',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['gc', ['a5']], ['finish']]),
{'log': [[1, ['b5', 'c5']], [2, ['e5']], [1, ['x5']], [2, ['d5']]], 'pages': {'1': ['a5'], '2': []}}),
('allocation after sweeping dies next cycle',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['a5']], ['finish'], ['alloc', 'y5', 2], ['gc', ['a5']], ['finish']]),
{'log': [[1, ['b5', 'c5']], [2, ['d5', 'e5']], [1, []], [2, ['y5']]], 'pages': {'1': ['a5'], '2': []}}),
('allocation into an unswept page mid-cycle',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['b5', 'e5']], ['alloc', 'y5', 2], ['alloc', 'x5', 1], ['gc', ['x5', 'y5']], ['finish']]),
{'log': [[2, ['d5']], [1, ['a5', 'c5']], [1, ['b5']], [2, ['e5']]], 'pages': {'1': ['x5'], '2': ['y5']}}),
('three cycles',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['a5', 'b5', 'd5']], ['gc', ['a5', 'd5']], ['gc', ['d5']], ['finish']]),
{'log': [[1, ['c5']], [2, ['e5']], [1, ['b5']], [2, []], [1, ['a5']], [2, []]],
'pages': {'1': [], '2': ['d5']}}),
('control: everything live',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['a5', 'b5', 'c5', 'd5', 'e5']], ['finish']]),
{'log': [[1, []], [2, []]], 'pages': {'1': ['a5', 'b5', 'c5'], '2': ['d5', 'e5']}})]]
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: lazy sweep before allocation | {'log': [[1, ['a1', 'b1', 'c1']], [2, ['d1', 'e1']]], 'pages': {'1': ['x1'], '2': []}} | {'log': [[1, ['b1', 'c1']], [2, ['e1']]], 'pages': {'1': ['a1', 'x1'], '2': ['d1']}} | Failed |
| second cycle with an unswept page | {'log': [[1, ['a1', 'b1', 'c1']], [2, ['d1', 'e1']], [1, ['x1']], [2, []]], 'pages': {'1': [], '2': []}} | {'log': [[1, ['b1', 'c1']], [2, ['e1']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': []}} | Failed |
| allocation after sweeping dies next cycle | {'log': [[1, ['a1', 'b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, ['y1']]], 'pages': {'1': [], '2': []}} | {'log': [[1, ['b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, ['y1']]], 'pages': {'1': ['a1'], '2': []}} | Failed |
| allocation into an unswept page mid-cycle | {'log': [[2, ['d1', 'e1']], [1, ['a1', 'b1', 'c1']], [1, ['x1']], [2, ['y1']]], 'pages': {'1': [], '2': []}} | {'log': [[2, ['d1']], [1, ['a1', 'c1']], [1, ['b1']], [2, ['e1']]], 'pages': {'1': ['x1'], '2': ['y1']}} | Failed |
| three cycles | {'log': [[1, ['a1', 'b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, []], [1, []], [2, []]], 'pages': {'1': [], '2': []}} | {'log': [[1, ['c1']], [2, ['e1']], [1, ['b1']], [2, []], [1, ['a1']], [2, []]], 'pages': {'1': [], '2': ['d1']}} | Failed |
| control: everything live | {'log': [[1, ['a1', 'b1', 'c1']], [2, ['d1', 'e1']]], 'pages': {'1': [], '2': []}} | {'log': [[1, []], [2, []]], 'pages': {'1': ['a1', 'b1', 'c1'], '2': ['d1', 'e1']}} | Failed |
SHA-256 / d98b6280d8b7cd1491768834ac9c31a1037a1dce85cfc196a511ad0651baa540
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(pages, events):
pages = {p: dict(v) for p, v in pages.items()}
epoch = 0
unswept = []
log = []
def sweep(p):
parity = epoch % 2
dead = sorted(o for o, m in pages[p].items() if m != parity)
for o in dead:
del pages[p][o]
log.append([p, dead])
unswept.remove(p)
for ev in events:
if ev[0] == 'gc':
while unswept:
sweep(unswept[0])
epoch += 1
for p in pages:
for o in pages[p]:
if o in ev[1]:
pages[p][o] = 1
unswept = sorted(pages)
elif ev[0] == 'alloc':
if ev[2] in unswept:
sweep(ev[2])
pages[ev[2]][ev[1]] = epoch % 2
else:
while unswept:
sweep(unswept[0])
return {'log': log, 'pages': {str(p): sorted(v) for p, v in sorted(pages.items())}}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: lazy sweep before allocation',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['finish']]),
{'log': [[1, ['b1', 'c1']], [2, ['e1']]], 'pages': {'1': ['a1', 'x1'], '2': ['d1']}}),
('second cycle with an unswept page',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['gc', ['a1']], ['finish']]),
{'log': [[1, ['b1', 'c1']], [2, ['e1']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': []}}),
('allocation after sweeping dies next cycle',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['a1']], ['finish'], ['alloc', 'y1', 2], ['gc', ['a1']], ['finish']]),
{'log': [[1, ['b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, ['y1']]], 'pages': {'1': ['a1'], '2': []}}),
('allocation into an unswept page mid-cycle',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['b1', 'e1']], ['alloc', 'y1', 2], ['alloc', 'x1', 1], ['gc', ['x1', 'y1']], ['finish']]),
{'log': [[2, ['d1']], [1, ['a1', 'c1']], [1, ['b1']], [2, ['e1']]], 'pages': {'1': ['x1'], '2': ['y1']}}),
('three cycles',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['a1', 'b1', 'd1']], ['gc', ['a1', 'd1']], ['gc', ['d1']], ['finish']]),
{'log': [[1, ['c1']], [2, ['e1']], [1, ['b1']], [2, []], [1, ['a1']], [2, []]],
'pages': {'1': [], '2': ['d1']}}),
('control: everything live',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['a1', 'b1', 'c1', 'd1', 'e1']], ['finish']]),
{'log': [[1, []], [2, []]], 'pages': {'1': ['a1', 'b1', 'c1'], '2': ['d1', 'e1']}})],
[('regression: lazy sweep before allocation',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['finish']]),
{'log': [[1, ['b2', 'c2']], [2, ['e2']]], 'pages': {'1': ['a2', 'x2'], '2': ['d2']}}),
('second cycle with an unswept page',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['gc', ['a2']], ['finish']]),
{'log': [[1, ['b2', 'c2']], [2, ['e2']], [1, ['x2']], [2, ['d2']]], 'pages': {'1': ['a2'], '2': []}}),
('allocation after sweeping dies next cycle',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['a2']], ['finish'], ['alloc', 'y2', 2], ['gc', ['a2']], ['finish']]),
{'log': [[1, ['b2', 'c2']], [2, ['d2', 'e2']], [1, []], [2, ['y2']]], 'pages': {'1': ['a2'], '2': []}}),
('allocation into an unswept page mid-cycle',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['b2', 'e2']], ['alloc', 'y2', 2], ['alloc', 'x2', 1], ['gc', ['x2', 'y2']], ['finish']]),
{'log': [[2, ['d2']], [1, ['a2', 'c2']], [1, ['b2']], [2, ['e2']]], 'pages': {'1': ['x2'], '2': ['y2']}}),
('three cycles',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['a2', 'b2', 'd2']], ['gc', ['a2', 'd2']], ['gc', ['d2']], ['finish']]),
{'log': [[1, ['c2']], [2, ['e2']], [1, ['b2']], [2, []], [1, ['a2']], [2, []]],
'pages': {'1': [], '2': ['d2']}}),
('control: everything live',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['a2', 'b2', 'c2', 'd2', 'e2']], ['finish']]),
{'log': [[1, []], [2, []]], 'pages': {'1': ['a2', 'b2', 'c2'], '2': ['d2', 'e2']}})],
[('regression: lazy sweep before allocation',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['finish']]),
{'log': [[1, ['b3', 'c3']], [2, ['e3']]], 'pages': {'1': ['a3', 'x3'], '2': ['d3']}}),
('second cycle with an unswept page',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['gc', ['a3']], ['finish']]),
{'log': [[1, ['b3', 'c3']], [2, ['e3']], [1, ['x3']], [2, ['d3']]], 'pages': {'1': ['a3'], '2': []}}),
('allocation after sweeping dies next cycle',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['a3']], ['finish'], ['alloc', 'y3', 2], ['gc', ['a3']], ['finish']]),
{'log': [[1, ['b3', 'c3']], [2, ['d3', 'e3']], [1, []], [2, ['y3']]], 'pages': {'1': ['a3'], '2': []}}),
('allocation into an unswept page mid-cycle',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['b3', 'e3']], ['alloc', 'y3', 2], ['alloc', 'x3', 1], ['gc', ['x3', 'y3']], ['finish']]),
{'log': [[2, ['d3']], [1, ['a3', 'c3']], [1, ['b3']], [2, ['e3']]], 'pages': {'1': ['x3'], '2': ['y3']}}),
('three cycles',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['a3', 'b3', 'd3']], ['gc', ['a3', 'd3']], ['gc', ['d3']], ['finish']]),
{'log': [[1, ['c3']], [2, ['e3']], [1, ['b3']], [2, []], [1, ['a3']], [2, []]],
'pages': {'1': [], '2': ['d3']}}),
('control: everything live',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['a3', 'b3', 'c3', 'd3', 'e3']], ['finish']]),
{'log': [[1, []], [2, []]], 'pages': {'1': ['a3', 'b3', 'c3'], '2': ['d3', 'e3']}})],
[('regression: lazy sweep before allocation',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['finish']]),
{'log': [[1, ['b4', 'c4']], [2, ['e4']]], 'pages': {'1': ['a4', 'x4'], '2': ['d4']}}),
('second cycle with an unswept page',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['gc', ['a4']], ['finish']]),
{'log': [[1, ['b4', 'c4']], [2, ['e4']], [1, ['x4']], [2, ['d4']]], 'pages': {'1': ['a4'], '2': []}}),
('allocation after sweeping dies next cycle',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['a4']], ['finish'], ['alloc', 'y4', 2], ['gc', ['a4']], ['finish']]),
{'log': [[1, ['b4', 'c4']], [2, ['d4', 'e4']], [1, []], [2, ['y4']]], 'pages': {'1': ['a4'], '2': []}}),
('allocation into an unswept page mid-cycle',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['b4', 'e4']], ['alloc', 'y4', 2], ['alloc', 'x4', 1], ['gc', ['x4', 'y4']], ['finish']]),
{'log': [[2, ['d4']], [1, ['a4', 'c4']], [1, ['b4']], [2, ['e4']]], 'pages': {'1': ['x4'], '2': ['y4']}}),
('three cycles',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['a4', 'b4', 'd4']], ['gc', ['a4', 'd4']], ['gc', ['d4']], ['finish']]),
{'log': [[1, ['c4']], [2, ['e4']], [1, ['b4']], [2, []], [1, ['a4']], [2, []]],
'pages': {'1': [], '2': ['d4']}}),
('control: everything live',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['a4', 'b4', 'c4', 'd4', 'e4']], ['finish']]),
{'log': [[1, []], [2, []]], 'pages': {'1': ['a4', 'b4', 'c4'], '2': ['d4', 'e4']}})],
[('regression: lazy sweep before allocation',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['finish']]),
{'log': [[1, ['b5', 'c5']], [2, ['e5']]], 'pages': {'1': ['a5', 'x5'], '2': ['d5']}}),
('second cycle with an unswept page',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['gc', ['a5']], ['finish']]),
{'log': [[1, ['b5', 'c5']], [2, ['e5']], [1, ['x5']], [2, ['d5']]], 'pages': {'1': ['a5'], '2': []}}),
('allocation after sweeping dies next cycle',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['a5']], ['finish'], ['alloc', 'y5', 2], ['gc', ['a5']], ['finish']]),
{'log': [[1, ['b5', 'c5']], [2, ['d5', 'e5']], [1, []], [2, ['y5']]], 'pages': {'1': ['a5'], '2': []}}),
('allocation into an unswept page mid-cycle',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['b5', 'e5']], ['alloc', 'y5', 2], ['alloc', 'x5', 1], ['gc', ['x5', 'y5']], ['finish']]),
{'log': [[2, ['d5']], [1, ['a5', 'c5']], [1, ['b5']], [2, ['e5']]], 'pages': {'1': ['x5'], '2': ['y5']}}),
('three cycles',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['a5', 'b5', 'd5']], ['gc', ['a5', 'd5']], ['gc', ['d5']], ['finish']]),
{'log': [[1, ['c5']], [2, ['e5']], [1, ['b5']], [2, []], [1, ['a5']], [2, []]],
'pages': {'1': [], '2': ['d5']}}),
('control: everything live',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['a5', 'b5', 'c5', 'd5', 'e5']], ['finish']]),
{'log': [[1, []], [2, []]], 'pages': {'1': ['a5', 'b5', 'c5'], '2': ['d5', 'e5']}})]]
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: lazy sweep before allocation | {'log': [[1, ['b1', 'c1']], [2, ['e1']]], 'pages': {'1': ['a1', 'x1'], '2': ['d1']}} | {'log': [[1, ['b1', 'c1']], [2, ['e1']]], 'pages': {'1': ['a1', 'x1'], '2': ['d1']}} | Passed |
| second cycle with an unswept page | {'log': [[1, ['b1', 'c1']], [2, ['e1']], [1, ['a1', 'x1']], [2, ['d1']]], 'pages': {'1': [], '2': []}} | {'log': [[1, ['b1', 'c1']], [2, ['e1']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': []}} | Failed |
| allocation after sweeping dies next cycle | {'log': [[1, ['b1', 'c1']], [2, ['d1', 'e1']], [1, ['a1']], [2, ['y1']]], 'pages': {'1': [], '2': []}} | {'log': [[1, ['b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, ['y1']]], 'pages': {'1': ['a1'], '2': []}} | Failed |
| allocation into an unswept page mid-cycle | {'log': [[2, ['d1']], [1, ['a1', 'c1']], [1, ['b1', 'x1']], [2, ['e1', 'y1']]], 'pages': {'1': [], '2': []}} | {'log': [[2, ['d1']], [1, ['a1', 'c1']], [1, ['b1']], [2, ['e1']]], 'pages': {'1': ['x1'], '2': ['y1']}} | Failed |
| three cycles | {'log': [[1, ['c1']], [2, ['e1']], [1, ['a1', 'b1']], [2, ['d1']], [1, []], [2, []]], 'pages': {'1': [], '2': []}} | {'log': [[1, ['c1']], [2, ['e1']], [1, ['b1']], [2, []], [1, ['a1']], [2, []]], 'pages': {'1': [], '2': ['d1']}} | Failed |
| control: everything live | {'log': [[1, []], [2, []]], 'pages': {'1': ['a1', 'b1', 'c1'], '2': ['d1', 'e1']}} | {'log': [[1, []], [2, []]], 'pages': {'1': ['a1', 'b1', 'c1'], '2': ['d1', 'e1']}} | Passed |
SHA-256 / 98f8478d135ad6caa4e1f172250c2045fe484070f848745feb42548b1b0aad54
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(pages, events):
pages = {p: dict(v) for p, v in pages.items()}
epoch = 0
unswept = []
log = []
def sweep(p):
parity = epoch % 2
dead = sorted(o for o, m in pages[p].items() if m != parity)
for o in dead:
del pages[p][o]
log.append([p, dead])
unswept.remove(p)
for ev in events:
if ev[0] == 'gc':
while unswept:
sweep(unswept[0])
epoch += 1
for p in pages:
for o in pages[p]:
if o in ev[1]:
pages[p][o] = epoch % 2
unswept = sorted(pages)
elif ev[0] == 'alloc':
if ev[2] in unswept:
sweep(ev[2])
pages[ev[2]][ev[1]] = epoch % 2
else:
while unswept:
sweep(unswept[0])
return {'log': log, 'pages': {str(p): sorted(v) for p, v in sorted(pages.items())}}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: lazy sweep before allocation',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['finish']]),
{'log': [[1, ['b1', 'c1']], [2, ['e1']]], 'pages': {'1': ['a1', 'x1'], '2': ['d1']}}),
('second cycle with an unswept page',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['gc', ['a1']], ['finish']]),
{'log': [[1, ['b1', 'c1']], [2, ['e1']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': []}}),
('allocation after sweeping dies next cycle',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['a1']], ['finish'], ['alloc', 'y1', 2], ['gc', ['a1']], ['finish']]),
{'log': [[1, ['b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, ['y1']]], 'pages': {'1': ['a1'], '2': []}}),
('allocation into an unswept page mid-cycle',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['b1', 'e1']], ['alloc', 'y1', 2], ['alloc', 'x1', 1], ['gc', ['x1', 'y1']], ['finish']]),
{'log': [[2, ['d1']], [1, ['a1', 'c1']], [1, ['b1']], [2, ['e1']]], 'pages': {'1': ['x1'], '2': ['y1']}}),
('three cycles',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['a1', 'b1', 'd1']], ['gc', ['a1', 'd1']], ['gc', ['d1']], ['finish']]),
{'log': [[1, ['c1']], [2, ['e1']], [1, ['b1']], [2, []], [1, ['a1']], [2, []]],
'pages': {'1': [], '2': ['d1']}}),
('control: everything live',
({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
[['gc', ['a1', 'b1', 'c1', 'd1', 'e1']], ['finish']]),
{'log': [[1, []], [2, []]], 'pages': {'1': ['a1', 'b1', 'c1'], '2': ['d1', 'e1']}})],
[('regression: lazy sweep before allocation',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['finish']]),
{'log': [[1, ['b2', 'c2']], [2, ['e2']]], 'pages': {'1': ['a2', 'x2'], '2': ['d2']}}),
('second cycle with an unswept page',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['gc', ['a2']], ['finish']]),
{'log': [[1, ['b2', 'c2']], [2, ['e2']], [1, ['x2']], [2, ['d2']]], 'pages': {'1': ['a2'], '2': []}}),
('allocation after sweeping dies next cycle',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['a2']], ['finish'], ['alloc', 'y2', 2], ['gc', ['a2']], ['finish']]),
{'log': [[1, ['b2', 'c2']], [2, ['d2', 'e2']], [1, []], [2, ['y2']]], 'pages': {'1': ['a2'], '2': []}}),
('allocation into an unswept page mid-cycle',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['b2', 'e2']], ['alloc', 'y2', 2], ['alloc', 'x2', 1], ['gc', ['x2', 'y2']], ['finish']]),
{'log': [[2, ['d2']], [1, ['a2', 'c2']], [1, ['b2']], [2, ['e2']]], 'pages': {'1': ['x2'], '2': ['y2']}}),
('three cycles',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['a2', 'b2', 'd2']], ['gc', ['a2', 'd2']], ['gc', ['d2']], ['finish']]),
{'log': [[1, ['c2']], [2, ['e2']], [1, ['b2']], [2, []], [1, ['a2']], [2, []]],
'pages': {'1': [], '2': ['d2']}}),
('control: everything live',
({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
[['gc', ['a2', 'b2', 'c2', 'd2', 'e2']], ['finish']]),
{'log': [[1, []], [2, []]], 'pages': {'1': ['a2', 'b2', 'c2'], '2': ['d2', 'e2']}})],
[('regression: lazy sweep before allocation',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['finish']]),
{'log': [[1, ['b3', 'c3']], [2, ['e3']]], 'pages': {'1': ['a3', 'x3'], '2': ['d3']}}),
('second cycle with an unswept page',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['gc', ['a3']], ['finish']]),
{'log': [[1, ['b3', 'c3']], [2, ['e3']], [1, ['x3']], [2, ['d3']]], 'pages': {'1': ['a3'], '2': []}}),
('allocation after sweeping dies next cycle',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['a3']], ['finish'], ['alloc', 'y3', 2], ['gc', ['a3']], ['finish']]),
{'log': [[1, ['b3', 'c3']], [2, ['d3', 'e3']], [1, []], [2, ['y3']]], 'pages': {'1': ['a3'], '2': []}}),
('allocation into an unswept page mid-cycle',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['b3', 'e3']], ['alloc', 'y3', 2], ['alloc', 'x3', 1], ['gc', ['x3', 'y3']], ['finish']]),
{'log': [[2, ['d3']], [1, ['a3', 'c3']], [1, ['b3']], [2, ['e3']]], 'pages': {'1': ['x3'], '2': ['y3']}}),
('three cycles',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['a3', 'b3', 'd3']], ['gc', ['a3', 'd3']], ['gc', ['d3']], ['finish']]),
{'log': [[1, ['c3']], [2, ['e3']], [1, ['b3']], [2, []], [1, ['a3']], [2, []]],
'pages': {'1': [], '2': ['d3']}}),
('control: everything live',
({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
[['gc', ['a3', 'b3', 'c3', 'd3', 'e3']], ['finish']]),
{'log': [[1, []], [2, []]], 'pages': {'1': ['a3', 'b3', 'c3'], '2': ['d3', 'e3']}})],
[('regression: lazy sweep before allocation',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['finish']]),
{'log': [[1, ['b4', 'c4']], [2, ['e4']]], 'pages': {'1': ['a4', 'x4'], '2': ['d4']}}),
('second cycle with an unswept page',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['gc', ['a4']], ['finish']]),
{'log': [[1, ['b4', 'c4']], [2, ['e4']], [1, ['x4']], [2, ['d4']]], 'pages': {'1': ['a4'], '2': []}}),
('allocation after sweeping dies next cycle',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['a4']], ['finish'], ['alloc', 'y4', 2], ['gc', ['a4']], ['finish']]),
{'log': [[1, ['b4', 'c4']], [2, ['d4', 'e4']], [1, []], [2, ['y4']]], 'pages': {'1': ['a4'], '2': []}}),
('allocation into an unswept page mid-cycle',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['b4', 'e4']], ['alloc', 'y4', 2], ['alloc', 'x4', 1], ['gc', ['x4', 'y4']], ['finish']]),
{'log': [[2, ['d4']], [1, ['a4', 'c4']], [1, ['b4']], [2, ['e4']]], 'pages': {'1': ['x4'], '2': ['y4']}}),
('three cycles',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['a4', 'b4', 'd4']], ['gc', ['a4', 'd4']], ['gc', ['d4']], ['finish']]),
{'log': [[1, ['c4']], [2, ['e4']], [1, ['b4']], [2, []], [1, ['a4']], [2, []]],
'pages': {'1': [], '2': ['d4']}}),
('control: everything live',
({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
[['gc', ['a4', 'b4', 'c4', 'd4', 'e4']], ['finish']]),
{'log': [[1, []], [2, []]], 'pages': {'1': ['a4', 'b4', 'c4'], '2': ['d4', 'e4']}})],
[('regression: lazy sweep before allocation',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['finish']]),
{'log': [[1, ['b5', 'c5']], [2, ['e5']]], 'pages': {'1': ['a5', 'x5'], '2': ['d5']}}),
('second cycle with an unswept page',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['gc', ['a5']], ['finish']]),
{'log': [[1, ['b5', 'c5']], [2, ['e5']], [1, ['x5']], [2, ['d5']]], 'pages': {'1': ['a5'], '2': []}}),
('allocation after sweeping dies next cycle',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['a5']], ['finish'], ['alloc', 'y5', 2], ['gc', ['a5']], ['finish']]),
{'log': [[1, ['b5', 'c5']], [2, ['d5', 'e5']], [1, []], [2, ['y5']]], 'pages': {'1': ['a5'], '2': []}}),
('allocation into an unswept page mid-cycle',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['b5', 'e5']], ['alloc', 'y5', 2], ['alloc', 'x5', 1], ['gc', ['x5', 'y5']], ['finish']]),
{'log': [[2, ['d5']], [1, ['a5', 'c5']], [1, ['b5']], [2, ['e5']]], 'pages': {'1': ['x5'], '2': ['y5']}}),
('three cycles',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['a5', 'b5', 'd5']], ['gc', ['a5', 'd5']], ['gc', ['d5']], ['finish']]),
{'log': [[1, ['c5']], [2, ['e5']], [1, ['b5']], [2, []], [1, ['a5']], [2, []]],
'pages': {'1': [], '2': ['d5']}}),
('control: everything live',
({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
[['gc', ['a5', 'b5', 'c5', 'd5', 'e5']], ['finish']]),
{'log': [[1, []], [2, []]], 'pages': {'1': ['a5', 'b5', 'c5'], '2': ['d5', 'e5']}})]]
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: lazy sweep before allocation | {'log': [[1, ['b1', 'c1']], [2, ['e1']]], 'pages': {'1': ['a1', 'x1'], '2': ['d1']}} | {'log': [[1, ['b1', 'c1']], [2, ['e1']]], 'pages': {'1': ['a1', 'x1'], '2': ['d1']}} | Passed |
| second cycle with an unswept page | {'log': [[1, ['b1', 'c1']], [2, ['e1']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': []}} | {'log': [[1, ['b1', 'c1']], [2, ['e1']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': []}} | Passed |
| allocation after sweeping dies next cycle | {'log': [[1, ['b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, ['y1']]], 'pages': {'1': ['a1'], '2': []}} | {'log': [[1, ['b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, ['y1']]], 'pages': {'1': ['a1'], '2': []}} | Passed |
| allocation into an unswept page mid-cycle | {'log': [[2, ['d1']], [1, ['a1', 'c1']], [1, ['b1']], [2, ['e1']]], 'pages': {'1': ['x1'], '2': ['y1']}} | {'log': [[2, ['d1']], [1, ['a1', 'c1']], [1, ['b1']], [2, ['e1']]], 'pages': {'1': ['x1'], '2': ['y1']}} | Passed |
| three cycles | {'log': [[1, ['c1']], [2, ['e1']], [1, ['b1']], [2, []], [1, ['a1']], [2, []]], 'pages': {'1': [], '2': ['d1']}} | {'log': [[1, ['c1']], [2, ['e1']], [1, ['b1']], [2, []], [1, ['a1']], [2, []]], 'pages': {'1': [], '2': ['d1']}} | Passed |
| control: everything live | {'log': [[1, []], [2, []]], 'pages': {'1': ['a1', 'b1', 'c1'], '2': ['d1', 'e1']}} | {'log': [[1, []], [2, []]], 'pages': {'1': ['a1', 'b1', 'c1'], '2': ['d1', 'e1']}} | Passed |
SHA-256 / 3989f345faac8e5d4a3e8453177b8da08df056b696809a696dbbe7299c539123
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.017277+00:00.
Case digest / 28a4df0869ad62e5d890be623d8f3a041fe730ce8399d47ad3a64db07977ae73