FAILURE MAP
← Case archive

FA-90406 / Garbage collector invariants / Open access

Trial deletion: children whitened without being scanned · case 01

Cycle members beyond the first child stay gray and survive, while children with outside references are whitened.

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

ROOT CAUSE

Whitening colours the direct children instead of recursively scanning them.

VERIFIED REPAIR

Scan each child so that it is judged by its own count and its subtree is visited.

Unsuccessful approach: Scanning only children that are themselves candidates leaves the rest of a cycle gray.

Case contract

Synchronous trial-deletion cycle collection. Reference counts are external references plus heap in-edges. For each candidate, mark gray: colour gray and, for every out-edge, decrement the child count and recurse. Then scan each candidate: a gray object with positive count is re-blackened together with everything it reaches, restoring one count per traversed edge; a gray object with zero count turns white and its children are scanned. White objects are garbage. Return the garbage and the counts of the surviving objects.

Why this case matters

Cycle collectors for reference-counted heaps depend on exact decrement/restore bookkeeping.

1 / The failure

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

N = 1
observations = []
def solve(heap, external, candidates):
    rc = {o: external.get(o, 0) for o in heap}
    for o, kids in heap.items():
        for c in kids:
            rc[c] += 1
    color = {o: 'black' for o in heap}
    def mark_gray(o):
        if color[o] != 'gray':
            color[o] = 'gray'
            for c in heap[o]:
                rc[c] -= 1
                mark_gray(c)
    def scan(o):
        if color[o] == 'gray':
            if rc[o] > 0:
                scan_black(o)
            else:
                color[o] = 'white'
                for c in heap[o]:
                    color[c] = 'white' if color[c] == 'gray' else color[c]
    def scan_black(o):
        color[o] = 'black'
        for c in heap[o]:
            rc[c] += 1
            if color[c] != 'black':
                scan_black(c)
    for o in candidates:
        mark_gray(o)
    for o in candidates:
        scan(o)
    garbage = sorted(o for o in heap if color[o] == 'white')
    return {'garbage': garbage, 'rc': {str(o): rc[o] for o in sorted(heap) if color[o] != 'white'}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: three-object garbage cycle',
   ({11: [12], 12: [13], 13: [11]}, {}, [11]),
   {'garbage': [11, 12, 13], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({11: [12], 12: [11, 13], 13: []}, {13: 1}, [11]),
   {'garbage': [11, 12], 'rc': {'13': 1}}),
  ('externally held cycle restores its counts',
   ({11: [12], 12: [11]}, {12: 1}, [11]),
   {'garbage': [], 'rc': {'11': 1, '12': 2}}),
  ('candidate sharing a child with a live object',
   ({15: [16], 16: [], 17: [16]}, {15: 1}, [17]),
   {'garbage': [17], 'rc': {'15': 1, '16': 1}}),
  ('self-referencing garbage', ({14: [14], 19: []}, {19: 1}, [14]), {'garbage': [14], 'rc': {'19': 1}}),
  ('object with two external references',
   ({18: [19], 19: []}, {18: 2}, [18]),
   {'garbage': [], 'rc': {'18': 2, '19': 1}}),
  ('control: acyclic live candidate',
   ({11: [12], 12: []}, {11: 1}, [11, 12]),
   {'garbage': [], 'rc': {'11': 1, '12': 1}})],
 [('regression: three-object garbage cycle',
   ({21: [22], 22: [23], 23: [21]}, {}, [21]),
   {'garbage': [21, 22, 23], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({21: [22], 22: [21, 23], 23: []}, {23: 1}, [21]),
   {'garbage': [21, 22], 'rc': {'23': 1}}),
  ('externally held cycle restores its counts',
   ({21: [22], 22: [21]}, {22: 1}, [21]),
   {'garbage': [], 'rc': {'21': 1, '22': 2}}),
  ('candidate sharing a child with a live object',
   ({25: [26], 26: [], 27: [26]}, {25: 1}, [27]),
   {'garbage': [27], 'rc': {'25': 1, '26': 1}}),
  ('self-referencing garbage', ({24: [24], 29: []}, {29: 1}, [24]), {'garbage': [24], 'rc': {'29': 1}}),
  ('object with two external references',
   ({28: [29], 29: []}, {28: 2}, [28]),
   {'garbage': [], 'rc': {'28': 2, '29': 1}}),
  ('control: acyclic live candidate',
   ({21: [22], 22: []}, {21: 1}, [21, 22]),
   {'garbage': [], 'rc': {'21': 1, '22': 1}})],
 [('regression: three-object garbage cycle',
   ({31: [32], 32: [33], 33: [31]}, {}, [31]),
   {'garbage': [31, 32, 33], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({31: [32], 32: [31, 33], 33: []}, {33: 1}, [31]),
   {'garbage': [31, 32], 'rc': {'33': 1}}),
  ('externally held cycle restores its counts',
   ({31: [32], 32: [31]}, {32: 1}, [31]),
   {'garbage': [], 'rc': {'31': 1, '32': 2}}),
  ('candidate sharing a child with a live object',
   ({35: [36], 36: [], 37: [36]}, {35: 1}, [37]),
   {'garbage': [37], 'rc': {'35': 1, '36': 1}}),
  ('self-referencing garbage', ({34: [34], 39: []}, {39: 1}, [34]), {'garbage': [34], 'rc': {'39': 1}}),
  ('object with two external references',
   ({38: [39], 39: []}, {38: 2}, [38]),
   {'garbage': [], 'rc': {'38': 2, '39': 1}}),
  ('control: acyclic live candidate',
   ({31: [32], 32: []}, {31: 1}, [31, 32]),
   {'garbage': [], 'rc': {'31': 1, '32': 1}})],
 [('regression: three-object garbage cycle',
   ({41: [42], 42: [43], 43: [41]}, {}, [41]),
   {'garbage': [41, 42, 43], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({41: [42], 42: [41, 43], 43: []}, {43: 1}, [41]),
   {'garbage': [41, 42], 'rc': {'43': 1}}),
  ('externally held cycle restores its counts',
   ({41: [42], 42: [41]}, {42: 1}, [41]),
   {'garbage': [], 'rc': {'41': 1, '42': 2}}),
  ('candidate sharing a child with a live object',
   ({45: [46], 46: [], 47: [46]}, {45: 1}, [47]),
   {'garbage': [47], 'rc': {'45': 1, '46': 1}}),
  ('self-referencing garbage', ({44: [44], 49: []}, {49: 1}, [44]), {'garbage': [44], 'rc': {'49': 1}}),
  ('object with two external references',
   ({48: [49], 49: []}, {48: 2}, [48]),
   {'garbage': [], 'rc': {'48': 2, '49': 1}}),
  ('control: acyclic live candidate',
   ({41: [42], 42: []}, {41: 1}, [41, 42]),
   {'garbage': [], 'rc': {'41': 1, '42': 1}})],
 [('regression: three-object garbage cycle',
   ({51: [52], 52: [53], 53: [51]}, {}, [51]),
   {'garbage': [51, 52, 53], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({51: [52], 52: [51, 53], 53: []}, {53: 1}, [51]),
   {'garbage': [51, 52], 'rc': {'53': 1}}),
  ('externally held cycle restores its counts',
   ({51: [52], 52: [51]}, {52: 1}, [51]),
   {'garbage': [], 'rc': {'51': 1, '52': 2}}),
  ('candidate sharing a child with a live object',
   ({55: [56], 56: [], 57: [56]}, {55: 1}, [57]),
   {'garbage': [57], 'rc': {'55': 1, '56': 1}}),
  ('self-referencing garbage', ({54: [54], 59: []}, {59: 1}, [54]), {'garbage': [54], 'rc': {'59': 1}}),
  ('object with two external references',
   ({58: [59], 59: []}, {58: 2}, [58]),
   {'garbage': [], 'rc': {'58': 2, '59': 1}}),
  ('control: acyclic live candidate',
   ({51: [52], 52: []}, {51: 1}, [51, 52]),
   {'garbage': [], 'rc': {'51': 1, '52': 1}})]]
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 fixtureActualExpectedOutcome
regression: three-object garbage cycle{'garbage': [11, 12], 'rc': {'13': 0}}{'garbage': [11, 12, 13], 'rc': {}}Failed
garbage cycle pointing at a live object{'garbage': [11, 12], 'rc': {'13': 1}}{'garbage': [11, 12], 'rc': {'13': 1}}Passed
externally held cycle restores its counts{'garbage': [11, 12], 'rc': {}}{'garbage': [], 'rc': {'11': 1, '12': 2}}Failed
candidate sharing a child with a live object{'garbage': [16, 17], 'rc': {'15': 1}}{'garbage': [17], 'rc': {'15': 1, '16': 1}}Failed
self-referencing garbage{'garbage': [14], 'rc': {'19': 1}}{'garbage': [14], 'rc': {'19': 1}}Passed
object with two external references{'garbage': [], 'rc': {'18': 2, '19': 1}}{'garbage': [], 'rc': {'18': 2, '19': 1}}Passed
control: acyclic live candidate{'garbage': [], 'rc': {'11': 1, '12': 1}}{'garbage': [], 'rc': {'11': 1, '12': 1}}Passed

SHA-256 / f681a2769fbcde20246b7fba9726c8a36896c7f0b0b69bf8d402611ffa9b2f35

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(heap, external, candidates):
    rc = {o: external.get(o, 0) for o in heap}
    for o, kids in heap.items():
        for c in kids:
            rc[c] += 1
    color = {o: 'black' for o in heap}
    def mark_gray(o):
        if color[o] != 'gray':
            color[o] = 'gray'
            for c in heap[o]:
                rc[c] -= 1
                mark_gray(c)
    def scan(o):
        if color[o] == 'gray':
            if rc[o] > 0:
                scan_black(o)
            else:
                color[o] = 'white'
                for c in heap[o]:
                    if c in candidates:
                        scan(c)
    def scan_black(o):
        color[o] = 'black'
        for c in heap[o]:
            rc[c] += 1
            if color[c] != 'black':
                scan_black(c)
    for o in candidates:
        mark_gray(o)
    for o in candidates:
        scan(o)
    garbage = sorted(o for o in heap if color[o] == 'white')
    return {'garbage': garbage, 'rc': {str(o): rc[o] for o in sorted(heap) if color[o] != 'white'}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: three-object garbage cycle',
   ({11: [12], 12: [13], 13: [11]}, {}, [11]),
   {'garbage': [11, 12, 13], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({11: [12], 12: [11, 13], 13: []}, {13: 1}, [11]),
   {'garbage': [11, 12], 'rc': {'13': 1}}),
  ('externally held cycle restores its counts',
   ({11: [12], 12: [11]}, {12: 1}, [11]),
   {'garbage': [], 'rc': {'11': 1, '12': 2}}),
  ('candidate sharing a child with a live object',
   ({15: [16], 16: [], 17: [16]}, {15: 1}, [17]),
   {'garbage': [17], 'rc': {'15': 1, '16': 1}}),
  ('self-referencing garbage', ({14: [14], 19: []}, {19: 1}, [14]), {'garbage': [14], 'rc': {'19': 1}}),
  ('object with two external references',
   ({18: [19], 19: []}, {18: 2}, [18]),
   {'garbage': [], 'rc': {'18': 2, '19': 1}}),
  ('control: acyclic live candidate',
   ({11: [12], 12: []}, {11: 1}, [11, 12]),
   {'garbage': [], 'rc': {'11': 1, '12': 1}})],
 [('regression: three-object garbage cycle',
   ({21: [22], 22: [23], 23: [21]}, {}, [21]),
   {'garbage': [21, 22, 23], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({21: [22], 22: [21, 23], 23: []}, {23: 1}, [21]),
   {'garbage': [21, 22], 'rc': {'23': 1}}),
  ('externally held cycle restores its counts',
   ({21: [22], 22: [21]}, {22: 1}, [21]),
   {'garbage': [], 'rc': {'21': 1, '22': 2}}),
  ('candidate sharing a child with a live object',
   ({25: [26], 26: [], 27: [26]}, {25: 1}, [27]),
   {'garbage': [27], 'rc': {'25': 1, '26': 1}}),
  ('self-referencing garbage', ({24: [24], 29: []}, {29: 1}, [24]), {'garbage': [24], 'rc': {'29': 1}}),
  ('object with two external references',
   ({28: [29], 29: []}, {28: 2}, [28]),
   {'garbage': [], 'rc': {'28': 2, '29': 1}}),
  ('control: acyclic live candidate',
   ({21: [22], 22: []}, {21: 1}, [21, 22]),
   {'garbage': [], 'rc': {'21': 1, '22': 1}})],
 [('regression: three-object garbage cycle',
   ({31: [32], 32: [33], 33: [31]}, {}, [31]),
   {'garbage': [31, 32, 33], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({31: [32], 32: [31, 33], 33: []}, {33: 1}, [31]),
   {'garbage': [31, 32], 'rc': {'33': 1}}),
  ('externally held cycle restores its counts',
   ({31: [32], 32: [31]}, {32: 1}, [31]),
   {'garbage': [], 'rc': {'31': 1, '32': 2}}),
  ('candidate sharing a child with a live object',
   ({35: [36], 36: [], 37: [36]}, {35: 1}, [37]),
   {'garbage': [37], 'rc': {'35': 1, '36': 1}}),
  ('self-referencing garbage', ({34: [34], 39: []}, {39: 1}, [34]), {'garbage': [34], 'rc': {'39': 1}}),
  ('object with two external references',
   ({38: [39], 39: []}, {38: 2}, [38]),
   {'garbage': [], 'rc': {'38': 2, '39': 1}}),
  ('control: acyclic live candidate',
   ({31: [32], 32: []}, {31: 1}, [31, 32]),
   {'garbage': [], 'rc': {'31': 1, '32': 1}})],
 [('regression: three-object garbage cycle',
   ({41: [42], 42: [43], 43: [41]}, {}, [41]),
   {'garbage': [41, 42, 43], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({41: [42], 42: [41, 43], 43: []}, {43: 1}, [41]),
   {'garbage': [41, 42], 'rc': {'43': 1}}),
  ('externally held cycle restores its counts',
   ({41: [42], 42: [41]}, {42: 1}, [41]),
   {'garbage': [], 'rc': {'41': 1, '42': 2}}),
  ('candidate sharing a child with a live object',
   ({45: [46], 46: [], 47: [46]}, {45: 1}, [47]),
   {'garbage': [47], 'rc': {'45': 1, '46': 1}}),
  ('self-referencing garbage', ({44: [44], 49: []}, {49: 1}, [44]), {'garbage': [44], 'rc': {'49': 1}}),
  ('object with two external references',
   ({48: [49], 49: []}, {48: 2}, [48]),
   {'garbage': [], 'rc': {'48': 2, '49': 1}}),
  ('control: acyclic live candidate',
   ({41: [42], 42: []}, {41: 1}, [41, 42]),
   {'garbage': [], 'rc': {'41': 1, '42': 1}})],
 [('regression: three-object garbage cycle',
   ({51: [52], 52: [53], 53: [51]}, {}, [51]),
   {'garbage': [51, 52, 53], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({51: [52], 52: [51, 53], 53: []}, {53: 1}, [51]),
   {'garbage': [51, 52], 'rc': {'53': 1}}),
  ('externally held cycle restores its counts',
   ({51: [52], 52: [51]}, {52: 1}, [51]),
   {'garbage': [], 'rc': {'51': 1, '52': 2}}),
  ('candidate sharing a child with a live object',
   ({55: [56], 56: [], 57: [56]}, {55: 1}, [57]),
   {'garbage': [57], 'rc': {'55': 1, '56': 1}}),
  ('self-referencing garbage', ({54: [54], 59: []}, {59: 1}, [54]), {'garbage': [54], 'rc': {'59': 1}}),
  ('object with two external references',
   ({58: [59], 59: []}, {58: 2}, [58]),
   {'garbage': [], 'rc': {'58': 2, '59': 1}}),
  ('control: acyclic live candidate',
   ({51: [52], 52: []}, {51: 1}, [51, 52]),
   {'garbage': [], 'rc': {'51': 1, '52': 1}})]]
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 fixtureActualExpectedOutcome
regression: three-object garbage cycle{'garbage': [11], 'rc': {'12': 0, '13': 0}}{'garbage': [11, 12, 13], 'rc': {}}Failed
garbage cycle pointing at a live object{'garbage': [11], 'rc': {'12': 0, '13': 1}}{'garbage': [11, 12], 'rc': {'13': 1}}Failed
externally held cycle restores its counts{'garbage': [11], 'rc': {'12': 1}}{'garbage': [], 'rc': {'11': 1, '12': 2}}Failed
candidate sharing a child with a live object{'garbage': [17], 'rc': {'15': 1, '16': 1}}{'garbage': [17], 'rc': {'15': 1, '16': 1}}Passed
self-referencing garbage{'garbage': [14], 'rc': {'19': 1}}{'garbage': [14], 'rc': {'19': 1}}Passed
object with two external references{'garbage': [], 'rc': {'18': 2, '19': 1}}{'garbage': [], 'rc': {'18': 2, '19': 1}}Passed
control: acyclic live candidate{'garbage': [], 'rc': {'11': 1, '12': 1}}{'garbage': [], 'rc': {'11': 1, '12': 1}}Passed

SHA-256 / d60d152128b933d96091ba2f087724260e95e33654dee387f00427eb53b9d7f6

3 / The verified repair

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

N = 1
observations = []
def solve(heap, external, candidates):
    rc = {o: external.get(o, 0) for o in heap}
    for o, kids in heap.items():
        for c in kids:
            rc[c] += 1
    color = {o: 'black' for o in heap}
    def mark_gray(o):
        if color[o] != 'gray':
            color[o] = 'gray'
            for c in heap[o]:
                rc[c] -= 1
                mark_gray(c)
    def scan(o):
        if color[o] == 'gray':
            if rc[o] > 0:
                scan_black(o)
            else:
                color[o] = 'white'
                for c in heap[o]:
                    scan(c)
    def scan_black(o):
        color[o] = 'black'
        for c in heap[o]:
            rc[c] += 1
            if color[c] != 'black':
                scan_black(c)
    for o in candidates:
        mark_gray(o)
    for o in candidates:
        scan(o)
    garbage = sorted(o for o in heap if color[o] == 'white')
    return {'garbage': garbage, 'rc': {str(o): rc[o] for o in sorted(heap) if color[o] != 'white'}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: three-object garbage cycle',
   ({11: [12], 12: [13], 13: [11]}, {}, [11]),
   {'garbage': [11, 12, 13], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({11: [12], 12: [11, 13], 13: []}, {13: 1}, [11]),
   {'garbage': [11, 12], 'rc': {'13': 1}}),
  ('externally held cycle restores its counts',
   ({11: [12], 12: [11]}, {12: 1}, [11]),
   {'garbage': [], 'rc': {'11': 1, '12': 2}}),
  ('candidate sharing a child with a live object',
   ({15: [16], 16: [], 17: [16]}, {15: 1}, [17]),
   {'garbage': [17], 'rc': {'15': 1, '16': 1}}),
  ('self-referencing garbage', ({14: [14], 19: []}, {19: 1}, [14]), {'garbage': [14], 'rc': {'19': 1}}),
  ('object with two external references',
   ({18: [19], 19: []}, {18: 2}, [18]),
   {'garbage': [], 'rc': {'18': 2, '19': 1}}),
  ('control: acyclic live candidate',
   ({11: [12], 12: []}, {11: 1}, [11, 12]),
   {'garbage': [], 'rc': {'11': 1, '12': 1}})],
 [('regression: three-object garbage cycle',
   ({21: [22], 22: [23], 23: [21]}, {}, [21]),
   {'garbage': [21, 22, 23], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({21: [22], 22: [21, 23], 23: []}, {23: 1}, [21]),
   {'garbage': [21, 22], 'rc': {'23': 1}}),
  ('externally held cycle restores its counts',
   ({21: [22], 22: [21]}, {22: 1}, [21]),
   {'garbage': [], 'rc': {'21': 1, '22': 2}}),
  ('candidate sharing a child with a live object',
   ({25: [26], 26: [], 27: [26]}, {25: 1}, [27]),
   {'garbage': [27], 'rc': {'25': 1, '26': 1}}),
  ('self-referencing garbage', ({24: [24], 29: []}, {29: 1}, [24]), {'garbage': [24], 'rc': {'29': 1}}),
  ('object with two external references',
   ({28: [29], 29: []}, {28: 2}, [28]),
   {'garbage': [], 'rc': {'28': 2, '29': 1}}),
  ('control: acyclic live candidate',
   ({21: [22], 22: []}, {21: 1}, [21, 22]),
   {'garbage': [], 'rc': {'21': 1, '22': 1}})],
 [('regression: three-object garbage cycle',
   ({31: [32], 32: [33], 33: [31]}, {}, [31]),
   {'garbage': [31, 32, 33], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({31: [32], 32: [31, 33], 33: []}, {33: 1}, [31]),
   {'garbage': [31, 32], 'rc': {'33': 1}}),
  ('externally held cycle restores its counts',
   ({31: [32], 32: [31]}, {32: 1}, [31]),
   {'garbage': [], 'rc': {'31': 1, '32': 2}}),
  ('candidate sharing a child with a live object',
   ({35: [36], 36: [], 37: [36]}, {35: 1}, [37]),
   {'garbage': [37], 'rc': {'35': 1, '36': 1}}),
  ('self-referencing garbage', ({34: [34], 39: []}, {39: 1}, [34]), {'garbage': [34], 'rc': {'39': 1}}),
  ('object with two external references',
   ({38: [39], 39: []}, {38: 2}, [38]),
   {'garbage': [], 'rc': {'38': 2, '39': 1}}),
  ('control: acyclic live candidate',
   ({31: [32], 32: []}, {31: 1}, [31, 32]),
   {'garbage': [], 'rc': {'31': 1, '32': 1}})],
 [('regression: three-object garbage cycle',
   ({41: [42], 42: [43], 43: [41]}, {}, [41]),
   {'garbage': [41, 42, 43], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({41: [42], 42: [41, 43], 43: []}, {43: 1}, [41]),
   {'garbage': [41, 42], 'rc': {'43': 1}}),
  ('externally held cycle restores its counts',
   ({41: [42], 42: [41]}, {42: 1}, [41]),
   {'garbage': [], 'rc': {'41': 1, '42': 2}}),
  ('candidate sharing a child with a live object',
   ({45: [46], 46: [], 47: [46]}, {45: 1}, [47]),
   {'garbage': [47], 'rc': {'45': 1, '46': 1}}),
  ('self-referencing garbage', ({44: [44], 49: []}, {49: 1}, [44]), {'garbage': [44], 'rc': {'49': 1}}),
  ('object with two external references',
   ({48: [49], 49: []}, {48: 2}, [48]),
   {'garbage': [], 'rc': {'48': 2, '49': 1}}),
  ('control: acyclic live candidate',
   ({41: [42], 42: []}, {41: 1}, [41, 42]),
   {'garbage': [], 'rc': {'41': 1, '42': 1}})],
 [('regression: three-object garbage cycle',
   ({51: [52], 52: [53], 53: [51]}, {}, [51]),
   {'garbage': [51, 52, 53], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({51: [52], 52: [51, 53], 53: []}, {53: 1}, [51]),
   {'garbage': [51, 52], 'rc': {'53': 1}}),
  ('externally held cycle restores its counts',
   ({51: [52], 52: [51]}, {52: 1}, [51]),
   {'garbage': [], 'rc': {'51': 1, '52': 2}}),
  ('candidate sharing a child with a live object',
   ({55: [56], 56: [], 57: [56]}, {55: 1}, [57]),
   {'garbage': [57], 'rc': {'55': 1, '56': 1}}),
  ('self-referencing garbage', ({54: [54], 59: []}, {59: 1}, [54]), {'garbage': [54], 'rc': {'59': 1}}),
  ('object with two external references',
   ({58: [59], 59: []}, {58: 2}, [58]),
   {'garbage': [], 'rc': {'58': 2, '59': 1}}),
  ('control: acyclic live candidate',
   ({51: [52], 52: []}, {51: 1}, [51, 52]),
   {'garbage': [], 'rc': {'51': 1, '52': 1}})]]
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 fixtureActualExpectedOutcome
regression: three-object garbage cycle{'garbage': [11, 12, 13], 'rc': {}}{'garbage': [11, 12, 13], 'rc': {}}Passed
garbage cycle pointing at a live object{'garbage': [11, 12], 'rc': {'13': 1}}{'garbage': [11, 12], 'rc': {'13': 1}}Passed
externally held cycle restores its counts{'garbage': [], 'rc': {'11': 1, '12': 2}}{'garbage': [], 'rc': {'11': 1, '12': 2}}Passed
candidate sharing a child with a live object{'garbage': [17], 'rc': {'15': 1, '16': 1}}{'garbage': [17], 'rc': {'15': 1, '16': 1}}Passed
self-referencing garbage{'garbage': [14], 'rc': {'19': 1}}{'garbage': [14], 'rc': {'19': 1}}Passed
object with two external references{'garbage': [], 'rc': {'18': 2, '19': 1}}{'garbage': [], 'rc': {'18': 2, '19': 1}}Passed
control: acyclic live candidate{'garbage': [], 'rc': {'11': 1, '12': 1}}{'garbage': [], 'rc': {'11': 1, '12': 1}}Passed

SHA-256 / 5be8f38d4baf25399de8304504e72080a2d15801a4b6927e002fd6e9ba35d101

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:26.423470+00:00.

Case digest / b2e692df0a8ed54acde520f4c6a6c6fab31f9f89922486e3bb508ec7f552da8f