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

N = 1
observations = []
def solve(heap, roots, base, limit):
    forward = {}
    tospace = []
    free = base
    def copy(a):
        nonlocal free
        if a is None:
            return None
        need = (heap[a]['size'] + 7) // 8 * 8
        if free + need > limit:
            raise MemoryError()
        forward[a] = free
        tospace.append([free, a, list(heap[a]['fields'])])
        free += need
        return forward[a]
    try:
        new_roots = [copy(r) for r in roots]
        scan = 0
        while scan < len(tospace):
            entry = tospace[scan]
            entry[2] = [copy(f) for f in entry[2]]
            scan += 1
    except MemoryError:
        return ['out-of-memory', len(tospace)]
    return {'roots': new_roots, 'layout': tospace, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 8}},
    [1],
    0,
    500),
   {'free': 32, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 16}},
    [1],
    0,
    500),
   {'free': 40, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 9}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 24}},
    [1],
    0,
    500),
   {'free': 48, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 32}},
    [1],
    0,
    500),
   {'free': 56, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 100, [1016, 1040]], [1016, 200, [1040]], [1040, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 200, [1024]], [1024, 300, [1032, None]], [1032, 100, [1000, 1024]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1072),
   {'free': 1072,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1048]],
               [1048, 300, [1056, None]],
               [1056, 100, [1024, 1048]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1071),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 40}},
    [1],
    0,
    500),
   {'free': 64, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(heap, roots, base, limit):
    forward = {}
    tospace = []
    free = base
    def copy(a):
        nonlocal free
        if a is None:
            return None
        if a in forward and a in roots:
            return forward[a]
        need = (heap[a]['size'] + 7) // 8 * 8
        if free + need > limit:
            raise MemoryError()
        forward[a] = free
        tospace.append([free, a, list(heap[a]['fields'])])
        free += need
        return forward[a]
    try:
        new_roots = [copy(r) for r in roots]
        scan = 0
        while scan < len(tospace):
            entry = tospace[scan]
            entry[2] = [copy(f) for f in entry[2]]
            scan += 1
    except MemoryError:
        return ['out-of-memory', len(tospace)]
    return {'roots': new_roots, 'layout': tospace, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 8}},
    [1],
    0,
    500),
   {'free': 32, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 16}},
    [1],
    0,
    500),
   {'free': 40, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 9}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 24}},
    [1],
    0,
    500),
   {'free': 48, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 32}},
    [1],
    0,
    500),
   {'free': 56, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 100, [1016, 1040]], [1016, 200, [1040]], [1040, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 200, [1024]], [1024, 300, [1032, None]], [1032, 100, [1000, 1024]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1072),
   {'free': 1072,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1048]],
               [1048, 300, [1056, None]],
               [1056, 100, [1024, 1048]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1071),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 40}},
    [1],
    0,
    500),
   {'free': 64, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})]]
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:
Shared objects are duplicated and cycles copy until to-space is exhausted.

Breadth-first semispace copying. heap maps from-space address -> {size, fields}. Roots are copied in order, then a scan pointer walks to-space copying each referenced object exactly once (forwarding addresses are reused) and rewriting fields to to-space addresses. Copies are bump-allocated from base with sizes rounded up to 8 bytes; if a copy would end beyond limit, return ["out-of-memory", copies so far]. Return new roots, the to-space layout [new, old, fields] and the final free pointer.

split: open-access


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

N = 1
observations = []
def solve(heap, roots, base, limit):
    forward = {}
    tospace = []
    free = base
    def copy(a):
        nonlocal free
        if a is None:
            return None
        if a in forward:
            return forward[a]
        need = heap[a]['size']
        if free + need > limit:
            raise MemoryError()
        forward[a] = free
        tospace.append([free, a, list(heap[a]['fields'])])
        free += need
        return forward[a]
    try:
        new_roots = [copy(r) for r in roots]
        scan = 0
        while scan < len(tospace):
            entry = tospace[scan]
            entry[2] = [copy(f) for f in entry[2]]
            scan += 1
    except MemoryError:
        return ['out-of-memory', len(tospace)]
    return {'roots': new_roots, 'layout': tospace, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 8}},
    [1],
    0,
    500),
   {'free': 32, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 16}},
    [1],
    0,
    500),
   {'free': 40, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 9}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 24}},
    [1],
    0,
    500),
   {'free': 48, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 32}},
    [1],
    0,
    500),
   {'free': 56, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 100, [1016, 1040]], [1016, 200, [1040]], [1040, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 200, [1024]], [1024, 300, [1032, None]], [1032, 100, [1000, 1024]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1072),
   {'free': 1072,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1048]],
               [1048, 300, [1056, None]],
               [1056, 100, [1024, 1048]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1071),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 40}},
    [1],
    0,
    500),
   {'free': 64, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

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

N = 1
observations = []
def solve(heap, roots, base, limit):
    forward = {}
    tospace = []
    free = base
    def copy(a):
        nonlocal free
        if a is None:
            return None
        if a in forward:
            return forward[a]
        need = heap[a]['size'] // 8 * 8 + 8
        if free + need > limit:
            raise MemoryError()
        forward[a] = free
        tospace.append([free, a, list(heap[a]['fields'])])
        free += need
        return forward[a]
    try:
        new_roots = [copy(r) for r in roots]
        scan = 0
        while scan < len(tospace):
            entry = tospace[scan]
            entry[2] = [copy(f) for f in entry[2]]
            scan += 1
    except MemoryError:
        return ['out-of-memory', len(tospace)]
    return {'roots': new_roots, 'layout': tospace, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 8}},
    [1],
    0,
    500),
   {'free': 32, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 16}},
    [1],
    0,
    500),
   {'free': 40, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 9}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 24}},
    [1],
    0,
    500),
   {'free': 48, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 32}},
    [1],
    0,
    500),
   {'free': 56, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 100, [1016, 1040]], [1016, 200, [1040]], [1040, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 200, [1024]], [1024, 300, [1032, None]], [1032, 100, [1000, 1024]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1072),
   {'free': 1072,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1048]],
               [1048, 300, [1056, None]],
               [1056, 100, [1024, 1048]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1071),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 40}},
    [1],
    0,
    500),
   {'free': 64, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})]]
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 with sizes that are not multiples of 8 leave later copies misaligned.

Breadth-first semispace copying. heap maps from-space address -> {size, fields}. Roots are copied in order, then a scan pointer walks to-space copying each referenced object exactly once (forwarding addresses are reused) and rewriting fields to to-space addresses. Copies are bump-allocated from base with sizes rounded up to 8 bytes; if a copy would end beyond limit, return ["out-of-memory", copies so far]. Return new roots, the to-space layout [new, old, fields] and the final free pointer.

split: open-access


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

N = 1
observations = []
def solve(heap, roots, base, limit):
    forward = {}
    tospace = []
    free = base
    def copy(a):
        nonlocal free
        if a is None:
            return None
        if a in forward:
            return forward[a]
        need = (heap[a]['size'] + 7) // 8 * 8
        if free + need >= limit:
            raise MemoryError()
        forward[a] = free
        tospace.append([free, a, list(heap[a]['fields'])])
        free += need
        return forward[a]
    try:
        new_roots = [copy(r) for r in roots]
        scan = 0
        while scan < len(tospace):
            entry = tospace[scan]
            entry[2] = [copy(f) for f in entry[2]]
            scan += 1
    except MemoryError:
        return ['out-of-memory', len(tospace)]
    return {'roots': new_roots, 'layout': tospace, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 8}},
    [1],
    0,
    500),
   {'free': 32, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 16}},
    [1],
    0,
    500),
   {'free': 40, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 9}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 24}},
    [1],
    0,
    500),
   {'free': 48, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 32}},
    [1],
    0,
    500),
   {'free': 56, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 100, [1016, 1040]], [1016, 200, [1040]], [1040, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 200, [1024]], [1024, 300, [1032, None]], [1032, 100, [1000, 1024]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1072),
   {'free': 1072,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1048]],
               [1048, 300, [1056, None]],
               [1056, 100, [1024, 1048]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1071),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 40}},
    [1],
    0,
    500),
   {'free': 64, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(heap, roots, base, limit):
    forward = {}
    tospace = []
    free = base
    def copy(a):
        nonlocal free
        if a is None:
            return None
        if a in forward:
            return forward[a]
        need = (heap[a]['size'] + 7) // 8 * 8
        if free + heap[a]['size'] > limit:
            raise MemoryError()
        forward[a] = free
        tospace.append([free, a, list(heap[a]['fields'])])
        free += need
        return forward[a]
    try:
        new_roots = [copy(r) for r in roots]
        scan = 0
        while scan < len(tospace):
            entry = tospace[scan]
            entry[2] = [copy(f) for f in entry[2]]
            scan += 1
    except MemoryError:
        return ['out-of-memory', len(tospace)]
    return {'roots': new_roots, 'layout': tospace, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 8}},
    [1],
    0,
    500),
   {'free': 32, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 16}},
    [1],
    0,
    500),
   {'free': 40, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 9}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 24}},
    [1],
    0,
    500),
   {'free': 48, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 32}},
    [1],
    0,
    500),
   {'free': 56, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 100, [1016, 1040]], [1016, 200, [1040]], [1040, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 200, [1024]], [1024, 300, [1032, None]], [1032, 100, [1000, 1024]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1072),
   {'free': 1072,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1048]],
               [1048, 300, [1056, None]],
               [1056, 100, [1024, 1048]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1071),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 40}},
    [1],
    0,
    500),
   {'free': 64, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})]]
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 heap whose survivors fit to-space exactly fails with out-of-memory.

Breadth-first semispace copying. heap maps from-space address -> {size, fields}. Roots are copied in order, then a scan pointer walks to-space copying each referenced object exactly once (forwarding addresses are reused) and rewriting fields to to-space addresses. Copies are bump-allocated from base with sizes rounded up to 8 bytes; if a copy would end beyond limit, return ["out-of-memory", copies so far]. Return new roots, the to-space layout [new, old, fields] and the final free pointer.

split: open-access