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

N = 1
observations = []
def solve(classes, objects, roots):
    def ref_slots(o):
        ob = objects[o]
        cls = classes[ob['class']]
        if cls['kind'] == 'objarray':
            return list(range(3, 3 + ob['words'][2]))
        if cls['kind'] == 'primarray':
            return []
        slots = []
        c = ob['class']
        while c is not None:
            for off, cnt in classes[c]['maps']:
                slots.extend(range(off, off + cnt))
            c = None
        return slots
    seen = set()
    stack = list(roots)
    bad = []
    while stack:
        o = stack.pop()
        if o in seen:
            continue
        seen.add(o)
        words = objects[o]['words']
        for s in ref_slots(o):
            v = words[s]
            if v == 0:
                continue
            if v not in objects:
                bad.append([o, s])
                continue
            stack.append(v)
    return {'live': sorted(seen), 'bad': sorted(bad)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: trace through fields, arrays and subclasses',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 6, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [100]),
   {'bad': [], 'live': [100, 101, 102, 103, 104, 107]}),
  ('object array elements and trailing padding',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 6, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [102]),
   {'bad': [], 'live': [102, 103, 104, 107]}),
  ('primitive array contents are not references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 6, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [103]),
   {'bad': [], 'live': [103]}),
  ('inherited reference field of a subclass',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 6, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [104]),
   {'bad': [], 'live': [104, 107]}),
  ('integer field that equals an object id',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 6, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [109, 101]),
   {'bad': [], 'live': [101, 105, 109]}),
  ('control: base object without references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 6, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [106]),
   {'bad': [], 'live': [106]})],
 [('regression: trace through fields, arrays and subclasses',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 7, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [100]),
   {'bad': [], 'live': [100, 101, 102, 103, 104, 107]}),
  ('object array elements and trailing padding',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 7, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [102]),
   {'bad': [], 'live': [102, 103, 104, 107]}),
  ('primitive array contents are not references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 7, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [103]),
   {'bad': [], 'live': [103]}),
  ('inherited reference field of a subclass',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 7, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [104]),
   {'bad': [], 'live': [104, 107]}),
  ('integer field that equals an object id',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 7, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [109, 101]),
   {'bad': [], 'live': [101, 105, 109]}),
  ('control: base object without references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 7, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [107]),
   {'bad': [], 'live': [107]})],
 [('regression: trace through fields, arrays and subclasses',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 8, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [100]),
   {'bad': [], 'live': [100, 101, 102, 103, 104, 107]}),
  ('object array elements and trailing padding',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 8, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [102]),
   {'bad': [], 'live': [102, 103, 104, 107]}),
  ('primitive array contents are not references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 8, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [103]),
   {'bad': [], 'live': [103]}),
  ('inherited reference field of a subclass',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 8, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [104]),
   {'bad': [], 'live': [104, 107]}),
  ('integer field that equals an object id',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 8, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [109, 101]),
   {'bad': [], 'live': [101, 105, 109]}),
  ('control: base object without references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 8, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [105]),
   {'bad': [], 'live': [105]})],
 [('regression: trace through fields, arrays and subclasses',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 9, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [100]),
   {'bad': [], 'live': [100, 101, 102, 103, 104, 107]}),
  ('object array elements and trailing padding',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 9, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [102]),
   {'bad': [], 'live': [102, 103, 104, 107]}),
  ('primitive array contents are not references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 9, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [103]),
   {'bad': [], 'live': [103]}),
  ('inherited reference field of a subclass',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 9, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [104]),
   {'bad': [], 'live': [104, 107]}),
  ('integer field that equals an object id',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 9, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [109, 101]),
   {'bad': [], 'live': [101, 105, 109]}),
  ('control: base object without references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 9, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [106]),
   {'bad': [], 'live': [106]})],
 [('regression: trace through fields, arrays and subclasses',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 10, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [100]),
   {'bad': [], 'live': [100, 101, 102, 103, 104, 107]}),
  ('object array elements and trailing padding',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 10, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [102]),
   {'bad': [], 'live': [102, 103, 104, 107]}),
  ('primitive array contents are not references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 10, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [103]),
   {'bad': [], 'live': [103]}),
  ('inherited reference field of a subclass',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 10, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [104]),
   {'bad': [], 'live': [104, 107]}),
  ('integer field that equals an object id',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 10, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [109, 101]),
   {'bad': [], 'live': [101, 105, 109]}),
  ('control: base object without references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 10, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [107]),
   {'bad': [], 'live': [107]})]]
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(classes, objects, roots):
    def ref_slots(o):
        ob = objects[o]
        cls = classes[ob['class']]
        if cls['kind'] == 'objarray':
            return list(range(3, 3 + ob['words'][2]))
        if cls['kind'] == 'primarray':
            return []
        slots = []
        c = ob['class']
        while c is not None:
            for off, cnt in classes[c]['maps']:
                slots.extend(range(off, off + cnt))
            c = classes[c]['super'] if not classes[c]['maps'] else None
        return slots
    seen = set()
    stack = list(roots)
    bad = []
    while stack:
        o = stack.pop()
        if o in seen:
            continue
        seen.add(o)
        words = objects[o]['words']
        for s in ref_slots(o):
            v = words[s]
            if v == 0:
                continue
            if v not in objects:
                bad.append([o, s])
                continue
            stack.append(v)
    return {'live': sorted(seen), 'bad': sorted(bad)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: trace through fields, arrays and subclasses',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 6, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [100]),
   {'bad': [], 'live': [100, 101, 102, 103, 104, 107]}),
  ('object array elements and trailing padding',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 6, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [102]),
   {'bad': [], 'live': [102, 103, 104, 107]}),
  ('primitive array contents are not references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 6, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [103]),
   {'bad': [], 'live': [103]}),
  ('inherited reference field of a subclass',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 6, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [104]),
   {'bad': [], 'live': [104, 107]}),
  ('integer field that equals an object id',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 6, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [109, 101]),
   {'bad': [], 'live': [101, 105, 109]}),
  ('control: base object without references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 6, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [106]),
   {'bad': [], 'live': [106]})],
 [('regression: trace through fields, arrays and subclasses',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 7, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [100]),
   {'bad': [], 'live': [100, 101, 102, 103, 104, 107]}),
  ('object array elements and trailing padding',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 7, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [102]),
   {'bad': [], 'live': [102, 103, 104, 107]}),
  ('primitive array contents are not references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 7, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [103]),
   {'bad': [], 'live': [103]}),
  ('inherited reference field of a subclass',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 7, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [104]),
   {'bad': [], 'live': [104, 107]}),
  ('integer field that equals an object id',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 7, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [109, 101]),
   {'bad': [], 'live': [101, 105, 109]}),
  ('control: base object without references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 7, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [107]),
   {'bad': [], 'live': [107]})],
 [('regression: trace through fields, arrays and subclasses',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 8, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [100]),
   {'bad': [], 'live': [100, 101, 102, 103, 104, 107]}),
  ('object array elements and trailing padding',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 8, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [102]),
   {'bad': [], 'live': [102, 103, 104, 107]}),
  ('primitive array contents are not references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 8, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [103]),
   {'bad': [], 'live': [103]}),
  ('inherited reference field of a subclass',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 8, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [104]),
   {'bad': [], 'live': [104, 107]}),
  ('integer field that equals an object id',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 8, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [109, 101]),
   {'bad': [], 'live': [101, 105, 109]}),
  ('control: base object without references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 8, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [105]),
   {'bad': [], 'live': [105]})],
 [('regression: trace through fields, arrays and subclasses',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 9, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [100]),
   {'bad': [], 'live': [100, 101, 102, 103, 104, 107]}),
  ('object array elements and trailing padding',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 9, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [102]),
   {'bad': [], 'live': [102, 103, 104, 107]}),
  ('primitive array contents are not references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 9, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [103]),
   {'bad': [], 'live': [103]}),
  ('inherited reference field of a subclass',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 9, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [104]),
   {'bad': [], 'live': [104, 107]}),
  ('integer field that equals an object id',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 9, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [109, 101]),
   {'bad': [], 'live': [101, 105, 109]}),
  ('control: base object without references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 9, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [106]),
   {'bad': [], 'live': [106]})],
 [('regression: trace through fields, arrays and subclasses',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 10, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [100]),
   {'bad': [], 'live': [100, 101, 102, 103, 104, 107]}),
  ('object array elements and trailing padding',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 10, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [102]),
   {'bad': [], 'live': [102, 103, 104, 107]}),
  ('primitive array contents are not references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 10, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [103]),
   {'bad': [], 'live': [103]}),
  ('inherited reference field of a subclass',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 10, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [104]),
   {'bad': [], 'live': [104, 107]}),
  ('integer field that equals an object id',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 10, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [109, 101]),
   {'bad': [], 'live': [101, 105, 109]}),
  ('control: base object without references',
   ({'Base': {'kind': 'instance', 'maps': [[2, 1]], 'super': None},
     'Derived': {'kind': 'instance', 'maps': [[4, 2]], 'super': 'Base'},
     'Leaf': {'kind': 'instance', 'maps': [], 'super': 'Derived'},
     'Object[]': {'kind': 'objarray', 'maps': [], 'super': None},
     'int[]': {'kind': 'primarray', 'maps': [], 'super': None}},
    {100: {'class': 'Derived', 'words': [51966, 0, 101, 7, 102, 0, 999]},
     101: {'class': 'Base', 'words': [51966, 0, 0, 105]},
     102: {'class': 'Object[]', 'words': [51966, 0, 2, 103, 104, 106]},
     103: {'class': 'int[]', 'words': [51966, 0, 3, 106, 10, 107]},
     104: {'class': 'Leaf', 'words': [51966, 0, 0, 108, 0, 107, 0]},
     105: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     106: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     107: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     108: {'class': 'Base', 'words': [51966, 0, 0, 0]},
     109: {'class': 'Derived', 'words': [51966, 0, 105, 106, 0, 0, 0]}},
    [107]),
   {'bad': [], 'live': [107]})]]
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:
Fields declared in superclasses are not traced for subclass instances.

Precise tracing with per-class reference maps. Objects are word lists: words 0-1 are the header; object arrays keep their length in word 2 and elements in words 3..3+len-1 (anything after is padding); primitive arrays contain no references. Instance classes list [offset, count] runs of reference words and inherit all superclass runs. A reference word of 0 is null; a nonzero reference that is not an object id is reported as [object, word]. Return the reachable ids and the bad references.

split: open-access


prompt:
After growing, the free share is still just below the minimum and the heap grows again next cycle.

After each full collection with live bytes L and capacity C: if the free share (C - L) / C is below min_free percent, grow to the smallest capacity whose free share is at least min_free, i.e. ceil(L * 100 / (100 - min_free)), never shrinking and never above max_heap; if the free share exceeds max_free percent, compute ceil(L * 100 / (100 - max_free)) floored at min_heap and move shrink_pct percent of the way from C toward it (integer arithmetic). Otherwise keep C. Return the capacity after each collection.

split: open-access


prompt:
The heap grows past its configured maximum.

After each full collection with live bytes L and capacity C: if the free share (C - L) / C is below min_free percent, grow to the smallest capacity whose free share is at least min_free, i.e. ceil(L * 100 / (100 - min_free)), never shrinking and never above max_heap; if the free share exceeds max_free percent, compute ceil(L * 100 / (100 - max_free)) floored at min_heap and move shrink_pct percent of the way from C toward it (integer arithmetic). Otherwise keep C. Return the capacity after each collection.

split: open-access


prompt:
Nearly empty heaps shrink below the configured minimum.

After each full collection with live bytes L and capacity C: if the free share (C - L) / C is below min_free percent, grow to the smallest capacity whose free share is at least min_free, i.e. ceil(L * 100 / (100 - min_free)), never shrinking and never above max_heap; if the free share exceeds max_free percent, compute ceil(L * 100 / (100 - max_free)) floored at min_heap and move shrink_pct percent of the way from C toward it (integer arithmetic). Otherwise keep C. Return the capacity after each collection.

split: open-access


prompt:
Shrinking removes a fixed share of the heap and can drop below the target.

After each full collection with live bytes L and capacity C: if the free share (C - L) / C is below min_free percent, grow to the smallest capacity whose free share is at least min_free, i.e. ceil(L * 100 / (100 - min_free)), never shrinking and never above max_heap; if the free share exceeds max_free percent, compute ceil(L * 100 / (100 - max_free)) floored at min_heap and move shrink_pct percent of the way from C toward it (integer arithmetic). Otherwise keep C. Return the capacity after each collection.

split: open-access


prompt:
Every collection grows the heap regardless of free space.

After each full collection with live bytes L and capacity C: if the free share (C - L) / C is below min_free percent, grow to the smallest capacity whose free share is at least min_free, i.e. ceil(L * 100 / (100 - min_free)), never shrinking and never above max_heap; if the free share exceeds max_free percent, compute ceil(L * 100 / (100 - max_free)) floored at min_heap and move shrink_pct percent of the way from C toward it (integer arithmetic). Otherwise keep C. Return the capacity after each collection.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
import cmath
N = 1
observations = []
def solve(x):
    n, gates = x
    dim = 1 << n
    st = [0j] * dim
    st[0] = 1 + 0j
    r = 1 / math.sqrt(2)
    for g in gates:
        op = g[0]
        if op in ('h', 'x', 'y', 'z', 's', 'sdg', 't'):
            m = 1 << g[1]
            for i in range(dim):
                if i & m:
                    continue
                a, b = st[i], st[i | m]
                if op == 'h':
                    st[i], st[i | m] = (a + b) * r, (a - b) * r
                elif op == 'x':
                    st[i], st[i | m] = b, a
                elif op == 'y':
                    st[i], st[i | m] = -1j * b, 1j * a
                elif op == 'z':
                    st[i | m] = -b
                elif op == 's':
                    st[i | m] = 1j * b
                elif op == 'sdg':
                    st[i | m] = -1j * b
                else:
                    st[i | m] = b * cmath.exp(1j * math.pi / 4)
        elif op == 'cx':
            c, t = 1 << g[2], 1 << g[1]
            for i in range(dim):
                if i & c and not i & t:
                    st[i], st[i | t] = st[i | t], st[i]
        elif op == 'cz':
            both = (1 << g[1]) | (1 << g[2])
            for i in range(dim):
                if i & both == both:
                    st[i] = -st[i]
        elif op == 'swap':
            a, b = 1 << g[1], 1 << g[2]
            for i in range(dim):
                if i & a and not i & b:
                    j = (i ^ a) | b
                    st[i], st[j] = st[j], st[i]
    return [[round(v.real, 6) + 0.0, round(v.imag, 6) + 0.0] for v in st]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression: bell pair', [2, [['h', 0], ['cx', 0, 1]]], [[0.707107, 0.0], [0.0, 0.0], [0.0, 0.0], [0.707107, 0.0]]], ['regression: ghz three qubits', [3, [['h', 0], ['cx', 0, 1], ['cx', 1, 2]]], [[0.707107, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.707107, 0.0]]], ['regression: cx with control on high qubit', [2, [['x', 1], ['cx', 1, 0]]], [[0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [1.0, 0.0]]], ['control: empty circuit on two qubits', [2, []], [[1.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['control: swap moves excitation', [3, [['x', 0], ['swap', 0, 2]]], [[0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [1.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['control: y on ground state', [1, [['y', 0]]], [[0.0, 0.0], [0.0, 1.0]]], ['control: y after x', [1, [['x', 0], ['y', 0]]], [[0.0, -1.0], [0.0, 0.0]]]], [['regression: random circuit 6', [2, [['cz', 0, 1], ['cz', 0, 1], ['z', 1], ['sdg', 0], ['x', 0], ['x', 1], ['cx', 0, 1]]], [[0.0, 0.0], [1.0, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['regression: random circuit 7', [2, [['s', 0], ['cz', 1, 0], ['x', 1], ['cx', 1, 0], ['swap', 1, 0]]], [[0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [1.0, 0.0]]], ['regression: random circuit 29', [2, [['h', 1], ['sdg', 0], ['cx', 1, 0], ['z', 1], ['h', 1], ['t', 0], ['s', 1]]], [[0.5, 0.0], [-0.353553, -0.353553], [0.0, 0.5], [-0.353553, 0.353553]]], ['control: t after h', [1, [['h', 0], ['t', 0]]], [[0.707107, 0.0], [0.5, 0.5]]], ['control: sdg after h', [2, [['h', 1], ['sdg', 1]]], [[0.707107, 0.0], [0.0, 0.0], [0.0, -0.707107], [0.0, 0.0]]], ['control: h on excited qubit', [1, [['x', 0], ['h', 0]]], [[0.707107, 0.0], [-0.707107, 0.0]]], ['control: single x on qubit 0 of three', [3, [['x', 0]]], [[0.0, 0.0], [1.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]]], [['regression: random circuit 12', [3, [['sdg', 2], ['h', 2], ['h', 1], ['s', 0], ['z', 0], ['cx', 0, 1]]], [[0.5, 0.0], [0.0, 0.0], [0.5, 0.0], [0.0, 0.0], [0.5, 0.0], [0.0, 0.0], [0.5, 0.0], [0.0, 0.0]]], ['regression: random circuit 21', [3, [['cz', 2, 0], ['s', 0], ['cx', 1, 0], ['y', 2], ['sdg', 0], ['sdg', 2], ['cx', 0, 2]]], [[0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [1.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['regression: random circuit 39', [3, [['swap', 0, 2], ['cx', 2, 1], ['y', 2], ['z', 2], ['cx', 0, 1], ['sdg', 0], ['cx', 2, 0]]], [[0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, -1.0], [0.0, 0.0], [0.0, 0.0]]], ['control: random circuit 0', [3, [['swap', 2, 1], ['cx', 2, 0], ['z', 2], ['y', 1], ['cx', 0, 2], ['s', 1], ['swap', 1, 0]]], [[0.0, 0.0], [-1.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['control: random circuit 1', [3, [['cx', 1, 2], ['cz', 2, 1]]], [[1.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['control: random circuit 2', [3, [['z', 0], ['sdg', 1], ['cx', 1, 0], ['cz', 0, 1], ['cx', 2, 0], ['y', 0], ['z', 2]]], [[0.0, 0.0], [0.0, 1.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['control: random circuit 3', [2, [['x', 1], ['s', 1], ['x', 0], ['h', 0], ['s', 1], ['h', 1]]], [[-0.5, 0.0], [0.5, 0.0], [0.5, 0.0], [-0.5, 0.0]]]], [['regression: random circuit 29', [2, [['h', 1], ['sdg', 0], ['cx', 1, 0], ['z', 1], ['h', 1], ['t', 0], ['s', 1]]], [[0.5, 0.0], [-0.353553, -0.353553], [0.0, 0.5], [-0.353553, 0.353553]]], ['regression: random circuit 38', [2, [['sdg', 0], ['x', 0], ['cx', 0, 1], ['z', 1]]], [[0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [-1.0, 0.0]]], ['regression: cx with control on high qubit', [2, [['x', 1], ['cx', 1, 0]]], [[0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [1.0, 0.0]]], ['control: random circuit 4', [2, [['cx', 0, 1], ['cz', 0, 1], ['h', 1], ['x', 1], ['y', 0], ['swap', 0, 1]]], [[0.0, 0.0], [0.0, 0.0], [0.0, 0.707107], [0.0, 0.707107]]], ['control: random circuit 5', [2, [['cx', 1, 0], ['cx', 0, 1], ['t', 1], ['h', 1]]], [[0.707107, 0.0], [0.0, 0.0], [0.707107, 0.0], [0.0, 0.0]]], ['control: random circuit 8', [1, [['s', 0], ['h', 0], ['s', 0]]], [[0.707107, 0.0], [0.0, 0.707107]]], ['control: random circuit 9', [1, [['z', 0], ['t', 0], ['z', 0], ['h', 0]]], [[0.707107, 0.0], [0.707107, 0.0]]]], [['regression: bell pair', [2, [['h', 0], ['cx', 0, 1]]], [[0.707107, 0.0], [0.0, 0.0], [0.0, 0.0], [0.707107, 0.0]]], ['regression: ghz three qubits', [3, [['h', 0], ['cx', 0, 1], ['cx', 1, 2]]], [[0.707107, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.707107, 0.0]]], ['regression: random circuit 29', [2, [['h', 1], ['sdg', 0], ['cx', 1, 0], ['z', 1], ['h', 1], ['t', 0], ['s', 1]]], [[0.5, 0.0], [-0.353553, -0.353553], [0.0, 0.5], [-0.353553, 0.353553]]], ['control: random circuit 11', [2, [['s', 0], ['h', 0]]], [[0.707107, 0.0], [0.707107, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['control: random circuit 13', [2, [['sdg', 0], ['cz', 0, 1], ['swap', 0, 1], ['cx', 1, 0]]], [[1.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['control: random circuit 14', [2, [['z', 0], ['swap', 0, 1], ['x', 1], ['t', 0]]], [[0.0, 0.0], [0.0, 0.0], [1.0, 0.0], [0.0, 0.0]]], ['control: random circuit 15', [2, [['cx', 1, 0], ['z', 0], ['cz', 1, 0], ['h', 1], ['h', 0], ['y', 1], ['h', 1]]], [[0.0, 0.0], [0.0, 0.0], [0.0, -0.707107], [0.0, -0.707107]]]]]
for label, args, expected in fixtures[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
import math
import cmath
N = 1
observations = []
def solve(x):
    n, gates = x
    dim = 1 << n
    st = [0j] * dim
    st[0] = 1 + 0j
    r = 1 / math.sqrt(2)
    for g in gates:
        op = g[0]
        if op in ('h', 'x', 'y', 'z', 's', 'sdg', 't'):
            m = 1 << g[1]
            for i in range(dim):
                if i & m:
                    continue
                a, b = st[i], st[i | m]
                if op == 'h':
                    st[i], st[i | m] = (a + b) * r, (a - b) * r
                elif op == 'x':
                    st[i], st[i | m] = b, a
                elif op == 'y':
                    st[i], st[i | m] = -1j * b, 1j * a
                elif op == 'z':
                    st[i | m] = -b
                elif op == 's':
                    st[i | m] = 1j * b
                elif op == 'sdg':
                    st[i | m] = -1j * b
                else:
                    st[i | m] = b * cmath.exp(1j * math.pi / 4)
        elif op == 'cx':
            c, t = 1 << g[1], 1 << g[2]
            for i in range(dim):
                if i & c == 1 and not i & t:
                    st[i], st[i | t] = st[i | t], st[i]
        elif op == 'cz':
            both = (1 << g[1]) | (1 << g[2])
            for i in range(dim):
                if i & both == both:
                    st[i] = -st[i]
        elif op == 'swap':
            a, b = 1 << g[1], 1 << g[2]
            for i in range(dim):
                if i & a and not i & b:
                    j = (i ^ a) | b
                    st[i], st[j] = st[j], st[i]
    return [[round(v.real, 6) + 0.0, round(v.imag, 6) + 0.0] for v in st]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression: bell pair', [2, [['h', 0], ['cx', 0, 1]]], [[0.707107, 0.0], [0.0, 0.0], [0.0, 0.0], [0.707107, 0.0]]], ['regression: ghz three qubits', [3, [['h', 0], ['cx', 0, 1], ['cx', 1, 2]]], [[0.707107, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.707107, 0.0]]], ['regression: cx with control on high qubit', [2, [['x', 1], ['cx', 1, 0]]], [[0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [1.0, 0.0]]], ['control: empty circuit on two qubits', [2, []], [[1.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['control: swap moves excitation', [3, [['x', 0], ['swap', 0, 2]]], [[0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [1.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['control: y on ground state', [1, [['y', 0]]], [[0.0, 0.0], [0.0, 1.0]]], ['control: y after x', [1, [['x', 0], ['y', 0]]], [[0.0, -1.0], [0.0, 0.0]]]], [['regression: random circuit 6', [2, [['cz', 0, 1], ['cz', 0, 1], ['z', 1], ['sdg', 0], ['x', 0], ['x', 1], ['cx', 0, 1]]], [[0.0, 0.0], [1.0, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['regression: random circuit 7', [2, [['s', 0], ['cz', 1, 0], ['x', 1], ['cx', 1, 0], ['swap', 1, 0]]], [[0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [1.0, 0.0]]], ['regression: random circuit 29', [2, [['h', 1], ['sdg', 0], ['cx', 1, 0], ['z', 1], ['h', 1], ['t', 0], ['s', 1]]], [[0.5, 0.0], [-0.353553, -0.353553], [0.0, 0.5], [-0.353553, 0.353553]]], ['control: t after h', [1, [['h', 0], ['t', 0]]], [[0.707107, 0.0], [0.5, 0.5]]], ['control: sdg after h', [2, [['h', 1], ['sdg', 1]]], [[0.707107, 0.0], [0.0, 0.0], [0.0, -0.707107], [0.0, 0.0]]], ['control: h on excited qubit', [1, [['x', 0], ['h', 0]]], [[0.707107, 0.0], [-0.707107, 0.0]]], ['control: single x on qubit 0 of three', [3, [['x', 0]]], [[0.0, 0.0], [1.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]]], [['regression: random circuit 12', [3, [['sdg', 2], ['h', 2], ['h', 1], ['s', 0], ['z', 0], ['cx', 0, 1]]], [[0.5, 0.0], [0.0, 0.0], [0.5, 0.0], [0.0, 0.0], [0.5, 0.0], [0.0, 0.0], [0.5, 0.0], [0.0, 0.0]]], ['regression: random circuit 21', [3, [['cz', 2, 0], ['s', 0], ['cx', 1, 0], ['y', 2], ['sdg', 0], ['sdg', 2], ['cx', 0, 2]]], [[0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [1.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['regression: random circuit 39', [3, [['swap', 0, 2], ['cx', 2, 1], ['y', 2], ['z', 2], ['cx', 0, 1], ['sdg', 0], ['cx', 2, 0]]], [[0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, -1.0], [0.0, 0.0], [0.0, 0.0]]], ['control: random circuit 0', [3, [['swap', 2, 1], ['cx', 2, 0], ['z', 2], ['y', 1], ['cx', 0, 2], ['s', 1], ['swap', 1, 0]]], [[0.0, 0.0], [-1.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['control: random circuit 1', [3, [['cx', 1, 2], ['cz', 2, 1]]], [[1.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['control: random circuit 2', [3, [['z', 0], ['sdg', 1], ['cx', 1, 0], ['cz', 0, 1], ['cx', 2, 0], ['y', 0], ['z', 2]]], [[0.0, 0.0], [0.0, 1.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['control: random circuit 3', [2, [['x', 1], ['s', 1], ['x', 0], ['h', 0], ['s', 1], ['h', 1]]], [[-0.5, 0.0], [0.5, 0.0], [0.5, 0.0], [-0.5, 0.0]]]], [['regression: random circuit 29', [2, [['h', 1], ['sdg', 0], ['cx', 1, 0], ['z', 1], ['h', 1], ['t', 0], ['s', 1]]], [[0.5, 0.0], [-0.353553, -0.353553], [0.0, 0.5], [-0.353553, 0.353553]]], ['regression: random circuit 38', [2, [['sdg', 0], ['x', 0], ['cx', 0, 1], ['z', 1]]], [[0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [-1.0, 0.0]]], ['regression: cx with control on high qubit', [2, [['x', 1], ['cx', 1, 0]]], [[0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [1.0, 0.0]]], ['control: random circuit 4', [2, [['cx', 0, 1], ['cz', 0, 1], ['h', 1], ['x', 1], ['y', 0], ['swap', 0, 1]]], [[0.0, 0.0], [0.0, 0.0], [0.0, 0.707107], [0.0, 0.707107]]], ['control: random circuit 5', [2, [['cx', 1, 0], ['cx', 0, 1], ['t', 1], ['h', 1]]], [[0.707107, 0.0], [0.0, 0.0], [0.707107, 0.0], [0.0, 0.0]]], ['control: random circuit 8', [1, [['s', 0], ['h', 0], ['s', 0]]], [[0.707107, 0.0], [0.0, 0.707107]]], ['control: random circuit 9', [1, [['z', 0], ['t', 0], ['z', 0], ['h', 0]]], [[0.707107, 0.0], [0.707107, 0.0]]]], [['regression: bell pair', [2, [['h', 0], ['cx', 0, 1]]], [[0.707107, 0.0], [0.0, 0.0], [0.0, 0.0], [0.707107, 0.0]]], ['regression: ghz three qubits', [3, [['h', 0], ['cx', 0, 1], ['cx', 1, 2]]], [[0.707107, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.707107, 0.0]]], ['regression: random circuit 29', [2, [['h', 1], ['sdg', 0], ['cx', 1, 0], ['z', 1], ['h', 1], ['t', 0], ['s', 1]]], [[0.5, 0.0], [-0.353553, -0.353553], [0.0, 0.5], [-0.353553, 0.353553]]], ['control: random circuit 11', [2, [['s', 0], ['h', 0]]], [[0.707107, 0.0], [0.707107, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['control: random circuit 13', [2, [['sdg', 0], ['cz', 0, 1], ['swap', 0, 1], ['cx', 1, 0]]], [[1.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]], ['control: random circuit 14', [2, [['z', 0], ['swap', 0, 1], ['x', 1], ['t', 0]]], [[0.0, 0.0], [0.0, 0.0], [1.0, 0.0], [0.0, 0.0]]], ['control: random circuit 15', [2, [['cx', 1, 0], ['z', 0], ['cz', 1, 0], ['h', 1], ['h', 0], ['y', 1], ['h', 1]]], [[0.0, 0.0], [0.0, 0.0], [0.0, -0.707107], [0.0, -0.707107]]]]]
for label, args, expected in fixtures[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 Bell-pair circuit with CNOT(0,1) leaves the state as |+>|0> amplitudes on the wrong basis states whenever the control is not in superposition symmetrically.

Input [n, gates]; start in |0...0>, apply gates h,x,y,z,s,sdg,t (["g", q]) and cx,cz,swap (["g", a, b]) with qubit 0 as the least significant bit of the basis index; return the statevector as [re, im] pairs rounded to 6 decimals.

split: open-access