FA-90566 / Garbage collector invariants / Open access

Ephemerons: dead tables reported for clearing · case 01

Clearing work is scheduled for tables that are themselves garbage.

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

ROOT CAUSE

Entries are reported whenever the key died, even if the table is unreachable.

VERIFIED REPAIR

Report entries of live tables whose keys are dead.

Unsuccessful approach: Keying the report on dead values misses dead keys whose values survive through other paths.

Case 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).

Why this case matters

WeakMap-style tables need fixpoint ephemeron marking or they leak or lose entries.

1 / The failure

Exit 1

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

N = 1
observations = []
def solve(heap, roots, eph):
    live = set()
    def mark(starts):
        stack = list(starts)
        while stack:
            o = stack.pop()
            if o in live:
                continue
            live.add(o)
            stack.extend(heap.get(o, []))
    mark(roots)
    changed = True
    while changed:
        changed = False
        for table, k, v in eph:
            if table in live and k in live and v not in live:
                mark([v])
                changed = True
    cleared = sorted([t, k] for t, k, v in eph if k not in live)
    return {'live': sorted(live), 'cleared': cleared}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: ephemeron chain listed in reverse',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('dead key does not retain its value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead table does not retain values',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K1_1', 'V5_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K2_1', 'V6_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K3_1', 'V7_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1'], ['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('control: plain reachability',
   ({'a1': ['b1'], 'root': ['a1']}, ['root'], []),
   {'cleared': [], 'live': ['a1', 'b1', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('dead key does not retain its value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead table does not retain values',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K1_2', 'V5_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K2_2', 'V6_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K3_2', 'V7_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [['T2', 'K3_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2'], ['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('control: plain reachability',
   ({'a2': ['b2'], 'root': ['a2']}, ['root'], []),
   {'cleared': [], 'live': ['a2', 'b2', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('dead key does not retain its value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead table does not retain values',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K1_3', 'V5_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K2_3', 'V6_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K3_3', 'V7_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [['T3', 'K3_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3'], ['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('control: plain reachability',
   ({'a3': ['b3'], 'root': ['a3']}, ['root'], []),
   {'cleared': [], 'live': ['a3', 'b3', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('dead key does not retain its value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead table does not retain values',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K1_4', 'V5_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K2_4', 'V6_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K3_4', 'V7_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [['T4', 'K3_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4'], ['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('control: plain reachability',
   ({'a4': ['b4'], 'root': ['a4']}, ['root'], []),
   {'cleared': [], 'live': ['a4', 'b4', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('dead key does not retain its value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead table does not retain values',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K1_5', 'V5_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K2_5', 'V6_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K3_5', 'V7_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [['T5', 'K3_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5'], ['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('control: plain reachability',
   ({'a5': ['b5'], 'root': ['a5']}, ['root'], []),
   {'cleared': [], 'live': ['a5', 'b5', 'root']})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
regression: ephemeron chain listed in reverse	`{'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}`	`{'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}`	Passed
dead key does not retain its value	`{'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}`	`{'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}`	Passed
dead table does not retain values	`{'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}`	`{'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}`	Passed
dead key in a dead table is not reported	`{'cleared': [['U1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}`	`{'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}`	Failed
dead key whose value is live elsewhere	`{'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}`	`{'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}`	Passed
value reached through a key held only by another value	`{'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}`	`{'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}`	Passed
control: plain reachability	`{'cleared': [], 'live': ['a1', 'b1', 'root']}`	`{'cleared': [], 'live': ['a1', 'b1', 'root']}`	Passed

SHA-256 / 214e845c786921e63263a8789f236373605ce0c0d69a9d87f6914393fc392e9c

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(heap, roots, eph):
    live = set()
    def mark(starts):
        stack = list(starts)
        while stack:
            o = stack.pop()
            if o in live:
                continue
            live.add(o)
            stack.extend(heap.get(o, []))
    mark(roots)
    changed = True
    while changed:
        changed = False
        for table, k, v in eph:
            if table in live and k in live and v not in live:
                mark([v])
                changed = True
    cleared = sorted([t, k] for t, k, v in eph if t in live and v not in live)
    return {'live': sorted(live), 'cleared': cleared}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: ephemeron chain listed in reverse',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('dead key does not retain its value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead table does not retain values',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K1_1', 'V5_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K2_1', 'V6_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K3_1', 'V7_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1'], ['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('control: plain reachability',
   ({'a1': ['b1'], 'root': ['a1']}, ['root'], []),
   {'cleared': [], 'live': ['a1', 'b1', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('dead key does not retain its value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead table does not retain values',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K1_2', 'V5_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K2_2', 'V6_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K3_2', 'V7_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [['T2', 'K3_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2'], ['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('control: plain reachability',
   ({'a2': ['b2'], 'root': ['a2']}, ['root'], []),
   {'cleared': [], 'live': ['a2', 'b2', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('dead key does not retain its value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead table does not retain values',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K1_3', 'V5_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K2_3', 'V6_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K3_3', 'V7_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [['T3', 'K3_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3'], ['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('control: plain reachability',
   ({'a3': ['b3'], 'root': ['a3']}, ['root'], []),
   {'cleared': [], 'live': ['a3', 'b3', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('dead key does not retain its value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead table does not retain values',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K1_4', 'V5_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K2_4', 'V6_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K3_4', 'V7_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [['T4', 'K3_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4'], ['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('control: plain reachability',
   ({'a4': ['b4'], 'root': ['a4']}, ['root'], []),
   {'cleared': [], 'live': ['a4', 'b4', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('dead key does not retain its value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead table does not retain values',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K1_5', 'V5_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K2_5', 'V6_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K3_5', 'V7_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [['T5', 'K3_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5'], ['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('control: plain reachability',
   ({'a5': ['b5'], 'root': ['a5']}, ['root'], []),
   {'cleared': [], 'live': ['a5', 'b5', 'root']})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
regression: ephemeron chain listed in reverse	`{'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}`	`{'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}`	Passed
dead key does not retain its value	`{'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}`	`{'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}`	Passed
dead table does not retain values	`{'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}`	`{'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}`	Passed
dead key in a dead table is not reported	`{'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}`	`{'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}`	Passed
dead key whose value is live elsewhere	`{'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}`	`{'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}`	Failed
value reached through a key held only by another value	`{'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}`	`{'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}`	Passed
control: plain reachability	`{'cleared': [], 'live': ['a1', 'b1', 'root']}`	`{'cleared': [], 'live': ['a1', 'b1', 'root']}`	Passed

SHA-256 / 871d02a4712d96d4764fb6011a28edd5053a3a260d1ebf767ac6d24e9ac77b56

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(heap, roots, eph):
    live = set()
    def mark(starts):
        stack = list(starts)
        while stack:
            o = stack.pop()
            if o in live:
                continue
            live.add(o)
            stack.extend(heap.get(o, []))
    mark(roots)
    changed = True
    while changed:
        changed = False
        for table, k, v in eph:
            if table in live and k in live and v not in live:
                mark([v])
                changed = True
    cleared = sorted([t, k] for t, k, v in eph if t in live and k not in live)
    return {'live': sorted(live), 'cleared': cleared}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: ephemeron chain listed in reverse',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('dead key does not retain its value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead table does not retain values',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K1_1', 'V5_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['U1', 'K2_1', 'V6_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'K3_1', 'V7_1'], ['T1', 'K1_1', 'V1_1']]),
   {'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_1': [], 'K2_1': [], 'K3_1': [], 'T1': [], 'U1': [], 'root': ['T1', 'K1_1', 'V7_1']},
    ['root'],
    [['T1', 'V2_1', 'V3_1'], ['T1', 'V1_1', 'V2_1'], ['T1', 'K1_1', 'V1_1'], ['T1', 'K2_1', 'V4_1']]),
   {'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}),
  ('control: plain reachability',
   ({'a1': ['b1'], 'root': ['a1']}, ['root'], []),
   {'cleared': [], 'live': ['a1', 'b1', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('dead key does not retain its value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead table does not retain values',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K1_2', 'V5_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V7_2', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['U2', 'K2_2', 'V6_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'K3_2', 'V7_2'], ['T2', 'K1_2', 'V1_2']]),
   {'cleared': [['T2', 'K3_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V7_2', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_2': [], 'K2_2': [], 'K3_2': [], 'T2': [], 'U2': [], 'root': ['T2', 'K1_2', 'V7_2']},
    ['root'],
    [['T2', 'V2_2', 'V3_2'], ['T2', 'V1_2', 'V2_2'], ['T2', 'K1_2', 'V1_2'], ['T2', 'K2_2', 'V4_2']]),
   {'cleared': [['T2', 'K2_2']], 'live': ['K1_2', 'T2', 'V1_2', 'V2_2', 'V3_2', 'V7_2', 'root']}),
  ('control: plain reachability',
   ({'a2': ['b2'], 'root': ['a2']}, ['root'], []),
   {'cleared': [], 'live': ['a2', 'b2', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('dead key does not retain its value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead table does not retain values',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K1_3', 'V5_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V7_3', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['U3', 'K2_3', 'V6_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'K3_3', 'V7_3'], ['T3', 'K1_3', 'V1_3']]),
   {'cleared': [['T3', 'K3_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V7_3', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_3': [], 'K2_3': [], 'K3_3': [], 'T3': [], 'U3': [], 'root': ['T3', 'K1_3', 'V7_3']},
    ['root'],
    [['T3', 'V2_3', 'V3_3'], ['T3', 'V1_3', 'V2_3'], ['T3', 'K1_3', 'V1_3'], ['T3', 'K2_3', 'V4_3']]),
   {'cleared': [['T3', 'K2_3']], 'live': ['K1_3', 'T3', 'V1_3', 'V2_3', 'V3_3', 'V7_3', 'root']}),
  ('control: plain reachability',
   ({'a3': ['b3'], 'root': ['a3']}, ['root'], []),
   {'cleared': [], 'live': ['a3', 'b3', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('dead key does not retain its value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead table does not retain values',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K1_4', 'V5_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V7_4', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['U4', 'K2_4', 'V6_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'K3_4', 'V7_4'], ['T4', 'K1_4', 'V1_4']]),
   {'cleared': [['T4', 'K3_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V7_4', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_4': [], 'K2_4': [], 'K3_4': [], 'T4': [], 'U4': [], 'root': ['T4', 'K1_4', 'V7_4']},
    ['root'],
    [['T4', 'V2_4', 'V3_4'], ['T4', 'V1_4', 'V2_4'], ['T4', 'K1_4', 'V1_4'], ['T4', 'K2_4', 'V4_4']]),
   {'cleared': [['T4', 'K2_4']], 'live': ['K1_4', 'T4', 'V1_4', 'V2_4', 'V3_4', 'V7_4', 'root']}),
  ('control: plain reachability',
   ({'a4': ['b4'], 'root': ['a4']}, ['root'], []),
   {'cleared': [], 'live': ['a4', 'b4', 'root']})],
 [('regression: ephemeron chain listed in reverse',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('dead key does not retain its value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead table does not retain values',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K1_5', 'V5_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V7_5', 'root']}),
  ('dead key in a dead table is not reported',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['U5', 'K2_5', 'V6_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('dead key whose value is live elsewhere',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'K3_5', 'V7_5'], ['T5', 'K1_5', 'V1_5']]),
   {'cleared': [['T5', 'K3_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V7_5', 'root']}),
  ('value reached through a key held only by another value',
   ({'K1_5': [], 'K2_5': [], 'K3_5': [], 'T5': [], 'U5': [], 'root': ['T5', 'K1_5', 'V7_5']},
    ['root'],
    [['T5', 'V2_5', 'V3_5'], ['T5', 'V1_5', 'V2_5'], ['T5', 'K1_5', 'V1_5'], ['T5', 'K2_5', 'V4_5']]),
   {'cleared': [['T5', 'K2_5']], 'live': ['K1_5', 'T5', 'V1_5', 'V2_5', 'V3_5', 'V7_5', 'root']}),
  ('control: plain reachability',
   ({'a5': ['b5'], 'root': ['a5']}, ['root'], []),
   {'cleared': [], 'live': ['a5', 'b5', 'root']})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
regression: ephemeron chain listed in reverse	`{'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}`	`{'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}`	Passed
dead key does not retain its value	`{'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}`	`{'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V7_1', 'root']}`	Passed
dead table does not retain values	`{'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}`	`{'cleared': [], 'live': ['K1_1', 'T1', 'V7_1', 'root']}`	Passed
dead key in a dead table is not reported	`{'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}`	`{'cleared': [], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}`	Passed
dead key whose value is live elsewhere	`{'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}`	`{'cleared': [['T1', 'K3_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V7_1', 'root']}`	Passed
value reached through a key held only by another value	`{'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}`	`{'cleared': [['T1', 'K2_1']], 'live': ['K1_1', 'T1', 'V1_1', 'V2_1', 'V3_1', 'V7_1', 'root']}`	Passed
control: plain reachability	`{'cleared': [], 'live': ['a1', 'b1', 'root']}`	`{'cleared': [], 'live': ['a1', 'b1', 'root']}`	Passed

SHA-256 / 65af37c95a05baa7ec27a4ccac65ae988011beb8033f789f918761b7a8371ef9

Verification & scope

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

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

Case digest / ada40a36a25990991539fcf9e702d9e301f7df7773c5c5e720f88f6882793e4a