{"abstract":"Addresses at the beginning of a card are attributed to the next object.","category":"Garbage collector invariants","checks":6,"contract":"A contiguous heap of [start, size] objects is covered by cards of the given size. For each card the table stores the offset of the first object that starts inside the card; a card with no object start that is covered by an object from card c stores -(k - c), a direct back-skip to that card. To find the object containing address q: from q's card follow back-skips; if the card's first start lies after q, move to the previous card; then walk objects forward until one contains q (an entry that does not land on an object start yields corrupt-table). Return the table and the owner start for each query.","evaluation_group":"w2-garbage-collector-invariants-block-offset-table","failed_approach":"Returning no owner abandons addresses that belong to an object from an earlier card.","family":"w2-garbage-collector-invariants-block-offset-table-start-after-query","id":"FA-90701","implementations":{"attempt":{"sha256":"e6a64f879561cd3723bad06479de83e63ff7276af9e6dec8ba5caaab7d05bdea","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(objs, card, heap_end, queries):\n    size_of = {s: z for s, z in objs}\n    ncards = (heap_end + card - 1) // card\n    table = [None] * ncards\n    for start, size in sorted(objs):\n        c = start // card\n        if table[c] is None or table[c] < 0:\n            table[c] = start - c * card\n        last = (start + size - 1) // card\n        for k in range(c + 1, min(last, ncards - 1) + 1):\n            if table[k] is None:\n                table[k] = -(k - c)\n    def owner(q):\n        c = q // card\n        while c >= 0:\n            e = table[c]\n            if e is None:\n                return None\n            if e < 0:\n                c += e\n                continue\n            a = c * card + e\n            if a not in size_of:\n                return 'corrupt-table'\n            if a > q:\n                return None\n            while a + size_of[a] <= q:\n                a += size_of[a]\n                if a not in size_of:\n                    return None\n            return a\n        return None\n    return {'table': table, 'owners': [owner(q) for q in queries]}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: owners across spanning objects',\n   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),\n   {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),\n  ('addresses just before a card-internal start',\n   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],\n    64,\n    472,\n    [47, 147, 167, 367, 391, 407]),\n   {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),\n  ('first address of every card',\n   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],\n    64,\n    472,\n    [0, 64, 128, 192, 256, 320, 384, 448]),\n   {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),\n  ('object ends and starts',\n   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],\n    64,\n    472,\n    [147, 148, 168, 391, 408]),\n   {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),\n  ('smaller cards',\n   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),\n   {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),\n  ('control: single object heap',\n   ([[0, 264]], 64, 264, [0, 100, 255]),\n   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],\n [('regression: owners across spanning objects',\n   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),\n   {'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),\n  ('addresses just before a card-internal start',\n   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],\n    64,\n    480,\n    [55, 155, 175, 375, 399, 415]),\n   {'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),\n  ('first address of every card',\n   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],\n    64,\n    480,\n    [0, 64, 128, 192, 256, 320, 384, 448]),\n   {'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),\n  ('object ends and starts',\n   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],\n    64,\n    480,\n    [155, 156, 176, 399, 416]),\n   {'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),\n  ('smaller cards',\n   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),\n   {'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),\n  ('control: single object heap',\n   ([[0, 272]], 64, 272, [0, 100, 255]),\n   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],\n [('regression: owners across spanning objects',\n   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),\n   {'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),\n  ('addresses just before a card-internal start',\n   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],\n    64,\n    488,\n    [63, 163, 183, 383, 407, 423]),\n   {'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),\n  ('first address of every card',\n   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],\n    64,\n    488,\n    [0, 64, 128, 192, 256, 320, 384, 448]),\n   {'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),\n  ('object ends and starts',\n   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],\n    64,\n    488,\n    [163, 164, 184, 407, 424]),\n   {'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),\n  ('smaller cards',\n   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),\n   {'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),\n  ('control: single object heap',\n   ([[0, 280]], 64, 280, [0, 100, 255]),\n   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],\n [('regression: owners across spanning objects',\n   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),\n   {'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),\n  ('addresses just before a card-internal start',\n   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],\n    64,\n    496,\n    [71, 171, 191, 391, 415, 431]),\n   {'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),\n  ('first address of every card',\n   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],\n    64,\n    496,\n    [0, 64, 128, 192, 256, 320, 384, 448]),\n   {'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),\n  ('object ends and starts',\n   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],\n    64,\n    496,\n    [171, 172, 192, 415, 432]),\n   {'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),\n  ('smaller cards',\n   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),\n   {'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),\n  ('control: single object heap',\n   ([[0, 288]], 64, 288, [0, 100, 255]),\n   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],\n [('regression: owners across spanning objects',\n   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),\n   {'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),\n  ('addresses just before a card-internal start',\n   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],\n    64,\n    504,\n    [79, 179, 199, 399, 423, 439]),\n   {'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),\n  ('first address of every card',\n   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],\n    64,\n    504,\n    [0, 64, 128, 192, 256, 320, 384, 448]),\n   {'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),\n  ('object ends and starts',\n   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],\n    64,\n    504,\n    [179, 180, 200, 423, 440]),\n   {'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),\n  ('smaller cards',\n   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),\n   {'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),\n  ('control: single object heap',\n   ([[0, 296]], 64, 296, [0, 100, 255]),\n   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"72538ea4848a2a6da8fe02324943e7d937ff73bf7d2e30da399310b40fa5f5ba","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(objs, card, heap_end, queries):\n    size_of = {s: z for s, z in objs}\n    ncards = (heap_end + card - 1) // card\n    table = [None] * ncards\n    for start, size in sorted(objs):\n        c = start // card\n        if table[c] is None or table[c] < 0:\n            table[c] = start - c * card\n        last = (start + size - 1) // card\n        for k in range(c + 1, min(last, ncards - 1) + 1):\n            if table[k] is None:\n                table[k] = -(k - c)\n    def owner(q):\n        c = q // card\n        while c >= 0:\n            e = table[c]\n            if e is None:\n                return None\n            if e < 0:\n                c += e\n                continue\n            a = c * card + e\n            if a not in size_of:\n                return 'corrupt-table'\n            if a > q:\n                return a\n            while a + size_of[a] <= q:\n                a += size_of[a]\n                if a not in size_of:\n                    return None\n            return a\n        return None\n    return {'table': table, 'owners': [owner(q) for q in queries]}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: owners across spanning objects',\n   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),\n   {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),\n  ('addresses just before a card-internal start',\n   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],\n    64,\n    472,\n    [47, 147, 167, 367, 391, 407]),\n   {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),\n  ('first address of every card',\n   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],\n    64,\n    472,\n    [0, 64, 128, 192, 256, 320, 384, 448]),\n   {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),\n  ('object ends and starts',\n   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],\n    64,\n    472,\n    [147, 148, 168, 391, 408]),\n   {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),\n  ('smaller cards',\n   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),\n   {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),\n  ('control: single object heap',\n   ([[0, 264]], 64, 264, [0, 100, 255]),\n   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],\n [('regression: owners across spanning objects',\n   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),\n   {'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),\n  ('addresses just before a card-internal start',\n   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],\n    64,\n    480,\n    [55, 155, 175, 375, 399, 415]),\n   {'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),\n  ('first address of every card',\n   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],\n    64,\n    480,\n    [0, 64, 128, 192, 256, 320, 384, 448]),\n   {'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),\n  ('object ends and starts',\n   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],\n    64,\n    480,\n    [155, 156, 176, 399, 416]),\n   {'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),\n  ('smaller cards',\n   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),\n   {'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),\n  ('control: single object heap',\n   ([[0, 272]], 64, 272, [0, 100, 255]),\n   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],\n [('regression: owners across spanning objects',\n   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),\n   {'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),\n  ('addresses just before a card-internal start',\n   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],\n    64,\n    488,\n    [63, 163, 183, 383, 407, 423]),\n   {'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),\n  ('first address of every card',\n   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],\n    64,\n    488,\n    [0, 64, 128, 192, 256, 320, 384, 448]),\n   {'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),\n  ('object ends and starts',\n   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],\n    64,\n    488,\n    [163, 164, 184, 407, 424]),\n   {'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),\n  ('smaller cards',\n   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),\n   {'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),\n  ('control: single object heap',\n   ([[0, 280]], 64, 280, [0, 100, 255]),\n   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],\n [('regression: owners across spanning objects',\n   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),\n   {'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),\n  ('addresses just before a card-internal start',\n   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],\n    64,\n    496,\n    [71, 171, 191, 391, 415, 431]),\n   {'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),\n  ('first address of every card',\n   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],\n    64,\n    496,\n    [0, 64, 128, 192, 256, 320, 384, 448]),\n   {'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),\n  ('object ends and starts',\n   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],\n    64,\n    496,\n    [171, 172, 192, 415, 432]),\n   {'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),\n  ('smaller cards',\n   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),\n   {'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),\n  ('control: single object heap',\n   ([[0, 288]], 64, 288, [0, 100, 255]),\n   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],\n [('regression: owners across spanning objects',\n   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),\n   {'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),\n  ('addresses just before a card-internal start',\n   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],\n    64,\n    504,\n    [79, 179, 199, 399, 423, 439]),\n   {'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),\n  ('first address of every card',\n   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],\n    64,\n    504,\n    [0, 64, 128, 192, 256, 320, 384, 448]),\n   {'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),\n  ('object ends and starts',\n   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],\n    64,\n    504,\n    [179, 180, 200, 423, 440]),\n   {'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),\n  ('smaller cards',\n   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),\n   {'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),\n  ('control: single object heap',\n   ([[0, 296]], 64, 296, [0, 100, 255]),\n   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"429b796ebe6a29dc46c0d23387dc8dedec0954e5c693f7ebd64e4beef84bcdce","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(objs, card, heap_end, queries):\n    size_of = {s: z for s, z in objs}\n    ncards = (heap_end + card - 1) // card\n    table = [None] * ncards\n    for start, size in sorted(objs):\n        c = start // card\n        if table[c] is None or table[c] < 0:\n            table[c] = start - c * card\n        last = (start + size - 1) // card\n        for k in range(c + 1, min(last, ncards - 1) + 1):\n            if table[k] is None:\n                table[k] = -(k - c)\n    def owner(q):\n        c = q // card\n        while c >= 0:\n            e = table[c]\n            if e is None:\n                return None\n            if e < 0:\n                c += e\n                continue\n            a = c * card + e\n            if a not in size_of:\n                return 'corrupt-table'\n            if a > q:\n                c -= 1\n                continue\n            while a + size_of[a] <= q:\n                a += size_of[a]\n                if a not in size_of:\n                    return None\n            return a\n        return None\n    return {'table': table, 'owners': [owner(q) for q in queries]}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: owners across spanning objects',\n   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),\n   {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),\n  ('addresses just before a card-internal start',\n   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],\n    64,\n    472,\n    [47, 147, 167, 367, 391, 407]),\n   {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),\n  ('first address of every card',\n   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],\n    64,\n    472,\n    [0, 64, 128, 192, 256, 320, 384, 448]),\n   {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),\n  ('object ends and starts',\n   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],\n    64,\n    472,\n    [147, 148, 168, 391, 408]),\n   {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),\n  ('smaller cards',\n   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),\n   {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),\n  ('control: single object heap',\n   ([[0, 264]], 64, 264, [0, 100, 255]),\n   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],\n [('regression: owners across spanning objects',\n   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),\n   {'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),\n  ('addresses just before a card-internal start',\n   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],\n    64,\n    480,\n    [55, 155, 175, 375, 399, 415]),\n   {'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),\n  ('first address of every card',\n   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],\n    64,\n    480,\n    [0, 64, 128, 192, 256, 320, 384, 448]),\n   {'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),\n  ('object ends and starts',\n   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],\n    64,\n    480,\n    [155, 156, 176, 399, 416]),\n   {'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),\n  ('smaller cards',\n   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),\n   {'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),\n  ('control: single object heap',\n   ([[0, 272]], 64, 272, [0, 100, 255]),\n   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],\n [('regression: owners across spanning objects',\n   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),\n   {'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),\n  ('addresses just before a card-internal start',\n   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],\n    64,\n    488,\n    [63, 163, 183, 383, 407, 423]),\n   {'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),\n  ('first address of every card',\n   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],\n    64,\n    488,\n    [0, 64, 128, 192, 256, 320, 384, 448]),\n   {'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),\n  ('object ends and starts',\n   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],\n    64,\n    488,\n    [163, 164, 184, 407, 424]),\n   {'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),\n  ('smaller cards',\n   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),\n   {'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),\n  ('control: single object heap',\n   ([[0, 280]], 64, 280, [0, 100, 255]),\n   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],\n [('regression: owners across spanning objects',\n   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),\n   {'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),\n  ('addresses just before a card-internal start',\n   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],\n    64,\n    496,\n    [71, 171, 191, 391, 415, 431]),\n   {'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),\n  ('first address of every card',\n   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],\n    64,\n    496,\n    [0, 64, 128, 192, 256, 320, 384, 448]),\n   {'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),\n  ('object ends and starts',\n   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],\n    64,\n    496,\n    [171, 172, 192, 415, 432]),\n   {'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),\n  ('smaller cards',\n   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),\n   {'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),\n  ('control: single object heap',\n   ([[0, 288]], 64, 288, [0, 100, 255]),\n   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],\n [('regression: owners across spanning objects',\n   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),\n   {'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),\n  ('addresses just before a card-internal start',\n   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],\n    64,\n    504,\n    [79, 179, 199, 399, 423, 439]),\n   {'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),\n  ('first address of every card',\n   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],\n    64,\n    504,\n    [0, 64, 128, 192, 256, 320, 384, 448]),\n   {'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),\n  ('object ends and starts',\n   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],\n    64,\n    504,\n    [179, 180, 200, 423, 440]),\n   {'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),\n  ('smaller cards',\n   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),\n   {'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),\n  ('control: single object heap',\n   ([[0, 296]], 64, 296, [0, 100, 255]),\n   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"A deterministic, bounded teaching model of one garbage-collector mechanism with stipulated rules; it is not a production collector and claims no conformance to any particular runtime. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-garbage-collector-invariants-block-offset-table-start-after-query","generated_at":"2026-09-29T14:51:29.099090+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Card scanning needs to locate object starts quickly; a stale or wrong table misparses the heap.","repair":"Move to the previous card and resolve from there.","root_cause":"When the card's first object starts beyond the query, that object is returned instead of searching the previous card.","sha256":"32ff2fcb98c7c7b29e3d56d8d9ddd5b390f0dcf9a5798bb7fee04dfffb92ae32","title":"Block offset table: first object in the card returned even when it starts after the address · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":41.797,"exit_code":1,"observations":[{"actual":{"owners":[48,168,368],"table":[0,-1,20,-1,-2,48,8,-1]},"check":"regression: owners across spanning objects","expected":{"owners":[48,168,368],"table":[0,-1,20,-1,-2,48,8,-1]},"passed":true},{"actual":{"owners":[0,null,148,null,null,392],"table":[0,-1,20,-1,-2,48,8,-1]},"check":"addresses just before a card-internal start","expected":{"owners":[0,48,148,168,368,392],"table":[0,-1,20,-1,-2,48,8,-1]},"passed":false},{"actual":{"owners":[0,48,null,168,168,null,null,408],"table":[0,-1,20,-1,-2,48,8,-1]},"check":"first address of every card","expected":{"owners":[0,48,48,168,168,168,368,408],"table":[0,-1,20,-1,-2,48,8,-1]},"passed":false},{"actual":{"owners":[null,148,168,null,408],"table":[0,-1,20,-1,-2,48,8,-1]},"check":"object ends and starts","expected":{"owners":[48,148,168,368,408],"table":[0,-1,20,-1,-2,48,8,-1]},"passed":false},{"actual":{"owners":[168,408,0],"table":[0,16,-1,-2,20,8,-1,-2,-3,-4,-5,16,8,-1,-2]},"check":"smaller cards","expected":{"owners":[168,408,0],"table":[0,16,-1,-2,20,8,-1,-2,-3,-4,-5,16,8,-1,-2]},"passed":true},{"actual":{"owners":[0,0,0],"table":[0,-1,-2,-3,-4]},"check":"control: single object heap","expected":{"owners":[0,0,0],"table":[0,-1,-2,-3,-4]},"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: owners across spanning objects\", \"actual\": {\"table\": [0, -1, 20, -1, -2, 48, 8, -1], \"owners\": [48, 168, 368]}, \"expected\": {\"owners\": [48, 168, 368], \"table\": [0, -1, 20, -1, -2, 48, 8, -1]}, \"passed\": true}, {\"check\": \"addresses just before a card-internal start\", \"actual\": {\"table\": [0, -1, 20, -1, -2, 48, 8, -1], \"owners\": [0, null, 148, null, null, 392]}, \"expected\": {\"owners\": [0, 48, 148, 168, 368, 392], \"table\": [0, -1, 20, -1, -2, 48, 8, -1]}, \"passed\": false}, {\"check\": \"first address of every card\", \"actual\": {\"table\": [0, -1, 20, -1, -2, 48, 8, -1], \"owners\": [0, 48, null, 168, 168, null, null, 408]}, \"expected\": {\"owners\": [0, 48, 48, 168, 168, 168, 368, 408], \"table\": [0, -1, 20, -1, -2, 48, 8, -1]}, \"passed\": false}, {\"check\": \"object ends and starts\", \"actual\": {\"table\": [0, -1, 20, -1, -2, 48, 8, -1], \"owners\": [null, 148, 168, null, 408]}, \"expected\": {\"owners\": [48, 148, 168, 368, 408], \"table\": [0, -1, 20, -1, -2, 48, 8, -1]}, \"passed\": false}, {\"check\": \"smaller cards\", \"actual\": {\"table\": [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2], \"owners\": [168, 408, 0]}, \"expected\": {\"owners\": [168, 408, 0], \"table\": [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}, \"passed\": true}, {\"check\": \"control: single object heap\", \"actual\": {\"table\": [0, -1, -2, -3, -4], \"owners\": [0, 0, 0]}, \"expected\": {\"owners\": [0, 0, 0], \"table\": [0, -1, -2, -3, -4]}, \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":39.324,"exit_code":1,"observations":[{"actual":{"owners":[48,168,368],"table":[0,-1,20,-1,-2,48,8,-1]},"check":"regression: owners across spanning objects","expected":{"owners":[48,168,368],"table":[0,-1,20,-1,-2,48,8,-1]},"passed":true},{"actual":{"owners":[0,148,148,368,392,392],"table":[0,-1,20,-1,-2,48,8,-1]},"check":"addresses just before a card-internal start","expected":{"owners":[0,48,148,168,368,392],"table":[0,-1,20,-1,-2,48,8,-1]},"passed":false},{"actual":{"owners":[0,48,148,168,168,368,392,408],"table":[0,-1,20,-1,-2,48,8,-1]},"check":"first address of every card","expected":{"owners":[0,48,48,168,168,168,368,408],"table":[0,-1,20,-1,-2,48,8,-1]},"passed":false},{"actual":{"owners":[148,148,168,392,408],"table":[0,-1,20,-1,-2,48,8,-1]},"check":"object ends and starts","expected":{"owners":[48,148,168,368,408],"table":[0,-1,20,-1,-2,48,8,-1]},"passed":false},{"actual":{"owners":[168,408,0],"table":[0,16,-1,-2,20,8,-1,-2,-3,-4,-5,16,8,-1,-2]},"check":"smaller cards","expected":{"owners":[168,408,0],"table":[0,16,-1,-2,20,8,-1,-2,-3,-4,-5,16,8,-1,-2]},"passed":true},{"actual":{"owners":[0,0,0],"table":[0,-1,-2,-3,-4]},"check":"control: single object heap","expected":{"owners":[0,0,0],"table":[0,-1,-2,-3,-4]},"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: owners across spanning objects\", \"actual\": {\"table\": [0, -1, 20, -1, -2, 48, 8, -1], \"owners\": [48, 168, 368]}, \"expected\": {\"owners\": [48, 168, 368], \"table\": [0, -1, 20, -1, -2, 48, 8, -1]}, \"passed\": true}, {\"check\": \"addresses just before a card-internal start\", \"actual\": {\"table\": [0, -1, 20, -1, -2, 48, 8, -1], \"owners\": [0, 148, 148, 368, 392, 392]}, \"expected\": {\"owners\": [0, 48, 148, 168, 368, 392], \"table\": [0, -1, 20, -1, -2, 48, 8, -1]}, \"passed\": false}, {\"check\": \"first address of every card\", \"actual\": {\"table\": [0, -1, 20, -1, -2, 48, 8, -1], \"owners\": [0, 48, 148, 168, 168, 368, 392, 408]}, \"expected\": {\"owners\": [0, 48, 48, 168, 168, 168, 368, 408], \"table\": [0, -1, 20, -1, -2, 48, 8, -1]}, \"passed\": false}, {\"check\": \"object ends and starts\", \"actual\": {\"table\": [0, -1, 20, -1, -2, 48, 8, -1], \"owners\": [148, 148, 168, 392, 408]}, \"expected\": {\"owners\": [48, 148, 168, 368, 408], \"table\": [0, -1, 20, -1, -2, 48, 8, -1]}, \"passed\": false}, {\"check\": \"smaller cards\", \"actual\": {\"table\": [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2], \"owners\": [168, 408, 0]}, \"expected\": {\"owners\": [168, 408, 0], \"table\": [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}, \"passed\": true}, {\"check\": \"control: single object heap\", \"actual\": {\"table\": [0, -1, -2, -3, -4], \"owners\": [0, 0, 0]}, \"expected\": {\"owners\": [0, 0, 0], \"table\": [0, -1, -2, -3, -4]}, \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":39.98,"exit_code":0,"observations":[{"actual":{"owners":[48,168,368],"table":[0,-1,20,-1,-2,48,8,-1]},"check":"regression: owners across spanning objects","expected":{"owners":[48,168,368],"table":[0,-1,20,-1,-2,48,8,-1]},"passed":true},{"actual":{"owners":[0,48,148,168,368,392],"table":[0,-1,20,-1,-2,48,8,-1]},"check":"addresses just before a card-internal start","expected":{"owners":[0,48,148,168,368,392],"table":[0,-1,20,-1,-2,48,8,-1]},"passed":true},{"actual":{"owners":[0,48,48,168,168,168,368,408],"table":[0,-1,20,-1,-2,48,8,-1]},"check":"first address of every card","expected":{"owners":[0,48,48,168,168,168,368,408],"table":[0,-1,20,-1,-2,48,8,-1]},"passed":true},{"actual":{"owners":[48,148,168,368,408],"table":[0,-1,20,-1,-2,48,8,-1]},"check":"object ends and starts","expected":{"owners":[48,148,168,368,408],"table":[0,-1,20,-1,-2,48,8,-1]},"passed":true},{"actual":{"owners":[168,408,0],"table":[0,16,-1,-2,20,8,-1,-2,-3,-4,-5,16,8,-1,-2]},"check":"smaller cards","expected":{"owners":[168,408,0],"table":[0,16,-1,-2,20,8,-1,-2,-3,-4,-5,16,8,-1,-2]},"passed":true},{"actual":{"owners":[0,0,0],"table":[0,-1,-2,-3,-4]},"check":"control: single object heap","expected":{"owners":[0,0,0],"table":[0,-1,-2,-3,-4]},"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: owners across spanning objects\", \"actual\": {\"table\": [0, -1, 20, -1, -2, 48, 8, -1], \"owners\": [48, 168, 368]}, \"expected\": {\"owners\": [48, 168, 368], \"table\": [0, -1, 20, -1, -2, 48, 8, -1]}, \"passed\": true}, {\"check\": \"addresses just before a card-internal start\", \"actual\": {\"table\": [0, -1, 20, -1, -2, 48, 8, -1], \"owners\": [0, 48, 148, 168, 368, 392]}, \"expected\": {\"owners\": [0, 48, 148, 168, 368, 392], \"table\": [0, -1, 20, -1, -2, 48, 8, -1]}, \"passed\": true}, {\"check\": \"first address of every card\", \"actual\": {\"table\": [0, -1, 20, -1, -2, 48, 8, -1], \"owners\": [0, 48, 48, 168, 168, 168, 368, 408]}, \"expected\": {\"owners\": [0, 48, 48, 168, 168, 168, 368, 408], \"table\": [0, -1, 20, -1, -2, 48, 8, -1]}, \"passed\": true}, {\"check\": \"object ends and starts\", \"actual\": {\"table\": [0, -1, 20, -1, -2, 48, 8, -1], \"owners\": [48, 148, 168, 368, 408]}, \"expected\": {\"owners\": [48, 148, 168, 368, 408], \"table\": [0, -1, 20, -1, -2, 48, 8, -1]}, \"passed\": true}, {\"check\": \"smaller cards\", \"actual\": {\"table\": [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2], \"owners\": [168, 408, 0]}, \"expected\": {\"owners\": [168, 408, 0], \"table\": [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}, \"passed\": true}, {\"check\": \"control: single object heap\", \"actual\": {\"table\": [0, -1, -2, -3, -4], \"owners\": [0, 0, 0]}, \"expected\": {\"owners\": [0, 0, 0], \"table\": [0, -1, -2, -3, -4]}, \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}