{"abstract":"A branch pushed out of range by another branch widening stays short and wraps.","category":"Bytecode virtual machines","checks":7,"contract":"Assemble [\"label\", name], [\"data\", nbytes], [\"jmp\", label], [\"jz\", label]. Branches start in the short form (2 bytes, signed 8-bit displacement from the end of the instruction, valid -128..127). A short branch whose displacement does not fit is widened (jmp.w 3 bytes, jz.w 4 bytes) and addresses are recomputed until no branch changes (branches never shrink). Report duplicate or undefined labels; otherwise return each branch as [address, mnemonic, displacement from its own end] and the total size.","evaluation_group":"w2-bytecode-virtual-machines-branch-relaxation-assembler","failed_approach":"Allowing a second pass still misses cascades that need three rounds.","family":"w2-bytecode-virtual-machines-branch-relaxation-assembler-fixpoint-iteration","id":"FA-90151","implementations":{"attempt":{"sha256":"ecdfad005bc2efd574dfa3e0d876f1c3119661ca839e286f89dae85b9e0acbef","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(prog):\n    labels_seen = set()\n    for ins in prog:\n        if ins[0] == 'label':\n            if ins[1] in labels_seen:\n                return ['duplicate-label', ins[1]]\n            labels_seen.add(ins[1])\n    for ins in prog:\n        if ins[0] in ('jmp', 'jz') and ins[1] not in labels_seen:\n            return ['undefined-label', ins[1]]\n    long_form = set()\n    def size(i, ins):\n        if i in long_form:\n            return 4 if ins[0] == 'jz' else 3\n        return 2\n    rounds = 0\n    while True:\n        rounds += 1\n        addr = 0\n        addrs = []\n        where = {}\n        for i, ins in enumerate(prog):\n            addrs.append(addr)\n            if ins[0] == 'label':\n                where[ins[1]] = addr\n            elif ins[0] == 'data':\n                addr += ins[1]\n            else:\n                addr += size(i, ins)\n        changed = False\n        for i, ins in enumerate(prog):\n            if ins[0] in ('jmp', 'jz') and i not in long_form:\n                off = where[ins[1]] - (addrs[i] + 2)\n                if off < -128 or off > 127:\n                    long_form.add(i)\n                    changed = True\n        if not changed or rounds >= 2:\n            break\n    out = []\n    for i, ins in enumerate(prog):\n        if ins[0] in ('jmp', 'jz'):\n            suffix = '.w' if i in long_form else ''\n            out.append([addrs[i], ins[0] + suffix, where[ins[1]] - (addrs[i] + size(i, ins))])\n    return {'branches': out, 'size': addr}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: three-step widening cascade',\n   ([['data', 1],\n     ['jmp', 'A'],\n     ['data', 10],\n     ['jz', 'B'],\n     ['data', 115],\n     ['label', 'A'],\n     ['jmp', 'C'],\n     ['data', 10],\n     ['label', 'B'],\n     ['data', 118],\n     ['label', 'C'],\n     ['data', 1]],),\n   {'branches': [[1, 'jmp.w', 129], [14, 'jz.w', 128], [133, 'jmp.w', 128]], 'size': 265}),\n  ('backward branch exactly -128 stays short',\n   ([['label', 'top'], ['data', 126], ['jz', 'top'], ['data', 1], ['jmp', 'top']],),\n   {'branches': [[126, 'jz', -128], [129, 'jmp.w', -132]], 'size': 132}),\n  ('forward branch just around the short limit',\n   ([['data', 1], ['jmp', 'e'], ['data', 127], ['label', 'e'], ['jz', 'f'], ['data', 128], ['label', 'f']],),\n   {'branches': [[1, 'jmp', 127], [130, 'jz.w', 128]], 'size': 262}),\n  ('wide conditional branch is four bytes',\n   ([['jz', 'x'], ['data', 201], ['label', 'x'], ['jmp', 'x']],),\n   {'branches': [[0, 'jz.w', 201], [205, 'jmp', -2]], 'size': 207}),\n  ('short branches to adjacent labels',\n   ([['jz', 'a'], ['label', 'a'], ['data', 1], ['jmp', 'a']],),\n   {'branches': [[0, 'jz', 0], [3, 'jmp', -3]], 'size': 5}),\n  ('duplicate label', ([['label', 'a'], ['data', 1], ['label', 'a']],), ['duplicate-label', 'a']),\n  ('undefined label', ([['jmp', 'nowhere'], ['data', 1]],), ['undefined-label', 'nowhere'])],\n [('regression: three-step widening cascade',\n   ([['data', 2],\n     ['jmp', 'A'],\n     ['data', 10],\n     ['jz', 'B'],\n     ['data', 115],\n     ['label', 'A'],\n     ['jmp', 'C'],\n     ['data', 10],\n     ['label', 'B'],\n     ['data', 118],\n     ['label', 'C'],\n     ['data', 1]],),\n   {'branches': [[2, 'jmp.w', 129], [15, 'jz.w', 128], [134, 'jmp.w', 128]], 'size': 266}),\n  ('backward branch exactly -128 stays short',\n   ([['label', 'top'], ['data', 126], ['jz', 'top'], ['data', 2], ['jmp', 'top']],),\n   {'branches': [[126, 'jz', -128], [130, 'jmp.w', -133]], 'size': 133}),\n  ('forward branch just around the short limit',\n   ([['data', 2], ['jmp', 'e'], ['data', 127], ['label', 'e'], ['jz', 'f'], ['data', 128], ['label', 'f']],),\n   {'branches': [[2, 'jmp', 127], [131, 'jz.w', 128]], 'size': 263}),\n  ('wide conditional branch is four bytes',\n   ([['jz', 'x'], ['data', 202], ['label', 'x'], ['jmp', 'x']],),\n   {'branches': [[0, 'jz.w', 202], [206, 'jmp', -2]], 'size': 208}),\n  ('short branches to adjacent labels',\n   ([['jz', 'a'], ['label', 'a'], ['data', 2], ['jmp', 'a']],),\n   {'branches': [[0, 'jz', 0], [4, 'jmp', -4]], 'size': 6}),\n  ('duplicate label', ([['label', 'a'], ['data', 2], ['label', 'a']],), ['duplicate-label', 'a']),\n  ('undefined label', ([['jmp', 'nowhere'], ['data', 2]],), ['undefined-label', 'nowhere'])],\n [('regression: three-step widening cascade',\n   ([['data', 3],\n     ['jmp', 'A'],\n     ['data', 10],\n     ['jz', 'B'],\n     ['data', 115],\n     ['label', 'A'],\n     ['jmp', 'C'],\n     ['data', 10],\n     ['label', 'B'],\n     ['data', 118],\n     ['label', 'C'],\n     ['data', 1]],),\n   {'branches': [[3, 'jmp.w', 129], [16, 'jz.w', 128], [135, 'jmp.w', 128]], 'size': 267}),\n  ('backward branch exactly -128 stays short',\n   ([['label', 'top'], ['data', 126], ['jz', 'top'], ['data', 3], ['jmp', 'top']],),\n   {'branches': [[126, 'jz', -128], [131, 'jmp.w', -134]], 'size': 134}),\n  ('forward branch just around the short limit',\n   ([['data', 3], ['jmp', 'e'], ['data', 127], ['label', 'e'], ['jz', 'f'], ['data', 128], ['label', 'f']],),\n   {'branches': [[3, 'jmp', 127], [132, 'jz.w', 128]], 'size': 264}),\n  ('wide conditional branch is four bytes',\n   ([['jz', 'x'], ['data', 203], ['label', 'x'], ['jmp', 'x']],),\n   {'branches': [[0, 'jz.w', 203], [207, 'jmp', -2]], 'size': 209}),\n  ('short branches to adjacent labels',\n   ([['jz', 'a'], ['label', 'a'], ['data', 3], ['jmp', 'a']],),\n   {'branches': [[0, 'jz', 0], [5, 'jmp', -5]], 'size': 7}),\n  ('duplicate label', ([['label', 'a'], ['data', 3], ['label', 'a']],), ['duplicate-label', 'a']),\n  ('undefined label', ([['jmp', 'nowhere'], ['data', 3]],), ['undefined-label', 'nowhere'])],\n [('regression: three-step widening cascade',\n   ([['data', 4],\n     ['jmp', 'A'],\n     ['data', 10],\n     ['jz', 'B'],\n     ['data', 115],\n     ['label', 'A'],\n     ['jmp', 'C'],\n     ['data', 10],\n     ['label', 'B'],\n     ['data', 118],\n     ['label', 'C'],\n     ['data', 1]],),\n   {'branches': [[4, 'jmp.w', 129], [17, 'jz.w', 128], [136, 'jmp.w', 128]], 'size': 268}),\n  ('backward branch exactly -128 stays short',\n   ([['label', 'top'], ['data', 126], ['jz', 'top'], ['data', 4], ['jmp', 'top']],),\n   {'branches': [[126, 'jz', -128], [132, 'jmp.w', -135]], 'size': 135}),\n  ('forward branch just around the short limit',\n   ([['data', 4], ['jmp', 'e'], ['data', 127], ['label', 'e'], ['jz', 'f'], ['data', 128], ['label', 'f']],),\n   {'branches': [[4, 'jmp', 127], [133, 'jz.w', 128]], 'size': 265}),\n  ('wide conditional branch is four bytes',\n   ([['jz', 'x'], ['data', 204], ['label', 'x'], ['jmp', 'x']],),\n   {'branches': [[0, 'jz.w', 204], [208, 'jmp', -2]], 'size': 210}),\n  ('short branches to adjacent labels',\n   ([['jz', 'a'], ['label', 'a'], ['data', 4], ['jmp', 'a']],),\n   {'branches': [[0, 'jz', 0], [6, 'jmp', -6]], 'size': 8}),\n  ('duplicate label', ([['label', 'a'], ['data', 4], ['label', 'a']],), ['duplicate-label', 'a']),\n  ('undefined label', ([['jmp', 'nowhere'], ['data', 4]],), ['undefined-label', 'nowhere'])],\n [('regression: three-step widening cascade',\n   ([['data', 5],\n     ['jmp', 'A'],\n     ['data', 10],\n     ['jz', 'B'],\n     ['data', 115],\n     ['label', 'A'],\n     ['jmp', 'C'],\n     ['data', 10],\n     ['label', 'B'],\n     ['data', 118],\n     ['label', 'C'],\n     ['data', 1]],),\n   {'branches': [[5, 'jmp.w', 129], [18, 'jz.w', 128], [137, 'jmp.w', 128]], 'size': 269}),\n  ('backward branch exactly -128 stays short',\n   ([['label', 'top'], ['data', 126], ['jz', 'top'], ['data', 5], ['jmp', 'top']],),\n   {'branches': [[126, 'jz', -128], [133, 'jmp.w', -136]], 'size': 136}),\n  ('forward branch just around the short limit',\n   ([['data', 5], ['jmp', 'e'], ['data', 127], ['label', 'e'], ['jz', 'f'], ['data', 128], ['label', 'f']],),\n   {'branches': [[5, 'jmp', 127], [134, 'jz.w', 128]], 'size': 266}),\n  ('wide conditional branch is four bytes',\n   ([['jz', 'x'], ['data', 205], ['label', 'x'], ['jmp', 'x']],),\n   {'branches': [[0, 'jz.w', 205], [209, 'jmp', -2]], 'size': 211}),\n  ('short branches to adjacent labels',\n   ([['jz', 'a'], ['label', 'a'], ['data', 5], ['jmp', 'a']],),\n   {'branches': [[0, 'jz', 0], [7, 'jmp', -7]], 'size': 9}),\n  ('duplicate label', ([['label', 'a'], ['data', 5], ['label', 'a']],), ['duplicate-label', 'a']),\n  ('undefined label', ([['jmp', 'nowhere'], ['data', 5]],), ['undefined-label', 'nowhere'])]]\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":"320783401a76eb54dd52478ca597d671c9b2afbedb01984c8851aaaf4a9904f6","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(prog):\n    labels_seen = set()\n    for ins in prog:\n        if ins[0] == 'label':\n            if ins[1] in labels_seen:\n                return ['duplicate-label', ins[1]]\n            labels_seen.add(ins[1])\n    for ins in prog:\n        if ins[0] in ('jmp', 'jz') and ins[1] not in labels_seen:\n            return ['undefined-label', ins[1]]\n    long_form = set()\n    def size(i, ins):\n        if i in long_form:\n            return 4 if ins[0] == 'jz' else 3\n        return 2\n    rounds = 0\n    while True:\n        rounds += 1\n        addr = 0\n        addrs = []\n        where = {}\n        for i, ins in enumerate(prog):\n            addrs.append(addr)\n            if ins[0] == 'label':\n                where[ins[1]] = addr\n            elif ins[0] == 'data':\n                addr += ins[1]\n            else:\n                addr += size(i, ins)\n        changed = False\n        for i, ins in enumerate(prog):\n            if ins[0] in ('jmp', 'jz') and i not in long_form:\n                off = where[ins[1]] - (addrs[i] + 2)\n                if off < -128 or off > 127:\n                    long_form.add(i)\n                    changed = True\n        if not changed or rounds >= 1:\n            break\n    out = []\n    for i, ins in enumerate(prog):\n        if ins[0] in ('jmp', 'jz'):\n            suffix = '.w' if i in long_form else ''\n            out.append([addrs[i], ins[0] + suffix, where[ins[1]] - (addrs[i] + size(i, ins))])\n    return {'branches': out, 'size': addr}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: three-step widening cascade',\n   ([['data', 1],\n     ['jmp', 'A'],\n     ['data', 10],\n     ['jz', 'B'],\n     ['data', 115],\n     ['label', 'A'],\n     ['jmp', 'C'],\n     ['data', 10],\n     ['label', 'B'],\n     ['data', 118],\n     ['label', 'C'],\n     ['data', 1]],),\n   {'branches': [[1, 'jmp.w', 129], [14, 'jz.w', 128], [133, 'jmp.w', 128]], 'size': 265}),\n  ('backward branch exactly -128 stays short',\n   ([['label', 'top'], ['data', 126], ['jz', 'top'], ['data', 1], ['jmp', 'top']],),\n   {'branches': [[126, 'jz', -128], [129, 'jmp.w', -132]], 'size': 132}),\n  ('forward branch just around the short limit',\n   ([['data', 1], ['jmp', 'e'], ['data', 127], ['label', 'e'], ['jz', 'f'], ['data', 128], ['label', 'f']],),\n   {'branches': [[1, 'jmp', 127], [130, 'jz.w', 128]], 'size': 262}),\n  ('wide conditional branch is four bytes',\n   ([['jz', 'x'], ['data', 201], ['label', 'x'], ['jmp', 'x']],),\n   {'branches': [[0, 'jz.w', 201], [205, 'jmp', -2]], 'size': 207}),\n  ('short branches to adjacent labels',\n   ([['jz', 'a'], ['label', 'a'], ['data', 1], ['jmp', 'a']],),\n   {'branches': [[0, 'jz', 0], [3, 'jmp', -3]], 'size': 5}),\n  ('duplicate label', ([['label', 'a'], ['data', 1], ['label', 'a']],), ['duplicate-label', 'a']),\n  ('undefined label', ([['jmp', 'nowhere'], ['data', 1]],), ['undefined-label', 'nowhere'])],\n [('regression: three-step widening cascade',\n   ([['data', 2],\n     ['jmp', 'A'],\n     ['data', 10],\n     ['jz', 'B'],\n     ['data', 115],\n     ['label', 'A'],\n     ['jmp', 'C'],\n     ['data', 10],\n     ['label', 'B'],\n     ['data', 118],\n     ['label', 'C'],\n     ['data', 1]],),\n   {'branches': [[2, 'jmp.w', 129], [15, 'jz.w', 128], [134, 'jmp.w', 128]], 'size': 266}),\n  ('backward branch exactly -128 stays short',\n   ([['label', 'top'], ['data', 126], ['jz', 'top'], ['data', 2], ['jmp', 'top']],),\n   {'branches': [[126, 'jz', -128], [130, 'jmp.w', -133]], 'size': 133}),\n  ('forward branch just around the short limit',\n   ([['data', 2], ['jmp', 'e'], ['data', 127], ['label', 'e'], ['jz', 'f'], ['data', 128], ['label', 'f']],),\n   {'branches': [[2, 'jmp', 127], [131, 'jz.w', 128]], 'size': 263}),\n  ('wide conditional branch is four bytes',\n   ([['jz', 'x'], ['data', 202], ['label', 'x'], ['jmp', 'x']],),\n   {'branches': [[0, 'jz.w', 202], [206, 'jmp', -2]], 'size': 208}),\n  ('short branches to adjacent labels',\n   ([['jz', 'a'], ['label', 'a'], ['data', 2], ['jmp', 'a']],),\n   {'branches': [[0, 'jz', 0], [4, 'jmp', -4]], 'size': 6}),\n  ('duplicate label', ([['label', 'a'], ['data', 2], ['label', 'a']],), ['duplicate-label', 'a']),\n  ('undefined label', ([['jmp', 'nowhere'], ['data', 2]],), ['undefined-label', 'nowhere'])],\n [('regression: three-step widening cascade',\n   ([['data', 3],\n     ['jmp', 'A'],\n     ['data', 10],\n     ['jz', 'B'],\n     ['data', 115],\n     ['label', 'A'],\n     ['jmp', 'C'],\n     ['data', 10],\n     ['label', 'B'],\n     ['data', 118],\n     ['label', 'C'],\n     ['data', 1]],),\n   {'branches': [[3, 'jmp.w', 129], [16, 'jz.w', 128], [135, 'jmp.w', 128]], 'size': 267}),\n  ('backward branch exactly -128 stays short',\n   ([['label', 'top'], ['data', 126], ['jz', 'top'], ['data', 3], ['jmp', 'top']],),\n   {'branches': [[126, 'jz', -128], [131, 'jmp.w', -134]], 'size': 134}),\n  ('forward branch just around the short limit',\n   ([['data', 3], ['jmp', 'e'], ['data', 127], ['label', 'e'], ['jz', 'f'], ['data', 128], ['label', 'f']],),\n   {'branches': [[3, 'jmp', 127], [132, 'jz.w', 128]], 'size': 264}),\n  ('wide conditional branch is four bytes',\n   ([['jz', 'x'], ['data', 203], ['label', 'x'], ['jmp', 'x']],),\n   {'branches': [[0, 'jz.w', 203], [207, 'jmp', -2]], 'size': 209}),\n  ('short branches to adjacent labels',\n   ([['jz', 'a'], ['label', 'a'], ['data', 3], ['jmp', 'a']],),\n   {'branches': [[0, 'jz', 0], [5, 'jmp', -5]], 'size': 7}),\n  ('duplicate label', ([['label', 'a'], ['data', 3], ['label', 'a']],), ['duplicate-label', 'a']),\n  ('undefined label', ([['jmp', 'nowhere'], ['data', 3]],), ['undefined-label', 'nowhere'])],\n [('regression: three-step widening cascade',\n   ([['data', 4],\n     ['jmp', 'A'],\n     ['data', 10],\n     ['jz', 'B'],\n     ['data', 115],\n     ['label', 'A'],\n     ['jmp', 'C'],\n     ['data', 10],\n     ['label', 'B'],\n     ['data', 118],\n     ['label', 'C'],\n     ['data', 1]],),\n   {'branches': [[4, 'jmp.w', 129], [17, 'jz.w', 128], [136, 'jmp.w', 128]], 'size': 268}),\n  ('backward branch exactly -128 stays short',\n   ([['label', 'top'], ['data', 126], ['jz', 'top'], ['data', 4], ['jmp', 'top']],),\n   {'branches': [[126, 'jz', -128], [132, 'jmp.w', -135]], 'size': 135}),\n  ('forward branch just around the short limit',\n   ([['data', 4], ['jmp', 'e'], ['data', 127], ['label', 'e'], ['jz', 'f'], ['data', 128], ['label', 'f']],),\n   {'branches': [[4, 'jmp', 127], [133, 'jz.w', 128]], 'size': 265}),\n  ('wide conditional branch is four bytes',\n   ([['jz', 'x'], ['data', 204], ['label', 'x'], ['jmp', 'x']],),\n   {'branches': [[0, 'jz.w', 204], [208, 'jmp', -2]], 'size': 210}),\n  ('short branches to adjacent labels',\n   ([['jz', 'a'], ['label', 'a'], ['data', 4], ['jmp', 'a']],),\n   {'branches': [[0, 'jz', 0], [6, 'jmp', -6]], 'size': 8}),\n  ('duplicate label', ([['label', 'a'], ['data', 4], ['label', 'a']],), ['duplicate-label', 'a']),\n  ('undefined label', ([['jmp', 'nowhere'], ['data', 4]],), ['undefined-label', 'nowhere'])],\n [('regression: three-step widening cascade',\n   ([['data', 5],\n     ['jmp', 'A'],\n     ['data', 10],\n     ['jz', 'B'],\n     ['data', 115],\n     ['label', 'A'],\n     ['jmp', 'C'],\n     ['data', 10],\n     ['label', 'B'],\n     ['data', 118],\n     ['label', 'C'],\n     ['data', 1]],),\n   {'branches': [[5, 'jmp.w', 129], [18, 'jz.w', 128], [137, 'jmp.w', 128]], 'size': 269}),\n  ('backward branch exactly -128 stays short',\n   ([['label', 'top'], ['data', 126], ['jz', 'top'], ['data', 5], ['jmp', 'top']],),\n   {'branches': [[126, 'jz', -128], [133, 'jmp.w', -136]], 'size': 136}),\n  ('forward branch just around the short limit',\n   ([['data', 5], ['jmp', 'e'], ['data', 127], ['label', 'e'], ['jz', 'f'], ['data', 128], ['label', 'f']],),\n   {'branches': [[5, 'jmp', 127], [134, 'jz.w', 128]], 'size': 266}),\n  ('wide conditional branch is four bytes',\n   ([['jz', 'x'], ['data', 205], ['label', 'x'], ['jmp', 'x']],),\n   {'branches': [[0, 'jz.w', 205], [209, 'jmp', -2]], 'size': 211}),\n  ('short branches to adjacent labels',\n   ([['jz', 'a'], ['label', 'a'], ['data', 5], ['jmp', 'a']],),\n   {'branches': [[0, 'jz', 0], [7, 'jmp', -7]], 'size': 9}),\n  ('duplicate label', ([['label', 'a'], ['data', 5], ['label', 'a']],), ['duplicate-label', 'a']),\n  ('undefined label', ([['jmp', 'nowhere'], ['data', 5]],), ['undefined-label', 'nowhere'])]]\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":"5a4b39057fb8f9e7546d6e8ccf83030c6152d4ff3e885d18e02aaf74ad35f1c5","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(prog):\n    labels_seen = set()\n    for ins in prog:\n        if ins[0] == 'label':\n            if ins[1] in labels_seen:\n                return ['duplicate-label', ins[1]]\n            labels_seen.add(ins[1])\n    for ins in prog:\n        if ins[0] in ('jmp', 'jz') and ins[1] not in labels_seen:\n            return ['undefined-label', ins[1]]\n    long_form = set()\n    def size(i, ins):\n        if i in long_form:\n            return 4 if ins[0] == 'jz' else 3\n        return 2\n    rounds = 0\n    while True:\n        rounds += 1\n        addr = 0\n        addrs = []\n        where = {}\n        for i, ins in enumerate(prog):\n            addrs.append(addr)\n            if ins[0] == 'label':\n                where[ins[1]] = addr\n            elif ins[0] == 'data':\n                addr += ins[1]\n            else:\n                addr += size(i, ins)\n        changed = False\n        for i, ins in enumerate(prog):\n            if ins[0] in ('jmp', 'jz') and i not in long_form:\n                off = where[ins[1]] - (addrs[i] + 2)\n                if off < -128 or off > 127:\n                    long_form.add(i)\n                    changed = True\n        if not changed or rounds > len(prog):\n            break\n    out = []\n    for i, ins in enumerate(prog):\n        if ins[0] in ('jmp', 'jz'):\n            suffix = '.w' if i in long_form else ''\n            out.append([addrs[i], ins[0] + suffix, where[ins[1]] - (addrs[i] + size(i, ins))])\n    return {'branches': out, 'size': addr}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: three-step widening cascade',\n   ([['data', 1],\n     ['jmp', 'A'],\n     ['data', 10],\n     ['jz', 'B'],\n     ['data', 115],\n     ['label', 'A'],\n     ['jmp', 'C'],\n     ['data', 10],\n     ['label', 'B'],\n     ['data', 118],\n     ['label', 'C'],\n     ['data', 1]],),\n   {'branches': [[1, 'jmp.w', 129], [14, 'jz.w', 128], [133, 'jmp.w', 128]], 'size': 265}),\n  ('backward branch exactly -128 stays short',\n   ([['label', 'top'], ['data', 126], ['jz', 'top'], ['data', 1], ['jmp', 'top']],),\n   {'branches': [[126, 'jz', -128], [129, 'jmp.w', -132]], 'size': 132}),\n  ('forward branch just around the short limit',\n   ([['data', 1], ['jmp', 'e'], ['data', 127], ['label', 'e'], ['jz', 'f'], ['data', 128], ['label', 'f']],),\n   {'branches': [[1, 'jmp', 127], [130, 'jz.w', 128]], 'size': 262}),\n  ('wide conditional branch is four bytes',\n   ([['jz', 'x'], ['data', 201], ['label', 'x'], ['jmp', 'x']],),\n   {'branches': [[0, 'jz.w', 201], [205, 'jmp', -2]], 'size': 207}),\n  ('short branches to adjacent labels',\n   ([['jz', 'a'], ['label', 'a'], ['data', 1], ['jmp', 'a']],),\n   {'branches': [[0, 'jz', 0], [3, 'jmp', -3]], 'size': 5}),\n  ('duplicate label', ([['label', 'a'], ['data', 1], ['label', 'a']],), ['duplicate-label', 'a']),\n  ('undefined label', ([['jmp', 'nowhere'], ['data', 1]],), ['undefined-label', 'nowhere'])],\n [('regression: three-step widening cascade',\n   ([['data', 2],\n     ['jmp', 'A'],\n     ['data', 10],\n     ['jz', 'B'],\n     ['data', 115],\n     ['label', 'A'],\n     ['jmp', 'C'],\n     ['data', 10],\n     ['label', 'B'],\n     ['data', 118],\n     ['label', 'C'],\n     ['data', 1]],),\n   {'branches': [[2, 'jmp.w', 129], [15, 'jz.w', 128], [134, 'jmp.w', 128]], 'size': 266}),\n  ('backward branch exactly -128 stays short',\n   ([['label', 'top'], ['data', 126], ['jz', 'top'], ['data', 2], ['jmp', 'top']],),\n   {'branches': [[126, 'jz', -128], [130, 'jmp.w', -133]], 'size': 133}),\n  ('forward branch just around the short limit',\n   ([['data', 2], ['jmp', 'e'], ['data', 127], ['label', 'e'], ['jz', 'f'], ['data', 128], ['label', 'f']],),\n   {'branches': [[2, 'jmp', 127], [131, 'jz.w', 128]], 'size': 263}),\n  ('wide conditional branch is four bytes',\n   ([['jz', 'x'], ['data', 202], ['label', 'x'], ['jmp', 'x']],),\n   {'branches': [[0, 'jz.w', 202], [206, 'jmp', -2]], 'size': 208}),\n  ('short branches to adjacent labels',\n   ([['jz', 'a'], ['label', 'a'], ['data', 2], ['jmp', 'a']],),\n   {'branches': [[0, 'jz', 0], [4, 'jmp', -4]], 'size': 6}),\n  ('duplicate label', ([['label', 'a'], ['data', 2], ['label', 'a']],), ['duplicate-label', 'a']),\n  ('undefined label', ([['jmp', 'nowhere'], ['data', 2]],), ['undefined-label', 'nowhere'])],\n [('regression: three-step widening cascade',\n   ([['data', 3],\n     ['jmp', 'A'],\n     ['data', 10],\n     ['jz', 'B'],\n     ['data', 115],\n     ['label', 'A'],\n     ['jmp', 'C'],\n     ['data', 10],\n     ['label', 'B'],\n     ['data', 118],\n     ['label', 'C'],\n     ['data', 1]],),\n   {'branches': [[3, 'jmp.w', 129], [16, 'jz.w', 128], [135, 'jmp.w', 128]], 'size': 267}),\n  ('backward branch exactly -128 stays short',\n   ([['label', 'top'], ['data', 126], ['jz', 'top'], ['data', 3], ['jmp', 'top']],),\n   {'branches': [[126, 'jz', -128], [131, 'jmp.w', -134]], 'size': 134}),\n  ('forward branch just around the short limit',\n   ([['data', 3], ['jmp', 'e'], ['data', 127], ['label', 'e'], ['jz', 'f'], ['data', 128], ['label', 'f']],),\n   {'branches': [[3, 'jmp', 127], [132, 'jz.w', 128]], 'size': 264}),\n  ('wide conditional branch is four bytes',\n   ([['jz', 'x'], ['data', 203], ['label', 'x'], ['jmp', 'x']],),\n   {'branches': [[0, 'jz.w', 203], [207, 'jmp', -2]], 'size': 209}),\n  ('short branches to adjacent labels',\n   ([['jz', 'a'], ['label', 'a'], ['data', 3], ['jmp', 'a']],),\n   {'branches': [[0, 'jz', 0], [5, 'jmp', -5]], 'size': 7}),\n  ('duplicate label', ([['label', 'a'], ['data', 3], ['label', 'a']],), ['duplicate-label', 'a']),\n  ('undefined label', ([['jmp', 'nowhere'], ['data', 3]],), ['undefined-label', 'nowhere'])],\n [('regression: three-step widening cascade',\n   ([['data', 4],\n     ['jmp', 'A'],\n     ['data', 10],\n     ['jz', 'B'],\n     ['data', 115],\n     ['label', 'A'],\n     ['jmp', 'C'],\n     ['data', 10],\n     ['label', 'B'],\n     ['data', 118],\n     ['label', 'C'],\n     ['data', 1]],),\n   {'branches': [[4, 'jmp.w', 129], [17, 'jz.w', 128], [136, 'jmp.w', 128]], 'size': 268}),\n  ('backward branch exactly -128 stays short',\n   ([['label', 'top'], ['data', 126], ['jz', 'top'], ['data', 4], ['jmp', 'top']],),\n   {'branches': [[126, 'jz', -128], [132, 'jmp.w', -135]], 'size': 135}),\n  ('forward branch just around the short limit',\n   ([['data', 4], ['jmp', 'e'], ['data', 127], ['label', 'e'], ['jz', 'f'], ['data', 128], ['label', 'f']],),\n   {'branches': [[4, 'jmp', 127], [133, 'jz.w', 128]], 'size': 265}),\n  ('wide conditional branch is four bytes',\n   ([['jz', 'x'], ['data', 204], ['label', 'x'], ['jmp', 'x']],),\n   {'branches': [[0, 'jz.w', 204], [208, 'jmp', -2]], 'size': 210}),\n  ('short branches to adjacent labels',\n   ([['jz', 'a'], ['label', 'a'], ['data', 4], ['jmp', 'a']],),\n   {'branches': [[0, 'jz', 0], [6, 'jmp', -6]], 'size': 8}),\n  ('duplicate label', ([['label', 'a'], ['data', 4], ['label', 'a']],), ['duplicate-label', 'a']),\n  ('undefined label', ([['jmp', 'nowhere'], ['data', 4]],), ['undefined-label', 'nowhere'])],\n [('regression: three-step widening cascade',\n   ([['data', 5],\n     ['jmp', 'A'],\n     ['data', 10],\n     ['jz', 'B'],\n     ['data', 115],\n     ['label', 'A'],\n     ['jmp', 'C'],\n     ['data', 10],\n     ['label', 'B'],\n     ['data', 118],\n     ['label', 'C'],\n     ['data', 1]],),\n   {'branches': [[5, 'jmp.w', 129], [18, 'jz.w', 128], [137, 'jmp.w', 128]], 'size': 269}),\n  ('backward branch exactly -128 stays short',\n   ([['label', 'top'], ['data', 126], ['jz', 'top'], ['data', 5], ['jmp', 'top']],),\n   {'branches': [[126, 'jz', -128], [133, 'jmp.w', -136]], 'size': 136}),\n  ('forward branch just around the short limit',\n   ([['data', 5], ['jmp', 'e'], ['data', 127], ['label', 'e'], ['jz', 'f'], ['data', 128], ['label', 'f']],),\n   {'branches': [[5, 'jmp', 127], [134, 'jz.w', 128]], 'size': 266}),\n  ('wide conditional branch is four bytes',\n   ([['jz', 'x'], ['data', 205], ['label', 'x'], ['jmp', 'x']],),\n   {'branches': [[0, 'jz.w', 205], [209, 'jmp', -2]], 'size': 211}),\n  ('short branches to adjacent labels',\n   ([['jz', 'a'], ['label', 'a'], ['data', 5], ['jmp', 'a']],),\n   {'branches': [[0, 'jz', 0], [7, 'jmp', -7]], 'size': 9}),\n  ('duplicate label', ([['label', 'a'], ['data', 5], ['label', 'a']],), ['duplicate-label', 'a']),\n  ('undefined label', ([['jmp', 'nowhere'], ['data', 5]],), ['undefined-label', 'nowhere'])]]\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 bytecode virtual machine mechanism with a stipulated instruction encoding; it is not a production VM and claims no conformance to any real specification. 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-bytecode-virtual-machines-branch-relaxation-assembler-fixpoint-iteration","generated_at":"2026-09-29T14:51:23.994906+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Variable-length branch encodings need fixpoint relaxation to produce correct displacements.","repair":"Repeat address assignment until no branch is widened (bounded by the number of instructions).","root_cause":"Relaxation stops after the first pass even when widening changed addresses.","sha256":"84a59ef1fdb6b5c7b524eb11261f20a8e02521656ec7e7b532559871b58d8231","title":"Branch relaxation: single relaxation pass · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":40.582,"exit_code":1,"observations":[{"actual":{"branches":[[1,"jmp",127],[13,"jz.w",126],[130,"jmp.w",128]],"size":262},"check":"regression: three-step widening cascade","expected":{"branches":[[1,"jmp.w",129],[14,"jz.w",128],[133,"jmp.w",128]],"size":265},"passed":false},{"actual":{"branches":[[126,"jz",-128],[129,"jmp.w",-132]],"size":132},"check":"backward branch exactly -128 stays short","expected":{"branches":[[126,"jz",-128],[129,"jmp.w",-132]],"size":132},"passed":true},{"actual":{"branches":[[1,"jmp",127],[130,"jz.w",128]],"size":262},"check":"forward branch just around the short limit","expected":{"branches":[[1,"jmp",127],[130,"jz.w",128]],"size":262},"passed":true},{"actual":{"branches":[[0,"jz.w",201],[205,"jmp",-2]],"size":207},"check":"wide conditional branch is four bytes","expected":{"branches":[[0,"jz.w",201],[205,"jmp",-2]],"size":207},"passed":true},{"actual":{"branches":[[0,"jz",0],[3,"jmp",-3]],"size":5},"check":"short branches to adjacent labels","expected":{"branches":[[0,"jz",0],[3,"jmp",-3]],"size":5},"passed":true},{"actual":["duplicate-label","a"],"check":"duplicate label","expected":["duplicate-label","a"],"passed":true},{"actual":["undefined-label","nowhere"],"check":"undefined label","expected":["undefined-label","nowhere"],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: three-step widening cascade\", \"actual\": {\"branches\": [[1, \"jmp\", 127], [13, \"jz.w\", 126], [130, \"jmp.w\", 128]], \"size\": 262}, \"expected\": {\"branches\": [[1, \"jmp.w\", 129], [14, \"jz.w\", 128], [133, \"jmp.w\", 128]], \"size\": 265}, \"passed\": false}, {\"check\": \"backward branch exactly -128 stays short\", \"actual\": {\"branches\": [[126, \"jz\", -128], [129, \"jmp.w\", -132]], \"size\": 132}, \"expected\": {\"branches\": [[126, \"jz\", -128], [129, \"jmp.w\", -132]], \"size\": 132}, \"passed\": true}, {\"check\": \"forward branch just around the short limit\", \"actual\": {\"branches\": [[1, \"jmp\", 127], [130, \"jz.w\", 128]], \"size\": 262}, \"expected\": {\"branches\": [[1, \"jmp\", 127], [130, \"jz.w\", 128]], \"size\": 262}, \"passed\": true}, {\"check\": \"wide conditional branch is four bytes\", \"actual\": {\"branches\": [[0, \"jz.w\", 201], [205, \"jmp\", -2]], \"size\": 207}, \"expected\": {\"branches\": [[0, \"jz.w\", 201], [205, \"jmp\", -2]], \"size\": 207}, \"passed\": true}, {\"check\": \"short branches to adjacent labels\", \"actual\": {\"branches\": [[0, \"jz\", 0], [3, \"jmp\", -3]], \"size\": 5}, \"expected\": {\"branches\": [[0, \"jz\", 0], [3, \"jmp\", -3]], \"size\": 5}, \"passed\": true}, {\"check\": \"duplicate label\", \"actual\": [\"duplicate-label\", \"a\"], \"expected\": [\"duplicate-label\", \"a\"], \"passed\": true}, {\"check\": \"undefined label\", \"actual\": [\"undefined-label\", \"nowhere\"], \"expected\": [\"undefined-label\", \"nowhere\"], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":39.228,"exit_code":1,"observations":[{"actual":{"branches":[[1,"jmp",127],[13,"jz",127],[130,"jmp.w",127]],"size":261},"check":"regression: three-step widening cascade","expected":{"branches":[[1,"jmp.w",129],[14,"jz.w",128],[133,"jmp.w",128]],"size":265},"passed":false},{"actual":{"branches":[[126,"jz",-128],[129,"jmp.w",-132]],"size":131},"check":"backward branch exactly -128 stays short","expected":{"branches":[[126,"jz",-128],[129,"jmp.w",-132]],"size":132},"passed":false},{"actual":{"branches":[[1,"jmp",127],[130,"jz.w",126]],"size":260},"check":"forward branch just around the short limit","expected":{"branches":[[1,"jmp",127],[130,"jz.w",128]],"size":262},"passed":false},{"actual":{"branches":[[0,"jz.w",199],[203,"jmp",-2]],"size":205},"check":"wide conditional branch is four bytes","expected":{"branches":[[0,"jz.w",201],[205,"jmp",-2]],"size":207},"passed":false},{"actual":{"branches":[[0,"jz",0],[3,"jmp",-3]],"size":5},"check":"short branches to adjacent labels","expected":{"branches":[[0,"jz",0],[3,"jmp",-3]],"size":5},"passed":true},{"actual":["duplicate-label","a"],"check":"duplicate label","expected":["duplicate-label","a"],"passed":true},{"actual":["undefined-label","nowhere"],"check":"undefined label","expected":["undefined-label","nowhere"],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: three-step widening cascade\", \"actual\": {\"branches\": [[1, \"jmp\", 127], [13, \"jz\", 127], [130, \"jmp.w\", 127]], \"size\": 261}, \"expected\": {\"branches\": [[1, \"jmp.w\", 129], [14, \"jz.w\", 128], [133, \"jmp.w\", 128]], \"size\": 265}, \"passed\": false}, {\"check\": \"backward branch exactly -128 stays short\", \"actual\": {\"branches\": [[126, \"jz\", -128], [129, \"jmp.w\", -132]], \"size\": 131}, \"expected\": {\"branches\": [[126, \"jz\", -128], [129, \"jmp.w\", -132]], \"size\": 132}, \"passed\": false}, {\"check\": \"forward branch just around the short limit\", \"actual\": {\"branches\": [[1, \"jmp\", 127], [130, \"jz.w\", 126]], \"size\": 260}, \"expected\": {\"branches\": [[1, \"jmp\", 127], [130, \"jz.w\", 128]], \"size\": 262}, \"passed\": false}, {\"check\": \"wide conditional branch is four bytes\", \"actual\": {\"branches\": [[0, \"jz.w\", 199], [203, \"jmp\", -2]], \"size\": 205}, \"expected\": {\"branches\": [[0, \"jz.w\", 201], [205, \"jmp\", -2]], \"size\": 207}, \"passed\": false}, {\"check\": \"short branches to adjacent labels\", \"actual\": {\"branches\": [[0, \"jz\", 0], [3, \"jmp\", -3]], \"size\": 5}, \"expected\": {\"branches\": [[0, \"jz\", 0], [3, \"jmp\", -3]], \"size\": 5}, \"passed\": true}, {\"check\": \"duplicate label\", \"actual\": [\"duplicate-label\", \"a\"], \"expected\": [\"duplicate-label\", \"a\"], \"passed\": true}, {\"check\": \"undefined label\", \"actual\": [\"undefined-label\", \"nowhere\"], \"expected\": [\"undefined-label\", \"nowhere\"], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":40.298,"exit_code":0,"observations":[{"actual":{"branches":[[1,"jmp.w",129],[14,"jz.w",128],[133,"jmp.w",128]],"size":265},"check":"regression: three-step widening cascade","expected":{"branches":[[1,"jmp.w",129],[14,"jz.w",128],[133,"jmp.w",128]],"size":265},"passed":true},{"actual":{"branches":[[126,"jz",-128],[129,"jmp.w",-132]],"size":132},"check":"backward branch exactly -128 stays short","expected":{"branches":[[126,"jz",-128],[129,"jmp.w",-132]],"size":132},"passed":true},{"actual":{"branches":[[1,"jmp",127],[130,"jz.w",128]],"size":262},"check":"forward branch just around the short limit","expected":{"branches":[[1,"jmp",127],[130,"jz.w",128]],"size":262},"passed":true},{"actual":{"branches":[[0,"jz.w",201],[205,"jmp",-2]],"size":207},"check":"wide conditional branch is four bytes","expected":{"branches":[[0,"jz.w",201],[205,"jmp",-2]],"size":207},"passed":true},{"actual":{"branches":[[0,"jz",0],[3,"jmp",-3]],"size":5},"check":"short branches to adjacent labels","expected":{"branches":[[0,"jz",0],[3,"jmp",-3]],"size":5},"passed":true},{"actual":["duplicate-label","a"],"check":"duplicate label","expected":["duplicate-label","a"],"passed":true},{"actual":["undefined-label","nowhere"],"check":"undefined label","expected":["undefined-label","nowhere"],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: three-step widening cascade\", \"actual\": {\"branches\": [[1, \"jmp.w\", 129], [14, \"jz.w\", 128], [133, \"jmp.w\", 128]], \"size\": 265}, \"expected\": {\"branches\": [[1, \"jmp.w\", 129], [14, \"jz.w\", 128], [133, \"jmp.w\", 128]], \"size\": 265}, \"passed\": true}, {\"check\": \"backward branch exactly -128 stays short\", \"actual\": {\"branches\": [[126, \"jz\", -128], [129, \"jmp.w\", -132]], \"size\": 132}, \"expected\": {\"branches\": [[126, \"jz\", -128], [129, \"jmp.w\", -132]], \"size\": 132}, \"passed\": true}, {\"check\": \"forward branch just around the short limit\", \"actual\": {\"branches\": [[1, \"jmp\", 127], [130, \"jz.w\", 128]], \"size\": 262}, \"expected\": {\"branches\": [[1, \"jmp\", 127], [130, \"jz.w\", 128]], \"size\": 262}, \"passed\": true}, {\"check\": \"wide conditional branch is four bytes\", \"actual\": {\"branches\": [[0, \"jz.w\", 201], [205, \"jmp\", -2]], \"size\": 207}, \"expected\": {\"branches\": [[0, \"jz.w\", 201], [205, \"jmp\", -2]], \"size\": 207}, \"passed\": true}, {\"check\": \"short branches to adjacent labels\", \"actual\": {\"branches\": [[0, \"jz\", 0], [3, \"jmp\", -3]], \"size\": 5}, \"expected\": {\"branches\": [[0, \"jz\", 0], [3, \"jmp\", -3]], \"size\": 5}, \"passed\": true}, {\"check\": \"duplicate label\", \"actual\": [\"duplicate-label\", \"a\"], \"expected\": [\"duplicate-label\", \"a\"], \"passed\": true}, {\"check\": \"undefined label\", \"actual\": [\"undefined-label\", \"nowhere\"], \"expected\": [\"undefined-label\", \"nowhere\"], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}