rustpython_vm/builtins/

type.rs

use super::{
    PyClassMethod, PyDict, PyDictRef, PyList, PyStaticMethod, PyStr, PyStrInterned, PyStrRef,
    PyTupleRef, PyUtf8StrRef, PyWeak, mappingproxy::PyMappingProxy, object, union_,
};
use crate::{
    AsObject, Context, Py, PyAtomicRef, PyObject, PyObjectRef, PyPayload, PyRef, PyResult,
    TryFromObject, VirtualMachine,
    builtins::{
        PyBaseExceptionRef,
        descriptor::{
            MemberAccess, MemberKind, PyDescriptorOwned, PyMemberDef, PyMemberDescriptor,
            PyMemberFlags,
        },
        function::{PyCellRef, PyFunction},
        tuple::{IntoPyTuple, PyTuple},
    },
    class::{PyClassDef, PyClassImpl, StaticType},
    common::{
        borrow::BorrowedValue,
        lock::{PyRwLock, PyRwLockReadGuard},
    },
    function::{
        ArgumentError, FromArgs, FuncArgs, ItemDoc, KwArgs, Param, PyMethodDef, PySetterValue,
        db_doc,
    },
    object::{Traverse, TraverseFn},
    protocol::{PyIterReturn, PyNumberMethods},
    types::{
        AsNumber, Callable, Constructor, GetAttr, Initializer, NewFunc, PyTypeFlags, PyTypeSlots,
        Representable, SLOT_DEFS, SetAttr, TypeDataRef, TypeDataRefMut, TypeDataSlot, fn_addr,
        new_wrapper,
    },
};
use core::{
    any::Any,
    borrow::Borrow,
    cell::Cell,
    ops::Deref,
    pin::Pin,
    sync::atomic::{AtomicBool, AtomicPtr, AtomicU32, Ordering},
};
use indexmap::{IndexMap, map::Entry};
use itertools::Itertools;
use num_traits::ToPrimitive;
use rustpython_common::wtf8::Wtf8;
use std::collections::HashSet;

pub(crate) type PyTypeTupleRef = PyRef<PyTuple<PyTypeRef>>;

#[pyclass(module = false, name = "type", traverse = "manual")]
pub struct PyType {
    // tp_base. Written under the type lock (see `set_bases`); read lock-free.
    #[pymember(name = "__base__", doc = false)]
    pub base: PyAtomicRef<Option<Self>>,
    pub bases: PyRwLock<PyTypeTupleRef>,
    pub mro: PyRwLock<Vec<PyTypeRef>>,
    pub subclasses: PyRwLock<Vec<PyRef<PyWeak>>>,
    pub attributes: TypeNamespace,
    #[pymember(name = "__itemsize__", path = "itemsize")]
    #[pymember(name = "__basicsize__", path = "basicsize")]
    #[pymember(name = "__flags__", path = "flags")]
    pub slots: PyTypeSlots,
    pub heaptype_ext: Option<Pin<Box<HeapTypeExt>>>,
    /// Type version tag for inline caching. 0 means unassigned/invalidated.
    pub tp_version_tag: AtomicU32,
}

/// Monotonic counter for type version tags. Once it reaches `u32::MAX`,
/// version assignment returns 0 permanently, disabling new inline-cache
/// entries but not invalidating correctness (cache misses fall back to the
/// generic path).
static NEXT_TYPE_VERSION: AtomicU32 = AtomicU32::new(1);

const MANAGED_DICT_FLAGS: PyTypeFlags =
    PyTypeFlags::from_slice(&[PyTypeFlags::HAS_DICT, PyTypeFlags::MANAGED_DICT]);

const MANAGED_DICT_INLINE_FLAGS: PyTypeFlags = PyTypeFlags::from_slice(&[
    PyTypeFlags::HAS_DICT,
    PyTypeFlags::MANAGED_DICT,
    PyTypeFlags::INLINE_VALUES,
]);

const WEAKREF_FLAGS: PyTypeFlags =
    PyTypeFlags::from_slice(&[PyTypeFlags::HAS_WEAKREF, PyTypeFlags::MANAGED_WEAKREF]);

// Method cache (type_cache / MCACHE): direct-mapped cache keyed by
// (tp_version_tag, interned_name_ptr).
//
// Uses a lock-free SeqLock pattern for the read/write protocol:
//  - Readers validate sequence/version/name before and after the value read.
//  - Writers bracket updates with sequence odd/even transitions.
// No mutex needed on the hot path (cache hit).

const TYPE_CACHE_SIZE_EXP: u32 = 12;
const TYPE_CACHE_SIZE: usize = 1 << TYPE_CACHE_SIZE_EXP;
const TYPE_CACHE_MASK: usize = TYPE_CACHE_SIZE - 1;

struct TypeCacheEntry {
    /// Sequence lock (odd = write in progress, even = quiescent).
    sequence: AtomicU32,
    /// tp_version_tag at cache time. 0 = empty/invalid.
    version: AtomicU32,
    /// Interned attribute name pointer (pointer equality check).
    name: AtomicPtr<PyStrInterned>,
    /// Cached lookup result as raw pointer. null = empty.
    /// The cache holds a **borrowed** pointer (no refcount increment).
    /// Safety: `type_cache_clear()` nullifies all entries during GC,
    /// and `type_cache_clear_version()` nullifies entries when a type
    /// is modified — both before the source dict entry is removed.
    /// Types are always part of reference cycles (via `mro` self-reference)
    /// so they are always collected by the cyclic GC (never refcount-freed).
    value: AtomicPtr<PyObject>,
}

// SAFETY: TypeCacheEntry is thread-safe:
// - All fields use atomic operations
// - Value pointer is valid as long as version matches (SeqLock pattern)
// - PyObjectRef uses atomic reference counting
unsafe impl Send for TypeCacheEntry {}
unsafe impl Sync for TypeCacheEntry {}

impl TypeCacheEntry {
    fn new() -> Self {
        Self {
            sequence: AtomicU32::new(0),
            version: AtomicU32::new(0),
            name: AtomicPtr::new(core::ptr::null_mut()),
            value: AtomicPtr::new(core::ptr::null_mut()),
        }
    }

    #[inline]
    fn begin_write(&self) {
        let mut seq = self.sequence.load(Ordering::Acquire);
        loop {
            while (seq & 1) != 0 {
                core::hint::spin_loop();
                seq = self.sequence.load(Ordering::Acquire);
            }
            match self.sequence.compare_exchange_weak(
                seq,
                seq.wrapping_add(1),
                Ordering::AcqRel,
                Ordering::Acquire,
            ) {
                Ok(_) => {
                    core::sync::atomic::fence(Ordering::Release);
                    break;
                }
                Err(observed) => {
                    core::hint::spin_loop();
                    seq = observed;
                }
            }
        }
    }

    #[inline]
    fn end_write(&self) {
        self.sequence.fetch_add(1, Ordering::Release);
    }

    #[inline]
    fn begin_read(&self) -> u32 {
        let mut sequence = self.sequence.load(Ordering::Acquire);
        while (sequence & 1) != 0 {
            core::hint::spin_loop();
            sequence = self.sequence.load(Ordering::Acquire);
        }
        sequence
    }

    #[inline]
    fn end_read(&self, previous: u32) -> bool {
        core::sync::atomic::fence(Ordering::Acquire);
        self.sequence.load(Ordering::Relaxed) == previous
    }

    /// Null out the cached value pointer.
    /// Caller must ensure no concurrent reads can observe this entry
    /// (version should be set to 0 first).
    fn clear_value(&self) {
        self.value.store(core::ptr::null_mut(), Ordering::Relaxed);
    }
}

// std::sync::LazyLock is used here (not crate::common::lock::LazyLock)
// because TYPE_CACHE is a global shared across test threads. The common
// LazyLock delegates to LazyCell in non-threading mode, which is !Sync.
static TYPE_CACHE: std::sync::LazyLock<Box<[TypeCacheEntry]>> = std::sync::LazyLock::new(|| {
    (0..TYPE_CACHE_SIZE)
        .map(|_| TypeCacheEntry::new())
        .collect::<Vec<_>>()
        .into_boxed_slice()
});

/// When true, find_name_in_mro skips populating the cache.
/// Set during GC's type_cache_clear to prevent re-population from drops.
static TYPE_CACHE_CLEARING: AtomicBool = AtomicBool::new(false);

/// MCACHE_HASH: XOR of version and name pointer hash, masked to cache size.
#[inline]
fn type_cache_hash(version: u32, name: &'static PyStrInterned) -> usize {
    let name_hash = (name as *const PyStrInterned as usize >> 3) as u32;
    ((version ^ name_hash) as usize) & TYPE_CACHE_MASK
}

/// Invalidate cache entries for a specific version tag.
/// Called from modified() when a type is changed.
fn type_cache_clear_version(version: u32) {
    for entry in TYPE_CACHE.iter() {
        if entry.version.load(Ordering::Relaxed) == version {
            entry.begin_write();
            if entry.version.load(Ordering::Relaxed) == version {
                entry.version.store(0, Ordering::Release);
                entry.clear_value();
            }
            entry.end_write();
        }
    }
}

/// Clear all method cache entries (_PyType_ClearCache).
/// Called during GC collection to nullify borrowed pointers before
/// the collector breaks cycles.
///
/// Sets TYPE_CACHE_CLEARING to suppress cache re-population during the
/// entire operation, preventing concurrent lookups from repopulating
/// entries while we're clearing them.
pub(crate) fn type_cache_clear() {
    TYPE_CACHE_CLEARING.store(true, Ordering::Release);
    for entry in TYPE_CACHE.iter() {
        entry.begin_write();
        entry.version.store(0, Ordering::Release);
        entry.clear_value();
        entry.end_write();
    }
    TYPE_CACHE_CLEARING.store(false, Ordering::Release);
}

/// Repair type-cache SeqLock state in the post-fork child.
///
/// If fork happens while a writer holds an entry SeqLock, the child inherits
/// the odd sequence value with no surviving writer to release it. Clear only
/// those in-progress entries, matching `_PyTypes_AfterFork()`.
#[cfg(all(feature = "host_env", unix))]
pub(crate) unsafe fn type_cache_after_fork() {
    for entry in TYPE_CACHE.iter() {
        let seq = entry.sequence.load(Ordering::Relaxed);
        if (seq & 1) == 0 {
            continue;
        }
        entry.value.store(core::ptr::null_mut(), Ordering::Relaxed);
        entry.name.store(core::ptr::null_mut(), Ordering::Relaxed);
        entry.version.store(0, Ordering::Relaxed);
        entry.sequence.store(0, Ordering::Relaxed);
    }
}

unsafe impl crate::object::Traverse for PyType {
    fn traverse(&self, tracer_fn: &mut crate::object::TraverseFn<'_>) {
        if let Some(base) = self.base.deref() {
            tracer_fn(base.as_object());
        }
        // Skip when a writer holds `bases` (same rule as `Traverse for PyRwLock`).
        if let Some(bases) = self.bases.try_read_recursive() {
            tracer_fn(bases.as_untyped().as_object());
        }
        self.mro.traverse(tracer_fn);
        self.subclasses.traverse(tracer_fn);
        self.attributes.traverse(tracer_fn);
        if let Some(ext) = self.heaptype_ext.as_ref() {
            ext.specialization_cache.traverse(tracer_fn);
        }
    }

    /// type_clear: break reference cycles in type objects
    fn clear(&mut self, out: &mut Vec<crate::PyObjectRef>) {
        // SAFETY: tp_clear runs with exclusive access to the type object.
        if let Some(base) = unsafe { self.base.swap(None) } {
            out.push(base.into());
        }
        // Clone the empty tuple before taking the write lock: `object`'s
        // `bases` is this same lock, and `.read()` while exclusive panics
        // on CellRwLock (and hangs on parking_lot).
        let empty = object::PyBaseObject::static_type().bases.read().clone();
        if let Some(mut bases) = self.bases.try_write() {
            let old_bases = core::mem::replace(&mut *bases, empty);
            out.push(old_bases.into_untyped().into());
        }
        if let Some(mut guard) = self.mro.try_write() {
            for typ in guard.drain(..) {
                out.push(typ.into());
            }
        }
        if let Some(mut guard) = self.subclasses.try_write() {
            for weak in guard.drain(..) {
                out.push(weak.into());
            }
        }
        self.attributes.drain_into(out);
        if let Some(ext) = self.heaptype_ext.as_ref() {
            ext.specialization_cache.clear_into(out);
        }
    }
}

// PyHeapTypeObject in CPython
pub struct HeapTypeExt {
    pub name: PyRwLock<PyUtf8StrRef>,
    pub qualname: PyRwLock<PyStrRef>,
    pub slots: Option<PyRef<PyTuple<PyStrRef>>>,
    pub type_data: PyRwLock<Option<TypeDataSlot>>,
    pub specialization_cache: TypeSpecializationCache,
    /// The interpreter this type was created in, or `None` for the types the
    /// shared context builds before any interpreter exists.
    pub interpreter_id: Option<i64>,
}

impl HeapTypeExt {
    /// The interpreter a type created right now belongs to.
    fn creating_interpreter_id() -> Option<i64> {
        crate::vm::thread::try_with_current_vm(|vm| vm.state.interpreter_id)
    }
}

pub struct TypeSpecializationCache {
    pub init: PyAtomicRef<Option<PyFunction>>,
    pub init_version: AtomicU32,
    pub getitem: PyAtomicRef<Option<PyFunction>>,
    pub getitem_version: AtomicU32,
}

impl TypeSpecializationCache {
    fn new() -> Self {
        Self {
            init: PyAtomicRef::from(None::<PyRef<PyFunction>>),
            init_version: AtomicU32::new(0),
            getitem: PyAtomicRef::from(None::<PyRef<PyFunction>>),
            getitem_version: AtomicU32::new(0),
        }
    }

    #[inline]
    fn swap_init(&self, new_init: Option<PyRef<PyFunction>>) {
        if let Some(new) = &new_init {
            new.as_object().mark_cache_published();
        }
        // SAFETY: reclamation of published objects is deferred via QSBR;
        // racing load_owned readers never touch freed memory.
        let old = unsafe { self.init.swap(new_init) };
        if let Some(old) = old {
            // Dropping may run arbitrary Python; defer past the type lock.
            rustpython_common::refcount::try_defer_drop(move || drop(old));
        }
    }

    #[inline]
    fn swap_getitem(&self, new_getitem: Option<PyRef<PyFunction>>) {
        if let Some(new) = &new_getitem {
            new.as_object().mark_cache_published();
        }
        // SAFETY: as in swap_init.
        let old = unsafe { self.getitem.swap(new_getitem) };
        if let Some(old) = old {
            rustpython_common::refcount::try_defer_drop(move || drop(old));
        }
    }

    #[inline]
    fn invalidate_for_type_modified(&self) {
        self.swap_init(None);
        self.init_version.store(0, Ordering::Release);
        self.swap_getitem(None);
        self.getitem_version.store(0, Ordering::Release);
    }

    fn traverse(&self, tracer_fn: &mut TraverseFn<'_>) {
        if let Some(init) = self.init.deref() {
            tracer_fn(init.as_object());
        }
        if let Some(getitem) = self.getitem.deref() {
            tracer_fn(getitem.as_object());
        }
    }

    fn clear_into(&self, out: &mut Vec<PyObjectRef>) {
        let old_init = unsafe { self.init.swap(None) };
        if let Some(old_init) = old_init {
            out.push(old_init.into());
        }
        self.init_version.store(0, Ordering::Release);
        let old_getitem = unsafe { self.getitem.swap(None) };
        if let Some(old_getitem) = old_getitem {
            out.push(old_getitem.into());
        }
        self.getitem_version.store(0, Ordering::Release);
    }
}

pub type PyTypeRef = PyRef<PyType>;

cfg_select! {
    feature = "threading" => {
        unsafe impl Send for PyType {}
        unsafe impl Sync for PyType {}
    }
    _ => {}
}

/// For attributes we do not use a dict, but an IndexMap, which is an Hash Table
/// that maintains order and is compatible with the standard HashMap  This is probably
/// faster and only supports strings as keys.
pub(crate) type PyAttributes =
    IndexMap<&'static PyStrInterned, PyObjectRef, rapidhash::quality::RandomState>;

unsafe impl Traverse for PyAttributes {
    fn traverse(&self, tracer_fn: &mut TraverseFn<'_>) {
        self.values().for_each(|v| v.traverse(tracer_fn));
    }
}

/// A type's namespace, `tp_dict`.
///
/// Types created while an interpreter is running own a real dict, so the object
/// `__classdictcell__` hands to annotation scopes is the type's own storage.
/// The types `Context::genesis` builds cannot have one: hashing a string needs
/// a VM and none exists yet, so they keep an interned-key map instead.
pub enum TypeNamespace {
    Attributes(PyRwLock<PyAttributes>),
    Dict(PyDictRef),
}

unsafe impl Traverse for TypeNamespace {
    fn traverse(&self, tracer_fn: &mut TraverseFn<'_>) {
        match self {
            Self::Attributes(attrs) => {
                if let Some(attrs) = attrs.try_read_recursive() {
                    attrs.traverse(tracer_fn);
                }
            }
            Self::Dict(dict) => tracer_fn(dict.as_object()),
        }
    }
}

impl Default for TypeNamespace {
    fn default() -> Self {
        Self::Attributes(PyRwLock::default())
    }
}

impl From<PyAttributes> for TypeNamespace {
    fn from(attrs: PyAttributes) -> Self {
        Self::Attributes(PyRwLock::new(attrs))
    }
}

impl TypeNamespace {
    /// The namespace as a dict, for the types that have one.
    pub fn as_dict(&self) -> Option<&Py<PyDict>> {
        match self {
            Self::Attributes(_) => None,
            Self::Dict(dict) => Some(dict),
        }
    }

    /// Build a dict-backed namespace holding `attrs`, or fall back to an
    /// interned-key map when no VM is running to hash the keys with.
    fn new(attrs: PyAttributes, ctx: &Context) -> Self {
        let built = crate::vm::thread::try_with_current_vm(|vm| {
            let dict = ctx.new_dict();
            for (key, value) in &attrs {
                dict.set_item(*key, value.clone(), vm)?;
            }
            PyResult::Ok(dict)
        });
        match built {
            Some(Ok(dict)) => Self::Dict(dict),
            _ => attrs.into(),
        }
    }

    pub fn get(&self, name: &'static PyStrInterned) -> Option<PyObjectRef> {
        match self {
            Self::Attributes(attrs) => attrs.read().get(name).cloned(),
            Self::Dict(dict) => dict_get(dict, name),
        }
    }

    pub fn contains(&self, name: &'static PyStrInterned) -> bool {
        match self {
            Self::Attributes(attrs) => attrs.read().contains_key(name),
            Self::Dict(dict) => {
                match crate::vm::thread::try_with_current_vm(|vm| dict.contains_key(name, vm)) {
                    Some(found) => found,
                    None => dict_get(dict, name).is_some(),
                }
            }
        }
    }

    /// Bind `name` to `value`, dropping whatever it displaced.
    pub fn set(&self, name: &'static PyStrInterned, value: PyObjectRef) {
        drop(self.insert(name, value));
    }

    /// Bind `name` to `value` and hand back what it displaced, so the caller
    /// can decide where the old value is dropped.
    pub fn insert(&self, name: &'static PyStrInterned, value: PyObjectRef) -> Option<PyObjectRef> {
        match self {
            Self::Attributes(attrs) => attrs.write().insert(name, value),
            Self::Dict(dict) => {
                let previous = dict_get(dict, name);
                if let Some(Err(_)) | None =
                    crate::vm::thread::try_with_current_vm(|vm| dict.set_item(name, value, vm))
                {
                    debug_assert!(false, "type namespace write without a running VM");
                }
                previous
            }
        }
    }

    pub fn remove(&self, name: &'static PyStrInterned) -> Option<PyObjectRef> {
        match self {
            Self::Attributes(attrs) => attrs.write().shift_remove(name),
            Self::Dict(dict) => {
                let previous = dict_get(dict, name)?;
                crate::vm::thread::try_with_current_vm(|vm| dict.del_item(name, vm).ok());
                Some(previous)
            }
        }
    }

    /// The namespace contents in insertion order.
    pub fn entries(&self) -> Vec<(PyObjectRef, PyObjectRef)> {
        match self {
            Self::Attributes(attrs) => attrs
                .read()
                .iter()
                .map(|(name, value)| ((*name).to_object(), value.clone()))
                .collect(),
            Self::Dict(dict) => dict.into_iter().collect(),
        }
    }

    /// The namespace keyed by interned name; dict keys that are not strings
    /// are left out, since `PyAttributes` has nowhere to put them.
    pub fn attributes(&self, ctx: &Context) -> PyAttributes {
        match self {
            Self::Attributes(attrs) => attrs.read().clone(),
            Self::Dict(dict) => dict
                .into_iter()
                .filter_map(|(key, value)| {
                    let key = key.downcast_ref::<PyStr>()?;
                    Some((ctx.intern_str(key.as_wtf8()), value))
                })
                .collect(),
        }
    }

    /// The interned names in the namespace; dict keys that are not strings are
    /// left out.
    pub fn interned_names(&self, ctx: &Context) -> Vec<&'static PyStrInterned> {
        match self {
            Self::Attributes(attrs) => attrs.read().keys().copied().collect(),
            Self::Dict(dict) => dict
                .into_iter()
                .filter_map(|(key, _)| {
                    let key = key.downcast_ref::<PyStr>()?;
                    Some(ctx.intern_str(key.as_wtf8()))
                })
                .collect(),
        }
    }

    /// Empty the namespace, handing the values to the caller. Used by tp_clear.
    fn drain_into(&mut self, out: &mut Vec<PyObjectRef>) {
        match self {
            Self::Attributes(attrs) => {
                if let Some(mut guard) = attrs.try_write() {
                    out.extend(guard.drain(..).map(|(_, value)| value));
                }
            }
            Self::Dict(dict) => {
                out.extend((&**dict).into_iter().map(|(_, value)| value));
                Py::<PyDict>::clear(dict);
            }
        }
    }
}

/// Look a name up in a dict-backed namespace. Falls back to a scan when no VM
/// is running, since hashing the key needs one.
fn dict_get(dict: &Py<PyDict>, name: &'static PyStrInterned) -> Option<PyObjectRef> {
    match crate::vm::thread::try_with_current_vm(|vm| dict.get_item_opt(name, vm)) {
        Some(found) => found.ok().flatten(),
        None => dict
            .into_iter()
            .find(|(key, _)| {
                key.downcast_ref::<PyStr>()
                    .is_some_and(|key| key.as_wtf8() == name.as_wtf8())
            })
            .map(|(_, value)| value),
    }
}

impl core::fmt::Display for PyType {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        core::fmt::Display::fmt(&self.name(), f)
    }
}

impl core::fmt::Debug for PyType {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        write!(f, "[PyType {}]", self.name())
    }
}

impl PyPayload for PyType {
    #[inline]
    fn class(ctx: &Context) -> &'static Py<PyType> {
        ctx.types.type_type
    }
}

/// The name a class is built under, which the namespace it is built from may
/// carry and which is faulted for not being a string. = type_new_set_attrs
fn downcast_qualname(value: PyObjectRef, vm: &VirtualMachine) -> PyResult<PyRef<PyStr>> {
    match value.downcast::<PyStr>() {
        Ok(value) => Ok(value),
        Err(value) => Err(vm.new_type_error(format!(
            "type __qualname__ must be a str, not {}",
            value.class().name()
        ))),
    }
}

fn is_subtype_with_mro(a_mro: &[PyTypeRef], a: &Py<PyType>, b: &Py<PyType>) -> bool {
    if a_mro.is_empty() {
        let mut current = Some(a);
        while let Some(typ) = current {
            if typ.is(b) {
                return true;
            }
            current = typ.base.deref();
        }
        return false;
    }
    a_mro.iter().any(|item| item.is(b))
}

impl PyType {
    #[inline]
    fn with_type_lock<R>(vm: &VirtualMachine, f: impl FnOnce() -> R) -> R {
        // Drops deferred via try_defer_drop inside the critical section run
        // after the guard is released, outside the lock.
        //
        // The lock is reentrant on the same thread so a custom mro() can
        // assign __bases__ (and re-enter here) without deadlocking.
        thread_local! {
            static HELD: Cell<bool> = const { Cell::new(false) };
        }
        rustpython_common::refcount::with_deferred_drops(|| {
            HELD.with(|held| {
                if held.get() {
                    f()
                } else {
                    let _guard = vm.state.type_mutex.lock();
                    held.set(true);
                    let result = f();
                    held.set(false);
                    result
                }
            })
        })
    }

    /// Assign a fresh version tag. Returns 0 if the version counter has been
    /// exhausted, in which case no new cache entries can be created.
    fn assign_version_tag_inner(&self) -> u32 {
        let v = self.tp_version_tag.load(Ordering::Acquire);
        if v != 0 {
            return v;
        }

        // Assign versions to all direct bases first (MRO invariant).
        for base in self.bases.read().as_slice() {
            if base.assign_version_tag_inner() == 0 {
                return 0;
            }
        }

        loop {
            let current = NEXT_TYPE_VERSION.load(Ordering::Relaxed);
            let Some(next) = current.checked_add(1) else {
                return 0; // Overflow: version space exhausted
            };
            if NEXT_TYPE_VERSION
                .compare_exchange_weak(current, next, Ordering::Relaxed, Ordering::Relaxed)
                .is_ok()
            {
                self.tp_version_tag.store(current, Ordering::Release);
                return current;
            }
        }
    }

    pub(crate) fn version_for_specialization(&self, vm: &VirtualMachine) -> u32 {
        let version = self.tp_version_tag.load(Ordering::Acquire);
        if version != 0 {
            return version;
        }
        Self::with_type_lock(vm, || {
            let version = self.tp_version_tag.load(Ordering::Acquire);
            if version == 0 {
                self.assign_version_tag_inner()
            } else {
                version
            }
        })
    }

    /// Invalidate this type's version tag and cascade to all subclasses.
    fn modified_inner(&self) {
        let old_version = self.tp_version_tag.load(Ordering::Acquire);
        if old_version == 0 {
            return;
        }
        let subclasses = self.subclasses.read();
        for weak_ref in subclasses.iter() {
            if let Some(sub) = weak_ref.upgrade() {
                sub.downcast_ref::<Self>().unwrap().modified_inner();
            }
        }
        self.tp_version_tag.store(0, Ordering::SeqCst);
        // Nullify borrowed pointers in cache entries for this version
        // so they don't dangle after the dict is modified.
        type_cache_clear_version(old_version);
        if let Some(ext) = self.heaptype_ext.as_ref() {
            ext.specialization_cache.invalidate_for_type_modified();
        }
    }

    /// Store a specific `tp_version_tag` without going through assignment.
    pub(crate) fn assign_specific_version(&self, version: u32) {
        self.tp_version_tag.store(version, Ordering::Release);
    }

    pub fn modified(&self) {
        if self.tp_version_tag.load(Ordering::Acquire) == 0 {
            return;
        }
        if let Some(()) = crate::vm::thread::try_with_current_vm(|vm| {
            Self::with_type_lock(vm, || self.modified_inner());
        }) {
            return;
        }
        self.modified_inner();
    }

    /// Whether the interpreter with `interpreter_id` can see this type.
    ///
    /// Interpreters share the context, so a subclass of a shared type is
    /// recorded on an object every interpreter reaches. Only the interpreter
    /// that created it can name it, so only that one lists it.
    pub fn is_visible_to_interpreter(&self, interpreter_id: i64) -> bool {
        match self
            .heaptype_ext
            .as_ref()
            .and_then(|ext| ext.interpreter_id)
        {
            Some(owner) => owner == interpreter_id,
            None => true,
        }
    }

    pub fn new_simple_heap(
        name: &str,
        base: &Py<Self>,
        ctx: &Context,
    ) -> Result<PyRef<Self>, String> {
        Self::new_heap(
            name,
            vec![base.to_owned()],
            Default::default(),
            Default::default(),
            Self::static_type().to_owned(),
            ctx,
        )
    }
    pub fn new_heap(
        name: &str,
        bases: Vec<PyRef<Self>>,
        attrs: PyAttributes,
        slots: PyTypeSlots,
        metaclass: PyRef<Self>,
        ctx: &Context,
    ) -> Result<PyRef<Self>, String> {
        // TODO: ensure clean slot name
        // assert_eq!(slots.name.borrow(), "");

        // Set HEAPTYPE flag for heap-allocated types
        slots.flags.insert(PyTypeFlags::HEAPTYPE);

        let name_utf8 = ctx.new_utf8_str(name);
        let name = name_utf8.clone().into_wtf8();
        let heaptype_ext = HeapTypeExt {
            name: PyRwLock::new(name_utf8),
            qualname: PyRwLock::new(name),
            slots: None,
            type_data: PyRwLock::new(None),
            specialization_cache: TypeSpecializationCache::new(),
            interpreter_id: HeapTypeExt::creating_interpreter_id(),
        };
        let bases = PyTuple::new_ref_typed(bases, ctx);
        let base = bases.as_slice()[0].clone();

        Self::new_heap_inner(
            base,
            bases,
            attrs,
            slots,
            heaptype_ext,
            metaclass,
            ctx,
            false,
        )
    }

    /// Equivalent to CPython's PyType_Check macro
    /// Checks if obj is an instance of type (or its subclass)
    pub(crate) fn check(obj: &PyObject) -> Option<&Py<Self>> {
        obj.downcast_ref::<Self>()
    }

    fn resolve_mro(bases: &[PyRef<Self>]) -> Result<Vec<PyTypeRef>, String> {
        // Check for duplicates in bases.
        let mut unique_bases = HashSet::new();
        for base in bases {
            if !unique_bases.insert(base.get_id()) {
                return Err(format!("duplicate base class {}", base.name()));
            }
        }

        let mros = bases
            .iter()
            .map(|base| base.mro_map_collect(|t| t.to_owned()))
            .collect();
        linearise_mro(mros)
    }

    /// Inherit SEQUENCE and MAPPING flags from base classes
    /// Check all bases in order and inherit the first SEQUENCE or MAPPING flag found
    fn inherit_patma_flags(slots: &mut PyTypeSlots, bases: &[PyRef<Self>]) {
        // If flags are already set, don't override
        if !slots.flags.load().is_disjoint(&PyTypeFlags::COLLECTION) {
            return;
        }

        // Check each base in order and inherit the first collection flag found
        for base in bases {
            let base_flags = base.slots.flags.load() & PyTypeFlags::COLLECTION;
            if !base_flags.is_empty() {
                slots.flags |= base_flags;
                return;
            }
        }
    }

    pub fn has_patma_collection_flag(&self, flag: u8) -> bool {
        debug_assert!(flag == PyTypeFlags::SEQUENCE || flag == PyTypeFlags::MAPPING);
        self.slots.flags.has_feature(flag)
    }

    pub fn set_is_abstract(&self, is_abstract: bool) {
        if is_abstract {
            self.slots.flags.insert(PyTypeFlags::IS_ABSTRACT);
        } else {
            self.slots.flags.remove(PyTypeFlags::IS_ABSTRACT);
        }
        self.modified();
    }

    pub fn set_abc_collection_flags_recursive(&self, flags: PyTypeFlags) {
        let flags = flags & PyTypeFlags::COLLECTION;
        if flags.is_empty() {
            return;
        }
        self.slots
            .flags
            .replace_masked(PyTypeFlags::COLLECTION, flags);
        self.modified();
        for weak_ref in self.subclasses.read().iter() {
            if let Some(subclass) = weak_ref.upgrade()
                && let Some(subclass) = subclass.downcast_ref::<Self>()
            {
                subclass.set_abc_collection_flags_recursive(flags);
            }
        }
    }

    /// Check for __abc_tpflags__ and set the appropriate flags
    /// This checks in attrs and all base classes for __abc_tpflags__
    fn check_abc_tpflags(
        slots: &mut PyTypeSlots,
        attrs: &PyAttributes,
        bases: &[PyRef<Self>],
        ctx: &Context,
    ) -> Result<(), String> {
        // Always validate this class's own __abc_tpflags__ even when slot
        // flags were already inherited, otherwise a child setting both
        // Py_TPFLAGS_SEQUENCE and Py_TPFLAGS_MAPPING would slip through.
        let abc_tpflags_name = ctx.intern_str("__abc_tpflags__");
        if let Some(abc_tpflags_obj) = attrs.get(abc_tpflags_name)
            && let Some(int_obj) = abc_tpflags_obj.downcast_ref::<crate::builtins::int::PyInt>()
        {
            let flags_val = int_obj.as_bigint().to_i64().unwrap_or(0);
            let abc_flags = PyTypeFlags::from_bits_truncate(flags_val as u64);
            let masked = abc_flags & PyTypeFlags::COLLECTION;
            if masked == PyTypeFlags::COLLECTION {
                return Err(
                    "__abc_tpflags__ cannot be both Py_TPFLAGS_SEQUENCE and Py_TPFLAGS_MAPPING"
                        .to_owned(),
                );
            }
            slots.flags.remove_masked(PyTypeFlags::COLLECTION);
            slots.flags |= masked;
            return Ok(());
        }

        // No __abc_tpflags__ on this class. Inheritance already happened in
        // inherit_patma_flags, using base order and including ABC markers.
        if !slots.flags.load().is_disjoint(&PyTypeFlags::COLLECTION) {
            return Ok(());
        }

        // Then check in base classes for legacy paths that bypassed
        // inherit_patma_flags.
        for base in bases {
            if let Some(abc_tpflags_obj) = base.find_name_in_mro(abc_tpflags_name)
                && let Some(int_obj) = abc_tpflags_obj.downcast_ref::<crate::builtins::int::PyInt>()
            {
                let flags_val = int_obj.as_bigint().to_i64().unwrap_or(0);
                let abc_flags = PyTypeFlags::from_bits_truncate(flags_val as u64);
                let masked = abc_flags & PyTypeFlags::COLLECTION;
                if masked == PyTypeFlags::COLLECTION {
                    return Err(
                        "__abc_tpflags__ cannot be both Py_TPFLAGS_SEQUENCE and Py_TPFLAGS_MAPPING"
                            .to_owned(),
                    );
                }
                slots.flags.remove_masked(PyTypeFlags::COLLECTION);
                slots.flags |= masked;
                return Ok(());
            }
        }
        Ok(())
    }

    #[allow(clippy::too_many_arguments)]
    fn new_heap_inner(
        base: PyRef<Self>,
        bases: PyTypeTupleRef,
        attrs: PyAttributes,
        mut slots: PyTypeSlots,
        heaptype_ext: HeapTypeExt,
        metaclass: PyRef<Self>,
        ctx: &Context,
        defer_mro: bool,
    ) -> Result<PyRef<Self>, String> {
        let mro = if defer_mro {
            // Leave tp_mro unset so a custom metaclass mro() sees __mro__ is None.
            Vec::new()
        } else {
            Self::resolve_mro(bases.as_slice())?
        };

        // Layout flags come from each direct base's own flags. A custom
        // mro() can omit a physical base from the stored MRO.
        if bases
            .as_slice()
            .iter()
            .any(|b| b.slots.flags.has_feature(PyTypeFlags::HAS_DICT))
        {
            slots.flags.insert(PyTypeFlags::HAS_DICT);
        }
        if bases
            .as_slice()
            .iter()
            .any(|b| b.slots.flags.has_feature(PyTypeFlags::MANAGED_DICT))
        {
            slots.flags.insert(PyTypeFlags::MANAGED_DICT);
        }

        if bases
            .as_slice()
            .iter()
            .any(|b| b.slots.flags.has_feature(PyTypeFlags::HAS_WEAKREF))
        {
            slots.flags |= WEAKREF_FLAGS;
        }

        // Inherit SEQUENCE and MAPPING flags from base classes
        Self::inherit_patma_flags(&mut slots, bases.as_slice());

        // Check for __abc_tpflags__ from ABCMeta (for collections.abc.Sequence, Mapping, etc.)
        Self::check_abc_tpflags(&mut slots, &attrs, bases.as_slice(), ctx)?;

        if slots.basicsize == 0 {
            slots.basicsize = base.slots.basicsize;
        }

        // Normalize: any type with HAS_WEAKREF gets MANAGED_WEAKREF
        if slots.flags.has_feature(PyTypeFlags::HAS_WEAKREF) {
            slots.flags.insert(PyTypeFlags::MANAGED_WEAKREF);
        }

        if let Some(qualname) = attrs.get(identifier!(ctx, __qualname__))
            && !qualname.fast_isinstance(ctx.types.str_type)
        {
            return Err(format!(
                "type __qualname__ must be a str, not {}",
                qualname.class().name()
            ));
        }

        let new_type = PyRef::new_ref(
            Self {
                base: Some(base).into(),
                bases: PyRwLock::new(bases),
                mro: PyRwLock::new(mro),
                subclasses: PyRwLock::default(),
                attributes: TypeNamespace::new(attrs, ctx),
                slots,
                heaptype_ext: Some(Pin::new(Box::new(heaptype_ext))),
                tp_version_tag: AtomicU32::new(0),
            },
            metaclass,
            None,
        );
        if !defer_mro {
            new_type.mro.write().insert(0, new_type.clone());
            new_type.init_slots(ctx);
        }

        let weakref_type = super::PyWeak::static_type();
        for base in new_type.bases.read().as_slice() {
            base.subclasses.write().push(
                new_type
                    .as_object()
                    .downgrade_with_weakref_typ_opt(None, weakref_type.to_owned())
                    .unwrap(),
            );
        }

        Ok(new_type)
    }

    pub fn new_static(
        base: PyRef<Self>,
        attrs: PyAttributes,
        mut slots: PyTypeSlots,
        metaclass: PyRef<Self>,
    ) -> Result<PyRef<Self>, String> {
        if base.slots.flags.has_feature(PyTypeFlags::HAS_DICT) {
            slots.flags.insert(PyTypeFlags::HAS_DICT);
        }
        if base.slots.flags.has_feature(PyTypeFlags::HAS_WEAKREF) {
            slots.flags |= WEAKREF_FLAGS;
        }

        // Inherit SEQUENCE and MAPPING flags from base class
        // For static types, we only have a single base
        Self::inherit_patma_flags(&mut slots, core::slice::from_ref(&base));

        if slots.basicsize == 0 {
            slots.basicsize = base.slots.basicsize;
        }

        // Normalize: any type with HAS_WEAKREF gets MANAGED_WEAKREF
        if slots.flags.has_feature(PyTypeFlags::HAS_WEAKREF) {
            slots.flags.insert(PyTypeFlags::MANAGED_WEAKREF);
        }

        let bases =
            PyTuple::new_ref_typed_with_type(vec![base.clone()], PyTuple::static_type().to_owned());
        let mro = base.mro_map_collect(|x| x.to_owned());

        let new_type = PyRef::new_ref(
            Self {
                base: Some(base).into(),
                bases: PyRwLock::new(bases),
                mro: PyRwLock::new(mro),
                subclasses: PyRwLock::default(),
                attributes: attrs.into(),
                slots,
                heaptype_ext: None,
                tp_version_tag: AtomicU32::new(0),
            },
            metaclass,
            None,
        );

        // Static types are not tracked by GC.
        // They are immortal and never participate in collectable cycles.
        // Heap types from PyType_FromSpec stay tracked.
        if !new_type.slots.flags.has_feature(PyTypeFlags::HEAPTYPE) {
            unsafe {
                crate::gc_state::gc_state()
                    .untrack_object(core::ptr::NonNull::from(new_type.as_object()));
            }
            new_type.as_object().clear_gc_tracked();
        }

        new_type.mro.write().insert(0, new_type.clone());

        // Note: inherit_slots is called in PyClassImpl::init_class after
        // slots are fully initialized by make_slots()

        Self::set_new(&new_type.slots, new_type.base.deref());
        Self::set_alloc(&new_type.slots, new_type.base.deref());

        let weakref_type = super::PyWeak::static_type();
        for base in new_type.bases.read().as_slice() {
            base.subclasses.write().push(
                new_type
                    .as_object()
                    .downgrade_with_weakref_typ_opt(None, weakref_type.to_owned())
                    .unwrap(),
            );
        }

        Ok(new_type)
    }

    pub(crate) fn init_slots(&self, ctx: &Context) {
        // Inherit slots from MRO (mro[0] is self, so skip it)
        let mro_guard = self.mro.read();
        if mro_guard.is_empty() {
            return;
        }
        let mro: Vec<_> = mro_guard[1..].to_vec();
        drop(mro_guard);
        for base in &mro {
            self.inherit_slots(base);
        }

        // Wire dunder methods to slots
        #[allow(clippy::mutable_key_type)]
        let mut slot_name_set = std::collections::HashSet::new();

        // mro[0] is self, so skip it; self.attributes is checked separately below
        for cls in &self.mro.read()[1..] {
            for name in cls.attributes.interned_names(ctx) {
                if name.as_bytes().starts_with(b"__") && name.as_bytes().ends_with(b"__") {
                    slot_name_set.insert(name);
                }
            }
        }
        for name in self.attributes.interned_names(ctx) {
            if name.as_bytes().starts_with(b"__") && name.as_bytes().ends_with(b"__") {
                slot_name_set.insert(name);
            }
        }
        // Sort for deterministic iteration order (important for slot processing)
        let mut slot_names: Vec<_> = slot_name_set.into_iter().collect();
        slot_names.sort_by_key(|name| name.as_str());
        for attr_name in slot_names {
            self.update_slot::<true>(attr_name, ctx);
        }

        Self::set_new(&self.slots, self.base.deref());
        Self::set_alloc(&self.slots, self.base.deref());
    }

    /// Recompute every slot for this type and all its descendants. update_all_slots
    ///
    /// Unlike `init_slots`, which is additive and driven only by the dunder names
    /// present in the current MRO, this iterates the full `SLOT_DEFS` name table so
    /// a slot whose method left the MRO is reset instead of left stale. Must be
    /// called under the type lock after MROs have been recomputed.
    pub(crate) fn update_all_slots(&self, ctx: &Context) {
        // Invalidate version tags first; cascades to subclasses.
        self.modified_inner();
        // Distinct names only; update_slot fans out to every SLOT_DEFS entry
        // sharing the name and recurses into subclasses on its own.
        let mut seen = std::collections::HashSet::new();
        for def in SLOT_DEFS {
            if seen.insert(def.name) {
                let name = ctx.intern_str(def.name);
                self.update_slot::<true>(name, ctx);
            }
        }
    }

    fn set_new(slots: &PyTypeSlots, base: Option<&Py<Self>>) {
        if slots.flags.has_feature(PyTypeFlags::DISALLOW_INSTANTIATION) {
            slots.new.store(None)
        } else if slots.new.load().is_none() {
            slots.new.store(base.and_then(|base| base.slots.new.load()))
        }
    }

    fn set_alloc(slots: &PyTypeSlots, base: Option<&Py<Self>>) {
        if slots.alloc.load().is_none() {
            slots
                .alloc
                .store(base.and_then(|base| base.slots.alloc.load()));
        }
    }

    pub(crate) fn finalize_bootstrap_static(typ: &Py<Self>) {
        Self::set_new(&typ.slots, typ.base.deref());
        Self::set_alloc(&typ.slots, typ.base.deref());
    }

    /// Inherit slots from base type. inherit_slots
    pub(crate) fn inherit_slots(&self, base: &Self) {
        // Use SLOT_DEFS to iterate all slots
        for def in SLOT_DEFS {
            def.accessor.copyslot_if_none(self, base);
        }
    }

    // This is used for class initialization where the vm is not yet available.
    pub fn set_str_attr<V: Into<PyObjectRef>>(
        &self,
        attr_name: &str,
        value: V,
        ctx: impl AsRef<Context>,
    ) {
        let ctx = ctx.as_ref();
        let attr_name = ctx.intern_str(attr_name);
        self.set_attr(attr_name, value.into())
    }

    pub fn set_attr(&self, attr_name: &'static PyStrInterned, value: PyObjectRef) {
        // Invalidate caches BEFORE modifying attributes so that borrowed
        // pointers in cache entries are nullified while the source objects
        // are still alive.
        self.modified();
        self.attributes.set(attr_name, value);
    }

    /// Internal get_attr implementation for fast lookup on a class.
    /// Searches the full MRO (including self) with method cache acceleration.
    pub fn get_attr(&self, attr_name: &'static PyStrInterned) -> Option<PyObjectRef> {
        self.find_name_in_mro(attr_name)
    }

    /// `_PyType_LookupRefAndVersion` equivalent for interned names.
    /// Returns the observed lookup result and the type version used for the lookup.
    ///
    /// Uses a lock-free SeqLock-style pattern:
    ///   Read:  load sequence/version/name → load value + try_to_owned →
    ///          validate value pointer + sequence
    ///   Write: sequence(begin) → version=0 → swap value/name → version=assigned → sequence(end)
    pub(crate) fn lookup_ref_and_version_interned(
        &self,
        name: &'static PyStrInterned,
        vm: &VirtualMachine,
    ) -> (Option<PyObjectRef>, u32) {
        #[cfg(all(feature = "threading", debug_assertions))]
        crate::vm::thread::debug_assert_current_thread_attached();

        let version = self.tp_version_tag.load(Ordering::Acquire);
        if version != 0 {
            let idx = type_cache_hash(version, name);
            let entry = &TYPE_CACHE[idx];
            let name_ptr = name as *const _ as *mut _;
            loop {
                let seq1 = entry.begin_read();
                let entry_version = entry.version.load(Ordering::Acquire);
                let type_version = self.tp_version_tag.load(Ordering::Acquire);
                if entry_version != type_version
                    || !core::ptr::eq(entry.name.load(Ordering::Relaxed), name_ptr)
                {
                    break;
                }
                let ptr = entry.value.load(Ordering::Acquire);
                if ptr.is_null() {
                    if entry.end_read(seq1) {
                        return (None, entry_version);
                    }
                    continue;
                }
                if let Some(cloned) = unsafe { PyObject::try_to_owned_from_ptr(ptr) } {
                    let same_ptr = core::ptr::eq(entry.value.load(Ordering::Relaxed), ptr);
                    if same_ptr && entry.end_read(seq1) {
                        return (Some(cloned), entry_version);
                    }
                    drop(cloned);
                    continue;
                }
                break;
            }
        }

        Self::with_type_lock(vm, || {
            let assigned = if self.tp_version_tag.load(Ordering::Acquire) == 0 {
                self.assign_version_tag_inner()
            } else {
                self.tp_version_tag.load(Ordering::Acquire)
            };
            let result = self.find_name_in_mro_uncached(name);
            if assigned != 0
                && !TYPE_CACHE_CLEARING.load(Ordering::Acquire)
                && self.tp_version_tag.load(Ordering::Acquire) == assigned
            {
                let idx = type_cache_hash(assigned, name);
                let entry = &TYPE_CACHE[idx];
                let name_ptr = name as *const _ as *mut _;
                entry.begin_write();
                entry.version.store(0, Ordering::Release);
                let new_ptr = result.as_ref().map_or(core::ptr::null_mut(), |found| {
                    // Defer memory reclamation of cached values via QSBR so
                    // racing readers never try-incref freed memory.
                    found.mark_cache_published();
                    &**found as *const PyObject as *mut _
                });
                entry.value.store(new_ptr, Ordering::Relaxed);
                entry.name.store(name_ptr, Ordering::Relaxed);
                entry.version.store(assigned, Ordering::Release);
                entry.end_write();
            }
            (result, assigned)
        })
    }

    /// Cache __init__ for CALL_ALLOC_AND_ENTER_INIT specialization.
    /// The cache is valid only when guarded by the type version check.
    pub(crate) fn cache_init_for_specialization(
        &self,
        init: PyRef<PyFunction>,
        tp_version: u32,
        vm: &VirtualMachine,
    ) -> bool {
        let Some(ext) = self.heaptype_ext.as_ref() else {
            return false;
        };
        if tp_version == 0 {
            return false;
        }
        Self::with_type_lock(vm, || {
            if self.tp_version_tag.load(Ordering::Acquire) != tp_version {
                return false;
            }
            let func_version = init.get_version_for_current_state();
            if func_version == 0 {
                return false;
            }
            ext.specialization_cache.swap_init(Some(init));
            ext.specialization_cache
                .init_version
                .store(func_version, Ordering::Release);
            true
        })
    }

    /// Read cached __init__ for CALL_ALLOC_AND_ENTER_INIT specialization.
    pub(crate) fn get_cached_init_for_specialization(
        &self,
        tp_version: u32,
    ) -> Option<(PyRef<PyFunction>, u32)> {
        let ext = self.heaptype_ext.as_ref()?;
        if tp_version == 0 {
            return None;
        }
        if self.tp_version_tag.load(Ordering::Acquire) != tp_version {
            return None;
        }
        // Check order: pointer (Acquire) then function version.
        let init = ext.specialization_cache.init.load_owned()?;
        let cached_version = ext
            .specialization_cache
            .init_version
            .load(Ordering::Acquire);
        if cached_version == 0 {
            return None;
        }
        Some((init, cached_version))
    }

    /// Cache __getitem__ for BINARY_OP_SUBSCR_GETITEM specialization.
    /// The cache is valid only when guarded by the type version check.
    pub(crate) fn cache_getitem_for_specialization(
        &self,
        getitem: PyRef<PyFunction>,
        tp_version: u32,
        vm: &VirtualMachine,
    ) -> bool {
        let Some(ext) = self.heaptype_ext.as_ref() else {
            return false;
        };
        if tp_version == 0 {
            return false;
        }
        Self::with_type_lock(vm, || {
            if self.tp_version_tag.load(Ordering::Acquire) != tp_version {
                return false;
            }
            let func_version = getitem.get_version_for_current_state();
            if func_version == 0 {
                return false;
            }
            ext.specialization_cache.swap_getitem(Some(getitem));
            ext.specialization_cache
                .getitem_version
                .store(func_version, Ordering::Release);
            true
        })
    }

    /// Read cached __getitem__ for BINARY_OP_SUBSCR_GETITEM specialization.
    pub(crate) fn get_cached_getitem_for_specialization(&self) -> Option<(PyRef<PyFunction>, u32)> {
        let ext = self.heaptype_ext.as_ref()?;
        // Check order: pointer (Acquire) then function version.
        let getitem = ext.specialization_cache.getitem.load_owned()?;
        let cached_version = ext
            .specialization_cache
            .getitem_version
            .load(Ordering::Acquire);
        if cached_version == 0 {
            return None;
        }
        Some((getitem, cached_version))
    }

    pub fn get_direct_attr(&self, attr_name: &'static PyStrInterned) -> Option<PyObjectRef> {
        self.attributes.get(attr_name)
    }

    /// find_name_in_mro with method cache (MCACHE).
    /// Looks in tp_dict of types in MRO, bypasses descriptors.
    fn find_name_in_mro(&self, name: &'static PyStrInterned) -> Option<PyObjectRef> {
        crate::vm::thread::try_with_current_vm(|vm| {
            self.lookup_ref_and_version_interned(name, vm).0
        })
        // No current VM: this thread is not registered for QSBR, so the
        // lock-free cache read protocol is not sound here. Walk the MRO
        // under the attributes locks instead (the dicts hold strong refs).
        .unwrap_or_else(|| self.find_name_in_mro_uncached(name))
    }

    /// Raw MRO walk without cache.
    fn find_name_in_mro_uncached(&self, name: &'static PyStrInterned) -> Option<PyObjectRef> {
        // Keep a strong snapshot of the MRO because tp_mro can be replaced
        // during dict lookup, e.g. when comparing to non-string keys.
        let mro: Vec<PyTypeRef> = self.mro.read().iter().cloned().collect();
        for cls in &mro {
            if let Some(value) = cls.attributes.get(name) {
                return Some(value);
            }
        }
        None
    }

    /// _PyType_LookupRef: look up a name through the MRO without setting an exception.
    pub fn lookup_ref(&self, name: &Py<PyStr>, vm: &VirtualMachine) -> Option<PyObjectRef> {
        let interned_name = vm.ctx.interned_str(name)?;
        self.lookup_ref_and_version_interned(interned_name, vm).0
    }

    pub fn get_super_attr(&self, attr_name: &'static PyStrInterned) -> Option<PyObjectRef> {
        let mro = self.mro.read();
        mro.get(1..)?
            .iter()
            .find_map(|class| class.attributes.get(attr_name))
    }

    /// Fast lookup for attribute existence on a class.
    pub fn has_attr(&self, attr_name: &'static PyStrInterned) -> bool {
        self.has_name_in_mro(attr_name)
    }

    /// Check if attribute exists in MRO, using method cache for fast check.
    /// Unlike find_name_in_mro, avoids cloning the value on cache hit.
    fn has_name_in_mro(&self, name: &'static PyStrInterned) -> bool {
        #[cfg(all(feature = "threading", debug_assertions))]
        crate::vm::thread::debug_assert_current_thread_attached();

        let version = self.tp_version_tag.load(Ordering::Acquire);
        if version != 0 {
            let idx = type_cache_hash(version, name);
            let entry = &TYPE_CACHE[idx];
            let name_ptr = name as *const _ as *mut _;
            loop {
                let seq1 = entry.begin_read();
                let v1 = entry.version.load(Ordering::Acquire);
                let type_version = self.tp_version_tag.load(Ordering::Acquire);
                if v1 != type_version
                    || !core::ptr::eq(entry.name.load(Ordering::Relaxed), name_ptr)
                {
                    break;
                }
                let ptr = entry.value.load(Ordering::Acquire);
                if entry.end_read(seq1) {
                    if !ptr.is_null() {
                        return true;
                    }
                    break;
                }
                continue;
            }
        }

        // Cache miss — use find_name_in_mro which populates cache
        self.find_name_in_mro(name).is_some()
    }

    pub fn get_attributes(&self, ctx: &Context) -> PyAttributes {
        // Gather all members here:
        let mut attributes = PyAttributes::default();

        // mro[0] is self, so we iterate through the entire MRO in reverse
        for bc in self.mro.read().iter().map(|cls| -> &Self { cls }).rev() {
            attributes.extend(bc.attributes.attributes(ctx));
        }

        attributes
    }

    // bound method for every type
    pub(crate) fn __new__(zelf: PyRef<Self>, args: FuncArgs, vm: &VirtualMachine) -> PyResult {
        let (subtype, args): (PyRef<Self>, FuncArgs) = args.bind(vm)?;
        if !subtype.fast_issubclass(&zelf) {
            return Err(vm.new_type_error(format!(
                "{zelf}.__new__({subtype}): {subtype} is not a subtype of {zelf}",
                zelf = zelf.name(),
                subtype = subtype.name(),
            )));
        }
        call_slot_new(&zelf, subtype, args, vm)
    }

    fn name_inner<'a, R: 'a>(
        &'a self,
        static_f: impl FnOnce(&'static str) -> R,
        heap_f: impl FnOnce(&'a HeapTypeExt) -> R,
    ) -> R {
        if let Some(ref ext) = self.heaptype_ext {
            heap_f(ext)
        } else {
            static_f(self.slots.name)
        }
    }

    pub fn slot_name(&self) -> BorrowedValue<'_, str> {
        self.name_inner(
            |name| name.into(),
            |ext| PyRwLockReadGuard::map(ext.name.read(), |name| name.as_str()).into(),
        )
    }

    pub fn __qualname__(&self, vm: &VirtualMachine) -> PyObjectRef {
        if let Some(ref heap_type) = self.heaptype_ext {
            heap_type.qualname.read().clone().into()
        } else {
            // For static types, return the name
            vm.ctx.new_str(self.name().deref()).into()
        }
    }
    pub fn __module__(&self, vm: &VirtualMachine) -> PyResult<PyObjectRef> {
        // Heap types store the module in the type dict. Static types take the
        // text before the last `.` of the type name, or `builtins`.
        if self.slots.flags.has_feature(PyTypeFlags::HEAPTYPE) {
            return self
                .attributes
                .get(identifier!(vm, __module__))
                .ok_or_else(|| vm.new_attribute_error("__module__"));
        }
        let slot_name = self.slot_name();
        let module = if let Some((module, _)) = slot_name.rsplit_once('.') {
            vm.ctx.intern_str(module)
        } else {
            vm.ctx.intern_str("builtins")
        };
        Ok(module.to_object())
    }

    /// The type's fully qualified name, the way the `%T` format code prints it:
    /// `module.qualname`, with a `builtins` or `__main__` module left off.
    pub fn fully_qualified_name(&self, vm: &VirtualMachine) -> PyResult<String> {
        let qualname = self.__qualname__(vm);
        let qualname = qualname
            .downcast_ref::<PyStr>()
            .and_then(|qualname| qualname.to_str())
            .map_or_else(|| self.name().to_string(), str::to_owned);
        let module = self.__module__(vm)?;
        Ok(
            match module.downcast_ref::<PyStr>().and_then(|m| m.to_str()) {
                Some("builtins" | "__main__") | None => qualname,
                Some(module) => format!("{module}.{qualname}"),
            },
        )
    }

    pub fn name(&self) -> BorrowedValue<'_, str> {
        self.name_inner(
            |name| name.rsplit_once('.').map_or(name, |(_, name)| name).into(),
            |ext| PyRwLockReadGuard::map(ext.name.read(), |name| name.as_str()).into(),
        )
    }

    // Type Data Slot API - CPython's PyObject_GetTypeData equivalent

    /// Initialize type data for this type. Can only be called once.
    /// Returns an error if the type is not a heap type or if data is already initialized.
    pub fn init_type_data<T: Any + Send + Sync + 'static>(&self, data: T) -> Result<(), String> {
        let ext = self
            .heaptype_ext
            .as_ref()
            .ok_or_else(|| "Cannot set type data on non-heap types".to_string())?;

        let mut type_data = ext.type_data.write();
        if type_data.is_some() {
            return Err("Type data already initialized".to_string());
        }
        *type_data = Some(TypeDataSlot::new(data));
        Ok(())
    }

    /// Get a read guard to the type data.
    /// Returns None if the type is not a heap type, has no data, or the data type doesn't match.
    pub fn get_type_data<T: Any + 'static>(&self) -> Option<TypeDataRef<'_, T>> {
        self.heaptype_ext
            .as_ref()
            .and_then(|ext| TypeDataRef::try_new(ext.type_data.read()))
    }

    /// Get a write guard to the type data.
    /// Returns None if the type is not a heap type, has no data, or the data type doesn't match.
    pub fn get_type_data_mut<T: Any + 'static>(&self) -> Option<TypeDataRefMut<'_, T>> {
        self.heaptype_ext
            .as_ref()
            .and_then(|ext| TypeDataRefMut::try_new(ext.type_data.write()))
    }

    /// Check if this type has type data of the given type.
    pub fn has_type_data<T: Any + 'static>(&self) -> bool {
        self.heaptype_ext.as_ref().is_some_and(|ext| {
            ext.type_data
                .read()
                .as_ref()
                .is_some_and(|slot| slot.get::<T>().is_some())
        })
    }
}

impl Py<PyType> {
    #[inline]
    pub fn slots(&self) -> &PyTypeSlots {
        &self.payload().slots
    }

    #[inline]
    pub fn attributes(&self) -> &TypeNamespace {
        &self.payload().attributes
    }

    #[inline]
    pub fn tp_version_tag(&self) -> &AtomicU32 {
        &self.payload().tp_version_tag
    }

    #[inline]
    pub fn heaptype_ext(&self) -> Option<&HeapTypeExt> {
        self.payload().heaptype_ext.as_deref()
    }

    pub fn is_subtype(&self, other: &Self) -> bool {
        is_subtype_with_mro(&self.mro.read(), self, other)
    }

    /// Equivalent to CPython's PyType_CheckExact macro
    /// Checks if obj is exactly a type (not a subclass)
    pub fn check_exact<'a>(obj: &'a PyObject, vm: &VirtualMachine) -> Option<&'a Self> {
        obj.downcast_ref_if_exact::<PyType>(vm)
    }

    /// Determines if `subclass` is actually a subclass of `cls`, this doesn't call __subclasscheck__,
    /// so only use this if `cls` is known to have not overridden the base __subclasscheck__ magic
    /// method.
    pub fn fast_issubclass(&self, cls: &impl Borrow<PyObject>) -> bool {
        let mro = self.mro.read();
        if mro.is_empty() {
            return self.as_object().is(cls.borrow());
        }
        mro.iter().any(|c| c.is(cls.borrow()))
    }

    pub fn mro_map_collect<F, R>(&self, f: F) -> Vec<R>
    where
        F: Fn(&Self) -> R,
    {
        self.mro.read().iter().map(|x| &**x).map(f).collect()
    }

    pub fn mro_collect(&self) -> Vec<PyRef<PyType>> {
        self.mro
            .read()
            .iter()
            .map(|x| &**x)
            .map(|x| x.to_owned())
            .collect()
    }

    pub fn iter_base_chain(&self) -> impl Iterator<Item = &Self> {
        core::iter::successors(Some(self), |cls| cls.base.deref())
    }

    pub fn extend_methods(&'static self, method_defs: &'static [PyMethodDef], ctx: &Context) {
        for method_def in method_defs {
            let method = method_def.to_proper_method(self, ctx);
            self.set_attr(ctx.intern_str(method_def.name), method);
        }
    }
}

impl PyType {
    pub fn __ror__(zelf: PyObjectRef, other: PyObjectRef, vm: &VirtualMachine) -> PyResult {
        or_(other, zelf, vm)
    }

    pub fn __or__(zelf: PyObjectRef, other: PyObjectRef, vm: &VirtualMachine) -> PyResult {
        or_(zelf, other, vm)
    }

    fn check_set_special_type_attr(
        &self,
        name: &PyStrInterned,
        vm: &VirtualMachine,
    ) -> PyResult<()> {
        if self.slots.flags.has_feature(PyTypeFlags::IMMUTABLETYPE) {
            return Err(vm.new_type_error(format!(
                "cannot set '{}' attribute of immutable type '{}'",
                name,
                self.slot_name()
            )));
        }
        Ok(())
    }
}

#[pyclass(
    itemsize = core::mem::size_of::<crate::builtins::descriptor::PyMemberDefLayout>(),
    with(
        Py,
        Constructor,
        Initializer,
        GetAttr,
        SetAttr,
        Callable,
        AsNumber,
        Representable
    ),
    flags(BASETYPE, HAS_DICT, HAS_WEAKREF)
)]
impl PyType {}

/// Accepts and ignores any arguments.
struct PrepareArgs;

impl FromArgs for PrepareArgs {
    const PARAMS: Option<&'static [Param]> = Some(&[
        Param::positional_only("name"),
        Param::positional_only("bases"),
        Param::var_keyword("kwds"),
    ]);

    fn from_args(_vm: &VirtualMachine, args: &mut FuncArgs) -> Result<Self, ArgumentError> {
        core::mem::take(args);
        Ok(Self)
    }
}

impl Constructor for PyType {
    type Args = FuncArgs;

    fn slot_new(metatype: PyTypeRef, args: FuncArgs, vm: &VirtualMachine) -> PyResult {
        vm_trace!("type.__new__ {:?}", args);

        let is_type_type = metatype.is(vm.ctx.types.type_type);
        if is_type_type && args.args.len() == 1 && args.kwargs.is_empty() {
            return Ok(args.args[0].class().to_owned().into());
        }

        if args.args.len() != 3 {
            return Err(vm.new_type_error(if is_type_type {
                "type() takes 1 or 3 arguments".to_owned()
            } else {
                format!(
                    "type.__new__() takes exactly 3 arguments ({} given)",
                    args.args.len()
                )
            }));
        }

        let (name, bases, dict, kwargs): (PyStrRef, PyTupleRef, PyDictRef, KwArgs) =
            args.clone().bind_for(vm, Self::NAME)?;

        // A mapping that is not an exact dict (e.g. OrderedDict) keeps its
        // own iteration order; copy via the mapping protocol so that order
        // lands in the type dict.
        let dict = if args.args[2].class().is(vm.ctx.types.dict_type) {
            dict
        } else {
            let copied = vm.ctx.new_dict();
            copied.merge_object(args.args[2].clone(), vm)?;
            copied
        };

        if name.as_bytes().contains(&0) {
            return Err(vm.new_value_error("type name must not contain null characters"));
        }
        let name = name.try_into_utf8(vm)?;

        let (metatype, base, bases, base_is_type) = if bases.as_slice().is_empty() {
            let base = vm.ctx.types.object_type.to_owned();
            let bases = PyTuple::new_ref_typed(vec![base.clone()], &vm.ctx);
            (metatype, base, bases, false)
        } else {
            for obj in bases.as_slice() {
                if obj.downcast_ref::<Self>().is_none() {
                    if vm
                        .get_attribute_opt(obj, identifier!(vm, __mro_entries__))?
                        .is_some()
                    {
                        return Err(vm.new_type_error(
                            "type() doesn't support MRO entry resolution; \
                             use types.new_class()",
                        ));
                    }
                    return Err(vm.new_type_error("bases must be types"));
                }
            }
            let bases = bases.try_into_typed::<Self>(vm)?;

            // Search the bases for the proper metatype to deal with this:
            let winner = calculate_meta_class(metatype.clone(), bases.as_slice(), vm)?;
            let metatype = if !winner.is(&metatype) {
                if let Some(ref slot_new) = winner.slots.new.load() {
                    // Pass it to the winner
                    return slot_new(winner, args, vm);
                }
                winner
            } else {
                metatype
            };

            let base = best_base(bases.as_slice(), vm)?;
            let base_is_type = base.is(vm.ctx.types.type_type);

            (metatype, base.to_owned(), bases, base_is_type)
        };

        let qualname = dict
            .get_item_opt(identifier!(vm, __qualname__), vm)?
            .map(|obj| downcast_qualname(obj, vm))
            .transpose()?
            .unwrap_or_else(|| {
                // If __qualname__ is not provided, we can use the name as default
                name.clone().into_wtf8()
            });

        let mut attributes = dict.to_attributes(vm, |vm| {
            crate::stdlib::_warnings::warn(
                vm.ctx.exceptions.runtime_warning,
                format!("non-string key in the __dict__ of class {name}"),
                1,
                vm,
            )
        })?;
        attributes.shift_remove(identifier!(vm, __qualname__));

        // Check __doc__ for surrogates - raises UnicodeEncodeError during type creation
        if let Some(doc) = attributes.get(identifier!(vm, __doc__))
            && let Some(doc_str) = doc.downcast_ref::<PyStr>()
        {
            doc_str.ensure_valid_utf8(vm)?;
        }

        if let Some(f) = attributes.get_mut(identifier!(vm, __init_subclass__))
            && f.class().is(vm.ctx.types.function_type)
        {
            *f = PyClassMethod::from(f.clone()).into_pyobject(vm);
        }

        if let Some(f) = attributes.get_mut(identifier!(vm, __class_getitem__))
            && f.class().is(vm.ctx.types.function_type)
        {
            *f = PyClassMethod::from(f.clone()).into_pyobject(vm);
        }

        if let Some(f) = attributes.get_mut(identifier!(vm, __new__))
            && f.class().is(vm.ctx.types.function_type)
        {
            *f = PyStaticMethod::from(f.clone()).into_pyobject(vm);
        }

        if let Some(globals) = crate::frame::current_globals() {
            let entry = attributes.entry(identifier!(vm, __module__));
            if let Entry::Vacant(entry) = entry
                && let Some(module_name) = globals.get_item_opt(identifier!(vm, __name__), vm)?
            {
                entry.insert(module_name);
            }
        }

        if attributes.get(identifier!(vm, __eq__)).is_some()
            && attributes.get(identifier!(vm, __hash__)).is_none()
        {
            // if __eq__ exists but __hash__ doesn't, overwrite it with None so it doesn't inherit the default hash
            // https://docs.python.org/3/reference/datamodel.html#object.__hash__
            attributes.insert(identifier!(vm, __hash__), vm.ctx.none.clone().into());
        }

        let (heaptype_slots, add_dict, add_weakref): (
            Option<PyRef<PyTuple<PyStrRef>>>,
            bool,
            bool,
        ) = if let Some(x) = attributes.get(identifier!(vm, __slots__)) {
            // Check if __slots__ is bytes - not allowed
            if x.class().is(vm.ctx.types.bytes_type) {
                return Err(vm.new_type_error("__slots__ items must be strings, not 'bytes'"));
            }

            let slots = if x.class().is(vm.ctx.types.str_type) {
                let x = unsafe { x.downcast_unchecked_ref::<PyStr>() };
                PyTuple::new_ref_typed(vec![x.to_owned()], &vm.ctx)
            } else {
                let iter = x.get_iter(vm)?;
                let elements = {
                    let mut elements = Vec::new();
                    while let PyIterReturn::Return(element) = iter.next(vm)? {
                        // Check if any slot item is bytes
                        if element.class().is(vm.ctx.types.bytes_type) {
                            return Err(
                                vm.new_type_error("__slots__ items must be strings, not 'bytes'")
                            );
                        }
                        elements.push(element);
                    }
                    elements
                };
                let tuple = elements.into_pytuple(vm);
                tuple.try_into_typed(vm)?
            };

            // Any nonempty __slots__ is rejected when the base has a variable
            // item size, including a tuple of only `__dict__` or `__weakref__`.
            // Types like weakref.ref have itemsize 0 and do allow slots.
            if !slots.as_slice().is_empty() && base.slots.itemsize > 0 {
                return Err(vm.new_type_error(format!(
                    "nonempty __slots__ not supported for subtype of '{}'",
                    base.name()
                )));
            }

            // Validate slot names and track duplicates
            let mut seen_dict = false;
            let mut seen_weakref = false;
            for slot in slots.as_slice() {
                // Use isidentifier for validation (handles Unicode properly)
                if !slot.isidentifier() {
                    return Err(vm.new_type_error("__slots__ must be identifiers"));
                }

                let slot_name = slot.as_bytes();

                // Check for duplicate __dict__
                if slot_name == b"__dict__" {
                    if seen_dict {
                        return Err(
                            vm.new_type_error("__dict__ slot disallowed: we already got one")
                        );
                    }
                    seen_dict = true;
                }

                // Check for duplicate __weakref__
                if slot_name == b"__weakref__" {
                    if seen_weakref {
                        return Err(
                            vm.new_type_error("__weakref__ slot disallowed: we already got one")
                        );
                    }
                    seen_weakref = true;
                }

                // __qualname__ and __classcell__ are written by the compiler
                // and may share a name with a slot.
                if slot_name != b"__qualname__"
                    && slot_name != b"__classcell__"
                    && slot_name != b"__classdictcell__"
                    && attributes.contains_key(vm.ctx.intern_str(slot.as_wtf8()))
                {
                    return Err(vm.new_value_error(format!(
                        "'{}' in __slots__ conflicts with class variable",
                        slot.as_wtf8()
                    )));
                }
            }

            // Check if base class already has __dict__ - can't redefine it
            if seen_dict && base.slots.flags.has_feature(PyTypeFlags::HAS_DICT) {
                return Err(vm.new_type_error("__dict__ slot disallowed: we already got one"));
            }

            // Check if base class already has __weakref__ - can't redefine it
            if seen_weakref && base.slots.flags.has_feature(PyTypeFlags::HAS_WEAKREF) {
                return Err(vm.new_type_error("__weakref__ slot disallowed: we already got one"));
            }

            // Check if __dict__ or __weakref__ is in slots
            let dict_name = "__dict__";
            let weakref_name = "__weakref__";
            let has_dict = slots.as_slice().iter().any(|s| s.as_wtf8() == dict_name);
            let add_weakref = seen_weakref;

            // Filter out __dict__ and __weakref__ from slots
            // (they become descriptors, not member slots), then sort so
            // __class__ assignment can compare layouts by slot name.
            let mut filtered: Vec<PyStrRef> = slots
                .as_slice()
                .iter()
                .filter(|s| s.as_wtf8() != dict_name && s.as_wtf8() != weakref_name)
                .cloned()
                .collect();
            filtered.sort_by(|a, b| a.as_bytes().cmp(b.as_bytes()));
            let filtered_slots = PyTuple::new_ref_typed(filtered, &vm.ctx);

            (Some(filtered_slots), has_dict, add_weakref)
        } else {
            (None, false, false)
        };

        // FIXME: this is a temporary fix. multi bases with multiple slots will break object
        let base_member_count = bases
            .as_slice()
            .iter()
            .map(|base| base.slots.member_count)
            .max()
            .unwrap();
        let heaptype_member_count = heaptype_slots.as_ref().map_or(0, |x| x.as_slice().len());
        let member_count: usize = base_member_count + heaptype_member_count;

        let mut flags = PyTypeFlags::HEAP_TYPE;

        // Check if we may add dict
        // We can only add a dict if the primary base class doesn't already have one
        // In CPython, this checks tp_dictoffset == 0
        let may_add_dict = !base.slots.flags.has_feature(PyTypeFlags::HAS_DICT);

        // Add HAS_DICT and MANAGED_DICT if:
        // 1. __slots__ is not defined AND base doesn't have dict, OR
        // 2. __dict__ is in __slots__
        if (heaptype_slots.is_none() && may_add_dict) || add_dict {
            // type_ready_managed_dict: fixed-size managed-dict types
            // get an inline values array after the object.
            flags |= if base.slots.itemsize == 0 {
                MANAGED_DICT_INLINE_FLAGS
            } else {
                MANAGED_DICT_FLAGS
            };
        }

        // Add HAS_WEAKREF if:
        // 1. __slots__ is not defined (automatic weakref support), OR
        // 2. __weakref__ is in __slots__
        // A variable-size base does not gain a weakref slot.
        let may_add_weakref =
            base.slots.itemsize == 0 && !base.slots.flags.has_feature(PyTypeFlags::HAS_WEAKREF);
        if (heaptype_slots.is_none() && may_add_weakref) || add_weakref {
            flags |= WEAKREF_FLAGS;
        }

        let (slots, heaptype_ext) = {
            let slots = PyTypeSlots {
                flags: crate::types::AtomicPyTypeFlags::from_plain(flags),
                member_count,
                itemsize: base.slots.itemsize,
                ..PyTypeSlots::heap_default()
            };
            let heaptype_ext = HeapTypeExt {
                name: PyRwLock::new(name),
                qualname: PyRwLock::new(qualname),
                slots: heaptype_slots.clone(),
                type_data: PyRwLock::new(None),
                specialization_cache: TypeSpecializationCache::new(),
                interpreter_id: HeapTypeExt::creating_interpreter_id(),
            };
            (slots, heaptype_ext)
        };

        let custom_mro = !metatype.is(vm.ctx.types.type_type);
        let typ = Self::new_heap_inner(
            base,
            bases,
            attributes,
            slots,
            heaptype_ext,
            metatype,
            &vm.ctx,
            custom_mro,
        )
        .map_err(|e| vm.new_type_error(e))?;

        // tp_dict keeps non-string keys so lookup can hash-compare them.
        if let Some(tp_dict) = typ.attributes.as_dict() {
            for (key, value) in &*dict {
                if key.downcast_ref::<PyStr>().is_none() {
                    tp_dict.set_item(&*key, value, vm)?;
                }
            }
        }

        // Fill __classcell__ before a custom mro() runs so methods that
        // close over __class__ can execute during type creation.
        if let Some(cell) = typ.attributes.get(identifier!(vm, __classcell__)) {
            let cell = PyCellRef::try_from_object(vm, cell.clone()).map_err(|_| {
                vm.new_type_error(format!(
                    "__classcell__ must be a nonlocal cell, not {}",
                    cell.class().name()
                ))
            })?;
            cell.set(Some(typ.clone().into()));
            typ.attributes.remove(identifier!(vm, __classcell__));
        }
        if let Some(cell) = typ.attributes.get(identifier!(vm, __classdictcell__)) {
            let cell = PyCellRef::try_from_object(vm, cell.clone()).map_err(|_| {
                vm.new_type_error(format!(
                    "__classdictcell__ must be a nonlocal cell, not {}",
                    cell.class().name()
                ))
            })?;
            let namespace = typ
                .attributes
                .as_dict()
                .expect("a type built by type.__new__ has a dict namespace");
            cell.set(Some(namespace.to_owned().into()));
            typ.attributes.remove(identifier!(vm, __classdictcell__));
        }

        if custom_mro {
            mro_internal(&typ, vm)?;
            typ.init_slots(&vm.ctx);
        }

        if let Some(ref slots) = heaptype_slots {
            let class_name = typ.name().to_string();
            for (offset, member) in (base_member_count..).zip(slots.as_slice().iter()) {
                // Apply name mangling for private attributes (__x -> _ClassName__x)
                let member_str = member
                    .to_str()
                    .ok_or_else(|| vm.new_type_error("__slots__ must be valid UTF-8 strings"))?;
                let mangled_name = mangle_name(&class_name, member_str);
                let member_def = PyMemberDef {
                    name: mangled_name.clone(),
                    kind: MemberKind::ObjectEx,
                    offset: crate::object::slot_member_offset(offset),
                    flags: PyMemberFlags::empty(),
                    doc: ItemDoc::NONE,
                };
                let attr_name = vm.ctx.intern_str(mangled_name.as_str());
                let member_descriptor: PyRef<PyMemberDescriptor> =
                    vm.ctx.new_pyref(PyMemberDescriptor {
                        common: PyDescriptorOwned {
                            typ: typ.clone(),
                            name: attr_name,
                            qualname: PyRwLock::new(None),
                        },
                        member: member_def,
                        access: MemberAccess::Offset,
                    });
                // __slots__ attributes always get a member descriptor
                // (this overrides any inherited attribute from MRO)
                typ.set_attr(attr_name, member_descriptor.into());
                // `init_slots` already ran in `new_heap_inner` before these member
                // descriptors existed, so a slot name shaped like a dunder (e.g. a
                // class that puts "__setitem__" in `__slots__` to store a per-instance
                // callable under a slot descriptor) was never wired into the type's C
                // slots (mp_ass_subscript and friends). Recompute the slot now that
                // the attribute is actually present on the type.
                if attr_name.as_bytes().starts_with(b"__") && attr_name.as_bytes().ends_with(b"__")
                {
                    typ.update_slot::<true>(attr_name, &vm.ctx);
                }
            }
        }

        // All *classes* should have a dict. Exceptions are *instances* of
        // classes that define __slots__ and instances of built-in classes
        // (with exceptions, e.g function)
        // Also, type subclasses don't need their own __dict__ descriptor
        // since they inherit it from type

        // Add __dict__ descriptor after type creation to ensure correct __objclass__
        // Only add if:
        // 1. base is not type (type subclasses inherit __dict__ from type)
        // 2. the class has HAS_DICT flag (i.e., __slots__ was not defined or __dict__ is in __slots__)
        // 3. no base class in MRO already provides __dict__ descriptor
        if !base_is_type && typ.slots.flags.has_feature(PyTypeFlags::HAS_DICT) {
            let __dict__ = identifier!(vm, __dict__);
            let has_inherited_dict = typ
                .mro
                .read()
                .iter()
                .any(|base| base.attributes.contains(__dict__));
            if !typ.attributes.contains(__dict__) && !has_inherited_dict {
                let getset = super::PyGetSet::new("__dict__", &typ, &vm.ctx)
                    .with_get(subtype_get_dict)
                    .with_set(subtype_set_dict)
                    .with_doc(ItemDoc::static_text("dictionary for instance variables"));
                let descriptor = PyRef::new_ref(getset, vm.ctx.types.getset_type.to_owned(), None);
                typ.attributes.set(__dict__, descriptor.into());
            }
        }

        // Add __weakref__ descriptor for types with HAS_WEAKREF
        if typ.slots.flags.has_feature(PyTypeFlags::HAS_WEAKREF) {
            let __weakref__ = vm.ctx.intern_str("__weakref__");
            let has_inherited_weakref = typ
                .mro
                .read()
                .iter()
                .any(|base| base.attributes.contains(__weakref__));
            if !typ.attributes.contains(__weakref__) && !has_inherited_weakref {
                let getset = super::PyGetSet::new("__weakref__", &typ, &vm.ctx)
                    .with_get(subtype_get_weakref)
                    .with_set(subtype_set_weakref)
                    .with_doc(ItemDoc::static_text(
                        "list of weak references to the object",
                    ));
                let descriptor = PyRef::new_ref(getset, vm.ctx.types.getset_type.to_owned(), None);
                typ.attributes.set(__weakref__, descriptor.into());
            }
        }

        // Set __doc__ to None if not already present in the type's dict
        // This matches CPython's behavior in type_dict_set_doc (typeobject.c)
        // which ensures every type has a __doc__ entry in its dict
        {
            let __doc__ = identifier!(vm, __doc__);
            if !typ.attributes.contains(__doc__) {
                typ.attributes.set(__doc__, vm.ctx.none());
            }
        }

        // avoid deadlock
        let attributes = typ
            .attributes
            .entries()
            .into_iter()
            .filter_map(|(name, obj)| {
                vm.get_method(obj.clone(), identifier!(vm, __set_name__))
                    .map(|res| res.map(|meth| (obj, name, meth)))
            })
            .collect::<PyResult<Vec<_>>>()?;
        for (obj, name, set_name) in attributes {
            let name_repr = name
                .str(vm)
                .map_or_else(|_| "?".to_owned(), |name| name.to_string());
            set_name.call((typ.clone(), name), vm).inspect_err(|e| {
                // PEP 678: Add a note to the original exception instead of wrapping it
                // (Python 3.12+, gh-77757)
                let note = format!(
                    "Error calling __set_name__ on '{}' instance '{}' in '{}'",
                    obj.class().name(),
                    name_repr,
                    typ.name()
                );
                // Ignore result - adding a note is best-effort, the original exception is what matters
                drop(vm.call_method(e.as_object(), "add_note", (vm.ctx.new_str(note.as_str()),)));
            })?;
        }

        // type_new_init_subclass: super(type, type).__init_subclass__(**kwds)
        let super_obj = vm
            .ctx
            .types
            .super_type
            .as_object()
            .call((typ.clone(), typ.clone()), vm)?;
        super_obj
            .get_attr(identifier!(vm, __init_subclass__), vm)?
            .call(kwargs, vm)?;

        Ok(typ.into())
    }

    fn py_new(_cls: &Py<PyType>, _args: Self::Args, _vm: &VirtualMachine) -> PyResult<Self> {
        unimplemented!("use slot_new")
    }
}

const SIGNATURE_END_MARKER: &str = ")\n--\n\n";
fn get_signature(doc: &str) -> Option<&str> {
    doc.find(SIGNATURE_END_MARKER).map(|index| &doc[..=index])
}

fn find_signature<'a>(name: &str, doc: &'a str) -> Option<&'a str> {
    let name = name.rsplit('.').next().unwrap();
    let doc = doc.strip_prefix(name)?;
    doc.starts_with('(').then_some(doc)
}

pub(crate) fn get_text_signature_from_internal_doc<'a>(
    name: &str,
    internal_doc: &'a str,
) -> Option<&'a str> {
    find_signature(name, internal_doc).and_then(get_signature)
}

// _PyType_DocWithoutSignature in CPython
fn doc_without_signature<'a>(name: &str, internal_doc: &'a str) -> &'a str {
    // If the doc starts with the type name and a '(', it's a signature
    if let Some(doc_without_sig) = find_signature(name, internal_doc) {
        // Find where the signature ends
        if let Some(sig_end_pos) = doc_without_sig.find(SIGNATURE_END_MARKER) {
            let after_sig = &doc_without_sig[sig_end_pos + SIGNATURE_END_MARKER.len()..];
            // Return the documentation after the signature, or empty string if none
            return after_sig;
        }
    }
    // If no signature found, return the whole doc
    internal_doc
}

// _PyType_GetDocFromInternalDoc in CPython
pub(crate) fn get_doc_from_internal_doc<'a>(name: &str, internal_doc: &'a str) -> Option<&'a str> {
    let doc = doc_without_signature(name, internal_doc);
    (!doc.is_empty()).then_some(doc)
}

pub(crate) fn rendered_item_doc(name: &str, doc: ItemDoc) -> Option<&'static str> {
    if doc.len != 0 {
        return db_doc(doc.offset, doc.len);
    }
    doc.text
        .and_then(|text| get_doc_from_internal_doc(name, text))
}

impl Initializer for PyType {
    type Args = FuncArgs;

    // type_init
    fn slot_init(_zelf: &PyObject, args: FuncArgs, vm: &VirtualMachine) -> PyResult<()> {
        // type.__init__() takes 1 or 3 arguments
        if args.args.len() == 1 && !args.kwargs.is_empty() {
            return Err(vm.new_type_error("type.__init__() takes no keyword arguments"));
        }
        if args.args.len() != 1 && args.args.len() != 3 {
            return Err(vm.new_type_error("type.__init__() takes 1 or 3 arguments"));
        }
        Ok(())
    }

    fn init(_zelf: &Py<Self>, _args: Self::Args, _vm: &VirtualMachine) -> PyResult<()> {
        unreachable!("slot_init is defined")
    }
}

impl GetAttr for PyType {
    fn getattro(zelf: &Py<Self>, name_str: &Py<PyStr>, vm: &VirtualMachine) -> PyResult {
        #[cold]
        fn attribute_error(
            zelf: &Py<PyType>,
            name: &Wtf8,
            vm: &VirtualMachine,
        ) -> PyBaseExceptionRef {
            vm.new_attribute_error(format!(
                "type object '{}' has no attribute '{}'",
                zelf.slot_name(),
                name,
            ))
        }

        let Some(name) = vm.ctx.interned_str(name_str) else {
            return Err(attribute_error(zelf, name_str.as_wtf8(), vm));
        };
        vm_trace!("type.__getattribute__({:?}, {:?})", zelf, name);
        let mcl = zelf.class();
        let mcl_attr = mcl.get_attr(name);

        if let Some(ref attr) = mcl_attr {
            let attr_class = attr.class();
            let has_descr_set = attr_class.slots.descr_set.load().is_some();
            if has_descr_set {
                let descr_get = attr_class.slots.descr_get.load();
                if let Some(descr_get) = descr_get {
                    return descr_get(
                        attr.as_object(),
                        Some(zelf.as_object()),
                        Some(mcl.as_object()),
                        vm,
                    );
                }
            }
        }

        let zelf_attr = zelf.get_attr(name);

        if let Some(attr) = zelf_attr {
            let descr_get = attr.class().slots().descr_get.load();
            if let Some(descr_get) = descr_get {
                descr_get(attr.as_object(), None, Some(zelf.as_object()), vm)
            } else {
                Ok(attr)
            }
        } else if let Some(attr) = mcl_attr {
            vm.call_if_get_descriptor(&attr, zelf.to_owned().into())
        } else {
            Err(attribute_error(zelf, name_str.as_wtf8(), vm))
        }
    }
}

#[pyclass]
impl Py<PyType> {
    #[pygetset]
    fn __mro__(&self, vm: &VirtualMachine) -> PyObjectRef {
        let mro = self.mro.read();
        if mro.is_empty() {
            return vm.ctx.none();
        }
        let elements: Vec<PyObjectRef> = mro.iter().map(|x| x.as_object().to_owned()).collect();
        drop(mro);
        vm.ctx.new_tuple(elements).into()
    }

    #[pygetset]
    fn __doc__(&self, vm: &VirtualMachine) -> PyResult {
        // Similar to CPython's type_get_doc
        // For non-heap types (static types), check if there's an internal doc
        let internal_doc = self.slots.doc;
        if !self.slots.flags.has_feature(PyTypeFlags::HEAPTYPE)
            && (internal_doc.text.is_some() || internal_doc.len != 0)
        {
            let doc_str = rendered_item_doc(&self.name(), internal_doc);
            return Ok(doc_str.map_or_else(|| vm.ctx.none(), |doc| vm.ctx.new_str(doc).into()));
        }

        // Check if there's a __doc__ in THIS type's dict only (not MRO)
        // CPython returns None if __doc__ is not in the type's own dict
        if let Some(doc_attr) = self.get_direct_attr(vm.ctx.intern_str("__doc__")) {
            // If it's a descriptor, call its __get__ method
            let descr_get = doc_attr.class().slots().descr_get.load();
            if let Some(descr_get) = descr_get {
                descr_get(doc_attr.as_object(), None, Some(self.as_object()), vm)
            } else {
                Ok(doc_attr)
            }
        } else {
            Ok(vm.ctx.none())
        }
    }

    #[pygetset(setter)]
    fn set___doc__(&self, value: PySetterValue, vm: &VirtualMachine) -> PyResult<()> {
        // Similar to CPython's type_set_doc
        let value = value.ok_or_else(|| {
            vm.new_type_error(format!(
                "cannot delete '__doc__' attribute of immutable type '{}'",
                self.name()
            ))
        })?;

        // Check if we can set this special type attribute
        self.check_set_special_type_attr(identifier!(vm, __doc__), vm)?;

        let _prev_value = PyType::with_type_lock(vm, || {
            self.modified_inner();
            self.attributes.insert(identifier!(vm, __doc__), value)
        });

        Ok(())
    }

    #[pymethod]
    fn __dir__(&self, vm: &VirtualMachine) -> PyList {
        let attributes: Vec<PyObjectRef> = self
            .get_attributes(&vm.ctx)
            .into_iter()
            .map(|(k, _)| k.to_object())
            .collect();
        PyList::from(attributes)
    }

    #[pymethod]
    fn __instancecheck__(&self, instance: PyObjectRef, vm: &VirtualMachine) -> PyResult<bool> {
        // Use real_is_instance to avoid infinite recursion
        instance.real_is_instance(self.as_object(), vm)
    }

    #[pymethod]
    fn __subclasscheck__(&self, subclass: PyObjectRef, vm: &VirtualMachine) -> PyResult<bool> {
        // Use real_is_subclass to avoid going through __subclasscheck__ recursion
        // This matches CPython's type___subclasscheck___impl which calls _PyObject_RealIsSubclass
        subclass.real_is_subclass(self.as_object(), vm)
    }

    #[pyclassmethod]
    fn __subclasshook__(_args: FuncArgs, vm: &VirtualMachine) -> PyObjectRef {
        vm.ctx.not_implemented()
    }

    #[pymethod]
    fn mro(&self, vm: &VirtualMachine) -> PyResult<Vec<PyObjectRef>> {
        Ok(mro_implementation(self, vm)?
            .into_iter()
            .map(Into::into)
            .collect())
    }

    #[pygetset]
    fn __bases__(&self, vm: &VirtualMachine) -> PyTupleRef {
        PyType::with_type_lock(vm, || self.bases.read().clone().into_untyped())
    }
    #[pygetset(setter, name = "__bases__")]
    fn set_bases(zelf: &Self, bases_tuple: PyTupleRef, vm: &VirtualMachine) -> PyResult<()> {
        // TODO: Assigning to __bases__ is only used in typing.NamedTupleMeta.__new__
        // Rather than correctly re-initializing the class, we are skipping a few steps for now
        if zelf.slots().flags.has_feature(PyTypeFlags::IMMUTABLETYPE) {
            return Err(vm.new_type_error(format!(
                "cannot set '__bases__' attribute of immutable type '{}'",
                zelf.name()
            )));
        }
        if bases_tuple.as_slice().is_empty() {
            return Err(vm.new_type_error(format!(
                "can only assign non-empty tuple to {}.__bases__, not ()",
                zelf.name()
            )));
        }
        for base in bases_tuple.as_slice() {
            if base.downcast_ref::<PyType>().is_none() {
                return Err(vm.new_type_error(format!(
                    "{}.__bases__ must be tuple of classes, not '{}'",
                    zelf.name(),
                    base.class().name()
                )));
            }
        }
        let bases = bases_tuple.try_into_typed::<PyType>(vm)?;

        // Compute the new solid base before committing anything. This also
        // validates the new bases (BASETYPE flag, no instance layout
        // conflict), the same checks type creation performs.
        let new_base = best_base(bases.as_slice(), vm)?.to_owned();

        // Reject reparenting onto a base whose instances have an incompatible
        // object layout.
        let old_base_owned = zelf.base.load_owned();
        let old_base = old_base_owned
            .as_deref()
            .unwrap_or(vm.ctx.types.object_type);
        compatible_for_assignment(old_base, &new_base, "__bases__", vm)?;

        // References released inside the critical section are collected here
        // and dropped after the lock: dropping them inside can run arbitrary
        // code that re-acquires the non-reentrant type mutex.
        let mut retired: Vec<PyObjectRef> = Vec::new();

        // A base swapped out of `zelf.base` may still be observed by
        // concurrent lock-free readers; keep it alive in the frame's
        // temporary refs so they never see a dangling pointer.
        let keep_alive = |type_ref: PyTypeRef, retired: &mut Vec<PyObjectRef>| {
            if let Some(frame) = vm.current_frame() {
                frame
                    .iframe()
                    .cold()
                    .temporary_refs
                    .lock()
                    .push(type_ref.into());
            } else {
                retired.push(type_ref.into());
            }
        };

        let add_as_subclass = |bases: &[PyTypeRef]| {
            let weakref_type = super::PyWeak::static_type();
            for base in bases {
                base.subclasses.write().push(
                    zelf.as_object()
                        .downgrade_with_weakref_typ_opt(None, weakref_type.to_owned())
                        .unwrap(),
                );
            }
        };

        let remove_as_subclass = |bases: &[PyTypeRef], retired: &mut Vec<PyObjectRef>| {
            for base in bases {
                let mut subclasses = base.subclasses.write();
                let mut kept = Vec::with_capacity(subclasses.len());
                for weak in subclasses.drain(..) {
                    match weak.upgrade() {
                        Some(obj) if obj.is(zelf.as_object()) => {
                            retired.push(obj);
                            retired.push(weak.into());
                        }
                        Some(obj) => {
                            retired.push(obj);
                            kept.push(weak);
                        }
                        None => retired.push(weak.into()),
                    }
                }
                *subclasses = kept;
            }
        };

        let result = PyType::with_type_lock(vm, || {
            for base in bases.as_slice() {
                if is_subtype_with_mro(&base.mro.read(), base, zelf)
                    || (!base.mro.read().is_empty() && type_is_subtype_base_chain(base, zelf, vm))
                {
                    return Err(vm.new_type_error("a __bases__ item causes an inheritance cycle"));
                }
            }

            let old_bases = core::mem::replace(&mut *zelf.bases.write(), bases.clone());
            let old_base = unsafe { zelf.base.swap(Some(new_base.clone())) };

            // Recursively update the mros of this class and all subclasses,
            // recording the previous mros so a failure can be rolled back.
            fn update_mro_recursively(
                cls: &Py<PyType>,
                undo: &mut Vec<(PyTypeRef, Vec<PyTypeRef>)>,
                vm: &VirtualMachine,
            ) -> PyResult<i32> {
                let old_ptr = cls.mro.read().as_ptr();
                let new_mro = mro_invoke(cls, vm)?;
                if cls.mro.read().as_ptr() != old_ptr {
                    // A nested custom mro() already replaced tp_mro.
                    return Ok(0);
                }
                let old_mro = core::mem::replace(&mut *cls.mro.write(), new_mro);
                undo.push((cls.to_owned(), old_mro));
                cls.modified_inner();
                let subclasses: Vec<PyTypeRef> = cls
                    .subclasses
                    .read()
                    .iter()
                    .filter_map(|subclass| subclass.upgrade())
                    .filter_map(|subclass| subclass.downcast::<PyType>().ok())
                    .collect();
                for subclass in subclasses {
                    update_mro_recursively(&subclass, undo, vm)?;
                }
                Ok(1)
            }
            let mut undo = Vec::new();
            if let Err(err) = update_mro_recursively(zelf, &mut undo, vm) {
                // Roll back to the previous state. A class reachable through
                // multiple bases is recorded once per visit, so restore in
                // reverse to end with the first-recorded (original) mro.
                for (cls, old_mro) in undo.into_iter().rev() {
                    let failed_mro = core::mem::replace(&mut *cls.mro.write(), old_mro);
                    retired.extend(failed_mro.into_iter().map(Into::into));
                    retired.push(cls.into());
                }
                // Take no action if tp_bases was replaced through reentrance.
                if core::ptr::eq(&**zelf.bases.read(), &*bases) {
                    let failed_bases = core::mem::replace(&mut *zelf.bases.write(), old_bases);
                    if let Some(failed_base) = unsafe { zelf.base.swap(old_base) } {
                        keep_alive(failed_base, &mut retired);
                    }
                    retired.push(failed_bases.into_untyped().into());
                    zelf.modified_inner();
                } else {
                    retired.push(old_bases.into_untyped().into());
                    if let Some(old_base) = old_base {
                        keep_alive(old_base, &mut retired);
                    }
                }
                return Err(err);
            }
            // Retire the replaced mros as well; dropping them here would
            // release them while the lock is held.
            for (cls, old_mro) in undo {
                retired.extend(old_mro.into_iter().map(Into::into));
                retired.push(cls.into());
            }

            // Take no action if tp_bases was replaced through reentrance.
            if core::ptr::eq(&**zelf.bases.read(), &*bases) {
                remove_as_subclass(old_bases.as_slice(), &mut retired);
                add_as_subclass(bases.as_slice());
                zelf.update_all_slots(&vm.ctx);
            }

            retired.push(old_bases.into_untyped().into());
            if let Some(old_base) = old_base {
                keep_alive(old_base, &mut retired);
            }
            crate::stdlib::_testinternalcapi::note_set_bases();
            Ok(())
        });
        drop(retired);
        result
    }

    #[pygetset]
    fn __abstractmethods__(zelf: &Self, vm: &VirtualMachine) -> PyResult {
        if zelf.is(vm.ctx.types.type_type) {
            return Err(vm.new_attribute_error("__abstractmethods__"));
        }
        zelf.get_direct_attr(identifier!(vm, __abstractmethods__))
            .ok_or_else(|| vm.new_attribute_error("__abstractmethods__"))
    }

    #[pygetset(setter)]
    fn set___abstractmethods__(&self, value: PySetterValue, vm: &VirtualMachine) -> PyResult<()> {
        let key = identifier!(vm, __abstractmethods__);
        let is_abstract = match &value {
            PySetterValue::Assign(val) => val.try_to_bool(vm)?,
            PySetterValue::Delete => false,
        };
        match value {
            PySetterValue::Assign(val) => {
                PyType::with_type_lock(vm, || {
                    self.modified_inner();
                    let _prev = self.attributes.insert(key, val);
                    self.set_is_abstract(is_abstract);
                });
            }
            PySetterValue::Delete => {
                let removed = PyType::with_type_lock(vm, || {
                    self.modified_inner();
                    let removed = self.attributes.remove(key);
                    if removed.is_some() {
                        self.set_is_abstract(false);
                    }
                    removed
                });
                if removed.is_none() {
                    return Err(vm.new_attribute_error("__abstractmethods__"));
                }
            }
        }
        Ok(())
    }

    #[pygetset]
    pub fn __name__(&self, vm: &VirtualMachine) -> PyStrRef {
        self.name_inner(
            |name| {
                vm.ctx
                    .interned_str(name.rsplit_once('.').map_or(name, |(_, name)| name))
                    .unwrap_or_else(|| {
                        panic!(
                            "static type name must be already interned but {} is not",
                            self.slot_name()
                        )
                    })
                    .to_owned()
            },
            |ext| ext.name.read().clone().into_wtf8(),
        )
    }

    #[pygetset]
    pub fn __qualname__(&self, vm: &VirtualMachine) -> PyObjectRef {
        self.payload.__qualname__(vm)
    }

    #[pygetset(setter)]
    fn set___qualname__(&self, value: PySetterValue, vm: &VirtualMachine) -> PyResult<()> {
        self.check_set_special_type_attr(identifier!(vm, __qualname__), vm)?;
        let value = value.ok_or_else(|| {
            vm.new_type_error(format!(
                "cannot delete '__qualname__' attribute of immutable type '{}'",
                self.name()
            ))
        })?;

        let str_value = downcast_qualname(value, vm)?;

        let heap_type = self.heaptype_ext.as_ref().ok_or_else(|| {
            vm.new_type_error(format!(
                "cannot set '__qualname__' attribute of immutable type '{}'",
                self.name()
            ))
        })?;

        // Use std::mem::replace to swap the new value in and get the old value out,
        // then drop the old value after releasing the lock
        let _old_qualname = {
            let mut qualname_guard = heap_type.qualname.write();
            core::mem::replace(&mut *qualname_guard, str_value)
        };
        // old_qualname is dropped here, outside the lock scope

        Ok(())
    }

    #[pygetset]
    fn __annotate__(&self, vm: &VirtualMachine) -> PyResult<PyObjectRef> {
        if !self.slots.flags.has_feature(PyTypeFlags::HEAPTYPE) {
            return Err(vm.new_attribute_error(format!(
                "type object '{}' has no attribute '__annotate__'",
                self.name()
            )));
        }

        let annotate_key = identifier!(vm, __annotate__);
        let annotate_func_key = identifier!(vm, __annotate_func__);
        if let Some(annotate) = self.attributes.get(annotate_key) {
            return Ok(annotate);
        }
        if let Some(annotate) = self.attributes.get(annotate_func_key) {
            return Ok(annotate);
        }

        let none = vm.ctx.none();
        let (result, _prev) = PyType::with_type_lock(vm, || {
            if let Some(annotate) = self.attributes.get(annotate_key) {
                return (annotate, None);
            }
            if let Some(annotate) = self.attributes.get(annotate_func_key) {
                return (annotate, None);
            }
            self.modified_inner();
            let prev = self.attributes.insert(annotate_func_key, none.clone());
            (none, prev)
        });
        Ok(result)
    }

    #[pygetset(setter)]
    fn set___annotate__(&self, value: PySetterValue, vm: &VirtualMachine) -> PyResult<()> {
        let value = match value {
            PySetterValue::Delete => {
                return Err(vm.new_type_error("cannot delete __annotate__ attribute"));
            }
            PySetterValue::Assign(v) => v,
        };

        if self.slots.flags.has_feature(PyTypeFlags::IMMUTABLETYPE) {
            return Err(vm.new_type_error(format!(
                "cannot set '__annotate__' attribute of immutable type '{}'",
                self.name()
            )));
        }

        if !vm.is_none(&value) && !value.is_callable() {
            return Err(vm.new_type_error("__annotate__ must be callable or None"));
        }

        let _prev_values = PyType::with_type_lock(vm, || {
            self.modified_inner();
            // Clear cached annotations only when setting to a new callable
            let removed = if !vm.is_none(&value) {
                self.attributes
                    .remove(identifier!(vm, __annotations_cache__))
            } else {
                None
            };
            let prev = self
                .attributes
                .insert(identifier!(vm, __annotate_func__), value);
            (removed, prev)
        });

        Ok(())
    }

    #[pygetset]
    fn __annotations__(&self, vm: &VirtualMachine) -> PyResult<PyObjectRef> {
        let annotations_key = identifier!(vm, __annotations__);
        let annotations_cache_key = identifier!(vm, __annotations_cache__);
        if let Some(annotations) = self.attributes.get(annotations_key) {
            // Ignore the __annotations__ descriptor stored on type itself.
            if !annotations.class().is(vm.ctx.types.getset_type) {
                if vm.is_none(&annotations)
                    || annotations.class().is(vm.ctx.types.dict_type)
                    || self.slots.flags.has_feature(PyTypeFlags::HEAPTYPE)
                {
                    return Ok(annotations);
                }
                return Err(vm.new_attribute_error(format!(
                    "type object '{}' has no attribute '__annotations__'",
                    self.name()
                )));
            }
        }
        if let Some(annotations) = self.attributes.get(annotations_cache_key) {
            if vm.is_none(&annotations)
                || annotations.class().is(vm.ctx.types.dict_type)
                || self.slots.flags.has_feature(PyTypeFlags::HEAPTYPE)
            {
                return Ok(annotations);
            }
            return Err(vm.new_attribute_error(format!(
                "type object '{}' has no attribute '__annotations__'",
                self.name()
            )));
        }

        if !self.slots.flags.has_feature(PyTypeFlags::HEAPTYPE) {
            return Err(vm.new_attribute_error(format!(
                "type object '{}' has no attribute '__annotations__'",
                self.name()
            )));
        }

        // Get __annotate__ and call it if callable
        let annotate = self.__annotate__(vm)?;
        let annotations = if annotate.is_callable() {
            // Call __annotate__(1) where 1 is FORMAT_VALUE
            let result = annotate.call((1i32,), vm)?;
            if !result.class().is(vm.ctx.types.dict_type) {
                return Err(vm.new_type_error(format!(
                    "__annotate__ returned non-dict of type '{}'",
                    result.class().name()
                )));
            }
            result
        } else {
            vm.ctx.new_dict().into()
        };

        let (result, _prev) = PyType::with_type_lock(vm, || {
            if let Some(existing) = self.attributes.get(annotations_key)
                && !existing.class().is(vm.ctx.types.getset_type)
            {
                return (existing, None);
            }
            if let Some(existing) = self.attributes.get(annotations_cache_key) {
                return (existing, None);
            }
            self.modified_inner();
            let prev = self
                .attributes
                .insert(annotations_cache_key, annotations.clone());
            (annotations, prev)
        });
        Ok(result)
    }

    #[pygetset(setter)]
    fn set___annotations__(
        &self,
        value: crate::function::PySetterValue<PyObjectRef>,
        vm: &VirtualMachine,
    ) -> PyResult<()> {
        if self.slots.flags.has_feature(PyTypeFlags::IMMUTABLETYPE) {
            return Err(vm.new_type_error(format!(
                "cannot set '__annotations__' attribute of immutable type '{}'",
                self.name()
            )));
        }

        let _prev_values = PyType::with_type_lock(vm, || {
            self.modified_inner();
            let has_annotations = self.attributes.contains(identifier!(vm, __annotations__));

            let mut prev = Vec::new();
            match value {
                crate::function::PySetterValue::Assign(value) => {
                    let key = if has_annotations {
                        identifier!(vm, __annotations__)
                    } else {
                        identifier!(vm, __annotations_cache__)
                    };
                    prev.extend(self.attributes.insert(key, value));
                    if has_annotations {
                        prev.extend(
                            self.attributes
                                .remove(identifier!(vm, __annotations_cache__)),
                        );
                    }
                }
                crate::function::PySetterValue::Delete => {
                    let removed = if has_annotations {
                        self.attributes.remove(identifier!(vm, __annotations__))
                    } else {
                        self.attributes
                            .remove(identifier!(vm, __annotations_cache__))
                    };
                    if removed.is_none() {
                        return Err(vm.new_attribute_error("__annotations__"));
                    }
                    prev.extend(removed);
                    if has_annotations {
                        prev.extend(
                            self.attributes
                                .remove(identifier!(vm, __annotations_cache__)),
                        );
                    }
                }
            }
            prev.extend(self.attributes.remove(identifier!(vm, __annotate_func__)));
            prev.extend(self.attributes.remove(identifier!(vm, __annotate__)));
            Ok(prev)
        })?;

        Ok(())
    }

    #[pygetset]
    pub fn __module__(&self, vm: &VirtualMachine) -> PyResult<PyObjectRef> {
        self.payload.__module__(vm)
    }

    #[pygetset(setter)]
    fn set___module__(&self, value: PyObjectRef, vm: &VirtualMachine) -> PyResult<()> {
        self.check_set_special_type_attr(identifier!(vm, __module__), vm)?;
        let _prev_values = PyType::with_type_lock(vm, || {
            self.modified_inner();
            let removed = self.attributes.remove(identifier!(vm, __firstlineno__));
            let prev = self.attributes.insert(identifier!(vm, __module__), value);
            (removed, prev)
        });
        Ok(())
    }

    #[pyclassmethod]
    fn __prepare__(_cls: PyTypeRef, _args: PrepareArgs, vm: &VirtualMachine) -> PyDictRef {
        vm.ctx.new_dict()
    }

    #[pymethod]
    fn __subclasses__(&self, vm: &VirtualMachine) -> PyList {
        let mut subclasses = self.subclasses.write();
        subclasses.retain(|x| x.upgrade().is_some());
        let interpreter_id = vm.state.interpreter_id;
        PyList::from(
            subclasses
                .iter()
                .filter_map(|x| x.upgrade())
                .filter(|obj| {
                    obj.downcast_ref::<PyType>()
                        .is_none_or(|typ| typ.is_visible_to_interpreter(interpreter_id))
                })
                .collect::<Vec<_>>(),
        )
    }

    #[pygetset]
    fn __dict__(zelf: PyRef<PyType>) -> PyMappingProxy {
        PyMappingProxy::from(zelf)
    }

    #[pygetset(setter)]
    fn set___dict__(&self, _value: PyObjectRef, vm: &VirtualMachine) -> PyResult<()> {
        Err(vm.new_attribute_error(format!(
            "attribute '__dict__' of '{}' objects is not writable",
            self.name()
        )))
    }

    #[pygetset(setter)]
    fn set___name__(&self, value: PyObjectRef, vm: &VirtualMachine) -> PyResult<()> {
        self.check_set_special_type_attr(identifier!(vm, __name__), vm)?;
        let name = value.downcast::<PyStr>().map_err(|value| {
            vm.new_type_error(format!(
                "can only assign string to {}.__name__, not '{}'",
                self.slot_name(),
                value.class().slot_name(),
            ))
        })?;
        if name.as_bytes().contains(&0) {
            return Err(vm.new_value_error("type name must not contain null characters"));
        }
        let name = name.try_into_utf8(vm)?;

        let heap_type = self.heaptype_ext.as_ref().ok_or_else(|| {
            vm.new_type_error(format!(
                "cannot set '__name__' attribute of immutable type '{}'",
                self.slot_name()
            ))
        })?;

        // Use std::mem::replace to swap the new value in and get the old value out,
        // then drop the old value after releasing the lock
        let _old_name = {
            let mut name_guard = heap_type.name.write();
            core::mem::replace(&mut *name_guard, name)
        };
        // old_name is dropped here, outside the lock scope

        Ok(())
    }

    #[pygetset]
    fn __text_signature__(&self, vm: &VirtualMachine) -> Option<String> {
        let name = self.name();
        if let Some(text) = self.slots.doc.text
            && let Some(signature) = get_text_signature_from_internal_doc(&name, text)
        {
            return Some(signature.to_string());
        }
        if self.slots.flags.has_feature(PyTypeFlags::HEAPTYPE)
            && let Some(doc_attr) = self.get_direct_attr(identifier!(vm, __doc__))
            && let Some(doc) = doc_attr.downcast_ref::<PyStr>()
            && let Some(doc) = doc.to_str()
            && let Some(signature) = get_text_signature_from_internal_doc(&name, doc)
        {
            return Some(signature.to_string());
        }
        None
    }

    #[pygetset]
    fn __type_params__(&self, vm: &VirtualMachine) -> PyObjectRef {
        let key = identifier!(vm, __type_params__);
        if let Some(params) = self.attributes.get(key)
            // Builtin type namespaces store the getset wrapper under this
            // name; heap types store the actual value.
            && !params.class().is(vm.ctx.types.getset_type)
        {
            return params;
        }
        vm.ctx.empty_tuple.clone().into()
    }

    #[pygetset(setter)]
    fn set___type_params__(&self, value: PySetterValue, vm: &VirtualMachine) -> PyResult<()> {
        let key = identifier!(vm, __type_params__);
        match value {
            PySetterValue::Assign(val) => {
                self.check_set_special_type_attr(key, vm)?;
                let _prev_value = PyType::with_type_lock(vm, || {
                    self.modified_inner();
                    self.attributes.insert(key, val)
                });
            }
            PySetterValue::Delete => {
                return Err(vm.new_type_error("cannot delete '__type_params__'"));
            }
        }
        Ok(())
    }
}

impl SetAttr for PyType {
    fn setattro(
        zelf: &Py<Self>,
        attr_name: &Py<PyStr>,
        value: PySetterValue,
        vm: &VirtualMachine,
    ) -> PyResult<()> {
        let attr_name = vm.ctx.intern_str(attr_name.as_wtf8());
        if zelf.slots().flags.has_feature(PyTypeFlags::IMMUTABLETYPE) {
            return Err(vm.new_type_error(format!(
                "cannot set '{}' attribute of immutable type '{}'",
                attr_name,
                zelf.slot_name()
            )));
        }
        if let Some(attr) = zelf.get_class_attr(attr_name) {
            let descr_set = attr.class().slots().descr_set.load();
            if let Some(descriptor) = descr_set {
                return descriptor(&attr, zelf.to_owned().into(), value, vm);
            }
        }
        let assign = value.is_assign();

        // Drop old value OUTSIDE the type lock to avoid deadlock:
        // dropping may trigger weakref callbacks → method calls →
        // LOAD_ATTR specialization → version_for_specialization → type lock.
        let _prev_value = Self::with_type_lock(vm, || {
            // Invalidate inline caches before modifying attributes.
            // This ensures other threads see the version invalidation before
            // any attribute changes, preventing use-after-free of cached descriptors.
            zelf.modified_inner();

            let prev_value = if let PySetterValue::Assign(value) = value {
                zelf.attributes().insert(attr_name, value)
            } else {
                let prev_value = zelf.attributes().remove(attr_name);
                if prev_value.is_none() {
                    return Err(vm.new_attribute_error(format!(
                        "type object '{}' has no attribute '{}'",
                        zelf.name(),
                        attr_name,
                    )));
                }
                prev_value
            };

            // Keep the slot-table rewrite inside the same transaction as the
            // dict mutation and version invalidation.
            if attr_name.as_wtf8().starts_with("__") && attr_name.as_wtf8().ends_with("__") {
                if assign {
                    zelf.update_slot::<true>(attr_name, &vm.ctx);
                } else {
                    zelf.update_slot::<false>(attr_name, &vm.ctx);
                }
            }
            Ok(prev_value)
        })?;
        Ok(())
    }
}

impl Callable for PyType {
    type Args = FuncArgs;
    fn call(zelf: &Py<Self>, args: FuncArgs, vm: &VirtualMachine) -> PyResult {
        vm_trace!("type_call: {:?}", zelf);

        if zelf.is(vm.ctx.types.type_type) {
            let num_args = args.args.len();
            if num_args == 1 && args.kwargs.is_empty() {
                return Ok(args.args[0].obj_type());
            }
            if num_args != 3 {
                return Err(vm.new_type_error("type() takes 1 or 3 arguments"));
            }
        }

        let Some(slot_new) = zelf.slots().new.load() else {
            return Err(
                vm.new_type_error(format!("cannot create '{}' instances", zelf.slots().name))
            );
        };

        // Both the new and init slots consume args, so the init call gets a
        // separate copy prepared before slot_new runs.
        let init_args = if args.is_empty() {
            // Even cloning empty args costs a kwargs map clone; a default
            // FuncArgs is indistinguishable from such a clone.
            FuncArgs::default()
        } else {
            // Skip the clone when no init call can follow: the class has no
            // init slot, is not `type` itself, and its new slot is a native
            // function. new_wrapper is excluded because a Python `__new__`
            // can install an `__init__` on the class or return an instance
            // of another class while it runs.
            // The address comparison is against the single new_wrapper fn item,
            // so a mismatch is conservative: if it ever compared unequal for the
            // wrapper it would only take the slower cloning path, never the fast
            // path incorrectly.
            if zelf.slots().init.load().is_none()
                && !zelf.is(vm.ctx.types.type_type)
                && crate::types::fn_addr(slot_new)
                    != crate::types::fn_addr(crate::types::new_wrapper as crate::types::NewFunc)
            {
                return slot_new(zelf.to_owned(), args, vm);
            }
            args.clone()
        };

        let obj = slot_new(zelf.to_owned(), args, vm)?;

        if !obj.class().fast_issubclass(zelf) {
            return Ok(obj);
        }

        if let Some(init_method) = obj.class().slots().init.load() {
            init_method(&obj, init_args, vm)?;
        }
        Ok(obj)
    }
}

impl AsNumber for PyType {
    fn as_number() -> &'static PyNumberMethods {
        static AS_NUMBER: PyNumberMethods = PyNumberMethods {
            or: Some(|a, b, vm| or_(a.to_owned(), b.to_owned(), vm)),
            ..PyNumberMethods::NOT_IMPLEMENTED
        };
        &AS_NUMBER
    }
}

impl Representable for PyType {
    #[inline]
    fn repr_str(zelf: &Py<Self>, vm: &VirtualMachine) -> PyResult<String> {
        // A missing `__module__` is not an error here.
        let module = zelf.__module__(vm).ok();
        let module = module
            .as_ref()
            .and_then(|m| m.downcast_ref::<PyStr>())
            .map(|m| m.as_wtf8());

        let repr = match module {
            Some(module) if module != "builtins" => {
                let qualname = zelf.__qualname__(vm);
                let qualname = qualname.downcast_ref::<PyStr>().map(|n| n.as_wtf8());
                let name = zelf.name();
                let qualname = qualname.unwrap_or_else(|| name.as_ref());
                format!("<class '{module}.{qualname}'>")
            }
            _ => format!("<class '{}'>", zelf.slot_name()),
        };
        Ok(repr)
    }
}

// = get_builtin_base_with_dict
fn get_builtin_base_with_dict(typ: &Py<PyType>, vm: &VirtualMachine) -> Option<PyTypeRef> {
    let mut current = Some(typ.to_owned());
    while let Some(t) = current {
        // In CPython: type->tp_dictoffset != 0 && !(type->tp_flags & Py_TPFLAGS_HEAPTYPE)
        // Special case: type itself is a builtin with dict support
        if t.is(vm.ctx.types.type_type) {
            return Some(t);
        }
        // We check HAS_DICT flag (equivalent to tp_dictoffset != 0) and HEAPTYPE
        if t.slots.flags.has_feature(PyTypeFlags::HAS_DICT)
            && !t.slots.flags.has_feature(PyTypeFlags::HEAPTYPE)
        {
            return Some(t);
        }
        current = t.base.load_owned();
    }
    None
}

// = get_dict_descriptor
fn get_dict_descriptor(base: &Py<PyType>, vm: &VirtualMachine) -> Option<PyObjectRef> {
    let dict_attr = identifier!(vm, __dict__);
    // Use _PyType_Lookup (which is lookup_ref in RustPython)
    base.lookup_ref(dict_attr, vm)
}

// = raise_dict_descr_error
fn raise_dict_descriptor_error(obj: &PyObject, vm: &VirtualMachine) -> PyBaseExceptionRef {
    vm.new_type_error(format!(
        "this __dict__ descriptor does not support '{}' objects",
        obj.class().name()
    ))
}

fn subtype_get_dict(obj: PyObjectRef, vm: &VirtualMachine) -> PyResult {
    let base = get_builtin_base_with_dict(obj.class(), vm);

    if let Some(base_type) = base {
        if let Some(descr) = get_dict_descriptor(&base_type, vm) {
            // Call the descriptor's tp_descr_get
            vm.call_get_descriptor(&descr, &obj)
                .unwrap_or_else(|| Err(raise_dict_descriptor_error(&obj, vm)))
        } else {
            Err(raise_dict_descriptor_error(&obj, vm))
        }
    } else {
        // PyObject_GenericGetDict
        object::object_get_dict(obj, vm).map(Into::into)
    }
}

// = subtype_setdict
fn subtype_set_dict(obj: PyObjectRef, value: PySetterValue, vm: &VirtualMachine) -> PyResult<()> {
    let base = get_builtin_base_with_dict(obj.class(), vm);

    if let Some(base_type) = base {
        if let Some(descr) = get_dict_descriptor(&base_type, vm) {
            // Call the descriptor's tp_descr_set
            let descr_set = descr
                .class()
                .slots
                .descr_set
                .load()
                .ok_or_else(|| raise_dict_descriptor_error(&obj, vm))?;
            descr_set(&descr, obj, value, vm)
        } else {
            Err(raise_dict_descriptor_error(&obj, vm))
        }
    } else {
        // _PyObject_SetDict
        object::object_set_dict(obj, value, vm)?;
        Ok(())
    }
}

// subtype_get_weakref
fn subtype_get_weakref(obj: PyObjectRef, vm: &VirtualMachine) -> PyObjectRef {
    // Return the first weakref in the weakref list, or None
    let weakref = obj.get_weakrefs();
    weakref.unwrap_or_else(|| vm.ctx.none())
}

// subtype_set_weakref: __weakref__ is read-only
fn subtype_set_weakref(obj: PyObjectRef, _value: PyObjectRef, vm: &VirtualMachine) -> PyResult<()> {
    Err(vm.new_attribute_error(format!(
        "attribute '__weakref__' of '{}' objects is not writable",
        obj.class().name()
    )))
}

/*
 * The magical type type
 */

/// Vectorcall for PyType (PEP 590).
/// Fast path: type(x) returns x.__class__ without constructing FuncArgs.
///
/// # Implementation note: `slots.vectorcall` dual use
///
/// CPython has three distinct fields on PyTypeObject:
///   - `tp_vectorcall`: constructor fast path (e.g. `list_vectorcall`)
///   - `tp_vectorcall_offset`: per-instance vectorcall for callables (e.g. functions)
///   - `tp_call`: standard call slot
///
/// RustPython collapses the first two into a single `slots.vectorcall`. The
/// `call.is_none()` guard below distinguishes the two uses: callable types have
/// `slots.call` set, so their `slots.vectorcall` is for calling instances,
/// not for construction.
///
/// This heuristic is correct for all current builtins but is not a general
/// solution — `type` itself is both callable and has a constructor vectorcall,
/// handled by the explicit `zelf.is(type_type)` check above the guard.
/// If more such types arise, consider splitting into a dedicated
/// `constructor_vectorcall` slot.
fn vectorcall_type(
    zelf_obj: &PyObject,
    args: Vec<PyObjectRef>,
    nargs: usize,
    kwnames: Option<&[PyObjectRef]>,
    vm: &VirtualMachine,
) -> PyResult {
    let zelf: &Py<PyType> = zelf_obj.downcast_ref().unwrap();

    // type(x) fast path: single positional arg, no kwargs
    if zelf.is(vm.ctx.types.type_type) {
        let no_kwargs = kwnames.is_none_or(|kw| kw.is_empty());
        if nargs == 1 && no_kwargs {
            return Ok(args[0].obj_type());
        }
    } else if zelf.slots().call.load().is_none() && zelf.slots().new.load().is_some() {
        // Per-type constructor vectorcall for non-callable types (dict, list, int, etc.)
        // Also guard on slots.new to avoid dispatching for DISALLOW_INSTANTIATION types.
        if let Some(type_vc) = zelf.slots().vectorcall.load() {
            return type_vc(zelf_obj, args, nargs, kwnames, vm);
        }
    }

    // Fallback: construct FuncArgs and use standard call
    let func_args = FuncArgs::from_vectorcall_owned(args, nargs, kwnames);
    PyType::call(zelf, func_args, vm)
}

pub(crate) fn init(ctx: &'static Context) {
    PyType::extend_class(ctx, ctx.types.type_type);
    ctx.types
        .type_type
        .slots
        .vectorcall
        .store(Some(vectorcall_type));
}

pub(crate) fn call_slot_new(
    typ: &Py<PyType>,
    subtype: PyTypeRef,
    args: FuncArgs,
    vm: &VirtualMachine,
) -> PyResult {
    // Check DISALLOW_INSTANTIATION flag on subtype (the type being instantiated)
    if subtype
        .slots
        .flags
        .has_feature(PyTypeFlags::DISALLOW_INSTANTIATION)
    {
        return Err(vm.new_type_error(format!("cannot create '{}' instances", subtype.slot_name())));
    }

    // "is not safe" check (tp_new_wrapper). Walk past bases whose tp_new is
    // new_wrapper so a Python subclass of a native heap type still reaches
    // that type's tp_new; reject object.__new__(dict) and similar.
    let mut staticbase = subtype.clone();
    while staticbase
        .slots
        .new
        .load()
        .is_some_and(|f| fn_addr(f) == fn_addr(new_wrapper as NewFunc))
    {
        match staticbase.base.load_owned() {
            Some(base) => staticbase = base,
            None => break,
        }
    }

    let typ_new = typ.slots.new.load();
    let staticbase_new = staticbase.slots.new.load();
    if typ_new.map(fn_addr) != staticbase_new.map(fn_addr) {
        return Err(vm.new_type_error(format!(
            "{}.__new__({}) is not safe, use {}.__new__()",
            typ.slot_name(),
            subtype.slot_name(),
            staticbase.slot_name()
        )));
    }

    let slot_new = typ
        .slots
        .new
        .load()
        .expect("Should be able to find a new slot somewhere in the mro");
    slot_new(subtype, args, vm)
}

pub(crate) fn or_(zelf: PyObjectRef, other: PyObjectRef, vm: &VirtualMachine) -> PyResult {
    union_::or_op(zelf, other, vm)
}

fn take_next_base(bases: &mut [Vec<PyTypeRef>]) -> Option<PyTypeRef> {
    for base in bases.iter() {
        let head = base[0].clone();
        if !bases.iter().any(|x| x[1..].iter().any(|x| x.is(&head))) {
            // Remove from other heads.
            for item in bases.iter_mut() {
                if item[0].is(&head) {
                    item.remove(0);
                }
            }

            return Some(head);
        }
    }

    None
}

fn linearise_mro(mut bases: Vec<Vec<PyTypeRef>>) -> Result<Vec<PyTypeRef>, String> {
    vm_trace!("Linearise MRO: {:?}", bases);
    // Python requires that the class direct bases are kept in the same order.
    // This is called local precedence ordering.
    // This means we must verify that for classes A(), B(A) we must reject C(A, B) even though this
    // algorithm will allow the mro ordering of [C, B, A, object].
    // To verify this, we make sure non of the direct bases are in the mro of bases after them.
    for (i, base_mro) in bases.iter().enumerate() {
        let base = &base_mro[0]; // MROs cannot be empty.
        for later_mro in &bases[i + 1..] {
            // We start at index 1 to skip direct bases.
            // This will not catch duplicate bases, but such a thing is already tested for.
            if later_mro[1..].iter().any(|cls| cls.is(base)) {
                return Err(format!(
                    "Cannot create a consistent method resolution order (MRO) for bases {}",
                    bases.iter().map(|x| x.first().unwrap()).format(", ")
                ));
            }
        }
    }

    let mut result = vec![];
    while !bases.is_empty() {
        let head = take_next_base(&mut bases).ok_or_else(|| {
            // Take the head class of each class here. Now that we have reached the problematic bases.
            // Because this failed, we assume the lists cannot be empty.
            format!(
                "Cannot create a consistent method resolution order (MRO) for bases {}",
                bases.iter().map(|x| x.first().unwrap()).format(", ")
            )
        })?;

        result.push(head);

        bases.retain(|x| !x.is_empty());
    }
    Ok(result)
}

fn calculate_meta_class(
    metatype: PyTypeRef,
    bases: &[PyTypeRef],
    vm: &VirtualMachine,
) -> PyResult<PyTypeRef> {
    // = _PyType_CalculateMetaclass
    let mut winner = metatype;
    for base in bases {
        let base_type = base.class();

        // First try fast_issubclass for PyType instances
        if winner.fast_issubclass(base_type) {
            continue;
        } else if base_type.fast_issubclass(&winner) {
            winner = base_type.to_owned();
            continue;
        }

        // If fast_issubclass didn't work, fall back to general is_subclass
        // This handles cases where metaclasses are not PyType subclasses
        let winner_is_subclass = winner.as_object().is_subclass(base_type.as_object(), vm)?;
        if winner_is_subclass {
            continue;
        }

        let base_type_is_subclass = base_type.as_object().is_subclass(winner.as_object(), vm)?;
        if base_type_is_subclass {
            winner = base_type.to_owned();
            continue;
        }

        return Err(vm.new_type_error(
            "metaclass conflict: the metaclass of a derived class must be a (non-strict) subclass \
             of the metaclasses of all its bases",
        ));
    }
    Ok(winner)
}

fn type_is_subtype_base_chain(a: &Py<PyType>, b: &Py<PyType>, vm: &VirtualMachine) -> bool {
    let mut current = Some(a);
    while let Some(typ) = current {
        if typ.is(b) {
            return true;
        }
        current = typ.base.deref();
    }
    b.is(vm.ctx.types.object_type)
}

fn mro_implementation(typ: &Py<PyType>, vm: &VirtualMachine) -> PyResult<Vec<PyTypeRef>> {
    for base in typ.bases.read().as_slice() {
        if base.mro.read().is_empty() {
            return Err(vm.new_type_error(format!(
                "Cannot extend an incomplete type '{}'",
                base.name()
            )));
        }
    }
    let mut mro =
        PyType::resolve_mro(typ.bases.read().as_slice()).map_err(|msg| vm.new_type_error(msg))?;
    mro.insert(0, typ.to_owned());
    Ok(mro)
}

fn mro_check(typ: &Py<PyType>, mro: &[PyObjectRef], vm: &VirtualMachine) -> PyResult<()> {
    let solid = solid_base(typ, vm).to_owned();
    for obj in mro {
        let Some(base) = obj.downcast_ref::<PyType>() else {
            return Err(vm.new_type_error(format!(
                "mro() returned a non-class ('{}')",
                obj.class().name()
            )));
        };
        if !is_subtype_with_mro(&solid.mro.read(), &solid, solid_base(base, vm)) {
            return Err(vm.new_type_error(format!(
                "mro() returned base with unsuitable layout ('{}')",
                base.slot_name()
            )));
        }
    }
    Ok(())
}

fn mro_invoke(typ: &Py<PyType>, vm: &VirtualMachine) -> PyResult<Vec<PyTypeRef>> {
    let custom = !typ.class().is(vm.ctx.types.type_type);
    if !custom {
        return mro_implementation(typ, vm);
    }

    let mro_result = vm.call_special_method(typ.as_object(), identifier!(vm, mro), ())?;
    let items: Vec<PyObjectRef> = mro_result.try_to_value(vm)?;
    if items.is_empty() {
        return Err(vm.new_type_error("type MRO must not be empty"));
    }
    mro_check(typ, &items, vm)?;
    items
        .into_iter()
        .map(|obj| {
            obj.downcast::<PyType>().map_err(|obj| {
                vm.new_type_error(format!(
                    "mro() returned a non-class ('{}')",
                    obj.class().name()
                ))
            })
        })
        .collect()
}

fn mro_internal(typ: &Py<PyType>, vm: &VirtualMachine) -> PyResult<i32> {
    let old_ptr = typ.mro.read().as_ptr();
    let new_mro = mro_invoke(typ, vm)?;
    if typ.mro.read().as_ptr() != old_ptr {
        return Ok(0);
    }
    *typ.mro.write() = new_mro;
    typ.modified();
    Ok(1)
}

/// Returns true if the two types have different instance layouts.
fn shape_differs(t1: &Py<PyType>, t2: &Py<PyType>) -> bool {
    t1.slots.basicsize != t2.slots.basicsize || t1.slots.itemsize != t2.slots.itemsize
}

fn solid_base<'a>(typ: &'a Py<PyType>, vm: &VirtualMachine) -> &'a Py<PyType> {
    let base = if let Some(base) = typ.base.deref() {
        solid_base(base, vm)
    } else {
        vm.ctx.types.object_type
    };

    if shape_differs(typ, base) { typ } else { base }
}

fn best_base<'a>(bases: &'a [PyTypeRef], vm: &VirtualMachine) -> PyResult<&'a Py<PyType>> {
    let mut base: Option<&Py<PyType>> = None;
    let mut winner: Option<&Py<PyType>> = None;

    for base_i in bases {
        // if !base_i.fast_issubclass(vm.ctx.types.type_type) {
        //     println!("base_i type : {}", base_i.name());
        //     return Err(vm.new_type_error("best must be types".into()));
        // }

        if !base_i.slots.flags.has_feature(PyTypeFlags::BASETYPE) {
            return Err(vm.new_type_error(format!(
                "type '{}' is not an acceptable base type",
                base_i.slot_name()
            )));
        }

        let candidate = solid_base(base_i, vm);
        if winner.is_none() {
            winner = Some(candidate);
            base = Some(&**base_i);
        } else if winner.unwrap().fast_issubclass(candidate) {
            // Do nothing
        } else if candidate.fast_issubclass(winner.unwrap()) {
            winner = Some(candidate);
            base = Some(&**base_i);
        } else {
            return Err(vm.new_type_error("multiple bases have instance layout conflict"));
        }
    }

    debug_assert!(base.is_some());
    Ok(base.unwrap())
}

fn type_has_dict(typ: &Py<PyType>) -> bool {
    typ.slots.flags.has_feature(PyTypeFlags::HAS_DICT)
}

fn type_has_weakref(typ: &Py<PyType>) -> bool {
    typ.slots.flags.has_feature(PyTypeFlags::HAS_WEAKREF)
}

/// Returns true if `child` adds no instance layout of its own beyond its base,
/// so the base can stand in for it when comparing object layouts.
fn compatible_with_base(child: &Py<PyType>) -> bool {
    let Some(parent) = child.base.deref() else {
        return false;
    };
    child.slots.basicsize == parent.slots.basicsize
        && child.slots.itemsize == parent.slots.itemsize
        && child.slots.member_count == parent.slots.member_count
        && type_has_dict(child) == type_has_dict(parent)
        && type_has_weakref(child) == type_has_weakref(parent)
}

/// Walk up to the most derived base that actually fixes the instance layout.
fn layout_solid_base(mut typ: &Py<PyType>) -> &Py<PyType> {
    while compatible_with_base(typ) {
        typ = typ.base.deref().unwrap();
    }
    typ
}

/// Returns true if `a` and `b`, which share the same base, added the same
/// instance layout (`__dict__`, `__weakref__`, and `__slots__`).
fn same_slots_added(a: &Py<PyType>, b: &Py<PyType>) -> bool {
    if a.slots.basicsize != b.slots.basicsize
        || a.slots.itemsize != b.slots.itemsize
        || a.slots.member_count != b.slots.member_count
        || type_has_dict(a) != type_has_dict(b)
        || type_has_weakref(a) != type_has_weakref(b)
    {
        return false;
    }
    match (
        a.heaptype_ext.as_ref().and_then(|e| e.slots.as_ref()),
        b.heaptype_ext.as_ref().and_then(|e| e.slots.as_ref()),
    ) {
        (Some(x), Some(y)) => {
            x.as_slice().len() == y.as_slice().len()
                && x.as_slice()
                    .iter()
                    .zip(y.as_slice().iter())
                    .all(|(p, q)| p.as_wtf8() == q.as_wtf8())
        }
        _ => true,
    }
}

/// Validates that instances of `old_to` and `new_to` share an interchangeable
/// object layout, the check `__class__` and `__bases__` assignment perform.
///
/// `attr` names the attribute being assigned for the error message; the
/// message reports `new_to` first and `old_to` second.
pub(crate) fn compatible_for_assignment(
    old_to: &Py<PyType>,
    new_to: &Py<PyType>,
    attr: &str,
    vm: &VirtualMachine,
) -> PyResult<()> {
    let newbase = layout_solid_base(new_to);
    let oldbase = layout_solid_base(old_to);
    let bases_equal = match (newbase.base.deref(), oldbase.base.deref()) {
        (Some(x), Some(y)) => x.is(y),
        (None, None) => true,
        _ => false,
    };
    let compatible = newbase.is(oldbase) || (bases_equal && same_slots_added(newbase, oldbase));
    if compatible {
        return Ok(());
    }
    Err(vm.new_type_error(format!(
        "{attr} assignment: '{}' object layout differs from '{}'",
        new_to.name(),
        old_to.name()
    )))
}

/// Apply Python name mangling for private attributes.
/// `__x` becomes `_ClassName__x` if inside a class.
fn mangle_name(class_name: &str, name: &str) -> String {
    // Only mangle names starting with __ and not ending with __
    if !name.starts_with("__") || name.ends_with("__") || name.contains('.') {
        return name.to_string();
    }
    // Strip leading underscores from class name
    let class_name = class_name.trim_start_matches('_');
    format!("_{class_name}{name}")
}

#[cfg(test)]
mod tests {
    use super::*;

    fn map_ids(obj: Result<Vec<PyTypeRef>, String>) -> Result<Vec<usize>, String> {
        Ok(obj?.into_iter().map(|x| x.get_id()).collect())
    }

    #[test]
    fn linearise() {
        let context = Context::genesis();
        let object = context.types.object_type.to_owned();
        let type_type = context.types.type_type.to_owned();

        let a = PyType::new_heap(
            "A",
            vec![object.clone()],
            PyAttributes::default(),
            Default::default(),
            type_type.clone(),
            context,
        )
        .unwrap();
        let b = PyType::new_heap(
            "B",
            vec![object.clone()],
            PyAttributes::default(),
            Default::default(),
            type_type,
            context,
        )
        .unwrap();

        assert_eq!(
            map_ids(linearise_mro(vec![
                vec![object.clone()],
                vec![object.clone()]
            ])),
            map_ids(Ok(vec![object.clone()]))
        );
        assert_eq!(
            map_ids(linearise_mro(vec![
                vec![a.clone(), object.clone()],
                vec![b.clone(), object.clone()],
            ])),
            map_ids(Ok(vec![a, b, object]))
        );
    }
}