Objects/typeobject.c

   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_INT, offsetof(PyTypeObject,tp_basicsize),READONLY},
 192         {"__itemsize__", T_INT, 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 = PyDict_GetItemString(type->tp_dict,
 311                                              "__abstractmethods__");
 312         if (!mod) {
 313                 PyErr_Format(PyExc_AttributeError, "__abstractmethods__");
 314                 return NULL;
 315         }
 316         Py_XINCREF(mod);
 317         return mod;
 318 }
 319
 320 static int
 321 type_set_abstractmethods(PyTypeObject *type, PyObject *value, void *context)
 322 {
 323         /* __abstractmethods__ should only be set once on a type, in
 324            abc.ABCMeta.__new__, so this function doesn't do anything
 325            special to update subclasses.
 326         */
 327         int res = PyDict_SetItemString(type->tp_dict,
 328                                        "__abstractmethods__", value);
 329         if (res == 0) {
 330                 PyType_Modified(type);
 331                 if (value && PyObject_IsTrue(value)) {
 332                         type->tp_flags |= Py_TPFLAGS_IS_ABSTRACT;
 333                 }
 334                 else {
 335                         type->tp_flags &= ~Py_TPFLAGS_IS_ABSTRACT;
 336                 }
 337         }
 338         return res;
 339 }
 340
 341 static PyObject *
 342 type_get_bases(PyTypeObject *type, void *context)
 343 {
 344         Py_INCREF(type->tp_bases);
 345         return type->tp_bases;
 346 }
 347
 348 static PyTypeObject *best_base(PyObject *);
 349 static int mro_internal(PyTypeObject *);
 350 static int compatible_for_assignment(PyTypeObject *, PyTypeObject *, char *);
 351 static int add_subclass(PyTypeObject*, PyTypeObject*);
 352 static void remove_subclass(PyTypeObject *, PyTypeObject *);
 353 static void update_all_slots(PyTypeObject *);
 354
 355 typedef int (*update_callback)(PyTypeObject *, void *);
 356 static int update_subclasses(PyTypeObject *type, PyObject *name,
 357                              update_callback callback, void *data);
 358 static int recurse_down_subclasses(PyTypeObject *type, PyObject *name,
 359                                    update_callback callback, void *data);
 360
 361 static int
 362 mro_subclasses(PyTypeObject *type, PyObject* temp)
 363 {
 364         PyTypeObject *subclass;
 365         PyObject *ref, *subclasses, *old_mro;
 366         Py_ssize_t i, n;
 367
 368         subclasses = type->tp_subclasses;
 369         if (subclasses == NULL)
 370                 return 0;
 371         assert(PyList_Check(subclasses));
 372         n = PyList_GET_SIZE(subclasses);
 373         for (i = 0; i < n; i++) {
 374                 ref = PyList_GET_ITEM(subclasses, i);
 375                 assert(PyWeakref_CheckRef(ref));
 376                 subclass = (PyTypeObject *)PyWeakref_GET_OBJECT(ref);
 377                 assert(subclass != NULL);
 378                 if ((PyObject *)subclass == Py_None)
 379                         continue;
 380                 assert(PyType_Check(subclass));
 381                 old_mro = subclass->tp_mro;
 382                 if (mro_internal(subclass) < 0) {
 383                         subclass->tp_mro = old_mro;
 384                         return -1;
 385                 }
 386                 else {
 387                         PyObject* tuple;
 388                         tuple = PyTuple_Pack(2, subclass, old_mro);
 389                         Py_DECREF(old_mro);
 390                         if (!tuple)
 391                                 return -1;
 392                         if (PyList_Append(temp, tuple) < 0)
 393                                 return -1;
 394                         Py_DECREF(tuple);
 395                 }
 396                 if (mro_subclasses(subclass, temp) < 0)
 397                         return -1;
 398         }
 399         return 0;
 400 }
 401
 402 static int
 403 type_set_bases(PyTypeObject *type, PyObject *value, void *context)
 404 {
 405         Py_ssize_t i;
 406         int r = 0;
 407         PyObject *ob, *temp;
 408         PyTypeObject *new_base, *old_base;
 409         PyObject *old_bases, *old_mro;
 410
 411         if (!(type->tp_flags & Py_TPFLAGS_HEAPTYPE)) {
 412                 PyErr_Format(PyExc_TypeError,
 413                              "can't set %s.__bases__", type->tp_name);
 414                 return -1;
 415         }
 416         if (!value) {
 417                 PyErr_Format(PyExc_TypeError,
 418                              "can't delete %s.__bases__", type->tp_name);
 419                 return -1;
 420         }
 421         if (!PyTuple_Check(value)) {
 422                 PyErr_Format(PyExc_TypeError,
 423                      "can only assign tuple to %s.__bases__, not %s",
 424                              type->tp_name, Py_TYPE(value)->tp_name);
 425                 return -1;
 426         }
 427         if (PyTuple_GET_SIZE(value) == 0) {
 428                 PyErr_Format(PyExc_TypeError,
 429                      "can only assign non-empty tuple to %s.__bases__, not ()",
 430                              type->tp_name);
 431                 return -1;
 432         }
 433         for (i = 0; i < PyTuple_GET_SIZE(value); i++) {
 434                 ob = PyTuple_GET_ITEM(value, i);
 435                 if (!PyClass_Check(ob) && !PyType_Check(ob)) {
 436                         PyErr_Format(
 437                                 PyExc_TypeError,
 438         "%s.__bases__ must be tuple of old- or new-style classes, not '%s'",
 439                                 type->tp_name, Py_TYPE(ob)->tp_name);
 440                         return -1;
 441                 }
 442                 if (PyType_Check(ob)) {
 443                         if (PyType_IsSubtype((PyTypeObject*)ob, type)) {
 444                                 PyErr_SetString(PyExc_TypeError,
 445                         "a __bases__ item causes an inheritance cycle");
 446                                 return -1;
 447                         }
 448                 }
 449         }
 450
 451         new_base = best_base(value);
 452
 453         if (!new_base) {
 454                 return -1;
 455         }
 456
 457         if (!compatible_for_assignment(type->tp_base, new_base, "__bases__"))
 458                 return -1;
 459
 460         Py_INCREF(new_base);
 461         Py_INCREF(value);
 462
 463         old_bases = type->tp_bases;
 464         old_base = type->tp_base;
 465         old_mro = type->tp_mro;
 466
 467         type->tp_bases = value;
 468         type->tp_base = new_base;
 469
 470         if (mro_internal(type) < 0) {
 471                 goto bail;
 472         }
 473
 474         temp = PyList_New(0);
 475         if (!temp)
 476                 goto bail;
 477
 478         r = mro_subclasses(type, temp);
 479
 480         if (r < 0) {
 481                 for (i = 0; i < PyList_Size(temp); i++) {
 482                         PyTypeObject* cls;
 483                         PyObject* mro;
 484                         PyArg_UnpackTuple(PyList_GET_ITEM(temp, i),
 485                                          "", 2, 2, &cls, &mro);
 486                         Py_INCREF(mro);
 487                         ob = cls->tp_mro;
 488                         cls->tp_mro = mro;
 489                         Py_DECREF(ob);
 490                 }
 491                 Py_DECREF(temp);
 492                 goto bail;
 493         }
 494
 495         Py_DECREF(temp);
 496
 497         /* any base that was in __bases__ but now isn't, we
 498            need to remove |type| from its tp_subclasses.
 499            conversely, any class now in __bases__ that wasn't
 500            needs to have |type| added to its subclasses. */
 501
 502         /* for now, sod that: just remove from all old_bases,
 503            add to all new_bases */
 504
 505         for (i = PyTuple_GET_SIZE(old_bases) - 1; i >= 0; i--) {
 506                 ob = PyTuple_GET_ITEM(old_bases, i);
 507                 if (PyType_Check(ob)) {
 508                         remove_subclass(
 509                                 (PyTypeObject*)ob, type);
 510                 }
 511         }
 512
 513         for (i = PyTuple_GET_SIZE(value) - 1; i >= 0; i--) {
 514                 ob = PyTuple_GET_ITEM(value, i);
 515                 if (PyType_Check(ob)) {
 516                         if (add_subclass((PyTypeObject*)ob, type) < 0)
 517                                 r = -1;
 518                 }
 519         }
 520
 521         update_all_slots(type);
 522
 523         Py_DECREF(old_bases);
 524         Py_DECREF(old_base);
 525         Py_DECREF(old_mro);
 526
 527         return r;
 528
 529   bail:
 530         Py_DECREF(type->tp_bases);
 531         Py_DECREF(type->tp_base);
 532         if (type->tp_mro != old_mro) {
 533                 Py_DECREF(type->tp_mro);
 534         }
 535
 536         type->tp_bases = old_bases;
 537         type->tp_base = old_base;
 538         type->tp_mro = old_mro;
 539
 540         return -1;
 541 }
 542
 543 static PyObject *
 544 type_dict(PyTypeObject *type, void *context)
 545 {
 546         if (type->tp_dict == NULL) {
 547                 Py_INCREF(Py_None);
 548                 return Py_None;
 549         }
 550         return PyDictProxy_New(type->tp_dict);
 551 }
 552
 553 static PyObject *
 554 type_get_doc(PyTypeObject *type, void *context)
 555 {
 556         PyObject *result;
 557         if (!(type->tp_flags & Py_TPFLAGS_HEAPTYPE) && type->tp_doc != NULL)
 558                 return PyString_FromString(type->tp_doc);
 559         result = PyDict_GetItemString(type->tp_dict, "__doc__");
 560         if (result == NULL) {
 561                 result = Py_None;
 562                 Py_INCREF(result);
 563         }
 564         else if (Py_TYPE(result)->tp_descr_get) {
 565                 result = Py_TYPE(result)->tp_descr_get(result, NULL,
 566                                                        (PyObject *)type);
 567         }
 568         else {
 569                 Py_INCREF(result);
 570         }
 571         return result;
 572 }
 573
 574 static PyGetSetDef type_getsets[] = {
 575         {"__name__", (getter)type_name, (setter)type_set_name, NULL},
 576         {"__bases__", (getter)type_get_bases, (setter)type_set_bases, NULL},
 577         {"__module__", (getter)type_module, (setter)type_set_module, NULL},
 578         {"__abstractmethods__", (getter)type_abstractmethods,
 579          (setter)type_set_abstractmethods, NULL},
 580         {"__dict__",  (getter)type_dict,  NULL, NULL},
 581         {"__doc__", (getter)type_get_doc, NULL, NULL},
 582         {0}
 583 };
 584
 585 static int
 586 type_compare(PyObject *v, PyObject *w)
 587 {
 588         /* This is called with type objects only. So we
 589            can just compare the addresses. */
 590         Py_uintptr_t vv = (Py_uintptr_t)v;
 591         Py_uintptr_t ww = (Py_uintptr_t)w;
 592         return (vv < ww) ? -1 : (vv > ww) ? 1 : 0;
 593 }
 594
 595 static PyObject*
 596 type_richcompare(PyObject *v, PyObject *w, int op)
 597 {
 598         PyObject *result;
 599         Py_uintptr_t vv, ww;
 600         int c;
 601
 602         /* Make sure both arguments are types. */
 603         if (!PyType_Check(v) || !PyType_Check(w)) {
 604                 result = Py_NotImplemented;
 605                 goto out;
 606         }
 607
 608         /* Py3K warning if comparison isn't == or !=  */
 609         if (Py_Py3kWarningFlag && op != Py_EQ && op != Py_NE &&
 610                 PyErr_WarnEx(PyExc_DeprecationWarning,
 611                            "type inequality comparisons not supported "
 612                            "in 3.x", 1) < 0) {
 613                 return NULL;
 614         }
 615
 616         /* Compare addresses */
 617         vv = (Py_uintptr_t)v;
 618         ww = (Py_uintptr_t)w;
 619         switch (op) {
 620         case Py_LT: c = vv <  ww; break;
 621         case Py_LE: c = vv <= ww; break;
 622         case Py_EQ: c = vv == ww; break;
 623         case Py_NE: c = vv != ww; break;
 624         case Py_GT: c = vv >  ww; break;
 625         case Py_GE: c = vv >= ww; break;
 626         default:
 627                 result = Py_NotImplemented;
 628                 goto out;
 629         }
 630         result = c ? Py_True : Py_False;
 631
 632   /* incref and return */
 633   out:
 634         Py_INCREF(result);
 635         return result;
 636 }
 637
 638 static PyObject *
 639 type_repr(PyTypeObject *type)
 640 {
 641         PyObject *mod, *name, *rtn;
 642         char *kind;
 643
 644         mod = type_module(type, NULL);
 645         if (mod == NULL)
 646                 PyErr_Clear();
 647         else if (!PyString_Check(mod)) {
 648                 Py_DECREF(mod);
 649                 mod = NULL;
 650         }
 651         name = type_name(type, NULL);
 652         if (name == NULL)
 653                 return NULL;
 654
 655         if (type->tp_flags & Py_TPFLAGS_HEAPTYPE)
 656                 kind = "class";
 657         else
 658                 kind = "type";
 659
 660         if (mod != NULL && strcmp(PyString_AS_STRING(mod), "__builtin__")) {
 661                 rtn = PyString_FromFormat("<%s '%s.%s'>",
 662                                           kind,
 663                                           PyString_AS_STRING(mod),
 664                                           PyString_AS_STRING(name));
 665         }
 666         else
 667                 rtn = PyString_FromFormat("<%s '%s'>", kind, type->tp_name);
 668
 669         Py_XDECREF(mod);
 670         Py_DECREF(name);
 671         return rtn;
 672 }
 673
 674 static PyObject *
 675 type_call(PyTypeObject *type, PyObject *args, PyObject *kwds)
 676 {
 677         PyObject *obj;
 678
 679         if (type->tp_new == NULL) {
 680                 PyErr_Format(PyExc_TypeError,
 681                              "cannot create '%.100s' instances",
 682                              type->tp_name);
 683                 return NULL;
 684         }
 685
 686         obj = type->tp_new(type, args, kwds);
 687         if (obj != NULL) {
 688                 /* Ugly exception: when the call was type(something),
 689                    don't call tp_init on the result. */
 690                 if (type == &PyType_Type &&
 691                     PyTuple_Check(args) && PyTuple_GET_SIZE(args) == 1 &&
 692                     (kwds == NULL ||
 693                      (PyDict_Check(kwds) && PyDict_Size(kwds) == 0)))
 694                         return obj;
 695                 /* If the returned object is not an instance of type,
 696                    it won't be initialized. */
 697                 if (!PyType_IsSubtype(obj->ob_type, type))
 698                         return obj;
 699                 type = obj->ob_type;
 700                 if (PyType_HasFeature(type, Py_TPFLAGS_HAVE_CLASS) &&
 701                     type->tp_init != NULL &&
 702                     type->tp_init(obj, args, kwds) < 0) {
 703                         Py_DECREF(obj);
 704                         obj = NULL;
 705                 }
 706         }
 707         return obj;
 708 }
 709
 710 PyObject *
 711 PyType_GenericAlloc(PyTypeObject *type, Py_ssize_t nitems)
 712 {
 713         PyObject *obj;
 714         const size_t size = _PyObject_VAR_SIZE(type, nitems+1);
 715         /* note that we need to add one, for the sentinel */
 716
 717         if (PyType_IS_GC(type))
 718                 obj = _PyObject_GC_Malloc(size);
 719         else
 720                 obj = (PyObject *)PyObject_MALLOC(size);
 721
 722         if (obj == NULL)
 723                 return PyErr_NoMemory();
 724
 725         memset(obj, '\0', size);
 726
 727         if (type->tp_flags & Py_TPFLAGS_HEAPTYPE)
 728                 Py_INCREF(type);
 729
 730         if (type->tp_itemsize == 0)
 731                 PyObject_INIT(obj, type);
 732         else
 733                 (void) PyObject_INIT_VAR((PyVarObject *)obj, type, nitems);
 734
 735         if (PyType_IS_GC(type))
 736                 _PyObject_GC_TRACK(obj);
 737         return obj;
 738 }
 739
 740 PyObject *
 741 PyType_GenericNew(PyTypeObject *type, PyObject *args, PyObject *kwds)
 742 {
 743         return type->tp_alloc(type, 0);
 744 }
 745
 746 /* Helpers for subtyping */
 747
 748 static int
 749 traverse_slots(PyTypeObject *type, PyObject *self, visitproc visit, void *arg)
 750 {
 751         Py_ssize_t i, n;
 752         PyMemberDef *mp;
 753
 754         n = Py_SIZE(type);
 755         mp = PyHeapType_GET_MEMBERS((PyHeapTypeObject *)type);
 756         for (i = 0; i < n; i++, mp++) {
 757                 if (mp->type == T_OBJECT_EX) {
 758                         char *addr = (char *)self + mp->offset;
 759                         PyObject *obj = *(PyObject **)addr;
 760                         if (obj != NULL) {
 761                                 int err = visit(obj, arg);
 762                                 if (err)
 763                                         return err;
 764                         }
 765                 }
 766         }
 767         return 0;
 768 }
 769
 770 static int
 771 subtype_traverse(PyObject *self, visitproc visit, void *arg)
 772 {
 773         PyTypeObject *type, *base;
 774         traverseproc basetraverse;
 775
 776         /* Find the nearest base with a different tp_traverse,
 777            and traverse slots while we're at it */
 778         type = Py_TYPE(self);
 779         base = type;
 780         while ((basetraverse = base->tp_traverse) == subtype_traverse) {
 781                 if (Py_SIZE(base)) {
 782                         int err = traverse_slots(base, self, visit, arg);
 783                         if (err)
 784                                 return err;
 785                 }
 786                 base = base->tp_base;
 787                 assert(base);
 788         }
 789
 790         if (type->tp_dictoffset != base->tp_dictoffset) {
 791                 PyObject **dictptr = _PyObject_GetDictPtr(self);
 792                 if (dictptr && *dictptr)
 793                         Py_VISIT(*dictptr);
 794         }
 795
 796         if (type->tp_flags & Py_TPFLAGS_HEAPTYPE)
 797                 /* For a heaptype, the instances count as references
 798                    to the type.  Traverse the type so the collector
 799                    can find cycles involving this link. */
 800                 Py_VISIT(type);
 801
 802         if (basetraverse)
 803                 return basetraverse(self, visit, arg);
 804         return 0;
 805 }
 806
 807 static void
 808 clear_slots(PyTypeObject *type, PyObject *self)
 809 {
 810         Py_ssize_t i, n;
 811         PyMemberDef *mp;
 812
 813         n = Py_SIZE(type);
 814         mp = PyHeapType_GET_MEMBERS((PyHeapTypeObject *)type);
 815         for (i = 0; i < n; i++, mp++) {
 816                 if (mp->type == T_OBJECT_EX && !(mp->flags & READONLY)) {
 817                         char *addr = (char *)self + mp->offset;
 818                         PyObject *obj = *(PyObject **)addr;
 819                         if (obj != NULL) {
 820                                 *(PyObject **)addr = NULL;
 821                                 Py_DECREF(obj);
 822                         }
 823                 }
 824         }
 825 }
 826
 827 static int
 828 subtype_clear(PyObject *self)
 829 {
 830         PyTypeObject *type, *base;
 831         inquiry baseclear;
 832
 833         /* Find the nearest base with a different tp_clear
 834            and clear slots while we're at it */
 835         type = Py_TYPE(self);
 836         base = type;
 837         while ((baseclear = base->tp_clear) == subtype_clear) {
 838                 if (Py_SIZE(base))
 839                         clear_slots(base, self);
 840                 base = base->tp_base;
 841                 assert(base);
 842         }
 843
 844         /* There's no need to clear the instance dict (if any);
 845            the collector will call its tp_clear handler. */
 846
 847         if (baseclear)
 848                 return baseclear(self);
 849         return 0;
 850 }
 851
 852 static void
 853 subtype_dealloc(PyObject *self)
 854 {
 855         PyTypeObject *type, *base;
 856         destructor basedealloc;
 857
 858         /* Extract the type; we expect it to be a heap type */
 859         type = Py_TYPE(self);
 860         assert(type->tp_flags & Py_TPFLAGS_HEAPTYPE);
 861
 862         /* Test whether the type has GC exactly once */
 863
 864         if (!PyType_IS_GC(type)) {
 865                 /* It's really rare to find a dynamic type that doesn't have
 866                    GC; it can only happen when deriving from 'object' and not
 867                    adding any slots or instance variables.  This allows
 868                    certain simplifications: there's no need to call
 869                    clear_slots(), or DECREF the dict, or clear weakrefs. */
 870
 871                 /* Maybe call finalizer; exit early if resurrected */
 872                 if (type->tp_del) {
 873                         type->tp_del(self);
 874                         if (self->ob_refcnt > 0)
 875                                 return;
 876                 }
 877
 878                 /* Find the nearest base with a different tp_dealloc */
 879                 base = type;
 880                 while ((basedealloc = base->tp_dealloc) == subtype_dealloc) {
 881                         assert(Py_SIZE(base) == 0);
 882                         base = base->tp_base;
 883                         assert(base);
 884                 }
 885
 886                 /* Call the base tp_dealloc() */
 887                 assert(basedealloc);
 888                 basedealloc(self);
 889
 890                 /* Can't reference self beyond this point */
 891                 Py_DECREF(type);
 892
 893                 /* Done */
 894                 return;
 895         }
 896
 897         /* We get here only if the type has GC */
 898
 899         /* UnTrack and re-Track around the trashcan macro, alas */
 900         /* See explanation at end of function for full disclosure */
 901         PyObject_GC_UnTrack(self);
 902         ++_PyTrash_delete_nesting;
 903         Py_TRASHCAN_SAFE_BEGIN(self);
 904         --_PyTrash_delete_nesting;
 905         /* DO NOT restore GC tracking at this point.  weakref callbacks
 906          * (if any, and whether directly here or indirectly in something we
 907          * call) may trigger GC, and if self is tracked at that point, it
 908          * will look like trash to GC and GC will try to delete self again.
 909          */
 910
 911         /* Find the nearest base with a different tp_dealloc */
 912         base = type;
 913         while ((basedealloc = base->tp_dealloc) == subtype_dealloc) {
 914                 base = base->tp_base;
 915                 assert(base);
 916         }
 917
 918         /* If we added a weaklist, we clear it.  Do this *before* calling
 919            the finalizer (__del__), clearing slots, or clearing the instance
 920            dict. */
 921
 922         if (type->tp_weaklistoffset && !base->tp_weaklistoffset)
 923                 PyObject_ClearWeakRefs(self);
 924
 925         /* Maybe call finalizer; exit early if resurrected */
 926         if (type->tp_del) {
 927                 _PyObject_GC_TRACK(self);
 928                 type->tp_del(self);
 929                 if (self->ob_refcnt > 0)
 930                         goto endlabel;  /* resurrected */
 931                 else
 932                         _PyObject_GC_UNTRACK(self);
 933                 /* New weakrefs could be created during the finalizer call.
 934                     If this occurs, clear them out without calling their
 935                     finalizers since they might rely on part of the object
 936                     being finalized that has already been destroyed. */
 937                 if (type->tp_weaklistoffset && !base->tp_weaklistoffset) {
 938                         /* Modeled after GET_WEAKREFS_LISTPTR() */
 939                         PyWeakReference **list = (PyWeakReference **) \
 940                                 PyObject_GET_WEAKREFS_LISTPTR(self);
 941                         while (*list)
 942                                 _PyWeakref_ClearRef(*list);
 943                 }
 944         }
 945
 946         /*  Clear slots up to the nearest base with a different tp_dealloc */
 947         base = type;
 948         while ((basedealloc = base->tp_dealloc) == subtype_dealloc) {
 949                 if (Py_SIZE(base))
 950                         clear_slots(base, self);
 951                 base = base->tp_base;
 952                 assert(base);
 953         }
 954
 955         /* If we added a dict, DECREF it */
 956         if (type->tp_dictoffset && !base->tp_dictoffset) {
 957                 PyObject **dictptr = _PyObject_GetDictPtr(self);
 958                 if (dictptr != NULL) {
 959                         PyObject *dict = *dictptr;
 960                         if (dict != NULL) {
 961                                 Py_DECREF(dict);
 962                                 *dictptr = NULL;
 963                         }
 964                 }
 965         }
 966
 967         /* Call the base tp_dealloc(); first retrack self if
 968          * basedealloc knows about gc.
 969          */
 970         if (PyType_IS_GC(base))
 971                 _PyObject_GC_TRACK(self);
 972         assert(basedealloc);
 973         basedealloc(self);
 974
 975         /* Can't reference self beyond this point */
 976         Py_DECREF(type);
 977
 978   endlabel:
 979         ++_PyTrash_delete_nesting;
 980         Py_TRASHCAN_SAFE_END(self);
 981         --_PyTrash_delete_nesting;
 982
 983         /* Explanation of the weirdness around the trashcan macros:
 984
 985            Q. What do the trashcan macros do?
 986
 987            A. Read the comment titled "Trashcan mechanism" in object.h.
 988               For one, this explains why there must be a call to GC-untrack
 989               before the trashcan begin macro.  Without understanding the
 990               trashcan code, the answers to the following questions don't make
 991               sense.
 992
 993            Q. Why do we GC-untrack before the trashcan and then immediately
 994               GC-track again afterward?
 995
 996            A. In the case that the base class is GC-aware, the base class
 997               probably GC-untracks the object.  If it does that using the
 998               UNTRACK macro, this will crash when the object is already
 999               untracked.  Because we don't know what the base class does, the
1000               only safe thing is to make sure the object is tracked when we
1001               call the base class dealloc.  But...  The trashcan begin macro
1002               requires that the object is *untracked* before it is called.  So
1003               the dance becomes:
1004
1005                  GC untrack
1006                  trashcan begin
1007                  GC track
1008
1009            Q. Why did the last question say "immediately GC-track again"?
1010               It's nowhere near immediately.
1011
1012            A. Because the code *used* to re-track immediately.  Bad Idea.
1013               self has a refcount of 0, and if gc ever gets its hands on it
1014               (which can happen if any weakref callback gets invoked), it
1015               looks like trash to gc too, and gc also tries to delete self
1016               then.  But we're already deleting self.  Double dealloction is
1017               a subtle disaster.
1018
1019            Q. Why the bizarre (net-zero) manipulation of
1020               _PyTrash_delete_nesting around the trashcan macros?
1021
1022            A. Some base classes (e.g. list) also use the trashcan mechanism.
1023               The following scenario used to be possible:
1024
1025               - suppose the trashcan level is one below the trashcan limit
1026
1027               - subtype_dealloc() is called
1028
1029               - the trashcan limit is not yet reached, so the trashcan level
1030                 is incremented and the code between trashcan begin and end is
1031                 executed
1032
1033               - this destroys much of the object's contents, including its
1034                 slots and __dict__
1035
1036               - basedealloc() is called; this is really list_dealloc(), or
1037                 some other type which also uses the trashcan macros
1038
1039               - the trashcan limit is now reached, so the object is put on the
1040                 trashcan's to-be-deleted-later list
1041
1042               - basedealloc() returns
1043
1044               - subtype_dealloc() decrefs the object's type
1045
1046               - subtype_dealloc() returns
1047
1048               - later, the trashcan code starts deleting the objects from its
1049                 to-be-deleted-later list
1050
1051               - subtype_dealloc() is called *AGAIN* for the same object
1052
1053               - at the very least (if the destroyed slots and __dict__ don't
1054                 cause problems) the object's type gets decref'ed a second
1055                 time, which is *BAD*!!!
1056
1057               The remedy is to make sure that if the code between trashcan
1058               begin and end in subtype_dealloc() is called, the code between
1059               trashcan begin and end in basedealloc() will also be called.
1060               This is done by decrementing the level after passing into the
1061               trashcan block, and incrementing it just before leaving the
1062               block.
1063
1064               But now it's possible that a chain of objects consisting solely
1065               of objects whose deallocator is subtype_dealloc() will defeat
1066               the trashcan mechanism completely: the decremented level means
1067               that the effective level never reaches the limit.  Therefore, we
1068               *increment* the level *before* entering the trashcan block, and
1069               matchingly decrement it after leaving.  This means the trashcan
1070               code will trigger a little early, but that's no big deal.
1071
1072            Q. Are there any live examples of code in need of all this
1073               complexity?
1074
1075            A. Yes.  See SF bug 668433 for code that crashed (when Python was
1076               compiled in debug mode) before the trashcan level manipulations
1077               were added.  For more discussion, see SF patches 581742, 575073
1078               and bug 574207.
1079         */
1080 }
1081
1082 static PyTypeObject *solid_base(PyTypeObject *type);
1083
1084 /* type test with subclassing support */
1085
1086 int
1087 PyType_IsSubtype(PyTypeObject *a, PyTypeObject *b)
1088 {
1089         PyObject *mro;
1090
1091         if (!(a->tp_flags & Py_TPFLAGS_HAVE_CLASS))
1092                 return b == a || b == &PyBaseObject_Type;
1093
1094         mro = a->tp_mro;
1095         if (mro != NULL) {
1096                 /* Deal with multiple inheritance without recursion
1097                    by walking the MRO tuple */
1098                 Py_ssize_t i, n;
1099                 assert(PyTuple_Check(mro));
1100                 n = PyTuple_GET_SIZE(mro);
1101                 for (i = 0; i < n; i++) {
1102                         if (PyTuple_GET_ITEM(mro, i) == (PyObject *)b)
1103                                 return 1;
1104                 }
1105                 return 0;
1106         }
1107         else {
1108                 /* a is not completely initilized yet; follow tp_base */
1109                 do {
1110                         if (a == b)
1111                                 return 1;
1112                         a = a->tp_base;
1113                 } while (a != NULL);
1114                 return b == &PyBaseObject_Type;
1115         }
1116 }
1117
1118 /* Internal routines to do a method lookup in the type
1119    without looking in the instance dictionary
1120    (so we can't use PyObject_GetAttr) but still binding
1121    it to the instance.  The arguments are the object,
1122    the method name as a C string, and the address of a
1123    static variable used to cache the interned Python string.
1124
1125    Two variants:
1126
1127    - lookup_maybe() returns NULL without raising an exception
1128      when the _PyType_Lookup() call fails;
1129
1130    - lookup_method() always raises an exception upon errors.
1131 */
1132
1133 static PyObject *
1134 lookup_maybe(PyObject *self, char *attrstr, PyObject **attrobj)
1135 {
1136         PyObject *res;
1137
1138         if (*attrobj == NULL) {
1139                 *attrobj = PyString_InternFromString(attrstr);
1140                 if (*attrobj == NULL)
1141                         return NULL;
1142         }
1143         res = _PyType_Lookup(Py_TYPE(self), *attrobj);
1144         if (res != NULL) {
1145                 descrgetfunc f;
1146                 if ((f = Py_TYPE(res)->tp_descr_get) == NULL)
1147                         Py_INCREF(res);
1148                 else
1149                         res = f(res, self, (PyObject *)(Py_TYPE(self)));
1150         }
1151         return res;
1152 }
1153
1154 static PyObject *
1155 lookup_method(PyObject *self, char *attrstr, PyObject **attrobj)
1156 {
1157         PyObject *res = lookup_maybe(self, attrstr, attrobj);
1158         if (res == NULL && !PyErr_Occurred())
1159                 PyErr_SetObject(PyExc_AttributeError, *attrobj);
1160         return res;
1161 }
1162
1163 /* A variation of PyObject_CallMethod that uses lookup_method()
1164    instead of PyObject_GetAttrString().  This uses the same convention
1165    as lookup_method to cache the interned name string object. */
1166
1167 static PyObject *
1168 call_method(PyObject *o, char *name, PyObject **nameobj, char *format, ...)
1169 {
1170         va_list va;
1171         PyObject *args, *func = 0, *retval;
1172         va_start(va, format);
1173
1174         func = lookup_maybe(o, name, nameobj);
1175         if (func == NULL) {
1176                 va_end(va);
1177                 if (!PyErr_Occurred())
1178                         PyErr_SetObject(PyExc_AttributeError, *nameobj);
1179                 return NULL;
1180         }
1181
1182         if (format && *format)
1183                 args = Py_VaBuildValue(format, va);
1184         else
1185                 args = PyTuple_New(0);
1186
1187         va_end(va);
1188
1189         if (args == NULL)
1190                 return NULL;
1191
1192         assert(PyTuple_Check(args));
1193         retval = PyObject_Call(func, args, NULL);
1194
1195         Py_DECREF(args);
1196         Py_DECREF(func);
1197
1198         return retval;
1199 }
1200
1201 /* Clone of call_method() that returns NotImplemented when the lookup fails. */
1202
1203 static PyObject *
1204 call_maybe(PyObject *o, char *name, PyObject **nameobj, char *format, ...)
1205 {
1206         va_list va;
1207         PyObject *args, *func = 0, *retval;
1208         va_start(va, format);
1209
1210         func = lookup_maybe(o, name, nameobj);
1211         if (func == NULL) {
1212                 va_end(va);
1213                 if (!PyErr_Occurred()) {
1214                         Py_INCREF(Py_NotImplemented);
1215                         return Py_NotImplemented;
1216                 }
1217                 return NULL;
1218         }
1219
1220         if (format && *format)
1221                 args = Py_VaBuildValue(format, va);
1222         else
1223                 args = PyTuple_New(0);
1224
1225         va_end(va);
1226
1227         if (args == NULL)
1228                 return NULL;
1229
1230         assert(PyTuple_Check(args));
1231         retval = PyObject_Call(func, args, NULL);
1232
1233         Py_DECREF(args);
1234         Py_DECREF(func);
1235
1236         return retval;
1237 }
1238
1239 static int
1240 fill_classic_mro(PyObject *mro, PyObject *cls)
1241 {
1242         PyObject *bases, *base;
1243         Py_ssize_t i, n;
1244
1245         assert(PyList_Check(mro));
1246         assert(PyClass_Check(cls));
1247         i = PySequence_Contains(mro, cls);
1248         if (i < 0)
1249                 return -1;
1250         if (!i) {
1251                 if (PyList_Append(mro, cls) < 0)
1252                         return -1;
1253         }
1254         bases = ((PyClassObject *)cls)->cl_bases;
1255         assert(bases && PyTuple_Check(bases));
1256         n = PyTuple_GET_SIZE(bases);
1257         for (i = 0; i < n; i++) {
1258                 base = PyTuple_GET_ITEM(bases, i);
1259                 if (fill_classic_mro(mro, base) < 0)
1260                         return -1;
1261         }
1262         return 0;
1263 }
1264
1265 static PyObject *
1266 classic_mro(PyObject *cls)
1267 {
1268         PyObject *mro;
1269
1270         assert(PyClass_Check(cls));
1271         mro = PyList_New(0);
1272         if (mro != NULL) {
1273                 if (fill_classic_mro(mro, cls) == 0)
1274                         return mro;
1275                 Py_DECREF(mro);
1276         }
1277         return NULL;
1278 }
1279
1280 /*
1281     Method resolution order algorithm C3 described in
1282     "A Monotonic Superclass Linearization for Dylan",
1283     by Kim Barrett, Bob Cassel, Paul Haahr,
1284     David A. Moon, Keith Playford, and P. Tucker Withington.
1285     (OOPSLA 1996)
1286
1287     Some notes about the rules implied by C3:
1288
1289     No duplicate bases.
1290     It isn't legal to repeat a class in a list of base classes.
1291
1292     The next three properties are the 3 constraints in "C3".
1293
1294     Local precendece order.
1295     If A precedes B in C's MRO, then A will precede B in the MRO of all
1296     subclasses of C.
1297
1298     Monotonicity.
1299     The MRO of a class must be an extension without reordering of the
1300     MRO of each of its superclasses.
1301
1302     Extended Precedence Graph (EPG).
1303     Linearization is consistent if there is a path in the EPG from
1304     each class to all its successors in the linearization.  See
1305     the paper for definition of EPG.
1306  */
1307
1308 static int
1309 tail_contains(PyObject *list, int whence, PyObject *o) {
1310         Py_ssize_t j, size;
1311         size = PyList_GET_SIZE(list);
1312
1313         for (j = whence+1; j < size; j++) {
1314                 if (PyList_GET_ITEM(list, j) == o)
1315                         return 1;
1316         }
1317         return 0;
1318 }
1319
1320 static PyObject *
1321 class_name(PyObject *cls)
1322 {
1323         PyObject *name = PyObject_GetAttrString(cls, "__name__");
1324         if (name == NULL) {
1325                 PyErr_Clear();
1326                 Py_XDECREF(name);
1327                 name = PyObject_Repr(cls);
1328         }
1329         if (name == NULL)
1330                 return NULL;
1331         if (!PyString_Check(name)) {
1332                 Py_DECREF(name);
1333                 return NULL;
1334         }
1335         return name;
1336 }
1337
1338 static int
1339 check_duplicates(PyObject *list)
1340 {
1341         Py_ssize_t i, j, n;
1342         /* Let's use a quadratic time algorithm,
1343            assuming that the bases lists is short.
1344         */
1345         n = PyList_GET_SIZE(list);
1346         for (i = 0; i < n; i++) {
1347                 PyObject *o = PyList_GET_ITEM(list, i);
1348                 for (j = i + 1; j < n; j++) {
1349                         if (PyList_GET_ITEM(list, j) == o) {
1350                                 o = class_name(o);
1351                                 PyErr_Format(PyExc_TypeError,
1352                                              "duplicate base class %s",
1353                                              o ? PyString_AS_STRING(o) : "?");
1354                                 Py_XDECREF(o);
1355                                 return -1;
1356                         }
1357                 }
1358         }
1359         return 0;
1360 }
1361
1362 /* Raise a TypeError for an MRO order disagreement.
1363
1364    It's hard to produce a good error message.  In the absence of better
1365    insight into error reporting, report the classes that were candidates
1366    to be put next into the MRO.  There is some conflict between the
1367    order in which they should be put in the MRO, but it's hard to
1368    diagnose what constraint can't be satisfied.
1369 */
1370
1371 static void
1372 set_mro_error(PyObject *to_merge, int *remain)
1373 {
1374         Py_ssize_t i, n, off, to_merge_size;
1375         char buf[1000];
1376         PyObject *k, *v;
1377         PyObject *set = PyDict_New();
1378         if (!set) return;
1379
1380         to_merge_size = PyList_GET_SIZE(to_merge);
1381         for (i = 0; i < to_merge_size; i++) {
1382                 PyObject *L = PyList_GET_ITEM(to_merge, i);
1383                 if (remain[i] < PyList_GET_SIZE(L)) {
1384                         PyObject *c = PyList_GET_ITEM(L, remain[i]);
1385                         if (PyDict_SetItem(set, c, Py_None) < 0) {
1386                                 Py_DECREF(set);
1387                                 return;
1388                         }
1389                 }
1390         }
1391         n = PyDict_Size(set);
1392
1393         off = PyOS_snprintf(buf, sizeof(buf), "Cannot create a \
1394 consistent method resolution\norder (MRO) for bases");
1395         i = 0;
1396         while (PyDict_Next(set, &i, &k, &v) && (size_t)off < sizeof(buf)) {
1397                 PyObject *name = class_name(k);
1398                 off += PyOS_snprintf(buf + off, sizeof(buf) - off, " %s",
1399                                      name ? PyString_AS_STRING(name) : "?");
1400                 Py_XDECREF(name);
1401                 if (--n && (size_t)(off+1) < sizeof(buf)) {
1402                         buf[off++] = ',';
1403                         buf[off] = '\0';
1404                 }
1405         }
1406         PyErr_SetString(PyExc_TypeError, buf);
1407         Py_DECREF(set);
1408 }
1409
1410 static int
1411 pmerge(PyObject *acc, PyObject* to_merge) {
1412         Py_ssize_t i, j, to_merge_size, empty_cnt;
1413         int *remain;
1414         int ok;
1415
1416         to_merge_size = PyList_GET_SIZE(to_merge);
1417
1418         /* remain stores an index into each sublist of to_merge.
1419            remain[i] is the index of the next base in to_merge[i]
1420            that is not included in acc.
1421         */
1422         remain = (int *)PyMem_MALLOC(SIZEOF_INT*to_merge_size);
1423         if (remain == NULL)
1424                 return -1;
1425         for (i = 0; i < to_merge_size; i++)
1426                 remain[i] = 0;
1427
1428   again:
1429         empty_cnt = 0;
1430         for (i = 0; i < to_merge_size; i++) {
1431                 PyObject *candidate;
1432
1433                 PyObject *cur_list = PyList_GET_ITEM(to_merge, i);
1434
1435                 if (remain[i] >= PyList_GET_SIZE(cur_list)) {
1436                         empty_cnt++;
1437                         continue;
1438                 }
1439
1440                 /* Choose next candidate for MRO.
1441
1442                    The input sequences alone can determine the choice.
1443                    If not, choose the class which appears in the MRO
1444                    of the earliest direct superclass of the new class.
1445                 */
1446
1447                 candidate = PyList_GET_ITEM(cur_list, remain[i]);
1448                 for (j = 0; j < to_merge_size; j++) {
1449                         PyObject *j_lst = PyList_GET_ITEM(to_merge, j);
1450                         if (tail_contains(j_lst, remain[j], candidate)) {
1451                                 goto skip; /* continue outer loop */
1452                         }
1453                 }
1454                 ok = PyList_Append(acc, candidate);
1455                 if (ok < 0) {
1456                         PyMem_Free(remain);
1457                         return -1;
1458                 }
1459                 for (j = 0; j < to_merge_size; j++) {
1460                         PyObject *j_lst = PyList_GET_ITEM(to_merge, j);
1461                         if (remain[j] < PyList_GET_SIZE(j_lst) &&
1462                             PyList_GET_ITEM(j_lst, remain[j]) == candidate) {
1463                                 remain[j]++;
1464                         }
1465                 }
1466                 goto again;
1467           skip: ;
1468         }
1469
1470         if (empty_cnt == to_merge_size) {
1471                 PyMem_FREE(remain);
1472                 return 0;
1473         }
1474         set_mro_error(to_merge, remain);
1475         PyMem_FREE(remain);
1476         return -1;
1477 }
1478
1479 static PyObject *
1480 mro_implementation(PyTypeObject *type)
1481 {
1482         Py_ssize_t i, n;
1483         int ok;
1484         PyObject *bases, *result;
1485         PyObject *to_merge, *bases_aslist;
1486
1487         if (type->tp_dict == NULL) {
1488                 if (PyType_Ready(type) < 0)
1489                         return NULL;
1490         }
1491
1492         /* Find a superclass linearization that honors the constraints
1493            of the explicit lists of bases and the constraints implied by
1494            each base class.
1495
1496            to_merge is a list of lists, where each list is a superclass
1497            linearization implied by a base class.  The last element of
1498            to_merge is the declared list of bases.
1499         */
1500
1501         bases = type->tp_bases;
1502         n = PyTuple_GET_SIZE(bases);
1503
1504         to_merge = PyList_New(n+1);
1505         if (to_merge == NULL)
1506                 return NULL;
1507
1508         for (i = 0; i < n; i++) {
1509                 PyObject *base = PyTuple_GET_ITEM(bases, i);
1510                 PyObject *parentMRO;
1511                 if (PyType_Check(base))
1512                         parentMRO = PySequence_List(
1513                                 ((PyTypeObject*)base)->tp_mro);
1514                 else
1515                         parentMRO = classic_mro(base);
1516                 if (parentMRO == NULL) {
1517                         Py_DECREF(to_merge);
1518                         return NULL;
1519                 }
1520
1521                 PyList_SET_ITEM(to_merge, i, parentMRO);
1522         }
1523
1524         bases_aslist = PySequence_List(bases);
1525         if (bases_aslist == NULL) {
1526                 Py_DECREF(to_merge);
1527                 return NULL;
1528         }
1529         /* This is just a basic sanity check. */
1530         if (check_duplicates(bases_aslist) < 0) {
1531                 Py_DECREF(to_merge);
1532                 Py_DECREF(bases_aslist);
1533                 return NULL;
1534         }
1535         PyList_SET_ITEM(to_merge, n, bases_aslist);
1536
1537         result = Py_BuildValue("[O]", (PyObject *)type);
1538         if (result == NULL) {
1539                 Py_DECREF(to_merge);
1540                 return NULL;
1541         }
1542
1543         ok = pmerge(result, to_merge);
1544         Py_DECREF(to_merge);
1545         if (ok < 0) {
1546                 Py_DECREF(result);
1547                 return NULL;
1548         }
1549
1550         return result;
1551 }
1552
1553 static PyObject *
1554 mro_external(PyObject *self)
1555 {
1556         PyTypeObject *type = (PyTypeObject *)self;
1557
1558         return mro_implementation(type);
1559 }
1560
1561 static int
1562 mro_internal(PyTypeObject *type)
1563 {
1564         PyObject *mro, *result, *tuple;
1565         int checkit = 0;
1566
1567         if (Py_TYPE(type) == &PyType_Type) {
1568                 result = mro_implementation(type);
1569         }
1570         else {
1571                 static PyObject *mro_str;
1572                 checkit = 1;
1573                 mro = lookup_method((PyObject *)type, "mro", &mro_str);
1574                 if (mro == NULL)
1575                         return -1;
1576                 result = PyObject_CallObject(mro, NULL);
1577                 Py_DECREF(mro);
1578         }
1579         if (result == NULL)
1580                 return -1;
1581         tuple = PySequence_Tuple(result);
1582         Py_DECREF(result);
1583         if (tuple == NULL)
1584                 return -1;
1585         if (checkit) {
1586                 Py_ssize_t i, len;
1587                 PyObject *cls;
1588                 PyTypeObject *solid;
1589
1590                 solid = solid_base(type);
1591
1592                 len = PyTuple_GET_SIZE(tuple);
1593
1594                 for (i = 0; i < len; i++) {
1595                         PyTypeObject *t;
1596                         cls = PyTuple_GET_ITEM(tuple, i);
1597                         if (PyClass_Check(cls))
1598                                 continue;
1599                         else if (!PyType_Check(cls)) {
1600                                 PyErr_Format(PyExc_TypeError,
1601                              "mro() returned a non-class ('%.500s')",
1602                                              Py_TYPE(cls)->tp_name);
1603                                 Py_DECREF(tuple);
1604                                 return -1;
1605                         }
1606                         t = (PyTypeObject*)cls;
1607                         if (!PyType_IsSubtype(solid, solid_base(t))) {
1608                                 PyErr_Format(PyExc_TypeError,
1609                      "mro() returned base with unsuitable layout ('%.500s')",
1610                                              t->tp_name);
1611                                 Py_DECREF(tuple);
1612                                 return -1;
1613                         }
1614                 }
1615         }
1616         type->tp_mro = tuple;
1617
1618         type_mro_modified(type, type->tp_mro);
1619         /* corner case: the old-style super class might have been hidden
1620            from the custom MRO */
1621         type_mro_modified(type, type->tp_bases);
1622
1623         PyType_Modified(type);
1624
1625         return 0;
1626 }
1627
1628
1629 /* Calculate the best base amongst multiple base classes.
1630    This is the first one that's on the path to the "solid base". */
1631
1632 static PyTypeObject *
1633 best_base(PyObject *bases)
1634 {
1635         Py_ssize_t i, n;
1636         PyTypeObject *base, *winner, *candidate, *base_i;
1637         PyObject *base_proto;
1638
1639         assert(PyTuple_Check(bases));
1640         n = PyTuple_GET_SIZE(bases);
1641         assert(n > 0);
1642         base = NULL;
1643         winner = NULL;
1644         for (i = 0; i < n; i++) {
1645                 base_proto = PyTuple_GET_ITEM(bases, i);
1646                 if (PyClass_Check(base_proto))
1647                         continue;
1648                 if (!PyType_Check(base_proto)) {
1649                         PyErr_SetString(
1650                                 PyExc_TypeError,
1651                                 "bases must be types");
1652                         return NULL;
1653                 }
1654                 base_i = (PyTypeObject *)base_proto;
1655                 if (base_i->tp_dict == NULL) {
1656                         if (PyType_Ready(base_i) < 0)
1657                                 return NULL;
1658                 }
1659                 candidate = solid_base(base_i);
1660                 if (winner == NULL) {
1661                         winner = candidate;
1662                         base = base_i;
1663                 }
1664                 else if (PyType_IsSubtype(winner, candidate))
1665                         ;
1666                 else if (PyType_IsSubtype(candidate, winner)) {
1667                         winner = candidate;
1668                         base = base_i;
1669                 }
1670                 else {
1671                         PyErr_SetString(
1672                                 PyExc_TypeError,
1673                                 "multiple bases have "
1674                                 "instance lay-out conflict");
1675                         return NULL;
1676                 }
1677         }
1678         if (base == NULL)
1679                 PyErr_SetString(PyExc_TypeError,
1680                         "a new-style class can't have only classic bases");
1681         return base;
1682 }
1683
1684 static int
1685 extra_ivars(PyTypeObject *type, PyTypeObject *base)
1686 {
1687         size_t t_size = type->tp_basicsize;
1688         size_t b_size = base->tp_basicsize;
1689
1690         assert(t_size >= b_size); /* Else type smaller than base! */
1691         if (type->tp_itemsize || base->tp_itemsize) {
1692                 /* If itemsize is involved, stricter rules */
1693                 return t_size != b_size ||
1694                         type->tp_itemsize != base->tp_itemsize;
1695         }
1696         if (type->tp_weaklistoffset && base->tp_weaklistoffset == 0 &&
1697             type->tp_weaklistoffset + sizeof(PyObject *) == t_size &&
1698             type->tp_flags & Py_TPFLAGS_HEAPTYPE)
1699                 t_size -= sizeof(PyObject *);
1700         if (type->tp_dictoffset && base->tp_dictoffset == 0 &&
1701             type->tp_dictoffset + sizeof(PyObject *) == t_size &&
1702             type->tp_flags & Py_TPFLAGS_HEAPTYPE)
1703                 t_size -= sizeof(PyObject *);
1704
1705         return t_size != b_size;
1706 }
1707
1708 static PyTypeObject *
1709 solid_base(PyTypeObject *type)
1710 {
1711         PyTypeObject *base;
1712
1713         if (type->tp_base)
1714                 base = solid_base(type->tp_base);
1715         else
1716                 base = &PyBaseObject_Type;
1717         if (extra_ivars(type, base))
1718                 return type;
1719         else
1720                 return base;
1721 }
1722
1723 static void object_dealloc(PyObject *);
1724 static int object_init(PyObject *, PyObject *, PyObject *);
1725 static int update_slot(PyTypeObject *, PyObject *);
1726 static void fixup_slot_dispatchers(PyTypeObject *);
1727
1728 /*
1729  * Helpers for  __dict__ descriptor.  We don't want to expose the dicts
1730  * inherited from various builtin types.  The builtin base usually provides
1731  * its own __dict__ descriptor, so we use that when we can.
1732  */
1733 static PyTypeObject *
1734 get_builtin_base_with_dict(PyTypeObject *type)
1735 {
1736         while (type->tp_base != NULL) {
1737                 if (type->tp_dictoffset != 0 &&
1738                     !(type->tp_flags & Py_TPFLAGS_HEAPTYPE))
1739                         return type;
1740                 type = type->tp_base;
1741         }
1742         return NULL;
1743 }
1744
1745 static PyObject *
1746 get_dict_descriptor(PyTypeObject *type)
1747 {
1748         static PyObject *dict_str;
1749         PyObject *descr;
1750
1751         if (dict_str == NULL) {
1752                 dict_str = PyString_InternFromString("__dict__");
1753                 if (dict_str == NULL)
1754                         return NULL;
1755         }
1756         descr = _PyType_Lookup(type, dict_str);
1757         if (descr == NULL || !PyDescr_IsData(descr))
1758                 return NULL;
1759
1760         return descr;
1761 }
1762
1763 static void
1764 raise_dict_descr_error(PyObject *obj)
1765 {
1766         PyErr_Format(PyExc_TypeError,
1767                      "this __dict__ descriptor does not support "
1768                      "'%.200s' objects", obj->ob_type->tp_name);
1769 }
1770
1771 static PyObject *
1772 subtype_dict(PyObject *obj, void *context)
1773 {
1774         PyObject **dictptr;
1775         PyObject *dict;
1776         PyTypeObject *base;
1777
1778         base = get_builtin_base_with_dict(obj->ob_type);
1779         if (base != NULL) {
1780                 descrgetfunc func;
1781                 PyObject *descr = get_dict_descriptor(base);
1782                 if (descr == NULL) {
1783                         raise_dict_descr_error(obj);
1784                         return NULL;
1785                 }
1786                 func = descr->ob_type->tp_descr_get;
1787                 if (func == NULL) {
1788                         raise_dict_descr_error(obj);
1789                         return NULL;
1790                 }
1791                 return func(descr, obj, (PyObject *)(obj->ob_type));
1792         }
1793
1794         dictptr = _PyObject_GetDictPtr(obj);
1795         if (dictptr == NULL) {
1796                 PyErr_SetString(PyExc_AttributeError,
1797                                 "This object has no __dict__");
1798                 return NULL;
1799         }
1800         dict = *dictptr;
1801         if (dict == NULL)
1802                 *dictptr = dict = PyDict_New();
1803         Py_XINCREF(dict);
1804         return dict;
1805 }
1806
1807 static int
1808 subtype_setdict(PyObject *obj, PyObject *value, void *context)
1809 {
1810         PyObject **dictptr;
1811         PyObject *dict;
1812         PyTypeObject *base;
1813
1814         base = get_builtin_base_with_dict(obj->ob_type);
1815         if (base != NULL) {
1816                 descrsetfunc func;
1817                 PyObject *descr = get_dict_descriptor(base);
1818                 if (descr == NULL) {
1819                         raise_dict_descr_error(obj);
1820                         return -1;
1821                 }
1822                 func = descr->ob_type->tp_descr_set;
1823                 if (func == NULL) {
1824                         raise_dict_descr_error(obj);
1825                         return -1;
1826                 }
1827                 return func(descr, obj, value);
1828         }
1829
1830         dictptr = _PyObject_GetDictPtr(obj);
1831         if (dictptr == NULL) {
1832                 PyErr_SetString(PyExc_AttributeError,
1833                                 "This object has no __dict__");
1834                 return -1;
1835         }
1836         if (value != NULL && !PyDict_Check(value)) {
1837                 PyErr_Format(PyExc_TypeError,
1838                              "__dict__ must be set to a dictionary, "
1839                              "not a '%.200s'", Py_TYPE(value)->tp_name);
1840                 return -1;
1841         }
1842         dict = *dictptr;
1843         Py_XINCREF(value);
1844         *dictptr = value;
1845         Py_XDECREF(dict);
1846         return 0;
1847 }
1848
1849 static PyObject *
1850 subtype_getweakref(PyObject *obj, void *context)
1851 {
1852         PyObject **weaklistptr;
1853         PyObject *result;
1854
1855         if (Py_TYPE(obj)->tp_weaklistoffset == 0) {
1856                 PyErr_SetString(PyExc_AttributeError,
1857                                 "This object has no __weakref__");
1858                 return NULL;
1859         }
1860         assert(Py_TYPE(obj)->tp_weaklistoffset > 0);
1861         assert(Py_TYPE(obj)->tp_weaklistoffset + sizeof(PyObject *) <=
1862                (size_t)(Py_TYPE(obj)->tp_basicsize));
1863         weaklistptr = (PyObject **)
1864                 ((char *)obj + Py_TYPE(obj)->tp_weaklistoffset);
1865         if (*weaklistptr == NULL)
1866                 result = Py_None;
1867         else
1868                 result = *weaklistptr;
1869         Py_INCREF(result);
1870         return result;
1871 }
1872
1873 /* Three variants on the subtype_getsets list. */
1874
1875 static PyGetSetDef subtype_getsets_full[] = {
1876         {"__dict__", subtype_dict, subtype_setdict,
1877          PyDoc_STR("dictionary for instance variables (if defined)")},
1878         {"__weakref__", subtype_getweakref, NULL,
1879          PyDoc_STR("list of weak references to the object (if defined)")},
1880         {0}
1881 };
1882
1883 static PyGetSetDef subtype_getsets_dict_only[] = {
1884         {"__dict__", subtype_dict, subtype_setdict,
1885          PyDoc_STR("dictionary for instance variables (if defined)")},
1886         {0}
1887 };
1888
1889 static PyGetSetDef subtype_getsets_weakref_only[] = {
1890         {"__weakref__", subtype_getweakref, NULL,
1891          PyDoc_STR("list of weak references to the object (if defined)")},
1892         {0}
1893 };
1894
1895 static int
1896 valid_identifier(PyObject *s)
1897 {
1898         unsigned char *p;
1899         Py_ssize_t i, n;
1900
1901         if (!PyString_Check(s)) {
1902                 PyErr_Format(PyExc_TypeError,
1903                              "__slots__ items must be strings, not '%.200s'",
1904                              Py_TYPE(s)->tp_name);
1905                 return 0;
1906         }
1907         p = (unsigned char *) PyString_AS_STRING(s);
1908         n = PyString_GET_SIZE(s);
1909         /* We must reject an empty name.  As a hack, we bump the
1910            length to 1 so that the loop will balk on the trailing \0. */
1911         if (n == 0)
1912                 n = 1;
1913         for (i = 0; i < n; i++, p++) {
1914                 if (!(i == 0 ? isalpha(*p) : isalnum(*p)) && *p != '_') {
1915                         PyErr_SetString(PyExc_TypeError,
1916                                         "__slots__ must be identifiers");
1917                         return 0;
1918                 }
1919         }
1920         return 1;
1921 }
1922
1923 #ifdef Py_USING_UNICODE
1924 /* Replace Unicode objects in slots.  */
1925
1926 static PyObject *
1927 _unicode_to_string(PyObject *slots, Py_ssize_t nslots)
1928 {
1929         PyObject *tmp = NULL;
1930         PyObject *slot_name, *new_name;
1931         Py_ssize_t i;
1932
1933         for (i = 0; i < nslots; i++) {
1934                 if (PyUnicode_Check(slot_name = PyTuple_GET_ITEM(slots, i))) {
1935                         if (tmp == NULL) {
1936                                 tmp = PySequence_List(slots);
1937                                 if (tmp == NULL)
1938                                         return NULL;
1939                         }
1940                         new_name = _PyUnicode_AsDefaultEncodedString(slot_name,
1941                                                                      NULL);
1942                         if (new_name == NULL) {
1943                                 Py_DECREF(tmp);
1944                                 return NULL;
1945                         }
1946                         Py_INCREF(new_name);
1947                         PyList_SET_ITEM(tmp, i, new_name);
1948                         Py_DECREF(slot_name);
1949                 }
1950         }
1951         if (tmp != NULL) {
1952                 slots = PyList_AsTuple(tmp);
1953                 Py_DECREF(tmp);
1954         }
1955         return slots;
1956 }
1957 #endif
1958
1959 /* Forward */
1960 static int
1961 object_init(PyObject *self, PyObject *args, PyObject *kwds);
1962
1963 static int
1964 type_init(PyObject *cls, PyObject *args, PyObject *kwds)
1965 {
1966         int res;
1967
1968         assert(args != NULL && PyTuple_Check(args));
1969         assert(kwds == NULL || PyDict_Check(kwds));
1970
1971         if (kwds != NULL && PyDict_Check(kwds) && PyDict_Size(kwds) != 0) {
1972                 PyErr_SetString(PyExc_TypeError,
1973                                 "type.__init__() takes no keyword arguments");
1974                 return -1;
1975         }
1976
1977         if (args != NULL && PyTuple_Check(args) &&
1978             (PyTuple_GET_SIZE(args) != 1 && PyTuple_GET_SIZE(args) != 3)) {
1979                 PyErr_SetString(PyExc_TypeError,
1980                                 "type.__init__() takes 1 or 3 arguments");
1981                 return -1;
1982         }
1983
1984         /* Call object.__init__(self) now. */
1985         /* XXX Could call super(type, cls).__init__() but what's the point? */
1986         args = PyTuple_GetSlice(args, 0, 0);
1987         res = object_init(cls, args, NULL);
1988         Py_DECREF(args);
1989         return res;
1990 }
1991
1992 static PyObject *
1993 type_new(PyTypeObject *metatype, PyObject *args, PyObject *kwds)
1994 {
1995         PyObject *name, *bases, *dict;
1996         static char *kwlist[] = {"name", "bases", "dict", 0};
1997         PyObject *slots, *tmp, *newslots;
1998         PyTypeObject *type, *base, *tmptype, *winner;
1999         PyHeapTypeObject *et;
2000         PyMemberDef *mp;
2001         Py_ssize_t i, nbases, nslots, slotoffset, add_dict, add_weak;
2002         int j, may_add_dict, may_add_weak;
2003
2004         assert(args != NULL && PyTuple_Check(args));
2005         assert(kwds == NULL || PyDict_Check(kwds));
2006
2007         /* Special case: type(x) should return x->ob_type */
2008         {
2009                 const Py_ssize_t nargs = PyTuple_GET_SIZE(args);
2010                 const Py_ssize_t nkwds = kwds == NULL ? 0 : PyDict_Size(kwds);
2011
2012                 if (PyType_CheckExact(metatype) && nargs == 1 && nkwds == 0) {
2013                         PyObject *x = PyTuple_GET_ITEM(args, 0);
2014                         Py_INCREF(Py_TYPE(x));
2015                         return (PyObject *) Py_TYPE(x);
2016                 }
2017
2018                 /* SF bug 475327 -- if that didn't trigger, we need 3
2019                    arguments. but PyArg_ParseTupleAndKeywords below may give
2020                    a msg saying type() needs exactly 3. */
2021                 if (nargs + nkwds != 3) {
2022                         PyErr_SetString(PyExc_TypeError,
2023                                         "type() takes 1 or 3 arguments");
2024                         return NULL;
2025                 }
2026         }
2027
2028         /* Check arguments: (name, bases, dict) */
2029         if (!PyArg_ParseTupleAndKeywords(args, kwds, "SO!O!:type", kwlist,
2030                                          &name,
2031                                          &PyTuple_Type, &bases,
2032                                          &PyDict_Type, &dict))
2033                 return NULL;
2034
2035         /* Determine the proper metatype to deal with this,
2036            and check for metatype conflicts while we're at it.
2037            Note that if some other metatype wins to contract,
2038            it's possible that its instances are not types. */
2039         nbases = PyTuple_GET_SIZE(bases);
2040         winner = metatype;
2041         for (i = 0; i < nbases; i++) {
2042                 tmp = PyTuple_GET_ITEM(bases, i);
2043                 tmptype = tmp->ob_type;
2044                 if (tmptype == &PyClass_Type)
2045                         continue; /* Special case classic classes */
2046                 if (PyType_IsSubtype(winner, tmptype))
2047                         continue;
2048                 if (PyType_IsSubtype(tmptype, winner)) {
2049                         winner = tmptype;
2050                         continue;
2051                 }
2052                 PyErr_SetString(PyExc_TypeError,
2053                                 "metaclass conflict: "
2054                                 "the metaclass of a derived class "
2055                                 "must be a (non-strict) subclass "
2056                                 "of the metaclasses of all its bases");
2057                 return NULL;
2058         }
2059         if (winner != metatype) {
2060                 if (winner->tp_new != type_new) /* Pass it to the winner */
2061                         return winner->tp_new(winner, args, kwds);
2062                 metatype = winner;
2063         }
2064
2065         /* Adjust for empty tuple bases */
2066         if (nbases == 0) {
2067                 bases = PyTuple_Pack(1, &PyBaseObject_Type);
2068                 if (bases == NULL)
2069                         return NULL;
2070                 nbases = 1;
2071         }
2072         else
2073                 Py_INCREF(bases);
2074
2075         /* XXX From here until type is allocated, "return NULL" leaks bases! */
2076
2077         /* Calculate best base, and check that all bases are type objects */
2078         base = best_base(bases);
2079         if (base == NULL) {
2080                 Py_DECREF(bases);
2081                 return NULL;
2082         }
2083         if (!PyType_HasFeature(base, Py_TPFLAGS_BASETYPE)) {
2084                 PyErr_Format(PyExc_TypeError,
2085                              "type '%.100s' is not an acceptable base type",
2086                              base->tp_name);
2087                 Py_DECREF(bases);
2088                 return NULL;
2089         }
2090
2091         /* Check for a __slots__ sequence variable in dict, and count it */
2092         slots = PyDict_GetItemString(dict, "__slots__");
2093         nslots = 0;
2094         add_dict = 0;
2095         add_weak = 0;
2096         may_add_dict = base->tp_dictoffset == 0;
2097         may_add_weak = base->tp_weaklistoffset == 0 && base->tp_itemsize == 0;
2098         if (slots == NULL) {
2099                 if (may_add_dict) {
2100                         add_dict++;
2101                 }
2102                 if (may_add_weak) {
2103                         add_weak++;
2104                 }
2105         }
2106         else {
2107                 /* Have slots */
2108
2109                 /* Make it into a tuple */
2110                 if (PyString_Check(slots) || PyUnicode_Check(slots))
2111                         slots = PyTuple_Pack(1, slots);
2112                 else
2113                         slots = PySequence_Tuple(slots);
2114                 if (slots == NULL) {
2115                         Py_DECREF(bases);
2116                         return NULL;
2117                 }
2118                 assert(PyTuple_Check(slots));
2119
2120                 /* Are slots allowed? */
2121                 nslots = PyTuple_GET_SIZE(slots);
2122                 if (nslots > 0 && base->tp_itemsize != 0) {
2123                         PyErr_Format(PyExc_TypeError,
2124                                      "nonempty __slots__ "
2125                                      "not supported for subtype of '%s'",
2126                                      base->tp_name);
2127                   bad_slots:
2128                         Py_DECREF(bases);
2129                         Py_DECREF(slots);
2130                         return NULL;
2131                 }
2132
2133 #ifdef Py_USING_UNICODE
2134                 tmp = _unicode_to_string(slots, nslots);
2135                 if (tmp == NULL)
2136                         goto bad_slots;
2137                 if (tmp != slots) {
2138                         Py_DECREF(slots);
2139                         slots = tmp;
2140                 }
2141 #endif
2142                 /* Check for valid slot names and two special cases */
2143                 for (i = 0; i < nslots; i++) {
2144                         PyObject *tmp = PyTuple_GET_ITEM(slots, i);
2145                         char *s;
2146                         if (!valid_identifier(tmp))
2147                                 goto bad_slots;
2148                         assert(PyString_Check(tmp));
2149                         s = PyString_AS_STRING(tmp);
2150                         if (strcmp(s, "__dict__") == 0) {
2151                                 if (!may_add_dict || add_dict) {
2152                                         PyErr_SetString(PyExc_TypeError,
2153                                                 "__dict__ slot disallowed: "
2154                                                 "we already got one");
2155                                         goto bad_slots;
2156                                 }
2157                                 add_dict++;
2158                         }
2159                         if (strcmp(s, "__weakref__") == 0) {
2160                                 if (!may_add_weak || add_weak) {
2161                                         PyErr_SetString(PyExc_TypeError,
2162                                                 "__weakref__ slot disallowed: "
2163                                                 "either we already got one, "
2164                                                 "or __itemsize__ != 0");
2165                                         goto bad_slots;
2166                                 }
2167                                 add_weak++;
2168                         }
2169                 }
2170
2171                 /* Copy slots into a list, mangle names and sort them.
2172                    Sorted names are needed for __class__ assignment.
2173                    Convert them back to tuple at the end.
2174                 */
2175                 newslots = PyList_New(nslots - add_dict - add_weak);
2176                 if (newslots == NULL)
2177                         goto bad_slots;
2178                 for (i = j = 0; i < nslots; i++) {
2179                         char *s;
2180                         tmp = PyTuple_GET_ITEM(slots, i);
2181                         s = PyString_AS_STRING(tmp);
2182                         if ((add_dict && strcmp(s, "__dict__") == 0) ||
2183                             (add_weak && strcmp(s, "__weakref__") == 0))
2184                                 continue;
2185                         tmp =_Py_Mangle(name, tmp);
2186                         if (!tmp)
2187                             goto bad_slots;
2188                         PyList_SET_ITEM(newslots, j, tmp);
2189                         j++;
2190                 }
2191                 assert(j == nslots - add_dict - add_weak);
2192                 nslots = j;
2193                 Py_DECREF(slots);
2194                 if (PyList_Sort(newslots) == -1) {
2195                         Py_DECREF(bases);
2196                         Py_DECREF(newslots);
2197                         return NULL;
2198                 }
2199                 slots = PyList_AsTuple(newslots);
2200                 Py_DECREF(newslots);
2201                 if (slots == NULL) {
2202                         Py_DECREF(bases);
2203                         return NULL;
2204                 }
2205
2206                 /* Secondary bases may provide weakrefs or dict */
2207                 if (nbases > 1 &&
2208                     ((may_add_dict && !add_dict) ||
2209                      (may_add_weak && !add_weak))) {
2210                         for (i = 0; i < nbases; i++) {
2211                                 tmp = PyTuple_GET_ITEM(bases, i);
2212                                 if (tmp == (PyObject *)base)
2213                                         continue; /* Skip primary base */
2214                                 if (PyClass_Check(tmp)) {
2215                                         /* Classic base class provides both */
2216                                         if (may_add_dict && !add_dict)
2217                                                 add_dict++;
2218                                         if (may_add_weak && !add_weak)
2219                                                 add_weak++;
2220                                         break;
2221                                 }
2222                                 assert(PyType_Check(tmp));
2223                                 tmptype = (PyTypeObject *)tmp;
2224                                 if (may_add_dict && !add_dict &&
2225                                     tmptype->tp_dictoffset != 0)
2226                                         add_dict++;
2227                                 if (may_add_weak && !add_weak &&
2228                                     tmptype->tp_weaklistoffset != 0)
2229                                         add_weak++;
2230                                 if (may_add_dict && !add_dict)
2231                                         continue;
2232                                 if (may_add_weak && !add_weak)
2233                                         continue;
2234                                 /* Nothing more to check */
2235                                 break;
2236                         }
2237                 }
2238         }
2239
2240         /* XXX From here until type is safely allocated,
2241            "return NULL" may leak slots! */
2242
2243         /* Allocate the type object */
2244         type = (PyTypeObject *)metatype->tp_alloc(metatype, nslots);
2245         if (type == NULL) {
2246                 Py_XDECREF(slots);
2247                 Py_DECREF(bases);
2248                 return NULL;
2249         }
2250
2251         /* Keep name and slots alive in the extended type object */
2252         et = (PyHeapTypeObject *)type;
2253         Py_INCREF(name);
2254         et->ht_name = name;
2255         et->ht_slots = slots;
2256
2257         /* Initialize tp_flags */
2258         type->tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HEAPTYPE |
2259                 Py_TPFLAGS_BASETYPE;
2260         if (base->tp_flags & Py_TPFLAGS_HAVE_GC)
2261                 type->tp_flags |= Py_TPFLAGS_HAVE_GC;
2262
2263         /* It's a new-style number unless it specifically inherits any
2264            old-style numeric behavior */
2265         if ((base->tp_flags & Py_TPFLAGS_CHECKTYPES) ||
2266             (base->tp_as_number == NULL))
2267                 type->tp_flags |= Py_TPFLAGS_CHECKTYPES;
2268
2269         /* Initialize essential fields */
2270         type->tp_as_number = &et->as_number;
2271         type->tp_as_sequence = &et->as_sequence;
2272         type->tp_as_mapping = &et->as_mapping;
2273         type->tp_as_buffer = &et->as_buffer;
2274         type->tp_name = PyString_AS_STRING(name);
2275
2276         /* Set tp_base and tp_bases */
2277         type->tp_bases = bases;
2278         Py_INCREF(base);
2279         type->tp_base = base;
2280
2281         /* Initialize tp_dict from passed-in dict */
2282         type->tp_dict = dict = PyDict_Copy(dict);
2283         if (dict == NULL) {
2284                 Py_DECREF(type);
2285                 return NULL;
2286         }
2287
2288         /* Set __module__ in the dict */
2289         if (PyDict_GetItemString(dict, "__module__") == NULL) {
2290                 tmp = PyEval_GetGlobals();
2291                 if (tmp != NULL) {
2292                         tmp = PyDict_GetItemString(tmp, "__name__");
2293                         if (tmp != NULL) {
2294                                 if (PyDict_SetItemString(dict, "__module__",
2295                                                          tmp) < 0)
2296                                         return NULL;
2297                         }
2298                 }
2299         }
2300
2301         /* Set tp_doc to a copy of dict['__doc__'], if the latter is there
2302            and is a string.  The __doc__ accessor will first look for tp_doc;
2303            if that fails, it will still look into __dict__.
2304         */
2305         {
2306                 PyObject *doc = PyDict_GetItemString(dict, "__doc__");
2307                 if (doc != NULL && PyString_Check(doc)) {
2308                         const size_t n = (size_t)PyString_GET_SIZE(doc);
2309                         char *tp_doc = (char *)PyObject_MALLOC(n+1);
2310                         if (tp_doc == NULL) {
2311                                 Py_DECREF(type);
2312                                 return NULL;
2313                         }
2314                         memcpy(tp_doc, PyString_AS_STRING(doc), n+1);
2315                         type->tp_doc = tp_doc;
2316                 }
2317         }
2318
2319         /* Special-case __new__: if it's a plain function,
2320            make it a static function */
2321         tmp = PyDict_GetItemString(dict, "__new__");
2322         if (tmp != NULL && PyFunction_Check(tmp)) {
2323                 tmp = PyStaticMethod_New(tmp);
2324                 if (tmp == NULL) {
2325                         Py_DECREF(type);
2326                         return NULL;
2327                 }
2328                 PyDict_SetItemString(dict, "__new__", tmp);
2329                 Py_DECREF(tmp);
2330         }
2331
2332         /* Add descriptors for custom slots from __slots__, or for __dict__ */
2333         mp = PyHeapType_GET_MEMBERS(et);
2334         slotoffset = base->tp_basicsize;
2335         if (slots != NULL) {
2336                 for (i = 0; i < nslots; i++, mp++) {
2337                         mp->name = PyString_AS_STRING(
2338                                 PyTuple_GET_ITEM(slots, i));
2339                         mp->type = T_OBJECT_EX;
2340                         mp->offset = slotoffset;
2341
2342                         /* __dict__ and __weakref__ are already filtered out */
2343                         assert(strcmp(mp->name, "__dict__") != 0);
2344                         assert(strcmp(mp->name, "__weakref__") != 0);
2345
2346                         slotoffset += sizeof(PyObject *);
2347                 }
2348         }
2349         if (add_dict) {
2350                 if (base->tp_itemsize)
2351                         type->tp_dictoffset = -(long)sizeof(PyObject *);
2352                 else
2353                         type->tp_dictoffset = slotoffset;
2354                 slotoffset += sizeof(PyObject *);
2355         }
2356         if (add_weak) {
2357                 assert(!base->tp_itemsize);
2358                 type->tp_weaklistoffset = slotoffset;
2359                 slotoffset += sizeof(PyObject *);
2360         }
2361         type->tp_basicsize = slotoffset;
2362         type->tp_itemsize = base->tp_itemsize;
2363         type->tp_members = PyHeapType_GET_MEMBERS(et);
2364
2365         if (type->tp_weaklistoffset && type->tp_dictoffset)
2366                 type->tp_getset = subtype_getsets_full;
2367         else if (type->tp_weaklistoffset && !type->tp_dictoffset)
2368                 type->tp_getset = subtype_getsets_weakref_only;
2369         else if (!type->tp_weaklistoffset && type->tp_dictoffset)
2370                 type->tp_getset = subtype_getsets_dict_only;
2371         else
2372                 type->tp_getset = NULL;
2373
2374         /* Special case some slots */
2375         if (type->tp_dictoffset != 0 || nslots > 0) {
2376                 if (base->tp_getattr == NULL && base->tp_getattro == NULL)
2377                         type->tp_getattro = PyObject_GenericGetAttr;
2378                 if (base->tp_setattr == NULL && base->tp_setattro == NULL)
2379                         type->tp_setattro = PyObject_GenericSetAttr;
2380         }
2381         type->tp_dealloc = subtype_dealloc;
2382
2383         /* Enable GC unless there are really no instance variables possible */
2384         if (!(type->tp_basicsize == sizeof(PyObject) &&
2385               type->tp_itemsize == 0))
2386                 type->tp_flags |= Py_TPFLAGS_HAVE_GC;
2387
2388         /* Always override allocation strategy to use regular heap */
2389         type->tp_alloc = PyType_GenericAlloc;
2390         if (type->tp_flags & Py_TPFLAGS_HAVE_GC) {
2391                 type->tp_free = PyObject_GC_Del;
2392                 type->tp_traverse = subtype_traverse;
2393                 type->tp_clear = subtype_clear;
2394         }
2395         else
2396                 type->tp_free = PyObject_Del;
2397
2398         /* Initialize the rest */
2399         if (PyType_Ready(type) < 0) {
2400                 Py_DECREF(type);
2401                 return NULL;
2402         }
2403
2404         /* Put the proper slots in place */
2405         fixup_slot_dispatchers(type);
2406
2407         return (PyObject *)type;
2408 }
2409
2410 /* Internal API to look for a name through the MRO.
2411    This returns a borrowed reference, and doesn't set an exception! */
2412 PyObject *
2413 _PyType_Lookup(PyTypeObject *type, PyObject *name)
2414 {
2415         Py_ssize_t i, n;
2416         PyObject *mro, *res, *base, *dict;
2417         unsigned int h;
2418
2419         if (MCACHE_CACHEABLE_NAME(name) &&
2420             PyType_HasFeature(type, Py_TPFLAGS_VALID_VERSION_TAG)) {
2421                 /* fast path */
2422                 h = MCACHE_HASH_METHOD(type, name);
2423                 if (method_cache[h].version == type->tp_version_tag &&
2424                     method_cache[h].name == name)
2425                     return method_cache[h].value;
2426         }
2427
2428         /* Look in tp_dict of types in MRO */
2429         mro = type->tp_mro;
2430
2431         /* If mro is NULL, the type is either not yet initialized
2432            by PyType_Ready(), or already cleared by type_clear().
2433            Either way the safest thing to do is to return NULL. */
2434         if (mro == NULL)
2435                 return NULL;
2436
2437         res = NULL;
2438         assert(PyTuple_Check(mro));
2439         n = PyTuple_GET_SIZE(mro);
2440         for (i = 0; i < n; i++) {
2441                 base = PyTuple_GET_ITEM(mro, i);
2442                 if (PyClass_Check(base))
2443                         dict = ((PyClassObject *)base)->cl_dict;
2444                 else {
2445                         assert(PyType_Check(base));
2446                         dict = ((PyTypeObject *)base)->tp_dict;
2447                 }
2448                 assert(dict && PyDict_Check(dict));
2449                 res = PyDict_GetItem(dict, name);
2450                 if (res != NULL)
2451                         break;
2452         }
2453
2454         if (MCACHE_CACHEABLE_NAME(name) && assign_version_tag(type)) {
2455                 h = MCACHE_HASH_METHOD(type, name);
2456                 method_cache[h].version = type->tp_version_tag;
2457                 method_cache[h].value = res;  /* borrowed */
2458                 Py_INCREF(name);
2459                 Py_DECREF(method_cache[h].name);
2460                 method_cache[h].name = name;
2461         }
2462         return res;
2463 }
2464
2465 /* This is similar to PyObject_GenericGetAttr(),
2466    but uses _PyType_Lookup() instead of just looking in type->tp_dict. */
2467 static PyObject *
2468 type_getattro(PyTypeObject *type, PyObject *name)
2469 {
2470         PyTypeObject *metatype = Py_TYPE(type);
2471         PyObject *meta_attribute, *attribute;
2472         descrgetfunc meta_get;
2473
2474         /* Initialize this type (we'll assume the metatype is initialized) */
2475         if (type->tp_dict == NULL) {
2476                 if (PyType_Ready(type) < 0)
2477                         return NULL;
2478         }
2479
2480         /* No readable descriptor found yet */
2481         meta_get = NULL;
2482
2483         /* Look for the attribute in the metatype */
2484         meta_attribute = _PyType_Lookup(metatype, name);
2485
2486         if (meta_attribute != NULL) {
2487                 meta_get = Py_TYPE(meta_attribute)->tp_descr_get;
2488
2489                 if (meta_get != NULL && PyDescr_IsData(meta_attribute)) {
2490                         /* Data descriptors implement tp_descr_set to intercept
2491                          * writes. Assume the attribute is not overridden in
2492                          * type's tp_dict (and bases): call the descriptor now.
2493                          */
2494                         return meta_get(meta_attribute, (PyObject *)type,
2495                                         (PyObject *)metatype);
2496                 }
2497                 Py_INCREF(meta_attribute);
2498         }
2499
2500         /* No data descriptor found on metatype. Look in tp_dict of this
2501          * type and its bases */
2502         attribute = _PyType_Lookup(type, name);
2503         if (attribute != NULL) {
2504                 /* Implement descriptor functionality, if any */
2505                 descrgetfunc local_get = Py_TYPE(attribute)->tp_descr_get;
2506
2507                 Py_XDECREF(meta_attribute);
2508
2509                 if (local_get != NULL) {
2510                         /* NULL 2nd argument indicates the descriptor was
2511                          * found on the target object itself (or a base)  */
2512                         return local_get(attribute, (PyObject *)NULL,
2513                                          (PyObject *)type);
2514                 }
2515
2516                 Py_INCREF(attribute);
2517                 return attribute;
2518         }
2519
2520         /* No attribute found in local __dict__ (or bases): use the
2521          * descriptor from the metatype, if any */
2522         if (meta_get != NULL) {
2523                 PyObject *res;
2524                 res = meta_get(meta_attribute, (PyObject *)type,
2525                                (PyObject *)metatype);
2526                 Py_DECREF(meta_attribute);
2527                 return res;
2528         }
2529
2530         /* If an ordinary attribute was found on the metatype, return it now */
2531         if (meta_attribute != NULL) {
2532                 return meta_attribute;
2533         }
2534
2535         /* Give up */
2536         PyErr_Format(PyExc_AttributeError,
2537                          "type object '%.50s' has no attribute '%.400s'",
2538                          type->tp_name, PyString_AS_STRING(name));
2539         return NULL;
2540 }
2541
2542 static int
2543 type_setattro(PyTypeObject *type, PyObject *name, PyObject *value)
2544 {
2545         if (!(type->tp_flags & Py_TPFLAGS_HEAPTYPE)) {
2546                 PyErr_Format(
2547                         PyExc_TypeError,
2548                         "can't set attributes of built-in/extension type '%s'",
2549                         type->tp_name);
2550                 return -1;
2551         }
2552         if (PyObject_GenericSetAttr((PyObject *)type, name, value) < 0)
2553                 return -1;
2554         return update_slot(type, name);
2555 }
2556
2557 static void
2558 type_dealloc(PyTypeObject *type)
2559 {
2560         PyHeapTypeObject *et;
2561
2562         /* Assert this is a heap-allocated type object */
2563         assert(type->tp_flags & Py_TPFLAGS_HEAPTYPE);
2564         _PyObject_GC_UNTRACK(type);
2565         PyObject_ClearWeakRefs((PyObject *)type);
2566         et = (PyHeapTypeObject *)type;
2567         Py_XDECREF(type->tp_base);
2568         Py_XDECREF(type->tp_dict);
2569         Py_XDECREF(type->tp_bases);
2570         Py_XDECREF(type->tp_mro);
2571         Py_XDECREF(type->tp_cache);
2572         Py_XDECREF(type->tp_subclasses);
2573         /* A type's tp_doc is heap allocated, unlike the tp_doc slots
2574          * of most other objects.  It's okay to cast it to char *.
2575          */
2576         PyObject_Free((char *)type->tp_doc);
2577         Py_XDECREF(et->ht_name);
2578         Py_XDECREF(et->ht_slots);
2579         Py_TYPE(type)->tp_free((PyObject *)type);
2580 }
2581
2582 static PyObject *
2583 type_subclasses(PyTypeObject *type, PyObject *args_ignored)
2584 {
2585         PyObject *list, *raw, *ref;
2586         Py_ssize_t i, n;
2587
2588         list = PyList_New(0);
2589         if (list == NULL)
2590                 return NULL;
2591         raw = type->tp_subclasses;
2592         if (raw == NULL)
2593                 return list;
2594         assert(PyList_Check(raw));
2595         n = PyList_GET_SIZE(raw);
2596         for (i = 0; i < n; i++) {
2597                 ref = PyList_GET_ITEM(raw, i);
2598                 assert(PyWeakref_CheckRef(ref));
2599                 ref = PyWeakref_GET_OBJECT(ref);
2600                 if (ref != Py_None) {
2601                         if (PyList_Append(list, ref) < 0) {
2602                                 Py_DECREF(list);
2603                                 return NULL;
2604                         }
2605                 }
2606         }
2607         return list;
2608 }
2609
2610 static PyMethodDef type_methods[] = {
2611         {"mro", (PyCFunction)mro_external, METH_NOARGS,
2612          PyDoc_STR("mro() -> list\nreturn a type's method resolution order")},
2613         {"__subclasses__", (PyCFunction)type_subclasses, METH_NOARGS,
2614          PyDoc_STR("__subclasses__() -> list of immediate subclasses")},
2615         {0}
2616 };
2617
2618 PyDoc_STRVAR(type_doc,
2619 "type(object) -> the object's type\n"
2620 "type(name, bases, dict) -> a new type");
2621
2622 static int
2623 type_traverse(PyTypeObject *type, visitproc visit, void *arg)
2624 {
2625         /* Because of type_is_gc(), the collector only calls this
2626            for heaptypes. */
2627         assert(type->tp_flags & Py_TPFLAGS_HEAPTYPE);
2628
2629         Py_VISIT(type->tp_dict);
2630         Py_VISIT(type->tp_cache);
2631         Py_VISIT(type->tp_mro);
2632         Py_VISIT(type->tp_bases);
2633         Py_VISIT(type->tp_base);
2634
2635         /* There's no need to visit type->tp_subclasses or
2636            ((PyHeapTypeObject *)type)->ht_slots, because they can't be involved
2637            in cycles; tp_subclasses is a list of weak references,
2638            and slots is a tuple of strings. */
2639
2640         return 0;
2641 }
2642
2643 static int
2644 type_clear(PyTypeObject *type)
2645 {
2646         /* Because of type_is_gc(), the collector only calls this
2647            for heaptypes. */
2648         assert(type->tp_flags & Py_TPFLAGS_HEAPTYPE);
2649
2650         /* The only field we need to clear is tp_mro, which is part of a
2651            hard cycle (its first element is the class itself) that won't
2652            be broken otherwise (it's a tuple and tuples don't have a
2653            tp_clear handler).  None of the other fields need to be
2654            cleared, and here's why:
2655
2656            tp_dict:
2657                It is a dict, so the collector will call its tp_clear.
2658
2659            tp_cache:
2660                Not used; if it were, it would be a dict.
2661
2662            tp_bases, tp_base:
2663                If these are involved in a cycle, there must be at least
2664                one other, mutable object in the cycle, e.g. a base
2665                class's dict; the cycle will be broken that way.
2666
2667            tp_subclasses:
2668                A list of weak references can't be part of a cycle; and
2669                lists have their own tp_clear.
2670
2671            slots (in PyHeapTypeObject):
2672                A tuple of strings can't be part of a cycle.
2673         */
2674
2675         Py_CLEAR(type->tp_mro);
2676
2677         return 0;
2678 }
2679
2680 static int
2681 type_is_gc(PyTypeObject *type)
2682 {
2683         return type->tp_flags & Py_TPFLAGS_HEAPTYPE;
2684 }
2685
2686 PyTypeObject PyType_Type = {
2687         PyVarObject_HEAD_INIT(&PyType_Type, 0)
2688         "type",                                 /* tp_name */
2689         sizeof(PyHeapTypeObject),               /* tp_basicsize */
2690         sizeof(PyMemberDef),                    /* tp_itemsize */
2691         (destructor)type_dealloc,               /* tp_dealloc */
2692         0,                                      /* tp_print */
2693         0,                                      /* tp_getattr */
2694         0,                                      /* tp_setattr */
2695         type_compare,                           /* tp_compare */
2696         (reprfunc)type_repr,                    /* tp_repr */
2697         0,                                      /* tp_as_number */
2698         0,                                      /* tp_as_sequence */
2699         0,                                      /* tp_as_mapping */
2700         (hashfunc)_Py_HashPointer,              /* tp_hash */
2701         (ternaryfunc)type_call,                 /* tp_call */
2702         0,                                      /* tp_str */
2703         (getattrofunc)type_getattro,            /* tp_getattro */
2704         (setattrofunc)type_setattro,            /* tp_setattro */
2705         0,                                      /* tp_as_buffer */
2706         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2707                 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_TYPE_SUBCLASS, /* tp_flags */
2708         type_doc,                               /* tp_doc */
2709         (traverseproc)type_traverse,            /* tp_traverse */
2710         (inquiry)type_clear,                    /* tp_clear */
2711         type_richcompare,                                       /* tp_richcompare */
2712         offsetof(PyTypeObject, tp_weaklist),    /* tp_weaklistoffset */
2713         0,                                      /* tp_iter */
2714         0,                                      /* tp_iternext */
2715         type_methods,                           /* tp_methods */
2716         type_members,                           /* tp_members */
2717         type_getsets,                           /* tp_getset */
2718         0,                                      /* tp_base */
2719         0,                                      /* tp_dict */
2720         0,                                      /* tp_descr_get */
2721         0,                                      /* tp_descr_set */
2722         offsetof(PyTypeObject, tp_dict),        /* tp_dictoffset */
2723         type_init,                              /* tp_init */
2724         0,                                      /* tp_alloc */
2725         type_new,                               /* tp_new */
2726         PyObject_GC_Del,                        /* tp_free */
2727         (inquiry)type_is_gc,                    /* tp_is_gc */
2728 };
2729
2730
2731 /* The base type of all types (eventually)... except itself. */
2732
2733 /* You may wonder why object.__new__() only complains about arguments
2734    when object.__init__() is not overridden, and vice versa.
2735
2736    Consider the use cases:
2737
2738    1. When neither is overridden, we want to hear complaints about
2739       excess (i.e., any) arguments, since their presence could
2740       indicate there's a bug.
2741
2742    2. When defining an Immutable type, we are likely to override only
2743       __new__(), since __init__() is called too late to initialize an
2744       Immutable object.  Since __new__() defines the signature for the
2745       type, it would be a pain to have to override __init__() just to
2746       stop it from complaining about excess arguments.
2747
2748    3. When defining a Mutable type, we are likely to override only
2749       __init__().  So here the converse reasoning applies: we don't
2750       want to have to override __new__() just to stop it from
2751       complaining.
2752
2753    4. When __init__() is overridden, and the subclass __init__() calls
2754       object.__init__(), the latter should complain about excess
2755       arguments; ditto for __new__().
2756
2757    Use cases 2 and 3 make it unattractive to unconditionally check for
2758    excess arguments.  The best solution that addresses all four use
2759    cases is as follows: __init__() complains about excess arguments
2760    unless __new__() is overridden and __init__() is not overridden
2761    (IOW, if __init__() is overridden or __new__() is not overridden);
2762    symmetrically, __new__() complains about excess arguments unless
2763    __init__() is overridden and __new__() is not overridden
2764    (IOW, if __new__() is overridden or __init__() is not overridden).
2765
2766    However, for backwards compatibility, this breaks too much code.
2767    Therefore, in 2.6, we'll *warn* about excess arguments when both
2768    methods are overridden; for all other cases we'll use the above
2769    rules.
2770
2771 */
2772
2773 /* Forward */
2774 static PyObject *
2775 object_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
2776
2777 static int
2778 excess_args(PyObject *args, PyObject *kwds)
2779 {
2780         return PyTuple_GET_SIZE(args) ||
2781                 (kwds && PyDict_Check(kwds) && PyDict_Size(kwds));
2782 }
2783
2784 static int
2785 object_init(PyObject *self, PyObject *args, PyObject *kwds)
2786 {
2787         int err = 0;
2788         if (excess_args(args, kwds)) {
2789                 PyTypeObject *type = Py_TYPE(self);
2790                 if (type->tp_init != object_init &&
2791                     type->tp_new != object_new)
2792                 {
2793                         err = PyErr_WarnEx(PyExc_DeprecationWarning,
2794                                    "object.__init__() takes no parameters",
2795                                    1);
2796                 }
2797                 else if (type->tp_init != object_init ||
2798                          type->tp_new == object_new)
2799                 {
2800                         PyErr_SetString(PyExc_TypeError,
2801                                 "object.__init__() takes no parameters");
2802                         err = -1;
2803                 }
2804         }
2805         return err;
2806 }
2807
2808 static PyObject *
2809 object_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2810 {
2811         int err = 0;
2812         if (excess_args(args, kwds)) {
2813                 if (type->tp_new != object_new &&
2814                     type->tp_init != object_init)
2815                 {
2816                         err = PyErr_WarnEx(PyExc_DeprecationWarning,
2817                                    "object.__new__() takes no parameters",
2818                                    1);
2819                 }
2820                 else if (type->tp_new != object_new ||
2821                          type->tp_init == object_init)
2822                 {
2823                         PyErr_SetString(PyExc_TypeError,
2824                                 "object.__new__() takes no parameters");
2825                         err = -1;
2826                 }
2827         }
2828         if (err < 0)
2829                 return NULL;
2830
2831         if (type->tp_flags & Py_TPFLAGS_IS_ABSTRACT) {
2832                 static PyObject *comma = NULL;
2833                 PyObject *abstract_methods = NULL;
2834                 PyObject *builtins;
2835                 PyObject *sorted;
2836                 PyObject *sorted_methods = NULL;
2837                 PyObject *joined = NULL;
2838                 const char *joined_str;
2839
2840                 /* Compute ", ".join(sorted(type.__abstractmethods__))
2841                    into joined. */
2842                 abstract_methods = type_abstractmethods(type, NULL);
2843                 if (abstract_methods == NULL)
2844                         goto error;
2845                 builtins = PyEval_GetBuiltins();
2846                 if (builtins == NULL)
2847                         goto error;
2848                 sorted = PyDict_GetItemString(builtins, "sorted");
2849                 if (sorted == NULL)
2850                         goto error;
2851                 sorted_methods = PyObject_CallFunctionObjArgs(sorted,
2852                                                               abstract_methods,
2853                                                               NULL);
2854                 if (sorted_methods == NULL)
2855                         goto error;
2856                 if (comma == NULL) {
2857                         comma = PyString_InternFromString(", ");
2858                         if (comma == NULL)
2859                                 goto error;
2860                 }
2861                 joined = PyObject_CallMethod(comma, "join",
2862                                              "O",  sorted_methods);
2863                 if (joined == NULL)
2864                         goto error;
2865                 joined_str = PyString_AsString(joined);
2866                 if (joined_str == NULL)
2867                         goto error;
2868
2869                 PyErr_Format(PyExc_TypeError,
2870                              "Can't instantiate abstract class %s "
2871                              "with abstract methods %s",
2872                              type->tp_name,
2873                              joined_str);
2874         error:
2875                 Py_XDECREF(joined);
2876                 Py_XDECREF(sorted_methods);
2877                 Py_XDECREF(abstract_methods);
2878                 return NULL;
2879         }
2880         return type->tp_alloc(type, 0);
2881 }
2882
2883 static void
2884 object_dealloc(PyObject *self)
2885 {
2886         Py_TYPE(self)->tp_free(self);
2887 }
2888
2889 static PyObject *
2890 object_repr(PyObject *self)
2891 {
2892         PyTypeObject *type;
2893         PyObject *mod, *name, *rtn;
2894
2895         type = Py_TYPE(self);
2896         mod = type_module(type, NULL);
2897         if (mod == NULL)
2898                 PyErr_Clear();
2899         else if (!PyString_Check(mod)) {
2900                 Py_DECREF(mod);
2901                 mod = NULL;
2902         }
2903         name = type_name(type, NULL);
2904         if (name == NULL)
2905                 return NULL;
2906         if (mod != NULL && strcmp(PyString_AS_STRING(mod), "__builtin__"))
2907                 rtn = PyString_FromFormat("<%s.%s object at %p>",
2908                                           PyString_AS_STRING(mod),
2909                                           PyString_AS_STRING(name),
2910                                           self);
2911         else
2912                 rtn = PyString_FromFormat("<%s object at %p>",
2913                                           type->tp_name, self);
2914         Py_XDECREF(mod);
2915         Py_DECREF(name);
2916         return rtn;
2917 }
2918
2919 static PyObject *
2920 object_str(PyObject *self)
2921 {
2922         unaryfunc f;
2923
2924         f = Py_TYPE(self)->tp_repr;
2925         if (f == NULL)
2926                 f = object_repr;
2927         return f(self);
2928 }
2929
2930 static PyObject *
2931 object_get_class(PyObject *self, void *closure)
2932 {
2933         Py_INCREF(Py_TYPE(self));
2934         return (PyObject *)(Py_TYPE(self));
2935 }
2936
2937 static int
2938 equiv_structs(PyTypeObject *a, PyTypeObject *b)
2939 {
2940         return a == b ||
2941                (a != NULL &&
2942                 b != NULL &&
2943                 a->tp_basicsize == b->tp_basicsize &&
2944                 a->tp_itemsize == b->tp_itemsize &&
2945                 a->tp_dictoffset == b->tp_dictoffset &&
2946                 a->tp_weaklistoffset == b->tp_weaklistoffset &&
2947                 ((a->tp_flags & Py_TPFLAGS_HAVE_GC) ==
2948                  (b->tp_flags & Py_TPFLAGS_HAVE_GC)));
2949 }
2950
2951 static int
2952 same_slots_added(PyTypeObject *a, PyTypeObject *b)
2953 {
2954         PyTypeObject *base = a->tp_base;
2955         Py_ssize_t size;
2956         PyObject *slots_a, *slots_b;
2957
2958         if (base != b->tp_base)
2959                 return 0;
2960         if (equiv_structs(a, base) && equiv_structs(b, base))
2961                 return 1;
2962         size = base->tp_basicsize;
2963         if (a->tp_dictoffset == size && b->tp_dictoffset == size)
2964                 size += sizeof(PyObject *);
2965         if (a->tp_weaklistoffset == size && b->tp_weaklistoffset == size)
2966                 size += sizeof(PyObject *);
2967
2968         /* Check slots compliance */
2969         slots_a = ((PyHeapTypeObject *)a)->ht_slots;
2970         slots_b = ((PyHeapTypeObject *)b)->ht_slots;
2971         if (slots_a && slots_b) {
2972                 if (PyObject_Compare(slots_a, slots_b) != 0)
2973                         return 0;
2974                 size += sizeof(PyObject *) * PyTuple_GET_SIZE(slots_a);
2975         }
2976         return size == a->tp_basicsize && size == b->tp_basicsize;
2977 }
2978
2979 static int
2980 compatible_for_assignment(PyTypeObject* oldto, PyTypeObject* newto, char* attr)
2981 {
2982         PyTypeObject *newbase, *oldbase;
2983
2984         if (newto->tp_dealloc != oldto->tp_dealloc ||
2985             newto->tp_free != oldto->tp_free)
2986         {
2987                 PyErr_Format(PyExc_TypeError,
2988                              "%s assignment: "
2989                              "'%s' deallocator differs from '%s'",
2990                              attr,
2991                              newto->tp_name,
2992                              oldto->tp_name);
2993                 return 0;
2994         }
2995         newbase = newto;
2996         oldbase = oldto;
2997         while (equiv_structs(newbase, newbase->tp_base))
2998                 newbase = newbase->tp_base;
2999         while (equiv_structs(oldbase, oldbase->tp_base))
3000                 oldbase = oldbase->tp_base;
3001         if (newbase != oldbase &&
3002             (newbase->tp_base != oldbase->tp_base ||
3003              !same_slots_added(newbase, oldbase))) {
3004                 PyErr_Format(PyExc_TypeError,
3005                              "%s assignment: "
3006                              "'%s' object layout differs from '%s'",
3007                              attr,
3008                              newto->tp_name,
3009                              oldto->tp_name);
3010                 return 0;
3011         }
3012
3013         return 1;
3014 }
3015
3016 static int
3017 object_set_class(PyObject *self, PyObject *value, void *closure)
3018 {
3019         PyTypeObject *oldto = Py_TYPE(self);
3020         PyTypeObject *newto;
3021
3022         if (value == NULL) {
3023                 PyErr_SetString(PyExc_TypeError,
3024                                 "can't delete __class__ attribute");
3025                 return -1;
3026         }
3027         if (!PyType_Check(value)) {
3028                 PyErr_Format(PyExc_TypeError,
3029                   "__class__ must be set to new-style class, not '%s' object",
3030                   Py_TYPE(value)->tp_name);
3031                 return -1;
3032         }
3033         newto = (PyTypeObject *)value;
3034         if (!(newto->tp_flags & Py_TPFLAGS_HEAPTYPE) ||
3035             !(oldto->tp_flags & Py_TPFLAGS_HEAPTYPE))
3036         {
3037                 PyErr_Format(PyExc_TypeError,
3038                              "__class__ assignment: only for heap types");
3039                 return -1;
3040         }
3041         if (compatible_for_assignment(newto, oldto, "__class__")) {
3042                 Py_INCREF(newto);
3043                 Py_TYPE(self) = newto;
3044                 Py_DECREF(oldto);
3045                 return 0;
3046         }
3047         else {
3048                 return -1;
3049         }
3050 }
3051
3052 static PyGetSetDef object_getsets[] = {
3053         {"__class__", object_get_class, object_set_class,
3054          PyDoc_STR("the object's class")},
3055         {0}
3056 };
3057
3058
3059 /* Stuff to implement __reduce_ex__ for pickle protocols >= 2.
3060    We fall back to helpers in copy_reg for:
3061    - pickle protocols < 2
3062    - calculating the list of slot names (done only once per class)
3063    - the __newobj__ function (which is used as a token but never called)
3064 */
3065
3066 static PyObject *
3067 import_copyreg(void)
3068 {
3069         static PyObject *copyreg_str;
3070
3071         if (!copyreg_str) {
3072                 copyreg_str = PyString_InternFromString("copy_reg");
3073                 if (copyreg_str == NULL)
3074                         return NULL;
3075         }
3076
3077         return PyImport_Import(copyreg_str);
3078 }
3079
3080 static PyObject *
3081 slotnames(PyObject *cls)
3082 {
3083         PyObject *clsdict;
3084         PyObject *copyreg;
3085         PyObject *slotnames;
3086
3087         if (!PyType_Check(cls)) {
3088                 Py_INCREF(Py_None);
3089                 return Py_None;
3090         }
3091
3092         clsdict = ((PyTypeObject *)cls)->tp_dict;
3093         slotnames = PyDict_GetItemString(clsdict, "__slotnames__");
3094         if (slotnames != NULL && PyList_Check(slotnames)) {
3095                 Py_INCREF(slotnames);
3096                 return slotnames;
3097         }
3098
3099         copyreg = import_copyreg();
3100         if (copyreg == NULL)
3101                 return NULL;
3102
3103         slotnames = PyObject_CallMethod(copyreg, "_slotnames", "O", cls);
3104         Py_DECREF(copyreg);
3105         if (slotnames != NULL &&
3106             slotnames != Py_None &&
3107             !PyList_Check(slotnames))
3108         {
3109                 PyErr_SetString(PyExc_TypeError,
3110                         "copy_reg._slotnames didn't return a list or None");
3111                 Py_DECREF(slotnames);
3112                 slotnames = NULL;
3113         }
3114
3115         return slotnames;
3116 }
3117
3118 static PyObject *
3119 reduce_2(PyObject *obj)
3120 {
3121         PyObject *cls, *getnewargs;
3122         PyObject *args = NULL, *args2 = NULL;
3123         PyObject *getstate = NULL, *state = NULL, *names = NULL;
3124         PyObject *slots = NULL, *listitems = NULL, *dictitems = NULL;
3125         PyObject *copyreg = NULL, *newobj = NULL, *res = NULL;
3126         Py_ssize_t i, n;
3127
3128         cls = PyObject_GetAttrString(obj, "__class__");
3129         if (cls == NULL)
3130                 return NULL;
3131
3132         getnewargs = PyObject_GetAttrString(obj, "__getnewargs__");
3133         if (getnewargs != NULL) {
3134                 args = PyObject_CallObject(getnewargs, NULL);
3135                 Py_DECREF(getnewargs);
3136                 if (args != NULL && !PyTuple_Check(args)) {
3137                         PyErr_Format(PyExc_TypeError,
3138                                 "__getnewargs__ should return a tuple, "
3139                                 "not '%.200s'", Py_TYPE(args)->tp_name);
3140                         goto end;
3141                 }
3142         }
3143         else {
3144                 PyErr_Clear();
3145                 args = PyTuple_New(0);
3146         }
3147         if (args == NULL)
3148                 goto end;
3149
3150         getstate = PyObject_GetAttrString(obj, "__getstate__");
3151         if (getstate != NULL) {
3152                 state = PyObject_CallObject(getstate, NULL);
3153                 Py_DECREF(getstate);
3154                 if (state == NULL)
3155                         goto end;
3156         }
3157         else {
3158                 PyErr_Clear();
3159                 state = PyObject_GetAttrString(obj, "__dict__");
3160                 if (state == NULL) {
3161                         PyErr_Clear();
3162                         state = Py_None;
3163                         Py_INCREF(state);
3164                 }
3165                 names = slotnames(cls);
3166                 if (names == NULL)
3167                         goto end;
3168                 if (names != Py_None) {
3169                         assert(PyList_Check(names));
3170                         slots = PyDict_New();
3171                         if (slots == NULL)
3172                                 goto end;
3173                         n = 0;
3174                         /* Can't pre-compute the list size; the list
3175                            is stored on the class so accessible to other
3176                            threads, which may be run by DECREF */
3177                         for (i = 0; i < PyList_GET_SIZE(names); i++) {
3178                                 PyObject *name, *value;
3179                                 name = PyList_GET_ITEM(names, i);
3180                                 value = PyObject_GetAttr(obj, name);
3181                                 if (value == NULL)
3182                                         PyErr_Clear();
3183                                 else {
3184                                         int err = PyDict_SetItem(slots, name,
3185                                                                  value);
3186                                         Py_DECREF(value);
3187                                         if (err)
3188                                                 goto end;
3189                                         n++;
3190                                 }
3191                         }
3192                         if (n) {
3193                                 state = Py_BuildValue("(NO)", state, slots);
3194                                 if (state == NULL)
3195                                         goto end;
3196                         }
3197                 }
3198         }
3199
3200         if (!PyList_Check(obj)) {
3201                 listitems = Py_None;
3202                 Py_INCREF(listitems);
3203         }
3204         else {
3205                 listitems = PyObject_GetIter(obj);
3206                 if (listitems == NULL)
3207                         goto end;
3208         }
3209
3210         if (!PyDict_Check(obj)) {
3211                 dictitems = Py_None;
3212                 Py_INCREF(dictitems);
3213         }
3214         else {
3215                 dictitems = PyObject_CallMethod(obj, "iteritems", "");
3216                 if (dictitems == NULL)
3217                         goto end;
3218         }
3219
3220         copyreg = import_copyreg();
3221         if (copyreg == NULL)
3222                 goto end;
3223         newobj = PyObject_GetAttrString(copyreg, "__newobj__");
3224         if (newobj == NULL)
3225                 goto end;
3226
3227         n = PyTuple_GET_SIZE(args);
3228         args2 = PyTuple_New(n+1);
3229         if (args2 == NULL)
3230                 goto end;
3231         PyTuple_SET_ITEM(args2, 0, cls);
3232         cls = NULL;
3233         for (i = 0; i < n; i++) {
3234                 PyObject *v = PyTuple_GET_ITEM(args, i);
3235                 Py_INCREF(v);
3236                 PyTuple_SET_ITEM(args2, i+1, v);
3237         }
3238
3239         res = PyTuple_Pack(5, newobj, args2, state, listitems, dictitems);
3240
3241   end:
3242         Py_XDECREF(cls);
3243         Py_XDECREF(args);
3244         Py_XDECREF(args2);
3245         Py_XDECREF(slots);
3246         Py_XDECREF(state);
3247         Py_XDECREF(names);
3248         Py_XDECREF(listitems);
3249         Py_XDECREF(dictitems);
3250         Py_XDECREF(copyreg);
3251         Py_XDECREF(newobj);
3252         return res;
3253 }
3254
3255 /*
3256  * There were two problems when object.__reduce__ and object.__reduce_ex__
3257  * were implemented in the same function:
3258  *  - trying to pickle an object with a custom __reduce__ method that
3259  *    fell back to object.__reduce__ in certain circumstances led to
3260  *    infinite recursion at Python level and eventual RuntimeError.
3261  *  - Pickling objects that lied about their type by overwriting the
3262  *    __class__ descriptor could lead to infinite recursion at C level
3263  *    and eventual segfault.
3264  *
3265  * Because of backwards compatibility, the two methods still have to
3266  * behave in the same way, even if this is not required by the pickle
3267  * protocol. This common functionality was moved to the _common_reduce
3268  * function.
3269  */
3270 static PyObject *
3271 _common_reduce(PyObject *self, int proto)
3272 {
3273         PyObject *copyreg, *res;
3274
3275         if (proto >= 2)
3276                 return reduce_2(self);
3277
3278         copyreg = import_copyreg();
3279         if (!copyreg)
3280                 return NULL;
3281
3282         res = PyEval_CallMethod(copyreg, "_reduce_ex", "(Oi)", self, proto);
3283         Py_DECREF(copyreg);
3284
3285         return res;
3286 }
3287
3288 static PyObject *
3289 object_reduce(PyObject *self, PyObject *args)
3290 {
3291         int proto = 0;
3292
3293         if (!PyArg_ParseTuple(args, "|i:__reduce__", &proto))
3294                 return NULL;
3295
3296         return _common_reduce(self, proto);
3297 }
3298
3299 static PyObject *
3300 object_reduce_ex(PyObject *self, PyObject *args)
3301 {
3302         PyObject *reduce, *res;
3303         int proto = 0;
3304
3305         if (!PyArg_ParseTuple(args, "|i:__reduce_ex__", &proto))
3306                 return NULL;
3307
3308         reduce = PyObject_GetAttrString(self, "__reduce__");
3309         if (reduce == NULL)
3310                 PyErr_Clear();
3311         else {
3312                 PyObject *cls, *clsreduce, *objreduce;
3313                 int override;
3314                 cls = PyObject_GetAttrString(self, "__class__");
3315                 if (cls == NULL) {
3316                         Py_DECREF(reduce);
3317                         return NULL;
3318                 }
3319                 clsreduce = PyObject_GetAttrString(cls, "__reduce__");
3320                 Py_DECREF(cls);
3321                 if (clsreduce == NULL) {
3322                         Py_DECREF(reduce);
3323                         return NULL;
3324                 }
3325                 objreduce = PyDict_GetItemString(PyBaseObject_Type.tp_dict,
3326                                                  "__reduce__");
3327                 override = (clsreduce != objreduce);
3328                 Py_DECREF(clsreduce);
3329                 if (override) {
3330                         res = PyObject_CallObject(reduce, NULL);
3331                         Py_DECREF(reduce);
3332                         return res;
3333                 }
3334                 else
3335                         Py_DECREF(reduce);
3336         }
3337
3338         return _common_reduce(self, proto);
3339 }
3340
3341 static PyObject *
3342 object_subclasshook(PyObject *cls, PyObject *args)
3343 {
3344         Py_INCREF(Py_NotImplemented);
3345         return Py_NotImplemented;
3346 }
3347
3348 PyDoc_STRVAR(object_subclasshook_doc,
3349 "Abstract classes can override this to customize issubclass().\n"
3350 "\n"
3351 "This is invoked early on by abc.ABCMeta.__subclasscheck__().\n"
3352 "It should return True, False or NotImplemented.  If it returns\n"
3353 "NotImplemented, the normal algorithm is used.  Otherwise, it\n"
3354 "overrides the normal algorithm (and the outcome is cached).\n");
3355
3356 /*
3357    from PEP 3101, this code implements:
3358
3359    class object:
3360        def __format__(self, format_spec):
3361            if isinstance(format_spec, str):
3362                return format(str(self), format_spec)
3363            elif isinstance(format_spec, unicode):
3364                return format(unicode(self), format_spec)
3365 */
3366 static PyObject *
3367 object_format(PyObject *self, PyObject *args)
3368 {
3369         PyObject *format_spec;
3370         PyObject *self_as_str = NULL;
3371         PyObject *result = NULL;
3372         PyObject *format_meth = NULL;
3373
3374         if (!PyArg_ParseTuple(args, "O:__format__", &format_spec))
3375                 return NULL;
3376         if (PyUnicode_Check(format_spec)) {
3377                 self_as_str = PyObject_Unicode(self);
3378         } else if (PyString_Check(format_spec)) {
3379                 self_as_str = PyObject_Str(self);
3380         } else {
3381                 PyErr_SetString(PyExc_TypeError, "argument to __format__ must be unicode or str");
3382                 return NULL;
3383         }
3384
3385         if (self_as_str != NULL) {
3386                 /* find the format function */
3387                 format_meth = PyObject_GetAttrString(self_as_str, "__format__");
3388                 if (format_meth != NULL) {
3389                        /* and call it */
3390                         result = PyObject_CallFunctionObjArgs(format_meth, format_spec, NULL);
3391                 }
3392         }
3393
3394         Py_XDECREF(self_as_str);
3395         Py_XDECREF(format_meth);
3396
3397         return result;
3398 }
3399
3400 static PyObject *
3401 object_sizeof(PyObject *self, PyObject *args)
3402 {
3403         Py_ssize_t res, isize;
3404
3405         res = 0;
3406         isize = self->ob_type->tp_itemsize;
3407         if (isize > 0)
3408                 res = self->ob_type->ob_size * isize;
3409         res += self->ob_type->tp_basicsize;
3410
3411         return PyInt_FromSsize_t(res);
3412 }
3413
3414 static PyMethodDef object_methods[] = {
3415         {"__reduce_ex__", object_reduce_ex, METH_VARARGS,
3416          PyDoc_STR("helper for pickle")},
3417         {"__reduce__", object_reduce, METH_VARARGS,
3418          PyDoc_STR("helper for pickle")},
3419         {"__subclasshook__", object_subclasshook, METH_CLASS | METH_VARARGS,
3420          object_subclasshook_doc},
3421         {"__format__", object_format, METH_VARARGS,
3422          PyDoc_STR("default object formatter")},
3423         {"__sizeof__", object_sizeof, METH_NOARGS,
3424          PyDoc_STR("__sizeof__() -> size of object in memory, in bytes")},
3425         {0}
3426 };
3427
3428
3429 PyTypeObject PyBaseObject_Type = {
3430         PyVarObject_HEAD_INIT(&PyType_Type, 0)
3431         "object",                               /* tp_name */
3432         sizeof(PyObject),                       /* tp_basicsize */
3433         0,                                      /* tp_itemsize */
3434         object_dealloc,                         /* tp_dealloc */
3435         0,                                      /* tp_print */
3436         0,                                      /* tp_getattr */
3437         0,                                      /* tp_setattr */
3438         0,                                      /* tp_compare */
3439         object_repr,                            /* tp_repr */
3440         0,                                      /* tp_as_number */
3441         0,                                      /* tp_as_sequence */
3442         0,                                      /* tp_as_mapping */
3443         (hashfunc)_Py_HashPointer,              /* tp_hash */
3444         0,                                      /* tp_call */
3445         object_str,                             /* tp_str */
3446         PyObject_GenericGetAttr,                /* tp_getattro */
3447         PyObject_GenericSetAttr,                /* tp_setattro */
3448         0,                                      /* tp_as_buffer */
3449         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /* tp_flags */
3450         PyDoc_STR("The most base type"),        /* tp_doc */
3451         0,                                      /* tp_traverse */
3452         0,                                      /* tp_clear */
3453         0,                                      /* tp_richcompare */
3454         0,                                      /* tp_weaklistoffset */
3455         0,                                      /* tp_iter */
3456         0,                                      /* tp_iternext */
3457         object_methods,                         /* tp_methods */
3458         0,                                      /* tp_members */
3459         object_getsets,                         /* tp_getset */
3460         0,                                      /* tp_base */
3461         0,                                      /* tp_dict */
3462         0,                                      /* tp_descr_get */
3463         0,                                      /* tp_descr_set */
3464         0,                                      /* tp_dictoffset */
3465         object_init,                            /* tp_init */
3466         PyType_GenericAlloc,                    /* tp_alloc */
3467         object_new,                             /* tp_new */
3468         PyObject_Del,                           /* tp_free */
3469 };
3470
3471
3472 /* Initialize the __dict__ in a type object */
3473
3474 static int
3475 add_methods(PyTypeObject *type, PyMethodDef *meth)
3476 {
3477         PyObject *dict = type->tp_dict;
3478
3479         for (; meth->ml_name != NULL; meth++) {
3480                 PyObject *descr;
3481                 if (PyDict_GetItemString(dict, meth->ml_name) &&
3482                         !(meth->ml_flags & METH_COEXIST))
3483                                 continue;
3484                 if (meth->ml_flags & METH_CLASS) {
3485                         if (meth->ml_flags & METH_STATIC) {
3486                                 PyErr_SetString(PyExc_ValueError,
3487                                      "method cannot be both class and static");
3488                                 return -1;
3489                         }
3490                         descr = PyDescr_NewClassMethod(type, meth);
3491                 }
3492                 else if (meth->ml_flags & METH_STATIC) {
3493                         PyObject *cfunc = PyCFunction_New(meth, NULL);
3494                         if (cfunc == NULL)
3495                                 return -1;
3496                         descr = PyStaticMethod_New(cfunc);
3497                         Py_DECREF(cfunc);
3498                 }
3499                 else {
3500                         descr = PyDescr_NewMethod(type, meth);
3501                 }
3502                 if (descr == NULL)
3503                         return -1;
3504                 if (PyDict_SetItemString(dict, meth->ml_name, descr) < 0)
3505                         return -1;
3506                 Py_DECREF(descr);
3507         }
3508         return 0;
3509 }
3510
3511 static int
3512 add_members(PyTypeObject *type, PyMemberDef *memb)
3513 {
3514         PyObject *dict = type->tp_dict;
3515
3516         for (; memb->name != NULL; memb++) {
3517                 PyObject *descr;
3518                 if (PyDict_GetItemString(dict, memb->name))
3519                         continue;
3520                 descr = PyDescr_NewMember(type, memb);
3521                 if (descr == NULL)
3522                         return -1;
3523                 if (PyDict_SetItemString(dict, memb->name, descr) < 0)
3524                         return -1;
3525                 Py_DECREF(descr);
3526         }
3527         return 0;
3528 }
3529
3530 static int
3531 add_getset(PyTypeObject *type, PyGetSetDef *gsp)
3532 {
3533         PyObject *dict = type->tp_dict;
3534
3535         for (; gsp->name != NULL; gsp++) {
3536                 PyObject *descr;
3537                 if (PyDict_GetItemString(dict, gsp->name))
3538                         continue;
3539                 descr = PyDescr_NewGetSet(type, gsp);
3540
3541                 if (descr == NULL)
3542                         return -1;
3543                 if (PyDict_SetItemString(dict, gsp->name, descr) < 0)
3544                         return -1;
3545                 Py_DECREF(descr);
3546         }
3547         return 0;
3548 }
3549
3550 static void
3551 inherit_special(PyTypeObject *type, PyTypeObject *base)
3552 {
3553         Py_ssize_t oldsize, newsize;
3554
3555         /* Special flag magic */
3556         if (!type->tp_as_buffer && base->tp_as_buffer) {
3557                 type->tp_flags &= ~Py_TPFLAGS_HAVE_GETCHARBUFFER;
3558                 type->tp_flags |=
3559                         base->tp_flags & Py_TPFLAGS_HAVE_GETCHARBUFFER;
3560         }
3561         if (!type->tp_as_sequence && base->tp_as_sequence) {
3562                 type->tp_flags &= ~Py_TPFLAGS_HAVE_SEQUENCE_IN;
3563                 type->tp_flags |= base->tp_flags & Py_TPFLAGS_HAVE_SEQUENCE_IN;
3564         }
3565         if ((type->tp_flags & Py_TPFLAGS_HAVE_INPLACEOPS) !=
3566             (base->tp_flags & Py_TPFLAGS_HAVE_INPLACEOPS)) {
3567                 if ((!type->tp_as_number && base->tp_as_number) ||
3568                     (!type->tp_as_sequence && base->tp_as_sequence)) {
3569                         type->tp_flags &= ~Py_TPFLAGS_HAVE_INPLACEOPS;
3570                         if (!type->tp_as_number && !type->tp_as_sequence) {
3571                                 type->tp_flags |= base->tp_flags &
3572                                         Py_TPFLAGS_HAVE_INPLACEOPS;
3573                         }
3574                 }
3575                 /* Wow */
3576         }
3577         if (!type->tp_as_number && base->tp_as_number) {
3578                 type->tp_flags &= ~Py_TPFLAGS_CHECKTYPES;
3579                 type->tp_flags |= base->tp_flags & Py_TPFLAGS_CHECKTYPES;
3580         }
3581
3582         /* Copying basicsize is connected to the GC flags */
3583         oldsize = base->tp_basicsize;
3584         newsize = type->tp_basicsize ? type->tp_basicsize : oldsize;
3585         if (!(type->tp_flags & Py_TPFLAGS_HAVE_GC) &&
3586             (base->tp_flags & Py_TPFLAGS_HAVE_GC) &&
3587             (type->tp_flags & Py_TPFLAGS_HAVE_RICHCOMPARE/*GC slots exist*/) &&
3588             (!type->tp_traverse && !type->tp_clear)) {
3589                 type->tp_flags |= Py_TPFLAGS_HAVE_GC;
3590                 if (type->tp_traverse == NULL)
3591                         type->tp_traverse = base->tp_traverse;
3592                 if (type->tp_clear == NULL)
3593                         type->tp_clear = base->tp_clear;
3594         }
3595         if (type->tp_flags & base->tp_flags & Py_TPFLAGS_HAVE_CLASS) {
3596                 /* The condition below could use some explanation.
3597                    It appears that tp_new is not inherited for static types
3598                    whose base class is 'object'; this seems to be a precaution
3599                    so that old extension types don't suddenly become
3600                    callable (object.__new__ wouldn't insure the invariants
3601                    that the extension type's own factory function ensures).
3602                    Heap types, of course, are under our control, so they do
3603                    inherit tp_new; static extension types that specify some
3604                    other built-in type as the default are considered
3605                    new-style-aware so they also inherit object.__new__. */
3606                 if (base != &PyBaseObject_Type ||
3607                     (type->tp_flags & Py_TPFLAGS_HEAPTYPE)) {
3608                         if (type->tp_new == NULL)
3609                                 type->tp_new = base->tp_new;
3610                 }
3611         }
3612         type->tp_basicsize = newsize;
3613
3614         /* Copy other non-function slots */
3615
3616 #undef COPYVAL
3617 #define COPYVAL(SLOT) \
3618         if (type->SLOT == 0) type->SLOT = base->SLOT
3619
3620         COPYVAL(tp_itemsize);
3621         if (type->tp_flags & base->tp_flags & Py_TPFLAGS_HAVE_WEAKREFS) {
3622                 COPYVAL(tp_weaklistoffset);
3623         }
3624         if (type->tp_flags & base->tp_flags & Py_TPFLAGS_HAVE_CLASS) {
3625                 COPYVAL(tp_dictoffset);
3626         }
3627
3628         /* Setup fast subclass flags */
3629         if (PyType_IsSubtype(base, (PyTypeObject*)PyExc_BaseException))
3630                 type->tp_flags |= Py_TPFLAGS_BASE_EXC_SUBCLASS;
3631         else if (PyType_IsSubtype(base, &PyType_Type))
3632                 type->tp_flags |= Py_TPFLAGS_TYPE_SUBCLASS;
3633         else if (PyType_IsSubtype(base, &PyInt_Type))
3634                 type->tp_flags |= Py_TPFLAGS_INT_SUBCLASS;
3635         else if (PyType_IsSubtype(base, &PyLong_Type))
3636                 type->tp_flags |= Py_TPFLAGS_LONG_SUBCLASS;
3637         else if (PyType_IsSubtype(base, &PyString_Type))
3638                 type->tp_flags |= Py_TPFLAGS_STRING_SUBCLASS;
3639 #ifdef Py_USING_UNICODE
3640         else if (PyType_IsSubtype(base, &PyUnicode_Type))
3641                 type->tp_flags |= Py_TPFLAGS_UNICODE_SUBCLASS;
3642 #endif
3643         else if (PyType_IsSubtype(base, &PyTuple_Type))
3644                 type->tp_flags |= Py_TPFLAGS_TUPLE_SUBCLASS;
3645         else if (PyType_IsSubtype(base, &PyList_Type))
3646                 type->tp_flags |= Py_TPFLAGS_LIST_SUBCLASS;
3647         else if (PyType_IsSubtype(base, &PyDict_Type))
3648                 type->tp_flags |= Py_TPFLAGS_DICT_SUBCLASS;
3649 }
3650
3651 static void
3652 inherit_slots(PyTypeObject *type, PyTypeObject *base)
3653 {
3654         PyTypeObject *basebase;
3655
3656 #undef SLOTDEFINED
3657 #undef COPYSLOT
3658 #undef COPYNUM
3659 #undef COPYSEQ
3660 #undef COPYMAP
3661 #undef COPYBUF
3662
3663 #define SLOTDEFINED(SLOT) \
3664         (base->SLOT != 0 && \
3665          (basebase == NULL || base->SLOT != basebase->SLOT))
3666
3667 #define COPYSLOT(SLOT) \
3668         if (!type->SLOT && SLOTDEFINED(SLOT)) type->SLOT = base->SLOT
3669
3670 #define COPYNUM(SLOT) COPYSLOT(tp_as_number->SLOT)
3671 #define COPYSEQ(SLOT) COPYSLOT(tp_as_sequence->SLOT)
3672 #define COPYMAP(SLOT) COPYSLOT(tp_as_mapping->SLOT)
3673 #define COPYBUF(SLOT) COPYSLOT(tp_as_buffer->SLOT)
3674
3675         /* This won't inherit indirect slots (from tp_as_number etc.)
3676            if type doesn't provide the space. */
3677
3678         if (type->tp_as_number != NULL && base->tp_as_number != NULL) {
3679                 basebase = base->tp_base;
3680                 if (basebase->tp_as_number == NULL)
3681                         basebase = NULL;
3682                 COPYNUM(nb_add);
3683                 COPYNUM(nb_subtract);
3684                 COPYNUM(nb_multiply);
3685                 COPYNUM(nb_divide);
3686                 COPYNUM(nb_remainder);
3687                 COPYNUM(nb_divmod);
3688                 COPYNUM(nb_power);
3689                 COPYNUM(nb_negative);
3690                 COPYNUM(nb_positive);
3691                 COPYNUM(nb_absolute);
3692                 COPYNUM(nb_nonzero);
3693                 COPYNUM(nb_invert);
3694                 COPYNUM(nb_lshift);
3695                 COPYNUM(nb_rshift);
3696                 COPYNUM(nb_and);
3697                 COPYNUM(nb_xor);
3698                 COPYNUM(nb_or);
3699                 COPYNUM(nb_coerce);
3700                 COPYNUM(nb_int);
3701                 COPYNUM(nb_long);
3702                 COPYNUM(nb_float);
3703                 COPYNUM(nb_oct);
3704                 COPYNUM(nb_hex);
3705                 COPYNUM(nb_inplace_add);
3706                 COPYNUM(nb_inplace_subtract);
3707                 COPYNUM(nb_inplace_multiply);
3708                 COPYNUM(nb_inplace_divide);
3709                 COPYNUM(nb_inplace_remainder);
3710                 COPYNUM(nb_inplace_power);
3711                 COPYNUM(nb_inplace_lshift);
3712                 COPYNUM(nb_inplace_rshift);
3713                 COPYNUM(nb_inplace_and);
3714                 COPYNUM(nb_inplace_xor);
3715                 COPYNUM(nb_inplace_or);
3716                 if (base->tp_flags & Py_TPFLAGS_CHECKTYPES) {
3717                         COPYNUM(nb_true_divide);
3718                         COPYNUM(nb_floor_divide);
3719                         COPYNUM(nb_inplace_true_divide);
3720                         COPYNUM(nb_inplace_floor_divide);
3721                 }
3722                 if (base->tp_flags & Py_TPFLAGS_HAVE_INDEX) {
3723                         COPYNUM(nb_index);
3724                 }
3725         }
3726
3727         if (type->tp_as_sequence != NULL && base->tp_as_sequence != NULL) {
3728                 basebase = base->tp_base;
3729                 if (basebase->tp_as_sequence == NULL)
3730                         basebase = NULL;
3731                 COPYSEQ(sq_length);
3732                 COPYSEQ(sq_concat);
3733                 COPYSEQ(sq_repeat);
3734                 COPYSEQ(sq_item);
3735                 COPYSEQ(sq_slice);
3736                 COPYSEQ(sq_ass_item);
3737                 COPYSEQ(sq_ass_slice);
3738                 COPYSEQ(sq_contains);
3739                 COPYSEQ(sq_inplace_concat);
3740                 COPYSEQ(sq_inplace_repeat);
3741         }
3742
3743         if (type->tp_as_mapping != NULL && base->tp_as_mapping != NULL) {
3744                 basebase = base->tp_base;
3745                 if (basebase->tp_as_mapping == NULL)
3746                         basebase = NULL;
3747                 COPYMAP(mp_length);
3748                 COPYMAP(mp_subscript);
3749                 COPYMAP(mp_ass_subscript);
3750         }
3751
3752         if (type->tp_as_buffer != NULL && base->tp_as_buffer != NULL) {
3753                 basebase = base->tp_base;
3754                 if (basebase->tp_as_buffer == NULL)
3755                         basebase = NULL;
3756                 COPYBUF(bf_getreadbuffer);
3757                 COPYBUF(bf_getwritebuffer);
3758                 COPYBUF(bf_getsegcount);
3759                 COPYBUF(bf_getcharbuffer);
3760                 COPYBUF(bf_getbuffer);
3761                 COPYBUF(bf_releasebuffer);
3762         }
3763
3764         basebase = base->tp_base;
3765
3766         COPYSLOT(tp_dealloc);
3767         COPYSLOT(tp_print);
3768         if (type->tp_getattr == NULL && type->tp_getattro == NULL) {
3769                 type->tp_getattr = base->tp_getattr;
3770                 type->tp_getattro = base->tp_getattro;
3771         }
3772         if (type->tp_setattr == NULL && type->tp_setattro == NULL) {
3773                 type->tp_setattr = base->tp_setattr;
3774                 type->tp_setattro = base->tp_setattro;
3775         }
3776         /* tp_compare see tp_richcompare */
3777         COPYSLOT(tp_repr);
3778         /* tp_hash see tp_richcompare */
3779         COPYSLOT(tp_call);
3780         COPYSLOT(tp_str);
3781         if (type->tp_flags & base->tp_flags & Py_TPFLAGS_HAVE_RICHCOMPARE) {
3782                 if (type->tp_compare == NULL &&
3783                     type->tp_richcompare == NULL &&
3784                     type->tp_hash == NULL)
3785                 {
3786                         type->tp_compare = base->tp_compare;
3787                         type->tp_richcompare = base->tp_richcompare;
3788                         type->tp_hash = base->tp_hash;
3789                 }
3790         }
3791         else {
3792                 COPYSLOT(tp_compare);
3793         }
3794         if (type->tp_flags & base->tp_flags & Py_TPFLAGS_HAVE_ITER) {
3795                 COPYSLOT(tp_iter);
3796                 COPYSLOT(tp_iternext);
3797         }
3798         if (type->tp_flags & base->tp_flags & Py_TPFLAGS_HAVE_CLASS) {
3799                 COPYSLOT(tp_descr_get);
3800                 COPYSLOT(tp_descr_set);
3801                 COPYSLOT(tp_dictoffset);
3802                 COPYSLOT(tp_init);
3803                 COPYSLOT(tp_alloc);
3804                 COPYSLOT(tp_is_gc);
3805                 if ((type->tp_flags & Py_TPFLAGS_HAVE_GC) ==
3806                     (base->tp_flags & Py_TPFLAGS_HAVE_GC)) {
3807                         /* They agree about gc. */
3808                         COPYSLOT(tp_free);
3809                 }
3810                 else if ((type->tp_flags & Py_TPFLAGS_HAVE_GC) &&
3811                          type->tp_free == NULL &&
3812                          base->tp_free == _PyObject_Del) {
3813                         /* A bit of magic to plug in the correct default
3814                          * tp_free function when a derived class adds gc,
3815                          * didn't define tp_free, and the base uses the
3816                          * default non-gc tp_free.
3817                          */
3818                         type->tp_free = PyObject_GC_Del;
3819                 }
3820                 /* else they didn't agree about gc, and there isn't something
3821                  * obvious to be done -- the type is on its own.
3822                  */
3823         }
3824 }
3825
3826 static int add_operators(PyTypeObject *);
3827
3828 int
3829 PyType_Ready(PyTypeObject *type)
3830 {
3831         PyObject *dict, *bases;
3832         PyTypeObject *base;
3833         Py_ssize_t i, n;
3834
3835         if (type->tp_flags & Py_TPFLAGS_READY) {
3836                 assert(type->tp_dict != NULL);
3837                 return 0;
3838         }
3839         assert((type->tp_flags & Py_TPFLAGS_READYING) == 0);
3840
3841         type->tp_flags |= Py_TPFLAGS_READYING;
3842
3843 #ifdef Py_TRACE_REFS
3844         /* PyType_Ready is the closest thing we have to a choke point
3845          * for type objects, so is the best place I can think of to try
3846          * to get type objects into the doubly-linked list of all objects.
3847          * Still, not all type objects go thru PyType_Ready.
3848          */
3849         _Py_AddToAllObjects((PyObject *)type, 0);
3850 #endif
3851
3852         /* Initialize tp_base (defaults to BaseObject unless that's us) */
3853         base = type->tp_base;
3854         if (base == NULL && type != &PyBaseObject_Type) {
3855                 base = type->tp_base = &PyBaseObject_Type;
3856                 Py_INCREF(base);
3857         }
3858
3859         /* Now the only way base can still be NULL is if type is
3860          * &PyBaseObject_Type.
3861          */
3862
3863         /* Initialize the base class */
3864         if (base && base->tp_dict == NULL) {
3865                 if (PyType_Ready(base) < 0)
3866                         goto error;
3867         }
3868
3869         /* Initialize ob_type if NULL.  This means extensions that want to be
3870            compilable separately on Windows can call PyType_Ready() instead of
3871            initializing the ob_type field of their type objects. */
3872         /* The test for base != NULL is really unnecessary, since base is only
3873            NULL when type is &PyBaseObject_Type, and we know its ob_type is
3874            not NULL (it's initialized to &PyType_Type).  But coverity doesn't
3875            know that. */
3876         if (Py_TYPE(type) == NULL && base != NULL)
3877                 Py_TYPE(type) = Py_TYPE(base);
3878
3879         /* Initialize tp_bases */
3880         bases = type->tp_bases;
3881         if (bases == NULL) {
3882                 if (base == NULL)
3883                         bases = PyTuple_New(0);
3884                 else
3885                         bases = PyTuple_Pack(1, base);
3886                 if (bases == NULL)
3887                         goto error;
3888                 type->tp_bases = bases;
3889         }
3890
3891         /* Initialize tp_dict */
3892         dict = type->tp_dict;
3893         if (dict == NULL) {
3894                 dict = PyDict_New();
3895                 if (dict == NULL)
3896                         goto error;
3897                 type->tp_dict = dict;
3898         }
3899
3900         /* Add type-specific descriptors to tp_dict */
3901         if (add_operators(type) < 0)
3902                 goto error;
3903         if (type->tp_methods != NULL) {
3904                 if (add_methods(type, type->tp_methods) < 0)
3905                         goto error;
3906         }
3907         if (type->tp_members != NULL) {
3908                 if (add_members(type, type->tp_members) < 0)
3909                         goto error;
3910         }
3911         if (type->tp_getset != NULL) {
3912                 if (add_getset(type, type->tp_getset) < 0)
3913                         goto error;
3914         }
3915
3916         /* Calculate method resolution order */
3917         if (mro_internal(type) < 0) {
3918                 goto error;
3919         }
3920
3921         /* Inherit special flags from dominant base */
3922         if (type->tp_base != NULL)
3923                 inherit_special(type, type->tp_base);
3924
3925         /* Initialize tp_dict properly */
3926         bases = type->tp_mro;
3927         assert(bases != NULL);
3928         assert(PyTuple_Check(bases));
3929         n = PyTuple_GET_SIZE(bases);
3930         for (i = 1; i < n; i++) {
3931                 PyObject *b = PyTuple_GET_ITEM(bases, i);
3932                 if (PyType_Check(b))
3933                         inherit_slots(type, (PyTypeObject *)b);
3934         }
3935
3936         /* Sanity check for tp_free. */
3937         if (PyType_IS_GC(type) && (type->tp_flags & Py_TPFLAGS_BASETYPE) &&
3938             (type->tp_free == NULL || type->tp_free == PyObject_Del)) {
3939                 /* This base class needs to call tp_free, but doesn't have
3940                  * one, or its tp_free is for non-gc'ed objects.
3941                  */
3942                 PyErr_Format(PyExc_TypeError, "type '%.100s' participates in "
3943                              "gc and is a base type but has inappropriate "
3944                              "tp_free slot",
3945                              type->tp_name);
3946                 goto error;
3947         }
3948
3949         /* if the type dictionary doesn't contain a __doc__, set it from
3950            the tp_doc slot.
3951          */
3952         if (PyDict_GetItemString(type->tp_dict, "__doc__") == NULL) {
3953                 if (type->tp_doc != NULL) {
3954                         PyObject *doc = PyString_FromString(type->tp_doc);
3955                         if (doc == NULL)
3956                                 goto error;
3957                         PyDict_SetItemString(type->tp_dict, "__doc__", doc);
3958                         Py_DECREF(doc);
3959                 } else {
3960                         PyDict_SetItemString(type->tp_dict,
3961                                              "__doc__", Py_None);
3962                 }
3963         }
3964
3965         /* Some more special stuff */
3966         base = type->tp_base;
3967         if (base != NULL) {
3968                 if (type->tp_as_number == NULL)
3969                         type->tp_as_number = base->tp_as_number;
3970                 if (type->tp_as_sequence == NULL)
3971                         type->tp_as_sequence = base->tp_as_sequence;
3972                 if (type->tp_as_mapping == NULL)
3973                         type->tp_as_mapping = base->tp_as_mapping;
3974                 if (type->tp_as_buffer == NULL)
3975                         type->tp_as_buffer = base->tp_as_buffer;
3976         }
3977
3978         /* Link into each base class's list of subclasses */
3979         bases = type->tp_bases;
3980         n = PyTuple_GET_SIZE(bases);
3981         for (i = 0; i < n; i++) {
3982                 PyObject *b = PyTuple_GET_ITEM(bases, i);
3983                 if (PyType_Check(b) &&
3984                     add_subclass((PyTypeObject *)b, type) < 0)
3985                         goto error;
3986         }
3987
3988         /* All done -- set the ready flag */
3989         assert(type->tp_dict != NULL);
3990         type->tp_flags =
3991                 (type->tp_flags & ~Py_TPFLAGS_READYING) | Py_TPFLAGS_READY;
3992         return 0;
3993
3994   error:
3995         type->tp_flags &= ~Py_TPFLAGS_READYING;
3996         return -1;
3997 }
3998
3999 static int
4000 add_subclass(PyTypeObject *base, PyTypeObject *type)
4001 {
4002         Py_ssize_t i;
4003         int result;
4004         PyObject *list, *ref, *newobj;
4005
4006         list = base->tp_subclasses;
4007         if (list == NULL) {
4008                 base->tp_subclasses = list = PyList_New(0);
4009                 if (list == NULL)
4010                         return -1;
4011         }
4012         assert(PyList_Check(list));
4013         newobj = PyWeakref_NewRef((PyObject *)type, NULL);
4014         i = PyList_GET_SIZE(list);
4015         while (--i >= 0) {
4016                 ref = PyList_GET_ITEM(list, i);
4017                 assert(PyWeakref_CheckRef(ref));
4018                 if (PyWeakref_GET_OBJECT(ref) == Py_None)
4019                         return PyList_SetItem(list, i, newobj);
4020         }
4021         result = PyList_Append(list, newobj);
4022         Py_DECREF(newobj);
4023         return result;
4024 }
4025
4026 static void
4027 remove_subclass(PyTypeObject *base, PyTypeObject *type)
4028 {
4029         Py_ssize_t i;
4030         PyObject *list, *ref;
4031
4032         list = base->tp_subclasses;
4033         if (list == NULL) {
4034                 return;
4035         }
4036         assert(PyList_Check(list));
4037         i = PyList_GET_SIZE(list);
4038         while (--i >= 0) {
4039                 ref = PyList_GET_ITEM(list, i);
4040                 assert(PyWeakref_CheckRef(ref));
4041                 if (PyWeakref_GET_OBJECT(ref) == (PyObject*)type) {
4042                         /* this can't fail, right? */
4043                         PySequence_DelItem(list, i);
4044                         return;
4045                 }
4046         }
4047 }
4048
4049 static int
4050 check_num_args(PyObject *ob, int n)
4051 {
4052         if (!PyTuple_CheckExact(ob)) {
4053                 PyErr_SetString(PyExc_SystemError,
4054                     "PyArg_UnpackTuple() argument list is not a tuple");
4055                 return 0;
4056         }
4057         if (n == PyTuple_GET_SIZE(ob))
4058                 return 1;
4059         PyErr_Format(
4060             PyExc_TypeError,
4061             "expected %d arguments, got %zd", n, PyTuple_GET_SIZE(ob));
4062         return 0;
4063 }
4064
4065 /* Generic wrappers for overloadable 'operators' such as __getitem__ */
4066
4067 /* There's a wrapper *function* for each distinct function typedef used
4068    for type object slots (e.g. binaryfunc, ternaryfunc, etc.).  There's a
4069    wrapper *table* for each distinct operation (e.g. __len__, __add__).
4070    Most tables have only one entry; the tables for binary operators have two
4071    entries, one regular and one with reversed arguments. */
4072
4073 static PyObject *
4074 wrap_lenfunc(PyObject *self, PyObject *args, void *wrapped)
4075 {
4076         lenfunc func = (lenfunc)wrapped;
4077         Py_ssize_t res;
4078
4079         if (!check_num_args(args, 0))
4080                 return NULL;
4081         res = (*func)(self);
4082         if (res == -1 && PyErr_Occurred())
4083                 return NULL;
4084         return PyInt_FromLong((long)res);
4085 }
4086
4087 static PyObject *
4088 wrap_inquirypred(PyObject *self, PyObject *args, void *wrapped)
4089 {
4090         inquiry func = (inquiry)wrapped;
4091         int res;
4092
4093         if (!check_num_args(args, 0))
4094                 return NULL;
4095         res = (*func)(self);
4096         if (res == -1 && PyErr_Occurred())
4097                 return NULL;
4098         return PyBool_FromLong((long)res);
4099 }
4100
4101 static PyObject *
4102 wrap_binaryfunc(PyObject *self, PyObject *args, void *wrapped)
4103 {
4104         binaryfunc func = (binaryfunc)wrapped;
4105         PyObject *other;
4106
4107         if (!check_num_args(args, 1))
4108                 return NULL;
4109         other = PyTuple_GET_ITEM(args, 0);
4110         return (*func)(self, other);
4111 }
4112
4113 static PyObject *
4114 wrap_binaryfunc_l(PyObject *self, PyObject *args, void *wrapped)
4115 {
4116         binaryfunc func = (binaryfunc)wrapped;
4117         PyObject *other;
4118
4119         if (!check_num_args(args, 1))
4120                 return NULL;
4121         other = PyTuple_GET_ITEM(args, 0);
4122         if (!(self->ob_type->tp_flags & Py_TPFLAGS_CHECKTYPES) &&
4123             !PyType_IsSubtype(other->ob_type, self->ob_type)) {
4124                 Py_INCREF(Py_NotImplemented);
4125                 return Py_NotImplemented;
4126         }
4127         return (*func)(self, other);
4128 }
4129
4130 static PyObject *
4131 wrap_binaryfunc_r(PyObject *self, PyObject *args, void *wrapped)
4132 {
4133         binaryfunc func = (binaryfunc)wrapped;
4134         PyObject *other;
4135
4136         if (!check_num_args(args, 1))
4137                 return NULL;
4138         other = PyTuple_GET_ITEM(args, 0);
4139         if (!(self->ob_type->tp_flags & Py_TPFLAGS_CHECKTYPES) &&
4140             !PyType_IsSubtype(other->ob_type, self->ob_type)) {
4141                 Py_INCREF(Py_NotImplemented);
4142                 return Py_NotImplemented;
4143         }
4144         return (*func)(other, self);
4145 }
4146
4147 static PyObject *
4148 wrap_coercefunc(PyObject *self, PyObject *args, void *wrapped)
4149 {
4150         coercion func = (coercion)wrapped;
4151         PyObject *other, *res;
4152         int ok;
4153
4154         if (!check_num_args(args, 1))
4155                 return NULL;
4156         other = PyTuple_GET_ITEM(args, 0);
4157         ok = func(&self, &other);
4158         if (ok < 0)
4159                 return NULL;
4160         if (ok > 0) {
4161                 Py_INCREF(Py_NotImplemented);
4162                 return Py_NotImplemented;
4163         }
4164         res = PyTuple_New(2);
4165         if (res == NULL) {
4166                 Py_DECREF(self);
4167                 Py_DECREF(other);
4168                 return NULL;
4169         }
4170         PyTuple_SET_ITEM(res, 0, self);
4171         PyTuple_SET_ITEM(res, 1, other);
4172         return res;
4173 }
4174
4175 static PyObject *
4176 wrap_ternaryfunc(PyObject *self, PyObject *args, void *wrapped)
4177 {
4178         ternaryfunc func = (ternaryfunc)wrapped;
4179         PyObject *other;
4180         PyObject *third = Py_None;
4181
4182         /* Note: This wrapper only works for __pow__() */
4183
4184         if (!PyArg_UnpackTuple(args, "", 1, 2, &other, &third))
4185                 return NULL;
4186         return (*func)(self, other, third);
4187 }
4188
4189 static PyObject *
4190 wrap_ternaryfunc_r(PyObject *self, PyObject *args, void *wrapped)
4191 {
4192         ternaryfunc func = (ternaryfunc)wrapped;
4193         PyObject *other;
4194         PyObject *third = Py_None;
4195
4196         /* Note: This wrapper only works for __pow__() */
4197
4198         if (!PyArg_UnpackTuple(args, "", 1, 2, &other, &third))
4199                 return NULL;
4200         return (*func)(other, self, third);
4201 }
4202
4203 static PyObject *
4204 wrap_unaryfunc(PyObject *self, PyObject *args, void *wrapped)
4205 {
4206         unaryfunc func = (unaryfunc)wrapped;
4207
4208         if (!check_num_args(args, 0))
4209                 return NULL;
4210         return (*func)(self);
4211 }
4212
4213 static PyObject *
4214 wrap_indexargfunc(PyObject *self, PyObject *args, void *wrapped)
4215 {
4216         ssizeargfunc func = (ssizeargfunc)wrapped;
4217         PyObject* o;
4218         Py_ssize_t i;
4219
4220         if (!PyArg_UnpackTuple(args, "", 1, 1, &o))
4221                 return NULL;
4222         i = PyNumber_AsSsize_t(o, PyExc_OverflowError);
4223         if (i == -1 && PyErr_Occurred())
4224                 return NULL;
4225         return (*func)(self, i);
4226 }
4227
4228 static Py_ssize_t
4229 getindex(PyObject *self, PyObject *arg)
4230 {
4231         Py_ssize_t i;
4232
4233         i = PyNumber_AsSsize_t(arg, PyExc_OverflowError);
4234         if (i == -1 && PyErr_Occurred())
4235                 return -1;
4236         if (i < 0) {
4237                 PySequenceMethods *sq = Py_TYPE(self)->tp_as_sequence;
4238                 if (sq && sq->sq_length) {
4239                         Py_ssize_t n = (*sq->sq_length)(self);
4240                         if (n < 0)
4241                                 return -1;
4242                         i += n;
4243                 }
4244         }
4245         return i;
4246 }
4247
4248 static PyObject *
4249 wrap_sq_item(PyObject *self, PyObject *args, void *wrapped)
4250 {
4251         ssizeargfunc func = (ssizeargfunc)wrapped;
4252         PyObject *arg;
4253         Py_ssize_t i;
4254
4255         if (PyTuple_GET_SIZE(args) == 1) {
4256                 arg = PyTuple_GET_ITEM(args, 0);
4257                 i = getindex(self, arg);
4258                 if (i == -1 && PyErr_Occurred())
4259                         return NULL;
4260                 return (*func)(self, i);
4261         }
4262         check_num_args(args, 1);
4263         assert(PyErr_Occurred());
4264         return NULL;
4265 }
4266
4267 static PyObject *
4268 wrap_ssizessizeargfunc(PyObject *self, PyObject *args, void *wrapped)
4269 {
4270         ssizessizeargfunc func = (ssizessizeargfunc)wrapped;
4271         Py_ssize_t i, j;
4272
4273         if (!PyArg_ParseTuple(args, "nn", &i, &j))
4274                 return NULL;
4275         return (*func)(self, i, j);
4276 }
4277
4278 static PyObject *
4279 wrap_sq_setitem(PyObject *self, PyObject *args, void *wrapped)
4280 {
4281         ssizeobjargproc func = (ssizeobjargproc)wrapped;
4282         Py_ssize_t i;
4283         int res;
4284         PyObject *arg, *value;
4285
4286         if (!PyArg_UnpackTuple(args, "", 2, 2, &arg, &value))
4287                 return NULL;
4288         i = getindex(self, arg);
4289         if (i == -1 && PyErr_Occurred())
4290                 return NULL;
4291         res = (*func)(self, i, value);
4292         if (res == -1 && PyErr_Occurred())
4293                 return NULL;
4294         Py_INCREF(Py_None);
4295         return Py_None;
4296 }
4297
4298 static PyObject *
4299 wrap_sq_delitem(PyObject *self, PyObject *args, void *wrapped)
4300 {
4301         ssizeobjargproc func = (ssizeobjargproc)wrapped;
4302         Py_ssize_t i;
4303         int res;
4304         PyObject *arg;
4305
4306         if (!check_num_args(args, 1))
4307                 return NULL;
4308         arg = PyTuple_GET_ITEM(args, 0);
4309         i = getindex(self, arg);
4310         if (i == -1 && PyErr_Occurred())
4311                 return NULL;
4312         res = (*func)(self, i, NULL);
4313         if (res == -1 && PyErr_Occurred())
4314                 return NULL;
4315         Py_INCREF(Py_None);
4316         return Py_None;
4317 }
4318
4319 static PyObject *
4320 wrap_ssizessizeobjargproc(PyObject *self, PyObject *args, void *wrapped)
4321 {
4322         ssizessizeobjargproc func = (ssizessizeobjargproc)wrapped;
4323         Py_ssize_t i, j;
4324         int res;
4325         PyObject *value;
4326
4327         if (!PyArg_ParseTuple(args, "nnO", &i, &j, &value))
4328                 return NULL;
4329         res = (*func)(self, i, j, value);
4330         if (res == -1 && PyErr_Occurred())
4331                 return NULL;
4332         Py_INCREF(Py_None);
4333         return Py_None;
4334 }
4335
4336 static PyObject *
4337 wrap_delslice(PyObject *self, PyObject *args, void *wrapped)
4338 {
4339         ssizessizeobjargproc func = (ssizessizeobjargproc)wrapped;
4340         Py_ssize_t i, j;
4341         int res;
4342
4343         if (!PyArg_ParseTuple(args, "nn", &i, &j))
4344                 return NULL;
4345         res = (*func)(self, i, j, NULL);
4346         if (res == -1 && PyErr_Occurred())
4347                 return NULL;
4348         Py_INCREF(Py_None);
4349         return Py_None;
4350 }
4351
4352 /* XXX objobjproc is a misnomer; should be objargpred */
4353 static PyObject *
4354 wrap_objobjproc(PyObject *self, PyObject *args, void *wrapped)
4355 {
4356         objobjproc func = (objobjproc)wrapped;
4357         int res;
4358         PyObject *value;
4359
4360         if (!check_num_args(args, 1))
4361                 return NULL;
4362         value = PyTuple_GET_ITEM(args, 0);
4363         res = (*func)(self, value);
4364         if (res == -1 && PyErr_Occurred())
4365                 return NULL;
4366         else
4367                 return PyBool_FromLong(res);
4368 }
4369
4370 static PyObject *
4371 wrap_objobjargproc(PyObject *self, PyObject *args, void *wrapped)
4372 {
4373         objobjargproc func = (objobjargproc)wrapped;
4374         int res;
4375         PyObject *key, *value;
4376
4377         if (!PyArg_UnpackTuple(args, "", 2, 2, &key, &value))
4378                 return NULL;
4379         res = (*func)(self, key, value);
4380         if (res == -1 && PyErr_Occurred())
4381                 return NULL;
4382         Py_INCREF(Py_None);
4383         return Py_None;
4384 }
4385
4386 static PyObject *
4387 wrap_delitem(PyObject *self, PyObject *args, void *wrapped)
4388 {
4389         objobjargproc func = (objobjargproc)wrapped;
4390         int res;
4391         PyObject *key;
4392
4393         if (!check_num_args(args, 1))
4394                 return NULL;
4395         key = PyTuple_GET_ITEM(args, 0);
4396         res = (*func)(self, key, NULL);
4397         if (res == -1 && PyErr_Occurred())
4398                 return NULL;
4399         Py_INCREF(Py_None);
4400         return Py_None;
4401 }
4402
4403 static PyObject *
4404 wrap_cmpfunc(PyObject *self, PyObject *args, void *wrapped)
4405 {
4406         cmpfunc func = (cmpfunc)wrapped;
4407         int res;
4408         PyObject *other;
4409
4410         if (!check_num_args(args, 1))
4411                 return NULL;
4412         other = PyTuple_GET_ITEM(args, 0);
4413         if (Py_TYPE(other)->tp_compare != func &&
4414             !PyType_IsSubtype(Py_TYPE(other), Py_TYPE(self))) {
4415                 PyErr_Format(
4416                         PyExc_TypeError,
4417                         "%s.__cmp__(x,y) requires y to be a '%s', not a '%s'",
4418                         Py_TYPE(self)->tp_name,
4419                         Py_TYPE(self)->tp_name,
4420                         Py_TYPE(other)->tp_name);
4421                 return NULL;
4422         }
4423         res = (*func)(self, other);
4424         if (PyErr_Occurred())
4425                 return NULL;
4426         return PyInt_FromLong((long)res);
4427 }
4428
4429 /* Helper to check for object.__setattr__ or __delattr__ applied to a type.
4430    This is called the Carlo Verre hack after its discoverer. */
4431 static int
4432 hackcheck(PyObject *self, setattrofunc func, char *what)
4433 {
4434         PyTypeObject *type = Py_TYPE(self);
4435         while (type && type->tp_flags & Py_TPFLAGS_HEAPTYPE)
4436                 type = type->tp_base;
4437         /* If type is NULL now, this is a really weird type.
4438            In the spirit of backwards compatibility (?), just shut up. */
4439         if (type && type->tp_setattro != func) {
4440                 PyErr_Format(PyExc_TypeError,
4441                              "can't apply this %s to %s object",
4442                              what,
4443                              type->tp_name);
4444                 return 0;
4445         }
4446         return 1;
4447 }
4448
4449 static PyObject *
4450 wrap_setattr(PyObject *self, PyObject *args, void *wrapped)
4451 {
4452         setattrofunc func = (setattrofunc)wrapped;
4453         int res;
4454         PyObject *name, *value;
4455
4456         if (!PyArg_UnpackTuple(args, "", 2, 2, &name, &value))
4457                 return NULL;
4458         if (!hackcheck(self, func, "__setattr__"))
4459                 return NULL;
4460         res = (*func)(self, name, value);
4461         if (res < 0)
4462                 return NULL;
4463         Py_INCREF(Py_None);
4464         return Py_None;
4465 }
4466
4467 static PyObject *
4468 wrap_delattr(PyObject *self, PyObject *args, void *wrapped)
4469 {
4470         setattrofunc func = (setattrofunc)wrapped;
4471         int res;
4472         PyObject *name;
4473
4474         if (!check_num_args(args, 1))
4475                 return NULL;
4476         name = PyTuple_GET_ITEM(args, 0);
4477         if (!hackcheck(self, func, "__delattr__"))
4478                 return NULL;
4479         res = (*func)(self, name, NULL);
4480         if (res < 0)
4481                 return NULL;
4482         Py_INCREF(Py_None);
4483         return Py_None;
4484 }
4485
4486 static PyObject *
4487 wrap_hashfunc(PyObject *self, PyObject *args, void *wrapped)
4488 {
4489         hashfunc func = (hashfunc)wrapped;
4490         long res;
4491
4492         if (!check_num_args(args, 0))
4493                 return NULL;
4494         res = (*func)(self);
4495         if (res == -1 && PyErr_Occurred())
4496                 return NULL;
4497         return PyInt_FromLong(res);
4498 }
4499
4500 static PyObject *
4501 wrap_call(PyObject *self, PyObject *args, void *wrapped, PyObject *kwds)
4502 {
4503         ternaryfunc func = (ternaryfunc)wrapped;
4504
4505         return (*func)(self, args, kwds);
4506 }
4507
4508 static PyObject *
4509 wrap_richcmpfunc(PyObject *self, PyObject *args, void *wrapped, int op)
4510 {
4511         richcmpfunc func = (richcmpfunc)wrapped;
4512         PyObject *other;
4513
4514         if (!check_num_args(args, 1))
4515                 return NULL;
4516         other = PyTuple_GET_ITEM(args, 0);
4517         return (*func)(self, other, op);
4518 }
4519
4520 #undef RICHCMP_WRAPPER
4521 #define RICHCMP_WRAPPER(NAME, OP) \
4522 static PyObject * \
4523 richcmp_##NAME(PyObject *self, PyObject *args, void *wrapped) \
4524 { \
4525         return wrap_richcmpfunc(self, args, wrapped, OP); \
4526 }
4527
4528 RICHCMP_WRAPPER(lt, Py_LT)
4529 RICHCMP_WRAPPER(le, Py_LE)
4530 RICHCMP_WRAPPER(eq, Py_EQ)
4531 RICHCMP_WRAPPER(ne, Py_NE)
4532 RICHCMP_WRAPPER(gt, Py_GT)
4533 RICHCMP_WRAPPER(ge, Py_GE)
4534
4535 static PyObject *
4536 wrap_next(PyObject *self, PyObject *args, void *wrapped)
4537 {
4538         unaryfunc func = (unaryfunc)wrapped;
4539         PyObject *res;
4540
4541         if (!check_num_args(args, 0))
4542                 return NULL;
4543         res = (*func)(self);
4544         if (res == NULL && !PyErr_Occurred())
4545                 PyErr_SetNone(PyExc_StopIteration);
4546         return res;
4547 }
4548
4549 static PyObject *
4550 wrap_descr_get(PyObject *self, PyObject *args, void *wrapped)
4551 {
4552         descrgetfunc func = (descrgetfunc)wrapped;
4553         PyObject *obj;
4554         PyObject *type = NULL;
4555
4556         if (!PyArg_UnpackTuple(args, "", 1, 2, &obj, &type))
4557                 return NULL;
4558         if (obj == Py_None)
4559                 obj = NULL;
4560         if (type == Py_None)
4561                 type = NULL;
4562         if (type == NULL &&obj == NULL) {
4563                 PyErr_SetString(PyExc_TypeError,
4564                                 "__get__(None, None) is invalid");
4565                 return NULL;
4566         }
4567         return (*func)(self, obj, type);
4568 }
4569
4570 static PyObject *
4571 wrap_descr_set(PyObject *self, PyObject *args, void *wrapped)
4572 {
4573         descrsetfunc func = (descrsetfunc)wrapped;
4574         PyObject *obj, *value;
4575         int ret;
4576
4577         if (!PyArg_UnpackTuple(args, "", 2, 2, &obj, &value))
4578                 return NULL;
4579         ret = (*func)(self, obj, value);
4580         if (ret < 0)
4581                 return NULL;
4582         Py_INCREF(Py_None);
4583         return Py_None;
4584 }
4585
4586 static PyObject *
4587 wrap_descr_delete(PyObject *self, PyObject *args, void *wrapped)
4588 {
4589         descrsetfunc func = (descrsetfunc)wrapped;
4590         PyObject *obj;
4591         int ret;
4592
4593         if (!check_num_args(args, 1))
4594                 return NULL;
4595         obj = PyTuple_GET_ITEM(args, 0);
4596         ret = (*func)(self, obj, NULL);
4597         if (ret < 0)
4598                 return NULL;
4599         Py_INCREF(Py_None);
4600         return Py_None;
4601 }
4602
4603 static PyObject *
4604 wrap_init(PyObject *self, PyObject *args, void *wrapped, PyObject *kwds)
4605 {
4606         initproc func = (initproc)wrapped;
4607
4608         if (func(self, args, kwds) < 0)
4609                 return NULL;
4610         Py_INCREF(Py_None);
4611         return Py_None;
4612 }
4613
4614 static PyObject *
4615 tp_new_wrapper(PyObject *self, PyObject *args, PyObject *kwds)
4616 {
4617         PyTypeObject *type, *subtype, *staticbase;
4618         PyObject *arg0, *res;
4619
4620         if (self == NULL || !PyType_Check(self))
4621                 Py_FatalError("__new__() called with non-type 'self'");
4622         type = (PyTypeObject *)self;
4623         if (!PyTuple_Check(args) || PyTuple_GET_SIZE(args) < 1) {
4624                 PyErr_Format(PyExc_TypeError,
4625                              "%s.__new__(): not enough arguments",
4626                              type->tp_name);
4627                 return NULL;
4628         }
4629         arg0 = PyTuple_GET_ITEM(args, 0);
4630         if (!PyType_Check(arg0)) {
4631                 PyErr_Format(PyExc_TypeError,
4632                              "%s.__new__(X): X is not a type object (%s)",
4633                              type->tp_name,
4634                              Py_TYPE(arg0)->tp_name);
4635                 return NULL;
4636         }
4637         subtype = (PyTypeObject *)arg0;
4638         if (!PyType_IsSubtype(subtype, type)) {
4639                 PyErr_Format(PyExc_TypeError,
4640                              "%s.__new__(%s): %s is not a subtype of %s",
4641                              type->tp_name,
4642                              subtype->tp_name,
4643                              subtype->tp_name,
4644                              type->tp_name);
4645                 return NULL;
4646         }
4647
4648         /* Check that the use doesn't do something silly and unsafe like
4649            object.__new__(dict).  To do this, we check that the
4650            most derived base that's not a heap type is this type. */
4651         staticbase = subtype;
4652         while (staticbase && (staticbase->tp_flags & Py_TPFLAGS_HEAPTYPE))
4653                 staticbase = staticbase->tp_base;
4654         /* If staticbase is NULL now, it is a really weird type.
4655            In the spirit of backwards compatibility (?), just shut up. */
4656         if (staticbase && staticbase->tp_new != type->tp_new) {
4657                 PyErr_Format(PyExc_TypeError,
4658                              "%s.__new__(%s) is not safe, use %s.__new__()",
4659                              type->tp_name,
4660                              subtype->tp_name,
4661                              staticbase == NULL ? "?" : staticbase->tp_name);
4662                 return NULL;
4663         }
4664
4665         args = PyTuple_GetSlice(args, 1, PyTuple_GET_SIZE(args));
4666         if (args == NULL)
4667                 return NULL;
4668         res = type->tp_new(subtype, args, kwds);
4669         Py_DECREF(args);
4670         return res;
4671 }
4672
4673 static struct PyMethodDef tp_new_methoddef[] = {
4674         {"__new__", (PyCFunction)tp_new_wrapper, METH_VARARGS|METH_KEYWORDS,
4675          PyDoc_STR("T.__new__(S, ...) -> "
4676                    "a new object with type S, a subtype of T")},
4677         {0}
4678 };
4679
4680 static int
4681 add_tp_new_wrapper(PyTypeObject *type)
4682 {
4683         PyObject *func;
4684
4685         if (PyDict_GetItemString(type->tp_dict, "__new__") != NULL)
4686                 return 0;
4687         func = PyCFunction_New(tp_new_methoddef, (PyObject *)type);
4688         if (func == NULL)
4689                 return -1;
4690         if (PyDict_SetItemString(type->tp_dict, "__new__", func)) {
4691                 Py_DECREF(func);
4692                 return -1;
4693         }
4694         Py_DECREF(func);
4695         return 0;
4696 }
4697
4698 /* Slot wrappers that call the corresponding __foo__ slot.  See comments
4699    below at override_slots() for more explanation. */
4700
4701 #define SLOT0(FUNCNAME, OPSTR) \
4702 static PyObject * \
4703 FUNCNAME(PyObject *self) \
4704 { \
4705         static PyObject *cache_str; \
4706         return call_method(self, OPSTR, &cache_str, "()"); \
4707 }
4708
4709 #define SLOT1(FUNCNAME, OPSTR, ARG1TYPE, ARGCODES) \
4710 static PyObject * \
4711 FUNCNAME(PyObject *self, ARG1TYPE arg1) \
4712 { \
4713         static PyObject *cache_str; \
4714         return call_method(self, OPSTR, &cache_str, "(" ARGCODES ")", arg1); \
4715 }
4716
4717 /* Boolean helper for SLOT1BINFULL().
4718    right.__class__ is a nontrivial subclass of left.__class__. */
4719 static int
4720 method_is_overloaded(PyObject *left, PyObject *right, char *name)
4721 {
4722         PyObject *a, *b;
4723         int ok;
4724
4725         b = PyObject_GetAttrString((PyObject *)(Py_TYPE(right)), name);
4726         if (b == NULL) {
4727                 PyErr_Clear();
4728                 /* If right doesn't have it, it's not overloaded */
4729                 return 0;
4730         }
4731
4732         a = PyObject_GetAttrString((PyObject *)(Py_TYPE(left)), name);
4733         if (a == NULL) {
4734                 PyErr_Clear();
4735                 Py_DECREF(b);
4736                 /* If right has it but left doesn't, it's overloaded */
4737                 return 1;
4738         }
4739
4740         ok = PyObject_RichCompareBool(a, b, Py_NE);
4741         Py_DECREF(a);
4742         Py_DECREF(b);
4743         if (ok < 0) {
4744                 PyErr_Clear();
4745                 return 0;
4746         }
4747
4748         return ok;
4749 }
4750
4751
4752 #define SLOT1BINFULL(FUNCNAME, TESTFUNC, SLOTNAME, OPSTR, ROPSTR) \
4753 static PyObject * \
4754 FUNCNAME(PyObject *self, PyObject *other) \
4755 { \
4756         static PyObject *cache_str, *rcache_str; \
4757         int do_other = Py_TYPE(self) != Py_TYPE(other) && \
4758             Py_TYPE(other)->tp_as_number != NULL && \
4759             Py_TYPE(other)->tp_as_number->SLOTNAME == TESTFUNC; \
4760         if (Py_TYPE(self)->tp_as_number != NULL && \
4761             Py_TYPE(self)->tp_as_number->SLOTNAME == TESTFUNC) { \
4762                 PyObject *r; \
4763                 if (do_other && \
4764                     PyType_IsSubtype(Py_TYPE(other), Py_TYPE(self)) && \
4765                     method_is_overloaded(self, other, ROPSTR)) { \
4766                         r = call_maybe( \
4767                                 other, ROPSTR, &rcache_str, "(O)", self); \
4768                         if (r != Py_NotImplemented) \
4769                                 return r; \
4770                         Py_DECREF(r); \
4771                         do_other = 0; \
4772                 } \
4773                 r = call_maybe( \
4774                         self, OPSTR, &cache_str, "(O)", other); \
4775                 if (r != Py_NotImplemented || \
4776                     Py_TYPE(other) == Py_TYPE(self)) \
4777                         return r; \
4778                 Py_DECREF(r); \
4779         } \
4780         if (do_other) { \
4781                 return call_maybe( \
4782                         other, ROPSTR, &rcache_str, "(O)", self); \
4783         } \
4784         Py_INCREF(Py_NotImplemented); \
4785         return Py_NotImplemented; \
4786 }
4787
4788 #define SLOT1BIN(FUNCNAME, SLOTNAME, OPSTR, ROPSTR) \
4789         SLOT1BINFULL(FUNCNAME, FUNCNAME, SLOTNAME, OPSTR, ROPSTR)
4790
4791 #define SLOT2(FUNCNAME, OPSTR, ARG1TYPE, ARG2TYPE, ARGCODES) \
4792 static PyObject * \
4793 FUNCNAME(PyObject *self, ARG1TYPE arg1, ARG2TYPE arg2) \
4794 { \
4795         static PyObject *cache_str; \
4796         return call_method(self, OPSTR, &cache_str, \
4797                            "(" ARGCODES ")", arg1, arg2); \
4798 }
4799
4800 static Py_ssize_t
4801 slot_sq_length(PyObject *self)
4802 {
4803         static PyObject *len_str;
4804         PyObject *res = call_method(self, "__len__", &len_str, "()");
4805         Py_ssize_t len;
4806
4807         if (res == NULL)
4808                 return -1;
4809         len = PyInt_AsSsize_t(res);
4810         Py_DECREF(res);
4811         if (len < 0) {
4812                 if (!PyErr_Occurred())
4813                         PyErr_SetString(PyExc_ValueError,
4814                                         "__len__() should return >= 0");
4815                 return -1;
4816         }
4817         return len;
4818 }
4819
4820 /* Super-optimized version of slot_sq_item.
4821    Other slots could do the same... */
4822 static PyObject *
4823 slot_sq_item(PyObject *self, Py_ssize_t i)
4824 {
4825         static PyObject *getitem_str;
4826         PyObject *func, *args = NULL, *ival = NULL, *retval = NULL;
4827         descrgetfunc f;
4828
4829         if (getitem_str == NULL) {
4830                 getitem_str = PyString_InternFromString("__getitem__");
4831                 if (getitem_str == NULL)
4832                         return NULL;
4833         }
4834         func = _PyType_Lookup(Py_TYPE(self), getitem_str);
4835         if (func != NULL) {
4836                 if ((f = Py_TYPE(func)->tp_descr_get) == NULL)
4837                         Py_INCREF(func);
4838                 else {
4839                         func = f(func, self, (PyObject *)(Py_TYPE(self)));
4840                         if (func == NULL) {
4841                                 return NULL;
4842                         }
4843                 }
4844                 ival = PyInt_FromSsize_t(i);
4845                 if (ival != NULL) {
4846                         args = PyTuple_New(1);
4847                         if (args != NULL) {
4848                                 PyTuple_SET_ITEM(args, 0, ival);
4849                                 retval = PyObject_Call(func, args, NULL);
4850                                 Py_XDECREF(args);
4851                                 Py_XDECREF(func);
4852                                 return retval;
4853                         }
4854                 }
4855         }
4856         else {
4857                 PyErr_SetObject(PyExc_AttributeError, getitem_str);
4858         }
4859         Py_XDECREF(args);
4860         Py_XDECREF(ival);
4861         Py_XDECREF(func);
4862         return NULL;
4863 }
4864
4865 SLOT2(slot_sq_slice, "__getslice__", Py_ssize_t, Py_ssize_t, "nn")
4866
4867 static int
4868 slot_sq_ass_item(PyObject *self, Py_ssize_t index, PyObject *value)
4869 {
4870         PyObject *res;
4871         static PyObject *delitem_str, *setitem_str;
4872
4873         if (value == NULL)
4874                 res = call_method(self, "__delitem__", &delitem_str,
4875                                   "(n)", index);
4876         else
4877                 res = call_method(self, "__setitem__", &setitem_str,
4878                                   "(nO)", index, value);
4879         if (res == NULL)
4880                 return -1;
4881         Py_DECREF(res);
4882         return 0;
4883 }
4884
4885 static int
4886 slot_sq_ass_slice(PyObject *self, Py_ssize_t i, Py_ssize_t j, PyObject *value)
4887 {
4888         PyObject *res;
4889         static PyObject *delslice_str, *setslice_str;
4890
4891         if (value == NULL)
4892                 res = call_method(self, "__delslice__", &delslice_str,
4893                                   "(nn)", i, j);
4894         else
4895                 res = call_method(self, "__setslice__", &setslice_str,
4896                                   "(nnO)", i, j, value);
4897         if (res == NULL)
4898                 return -1;
4899         Py_DECREF(res);
4900         return 0;
4901 }
4902
4903 static int
4904 slot_sq_contains(PyObject *self, PyObject *value)
4905 {
4906         PyObject *func, *res, *args;
4907         int result = -1;
4908
4909         static PyObject *contains_str;
4910
4911         func = lookup_maybe(self, "__contains__", &contains_str);
4912         if (func != NULL) {
4913                 args = PyTuple_Pack(1, value);
4914                 if (args == NULL)
4915                         res = NULL;
4916                 else {
4917                         res = PyObject_Call(func, args, NULL);
4918                         Py_DECREF(args);
4919                 }
4920                 Py_DECREF(func);
4921                 if (res != NULL) {
4922                         result = PyObject_IsTrue(res);
4923                         Py_DECREF(res);
4924                 }
4925         }
4926         else if (! PyErr_Occurred()) {
4927                 /* Possible results: -1 and 1 */
4928                 result = (int)_PySequence_IterSearch(self, value,
4929                                                  PY_ITERSEARCH_CONTAINS);
4930         }
4931         return result;
4932 }
4933
4934 #define slot_mp_length slot_sq_length
4935
4936 SLOT1(slot_mp_subscript, "__getitem__", PyObject *, "O")
4937
4938 static int
4939 slot_mp_ass_subscript(PyObject *self, PyObject *key, PyObject *value)
4940 {
4941         PyObject *res;
4942         static PyObject *delitem_str, *setitem_str;
4943
4944         if (value == NULL)
4945                 res = call_method(self, "__delitem__", &delitem_str,
4946                                   "(O)", key);
4947         else
4948                 res = call_method(self, "__setitem__", &setitem_str,
4949                                  "(OO)", key, value);
4950         if (res == NULL)
4951                 return -1;
4952         Py_DECREF(res);
4953         return 0;
4954 }
4955
4956 SLOT1BIN(slot_nb_add, nb_add, "__add__", "__radd__")
4957 SLOT1BIN(slot_nb_subtract, nb_subtract, "__sub__", "__rsub__")
4958 SLOT1BIN(slot_nb_multiply, nb_multiply, "__mul__", "__rmul__")
4959 SLOT1BIN(slot_nb_divide, nb_divide, "__div__", "__rdiv__")
4960 SLOT1BIN(slot_nb_remainder, nb_remainder, "__mod__", "__rmod__")
4961 SLOT1BIN(slot_nb_divmod, nb_divmod, "__divmod__", "__rdivmod__")
4962
4963 static PyObject *slot_nb_power(PyObject *, PyObject *, PyObject *);
4964
4965 SLOT1BINFULL(slot_nb_power_binary, slot_nb_power,
4966              nb_power, "__pow__", "__rpow__")
4967
4968 static PyObject *
4969 slot_nb_power(PyObject *self, PyObject *other, PyObject *modulus)
4970 {
4971         static PyObject *pow_str;
4972
4973         if (modulus == Py_None)
4974                 return slot_nb_power_binary(self, other);
4975         /* Three-arg power doesn't use __rpow__.  But ternary_op
4976            can call this when the second argument's type uses
4977            slot_nb_power, so check before calling self.__pow__. */
4978         if (Py_TYPE(self)->tp_as_number != NULL &&
4979             Py_TYPE(self)->tp_as_number->nb_power == slot_nb_power) {
4980                 return call_method(self, "__pow__", &pow_str,
4981                                    "(OO)", other, modulus);
4982         }
4983         Py_INCREF(Py_NotImplemented);
4984         return Py_NotImplemented;
4985 }
4986
4987 SLOT0(slot_nb_negative, "__neg__")
4988 SLOT0(slot_nb_positive, "__pos__")
4989 SLOT0(slot_nb_absolute, "__abs__")
4990
4991 static int
4992 slot_nb_nonzero(PyObject *self)
4993 {
4994         PyObject *func, *args;
4995         static PyObject *nonzero_str, *len_str;
4996         int result = -1;
4997
4998         func = lookup_maybe(self, "__nonzero__", &nonzero_str);
4999         if (func == NULL) {
5000                 if (PyErr_Occurred())
5001                         return -1;
5002                 func = lookup_maybe(self, "__len__", &len_str);
5003                 if (func == NULL)
5004                         return PyErr_Occurred() ? -1 : 1;
5005         }
5006         args = PyTuple_New(0);
5007         if (args != NULL) {
5008                 PyObject *temp = PyObject_Call(func, args, NULL);
5009                 Py_DECREF(args);
5010                 if (temp != NULL) {
5011                         if (PyInt_CheckExact(temp) || PyBool_Check(temp))
5012                                 result = PyObject_IsTrue(temp);
5013                         else {
5014                                 PyErr_Format(PyExc_TypeError,
5015                                              "__nonzero__ should return "
5016                                              "bool or int, returned %s",
5017                                              temp->ob_type->tp_name);
5018                                 result = -1;
5019                         }
5020                         Py_DECREF(temp);
5021                 }
5022         }
5023         Py_DECREF(func);
5024         return result;
5025 }
5026
5027
5028 static PyObject *
5029 slot_nb_index(PyObject *self)
5030 {
5031         static PyObject *index_str;
5032         return call_method(self, "__index__", &index_str, "()");
5033 }
5034
5035
5036 SLOT0(slot_nb_invert, "__invert__")
5037 SLOT1BIN(slot_nb_lshift, nb_lshift, "__lshift__", "__rlshift__")
5038 SLOT1BIN(slot_nb_rshift, nb_rshift, "__rshift__", "__rrshift__")
5039 SLOT1BIN(slot_nb_and, nb_and, "__and__", "__rand__")
5040 SLOT1BIN(slot_nb_xor, nb_xor, "__xor__", "__rxor__")
5041 SLOT1BIN(slot_nb_or, nb_or, "__or__", "__ror__")
5042
5043 static int
5044 slot_nb_coerce(PyObject **a, PyObject **b)
5045 {
5046         static PyObject *coerce_str;
5047         PyObject *self = *a, *other = *b;
5048
5049         if (self->ob_type->tp_as_number != NULL &&
5050             self->ob_type->tp_as_number->nb_coerce == slot_nb_coerce) {
5051                 PyObject *r;
5052                 r = call_maybe(
5053                         self, "__coerce__", &coerce_str, "(O)", other);
5054                 if (r == NULL)
5055                         return -1;
5056                 if (r == Py_NotImplemented) {
5057                         Py_DECREF(r);
5058                 }
5059                 else {
5060                         if (!PyTuple_Check(r) || PyTuple_GET_SIZE(r) != 2) {
5061                                 PyErr_SetString(PyExc_TypeError,
5062                                         "__coerce__ didn't return a 2-tuple");
5063                                 Py_DECREF(r);
5064                                 return -1;
5065                         }
5066                         *a = PyTuple_GET_ITEM(r, 0);
5067                         Py_INCREF(*a);
5068                         *b = PyTuple_GET_ITEM(r, 1);
5069                         Py_INCREF(*b);
5070                         Py_DECREF(r);
5071                         return 0;
5072                 }
5073         }
5074         if (other->ob_type->tp_as_number != NULL &&
5075             other->ob_type->tp_as_number->nb_coerce == slot_nb_coerce) {
5076                 PyObject *r;
5077                 r = call_maybe(
5078                         other, "__coerce__", &coerce_str, "(O)", self);
5079                 if (r == NULL)
5080                         return -1;
5081                 if (r == Py_NotImplemented) {
5082                         Py_DECREF(r);
5083                         return 1;
5084                 }
5085                 if (!PyTuple_Check(r) || PyTuple_GET_SIZE(r) != 2) {
5086                         PyErr_SetString(PyExc_TypeError,
5087                                         "__coerce__ didn't return a 2-tuple");
5088                         Py_DECREF(r);
5089                         return -1;
5090                 }
5091                 *a = PyTuple_GET_ITEM(r, 1);
5092                 Py_INCREF(*a);
5093                 *b = PyTuple_GET_ITEM(r, 0);
5094                 Py_INCREF(*b);
5095                 Py_DECREF(r);
5096                 return 0;
5097         }
5098         return 1;
5099 }
5100
5101 SLOT0(slot_nb_int, "__int__")
5102 SLOT0(slot_nb_long, "__long__")
5103 SLOT0(slot_nb_float, "__float__")
5104 SLOT0(slot_nb_oct, "__oct__")
5105 SLOT0(slot_nb_hex, "__hex__")
5106 SLOT1(slot_nb_inplace_add, "__iadd__", PyObject *, "O")
5107 SLOT1(slot_nb_inplace_subtract, "__isub__", PyObject *, "O")
5108 SLOT1(slot_nb_inplace_multiply, "__imul__", PyObject *, "O")
5109 SLOT1(slot_nb_inplace_divide, "__idiv__", PyObject *, "O")
5110 SLOT1(slot_nb_inplace_remainder, "__imod__", PyObject *, "O")
5111 /* Can't use SLOT1 here, because nb_inplace_power is ternary */
5112 static PyObject *
5113 slot_nb_inplace_power(PyObject *self, PyObject * arg1, PyObject *arg2)
5114 {
5115   static PyObject *cache_str;
5116   return call_method(self, "__ipow__", &cache_str, "(" "O" ")", arg1);
5117 }
5118 SLOT1(slot_nb_inplace_lshift, "__ilshift__", PyObject *, "O")
5119 SLOT1(slot_nb_inplace_rshift, "__irshift__", PyObject *, "O")
5120 SLOT1(slot_nb_inplace_and, "__iand__", PyObject *, "O")
5121 SLOT1(slot_nb_inplace_xor, "__ixor__", PyObject *, "O")
5122 SLOT1(slot_nb_inplace_or, "__ior__", PyObject *, "O")
5123 SLOT1BIN(slot_nb_floor_divide, nb_floor_divide,
5124          "__floordiv__", "__rfloordiv__")
5125 SLOT1BIN(slot_nb_true_divide, nb_true_divide, "__truediv__", "__rtruediv__")
5126 SLOT1(slot_nb_inplace_floor_divide, "__ifloordiv__", PyObject *, "O")
5127 SLOT1(slot_nb_inplace_true_divide, "__itruediv__", PyObject *, "O")
5128
5129 static int
5130 half_compare(PyObject *self, PyObject *other)
5131 {
5132         PyObject *func, *args, *res;
5133         static PyObject *cmp_str;
5134         Py_ssize_t c;
5135
5136         func = lookup_method(self, "__cmp__", &cmp_str);
5137         if (func == NULL) {
5138                 PyErr_Clear();
5139         }
5140         else {
5141                 args = PyTuple_Pack(1, other);
5142                 if (args == NULL)
5143                         res = NULL;
5144                 else {
5145                         res = PyObject_Call(func, args, NULL);
5146                         Py_DECREF(args);
5147                 }
5148                 Py_DECREF(func);
5149                 if (res != Py_NotImplemented) {
5150                         if (res == NULL)
5151                                 return -2;
5152                         c = PyInt_AsLong(res);
5153                         Py_DECREF(res);
5154                         if (c == -1 && PyErr_Occurred())
5155                                 return -2;
5156                         return (c < 0) ? -1 : (c > 0) ? 1 : 0;
5157                 }
5158                 Py_DECREF(res);
5159         }
5160         return 2;
5161 }
5162
5163 /* This slot is published for the benefit of try_3way_compare in object.c */
5164 int
5165 _PyObject_SlotCompare(PyObject *self, PyObject *other)
5166 {
5167         int c;
5168
5169         if (Py_TYPE(self)->tp_compare == _PyObject_SlotCompare) {
5170                 c = half_compare(self, other);
5171                 if (c <= 1)
5172                         return c;
5173         }
5174         if (Py_TYPE(other)->tp_compare == _PyObject_SlotCompare) {
5175                 c = half_compare(other, self);
5176                 if (c < -1)
5177                         return -2;
5178                 if (c <= 1)
5179                         return -c;
5180         }
5181         return (void *)self < (void *)other ? -1 :
5182                 (void *)self > (void *)other ? 1 : 0;
5183 }
5184
5185 static PyObject *
5186 slot_tp_repr(PyObject *self)
5187 {
5188         PyObject *func, *res;
5189         static PyObject *repr_str;
5190
5191         func = lookup_method(self, "__repr__", &repr_str);
5192         if (func != NULL) {
5193                 res = PyEval_CallObject(func, NULL);
5194                 Py_DECREF(func);
5195                 return res;
5196         }
5197         PyErr_Clear();
5198         return PyString_FromFormat("<%s object at %p>",
5199                                    Py_TYPE(self)->tp_name, self);
5200 }
5201
5202 static PyObject *
5203 slot_tp_str(PyObject *self)
5204 {
5205         PyObject *func, *res;
5206         static PyObject *str_str;
5207
5208         func = lookup_method(self, "__str__", &str_str);
5209         if (func != NULL) {
5210                 res = PyEval_CallObject(func, NULL);
5211                 Py_DECREF(func);
5212                 return res;
5213         }
5214         else {
5215                 PyErr_Clear();
5216                 return slot_tp_repr(self);
5217         }
5218 }
5219
5220 static long
5221 slot_tp_hash(PyObject *self)
5222 {
5223         PyObject *func;
5224         static PyObject *hash_str, *eq_str, *cmp_str;
5225         long h;
5226
5227         func = lookup_method(self, "__hash__", &hash_str);
5228
5229         if (func != NULL && func != Py_None) {
5230                 PyObject *res = PyEval_CallObject(func, NULL);
5231                 Py_DECREF(func);
5232                 if (res == NULL)
5233                         return -1;
5234                 if (PyLong_Check(res))
5235                         h = PyLong_Type.tp_hash(res);
5236                 else
5237                         h = PyInt_AsLong(res);
5238                 Py_DECREF(res);
5239         }
5240         else {
5241                 Py_XDECREF(func); /* may be None */
5242                 PyErr_Clear();
5243                 func = lookup_method(self, "__eq__", &eq_str);
5244                 if (func == NULL) {
5245                         PyErr_Clear();
5246                         func = lookup_method(self, "__cmp__", &cmp_str);
5247                 }
5248                 if (func != NULL) {
5249                         Py_DECREF(func);
5250                         return PyObject_HashNotImplemented(self);
5251                 }
5252                 PyErr_Clear();
5253                 h = _Py_HashPointer((void *)self);
5254         }
5255         if (h == -1 && !PyErr_Occurred())
5256                 h = -2;
5257         return h;
5258 }
5259
5260 static PyObject *
5261 slot_tp_call(PyObject *self, PyObject *args, PyObject *kwds)
5262 {
5263         static PyObject *call_str;
5264         PyObject *meth = lookup_method(self, "__call__", &call_str);
5265         PyObject *res;
5266
5267         if (meth == NULL)
5268                 return NULL;
5269
5270         res = PyObject_Call(meth, args, kwds);
5271
5272         Py_DECREF(meth);
5273         return res;
5274 }
5275
5276 /* There are two slot dispatch functions for tp_getattro.
5277
5278    - slot_tp_getattro() is used when __getattribute__ is overridden
5279      but no __getattr__ hook is present;
5280
5281    - slot_tp_getattr_hook() is used when a __getattr__ hook is present.
5282
5283    The code in update_one_slot() always installs slot_tp_getattr_hook(); this
5284    detects the absence of __getattr__ and then installs the simpler slot if
5285    necessary. */
5286
5287 static PyObject *
5288 slot_tp_getattro(PyObject *self, PyObject *name)
5289 {
5290         static PyObject *getattribute_str = NULL;
5291         return call_method(self, "__getattribute__", &getattribute_str,
5292                            "(O)", name);
5293 }
5294
5295 static PyObject *
5296 slot_tp_getattr_hook(PyObject *self, PyObject *name)
5297 {
5298         PyTypeObject *tp = Py_TYPE(self);
5299         PyObject *getattr, *getattribute, *res;
5300         static PyObject *getattribute_str = NULL;
5301         static PyObject *getattr_str = NULL;
5302
5303         if (getattr_str == NULL) {
5304                 getattr_str = PyString_InternFromString("__getattr__");
5305                 if (getattr_str == NULL)
5306                         return NULL;
5307         }
5308         if (getattribute_str == NULL) {
5309                 getattribute_str =
5310                         PyString_InternFromString("__getattribute__");
5311                 if (getattribute_str == NULL)
5312                         return NULL;
5313         }
5314         getattr = _PyType_Lookup(tp, getattr_str);
5315         if (getattr == NULL) {
5316                 /* No __getattr__ hook: use a simpler dispatcher */
5317                 tp->tp_getattro = slot_tp_getattro;
5318                 return slot_tp_getattro(self, name);
5319         }
5320         getattribute = _PyType_Lookup(tp, getattribute_str);
5321         if (getattribute == NULL ||
5322             (Py_TYPE(getattribute) == &PyWrapperDescr_Type &&
5323              ((PyWrapperDescrObject *)getattribute)->d_wrapped ==
5324              (void *)PyObject_GenericGetAttr))
5325                 res = PyObject_GenericGetAttr(self, name);
5326         else
5327                 res = PyObject_CallFunctionObjArgs(getattribute, self, name, NULL);
5328         if (res == NULL && PyErr_ExceptionMatches(PyExc_AttributeError)) {
5329                 PyErr_Clear();
5330                 res = PyObject_CallFunctionObjArgs(getattr, self, name, NULL);
5331         }
5332         return res;
5333 }
5334
5335 static int
5336 slot_tp_setattro(PyObject *self, PyObject *name, PyObject *value)
5337 {
5338         PyObject *res;
5339         static PyObject *delattr_str, *setattr_str;
5340
5341         if (value == NULL)
5342                 res = call_method(self, "__delattr__", &delattr_str,
5343                                   "(O)", name);
5344         else
5345                 res = call_method(self, "__setattr__", &setattr_str,
5346                                   "(OO)", name, value);
5347         if (res == NULL)
5348                 return -1;
5349         Py_DECREF(res);
5350         return 0;
5351 }
5352
5353 static char *name_op[] = {
5354     "__lt__",
5355     "__le__",
5356     "__eq__",
5357     "__ne__",
5358     "__gt__",
5359     "__ge__",
5360 };
5361
5362 static PyObject *
5363 half_richcompare(PyObject *self, PyObject *other, int op)
5364 {
5365         PyObject *func, *args, *res;
5366         static PyObject *op_str[6];
5367
5368         func = lookup_method(self, name_op[op], &op_str[op]);
5369         if (func == NULL) {
5370                 PyErr_Clear();
5371                 Py_INCREF(Py_NotImplemented);
5372                 return Py_NotImplemented;
5373         }
5374         args = PyTuple_Pack(1, other);
5375         if (args == NULL)
5376                 res = NULL;
5377         else {
5378                 res = PyObject_Call(func, args, NULL);
5379                 Py_DECREF(args);
5380         }
5381         Py_DECREF(func);
5382         return res;
5383 }
5384
5385 static PyObject *
5386 slot_tp_richcompare(PyObject *self, PyObject *other, int op)
5387 {
5388         PyObject *res;
5389
5390         if (Py_TYPE(self)->tp_richcompare == slot_tp_richcompare) {
5391                 res = half_richcompare(self, other, op);
5392                 if (res != Py_NotImplemented)
5393                         return res;
5394                 Py_DECREF(res);
5395         }
5396         if (Py_TYPE(other)->tp_richcompare == slot_tp_richcompare) {
5397                 res = half_richcompare(other, self, _Py_SwappedOp[op]);
5398                 if (res != Py_NotImplemented) {
5399                         return res;
5400                 }
5401                 Py_DECREF(res);
5402         }
5403         Py_INCREF(Py_NotImplemented);
5404         return Py_NotImplemented;
5405 }
5406
5407 static PyObject *
5408 slot_tp_iter(PyObject *self)
5409 {
5410         PyObject *func, *res;
5411         static PyObject *iter_str, *getitem_str;
5412
5413         func = lookup_method(self, "__iter__", &iter_str);
5414         if (func != NULL) {
5415                 PyObject *args;
5416                 args = res = PyTuple_New(0);
5417                 if (args != NULL) {
5418                         res = PyObject_Call(func, args, NULL);
5419                         Py_DECREF(args);
5420                 }
5421                 Py_DECREF(func);
5422                 return res;
5423         }
5424         PyErr_Clear();
5425         func = lookup_method(self, "__getitem__", &getitem_str);
5426         if (func == NULL) {
5427                 PyErr_Format(PyExc_TypeError,
5428                              "'%.200s' object is not iterable",
5429                              Py_TYPE(self)->tp_name);
5430                 return NULL;
5431         }
5432         Py_DECREF(func);
5433         return PySeqIter_New(self);
5434 }
5435
5436 static PyObject *
5437 slot_tp_iternext(PyObject *self)
5438 {
5439         static PyObject *next_str;
5440         return call_method(self, "next", &next_str, "()");
5441 }
5442
5443 static PyObject *
5444 slot_tp_descr_get(PyObject *self, PyObject *obj, PyObject *type)
5445 {
5446         PyTypeObject *tp = Py_TYPE(self);
5447         PyObject *get;
5448         static PyObject *get_str = NULL;
5449
5450         if (get_str == NULL) {
5451                 get_str = PyString_InternFromString("__get__");
5452                 if (get_str == NULL)
5453                         return NULL;
5454         }
5455         get = _PyType_Lookup(tp, get_str);
5456         if (get == NULL) {
5457                 /* Avoid further slowdowns */
5458                 if (tp->tp_descr_get == slot_tp_descr_get)
5459                         tp->tp_descr_get = NULL;
5460                 Py_INCREF(self);
5461                 return self;
5462         }
5463         if (obj == NULL)
5464                 obj = Py_None;
5465         if (type == NULL)
5466                 type = Py_None;
5467         return PyObject_CallFunctionObjArgs(get, self, obj, type, NULL);
5468 }
5469
5470 static int
5471 slot_tp_descr_set(PyObject *self, PyObject *target, PyObject *value)
5472 {
5473         PyObject *res;
5474         static PyObject *del_str, *set_str;
5475
5476         if (value == NULL)
5477                 res = call_method(self, "__delete__", &del_str,
5478                                   "(O)", target);
5479         else
5480                 res = call_method(self, "__set__", &set_str,
5481                                   "(OO)", target, value);
5482         if (res == NULL)
5483                 return -1;
5484         Py_DECREF(res);
5485         return 0;
5486 }
5487
5488 static int
5489 slot_tp_init(PyObject *self, PyObject *args, PyObject *kwds)
5490 {
5491         static PyObject *init_str;
5492         PyObject *meth = lookup_method(self, "__init__", &init_str);
5493         PyObject *res;
5494
5495         if (meth == NULL)
5496                 return -1;
5497         res = PyObject_Call(meth, args, kwds);
5498         Py_DECREF(meth);
5499         if (res == NULL)
5500                 return -1;
5501         if (res != Py_None) {
5502                 PyErr_Format(PyExc_TypeError,
5503                              "__init__() should return None, not '%.200s'",
5504                              Py_TYPE(res)->tp_name);
5505                 Py_DECREF(res);
5506                 return -1;
5507         }
5508         Py_DECREF(res);
5509         return 0;
5510 }
5511
5512 static PyObject *
5513 slot_tp_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
5514 {
5515         static PyObject *new_str;
5516         PyObject *func;
5517         PyObject *newargs, *x;
5518         Py_ssize_t i, n;
5519
5520         if (new_str == NULL) {
5521                 new_str = PyString_InternFromString("__new__");
5522                 if (new_str == NULL)
5523                         return NULL;
5524         }
5525         func = PyObject_GetAttr((PyObject *)type, new_str);
5526         if (func == NULL)
5527                 return NULL;
5528         assert(PyTuple_Check(args));
5529         n = PyTuple_GET_SIZE(args);
5530         newargs = PyTuple_New(n+1);
5531         if (newargs == NULL)
5532                 return NULL;
5533         Py_INCREF(type);
5534         PyTuple_SET_ITEM(newargs, 0, (PyObject *)type);
5535         for (i = 0; i < n; i++) {
5536                 x = PyTuple_GET_ITEM(args, i);
5537                 Py_INCREF(x);
5538                 PyTuple_SET_ITEM(newargs, i+1, x);
5539         }
5540         x = PyObject_Call(func, newargs, kwds);
5541         Py_DECREF(newargs);
5542         Py_DECREF(func);
5543         return x;
5544 }
5545
5546 static void
5547 slot_tp_del(PyObject *self)
5548 {
5549         static PyObject *del_str = NULL;
5550         PyObject *del, *res;
5551         PyObject *error_type, *error_value, *error_traceback;
5552
5553         /* Temporarily resurrect the object. */
5554         assert(self->ob_refcnt == 0);
5555         self->ob_refcnt = 1;
5556
5557         /* Save the current exception, if any. */
5558         PyErr_Fetch(&error_type, &error_value, &error_traceback);
5559
5560         /* Execute __del__ method, if any. */
5561         del = lookup_maybe(self, "__del__", &del_str);
5562         if (del != NULL) {
5563                 res = PyEval_CallObject(del, NULL);
5564                 if (res == NULL)
5565                         PyErr_WriteUnraisable(del);
5566                 else
5567                         Py_DECREF(res);
5568                 Py_DECREF(del);
5569         }
5570
5571         /* Restore the saved exception. */
5572         PyErr_Restore(error_type, error_value, error_traceback);
5573
5574         /* Undo the temporary resurrection; can't use DECREF here, it would
5575          * cause a recursive call.
5576          */
5577         assert(self->ob_refcnt > 0);
5578         if (--self->ob_refcnt == 0)
5579                 return; /* this is the normal path out */
5580
5581         /* __del__ resurrected it!  Make it look like the original Py_DECREF
5582          * never happened.
5583          */
5584         {
5585                 Py_ssize_t refcnt = self->ob_refcnt;
5586                 _Py_NewReference(self);
5587                 self->ob_refcnt = refcnt;
5588         }
5589         assert(!PyType_IS_GC(Py_TYPE(self)) ||
5590                _Py_AS_GC(self)->gc.gc_refs != _PyGC_REFS_UNTRACKED);
5591         /* If Py_REF_DEBUG, _Py_NewReference bumped _Py_RefTotal, so
5592          * we need to undo that. */
5593         _Py_DEC_REFTOTAL;
5594         /* If Py_TRACE_REFS, _Py_NewReference re-added self to the object
5595          * chain, so no more to do there.
5596          * If COUNT_ALLOCS, the original decref bumped tp_frees, and
5597          * _Py_NewReference bumped tp_allocs:  both of those need to be
5598          * undone.
5599          */
5600 #ifdef COUNT_ALLOCS
5601         --Py_TYPE(self)->tp_frees;
5602         --Py_TYPE(self)->tp_allocs;
5603 #endif
5604 }
5605
5606
5607 /* Table mapping __foo__ names to tp_foo offsets and slot_tp_foo wrapper
5608    functions.  The offsets here are relative to the 'PyHeapTypeObject'
5609    structure, which incorporates the additional structures used for numbers,
5610    sequences and mappings.
5611    Note that multiple names may map to the same slot (e.g. __eq__,
5612    __ne__ etc. all map to tp_richcompare) and one name may map to multiple
5613    slots (e.g. __str__ affects tp_str as well as tp_repr). The table is
5614    terminated with an all-zero entry.  (This table is further initialized and
5615    sorted in init_slotdefs() below.) */
5616
5617 typedef struct wrapperbase slotdef;
5618
5619 #undef TPSLOT
5620 #undef FLSLOT
5621 #undef ETSLOT
5622 #undef SQSLOT
5623 #undef MPSLOT
5624 #undef NBSLOT
5625 #undef UNSLOT
5626 #undef IBSLOT
5627 #undef BINSLOT
5628 #undef RBINSLOT
5629
5630 #define TPSLOT(NAME, SLOT, FUNCTION, WRAPPER, DOC) \
5631         {NAME, offsetof(PyTypeObject, SLOT), (void *)(FUNCTION), WRAPPER, \
5632          PyDoc_STR(DOC)}
5633 #define FLSLOT(NAME, SLOT, FUNCTION, WRAPPER, DOC, FLAGS) \
5634         {NAME, offsetof(PyTypeObject, SLOT), (void *)(FUNCTION), WRAPPER, \
5635          PyDoc_STR(DOC), FLAGS}
5636 #define ETSLOT(NAME, SLOT, FUNCTION, WRAPPER, DOC) \
5637         {NAME, offsetof(PyHeapTypeObject, SLOT), (void *)(FUNCTION), WRAPPER, \
5638          PyDoc_STR(DOC)}
5639 #define SQSLOT(NAME, SLOT, FUNCTION, WRAPPER, DOC) \
5640         ETSLOT(NAME, as_sequence.SLOT, FUNCTION, WRAPPER, DOC)
5641 #define MPSLOT(NAME, SLOT, FUNCTION, WRAPPER, DOC) \
5642         ETSLOT(NAME, as_mapping.SLOT, FUNCTION, WRAPPER, DOC)
5643 #define NBSLOT(NAME, SLOT, FUNCTION, WRAPPER, DOC) \
5644         ETSLOT(NAME, as_number.SLOT, FUNCTION, WRAPPER, DOC)
5645 #define UNSLOT(NAME, SLOT, FUNCTION, WRAPPER, DOC) \
5646         ETSLOT(NAME, as_number.SLOT, FUNCTION, WRAPPER, \
5647                "x." NAME "() <==> " DOC)
5648 #define IBSLOT(NAME, SLOT, FUNCTION, WRAPPER, DOC) \
5649         ETSLOT(NAME, as_number.SLOT, FUNCTION, WRAPPER, \
5650                "x." NAME "(y) <==> x" DOC "y")
5651 #define BINSLOT(NAME, SLOT, FUNCTION, DOC) \
5652         ETSLOT(NAME, as_number.SLOT, FUNCTION, wrap_binaryfunc_l, \
5653                "x." NAME "(y) <==> x" DOC "y")
5654 #define RBINSLOT(NAME, SLOT, FUNCTION, DOC) \
5655         ETSLOT(NAME, as_number.SLOT, FUNCTION, wrap_binaryfunc_r, \
5656                "x." NAME "(y) <==> y" DOC "x")
5657 #define BINSLOTNOTINFIX(NAME, SLOT, FUNCTION, DOC) \
5658         ETSLOT(NAME, as_number.SLOT, FUNCTION, wrap_binaryfunc_l, \
5659                "x." NAME "(y) <==> " DOC)
5660 #define RBINSLOTNOTINFIX(NAME, SLOT, FUNCTION, DOC) \
5661         ETSLOT(NAME, as_number.SLOT, FUNCTION, wrap_binaryfunc_r, \
5662                "x." NAME "(y) <==> " DOC)
5663
5664 static slotdef slotdefs[] = {
5665         SQSLOT("__len__", sq_length, slot_sq_length, wrap_lenfunc,
5666                "x.__len__() <==> len(x)"),
5667         /* Heap types defining __add__/__mul__ have sq_concat/sq_repeat == NULL.
5668            The logic in abstract.c always falls back to nb_add/nb_multiply in
5669            this case.  Defining both the nb_* and the sq_* slots to call the
5670            user-defined methods has unexpected side-effects, as shown by
5671            test_descr.notimplemented() */
5672         SQSLOT("__add__", sq_concat, NULL, wrap_binaryfunc,
5673           "x.__add__(y) <==> x+y"),
5674         SQSLOT("__mul__", sq_repeat, NULL, wrap_indexargfunc,
5675           "x.__mul__(n) <==> x*n"),
5676         SQSLOT("__rmul__", sq_repeat, NULL, wrap_indexargfunc,
5677           "x.__rmul__(n) <==> n*x"),
5678         SQSLOT("__getitem__", sq_item, slot_sq_item, wrap_sq_item,
5679                "x.__getitem__(y) <==> x[y]"),
5680         SQSLOT("__getslice__", sq_slice, slot_sq_slice, wrap_ssizessizeargfunc,
5681                "x.__getslice__(i, j) <==> x[i:j]\n\
5682                \n\
5683                Use of negative indices is not supported."),
5684         SQSLOT("__setitem__", sq_ass_item, slot_sq_ass_item, wrap_sq_setitem,
5685                "x.__setitem__(i, y) <==> x[i]=y"),
5686         SQSLOT("__delitem__", sq_ass_item, slot_sq_ass_item, wrap_sq_delitem,
5687                "x.__delitem__(y) <==> del x[y]"),
5688         SQSLOT("__setslice__", sq_ass_slice, slot_sq_ass_slice,
5689                wrap_ssizessizeobjargproc,
5690                "x.__setslice__(i, j, y) <==> x[i:j]=y\n\
5691                \n\
5692                Use  of negative indices is not supported."),
5693         SQSLOT("__delslice__", sq_ass_slice, slot_sq_ass_slice, wrap_delslice,
5694                "x.__delslice__(i, j) <==> del x[i:j]\n\
5695                \n\
5696                Use of negative indices is not supported."),
5697         SQSLOT("__contains__", sq_contains, slot_sq_contains, wrap_objobjproc,
5698                "x.__contains__(y) <==> y in x"),
5699         SQSLOT("__iadd__", sq_inplace_concat, NULL,
5700           wrap_binaryfunc, "x.__iadd__(y) <==> x+=y"),
5701         SQSLOT("__imul__", sq_inplace_repeat, NULL,
5702           wrap_indexargfunc, "x.__imul__(y) <==> x*=y"),
5703
5704         MPSLOT("__len__", mp_length, slot_mp_length, wrap_lenfunc,
5705                "x.__len__() <==> len(x)"),
5706         MPSLOT("__getitem__", mp_subscript, slot_mp_subscript,
5707                wrap_binaryfunc,
5708                "x.__getitem__(y) <==> x[y]"),
5709         MPSLOT("__setitem__", mp_ass_subscript, slot_mp_ass_subscript,
5710                wrap_objobjargproc,
5711                "x.__setitem__(i, y) <==> x[i]=y"),
5712         MPSLOT("__delitem__", mp_ass_subscript, slot_mp_ass_subscript,
5713                wrap_delitem,
5714                "x.__delitem__(y) <==> del x[y]"),
5715
5716         BINSLOT("__add__", nb_add, slot_nb_add,
5717                 "+"),
5718         RBINSLOT("__radd__", nb_add, slot_nb_add,
5719                  "+"),
5720         BINSLOT("__sub__", nb_subtract, slot_nb_subtract,
5721                 "-"),
5722         RBINSLOT("__rsub__", nb_subtract, slot_nb_subtract,
5723                  "-"),
5724         BINSLOT("__mul__", nb_multiply, slot_nb_multiply,
5725                 "*"),
5726         RBINSLOT("__rmul__", nb_multiply, slot_nb_multiply,
5727                  "*"),
5728         BINSLOT("__div__", nb_divide, slot_nb_divide,
5729                 "/"),
5730         RBINSLOT("__rdiv__", nb_divide, slot_nb_divide,
5731                  "/"),
5732         BINSLOT("__mod__", nb_remainder, slot_nb_remainder,
5733                 "%"),
5734         RBINSLOT("__rmod__", nb_remainder, slot_nb_remainder,
5735                  "%"),
5736         BINSLOTNOTINFIX("__divmod__", nb_divmod, slot_nb_divmod,
5737                 "divmod(x, y)"),
5738         RBINSLOTNOTINFIX("__rdivmod__", nb_divmod, slot_nb_divmod,
5739                  "divmod(y, x)"),
5740         NBSLOT("__pow__", nb_power, slot_nb_power, wrap_ternaryfunc,
5741                "x.__pow__(y[, z]) <==> pow(x, y[, z])"),
5742         NBSLOT("__rpow__", nb_power, slot_nb_power, wrap_ternaryfunc_r,
5743                "y.__rpow__(x[, z]) <==> pow(x, y[, z])"),
5744         UNSLOT("__neg__", nb_negative, slot_nb_negative, wrap_unaryfunc, "-x"),
5745         UNSLOT("__pos__", nb_positive, slot_nb_positive, wrap_unaryfunc, "+x"),
5746         UNSLOT("__abs__", nb_absolute, slot_nb_absolute, wrap_unaryfunc,
5747                "abs(x)"),
5748         UNSLOT("__nonzero__", nb_nonzero, slot_nb_nonzero, wrap_inquirypred,
5749                "x != 0"),
5750         UNSLOT("__invert__", nb_invert, slot_nb_invert, wrap_unaryfunc, "~x"),
5751         BINSLOT("__lshift__", nb_lshift, slot_nb_lshift, "<<"),
5752         RBINSLOT("__rlshift__", nb_lshift, slot_nb_lshift, "<<"),
5753         BINSLOT("__rshift__", nb_rshift, slot_nb_rshift, ">>"),
5754         RBINSLOT("__rrshift__", nb_rshift, slot_nb_rshift, ">>"),
5755         BINSLOT("__and__", nb_and, slot_nb_and, "&"),
5756         RBINSLOT("__rand__", nb_and, slot_nb_and, "&"),
5757         BINSLOT("__xor__", nb_xor, slot_nb_xor, "^"),
5758         RBINSLOT("__rxor__", nb_xor, slot_nb_xor, "^"),
5759         BINSLOT("__or__", nb_or, slot_nb_or, "|"),
5760         RBINSLOT("__ror__", nb_or, slot_nb_or, "|"),
5761         NBSLOT("__coerce__", nb_coerce, slot_nb_coerce, wrap_coercefunc,
5762                "x.__coerce__(y) <==> coerce(x, y)"),
5763         UNSLOT("__int__", nb_int, slot_nb_int, wrap_unaryfunc,
5764                "int(x)"),
5765         UNSLOT("__long__", nb_long, slot_nb_long, wrap_unaryfunc,
5766                "long(x)"),
5767         UNSLOT("__float__", nb_float, slot_nb_float, wrap_unaryfunc,
5768                "float(x)"),
5769         UNSLOT("__oct__", nb_oct, slot_nb_oct, wrap_unaryfunc,
5770                "oct(x)"),
5771         UNSLOT("__hex__", nb_hex, slot_nb_hex, wrap_unaryfunc,
5772                "hex(x)"),
5773         NBSLOT("__index__", nb_index, slot_nb_index, wrap_unaryfunc,
5774                "x[y:z] <==> x[y.__index__():z.__index__()]"),
5775         IBSLOT("__iadd__", nb_inplace_add, slot_nb_inplace_add,
5776                wrap_binaryfunc, "+"),
5777         IBSLOT("__isub__", nb_inplace_subtract, slot_nb_inplace_subtract,
5778                wrap_binaryfunc, "-"),
5779         IBSLOT("__imul__", nb_inplace_multiply, slot_nb_inplace_multiply,
5780                wrap_binaryfunc, "*"),
5781         IBSLOT("__idiv__", nb_inplace_divide, slot_nb_inplace_divide,
5782                wrap_binaryfunc, "/"),
5783         IBSLOT("__imod__", nb_inplace_remainder, slot_nb_inplace_remainder,
5784                wrap_binaryfunc, "%"),
5785         IBSLOT("__ipow__", nb_inplace_power, slot_nb_inplace_power,
5786                wrap_binaryfunc, "**"),
5787         IBSLOT("__ilshift__", nb_inplace_lshift, slot_nb_inplace_lshift,
5788                wrap_binaryfunc, "<<"),
5789         IBSLOT("__irshift__", nb_inplace_rshift, slot_nb_inplace_rshift,
5790                wrap_binaryfunc, ">>"),
5791         IBSLOT("__iand__", nb_inplace_and, slot_nb_inplace_and,
5792                wrap_binaryfunc, "&"),
5793         IBSLOT("__ixor__", nb_inplace_xor, slot_nb_inplace_xor,
5794                wrap_binaryfunc, "^"),
5795         IBSLOT("__ior__", nb_inplace_or, slot_nb_inplace_or,
5796                wrap_binaryfunc, "|"),
5797         BINSLOT("__floordiv__", nb_floor_divide, slot_nb_floor_divide, "//"),
5798         RBINSLOT("__rfloordiv__", nb_floor_divide, slot_nb_floor_divide, "//"),
5799         BINSLOT("__truediv__", nb_true_divide, slot_nb_true_divide, "/"),
5800         RBINSLOT("__rtruediv__", nb_true_divide, slot_nb_true_divide, "/"),
5801         IBSLOT("__ifloordiv__", nb_inplace_floor_divide,
5802                slot_nb_inplace_floor_divide, wrap_binaryfunc, "//"),
5803         IBSLOT("__itruediv__", nb_inplace_true_divide,
5804                slot_nb_inplace_true_divide, wrap_binaryfunc, "/"),
5805
5806         TPSLOT("__str__", tp_str, slot_tp_str, wrap_unaryfunc,
5807                "x.__str__() <==> str(x)"),
5808         TPSLOT("__str__", tp_print, NULL, NULL, ""),
5809         TPSLOT("__repr__", tp_repr, slot_tp_repr, wrap_unaryfunc,
5810                "x.__repr__() <==> repr(x)"),
5811         TPSLOT("__repr__", tp_print, NULL, NULL, ""),
5812         TPSLOT("__cmp__", tp_compare, _PyObject_SlotCompare, wrap_cmpfunc,
5813                "x.__cmp__(y) <==> cmp(x,y)"),
5814         TPSLOT("__hash__", tp_hash, slot_tp_hash, wrap_hashfunc,
5815                "x.__hash__() <==> hash(x)"),
5816         FLSLOT("__call__", tp_call, slot_tp_call, (wrapperfunc)wrap_call,
5817                "x.__call__(...) <==> x(...)", PyWrapperFlag_KEYWORDS),
5818         TPSLOT("__getattribute__", tp_getattro, slot_tp_getattr_hook,
5819                wrap_binaryfunc, "x.__getattribute__('name') <==> x.name"),
5820         TPSLOT("__getattribute__", tp_getattr, NULL, NULL, ""),
5821         TPSLOT("__getattr__", tp_getattro, slot_tp_getattr_hook, NULL, ""),
5822         TPSLOT("__getattr__", tp_getattr, NULL, NULL, ""),
5823         TPSLOT("__setattr__", tp_setattro, slot_tp_setattro, wrap_setattr,
5824                "x.__setattr__('name', value) <==> x.name = value"),
5825         TPSLOT("__setattr__", tp_setattr, NULL, NULL, ""),
5826         TPSLOT("__delattr__", tp_setattro, slot_tp_setattro, wrap_delattr,
5827                "x.__delattr__('name') <==> del x.name"),
5828         TPSLOT("__delattr__", tp_setattr, NULL, NULL, ""),
5829         TPSLOT("__lt__", tp_richcompare, slot_tp_richcompare, richcmp_lt,
5830                "x.__lt__(y) <==> x<y"),
5831         TPSLOT("__le__", tp_richcompare, slot_tp_richcompare, richcmp_le,
5832                "x.__le__(y) <==> x<=y"),
5833         TPSLOT("__eq__", tp_richcompare, slot_tp_richcompare, richcmp_eq,
5834                "x.__eq__(y) <==> x==y"),
5835         TPSLOT("__ne__", tp_richcompare, slot_tp_richcompare, richcmp_ne,
5836                "x.__ne__(y) <==> x!=y"),
5837         TPSLOT("__gt__", tp_richcompare, slot_tp_richcompare, richcmp_gt,
5838                "x.__gt__(y) <==> x>y"),
5839         TPSLOT("__ge__", tp_richcompare, slot_tp_richcompare, richcmp_ge,
5840                "x.__ge__(y) <==> x>=y"),
5841         TPSLOT("__iter__", tp_iter, slot_tp_iter, wrap_unaryfunc,
5842                "x.__iter__() <==> iter(x)"),
5843         TPSLOT("next", tp_iternext, slot_tp_iternext, wrap_next,
5844                "x.next() -> the next value, or raise StopIteration"),
5845         TPSLOT("__get__", tp_descr_get, slot_tp_descr_get, wrap_descr_get,
5846                "descr.__get__(obj[, type]) -> value"),
5847         TPSLOT("__set__", tp_descr_set, slot_tp_descr_set, wrap_descr_set,
5848                "descr.__set__(obj, value)"),
5849         TPSLOT("__delete__", tp_descr_set, slot_tp_descr_set,
5850                wrap_descr_delete, "descr.__delete__(obj)"),
5851         FLSLOT("__init__", tp_init, slot_tp_init, (wrapperfunc)wrap_init,
5852                "x.__init__(...) initializes x; "
5853                "see x.__class__.__doc__ for signature",
5854                PyWrapperFlag_KEYWORDS),
5855         TPSLOT("__new__", tp_new, slot_tp_new, NULL, ""),
5856         TPSLOT("__del__", tp_del, slot_tp_del, NULL, ""),
5857         {NULL}
5858 };
5859
5860 /* Given a type pointer and an offset gotten from a slotdef entry, return a
5861    pointer to the actual slot.  This is not quite the same as simply adding
5862    the offset to the type pointer, since it takes care to indirect through the
5863    proper indirection pointer (as_buffer, etc.); it returns NULL if the
5864    indirection pointer is NULL. */
5865 static void **
5866 slotptr(PyTypeObject *type, int ioffset)
5867 {
5868         char *ptr;
5869         long offset = ioffset;
5870
5871         /* Note: this depends on the order of the members of PyHeapTypeObject! */
5872         assert(offset >= 0);
5873         assert((size_t)offset < offsetof(PyHeapTypeObject, as_buffer));
5874         if ((size_t)offset >= offsetof(PyHeapTypeObject, as_sequence)) {
5875                 ptr = (char *)type->tp_as_sequence;
5876                 offset -= offsetof(PyHeapTypeObject, as_sequence);
5877         }
5878         else if ((size_t)offset >= offsetof(PyHeapTypeObject, as_mapping)) {
5879                 ptr = (char *)type->tp_as_mapping;
5880                 offset -= offsetof(PyHeapTypeObject, as_mapping);
5881         }
5882         else if ((size_t)offset >= offsetof(PyHeapTypeObject, as_number)) {
5883                 ptr = (char *)type->tp_as_number;
5884                 offset -= offsetof(PyHeapTypeObject, as_number);
5885         }
5886         else {
5887                 ptr = (char *)type;
5888         }
5889         if (ptr != NULL)
5890                 ptr += offset;
5891         return (void **)ptr;
5892 }
5893
5894 /* Length of array of slotdef pointers used to store slots with the
5895    same __name__.  There should be at most MAX_EQUIV-1 slotdef entries with
5896    the same __name__, for any __name__. Since that's a static property, it is
5897    appropriate to declare fixed-size arrays for this. */
5898 #define MAX_EQUIV 10
5899
5900 /* Return a slot pointer for a given name, but ONLY if the attribute has
5901    exactly one slot function.  The name must be an interned string. */
5902 static void **
5903 resolve_slotdups(PyTypeObject *type, PyObject *name)
5904 {
5905         /* XXX Maybe this could be optimized more -- but is it worth it? */
5906
5907         /* pname and ptrs act as a little cache */
5908         static PyObject *pname;
5909         static slotdef *ptrs[MAX_EQUIV];
5910         slotdef *p, **pp;
5911         void **res, **ptr;
5912
5913         if (pname != name) {
5914                 /* Collect all slotdefs that match name into ptrs. */
5915                 pname = name;
5916                 pp = ptrs;
5917                 for (p = slotdefs; p->name_strobj; p++) {
5918                         if (p->name_strobj == name)
5919                                 *pp++ = p;
5920                 }
5921                 *pp = NULL;
5922         }
5923
5924         /* Look in all matching slots of the type; if exactly one of these has
5925            a filled-in slot, return its value.  Otherwise return NULL. */
5926         res = NULL;
5927         for (pp = ptrs; *pp; pp++) {
5928                 ptr = slotptr(type, (*pp)->offset);
5929                 if (ptr == NULL || *ptr == NULL)
5930                         continue;
5931                 if (res != NULL)
5932                         return NULL;
5933                 res = ptr;
5934         }
5935         return res;
5936 }
5937
5938 /* Common code for update_slots_callback() and fixup_slot_dispatchers().  This
5939    does some incredibly complex thinking and then sticks something into the
5940    slot.  (It sees if the adjacent slotdefs for the same slot have conflicting
5941    interests, and then stores a generic wrapper or a specific function into
5942    the slot.)  Return a pointer to the next slotdef with a different offset,
5943    because that's convenient  for fixup_slot_dispatchers(). */
5944 static slotdef *
5945 update_one_slot(PyTypeObject *type, slotdef *p)
5946 {
5947         PyObject *descr;
5948         PyWrapperDescrObject *d;
5949         void *generic = NULL, *specific = NULL;
5950         int use_generic = 0;
5951         int offset = p->offset;
5952         void **ptr = slotptr(type, offset);
5953
5954         if (ptr == NULL) {
5955                 do {
5956                         ++p;
5957                 } while (p->offset == offset);
5958                 return p;
5959         }
5960         do {
5961                 descr = _PyType_Lookup(type, p->name_strobj);
5962                 if (descr == NULL)
5963                         continue;
5964                 if (Py_TYPE(descr) == &PyWrapperDescr_Type) {
5965                         void **tptr = resolve_slotdups(type, p->name_strobj);
5966                         if (tptr == NULL || tptr == ptr)
5967                                 generic = p->function;
5968                         d = (PyWrapperDescrObject *)descr;
5969                         if (d->d_base->wrapper == p->wrapper &&
5970                             PyType_IsSubtype(type, d->d_type))
5971                         {
5972                                 if (specific == NULL ||
5973                                     specific == d->d_wrapped)
5974                                         specific = d->d_wrapped;
5975                                 else
5976                                         use_generic = 1;
5977                         }
5978                 }
5979                 else if (Py_TYPE(descr) == &PyCFunction_Type &&
5980                          PyCFunction_GET_FUNCTION(descr) ==
5981                          (PyCFunction)tp_new_wrapper &&
5982                          strcmp(p->name, "__new__") == 0)
5983                 {
5984                         /* The __new__ wrapper is not a wrapper descriptor,
5985                            so must be special-cased differently.
5986                            If we don't do this, creating an instance will
5987                            always use slot_tp_new which will look up
5988                            __new__ in the MRO which will call tp_new_wrapper
5989                            which will look through the base classes looking
5990                            for a static base and call its tp_new (usually
5991                            PyType_GenericNew), after performing various
5992                            sanity checks and constructing a new argument
5993                            list.  Cut all that nonsense short -- this speeds
5994                            up instance creation tremendously. */
5995                         specific = (void *)type->tp_new;
5996                         /* XXX I'm not 100% sure that there isn't a hole
5997                            in this reasoning that requires additional
5998                            sanity checks.  I'll buy the first person to
5999                            point out a bug in this reasoning a beer. */
6000                 }
6001                 else if (descr == Py_None &&
6002                          strcmp(p->name, "__hash__") == 0) {
6003                         /* We specifically allow __hash__ to be set to None
6004                            to prevent inheritance of the default
6005                            implementation from object.__hash__ */
6006                         specific = PyObject_HashNotImplemented;
6007                 }
6008                 else {
6009                         use_generic = 1;
6010                         generic = p->function;
6011                 }
6012         } while ((++p)->offset == offset);
6013         if (specific && !use_generic)
6014                 *ptr = specific;
6015         else
6016                 *ptr = generic;
6017         return p;
6018 }
6019
6020 /* In the type, update the slots whose slotdefs are gathered in the pp array.
6021    This is a callback for update_subclasses(). */
6022 static int
6023 update_slots_callback(PyTypeObject *type, void *data)
6024 {
6025         slotdef **pp = (slotdef **)data;
6026
6027         for (; *pp; pp++)
6028                 update_one_slot(type, *pp);
6029         return 0;
6030 }
6031
6032 /* Comparison function for qsort() to compare slotdefs by their offset, and
6033    for equal offset by their address (to force a stable sort). */
6034 static int
6035 slotdef_cmp(const void *aa, const void *bb)
6036 {
6037         const slotdef *a = (const slotdef *)aa, *b = (const slotdef *)bb;
6038         int c = a->offset - b->offset;
6039         if (c != 0)
6040                 return c;
6041         else
6042                 /* Cannot use a-b, as this gives off_t,
6043                    which may lose precision when converted to int. */
6044                 return (a > b) ? 1 : (a < b) ? -1 : 0;
6045 }
6046
6047 /* Initialize the slotdefs table by adding interned string objects for the
6048    names and sorting the entries. */
6049 static void
6050 init_slotdefs(void)
6051 {
6052         slotdef *p;
6053         static int initialized = 0;
6054
6055         if (initialized)
6056                 return;
6057         for (p = slotdefs; p->name; p++) {
6058                 p->name_strobj = PyString_InternFromString(p->name);
6059                 if (!p->name_strobj)
6060                         Py_FatalError("Out of memory interning slotdef names");
6061         }
6062         qsort((void *)slotdefs, (size_t)(p-slotdefs), sizeof(slotdef),
6063               slotdef_cmp);
6064         initialized = 1;
6065 }
6066
6067 /* Update the slots after assignment to a class (type) attribute. */
6068 static int
6069 update_slot(PyTypeObject *type, PyObject *name)
6070 {
6071         slotdef *ptrs[MAX_EQUIV];
6072         slotdef *p;
6073         slotdef **pp;
6074         int offset;
6075
6076         /* Clear the VALID_VERSION flag of 'type' and all its
6077            subclasses.  This could possibly be unified with the
6078            update_subclasses() recursion below, but carefully:
6079            they each have their own conditions on which to stop
6080            recursing into subclasses. */
6081         PyType_Modified(type);
6082
6083         init_slotdefs();
6084         pp = ptrs;
6085         for (p = slotdefs; p->name; p++) {
6086                 /* XXX assume name is interned! */
6087                 if (p->name_strobj == name)
6088                         *pp++ = p;
6089         }
6090         *pp = NULL;
6091         for (pp = ptrs; *pp; pp++) {
6092                 p = *pp;
6093                 offset = p->offset;
6094                 while (p > slotdefs && (p-1)->offset == offset)
6095                         --p;
6096                 *pp = p;
6097         }
6098         if (ptrs[0] == NULL)
6099                 return 0; /* Not an attribute that affects any slots */
6100         return update_subclasses(type, name,
6101                                  update_slots_callback, (void *)ptrs);
6102 }
6103
6104 /* Store the proper functions in the slot dispatches at class (type)
6105    definition time, based upon which operations the class overrides in its
6106    dict. */
6107 static void
6108 fixup_slot_dispatchers(PyTypeObject *type)
6109 {
6110         slotdef *p;
6111
6112         init_slotdefs();
6113         for (p = slotdefs; p->name; )
6114                 p = update_one_slot(type, p);
6115 }
6116
6117 static void
6118 update_all_slots(PyTypeObject* type)
6119 {
6120         slotdef *p;
6121
6122         init_slotdefs();
6123         for (p = slotdefs; p->name; p++) {
6124                 /* update_slot returns int but can't actually fail */
6125                 update_slot(type, p->name_strobj);
6126         }
6127 }
6128
6129 /* recurse_down_subclasses() and update_subclasses() are mutually
6130    recursive functions to call a callback for all subclasses,
6131    but refraining from recursing into subclasses that define 'name'. */
6132
6133 static int
6134 update_subclasses(PyTypeObject *type, PyObject *name,
6135                   update_callback callback, void *data)
6136 {
6137         if (callback(type, data) < 0)
6138                 return -1;
6139         return recurse_down_subclasses(type, name, callback, data);
6140 }
6141
6142 static int
6143 recurse_down_subclasses(PyTypeObject *type, PyObject *name,
6144                         update_callback callback, void *data)
6145 {
6146         PyTypeObject *subclass;
6147         PyObject *ref, *subclasses, *dict;
6148         Py_ssize_t i, n;
6149
6150         subclasses = type->tp_subclasses;
6151         if (subclasses == NULL)
6152                 return 0;
6153         assert(PyList_Check(subclasses));
6154         n = PyList_GET_SIZE(subclasses);
6155         for (i = 0; i < n; i++) {
6156                 ref = PyList_GET_ITEM(subclasses, i);
6157                 assert(PyWeakref_CheckRef(ref));
6158                 subclass = (PyTypeObject *)PyWeakref_GET_OBJECT(ref);
6159                 assert(subclass != NULL);
6160                 if ((PyObject *)subclass == Py_None)
6161                         continue;
6162                 assert(PyType_Check(subclass));
6163                 /* Avoid recursing down into unaffected classes */
6164                 dict = subclass->tp_dict;
6165                 if (dict != NULL && PyDict_Check(dict) &&
6166                     PyDict_GetItem(dict, name) != NULL)
6167                         continue;
6168                 if (update_subclasses(subclass, name, callback, data) < 0)
6169                         return -1;
6170         }
6171         return 0;
6172 }
6173
6174 /* This function is called by PyType_Ready() to populate the type's
6175    dictionary with method descriptors for function slots.  For each
6176    function slot (like tp_repr) that's defined in the type, one or more
6177    corresponding descriptors are added in the type's tp_dict dictionary
6178    under the appropriate name (like __repr__).  Some function slots
6179    cause more than one descriptor to be added (for example, the nb_add
6180    slot adds both __add__ and __radd__ descriptors) and some function
6181    slots compete for the same descriptor (for example both sq_item and
6182    mp_subscript generate a __getitem__ descriptor).
6183
6184    In the latter case, the first slotdef entry encoutered wins.  Since
6185    slotdef entries are sorted by the offset of the slot in the
6186    PyHeapTypeObject, this gives us some control over disambiguating
6187    between competing slots: the members of PyHeapTypeObject are listed
6188    from most general to least general, so the most general slot is
6189    preferred.  In particular, because as_mapping comes before as_sequence,
6190    for a type that defines both mp_subscript and sq_item, mp_subscript
6191    wins.
6192
6193    This only adds new descriptors and doesn't overwrite entries in
6194    tp_dict that were previously defined.  The descriptors contain a
6195    reference to the C function they must call, so that it's safe if they
6196    are copied into a subtype's __dict__ and the subtype has a different
6197    C function in its slot -- calling the method defined by the
6198    descriptor will call the C function that was used to create it,
6199    rather than the C function present in the slot when it is called.
6200    (This is important because a subtype may have a C function in the
6201    slot that calls the method from the dictionary, and we want to avoid
6202    infinite recursion here.) */
6203
6204 static int
6205 add_operators(PyTypeObject *type)
6206 {
6207         PyObject *dict = type->tp_dict;
6208         slotdef *p;
6209         PyObject *descr;
6210         void **ptr;
6211
6212         init_slotdefs();
6213         for (p = slotdefs; p->name; p++) {
6214                 if (p->wrapper == NULL)
6215                         continue;
6216                 ptr = slotptr(type, p->offset);
6217                 if (!ptr || !*ptr)
6218                         continue;
6219                 if (PyDict_GetItem(dict, p->name_strobj))
6220                         continue;
6221                 if (*ptr == PyObject_HashNotImplemented) {
6222                         /* Classes may prevent the inheritance of the tp_hash
6223                            slot by storing PyObject_HashNotImplemented in it. Make it
6224                            visible as a None value for the __hash__ attribute. */
6225                         if (PyDict_SetItem(dict, p->name_strobj, Py_None) < 0)
6226                                 return -1;
6227                 }
6228                 else {
6229                         descr = PyDescr_NewWrapper(type, p, *ptr);
6230                         if (descr == NULL)
6231                                 return -1;
6232                         if (PyDict_SetItem(dict, p->name_strobj, descr) < 0)
6233                                 return -1;
6234                         Py_DECREF(descr);
6235                 }
6236         }
6237         if (type->tp_new != NULL) {
6238                 if (add_tp_new_wrapper(type) < 0)
6239                         return -1;
6240         }
6241         return 0;
6242 }
6243
6244
6245 /* Cooperative 'super' */
6246
6247 typedef struct {
6248         PyObject_HEAD
6249         PyTypeObject *type;
6250         PyObject *obj;
6251         PyTypeObject *obj_type;
6252 } superobject;
6253
6254 static PyMemberDef super_members[] = {
6255         {"__thisclass__", T_OBJECT, offsetof(superobject, type), READONLY,
6256          "the class invoking super()"},
6257         {"__self__",  T_OBJECT, offsetof(superobject, obj), READONLY,
6258          "the instance invoking super(); may be None"},
6259         {"__self_class__", T_OBJECT, offsetof(superobject, obj_type), READONLY,
6260          "the type of the instance invoking super(); may be None"},
6261         {0}
6262 };
6263
6264 static void
6265 super_dealloc(PyObject *self)
6266 {
6267         superobject *su = (superobject *)self;
6268
6269         _PyObject_GC_UNTRACK(self);
6270         Py_XDECREF(su->obj);
6271         Py_XDECREF(su->type);
6272         Py_XDECREF(su->obj_type);
6273         Py_TYPE(self)->tp_free(self);
6274 }
6275
6276 static PyObject *
6277 super_repr(PyObject *self)
6278 {
6279         superobject *su = (superobject *)self;
6280
6281         if (su->obj_type)
6282                 return PyString_FromFormat(
6283                         "<super: <class '%s'>, <%s object>>",
6284                         su->type ? su->type->tp_name : "NULL",
6285                         su->obj_type->tp_name);
6286         else
6287                 return PyString_FromFormat(
6288                         "<super: <class '%s'>, NULL>",
6289                         su->type ? su->type->tp_name : "NULL");
6290 }
6291
6292 static PyObject *
6293 super_getattro(PyObject *self, PyObject *name)
6294 {
6295         superobject *su = (superobject *)self;
6296         int skip = su->obj_type == NULL;
6297
6298         if (!skip) {
6299                 /* We want __class__ to return the class of the super object
6300                    (i.e. super, or a subclass), not the class of su->obj. */
6301                 skip = (PyString_Check(name) &&
6302                         PyString_GET_SIZE(name) == 9 &&
6303                         strcmp(PyString_AS_STRING(name), "__class__") == 0);
6304         }
6305
6306         if (!skip) {
6307                 PyObject *mro, *res, *tmp, *dict;
6308                 PyTypeObject *starttype;
6309                 descrgetfunc f;
6310                 Py_ssize_t i, n;
6311
6312                 starttype = su->obj_type;
6313                 mro = starttype->tp_mro;
6314
6315                 if (mro == NULL)
6316                         n = 0;
6317                 else {
6318                         assert(PyTuple_Check(mro));
6319                         n = PyTuple_GET_SIZE(mro);
6320                 }
6321                 for (i = 0; i < n; i++) {
6322                         if ((PyObject *)(su->type) == PyTuple_GET_ITEM(mro, i))
6323                                 break;
6324                 }
6325                 i++;
6326                 res = NULL;
6327                 for (; i < n; i++) {
6328                         tmp = PyTuple_GET_ITEM(mro, i);
6329                         if (PyType_Check(tmp))
6330                                 dict = ((PyTypeObject *)tmp)->tp_dict;
6331                         else if (PyClass_Check(tmp))
6332                                 dict = ((PyClassObject *)tmp)->cl_dict;
6333                         else
6334                                 continue;
6335                         res = PyDict_GetItem(dict, name);
6336                         if (res != NULL) {
6337                                 Py_INCREF(res);
6338                                 f = Py_TYPE(res)->tp_descr_get;
6339                                 if (f != NULL) {
6340                                         tmp = f(res,
6341                                                 /* Only pass 'obj' param if
6342                                                    this is instance-mode super
6343                                                    (See SF ID #743627)
6344                                                 */
6345                                                 (su->obj == (PyObject *)
6346                                                             su->obj_type
6347                                                         ? (PyObject *)NULL
6348                                                         : su->obj),
6349                                                 (PyObject *)starttype);
6350                                         Py_DECREF(res);
6351                                         res = tmp;
6352                                 }
6353                                 return res;
6354                         }
6355                 }
6356         }
6357         return PyObject_GenericGetAttr(self, name);
6358 }
6359
6360 static PyTypeObject *
6361 supercheck(PyTypeObject *type, PyObject *obj)
6362 {
6363         /* Check that a super() call makes sense.  Return a type object.
6364
6365            obj can be a new-style class, or an instance of one:
6366
6367            - If it is a class, it must be a subclass of 'type'.  This case is
6368              used for class methods; the return value is obj.
6369
6370            - If it is an instance, it must be an instance of 'type'.  This is
6371              the normal case; the return value is obj.__class__.
6372
6373            But... when obj is an instance, we want to allow for the case where
6374            Py_TYPE(obj) is not a subclass of type, but obj.__class__ is!
6375            This will allow using super() with a proxy for obj.
6376         */
6377
6378         /* Check for first bullet above (special case) */
6379         if (PyType_Check(obj) && PyType_IsSubtype((PyTypeObject *)obj, type)) {
6380                 Py_INCREF(obj);
6381                 return (PyTypeObject *)obj;
6382         }
6383
6384         /* Normal case */
6385         if (PyType_IsSubtype(Py_TYPE(obj), type)) {
6386                 Py_INCREF(Py_TYPE(obj));
6387                 return Py_TYPE(obj);
6388         }
6389         else {
6390                 /* Try the slow way */
6391                 static PyObject *class_str = NULL;
6392                 PyObject *class_attr;
6393
6394                 if (class_str == NULL) {
6395                         class_str = PyString_FromString("__class__");
6396                         if (class_str == NULL)
6397                                 return NULL;
6398                 }
6399
6400                 class_attr = PyObject_GetAttr(obj, class_str);
6401
6402                 if (class_attr != NULL &&
6403                     PyType_Check(class_attr) &&
6404                     (PyTypeObject *)class_attr != Py_TYPE(obj))
6405                 {
6406                         int ok = PyType_IsSubtype(
6407                                 (PyTypeObject *)class_attr, type);
6408                         if (ok)
6409                                 return (PyTypeObject *)class_attr;
6410                 }
6411
6412                 if (class_attr == NULL)
6413                         PyErr_Clear();
6414                 else
6415                         Py_DECREF(class_attr);
6416         }
6417
6418         PyErr_SetString(PyExc_TypeError,
6419                         "super(type, obj): "
6420                         "obj must be an instance or subtype of type");
6421         return NULL;
6422 }
6423
6424 static PyObject *
6425 super_descr_get(PyObject *self, PyObject *obj, PyObject *type)
6426 {
6427         superobject *su = (superobject *)self;
6428         superobject *newobj;
6429
6430         if (obj == NULL || obj == Py_None || su->obj != NULL) {
6431                 /* Not binding to an object, or already bound */
6432                 Py_INCREF(self);
6433                 return self;
6434         }
6435         if (Py_TYPE(su) != &PySuper_Type)
6436                 /* If su is an instance of a (strict) subclass of super,
6437                    call its type */
6438                 return PyObject_CallFunctionObjArgs((PyObject *)Py_TYPE(su),
6439                                                     su->type, obj, NULL);
6440         else {
6441                 /* Inline the common case */
6442                 PyTypeObject *obj_type = supercheck(su->type, obj);
6443                 if (obj_type == NULL)
6444                         return NULL;
6445                 newobj = (superobject *)PySuper_Type.tp_new(&PySuper_Type,
6446                                                          NULL, NULL);
6447                 if (newobj == NULL)
6448                         return NULL;
6449                 Py_INCREF(su->type);
6450                 Py_INCREF(obj);
6451                 newobj->type = su->type;
6452                 newobj->obj = obj;
6453                 newobj->obj_type = obj_type;
6454                 return (PyObject *)newobj;
6455         }
6456 }
6457
6458 static int
6459 super_init(PyObject *self, PyObject *args, PyObject *kwds)
6460 {
6461         superobject *su = (superobject *)self;
6462         PyTypeObject *type;
6463         PyObject *obj = NULL;
6464         PyTypeObject *obj_type = NULL;
6465
6466         if (!_PyArg_NoKeywords("super", kwds))
6467                 return -1;
6468         if (!PyArg_ParseTuple(args, "O!|O:super", &PyType_Type, &type, &obj))
6469                 return -1;
6470         if (obj == Py_None)
6471                 obj = NULL;
6472         if (obj != NULL) {
6473                 obj_type = supercheck(type, obj);
6474                 if (obj_type == NULL)
6475                         return -1;
6476                 Py_INCREF(obj);
6477         }
6478         Py_INCREF(type);
6479         su->type = type;
6480         su->obj = obj;
6481         su->obj_type = obj_type;
6482         return 0;
6483 }
6484
6485 PyDoc_STRVAR(super_doc,
6486 "super(type) -> unbound super object\n"
6487 "super(type, obj) -> bound super object; requires isinstance(obj, type)\n"
6488 "super(type, type2) -> bound super object; requires issubclass(type2, type)\n"
6489 "Typical use to call a cooperative superclass method:\n"
6490 "class C(B):\n"
6491 "    def meth(self, arg):\n"
6492 "        super(C, self).meth(arg)");
6493
6494 static int
6495 super_traverse(PyObject *self, visitproc visit, void *arg)
6496 {
6497         superobject *su = (superobject *)self;
6498
6499         Py_VISIT(su->obj);
6500         Py_VISIT(su->type);
6501         Py_VISIT(su->obj_type);
6502
6503         return 0;
6504 }
6505
6506 PyTypeObject PySuper_Type = {
6507         PyVarObject_HEAD_INIT(&PyType_Type, 0)
6508         "super",                                /* tp_name */
6509         sizeof(superobject),                    /* tp_basicsize */
6510         0,                                      /* tp_itemsize */
6511         /* methods */
6512         super_dealloc,                          /* tp_dealloc */
6513         0,                                      /* tp_print */
6514         0,                                      /* tp_getattr */
6515         0,                                      /* tp_setattr */
6516         0,                                      /* tp_compare */
6517         super_repr,                             /* tp_repr */
6518         0,                                      /* tp_as_number */
6519         0,                                      /* tp_as_sequence */
6520         0,                                      /* tp_as_mapping */
6521         0,                                      /* tp_hash */
6522         0,                                      /* tp_call */
6523         0,                                      /* tp_str */
6524         super_getattro,                         /* tp_getattro */
6525         0,                                      /* tp_setattro */
6526         0,                                      /* tp_as_buffer */
6527         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
6528                 Py_TPFLAGS_BASETYPE,            /* tp_flags */
6529         super_doc,                              /* tp_doc */
6530         super_traverse,                         /* tp_traverse */
6531         0,                                      /* tp_clear */
6532         0,                                      /* tp_richcompare */
6533         0,                                      /* tp_weaklistoffset */
6534         0,                                      /* tp_iter */
6535         0,                                      /* tp_iternext */
6536         0,                                      /* tp_methods */
6537         super_members,                          /* tp_members */
6538         0,                                      /* tp_getset */
6539         0,                                      /* tp_base */
6540         0,                                      /* tp_dict */
6541         super_descr_get,                        /* tp_descr_get */
6542         0,                                      /* tp_descr_set */
6543         0,                                      /* tp_dictoffset */
6544         super_init,                             /* tp_init */
6545         PyType_GenericAlloc,                    /* tp_alloc */
6546         PyType_GenericNew,                      /* tp_new */
6547         PyObject_GC_Del,                        /* tp_free */
6548 };