AA key conversion woes

[Timon Gehr]

On 04/18/2012 01:51 AM, H. S. Teoh wrote:
> 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?
>

The term 'head' is usually used to denote the first element, and 'tail' 
is whatever is left when it is removed.

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

I think what you describe is (almost) the same problem as for classes.
It is a general and rather embarrassing issue with the type system. (it 
comes up all the time.) We need tail-qualifiers or a different feature 
akin to a 'rebindable' qualifier.


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