FAILURE MAP
← Case archive

FA-90521 / Garbage collector invariants / Open access

Card marking: promotion one collection late · case 01

Objects stay young one minor collection longer than the tenuring threshold allows.

Verified by executionVariant 1 · 6 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

Promotion requires age strictly greater than tenure.

THE FAILURE

Promotion requires age strictly greater than tenure.

Unsuccessful approach: Comparing with tenure - 1 promotes one collection early.

Case contract

Two generations. objs maps id -> [generation, address, fields]; a field slot i of an old object lives at address + 8*i and belongs to card (slot address // 64). store writes a field and, when an old object receives a young reference, dirties that slot's card. minor: roots plus young referents of old slots in dirty cards seed a trace through young objects; unreached young objects are freed; survivors age by one and are promoted (addresses from 4096 in 64-byte steps) when age >= tenure; the card set is then rebuilt from every old slot that still references a young object. alloc id creates a young object with one null field; root/unroot edit the root list. Return per-minor {freed, promoted, cards}; following a freed object reports {"dangling": id}.

Why this case matters

Minor collections are only correct if the remembered set covers every old-to-young pointer.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(objs, roots, events, tenure):
    objs = {k: {'gen': v[0], 'addr': v[1], 'fields': list(v[2]), 'age': 0} for k, v in objs.items()}
    roots = list(roots)
    cards = set()
    log = []
    next_addr = 4096
    def slot_card(o, i):
        return (objs[o]['addr'] + 8 * i) // 64
    try:
        for ev in events:
            if ev[0] == 'store':
                _, src, i, dst = ev
                objs[src]['fields'][i] = dst
                if objs[src]['gen'] == 'old' and dst is not None and objs[dst]['gen'] == 'young':
                    cards.add(slot_card(src, i))
            elif ev[0] == 'alloc':
                objs[ev[1]] = {'gen': 'young', 'addr': 0, 'fields': [None], 'age': 0}
            elif ev[0] == 'root':
                roots.append(ev[1])
            elif ev[0] == 'unroot':
                roots.remove(ev[1])
            else:
                grey = [r for r in roots if objs[r]['gen'] == 'young']
                for o, ob in objs.items():
                    if ob['gen'] == 'old':
                        for i, f in enumerate(ob['fields']):
                            if slot_card(o, i) in cards and f is not None and objs[f]['gen'] == 'young':
                                grey.append(f)
                live = set()
                while grey:
                    y = grey.pop()
                    if y in live:
                        continue
                    live.add(y)
                    for f in objs[y]['fields']:
                        if f is not None and objs[f]['gen'] == 'young':
                            grey.append(f)
                dead = sorted(k for k, ob in objs.items() if ob['gen'] == 'young' and k not in live)
                for k in dead:
                    del objs[k]
                promoted = []
                for k in sorted(live):
                    objs[k]['age'] += 1
                    if objs[k]['age'] > tenure:
                        objs[k]['gen'] = 'old'
                        objs[k]['addr'] = next_addr
                        next_addr += 64
                        promoted.append(k)
                cards = set()
                for o in [k for k, ob in objs.items() if ob['gen'] == 'old']:
                    for i, f in enumerate(objs[o]['fields']):
                        if f is not None and objs[f]['gen'] == 'young':
                            cards.add(slot_card(o, i))
                log.append({'freed': dead, 'promoted': promoted, 'cards': sorted(cards)})
    except KeyError as e:
        log.append({'dangling': e.args[0]})
    return log
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [1], 'freed': [13, 14], 'promoted': []}, {'cards': [1], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [0, 1], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [2], 'freed': [13, 14], 'promoted': []}, {'cards': [2], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [4], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [1, 2], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [3], 'freed': [13, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [5], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [2, 3], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [4], 'freed': [13, 14], 'promoted': []}, {'cards': [4], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [6], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [3, 4], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [5], 'freed': [13, 14], 'promoted': []}, {'cards': [5], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [7], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [4, 5], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])]]
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 fixtureActualExpectedOutcome
regression: old-to-young edge survives two minor collections[{'cards': [1], 'freed': [13, 14], 'promoted': []}, {'cards': [1], 'freed': [], 'promoted': []}][{'cards': [1], 'freed': [13, 14], 'promoted': []}, {'cards': [1], 'freed': [], 'promoted': []}]Passed
edge stored after the target survived once[{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}][{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]Passed
promotion at the tenuring threshold[{'cards': [], 'freed': [13, 14], 'promoted': []}, {'cards': [], 'freed': [], 'promoted': []}, {'cards': [], 'freed': [], 'promoted': [11, 12]}][{'cards': [], 'freed': [13, 14], 'promoted': []}, {'cards': [], 'freed': [], 'promoted': [11, 12]}, {'cards': [], 'freed': [], 'promoted': []}]Failed
promoted object pointing at a younger object[{'cards': [], 'freed': [13, 14], 'promoted': []}, {'cards': [], 'freed': [12], 'promoted': []}, {'cards': [64], 'freed': [], 'promoted': [11]}][{'cards': [], 'freed': [13, 14], 'promoted': []}, {'cards': [64], 'freed': [12], 'promoted': [11]}, {'cards': [], 'freed': [], 'promoted': [15]}]Failed
card of a slot in the next card[{'cards': [0, 1], 'freed': [11, 12], 'promoted': []}][{'cards': [0, 1], 'freed': [11, 12], 'promoted': []}]Passed
control: unreferenced young objects die[{'cards': [], 'freed': [11, 13, 14], 'promoted': []}][{'cards': [], 'freed': [11, 13, 14], 'promoted': []}]Passed

SHA-256 / 5f8125a2715d4a88dc56890858ffb076321f5f9879347cf683419a33a0d93eff

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(objs, roots, events, tenure):
    objs = {k: {'gen': v[0], 'addr': v[1], 'fields': list(v[2]), 'age': 0} for k, v in objs.items()}
    roots = list(roots)
    cards = set()
    log = []
    next_addr = 4096
    def slot_card(o, i):
        return (objs[o]['addr'] + 8 * i) // 64
    try:
        for ev in events:
            if ev[0] == 'store':
                _, src, i, dst = ev
                objs[src]['fields'][i] = dst
                if objs[src]['gen'] == 'old' and dst is not None and objs[dst]['gen'] == 'young':
                    cards.add(slot_card(src, i))
            elif ev[0] == 'alloc':
                objs[ev[1]] = {'gen': 'young', 'addr': 0, 'fields': [None], 'age': 0}
            elif ev[0] == 'root':
                roots.append(ev[1])
            elif ev[0] == 'unroot':
                roots.remove(ev[1])
            else:
                grey = [r for r in roots if objs[r]['gen'] == 'young']
                for o, ob in objs.items():
                    if ob['gen'] == 'old':
                        for i, f in enumerate(ob['fields']):
                            if slot_card(o, i) in cards and f is not None and objs[f]['gen'] == 'young':
                                grey.append(f)
                live = set()
                while grey:
                    y = grey.pop()
                    if y in live:
                        continue
                    live.add(y)
                    for f in objs[y]['fields']:
                        if f is not None and objs[f]['gen'] == 'young':
                            grey.append(f)
                dead = sorted(k for k, ob in objs.items() if ob['gen'] == 'young' and k not in live)
                for k in dead:
                    del objs[k]
                promoted = []
                for k in sorted(live):
                    objs[k]['age'] += 1
                    if objs[k]['age'] >= tenure - 1:
                        objs[k]['gen'] = 'old'
                        objs[k]['addr'] = next_addr
                        next_addr += 64
                        promoted.append(k)
                cards = set()
                for o in [k for k, ob in objs.items() if ob['gen'] == 'old']:
                    for i, f in enumerate(objs[o]['fields']):
                        if f is not None and objs[f]['gen'] == 'young':
                            cards.add(slot_card(o, i))
                log.append({'freed': dead, 'promoted': promoted, 'cards': sorted(cards)})
    except KeyError as e:
        log.append({'dangling': e.args[0]})
    return log
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [1], 'freed': [13, 14], 'promoted': []}, {'cards': [1], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [0, 1], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [2], 'freed': [13, 14], 'promoted': []}, {'cards': [2], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [4], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [1, 2], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [3], 'freed': [13, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [5], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [2, 3], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [4], 'freed': [13, 14], 'promoted': []}, {'cards': [4], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [6], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [3, 4], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [5], 'freed': [13, 14], 'promoted': []}, {'cards': [5], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [7], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [4, 5], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])]]
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 fixtureActualExpectedOutcome
regression: old-to-young edge survives two minor collections[{'cards': [1], 'freed': [13, 14], 'promoted': []}, {'cards': [1], 'freed': [], 'promoted': []}][{'cards': [1], 'freed': [13, 14], 'promoted': []}, {'cards': [1], 'freed': [], 'promoted': []}]Passed
edge stored after the target survived once[{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}][{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]Passed
promotion at the tenuring threshold[{'cards': [], 'freed': [13, 14], 'promoted': [11, 12]}, {'cards': [], 'freed': [], 'promoted': []}, {'cards': [], 'freed': [], 'promoted': []}][{'cards': [], 'freed': [13, 14], 'promoted': []}, {'cards': [], 'freed': [], 'promoted': [11, 12]}, {'cards': [], 'freed': [], 'promoted': []}]Failed
promoted object pointing at a younger object[{'cards': [], 'freed': [13, 14], 'promoted': [11, 12]}, {'cards': [], 'freed': [], 'promoted': [15]}, {'cards': [], 'freed': [], 'promoted': []}][{'cards': [], 'freed': [13, 14], 'promoted': []}, {'cards': [64], 'freed': [12], 'promoted': [11]}, {'cards': [], 'freed': [], 'promoted': [15]}]Failed
card of a slot in the next card[{'cards': [0, 1], 'freed': [11, 12], 'promoted': []}][{'cards': [0, 1], 'freed': [11, 12], 'promoted': []}]Passed
control: unreferenced young objects die[{'cards': [], 'freed': [11, 13, 14], 'promoted': []}][{'cards': [], 'freed': [11, 13, 14], 'promoted': []}]Passed

SHA-256 / 2488dc7882a4ed713a93c0f5a81b6de46a200db64d309deecb6d297ce8ac221b

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 6 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Sign in to the archive ↗

Verification & scope

A deterministic, bounded teaching model of one garbage-collector mechanism with stipulated rules; it is not a production collector and claims no conformance to any particular runtime. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:51:27.660472+00:00.

Case digest / 434d73ed041e7216a897faf5f62d9e22c1e024dd299b23420d5078a200b4ecc5