"""
Dynamo implementations of CPython's PyObject_* default slot algorithms.

Analogous to CPython's Objects/object.c, this module holds the general
dispatch machinery that is independent of any specific type.
Per-type hook implementations (nb_bool_impl, tp_richcompare_impl, tp_getattro_impl,
etc.) live in their respective VT files.
"""

import abc
import collections
import enum
import sys
import types
import typing
from functools import lru_cache, partial
from typing import NoReturn, TYPE_CHECKING

import torch
from torch._C._dynamo import (
    get_type_slots,
    has_slot,
    PyMappingSlots,
    PyNumberSlots,
    PySequenceSlots,
    PyTypeSlots,
)

from .. import graph_break_hints, polyfills, variables
from ..exc import (
    handle_observed_exception,
    ObservedTypeError,
    raise_observed_exception,
    raise_type_error,
    UnhandledDescriptorError,
    unimplemented,
)
from ..source import AttrSource, Source
from ..utils import istype
from .base import (
    AsPythonConstantNotImplementedError,
    AttrMutationKind,
    maybe_get_python_type,
    NO_SUCH_SUBOBJ,
    VariableTracker,
)
from .constant import ConstantVariable


if TYPE_CHECKING:
    from ..symbolic_convert import InstructionTranslatorBase


def vt_identity_compare(
    left: VariableTracker,
    right: VariableTracker,
) -> "VariableTracker | None":
    """Try to determine Python identity (left is right) at trace time.

    Returns ConstantVariable(True/False) if determinable, else None.
    Mirrors the logic in BuiltinVariable's handle_is handler.
    """
    if left is right:
        return ConstantVariable.create(True)

    left_val = left.get_real_python_backed_value()
    right_val = right.get_real_python_backed_value()
    left_known = left_val is not NO_SUCH_SUBOBJ
    right_known = right_val is not NO_SUCH_SUBOBJ

    if left_known and right_known:
        return (
            ConstantVariable.create(True)
            if left_val is right_val
            else ConstantVariable.create(False)
        )

    # One side has a concrete backing object, the other doesn't — they can't
    # be the same object.
    if left_known != right_known:
        return ConstantVariable.create(False)

    # Objects created during tracing: VT identity = Python identity.
    from .dicts import ConstDictVariable
    from .lists import ListVariable
    from .misc import TracebackVariable
    from .sets import SetVariable

    if isinstance(
        left, (ConstDictVariable, ListVariable, SetVariable, TracebackVariable)
    ):
        return ConstantVariable.create(False)

    # Different Python types can never be the same object.
    try:
        if left.python_type() is not right.python_type():
            return ConstantVariable.create(False)
    except NotImplementedError:
        pass

    # Different exception types are never identical.
    if (
        istype(left, variables.ExceptionVariable)
        and istype(right, variables.ExceptionVariable)
        and left.exc_type is not right.exc_type  # type: ignore[attr-defined]
    ):
        return ConstantVariable.create(False)

    return None


def binop_type_error(
    tx: "InstructionTranslatorBase",
    v: VariableTracker,
    w: VariableTracker,
    op_symbol: str,
) -> NoReturn:
    raise_type_error(
        tx,
        f"unsupported operand type(s) for {op_symbol}: '{v.python_type_name()}' and '{w.python_type_name()}'",
    )


@lru_cache(maxsize=256)
def _get_cached_slots(obj_type: type) -> tuple[int, int, int, int]:
    """Get all type slots for a type (cached)."""
    return get_type_slots(obj_type)


def type_implements_sq_slot(obj_type: type, slot: int) -> bool:
    """Check whether obj_type implements the given sq slot."""
    seq_slots, _, _, _ = _get_cached_slots(obj_type)
    return has_slot(seq_slots, slot)


def type_implements_mp_slot(obj_type: type, slot: int) -> bool:
    """Check whether obj_type implements the given mp slot."""
    _, map_slots, _, _ = _get_cached_slots(obj_type)
    return has_slot(map_slots, slot)


# PySequenceSlots
type_implements_sq_item = partial(type_implements_sq_slot, slot=PySequenceSlots.SQ_ITEM)
type_implements_sq_length = partial(
    type_implements_sq_slot, slot=PySequenceSlots.SQ_LENGTH
)
type_implements_sq_concat = partial(
    type_implements_sq_slot, slot=PySequenceSlots.SQ_CONCAT
)
type_implements_sq_inplace_concat = partial(
    type_implements_sq_slot, slot=PySequenceSlots.SQ_INPLACE_CONCAT
)
type_implements_sq_contains = partial(
    type_implements_sq_slot, slot=PySequenceSlots.SQ_CONTAINS
)
type_implements_sq_ass_item = partial(
    type_implements_sq_slot, slot=PySequenceSlots.SQ_ASS_ITEM
)
type_implements_sq_repeat = partial(
    type_implements_sq_slot, slot=PySequenceSlots.SQ_REPEAT
)

type_implements_sq_inplace_repeat = partial(
    type_implements_sq_slot, slot=PySequenceSlots.SQ_INPLACE_REPEAT
)

# PyMappingSlots
type_implements_mp_length = partial(
    type_implements_mp_slot, slot=PyMappingSlots.MP_LENGTH
)
type_implements_mp_subscript = partial(
    type_implements_mp_slot, slot=PyMappingSlots.MP_SUBSCRIPT
)
type_implements_mp_ass_subscript = partial(
    type_implements_mp_slot, slot=PyMappingSlots.MP_ASS_SUBSCRIPT
)
type_implements_mp_length = partial(
    type_implements_mp_slot, slot=PyMappingSlots.MP_LENGTH
)


def type_implements_nb_slot(obj_type: type, slot: int) -> bool:
    """Check whether obj_type implements the nb slot."""
    _, _, number_slots, _ = _get_cached_slots(obj_type)
    return has_slot(number_slots, slot)


type_implements_nb_add = partial(type_implements_nb_slot, slot=PyNumberSlots.NB_ADD)
type_implements_nb_subtract = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_SUBTRACT
)
type_implements_nb_multiply = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_MULTIPLY
)
type_implements_nb_remainder = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_REMAINDER
)
type_implements_nb_power = partial(type_implements_nb_slot, slot=PyNumberSlots.NB_POWER)
type_implements_nb_negative = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_NEGATIVE
)
type_implements_nb_positive = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_POSITIVE
)
type_implements_nb_absolute = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_ABSOLUTE
)
type_implements_nb_bool = partial(type_implements_nb_slot, slot=PyNumberSlots.NB_BOOL)
type_implements_nb_invert = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_INVERT
)
type_implements_nb_lshift = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_LSHIFT
)
type_implements_nb_rshift = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_RSHIFT
)
type_implements_nb_and = partial(type_implements_nb_slot, slot=PyNumberSlots.NB_AND)
type_implements_nb_xor = partial(type_implements_nb_slot, slot=PyNumberSlots.NB_XOR)
type_implements_nb_or = partial(type_implements_nb_slot, slot=PyNumberSlots.NB_OR)
type_implements_nb_int = partial(type_implements_nb_slot, slot=PyNumberSlots.NB_INT)
type_implements_nb_float = partial(type_implements_nb_slot, slot=PyNumberSlots.NB_FLOAT)
type_implements_nb_inplace_add = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_INPLACE_ADD
)
type_implements_nb_inplace_subtract = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_INPLACE_SUBTRACT
)
type_implements_nb_inplace_multiply = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_INPLACE_MULTIPLY
)
type_implements_nb_inplace_remainder = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_INPLACE_REMAINDER
)
type_implements_nb_inplace_power = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_INPLACE_POWER
)
type_implements_nb_inplace_lshift = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_INPLACE_LSHIFT
)
type_implements_nb_inplace_rshift = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_INPLACE_RSHIFT
)
type_implements_nb_inplace_and = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_INPLACE_AND
)
type_implements_nb_inplace_xor = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_INPLACE_XOR
)
type_implements_nb_inplace_or = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_INPLACE_OR
)
type_implements_nb_floor_divide = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_FLOOR_DIVIDE
)
type_implements_nb_true_divide = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_TRUE_DIVIDE
)
type_implements_nb_inplace_floor_divide = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_INPLACE_FLOOR_DIVIDE
)
type_implements_nb_inplace_true_divide = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_INPLACE_TRUE_DIVIDE
)
type_implements_nb_index = partial(type_implements_nb_slot, slot=PyNumberSlots.NB_INDEX)
type_implements_nb_matrix_multiply = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_MATRIX_MULTIPLY
)
type_implements_nb_inplace_matrix_multiply = partial(
    type_implements_nb_slot, slot=PyNumberSlots.NB_INPLACE_MATRIX_MULTIPLY
)


def type_implements_tp_iter(obj_type: type) -> bool:
    _, _, _, type_slot = _get_cached_slots(obj_type)
    return has_slot(type_slot, PyTypeSlots.TP_ITER)


def type_implements_tp_iternext(obj_type: type) -> bool:
    _, _, _, type_slot = _get_cached_slots(obj_type)
    return has_slot(type_slot, PyTypeSlots.TP_ITERNEXT)


def type_implements_tp_repr(obj_type: type) -> bool:
    """Check whether obj_type implements the tp_repr slot."""
    _, _, _, type_slot = _get_cached_slots(obj_type)
    return has_slot(type_slot, PyTypeSlots.TP_REPR)


def type_implements_tp_str(obj_type: type) -> bool:
    """Check whether obj_type implements the tp_str slot."""
    _, _, _, type_slot = _get_cached_slots(obj_type)
    return has_slot(type_slot, PyTypeSlots.TP_STR)


def type_implements_tp_call(obj_type: type) -> bool:
    """Check whether obj_type implements the tp_call slot."""
    _, _, _, type_slot = _get_cached_slots(obj_type)
    return has_slot(type_slot, PyTypeSlots.TP_CALL)


def pyiter_check(obj_type: type) -> bool:
    # ref: https://github.com/python/cpython/blob/3.13/Objects/abstract.c#L2891-L2897
    # CPython checks if tp_iternext != _PyObject_NextNotImplemented
    # Dynamo only sets the bit if __next__ is actually defined
    return type_implements_tp_iternext(obj_type)


def pysequence_check(obj_type: type) -> bool:
    """Implements PySequence_Check semantics for VariableTracker objects."""
    # ref: https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1714-L1721
    if issubclass(obj_type, dict):
        return False
    return type_implements_sq_item(obj_type)


def pyindex_check(obj_type: type) -> bool:
    """Implements _PyIndex_Check semantics for VariableTracker objects."""
    # ref: https://github.com/python/cpython/blob/3.13/Include/internal/pycore_abstract.h#L11-L17
    return type_implements_nb_index(obj_type)


def pycallable_check(obj_type: type) -> bool:
    """Implements PyCallable_Check: type(x)->tp_call != NULL.

    obj_type is the object's Python type (Py_TYPE(x)); a non-NULL tp_call
    slot on it means instances are callable.

    ref: https://github.com/python/cpython/blob/v3.13.0/Objects/call.c#L52-L57
    """
    return type_implements_tp_call(obj_type)


def pyiter_send(
    tx: "InstructionTranslatorBase", iter_: VariableTracker, arg: VariableTracker
) -> VariableTracker:
    """Implements PyIter_Send semantics for VariableTracker objects.

    ref: https://github.com/python/cpython/blob/51b511d7299f91a458e40d1ea997bd7e6cd3deef/Objects/abstract.c#L2930-L2953
    """

    tp_iternext = iter_.tp_iternext
    if arg.is_constant_none() and tp_iternext is not None:
        return iter_.tp_iternext_impl(tx)
    else:
        return iter_.call_method(tx, "send", [arg], {})


def pymapping_size(
    tx: "InstructionTranslatorBase", obj: "VariableTracker"
) -> "VariableTracker":
    # ref: https://github.com/python/cpython/blob/v3.13.3/Objects/abstract.c#L2308-L2330
    if obj.tp_as_mapping.mp_length:
        return obj.mp_length_impl(tx)

    if obj.tp_as_sequence.sq_length is not None:
        raise_type_error(tx, f"{obj.python_type_name()} is not a mapping")

    raise_type_error(tx, f"object of type {obj.python_type_name()} has no len()")


def generic_size(
    tx: "InstructionTranslatorBase", obj: "VariableTracker"
) -> "VariableTracker":
    # ref: https://github.com/python/cpython/blob/v3.13.3/Objects/abstract.c#L53-L69
    """
    Implements PyObject_Size/PyObject_Length semantics for VariableTracker objects.
    Dispatches to sq_length (sequences) or mp_length (mappings) depending on the VT type.
    """

    if obj.tp_as_sequence.sq_length:
        return obj.sq_length_impl(tx)
    return pymapping_size(tx, obj)


def generic_is_true(
    tx: "InstructionTranslatorBase", obj: VariableTracker
) -> VariableTracker:
    """Mirrors PyObject_IsTrue.

    https://github.com/python/cpython/blob/c09ccd9c429/Objects/object.c#L2135-L2158

    Resolution order: constants → nb_bool → mp_length/sq_length → truthy.
    """
    from .constant import ConstantVariable

    if obj.is_python_constant():
        try:
            return ConstantVariable.create(bool(obj.as_python_constant()))
        except Exception as e:
            raise_observed_exception(type(e), tx, args=[str(e)])

    if obj.tp_as_number.nb_bool:
        result = obj.nb_bool_impl(tx)
        if result is not None:
            return result

    try:
        length = generic_size(tx, obj)
        from .tensor import SymNodeVariable

        if isinstance(length, SymNodeVariable):
            return SymNodeVariable.create(tx, length.as_proxy() > 0)
        length_val = length.as_python_constant()
        if length_val < 0:
            raise_observed_exception(
                ValueError, tx, args=["__len__() should return >= 0"]
            )
        return ConstantVariable.create(length_val > 0)
    except ObservedTypeError:
        handle_observed_exception(tx)

    return ConstantVariable.create(True)


_repr_running: set[int] = set()


def generic_repr(
    tx: "InstructionTranslatorBase", obj: VariableTracker
) -> VariableTracker:
    """Mirrors PyObject_Repr with Py_ReprEnter/Py_ReprLeave cycle detection.

    https://github.com/python/cpython/blob/v3.13.3/Objects/object.c#L745-L778

    Resolution order: tp_repr -> TypeError if the result is not str.
    """
    obj_type = maybe_get_python_type(obj)

    tp_repr = obj.tp_repr
    if tp_repr is not None:
        obj_id = id(obj)
        if obj_id in _repr_running:
            sentinel = {list: "[...]", dict: "{...}", collections.deque: "[...]"}
            return ConstantVariable.create(sentinel.get(obj_type, "..."))
        _repr_running.add(obj_id)
        try:
            result = obj.tp_repr_impl(tx)
        finally:
            _repr_running.discard(obj_id)
        result_type = maybe_get_python_type(result)
        if not issubclass(result_type, str):
            if sys.version_info >= (3, 15):
                err_str = f"{obj.python_qualified_name()}.__repr__() must return a str, not int"
            else:
                err_str = f"__repr__ returned non-string (type {result_type.__name__})"
            raise_type_error(tx, err_str)
        return result

    raise_type_error(tx, f"object of type '{obj.python_type_name()}' has no repr")


def generic_str(
    tx: "InstructionTranslatorBase", obj: "VariableTracker"
) -> "VariableTracker":
    """Mirrors PyObject_Str semantics in Dynamo.

    https://github.com/python/cpython/blob/v3.13.3/Objects/object.c#L781-L829

    Resolution order: str identity check -> tp_str (tp_str_impl) -> tp_repr fallback.
    """
    from ..exc import TorchDynamoException

    if maybe_get_python_type(obj) is str:
        return obj

    try:
        if obj.tp_str and type(obj).tp_str_impl is not VariableTracker.tp_str_impl:
            result = obj.tp_str_impl(tx)
        else:
            result = generic_repr(tx, obj)
    except TorchDynamoException:
        raise
    except Exception as exc:
        raise_observed_exception(type(exc), tx, args=list(exc.args))

    result_type = maybe_get_python_type(result)
    if not issubclass(result_type, str):
        if sys.version_info >= (3, 15):
            err_str = f"{obj.python_qualified_name()}.__str__() must return a str, not {result.python_qualified_name()}"
        else:
            err_str = f"__str__ returned non-string (type {result_type.__name__})"
        raise_type_error(tx, err_str)
    return result


def generic_getitem(
    tx: "InstructionTranslatorBase",
    obj: VariableTracker,
    key: VariableTracker,
) -> VariableTracker:
    """CPython's PyObject_GetItem — dispatch to the type's mp_subscript/sq_item.

    PyObject_GetItem: https://github.com/python/cpython/blob/62a6e898e01/Objects/abstract.c#L155-L206

    CPython checks three branches in order:
      1. tp_as_mapping->mp_subscript  (L161-166)
      2. tp_as_sequence->sq_item      (L168-181) — only if key passes _PyIndex_Check
      3. PyType_Check(o)              (L183-203) — type[int] → GenericAlias/__class_getitem__

    Branch 1 is the common path (list, tuple, dict, range all have mp_subscript).
    Branch 2 fires for types with only sq_item (e.g. deque).
    Branch 3 delegates to mp_subscript_impl for type objects (__class_getitem__).
    """
    obj_type = maybe_get_python_type(obj)
    # Branch 1: mp_subscript
    if obj.tp_as_mapping.mp_subscript:
        return obj.mp_subscript_impl(tx, key)
    # Branch 2: sq_item (only if mp_subscript is absent)
    # CPython: abstract.c L168-181 — _PyIndex_Check(key) → PyNumber_AsSsize_t
    #          → PySequence_GetItem (wraps negative, calls sq_item)
    if obj.tp_as_sequence.sq_item is not None:
        key_type = maybe_get_python_type(key)
        if pyindex_check(key_type):
            key = pynumber_as_ssize_t(tx, key, IndexError)
            return pysequence_getitem(tx, obj, key)
        raise_type_error(
            tx,
            f"{obj_type.__name__} indices must be integers, not {key_type.__name__}",
        )
    # Branch 3: PyType_Check → __class_getitem__ (abstract.c L183-203)
    # In 3.10+ type.__getitem__ sets mp_subscript so this is normally caught
    # by Branch 1, but we check explicitly for safety.
    if issubclass(obj_type, type):
        return obj.mp_subscript_impl(tx, key)
    # CPython: abstract.c L205
    raise_type_error(tx, f"'{obj_type.__name__}' object is not subscriptable")


def pysequence_getitem(
    tx: "InstructionTranslatorBase",
    obj: VariableTracker,
    index: VariableTracker,
) -> VariableTracker:
    """CPython's PySequence_GetItem — always sq_item, never mp_subscript.

    ref: https://github.com/python/cpython/blob/v3.13.3/Objects/abstract.c#L1874-L1902

    Called by PyObject_GetItem branch 2, reversed() fallback, and the old
    iteration protocol.  Wraps negative indices via sq_length before
    dispatching to sq_item.
    """
    sq_item = obj.tp_as_sequence.sq_item
    if sq_item is not None:
        # Negative index wrapping (abstract.c L2175-2183)
        if isinstance(index, ConstantVariable):
            index_val = index.as_python_constant()
            if isinstance(index_val, int) and index_val < 0:
                if obj.tp_as_sequence.sq_length is not None:
                    length = obj.sq_length_impl(tx)
                    index = ConstantVariable.create(
                        index_val + length.as_python_constant()
                    )
        return obj.sq_item_impl(tx, index)

    if obj.tp_as_mapping.mp_subscript is not None:
        raise_type_error(tx, f"'{obj.python_type_name()}' is not a sequence")

    raise_type_error(tx, f"'{obj.python_type_name()}' object does not support indexing")


def pysequence_setitem(
    tx: "InstructionTranslatorBase",
    s: VariableTracker,
    i: VariableTracker,
    o: VariableTracker,
) -> VariableTracker:
    # ref: https://github.com/python/cpython/blob/3.13/Objects/abstract.c#L1926-L1957 (PySequence_SetItem)
    sq_ass_item = s.tp_as_sequence.sq_ass_item
    if sq_ass_item is not None:
        # Negative index wrapping (abstract.c L1944-1952)
        if isinstance(i, ConstantVariable):
            index_val = i.as_python_constant()
            if isinstance(index_val, int) and index_val < 0:
                if s.tp_as_sequence.sq_length is not None:
                    length = s.sq_length_impl(tx)
                    i = ConstantVariable.create(index_val + length.as_python_constant())
        return s.sq_ass_item_impl(tx, i, o)

    if s.tp_as_mapping.mp_ass_subscript is not None:
        raise_type_error(tx, f"'{s.python_type_name()}' is not a sequence")

    raise_type_error(
        tx, f"'{s.python_type_name()}' object does not support item assignment"
    )


def generic_setitem(
    tx: "InstructionTranslatorBase",
    o: VariableTracker,
    key: VariableTracker,
    value: VariableTracker,
) -> VariableTracker:
    # ref: https://github.com/python/cpython/blob/3.13/Objects/abstract.c#L222-L254
    mp_ass_subscript = o.tp_as_mapping.mp_ass_subscript
    if mp_ass_subscript is not None:
        return o.mp_ass_subscript_impl(tx, key, value)

    if o.tp_as_sequence.sq_ass_item is not None:
        key_type = maybe_get_python_type(key)
        if pyindex_check(key_type):
            key_value = pynumber_as_ssize_t(tx, key, err=IndexError)
            return pysequence_setitem(tx, o, key_value, value)
        raise_type_error(
            tx, f"sequence index must be integer, not '{key.python_type_name()}'"
        )
    raise_type_error(
        tx, f"'{o.python_type_name()}' object does not support item assignment"
    )


def pysequence_delitem(
    tx: "InstructionTranslatorBase",
    s: VariableTracker,
    i: VariableTracker,
) -> VariableTracker:
    # ref: https://github.com/python/cpython/blob/3.13/Objects/abstract.c#L1959-L1990

    sq_ass_item = s.tp_as_sequence.sq_ass_item
    if sq_ass_item is not None:
        if isinstance(i, ConstantVariable):
            idx = i.as_python_constant()
            if idx < 0:
                if s.tp_as_sequence.sq_length is not None:
                    length = s.sq_length_impl(tx)
                    i = pynumber_add(tx, i, length)
        return s.sq_ass_item_impl(tx, i, None)

    if s.tp_as_mapping.mp_ass_subscript is not None:
        raise_type_error(tx, f"'{s.python_type_name()}' is not a sequence")

    raise_type_error(
        tx, f"'{s.python_type_name()}' object does not support item deletion"
    )


def generic_delitem(
    tx: "InstructionTranslatorBase",
    o: VariableTracker,
    key: VariableTracker,
) -> VariableTracker:
    # ref: https://github.com/python/cpython/blob/3.13/Objects/abstract.c#L256-L288

    mp_ass_subscript = o.tp_as_mapping.mp_ass_subscript
    if mp_ass_subscript is not None:
        return o.mp_ass_subscript_impl(tx, key, None)

    key_type = maybe_get_python_type(key)
    if pyindex_check(key_type):
        key_value = key.nb_index_impl(tx)
        return pysequence_delitem(tx, o, key_value)
    elif o.tp_as_sequence.sq_ass_item is not None:
        raise_type_error(
            tx, f"sequence index must be integer, not {key.python_type_name()}"
        )

    raise_type_error(tx, f"'{o.python_type_name()}' does not support item deletion")


def pynumber_int(
    tx: "InstructionTranslatorBase", obj: VariableTracker
) -> VariableTracker:
    """Mirrors PyNumber_Long (int(x) dispatch).

    https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1520-L1632

    Resolution: nb_int → nb_index → str/bytes/bytearray parsing → TypeError.
    """
    from .constant import ConstantVariable

    # Fast path for int (sub)class instances — mirrors PyLong_Check at the
    # top of PyNumber_Long (abstract.c:1531). Avoids infinite recursion for
    # int subclasses like IntEnum whose __int__ calls int() again.
    if obj.is_python_constant() and isinstance(obj.as_python_constant(), int):
        return ConstantVariable.create(int(obj.as_python_constant()))

    if obj.tp_as_number.nb_int is not None:
        res = obj.nb_int_impl(tx)
        if res.python_type() is not int:
            raise_type_error(
                tx,
                f"__int__ returned non-int (type {res.python_type_name()})",
            )
        return res

    if obj.tp_as_number.nb_index is not None:
        return obj.nb_index_impl(tx)

    # String/bytes/bytearray parsing fallback.
    # https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1598-L1612
    if obj.is_python_constant() and isinstance(
        obj.as_python_constant(), (str, bytes, bytearray)
    ):
        try:
            return ConstantVariable.create(int(obj.as_python_constant()))
        except ValueError as e:
            raise_observed_exception(ValueError, tx, args=[str(e)])

    raise_type_error(
        tx,
        f"int() argument must be a string, a bytes-like object "
        f"or a real number, not '{obj.python_type_name()}'",
    )


def pylong_from_base(
    tx: "InstructionTranslatorBase", x: VariableTracker, obase: VariableTracker
) -> VariableTracker | None:
    """Mirrors the explicit-base path of long_new_impl (int(x, base)).

    https://github.com/python/cpython/blob/v3.13.0/Objects/longobject.c#L5879-L5922

    The base is resolved via PyNumber_AsSsize_t, which consults __index__, so
    any __index__-able object is accepted. Returns None (graph break) when the
    inputs cannot be resolved to Python constants.
    """
    # base = PyNumber_AsSsize_t(obase, NULL) -> nb_index.
    if obase.is_python_constant() and issubclass(obase.python_type(), int):
        base_vt = obase
    elif obase.tp_as_number.nb_index is not None:
        base_vt = obase.nb_index_impl(tx)
    else:
        raise_type_error(
            tx,
            f"'{obase.python_type_name()}' object cannot be interpreted as an integer",
        )
    if not (base_vt.is_python_constant() and issubclass(base_vt.python_type(), int)):
        return None
    base = base_vt.as_python_constant()
    if (base != 0 and base < 2) or base > 36:
        raise_observed_exception(
            ValueError, tx, args=["int() base must be >= 2 and <= 36, or 0"]
        )
    if not x.is_python_constant():
        return None
    xval = x.as_python_constant()
    if not isinstance(xval, (str, bytes, bytearray)):
        raise_type_error(tx, "int() can't convert non-string with explicit base")
    try:
        return ConstantVariable.create(int(xval, base))
    except ValueError as e:
        raise_observed_exception(ValueError, tx, args=list(e.args))


def pynumber_float(
    tx: "InstructionTranslatorBase", obj: VariableTracker
) -> VariableTracker:
    """Mirrors PyNumber_Float (float(x) dispatch).

    https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1635-L1692

    Resolution: nb_float → nb_index → str parsing → TypeError.
    """
    from .constant import ConstantVariable

    # Fast path: if the value is already a float constant, return it directly.
    # Mirrors PyFloat_CheckExact fast path at the top of PyNumber_Float
    # (abstract.c:1641-1643).
    if obj.is_python_constant() and isinstance(obj.as_python_constant(), float):
        return ConstantVariable.create(float(obj.as_python_constant()))

    if obj.tp_as_number.nb_float is not None:
        res = obj.nb_float_impl(tx)
        if res.python_type() is not float:
            raise_type_error(
                tx,
                f"__float__ returned non-float (type {res.python_type_name()})",
            )
        return res

    # https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1674-L1685
    if obj.tp_as_number.nb_index is not None:
        return obj.nb_index_impl(tx)

    # PyFloat_FromString fallback — handles str and bytes.
    # https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1691
    if issubclass(obj.python_type(), (str, bytes)):
        try:
            return ConstantVariable.create(float(obj.as_python_constant()))
        except ValueError as e:
            raise_observed_exception(ValueError, tx, args=[str(e)])

    raise_type_error(
        tx,
        f"float() argument must be a string or a real number, "
        f"not '{obj.python_type_name()}'",
    )


def getindex(
    tx: "InstructionTranslatorBase",
    obj: VariableTracker,
    arg: VariableTracker,
) -> VariableTracker:
    """Mirrors typeobject.c::getindex: calls PyNumber_AsSsize_t then tp_as_sequence.sq_length"""
    obj_type = maybe_get_python_type(obj)

    i = pynumber_as_ssize_t(tx, arg, err=OverflowError)
    if i.as_python_constant() < 0:
        if type_implements_sq_length(obj_type):
            length = obj.sq_length_impl(tx)
            i = pynumber_add(tx, i, length)
    return i


def pylong_as_ssize_t(tx: "InstructionTranslatorBase", obj: VariableTracker) -> int:
    """Mirrors PyLong_AsSsize_t: requires an int (or subclass).
    values outside the Py_ssize_t range raise OverflowError.

    https://github.com/python/cpython/blob/60403a5409ff2c3f3b07dd2ca91a7a3e096839c7/Objects/longobject.c#L576
    """
    # Starting on Python 3.16, this will explicitly require an integer instance
    # https://docs.python.org/3/deprecations/index.html#pending-removal-in-python-3-16
    if not issubclass(obj.python_type(), int):
        raise_type_error(tx, "an integer is required")
    val = obj.as_python_constant()
    if not -sys.maxsize - 1 <= val <= sys.maxsize:
        raise_observed_exception(
            OverflowError,
            tx,
            args=["Python int too large to convert to C ssize_t"],
        )
    return val


def pynumber_as_ssize_t(
    tx: "InstructionTranslatorBase",
    item: VariableTracker,
    err: type[Exception] | None = IndexError,
) -> VariableTracker:
    """Mirrors PyNumber_AsSsize_t: _PyNumber_Index(item) then PyLong_AsSsize_t.

    On overflow (value outside the Py_ssize_t range) CPython remaps the
    OverflowError to `err`, or clips to the Py_ssize_t bounds when err is None.

    https://github.com/python/cpython/blob/60403a5409ff2c3f3b07dd2ca91a7a3e096839c7/Objects/abstract.c#L1469
    """
    from .tensor import SymNodeVariable

    value = pynumber_index(tx, item)

    # PyLong_AsSsize_t: a symbolic int must be specialized to a concrete
    # ssize_t (with guard) to be usable as a C index.
    if isinstance(value, SymNodeVariable):
        val = value.evaluate_expr(tx.output)
    else:
        val = value.as_python_constant()

    if not isinstance(val, int):
        raise AssertionError("pynumber_index did not return an int-like value")

    if -sys.maxsize - 1 <= val <= sys.maxsize:
        return ConstantVariable.create(int(val))
    if err is None:
        r = sys.maxsize if val > 0 else -sys.maxsize - 1
        return ConstantVariable.create(r)
    raise_observed_exception(
        err,
        tx,
        args=[f"cannot fit '{item.python_type_name()}' into an index-sized integer"],
    )


def pynumber_index(
    tx: "InstructionTranslatorBase", obj: VariableTracker
) -> "VariableTracker":
    """Mirrors PyNumber_Index (index(x) dispatch)."""

    if obj.tp_as_number.nb_index is None:
        raise_type_error(
            tx,
            f"'{obj.python_type_name()}' object cannot be interpreted as an integer",
        )

    result = obj.nb_index_impl(tx)

    if not issubclass(result.python_type(), int):
        raise_type_error(
            tx,
            f"__index__ returned non-int (type {result.python_type_name()})",
        )

    return result


def pynumber_tobase(
    tx: "InstructionTranslatorBase", obj: VariableTracker, base: int
) -> VariableTracker | None:
    """Mirrors PyNumber_ToBase (bin/oct/hex dispatch).

    https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1653-L1666

    Resolves __index__ (raising TypeError if absent), then formats the
    resulting int in the requested base. Returns None (graph break) when the
    index result is not a Python constant.
    """
    index = pynumber_index(tx, obj)
    format_fn = {2: bin, 8: oct, 16: hex}[base]
    return ConstantVariable.create(format_fn(index.as_python_constant()))


def pyiter_next(
    tx: "InstructionTranslatorBase", obj: VariableTracker
) -> "VariableTracker":
    """
    Implements PyIter_Next / tp_iternext semantics for VariableTracker objects.

    Calls obj.tp_iternext_impl(tx) if the object is an iterator, otherwise raises
    TypeError. StopIteration propagation is left to the caller (mirrors
    CPython's iternext contract where NULL return signals exhaustion).
    """
    # ref: https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L2865

    tp_iternext = obj.tp_iternext
    if tp_iternext is None:
        raise_type_error(tx, f"expected an iterator, got '{obj.python_type_name()}'")

    return obj.tp_iternext_impl(tx)


def pynumber_negative(
    tx: "InstructionTranslatorBase", obj: VariableTracker
) -> VariableTracker:
    """Mirrors PyNumber_Negative.

    https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1375-L1392

    Algorithm:
    1. If type has nb_negative slot, call obj.nb_negative_impl(tx)
    2. Otherwise, raise TypeError
    """

    nb_negative = obj.tp_as_number.nb_negative
    if nb_negative is not None:
        return obj.nb_negative_impl(tx)

    raise_type_error(
        tx,
        f"bad operand type for unary -: '{obj.python_type_name()}'",
    )


def pynumber_positive(
    tx: "InstructionTranslatorBase", obj: VariableTracker
) -> VariableTracker:
    """Mirrors PyNumber_Positive.

    https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1375-L1393

    Algorithm:
    1. If type has nb_positive slot, call obj.nb_positive_impl(tx)
    2. Otherwise, raise TypeError
    """

    nb_positive = obj.tp_as_number.nb_positive
    if nb_positive is not None:
        return obj.nb_positive_impl(tx)

    raise_type_error(
        tx,
        f"bad operand type for unary +: '{obj.python_type_name()}'",
    )


def pynumber_absolute(
    tx: "InstructionTranslatorBase", obj: VariableTracker
) -> VariableTracker:
    """Mirrors PyNumber_Absolute.

    https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1375-L1395

    Algorithm:
    1. If type has nb_absolute slot, call obj.nb_absolute_impl(tx)
    2. Otherwise, raise TypeError
    """

    nb_absolute = obj.tp_as_number.nb_absolute
    if nb_absolute is not None:
        return obj.nb_absolute_impl(tx)

    raise_type_error(
        tx,
        f"bad operand type for abs(): '{obj.python_type_name()}'",
    )


def vt_is_iterable(obj: VariableTracker) -> bool:
    """Check if the object supports iteration (i.e. has tp_iter or sequence protocol)."""
    T = maybe_get_python_type(obj)
    return obj.tp_iter is not None or pysequence_check(T)


def pynumber_invert(
    tx: "InstructionTranslatorBase", obj: VariableTracker
) -> VariableTracker:
    """Mirrors PyNumber_Invert.

    https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1375-L1394

    Algorithm:
    1. If type has nb_invert slot, call obj.nb_invert_impl(tx)
    2. Otherwise, raise TypeError
    """

    nb_invert = obj.tp_as_number.nb_invert
    if nb_invert is not None:
        return obj.nb_invert_impl(tx)

    raise_type_error(
        tx,
        f"bad operand type for unary ~: '{obj.python_type_name()}'",
    )


def generic_getiter(
    tx: "InstructionTranslatorBase", obj: VariableTracker
) -> "VariableTracker":
    """
    Implements PyObject_GetIter semantics for VariableTracker objects.
    Routes to obj.tp_iter_impl(tx), the tp_iter slot on the object's type.
    """

    # ref: https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L2847-L2870
    # The algorithm for PyObject_GetIter works as follows: Steps:
    # 1. If the object has tp_iter slot, call it and return the result. The
    #    return object must be an iterator (it must have a tp_iternext slot)
    # 2. If the object implements the sequence protocol - implements __getitem__
    #    then create a sequence iterator for the object and return it
    # 3. Otherwise, raise a TypeError

    T = maybe_get_python_type(obj)
    tp_iter = obj.tp_iter
    if tp_iter is not None:
        res = obj.tp_iter_impl(tx)
        res_T = maybe_get_python_type(res)
        if not pyiter_check(res_T):
            if sys.version_info >= (3, 15):
                err_str = f"{obj.python_qualified_name()}.__iter__() must return an iterator, not {res.python_qualified_name()}"
            else:
                err_str = (
                    f"iter() returned non-iterator of type '{res.python_type_name()}'"
                )
            raise_type_error(tx, err_str)
        return res
    elif pysequence_check(T):
        from .functions import UserFunctionVariable

        return UserFunctionVariable(polyfills.builtins.sequence_iterator).call_function(
            tx, [obj], {}
        )
    else:
        raise_type_error(tx, f"'{obj.python_type_name()}' object is not iterable")


# ---------------------------------------------------------------------------
# Binary-op dispatch (CPython's abstract.c: binary_op1 / binary_op)
# https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L927 (binary_op1)
# ---------------------------------------------------------------------------

NB_SLOT_MAPPING = {
    "nb_lshift": PyNumberSlots.NB_LSHIFT,
    "nb_inplace_lshift": PyNumberSlots.NB_INPLACE_LSHIFT,
    "nb_inplace_rshift": PyNumberSlots.NB_INPLACE_RSHIFT,
    "nb_rshift": PyNumberSlots.NB_RSHIFT,
    "nb_or": PyNumberSlots.NB_OR,
    "nb_inplace_or": PyNumberSlots.NB_INPLACE_OR,
    "nb_subtract": PyNumberSlots.NB_SUBTRACT,
    "nb_inplace_subtract": PyNumberSlots.NB_INPLACE_SUBTRACT,
    "nb_add": PyNumberSlots.NB_ADD,
    "nb_inplace_add": PyNumberSlots.NB_INPLACE_ADD,
    "nb_multiply": PyNumberSlots.NB_MULTIPLY,
    "nb_inplace_multiply": PyNumberSlots.NB_INPLACE_MULTIPLY,
    "nb_matrix_multiply": PyNumberSlots.NB_MATRIX_MULTIPLY,
    "nb_inplace_matrix_multiply": PyNumberSlots.NB_INPLACE_MATRIX_MULTIPLY,
    "nb_and": PyNumberSlots.NB_AND,
    "nb_inplace_and": PyNumberSlots.NB_INPLACE_AND,
    "nb_xor": PyNumberSlots.NB_XOR,
    "nb_inplace_xor": PyNumberSlots.NB_INPLACE_XOR,
    "nb_floor_divide": PyNumberSlots.NB_FLOOR_DIVIDE,
    "nb_inplace_floor_divide": PyNumberSlots.NB_INPLACE_FLOOR_DIVIDE,
    "nb_true_divide": PyNumberSlots.NB_TRUE_DIVIDE,
    "nb_inplace_true_divide": PyNumberSlots.NB_INPLACE_TRUE_DIVIDE,
    "nb_remainder": PyNumberSlots.NB_REMAINDER,
    "nb_inplace_remainder": PyNumberSlots.NB_INPLACE_REMAINDER,
    "nb_divmod": PyNumberSlots.NB_DIVMOD,
    "nb_power": PyNumberSlots.NB_POWER,
    "nb_inplace_power": PyNumberSlots.NB_INPLACE_POWER,
}


def is_nb_not_implemented(result: VariableTracker) -> bool:
    return result.is_constant_match(NotImplemented)


def is_python_subtype(w: VariableTracker, v: VariableTracker) -> bool:
    """Check if w's underlying Python type is a proper subtype of v's."""
    try:
        return issubclass(w.python_type(), v.python_type())
    except NotImplementedError:
        return False


#   Calling scheme used for binary operations:
#
#   Order operations are tried until either a valid result or error:
#     w.op(v,w)[*], v.op(v,w), w.op(v,w)
#
#   [*] only when Py_TYPE(v) != Py_TYPE(w) && Py_TYPE(w) is a subclass of
#       Py_TYPE(v)


def binary_op1(
    tx: "InstructionTranslatorBase",
    v: VariableTracker,
    w: VariableTracker,
    op_slot: str,
) -> VariableTracker:
    """CPython's binary_op1: try v's slot, then w's slot with subclass priority.

    Each VT that participates provides a ``<op_slot>_impl(self, tx, other,
    reverse)`` method. ``reverse=False`` means "self is left operand" (forward,
    e.g. ``__or__``), ``reverse=True`` means "self is right operand" (reverse,
    e.g. ``__ror__``). For built-in types the flag is ignored because their
    slots check both operands symmetrically.

    CPython splits the check into two steps: ``Py_TYPE(v)->tp_as_number !=
    NULL`` (does the type have a number-protocol struct), then read the
    slot pointer (which may itself be NULL).  We collapse both into a
    single :func:`type_implements_nb_slot` query — its bit is set only
    when the specific slot is non-NULL, which already implies
    ``tp_as_number`` is non-NULL.  Treating a missing slot as "no impl"
    is what keeps the base ``VariableTracker.nb_*_impl`` graph-break
    out of the path for types that genuinely lack the slot in C.

    https://github.com/python/cpython/blob/3.13/Objects/abstract.c#L926-L977
    """
    impl_attr = f"{op_slot}_impl"
    nb_slot_bit = NB_SLOT_MAPPING[op_slot]

    v_type = maybe_get_python_type(v)
    w_type = maybe_get_python_type(w)

    v_slot = (
        getattr(type(v), impl_attr, None)
        if type_implements_nb_slot(v_type, nb_slot_bit)
        else None
    )
    w_slot = (
        getattr(type(w), impl_attr, None)
        if type_implements_nb_slot(w_type, nb_slot_bit)
        else None
    )

    # CPython skips slotw if Py_TYPE(w) == Py_TYPE(v) (one C type, one slot
    # function).  In Dynamo two VT subclasses can share a Python type — e.g.
    # ConstantVariable(3) and SymNodeVariable both report ``int`` — yet have
    # different ``nb_*_impl`` methods.  Comparing the slots themselves
    # captures both "literally the same function" (CPython's check) and
    # "different VT subclasses sharing a python_type", so we drop the type
    # equality check.
    if v_slot is w_slot:
        w_slot = None

    if v_slot is not None:
        # Subclass priority: if w's Python type is a proper subtype of v's
        # Python type and overrides the slot, try w first (CPython abstract.c:952-960).
        if w_slot is not None and is_python_subtype(w, v):
            # CPython ALWAYS calls the slot with (v, w), even for reverse slots.
            # Since w_slot is a method call, we use reverse=True to indicate w
            # is the right operand, matching CPython's semantics.
            result = w_slot(w, tx, v, True)
            if not is_nb_not_implemented(result):
                return result
            w_slot = None
        result = v_slot(v, tx, w, False)
        if not is_nb_not_implemented(result):
            return result
    if w_slot is not None:
        result = w_slot(w, tx, v, True)
        if not is_nb_not_implemented(result):
            return result
    return ConstantVariable.create(NotImplemented)


def binary_op(
    tx: "InstructionTranslatorBase",
    v: VariableTracker,
    w: VariableTracker,
    op_slot: str,
    op_symbol: str,
) -> VariableTracker:
    """CPython's binary_op: binary_op1 + TypeError fallback.
    https://github.com/python/cpython/blob/3.13/Objects/abstract.c#L997-L1020
    """

    result = binary_op1(tx, v, w, op_slot)
    if is_nb_not_implemented(result):
        binop_type_error(tx, v, w, op_symbol)
    return result


def ternary_op(
    tx: "InstructionTranslatorBase",
    v: VariableTracker,
    w: VariableTracker,
    z: VariableTracker | None,
    op_slot: str,
    op_name: str,
) -> VariableTracker:
    impl_attr = f"{op_slot}_impl"
    nb_slot_bit = NB_SLOT_MAPPING[op_slot]

    v_type = maybe_get_python_type(v)
    w_type = maybe_get_python_type(w)

    v_slot = (
        getattr(type(v), impl_attr, None)
        if type_implements_nb_slot(v_type, nb_slot_bit)
        else None
    )

    w_slot = (
        getattr(type(w), impl_attr, None)
        if type_implements_nb_slot(w_type, nb_slot_bit)
        else None
    )

    if v_slot is w_slot:
        w_slot = None

    if v_slot:
        if w_slot and is_python_subtype(w, v):
            result = w_slot(w, tx, v, z, True)
            if not is_nb_not_implemented(result):
                return result
            w_slot = None
        result = v_slot(v, tx, w, z, False)
        if not is_nb_not_implemented(result):
            return result
    if w_slot:
        result = w_slot(w, tx, v, z, True)
        if not is_nb_not_implemented(result):
            return result

    if z:
        z_type = maybe_get_python_type(z)
        if type_implements_nb_slot(z_type, nb_slot_bit):
            z_impl_attr = f"{op_slot}_z_impl"
            z_slot = getattr(type(z), z_impl_attr, None)
            if z_slot in (v_slot, w_slot):
                z_slot = None
            if z_slot:
                result = z_slot(z, tx, v, w)
                if not is_nb_not_implemented(result):
                    return result

    if z is None:
        binop_type_error(tx, v, w, op_name)
    else:
        raise_type_error(
            tx,
            f"unsupported operand type(s) for {op_name}: "
            f"'{v.python_type_name()}', '{w.python_type_name()}', '{z.python_type_name()}'",
        )


def ternary_iop(
    tx: "InstructionTranslatorBase",
    v: VariableTracker,
    w: VariableTracker,
    z: VariableTracker | None,
    iop_slot: str,
    op_slot: str,
    op_name: str,
) -> VariableTracker:
    v_type = maybe_get_python_type(v)
    if type_implements_nb_slot(v_type, NB_SLOT_MAPPING[iop_slot]):
        impl_attr = f"{iop_slot}_impl"
        slot = getattr(type(v), impl_attr)
        result = slot(v, tx, w, z)
        if not is_nb_not_implemented(result):
            return result

    return ternary_op(tx, v, w, z, op_slot, op_name)


#  Binary in-place operators
#
#    The in-place operators are defined to fall back to the 'normal', non
#    in-place operations, if the in-place methods are not in place.
#
#    - If the left hand object has the appropriate struct members, and they are
#      filled, call the appropriate function and return the result.  No coercion
#      is done on the arguments; the left-hand object is the one the operation
#      is performed on, and it's up to the function to deal with the right-hand
#      object.
#
#    - Otherwise, in-place modification is not supported. Handle it exactly as a
#      non in-place operation of the same kind.


def binary_iop1(
    tx: "InstructionTranslatorBase",
    v: VariableTracker,
    w: VariableTracker,
    iop_slot: str,
    op_slot: str,
) -> VariableTracker:
    v_type = maybe_get_python_type(v)

    if type_implements_nb_slot(v_type, NB_SLOT_MAPPING[iop_slot]):
        impl_attr = f"{iop_slot}_impl"
        slot = getattr(type(v), impl_attr)
        result = slot(v, tx, w)
        if not is_nb_not_implemented(result):
            return result

    return binary_op1(tx, v, w, op_slot)


def binary_iop(
    tx: "InstructionTranslatorBase",
    v: VariableTracker,
    w: VariableTracker,
    iop_slot: str,
    op_slot: str,
    op_symbol: str,
) -> VariableTracker:
    """CPython's binary_iop: try inplace slot, fallback to binary_op1.

    Combines binary_iop1 + TypeError fallback from binary_iop.
    https://github.com/python/cpython/blob/3.13/Objects/abstract.c#L1229-L1270 (binary_iop1, binary_iop)
    """
    result = binary_iop1(tx, v, w, iop_slot, op_slot)
    if is_nb_not_implemented(result):
        binop_type_error(tx, v, w, op_symbol)
    return result


# add / inplace add needs special handling
def pynumber_add(
    tx: "InstructionTranslatorBase",
    v: VariableTracker,
    w: VariableTracker,
) -> VariableTracker:
    """Implements addition via nb_add / nb_inplace_add with binary_op dispatch."""
    # ref: https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1138-L1155
    result = binary_op1(tx, v, w, "nb_add")
    if not is_nb_not_implemented(result):
        return result

    sq_concat = v.tp_as_sequence.sq_concat
    if sq_concat is not None:
        return v.sq_concat_impl(tx, w)
    binop_type_error(tx, v, w, "+")


def pynumber_inplace_add(
    tx: "InstructionTranslatorBase",
    v: VariableTracker,
    w: VariableTracker,
) -> VariableTracker:
    """Implements in-place addition via nb_inplace_add with binary_iop dispatch."""
    # ref: https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1307-L1328
    result = binary_iop1(tx, v, w, "nb_inplace_add", "nb_add")
    if is_nb_not_implemented(result):
        sq_inplace_concat = v.tp_as_sequence.sq_inplace_concat
        sq_concat = v.tp_as_sequence.sq_concat
        if sq_inplace_concat is not None:
            return v.sq_inplace_concat_impl(tx, w)
        elif sq_concat is not None:
            return v.sq_concat_impl(tx, w)
        else:
            binop_type_error(tx, v, w, "+=")
    return result


# ---------------------------------------------------------------------------
# Multiplication: PyNumber_Multiply / PyNumber_InPlaceMultiply
#
# Multiplication is special because numeric types implement nb_multiply but
# sequence types (list, tuple, str, bytes, bytearray) implement only sq_repeat.
# CPython's PyNumber_Multiply tries nb_multiply first (via binary_op1) and on
# NotImplemented falls back to sq_repeat on either operand.
#
# https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1156-L1193
# ---------------------------------------------------------------------------


def pysequence_repeat(
    tx: "InstructionTranslatorBase",
    seq: VariableTracker,
    n: VariableTracker,
) -> VariableTracker:
    """Mirrors CPython's sequence_repeat helper.

    Validates that ``n`` is index-like, converts it to an int, and dispatches
    to ``seq.sq_repeat_impl(tx, count)``.

    https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1156-L1174
    """
    n_type = maybe_get_python_type(n)
    if not pyindex_check(n_type):
        raise_type_error(
            tx,
            f"can't multiply sequence by non-int of type '{n.python_type_name()}'",
        )
    count = n.nb_index_impl(tx)
    validate_sequence_repeat_count(tx, count)
    return seq.sq_repeat_impl(tx, count)


def pysequence_inplace_repeat(
    tx: "InstructionTranslatorBase",
    seq: VariableTracker,
    n: VariableTracker,
) -> VariableTracker:
    """pysequence_repeat using sq_inplace_repeat.

    The validation step is identical to ``pysequence_repeat``; only the
    target slot differs.
    """
    n_type = maybe_get_python_type(n)
    if not pyindex_check(n_type):
        raise_type_error(
            tx,
            f"can't multiply sequence by non-int of type '{n.python_type_name()}'",
        )
    count = n.nb_index_impl(tx)
    validate_sequence_repeat_count(tx, count)
    return seq.sq_inplace_repeat_impl(tx, count)


def validate_sequence_repeat_count(
    tx: "InstructionTranslatorBase",
    count: VariableTracker,
) -> None:
    n = count.as_python_constant()
    if n < -sys.maxsize - 1 or n > sys.maxsize:
        raise_observed_exception(
            OverflowError,
            tx,
            args=["cannot fit 'int' into an index-sized integer"],
        )


def pynumber_multiply(
    tx: "InstructionTranslatorBase",
    v: VariableTracker,
    w: VariableTracker,
) -> VariableTracker:
    """Mirrors CPython's PyNumber_Multiply.

    Try nb_multiply via binary_op1; on NotImplemented fall back to sq_repeat
    on either operand.  TypeError if no path works.

    https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1176-L1193
    """
    result = binary_op1(tx, v, w, "nb_multiply")
    if not is_nb_not_implemented(result):
        return result

    if v.tp_as_sequence.sq_repeat is not None:
        return pysequence_repeat(tx, v, w)
    if w.tp_as_sequence.sq_repeat is not None:
        return pysequence_repeat(tx, w, v)

    raise_type_error(
        tx,
        f"unsupported operand type(s) for *: "
        f"'{v.python_type_name()}' and '{w.python_type_name()}'",
    )


def pynumber_inplace_multiply(
    tx: "InstructionTranslatorBase",
    v: VariableTracker,
    w: VariableTracker,
) -> VariableTracker:
    """Mirrors CPython's PyNumber_InPlaceMultiply.

    Try nb_inplace_multiply / nb_multiply via binary_iop1; on NotImplemented
    fall back to sq_inplace_repeat (preferred), then sq_repeat.

    https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L1330-L1357
    """
    result = binary_iop1(tx, v, w, "nb_inplace_multiply", "nb_multiply")
    if not is_nb_not_implemented(result):
        return result

    if v.tp_as_sequence.sq_inplace_repeat is not None:
        return pysequence_inplace_repeat(tx, v, w)
    if v.tp_as_sequence.sq_repeat is not None:
        return pysequence_repeat(tx, v, w)
    # Cannot mutate w in-place — abstract.c L1348-1352 explicitly avoids
    # sq_inplace_repeat on the right-hand operand.
    if w.tp_as_sequence.sq_repeat is not None:
        return pysequence_repeat(tx, w, v)

    raise_type_error(
        tx,
        f"unsupported operand type(s) for *=: "
        f"'{v.python_type_name()}' and '{w.python_type_name()}'",
    )


def pynumber_matrix_multiply(
    tx: "InstructionTranslatorBase",
    v: VariableTracker,
    w: VariableTracker,
) -> VariableTracker:
    """Mirrors CPython's PyNumber_MatrixMultiply."""
    return binary_op(tx, v, w, "nb_matrix_multiply", "@")


def pynumber_inplace_matrix_multiply(
    tx: "InstructionTranslatorBase",
    v: VariableTracker,
    w: VariableTracker,
) -> VariableTracker:
    """Mirrors CPython's PyNumber_InPlaceMatrixMultiply."""
    return binary_iop(
        tx,
        v,
        w,
        "nb_inplace_matrix_multiply",
        "nb_matrix_multiply",
        "@=",
    )


# ---------------------------------------------------------------------------
# Type-object slot wrappers for ``__mul__`` / ``__rmul__`` / ``__imul__``
#
# These mirror the *type object*'s installation of ``__mul__`` etc. as a
# method, not the operator dispatch.  In CPython the user-visible
# ``int.__mul__`` and ``list.__mul__`` are different functions, each
# generated at type-construction time from ``Objects/typeobject.c``'s
# ``slotdefs[]`` table:
#
#   slotdefs[]:
#     BINSLOT(__mul__, nb_multiply, slot_nb_multiply, "*")    [L10323]
#     SQSLOT (__mul__, sq_repeat,   NULL, wrap_indexargfunc)  [L10419]
#     RBINSLOT(__rmul__, nb_multiply, slot_nb_multiply, "*")  [L10325]
#     SQSLOT (__rmul__, sq_repeat,   NULL, wrap_indexargfunc) [L10421]
#     IBSLOT (__imul__, nb_inplace_multiply, ...)             [L10364]
#     SQSLOT (__imul__, sq_inplace_repeat, NULL, ...)         [L10434]
#
# https://github.com/python/cpython/blob/v3.13.13/Objects/typeobject.c#L10244 (slotdefs[])
# https://github.com/python/cpython/blob/v3.13.13/Objects/typeobject.c#L10412-L10416 (rationale comment)
#
# ``add_operators`` walks ``slotdefs[]`` and inserts a method into the
# type's ``__dict__`` for whichever slot the type fills.  As the comment
# at L10412 notes, types fill at most one of ``nb_multiply`` /
# ``sq_repeat`` per op; nb_* takes priority because its slotdef appears
# first.  ``slot_wrapper_mul``/``slot_wrapper_imul`` reproduce that
# selection so that ``call_method`` routing for direct dunder calls
# (``[1, 2].__mul__(3)``) reaches the correct slot.
#
# Distinct from ``pynumber_multiply`` / ``pynumber_inplace_multiply``, which
# mirror the operator-level algorithm in ``Objects/abstract.c``
# (``PyNumber_Multiply``) — cross-operand subclass priority and the
# ``sq_repeat`` fallback when ``nb_multiply`` returns ``NotImplemented``.
# ---------------------------------------------------------------------------


def slot_wrapper_mul(
    tx: "InstructionTranslatorBase",
    self: VariableTracker,
    other: VariableTracker,
    reverse: bool = False,
) -> VariableTracker:
    """``self.__mul__(other)`` / ``self.__rmul__(other)`` slot wrapper."""
    nb_multiply = self.tp_as_number.nb_multiply
    if nb_multiply is not None:
        return self.nb_multiply_impl(tx, other, reverse=reverse)
    if self.tp_as_sequence.sq_repeat is not None:
        # SQSLOT for __mul__ and __rmul__ both use ``wrap_indexargfunc`` —
        # the wrapper ignores the reverse flag because sq_repeat takes
        # ``(seq, count)`` regardless of which side ``self`` is on.
        return pysequence_repeat(tx, self, other)
    raise_type_error(
        tx,
        f"unsupported operand type(s) for *: "
        f"'{self.python_type_name()}' and '{other.python_type_name()}'",
    )


def slot_wrapper_imul(
    tx: "InstructionTranslatorBase",
    self: VariableTracker,
    other: VariableTracker,
) -> VariableTracker:
    """``self.__imul__(other)`` slot wrapper.

    When neither ``nb_inplace_multiply`` nor ``sq_inplace_repeat`` is
    installed, the slotdef machinery doesn't generate ``__imul__`` at all
    — but the operator-level fallback in ``slot_nb_inplace_multiply``
    (typeobject.c) does try the non-inplace slot.  We mirror that here so
    method lookups don't graph-break on (e.g.) tuple, even though tuple
    has no ``__imul__`` attribute in standard CPython.
    """
    nb_inplace_multiply = self.tp_as_number.nb_inplace_multiply
    if nb_inplace_multiply is not None:
        return self.nb_inplace_multiply_impl(tx, other)
    if self.tp_as_sequence.sq_inplace_repeat is not None:
        return pysequence_inplace_repeat(tx, self, other)
    return slot_wrapper_mul(tx, self, other)


# ---------------------------------------------------------------------------
# Type-object slot wrappers for ``__add__`` / ``__radd__`` / ``__iadd__``

#   BINSLOT (__add__,  nb_add,      slot_nb_add, "+")           [typeobject.c L10915]
#   RBINSLOT(__radd__, nb_add,      slot_nb_add, "+")           [L10917]
#   SQSLOT  (__add__,  sq_concat,   NULL, wrap_binaryfunc)      [L11017]
#   IBSLOT  (__iadd__, nb_inplace_add, ...)                     [L10960]
#   SQSLOT  (__iadd__, sq_inplace_concat, NULL, ...)            [L11031]
#
# Distinct from ``pynumber_add`` / ``pynumber_inplace_add``, which mirror the
# operator-level ``PyNumber_Add`` (cross-operand priority, sq_concat fallback).
# ---------------------------------------------------------------------------


def slot_wrapper_add(
    tx: "InstructionTranslatorBase",
    self: VariableTracker,
    other: VariableTracker,
    reverse: bool = False,
) -> VariableTracker:
    """``self.__add__(other)`` / ``self.__radd__(other)`` slot wrapper."""
    nb_add = self.tp_as_number.nb_add
    if nb_add is not None:
        return self.nb_add_impl(tx, other, reverse=reverse)
    # No SQSLOT(__radd__): sq_concat backs only the forward __add__.
    sq_concat = self.tp_as_sequence.sq_concat
    if not reverse and sq_concat is not None:
        return self.sq_concat_impl(tx, other)
    raise_type_error(
        tx,
        f"unsupported operand type(s) for +: "
        f"'{self.python_type_name()}' and '{other.python_type_name()}'",
    )


def slot_wrapper_iadd(
    tx: "InstructionTranslatorBase",
    self: VariableTracker,
    other: VariableTracker,
) -> VariableTracker:
    """``self.__iadd__(other)`` slot wrapper.

    Mirrors ``slot_wrapper_imul``: when neither ``nb_inplace_add`` nor
    ``sq_inplace_concat`` is installed, fall back to the non-inplace slot.
    """
    nb_inplace_add = self.tp_as_number.nb_inplace_add
    if nb_inplace_add is not None:
        return self.nb_inplace_add_impl(tx, other)
    sq_inplace_concat = self.tp_as_sequence.sq_inplace_concat
    if sq_inplace_concat is not None:
        return self.sq_inplace_concat_impl(tx, other)
    return slot_wrapper_add(tx, self, other)


# ---------------------------------------------------------------------------
# tp_richcompare -- comparison dispatch
#
# CPython comparison architecture (Objects/object.c, Objects/typeobject.c):
#
#   a == b  (COMPARE_OP bytecode)
#     -> PyObject_RichCompare(a, b, Py_EQ)
#       -> do_richcompare(a, b, Py_EQ)            # the 4-step algorithm
#         -> type(a)->tp_richcompare(a, b, Py_EQ)  # per-type slot
#
#   a.__eq__(b)  (attribute access)
#     -> type(a)->tp_getattro(a, "__eq__")          # descriptor protocol
#     -> returns wrapper bound to tp_richcompare
#     -> calling wrapper invokes tp_richcompare(a, b, Py_EQ) directly
#
# do_richcompare algorithm (Objects/object.c#L901-L955):
#   1. Subclass priority: if type(b) is a proper subclass of type(a),
#      try type(b)->tp_richcompare(b, a, swapped_op) first
#   2. Forward: type(a)->tp_richcompare(a, b, op)
#   3. Reflected: type(b)->tp_richcompare(b, a, swapped_op)
#   4. Fallback: identity for eq/ne, TypeError for ordering
#
# Dynamo implementation:
#
#   tp_richcompare_impl(self, tx, other, op) -- per-VT slot, analogous to
#     tp_richcompare.  Returns ConstantVariable(NotImplemented) when the
#     type does not handle the comparison.
#
#   generic_richcompare(tx, lhs, rhs, op) -- analogous to do_richcompare.
#     Implements the 4-step algorithm directly using tp_richcompare_impl
#     slots.  If a user comparison method graph-breaks, the Unsupported
#     exception propagates to COMPARE_OP (which has
#     @break_graph_if_unsupported) and runs the comparison eagerly.
#     UDOV.tp_richcompare_impl disables nested graph breaks on the resolved
#     funcvar so the InliningInstructionTranslator does not try to split
#     the inlined user method mid-function.
#
# Two entry points converge on tp_richcompare_impl:
#
#   COMPARE_OP (a == b):
#     -> BuiltinVariable dispatch -> generic_richcompare
#       -> tp_richcompare_impl (4-step: subclass priority, forward, reflected, fallback)
#
#   call_method("__eq__") (a.__eq__(b) in user code):
#     -> base.py call_method -> tp_richcompare_impl directly
#
# The call_method path calls tp_richcompare_impl directly (not
# generic_richcompare) to match CPython semantics: a.__eq__(b) invokes
# the type's tp_richcompare slot without do_richcompare's reflected-
# operand protocol, and may return NotImplemented.
# ---------------------------------------------------------------------------


is_richcompare_not_implemented = is_nb_not_implemented


def object_richcompare(
    self: VariableTracker,
    tx: "InstructionTranslatorBase",
    other: VariableTracker,
    op: str,
) -> VariableTracker:
    """object's tp_richcompare.

    https://github.com/python/cpython/blob/e76aa128fe/Objects/typeobject.c#L6263-L6305
    - __eq__: identity check, else NotImplemented
    - __ne__: delegates to tp_richcompare(self, other, Py_EQ) and inverts
    - ordering
    """
    if op == "__eq__":
        identity = vt_identity_compare(self, other)
        if identity is not None and identity.as_python_constant():
            return ConstantVariable.create(True)
        return ConstantVariable.create(NotImplemented)
    elif op == "__ne__":
        # https://github.com/python/cpython/blob/e76aa128fe/Objects/typeobject.c#L6279-L6298
        # Safe to call as_python_constant(): only identity-based types use
        # object_richcompare, so eq_result is always True or NotImplemented.
        eq_result = self.tp_richcompare_impl(tx, other, "__eq__")
        if is_richcompare_not_implemented(eq_result):
            return eq_result
        return ConstantVariable.create(not eq_result.as_python_constant())
    else:
        return ConstantVariable.create(NotImplemented)


def python_constant_richcompare_impl(
    self: VariableTracker,
    tx: "InstructionTranslatorBase",
    other: VariableTracker,
    op: str,
) -> VariableTracker:
    """Constant-fold comparison for types with as_python_constant()."""
    if not self.is_python_constant() or not other.is_python_constant():
        return ConstantVariable.create(NotImplemented)
    self_val = self.as_python_constant()
    other_val = other.as_python_constant()
    try:
        result = getattr(type(self_val), op)(self_val, other_val)
    except TypeError as e:
        raise_observed_exception(TypeError, tx, args=list(e.args))
    return ConstantVariable.create(result)


# _Py_SwappedOp: https://github.com/python/cpython/blob/e76aa128fe/Objects/object.c#L987
_REFLECTED_OP: dict[str, str] = {
    "__lt__": "__gt__",
    "__gt__": "__lt__",
    "__le__": "__ge__",
    "__ge__": "__le__",
    "__eq__": "__eq__",
    "__ne__": "__ne__",
}

_OP_STR: dict[str, str] = {
    "__lt__": "<",
    "__le__": "<=",
    "__eq__": "==",
    "__ne__": "!=",
    "__gt__": ">",
    "__ge__": ">=",
}


def generic_richcompare(
    tx: "InstructionTranslatorBase",
    v: VariableTracker,
    w: VariableTracker,
    op: str,
) -> VariableTracker:
    """Dynamo's do_richcompare.

    https://github.com/python/cpython/blob/e76aa128fe/Objects/object.c#L994-L1039

    Implements the 4-step algorithm directly using tp_richcompare_impl slots.
    Graph breaks inside user comparison methods propagate to COMPARE_OP
    (which runs eagerly) because UDOV.tp_richcompare_impl disables nested
    graph breaks on the resolved funcvar.
    """
    reflected = _REFLECTED_OP[op]

    try:
        v_type = v.python_type()
    except NotImplementedError:
        v_type = None
    try:
        w_type = w.python_type()
    except NotImplementedError:
        w_type = None

    checked_reverse = False

    # Step 1: subclass priority
    if (
        v_type is not None
        and w_type is not None
        and v_type is not w_type
        and issubclass(w_type, v_type)
    ):
        checked_reverse = True
        result = w.tp_richcompare_impl(tx, v, reflected)
        if not is_richcompare_not_implemented(result):
            return result

    # Step 2: forward
    result = v.tp_richcompare_impl(tx, w, op)
    if not is_richcompare_not_implemented(result):
        return result

    # Step 3: reflected (if not already tried)
    if not checked_reverse:
        result = w.tp_richcompare_impl(tx, v, reflected)
        if not is_richcompare_not_implemented(result):
            return result

    # Step 4: fallback
    if op in ("__eq__", "__ne__"):
        identity = vt_identity_compare(v, w)
        if identity is not None:
            if op == "__ne__":
                return ConstantVariable.create(not identity.as_python_constant())
            return identity
        unimplemented(
            gb_type="richcompare identity fallback undetermined",
            context=f"generic_richcompare({v}, {w}, {op})",
            explanation="Cannot determine object identity for comparison fallback.",
            hints=[*graph_break_hints.SUPPORTABLE],
        )
    else:
        raise_type_error(
            tx,
            f"'{_OP_STR[op]}' not supported between instances of "
            f"'{v.python_type_name()}' and '{w.python_type_name()}'",
        )


def generic_richcompare_bool(
    tx: "InstructionTranslatorBase",
    v: VariableTracker,
    w: VariableTracker,
    op: str,
) -> VariableTracker:
    """Dynamo's PyObject_RichCompareBool for eq/ne.

    https://github.com/python/cpython/blob/e76aa128fe/Objects/object.c#L1046-L1080

    Like generic_richcompare, but with an identity shortcut first: if v
    and w are the same Python object, eq is True and ne is False. This
    matters for NaN (nan is nan -> True, but nan == nan -> False). Used by
    container comparisons (list_richcompare, tuplerichcompare) which call
    PyObject_RichCompareBool per element in CPython.
    """
    if op not in ("__eq__", "__ne__"):
        raise AssertionError(f"generic_richcompare_bool only supports eq/ne, got {op}")
    identity = vt_identity_compare(v, w)
    if identity is not None and identity.as_python_constant():
        return ConstantVariable.create(op == "__eq__")
    return generic_richcompare(tx, v, w, op)


def generic_hash_impl(
    tx: "InstructionTranslatorBase", obj: VariableTracker
) -> tuple[int, bool]:
    """Internal API: compute hash as (value, is_fake).

    Dispatches to the VT's hash_impl.  Called by generic_hash (which wraps
    the result in a VT), container hash_impls (which propagate is_fake),
    and HashableTracker (which just needs the int).
    """
    return obj.hash_impl(tx)


def generic_hash(
    tx: "InstructionTranslatorBase", obj: VariableTracker
) -> VariableTracker:
    """User-facing API: mirrors PyObject_Hash, returns a VariableTracker.

    https://github.com/python/cpython/blob/e76aa128fe/Objects/object.c#L1101-L1115

    Wraps the result in ConstantVariable or FakeIdVariable depending on
    whether the hash depends on a sourceless object's identity.
    """
    from .constant import ConstantVariable, FakeIdVariable, FakeValueKind

    h, is_fake = generic_hash_impl(tx, obj)
    if is_fake:
        return FakeIdVariable(h, kind=FakeValueKind.HASH)
    return ConstantVariable.create(h)


def pysequence_contains(
    tx: "InstructionTranslatorBase", obj: "VariableTracker", item: "VariableTracker"
) -> "VariableTracker":
    """
    Implements PySequence_Contains semantics for VariableTracker objects.

    If the object has sq_contains (i.e., __contains__), calls obj.sq_contains_impl(tx, item).
    Otherwise falls back to iterating over obj and comparing each element.
    """
    # ref: https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L2272-L2283
    sq_contains = obj.tp_as_sequence.sq_contains
    if sq_contains is not None:
        return obj.sq_contains_impl(tx, item)
    else:
        # iter fallback handles both __iter__ and __getitem__ sequence protocol cases
        it = generic_getiter(tx, obj)
        return VariableTracker.build(
            tx, polyfills.impl_CONTAINS_OP_fallback
        ).call_function(tx, [item, it], {})


# Metaclasses whose __subclasscheck__ Dynamo can't trace but whose
# behavior we're willing to observe at trace time via Python's issubclass.
# Each entry trades fidelity to the metaclass's side effects (e.g. ABC's
# subclass cache mutation) for coverage of the common case.
_CONSTANT_FOLD_SUBCLASSCHECK_METACLASSES: tuple[type, ...] = (
    abc.ABCMeta,
    torch._C._TensorMeta,  # actually just type.__subclasscheck__, but easier to list it here
    enum.EnumMeta,
)


def generic_issubclass(
    tx: "InstructionTranslatorBase",
    derived: VariableTracker,
    cls: VariableTracker,
) -> VariableTracker:
    """Mirrors CPython's PyObject_IsSubclass / object_issubclass.

    https://github.com/python/cpython/blob/v3.13.0/Objects/abstract.c#L2766-L2823

    This only attempts to replicate object_issubclass, otherwise we delegate to cpython
    """
    derived_py = derived.get_real_python_backed_value()
    cls_py = cls.get_real_python_backed_value()
    if derived_py is NO_SUCH_SUBOBJ or cls_py is NO_SUCH_SUBOBJ:
        unimplemented(
            gb_type="issubclass() with unsupported arguments",
            context=f"issubclass({derived}, {cls})",
            explanation="Arguments to issubclass() must be backed by python values.",
            hints=[
                "Make sure your arguments are types.",
                *graph_break_hints.USER_ERROR,
                *graph_break_hints.SUPPORTABLE,
            ],
        )
    cls_type = maybe_get_python_type(cls)

    # Step 1: PyType_CheckExact fast path — abstract.c L2772
    if cls_type is type:
        try:
            return ConstantVariable.create(
                issubclass(
                    derived_py,  # pyrefly: ignore [bad-argument-type]
                    cls_py,  # pyrefly: ignore [invalid-argument]
                )
            )
        except TypeError as e:
            raise_observed_exception(TypeError, tx, args=list(e.args))

    # Step 2: PEP 604 Union (e.g. ``int | str``) — abstract.c L2779-2781.
    union_types = {types.UnionType}
    if sys.version_info < (3, 14):
        union_types.add(
            typing._UnionGenericAlias  # pyrefly: ignore [missing-attribute]
        )
    if cls_type in union_types:
        # TODO can trace this once TypingVariable is removed
        args = typing.get_args(cls_py)
        cls = VariableTracker.build(tx, args)

    # Step 3: tuple of classes — abstract.c L2783-2799.  Check for
    # TupleVariable instead of tuple to make the type checker happy.
    from .lists import TupleVariable

    if isinstance(cls, TupleVariable):
        for item in cls.items:
            r = generic_issubclass(tx, derived, item)
            if isinstance(r, ConstantVariable) and r.value:
                return ConstantVariable.create(True)
        return ConstantVariable.create(False)

    # Allowlist short-circuit for Step 4: constant-fold via Python's
    # issubclass for metaclasses whose ``__subclasscheck__`` Dynamo can't
    # trace (see _CONSTANT_FOLD_SUBCLASSCHECK_METACLASSES).  Note that ABCMeta
    # is problematic in particular since it caches registered subclasses.
    # Ideally this should be traced or guarded
    if isinstance(cls_py, type) and issubclass(
        type(cls_py), _CONSTANT_FOLD_SUBCLASSCHECK_METACLASSES
    ):
        try:
            return ConstantVariable.create(
                issubclass(
                    derived_py,  # pyrefly: ignore [bad-argument-type]
                    cls_py,
                )
            )
        except TypeError as e:
            raise_observed_exception(TypeError, tx, args=list(e.args))

    # TypeError gate, mirroring abstract.c L2822 ``recursive_issubclass``:
    # CPython reaches that fallback when ``_PyObject_LookupSpecial`` for
    # ``__subclasscheck__`` returns NULL, and its first action is
    # ``check_class(cls, ...)`` which raises this TypeError.  We check
    # eagerly because Dynamo's ``call_method`` below would graph-break
    # rather than cleanly signal "no such method".
    if not isinstance(cls_py, type):
        raise_type_error(
            tx,
            "issubclass() arg 2 must be a class, a tuple of classes, or a union",
        )

    # Step 4: general case — call ``__subclasscheck__`` on cls's metaclass
    # (abstract.c L2801-2815).  Runs user code on a custom metaclass.
    result = cls.call_method(tx, "__subclasscheck__", [derived], {})

    # Coerce to bool (PyObject_IsTrue, abstract.c L2812).
    return generic_is_true(tx, result)


# ── tp_getattro ──────────────────────────────────────────────────────
#
# Dynamo's PyObject_GetAttr / PyObject_GenericGetAttr.
#
# CPython references:
#   PyObject_GetAttr:        Objects/object.c#L1259-L1283
#   PyObject_GenericGetAttr: Objects/object.c#L1611-L1683
#   _PyType_LookupRef:       Objects/typeobject.c#L5208-L5262
#
# PyObject_GetAttr(obj, name):
#     tp = Py_TYPE(obj)
#     if tp->tp_getattro:
#         return tp->tp_getattro(obj, name)
#     ...
#     raise AttributeError
#
# Dispatch path:
#     LOAD_ATTR / getattr() -> GetAttrBuiltinVariable -> generic_getattr
#         -> obj.tp_getattro_impl(tx, name)
#
# The base VariableTracker.tp_getattro_impl tries object_generic_getattr()
# first (MRO walk + descriptor protocol), falling back to const_getattr
# on _UnhandledDescriptorError.  Callers of object_generic_getattr
# directly must handle _UnhandledDescriptorError at every step (2, 4,
# and 7), not just for unrecognized descriptor types.
#
# VTs with custom tp_getattro (TensorVariable, NNModuleVariable,
# UserDefinedClassVariable, SuperVariable) override tp_getattro_impl.

_NO_DEFAULT = object()


_UnhandledDescriptorError = UnhandledDescriptorError


def mro_lookup(py_type: type, name: str) -> object:
    """Walk py_type.__mro__ to find *name* in the class hierarchy.

    Mirrors CPython's _PyType_LookupRef (Objects/typeobject.c).
    Searches only the class chain (py_type.__mro__), NOT the metaclass
    chain.  Returns the raw descriptor/value from the class __dict__,
    or NO_SUCH_SUBOBJ if not found.
    """
    for base in py_type.__mro__:
        if name in base.__dict__:
            return base.__dict__[name]
    return NO_SUCH_SUBOBJ


def _resolve_descriptor_get(
    tx: "InstructionTranslatorBase",
    type_attr: object,
    obj: VariableTracker,
    class_vt: VariableTracker,
    source: "Source | None",
) -> "VariableTracker | None":
    """Invoke tp_descr_get on a type attribute if it's a descriptor.

    Handles all descriptor types that have dedicated VTs with
    tp_descr_get_impl.  Returns None if type_attr is not a recognized
    descriptor type (plain class variable).
    """
    import types as _types

    if isinstance(type_attr, property):
        prop_vt = variables.PropertyVariable(type_attr, source=source)
        return prop_vt.tp_descr_get_impl(tx, obj, class_vt)
    if isinstance(type_attr, _types.MemberDescriptorType):
        md_vt = variables.MemberDescriptorVariable(type_attr, source=source)
        return md_vt.tp_descr_get_impl(tx, obj, class_vt)
    if isinstance(type_attr, _types.GetSetDescriptorType):
        gs_vt = variables.GetSetDescriptorVariable(type_attr, source=source)
        return gs_vt.tp_descr_get_impl(tx, obj, class_vt)
    _tuplegetter = collections._tuplegetter  # pyrefly: ignore[missing-attribute]
    if isinstance(type_attr, _tuplegetter):
        tg_vt = variables.TupleGetterVariable(type_attr, source=source)
        return tg_vt.tp_descr_get_impl(tx, obj, class_vt)
    if isinstance(type_attr, staticmethod):
        sm_vt = variables.StaticMethodVariable(type_attr, source=source)
        return sm_vt.tp_descr_get_impl(tx, obj, class_vt)
    if isinstance(type_attr, classmethod):
        cm_vt = variables.ClassMethodVariable(type_attr, source=source)
        return cm_vt.tp_descr_get_impl(tx, obj, class_vt)
    if isinstance(type_attr, _types.ClassMethodDescriptorType):
        cmd_vt = variables.ClassMethodDescriptorVariable(type_attr, source=source)
        return cmd_vt.tp_descr_get_impl(tx, obj, class_vt)
    if isinstance(type_attr, _types.WrapperDescriptorType):
        wd_vt = variables.WrapperDescriptorVariable(
            type_attr, owner=class_vt, source=source
        )
        return wd_vt.tp_descr_get_impl(tx, obj, class_vt)
    if isinstance(type_attr, _types.MethodDescriptorType):
        md_vt = variables.MethodDescriptorVariable(
            type_attr, owner=class_vt, source=source
        )
        return md_vt.tp_descr_get_impl(tx, obj, class_vt)
    if isinstance(type_attr, _types.FunctionType):
        return variables.UserMethodVariable(type_attr, obj, source=source)

    return None


# BuiltinFunctionType is intentionally excluded: _resolve_descriptor_get
# does not handle it, so it falls through to _UnhandledDescriptorError
# and generic_getattr's GetAttrVariable fallback.
_METHOD_TYPES = (
    types.FunctionType,
    types.MethodDescriptorType,
    types.WrapperDescriptorType,
)


def _is_method_type(type_attr: object) -> bool:
    return isinstance(type_attr, _METHOD_TYPES)


def _has_custom_call_method(obj: VariableTracker) -> bool:
    for cls in type(obj).__mro__:
        if cls is VariableTracker:
            return False
        if "call_method" in cls.__dict__:
            return True
    return False


def object_generic_getattr(
    tx: "InstructionTranslatorBase",
    obj: VariableTracker,
    name: str,
) -> VariableTracker:
    """Dynamo's PyObject_GenericGetAttr.

    https://github.com/python/cpython/blob/e76aa128fe/Objects/object.c#L1611-L1683

    Implements the standard attribute lookup algorithm using the VT's
    python_type() for MRO walking, and hooks on the VT for instance dict
    and __getattr__ fallback.

    Steps:
      1. MRO walk on python_type() for type_attr
      2. Data descriptor -> invoke tp_descr_get
      3. Instance dict -> obj.lookup_instance_dict(tx, name)
      4. Non-data descriptor -> invoke tp_descr_get
      5. Plain class variable -> wrap in VT
      6. __getattr__ fallback -> obj.call_getattr_fallback(tx, name)
      7. AttributeError
    """
    from .user_defined import is_data_descriptor

    py_type = obj.python_type()
    source = obj.source and AttrSource(obj.source, name)

    # Step 1: MRO walk.
    type_attr = mro_lookup(py_type, name)

    # Step 2: Data descriptor takes priority over instance dict.
    if type_attr is not NO_SUCH_SUBOBJ and is_data_descriptor(type_attr):
        class_vt = VariableTracker.build(tx, py_type)
        result = _resolve_descriptor_get(tx, type_attr, obj, class_vt, source)
        if result is not None:
            return result
        raise _UnhandledDescriptorError(
            f"object_generic_getattr: unhandled data descriptor "
            f"{type(type_attr)} for {name}"
        )

    # Step 3: Instance dict (tp_dictoffset).
    instance_result = obj.lookup_instance_dict(tx, name)
    if instance_result is not None:
        return instance_result

    # Step 4: Non-data descriptor with __get__.
    if type_attr is not NO_SUCH_SUBOBJ and hasattr(type(type_attr), "__get__"):
        # If the VT dispatches this method through call_method (a hand-written
        # override or a tp_methods entry), return a CallMethodVariable that
        # dispatches through call_method instead of inlining the resolved
        # method directly.  This preserves custom tracing logic (side effects,
        # graph nodes, suppression) that MRO-based resolution via
        # UserMethodVariable would bypass.
        if _is_method_type(type_attr) and (
            obj._lookup_tp_table(name, "tp_methods") is not None
            or _has_custom_call_method(obj)
        ):
            return variables.CallMethodVariable(obj, name, source=source)

        class_vt = VariableTracker.build(tx, py_type)
        result = _resolve_descriptor_get(tx, type_attr, obj, class_vt, source)
        if result is not None:
            return result
        raise _UnhandledDescriptorError(
            f"object_generic_getattr: unhandled non-data descriptor "
            f"{type(type_attr)} for {name}"
        )

    # Step 5: Plain class variable (no __get__).
    if type_attr is not NO_SUCH_SUBOBJ:
        return VariableTracker.build(tx, type_attr, source)

    # Step 6: __getattr__ fallback.
    getattr_result = obj.call_getattr_fallback(tx, name)
    if getattr_result is not None:
        return getattr_result

    # Step 7: Attribute not found -- signal to caller to fall back.
    raise _UnhandledDescriptorError(
        f"object_generic_getattr: '{py_type.__name__}' has no attribute '{name}'"
    )


def generic_getattr(
    tx: "InstructionTranslatorBase",
    obj: VariableTracker,
    name: str,
    default: "VariableTracker | object" = _NO_DEFAULT,
) -> VariableTracker:
    """Dynamo's PyObject_GetAttr: attribute access dispatch.

    Checks side effects for pending attribute mutations, then dispatches
    to obj.tp_getattro_impl(tx, name).  On NotImplementedError, falls back
    to GetAttrVariable (deferred resolution).
    """
    from .user_defined import is_data_descriptor

    # NOTE [Tensor "grad" and "_grad" attr]
    if obj.is_tensor() and name == "_grad":
        name = "grad"

    # Side effects: check for pending attribute mutations.
    if tx.output.side_effects.has_pending_mutation_of_attr(obj, name):
        if not isinstance(obj, variables.UserDefinedObjectVariable):
            return tx.output.side_effects.load_attr(obj, name)
        if tx.output.side_effects.has_pending_mutation_of_attr(
            obj, name, AttrMutationKind.INSTANCE_DICT
        ):
            value = tx.output.side_effects.load_attr(obj, name, deleted_ok=True)
            type_attr = obj.lookup_class_mro_attr(name)
            if not isinstance(value, variables.DeletedVariable) and (
                type_attr is NO_SUCH_SUBOBJ or not is_data_descriptor(type_attr)
            ):
                return value

    # Handle default for getattr(obj, name, default).
    if default is not _NO_DEFAULT:
        hasattr_var = obj.call_obj_hasattr(tx, name)
        if not hasattr_var.is_constant_match(True, False):
            raise AssertionError(
                f"hasattr_var must be a constant True or False, got {hasattr_var}"
            )
        if not hasattr_var.as_python_constant():
            return default  # type: ignore[return-value]

    # tp_getset/tp_members are data descriptors: resolve ahead of the VT's
    # tp_getattro so a tp_getattro_impl override need not repeat the consult.
    getset = obj.lookup_tp_getset_member(name)
    if getset is not None:
        result = getset.getter(obj, tx)
        if result is not None:
            return result

    # Core dispatch: call the VT's tp_getattro_impl (tp_getattro).
    source = obj.source and AttrSource(obj.source, name)
    try:
        return obj.tp_getattro_impl(tx, name)
    except AsPythonConstantNotImplementedError:
        raise
    except NotImplementedError:
        return variables.GetAttrVariable(obj, name, source=source)