collections.abc.Mapping should include a __reversed__ that raises TypeError

[abarnert]

BPO	25864
Nosy	@gvanrossum, @rhettinger, @terryjreedy, @ncoghlan, @bitdancer, @vadmium, @serhiy-storchaka, @Vgr255, @AlexWaygood
Files	cpython-iter-patch.diff

^{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 2021-12-15.06:41:16.363>
created_at = <Date 2015-12-15.03:38:38.957>
labels = ['type-bug', 'library']
title = 'collections.abc.Mapping should include a __reversed__ that raises TypeError'
updated_at = <Date 2021-12-15.06:41:16.362>
user = 'https://bugs.python.org/abarnert'

bugs.python.org fields:

activity = <Date 2021-12-15.06:41:16.362>
actor = 'rhettinger'
assignee = 'none'
closed = True
closed_date = <Date 2021-12-15.06:41:16.363>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2015-12-15.03:38:38.957>
creator = 'abarnert'
dependencies = []
files = ['41440']
hgrepos = []
issue_num = 25864
keywords = ['patch']
message_count = 34.0
messages = ['256434', '256435', '256436', '256437', '256438', '256439', '256442', '256572', '256576', '256578', '256579', '256643', '256645', '256690', '256712', '256910', '257045', '257046', '257049', '257053', '257057', '257062', '257063', '257064', '257128', '257276', '257308', '257314', '257483', '257484', '257485', '257494', '257500', '408571']
nosy_count = 11.0
nosy_names = ['gvanrossum', 'rhettinger', 'terry.reedy', 'ncoghlan', 'r.david.murray', 'martin.panter', 'serhiy.storchaka', 'abarnert', 'abarry', 'curioswati', 'AlexWaygood']
pr_nums = []
priority = 'low'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue25864'
versions = ['Python 3.6']

[abarnert]

Example:

    class MyDict(collections.abc.Mapping):
        def __init__(self, d): self.d = d
        def __len__(self): return len(self.d)
        def __getitem__(self, key): return self.d[key]
        def __iter__(self): return iter(self.d)

    d = {1:2, 3:4}
    m = MyDict({1: 2, 3: 4})

If you do reversed(d), you get a nice TypeError: argument to reversed() must be a sequence. But if you do reversed(m), you get a reversed iterator. And when you iterate it, presumably expecting to get 0 and 1 in some arbitrary order, you instead get 3, and then a KeyError: 0.

Of course it's obvious why this happens once you think about it: in order to handle types that implement the old-style sequence protocol (just respond to __getitem__ for all integers from 0 to len(self)), reversed has to fall back to trying __getitem__ for all integers from len(d)-1 to 0.

If you provide a __reversed__ method, it just calls that. Or, if you're a C-API mapping like dict, PySequence_Check will return false and it'll raise a TypeError. But for a Python mapping, there's no way PySequence_Check or anything else can know that you're not actually a sequence (after all, you implement __getitem__ and __len__), so it tries to use you as one, and confusion results.

I think trying to fix this for _all_ possible mappings is a non-starter.

But fixing it for mappings that use collections.abc.Mapping is easy: just provide a default implementation of collections.abc.Mapping.__reversed__ that just raises a TypeError.

I can't imagine this would break any working code. If it did, the workaround would be simple: just implement def __reversed__(self): return (self[k] for k in reversed(range(len(self)))).

[curioswati]

Can it be reproduced in default branch? I tried but got:
AttributeError: module 'collections' has no attribute 'abc'

[Vgr255]

You need to do 'import collections.abc' as abc is a submodule of collections, and is not imported from a bare 'import collections'.

[curioswati]

If you do reversed(d), you get a nice TypeError: argument to reversed() must be a sequence. But if you do reversed(m), you get a reversed iterator. And when you iterate it, presumably expecting to get 0 and 1 in some arbitrary order, you instead get 3, and then a KeyError:0.

I got 2 instead of 3.

What are we exactly expecting here? How can a dictionary be reversed?

I can't imagine this would break any working code. If it did, the workaround would be simple: just implement def __reversed__(self): return (self[k] for k in reversed(range(len(self)))).

This seems to make no difference. I still got the KeyError.

[abarnert]

What are we exactly expecting here?

Well, naively, I was expecting a TypeError, just as you get for dict, or a subclass of dict, or a custom extension type that implements the C-API mapping protocol.

Once you understand how reversed works, you can understand why it gives you a nonsensical and useless iterator instead. But nobody would actually _want_ that.

So, as I proposed in the initial description, and the title, what we should be doing is raising a TypeError.

How can a dictionary be reversed?

Assuming this is a pointless rhetorical question: That's exactly the point. There's no sensible meaning to reversing a dictionary, so it should raise a TypeError. Exactly as it already does for dict, subclasses of dict, and C-API mappings.

If this wasn't rhetorical: I guess you could argue that any arbitrary order in reverse is any arbitrary order, so even returning iter(m) would be acceptable. Or maybe reversed(list(m)) would be even better, if it didn't require O(N) space. But in practice, nobody will ever expect that--again, they don't get it from dict, subclasses, C-API mappings--so why go out of our way to implement it? So, again, it should raise a TypeError.

This seems to make no difference. I still got the KeyError.

Of course. Again, the current behavior is nonsensical, will almost always raise a KeyError at some point, and will never be anything a reasonable person wants. So a workaround that restores the current behavior will also be nonsensical, almost always raise a KeyError at some point, and never be anything a reasonable person wants.

But, if you happen to be unreasonably unreasonable--say, you created a mapping with {2:40, 0:10, 1:20} and actually wanted reversed(m) to confusingly give you 40, 20, 10--and this change did break your code, the workaround would restore it.

[rhettinger]

I've seen no evidence that this a problem in practice. It seems no more interesting or problematic than sequence argument unpacking working with dictionaries, "a, b = {'one': 1, 'two': 2}".

[abarnert]

It seems no more interesting or problematic than sequence argument unpacking working with dictionaries, "a, b = {'one': 1, 'two': 2}".

Dictionaries (including dicts, dict subclasses, and custom Mappings) are iterables. People use that fact every time they write for key in d. So it's not at all problematic that they work with iterable unpacking. Especially since here, custom Mappings work exactly the same way as dicts, dict subclasses, custom Sets, iterators, and every other kind of iterable.

Dictionaries are not sequences. People never write code expecting them to be. So it is problematic that they work with sequence reversing. Especially since here, custom Mappings do _not_ work the same way as dicts, dict subclasses, custom Sets, iterators, and other non-sequences, all of which raise a TypeError.

[curioswati]

But the work around suggested here as:

def __reversed__(self):
    return (self[k] for k in reversed(range(len(self))))

is also not a general solution, i.e. it is applicable for the following case:
m = MyDict({2:40, 0:10, 1:20})

but for any other mapping which does not have 0 as a key, it results in KeyError. So another solution, which would be more general could be:

def __reversed__(self):
    keys = [k for k in self.keys()]
    return (self[k] for k in reversed(keys))

[bitdancer]

No, the workaround was for duplicating the existing behavior if the fix (raising an error like a normal dict does) broken someone's code. The *only* possibility here is to have a __reversed__ that raises a TypeError.

What is it that makes reversed raise a typeerror on dict here? Not that we can change it at this point, but reversed blindly using len and __getitem__ for user classes but not on dict is rather inconsistent. I suppose the dict TypeError special case catches common mistakes? In which case adding a __reversed__ that raises a TypeError to Mapping seems to make sense for the same reason.

[abarnert]

@r. David Murray:

What is it that makes reversed raise a typeerror on dict here?

There are separate slots for tp_as_sequence and tp_as_mapping, so a C type can be (and generally is) one or the other, not both.

But for Python types, anything that has __getitem__ is both a sequence and a mapping at the C level. (It's one of the few minor inconsistencies between C and Python types left, like having separate slots for nb_add and sq_concat in C but only __add__ for both in Python.)

Not that we can change it at this point, but reversed blindly using len and __getitem__ for user classes but not on dict is rather inconsistent.

But it's consistent with iter blindly using __len__ and __getitem__ if __iter__ is not present on Python classes but not doing that on C classes. That's how "old-style sequences" work, and I don't think we want to get rid of those (and, even if we did, I'm pretty sure that would require at least a thread on -dev or -ideas...).

I suppose the dict TypeError special case catches common mistakes?

Yes. That's probably not why it was implemented (it's easier for a C type to _not_ fake being a broken sequence than to do so), but it has that positive effect.

In which case adding a __reversed__ that raises a TypeError to Mapping seems to make sense for the same reason.

Exactly.

I think Raymond's point is that, while it does make sense, it may still not be important enough to be worth even two lines of code. Hopefully we can get more than two opinions (his and mine) on that question; otherwise, at least as far as I'm concerned, he trumps me.

[abarnert]

@Swati Jaiswal:

But the work around suggested here ... is also not a general solution, i.e. ... for any other mapping which does not have 0 as a key, it results in KeyError.

You're missing the point. The workaround isn't intended to be a general solution to making mappings reversible. It's intended to produce the exact same behavior as the current design, for any code that somehow depends on that. So, any mapping that happens to be reversible by luck is reversible with the workaround; any mapping that successfully produces odd nonsense produces the same odd nonsense; any mapping that raises a KeyError(0) will raise the same KeyError(0).

In the incredibly vast majority of cases (probably 100%) you will not want that workaround; you will want the new behavior that raises a TypeError instead. I don't think the workaround needs to be mentioned in the documentation or anything; I just produced it to prove that, on the incredibly unlikely chance that the change is a problem for someone, the workaround to restore the old behavior is trivial.

Meanwhile, your general solution takes linear space, and linear up-front work, which makes it unacceptable for a general __reversed__ implementation. When you actually want, you can do it manually and explicitly in a one-liner, as already explained in the docs.

If you're still not getting this, pretend I never mentioned the workaround. It really doesn't matter.

[curioswati]

Okay, so should I go for a patch for it? And sorry if it sounds naive, but do we provide the work around or the user would implement if they purposely want it. If we provide it, then where should it be written?

[curioswati]

@andrew Barnert,
sorry, I didn't get your previous messages so please ignore the last message i sent. I got your point i.e. We just need to provide the TypeError in the Mapping. And the work around is never implemented.
Should I go for the patch with it?