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

@gvanrossum

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']

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)))).

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

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

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.

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.

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}".

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.

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))

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.

@r

@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.

@Swati

@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.

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?

@andrew

@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?

This sounds good. Also, reversed() could then be modified to produce a
better error.

Should iter also be modified to produce a better error if __iter__ is None?

Also, should this be documented? Maybe a sentence in the "Special method names" section of the "Data model" chapter, like this:

To indicate that some syntax is not supported, set the corresponding special method name to None. For example, if __iter__ is None, the class is not iterable, so iter() will not look for __getitem__.

All sounds fine.

The attached patch does the following:

collections.abc.Mapping.__reversed__ = None.
collections.abc.Iterable.__subclasshook__ checks for None the same way Hashable does:
- This tests for any falsey value, not just None. I'm not sure this is ideal, but it's consistent with Hashable, and it's unlikely to ever matter.
- The test will only block implicit subclassing. If a class, e.g., inherits from tuple (which is explicitly registered with Sequence, which inherits from Iterable), it's Iterable, even if it sets __iter__ = None. I think this is the right behavior, and it's consistent with Hashable.
iter and reversed add checks for None, which raise a TypeError with the appropriate message (instead of "'NoneType' is not callable").
datamodel.rst section "Special method names" includes a paragraph on setting special methods to None.
Tests for changes to reversed (in test_enumerate.py), iter (in test_iter.py), Iterable (in test_collections.py), and Mapping (in collections.py).

If this patch goes ahead, I think the ABC documentation should clarify which methods are checked for None and which aren’t. The datamodel.rst file will suggest None for any method, but ABC will only support it for Iterable and Hashable (I think).

Also, what is the point of the odd __getitem__() method in test_enumerate.py? Maybe you should use assertRaisesRegex() to check that the intended TypeError is actually raised.

If this patch goes ahead, I think the ABC documentation should clarify which methods are checked for None and which aren’t.

That seems fair.

Also, as you pointed out on bpo-25958, at least one other ABC has the same problem as Iterable: you can block the "in" operator by setting __contains__=None, but you'll still be a Container. So, do we want to go through all of the existing ABCs and make sure they all do this negative check, instead of just Iterable?

Also, what is the point of the odd __getitem__() method in test_enumerate.py? Maybe you should use assertRaisesRegex() to check that the intended TypeError is actually raised.

If an implementation doesn't raise a TypeError there, that's a failure. If it raises one with a different (possibly less helpful) message, I think that's just a quality-of-implementation issue, isn't it?

IMO allowing any special method to be set to None seems to make more trouble than it is worth. Are there practical problems to address, or are they all theoretical?

Ideally I think it would be better to require __reversed__() for reverse() to work, but such a change would break compatibility.

Regarding test_enumerate.py, your class looks like this:

class Blocked(object):
    def __getitem__(self): return 1
    def __len__(self): return 2
    __reversed__ = None

The signature of __getitem__() is wrong, and causes a TypeError during iteration, although your particular test does not go that far. When I see someone using assertRaises() with a common exception like TypeError, I instinctively suggest checking the message to avoid these kind of test case bugs.

I suggest either remove __getitem__() if it serves no purpose, or change it to something like this if you really want an unreversible sequence:

def __getitem__(self, index):
    return (1, 1)[index]

I think I tried to address all questions in bpo-25958.

IMO allowing any special method to be set to None seems to make more trouble than it is worth.

That's exactly why allowing _any_ special method to be None is a separate issue (bpo-25958). Most special methods don't have any corresponding problem to the one with __reversed__.

Ideally I think it would be better to require __reversed__() for reverse() to work, but such a change would break compatibility.

See the -ideas thread "Deprecating the old-style sequence protocol" (http://article.gmane.org/gmane.comp.python.ideas/37588).

Regarding test_enumerate.py, your class looks like this:

Please look at the two classes directly above it in the same function. The new Blocked exactly parallels the existing NoLen.

I suggest either remove __getitem__() if it serves no purpose

It very definitely serves a purpose. The whole point of the new test is that reversed will not fall back to using __getitem__ and __len__ if __reversed__ is None. So __getitem__ has to be there; otherwise, we already know (from the NoGetItem test) that it wouldn't get called anyway.

This is exactly the same as the NoLen test, which verifies that __reversed__ will not fall back to __getitem__ and __len__ if one is present but not both.

, or change it to something like this if you really want an unreversible sequence:

Sure, if I wanted a real class that could be used as a sequence but could not be reversed. But all I want here is a toy class for testing the specific method lookup behavior. Again, exactly like the existing classes in the same test.

Finally, from your previous comment:

I think the ABC documentation should clarify which methods are checked for None and which aren’t.

Looking at this a bit more: The ABC documentation doesn't even tell you that, e.g., Container and Hashable have subclass hooks that automatically make any class with __contains__ and __hash__ act like registered subclasses while, say, Sequence and Set don't. So, you're suggesting that we should explain where the hooks in some of those types differ, when we haven't even mentioned where the hooks exist at all. Maybe collections.abc _should_ have more detail in the docs, but I don't think that should be part of this bug. (Practically, I've always found the link to the source at the top sufficient--trying to work out exactly why tuple meets some ABC and some custom third-party sequence doesn't, which is a pretty rare case to begin with, is also pretty easy to deal with: you scan the source, quickly find that Sequence.register(tuple), read up on what it does, and realize that collections.abc.Sequence.register(joeschmoe.JoeSchmoeSequence) is what you want, and you're done.)

Agreed that improving the docs doesn't belong in this bug, but in general
if the docs aren't clear enough and only a visit to the source helps you
understand, something's wrong. Because the source may do things one way
today and be changed to do things differently tomorrow, all within the
(intended) promises of the API. But without docs we don't know what those
promises are.

I’m sorry I only read your patch and did not see the NoLen class above Blocked. (I blame the lack of Reitveld review link.) I still think __getitem__() should have a valid signature, but I acknowledge that it’s not really your fault. :)

My main concern about the documentation was that in your patch you say _all_ special methods are now allowed to be None, but in your code you only check __iter__(). This is adding new undocumented inconsistencies e.g. with Iterable vs Container. Maybe it would be better to only say that setting __iter__ to None is supported, instead of setting any special method.

My main concern about the documentation was that in your patch you say _all_ special methods are now allowed to be None, but in your code you only check __iter__(). This is adding new undocumented inconsistencies e.g. with Iterable vs Container.

No it isn't. We already have undocumented inconsistencies between, e.g., Hashable vs. Container; we're just moving Iterable from one set to the other. (Notice that there's an even larger inconsistency between, e.g., Hashable and Container vs. Sequence and Set. As Guido suggests, that probably _does_ need to be fixed, but not as part of this bug, or bpo-25958.)

And, as for the docs, it's already true that you can block fallback and inheritance of special methods by assigning them to None, but that isn't documented anywhere.

So, this bug doesn't add fix any of those inconsistencies, but it doesn't add any new ones, either. If you think we actually _need_ to fix them, see bpo-25958 as at least a starting point. (Notice that Guido seems to want that one fixed, so, assuming I can write a decent patch for it, this bug would then become a one-liner: "__reversed__ = None" inside Mapping.)

The proposed patch appears to have been implemented in 97c1adf, and there has been no discussion for five years. I think this can now be closed.

Navigation Menu

Repository navigation

collections.abc.Mapping should include a reversed that raises TypeError #70051

10 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

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

Description

Activity

abarnert commented on Dec 15, 2015

curioswati commented on Dec 15, 2015

Vgr255 commented on Dec 15, 2015

curioswati commented on Dec 15, 2015

abarnert commented on Dec 15, 2015

rhettinger commented on Dec 15, 2015

abarnert commented on Dec 15, 2015

curioswati commented on Dec 17, 2015

bitdancer commented on Dec 17, 2015

abarnert commented on Dec 17, 2015

abarnert commented on Dec 17, 2015

curioswati commented on Dec 18, 2015

curioswati commented on Dec 18, 2015

10 remaining items

abarnert commented on Dec 27, 2015

gvanrossum commented on Dec 27, 2015

abarnert commented on Dec 28, 2015

vadmium commented on Jan 1, 2016

abarnert commented on Jan 1, 2016

vadmium commented on Jan 1, 2016

gvanrossum commented on Jan 4, 2016

abarnert commented on Jan 4, 2016

gvanrossum commented on Jan 4, 2016

vadmium commented on Jan 4, 2016

abarnert commented on Jan 4, 2016

AlexWaygood commented on Dec 14, 2021

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions

collections.abc.Mapping should include a reversed that raises TypeError #70051