{"abstract":"Clearing work is scheduled for tables that are themselves garbage.","category":"Garbage collector invariants","checks":7,"contract":"Ephemeron entries [table, key, value]: the value is traced only when both the table and the key are reachable; values may make further keys reachable, so iterate to a fixpoint. Keys and tables are never retained by an entry. Return the sorted live set and the [table, key] entries of live tables whose key died (to be cleared).","evaluation_group":"w2-garbage-collector-invariants-ephemeron-tables","failed_approach":"Keying the report on dead values misses dead keys whose values survive through other paths.","family":"w2-garbage-collector-invariants-ephemeron-tables-clearing-criterion","id":"FA-90566","implementations":{"attempt":{"sha256":"871d02a4712d96d4764fb6011a28edd5053a3a260d1ebf767ac6d24e9ac77b56","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(heap, roots, eph):\n    live = set()\n    def mark(starts):\n        stack = list(starts)\n        while stack:\n            o = stack.pop()\n            if o in live:\n                continue\n            live.add(o)\n            stack.extend(heap.get(o, []))\n    mark(roots)\n    changed = True\n    while changed:\n        changed = False\n        for table, k, v in eph:\n            if table in live and k in live and v not in live:\n                mark([v])\n                changed = True\n    cleared = sorted([t, k] for t, k, v in eph if t in live and v not in live)\n    return {'live': sorted(live), 'cleared': cleared}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: ephemeron chain listed in reverse',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1']]),\n   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),\n  ('dead key does not retain its value',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['T1', 'K2_1', 'V4_1']]),\n   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),\n  ('dead table does not retain values',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['U1', 'K1_1', 'V5_1']]),\n   {'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),\n  ('dead key in a dead table is not reported',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['U1', 'K2_1', 'V6_1'], ['T1', 'K1_1', 'V1_1']]),\n   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),\n  ('dead key whose value is live elsewhere',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['T1', 'K3_1', 'V7_1'], ['T1', 'K1_1', 'V1_1']]),\n   {'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),\n  ('value reached through a key held only by another value',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1'], ['T1', 'K2_1', 'V4_1']]),\n   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),\n  ('control: plain reachability',\n   ({'a1': ['b1'], 'root': ['a1']}, ['root'], []),\n   {'cleared': [], 'live': ['a1', 'b1', 'root']})],\n [('regression: ephemeron chain listed in reverse',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2']]),\n   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),\n  ('dead key does not retain its value',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['T2', 'K2_2', 'V4_2']]),\n   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),\n  ('dead table does not retain values',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['U2', 'K1_2', 'V5_2']]),\n   {'cleared': [], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),\n  ('dead key in a dead table is not reported',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['U2', 'K2_2', 'V6_2'], ['T2', 'K1_2', 'V1_2']]),\n   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),\n  ('dead key whose value is live elsewhere',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['T2', 'K3_2', 'V7_2'], ['T2', 'K1_2', 'V1_2']]),\n   {'cleared': [['T2', 'K3_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),\n  ('value reached through a key held only by another value',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2'], ['T2', 'K2_2', 'V4_2']]),\n   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),\n  ('control: plain reachability',\n   ({'a2': ['b2'], 'root': ['a2']}, ['root'], []),\n   {'cleared': [], 'live': ['a2', 'b2', 'root']})],\n [('regression: ephemeron chain listed in reverse',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3']]),\n   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),\n  ('dead key does not retain its value',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['T3', 'K2_3', 'V4_3']]),\n   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),\n  ('dead table does not retain values',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['U3', 'K1_3', 'V5_3']]),\n   {'cleared': [], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),\n  ('dead key in a dead table is not reported',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['U3', 'K2_3', 'V6_3'], ['T3', 'K1_3', 'V1_3']]),\n   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),\n  ('dead key whose value is live elsewhere',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['T3', 'K3_3', 'V7_3'], ['T3', 'K1_3', 'V1_3']]),\n   {'cleared': [['T3', 'K3_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),\n  ('value reached through a key held only by another value',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3'], ['T3', 'K2_3', 'V4_3']]),\n   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),\n  ('control: plain reachability',\n   ({'a3': ['b3'], 'root': ['a3']}, ['root'], []),\n   {'cleared': [], 'live': ['a3', 'b3', 'root']})],\n [('regression: ephemeron chain listed in reverse',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4']]),\n   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),\n  ('dead key does not retain its value',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['T4', 'K2_4', 'V4_4']]),\n   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),\n  ('dead table does not retain values',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['U4', 'K1_4', 'V5_4']]),\n   {'cleared': [], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),\n  ('dead key in a dead table is not reported',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['U4', 'K2_4', 'V6_4'], ['T4', 'K1_4', 'V1_4']]),\n   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),\n  ('dead key whose value is live elsewhere',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['T4', 'K3_4', 'V7_4'], ['T4', 'K1_4', 'V1_4']]),\n   {'cleared': [['T4', 'K3_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),\n  ('value reached through a key held only by another value',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4'], ['T4', 'K2_4', 'V4_4']]),\n   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),\n  ('control: plain reachability',\n   ({'a4': ['b4'], 'root': ['a4']}, ['root'], []),\n   {'cleared': [], 'live': ['a4', 'b4', 'root']})],\n [('regression: ephemeron chain listed in reverse',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5']]),\n   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),\n  ('dead key does not retain its value',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['T5', 'K2_5', 'V4_5']]),\n   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),\n  ('dead table does not retain values',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['U5', 'K1_5', 'V5_5']]),\n   {'cleared': [], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),\n  ('dead key in a dead table is not reported',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['U5', 'K2_5', 'V6_5'], ['T5', 'K1_5', 'V1_5']]),\n   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),\n  ('dead key whose value is live elsewhere',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['T5', 'K3_5', 'V7_5'], ['T5', 'K1_5', 'V1_5']]),\n   {'cleared': [['T5', 'K3_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),\n  ('value reached through a key held only by another value',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5'], ['T5', 'K2_5', 'V4_5']]),\n   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),\n  ('control: plain reachability',\n   ({'a5': ['b5'], 'root': ['a5']}, ['root'], []),\n   {'cleared': [], 'live': ['a5', 'b5', 'root']})]]\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":"214e845c786921e63263a8789f236373605ce0c0d69a9d87f6914393fc392e9c","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(heap, roots, eph):\n    live = set()\n    def mark(starts):\n        stack = list(starts)\n        while stack:\n            o = stack.pop()\n            if o in live:\n                continue\n            live.add(o)\n            stack.extend(heap.get(o, []))\n    mark(roots)\n    changed = True\n    while changed:\n        changed = False\n        for table, k, v in eph:\n            if table in live and k in live and v not in live:\n                mark([v])\n                changed = True\n    cleared = sorted([t, k] for t, k, v in eph if k not in live)\n    return {'live': sorted(live), 'cleared': cleared}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: ephemeron chain listed in reverse',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1']]),\n   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),\n  ('dead key does not retain its value',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['T1', 'K2_1', 'V4_1']]),\n   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),\n  ('dead table does not retain values',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['U1', 'K1_1', 'V5_1']]),\n   {'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),\n  ('dead key in a dead table is not reported',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['U1', 'K2_1', 'V6_1'], ['T1', 'K1_1', 'V1_1']]),\n   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),\n  ('dead key whose value is live elsewhere',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['T1', 'K3_1', 'V7_1'], ['T1', 'K1_1', 'V1_1']]),\n   {'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),\n  ('value reached through a key held only by another value',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1'], ['T1', 'K2_1', 'V4_1']]),\n   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),\n  ('control: plain reachability',\n   ({'a1': ['b1'], 'root': ['a1']}, ['root'], []),\n   {'cleared': [], 'live': ['a1', 'b1', 'root']})],\n [('regression: ephemeron chain listed in reverse',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2']]),\n   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),\n  ('dead key does not retain its value',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['T2', 'K2_2', 'V4_2']]),\n   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),\n  ('dead table does not retain values',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['U2', 'K1_2', 'V5_2']]),\n   {'cleared': [], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),\n  ('dead key in a dead table is not reported',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['U2', 'K2_2', 'V6_2'], ['T2', 'K1_2', 'V1_2']]),\n   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),\n  ('dead key whose value is live elsewhere',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['T2', 'K3_2', 'V7_2'], ['T2', 'K1_2', 'V1_2']]),\n   {'cleared': [['T2', 'K3_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),\n  ('value reached through a key held only by another value',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2'], ['T2', 'K2_2', 'V4_2']]),\n   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),\n  ('control: plain reachability',\n   ({'a2': ['b2'], 'root': ['a2']}, ['root'], []),\n   {'cleared': [], 'live': ['a2', 'b2', 'root']})],\n [('regression: ephemeron chain listed in reverse',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3']]),\n   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),\n  ('dead key does not retain its value',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['T3', 'K2_3', 'V4_3']]),\n   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),\n  ('dead table does not retain values',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['U3', 'K1_3', 'V5_3']]),\n   {'cleared': [], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),\n  ('dead key in a dead table is not reported',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['U3', 'K2_3', 'V6_3'], ['T3', 'K1_3', 'V1_3']]),\n   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),\n  ('dead key whose value is live elsewhere',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['T3', 'K3_3', 'V7_3'], ['T3', 'K1_3', 'V1_3']]),\n   {'cleared': [['T3', 'K3_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),\n  ('value reached through a key held only by another value',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3'], ['T3', 'K2_3', 'V4_3']]),\n   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),\n  ('control: plain reachability',\n   ({'a3': ['b3'], 'root': ['a3']}, ['root'], []),\n   {'cleared': [], 'live': ['a3', 'b3', 'root']})],\n [('regression: ephemeron chain listed in reverse',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4']]),\n   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),\n  ('dead key does not retain its value',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['T4', 'K2_4', 'V4_4']]),\n   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),\n  ('dead table does not retain values',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['U4', 'K1_4', 'V5_4']]),\n   {'cleared': [], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),\n  ('dead key in a dead table is not reported',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['U4', 'K2_4', 'V6_4'], ['T4', 'K1_4', 'V1_4']]),\n   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),\n  ('dead key whose value is live elsewhere',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['T4', 'K3_4', 'V7_4'], ['T4', 'K1_4', 'V1_4']]),\n   {'cleared': [['T4', 'K3_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),\n  ('value reached through a key held only by another value',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4'], ['T4', 'K2_4', 'V4_4']]),\n   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),\n  ('control: plain reachability',\n   ({'a4': ['b4'], 'root': ['a4']}, ['root'], []),\n   {'cleared': [], 'live': ['a4', 'b4', 'root']})],\n [('regression: ephemeron chain listed in reverse',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5']]),\n   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),\n  ('dead key does not retain its value',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['T5', 'K2_5', 'V4_5']]),\n   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),\n  ('dead table does not retain values',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['U5', 'K1_5', 'V5_5']]),\n   {'cleared': [], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),\n  ('dead key in a dead table is not reported',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['U5', 'K2_5', 'V6_5'], ['T5', 'K1_5', 'V1_5']]),\n   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),\n  ('dead key whose value is live elsewhere',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['T5', 'K3_5', 'V7_5'], ['T5', 'K1_5', 'V1_5']]),\n   {'cleared': [['T5', 'K3_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),\n  ('value reached through a key held only by another value',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5'], ['T5', 'K2_5', 'V4_5']]),\n   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),\n  ('control: plain reachability',\n   ({'a5': ['b5'], 'root': ['a5']}, ['root'], []),\n   {'cleared': [], 'live': ['a5', 'b5', 'root']})]]\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"},"fixed":{"sha256":"65af37c95a05baa7ec27a4ccac65ae988011beb8033f789f918761b7a8371ef9","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(heap, roots, eph):\n    live = set()\n    def mark(starts):\n        stack = list(starts)\n        while stack:\n            o = stack.pop()\n            if o in live:\n                continue\n            live.add(o)\n            stack.extend(heap.get(o, []))\n    mark(roots)\n    changed = True\n    while changed:\n        changed = False\n        for table, k, v in eph:\n            if table in live and k in live and v not in live:\n                mark([v])\n                changed = True\n    cleared = sorted([t, k] for t, k, v in eph if t in live and k not in live)\n    return {'live': sorted(live), 'cleared': cleared}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: ephemeron chain listed in reverse',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1']]),\n   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),\n  ('dead key does not retain its value',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['T1', 'K2_1', 'V4_1']]),\n   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),\n  ('dead table does not retain values',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['U1', 'K1_1', 'V5_1']]),\n   {'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),\n  ('dead key in a dead table is not reported',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['U1', 'K2_1', 'V6_1'], ['T1', 'K1_1', 'V1_1']]),\n   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),\n  ('dead key whose value is live elsewhere',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['T1', 'K3_1', 'V7_1'], ['T1', 'K1_1', 'V1_1']]),\n   {'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),\n  ('value reached through a key held only by another value',\n   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},\n    ['root'],\n    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1'], ['T1', 'K2_1', 'V4_1']]),\n   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),\n  ('control: plain reachability',\n   ({'a1': ['b1'], 'root': ['a1']}, ['root'], []),\n   {'cleared': [], 'live': ['a1', 'b1', 'root']})],\n [('regression: ephemeron chain listed in reverse',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2']]),\n   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),\n  ('dead key does not retain its value',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['T2', 'K2_2', 'V4_2']]),\n   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),\n  ('dead table does not retain values',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['U2', 'K1_2', 'V5_2']]),\n   {'cleared': [], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),\n  ('dead key in a dead table is not reported',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['U2', 'K2_2', 'V6_2'], ['T2', 'K1_2', 'V1_2']]),\n   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),\n  ('dead key whose value is live elsewhere',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['T2', 'K3_2', 'V7_2'], ['T2', 'K1_2', 'V1_2']]),\n   {'cleared': [['T2', 'K3_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),\n  ('value reached through a key held only by another value',\n   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},\n    ['root'],\n    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2'], ['T2', 'K2_2', 'V4_2']]),\n   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),\n  ('control: plain reachability',\n   ({'a2': ['b2'], 'root': ['a2']}, ['root'], []),\n   {'cleared': [], 'live': ['a2', 'b2', 'root']})],\n [('regression: ephemeron chain listed in reverse',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3']]),\n   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),\n  ('dead key does not retain its value',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['T3', 'K2_3', 'V4_3']]),\n   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),\n  ('dead table does not retain values',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['U3', 'K1_3', 'V5_3']]),\n   {'cleared': [], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),\n  ('dead key in a dead table is not reported',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['U3', 'K2_3', 'V6_3'], ['T3', 'K1_3', 'V1_3']]),\n   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),\n  ('dead key whose value is live elsewhere',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['T3', 'K3_3', 'V7_3'], ['T3', 'K1_3', 'V1_3']]),\n   {'cleared': [['T3', 'K3_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),\n  ('value reached through a key held only by another value',\n   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},\n    ['root'],\n    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3'], ['T3', 'K2_3', 'V4_3']]),\n   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),\n  ('control: plain reachability',\n   ({'a3': ['b3'], 'root': ['a3']}, ['root'], []),\n   {'cleared': [], 'live': ['a3', 'b3', 'root']})],\n [('regression: ephemeron chain listed in reverse',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4']]),\n   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),\n  ('dead key does not retain its value',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['T4', 'K2_4', 'V4_4']]),\n   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),\n  ('dead table does not retain values',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['U4', 'K1_4', 'V5_4']]),\n   {'cleared': [], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),\n  ('dead key in a dead table is not reported',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['U4', 'K2_4', 'V6_4'], ['T4', 'K1_4', 'V1_4']]),\n   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),\n  ('dead key whose value is live elsewhere',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['T4', 'K3_4', 'V7_4'], ['T4', 'K1_4', 'V1_4']]),\n   {'cleared': [['T4', 'K3_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),\n  ('value reached through a key held only by another value',\n   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},\n    ['root'],\n    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4'], ['T4', 'K2_4', 'V4_4']]),\n   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),\n  ('control: plain reachability',\n   ({'a4': ['b4'], 'root': ['a4']}, ['root'], []),\n   {'cleared': [], 'live': ['a4', 'b4', 'root']})],\n [('regression: ephemeron chain listed in reverse',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5']]),\n   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),\n  ('dead key does not retain its value',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['T5', 'K2_5', 'V4_5']]),\n   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),\n  ('dead table does not retain values',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['U5', 'K1_5', 'V5_5']]),\n   {'cleared': [], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),\n  ('dead key in a dead table is not reported',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['U5', 'K2_5', 'V6_5'], ['T5', 'K1_5', 'V1_5']]),\n   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),\n  ('dead key whose value is live elsewhere',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['T5', 'K3_5', 'V7_5'], ['T5', 'K1_5', 'V1_5']]),\n   {'cleared': [['T5', 'K3_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),\n  ('value reached through a key held only by another value',\n   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},\n    ['root'],\n    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5'], ['T5', 'K2_5', 'V4_5']]),\n   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),\n  ('control: plain reachability',\n   ({'a5': ['b5'], 'root': ['a5']}, ['root'], []),\n   {'cleared': [], 'live': ['a5', 'b5', 'root']})]]\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-ephemeron-tables-clearing-criterion","generated_at":"2026-09-29T14:51:27.832488+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"WeakMap-style tables need fixpoint ephemeron marking or they leak or lose entries.","repair":"Report entries of live tables whose keys are dead.","root_cause":"Entries are reported whenever the key died, even if the table is unreachable.","sha256":"ada40a36a25990991539fcf9e702d9e301f7df7773c5c5e720f88f6882793e4a","title":"Ephemerons: dead tables reported for clearing · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":42.441,"exit_code":1,"observations":[{"actual":{"cleared":[],"live":["K1_1","T1","V1_1","V2_1","V3_1","V7_1","root"]},"check":"regression: ephemeron chain listed in reverse","expected":{"cleared":[],"live":["K1_1","T1","V1_1","V2_1","V3_1","V7_1","root"]},"passed":true},{"actual":{"cleared":[["T1","K2_1"]],"live":["K1_1","T1","V7_1","root"]},"check":"dead key does not retain its value","expected":{"cleared":[["T1","K2_1"]],"live":["K1_1","T1","V7_1","root"]},"passed":true},{"actual":{"cleared":[],"live":["K1_1","T1","V7_1","root"]},"check":"dead table does not retain values","expected":{"cleared":[],"live":["K1_1","T1","V7_1","root"]},"passed":true},{"actual":{"cleared":[],"live":["K1_1","T1","V1_1","V7_1","root"]},"check":"dead key in a dead table is not reported","expected":{"cleared":[],"live":["K1_1","T1","V1_1","V7_1","root"]},"passed":true},{"actual":{"cleared":[],"live":["K1_1","T1","V1_1","V7_1","root"]},"check":"dead key whose value is live elsewhere","expected":{"cleared":[["T1","K3_1"]],"live":["K1_1","T1","V1_1","V7_1","root"]},"passed":false},{"actual":{"cleared":[["T1","K2_1"]],"live":["K1_1","T1","V1_1","V2_1","V3_1","V7_1","root"]},"check":"value reached through a key held only by another value","expected":{"cleared":[["T1","K2_1"]],"live":["K1_1","T1","V1_1","V2_1","V3_1","V7_1","root"]},"passed":true},{"actual":{"cleared":[],"live":["a1","b1","root"]},"check":"control: plain reachability","expected":{"cleared":[],"live":["a1","b1","root"]},"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: ephemeron chain listed in reverse\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V2_1\", \"V3_1\", \"V7_1\", \"root\"], \"cleared\": []}, \"expected\": {\"cleared\": [], \"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V2_1\", \"V3_1\", \"V7_1\", \"root\"]}, \"passed\": true}, {\"check\": \"dead key does not retain its value\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V7_1\", \"root\"], \"cleared\": [[\"T1\", \"K2_1\"]]}, \"expected\": {\"cleared\": [[\"T1\", \"K2_1\"]], \"live\": [\"K1_1\", \"T1\", \"V7_1\", \"root\"]}, \"passed\": true}, {\"check\": \"dead table does not retain values\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V7_1\", \"root\"], \"cleared\": []}, \"expected\": {\"cleared\": [], \"live\": [\"K1_1\", \"T1\", \"V7_1\", \"root\"]}, \"passed\": true}, {\"check\": \"dead key in a dead table is not reported\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V7_1\", \"root\"], \"cleared\": []}, \"expected\": {\"cleared\": [], \"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V7_1\", \"root\"]}, \"passed\": true}, {\"check\": \"dead key whose value is live elsewhere\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V7_1\", \"root\"], \"cleared\": []}, \"expected\": {\"cleared\": [[\"T1\", \"K3_1\"]], \"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V7_1\", \"root\"]}, \"passed\": false}, {\"check\": \"value reached through a key held only by another value\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V2_1\", \"V3_1\", \"V7_1\", \"root\"], \"cleared\": [[\"T1\", \"K2_1\"]]}, \"expected\": {\"cleared\": [[\"T1\", \"K2_1\"]], \"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V2_1\", \"V3_1\", \"V7_1\", \"root\"]}, \"passed\": true}, {\"check\": \"control: plain reachability\", \"actual\": {\"live\": [\"a1\", \"b1\", \"root\"], \"cleared\": []}, \"expected\": {\"cleared\": [], \"live\": [\"a1\", \"b1\", \"root\"]}, \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":40.631,"exit_code":1,"observations":[{"actual":{"cleared":[],"live":["K1_1","T1","V1_1","V2_1","V3_1","V7_1","root"]},"check":"regression: ephemeron chain listed in reverse","expected":{"cleared":[],"live":["K1_1","T1","V1_1","V2_1","V3_1","V7_1","root"]},"passed":true},{"actual":{"cleared":[["T1","K2_1"]],"live":["K1_1","T1","V7_1","root"]},"check":"dead key does not retain its value","expected":{"cleared":[["T1","K2_1"]],"live":["K1_1","T1","V7_1","root"]},"passed":true},{"actual":{"cleared":[],"live":["K1_1","T1","V7_1","root"]},"check":"dead table does not retain values","expected":{"cleared":[],"live":["K1_1","T1","V7_1","root"]},"passed":true},{"actual":{"cleared":[["U1","K2_1"]],"live":["K1_1","T1","V1_1","V7_1","root"]},"check":"dead key in a dead table is not reported","expected":{"cleared":[],"live":["K1_1","T1","V1_1","V7_1","root"]},"passed":false},{"actual":{"cleared":[["T1","K3_1"]],"live":["K1_1","T1","V1_1","V7_1","root"]},"check":"dead key whose value is live elsewhere","expected":{"cleared":[["T1","K3_1"]],"live":["K1_1","T1","V1_1","V7_1","root"]},"passed":true},{"actual":{"cleared":[["T1","K2_1"]],"live":["K1_1","T1","V1_1","V2_1","V3_1","V7_1","root"]},"check":"value reached through a key held only by another value","expected":{"cleared":[["T1","K2_1"]],"live":["K1_1","T1","V1_1","V2_1","V3_1","V7_1","root"]},"passed":true},{"actual":{"cleared":[],"live":["a1","b1","root"]},"check":"control: plain reachability","expected":{"cleared":[],"live":["a1","b1","root"]},"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: ephemeron chain listed in reverse\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V2_1\", \"V3_1\", \"V7_1\", \"root\"], \"cleared\": []}, \"expected\": {\"cleared\": [], \"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V2_1\", \"V3_1\", \"V7_1\", \"root\"]}, \"passed\": true}, {\"check\": \"dead key does not retain its value\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V7_1\", \"root\"], \"cleared\": [[\"T1\", \"K2_1\"]]}, \"expected\": {\"cleared\": [[\"T1\", \"K2_1\"]], \"live\": [\"K1_1\", \"T1\", \"V7_1\", \"root\"]}, \"passed\": true}, {\"check\": \"dead table does not retain values\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V7_1\", \"root\"], \"cleared\": []}, \"expected\": {\"cleared\": [], \"live\": [\"K1_1\", \"T1\", \"V7_1\", \"root\"]}, \"passed\": true}, {\"check\": \"dead key in a dead table is not reported\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V7_1\", \"root\"], \"cleared\": [[\"U1\", \"K2_1\"]]}, \"expected\": {\"cleared\": [], \"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V7_1\", \"root\"]}, \"passed\": false}, {\"check\": \"dead key whose value is live elsewhere\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V7_1\", \"root\"], \"cleared\": [[\"T1\", \"K3_1\"]]}, \"expected\": {\"cleared\": [[\"T1\", \"K3_1\"]], \"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V7_1\", \"root\"]}, \"passed\": true}, {\"check\": \"value reached through a key held only by another value\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V2_1\", \"V3_1\", \"V7_1\", \"root\"], \"cleared\": [[\"T1\", \"K2_1\"]]}, \"expected\": {\"cleared\": [[\"T1\", \"K2_1\"]], \"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V2_1\", \"V3_1\", \"V7_1\", \"root\"]}, \"passed\": true}, {\"check\": \"control: plain reachability\", \"actual\": {\"live\": [\"a1\", \"b1\", \"root\"], \"cleared\": []}, \"expected\": {\"cleared\": [], \"live\": [\"a1\", \"b1\", \"root\"]}, \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":42.908,"exit_code":0,"observations":[{"actual":{"cleared":[],"live":["K1_1","T1","V1_1","V2_1","V3_1","V7_1","root"]},"check":"regression: ephemeron chain listed in reverse","expected":{"cleared":[],"live":["K1_1","T1","V1_1","V2_1","V3_1","V7_1","root"]},"passed":true},{"actual":{"cleared":[["T1","K2_1"]],"live":["K1_1","T1","V7_1","root"]},"check":"dead key does not retain its value","expected":{"cleared":[["T1","K2_1"]],"live":["K1_1","T1","V7_1","root"]},"passed":true},{"actual":{"cleared":[],"live":["K1_1","T1","V7_1","root"]},"check":"dead table does not retain values","expected":{"cleared":[],"live":["K1_1","T1","V7_1","root"]},"passed":true},{"actual":{"cleared":[],"live":["K1_1","T1","V1_1","V7_1","root"]},"check":"dead key in a dead table is not reported","expected":{"cleared":[],"live":["K1_1","T1","V1_1","V7_1","root"]},"passed":true},{"actual":{"cleared":[["T1","K3_1"]],"live":["K1_1","T1","V1_1","V7_1","root"]},"check":"dead key whose value is live elsewhere","expected":{"cleared":[["T1","K3_1"]],"live":["K1_1","T1","V1_1","V7_1","root"]},"passed":true},{"actual":{"cleared":[["T1","K2_1"]],"live":["K1_1","T1","V1_1","V2_1","V3_1","V7_1","root"]},"check":"value reached through a key held only by another value","expected":{"cleared":[["T1","K2_1"]],"live":["K1_1","T1","V1_1","V2_1","V3_1","V7_1","root"]},"passed":true},{"actual":{"cleared":[],"live":["a1","b1","root"]},"check":"control: plain reachability","expected":{"cleared":[],"live":["a1","b1","root"]},"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: ephemeron chain listed in reverse\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V2_1\", \"V3_1\", \"V7_1\", \"root\"], \"cleared\": []}, \"expected\": {\"cleared\": [], \"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V2_1\", \"V3_1\", \"V7_1\", \"root\"]}, \"passed\": true}, {\"check\": \"dead key does not retain its value\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V7_1\", \"root\"], \"cleared\": [[\"T1\", \"K2_1\"]]}, \"expected\": {\"cleared\": [[\"T1\", \"K2_1\"]], \"live\": [\"K1_1\", \"T1\", \"V7_1\", \"root\"]}, \"passed\": true}, {\"check\": \"dead table does not retain values\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V7_1\", \"root\"], \"cleared\": []}, \"expected\": {\"cleared\": [], \"live\": [\"K1_1\", \"T1\", \"V7_1\", \"root\"]}, \"passed\": true}, {\"check\": \"dead key in a dead table is not reported\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V7_1\", \"root\"], \"cleared\": []}, \"expected\": {\"cleared\": [], \"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V7_1\", \"root\"]}, \"passed\": true}, {\"check\": \"dead key whose value is live elsewhere\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V7_1\", \"root\"], \"cleared\": [[\"T1\", \"K3_1\"]]}, \"expected\": {\"cleared\": [[\"T1\", \"K3_1\"]], \"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V7_1\", \"root\"]}, \"passed\": true}, {\"check\": \"value reached through a key held only by another value\", \"actual\": {\"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V2_1\", \"V3_1\", \"V7_1\", \"root\"], \"cleared\": [[\"T1\", \"K2_1\"]]}, \"expected\": {\"cleared\": [[\"T1\", \"K2_1\"]], \"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V2_1\", \"V3_1\", \"V7_1\", \"root\"]}, \"passed\": true}, {\"check\": \"control: plain reachability\", \"actual\": {\"live\": [\"a1\", \"b1\", \"root\"], \"cleared\": []}, \"expected\": {\"cleared\": [], \"live\": [\"a1\", \"b1\", \"root\"]}, \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}