FAILURE MAP
← Case archive

FA-90421 / Garbage collector invariants / Open access

Cheney copy: copies bump-allocated at their raw size · case 01

Objects with sizes that are not multiples of 8 leave later copies misaligned.

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

ROOT CAUSE

The bump size is the raw object size without rounding.

VERIFIED REPAIR

Round each object size up to the next multiple of 8.

Unsuccessful approach: Always adding 8 after rounding down wastes a word for sizes that are already aligned.

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']
        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': 1037, 'layout': [[1000, 100, [1016, 1029]], [1016, 200, [1029]], [1029, 300, [1000, 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': 1037, 'layout': [[1000, 200, [1013]], [1013, 300, [1021, None]], [1021, 100, [1000, 1013]]], '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': 1037, '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]}Failed
to-space exactly full{'free': 1061, 'layout': [[1000, 400, [1024]], [1024, 200, [1037]], [1037, 300, [1045, None]], [1045, 100, [1024, 1037]]], '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': 1061, 'layout': [[1000, 400, [1024]], [1024, 200, [1037]], [1037, 300, [1045, None]], [1045, 100, [1024, 1037]]], 'roots': [1000]}['out-of-memory', 3]Failed
aligned size fits but raw size would too{'free': 10, '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 / 009ec229550473b953d876c74aa285b7e4f23028cd57031be2cd9ffa573e847f

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'] // 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)
Boundary fixtureActualExpectedOutcome
regression: shared object and cycle copied once{'free': 1056, 'layout': [[1000, 100, [1024, 1040]], [1024, 200, [1040]], [1040, 300, [1000, 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': 1056, 'layout': [[1000, 200, [1016]], [1016, 300, [1032, None]], [1032, 100, [1000, 1016]]], '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': 1056, 'layout': [[1000, 300, [1016, None]], [1016, 100, [1040, 1000]], [1040, 200, [1000]]], '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['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', 2]['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': 64, 'layout': [[0, 1, [16]], [16, 2, [32]], [32, 3, [48]], [48, 4, []]], 'roots': [0]}{'free': 32, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]}Failed

SHA-256 / c9627ce24cec56cd40bbf7739b1aca709ce435d5a2c2acfc14c5b3db43fa9dcb

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.476463+00:00.

Case digest / 016b7e723dcf8f74a6004c1a16ecc3752769a105cbf898b3f38ad4a532687f27