AA key conversion woes

[kenji hara]

2012年4月18日3:41 H. S. Teoh <hsteoh at quickfur.ath.cx>:
> 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.

I think AA key should be immutable, but in some case, whole immutable
is not needed.
- With basic type keys (int, long, double, ...), they have no
indirections, so you can add/remove qualifiers as you expects.

   int user_specified_key;
   immutable int AA_stored_key = user_specified_key;  // add qualifier
copy conversion, it is safe.

- With compound types (arrays, and pointers), if they have no
*mutable* indirections, you can add/remove their head qualifiers with
copy conversion.

   int[int[]] aa;  // same as int[immutable(int[])]
   immutable(int)[] key1;
   aa[key1] = 10;   // key1 is implicitly convertible to immutable(int[])
   int[] key2;
   aa[key2] = 10;   // Error! key2 is not implicitly convertible to
immutable(int[])
   aa[key2.idup] = 10;   // valid

   int[int*] aa;  // same as int[immutable(int*)]
   immutable(int)* key1;
   aa[key1] = 10;   // key1 is implicitly convertible to immutable(int*)
   int* key2;
   aa[key2] = 10;   // Error! key2 is not implicitly convertible to
immutable(int*)

Then, you can check the AA key type with assertion like follows:

template AssociativeArray(Key, Value)
  if (is(typeof((ref Key key){
     immutable(Key) ikey = key;  // Key is implicitly convertible to
immutable(Key)?
  })))
{
    alias immutable(Key) InterfaceKeyType;

    InterfaceKeyType[] keys();
      // even if InterfaceKeyType == immutable(string),
      // keys[n] can implicitly convertible to string.

  private:
    struct Slot { InterfaceKeyType* key; ... }
}

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

You can apply to them same rule as built-in compound types."If the
given Key type has mutable indirection, whole immutable key is
required, otherwise, you can store keys that head mutable but tail
immutable.

struct S1 { immutable(int)[] arr; }
auto s1m = S1([1,2,3]);
immutable s1i = s1m;  // s1i.arr is still immutable, so you can
convert s1 to immutable with copy.
int[S1] aa;
aa[s1m] = 10; // valid, s1m is implicitly convertible to immutable(S1)

struct S2 { int[] arr; }
auto s2m = S2([1,2,3]);
immutable s2i = s2m;  // this conversion breaks const system, then
compiler rejects this line.
int[S2] aa;
aa[s2m] = 10; // invalid! user should create immutable copy of s2m explicitly

class C { ... }
auto cm = new C();  // class reference is always reference in D.
immutable ci1 = cm;  // so this is always invalid.
immutable ci2 = immutable(C)();
int[C] aa;
aa[cm] = 10; // always invalid, cm is not implicitly convertible to immutable(C)
aa[ci2] = 10; // valid

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

If Key type has inout qualifier, AA implementation should replace it to const.
int[inout(int)[]] --> AssociativeArray!(const(int)[], int)

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

Agreed. It is enough restriction for AA key.
With implicitly convertible to immutable rule I explained above, we
can keep convenient usage.

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

Thanks.

Kenji Hara