BTW, here are a list of tango classes that can corrupt data that was not passed to them.  These should probably be fixed:

tango.net.ftp.FtpClient
tango.net.cluster.NetworkCall
tango.util.log.Hierarchy
tango.stdc.stringz

I haven't looked through phobos, but I'm sure there are instances which have this problem as well.

-Steve

Steven Schveighoffer wrote:
> "Regan Heath" wrote
>> Both variables above are references to the same data.  You're using one variable to change that data, therefore the other variable which still refers to the same data, sees the changes.
>>
>> If the concatenation operation had to reallocate the memory it would produce a copy, and you wouldn't see the changes.
>>
>> So, this behaviour is non deterministic, however...
> 
> The problem is that invariant data is changing.  This is a no-no for pure
> functions which Walter has planned.  If invariant data can change without violating the rules of the spec, then the compiler implementation or design is flawed.  I think the design is what is flawed.

That is another issue which I didn't even address.

Assuming 'string' means 'invariant(char)' and assuming that means the char values cannot change (I say assuming because I haven't had the chance to really internalise the new const yet) then I reckon the implementation of invariant is simply broken/buggy.

> I have several problems with this concat operator issue.
> 
> First, that x ~= y does not effect the same behavior as x = x ~ y.  This is a fundamental flaw in the language in my opinion.  any operator of the op= form is supposed to mean the same as x = x op y.  This is consistent throughout all of D, except in this case.

The problem stems from the fact that x ~= y always assigns the result to x, whereas x ~ y can potentially be assigned to something else.  This means the latter must create a new/temporary object to store the result.

In the case of arrays this effectively means that x ~ y always creates a new array which is a copy of the old ones.  But x ~= y need not create a new array as it can append to the existing one.

The ~= form therefore allows an optimisation which is beneficial.  Not allowing people to have both methods at their disposal would likely cause an outcry.

> Second, there is the issue of the spec.  The spec clearly states that concatenation should result in a copy of both sides.  

1. The website cannot be trusted completely and is often behind the compiler when it comes to the spec.

2. It could be argued that "concatenation" is the x ~ y form and not the ~= form, which is called "append".  From the website spec:

"The binary operator ~ is the cat operator. It is used to concatenate arrays"

"Similarly, the ~= operator means append"

"Concatenation always creates a copy of its operands, even if one of the operands is a 0 length array"

I'm probably splitting hairs here and I doubt there is much point arguing it - I just wanted to point out another way of reading the spec.

> Obviously, this isn't
> true in all cases.  The spec should be changed for both D 1.x and 2.x IMMEDIATELY to prevent unsuspecting coders from using ~= when what they really want is just ~.
>
> Third, I have not seen this T[new] operator described anywhere, but I am concerned that D 1.0 will not be updated.  This leaves all coders who are not ready to switch to D 2 at risk.  But from the inferred behavior of T[new], I'm expecting that this will probably fix the problem.

Aside from the apparent invariant bug the only case which causes me a slight worry is the case involving a struct.  The only solution I can imagine would be to somehow determine the memory was originally allocated to a 'struct' and therefore reallocation for an 'array' must cause a copy.

I'm not sure what information the GC keeps on allocated blocks, I believe there is a pointers/nopointers flag and that could form the basis of a fairly crude test perhaps (as struct contains pointers and char[] does not);

Even if nothing can be done to detect this case I'm not sure it's a huge issue, after all it only affects people using static arrays as the first member of a struct which they take a slice of and then modify (concatenate) without performing "copy on write" - which is a no no in D anyway.

Regan

Regan Heath wrote:
> 
> The example shown above is not corrupting any memory.  The 2nd one (not shown above) seems to be and it worries me much more.

The same "copy on write" issue applies to each case, but I agree that the behavior of the second is certainly less appealing.  And you're right that it can and will corrupt memory if used in this manner.  A pointer to the head of the struct is equal to a pointer to the head of the array, so right now the runtime is assuming that the entire block belongs to the array, which is wrong.  Unfortunately, there is little that can be done about this mechanically.  When a slice of the struct array is taken, type information is lost, so the compiler doesn't even know there's a struct involved, and so would be unable to supply additional type information to the runtime.


Sean

Steven Schveighoffer wrote:
> "Regan Heath" wrote
>> Steven Schveighoffer wrote:
>>> "Sean Kelly" wrote
>>>> Steven Schveighoffer wrote:
>>>>> "Steven Schveighoffer" wrote
>>>>>> Another reason why this is seems to be a bug and NOT a feature:
>>>>>>
>>>>>>        string ab = "ab".idup;
>>>>>>        string a = ab[0..1];
>>>>>>        a ~= "c";
>>>>>>        writefln("ab = ",ab); // also outputs "ac"
>>>>>>
>>>>>> This changes an invariant string without compiler complaint!
>>>>> more bugs :)
>>>> This is expected behavior.
>> In this post I'm commenting on the example shown above, not the 2nd one (which to be honest is much more worrying).  I am a bit confused as to which example Sean was saying was "expected behaviour".
>>
>>> Behavior by design, perhaps.  Expected, I should hope not.  I would never expect to be able to have one variable overwrite another without obvious casting.
>> Both variables above are references to the same data.  You're using one variable to change that data, therefore the other variable which still refers to the same data, sees the changes.
>>
>> If the concatenation operation had to reallocate the memory it would produce a copy, and you wouldn't see the changes.
>>
>> So, this behaviour is non deterministic, however...
> 
> The problem is that invariant data is changing.  This is a no-no for pure functions which Walter has planned.  If invariant data can change without violating the rules of the spec, then the compiler implementation or design is flawed.  I think the design is what is flawed.

One could argue that invariant data is changing because of a programmer error, but you have a point.

> I have several problems with this concat operator issue.
> 
> First, that x ~= y does not effect the same behavior as x = x ~ y.  This is a fundamental flaw in the language in my opinion.  any operator of the op= form is supposed to mean the same as x = x op y.  This is consistent throughout all of D, except in this case.
> 
> Second, there is the issue of the spec.  The spec clearly states that concatenation should result in a copy of both sides.  Obviously, this isn't true in all cases.  The spec should be changed for both D 1.x and 2.x IMMEDIATELY to prevent unsuspecting coders from using ~= when what they really want is just ~.

Or the runtime could be changed to always copy.  However, it would absolutely murder application performance for something like this:

char[] buf;
for( int i = 0; i < 1_000_000; ++i )
    buf ~= 'a';

And looping on an append is a pretty typical use case, in my experience.

> Third, I have not seen this T[new] operator described anywhere, but I am concerned that D 1.0 will not be updated.  This leaves all coders who are not ready to switch to D 2 at risk.  But from the inferred behavior of T[new], I'm expecting that this will probably fix the problem.

The T[new] syntax basically said that resizable arrays would be declared as T[new] and non-resizable slices would be declared as T[].  My major problem with this is that it would change the way normal arrays are declared, and break tons of code in the process.


Sean

Regan Heath wrote:
> Steven Schveighoffer wrote:
>> "Regan Heath" wrote
>>> Both variables above are references to the same data.  You're using one variable to change that data, therefore the other variable which still refers to the same data, sees the changes.
>>>
>>> If the concatenation operation had to reallocate the memory it would produce a copy, and you wouldn't see the changes.
>>>
>>> So, this behaviour is non deterministic, however...
>>
>> The problem is that invariant data is changing.  This is a no-no for pure
>> functions which Walter has planned.  If invariant data can change without violating the rules of the spec, then the compiler implementation or design is flawed.  I think the design is what is flawed.
> 
> That is another issue which I didn't even address.
> 
> Assuming 'string' means 'invariant(char)' and assuming that means the char values cannot change (I say assuming because I haven't had the chance to really internalise the new const yet) then I reckon the implementation of invariant is simply broken/buggy.

I don't know that it's broken so much as potentially misleading.  That example never actually changed any of the data in the string, it simply appended additional data to the string.  Thus invariance of the data was preserved.

>> Third, I have not seen this T[new] operator described anywhere, but I am concerned that D 1.0 will not be updated.  This leaves all coders who are not ready to switch to D 2 at risk.  But from the inferred behavior of T[new], I'm expecting that this will probably fix the problem.
> 
> Aside from the apparent invariant bug the only case which causes me a slight worry is the case involving a struct.  The only solution I can imagine would be to somehow determine the memory was originally allocated to a 'struct' and therefore reallocation for an 'array' must cause a copy.
> 
> I'm not sure what information the GC keeps on allocated blocks, I believe there is a pointers/nopointers flag and that could form the basis of a fairly crude test perhaps (as struct contains pointers and char[] does not);

That's pretty much it.  And if the GC were to retain additional type info it would be tailored to finding pointers for collection purposes rather than determining whether one section of a block is a static array or an int.

> Even if nothing can be done to detect this case I'm not sure it's a huge issue, after all it only affects people using static arrays as the first member of a struct which they take a slice of and then modify (concatenate) without performing "copy on write" - which is a no no in D anyway.

Right.


Sean

Steven Schveighoffer wrote:
> BTW, here are a list of tango classes that can corrupt data that was not passed to them.  These should probably be fixed:
> 
> tango.net.ftp.FtpClient
> tango.net.cluster.NetworkCall
> tango.util.log.Hierarchy
> tango.stdc.stringz
> 
> I haven't looked through phobos, but I'm sure there are instances which have this problem as well.

Thanks, I'll look into these.


Sean

Regan Heath wrote:
> Steven Schveighoffer wrote:
>> import std.stdio;
>>
>> struct X
>> {
>>         char[5] myArray;
>>         int x;
>> }
>>
>> void main()
>> {
>>         X[] x = new X[2];
>>         x[0].myArray[] = "hello";
>>         char[] myslice = x[0].myArray[0..3];
>>         writefln("%x %x %x", &x[0].x, &x[0].myArray[0], &myslice[0]);
>>         myslice ~= "hithere";
>>         writefln("%x %x %x", &x[0].x, &x[0].myArray[0], &myslice[0]);
>>         writefln("%s %d", x[0].myArray, x[0].x);
>> }
>>
>> output:
>>
>> 868FE8 868FE0 868FE0
>> 868FE8 868FE0 868FE0
>> helhi 25970
> 
> This one worries me.
> 
> I believe the problem is caused by the memory address of myArray[0] being the same as the memory address of the struct.  Is this what you realised Sean... I may be a bit slow on the uptake here :)

Yes :-)


Sean

Sean Kelly wrote:
> Regan Heath wrote:
>> Steven Schveighoffer wrote:
>>> The problem is that invariant data is changing.  This is a no-no for pure
>>> functions which Walter has planned.  If invariant data can change without violating the rules of the spec, then the compiler implementation or design is flawed.  I think the design is what is flawed.
>>
>> That is another issue which I didn't even address.
>>
>> Assuming 'string' means 'invariant(char)' and assuming that means the char values cannot change (I say assuming because I haven't had the chance to really internalise the new const yet) then I reckon the implementation of invariant is simply broken/buggy.
> 
> I don't know that it's broken so much as potentially misleading.  That example never actually changed any of the data in the string, it simply appended additional data to the string.  Thus invariance of the data was preserved.

[example pasted again for clarity]

> string ab = "ab".idup;
> string a = ab[0..1];
> a ~= "c";
> writefln("ab = ",ab); // also outputs "ac"

True for 'a' but when appending to 'a' it writes over the memory which 'ab' guarantees is invariant.

So, in the general case any slice of invariant data which is shorter than the original invariant data can be used to overwrite the original invariant data after the slice.

Perhaps ~= should be disabled for invariant arrays.

Regan

"Regan Heath" wrote
> 2. It could be argued that "concatenation" is the x ~ y form and not the ~= form, which is called "append".  From the website spec:
>
> "The binary operator ~ is the cat operator. It is used to concatenate arrays"
>
> "Similarly, the ~= operator means append"
>
> "Concatenation always creates a copy of its operands, even if one of the operands is a 0 length array"

Look at the example for append:

"a ~= b;		// a becomes the concatenation of a and b"

This is the only explanation of what "append" does.

Yes, we are splitting hairs, but they are important hairs to split :) Having the spec be accurate is important for not only compiler implementors (which right now doesn't matter much but might in the future) and to developers using D.

Just a simple explanation of:

append may or may not re-use the memory that the original array uses. Therefore you should not use the append operator unless you know the array to be appended to is a dynamic array and not a slice of a dynamic array.  If this isn't the case, memory corruption can occur:

(paste Oskar's example here)

-Steve

Regan Heath wrote:
> Sean Kelly wrote:
>> Regan Heath wrote:
>>> Steven Schveighoffer wrote:
>>>> The problem is that invariant data is changing.  This is a no-no for pure
>>>> functions which Walter has planned.  If invariant data can change without violating the rules of the spec, then the compiler implementation or design is flawed.  I think the design is what is flawed.
>>>
>>> That is another issue which I didn't even address.
>>>
>>> Assuming 'string' means 'invariant(char)' and assuming that means the char values cannot change (I say assuming because I haven't had the chance to really internalise the new const yet) then I reckon the implementation of invariant is simply broken/buggy.
>>
>> I don't know that it's broken so much as potentially misleading.  That example never actually changed any of the data in the string, it simply appended additional data to the string.  Thus invariance of the data was preserved.
> 
> [example pasted again for clarity]
> 
>  > string ab = "ab".idup;
>  > string a = ab[0..1];
>  > a ~= "c";
>  > writefln("ab = ",ab); // also outputs "ac"
> 
> True for 'a' but when appending to 'a' it writes over the memory which 'ab' guarantees is invariant.

Oops, you're right.

> So, in the general case any slice of invariant data which is shorter than the original invariant data can be used to overwrite the original invariant data after the slice.
> 
> Perhaps ~= should be disabled for invariant arrays.

Or perhaps it should always reallocate.  I'd originally thought it actually did this based on something Walter said, but I misunderstood.


Sean