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