AA key conversion woes

[SomeDude]

On Thursday, 19 April 2012 at 19:31:36 UTC, H. S. Teoh wrote:
> On Wed, Apr 18, 2012 at 04:02:05PM +0200, Somedude wrote:
> [...]
>> I'm not sure I understood the whole issue and its 
>> implications, but
>> would this work: a map template that takes any parameter T as 
>> key AND
>> a lambda/anonymous/delegate function as a hash function ? 
>> Unlike Java,
>> passing the hash function avoids having to define a hashCode() 
>> and
>> equals() method for each class.
>
> In my mind, such a thing would belong to std.container. The 
> built-in
> AA's should be as straightforward as possible, that is, given 
> any
> reasonable key type, it should do the "right thing".
>
> Also, it's not hard to use UFCS to make a default toHash() 
> function for
> classes that uses some default hashing algorithm on any class 
> (same
> thing applies to structs) so that you don't have to define them 
> per
> class unless you wish to override the default hash function.
>
>
>> We don't impose any restraint on T, .keys would simply return 
>> T[], e.g
>> if T is immutable(int), .keys would be immutable(int)[].
>> I don't see the necessity for .keys itself to be an immutable 
>> array. I
>> even think it would be counter productive.
>
> Believe me, I would rather not have immutable keys if I could 
> help it,
> because it makes things so much simpler. However:
>
> (1) It leads to subtle breakages due to unintended aliasing:
>
> 	int[int[]] aa;
> 	int[] key1 = [1,2,3];
> 	aa[key1] = 123;
> 	key1[0] = 2;	// uh oh!
> 	assert(aa[[1,2,3]] == 123);	// assertion fails, key has
> 					// changed without AA's knowledge
>

Yeah, I thought about that, but then it's the programmer's 
responsibility to not shoot himself in the foot, and if he wants 
to be safe, he can still declare his keys immutable from the 
start. My concern is imposing a useless copy upon the programmer 
who has mutable keys for the sake of using the AA. There should 
be zero overhead. If for some reason he is forced to do that, he 
will end up writing his own implementation.

> (2) It tickles some compiler bugs/language ambiguities that 
> causes
> things like this to not work as expected:
>
> 	int[char[]] aa;
> 	aa["abc"] = 123;	// compile error: cannot convert string to 
> char[]
> 	const(char)[] key1 = "abc";	// works
> 	aa[key1] = 123;		// compile error: cannot convert 
> const(char)[] to char[]
>

OK, aa["abc".dup] = 123 works, though. I don't know if there is a 
better way to do this. Anyway, I agree it's super ugly code, but 
how many times does the program do this copy ? Once at the AA 
initialization (because you are not going to insert millions of 
string litterals by hand in your code). How many times does it 
need to copy the other keys ? Zero. OTOH, if you force the keys 
to be immutable, your string litteral will be nicer looking, but 
you may force a million copies of char[] to make them immutable 
keys (most often, the keys will be determined by the incoming 
data, not your string litterals). Performance and memory wise, 
it's very bad, and when the programmer sees there is no possible 
workaround, he won't be happy.

> Having immutable keys (or at least const keys) allows the AA
> implementation to specify const(keytype) in opIndex's 
> parameters, so
> that you can pass in char[], const(char)[], or string, and it 
> will work
> as expected.

Yeah, but that's a "comfort" for initialization, when you have to 
deal with the million real data, you'll force a duplication, and 
that's bad. Worse, if after that, the programmer needs to get 
.keys, he will have to perform another cast on all the elements 
of the array to remove the immutable afterwards because he wants 
to use the keys with the rest of his code which deals with 
mutable data.

> As for .keys, I agree that it should not be an immutable array, 
> it just
> needs to be tail-immutable (its elements are immutable, but the 
> array
> can be changed).
>
>
> T