burner
commented
16 years ago andrei (@andralex) commented on 2008-01-31T14:14:28Z
We are well aware of the limitation, and are considering a number of approaches to it, some along the lines suggested by this enhancement request. It is a hard problem for multiple reasons. One of them is that the solution suggested in the enhancement request is unsound for a number of types, including arrays of arrays. This is because concatenating two arrays of arrays is not "deep" - it will create a new outer array but it will not duplicate each of the contained array. Consider:
int[][] array1 = new int[][10];
invariant(int[]) x = ([ 1, 2, 3 ]).idup;
invariant(int[])[] array2 = [ x ];
int[][] array3 = array1 ~ array2;
array3[10][0] = 5; // unsound, changes invariant arrayThis illustrates how code with the proposed semantics can violate immutability.
To recap today's semantics, consider:
import std.stdio;
struct S { int * p; }
void main() { test!(int); test!(int[]); test!(S); }
void test(T)() { auto m = new T[10]; auto c = new const(T)[15]; auto i = new invariant(T)[20]; auto mm = m ~ m; auto mc = m ~ c; auto mi = m ~ i; auto cc = c ~ c; auto ci = c ~ i; auto ii = i ~ i; writeln("mm: ", typeof(mm).stringof); writeln("mc: ", typeof(mc).stringof); writeln("mi: ", typeof(mi).stringof); writeln("cc: ", typeof(cc).stringof); writeln("ci: ", typeof(ci).stringof); writeln("ii: ", typeof(ii).stringof); }
This program prints:
mm: int[] mc: int[] mi: int[] cc: const(int)[] ci: int[] ii: invariant(int)[] mm: int[][] mc: const(int)[][] mi: const(int)[][] cc: const(int[])[] ci: const(int)[][] ii: invariant(int[])[] mm: S[] mc: const(S)[] mi: const(S)[] cc: const(S)[] ci: const(S)[] ii: invariant(S)[]
which is quite inconsistent (handles int, int[], and S all differently) and worthy a bug report.
One direction explored to address this problem is allowing definition of polysemous types - types that can exist only as rvalues and allow implicit conversion to a number of other types. Within that framework it should be possible to design a parameterized type called Unique!(T) that allows conversions to invariant(T) and T alike. Then a function such as listdir could return Unique!(char[]) which can be converted, to its client's desire, to either a mutable or immutable array.
Unique!(T) would remain unsound because there is no statically checkable way to initialize it properly, so it needs to be used with care. Basically the issue of typing "fresh" data reveals a hole in our type system that would be hard to fix without complicating it to an extent we considered unacceptable. To estimate the work involved for both compiler designers and users, I suggest consulting the paper archjava.fluid.cs.cmu.edu/papers/oopsla02.pdf (look for "unique).
Andrei
schveiguy (schveiguy) reported this on 2007-11-09T13:45:37Z
Transfered from https://issues.dlang.org/show_bug.cgi?id=1654
CC List
Description
One of the great aspects of D is the array concatenation operator. However, the current compiler sets the type of the result according to the operands. This prevents using invariant or const arrays to build a mutable array without doing extra work. For example, the toStringz function:
char *toStringz(const(char)[] s) { copy = new char[s.length + 1]; copy[0..s.length] = s; copy[s.length] = 0; return copy.ptr; }
This could easily be written as: return (s ~ "\0").ptr;
Except that the result of the concatenation is a const(char)[].
But why does it need to be const? I'm guessing that the reason is because when dealing with functions that take invariant strings, it would be ugly to always have to cast to invariant when doing concatenation. And of course, functions that use invariant strings can be optimized differently than mutable or even const strings.
The issue I see is that the true result IS mutable, because it is generated from the heap. It's artificially cast to invariant to keep the type the same.
So here is a proposal that would allow efficiency, and utilization of the fact that concatenation always results in newly allocated data:
First, there should be two array concatenation operator internal functions. One that takes two invariant arrays and one that takes two const arrays. I'll call them icat and ccat respectively. Both will return mutable arrays. The icat function can be pure when pure functions are supported.
When the compiler encounters an array concatenation in code, if at least one argument is not invariant, then ccat will be used. If both arguments are invariant, then icat will be used.
Regardless of the method used, if the resulting rvalue is expected to be invariant, then an implicit invariant cast is allowed. This means that the following code does not need invariant casts:
char[] blah = "hello".dup; string blah2 = blah ~ "world";
If the result is assigned to an lvalue that is either const or mutable, then no cast is needed (mutable array is implicitly castable to const).
This would allow us to use the full potential of array concatenation without having to worry about casting away invariant or writing several lines of code to get around this problem.
I'll further point out that the workaround for the current problem does not allow efficient concatenation. For example:
const(char)[] a1, a2;
// method 1, just dup it. // the problem is that we make a needless temporary copy of the data char[] cat1 = (a1 ~ a2).dup;
// method 2, build a temporary array // the problem is that the initialization of the array is needless. char[] cat2 = new char[a1.length + a2.length]; // needless init of memory cat2[0..a1.length] = a1; cat2[a1.length..$] = a2;
In addition, idup is not needed for creating an invariant array out of the concatenation of two mutable or const arrays.