www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - resizeable arrays: T[new]

reply Walter Bright <newshound1 digitalmars.com> writes:
Sean Kelly wrote:

 Jarrett Billingsley wrote:

 "Sean Kelly" <sean f4.ca> wrote in message 




news:f3uoj5$1b1i$1 digitalmars.com...

 Most array algorithms would apply.  But I'm still not sure I see
 the point of having an immutable reference, because it's just passed
 by value anyway.  Who cares if the size of the array is modified
 within a function where it's not passed by reference?  The change is
 just local to the function anyway.


 If that array is pointing into some meaningful area of memory (like
 in the example, a texture buffer), resizing the array could (probably
 would) move the array around, which I guess isn't illegal but then
 the function operating on the array wouldn't be accessing the correct
 place.  Prevent them from changing the length, it prevents them from
 accessing anywhere but there.


 Well yeah.  I don't personally think this is a problem because it
 doesn't affect the callee in any way, but I can see how others might
 disagree.  Doesn't 'final' do this now though?


There was a lot of talk about this problem today. Final doesn't quite do 
it, because it's not part of the type signature of the function. But 
making it a type signature adds a whole raft of complexity, and also 
inevitably completely screws up the notion of transitivity of const and 
invariant.

(The problem is if I pass a slice to a function, and then that function 
reallocates the slice by changing the length or appending to it, it can 
affect other slices into the same data in very hard-to-explain ways. 
Essentially, we needed to find a way to disallow it. Options explored 
and found unacceptable were final (causes more problems), ref counting 
arrays (too expensive), always duping (too expensive), adding 'slice' 
bits to the fat pointers (doesn't work), adding ref counting to the 
memory chunks (too expensive), and data flow analysis hacks (unreliable, 
inconsistent). Note that other languages solve the problem with ref 
counting, but we considered that unacceptable for D because it adds 50% 
to the cost of transferring arrays around, and big runtime costs in 
manipulating the ref counts. And that doesn't even consider 
multithreading or exception safety requirements.)

Now, it turns out that it is very rare for a function to legitimately 
want to resize a buffer passed to it. So we finally hit on the idea of 
making a resizeable array a different type, say:

    T[n]   a;  // static array
    T[]    b;  // dynamic array
    T[new] c;  // resizeable array

    a.length = 6;   // error, static array
    b.length = 6;   // error, dynamic array is not resizeable
    c.length = 6;   // ok
    b = c;          // ok, implicit conversion of resizeable to dynamic
    c = b;          // error
    c = b[0..n];    // error
    b = c[0..n];    // ok, but watch out if c is later resized
    b = c[0..n].dup; // ok, no worries
    c = cast(T[new])b; // ok, but this will be deliberate

Note that .dup will return a T[new], as will operator new. Slicing will 
return a T[]. The runtime representation of T[new] will be identical to 
that of T[], just the type is different.

So, if our function parameter is typed as T[], we know there isn't going 
to be any monkey business going on in that function with our other 
slices. If it's T[new], we know we need to take a hard look at it.

I think this will entail only very rare changes to user code, but will 
be a big improvement in type safety. Note that it will *still* possible 
for array resizing to affect other slices into the same array, but it's 
far, far less likely to happen inadvertently. The attractiveness of this 
solution is it nearly completely solves the problem with zero runtime cost.
Jun 04 2007
next sibling parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
I agree with your reasoning for this (honestly, the solution had never
occured to me before, although looking back I can think of a few places
where it would have been quite useful), although I can't say I'm a fan
of the syntax.  The "new" inside the brackets just looks strange; a new
what?

A few possible alternatives:

T[new]	// Proposed
T[$]	// Since $ already means "length" for arrays
T[*]	// Indicating the index could be anything
T[..]	// Bit of a stretch...
T[volatile] // Bit long
T[[]]	// Just ugly

Like I said; I'm erring on the side of liking the idea, just not the use
of "new" in that particular spot.

	-- Daniel
Jun 04 2007
next sibling parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Daniel Keep wrote:

 The "new" inside the brackets just looks strange; a new what?


I'm with you here ;)



 A few possible alternatives:
 
 T[new]	// Proposed


Looks awkward, yeah. And it would produce false hits for anyone doing 
new-hunting (happens when you care about allocations, but prototype 
using 'new').



 T[$]	// Since $ already means "length" for arrays


I don't like it... Looks like an out of bounds error to my parser ;)



 T[*]	// Indicating the index could be anything


++votes;


-- 
Tomasz Stachowiak
http://h3.team0xf.com/
h3/h3r3tic on #D freenode
Jun 04 2007
next sibling parent reply Lionello Lunesu <lio lunesu.remove.com> writes:
Tom S wrote:

 Daniel Keep wrote:

 The "new" inside the brackets just looks strange; a new what?


 
 I'm with you here ;)
 
 

 A few possible alternatives:

 T[new]    // Proposed


 
 Looks awkward, yeah. And it would produce false hits for anyone doing 
 new-hunting (happens when you care about allocations, but prototype 
 using 'new').


Huh. To me, that sounds like an argument *for* using [new], since any 
array passed as [new] can cause an allocation in that function.

I like the [new] syntax :P

L.
Jun 04 2007
parent Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Lionello Lunesu wrote:

 Tom S wrote:

 Daniel Keep wrote:

 The "new" inside the brackets just looks strange; a new what?


 I'm with you here ;)



 A few possible alternatives:

 T[new]    // Proposed


 Looks awkward, yeah. And it would produce false hits for anyone doing 
 new-hunting (happens when you care about allocations, but prototype 
 using 'new').


 
 Huh. To me, that sounds like an argument *for* using [new], since any 
 array passed as [new] can cause an allocation in that function.


Not really, if you consider that it may be modified using realloc or 
some other wild schemes. And these are ok. I'd usually search for 'new', 
'~' and 'length' :P



 I like the [new] syntax :P


Nooooo! What have I done! *slaps himself with a trout*


-- 
Tomasz Stachowiak
http://h3.team0xf.com/
h3/h3r3tic on #D freenode
Jun 04 2007
prev sibling parent Walter Bright <newshound1 digitalmars.com> writes:
Tom S wrote:

 A few possible alternatives:

 T[new]    // Proposed


 
 Looks awkward, yeah. And it would produce false hits for anyone doing 
 new-hunting (happens when you care about allocations, but prototype 
 using 'new').


I'm not necessarily sold on that syntax, but it's workable and unambiguous.


 

 T[$]    // Since $ already means "length" for arrays


 
 I don't like it... Looks like an out of bounds error to my parser ;)


There are parsing ambiguities with that I wish to avoid.



 T[*]    // Indicating the index could be anything


 ++votes;


That is used for VLA's in C99, which could mislead people.
Jun 04 2007
prev sibling next sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Daniel Keep wrote:

 I agree with your reasoning for this (honestly, the solution had never
 occured to me before, although looking back I can think of a few places
 where it would have been quite useful), although I can't say I'm a fan
 of the syntax.  The "new" inside the brackets just looks strange; a new
 what?
 
 A few possible alternatives:
 
 T[new]	// Proposed


Like the idea.  Not being able to tell a slice from a "real" array has 
always made me a bit uncomfortable, though it never occurred to me to 
make them separate types.  I would have expected it would introduce more 
headaches than it solves, but sounds like maybe not.  Cool.

T[new], though, doesn't speak to me as a syntax.


 T[$]	// Since $ already means "length" for arrays


Reminding us that '$'/length  can be assigned to ... not bad.


 T[..]	// Bit of a stretch...


I liked it at first till I realized it would mean the *opposite* of the 
what seems obvious to me -- i.e. I took it to mean that T is slice-like, 
meaning it can't be resized.  But it's supposed to be the other case.


 T[*]	// Indicating the index could be anything


That's not bad.


 T[volatile] // Bit long


Yeh, too long.


 T[[]]	// Just ugly


Eh.

Here's another:

T[~] // mnemonic: T can be concatenated onto

Or maybe it should just be a different brace type?
T{} = new T[10];

Probably breaks context freeness or something, but I like it if for no 
other reason than the braces are shift-[ shift-] on the US keyboard. 
It's also easy to type, and it's a nice mnemonic for array with 
augmented capabilities.

All the T[punctuation] varieties are going to be pretty annoying to 
type, I think.


--bb
Jun 04 2007
next sibling parent Downs <default_357-line yahoo.de> writes:
Bill Baxter wrote:

 T[~] // mnemonic: T can be concatenated onto


Seconded. I like it! :)
  -downs
Jun 04 2007
prev sibling next sibling parent Downs <default_357-line yahoo.de> writes:
Bill Baxter wrote:

 T{} = new T[10];
 
 Probably breaks context freeness or something, but I like it if for no 
 other reason than the braces are shift-[ shift-] on the US keyboard. 
 It's also easy to type, and it's a nice mnemonic for array with 
 augmented capabilities.


I missed that in my original reply. {} are slightly harder to
type than [] on german keyboards, because all the braces require the use of the
alt-gr key (just right of space).
This means [] is .. doable, but quickly typing {} requires quite a bit of
finger stretching.
(I usually put the thumb on alt-gr and reach over it with the index digit, and
.. well, { is the alt-gr usage of the 7 key. Acrobatics! :D )
  -- downs
Jun 04 2007
prev sibling parent torhu <fake address.dude> writes:
Bill Baxter wrote:

 Daniel Keep wrote:

 T[*]	// Indicating the index could be anything


 
 That's not bad.


It means something completely different in C99.  Not that that matters much.



 T[~] // mnemonic: T can be concatenated onto
 


Somehow this appeals to me. :)
Jun 04 2007
prev sibling next sibling parent Lars Ivar Igesund <larsivar igesund.net> writes:
Daniel Keep wrote:


 
 I agree with your reasoning for this (honestly, the solution had never
 occured to me before, although looking back I can think of a few places
 where it would have been quite useful), although I can't say I'm a fan
 of the syntax.  The "new" inside the brackets just looks strange; a new
 what?



 T[*]  // Indicating the index could be anything


This one.

-- 
Lars Ivar Igesund
blog at http://larsivi.net
DSource, #d.tango & #D: larsivi
Dancing the Tango
Jun 04 2007
prev sibling parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
Daniel Keep wrote:

 ...
 A few possible alternatives:
 
 T[new]	// Proposed
 T[$]	// Since $ already means "length" for arrays
 T[*]	// Indicating the index could be anything
 T[..]	// Bit of a stretch...
 T[volatile] // Bit long
 T[[]]	// Just ugly


One thing that didn't occur to me until just now is that T[$], T[*],
T[~] (and someone suggested T[?] on IRC) require you to alternate the
use of the shift key.  This means that I keep accidentally typing T[$}
or T{$] or T[4}.

I do think that T[*] is probably the nicest looking without giving the
wrong initial impression (T[$] could be misinterpreted as a typo, as
could T[..]), but is tricky to type quickly.  T[..] is easy to type
fast, as is T[new].

Another thing to consider is that T[*] requires your hands to move
further than either T[$] or T[..].

A few other possible symbols that can be entered without using shift (at
least on my keyboard):

T[.]
T[,]
T[`]
T[-]
T[=]
T[;]

I'm not counting keys on the numeric keypad because it's too far away
from the usual resting position of the hands.

Just something to chew on :)

	-- Daniel
Jun 04 2007
parent "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Daniel Keep" <daniel.keep.lists gmail.com> wrote in message 
news:f412os$24fh$1 digitalmars.com...

 Another thing to consider is that T[*] requires your hands to move
 further than either T[$] or T[..].


Ho-hoh!  I've got an asterisk key between my left ctrl and alt keys.  No 
shift for me ;)


 T[.]


Odd.  Doesn't say much.


 T[,]





 T[`]
 T[-]
 T[=]
 T[;]


All odd.  T[=] doesn't look bad, T[-] is easier to type for me.
Jun 04 2007
prev sibling next sibling parent reply Manfred Nowak <svv1999 hotmail.com> writes:
Walter Bright wrote


 The attractiveness of this 
 solution is it nearly completely solves the problem with zero
 runtime cost. 


Great thought.
If incorporating this new type, please address also the complication 
of having two views on the storage allocated for resizable arrays:
- the "potential" capacity, to which the `length' property currently 
can grow without the need of allocating more consecutive space
- the "actual" capacity, which is currently set/get by the `length' 
property

It is a pity, that the documentation, 
http://www.digitalmars.com/d/arrays.html#resize,
illustrates a pattern that can be easily incorporated into the 
language as a default behaviour:
- introduce new `length.pot' r/w-property
- whenever the `length' property exceeds the `length.pot' property 
double the `length.pot' property and allocate appropriate space
- issue an error when `length.pot' is decreased below the value of 
`length'
 
-manfred
Jun 04 2007
next sibling parent Lionello Lunesu <lio lunesu.remove.com> writes:
Manfred Nowak wrote:

 Walter Bright wrote
 

 The attractiveness of this 
 solution is it nearly completely solves the problem with zero
 runtime cost. 


 
 Great thought.
 If incorporating this new type, please address also the complication 
 of having two views on the storage allocated for resizable arrays:
 - the "potential" capacity, to which the `length' property currently 
 can grow without the need of allocating more consecutive space
 - the "actual" capacity, which is currently set/get by the `length' 
 property
 
 It is a pity, that the documentation, 
 http://www.digitalmars.com/d/arrays.html#resize,
 illustrates a pattern that can be easily incorporated into the 
 language as a default behaviour:
 - introduce new `length.pot' r/w-property
 - whenever the `length' property exceeds the `length.pot' property 
 double the `length.pot' property and allocate appropriate space
 - issue an error when `length.pot' is decreased below the value of 
 `length'


I agree. Although I'd keep the syntax less freaky by adding a property 
directly to arrays, array.capacity makes the most sense IMHO. It can be 
write-only for all I care.

Honestly, the array.length=12; array.length=0; -pattern (if you can call 
it that) is horrendous and should have been taken care of before v1.0 
was released, in my not so humble opinion.

L.
Jun 04 2007
prev sibling parent Daniel Keep <daniel.keep.lists gmail.com> writes:
Manfred Nowak wrote:

 ...
 If incorporating this new type, please address also the complication 
 of having two views on the storage allocated for resizable arrays:
 - the "potential" capacity, to which the `length' property currently 
 can grow without the need of allocating more consecutive space
 - the "actual" capacity, which is currently set/get by the `length' 
 property
 
 It is a pity, that the documentation, 
 http://www.digitalmars.com/d/arrays.html#resize,
 illustrates a pattern that can be easily incorporated into the 
 language as a default behaviour:
 - introduce new `length.pot' r/w-property
 - whenever the `length' property exceeds the `length.pot' property 
 double the `length.pot' property and allocate appropriate space
 - issue an error when `length.pot' is decreased below the value of 
 `length'
  
 -manfred


This can be pretty trivially implemented as a user type; if Walter added
implicit casts and, say, opDollar, it'd be nigh indistinguishable from
regular arrays.

Just threw up a quick and dirty version here:
http://www.prowiki.org/wiki4d/wiki.cgi?DanielKeep/snippets (bottom of
the page).

	-- Daniel
Jun 04 2007
prev sibling next sibling parent reply Derek Parnell <derek psych.ward> writes:
On Mon, 04 Jun 2007 02:33:58 -0700, Walter Bright wrote:


 ... we finally hit on the idea of 
 making a resizeable array a different type, say:
 
     T[n]   a;  // static array
     T[]    b;  // dynamic array
     T[new] c;  // resizeable array
 
     a.length = 6;   // error, static array
     b.length = 6;   // error, dynamic array is not resizeable
     c.length = 6;   // ok


Huh? 'static array' used to mean fixed-size array and 'dynamic array' used
to mean 'variable-length array' ... so a dynamic array is not dynamic
anymore? 

So a dynamic array is 'sizeable' but not 'resizable'. In other words, once
its length has been set it can never be changed again? Is that what you are
saying? And is that a compile-time or a run-time check?

If this is what 'resizeable' means for dynamic arrays then nearly all my
dynamic arrays will have to be changed to resizable ones, because I rely on
that feature for lots of things. 

What is the point of having dynmaic arrays now? The difference between them
an static arrays is rather small.


     b = c;          // ok, implicit conversion of resizeable to dynamic


But hang on, you said that b.length isn't allowed to change? Or did you
mean that it can only change if b.ptr also being updated?


 I think this will entail only very rare changes to user code, but will 
 be a big improvement in type safety. 


Not so sure about that ... I'll do some analysis and report back.

-- 
Derek Parnell
Melbourne, Australia
"Justice for David Hicks!"
skype: derek.j.parnell
Jun 04 2007
parent reply Walter Bright <newshound1 digitalmars.com> writes:
Derek Parnell wrote:

 On Mon, 04 Jun 2007 02:33:58 -0700, Walter Bright wrote:
 

 ... we finally hit on the idea of 
 making a resizeable array a different type, say:

     T[n]   a;  // static array
     T[]    b;  // dynamic array
     T[new] c;  // resizeable array

     a.length = 6;   // error, static array
     b.length = 6;   // error, dynamic array is not resizeable
     c.length = 6;   // ok


 
 Huh? 'static array' used to mean fixed-size array


It still does.


 and 'dynamic array' used
 to mean 'variable-length array' ... so a dynamic array is not dynamic
 anymore?


A dynamic array would now mean that its length is not known at compile time.


 So a dynamic array is 'sizeable' but not 'resizable'. In other words, once
 its length has been set it can never be changed again? Is that what you are
 saying?


Yes.


 And is that a compile-time or a run-time check?


Compile time.


 If this is what 'resizeable' means for dynamic arrays then nearly all my
 dynamic arrays will have to be changed to resizable ones, because I rely on
 that feature for lots of things. 


Without looking at your code, I suspect it may be less than you think. I 
thought I was modifying strings all the time, so when switching over to 
const strings, I expected lots and lots of work. Turns out, only rarely 
do I do this.



 What is the point of having dynmaic arrays now? The difference between them
 an static arrays is rather small.


Consider the following:

	alias char[] string;

That alone justifies it! And the difference between static arrays and 
dynamic arrays is very large. For one thing, static arrays are passed by 
value, and dynamic arrays by reference.


     b = c;          // ok, implicit conversion of resizeable to dynamic


 
 But hang on, you said that b.length isn't allowed to change? Or did you
 mean that it can only change if b.ptr also being updated?


I meant that the underlying array cannot be resized through b. b itself 
can have its ptr/length values changed through simple assignment, but 
there will be no realloc happening.


 I think this will entail only very rare changes to user code, but will 
 be a big improvement in type safety. 


 
 Not so sure about that ... I'll do some analysis and report back.
Jun 04 2007
next sibling parent reply BCS <BCS pathlink.com> writes:
Walter Bright wrote:

 Derek Parnell wrote:

 On Mon, 04 Jun 2007 02:33:58 -0700, Walter Bright wrote:

     b = c;          // ok, implicit conversion of resizeable to dynamic



 But hang on, you said that b.length isn't allowed to change? Or did you
 mean that it can only change if b.ptr also being updated?


 
 
 I meant that the underlying array cannot be resized through b. b itself 
 can have its ptr/length values changed through simple assignment, but 
 there will be no realloc happening.
 


so with T[n], .length (all by it's self) is a compile time const, with 
T[] it is an r-value and with T[new] it is an l-value. Is that more or 
less the sum of it?
Jun 04 2007
parent Walter Bright <newshound1 digitalmars.com> writes:
BCS wrote:

 Walter Bright wrote:

 Derek Parnell wrote:

 On Mon, 04 Jun 2007 02:33:58 -0700, Walter Bright wrote:

     b = c;          // ok, implicit conversion of resizeable to dynamic



 But hang on, you said that b.length isn't allowed to change? Or did you
 mean that it can only change if b.ptr also being updated?



 I meant that the underlying array cannot be resized through b. b 
 itself can have its ptr/length values changed through simple 
 assignment, but there will be no realloc happening.


 
 so with T[n], .length (all by it's self) is a compile time const, with 
 T[] it is an r-value and with T[new] it is an l-value. Is that more or 
 less the sum of it?


Yes.
Jun 04 2007
prev sibling parent reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
Walter Bright skrev:


 [...] the difference between static arrays and 
 dynamic arrays is very large. For one thing, static arrays are passed by 
 value, and dynamic arrays by reference.


This sounds intriguing. Does this mean that static arrays will be passed 
by value in D 2.0? Will string literals become dynamic (invariant) 
arrays instead of static too?

/Oskar
Jun 07 2007
parent reply Walter Bright <newshound1 digitalmars.com> writes:
Oskar Linde wrote:

 Walter Bright skrev:
 

 [...] the difference between static arrays and dynamic arrays is very 
 large. For one thing, static arrays are passed by value, and dynamic 
 arrays by reference.


 
 This sounds intriguing. Does this mean that static arrays will be passed 
 by value in D 2.0?


Yes.


 Will string literals become dynamic (invariant) 
 arrays instead of static too?


They'll be invariant static arrays.
Jun 08 2007
next sibling parent Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
Walter Bright skrev:

 Oskar Linde wrote:

 Walter Bright skrev:


 [...] the difference between static arrays and dynamic arrays is very 
 large. For one thing, static arrays are passed by value, and dynamic 
 arrays by reference.


 This sounds intriguing. Does this mean that static arrays will be 
 passed by value in D 2.0?


 
 Yes.


That is wonderful! Another wrinkle ironed out.


 Will string literals become dynamic (invariant) arrays instead of 
 static too?


 
 They'll be invariant static arrays.


Yeah, I got that a few minutes after posting from another post.  My only 
(minor) concern here was the potential performance penalty of passing 
string literals to simple template functions, like

void foo(T)(T x) {...},

but there are plenty of ways to deal with that. For example, since they 
are invariant, I guess they could be passed by reference behind the 
scenes anyway.

/Oskar
Jun 08 2007
prev sibling parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Walter Bright" <newshound1 digitalmars.com> wrote in message 
news:f4b70o$i3t$1 digitalmars.com...

 Oskar Linde wrote:

 They'll be invariant static arrays.


Why wouldn't they be invariant unresizable arrays?  Or do you plan on fixing 
all the special casing stuff that has to be taken into account when using 
string literals in {templates, array literals, AA literals, etc.}?
Jun 08 2007
parent reply Walter Bright <newshound1 digitalmars.com> writes:
Jarrett Billingsley wrote:

 "Walter Bright" <newshound1 digitalmars.com> wrote in message 
 news:f4b70o$i3t$1 digitalmars.com...

 Oskar Linde wrote:

 They'll be invariant static arrays.


 
 Why wouldn't they be invariant unresizable arrays?


Because static arrays can be implicitly cast to unresizable arrays, but 
not vice versa.


 Or do you plan on fixing 
 all the special casing stuff that has to be taken into account when using 
 string literals in {templates, array literals, AA literals, etc.}? 


I don't know what you mean.
Jun 08 2007
parent "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Walter Bright" <newshound1 digitalmars.com> wrote in message >

 Because static arrays can be implicitly cast to unresizable arrays, but 
 not vice versa.


Why would you need it to implicitly cast to a static array?  So you can 
initialize things like "char[4] = "abcd";" ?


 I don't know what you mean.


// cannot implicitly convert expression (["hi","bye"]) of type char[][2] to 
char
// auto a = ["hi", "bye"];

// works
auto a = ["hi"[], "bye"];

int[char[]] aa;

// cannot implicitly convert expression ("bye") of type char[3] to char[2]
//aa = ["hi":1, "bye":2];

// works
aa = ["hi"[]:1, "bye":2];

typeof(T[0]) foo(T...)()
{
    return T[0];
}

// Error: functions cannot return static array char[2]
//foo!("hi")();

// works
foo!("hi"[])();

Templates also have to deal with static array types in completely different 
ways, since they can't be returned and their .init is not the same type as 
them.
Jun 08 2007
prev sibling next sibling parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Walter Bright wrote:

 Now, it turns out that it is very rare for a function to legitimately 
 want to resize a buffer passed to it. So we finally hit on the idea of 
 making a resizeable array a different type, say:
 
    T[n]   a;  // static array
    T[]    b;  // dynamic array
    T[new] c;  // resizeable array
 
    a.length = 6;   // error, static array
    b.length = 6;   // error, dynamic array is not resizeable
    c.length = 6;   // ok
    b = c;          // ok, implicit conversion of resizeable to dynamic
    c = b;          // error
    c = b[0..n];    // error
    b = c[0..n];    // ok, but watch out if c is later resized
    b = c[0..n].dup; // ok, no worries
    c = cast(T[new])b; // ok, but this will be deliberate


What about
	c = a;
?
I have several places where I have functions that follow this pattern:
---
T[] foo(<parameters>, T[] buffer = null) {
     buffer.length = <something>;
     <fill buffer>
     return buffer;
}
---
These are intended to be usable with "buffer" being either a 
stack-allocated static array or a heap-allocated dynamic array. If the 
passed buffer is big enough a slice is returned, otherwise it gets 
enlarged (and possibly reallocated on the heap).
I guess with this proposed modification I'd want to accept and return a 
"T[new]", but will that allow static arrays (stack-allocated) to be 
passed in?
I'd hate to have to write two different functions, one for static arrays 
and slices and one for resizable arrays... (and I'm not fond of the idea 
of extra casts to make it work with a single function)

Also, I often write toString() members of objects (and other functions 
returning strings) like this:
---
char[] toString() {
     auto ret = "prefix";
     foreach (elt; children) {
         ret ~= elt.toString();
         // perhaps append a separator here
     }
     // if separators were appended, remove the last one here
     ret ~= "postfix";
     return ret;
}
---
Will these need to be changed? (probably a .dup after the "prefix" string)
(Since string constants are also static arrays, this is the same basic 
issue as above)


 I think this will entail only very rare changes to user code, but will 
 be a big improvement in type safety. Note that it will *still* possible 
 for array resizing to affect other slices into the same array, but it's 
 far, far less likely to happen inadvertently. The attractiveness of this 
 solution is it nearly completely solves the problem with zero runtime cost.


I think I may need to make quite some changes actually, though the 
changes required to the latter code sample I gave will be minimal.


Another question, will the following be allowed:
---
class Base {
     abstract char[] foo();
}

class Derived : Base {
     override char[new] foo() { assert(0, "Not implemented yet"); }
}
---
?
Jun 04 2007
parent Walter Bright <newshound1 digitalmars.com> writes:
Frits van Bommel wrote:

 Walter Bright wrote:

 Now, it turns out that it is very rare for a function to legitimately 
 want to resize a buffer passed to it. So we finally hit on the idea of 
 making a resizeable array a different type, say:

    T[n]   a;  // static array
    T[]    b;  // dynamic array
    T[new] c;  // resizeable array

    a.length = 6;   // error, static array
    b.length = 6;   // error, dynamic array is not resizeable
    c.length = 6;   // ok
    b = c;          // ok, implicit conversion of resizeable to dynamic
    c = b;          // error
    c = b[0..n];    // error
    b = c[0..n];    // ok, but watch out if c is later resized
    b = c[0..n].dup; // ok, no worries
    c = cast(T[new])b; // ok, but this will be deliberate


 
 What about
     c = a;
 ?


Good question. That'll be allowed. I have a couple misgivings about it, 
though.


 I have several places where I have functions that follow this pattern:
 ---
 T[] foo(<parameters>, T[] buffer = null) {
     buffer.length = <something>;
     <fill buffer>
     return buffer;
 }
 ---
 These are intended to be usable with "buffer" being either a 
 stack-allocated static array or a heap-allocated dynamic array. If the 
 passed buffer is big enough a slice is returned, otherwise it gets 
 enlarged (and possibly reallocated on the heap).
 I guess with this proposed modification I'd want to accept and return a 
 "T[new]", but will that allow static arrays (stack-allocated) to be 
 passed in?


Yes.


 I'd hate to have to write two different functions, one for static arrays 
 and slices and one for resizable arrays... (and I'm not fond of the idea 
 of extra casts to make it work with a single function)
 
 Also, I often write toString() members of objects (and other functions 
 returning strings) like this:
 ---
 char[] toString() {
     auto ret = "prefix";
     foreach (elt; children) {
         ret ~= elt.toString();
         // perhaps append a separator here
     }
     // if separators were appended, remove the last one here
     ret ~= "postfix";
     return ret;
 }
 ---
 Will these need to be changed? (probably a .dup after the "prefix" string)
 (Since string constants are also static arrays, this is the same basic 
 issue as above)


You'd need to rewrite it as:

---
string toString() {
     invariant(char)[new] ret = "prefix";
     foreach (elt; children) {
         ret ~= elt.toString();
         // perhaps append a separator here
     }
     // if separators were appended, remove the last one here
     ret ~= "postfix";
     return ret;
}
---
since the type of "prefix" will be invariant(char)[6];
You'll need to use "string" as a return type, because you'll potentially 
be returning a reference to an immutable string literal, and that must 
be reflected in the type. If you chose to do "prefix".dup, it could be 
written as:

---
string toString() {
     auto ret = "prefix".dup;
     foreach (elt; children) {
         ret ~= elt.toString();
         // perhaps append a separator here
     }
     // if separators were appended, remove the last one here
     ret ~= "postfix";
     return ret;
}
---

and the return type could be either string or char[]. The type of ret 
here will be char[new], as that is what .dup will return.


 I think this will entail only very rare changes to user code, but will 
 be a big improvement in type safety. Note that it will *still* 
 possible for array resizing to affect other slices into the same 
 array, but it's far, far less likely to happen inadvertently. The 
 attractiveness of this solution is it nearly completely solves the 
 problem with zero runtime cost.


 
 I think I may need to make quite some changes actually, though the 
 changes required to the latter code sample I gave will be minimal.
 
 
 Another question, will the following be allowed:
 ---
 class Base {
     abstract char[] foo();
 }
 
 class Derived : Base {
     override char[new] foo() { assert(0, "Not implemented yet"); }
 }
 ---
 ?


Yes, since char[new] can be implicitly converted to char[]. The reverse 
will not work.
Jun 04 2007
prev sibling next sibling parent reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
Walter Bright wrote:


 Now, it turns out that it is very rare for a function to legitimately 
 want to resize a buffer passed to it. So we finally hit on the idea of 
 making a resizeable array a different type, say:


An excellent suggestion. And I'm not only saying that because I have 
suggested this several times myself. :p

The dual resizable array / slice semantics of the old dynamic array have 
several subtle problems, and also considering the fact that slices and 
resizable arrays are two very different beasts that seldom need to be 
mixed makes this a welcome change. I'm glad that introducing separate 
types seems to be relatively painless.


 
    T[n]   a;  // static array
    T[]    b;  // dynamic array
    T[new] c;  // resizeable array


I'd propose a different nomenclature:

T[n]   a;  // static array
T[]    b;  // (array) slice
T[new] c;  // dynamic array

I also agree with others that there are better alternatives to "new". 
T[*] is my favorite.


 So, if our function parameter is typed as T[], we know there isn't going 
 to be any monkey business going on in that function with our other 
 slices. If it's T[new], we know we need to take a hard look at it.


It will still be a bit weird appending to or resizing a T[new] function 
argument that isn't passed by reference... Actually it will most likely 
be a bug. It would be *very* neat getting that fixed too.

In 99.9 cases of 100 where one passes a T[new] as a function argument, 
one wants the argument to be passed by reference. The remaining 0.1 
cases have obvious workarounds. So... Is there any way T[new] somehow 
could be made a reference type? Just like T[U] has become.

E.g. it would be nice if the following just worked:

void appendTo(T[new] arr, T val) { arr ~= val; }

Without the problem of the user accidentally forgetting to pass arr by 
reference.

Short version: You always want to pass ref T[new]. Forgetting ref is 
probably a bug, but is silently accepted by the compiler. Ergo, ref 
should be the default. :)

/Oskar
Jun 04 2007
parent reply Walter Bright <newshound1 digitalmars.com> writes:
Oskar Linde wrote:

 Walter Bright wrote:
 

 Now, it turns out that it is very rare for a function to legitimately 
 want to resize a buffer passed to it. So we finally hit on the idea of 
 making a resizeable array a different type, say:


 
 An excellent suggestion. And I'm not only saying that because I have 
 suggested this several times myself. :p


Can you point me to the posting(s)? You should get the credit for being 
first.


    T[n]   a;  // static array
    T[]    b;  // dynamic array
    T[new] c;  // resizeable array


 
 I'd propose a different nomenclature:
 
 T[n]   a;  // static array
 T[]    b;  // (array) slice
 T[new] c;  // dynamic array


I like "resizeable" array because it is pretty clear what it does.


 I also agree with others that there are better alternatives to "new". 
 T[*] is my favorite.


Looks like C99's VLA.


 Short version: You always want to pass ref T[new]. Forgetting ref is 
 probably a bug, but is silently accepted by the compiler. Ergo, ref 
 should be the default. :)


Frits has posted a realistic use case that argues it shouldn't be.
Jun 04 2007
next sibling parent reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
Walter Bright skrev:

 Oskar Linde wrote:

 Walter Bright wrote:


 Now, it turns out that it is very rare for a function to legitimately 
 want to resize a buffer passed to it. So we finally hit on the idea 
 of making a resizeable array a different type, say:


 An excellent suggestion. And I'm not only saying that because I have 
 suggested this several times myself. :p


 
 Can you point me to the posting(s)? You should get the credit for being 
 first.


Looking back at some of my posts, I don't think I ever made a public 
newsgroup post actually suggesting D change in this way... For the 
reason that I never dared to believe such a change could ever happen. I 
found some rants on the topic of the separate semantics of slices and 
resizable arrays, but it is hardly posts I feel very proud of. :p

http://www.digitalmars.com/d/archives/digitalmars/D/bugs/bug_or_feature_9420.html#N9425
http://www.digitalmars.com/d/archives/digitalmars/D/learn/3521.html#N3593
http://www.digitalmars.com/d/archives/digitalmars/D/learn/3354.html#N3357


    T[n]   a;  // static array
    T[]    b;  // dynamic array
    T[new] c;  // resizeable array


 I'd propose a different nomenclature:

 T[n]   a;  // static array
 T[]    b;  // (array) slice
 T[new] c;  // dynamic array


 
 I like "resizeable" array because it is pretty clear what it does. 


Ok, another suggestion: (Sneakily injecting the [*] too... :)

T[n]   a;  // static array
T[]    b;  // array view
T[*]   c;  // dynamic array

IMHO, "array view" is a better description than "dynamic array". But it 
depends on your point of view, of course.


 I also agree with others that there are better alternatives to "new". 
 T[*] is my favorite.


 
 Looks like C99's VLA.


Afaik, it is only used for vla _prototypes_ in C99, and is that really a 
problem? It is not like the compiler won't warn you if you write:

extern(C) void foo(int,int[*]);

right? And I don't really see how using T[*] for resizable arrays in D 
is any different from using T[] for non-resizable ones -- T[] also means 
something slightly different in C99.


 Short version: You always want to pass ref T[new]. Forgetting ref is 
 probably a bug, but is silently accepted by the compiler. Ergo, ref 
 should be the default. :)


 
 Frits has posted a realistic use case that argues it shouldn't be.


I presume you mean:

T[] foo(<parameters>, T[] buffer = null) {
     buffer.length = <something>;
     <fill buffer>
     return buffer;
}

"""These are intended to be usable with "buffer" being either a 
stack-allocated static array or a heap-allocated dynamic array. If the 
passed buffer is big enough a slice is returned, otherwise it gets 
enlarged (and possibly reallocated on the heap)."""

The buffer.length = <something>; in the use case might be a neat trick, 
but is it really that essential? Consider the rewrite: (T[] means 
non-resizable dynamic array)

T[] foo(<parameters>, T[] buffer = null)
{
     T[] ret = buffer.length >= needed_capacity
             ? buffer[0..needed_capacity]
             : new T[needed_capacity];
     <fill ret>
     return ret;
}

The only advantage of the original code is that it might be able to 
squeeze a few extra bytes out of a buffer that for some reason would not 
be at its full capacity. But is that really a feature? I would 
personally not have expected this assert to potentially fail:

T[] buffer = new T[1000];
T[] ret = foo(buffer);
assert(ret.length <= buffer.length || ret.ptr != buffer.ptr);

So I don't really see what you gain from being able to pass a resizable 
array by value and then change its length. At least not compared to what 
you gain by not being able to do that.

/Oskar
Jun 04 2007
parent Walter Bright <newshound1 digitalmars.com> writes:
Oskar Linde wrote:

 The buffer.length = <something>; in the use case might be a neat trick, 
 but is it really that essential? Consider the rewrite: (T[] means 
 non-resizable dynamic array)
 
 T[] foo(<parameters>, T[] buffer = null)
 {
     T[] ret = buffer.length >= needed_capacity
             ? buffer[0..needed_capacity]
             : new T[needed_capacity];
     <fill ret>
     return ret;
 }


You're probably right with that.
Jun 04 2007
prev sibling parent reply Derek Parnell <derek psych.ward> writes:
On Mon, 04 Jun 2007 10:45:09 -0700, Walter Bright wrote:


    T[n]   a;  // static array
    T[]    b;  // dynamic array
    T[new] c;  // resizeable array


 
 I'd propose a different nomenclature:
 
 T[n]   a;  // static array
 T[]    b;  // (array) slice
 T[new] c;  // dynamic array


 
 I like "resizeable" array because it is pretty clear what it does.


I think you are quite wrong Walter. The new interpretation of 'x[]' is
almost identical to what we used to think of as a slice. And the
interpreatation of 'x[new]' is exactly what used to be known as a dynamic
array. 

Your change will effect all code immediately whereas reversing the
(changed) meaning of '[]' and '[new]' to mean 'resizable' and 'slice' will
allow coders to change their coding over time. Unless of course that's what
you are trying to do ...


-- 
Derek Parnell
Melbourne, Australia
"Justice for David Hicks!"
skype: derek.j.parnell
Jun 04 2007
next sibling parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Derek Parnell wrote:

 On Mon, 04 Jun 2007 10:45:09 -0700, Walter Bright wrote:
 

    T[n]   a;  // static array
    T[]    b;  // dynamic array
    T[new] c;  // resizeable array


 I'd propose a different nomenclature:

 T[n]   a;  // static array
 T[]    b;  // (array) slice
 T[new] c;  // dynamic array


 I like "resizeable" array because it is pretty clear what it does.


 
 I think you are quite wrong Walter. The new interpretation of 'x[]' is
 almost identical to what we used to think of as a slice. And the
 interpreatation of 'x[new]' is exactly what used to be known as a dynamic
 array. 
 
 Your change will effect all code immediately whereas reversing the
 (changed) meaning of '[]' and '[new]' to mean 'resizable' and 'slice' will
 allow coders to change their coding over time. Unless of course that's what
 you are trying to do ...


Except that the non-resizable arrays will be more common in use than the 
fully dynamic ones. Thus, the resizable are a special case and deserve 
special syntax. *Except* that it's similar to const-by default, while D 
will use mutable-by default.

Long story short, IMHO, it makes more sense to do const-by-default 
everywhere, just as using non-resizable arrays by default. But what 
you're suggesting will probably be more consistent with the planned 
constness facilities. And as I understand it, their main selling point 
over const-by-default is the smaller number of changes required in 
existing code.


-- 
Tomasz Stachowiak
http://h3.team0xf.com/
h3/h3r3tic on #D freenode
Jun 04 2007
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Tom S wrote:

 Derek Parnell wrote:

 On Mon, 04 Jun 2007 10:45:09 -0700, Walter Bright wrote:


    T[n]   a;  // static array
    T[]    b;  // dynamic array
    T[new] c;  // resizeable array


 I'd propose a different nomenclature:

 T[n]   a;  // static array
 T[]    b;  // (array) slice
 T[new] c;  // dynamic array


 I like "resizeable" array because it is pretty clear what it does.


 I think you are quite wrong Walter. The new interpretation of 'x[]' is
 almost identical to what we used to think of as a slice. And the
 interpreatation of 'x[new]' is exactly what used to be known as a dynamic
 array.
 Your change will effect all code immediately whereas reversing the
 (changed) meaning of '[]' and '[new]' to mean 'resizable' and 'slice' 
 will
 allow coders to change their coding over time. Unless of course that's 
 what
 you are trying to do ...


 
 Except that the non-resizable arrays will be more common in use than the 
 fully dynamic ones. Thus, the resizable are a special case and deserve 
 special syntax. *Except* that it's similar to const-by default, while D 
 will use mutable-by default.


I think it really depends.  I can imagine for a lot of folks it will 
basically boil down to parameter vs. local variable.  If it's a 
parameter you want slice-semantics, if it's a local variable you want 
resizeable semantics.  A quick grep through my code gave me about 400 
lines where I used '~='.  That doesn't tell you all that much, but it 
does give something close to an upper bound.  For each of those lines a 
T[] somewhere is going to need to be changed to a T[new] (or whatever). 
The number could be less if I'm using auto.  But I also use
    T[] x; x.length = N;
a lot.  Those will need to be changed too.

On the other hand "[]" appears about 1700 times.  That says to me that 
arrays that I don't resize (whether in paramter or not) are probably 
significantly more common than those I do.  But either way it's a 
significant amount of code to change.

--bb
Jun 04 2007
prev sibling parent gareis <dhasenan gmail.com> writes:
Derek Parnell wrote:

 On Mon, 04 Jun 2007 10:45:09 -0700, Walter Bright wrote:
 

    T[n]   a;  // static array
    T[]    b;  // dynamic array
    T[new] c;  // resizeable array


 I'd propose a different nomenclature:

 T[n]   a;  // static array
 T[]    b;  // (array) slice
 T[new] c;  // dynamic array


 I like "resizeable" array because it is pretty clear what it does.


 
 I think you are quite wrong Walter. The new interpretation of 'x[]' is
 almost identical to what we used to think of as a slice. And the
 interpreatation of 'x[new]' is exactly what used to be known as a dynamic
 array. 
 
 Your change will effect all code immediately whereas reversing the
 (changed) meaning of '[]' and '[new]' to mean 'resizable' and 'slice' will
 allow coders to change their coding over time. Unless of course that's what
 you are trying to do ...
 
 


There's another issue. Function parameters cover most of the ground that 
this does, if not more. There's already a set of keywords that can be 
used here with the same meaning.

C++ has T const * as a single-allocate array and T* as the resizeable 
form (albeit only with realloc). It'd be a bit ugly, but D could do T 
const[] or T const([]) for the single-allocate array and T[] for the 
resizeable form.

T const[] also addresses the above issue of converting code. I'm working 
on a MUD currently, and since it's a text-based game just about 
everything involved is string catenation. Either I'd suddenly grow to 
love the auto keyword (but specifying types manually is a comforting 
sanity check), or I'd have to convert almost every string to be mutable.

Walter, you said already that you couldn't think of many cases where it 
would be useful to have an immutable array of mutable elements. But now 
it seems that not only are you implementing that, but you're making it 
the default. I'm confused. Why are you doing it?

I agree it's useful to have these slice arrays, but it's an edge case. 
Please don't require extra keywords to get to the common case.
Jun 04 2007
prev sibling next sibling parent reply Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:

 
 (The problem is if I pass a slice to a function, and then that function 
 reallocates the slice by changing the length or appending to it, it can 
 affect other slices into the same data in very hard-to-explain ways.


I'm not sure I understand how a reallocation could affect other slices 
into the same data.  If a reallocation occurs, that reallocation will be 
into entirely new memory, provided the slice doesn't start at the head 
of a memory block.  Is it the condition I just mentioned that's a 
problem?  If so, I suppose it is one way to trick the compiler into 
thinking the reference no longer refers to const data, when in fact it 
does.  If not, could you point me in the right direction?


 Now, it turns out that it is very rare for a function to legitimately 
 want to resize a buffer passed to it. So we finally hit on the idea of 
 making a resizeable array a different type, say:
 
    T[n]   a;  // static array
    T[]    b;  // dynamic array
    T[new] c;  // resizeable array


Well, I think it is very rare for a function to want to resize an array 
that isn't passed by reference.  My first reaction would be to disallow 
resizing of non-ref array parameters entirely.  Since resizing may occur 
in place, this could be seen as a mutating operation on the underlying 
data.  If the user wants to resize a non-ref array parameter for local 
use he use assign ops and such.

I think this may be related to a question I've been avoiding until now: 
how will the new const features interact with struct and class member 
function use?  Will it always be legal to call member functions of const 
objects?  Will it never be legal?  Or perhaps there will be a way to 
label some operations as non-modifying (which suggests logical const)?


Sean
Jun 04 2007
parent reply Walter Bright <newshound1 digitalmars.com> writes:
Sean Kelly wrote:

 Walter Bright wrote:

 (The problem is if I pass a slice to a function, and then that 
 function reallocates the slice by changing the length or appending to 
 it, it can affect other slices into the same data in very 
 hard-to-explain ways.


 
 I'm not sure I understand how a reallocation could affect other slices 
 into the same data.  If a reallocation occurs, that reallocation will be 
 into entirely new memory, provided the slice doesn't start at the head 
 of a memory block.  Is it the condition I just mentioned that's a 
 problem?  If so, I suppose it is one way to trick the compiler into 
 thinking the reference no longer refers to const data, when in fact it 
 does.  If not, could you point me in the right direction?


Given:

	int[] a = new int[7];
	int[] b = a[1..6];
	b[1] = 2;   // writes through to a[2]
	b.length = 4;
	b[1] = 3;   // writes through to a[2]
	b.length = 6;
	b[1] = 4;   // does not write through to a[2]


 Now, it turns out that it is very rare for a function to legitimately 
 want to resize a buffer passed to it. So we finally hit on the idea of 
 making a resizeable array a different type, say:

    T[n]   a;  // static array
    T[]    b;  // dynamic array
    T[new] c;  // resizeable array


 
 Well, I think it is very rare for a function to want to resize an array 
 that isn't passed by reference.  My first reaction would be to disallow 
 resizing of non-ref array parameters entirely.  Since resizing may occur 
 in place, this could be seen as a mutating operation on the underlying 
 data.  If the user wants to resize a non-ref array parameter for local 
 use he use assign ops and such.


That was my first reaction too, but Frits posted a reasonable use case.



 I think this may be related to a question I've been avoiding until now: 
 how will the new const features interact with struct and class member 
 function use?  Will it always be legal to call member functions of const 
 objects?  Will it never be legal?  Or perhaps there will be a way to 
 label some operations as non-modifying (which suggests logical const)?


You'll only be able to call const member functions on const objects.
Jun 04 2007
next sibling parent reply Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:

 Sean Kelly wrote:

 Walter Bright wrote:

 (The problem is if I pass a slice to a function, and then that 
 function reallocates the slice by changing the length or appending to 
 it, it can affect other slices into the same data in very 
 hard-to-explain ways.


 I'm not sure I understand how a reallocation could affect other slices 
 into the same data.  If a reallocation occurs, that reallocation will 
 be into entirely new memory, provided the slice doesn't start at the 
 head of a memory block.  Is it the condition I just mentioned that's a 
 problem?  If so, I suppose it is one way to trick the compiler into 
 thinking the reference no longer refers to const data, when in fact it 
 does.  If not, could you point me in the right direction?


 
 Given:
 
     int[] a = new int[7];
     int[] b = a[1..6];
     b[1] = 2;   // writes through to a[2]
     b.length = 4;
     b[1] = 3;   // writes through to a[2]
     b.length = 6;
     b[1] = 4;   // does not write through to a[2]


Okay, so it is related to non-reallocating changes.  Thanks.


 Now, it turns out that it is very rare for a function to legitimately 
 want to resize a buffer passed to it. So we finally hit on the idea 
 of making a resizeable array a different type, say:

    T[n]   a;  // static array
    T[]    b;  // dynamic array
    T[new] c;  // resizeable array


 Well, I think it is very rare for a function to want to resize an 
 array that isn't passed by reference.  My first reaction would be to 
 disallow resizing of non-ref array parameters entirely.  Since 
 resizing may occur in place, this could be seen as a mutating 
 operation on the underlying data.  If the user wants to resize a 
 non-ref array parameter for local use he use assign ops and such.


 
 That was my first reaction too, but Frits posted a reasonable use case.


Do you mean:

     T[] foo(<parameters>, T[] buffer = null) {
         buffer.length = <something>;
         <fill buffer>
         return buffer;
     }

Wouldn't it work if changed to this:

     T[] foo(<parameters>, T[] buffer = null) {
         if( buffer.length < newSize )
             buffer = new T[newSize];
         <fill buffer>
         return buffer;
     }

I think it's arguable that the second form is also more meaningful given 
that the array is not passed by reference.


Sean
Jun 04 2007
parent reply Sean Kelly <sean f4.ca> writes:
Sean Kelly wrote:

 Walter Bright wrote:

 Sean Kelly wrote:

 Well, I think it is very rare for a function to want to resize an 
 array that isn't passed by reference.  My first reaction would be to 
 disallow resizing of non-ref array parameters entirely.  Since 
 resizing may occur in place, this could be seen as a mutating 
 operation on the underlying data.  If the user wants to resize a 
 non-ref array parameter for local use he use assign ops and such.


 That was my first reaction too, but Frits posted a reasonable use case.


 
 Do you mean:
 
     T[] foo(<parameters>, T[] buffer = null) {
         buffer.length = <something>;
         <fill buffer>
         return buffer;
     }
 
 Wouldn't it work if changed to this:
 
     T[] foo(<parameters>, T[] buffer = null) {
         if( buffer.length < newSize )
             buffer = new T[newSize];
         <fill buffer>
         return buffer;
     }
 
 I think it's arguable that the second form is also more meaningful given 
 that the array is not passed by reference.


Given the above, am I correct in assuming that it will only be illegal 
to resize an array via .length if the underlying data is const?  If the 
data is not const then it seems completely legitimate to resize the 
supplied array, even if doing so means an in-place expansion.


Sean
Jun 05 2007
parent reply Walter Bright <newshound1 digitalmars.com> writes:
Sean Kelly wrote:

 Given the above, am I correct in assuming that it will only be illegal 
 to resize an array via .length if the underlying data is const?  If the 
 data is not const then it seems completely legitimate to resize the 
 supplied array, even if doing so means an in-place expansion.


Making the referred to data const does not inhibit resizing, because 
resizing does not change the referred to data.

The key to understanding dynamic arrays is understanding their 
representation. Dynamic arrays of const data are like a C++ struct 
defined as:

struct DynamicArray
{
	size_t length;
	const char *ptr;
}

Here, I can change .length and .ptr EVEN THOUGH the data being pointed 
to is const.
Jun 06 2007
parent reply Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:

 Sean Kelly wrote:

 Given the above, am I correct in assuming that it will only be illegal 
 to resize an array via .length if the underlying data is const?  If 
 the data is not const then it seems completely legitimate to resize 
 the supplied array, even if doing so means an in-place expansion.


 
 Making the referred to data const does not inhibit resizing, because 
 resizing does not change the referred to data.
 
 The key to understanding dynamic arrays is understanding their 
 representation. Dynamic arrays of const data are like a C++ struct 
 defined as:
 
 struct DynamicArray
 {
     size_t length;
     const char *ptr;
 }
 
 Here, I can change .length and .ptr EVEN THOUGH the data being pointed 
 to is const.


Okay, that makes sense.  So I'm not sure I entirely understand the 
problem with resizing even mutable array in place.  Could this just be 
an instance where documentation is indeed sufficient?  I can't think of 
a situation where I would actually pass a slice of a buffer to a routine 
that may grow that buffer when writing to it--it just doesn't make any 
sense from a use perspective.  Is this something that we really need to 
add const features to check?


Sean
Jun 06 2007
parent reply Reiner Pope <some address.com> writes:
Sean Kelly wrote:
  > Okay, that makes sense.  So I'm not sure I entirely understand the

 problem with resizing even mutable array in place.  Could this just be 
 an instance where documentation is indeed sufficient?  I can't think of 
 a situation where I would actually pass a slice of a buffer to a routine 
 that may grow that buffer when writing to it--it just doesn't make any 
 sense from a use perspective.  Is this something that we really need to 
 add const features to check?


I don't know if this helps, but currently the following code behaves 
unexpectedly with version=bad


 import std.stdio;
 
 void main()
 {
     char[] data = "1 50.0 60".dup;
 
     writefln( data[0..1].withDecimals() );
     writefln( data );                      // with version=bad prints "1.00.0
60" instead of "1 50.0 60"
     writefln( data[2..6].withDecimals() );
     writefln( data[7..$].withDecimals() );
 }
 
 char[] withDecimals(char[] num)
 {
     foreach (i, c; num)
         if (c == '.')
             return num;
 
 version(bad)
 {
     num ~= ".0";
     return num;
 }
 else
 {
     return (num ~ ".0");
 }
 
 }      


I'm not sure what the suggested rewrite of this would be. To avoid 
unnecessary dup'ing, perhaps:


 
 private char[new] withDecimals(char[new] num, bool needsDup)
 {
     foreach (i, c; num)
         if (c == '.')
             return num;
 
     if (needsDup)
         num = num.dup;
     num ~= ".0";
     return num;
 }
 
 char[new] withDecimals(char[new] num)
 {
     return withDecimals(num, false);
 }
 
 char[] withDecimals(char[] num)
 {
     return withDecimals(cast(char[new])num, true)
 }
  


    -- Reiner
Jun 06 2007
parent Reiner Pope <some address.com> writes:
Reiner Pope wrote:

 I'm not sure what the suggested rewrite of this would be. 


Actually, it would make more sense to template it:


 char[new=IsNew] withDecimals(bool IsNew)(char[new=IsNew] num)
 {
     foreach (i, c; num)
         if (c == '.')
             return num;
 
     char[new] newNum;
     static if (IsNew)
         newNum = num;
     else
         newNum = num.dup;
 
     newNum ~= ".0";
     return newNum;
 }



   -- Reiner
Jun 07 2007
prev sibling parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Walter Bright wrote:

 Sean Kelly wrote:

 Walter Bright wrote:

 (The problem is if I pass a slice to a function, and then that 
 function reallocates the slice by changing the length or appending to 
 it, it can affect other slices into the same data in very 
 hard-to-explain ways.


 I'm not sure I understand how a reallocation could affect other slices 
 into the same data.  If a reallocation occurs, that reallocation will 
 be into entirely new memory, provided the slice doesn't start at the 
 head of a memory block.  Is it the condition I just mentioned that's a 
 problem?  If so, I suppose it is one way to trick the compiler into 
 thinking the reference no longer refers to const data, when in fact it 
 does.  If not, could you point me in the right direction?


 
 Given:
 
     int[] a = new int[7];
     int[] b = a[1..6];
     b[1] = 2;   // writes through to a[2]
     b.length = 4;
     b[1] = 3;   // writes through to a[2]
     b.length = 6;
     b[1] = 4;   // does not write through to a[2]
 


So, is that the problem we are trying to solve? Why not just simply make 
it so that setting .length *allways* creates a new array?

Hum, now that I think about it, this may not only be a better solution, 
it may be the *only* real solution. Even, with the new 
resizable/unresizable array proposal you can have the same problem as above:

   int[new] a = new int[7];
   int[new] b = a;
   b.length = 6;

   b[1] = 2;   // writes through to a[1]
   b.length = 4;
   b[1] = 3;   // writes through to a[1]
   b.length = 10;
   b[1] = 4;   // does not write through to a[1]

Why does this problem exist? Because, setting an array length may or may 
not create a new array, and there isn't a way to know which will happen. 
  Well, in that code segment we can see when it will resize, but we 
can't know in the general case (like when we receive an array as a 
function parameter). This makes setting .length as very unsafe 
operation, if not plain *broken*.

(Oskar, I would particularly like to hear your opinion on this)

-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Jun 09 2007
next sibling parent Deewiant <deewiant.doesnotlike.spam gmail.com> writes:
Bruno Medeiros wrote:

   int[new] a = new int[7];
   int[new] b = a;
   b.length = 6;
 
   b[1] = 2;   // writes through to a[1]
   b.length = 4;
   b[1] = 3;   // writes through to a[1]
   b.length = 10;
   b[1] = 4;   // does not write through to a[1]
 
 Why does this problem exist? Because, setting an array length may or may
 not create a new array, and there isn't a way to know which will happen.
 Well, in that code segment we can see when it will resize, but we can't
 know in the general case (like when we receive an array as a function
 parameter). This makes setting .length as very unsafe operation, if not
 plain *broken*.
 


There could perhaps be an internal flag in every array, initially set to false.
It would be set in the b = a assignment, thus making it known that b is an alias
to a. Then, when b.length is modified, a new array is created and the flag is
unset.

I'm not quite sure how robust this would be, but having .length changeable
without creating a new array is just too handy to give up. Otherwise, we'd have
to use realloc() to achieve the same effect.

The loss here is 1 bit of .length or 1 byte in the array struct for the flag,
and the overhead of having to check it whenever .length is modified.

Of course, the simplest solution is simply to say that modification of .length
for aliased arrays is undefined behaviour.

-- 
Remove ".doesnotlike.spam" from the mail address.
Jun 09 2007
prev sibling parent reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
Bruno Medeiros skrev:

 Walter Bright wrote:

 Sean Kelly wrote:

 Walter Bright wrote:

 (The problem is if I pass a slice to a function, and then that 
 function reallocates the slice by changing the length or appending 
 to it, it can affect other slices into the same data in very 
 hard-to-explain ways.


 I'm not sure I understand how a reallocation could affect other 
 slices into the same data.  If a reallocation occurs, that 
 reallocation will be into entirely new memory, provided the slice 
 doesn't start at the head of a memory block.  Is it the condition I 
 just mentioned that's a problem?  If so, I suppose it is one way to 
 trick the compiler into thinking the reference no longer refers to 
 const data, when in fact it does.  If not, could you point me in the 
 right direction?


 Given:

     int[] a = new int[7];
     int[] b = a[1..6];
     b[1] = 2;   // writes through to a[2]
     b.length = 4;
     b[1] = 3;   // writes through to a[2]
     b.length = 6;
     b[1] = 4;   // does not write through to a[2]


 
 So, is that the problem we are trying to solve? Why not just simply make 
 it so that setting .length *allways* creates a new array?


Not really an option. That would make ~= O(n^2) instead of O(n).



 Hum, now that I think about it, this may not only be a better solution, 
 it may be the *only* real solution. Even, with the new 
 resizable/unresizable array proposal you can have the same problem as 
 above:
 
   int[new] a = new int[7];
   int[new] b = a;
   b.length = 6;
 
   b[1] = 2;   // writes through to a[1]
   b.length = 4;
   b[1] = 3;   // writes through to a[1]
   b.length = 10;
   b[1] = 4;   // does not write through to a[1]
 
 Why does this problem exist? Because, setting an array length may or may 
 not create a new array, and there isn't a way to know which will happen. 
  Well, in that code segment we can see when it will resize, but we can't 
 know in the general case (like when we receive an array as a function 
 parameter). This makes setting .length as very unsafe operation, if not 
 plain *broken*.


That's why my suggestion was making T[new] a reference type instead of a 
value type, just like T[U] has become.

The associative array used to have a similar issue. Previously (before D 
0.151):

int[int] a = ...;
int[int] b = a;
b[0] = 0;

could potentially corrupt a...


And an analogue for todays dynamic array:

int[] a = ...;
int[] b = a;
b.length = 1;
b ~= ...;

will corrupt a.


The solution would be identical: Make the resizable array a reference 
type. Todays value type behavior for dynamic arrays are perfect for 
slices, just not for resizable arrays.

Another option, if one wishes to resolve the above issues and have 
T[new] remain a value type, would be to insert an implicit .dup on 
assignment for T[new]. That way, there would never be two resizable 
arrays sharing the same ptr.

/Oskar
Jun 09 2007
next sibling parent Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
Oskar Linde skrev:


 Not really an option. That would make ~= O(n^2) instead of O(n).


Ehm, I mean O(n) instead of O(1) of course.

/Oskar
Jun 09 2007
prev sibling parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Oskar Linde wrote:

 Bruno Medeiros skrev:

 Walter Bright wrote:

 Sean Kelly wrote:

 Walter Bright wrote:

 (The problem is if I pass a slice to a function, and then that 
 function reallocates the slice by changing the length or appending 
 to it, it can affect other slices into the same data in very 
 hard-to-explain ways.


 I'm not sure I understand how a reallocation could affect other 
 slices into the same data.  If a reallocation occurs, that 
 reallocation will be into entirely new memory, provided the slice 
 doesn't start at the head of a memory block.  Is it the condition I 
 just mentioned that's a problem?  If so, I suppose it is one way to 
 trick the compiler into thinking the reference no longer refers to 
 const data, when in fact it does.  If not, could you point me in the 
 right direction?


 Given:

     int[] a = new int[7];
     int[] b = a[1..6];
     b[1] = 2;   // writes through to a[2]
     b.length = 4;
     b[1] = 3;   // writes through to a[2]
     b.length = 6;
     b[1] = 4;   // does not write through to a[2]


 So, is that the problem we are trying to solve? Why not just simply 
 make it so that setting .length *allways* creates a new array?


 
 Not really an option. That would make ~= O(n^2) instead of O(n).
 
 


Hum, didn't recall that. However, I still wouldn't say it's not an 
option. You're asking to choose between performance (significant only in 
some cases, like realloc'ing in loops) and correctness/"safeness". 
Safeness because length setting is not safe in the general case, but 
only if you know who and how the array was allocated, and also that no 
other references to it exist (in the case you are increasing the 
length). It seems to me that it should be left to the compiler, through 
code analysis, whether the in-place realloc optimization can be safely 
performed or not (i.e., without changing program semantics).
However, since this would take quite some work to implement in the 
compiler, and also since some people may like to know for sure if their 
optimization is implemented or not, we could have a syntax (alternative 
to setting the length), that would do an inplace realloc. It could be 
another property (ar.inlength = 42), or simply a method 
(ar.realloc(42)), or whatever other syntax.
This would mean that concatenation operators would always dup the array, 
so when you would want to resize inplace you couldn't use the 
concatenation operators. That would be, I think, the only difference 
versus the two array types solution. But given the rarity of inplace 
resizing, does not being able to use the concatenation operators justify 
adding a new array type to the language?



 Hum, now that I think about it, this may not only be a better 
 solution, it may be the *only* real solution. Even, with the new 
 resizable/unresizable array proposal you can have the same problem as 
 above:

   int[new] a = new int[7];
   int[new] b = a;
   b.length = 6;

   b[1] = 2;   // writes through to a[1]
   b.length = 4;
   b[1] = 3;   // writes through to a[1]
   b.length = 10;
   b[1] = 4;   // does not write through to a[1]

 Why does this problem exist? Because, setting an array length may or 
 may not create a new array, and there isn't a way to know which will 
 happen.  Well, in that code segment we can see when it will resize, 
 but we can't know in the general case (like when we receive an array 
 as a function parameter). This makes setting .length as very unsafe 
 operation, if not plain *broken*.


 
 That's why my suggestion was making T[new] a reference type instead of a 
 value type, just like T[U] has become.
 
 The associative array used to have a similar issue. Previously (before D 
 0.151):
 
 int[int] a = ...;
 int[int] b = a;
 b[0] = 0;
 
 could potentially corrupt a...
 
 
 And an analogue for todays dynamic array:
 
 int[] a = ...;
 int[] b = a;
 b.length = 1;
 b ~= ...;
 
 will corrupt a.
 
 
 The solution would be identical: Make the resizable array a reference 
 type. Todays value type behavior for dynamic arrays are perfect for 
 slices, just not for resizable arrays.
 
 Another option, if one wishes to resolve the above issues and have 
 T[new] remain a value type, would be to insert an implicit .dup on 
 assignment for T[new]. That way, there would never be two resizable 
 arrays sharing the same ptr.
 
 /Oskar


Yeah, I guess those two would also be solutions, although I don't see 
right now if there could be some other implications with those usages.

But in any case, even having two array kinds, and whatever the way the 
resizable array kind works, why do the non-resizable arrays need to be 
non-resizable at all? They could be resizable, but having the resize 
operation always allocate a new array (and consequently also allow 
concatenation). You gain language functionality and lose *nothing*.

-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Jun 10 2007
prev sibling next sibling parent reply Ary Manzana <ary esperanto.org.ar> writes:
Walter Bright escribió:

 
    T[n]   a;  // static array
    T[]    b;  // dynamic array
    T[new] c;  // resizeable array
 
    a.length = 6;   // error, static array
    b.length = 6;   // error, dynamic array is not resizeable
    c.length = 6;   // ok
    b = c;          // ok, implicit conversion of resizeable to dynamic
    c = b;          // error
    c = b[0..n];    // error
    b = c[0..n];    // ok, but watch out if c is later resized
    b = c[0..n].dup; // ok, no worries
    c = cast(T[new])b; // ok, but this will be deliberate


I don't understand how dynamic arrays work with this change.

T[] b;        // b is a dynamic array of size... ???
b.length = 6; // error, dynamic array is not resizeable ????????

So maybe this should be:

T[] b = new T[6]; // ... of size 6, and 6 can
                   // be replaced with a dynamic variable

Is this the intention of it?

I've only wrote one program in D, and I used dynamic arrays as lists 
(AKA ArrayList in Java). So I guess my program will break with this 
change, because I can't concatenate anymore. Maybe I've been using 
dynamic arrays in the wrong way?
Jun 04 2007
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Ary Manzana wrote:

 Walter Bright escribió:

    T[n]   a;  // static array
    T[]    b;  // dynamic array
    T[new] c;  // resizeable array

    a.length = 6;   // error, static array
    b.length = 6;   // error, dynamic array is not resizeable
    c.length = 6;   // ok
    b = c;          // ok, implicit conversion of resizeable to dynamic
    c = b;          // error
    c = b[0..n];    // error
    b = c[0..n];    // ok, but watch out if c is later resized
    b = c[0..n].dup; // ok, no worries
    c = cast(T[new])b; // ok, but this will be deliberate


 
 I don't understand how dynamic arrays work with this change.
 
 T[] b;        // b is a dynamic array of size... ???
 b.length = 6; // error, dynamic array is not resizeable ????????
 
 So maybe this should be:
 
 T[] b = new T[6]; // ... of size 6, and 6 can
                   // be replaced with a dynamic variable
 
 Is this the intention of it?


Yep, I'm pretty sure that's what you'll have to do for a 
*non*-resizeable array.  On the other hand if you want to be able to 
resize (using Walter's not-so-popular syntax):

T[new] b;
b.length = 6;


 I've only wrote one program in D, and I used dynamic arrays as lists 
 (AKA ArrayList in Java). So I guess my program will break with this 
 change, because I can't concatenate anymore. Maybe I've been using 
 dynamic arrays in the wrong way?  


Nope, the way you've been using them is fine.  But to get safer slices, 
something's got to change.  And since not resizing is less common than 
resizing, it makes more sense to change the syntax for the resizeable 
arrays.

--bb
Jun 04 2007
prev sibling next sibling parent reply Sean Kelly <sean f4.ca> writes:
It just occurred to me this morning that I may have missed something 
regarding the proposed const changes.  Given the following D 1.0 code, 
can someone tell me whether or how it will change in D 2.0?

     void alter( char[] str )
     {
         str[0] = 'x';
     }

     char[] buf = "abc".dup;

     alter( buf );
     alter( buf[1 .. $] );

     printf( "%.*s\n", buf ); // should print "xxc"



Sean
Jun 05 2007
parent reply Brad Roberts <braddr puremagic.com> writes:
I believe that code would not need to change to retain existing behavior.

The function args aren't const by default since it's not using 'in'.  So 
it'll be fine.  The syntax used is also to pass a slice. which would 
become non-resizeable, which you're not resizing, so that's fine.  Slices 
are to retain their write through behavior, so that's fine.  Your 
initialization of buf would have an implicit cast from dup's T[new] to 
buf's T[], which works.  Passing a T[] to a function taking a T[] is 
perfectly normal.. 

So, that code 'just works'.

Later,
Brad

(now, time for Walter to point out the flaw in my reasoning)

On Tue, 5 Jun 2007, Sean Kelly wrote:


 Date: Tue, 05 Jun 2007 10:16:53 -0700
 From: Sean Kelly <sean f4.ca>
 Reply-To: digitalmars.D.announce <digitalmars-d-announce puremagic.com>
 To: digitalmars-d-announce puremagic.com
 Newsgroups: digitalmars.D.announce
 Subject: Re: resizeable arrays: T[new]
 
 It just occurred to me this morning that I may have missed something regarding
 the proposed const changes.  Given the following D 1.0 code, can someone tell
 me whether or how it will change in D 2.0?
 
     void alter( char[] str )
     {
         str[0] = 'x';
     }
 
     char[] buf = "abc".dup;
 
     alter( buf );
     alter( buf[1 .. $] );
 
     printf( "%.*s\n", buf ); // should print "xxc"
 
 
 
 Sean
Jun 05 2007
parent Sean Kelly <sean f4.ca> writes:
Brad Roberts wrote:

 I believe that code would not need to change to retain existing behavior.
 
 The function args aren't const by default since it's not using 'in'.  So 
 it'll be fine.  The syntax used is also to pass a slice. which would 
 become non-resizeable, which you're not resizing, so that's fine.  Slices 
 are to retain their write through behavior, so that's fine.  Your 
 initialization of buf would have an implicit cast from dup's T[new] to 
 buf's T[], which works.  Passing a T[] to a function taking a T[] is 
 perfectly normal.. 
 
 So, that code 'just works'.


Thanks for clearing this up.  After thinking about the talk yesterday 
I'd started to wonder if the "write through" feature of slices might 
change, etc.  It's very reassuring to know that this isn't the case.


Sean
Jun 05 2007
prev sibling parent orgoton <orgoton mindless.com> writes:
torhu Wrote:


 Bill Baxter wrote:

 Daniel Keep wrote:

 T[*]	// Indicating the index could be anything


 
 That's not bad.


 
 It means something completely different in C99.  Not that that matters much.
 
 

 T[~] // mnemonic: T can be concatenated onto
 


 
 Somehow this appeals to me. :)



vote++

cheers.
Jun 09 2007