How are you detecting mutability? My understanding is that mutability arises solely through the addition of mutating methods and that in the general case this isn't easily detected.

Also, isn't it a valid pattern to subclass a mutable class like dict and then override the mutating methods to disable them and create an immutable class? IIRC, there are frozendict implementations that do exactly this.

This is about type objects themselves, not instances – e.g. the str type is immutable so you can't set str.foo.
Immutable types have Py_TPFLAGS_IMMUTABLETYPE set.

The C API currently allows creating immutable types from mutable bases

Ah? Would you mind to elaborate? Do you have an example?

Are you talking about defining a heap type which inherits from a heap type or a static type?

type_ready_mro() implements the following check. Does it prevent the issue for static types at least?

    /* All bases of statically allocated type should be statically allocated */
    if (!(type->tp_flags & Py_TPFLAGS_HEAPTYPE)) {
        PyObject *mro = type->tp_mro;
        Py_ssize_t n = PyTuple_GET_SIZE(mro);
        for (Py_ssize_t i = 0; i < n; i++) {
            PyTypeObject *base = _PyType_CAST(PyTuple_GET_ITEM(mro, i));
            if (base->tp_flags & Py_TPFLAGS_HEAPTYPE) {
                PyErr_Format(PyExc_TypeError,
                             "type '%.100s' is not dynamically allocated but "
                             "its base type '%.100s' is dynamically allocated",
                             type->tp_name, base->tp_name);
                return -1;
            }
        }
    }

@vstinner, this test that can serve as an example: https://github.com/python/cpython/pull/95533/files#diff-a537c794ffb51531649e2b81f9ae6978c25077de6aa10c9134576ac628fcc345R629-R654

Yes, static types aren't affected. Only heap types can be mutable.

Py_TPFLAGS_IMMUTABLETYPE was added to simplify the conversion of static types to heap types. Inheriting static types from heap types was forbidden (I do not remember exact reason but it is likely that it was the same reason as of this issue). Perhaps allowing inheriting type with a heap type was Py_TPFLAGS_IMMUTABLETYPE was a mistake. And since it is a new feature, should not we just disallow it instead of emitting a warning?

It's not a new feature any more. I'd rather go through the deprecation cycle than try to prove no one is using this.