AA key conversion woes

[Timon Gehr]

On 04/17/2012 08:41 PM, H. S. Teoh wrote:
> 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.
>

How? This is the current behavior:
int[int[]] aa;
static assert(is(typeof(aa.keys)==const(int)[][]));

A change from const(int)[][] to immutable(int)[][] shouldn't break a 
significant amount of 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?
>

They could implement .dup or .idup if they want those semantics. If the 
container cannot figure out how to get an immutable key from a mutable 
key, then indexing with mutable keys is disabled.

> 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.)
>

immutable is implicitly shared, but implicit .idup should be disabled. 
For inout there would need to be a general solution for resolving 
templated types. For example:

struct S(T){
     int[] x;
     auto opResolveInout(string op){ ... } // op is "const"/immutable/""
}

> 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.

Probably it should return an array of tail-immutable keys. Additionally, 
as Andrej proposes, there should be ikeys that returns a tail-immutable 
array.

> 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,

Lookup should succeed without implicit .idup whenever supportable. 
Otherwise I fail to see the benefit of the implicit .idup behavior and 
it should be dropped entirely.

> 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
>

'keys' should return an array of tail-immutable keys.
int[int] => typeof(keys)==int[], typeof(ikeys)==immutable(int)[]
int[int[]] => typeof(keys) == immutable(int)[][], 
typeof(ikeys)==immutable(int[])[].

etc.