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

N = 1
observations = []
def solve(events):
    objs = {}
    freed = []
    dealloc = []
    out = []
    def release(o):
        if o is None:
            return
        b = objs[o]
        b['rc'] -= 1
        if b['rc'] == 0:
            freed.append(o)
            kids, b['fields'] = b['fields'], []
            if b['weak'] == 0:
                dealloc.append(o)
                del objs[o]
            for c in kids:
                release(c)
    try:
        for ev in events:
            op = ev[0]
            if op == 'new':
                objs[ev[1]] = {'rc': 1, 'weak': 0, 'fields': [None] * ev[2]}
            elif op == 'drop':
                release(ev[1])
            elif op == 'store':
                _, src, field, dst = ev
                old = objs[src]['fields'][field]
                release(old)
                if dst is not None:
                    objs[dst]['rc'] += 1
                objs[src]['fields'][field] = dst
            elif op == 'weak':
                objs[ev[1]]['weak'] += 1
            elif op == 'unweak':
                b = objs[ev[1]]
                b['weak'] -= 1
                if b['weak'] == 0 and b['rc'] == 0:
                    dealloc.append(ev[1])
                    del objs[ev[1]]
            else:
                b = objs[ev[1]]
                if b['rc'] > 0:
                    b['rc'] += 1
                    out.append(True)
                else:
                    out.append(False)
    except (KeyError, IndexError):
        out.append('use-after-free')
    return {'out': out, 'freed': freed, 'dealloc': dealloc,
            'rc': {str(k): [v['rc'], v['weak']] for k, v in sorted(objs.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: overwrite with a child of the old value',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 12, 0, 13],
     ['drop', 13],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 13]],),
   {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 12],
     ['upgrade', 12]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 11, 2],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['store', 11, 1, 12],
     ['drop', 12],
     ['drop', 11]],),
   {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 11, 0], ['weak', 11], ['drop', 11], ['upgrade', 11], ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['weak', 11],
     ['drop', 11],
     ['upgrade', 11],
     ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 11, 0], ['weak', 11], ['unweak', 11], ['upgrade', 11], ['drop', 11], ['drop', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 11, 0, 12],
     ['store', 12, 0, 13],
     ['drop', 12],
     ['drop', 13],
     ['drop', 11]],),
   {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 22, 0, 23],
     ['drop', 23],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 23]],),
   {'dealloc': [22], 'freed': [22], 'out': [], 'rc': {'21': [1, 0], '23': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 22],
     ['upgrade', 22]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'21': [1, 0], '22': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 21, 2],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['store', 21, 1, 22],
     ['drop', 22],
     ['drop', 21]],),
   {'dealloc': [21, 22], 'freed': [21, 22], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 21, 0], ['weak', 21], ['drop', 21], ['upgrade', 21], ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['weak', 21],
     ['drop', 21],
     ['upgrade', 21],
     ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {'22': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 21, 0], ['weak', 21], ['unweak', 21], ['upgrade', 21], ['drop', 21], ['drop', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 21, 0, 22],
     ['store', 22, 0, 23],
     ['drop', 22],
     ['drop', 23],
     ['drop', 21]],),
   {'dealloc': [21, 22, 23], 'freed': [21, 22, 23], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 32, 0, 33],
     ['drop', 33],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 33]],),
   {'dealloc': [32], 'freed': [32], 'out': [], 'rc': {'31': [1, 0], '33': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 32],
     ['upgrade', 32]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'31': [1, 0], '32': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 31, 2],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['store', 31, 1, 32],
     ['drop', 32],
     ['drop', 31]],),
   {'dealloc': [31, 32], 'freed': [31, 32], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 31, 0], ['weak', 31], ['drop', 31], ['upgrade', 31], ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['weak', 31],
     ['drop', 31],
     ['upgrade', 31],
     ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {'32': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 31, 0], ['weak', 31], ['unweak', 31], ['upgrade', 31], ['drop', 31], ['drop', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 31, 0, 32],
     ['store', 32, 0, 33],
     ['drop', 32],
     ['drop', 33],
     ['drop', 31]],),
   {'dealloc': [31, 32, 33], 'freed': [31, 32, 33], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 42, 0, 43],
     ['drop', 43],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 43]],),
   {'dealloc': [42], 'freed': [42], 'out': [], 'rc': {'41': [1, 0], '43': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 42],
     ['upgrade', 42]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'41': [1, 0], '42': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 41, 2],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['store', 41, 1, 42],
     ['drop', 42],
     ['drop', 41]],),
   {'dealloc': [41, 42], 'freed': [41, 42], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 41, 0], ['weak', 41], ['drop', 41], ['upgrade', 41], ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['weak', 41],
     ['drop', 41],
     ['upgrade', 41],
     ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {'42': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 41, 0], ['weak', 41], ['unweak', 41], ['upgrade', 41], ['drop', 41], ['drop', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 41, 0, 42],
     ['store', 42, 0, 43],
     ['drop', 42],
     ['drop', 43],
     ['drop', 41]],),
   {'dealloc': [41, 42, 43], 'freed': [41, 42, 43], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 52, 0, 53],
     ['drop', 53],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 53]],),
   {'dealloc': [52], 'freed': [52], 'out': [], 'rc': {'51': [1, 0], '53': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 52],
     ['upgrade', 52]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'51': [1, 0], '52': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 51, 2],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['store', 51, 1, 52],
     ['drop', 52],
     ['drop', 51]],),
   {'dealloc': [51, 52], 'freed': [51, 52], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 51, 0], ['weak', 51], ['drop', 51], ['upgrade', 51], ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['weak', 51],
     ['drop', 51],
     ['upgrade', 51],
     ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {'52': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 51, 0], ['weak', 51], ['unweak', 51], ['upgrade', 51], ['drop', 51], ['drop', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 51, 0, 52],
     ['store', 52, 0, 53],
     ['drop', 52],
     ['drop', 53],
     ['drop', 51]],),
   {'dealloc': [51, 52, 53], 'freed': [51, 52, 53], 'out': [], 'rc': {}})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(events):
    objs = {}
    freed = []
    dealloc = []
    out = []
    def release(o):
        if o is None:
            return
        b = objs[o]
        b['rc'] -= 1
        if b['rc'] == 0:
            freed.append(o)
            kids, b['fields'] = b['fields'], []
            if b['weak'] == 0:
                dealloc.append(o)
                del objs[o]
            for c in kids:
                release(c)
    try:
        for ev in events:
            op = ev[0]
            if op == 'new':
                objs[ev[1]] = {'rc': 1, 'weak': 0, 'fields': [None] * ev[2]}
            elif op == 'drop':
                release(ev[1])
            elif op == 'store':
                _, src, field, dst = ev
                old = objs[src]['fields'][field]
                if old is not dst:
                    release(old)
                    if dst is not None:
                        objs[dst]['rc'] += 1
                objs[src]['fields'][field] = dst
            elif op == 'weak':
                objs[ev[1]]['weak'] += 1
            elif op == 'unweak':
                b = objs[ev[1]]
                b['weak'] -= 1
                if b['weak'] == 0 and b['rc'] == 0:
                    dealloc.append(ev[1])
                    del objs[ev[1]]
            else:
                b = objs[ev[1]]
                if b['rc'] > 0:
                    b['rc'] += 1
                    out.append(True)
                else:
                    out.append(False)
    except (KeyError, IndexError):
        out.append('use-after-free')
    return {'out': out, 'freed': freed, 'dealloc': dealloc,
            'rc': {str(k): [v['rc'], v['weak']] for k, v in sorted(objs.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: overwrite with a child of the old value',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 12, 0, 13],
     ['drop', 13],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 13]],),
   {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 12],
     ['upgrade', 12]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 11, 2],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['store', 11, 1, 12],
     ['drop', 12],
     ['drop', 11]],),
   {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 11, 0], ['weak', 11], ['drop', 11], ['upgrade', 11], ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['weak', 11],
     ['drop', 11],
     ['upgrade', 11],
     ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 11, 0], ['weak', 11], ['unweak', 11], ['upgrade', 11], ['drop', 11], ['drop', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 11, 0, 12],
     ['store', 12, 0, 13],
     ['drop', 12],
     ['drop', 13],
     ['drop', 11]],),
   {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 22, 0, 23],
     ['drop', 23],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 23]],),
   {'dealloc': [22], 'freed': [22], 'out': [], 'rc': {'21': [1, 0], '23': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 22],
     ['upgrade', 22]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'21': [1, 0], '22': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 21, 2],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['store', 21, 1, 22],
     ['drop', 22],
     ['drop', 21]],),
   {'dealloc': [21, 22], 'freed': [21, 22], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 21, 0], ['weak', 21], ['drop', 21], ['upgrade', 21], ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['weak', 21],
     ['drop', 21],
     ['upgrade', 21],
     ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {'22': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 21, 0], ['weak', 21], ['unweak', 21], ['upgrade', 21], ['drop', 21], ['drop', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 21, 0, 22],
     ['store', 22, 0, 23],
     ['drop', 22],
     ['drop', 23],
     ['drop', 21]],),
   {'dealloc': [21, 22, 23], 'freed': [21, 22, 23], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 32, 0, 33],
     ['drop', 33],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 33]],),
   {'dealloc': [32], 'freed': [32], 'out': [], 'rc': {'31': [1, 0], '33': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 32],
     ['upgrade', 32]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'31': [1, 0], '32': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 31, 2],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['store', 31, 1, 32],
     ['drop', 32],
     ['drop', 31]],),
   {'dealloc': [31, 32], 'freed': [31, 32], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 31, 0], ['weak', 31], ['drop', 31], ['upgrade', 31], ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['weak', 31],
     ['drop', 31],
     ['upgrade', 31],
     ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {'32': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 31, 0], ['weak', 31], ['unweak', 31], ['upgrade', 31], ['drop', 31], ['drop', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 31, 0, 32],
     ['store', 32, 0, 33],
     ['drop', 32],
     ['drop', 33],
     ['drop', 31]],),
   {'dealloc': [31, 32, 33], 'freed': [31, 32, 33], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 42, 0, 43],
     ['drop', 43],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 43]],),
   {'dealloc': [42], 'freed': [42], 'out': [], 'rc': {'41': [1, 0], '43': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 42],
     ['upgrade', 42]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'41': [1, 0], '42': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 41, 2],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['store', 41, 1, 42],
     ['drop', 42],
     ['drop', 41]],),
   {'dealloc': [41, 42], 'freed': [41, 42], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 41, 0], ['weak', 41], ['drop', 41], ['upgrade', 41], ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['weak', 41],
     ['drop', 41],
     ['upgrade', 41],
     ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {'42': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 41, 0], ['weak', 41], ['unweak', 41], ['upgrade', 41], ['drop', 41], ['drop', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 41, 0, 42],
     ['store', 42, 0, 43],
     ['drop', 42],
     ['drop', 43],
     ['drop', 41]],),
   {'dealloc': [41, 42, 43], 'freed': [41, 42, 43], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 52, 0, 53],
     ['drop', 53],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 53]],),
   {'dealloc': [52], 'freed': [52], 'out': [], 'rc': {'51': [1, 0], '53': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 52],
     ['upgrade', 52]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'51': [1, 0], '52': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 51, 2],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['store', 51, 1, 52],
     ['drop', 52],
     ['drop', 51]],),
   {'dealloc': [51, 52], 'freed': [51, 52], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 51, 0], ['weak', 51], ['drop', 51], ['upgrade', 51], ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['weak', 51],
     ['drop', 51],
     ['upgrade', 51],
     ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {'52': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 51, 0], ['weak', 51], ['unweak', 51], ['upgrade', 51], ['drop', 51], ['drop', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 51, 0, 52],
     ['store', 52, 0, 53],
     ['drop', 52],
     ['drop', 53],
     ['drop', 51]],),
   {'dealloc': [51, 52, 53], 'freed': [51, 52, 53], 'out': [], 'rc': {}})]]
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:
Self-assignment or storing a child of the old value frees the object being stored.

Objects carry a strong count and a weak count. new id k: strong 1 (the creating reference), k null fields. drop id: release one strong reference. store src i dst: retain dst, then write, then release the old value. When the strong count reaches 0 the object is destroyed (recorded in freed, its fields released recursively in field order) and, if no weak references remain, its control block is deallocated too; unweak deallocates a destroyed object's block when the last weak reference goes. upgrade id succeeds (and adds a strong reference) only while the strong count is positive. Touching a deallocated block reports "use-after-free".

split: open-access


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

N = 1
observations = []
def solve(events):
    objs = {}
    freed = []
    dealloc = []
    out = []
    def release(o):
        if o is None:
            return
        b = objs[o]
        b['rc'] -= 1
        if b['rc'] == 0:
            freed.append(o)
            kids, b['fields'] = b['fields'], []
            if b['weak'] == 0:
                dealloc.append(o)
                del objs[o]
            del kids
    try:
        for ev in events:
            op = ev[0]
            if op == 'new':
                objs[ev[1]] = {'rc': 1, 'weak': 0, 'fields': [None] * ev[2]}
            elif op == 'drop':
                release(ev[1])
            elif op == 'store':
                _, src, field, dst = ev
                if dst is not None:
                    objs[dst]['rc'] += 1
                old = objs[src]['fields'][field]
                objs[src]['fields'][field] = dst
                release(old)
            elif op == 'weak':
                objs[ev[1]]['weak'] += 1
            elif op == 'unweak':
                b = objs[ev[1]]
                b['weak'] -= 1
                if b['weak'] == 0 and b['rc'] == 0:
                    dealloc.append(ev[1])
                    del objs[ev[1]]
            else:
                b = objs[ev[1]]
                if b['rc'] > 0:
                    b['rc'] += 1
                    out.append(True)
                else:
                    out.append(False)
    except (KeyError, IndexError):
        out.append('use-after-free')
    return {'out': out, 'freed': freed, 'dealloc': dealloc,
            'rc': {str(k): [v['rc'], v['weak']] for k, v in sorted(objs.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: overwrite with a child of the old value',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 12, 0, 13],
     ['drop', 13],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 13]],),
   {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 12],
     ['upgrade', 12]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 11, 2],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['store', 11, 1, 12],
     ['drop', 12],
     ['drop', 11]],),
   {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 11, 0], ['weak', 11], ['drop', 11], ['upgrade', 11], ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['weak', 11],
     ['drop', 11],
     ['upgrade', 11],
     ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 11, 0], ['weak', 11], ['unweak', 11], ['upgrade', 11], ['drop', 11], ['drop', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 11, 0, 12],
     ['store', 12, 0, 13],
     ['drop', 12],
     ['drop', 13],
     ['drop', 11]],),
   {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 22, 0, 23],
     ['drop', 23],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 23]],),
   {'dealloc': [22], 'freed': [22], 'out': [], 'rc': {'21': [1, 0], '23': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 22],
     ['upgrade', 22]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'21': [1, 0], '22': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 21, 2],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['store', 21, 1, 22],
     ['drop', 22],
     ['drop', 21]],),
   {'dealloc': [21, 22], 'freed': [21, 22], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 21, 0], ['weak', 21], ['drop', 21], ['upgrade', 21], ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['weak', 21],
     ['drop', 21],
     ['upgrade', 21],
     ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {'22': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 21, 0], ['weak', 21], ['unweak', 21], ['upgrade', 21], ['drop', 21], ['drop', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 21, 0, 22],
     ['store', 22, 0, 23],
     ['drop', 22],
     ['drop', 23],
     ['drop', 21]],),
   {'dealloc': [21, 22, 23], 'freed': [21, 22, 23], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 32, 0, 33],
     ['drop', 33],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 33]],),
   {'dealloc': [32], 'freed': [32], 'out': [], 'rc': {'31': [1, 0], '33': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 32],
     ['upgrade', 32]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'31': [1, 0], '32': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 31, 2],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['store', 31, 1, 32],
     ['drop', 32],
     ['drop', 31]],),
   {'dealloc': [31, 32], 'freed': [31, 32], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 31, 0], ['weak', 31], ['drop', 31], ['upgrade', 31], ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['weak', 31],
     ['drop', 31],
     ['upgrade', 31],
     ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {'32': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 31, 0], ['weak', 31], ['unweak', 31], ['upgrade', 31], ['drop', 31], ['drop', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 31, 0, 32],
     ['store', 32, 0, 33],
     ['drop', 32],
     ['drop', 33],
     ['drop', 31]],),
   {'dealloc': [31, 32, 33], 'freed': [31, 32, 33], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 42, 0, 43],
     ['drop', 43],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 43]],),
   {'dealloc': [42], 'freed': [42], 'out': [], 'rc': {'41': [1, 0], '43': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 42],
     ['upgrade', 42]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'41': [1, 0], '42': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 41, 2],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['store', 41, 1, 42],
     ['drop', 42],
     ['drop', 41]],),
   {'dealloc': [41, 42], 'freed': [41, 42], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 41, 0], ['weak', 41], ['drop', 41], ['upgrade', 41], ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['weak', 41],
     ['drop', 41],
     ['upgrade', 41],
     ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {'42': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 41, 0], ['weak', 41], ['unweak', 41], ['upgrade', 41], ['drop', 41], ['drop', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 41, 0, 42],
     ['store', 42, 0, 43],
     ['drop', 42],
     ['drop', 43],
     ['drop', 41]],),
   {'dealloc': [41, 42, 43], 'freed': [41, 42, 43], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 52, 0, 53],
     ['drop', 53],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 53]],),
   {'dealloc': [52], 'freed': [52], 'out': [], 'rc': {'51': [1, 0], '53': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 52],
     ['upgrade', 52]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'51': [1, 0], '52': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 51, 2],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['store', 51, 1, 52],
     ['drop', 52],
     ['drop', 51]],),
   {'dealloc': [51, 52], 'freed': [51, 52], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 51, 0], ['weak', 51], ['drop', 51], ['upgrade', 51], ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['weak', 51],
     ['drop', 51],
     ['upgrade', 51],
     ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {'52': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 51, 0], ['weak', 51], ['unweak', 51], ['upgrade', 51], ['drop', 51], ['drop', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 51, 0, 52],
     ['store', 52, 0, 53],
     ['drop', 52],
     ['drop', 53],
     ['drop', 51]],),
   {'dealloc': [51, 52, 53], 'freed': [51, 52, 53], 'out': [], 'rc': {}})]]
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(events):
    objs = {}
    freed = []
    dealloc = []
    out = []
    def release(o):
        if o is None:
            return
        b = objs[o]
        b['rc'] -= 1
        if b['rc'] == 0:
            freed.append(o)
            kids, b['fields'] = b['fields'], []
            if b['weak'] == 0:
                dealloc.append(o)
                del objs[o]
            for c in set(kids):
                release(c)
    try:
        for ev in events:
            op = ev[0]
            if op == 'new':
                objs[ev[1]] = {'rc': 1, 'weak': 0, 'fields': [None] * ev[2]}
            elif op == 'drop':
                release(ev[1])
            elif op == 'store':
                _, src, field, dst = ev
                if dst is not None:
                    objs[dst]['rc'] += 1
                old = objs[src]['fields'][field]
                objs[src]['fields'][field] = dst
                release(old)
            elif op == 'weak':
                objs[ev[1]]['weak'] += 1
            elif op == 'unweak':
                b = objs[ev[1]]
                b['weak'] -= 1
                if b['weak'] == 0 and b['rc'] == 0:
                    dealloc.append(ev[1])
                    del objs[ev[1]]
            else:
                b = objs[ev[1]]
                if b['rc'] > 0:
                    b['rc'] += 1
                    out.append(True)
                else:
                    out.append(False)
    except (KeyError, IndexError):
        out.append('use-after-free')
    return {'out': out, 'freed': freed, 'dealloc': dealloc,
            'rc': {str(k): [v['rc'], v['weak']] for k, v in sorted(objs.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: overwrite with a child of the old value',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 12, 0, 13],
     ['drop', 13],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 13]],),
   {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 12],
     ['upgrade', 12]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 11, 2],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['store', 11, 1, 12],
     ['drop', 12],
     ['drop', 11]],),
   {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 11, 0], ['weak', 11], ['drop', 11], ['upgrade', 11], ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['weak', 11],
     ['drop', 11],
     ['upgrade', 11],
     ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 11, 0], ['weak', 11], ['unweak', 11], ['upgrade', 11], ['drop', 11], ['drop', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 11, 0, 12],
     ['store', 12, 0, 13],
     ['drop', 12],
     ['drop', 13],
     ['drop', 11]],),
   {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 22, 0, 23],
     ['drop', 23],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 23]],),
   {'dealloc': [22], 'freed': [22], 'out': [], 'rc': {'21': [1, 0], '23': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 22],
     ['upgrade', 22]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'21': [1, 0], '22': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 21, 2],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['store', 21, 1, 22],
     ['drop', 22],
     ['drop', 21]],),
   {'dealloc': [21, 22], 'freed': [21, 22], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 21, 0], ['weak', 21], ['drop', 21], ['upgrade', 21], ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['weak', 21],
     ['drop', 21],
     ['upgrade', 21],
     ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {'22': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 21, 0], ['weak', 21], ['unweak', 21], ['upgrade', 21], ['drop', 21], ['drop', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 21, 0, 22],
     ['store', 22, 0, 23],
     ['drop', 22],
     ['drop', 23],
     ['drop', 21]],),
   {'dealloc': [21, 22, 23], 'freed': [21, 22, 23], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 32, 0, 33],
     ['drop', 33],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 33]],),
   {'dealloc': [32], 'freed': [32], 'out': [], 'rc': {'31': [1, 0], '33': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 32],
     ['upgrade', 32]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'31': [1, 0], '32': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 31, 2],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['store', 31, 1, 32],
     ['drop', 32],
     ['drop', 31]],),
   {'dealloc': [31, 32], 'freed': [31, 32], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 31, 0], ['weak', 31], ['drop', 31], ['upgrade', 31], ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['weak', 31],
     ['drop', 31],
     ['upgrade', 31],
     ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {'32': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 31, 0], ['weak', 31], ['unweak', 31], ['upgrade', 31], ['drop', 31], ['drop', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 31, 0, 32],
     ['store', 32, 0, 33],
     ['drop', 32],
     ['drop', 33],
     ['drop', 31]],),
   {'dealloc': [31, 32, 33], 'freed': [31, 32, 33], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 42, 0, 43],
     ['drop', 43],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 43]],),
   {'dealloc': [42], 'freed': [42], 'out': [], 'rc': {'41': [1, 0], '43': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 42],
     ['upgrade', 42]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'41': [1, 0], '42': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 41, 2],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['store', 41, 1, 42],
     ['drop', 42],
     ['drop', 41]],),
   {'dealloc': [41, 42], 'freed': [41, 42], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 41, 0], ['weak', 41], ['drop', 41], ['upgrade', 41], ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['weak', 41],
     ['drop', 41],
     ['upgrade', 41],
     ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {'42': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 41, 0], ['weak', 41], ['unweak', 41], ['upgrade', 41], ['drop', 41], ['drop', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 41, 0, 42],
     ['store', 42, 0, 43],
     ['drop', 42],
     ['drop', 43],
     ['drop', 41]],),
   {'dealloc': [41, 42, 43], 'freed': [41, 42, 43], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 52, 0, 53],
     ['drop', 53],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 53]],),
   {'dealloc': [52], 'freed': [52], 'out': [], 'rc': {'51': [1, 0], '53': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 52],
     ['upgrade', 52]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'51': [1, 0], '52': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 51, 2],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['store', 51, 1, 52],
     ['drop', 52],
     ['drop', 51]],),
   {'dealloc': [51, 52], 'freed': [51, 52], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 51, 0], ['weak', 51], ['drop', 51], ['upgrade', 51], ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['weak', 51],
     ['drop', 51],
     ['upgrade', 51],
     ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {'52': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 51, 0], ['weak', 51], ['unweak', 51], ['upgrade', 51], ['drop', 51], ['drop', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 51, 0, 52],
     ['store', 52, 0, 53],
     ['drop', 52],
     ['drop', 53],
     ['drop', 51]],),
   {'dealloc': [51, 52, 53], 'freed': [51, 52, 53], 'out': [], 'rc': {}})]]
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:
Objects reachable only from a destroyed object keep positive counts forever.

Objects carry a strong count and a weak count. new id k: strong 1 (the creating reference), k null fields. drop id: release one strong reference. store src i dst: retain dst, then write, then release the old value. When the strong count reaches 0 the object is destroyed (recorded in freed, its fields released recursively in field order) and, if no weak references remain, its control block is deallocated too; unweak deallocates a destroyed object's block when the last weak reference goes. upgrade id succeeds (and adds a strong reference) only while the strong count is positive. Touching a deallocated block reports "use-after-free".

split: open-access


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

N = 1
observations = []
def solve(events):
    objs = {}
    freed = []
    dealloc = []
    out = []
    def release(o):
        if o is None:
            return
        b = objs[o]
        b['rc'] -= 1
        if b['rc'] == 0:
            freed.append(o)
            kids, b['fields'] = b['fields'], []
            if b['weak'] == 0:
                dealloc.append(o)
                del objs[o]
            for c in kids:
                release(c)
    try:
        for ev in events:
            op = ev[0]
            if op == 'new':
                objs[ev[1]] = {'rc': 1, 'weak': 0, 'fields': [None] * ev[2]}
            elif op == 'drop':
                release(ev[1])
            elif op == 'store':
                _, src, field, dst = ev
                if dst is not None:
                    objs[dst]['rc'] += 1
                old = objs[src]['fields'][field]
                objs[src]['fields'][field] = dst
                release(old)
            elif op == 'weak':
                objs[ev[1]]['weak'] += 1
            elif op == 'unweak':
                b = objs[ev[1]]
                b['weak'] -= 1
                if b['weak'] == 0 and b['rc'] == 0:
                    dealloc.append(ev[1])
                    del objs[ev[1]]
            else:
                b = objs[ev[1]]
                if ev[1] in objs:
                    b['rc'] += 1
                    out.append(True)
                else:
                    out.append(False)
    except (KeyError, IndexError):
        out.append('use-after-free')
    return {'out': out, 'freed': freed, 'dealloc': dealloc,
            'rc': {str(k): [v['rc'], v['weak']] for k, v in sorted(objs.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: overwrite with a child of the old value',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 12, 0, 13],
     ['drop', 13],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 13]],),
   {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 12],
     ['upgrade', 12]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 11, 2],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['store', 11, 1, 12],
     ['drop', 12],
     ['drop', 11]],),
   {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 11, 0], ['weak', 11], ['drop', 11], ['upgrade', 11], ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['weak', 11],
     ['drop', 11],
     ['upgrade', 11],
     ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 11, 0], ['weak', 11], ['unweak', 11], ['upgrade', 11], ['drop', 11], ['drop', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 11, 0, 12],
     ['store', 12, 0, 13],
     ['drop', 12],
     ['drop', 13],
     ['drop', 11]],),
   {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 22, 0, 23],
     ['drop', 23],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 23]],),
   {'dealloc': [22], 'freed': [22], 'out': [], 'rc': {'21': [1, 0], '23': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 22],
     ['upgrade', 22]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'21': [1, 0], '22': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 21, 2],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['store', 21, 1, 22],
     ['drop', 22],
     ['drop', 21]],),
   {'dealloc': [21, 22], 'freed': [21, 22], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 21, 0], ['weak', 21], ['drop', 21], ['upgrade', 21], ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['weak', 21],
     ['drop', 21],
     ['upgrade', 21],
     ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {'22': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 21, 0], ['weak', 21], ['unweak', 21], ['upgrade', 21], ['drop', 21], ['drop', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 21, 0, 22],
     ['store', 22, 0, 23],
     ['drop', 22],
     ['drop', 23],
     ['drop', 21]],),
   {'dealloc': [21, 22, 23], 'freed': [21, 22, 23], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 32, 0, 33],
     ['drop', 33],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 33]],),
   {'dealloc': [32], 'freed': [32], 'out': [], 'rc': {'31': [1, 0], '33': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 32],
     ['upgrade', 32]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'31': [1, 0], '32': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 31, 2],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['store', 31, 1, 32],
     ['drop', 32],
     ['drop', 31]],),
   {'dealloc': [31, 32], 'freed': [31, 32], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 31, 0], ['weak', 31], ['drop', 31], ['upgrade', 31], ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['weak', 31],
     ['drop', 31],
     ['upgrade', 31],
     ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {'32': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 31, 0], ['weak', 31], ['unweak', 31], ['upgrade', 31], ['drop', 31], ['drop', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 31, 0, 32],
     ['store', 32, 0, 33],
     ['drop', 32],
     ['drop', 33],
     ['drop', 31]],),
   {'dealloc': [31, 32, 33], 'freed': [31, 32, 33], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 42, 0, 43],
     ['drop', 43],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 43]],),
   {'dealloc': [42], 'freed': [42], 'out': [], 'rc': {'41': [1, 0], '43': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 42],
     ['upgrade', 42]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'41': [1, 0], '42': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 41, 2],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['store', 41, 1, 42],
     ['drop', 42],
     ['drop', 41]],),
   {'dealloc': [41, 42], 'freed': [41, 42], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 41, 0], ['weak', 41], ['drop', 41], ['upgrade', 41], ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['weak', 41],
     ['drop', 41],
     ['upgrade', 41],
     ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {'42': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 41, 0], ['weak', 41], ['unweak', 41], ['upgrade', 41], ['drop', 41], ['drop', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 41, 0, 42],
     ['store', 42, 0, 43],
     ['drop', 42],
     ['drop', 43],
     ['drop', 41]],),
   {'dealloc': [41, 42, 43], 'freed': [41, 42, 43], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 52, 0, 53],
     ['drop', 53],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 53]],),
   {'dealloc': [52], 'freed': [52], 'out': [], 'rc': {'51': [1, 0], '53': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 52],
     ['upgrade', 52]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'51': [1, 0], '52': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 51, 2],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['store', 51, 1, 52],
     ['drop', 52],
     ['drop', 51]],),
   {'dealloc': [51, 52], 'freed': [51, 52], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 51, 0], ['weak', 51], ['drop', 51], ['upgrade', 51], ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['weak', 51],
     ['drop', 51],
     ['upgrade', 51],
     ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {'52': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 51, 0], ['weak', 51], ['unweak', 51], ['upgrade', 51], ['drop', 51], ['drop', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 51, 0, 52],
     ['store', 52, 0, 53],
     ['drop', 52],
     ['drop', 53],
     ['drop', 51]],),
   {'dealloc': [51, 52, 53], 'freed': [51, 52, 53], 'out': [], 'rc': {}})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(events):
    objs = {}
    freed = []
    dealloc = []
    out = []
    def release(o):
        if o is None:
            return
        b = objs[o]
        b['rc'] -= 1
        if b['rc'] == 0:
            freed.append(o)
            kids, b['fields'] = b['fields'], []
            if b['weak'] == 0:
                dealloc.append(o)
                del objs[o]
            for c in kids:
                release(c)
    try:
        for ev in events:
            op = ev[0]
            if op == 'new':
                objs[ev[1]] = {'rc': 1, 'weak': 0, 'fields': [None] * ev[2]}
            elif op == 'drop':
                release(ev[1])
            elif op == 'store':
                _, src, field, dst = ev
                if dst is not None:
                    objs[dst]['rc'] += 1
                old = objs[src]['fields'][field]
                objs[src]['fields'][field] = dst
                release(old)
            elif op == 'weak':
                objs[ev[1]]['weak'] += 1
            elif op == 'unweak':
                b = objs[ev[1]]
                b['weak'] -= 1
                if b['weak'] == 0 and b['rc'] == 0:
                    dealloc.append(ev[1])
                    del objs[ev[1]]
            else:
                b = objs[ev[1]]
                if b['rc'] >= 0:
                    b['rc'] += 1
                    out.append(True)
                else:
                    out.append(False)
    except (KeyError, IndexError):
        out.append('use-after-free')
    return {'out': out, 'freed': freed, 'dealloc': dealloc,
            'rc': {str(k): [v['rc'], v['weak']] for k, v in sorted(objs.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: overwrite with a child of the old value',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 12, 0, 13],
     ['drop', 13],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 13]],),
   {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 12],
     ['upgrade', 12]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 11, 2],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['store', 11, 1, 12],
     ['drop', 12],
     ['drop', 11]],),
   {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 11, 0], ['weak', 11], ['drop', 11], ['upgrade', 11], ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['weak', 11],
     ['drop', 11],
     ['upgrade', 11],
     ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 11, 0], ['weak', 11], ['unweak', 11], ['upgrade', 11], ['drop', 11], ['drop', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 11, 0, 12],
     ['store', 12, 0, 13],
     ['drop', 12],
     ['drop', 13],
     ['drop', 11]],),
   {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 22, 0, 23],
     ['drop', 23],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 23]],),
   {'dealloc': [22], 'freed': [22], 'out': [], 'rc': {'21': [1, 0], '23': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 22],
     ['upgrade', 22]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'21': [1, 0], '22': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 21, 2],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['store', 21, 1, 22],
     ['drop', 22],
     ['drop', 21]],),
   {'dealloc': [21, 22], 'freed': [21, 22], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 21, 0], ['weak', 21], ['drop', 21], ['upgrade', 21], ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['weak', 21],
     ['drop', 21],
     ['upgrade', 21],
     ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {'22': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 21, 0], ['weak', 21], ['unweak', 21], ['upgrade', 21], ['drop', 21], ['drop', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 21, 0, 22],
     ['store', 22, 0, 23],
     ['drop', 22],
     ['drop', 23],
     ['drop', 21]],),
   {'dealloc': [21, 22, 23], 'freed': [21, 22, 23], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 32, 0, 33],
     ['drop', 33],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 33]],),
   {'dealloc': [32], 'freed': [32], 'out': [], 'rc': {'31': [1, 0], '33': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 32],
     ['upgrade', 32]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'31': [1, 0], '32': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 31, 2],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['store', 31, 1, 32],
     ['drop', 32],
     ['drop', 31]],),
   {'dealloc': [31, 32], 'freed': [31, 32], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 31, 0], ['weak', 31], ['drop', 31], ['upgrade', 31], ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['weak', 31],
     ['drop', 31],
     ['upgrade', 31],
     ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {'32': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 31, 0], ['weak', 31], ['unweak', 31], ['upgrade', 31], ['drop', 31], ['drop', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 31, 0, 32],
     ['store', 32, 0, 33],
     ['drop', 32],
     ['drop', 33],
     ['drop', 31]],),
   {'dealloc': [31, 32, 33], 'freed': [31, 32, 33], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 42, 0, 43],
     ['drop', 43],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 43]],),
   {'dealloc': [42], 'freed': [42], 'out': [], 'rc': {'41': [1, 0], '43': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 42],
     ['upgrade', 42]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'41': [1, 0], '42': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 41, 2],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['store', 41, 1, 42],
     ['drop', 42],
     ['drop', 41]],),
   {'dealloc': [41, 42], 'freed': [41, 42], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 41, 0], ['weak', 41], ['drop', 41], ['upgrade', 41], ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['weak', 41],
     ['drop', 41],
     ['upgrade', 41],
     ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {'42': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 41, 0], ['weak', 41], ['unweak', 41], ['upgrade', 41], ['drop', 41], ['drop', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 41, 0, 42],
     ['store', 42, 0, 43],
     ['drop', 42],
     ['drop', 43],
     ['drop', 41]],),
   {'dealloc': [41, 42, 43], 'freed': [41, 42, 43], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 52, 0, 53],
     ['drop', 53],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 53]],),
   {'dealloc': [52], 'freed': [52], 'out': [], 'rc': {'51': [1, 0], '53': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 52],
     ['upgrade', 52]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'51': [1, 0], '52': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 51, 2],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['store', 51, 1, 52],
     ['drop', 52],
     ['drop', 51]],),
   {'dealloc': [51, 52], 'freed': [51, 52], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 51, 0], ['weak', 51], ['drop', 51], ['upgrade', 51], ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['weak', 51],
     ['drop', 51],
     ['upgrade', 51],
     ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {'52': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 51, 0], ['weak', 51], ['unweak', 51], ['upgrade', 51], ['drop', 51], ['drop', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 51, 0, 52],
     ['store', 52, 0, 53],
     ['drop', 52],
     ['drop', 53],
     ['drop', 51]],),
   {'dealloc': [51, 52, 53], 'freed': [51, 52, 53], 'out': [], 'rc': {}})]]
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:
upgrade() on an object whose last strong reference is gone succeeds and returns a destroyed object.

Objects carry a strong count and a weak count. new id k: strong 1 (the creating reference), k null fields. drop id: release one strong reference. store src i dst: retain dst, then write, then release the old value. When the strong count reaches 0 the object is destroyed (recorded in freed, its fields released recursively in field order) and, if no weak references remain, its control block is deallocated too; unweak deallocates a destroyed object's block when the last weak reference goes. upgrade id succeeds (and adds a strong reference) only while the strong count is positive. Touching a deallocated block reports "use-after-free".

split: open-access


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

N = 1
observations = []
def solve(events):
    objs = {}
    freed = []
    dealloc = []
    out = []
    def release(o):
        if o is None:
            return
        b = objs[o]
        b['rc'] -= 1
        if b['rc'] == 0:
            freed.append(o)
            kids, b['fields'] = b['fields'], []
            if b['rc'] == 0:
                dealloc.append(o)
                del objs[o]
            for c in kids:
                release(c)
    try:
        for ev in events:
            op = ev[0]
            if op == 'new':
                objs[ev[1]] = {'rc': 1, 'weak': 0, 'fields': [None] * ev[2]}
            elif op == 'drop':
                release(ev[1])
            elif op == 'store':
                _, src, field, dst = ev
                if dst is not None:
                    objs[dst]['rc'] += 1
                old = objs[src]['fields'][field]
                objs[src]['fields'][field] = dst
                release(old)
            elif op == 'weak':
                objs[ev[1]]['weak'] += 1
            elif op == 'unweak':
                b = objs[ev[1]]
                b['weak'] -= 1
                if b['weak'] == 0 and b['rc'] == 0:
                    dealloc.append(ev[1])
                    del objs[ev[1]]
            else:
                b = objs[ev[1]]
                if b['rc'] > 0:
                    b['rc'] += 1
                    out.append(True)
                else:
                    out.append(False)
    except (KeyError, IndexError):
        out.append('use-after-free')
    return {'out': out, 'freed': freed, 'dealloc': dealloc,
            'rc': {str(k): [v['rc'], v['weak']] for k, v in sorted(objs.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: overwrite with a child of the old value',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 12, 0, 13],
     ['drop', 13],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 13]],),
   {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 12],
     ['upgrade', 12]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 11, 2],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['store', 11, 1, 12],
     ['drop', 12],
     ['drop', 11]],),
   {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 11, 0], ['weak', 11], ['drop', 11], ['upgrade', 11], ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['weak', 11],
     ['drop', 11],
     ['upgrade', 11],
     ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 11, 0], ['weak', 11], ['unweak', 11], ['upgrade', 11], ['drop', 11], ['drop', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 11, 0, 12],
     ['store', 12, 0, 13],
     ['drop', 12],
     ['drop', 13],
     ['drop', 11]],),
   {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 22, 0, 23],
     ['drop', 23],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 23]],),
   {'dealloc': [22], 'freed': [22], 'out': [], 'rc': {'21': [1, 0], '23': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 22],
     ['upgrade', 22]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'21': [1, 0], '22': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 21, 2],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['store', 21, 1, 22],
     ['drop', 22],
     ['drop', 21]],),
   {'dealloc': [21, 22], 'freed': [21, 22], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 21, 0], ['weak', 21], ['drop', 21], ['upgrade', 21], ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['weak', 21],
     ['drop', 21],
     ['upgrade', 21],
     ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {'22': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 21, 0], ['weak', 21], ['unweak', 21], ['upgrade', 21], ['drop', 21], ['drop', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 21, 0, 22],
     ['store', 22, 0, 23],
     ['drop', 22],
     ['drop', 23],
     ['drop', 21]],),
   {'dealloc': [21, 22, 23], 'freed': [21, 22, 23], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 32, 0, 33],
     ['drop', 33],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 33]],),
   {'dealloc': [32], 'freed': [32], 'out': [], 'rc': {'31': [1, 0], '33': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 32],
     ['upgrade', 32]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'31': [1, 0], '32': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 31, 2],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['store', 31, 1, 32],
     ['drop', 32],
     ['drop', 31]],),
   {'dealloc': [31, 32], 'freed': [31, 32], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 31, 0], ['weak', 31], ['drop', 31], ['upgrade', 31], ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['weak', 31],
     ['drop', 31],
     ['upgrade', 31],
     ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {'32': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 31, 0], ['weak', 31], ['unweak', 31], ['upgrade', 31], ['drop', 31], ['drop', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 31, 0, 32],
     ['store', 32, 0, 33],
     ['drop', 32],
     ['drop', 33],
     ['drop', 31]],),
   {'dealloc': [31, 32, 33], 'freed': [31, 32, 33], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 42, 0, 43],
     ['drop', 43],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 43]],),
   {'dealloc': [42], 'freed': [42], 'out': [], 'rc': {'41': [1, 0], '43': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 42],
     ['upgrade', 42]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'41': [1, 0], '42': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 41, 2],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['store', 41, 1, 42],
     ['drop', 42],
     ['drop', 41]],),
   {'dealloc': [41, 42], 'freed': [41, 42], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 41, 0], ['weak', 41], ['drop', 41], ['upgrade', 41], ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['weak', 41],
     ['drop', 41],
     ['upgrade', 41],
     ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {'42': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 41, 0], ['weak', 41], ['unweak', 41], ['upgrade', 41], ['drop', 41], ['drop', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 41, 0, 42],
     ['store', 42, 0, 43],
     ['drop', 42],
     ['drop', 43],
     ['drop', 41]],),
   {'dealloc': [41, 42, 43], 'freed': [41, 42, 43], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 52, 0, 53],
     ['drop', 53],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 53]],),
   {'dealloc': [52], 'freed': [52], 'out': [], 'rc': {'51': [1, 0], '53': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 52],
     ['upgrade', 52]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'51': [1, 0], '52': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 51, 2],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['store', 51, 1, 52],
     ['drop', 52],
     ['drop', 51]],),
   {'dealloc': [51, 52], 'freed': [51, 52], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 51, 0], ['weak', 51], ['drop', 51], ['upgrade', 51], ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['weak', 51],
     ['drop', 51],
     ['upgrade', 51],
     ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {'52': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 51, 0], ['weak', 51], ['unweak', 51], ['upgrade', 51], ['drop', 51], ['drop', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 51, 0, 52],
     ['store', 52, 0, 53],
     ['drop', 52],
     ['drop', 53],
     ['drop', 51]],),
   {'dealloc': [51, 52, 53], 'freed': [51, 52, 53], 'out': [], 'rc': {}})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(events):
    objs = {}
    freed = []
    dealloc = []
    out = []
    def release(o):
        if o is None:
            return
        b = objs[o]
        b['rc'] -= 1
        if b['rc'] == 0:
            freed.append(o)
            kids, b['fields'] = b['fields'], []
            if b['weak'] <= 1:
                dealloc.append(o)
                del objs[o]
            for c in kids:
                release(c)
    try:
        for ev in events:
            op = ev[0]
            if op == 'new':
                objs[ev[1]] = {'rc': 1, 'weak': 0, 'fields': [None] * ev[2]}
            elif op == 'drop':
                release(ev[1])
            elif op == 'store':
                _, src, field, dst = ev
                if dst is not None:
                    objs[dst]['rc'] += 1
                old = objs[src]['fields'][field]
                objs[src]['fields'][field] = dst
                release(old)
            elif op == 'weak':
                objs[ev[1]]['weak'] += 1
            elif op == 'unweak':
                b = objs[ev[1]]
                b['weak'] -= 1
                if b['weak'] == 0 and b['rc'] == 0:
                    dealloc.append(ev[1])
                    del objs[ev[1]]
            else:
                b = objs[ev[1]]
                if b['rc'] > 0:
                    b['rc'] += 1
                    out.append(True)
                else:
                    out.append(False)
    except (KeyError, IndexError):
        out.append('use-after-free')
    return {'out': out, 'freed': freed, 'dealloc': dealloc,
            'rc': {str(k): [v['rc'], v['weak']] for k, v in sorted(objs.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: overwrite with a child of the old value',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 12, 0, 13],
     ['drop', 13],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 13]],),
   {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 12],
     ['upgrade', 12]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 11, 2],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['store', 11, 1, 12],
     ['drop', 12],
     ['drop', 11]],),
   {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 11, 0], ['weak', 11], ['drop', 11], ['upgrade', 11], ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['weak', 11],
     ['drop', 11],
     ['upgrade', 11],
     ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 11, 0], ['weak', 11], ['unweak', 11], ['upgrade', 11], ['drop', 11], ['drop', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 11, 0, 12],
     ['store', 12, 0, 13],
     ['drop', 12],
     ['drop', 13],
     ['drop', 11]],),
   {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 22, 0, 23],
     ['drop', 23],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 23]],),
   {'dealloc': [22], 'freed': [22], 'out': [], 'rc': {'21': [1, 0], '23': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 22],
     ['upgrade', 22]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'21': [1, 0], '22': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 21, 2],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['store', 21, 1, 22],
     ['drop', 22],
     ['drop', 21]],),
   {'dealloc': [21, 22], 'freed': [21, 22], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 21, 0], ['weak', 21], ['drop', 21], ['upgrade', 21], ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['weak', 21],
     ['drop', 21],
     ['upgrade', 21],
     ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {'22': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 21, 0], ['weak', 21], ['unweak', 21], ['upgrade', 21], ['drop', 21], ['drop', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 21, 0, 22],
     ['store', 22, 0, 23],
     ['drop', 22],
     ['drop', 23],
     ['drop', 21]],),
   {'dealloc': [21, 22, 23], 'freed': [21, 22, 23], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 32, 0, 33],
     ['drop', 33],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 33]],),
   {'dealloc': [32], 'freed': [32], 'out': [], 'rc': {'31': [1, 0], '33': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 32],
     ['upgrade', 32]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'31': [1, 0], '32': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 31, 2],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['store', 31, 1, 32],
     ['drop', 32],
     ['drop', 31]],),
   {'dealloc': [31, 32], 'freed': [31, 32], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 31, 0], ['weak', 31], ['drop', 31], ['upgrade', 31], ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['weak', 31],
     ['drop', 31],
     ['upgrade', 31],
     ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {'32': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 31, 0], ['weak', 31], ['unweak', 31], ['upgrade', 31], ['drop', 31], ['drop', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 31, 0, 32],
     ['store', 32, 0, 33],
     ['drop', 32],
     ['drop', 33],
     ['drop', 31]],),
   {'dealloc': [31, 32, 33], 'freed': [31, 32, 33], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 42, 0, 43],
     ['drop', 43],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 43]],),
   {'dealloc': [42], 'freed': [42], 'out': [], 'rc': {'41': [1, 0], '43': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 42],
     ['upgrade', 42]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'41': [1, 0], '42': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 41, 2],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['store', 41, 1, 42],
     ['drop', 42],
     ['drop', 41]],),
   {'dealloc': [41, 42], 'freed': [41, 42], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 41, 0], ['weak', 41], ['drop', 41], ['upgrade', 41], ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['weak', 41],
     ['drop', 41],
     ['upgrade', 41],
     ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {'42': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 41, 0], ['weak', 41], ['unweak', 41], ['upgrade', 41], ['drop', 41], ['drop', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 41, 0, 42],
     ['store', 42, 0, 43],
     ['drop', 42],
     ['drop', 43],
     ['drop', 41]],),
   {'dealloc': [41, 42, 43], 'freed': [41, 42, 43], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 52, 0, 53],
     ['drop', 53],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 53]],),
   {'dealloc': [52], 'freed': [52], 'out': [], 'rc': {'51': [1, 0], '53': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 52],
     ['upgrade', 52]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'51': [1, 0], '52': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 51, 2],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['store', 51, 1, 52],
     ['drop', 52],
     ['drop', 51]],),
   {'dealloc': [51, 52], 'freed': [51, 52], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 51, 0], ['weak', 51], ['drop', 51], ['upgrade', 51], ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['weak', 51],
     ['drop', 51],
     ['upgrade', 51],
     ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {'52': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 51, 0], ['weak', 51], ['unweak', 51], ['upgrade', 51], ['drop', 51], ['drop', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 51, 0, 52],
     ['store', 52, 0, 53],
     ['drop', 52],
     ['drop', 53],
     ['drop', 51]],),
   {'dealloc': [51, 52, 53], 'freed': [51, 52, 53], 'out': [], 'rc': {}})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
A later upgrade or unweak through a surviving weak reference touches freed memory.

Objects carry a strong count and a weak count. new id k: strong 1 (the creating reference), k null fields. drop id: release one strong reference. store src i dst: retain dst, then write, then release the old value. When the strong count reaches 0 the object is destroyed (recorded in freed, its fields released recursively in field order) and, if no weak references remain, its control block is deallocated too; unweak deallocates a destroyed object's block when the last weak reference goes. upgrade id succeeds (and adds a strong reference) only while the strong count is positive. Touching a deallocated block reports "use-after-free".

split: open-access