rustpython_vm/builtins/

type.rs

use super::{
    PyClassMethod, 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::{
            MemberGetter, MemberKind, MemberSetter, PyDescriptorOwned, PyMemberDef,
            PyMemberDescriptor,
        },
        function::{PyCellRef, PyFunction},
        tuple::{IntoPyTuple, PyTuple},
    },
    class::{PyClassImpl, StaticType},
    common::{
        ascii,
        borrow::BorrowedValue,
        lock::{PyMutex, PyRwLock, PyRwLockReadGuard},
    },
    function::{FuncArgs, KwArgs, OptionalArg, PyMethodDef, PySetterValue},
    object::{Traverse, TraverseFn},
    protocol::{PyIterReturn, PyNumberMethods},
    types::{
        AsNumber, Callable, Constructor, GetAttr, Initializer, PyTypeFlags, PyTypeSlots,
        Representable, SLOT_DEFS, SetAttr, TypeDataRef, TypeDataRefMut, TypeDataSlot,
    },
};
use core::{
    any::Any,
    borrow::Borrow,
    ops::Deref,
    pin::Pin,
    ptr::NonNull,
    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;

#[pyclass(module = false, name = "type", traverse = "manual")]
pub struct PyType {
    pub base: Option<PyTypeRef>,
    pub bases: PyRwLock<Vec<PyTypeRef>>,
    pub mro: PyRwLock<Vec<PyTypeRef>>,
    pub subclasses: PyRwLock<Vec<PyRef<PyWeak>>>,
    pub attributes: PyRwLock<PyAttributes>,
    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`,
/// `assign_version_tag()` 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);

// 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 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);
}

unsafe impl crate::object::Traverse for PyType {
    fn traverse(&self, tracer_fn: &mut crate::object::TraverseFn<'_>) {
        self.base.traverse(tracer_fn);
        self.bases.traverse(tracer_fn);
        self.mro.traverse(tracer_fn);
        self.subclasses.traverse(tracer_fn);
        self.attributes
            .read_recursive()
            .iter()
            .map(|(_, v)| v.traverse(tracer_fn))
            .count();
        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>) {
        if let Some(base) = self.base.take() {
            out.push(base.into());
        }
        if let Some(mut guard) = self.bases.try_write() {
            for base in guard.drain(..) {
                out.push(base.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());
            }
        }
        if let Some(mut guard) = self.attributes.try_write() {
            for (_, val) in guard.drain(..) {
                out.push(val);
            }
        }
        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,
}

pub struct TypeSpecializationCache {
    pub init: PyAtomicRef<Option<PyFunction>>,
    pub getitem: PyAtomicRef<Option<PyFunction>>,
    pub getitem_version: AtomicU32,
    // Serialize cache writes/invalidation similar to CPython's BEGIN_TYPE_LOCK.
    write_lock: PyMutex<()>,
    retired: PyRwLock<Vec<PyObjectRef>>,
}

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

    #[inline]
    fn retire_old_function(&self, old: Option<PyRef<PyFunction>>) {
        if let Some(old) = old {
            self.retired.write().push(old.into());
        }
    }

    #[inline]
    fn swap_init(&self, new_init: Option<PyRef<PyFunction>>, vm: Option<&VirtualMachine>) {
        if let Some(vm) = vm {
            // Keep replaced refs alive for the currently executing frame, matching
            // CPython-style "old pointer remains valid during ongoing execution"
            // without accumulating global retired refs.
            self.init.swap_to_temporary_refs(new_init, vm);
            return;
        }
        // SAFETY: old value is moved to `retired`, so it stays alive while
        // concurrent readers may still hold borrowed references.
        let old = unsafe { self.init.swap(new_init) };
        self.retire_old_function(old);
    }

    #[inline]
    fn swap_getitem(&self, new_getitem: Option<PyRef<PyFunction>>, vm: Option<&VirtualMachine>) {
        if let Some(vm) = vm {
            self.getitem.swap_to_temporary_refs(new_getitem, vm);
            return;
        }
        // SAFETY: old value is moved to `retired`, so it stays alive while
        // concurrent readers may still hold borrowed references.
        let old = unsafe { self.getitem.swap(new_getitem) };
        self.retire_old_function(old);
    }

    #[inline]
    fn invalidate_for_type_modified(&self) {
        let _guard = self.write_lock.lock();
        // _spec_cache contract: type modification invalidates all cached
        // specialization functions.
        self.swap_init(None, None);
        self.swap_getitem(None, None);
    }

    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());
        }
        self.retired
            .read()
            .iter()
            .map(|obj| obj.traverse(tracer_fn))
            .count();
    }

    fn clear_into(&self, out: &mut Vec<PyObjectRef>) {
        let _guard = self.write_lock.lock();
        let old_init = unsafe { self.init.swap(None) };
        if let Some(old_init) = old_init {
            out.push(old_init.into());
        }
        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);
        out.extend(self.retired.write().drain(..));
    }
}

pub struct PointerSlot<T>(NonNull<T>);

unsafe impl<T> Sync for PointerSlot<T> {}
unsafe impl<T> Send for PointerSlot<T> {}

impl<T> PointerSlot<T> {
    pub const unsafe fn borrow_static(&self) -> &'static T {
        unsafe { self.0.as_ref() }
    }
}

impl<T> Clone for PointerSlot<T> {
    fn clone(&self) -> Self {
        *self
    }
}

impl<T> Copy for PointerSlot<T> {}

impl<T> From<&'static T> for PointerSlot<T> {
    fn from(x: &'static T) -> Self {
        Self(NonNull::from(x))
    }
}

impl<T> AsRef<T> for PointerSlot<T> {
    fn as_ref(&self) -> &T {
        unsafe { self.0.as_ref() }
    }
}

pub type PyTypeRef = PyRef<PyType>;

cfg_if::cfg_if! {
    if #[cfg(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 type PyAttributes = IndexMap<&'static PyStrInterned, PyObjectRef, ahash::RandomState>;

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

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
    }
}

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!(
            "can only assign string to __qualname__, not '{}'",
            value.class().name()
        ))),
    }
}

fn is_subtype_with_mro(a_mro: &[PyTypeRef], a: &Py<PyType>, b: &Py<PyType>) -> bool {
    if a.is(b) {
        return true;
    }
    for item in a_mro {
        if item.is(b) {
            return true;
        }
    }
    false
}

impl PyType {
    /// Assign a fresh version tag. Returns 0 if the version counter has been
    /// exhausted, in which case no new cache entries can be created.
    pub fn assign_version_tag(&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().iter() {
            if base.assign_version_tag() == 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;
            }
        }
    }

    /// Invalidate this type's version tag and cascade to all subclasses.
    pub fn modified(&self) {
        if let Some(ext) = self.heaptype_ext.as_ref() {
            ext.specialization_cache.invalidate_for_type_modified();
        }
        // If already invalidated, all subclasses must also be invalidated
        // (guaranteed by the MRO invariant in assign_version_tag).
        let old_version = self.tp_version_tag.load(Ordering::Acquire);
        if old_version == 0 {
            return;
        }
        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);
        let subclasses = self.subclasses.read();
        for weak_ref in subclasses.iter() {
            if let Some(sub) = weak_ref.upgrade() {
                sub.downcast_ref::<PyType>().unwrap().modified();
            }
        }
    }

    pub fn new_simple_heap(
        name: &str,
        base: &Py<PyType>,
        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,
        mut 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 |= 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(),
        };
        let base = bases[0].clone();

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

    /// 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>]) {
        const COLLECTION_FLAGS: PyTypeFlags = PyTypeFlags::from_bits_truncate(
            PyTypeFlags::SEQUENCE.bits() | PyTypeFlags::MAPPING.bits(),
        );

        // If flags are already set, don't override
        if slots.flags.intersects(COLLECTION_FLAGS) {
            return;
        }

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

    /// 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,
    ) {
        const COLLECTION_FLAGS: PyTypeFlags = PyTypeFlags::from_bits_truncate(
            PyTypeFlags::SEQUENCE.bits() | PyTypeFlags::MAPPING.bits(),
        );

        // Don't override if flags are already set
        if slots.flags.intersects(COLLECTION_FLAGS) {
            return;
        }

        // First check in our own attributes
        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);
            slots.flags |= abc_flags & COLLECTION_FLAGS;
            return;
        }

        // Then check in base classes
        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);
                slots.flags |= abc_flags & COLLECTION_FLAGS;
                return;
            }
        }
    }

    #[allow(clippy::too_many_arguments)]
    fn new_heap_inner(
        base: PyRef<Self>,
        bases: Vec<PyRef<Self>>,
        attrs: PyAttributes,
        mut slots: PyTypeSlots,
        heaptype_ext: HeapTypeExt,
        metaclass: PyRef<Self>,
        ctx: &Context,
    ) -> Result<PyRef<Self>, String> {
        let mro = Self::resolve_mro(&bases)?;

        // Inherit HAS_DICT from any base in MRO that has it
        // (not just the first base, as any base with __dict__ means subclass needs it too)
        if mro
            .iter()
            .any(|b| b.slots.flags.has_feature(PyTypeFlags::HAS_DICT))
        {
            slots.flags |= PyTypeFlags::HAS_DICT
        }

        // Inherit HAS_WEAKREF/MANAGED_WEAKREF from any base in MRO that has it
        if mro
            .iter()
            .any(|b| b.slots.flags.has_feature(PyTypeFlags::HAS_WEAKREF))
        {
            slots.flags |= PyTypeFlags::HAS_WEAKREF | PyTypeFlags::MANAGED_WEAKREF
        }

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

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

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

        Self::inherit_readonly_slots(&mut slots, &base);

        // Normalize: any type with HAS_WEAKREF gets MANAGED_WEAKREF
        if slots.flags.has_feature(PyTypeFlags::HAS_WEAKREF) {
            slots.flags |= 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),
                bases: PyRwLock::new(bases),
                mro: PyRwLock::new(mro),
                subclasses: PyRwLock::default(),
                attributes: PyRwLock::new(attrs),
                slots,
                heaptype_ext: Some(Pin::new(Box::new(heaptype_ext))),
                tp_version_tag: AtomicU32::new(0),
            },
            metaclass,
            None,
        );
        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().iter() {
            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 |= PyTypeFlags::HAS_DICT
        }
        if base.slots.flags.has_feature(PyTypeFlags::HAS_WEAKREF) {
            slots.flags |= PyTypeFlags::HAS_WEAKREF | PyTypeFlags::MANAGED_WEAKREF
        }

        // 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;
        }

        Self::inherit_readonly_slots(&mut slots, &base);

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

        let bases = PyRwLock::new(vec![base.clone()]);
        let mro = base.mro_map_collect(|x| x.to_owned());

        let new_type = PyRef::new_ref(
            Self {
                base: Some(base),
                bases,
                mro: PyRwLock::new(mro),
                subclasses: PyRwLock::default(),
                attributes: PyRwLock::new(attrs),
                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.
        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);
        Self::set_alloc(&new_type.slots, &new_type.base);

        let weakref_type = super::PyWeak::static_type();
        for base in new_type.bases.read().iter() {
            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: Vec<_> = self.mro.read()[1..].to_vec();
        for base in mro.iter() {
            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..].iter() {
            for &name in cls.attributes.read().keys() {
                if name.as_bytes().starts_with(b"__") && name.as_bytes().ends_with(b"__") {
                    slot_name_set.insert(name);
                }
            }
        }
        for &name in self.attributes.read().keys() {
            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);
        Self::set_alloc(&self.slots, &self.base);
    }

    fn set_new(slots: &PyTypeSlots, base: &Option<PyTypeRef>) {
        if slots.flags.contains(PyTypeFlags::DISALLOW_INSTANTIATION) {
            slots.new.store(None)
        } else if slots.new.load().is_none() {
            slots.new.store(
                base.as_ref()
                    .map(|base| base.slots.new.load())
                    .unwrap_or(None),
            )
        }
    }

    fn set_alloc(slots: &PyTypeSlots, base: &Option<PyTypeRef>) {
        if slots.alloc.load().is_none() {
            slots.alloc.store(
                base.as_ref()
                    .map(|base| base.slots.alloc.load())
                    .unwrap_or(None),
            );
        }
    }

    /// Inherit readonly slots from base type at creation time.
    /// These slots are not AtomicCell and must be set before the type is used.
    fn inherit_readonly_slots(slots: &mut PyTypeSlots, base: &Self) {
        if slots.as_buffer.is_none() {
            slots.as_buffer = base.slots.as_buffer;
        }
    }

    /// Inherit slots from base type. inherit_slots
    pub(crate) fn inherit_slots(&self, base: &Self) {
        // Use SLOT_DEFS to iterate all slots
        // Note: as_buffer is handled in inherit_readonly_slots (not AtomicCell)
        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.write().insert(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)
    }

    /// 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;
        }
        if self.tp_version_tag.load(Ordering::Acquire) != tp_version {
            return false;
        }
        let _guard = ext.specialization_cache.write_lock.lock();
        if self.tp_version_tag.load(Ordering::Acquire) != tp_version {
            return false;
        }
        ext.specialization_cache.swap_init(Some(init), Some(vm));
        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>> {
        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;
        }
        ext.specialization_cache
            .init
            .to_owned_ordering(Ordering::Acquire)
    }

    /// 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;
        }
        let _guard = ext.specialization_cache.write_lock.lock();
        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), Some(vm));
        ext.specialization_cache
            .getitem_version
            .store(func_version, Ordering::Relaxed);
        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()?;
        // Match CPython check order: pointer (Acquire) then function version.
        let getitem = ext
            .specialization_cache
            .getitem
            .to_owned_ordering(Ordering::Acquire)?;
        let cached_version = ext
            .specialization_cache
            .getitem_version
            .load(Ordering::Relaxed);
        if cached_version == 0 {
            return None;
        }
        Some((getitem, cached_version))
    }

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

    /// find_name_in_mro with method cache (MCACHE).
    /// Looks in tp_dict of types in MRO, bypasses descriptors.
    ///
    /// 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)
    fn find_name_in_mro(&self, name: &'static PyStrInterned) -> Option<PyObjectRef> {
        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 ptr.is_null() {
                    if entry.end_read(seq1) {
                        break;
                    }
                    continue;
                }
                // _Py_TryIncrefCompare-style validation:
                // safe_inc via raw pointer, then ensure source is unchanged.
                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);
                    }
                    drop(cloned);
                    continue;
                }
                break;
            }
        }

        // Assign version BEFORE the MRO walk so that any concurrent
        // modified() call during the walk invalidates this version.
        let assigned = if version == 0 {
            self.assign_version_tag()
        } else {
            version
        };

        // MRO walk
        let result = self.find_name_in_mro_uncached(name);

        // Only cache positive results. Negative results are not cached to
        // avoid stale entries from transient MRO walk failures during
        // concurrent type modifications.
        if let Some(ref found) = result
            && 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();
            // Invalidate first to prevent readers from seeing partial state
            entry.version.store(0, Ordering::Release);
            // Store borrowed pointer (no refcount increment).
            let new_ptr = &**found as *const PyObject as *mut PyObject;
            entry.value.store(new_ptr, Ordering::Relaxed);
            entry.name.store(name_ptr, Ordering::Relaxed);
            // Activate entry — Release ensures value/name writes are visible
            entry.version.store(assigned, Ordering::Release);
            entry.end_write();
        }

        result
    }

    /// Raw MRO walk without cache.
    fn find_name_in_mro_uncached(&self, name: &'static PyStrInterned) -> Option<PyObjectRef> {
        for cls in self.mro.read().iter() {
            if let Some(value) = cls.attributes.read().get(name) {
                return Some(value.clone());
            }
        }
        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.find_name_in_mro(interned_name)
    }

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

    /// 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 {
        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) -> 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() {
            for (name, value) in bc.attributes.read().iter() {
                attributes.insert(name.to_owned(), value.clone());
            }
        }

        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: &PyUtf8StrRef| -> &str {
                    name.as_str()
                })
                .into()
            },
        )
    }

    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: &PyUtf8StrRef| -> &str {
                    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> {
    pub(crate) 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 {
        self.as_object().is(cls.borrow()) || self.mro.read()[1..].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.deref()).map(f).collect()
    }

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

    pub fn iter_base_chain(&self) -> impl Iterator<Item = &Self> {
        core::iter::successors(Some(self), |cls| cls.base.as_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);
        }
    }
}

#[pyclass(
    with(
        Py,
        Constructor,
        Initializer,
        GetAttr,
        SetAttr,
        Callable,
        AsNumber,
        Representable
    ),
    flags(BASETYPE, HAS_DICT, HAS_WEAKREF)
)]
impl PyType {
    #[pygetset]
    fn __bases__(&self, vm: &VirtualMachine) -> PyTupleRef {
        vm.ctx.new_tuple(
            self.bases
                .read()
                .iter()
                .map(|x| x.as_object().to_owned())
                .collect(),
        )
    }
    #[pygetset(setter, name = "__bases__")]
    fn set_bases(zelf: &Py<Self>, bases: Vec<PyTypeRef>, 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.is_empty() {
            return Err(vm.new_type_error(format!(
                "can only assign non-empty tuple to %s.__bases__, not {}",
                zelf.name()
            )));
        }

        // TODO: check for mro cycles

        // TODO: Remove this class from all subclass lists
        // for base in self.bases.read().iter() {
        //     let subclasses = base.subclasses.write();
        //     // TODO: how to uniquely identify the subclasses to remove?
        // }

        *zelf.bases.write() = bases;
        // Recursively update the mros of this class and all subclasses
        fn update_mro_recursively(cls: &PyType, vm: &VirtualMachine) -> PyResult<()> {
            let mut mro =
                PyType::resolve_mro(&cls.bases.read()).map_err(|msg| vm.new_type_error(msg))?;
            // Preserve self (mro[0]) when updating MRO
            mro.insert(0, cls.mro.read()[0].to_owned());
            *cls.mro.write() = mro;
            for subclass in cls.subclasses.write().iter() {
                let subclass = subclass.upgrade().unwrap();
                let subclass: &Py<PyType> = subclass.downcast_ref().unwrap();
                update_mro_recursively(subclass, vm)?;
            }
            Ok(())
        }
        update_mro_recursively(zelf, vm)?;

        // Invalidate inline caches
        zelf.modified();

        // TODO: do any old slots need to be cleaned up first?
        zelf.init_slots(&vm.ctx);

        // Register this type as a subclass of its new bases
        let weakref_type = super::PyWeak::static_type();
        for base in zelf.bases.read().iter() {
            base.subclasses.write().push(
                zelf.as_object()
                    .downgrade_with_weakref_typ_opt(None, weakref_type.to_owned())
                    .unwrap(),
            );
        }

        Ok(())
    }

    #[pygetset]
    fn __base__(&self) -> Option<PyTypeRef> {
        self.base.clone()
    }

    #[pygetset]
    const fn __flags__(&self) -> u64 {
        self.slots.flags.bits()
    }

    #[pygetset]
    fn __basicsize__(&self) -> usize {
        crate::object::SIZEOF_PYOBJECT_HEAD + self.slots.basicsize
    }

    #[pygetset]
    fn __itemsize__(&self) -> usize {
        self.slots.itemsize
    }

    #[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 {
        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()
        }
    }

    #[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 mut attrs = self.attributes.write();
        // First try __annotate__, in case that's been set explicitly
        if let Some(annotate) = attrs.get(identifier!(vm, __annotate__)).cloned() {
            return Ok(annotate);
        }
        // Then try __annotate_func__
        if let Some(annotate) = attrs.get(identifier!(vm, __annotate_func__)).cloned() {
            // TODO: Apply descriptor tp_descr_get if needed
            return Ok(annotate);
        }
        // Set __annotate_func__ = None and return None
        let none = vm.ctx.none();
        attrs.insert(identifier!(vm, __annotate_func__), none.clone());
        Ok(none)
    }

    #[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 mut attrs = self.attributes.write();
        // Clear cached annotations only when setting to a new callable
        if !vm.is_none(&value) {
            attrs.swap_remove(identifier!(vm, __annotations_cache__));
        }
        attrs.insert(identifier!(vm, __annotate_func__), value.clone());

        Ok(())
    }

    #[pygetset]
    fn __annotations__(&self, vm: &VirtualMachine) -> PyResult<PyObjectRef> {
        let attrs = self.attributes.read();
        if let Some(annotations) = attrs.get(identifier!(vm, __annotations__)).cloned() {
            // 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()
                )));
            }
        }
        // Then try __annotations_cache__
        if let Some(annotations) = attrs.get(identifier!(vm, __annotations_cache__)).cloned() {
            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()
            )));
        }
        drop(attrs);

        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()
        };

        // Cache the result in __annotations_cache__
        self.attributes
            .write()
            .insert(identifier!(vm, __annotations_cache__), annotations.clone());
        Ok(annotations)
    }

    #[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 mut attrs = self.attributes.write();
        let has_annotations = attrs.contains_key(identifier!(vm, __annotations__));

        match value {
            crate::function::PySetterValue::Assign(value) => {
                // SET path: store the value (including None)
                let key = if has_annotations {
                    identifier!(vm, __annotations__)
                } else {
                    identifier!(vm, __annotations_cache__)
                };
                attrs.insert(key, value);
                if has_annotations {
                    attrs.swap_remove(identifier!(vm, __annotations_cache__));
                }
            }
            crate::function::PySetterValue::Delete => {
                // DELETE path: remove the key
                let removed = if has_annotations {
                    attrs
                        .swap_remove(identifier!(vm, __annotations__))
                        .is_some()
                } else {
                    attrs
                        .swap_remove(identifier!(vm, __annotations_cache__))
                        .is_some()
                };
                if !removed {
                    return Err(vm.new_attribute_error("__annotations__"));
                }
                if has_annotations {
                    attrs.swap_remove(identifier!(vm, __annotations_cache__));
                }
            }
        }
        attrs.swap_remove(identifier!(vm, __annotate_func__));
        attrs.swap_remove(identifier!(vm, __annotate__));

        Ok(())
    }

    #[pygetset]
    pub fn __module__(&self, vm: &VirtualMachine) -> PyObjectRef {
        self.attributes
            .read()
            .get(identifier!(vm, __module__))
            .cloned()
            // We need to exclude this method from going into recursion:
            .and_then(|found| {
                if found.fast_isinstance(vm.ctx.types.getset_type) {
                    None
                } else {
                    Some(found)
                }
            })
            .unwrap_or_else(|| {
                // For non-heap types, extract module from tp_name (e.g. "typing.TypeAliasType" -> "typing")
                let slot_name = self.slot_name();
                if let Some((module, _)) = slot_name.rsplit_once('.') {
                    vm.ctx.intern_str(module).to_object()
                } else {
                    vm.ctx.new_str(ascii!("builtins")).into()
                }
            })
    }

    #[pygetset(setter)]
    fn set___module__(&self, value: PyObjectRef, vm: &VirtualMachine) -> PyResult<()> {
        self.check_set_special_type_attr(identifier!(vm, __module__), vm)?;
        let mut attributes = self.attributes.write();
        attributes.swap_remove(identifier!(vm, __firstlineno__));
        attributes.insert(identifier!(vm, __module__), value);
        Ok(())
    }

    #[pyclassmethod]
    fn __prepare__(
        _cls: PyTypeRef,
        _name: OptionalArg<PyObjectRef>,
        _bases: OptionalArg<PyObjectRef>,
        _kwargs: KwArgs,
        vm: &VirtualMachine,
    ) -> PyDictRef {
        vm.ctx.new_dict()
    }

    #[pymethod]
    fn __subclasses__(&self) -> PyList {
        let mut subclasses = self.subclasses.write();
        subclasses.retain(|x| x.upgrade().is_some());
        PyList::from(
            subclasses
                .iter()
                .map(|x| x.upgrade().unwrap())
                .collect::<Vec<_>>(),
        )
    }

    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)
    }

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

    #[pygetset(setter)]
    fn set___dict__(&self, _value: PyObjectRef, vm: &VirtualMachine) -> PyResult<()> {
        Err(vm.new_not_implemented_error(
            "Setting __dict__ attribute on a type isn't yet implemented",
        ))
    }

    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(())
    }

    #[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) -> Option<String> {
        self.slots
            .doc
            .and_then(|doc| get_text_signature_from_internal_doc(&self.name(), doc))
            .map(|signature| signature.to_string())
    }

    #[pygetset]
    fn __type_params__(&self, vm: &VirtualMachine) -> PyTupleRef {
        let attrs = self.attributes.read();
        let key = identifier!(vm, __type_params__);
        if let Some(params) = attrs.get(&key)
            && let Ok(tuple) = params.clone().downcast::<PyTuple>()
        {
            return tuple;
        }
        // Return empty tuple if not found or not a tuple
        vm.ctx.empty_tuple.clone()
    }

    #[pygetset(setter)]
    fn set___type_params__(
        &self,
        value: PySetterValue<PyTupleRef>,
        vm: &VirtualMachine,
    ) -> PyResult<()> {
        match value {
            PySetterValue::Assign(ref val) => {
                let key = identifier!(vm, __type_params__);
                self.check_set_special_type_attr(key, vm)?;
                self.modified();
                self.attributes.write().insert(key, val.clone().into());
            }
            PySetterValue::Delete => {
                // For delete, we still need to check if the type is immutable
                if self.slots.flags.has_feature(PyTypeFlags::IMMUTABLETYPE) {
                    return Err(vm.new_type_error(format!(
                        "cannot delete '__type_params__' attribute of immutable type '{}'",
                        self.slot_name()
                    )));
                }
                let key = identifier!(vm, __type_params__);
                self.modified();
                self.attributes.write().shift_remove(&key);
            }
        }
        Ok(())
    }
}

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(vm)?;

        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.is_empty() {
            let base = vm.ctx.types.object_type.to_owned();
            (metatype, base.clone(), vec![base], false)
        } else {
            let bases = bases
                .iter()
                .map(|obj| {
                    obj.clone().downcast::<Self>().or_else(|obj| {
                        if vm
                            .get_attribute_opt(obj, identifier!(vm, __mro_entries__))?
                            .is_some()
                        {
                            Err(vm.new_type_error(
                                "type() doesn't support MRO entry resolution; \
                                 use types.new_class()",
                            ))
                        } else {
                            Err(vm.new_type_error("bases must be types"))
                        }
                    })
                })
                .collect::<PyResult<Vec<_>>>()?;

            // Search the bases for the proper metatype to deal with this:
            let winner = calculate_meta_class(metatype.clone(), &bases, 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, 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);
        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(current_frame) = vm.current_frame() {
            let entry = attributes.entry(identifier!(vm, __module__));
            if matches!(entry, Entry::Vacant(_)) {
                let module_name = vm.unwrap_or_none(
                    current_frame
                        .globals
                        .get_item_opt(identifier!(vm, __name__), vm)?,
                );
                entry.or_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)?
            };

            // Check if base has itemsize > 0 - can't add arbitrary slots to variable-size types
            // Types like int, bytes, tuple have itemsize > 0 and don't allow custom slots
            // But types like weakref.ref have itemsize = 0 and DO allow slots
            let has_custom_slots = slots
                .iter()
                .any(|s| !matches!(s.as_bytes(), b"__dict__" | b"__weakref__"));
            if has_custom_slots && 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.iter() {
                // 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;
                }

                // Check if slot name conflicts with class attributes
                if attributes.contains_key(vm.ctx.intern_str(slot.as_wtf8())) {
                    return Err(vm.new_value_error(format!(
                        "'{}' in __slots__ conflicts with a 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.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)
            let filtered_slots = if has_dict || add_weakref {
                let filtered: Vec<PyStrRef> = slots
                    .iter()
                    .filter(|s| s.as_wtf8() != dict_name && s.as_wtf8() != weakref_name)
                    .cloned()
                    .collect();
                PyTuple::new_ref_typed(filtered, &vm.ctx)
            } else {
                slots
            };

            (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
            .iter()
            .map(|base| base.slots.member_count)
            .max()
            .unwrap();
        let heaptype_member_count = heaptype_slots.as_ref().map(|x| x.len()).unwrap_or(0);
        let member_count: usize = base_member_count + heaptype_member_count;

        let mut flags = PyTypeFlags::heap_type_flags();

        // 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 {
            flags |= PyTypeFlags::HAS_DICT | PyTypeFlags::MANAGED_DICT;
        }

        // Add HAS_WEAKREF if:
        // 1. __slots__ is not defined (automatic weakref support), OR
        // 2. __weakref__ is in __slots__
        let may_add_weakref = !base.slots.flags.has_feature(PyTypeFlags::HAS_WEAKREF);
        if (heaptype_slots.is_none() && may_add_weakref) || add_weakref {
            flags |= PyTypeFlags::HAS_WEAKREF | PyTypeFlags::MANAGED_WEAKREF;
        }

        let (slots, heaptype_ext) = {
            let slots = PyTypeSlots {
                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(),
            };
            (slots, heaptype_ext)
        };

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

        if let Some(ref slots) = heaptype_slots {
            let mut offset = base_member_count;
            let class_name = typ.name().to_string();
            for member in slots.as_slice() {
                // 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,
                    getter: MemberGetter::Offset(offset),
                    setter: MemberSetter::Offset(offset),
                    doc: 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,
                    });
                // __slots__ attributes always get a member descriptor
                // (this overrides any inherited attribute from MRO)
                typ.set_attr(attr_name, member_descriptor.into());
                offset += 1;
            }
        }

        {
            let mut attrs = typ.attributes.write();
            if let Some(cell) = attrs.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()));
                attrs.shift_remove(identifier!(vm, __classcell__));
            }
            if let Some(cell) = attrs.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()
                    ))
                })?;
                cell.set(Some(dict.clone().into()));
                attrs.shift_remove(identifier!(vm, __classdictcell__));
            }
        }

        // 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.read().contains_key(&__dict__));
            if !typ.attributes.read().contains_key(&__dict__) && !has_inherited_dict {
                unsafe {
                    let descriptor =
                        vm.ctx
                            .new_getset("__dict__", &typ, subtype_get_dict, subtype_set_dict);
                    typ.attributes.write().insert(__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.read().contains_key(&__weakref__));
            if !typ.attributes.read().contains_key(&__weakref__) && !has_inherited_weakref {
                unsafe {
                    let descriptor = vm.ctx.new_getset(
                        "__weakref__",
                        &typ,
                        subtype_get_weakref,
                        subtype_set_weakref,
                    );
                    typ.attributes
                        .write()
                        .insert(__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.read().contains_key(&__doc__) {
                typ.attributes.write().insert(__doc__, vm.ctx.none());
            }
        }

        // avoid deadlock
        let attributes = typ
            .attributes
            .read()
            .iter()
            .filter_map(|(name, obj)| {
                vm.get_method(obj.clone(), identifier!(vm, __set_name__))
                    .map(|res| res.map(|meth| (obj.clone(), name.to_owned(), meth)))
            })
            .collect::<PyResult<Vec<_>>>()?;
        for (obj, name, set_name) in attributes {
            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,
                    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()),)));
            })?;
        }

        if let Some(init_subclass) = typ.get_super_attr(identifier!(vm, __init_subclass__)) {
            let init_subclass = vm
                .call_get_descriptor_specific(&init_subclass, None, Some(typ.clone().into()))
                .unwrap_or(Ok(init_subclass))?;
            init_subclass.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_GetDocFromInternalDoc in CPython
fn get_doc_from_internal_doc<'a>(name: &str, internal_doc: &'a str) -> &'a str {
    // Similar to CPython's _PyType_DocWithoutSignature
    // 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
}

impl Initializer for PyType {
    type Args = FuncArgs;

    // type_init
    fn slot_init(_zelf: PyObjectRef, 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: PyRef<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 {
                    let mcl = mcl.to_owned().into();
                    return descr_get(attr.clone(), Some(zelf.to_owned().into()), Some(mcl), 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, None, Some(zelf.to_owned().into()), 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) -> PyTuple {
        let elements: Vec<PyObjectRef> = self.mro_map_collect(|x| x.as_object().to_owned());
        PyTuple::new_unchecked(elements.into_boxed_slice())
    }

    #[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
        if !self.slots.flags.has_feature(PyTypeFlags::HEAPTYPE)
            && let Some(internal_doc) = self.slots.doc
        {
            // Process internal doc, removing signature if present
            let doc_str = get_doc_from_internal_doc(&self.name(), internal_doc);
            return Ok(vm.ctx.new_str(doc_str).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, None, Some(self.to_owned().into()), 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 type '{}'",
                self.name()
            ))
        })?;

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

        // Set the __doc__ in the type's dict
        self.attributes
            .write()
            .insert(identifier!(vm, __doc__), value);

        Ok(())
    }

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

    #[pymethod]
    fn __instancecheck__(&self, obj: PyObjectRef, vm: &VirtualMachine) -> PyResult<bool> {
        // Use real_is_instance to avoid infinite recursion
        obj.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) -> Vec<PyObjectRef> {
        self.mro_map_collect(|cls| cls.to_owned().into())
    }
}

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();

        // 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();

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

        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(())
    }
}

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 obj = if let Some(slot_new) = zelf.slots.new.load() {
            slot_new(zelf.to_owned(), args.clone(), vm)?
        } else {
            return Err(vm.new_type_error(format!("cannot create '{}' instances", zelf.slots.name)));
        };

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

        if let Some(init_method) = obj.class().slots.init.load() {
            init_method(obj.clone(), 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> {
        let module = zelf.__module__(vm);
        let module = module.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.contains(PyTypeFlags::HAS_DICT)
            && !t.slots.flags.contains(PyTypeFlags::HEAPTYPE)
        {
            return Some(t);
        }
        current = t.__base__();
    }
    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.clone())
                .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: 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_set
            let descr_set = descr
                .class()
                .slots
                .descr_set
                .load()
                .ok_or_else(|| raise_dict_descriptor_error(&obj, vm))?;
            descr_set(&descr, obj, PySetterValue::Assign(value), vm)
        } else {
            Err(raise_dict_descriptor_error(&obj, vm))
        }
    } else {
        // PyObject_GenericSetDict
        object::object_set_dict(obj, value.try_into_value(vm)?, vm)?;
        Ok(())
    }
}

// subtype_get_weakref
fn subtype_get_weakref(obj: PyObjectRef, vm: &VirtualMachine) -> PyResult {
    // Return the first weakref in the weakref list, or None
    let weakref = obj.get_weakrefs();
    Ok(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: PyTypeRef,
    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 logic)
    // Check that the user doesn't do something silly and unsafe like
    // object.__new__(dict). To do this, we check that the most derived base
    // that's not a heap type is this type.
    let mut staticbase = subtype.clone();
    while staticbase.slots.flags.has_feature(PyTypeFlags::HEAPTYPE) {
        if let Some(base) = staticbase.base.as_ref() {
            staticbase = base.clone();
        } else {
            break;
        }
    }

    // Check if staticbase's tp_new differs from typ's tp_new
    let typ_new = typ.slots.new.load();
    let staticbase_new = staticbase.slots.new.load();
    if typ_new.map(|f| f as usize) != staticbase_new.map(|f| f as usize) {
        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)
}

/// Returns true if the two types have different instance layouts.
fn shape_differs(t1: &Py<PyType>, t2: &Py<PyType>) -> bool {
    t1.__basicsize__() != t2.__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 {
        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.deref());
        } else if winner.unwrap().fast_issubclass(candidate) {
            // Do nothing
        } else if candidate.fast_issubclass(winner.unwrap()) {
            winner = Some(candidate);
            base = Some(base_i.deref());
        } else {
            return Err(vm.new_type_error("multiple bases have instance layout conflict"));
        }
    }

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

/// 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 test_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]))
        );
    }
}