"""Python control flow graph generation and bytecode assembly."""

import math
import os
import sys
from rpython.rlib.objectmodel import specialize, we_are_translated
from rpython.rlib import rstring

from pypy.interpreter.astcompiler import ast, consts, misc, symtable
from pypy.interpreter.error import OperationError
from pypy.interpreter.pycode import PyCode
from pypy.interpreter.miscutils import string_sort
from pypy.tool import stdlib_opcode as ops

is_absolute_jump = misc.dict_to_switch(
    {opcode.index: True
        for opcode in ops.unrolling_opcode_descs
        if opcode.index in ops.hasjabs},
    default=False)

# Compiler-internal scope markers.  Not real opcodes: absent from
# lib-python/3/opcode.py and the interpreter dispatch.  Values match
# CPython's compile.c #defines (negative, so they can never collide with
# any real opcode number).
_SETUP_FINALLY = -1   # open exception scope, lasti=False
_SETUP_CLEANUP = -2   # open exception scope, lasti=True (try/finally/except-as)
_SETUP_WITH    = -3   # open exception scope, lasti=True, depth_sub=1 (with-blocks)
_POP_BLOCK     = -4   # close exception scope

PSEUDO_OPNAMES = ['_SETUP_FINALLY', '_SETUP_CLEANUP', '_SETUP_WITH', '_POP_BLOCK']

# Pseudo-instructions: present in block.instructions so _build_exceptiontable
# and _stacksize can read them, but they contribute zero bytes to the encoded
# bytecode and have no interpreter dispatch.
is_pseudo_opcode = misc.dict_to_switch(
    {_SETUP_FINALLY: True,
     _SETUP_CLEANUP: True,
     _SETUP_WITH:    True,
     _POP_BLOCK:     True},
    default=False)


class StackDepthComputationError(Exception):
    pass

UNKNOWN_POSITION = (-1, -1, -1, -1)

class Instruction(object):
    """Represents a single opcode."""

    _stack_depth_after = -99 # used before translation only

    def __init__(self, opcode, arg=0, position_info=UNKNOWN_POSITION):
        self.opcode = opcode
        self.arg = arg
        self.position_info = position_info
        self.jump = None

    def copy(self):
        res = Instruction(self.opcode, self.arg, self.position_info)
        res.jump = self.jump
        return res

    def size(self):
        """Return the size of bytes of this instruction when it is
        encoded.
        """
        if is_pseudo_opcode(self.opcode):
            return 0
        if self.arg <= 0xff:
            return 2
        if self.arg <= 0xffff:
            return 4
        if self.arg <= 0xffffff:
            return 6
        return 8

    def encode(self, code):
        if is_pseudo_opcode(self.opcode):
            return
        opcode = self.opcode

        arg = self.arg
        size = self.size()
        if size == 8:
            code.append(chr(ops.EXTENDED_ARG))
            code.append(chr((arg >> 24) & 0xff))
            assert ((arg >> 24) & 0xff) == (arg >> 24)
        if size >= 6:
            code.append(chr(ops.EXTENDED_ARG))
            code.append(chr((arg >> 16) & 0xff))
        if size >= 4:
            code.append(chr(ops.EXTENDED_ARG))
            code.append(chr((arg >> 8) & 0xff))
        if size >= 2:
            code.append(chr(opcode))
            code.append(chr(arg & 0xff))


    def jump_to(self, target):
        """Indicate the target this jump instruction.

        The opcode must be a JUMP opcode.
        """
        self.jump = target

    def update_position_if_not_set(self, position_info):
        if self.position_info[0] < 0:
            self.position_info = position_info
        else:
            position_info = self.position_info
        # returns the value of self.position_info, whether it was written to or
        # not
        return position_info

    @staticmethod
    def is_setup_pseudo_code(opcode):
        return opcode in (_SETUP_FINALLY, _SETUP_CLEANUP, _SETUP_WITH)

    def opname(self):
        # for debugging
        if self.opcode >= 0:
            return ops.opname[self.opcode]
        else:
            return PSEUDO_OPNAMES[~self.opcode]

    def __repr__(self):
        data = ["<", self._opname()]
        if self.opcode >= ops.HAVE_ARGUMENT:
            data.append(" ")
            data.append(str(self.arg))
            if self.jump is not None:
                data.append(" ")
                data.append(str(self.jump))
        data.append(" lineno=%s>" % (self.position_info[0], ))
        return "".join(data)


class Block(object):
    """A basic control flow block.

    It has one entry point and several possible exit points.  Its
    instructions may be jumps to other blocks, or if control flow
    reaches the end of the block, it continues to next_block.
    """

    _source = None

    def __init__(self):
        self.instructions = []
        self.next_block = None
        self.marked = 0
        # is True if instructions[-1] is one that unconditionally leaves the
        # execution of the instructions in the block (return, raise,
        # unconditional jumps)
        self.cant_add_instructions = False
        self.exits_function = False
        self.auto_inserted_return = False
        # set by codegen for exception-handler blocks so _stacksize finds them
        # even when no SETUP_FINALLY/EXCEPT jump instruction targets them
        self.forced_initial_depth = -1
        # set by _build_exceptiontable Phase 1 when this block is a handler target
        self.exc_lasti = False
        self.exc_depth_adj = 0
        self.exc_depth_sub = 0

    def __repr__(self):
        return "<Block %s>" % (self.instructions, )

    def emit_instr(self, instr):
        self.instructions.append(instr)
        op = instr.opcode
        if (
                op == ops.RETURN_VALUE or
                op == ops.RAISE_VARARGS or
                op == ops.RERAISE
        ):
            self.exits_function = True
            self.cant_add_instructions = True
        elif (
                op == ops.JUMP_FORWARD or
                op == ops.JUMP_ABSOLUTE
        ):
            self.cant_add_instructions = True

    def _post_order_see(self, stack):
        if self.marked == 0:
            self.marked = 1
            stack.append(self)

    def copy(self):
        copy = Block()
        copy.auto_inserted_return = self.auto_inserted_return
        for instr in self.instructions:
            copy.emit_instr(instr.copy())
        return copy


    def post_order(self):
        """Return this block and its children in post order.  This means
        that the graph of blocks is first cleaned up to ignore
        back-edges, thus turning it into a DAG.  Then the DAG is
        linearized.  For example:

                   A --> B -\           =>     [A, D, B, C]
                     \-> D ---> C
        """
        resultblocks = []
        stack = [self]
        self.marked = 1
        while stack:
            current = stack[-1]
            if current.marked == 1:
                current.marked = 2
                if current.next_block is not None:
                    current.next_block._post_order_see(stack)
            else:
                i = current.marked - 2
                assert i >= 0
                while i < len(current.instructions):
                    instr = current.instructions[i]
                    i += 1
                    if instr.jump is not None:
                        current.marked = i + 2
                        instr.jump._post_order_see(stack)
                        break
                else:
                    resultblocks.append(current)
                    stack.pop()
        resultblocks.reverse()
        for block in resultblocks:
            block.marked = 0
        return resultblocks

    def code_size(self):
        """Return the encoded size of all the instructions in this
        block.
        """
        i = 0
        for instr in self.instructions:
            i += instr.size()
        return i

    def get_code(self, code):
        """Encode the instructions in this block into bytecode."""
        startsize = code.getlength()
        for instr in self.instructions:
            instr.encode(code)
        assert code.getlength() == startsize + self.code_size()
        assert code.getlength() & 1 == 0

    def jump_thread(self):
        # do jump threading
        # 1) skip empty .next_block
        if not self.cant_add_instructions:
            while self.next_block is not None and not self.next_block.instructions:
                self.next_block = self.next_block.next_block

        # 2) jump-thread instructions
        i = 0
        while i < len(self.instructions):
            instr = self.instructions[i]
            instr_lineno = instr.position_info[0]
            i += 1
            target = instr.jump
            if not target:
                continue
            # replace a jump to an empty block with a jump to its successor
            while not target.instructions:
                target = instr.jump = target.next_block
                assert target is not None
            opcode = instr.opcode
            target_instr = target.instructions[0]
            target_lineno = target_instr.position_info[0]
            target_opcode = target_instr.opcode
            if ((target_opcode == ops.JUMP_ABSOLUTE or target_opcode == ops.JUMP_FORWARD) and
                    target_instr.jump.instructions and
                    target_instr.jump.instructions[0].position_info[0] == target_lineno):
                # we have an unconditional jump where the jump instruction and
                # the target of the jump have the same lineno, so it's safe to
                # skip the jump
                pass
            elif target_lineno != -1 and target_lineno != instr_lineno:
                continue # don't jump thread to not lose lines
            if target_instr is instr:
                continue # it's the same instruction (ie an infinite loop)
            # Optimize an unconditional jump going to another
            # unconditional jump.
            if opcode == ops.JUMP_ABSOLUTE or opcode == ops.JUMP_FORWARD:
                if target_opcode == ops.JUMP_ABSOLUTE:
                    instr.opcode = ops.JUMP_ABSOLUTE
                    instr.jump = target_instr.jump
                    i -= 1 # look at this instruction again
                elif target_opcode == ops.JUMP_FORWARD:
                    instr.jump = target_instr.jump
                    i -= 1 # look at this instruction again
                elif target_opcode == ops.RETURN_VALUE:
                    # Replace JUMP_* to a RETURN into
                    # just a RETURN
                    instr.opcode = ops.RETURN_VALUE
                    instr.jump = None
                continue
            if opcode == ops.JUMP_IF_FALSE_OR_POP:
                if (target_opcode == ops.JUMP_ABSOLUTE or
                        target_opcode == ops.JUMP_FORWARD or
                        target_opcode == ops.JUMP_IF_FALSE_OR_POP):
                    instr.jump = target_instr.jump
                    i -= 1 # look at this instruction again
            if opcode == ops.JUMP_IF_TRUE_OR_POP:
                if (target_opcode == ops.JUMP_ABSOLUTE or
                        target_opcode == ops.JUMP_FORWARD or
                        target_opcode == ops.JUMP_IF_TRUE_OR_POP):
                    instr.jump = target_instr.jump
                    i -= 1 # look at this instruction again
            if (opcode == ops.POP_JUMP_IF_FALSE or
                  opcode == ops.POP_JUMP_IF_TRUE or
                  opcode == ops.POP_JUMP_FORWARD_IF_NONE or
                  opcode == ops.POP_JUMP_FORWARD_IF_NOT_NONE
            ):
                if (target_opcode == ops.JUMP_ABSOLUTE or
                        target_opcode == ops.JUMP_FORWARD):
                    instr.jump = target_instr.jump
                    i -= 1 # look at this instruction again


def _make_index_dict_filter(syms, flag1, flag2):
    names = syms.keys()
    string_sort(names)   # return cell vars in alphabetical order
    i = 0
    result = {}
    for name in names:
        scope = syms[name]
        if scope in (flag1, flag2):
            result[name] = i
            i += 1
    return result


@specialize.argtype(0)
def _iter_to_dict(iterable, offset=0):
    result = {}
    index = offset
    for item in iterable:
        result[item] = index
        index += 1
    return result


class PythonCodeMaker(ast.ASTVisitor):
    """Knows how to assemble a PyCode object."""
    _debug_flag = False
    qualname = None

    def __init__(self, space, name, first_lineno, scope, compile_info):
        self.space = space
        self.name = name
        self.first_lineno = first_lineno
        self.compile_info = compile_info
        self.first_block = self.new_block()
        self.current_block = self.first_block
        self._is_dead_code = False
        self.names = {}
        self.var_names = _iter_to_dict(scope.varnames)
        self.cell_vars = _make_index_dict_filter(scope.symbols,
                                                 symtable.SCOPE_CELL,
                                                 symtable.SCOPE_CELL_CLASS)
        string_sort(scope.free_vars)    # return free vars in alphabetical order
        self.free_vars = _iter_to_dict(scope.free_vars, len(self.cell_vars))
        self.w_consts = space.newdict()
        self.consts_w = []
        self.argcount = 0
        self.posonlyargcount = 0
        self.kwonlyargcount = 0
        self.no_position_info()
        self.add_none_to_final_return = True
        self.match_context = None
        self._stack_depth = 0  # running stack depth counter at current emit point

    def __repr__(self):
        return "<PythonCodeMaker %s in %s:%s>" % (self.name, self.compile_info.filename, self.first_lineno)

    def _check_consistency(self, blocks):
        current_off = 0
        for block in blocks:
            assert block.offset == current_off
            for instr in block.instructions:
                current_off += instr.size()

    def view(self, blocks=None):
        from pypy.interpreter.astcompiler.codegen import view
        return view(blocks or self.first_block)

    def new_block(self):
        return Block()

    def use_block(self, block):
        """Start emitting bytecode into block."""
        self.current_block = block
        if block.forced_initial_depth >= 0:
            self._stack_depth = block.forced_initial_depth

    def use_next_block(self, block=None):
        """Set this block as the next_block for the last and use it."""
        if block is None:
            block = self.new_block()
        self.current_block.next_block = block
        self.use_block(block)
        return block

    def is_dead_code(self):
        """Return False if any code can be meaningfully added to the
        current block, or True if it would be dead code."""
        return self._is_dead_code or self.current_block.cant_add_instructions

    def all_dead_code(self):
        return DeadCode(self)

    def emit_op(self, op):
        """Emit an opcode without an argument."""
        instr = Instruction(op, position_info=self.position_info)
        if not self.is_dead_code():
            self.current_block.emit_instr(instr)
            self._stack_depth += _opcode_stack_effect(op, 0)
        return instr

    def emit_op_arg(self, op, arg):
        """Emit an opcode with an integer argument."""
        instr = Instruction(op, arg, position_info=self.position_info)
        if not self.is_dead_code():
            self.current_block.emit_instr(instr)
            self._stack_depth += _opcode_stack_effect(op, arg)

    def emit_swaps(self, arg):
        # Emit n-1 SWAPs to rotate TOS to depth n (CPython 3.11 style),
        # so that apply_static_swaps can eliminate them statically.
        for i in range(arg, 1, -1):
            self.emit_op_arg(ops.SWAP, i)

    def emit_op_name(self, op, container, name):
        """Emit an opcode referencing a name."""
        self.emit_op_arg(op, self.add_name(container, name))

    def emit_jump(self, op, block_to):
        """Emit a jump opcode to another block."""
        was_dead = self.is_dead_code()
        depth_before = self._stack_depth
        self.emit_op(op).jump_to(block_to)
        if not was_dead and Instruction.is_setup_pseudo_code(op):
            jump_effect = _opcode_stack_effect_jump(op)
            jump_depth = depth_before + jump_effect
            if jump_depth > block_to.forced_initial_depth:
                block_to.forced_initial_depth = jump_depth

    def emit_jump_noline(self, op, block_to):
        """Emit a jump with no position info, matching CPython's ADDOP_JUMP_NOLINE."""
        self.no_position_info()
        self.emit_jump(op, block_to)

    def emit_compare(self, ast_op_kind):
        from pypy.interpreter.astcompiler.codegen import compare_operations
        opcode, op_kind = compare_operations(ast_op_kind)
        self.emit_op_arg(opcode, op_kind)

    def emit_line_tracing_nop(self, node=None):
        old_position_info = UNKNOWN_POSITION
        if node:
            old_position_info = self.position_info
            self.update_position(node)
        self.emit_op(ops.NOP)
        if node:
            self.position_info = old_position_info

    def add_name(self, container, name):
        """Get the index of a name in container."""
        name = self.scope.mangle(name)
        try:
            index = container[name]
        except KeyError:
            index = len(container)
            container[name] = index
        return index

    def add_const(self, w_obj):
        """Add a W_Root to the constant array and return its location."""
        space = self.space
        if isinstance(w_obj, PyCode):
            # unlike CPython, never share code objects, it's pointless
            w_key = space.id(w_obj)
        else:
            w_key = PyCode.const_comparison_key(self.space, w_obj)

        w_len = space.finditem(self.w_consts, w_key)
        if w_len is not None:
            length = space.int_w(w_len)
        else:
            length = len(self.consts_w)
            w_obj = misc.intern_if_common_string(space, w_obj)
            self.consts_w.append(w_obj)
            space.setitem(self.w_consts, w_key, space.newint(length))
        if length == 0:
            self.scope.doc_removable = False
        return length


    def load_const(self, obj):
        if self.is_dead_code():
            return
        index = self.add_const(obj)
        self.emit_op_arg(ops.LOAD_CONST, index)

    @specialize.argtype(1)
    def update_position(self, node):
        """Change the position for the next instructions to that of node."""
        if self.is_dead_code():
            return self.position_info
        if isinstance(node, tuple):
            position_info = node
        else:
            position_info = (node.lineno, node.end_lineno, node.col_offset, node.end_col_offset)
        old_position_info = self.position_info
        self.position_info =  position_info
        return old_position_info

    def no_position_info(self):
        if self.is_dead_code():
            return
        self.position_info = (-1, ) * 4

    def new_match_context(self):
        return MatchContext(self)

    def sub_pattern_context(self):
        return SubMatchContext(self)

    def _resolve_block_targets(self, blocks):
        """Compute the arguments of jump instructions."""
        # The reason for this loop is extended jumps.  EXTENDED_ARG
        # extends the bytecode size, so it might invalidate the offsets we've
        # already given.  Thus we have to loop until the size of all jump
        # instructions is stable. Any extended jump at all is extremely rare,
        # so performance should not be too concerning.
        while True:
            offset = 0
            force_redo = False
            # Calculate the code offset of each block.
            for block in blocks:
                block.offset = offset
                offset += block.code_size()
            totalsize = offset
            for block in blocks:
                offset = block.offset
                for instr in block.instructions:
                    size = instr.size()
                    offset += size
                    if instr.jump is not None:
                        target = instr.jump
                        if is_absolute_jump(instr.opcode):
                            jump_arg = target.offset
                        else:
                            jump_arg = target.offset - offset
                        assert jump_arg >= 0
                        jump_arg //= 2
                        instr.arg = jump_arg
                        if instr.size() != size:
                            force_redo = True
            if not force_redo:
                self._check_consistency(blocks)
                return totalsize

    def _get_code_flags(self):
        """Get an extra flags that should be attached to the code object."""
        raise NotImplementedError

    def _stacksize_error_pos(self, depth, blocks, block, instr):
        # This case occurs if this code object uses some
        # construction for which the stack depth computation
        # is wrong (too high).  If you get here while working
        # on the astcompiler, then you should at first ignore
        # the error, and comment out the 'raise' below.  Such
        # an error is not really bad: it is just a bit
        # wasteful.  For release-ready versions, though, we'd
        # like not to be wasteful. :-)
        if not we_are_translated():
            self._stack_depth_debug_print(blocks, block, instr)
        os.write(2, "StackDepthComputationError(POS) in %s at %s:%s depth %s\n"
          % (self.compile_info.filename, self.name, self.first_lineno, depth))
        raise StackDepthComputationError   # would-be-nice-not-to-have

    def _stack_depth_debug_print(self, blocks, errorblock, errorinstr):
        print "\n" * 5
        print self.name
        for block in blocks:
            print "======="
            print block
            if block is errorblock:
                print "ERROR IS IN THIS BLOCK"
            print "stack depth at start", block.initial_depth
            if block._source is not None:
                print "stack depth at start set via", block._source
            for instr in block.instructions:
                print "--->" if instr is errorinstr else "    ", instr,
                if instr._stack_depth_after != -99:
                    print "stacksize afterwards: %s" % instr._stack_depth_after
                else:
                    print


    def _stacksize(self, blocks):
        """Compute co_stacksize."""
        for block in blocks:
            block.initial_depth = -99
        blocks[0].initial_depth = 0
        # Apply forced depths set by codegen for exception-handler blocks
        # that are unreachable via the instruction graph (no SETUP_* jump targets them).
        for block in blocks:
            if block.forced_initial_depth >= 0 and block.forced_initial_depth > block.initial_depth:
                block.initial_depth = block.forced_initial_depth
        # Assumes that it is sufficient to walk the blocks in 'post-order'.
        # This means we ignore all back-edges, but apart from that, we only
        # look into a block when all the previous blocks have been done.
        self._max_depth = 0
        for block in blocks:
            depth = self._do_stack_depth_walk(block, blocks)
            if block.auto_inserted_return and depth != 0:
                self._stacksize_error_pos(depth, blocks, block, None)
        return self._max_depth

    def _next_stack_depth_walk(self, nextblock, depth, source):
        if depth > nextblock.initial_depth:
            nextblock.initial_depth = depth
            if not we_are_translated():
                nextblock._source = source

    def _do_stack_depth_walk(self, block, blocks):
        depth = block.initial_depth
        if depth == -99:     # this block is never reached, skip
             return 0

        for instr in block.instructions:
            orig_depth = depth
            depth += _opcode_stack_effect(instr.opcode, instr.arg)
            if not we_are_translated():
                instr._stack_depth_after = depth
            if depth < 0:
                # This is really a fatal error, don't comment out this
                # 'raise'.  It means that the stack depth computation
                # thinks there is a path that yields a negative stack
                # depth, which means that it underestimates the space
                # needed and it would crash when interpreting this
                # code.
                if not we_are_translated():
                    instr._stack_depth_after = depth
                    self._stack_depth_debug_print(blocks, block, instr)
                os.write(2, "StackDepthComputationError(NEG) in %s at %s:%s\n"
                  % (self.compile_info.filename, self.name, self.first_lineno))
                raise StackDepthComputationError   # really fatal error
            if depth >= self._max_depth:
                self._max_depth = depth
            jump_op = instr.opcode
            if instr.jump is not None:
                target_depth = orig_depth + _opcode_stack_effect_jump(jump_op)
                if target_depth > self._max_depth:
                    self._max_depth = target_depth
                self._next_stack_depth_walk(instr.jump, target_depth, (block, instr))
                if jump_op == ops.JUMP_ABSOLUTE or jump_op == ops.JUMP_FORWARD:
                    # Nothing more can occur.
                    break
            elif jump_op == ops.RETURN_VALUE:
                if depth:
                    self._stacksize_error_pos(depth, blocks, block, instr)
                break
            elif jump_op == ops.RAISE_VARARGS:
                break
            elif jump_op == ops.RERAISE:
                break
        else:
            if block.next_block:
                self._next_stack_depth_walk(block.next_block, depth, (block, None))
        return depth

    def _build_positions(self, blocks):
        """Build the column offset table (with end column offsets)."""
        from pypy.interpreter.location import encode_single_position
        table = rstring.StringBuilder()
        for block in blocks:
            for instr in block.instructions:
                if is_pseudo_opcode(instr.opcode):
                    continue
                encode_single_position(table, instr.position_info, self.first_lineno)
                for extra in range((instr.size() - 2) // 2):
                    encode_single_position(table, UNKNOWN_POSITION, self.first_lineno)
        return table.build()

    def _build_code(self, blocks, size):
        bytecode = rstring.StringBuilder(size)
        for block in blocks:
            block.get_code(bytecode)
        return bytecode.build()

    def jump_thread(self, blocks):
        for block in blocks:
            block.jump_thread()

    def compute_predecessors_in_marked(self, blocks):
        # compute predecessors, use the 'marked' attribute for it
        def increase_incoming(block, todo):
            block.marked += 1
            if block.marked == 1:
                todo.append(block)
        for block in blocks:
            block.marked = 0
        self.first_block.marked = 1
        todo = [self.first_block]
        while todo:
            block = todo.pop()
            # mark next_block, but only if the edge can actually be taken
            if block.next_block and not block.cant_add_instructions:
                increase_incoming(block.next_block, todo)
            for instr in block.instructions:
                if instr.jump:
                    increase_incoming(instr.jump, todo)

    def propagate_line_numbers(self, blocks):
        # here block.marked stores the number of predecessor blocks.
        # use that info to propagate position information
        for block in blocks:
            if not block.instructions or block.marked == 0:
                continue
            prev_position = UNKNOWN_POSITION
            for instr in block.instructions:
                prev_position = instr.update_position_if_not_set(prev_position)
                if instr.jump is not None and instr.jump.marked == 1 and instr.jump.instructions:
                    if instr.is_setup_pseudo_code(instr.opcode):
                        continue # don't propagate line info into exception handler blocks
                    instr.jump.instructions[0].update_position_if_not_set(prev_position)
            next_block = block.next_block
            if (next_block and not block.cant_add_instructions and
                    next_block.marked == 1 and next_block.instructions):
                next_first_op = next_block.instructions[0]
                if next_first_op.is_setup_pseudo_code(next_first_op.opcode):
                    next_block.instructions[0].update_position_if_not_set(prev_position)

    def guarantee_lineno_for_exits(self, blocks):
        # CPython equivalent: guarantee_lineno_for_exits (compile.c).
        # After propagate_line_numbers, any block ending in RETURN_VALUE whose
        # last instruction is still UNSET gets the running lineno assigned to
        # all its UNSET instructions.
        lineno = self.first_lineno
        for block in blocks:
            if not block.instructions:
                continue
            last = block.instructions[-1]
            if last.position_info[0] < 0:
                if last.opcode == ops.RETURN_VALUE:
                    for instr in block.instructions:
                        if instr.position_info[0] < 0:
                            instr.position_info = (lineno,
                                                   instr.position_info[1],
                                                   instr.position_info[2],
                                                   instr.position_info[3])
            else:
                lineno = last.position_info[0]

    def optimize_unreachable_code(self, blocks):
        # block.marked still stores the predecessor information. use it to
        # remove all instructions from unreachable blocks, and optimize
        # JUMP_FORWARD instructions that go to the next block in the sequence
        # anyway. reset block.marked afterwards
        last_reachable = None
        for i, block in enumerate(blocks):
            # for blocks with 0 predecessors, don't emit any code for them by
            # setting the instructions to the empty list
            if block.marked == 0:
                block.instructions = []
                block.cant_add_instructions = False
                block.forced_initial_depth = -1
                continue
            last_reachable = block
            if block.instructions and i < len(blocks) - 1:
                lastop = block.instructions[-1]
                if lastop.opcode == ops.JUMP_FORWARD:
                    # find the block we would fall through
                    target = None
                    for j in range(i + 1, len(blocks)):
                        target = blocks[j]
                        if target.marked:
                            break
                    assert target is not None
                    if target is lastop.jump:
                        lastop.opcode = ops.NOP
                        lastop.jump = None
                        block.next_block = blocks[i + 1]
                        block.cant_add_instructions = False
            block.marked = 0
        # the last reachable block must have cant_add_instructions
        assert last_reachable is not None and last_reachable.cant_add_instructions

    def apply_static_swaps(self, blocks):
        """Eliminate statically-known SWAP sequences (port of CPython's pass)."""
        for block in blocks:
            instructions = block.instructions
            for i in range(len(instructions)):
                if instructions[i].opcode == ops.SWAP:
                    _apply_static_swaps(instructions, i)

    def _finalize_blocks(self):
        # Unless it's interactive, every code object must end in a return.
        if self._debug_flag:
            import pdb; pdb.set_trace()
        if not self.current_block.cant_add_instructions:
            # the implicit return has no position info, unless the function
            # contains no bytecodes at all. in that case the RETURN_VALUE gets
            # the firstlineno as the position
            if (self.current_block is self.first_block and
                    len(self.current_block.instructions) == 0):
                self.position_info = (self.first_lineno, -1, -1, -1)
            else:
                self.no_position_info() # will be duplicated by duplicate_exits_without_lineno
            if self.add_none_to_final_return:
                self.load_const(self.space.w_None)
            self.emit_op(ops.RETURN_VALUE)
            self.current_block.auto_inserted_return = True
        blocks = self.first_block.post_order()

        remove_redundant_nops(blocks)
        self.jump_thread(blocks)
        self.extend_blocks(blocks)
        self.apply_static_swaps(blocks)
        self.compute_predecessors_in_marked(blocks)
        self.duplicate_exits_without_lineno(blocks)
        self.propagate_line_numbers(blocks)
        self.guarantee_lineno_for_exits(blocks)
        self.optimize_unreachable_code(blocks)
        mininum_lineno = remove_redundant_nops(blocks)
        # Set the first lineno if it is not already explicitly set.
        if self.first_lineno == -1:
            self.first_lineno = mininum_lineno
        size = self._resolve_block_targets(blocks)
        return blocks, size

    def _build_exceptiontable(self, blocks):
        """Build co_exceptiontable using a CPython-style per-block graph traversal.

        Phase 1: DFS from the entry block (blocks[0]), propagating the handler stack
        along CFG edges.  Each block records the handler stack at its entry point.
        This correctly handles duplicate_exits_without_lineno: inlined unconditional
        jumps update the stack only for their own execution path; the fallback branch
        (reached via a conditional jump from the predecessor) inherits its own copy.

        Phase 2: Scan blocks in bytecode order.  At each block boundary, reconcile
        cur_handler with the block's recorded entry stack.  Within a block, SETUP_*/
        POP_BLOCK pseudo-ops push and pop the stack to emit contiguous table entries.

        handler stack entry: (handler_block, lasti, depth_adjust, depth_sub)
          lasti = True when the table entry carries the lasti flag (_SETUP_CLEANUP/
                  _SETUP_WITH).
          depth_adjust = _opcode_stack_effect_jump(op) for the opening SETUP_*.
          depth_sub = 1 for _SETUP_WITH (__enter__ result consumed before body), 0 otherwise.
        """
        # --- Phase 1: graph traversal, compute per-block entry handler stacks ---
        # Like CPython's label_exception_targets: DFS over the CFG, tracking a
        # stack of active handler blocks.  stk is list of Block (not tuples);
        # per-handler metadata (lasti, depth_adj, depth_sub) is stored as
        # attributes on the handler Block itself (CPython: b_lasti, b_exceptdepth).
        block_entry_stack = {} # Block -> list of Block

        first_block = blocks[0]
        block_entry_stack[first_block] = []
        worklist = [first_block]

        while worklist:
            b = worklist.pop()
            stk = block_entry_stack[b][:]  # mutable working copy (list of Block)

            for instr in b.instructions:
                op = instr.opcode
                if instr.is_setup_pseudo_code(op):
                    handler_target = instr.jump
                    # Handler block gets entry stack BEFORE the push.
                    if handler_target not in block_entry_stack:
                        block_entry_stack[handler_target] = stk[:]
                        worklist.append(handler_target)
                    # Record handler metadata on the block (like CPython b_lasti).
                    handler_target.exc_lasti = (op != _SETUP_FINALLY)
                    handler_target.exc_depth_adj = _opcode_stack_effect_jump(op)
                    handler_target.exc_depth_sub = 1 if op == _SETUP_WITH else 0
                    stk.append(handler_target)
                elif op == _POP_BLOCK:
                    if stk:
                        # Only empty in unreachable blocks or malformed code
                        stk.pop()
                elif instr.jump is not None:
                    target = instr.jump
                    if target not in block_entry_stack:
                        block_entry_stack[target] = stk[:]
                        worklist.append(target)

            # Propagate to fallthrough successor.
            # Match CPython's label_exception_targets, which always follows
            # b_next unconditionally.
            if b.next_block is not None and b.next_block not in block_entry_stack:
                block_entry_stack[b.next_block] = stk
                worklist.append(b.next_block)

        # --- Phase 2: emit exception table entries ---
        # cur_handler is Block or None (like CPython's basicblock *handler).
        # all_entries collects (start, end, handler_block) 3-tuples.
        all_entries = []
        cur_handler = None   # type: Block or None
        cur_start = -1
        instr_offset = 0
        
        def close_dead_block(cur_handler, cur_start, offset, all_entries):
            # Close any open range
            if cur_handler is not None and cur_start < offset:
                all_entries.append((cur_start, offset, cur_handler))
            

        for block in blocks:
            entry = block_entry_stack.get(block)
            if entry is None:
                close_dead_block(cur_handler, cur_start, block.offset, all_entries)
                cur_handler = None
                cur_start = -1
                continue

            # Reconcile cur_handler with this block's entry stack top.
            new_handler = entry[-1] if entry else None
            if new_handler is not cur_handler:
                close_dead_block(cur_handler, cur_start, block.offset, all_entries)
                cur_handler = new_handler
                cur_start = block.offset

            stk = entry[:]
            instr_offset = block.offset

            for instr in block.instructions:
                op = instr.opcode
                instr_size = instr.size()

                if instr.is_setup_pseudo_code(op):
                    # All are 0-byte pseudos; close enclosing handler at instr_offset.
                    close_dead_block(cur_handler, cur_start, instr_offset, all_entries)
                    handler_target = instr.jump
                    stk.append(handler_target)
                    cur_handler = handler_target
                    cur_start = instr_offset + instr_size

                elif op == _POP_BLOCK:
                    close_dead_block(cur_handler, cur_start, instr_offset, all_entries)
                    if stk:
                        stk.pop()
                    cur_handler = stk[-1] if stk else None
                    cur_start = instr_offset  # _POP_BLOCK encodes as 0 bytes

                instr_offset += instr_size

        if not all_entries:
            return ''
        result = []
        for entry in all_entries:
            start, end, handler_block = entry[0], entry[1], entry[2]
            if end <= start:
                continue
            lasti = handler_block.exc_lasti
            depth_adjust = handler_block.exc_depth_adj
            depth_sub = handler_block.exc_depth_sub
            # depth = value stack depth just before handle_operation_error pushes
            # lasti (if lasti=True) and the exception object.
            # handler_block.initial_depth was seeded by emit_jump:
            #   initial_depth = depth_at_SETUP + depth_adjust
            #   => depth = initial_depth - depth_adjust - depth_sub
            depth = handler_block.initial_depth - depth_adjust - depth_sub
            if depth < 0:
                continue
            _encode_varint(result, start // 2, msb=0x80)
            _encode_varint(result, (end - start) // 2)
            _encode_varint(result, handler_block.offset // 2)
            dl = (depth << 1) | (1 if lasti else 0)
            _encode_varint(result, dl)
        return ''.join(result)

    def assemble(self):
        """Build a PyCode object."""
        blocks, size = self._finalize_blocks()
        stack_depth = self._stacksize(blocks)
        positions = self._build_positions(blocks)
        consts_w = self.consts_w[:]
        names = _list_from_dict(self.names)
        var_names = _list_from_dict(self.var_names)
        cell_names = _list_from_dict(self.cell_vars)
        free_names = _list_from_dict(self.free_vars, len(cell_names))
        flags = self._get_code_flags()
        bytecode = self._build_code(blocks, size)
        # (Only) inherit compilerflags in PyCF_MASK
        flags |= (self.compile_info.flags & consts.PyCF_MASK)
        if not we_are_translated():
            self._final_blocks = blocks
        exceptiontable = self._build_exceptiontable(blocks)
        return PyCode(self.space,
                      self.argcount,
                      self.posonlyargcount,
                      self.kwonlyargcount,
                      len(self.var_names),
                      stack_depth,
                      flags,
                      bytecode,
                      list(consts_w),
                      names,
                      var_names,
                      self.compile_info.filename,
                      self.name,
                      self.qualname,
                      self.first_lineno,
                      positions,
                      free_names,
                      cell_names,
                      self.compile_info.hidden_applevel,
                      exceptiontable=exceptiontable)

    def extend_blocks(self, blocks):
        # Inline small unconditional lineno-less RETURN_VALUE blocks into their
        # jump predecessors. Equivalent to CPython's extend_block() (compile.c).
        # Processing in reverse (leaves first) collapses chains in one pass.
        MAX_COPY_SIZE = 4
        for idx in range(len(blocks) - 1, -1, -1):
            block = blocks[idx]
            if not block.instructions or not block.cant_add_instructions:
                continue
            last = block.instructions[-1]
            if last.opcode not in (ops.JUMP_FORWARD, ops.JUMP_ABSOLUTE):
                continue
            target = last.jump
            if target is None or not target.instructions:
                continue
            if len(target.instructions) > MAX_COPY_SIZE:
                continue
            for instr in target.instructions:
                if instr.opcode == ops.RETURN_VALUE:
                    break
            else:
                continue
            has_lineno = False
            for instr in target.instructions:
                if instr.position_info[0] != -1:
                    has_lineno = True
                    break
            if has_lineno:
                continue
            # Inline: replace the JUMP with NOP (keeping its lineno, like CPython's
            # last->i_opcode = NOP), then append copies of target's instructions.
            last.opcode = ops.NOP
            last.jump = None
            block.cant_add_instructions = False
            for instr in target.instructions:
                block.emit_instr(instr.copy())

    def duplicate_exits_without_lineno(self, blocks):
        from pypy.interpreter.astcompiler.codegen import view
        def should_mark_block(block):
            # CPython: only mark exit blocks (b_exit=1), i.e. blocks containing
            # RETURN_VALUE or RERAISE, with all instructions having no lineno.
            has_exit = False
            for instr in block.instructions:
                if instr.opcode in (ops.RETURN_VALUE, ops.RERAISE):
                    has_exit = True
                if instr.position_info[0] != -1:
                    return False
                if instr.jump and (instr.jump.marked & 1) == 0:
                    return False
            if not has_exit:
                return False
            if block.next_block and not block.cant_add_instructions:
                return (block.next_block.marked & 1) == 1
            return True
        # this is a bit of a mess. we want *two* pieces of info in marked, the
        # number of predecessors and the "do I need to duplicate". left-shift
        # marked to have a bit free for the latter
        for block in blocks:
            block.marked <<= 1

        # mark blocks that are paths to an exit without meeting an instruction
        # with a line number. uses the fact that blocks is a post-order
        any_mark = False
        for i in range(len(blocks) - 1, -1, -1):
            block = blocks[i]
            # mark block if all instructions in block have -1 as the lineno
            # *and* all target blocks are also marked
            mark = should_mark_block(block)
            block.marked |= mark
            any_mark |= mark

        i = 0
        if not any_mark:
            i = len(blocks)

        # Build a successor dict to support O(1) insertion of copied blocks.
        # After the while loop we linearise the chain back into blocks[].
        # In CPython this is done by via a double linked list
        successor = {}
        for idx in range(len(blocks) - 1):
            successor[blocks[idx]] = blocks[idx + 1]
        if blocks:
            successor[blocks[-1]] = None
        any_copy = False

        while i < len(blocks):
            block = blocks[i]
            i += 1
            if (block.marked >> 1) == 0:
                # dead block
                continue
            j = 0
            while j < len(block.instructions):
                instr = block.instructions[j]
                j += 1
                target = instr.jump
                if target is None:
                    continue
                if instr.is_setup_pseudo_code(instr.opcode):
                    continue # don't do this for exception handlers
                # only do something if the target has no position info (lowest
                # bit set)
                if not target.marked & 1:
                    continue

                # path leading to automatically inserted return or reraise,
                # without line number

                # if it's an unconditional jump, inline it (single predecessor)
                # or copy it (multiple predecessors, matching CPython behaviour).
                if instr.opcode in (ops.JUMP_FORWARD, ops.JUMP_ABSOLUTE) and (target.marked >> 1) <= 1:
                    # Skip if target is a RERAISE-only block: duplicating it
                    # INTO this block would place the RERAISE inside the byte
                    # range of an enclosing try-body's exception-table entry
                    # (body blocks emitted by _visit_try_except/_visit_try_finally
                    # have a table entry body.offset...exc.offset, and the
                    # duplicated RERAISE would incorrectly fall inside that
                    # range, dispatching to the inner handler instead of the
                    # outer reraise cleanup).  Mirrors the RERAISE-only skip
                    # in the other branch below.
                    if (len(target.instructions) == 1 and
                            target.instructions[0].opcode == ops.RERAISE):
                        continue
                    assert block.cant_add_instructions
                    block.instructions.pop()
                    block.cant_add_instructions = False
                    j -= 1
                    target.marked -= 2 # one fewer incoming links
                    for target_instr in target.instructions:
                        target_instr = target_instr.copy()
                        if target_instr.position_info[0] == -1:
                            target_instr.position_info = instr.position_info
                        copy = target_instr.copy()
                        if copy.jump:
                            copy.jump.marked += 2
                        block.emit_instr(copy)
                    if target.next_block and not block.cant_add_instructions:
                        new_instr = Instruction(ops.JUMP_ABSOLUTE, position_info=instr.position_info)
                        new_instr.jump = target.next_block
                        target.next_block.marked += 2
                        block.emit_instr(new_instr)

                elif (target.marked >> 1) > 1:
                    # Don't copy blocks whose only instructions are RERAISE.
                    # Such blocks live inside exception-handler bodies emitted by
                    # _visit_try_finally (after no_position_info()).  Copying them
                    # appends the copy after all handler blocks, placing the RERAISE
                    # outside the enclosing try/except exception-table range.
                    # handle_operation_error then falls back to the block stack and
                    # creates a SApplicationException that breaks PUSH_EXC_INFO.
                    # Leaving the original block in place keeps it within range.
                    # Position accuracy is unaffected: RERAISE uses attach_tb=False
                    # so no traceback entry is ever generated at the RERAISE site.
                    if (len(target.instructions) == 1 and
                            target.instructions[0].opcode == ops.RERAISE):
                        continue
                    # copy the block, it has more than one predecessor
                    target.marked -= 2 # one fewer incoming links for old target
                    newtarget = target.copy()
                    newtarget.marked = 1 << 1 # new target has one incoming link
                    newtarget.instructions[0].position_info = instr.position_info
                    for copied_op in newtarget.instructions:
                        if copied_op.jump:
                            copied_op.jump.marked += 2
                    # deal with fall-through of copied target block - rare, but
                    # see test_if_call_or_call_bug
                    if target.next_block and not newtarget.cant_add_instructions:
                        new_instr = Instruction(ops.JUMP_ABSOLUTE, position_info=self.position_info)
                        new_instr.jump = target.next_block
                        target.next_block.marked += 2
                        newtarget.emit_instr(new_instr)
                    instr.jump = newtarget
                    successor[newtarget] = successor.get(target)
                    successor[target] = newtarget
                    blocks.append(newtarget)  # add to worklist for outer loop
                    any_copy = True

        if any_copy:
            new_blocks = []
            current = blocks[0]
            while current is not None:
                new_blocks.append(current)
                current = successor[current]
            assert len(new_blocks) == len(blocks)
            blocks[0:len(blocks)] = new_blocks

        for block in blocks:
            if (block.instructions and block.next_block and
                    not block.cant_add_instructions and
                    block.next_block.marked & 1):
                # now assign the linenumber to the "fallthrough" implicit
                # return block too
                block.next_block.instructions[0].position_info = block.instructions[-1].position_info
            block.marked >>= 1


class DeadCode(object):
    def __init__(self, codegen):
        self.codegen = codegen

    def __enter__(self, *args):
        self.old_value = self.codegen._is_dead_code
        self.codegen._is_dead_code = True

    def __exit__(self, *args):
        self.codegen._is_dead_code = self.old_value


class MatchContext(object):
    def __init__(self, codegen):
        self.codegen = codegen
        self._init_names()
        self.allow_always_passing = False
        # the extra objects currently on the stack that need cleaning up
        self.on_top = 0
        self._reset_cleanup_blocks()

    def _init_names(self):
        self.names_stored = {} # name -> int
        self.names_list = [] # list of names in order
        self.names_origins = [] # ast nodes to blame if a name repeats

    def add_name(self, name, node, codegen):
        index = self.names_stored.get(name, -1)
        if index >= 0:
            # already exists
            previous_node = self.names_origins[index]
            codegen.error(
                "multiple assignments to name '%s' in pattern, previous one was on line %s" % (
                    name, previous_node.lineno), node)
        else:
            self.names_stored[name] = len(self.names_stored)
            self.names_list.append(name)
            self.names_origins.append(node)

    def _reset_cleanup_blocks(self):
        self.next = self.codegen.new_block()
        # the cleanup blocks will all be chained in reverse order, each one
        # contains a POP_TOP and a jump to the next one
        self.cleanup_blocks = [self.next]

    def next_case(self, position_node=None):
        # add the POP_TOP instructions to the cleanup blocks
        for index in range(len(self.cleanup_blocks) - 1, 0, -1):
            block = self.cleanup_blocks[index]
            self.codegen.use_next_block(block)
            if position_node:
                self.codegen.update_position(position_node)
            self.codegen.emit_op(ops.POP_TOP)
        self.codegen.use_next_block(self.next)
        self._reset_cleanup_blocks()
        self._init_names()

    def emit_fail_jump(self, op, cleanup=0):
        # emits a (conditional or unconditional) jump to the cleanup block (ie,
        # failure) with the right number of POP_TOPs
        cleanup += self.on_top + len(self.names_stored)
        while cleanup >= len(self.cleanup_blocks):
            self.cleanup_blocks.append(self.codegen.new_block())
        target = self.cleanup_blocks[cleanup]
        self.codegen.emit_jump(op, target)

    def __enter__(self, *args):
        self.old_context = self.codegen.match_context
        self.codegen.match_context = self
        return self

    def __exit__(self, *args):
        self.codegen.match_context = self.old_context

class SubMatchContext(object):
    """ context manager for setting allow_always_passing to True and then
    restoring the old value on leaving. """
    def __init__(self, codegen):
        self.codegen = codegen

    def __enter__(self, *args):
        match_context = self.codegen.match_context
        self.old_value = match_context.allow_always_passing
        match_context.allow_always_passing = True
        return match_context

    def __exit__(self, *args):
        self.codegen.match_context.allow_always_passing = self.old_value

def _first_real_lineno(instructions):
    """Return the position_info[0] of the first non-pseudo instruction, or -1."""
    for instr in instructions:
        if not is_pseudo_opcode(instr.opcode):
            return instr.position_info[0]
    return -1


def _remove_redundant_nops(block):
    mininum_lineno = sys.maxint
    prevlineno = -1
    source = 0
    dest = 0
    instructions = block.instructions
    while source < len(instructions):
        op = instructions[source]
        source += 1
        lineno = op.position_info[0]
        if 0 < lineno < mininum_lineno:
            mininum_lineno = lineno
        if op.opcode == ops.NOP:
            if lineno == -1 or lineno == prevlineno:
                continue
            if source < len(instructions):
                # skip pseudo instructions to find the next real instruction
                next_lineno = _first_real_lineno(instructions[source:])
                if next_lineno == -1:
                    # no real instruction found - fall back to the raw next
                    # instruction's lineno (old behaviour for non-pseudo cases)
                    next_lineno = instructions[source].position_info[0]
                    if is_pseudo_opcode(instructions[source].opcode):
                        next_lineno = -1  # don't remove on all-pseudo tail
                if next_lineno >= 0 and lineno == next_lineno:
                    continue
            else:
                # last instruction in block is a NOP, check the next block.
                # Use only non-pseudo instructions: pseudo ones (SETUP_FINALLY
                # etc.) carry position info from the surrounding code but are
                # not emitted in the bytecode, so they must not count as the
                # "next instruction" for deduplication purposes.
                if block.next_block.instructions:
                    next_lineno = _first_real_lineno(block.next_block.instructions)
                    # Only remove if a real (non-pseudo) instruction was found
                    # with the same line. A block of all-pseudo instructions
                    # must not count as the "next instruction" here.
                    if next_lineno >= 0 and lineno == next_lineno:
                        continue
        prevlineno = lineno
        instructions[dest] = op
        dest += 1
    if dest != len(instructions):
        del instructions[dest:]
    return mininum_lineno

def remove_redundant_nops(blocks):
    mininum_lineno = sys.maxint
    for block in blocks:
        mininum_lineno = min(_remove_redundant_nops(block), mininum_lineno)
    if mininum_lineno == sys.maxint:
        mininum_lineno = 1
    return mininum_lineno


def _is_swappable(opcode):
    """Return True if this opcode can be reordered by apply_static_swaps."""
    return opcode == ops.STORE_FAST or opcode == ops.POP_TOP


def _stores_to(instr):
    """Return the oparg if STORE_FAST, else -1."""
    if instr.opcode == ops.STORE_FAST:
        return instr.arg
    return -1


def _next_swappable(instructions, start, lineno):
    """Return index of next swappable instruction after start, or -1."""
    i = start + 1
    while i < len(instructions):
        instr = instructions[i]
        if instr.opcode == ops.NOP or is_pseudo_opcode(instr.opcode):
            i += 1
            continue
        if lineno >= 0 and instr.position_info[0] != lineno:
            return -1
        if _is_swappable(instr.opcode):
            return i
        return -1
    return -1


def _apply_static_swaps(instructions, i):
    """Port of CPython's apply_static_swaps (compile.c).

    Scan backwards from position i for SWAP instructions and try to
    eliminate each one by statically reordering the following
    STORE_FAST/POP_TOP instructions instead of swapping at runtime.
    """
    while i >= 0:
        instr = instructions[i]
        if instr.opcode == ops.NOP or is_pseudo_opcode(instr.opcode):
            i -= 1
            continue
        if instr.opcode != ops.SWAP:
            if _is_swappable(instr.opcode):
                i -= 1
                continue
            return  # can't reason past this instruction
        # found a SWAP(n): find the j-th and k-th (= n-th) swappable followers
        j = _next_swappable(instructions, i, -1)
        if j < 0:
            return
        k = j
        lineno = instructions[j].position_info[0]
        for _ in range(instr.arg - 1):
            k = _next_swappable(instructions, k, lineno)
            if k < 0:
                return
        # check for conflicting stores
        store_j = _stores_to(instructions[j])
        store_k = _stores_to(instructions[k])
        if store_j >= 0 or store_k >= 0:
            if store_j == store_k:
                return
            for idx in range(j + 1, k):
                store_idx = _stores_to(instructions[idx])
                if store_idx >= 0 and (store_idx == store_j or store_idx == store_k):
                    return
        # success: replace SWAP with NOP and swap the two instructions
        instr.opcode = ops.NOP
        instructions[j], instructions[k] = instructions[k], instructions[j]
        i -= 1


def _encode_varint(result, value, msb=0):
    """Append a CPython-3.11-compatible varint encoding of value to result.
    Encodes 6 bits per byte, MSB first.  Bit 6 (0x40) is the continuation
    flag (set on every byte except the last).  Bit 7 (0x80) is the
    start-of-entry marker; pass msb=0x80 only on the first byte of an
    exception-table entry, 0 otherwise (matches CPython 3.11's
    assemble_emit_exception_table_item)."""
    assert value >= 0
    # Find the highest non-zero 6-bit chunk (shift counted in bits).
    shift = 0
    v = value >> 6
    while v:
        shift += 6
        v >>= 6
    # Write from the most-significant chunk down; all but the last get
    # the continuation bit.  msb (start marker) goes only on the first byte.
    while shift > 0:
        chunk = (value >> shift) & 63
        result.append(chr(chunk | 64 | msb))
        msb = 0
        shift -= 6
    result.append(chr((value & 63) | msb))


def _list_from_dict(d, offset=0):
    result = [None] * len(d)
    for obj, index in d.iteritems():
        result[index - offset] = obj
    return result


_static_opcode_stack_effects = {
    ops.NOP: 0,

    ops.POP_TOP: -1,
    ops.ROT_TWO: 0,
    ops.ROT_THREE: 0,
    ops.ROT_FOUR: 0,
    ops.DUP_TOP: 1,
    ops.DUP_TOP_TWO: 2,
    ops.COPY: 1,

    ops.UNARY_POSITIVE: 0,
    ops.UNARY_NEGATIVE: 0,
    ops.UNARY_NOT: 0,
    ops.UNARY_INVERT: 0,

    ops.LIST_APPEND: -1,
    ops.LIST_EXTEND: -1,
    ops.LIST_TO_TUPLE: 0,
    ops.SET_ADD: -1,
    ops.SET_UPDATE: -1,
    ops.MAP_ADD: -2,

    ops.BINARY_POWER: -1,
    ops.BINARY_MULTIPLY: -1,
    ops.BINARY_MODULO: -1,
    ops.BINARY_ADD: -1,
    ops.BINARY_SUBTRACT: -1,
    ops.BINARY_SUBSCR: -1,
    ops.BINARY_FLOOR_DIVIDE: -1,
    ops.BINARY_TRUE_DIVIDE: -1,
    ops.BINARY_MATRIX_MULTIPLY: -1,
    ops.BINARY_LSHIFT: -1,
    ops.BINARY_RSHIFT: -1,
    ops.BINARY_AND: -1,
    ops.BINARY_OR: -1,
    ops.BINARY_XOR: -1,

    ops.INPLACE_FLOOR_DIVIDE: -1,
    ops.INPLACE_TRUE_DIVIDE: -1,
    ops.INPLACE_ADD: -1,
    ops.INPLACE_SUBTRACT: -1,
    ops.INPLACE_MULTIPLY: -1,
    ops.INPLACE_MODULO: -1,
    ops.INPLACE_POWER: -1,
    ops.INPLACE_MATRIX_MULTIPLY: -1,
    ops.INPLACE_LSHIFT: -1,
    ops.INPLACE_RSHIFT: -1,
    ops.INPLACE_AND: -1,
    ops.INPLACE_OR: -1,
    ops.INPLACE_XOR: -1,

    ops.STORE_SUBSCR: -3,
    ops.DELETE_SUBSCR: -2,

    ops.GET_ITER: 0,
    ops.FOR_ITER: 1,

    ops.PRINT_EXPR: -1,

    ops.LOAD_BUILD_CLASS: 1,
    ops.POP_EXCEPT: -1,
    ops.PUSH_EXC_INFO: 1,
    ops.CHECK_EXC_MATCH: 0,
    _SETUP_FINALLY: 0,   # marker only; handler depth set via forced_initial_depth
    _SETUP_CLEANUP: 0,   # marker only; handler depth set via forced_initial_depth
    _SETUP_WITH:    0,   # marker only; handler depth set via forced_initial_depth
    _POP_BLOCK: 0,       # marker only
    ops.BEFORE_WITH: 1,

    ops.RETURN_VALUE: -1,
    ops.YIELD_VALUE: 0,
    ops.YIELD_FROM: -1,
    ops.COMPARE_OP: -1,
    ops.IS_OP: -1,
    ops.CONTAINS_OP: -1,

    ops.LOAD_METHOD: 1,

    ops.LOAD_NAME: 1,
    ops.STORE_NAME: -1,
    ops.DELETE_NAME: 0,

    ops.LOAD_FAST: 1,
    ops.STORE_FAST: -1,
    ops.DELETE_FAST: 0,

    ops.LOAD_ATTR: 0,
    ops.STORE_ATTR: -2,
    ops.DELETE_ATTR: -1,

    ops.LOAD_GLOBAL: 1,
    ops.STORE_GLOBAL: -1,
    ops.DELETE_GLOBAL: 0,
    ops.DELETE_DEREF: 0,

    ops.LOAD_CLOSURE: 1,
    ops.LOAD_DEREF: 1,
    ops.STORE_DEREF: -1,
    ops.DELETE_DEREF: 0,

    ops.GET_AWAITABLE: 0,
    ops.BEFORE_ASYNC_WITH: 1,
    ops.GET_AITER: 0,
    ops.GET_ANEXT: 1,
    ops.GET_YIELD_FROM_ITER: 0,
    ops.END_ASYNC_FOR: -3,

    ops.LOAD_CONST: 1,

    ops.IMPORT_STAR: -1,
    ops.IMPORT_NAME: -1,
    ops.IMPORT_FROM: 1,

    ops.JUMP_FORWARD: 0,
    ops.JUMP_ABSOLUTE: 0,
    ops.JUMP_IF_TRUE_OR_POP: -1,
    ops.JUMP_IF_FALSE_OR_POP: -1,
    ops.POP_JUMP_IF_TRUE: -1,
    ops.POP_JUMP_IF_FALSE: -1,
    ops.POP_JUMP_FORWARD_IF_NONE: -1,
    ops.POP_JUMP_FORWARD_IF_NOT_NONE: -1,
    ops.JUMP_IF_NOT_EXC_MATCH: -2,

    ops.SETUP_ANNOTATIONS: 0,

    ops.DICT_MERGE: -1,
    ops.DICT_UPDATE: -1,

    # TODO
    ops.BUILD_LIST_FROM_ARG: 1,
    ops.LOAD_REVDB_VAR: 1,

    ops.LOAD_CLASSDEREF: 1,
    ops.LOAD_ASSERTION_ERROR: 1,

    ops.RERAISE: -1,

    ops.WITH_EXCEPT_START: 1,

    ops.GET_LEN: 1,
    ops.MATCH_MAPPING: 1,
    ops.MATCH_SEQUENCE: 1,
    ops.MATCH_KEYS: 1,
    ops.COPY_DICT_WITHOUT_KEYS: 0,
    ops.SWAP: 0,
    ops.MATCH_CLASS: -1,

    ops.CHECK_EG_MATCH: 0,
    ops.PREP_RERAISE_STAR: -1,
}


def _compute_UNPACK_SEQUENCE(arg):
    return arg - 1

def _compute_UNPACK_EX(arg):
    return (arg & 0xFF) + (arg >> 8)

def _compute_BUILD_TUPLE(arg):
    return 1 - arg

def _compute_BUILD_LIST(arg):
    return 1 - arg

def _compute_BUILD_SET(arg):
    return 1 - arg

def _compute_BUILD_MAP(arg):
    return 1 - 2 * arg

def _compute_MAKE_FUNCTION(arg):
    return  -bool(arg & 0x01) - bool(arg & 0x02) - bool(arg & 0x04) - bool(arg & 0x08)

def _compute_BUILD_SLICE(arg):
    if arg == 3:
        return -2
    else:
        return -1

def _compute_RAISE_VARARGS(arg):
    return -arg

def _compute_CALL_FUNCTION(arg):
    return -arg

def _compute_CALL_FUNCTION_KW(arg):
    return -arg - 1

def _compute_CALL_FUNCTION_EX(arg):
    assert arg == 0 or arg == 1
    # either -1 or -2
    return -arg - 1

def _compute_CALL_METHOD(arg):
    return -arg - 1

def _compute_CALL_METHOD_KW(arg):
    return -arg - 2

def _compute_FORMAT_VALUE(arg):
    if (arg & consts.FVS_MASK) == consts.FVS_HAVE_SPEC:
        return -1
    return 0

def _compute_BUILD_STRING(arg):
    return 1 - arg

def _compute_BUILD_CONST_KEY_MAP(arg):
    return  -arg


_stack_effect_computers = {}
for name, func in globals().items():
    if name.startswith("_compute_"):
        func._always_inline_ = True
        _stack_effect_computers[getattr(ops, name[9:])] = func
for op, value in _static_opcode_stack_effects.iteritems():
    def func(arg, _value=value):
        return _value
    func._always_inline_ = True
    _stack_effect_computers[op] = func
del name, func, op, value


def _opcode_stack_effect(op, arg):
    """Return the stack effect of a opcode an its argument."""
    if Instruction.is_setup_pseudo_code(op) or op == _POP_BLOCK:
        return 0
    if we_are_translated():
        for possible_op in ops.unrolling_opcode_descs:
            # EXTENDED_ARG should never get in here.
            if possible_op.index == ops.EXTENDED_ARG:
                continue
            if op == possible_op.index:
                return _stack_effect_computers[possible_op.index](arg)
        else:
            raise KeyError("unknown opcode: %s" % (op,))
    else:
        try:
            return _static_opcode_stack_effects[op]
        except KeyError:
            try:
                return _stack_effect_computers[op](arg)
            except KeyError:
                raise KeyError("Unknown stack effect for %s (%s)" %
                               (ops.opname[op], op))

def _opcode_stack_effect_jump(op):
    if op == ops.FOR_ITER:
        return -1
    elif op == _SETUP_FINALLY:
        # Handler block receives exc pushed by handle_operation_error.
        # lasti=False so only exc is pushed: +1.
        return 1
    elif op == _SETUP_CLEANUP:
        # Like _SETUP_FINALLY but lasti=True: handle_operation_error also pushes
        # lasti_int before exc, so +2.
        return 2
    elif op == _SETUP_WITH:
        # lasti=True so handle_operation_error pushes lasti+exc (+2 items), but
        # BEFORE_WITH already pushed __enter__result at depth D=N+1.  The runtime
        # entry stack is N+2, so the jump effect is D+1-D = +1 (not +2).  Combined
        # with depth_sub=1: table depth = (D+1) - 1 - 1 = D-1 = N (base+__exit__).
        return 1
    elif op == ops.JUMP_IF_TRUE_OR_POP:
        return 0
    elif op == ops.JUMP_IF_FALSE_OR_POP:
        return 0
    elif op == ops.JUMP_IF_NOT_EXC_MATCH:
        return -2
    elif op == ops.POP_JUMP_IF_TRUE:
        return -1
    elif op == ops.POP_JUMP_IF_FALSE:
        return -1
    elif op == ops.POP_JUMP_FORWARD_IF_NONE:
        return -1
    elif op == ops.POP_JUMP_FORWARD_IF_NOT_NONE:
        return -1
    elif op == ops.JUMP_FORWARD:
        return 0
    elif op == ops.JUMP_ABSOLUTE:
        return 0
    raise KeyError


def _debug_print_blocks(blocks):
    labels = {block: i for (i, block) in enumerate(blocks)}
    for block in blocks:
        print "L%s:" % labels[block]
        for instruction in block.instructions:
            print instruction
