{"abstract":"Young objects reachable only from old objects are freed and later dereferenced.","category":"Garbage collector invariants","checks":6,"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}.","contract_signature":"objs, roots, events, tenure","evaluation_group":"w2-garbage-collector-invariants-generational-card-marking","failed_approach":"Filtering on age zero misses young objects that already survived a collection.","family":"w2-garbage-collector-invariants-generational-card-marking-barrier-filter","id":"FA-90516","implementations":{"attempt":{"sha256":"998a5099b7033cf7f17b4fe4021bce1b92921dbc60df4a049663661dc1043909","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(objs, roots, events, tenure):\n    objs = {k: {'gen': v[0], 'addr': v[1], 'fields': list(v[2]), 'age': 0} for k, v in objs.items()}\n    roots = list(roots)\n    cards = set()\n    log = []\n    next_addr = 4096\n    def slot_card(o, i):\n        return (objs[o]['addr'] + 8 * i) // 64\n    try:\n        for ev in events:\n            if ev[0] == 'store':\n                _, src, i, dst = ev\n                objs[src]['fields'][i] = dst\n                if objs[src]['gen'] == 'old' and dst is not None and objs[dst]['age'] == 0:\n                    cards.add(slot_card(src, i))\n            elif ev[0] == 'alloc':\n                objs[ev[1]] = {'gen': 'young', 'addr': 0, 'fields': [None], 'age': 0}\n            elif ev[0] == 'root':\n                roots.append(ev[1])\n            elif ev[0] == 'unroot':\n                roots.remove(ev[1])\n            else:\n                grey = [r for r in roots if objs[r]['gen'] == 'young']\n                for o, ob in objs.items():\n                    if ob['gen'] == 'old':\n                        for i, f in enumerate(ob['fields']):\n                            if slot_card(o, i) in cards and f is not None and objs[f]['gen'] == 'young':\n                                grey.append(f)\n                live = set()\n                while grey:\n                    y = grey.pop()\n                    if y in live:\n                        continue\n                    live.add(y)\n                    for f in objs[y]['fields']:\n                        if f is not None and objs[f]['gen'] == 'young':\n                            grey.append(f)\n                dead = sorted(k for k, ob in objs.items() if ob['gen'] == 'young' and k not in live)\n                for k in dead:\n                    del objs[k]\n                promoted = []\n                for k in sorted(live):\n                    objs[k]['age'] += 1\n                    if objs[k]['age'] >= tenure:\n                        objs[k]['gen'] = 'old'\n                        objs[k]['addr'] = next_addr\n                        next_addr += 64\n                        promoted.append(k)\n                cards = set()\n                for o in [k for k, ob in objs.items() if ob['gen'] == 'old']:\n                    for i, f in enumerate(objs[o]['fields']):\n                        if f is not None and objs[f]['gen'] == 'young':\n                            cards.add(slot_card(o, i))\n                log.append({'freed': dead, 'promoted': promoted, 'cards': sorted(cards)})\n    except KeyError as e:\n        log.append({'dangling': e.args[0]})\n    return log\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: old-to-young edge survives two minor collections',\n   ({1: ['old', 56, [None, None]],\n     2: ['old', 192, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 1, 11], ['minor'], ['minor']],\n    5),\n   [{'cards': [1], 'freed': [13, 14], 'promoted': []}, {'cards': [1], 'freed': [], 'promoted': []}]),\n  ('edge stored after the target survived once',\n   ({1: ['old', 56, [None, None]],\n     2: ['old', 192, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [13],\n    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],\n    5),\n   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]),\n  ('promotion at the tenuring threshold',\n   ({1: ['old', 56, [None, None]],\n     2: ['old', 192, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [], 'freed': [], 'promoted': [11, 12]},\n    {'cards': [], 'freed': [], 'promoted': []}]),\n  ('promoted object pointing at a younger object',\n   ({1: ['old', 56, [None, None]],\n     2: ['old', 192, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [64], 'freed': [12], 'promoted': [11]},\n    {'cards': [], 'freed': [], 'promoted': [15]}]),\n  ('card of a slot in the next card',\n   ({1: ['old', 56, [None, None]],\n     2: ['old', 192, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],\n    4),\n   [{'cards': [0, 1], 'freed': [11, 12], 'promoted': []}]),\n  ('control: unreferenced young objects die',\n   ({1: ['old', 56, [None, None]],\n     2: ['old', 192, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [12],\n    [['minor']],\n    3),\n   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],\n [('regression: old-to-young edge survives two minor collections',\n   ({1: ['old', 120, [None, None]],\n     2: ['old', 256, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 1, 11], ['minor'], ['minor']],\n    5),\n   [{'cards': [2], 'freed': [13, 14], 'promoted': []}, {'cards': [2], 'freed': [], 'promoted': []}]),\n  ('edge stored after the target survived once',\n   ({1: ['old', 120, [None, None]],\n     2: ['old', 256, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [13],\n    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],\n    5),\n   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [4], 'freed': [], 'promoted': []}]),\n  ('promotion at the tenuring threshold',\n   ({1: ['old', 120, [None, None]],\n     2: ['old', 256, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [], 'freed': [], 'promoted': [11, 12]},\n    {'cards': [], 'freed': [], 'promoted': []}]),\n  ('promoted object pointing at a younger object',\n   ({1: ['old', 120, [None, None]],\n     2: ['old', 256, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [64], 'freed': [12], 'promoted': [11]},\n    {'cards': [], 'freed': [], 'promoted': [15]}]),\n  ('card of a slot in the next card',\n   ({1: ['old', 120, [None, None]],\n     2: ['old', 256, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],\n    4),\n   [{'cards': [1, 2], 'freed': [11, 12], 'promoted': []}]),\n  ('control: unreferenced young objects die',\n   ({1: ['old', 120, [None, None]],\n     2: ['old', 256, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [12],\n    [['minor']],\n    3),\n   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],\n [('regression: old-to-young edge survives two minor collections',\n   ({1: ['old', 184, [None, None]],\n     2: ['old', 320, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 1, 11], ['minor'], ['minor']],\n    5),\n   [{'cards': [3], 'freed': [13, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]),\n  ('edge stored after the target survived once',\n   ({1: ['old', 184, [None, None]],\n     2: ['old', 320, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [13],\n    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],\n    5),\n   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [5], 'freed': [], 'promoted': []}]),\n  ('promotion at the tenuring threshold',\n   ({1: ['old', 184, [None, None]],\n     2: ['old', 320, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [], 'freed': [], 'promoted': [11, 12]},\n    {'cards': [], 'freed': [], 'promoted': []}]),\n  ('promoted object pointing at a younger object',\n   ({1: ['old', 184, [None, None]],\n     2: ['old', 320, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [64], 'freed': [12], 'promoted': [11]},\n    {'cards': [], 'freed': [], 'promoted': [15]}]),\n  ('card of a slot in the next card',\n   ({1: ['old', 184, [None, None]],\n     2: ['old', 320, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],\n    4),\n   [{'cards': [2, 3], 'freed': [11, 12], 'promoted': []}]),\n  ('control: unreferenced young objects die',\n   ({1: ['old', 184, [None, None]],\n     2: ['old', 320, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [12],\n    [['minor']],\n    3),\n   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],\n [('regression: old-to-young edge survives two minor collections',\n   ({1: ['old', 248, [None, None]],\n     2: ['old', 384, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 1, 11], ['minor'], ['minor']],\n    5),\n   [{'cards': [4], 'freed': [13, 14], 'promoted': []}, {'cards': [4], 'freed': [], 'promoted': []}]),\n  ('edge stored after the target survived once',\n   ({1: ['old', 248, [None, None]],\n     2: ['old', 384, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [13],\n    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],\n    5),\n   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [6], 'freed': [], 'promoted': []}]),\n  ('promotion at the tenuring threshold',\n   ({1: ['old', 248, [None, None]],\n     2: ['old', 384, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [], 'freed': [], 'promoted': [11, 12]},\n    {'cards': [], 'freed': [], 'promoted': []}]),\n  ('promoted object pointing at a younger object',\n   ({1: ['old', 248, [None, None]],\n     2: ['old', 384, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [64], 'freed': [12], 'promoted': [11]},\n    {'cards': [], 'freed': [], 'promoted': [15]}]),\n  ('card of a slot in the next card',\n   ({1: ['old', 248, [None, None]],\n     2: ['old', 384, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],\n    4),\n   [{'cards': [3, 4], 'freed': [11, 12], 'promoted': []}]),\n  ('control: unreferenced young objects die',\n   ({1: ['old', 248, [None, None]],\n     2: ['old', 384, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [12],\n    [['minor']],\n    3),\n   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],\n [('regression: old-to-young edge survives two minor collections',\n   ({1: ['old', 312, [None, None]],\n     2: ['old', 448, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 1, 11], ['minor'], ['minor']],\n    5),\n   [{'cards': [5], 'freed': [13, 14], 'promoted': []}, {'cards': [5], 'freed': [], 'promoted': []}]),\n  ('edge stored after the target survived once',\n   ({1: ['old', 312, [None, None]],\n     2: ['old', 448, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [13],\n    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],\n    5),\n   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [7], 'freed': [], 'promoted': []}]),\n  ('promotion at the tenuring threshold',\n   ({1: ['old', 312, [None, None]],\n     2: ['old', 448, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [], 'freed': [], 'promoted': [11, 12]},\n    {'cards': [], 'freed': [], 'promoted': []}]),\n  ('promoted object pointing at a younger object',\n   ({1: ['old', 312, [None, None]],\n     2: ['old', 448, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [64], 'freed': [12], 'promoted': [11]},\n    {'cards': [], 'freed': [], 'promoted': [15]}]),\n  ('card of a slot in the next card',\n   ({1: ['old', 312, [None, None]],\n     2: ['old', 448, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],\n    4),\n   [{'cards': [4, 5], 'freed': [11, 12], 'promoted': []}]),\n  ('control: unreferenced young objects die',\n   ({1: ['old', 312, [None, None]],\n     2: ['old', 448, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [12],\n    [['minor']],\n    3),\n   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"7d2158bc6e632a9956a809dc57449303d093fdae071390ef163e926a0c571596","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(objs, roots, events, tenure):\n    objs = {k: {'gen': v[0], 'addr': v[1], 'fields': list(v[2]), 'age': 0} for k, v in objs.items()}\n    roots = list(roots)\n    cards = set()\n    log = []\n    next_addr = 4096\n    def slot_card(o, i):\n        return (objs[o]['addr'] + 8 * i) // 64\n    try:\n        for ev in events:\n            if ev[0] == 'store':\n                _, src, i, dst = ev\n                objs[src]['fields'][i] = dst\n                if objs[src]['gen'] == 'young' and dst is not None and objs[dst]['gen'] == 'young':\n                    cards.add(slot_card(src, i))\n            elif ev[0] == 'alloc':\n                objs[ev[1]] = {'gen': 'young', 'addr': 0, 'fields': [None], 'age': 0}\n            elif ev[0] == 'root':\n                roots.append(ev[1])\n            elif ev[0] == 'unroot':\n                roots.remove(ev[1])\n            else:\n                grey = [r for r in roots if objs[r]['gen'] == 'young']\n                for o, ob in objs.items():\n                    if ob['gen'] == 'old':\n                        for i, f in enumerate(ob['fields']):\n                            if slot_card(o, i) in cards and f is not None and objs[f]['gen'] == 'young':\n                                grey.append(f)\n                live = set()\n                while grey:\n                    y = grey.pop()\n                    if y in live:\n                        continue\n                    live.add(y)\n                    for f in objs[y]['fields']:\n                        if f is not None and objs[f]['gen'] == 'young':\n                            grey.append(f)\n                dead = sorted(k for k, ob in objs.items() if ob['gen'] == 'young' and k not in live)\n                for k in dead:\n                    del objs[k]\n                promoted = []\n                for k in sorted(live):\n                    objs[k]['age'] += 1\n                    if objs[k]['age'] >= tenure:\n                        objs[k]['gen'] = 'old'\n                        objs[k]['addr'] = next_addr\n                        next_addr += 64\n                        promoted.append(k)\n                cards = set()\n                for o in [k for k, ob in objs.items() if ob['gen'] == 'old']:\n                    for i, f in enumerate(objs[o]['fields']):\n                        if f is not None and objs[f]['gen'] == 'young':\n                            cards.add(slot_card(o, i))\n                log.append({'freed': dead, 'promoted': promoted, 'cards': sorted(cards)})\n    except KeyError as e:\n        log.append({'dangling': e.args[0]})\n    return log\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: old-to-young edge survives two minor collections',\n   ({1: ['old', 56, [None, None]],\n     2: ['old', 192, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 1, 11], ['minor'], ['minor']],\n    5),\n   [{'cards': [1], 'freed': [13, 14], 'promoted': []}, {'cards': [1], 'freed': [], 'promoted': []}]),\n  ('edge stored after the target survived once',\n   ({1: ['old', 56, [None, None]],\n     2: ['old', 192, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [13],\n    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],\n    5),\n   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]),\n  ('promotion at the tenuring threshold',\n   ({1: ['old', 56, [None, None]],\n     2: ['old', 192, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [], 'freed': [], 'promoted': [11, 12]},\n    {'cards': [], 'freed': [], 'promoted': []}]),\n  ('promoted object pointing at a younger object',\n   ({1: ['old', 56, [None, None]],\n     2: ['old', 192, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [64], 'freed': [12], 'promoted': [11]},\n    {'cards': [], 'freed': [], 'promoted': [15]}]),\n  ('card of a slot in the next card',\n   ({1: ['old', 56, [None, None]],\n     2: ['old', 192, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],\n    4),\n   [{'cards': [0, 1], 'freed': [11, 12], 'promoted': []}]),\n  ('control: unreferenced young objects die',\n   ({1: ['old', 56, [None, None]],\n     2: ['old', 192, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [12],\n    [['minor']],\n    3),\n   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],\n [('regression: old-to-young edge survives two minor collections',\n   ({1: ['old', 120, [None, None]],\n     2: ['old', 256, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 1, 11], ['minor'], ['minor']],\n    5),\n   [{'cards': [2], 'freed': [13, 14], 'promoted': []}, {'cards': [2], 'freed': [], 'promoted': []}]),\n  ('edge stored after the target survived once',\n   ({1: ['old', 120, [None, None]],\n     2: ['old', 256, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [13],\n    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],\n    5),\n   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [4], 'freed': [], 'promoted': []}]),\n  ('promotion at the tenuring threshold',\n   ({1: ['old', 120, [None, None]],\n     2: ['old', 256, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [], 'freed': [], 'promoted': [11, 12]},\n    {'cards': [], 'freed': [], 'promoted': []}]),\n  ('promoted object pointing at a younger object',\n   ({1: ['old', 120, [None, None]],\n     2: ['old', 256, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [64], 'freed': [12], 'promoted': [11]},\n    {'cards': [], 'freed': [], 'promoted': [15]}]),\n  ('card of a slot in the next card',\n   ({1: ['old', 120, [None, None]],\n     2: ['old', 256, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],\n    4),\n   [{'cards': [1, 2], 'freed': [11, 12], 'promoted': []}]),\n  ('control: unreferenced young objects die',\n   ({1: ['old', 120, [None, None]],\n     2: ['old', 256, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [12],\n    [['minor']],\n    3),\n   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],\n [('regression: old-to-young edge survives two minor collections',\n   ({1: ['old', 184, [None, None]],\n     2: ['old', 320, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 1, 11], ['minor'], ['minor']],\n    5),\n   [{'cards': [3], 'freed': [13, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]),\n  ('edge stored after the target survived once',\n   ({1: ['old', 184, [None, None]],\n     2: ['old', 320, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [13],\n    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],\n    5),\n   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [5], 'freed': [], 'promoted': []}]),\n  ('promotion at the tenuring threshold',\n   ({1: ['old', 184, [None, None]],\n     2: ['old', 320, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [], 'freed': [], 'promoted': [11, 12]},\n    {'cards': [], 'freed': [], 'promoted': []}]),\n  ('promoted object pointing at a younger object',\n   ({1: ['old', 184, [None, None]],\n     2: ['old', 320, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [64], 'freed': [12], 'promoted': [11]},\n    {'cards': [], 'freed': [], 'promoted': [15]}]),\n  ('card of a slot in the next card',\n   ({1: ['old', 184, [None, None]],\n     2: ['old', 320, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],\n    4),\n   [{'cards': [2, 3], 'freed': [11, 12], 'promoted': []}]),\n  ('control: unreferenced young objects die',\n   ({1: ['old', 184, [None, None]],\n     2: ['old', 320, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [12],\n    [['minor']],\n    3),\n   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],\n [('regression: old-to-young edge survives two minor collections',\n   ({1: ['old', 248, [None, None]],\n     2: ['old', 384, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 1, 11], ['minor'], ['minor']],\n    5),\n   [{'cards': [4], 'freed': [13, 14], 'promoted': []}, {'cards': [4], 'freed': [], 'promoted': []}]),\n  ('edge stored after the target survived once',\n   ({1: ['old', 248, [None, None]],\n     2: ['old', 384, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [13],\n    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],\n    5),\n   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [6], 'freed': [], 'promoted': []}]),\n  ('promotion at the tenuring threshold',\n   ({1: ['old', 248, [None, None]],\n     2: ['old', 384, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [], 'freed': [], 'promoted': [11, 12]},\n    {'cards': [], 'freed': [], 'promoted': []}]),\n  ('promoted object pointing at a younger object',\n   ({1: ['old', 248, [None, None]],\n     2: ['old', 384, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [64], 'freed': [12], 'promoted': [11]},\n    {'cards': [], 'freed': [], 'promoted': [15]}]),\n  ('card of a slot in the next card',\n   ({1: ['old', 248, [None, None]],\n     2: ['old', 384, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],\n    4),\n   [{'cards': [3, 4], 'freed': [11, 12], 'promoted': []}]),\n  ('control: unreferenced young objects die',\n   ({1: ['old', 248, [None, None]],\n     2: ['old', 384, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [12],\n    [['minor']],\n    3),\n   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],\n [('regression: old-to-young edge survives two minor collections',\n   ({1: ['old', 312, [None, None]],\n     2: ['old', 448, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 1, 11], ['minor'], ['minor']],\n    5),\n   [{'cards': [5], 'freed': [13, 14], 'promoted': []}, {'cards': [5], 'freed': [], 'promoted': []}]),\n  ('edge stored after the target survived once',\n   ({1: ['old', 312, [None, None]],\n     2: ['old', 448, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [13],\n    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],\n    5),\n   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [7], 'freed': [], 'promoted': []}]),\n  ('promotion at the tenuring threshold',\n   ({1: ['old', 312, [None, None]],\n     2: ['old', 448, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [], 'freed': [], 'promoted': [11, 12]},\n    {'cards': [], 'freed': [], 'promoted': []}]),\n  ('promoted object pointing at a younger object',\n   ({1: ['old', 312, [None, None]],\n     2: ['old', 448, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [11],\n    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],\n    2),\n   [{'cards': [], 'freed': [13, 14], 'promoted': []},\n    {'cards': [64], 'freed': [12], 'promoted': [11]},\n    {'cards': [], 'freed': [], 'promoted': [15]}]),\n  ('card of a slot in the next card',\n   ({1: ['old', 312, [None, None]],\n     2: ['old', 448, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [],\n    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],\n    4),\n   [{'cards': [4, 5], 'freed': [11, 12], 'promoted': []}]),\n  ('control: unreferenced young objects die',\n   ({1: ['old', 312, [None, None]],\n     2: ['old', 448, [None]],\n     11: ['young', 0, [12]],\n     12: ['young', 0, []],\n     13: ['young', 0, []],\n     14: ['young', 0, [None]]},\n    [12],\n    [['minor']],\n    3),\n   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-garbage-collector-invariants-generational-card-marking-barrier-filter","generated_at":"2026-09-29T14:51:27.660472+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Minor collections are only correct if the remembered set covers every old-to-young pointer.","root_cause":"The post-write barrier checks for a young source instead of an old one.","sha256":"f836ea6fd6debadbf9c4c260bb9b87669c794f85685dd2ea4454245f93d72d57","title":"Card marking: barrier records young-to-young stores · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verified":true,"visibility":"public","verification":{"attempt":{"elapsed_ms":42.379,"exit_code":1,"observations":[{"actual":[{"cards":[1],"freed":[13,14],"promoted":[]},{"cards":[1],"freed":[],"promoted":[]}],"check":"regression: old-to-young edge survives two minor collections","expected":[{"cards":[1],"freed":[13,14],"promoted":[]},{"cards":[1],"freed":[],"promoted":[]}],"passed":true},{"actual":[{"cards":[],"freed":[11,12,14],"promoted":[]},{"dangling":13}],"check":"edge stored after the target survived once","expected":[{"cards":[],"freed":[11,12,14],"promoted":[]},{"cards":[3],"freed":[],"promoted":[]}],"passed":false},{"actual":[{"cards":[],"freed":[13,14],"promoted":[]},{"cards":[],"freed":[],"promoted":[11,12]},{"cards":[],"freed":[],"promoted":[]}],"check":"promotion at the tenuring threshold","expected":[{"cards":[],"freed":[13,14],"promoted":[]},{"cards":[],"freed":[],"promoted":[11,12]},{"cards":[],"freed":[],"promoted":[]}],"passed":true},{"actual":[{"cards":[],"freed":[13,14],"promoted":[]},{"cards":[64],"freed":[12],"promoted":[11]},{"cards":[],"freed":[],"promoted":[15]}],"check":"promoted object pointing at a younger object","expected":[{"cards":[],"freed":[13,14],"promoted":[]},{"cards":[64],"freed":[12],"promoted":[11]},{"cards":[],"freed":[],"promoted":[15]}],"passed":true},{"actual":[{"cards":[0,1],"freed":[11,12],"promoted":[]}],"check":"card of a slot in the next card","expected":[{"cards":[0,1],"freed":[11,12],"promoted":[]}],"passed":true},{"actual":[{"cards":[],"freed":[11,13,14],"promoted":[]}],"check":"control: unreferenced young objects die","expected":[{"cards":[],"freed":[11,13,14],"promoted":[]}],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: old-to-young edge survives two minor collections\", \"actual\": [{\"freed\": [13, 14], \"promoted\": [], \"cards\": [1]}, {\"freed\": [], \"promoted\": [], \"cards\": [1]}], \"expected\": [{\"cards\": [1], \"freed\": [13, 14], \"promoted\": []}, {\"cards\": [1], \"freed\": [], \"promoted\": []}], \"passed\": true}, {\"check\": \"edge stored after the target survived once\", \"actual\": [{\"freed\": [11, 12, 14], \"promoted\": [], \"cards\": []}, {\"dangling\": 13}], \"expected\": [{\"cards\": [], \"freed\": [11, 12, 14], \"promoted\": []}, {\"cards\": [3], \"freed\": [], \"promoted\": []}], \"passed\": false}, {\"check\": \"promotion at the tenuring threshold\", \"actual\": [{\"freed\": [13, 14], \"promoted\": [], \"cards\": []}, {\"freed\": [], \"promoted\": [11, 12], \"cards\": []}, {\"freed\": [], \"promoted\": [], \"cards\": []}], \"expected\": [{\"cards\": [], \"freed\": [13, 14], \"promoted\": []}, {\"cards\": [], \"freed\": [], \"promoted\": [11, 12]}, {\"cards\": [], \"freed\": [], \"promoted\": []}], \"passed\": true}, {\"check\": \"promoted object pointing at a younger object\", \"actual\": [{\"freed\": [13, 14], \"promoted\": [], \"cards\": []}, {\"freed\": [12], \"promoted\": [11], \"cards\": [64]}, {\"freed\": [], \"promoted\": [15], \"cards\": []}], \"expected\": [{\"cards\": [], \"freed\": [13, 14], \"promoted\": []}, {\"cards\": [64], \"freed\": [12], \"promoted\": [11]}, {\"cards\": [], \"freed\": [], \"promoted\": [15]}], \"passed\": true}, {\"check\": \"card of a slot in the next card\", \"actual\": [{\"freed\": [11, 12], \"promoted\": [], \"cards\": [0, 1]}], \"expected\": [{\"cards\": [0, 1], \"freed\": [11, 12], \"promoted\": []}], \"passed\": true}, {\"check\": \"control: unreferenced young objects die\", \"actual\": [{\"freed\": [11, 13, 14], \"promoted\": [], \"cards\": []}], \"expected\": [{\"cards\": [], \"freed\": [11, 13, 14], \"promoted\": []}], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":42.586,"exit_code":1,"observations":[{"actual":[{"dangling":11}],"check":"regression: old-to-young edge survives two minor collections","expected":[{"cards":[1],"freed":[13,14],"promoted":[]},{"cards":[1],"freed":[],"promoted":[]}],"passed":false},{"actual":[{"cards":[],"freed":[11,12,14],"promoted":[]},{"dangling":13}],"check":"edge stored after the target survived once","expected":[{"cards":[],"freed":[11,12,14],"promoted":[]},{"cards":[3],"freed":[],"promoted":[]}],"passed":false},{"actual":[{"cards":[],"freed":[13,14],"promoted":[]},{"cards":[],"freed":[],"promoted":[11,12]},{"cards":[],"freed":[],"promoted":[]}],"check":"promotion at the tenuring threshold","expected":[{"cards":[],"freed":[13,14],"promoted":[]},{"cards":[],"freed":[],"promoted":[11,12]},{"cards":[],"freed":[],"promoted":[]}],"passed":true},{"actual":[{"cards":[],"freed":[13,14],"promoted":[]},{"cards":[64],"freed":[12],"promoted":[11]},{"cards":[],"freed":[],"promoted":[15]}],"check":"promoted object pointing at a younger object","expected":[{"cards":[],"freed":[13,14],"promoted":[]},{"cards":[64],"freed":[12],"promoted":[11]},{"cards":[],"freed":[],"promoted":[15]}],"passed":true},{"actual":[{"dangling":13}],"check":"card of a slot in the next card","expected":[{"cards":[0,1],"freed":[11,12],"promoted":[]}],"passed":false},{"actual":[{"cards":[],"freed":[11,13,14],"promoted":[]}],"check":"control: unreferenced young objects die","expected":[{"cards":[],"freed":[11,13,14],"promoted":[]}],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: old-to-young edge survives two minor collections\", \"actual\": [{\"dangling\": 11}], \"expected\": [{\"cards\": [1], \"freed\": [13, 14], \"promoted\": []}, {\"cards\": [1], \"freed\": [], \"promoted\": []}], \"passed\": false}, {\"check\": \"edge stored after the target survived once\", \"actual\": [{\"freed\": [11, 12, 14], \"promoted\": [], \"cards\": []}, {\"dangling\": 13}], \"expected\": [{\"cards\": [], \"freed\": [11, 12, 14], \"promoted\": []}, {\"cards\": [3], \"freed\": [], \"promoted\": []}], \"passed\": false}, {\"check\": \"promotion at the tenuring threshold\", \"actual\": [{\"freed\": [13, 14], \"promoted\": [], \"cards\": []}, {\"freed\": [], \"promoted\": [11, 12], \"cards\": []}, {\"freed\": [], \"promoted\": [], \"cards\": []}], \"expected\": [{\"cards\": [], \"freed\": [13, 14], \"promoted\": []}, {\"cards\": [], \"freed\": [], \"promoted\": [11, 12]}, {\"cards\": [], \"freed\": [], \"promoted\": []}], \"passed\": true}, {\"check\": \"promoted object pointing at a younger object\", \"actual\": [{\"freed\": [13, 14], \"promoted\": [], \"cards\": []}, {\"freed\": [12], \"promoted\": [11], \"cards\": [64]}, {\"freed\": [], \"promoted\": [15], \"cards\": []}], \"expected\": [{\"cards\": [], \"freed\": [13, 14], \"promoted\": []}, {\"cards\": [64], \"freed\": [12], \"promoted\": [11]}, {\"cards\": [], \"freed\": [], \"promoted\": [15]}], \"passed\": true}, {\"check\": \"card of a slot in the next card\", \"actual\": [{\"dangling\": 13}], \"expected\": [{\"cards\": [0, 1], \"freed\": [11, 12], \"promoted\": []}], \"passed\": false}, {\"check\": \"control: unreferenced young objects die\", \"actual\": [{\"freed\": [11, 13, 14], \"promoted\": [], \"cards\": []}], \"expected\": [{\"cards\": [], \"freed\": [11, 13, 14], \"promoted\": []}], \"passed\": true}], \"passed\": false}\n"}},"member_only":{"stages":["fixed"],"fields":["implementations.fixed","verification.fixed","harness","repair"],"note":"The verified repair, its recorded checks, the repair description, and the scoring harness are available to members."}}