12

According to PEP 468:

Starting in version 3.6 Python will preserve the order of keyword arguments as passed to a function. To accomplish this the collected kwargs will now be an ordered mapping. Note that this does not necessarily mean OrderedDict.

In that case, why does this ordered mapping fail to respect equality comparison with Python's canonical ordered mapping type, the collections.OrderedDict:

>>> from collections import OrderedDict
>>> data = OrderedDict(zip('xy', 'xy'))
>>> def foo(**kwargs):
...     return kwargs == data
... 
>>> foo(x='x', y='y')  # expected result: True
True
>>> foo(y='y', x='x')  # expected result: False
True

Although iteration order is now preserved, kwargs seems to be behaving just like a normal dict for the comparisons. Python has a C implemented ordered dict since 3.5, so it could conceivably have been used directly (or, if performance was still a concern, a faster implementation using a thin subclass of the 3.6 compact dict).

Why doesn't the ordered mapping received by a function respect ordering in equality comparisons?

user2357112
  • 260,549
  • 28
  • 431
  • 505
wim
  • 338,267
  • 99
  • 616
  • 750

4 Answers4

14

Regardless of what an “ordered mapping” means, as long as it’s not necessarily OrderedDict, OrderedDict’s == won’t take into account its order. Docs:

Equality tests between OrderedDict objects are order-sensitive and are implemented as list(od1.items())==list(od2.items()). Equality tests between OrderedDict objects and other Mapping objects are order-insensitive like regular dictionaries. This allows OrderedDict objects to be substituted anywhere a regular dictionary is used.

Ry-
  • 218,210
  • 55
  • 464
  • 476
  • 1
    3.6 dict order is implementation detail, but the `kwargs` object received by a function being an ordered mapping is not an implementation detail. So it should have correct equality comparisons with other ordered mappings, shouldn't it? – wim Mar 07 '18 at 18:54
  • @wim: Added some parentheses. – Ry- Mar 07 '18 at 18:55
  • @wim Regarding you equality operator, you cannot do what you want without violating the "transitive" requirement of the equals operator. That is, if `dict0 == ordered_dict0` and `dict0 == ordered_dict1`, then it must necessarily be that `ordered_dict0 == ordered_dict1`. With what you are suggesting this might not always be the case. – Dunes Mar 07 '18 at 19:01
  • I think you're missing the point of the question. The claim in the PEP is that "kwargs is an ordered mapping" but the implementation seems to be something weaker, something more like "the kwargs will preserve iteration order". – wim Mar 07 '18 at 19:01
  • 2
    @Dunes Transitivity is already broken (`OrderedDict([(1,2), (3,4)]) == {1:2, 3:4} == OrderedDict([(3,4), (1,2)])`), so who cares? – wim Mar 07 '18 at 19:04
  • @Ryan I still don't think it's really answering the question, this is just restating what the behaviour **is**. The CPython devs were surely aware there was a design choice to make here, and took this decision intentionally. I'm looking for the reason(s). – wim Mar 07 '18 at 19:24
  • 6
    @wim: It's showing that the behaviour is documented. I don't think you have a strong case for expecting the comparison to take order into account. – Ry- Mar 07 '18 at 20:03
  • @Ryan It is **not even showing that the behaviour is documented**, strictly speaking. I put `return kwargs == data`, not `return data == kwargs`, which means that the "ordered mapping" has the first responsibility of handling the comparison, so how `OrderedDict.__eq__` is implemented is immaterial here. It happens that `OrderedDict` is a subclass of `dict`, and `kwargs` *is a* `dict`, so the implementation of `OrderedDict.__eq__` is taken into account, but there is no reason it had to be done this way. – wim Mar 10 '18 at 17:13
10

"Ordered mapping" only means the mapping has to preserve order. It doesn't mean that order has to be part of the mapping's == relation.

The purpose of PEP 468 is just to preserve the ordering information. Having order be part of == would produce backward incompatibility without any real benefit to any of the use cases that motivated PEP 468. Using OrderedDict would also be more expensive (since OrderedDict still maintains its own separate linked list to track order, and it can't abandon that linked list without sacrificing big-O efficiency in popitem and move_to_end).

user2357112
  • 260,549
  • 28
  • 431
  • 505
  • 1. I'm not convinced on the idea that changing `==` here would have to be more expensive (though using `OrderedDict` itself would be more expensive, yes). For example, the compact dict impl improved performance along with preserved order. 2. What backwards incompatibility would have been produced, that was not a bug in the first place? Changing this would not effect comparisons against other dicts, only against other ordered mappings. – wim Mar 07 '18 at 19:19
  • 4
    @wim: 1) Changing `==` for *all* dicts would break an absurd amount of code for no practical reason, and making a new dict subclass just to have order be part of `==` would add complexity for no real benefit, as well as introducing interoperability issues with OrderedDict. 2) Any code relying on the old definition of `==` would break. Relying on the definition of `==` isn't a bug. Also, C code that uses PyDict_Whatever to access keyword argument dicts would need to be reexamined if keyword arguments come in a dict subclass or other mapping type. – user2357112 Mar 07 '18 at 19:27
8

The answer to your first 'why' is because this feature is implemented by using a plain dict in CPython. As @Ryan's answer points out, this means that comparisons won't be order-sensitive.

The second 'why' here is why this doesn't use an OrderedDict.

Using an OrderedDict was the initial plan as stated in the first draft of PEP 486. The idea, as stated in this reply, was to collect some perf data to show the effect of plugging in the OrderedDict since this was a point of contention when the idea was floated around before. The author of the PEP even alluded to the order preserving dict being another option in the final reply on that thread.

After that, the conversation on the topic seems to have died down until Python 3.6 came along. When the new dict came, it had the nice side-effect of just implementing PEP 486 out of the box (as this Python-dev thread states). The specific message in that thread also states how the author wanted the term OrderedDict to be changed to Ordered Mapping. (This is also when a new commit on PEP 468, after the initial one, was made)

As far as I can tell, this rewording was done in order to allow other implementations to provide this feature as they see fit. CPython and PyPy already had a dict that easily implemented PEP 468, other implementations might opt for an OrderedDict, others could go for another form of an ordered mapping.

That does open the door for a problem, though. It does mean that, theoretically, in an implementation of Python 3.6 with an OrderedDict as the structure implementing this feature, the comparison would be order-sensitive while in others (CPython) it wouldn't. (In Python 3.7, all dicts are required to be insertion-ordered so this point is probably moot since all implementations would use it for **kwargs)

Though it does seem like an issue, it really isn't. As @user2357112 pointed out, there's no guarantee on ==. PEP 468 only guarantees order. As far as I can tell, == is basically implementation defined.

In short, it compares equal in CPython because kwargs in CPython is a dict and it's a dict because after 3.6 the whole thing just worked.

Dimitris Fasarakis Hilliard
  • 150,925
  • 31
  • 268
  • 253
  • Great finds Jim, this seems to be the correct answer (particularly [this](https://mail.python.org/pipermail/python-dev/2016-September/146327.html) part). The **kwargs iteration order was a "happy accident" of other developments in the dict type. So, they dusted off the PEP 486 and accepted it, but that was more or less a side effect of compact dict impl. I do think they could have re-worded the PEP more carefully, because any "ordered mapping" worth its salt should likely have the ordering considered by eq comparisons. – wim Mar 07 '18 at 22:14
  • i.e., the 3.6 dict is not an ordered mapping, it's just a mapping that happens to preserve insertion order. – wim Mar 07 '18 at 22:18
  • 1
    @wim The PEP is probably not as fleshed out as you would expect since it didn't go through the usual Python-dev iterations other PEPs go through. Also, yes, it isn't ordered in the sense that `OrderedDict` is defined to be. Using "ordered" is misleading but "marketing" I guess. I'll guess I need to clarify that in a couple of my answers. – Dimitris Fasarakis Hilliard Mar 07 '18 at 22:36
1

Just to add, if you do want to make this check (without relying on an implementation detail (which even then, won't be in python 3.7)), just do

from collections import OrderedDict
>>> data = OrderedDict(zip('xy', 'xy'))
>>> def foo(**kwargs):
...     return OrderedDict(kwargs) == data

since this is guaranteed to be True.

FHTMitchell
  • 11,793
  • 2
  • 35
  • 47
  • I'm aware of the workaround, but why is that necessary in the first place since *kwargs will now be an ordered mapping*? – wim Mar 07 '18 at 18:58
  • This returns `False` for both `foo(y='y', x='x')` and `foo(x='x', y='y')` – smac89 Mar 07 '18 at 19:00
  • @smac89 does it? `foo(x='x', y='y')` gives me `True`. Are you not running python 3.6, or is this something whereby `OrderedDict` doesn't add `dict` elements in order? – FHTMitchell Mar 07 '18 at 19:03
  • @FHTMitchell, I think I was running 3.5 when I tested that. I will install 3.6 and check – smac89 Mar 07 '18 at 19:06
  • @wim Because the `dict` equality operator does not care about order. Just because order is preserved, there is no guarantee that equality operators take this into account. – FHTMitchell Mar 07 '18 at 19:06
  • @FHTMitchell But there is no guarantee that `kwargs` has to be a `dict`, and so use the dict equality methods, either. It could easily be a thin subclass of dict that overrides `__eq__`. – wim Mar 07 '18 at 19:09
  • 3
    I'm not sure of the usefulness of this answer in a "Why" question. Seems more suitable as a comment, really. – Dimitris Fasarakis Hilliard Mar 07 '18 at 19:12
  • That would be a terrible idea that breaks backward compatibility. Again "guarantees order preservation" makes no comment as to whether an equality test takes it into account. – FHTMitchell Mar 07 '18 at 19:15
  • @JimFasarakisHilliard because it shows that it is doable quickly and simply, so part of the answer "why" is because it wasn't considered necessary since the solution to this particular problem is easy. – FHTMitchell Mar 07 '18 at 19:16