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

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

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

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

prompt:
An unreachable object with a finalizer is resurrected forever and never freed.

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

split: open-access


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

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

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

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

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

prompt:
A finalizer runs against an object whose fields point at freed memory.

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

split: open-access


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

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

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

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

prompt:
Cleanup actions run for objects that a pending finalizer can still reach.

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

split: open-access


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

source:
"""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
    for _ in range(2):
        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)

prompt:
Values whose keys become reachable only through later-listed ephemerons are dropped.

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

split: open-access