digitalmars.D.bugs - [Issue 11037] New: AA's totally broken for struct keys with indirection
- d-bugmail puremagic.com (86/86) Sep 13 2013 http://d.puremagic.com/issues/show_bug.cgi?id=11037
- d-bugmail puremagic.com (6/6) Sep 18 2013 http://d.puremagic.com/issues/show_bug.cgi?id=11037
http://d.puremagic.com/issues/show_bug.cgi?id=11037 Summary: AA's totally broken for struct keys with indirection Product: D Version: D2 Platform: All OS/Version: All Status: NEW Severity: major Priority: P2 Component: druntime AssignedTo: nobody puremagic.com ReportedBy: hsteoh quickfur.ath.cx 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. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Sep 13 2013
http://d.puremagic.com/issues/show_bug.cgi?id=11037 Fix for (2): https://github.com/D-Programming-Language/druntime/pull/522 -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Sep 18 2013