broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, words, interior):
    starts = sorted(o[0] for o in objs)
    size_of = {o[0]: o[1] for o in objs}
    alloc = {o[0]: o[2] for o in objs}
    lo = min(starts) if starts else 0
    hi = max(s + size_of[s] for s in starts) if starts else 0
    found = set()
    for w in words:
        if w & 7 != 3:
            continue
        a = w - 3
        if not (lo <= a < hi):
            continue
        i = bisect.bisect_right(starts, a) - 1
        s = starts[i]
        if not alloc[s]:
            continue
        if a == s or (a < s + size_of[s]):
            found.add(s)
    return sorted(found)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: tagged start pointers only',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),
   [320, 352]),
  ('interior pointers when allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),
   [320, 352, 416]),
  ('interior pointer rejected when not allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),
   []),
  ('pointers to a free block',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),
   []),
  ('pointer exactly at a later object start',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),
   [416]),
  ('control: untagged words ignored',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),
   [])],
 [('regression: tagged start pointers only',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),
   [576, 608]),
  ('interior pointers when allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),
   [576, 608, 672]),
  ('interior pointer rejected when not allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),
   []),
  ('pointers to a free block',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),
   []),
  ('pointer exactly at a later object start',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),
   [672]),
  ('control: untagged words ignored',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),
   [])],
 [('regression: tagged start pointers only',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),
   [832, 864]),
  ('interior pointers when allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),
   [832, 864, 928]),
  ('interior pointer rejected when not allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),
   []),
  ('pointers to a free block',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),
   []),
  ('pointer exactly at a later object start',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),
   [928]),
  ('control: untagged words ignored',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],
    [1091, 1123, 1090, 1131],
    False),
   [1088, 1120]),
  ('interior pointers when allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),
   [1088, 1120, 1184]),
  ('interior pointer rejected when not allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),
   []),
  ('pointers to a free block',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),
   []),
  ('pointer exactly at a later object start',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),
   [1184]),
  ('control: untagged words ignored',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],
    [1347, 1379, 1346, 1387],
    False),
   [1344, 1376]),
  ('interior pointers when allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),
   [1344, 1376, 1440]),
  ('interior pointer rejected when not allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),
   []),
  ('pointers to a free block',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),
   []),
  ('pointer exactly at a later object start',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),
   [1440]),
  ('control: untagged words ignored',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),
   [])]]
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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, words, interior):
    starts = sorted(o[0] for o in objs)
    size_of = {o[0]: o[1] for o in objs}
    alloc = {o[0]: o[2] for o in objs}
    lo = min(starts) if starts else 0
    hi = max(s + size_of[s] for s in starts) if starts else 0
    found = set()
    for w in words:
        if w & 7 != 3:
            continue
        a = w - 3
        if not (lo <= a < hi):
            continue
        i = bisect.bisect_right(starts, a) - 1
        s = starts[i]
        if not alloc[s]:
            continue
        if a == s or (interior or a - s < 8):
            found.add(s)
    return sorted(found)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: tagged start pointers only',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),
   [320, 352]),
  ('interior pointers when allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),
   [320, 352, 416]),
  ('interior pointer rejected when not allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),
   []),
  ('pointers to a free block',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),
   []),
  ('pointer exactly at a later object start',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),
   [416]),
  ('control: untagged words ignored',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),
   [])],
 [('regression: tagged start pointers only',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),
   [576, 608]),
  ('interior pointers when allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),
   [576, 608, 672]),
  ('interior pointer rejected when not allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),
   []),
  ('pointers to a free block',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),
   []),
  ('pointer exactly at a later object start',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),
   [672]),
  ('control: untagged words ignored',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),
   [])],
 [('regression: tagged start pointers only',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),
   [832, 864]),
  ('interior pointers when allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),
   [832, 864, 928]),
  ('interior pointer rejected when not allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),
   []),
  ('pointers to a free block',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),
   []),
  ('pointer exactly at a later object start',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),
   [928]),
  ('control: untagged words ignored',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],
    [1091, 1123, 1090, 1131],
    False),
   [1088, 1120]),
  ('interior pointers when allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),
   [1088, 1120, 1184]),
  ('interior pointer rejected when not allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),
   []),
  ('pointers to a free block',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),
   []),
  ('pointer exactly at a later object start',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),
   [1184]),
  ('control: untagged words ignored',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],
    [1347, 1379, 1346, 1387],
    False),
   [1344, 1376]),
  ('interior pointers when allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),
   [1344, 1376, 1440]),
  ('interior pointer rejected when not allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),
   []),
  ('pointers to a free block',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),
   []),
  ('pointer exactly at a later object start',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),
   [1440]),
  ('control: untagged words ignored',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),
   [])]]
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)

prompt:
Configurations that only recognise object-start pointers pin objects through interior addresses.

Conservative scanning of machine words. A word whose low three bits are 011 is a tagged heap pointer to address word - 3; all other words are immediates. objs are [start, size, allocated] in any order. A candidate address pins the allocated object whose start equals it, or, when interior pointers are enabled, the allocated object whose [start, start+size) contains it; addresses in gaps, in free blocks or outside the heap pin nothing. Return the sorted starts of pinned objects.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, words, interior):
    starts = sorted(o[0] for o in objs)
    size_of = {o[0]: o[1] for o in objs}
    alloc = {o[0]: o[2] for o in objs}
    lo = min(starts) if starts else 0
    hi = max(s + size_of[s] for s in starts) if starts else 0
    found = set()
    for w in words:
        if w & 7 != 3:
            continue
        a = w - 3
        if not (lo <= a < hi):
            continue
        i = bisect.bisect_left(starts, a) - 1
        s = starts[i]
        if not alloc[s]:
            continue
        if a == s or (interior and a < s + size_of[s]):
            found.add(s)
    return sorted(found)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: tagged start pointers only',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),
   [320, 352]),
  ('interior pointers when allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),
   [320, 352, 416]),
  ('interior pointer rejected when not allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),
   []),
  ('pointers to a free block',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),
   []),
  ('pointer exactly at a later object start',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),
   [416]),
  ('control: untagged words ignored',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),
   [])],
 [('regression: tagged start pointers only',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),
   [576, 608]),
  ('interior pointers when allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),
   [576, 608, 672]),
  ('interior pointer rejected when not allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),
   []),
  ('pointers to a free block',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),
   []),
  ('pointer exactly at a later object start',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),
   [672]),
  ('control: untagged words ignored',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),
   [])],
 [('regression: tagged start pointers only',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),
   [832, 864]),
  ('interior pointers when allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),
   [832, 864, 928]),
  ('interior pointer rejected when not allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),
   []),
  ('pointers to a free block',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),
   []),
  ('pointer exactly at a later object start',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),
   [928]),
  ('control: untagged words ignored',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],
    [1091, 1123, 1090, 1131],
    False),
   [1088, 1120]),
  ('interior pointers when allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),
   [1088, 1120, 1184]),
  ('interior pointer rejected when not allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),
   []),
  ('pointers to a free block',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),
   []),
  ('pointer exactly at a later object start',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),
   [1184]),
  ('control: untagged words ignored',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],
    [1347, 1379, 1346, 1387],
    False),
   [1344, 1376]),
  ('interior pointers when allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),
   [1344, 1376, 1440]),
  ('interior pointer rejected when not allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),
   []),
  ('pointers to a free block',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),
   []),
  ('pointer exactly at a later object start',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),
   [1440]),
  ('control: untagged words ignored',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),
   [])]]
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)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, words, interior):
    starts = sorted(o[0] for o in objs)
    size_of = {o[0]: o[1] for o in objs}
    alloc = {o[0]: o[2] for o in objs}
    lo = min(starts) if starts else 0
    hi = max(s + size_of[s] for s in starts) if starts else 0
    found = set()
    for w in words:
        if w & 7 != 3:
            continue
        a = w - 3
        if not (lo <= a < hi):
            continue
        i = min(bisect.bisect_left(starts, a), len(starts) - 1)
        s = starts[i]
        if not alloc[s]:
            continue
        if a == s or (interior and a < s + size_of[s]):
            found.add(s)
    return sorted(found)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: tagged start pointers only',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),
   [320, 352]),
  ('interior pointers when allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),
   [320, 352, 416]),
  ('interior pointer rejected when not allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),
   []),
  ('pointers to a free block',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),
   []),
  ('pointer exactly at a later object start',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),
   [416]),
  ('control: untagged words ignored',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),
   [])],
 [('regression: tagged start pointers only',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),
   [576, 608]),
  ('interior pointers when allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),
   [576, 608, 672]),
  ('interior pointer rejected when not allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),
   []),
  ('pointers to a free block',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),
   []),
  ('pointer exactly at a later object start',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),
   [672]),
  ('control: untagged words ignored',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),
   [])],
 [('regression: tagged start pointers only',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),
   [832, 864]),
  ('interior pointers when allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),
   [832, 864, 928]),
  ('interior pointer rejected when not allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),
   []),
  ('pointers to a free block',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),
   []),
  ('pointer exactly at a later object start',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),
   [928]),
  ('control: untagged words ignored',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],
    [1091, 1123, 1090, 1131],
    False),
   [1088, 1120]),
  ('interior pointers when allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),
   [1088, 1120, 1184]),
  ('interior pointer rejected when not allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),
   []),
  ('pointers to a free block',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),
   []),
  ('pointer exactly at a later object start',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),
   [1184]),
  ('control: untagged words ignored',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],
    [1347, 1379, 1346, 1387],
    False),
   [1344, 1376]),
  ('interior pointers when allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),
   [1344, 1376, 1440]),
  ('interior pointer rejected when not allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),
   []),
  ('pointers to a free block',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),
   []),
  ('pointer exactly at a later object start',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),
   [1440]),
  ('control: untagged words ignored',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),
   [])]]
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)

prompt:
References to an object's first word pin the neighbouring object or nothing.

Conservative scanning of machine words. A word whose low three bits are 011 is a tagged heap pointer to address word - 3; all other words are immediates. objs are [start, size, allocated] in any order. A candidate address pins the allocated object whose start equals it, or, when interior pointers are enabled, the allocated object whose [start, start+size) contains it; addresses in gaps, in free blocks or outside the heap pin nothing. Return the sorted starts of pinned objects.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, words, interior):
    starts = sorted(o[0] for o in objs)
    size_of = {o[0]: o[1] for o in objs}
    alloc = {o[0]: o[2] for o in objs}
    lo = min(starts) if starts else 0
    hi = max(s + size_of[s] for s in starts) if starts else 0
    found = set()
    for w in words:
        if w & 7 != 3:
            continue
        a = w - 3
        if not (lo <= a < hi):
            continue
        i = bisect.bisect_right(starts, a) - 1
        s = starts[i]
        if a == s or (interior and a < s + size_of[s]):
            found.add(s)
    return sorted(found)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: tagged start pointers only',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),
   [320, 352]),
  ('interior pointers when allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),
   [320, 352, 416]),
  ('interior pointer rejected when not allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),
   []),
  ('pointers to a free block',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),
   []),
  ('pointer exactly at a later object start',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),
   [416]),
  ('control: untagged words ignored',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),
   [])],
 [('regression: tagged start pointers only',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),
   [576, 608]),
  ('interior pointers when allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),
   [576, 608, 672]),
  ('interior pointer rejected when not allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),
   []),
  ('pointers to a free block',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),
   []),
  ('pointer exactly at a later object start',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),
   [672]),
  ('control: untagged words ignored',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),
   [])],
 [('regression: tagged start pointers only',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),
   [832, 864]),
  ('interior pointers when allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),
   [832, 864, 928]),
  ('interior pointer rejected when not allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),
   []),
  ('pointers to a free block',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),
   []),
  ('pointer exactly at a later object start',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),
   [928]),
  ('control: untagged words ignored',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],
    [1091, 1123, 1090, 1131],
    False),
   [1088, 1120]),
  ('interior pointers when allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),
   [1088, 1120, 1184]),
  ('interior pointer rejected when not allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),
   []),
  ('pointers to a free block',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),
   []),
  ('pointer exactly at a later object start',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),
   [1184]),
  ('control: untagged words ignored',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],
    [1347, 1379, 1346, 1387],
    False),
   [1344, 1376]),
  ('interior pointers when allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),
   [1344, 1376, 1440]),
  ('interior pointer rejected when not allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),
   []),
  ('pointers to a free block',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),
   []),
  ('pointer exactly at a later object start',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),
   [1440]),
  ('control: untagged words ignored',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),
   [])]]
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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, words, interior):
    starts = sorted(o[0] for o in objs)
    size_of = {o[0]: o[1] for o in objs}
    alloc = {o[0]: o[2] for o in objs}
    lo = min(starts) if starts else 0
    hi = max(s + size_of[s] for s in starts) if starts else 0
    found = set()
    for w in words:
        if w & 7 != 3:
            continue
        a = w - 3
        if not (lo <= a < hi):
            continue
        i = bisect.bisect_right(starts, a) - 1
        s = starts[i]
        if not alloc[s] and a == s:
            continue
        if a == s or (interior and a < s + size_of[s]):
            found.add(s)
    return sorted(found)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: tagged start pointers only',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [323, 355, 322, 363], False),
   [320, 352]),
  ('interior pointers when allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427, 339], True),
   [320, 352, 416]),
  ('interior pointer rejected when not allowed',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [363, 427], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [371, 403], True),
   []),
  ('pointers to a free block',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [387, 395], True),
   []),
  ('pointer exactly at a later object start',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [419, 451, 267], False),
   [416]),
  ('control: untagged words ignored',
   ([[416, 32, True], [320, 32, True], [352, 16, True], [384, 16, False]], [320, 352, 416], True),
   [])],
 [('regression: tagged start pointers only',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [579, 611, 578, 619], False),
   [576, 608]),
  ('interior pointers when allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683, 595], True),
   [576, 608, 672]),
  ('interior pointer rejected when not allowed',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [619, 683], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [627, 659], True),
   []),
  ('pointers to a free block',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [643, 651], True),
   []),
  ('pointer exactly at a later object start',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [675, 707, 523], False),
   [672]),
  ('control: untagged words ignored',
   ([[672, 32, True], [576, 32, True], [608, 16, True], [640, 16, False]], [576, 608, 672], True),
   [])],
 [('regression: tagged start pointers only',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [835, 867, 834, 875], False),
   [832, 864]),
  ('interior pointers when allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939, 851], True),
   [832, 864, 928]),
  ('interior pointer rejected when not allowed',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [875, 939], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [883, 915], True),
   []),
  ('pointers to a free block',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [899, 907], True),
   []),
  ('pointer exactly at a later object start',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [931, 963, 779], False),
   [928]),
  ('control: untagged words ignored',
   ([[928, 32, True], [832, 32, True], [864, 16, True], [896, 16, False]], [832, 864, 928], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]],
    [1091, 1123, 1090, 1131],
    False),
   [1088, 1120]),
  ('interior pointers when allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195, 1107], True),
   [1088, 1120, 1184]),
  ('interior pointer rejected when not allowed',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1131, 1195], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1139, 1171], True),
   []),
  ('pointers to a free block',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1155, 1163], True),
   []),
  ('pointer exactly at a later object start',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1187, 1219, 1035], False),
   [1184]),
  ('control: untagged words ignored',
   ([[1184, 32, True], [1088, 32, True], [1120, 16, True], [1152, 16, False]], [1088, 1120, 1184], True),
   [])],
 [('regression: tagged start pointers only',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]],
    [1347, 1379, 1346, 1387],
    False),
   [1344, 1376]),
  ('interior pointers when allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451, 1363], True),
   [1344, 1376, 1440]),
  ('interior pointer rejected when not allowed',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1387, 1451], False),
   []),
  ('one-past-the-end pointer into a gap',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1395, 1427], True),
   []),
  ('pointers to a free block',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1411, 1419], True),
   []),
  ('pointer exactly at a later object start',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1443, 1475, 1291], False),
   [1440]),
  ('control: untagged words ignored',
   ([[1440, 32, True], [1344, 32, True], [1376, 16, True], [1408, 16, False]], [1344, 1376, 1440], True),
   [])]]
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)

prompt:
Stale stack words keep free-list blocks reserved.

Conservative scanning of machine words. A word whose low three bits are 011 is a tagged heap pointer to address word - 3; all other words are immediates. objs are [start, size, allocated] in any order. A candidate address pins the allocated object whose start equals it, or, when interior pointers are enabled, the allocated object whose [start, start+size) contains it; addresses in gaps, in free blocks or outside the heap pin nothing. Return the sorted starts of pinned objects.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(frames, maps, moves):
    out = []
    for f in frames:
        key = f['pc']
        if key not in maps:
            return ['no-stackmap', key]
        m = maps[key]
        old = list(f['slots'])
        slots = list(old)
        for i in range(len(slots)):
            if m['refs'] >> (len(slots) - 1 - i) & 1 and old[i] is not None:
                slots[i] = moves.get(old[i], old[i])
        for dslot, bslot in m['derived']:
            base = old[bslot]
            slots[dslot] = moves.get(base, base) + (old[dslot] - base)
        out.append(slots)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 8, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[5016, 8, 2400, 5032, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3001]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[2000, 5016, 3001]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1989]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2389]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3005]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5016, 3000, 3005]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 12, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 12]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [1, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[1, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 9, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[5032, 9, 2400, 5048, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3002]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[2000, 5032, 3002]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1988]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2388]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3006]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5032, 3000, 3006]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 13, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 13]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [2, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[2, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 10, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[5048, 10, 2400, 5064, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3003]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[2000, 5048, 3003]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1987]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2387]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3007]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5048, 3000, 3007]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 14, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 14]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [3, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[3, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 11, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[5064, 11, 2400, 5080, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3004]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[2000, 5064, 3004]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1986]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2386]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3008]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5064, 3000, 3008]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 15, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 15]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [4, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[4, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 12, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[5080, 12, 2400, 5096, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3005]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[2000, 5080, 3005]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1985]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2385]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3009]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5080, 3000, 3009]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 16, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 16]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [5, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[5, None, 0]])]]
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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(frames, maps, moves):
    out = []
    for f in frames:
        key = f['pc']
        if key not in maps:
            return ['no-stackmap', key]
        m = maps[key]
        old = list(f['slots'])
        slots = list(old)
        for i in range(len(slots)):
            if m['refs'] & (1 << i + 1) and old[i] is not None:
                slots[i] = moves.get(old[i], old[i])
        for dslot, bslot in m['derived']:
            base = old[bslot]
            slots[dslot] = moves.get(base, base) + (old[dslot] - base)
        out.append(slots)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 8, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[5016, 8, 2400, 5032, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3001]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[2000, 5016, 3001]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1989]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2389]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3005]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5016, 3000, 3005]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 12, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 12]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [1, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[1, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 9, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[5032, 9, 2400, 5048, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3002]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[2000, 5032, 3002]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1988]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2388]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3006]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5032, 3000, 3006]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 13, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 13]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [2, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[2, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 10, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[5048, 10, 2400, 5064, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3003]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[2000, 5048, 3003]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1987]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2387]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3007]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5048, 3000, 3007]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 14, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 14]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [3, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[3, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 11, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[5064, 11, 2400, 5080, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3004]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[2000, 5064, 3004]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1986]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2386]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3008]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5064, 3000, 3008]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 15, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 15]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [4, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[4, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 12, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[5080, 12, 2400, 5096, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3005]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[2000, 5080, 3005]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1985]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2385]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3009]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5080, 3000, 3009]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 16, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 16]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [5, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[5, None, 0]])]]
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)

prompt:
Integer slots are relocated as pointers while real reference slots keep stale addresses.

Relocate frame slots after a moving collection. Each frame has a safepoint pc and a slot list; maps[pc] gives a reference bitmask (bit i set means slot i holds a reference; bit 0 is slot 0) and derived pointers [derived_slot, base_slot], which hold base + offset and are not in the mask. moves maps old object addresses to new ones (unmoved objects are absent or map to themselves). Reference slots are relocated, derived slots become new base + (old derived - old base), and every other slot is left untouched. A pc without a map returns ["no-stackmap", pc].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(frames, maps, moves):
    out = []
    for f in frames:
        key = f['pc']
        if key not in maps:
            return ['no-stackmap', key]
        m = maps[key]
        old = list(f['slots'])
        slots = list(old)
        for i in range(len(slots)):
            if m['refs'] >> i & 1 and old[i] is not None:
                slots[i] = moves.get(old[i], old[i])
        for dslot, bslot in m['derived']:
            base = slots[bslot]
            slots[dslot] = moves.get(base, base) + (old[dslot] - base)
        out.append(slots)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 8, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[5016, 8, 2400, 5032, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3001]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[2000, 5016, 3001]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1989]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2389]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3005]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5016, 3000, 3005]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 12, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 12]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [1, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[1, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 9, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[5032, 9, 2400, 5048, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3002]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[2000, 5032, 3002]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1988]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2388]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3006]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5032, 3000, 3006]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 13, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 13]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [2, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[2, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 10, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[5048, 10, 2400, 5064, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3003]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[2000, 5048, 3003]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1987]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2387]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3007]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5048, 3000, 3007]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 14, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 14]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [3, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[3, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 11, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[5064, 11, 2400, 5080, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3004]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[2000, 5064, 3004]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1986]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2386]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3008]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5064, 3000, 3008]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 15, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 15]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [4, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[4, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 12, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[5080, 12, 2400, 5096, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3005]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[2000, 5080, 3005]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1985]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2385]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3009]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5080, 3000, 3009]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 16, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 16]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [5, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[5, None, 0]])]]
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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(frames, maps, moves):
    out = []
    for f in frames:
        key = f['pc']
        if key not in maps:
            return ['no-stackmap', key]
        m = maps[key]
        old = list(f['slots'])
        slots = list(old)
        for i in range(len(slots)):
            if m['refs'] >> i & 1 and old[i] is not None:
                slots[i] = moves.get(old[i], old[i])
        for dslot, bslot in m['derived']:
            base = old[dslot]
            slots[dslot] = moves.get(base, base) + (old[dslot] - base)
        out.append(slots)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 8, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[5016, 8, 2400, 5032, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3001]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[2000, 5016, 3001]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1989]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2389]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3005]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5016, 3000, 3005]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 12, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 12]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [1, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[1, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 9, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[5032, 9, 2400, 5048, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3002]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[2000, 5032, 3002]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1988]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2388]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3006]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5032, 3000, 3006]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 13, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 13]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [2, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[2, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 10, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[5048, 10, 2400, 5064, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3003]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[2000, 5048, 3003]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1987]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2387]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3007]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5048, 3000, 3007]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 14, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 14]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [3, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[3, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 11, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[5064, 11, 2400, 5080, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3004]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[2000, 5064, 3004]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1986]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2386]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3008]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5064, 3000, 3008]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 15, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 15]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [4, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[4, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 12, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[5080, 12, 2400, 5096, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3005]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[2000, 5080, 3005]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1985]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2385]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3009]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5080, 3000, 3009]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 16, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 16]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [5, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[5, None, 0]])]]
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)

prompt:
Interior pointers into moved objects end up offset by the distance the object moved.

Relocate frame slots after a moving collection. Each frame has a safepoint pc and a slot list; maps[pc] gives a reference bitmask (bit i set means slot i holds a reference; bit 0 is slot 0) and derived pointers [derived_slot, base_slot], which hold base + offset and are not in the mask. moves maps old object addresses to new ones (unmoved objects are absent or map to themselves). Reference slots are relocated, derived slots become new base + (old derived - old base), and every other slot is left untouched. A pc without a map returns ["no-stackmap", pc].

split: open-access


source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(frames, maps, moves):
    out = []
    for f in frames:
        key = f['pc']
        if key not in maps:
            return ['no-stackmap', key]
        m = maps[key]
        old = list(f['slots'])
        slots = list(old)
        for i in range(len(slots)):
            if (m['refs'] >> i & 1 or old[i] in moves) and old[i] is not None:
                slots[i] = moves.get(old[i], old[i])
        for dslot, bslot in m['derived']:
            base = old[bslot]
            slots[dslot] = moves.get(base, base) + (old[dslot] - base)
        out.append(slots)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 8, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[5016, 8, 2400, 5032, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3001]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[2000, 5016, 3001]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1989]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2389]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3005]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5016, 3000, 3005]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 12, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 12]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [1, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5016, 2000: 2400, 3000: 3000}),
   [[1, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 9, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[5032, 9, 2400, 5048, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3002]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[2000, 5032, 3002]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1988]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2388]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3006]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5032, 3000, 3006]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 13, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 13]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [2, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5032, 2000: 2400, 3000: 3000}),
   [[2, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 10, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[5048, 10, 2400, 5064, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3003]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[2000, 5048, 3003]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1987]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2387]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3007]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5048, 3000, 3007]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 14, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 14]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [3, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5048, 2000: 2400, 3000: 3000}),
   [[3, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 11, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[5064, 11, 2400, 5080, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3004]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[2000, 5064, 3004]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1986]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2386]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3008]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5064, 3000, 3008]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 15, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 15]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [4, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5064, 2000: 2400, 3000: 3000}),
   [[4, None, 0]])],
 [('regression: references, integers and derived pointers',
   ([{'pc': 10, 'slots': [1000, 12, 2000, 1016, 1000, 1992]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[5080, 12, 2400, 5096, 1000, 2392]]),
  ('integer that looks like a moved address',
   ([{'pc': 20, 'slots': [2000, 1000, 3005]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[2000, 5080, 3005]]),
  ('derived pointer below its base',
   ([{'pc': 30, 'slots': [None, 2000, 1985]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[None, 2400, 2385]]),
  ('several frames',
   ([{'pc': 20, 'slots': [5, 2000, 9]}, {'pc': 30, 'slots': [1000, 3000, 3009]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[5, 2400, 9], [5080, 3000, 3009]]),
  ('missing stack map',
   ([{'pc': 20, 'slots': [1, 2, 3]}, {'pc': 16, 'slots': []}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   ['no-stackmap', 16]),
  ('control: null reference slots',
   ([{'pc': 20, 'slots': [5, None, 0]}],
    {10: {'derived': [[3, 0], [5, 2]], 'refs': 5},
     20: {'derived': [], 'refs': 2},
     30: {'derived': [[2, 1]], 'refs': 3}},
    {1000: 5080, 2000: 2400, 3000: 3000}),
   [[5, None, 0]])]]
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)

prompt:
Integers that happen to equal an old object address are silently rewritten.

Relocate frame slots after a moving collection. Each frame has a safepoint pc and a slot list; maps[pc] gives a reference bitmask (bit i set means slot i holds a reference; bit 0 is slot 0) and derived pointers [derived_slot, base_slot], which hold base + offset and are not in the mask. moves maps old object addresses to new ones (unmoved objects are absent or map to themselves). Reference slots are relocated, derived slots become new base + (old derived - old base), and every other slot is left untouched. A pc without a map returns ["no-stackmap", pc].

split: open-access