FA-90426 / Garbage collector invariants / Open access

Cheney copy: exactly filling to-space reported as overflow · case 01

A heap whose survivors fit to-space exactly fails with out-of-memory.

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

ROOT CAUSE

The limit comparison uses >=, rejecting a copy that ends precisely at the limit.

VERIFIED REPAIR

Fail only when the aligned copy would end beyond the limit.

Unsuccessful approach: Checking the raw size lets an aligned copy overrun the limit.

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):
            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 fixture	Actual	Expected	Outcome
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	`['out-of-memory', 3]`	`{'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	`['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 / 2daedeb5b8fe6d977c594743b67b81c02c634028bdc623bffbc789ba5fc28464

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 + 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)

Boundary fixture	Actual	Expected	Outcome
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	`{'free': 16, 'layout': [[0, 1, []]], 'roots': [0]}`	`['out-of-memory', 0]`	Failed
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 / 8839dd61e087574ba13ebbbe342e4db03657f64bf18e33ac0fffb1177f75bc70

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 fixture	Actual	Expected	Outcome
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.509611+00:00.

Case digest / 73ab7505ea7c7d510b3ce0776e17a8c01546ab5a81a4aa5213e43a4042d8ea6a