www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 11037] New: AA's totally broken for struct keys with indirection

reply d-bugmail puremagic.com writes:
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: -------
Sep 13 2013
parent d-bugmail puremagic.com writes:
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: -------
Sep 18 2013