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

Mon Mar 4 20:39:48 CET 2013

http://hg.python.org/cpython/rev/451299b97b4f
changeset: 82480:451299b97b4f
branch: 3.3
parent: 82476:1a589001d752
parent: 82479:905b02749c26
user: Antoine Pitrou <solipsis at pitrou.net>
date: Mon Mar 04 20:33:36 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
@@ -319,6 +319,16 @@
 return chain(map(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:
 
 def test_non_sequence(self):
@@ -369,6 +379,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, TestCase):
 module = py_heapq
diff --git a/Misc/NEWS b/Misc/NEWS
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -193,6 +193,9 @@
 Library
 -------
 
+- Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when
+ the list is being resized concurrently.
+
 - Issue #16962: Use getdents64 instead of the obsolete getdents syscall
 in the subprocess module on Linux.
 
diff --git a/Modules/_heapqmodule.c b/Modules/_heapqmodule.c
--- a/Modules/_heapqmodule.c
+++ b/Modules/_heapqmodule.c
@@ -11,12 +11,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;
 }
@@ -33,12 +35,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);
@@ -50,10 +64,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");
@@ -79,13 +95,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
