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 int
3652 overrides_name(PyTypeObject *type, char *name)
3653 {
3654         PyObject *dict = type->tp_dict;
3655
3656         assert(dict != NULL);
3657         if (PyDict_GetItemString(dict, name) != NULL) {
3658                 return 1;
3659         }
3660         return 0;
3661 }
3662
3663 #define OVERRIDES_HASH(x)       overrides_name(x, "__hash__")
3664 #define OVERRIDES_CMP(x)        overrides_name(x, "__cmp__")
3665 #define OVERRIDES_EQ(x)         overrides_name(x, "__eq__")
3666
3667 static void
3668 inherit_slots(PyTypeObject *type, PyTypeObject *base)
3669 {
3670         PyTypeObject *basebase;
3671
3672 #undef SLOTDEFINED
3673 #undef COPYSLOT
3674 #undef COPYNUM
3675 #undef COPYSEQ
3676 #undef COPYMAP
3677 #undef COPYBUF
3678
3679 #define SLOTDEFINED(SLOT) \
3680         (base->SLOT != 0 && \
3681          (basebase == NULL || base->SLOT != basebase->SLOT))
3682
3683 #define COPYSLOT(SLOT) \
3684         if (!type->SLOT && SLOTDEFINED(SLOT)) type->SLOT = base->SLOT
3685
3686 #define COPYNUM(SLOT) COPYSLOT(tp_as_number->SLOT)
3687 #define COPYSEQ(SLOT) COPYSLOT(tp_as_sequence->SLOT)
3688 #define COPYMAP(SLOT) COPYSLOT(tp_as_mapping->SLOT)
3689 #define COPYBUF(SLOT) COPYSLOT(tp_as_buffer->SLOT)
3690
3691         /* This won't inherit indirect slots (from tp_as_number etc.)
3692            if type doesn't provide the space. */
3693
3694         if (type->tp_as_number != NULL && base->tp_as_number != NULL) {
3695                 basebase = base->tp_base;
3696                 if (basebase->tp_as_number == NULL)
3697                         basebase = NULL;
3698                 COPYNUM(nb_add);
3699                 COPYNUM(nb_subtract);
3700                 COPYNUM(nb_multiply);
3701                 COPYNUM(nb_divide);
3702                 COPYNUM(nb_remainder);
3703                 COPYNUM(nb_divmod);
3704                 COPYNUM(nb_power);
3705                 COPYNUM(nb_negative);
3706                 COPYNUM(nb_positive);
3707                 COPYNUM(nb_absolute);
3708                 COPYNUM(nb_nonzero);
3709                 COPYNUM(nb_invert);
3710                 COPYNUM(nb_lshift);
3711                 COPYNUM(nb_rshift);
3712                 COPYNUM(nb_and);
3713                 COPYNUM(nb_xor);
3714                 COPYNUM(nb_or);
3715                 COPYNUM(nb_coerce);
3716                 COPYNUM(nb_int);
3717                 COPYNUM(nb_long);
3718                 COPYNUM(nb_float);
3719                 COPYNUM(nb_oct);
3720                 COPYNUM(nb_hex);
3721                 COPYNUM(nb_inplace_add);
3722                 COPYNUM(nb_inplace_subtract);
3723                 COPYNUM(nb_inplace_multiply);
3724                 COPYNUM(nb_inplace_divide);
3725                 COPYNUM(nb_inplace_remainder);
3726                 COPYNUM(nb_inplace_power);
3727                 COPYNUM(nb_inplace_lshift);
3728                 COPYNUM(nb_inplace_rshift);
3729                 COPYNUM(nb_inplace_and);
3730                 COPYNUM(nb_inplace_xor);
3731                 COPYNUM(nb_inplace_or);
3732                 if (base->tp_flags & Py_TPFLAGS_CHECKTYPES) {
3733                         COPYNUM(nb_true_divide);
3734                         COPYNUM(nb_floor_divide);
3735                         COPYNUM(nb_inplace_true_divide);
3736                         COPYNUM(nb_inplace_floor_divide);
3737                 }
3738                 if (base->tp_flags & Py_TPFLAGS_HAVE_INDEX) {
3739                         COPYNUM(nb_index);
3740                 }
3741         }
3742
3743         if (type->tp_as_sequence != NULL && base->tp_as_sequence != NULL) {
3744                 basebase = base->tp_base;
3745                 if (basebase->tp_as_sequence == NULL)
3746                         basebase = NULL;
3747                 COPYSEQ(sq_length);
3748                 COPYSEQ(sq_concat);
3749                 COPYSEQ(sq_repeat);
3750                 COPYSEQ(sq_item);
3751                 COPYSEQ(sq_slice);
3752                 COPYSEQ(sq_ass_item);
3753                 COPYSEQ(sq_ass_slice);
3754                 COPYSEQ(sq_contains);
3755                 COPYSEQ(sq_inplace_concat);
3756                 COPYSEQ(sq_inplace_repeat);
3757         }
3758
3759         if (type->tp_as_mapping != NULL && base->tp_as_mapping != NULL) {
3760                 basebase = base->tp_base;
3761                 if (basebase->tp_as_mapping == NULL)
3762                         basebase = NULL;
3763                 COPYMAP(mp_length);
3764                 COPYMAP(mp_subscript);
3765                 COPYMAP(mp_ass_subscript);
3766         }
3767
3768         if (type->tp_as_buffer != NULL && base->tp_as_buffer != NULL) {
3769                 basebase = base->tp_base;
3770                 if (basebase->tp_as_buffer == NULL)
3771                         basebase = NULL;
3772                 COPYBUF(bf_getreadbuffer);
3773                 COPYBUF(bf_getwritebuffer);
3774                 COPYBUF(bf_getsegcount);
3775                 COPYBUF(bf_getcharbuffer);
3776                 COPYBUF(bf_getbuffer);
3777                 COPYBUF(bf_releasebuffer);
3778         }
3779
3780         basebase = base->tp_base;
3781
3782         COPYSLOT(tp_dealloc);
3783         COPYSLOT(tp_print);
3784         if (type->tp_getattr == NULL && type->tp_getattro == NULL) {
3785                 type->tp_getattr = base->tp_getattr;
3786                 type->tp_getattro = base->tp_getattro;
3787         }
3788         if (type->tp_setattr == NULL && type->tp_setattro == NULL) {
3789                 type->tp_setattr = base->tp_setattr;
3790                 type->tp_setattro = base->tp_setattro;
3791         }
3792         /* tp_compare see tp_richcompare */
3793         COPYSLOT(tp_repr);
3794         /* tp_hash see tp_richcompare */
3795         COPYSLOT(tp_call);
3796         COPYSLOT(tp_str);
3797         if (type->tp_flags & base->tp_flags & Py_TPFLAGS_HAVE_RICHCOMPARE) {
3798                 if (type->tp_compare == NULL &&
3799                     type->tp_richcompare == NULL &&
3800                     type->tp_hash == NULL)
3801                 {
3802                         type->tp_compare = base->tp_compare;
3803                         type->tp_richcompare = base->tp_richcompare;
3804                         type->tp_hash = base->tp_hash;
3805                         /* Check for changes to inherited methods in Py3k*/
3806                         if (Py_Py3kWarningFlag) {
3807                                 if (base->tp_hash &&
3808                                                 (base->tp_hash != PyObject_HashNotImplemented) &&
3809                                                 !OVERRIDES_HASH(type)) {
3810                                         if (OVERRIDES_CMP(type)) {
3811                                                 PyErr_WarnPy3k("Overriding "
3812                                                   "__cmp__ blocks inheritance "
3813                                                   "of __hash__ in 3.x",
3814                                                   1);
3815                                         }
3816                                         if (OVERRIDES_EQ(type)) {
3817                                                 PyErr_WarnPy3k("Overriding "
3818                                                   "__eq__ blocks inheritance "
3819                                                   "of __hash__ in 3.x",
3820                                                   1);
3821                                         }
3822                                 }
3823                         }
3824                 }
3825         }
3826         else {
3827                 COPYSLOT(tp_compare);
3828         }
3829         if (type->tp_flags & base->tp_flags & Py_TPFLAGS_HAVE_ITER) {
3830                 COPYSLOT(tp_iter);
3831                 COPYSLOT(tp_iternext);
3832         }
3833         if (type->tp_flags & base->tp_flags & Py_TPFLAGS_HAVE_CLASS) {
3834                 COPYSLOT(tp_descr_get);
3835                 COPYSLOT(tp_descr_set);
3836                 COPYSLOT(tp_dictoffset);
3837                 COPYSLOT(tp_init);
3838                 COPYSLOT(tp_alloc);
3839                 COPYSLOT(tp_is_gc);
3840                 if ((type->tp_flags & Py_TPFLAGS_HAVE_GC) ==
3841                     (base->tp_flags & Py_TPFLAGS_HAVE_GC)) {
3842                         /* They agree about gc. */
3843                         COPYSLOT(tp_free);
3844                 }
3845                 else if ((type->tp_flags & Py_TPFLAGS_HAVE_GC) &&
3846                          type->tp_free == NULL &&
3847                          base->tp_free == _PyObject_Del) {
3848                         /* A bit of magic to plug in the correct default
3849                          * tp_free function when a derived class adds gc,
3850                          * didn't define tp_free, and the base uses the
3851                          * default non-gc tp_free.
3852                          */
3853                         type->tp_free = PyObject_GC_Del;
3854                 }
3855                 /* else they didn't agree about gc, and there isn't something
3856                  * obvious to be done -- the type is on its own.
3857                  */
3858         }
3859 }
3860
3861 static int add_operators(PyTypeObject *);
3862
3863 int
3864 PyType_Ready(PyTypeObject *type)
3865 {
3866         PyObject *dict, *bases;
3867         PyTypeObject *base;
3868         Py_ssize_t i, n;
3869
3870         if (type->tp_flags & Py_TPFLAGS_READY) {
3871                 assert(type->tp_dict != NULL);
3872                 return 0;
3873         }
3874         assert((type->tp_flags & Py_TPFLAGS_READYING) == 0);
3875
3876         type->tp_flags |= Py_TPFLAGS_READYING;
3877
3878 #ifdef Py_TRACE_REFS
3879         /* PyType_Ready is the closest thing we have to a choke point
3880          * for type objects, so is the best place I can think of to try
3881          * to get type objects into the doubly-linked list of all objects.
3882          * Still, not all type objects go thru PyType_Ready.
3883          */
3884         _Py_AddToAllObjects((PyObject *)type, 0);
3885 #endif
3886
3887         /* Initialize tp_base (defaults to BaseObject unless that's us) */
3888         base = type->tp_base;
3889         if (base == NULL && type != &PyBaseObject_Type) {
3890                 base = type->tp_base = &PyBaseObject_Type;
3891                 Py_INCREF(base);
3892         }
3893
3894         /* Now the only way base can still be NULL is if type is
3895          * &PyBaseObject_Type.
3896          */
3897
3898         /* Initialize the base class */
3899         if (base && base->tp_dict == NULL) {
3900                 if (PyType_Ready(base) < 0)
3901                         goto error;
3902         }
3903
3904         /* Initialize ob_type if NULL.  This means extensions that want to be
3905            compilable separately on Windows can call PyType_Ready() instead of
3906            initializing the ob_type field of their type objects. */
3907         /* The test for base != NULL is really unnecessary, since base is only
3908            NULL when type is &PyBaseObject_Type, and we know its ob_type is
3909            not NULL (it's initialized to &PyType_Type).  But coverity doesn't
3910            know that. */
3911         if (Py_TYPE(type) == NULL && base != NULL)
3912                 Py_TYPE(type) = Py_TYPE(base);
3913
3914         /* Initialize tp_bases */
3915         bases = type->tp_bases;
3916         if (bases == NULL) {
3917                 if (base == NULL)
3918                         bases = PyTuple_New(0);
3919                 else
3920                         bases = PyTuple_Pack(1, base);
3921                 if (bases == NULL)
3922                         goto error;
3923                 type->tp_bases = bases;
3924         }
3925
3926         /* Initialize tp_dict */
3927         dict = type->tp_dict;
3928         if (dict == NULL) {
3929                 dict = PyDict_New();
3930                 if (dict == NULL)
3931                         goto error;
3932                 type->tp_dict = dict;
3933         }
3934
3935         /* Add type-specific descriptors to tp_dict */
3936         if (add_operators(type) < 0)
3937                 goto error;
3938         if (type->tp_methods != NULL) {
3939                 if (add_methods(type, type->tp_methods) < 0)
3940                         goto error;
3941         }
3942         if (type->tp_members != NULL) {
3943                 if (add_members(type, type->tp_members) < 0)
3944                         goto error;
3945         }
3946         if (type->tp_getset != NULL) {
3947                 if (add_getset(type, type->tp_getset) < 0)
3948                         goto error;
3949         }
3950
3951         /* Calculate method resolution order */
3952         if (mro_internal(type) < 0) {
3953                 goto error;
3954         }
3955
3956         /* Inherit special flags from dominant base */
3957         if (type->tp_base != NULL)
3958                 inherit_special(type, type->tp_base);
3959
3960         /* Initialize tp_dict properly */
3961         bases = type->tp_mro;
3962         assert(bases != NULL);
3963         assert(PyTuple_Check(bases));
3964         n = PyTuple_GET_SIZE(bases);
3965         for (i = 1; i < n; i++) {
3966                 PyObject *b = PyTuple_GET_ITEM(bases, i);
3967                 if (PyType_Check(b))
3968                         inherit_slots(type, (PyTypeObject *)b);
3969         }
3970
3971         /* Sanity check for tp_free. */
3972         if (PyType_IS_GC(type) && (type->tp_flags & Py_TPFLAGS_BASETYPE) &&
3973             (type->tp_free == NULL || type->tp_free == PyObject_Del)) {
3974                 /* This base class needs to call tp_free, but doesn't have
3975                  * one, or its tp_free is for non-gc'ed objects.
3976                  */
3977                 PyErr_Format(PyExc_TypeError, "type '%.100s' participates in "
3978                              "gc and is a base type but has inappropriate "
3979                              "tp_free slot",
3980                              type->tp_name);
3981                 goto error;
3982         }
3983
3984         /* if the type dictionary doesn't contain a __doc__, set it from
3985            the tp_doc slot.
3986          */
3987         if (PyDict_GetItemString(type->tp_dict, "__doc__") == NULL) {
3988                 if (type->tp_doc != NULL) {
3989                         PyObject *doc = PyString_FromString(type->tp_doc);
3990                         if (doc == NULL)
3991                                 goto error;
3992                         PyDict_SetItemString(type->tp_dict, "__doc__", doc);
3993                         Py_DECREF(doc);
3994                 } else {
3995                         PyDict_SetItemString(type->tp_dict,
3996                                              "__doc__", Py_None);
3997                 }
3998         }
3999
4000         /* Some more special stuff */
4001         base = type->tp_base;
4002         if (base != NULL) {
4003                 if (type->tp_as_number == NULL)
4004                         type->tp_as_number = base->tp_as_number;
4005                 if (type->tp_as_sequence == NULL)
4006                         type->tp_as_sequence = base->tp_as_sequence;
4007                 if (type->tp_as_mapping == NULL)
4008                         type->tp_as_mapping = base->tp_as_mapping;
4009                 if (type->tp_as_buffer == NULL)
4010                         type->tp_as_buffer = base->tp_as_buffer;
4011         }
4012
4013         /* Link into each base class's list of subclasses */
4014         bases = type->tp_bases;
4015         n = PyTuple_GET_SIZE(bases);
4016         for (i = 0; i < n; i++) {
4017                 PyObject *b = PyTuple_GET_ITEM(bases, i);
4018                 if (PyType_Check(b) &&
4019                     add_subclass((PyTypeObject *)b, type) < 0)
4020                         goto error;
4021         }
4022
4023         /* All done -- set the ready flag */
4024         assert(type->tp_dict != NULL);
4025         type->tp_flags =
4026                 (type->tp_flags & ~Py_TPFLAGS_READYING) | Py_TPFLAGS_READY;
4027         return 0;
4028
4029   error:
4030         type->tp_flags &= ~Py_TPFLAGS_READYING;
4031         return -1;
4032 }
4033
4034 static int
4035 add_subclass(PyTypeObject *base, PyTypeObject *type)
4036 {
4037         Py_ssize_t i;
4038         int result;
4039         PyObject *list, *ref, *newobj;
4040
4041         list = base->tp_subclasses;
4042         if (list == NULL) {
4043                 base->tp_subclasses = list = PyList_New(0);
4044                 if (list == NULL)
4045                         return -1;
4046         }
4047         assert(PyList_Check(list));
4048         newobj = PyWeakref_NewRef((PyObject *)type, NULL);
4049         i = PyList_GET_SIZE(list);
4050         while (--i >= 0) {
4051                 ref = PyList_GET_ITEM(list, i);
4052                 assert(PyWeakref_CheckRef(ref));
4053                 if (PyWeakref_GET_OBJECT(ref) == Py_None)
4054                         return PyList_SetItem(list, i, newobj);
4055         }
4056         result = PyList_Append(list, newobj);
4057         Py_DECREF(newobj);
4058         return result;
4059 }
4060
4061 static void
4062 remove_subclass(PyTypeObject *base, PyTypeObject *type)
4063 {
4064         Py_ssize_t i;
4065         PyObject *list, *ref;
4066
4067         list = base->tp_subclasses;
4068         if (list == NULL) {
4069                 return;
4070         }
4071         assert(PyList_Check(list));
4072         i = PyList_GET_SIZE(list);
4073         while (--i >= 0) {
4074                 ref = PyList_GET_ITEM(list, i);
4075                 assert(PyWeakref_CheckRef(ref));
4076                 if (PyWeakref_GET_OBJECT(ref) == (PyObject*)type) {
4077                         /* this can't fail, right? */
4078                         PySequence_DelItem(list, i);
4079                         return;
4080                 }
4081         }
4082 }
4083
4084 static int
4085 check_num_args(PyObject *ob, int n)
4086 {
4087         if (!PyTuple_CheckExact(ob)) {
4088                 PyErr_SetString(PyExc_SystemError,
4089                     "PyArg_UnpackTuple() argument list is not a tuple");
4090                 return 0;
4091         }
4092         if (n == PyTuple_GET_SIZE(ob))
4093                 return 1;
4094         PyErr_Format(
4095             PyExc_TypeError,
4096             "expected %d arguments, got %zd", n, PyTuple_GET_SIZE(ob));
4097         return 0;
4098 }
4099
4100 /* Generic wrappers for overloadable 'operators' such as __getitem__ */
4101
4102 /* There's a wrapper *function* for each distinct function typedef used
4103    for type object slots (e.g. binaryfunc, ternaryfunc, etc.).  There's a
4104    wrapper *table* for each distinct operation (e.g. __len__, __add__).
4105    Most tables have only one entry; the tables for binary operators have two
4106    entries, one regular and one with reversed arguments. */
4107
4108 static PyObject *
4109 wrap_lenfunc(PyObject *self, PyObject *args, void *wrapped)
4110 {
4111         lenfunc func = (lenfunc)wrapped;
4112         Py_ssize_t res;
4113
4114         if (!check_num_args(args, 0))
4115                 return NULL;
4116         res = (*func)(self);
4117         if (res == -1 && PyErr_Occurred())
4118                 return NULL;
4119         return PyInt_FromLong((long)res);
4120 }
4121
4122 static PyObject *
4123 wrap_inquirypred(PyObject *self, PyObject *args, void *wrapped)
4124 {
4125         inquiry func = (inquiry)wrapped;
4126         int res;
4127
4128         if (!check_num_args(args, 0))
4129                 return NULL;
4130         res = (*func)(self);
4131         if (res == -1 && PyErr_Occurred())
4132                 return NULL;
4133         return PyBool_FromLong((long)res);
4134 }
4135
4136 static PyObject *
4137 wrap_binaryfunc(PyObject *self, PyObject *args, void *wrapped)
4138 {
4139         binaryfunc func = (binaryfunc)wrapped;
4140         PyObject *other;
4141
4142         if (!check_num_args(args, 1))
4143                 return NULL;
4144         other = PyTuple_GET_ITEM(args, 0);
4145         return (*func)(self, other);
4146 }
4147
4148 static PyObject *
4149 wrap_binaryfunc_l(PyObject *self, PyObject *args, void *wrapped)
4150 {
4151         binaryfunc func = (binaryfunc)wrapped;
4152         PyObject *other;
4153
4154         if (!check_num_args(args, 1))
4155                 return NULL;
4156         other = PyTuple_GET_ITEM(args, 0);
4157         if (!(self->ob_type->tp_flags & Py_TPFLAGS_CHECKTYPES) &&
4158             !PyType_IsSubtype(other->ob_type, self->ob_type)) {
4159                 Py_INCREF(Py_NotImplemented);
4160                 return Py_NotImplemented;
4161         }
4162         return (*func)(self, other);
4163 }
4164
4165 static PyObject *
4166 wrap_binaryfunc_r(PyObject *self, PyObject *args, void *wrapped)
4167 {
4168         binaryfunc func = (binaryfunc)wrapped;
4169         PyObject *other;
4170
4171         if (!check_num_args(args, 1))
4172                 return NULL;
4173         other = PyTuple_GET_ITEM(args, 0);
4174         if (!(self->ob_type->tp_flags & Py_TPFLAGS_CHECKTYPES) &&
4175             !PyType_IsSubtype(other->ob_type, self->ob_type)) {
4176                 Py_INCREF(Py_NotImplemented);
4177                 return Py_NotImplemented;
4178         }
4179         return (*func)(other, self);
4180 }
4181
4182 static PyObject *
4183 wrap_coercefunc(PyObject *self, PyObject *args, void *wrapped)
4184 {
4185         coercion func = (coercion)wrapped;
4186         PyObject *other, *res;
4187         int ok;
4188
4189         if (!check_num_args(args, 1))
4190                 return NULL;
4191         other = PyTuple_GET_ITEM(args, 0);
4192         ok = func(&self, &other);
4193         if (ok < 0)
4194                 return NULL;
4195         if (ok > 0) {
4196                 Py_INCREF(Py_NotImplemented);
4197                 return Py_NotImplemented;
4198         }
4199         res = PyTuple_New(2);
4200         if (res == NULL) {
4201                 Py_DECREF(self);
4202                 Py_DECREF(other);
4203                 return NULL;
4204         }
4205         PyTuple_SET_ITEM(res, 0, self);
4206         PyTuple_SET_ITEM(res, 1, other);
4207         return res;
4208 }
4209
4210 static PyObject *
4211 wrap_ternaryfunc(PyObject *self, PyObject *args, void *wrapped)
4212 {
4213         ternaryfunc func = (ternaryfunc)wrapped;
4214         PyObject *other;
4215         PyObject *third = Py_None;
4216
4217         /* Note: This wrapper only works for __pow__() */
4218
4219         if (!PyArg_UnpackTuple(args, "", 1, 2, &other, &third))
4220                 return NULL;
4221         return (*func)(self, other, third);
4222 }
4223
4224 static PyObject *
4225 wrap_ternaryfunc_r(PyObject *self, PyObject *args, void *wrapped)
4226 {
4227         ternaryfunc func = (ternaryfunc)wrapped;
4228         PyObject *other;
4229         PyObject *third = Py_None;
4230
4231         /* Note: This wrapper only works for __pow__() */
4232
4233         if (!PyArg_UnpackTuple(args, "", 1, 2, &other, &third))
4234                 return NULL;
4235         return (*func)(other, self, third);
4236 }
4237
4238 static PyObject *
4239 wrap_unaryfunc(PyObject *self, PyObject *args, void *wrapped)
4240 {
4241         unaryfunc func = (unaryfunc)wrapped;
4242
4243         if (!check_num_args(args, 0))
4244                 return NULL;
4245         return (*func)(self);
4246 }
4247
4248 static PyObject *
4249 wrap_indexargfunc(PyObject *self, PyObject *args, void *wrapped)
4250 {
4251         ssizeargfunc func = (ssizeargfunc)wrapped;
4252         PyObject* o;
4253         Py_ssize_t i;
4254
4255         if (!PyArg_UnpackTuple(args, "", 1, 1, &o))
4256                 return NULL;
4257         i = PyNumber_AsSsize_t(o, PyExc_OverflowError);
4258         if (i == -1 && PyErr_Occurred())
4259                 return NULL;
4260         return (*func)(self, i);
4261 }
4262
4263 static Py_ssize_t
4264 getindex(PyObject *self, PyObject *arg)
4265 {
4266         Py_ssize_t i;
4267
4268         i = PyNumber_AsSsize_t(arg, PyExc_OverflowError);
4269         if (i == -1 && PyErr_Occurred())
4270                 return -1;
4271         if (i < 0) {
4272                 PySequenceMethods *sq = Py_TYPE(self)->tp_as_sequence;
4273                 if (sq && sq->sq_length) {
4274                         Py_ssize_t n = (*sq->sq_length)(self);
4275                         if (n < 0)
4276                                 return -1;
4277                         i += n;
4278                 }
4279         }
4280         return i;
4281 }
4282
4283 static PyObject *
4284 wrap_sq_item(PyObject *self, PyObject *args, void *wrapped)
4285 {
4286         ssizeargfunc func = (ssizeargfunc)wrapped;
4287         PyObject *arg;
4288         Py_ssize_t i;
4289
4290         if (PyTuple_GET_SIZE(args) == 1) {
4291                 arg = PyTuple_GET_ITEM(args, 0);
4292                 i = getindex(self, arg);
4293                 if (i == -1 && PyErr_Occurred())
4294                         return NULL;
4295                 return (*func)(self, i);
4296         }
4297         check_num_args(args, 1);
4298         assert(PyErr_Occurred());
4299         return NULL;
4300 }
4301
4302 static PyObject *
4303 wrap_ssizessizeargfunc(PyObject *self, PyObject *args, void *wrapped)
4304 {
4305         ssizessizeargfunc func = (ssizessizeargfunc)wrapped;
4306         Py_ssize_t i, j;
4307
4308         if (!PyArg_ParseTuple(args, "nn", &i, &j))
4309                 return NULL;
4310         return (*func)(self, i, j);
4311 }
4312
4313 static PyObject *
4314 wrap_sq_setitem(PyObject *self, PyObject *args, void *wrapped)
4315 {
4316         ssizeobjargproc func = (ssizeobjargproc)wrapped;
4317         Py_ssize_t i;
4318         int res;
4319         PyObject *arg, *value;
4320
4321         if (!PyArg_UnpackTuple(args, "", 2, 2, &arg, &value))
4322                 return NULL;
4323         i = getindex(self, arg);
4324         if (i == -1 && PyErr_Occurred())
4325                 return NULL;
4326         res = (*func)(self, i, value);
4327         if (res == -1 && PyErr_Occurred())
4328                 return NULL;
4329         Py_INCREF(Py_None);
4330         return Py_None;
4331 }
4332
4333 static PyObject *
4334 wrap_sq_delitem(PyObject *self, PyObject *args, void *wrapped)
4335 {
4336         ssizeobjargproc func = (ssizeobjargproc)wrapped;
4337         Py_ssize_t i;
4338         int res;
4339         PyObject *arg;
4340
4341         if (!check_num_args(args, 1))
4342                 return NULL;
4343         arg = PyTuple_GET_ITEM(args, 0);
4344         i = getindex(self, arg);
4345         if (i == -1 && PyErr_Occurred())
4346                 return NULL;
4347         res = (*func)(self, i, NULL);
4348         if (res == -1 && PyErr_Occurred())
4349                 return NULL;
4350         Py_INCREF(Py_None);
4351         return Py_None;
4352 }
4353
4354 static PyObject *
4355 wrap_ssizessizeobjargproc(PyObject *self, PyObject *args, void *wrapped)
4356 {
4357         ssizessizeobjargproc func = (ssizessizeobjargproc)wrapped;
4358         Py_ssize_t i, j;
4359         int res;
4360         PyObject *value;
4361
4362         if (!PyArg_ParseTuple(args, "nnO", &i, &j, &value))
4363                 return NULL;
4364         res = (*func)(self, i, j, value);
4365         if (res == -1 && PyErr_Occurred())
4366                 return NULL;
4367         Py_INCREF(Py_None);
4368         return Py_None;
4369 }
4370
4371 static PyObject *
4372 wrap_delslice(PyObject *self, PyObject *args, void *wrapped)
4373 {
4374         ssizessizeobjargproc func = (ssizessizeobjargproc)wrapped;
4375         Py_ssize_t i, j;
4376         int res;
4377
4378         if (!PyArg_ParseTuple(args, "nn", &i, &j))
4379                 return NULL;
4380         res = (*func)(self, i, j, NULL);
4381         if (res == -1 && PyErr_Occurred())
4382                 return NULL;
4383         Py_INCREF(Py_None);
4384         return Py_None;
4385 }
4386
4387 /* XXX objobjproc is a misnomer; should be objargpred */
4388 static PyObject *
4389 wrap_objobjproc(PyObject *self, PyObject *args, void *wrapped)
4390 {
4391         objobjproc func = (objobjproc)wrapped;
4392         int res;
4393         PyObject *value;
4394
4395         if (!check_num_args(args, 1))
4396                 return NULL;
4397         value = PyTuple_GET_ITEM(args, 0);
4398         res = (*func)(self, value);
4399         if (res == -1 && PyErr_Occurred())
4400                 return NULL;
4401         else
4402                 return PyBool_FromLong(res);
4403 }
4404
4405 static PyObject *
4406 wrap_objobjargproc(PyObject *self, PyObject *args, void *wrapped)
4407 {
4408         objobjargproc func = (objobjargproc)wrapped;
4409         int res;
4410         PyObject *key, *value;
4411
4412         if (!PyArg_UnpackTuple(args, "", 2, 2, &key, &value))
4413                 return NULL;
4414         res = (*func)(self, key, value);
4415         if (res == -1 && PyErr_Occurred())
4416                 return NULL;
4417         Py_INCREF(Py_None);
4418         return Py_None;
4419 }
4420
4421 static PyObject *
4422 wrap_delitem(PyObject *self, PyObject *args, void *wrapped)
4423 {
4424         objobjargproc func = (objobjargproc)wrapped;
4425         int res;
4426         PyObject *key;
4427
4428         if (!check_num_args(args, 1))
4429                 return NULL;
4430         key = PyTuple_GET_ITEM(args, 0);
4431         res = (*func)(self, key, NULL);
4432         if (res == -1 && PyErr_Occurred())
4433                 return NULL;
4434         Py_INCREF(Py_None);
4435         return Py_None;
4436 }
4437
4438 static PyObject *
4439 wrap_cmpfunc(PyObject *self, PyObject *args, void *wrapped)
4440 {
4441         cmpfunc func = (cmpfunc)wrapped;
4442         int res;
4443         PyObject *other;
4444
4445         if (!check_num_args(args, 1))
4446                 return NULL;
4447         other = PyTuple_GET_ITEM(args, 0);
4448         if (Py_TYPE(other)->tp_compare != func &&
4449             !PyType_IsSubtype(Py_TYPE(other), Py_TYPE(self))) {
4450                 PyErr_Format(
4451                         PyExc_TypeError,
4452                         "%s.__cmp__(x,y) requires y to be a '%s', not a '%s'",
4453                         Py_TYPE(self)->tp_name,
4454                         Py_TYPE(self)->tp_name,
4455                         Py_TYPE(other)->tp_name);
4456                 return NULL;
4457         }
4458         res = (*func)(self, other);
4459         if (PyErr_Occurred())
4460                 return NULL;
4461         return PyInt_FromLong((long)res);
4462 }
4463
4464 /* Helper to check for object.__setattr__ or __delattr__ applied to a type.
4465    This is called the Carlo Verre hack after its discoverer. */
4466 static int
4467 hackcheck(PyObject *self, setattrofunc func, char *what)
4468 {
4469         PyTypeObject *type = Py_TYPE(self);
4470         while (type && type->tp_flags & Py_TPFLAGS_HEAPTYPE)
4471                 type = type->tp_base;
4472         /* If type is NULL now, this is a really weird type.
4473            In the spirit of backwards compatibility (?), just shut up. */
4474         if (type && type->tp_setattro != func) {
4475                 PyErr_Format(PyExc_TypeError,
4476                              "can't apply this %s to %s object",
4477                              what,
4478                              type->tp_name);
4479                 return 0;
4480         }
4481         return 1;
4482 }
4483
4484 static PyObject *
4485 wrap_setattr(PyObject *self, PyObject *args, void *wrapped)
4486 {
4487         setattrofunc func = (setattrofunc)wrapped;
4488         int res;
4489         PyObject *name, *value;
4490
4491         if (!PyArg_UnpackTuple(args, "", 2, 2, &name, &value))
4492                 return NULL;
4493         if (!hackcheck(self, func, "__setattr__"))
4494                 return NULL;
4495         res = (*func)(self, name, value);
4496         if (res < 0)
4497                 return NULL;
4498         Py_INCREF(Py_None);
4499         return Py_None;
4500 }
4501
4502 static PyObject *
4503 wrap_delattr(PyObject *self, PyObject *args, void *wrapped)
4504 {
4505         setattrofunc func = (setattrofunc)wrapped;
4506         int res;
4507         PyObject *name;
4508
4509         if (!check_num_args(args, 1))
4510                 return NULL;
4511         name = PyTuple_GET_ITEM(args, 0);
4512         if (!hackcheck(self, func, "__delattr__"))
4513                 return NULL;
4514         res = (*func)(self, name, NULL);
4515         if (res < 0)
4516                 return NULL;
4517         Py_INCREF(Py_None);
4518         return Py_None;
4519 }
4520
4521 static PyObject *
4522 wrap_hashfunc(PyObject *self, PyObject *args, void *wrapped)
4523 {
4524         hashfunc func = (hashfunc)wrapped;
4525         long res;
4526
4527         if (!check_num_args(args, 0))
4528                 return NULL;
4529         res = (*func)(self);
4530         if (res == -1 && PyErr_Occurred())
4531                 return NULL;
4532         return PyInt_FromLong(res);
4533 }
4534
4535 static PyObject *
4536 wrap_call(PyObject *self, PyObject *args, void *wrapped, PyObject *kwds)
4537 {
4538         ternaryfunc func = (ternaryfunc)wrapped;
4539
4540         return (*func)(self, args, kwds);
4541 }
4542
4543 static PyObject *
4544 wrap_richcmpfunc(PyObject *self, PyObject *args, void *wrapped, int op)
4545 {
4546         richcmpfunc func = (richcmpfunc)wrapped;
4547         PyObject *other;
4548
4549         if (!check_num_args(args, 1))
4550                 return NULL;
4551         other = PyTuple_GET_ITEM(args, 0);
4552         return (*func)(self, other, op);
4553 }
4554
4555 #undef RICHCMP_WRAPPER
4556 #define RICHCMP_WRAPPER(NAME, OP) \
4557 static PyObject * \
4558 richcmp_##NAME(PyObject *self, PyObject *args, void *wrapped) \
4559 { \
4560         return wrap_richcmpfunc(self, args, wrapped, OP); \
4561 }
4562
4563 RICHCMP_WRAPPER(lt, Py_LT)
4564 RICHCMP_WRAPPER(le, Py_LE)
4565 RICHCMP_WRAPPER(eq, Py_EQ)
4566 RICHCMP_WRAPPER(ne, Py_NE)
4567 RICHCMP_WRAPPER(gt, Py_GT)
4568 RICHCMP_WRAPPER(ge, Py_GE)
4569
4570 static PyObject *
4571 wrap_next(PyObject *self, PyObject *args, void *wrapped)
4572 {
4573         unaryfunc func = (unaryfunc)wrapped;
4574         PyObject *res;
4575
4576         if (!check_num_args(args, 0))
4577                 return NULL;
4578         res = (*func)(self);
4579         if (res == NULL && !PyErr_Occurred())
4580                 PyErr_SetNone(PyExc_StopIteration);
4581         return res;
4582 }
4583
4584 static PyObject *
4585 wrap_descr_get(PyObject *self, PyObject *args, void *wrapped)
4586 {
4587         descrgetfunc func = (descrgetfunc)wrapped;
4588         PyObject *obj;
4589         PyObject *type = NULL;
4590
4591         if (!PyArg_UnpackTuple(args, "", 1, 2, &obj, &type))
4592                 return NULL;
4593         if (obj == Py_None)
4594                 obj = NULL;
4595         if (type == Py_None)
4596                 type = NULL;
4597         if (type == NULL &&obj == NULL) {
4598                 PyErr_SetString(PyExc_TypeError,
4599                                 "__get__(None, None) is invalid");
4600                 return NULL;
4601         }
4602         return (*func)(self, obj, type);
4603 }
4604
4605 static PyObject *
4606 wrap_descr_set(PyObject *self, PyObject *args, void *wrapped)
4607 {
4608         descrsetfunc func = (descrsetfunc)wrapped;
4609         PyObject *obj, *value;
4610         int ret;
4611
4612         if (!PyArg_UnpackTuple(args, "", 2, 2, &obj, &value))
4613                 return NULL;
4614         ret = (*func)(self, obj, value);
4615         if (ret < 0)
4616                 return NULL;
4617         Py_INCREF(Py_None);
4618         return Py_None;
4619 }
4620
4621 static PyObject *
4622 wrap_descr_delete(PyObject *self, PyObject *args, void *wrapped)
4623 {
4624         descrsetfunc func = (descrsetfunc)wrapped;
4625         PyObject *obj;
4626         int ret;
4627
4628         if (!check_num_args(args, 1))
4629                 return NULL;
4630         obj = PyTuple_GET_ITEM(args, 0);
4631         ret = (*func)(self, obj, NULL);
4632         if (ret < 0)
4633                 return NULL;
4634         Py_INCREF(Py_None);
4635         return Py_None;
4636 }
4637
4638 static PyObject *
4639 wrap_init(PyObject *self, PyObject *args, void *wrapped, PyObject *kwds)
4640 {
4641         initproc func = (initproc)wrapped;
4642
4643         if (func(self, args, kwds) < 0)
4644                 return NULL;
4645         Py_INCREF(Py_None);
4646         return Py_None;
4647 }
4648
4649 static PyObject *
4650 tp_new_wrapper(PyObject *self, PyObject *args, PyObject *kwds)
4651 {
4652         PyTypeObject *type, *subtype, *staticbase;
4653         PyObject *arg0, *res;
4654
4655         if (self == NULL || !PyType_Check(self))
4656                 Py_FatalError("__new__() called with non-type 'self'");
4657         type = (PyTypeObject *)self;
4658         if (!PyTuple_Check(args) || PyTuple_GET_SIZE(args) < 1) {
4659                 PyErr_Format(PyExc_TypeError,
4660                              "%s.__new__(): not enough arguments",
4661                              type->tp_name);
4662                 return NULL;
4663         }
4664         arg0 = PyTuple_GET_ITEM(args, 0);
4665         if (!PyType_Check(arg0)) {
4666                 PyErr_Format(PyExc_TypeError,
4667                              "%s.__new__(X): X is not a type object (%s)",
4668                              type->tp_name,
4669                              Py_TYPE(arg0)->tp_name);
4670                 return NULL;
4671         }
4672         subtype = (PyTypeObject *)arg0;
4673         if (!PyType_IsSubtype(subtype, type)) {
4674                 PyErr_Format(PyExc_TypeError,
4675                              "%s.__new__(%s): %s is not a subtype of %s",
4676                              type->tp_name,
4677                              subtype->tp_name,
4678                              subtype->tp_name,
4679                              type->tp_name);
4680                 return NULL;
4681         }
4682
4683         /* Check that the use doesn't do something silly and unsafe like
4684            object.__new__(dict).  To do this, we check that the
4685            most derived base that's not a heap type is this type. */
4686         staticbase = subtype;
4687         while (staticbase && (staticbase->tp_flags & Py_TPFLAGS_HEAPTYPE))
4688                 staticbase = staticbase->tp_base;
4689         /* If staticbase is NULL now, it is a really weird type.
4690            In the spirit of backwards compatibility (?), just shut up. */
4691         if (staticbase && staticbase->tp_new != type->tp_new) {
4692                 PyErr_Format(PyExc_TypeError,
4693                              "%s.__new__(%s) is not safe, use %s.__new__()",
4694                              type->tp_name,
4695                              subtype->tp_name,
4696                              staticbase == NULL ? "?" : staticbase->tp_name);
4697                 return NULL;
4698         }
4699
4700         args = PyTuple_GetSlice(args, 1, PyTuple_GET_SIZE(args));
4701         if (args == NULL)
4702                 return NULL;
4703         res = type->tp_new(subtype, args, kwds);
4704         Py_DECREF(args);
4705         return res;
4706 }
4707
4708 static struct PyMethodDef tp_new_methoddef[] = {
4709         {"__new__", (PyCFunction)tp_new_wrapper, METH_VARARGS|METH_KEYWORDS,
4710          PyDoc_STR("T.__new__(S, ...) -> "
4711                    "a new object with type S, a subtype of T")},
4712         {0}
4713 };
4714
4715 static int
4716 add_tp_new_wrapper(PyTypeObject *type)
4717 {
4718         PyObject *func;
4719
4720         if (PyDict_GetItemString(type->tp_dict, "__new__") != NULL)
4721                 return 0;
4722         func = PyCFunction_New(tp_new_methoddef, (PyObject *)type);
4723         if (func == NULL)
4724                 return -1;
4725         if (PyDict_SetItemString(type->tp_dict, "__new__", func)) {
4726                 Py_DECREF(func);
4727                 return -1;
4728         }
4729         Py_DECREF(func);
4730         return 0;
4731 }
4732
4733 /* Slot wrappers that call the corresponding __foo__ slot.  See comments
4734    below at override_slots() for more explanation. */
4735
4736 #define SLOT0(FUNCNAME, OPSTR) \
4737 static PyObject * \
4738 FUNCNAME(PyObject *self) \
4739 { \
4740         static PyObject *cache_str; \
4741         return call_method(self, OPSTR, &cache_str, "()"); \
4742 }
4743
4744 #define SLOT1(FUNCNAME, OPSTR, ARG1TYPE, ARGCODES) \
4745 static PyObject * \
4746 FUNCNAME(PyObject *self, ARG1TYPE arg1) \
4747 { \
4748         static PyObject *cache_str; \
4749         return call_method(self, OPSTR, &cache_str, "(" ARGCODES ")", arg1); \
4750 }
4751
4752 /* Boolean helper for SLOT1BINFULL().
4753    right.__class__ is a nontrivial subclass of left.__class__. */
4754 static int
4755 method_is_overloaded(PyObject *left, PyObject *right, char *name)
4756 {
4757         PyObject *a, *b;
4758         int ok;
4759
4760         b = PyObject_GetAttrString((PyObject *)(Py_TYPE(right)), name);
4761         if (b == NULL) {
4762                 PyErr_Clear();
4763                 /* If right doesn't have it, it's not overloaded */
4764                 return 0;
4765         }
4766
4767         a = PyObject_GetAttrString((PyObject *)(Py_TYPE(left)), name);
4768         if (a == NULL) {
4769                 PyErr_Clear();
4770                 Py_DECREF(b);
4771                 /* If right has it but left doesn't, it's overloaded */
4772                 return 1;
4773         }
4774
4775         ok = PyObject_RichCompareBool(a, b, Py_NE);
4776         Py_DECREF(a);
4777         Py_DECREF(b);
4778         if (ok < 0) {
4779                 PyErr_Clear();
4780                 return 0;
4781         }
4782
4783         return ok;
4784 }
4785
4786
4787 #define SLOT1BINFULL(FUNCNAME, TESTFUNC, SLOTNAME, OPSTR, ROPSTR) \
4788 static PyObject * \
4789 FUNCNAME(PyObject *self, PyObject *other) \
4790 { \
4791         static PyObject *cache_str, *rcache_str; \
4792         int do_other = Py_TYPE(self) != Py_TYPE(other) && \
4793             Py_TYPE(other)->tp_as_number != NULL && \
4794             Py_TYPE(other)->tp_as_number->SLOTNAME == TESTFUNC; \
4795         if (Py_TYPE(self)->tp_as_number != NULL && \
4796             Py_TYPE(self)->tp_as_number->SLOTNAME == TESTFUNC) { \
4797                 PyObject *r; \
4798                 if (do_other && \
4799                     PyType_IsSubtype(Py_TYPE(other), Py_TYPE(self)) && \
4800                     method_is_overloaded(self, other, ROPSTR)) { \
4801                         r = call_maybe( \
4802                                 other, ROPSTR, &rcache_str, "(O)", self); \
4803                         if (r != Py_NotImplemented) \
4804                                 return r; \
4805                         Py_DECREF(r); \
4806                         do_other = 0; \
4807                 } \
4808                 r = call_maybe( \
4809                         self, OPSTR, &cache_str, "(O)", other); \
4810                 if (r != Py_NotImplemented || \
4811                     Py_TYPE(other) == Py_TYPE(self)) \
4812                         return r; \
4813                 Py_DECREF(r); \
4814         } \
4815         if (do_other) { \
4816                 return call_maybe( \
4817                         other, ROPSTR, &rcache_str, "(O)", self); \
4818         } \
4819         Py_INCREF(Py_NotImplemented); \
4820         return Py_NotImplemented; \
4821 }
4822
4823 #define SLOT1BIN(FUNCNAME, SLOTNAME, OPSTR, ROPSTR) \
4824         SLOT1BINFULL(FUNCNAME, FUNCNAME, SLOTNAME, OPSTR, ROPSTR)
4825
4826 #define SLOT2(FUNCNAME, OPSTR, ARG1TYPE, ARG2TYPE, ARGCODES) \
4827 static PyObject * \
4828 FUNCNAME(PyObject *self, ARG1TYPE arg1, ARG2TYPE arg2) \
4829 { \
4830         static PyObject *cache_str; \
4831         return call_method(self, OPSTR, &cache_str, \
4832                            "(" ARGCODES ")", arg1, arg2); \
4833 }
4834
4835 static Py_ssize_t
4836 slot_sq_length(PyObject *self)
4837 {
4838         static PyObject *len_str;
4839         PyObject *res = call_method(self, "__len__", &len_str, "()");
4840         Py_ssize_t len;
4841
4842         if (res == NULL)
4843                 return -1;
4844         len = PyInt_AsSsize_t(res);
4845         Py_DECREF(res);
4846         if (len < 0) {
4847                 if (!PyErr_Occurred())
4848                         PyErr_SetString(PyExc_ValueError,
4849                                         "__len__() should return >= 0");
4850                 return -1;
4851         }
4852         return len;
4853 }
4854
4855 /* Super-optimized version of slot_sq_item.
4856    Other slots could do the same... */
4857 static PyObject *
4858 slot_sq_item(PyObject *self, Py_ssize_t i)
4859 {
4860         static PyObject *getitem_str;
4861         PyObject *func, *args = NULL, *ival = NULL, *retval = NULL;
4862         descrgetfunc f;
4863
4864         if (getitem_str == NULL) {
4865                 getitem_str = PyString_InternFromString("__getitem__");
4866                 if (getitem_str == NULL)
4867                         return NULL;
4868         }
4869         func = _PyType_Lookup(Py_TYPE(self), getitem_str);
4870         if (func != NULL) {
4871                 if ((f = Py_TYPE(func)->tp_descr_get) == NULL)
4872                         Py_INCREF(func);
4873                 else {
4874                         func = f(func, self, (PyObject *)(Py_TYPE(self)));
4875                         if (func == NULL) {
4876                                 return NULL;
4877                         }
4878                 }
4879                 ival = PyInt_FromSsize_t(i);
4880                 if (ival != NULL) {
4881                         args = PyTuple_New(1);
4882                         if (args != NULL) {
4883                                 PyTuple_SET_ITEM(args, 0, ival);
4884                                 retval = PyObject_Call(func, args, NULL);
4885                                 Py_XDECREF(args);
4886                                 Py_XDECREF(func);
4887                                 return retval;
4888                         }
4889                 }
4890         }
4891         else {
4892                 PyErr_SetObject(PyExc_AttributeError, getitem_str);
4893         }
4894         Py_XDECREF(args);
4895         Py_XDECREF(ival);
4896         Py_XDECREF(func);
4897         return NULL;
4898 }
4899
4900 SLOT2(slot_sq_slice, "__getslice__", Py_ssize_t, Py_ssize_t, "nn")
4901
4902 static int
4903 slot_sq_ass_item(PyObject *self, Py_ssize_t index, PyObject *value)
4904 {
4905         PyObject *res;
4906         static PyObject *delitem_str, *setitem_str;
4907
4908         if (value == NULL)
4909                 res = call_method(self, "__delitem__", &delitem_str,
4910                                   "(n)", index);
4911         else
4912                 res = call_method(self, "__setitem__", &setitem_str,
4913                                   "(nO)", index, value);
4914         if (res == NULL)
4915                 return -1;
4916         Py_DECREF(res);
4917         return 0;
4918 }
4919
4920 static int
4921 slot_sq_ass_slice(PyObject *self, Py_ssize_t i, Py_ssize_t j, PyObject *value)
4922 {
4923         PyObject *res;
4924         static PyObject *delslice_str, *setslice_str;
4925
4926         if (value == NULL)
4927                 res = call_method(self, "__delslice__", &delslice_str,
4928                                   "(nn)", i, j);
4929         else
4930                 res = call_method(self, "__setslice__", &setslice_str,
4931                                   "(nnO)", i, j, value);
4932         if (res == NULL)
4933                 return -1;
4934         Py_DECREF(res);
4935         return 0;
4936 }
4937
4938 static int
4939 slot_sq_contains(PyObject *self, PyObject *value)
4940 {
4941         PyObject *func, *res, *args;
4942         int result = -1;
4943
4944         static PyObject *contains_str;
4945
4946         func = lookup_maybe(self, "__contains__", &contains_str);
4947         if (func != NULL) {
4948                 args = PyTuple_Pack(1, value);
4949                 if (args == NULL)
4950                         res = NULL;
4951                 else {
4952                         res = PyObject_Call(func, args, NULL);
4953                         Py_DECREF(args);
4954                 }
4955                 Py_DECREF(func);
4956                 if (res != NULL) {
4957                         result = PyObject_IsTrue(res);
4958                         Py_DECREF(res);
4959                 }
4960         }
4961         else if (! PyErr_Occurred()) {
4962                 /* Possible results: -1 and 1 */
4963                 result = (int)_PySequence_IterSearch(self, value,
4964                                                  PY_ITERSEARCH_CONTAINS);
4965         }
4966         return result;
4967 }
4968
4969 #define slot_mp_length slot_sq_length
4970
4971 SLOT1(slot_mp_subscript, "__getitem__", PyObject *, "O")
4972
4973 static int
4974 slot_mp_ass_subscript(PyObject *self, PyObject *key, PyObject *value)
4975 {
4976         PyObject *res;
4977         static PyObject *delitem_str, *setitem_str;
4978
4979         if (value == NULL)
4980                 res = call_method(self, "__delitem__", &delitem_str,
4981                                   "(O)", key);
4982         else
4983                 res = call_method(self, "__setitem__", &setitem_str,
4984                                  "(OO)", key, value);
4985         if (res == NULL)
4986                 return -1;
4987         Py_DECREF(res);
4988         return 0;
4989 }
4990
4991 SLOT1BIN(slot_nb_add, nb_add, "__add__", "__radd__")
4992 SLOT1BIN(slot_nb_subtract, nb_subtract, "__sub__", "__rsub__")
4993 SLOT1BIN(slot_nb_multiply, nb_multiply, "__mul__", "__rmul__")
4994 SLOT1BIN(slot_nb_divide, nb_divide, "__div__", "__rdiv__")
4995 SLOT1BIN(slot_nb_remainder, nb_remainder, "__mod__", "__rmod__")
4996 SLOT1BIN(slot_nb_divmod, nb_divmod, "__divmod__", "__rdivmod__")
4997
4998 static PyObject *slot_nb_power(PyObject *, PyObject *, PyObject *);
4999
5000 SLOT1BINFULL(slot_nb_power_binary, slot_nb_power,
5001              nb_power, "__pow__", "__rpow__")
5002
5003 static PyObject *
5004 slot_nb_power(PyObject *self, PyObject *other, PyObject *modulus)
5005 {
5006         static PyObject *pow_str;
5007
5008         if (modulus == Py_None)
5009                 return slot_nb_power_binary(self, other);
5010         /* Three-arg power doesn't use __rpow__.  But ternary_op
5011            can call this when the second argument's type uses
5012            slot_nb_power, so check before calling self.__pow__. */
5013         if (Py_TYPE(self)->tp_as_number != NULL &&
5014             Py_TYPE(self)->tp_as_number->nb_power == slot_nb_power) {
5015                 return call_method(self, "__pow__", &pow_str,
5016                                    "(OO)", other, modulus);
5017         }
5018         Py_INCREF(Py_NotImplemented);
5019         return Py_NotImplemented;
5020 }
5021
5022 SLOT0(slot_nb_negative, "__neg__")
5023 SLOT0(slot_nb_positive, "__pos__")
5024 SLOT0(slot_nb_absolute, "__abs__")
5025
5026 static int
5027 slot_nb_nonzero(PyObject *self)
5028 {
5029         PyObject *func, *args;
5030         static PyObject *nonzero_str, *len_str;
5031         int result = -1;
5032
5033         func = lookup_maybe(self, "__nonzero__", &nonzero_str);
5034         if (func == NULL) {
5035                 if (PyErr_Occurred())
5036                         return -1;
5037                 func = lookup_maybe(self, "__len__", &len_str);
5038                 if (func == NULL)
5039                         return PyErr_Occurred() ? -1 : 1;
5040         }
5041         args = PyTuple_New(0);
5042         if (args != NULL) {
5043                 PyObject *temp = PyObject_Call(func, args, NULL);
5044                 Py_DECREF(args);
5045                 if (temp != NULL) {
5046                         if (PyInt_CheckExact(temp) || PyBool_Check(temp))
5047                                 result = PyObject_IsTrue(temp);
5048                         else {
5049                                 PyErr_Format(PyExc_TypeError,
5050                                              "__nonzero__ should return "
5051                                              "bool or int, returned %s",
5052                                              temp->ob_type->tp_name);
5053                                 result = -1;
5054                         }
5055                         Py_DECREF(temp);
5056                 }
5057         }
5058         Py_DECREF(func);
5059         return result;
5060 }
5061
5062
5063 static PyObject *
5064 slot_nb_index(PyObject *self)
5065 {
5066         static PyObject *index_str;
5067         return call_method(self, "__index__", &index_str, "()");
5068 }
5069
5070
5071 SLOT0(slot_nb_invert, "__invert__")
5072 SLOT1BIN(slot_nb_lshift, nb_lshift, "__lshift__", "__rlshift__")
5073 SLOT1BIN(slot_nb_rshift, nb_rshift, "__rshift__", "__rrshift__")
5074 SLOT1BIN(slot_nb_and, nb_and, "__and__", "__rand__")
5075 SLOT1BIN(slot_nb_xor, nb_xor, "__xor__", "__rxor__")
5076 SLOT1BIN(slot_nb_or, nb_or, "__or__", "__ror__")
5077
5078 static int
5079 slot_nb_coerce(PyObject **a, PyObject **b)
5080 {
5081         static PyObject *coerce_str;
5082         PyObject *self = *a, *other = *b;
5083
5084         if (self->ob_type->tp_as_number != NULL &&
5085             self->ob_type->tp_as_number->nb_coerce == slot_nb_coerce) {
5086                 PyObject *r;
5087                 r = call_maybe(
5088                         self, "__coerce__", &coerce_str, "(O)", other);
5089                 if (r == NULL)
5090                         return -1;
5091                 if (r == Py_NotImplemented) {
5092                         Py_DECREF(r);
5093                 }
5094                 else {
5095                         if (!PyTuple_Check(r) || PyTuple_GET_SIZE(r) != 2) {
5096                                 PyErr_SetString(PyExc_TypeError,
5097                                         "__coerce__ didn't return a 2-tuple");
5098                                 Py_DECREF(r);
5099                                 return -1;
5100                         }
5101                         *a = PyTuple_GET_ITEM(r, 0);
5102                         Py_INCREF(*a);
5103                         *b = PyTuple_GET_ITEM(r, 1);
5104                         Py_INCREF(*b);
5105                         Py_DECREF(r);
5106                         return 0;
5107                 }
5108         }
5109         if (other->ob_type->tp_as_number != NULL &&
5110             other->ob_type->tp_as_number->nb_coerce == slot_nb_coerce) {
5111                 PyObject *r;
5112                 r = call_maybe(
5113                         other, "__coerce__", &coerce_str, "(O)", self);
5114                 if (r == NULL)
5115                         return -1;
5116                 if (r == Py_NotImplemented) {
5117                         Py_DECREF(r);
5118                         return 1;
5119                 }
5120                 if (!PyTuple_Check(r) || PyTuple_GET_SIZE(r) != 2) {
5121                         PyErr_SetString(PyExc_TypeError,
5122                                         "__coerce__ didn't return a 2-tuple");
5123                         Py_DECREF(r);
5124                         return -1;
5125                 }
5126                 *a = PyTuple_GET_ITEM(r, 1);
5127                 Py_INCREF(*a);
5128                 *b = PyTuple_GET_ITEM(r, 0);
5129                 Py_INCREF(*b);
5130                 Py_DECREF(r);
5131                 return 0;
5132         }
5133         return 1;
5134 }
5135
5136 SLOT0(slot_nb_int, "__int__")
5137 SLOT0(slot_nb_long, "__long__")
5138 SLOT0(slot_nb_float, "__float__")
5139 SLOT0(slot_nb_oct, "__oct__")
5140 SLOT0(slot_nb_hex, "__hex__")
5141 SLOT1(slot_nb_inplace_add, "__iadd__", PyObject *, "O")
5142 SLOT1(slot_nb_inplace_subtract, "__isub__", PyObject *, "O")
5143 SLOT1(slot_nb_inplace_multiply, "__imul__", PyObject *, "O")
5144 SLOT1(slot_nb_inplace_divide, "__idiv__", PyObject *, "O")
5145 SLOT1(slot_nb_inplace_remainder, "__imod__", PyObject *, "O")
5146 /* Can't use SLOT1 here, because nb_inplace_power is ternary */
5147 static PyObject *
5148 slot_nb_inplace_power(PyObject *self, PyObject * arg1, PyObject *arg2)
5149 {
5150   static PyObject *cache_str;
5151   return call_method(self, "__ipow__", &cache_str, "(" "O" ")", arg1);
5152 }
5153 SLOT1(slot_nb_inplace_lshift, "__ilshift__", PyObject *, "O")
5154 SLOT1(slot_nb_inplace_rshift, "__irshift__", PyObject *, "O")
5155 SLOT1(slot_nb_inplace_and, "__iand__", PyObject *, "O")
5156 SLOT1(slot_nb_inplace_xor, "__ixor__", PyObject *, "O")
5157 SLOT1(slot_nb_inplace_or, "__ior__", PyObject *, "O")
5158 SLOT1BIN(slot_nb_floor_divide, nb_floor_divide,
5159          "__floordiv__", "__rfloordiv__")
5160 SLOT1BIN(slot_nb_true_divide, nb_true_divide, "__truediv__", "__rtruediv__")
5161 SLOT1(slot_nb_inplace_floor_divide, "__ifloordiv__", PyObject *, "O")
5162 SLOT1(slot_nb_inplace_true_divide, "__itruediv__", PyObject *, "O")
5163
5164 static int
5165 half_compare(PyObject *self, PyObject *other)
5166 {
5167         PyObject *func, *args, *res;
5168         static PyObject *cmp_str;
5169         Py_ssize_t c;
5170
5171         func = lookup_method(self, "__cmp__", &cmp_str);
5172         if (func == NULL) {
5173                 PyErr_Clear();
5174         }
5175         else {
5176                 args = PyTuple_Pack(1, other);
5177                 if (args == NULL)
5178                         res = NULL;
5179                 else {
5180                         res = PyObject_Call(func, args, NULL);
5181                         Py_DECREF(args);
5182                 }
5183                 Py_DECREF(func);
5184                 if (res != Py_NotImplemented) {
5185                         if (res == NULL)
5186                                 return -2;
5187                         c = PyInt_AsLong(res);
5188                         Py_DECREF(res);
5189                         if (c == -1 && PyErr_Occurred())
5190                                 return -2;
5191                         return (c < 0) ? -1 : (c > 0) ? 1 : 0;
5192                 }
5193                 Py_DECREF(res);
5194         }
5195         return 2;
5196 }
5197
5198 /* This slot is published for the benefit of try_3way_compare in object.c */
5199 int
5200 _PyObject_SlotCompare(PyObject *self, PyObject *other)
5201 {
5202         int c;
5203
5204         if (Py_TYPE(self)->tp_compare == _PyObject_SlotCompare) {
5205                 c = half_compare(self, other);
5206                 if (c <= 1)
5207                         return c;
5208         }
5209         if (Py_TYPE(other)->tp_compare == _PyObject_SlotCompare) {
5210                 c = half_compare(other, self);
5211                 if (c < -1)
5212                         return -2;
5213                 if (c <= 1)
5214                         return -c;
5215         }
5216         return (void *)self < (void *)other ? -1 :
5217                 (void *)self > (void *)other ? 1 : 0;
5218 }
5219
5220 static PyObject *
5221 slot_tp_repr(PyObject *self)
5222 {
5223         PyObject *func, *res;
5224         static PyObject *repr_str;
5225
5226         func = lookup_method(self, "__repr__", &repr_str);
5227         if (func != NULL) {
5228                 res = PyEval_CallObject(func, NULL);
5229                 Py_DECREF(func);
5230                 return res;
5231         }
5232         PyErr_Clear();
5233         return PyString_FromFormat("<%s object at %p>",
5234                                    Py_TYPE(self)->tp_name, self);
5235 }
5236
5237 static PyObject *
5238 slot_tp_str(PyObject *self)
5239 {
5240         PyObject *func, *res;
5241         static PyObject *str_str;
5242
5243         func = lookup_method(self, "__str__", &str_str);
5244         if (func != NULL) {
5245                 res = PyEval_CallObject(func, NULL);
5246                 Py_DECREF(func);
5247                 return res;
5248         }
5249         else {
5250                 PyErr_Clear();
5251                 return slot_tp_repr(self);
5252         }
5253 }
5254
5255 static long
5256 slot_tp_hash(PyObject *self)
5257 {
5258         PyObject *func;
5259         static PyObject *hash_str, *eq_str, *cmp_str;
5260         long h;
5261
5262         func = lookup_method(self, "__hash__", &hash_str);
5263
5264         if (func != NULL && func != Py_None) {
5265                 PyObject *res = PyEval_CallObject(func, NULL);
5266                 Py_DECREF(func);
5267                 if (res == NULL)
5268                         return -1;
5269                 if (PyLong_Check(res))
5270                         h = PyLong_Type.tp_hash(res);
5271                 else
5272                         h = PyInt_AsLong(res);
5273                 Py_DECREF(res);
5274         }
5275         else {
5276                 Py_XDECREF(func); /* may be None */
5277                 PyErr_Clear();
5278                 func = lookup_method(self, "__eq__", &eq_str);
5279                 if (func == NULL) {
5280                         PyErr_Clear();
5281                         func = lookup_method(self, "__cmp__", &cmp_str);
5282                 }
5283                 if (func != NULL) {
5284                         Py_DECREF(func);
5285                         return PyObject_HashNotImplemented(self);
5286                 }
5287                 PyErr_Clear();
5288                 h = _Py_HashPointer((void *)self);
5289         }
5290         if (h == -1 && !PyErr_Occurred())
5291                 h = -2;
5292         return h;
5293 }
5294
5295 static PyObject *
5296 slot_tp_call(PyObject *self, PyObject *args, PyObject *kwds)
5297 {
5298         static PyObject *call_str;
5299         PyObject *meth = lookup_method(self, "__call__", &call_str);
5300         PyObject *res;
5301
5302         if (meth == NULL)
5303                 return NULL;
5304
5305         res = PyObject_Call(meth, args, kwds);
5306
5307         Py_DECREF(meth);
5308         return res;
5309 }
5310
5311 /* There are two slot dispatch functions for tp_getattro.
5312
5313    - slot_tp_getattro() is used when __getattribute__ is overridden
5314      but no __getattr__ hook is present;
5315
5316    - slot_tp_getattr_hook() is used when a __getattr__ hook is present.
5317
5318    The code in update_one_slot() always installs slot_tp_getattr_hook(); this
5319    detects the absence of __getattr__ and then installs the simpler slot if
5320    necessary. */
5321
5322 static PyObject *
5323 slot_tp_getattro(PyObject *self, PyObject *name)
5324 {
5325         static PyObject *getattribute_str = NULL;
5326         return call_method(self, "__getattribute__", &getattribute_str,
5327                            "(O)", name);
5328 }
5329
5330 static PyObject *
5331 slot_tp_getattr_hook(PyObject *self, PyObject *name)
5332 {
5333         PyTypeObject *tp = Py_TYPE(self);
5334         PyObject *getattr, *getattribute, *res;
5335         static PyObject *getattribute_str = NULL;
5336         static PyObject *getattr_str = NULL;
5337
5338         if (getattr_str == NULL) {
5339                 getattr_str = PyString_InternFromString("__getattr__");
5340                 if (getattr_str == NULL)
5341                         return NULL;
5342         }
5343         if (getattribute_str == NULL) {
5344                 getattribute_str =
5345                         PyString_InternFromString("__getattribute__");
5346                 if (getattribute_str == NULL)
5347                         return NULL;
5348         }
5349         getattr = _PyType_Lookup(tp, getattr_str);
5350         if (getattr == NULL) {
5351                 /* No __getattr__ hook: use a simpler dispatcher */
5352                 tp->tp_getattro = slot_tp_getattro;
5353                 return slot_tp_getattro(self, name);
5354         }
5355         getattribute = _PyType_Lookup(tp, getattribute_str);
5356         if (getattribute == NULL ||
5357             (Py_TYPE(getattribute) == &PyWrapperDescr_Type &&
5358              ((PyWrapperDescrObject *)getattribute)->d_wrapped ==
5359              (void *)PyObject_GenericGetAttr))
5360                 res = PyObject_GenericGetAttr(self, name);
5361         else
5362                 res = PyObject_CallFunctionObjArgs(getattribute, self, name, NULL);
5363         if (res == NULL && PyErr_ExceptionMatches(PyExc_AttributeError)) {
5364                 PyErr_Clear();
5365                 res = PyObject_CallFunctionObjArgs(getattr, self, name, NULL);
5366         }
5367         return res;
5368 }
5369
5370 static int
5371 slot_tp_setattro(PyObject *self, PyObject *name, PyObject *value)
5372 {
5373         PyObject *res;
5374         static PyObject *delattr_str, *setattr_str;
5375
5376         if (value == NULL)
5377                 res = call_method(self, "__delattr__", &delattr_str,
5378                                   "(O)", name);
5379         else
5380                 res = call_method(self, "__setattr__", &setattr_str,
5381                                   "(OO)", name, value);
5382         if (res == NULL)
5383                 return -1;
5384         Py_DECREF(res);
5385         return 0;
5386 }
5387
5388 static char *name_op[] = {
5389     "__lt__",
5390     "__le__",
5391     "__eq__",
5392     "__ne__",
5393     "__gt__",
5394     "__ge__",
5395 };
5396
5397 static PyObject *
5398 half_richcompare(PyObject *self, PyObject *other, int op)
5399 {
5400         PyObject *func, *args, *res;
5401         static PyObject *op_str[6];
5402
5403         func = lookup_method(self, name_op[op], &op_str[op]);
5404         if (func == NULL) {
5405                 PyErr_Clear();
5406                 Py_INCREF(Py_NotImplemented);
5407                 return Py_NotImplemented;
5408         }
5409         args = PyTuple_Pack(1, other);
5410         if (args == NULL)
5411                 res = NULL;
5412         else {
5413                 res = PyObject_Call(func, args, NULL);
5414                 Py_DECREF(args);
5415         }
5416         Py_DECREF(func);
5417         return res;
5418 }
5419
5420 static PyObject *
5421 slot_tp_richcompare(PyObject *self, PyObject *other, int op)
5422 {
5423         PyObject *res;
5424
5425         if (Py_TYPE(self)->tp_richcompare == slot_tp_richcompare) {
5426                 res = half_richcompare(self, other, op);
5427                 if (res != Py_NotImplemented)
5428                         return res;
5429                 Py_DECREF(res);
5430         }
5431         if (Py_TYPE(other)->tp_richcompare == slot_tp_richcompare) {
5432                 res = half_richcompare(other, self, _Py_SwappedOp[op]);
5433                 if (res != Py_NotImplemented) {
5434                         return res;
5435                 }
5436                 Py_DECREF(res);
5437         }
5438         Py_INCREF(Py_NotImplemented);
5439         return Py_NotImplemented;
5440 }
5441
5442 static PyObject *
5443 slot_tp_iter(PyObject *self)
5444 {
5445         PyObject *func, *res;
5446         static PyObject *iter_str, *getitem_str;
5447
5448         func = lookup_method(self, "__iter__", &iter_str);
5449         if (func != NULL) {
5450                 PyObject *args;
5451                 args = res = PyTuple_New(0);
5452                 if (args != NULL) {
5453                         res = PyObject_Call(func, args, NULL);
5454                         Py_DECREF(args);
5455                 }
5456                 Py_DECREF(func);
5457                 return res;
5458         }
5459         PyErr_Clear();
5460         func = lookup_method(self, "__getitem__", &getitem_str);
5461         if (func == NULL) {
5462                 PyErr_Format(PyExc_TypeError,
5463                              "'%.200s' object is not iterable",
5464                              Py_TYPE(self)->tp_name);
5465                 return NULL;
5466         }
5467         Py_DECREF(func);
5468         return PySeqIter_New(self);
5469 }
5470
5471 static PyObject *
5472 slot_tp_iternext(PyObject *self)
5473 {
5474         static PyObject *next_str;
5475         return call_method(self, "next", &next_str, "()");
5476 }
5477
5478 static PyObject *
5479 slot_tp_descr_get(PyObject *self, PyObject *obj, PyObject *type)
5480 {
5481         PyTypeObject *tp = Py_TYPE(self);
5482         PyObject *get;
5483         static PyObject *get_str = NULL;
5484
5485         if (get_str == NULL) {
5486                 get_str = PyString_InternFromString("__get__");
5487                 if (get_str == NULL)
5488                         return NULL;
5489         }
5490         get = _PyType_Lookup(tp, get_str);
5491         if (get == NULL) {
5492                 /* Avoid further slowdowns */
5493                 if (tp->tp_descr_get == slot_tp_descr_get)
5494                         tp->tp_descr_get = NULL;
5495                 Py_INCREF(self);
5496                 return self;
5497         }
5498         if (obj == NULL)
5499                 obj = Py_None;
5500         if (type == NULL)
5501                 type = Py_None;
5502         return PyObject_CallFunctionObjArgs(get, self, obj, type, NULL);
5503 }
5504
5505 static int
5506 slot_tp_descr_set(PyObject *self, PyObject *target, PyObject *value)
5507 {
5508         PyObject *res;
5509         static PyObject *del_str, *set_str;
5510
5511         if (value == NULL)
5512                 res = call_method(self, "__delete__", &del_str,
5513                                   "(O)", target);
5514         else
5515                 res = call_method(self, "__set__", &set_str,
5516                                   "(OO)", target, value);
5517         if (res == NULL)
5518                 return -1;
5519         Py_DECREF(res);
5520         return 0;
5521 }
5522
5523 static int
5524 slot_tp_init(PyObject *self, PyObject *args, PyObject *kwds)
5525 {
5526         static PyObject *init_str;
5527         PyObject *meth = lookup_method(self, "__init__", &init_str);
5528         PyObject *res;
5529
5530         if (meth == NULL)
5531                 return -1;
5532         res = PyObject_Call(meth, args, kwds);
5533         Py_DECREF(meth);
5534         if (res == NULL)
5535                 return -1;
5536         if (res != Py_None) {
5537                 PyErr_Format(PyExc_TypeError,
5538                              "__init__() should return None, not '%.200s'",
5539                              Py_TYPE(res)->tp_name);
5540                 Py_DECREF(res);
5541                 return -1;
5542         }
5543         Py_DECREF(res);
5544         return 0;
5545 }
5546
5547 static PyObject *
5548 slot_tp_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
5549 {
5550         static PyObject *new_str;
5551         PyObject *func;
5552         PyObject *newargs, *x;
5553         Py_ssize_t i, n;
5554
5555         if (new_str == NULL) {
5556                 new_str = PyString_InternFromString("__new__");
5557                 if (new_str == NULL)
5558                         return NULL;
5559         }
5560         func = PyObject_GetAttr((PyObject *)type, new_str);
5561         if (func == NULL)
5562                 return NULL;
5563         assert(PyTuple_Check(args));
5564         n = PyTuple_GET_SIZE(args);
5565         newargs = PyTuple_New(n+1);
5566         if (newargs == NULL)
5567                 return NULL;
5568         Py_INCREF(type);
5569         PyTuple_SET_ITEM(newargs, 0, (PyObject *)type);
5570         for (i = 0; i < n; i++) {
5571                 x = PyTuple_GET_ITEM(args, i);
5572                 Py_INCREF(x);
5573                 PyTuple_SET_ITEM(newargs, i+1, x);
5574         }
5575         x = PyObject_Call(func, newargs, kwds);
5576         Py_DECREF(newargs);
5577         Py_DECREF(func);
5578         return x;
5579 }
5580
5581 static void
5582 slot_tp_del(PyObject *self)
5583 {
5584         static PyObject *del_str = NULL;
5585         PyObject *del, *res;
5586         PyObject *error_type, *error_value, *error_traceback;
5587
5588         /* Temporarily resurrect the object. */
5589         assert(self->ob_refcnt == 0);
5590         self->ob_refcnt = 1;
5591
5592         /* Save the current exception, if any. */
5593         PyErr_Fetch(&error_type, &error_value, &error_traceback);
5594
5595         /* Execute __del__ method, if any. */
5596         del = lookup_maybe(self, "__del__", &del_str);
5597         if (del != NULL) {
5598                 res = PyEval_CallObject(del, NULL);
5599                 if (res == NULL)
5600                         PyErr_WriteUnraisable(del);
5601                 else
5602                         Py_DECREF(res);
5603                 Py_DECREF(del);
5604         }
5605
5606         /* Restore the saved exception. */
5607         PyErr_Restore(error_type, error_value, error_traceback);
5608
5609         /* Undo the temporary resurrection; can't use DECREF here, it would
5610          * cause a recursive call.
5611          */
5612         assert(self->ob_refcnt > 0);
5613         if (--self->ob_refcnt == 0)
5614                 return; /* this is the normal path out */
5615
5616         /* __del__ resurrected it!  Make it look like the original Py_DECREF
5617          * never happened.
5618          */
5619         {
5620                 Py_ssize_t refcnt = self->ob_refcnt;
5621                 _Py_NewReference(self);
5622                 self->ob_refcnt = refcnt;
5623         }
5624         assert(!PyType_IS_GC(Py_TYPE(self)) ||
5625                _Py_AS_GC(self)->gc.gc_refs != _PyGC_REFS_UNTRACKED);
5626         /* If Py_REF_DEBUG, _Py_NewReference bumped _Py_RefTotal, so
5627          * we need to undo that. */
5628         _Py_DEC_REFTOTAL;
5629         /* If Py_TRACE_REFS, _Py_NewReference re-added self to the object
5630          * chain, so no more to do there.
5631          * If COUNT_ALLOCS, the original decref bumped tp_frees, and
5632          * _Py_NewReference bumped tp_allocs:  both of those need to be
5633          * undone.
5634          */
5635 #ifdef COUNT_ALLOCS
5636         --Py_TYPE(self)->tp_frees;
5637         --Py_TYPE(self)->tp_allocs;
5638 #endif
5639 }
5640
5641
5642 /* Table mapping __foo__ names to tp_foo offsets and slot_tp_foo wrapper
5643    functions.  The offsets here are relative to the 'PyHeapTypeObject'
5644    structure, which incorporates the additional structures used for numbers,
5645    sequences and mappings.
5646    Note that multiple names may map to the same slot (e.g. __eq__,
5647    __ne__ etc. all map to tp_richcompare) and one name may map to multiple
5648    slots (e.g. __str__ affects tp_str as well as tp_repr). The table is
5649    terminated with an all-zero entry.  (This table is further initialized and
5650    sorted in init_slotdefs() below.) */
5651
5652 typedef struct wrapperbase slotdef;
5653
5654 #undef TPSLOT
5655 #undef FLSLOT
5656 #undef ETSLOT
5657 #undef SQSLOT
5658 #undef MPSLOT
5659 #undef NBSLOT
5660 #undef UNSLOT
5661 #undef IBSLOT
5662 #undef BINSLOT
5663 #undef RBINSLOT
5664
5665 #define TPSLOT(NAME, SLOT, FUNCTION, WRAPPER, DOC) \
5666         {NAME, offsetof(PyTypeObject, SLOT), (void *)(FUNCTION), WRAPPER, \
5667          PyDoc_STR(DOC)}
5668 #define FLSLOT(NAME, SLOT, FUNCTION, WRAPPER, DOC, FLAGS) \
5669         {NAME, offsetof(PyTypeObject, SLOT), (void *)(FUNCTION), WRAPPER, \
5670          PyDoc_STR(DOC), FLAGS}
5671 #define ETSLOT(NAME, SLOT, FUNCTION, WRAPPER, DOC) \
5672         {NAME, offsetof(PyHeapTypeObject, SLOT), (void *)(FUNCTION), WRAPPER, \
5673          PyDoc_STR(DOC)}
5674 #define SQSLOT(NAME, SLOT, FUNCTION, WRAPPER, DOC) \
5675         ETSLOT(NAME, as_sequence.SLOT, FUNCTION, WRAPPER, DOC)
5676 #define MPSLOT(NAME, SLOT, FUNCTION, WRAPPER, DOC) \
5677         ETSLOT(NAME, as_mapping.SLOT, FUNCTION, WRAPPER, DOC)
5678 #define NBSLOT(NAME, SLOT, FUNCTION, WRAPPER, DOC) \
5679         ETSLOT(NAME, as_number.SLOT, FUNCTION, WRAPPER, DOC)
5680 #define UNSLOT(NAME, SLOT, FUNCTION, WRAPPER, DOC) \
5681         ETSLOT(NAME, as_number.SLOT, FUNCTION, WRAPPER, \
5682                "x." NAME "() <==> " DOC)
5683 #define IBSLOT(NAME, SLOT, FUNCTION, WRAPPER, DOC) \
5684         ETSLOT(NAME, as_number.SLOT, FUNCTION, WRAPPER, \
5685                "x." NAME "(y) <==> x" DOC "y")
5686 #define BINSLOT(NAME, SLOT, FUNCTION, DOC) \
5687         ETSLOT(NAME, as_number.SLOT, FUNCTION, wrap_binaryfunc_l, \
5688                "x." NAME "(y) <==> x" DOC "y")
5689 #define RBINSLOT(NAME, SLOT, FUNCTION, DOC) \
5690         ETSLOT(NAME, as_number.SLOT, FUNCTION, wrap_binaryfunc_r, \
5691                "x." NAME "(y) <==> y" DOC "x")
5692 #define BINSLOTNOTINFIX(NAME, SLOT, FUNCTION, DOC) \
5693         ETSLOT(NAME, as_number.SLOT, FUNCTION, wrap_binaryfunc_l, \
5694                "x." NAME "(y) <==> " DOC)
5695 #define RBINSLOTNOTINFIX(NAME, SLOT, FUNCTION, DOC) \
5696         ETSLOT(NAME, as_number.SLOT, FUNCTION, wrap_binaryfunc_r, \
5697                "x." NAME "(y) <==> " DOC)
5698
5699 static slotdef slotdefs[] = {
5700         SQSLOT("__len__", sq_length, slot_sq_length, wrap_lenfunc,
5701                "x.__len__() <==> len(x)"),
5702         /* Heap types defining __add__/__mul__ have sq_concat/sq_repeat == NULL.
5703            The logic in abstract.c always falls back to nb_add/nb_multiply in
5704            this case.  Defining both the nb_* and the sq_* slots to call the
5705            user-defined methods has unexpected side-effects, as shown by
5706            test_descr.notimplemented() */
5707         SQSLOT("__add__", sq_concat, NULL, wrap_binaryfunc,
5708           "x.__add__(y) <==> x+y"),
5709         SQSLOT("__mul__", sq_repeat, NULL, wrap_indexargfunc,
5710           "x.__mul__(n) <==> x*n"),
5711         SQSLOT("__rmul__", sq_repeat, NULL, wrap_indexargfunc,
5712           "x.__rmul__(n) <==> n*x"),
5713         SQSLOT("__getitem__", sq_item, slot_sq_item, wrap_sq_item,
5714                "x.__getitem__(y) <==> x[y]"),
5715         SQSLOT("__getslice__", sq_slice, slot_sq_slice, wrap_ssizessizeargfunc,
5716                "x.__getslice__(i, j) <==> x[i:j]\n\
5717                \n\
5718                Use of negative indices is not supported."),
5719         SQSLOT("__setitem__", sq_ass_item, slot_sq_ass_item, wrap_sq_setitem,
5720                "x.__setitem__(i, y) <==> x[i]=y"),
5721         SQSLOT("__delitem__", sq_ass_item, slot_sq_ass_item, wrap_sq_delitem,
5722                "x.__delitem__(y) <==> del x[y]"),
5723         SQSLOT("__setslice__", sq_ass_slice, slot_sq_ass_slice,
5724                wrap_ssizessizeobjargproc,
5725                "x.__setslice__(i, j, y) <==> x[i:j]=y\n\
5726                \n\
5727                Use  of negative indices is not supported."),
5728         SQSLOT("__delslice__", sq_ass_slice, slot_sq_ass_slice, wrap_delslice,
5729                "x.__delslice__(i, j) <==> del x[i:j]\n\
5730                \n\
5731                Use of negative indices is not supported."),
5732         SQSLOT("__contains__", sq_contains, slot_sq_contains, wrap_objobjproc,
5733                "x.__contains__(y) <==> y in x"),
5734         SQSLOT("__iadd__", sq_inplace_concat, NULL,
5735           wrap_binaryfunc, "x.__iadd__(y) <==> x+=y"),
5736         SQSLOT("__imul__", sq_inplace_repeat, NULL,
5737           wrap_indexargfunc, "x.__imul__(y) <==> x*=y"),
5738
5739         MPSLOT("__len__", mp_length, slot_mp_length, wrap_lenfunc,
5740                "x.__len__() <==> len(x)"),
5741         MPSLOT("__getitem__", mp_subscript, slot_mp_subscript,
5742                wrap_binaryfunc,
5743                "x.__getitem__(y) <==> x[y]"),
5744         MPSLOT("__setitem__", mp_ass_subscript, slot_mp_ass_subscript,
5745                wrap_objobjargproc,
5746                "x.__setitem__(i, y) <==> x[i]=y"),
5747         MPSLOT("__delitem__", mp_ass_subscript, slot_mp_ass_subscript,
5748                wrap_delitem,
5749                "x.__delitem__(y) <==> del x[y]"),
5750
5751         BINSLOT("__add__", nb_add, slot_nb_add,
5752                 "+"),
5753         RBINSLOT("__radd__", nb_add, slot_nb_add,
5754                  "+"),
5755         BINSLOT("__sub__", nb_subtract, slot_nb_subtract,
5756                 "-"),
5757         RBINSLOT("__rsub__", nb_subtract, slot_nb_subtract,
5758                  "-"),
5759         BINSLOT("__mul__", nb_multiply, slot_nb_multiply,
5760                 "*"),
5761         RBINSLOT("__rmul__", nb_multiply, slot_nb_multiply,
5762                  "*"),
5763         BINSLOT("__div__", nb_divide, slot_nb_divide,
5764                 "/"),
5765         RBINSLOT("__rdiv__", nb_divide, slot_nb_divide,
5766                  "/"),
5767         BINSLOT("__mod__", nb_remainder, slot_nb_remainder,
5768                 "%"),
5769         RBINSLOT("__rmod__", nb_remainder, slot_nb_remainder,
5770                  "%"),
5771         BINSLOTNOTINFIX("__divmod__", nb_divmod, slot_nb_divmod,
5772                 "divmod(x, y)"),
5773         RBINSLOTNOTINFIX("__rdivmod__", nb_divmod, slot_nb_divmod,
5774                  "divmod(y, x)"),
5775         NBSLOT("__pow__", nb_power, slot_nb_power, wrap_ternaryfunc,
5776                "x.__pow__(y[, z]) <==> pow(x, y[, z])"),
5777         NBSLOT("__rpow__", nb_power, slot_nb_power, wrap_ternaryfunc_r,
5778                "y.__rpow__(x[, z]) <==> pow(x, y[, z])"),
5779         UNSLOT("__neg__", nb_negative, slot_nb_negative, wrap_unaryfunc, "-x"),
5780         UNSLOT("__pos__", nb_positive, slot_nb_positive, wrap_unaryfunc, "+x"),
5781         UNSLOT("__abs__", nb_absolute, slot_nb_absolute, wrap_unaryfunc,
5782                "abs(x)"),
5783         UNSLOT("__nonzero__", nb_nonzero, slot_nb_nonzero, wrap_inquirypred,
5784                "x != 0"),
5785         UNSLOT("__invert__", nb_invert, slot_nb_invert, wrap_unaryfunc, "~x"),
5786         BINSLOT("__lshift__", nb_lshift, slot_nb_lshift, "<<"),
5787         RBINSLOT("__rlshift__", nb_lshift, slot_nb_lshift, "<<"),
5788         BINSLOT("__rshift__", nb_rshift, slot_nb_rshift, ">>"),
5789         RBINSLOT("__rrshift__", nb_rshift, slot_nb_rshift, ">>"),
5790         BINSLOT("__and__", nb_and, slot_nb_and, "&"),
5791         RBINSLOT("__rand__", nb_and, slot_nb_and, "&"),
5792         BINSLOT("__xor__", nb_xor, slot_nb_xor, "^"),
5793         RBINSLOT("__rxor__", nb_xor, slot_nb_xor, "^"),
5794         BINSLOT("__or__", nb_or, slot_nb_or, "|"),
5795         RBINSLOT("__ror__", nb_or, slot_nb_or, "|"),
5796         NBSLOT("__coerce__", nb_coerce, slot_nb_coerce, wrap_coercefunc,
5797                "x.__coerce__(y) <==> coerce(x, y)"),
5798         UNSLOT("__int__", nb_int, slot_nb_int, wrap_unaryfunc,
5799                "int(x)"),
5800         UNSLOT("__long__", nb_long, slot_nb_long, wrap_unaryfunc,
5801                "long(x)"),
5802         UNSLOT("__float__", nb_float, slot_nb_float, wrap_unaryfunc,
5803                "float(x)"),
5804         UNSLOT("__oct__", nb_oct, slot_nb_oct, wrap_unaryfunc,
5805                "oct(x)"),
5806         UNSLOT("__hex__", nb_hex, slot_nb_hex, wrap_unaryfunc,
5807                "hex(x)"),
5808         NBSLOT("__index__", nb_index, slot_nb_index, wrap_unaryfunc,
5809                "x[y:z] <==> x[y.__index__():z.__index__()]"),
5810         IBSLOT("__iadd__", nb_inplace_add, slot_nb_inplace_add,
5811                wrap_binaryfunc, "+"),
5812         IBSLOT("__isub__", nb_inplace_subtract, slot_nb_inplace_subtract,
5813                wrap_binaryfunc, "-"),
5814         IBSLOT("__imul__", nb_inplace_multiply, slot_nb_inplace_multiply,
5815                wrap_binaryfunc, "*"),
5816         IBSLOT("__idiv__", nb_inplace_divide, slot_nb_inplace_divide,
5817                wrap_binaryfunc, "/"),
5818         IBSLOT("__imod__", nb_inplace_remainder, slot_nb_inplace_remainder,
5819                wrap_binaryfunc, "%"),
5820         IBSLOT("__ipow__", nb_inplace_power, slot_nb_inplace_power,
5821                wrap_binaryfunc, "**"),
5822         IBSLOT("__ilshift__", nb_inplace_lshift, slot_nb_inplace_lshift,
5823                wrap_binaryfunc, "<<"),
5824         IBSLOT("__irshift__", nb_inplace_rshift, slot_nb_inplace_rshift,
5825                wrap_binaryfunc, ">>"),
5826         IBSLOT("__iand__", nb_inplace_and, slot_nb_inplace_and,
5827                wrap_binaryfunc, "&"),
5828         IBSLOT("__ixor__", nb_inplace_xor, slot_nb_inplace_xor,
5829                wrap_binaryfunc, "^"),
5830         IBSLOT("__ior__", nb_inplace_or, slot_nb_inplace_or,
5831                wrap_binaryfunc, "|"),
5832         BINSLOT("__floordiv__", nb_floor_divide, slot_nb_floor_divide, "//"),
5833         RBINSLOT("__rfloordiv__", nb_floor_divide, slot_nb_floor_divide, "//"),
5834         BINSLOT("__truediv__", nb_true_divide, slot_nb_true_divide, "/"),
5835         RBINSLOT("__rtruediv__", nb_true_divide, slot_nb_true_divide, "/"),
5836         IBSLOT("__ifloordiv__", nb_inplace_floor_divide,
5837                slot_nb_inplace_floor_divide, wrap_binaryfunc, "//"),
5838         IBSLOT("__itruediv__", nb_inplace_true_divide,
5839                slot_nb_inplace_true_divide, wrap_binaryfunc, "/"),
5840
5841         TPSLOT("__str__", tp_str, slot_tp_str, wrap_unaryfunc,
5842                "x.__str__() <==> str(x)"),
5843         TPSLOT("__str__", tp_print, NULL, NULL, ""),
5844         TPSLOT("__repr__", tp_repr, slot_tp_repr, wrap_unaryfunc,
5845                "x.__repr__() <==> repr(x)"),
5846         TPSLOT("__repr__", tp_print, NULL, NULL, ""),
5847         TPSLOT("__cmp__", tp_compare, _PyObject_SlotCompare, wrap_cmpfunc,
5848                "x.__cmp__(y) <==> cmp(x,y)"),
5849         TPSLOT("__hash__", tp_hash, slot_tp_hash, wrap_hashfunc,
5850                "x.__hash__() <==> hash(x)"),
5851         FLSLOT("__call__", tp_call, slot_tp_call, (wrapperfunc)wrap_call,
5852                "x.__call__(...) <==> x(...)", PyWrapperFlag_KEYWORDS),
5853         TPSLOT("__getattribute__", tp_getattro, slot_tp_getattr_hook,
5854                wrap_binaryfunc, "x.__getattribute__('name') <==> x.name"),
5855         TPSLOT("__getattribute__", tp_getattr, NULL, NULL, ""),
5856         TPSLOT("__getattr__", tp_getattro, slot_tp_getattr_hook, NULL, ""),
5857         TPSLOT("__getattr__", tp_getattr, NULL, NULL, ""),
5858         TPSLOT("__setattr__", tp_setattro, slot_tp_setattro, wrap_setattr,
5859                "x.__setattr__('name', value) <==> x.name = value"),
5860         TPSLOT("__setattr__", tp_setattr, NULL, NULL, ""),
5861         TPSLOT("__delattr__", tp_setattro, slot_tp_setattro, wrap_delattr,
5862                "x.__delattr__('name') <==> del x.name"),
5863         TPSLOT("__delattr__", tp_setattr, NULL, NULL, ""),
5864         TPSLOT("__lt__", tp_richcompare, slot_tp_richcompare, richcmp_lt,
5865                "x.__lt__(y) <==> x<y"),
5866         TPSLOT("__le__", tp_richcompare, slot_tp_richcompare, richcmp_le,
5867                "x.__le__(y) <==> x<=y"),
5868         TPSLOT("__eq__", tp_richcompare, slot_tp_richcompare, richcmp_eq,
5869                "x.__eq__(y) <==> x==y"),
5870         TPSLOT("__ne__", tp_richcompare, slot_tp_richcompare, richcmp_ne,
5871                "x.__ne__(y) <==> x!=y"),
5872         TPSLOT("__gt__", tp_richcompare, slot_tp_richcompare, richcmp_gt,
5873                "x.__gt__(y) <==> x>y"),
5874         TPSLOT("__ge__", tp_richcompare, slot_tp_richcompare, richcmp_ge,
5875                "x.__ge__(y) <==> x>=y"),
5876         TPSLOT("__iter__", tp_iter, slot_tp_iter, wrap_unaryfunc,
5877                "x.__iter__() <==> iter(x)"),
5878         TPSLOT("next", tp_iternext, slot_tp_iternext, wrap_next,
5879                "x.next() -> the next value, or raise StopIteration"),
5880         TPSLOT("__get__", tp_descr_get, slot_tp_descr_get, wrap_descr_get,
5881                "descr.__get__(obj[, type]) -> value"),
5882         TPSLOT("__set__", tp_descr_set, slot_tp_descr_set, wrap_descr_set,
5883                "descr.__set__(obj, value)"),
5884         TPSLOT("__delete__", tp_descr_set, slot_tp_descr_set,
5885                wrap_descr_delete, "descr.__delete__(obj)"),
5886         FLSLOT("__init__", tp_init, slot_tp_init, (wrapperfunc)wrap_init,
5887                "x.__init__(...) initializes x; "
5888                "see x.__class__.__doc__ for signature",
5889                PyWrapperFlag_KEYWORDS),
5890         TPSLOT("__new__", tp_new, slot_tp_new, NULL, ""),
5891         TPSLOT("__del__", tp_del, slot_tp_del, NULL, ""),
5892         {NULL}
5893 };
5894
5895 /* Given a type pointer and an offset gotten from a slotdef entry, return a
5896    pointer to the actual slot.  This is not quite the same as simply adding
5897    the offset to the type pointer, since it takes care to indirect through the
5898    proper indirection pointer (as_buffer, etc.); it returns NULL if the
5899    indirection pointer is NULL. */
5900 static void **
5901 slotptr(PyTypeObject *type, int ioffset)
5902 {
5903         char *ptr;
5904         long offset = ioffset;
5905
5906         /* Note: this depends on the order of the members of PyHeapTypeObject! */
5907         assert(offset >= 0);
5908         assert((size_t)offset < offsetof(PyHeapTypeObject, as_buffer));
5909         if ((size_t)offset >= offsetof(PyHeapTypeObject, as_sequence)) {
5910                 ptr = (char *)type->tp_as_sequence;
5911                 offset -= offsetof(PyHeapTypeObject, as_sequence);
5912         }
5913         else if ((size_t)offset >= offsetof(PyHeapTypeObject, as_mapping)) {
5914                 ptr = (char *)type->tp_as_mapping;
5915                 offset -= offsetof(PyHeapTypeObject, as_mapping);
5916         }
5917         else if ((size_t)offset >= offsetof(PyHeapTypeObject, as_number)) {
5918                 ptr = (char *)type->tp_as_number;
5919                 offset -= offsetof(PyHeapTypeObject, as_number);
5920         }
5921         else {
5922                 ptr = (char *)type;
5923         }
5924         if (ptr != NULL)
5925                 ptr += offset;
5926         return (void **)ptr;
5927 }
5928
5929 /* Length of array of slotdef pointers used to store slots with the
5930    same __name__.  There should be at most MAX_EQUIV-1 slotdef entries with
5931    the same __name__, for any __name__. Since that's a static property, it is
5932    appropriate to declare fixed-size arrays for this. */
5933 #define MAX_EQUIV 10
5934
5935 /* Return a slot pointer for a given name, but ONLY if the attribute has
5936    exactly one slot function.  The name must be an interned string. */
5937 static void **
5938 resolve_slotdups(PyTypeObject *type, PyObject *name)
5939 {
5940         /* XXX Maybe this could be optimized more -- but is it worth it? */
5941
5942         /* pname and ptrs act as a little cache */
5943         static PyObject *pname;
5944         static slotdef *ptrs[MAX_EQUIV];
5945         slotdef *p, **pp;
5946         void **res, **ptr;
5947
5948         if (pname != name) {
5949                 /* Collect all slotdefs that match name into ptrs. */
5950                 pname = name;
5951                 pp = ptrs;
5952                 for (p = slotdefs; p->name_strobj; p++) {
5953                         if (p->name_strobj == name)
5954                                 *pp++ = p;
5955                 }
5956                 *pp = NULL;
5957         }
5958
5959         /* Look in all matching slots of the type; if exactly one of these has
5960            a filled-in slot, return its value.  Otherwise return NULL. */
5961         res = NULL;
5962         for (pp = ptrs; *pp; pp++) {
5963                 ptr = slotptr(type, (*pp)->offset);
5964                 if (ptr == NULL || *ptr == NULL)
5965                         continue;
5966                 if (res != NULL)
5967                         return NULL;
5968                 res = ptr;
5969         }
5970         return res;
5971 }
5972
5973 /* Common code for update_slots_callback() and fixup_slot_dispatchers().  This
5974    does some incredibly complex thinking and then sticks something into the
5975    slot.  (It sees if the adjacent slotdefs for the same slot have conflicting
5976    interests, and then stores a generic wrapper or a specific function into
5977    the slot.)  Return a pointer to the next slotdef with a different offset,
5978    because that's convenient  for fixup_slot_dispatchers(). */
5979 static slotdef *
5980 update_one_slot(PyTypeObject *type, slotdef *p)
5981 {
5982         PyObject *descr;
5983         PyWrapperDescrObject *d;
5984         void *generic = NULL, *specific = NULL;
5985         int use_generic = 0;
5986         int offset = p->offset;
5987         void **ptr = slotptr(type, offset);
5988
5989         if (ptr == NULL) {
5990                 do {
5991                         ++p;
5992                 } while (p->offset == offset);
5993                 return p;
5994         }
5995         do {
5996                 descr = _PyType_Lookup(type, p->name_strobj);
5997                 if (descr == NULL)
5998                         continue;
5999                 if (Py_TYPE(descr) == &PyWrapperDescr_Type) {
6000                         void **tptr = resolve_slotdups(type, p->name_strobj);
6001                         if (tptr == NULL || tptr == ptr)
6002                                 generic = p->function;
6003                         d = (PyWrapperDescrObject *)descr;
6004                         if (d->d_base->wrapper == p->wrapper &&
6005                             PyType_IsSubtype(type, d->d_type))
6006                         {
6007                                 if (specific == NULL ||
6008                                     specific == d->d_wrapped)
6009                                         specific = d->d_wrapped;
6010                                 else
6011                                         use_generic = 1;
6012                         }
6013                 }
6014                 else if (Py_TYPE(descr) == &PyCFunction_Type &&
6015                          PyCFunction_GET_FUNCTION(descr) ==
6016                          (PyCFunction)tp_new_wrapper &&
6017                          strcmp(p->name, "__new__") == 0)
6018                 {
6019                         /* The __new__ wrapper is not a wrapper descriptor,
6020                            so must be special-cased differently.
6021                            If we don't do this, creating an instance will
6022                            always use slot_tp_new which will look up
6023                            __new__ in the MRO which will call tp_new_wrapper
6024                            which will look through the base classes looking
6025                            for a static base and call its tp_new (usually
6026                            PyType_GenericNew), after performing various
6027                            sanity checks and constructing a new argument
6028                            list.  Cut all that nonsense short -- this speeds
6029                            up instance creation tremendously. */
6030                         specific = (void *)type->tp_new;
6031                         /* XXX I'm not 100% sure that there isn't a hole
6032                            in this reasoning that requires additional
6033                            sanity checks.  I'll buy the first person to
6034                            point out a bug in this reasoning a beer. */
6035                 }
6036                 else if (descr == Py_None &&
6037                          strcmp(p->name, "__hash__") == 0) {
6038                         /* We specifically allow __hash__ to be set to None
6039                            to prevent inheritance of the default
6040                            implementation from object.__hash__ */
6041                         specific = PyObject_HashNotImplemented;
6042                 }
6043                 else {
6044                         use_generic = 1;
6045                         generic = p->function;
6046                 }
6047         } while ((++p)->offset == offset);
6048         if (specific && !use_generic)
6049                 *ptr = specific;
6050         else
6051                 *ptr = generic;
6052         return p;
6053 }
6054
6055 /* In the type, update the slots whose slotdefs are gathered in the pp array.
6056    This is a callback for update_subclasses(). */
6057 static int
6058 update_slots_callback(PyTypeObject *type, void *data)
6059 {
6060         slotdef **pp = (slotdef **)data;
6061
6062         for (; *pp; pp++)
6063                 update_one_slot(type, *pp);
6064         return 0;
6065 }
6066
6067 /* Comparison function for qsort() to compare slotdefs by their offset, and
6068    for equal offset by their address (to force a stable sort). */
6069 static int
6070 slotdef_cmp(const void *aa, const void *bb)
6071 {
6072         const slotdef *a = (const slotdef *)aa, *b = (const slotdef *)bb;
6073         int c = a->offset - b->offset;
6074         if (c != 0)
6075                 return c;
6076         else
6077                 /* Cannot use a-b, as this gives off_t,
6078                    which may lose precision when converted to int. */
6079                 return (a > b) ? 1 : (a < b) ? -1 : 0;
6080 }
6081
6082 /* Initialize the slotdefs table by adding interned string objects for the
6083    names and sorting the entries. */
6084 static void
6085 init_slotdefs(void)
6086 {
6087         slotdef *p;
6088         static int initialized = 0;
6089
6090         if (initialized)
6091                 return;
6092         for (p = slotdefs; p->name; p++) {
6093                 p->name_strobj = PyString_InternFromString(p->name);
6094                 if (!p->name_strobj)
6095                         Py_FatalError("Out of memory interning slotdef names");
6096         }
6097         qsort((void *)slotdefs, (size_t)(p-slotdefs), sizeof(slotdef),
6098               slotdef_cmp);
6099         initialized = 1;
6100 }
6101
6102 /* Update the slots after assignment to a class (type) attribute. */
6103 static int
6104 update_slot(PyTypeObject *type, PyObject *name)
6105 {
6106         slotdef *ptrs[MAX_EQUIV];
6107         slotdef *p;
6108         slotdef **pp;
6109         int offset;
6110
6111         /* Clear the VALID_VERSION flag of 'type' and all its
6112            subclasses.  This could possibly be unified with the
6113            update_subclasses() recursion below, but carefully:
6114            they each have their own conditions on which to stop
6115            recursing into subclasses. */
6116         PyType_Modified(type);
6117
6118         init_slotdefs();
6119         pp = ptrs;
6120         for (p = slotdefs; p->name; p++) {
6121                 /* XXX assume name is interned! */
6122                 if (p->name_strobj == name)
6123                         *pp++ = p;
6124         }
6125         *pp = NULL;
6126         for (pp = ptrs; *pp; pp++) {
6127                 p = *pp;
6128                 offset = p->offset;
6129                 while (p > slotdefs && (p-1)->offset == offset)
6130                         --p;
6131                 *pp = p;
6132         }
6133         if (ptrs[0] == NULL)
6134                 return 0; /* Not an attribute that affects any slots */
6135         return update_subclasses(type, name,
6136                                  update_slots_callback, (void *)ptrs);
6137 }
6138
6139 /* Store the proper functions in the slot dispatches at class (type)
6140    definition time, based upon which operations the class overrides in its
6141    dict. */
6142 static void
6143 fixup_slot_dispatchers(PyTypeObject *type)
6144 {
6145         slotdef *p;
6146
6147         init_slotdefs();
6148         for (p = slotdefs; p->name; )
6149                 p = update_one_slot(type, p);
6150 }
6151
6152 static void
6153 update_all_slots(PyTypeObject* type)
6154 {
6155         slotdef *p;
6156
6157         init_slotdefs();
6158         for (p = slotdefs; p->name; p++) {
6159                 /* update_slot returns int but can't actually fail */
6160                 update_slot(type, p->name_strobj);
6161         }
6162 }
6163
6164 /* recurse_down_subclasses() and update_subclasses() are mutually
6165    recursive functions to call a callback for all subclasses,
6166    but refraining from recursing into subclasses that define 'name'. */
6167
6168 static int
6169 update_subclasses(PyTypeObject *type, PyObject *name,
6170                   update_callback callback, void *data)
6171 {
6172         if (callback(type, data) < 0)
6173                 return -1;
6174         return recurse_down_subclasses(type, name, callback, data);
6175 }
6176
6177 static int
6178 recurse_down_subclasses(PyTypeObject *type, PyObject *name,
6179                         update_callback callback, void *data)
6180 {
6181         PyTypeObject *subclass;
6182         PyObject *ref, *subclasses, *dict;
6183         Py_ssize_t i, n;
6184
6185         subclasses = type->tp_subclasses;
6186         if (subclasses == NULL)
6187                 return 0;
6188         assert(PyList_Check(subclasses));
6189         n = PyList_GET_SIZE(subclasses);
6190         for (i = 0; i < n; i++) {
6191                 ref = PyList_GET_ITEM(subclasses, i);
6192                 assert(PyWeakref_CheckRef(ref));
6193                 subclass = (PyTypeObject *)PyWeakref_GET_OBJECT(ref);
6194                 assert(subclass != NULL);
6195                 if ((PyObject *)subclass == Py_None)
6196                         continue;
6197                 assert(PyType_Check(subclass));
6198                 /* Avoid recursing down into unaffected classes */
6199                 dict = subclass->tp_dict;
6200                 if (dict != NULL && PyDict_Check(dict) &&
6201                     PyDict_GetItem(dict, name) != NULL)
6202                         continue;
6203                 if (update_subclasses(subclass, name, callback, data) < 0)
6204                         return -1;
6205         }
6206         return 0;
6207 }
6208
6209 /* This function is called by PyType_Ready() to populate the type's
6210    dictionary with method descriptors for function slots.  For each
6211    function slot (like tp_repr) that's defined in the type, one or more
6212    corresponding descriptors are added in the type's tp_dict dictionary
6213    under the appropriate name (like __repr__).  Some function slots
6214    cause more than one descriptor to be added (for example, the nb_add
6215    slot adds both __add__ and __radd__ descriptors) and some function
6216    slots compete for the same descriptor (for example both sq_item and
6217    mp_subscript generate a __getitem__ descriptor).
6218
6219    In the latter case, the first slotdef entry encoutered wins.  Since
6220    slotdef entries are sorted by the offset of the slot in the
6221    PyHeapTypeObject, this gives us some control over disambiguating
6222    between competing slots: the members of PyHeapTypeObject are listed
6223    from most general to least general, so the most general slot is
6224    preferred.  In particular, because as_mapping comes before as_sequence,
6225    for a type that defines both mp_subscript and sq_item, mp_subscript
6226    wins.
6227
6228    This only adds new descriptors and doesn't overwrite entries in
6229    tp_dict that were previously defined.  The descriptors contain a
6230    reference to the C function they must call, so that it's safe if they
6231    are copied into a subtype's __dict__ and the subtype has a different
6232    C function in its slot -- calling the method defined by the
6233    descriptor will call the C function that was used to create it,
6234    rather than the C function present in the slot when it is called.
6235    (This is important because a subtype may have a C function in the
6236    slot that calls the method from the dictionary, and we want to avoid
6237    infinite recursion here.) */
6238
6239 static int
6240 add_operators(PyTypeObject *type)
6241 {
6242         PyObject *dict = type->tp_dict;
6243         slotdef *p;
6244         PyObject *descr;
6245         void **ptr;
6246
6247         init_slotdefs();
6248         for (p = slotdefs; p->name; p++) {
6249                 if (p->wrapper == NULL)
6250                         continue;
6251                 ptr = slotptr(type, p->offset);
6252                 if (!ptr || !*ptr)
6253                         continue;
6254                 if (PyDict_GetItem(dict, p->name_strobj))
6255                         continue;
6256                 if (*ptr == PyObject_HashNotImplemented) {
6257                         /* Classes may prevent the inheritance of the tp_hash
6258                            slot by storing PyObject_HashNotImplemented in it. Make it
6259                            visible as a None value for the __hash__ attribute. */
6260                         if (PyDict_SetItem(dict, p->name_strobj, Py_None) < 0)
6261                                 return -1;
6262                 }
6263                 else {
6264                         descr = PyDescr_NewWrapper(type, p, *ptr);
6265                         if (descr == NULL)
6266                                 return -1;
6267                         if (PyDict_SetItem(dict, p->name_strobj, descr) < 0)
6268                                 return -1;
6269                         Py_DECREF(descr);
6270                 }
6271         }
6272         if (type->tp_new != NULL) {
6273                 if (add_tp_new_wrapper(type) < 0)
6274                         return -1;
6275         }
6276         return 0;
6277 }
6278
6279
6280 /* Cooperative 'super' */
6281
6282 typedef struct {
6283         PyObject_HEAD
6284         PyTypeObject *type;
6285         PyObject *obj;
6286         PyTypeObject *obj_type;
6287 } superobject;
6288
6289 static PyMemberDef super_members[] = {
6290         {"__thisclass__", T_OBJECT, offsetof(superobject, type), READONLY,
6291          "the class invoking super()"},
6292         {"__self__",  T_OBJECT, offsetof(superobject, obj), READONLY,
6293          "the instance invoking super(); may be None"},
6294         {"__self_class__", T_OBJECT, offsetof(superobject, obj_type), READONLY,
6295          "the type of the instance invoking super(); may be None"},
6296         {0}
6297 };
6298
6299 static void
6300 super_dealloc(PyObject *self)
6301 {
6302         superobject *su = (superobject *)self;
6303
6304         _PyObject_GC_UNTRACK(self);
6305         Py_XDECREF(su->obj);
6306         Py_XDECREF(su->type);
6307         Py_XDECREF(su->obj_type);
6308         Py_TYPE(self)->tp_free(self);
6309 }
6310
6311 static PyObject *
6312 super_repr(PyObject *self)
6313 {
6314         superobject *su = (superobject *)self;
6315
6316         if (su->obj_type)
6317                 return PyString_FromFormat(
6318                         "<super: <class '%s'>, <%s object>>",
6319                         su->type ? su->type->tp_name : "NULL",
6320                         su->obj_type->tp_name);
6321         else
6322                 return PyString_FromFormat(
6323                         "<super: <class '%s'>, NULL>",
6324                         su->type ? su->type->tp_name : "NULL");
6325 }
6326
6327 static PyObject *
6328 super_getattro(PyObject *self, PyObject *name)
6329 {
6330         superobject *su = (superobject *)self;
6331         int skip = su->obj_type == NULL;
6332
6333         if (!skip) {
6334                 /* We want __class__ to return the class of the super object
6335                    (i.e. super, or a subclass), not the class of su->obj. */
6336                 skip = (PyString_Check(name) &&
6337                         PyString_GET_SIZE(name) == 9 &&
6338                         strcmp(PyString_AS_STRING(name), "__class__") == 0);
6339         }
6340
6341         if (!skip) {
6342                 PyObject *mro, *res, *tmp, *dict;
6343                 PyTypeObject *starttype;
6344                 descrgetfunc f;
6345                 Py_ssize_t i, n;
6346
6347                 starttype = su->obj_type;
6348                 mro = starttype->tp_mro;
6349
6350                 if (mro == NULL)
6351                         n = 0;
6352                 else {
6353                         assert(PyTuple_Check(mro));
6354                         n = PyTuple_GET_SIZE(mro);
6355                 }
6356                 for (i = 0; i < n; i++) {
6357                         if ((PyObject *)(su->type) == PyTuple_GET_ITEM(mro, i))
6358                                 break;
6359                 }
6360                 i++;
6361                 res = NULL;
6362                 for (; i < n; i++) {
6363                         tmp = PyTuple_GET_ITEM(mro, i);
6364                         if (PyType_Check(tmp))
6365                                 dict = ((PyTypeObject *)tmp)->tp_dict;
6366                         else if (PyClass_Check(tmp))
6367                                 dict = ((PyClassObject *)tmp)->cl_dict;
6368                         else
6369                                 continue;
6370                         res = PyDict_GetItem(dict, name);
6371                         if (res != NULL) {
6372                                 Py_INCREF(res);
6373                                 f = Py_TYPE(res)->tp_descr_get;
6374                                 if (f != NULL) {
6375                                         tmp = f(res,
6376                                                 /* Only pass 'obj' param if
6377                                                    this is instance-mode super
6378                                                    (See SF ID #743627)
6379                                                 */
6380                                                 (su->obj == (PyObject *)
6381                                                             su->obj_type
6382                                                         ? (PyObject *)NULL
6383                                                         : su->obj),
6384                                                 (PyObject *)starttype);
6385                                         Py_DECREF(res);
6386                                         res = tmp;
6387                                 }
6388                                 return res;
6389                         }
6390                 }
6391         }
6392         return PyObject_GenericGetAttr(self, name);
6393 }
6394
6395 static PyTypeObject *
6396 supercheck(PyTypeObject *type, PyObject *obj)
6397 {
6398         /* Check that a super() call makes sense.  Return a type object.
6399
6400            obj can be a new-style class, or an instance of one:
6401
6402            - If it is a class, it must be a subclass of 'type'.  This case is
6403              used for class methods; the return value is obj.
6404
6405            - If it is an instance, it must be an instance of 'type'.  This is
6406              the normal case; the return value is obj.__class__.
6407
6408            But... when obj is an instance, we want to allow for the case where
6409            Py_TYPE(obj) is not a subclass of type, but obj.__class__ is!
6410            This will allow using super() with a proxy for obj.
6411         */
6412
6413         /* Check for first bullet above (special case) */
6414         if (PyType_Check(obj) && PyType_IsSubtype((PyTypeObject *)obj, type)) {
6415                 Py_INCREF(obj);
6416                 return (PyTypeObject *)obj;
6417         }
6418
6419         /* Normal case */
6420         if (PyType_IsSubtype(Py_TYPE(obj), type)) {
6421                 Py_INCREF(Py_TYPE(obj));
6422                 return Py_TYPE(obj);
6423         }
6424         else {
6425                 /* Try the slow way */
6426                 static PyObject *class_str = NULL;
6427                 PyObject *class_attr;
6428
6429                 if (class_str == NULL) {
6430                         class_str = PyString_FromString("__class__");
6431                         if (class_str == NULL)
6432                                 return NULL;
6433                 }
6434
6435                 class_attr = PyObject_GetAttr(obj, class_str);
6436
6437                 if (class_attr != NULL &&
6438                     PyType_Check(class_attr) &&
6439                     (PyTypeObject *)class_attr != Py_TYPE(obj))
6440                 {
6441                         int ok = PyType_IsSubtype(
6442                                 (PyTypeObject *)class_attr, type);
6443                         if (ok)
6444                                 return (PyTypeObject *)class_attr;
6445                 }
6446
6447                 if (class_attr == NULL)
6448                         PyErr_Clear();
6449                 else
6450                         Py_DECREF(class_attr);
6451         }
6452
6453         PyErr_SetString(PyExc_TypeError,
6454                         "super(type, obj): "
6455                         "obj must be an instance or subtype of type");
6456         return NULL;
6457 }
6458
6459 static PyObject *
6460 super_descr_get(PyObject *self, PyObject *obj, PyObject *type)
6461 {
6462         superobject *su = (superobject *)self;
6463         superobject *newobj;
6464
6465         if (obj == NULL || obj == Py_None || su->obj != NULL) {
6466                 /* Not binding to an object, or already bound */
6467                 Py_INCREF(self);
6468                 return self;
6469         }
6470         if (Py_TYPE(su) != &PySuper_Type)
6471                 /* If su is an instance of a (strict) subclass of super,
6472                    call its type */
6473                 return PyObject_CallFunctionObjArgs((PyObject *)Py_TYPE(su),
6474                                                     su->type, obj, NULL);
6475         else {
6476                 /* Inline the common case */
6477                 PyTypeObject *obj_type = supercheck(su->type, obj);
6478                 if (obj_type == NULL)
6479                         return NULL;
6480                 newobj = (superobject *)PySuper_Type.tp_new(&PySuper_Type,
6481                                                          NULL, NULL);
6482                 if (newobj == NULL)
6483                         return NULL;
6484                 Py_INCREF(su->type);
6485                 Py_INCREF(obj);
6486                 newobj->type = su->type;
6487                 newobj->obj = obj;
6488                 newobj->obj_type = obj_type;
6489                 return (PyObject *)newobj;
6490         }
6491 }
6492
6493 static int
6494 super_init(PyObject *self, PyObject *args, PyObject *kwds)
6495 {
6496         superobject *su = (superobject *)self;
6497         PyTypeObject *type;
6498         PyObject *obj = NULL;
6499         PyTypeObject *obj_type = NULL;
6500
6501         if (!_PyArg_NoKeywords("super", kwds))
6502                 return -1;
6503         if (!PyArg_ParseTuple(args, "O!|O:super", &PyType_Type, &type, &obj))
6504                 return -1;
6505         if (obj == Py_None)
6506                 obj = NULL;
6507         if (obj != NULL) {
6508                 obj_type = supercheck(type, obj);
6509                 if (obj_type == NULL)
6510                         return -1;
6511                 Py_INCREF(obj);
6512         }
6513         Py_INCREF(type);
6514         su->type = type;
6515         su->obj = obj;
6516         su->obj_type = obj_type;
6517         return 0;
6518 }
6519
6520 PyDoc_STRVAR(super_doc,
6521 "super(type) -> unbound super object\n"
6522 "super(type, obj) -> bound super object; requires isinstance(obj, type)\n"
6523 "super(type, type2) -> bound super object; requires issubclass(type2, type)\n"
6524 "Typical use to call a cooperative superclass method:\n"
6525 "class C(B):\n"
6526 "    def meth(self, arg):\n"
6527 "        super(C, self).meth(arg)");
6528
6529 static int
6530 super_traverse(PyObject *self, visitproc visit, void *arg)
6531 {
6532         superobject *su = (superobject *)self;
6533
6534         Py_VISIT(su->obj);
6535         Py_VISIT(su->type);
6536         Py_VISIT(su->obj_type);
6537
6538         return 0;
6539 }
6540
6541 PyTypeObject PySuper_Type = {
6542         PyVarObject_HEAD_INIT(&PyType_Type, 0)
6543         "super",                                /* tp_name */
6544         sizeof(superobject),                    /* tp_basicsize */
6545         0,                                      /* tp_itemsize */
6546         /* methods */
6547         super_dealloc,                          /* tp_dealloc */
6548         0,                                      /* tp_print */
6549         0,                                      /* tp_getattr */
6550         0,                                      /* tp_setattr */
6551         0,                                      /* tp_compare */
6552         super_repr,                             /* tp_repr */
6553         0,                                      /* tp_as_number */
6554         0,                                      /* tp_as_sequence */
6555         0,                                      /* tp_as_mapping */
6556         0,                                      /* tp_hash */
6557         0,                                      /* tp_call */
6558         0,                                      /* tp_str */
6559         super_getattro,                         /* tp_getattro */
6560         0,                                      /* tp_setattro */
6561         0,                                      /* tp_as_buffer */
6562         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
6563                 Py_TPFLAGS_BASETYPE,            /* tp_flags */
6564         super_doc,                              /* tp_doc */
6565         super_traverse,                         /* tp_traverse */
6566         0,                                      /* tp_clear */
6567         0,                                      /* tp_richcompare */
6568         0,                                      /* tp_weaklistoffset */
6569         0,                                      /* tp_iter */
6570         0,                                      /* tp_iternext */
6571         0,                                      /* tp_methods */
6572         super_members,                          /* tp_members */
6573         0,                                      /* tp_getset */
6574         0,                                      /* tp_base */
6575         0,                                      /* tp_dict */
6576         super_descr_get,                        /* tp_descr_get */
6577         0,                                      /* tp_descr_set */
6578         0,                                      /* tp_dictoffset */
6579         super_init,                             /* tp_init */
6580         PyType_GenericAlloc,                    /* tp_alloc */
6581         PyType_GenericNew,                      /* tp_new */
6582         PyObject_GC_Del,                        /* tp_free */
6583 };