On Wed, Apr 18, 2012 at 12:37:21AM -0400, Jerry wrote: > Sean Kelly <[email protected]> writes: [...] > > I'm inclined to say that if a reference type is used as a key to an > > AA, the user either has to promise not to change (assumeUnique) it > > or explicitly .idup it himself on insertion. > > +1. If AA's insist on immutable object keys, I worry that that will > force more folks to roll their own hashtables when working with large > tables where the cost of duping all those keys actually matters. > > Also, I have found it useful on a number of occasions to key a hashtable > with an object where the hash function is only computed on part of the > object and the rest is mutable. [...]
Thanks for pointing out this case. It's definitely a valid (and arguably important) case, so the built-in AA implementation shouldn't insist on immutable keys. (Though I should add that you'll need to implement a compatible opEquals with your custom hash function for this to work correctly, since the AA lookup code *does* do key comparisons, not just hash value comparisons.) So really, what AA's really want with its keys is that their *hash value* and opEquals value (in the abstract sense) be immutable. Whether the key is actually immutable is, in some sense, unimportant if the hash value remains constant, and opEquals still compares equally with its previous state. However, going to the other extreme (completely trust the user to make .toHash and .opEquals consistent and "immutable", and allow keys with any kind of qualifiers) also causes other kinds of problems, most notably with implicit conversions for key literals and AA method const-correctness. So what about this instead: - Any type that the user can define, that allows custom toHash and opEquals methods, are allowed to have any qualifiers (AFAIK, this is basically any struct and class?); - Built-in value types are allowed any qualifiers (in this case it doesn't matter because unqualified and immutable are interconvertible via assignment); - Built-in reference types (pointers, refs, arrays) must be either tail-immutable, or the tail must be a struct or class (i.e., the user is allowed to use arrays of unqualified objects with custom toHash and opEquals as AA keys). This should allow the "nice" properties we can get from having the type system enforce key immutability, for simple key types, and still allow users to do complex stuff (define their own toHash/opEquals that ignore parts of the object) when they need to. If it were possible, I'd prefer to have the language enforce toHash and opEquals immutability, but I don't think that is possible (since it can potentially involve solving the halting problem). So this is the best compromise I can think of right now. What do people think of this new idea? (Or should I just let users use assumeUnique and leave it at that?) T -- Questions are the beginning of intelligence, but the fear of God is the beginning of wisdom.
