{"abstract":"Objects kept alive by references from outside the candidate subgraph are collected.","category":"Garbage collector invariants","checks":7,"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.","evaluation_group":"w2-garbage-collector-invariants-trial-deletion-cycles","failed_approach":"Also requiring the object to be a candidate collects shared children of live objects.","family":"w2-garbage-collector-invariants-trial-deletion-cycles-liveness-test","id":"FA-90401","implementations":{"attempt":{"sha256":"e9fc3b6ce1a9464309603e0593be6aa7c3754f4e1b83f95434bf20db985e7aa5","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(heap, external, candidates):\n    rc = {o: external.get(o, 0) for o in heap}\n    for o, kids in heap.items():\n        for c in kids:\n            rc[c] += 1\n    color = {o: 'black' for o in heap}\n    def mark_gray(o):\n        if color[o] != 'gray':\n            color[o] = 'gray'\n            for c in heap[o]:\n                rc[c] -= 1\n                mark_gray(c)\n    def scan(o):\n        if color[o] == 'gray':\n            if rc[o] > 0 and o in candidates:\n                scan_black(o)\n            else:\n                color[o] = 'white'\n                for c in heap[o]:\n                    scan(c)\n    def scan_black(o):\n        color[o] = 'black'\n        for c in heap[o]:\n            rc[c] += 1\n            if color[c] != 'black':\n                scan_black(c)\n    for o in candidates:\n        mark_gray(o)\n    for o in candidates:\n        scan(o)\n    garbage = sorted(o for o in heap if color[o] == 'white')\n    return {'garbage': garbage, 'rc': {str(o): rc[o] for o in sorted(heap) if color[o] != 'white'}}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: three-object garbage cycle',\n   ({11: [12], 12: [13], 13: [11]}, {}, [11]),\n   {'garbage': [11, 12, 13], 'rc': {}}),\n  ('garbage cycle pointing at a live object',\n   ({11: [12], 12: [11, 13], 13: []}, {13: 1}, [11]),\n   {'garbage': [11, 12], 'rc': {'13': 1}}),\n  ('externally held cycle restores its counts',\n   ({11: [12], 12: [11]}, {12: 1}, [11]),\n   {'garbage': [], 'rc': {'11': 1, '12': 2}}),\n  ('candidate sharing a child with a live object',\n   ({15: [16], 16: [], 17: [16]}, {15: 1}, [17]),\n   {'garbage': [17], 'rc': {'15': 1, '16': 1}}),\n  ('self-referencing garbage', ({14: [14], 19: []}, {19: 1}, [14]), {'garbage': [14], 'rc': {'19': 1}}),\n  ('object with two external references',\n   ({18: [19], 19: []}, {18: 2}, [18]),\n   {'garbage': [], 'rc': {'18': 2, '19': 1}}),\n  ('control: acyclic live candidate',\n   ({11: [12], 12: []}, {11: 1}, [11, 12]),\n   {'garbage': [], 'rc': {'11': 1, '12': 1}})],\n [('regression: three-object garbage cycle',\n   ({21: [22], 22: [23], 23: [21]}, {}, [21]),\n   {'garbage': [21, 22, 23], 'rc': {}}),\n  ('garbage cycle pointing at a live object',\n   ({21: [22], 22: [21, 23], 23: []}, {23: 1}, [21]),\n   {'garbage': [21, 22], 'rc': {'23': 1}}),\n  ('externally held cycle restores its counts',\n   ({21: [22], 22: [21]}, {22: 1}, [21]),\n   {'garbage': [], 'rc': {'21': 1, '22': 2}}),\n  ('candidate sharing a child with a live object',\n   ({25: [26], 26: [], 27: [26]}, {25: 1}, [27]),\n   {'garbage': [27], 'rc': {'25': 1, '26': 1}}),\n  ('self-referencing garbage', ({24: [24], 29: []}, {29: 1}, [24]), {'garbage': [24], 'rc': {'29': 1}}),\n  ('object with two external references',\n   ({28: [29], 29: []}, {28: 2}, [28]),\n   {'garbage': [], 'rc': {'28': 2, '29': 1}}),\n  ('control: acyclic live candidate',\n   ({21: [22], 22: []}, {21: 1}, [21, 22]),\n   {'garbage': [], 'rc': {'21': 1, '22': 1}})],\n [('regression: three-object garbage cycle',\n   ({31: [32], 32: [33], 33: [31]}, {}, [31]),\n   {'garbage': [31, 32, 33], 'rc': {}}),\n  ('garbage cycle pointing at a live object',\n   ({31: [32], 32: [31, 33], 33: []}, {33: 1}, [31]),\n   {'garbage': [31, 32], 'rc': {'33': 1}}),\n  ('externally held cycle restores its counts',\n   ({31: [32], 32: [31]}, {32: 1}, [31]),\n   {'garbage': [], 'rc': {'31': 1, '32': 2}}),\n  ('candidate sharing a child with a live object',\n   ({35: [36], 36: [], 37: [36]}, {35: 1}, [37]),\n   {'garbage': [37], 'rc': {'35': 1, '36': 1}}),\n  ('self-referencing garbage', ({34: [34], 39: []}, {39: 1}, [34]), {'garbage': [34], 'rc': {'39': 1}}),\n  ('object with two external references',\n   ({38: [39], 39: []}, {38: 2}, [38]),\n   {'garbage': [], 'rc': {'38': 2, '39': 1}}),\n  ('control: acyclic live candidate',\n   ({31: [32], 32: []}, {31: 1}, [31, 32]),\n   {'garbage': [], 'rc': {'31': 1, '32': 1}})],\n [('regression: three-object garbage cycle',\n   ({41: [42], 42: [43], 43: [41]}, {}, [41]),\n   {'garbage': [41, 42, 43], 'rc': {}}),\n  ('garbage cycle pointing at a live object',\n   ({41: [42], 42: [41, 43], 43: []}, {43: 1}, [41]),\n   {'garbage': [41, 42], 'rc': {'43': 1}}),\n  ('externally held cycle restores its counts',\n   ({41: [42], 42: [41]}, {42: 1}, [41]),\n   {'garbage': [], 'rc': {'41': 1, '42': 2}}),\n  ('candidate sharing a child with a live object',\n   ({45: [46], 46: [], 47: [46]}, {45: 1}, [47]),\n   {'garbage': [47], 'rc': {'45': 1, '46': 1}}),\n  ('self-referencing garbage', ({44: [44], 49: []}, {49: 1}, [44]), {'garbage': [44], 'rc': {'49': 1}}),\n  ('object with two external references',\n   ({48: [49], 49: []}, {48: 2}, [48]),\n   {'garbage': [], 'rc': {'48': 2, '49': 1}}),\n  ('control: acyclic live candidate',\n   ({41: [42], 42: []}, {41: 1}, [41, 42]),\n   {'garbage': [], 'rc': {'41': 1, '42': 1}})],\n [('regression: three-object garbage cycle',\n   ({51: [52], 52: [53], 53: [51]}, {}, [51]),\n   {'garbage': [51, 52, 53], 'rc': {}}),\n  ('garbage cycle pointing at a live object',\n   ({51: [52], 52: [51, 53], 53: []}, {53: 1}, [51]),\n   {'garbage': [51, 52], 'rc': {'53': 1}}),\n  ('externally held cycle restores its counts',\n   ({51: [52], 52: [51]}, {52: 1}, [51]),\n   {'garbage': [], 'rc': {'51': 1, '52': 2}}),\n  ('candidate sharing a child with a live object',\n   ({55: [56], 56: [], 57: [56]}, {55: 1}, [57]),\n   {'garbage': [57], 'rc': {'55': 1, '56': 1}}),\n  ('self-referencing garbage', ({54: [54], 59: []}, {59: 1}, [54]), {'garbage': [54], 'rc': {'59': 1}}),\n  ('object with two external references',\n   ({58: [59], 59: []}, {58: 2}, [58]),\n   {'garbage': [], 'rc': {'58': 2, '59': 1}}),\n  ('control: acyclic live candidate',\n   ({51: [52], 52: []}, {51: 1}, [51, 52]),\n   {'garbage': [], 'rc': {'51': 1, '52': 1}})]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"e8f254edc1fbe505bab3d52c04703fd3a1fb96f5f246f9f67bea685d69e3e1da","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(heap, external, candidates):\n    rc = {o: external.get(o, 0) for o in heap}\n    for o, kids in heap.items():\n        for c in kids:\n            rc[c] += 1\n    color = {o: 'black' for o in heap}\n    def mark_gray(o):\n        if color[o] != 'gray':\n            color[o] = 'gray'\n            for c in heap[o]:\n                rc[c] -= 1\n                mark_gray(c)\n    def scan(o):\n        if color[o] == 'gray':\n            if external.get(o, 0) > 0:\n                scan_black(o)\n            else:\n                color[o] = 'white'\n                for c in heap[o]:\n                    scan(c)\n    def scan_black(o):\n        color[o] = 'black'\n        for c in heap[o]:\n            rc[c] += 1\n            if color[c] != 'black':\n                scan_black(c)\n    for o in candidates:\n        mark_gray(o)\n    for o in candidates:\n        scan(o)\n    garbage = sorted(o for o in heap if color[o] == 'white')\n    return {'garbage': garbage, 'rc': {str(o): rc[o] for o in sorted(heap) if color[o] != 'white'}}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: three-object garbage cycle',\n   ({11: [12], 12: [13], 13: [11]}, {}, [11]),\n   {'garbage': [11, 12, 13], 'rc': {}}),\n  ('garbage cycle pointing at a live object',\n   ({11: [12], 12: [11, 13], 13: []}, {13: 1}, [11]),\n   {'garbage': [11, 12], 'rc': {'13': 1}}),\n  ('externally held cycle restores its counts',\n   ({11: [12], 12: [11]}, {12: 1}, [11]),\n   {'garbage': [], 'rc': {'11': 1, '12': 2}}),\n  ('candidate sharing a child with a live object',\n   ({15: [16], 16: [], 17: [16]}, {15: 1}, [17]),\n   {'garbage': [17], 'rc': {'15': 1, '16': 1}}),\n  ('self-referencing garbage', ({14: [14], 19: []}, {19: 1}, [14]), {'garbage': [14], 'rc': {'19': 1}}),\n  ('object with two external references',\n   ({18: [19], 19: []}, {18: 2}, [18]),\n   {'garbage': [], 'rc': {'18': 2, '19': 1}}),\n  ('control: acyclic live candidate',\n   ({11: [12], 12: []}, {11: 1}, [11, 12]),\n   {'garbage': [], 'rc': {'11': 1, '12': 1}})],\n [('regression: three-object garbage cycle',\n   ({21: [22], 22: [23], 23: [21]}, {}, [21]),\n   {'garbage': [21, 22, 23], 'rc': {}}),\n  ('garbage cycle pointing at a live object',\n   ({21: [22], 22: [21, 23], 23: []}, {23: 1}, [21]),\n   {'garbage': [21, 22], 'rc': {'23': 1}}),\n  ('externally held cycle restores its counts',\n   ({21: [22], 22: [21]}, {22: 1}, [21]),\n   {'garbage': [], 'rc': {'21': 1, '22': 2}}),\n  ('candidate sharing a child with a live object',\n   ({25: [26], 26: [], 27: [26]}, {25: 1}, [27]),\n   {'garbage': [27], 'rc': {'25': 1, '26': 1}}),\n  ('self-referencing garbage', ({24: [24], 29: []}, {29: 1}, [24]), {'garbage': [24], 'rc': {'29': 1}}),\n  ('object with two external references',\n   ({28: [29], 29: []}, {28: 2}, [28]),\n   {'garbage': [], 'rc': {'28': 2, '29': 1}}),\n  ('control: acyclic live candidate',\n   ({21: [22], 22: []}, {21: 1}, [21, 22]),\n   {'garbage': [], 'rc': {'21': 1, '22': 1}})],\n [('regression: three-object garbage cycle',\n   ({31: [32], 32: [33], 33: [31]}, {}, [31]),\n   {'garbage': [31, 32, 33], 'rc': {}}),\n  ('garbage cycle pointing at a live object',\n   ({31: [32], 32: [31, 33], 33: []}, {33: 1}, [31]),\n   {'garbage': [31, 32], 'rc': {'33': 1}}),\n  ('externally held cycle restores its counts',\n   ({31: [32], 32: [31]}, {32: 1}, [31]),\n   {'garbage': [], 'rc': {'31': 1, '32': 2}}),\n  ('candidate sharing a child with a live object',\n   ({35: [36], 36: [], 37: [36]}, {35: 1}, [37]),\n   {'garbage': [37], 'rc': {'35': 1, '36': 1}}),\n  ('self-referencing garbage', ({34: [34], 39: []}, {39: 1}, [34]), {'garbage': [34], 'rc': {'39': 1}}),\n  ('object with two external references',\n   ({38: [39], 39: []}, {38: 2}, [38]),\n   {'garbage': [], 'rc': {'38': 2, '39': 1}}),\n  ('control: acyclic live candidate',\n   ({31: [32], 32: []}, {31: 1}, [31, 32]),\n   {'garbage': [], 'rc': {'31': 1, '32': 1}})],\n [('regression: three-object garbage cycle',\n   ({41: [42], 42: [43], 43: [41]}, {}, [41]),\n   {'garbage': [41, 42, 43], 'rc': {}}),\n  ('garbage cycle pointing at a live object',\n   ({41: [42], 42: [41, 43], 43: []}, {43: 1}, [41]),\n   {'garbage': [41, 42], 'rc': {'43': 1}}),\n  ('externally held cycle restores its counts',\n   ({41: [42], 42: [41]}, {42: 1}, [41]),\n   {'garbage': [], 'rc': {'41': 1, '42': 2}}),\n  ('candidate sharing a child with a live object',\n   ({45: [46], 46: [], 47: [46]}, {45: 1}, [47]),\n   {'garbage': [47], 'rc': {'45': 1, '46': 1}}),\n  ('self-referencing garbage', ({44: [44], 49: []}, {49: 1}, [44]), {'garbage': [44], 'rc': {'49': 1}}),\n  ('object with two external references',\n   ({48: [49], 49: []}, {48: 2}, [48]),\n   {'garbage': [], 'rc': {'48': 2, '49': 1}}),\n  ('control: acyclic live candidate',\n   ({41: [42], 42: []}, {41: 1}, [41, 42]),\n   {'garbage': [], 'rc': {'41': 1, '42': 1}})],\n [('regression: three-object garbage cycle',\n   ({51: [52], 52: [53], 53: [51]}, {}, [51]),\n   {'garbage': [51, 52, 53], 'rc': {}}),\n  ('garbage cycle pointing at a live object',\n   ({51: [52], 52: [51, 53], 53: []}, {53: 1}, [51]),\n   {'garbage': [51, 52], 'rc': {'53': 1}}),\n  ('externally held cycle restores its counts',\n   ({51: [52], 52: [51]}, {52: 1}, [51]),\n   {'garbage': [], 'rc': {'51': 1, '52': 2}}),\n  ('candidate sharing a child with a live object',\n   ({55: [56], 56: [], 57: [56]}, {55: 1}, [57]),\n   {'garbage': [57], 'rc': {'55': 1, '56': 1}}),\n  ('self-referencing garbage', ({54: [54], 59: []}, {59: 1}, [54]), {'garbage': [54], 'rc': {'59': 1}}),\n  ('object with two external references',\n   ({58: [59], 59: []}, {58: 2}, [58]),\n   {'garbage': [], 'rc': {'58': 2, '59': 1}}),\n  ('control: acyclic live candidate',\n   ({51: [52], 52: []}, {51: 1}, [51, 52]),\n   {'garbage': [], 'rc': {'51': 1, '52': 1}})]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"5be8f38d4baf25399de8304504e72080a2d15801a4b6927e002fd6e9ba35d101","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(heap, external, candidates):\n    rc = {o: external.get(o, 0) for o in heap}\n    for o, kids in heap.items():\n        for c in kids:\n            rc[c] += 1\n    color = {o: 'black' for o in heap}\n    def mark_gray(o):\n        if color[o] != 'gray':\n            color[o] = 'gray'\n            for c in heap[o]:\n                rc[c] -= 1\n                mark_gray(c)\n    def scan(o):\n        if color[o] == 'gray':\n            if rc[o] > 0:\n                scan_black(o)\n            else:\n                color[o] = 'white'\n                for c in heap[o]:\n                    scan(c)\n    def scan_black(o):\n        color[o] = 'black'\n        for c in heap[o]:\n            rc[c] += 1\n            if color[c] != 'black':\n                scan_black(c)\n    for o in candidates:\n        mark_gray(o)\n    for o in candidates:\n        scan(o)\n    garbage = sorted(o for o in heap if color[o] == 'white')\n    return {'garbage': garbage, 'rc': {str(o): rc[o] for o in sorted(heap) if color[o] != 'white'}}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: three-object garbage cycle',\n   ({11: [12], 12: [13], 13: [11]}, {}, [11]),\n   {'garbage': [11, 12, 13], 'rc': {}}),\n  ('garbage cycle pointing at a live object',\n   ({11: [12], 12: [11, 13], 13: []}, {13: 1}, [11]),\n   {'garbage': [11, 12], 'rc': {'13': 1}}),\n  ('externally held cycle restores its counts',\n   ({11: [12], 12: [11]}, {12: 1}, [11]),\n   {'garbage': [], 'rc': {'11': 1, '12': 2}}),\n  ('candidate sharing a child with a live object',\n   ({15: [16], 16: [], 17: [16]}, {15: 1}, [17]),\n   {'garbage': [17], 'rc': {'15': 1, '16': 1}}),\n  ('self-referencing garbage', ({14: [14], 19: []}, {19: 1}, [14]), {'garbage': [14], 'rc': {'19': 1}}),\n  ('object with two external references',\n   ({18: [19], 19: []}, {18: 2}, [18]),\n   {'garbage': [], 'rc': {'18': 2, '19': 1}}),\n  ('control: acyclic live candidate',\n   ({11: [12], 12: []}, {11: 1}, [11, 12]),\n   {'garbage': [], 'rc': {'11': 1, '12': 1}})],\n [('regression: three-object garbage cycle',\n   ({21: [22], 22: [23], 23: [21]}, {}, [21]),\n   {'garbage': [21, 22, 23], 'rc': {}}),\n  ('garbage cycle pointing at a live object',\n   ({21: [22], 22: [21, 23], 23: []}, {23: 1}, [21]),\n   {'garbage': [21, 22], 'rc': {'23': 1}}),\n  ('externally held cycle restores its counts',\n   ({21: [22], 22: [21]}, {22: 1}, [21]),\n   {'garbage': [], 'rc': {'21': 1, '22': 2}}),\n  ('candidate sharing a child with a live object',\n   ({25: [26], 26: [], 27: [26]}, {25: 1}, [27]),\n   {'garbage': [27], 'rc': {'25': 1, '26': 1}}),\n  ('self-referencing garbage', ({24: [24], 29: []}, {29: 1}, [24]), {'garbage': [24], 'rc': {'29': 1}}),\n  ('object with two external references',\n   ({28: [29], 29: []}, {28: 2}, [28]),\n   {'garbage': [], 'rc': {'28': 2, '29': 1}}),\n  ('control: acyclic live candidate',\n   ({21: [22], 22: []}, {21: 1}, [21, 22]),\n   {'garbage': [], 'rc': {'21': 1, '22': 1}})],\n [('regression: three-object garbage cycle',\n   ({31: [32], 32: [33], 33: [31]}, {}, [31]),\n   {'garbage': [31, 32, 33], 'rc': {}}),\n  ('garbage cycle pointing at a live object',\n   ({31: [32], 32: [31, 33], 33: []}, {33: 1}, [31]),\n   {'garbage': [31, 32], 'rc': {'33': 1}}),\n  ('externally held cycle restores its counts',\n   ({31: [32], 32: [31]}, {32: 1}, [31]),\n   {'garbage': [], 'rc': {'31': 1, '32': 2}}),\n  ('candidate sharing a child with a live object',\n   ({35: [36], 36: [], 37: [36]}, {35: 1}, [37]),\n   {'garbage': [37], 'rc': {'35': 1, '36': 1}}),\n  ('self-referencing garbage', ({34: [34], 39: []}, {39: 1}, [34]), {'garbage': [34], 'rc': {'39': 1}}),\n  ('object with two external references',\n   ({38: [39], 39: []}, {38: 2}, [38]),\n   {'garbage': [], 'rc': {'38': 2, '39': 1}}),\n  ('control: acyclic live candidate',\n   ({31: [32], 32: []}, {31: 1}, [31, 32]),\n   {'garbage': [], 'rc': {'31': 1, '32': 1}})],\n [('regression: three-object garbage cycle',\n   ({41: [42], 42: [43], 43: [41]}, {}, [41]),\n   {'garbage': [41, 42, 43], 'rc': {}}),\n  ('garbage cycle pointing at a live object',\n   ({41: [42], 42: [41, 43], 43: []}, {43: 1}, [41]),\n   {'garbage': [41, 42], 'rc': {'43': 1}}),\n  ('externally held cycle restores its counts',\n   ({41: [42], 42: [41]}, {42: 1}, [41]),\n   {'garbage': [], 'rc': {'41': 1, '42': 2}}),\n  ('candidate sharing a child with a live object',\n   ({45: [46], 46: [], 47: [46]}, {45: 1}, [47]),\n   {'garbage': [47], 'rc': {'45': 1, '46': 1}}),\n  ('self-referencing garbage', ({44: [44], 49: []}, {49: 1}, [44]), {'garbage': [44], 'rc': {'49': 1}}),\n  ('object with two external references',\n   ({48: [49], 49: []}, {48: 2}, [48]),\n   {'garbage': [], 'rc': {'48': 2, '49': 1}}),\n  ('control: acyclic live candidate',\n   ({41: [42], 42: []}, {41: 1}, [41, 42]),\n   {'garbage': [], 'rc': {'41': 1, '42': 1}})],\n [('regression: three-object garbage cycle',\n   ({51: [52], 52: [53], 53: [51]}, {}, [51]),\n   {'garbage': [51, 52, 53], 'rc': {}}),\n  ('garbage cycle pointing at a live object',\n   ({51: [52], 52: [51, 53], 53: []}, {53: 1}, [51]),\n   {'garbage': [51, 52], 'rc': {'53': 1}}),\n  ('externally held cycle restores its counts',\n   ({51: [52], 52: [51]}, {52: 1}, [51]),\n   {'garbage': [], 'rc': {'51': 1, '52': 2}}),\n  ('candidate sharing a child with a live object',\n   ({55: [56], 56: [], 57: [56]}, {55: 1}, [57]),\n   {'garbage': [57], 'rc': {'55': 1, '56': 1}}),\n  ('self-referencing garbage', ({54: [54], 59: []}, {59: 1}, [54]), {'garbage': [54], 'rc': {'59': 1}}),\n  ('object with two external references',\n   ({58: [59], 59: []}, {58: 2}, [58]),\n   {'garbage': [], 'rc': {'58': 2, '59': 1}}),\n  ('control: acyclic live candidate',\n   ({51: [52], 52: []}, {51: 1}, [51, 52]),\n   {'garbage': [], 'rc': {'51': 1, '52': 1}})]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"A deterministic, bounded teaching model of one garbage-collector mechanism with stipulated rules; it is not a production collector and claims no conformance to any particular runtime. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-garbage-collector-invariants-trial-deletion-cycles-liveness-test","generated_at":"2026-09-29T14:51:26.377031+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Cycle collectors for reference-counted heaps depend on exact decrement/restore bookkeeping.","repair":"An object with any remaining count is live.","root_cause":"scan tests the external reference count instead of the count remaining after trial deletion.","sha256":"ff3fda1814cc39f6676f5316a05347a971fdb10168c1b7ab4f4972db3551986f","title":"Trial deletion: only external roots keep gray objects alive · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":42.182,"exit_code":1,"observations":[{"actual":{"garbage":[11,12,13],"rc":{}},"check":"regression: three-object garbage cycle","expected":{"garbage":[11,12,13],"rc":{}},"passed":true},{"actual":{"garbage":[11,12,13],"rc":{}},"check":"garbage cycle pointing at a live object","expected":{"garbage":[11,12],"rc":{"13":1}},"passed":false},{"actual":{"garbage":[11,12],"rc":{}},"check":"externally held cycle restores its counts","expected":{"garbage":[],"rc":{"11":1,"12":2}},"passed":false},{"actual":{"garbage":[16,17],"rc":{"15":1}},"check":"candidate sharing a child with a live object","expected":{"garbage":[17],"rc":{"15":1,"16":1}},"passed":false},{"actual":{"garbage":[14],"rc":{"19":1}},"check":"self-referencing garbage","expected":{"garbage":[14],"rc":{"19":1}},"passed":true},{"actual":{"garbage":[],"rc":{"18":2,"19":1}},"check":"object with two external references","expected":{"garbage":[],"rc":{"18":2,"19":1}},"passed":true},{"actual":{"garbage":[],"rc":{"11":1,"12":1}},"check":"control: acyclic live candidate","expected":{"garbage":[],"rc":{"11":1,"12":1}},"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: three-object garbage cycle\", \"actual\": {\"garbage\": [11, 12, 13], \"rc\": {}}, \"expected\": {\"garbage\": [11, 12, 13], \"rc\": {}}, \"passed\": true}, {\"check\": \"garbage cycle pointing at a live object\", \"actual\": {\"garbage\": [11, 12, 13], \"rc\": {}}, \"expected\": {\"garbage\": [11, 12], \"rc\": {\"13\": 1}}, \"passed\": false}, {\"check\": \"externally held cycle restores its counts\", \"actual\": {\"garbage\": [11, 12], \"rc\": {}}, \"expected\": {\"garbage\": [], \"rc\": {\"11\": 1, \"12\": 2}}, \"passed\": false}, {\"check\": \"candidate sharing a child with a live object\", \"actual\": {\"garbage\": [16, 17], \"rc\": {\"15\": 1}}, \"expected\": {\"garbage\": [17], \"rc\": {\"15\": 1, \"16\": 1}}, \"passed\": false}, {\"check\": \"self-referencing garbage\", \"actual\": {\"garbage\": [14], \"rc\": {\"19\": 1}}, \"expected\": {\"garbage\": [14], \"rc\": {\"19\": 1}}, \"passed\": true}, {\"check\": \"object with two external references\", \"actual\": {\"garbage\": [], \"rc\": {\"18\": 2, \"19\": 1}}, \"expected\": {\"garbage\": [], \"rc\": {\"18\": 2, \"19\": 1}}, \"passed\": true}, {\"check\": \"control: acyclic live candidate\", \"actual\": {\"garbage\": [], \"rc\": {\"11\": 1, \"12\": 1}}, \"expected\": {\"garbage\": [], \"rc\": {\"11\": 1, \"12\": 1}}, \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":42.361,"exit_code":1,"observations":[{"actual":{"garbage":[11,12,13],"rc":{}},"check":"regression: three-object garbage cycle","expected":{"garbage":[11,12,13],"rc":{}},"passed":true},{"actual":{"garbage":[11,12],"rc":{"13":1}},"check":"garbage cycle pointing at a live object","expected":{"garbage":[11,12],"rc":{"13":1}},"passed":true},{"actual":{"garbage":[],"rc":{"11":1,"12":2}},"check":"externally held cycle restores its counts","expected":{"garbage":[],"rc":{"11":1,"12":2}},"passed":true},{"actual":{"garbage":[16,17],"rc":{"15":1}},"check":"candidate sharing a child with a live object","expected":{"garbage":[17],"rc":{"15":1,"16":1}},"passed":false},{"actual":{"garbage":[14],"rc":{"19":1}},"check":"self-referencing garbage","expected":{"garbage":[14],"rc":{"19":1}},"passed":true},{"actual":{"garbage":[],"rc":{"18":2,"19":1}},"check":"object with two external references","expected":{"garbage":[],"rc":{"18":2,"19":1}},"passed":true},{"actual":{"garbage":[],"rc":{"11":1,"12":1}},"check":"control: acyclic live candidate","expected":{"garbage":[],"rc":{"11":1,"12":1}},"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: three-object garbage cycle\", \"actual\": {\"garbage\": [11, 12, 13], \"rc\": {}}, \"expected\": {\"garbage\": [11, 12, 13], \"rc\": {}}, \"passed\": true}, {\"check\": \"garbage cycle pointing at a live object\", \"actual\": {\"garbage\": [11, 12], \"rc\": {\"13\": 1}}, \"expected\": {\"garbage\": [11, 12], \"rc\": {\"13\": 1}}, \"passed\": true}, {\"check\": \"externally held cycle restores its counts\", \"actual\": {\"garbage\": [], \"rc\": {\"11\": 1, \"12\": 2}}, \"expected\": {\"garbage\": [], \"rc\": {\"11\": 1, \"12\": 2}}, \"passed\": true}, {\"check\": \"candidate sharing a child with a live object\", \"actual\": {\"garbage\": [16, 17], \"rc\": {\"15\": 1}}, \"expected\": {\"garbage\": [17], \"rc\": {\"15\": 1, \"16\": 1}}, \"passed\": false}, {\"check\": \"self-referencing garbage\", \"actual\": {\"garbage\": [14], \"rc\": {\"19\": 1}}, \"expected\": {\"garbage\": [14], \"rc\": {\"19\": 1}}, \"passed\": true}, {\"check\": \"object with two external references\", \"actual\": {\"garbage\": [], \"rc\": {\"18\": 2, \"19\": 1}}, \"expected\": {\"garbage\": [], \"rc\": {\"18\": 2, \"19\": 1}}, \"passed\": true}, {\"check\": \"control: acyclic live candidate\", \"actual\": {\"garbage\": [], \"rc\": {\"11\": 1, \"12\": 1}}, \"expected\": {\"garbage\": [], \"rc\": {\"11\": 1, \"12\": 1}}, \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":38.801,"exit_code":0,"observations":[{"actual":{"garbage":[11,12,13],"rc":{}},"check":"regression: three-object garbage cycle","expected":{"garbage":[11,12,13],"rc":{}},"passed":true},{"actual":{"garbage":[11,12],"rc":{"13":1}},"check":"garbage cycle pointing at a live object","expected":{"garbage":[11,12],"rc":{"13":1}},"passed":true},{"actual":{"garbage":[],"rc":{"11":1,"12":2}},"check":"externally held cycle restores its counts","expected":{"garbage":[],"rc":{"11":1,"12":2}},"passed":true},{"actual":{"garbage":[17],"rc":{"15":1,"16":1}},"check":"candidate sharing a child with a live object","expected":{"garbage":[17],"rc":{"15":1,"16":1}},"passed":true},{"actual":{"garbage":[14],"rc":{"19":1}},"check":"self-referencing garbage","expected":{"garbage":[14],"rc":{"19":1}},"passed":true},{"actual":{"garbage":[],"rc":{"18":2,"19":1}},"check":"object with two external references","expected":{"garbage":[],"rc":{"18":2,"19":1}},"passed":true},{"actual":{"garbage":[],"rc":{"11":1,"12":1}},"check":"control: acyclic live candidate","expected":{"garbage":[],"rc":{"11":1,"12":1}},"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: three-object garbage cycle\", \"actual\": {\"garbage\": [11, 12, 13], \"rc\": {}}, \"expected\": {\"garbage\": [11, 12, 13], \"rc\": {}}, \"passed\": true}, {\"check\": \"garbage cycle pointing at a live object\", \"actual\": {\"garbage\": [11, 12], \"rc\": {\"13\": 1}}, \"expected\": {\"garbage\": [11, 12], \"rc\": {\"13\": 1}}, \"passed\": true}, {\"check\": \"externally held cycle restores its counts\", \"actual\": {\"garbage\": [], \"rc\": {\"11\": 1, \"12\": 2}}, \"expected\": {\"garbage\": [], \"rc\": {\"11\": 1, \"12\": 2}}, \"passed\": true}, {\"check\": \"candidate sharing a child with a live object\", \"actual\": {\"garbage\": [17], \"rc\": {\"15\": 1, \"16\": 1}}, \"expected\": {\"garbage\": [17], \"rc\": {\"15\": 1, \"16\": 1}}, \"passed\": true}, {\"check\": \"self-referencing garbage\", \"actual\": {\"garbage\": [14], \"rc\": {\"19\": 1}}, \"expected\": {\"garbage\": [14], \"rc\": {\"19\": 1}}, \"passed\": true}, {\"check\": \"object with two external references\", \"actual\": {\"garbage\": [], \"rc\": {\"18\": 2, \"19\": 1}}, \"expected\": {\"garbage\": [], \"rc\": {\"18\": 2, \"19\": 1}}, \"passed\": true}, {\"check\": \"control: acyclic live candidate\", \"actual\": {\"garbage\": [], \"rc\": {\"11\": 1, \"12\": 1}}, \"expected\": {\"garbage\": [], \"rc\": {\"11\": 1, \"12\": 1}}, \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}