FAILURE MAP
← Case archive

FA-90446 / Garbage collector invariants / Open access

Sliding compaction: interior pointers snapped to object starts · case 01

Pointers into the middle of objects are redirected to the object headers.

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

ROOT CAUSE

Relocation maps the owning object but drops the pointer's offset.

VERIFIED REPAIR

Add the original offset to the owner's new address.

Unsuccessful approach: Relocating only exact starts leaves interior pointers at their old addresses.

Case contract

Mark-compact with sliding. objs are [start, size, fields] in arbitrary order; pointers (fields and roots) may point anywhere inside an object and belong to the object whose [start, start+size) contains them; a pointer outside every object is ["dangling-pointer", p]. Mark from the roots, assign new addresses to live objects in address order starting at base with no gaps, and relocate every pointer to new start + original offset. Return the new layout [new, old, fields], new roots and the new top.

Why this case matters

Sliding compaction must preserve address order and interior offsets while squeezing out dead space.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, roots, base):
    starts = sorted(o[0] for o in objs)
    info = {o[0]: o for o in objs}
    def owner(p):
        i = bisect.bisect_right(starts, p) - 1
        if i < 0:
            raise KeyError(p)
        s = starts[i]
        if p >= s + info[s][1]:
            raise KeyError(p)
        return s
    try:
        live = set()
        stack = [r for r in roots if r is not None]
        while stack:
            s = owner(stack.pop())
            if s in live:
                continue
            live.add(s)
            stack.extend(f for f in info[s][2] if f is not None)
        fwd = {}
        top = base
        for s in starts:
            if s in live:
                fwd[s] = top
                top += info[s][1]
        def reloc(p):
            if p is None:
                return None
            s = owner(p)
            return fwd[s]
        layout = [[fwd[s], s, [reloc(f) for f in info[s][2]]] for s in starts if s in live]
        new_roots = [reloc(r) for r in roots]
    except KeyError as e:
        return ['dangling-pointer', e.args[0]]
    except IndexError:
        return ['heap-walk-error']
    return {'layout': layout, 'roots': new_roots, 'top': top}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    41),
   {'layout': [[41, 100, [66, None]], [57, 124, [45]], [81, 148, [93]], [93, 160, []]],
    'roots': [41, 81],
    'top': 109}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [152], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [104], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    42),
   {'layout': [[42, 100, [68, None]], [58, 124, [46]], [82, 148, [94]], [94, 160, []]],
    'roots': [42, 82],
    'top': 110}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [153], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [105], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    43),
   {'layout': [[43, 100, [70, None]], [59, 124, [47]], [83, 148, [95]], [95, 160, []]],
    'roots': [43, 83],
    'top': 111}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [150], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [102], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    44),
   {'layout': [[44, 100, [72, None]], [60, 124, [48]], [84, 148, [96]], [96, 160, []]],
    'roots': [44, 84],
    'top': 112}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    45),
   {'layout': [[45, 100, [74, None]], [61, 124, [49]], [85, 148, [97]], [97, 160, []]],
    'roots': [45, 85],
    'top': 113}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})]]
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: interior pointers relocate with their object{'layout': [[100, 100, [116, None]], [116, 124, [100]]], 'roots': [100], 'top': 140}{'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}Failed
dead objects do not advance the compaction pointer{'layout': [[100, 100, [116, None]], [116, 124, [100]]], 'roots': [116], 'top': 140}{'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}Failed
pointer to an object start{'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}{'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}Passed
interior root{'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100], 'top': 128}{'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}Failed
compaction into a lower base{'layout': [[41, 100, [57, None]], [57, 124, [41]], [81, 148, [93]], [93, 160, []]], 'roots': [41, 81], 'top': 109}{'layout': [[41, 100, [66, None]], [57, 124, [45]], [81, 148, [93]], [93, 160, []]], 'roots': [41, 81], 'top': 109}Failed
control: no roots{'layout': [], 'roots': [None], 'top': 100}{'layout': [], 'roots': [None], 'top': 100}Passed

SHA-256 / 2190ee3106401ebadd9b36a23a847d83f348ea27e0ca2b0dabdbaa5109ac5ee3

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, roots, base):
    starts = sorted(o[0] for o in objs)
    info = {o[0]: o for o in objs}
    def owner(p):
        i = bisect.bisect_right(starts, p) - 1
        if i < 0:
            raise KeyError(p)
        s = starts[i]
        if p >= s + info[s][1]:
            raise KeyError(p)
        return s
    try:
        live = set()
        stack = [r for r in roots if r is not None]
        while stack:
            s = owner(stack.pop())
            if s in live:
                continue
            live.add(s)
            stack.extend(f for f in info[s][2] if f is not None)
        fwd = {}
        top = base
        for s in starts:
            if s in live:
                fwd[s] = top
                top += info[s][1]
        def reloc(p):
            if p is None:
                return None
            s = owner(p)
            return fwd.get(p, p)
        layout = [[fwd[s], s, [reloc(f) for f in info[s][2]]] for s in starts if s in live]
        new_roots = [reloc(r) for r in roots]
    except KeyError as e:
        return ['dangling-pointer', e.args[0]]
    except IndexError:
        return ['heap-walk-error']
    return {'layout': layout, 'roots': new_roots, 'top': top}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    41),
   {'layout': [[41, 100, [66, None]], [57, 124, [45]], [81, 148, [93]], [93, 160, []]],
    'roots': [41, 81],
    'top': 109}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [152], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [104], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    42),
   {'layout': [[42, 100, [68, None]], [58, 124, [46]], [82, 148, [94]], [94, 160, []]],
    'roots': [42, 82],
    'top': 110}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [153], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [105], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    43),
   {'layout': [[43, 100, [70, None]], [59, 124, [47]], [83, 148, [95]], [95, 160, []]],
    'roots': [43, 83],
    'top': 111}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [150], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [102], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    44),
   {'layout': [[44, 100, [72, None]], [60, 124, [48]], [84, 148, [96]], [96, 160, []]],
    'roots': [44, 84],
    'top': 112}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    45),
   {'layout': [[45, 100, [74, None]], [61, 124, [49]], [85, 148, [97]], [97, 160, []]],
    'roots': [45, 85],
    'top': 113}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})]]
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: interior pointers relocate with their object{'layout': [[100, 100, [133, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}{'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}Failed
dead objects do not advance the compaction pointer{'layout': [[100, 100, [133, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}{'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}Failed
pointer to an object start{'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}{'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}Passed
interior root{'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [151], 'top': 128}{'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}Failed
compaction into a lower base{'layout': [[41, 100, [133, None]], [57, 124, [104]], [81, 148, [93]], [93, 160, []]], 'roots': [41, 81], 'top': 109}{'layout': [[41, 100, [66, None]], [57, 124, [45]], [81, 148, [93]], [93, 160, []]], 'roots': [41, 81], 'top': 109}Failed
control: no roots{'layout': [], 'roots': [None], 'top': 100}{'layout': [], 'roots': [None], 'top': 100}Passed

SHA-256 / cbbfd7564ff426655d5af81579c1a42b8379291016353d7ca0a98d1f29a5b520

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, roots, base):
    starts = sorted(o[0] for o in objs)
    info = {o[0]: o for o in objs}
    def owner(p):
        i = bisect.bisect_right(starts, p) - 1
        if i < 0:
            raise KeyError(p)
        s = starts[i]
        if p >= s + info[s][1]:
            raise KeyError(p)
        return s
    try:
        live = set()
        stack = [r for r in roots if r is not None]
        while stack:
            s = owner(stack.pop())
            if s in live:
                continue
            live.add(s)
            stack.extend(f for f in info[s][2] if f is not None)
        fwd = {}
        top = base
        for s in starts:
            if s in live:
                fwd[s] = top
                top += info[s][1]
        def reloc(p):
            if p is None:
                return None
            s = owner(p)
            return fwd[s] + (p - s)
        layout = [[fwd[s], s, [reloc(f) for f in info[s][2]]] for s in starts if s in live]
        new_roots = [reloc(r) for r in roots]
    except KeyError as e:
        return ['dangling-pointer', e.args[0]]
    except IndexError:
        return ['heap-walk-error']
    return {'layout': layout, 'roots': new_roots, 'top': top}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    41),
   {'layout': [[41, 100, [66, None]], [57, 124, [45]], [81, 148, [93]], [93, 160, []]],
    'roots': [41, 81],
    'top': 109}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [152], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [104], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    42),
   {'layout': [[42, 100, [68, None]], [58, 124, [46]], [82, 148, [94]], [94, 160, []]],
    'roots': [42, 82],
    'top': 110}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [153], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [105], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    43),
   {'layout': [[43, 100, [70, None]], [59, 124, [47]], [83, 148, [95]], [95, 160, []]],
    'roots': [43, 83],
    'top': 111}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [150], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [102], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    44),
   {'layout': [[44, 100, [72, None]], [60, 124, [48]], [84, 148, [96]], [96, 160, []]],
    'roots': [44, 84],
    'top': 112}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    45),
   {'layout': [[45, 100, [74, None]], [61, 124, [49]], [85, 148, [97]], [97, 160, []]],
    'roots': [45, 85],
    'top': 113}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})]]
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: interior pointers relocate with their object{'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}{'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}Passed
dead objects do not advance the compaction pointer{'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}{'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}Passed
pointer to an object start{'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}{'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}Passed
interior root{'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}{'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}Passed
compaction into a lower base{'layout': [[41, 100, [66, None]], [57, 124, [45]], [81, 148, [93]], [93, 160, []]], 'roots': [41, 81], 'top': 109}{'layout': [[41, 100, [66, None]], [57, 124, [45]], [81, 148, [93]], [93, 160, []]], 'roots': [41, 81], 'top': 109}Passed
control: no roots{'layout': [], 'roots': [None], 'top': 100}{'layout': [], 'roots': [None], 'top': 100}Passed

SHA-256 / 7f6661f7901952b2ebb5af39b303c2f4767975b75505b69b16e560bb03440d9c

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

Case digest / d3a7fe94321dc43a0ce373d68b206f4d01cc0c2dce090b675f93fe654cece533