FA-90666 / Garbage collector invariants / Open access
Mark parity: new cycle starts with pages left unswept · case 01
Dead objects from the previous cycle are resurrected when the parity flips back to their stale mark.
ROOT CAUSE
A new cycle flips the parity without finishing the lazy sweep of the previous one.
VERIFIED REPAIR
Sweep every remaining page before advancing the epoch.
Unsuccessful approach: Dropping the unswept list skips those pages instead of sweeping them.
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':
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']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': ['e1']}} | {'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, []], [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, ['a1', 'c1']], [2, ['e1']]], 'pages': {'1': ['b1'], '2': ['d1']}} | {'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 / 7c7c5499bb579a132259b4c3a3a9e731b8389792eb38d485b8693d2fd5df3055
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':
unswept.clear()
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']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': ['e1']}} | {'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, []], [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, ['a1', 'c1']], [2, ['e1']]], 'pages': {'1': ['b1'], '2': ['d1']}} | {'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 / e788824d25054c1f19dc811775daaa96d201c0633414fa90b1669ea9eab86076
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:28.965911+00:00.
Case digest / 23c14721dc6622f4e70f0776901b9fb0774013fb62c9ac3657e18c82059dc0b0