Arrays passed by almost reference?

gzp galap at freemail.hu
Thu Nov 12 07:43:11 PST 2009


> 
> You can create DynamicArray and RandomAccessRange already now.
> 
> Currently int[] a is very intuitive in its purpose, its just some of the 
> implementation details that get confusing.
> 
> int doSomething(in int[]) a)
> tells me doSomething is going to process an  int array of any size and 
> not modify it.
> 
> int doSomething(int[] a)
> tells me doSomething is going to process an int array of any size and 
> possibly modify it.
> 
> An explicit 'out int[] a' would make it even more obvious what the 
> function is going to do.
> 
> The thing is, dynamic arrays and slices are pretty much the same thing, 
> its just hard to track what the underlying store points to.

I think problem is that, dynamic arrays and slices are NOT the same. 
They have a common subset of interfaces (length, at, slice(maybe)), but 
they are just different. An array owns it's element, it can 
resize/remove, etc. the underlying structure. Ex A special array that 
stores the elements in a tree can add remove nodes at any time, but a 
slice of this "array" cannot alter the tree - only the elements (For 
example a AVL-tree cannot have a slice that modifies the element as it 
would require a restructuring of the tree, element modification can be 
performed only through the array itself)
I know int[] is a much simpler storage, but it makes my point more 
understandable.

So now back to int[]
According to the current implementation

foo(ref int[]) is an array: It can add/remove elements (restructure the 
tree)

foo(int[]) is a mixed thing. It is a slice with an automatic copy 
feature. It is not an array nor a slice.
If it would be a slice, than the underling struct could not be altered, 
but here it can be.
It does not own its elements as it cannot resize the underlying 
structure without penalty.
Actually it is a slice + copy_on_resize. When you modify the elements, 
it alters the element of the referred array, but when you resize it, it 
copies (or not, depending on the DMD implementation!!!) the elements 
into another array and creates a new slice+copy_on_resize object for 
this array.

Thus foo(int[]) is worse than the dangling pointers or buffer overwrite 
errors from C(C++). Semantically they are correct, so bug produced from 
resized int[] cannot be detected using tricks like patterns in the 
memory. It is something that can cause really-really nasty bugs. 
Especially when the copy of the original array on resizing depend on the 
dmd implementation. (depends on how much extra datas are allocated for 
an array before they are really reallocated).


 From my point of view it's quite rare to have an array that is 
temporally extended with elements (partially enabling to modify to old 
ones), then  forget the new ones. So please don't favor a feature in the 
core language that is either hardly used and causes bugs, that can be 
hardly  detected.

So my proposal is that (as been already mentioned by others):
  - have array those contains the element + structure,
	ex RandomAccessArray!(int) AVLTree
  - have slices (ranges) of array, where the structure cannot be altered
  - decide if int[] stands for a short version for either 
RandomAccessArray!(int) or Range!(int), but DO NOT have a mixed meaning, 
that can be altered/modified with const/immutable/ref qualifiers.



Some random thoughts:
[1,2,3,4] literal is the array itself. It could alter the structure, if 
it would not be an immutable object.

int[] a = [1,2,3,4] a is a slice of the array, cannot be resized.

int[] a = new int[100]; is a slice too,
new int[100] is a short version for new RandomAccassArray!(int)(100)

int[100] b;
int[] a = b; is a short version for a copy: a = RandomAccassArray!(int)( 
b ).opRange() or a much better solution'd be a slice to a static array 
if that's possible.

a.array is the referred array, thus a.array ~= 2 could resize the array, 
1. the slice a itself is not modified, it still points to the original 
subset - but then what about the removed elements ???
2. the slice a is automatically resized to point to the altered structure
3. slices of static arrays they cannot be resized

const int[] cannot resize the underlying array
int[] can

int[new] is the array itself (i'm not sure)
int[new] a = new int[100];
int[] slice_a = a;
assert( slice_a.array.ptr == a.ptr );

Gzp.



More information about the Digitalmars-d mailing list