FAILURE MAP
← Case archive

FA-90431 / Garbage collector invariants / Open access

Cheney copy: scanning stops before the last copied object · case 01

Fields of the most recently copied object keep pointing into from-space.

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

ROOT CAUSE

The scan loop stops one object before the free pointer.

VERIFIED REPAIR

Scan until the scan index catches up with the number of copied objects.

Unsuccessful approach: Iterating over the initial to-space size never scans objects copied during the scan.

Case contract

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.

Why this case matters

Copying collectors rely on forwarding pointers and the scan/free invariant to preserve sharing.

1 / The failure

Exit 1
"""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) - 1:
            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)
Boundary fixtureActualExpectedOutcome
regression: shared object and cycle copied once{'free': 1016, 'layout': [[1000, 100, [200, 300]]], 'roots': [1000]}{'free': 1040, 'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]], 'roots': [1000]}Failed
odd sizes are rounded up to 8 bytes{'free': 1016, 'layout': [[1000, 200, [300]]], 'roots': [1000]}{'free': 1040, 'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]], 'roots': [1000]}Failed
two roots to the same object{'free': 1008, 'layout': [[1000, 300, [100, None]]], 'roots': [1000, 1000, None]}{'free': 1040, 'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]], 'roots': [1000, 1000, None]}Failed
to-space exactly full{'free': 1024, 'layout': [[1000, 400, [200]]], 'roots': [1000]}{'free': 1064, 'layout': [[1000, 400, [1024]], [1024, 200, [1040]], [1040, 300, [1048, None]], [1048, 100, [1024, 1040]]], 'roots': [1000]}Failed
to-space one byte short{'free': 1024, 'layout': [[1000, 400, [200]]], 'roots': [1000]}['out-of-memory', 3]Failed
aligned size fits but raw size would too['out-of-memory', 0]['out-of-memory', 0]Passed
last copied object is scanned{'free': 8, 'layout': [[0, 1, [2]]], 'roots': [0]}{'free': 32, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]}Failed

SHA-256 / 82b4a894cf663bcbd1f221ec050afafaaa8c5e26b3d216acc2c3445112e58768

2 / The unsuccessful fix

Exit 1
"""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
        for _ in range(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)
Boundary fixtureActualExpectedOutcome
regression: shared object and cycle copied once{'free': 1040, 'layout': [[1000, 100, [1016, 1032]], [1016, 200, [300]], [1032, 300, [100, None]]], 'roots': [1000]}{'free': 1040, 'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]], 'roots': [1000]}Failed
odd sizes are rounded up to 8 bytes{'free': 1024, 'layout': [[1000, 200, [1016]], [1016, 300, [100, None]]], 'roots': [1000]}{'free': 1040, 'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]], 'roots': [1000]}Failed
two roots to the same object{'free': 1024, 'layout': [[1000, 300, [1008, None]], [1008, 100, [200, 300]]], 'roots': [1000, 1000, None]}{'free': 1040, 'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]], 'roots': [1000, 1000, None]}Failed
to-space exactly full{'free': 1040, 'layout': [[1000, 400, [1024]], [1024, 200, [300]]], 'roots': [1000]}{'free': 1064, 'layout': [[1000, 400, [1024]], [1024, 200, [1040]], [1040, 300, [1048, None]], [1048, 100, [1024, 1040]]], 'roots': [1000]}Failed
to-space one byte short{'free': 1040, 'layout': [[1000, 400, [1024]], [1024, 200, [300]]], 'roots': [1000]}['out-of-memory', 3]Failed
aligned size fits but raw size would too['out-of-memory', 0]['out-of-memory', 0]Passed
last copied object is scanned{'free': 16, 'layout': [[0, 1, [8]], [8, 2, [3]]], 'roots': [0]}{'free': 32, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]}Failed

SHA-256 / 702b04c5ef64bf93eb1b39471987038024ef4f8d48a4ecc216d7f106bda91dbc

3 / The verified repair

Exit 0
"""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)
Boundary fixtureActualExpectedOutcome
regression: shared object and cycle copied once{'free': 1040, 'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]], 'roots': [1000]}{'free': 1040, 'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]], 'roots': [1000]}Passed
odd sizes are rounded up to 8 bytes{'free': 1040, 'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]], 'roots': [1000]}{'free': 1040, 'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]], 'roots': [1000]}Passed
two roots to the same object{'free': 1040, 'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]], 'roots': [1000, 1000, None]}{'free': 1040, 'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]], 'roots': [1000, 1000, None]}Passed
to-space exactly full{'free': 1064, 'layout': [[1000, 400, [1024]], [1024, 200, [1040]], [1040, 300, [1048, None]], [1048, 100, [1024, 1040]]], 'roots': [1000]}{'free': 1064, 'layout': [[1000, 400, [1024]], [1024, 200, [1040]], [1040, 300, [1048, None]], [1048, 100, [1024, 1040]]], 'roots': [1000]}Passed
to-space one byte short['out-of-memory', 3]['out-of-memory', 3]Passed
aligned size fits but raw size would too['out-of-memory', 0]['out-of-memory', 0]Passed
last copied object is scanned{'free': 32, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]}{'free': 32, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]}Passed

SHA-256 / f3a7e5dbccd98381433cd4777f7cac2772a4d918bb2c224b67b5c18f928f1600

Verification & scope

A deterministic, bounded teaching model of one garbage-collector mechanism with stipulated rules; it is not a production collector and claims no conformance to any particular runtime. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:51:26.551123+00:00.

Case digest / 9d44a02902870f181ba3c0a9f7e6d5ad7bf52a7025a143c35b0ed0bf0e0c0f20