FA-90726 / Garbage collector invariants / Open access
Identity hash: mask applied before the shift · case 01
Hashes of unmoved objects disagree with the value later stored on move.
ROOT CAUSE
The expression masks the address with 0xFFFF >> 3 instead of shifting first.
VERIFIED REPAIR
Shift the address right by 3, then mask with 0xFFFF.
Unsuccessful approach: Masking before shifting drops address bits 16-18 that the stored hash keeps.
Case contract
objs maps id -> [address, size]. The identity hash of an object is (address >> 3) & 0xFFFF of the address at which it was first hashed. Objects start unhashed; hash marks them hashed and returns the hash computed from the current address while they have not moved. The first move of a hashed object stores that hash in a new 8-byte trailing slot (size grows by 8) and later moves keep it; moving an unhashed object stores nothing. Return all hashes and the final [address, size] layout.
Why this case matters
Moving collectors must keep identity hashes stable even though they are derived from addresses.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(objs, events):
objs = {k: list(v) for k, v in objs.items()}
state = {o: 'unhashed' for o in objs}
stored = {}
out = []
for ev in events:
o = ev[1]
if ev[0] == 'hash':
if state[o] == 'unhashed':
state[o] = 'hashed'
if state[o] == 'hashed':
out.append(objs[o][0] & 0xFFFF >> 3)
else:
out.append(stored[o])
else:
if state[o] == 'hashed':
stored[o] = objs[o][0] >> 3 & 0xFFFF
state[o] = 'moved'
objs[o][1] += 8
objs[o][0] = ev[2]
return {'hashes': out, 'layout': {str(k): v for k, v in sorted(objs.items())}}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: hash survives a move',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 1], ['move', 1, 32768], ['hash', 1]]),
{'hashes': [8201, 8201], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}}),
('object moved twice after hashing',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]},
[['hash', 2], ['move', 2, 36872], ['move', 2, 40960], ['hash', 2]]),
{'hashes': [1024, 1024], 'layout': {'1': [65608, 24], '2': [40960, 24], '3': [201272, 32]}}),
('unhashed object moves freely',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 3, 16400], ['hash', 3], ['hash', 3]]),
{'hashes': [2050, 2050], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [16400, 32]}}),
('high address bits masked after shifting',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 3], ['hash', 1]]),
{'hashes': [25159, 8201], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [201272, 32]}}),
('hash requested again before any move',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 2], ['hash', 2], ['move', 1, 20488]]),
{'hashes': [1024, 1024], 'layout': {'1': [20488, 24], '2': [8192, 16], '3': [201272, 32]}}),
('control: no hashing',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 2, 24576], ['move', 2, 28680]]),
{'hashes': [], 'layout': {'1': [65608, 24], '2': [28680, 16], '3': [201272, 32]}})],
[('regression: hash survives a move',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 1], ['move', 1, 32768], ['hash', 1]]),
{'hashes': [8202, 8202], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}}),
('object moved twice after hashing',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]},
[['hash', 2], ['move', 2, 36880], ['move', 2, 40960], ['hash', 2]]),
{'hashes': [1024, 1024], 'layout': {'1': [65616, 24], '2': [40960, 24], '3': [201272, 32]}}),
('unhashed object moves freely',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 3, 16416], ['hash', 3], ['hash', 3]]),
{'hashes': [2052, 2052], 'layout': {'1': [65616, 24], '2': [8192, 16], '3': [16416, 32]}}),
('high address bits masked after shifting',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 3], ['hash', 1]]),
{'hashes': [25159, 8202], 'layout': {'1': [65616, 24], '2': [8192, 16], '3': [201272, 32]}}),
('hash requested again before any move',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 2], ['hash', 2], ['move', 1, 20496]]),
{'hashes': [1024, 1024], 'layout': {'1': [20496, 24], '2': [8192, 16], '3': [201272, 32]}}),
('control: no hashing',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 2, 24576], ['move', 2, 28688]]),
{'hashes': [], 'layout': {'1': [65616, 24], '2': [28688, 16], '3': [201272, 32]}})],
[('regression: hash survives a move',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 1], ['move', 1, 32768], ['hash', 1]]),
{'hashes': [8203, 8203], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}}),
('object moved twice after hashing',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]},
[['hash', 2], ['move', 2, 36888], ['move', 2, 40960], ['hash', 2]]),
{'hashes': [1024, 1024], 'layout': {'1': [65624, 24], '2': [40960, 24], '3': [201272, 32]}}),
('unhashed object moves freely',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 3, 16432], ['hash', 3], ['hash', 3]]),
{'hashes': [2054, 2054], 'layout': {'1': [65624, 24], '2': [8192, 16], '3': [16432, 32]}}),
('high address bits masked after shifting',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 3], ['hash', 1]]),
{'hashes': [25159, 8203], 'layout': {'1': [65624, 24], '2': [8192, 16], '3': [201272, 32]}}),
('hash requested again before any move',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 2], ['hash', 2], ['move', 1, 20504]]),
{'hashes': [1024, 1024], 'layout': {'1': [20504, 24], '2': [8192, 16], '3': [201272, 32]}}),
('control: no hashing',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 2, 24576], ['move', 2, 28696]]),
{'hashes': [], 'layout': {'1': [65624, 24], '2': [28696, 16], '3': [201272, 32]}})],
[('regression: hash survives a move',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 1], ['move', 1, 32768], ['hash', 1]]),
{'hashes': [8204, 8204], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}}),
('object moved twice after hashing',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]},
[['hash', 2], ['move', 2, 36896], ['move', 2, 40960], ['hash', 2]]),
{'hashes': [1024, 1024], 'layout': {'1': [65632, 24], '2': [40960, 24], '3': [201272, 32]}}),
('unhashed object moves freely',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 3, 16448], ['hash', 3], ['hash', 3]]),
{'hashes': [2056, 2056], 'layout': {'1': [65632, 24], '2': [8192, 16], '3': [16448, 32]}}),
('high address bits masked after shifting',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 3], ['hash', 1]]),
{'hashes': [25159, 8204], 'layout': {'1': [65632, 24], '2': [8192, 16], '3': [201272, 32]}}),
('hash requested again before any move',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 2], ['hash', 2], ['move', 1, 20512]]),
{'hashes': [1024, 1024], 'layout': {'1': [20512, 24], '2': [8192, 16], '3': [201272, 32]}}),
('control: no hashing',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 2, 24576], ['move', 2, 28704]]),
{'hashes': [], 'layout': {'1': [65632, 24], '2': [28704, 16], '3': [201272, 32]}})],
[('regression: hash survives a move',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 1], ['move', 1, 32768], ['hash', 1]]),
{'hashes': [8205, 8205], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}}),
('object moved twice after hashing',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]},
[['hash', 2], ['move', 2, 36904], ['move', 2, 40960], ['hash', 2]]),
{'hashes': [1024, 1024], 'layout': {'1': [65640, 24], '2': [40960, 24], '3': [201272, 32]}}),
('unhashed object moves freely',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 3, 16464], ['hash', 3], ['hash', 3]]),
{'hashes': [2058, 2058], 'layout': {'1': [65640, 24], '2': [8192, 16], '3': [16464, 32]}}),
('high address bits masked after shifting',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 3], ['hash', 1]]),
{'hashes': [25159, 8205], 'layout': {'1': [65640, 24], '2': [8192, 16], '3': [201272, 32]}}),
('hash requested again before any move',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 2], ['hash', 2], ['move', 1, 20520]]),
{'hashes': [1024, 1024], 'layout': {'1': [20520, 24], '2': [8192, 16], '3': [201272, 32]}}),
('control: no hashing',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 2, 24576], ['move', 2, 28712]]),
{'hashes': [], 'layout': {'1': [65640, 24], '2': [28712, 16], '3': [201272, 32]}})]]
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: hash survives a move | {'hashes': [72, 8201], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}} | {'hashes': [8201, 8201], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}} | Failed |
| object moved twice after hashing | {'hashes': [0, 1024], 'layout': {'1': [65608, 24], '2': [40960, 24], '3': [201272, 32]}} | {'hashes': [1024, 1024], 'layout': {'1': [65608, 24], '2': [40960, 24], '3': [201272, 32]}} | Failed |
| unhashed object moves freely | {'hashes': [16, 16], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [16400, 32]}} | {'hashes': [2050, 2050], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [16400, 32]}} | Failed |
| high address bits masked after shifting | {'hashes': [4664, 72], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [201272, 32]}} | {'hashes': [25159, 8201], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [201272, 32]}} | Failed |
| hash requested again before any move | {'hashes': [0, 0], 'layout': {'1': [20488, 24], '2': [8192, 16], '3': [201272, 32]}} | {'hashes': [1024, 1024], 'layout': {'1': [20488, 24], '2': [8192, 16], '3': [201272, 32]}} | Failed |
| control: no hashing | {'hashes': [], 'layout': {'1': [65608, 24], '2': [28680, 16], '3': [201272, 32]}} | {'hashes': [], 'layout': {'1': [65608, 24], '2': [28680, 16], '3': [201272, 32]}} | Passed |
SHA-256 / 07fe622eac8ce38b87c3fe65878336a9519cd5c62b4a45b3226507f889b47a44
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(objs, events):
objs = {k: list(v) for k, v in objs.items()}
state = {o: 'unhashed' for o in objs}
stored = {}
out = []
for ev in events:
o = ev[1]
if ev[0] == 'hash':
if state[o] == 'unhashed':
state[o] = 'hashed'
if state[o] == 'hashed':
out.append((objs[o][0] & 0xFFFF) >> 3)
else:
out.append(stored[o])
else:
if state[o] == 'hashed':
stored[o] = objs[o][0] >> 3 & 0xFFFF
state[o] = 'moved'
objs[o][1] += 8
objs[o][0] = ev[2]
return {'hashes': out, 'layout': {str(k): v for k, v in sorted(objs.items())}}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: hash survives a move',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 1], ['move', 1, 32768], ['hash', 1]]),
{'hashes': [8201, 8201], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}}),
('object moved twice after hashing',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]},
[['hash', 2], ['move', 2, 36872], ['move', 2, 40960], ['hash', 2]]),
{'hashes': [1024, 1024], 'layout': {'1': [65608, 24], '2': [40960, 24], '3': [201272, 32]}}),
('unhashed object moves freely',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 3, 16400], ['hash', 3], ['hash', 3]]),
{'hashes': [2050, 2050], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [16400, 32]}}),
('high address bits masked after shifting',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 3], ['hash', 1]]),
{'hashes': [25159, 8201], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [201272, 32]}}),
('hash requested again before any move',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 2], ['hash', 2], ['move', 1, 20488]]),
{'hashes': [1024, 1024], 'layout': {'1': [20488, 24], '2': [8192, 16], '3': [201272, 32]}}),
('control: no hashing',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 2, 24576], ['move', 2, 28680]]),
{'hashes': [], 'layout': {'1': [65608, 24], '2': [28680, 16], '3': [201272, 32]}})],
[('regression: hash survives a move',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 1], ['move', 1, 32768], ['hash', 1]]),
{'hashes': [8202, 8202], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}}),
('object moved twice after hashing',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]},
[['hash', 2], ['move', 2, 36880], ['move', 2, 40960], ['hash', 2]]),
{'hashes': [1024, 1024], 'layout': {'1': [65616, 24], '2': [40960, 24], '3': [201272, 32]}}),
('unhashed object moves freely',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 3, 16416], ['hash', 3], ['hash', 3]]),
{'hashes': [2052, 2052], 'layout': {'1': [65616, 24], '2': [8192, 16], '3': [16416, 32]}}),
('high address bits masked after shifting',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 3], ['hash', 1]]),
{'hashes': [25159, 8202], 'layout': {'1': [65616, 24], '2': [8192, 16], '3': [201272, 32]}}),
('hash requested again before any move',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 2], ['hash', 2], ['move', 1, 20496]]),
{'hashes': [1024, 1024], 'layout': {'1': [20496, 24], '2': [8192, 16], '3': [201272, 32]}}),
('control: no hashing',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 2, 24576], ['move', 2, 28688]]),
{'hashes': [], 'layout': {'1': [65616, 24], '2': [28688, 16], '3': [201272, 32]}})],
[('regression: hash survives a move',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 1], ['move', 1, 32768], ['hash', 1]]),
{'hashes': [8203, 8203], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}}),
('object moved twice after hashing',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]},
[['hash', 2], ['move', 2, 36888], ['move', 2, 40960], ['hash', 2]]),
{'hashes': [1024, 1024], 'layout': {'1': [65624, 24], '2': [40960, 24], '3': [201272, 32]}}),
('unhashed object moves freely',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 3, 16432], ['hash', 3], ['hash', 3]]),
{'hashes': [2054, 2054], 'layout': {'1': [65624, 24], '2': [8192, 16], '3': [16432, 32]}}),
('high address bits masked after shifting',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 3], ['hash', 1]]),
{'hashes': [25159, 8203], 'layout': {'1': [65624, 24], '2': [8192, 16], '3': [201272, 32]}}),
('hash requested again before any move',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 2], ['hash', 2], ['move', 1, 20504]]),
{'hashes': [1024, 1024], 'layout': {'1': [20504, 24], '2': [8192, 16], '3': [201272, 32]}}),
('control: no hashing',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 2, 24576], ['move', 2, 28696]]),
{'hashes': [], 'layout': {'1': [65624, 24], '2': [28696, 16], '3': [201272, 32]}})],
[('regression: hash survives a move',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 1], ['move', 1, 32768], ['hash', 1]]),
{'hashes': [8204, 8204], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}}),
('object moved twice after hashing',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]},
[['hash', 2], ['move', 2, 36896], ['move', 2, 40960], ['hash', 2]]),
{'hashes': [1024, 1024], 'layout': {'1': [65632, 24], '2': [40960, 24], '3': [201272, 32]}}),
('unhashed object moves freely',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 3, 16448], ['hash', 3], ['hash', 3]]),
{'hashes': [2056, 2056], 'layout': {'1': [65632, 24], '2': [8192, 16], '3': [16448, 32]}}),
('high address bits masked after shifting',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 3], ['hash', 1]]),
{'hashes': [25159, 8204], 'layout': {'1': [65632, 24], '2': [8192, 16], '3': [201272, 32]}}),
('hash requested again before any move',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 2], ['hash', 2], ['move', 1, 20512]]),
{'hashes': [1024, 1024], 'layout': {'1': [20512, 24], '2': [8192, 16], '3': [201272, 32]}}),
('control: no hashing',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 2, 24576], ['move', 2, 28704]]),
{'hashes': [], 'layout': {'1': [65632, 24], '2': [28704, 16], '3': [201272, 32]}})],
[('regression: hash survives a move',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 1], ['move', 1, 32768], ['hash', 1]]),
{'hashes': [8205, 8205], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}}),
('object moved twice after hashing',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]},
[['hash', 2], ['move', 2, 36904], ['move', 2, 40960], ['hash', 2]]),
{'hashes': [1024, 1024], 'layout': {'1': [65640, 24], '2': [40960, 24], '3': [201272, 32]}}),
('unhashed object moves freely',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 3, 16464], ['hash', 3], ['hash', 3]]),
{'hashes': [2058, 2058], 'layout': {'1': [65640, 24], '2': [8192, 16], '3': [16464, 32]}}),
('high address bits masked after shifting',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 3], ['hash', 1]]),
{'hashes': [25159, 8205], 'layout': {'1': [65640, 24], '2': [8192, 16], '3': [201272, 32]}}),
('hash requested again before any move',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 2], ['hash', 2], ['move', 1, 20520]]),
{'hashes': [1024, 1024], 'layout': {'1': [20520, 24], '2': [8192, 16], '3': [201272, 32]}}),
('control: no hashing',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 2, 24576], ['move', 2, 28712]]),
{'hashes': [], 'layout': {'1': [65640, 24], '2': [28712, 16], '3': [201272, 32]}})]]
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: hash survives a move | {'hashes': [9, 8201], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}} | {'hashes': [8201, 8201], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}} | Failed |
| object moved twice after hashing | {'hashes': [1024, 1024], 'layout': {'1': [65608, 24], '2': [40960, 24], '3': [201272, 32]}} | {'hashes': [1024, 1024], 'layout': {'1': [65608, 24], '2': [40960, 24], '3': [201272, 32]}} | Passed |
| unhashed object moves freely | {'hashes': [2050, 2050], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [16400, 32]}} | {'hashes': [2050, 2050], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [16400, 32]}} | Passed |
| high address bits masked after shifting | {'hashes': [583, 9], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [201272, 32]}} | {'hashes': [25159, 8201], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [201272, 32]}} | Failed |
| hash requested again before any move | {'hashes': [1024, 1024], 'layout': {'1': [20488, 24], '2': [8192, 16], '3': [201272, 32]}} | {'hashes': [1024, 1024], 'layout': {'1': [20488, 24], '2': [8192, 16], '3': [201272, 32]}} | Passed |
| control: no hashing | {'hashes': [], 'layout': {'1': [65608, 24], '2': [28680, 16], '3': [201272, 32]}} | {'hashes': [], 'layout': {'1': [65608, 24], '2': [28680, 16], '3': [201272, 32]}} | Passed |
SHA-256 / c5c636f57f3896fa3af414b616caf019ed13c9e24977bd2406af7e803431e616
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(objs, events):
objs = {k: list(v) for k, v in objs.items()}
state = {o: 'unhashed' for o in objs}
stored = {}
out = []
for ev in events:
o = ev[1]
if ev[0] == 'hash':
if state[o] == 'unhashed':
state[o] = 'hashed'
if state[o] == 'hashed':
out.append(objs[o][0] >> 3 & 0xFFFF)
else:
out.append(stored[o])
else:
if state[o] == 'hashed':
stored[o] = objs[o][0] >> 3 & 0xFFFF
state[o] = 'moved'
objs[o][1] += 8
objs[o][0] = ev[2]
return {'hashes': out, 'layout': {str(k): v for k, v in sorted(objs.items())}}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: hash survives a move',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 1], ['move', 1, 32768], ['hash', 1]]),
{'hashes': [8201, 8201], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}}),
('object moved twice after hashing',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]},
[['hash', 2], ['move', 2, 36872], ['move', 2, 40960], ['hash', 2]]),
{'hashes': [1024, 1024], 'layout': {'1': [65608, 24], '2': [40960, 24], '3': [201272, 32]}}),
('unhashed object moves freely',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 3, 16400], ['hash', 3], ['hash', 3]]),
{'hashes': [2050, 2050], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [16400, 32]}}),
('high address bits masked after shifting',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 3], ['hash', 1]]),
{'hashes': [25159, 8201], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [201272, 32]}}),
('hash requested again before any move',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 2], ['hash', 2], ['move', 1, 20488]]),
{'hashes': [1024, 1024], 'layout': {'1': [20488, 24], '2': [8192, 16], '3': [201272, 32]}}),
('control: no hashing',
({1: [65608, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 2, 24576], ['move', 2, 28680]]),
{'hashes': [], 'layout': {'1': [65608, 24], '2': [28680, 16], '3': [201272, 32]}})],
[('regression: hash survives a move',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 1], ['move', 1, 32768], ['hash', 1]]),
{'hashes': [8202, 8202], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}}),
('object moved twice after hashing',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]},
[['hash', 2], ['move', 2, 36880], ['move', 2, 40960], ['hash', 2]]),
{'hashes': [1024, 1024], 'layout': {'1': [65616, 24], '2': [40960, 24], '3': [201272, 32]}}),
('unhashed object moves freely',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 3, 16416], ['hash', 3], ['hash', 3]]),
{'hashes': [2052, 2052], 'layout': {'1': [65616, 24], '2': [8192, 16], '3': [16416, 32]}}),
('high address bits masked after shifting',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 3], ['hash', 1]]),
{'hashes': [25159, 8202], 'layout': {'1': [65616, 24], '2': [8192, 16], '3': [201272, 32]}}),
('hash requested again before any move',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 2], ['hash', 2], ['move', 1, 20496]]),
{'hashes': [1024, 1024], 'layout': {'1': [20496, 24], '2': [8192, 16], '3': [201272, 32]}}),
('control: no hashing',
({1: [65616, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 2, 24576], ['move', 2, 28688]]),
{'hashes': [], 'layout': {'1': [65616, 24], '2': [28688, 16], '3': [201272, 32]}})],
[('regression: hash survives a move',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 1], ['move', 1, 32768], ['hash', 1]]),
{'hashes': [8203, 8203], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}}),
('object moved twice after hashing',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]},
[['hash', 2], ['move', 2, 36888], ['move', 2, 40960], ['hash', 2]]),
{'hashes': [1024, 1024], 'layout': {'1': [65624, 24], '2': [40960, 24], '3': [201272, 32]}}),
('unhashed object moves freely',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 3, 16432], ['hash', 3], ['hash', 3]]),
{'hashes': [2054, 2054], 'layout': {'1': [65624, 24], '2': [8192, 16], '3': [16432, 32]}}),
('high address bits masked after shifting',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 3], ['hash', 1]]),
{'hashes': [25159, 8203], 'layout': {'1': [65624, 24], '2': [8192, 16], '3': [201272, 32]}}),
('hash requested again before any move',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 2], ['hash', 2], ['move', 1, 20504]]),
{'hashes': [1024, 1024], 'layout': {'1': [20504, 24], '2': [8192, 16], '3': [201272, 32]}}),
('control: no hashing',
({1: [65624, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 2, 24576], ['move', 2, 28696]]),
{'hashes': [], 'layout': {'1': [65624, 24], '2': [28696, 16], '3': [201272, 32]}})],
[('regression: hash survives a move',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 1], ['move', 1, 32768], ['hash', 1]]),
{'hashes': [8204, 8204], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}}),
('object moved twice after hashing',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]},
[['hash', 2], ['move', 2, 36896], ['move', 2, 40960], ['hash', 2]]),
{'hashes': [1024, 1024], 'layout': {'1': [65632, 24], '2': [40960, 24], '3': [201272, 32]}}),
('unhashed object moves freely',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 3, 16448], ['hash', 3], ['hash', 3]]),
{'hashes': [2056, 2056], 'layout': {'1': [65632, 24], '2': [8192, 16], '3': [16448, 32]}}),
('high address bits masked after shifting',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 3], ['hash', 1]]),
{'hashes': [25159, 8204], 'layout': {'1': [65632, 24], '2': [8192, 16], '3': [201272, 32]}}),
('hash requested again before any move',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 2], ['hash', 2], ['move', 1, 20512]]),
{'hashes': [1024, 1024], 'layout': {'1': [20512, 24], '2': [8192, 16], '3': [201272, 32]}}),
('control: no hashing',
({1: [65632, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 2, 24576], ['move', 2, 28704]]),
{'hashes': [], 'layout': {'1': [65632, 24], '2': [28704, 16], '3': [201272, 32]}})],
[('regression: hash survives a move',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 1], ['move', 1, 32768], ['hash', 1]]),
{'hashes': [8205, 8205], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}}),
('object moved twice after hashing',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]},
[['hash', 2], ['move', 2, 36904], ['move', 2, 40960], ['hash', 2]]),
{'hashes': [1024, 1024], 'layout': {'1': [65640, 24], '2': [40960, 24], '3': [201272, 32]}}),
('unhashed object moves freely',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 3, 16464], ['hash', 3], ['hash', 3]]),
{'hashes': [2058, 2058], 'layout': {'1': [65640, 24], '2': [8192, 16], '3': [16464, 32]}}),
('high address bits masked after shifting',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 3], ['hash', 1]]),
{'hashes': [25159, 8205], 'layout': {'1': [65640, 24], '2': [8192, 16], '3': [201272, 32]}}),
('hash requested again before any move',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]}, [['hash', 2], ['hash', 2], ['move', 1, 20520]]),
{'hashes': [1024, 1024], 'layout': {'1': [20520, 24], '2': [8192, 16], '3': [201272, 32]}}),
('control: no hashing',
({1: [65640, 24], 2: [8192, 16], 3: [201272, 32]}, [['move', 2, 24576], ['move', 2, 28712]]),
{'hashes': [], 'layout': {'1': [65640, 24], '2': [28712, 16], '3': [201272, 32]}})]]
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: hash survives a move | {'hashes': [8201, 8201], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}} | {'hashes': [8201, 8201], 'layout': {'1': [32768, 32], '2': [8192, 16], '3': [201272, 32]}} | Passed |
| object moved twice after hashing | {'hashes': [1024, 1024], 'layout': {'1': [65608, 24], '2': [40960, 24], '3': [201272, 32]}} | {'hashes': [1024, 1024], 'layout': {'1': [65608, 24], '2': [40960, 24], '3': [201272, 32]}} | Passed |
| unhashed object moves freely | {'hashes': [2050, 2050], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [16400, 32]}} | {'hashes': [2050, 2050], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [16400, 32]}} | Passed |
| high address bits masked after shifting | {'hashes': [25159, 8201], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [201272, 32]}} | {'hashes': [25159, 8201], 'layout': {'1': [65608, 24], '2': [8192, 16], '3': [201272, 32]}} | Passed |
| hash requested again before any move | {'hashes': [1024, 1024], 'layout': {'1': [20488, 24], '2': [8192, 16], '3': [201272, 32]}} | {'hashes': [1024, 1024], 'layout': {'1': [20488, 24], '2': [8192, 16], '3': [201272, 32]}} | Passed |
| control: no hashing | {'hashes': [], 'layout': {'1': [65608, 24], '2': [28680, 16], '3': [201272, 32]}} | {'hashes': [], 'layout': {'1': [65608, 24], '2': [28680, 16], '3': [201272, 32]}} | Passed |
SHA-256 / 833e8694f855cae3d49d4a975513f32316eb3a8276ffe6c1edb0c9e30f962259
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:29.282595+00:00.
Case digest / adb5dbdb133ac995d97c7cdf18a08c8d355c7378b5c55266890dc6210780f1ff