Associative Arrays Class Key Type

[fieldvoid]

The spec says that for class types to be used as keys in associative arrays, two member functions must be overridden - opEquals and opHash. However the compiler accepts code where the class has not overridden these two member functions, providing some default implementation.
I think that the spec might be outdated - if so it needs to be updated to specify that classes may provide custom implementations of opHash and opEquals, and to clarify whether having one member function overriden necessitates also overriding the other.

Please see example below:

import std.stdio;

class Foo {
}

class Bar : Foo {
}

void main () {
    bool[Foo] set;
    
    Foo a = new Foo;
    Foo b = new Bar;
    
    set[a] = true;
    set[b] = true;
    
    if (a in set) {
        "%s is in set".writefln(a);
    }
    
    if (b in set) {
        "%s is in set".writefln(b);
    }
    
    set.remove(b);
    
    if (b !in set) {
        "%s is not in set.".writefln(b);
    }
}

[jmdavis]

The spec should be made clearer, but the reality of the matter is that if you don't override both opEquals and toHash, AAs won't work correctly with a class type as the key. This is because the default implementations of those functions are borderline useless. The default opEquals uses is, so it's comparing the address of the two objects, not the objects themselves. Similarly, toHash hashes the address. There isn't really anything else that a default implementation could do (except maybe throw an exception, complaining that a proper implementation wasn't provided in whatever the actual type of the object is), but it's almost never what anyone actually wants.

So, while technically, you don't have to override both opEquals and toHash to use a class type as a key in an AA, realistically, you really do need to override both.

And just as a general rule, any type (not just classes) which implements or overrides toHash needs to provide opEquals as well, or they won't be consistent, and AAs won't work correctly with that type as a key. And since Object provides toHash, that also means that any class which overrides opEquals needs to also override toHash, or it will not work correctly if it's ever used as an AA key.

Really, Object should never have had opEquals or toHash on it, but that's a longstanding issue that's very hard to fix without breaking code.

[fieldvoid]

If we are trying to keep track of class instances in a recursive type such that class Obj { bool[Obj] branches; }, or with a struct example - struct Obj { bool[Obj*] branches; }, wouldn't the is behavior of opEquals be desirable? I think that checking by address is an expectation (at least it was for me) and seeing the spec claim otherwise was quite a surprise.

Consider a GUI system with widgets that keep track of subwidgets. I would want to keep track of the addresses of the instances. I think that comparing the objects themselves (a sort of deep comparison) isn't all that common of a use-case.

[jmdavis]

If we are trying to keep track of class instances in a recursive type such that class Obj { bool[Obj] branches; }, or with a struct example - struct Obj { bool[Obj*] branches; }, wouldn't the is behavior of opEquals be desirable? I think that checking by address is an expectation (at least it was for me) and seeing the spec claim otherwise was quite a surprise.

There probably are cases where it would be desirable, but I don't think that I've ever run into one personally, and I don't think that I've seen anyone looking for that. I would fully expect that most people would be surprised if they compared two objects with the same value and then got false because they weren't the exact same object, since they typically would have expected opEquals to have been overridden in whatever way was appropriate for that derived type - but depending on which industry you're in and what your typical use cases are, your experiences and expectations can obviously vary.

Either way, Object.opEquals uses is, and that's something that anyone using it should be aware of. With regards to AAs, I would guess that the most common misunderstanding related to that would simply be that it's very easy to override opEquals and forget toHash, which will result in bugs. If you override opEquals, you need to override both - at least if you're going to use toHash at all.

[fieldvoid]

I wouldn't say that overriding opEquals but leaving toHash is inherently buggy, no more than overloading an operator like + but having it do something that is not math related is buggy - it is just unexpected. [Edit]: I see that the spec does say that it is undefined behavior for overriding one member function but not the other (I think that's fine).

Thank you for clarifying all this. I'll open a PR to update the spec.

[jmdavis]

I wouldn't say that overriding opEquals but leaving toHash is inherently buggy, no more than overloading an operator like + but having it do something that is not math related is buggy - it is just unexpected. [Edit]: I see that the spec does say that it is undefined behavior for overriding one member function but not the other (I think that's fine).

It is most definitely a bug if you don't provide a toHash which matches the behavior of that type's opEquals. This is because the AAs (and really much of anything doing hashing) rely on two equal values having the same hash, and if you don't provide a toHash that matches opEquals, that's not going to happen.