Skip to content

Commit 974d757

Browse files
arigoarigo
committed
Upon insertion, if memory runs out, the deque was left in a corrupted state.
deque_item(): a performance bug: the linked list of blocks was followed from the left in most cases, because the test (i < (deque->len >> 1)) was after "i %= BLOCKLEN". deque_clear(): replaced a call to deque_len() with deque->len; not sure what this call was here for, nor if all compilers under the sun would inline it. deque_traverse(): I belive that it could be called by the GC when the deque has leftblock==rightblock==NULL, because it is tracked before the first block is allocated (though closely before). Still, a C extension module subclassing deque could provide its own tp_alloc that could trigger a GC collection after the PyObject_GC_Track()... deque_richcompare(): rewrote to cleanly check for end-of-iterations instead of relying on deque.__iter__().next() to succeed exactly len(deque) times -- an assumption which can break if deques are subclassed. Added a test. I wonder if the length should be explicitely bounded to INT_MAX, with OverflowErrors, as in listobject.c. On 64-bit machines, adding more than INT_MAX in the deque will result in trouble. (Note to anyone/me fixing this: carefully check for overflows if len is close to INT_MAX in the following functions: deque_rotate(), deque_item(), deque_ass_item())
1 parent 565ea5a commit 974d757

2 files changed

Lines changed: 43 additions & 34 deletions

File tree

‎Lib/test/test_deque.py‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -479,6 +479,15 @@ def test_weakref(self):
479479
d = None
480480
self.assertRaises(ReferenceError, str, p)
481481

482+
def test_strange_subclass(self):
483+
class X(deque):
484+
def __iter__(self):
485+
return iter([])
486+
d1 = X([1,2,3])
487+
d2 = X([4,5,6])
488+
d1 == d2 # not clear if this is supposed to be True or False,
489+
# but it used to give a SystemError
490+
482491
#==============================================================================
483492

484493
libreftest = """

‎Modules/collectionsmodule.c‎

Lines changed: 34 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -108,19 +108,19 @@ deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
108108
static PyObject *
109109
deque_append(dequeobject *deque, PyObject *item)
110110
{
111-
deque->rightindex++;
112-
deque->len++;
113111
deque->state++;
114-
if (deque->rightindex == BLOCKLEN) {
112+
if (deque->rightindex == BLOCKLEN-1) {
115113
block *b = newblock(deque->rightblock, NULL);
116114
if (b == NULL)
117115
return NULL;
118116
assert(deque->rightblock->rightlink == NULL);
119117
deque->rightblock->rightlink = b;
120118
deque->rightblock = b;
121-
deque->rightindex = 0;
119+
deque->rightindex = -1;
122120
}
123121
Py_INCREF(item);
122+
deque->len++;
123+
deque->rightindex++;
124124
deque->rightblock->data[deque->rightindex] = item;
125125
Py_RETURN_NONE;
126126
}
@@ -130,19 +130,19 @@ PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");
130130
static PyObject *
131131
deque_appendleft(dequeobject *deque, PyObject *item)
132132
{
133-
deque->leftindex--;
134-
deque->len++;
135133
deque->state++;
136-
if (deque->leftindex == -1) {
134+
if (deque->leftindex == 0) {
137135
block *b = newblock(NULL, deque->leftblock);
138136
if (b == NULL)
139137
return NULL;
140138
assert(deque->leftblock->leftlink == NULL);
141139
deque->leftblock->leftlink = b;
142140
deque->leftblock = b;
143-
deque->leftindex = BLOCKLEN - 1;
141+
deque->leftindex = BLOCKLEN;
144142
}
145143
Py_INCREF(item);
144+
deque->len++;
145+
deque->leftindex--;
146146
deque->leftblock->data[deque->leftindex] = item;
147147
Py_RETURN_NONE;
148148
}
@@ -233,10 +233,8 @@ deque_extend(dequeobject *deque, PyObject *iterable)
233233
return NULL;
234234

235235
while ((item = PyIter_Next(it)) != NULL) {
236-
deque->rightindex++;
237-
deque->len++;
238236
deque->state++;
239-
if (deque->rightindex == BLOCKLEN) {
237+
if (deque->rightindex == BLOCKLEN-1) {
240238
block *b = newblock(deque->rightblock, NULL);
241239
if (b == NULL) {
242240
Py_DECREF(item);
@@ -246,8 +244,10 @@ deque_extend(dequeobject *deque, PyObject *iterable)
246244
assert(deque->rightblock->rightlink == NULL);
247245
deque->rightblock->rightlink = b;
248246
deque->rightblock = b;
249-
deque->rightindex = 0;
247+
deque->rightindex = -1;
250248
}
249+
deque->len++;
250+
deque->rightindex++;
251251
deque->rightblock->data[deque->rightindex] = item;
252252
}
253253
Py_DECREF(it);
@@ -269,10 +269,8 @@ deque_extendleft(dequeobject *deque, PyObject *iterable)
269269
return NULL;
270270

271271
while ((item = PyIter_Next(it)) != NULL) {
272-
deque->leftindex--;
273-
deque->len++;
274272
deque->state++;
275-
if (deque->leftindex == -1) {
273+
if (deque->leftindex == 0) {
276274
block *b = newblock(NULL, deque->leftblock);
277275
if (b == NULL) {
278276
Py_DECREF(item);
@@ -282,8 +280,10 @@ deque_extendleft(dequeobject *deque, PyObject *iterable)
282280
assert(deque->leftblock->leftlink == NULL);
283281
deque->leftblock->leftlink = b;
284282
deque->leftblock = b;
285-
deque->leftindex = BLOCKLEN - 1;
283+
deque->leftindex = BLOCKLEN;
286284
}
285+
deque->len++;
286+
deque->leftindex--;
287287
deque->leftblock->data[deque->leftindex] = item;
288288
}
289289
Py_DECREF(it);
@@ -365,7 +365,7 @@ deque_item(dequeobject *deque, int i)
365365
{
366366
block *b;
367367
PyObject *item;
368-
int n;
368+
int n, index=i;
369369

370370
if (i < 0 || i >= deque->len) {
371371
PyErr_SetString(PyExc_IndexError,
@@ -383,7 +383,7 @@ deque_item(dequeobject *deque, int i)
383383
i += deque->leftindex;
384384
n = i / BLOCKLEN;
385385
i %= BLOCKLEN;
386-
if (i < (deque->len >> 1)) {
386+
if (index < (deque->len >> 1)) {
387387
b = deque->leftblock;
388388
while (n--)
389389
b = b->rightlink;
@@ -514,7 +514,6 @@ deque_traverse(dequeobject *deque, visitproc visit, void *arg)
514514
int index;
515515
int indexlo = deque->leftindex;
516516

517-
assert(deque->leftblock != NULL);
518517
for (b = deque->leftblock; b != NULL; b = b->rightlink) {
519518
const int indexhi = b == deque->rightblock ?
520519
deque->rightindex :
@@ -642,7 +641,7 @@ static PyObject *
642641
deque_richcompare(PyObject *v, PyObject *w, int op)
643642
{
644643
PyObject *it1=NULL, *it2=NULL, *x, *y;
645-
int i, b, vs, ws, minlen, cmp=-1;
644+
int b, vs, ws, cmp=-1;
646645

647646
if (!PyObject_TypeCheck(v, &deque_type) ||
648647
!PyObject_TypeCheck(w, &deque_type)) {
@@ -673,16 +672,13 @@ deque_richcompare(PyObject *v, PyObject *w, int op)
673672
it2 = PyObject_GetIter(w);
674673
if (it2 == NULL)
675674
goto done;
676-
minlen = (vs < ws) ? vs : ws;
677-
for (i=0 ; i < minlen ; i++) {
675+
for (;;) {
678676
x = PyIter_Next(it1);
679-
if (x == NULL)
677+
if (x == NULL && PyErr_Occurred())
680678
goto done;
681679
y = PyIter_Next(it2);
682-
if (y == NULL) {
683-
Py_DECREF(x);
684-
goto done;
685-
}
680+
if (x == NULL || y == NULL)
681+
break;
686682
b = PyObject_RichCompareBool(x, y, Py_EQ);
687683
if (b == 0) {
688684
cmp = PyObject_RichCompareBool(x, y, op);
@@ -695,14 +691,18 @@ deque_richcompare(PyObject *v, PyObject *w, int op)
695691
if (b == -1)
696692
goto done;
697693
}
698-
/* Elements are equal through minlen. The longest input is the greatest */
694+
/* We reached the end of one deque or both */
695+
Py_XDECREF(x);
696+
Py_XDECREF(y);
697+
if (PyErr_Occurred())
698+
goto done;
699699
switch (op) {
700-
case Py_LT: cmp = vs < ws; break;
701-
case Py_LE: cmp = vs <= ws; break;
702-
case Py_EQ: cmp = vs == ws; break;
703-
case Py_NE: cmp = vs != ws; break;
704-
case Py_GT: cmp = vs > ws; break;
705-
case Py_GE: cmp = vs >= ws; break;
700+
case Py_LT: cmp = y != NULL; break; /* if w was longer */
701+
case Py_LE: cmp = x == NULL; break; /* if v was not longer */
702+
case Py_EQ: cmp = x == y; break; /* if we reached the end of both */
703+
case Py_NE: cmp = x != y; break; /* if one deque continues */
704+
case Py_GT: cmp = x != NULL; break; /* if v was longer */
705+
case Py_GE: cmp = y == NULL; break; /* if w was not longer */
706706
}
707707

708708
done:

0 commit comments

Comments
 (0)