Bug 11037 – [AA] AA's totally broken for struct keys with indirection
Status
RESOLVED
Resolution
FIXED
Severity
major
Priority
P2
Component
druntime
Product
D
Version
D2
Platform
All
OS
All
Creation time
2013-09-13T16:32:00Z
Last change time
2014-07-07T02:52:51Z
Assigned to
nobody
Creator
hsteoh
Comments
Comment #0 by hsteoh — 2013-09-13T16:32:16Z
Code:
----
struct Key {
string x;
string y;
}
void main() {
bool[Key] aa;
aa[Key("a", "b")] = true;
assert(aa[Key("a", "b")] == true); // OK
assert(aa[Key("a".idup, "b".idup)] == true); // NG
}
----
There is a LOT more wrong with this code that appears at first glance.
The most obvious thing wrong is that Key doesn't define toHash, and the default toHash for structs just hashes the binary representation of the struct, so it's hashing on Key.x and Key.y's .ptr and .length values, rather than the contents of the strings. This problem can be shown by printing out the value of typeid(string).getHash(&key). However, it is masked by the fact that dmd folds identical string literals together, so in simple test cases where you simply write out "a" and "b", this problem doesn't surface. But when you use .idup to force the .ptr values to differ, as above, then the problem becomes manifest.
But even after defining opHash, it still doesn't work:
----
struct Key {
string x;
string y;
size_t toHash() const @safe nothrow
{
// Simple non-associative combination of the respective string hashes
return typeid(string).getHash(&sym)*2 +
typeid(string).getHash(&dep);
}
}
void main() {
bool[Key] aa;
aa[Key("a", "b")] = true;
assert(aa[Key("a", "b")] == true); // OK
assert(aa[Key("a".idup, "b".idup)] == true); // still NG
}
----
If you print out the value of typeid(string).getHash(&key) for the idup'd and non-idup'd Keys, you'll find that the hashes are now equal. But the AA still doesn't work -- what gives?
If you insert both Keys into the AA, then manually dump out the binary contents of the AA (e.g. with a debugger, or with a suitable pointer cast to appropriately-defined structs that mirror the definitions in aaA.d), it is seen that the keys hash to the same bucket, but two Slots are created for them. Looking over aaA.d, the only way this can happen is if the two structs don't compare equal.
But, and here is where it gets really pathological, defining opEquals for Key *still* doesn't work! Why? Because aaA.d currently uses TypeInfo.compare()==0 to determine if two keys are equal... but TypeInfo.compare is only defined if the struct declares opCmp. Defining opEquals doesn't help because that gets mapped to TypeInfo.equals, which in druntime has NO correlation with TypeInfo.compare even though TDPL says they must match.
So, the only way to get the above code to work is to *also* define Key.opCmp. Which is stupid if the struct has no natural ordering.
tl;dr, what this bug asks for is:
1) Make the default implementation of toHash for a struct to compute its hash based on the hash values of its respective fields (by calling *their* toHash, if defined);
2) Fix aaA.d to use TypeInfo.equals() instead of TypeInfo.compare(). Since AA's are by definition unordered, it makes no sense to use compare() for checking key equality.
3) (maybe?) Fix the way the compiler generates TypeInfo so that if one of opEquals or opCmp isn't defined, Typeinfo.compare or Typeinfo.equals (respectively) will have a default implementation *compatible with opEquals/opCmp*, respectively. Once Typeinfo.compare and Typeinfo.equals go out of sync, then everything just breaks in horrible ways.