[Issue 1654] Array concatenation should result in mutable or invariant depending on usage

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=1654


andrei at metalanguage.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED




------- Comment #1 from andrei at metalanguage.com  2008-01-31 14:14 -------
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 array

This 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


--