[Issue 612] New: Associative arrays ignore opEquals, contrary to the spec

November 27, 2006
Posted by d-bugmail
Permalink
d-bugmail
Permalink
http://d.puremagic.com/issues/show_bug.cgi?id=612

           Summary: Associative arrays ignore opEquals, contrary to the spec
           Product: D
           Version: 0.175
          Platform: PC
               URL: http://www.digitalmars.com/d/arrays.html
        OS/Version: Windows
            Status: NEW
          Keywords: wrong-code, spec
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: bugzilla@digitalmars.com
        ReportedBy: smjg@iname.com


"Classes can be used as the KeyType. For this to work, the class definition must override the following member functions of class Object:

    * hash_t toHash()
    * int opEquals(Object)
    * int opCmp(Object)"

"Structs or unions can be used as the KeyType. For this to work, the struct or union definition must define the following member functions:

    * hash_t toHash()
    * int opEquals(S) or int opEquals(S*)
    * int opCmp(S) or int opCmp(S*)"

It turns out that the current implementation of AAs is just ignoring opEquals. Take this code:

----------
import std.stdio;
import std.ctype;

struct IChar {
    char data;

    bit opEquals(IChar i) {
        debug writefln("Entered IChar.opEquals(IChar)");
        return data == i.data;
    }

    int opCmp(IChar i) {
        debug writefln("Entered IChar.opCmp(IChar)");
        return toupper(data) - toupper(i.data);
    }

    hash_t toHash() {
        debug writefln("Entered IChar.toHash()");
        return toupper(data);
    }
}

void main() {
    int[IChar] aa;
    IChar c1, c2;

    c1.data = 'c';
    c2.data = 'C';

    aa[c1] = 4;
    aa[c2] = 7;
    aa.rehash;
    writefln("aa[c1]: %d", aa[c1]);
    writefln("aa[c2]: %d", aa[c2]);
}
----------
7
7
----------

The output immediately shows that c1 and c2 are treated as being the same key. Compiling with -debug and running will further confirm that IChar.opEquals is never called.  The same occurs if a class is used instead of a struct.

Two possible solutions:

(a) Fix the implementation of AAs so that it uses opEquals to check that the key it's found for which opCmp returns zero does indeed match the key.

(b) Remove the existing mentions of opEquals from these sections, and explicitly state: For efficiency of lookups, opEquals is not used to compare keys.  Therefore, if a.opCmp(b) == 0, then a and b are the same key even if a != b.  Care must be taken to ensure that if a.opCmp(b) == 0 then a.toHash == b.toHash, otherwise undefined behaviour will occur.


--
Forums
