"""
Python polyfills for common builtins.
"""

# NOTE: 1. Please do not import any submodule in the directory here to avoid circular imports.
#       2. While adding a new polyfill module, also add it to POLYFILLED_MODULE_NAMES in loader.py.
#          Add it in the TYPE_CHECKING block below as well.

from __future__ import annotations

import importlib
import sys as py_sys
import types
from collections import OrderedDict
from collections.abc import Callable, Hashable, Iterable, Iterator, Mapping, Sequence
from itertools import repeat as _repeat
from operator import eq, ge, gt, le, lt, ne
from typing import Any, TYPE_CHECKING, TypeGuard, TypeVar
from typing_extensions import TypeIs

import torch


T = TypeVar("T")
U = TypeVar("U")
C = TypeVar("C")


if TYPE_CHECKING:
    from types import ModuleType

    from ..utils import dict_keys

    # Load by torch._dynamo.polyfills.loader
    # See also the POLYFILLED_MODULE_NAMES in torch/_dynamo/polyfills/loader.py
    # Put the submodules here to avoid circular imports
    from . import (
        _collections as _collections,
        builtins as builtins,
        functools as functools,
        heapq as heapq,
        io as io,
        itertools as itertools,
        operator as operator,
        os as os,
        pytree as pytree,
        struct as struct,
        sys as sys,
        torch_c_nn as torch_c_nn,
        traceback as traceback,
    )

from torch.overrides import BaseTorchFunctionMode


# These classes handle support for TorchFunctionModes across
# graph breaks
# Today the TorchFunctionMode enter (for the classes we support)
# simply pushes the mode onto the stack. Since after this occurs
# the stack is mutated, and we replay these mutations, we don't need
# any cleanup logic to be run once the graph break occurs, we simply replay
# these mutations to ensure at the graph break the torch function mode stack is correct
#  and reconstruct the torch function mode stack normally
# when we compile the resume function on the other side of the break.
# However, to ensure we exit properly
# in the resume function, we need to re-enter the contexts as we do other contexts.
# These contexts do nothing on enter, but provide the correct exit logic to ensure
# the stack state is correct.
class NoEnterTorchFunctionMode(BaseTorchFunctionMode):
    def __enter__(self) -> None:
        pass


# Used by WrappedUserFunctionVariable and similar to inline decorated function
# calls with bytecode backing. Without this, the context enter/exit happens in
# Python-level VT code, so a nested graph break inside `fn` would skip applying
# the context in the compiled fn/resume. By inlining through this polyfill, the
# `with` statement has real bytecode that the resume function can continue from.
def _fn_with_ctx(ctx: Any, fn: Callable[..., T], *args: Any, **kwargs: Any) -> T:
    with ctx:
        return fn(*args, **kwargs)


def index(
    iterator: Iterator[T],
    item: T,
    start: int = 0,
    end: int | None = None,
    not_found_msg: str = "{!r} is not in list",
) -> int:
    from itertools import islice

    for i, elem in islice(enumerate(iterator), start, end):
        if elem is item or elem == item:
            return i
    # Callers pass the message their sequence type raises in CPython, which is
    # not uniform: list/deque repr the value, tuple ignores it.
    raise ValueError(not_found_msg.format(item))


def repeat(item: T, count: int) -> Iterator[T]:
    for _ in range(count):
        yield item


def radians(x: float) -> float:
    import math

    return math.pi / 180.0 * x


def _sumprod_pairs(p: Iterable[Any], q: Iterable[Any]) -> Iterator[tuple[Any, Any]]:
    # Advance p and q in lockstep like CPython's math_sumprod_impl.
    p_it = iter(p)
    q_it = iter(q)
    while True:
        try:
            p_i = next(p_it)
        except StopIteration:
            try:
                next(q_it)
            except StopIteration:
                return
            raise ValueError("Inputs are not the same length") from None
        try:
            q_i = next(q_it)
        except StopIteration:
            raise ValueError("Inputs are not the same length") from None
        yield p_i, q_i


def sumprod(p: Iterable[Any], q: Iterable[Any], /) -> Any:
    # Materialize arbitrary iterables and call math.sumprod again on the lists.
    # Lists of constants are constant-folded, which keeps CPython's
    # extended-precision float accumulation; anything else goes to
    # sumprod_generic.
    import math

    # Narrows math for mypy on <3.12 stubs; the handler only dispatches here on 3.12+.
    if not hasattr(math, "sumprod"):
        raise NotImplementedError("math.sumprod requires Python 3.12+")
    ps: list[Any] = []
    qs: list[Any] = []
    for p_i, q_i in _sumprod_pairs(p, q):
        ps.append(p_i)
        qs.append(q_i)
    return math.sumprod(ps, qs)


def sumprod_generic(p: Iterable[Any], q: Iterable[Any], /) -> Any:
    # Generic path of CPython's math_sumprod_impl, without the float fast path.
    # Used for any list containing a non-constant element, so float constants
    # in that list are accumulated plainly too, like the sum polyfill in
    # polyfills/builtins.py.
    total = 0
    for p_i, q_i in _sumprod_pairs(p, q):
        total = total + p_i * q_i
    return total


def infer_size(a: Sequence[Any], b: Sequence[Any]) -> torch.Size:
    from torch.fx.experimental.symbolic_shapes import guard_or_false

    # Keep this in sync with torch._subclasses.fake_impls.infer_size and
    # aten/src/ATen/ExpandUtils.cpp::infer_size_impl.  In particular, check the
    # broadcasting cases before size equality: the former are often statically
    # known, while the latter may need to become a deferred runtime assertion.
    dims_a = len(a)
    dims_b = len(b)
    ndim = max(dims_a, dims_b)
    expanded_sizes = [0] * ndim

    for i in range(ndim - 1, -1, -1):
        offset = ndim - 1 - i
        dim_a = dims_a - 1 - offset
        dim_b = dims_b - 1 - offset
        size_a = a[dim_a] if dim_a >= 0 else 1
        size_b = b[dim_b] if dim_b >= 0 else 1

        # Dynamo requires torch._check message closures to capture only Python
        # constants, so report the static dimension without capturing sizes.
        error_message = f"invalid broadcast shape at dimension {i}"
        torch._check(
            guard_or_false(size_a == 1)
            or guard_or_false(size_b == 1)
            or size_a == size_b,
            lambda: error_message,
        )
        expanded_sizes[i] = size_b if guard_or_false(size_a == 1) else size_a

    return torch.Size(expanded_sizes)


def impl_IS_MAPPING(a: object) -> TypeIs[Mapping[Any, Any]]:
    return isinstance(a, Mapping)


def impl_MATCH_SEQUENCE(a: object) -> TypeGuard[Sequence[Any]]:
    return isinstance(a, Sequence) and not isinstance(a, (str, bytes, bytearray))


def _match_class_attr(obj: object, name: str, seen: set[str]) -> object:
    if name in seen:
        raise TypeError(f"{type(obj)} got multiple sub-patterns for attribute {name}")

    attr = getattr(obj, name)
    seen.add(name)
    return attr


def impl_MATCH_CLASS(
    subject: object, cls: type, nargs: int, kwargs: tuple[str, ...]
) -> tuple[object, ...] | None:
    if not isinstance(cls, type):
        raise TypeError("called match pattern must be a class")

    if not isinstance(subject, cls):
        return None

    typ = type(subject)
    match_self = False
    match_args = ()

    attrs = []
    seen = set()

    if nargs:
        if hasattr(typ, "__match_args__"):
            match_args = typ.__match_args__

            if not isinstance(match_args, tuple):
                raise TypeError(
                    f"{typ}.__match_args__ must be a tuple, (got {type(match_args)})"
                )

            for name in match_args[:nargs]:
                if not isinstance(name, str):
                    raise TypeError(
                        f"__match_args__ elements must be strings (got {type(name)})"
                    )
                attrs.append(_match_class_attr(subject, name, seen))
        else:
            # We should somehow check if the type has TPFLAGS_MATCH_SELF set
            # match_self is only true if TPFLAGS_MATCH_SELF is set, but there is
            # no way to check for it directly in Python. So we assume it is set
            # if there are no __match_args__
            match_self = True
            attrs.append(subject)

        allowed = 1 if match_self else len(match_args)
        if allowed < nargs:
            raise TypeError(
                f"accepts {allowed} positional sub-patterns ({nargs} given)"
            )

    for name in kwargs:
        attrs.append(_match_class_attr(subject, name, seen))

    return tuple(attrs)


def impl_MATCH_KEYS(obj: Mapping[T, U], keys: tuple[T, ...]) -> tuple[U, ...] | None:
    if not isinstance(obj, Mapping):
        raise AssertionError(f"Expected a Mapping, got {type(obj)}")
    if all(key in obj for key in keys):
        return tuple(obj[key] for key in keys)
    else:
        return None


def impl_CONTAINS_OP_fallback(a: T, b: Iterable[T]) -> bool:
    # performs fallback "a in b"
    # CPython: PySequence_Contains → _PySequence_IterSearch → PyObject_GetIter
    # PyObject_GetIter itself falls back to PySequence_GetItem when tp_iter is NULL.
    if hasattr(b, "__iter__"):
        for x in b:
            if x == a:
                return True
        return False
    if hasattr(b, "__getitem__"):
        i = 0
        while True:
            try:
                if b.__getitem__(i) == a:
                    return True
                i += 1
            except IndexError:
                return False
    raise TypeError(f"argument of type {type(b)} is not iterable")


def accumulate_grad(
    x: torch.Tensor,
    variable_grad: torch.Tensor | None,
    new_grad: torch.Tensor | None,
) -> torch.Tensor | None:
    # polyfills according to the Gradient Layout Contract
    if new_grad is None:
        return variable_grad
    new_grad_strided = torch.empty_like(x)
    new_grad_strided.copy_(new_grad)
    if variable_grad is None:
        return new_grad_strided
    elif variable_grad.is_sparse and not new_grad_strided.is_sparse:
        return new_grad_strided + variable_grad
    elif torch.is_grad_enabled():
        return variable_grad + new_grad_strided
    else:
        variable_grad.add_(new_grad_strided)
        return variable_grad


def accumulate_grad_no_alias(
    x: torch.Tensor,
    variable_grad: torch.Tensor | None,
    new_grad: torch.Tensor | None,
) -> torch.Tensor | None:
    # Mirrors inductor::accumulate_grad_: same gradient layout logic as
    # accumulate_grad, but the returned grad must not alias any input.
    if new_grad is None:
        if variable_grad is None:
            return None
        return variable_grad.clone()
    new_grad_strided = torch.empty_like(x)
    new_grad_strided.copy_(new_grad)
    if variable_grad is None:
        return new_grad_strided
    elif variable_grad.is_sparse and not new_grad_strided.is_sparse:
        return new_grad_strided + variable_grad
    elif torch.is_grad_enabled():
        return variable_grad + new_grad_strided
    else:
        result = variable_grad.clone()
        result.add_(new_grad_strided)
        return result


# This mirrors
# https://github.com/python/cpython/blob/a1c52d1265c65bcf0d9edf87e143843ad54f9b8f/Objects/listobject.c#L3352-L3413
def list_cmp(
    op: Callable[[Any, Any], bool], left: Sequence[T], right: Sequence[T]
) -> bool:
    """emulate `(1,2,3) > (1,2)` etc"""

    # Optimization: For equality, short-circuit if lengths differ
    # This avoids iterating through elements and triggering guards on SymInts
    left_len = len(left)
    right_len = len(right)

    if op is eq and left_len != right_len:
        return False
    if op is ne and left_len != right_len:
        return True

    # Apply `op` to the first pair that differ
    for a, b in zip(left, right):
        if a != b:
            return op(a, b)

    # No more pairs to compare, so compare sizes.
    return op(left_len, right_len)


def dict___eq__(d: dict[T, U], other: dict[T, U]) -> bool:
    # dict_equal reads the C struct (ma_used, dk_entries, _Py_dict_lookup), so
    # every access below goes through the unbound dict methods -- a dict
    # subclass overriding __len__ / keys / __getitem__ must not be consulted.
    # https://github.com/python/cpython/blob/e76aa128fe/Objects/dictobject.c#L4125-L4185
    if (dict.__len__(d) != dict.__len__(other)) or (dict.keys(d) != dict.keys(other)):
        return False

    if all(isinstance(a, OrderedDict) for a in (d, other)):
        return list(dict.items(d)) == list(dict.items(other))

    # CPython's dict_equal uses PyObject_RichCompareBool for value
    # comparison, which has an identity shortcut (if v is w, eq is True).
    # This matters for NaN: {k: nan} == {k: nan} is True when same nan.
    for k, v in dict.items(d):
        ov = dict.__getitem__(other, k)
        if v is not ov and v != ov:
            return False

    return True


def dictview_richcompare(
    op: Callable[[Any, Any], bool], self: Iterable[T], other: Iterable[T]
) -> bool:
    """Mirrors dictview_richcompare for dict_keys/dict_items vs set/frozenset.

    https://github.com/python/cpython/blob/e76aa128fe/Objects/dictobject.c#L5952-L6010
    Uses len() and ``in`` so that Dynamo traces through sq_length/sq_contains.
    """
    len_self = len(self)  # type: ignore[arg-type]
    len_other = len(other)  # type: ignore[arg-type]

    if op is eq:
        if len_self != len_other:
            return False
        return all(item in other for item in self)
    if op is ne:
        if len_self != len_other:
            return True
        return not all(item in other for item in self)
    if op is lt:
        if len_self >= len_other:
            return False
        return all(item in other for item in self)
    if op is le:
        if len_self > len_other:
            return False
        return all(item in other for item in self)
    if op is gt:
        if len_self <= len_other:
            return False
        return all(item in self for item in other)
    # ge
    if len_self < len_other:
        return False
    return all(item in self for item in other)


def assert_dict_equal(
    self_: Any, d1: dict[T, U], d2: dict[T, U], msg: str | None = None
) -> None:
    self_.assertTrue(d1 == d2, msg)


def assert_multi_line_equal(
    self_: Any, first: T, second: T, msg: str | None = None
) -> None:
    return self_.assertTrue(first == second, msg)


# The original impl. uses difflib
def assert_sequence_equal(
    self_: Any,
    seq1: Sequence[T],
    seq2: Sequence[T],
    msg: str | None = None,
    seq_type: type[Any] | None = None,
) -> None:
    return self_.assertTrue(seq1 == seq2, msg)


def getattr_and_trace(*args: Any, **kwargs: Any) -> Any:
    wrapper_obj = args[0]
    attr_name = args[1]
    fn = getattr(wrapper_obj, attr_name)
    return fn(*args[2:], **kwargs)


def getattr_and_trace_no_nested_graph_breaks(*args: Any, **kwargs: Any) -> Any:
    with torch._dynamo.disable_nested_graph_breaks():
        return getattr_and_trace(*args, **kwargs)


def mapping_get(obj: Mapping[T, U], key: T, value: U | None = None, /) -> U | None:
    try:
        return obj.__getitem__(key)
    except KeyError:
        return value


def instantiate_user_defined_class_object(
    cls: type[T], /, *args: Any, **kwargs: Any
) -> T:
    obj = cls.__new__(cls, *args, **kwargs)

    # Only call __init__ if the object's type is a subclass of cls.
    # CPython uses PyType_IsSubtype(Py_TYPE(obj), type) at the C level, which does NOT
    # go through metaclass __instancecheck__. Using isinstance() here would be wrong
    # for classes with custom __instancecheck__ (e.g. torch.ByteStorage).
    # Reference: https://github.com/python/cpython/blob/3.12/Objects/typeobject.c#L1670-L1673
    if issubclass(type(obj), cls):
        init_result = obj.__init__(*args, **kwargs)
        if init_result is not None:
            raise TypeError(
                f"__init__() should return None, not {type(init_result).__name__!r}"
            )
    return obj


def mutable_mapping_update(
    self,
    data: Mapping[T, U] | Iterable[tuple[T, U]] = (),
    /,
    **kwargs: Any,
) -> None:
    if isinstance(data, Mapping):
        # Merge standard mapping with PyMapping_Items
        for key, value in data.items():
            self[key] = value
    # FIXME: Enabling the `elif`-branch below needs too many `VariableClass.call_obj_hasattr` changes.
    #   >>> class Foo:
    #   ...     def __init__(self):
    #   ...         self.keys = lambda: ['a', 'b', 'c']  # not required to be a method
    #   ...
    #   ...     def __getitem__(self, key):
    #   ...         return 0
    #   ...
    #   >>> dict(Foo())
    #   {'a': 0, 'b': 0, 'c': 0}
    #
    # > This is a rare case, so we comment it out for now.
    #
    # elif hasattr(data, "keys"):
    #     # Merge mapping-like object with PyMapping_Keys + PyObject_GetItem
    #     for key in data.keys():
    #         self[key] = data[key]
    else:
        if not isinstance(data, Iterable):
            raise TypeError(f"{type(data).__name__!r} object is not iterable")
        # Likely a sequence of pairs
        for key, value in data:
            self[key] = value

    if kwargs:
        for key, value in kwargs.items():
            self[key] = value


# Used with something like dict(obj)
def construct_dict(
    cls: type[T],
    data: Mapping[object, object] | Iterable[tuple[object, object]] = (),
    /,
    **kwargs: Any,
) -> T:
    self = cls.__new__(cls)
    mutable_mapping_update(self, data, **kwargs)
    return self


def foreach_map_fn(*args: Any) -> Any:
    op = args[0]
    new_args: list[Any] = []
    at_least_one_list = False
    for arg in args[1:]:
        if not isinstance(arg, (list, tuple)):
            new_args.append(_repeat(arg))
        else:
            at_least_one_list = True
            new_args.append(arg)

    # Just apply op once to args if there are no lists
    if not at_least_one_list:
        return op(*args[1:])

    out = []
    for unpacked in zip(*new_args):
        out.append(op(*unpacked))

    return out


def foreach_lerp_inplace(
    self,
    end: list[torch.Tensor] | tuple[torch.Tensor, ...],
    weight: float | int | torch.Tensor,
) -> list[torch.Tensor] | tuple[torch.Tensor, ...]:
    # Decompose lerp via addcmul_ for FMA.  Uses the same dual-formula
    # approach as CUDA's native lerp to get bitwise identical results:
    #   |w| <  0.5  (low):  fma(w, diff, start)
    #   |w| >= 0.5  (high): fma(-(1-w), diff, end)
    # For tensor weights (e.g. 0-dim tensor from tensor betas in Adam) the
    # low formula is always used because the native lerp_scalar lowering
    # would crash on float(weight) for symbolic expressions.
    diff = torch._foreach_sub(end, self)
    if isinstance(weight, torch.Tensor):
        # Select base and weight for the dual formula before a single addcmul:
        #   low  (|w| <  0.5): fma(w,      diff, self)
        #   high (|w| >= 0.5): fma(-(1-w), diff, end)
        mask = weight.abs() >= 0.5
        neg_omw = -(1.0 - weight)
        w = torch.where(mask, neg_omw, weight)
        bases = [torch.where(mask, e, s) for s, e in zip(self, end)]
        w_list = [w] * len(diff)
        torch._foreach_addcmul_(bases, w_list, diff)
        for s, b in zip(self, bases):
            s.copy_(b)
    else:
        abs_weight = weight if weight >= 0 else -weight
        if abs_weight >= 0.5:
            # High formula: end + (-(1-w)) * diff  →  fma(-(1-w), diff, end)
            # Compute 1-w in target dtype to match CUDA rounding.
            d0 = self[0]
            neg_omw = -(1.0 - torch.tensor(weight, dtype=d0.dtype, device=d0.device))
            neg_omw_list = [neg_omw] * len(diff)
            for s, e in zip(self, end):
                s.copy_(e)
            torch._foreach_addcmul_(self, neg_omw_list, diff)
        else:
            # Low formula: start + w * diff  →  fma(w, diff, start)
            weights = [torch.full_like(d, weight) for d in diff]
            torch._foreach_addcmul_(self, weights, diff)
    return self


def foreach_pow_scalar(
    scalar: Any, exps: Sequence[bool | complex | float | int]
) -> tuple[torch.Tensor, ...]:
    return torch._foreach_pow([scalar for _ in exps], exps)


def predicate(obj: object) -> bool:
    # This will cause the rest of dynamo to handle the if statement correctly, so we don't have to rewrite it here.
    # We can't just use bool() here since we can't trace into that in general.
    if obj:
        return True
    return False


def group_tensors_by_device_and_dtype(
    tensorlistlist: list[list[torch.Tensor | None]], with_indices: bool = False
) -> dict[tuple[torch.device, torch.dtype], tuple[list[list[Any]], list[int]]]:
    """Pure Python implementation of torch._C._group_tensors_by_device_and_dtype.

    Groups tensors by their device and dtype. This is useful before sending
    tensors off to a foreach implementation, which requires tensors to be on
    one device and dtype.

    Args:
        tensorlistlist: A list of lists of tensors (tensors can be None).
        with_indices: If True, track original indices in the output.

    Returns:
        A dict mapping (device, dtype) tuples to (grouped_tensorlistlist, indices).
    """
    # Result dict: (device, dtype) -> (list of lists, indices)
    result: dict[
        tuple[torch.device, torch.dtype], tuple[list[list[Any]], list[int]]
    ] = {}

    if not tensorlistlist or not tensorlistlist[0]:
        return result

    num_lists = len(tensorlistlist)
    num_tensors = len(tensorlistlist[0])

    for idx in range(num_tensors):
        # Find the first non-None tensor at this index to get device and dtype
        first_tensor = None
        for tlist in tensorlistlist:
            if tlist is not None and idx < len(tlist) and tlist[idx] is not None:
                first_tensor = tlist[idx]
                break

        if first_tensor is None:
            # All tensors at this index are None, skip
            continue

        key = (first_tensor.device, first_tensor.dtype)

        if key not in result:
            # Initialize empty lists for each tensorlist
            result[key] = ([[] for _ in range(num_lists)], [])

        grouped_lists, indices = result[key]

        # Add tensors from each list at this index
        for list_idx, tlist in enumerate(tensorlistlist):
            if tlist is not None and idx < len(tlist):
                grouped_lists[list_idx].append(tlist[idx])
            else:
                grouped_lists[list_idx].append(None)

        if with_indices:
            indices.append(idx)

    return result


# Partially copied from CPython test/support/import_helper.py
# https://github.com/python/cpython/blob/bb8791c0b75b5970d109e5557bfcca8a578a02af/Lib/test/support/import_helper.py
def _save_and_remove_modules(names: set[str]) -> dict[str, ModuleType]:
    orig_modules = {}
    prefixes = tuple(name + "." for name in names)
    for modname in list(py_sys.modules):
        if modname in names or modname.startswith(prefixes):
            orig_modules[modname] = py_sys.modules.pop(modname)
    return orig_modules


def import_fresh_module(name: str, blocked: list[str]) -> ModuleType:
    # Keep track of modules saved for later restoration as well
    # as those which just need a blocking entry removed
    names = {name, *blocked}
    orig_modules = _save_and_remove_modules(names)
    for modname in blocked:
        py_sys.modules[modname] = None  # type: ignore[assignment]

    try:
        return importlib.import_module(name)
    finally:
        _save_and_remove_modules(names)
        py_sys.modules.update(orig_modules)


def property_isabstractmethod(prop: property) -> bool:
    for accessor in (prop.fget, prop.fset, prop.fdel):
        if getattr(accessor, "__isabstractmethod__", False):
            return True
    return False
