1 /* ABCMeta implementation */
2 #ifndef Py_BUILD_CORE_BUILTIN
3 #  define Py_BUILD_CORE_MODULE 1
4 #endif
5 
6 #include "Python.h"
7 #include "pycore_moduleobject.h"  // _PyModule_GetState()
8 #include "pycore_object.h"        // _PyType_GetSubclasses()
9 #include "pycore_runtime.h"       // _Py_ID()
10 #include "clinic/_abc.c.h"
11 
12 /*[clinic input]
13 module _abc
14 [clinic start generated code]*/
15 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=964f5328e1aefcda]*/
16 
17 PyDoc_STRVAR(_abc__doc__,
18 "Module contains faster C implementation of abc.ABCMeta");
19 
20 typedef struct {
21     PyTypeObject *_abc_data_type;
22     unsigned long long abc_invalidation_counter;
23 } _abcmodule_state;
24 
25 static inline _abcmodule_state*
get_abc_state(PyObject * module)26 get_abc_state(PyObject *module)
27 {
28     void *state = _PyModule_GetState(module);
29     assert(state != NULL);
30     return (_abcmodule_state *)state;
31 }
32 
33 /* This object stores internal state for ABCs.
34    Note that we can use normal sets for caches,
35    since they are never iterated over. */
36 typedef struct {
37     PyObject_HEAD
38     PyObject *_abc_registry;
39     PyObject *_abc_cache; /* Normal set of weak references. */
40     PyObject *_abc_negative_cache; /* Normal set of weak references. */
41     unsigned long long _abc_negative_cache_version;
42 } _abc_data;
43 
44 static int
abc_data_traverse(_abc_data * self,visitproc visit,void * arg)45 abc_data_traverse(_abc_data *self, visitproc visit, void *arg)
46 {
47     Py_VISIT(Py_TYPE(self));
48     Py_VISIT(self->_abc_registry);
49     Py_VISIT(self->_abc_cache);
50     Py_VISIT(self->_abc_negative_cache);
51     return 0;
52 }
53 
54 static int
abc_data_clear(_abc_data * self)55 abc_data_clear(_abc_data *self)
56 {
57     Py_CLEAR(self->_abc_registry);
58     Py_CLEAR(self->_abc_cache);
59     Py_CLEAR(self->_abc_negative_cache);
60     return 0;
61 }
62 
63 static void
abc_data_dealloc(_abc_data * self)64 abc_data_dealloc(_abc_data *self)
65 {
66     PyObject_GC_UnTrack(self);
67     PyTypeObject *tp = Py_TYPE(self);
68     (void)abc_data_clear(self);
69     tp->tp_free(self);
70     Py_DECREF(tp);
71 }
72 
73 static PyObject *
abc_data_new(PyTypeObject * type,PyObject * args,PyObject * kwds)74 abc_data_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
75 {
76     _abc_data *self = (_abc_data *) type->tp_alloc(type, 0);
77     _abcmodule_state *state = NULL;
78     if (self == NULL) {
79         return NULL;
80     }
81 
82     state = PyType_GetModuleState(type);
83     if (state == NULL) {
84         Py_DECREF(self);
85         return NULL;
86     }
87 
88     self->_abc_registry = NULL;
89     self->_abc_cache = NULL;
90     self->_abc_negative_cache = NULL;
91     self->_abc_negative_cache_version = state->abc_invalidation_counter;
92     return (PyObject *) self;
93 }
94 
95 PyDoc_STRVAR(abc_data_doc,
96 "Internal state held by ABC machinery.");
97 
98 static PyType_Slot _abc_data_type_spec_slots[] = {
99     {Py_tp_doc, (void *)abc_data_doc},
100     {Py_tp_new, abc_data_new},
101     {Py_tp_dealloc, abc_data_dealloc},
102     {Py_tp_traverse, abc_data_traverse},
103     {Py_tp_clear, abc_data_clear},
104     {0, 0}
105 };
106 
107 static PyType_Spec _abc_data_type_spec = {
108     .name = "_abc._abc_data",
109     .basicsize = sizeof(_abc_data),
110     .flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,
111     .slots = _abc_data_type_spec_slots,
112 };
113 
114 static _abc_data *
_get_impl(PyObject * module,PyObject * self)115 _get_impl(PyObject *module, PyObject *self)
116 {
117     _abcmodule_state *state = get_abc_state(module);
118     PyObject *impl = PyObject_GetAttr(self, &_Py_ID(_abc_impl));
119     if (impl == NULL) {
120         return NULL;
121     }
122     if (!Py_IS_TYPE(impl, state->_abc_data_type)) {
123         PyErr_SetString(PyExc_TypeError, "_abc_impl is set to a wrong type");
124         Py_DECREF(impl);
125         return NULL;
126     }
127     return (_abc_data *)impl;
128 }
129 
130 static int
_in_weak_set(PyObject * set,PyObject * obj)131 _in_weak_set(PyObject *set, PyObject *obj)
132 {
133     if (set == NULL || PySet_GET_SIZE(set) == 0) {
134         return 0;
135     }
136     PyObject *ref = PyWeakref_NewRef(obj, NULL);
137     if (ref == NULL) {
138         if (PyErr_ExceptionMatches(PyExc_TypeError)) {
139             PyErr_Clear();
140             return 0;
141         }
142         return -1;
143     }
144     int res = PySet_Contains(set, ref);
145     Py_DECREF(ref);
146     return res;
147 }
148 
149 static PyObject *
_destroy(PyObject * setweakref,PyObject * objweakref)150 _destroy(PyObject *setweakref, PyObject *objweakref)
151 {
152     PyObject *set;
153     set = PyWeakref_GET_OBJECT(setweakref);
154     if (set == Py_None) {
155         Py_RETURN_NONE;
156     }
157     Py_INCREF(set);
158     if (PySet_Discard(set, objweakref) < 0) {
159         Py_DECREF(set);
160         return NULL;
161     }
162     Py_DECREF(set);
163     Py_RETURN_NONE;
164 }
165 
166 static PyMethodDef _destroy_def = {
167     "_destroy", (PyCFunction) _destroy, METH_O
168 };
169 
170 static int
_add_to_weak_set(PyObject ** pset,PyObject * obj)171 _add_to_weak_set(PyObject **pset, PyObject *obj)
172 {
173     if (*pset == NULL) {
174         *pset = PySet_New(NULL);
175         if (*pset == NULL) {
176             return -1;
177         }
178     }
179 
180     PyObject *set = *pset;
181     PyObject *ref, *wr;
182     PyObject *destroy_cb;
183     wr = PyWeakref_NewRef(set, NULL);
184     if (wr == NULL) {
185         return -1;
186     }
187     destroy_cb = PyCFunction_NewEx(&_destroy_def, wr, NULL);
188     if (destroy_cb == NULL) {
189         Py_DECREF(wr);
190         return -1;
191     }
192     ref = PyWeakref_NewRef(obj, destroy_cb);
193     Py_DECREF(destroy_cb);
194     if (ref == NULL) {
195         Py_DECREF(wr);
196         return -1;
197     }
198     int ret = PySet_Add(set, ref);
199     Py_DECREF(wr);
200     Py_DECREF(ref);
201     return ret;
202 }
203 
204 /*[clinic input]
205 _abc._reset_registry
206 
207     self: object
208     /
209 
210 Internal ABC helper to reset registry of a given class.
211 
212 Should be only used by refleak.py
213 [clinic start generated code]*/
214 
215 static PyObject *
_abc__reset_registry(PyObject * module,PyObject * self)216 _abc__reset_registry(PyObject *module, PyObject *self)
217 /*[clinic end generated code: output=92d591a43566cc10 input=12a0b7eb339ac35c]*/
218 {
219     _abc_data *impl = _get_impl(module, self);
220     if (impl == NULL) {
221         return NULL;
222     }
223     if (impl->_abc_registry != NULL && PySet_Clear(impl->_abc_registry) < 0) {
224         Py_DECREF(impl);
225         return NULL;
226     }
227     Py_DECREF(impl);
228     Py_RETURN_NONE;
229 }
230 
231 /*[clinic input]
232 _abc._reset_caches
233 
234     self: object
235     /
236 
237 Internal ABC helper to reset both caches of a given class.
238 
239 Should be only used by refleak.py
240 [clinic start generated code]*/
241 
242 static PyObject *
_abc__reset_caches(PyObject * module,PyObject * self)243 _abc__reset_caches(PyObject *module, PyObject *self)
244 /*[clinic end generated code: output=f296f0d5c513f80c input=c0ac616fd8acfb6f]*/
245 {
246     _abc_data *impl = _get_impl(module, self);
247     if (impl == NULL) {
248         return NULL;
249     }
250     if (impl->_abc_cache != NULL && PySet_Clear(impl->_abc_cache) < 0) {
251         Py_DECREF(impl);
252         return NULL;
253     }
254     /* also the second cache */
255     if (impl->_abc_negative_cache != NULL &&
256             PySet_Clear(impl->_abc_negative_cache) < 0) {
257         Py_DECREF(impl);
258         return NULL;
259     }
260     Py_DECREF(impl);
261     Py_RETURN_NONE;
262 }
263 
264 /*[clinic input]
265 _abc._get_dump
266 
267     self: object
268     /
269 
270 Internal ABC helper for cache and registry debugging.
271 
272 Return shallow copies of registry, of both caches, and
273 negative cache version. Don't call this function directly,
274 instead use ABC._dump_registry() for a nice repr.
275 [clinic start generated code]*/
276 
277 static PyObject *
_abc__get_dump(PyObject * module,PyObject * self)278 _abc__get_dump(PyObject *module, PyObject *self)
279 /*[clinic end generated code: output=9d9569a8e2c1c443 input=2c5deb1bfe9e3c79]*/
280 {
281     _abc_data *impl = _get_impl(module, self);
282     if (impl == NULL) {
283         return NULL;
284     }
285     PyObject *res = Py_BuildValue("NNNK",
286                                   PySet_New(impl->_abc_registry),
287                                   PySet_New(impl->_abc_cache),
288                                   PySet_New(impl->_abc_negative_cache),
289                                   impl->_abc_negative_cache_version);
290     Py_DECREF(impl);
291     return res;
292 }
293 
294 // Compute set of abstract method names.
295 static int
compute_abstract_methods(PyObject * self)296 compute_abstract_methods(PyObject *self)
297 {
298     int ret = -1;
299     PyObject *abstracts = PyFrozenSet_New(NULL);
300     if (abstracts == NULL) {
301         return -1;
302     }
303 
304     PyObject *ns = NULL, *items = NULL, *bases = NULL;  // Py_XDECREF()ed on error.
305 
306     /* Stage 1: direct abstract methods. */
307     ns = PyObject_GetAttr(self, &_Py_ID(__dict__));
308     if (!ns) {
309         goto error;
310     }
311 
312     // We can't use PyDict_Next(ns) even when ns is dict because
313     // _PyObject_IsAbstract() can mutate ns.
314     items = PyMapping_Items(ns);
315     if (!items) {
316         goto error;
317     }
318     assert(PyList_Check(items));
319     for (Py_ssize_t pos = 0; pos < PyList_GET_SIZE(items); pos++) {
320         PyObject *it = PySequence_Fast(
321                 PyList_GET_ITEM(items, pos),
322                 "items() returned non-iterable");
323         if (!it) {
324             goto error;
325         }
326         if (PySequence_Fast_GET_SIZE(it) != 2) {
327             PyErr_SetString(PyExc_TypeError,
328                             "items() returned item which size is not 2");
329             Py_DECREF(it);
330             goto error;
331         }
332 
333         // borrowed
334         PyObject *key = PySequence_Fast_GET_ITEM(it, 0);
335         PyObject *value = PySequence_Fast_GET_ITEM(it, 1);
336         // items or it may be cleared while accessing __abstractmethod__
337         // So we need to keep strong reference for key
338         Py_INCREF(key);
339         int is_abstract = _PyObject_IsAbstract(value);
340         if (is_abstract < 0 ||
341                 (is_abstract && PySet_Add(abstracts, key) < 0)) {
342             Py_DECREF(it);
343             Py_DECREF(key);
344             goto error;
345         }
346         Py_DECREF(key);
347         Py_DECREF(it);
348     }
349 
350     /* Stage 2: inherited abstract methods. */
351     bases = PyObject_GetAttr(self, &_Py_ID(__bases__));
352     if (!bases) {
353         goto error;
354     }
355     if (!PyTuple_Check(bases)) {
356         PyErr_SetString(PyExc_TypeError, "__bases__ is not tuple");
357         goto error;
358     }
359 
360     for (Py_ssize_t pos = 0; pos < PyTuple_GET_SIZE(bases); pos++) {
361         PyObject *item = PyTuple_GET_ITEM(bases, pos);  // borrowed
362         PyObject *base_abstracts, *iter;
363 
364         if (_PyObject_LookupAttr(item, &_Py_ID(__abstractmethods__),
365                                  &base_abstracts) < 0) {
366             goto error;
367         }
368         if (base_abstracts == NULL) {
369             continue;
370         }
371         if (!(iter = PyObject_GetIter(base_abstracts))) {
372             Py_DECREF(base_abstracts);
373             goto error;
374         }
375         Py_DECREF(base_abstracts);
376         PyObject *key, *value;
377         while ((key = PyIter_Next(iter))) {
378             if (_PyObject_LookupAttr(self, key, &value) < 0) {
379                 Py_DECREF(key);
380                 Py_DECREF(iter);
381                 goto error;
382             }
383             if (value == NULL) {
384                 Py_DECREF(key);
385                 continue;
386             }
387 
388             int is_abstract = _PyObject_IsAbstract(value);
389             Py_DECREF(value);
390             if (is_abstract < 0 ||
391                     (is_abstract && PySet_Add(abstracts, key) < 0))
392             {
393                 Py_DECREF(key);
394                 Py_DECREF(iter);
395                 goto error;
396             }
397             Py_DECREF(key);
398         }
399         Py_DECREF(iter);
400         if (PyErr_Occurred()) {
401             goto error;
402         }
403     }
404 
405     if (PyObject_SetAttr(self, &_Py_ID(__abstractmethods__), abstracts) < 0) {
406         goto error;
407     }
408 
409     ret = 0;
410 error:
411     Py_DECREF(abstracts);
412     Py_XDECREF(ns);
413     Py_XDECREF(items);
414     Py_XDECREF(bases);
415     return ret;
416 }
417 
418 #define COLLECTION_FLAGS (Py_TPFLAGS_SEQUENCE | Py_TPFLAGS_MAPPING)
419 
420 /*[clinic input]
421 _abc._abc_init
422 
423     self: object
424     /
425 
426 Internal ABC helper for class set-up. Should be never used outside abc module.
427 [clinic start generated code]*/
428 
429 static PyObject *
_abc__abc_init(PyObject * module,PyObject * self)430 _abc__abc_init(PyObject *module, PyObject *self)
431 /*[clinic end generated code: output=594757375714cda1 input=8d7fe470ff77f029]*/
432 {
433     _abcmodule_state *state = get_abc_state(module);
434     PyObject *data;
435     if (compute_abstract_methods(self) < 0) {
436         return NULL;
437     }
438 
439     /* Set up inheritance registry. */
440     data = abc_data_new(state->_abc_data_type, NULL, NULL);
441     if (data == NULL) {
442         return NULL;
443     }
444     if (PyObject_SetAttr(self, &_Py_ID(_abc_impl), data) < 0) {
445         Py_DECREF(data);
446         return NULL;
447     }
448     Py_DECREF(data);
449     /* If __abc_tpflags__ & COLLECTION_FLAGS is set, then set the corresponding bit(s)
450      * in the new class.
451      * Used by collections.abc.Sequence and collections.abc.Mapping to indicate
452      * their special status w.r.t. pattern matching. */
453     if (PyType_Check(self)) {
454         PyTypeObject *cls = (PyTypeObject *)self;
455         PyObject *flags = PyDict_GetItemWithError(cls->tp_dict,
456                                                   &_Py_ID(__abc_tpflags__));
457         if (flags == NULL) {
458             if (PyErr_Occurred()) {
459                 return NULL;
460             }
461         }
462         else {
463             if (PyLong_CheckExact(flags)) {
464                 long val = PyLong_AsLong(flags);
465                 if (val == -1 && PyErr_Occurred()) {
466                     return NULL;
467                 }
468                 if ((val & COLLECTION_FLAGS) == COLLECTION_FLAGS) {
469                     PyErr_SetString(PyExc_TypeError, "__abc_tpflags__ cannot be both Py_TPFLAGS_SEQUENCE and Py_TPFLAGS_MAPPING");
470                     return NULL;
471                 }
472                 ((PyTypeObject *)self)->tp_flags |= (val & COLLECTION_FLAGS);
473             }
474             if (PyDict_DelItem(cls->tp_dict, &_Py_ID(__abc_tpflags__)) < 0) {
475                 return NULL;
476             }
477         }
478     }
479     Py_RETURN_NONE;
480 }
481 
482 static void
set_collection_flag_recursive(PyTypeObject * child,unsigned long flag)483 set_collection_flag_recursive(PyTypeObject *child, unsigned long flag)
484 {
485     assert(flag == Py_TPFLAGS_MAPPING || flag == Py_TPFLAGS_SEQUENCE);
486     if (PyType_HasFeature(child, Py_TPFLAGS_IMMUTABLETYPE) ||
487         (child->tp_flags & COLLECTION_FLAGS) == flag)
488     {
489         return;
490     }
491 
492     child->tp_flags &= ~COLLECTION_FLAGS;
493     child->tp_flags |= flag;
494 
495     PyObject *grandchildren = _PyType_GetSubclasses(child);
496     if (grandchildren == NULL) {
497         return;
498     }
499 
500     for (Py_ssize_t i = 0; i < PyList_GET_SIZE(grandchildren); i++) {
501         PyObject *grandchild = PyList_GET_ITEM(grandchildren, i);
502         set_collection_flag_recursive((PyTypeObject *)grandchild, flag);
503     }
504     Py_DECREF(grandchildren);
505 }
506 
507 /*[clinic input]
508 _abc._abc_register
509 
510     self: object
511     subclass: object
512     /
513 
514 Internal ABC helper for subclasss registration. Should be never used outside abc module.
515 [clinic start generated code]*/
516 
517 static PyObject *
_abc__abc_register_impl(PyObject * module,PyObject * self,PyObject * subclass)518 _abc__abc_register_impl(PyObject *module, PyObject *self, PyObject *subclass)
519 /*[clinic end generated code: output=7851e7668c963524 input=ca589f8c3080e67f]*/
520 {
521     if (!PyType_Check(subclass)) {
522         PyErr_SetString(PyExc_TypeError, "Can only register classes");
523         return NULL;
524     }
525     int result = PyObject_IsSubclass(subclass, self);
526     if (result > 0) {
527         Py_INCREF(subclass);
528         return subclass;  /* Already a subclass. */
529     }
530     if (result < 0) {
531         return NULL;
532     }
533     /* Subtle: test for cycles *after* testing for "already a subclass";
534        this means we allow X.register(X) and interpret it as a no-op. */
535     result = PyObject_IsSubclass(self, subclass);
536     if (result > 0) {
537         /* This would create a cycle, which is bad for the algorithm below. */
538         PyErr_SetString(PyExc_RuntimeError, "Refusing to create an inheritance cycle");
539         return NULL;
540     }
541     if (result < 0) {
542         return NULL;
543     }
544     _abc_data *impl = _get_impl(module, self);
545     if (impl == NULL) {
546         return NULL;
547     }
548     if (_add_to_weak_set(&impl->_abc_registry, subclass) < 0) {
549         Py_DECREF(impl);
550         return NULL;
551     }
552     Py_DECREF(impl);
553 
554     /* Invalidate negative cache */
555     get_abc_state(module)->abc_invalidation_counter++;
556 
557     /* Set Py_TPFLAGS_SEQUENCE  or Py_TPFLAGS_MAPPING flag */
558     if (PyType_Check(self)) {
559         unsigned long collection_flag = ((PyTypeObject *)self)->tp_flags & COLLECTION_FLAGS;
560         if (collection_flag) {
561             set_collection_flag_recursive((PyTypeObject *)subclass, collection_flag);
562         }
563     }
564     Py_INCREF(subclass);
565     return subclass;
566 }
567 
568 
569 /*[clinic input]
570 _abc._abc_instancecheck
571 
572     self: object
573     instance: object
574     /
575 
576 Internal ABC helper for instance checks. Should be never used outside abc module.
577 [clinic start generated code]*/
578 
579 static PyObject *
_abc__abc_instancecheck_impl(PyObject * module,PyObject * self,PyObject * instance)580 _abc__abc_instancecheck_impl(PyObject *module, PyObject *self,
581                              PyObject *instance)
582 /*[clinic end generated code: output=b8b5148f63b6b56f input=a4f4525679261084]*/
583 {
584     PyObject *subtype, *result = NULL, *subclass = NULL;
585     _abc_data *impl = _get_impl(module, self);
586     if (impl == NULL) {
587         return NULL;
588     }
589 
590     subclass = PyObject_GetAttr(instance, &_Py_ID(__class__));
591     if (subclass == NULL) {
592         Py_DECREF(impl);
593         return NULL;
594     }
595     /* Inline the cache checking. */
596     int incache = _in_weak_set(impl->_abc_cache, subclass);
597     if (incache < 0) {
598         goto end;
599     }
600     if (incache > 0) {
601         result = Py_True;
602         Py_INCREF(result);
603         goto end;
604     }
605     subtype = (PyObject *)Py_TYPE(instance);
606     if (subtype == subclass) {
607         if (impl->_abc_negative_cache_version == get_abc_state(module)->abc_invalidation_counter) {
608             incache = _in_weak_set(impl->_abc_negative_cache, subclass);
609             if (incache < 0) {
610                 goto end;
611             }
612             if (incache > 0) {
613                 result = Py_False;
614                 Py_INCREF(result);
615                 goto end;
616             }
617         }
618         /* Fall back to the subclass check. */
619         result = PyObject_CallMethodOneArg(self, &_Py_ID(__subclasscheck__),
620                                            subclass);
621         goto end;
622     }
623     result = PyObject_CallMethodOneArg(self, &_Py_ID(__subclasscheck__),
624                                        subclass);
625     if (result == NULL) {
626         goto end;
627     }
628 
629     switch (PyObject_IsTrue(result)) {
630     case -1:
631         Py_DECREF(result);
632         result = NULL;
633         break;
634     case 0:
635         Py_DECREF(result);
636         result = PyObject_CallMethodOneArg(self, &_Py_ID(__subclasscheck__),
637                                            subtype);
638         break;
639     case 1:  // Nothing to do.
640         break;
641     default:
642         Py_UNREACHABLE();
643     }
644 
645 end:
646     Py_XDECREF(impl);
647     Py_XDECREF(subclass);
648     return result;
649 }
650 
651 
652 // Return -1 when exception occurred.
653 // Return 1 when result is set.
654 // Return 0 otherwise.
655 static int subclasscheck_check_registry(_abc_data *impl, PyObject *subclass,
656                                         PyObject **result);
657 
658 /*[clinic input]
659 _abc._abc_subclasscheck
660 
661     self: object
662     subclass: object
663     /
664 
665 Internal ABC helper for subclasss checks. Should be never used outside abc module.
666 [clinic start generated code]*/
667 
668 static PyObject *
_abc__abc_subclasscheck_impl(PyObject * module,PyObject * self,PyObject * subclass)669 _abc__abc_subclasscheck_impl(PyObject *module, PyObject *self,
670                              PyObject *subclass)
671 /*[clinic end generated code: output=b56c9e4a530e3894 input=1d947243409d10b8]*/
672 {
673     if (!PyType_Check(subclass)) {
674         PyErr_SetString(PyExc_TypeError, "issubclass() arg 1 must be a class");
675         return NULL;
676     }
677 
678     PyObject *ok, *subclasses = NULL, *result = NULL;
679     _abcmodule_state *state = NULL;
680     Py_ssize_t pos;
681     int incache;
682     _abc_data *impl = _get_impl(module, self);
683     if (impl == NULL) {
684         return NULL;
685     }
686 
687     /* 1. Check cache. */
688     incache = _in_weak_set(impl->_abc_cache, subclass);
689     if (incache < 0) {
690         goto end;
691     }
692     if (incache > 0) {
693         result = Py_True;
694         goto end;
695     }
696 
697     state = get_abc_state(module);
698     /* 2. Check negative cache; may have to invalidate. */
699     if (impl->_abc_negative_cache_version < state->abc_invalidation_counter) {
700         /* Invalidate the negative cache. */
701         if (impl->_abc_negative_cache != NULL &&
702                 PySet_Clear(impl->_abc_negative_cache) < 0)
703         {
704             goto end;
705         }
706         impl->_abc_negative_cache_version = state->abc_invalidation_counter;
707     }
708     else {
709         incache = _in_weak_set(impl->_abc_negative_cache, subclass);
710         if (incache < 0) {
711             goto end;
712         }
713         if (incache > 0) {
714             result = Py_False;
715             goto end;
716         }
717     }
718 
719     /* 3. Check the subclass hook. */
720     ok = PyObject_CallMethodOneArg(
721             (PyObject *)self, &_Py_ID(__subclasshook__), subclass);
722     if (ok == NULL) {
723         goto end;
724     }
725     if (ok == Py_True) {
726         Py_DECREF(ok);
727         if (_add_to_weak_set(&impl->_abc_cache, subclass) < 0) {
728             goto end;
729         }
730         result = Py_True;
731         goto end;
732     }
733     if (ok == Py_False) {
734         Py_DECREF(ok);
735         if (_add_to_weak_set(&impl->_abc_negative_cache, subclass) < 0) {
736             goto end;
737         }
738         result = Py_False;
739         goto end;
740     }
741     if (ok != Py_NotImplemented) {
742         Py_DECREF(ok);
743         PyErr_SetString(PyExc_AssertionError, "__subclasshook__ must return either"
744                                               " False, True, or NotImplemented");
745         goto end;
746     }
747     Py_DECREF(ok);
748 
749     /* 4. Check if it's a direct subclass. */
750     PyObject *mro = ((PyTypeObject *)subclass)->tp_mro;
751     assert(PyTuple_Check(mro));
752     for (pos = 0; pos < PyTuple_GET_SIZE(mro); pos++) {
753         PyObject *mro_item = PyTuple_GET_ITEM(mro, pos);
754         assert(mro_item != NULL);
755         if ((PyObject *)self == mro_item) {
756             if (_add_to_weak_set(&impl->_abc_cache, subclass) < 0) {
757                 goto end;
758             }
759             result = Py_True;
760             goto end;
761         }
762     }
763 
764     /* 5. Check if it's a subclass of a registered class (recursive). */
765     if (subclasscheck_check_registry(impl, subclass, &result)) {
766         // Exception occurred or result is set.
767         goto end;
768     }
769 
770     /* 6. Check if it's a subclass of a subclass (recursive). */
771     subclasses = PyObject_CallMethod(self, "__subclasses__", NULL);
772     if (subclasses == NULL) {
773         goto end;
774     }
775     if (!PyList_Check(subclasses)) {
776         PyErr_SetString(PyExc_TypeError, "__subclasses__() must return a list");
777         goto end;
778     }
779     for (pos = 0; pos < PyList_GET_SIZE(subclasses); pos++) {
780         PyObject *scls = PyList_GET_ITEM(subclasses, pos);
781         Py_INCREF(scls);
782         int r = PyObject_IsSubclass(subclass, scls);
783         Py_DECREF(scls);
784         if (r > 0) {
785             if (_add_to_weak_set(&impl->_abc_cache, subclass) < 0) {
786                 goto end;
787             }
788             result = Py_True;
789             goto end;
790         }
791         if (r < 0) {
792             goto end;
793         }
794     }
795 
796     /* No dice; update negative cache. */
797     if (_add_to_weak_set(&impl->_abc_negative_cache, subclass) < 0) {
798         goto end;
799     }
800     result = Py_False;
801 
802 end:
803     Py_DECREF(impl);
804     Py_XDECREF(subclasses);
805     Py_XINCREF(result);
806     return result;
807 }
808 
809 
810 static int
subclasscheck_check_registry(_abc_data * impl,PyObject * subclass,PyObject ** result)811 subclasscheck_check_registry(_abc_data *impl, PyObject *subclass,
812                              PyObject **result)
813 {
814     // Fast path: check subclass is in weakref directly.
815     int ret = _in_weak_set(impl->_abc_registry, subclass);
816     if (ret < 0) {
817         *result = NULL;
818         return -1;
819     }
820     if (ret > 0) {
821         *result = Py_True;
822         return 1;
823     }
824 
825     if (impl->_abc_registry == NULL) {
826         return 0;
827     }
828     Py_ssize_t registry_size = PySet_Size(impl->_abc_registry);
829     if (registry_size == 0) {
830         return 0;
831     }
832     // Weakref callback may remove entry from set.
833     // So we take snapshot of registry first.
834     PyObject **copy = PyMem_Malloc(sizeof(PyObject*) * registry_size);
835     if (copy == NULL) {
836         PyErr_NoMemory();
837         return -1;
838     }
839     PyObject *key;
840     Py_ssize_t pos = 0;
841     Py_hash_t hash;
842     Py_ssize_t i = 0;
843 
844     while (_PySet_NextEntry(impl->_abc_registry, &pos, &key, &hash)) {
845         Py_INCREF(key);
846         copy[i++] = key;
847     }
848     assert(i == registry_size);
849 
850     for (i = 0; i < registry_size; i++) {
851         PyObject *rkey = PyWeakref_GetObject(copy[i]);
852         if (rkey == NULL) {
853             // Someone inject non-weakref type in the registry.
854             ret = -1;
855             break;
856         }
857         if (rkey == Py_None) {
858             continue;
859         }
860         Py_INCREF(rkey);
861         int r = PyObject_IsSubclass(subclass, rkey);
862         Py_DECREF(rkey);
863         if (r < 0) {
864             ret = -1;
865             break;
866         }
867         if (r > 0) {
868             if (_add_to_weak_set(&impl->_abc_cache, subclass) < 0) {
869                 ret = -1;
870                 break;
871             }
872             *result = Py_True;
873             ret = 1;
874             break;
875         }
876     }
877 
878     for (i = 0; i < registry_size; i++) {
879         Py_DECREF(copy[i]);
880     }
881     PyMem_Free(copy);
882     return ret;
883 }
884 
885 /*[clinic input]
886 _abc.get_cache_token
887 
888 Returns the current ABC cache token.
889 
890 The token is an opaque object (supporting equality testing) identifying the
891 current version of the ABC cache for virtual subclasses. The token changes
892 with every call to register() on any ABC.
893 [clinic start generated code]*/
894 
895 static PyObject *
_abc_get_cache_token_impl(PyObject * module)896 _abc_get_cache_token_impl(PyObject *module)
897 /*[clinic end generated code: output=c7d87841e033dacc input=70413d1c423ad9f9]*/
898 {
899     _abcmodule_state *state = get_abc_state(module);
900     return PyLong_FromUnsignedLongLong(state->abc_invalidation_counter);
901 }
902 
903 static struct PyMethodDef _abcmodule_methods[] = {
904     _ABC_GET_CACHE_TOKEN_METHODDEF
905     _ABC__ABC_INIT_METHODDEF
906     _ABC__RESET_REGISTRY_METHODDEF
907     _ABC__RESET_CACHES_METHODDEF
908     _ABC__GET_DUMP_METHODDEF
909     _ABC__ABC_REGISTER_METHODDEF
910     _ABC__ABC_INSTANCECHECK_METHODDEF
911     _ABC__ABC_SUBCLASSCHECK_METHODDEF
912     {NULL,       NULL}          /* sentinel */
913 };
914 
915 static int
_abcmodule_exec(PyObject * module)916 _abcmodule_exec(PyObject *module)
917 {
918     _abcmodule_state *state = get_abc_state(module);
919     state->abc_invalidation_counter = 0;
920     state->_abc_data_type = (PyTypeObject *)PyType_FromModuleAndSpec(module, &_abc_data_type_spec, NULL);
921     if (state->_abc_data_type == NULL) {
922         return -1;
923     }
924 
925     return 0;
926 }
927 
928 static int
_abcmodule_traverse(PyObject * module,visitproc visit,void * arg)929 _abcmodule_traverse(PyObject *module, visitproc visit, void *arg)
930 {
931     _abcmodule_state *state = get_abc_state(module);
932     Py_VISIT(state->_abc_data_type);
933     return 0;
934 }
935 
936 static int
_abcmodule_clear(PyObject * module)937 _abcmodule_clear(PyObject *module)
938 {
939     _abcmodule_state *state = get_abc_state(module);
940     Py_CLEAR(state->_abc_data_type);
941     return 0;
942 }
943 
944 static void
_abcmodule_free(void * module)945 _abcmodule_free(void *module)
946 {
947     _abcmodule_clear((PyObject *)module);
948 }
949 
950 static PyModuleDef_Slot _abcmodule_slots[] = {
951     {Py_mod_exec, _abcmodule_exec},
952     {0, NULL}
953 };
954 
955 static struct PyModuleDef _abcmodule = {
956     PyModuleDef_HEAD_INIT,
957     .m_name = "_abc",
958     .m_doc = _abc__doc__,
959     .m_size = sizeof(_abcmodule_state),
960     .m_methods = _abcmodule_methods,
961     .m_slots = _abcmodule_slots,
962     .m_traverse = _abcmodule_traverse,
963     .m_clear = _abcmodule_clear,
964     .m_free = _abcmodule_free,
965 };
966 
967 PyMODINIT_FUNC
PyInit__abc(void)968 PyInit__abc(void)
969 {
970     return PyModuleDef_Init(&_abcmodule);
971 }
972