AA key conversion woes

[H. S. Teoh]

On Tue, Apr 17, 2012 at 09:32:12PM +0200, Timon Gehr wrote:
> On 04/17/2012 09:04 PM, Dmitry Olshansky wrote:
> >On 17.04.2012 22:59, Timon Gehr wrote:
[...]
> >>No, an immutable array cannot be sorted regardless of whether or not
> >>the slice is mutable.
> >
> >Mm I believe you can sort array with immutable *elements* like say
> >strings (at least dchar ones).
> >
> >
> 
> immutable(string)[] <- tail-immutable array, cannot be sorted in place
> string[] <- can be sorted, but it is not tail-immutable

OK now I'm confused about what exactly "tail-immutable" means. An array
of strings can be one of:

	immutable(char)[][]	(==string[])
	immutable(char[])[]	(==immutable(string)[])
	immutable(char[][])	(==immutable(string[]))

Does "tail-immutable" mean that if you strip away one layer of the type
(i.e., x[] becomes x) then the result is immutable? Or does it mean only
the *last* layer of the type is immutable?

Anyway, this also brings up another complexity with AA key types: if the
key type is string, for example, then it's OK for .keys to return
string[], i.e., just a simple array of strings, because string itself is
immutable, and we don't care what the user does to the array of keys
since they cannot actually modify the strings stored in the AA.

So it seems that AA keys only need to be tail-immutable? Then .keys just
returns an array of tail-immutable keys.

The exception seems to be classes, because class objects are always
passed by reference, so there's a hidden layer of indirection there. So
in the case of class objects, the key itself has to be immutable
(technically, just the actual object needs to be immutable, not the
reference, but here the reference is implicit). This is a bit of a
troublesome case, because now .keys has to return an array of immutable
objects, but in theory it's OK to reassign those objects, as long as you
don't modify data in the object via the class reference.

Structs don't suffer from this problem, because they are passed by
value, so the array returned by .keys holds copies of the structs, which
can be mutable. But they do suffer from another kind of problem: if the
struct contains references (pointers or class objects) then the
referenced objects must be immutable, though the struct itself is OK to
be mutable. The problem is, I don't think this is expressible in the
current language. (How do you express a struct that can be assigned to,
but whose reference members are tail-const/tail-immutable?)

The simple solution of just returning an array of immutable keys suffers
from the problem of being non-sortable.


T

-- 
MSDOS = MicroSoft's Denial Of Service