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


--- Comment #0 from hsteoh@quickfur.ath.cx 2013-09-13 16:32:16 PDT ---
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: -------

http://d.puremagic.com/issues/show_bug.cgi?id=11037



--- Comment #1 from hsteoh@quickfur.ath.cx 2013-09-18 09:14:09 PDT ---
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: -------