Python-2.7.3/Objects/typeobject.c

Location Tool Test ID Function Issue
/builddir/build/BUILD/Python-2.7.3/Objects/typeobject.c:4737:22 clang-analyzer Access to field 'tp_name' results in a dereference of a null pointer (loaded from variable 'type')
/builddir/build/BUILD/Python-2.7.3/Objects/typeobject.c:4737:22 clang-analyzer Access to field 'tp_name' results in a dereference of a null pointer (loaded from variable 'type')
/builddir/build/BUILD/Python-2.7.3/Objects/typeobject.c:4744:22 clang-analyzer Access to field 'tp_name' results in a dereference of a null pointer (loaded from variable 'type')
/builddir/build/BUILD/Python-2.7.3/Objects/typeobject.c:4744:22 clang-analyzer Access to field 'tp_name' results in a dereference of a null pointer (loaded from variable 'type')
/builddir/build/BUILD/Python-2.7.3/Objects/typeobject.c:4752:22 clang-analyzer Access to field 'tp_name' results in a dereference of a null pointer (loaded from variable 'type')
/builddir/build/BUILD/Python-2.7.3/Objects/typeobject.c:4752:22 clang-analyzer Access to field 'tp_name' results in a dereference of a null pointer (loaded from variable 'type')
/builddir/build/BUILD/Python-2.7.3/Objects/typeobject.c:4767:45 clang-analyzer Access to field 'tp_new' results in a dereference of a null pointer (loaded from variable 'type')
/builddir/build/BUILD/Python-2.7.3/Objects/typeobject.c:4767:45 clang-analyzer Access to field 'tp_new' results in a dereference of a null pointer (loaded from variable 'type')
/builddir/build/BUILD/Python-2.7.3/Objects/typeobject.c:4779:11 clang-analyzer Access to field 'tp_new' results in a dereference of a null pointer (loaded from variable 'type')
/builddir/build/BUILD/Python-2.7.3/Objects/typeobject.c:4779:11 clang-analyzer Access to field 'tp_new' results in a dereference of a null pointer (loaded from variable 'type')
/builddir/build/BUILD/Python-2.7.3/Objects/typeobject.c:6041:23 clang-analyzer Access to field 'tp_as_sequence' results in a dereference of a null pointer (loaded from variable 'type')
/builddir/build/BUILD/Python-2.7.3/Objects/typeobject.c:6045:23 clang-analyzer Access to field 'tp_as_mapping' results in a dereference of a null pointer (loaded from variable 'type')
/builddir/build/BUILD/Python-2.7.3/Objects/typeobject.c:6049:23 clang-analyzer Access to field 'tp_as_number' results in a dereference of a null pointer (loaded from variable 'type')
   1 /* Type object implementation */
   2 
   3 #include "Python.h"
   4 #include "structmember.h"
   5 
   6 #include <ctype.h>
   7 
   8 
   9 /* Support type attribute cache */
  10 
  11 /* The cache can keep references to the names alive for longer than
  12    they normally would.  This is why the maximum size is limited to
  13    MCACHE_MAX_ATTR_SIZE, since it might be a problem if very large
  14    strings are used as attribute names. */
  15 #define MCACHE_MAX_ATTR_SIZE    100
  16 #define MCACHE_SIZE_EXP         10
  17 #define MCACHE_HASH(version, name_hash)                                 \
  18         (((unsigned int)(version) * (unsigned int)(name_hash))          \
  19          >> (8*sizeof(unsigned int) - MCACHE_SIZE_EXP))
  20 #define MCACHE_HASH_METHOD(type, name)                                  \
  21         MCACHE_HASH((type)->tp_version_tag,                     \
  22                     ((PyStringObject *)(name))->ob_shash)
  23 #define MCACHE_CACHEABLE_NAME(name)                                     \
  24         PyString_CheckExact(name) &&                            \
  25         PyString_GET_SIZE(name) <= MCACHE_MAX_ATTR_SIZE
  26 
  27 struct method_cache_entry {
  28     unsigned int version;
  29     PyObject *name;             /* reference to exactly a str or None */
  30     PyObject *value;            /* borrowed */
  31 };
  32 
  33 static struct method_cache_entry method_cache[1 << MCACHE_SIZE_EXP];
  34 static unsigned int next_version_tag = 0;
  35 
  36 unsigned int
  37 PyType_ClearCache(void)
  38 {
  39     Py_ssize_t i;
  40     unsigned int cur_version_tag = next_version_tag - 1;
  41 
  42     for (i = 0; i < (1 << MCACHE_SIZE_EXP); i++) {
  43         method_cache[i].version = 0;
  44         Py_CLEAR(method_cache[i].name);
  45         method_cache[i].value = NULL;
  46     }
  47     next_version_tag = 0;
  48     /* mark all version tags as invalid */
  49     PyType_Modified(&PyBaseObject_Type);
  50     return cur_version_tag;
  51 }
  52 
  53 void
  54 PyType_Modified(PyTypeObject *type)
  55 {
  56     /* Invalidate any cached data for the specified type and all
  57        subclasses.  This function is called after the base
  58        classes, mro, or attributes of the type are altered.
  59 
  60        Invariants:
  61 
  62        - Py_TPFLAGS_VALID_VERSION_TAG is never set if
  63          Py_TPFLAGS_HAVE_VERSION_TAG is not set (e.g. on type
  64          objects coming from non-recompiled extension modules)
  65 
  66        - before Py_TPFLAGS_VALID_VERSION_TAG can be set on a type,
  67          it must first be set on all super types.
  68 
  69        This function clears the Py_TPFLAGS_VALID_VERSION_TAG of a
  70        type (so it must first clear it on all subclasses).  The
  71        tp_version_tag value is meaningless unless this flag is set.
  72        We don't assign new version tags eagerly, but only as
  73        needed.
  74      */
  75     PyObject *raw, *ref;
  76     Py_ssize_t i, n;
  77 
  78     if (!PyType_HasFeature(type, Py_TPFLAGS_VALID_VERSION_TAG))
  79         return;
  80 
  81     raw = type->tp_subclasses;
  82     if (raw != NULL) {
  83         n = PyList_GET_SIZE(raw);
  84         for (i = 0; i < n; i++) {
  85             ref = PyList_GET_ITEM(raw, i);
  86             ref = PyWeakref_GET_OBJECT(ref);
  87             if (ref != Py_None) {
  88                 PyType_Modified((PyTypeObject *)ref);
  89             }
  90         }
  91     }
  92     type->tp_flags &= ~Py_TPFLAGS_VALID_VERSION_TAG;
  93 }
  94 
  95 static void
  96 type_mro_modified(PyTypeObject *type, PyObject *bases) {
  97     /*
  98        Check that all base classes or elements of the mro of type are
  99        able to be cached.  This function is called after the base
 100        classes or mro of the type are altered.
 101 
 102        Unset HAVE_VERSION_TAG and VALID_VERSION_TAG if the type
 103        inherits from an old-style class, either directly or if it
 104        appears in the MRO of a new-style class.  No support either for
 105        custom MROs that include types that are not officially super
 106        types.
 107 
 108        Called from mro_internal, which will subsequently be called on
 109        each subclass when their mro is recursively updated.
 110      */
 111     Py_ssize_t i, n;
 112     int clear = 0;
 113 
 114     if (!PyType_HasFeature(type, Py_TPFLAGS_HAVE_VERSION_TAG))
 115         return;
 116 
 117     n = PyTuple_GET_SIZE(bases);
 118     for (i = 0; i < n; i++) {
 119         PyObject *b = PyTuple_GET_ITEM(bases, i);
 120         PyTypeObject *cls;
 121 
 122         if (!PyType_Check(b) ) {
 123             clear = 1;
 124             break;
 125         }
 126 
 127         cls = (PyTypeObject *)b;
 128 
 129         if (!PyType_HasFeature(cls, Py_TPFLAGS_HAVE_VERSION_TAG) ||
 130             !PyType_IsSubtype(type, cls)) {
 131             clear = 1;
 132             break;
 133         }
 134     }
 135 
 136     if (clear)
 137         type->tp_flags &= ~(Py_TPFLAGS_HAVE_VERSION_TAG|
 138                             Py_TPFLAGS_VALID_VERSION_TAG);
 139 }
 140 
 141 static int
 142 assign_version_tag(PyTypeObject *type)
 143 {
 144     /* Ensure that the tp_version_tag is valid and set
 145        Py_TPFLAGS_VALID_VERSION_TAG.  To respect the invariant, this
 146        must first be done on all super classes.  Return 0 if this
 147        cannot be done, 1 if Py_TPFLAGS_VALID_VERSION_TAG.
 148     */
 149     Py_ssize_t i, n;
 150     PyObject *bases;
 151 
 152     if (PyType_HasFeature(type, Py_TPFLAGS_VALID_VERSION_TAG))
 153         return 1;
 154     if (!PyType_HasFeature(type, Py_TPFLAGS_HAVE_VERSION_TAG))
 155         return 0;
 156     if (!PyType_HasFeature(type, Py_TPFLAGS_READY))
 157         return 0;
 158 
 159     type->tp_version_tag = next_version_tag++;
 160     /* for stress-testing: next_version_tag &= 0xFF; */
 161 
 162     if (type->tp_version_tag == 0) {
 163         /* wrap-around or just starting Python - clear the whole
 164            cache by filling names with references to Py_None.
 165            Values are also set to NULL for added protection, as they
 166            are borrowed reference */
 167         for (i = 0; i < (1 << MCACHE_SIZE_EXP); i++) {
 168             method_cache[i].value = NULL;
 169             Py_XDECREF(method_cache[i].name);
 170             method_cache[i].name = Py_None;
 171             Py_INCREF(Py_None);
 172         }
 173         /* mark all version tags as invalid */
 174         PyType_Modified(&PyBaseObject_Type);
 175         return 1;
 176     }
 177     bases = type->tp_bases;
 178     n = PyTuple_GET_SIZE(bases);
 179     for (i = 0; i < n; i++) {
 180         PyObject *b = PyTuple_GET_ITEM(bases, i);
 181         assert(PyType_Check(b));
 182         if (!assign_version_tag((PyTypeObject *)b))
 183             return 0;
 184     }
 185     type->tp_flags |= Py_TPFLAGS_VALID_VERSION_TAG;
 186     return 1;
 187 }
 188 
 189 
 190 static PyMemberDef type_members[] = {
 191     {"__basicsize__", T_PYSSIZET, offsetof(PyTypeObject,tp_basicsize),READONLY},
 192     {"__itemsize__", T_PYSSIZET, offsetof(PyTypeObject, tp_itemsize), READONLY},
 193     {"__flags__", T_LONG, offsetof(PyTypeObject, tp_flags), READONLY},
 194     {"__weakrefoffset__", T_LONG,
 195      offsetof(PyTypeObject, tp_weaklistoffset), READONLY},
 196     {"__base__", T_OBJECT, offsetof(PyTypeObject, tp_base), READONLY},
 197     {"__dictoffset__", T_LONG,
 198      offsetof(PyTypeObject, tp_dictoffset), READONLY},
 199     {"__mro__", T_OBJECT, offsetof(PyTypeObject, tp_mro), READONLY},
 200     {0}
 201 };
 202 
 203 static PyObject *
 204 type_name(PyTypeObject *type, void *context)
 205 {
 206     const char *s;
 207 
 208     if (type->tp_flags & Py_TPFLAGS_HEAPTYPE) {
 209         PyHeapTypeObject* et = (PyHeapTypeObject*)type;
 210 
 211         Py_INCREF(et->ht_name);
 212         return et->ht_name;
 213     }
 214     else {
 215         s = strrchr(type->tp_name, '.');
 216         if (s == NULL)
 217             s = type->tp_name;
 218         else
 219             s++;
 220         return PyString_FromString(s);
 221     }
 222 }
 223 
 224 static int
 225 type_set_name(PyTypeObject *type, PyObject *value, void *context)
 226 {
 227     PyHeapTypeObject* et;
 228 
 229     if (!(type->tp_flags & Py_TPFLAGS_HEAPTYPE)) {
 230         PyErr_Format(PyExc_TypeError,
 231                      "can't set %s.__name__", type->tp_name);
 232         return -1;
 233     }
 234     if (!value) {
 235         PyErr_Format(PyExc_TypeError,
 236                      "can't delete %s.__name__", type->tp_name);
 237         return -1;
 238     }
 239     if (!PyString_Check(value)) {
 240         PyErr_Format(PyExc_TypeError,
 241                      "can only assign string to %s.__name__, not '%s'",
 242                      type->tp_name, Py_TYPE(value)->tp_name);
 243         return -1;
 244     }
 245     if (strlen(PyString_AS_STRING(value))
 246         != (size_t)PyString_GET_SIZE(value)) {
 247         PyErr_Format(PyExc_ValueError,
 248                      "__name__ must not contain null bytes");
 249         return -1;
 250     }
 251 
 252     et = (PyHeapTypeObject*)type;
 253 
 254     Py_INCREF(value);
 255 
 256     Py_DECREF(et->ht_name);
 257     et->ht_name = value;
 258 
 259     type->tp_name = PyString_AS_STRING(value);
 260 
 261     return 0;
 262 }
 263 
 264 static PyObject *
 265 type_module(PyTypeObject *type, void *context)
 266 {
 267     PyObject *mod;
 268     char *s;
 269 
 270     if (type->tp_flags & Py_TPFLAGS_HEAPTYPE) {
 271         mod = PyDict_GetItemString(type->tp_dict, "__module__");
 272         if (!mod) {
 273             PyErr_Format(PyExc_AttributeError, "__module__");
 274             return 0;
 275         }
 276         Py_XINCREF(mod);
 277         return mod;
 278     }
 279     else {
 280         s = strrchr(type->tp_name, '.');
 281         if (s != NULL)
 282             return PyString_FromStringAndSize(
 283                 type->tp_name, (Py_ssize_t)(s - type->tp_name));
 284         return PyString_FromString("__builtin__");
 285     }
 286 }
 287 
 288 static int
 289 type_set_module(PyTypeObject *type, PyObject *value, void *context)
 290 {
 291     if (!(type->tp_flags & Py_TPFLAGS_HEAPTYPE)) {
 292         PyErr_Format(PyExc_TypeError,
 293                      "can't set %s.__module__", type->tp_name);
 294         return -1;
 295     }
 296     if (!value) {
 297         PyErr_Format(PyExc_TypeError,
 298                      "can't delete %s.__module__", type->tp_name);
 299         return -1;
 300     }
 301 
 302     PyType_Modified(type);
 303 
 304     return PyDict_SetItemString(type->tp_dict, "__module__", value);
 305 }
 306 
 307 static PyObject *
 308 type_abstractmethods(PyTypeObject *type, void *context)
 309 {
 310     PyObject *mod = NULL;
 311     /* type itself has an __abstractmethods__ descriptor (this). Don't return
 312        that. */
 313     if (type != &PyType_Type)
 314         mod = PyDict_GetItemString(type->tp_dict, "__abstractmethods__");
 315     if (!mod) {
 316         PyErr_SetString(PyExc_AttributeError, "__abstractmethods__");
 317         return NULL;
 318     }
 319     Py_XINCREF(mod);
 320     return mod;
 321 }
 322 
 323 static int
 324 type_set_abstractmethods(PyTypeObject *type, PyObject *value, void *context)
 325 {
 326     /* __abstractmethods__ should only be set once on a type, in
 327        abc.ABCMeta.__new__, so this function doesn't do anything
 328        special to update subclasses.
 329     */
 330     int res;
 331     if (value != NULL) {
 332         res = PyDict_SetItemString(type->tp_dict, "__abstractmethods__", value);
 333     }
 334     else {
 335         res = PyDict_DelItemString(type->tp_dict, "__abstractmethods__");
 336         if (res && PyErr_ExceptionMatches(PyExc_KeyError)) {
 337             PyErr_SetString(PyExc_AttributeError, "__abstractmethods__");
 338             return -1;
 339         }
 340     }
 341     if (res == 0) {
 342         PyType_Modified(type);
 343         if (value && PyObject_IsTrue(value)) {
 344             type->tp_flags |= Py_TPFLAGS_IS_ABSTRACT;
 345         }
 346         else {
 347             type->tp_flags &= ~Py_TPFLAGS_IS_ABSTRACT;
 348         }
 349     }
 350     return res;
 351 }
 352 
 353 static PyObject *
 354 type_get_bases(PyTypeObject *type, void *context)
 355 {
 356     Py_INCREF(type->tp_bases);
 357     return type->tp_bases;
 358 }
 359 
 360 static PyTypeObject *best_base(PyObject *);
 361 static int mro_internal(PyTypeObject *);
 362 static int compatible_for_assignment(PyTypeObject *, PyTypeObject *, char *);
 363 static int add_subclass(PyTypeObject*, PyTypeObject*);
 364 static void remove_subclass(PyTypeObject *, PyTypeObject *);
 365 static void update_all_slots(PyTypeObject *);
 366 
 367 typedef int (*update_callback)(PyTypeObject *, void *);
 368 static int update_subclasses(PyTypeObject *type, PyObject *name,
 369                              update_callback callback, void *data);
 370 static int recurse_down_subclasses(PyTypeObject *type, PyObject *name,
 371                                    update_callback callback, void *data);
 372 
 373 static int
 374 mro_subclasses(PyTypeObject *type, PyObject* temp)
 375 {
 376     PyTypeObject *subclass;
 377     PyObject *ref, *subclasses, *old_mro;
 378     Py_ssize_t i, n;
 379 
 380     subclasses = type->tp_subclasses;
 381     if (subclasses == NULL)
 382         return 0;
 383     assert(PyList_Check(subclasses));
 384     n = PyList_GET_SIZE(subclasses);
 385     for (i = 0; i < n; i++) {
 386         ref = PyList_GET_ITEM(subclasses, i);
 387         assert(PyWeakref_CheckRef(ref));
 388         subclass = (PyTypeObject *)PyWeakref_GET_OBJECT(ref);
 389         assert(subclass != NULL);
 390         if ((PyObject *)subclass == Py_None)
 391             continue;
 392         assert(PyType_Check(subclass));
 393         old_mro = subclass->tp_mro;
 394         if (mro_internal(subclass) < 0) {
 395             subclass->tp_mro = old_mro;
 396             return -1;
 397         }
 398         else {
 399             PyObject* tuple;
 400             tuple = PyTuple_Pack(2, subclass, old_mro);
 401             Py_DECREF(old_mro);
 402             if (!tuple)
 403                 return -1;
 404             if (PyList_Append(temp, tuple) < 0)
 405                 return -1;
 406             Py_DECREF(tuple);
 407         }
 408         if (mro_subclasses(subclass, temp) < 0)
 409             return -1;
 410     }
 411     return 0;
 412 }
 413 
 414 static int
 415 type_set_bases(PyTypeObject *type, PyObject *value, void *context)
 416 {
 417     Py_ssize_t i;
 418     int r = 0;
 419     PyObject *ob, *temp;
 420     PyTypeObject *new_base, *old_base;
 421     PyObject *old_bases, *old_mro;
 422 
 423     if (!(type->tp_flags & Py_TPFLAGS_HEAPTYPE)) {
 424         PyErr_Format(PyExc_TypeError,
 425                      "can't set %s.__bases__", type->tp_name);
 426         return -1;
 427     }
 428     if (!value) {
 429         PyErr_Format(PyExc_TypeError,
 430                      "can't delete %s.__bases__", type->tp_name);
 431         return -1;
 432     }
 433     if (!PyTuple_Check(value)) {
 434         PyErr_Format(PyExc_TypeError,
 435              "can only assign tuple to %s.__bases__, not %s",
 436                  type->tp_name, Py_TYPE(value)->tp_name);
 437         return -1;
 438     }
 439     if (PyTuple_GET_SIZE(value) == 0) {
 440         PyErr_Format(PyExc_TypeError,
 441              "can only assign non-empty tuple to %s.__bases__, not ()",
 442                  type->tp_name);
 443         return -1;
 444     }
 445     for (i = 0; i < PyTuple_GET_SIZE(value); i++) {
 446         ob = PyTuple_GET_ITEM(value, i);
 447         if (!PyClass_Check(ob) && !PyType_Check(ob)) {
 448             PyErr_Format(
 449                 PyExc_TypeError,
 450     "%s.__bases__ must be tuple of old- or new-style classes, not '%s'",
 451                             type->tp_name, Py_TYPE(ob)->tp_name);
 452                     return -1;
 453         }
 454         if (PyType_Check(ob)) {
 455             if (PyType_IsSubtype((PyTypeObject*)ob, type)) {
 456                 PyErr_SetString(PyExc_TypeError,
 457             "a __bases__ item causes an inheritance cycle");
 458                 return -1;
 459             }
 460         }
 461     }
 462 
 463     new_base = best_base(value);
 464 
 465     if (!new_base) {
 466         return -1;
 467     }
 468 
 469     if (!compatible_for_assignment(type->tp_base, new_base, "__bases__"))
 470         return -1;
 471 
 472     Py_INCREF(new_base);
 473     Py_INCREF(value);
 474 
 475     old_bases = type->tp_bases;
 476     old_base = type->tp_base;
 477     old_mro = type->tp_mro;
 478 
 479     type->tp_bases = value;
 480     type->tp_base = new_base;
 481 
 482     if (mro_internal(type) < 0) {
 483         goto bail;
 484     }
 485 
 486     temp = PyList_New(0);
 487     if (!temp)
 488         goto bail;
 489 
 490     r = mro_subclasses(type, temp);
 491 
 492     if (r < 0) {
 493         for (i = 0; i < PyList_Size(temp); i++) {
 494             PyTypeObject* cls;
 495             PyObject* mro;
 496             PyArg_UnpackTuple(PyList_GET_ITEM(temp, i),
 497                              "", 2, 2, &cls, &mro);
 498             Py_INCREF(mro);
 499             ob = cls->tp_mro;
 500             cls->tp_mro = mro;
 501             Py_DECREF(ob);
 502         }
 503         Py_DECREF(temp);
 504         goto bail;
 505     }
 506 
 507     Py_DECREF(temp);
 508 
 509     /* any base that was in __bases__ but now isn't, we
 510        need to remove |type| from its tp_subclasses.
 511        conversely, any class now in __bases__ that wasn't
 512        needs to have |type| added to its subclasses. */
 513 
 514     /* for now, sod that: just remove from all old_bases,
 515        add to all new_bases */
 516 
 517     for (i = PyTuple_GET_SIZE(old_bases) - 1; i >= 0; i--) {
 518         ob = PyTuple_GET_ITEM(old_bases, i);
 519         if (PyType_Check(ob)) {
 520             remove_subclass(
 521                 (PyTypeObject*)ob, type);
 522         }
 523     }
 524 
 525     for (i = PyTuple_GET_SIZE(value) - 1; i >= 0; i--) {
 526         ob = PyTuple_GET_ITEM(value, i);
 527         if (PyType_Check(ob)) {
 528             if (add_subclass((PyTypeObject*)ob, type) < 0)
 529                 r = -1;
 530         }
 531     }
 532 
 533     update_all_slots(type);
 534 
 535     Py_DECREF(old_bases);
 536     Py_DECREF(old_base);
 537     Py_DECREF(old_mro);
 538 
 539     return r;
 540 
 541   bail:
 542     Py_DECREF(type->tp_bases);
 543     Py_DECREF(type->tp_base);
 544     if (type->tp_mro != old_mro) {
 545         Py_DECREF(type->tp_mro);
 546     }
 547 
 548     type->tp_bases = old_bases;
 549     type->tp_base = old_base;
 550     type->tp_mro = old_mro;
 551 
 552     return -1;
 553 }
 554 
 555 static PyObject *
 556 type_dict(PyTypeObject *type, void *context)
 557 {
 558     if (type->tp_dict == NULL) {
 559         Py_INCREF(Py_None);
 560         return Py_None;
 561     }
 562     return PyDictProxy_New(type->tp_dict);
 563 }
 564 
 565 static PyObject *
 566 type_get_doc(PyTypeObject *type, void *context)
 567 {
 568     PyObject *result;
 569     if (!(type->tp_flags & Py_TPFLAGS_HEAPTYPE) && type->tp_doc != NULL)
 570         return PyString_FromString(type->tp_doc);
 571     result = PyDict_GetItemString(type->tp_dict, "__doc__");
 572     if (result == NULL) {
 573         result = Py_None;
 574         Py_INCREF(result);
 575     }
 576     else if (Py_TYPE(result)->tp_descr_get) {
 577         result = Py_TYPE(result)->tp_descr_get(result, NULL,
 578                                                (PyObject *)type);
 579     }
 580     else {
 581         Py_INCREF(result);
 582     }
 583     return result;
 584 }
 585 
 586 static PyObject *
 587 type___instancecheck__(PyObject *type, PyObject *inst)
 588 {
 589     switch (_PyObject_RealIsInstance(inst, type)) {
 590     case -1:
 591         return NULL;
 592     case 0:
 593         Py_RETURN_FALSE;
 594     default:
 595         Py_RETURN_TRUE;
 596     }
 597 }
 598 
 599 
 600 static PyObject *
 601 type___subclasscheck__(PyObject *type, PyObject *inst)
 602 {
 603     switch (_PyObject_RealIsSubclass(inst, type)) {
 604     case -1:
 605         return NULL;
 606     case 0:
 607         Py_RETURN_FALSE;
 608     default:
 609         Py_RETURN_TRUE;
 610     }
 611 }
 612 
 613 
 614 static PyGetSetDef type_getsets[] = {
 615     {"__name__", (getter)type_name, (setter)type_set_name, NULL},
 616     {"__bases__", (getter)type_get_bases, (setter)type_set_bases, NULL},
 617     {"__module__", (getter)type_module, (setter)type_set_module, NULL},
 618     {"__abstractmethods__", (getter)type_abstractmethods,
 619      (setter)type_set_abstractmethods, NULL},
 620     {"__dict__",  (getter)type_dict,  NULL, NULL},
 621     {"__doc__", (getter)type_get_doc, NULL, NULL},
 622     {0}
 623 };
 624 
 625 
 626 static PyObject*
 627 type_richcompare(PyObject *v, PyObject *w, int op)
 628 {
 629     PyObject *result;
 630     Py_uintptr_t vv, ww;
 631     int c;
 632 
 633     /* Make sure both arguments are types. */
 634     if (!PyType_Check(v) || !PyType_Check(w) ||
 635         /* If there is a __cmp__ method defined, let it be called instead
 636            of our dumb function designed merely to warn.  See bug
 637            #7491. */
 638         Py_TYPE(v)->tp_compare || Py_TYPE(w)->tp_compare) {
 639         result = Py_NotImplemented;
 640         goto out;
 641     }
 642 
 643     /* Py3K warning if comparison isn't == or !=  */
 644     if (Py_Py3kWarningFlag && op != Py_EQ && op != Py_NE &&
 645         PyErr_WarnEx(PyExc_DeprecationWarning,
 646                    "type inequality comparisons not supported "
 647                    "in 3.x", 1) < 0) {
 648         return NULL;
 649     }
 650 
 651     /* Compare addresses */
 652     vv = (Py_uintptr_t)v;
 653     ww = (Py_uintptr_t)w;
 654     switch (op) {
 655     case Py_LT: c = vv <  ww; break;
 656     case Py_LE: c = vv <= ww; break;
 657     case Py_EQ: c = vv == ww; break;
 658     case Py_NE: c = vv != ww; break;
 659     case Py_GT: c = vv >  ww; break;
 660     case Py_GE: c = vv >= ww; break;
 661     default:
 662         result = Py_NotImplemented;
 663         goto out;
 664     }
 665     result = c ? Py_True : Py_False;
 666 
 667   /* incref and return */
 668   out:
 669     Py_INCREF(result);
 670     return result;
 671 }
 672 
 673 static PyObject *
 674 type_repr(PyTypeObject *type)
 675 {
 676     PyObject *mod, *name, *rtn;
 677     char *kind;
 678 
 679     mod = type_module(type, NULL);
 680     if (mod == NULL)
 681         PyErr_Clear();
 682     else if (!PyString_Check(mod)) {
 683         Py_DECREF(mod);
 684         mod = NULL;
 685     }
 686     name = type_name(type, NULL);
 687     if (name == NULL)
 688         return NULL;
 689 
 690     if (type->tp_flags & Py_TPFLAGS_HEAPTYPE)
 691         kind = "class";
 692     else
 693         kind = "type";
 694 
 695     if (mod != NULL && strcmp(PyString_AS_STRING(mod), "__builtin__")) {
 696         rtn = PyString_FromFormat("<%s '%s.%s'>",
 697                                   kind,
 698                                   PyString_AS_STRING(mod),
 699                                   PyString_AS_STRING(name));
 700     }
 701     else
 702         rtn = PyString_FromFormat("<%s '%s'>", kind, type->tp_name);
 703 
 704     Py_XDECREF(mod);
 705     Py_DECREF(name);
 706     return rtn;
 707 }
 708 
 709 static PyObject *
 710 type_call(PyTypeObject *type, PyObject *args, PyObject *kwds)
 711 {
 712     PyObject *obj;
 713 
 714     if (type->tp_new == NULL) {
 715         PyErr_Format(PyExc_TypeError,
 716                      "cannot create '%.100s' instances",
 717                      type->tp_name);
 718         return NULL;
 719     }
 720 
 721     obj = type->tp_new(type, args, kwds);
 722     if (obj != NULL) {
 723         /* Ugly exception: when the call was type(something),
 724            don't call tp_init on the result. */
 725         if (type == &PyType_Type &&
 726             PyTuple_Check(args) && PyTuple_GET_SIZE(args) == 1 &&
 727             (kwds == NULL ||
 728              (PyDict_Check(kwds) && PyDict_Size(kwds) == 0)))
 729             return obj;
 730         /* If the returned object is not an instance of type,
 731            it won't be initialized. */
 732         if (!PyType_IsSubtype(obj->ob_type, type))
 733             return obj;
 734         type = obj->ob_type;
 735         if (PyType_HasFeature(type, Py_TPFLAGS_HAVE_CLASS) &&
 736             type->tp_init != NULL &&
 737             type->tp_init(obj, args, kwds) < 0) {
 738             Py_DECREF(obj);
 739             obj = NULL;
 740         }
 741     }
 742     return obj;
 743 }
 744 
 745 PyObject *
 746 PyType_GenericAlloc(PyTypeObject *type, Py_ssize_t nitems)
 747 {
 748     PyObject *obj;
 749     const size_t size = _PyObject_VAR_SIZE(type, nitems+1);
 750     /* note that we need to add one, for the sentinel */
 751 
 752     if (PyType_IS_GC(type))
 753         obj = _PyObject_GC_Malloc(size);
 754     else
 755         obj = (PyObject *)PyObject_MALLOC(size);
 756 
 757     if (obj == NULL)
 758         return PyErr_NoMemory();
 759 
 760     memset(obj, '\0', size);
 761 
 762     if (type->tp_flags & Py_TPFLAGS_HEAPTYPE)
 763         Py_INCREF(type);
 764 
 765     if (type->tp_itemsize == 0)
 766         PyObject_INIT(obj, type);
 767     else
 768         (void) PyObject_INIT_VAR((PyVarObject *)obj, type, nitems);
 769 
 770     if (PyType_IS_GC(type))
 771         _PyObject_GC_TRACK(obj);
 772     return obj;
 773 }
 774 
 775 PyObject *
 776 PyType_GenericNew(PyTypeObject *type, PyObject *args, PyObject *kwds)
 777 {
 778     return type->tp_alloc(type, 0);
 779 }
 780 
 781 /* Helpers for subtyping */
 782 
 783 static int
 784 traverse_slots(PyTypeObject *type, PyObject *self, visitproc visit, void *arg)
 785 {
 786     Py_ssize_t i, n;
 787     PyMemberDef *mp;
 788 
 789     n = Py_SIZE(type);
 790     mp = PyHeapType_GET_MEMBERS((PyHeapTypeObject *)type);
 791     for (i = 0; i < n; i++, mp++) {
 792         if (mp->type == T_OBJECT_EX) {
 793             char *addr = (char *)self + mp->offset;
 794             PyObject *obj = *(PyObject **)addr;
 795             if (obj != NULL) {
 796                 int err = visit(obj, arg);
 797                 if (err)
 798                     return err;
 799             }
 800         }
 801     }
 802     return 0;
 803 }
 804 
 805 static int
 806 subtype_traverse(PyObject *self, visitproc visit, void *arg)
 807 {
 808     PyTypeObject *type, *base;
 809     traverseproc basetraverse;
 810 
 811     /* Find the nearest base with a different tp_traverse,
 812        and traverse slots while we're at it */
 813     type = Py_TYPE(self);
 814     base = type;
 815     while ((basetraverse = base->tp_traverse) == subtype_traverse) {
 816         if (Py_SIZE(base)) {
 817             int err = traverse_slots(base, self, visit, arg);
 818             if (err)
 819                 return err;
 820         }
 821         base = base->tp_base;
 822         assert(base);
 823     }
 824 
 825     if (type->tp_dictoffset != base->tp_dictoffset) {
 826         PyObject **dictptr = _PyObject_GetDictPtr(self);
 827         if (dictptr && *dictptr)
 828             Py_VISIT(*dictptr);
 829     }
 830 
 831     if (type->tp_flags & Py_TPFLAGS_HEAPTYPE)
 832         /* For a heaptype, the instances count as references
 833            to the type.          Traverse the type so the collector
 834            can find cycles involving this link. */
 835         Py_VISIT(type);
 836 
 837     if (basetraverse)
 838         return basetraverse(self, visit, arg);
 839     return 0;
 840 }
 841 
 842 static void
 843 clear_slots(PyTypeObject *type, PyObject *self)
 844 {
 845     Py_ssize_t i, n;
 846     PyMemberDef *mp;
 847 
 848     n = Py_SIZE(type);
 849     mp = PyHeapType_GET_MEMBERS((PyHeapTypeObject *)type);
 850     for (i = 0; i < n; i++, mp++) {
 851         if (mp->type == T_OBJECT_EX && !(mp->flags & READONLY)) {
 852             char *addr = (char *)self + mp->offset;
 853             PyObject *obj = *(PyObject **)addr;
 854             if (obj != NULL) {
 855                 *(PyObject **)addr = NULL;
 856                 Py_DECREF(obj);
 857             }
 858         }
 859     }
 860 }
 861 
 862 static int
 863 subtype_clear(PyObject *self)
 864 {
 865     PyTypeObject *type, *base;
 866     inquiry baseclear;
 867 
 868     /* Find the nearest base with a different tp_clear
 869        and clear slots while we're at it */
 870     type = Py_TYPE(self);
 871     base = type;
 872     while ((baseclear = base->tp_clear) == subtype_clear) {
 873         if (Py_SIZE(base))
 874             clear_slots(base, self);
 875         base = base->tp_base;
 876         assert(base);
 877     }
 878 
 879     /* There's no need to clear the instance dict (if any);
 880        the collector will call its tp_clear handler. */
 881 
 882     if (baseclear)
 883         return baseclear(self);
 884     return 0;
 885 }
 886 
 887 static void
 888 subtype_dealloc(PyObject *self)
 889 {
 890     PyTypeObject *type, *base;
 891     destructor basedealloc;
 892 
 893     /* Extract the type; we expect it to be a heap type */
 894     type = Py_TYPE(self);
 895     assert(type->tp_flags & Py_TPFLAGS_HEAPTYPE);
 896 
 897     /* Test whether the type has GC exactly once */
 898 
 899     if (!PyType_IS_GC(type)) {
 900         /* It's really rare to find a dynamic type that doesn't have
 901            GC; it can only happen when deriving from 'object' and not
 902            adding any slots or instance variables.  This allows
 903            certain simplifications: there's no need to call
 904            clear_slots(), or DECREF the dict, or clear weakrefs. */
 905 
 906         /* Maybe call finalizer; exit early if resurrected */
 907         if (type->tp_del) {
 908             type->tp_del(self);
 909             if (self->ob_refcnt > 0)
 910                 return;
 911         }
 912 
 913         /* Find the nearest base with a different tp_dealloc */
 914         base = type;
 915         while ((basedealloc = base->tp_dealloc) == subtype_dealloc) {
 916             assert(Py_SIZE(base) == 0);
 917             base = base->tp_base;
 918             assert(base);
 919         }
 920 
 921         /* Extract the type again; tp_del may have changed it */
 922         type = Py_TYPE(self);
 923 
 924         /* Call the base tp_dealloc() */
 925         assert(basedealloc);
 926         basedealloc(self);
 927 
 928         /* Can't reference self beyond this point */
 929         Py_DECREF(type);
 930 
 931         /* Done */
 932         return;
 933     }
 934 
 935     /* We get here only if the type has GC */
 936 
 937     /* UnTrack and re-Track around the trashcan macro, alas */
 938     /* See explanation at end of function for full disclosure */
 939     PyObject_GC_UnTrack(self);
 940     ++_PyTrash_delete_nesting;
 941     Py_TRASHCAN_SAFE_BEGIN(self);
 942     --_PyTrash_delete_nesting;
 943     /* DO NOT restore GC tracking at this point.  weakref callbacks
 944      * (if any, and whether directly here or indirectly in something we
 945      * call) may trigger GC, and if self is tracked at that point, it
 946      * will look like trash to GC and GC will try to delete self again.
 947      */
 948 
 949     /* Find the nearest base with a different tp_dealloc */
 950     base = type;
 951     while ((basedealloc = base->tp_dealloc) == subtype_dealloc) {
 952         base = base->tp_base;
 953         assert(base);
 954     }
 955 
 956     /* If we added a weaklist, we clear it.      Do this *before* calling
 957        the finalizer (__del__), clearing slots, or clearing the instance
 958        dict. */
 959 
 960     if (type->tp_weaklistoffset && !base->tp_weaklistoffset)
 961         PyObject_ClearWeakRefs(self);
 962 
 963     /* Maybe call finalizer; exit early if resurrected */
 964     if (type->tp_del) {
 965         _PyObject_GC_TRACK(self);
 966         type->tp_del(self);
 967         if (self->ob_refcnt > 0)
 968             goto endlabel;              /* resurrected */
 969         else
 970             _PyObject_GC_UNTRACK(self);
 971         /* New weakrefs could be created during the finalizer call.
 972             If this occurs, clear them out without calling their
 973             finalizers since they might rely on part of the object
 974             being finalized that has already been destroyed. */
 975         if (type->tp_weaklistoffset && !base->tp_weaklistoffset) {
 976             /* Modeled after GET_WEAKREFS_LISTPTR() */
 977             PyWeakReference **list = (PyWeakReference **) \
 978                 PyObject_GET_WEAKREFS_LISTPTR(self);
 979             while (*list)
 980                 _PyWeakref_ClearRef(*list);
 981         }
 982     }
 983 
 984     /*  Clear slots up to the nearest base with a different tp_dealloc */
 985     base = type;
 986     while (base->tp_dealloc == subtype_dealloc) {
 987         if (Py_SIZE(base))
 988             clear_slots(base, self);
 989         base = base->tp_base;
 990         assert(base);
 991     }
 992 
 993     /* If we added a dict, DECREF it */
 994     if (type->tp_dictoffset && !base->tp_dictoffset) {
 995         PyObject **dictptr = _PyObject_GetDictPtr(self);
 996         if (dictptr != NULL) {
 997             PyObject *dict = *dictptr;
 998             if (dict != NULL) {
 999                 Py_DECREF(dict);
1000                 *dictptr = NULL;
1001             }
1002         }
1003     }
1004 
1005     /* Extract the type again; tp_del may have changed it */
1006     type = Py_TYPE(self);
1007 
1008     /* Call the base tp_dealloc(); first retrack self if
1009      * basedealloc knows about gc.
1010      */
1011     if (PyType_IS_GC(base))
1012         _PyObject_GC_TRACK(self);
1013     assert(basedealloc);
1014     basedealloc(self);
1015 
1016     /* Can't reference self beyond this point */
1017     Py_DECREF(type);
1018 
1019   endlabel:
1020     ++_PyTrash_delete_nesting;
1021     Py_TRASHCAN_SAFE_END(self);
1022     --_PyTrash_delete_nesting;
1023 
1024     /* Explanation of the weirdness around the trashcan macros:
1025 
1026        Q. What do the trashcan macros do?
1027 
1028        A. Read the comment titled "Trashcan mechanism" in object.h.
1029           For one, this explains why there must be a call to GC-untrack
1030           before the trashcan begin macro.      Without understanding the
1031           trashcan code, the answers to the following questions don't make
1032           sense.
1033 
1034        Q. Why do we GC-untrack before the trashcan and then immediately
1035           GC-track again afterward?
1036 
1037        A. In the case that the base class is GC-aware, the base class
1038           probably GC-untracks the object.      If it does that using the
1039           UNTRACK macro, this will crash when the object is already
1040           untracked.  Because we don't know what the base class does, the
1041           only safe thing is to make sure the object is tracked when we
1042           call the base class dealloc.  But...  The trashcan begin macro
1043           requires that the object is *untracked* before it is called.  So
1044           the dance becomes:
1045 
1046          GC untrack
1047          trashcan begin
1048          GC track
1049 
1050        Q. Why did the last question say "immediately GC-track again"?
1051           It's nowhere near immediately.
1052 
1053        A. Because the code *used* to re-track immediately.      Bad Idea.
1054           self has a refcount of 0, and if gc ever gets its hands on it
1055           (which can happen if any weakref callback gets invoked), it
1056           looks like trash to gc too, and gc also tries to delete self
1057           then.  But we're already deleting self.  Double deallocation is
1058           a subtle disaster.
1059 
1060        Q. Why the bizarre (net-zero) manipulation of
1061           _PyTrash_delete_nesting around the trashcan macros?
1062 
1063        A. Some base classes (e.g. list) also use the trashcan mechanism.
1064           The following scenario used to be possible:
1065 
1066           - suppose the trashcan level is one below the trashcan limit
1067 
1068           - subtype_dealloc() is called
1069 
1070           - the trashcan limit is not yet reached, so the trashcan level
1071         is incremented and the code between trashcan begin and end is
1072         executed
1073 
1074           - this destroys much of the object's contents, including its
1075         slots and __dict__
1076 
1077           - basedealloc() is called; this is really list_dealloc(), or
1078         some other type which also uses the trashcan macros
1079 
1080           - the trashcan limit is now reached, so the object is put on the
1081         trashcan's to-be-deleted-later list
1082 
1083           - basedealloc() returns
1084 
1085           - subtype_dealloc() decrefs the object's type
1086 
1087           - subtype_dealloc() returns
1088 
1089           - later, the trashcan code starts deleting the objects from its
1090         to-be-deleted-later list
1091 
1092           - subtype_dealloc() is called *AGAIN* for the same object
1093 
1094           - at the very least (if the destroyed slots and __dict__ don't
1095         cause problems) the object's type gets decref'ed a second
1096         time, which is *BAD*!!!
1097 
1098           The remedy is to make sure that if the code between trashcan
1099           begin and end in subtype_dealloc() is called, the code between
1100           trashcan begin and end in basedealloc() will also be called.
1101           This is done by decrementing the level after passing into the
1102           trashcan block, and incrementing it just before leaving the
1103           block.
1104 
1105           But now it's possible that a chain of objects consisting solely
1106           of objects whose deallocator is subtype_dealloc() will defeat
1107           the trashcan mechanism completely: the decremented level means
1108           that the effective level never reaches the limit.      Therefore, we
1109           *increment* the level *before* entering the trashcan block, and
1110           matchingly decrement it after leaving.  This means the trashcan
1111           code will trigger a little early, but that's no big deal.
1112 
1113        Q. Are there any live examples of code in need of all this
1114           complexity?
1115 
1116        A. Yes.  See SF bug 668433 for code that crashed (when Python was
1117           compiled in debug mode) before the trashcan level manipulations
1118           were added.  For more discussion, see SF patches 581742, 575073
1119           and bug 574207.
1120     */
1121 }
1122 
1123 static PyTypeObject *solid_base(PyTypeObject *type);
1124 
1125 /* type test with subclassing support */
1126 
1127 int
1128 PyType_IsSubtype(PyTypeObject *a, PyTypeObject *b)
1129 {
1130     PyObject *mro;
1131 
1132     if (!(a->tp_flags & Py_TPFLAGS_HAVE_CLASS))
1133         return b == a || b == &PyBaseObject_Type;
1134 
1135     mro = a->tp_mro;
1136     if (mro != NULL) {
1137         /* Deal with multiple inheritance without recursion
1138            by walking the MRO tuple */
1139         Py_ssize_t i, n;
1140         assert(PyTuple_Check(mro));
1141         n = PyTuple_GET_SIZE(mro);
1142         for (i = 0; i < n; i++) {
1143             if (PyTuple_GET_ITEM(mro, i) == (PyObject *)b)
1144                 return 1;
1145         }
1146         return 0;
1147     }
1148     else {
1149         /* a is not completely initilized yet; follow tp_base */
1150         do {
1151             if (a == b)
1152                 return 1;
1153             a = a->tp_base;
1154         } while (a != NULL);
1155         return b == &PyBaseObject_Type;
1156     }
1157 }
1158 
1159 /* Internal routines to do a method lookup in the type
1160    without looking in the instance dictionary
1161    (so we can't use PyObject_GetAttr) but still binding
1162    it to the instance.  The arguments are the object,
1163    the method name as a C string, and the address of a
1164    static variable used to cache the interned Python string.
1165 
1166    Two variants:
1167 
1168    - lookup_maybe() returns NULL without raising an exception
1169      when the _PyType_Lookup() call fails;
1170 
1171    - lookup_method() always raises an exception upon errors.
1172 
1173    - _PyObject_LookupSpecial() exported for the benefit of other places.
1174 */
1175 
1176 static PyObject *
1177 lookup_maybe(PyObject *self, char *attrstr, PyObject **attrobj)
1178 {
1179     PyObject *res;
1180 
1181     if (*attrobj == NULL) {
1182         *attrobj = PyString_InternFromString(attrstr);
1183         if (*attrobj == NULL)
1184             return NULL;
1185     }
1186     res = _PyType_Lookup(Py_TYPE(self), *attrobj);
1187     if (res != NULL) {
1188         descrgetfunc f;
1189         if ((f = Py_TYPE(res)->tp_descr_get) == NULL)
1190             Py_INCREF(res);
1191         else
1192             res = f(res, self, (PyObject *)(Py_TYPE(self)));
1193     }
1194     return res;
1195 }
1196 
1197 static PyObject *
1198 lookup_method(PyObject *self, char *attrstr, PyObject **attrobj)
1199 {
1200     PyObject *res = lookup_maybe(self, attrstr, attrobj);
1201     if (res == NULL && !PyErr_Occurred())
1202         PyErr_SetObject(PyExc_AttributeError, *attrobj);
1203     return res;
1204 }
1205 
1206 PyObject *
1207 _PyObject_LookupSpecial(PyObject *self, char *attrstr, PyObject **attrobj)
1208 {
1209     assert(!PyInstance_Check(self));
1210     return lookup_maybe(self, attrstr, attrobj);
1211 }
1212 
1213 /* A variation of PyObject_CallMethod that uses lookup_method()
1214    instead of PyObject_GetAttrString().  This uses the same convention
1215    as lookup_method to cache the interned name string object. */
1216 
1217 static PyObject *
1218 call_method(PyObject *o, char *name, PyObject **nameobj, char *format, ...)
1219 {
1220     va_list va;
1221     PyObject *args, *func = 0, *retval;
1222     va_start(va, format);
1223 
1224     func = lookup_maybe(o, name, nameobj);
1225     if (func == NULL) {
1226         va_end(va);
1227         if (!PyErr_Occurred())
1228             PyErr_SetObject(PyExc_AttributeError, *nameobj);
1229         return NULL;
1230     }
1231 
1232     if (format && *format)
1233         args = Py_VaBuildValue(format, va);
1234     else
1235         args = PyTuple_New(0);
1236 
1237     va_end(va);
1238 
1239     if (args == NULL)
1240         return NULL;
1241 
1242     assert(PyTuple_Check(args));
1243     retval = PyObject_Call(func, args, NULL);
1244 
1245     Py_DECREF(args);
1246     Py_DECREF(func);
1247 
1248     return retval;
1249 }
1250 
1251 /* Clone of call_method() that returns NotImplemented when the lookup fails. */
1252 
1253 static PyObject *
1254 call_maybe(PyObject *o, char *name, PyObject **nameobj, char *format, ...)
1255 {
1256     va_list va;
1257     PyObject *args, *func = 0, *retval;
1258     va_start(va, format);
1259 
1260     func = lookup_maybe(o, name, nameobj);
1261     if (func == NULL) {
1262         va_end(va);
1263         if (!PyErr_Occurred()) {
1264             Py_INCREF(Py_NotImplemented);
1265             return Py_NotImplemented;
1266         }
1267         return NULL;
1268     }
1269 
1270     if (format && *format)
1271         args = Py_VaBuildValue(format, va);
1272     else
1273         args = PyTuple_New(0);
1274 
1275     va_end(va);
1276 
1277     if (args == NULL)
1278         return NULL;
1279 
1280     assert(PyTuple_Check(args));
1281     retval = PyObject_Call(func, args, NULL);
1282 
1283     Py_DECREF(args);
1284     Py_DECREF(func);
1285 
1286     return retval;
1287 }
1288 
1289 static int
1290 fill_classic_mro(PyObject *mro, PyObject *cls)
1291 {
1292     PyObject *bases, *base;
1293     Py_ssize_t i, n;
1294 
1295     assert(PyList_Check(mro));
1296     assert(PyClass_Check(cls));
1297     i = PySequence_Contains(mro, cls);
1298     if (i < 0)
1299         return -1;
1300     if (!i) {
1301         if (PyList_Append(mro, cls) < 0)
1302             return -1;
1303     }
1304     bases = ((PyClassObject *)cls)->cl_bases;
1305     assert(bases && PyTuple_Check(bases));
1306     n = PyTuple_GET_SIZE(bases);
1307     for (i = 0; i < n; i++) {
1308         base = PyTuple_GET_ITEM(bases, i);
1309         if (fill_classic_mro(mro, base) < 0)
1310             return -1;
1311     }
1312     return 0;
1313 }
1314 
1315 static PyObject *
1316 classic_mro(PyObject *cls)
1317 {
1318     PyObject *mro;
1319 
1320     assert(PyClass_Check(cls));
1321     mro = PyList_New(0);
1322     if (mro != NULL) {
1323         if (fill_classic_mro(mro, cls) == 0)
1324             return mro;
1325         Py_DECREF(mro);
1326     }
1327     return NULL;
1328 }
1329 
1330 /*
1331     Method resolution order algorithm C3 described in
1332     "A Monotonic Superclass Linearization for Dylan",
1333     by Kim Barrett, Bob Cassel, Paul Haahr,
1334     David A. Moon, Keith Playford, and P. Tucker Withington.
1335     (OOPSLA 1996)
1336 
1337     Some notes about the rules implied by C3:
1338 
1339     No duplicate bases.
1340     It isn't legal to repeat a class in a list of base classes.
1341 
1342     The next three properties are the 3 constraints in "C3".
1343 
1344     Local precendece order.
1345     If A precedes B in C's MRO, then A will precede B in the MRO of all
1346     subclasses of C.
1347 
1348     Monotonicity.
1349     The MRO of a class must be an extension without reordering of the
1350     MRO of each of its superclasses.
1351 
1352     Extended Precedence Graph (EPG).
1353     Linearization is consistent if there is a path in the EPG from
1354     each class to all its successors in the linearization.  See
1355     the paper for definition of EPG.
1356  */
1357 
1358 static int
1359 tail_contains(PyObject *list, int whence, PyObject *o) {
1360     Py_ssize_t j, size;
1361     size = PyList_GET_SIZE(list);
1362 
1363     for (j = whence+1; j < size; j++) {
1364         if (PyList_GET_ITEM(list, j) == o)
1365             return 1;
1366     }
1367     return 0;
1368 }
1369 
1370 static PyObject *
1371 class_name(PyObject *cls)
1372 {
1373     PyObject *name = PyObject_GetAttrString(cls, "__name__");
1374     if (name == NULL) {
1375         PyErr_Clear();
1376         Py_XDECREF(name);
1377         name = PyObject_Repr(cls);
1378     }
1379     if (name == NULL)
1380         return NULL;
1381     if (!PyString_Check(name)) {
1382         Py_DECREF(name);
1383         return NULL;
1384     }
1385     return name;
1386 }
1387 
1388 static int
1389 check_duplicates(PyObject *list)
1390 {
1391     Py_ssize_t i, j, n;
1392     /* Let's use a quadratic time algorithm,
1393        assuming that the bases lists is short.
1394     */
1395     n = PyList_GET_SIZE(list);
1396     for (i = 0; i < n; i++) {
1397         PyObject *o = PyList_GET_ITEM(list, i);
1398         for (j = i + 1; j < n; j++) {
1399             if (PyList_GET_ITEM(list, j) == o) {
1400                 o = class_name(o);
1401                 PyErr_Format(PyExc_TypeError,
1402                              "duplicate base class %s",
1403                              o ? PyString_AS_STRING(o) : "?");
1404                 Py_XDECREF(o);
1405                 return -1;
1406             }
1407         }
1408     }
1409     return 0;
1410 }
1411 
1412 /* Raise a TypeError for an MRO order disagreement.
1413 
1414    It's hard to produce a good error message.  In the absence of better
1415    insight into error reporting, report the classes that were candidates
1416    to be put next into the MRO.  There is some conflict between the
1417    order in which they should be put in the MRO, but it's hard to
1418    diagnose what constraint can't be satisfied.
1419 */
1420 
1421 static void
1422 set_mro_error(PyObject *to_merge, int *remain)
1423 {
1424     Py_ssize_t i, n, off, to_merge_size;
1425     char buf[1000];
1426     PyObject *k, *v;
1427     PyObject *set = PyDict_New();
1428     if (!set) return;
1429 
1430     to_merge_size = PyList_GET_SIZE(to_merge);
1431     for (i = 0; i < to_merge_size; i++) {
1432         PyObject *L = PyList_GET_ITEM(to_merge, i);
1433         if (remain[i] < PyList_GET_SIZE(L)) {
1434             PyObject *c = PyList_GET_ITEM(L, remain[i]);
1435             if (PyDict_SetItem(set, c, Py_None) < 0) {
1436                 Py_DECREF(set);
1437                 return;
1438             }
1439         }
1440     }
1441     n = PyDict_Size(set);
1442 
1443     off = PyOS_snprintf(buf, sizeof(buf), "Cannot create a \
1444 consistent method resolution\norder (MRO) for bases");
1445     i = 0;
1446     while (PyDict_Next(set, &i, &k, &v) && (size_t)off < sizeof(buf)) {
1447         PyObject *name = class_name(k);
1448         off += PyOS_snprintf(buf + off, sizeof(buf) - off, " %s",
1449                              name ? PyString_AS_STRING(name) : "?");
1450         Py_XDECREF(name);
1451         if (--n && (size_t)(off+1) < sizeof(buf)) {
1452             buf[off++] = ',';
1453             buf[off] = '\0';
1454         }
1455     }
1456     PyErr_SetString(PyExc_TypeError, buf);
1457     Py_DECREF(set);
1458 }
1459 
1460 static int
1461 pmerge(PyObject *acc, PyObject* to_merge) {
1462     Py_ssize_t i, j, to_merge_size, empty_cnt;
1463     int *remain;
1464     int ok;
1465 
1466     to_merge_size = PyList_GET_SIZE(to_merge);
1467 
1468     /* remain stores an index into each sublist of to_merge.
1469        remain[i] is the index of the next base in to_merge[i]
1470        that is not included in acc.
1471     */
1472     remain = (int *)PyMem_MALLOC(SIZEOF_INT*to_merge_size);
1473     if (remain == NULL)
1474         return -1;
1475     for (i = 0; i < to_merge_size; i++)
1476         remain[i] = 0;
1477 
1478   again:
1479     empty_cnt = 0;
1480     for (i = 0; i < to_merge_size; i++) {
1481         PyObject *candidate;
1482 
1483         PyObject *cur_list = PyList_GET_ITEM(to_merge, i);
1484 
1485         if (remain[i] >= PyList_GET_SIZE(cur_list)) {
1486             empty_cnt++;
1487             continue;
1488         }
1489 
1490         /* Choose next candidate for MRO.
1491 
1492            The input sequences alone can determine the choice.
1493            If not, choose the class which appears in the MRO
1494            of the earliest direct superclass of the new class.
1495         */
1496 
1497         candidate = PyList_GET_ITEM(cur_list, remain[i]);
1498         for (j = 0; j < to_merge_size; j++) {
1499             PyObject *j_lst = PyList_GET_ITEM(to_merge, j);
1500             if (tail_contains(j_lst, remain[j], candidate)) {
1501                 goto skip; /* continue outer loop */
1502             }
1503         }
1504         ok = PyList_Append(acc, candidate);
1505         if (ok < 0) {
1506             PyMem_Free(remain);
1507             return -1;
1508         }
1509         for (j = 0; j < to_merge_size; j++) {
1510             PyObject *j_lst = PyList_GET_ITEM(to_merge, j);
1511             if (remain[j] < PyList_GET_SIZE(j_lst) &&
1512                 PyList_GET_ITEM(j_lst, remain[j]) == candidate) {
1513                 remain[j]++;
1514             }
1515         }
1516         goto again;
1517       skip: ;
1518     }
1519 
1520     if (empty_cnt == to_merge_size) {
1521         PyMem_FREE(remain);
1522         return 0;
1523     }
1524     set_mro_error(to_merge, remain);
1525     PyMem_FREE(remain);
1526     return -1;
1527 }
1528 
1529 static PyObject *
1530 mro_implementation(PyTypeObject *type)
1531 {
1532     Py_ssize_t i, n;
1533     int ok;
1534     PyObject *bases, *result;
1535     PyObject *to_merge, *bases_aslist;
1536 
1537     if (type->tp_dict == NULL) {
1538         if (PyType_Ready(type) < 0)
1539             return NULL;
1540     }
1541 
1542     /* Find a superclass linearization that honors the constraints
1543        of the explicit lists of bases and the constraints implied by
1544        each base class.
1545 
1546        to_merge is a list of lists, where each list is a superclass
1547        linearization implied by a base class.  The last element of
1548        to_merge is the declared list of bases.
1549     */
1550 
1551     bases = type->tp_bases;
1552     n = PyTuple_GET_SIZE(bases);
1553 
1554     to_merge = PyList_New(n+1);
1555     if (to_merge == NULL)
1556         return NULL;
1557 
1558     for (i = 0; i < n; i++) {
1559         PyObject *base = PyTuple_GET_ITEM(bases, i);
1560         PyObject *parentMRO;
1561         if (PyType_Check(base))
1562             parentMRO = PySequence_List(
1563                 ((PyTypeObject*)base)->tp_mro);
1564         else
1565             parentMRO = classic_mro(base);
1566         if (parentMRO == NULL) {
1567             Py_DECREF(to_merge);
1568             return NULL;
1569         }
1570 
1571         PyList_SET_ITEM(to_merge, i, parentMRO);
1572     }
1573 
1574     bases_aslist = PySequence_List(bases);
1575     if (bases_aslist == NULL) {
1576         Py_DECREF(to_merge);
1577         return NULL;
1578     }
1579     /* This is just a basic sanity check. */
1580     if (check_duplicates(bases_aslist) < 0) {
1581         Py_DECREF(to_merge);
1582         Py_DECREF(bases_aslist);
1583         return NULL;
1584     }
1585     PyList_SET_ITEM(to_merge, n, bases_aslist);
1586 
1587     result = Py_BuildValue("[O]", (PyObject *)type);
1588     if (result == NULL) {
1589         Py_DECREF(to_merge);
1590         return NULL;
1591     }
1592 
1593     ok = pmerge(result, to_merge);
1594     Py_DECREF(to_merge);
1595     if (ok < 0) {
1596         Py_DECREF(result);
1597         return NULL;
1598     }
1599 
1600     return result;
1601 }
1602 
1603 static PyObject *
1604 mro_external(PyObject *self)
1605 {
1606     PyTypeObject *type = (PyTypeObject *)self;
1607 
1608     return mro_implementation(type);
1609 }
1610 
1611 static int
1612 mro_internal(PyTypeObject *type)
1613 {
1614     PyObject *mro, *result, *tuple;
1615     int checkit = 0;
1616 
1617     if (Py_TYPE(type) == &PyType_Type) {
1618         result = mro_implementation(type);
1619     }
1620     else {
1621         static PyObject *mro_str;
1622         checkit = 1;
1623         mro = lookup_method((PyObject *)type, "mro", &mro_str);
1624         if (mro == NULL)
1625             return -1;
1626         result = PyObject_CallObject(mro, NULL);
1627         Py_DECREF(mro);
1628     }
1629     if (result == NULL)
1630         return -1;
1631     tuple = PySequence_Tuple(result);
1632     Py_DECREF(result);
1633     if (tuple == NULL)
1634         return -1;
1635     if (checkit) {
1636         Py_ssize_t i, len;
1637         PyObject *cls;
1638         PyTypeObject *solid;
1639 
1640         solid = solid_base(type);
1641 
1642         len = PyTuple_GET_SIZE(tuple);
1643 
1644         for (i = 0; i < len; i++) {
1645             PyTypeObject *t;
1646             cls = PyTuple_GET_ITEM(tuple, i);
1647             if (PyClass_Check(cls))
1648                 continue;
1649             else if (!PyType_Check(cls)) {
1650                 PyErr_Format(PyExc_TypeError,
1651                  "mro() returned a non-class ('%.500s')",
1652                                  Py_TYPE(cls)->tp_name);
1653                 Py_DECREF(tuple);
1654                 return -1;
1655             }
1656             t = (PyTypeObject*)cls;
1657             if (!PyType_IsSubtype(solid, solid_base(t))) {
1658                 PyErr_Format(PyExc_TypeError,
1659              "mro() returned base with unsuitable layout ('%.500s')",
1660                                      t->tp_name);
1661                         Py_DECREF(tuple);
1662                         return -1;
1663             }
1664         }
1665     }
1666     type->tp_mro = tuple;
1667 
1668     type_mro_modified(type, type->tp_mro);
1669     /* corner case: the old-style super class might have been hidden
1670        from the custom MRO */
1671     type_mro_modified(type, type->tp_bases);
1672 
1673     PyType_Modified(type);
1674 
1675     return 0;
1676 }
1677 
1678 
1679 /* Calculate the best base amongst multiple base classes.
1680    This is the first one that's on the path to the "solid base". */
1681 
1682 static PyTypeObject *
1683 best_base(PyObject *bases)
1684 {
1685     Py_ssize_t i, n;
1686     PyTypeObject *base, *winner, *candidate, *base_i;
1687     PyObject *base_proto;
1688 
1689     assert(PyTuple_Check(bases));
1690     n = PyTuple_GET_SIZE(bases);
1691     assert(n > 0);
1692     base = NULL;
1693     winner = NULL;
1694     for (i = 0; i < n; i++) {
1695         base_proto = PyTuple_GET_ITEM(bases, i);
1696         if (PyClass_Check(base_proto))
1697             continue;
1698         if (!PyType_Check(base_proto)) {
1699             PyErr_SetString(
1700                 PyExc_TypeError,
1701                 "bases must be types");
1702             return NULL;
1703         }
1704         base_i = (PyTypeObject *)base_proto;
1705         if (base_i->tp_dict == NULL) {
1706             if (PyType_Ready(base_i) < 0)
1707                 return NULL;
1708         }
1709         candidate = solid_base(base_i);
1710         if (winner == NULL) {
1711             winner = candidate;
1712             base = base_i;
1713         }
1714         else if (PyType_IsSubtype(winner, candidate))
1715             ;
1716         else if (PyType_IsSubtype(candidate, winner)) {
1717             winner = candidate;
1718             base = base_i;
1719         }
1720         else {
1721             PyErr_SetString(
1722                 PyExc_TypeError,
1723                 "multiple bases have "
1724                 "instance lay-out conflict");
1725             return NULL;
1726         }
1727     }
1728     if (base == NULL)
1729         PyErr_SetString(PyExc_TypeError,
1730             "a new-style class can't have only classic bases");
1731     return base;
1732 }
1733 
1734 static int
1735 extra_ivars(PyTypeObject *type, PyTypeObject *base)
1736 {
1737     size_t t_size = type->tp_basicsize;
1738     size_t b_size = base->tp_basicsize;
1739 
1740     assert(t_size >= b_size); /* Else type smaller than base! */
1741     if (type->tp_itemsize || base->tp_itemsize) {
1742         /* If itemsize is involved, stricter rules */
1743         return t_size != b_size ||
1744             type->tp_itemsize != base->tp_itemsize;
1745     }
1746     if (type->tp_weaklistoffset && base->tp_weaklistoffset == 0 &&
1747         type->tp_weaklistoffset + sizeof(PyObject *) == t_size &&
1748         type->tp_flags & Py_TPFLAGS_HEAPTYPE)
1749         t_size -= sizeof(PyObject *);
1750     if (type->tp_dictoffset && base->tp_dictoffset == 0 &&
1751         type->tp_dictoffset + sizeof(PyObject *) == t_size &&
1752         type->tp_flags & Py_TPFLAGS_HEAPTYPE)
1753         t_size -= sizeof(PyObject *);
1754 
1755     return t_size != b_size;
1756 }
1757 
1758 static PyTypeObject *
1759 solid_base(PyTypeObject *type)
1760 {
1761     PyTypeObject *base;
1762 
1763     if (type->tp_base)
1764         base = solid_base(type->tp_base);
1765     else
1766         base = &PyBaseObject_Type;
1767     if (extra_ivars(type, base))
1768         return type;
1769     else
1770         return base;
1771 }
1772 
1773 static void object_dealloc(PyObject *);
1774 static int object_init(PyObject *, PyObject *, PyObject *);
1775 static int update_slot(PyTypeObject *, PyObject *);
1776 static void fixup_slot_dispatchers(PyTypeObject *);
1777 
1778 /*
1779  * Helpers for  __dict__ descriptor.  We don't want to expose the dicts
1780  * inherited from various builtin types.  The builtin base usually provides
1781  * its own __dict__ descriptor, so we use that when we can.
1782  */
1783 static PyTypeObject *
1784 get_builtin_base_with_dict(PyTypeObject *type)
1785 {
1786     while (type->tp_base != NULL) {
1787         if (type->tp_dictoffset != 0 &&
1788             !(type->tp_flags & Py_TPFLAGS_HEAPTYPE))
1789             return type;
1790         type = type->tp_base;
1791     }
1792     return NULL;
1793 }
1794 
1795 static PyObject *
1796 get_dict_descriptor(PyTypeObject *type)
1797 {
1798     static PyObject *dict_str;
1799     PyObject *descr;
1800 
1801     if (dict_str == NULL) {
1802         dict_str = PyString_InternFromString("__dict__");
1803         if (dict_str == NULL)
1804             return NULL;
1805     }
1806     descr = _PyType_Lookup(type, dict_str);
1807     if (descr == NULL || !PyDescr_IsData(descr))
1808         return NULL;
1809 
1810     return descr;
1811 }
1812 
1813 static void
1814 raise_dict_descr_error(PyObject *obj)
1815 {
1816     PyErr_Format(PyExc_TypeError,
1817                  "this __dict__ descriptor does not support "
1818                  "'%.200s' objects", obj->ob_type->tp_name);
1819 }
1820 
1821 static PyObject *
1822 subtype_dict(PyObject *obj, void *context)
1823 {
1824     PyObject **dictptr;
1825     PyObject *dict;
1826     PyTypeObject *base;
1827 
1828     base = get_builtin_base_with_dict(obj->ob_type);
1829     if (base != NULL) {
1830         descrgetfunc func;
1831         PyObject *descr = get_dict_descriptor(base);
1832         if (descr == NULL) {
1833             raise_dict_descr_error(obj);
1834             return NULL;
1835         }
1836         func = descr->ob_type->tp_descr_get;
1837         if (func == NULL) {
1838             raise_dict_descr_error(obj);
1839             return NULL;
1840         }
1841         return func(descr, obj, (PyObject *)(obj->ob_type));
1842     }
1843 
1844     dictptr = _PyObject_GetDictPtr(obj);
1845     if (dictptr == NULL) {
1846         PyErr_SetString(PyExc_AttributeError,
1847                         "This object has no __dict__");
1848         return NULL;
1849     }
1850     dict = *dictptr;
1851     if (dict == NULL)
1852         *dictptr = dict = PyDict_New();
1853     Py_XINCREF(dict);
1854     return dict;
1855 }
1856 
1857 static int
1858 subtype_setdict(PyObject *obj, PyObject *value, void *context)
1859 {
1860     PyObject **dictptr;
1861     PyObject *dict;
1862     PyTypeObject *base;
1863 
1864     base = get_builtin_base_with_dict(obj->ob_type);
1865     if (base != NULL) {
1866         descrsetfunc func;
1867         PyObject *descr = get_dict_descriptor(base);
1868         if (descr == NULL) {
1869             raise_dict_descr_error(obj);
1870             return -1;
1871         }
1872         func = descr->ob_type->tp_descr_set;
1873         if (func == NULL) {
1874             raise_dict_descr_error(obj);
1875             return -1;
1876         }
1877         return func(descr, obj, value);
1878     }
1879 
1880     dictptr = _PyObject_GetDictPtr(obj);
1881     if (dictptr == NULL) {
1882         PyErr_SetString(PyExc_AttributeError,
1883                         "This object has no __dict__");
1884         return -1;
1885     }
1886     if (value != NULL && !PyDict_Check(value)) {
1887         PyErr_Format(PyExc_TypeError,
1888                      "__dict__ must be set to a dictionary, "
1889                      "not a '%.200s'", Py_TYPE(value)->tp_name);
1890         return -1;
1891     }
1892     dict = *dictptr;
1893     Py_XINCREF(value);
1894     *dictptr = value;
1895     Py_XDECREF(dict);
1896     return 0;
1897 }
1898 
1899 static PyObject *
1900 subtype_getweakref(PyObject *obj, void *context)
1901 {
1902     PyObject **weaklistptr;
1903     PyObject *result;
1904 
1905     if (Py_TYPE(obj)->tp_weaklistoffset == 0) {
1906         PyErr_SetString(PyExc_AttributeError,
1907                         "This object has no __weakref__");
1908         return NULL;
1909     }
1910     assert(Py_TYPE(obj)->tp_weaklistoffset > 0);
1911     assert(Py_TYPE(obj)->tp_weaklistoffset + sizeof(PyObject *) <=
1912            (size_t)(Py_TYPE(obj)->tp_basicsize));
1913     weaklistptr = (PyObject **)
1914         ((char *)obj + Py_TYPE(obj)->tp_weaklistoffset);
1915     if (*weaklistptr == NULL)
1916         result = Py_None;
1917     else
1918         result = *weaklistptr;
1919     Py_INCREF(result);
1920     return result;
1921 }
1922 
1923 /* Three variants on the subtype_getsets list. */
1924 
1925 static PyGetSetDef subtype_getsets_full[] = {
1926     {"__dict__", subtype_dict, subtype_setdict,
1927      PyDoc_STR("dictionary for instance variables (if defined)")},
1928     {"__weakref__", subtype_getweakref, NULL,
1929      PyDoc_STR("list of weak references to the object (if defined)")},
1930     {0}
1931 };
1932 
1933 static PyGetSetDef subtype_getsets_dict_only[] = {
1934     {"__dict__", subtype_dict, subtype_setdict,
1935      PyDoc_STR("dictionary for instance variables (if defined)")},
1936     {0}
1937 };
1938 
1939 static PyGetSetDef subtype_getsets_weakref_only[] = {
1940     {"__weakref__", subtype_getweakref, NULL,
1941      PyDoc_STR("list of weak references to the object (if defined)")},
1942     {0}
1943 };
1944 
1945 static int
1946 valid_identifier(PyObject *s)
1947 {
1948     unsigned char *p;
1949     Py_ssize_t i, n;
1950 
1951     if (!PyString_Check(s)) {
1952         PyErr_Format(PyExc_TypeError,
1953                      "__slots__ items must be strings, not '%.200s'",
1954                      Py_TYPE(s)->tp_name);
1955         return 0;
1956     }
1957     p = (unsigned char *) PyString_AS_STRING(s);
1958     n = PyString_GET_SIZE(s);
1959     /* We must reject an empty name.  As a hack, we bump the
1960        length to 1 so that the loop will balk on the trailing \0. */
1961     if (n == 0)
1962         n = 1;
1963     for (i = 0; i < n; i++, p++) {
1964         if (!(i == 0 ? isalpha(*p) : isalnum(*p)) && *p != '_') {
1965             PyErr_SetString(PyExc_TypeError,
1966                             "__slots__ must be identifiers");
1967             return 0;
1968         }
1969     }
1970     return 1;
1971 }
1972 
1973 #ifdef Py_USING_UNICODE
1974 /* Replace Unicode objects in slots.  */
1975 
1976 static PyObject *
1977 _unicode_to_string(PyObject *slots, Py_ssize_t nslots)
1978 {
1979     PyObject *tmp = NULL;
1980     PyObject *slot_name, *new_name;
1981     Py_ssize_t i;
1982 
1983     for (i = 0; i < nslots; i++) {
1984         if (PyUnicode_Check(slot_name = PyTuple_GET_ITEM(slots, i))) {
1985             if (tmp == NULL) {
1986                 tmp = PySequence_List(slots);
1987                 if (tmp == NULL)
1988                     return NULL;
1989             }
1990             new_name = _PyUnicode_AsDefaultEncodedString(slot_name,
1991                                                          NULL);
1992             if (new_name == NULL) {
1993                 Py_DECREF(tmp);
1994                 return NULL;
1995             }
1996             Py_INCREF(new_name);
1997             PyList_SET_ITEM(tmp, i, new_name);
1998             Py_DECREF(slot_name);
1999         }
2000     }
2001     if (tmp != NULL) {
2002         slots = PyList_AsTuple(tmp);
2003         Py_DECREF(tmp);
2004     }
2005     return slots;
2006 }
2007 #endif
2008 
2009 /* Forward */
2010 static int
2011 object_init(PyObject *self, PyObject *args, PyObject *kwds);
2012 
2013 static int
2014 type_init(PyObject *cls, PyObject *args, PyObject *kwds)
2015 {
2016     int res;
2017 
2018     assert(args != NULL && PyTuple_Check(args));
2019     assert(kwds == NULL || PyDict_Check(kwds));
2020 
2021     if (kwds != NULL && PyDict_Check(kwds) && PyDict_Size(kwds) != 0) {
2022         PyErr_SetString(PyExc_TypeError,
2023                         "type.__init__() takes no keyword arguments");
2024         return -1;
2025     }
2026 
2027     if (args != NULL && PyTuple_Check(args) &&
2028         (PyTuple_GET_SIZE(args) != 1 && PyTuple_GET_SIZE(args) != 3)) {
2029         PyErr_SetString(PyExc_TypeError,
2030                         "type.__init__() takes 1 or 3 arguments");
2031         return -1;
2032     }
2033 
2034     /* Call object.__init__(self) now. */
2035     /* XXX Could call super(type, cls).__init__() but what's the point? */
2036     args = PyTuple_GetSlice(args, 0, 0);
2037     res = object_init(cls, args, NULL);
2038     Py_DECREF(args);
2039     return res;
2040 }
2041 
2042 static PyObject *
2043 type_new(PyTypeObject *metatype, PyObject *args, PyObject *kwds)
2044 {
2045     PyObject *name, *bases, *dict;
2046     static char *kwlist[] = {"name", "bases", "dict", 0};
2047     PyObject *slots, *tmp, *newslots;
2048     PyTypeObject *type, *base, *tmptype, *winner;
2049     PyHeapTypeObject *et;
2050     PyMemberDef *mp;
2051     Py_ssize_t i, nbases, nslots, slotoffset, add_dict, add_weak;
2052     int j, may_add_dict, may_add_weak;
2053 
2054     assert(args != NULL && PyTuple_Check(args));
2055     assert(kwds == NULL || PyDict_Check(kwds));
2056 
2057     /* Special case: type(x) should return x->ob_type */
2058     {
2059         const Py_ssize_t nargs = PyTuple_GET_SIZE(args);
2060         const Py_ssize_t nkwds = kwds == NULL ? 0 : PyDict_Size(kwds);
2061 
2062         if (PyType_CheckExact(metatype) && nargs == 1 && nkwds == 0) {
2063             PyObject *x = PyTuple_GET_ITEM(args, 0);
2064             Py_INCREF(Py_TYPE(x));
2065             return (PyObject *) Py_TYPE(x);
2066         }
2067 
2068         /* SF bug 475327 -- if that didn't trigger, we need 3
2069            arguments. but PyArg_ParseTupleAndKeywords below may give
2070            a msg saying type() needs exactly 3. */
2071         if (nargs + nkwds != 3) {
2072             PyErr_SetString(PyExc_TypeError,
2073                             "type() takes 1 or 3 arguments");
2074             return NULL;
2075         }
2076     }
2077 
2078     /* Check arguments: (name, bases, dict) */
2079     if (!PyArg_ParseTupleAndKeywords(args, kwds, "SO!O!:type", kwlist,
2080                                      &name,
2081                                      &PyTuple_Type, &bases,
2082                                      &PyDict_Type, &dict))
2083         return NULL;
2084 
2085     /* Determine the proper metatype to deal with this,
2086        and check for metatype conflicts while we're at it.
2087        Note that if some other metatype wins to contract,
2088        it's possible that its instances are not types. */
2089     nbases = PyTuple_GET_SIZE(bases);
2090     winner = metatype;
2091     for (i = 0; i < nbases; i++) {
2092         tmp = PyTuple_GET_ITEM(bases, i);
2093         tmptype = tmp->ob_type;
2094         if (tmptype == &PyClass_Type)
2095             continue; /* Special case classic classes */
2096         if (PyType_IsSubtype(winner, tmptype))
2097             continue;
2098         if (PyType_IsSubtype(tmptype, winner)) {
2099             winner = tmptype;
2100             continue;
2101         }
2102         PyErr_SetString(PyExc_TypeError,
2103                         "metaclass conflict: "
2104                         "the metaclass of a derived class "
2105                         "must be a (non-strict) subclass "
2106                         "of the metaclasses of all its bases");
2107         return NULL;
2108     }
2109     if (winner != metatype) {
2110         if (winner->tp_new != type_new) /* Pass it to the winner */
2111             return winner->tp_new(winner, args, kwds);
2112         metatype = winner;
2113     }
2114 
2115     /* Adjust for empty tuple bases */
2116     if (nbases == 0) {
2117         bases = PyTuple_Pack(1, &PyBaseObject_Type);
2118         if (bases == NULL)
2119             return NULL;
2120         nbases = 1;
2121     }
2122     else
2123         Py_INCREF(bases);
2124 
2125     /* XXX From here until type is allocated, "return NULL" leaks bases! */
2126 
2127     /* Calculate best base, and check that all bases are type objects */
2128     base = best_base(bases);
2129     if (base == NULL) {
2130         Py_DECREF(bases);
2131         return NULL;
2132     }
2133     if (!PyType_HasFeature(base, Py_TPFLAGS_BASETYPE)) {
2134         PyErr_Format(PyExc_TypeError,
2135                      "type '%.100s' is not an acceptable base type",
2136                      base->tp_name);
2137         Py_DECREF(bases);
2138         return NULL;
2139     }
2140 
2141     /* Check for a __slots__ sequence variable in dict, and count it */
2142     slots = PyDict_GetItemString(dict, "__slots__");
2143     nslots = 0;
2144     add_dict = 0;
2145     add_weak = 0;
2146     may_add_dict = base->tp_dictoffset == 0;
2147     may_add_weak = base->tp_weaklistoffset == 0 && base->tp_itemsize == 0;
2148     if (slots == NULL) {
2149         if (may_add_dict) {
2150             add_dict++;
2151         }
2152         if (may_add_weak) {
2153             add_weak++;
2154         }
2155     }
2156     else {
2157         /* Have slots */
2158 
2159         /* Make it into a tuple */
2160         if (PyString_Check(slots) || PyUnicode_Check(slots))
2161             slots = PyTuple_Pack(1, slots);
2162         else
2163             slots = PySequence_Tuple(slots);
2164         if (slots == NULL) {
2165             Py_DECREF(bases);
2166             return NULL;
2167         }
2168         assert(PyTuple_Check(slots));
2169 
2170         /* Are slots allowed? */
2171         nslots = PyTuple_GET_SIZE(slots);
2172         if (nslots > 0 && base->tp_itemsize != 0) {
2173             PyErr_Format(PyExc_TypeError,
2174                          "nonempty __slots__ "
2175                          "not supported for subtype of '%s'",
2176                          base->tp_name);
2177           bad_slots:
2178             Py_DECREF(bases);
2179             Py_DECREF(slots);
2180             return NULL;
2181         }
2182 
2183 #ifdef Py_USING_UNICODE
2184         tmp = _unicode_to_string(slots, nslots);
2185         if (tmp == NULL)
2186             goto bad_slots;
2187         if (tmp != slots) {
2188             Py_DECREF(slots);
2189             slots = tmp;
2190         }
2191 #endif
2192         /* Check for valid slot names and two special cases */
2193         for (i = 0; i < nslots; i++) {
2194             PyObject *tmp = PyTuple_GET_ITEM(slots, i);
2195             char *s;
2196             if (!valid_identifier(tmp))
2197                 goto bad_slots;
2198             assert(PyString_Check(tmp));
2199             s = PyString_AS_STRING(tmp);
2200             if (strcmp(s, "__dict__") == 0) {
2201                 if (!may_add_dict || add_dict) {
2202                     PyErr_SetString(PyExc_TypeError,
2203                         "__dict__ slot disallowed: "
2204                         "we already got one");
2205                     goto bad_slots;
2206                 }
2207                 add_dict++;
2208             }
2209             if (strcmp(s, "__weakref__") == 0) {
2210                 if (!may_add_weak || add_weak) {
2211                     PyErr_SetString(PyExc_TypeError,
2212                         "__weakref__ slot disallowed: "
2213                         "either we already got one, "
2214                         "or __itemsize__ != 0");
2215                     goto bad_slots;
2216                 }
2217                 add_weak++;
2218             }
2219         }
2220 
2221         /* Copy slots into a list, mangle names and sort them.
2222            Sorted names are needed for __class__ assignment.
2223            Convert them back to tuple at the end.
2224         */
2225         newslots = PyList_New(nslots - add_dict - add_weak);
2226         if (newslots == NULL)
2227             goto bad_slots;
2228         for (i = j = 0; i < nslots; i++) {
2229             char *s;
2230             tmp = PyTuple_GET_ITEM(slots, i);
2231             s = PyString_AS_STRING(tmp);
2232             if ((add_dict && strcmp(s, "__dict__") == 0) ||
2233                 (add_weak && strcmp(s, "__weakref__") == 0))
2234                 continue;
2235             tmp =_Py_Mangle(name, tmp);
2236             if (!tmp) {
2237                 Py_DECREF(newslots);
2238                 goto bad_slots;
2239             }
2240             PyList_SET_ITEM(newslots, j, tmp);
2241             j++;
2242         }
2243         assert(j == nslots - add_dict - add_weak);
2244         nslots = j;
2245         Py_DECREF(slots);
2246         if (PyList_Sort(newslots) == -1) {
2247             Py_DECREF(bases);
2248             Py_DECREF(newslots);
2249             return NULL;
2250         }
2251         slots = PyList_AsTuple(newslots);
2252         Py_DECREF(newslots);
2253         if (slots == NULL) {
2254             Py_DECREF(bases);
2255             return NULL;
2256         }
2257 
2258         /* Secondary bases may provide weakrefs or dict */
2259         if (nbases > 1 &&
2260             ((may_add_dict && !add_dict) ||
2261              (may_add_weak && !add_weak))) {
2262             for (i = 0; i < nbases; i++) {
2263                 tmp = PyTuple_GET_ITEM(bases, i);
2264                 if (tmp == (PyObject *)base)
2265                     continue; /* Skip primary base */
2266                 if (PyClass_Check(tmp)) {
2267                     /* Classic base class provides both */
2268                     if (may_add_dict && !add_dict)
2269                         add_dict++;
2270                     if (may_add_weak && !add_weak)
2271                         add_weak++;
2272                     break;
2273                 }
2274                 assert(PyType_Check(tmp));
2275                 tmptype = (PyTypeObject *)tmp;
2276                 if (may_add_dict && !add_dict &&
2277                     tmptype->tp_dictoffset != 0)
2278                     add_dict++;
2279                 if (may_add_weak && !add_weak &&
2280                     tmptype->tp_weaklistoffset != 0)
2281                     add_weak++;
2282                 if (may_add_dict && !add_dict)
2283                     continue;
2284                 if (may_add_weak && !add_weak)
2285                     continue;
2286                 /* Nothing more to check */
2287                 break;
2288             }
2289         }
2290     }
2291 
2292     /* XXX From here until type is safely allocated,
2293        "return NULL" may leak slots! */
2294 
2295     /* Allocate the type object */
2296     type = (PyTypeObject *)metatype->tp_alloc(metatype, nslots);
2297     if (type == NULL) {
2298         Py_XDECREF(slots);
2299         Py_DECREF(bases);
2300         return NULL;
2301     }
2302 
2303     /* Keep name and slots alive in the extended type object */
2304     et = (PyHeapTypeObject *)type;
2305     Py_INCREF(name);
2306     et->ht_name = name;
2307     et->ht_slots = slots;
2308 
2309     /* Initialize tp_flags */
2310     type->tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HEAPTYPE |
2311         Py_TPFLAGS_BASETYPE;
2312     if (base->tp_flags & Py_TPFLAGS_HAVE_GC)
2313         type->tp_flags |= Py_TPFLAGS_HAVE_GC;
2314     if (base->tp_flags & Py_TPFLAGS_HAVE_NEWBUFFER)
2315         type->tp_flags |= Py_TPFLAGS_HAVE_NEWBUFFER;
2316 
2317     /* It's a new-style number unless it specifically inherits any
2318        old-style numeric behavior */
2319     if ((base->tp_flags & Py_TPFLAGS_CHECKTYPES) ||
2320         (base->tp_as_number == NULL))
2321         type->tp_flags |= Py_TPFLAGS_CHECKTYPES;
2322 
2323     /* Initialize essential fields */
2324     type->tp_as_number = &et->as_number;
2325     type->tp_as_sequence = &et->as_sequence;
2326     type->tp_as_mapping = &et->as_mapping;
2327     type->tp_as_buffer = &et->as_buffer;
2328     type->tp_name = PyString_AS_STRING(name);
2329 
2330     /* Set tp_base and tp_bases */
2331     type->tp_bases = bases;
2332     Py_INCREF(base);
2333     type->tp_base = base;
2334 
2335     /* Initialize tp_dict from passed-in dict */
2336     type->tp_dict = dict = PyDict_Copy(dict);
2337     if (dict == NULL) {
2338         Py_DECREF(type);
2339         return NULL;
2340     }
2341 
2342     /* Set __module__ in the dict */
2343     if (PyDict_GetItemString(dict, "__module__") == NULL) {
2344         tmp = PyEval_GetGlobals();
2345         if (tmp != NULL) {
2346             tmp = PyDict_GetItemString(tmp, "__name__");
2347             if (tmp != NULL) {
2348                 if (PyDict_SetItemString(dict, "__module__",
2349                                          tmp) < 0)
2350                     return NULL;
2351             }
2352         }
2353     }
2354 
2355     /* Set tp_doc to a copy of dict['__doc__'], if the latter is there
2356        and is a string.  The __doc__ accessor will first look for tp_doc;
2357        if that fails, it will still look into __dict__.
2358     */
2359     {
2360         PyObject *doc = PyDict_GetItemString(dict, "__doc__");
2361         if (doc != NULL && PyString_Check(doc)) {
2362             const size_t n = (size_t)PyString_GET_SIZE(doc);
2363             char *tp_doc = (char *)PyObject_MALLOC(n+1);
2364             if (tp_doc == NULL) {
2365                 Py_DECREF(type);
2366                 return NULL;
2367             }
2368             memcpy(tp_doc, PyString_AS_STRING(doc), n+1);
2369             type->tp_doc = tp_doc;
2370         }
2371     }
2372 
2373     /* Special-case __new__: if it's a plain function,
2374        make it a static function */
2375     tmp = PyDict_GetItemString(dict, "__new__");
2376     if (tmp != NULL && PyFunction_Check(tmp)) {
2377         tmp = PyStaticMethod_New(tmp);
2378         if (tmp == NULL) {
2379             Py_DECREF(type);
2380             return NULL;
2381         }
2382         PyDict_SetItemString(dict, "__new__", tmp);
2383         Py_DECREF(tmp);
2384     }
2385 
2386     /* Add descriptors for custom slots from __slots__, or for __dict__ */
2387     mp = PyHeapType_GET_MEMBERS(et);
2388     slotoffset = base->tp_basicsize;
2389     if (slots != NULL) {
2390         for (i = 0; i < nslots; i++, mp++) {
2391             mp->name = PyString_AS_STRING(
2392                 PyTuple_GET_ITEM(slots, i));
2393             mp->type = T_OBJECT_EX;
2394             mp->offset = slotoffset;
2395 
2396             /* __dict__ and __weakref__ are already filtered out */
2397             assert(strcmp(mp->name, "__dict__") != 0);
2398             assert(strcmp(mp->name, "__weakref__") != 0);
2399 
2400             slotoffset += sizeof(PyObject *);
2401         }
2402     }
2403     if (add_dict) {
2404         if (base->tp_itemsize)
2405             type->tp_dictoffset = -(long)sizeof(PyObject *);
2406         else
2407             type->tp_dictoffset = slotoffset;
2408         slotoffset += sizeof(PyObject *);
2409     }
2410     if (add_weak) {
2411         assert(!base->tp_itemsize);
2412         type->tp_weaklistoffset = slotoffset;
2413         slotoffset += sizeof(PyObject *);
2414     }
2415     type->tp_basicsize = slotoffset;
2416     type->tp_itemsize = base->tp_itemsize;
2417     type->tp_members = PyHeapType_GET_MEMBERS(et);
2418 
2419     if (type->tp_weaklistoffset && type->tp_dictoffset)
2420         type->tp_getset = subtype_getsets_full;
2421     else if (type->tp_weaklistoffset && !type->tp_dictoffset)
2422         type->tp_getset = subtype_getsets_weakref_only;
2423     else if (!type->tp_weaklistoffset && type->tp_dictoffset)
2424         type->tp_getset = subtype_getsets_dict_only;
2425     else
2426         type->tp_getset = NULL;
2427 
2428     /* Special case some slots */
2429     if (type->tp_dictoffset != 0 || nslots > 0) {
2430         if (base->tp_getattr == NULL && base->tp_getattro == NULL)
2431             type->tp_getattro = PyObject_GenericGetAttr;
2432         if (base->tp_setattr == NULL && base->tp_setattro == NULL)
2433             type->tp_setattro = PyObject_GenericSetAttr;
2434     }
2435     type->tp_dealloc = subtype_dealloc;
2436 
2437     /* Enable GC unless there are really no instance variables possible */
2438     if (!(type->tp_basicsize == sizeof(PyObject) &&
2439           type->tp_itemsize == 0))
2440         type->tp_flags |= Py_TPFLAGS_HAVE_GC;
2441 
2442     /* Always override allocation strategy to use regular heap */
2443     type->tp_alloc = PyType_GenericAlloc;
2444     if (type->tp_flags & Py_TPFLAGS_HAVE_GC) {
2445         type->tp_free = PyObject_GC_Del;
2446         type->tp_traverse = subtype_traverse;
2447         type->tp_clear = subtype_clear;
2448     }
2449     else
2450         type->tp_free = PyObject_Del;
2451 
2452     /* Initialize the rest */
2453     if (PyType_Ready(type) < 0) {
2454         Py_DECREF(type);
2455         return NULL;
2456     }
2457 
2458     /* Put the proper slots in place */
2459     fixup_slot_dispatchers(type);
2460 
2461     return (PyObject *)type;
2462 }
2463 
2464 /* Internal API to look for a name through the MRO.
2465    This returns a borrowed reference, and doesn't set an exception! */
2466 PyObject *
2467 _PyType_Lookup(PyTypeObject *type, PyObject *name)
2468 {
2469     Py_ssize_t i, n;
2470     PyObject *mro, *res, *base, *dict;
2471     unsigned int h;
2472 
2473     if (MCACHE_CACHEABLE_NAME(name) &&
2474         PyType_HasFeature(type, Py_TPFLAGS_VALID_VERSION_TAG)) {
2475         /* fast path */
2476         h = MCACHE_HASH_METHOD(type, name);
2477         if (method_cache[h].version == type->tp_version_tag &&
2478             method_cache[h].name == name)
2479             return method_cache[h].value;
2480     }
2481 
2482     /* Look in tp_dict of types in MRO */
2483     mro = type->tp_mro;
2484 
2485     /* If mro is NULL, the type is either not yet initialized
2486        by PyType_Ready(), or already cleared by type_clear().
2487        Either way the safest thing to do is to return NULL. */
2488     if (mro == NULL)
2489         return NULL;
2490 
2491     res = NULL;
2492     assert(PyTuple_Check(mro));
2493     n = PyTuple_GET_SIZE(mro);
2494     for (i = 0; i < n; i++) {
2495         base = PyTuple_GET_ITEM(mro, i);
2496         if (PyClass_Check(base))
2497             dict = ((PyClassObject *)base)->cl_dict;
2498         else {
2499             assert(PyType_Check(base));
2500             dict = ((PyTypeObject *)base)->tp_dict;
2501         }
2502         assert(dict && PyDict_Check(dict));
2503         res = PyDict_GetItem(dict, name);
2504         if (res != NULL)
2505             break;
2506     }
2507 
2508     if (MCACHE_CACHEABLE_NAME(name) && assign_version_tag(type)) {
2509         h = MCACHE_HASH_METHOD(type, name);
2510         method_cache[h].version = type->tp_version_tag;
2511         method_cache[h].value = res;  /* borrowed */
2512         Py_INCREF(name);
2513         Py_DECREF(method_cache[h].name);
2514         method_cache[h].name = name;
2515     }
2516     return res;
2517 }
2518 
2519 /* This is similar to PyObject_GenericGetAttr(),
2520    but uses _PyType_Lookup() instead of just looking in type->tp_dict. */
2521 static PyObject *
2522 type_getattro(PyTypeObject *type, PyObject *name)
2523 {
2524     PyTypeObject *metatype = Py_TYPE(type);
2525     PyObject *meta_attribute, *attribute;
2526     descrgetfunc meta_get;
2527 
2528     /* Initialize this type (we'll assume the metatype is initialized) */
2529     if (type->tp_dict == NULL) {
2530         if (PyType_Ready(type) < 0)
2531             return NULL;
2532     }
2533 
2534     /* No readable descriptor found yet */
2535     meta_get = NULL;
2536 
2537     /* Look for the attribute in the metatype */
2538     meta_attribute = _PyType_Lookup(metatype, name);
2539 
2540     if (meta_attribute != NULL) {
2541         meta_get = Py_TYPE(meta_attribute)->tp_descr_get;
2542 
2543         if (meta_get != NULL && PyDescr_IsData(meta_attribute)) {
2544             /* Data descriptors implement tp_descr_set to intercept
2545              * writes. Assume the attribute is not overridden in
2546              * type's tp_dict (and bases): call the descriptor now.
2547              */
2548             return meta_get(meta_attribute, (PyObject *)type,
2549                             (PyObject *)metatype);
2550         }
2551         Py_INCREF(meta_attribute);
2552     }
2553 
2554     /* No data descriptor found on metatype. Look in tp_dict of this
2555      * type and its bases */
2556     attribute = _PyType_Lookup(type, name);
2557     if (attribute != NULL) {
2558         /* Implement descriptor functionality, if any */
2559         descrgetfunc local_get = Py_TYPE(attribute)->tp_descr_get;
2560 
2561         Py_XDECREF(meta_attribute);
2562 
2563         if (local_get != NULL) {
2564             /* NULL 2nd argument indicates the descriptor was
2565              * found on the target object itself (or a base)  */
2566             return local_get(attribute, (PyObject *)NULL,
2567                              (PyObject *)type);
2568         }
2569 
2570         Py_INCREF(attribute);
2571         return attribute;
2572     }
2573 
2574     /* No attribute found in local __dict__ (or bases): use the
2575      * descriptor from the metatype, if any */
2576     if (meta_get != NULL) {
2577         PyObject *res;
2578         res = meta_get(meta_attribute, (PyObject *)type,
2579                        (PyObject *)metatype);
2580         Py_DECREF(meta_attribute);
2581         return res;
2582     }
2583 
2584     /* If an ordinary attribute was found on the metatype, return it now */
2585     if (meta_attribute != NULL) {
2586         return meta_attribute;
2587     }
2588 
2589     /* Give up */
2590     PyErr_Format(PyExc_AttributeError,
2591                      "type object '%.50s' has no attribute '%.400s'",
2592                      type->tp_name, PyString_AS_STRING(name));
2593     return NULL;
2594 }
2595 
2596 static int
2597 type_setattro(PyTypeObject *type, PyObject *name, PyObject *value)
2598 {
2599     if (!(type->tp_flags & Py_TPFLAGS_HEAPTYPE)) {
2600         PyErr_Format(
2601             PyExc_TypeError,
2602             "can't set attributes of built-in/extension type '%s'",
2603             type->tp_name);
2604         return -1;
2605     }
2606     if (PyObject_GenericSetAttr((PyObject *)type, name, value) < 0)
2607         return -1;
2608     return update_slot(type, name);
2609 }
2610 
2611 static void
2612 type_dealloc(PyTypeObject *type)
2613 {
2614     PyHeapTypeObject *et;
2615 
2616     /* Assert this is a heap-allocated type object */
2617     assert(type->tp_flags & Py_TPFLAGS_HEAPTYPE);
2618     _PyObject_GC_UNTRACK(type);
2619     PyObject_ClearWeakRefs((PyObject *)type);
2620     et = (PyHeapTypeObject *)type;
2621     Py_XDECREF(type->tp_base);
2622     Py_XDECREF(type->tp_dict);
2623     Py_XDECREF(type->tp_bases);
2624     Py_XDECREF(type->tp_mro);
2625     Py_XDECREF(type->tp_cache);
2626     Py_XDECREF(type->tp_subclasses);
2627     /* A type's tp_doc is heap allocated, unlike the tp_doc slots
2628      * of most other objects.  It's okay to cast it to char *.
2629      */
2630     PyObject_Free((char *)type->tp_doc);
2631     Py_XDECREF(et->ht_name);
2632     Py_XDECREF(et->ht_slots);
2633     Py_TYPE(type)->tp_free((PyObject *)type);
2634 }
2635 
2636 static PyObject *
2637 type_subclasses(PyTypeObject *type, PyObject *args_ignored)
2638 {
2639     PyObject *list, *raw, *ref;
2640     Py_ssize_t i, n;
2641 
2642     list = PyList_New(0);
2643     if (list == NULL)
2644         return NULL;
2645     raw = type->tp_subclasses;
2646     if (raw == NULL)
2647         return list;
2648     assert(PyList_Check(raw));
2649     n = PyList_GET_SIZE(raw);
2650     for (i = 0; i < n; i++) {
2651         ref = PyList_GET_ITEM(raw, i);
2652         assert(PyWeakref_CheckRef(ref));
2653         ref = PyWeakref_GET_OBJECT(ref);
2654         if (ref != Py_None) {
2655             if (PyList_Append(list, ref) < 0) {
2656                 Py_DECREF(list);
2657                 return NULL;
2658             }
2659         }
2660     }
2661     return list;
2662 }
2663 
2664 static PyMethodDef type_methods[] = {
2665     {"mro", (PyCFunction)mro_external, METH_NOARGS,
2666      PyDoc_STR("mro() -> list\nreturn a type's method resolution order")},
2667     {"__subclasses__", (PyCFunction)type_subclasses, METH_NOARGS,
2668      PyDoc_STR("__subclasses__() -> list of immediate subclasses")},
2669     {"__instancecheck__", type___instancecheck__, METH_O,
2670      PyDoc_STR("__instancecheck__() -> bool\ncheck if an object is an instance")},
2671     {"__subclasscheck__", type___subclasscheck__, METH_O,
2672      PyDoc_STR("__subclasscheck__() -> bool\ncheck if a class is a subclass")},
2673     {0}
2674 };
2675 
2676 PyDoc_STRVAR(type_doc,
2677 "type(object) -> the object's type\n"
2678 "type(name, bases, dict) -> a new type");
2679 
2680 static int
2681 type_traverse(PyTypeObject *type, visitproc visit, void *arg)
2682 {
2683     /* Because of type_is_gc(), the collector only calls this
2684        for heaptypes. */
2685     assert(type->tp_flags & Py_TPFLAGS_HEAPTYPE);
2686 
2687     Py_VISIT(type->tp_dict);
2688     Py_VISIT(type->tp_cache);
2689     Py_VISIT(type->tp_mro);
2690     Py_VISIT(type->tp_bases);
2691     Py_VISIT(type->tp_base);
2692 
2693     /* There's no need to visit type->tp_subclasses or
2694        ((PyHeapTypeObject *)type)->ht_slots, because they can't be involved
2695        in cycles; tp_subclasses is a list of weak references,
2696        and slots is a tuple of strings. */
2697 
2698     return 0;
2699 }
2700 
2701 static int
2702 type_clear(PyTypeObject *type)
2703 {
2704     /* Because of type_is_gc(), the collector only calls this
2705        for heaptypes. */
2706     assert(type->tp_flags & Py_TPFLAGS_HEAPTYPE);
2707 
2708     /* We need to invalidate the method cache carefully before clearing
2709        the dict, so that other objects caught in a reference cycle
2710        don't start calling destroyed methods.
2711 
2712        Otherwise, the only field we need to clear is tp_mro, which is
2713        part of a hard cycle (its first element is the class itself) that
2714        won't be broken otherwise (it's a tuple and tuples don't have a
2715        tp_clear handler).  None of the other fields need to be
2716        cleared, and here's why:
2717 
2718        tp_cache:
2719            Not used; if it were, it would be a dict.
2720 
2721        tp_bases, tp_base:
2722            If these are involved in a cycle, there must be at least
2723            one other, mutable object in the cycle, e.g. a base
2724            class's dict; the cycle will be broken that way.
2725 
2726        tp_subclasses:
2727            A list of weak references can't be part of a cycle; and
2728            lists have their own tp_clear.
2729 
2730        slots (in PyHeapTypeObject):
2731            A tuple of strings can't be part of a cycle.
2732     */
2733 
2734     PyType_Modified(type);
2735     if (type->tp_dict)
2736         PyDict_Clear(type->tp_dict);
2737     Py_CLEAR(type->tp_mro);
2738 
2739     return 0;
2740 }
2741 
2742 static int
2743 type_is_gc(PyTypeObject *type)
2744 {
2745     return type->tp_flags & Py_TPFLAGS_HEAPTYPE;
2746 }
2747 
2748 PyTypeObject PyType_Type = {
2749     PyVarObject_HEAD_INIT(&PyType_Type, 0)
2750     "type",                                     /* tp_name */
2751     sizeof(PyHeapTypeObject),                   /* tp_basicsize */
2752     sizeof(PyMemberDef),                        /* tp_itemsize */
2753     (destructor)type_dealloc,                   /* tp_dealloc */
2754     0,                                          /* tp_print */
2755     0,                                          /* tp_getattr */
2756     0,                                          /* tp_setattr */
2757     0,                                  /* tp_compare */
2758     (reprfunc)type_repr,                        /* tp_repr */
2759     0,                                          /* tp_as_number */
2760     0,                                          /* tp_as_sequence */
2761     0,                                          /* tp_as_mapping */
2762     (hashfunc)_Py_HashPointer,                  /* tp_hash */
2763     (ternaryfunc)type_call,                     /* tp_call */
2764     0,                                          /* tp_str */
2765     (getattrofunc)type_getattro,                /* tp_getattro */
2766     (setattrofunc)type_setattro,                /* tp_setattro */
2767     0,                                          /* tp_as_buffer */
2768     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2769         Py_TPFLAGS_BASETYPE | Py_TPFLAGS_TYPE_SUBCLASS,         /* tp_flags */
2770     type_doc,                                   /* tp_doc */
2771     (traverseproc)type_traverse,                /* tp_traverse */
2772     (inquiry)type_clear,                        /* tp_clear */
2773     type_richcompare,                                           /* tp_richcompare */
2774     offsetof(PyTypeObject, tp_weaklist),        /* tp_weaklistoffset */
2775     0,                                          /* tp_iter */
2776     0,                                          /* tp_iternext */
2777     type_methods,                               /* tp_methods */
2778     type_members,                               /* tp_members */
2779     type_getsets,                               /* tp_getset */
2780     0,                                          /* tp_base */
2781     0,                                          /* tp_dict */
2782     0,                                          /* tp_descr_get */
2783     0,                                          /* tp_descr_set */
2784     offsetof(PyTypeObject, tp_dict),            /* tp_dictoffset */
2785     type_init,                                  /* tp_init */
2786     0,                                          /* tp_alloc */
2787     type_new,                                   /* tp_new */
2788     PyObject_GC_Del,                            /* tp_free */
2789     (inquiry)type_is_gc,                        /* tp_is_gc */
2790 };
2791 
2792 
2793 /* The base type of all types (eventually)... except itself. */
2794 
2795 /* You may wonder why object.__new__() only complains about arguments
2796    when object.__init__() is not overridden, and vice versa.
2797 
2798    Consider the use cases:
2799 
2800    1. When neither is overridden, we want to hear complaints about
2801       excess (i.e., any) arguments, since their presence could
2802       indicate there's a bug.
2803 
2804    2. When defining an Immutable type, we are likely to override only
2805       __new__(), since __init__() is called too late to initialize an
2806       Immutable object.  Since __new__() defines the signature for the
2807       type, it would be a pain to have to override __init__() just to
2808       stop it from complaining about excess arguments.
2809 
2810    3. When defining a Mutable type, we are likely to override only
2811       __init__().  So here the converse reasoning applies: we don't
2812       want to have to override __new__() just to stop it from
2813       complaining.
2814 
2815    4. When __init__() is overridden, and the subclass __init__() calls
2816       object.__init__(), the latter should complain about excess
2817       arguments; ditto for __new__().
2818 
2819    Use cases 2 and 3 make it unattractive to unconditionally check for
2820    excess arguments.  The best solution that addresses all four use
2821    cases is as follows: __init__() complains about excess arguments
2822    unless __new__() is overridden and __init__() is not overridden
2823    (IOW, if __init__() is overridden or __new__() is not overridden);
2824    symmetrically, __new__() complains about excess arguments unless
2825    __init__() is overridden and __new__() is not overridden
2826    (IOW, if __new__() is overridden or __init__() is not overridden).
2827 
2828    However, for backwards compatibility, this breaks too much code.
2829    Therefore, in 2.6, we'll *warn* about excess arguments when both
2830    methods are overridden; for all other cases we'll use the above
2831    rules.
2832 
2833 */
2834 
2835 /* Forward */
2836 static PyObject *
2837 object_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
2838 
2839 static int
2840 excess_args(PyObject *args, PyObject *kwds)
2841 {
2842     return PyTuple_GET_SIZE(args) ||
2843         (kwds && PyDict_Check(kwds) && PyDict_Size(kwds));
2844 }
2845 
2846 static int
2847 object_init(PyObject *self, PyObject *args, PyObject *kwds)
2848 {
2849     int err = 0;
2850     if (excess_args(args, kwds)) {
2851         PyTypeObject *type = Py_TYPE(self);
2852         if (type->tp_init != object_init &&
2853             type->tp_new != object_new)
2854         {
2855             err = PyErr_WarnEx(PyExc_DeprecationWarning,
2856                        "object.__init__() takes no parameters",
2857                        1);
2858         }
2859         else if (type->tp_init != object_init ||
2860                  type->tp_new == object_new)
2861         {
2862             PyErr_SetString(PyExc_TypeError,
2863                 "object.__init__() takes no parameters");
2864             err = -1;
2865         }
2866     }
2867     return err;
2868 }
2869 
2870 static PyObject *
2871 object_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2872 {
2873     int err = 0;
2874     if (excess_args(args, kwds)) {
2875         if (type->tp_new != object_new &&
2876             type->tp_init != object_init)
2877         {
2878             err = PyErr_WarnEx(PyExc_DeprecationWarning,
2879                        "object.__new__() takes no parameters",
2880                        1);
2881         }
2882         else if (type->tp_new != object_new ||
2883                  type->tp_init == object_init)
2884         {
2885             PyErr_SetString(PyExc_TypeError,
2886                 "object.__new__() takes no parameters");
2887             err = -1;
2888         }
2889     }
2890     if (err < 0)
2891         return NULL;
2892 
2893     if (type->tp_flags & Py_TPFLAGS_IS_ABSTRACT) {
2894         static PyObject *comma = NULL;
2895         PyObject *abstract_methods = NULL;
2896         PyObject *builtins;
2897         PyObject *sorted;
2898         PyObject *sorted_methods = NULL;
2899         PyObject *joined = NULL;
2900         const char *joined_str;
2901 
2902         /* Compute ", ".join(sorted(type.__abstractmethods__))
2903            into joined. */
2904         abstract_methods = type_abstractmethods(type, NULL);
2905         if (abstract_methods == NULL)
2906             goto error;
2907         builtins = PyEval_GetBuiltins();
2908         if (builtins == NULL)
2909             goto error;
2910         sorted = PyDict_GetItemString(builtins, "sorted");
2911         if (sorted == NULL)
2912             goto error;
2913         sorted_methods = PyObject_CallFunctionObjArgs(sorted,
2914                                                       abstract_methods,
2915                                                       NULL);
2916         if (sorted_methods == NULL)
2917             goto error;
2918         if (comma == NULL) {
2919             comma = PyString_InternFromString(", ");
2920             if (comma == NULL)
2921                 goto error;
2922         }
2923         joined = PyObject_CallMethod(comma, "join",
2924                                      "O",  sorted_methods);
2925         if (joined == NULL)
2926             goto error;
2927         joined_str = PyString_AsString(joined);
2928         if (joined_str == NULL)
2929             goto error;
2930 
2931         PyErr_Format(PyExc_TypeError,
2932                      "Can't instantiate abstract class %s "
2933                      "with abstract methods %s",
2934                      type->tp_name,
2935                      joined_str);
2936     error:
2937         Py_XDECREF(joined);
2938         Py_XDECREF(sorted_methods);
2939         Py_XDECREF(abstract_methods);
2940         return NULL;
2941     }
2942     return type->tp_alloc(type, 0);
2943 }
2944 
2945 static void
2946 object_dealloc(PyObject *self)
2947 {
2948     Py_TYPE(self)->tp_free(self);
2949 }
2950 
2951 static PyObject *
2952 object_repr(PyObject *self)
2953 {
2954     PyTypeObject *type;
2955     PyObject *mod, *name, *rtn;
2956 
2957     type = Py_TYPE(self);
2958     mod = type_module(type, NULL);
2959     if (mod == NULL)
2960         PyErr_Clear();
2961     else if (!PyString_Check(mod)) {
2962         Py_DECREF(mod);
2963         mod = NULL;
2964     }
2965     name = type_name(type, NULL);
2966     if (name == NULL)
2967         return NULL;
2968     if (mod != NULL && strcmp(PyString_AS_STRING(mod), "__builtin__"))
2969         rtn = PyString_FromFormat("<%s.%s object at %p>",
2970                                   PyString_AS_STRING(mod),
2971                                   PyString_AS_STRING(name),
2972                                   self);
2973     else
2974         rtn = PyString_FromFormat("<%s object at %p>",
2975                                   type->tp_name, self);
2976     Py_XDECREF(mod);
2977     Py_DECREF(name);
2978     return rtn;
2979 }
2980 
2981 static PyObject *
2982 object_str(PyObject *self)
2983 {
2984     unaryfunc f;
2985 
2986     f = Py_TYPE(self)->tp_repr;
2987     if (f == NULL || f == object_str)
2988         f = object_repr;
2989     return f(self);
2990 }
2991 
2992 static PyObject *
2993 object_get_class(PyObject *self, void *closure)
2994 {
2995     Py_INCREF(Py_TYPE(self));
2996     return (PyObject *)(Py_TYPE(self));
2997 }
2998 
2999 static int
3000 equiv_structs(PyTypeObject *a, PyTypeObject *b)
3001 {
3002     return a == b ||
3003            (a != NULL &&
3004         b != NULL &&
3005         a->tp_basicsize == b->tp_basicsize &&
3006         a->tp_itemsize == b->tp_itemsize &&
3007         a->tp_dictoffset == b->tp_dictoffset &&
3008         a->tp_weaklistoffset == b->tp_weaklistoffset &&
3009         ((a->tp_flags & Py_TPFLAGS_HAVE_GC) ==
3010          (b->tp_flags & Py_TPFLAGS_HAVE_GC)));
3011 }
3012 
3013 static int
3014 same_slots_added(PyTypeObject *a, PyTypeObject *b)
3015 {
3016     PyTypeObject *base = a->tp_base;
3017     Py_ssize_t size;
3018     PyObject *slots_a, *slots_b;
3019 
3020     assert(base == b->tp_base);
3021     size = base->tp_basicsize;
3022     if (a->tp_dictoffset == size && b->tp_dictoffset == size)
3023         size += sizeof(PyObject *);
3024     if (a->tp_weaklistoffset == size && b->tp_weaklistoffset == size)
3025         size += sizeof(PyObject *);
3026 
3027     /* Check slots compliance */
3028     slots_a = ((PyHeapTypeObject *)a)->ht_slots;
3029     slots_b = ((PyHeapTypeObject *)b)->ht_slots;
3030     if (slots_a && slots_b) {
3031         if (PyObject_Compare(slots_a, slots_b) != 0)
3032             return 0;
3033         size += sizeof(PyObject *) * PyTuple_GET_SIZE(slots_a);
3034     }
3035     return size == a->tp_basicsize && size == b->tp_basicsize;
3036 }
3037 
3038 static int
3039 compatible_for_assignment(PyTypeObject* oldto, PyTypeObject* newto, char* attr)
3040 {
3041     PyTypeObject *newbase, *oldbase;
3042 
3043     if (newto->tp_dealloc != oldto->tp_dealloc ||
3044         newto->tp_free != oldto->tp_free)
3045     {
3046         PyErr_Format(PyExc_TypeError,
3047                      "%s assignment: "
3048                      "'%s' deallocator differs from '%s'",
3049                      attr,
3050                      newto->tp_name,
3051                      oldto->tp_name);
3052         return 0;
3053     }
3054     newbase = newto;
3055     oldbase = oldto;
3056     while (equiv_structs(newbase, newbase->tp_base))
3057         newbase = newbase->tp_base;
3058     while (equiv_structs(oldbase, oldbase->tp_base))
3059         oldbase = oldbase->tp_base;
3060     if (newbase != oldbase &&
3061         (newbase->tp_base != oldbase->tp_base ||
3062          !same_slots_added(newbase, oldbase))) {
3063         PyErr_Format(PyExc_TypeError,
3064                      "%s assignment: "
3065                      "'%s' object layout differs from '%s'",
3066                      attr,
3067                      newto->tp_name,
3068                      oldto->tp_name);
3069         return 0;
3070     }
3071 
3072     return 1;
3073 }
3074 
3075 static int
3076 object_set_class(PyObject *self, PyObject *value, void *closure)
3077 {
3078     PyTypeObject *oldto = Py_TYPE(self);
3079     PyTypeObject *newto;
3080 
3081     if (value == NULL) {
3082         PyErr_SetString(PyExc_TypeError,
3083                         "can't delete __class__ attribute");
3084         return -1;
3085     }
3086     if (!PyType_Check(value)) {
3087         PyErr_Format(PyExc_TypeError,
3088           "__class__ must be set to new-style class, not '%s' object",
3089           Py_TYPE(value)->tp_name);
3090         return -1;
3091     }
3092     newto = (PyTypeObject *)value;
3093     if (!(newto->tp_flags & Py_TPFLAGS_HEAPTYPE) ||
3094         !(oldto->tp_flags & Py_TPFLAGS_HEAPTYPE))
3095     {
3096         PyErr_Format(PyExc_TypeError,
3097                      "__class__ assignment: only for heap types");
3098         return -1;
3099     }
3100     if (compatible_for_assignment(newto, oldto, "__class__")) {
3101         Py_INCREF(newto);
3102         Py_TYPE(self) = newto;
3103         Py_DECREF(oldto);
3104         return 0;
3105     }
3106     else {
3107         return -1;
3108     }
3109 }
3110 
3111 static PyGetSetDef object_getsets[] = {
3112     {"__class__", object_get_class, object_set_class,
3113      PyDoc_STR("the object's class")},
3114     {0}
3115 };
3116 
3117 
3118 /* Stuff to implement __reduce_ex__ for pickle protocols >= 2.
3119    We fall back to helpers in copy_reg for:
3120    - pickle protocols < 2
3121    - calculating the list of slot names (done only once per class)
3122    - the __newobj__ function (which is used as a token but never called)
3123 */
3124 
3125 static PyObject *
3126 import_copyreg(void)
3127 {
3128     static PyObject *copyreg_str;
3129 
3130     if (!copyreg_str) {
3131         copyreg_str = PyString_InternFromString("copy_reg");
3132         if (copyreg_str == NULL)
3133             return NULL;
3134     }
3135 
3136     return PyImport_Import(copyreg_str);
3137 }
3138 
3139 static PyObject *
3140 slotnames(PyObject *cls)
3141 {
3142     PyObject *clsdict;
3143     PyObject *copyreg;
3144     PyObject *slotnames;
3145 
3146     if (!PyType_Check(cls)) {
3147         Py_INCREF(Py_None);
3148         return Py_None;
3149     }
3150 
3151     clsdict = ((PyTypeObject *)cls)->tp_dict;
3152     slotnames = PyDict_GetItemString(clsdict, "__slotnames__");
3153     if (slotnames != NULL && PyList_Check(slotnames)) {
3154         Py_INCREF(slotnames);
3155         return slotnames;
3156     }
3157 
3158     copyreg = import_copyreg();
3159     if (copyreg == NULL)
3160         return NULL;
3161 
3162     slotnames = PyObject_CallMethod(copyreg, "_slotnames", "O", cls);
3163     Py_DECREF(copyreg);
3164     if (slotnames != NULL &&
3165         slotnames != Py_None &&
3166         !PyList_Check(slotnames))
3167     {
3168         PyErr_SetString(PyExc_TypeError,
3169             "copy_reg._slotnames didn't return a list or None");
3170         Py_DECREF(slotnames);
3171         slotnames = NULL;
3172     }
3173 
3174     return slotnames;
3175 }
3176 
3177 static PyObject *
3178 reduce_2(PyObject *obj)
3179 {
3180     PyObject *cls, *getnewargs;
3181     PyObject *args = NULL, *args2 = NULL;
3182     PyObject *getstate = NULL, *state = NULL, *names = NULL;
3183     PyObject *slots = NULL, *listitems = NULL, *dictitems = NULL;
3184     PyObject *copyreg = NULL, *newobj = NULL, *res = NULL;
3185     Py_ssize_t i, n;
3186 
3187     cls = PyObject_GetAttrString(obj, "__class__");
3188     if (cls == NULL)
3189         return NULL;
3190 
3191     getnewargs = PyObject_GetAttrString(obj, "__getnewargs__");
3192     if (getnewargs != NULL) {
3193         args = PyObject_CallObject(getnewargs, NULL);
3194         Py_DECREF(getnewargs);
3195         if (args != NULL && !PyTuple_Check(args)) {
3196             PyErr_Format(PyExc_TypeError,
3197                 "__getnewargs__ should return a tuple, "
3198                 "not '%.200s'", Py_TYPE(args)->tp_name);
3199             goto end;
3200         }
3201     }
3202     else {
3203         PyErr_Clear();
3204         args = PyTuple_New(0);
3205     }
3206     if (args == NULL)
3207         goto end;
3208 
3209     getstate = PyObject_GetAttrString(obj, "__getstate__");
3210     if (getstate != NULL) {
3211         state = PyObject_CallObject(getstate, NULL);
3212         Py_DECREF(getstate);
3213         if (state == NULL)
3214             goto end;
3215     }
3216     else {
3217         PyErr_Clear();
3218         state = PyObject_GetAttrString(obj, "__dict__");
3219         if (state == NULL) {
3220             PyErr_Clear();
3221             state = Py_None;
3222             Py_INCREF(state);
3223         }
3224         names = slotnames(cls);
3225         if (names == NULL)
3226             goto end;
3227         if (names != Py_None) {
3228             assert(PyList_Check(names));
3229             slots = PyDict_New();
3230             if (slots == NULL)
3231                 goto end;
3232             n = 0;
3233             /* Can't pre-compute the list size; the list
3234                is stored on the class so accessible to other
3235                threads, which may be run by DECREF */
3236             for (i = 0; i < PyList_GET_SIZE(names); i++) {
3237                 PyObject *name, *value;
3238                 name = PyList_GET_ITEM(names, i);
3239                 value = PyObject_GetAttr(obj, name);
3240                 if (value == NULL)
3241                     PyErr_Clear();
3242                 else {
3243                     int err = PyDict_SetItem(slots, name,
3244                                              value);
3245                     Py_DECREF(value);
3246                     if (err)
3247                         goto end;
3248                     n++;
3249                 }
3250             }
3251             if (n) {
3252                 state = Py_BuildValue("(NO)", state, slots);
3253                 if (state == NULL)
3254                     goto end;
3255             }
3256         }
3257     }
3258 
3259     if (!PyList_Check(obj)) {
3260         listitems = Py_None;
3261         Py_INCREF(listitems);
3262     }
3263     else {
3264         listitems = PyObject_GetIter(obj);
3265         if (listitems == NULL)
3266             goto end;
3267     }
3268 
3269     if (!PyDict_Check(obj)) {
3270         dictitems = Py_None;
3271         Py_INCREF(dictitems);
3272     }
3273     else {
3274         dictitems = PyObject_CallMethod(obj, "iteritems", "");
3275         if (dictitems == NULL)
3276             goto end;
3277     }
3278 
3279     copyreg = import_copyreg();
3280     if (copyreg == NULL)
3281         goto end;
3282     newobj = PyObject_GetAttrString(copyreg, "__newobj__");
3283     if (newobj == NULL)
3284         goto end;
3285 
3286     n = PyTuple_GET_SIZE(args);
3287     args2 = PyTuple_New(n+1);
3288     if (args2 == NULL)
3289         goto end;
3290     PyTuple_SET_ITEM(args2, 0, cls);
3291     cls = NULL;
3292     for (i = 0; i < n; i++) {
3293         PyObject *v = PyTuple_GET_ITEM(args, i);
3294         Py_INCREF(v);
3295         PyTuple_SET_ITEM(args2, i+1, v);
3296     }
3297 
3298     res = PyTuple_Pack(5, newobj, args2, state, listitems, dictitems);
3299 
3300   end:
3301     Py_XDECREF(cls);
3302     Py_XDECREF(args);
3303     Py_XDECREF(args2);
3304     Py_XDECREF(slots);
3305     Py_XDECREF(state);
3306     Py_XDECREF(names);
3307     Py_XDECREF(listitems);
3308     Py_XDECREF(dictitems);
3309     Py_XDECREF(copyreg);
3310     Py_XDECREF(newobj);
3311     return res;
3312 }
3313 
3314 /*
3315  * There were two problems when object.__reduce__ and object.__reduce_ex__
3316  * were implemented in the same function:
3317  *  - trying to pickle an object with a custom __reduce__ method that
3318  *    fell back to object.__reduce__ in certain circumstances led to
3319  *    infinite recursion at Python level and eventual RuntimeError.
3320  *  - Pickling objects that lied about their type by overwriting the
3321  *    __class__ descriptor could lead to infinite recursion at C level
3322  *    and eventual segfault.
3323  *
3324  * Because of backwards compatibility, the two methods still have to
3325  * behave in the same way, even if this is not required by the pickle
3326  * protocol. This common functionality was moved to the _common_reduce
3327  * function.
3328  */
3329 static PyObject *
3330 _common_reduce(PyObject *self, int proto)
3331 {
3332     PyObject *copyreg, *res;
3333 
3334     if (proto >= 2)
3335         return reduce_2(self);
3336 
3337     copyreg = import_copyreg();
3338     if (!copyreg)
3339         return NULL;
3340 
3341     res = PyEval_CallMethod(copyreg, "_reduce_ex", "(Oi)", self, proto);
3342     Py_DECREF(copyreg);
3343 
3344     return res;
3345 }
3346 
3347 static PyObject *
3348 object_reduce(PyObject *self, PyObject *args)
3349 {
3350     int proto = 0;
3351 
3352     if (!PyArg_ParseTuple(args, "|i:__reduce__", &proto))
3353         return NULL;
3354 
3355     return _common_reduce(self, proto);
3356 }
3357 
3358 static PyObject *
3359 object_reduce_ex(PyObject *self, PyObject *args)
3360 {
3361     PyObject *reduce, *res;
3362     int proto = 0;
3363 
3364     if (!PyArg_ParseTuple(args, "|i:__reduce_ex__", &proto))
3365         return NULL;
3366 
3367     reduce = PyObject_GetAttrString(self, "__reduce__");
3368     if (reduce == NULL)
3369         PyErr_Clear();
3370     else {
3371         PyObject *cls, *clsreduce, *objreduce;
3372         int override;
3373         cls = PyObject_GetAttrString(self, "__class__");
3374         if (cls == NULL) {
3375             Py_DECREF(reduce);
3376             return NULL;
3377         }
3378         clsreduce = PyObject_GetAttrString(cls, "__reduce__");
3379         Py_DECREF(cls);
3380         if (clsreduce == NULL) {
3381             Py_DECREF(reduce);
3382             return NULL;
3383         }
3384         objreduce = PyDict_GetItemString(PyBaseObject_Type.tp_dict,
3385                                          "__reduce__");
3386         override = (clsreduce != objreduce);
3387         Py_DECREF(clsreduce);
3388         if (override) {
3389             res = PyObject_CallObject(reduce, NULL);
3390             Py_DECREF(reduce);
3391             return res;
3392         }
3393         else
3394             Py_DECREF(reduce);
3395     }
3396 
3397     return _common_reduce(self, proto);
3398 }
3399 
3400 static PyObject *
3401 object_subclasshook(PyObject *cls, PyObject *args)
3402 {
3403     Py_INCREF(Py_NotImplemented);
3404     return Py_NotImplemented;
3405 }
3406 
3407 PyDoc_STRVAR(object_subclasshook_doc,
3408 "Abstract classes can override this to customize issubclass().\n"
3409 "\n"
3410 "This is invoked early on by abc.ABCMeta.__subclasscheck__().\n"
3411 "It should return True, False or NotImplemented.  If it returns\n"
3412 "NotImplemented, the normal algorithm is used.  Otherwise, it\n"
3413 "overrides the normal algorithm (and the outcome is cached).\n");
3414 
3415 /*
3416    from PEP 3101, this code implements:
3417 
3418    class object:
3419        def __format__(self, format_spec):
3420        if isinstance(format_spec, str):
3421            return format(str(self), format_spec)
3422        elif isinstance(format_spec, unicode):
3423            return format(unicode(self), format_spec)
3424 */
3425 static PyObject *
3426 object_format(PyObject *self, PyObject *args)
3427 {
3428     PyObject *format_spec;
3429     PyObject *self_as_str = NULL;
3430     PyObject *result = NULL;
3431     Py_ssize_t format_len;
3432 
3433     if (!PyArg_ParseTuple(args, "O:__format__", &format_spec))
3434         return NULL;
3435 #ifdef Py_USING_UNICODE
3436     if (PyUnicode_Check(format_spec)) {
3437         format_len = PyUnicode_GET_SIZE(format_spec);
3438         self_as_str = PyObject_Unicode(self);
3439     } else if (PyString_Check(format_spec)) {
3440 #else
3441     if (PyString_Check(format_spec)) {
3442 #endif
3443         format_len = PyString_GET_SIZE(format_spec);
3444         self_as_str = PyObject_Str(self);
3445     } else {
3446         PyErr_SetString(PyExc_TypeError,
3447                  "argument to __format__ must be unicode or str");
3448         return NULL;
3449     }
3450 
3451     if (self_as_str != NULL) {
3452         /* Issue 7994: If we're converting to a string, we
3453            should reject format specifications */
3454         if (format_len > 0) {
3455             if (PyErr_WarnEx(PyExc_PendingDeprecationWarning,
3456              "object.__format__ with a non-empty format "
3457              "string is deprecated", 1) < 0) {
3458                 goto done;
3459             }
3460             /* Eventually this will become an error:
3461             PyErr_Format(PyExc_TypeError,
3462                "non-empty format string passed to object.__format__");
3463             goto done;
3464             */
3465         }
3466         result = PyObject_Format(self_as_str, format_spec);
3467     }
3468 
3469 done:
3470     Py_XDECREF(self_as_str);
3471 
3472     return result;
3473 }
3474 
3475 static PyObject *
3476 object_sizeof(PyObject *self, PyObject *args)
3477 {
3478     Py_ssize_t res, isize;
3479 
3480     res = 0;
3481     isize = self->ob_type->tp_itemsize;
3482     if (isize > 0)
3483         res = self->ob_type->ob_size * isize;
3484     res += self->ob_type->tp_basicsize;
3485 
3486     return PyInt_FromSsize_t(res);
3487 }
3488 
3489 static PyMethodDef object_methods[] = {
3490     {"__reduce_ex__", object_reduce_ex, METH_VARARGS,
3491      PyDoc_STR("helper for pickle")},
3492     {"__reduce__", object_reduce, METH_VARARGS,
3493      PyDoc_STR("helper for pickle")},
3494     {"__subclasshook__", object_subclasshook, METH_CLASS | METH_VARARGS,
3495      object_subclasshook_doc},
3496     {"__format__", object_format, METH_VARARGS,
3497      PyDoc_STR("default object formatter")},
3498     {"__sizeof__", object_sizeof, METH_NOARGS,
3499      PyDoc_STR("__sizeof__() -> int\nsize of object in memory, in bytes")},
3500     {0}
3501 };
3502 
3503 
3504 PyTypeObject PyBaseObject_Type = {
3505     PyVarObject_HEAD_INIT(&PyType_Type, 0)
3506     "object",                                   /* tp_name */
3507     sizeof(PyObject),                           /* tp_basicsize */
3508     0,                                          /* tp_itemsize */
3509     object_dealloc,                             /* tp_dealloc */
3510     0,                                          /* tp_print */
3511     0,                                          /* tp_getattr */
3512     0,                                          /* tp_setattr */
3513     0,                                          /* tp_compare */
3514     object_repr,                                /* tp_repr */
3515     0,                                          /* tp_as_number */
3516     0,                                          /* tp_as_sequence */
3517     0,                                          /* tp_as_mapping */
3518     (hashfunc)_Py_HashPointer,                  /* tp_hash */
3519     0,                                          /* tp_call */
3520     object_str,                                 /* tp_str */
3521     PyObject_GenericGetAttr,                    /* tp_getattro */
3522     PyObject_GenericSetAttr,                    /* tp_setattro */
3523     0,                                          /* tp_as_buffer */
3524     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /* tp_flags */
3525     PyDoc_STR("The most base type"),            /* tp_doc */
3526     0,                                          /* tp_traverse */
3527     0,                                          /* tp_clear */
3528     0,                                          /* tp_richcompare */
3529     0,                                          /* tp_weaklistoffset */
3530     0,                                          /* tp_iter */
3531     0,                                          /* tp_iternext */
3532     object_methods,                             /* tp_methods */
3533     0,                                          /* tp_members */
3534     object_getsets,                             /* tp_getset */
3535     0,                                          /* tp_base */
3536     0,                                          /* tp_dict */
3537     0,                                          /* tp_descr_get */
3538     0,                                          /* tp_descr_set */
3539     0,                                          /* tp_dictoffset */
3540     object_init,                                /* tp_init */
3541     PyType_GenericAlloc,                        /* tp_alloc */
3542     object_new,                                 /* tp_new */
3543     PyObject_Del,                               /* tp_free */
3544 };
3545 
3546 
3547 /* Initialize the __dict__ in a type object */
3548 
3549 static int
3550 add_methods(PyTypeObject *type, PyMethodDef *meth)
3551 {
3552     PyObject *dict = type->tp_dict;
3553 
3554     for (; meth->ml_name != NULL; meth++) {
3555         PyObject *descr;
3556         if (PyDict_GetItemString(dict, meth->ml_name) &&
3557             !(meth->ml_flags & METH_COEXIST))
3558                 continue;
3559         if (meth->ml_flags & METH_CLASS) {
3560             if (meth->ml_flags & METH_STATIC) {
3561                 PyErr_SetString(PyExc_ValueError,
3562                      "method cannot be both class and static");
3563                 return -1;
3564             }
3565             descr = PyDescr_NewClassMethod(type, meth);
3566         }
3567         else if (meth->ml_flags & METH_STATIC) {
3568             PyObject *cfunc = PyCFunction_New(meth, NULL);
3569             if (cfunc == NULL)
3570                 return -1;
3571             descr = PyStaticMethod_New(cfunc);
3572             Py_DECREF(cfunc);
3573         }
3574         else {
3575             descr = PyDescr_NewMethod(type, meth);
3576         }
3577         if (descr == NULL)
3578             return -1;
3579         if (PyDict_SetItemString(dict, meth->ml_name, descr) < 0)
3580             return -1;
3581         Py_DECREF(descr);
3582     }
3583     return 0;
3584 }
3585 
3586 static int
3587 add_members(PyTypeObject *type, PyMemberDef *memb)
3588 {
3589     PyObject *dict = type->tp_dict;
3590 
3591     for (; memb->name != NULL; memb++) {
3592         PyObject *descr;
3593         if (PyDict_GetItemString(dict, memb->name))
3594             continue;
3595         descr = PyDescr_NewMember(type, memb);
3596         if (descr == NULL)
3597             return -1;
3598         if (PyDict_SetItemString(dict, memb->name, descr) < 0)
3599             return -1;
3600         Py_DECREF(descr);
3601     }
3602     return 0;
3603 }
3604 
3605 static int
3606 add_getset(PyTypeObject *type, PyGetSetDef *gsp)
3607 {
3608     PyObject *dict = type->tp_dict;
3609 
3610     for (; gsp->name != NULL; gsp++) {
3611         PyObject *descr;
3612         if (PyDict_GetItemString(dict, gsp->name))
3613             continue;
3614         descr = PyDescr_NewGetSet(type, gsp);
3615 
3616         if (descr == NULL)
3617             return -1;
3618         if (PyDict_SetItemString(dict, gsp->name, descr) < 0)
3619             return -1;
3620         Py_DECREF(descr);
3621     }
3622     return 0;
3623 }
3624 
3625 #define BUFFER_FLAGS (Py_TPFLAGS_HAVE_GETCHARBUFFER | Py_TPFLAGS_HAVE_NEWBUFFER)
3626 
3627 static void
3628 inherit_special(PyTypeObject *type, PyTypeObject *base)
3629 {
3630     Py_ssize_t oldsize, newsize;
3631 
3632     /* Special flag magic */
3633     if (!type->tp_as_buffer && base->tp_as_buffer) {
3634         type->tp_flags &= ~BUFFER_FLAGS;
3635         type->tp_flags |=
3636             base->tp_flags & BUFFER_FLAGS;
3637     }
3638     if (!type->tp_as_sequence && base->tp_as_sequence) {
3639         type->tp_flags &= ~Py_TPFLAGS_HAVE_SEQUENCE_IN;
3640         type->tp_flags |= base->tp_flags & Py_TPFLAGS_HAVE_SEQUENCE_IN;
3641     }
3642     if ((type->tp_flags & Py_TPFLAGS_HAVE_INPLACEOPS) !=
3643         (base->tp_flags & Py_TPFLAGS_HAVE_INPLACEOPS)) {
3644         if ((!type->tp_as_number && base->tp_as_number) ||
3645             (!type->tp_as_sequence && base->tp_as_sequence)) {
3646             type->tp_flags &= ~Py_TPFLAGS_HAVE_INPLACEOPS;
3647             if (!type->tp_as_number && !type->tp_as_sequence) {
3648                 type->tp_flags |= base->tp_flags &
3649                     Py_TPFLAGS_HAVE_INPLACEOPS;
3650             }
3651         }
3652         /* Wow */
3653     }
3654     if (!type->tp_as_number && base->tp_as_number) {
3655         type->tp_flags &= ~Py_TPFLAGS_CHECKTYPES;
3656         type->tp_flags |= base->tp_flags & Py_TPFLAGS_CHECKTYPES;
3657     }
3658 
3659     /* Copying basicsize is connected to the GC flags */
3660     oldsize = base->tp_basicsize;
3661     newsize = type->tp_basicsize ? type->tp_basicsize : oldsize;
3662     if (!(type->tp_flags & Py_TPFLAGS_HAVE_GC) &&
3663         (base->tp_flags & Py_TPFLAGS_HAVE_GC) &&
3664         (type->tp_flags & Py_TPFLAGS_HAVE_RICHCOMPARE/*GC slots exist*/) &&
3665         (!type->tp_traverse && !type->tp_clear)) {
3666         type->tp_flags |= Py_TPFLAGS_HAVE_GC;
3667         if (type->tp_traverse == NULL)
3668             type->tp_traverse = base->tp_traverse;
3669         if (type->tp_clear == NULL)
3670             type->tp_clear = base->tp_clear;
3671     }
3672     if (type->tp_flags & base->tp_flags & Py_TPFLAGS_HAVE_CLASS) {
3673         /* The condition below could use some explanation.
3674            It appears that tp_new is not inherited for static types
3675            whose base class is 'object'; this seems to be a precaution
3676            so that old extension types don't suddenly become
3677            callable (object.__new__ wouldn't insure the invariants
3678            that the extension type's own factory function ensures).
3679            Heap types, of course, are under our control, so they do
3680            inherit tp_new; static extension types that specify some
3681            other built-in type as the default are considered
3682            new-style-aware so they also inherit object.__new__. */
3683         if (base != &PyBaseObject_Type ||
3684             (type->tp_flags & Py_TPFLAGS_HEAPTYPE)) {
3685             if (type->tp_new == NULL)
3686                 type->tp_new = base->tp_new;
3687         }
3688     }
3689     type->tp_basicsize = newsize;
3690 
3691     /* Copy other non-function slots */
3692 
3693 #undef COPYVAL
3694 #define COPYVAL(SLOT) \
3695     if (type->SLOT == 0) type->SLOT = base->SLOT
3696 
3697     COPYVAL(tp_itemsize);
3698     if (type->tp_flags & base->tp_flags & Py_TPFLAGS_HAVE_WEAKREFS) {
3699         COPYVAL(tp_weaklistoffset);
3700     }
3701     if (type->tp_flags & base->tp_flags & Py_TPFLAGS_HAVE_CLASS) {
3702         COPYVAL(tp_dictoffset);
3703     }
3704 
3705     /* Setup fast subclass flags */
3706     if (PyType_IsSubtype(base, (PyTypeObject*)PyExc_BaseException))
3707         type->tp_flags |= Py_TPFLAGS_BASE_EXC_SUBCLASS;
3708     else if (PyType_IsSubtype(base, &PyType_Type))
3709         type->tp_flags |= Py_TPFLAGS_TYPE_SUBCLASS;
3710     else if (PyType_IsSubtype(base, &PyInt_Type))
3711         type->tp_flags |= Py_TPFLAGS_INT_SUBCLASS;
3712     else if (PyType_IsSubtype(base, &PyLong_Type))
3713         type->tp_flags |= Py_TPFLAGS_LONG_SUBCLASS;
3714     else if (PyType_IsSubtype(base, &PyString_Type))
3715         type->tp_flags |= Py_TPFLAGS_STRING_SUBCLASS;
3716 #ifdef Py_USING_UNICODE
3717     else if (PyType_IsSubtype(base, &PyUnicode_Type))
3718         type->tp_flags |= Py_TPFLAGS_UNICODE_SUBCLASS;
3719 #endif
3720     else if (PyType_IsSubtype(base, &PyTuple_Type))
3721         type->tp_flags |= Py_TPFLAGS_TUPLE_SUBCLASS;
3722     else if (PyType_IsSubtype(base, &PyList_Type))
3723         type->tp_flags |= Py_TPFLAGS_LIST_SUBCLASS;
3724     else if (PyType_IsSubtype(base, &PyDict_Type))
3725         type->tp_flags |= Py_TPFLAGS_DICT_SUBCLASS;
3726 }
3727 
3728 static int
3729 overrides_name(PyTypeObject *type, char *name)
3730 {
3731     PyObject *dict = type->tp_dict;
3732 
3733     assert(dict != NULL);
3734     if (PyDict_GetItemString(dict, name) != NULL) {
3735         return 1;
3736     }
3737     return 0;
3738 }
3739 
3740 #define OVERRIDES_HASH(x)       overrides_name(x, "__hash__")
3741 #define OVERRIDES_EQ(x)         overrides_name(x, "__eq__")
3742 
3743 static void
3744 inherit_slots(PyTypeObject *type, PyTypeObject *base)
3745 {
3746     PyTypeObject *basebase;
3747 
3748 #undef SLOTDEFINED
3749 #undef COPYSLOT
3750 #undef COPYNUM
3751 #undef COPYSEQ
3752 #undef COPYMAP
3753 #undef COPYBUF
3754 
3755 #define SLOTDEFINED(SLOT) \
3756     (base->SLOT != 0 && \
3757      (basebase == NULL || base->SLOT != basebase->SLOT))
3758 
3759 #define COPYSLOT(SLOT) \
3760     if (!type->SLOT && SLOTDEFINED(SLOT)) type->SLOT = base->SLOT
3761 
3762 #define COPYNUM(SLOT) COPYSLOT(tp_as_number->SLOT)
3763 #define COPYSEQ(SLOT) COPYSLOT(tp_as_sequence->SLOT)
3764 #define COPYMAP(SLOT) COPYSLOT(tp_as_mapping->SLOT)
3765 #define COPYBUF(SLOT) COPYSLOT(tp_as_buffer->SLOT)
3766 
3767     /* This won't inherit indirect slots (from tp_as_number etc.)
3768        if type doesn't provide the space. */
3769 
3770     if (type->tp_as_number != NULL && base->tp_as_number != NULL) {
3771         basebase = base->tp_base;
3772         if (basebase->tp_as_number == NULL)
3773             basebase = NULL;
3774         COPYNUM(nb_add);
3775         COPYNUM(nb_subtract);
3776         COPYNUM(nb_multiply);
3777         COPYNUM(nb_divide);
3778         COPYNUM(nb_remainder);
3779         COPYNUM(nb_divmod);
3780         COPYNUM(nb_power);
3781         COPYNUM(nb_negative);
3782         COPYNUM(nb_positive);
3783         COPYNUM(nb_absolute);
3784         COPYNUM(nb_nonzero);
3785         COPYNUM(nb_invert);
3786         COPYNUM(nb_lshift);
3787         COPYNUM(nb_rshift);
3788         COPYNUM(nb_and);
3789         COPYNUM(nb_xor);
3790         COPYNUM(nb_or);
3791         COPYNUM(nb_coerce);
3792         COPYNUM(nb_int);
3793         COPYNUM(nb_long);
3794         COPYNUM(nb_float);
3795         COPYNUM(nb_oct);
3796         COPYNUM(nb_hex);
3797         COPYNUM(nb_inplace_add);
3798         COPYNUM(nb_inplace_subtract);
3799         COPYNUM(nb_inplace_multiply);
3800         COPYNUM(nb_inplace_divide);
3801         COPYNUM(nb_inplace_remainder);
3802         COPYNUM(nb_inplace_power);
3803         COPYNUM(nb_inplace_lshift);
3804         COPYNUM(nb_inplace_rshift);
3805         COPYNUM(nb_inplace_and);
3806         COPYNUM(nb_inplace_xor);
3807         COPYNUM(nb_inplace_or);
3808         if (base->tp_flags & Py_TPFLAGS_CHECKTYPES) {
3809             COPYNUM(nb_true_divide);
3810             COPYNUM(nb_floor_divide);
3811             COPYNUM(nb_inplace_true_divide);
3812             COPYNUM(nb_inplace_floor_divide);
3813         }
3814         if (base->tp_flags & Py_TPFLAGS_HAVE_INDEX) {
3815             COPYNUM(nb_index);
3816         }
3817     }
3818 
3819     if (type->tp_as_sequence != NULL && base->tp_as_sequence != NULL) {
3820         basebase = base->tp_base;
3821         if (basebase->tp_as_sequence == NULL)
3822             basebase = NULL;
3823         COPYSEQ(sq_length);
3824         COPYSEQ(sq_concat);
3825         COPYSEQ(sq_repeat);
3826         COPYSEQ(sq_item);
3827         COPYSEQ(sq_slice);
3828         COPYSEQ(sq_ass_item);
3829         COPYSEQ(sq_ass_slice);
3830         COPYSEQ(sq_contains);
3831         COPYSEQ(sq_inplace_concat);
3832         COPYSEQ(sq_inplace_repeat);
3833     }
3834 
3835     if (type->tp_as_mapping != NULL && base->tp_as_mapping != NULL) {
3836         basebase = base->tp_base;
3837         if (basebase->tp_as_mapping == NULL)
3838             basebase = NULL;
3839         COPYMAP(mp_length);
3840         COPYMAP(mp_subscript);
3841         COPYMAP(mp_ass_subscript);
3842     }
3843 
3844     if (type->tp_as_buffer != NULL && base->tp_as_buffer != NULL) {
3845         basebase = base->tp_base;
3846         if (basebase->tp_as_buffer == NULL)
3847             basebase = NULL;
3848         COPYBUF(bf_getreadbuffer);
3849         COPYBUF(bf_getwritebuffer);
3850         COPYBUF(bf_getsegcount);
3851         COPYBUF(bf_getcharbuffer);
3852         COPYBUF(bf_getbuffer);
3853         COPYBUF(bf_releasebuffer);
3854     }
3855 
3856     basebase = base->tp_base;
3857 
3858     COPYSLOT(tp_dealloc);
3859     COPYSLOT(tp_print);
3860     if (type->tp_getattr == NULL && type->tp_getattro == NULL) {
3861         type->tp_getattr = base->tp_getattr;
3862         type->tp_getattro = base->tp_getattro;
3863     }
3864     if (type->tp_setattr == NULL && type->tp_setattro == NULL) {
3865         type->tp_setattr = base->tp_setattr;
3866         type->tp_setattro = base->tp_setattro;
3867     }
3868     /* tp_compare see tp_richcompare */
3869     COPYSLOT(tp_repr);
3870     /* tp_hash see tp_richcompare */
3871     COPYSLOT(tp_call);
3872     COPYSLOT(tp_str);
3873     if (type->tp_flags & base->tp_flags & Py_TPFLAGS_HAVE_RICHCOMPARE) {
3874         if (type->tp_compare == NULL &&
3875             type->tp_richcompare == NULL &&
3876             type->tp_hash == NULL)
3877         {
3878             type->tp_compare = base->tp_compare;
3879             type->tp_richcompare = base->tp_richcompare;
3880             type->tp_hash = base->tp_hash;
3881             /* Check for changes to inherited methods in Py3k*/
3882             if (Py_Py3kWarningFlag) {
3883                 if (base->tp_hash &&
3884                                 (base->tp_hash != PyObject_HashNotImplemented) &&
3885                                 !OVERRIDES_HASH(type)) {
3886                     if (OVERRIDES_EQ(type)) {
3887                         if (PyErr_WarnPy3k("Overriding "
3888                                            "__eq__ blocks inheritance "
3889                                            "of __hash__ in 3.x",
3890                                            1) < 0)
3891                             /* XXX This isn't right.  If the warning is turned
3892                                into an exception, we should be communicating
3893                                the error back to the caller, but figuring out
3894                                how to clean up in that case is tricky.  See
3895                                issue 8627 for more. */
3896                             PyErr_Clear();
3897                     }
3898                 }
3899             }
3900         }
3901     }
3902     else {
3903         COPYSLOT(tp_compare);
3904     }
3905     if (type->tp_flags & base->tp_flags & Py_TPFLAGS_HAVE_ITER) {
3906         COPYSLOT(tp_iter);
3907         COPYSLOT(tp_iternext);
3908     }
3909     if (type->tp_flags & base->tp_flags & Py_TPFLAGS_HAVE_CLASS) {
3910         COPYSLOT(tp_descr_get);
3911         COPYSLOT(tp_descr_set);
3912         COPYSLOT(tp_dictoffset);
3913         COPYSLOT(tp_init);
3914         COPYSLOT(tp_alloc);
3915         COPYSLOT(tp_is_gc);
3916         if ((type->tp_flags & Py_TPFLAGS_HAVE_GC) ==
3917             (base->tp_flags & Py_TPFLAGS_HAVE_GC)) {
3918             /* They agree about gc. */
3919             COPYSLOT(tp_free);
3920         }
3921         else if ((type->tp_flags & Py_TPFLAGS_HAVE_GC) &&
3922                  type->tp_free == NULL &&
3923                  base->tp_free == _PyObject_Del) {
3924             /* A bit of magic to plug in the correct default
3925              * tp_free function when a derived class adds gc,
3926              * didn't define tp_free, and the base uses the
3927              * default non-gc tp_free.
3928              */
3929             type->tp_free = PyObject_GC_Del;
3930         }
3931         /* else they didn't agree about gc, and there isn't something
3932          * obvious to be done -- the type is on its own.
3933          */
3934     }
3935 }
3936 
3937 static int add_operators(PyTypeObject *);
3938 
3939 int
3940 PyType_Ready(PyTypeObject *type)
3941 {
3942     PyObject *dict, *bases;
3943     PyTypeObject *base;
3944     Py_ssize_t i, n;
3945 
3946     if (type->tp_flags & Py_TPFLAGS_READY) {
3947         assert(type->tp_dict != NULL);
3948         return 0;
3949     }
3950     assert((type->tp_flags & Py_TPFLAGS_READYING) == 0);
3951 
3952     type->tp_flags |= Py_TPFLAGS_READYING;
3953 
3954 #ifdef Py_TRACE_REFS
3955     /* PyType_Ready is the closest thing we have to a choke point
3956      * for type objects, so is the best place I can think of to try
3957      * to get type objects into the doubly-linked list of all objects.
3958      * Still, not all type objects go thru PyType_Ready.
3959      */
3960     _Py_AddToAllObjects((PyObject *)type, 0);
3961 #endif
3962 
3963     /* Initialize tp_base (defaults to BaseObject unless that's us) */
3964     base = type->tp_base;
3965     if (base == NULL && type != &PyBaseObject_Type) {
3966         base = type->tp_base = &PyBaseObject_Type;
3967         Py_INCREF(base);
3968     }
3969 
3970     /* Now the only way base can still be NULL is if type is
3971      * &PyBaseObject_Type.
3972      */
3973 
3974     /* Initialize the base class */
3975     if (base && base->tp_dict == NULL) {
3976         if (PyType_Ready(base) < 0)
3977             goto error;
3978     }
3979 
3980     /* Initialize ob_type if NULL.      This means extensions that want to be
3981        compilable separately on Windows can call PyType_Ready() instead of
3982        initializing the ob_type field of their type objects. */
3983     /* The test for base != NULL is really unnecessary, since base is only
3984        NULL when type is &PyBaseObject_Type, and we know its ob_type is
3985        not NULL (it's initialized to &PyType_Type).      But coverity doesn't
3986        know that. */
3987     if (Py_TYPE(type) == NULL && base != NULL)
3988         Py_TYPE(type) = Py_TYPE(base);
3989 
3990     /* Initialize tp_bases */
3991     bases = type->tp_bases;
3992     if (bases == NULL) {
3993         if (base == NULL)
3994             bases = PyTuple_New(0);
3995         else
3996             bases = PyTuple_Pack(1, base);
3997         if (bases == NULL)
3998             goto error;
3999         type->tp_bases = bases;
4000     }
4001 
4002     /* Initialize tp_dict */
4003     dict = type->tp_dict;
4004     if (dict == NULL) {
4005         dict = PyDict_New();
4006         if (dict == NULL)
4007             goto error;
4008         type->tp_dict = dict;
4009     }
4010 
4011     /* Add type-specific descriptors to tp_dict */
4012     if (add_operators(type) < 0)
4013         goto error;
4014     if (type->tp_methods != NULL) {
4015         if (add_methods(type, type->tp_methods) < 0)
4016             goto error;
4017     }
4018     if (type->tp_members != NULL) {
4019         if (add_members(type, type->tp_members) < 0)
4020             goto error;
4021     }
4022     if (type->tp_getset != NULL) {
4023         if (add_getset(type, type->tp_getset) < 0)
4024             goto error;
4025     }
4026 
4027     /* Calculate method resolution order */
4028     if (mro_internal(type) < 0) {
4029         goto error;
4030     }
4031 
4032     /* Inherit special flags from dominant base */
4033     if (type->tp_base != NULL)
4034         inherit_special(type, type->tp_base);
4035 
4036     /* Initialize tp_dict properly */
4037     bases = type->tp_mro;
4038     assert(bases != NULL);
4039     assert(PyTuple_Check(bases));
4040     n = PyTuple_GET_SIZE(bases);
4041     for (i = 1; i < n; i++) {
4042         PyObject *b = PyTuple_GET_ITEM(bases, i);
4043         if (PyType_Check(b))
4044             inherit_slots(type, (PyTypeObject *)b);
4045     }
4046 
4047     /* Sanity check for tp_free. */
4048     if (PyType_IS_GC(type) && (type->tp_flags & Py_TPFLAGS_BASETYPE) &&
4049         (type->tp_free == NULL || type->tp_free == PyObject_Del)) {
4050         /* This base class needs to call tp_free, but doesn't have
4051          * one, or its tp_free is for non-gc'ed objects.
4052          */
4053         PyErr_Format(PyExc_TypeError, "type '%.100s' participates in "
4054                      "gc and is a base type but has inappropriate "
4055                      "tp_free slot",
4056                      type->tp_name);
4057         goto error;
4058     }
4059 
4060     /* if the type dictionary doesn't contain a __doc__, set it from
4061        the tp_doc slot.
4062      */
4063     if (PyDict_GetItemString(type->tp_dict, "__doc__") == NULL) {
4064         if (type->tp_doc != NULL) {
4065             PyObject *doc = PyString_FromString(type->tp_doc);
4066             if (doc == NULL)
4067                 goto error;
4068             PyDict_SetItemString(type->tp_dict, "__doc__", doc);
4069             Py_DECREF(doc);
4070         } else {
4071             PyDict_SetItemString(type->tp_dict,
4072                                  "__doc__", Py_None);
4073         }
4074     }
4075 
4076     /* Some more special stuff */
4077     base = type->tp_base;
4078     if (base != NULL) {
4079         if (type->tp_as_number == NULL)
4080             type->tp_as_number = base->tp_as_number;
4081         if (type->tp_as_sequence == NULL)
4082             type->tp_as_sequence = base->tp_as_sequence;
4083         if (type->tp_as_mapping == NULL)
4084             type->tp_as_mapping = base->tp_as_mapping;
4085         if (type->tp_as_buffer == NULL)
4086             type->tp_as_buffer = base->tp_as_buffer;
4087     }
4088 
4089     /* Link into each base class's list of subclasses */
4090     bases = type->tp_bases;
4091     n = PyTuple_GET_SIZE(bases);
4092     for (i = 0; i < n; i++) {
4093         PyObject *b = PyTuple_GET_ITEM(bases, i);
4094         if (PyType_Check(b) &&
4095             add_subclass((PyTypeObject *)b, type) < 0)
4096             goto error;
4097     }
4098 
4099     /* All done -- set the ready flag */
4100     assert(type->tp_dict != NULL);
4101     type->tp_flags =
4102         (type->tp_flags & ~Py_TPFLAGS_READYING) | Py_TPFLAGS_READY;
4103     return 0;
4104 
4105   error:
4106     type->tp_flags &= ~Py_TPFLAGS_READYING;
4107     return -1;
4108 }
4109 
4110 static int
4111 add_subclass(PyTypeObject *base, PyTypeObject *type)
4112 {
4113     Py_ssize_t i;
4114     int result;
4115     PyObject *list, *ref, *newobj;
4116 
4117     list = base->tp_subclasses;
4118     if (list == NULL) {
4119         base->tp_subclasses = list = PyList_New(0);
4120         if (list == NULL)
4121             return -1;
4122     }
4123     assert(PyList_Check(list));
4124     newobj = PyWeakref_NewRef((PyObject *)type, NULL);
4125     i = PyList_GET_SIZE(list);
4126     while (--i >= 0) {
4127