AA key conversion woes

[H. S. Teoh]

I'm having some major roadblocks with the AA implementation w.r.t. how
to store/convert AA key types correctly. I've been working on this for a
while now but still cannot find a satisfactory solution; hopefully y'all
can help.

First, in order to take advantage of the compiler's auto-conversion
magic (such as using literal [1,2,3] for ubyte[] keys, etc.) and to
avoid template bloat, we must take const(Key) as argument for all key
lookup methods. So Key must at least be stored as const. But since we
have to do this already, might as well do it right: Keys should be
stored as immutable.

The nice thing about this is that we can now *guarantee* that AA's won't
malfunction due to the user changing stored key values via an external
mutable reference.

The bad thing about this is how to deal with the various key types that
the user might try to pass in:

1) For value types like int, there's no problem: immutable(int)
interconverts freely with int via assignment, so we can store int keys
however we like, and we can always hand back unqualified ints to the
user. So if the user declares int[int], .keys will give int[], and if
the user declares const(int)[int], then .keys will give back
const(int)[]. No problem.

2) Where things get hairy is when non-trivial keys are stored. Take
arrays for example. If the user declares int[int[]], then we need an
.idup so that we can store the key as immutable(int)[] (or should that
be immutable(int[])?). But now if the user passes in an int[] key, we
will need to .idup it in order to store it. This is acceptable, but what
should .keys return?  If I were the user, I'd expect int[][], but since
we can't implicitly convert immutable(int)[] to int[], we need a .dup
for each key.  Which introduces unnecessary overhead, since for the most
part the user doesn't need to change the keys anyway. But handing back
immutable(int)[][] from .keys will break a lot of existing code.

3) With arrays, things are still not too bad because we have .dup and
.idup. But what about structs or classes? We do not have .idup if the
key type is specified as non-immutable, so how should the keys be
stored? (Besides, do we *want* to clone objects used as AA keys in the
first place?) And what type should .keys return?

4) What should be done if the key type is shared or inout? (I'm tempted
to say outright prohibit shared, but people may not like their code
breaking if they're actually using that in existing code.)

I'm tempted to propose that the language should be changed so that AA
keys are *always* immutable implicitly. That is, writing int[int] is
exactly the same as writing int[immutable(int)], and .keys will always
return immutable. This is the "correct" approach IMO, and existing code
should be fixed if this breaks them. This will simplify a lot of the
mess above (we can still support .idup for when the user wants to lookup
mutable keys, etc., but there will be no concessions for .keys to hand
back mutable keys -- .dup them yourself).

But I'm expecting some negative reactions to this hardline approach. :-)

But even then, I'm considering if .keys should return a mutable array if
the key is a value type (e.g., it's harmless for int[int].keys to return
int[] because the int's are a copy anyway, and this way user code won't
be unnecessarily straitjacketed to propagate immutable throughout).

I'd like to hear how people think this should work, so that the new AA
implementation will be more acceptable.


T

-- 
Never trust an operating system you don't have source for! -- Martin Schulze