Implicit conversions for AA keys

[Andrei Alexandrescu]

On 3/23/12 12:54 PM, H. S. Teoh wrote:
> Currently my AA implementation supports automatic key conversion (as
> suggested by Andrei), for example:
>
> 	AA!(string,int) aa;
> 	char[] key = "abc".dup;
> 	aa[key] = 1;		// automatically converts char[] to
> 				// string via .idup
>
> The way this is implemented is by allowing any input key type that can
> implicitly convert to the actual key type, or types that can be
> converted via .idup or slicing (to support using dynamic arrays for
> static array keys). While this is all nice and general, it is also *too*
> general:
>
> 	AA!(double,int) aa;
> 	int x = 1;
> 	aa[x] = 1;		//<---PROBLEM
[snip]

Let's see what requirements need to be satisfied by []. Say k is a value 
of the key type and x is a value being looked up.

First, we need to be able to evaluate k == x. So the types must be 
comparable.

Second, we need if x == k, then hash(k) == hash(x). This is tricky in 
general, but let's say we can approximate to the compile-time 
requirement that the hash function resolves to the same entity for both 
typeof(x) and typeof(k). This would rule out e.g. int and double but 
would leave char[] and string.

To include int and double correctly, we'd amend the second rule as 
follows. If typeof(x) converts implicitly to typeof(k), then use 
hash(cast(typeof(k)) x) instead of hash(x). This makes it possible to 
look up for an int in a hash of doubles, but not vice versa, which is great.

These two are sufficient for lookup. For store, we also need the third 
rule, which is to!(typeof(k))(x) must compile and run.


Andrei