Container templates and constancy of elements

[H. S. Teoh]

On Wed, Mar 14, 2012 at 06:51:54PM +0000, Stewart Gordon wrote:
> With some containers, such as lists and trees (binary search trees
> aside), it doesn't matter if the elements can change state, since
> the data structure remains well-formed.
> 
> However, with others, such as sets and AAs, it's desirable if the
> keys don't mutate.  Any operations on them won't work right if there
> are keys in the wrong hash slots or out of order (depending on the
> underlying data structure) because they have changed since being put
> into the container.  Of course, this doesn't apply to _values_ in an
> AA, since these can safely mutate.

IMO, AA keys should be *implicitly* immutable. That is, when you declare
something like:

	int[ubyte[]] x;

then the key type of x should be immutable(ubyte)[], not ubyte[].

Otherwise, it just doesn't make any sense, and causes several of the
AA-related bugs currently on the bugtracker.


> In Java and D1, it seems you just have to go on trust if you want
> your container to accept key types other than strict value types.
> But can we do better in D2 - short of forcing the key type to be
> immutable, which would hinder the container's usefulness?
> 
> But it seems D2 has taken one step in that general direction by
> automatically tail-consting the key type of an AA.  But it doesn't
> stop modifications to the key through mutable references to the
> data.

Exactly. AA keys must be immutable, no matter what. Of course, to
interact nicely with existing code, methods like .opIndex or .get should
also accept mutable keys for lookup purposes, and .idup them when a new
entry needs to be created.


> And if the key is of class type, you can still modify the object,
> since D2 conflates constancy of an object reference with constancy of
> the object itself.  This is in itself silly.  Really, D should have
> tail-const built in for stuff like this.

This is a major PITA. Especially if you're trying to be const-correct in
your code, then it leads to nonsense like being unable to traverse a
linked list inside a const method, because the iteration pointer itself
is const (whereas it's the *data* it's pointing to that's const) so you
can't overwrite the loop variable. However, you *can* recursively search
the list.

I find this to be a major WAT in D.


[...]
> I suppose there are a few possibilities for what constancy to apply
> to elements of a data structure to which changes might affect the
> structure's integrity:
> 
> (a) force the type to be tail-const if it's an array, otherwise don't add any constancy
> (b) force the type to be tail-const if it's an array, or fully const if it's a class
> (c) force the type to be tail-immutable if it's an array, otherwise don't add any constancy
> (d) force the type to be tail-immutable if it's an array, or fully immutable if it's a class
> (e) don't add any constancy, but just rely on trust
> 
> 
> Currently, AAs implement (a).

Which is prone to bugs.


> (d) guarantees that changes to the data that mess up the data
> structure will never happen, at least if the programmer doesn't bypass
> the const system.
[...]

I believe this is the best way to go. Well, at least for AA's this is
needed. Otherwise there will always be the possibility that AA's will
malfunction when the key changes behind the container's back.


T

-- 
Just because you survived after you did it, doesn't mean it wasn't stupid!