deque.pop(index) is not supported

[Akuli]

BPO	41409
Nosy	@rhettinger, @JimJJewett, @serhiy-storchaka, @Akuli, @pablogsal, @ShubhamKJha, @KmolYuan

^{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 = None
closed_at = <Date 2020-07-28.03:30:22.736>
created_at = <Date 2020-07-27.14:18:55.663>
labels = ['type-bug', 'library', '3.10']
title = 'deque.pop(index) is not supported'
updated_at = <Date 2020-07-28.17:48:46.574>
user = 'https://github.com/Akuli'

bugs.python.org fields:

activity = <Date 2020-07-28.17:48:46.574>
actor = 'pablogsal'
assignee = 'none'
closed = True
closed_date = <Date 2020-07-28.03:30:22.736>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2020-07-27.14:18:55.663>
creator = 'Akuli'
dependencies = []
files = []
hgrepos = []
issue_num = 41409
keywords = []
message_count = 14.0
messages = ['374378', '374380', '374381', '374382', '374384', '374386', '374415', '374432', '374458', '374464', '374472', '374483', '374493', '374514']
nosy_count = 8.0
nosy_names = ['rhettinger', 'stutzbach', 'Jim.Jewett', 'serhiy.storchaka', 'Akuli', 'pablogsal', 'ShubhamKJha', 'Yuan']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue41409'
versions = ['Python 3.10']

[Akuli]

The pop method of collections.deque can't be used like deque.pop(index), even though del deque[index] or deque.pop() without an argument works. This breaks the Liskov substitution principle because collections.abc.MutableMapping supports the .pop(index) usage. Is this intentional?

related typeshed issue: python/typeshed#4364

[serhiy-storchaka]

deque is not a subclass of MutableMapping, so the Liskov substitution principle is not related here.

deque is not registered as a virtual subclass of MutableMapping and it lacks a number of MutableMapping methods.

>>> import collections.abc
>>> issubclass(collections.deque, collections.abc.MutableMapping)
False
>>> sorted(set(dir(collections.abc.MutableMapping)) - set(dir(collections.deque)))
['_MutableMapping__marker', '__abstractmethods__', '__module__', '__slots__', '_abc_impl', 'get', 'items', 'keys', 'popitem', 'setdefault', 'update', 'values']

[Akuli]

I meant MutableSequence instead of MutableMapping. Oops.

[serhiy-storchaka]

>>> issubclass(collections.deque, collections.abc.MutableSequence)
True
>>> sorted(set(dir(collections.abc.MutableSequence)) - set(dir(collections.deque)))
['__abstractmethods__', '__module__', '__slots__', '_abc_impl']

Well, it is a bug.

[KmolYuan]

Same status as slicing support from MutableSequence.

[ShubhamKJha]

Hi, I want to start contributing to CPython. Can I take up this issue?

[pablogsal]

Hi, I want to start contributing to CPython. Can I take up this issue?

Sure, go ahead. Feel free to ping one of us in the PR for review

[jimjjewett]

It may well have been intentional, as deques should normally be mutated only at the ends. But Raymond did make changes to conform to the ABC, so this should probably be supported too. Go ahead and include docstrings and/or discouraging it, though, except for i=0 and i=-1

[rhettinger]

This was an intentional decision. Deques designed for fast access at the end points. Also, pop() is a core deque operation that needs to be fast. Altering its signature with an optional argument would slow it down.

Thank you for the suggestion, but we really shouldn't do this.

[rhettinger]

FWIW, the relationship between a concrete class and an ABC is normative with respect to core capabilities but isn't 100% strict. Concrete classes can vary in small respects when it makes sense. For example, the __or__ and __and__ methods for collections.Set will accept any iterable, but the concrete does not.

We use the Liskov substitution principle as a guide, not as a law. In a number of cases, we choose practicality-beats-purity and allow subclasses to differ in ways than their parents. Counter() doesn't support fromkeys(). OrderedDict.popitem() has different signature than dict.popitem().

Hope that insight was helpful.

[serhiy-storchaka]

If deque does not fully support the MutableSequence interface, should not it be un-regitered as MutableSequence? Maybe we need other abstract class which would be parent of MutableSequence and deque?

[Akuli]

I don't think it's very common to write code that needs to work with any MutableSequence but not with any Sequence. I think that's the only situation where missing support for deque.pop(index) is a problem.

Maybe deque should be a Sequence but not a MutableSequence. Or maybe there should be a way to say "MutableSequence does not require support for .pop(index) even though you get it by inheriting from MutableSequence".

[rhettinger]

If deque does not fully support the MutableSequence interface,
should not it be un-regitered as MutableSequence?

You could unregister it, but for such a minor variance, it isn't worth it. We're not unregistering sets and frozenset from Set even though there are minor variances in the operators.

The ABCs are quite limited in what they do. The underlying machinery is mostly about determining whether a method is present or not. Concrete classes are free to override, extend or raise NotImplemented. For example, a Counter is still a mapping even though fromkeys() raises NotImplemented and update() has different semantics than Mapping.

Jelle has already adapted TypeShed to match the concrete class, so no actual user issue remains.

[pablogsal]

I am convinced by Raymond's argument, it seems that with the current state of the ABC classes and semantics the most pragmatical solution is the status quo. It would be a weird if deque is a Sequence but not a MutableSequence because it can clearly be mutated.

[AndreiPashkin]

@rhettinger, what do you think about adding more general purpose collections like LinkedList and DoublyLinkedList to collections? I've encountered a use case where I'd need them and there is no single popular and well-maintained library in Python's eco-system that has them implemented.

[AndreiPashkin]

@rhettinger

Deques designed for fast access at the end points. Also, pop() is a core deque operation that needs to be fast. Altering its signature with an optional argument would slow it down.

Also a counter-argument to that. collections.deque has insert(i, x) that supports indexing and conforms with MutableSequence interface even though it could be made faster without indexing. So if we already have index(i, x), why couldn't we have pop(i)? And for speed it would be possible to add a special method like fast_pop().