Issue #14010: Fix a crash when iterating or deleting deeply nested filters

(builting and in itertools module, i.e. map(), itertools.chain(), etc).

6 files changed, 224 insertions, 14 deletions

diff --git a/Lib/test/test_builtin.py b/Lib/test/test_builtin.py
index f46f8d5..b601ea4 100644
--- a/Lib/test/test_builtin.py
+++ b/Lib/test/test_builtin.py
@@ -1564,8 +1564,40 @@ class TestSorted(unittest.TestCase):
         data = 'The quick Brown fox Jumped over The lazy Dog'.split()
         self.assertRaises(TypeError, sorted, data, None, lambda x,y: 0)
 
+class TestRecursionLimit(unittest.TestCase):
+    # Issue #14010
+    recursionlimit = sys.getrecursionlimit()
+
+    def test_filter(self):
+        it = (0, 1)
+        for _ in range(self.recursionlimit):
+            it = filter(bool, it)
+        with self.assertRaises(RuntimeError):
+            for _ in it:
+                pass
+        del it
+
+    def test_map(self):
+        it = (0, 1)
+        for _ in range(self.recursionlimit):
+            it = map(int, it)
+        with self.assertRaises(RuntimeError):
+            for _ in it:
+                pass
+        del it
+
+    def test_zip(self):
+        it = (0, 1)
+        for _ in range(self.recursionlimit):
+            it = zip(it)
+        with self.assertRaises(RuntimeError):
+            for _ in it:
+                pass
+        del it
+
+
 def test_main(verbose=None):
-    test_classes = (BuiltinTest, TestSorted)
+    test_classes = (BuiltinTest, TestSorted, TestRecursionLimit)
 
     run_unittest(*test_classes)
 
diff --git a/Lib/test/test_itertools.py b/Lib/test/test_itertools.py
index fdf7984..2a395b5 100644
--- a/Lib/test/test_itertools.py
+++ b/Lib/test/test_itertools.py
@@ -1808,6 +1808,121 @@ class SubclassWithKwargsTest(unittest.TestCase):
                 self.assertNotIn("does not take keyword arguments", err.args[0])
 
 
+class TestRecursionLimit(unittest.TestCase):
+    # Issue #14010
+    recursionlimit = sys.getrecursionlimit()
+
+    def test_accumulate(self):
+        it = (0, 1)
+        for _ in range(self.recursionlimit):
+            it = accumulate(it)
+        with self.assertRaises(RuntimeError):
+            for _ in it:
+                pass
+        del it
+
+    def test_chain(self):
+        it = (0, 1)
+        for _ in range(self.recursionlimit):
+            it = chain(it, ())
+        with self.assertRaises(RuntimeError):
+            for _ in it:
+                pass
+        del it
+
+    def test_compress(self):
+        data = (0, 1)
+        selectors = (True, True)
+        it = data
+        for _ in range(self.recursionlimit):
+            it = compress(it, selectors)
+        with self.assertRaises(RuntimeError):
+            for _ in it:
+                pass
+        del it
+
+        it = selectors
+        for _ in range(self.recursionlimit):
+            it = compress(data, it)
+        with self.assertRaises(RuntimeError):
+            for _ in it:
+                pass
+        del it
+
+    def test_cycle(self):
+        it = (0, 1)
+        for _ in range(self.recursionlimit):
+            it = cycle(it)
+        with self.assertRaises(RuntimeError):
+            for _ in range(3):
+                next(it)
+        del it
+
+    def test_dropwhile(self):
+        it = (0, 1, 0)
+        for _ in range(self.recursionlimit):
+            it = dropwhile(bool, it)
+        with self.assertRaises(RuntimeError):
+            for _ in it:
+                pass
+        del it
+
+    def test_filterfalse(self):
+        it = (0, 1)
+        for _ in range(self.recursionlimit):
+            it = filterfalse(bool, it)
+        with self.assertRaises(RuntimeError):
+            for _ in it:
+                pass
+        del it
+
+    def test_groupby(self):
+        key = operator.itemgetter(0)
+        it = ((0, []), (1, []))
+        for _ in range(self.recursionlimit):
+            it = groupby(it, key)
+        with self.assertRaises(RuntimeError):
+            for _ in it:
+                pass
+        del it
+
+    def test_islice(self):
+        it = (0, 1)
+        for _ in range(self.recursionlimit):
+            it = islice(it, 2)
+        with self.assertRaises(RuntimeError):
+            for _ in it:
+                pass
+        del it
+
+    def test_starmap(self):
+        it = 'ab'
+        for _ in range(self.recursionlimit):
+            it = starmap(tuple, it)
+        with self.assertRaises(RuntimeError):
+            for _ in it:
+                pass
+        del it
+
+    def test_takewhile(self):
+        it = (1, 0)
+        for _ in range(self.recursionlimit):
+            it = takewhile(bool, it)
+        with self.assertRaises(RuntimeError):
+            for _ in it:
+                pass
+        del it
+
+    def test_zip_longest(self):
+        it = (0, 1)
+        for _ in range(self.recursionlimit):
+            it = zip_longest(it)
+        with self.assertRaises(RuntimeError):
+            for _ in it:
+                pass
+        del it
+
+
 libreftest = """ Doctest for examples in the library reference: libitertools.tex
 
 
@@ -2042,7 +2157,7 @@ __test__ = {'libreftest' : libreftest}
 def test_main(verbose=None):
     test_classes = (TestBasicOps, TestVariousIteratorArgs, TestGC,
                     RegressionTests, LengthTransparency,
-                    SubclassWithKwargsTest, TestExamples)
+                    SubclassWithKwargsTest, TestExamples, TestRecursionLimit)
     support.run_unittest(*test_classes)
 
     # verify reference counting
diff --git a/Misc/NEWS b/Misc/NEWS
index f60f892..bff486a 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -10,6 +10,9 @@ What's New in Python 3.4.0 Alpha 1?
 Core and Builtins
 -----------------
 
+- Issue #14010: Fix a crash when iterating or deleting deeply nested filters
+  (builting and in itertools module, i.e. map(), itertools.chain(), etc).
+
 - Issue #17469: Fix _Py_GetAllocatedBlocks() and sys.getallocatedblocks()
   when running on valgrind.
 
diff --git a/Modules/itertoolsmodule.c b/Modules/itertoolsmodule.c
index 644104e..74c5d98 100644
--- a/Modules/itertoolsmodule.c
+++ b/Modules/itertoolsmodule.c
@@ -54,12 +54,14 @@ static void
 groupby_dealloc(groupbyobject *gbo)
 {
     PyObject_GC_UnTrack(gbo);
+    Py_TRASHCAN_SAFE_BEGIN(gbo)
     Py_XDECREF(gbo->it);
     Py_XDECREF(gbo->keyfunc);
     Py_XDECREF(gbo->tgtkey);
     Py_XDECREF(gbo->currkey);
     Py_XDECREF(gbo->currvalue);
     Py_TYPE(gbo)->tp_free(gbo);
+    Py_TRASHCAN_SAFE_END(gbo)
 }
 
 static int
@@ -911,9 +913,11 @@ static void
 cycle_dealloc(cycleobject *lz)
 {
     PyObject_GC_UnTrack(lz);
+    Py_TRASHCAN_SAFE_BEGIN(lz)
     Py_XDECREF(lz->saved);
     Py_XDECREF(lz->it);
     Py_TYPE(lz)->tp_free(lz);
+    Py_TRASHCAN_SAFE_END(lz)
 }
 
 static int
@@ -1088,9 +1092,11 @@ static void
 dropwhile_dealloc(dropwhileobject *lz)
 {
     PyObject_GC_UnTrack(lz);
+    Py_TRASHCAN_SAFE_BEGIN(lz)
     Py_XDECREF(lz->func);
     Py_XDECREF(lz->it);
     Py_TYPE(lz)->tp_free(lz);
+    Py_TRASHCAN_SAFE_END(lz)
 }
 
 static int
@@ -1111,7 +1117,10 @@ dropwhile_next(dropwhileobject *lz)
 
     iternext = *Py_TYPE(it)->tp_iternext;
     for (;;) {
+        if (Py_EnterRecursiveCall(" while iterating"))
+            return NULL;
         item = iternext(it);
+        Py_LeaveRecursiveCall();
         if (item == NULL)
             return NULL;
         if (lz->start == 1)
@@ -1257,9 +1266,11 @@ static void
 takewhile_dealloc(takewhileobject *lz)
 {
     PyObject_GC_UnTrack(lz);
+    Py_TRASHCAN_SAFE_BEGIN(lz)
     Py_XDECREF(lz->func);
     Py_XDECREF(lz->it);
     Py_TYPE(lz)->tp_free(lz);
+    Py_TRASHCAN_SAFE_END(lz)
 }
 
 static int
@@ -1280,7 +1291,10 @@ takewhile_next(takewhileobject *lz)
     if (lz->stop == 1)
         return NULL;
 
+    if (Py_EnterRecursiveCall(" while iterating"))
+        return NULL;
     item = (*Py_TYPE(it)->tp_iternext)(it);
+    Py_LeaveRecursiveCall();
     if (item == NULL)
         return NULL;
 
@@ -1472,8 +1486,10 @@ static void
 islice_dealloc(isliceobject *lz)
 {
     PyObject_GC_UnTrack(lz);
+    Py_TRASHCAN_SAFE_BEGIN(lz)
     Py_XDECREF(lz->it);
     Py_TYPE(lz)->tp_free(lz);
+    Py_TRASHCAN_SAFE_END(lz)
 }
 
 static int
@@ -1494,7 +1510,10 @@ islice_next(isliceobject *lz)
 
     iternext = *Py_TYPE(it)->tp_iternext;
     while (lz->cnt < lz->next) {
+        if (Py_EnterRecursiveCall(" while iterating"))
+            return NULL;
         item = iternext(it);
+        Py_LeaveRecursiveCall();
         if (item == NULL)
             return NULL;
         Py_DECREF(item);
@@ -1502,7 +1521,10 @@ islice_next(isliceobject *lz)
     }
     if (stop != -1 && lz->cnt >= stop)
         return NULL;
+    if (Py_EnterRecursiveCall(" while iterating"))
+        return NULL;
     item = iternext(it);
+    Py_LeaveRecursiveCall();
     if (item == NULL)
         return NULL;
     lz->cnt++;
@@ -1653,9 +1675,11 @@ static void
 starmap_dealloc(starmapobject *lz)
 {
     PyObject_GC_UnTrack(lz);
+    Py_TRASHCAN_SAFE_BEGIN(lz)
     Py_XDECREF(lz->func);
     Py_XDECREF(lz->it);
     Py_TYPE(lz)->tp_free(lz);
+    Py_TRASHCAN_SAFE_END(lz)
 }
 
 static int
@@ -1673,7 +1697,10 @@ starmap_next(starmapobject *lz)
     PyObject *result;
     PyObject *it = lz->it;
 
+    if (Py_EnterRecursiveCall(" while iterating"))
+        return NULL;
     args = (*Py_TYPE(it)->tp_iternext)(it);
+    Py_LeaveRecursiveCall();
     if (args == NULL)
         return NULL;
     if (!PyTuple_CheckExact(args)) {
@@ -1809,9 +1836,11 @@ static void
 chain_dealloc(chainobject *lz)
 {
     PyObject_GC_UnTrack(lz);
+    Py_TRASHCAN_SAFE_BEGIN(lz)
     Py_XDECREF(lz->active);
     Py_XDECREF(lz->source);
     Py_TYPE(lz)->tp_free(lz);
+    Py_TRASHCAN_SAFE_END(lz)
 }
 
 static int
@@ -3340,10 +3369,12 @@ static void
 accumulate_dealloc(accumulateobject *lz)
 {
     PyObject_GC_UnTrack(lz);
+    Py_TRASHCAN_SAFE_BEGIN(lz)
     Py_XDECREF(lz->binop);
     Py_XDECREF(lz->total);
     Py_XDECREF(lz->it);
     Py_TYPE(lz)->tp_free(lz);
+    Py_TRASHCAN_SAFE_END(lz)
 }
 
 static int
@@ -3514,9 +3545,11 @@ static void
 compress_dealloc(compressobject *lz)
 {
     PyObject_GC_UnTrack(lz);
+    Py_TRASHCAN_SAFE_BEGIN(lz)
     Py_XDECREF(lz->data);
     Py_XDECREF(lz->selectors);
     Py_TYPE(lz)->tp_free(lz);
+    Py_TRASHCAN_SAFE_END(lz)
 }
 
 static int
@@ -3543,11 +3576,16 @@ compress_next(compressobject *lz)
            exception first).
         */
 
+        if (Py_EnterRecursiveCall(" while iterating"))
+            return NULL;
         datum = datanext(data);
-        if (datum == NULL)
+        if (datum == NULL) {
+            Py_LeaveRecursiveCall();
             return NULL;
+        }
 
         selector = selectornext(selectors);
+        Py_LeaveRecursiveCall();
         if (selector == NULL) {
             Py_DECREF(datum);
             return NULL;
@@ -3674,9 +3712,11 @@ static void
 filterfalse_dealloc(filterfalseobject *lz)
 {
     PyObject_GC_UnTrack(lz);
+    Py_TRASHCAN_SAFE_BEGIN(lz)
     Py_XDECREF(lz->func);
     Py_XDECREF(lz->it);
     Py_TYPE(lz)->tp_free(lz);
+    Py_TRASHCAN_SAFE_END(lz)
 }
 
 static int
@@ -3697,7 +3737,10 @@ filterfalse_next(filterfalseobject *lz)
 
     iternext = *Py_TYPE(it)->tp_iternext;
     for (;;) {
+        if (Py_EnterRecursiveCall(" while iterating"))
+            return NULL;
         item = iternext(it);
+        Py_LeaveRecursiveCall();
         if (item == NULL)
             return NULL;
 
@@ -4261,10 +4304,12 @@ static void
 zip_longest_dealloc(ziplongestobject *lz)
 {
     PyObject_GC_UnTrack(lz);
+    Py_TRASHCAN_SAFE_BEGIN(lz)
     Py_XDECREF(lz->ittuple);
     Py_XDECREF(lz->result);
     Py_XDECREF(lz->fillvalue);
     Py_TYPE(lz)->tp_free(lz);
+    Py_TRASHCAN_SAFE_END(lz)
 }
 
 static int
diff --git a/Objects/abstract.c b/Objects/abstract.c
index 4326cfa..9b31d7a 100644
--- a/Objects/abstract.c
+++ b/Objects/abstract.c
@@ -1238,7 +1238,7 @@ PyNumber_AsSsize_t(PyObject *item, PyObject *err)
   to be an int or have an __int__ method. Steals integral's
   reference. error_format will be used to create the TypeError if integral
   isn't actually an Integral instance. error_format should be a format string
-  that can accept a char* naming integral's type. 
+  that can accept a char* naming integral's type.
 */
 static PyObject *
 convert_integral_to_int(PyObject *integral, const char *error_format)
@@ -1257,7 +1257,7 @@ convert_integral_to_int(PyObject *integral, const char *error_format)
     }
     PyErr_Format(PyExc_TypeError, error_format, Py_TYPE(integral)->tp_name);
     Py_DECREF(integral);
-    return NULL;    
+    return NULL;
 }
 
 
@@ -2702,7 +2702,10 @@ PyObject *
 PyIter_Next(PyObject *iter)
 {
     PyObject *result;
+    if (Py_EnterRecursiveCall(" while iterating"))
+        return NULL;
     result = (*iter->ob_type->tp_iternext)(iter);
+    Py_LeaveRecursiveCall();
     if (result == NULL &&
         PyErr_Occurred() &&
         PyErr_ExceptionMatches(PyExc_StopIteration))
diff --git a/Python/bltinmodule.c b/Python/bltinmodule.c
index a486b49..6344c68 100644
--- a/Python/bltinmodule.c
+++ b/Python/bltinmodule.c
@@ -391,9 +391,11 @@ static void
 filter_dealloc(filterobject *lz)
 {
     PyObject_GC_UnTrack(lz);
+    Py_TRASHCAN_SAFE_BEGIN(lz)
     Py_XDECREF(lz->func);
     Py_XDECREF(lz->it);
     Py_TYPE(lz)->tp_free(lz);
+    Py_TRASHCAN_SAFE_END(lz)
 }
 
 static int
@@ -414,7 +416,10 @@ filter_next(filterobject *lz)
 
     iternext = *Py_TYPE(it)->tp_iternext;
     for (;;) {
+        if (Py_EnterRecursiveCall(" while iterating"))
+            return NULL;
         item = iternext(it);
+        Py_LeaveRecursiveCall();
         if (item == NULL)
             return NULL;
 
@@ -1031,9 +1036,11 @@ static void
 map_dealloc(mapobject *lz)
 {
     PyObject_GC_UnTrack(lz);
+    Py_TRASHCAN_SAFE_BEGIN(lz)
     Py_XDECREF(lz->iters);
     Py_XDECREF(lz->func);
     Py_TYPE(lz)->tp_free(lz);
+    Py_TRASHCAN_SAFE_END(lz)
 }
 
 static int
@@ -2220,9 +2227,11 @@ static void
 zip_dealloc(zipobject *lz)
 {
     PyObject_GC_UnTrack(lz);
+    Py_TRASHCAN_SAFE_BEGIN(lz)
     Py_XDECREF(lz->ittuple);
     Py_XDECREF(lz->result);
     Py_TYPE(lz)->tp_free(lz);
+    Py_TRASHCAN_SAFE_END(lz)
 }
 
 static int
@@ -2245,15 +2254,15 @@ zip_next(zipobject *lz)
 
     if (tuplesize == 0)
         return NULL;
+    if (Py_EnterRecursiveCall(" while iterating"))
+        return NULL;
     if (Py_REFCNT(result) == 1) {
         Py_INCREF(result);
         for (i=0 ; i < tuplesize ; i++) {
             it = PyTuple_GET_ITEM(lz->ittuple, i);
             item = (*Py_TYPE(it)->tp_iternext)(it);
-            if (item == NULL) {
-                Py_DECREF(result);
-                return NULL;
-            }
+            if (item == NULL)
+                goto error;
             olditem = PyTuple_GET_ITEM(result, i);
             PyTuple_SET_ITEM(result, i, item);
             Py_DECREF(olditem);
@@ -2261,18 +2270,21 @@ zip_next(zipobject *lz)
     } else {
         result = PyTuple_New(tuplesize);
         if (result == NULL)
-            return NULL;
+            goto error;
         for (i=0 ; i < tuplesize ; i++) {
             it = PyTuple_GET_ITEM(lz->ittuple, i);
             item = (*Py_TYPE(it)->tp_iternext)(it);
-            if (item == NULL) {
-                Py_DECREF(result);
-                return NULL;
-            }
+            if (item == NULL)
+                goto error;
             PyTuple_SET_ITEM(result, i, item);
         }
     }
+    Py_LeaveRecursiveCall();
     return result;
+error:
+    Py_XDECREF(result);
+    Py_LeaveRecursiveCall();
+    return NULL;
 }
 
 static PyObject *