bpo-43977: Use tp_flags for collection matching (GH-25723)

* Add Py_TPFLAGS_SEQUENCE and Py_TPFLAGS_MAPPING, add to all relevant standard builtin classes.

* Set relevant flags on collections.abc.Sequence and Mapping.

* Use flags in MATCH_SEQUENCE and MATCH_MAPPING opcodes.

* Inherit Py_TPFLAGS_SEQUENCE and Py_TPFLAGS_MAPPING.

* Add NEWS

* Remove interpreter-state map_abc and seq_abc fields.

16 files changed, 74 insertions, 83 deletions

diff --git a/Include/internal/pycore_interp.h b/Include/internal/pycore_interp.h
index 11d31da..bfd082b 100644
--- a/Include/internal/pycore_interp.h
+++ b/Include/internal/pycore_interp.h
@@ -247,10 +247,6 @@ struct _is {
     // importlib module
     PyObject *importlib;
 
-    // Kept handy for pattern matching:
-    PyObject *map_abc;  // _collections_abc.Mapping
-    PyObject *seq_abc;  // _collections_abc.Sequence
-
     /* Used in Modules/_threadmodule.c. */
     long num_threads;
     /* Support for runtime thread stack size tuning.
diff --git a/Include/object.h b/Include/object.h
index d8476f9..cffe72c 100644
--- a/Include/object.h
+++ b/Include/object.h
@@ -320,6 +320,13 @@ Code can use PyType_HasFeature(type_ob, flag_value) to test whether the
 given type object has a specified feature.
 */
 
+#ifndef Py_LIMITED_API
+/* Set if instances of the type object are treated as sequences for pattern matching */
+#define Py_TPFLAGS_SEQUENCE (1 << 5)
+/* Set if instances of the type object are treated as mappings for pattern matching */
+#define Py_TPFLAGS_MAPPING (1 << 6)
+#endif
+
 /* Set if the type object is immutable: type attributes cannot be set nor deleted */
 #define Py_TPFLAGS_IMMUTABLETYPE (1UL << 8)
 
diff --git a/Lib/_collections_abc.py b/Lib/_collections_abc.py
index dddf8a2..d92b848 100644
--- a/Lib/_collections_abc.py
+++ b/Lib/_collections_abc.py
@@ -793,7 +793,6 @@ MutableSet.register(set)
 
 ### MAPPINGS ###
 
-
 class Mapping(Collection):
     """A Mapping is a generic container for associating key/value
     pairs.
@@ -804,6 +803,9 @@ class Mapping(Collection):
 
     __slots__ = ()
 
+    # Tell ABCMeta.__new__ that this class should have TPFLAGS_MAPPING set.
+    __abc_tpflags__ = 1 << 6 # Py_TPFLAGS_MAPPING
+
     @abstractmethod
     def __getitem__(self, key):
         raise KeyError
@@ -842,7 +844,6 @@ class Mapping(Collection):
 
     __reversed__ = None
 
-
 Mapping.register(mappingproxy)
 
 
@@ -1011,7 +1012,6 @@ MutableMapping.register(dict)
 
 ### SEQUENCES ###
 
-
 class Sequence(Reversible, Collection):
     """All the operations on a read-only sequence.
 
@@ -1021,6 +1021,9 @@ class Sequence(Reversible, Collection):
 
     __slots__ = ()
 
+    # Tell ABCMeta.__new__ that this class should have TPFLAGS_SEQUENCE set.
+    __abc_tpflags__ = 1 << 5 # Py_TPFLAGS_SEQUENCE
+
     @abstractmethod
     def __getitem__(self, index):
         raise IndexError
@@ -1072,7 +1075,6 @@ class Sequence(Reversible, Collection):
         'S.count(value) -> integer -- return number of occurrences of value'
         return sum(1 for v in self if v is value or v == value)
 
-
 Sequence.register(tuple)
 Sequence.register(str)
 Sequence.register(range)
diff --git a/Misc/NEWS.d/next/Core and Builtins/2021-04-29-17-40-25.bpo-43977.FrQhge.rst b/Misc/NEWS.d/next/Core and Builtins/2021-04-29-17-40-25.bpo-43977.FrQhge.rst
new file mode 100644
index 0000000..038d739
--- /dev/null
+++ b/Misc/NEWS.d/next/Core and Builtins/2021-04-29-17-40-25.bpo-43977.FrQhge.rst
@@ -0,0 +1,2 @@
+Use :c:member:`~PyTypeObject.tp_flags` on the class object to determine if the subject is a sequence
+or mapping when pattern matching. Avoids the need to import :mod:`collections.abc` when pattern matching.
diff --git a/Modules/_abc.c b/Modules/_abc.c
index 0ddc2ab..39261dd 100644
--- a/Modules/_abc.c
+++ b/Modules/_abc.c
@@ -15,6 +15,7 @@ PyDoc_STRVAR(_abc__doc__,
 _Py_IDENTIFIER(__abstractmethods__);
 _Py_IDENTIFIER(__class__);
 _Py_IDENTIFIER(__dict__);
+_Py_IDENTIFIER(__abc_tpflags__);
 _Py_IDENTIFIER(__bases__);
 _Py_IDENTIFIER(_abc_impl);
 _Py_IDENTIFIER(__subclasscheck__);
@@ -417,6 +418,8 @@ error:
     return ret;
 }
 
+#define COLLECTION_FLAGS (Py_TPFLAGS_SEQUENCE | Py_TPFLAGS_MAPPING)
+
 /*[clinic input]
 _abc._abc_init
 
@@ -446,6 +449,31 @@ _abc__abc_init(PyObject *module, PyObject *self)
         return NULL;
     }
     Py_DECREF(data);
+    /* If __abc_tpflags__ & COLLECTION_FLAGS is set, then set the corresponding bit(s)
+     * in the new class.
+     * Used by collections.abc.Sequence and collections.abc.Mapping to indicate
+     * their special status w.r.t. pattern matching. */
+    if (PyType_Check(self)) {
+        PyTypeObject *cls = (PyTypeObject *)self;
+        PyObject *flags = _PyDict_GetItemIdWithError(cls->tp_dict, &PyId___abc_tpflags__);
+        if (flags == NULL) {
+            if (PyErr_Occurred()) {
+                return NULL;
+            }
+        }
+        else {
+            if (PyLong_CheckExact(flags)) {
+                long val = PyLong_AsLong(flags);
+                if (val == -1 && PyErr_Occurred()) {
+                    return NULL;
+                }
+                ((PyTypeObject *)self)->tp_flags |= (val & COLLECTION_FLAGS);
+            }
+            if (_PyDict_DelItemId(cls->tp_dict, &PyId___abc_tpflags__) < 0) {
+                return NULL;
+            }
+        }
+    }
     Py_RETURN_NONE;
 }
 
@@ -499,6 +527,11 @@ _abc__abc_register_impl(PyObject *module, PyObject *self, PyObject *subclass)
     /* Invalidate negative cache */
     get_abc_state(module)->abc_invalidation_counter++;
 
+    if (PyType_Check(subclass) && PyType_Check(self) &&
+        !PyType_HasFeature((PyTypeObject *)subclass, Py_TPFLAGS_IMMUTABLETYPE))
+    {
+        ((PyTypeObject *)subclass)->tp_flags |= (((PyTypeObject *)self)->tp_flags & COLLECTION_FLAGS);
+    }
     Py_INCREF(subclass);
     return subclass;
 }
diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c
index 8b01a7f..9c8701a 100644
--- a/Modules/_collectionsmodule.c
+++ b/Modules/_collectionsmodule.c
@@ -1662,7 +1662,8 @@ static PyTypeObject deque_type = {
     PyObject_GenericGetAttr,            /* tp_getattro */
     0,                                  /* tp_setattro */
     0,                                  /* tp_as_buffer */
-    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,
+    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
+    Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_SEQUENCE,
                                         /* tp_flags */
     deque_doc,                          /* tp_doc */
     (traverseproc)deque_traverse,       /* tp_traverse */
diff --git a/Modules/arraymodule.c b/Modules/arraymodule.c
index 367621f..d65c144 100644
--- a/Modules/arraymodule.c
+++ b/Modules/arraymodule.c
@@ -2848,7 +2848,8 @@ static PyType_Spec array_spec = {
     .name = "array.array",
     .basicsize = sizeof(arrayobject),
     .flags = (Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
-              Py_TPFLAGS_IMMUTABLETYPE),
+              Py_TPFLAGS_IMMUTABLETYPE |
+              Py_TPFLAGS_SEQUENCE),
     .slots = array_slots,
 };
 
diff --git a/Objects/descrobject.c b/Objects/descrobject.c
index dd41620..57a9607 100644
--- a/Objects/descrobject.c
+++ b/Objects/descrobject.c
@@ -1852,7 +1852,8 @@ PyTypeObject PyDictProxy_Type = {
     PyObject_GenericGetAttr,                    /* tp_getattro */
     0,                                          /* tp_setattro */
     0,                                          /* tp_as_buffer */
-    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
+    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
+        Py_TPFLAGS_MAPPING,                     /* tp_flags */
     0,                                          /* tp_doc */
     mappingproxy_traverse,                      /* tp_traverse */
     0,                                          /* tp_clear */
diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 0aeee70..9e2c122 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -3553,7 +3553,7 @@ PyTypeObject PyDict_Type = {
     0,                                          /* tp_as_buffer */
     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
         Py_TPFLAGS_BASETYPE | Py_TPFLAGS_DICT_SUBCLASS |
-        _Py_TPFLAGS_MATCH_SELF,               /* tp_flags */
+        _Py_TPFLAGS_MATCH_SELF | Py_TPFLAGS_MAPPING,  /* tp_flags */
     dictionary_doc,                             /* tp_doc */
     dict_traverse,                              /* tp_traverse */
     dict_tp_clear,                              /* tp_clear */
diff --git a/Objects/listobject.c b/Objects/listobject.c
index e7987a6..6eb7dce 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -3053,7 +3053,7 @@ PyTypeObject PyList_Type = {
     0,                                          /* tp_as_buffer */
     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
         Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS |
-        _Py_TPFLAGS_MATCH_SELF,               /* tp_flags */
+        _Py_TPFLAGS_MATCH_SELF | Py_TPFLAGS_SEQUENCE,  /* tp_flags */
     list___init____doc__,                       /* tp_doc */
     (traverseproc)list_traverse,                /* tp_traverse */
     (inquiry)_list_clear,                       /* tp_clear */
diff --git a/Objects/memoryobject.c b/Objects/memoryobject.c
index d328f4d..913d358 100644
--- a/Objects/memoryobject.c
+++ b/Objects/memoryobject.c
@@ -3287,7 +3287,8 @@ PyTypeObject PyMemoryView_Type = {
     PyObject_GenericGetAttr,                  /* tp_getattro */
     0,                                        /* tp_setattro */
     &memory_as_buffer,                        /* tp_as_buffer */
-    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,  /* tp_flags */
+    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
+       Py_TPFLAGS_SEQUENCE,                   /* tp_flags */
     memoryview__doc__,                        /* tp_doc */
     (traverseproc)memory_traverse,            /* tp_traverse */
     (inquiry)memory_clear,                    /* tp_clear */
diff --git a/Objects/rangeobject.c b/Objects/rangeobject.c
index 530426c..3e05707 100644
--- a/Objects/rangeobject.c
+++ b/Objects/rangeobject.c
@@ -735,7 +735,7 @@ PyTypeObject PyRange_Type = {
         PyObject_GenericGetAttr,  /* tp_getattro */
         0,                      /* tp_setattro */
         0,                      /* tp_as_buffer */
-        Py_TPFLAGS_DEFAULT,     /* tp_flags */
+        Py_TPFLAGS_DEFAULT | Py_TPFLAGS_SEQUENCE,  /* tp_flags */
         range_doc,              /* tp_doc */
         0,                      /* tp_traverse */
         0,                      /* tp_clear */
diff --git a/Objects/tupleobject.c b/Objects/tupleobject.c
index 89c393c..6b1ab74 100644
--- a/Objects/tupleobject.c
+++ b/Objects/tupleobject.c
@@ -918,7 +918,7 @@ PyTypeObject PyTuple_Type = {
     0,                                          /* tp_as_buffer */
     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
         Py_TPFLAGS_BASETYPE | Py_TPFLAGS_TUPLE_SUBCLASS |
-        _Py_TPFLAGS_MATCH_SELF,               /* tp_flags */
+        _Py_TPFLAGS_MATCH_SELF | Py_TPFLAGS_SEQUENCE,  /* tp_flags */
     tuple_new__doc__,                           /* tp_doc */
     (traverseproc)tupletraverse,                /* tp_traverse */
     0,                                          /* tp_clear */
diff --git a/Objects/typeobject.c b/Objects/typeobject.c
index ac4dc1d..19d619f 100644
--- a/Objects/typeobject.c
+++ b/Objects/typeobject.c
@@ -5717,10 +5717,15 @@ inherit_special(PyTypeObject *type, PyTypeObject *base)
     else if (PyType_IsSubtype(base, &PyDict_Type)) {
         type->tp_flags |= Py_TPFLAGS_DICT_SUBCLASS;
     }
-
     if (PyType_HasFeature(base, _Py_TPFLAGS_MATCH_SELF)) {
         type->tp_flags |= _Py_TPFLAGS_MATCH_SELF;
     }
+    if (PyType_HasFeature(base, Py_TPFLAGS_SEQUENCE)) {
+        type->tp_flags |= Py_TPFLAGS_SEQUENCE;
+    }
+    if (PyType_HasFeature(base, Py_TPFLAGS_MAPPING)) {
+        type->tp_flags |= Py_TPFLAGS_MAPPING;
+    }
 }
 
 static int
diff --git a/Python/ceval.c b/Python/ceval.c
index 326930b..866c57a 100644
--- a/Python/ceval.c
+++ b/Python/ceval.c
@@ -3889,76 +3889,20 @@ main_loop:
         }
 
         case TARGET(MATCH_MAPPING): {
-            // PUSH(isinstance(TOS, _collections_abc.Mapping))
             PyObject *subject = TOP();
-            // Fast path for dicts:
-            if (PyDict_Check(subject)) {
-                Py_INCREF(Py_True);
-                PUSH(Py_True);
-                DISPATCH();
-            }
-            // Lazily import _collections_abc.Mapping, and keep it handy on the
-            // PyInterpreterState struct (it gets cleaned up at exit):
-            PyInterpreterState *interp = PyInterpreterState_Get();
-            if (interp->map_abc == NULL) {
-                PyObject *abc = PyImport_ImportModule("_collections_abc");
-                if (abc == NULL) {
-                    goto error;
-                }
-                interp->map_abc = PyObject_GetAttrString(abc, "Mapping");
-                if (interp->map_abc == NULL) {
-                    goto error;
-                }
-            }
-            int match = PyObject_IsInstance(subject, interp->map_abc);
-            if (match < 0) {
-                goto error;
-            }
-            PUSH(PyBool_FromLong(match));
+            int match = Py_TYPE(subject)->tp_flags & Py_TPFLAGS_MAPPING;
+            PyObject *res = match ? Py_True : Py_False;
+            Py_INCREF(res);
+            PUSH(res);
             DISPATCH();
         }
 
         case TARGET(MATCH_SEQUENCE): {
-            // PUSH(not isinstance(TOS, (bytearray, bytes, str))
-            //      and isinstance(TOS, _collections_abc.Sequence))
             PyObject *subject = TOP();
-            // Fast path for lists and tuples:
-            if (PyType_FastSubclass(Py_TYPE(subject),
-                                    Py_TPFLAGS_LIST_SUBCLASS |
-                                    Py_TPFLAGS_TUPLE_SUBCLASS))
-            {
-                Py_INCREF(Py_True);
-                PUSH(Py_True);
-                DISPATCH();
-            }
-            // Bail on some possible Sequences that we intentionally exclude:
-            if (PyType_FastSubclass(Py_TYPE(subject),
-                                    Py_TPFLAGS_BYTES_SUBCLASS |
-                                    Py_TPFLAGS_UNICODE_SUBCLASS) ||
-                PyByteArray_Check(subject))
-            {
-                Py_INCREF(Py_False);
-                PUSH(Py_False);
-                DISPATCH();
-            }
-            // Lazily import _collections_abc.Sequence, and keep it handy on the
-            // PyInterpreterState struct (it gets cleaned up at exit):
-            PyInterpreterState *interp = PyInterpreterState_Get();
-            if (interp->seq_abc == NULL) {
-                PyObject *abc = PyImport_ImportModule("_collections_abc");
-                if (abc == NULL) {
-                    goto error;
-                }
-                interp->seq_abc = PyObject_GetAttrString(abc, "Sequence");
-                if (interp->seq_abc == NULL) {
-                    goto error;
-                }
-            }
-            int match = PyObject_IsInstance(subject, interp->seq_abc);
-            if (match < 0) {
-                goto error;
-            }
-            PUSH(PyBool_FromLong(match));
+            int match = Py_TYPE(subject)->tp_flags & Py_TPFLAGS_SEQUENCE;
+            PyObject *res = match ? Py_True : Py_False;
+            Py_INCREF(res);
+            PUSH(res);
             DISPATCH();
         }
 
diff --git a/Python/pystate.c b/Python/pystate.c
index 81bcf68..aeebd6f 100644
--- a/Python/pystate.c
+++ b/Python/pystate.c
@@ -308,8 +308,6 @@ interpreter_clear(PyInterpreterState *interp, PyThreadState *tstate)
     Py_CLEAR(interp->importlib);
     Py_CLEAR(interp->import_func);
     Py_CLEAR(interp->dict);
-    Py_CLEAR(interp->map_abc);
-    Py_CLEAR(interp->seq_abc);
 #ifdef HAVE_FORK
     Py_CLEAR(interp->before_forkers);
     Py_CLEAR(interp->after_forkers_parent);