Equality of OrderedDict

[lucaferranti]

I am a little confused by the following, is it intentional that == does not take into account the order of keys for OrderedDict?

julia> a1 = OrderedDict(:A => 1, :B => 2, :C => 3)
OrderedDict{Symbol, Int64} with 3 entries:
  :A => 1
  :B => 2
  :C => 3

julia> a2 = OrderedDict(:B => 2, :A => 1, :C => 3)
OrderedDict{Symbol, Int64} with 3 entries:
  :B => 2
  :A => 1
  :C => 3

julia> a1 == a2
true

this is mainly motivated by testing purposes, as I think in tests one wants to check that also the keys order is correct. Well, arguably one can always do

@test all(kv1 == kv2 for (kv1, kv2) in zip(a1, a2))

so maybe it's not a biggie.

[oxinabox]

This is because it is falling back to the generic == on AbstractDicts, which are unordered.

julia> od = OrderedDict(1=>2)
OrderedDict{Int64, Int64} with 1 entry:
  1 => 2

julia> @which ==(od, od)
==(l::AbstractDict, r::AbstractDict) in Base at abstractdict.jl:468

Whether or not this is sensible is not clear to me.

For what it is worth our behavour disagrees with python.

>>> from collections import OrderedDict
>>>  d = OrderedDict.fromkeys('abcde')
>>>  d2 = OrderedDict.fromkeys('edcba')
>>> d==d2
False

>>> d==d
True

Python treats ordered dicts as equal only if they have the same contents in the same order)

[einarpersson]

I definitely expected that == would differentiate between two OrderedDicts if they differ in order. Isn´t that the whole point, i.e. saying that "no these are not same despite having the same elements, because they are in different order".

[jariji]

For any type T, x::T and y::T should not have x == y unless x and y agree on all aspects of their public API. Since order is part of the public API of Ordered containers, they should not be ==(::T, ::T) unless they agree on order.

[fingolfin]

@jariji that is a very vague characterization, it is not clear to me what that really would mean.

If I understand you correctly (and I may not) then Julia is violating this principle already in many ways. E.g.:

julia> 1 == true
true

julia> !true
false

julia> !1
ERROR: MethodError: no method matching !(::Int64)
The function `!` exists, but no method is defined for this combination of argument types.

Arguably ! is part of the public API of booleans. And it not working on other integers also is public behavior.

OK perhaps you'll argue this doesn't count because one is an error. So how about this:

julia> x = Int8(127); y = UInt8(127);

julia> x == y
true

julia> x + x == y + y
false

julia> x + x == x + y
false

[fingolfin]

Don't get me wrong, this is not meant to argue that the current behavior is right / correct / preferable / whatever, just that I don't buy this particular argument.

Another aspect to consider is that changing the behavior of == would be a breaking change, i.e. it would have to go into a major release like 2.0.0.

Unlike some other breaking changes we may want to apply, like fixing some type piracy issues (see issue #25 ) this one is more tricky as it has the potential to introduce one of the worst kinds of bugs: code that previously worked correctly in downstream packages could be suddenly start producing wrong results. That is really undesirable.

Thus, personally I think the ship has sailed on this one. If this was day 1, I'd be fine with taking the order into account, but there are now > 350 direct dependencies on this package in the ecosystem, and a couple thousand indirect one. Thus as outlined I believe changing this risks breaking too much code in a really bad way. The gain seems minimal.

So I would say "By now, this is indeed as intended", and we should document it explicitly as such.

To still help users, perhaps we could introduce a "compare while taking order into account" method. Say is_strictly_equal or so

Also perhaps it would help to add a new StrictOrderedDict type which behaves like OrderedDict except for equality (and perhaps a few additional points). To implement this, one could add another type parameter strict to OrderedDict, so the implementation would be the same. Roughly like this:

mutable struct GenOrderedDict{K,V,strict} <: AbstractDict{K,V}
    slots::Vector{Int32}
    keys::Vector{K}
    vals::Vector{V}
    ndel::Int
    maxprobe::Int
    dirty::Bool
end

const OrderedDict{K,V} = GenOrderedDict{K,V,false}
const StrictOrderedDict{K,V} = GenOrderedDict{K,V,true}

Of course then one still would have to duplicate a bunch of constructors and adjust other places to use GenOrderedDict instead of OrderedDict

Any code which currently only expects an OrderedDict would not accept a StrictOrderedDict out of box -- but that's a feature, not a bug, as the idea precisely was to not sneak in the changed behavior but rather require code to explicitly support it...

[jariji]

@fingolfin I say "For any type T, x::T and y::T ...", assuming x and y have the same type. But in the example of x::Bool; y::Int; x==y, x and y have different types. I was not making an argument about what == means across different types, which is more complicated. I'm only addressing the simpler case of a single type.

[fingolfin]

but there is also the matter of transitivity: x == y and y == z should perhaps imply x == z (granted I am sure Julia also violates that already).

In any case it does not change the fact that surely there is code out there relying on the current behavior, so changing it would be a (painful) breaking change

[willow-ahrens]

Since it seems we've agreed that ordered collections are equal regardless of order, then we should also make their hashes equal under the same circumstances right? #148

[oxinabox]

I am not sure that we have agreed that. Indeed I think most of the above say that we should be taking into account order.
But indeed if we are not then hash should also be ignorant of order

[timholy]

When I use OrderedDict, typically the main alternative I might consider is Vector{Pair{A,B}}. Since the latter requires equality of ordering, I think == for OrderedDict needs to require that the ordering be the same.

[willow-ahrens]

My mistake, I see there was only consensus that we need a major version bump to change the == behavior, not that we don't want to change it eventually.

Currently, this implementation does not conform to the spec set out in Base (isequal implies hash equality). This was a surprising, silent error where two things which were == did not behave correctly as dictionary keys. Can we at least make the hash behavior consistent with == for now, and make a plan to change both == and the hash behavior later in the major version bump when it comes along?

Alternatively, can we introduce a new type, perhaps called "StrictlyOrderedDict", which is a wrapper type with order-matters behavior to support both cases?

In my use cases, I've always used Ordered collections to obtain reproducible output in my CI. I wrapped the other behavior, adding the "StableSet" wrapper type which treats different orders as equal but returns a stable iteration order. I think it's worth it to support both use cases. I just really think the inconsistency is a rather surprising bug which should be fixed.

[oxinabox]

Definately needs to be fixed.
I think we should just change this.
We are due a breaking version very soon.
If someone wanted to make a PR now to change equality (and hash if required) to consider order I would merge it today into the current branch for the next release)