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

The catch here is that int implicitly converts to double, *but* the underlying representation is different, so int.toHash() != double.toHash(). But currently the above code compiles, but computes the wrong hash value for the key, so that aa[1u] and aa[1.0f] are distinct entries, which is nonsensical.

So the question is, how to restrict input key types so that we only allow input keys that have the same representation as the AA key type?

A more advanced solution is to perform representation conversions (e.g., int -> double) first, and *then* compute the hash, and *then* use .idup or slicing if the input key needs to be duplicated (in the first example above, the char[] is not .idup'd until a new entry actually needs to be created).

However, I don't know how to check for such cases using function/template signature constraints, besides hard-coding all known conversions (which is ugly, fragile, and hard to maintain). IOW, if is(InputType : KeyType) is true, then how do I tell whether the implicit conversion involves a representation conversion, or merely a const conversion (e.g., immutable->const or unqualified->const)?


T

-- 
This is a tpyo.

Why do you not just do the conversion and then compute the hash, even if the representation is the same?

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