[Python-checkins] cpython (2.7): Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list

antoine.pitrou python-checkins at python.org
Mon Mar 4 20:33:55 CET 2013


http://hg.python.org/cpython/rev/21ded74b51fa
changeset:   82478:21ded74b51fa
branch:      2.7
parent:      82475:654136546895
user:        Antoine Pitrou <solipsis at pitrou.net>
date:        Mon Mar 04 20:30:01 2013 +0100
summary:
  Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently.

files:
  Lib/test/test_heapq.py |  26 +++++++++++++++++++
  Misc/NEWS              |   3 ++
  Modules/_heapqmodule.c |  40 +++++++++++++++++++++++++----
  3 files changed, 63 insertions(+), 6 deletions(-)


diff --git a/Lib/test/test_heapq.py b/Lib/test/test_heapq.py
--- a/Lib/test/test_heapq.py
+++ b/Lib/test/test_heapq.py
@@ -315,6 +315,16 @@
     'Test multiple tiers of iterators'
     return chain(imap(lambda x:x, R(Ig(G(seqn)))))
 
+class SideEffectLT:
+    def __init__(self, value, heap):
+        self.value = value
+        self.heap = heap
+
+    def __lt__(self, other):
+        self.heap[:] = []
+        return self.value < other.value
+
+
 class TestErrorHandling(TestCase):
     module = None
 
@@ -361,6 +371,22 @@
                 self.assertRaises(TypeError, f, 2, N(s))
                 self.assertRaises(ZeroDivisionError, f, 2, E(s))
 
+    # Issue #17278: the heap may change size while it's being walked.
+
+    def test_heappush_mutating_heap(self):
+        heap = []
+        heap.extend(SideEffectLT(i, heap) for i in range(200))
+        # Python version raises IndexError, C version RuntimeError
+        with self.assertRaises((IndexError, RuntimeError)):
+            self.module.heappush(heap, SideEffectLT(5, heap))
+
+    def test_heappop_mutating_heap(self):
+        heap = []
+        heap.extend(SideEffectLT(i, heap) for i in range(200))
+        # Python version raises IndexError, C version RuntimeError
+        with self.assertRaises((IndexError, RuntimeError)):
+            self.module.heappop(heap)
+
 
 class TestErrorHandlingPython(TestErrorHandling):
     module = py_heapq
diff --git a/Misc/NEWS b/Misc/NEWS
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -214,6 +214,9 @@
 Library
 -------
 
+- Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when
+  the list is being resized concurrently.
+
 - Issue #17018: Make Process.join() retry if os.waitpid() fails with EINTR.
 
 - Issue #14720: sqlite3: Convert datetime microseconds correctly.
diff --git a/Modules/_heapqmodule.c b/Modules/_heapqmodule.c
--- a/Modules/_heapqmodule.c
+++ b/Modules/_heapqmodule.c
@@ -35,12 +35,14 @@
 static int
 _siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
 {
-    PyObject *newitem, *parent;
+    PyObject *newitem, *parent, *olditem;
     int cmp;
     Py_ssize_t parentpos;
+    Py_ssize_t size;
 
     assert(PyList_Check(heap));
-    if (pos >= PyList_GET_SIZE(heap)) {
+    size = PyList_GET_SIZE(heap);
+    if (pos >= size) {
         PyErr_SetString(PyExc_IndexError, "index out of range");
         return -1;
     }
@@ -57,12 +59,24 @@
             Py_DECREF(newitem);
             return -1;
         }
+        if (size != PyList_GET_SIZE(heap)) {
+            Py_DECREF(newitem);
+            PyErr_SetString(PyExc_RuntimeError,
+                            "list changed size during iteration");
+            return -1;
+        }
         if (cmp == 0)
             break;
         Py_INCREF(parent);
-        Py_DECREF(PyList_GET_ITEM(heap, pos));
+        olditem = PyList_GET_ITEM(heap, pos);
         PyList_SET_ITEM(heap, pos, parent);
+        Py_DECREF(olditem);
         pos = parentpos;
+        if (size != PyList_GET_SIZE(heap)) {
+            PyErr_SetString(PyExc_RuntimeError,
+                            "list changed size during iteration");
+            return -1;
+        }
     }
     Py_DECREF(PyList_GET_ITEM(heap, pos));
     PyList_SET_ITEM(heap, pos, newitem);
@@ -74,10 +88,12 @@
 {
     Py_ssize_t startpos, endpos, childpos, rightpos;
     int cmp;
-    PyObject *newitem, *tmp;
+    PyObject *newitem, *tmp, *olditem;
+    Py_ssize_t size;
 
     assert(PyList_Check(heap));
-    endpos = PyList_GET_SIZE(heap);
+    size = PyList_GET_SIZE(heap);
+    endpos = size;
     startpos = pos;
     if (pos >= endpos) {
         PyErr_SetString(PyExc_IndexError, "index out of range");
@@ -102,13 +118,25 @@
             if (cmp == 0)
                 childpos = rightpos;
         }
+        if (size != PyList_GET_SIZE(heap)) {
+            Py_DECREF(newitem);
+            PyErr_SetString(PyExc_RuntimeError,
+                            "list changed size during iteration");
+            return -1;
+        }
         /* Move the smaller child up. */
         tmp = PyList_GET_ITEM(heap, childpos);
         Py_INCREF(tmp);
-        Py_DECREF(PyList_GET_ITEM(heap, pos));
+        olditem = PyList_GET_ITEM(heap, pos);
         PyList_SET_ITEM(heap, pos, tmp);
+        Py_DECREF(olditem);
         pos = childpos;
         childpos = 2*pos + 1;
+        if (size != PyList_GET_SIZE(heap)) {
+            PyErr_SetString(PyExc_RuntimeError,
+                            "list changed size during iteration");
+            return -1;
+        }
     }
 
     /* The leaf at pos is empty now.  Put newitem there, and and bubble

-- 
Repository URL: http://hg.python.org/cpython


More information about the Python-checkins mailing list