FA-90441 / Garbage collector invariants / Open access

Sliding compaction: new addresses assigned in input order · case 01

Objects are permuted instead of slid, so live objects can overtake each other.

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

ROOT CAUSE

Forwarding addresses follow the order the objects were listed in, not their addresses.

VERIFIED REPAIR

Assign forwarding addresses in ascending address order.

Unsuccessful approach: Ordering by size moves large objects first and still breaks address order.

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 [o[0] for o in objs]:
            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 fixture	Actual	Expected	Outcome
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': [[116, 148, [100]], [100, 160, []]], 'roots': [116, 100], 'top': 128}`	`{'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}`	Failed
interior root	`{'layout': [[116, 148, [100]], [100, 160, []]], 'roots': [119], 'top': 128}`	`{'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}`	Failed
compaction into a lower base	`{'layout': [[57, 100, [82, None]], [73, 124, [61]], [97, 148, [41]], [41, 160, []]], 'roots': [57, 97], '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 / 4872ae47afae84b7bca2668a51a8dd34912f048c869f3dc84f21fef31141f47f

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 sorted(starts, key=lambda s: -info[s][1]):
            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 fixture	Actual	Expected	Outcome
regression: interior pointers relocate with their object	`{'layout': [[124, 100, [109, None]], [100, 124, [128]]], 'roots': [124], 'top': 140}`	`{'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}`	Failed
dead objects do not advance the compaction pointer	`{'layout': [[124, 100, [109, None]], [100, 124, [128]]], 'roots': [100], 'top': 140}`	`{'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}`	Failed
pointer to an object start	`{'layout': [[116, 148, [100]], [100, 160, []]], 'roots': [116, 100], 'top': 128}`	`{'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}`	Failed
interior root	`{'layout': [[116, 148, [100]], [100, 160, []]], 'roots': [119], 'top': 128}`	`{'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}`	Failed
compaction into a lower base	`{'layout': [[65, 100, [50, None]], [41, 124, [69]], [97, 148, [81]], [81, 160, []]], 'roots': [65, 97], '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 / 89f24d580a683752730cf63d1e8aef27ef7e6dc770cb225cb77c1e9f0c41f737

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

Case digest / 0abb85d859488bb7a149b698af6541ff9b28e39113a5edf0ecdaab440e9de3b5