{"abstract":"Objects with sizes that are not multiples of 8 leave later copies misaligned.","category":"Garbage collector invariants","checks":7,"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.","contract_signature":"heap, roots, base, limit","evaluation_group":"w2-garbage-collector-invariants-cheney-semispace-copy","failed_approach":"Always adding 8 after rounding down wastes a word for sizes that are already aligned.","family":"w2-garbage-collector-invariants-cheney-semispace-copy-allocation-alignment","id":"FA-90421","implementations":{"attempt":{"sha256":"c9627ce24cec56cd40bbf7739b1aca709ce435d5a2c2acfc14c5b3db43fa9dcb","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(heap, roots, base, limit):\n    forward = {}\n    tospace = []\n    free = base\n    def copy(a):\n        nonlocal free\n        if a is None:\n            return None\n        if a in forward:\n            return forward[a]\n        need = heap[a]['size'] // 8 * 8 + 8\n        if free + need > limit:\n            raise MemoryError()\n        forward[a] = free\n        tospace.append([free, a, list(heap[a]['fields'])])\n        free += need\n        return forward[a]\n    try:\n        new_roots = [copy(r) for r in roots]\n        scan = 0\n        while scan < len(tospace):\n            entry = tospace[scan]\n            entry[2] = [copy(f) for f in entry[2]]\n            scan += 1\n    except MemoryError:\n        return ['out-of-memory', len(tospace)]\n    return {'roots': new_roots, 'layout': tospace, 'free': free}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: shared object and cycle copied once',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 13},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [100],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],\n    'roots': [1000]}),\n  ('odd sizes are rounded up to 8 bytes',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 13},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [200],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],\n    'roots': [1000]}),\n  ('two roots to the same object',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 13},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [300, 300, None],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],\n    'roots': [1000, 1000, None]}),\n  ('to-space exactly full',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 13},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1064),\n   {'free': 1064,\n    'layout': [[1000, 400, [1024]],\n               [1024, 200, [1040]],\n               [1040, 300, [1048, None]],\n               [1048, 100, [1024, 1040]]],\n    'roots': [1000]}),\n  ('to-space one byte short',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 13},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1063),\n   ['out-of-memory', 3]),\n  ('aligned size fits but raw size would too',\n   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),\n   ['out-of-memory', 0]),\n  ('last copied object is scanned',\n   ({1: {'fields': [2], 'size': 8},\n     2: {'fields': [3], 'size': 8},\n     3: {'fields': [4], 'size': 8},\n     4: {'fields': [], 'size': 8}},\n    [1],\n    0,\n    500),\n   {'free': 32, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],\n [('regression: shared object and cycle copied once',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 14},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [100],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],\n    'roots': [1000]}),\n  ('odd sizes are rounded up to 8 bytes',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 14},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [200],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],\n    'roots': [1000]}),\n  ('two roots to the same object',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 14},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [300, 300, None],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],\n    'roots': [1000, 1000, None]}),\n  ('to-space exactly full',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 14},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1064),\n   {'free': 1064,\n    'layout': [[1000, 400, [1024]],\n               [1024, 200, [1040]],\n               [1040, 300, [1048, None]],\n               [1048, 100, [1024, 1040]]],\n    'roots': [1000]}),\n  ('to-space one byte short',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 14},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1063),\n   ['out-of-memory', 3]),\n  ('aligned size fits but raw size would too',\n   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),\n   ['out-of-memory', 0]),\n  ('last copied object is scanned',\n   ({1: {'fields': [2], 'size': 8},\n     2: {'fields': [3], 'size': 8},\n     3: {'fields': [4], 'size': 8},\n     4: {'fields': [], 'size': 16}},\n    [1],\n    0,\n    500),\n   {'free': 40, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],\n [('regression: shared object and cycle copied once',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 15},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [100],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],\n    'roots': [1000]}),\n  ('odd sizes are rounded up to 8 bytes',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 15},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [200],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],\n    'roots': [1000]}),\n  ('two roots to the same object',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 15},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [300, 300, None],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],\n    'roots': [1000, 1000, None]}),\n  ('to-space exactly full',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 15},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1064),\n   {'free': 1064,\n    'layout': [[1000, 400, [1024]],\n               [1024, 200, [1040]],\n               [1040, 300, [1048, None]],\n               [1048, 100, [1024, 1040]]],\n    'roots': [1000]}),\n  ('to-space one byte short',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 15},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1063),\n   ['out-of-memory', 3]),\n  ('aligned size fits but raw size would too',\n   ({1: {'fields': [], 'size': 9}}, [1], 0, 12),\n   ['out-of-memory', 0]),\n  ('last copied object is scanned',\n   ({1: {'fields': [2], 'size': 8},\n     2: {'fields': [3], 'size': 8},\n     3: {'fields': [4], 'size': 8},\n     4: {'fields': [], 'size': 24}},\n    [1],\n    0,\n    500),\n   {'free': 48, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],\n [('regression: shared object and cycle copied once',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 16},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [100],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],\n    'roots': [1000]}),\n  ('odd sizes are rounded up to 8 bytes',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 16},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [200],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],\n    'roots': [1000]}),\n  ('two roots to the same object',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 16},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [300, 300, None],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],\n    'roots': [1000, 1000, None]}),\n  ('to-space exactly full',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 16},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1064),\n   {'free': 1064,\n    'layout': [[1000, 400, [1024]],\n               [1024, 200, [1040]],\n               [1040, 300, [1048, None]],\n               [1048, 100, [1024, 1040]]],\n    'roots': [1000]}),\n  ('to-space one byte short',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 16},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1063),\n   ['out-of-memory', 3]),\n  ('aligned size fits but raw size would too',\n   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),\n   ['out-of-memory', 0]),\n  ('last copied object is scanned',\n   ({1: {'fields': [2], 'size': 8},\n     2: {'fields': [3], 'size': 8},\n     3: {'fields': [4], 'size': 8},\n     4: {'fields': [], 'size': 32}},\n    [1],\n    0,\n    500),\n   {'free': 56, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],\n [('regression: shared object and cycle copied once',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 17},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [100],\n    1000,\n    2000),\n   {'free': 1048,\n    'layout': [[1000, 100, [1016, 1040]], [1016, 200, [1040]], [1040, 300, [1000, None]]],\n    'roots': [1000]}),\n  ('odd sizes are rounded up to 8 bytes',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 17},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [200],\n    1000,\n    2000),\n   {'free': 1048,\n    'layout': [[1000, 200, [1024]], [1024, 300, [1032, None]], [1032, 100, [1000, 1024]]],\n    'roots': [1000]}),\n  ('two roots to the same object',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 17},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [300, 300, None],\n    1000,\n    2000),\n   {'free': 1048,\n    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],\n    'roots': [1000, 1000, None]}),\n  ('to-space exactly full',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 17},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1072),\n   {'free': 1072,\n    'layout': [[1000, 400, [1024]],\n               [1024, 200, [1048]],\n               [1048, 300, [1056, None]],\n               [1056, 100, [1024, 1048]]],\n    'roots': [1000]}),\n  ('to-space one byte short',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 17},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1071),\n   ['out-of-memory', 3]),\n  ('aligned size fits but raw size would too',\n   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),\n   ['out-of-memory', 0]),\n  ('last copied object is scanned',\n   ({1: {'fields': [2], 'size': 8},\n     2: {'fields': [3], 'size': 8},\n     3: {'fields': [4], 'size': 8},\n     4: {'fields': [], 'size': 40}},\n    [1],\n    0,\n    500),\n   {'free': 64, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"009ec229550473b953d876c74aa285b7e4f23028cd57031be2cd9ffa573e847f","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(heap, roots, base, limit):\n    forward = {}\n    tospace = []\n    free = base\n    def copy(a):\n        nonlocal free\n        if a is None:\n            return None\n        if a in forward:\n            return forward[a]\n        need = heap[a]['size']\n        if free + need > limit:\n            raise MemoryError()\n        forward[a] = free\n        tospace.append([free, a, list(heap[a]['fields'])])\n        free += need\n        return forward[a]\n    try:\n        new_roots = [copy(r) for r in roots]\n        scan = 0\n        while scan < len(tospace):\n            entry = tospace[scan]\n            entry[2] = [copy(f) for f in entry[2]]\n            scan += 1\n    except MemoryError:\n        return ['out-of-memory', len(tospace)]\n    return {'roots': new_roots, 'layout': tospace, 'free': free}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: shared object and cycle copied once',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 13},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [100],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],\n    'roots': [1000]}),\n  ('odd sizes are rounded up to 8 bytes',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 13},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [200],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],\n    'roots': [1000]}),\n  ('two roots to the same object',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 13},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [300, 300, None],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],\n    'roots': [1000, 1000, None]}),\n  ('to-space exactly full',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 13},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1064),\n   {'free': 1064,\n    'layout': [[1000, 400, [1024]],\n               [1024, 200, [1040]],\n               [1040, 300, [1048, None]],\n               [1048, 100, [1024, 1040]]],\n    'roots': [1000]}),\n  ('to-space one byte short',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 13},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1063),\n   ['out-of-memory', 3]),\n  ('aligned size fits but raw size would too',\n   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),\n   ['out-of-memory', 0]),\n  ('last copied object is scanned',\n   ({1: {'fields': [2], 'size': 8},\n     2: {'fields': [3], 'size': 8},\n     3: {'fields': [4], 'size': 8},\n     4: {'fields': [], 'size': 8}},\n    [1],\n    0,\n    500),\n   {'free': 32, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],\n [('regression: shared object and cycle copied once',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 14},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [100],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],\n    'roots': [1000]}),\n  ('odd sizes are rounded up to 8 bytes',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 14},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [200],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],\n    'roots': [1000]}),\n  ('two roots to the same object',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 14},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [300, 300, None],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],\n    'roots': [1000, 1000, None]}),\n  ('to-space exactly full',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 14},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1064),\n   {'free': 1064,\n    'layout': [[1000, 400, [1024]],\n               [1024, 200, [1040]],\n               [1040, 300, [1048, None]],\n               [1048, 100, [1024, 1040]]],\n    'roots': [1000]}),\n  ('to-space one byte short',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 14},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1063),\n   ['out-of-memory', 3]),\n  ('aligned size fits but raw size would too',\n   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),\n   ['out-of-memory', 0]),\n  ('last copied object is scanned',\n   ({1: {'fields': [2], 'size': 8},\n     2: {'fields': [3], 'size': 8},\n     3: {'fields': [4], 'size': 8},\n     4: {'fields': [], 'size': 16}},\n    [1],\n    0,\n    500),\n   {'free': 40, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],\n [('regression: shared object and cycle copied once',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 15},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [100],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],\n    'roots': [1000]}),\n  ('odd sizes are rounded up to 8 bytes',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 15},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [200],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],\n    'roots': [1000]}),\n  ('two roots to the same object',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 15},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [300, 300, None],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],\n    'roots': [1000, 1000, None]}),\n  ('to-space exactly full',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 15},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1064),\n   {'free': 1064,\n    'layout': [[1000, 400, [1024]],\n               [1024, 200, [1040]],\n               [1040, 300, [1048, None]],\n               [1048, 100, [1024, 1040]]],\n    'roots': [1000]}),\n  ('to-space one byte short',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 15},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1063),\n   ['out-of-memory', 3]),\n  ('aligned size fits but raw size would too',\n   ({1: {'fields': [], 'size': 9}}, [1], 0, 12),\n   ['out-of-memory', 0]),\n  ('last copied object is scanned',\n   ({1: {'fields': [2], 'size': 8},\n     2: {'fields': [3], 'size': 8},\n     3: {'fields': [4], 'size': 8},\n     4: {'fields': [], 'size': 24}},\n    [1],\n    0,\n    500),\n   {'free': 48, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],\n [('regression: shared object and cycle copied once',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 16},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [100],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],\n    'roots': [1000]}),\n  ('odd sizes are rounded up to 8 bytes',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 16},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [200],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],\n    'roots': [1000]}),\n  ('two roots to the same object',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 16},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [300, 300, None],\n    1000,\n    2000),\n   {'free': 1040,\n    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],\n    'roots': [1000, 1000, None]}),\n  ('to-space exactly full',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 16},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1064),\n   {'free': 1064,\n    'layout': [[1000, 400, [1024]],\n               [1024, 200, [1040]],\n               [1040, 300, [1048, None]],\n               [1048, 100, [1024, 1040]]],\n    'roots': [1000]}),\n  ('to-space one byte short',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 16},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1063),\n   ['out-of-memory', 3]),\n  ('aligned size fits but raw size would too',\n   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),\n   ['out-of-memory', 0]),\n  ('last copied object is scanned',\n   ({1: {'fields': [2], 'size': 8},\n     2: {'fields': [3], 'size': 8},\n     3: {'fields': [4], 'size': 8},\n     4: {'fields': [], 'size': 32}},\n    [1],\n    0,\n    500),\n   {'free': 56, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],\n [('regression: shared object and cycle copied once',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 17},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [100],\n    1000,\n    2000),\n   {'free': 1048,\n    'layout': [[1000, 100, [1016, 1040]], [1016, 200, [1040]], [1040, 300, [1000, None]]],\n    'roots': [1000]}),\n  ('odd sizes are rounded up to 8 bytes',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 17},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [200],\n    1000,\n    2000),\n   {'free': 1048,\n    'layout': [[1000, 200, [1024]], [1024, 300, [1032, None]], [1032, 100, [1000, 1024]]],\n    'roots': [1000]}),\n  ('two roots to the same object',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 17},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [300, 300, None],\n    1000,\n    2000),\n   {'free': 1048,\n    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],\n    'roots': [1000, 1000, None]}),\n  ('to-space exactly full',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 17},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1072),\n   {'free': 1072,\n    'layout': [[1000, 400, [1024]],\n               [1024, 200, [1048]],\n               [1048, 300, [1056, None]],\n               [1056, 100, [1024, 1048]]],\n    'roots': [1000]}),\n  ('to-space one byte short',\n   ({100: {'fields': [200, 300], 'size': 16},\n     200: {'fields': [300], 'size': 17},\n     300: {'fields': [100, None], 'size': 8},\n     400: {'fields': [200], 'size': 24}},\n    [400],\n    1000,\n    1071),\n   ['out-of-memory', 3]),\n  ('aligned size fits but raw size would too',\n   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),\n   ['out-of-memory', 0]),\n  ('last copied object is scanned',\n   ({1: {'fields': [2], 'size': 8},\n     2: {'fields': [3], 'size': 8},\n     3: {'fields': [4], 'size': 8},\n     4: {'fields': [], 'size': 40}},\n    [1],\n    0,\n    500),\n   {'free': 64, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-garbage-collector-invariants-cheney-semispace-copy-allocation-alignment","generated_at":"2026-09-29T14:51:26.551123+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Copying collectors rely on forwarding pointers and the scan/free invariant to preserve sharing.","root_cause":"The bump size is the raw object size without rounding.","sha256":"d21133580db3bd7b5e265102e960ce9cf8fd26a039ad780428f368ac4678a197","title":"Cheney copy: copies bump-allocated at their raw size · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verified":true,"visibility":"public","verification":{"attempt":{"elapsed_ms":41.184,"exit_code":1,"observations":[{"actual":{"free":1056,"layout":[[1000,100,[1024,1040]],[1024,200,[1040]],[1040,300,[1000,null]]],"roots":[1000]},"check":"regression: shared object and cycle copied once","expected":{"free":1040,"layout":[[1000,100,[1016,1032]],[1016,200,[1032]],[1032,300,[1000,null]]],"roots":[1000]},"passed":false},{"actual":{"free":1056,"layout":[[1000,200,[1016]],[1016,300,[1032,null]],[1032,100,[1000,1016]]],"roots":[1000]},"check":"odd sizes are rounded up to 8 bytes","expected":{"free":1040,"layout":[[1000,200,[1016]],[1016,300,[1024,null]],[1024,100,[1000,1016]]],"roots":[1000]},"passed":false},{"actual":{"free":1056,"layout":[[1000,300,[1016,null]],[1016,100,[1040,1000]],[1040,200,[1000]]],"roots":[1000,1000,null]},"check":"two roots to the same object","expected":{"free":1040,"layout":[[1000,300,[1008,null]],[1008,100,[1024,1000]],[1024,200,[1000]]],"roots":[1000,1000,null]},"passed":false},{"actual":["out-of-memory",3],"check":"to-space exactly full","expected":{"free":1064,"layout":[[1000,400,[1024]],[1024,200,[1040]],[1040,300,[1048,null]],[1048,100,[1024,1040]]],"roots":[1000]},"passed":false},{"actual":["out-of-memory",2],"check":"to-space one byte short","expected":["out-of-memory",3],"passed":false},{"actual":["out-of-memory",0],"check":"aligned size fits but raw size would too","expected":["out-of-memory",0],"passed":true},{"actual":{"free":64,"layout":[[0,1,[16]],[16,2,[32]],[32,3,[48]],[48,4,[]]],"roots":[0]},"check":"last copied object is scanned","expected":{"free":32,"layout":[[0,1,[8]],[8,2,[16]],[16,3,[24]],[24,4,[]]],"roots":[0]},"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: shared object and cycle copied once\", \"actual\": {\"roots\": [1000], \"layout\": [[1000, 100, [1024, 1040]], [1024, 200, [1040]], [1040, 300, [1000, null]]], \"free\": 1056}, \"expected\": {\"free\": 1040, \"layout\": [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, null]]], \"roots\": [1000]}, \"passed\": false}, {\"check\": \"odd sizes are rounded up to 8 bytes\", \"actual\": {\"roots\": [1000], \"layout\": [[1000, 200, [1016]], [1016, 300, [1032, null]], [1032, 100, [1000, 1016]]], \"free\": 1056}, \"expected\": {\"free\": 1040, \"layout\": [[1000, 200, [1016]], [1016, 300, [1024, null]], [1024, 100, [1000, 1016]]], \"roots\": [1000]}, \"passed\": false}, {\"check\": \"two roots to the same object\", \"actual\": {\"roots\": [1000, 1000, null], \"layout\": [[1000, 300, [1016, null]], [1016, 100, [1040, 1000]], [1040, 200, [1000]]], \"free\": 1056}, \"expected\": {\"free\": 1040, \"layout\": [[1000, 300, [1008, null]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]], \"roots\": [1000, 1000, null]}, \"passed\": false}, {\"check\": \"to-space exactly full\", \"actual\": [\"out-of-memory\", 3], \"expected\": {\"free\": 1064, \"layout\": [[1000, 400, [1024]], [1024, 200, [1040]], [1040, 300, [1048, null]], [1048, 100, [1024, 1040]]], \"roots\": [1000]}, \"passed\": false}, {\"check\": \"to-space one byte short\", \"actual\": [\"out-of-memory\", 2], \"expected\": [\"out-of-memory\", 3], \"passed\": false}, {\"check\": \"aligned size fits but raw size would too\", \"actual\": [\"out-of-memory\", 0], \"expected\": [\"out-of-memory\", 0], \"passed\": true}, {\"check\": \"last copied object is scanned\", \"actual\": {\"roots\": [0], \"layout\": [[0, 1, [16]], [16, 2, [32]], [32, 3, [48]], [48, 4, []]], \"free\": 64}, \"expected\": {\"free\": 32, \"layout\": [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], \"roots\": [0]}, \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":40.495,"exit_code":1,"observations":[{"actual":{"free":1037,"layout":[[1000,100,[1016,1029]],[1016,200,[1029]],[1029,300,[1000,null]]],"roots":[1000]},"check":"regression: shared object and cycle copied once","expected":{"free":1040,"layout":[[1000,100,[1016,1032]],[1016,200,[1032]],[1032,300,[1000,null]]],"roots":[1000]},"passed":false},{"actual":{"free":1037,"layout":[[1000,200,[1013]],[1013,300,[1021,null]],[1021,100,[1000,1013]]],"roots":[1000]},"check":"odd sizes are rounded up to 8 bytes","expected":{"free":1040,"layout":[[1000,200,[1016]],[1016,300,[1024,null]],[1024,100,[1000,1016]]],"roots":[1000]},"passed":false},{"actual":{"free":1037,"layout":[[1000,300,[1008,null]],[1008,100,[1024,1000]],[1024,200,[1000]]],"roots":[1000,1000,null]},"check":"two roots to the same object","expected":{"free":1040,"layout":[[1000,300,[1008,null]],[1008,100,[1024,1000]],[1024,200,[1000]]],"roots":[1000,1000,null]},"passed":false},{"actual":{"free":1061,"layout":[[1000,400,[1024]],[1024,200,[1037]],[1037,300,[1045,null]],[1045,100,[1024,1037]]],"roots":[1000]},"check":"to-space exactly full","expected":{"free":1064,"layout":[[1000,400,[1024]],[1024,200,[1040]],[1040,300,[1048,null]],[1048,100,[1024,1040]]],"roots":[1000]},"passed":false},{"actual":{"free":1061,"layout":[[1000,400,[1024]],[1024,200,[1037]],[1037,300,[1045,null]],[1045,100,[1024,1037]]],"roots":[1000]},"check":"to-space one byte short","expected":["out-of-memory",3],"passed":false},{"actual":{"free":10,"layout":[[0,1,[]]],"roots":[0]},"check":"aligned size fits but raw size would too","expected":["out-of-memory",0],"passed":false},{"actual":{"free":32,"layout":[[0,1,[8]],[8,2,[16]],[16,3,[24]],[24,4,[]]],"roots":[0]},"check":"last copied object is scanned","expected":{"free":32,"layout":[[0,1,[8]],[8,2,[16]],[16,3,[24]],[24,4,[]]],"roots":[0]},"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: shared object and cycle copied once\", \"actual\": {\"roots\": [1000], \"layout\": [[1000, 100, [1016, 1029]], [1016, 200, [1029]], [1029, 300, [1000, null]]], \"free\": 1037}, \"expected\": {\"free\": 1040, \"layout\": [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, null]]], \"roots\": [1000]}, \"passed\": false}, {\"check\": \"odd sizes are rounded up to 8 bytes\", \"actual\": {\"roots\": [1000], \"layout\": [[1000, 200, [1013]], [1013, 300, [1021, null]], [1021, 100, [1000, 1013]]], \"free\": 1037}, \"expected\": {\"free\": 1040, \"layout\": [[1000, 200, [1016]], [1016, 300, [1024, null]], [1024, 100, [1000, 1016]]], \"roots\": [1000]}, \"passed\": false}, {\"check\": \"two roots to the same object\", \"actual\": {\"roots\": [1000, 1000, null], \"layout\": [[1000, 300, [1008, null]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]], \"free\": 1037}, \"expected\": {\"free\": 1040, \"layout\": [[1000, 300, [1008, null]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]], \"roots\": [1000, 1000, null]}, \"passed\": false}, {\"check\": \"to-space exactly full\", \"actual\": {\"roots\": [1000], \"layout\": [[1000, 400, [1024]], [1024, 200, [1037]], [1037, 300, [1045, null]], [1045, 100, [1024, 1037]]], \"free\": 1061}, \"expected\": {\"free\": 1064, \"layout\": [[1000, 400, [1024]], [1024, 200, [1040]], [1040, 300, [1048, null]], [1048, 100, [1024, 1040]]], \"roots\": [1000]}, \"passed\": false}, {\"check\": \"to-space one byte short\", \"actual\": {\"roots\": [1000], \"layout\": [[1000, 400, [1024]], [1024, 200, [1037]], [1037, 300, [1045, null]], [1045, 100, [1024, 1037]]], \"free\": 1061}, \"expected\": [\"out-of-memory\", 3], \"passed\": false}, {\"check\": \"aligned size fits but raw size would too\", \"actual\": {\"roots\": [0], \"layout\": [[0, 1, []]], \"free\": 10}, \"expected\": [\"out-of-memory\", 0], \"passed\": false}, {\"check\": \"last copied object is scanned\", \"actual\": {\"roots\": [0], \"layout\": [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], \"free\": 32}, \"expected\": {\"free\": 32, \"layout\": [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], \"roots\": [0]}, \"passed\": true}], \"passed\": false}\n"}},"member_only":{"stages":["fixed"],"fields":["implementations.fixed","verification.fixed","harness","repair"],"note":"The verified repair, its recorded checks, the repair description, and the scoring harness are available to members."}}