{"abstract":"Weak-keyed tables keep every value alive, leaking entries whose keys died.","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":"Accepting only root keys drops values whose keys are reachable through the heap.","family":"w2-garbage-collector-invariants-ephemeron-tables-key-reachability-requirement","id":"FA-90556","implementations":{"attempt":{"sha256":"93f822e439ee3c62b66d083483f4ed62f06bc735b8dd6317ad621c9d70367f72","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 roots 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"},"broken":{"sha256":"31abb515de7381a19e9fd9caaf8fdac16a3d3e7870122ed30b67e5b068677c22","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 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"},"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-key-reachability-requirement","generated_at":"2026-09-29T14:51:27.786678+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":"Trace the value only when the key is reachable.","root_cause":"The value is marked without checking that its key is reachable.","sha256":"33c4d32528d3eec7e34c0210cfca81587158c7d16ce2b779bcfd32e0d15de0aa","title":"Ephemerons: values traced regardless of key liveness · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":39.143,"exit_code":1,"observations":[{"actual":{"cleared":[["T1","V1_1"],["T1","V2_1"]],"live":["K1_1","T1","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":false},{"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","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","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"],["T1","V1_1"],["T1","V2_1"]],"live":["K1_1","T1","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":false},{"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\", \"V7_1\", \"root\"], \"cleared\": [[\"T1\", \"V1_1\"], [\"T1\", \"V2_1\"]]}, \"expected\": {\"cleared\": [], \"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V2_1\", \"V3_1\", \"V7_1\", \"root\"]}, \"passed\": false}, {\"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\", \"V7_1\", \"root\"], \"cleared\": []}, \"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\", \"V7_1\", \"root\"], \"cleared\": [[\"T1\", \"K3_1\"]]}, \"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\", \"V7_1\", \"root\"], \"cleared\": [[\"T1\", \"K2_1\"], [\"T1\", \"V1_1\"], [\"T1\", \"V2_1\"]]}, \"expected\": {\"cleared\": [[\"T1\", \"K2_1\"]], \"live\": [\"K1_1\", \"T1\", \"V1_1\", \"V2_1\", \"V3_1\", \"V7_1\", \"root\"]}, \"passed\": false}, {\"check\": \"control: plain reachability\", \"actual\": {\"live\": [\"a1\", \"b1\", \"root\"], \"cleared\": []}, \"expected\": {\"cleared\": [], \"live\": [\"a1\", \"b1\", \"root\"]}, \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":41.607,"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","V4_1","V7_1","root"]},"check":"dead key does not retain its value","expected":{"cleared":[["T1","K2_1"]],"live":["K1_1","T1","V7_1","root"]},"passed":false},{"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","V4_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":false},{"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\", \"V4_1\", \"V7_1\", \"root\"], \"cleared\": [[\"T1\", \"K2_1\"]]}, \"expected\": {\"cleared\": [[\"T1\", \"K2_1\"]], \"live\": [\"K1_1\", \"T1\", \"V7_1\", \"root\"]}, \"passed\": false}, {\"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\", \"V4_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\": false}, {\"check\": \"control: plain reachability\", \"actual\": {\"live\": [\"a1\", \"b1\", \"root\"], \"cleared\": []}, \"expected\": {\"cleared\": [], \"live\": [\"a1\", \"b1\", \"root\"]}, \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":41.136,"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"}