broken_source:
"""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)

source:
"""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)

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

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}.

split: open-access


broken_source:
"""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 promoted:
                    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)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""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' and k not in promoted]:
                    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)

prompt:
Old-to-young references recorded before a minor collection are forgotten afterwards.

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}.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(heap, roots, weak, finalizable, phantom, cycles):
    heap = {k: list(v) for k, v in heap.items()}
    weak = {r: t for r, t in weak}
    phantom = {r: t for r, t in phantom}
    pending = set(finalizable)
    out = []
    def trace(starts, seen):
        stack = list(starts)
        while stack:
            o = stack.pop()
            if o is None or o in seen or o not in heap:
                continue
            seen.add(o)
            stack.extend(heap[o])
        return seen
    for _ in range(cycles):
        strong = trace(roots, set())
        to_final = sorted(o for o in pending if o not in strong and o in heap)
        reach = trace(to_final, set(strong))
        cleared = sorted(r for r, t in weak.items() if t is not None and t not in reach)
        for r in cleared:
            weak[r] = None
        pending -= set(to_final)
        enq = sorted(r for r, t in phantom.items() if t is not None and t not in reach)
        for r in enq:
            phantom[r] = None
        freed = sorted(o for o in heap if o not in reach)
        for o in freed:
            del heap[o]
        out.append({'weak': cleared, 'finalize': to_final, 'phantom': enq, 'freed': freed})
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: finalizable object over two cycles',
   ({11: [12], 12: [], 13: [14], 14: [15], 15: [], 16: []},
    [11],
    [['w1', 13], ['w2', 12]],
    [13],
    [['p1', 14], ['p2', 16]],
    2),
   [{'finalize': [13], 'freed': [16], 'phantom': ['p2'], 'weak': ['w1']},
    {'finalize': [], 'freed': [13, 14, 15], 'phantom': ['p1'], 'weak': []}]),
  ('weak reference to a resurrected object',
   ({11: [12], 12: [], 13: [14], 14: [15], 15: [], 16: []}, [11], [['w1', 13]], [13], [], 1),
   [{'finalize': [13], 'freed': [16], 'phantom': [], 'weak': ['w1']}]),
  ('finalizer runs only once',
   ({11: [12], 12: [], 13: [14], 14: [15], 15: [], 16: []}, [11], [], [13], [], 3),
   [{'finalize': [13], 'freed': [16], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [13, 14, 15], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}]),
  ('children of a finalizable object stay alive',
   ({11: [12], 12: [], 13: [14], 14: [15], 15: [], 16: []}, [11], [], [13], [['p1', 15]], 1),
   [{'finalize': [13], 'freed': [16], 'phantom': [], 'weak': []}]),
  ('phantom of an object only reachable from a finalizable one',
   ({11: [12], 12: [], 13: [14], 14: [15], 15: [], 16: []}, [11], [], [13], [['p1', 14]], 2),
   [{'finalize': [13], 'freed': [16], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [13, 14, 15], 'phantom': ['p1'], 'weak': []}]),
  ('control: all strongly reachable',
   ({11: [12], 12: [], 13: [14], 14: [15], 15: [], 16: []},
    [11, 13, 16],
    [['w1', 13], ['w2', 12]],
    [13],
    [['p1', 14], ['p2', 16]],
    2),
   [{'finalize': [], 'freed': [], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}])],
 [('regression: finalizable object over two cycles',
   ({21: [22], 22: [], 23: [24], 24: [25], 25: [], 26: []},
    [21],
    [['w1', 23], ['w2', 22]],
    [23],
    [['p1', 24], ['p2', 26]],
    2),
   [{'finalize': [23], 'freed': [26], 'phantom': ['p2'], 'weak': ['w1']},
    {'finalize': [], 'freed': [23, 24, 25], 'phantom': ['p1'], 'weak': []}]),
  ('weak reference to a resurrected object',
   ({21: [22], 22: [], 23: [24], 24: [25], 25: [], 26: []}, [21], [['w1', 23]], [23], [], 1),
   [{'finalize': [23], 'freed': [26], 'phantom': [], 'weak': ['w1']}]),
  ('finalizer runs only once',
   ({21: [22], 22: [], 23: [24], 24: [25], 25: [], 26: []}, [21], [], [23], [], 3),
   [{'finalize': [23], 'freed': [26], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [23, 24, 25], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}]),
  ('children of a finalizable object stay alive',
   ({21: [22], 22: [], 23: [24], 24: [25], 25: [], 26: []}, [21], [], [23], [['p1', 25]], 1),
   [{'finalize': [23], 'freed': [26], 'phantom': [], 'weak': []}]),
  ('phantom of an object only reachable from a finalizable one',
   ({21: [22], 22: [], 23: [24], 24: [25], 25: [], 26: []}, [21], [], [23], [['p1', 24]], 2),
   [{'finalize': [23], 'freed': [26], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [23, 24, 25], 'phantom': ['p1'], 'weak': []}]),
  ('control: all strongly reachable',
   ({21: [22], 22: [], 23: [24], 24: [25], 25: [], 26: []},
    [21, 23, 26],
    [['w1', 23], ['w2', 22]],
    [23],
    [['p1', 24], ['p2', 26]],
    2),
   [{'finalize': [], 'freed': [], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}])],
 [('regression: finalizable object over two cycles',
   ({31: [32], 32: [], 33: [34], 34: [35], 35: [], 36: []},
    [31],
    [['w1', 33], ['w2', 32]],
    [33],
    [['p1', 34], ['p2', 36]],
    2),
   [{'finalize': [33], 'freed': [36], 'phantom': ['p2'], 'weak': ['w1']},
    {'finalize': [], 'freed': [33, 34, 35], 'phantom': ['p1'], 'weak': []}]),
  ('weak reference to a resurrected object',
   ({31: [32], 32: [], 33: [34], 34: [35], 35: [], 36: []}, [31], [['w1', 33]], [33], [], 1),
   [{'finalize': [33], 'freed': [36], 'phantom': [], 'weak': ['w1']}]),
  ('finalizer runs only once',
   ({31: [32], 32: [], 33: [34], 34: [35], 35: [], 36: []}, [31], [], [33], [], 3),
   [{'finalize': [33], 'freed': [36], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [33, 34, 35], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}]),
  ('children of a finalizable object stay alive',
   ({31: [32], 32: [], 33: [34], 34: [35], 35: [], 36: []}, [31], [], [33], [['p1', 35]], 1),
   [{'finalize': [33], 'freed': [36], 'phantom': [], 'weak': []}]),
  ('phantom of an object only reachable from a finalizable one',
   ({31: [32], 32: [], 33: [34], 34: [35], 35: [], 36: []}, [31], [], [33], [['p1', 34]], 2),
   [{'finalize': [33], 'freed': [36], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [33, 34, 35], 'phantom': ['p1'], 'weak': []}]),
  ('control: all strongly reachable',
   ({31: [32], 32: [], 33: [34], 34: [35], 35: [], 36: []},
    [31, 33, 36],
    [['w1', 33], ['w2', 32]],
    [33],
    [['p1', 34], ['p2', 36]],
    2),
   [{'finalize': [], 'freed': [], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}])],
 [('regression: finalizable object over two cycles',
   ({41: [42], 42: [], 43: [44], 44: [45], 45: [], 46: []},
    [41],
    [['w1', 43], ['w2', 42]],
    [43],
    [['p1', 44], ['p2', 46]],
    2),
   [{'finalize': [43], 'freed': [46], 'phantom': ['p2'], 'weak': ['w1']},
    {'finalize': [], 'freed': [43, 44, 45], 'phantom': ['p1'], 'weak': []}]),
  ('weak reference to a resurrected object',
   ({41: [42], 42: [], 43: [44], 44: [45], 45: [], 46: []}, [41], [['w1', 43]], [43], [], 1),
   [{'finalize': [43], 'freed': [46], 'phantom': [], 'weak': ['w1']}]),
  ('finalizer runs only once',
   ({41: [42], 42: [], 43: [44], 44: [45], 45: [], 46: []}, [41], [], [43], [], 3),
   [{'finalize': [43], 'freed': [46], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [43, 44, 45], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}]),
  ('children of a finalizable object stay alive',
   ({41: [42], 42: [], 43: [44], 44: [45], 45: [], 46: []}, [41], [], [43], [['p1', 45]], 1),
   [{'finalize': [43], 'freed': [46], 'phantom': [], 'weak': []}]),
  ('phantom of an object only reachable from a finalizable one',
   ({41: [42], 42: [], 43: [44], 44: [45], 45: [], 46: []}, [41], [], [43], [['p1', 44]], 2),
   [{'finalize': [43], 'freed': [46], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [43, 44, 45], 'phantom': ['p1'], 'weak': []}]),
  ('control: all strongly reachable',
   ({41: [42], 42: [], 43: [44], 44: [45], 45: [], 46: []},
    [41, 43, 46],
    [['w1', 43], ['w2', 42]],
    [43],
    [['p1', 44], ['p2', 46]],
    2),
   [{'finalize': [], 'freed': [], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}])],
 [('regression: finalizable object over two cycles',
   ({51: [52], 52: [], 53: [54], 54: [55], 55: [], 56: []},
    [51],
    [['w1', 53], ['w2', 52]],
    [53],
    [['p1', 54], ['p2', 56]],
    2),
   [{'finalize': [53], 'freed': [56], 'phantom': ['p2'], 'weak': ['w1']},
    {'finalize': [], 'freed': [53, 54, 55], 'phantom': ['p1'], 'weak': []}]),
  ('weak reference to a resurrected object',
   ({51: [52], 52: [], 53: [54], 54: [55], 55: [], 56: []}, [51], [['w1', 53]], [53], [], 1),
   [{'finalize': [53], 'freed': [56], 'phantom': [], 'weak': ['w1']}]),
  ('finalizer runs only once',
   ({51: [52], 52: [], 53: [54], 54: [55], 55: [], 56: []}, [51], [], [53], [], 3),
   [{'finalize': [53], 'freed': [56], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [53, 54, 55], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}]),
  ('children of a finalizable object stay alive',
   ({51: [52], 52: [], 53: [54], 54: [55], 55: [], 56: []}, [51], [], [53], [['p1', 55]], 1),
   [{'finalize': [53], 'freed': [56], 'phantom': [], 'weak': []}]),
  ('phantom of an object only reachable from a finalizable one',
   ({51: [52], 52: [], 53: [54], 54: [55], 55: [], 56: []}, [51], [], [53], [['p1', 54]], 2),
   [{'finalize': [53], 'freed': [56], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [53, 54, 55], 'phantom': ['p1'], 'weak': []}]),
  ('control: all strongly reachable',
   ({51: [52], 52: [], 53: [54], 54: [55], 55: [], 56: []},
    [51, 53, 56],
    [['w1', 53], ['w2', 52]],
    [53],
    [['p1', 54], ['p2', 56]],
    2),
   [{'finalize': [], 'freed': [], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}])]]
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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(heap, roots, weak, finalizable, phantom, cycles):
    heap = {k: list(v) for k, v in heap.items()}
    weak = {r: t for r, t in weak}
    phantom = {r: t for r, t in phantom}
    pending = set(finalizable)
    out = []
    def trace(starts, seen):
        stack = list(starts)
        while stack:
            o = stack.pop()
            if o is None or o in seen or o not in heap:
                continue
            seen.add(o)
            stack.extend(heap[o])
        return seen
    for _ in range(cycles):
        strong = trace(roots, set())
        to_final = sorted(o for o in pending if o not in strong and o in heap)
        reach = trace(to_final, set(strong))
        cleared = sorted(r for r, t in weak.items() if t is not None and t not in strong and t not in to_final)
        for r in cleared:
            weak[r] = None
        pending -= set(to_final)
        enq = sorted(r for r, t in phantom.items() if t is not None and t not in reach)
        for r in enq:
            phantom[r] = None
        freed = sorted(o for o in heap if o not in reach)
        for o in freed:
            del heap[o]
        out.append({'weak': cleared, 'finalize': to_final, 'phantom': enq, 'freed': freed})
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: finalizable object over two cycles',
   ({11: [12], 12: [], 13: [14], 14: [15], 15: [], 16: []},
    [11],
    [['w1', 13], ['w2', 12]],
    [13],
    [['p1', 14], ['p2', 16]],
    2),
   [{'finalize': [13], 'freed': [16], 'phantom': ['p2'], 'weak': ['w1']},
    {'finalize': [], 'freed': [13, 14, 15], 'phantom': ['p1'], 'weak': []}]),
  ('weak reference to a resurrected object',
   ({11: [12], 12: [], 13: [14], 14: [15], 15: [], 16: []}, [11], [['w1', 13]], [13], [], 1),
   [{'finalize': [13], 'freed': [16], 'phantom': [], 'weak': ['w1']}]),
  ('finalizer runs only once',
   ({11: [12], 12: [], 13: [14], 14: [15], 15: [], 16: []}, [11], [], [13], [], 3),
   [{'finalize': [13], 'freed': [16], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [13, 14, 15], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}]),
  ('children of a finalizable object stay alive',
   ({11: [12], 12: [], 13: [14], 14: [15], 15: [], 16: []}, [11], [], [13], [['p1', 15]], 1),
   [{'finalize': [13], 'freed': [16], 'phantom': [], 'weak': []}]),
  ('phantom of an object only reachable from a finalizable one',
   ({11: [12], 12: [], 13: [14], 14: [15], 15: [], 16: []}, [11], [], [13], [['p1', 14]], 2),
   [{'finalize': [13], 'freed': [16], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [13, 14, 15], 'phantom': ['p1'], 'weak': []}]),
  ('control: all strongly reachable',
   ({11: [12], 12: [], 13: [14], 14: [15], 15: [], 16: []},
    [11, 13, 16],
    [['w1', 13], ['w2', 12]],
    [13],
    [['p1', 14], ['p2', 16]],
    2),
   [{'finalize': [], 'freed': [], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}])],
 [('regression: finalizable object over two cycles',
   ({21: [22], 22: [], 23: [24], 24: [25], 25: [], 26: []},
    [21],
    [['w1', 23], ['w2', 22]],
    [23],
    [['p1', 24], ['p2', 26]],
    2),
   [{'finalize': [23], 'freed': [26], 'phantom': ['p2'], 'weak': ['w1']},
    {'finalize': [], 'freed': [23, 24, 25], 'phantom': ['p1'], 'weak': []}]),
  ('weak reference to a resurrected object',
   ({21: [22], 22: [], 23: [24], 24: [25], 25: [], 26: []}, [21], [['w1', 23]], [23], [], 1),
   [{'finalize': [23], 'freed': [26], 'phantom': [], 'weak': ['w1']}]),
  ('finalizer runs only once',
   ({21: [22], 22: [], 23: [24], 24: [25], 25: [], 26: []}, [21], [], [23], [], 3),
   [{'finalize': [23], 'freed': [26], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [23, 24, 25], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}]),
  ('children of a finalizable object stay alive',
   ({21: [22], 22: [], 23: [24], 24: [25], 25: [], 26: []}, [21], [], [23], [['p1', 25]], 1),
   [{'finalize': [23], 'freed': [26], 'phantom': [], 'weak': []}]),
  ('phantom of an object only reachable from a finalizable one',
   ({21: [22], 22: [], 23: [24], 24: [25], 25: [], 26: []}, [21], [], [23], [['p1', 24]], 2),
   [{'finalize': [23], 'freed': [26], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [23, 24, 25], 'phantom': ['p1'], 'weak': []}]),
  ('control: all strongly reachable',
   ({21: [22], 22: [], 23: [24], 24: [25], 25: [], 26: []},
    [21, 23, 26],
    [['w1', 23], ['w2', 22]],
    [23],
    [['p1', 24], ['p2', 26]],
    2),
   [{'finalize': [], 'freed': [], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}])],
 [('regression: finalizable object over two cycles',
   ({31: [32], 32: [], 33: [34], 34: [35], 35: [], 36: []},
    [31],
    [['w1', 33], ['w2', 32]],
    [33],
    [['p1', 34], ['p2', 36]],
    2),
   [{'finalize': [33], 'freed': [36], 'phantom': ['p2'], 'weak': ['w1']},
    {'finalize': [], 'freed': [33, 34, 35], 'phantom': ['p1'], 'weak': []}]),
  ('weak reference to a resurrected object',
   ({31: [32], 32: [], 33: [34], 34: [35], 35: [], 36: []}, [31], [['w1', 33]], [33], [], 1),
   [{'finalize': [33], 'freed': [36], 'phantom': [], 'weak': ['w1']}]),
  ('finalizer runs only once',
   ({31: [32], 32: [], 33: [34], 34: [35], 35: [], 36: []}, [31], [], [33], [], 3),
   [{'finalize': [33], 'freed': [36], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [33, 34, 35], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}]),
  ('children of a finalizable object stay alive',
   ({31: [32], 32: [], 33: [34], 34: [35], 35: [], 36: []}, [31], [], [33], [['p1', 35]], 1),
   [{'finalize': [33], 'freed': [36], 'phantom': [], 'weak': []}]),
  ('phantom of an object only reachable from a finalizable one',
   ({31: [32], 32: [], 33: [34], 34: [35], 35: [], 36: []}, [31], [], [33], [['p1', 34]], 2),
   [{'finalize': [33], 'freed': [36], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [33, 34, 35], 'phantom': ['p1'], 'weak': []}]),
  ('control: all strongly reachable',
   ({31: [32], 32: [], 33: [34], 34: [35], 35: [], 36: []},
    [31, 33, 36],
    [['w1', 33], ['w2', 32]],
    [33],
    [['p1', 34], ['p2', 36]],
    2),
   [{'finalize': [], 'freed': [], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}])],
 [('regression: finalizable object over two cycles',
   ({41: [42], 42: [], 43: [44], 44: [45], 45: [], 46: []},
    [41],
    [['w1', 43], ['w2', 42]],
    [43],
    [['p1', 44], ['p2', 46]],
    2),
   [{'finalize': [43], 'freed': [46], 'phantom': ['p2'], 'weak': ['w1']},
    {'finalize': [], 'freed': [43, 44, 45], 'phantom': ['p1'], 'weak': []}]),
  ('weak reference to a resurrected object',
   ({41: [42], 42: [], 43: [44], 44: [45], 45: [], 46: []}, [41], [['w1', 43]], [43], [], 1),
   [{'finalize': [43], 'freed': [46], 'phantom': [], 'weak': ['w1']}]),
  ('finalizer runs only once',
   ({41: [42], 42: [], 43: [44], 44: [45], 45: [], 46: []}, [41], [], [43], [], 3),
   [{'finalize': [43], 'freed': [46], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [43, 44, 45], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}]),
  ('children of a finalizable object stay alive',
   ({41: [42], 42: [], 43: [44], 44: [45], 45: [], 46: []}, [41], [], [43], [['p1', 45]], 1),
   [{'finalize': [43], 'freed': [46], 'phantom': [], 'weak': []}]),
  ('phantom of an object only reachable from a finalizable one',
   ({41: [42], 42: [], 43: [44], 44: [45], 45: [], 46: []}, [41], [], [43], [['p1', 44]], 2),
   [{'finalize': [43], 'freed': [46], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [43, 44, 45], 'phantom': ['p1'], 'weak': []}]),
  ('control: all strongly reachable',
   ({41: [42], 42: [], 43: [44], 44: [45], 45: [], 46: []},
    [41, 43, 46],
    [['w1', 43], ['w2', 42]],
    [43],
    [['p1', 44], ['p2', 46]],
    2),
   [{'finalize': [], 'freed': [], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}])],
 [('regression: finalizable object over two cycles',
   ({51: [52], 52: [], 53: [54], 54: [55], 55: [], 56: []},
    [51],
    [['w1', 53], ['w2', 52]],
    [53],
    [['p1', 54], ['p2', 56]],
    2),
   [{'finalize': [53], 'freed': [56], 'phantom': ['p2'], 'weak': ['w1']},
    {'finalize': [], 'freed': [53, 54, 55], 'phantom': ['p1'], 'weak': []}]),
  ('weak reference to a resurrected object',
   ({51: [52], 52: [], 53: [54], 54: [55], 55: [], 56: []}, [51], [['w1', 53]], [53], [], 1),
   [{'finalize': [53], 'freed': [56], 'phantom': [], 'weak': ['w1']}]),
  ('finalizer runs only once',
   ({51: [52], 52: [], 53: [54], 54: [55], 55: [], 56: []}, [51], [], [53], [], 3),
   [{'finalize': [53], 'freed': [56], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [53, 54, 55], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}]),
  ('children of a finalizable object stay alive',
   ({51: [52], 52: [], 53: [54], 54: [55], 55: [], 56: []}, [51], [], [53], [['p1', 55]], 1),
   [{'finalize': [53], 'freed': [56], 'phantom': [], 'weak': []}]),
  ('phantom of an object only reachable from a finalizable one',
   ({51: [52], 52: [], 53: [54], 54: [55], 55: [], 56: []}, [51], [], [53], [['p1', 54]], 2),
   [{'finalize': [53], 'freed': [56], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [53, 54, 55], 'phantom': ['p1'], 'weak': []}]),
  ('control: all strongly reachable',
   ({51: [52], 52: [], 53: [54], 54: [55], 55: [], 56: []},
    [51, 53, 56],
    [['w1', 53], ['w2', 52]],
    [53],
    [['p1', 54], ['p2', 56]],
    2),
   [{'finalize': [], 'freed': [], 'phantom': [], 'weak': []},
    {'finalize': [], 'freed': [], 'phantom': [], 'weak': []}])]]
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)

prompt:
A weak reference still returns an object that is about to be finalized.

Each cycle: trace strong reachability from roots (weak and phantom references are not traced); weak references whose referent is not strongly reachable are cleared; pending finalizable objects that are not strongly reachable are queued for finalization once and resurrected together with everything they reach for this cycle; phantom references are enqueued only when their referent is not reachable even through the resurrected set; everything else is freed. Return per cycle the cleared weak refs, finalized objects, enqueued phantoms and freed objects.

split: open-access