Mailman 3 Bug or not? Different behaviour iterating list and collections.deque - Python-Dev

Bug or not? Different behaviour iterating list and collections.deque

Christos Georgiou

7 Jan 2007 7 Jan '07

2:38 a.m.

Hello, people. I am not sure whether this is a bug or intentional, so I thought checking it with you before opening a bug. I will explain this issue, but please understand this is not a question for help to change the algorithm (this has been done already), so it's not a question of c.l.py. It's a matter of discrepancy. A list that changes while iterating produces no errors, while a deque fails. Given the following example code: #code start import itertools, collections def item_is_special(item): "Just a dummy check in this example" return item % 3 == 0 def item_products(item): "Also a dummy function for the example" return [item*20+1, item*30+1] def process_list(items, type_of_que, special_case): # we want to process some items, but some of them # produce other items to be processed by the # same algorithm products= type_of_que() if special_case: products.append(-1) for item in itertools.chain(items, products): if item_is_special(item): for product in item_products(item): products.append(product) else: print "got", item #code end we have the following cases:

...

...
...
process_list(numbers, list, False) got 1 got 2 got 61 got 91

List works as expected.

...

...
...
process_list(numbers, collections.deque, False) got 1 got 2

deque does not work, most probably because deque.__iter__ of an empty deque ignores later changes. For this reason the `special_case' parameter was inserted in the code above, so that there is at least an item when itertools.chain calls iter on the deque:

...

...
...
process_list(numbers, collections.deque, True) got 1 got 2 Traceback (most recent call last): File "<stdin>", line 1, in <module> File "testdequeiter.py", line 17, in process_list for item in itertools.chain(items, products): RuntimeError: deque mutated during iteration

Is that intentional? If not, let me know so that I open a bug.

Show replies by date

Christos Georgiou

7 Jan 7 Jan

2:50 a.m.

New subject: Bug or not? Different behaviour iterating list andcollections.deque

Forgive my piggy backing, but I forgot to include the only related post I found, which did not clear things up for me: http://groups.google.com/group/comp.lang.python/msg/e2dcb2362649a601

Josiah Carlson

9:58 a.m.

"Christos Georgiou" wrote:

...

Hello, people. I am not sure whether this is a bug or intentional, so I thought checking it with you before opening a bug. I will explain this issue, but please understand this is not a question for help to change the algorithm (this has been done already), so it's not a question of c.l.py. It's a matter of discrepancy.

[snip]

...

Forgive my piggy backing, but I forgot to include the only related post I found, which did not clear things up for me:

http://groups.google.com/group/comp.lang.python/msg/e2dcb2362649a601

Lists are not deques, deques are not lists. As stated in the post you link to states, the behavior of lists and deques is different in the same situation, so while one may "work" for your task, the other may not. I would, generally speaking, concur with Rayomond's recommendation in the post and say that mutation of the item you are iterating over is confusing, and it certainly is likely far more tricky than you should be when writing software so that people can use it. In this case, you are making it even worse by attempting to merge a list and deque, under the presumption that they should do the same thing. They don't. They are documented not to do the same thing. And you read a post explaining that they don't do the same thing and cited it. My suggestion: don't do what you are doing. Input list, output list. Make your life simple. Appending to a list is fast. If you *need* to merge a list and deque, do to some insane requirements by an organization, write your own wrapper that does what you think is the right thing to do in this case. - Josiah

Christos Georgiou

10:23 a.m.

New subject: Bug or not? Different behaviour iterating list andcollections.deque

"Josiah Carlson" wrote in message news:20070107095022.8D37.JCARLSON@uci.edu...

...

"Christos Georgiou" wrote:

...

...
[snip] issue, but please understand this is not a question for help to change the algorithm (this has been done already), so it's not a question of c.l.py. It's a matter of discrepancy. [snip]

[snip Josiah's wordy "it's intentional and not a bug" in the form of a suggestion for a change of algorithm]

Like I said, this wasn't a c.l.py question, even if you thought it deserved a c.l.py answer. In any case, you answered my question, and thank you. It not being a bug suits me just fine. Allow me to make sure we talk about the same thing here, though: both the example code I provided and the original one do modify the iterable *only* between the following A and B points in time: Point A: itertools.chain calls iter() on the iterable. (Appending to the iterable (list, deque) occur here, and only here.) Point B: itertools.chain starts calling iterable.next(). This is a different case from the one mentioned in the post by Raymond, and that is why I asked. For example, if itertools.chain called iter() on its arguments when actually needing to iterate over them instead of at the beginning, the code would work. But I really, really don't mind whatever the function, as long as it's by design, and that's the reason I didn't submit a bug in the tracker. That's all. I won't (and never intended) to defend any algorithms.

"Martin v. Löwis"

4:37 p.m.

New subject: Bug or not? Different behaviour iterating list and collections.deque

Christos Georgiou schrieb:

...

Is that intentional?

It would have helped if you had said what "that" is you are referring to, it would also have helped if you had stated an opinion on whether you believe that to be a bug. For example, I think I would have phrased your post like this: """ If I apply .next() to an iter of a deque that has been modified, I get a RuntimeError: py> d=collections.deque() py> d.append(10) py> i=iter(d) py> d.append(10) py> i.next() Traceback (most recent call last): File "<stdin>", line 1, in ? RuntimeError: deque mutated during iteration Yet when I apply .next() to an iter of an initially-empty deque, I get StopIteration: py> d=collections.deque() py> i=iter(d) py> d.append(10) py> i.next() Traceback (most recent call last): File "<stdin>", line 1, in ? StopIteration Is this a bug? Shouldn't the second example also raise the RuntimeError as the deque has been modified? (also, is appending an element a modification or a mutation?) """ To this question (.next on an iterator of a modified deque), my answer would be: "yes, that is a bug". However, I feel you are referring to a different issue, unfortunately, I cannot tell from your post what that issue is. Regards, Martin

Christos Georgiou

8 Jan 8 Jan

1:29 a.m.

""Martin v. Löwis"" wrote in message news:45A19243.2000109@v.loewis.de...

...

Christos Georgiou schrieb:

...
Is that intentional?

It would have helped if you had said what "that" is you are referring to, it would also have helped if you had stated an opinion on whether you believe that to be a bug. For example, I think I would have phrased your post like this:

Yes, you are correct: I see now that I was too cryptic, but being cryptic was not my intention; instead, I wanted to avoid a discussion on the issue of the algorithm, which I didn't manage to avoid, so obviously my terseness was mistaken. I should be clear from the start. In retrospection, the example code I chose, although it showed the two issues I thought important ('list / deque iteration discrepancy' and 'empty / non-empty deque iteration discrepancy') was not as plain as needed, since it gave to Josiah, at least, the impression that the matter was about list / deque merging.

...

""" If I apply .next() to an iter of a deque that has been modified, I get a RuntimeError:

py> d=collections.deque() py> d.append(10) py> i=iter(d) py> d.append(10) py> i.next() Traceback (most recent call last): File "<stdin>", line 1, in ? RuntimeError: deque mutated during iteration

Yet when I apply .next() to an iter of an initially-empty deque, I get StopIteration:

py> d=collections.deque() py> i=iter(d) py> d.append(10) py> i.next() Traceback (most recent call last): File "<stdin>", line 1, in ? StopIteration

Is this a bug? Shouldn't the second example also raise the RuntimeError as the deque has been modified? (also, is appending an element a modification or a mutation?) """

To this question (.next on an iterator of a modified deque), my answer would be: "yes, that is a bug".

Yes. This behaviour was meant to be shown with the 'special_case' check. I will open a bug for this.

...

However, I feel you are referring to a different issue, unfortunately, I cannot tell from your post what that issue is.

No, you managed to capture large part of the essence of what I was saying, but again, this was not your responsibility, but mine. I should be more explicit. Thank you.

Raymond Hettinger

9:16 a.m.

New subject: Bug or not? Different behaviour iterating list andcollections.deque

"Christos Georgiou"

...

In retrospection, the example code I chose, although it showed the two issues I thought important ('list / deque iteration discrepancy' and 'empty / non-empty deque iteration discrepancy') was not as plain as needed, ...

Lists are unique in the way they allow mutation during iteration because indexed lookup allows for a meaningful definition of what should be done as the list mutates. In contrast, deques are more like dictionaries and should not be mutated during iteration. The issue is that a deque could be so substantially modified that there is not a clear, meaningful, and useful definition of what item should be next served-up. With respect to the second question, please assign an SF report to me and I'll look at it in detail when I have time. It appears to be an idiosyncracy resulting from the ordering of the test for StopIteration versus the test for RuntimeError. The question is whether I can swap the test order without introducing other anomalies. Raymond P.S. The patch would look like this: Index: collectionsmodule.c =================================================================== --- collectionsmodule.c (revision 53281) +++ collectionsmodule.c (working copy) @@ -911,15 +911,14 @@ { PyObject *item; - if (it->counter == 0) - return NULL; - if (it->deque->state != it->state) { it->counter = 0; PyErr_SetString(PyExc_RuntimeError, "deque mutated during iteration"); return NULL; } + if (it->counter == 0) + return NULL; assert (!(it->b == it->deque->rightblock && it->index > it->deque->rightindex));

6315

Age (days ago)

6316

Last active (days ago)

List overview

Download

6 comments

4 participants

participants (4)

"Martin v. Löwis"
Christos Georgiou
Josiah Carlson
Raymond Hettinger

Bug or not? Different behaviour iterating list and collections.deque

Christos Georgiou

Christos Georgiou

Josiah Carlson

Christos Georgiou

"Martin v. Löwis"

Christos Georgiou

Raymond Hettinger

tags

participants (4)