Container templates and constancy of elements

[Steven Schveighoffer]

On Wed, 14 Mar 2012 14:51:54 -0400, Stewart Gordon <smjg_1998 at yahoo.com>  
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.
>
> 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.  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.  OK, so there's Rebindable, but I've found  
> it to be a PITA when trying to do generic programming with it, as well  
> as leading to this AA key anomaly because it isn't a built-in feature.
>
>
> 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).  (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.  (e) is the route D1 and  
> Java are forced to take.  Am I right in thinking that sets and maps in  
> the C++ STL take the same path?
>
>
> Anyway, what are people's thoughts on the right way to go here?

IMO, @safe code should only allow d, @system/trusted should allow e.

And the compiler shouldn't be "helping" you by adding const annotations.   
That is:

int[char[]] aa;

this line should either compile, and the type should be int[char[]] aa, or  
it should not compile.

D is supposed to be able to do "at your own risk" bare-metal types of  
things.  This seems like it unnecessarily limits code.

-Steve