FA-90721 / Garbage collector invariants / Open access
Identity hash: moved objects hash their current address · case 01
hashCode changes after every collection that moves the object.
ROOT CAUSE
The lookup for moved objects ignores the stored slot.
VERIFIED REPAIR
Return the stored hash once an object has moved.
Unsuccessful approach: Re-deriving from the stored value shifts and masks it a second time.
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] >> 3 & 0xFFFF)
else:
out.append(objs[o][0] >> 3 & 0xFFFF)
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, 4096], '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, 5120], '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': [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 / d3d56bd78378d8eb53a7653317ce53cdcd75a394ed7ac59f8556ed99c0432293
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] >> 3 & 0xFFFF)
else:
out.append(stored.get(o, objs[o][0]) >> 3 & 0xFFFF)
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, 1025], '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, 128], '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': [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 / 300b377c1798b734ddbe1f859a5ff2d44d0a3f0def5956d6ba79497de416b086
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.282725+00:00.
Case digest / 6d64fea93d814b2361261acb3d195834affab30e97117a9dab707fd7c8c39cf0