www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - dynamic arrays of immutable question: Are the elements actually

reply "monarch_dodra" <monarchdodra gmail.com> writes:
I was investigating the inner working of appender, and I'm not 
100% sure what it is doing with arrays of immutables is 
completely kosher.

However, I'm not 100% how arrays of immutables work.

In particular, since dynamic arrays can be appended to, by 
design, the elements can be mutated, right?
I mean, take this program:
//----
     immutable(int)[] arr = [1, 2];
     // data in memory [1, 2, 0, 0, 0, ...

     arr ~= 3;
     // data in memory [1, 2, 3, 0, 0, ...

     arr ~= 4;
     // data in memory [1, 2, 3, 4, 0, ...
//----
I don't actually know if the data is 0 initilized, but I figure 
it is irrelevent: The point is that the data *has* to be mutated 
for appending, so the data can't be immutable.

So my question is:
If I by-pass compiler protections via casting, is modifying the 
elements of a dynamic array* of immutables actually defined 
behavior ?

* Assuming GC allocated dynamic array, and not slice of static 
immutable array, for example.

http://dpaste.dzfl.pl/41eeeacf
Jan 09 2013
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, January 09, 2013 13:29:43 monarch_dodra wrote:

 I was investigating the inner working of appender, and I'm not
 100% sure what it is doing with arrays of immutables is
 completely kosher.
 
 However, I'm not 100% how arrays of immutables work.
 
 In particular, since dynamic arrays can be appended to, by
 design, the elements can be mutated, right?
 I mean, take this program:
 //----
      immutable(int)[] arr = [1, 2];
      // data in memory [1, 2, 0, 0, 0, ...
 
      arr ~= 3;
      // data in memory [1, 2, 3, 0, 0, ...
 
      arr ~= 4;
      // data in memory [1, 2, 3, 4, 0, ...
 //----
 I don't actually know if the data is 0 initilized, but I figure
 it is irrelevent: The point is that the data *has* to be mutated
 for appending, so the data can't be immutable.
 
 So my question is:
 If I by-pass compiler protections via casting, is modifying the
 elements of a dynamic array* of immutables actually defined
 behavior ?
 
 * Assuming GC allocated dynamic array, and not slice of static
 immutable array, for example.
 
 http://dpaste.dzfl.pl/41eeeacf


When you append to array, the elements being added are in untyped memory. So, 
no mutation of immutable anything is going on at all.

I don't know what Appender is doing, but casting away immutable and mutating 
anything is undefined behavior. However, if you _know_ that the data is 
actually mutable, then you can get away with it. It's still technically 
undefined behavior though. Pretty much the only place that it would make sense 
to do that that I can think of is with std.concurrency, but again, I don't 
know what Appender is doing.

- Jonathan M Davis
Jan 09 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 9 January 2013 at 12:38:13 UTC, Jonathan M Davis 
wrote:

 When you append to array, the elements being added are in 
 untyped memory. So,
 no mutation of immutable anything is going on at all.


Ok, I guess that makes sense.


 I don't know what Appender is doing, but casting away immutable 
 and mutating
 anything is undefined behavior. However, if you _know_ that the 
 data is
 actually mutable, then you can get away with it. It's still 
 technically
 undefined behavior though. Pretty much the only place that it 
 would make sense
 to do that that I can think of is with std.concurrency, but 
 again, I don't
 know what Appender is doing.


Hum...

Appender uses "arr.length = arr.capacity" so as to mark the array 
as "used" so that if anybody tries to append to the array, it 
will not interfere with appender. Does this operation "make the 
memory typed"?

Here is a reduced test case of what appender does

http://dpaste.dzfl.pl/d8fce486

//----
import std.stdio;

void main()
{
     //The initial array
     immutable(int)[] arr1 = [0, 1, 2, 3];

     //The same array, aliased as mutable;
     int[] arr2 = cast(int[])arr1;

     //Change underlying range size so that other appends to arr1 
cause relocation
     size_t capacity = arr1.capacity;
     if (capacity > arr1.length)
     {
         auto tmp = arr2;
         tmp.length = tmp.capacity;
         assert(arr2.ptr == tmp.ptr);
         assert(arr1.capacity == 0);
     }
     else
         assert(0); //To make sure we are actually testing 
something

     //Write to the not yet written but reserved to zone
     for ( ; arr2.length < capacity; )
     {
         immutable len = arr2.length;
         arr2.ptr[len] = cast(int)len; //HERE
         arr2 = arr2.ptr[0 .. len + 1];
     }

     //Check arr2
     writeln(arr2);
}
//----

The original line I am concerned about is "HERE": Is this a legal 
mutation?

On topic, the actual code in Appender looks like this
//----
//Type of item is "U", with "isImplicitlyConvertible!(U, T)"
_data.arr.ptr[len] = cast(Unqual!T)item;
//----
Worth noting is:
* This will bigtime fail if T has a constructor (should use 
emplace).
* Also, is that cast even legal?

If emplace is able to modify the user provided immutable array, 
then wouldn't it be better off storing an actual "T[]" (instead 
of (Unqual!T)[]): This would avoid any abusive use of casts, and 
preserve the qualified type, right?
Jan 09 2013
next sibling parent reply ollie <ollie home.net> writes:
On Wed, 09 Jan 2013 14:38:13 +0100, monarch_dodra wrote:


 On Wednesday, 9 January 2013 at 12:38:13 UTC, Jonathan M Davis wrote:

 When you append to array, the elements being added are in untyped
 memory. So,
 no mutation of immutable anything is going on at all.


 
 Ok, I guess that makes sense.
 


Newbie answer and question to follow.

The area of memory after .length to .capacity is not defined (untyped) in 
the D spec.  It is a trick used by the compiler to not slow down appends 
with repetitive memory allocations.  I believe that since the memory has 
been allocated for an array of a certain type, the extra capacity memory 
should be of that type until the array and its slices have been 
deallocated by druntime.

My question is about immutable and casting in general.  I've heard Walter 
say of immutable, "Turtles all the way down.".  If say I have a plug-in  
system with a defined interface and I pass it an immutable array (ie 
immutable(int)[]) then it uses a cast to mutate, that seems to defeat the 
purpose of immutable.  When the plug-in returns, I now have an immutable 
array that has been mutated.  Is this how immutable and casting are 
supposed to work?
Jan 09 2013
next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 9 January 2013 at 17:22:25 UTC, ollie wrote:

 My question is about immutable and casting in general.  I've 
 heard Walter
 say of immutable, "Turtles all the way down.".  If say I have a 
 plug-in
 system with a defined interface and I pass it an immutable 
 array (ie
 immutable(int)[]) then it uses a cast to mutate, that seems to 
 defeat the
 purpose of immutable.  When the plug-in returns, I now have an 
 immutable
 array that has been mutated.  Is this how immutable and casting 
 are
 supposed to work?


Seems you are raising two different issues:

"Turtles all the way down" means the immutability is transitive.

For example, an "immutable(int*)" means both the pointer AND
pointee are immutable. This is in contrast to C++, where you can
have a const pointer to non const data. This is impossible in D.

As for the cast question: Casting is a means to do *anything* you
want, no guarantees. If you want to do something illegal, there's
no one left to stop you. Not really any different from C++
actually.
Jan 09 2013
prev sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, January 09, 2013 17:22:25 ollie wrote:

 On Wed, 09 Jan 2013 14:38:13 +0100, monarch_dodra wrote:

 On Wednesday, 9 January 2013 at 12:38:13 UTC, Jonathan M Davis wrote:

 When you append to array, the elements being added are in untyped
 memory. So,
 no mutation of immutable anything is going on at all.


 
 Ok, I guess that makes sense.


 
 Newbie answer and question to follow.
 
 The area of memory after .length to .capacity is not defined (untyped) in
 the D spec. It is a trick used by the compiler to not slow down appends
 with repetitive memory allocations. I believe that since the memory has
 been allocated for an array of a certain type, the extra capacity memory
 should be of that type until the array and its slices have been
 deallocated by druntime.
 
 My question is about immutable and casting in general. I've heard Walter
 say of immutable, "Turtles all the way down.". If say I have a plug-in
 system with a defined interface and I pass it an immutable array (ie
 immutable(int)[]) then it uses a cast to mutate, that seems to defeat the
 purpose of immutable. When the plug-in returns, I now have an immutable
 array that has been mutated. Is this how immutable and casting are
 supposed to work?


If you mutate a variable after casting away either const or immutable, it's 
undefined behavior (unlike C++). Don't do it. You're breaking the type system 
when you do and will end up with bugs. It's possible, because D is a systems 
language, and if you know exactly what you're doing, you can get away with it 
under some circumstances, but it's still undefined behavior, and the compiler 
is free to assume that immutable data _never_ changes, so even if the data is 
not in read-only memory (if it were, mutating it after casting away immutable 
would likely result in a segfault), you'll end up with nasty bugs if you cast 
away immutable to mutate it, because the compiler will optimize code based on 
the assumption that the data will never change.

http://stackoverflow.com/questions/4219600/logical-const-in-d/4221334

The _only_ cases where it generally might make sense to cast away immutable is 
if you're passing data to a C function which you _know_ won't mutate it but 
unfortunately doesn't use const in its signature or when you're using 
std.concurrency - in which case, you can get away with casting an object to 
immutable to pass it across threads and then casting immutable away again as 
long as you _know_ that the original thread doesn't keep any references to the 
object. But even then, you really should be using shared for that rather than 
immutable, but there's a bug that prevents shared from currently working with 
std.concurrency like it should.

D's const and immutable provide hard guarantees, so casting them away is
generally just begging for trouble, because then _you_ must guarantee the
same things that the compiler normally would.

- Jonathan M Davis
Jan 09 2013
prev sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 9 January 2013 at 13:38:14 UTC, monarch_dodra wrote:

 The original line I am concerned about is "HERE": Is this a 
 legal mutation?


I think I got my answer actually: No. No it isn't. Changing the 
array's length initialize the not yet typed memory to T.init, 
ergo, it types the memory, so changing it again would be illegal 
(AFAIK).

This has not failed on any platform yet though.

//----
import std.stdio;


struct S
{
     int i = 9;	
}

void main()
{
     //The initial array
     immutable(S)[] arr1 = [S(0)];

     size_t capacity = arr1.capacity;
     writeln(arr1.ptr[0 .. arr1.capacity]);
     arr1.length = arr1.capacity;
     writeln(arr1);
}
//----
[immutable(S)(0), immutable(S)(10991), immutable(S)(493355328)]
[immutable(S)(0), immutable(S)(9), immutable(S)(9)]
//----

The "good news" is that since the values are T.init'd, then 
opEqual becomes somewhat more valid, although arguably, it should 
really be in-place construction, *especially* if immutable is 
involved (or types without opAssign...).
Jan 09 2013
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 9 January 2013 at 18:17:52 UTC, monarch_dodra wrote:

 The "good news" is that since the values are T.init'd, then 
 opEqual becomes somewhat more valid, although arguably, it 
 should really be in-place construction, *especially* if 
 immutable is involved (or types without opAssign...).


Wait, never mind. That's only a special case in Appender's 
implementation. Since it mallocs the rest of the time, this 
doesn't hold, and anything with a constructor (or just) will not 
be correctly initialized :/
Jan 09 2013