Undefined behavior for deque.insert() when len(d) == maxlen

[rhettinger]

BPO	26194
Nosy	@tim-one, @rhettinger, @mdickinson, @vstinner, @vadmium, @serhiy-storchaka, @MojoVampire
Files	full_deque.diff: Option to raise an IndexError full_deque_alt.diff: Plain insert followed by pop from right full_deque2.diff: Index error for insert into a full deque

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2016-02-07.09:06:11.915>
created_at = <Date 2016-01-24.17:47:04.579>
labels = ['extension-modules', 'type-bug']
title = 'Undefined behavior for deque.insert() when len(d) == maxlen'
updated_at = <Date 2016-02-07.09:06:11.915>
user = 'https://github.com/rhettinger'

bugs.python.org fields:

activity = <Date 2016-02-07.09:06:11.915>
actor = 'rhettinger'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2016-02-07.09:06:11.915>
closer = 'rhettinger'
components = ['Extension Modules']
creation = <Date 2016-01-24.17:47:04.579>
creator = 'rhettinger'
dependencies = []
files = ['41717', '41718', '41732']
hgrepos = []
issue_num = 26194
keywords = ['patch']
message_count = 28.0
messages = ['258893', '258943', '258947', '258948', '258995', '258996', '259004', '259005', '259007', '259010', '259043', '259046', '259050', '259055', '259063', '259072', '259115', '259156', '259216', '259359', '259369', '259372', '259405', '259418', '259501', '259507', '259519', '259527']
nosy_count = 8.0
nosy_names = ['tim.peters', 'rhettinger', 'mark.dickinson', 'vstinner', 'python-dev', 'martin.panter', 'serhiy.storchaka', 'josh.r']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue26194'
versions = ['Python 3.5', 'Python 3.6']

[rhettinger]

The behavior of deque.insert() in a bounded deque is a bit odd:

>>> from collections import deque
>>> d = deque(range(20), maxlen=10)
>>> d
deque([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], maxlen=10)
>>> d.insert(3, 'New')
>>> d
deque([19, 10, 11, 'New', 13, 14, 15, 16, 17, 18], maxlen=10)
#       ^   ^        ^--- The 12 got replaced
#       |   \--- The elements before the insertion point got rotated
#       \--- The final element got rotated to first position

With append/appendleft/extend/extendleft, the intended and useful behavior for maxlen is to pop from the opposite end. But for deque.insert(), the best and most useful behavior invariants are less obvious.

Ideally, the effect of d.insert(0, item) would be the same as d.appendleft(item), and the effect of d.insert(len(d), item) would be the same as d.append(item).

Also, d.insert(i, newitem) should have the post-condition:

assert d[i] == newitem if i < len(d) else d[-1] == newitem

Having decided where to put the newitem, the question turns to deciding which element should be popped-off to maintain the size invariant.

I'm thinking that it should always be the rightmost element that gets popped, so that items before the inserted element never get moved. This matches what insert() does for unbounded deques, making it the least surprising choice.

[rhettinger]

Mark, Serhiy and Timmy, do you have any thoughts on what is the right behavior?

One option is to always pop the rightmost element to make room, but that results in a weird asymmetry between d.insert(len(d), item) and what d.append(item) would do. I can't seem to come with a coherent set of invariants that doesn't have a surprising discontinuity.

Another option is to "refuse the temptation to guess" at what the user intends for the popped-off element to be and to raise an exception. But that isn't very user friendly either.

[rhettinger]

Another take: Do a regular insertion with no special cases, followed by a pop from the right:

>>> for i in range(len(d) + 1):
	s = list(d)
	s.insert(i, None)      
	_ = s.pop()
	print(i, s)
	
0 [None, 'a', 'b']
1 ['a', None, 'b']
2 ['a', 'b', None]
3 ['a', 'b', 'c']

Nice parts:

• Doesn't change pop direction depending on the inputs
• Guarantee that entries to the left of i will keep their position.
• Post condition of d[i]==newelem applies whenever i exists.

Not nice part:

• Initially surprising that d.insert(len(d), newelem) does not actually insert newelem.
• d.insert(len(d), newelem) not the same as d.append(newelem).

Another alternative is to raise an exception for the one case where index==maxlen, with the theory being that d[index] won't be a valid index so you can't insert anything there.

[rhettinger]

The plain-insert-followed-by-a-pop-on-the-right is giving reasonable results with nice properties:

d.insert(0, i)

---

0 --> deque([0], maxlen=4)
1 --> deque([1, 0], maxlen=4)
2 --> deque([2, 1, 0], maxlen=4)
3 --> deque([3, 2, 1, 0], maxlen=4)
4 --> deque([4, 3, 2, 1], maxlen=4)
5 --> deque([5, 4, 3, 2], maxlen=4)
6 --> deque([6, 5, 4, 3], maxlen=4)
7 --> deque([7, 6, 5, 4], maxlen=4)
8 --> deque([8, 7, 6, 5], maxlen=4)
9 --> deque([9, 8, 7, 6], maxlen=4)

d.insert(len(d), i)
-----------------------------------
0 --> deque([0], maxlen=4)
1 --> deque([0, 1], maxlen=4)
2 --> deque([0, 1, 2], maxlen=4)
3 --> deque([0, 1, 2, 3], maxlen=4)
4 --> deque([0, 1, 2, 3], maxlen=4)
5 --> deque([0, 1, 2, 3], maxlen=4)
6 --> deque([0, 1, 2, 3], maxlen=4)
7 --> deque([0, 1, 2, 3], maxlen=4)
8 --> deque([0, 1, 2, 3], maxlen=4)
9 --> deque([0, 1, 2, 3], maxlen=4)

[python-dev]

New changeset ce3d47eaeb21 by Raymond Hettinger in branch '3.5':
Issue bpo-26194: Fix undefined behavior for deque.insert() when len(d) == maxlen
https://hg.python.org/cpython/rev/ce3d47eaeb21

[serhiy-storchaka]

New behavior looks less surprising to me.

Old behavior is even more weird for negative indices:

>>> from collections import deque
>>> d = deque(range(20), maxlen=10)
>>> d
deque([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], maxlen=10)
>>> d.insert(-3, 'New')
>>> d
deque([11, 12, 13, 14, 15, 16, 'New', 18, 19, 10], maxlen=10)

Note that new element not just replaced the old one in the middle of the deque, but all context was rotated one position left.

Patched code behave less surprising.

>>> d.insert(-3, 'New')
>>> d                                                                   
deque([10, 11, 12, 13, 14, 15, 'New', 16, 17, 18], maxlen=10)

[serhiy-storchaka]

But the postcondition d[i] == newitem is broken if i is negative.

>>> d = deque('ABC', maxlen=3)
>>> d.insert(-1, None)
>>> d
deque(['A', None, 'B'], maxlen=3)

I would expected ['A', 'B', None].

[vstinner]

I would expected ['A', 'B', None].

Hum, it seems consistent with list behaviour, no?

>>> x=list("abc")
>>> x.insert(-1, "X")
>>> x
['a', 'b', 'X', 'c']

-1 is the same than len(x)-1 (2 in this example).

deque(['A', None, 'B'], maxlen=3) seems correct to me.

[serhiy-storchaka]

-1 is the position before the last element ('C'). After popping-off extra element the result can be ['A', 'B', None] or ['B', None, 'C'].

[vstinner]

-1 is the position before the last element ('C'). After popping-off extra element the result can be ['A', 'B', None] or ['B', None, 'C'].

Oh ok :-) Now I'm confused, I don't know what is the expected behaviour :-)