#include "Python.h"

#include "frameobject.h"

#include "structmember.h"

#include <ctype.h>

#define MCACHE_MAX_ATTR_SIZE 100

#define MCACHE_SIZE_EXP 12

#define MCACHE_HASH(version, name_hash) \

(((unsigned int)(version) ^ (unsigned int)(name_hash)) \

& ((1 << MCACHE_SIZE_EXP) - 1))

#define MCACHE_HASH_METHOD(type, name) \

MCACHE_HASH((type)->tp_version_tag, \

((PyASCIIObject *)(name))->hash)

#define MCACHE_CACHEABLE_NAME(name) \

PyUnicode_CheckExact(name) && \

PyUnicode_READY(name) != -1 && \

PyUnicode_GET_LENGTH(name) <= MCACHE_MAX_ATTR_SIZE

struct method_cache_entry {

};

static struct method_cache_entry method_cache[1 << MCACHE_SIZE_EXP];

static unsigned int next_version_tag = 0;

#define MCACHE_STATS 0

#if MCACHE_STATS

static size_t method_cache_hits = 0;

static size_t method_cache_misses = 0;

static size_t method_cache_collisions = 0;

_Py_IDENTIFIER(__abstractmethods__);

_Py_IDENTIFIER(__class__);

_Py_IDENTIFIER(__delitem__);

_Py_IDENTIFIER(__dict__);

_Py_IDENTIFIER(__doc__);

_Py_IDENTIFIER(__getattribute__);

_Py_IDENTIFIER(__getitem__);

_Py_IDENTIFIER(__hash__);

_Py_IDENTIFIER(__len__);

_Py_IDENTIFIER(__module__);

_Py_IDENTIFIER(__name__);

_Py_IDENTIFIER(__new__);

_Py_IDENTIFIER(__setitem__);

_Py_IDENTIFIER(builtins);

static PyObject *

slot_tp_new(PyTypeObject *type, PyObject *args, PyObject *kwds);

static void

clear_slotdefs(void);

static const char *

find_signature(const char *name, const char *doc)

{

const char *dot;

size_t length;

if (!doc)

return NULL;

assert(name != NULL);

/* for dotted names like classes, only use the last component */

dot = strrchr(name, '.');

if (dot)

name = dot + 1;

length = strlen(name);

if (strncmp(doc, name, length))

return NULL;

doc += length;

if (*doc != '(')

return NULL;

return doc;

}

#define SIGNATURE_END_MARKER ")\n--\n\n"

#define SIGNATURE_END_MARKER_LENGTH 6

static const char *

skip_signature(const char *doc)

{

while (*doc) {

if ((*doc == *SIGNATURE_END_MARKER) &&

!strncmp(doc, SIGNATURE_END_MARKER, SIGNATURE_END_MARKER_LENGTH))

return doc + SIGNATURE_END_MARKER_LENGTH;

if ((*doc == '\n') && (doc[1] == '\n'))

return NULL;

doc++;

}

return NULL;

}

static const char *

_PyType_DocWithoutSignature(const char *name, const char *internal_doc)

{

const char *doc = find_signature(name, internal_doc);

if (doc) {

doc = skip_signature(doc);

if (doc)

return doc;

}

return internal_doc;

}

PyObject *

_PyType_GetDocFromInternalDoc(const char *name, const char *internal_doc)

{

const char *doc = _PyType_DocWithoutSignature(name, internal_doc);

if (!doc || *doc == '\0') {

Py_INCREF(Py_None);

return Py_None;

}

return PyUnicode_FromString(doc);

}

PyObject *

_PyType_GetTextSignatureFromInternalDoc(const char *name, const char *internal_doc)

{

const char *start = find_signature(name, internal_doc);

const char *end;

if (start)

end = skip_signature(start);

else

end = NULL;

if (!end) {

Py_INCREF(Py_None);

return Py_None;

}

/* back "end" up until it points just past the final ')' */

end -= SIGNATURE_END_MARKER_LENGTH - 1;

assert((end - start) >= 2); /* should be "()" at least */

assert(end[-1] == ')');

assert(end[0] == '\n');

return PyUnicode_FromStringAndSize(start, end - start);

}

PyType_ClearCache(void)

{

Py_ssize_t i;

unsigned int cur_version_tag = next_version_tag - 1;

#if MCACHE_STATS

size_t total = method_cache_hits + method_cache_collisions + method_cache_misses;

fprintf(stderr, "-- Method cache hits = %zd (%d%%)\n",

method_cache_hits, (int) (100.0 * method_cache_hits / total));

fprintf(stderr, "-- Method cache true misses = %zd (%d%%)\n",

method_cache_misses, (int) (100.0 * method_cache_misses / total));

fprintf(stderr, "-- Method cache collisions = %zd (%d%%)\n",

method_cache_collisions, (int) (100.0 * method_cache_collisions / total));

fprintf(stderr, "-- Method cache size = %zd KB\n",

sizeof(method_cache) / 1024);

for (i = 0; i < (1 << MCACHE_SIZE_EXP); i++) {

method_cache[i].version = 0;

Py_CLEAR(method_cache[i].name);

method_cache[i].value = NULL;

}

next_version_tag = 0;

/* mark all version tags as invalid */

PyType_Modified(&PyBaseObject_Type);

return cur_version_tag;

}

_PyType_Fini(void)

{

PyType_ClearCache();

clear_slotdefs();

}

PyType_Modified(PyTypeObject *type)

{

/* Invalidate any cached data for the specified type and all

PyObject *raw, *ref;

Py_ssize_t i;

if (!PyType_HasFeature(type, Py_TPFLAGS_VALID_VERSION_TAG))

return;

raw = type->tp_subclasses;

if (raw != NULL) {

assert(PyDict_CheckExact(raw));

i = 0;

while (PyDict_Next(raw, &i, NULL, &ref)) {

assert(PyWeakref_CheckRef(ref));

ref = PyWeakref_GET_OBJECT(ref);

if (ref != Py_None) {

PyType_Modified((PyTypeObject *)ref);

}

}

}

type->tp_flags &= ~Py_TPFLAGS_VALID_VERSION_TAG;

}

static void

type_mro_modified(PyTypeObject *type, PyObject *bases) {

/*

Py_ssize_t i, n;

int clear = 0;

if (!PyType_HasFeature(type, Py_TPFLAGS_HAVE_VERSION_TAG))

return;

n = PyTuple_GET_SIZE(bases);

for (i = 0; i < n; i++) {

PyObject *b = PyTuple_GET_ITEM(bases, i);

PyTypeObject *cls;

assert(PyType_Check(b));

cls = (PyTypeObject *)b;

if (!PyType_HasFeature(cls, Py_TPFLAGS_HAVE_VERSION_TAG) ||

!PyType_IsSubtype(type, cls)) {

clear = 1;

break;

}

}

if (clear)

type->tp_flags &= ~(Py_TPFLAGS_HAVE_VERSION_TAG|

Py_TPFLAGS_VALID_VERSION_TAG);

}

static int

assign_version_tag(PyTypeObject *type)

{

/* Ensure that the tp_version_tag is valid and set

Py_ssize_t i, n;

PyObject *bases;

if (PyType_HasFeature(type, Py_TPFLAGS_VALID_VERSION_TAG))

return 1;

if (!PyType_HasFeature(type, Py_TPFLAGS_HAVE_VERSION_TAG))

return 0;

if (!PyType_HasFeature(type, Py_TPFLAGS_READY))

return 0;

type->tp_version_tag = next_version_tag++;

/* for stress-testing: next_version_tag &= 0xFF; */

if (type->tp_version_tag == 0) {

/* wrap-around or just starting Python - clear the whole

for (i = 0; i < (1 << MCACHE_SIZE_EXP); i++) {

method_cache[i].value = NULL;

Py_INCREF(Py_None);

Py_XSETREF(method_cache[i].name, Py_None);

}

/* mark all version tags as invalid */

PyType_Modified(&PyBaseObject_Type);

return 1;

}

bases = type->tp_bases;

n = PyTuple_GET_SIZE(bases);

for (i = 0; i < n; i++) {

PyObject *b = PyTuple_GET_ITEM(bases, i);

assert(PyType_Check(b));

if (!assign_version_tag((PyTypeObject *)b))

return 0;

}

type->tp_flags |= Py_TPFLAGS_VALID_VERSION_TAG;

return 1;

}

static PyMemberDef type_members[] = {

{"__basicsize__", T_PYSSIZET, offsetof(PyTypeObject,tp_basicsize),READONLY},

{"__itemsize__", T_PYSSIZET, offsetof(PyTypeObject, tp_itemsize), READONLY},

{"__flags__", T_LONG, offsetof(PyTypeObject, tp_flags), READONLY},

{"__weakrefoffset__", T_LONG,

offsetof(PyTypeObject, tp_weaklistoffset), READONLY},

{"__base__", T_OBJECT, offsetof(PyTypeObject, tp_base), READONLY},

{"__dictoffset__", T_LONG,

offsetof(PyTypeObject, tp_dictoffset), READONLY},

{"__mro__", T_OBJECT, offsetof(PyTypeObject, tp_mro), READONLY},

{0}

};

static int

check_set_special_type_attr(PyTypeObject *type, PyObject *value, const char *name)

{

if (!(type->tp_flags & Py_TPFLAGS_HEAPTYPE)) {

PyErr_Format(PyExc_TypeError,

"can't set %s.%s", type->tp_name, name);

return 0;

}

if (!value) {

PyErr_Format(PyExc_TypeError,

"can't delete %s.%s", type->tp_name, name);

return 0;

}

return 1;

}

static PyObject *

type_name(PyTypeObject *type, void *context)

{

const char *s;

if (type->tp_flags & Py_TPFLAGS_HEAPTYPE) {

PyHeapTypeObject* et = (PyHeapTypeObject*)type;

Py_INCREF(et->ht_name);

return et->ht_name;

}

else {

s = strrchr(type->tp_name, '.');

if (s == NULL)

s = type->tp_name;

else

s++;

return PyUnicode_FromString(s);

}

}

static PyObject *

type_qualname(PyTypeObject *type, void *context)

{

if (type->tp_flags & Py_TPFLAGS_HEAPTYPE) {

PyHeapTypeObject* et = (PyHeapTypeObject*)type;

Py_INCREF(et->ht_qualname);

return et->ht_qualname;

}

else {

return type_name(type, context);

}

}

static int

type_set_name(PyTypeObject *type, PyObject *value, void *context)

{

const char *tp_name;

Py_ssize_t name_size;

if (!check_set_special_type_attr(type, value, "__name__"))

return -1;

if (!PyUnicode_Check(value)) {

PyErr_Format(PyExc_TypeError,

"can only assign string to %s.__name__, not '%s'",

type->tp_name, Py_TYPE(value)->tp_name);

return -1;

}

tp_name = PyUnicode_AsUTF8AndSize(value, &name_size);

if (tp_name == NULL)

return -1;

if (strlen(tp_name) != (size_t)name_size) {

PyErr_SetString(PyExc_ValueError,

"type name must not contain null characters");

return -1;

}

type->tp_name = tp_name;

Py_INCREF(value);

Py_SETREF(((PyHeapTypeObject*)type)->ht_name, value);

return 0;

}

static int

type_set_qualname(PyTypeObject *type, PyObject *value, void *context)

{

PyHeapTypeObject* et;

if (!check_set_special_type_attr(type, value, "__qualname__"))

return -1;

if (!PyUnicode_Check(value)) {

PyErr_Format(PyExc_TypeError,

"can only assign string to %s.__qualname__, not '%s'",

type->tp_name, Py_TYPE(value)->tp_name);

return -1;

}

et = (PyHeapTypeObject*)type;

Py_INCREF(value);

Py_SETREF(et->ht_qualname, value);

return 0;

}

static PyObject *

type_module(PyTypeObject *type, void *context)

{

char *s;

if (type->tp_flags & Py_TPFLAGS_HEAPTYPE) {

PyObject *mod = _PyDict_GetItemId(type->tp_dict, &PyId___module__);

if (!mod) {

PyErr_Format(PyExc_AttributeError, "__module__");

return 0;

}

Py_XINCREF(mod);

return mod;

}

else {

PyObject *name;

s = strrchr(type->tp_name, '.');

if (s != NULL)

return PyUnicode_FromStringAndSize(

type->tp_name, (Py_ssize_t)(s - type->tp_name));

name = _PyUnicode_FromId(&PyId_builtins);

Py_XINCREF(name);

return name;

}

}

static int

type_set_module(PyTypeObject *type, PyObject *value, void *context)

{

if (!check_set_special_type_attr(type, value, "__module__"))

return -1;

PyType_Modified(type);

return _PyDict_SetItemId(type->tp_dict, &PyId___module__, value);

}

static PyObject *

type_abstractmethods(PyTypeObject *type, void *context)

{

PyObject *mod = NULL;

/* type itself has an __abstractmethods__ descriptor (this). Don't return

if (type != &PyType_Type)

mod = _PyDict_GetItemId(type->tp_dict, &PyId___abstractmethods__);

if (!mod) {

PyObject *message = _PyUnicode_FromId(&PyId___abstractmethods__);

if (message)

PyErr_SetObject(PyExc_AttributeError, message);

return NULL;

}

Py_XINCREF(mod);

return mod;

}

static int

type_set_abstractmethods(PyTypeObject *type, PyObject *value, void *context)

{

/* __abstractmethods__ should only be set once on a type, in

int abstract, res;

if (value != NULL) {

abstract = PyObject_IsTrue(value);

if (abstract < 0)

return -1;

res = _PyDict_SetItemId(type->tp_dict, &PyId___abstractmethods__, value);

}

else {

abstract = 0;

res = _PyDict_DelItemId(type->tp_dict, &PyId___abstractmethods__);

if (res && PyErr_ExceptionMatches(PyExc_KeyError)) {

PyObject *message = _PyUnicode_FromId(&PyId___abstractmethods__);

if (message)

PyErr_SetObject(PyExc_AttributeError, message);

return -1;

}

}

if (res == 0) {

PyType_Modified(type);

if (abstract)

type->tp_flags |= Py_TPFLAGS_IS_ABSTRACT;

else

type->tp_flags &= ~Py_TPFLAGS_IS_ABSTRACT;

}

return res;

}

static PyObject *

type_get_bases(PyTypeObject *type, void *context)

{

Py_INCREF(type->tp_bases);

return type->tp_bases;

}

static PyTypeObject *best_base(PyObject *);

static int mro_internal(PyTypeObject *, PyObject **);

Py_LOCAL_INLINE(int) type_is_subtype_base_chain(PyTypeObject *, PyTypeObject *);

static int compatible_for_assignment(PyTypeObject *, PyTypeObject *, char *);

static int add_subclass(PyTypeObject*, PyTypeObject*);

static int add_all_subclasses(PyTypeObject *type, PyObject *bases);

static void remove_subclass(PyTypeObject *, PyTypeObject *);

static void remove_all_subclasses(PyTypeObject *type, PyObject *bases);

static void update_all_slots(PyTypeObject *);

typedef int (*update_callback)(PyTypeObject *, void *);

static int update_subclasses(PyTypeObject *type, PyObject *name,

update_callback callback, void *data);

static int recurse_down_subclasses(PyTypeObject *type, PyObject *name,

update_callback callback, void *data);

static PyObject *type_subclasses(PyTypeObject *type, PyObject *ignored);

static int

mro_hierarchy(PyTypeObject *type, PyObject *temp)

{

int res;

PyObject *new_mro, *old_mro;

PyObject *tuple;

PyObject *subclasses;

Py_ssize_t i, n;

res = mro_internal(type, &old_mro);

if (res <= 0)

/* error / reentrance */

return res;

new_mro = type->tp_mro;

if (old_mro != NULL)

tuple = PyTuple_Pack(3, type, new_mro, old_mro);

else

tuple = PyTuple_Pack(2, type, new_mro);

if (tuple != NULL)

res = PyList_Append(temp, tuple);

else

res = -1;

Py_XDECREF(tuple);

if (res < 0) {

type->tp_mro = old_mro;

Py_DECREF(new_mro);

return -1;

}

Py_XDECREF(old_mro);

/* Obtain a copy of subclasses list to iterate over.

subclasses = type_subclasses(type, NULL);

if (subclasses == NULL)

return -1;

n = PyList_GET_SIZE(subclasses);

for (i = 0; i < n; i++) {

PyTypeObject *subclass;

subclass = (PyTypeObject *)PyList_GET_ITEM(subclasses, i);

res = mro_hierarchy(subclass, temp);

if (res < 0)

break;

}

Py_DECREF(subclasses);

return res;

}

static int

type_set_bases(PyTypeObject *type, PyObject *new_bases, void *context)

{

int res = 0;

PyObject *temp;

PyObject *old_bases;

PyTypeObject *new_base, *old_base;

Py_ssize_t i;

if (!check_set_special_type_attr(type, new_bases, "__bases__"))

return -1;

if (!PyTuple_Check(new_bases)) {

PyErr_Format(PyExc_TypeError,

"can only assign tuple to %s.__bases__, not %s",

type->tp_name, Py_TYPE(new_bases)->tp_name);

return -1;

}

if (PyTuple_GET_SIZE(new_bases) == 0) {

PyErr_Format(PyExc_TypeError,

"can only assign non-empty tuple to %s.__bases__, not ()",

type->tp_name);

return -1;

}

for (i = 0; i < PyTuple_GET_SIZE(new_bases); i++) {

PyObject *ob;

PyTypeObject *base;

ob = PyTuple_GET_ITEM(new_bases, i);

if (!PyType_Check(ob)) {

PyErr_Format(PyExc_TypeError,

"%s.__bases__ must be tuple of classes, not '%s'",

type->tp_name, Py_TYPE(ob)->tp_name);

return -1;

}

base = (PyTypeObject*)ob;

if (PyType_IsSubtype(base, type) ||

/* In case of reentering here again through a custom mro()

(base->tp_mro != NULL && type_is_subtype_base_chain(base, type))) {

PyErr_SetString(PyExc_TypeError,

"a __bases__ item causes an inheritance cycle");

return -1;

}

}

new_base = best_base(new_bases);

if (new_base == NULL)

return -1;

if (!compatible_for_assignment(type->tp_base, new_base, "__bases__"))

return -1;

Py_INCREF(new_bases);

Py_INCREF(new_base);

old_bases = type->tp_bases;

old_base = type->tp_base;

type->tp_bases = new_bases;

type->tp_base = new_base;

temp = PyList_New(0);

if (temp == NULL)

goto bail;

if (mro_hierarchy(type, temp) < 0)

goto undo;

Py_DECREF(temp);

/* Take no action in case if type->tp_bases has been replaced

if (type->tp_bases == new_bases) {

/* any base that was in __bases__ but now isn't, we

/* for now, sod that: just remove from all old_bases,

remove_all_subclasses(type, old_bases);

res = add_all_subclasses(type, new_bases);

update_all_slots(type);

}

Py_DECREF(old_bases);

Py_DECREF(old_base);

return res;

undo:

for (i = PyList_GET_SIZE(temp) - 1; i >= 0; i--) {

PyTypeObject *cls;

PyObject *new_mro, *old_mro = NULL;

PyArg_UnpackTuple(PyList_GET_ITEM(temp, i),

"", 2, 3, &cls, &new_mro, &old_mro);

/* Do not rollback if cls has a newer version of MRO. */

if (cls->tp_mro == new_mro) {

Py_XINCREF(old_mro);

cls->tp_mro = old_mro;

Py_DECREF(new_mro);

}

}

Py_DECREF(temp);

bail:

if (type->tp_bases == new_bases) {

assert(type->tp_base == new_base);

type->tp_bases = old_bases;

type->tp_base = old_base;

Py_DECREF(new_bases);

Py_DECREF(new_base);

}

else {

Py_DECREF(old_bases);

Py_DECREF(old_base);

}

return -1;

}

static PyObject *

type_dict(PyTypeObject *type, void *context)

{

if (type->tp_dict == NULL) {

Py_INCREF(Py_None);

return Py_None;

}

return PyDictProxy_New(type->tp_dict);

}

static PyObject *

type_get_doc(PyTypeObject *type, void *context)

{

PyObject *result;

if (!(type->tp_flags & Py_TPFLAGS_HEAPTYPE) && type->tp_doc != NULL) {

return _PyType_GetDocFromInternalDoc(type->tp_name, type->tp_doc);

}

result = _PyDict_GetItemId(type->tp_dict, &PyId___doc__);

if (result == NULL) {

result = Py_None;

Py_INCREF(result);

}

else if (Py_TYPE(result)->tp_descr_get) {

result = Py_TYPE(result)->tp_descr_get(result, NULL,

(PyObject *)type);

}

else {

Py_INCREF(result);

}

return result;

}

static PyObject *

type_get_text_signature(PyTypeObject *type, void *context)

{

return _PyType_GetTextSignatureFromInternalDoc(type->tp_name, type->tp_doc);

}

static int

type_set_doc(PyTypeObject *type, PyObject *value, void *context)

{

if (!check_set_special_type_attr(type, value, "__doc__"))

return -1;

PyType_Modified(type);

return _PyDict_SetItemId(type->tp_dict, &PyId___doc__, value);

}

static PyObject *

type___instancecheck__(PyObject *type, PyObject *inst)

{

switch (_PyObject_RealIsInstance(inst, type)) {

case -1:

return NULL;

case 0:

Py_RETURN_FALSE;

default:

Py_RETURN_TRUE;

}

}

static PyObject *

type___subclasscheck__(PyObject *type, PyObject *inst)

{

switch (_PyObject_RealIsSubclass(inst, type)) {

case -1:

return NULL;

case 0:

Py_RETURN_FALSE;

default:

Py_RETURN_TRUE;

}

}

static PyGetSetDef type_getsets[] = {

{"__name__", (getter)type_name, (setter)type_set_name, NULL},

{"__qualname__", (getter)type_qualname, (setter)type_set_qualname, NULL},

{"__bases__", (getter)type_get_bases, (setter)type_set_bases, NULL},

{"__module__", (getter)type_module, (setter)type_set_module, NULL},

{"__abstractmethods__", (getter)type_abstractmethods,

(setter)type_set_abstractmethods, NULL},

{"__dict__", (getter)type_dict, NULL, NULL},

{"__doc__", (getter)type_get_doc, (setter)type_set_doc, NULL},

{"__text_signature__", (getter)type_get_text_signature, NULL, NULL},

{0}

};

static PyObject *

type_repr(PyTypeObject *type)

{

PyObject *mod, *name, *rtn;

mod = type_module(type, NULL);

if (mod == NULL)

PyErr_Clear();

else if (!PyUnicode_Check(mod)) {

Py_DECREF(mod);

mod = NULL;

}

name = type_qualname(type, NULL);

if (name == NULL) {

Py_XDECREF(mod);

return NULL;

}

if (mod != NULL && !_PyUnicode_EqualToASCIIId(mod, &PyId_builtins))

rtn = PyUnicode_FromFormat("<class '%U.%U'>", mod, name);

else

rtn = PyUnicode_FromFormat("<class '%s'>", type->tp_name);

Py_XDECREF(mod);

Py_DECREF(name);

return rtn;

}

static PyObject *

type_call(PyTypeObject *type, PyObject *args, PyObject *kwds)

{

PyObject *obj;

if (type->tp_new == NULL) {

PyErr_Format(PyExc_TypeError,

"cannot create '%.100s' instances",

type->tp_name);

return NULL;

}

#ifdef Py_DEBUG

/* type_call() must not be called with an exception set,

assert(!PyErr_Occurred());

obj = type->tp_new(type, args, kwds);

if (obj != NULL) {

/* Ugly exception: when the call was type(something),

if (type == &PyType_Type &&

PyTuple_Check(args) && PyTuple_GET_SIZE(args) == 1 &&

(kwds == NULL ||

(PyDict_Check(kwds) && PyDict_Size(kwds) == 0)))

return obj;

/* If the returned object is not an instance of type,

if (!PyType_IsSubtype(Py_TYPE(obj), type))

return obj;

type = Py_TYPE(obj);

if (type->tp_init != NULL) {

int res = type->tp_init(obj, args, kwds);

if (res < 0) {

Py_DECREF(obj);

obj = NULL;

}

}

}

return obj;

}

PyObject *

PyType_GenericAlloc(PyTypeObject *type, Py_ssize_t nitems)

{

PyObject *obj;

const size_t size = _PyObject_VAR_SIZE(type, nitems+1);

/* note that we need to add one, for the sentinel */

if (PyType_IS_GC(type))

obj = _PyObject_GC_Malloc(size);

else

obj = (PyObject *)PyObject_MALLOC(size);

if (obj == NULL)

return PyErr_NoMemory();

memset(obj, '\0', size);

if (type->tp_flags & Py_TPFLAGS_HEAPTYPE)

Py_INCREF(type);

if (type->tp_itemsize == 0)

(void)PyObject_INIT(obj, type);

else

(void) PyObject_INIT_VAR((PyVarObject *)obj, type, nitems);

if (PyType_IS_GC(type))

_PyObject_GC_TRACK(obj);

return obj;

}

PyObject *

PyType_GenericNew(PyTypeObject *type, PyObject *args, PyObject *kwds)

{

return type->tp_alloc(type, 0);

}

static int

traverse_slots(PyTypeObject *type, PyObject *self, visitproc visit, void *arg)

{

Py_ssize_t i, n;

PyMemberDef *mp;

n = Py_SIZE(type);

mp = PyHeapType_GET_MEMBERS((PyHeapTypeObject *)type);

for (i = 0; i < n; i++, mp++) {

if (mp->type == T_OBJECT_EX) {

char *addr = (char *)self + mp->offset;

PyObject *obj = *(PyObject **)addr;

if (obj != NULL) {

int err = visit(obj, arg);

if (err)

return err;

}

}

}

return 0;

}

static int

subtype_traverse(PyObject *self, visitproc visit, void *arg)

{

PyTypeObject *type, *base;

traverseproc basetraverse;

/* Find the nearest base with a different tp_traverse,

type = Py_TYPE(self);

base = type;

while ((basetraverse = base->tp_traverse) == subtype_traverse) {

if (Py_SIZE(base)) {

int err = traverse_slots(base, self, visit, arg);

if (err)

return err;

}

base = base->tp_base;

assert(base);

}

if (type->tp_dictoffset != base->tp_dictoffset) {

PyObject **dictptr = _PyObject_GetDictPtr(self);

if (dictptr && *dictptr)

Py_VISIT(*dictptr);

}