digitalmars.D - array cast should be supported corrected
- Frank Benoit (15/15) Aug 06 2008 interface I{}
- BCS (5/22) Aug 06 2008 this has come up before (IIRC) and the reply from Walter was that becaus...
- Frank Benoit (9/36) Aug 06 2008 Yes it is broken by design.
- BCS (4/9) Aug 06 2008 Array cat's /always/ do a O(?) allocation and a O(n+m) copy. Cast usuall...
- Bill Baxter (12/22) Aug 06 2008 Not true for ~=. Sometimes allocates sometimes doesn't. You'll have
- BCS (14/39) Aug 06 2008 http://www.digitalmars.com/d/1.0/arrays.html
- Steven Schveighoffer (19/43) Aug 07 2008 I once thought as you do. However, there is a conflicting statement lat...
- BCS (3/43) Aug 08 2008 ok, new version: "Array cat's are /always/ suposed to do a O(?) allocati...
- bearophile (6/9) Aug 06 2008 Here I agree with Walter, a good language *must* act as much transparent...
- Robert Fraser (14/33) Aug 06 2008 The only way to do this is if the cast performed a copy. Consider:
- maelp (4/12) Aug 07 2008 I guess, for most of the D programming language design decisions, it wou...
- Steven Schveighoffer (8/38) Aug 07 2008 Aliasing is possible. The problem is that for interfaces, the pointer i...
- Robert Fraser (25/69) Aug 07 2008 If you can replace "I" with an abstract class and get it to
- Steven Schveighoffer (30/103) Aug 07 2008 Actually, because of the way arrays work, this will cause a segfault onl...
- Robert Fraser (17/63) Aug 07 2008 We're saying the same thing ;-P. From wiktionary:
- Steven Schveighoffer (9/53) Aug 08 2008 That eliminates the possibility of having covariant functions that retur...
- Frank Benoit (2/24) Aug 07 2008 I filed this as report 2270.
interface I{} class C : I {} C[] carray = getInstance(); I[] iarray = carray; // compile error I[] iarray = cast(I[])carray; // runtime error (1) // correct way: I[] iarray = new I[carray.length]; foreach( idx, c; carray ){ iarray[idx] = c; // implicit cast } I use a template for doing this, but this looks so ugly. I[] iarray = arraycast!(I)(carray); I think the D compiler should call a runtime method in (1) to do the cast in a loop, instead of doing a simple type change that is not working correctly.
Aug 06 2008
Reply to Frank,interface I{} class C : I {} C[] carray = getInstance(); I[] iarray = carray; // compile error I[] iarray = cast(I[])carray; // runtime error (1) // correct way: I[] iarray = new I[carray.length]; foreach( idx, c; carray ){ iarray[idx] = c; // implicit cast } I use a template for doing this, but this looks so ugly. I[] iarray = arraycast!(I)(carray); I think the D compiler should call a runtime method in (1) to do the cast in a loop, instead of doing a simple type change that is not working correctly.this has come up before (IIRC) and the reply from Walter was that because the conversion is O(n) it should not be put into a cast that is otherwise O(1). OTOH if the cast(I[])carray is broken, that should be fixed (forbidden).
Aug 06 2008
BCS schrieb:Reply to Frank,Yes it is broken by design. When casting from class ref to interface ref the numerical value of the reference must get an offset applied. So if the O(n) operation (the loop above) is not made, the resulting array is not usable. However. What is better in a template arraycast with o(n) or a cast? The programmer always needs to know what the concequences are. With this argumentation the string concatenation ~ should also be banned from the language, because hidden heap allocation has always unbound execution time.interface I{} class C : I {} C[] carray = getInstance(); I[] iarray = carray; // compile error I[] iarray = cast(I[])carray; // runtime error (1) // correct way: I[] iarray = new I[carray.length]; foreach( idx, c; carray ){ iarray[idx] = c; // implicit cast } I use a template for doing this, but this looks so ugly. I[] iarray = arraycast!(I)(carray); I think the D compiler should call a runtime method in (1) to do the cast in a loop, instead of doing a simple type change that is not working correctly.this has come up before (IIRC) and the reply from Walter was that because the conversion is O(n) it should not be put into a cast that is otherwise O(1). OTOH if the cast(I[])carray is broken, that should be fixed (forbidden).
Aug 06 2008
Reply to Frank,However. What is better in a template arraycast with o(n) or a cast? The programmer always needs to know what the concequences are. With this argumentation the string concatenation ~ should also be banned from the language, because hidden heap allocation has always unbound execution time.Array cat's /always/ do a O(?) allocation and a O(n+m) copy. Cast usually does a O(1) transformation. Having the corner case be much worse than the normal case is the problem, not the fact it's O(n).
Aug 06 2008
On Thu, Aug 7, 2008 at 6:06 AM, BCS <ao pathlink.com> wrote:Reply to Frank,Not true for ~=. Sometimes allocates sometimes doesn't. You'll have to come up with a better argument than that. :-) That said, I don't see why writing arraycast!(T)(x) is so much worse than cast(T)x. I wish D had more flavors of cast. The current cast is a very blunt instrument. Seems obvious to me that It's a bad idea to use the same construct to mean "please convert this to a T" and "please pretend the bits of this are actually bits of a T". C++ added all those extra kinds of casts for a reason.However. What is better in a template arraycast with o(n) or a cast? The programmer always needs to know what the concequences are. With this argumentation the string concatenation ~ should also be banned from the language, because hidden heap allocation has always unbound execution time.Array cat's /always/ do a O(?) allocation and a O(n+m) copy.Cast usually does a O(1) transformation. Having the corner case be much worse than the normal case is the problem, not the fact it's O(n).I think casting to an interface is O(n) in the number of interfaces the object supports, no? --bb
Aug 06 2008
Reply to Bill,On Thu, Aug 7, 2008 at 6:06 AM, BCS <ao pathlink.com> wrote:http://www.digitalmars.com/d/1.0/arrays.html "Concatenation always creates a copy of its operands" http://www.digitalmars.com/d/1.0/expression.html "" Assignment operator expressions, such as: a op= b are semantically equivalent to: a = a op b ""Reply to Frank,Not true for ~=. Sometimes allocates sometimes doesn't. You'll have to come up with a better argument than that. :-)However. What is better in a template arraycast with o(n) or a cast? The programmer always needs to know what the concequences are. With this argumentation the string concatenation ~ should also be banned from the language, because hidden heap allocation has always unbound execution time.Array cat's /always/ do a O(?) allocation and a O(n+m) copy.I think that it's just a simple addition as the interface vtbl in a given class is at a constant offset from the base of the object. I don't /think/ a class to interface cast can fail at run time. OTOH casting from an interface to a base class of the actual type... I haven't a clue what that's doing. Might be O(n) on the number of derivations The O(n) I was looking at would be on the length of the array.Cast usually does a O(1) transformation. Having the corner case be much worse than the normal case is the problem, not the fact it's O(n).I think casting to an interface is O(n) in the number of interfaces the object supports, no?--bb
Aug 06 2008
"BCS" <ao pathlink.com> wrote in message news:55391cb3300e68cac5e93619c98c news.digitalmars.com...Reply to Bill,I once thought as you do. However, there is a conflicting statement later in that page: http://www.digitalmars.com/d/1.0/arrays.html#resize Although it says that it applies to the ~ and ~= operator, in reality it only applies to the ~= operator, I think that is an error in the spec. Go ahead and try it out: char[] x = new char[1]; x[0] = 'a'; char[] y = x; x ~= 'a'; assert(x.ptr == y.ptr); y ~= 'b'; assert(x[1] == 'b'); // now the concatenation operator y = y ~ 'c'; assert(y.ptr != x.ptr); -SteveOn Thu, Aug 7, 2008 at 6:06 AM, BCS <ao pathlink.com> wrote:http://www.digitalmars.com/d/1.0/arrays.html "Concatenation always creates a copy of its operands" http://www.digitalmars.com/d/1.0/expression.html "" Assignment operator expressions, such as: a op= b are semantically equivalent to: a = a op b ""Reply to Frank,Not true for ~=. Sometimes allocates sometimes doesn't. You'll have to come up with a better argument than that. :-)However. What is better in a template arraycast with o(n) or a cast? The programmer always needs to know what the concequences are. With this argumentation the string concatenation ~ should also be banned from the language, because hidden heap allocation has always unbound execution time.Array cat's /always/ do a O(?) allocation and a O(n+m) copy.
Aug 07 2008
Reply to Steven,"BCS" <ao pathlink.com> wrote in message news:55391cb3300e68cac5e93619c98c news.digitalmars.com...ok, new version: "Array cat's are /always/ suposed to do a O(?) allocation and a O(n+m) copy."Reply to Bill,I once thought as you do. However, there is a conflicting statement later in that page: http://www.digitalmars.com/d/1.0/arrays.html#resize Although it says that it applies to the ~ and ~= operator, in reality it only applies to the ~= operator, I think that is an error in the spec.On Thu, Aug 7, 2008 at 6:06 AM, BCS <ao pathlink.com> wrote:http://www.digitalmars.com/d/1.0/arrays.html "Concatenation always creates a copy of its operands" http://www.digitalmars.com/d/1.0/expression.html "" Assignment operator expressions, such as: a op= b are semantically equivalent to: a = a op b ""Reply to Frank,Not true for ~=. Sometimes allocates sometimes doesn't. You'll have to come up with a better argument than that. :-)However. What is better in a template arraycast with o(n) or a cast? The programmer always needs to know what the concequences are. With this argumentation the string concatenation ~ should also be banned from the language, because hidden heap allocation has always unbound execution time.Array cat's /always/ do a O(?) allocation and a O(n+m) copy.
Aug 08 2008
Frank Benoit:The programmer always needs to know what the concequences are. With this argumentation the string concatenation ~ should also be banned from the language, because hidden heap allocation has always unbound execution time.Here I agree with Walter, a good language *must* act as much transparently as humanly possible, otherwise the life of the programmer becomes miserable (the only problems I find in D are when I mix GC-managed pointers with GC-unmanaged pointers in data structures, this leads to complex situations because I haven't written the GC, I don't know much about how its internals work, so in those situations for me it's *not* transparent). But D is a language designed to prevent programmer bugs when possible, so a simple solution is to make the compiler raise a compilation error at compile time in those situations. Then, if people want it, it can optionally be added a different kind of cast to D, maybe an array_cast(), that is known to work in O(n). Bye, bearophile
Aug 06 2008
Frank Benoit Wrote:interface I{} class C : I {} C[] carray = getInstance(); I[] iarray = carray; // compile error I[] iarray = cast(I[])carray; // runtime error (1) // correct way: I[] iarray = new I[carray.length]; foreach( idx, c; carray ){ iarray[idx] = c; // implicit cast } I use a template for doing this, but this looks so ugly. I[] iarray = arraycast!(I)(carray); I think the D compiler should call a runtime method in (1) to do the cast in a loop, instead of doing a simple type change that is not working correctly.The only way to do this is if the cast performed a copy. Consider: interface I { } class A : I { } class B : I { } A[] aarray; I[] iarray = aarray; iarray ~= new B(); A a = aarray[0]; // you BROKE my TYPE SYSTEM -- this is an instance of B When upcasting an array you NEED to copy; you cannot alias. And a cast should never make a copy, since that's unexpected behavior. In Java, List<A> is not upcastable to List<I>, only to List<? extends I> to solve this exact problem. This syntax is pretty ugly, though, so I wouldn't recommend it for D.
Aug 06 2008
interface I { } class A : I { } class B : I { } A[] aarray; I[] iarray = aarray; iarray ~= new B(); A a = aarray[0]; // you BROKE my TYPE SYSTEM -- this is an instance of BI guess, for most of the D programming language design decisions, it would help if we had a kind of wiki listing those counterexamples, because it helps a lot when trying to wrap one's head on "why is this feature un/available". We should just collect those and possibly link them from the D documentation
Aug 07 2008
"Robert Fraser" wroteFrank Benoit Wrote:Aliasing is possible. The problem is that for interfaces, the pointer is changed. If you change I to be a class, not an interface, then your code will compile (of course, it has the same problem as you have added a B to the end of an A array, but in general, casting from A[] to B[] where A is implicitly castable to B and both A and B use the same amount of space, is allowed. Except for Interfaces :) ) -Steveinterface I{} class C : I {} C[] carray = getInstance(); I[] iarray = carray; // compile error I[] iarray = cast(I[])carray; // runtime error (1) // correct way: I[] iarray = new I[carray.length]; foreach( idx, c; carray ){ iarray[idx] = c; // implicit cast } I use a template for doing this, but this looks so ugly. I[] iarray = arraycast!(I)(carray); I think the D compiler should call a runtime method in (1) to do the cast in a loop, instead of doing a simple type change that is not working correctly.The only way to do this is if the cast performed a copy. Consider: interface I { } class A : I { } class B : I { } A[] aarray; I[] iarray = aarray; iarray ~= new B(); A a = aarray[0]; // you BROKE my TYPE SYSTEM -- this is an instance of B When upcasting an array you NEED to copy; you cannot alias. And a cast should never make a copy, since that's unexpected behavior.
Aug 07 2008
Steven Schveighoffer Wrote:"Robert Fraser" wroteIf you can replace "I" with an abstract class and get it to compile right, that's a good old-fashioned bug. It doesn't matter if A and B are the same size (unless you're using scope classes which might lead to slicing), the problem is that the bits are being interpreted as different types than they are. // Note these definitions -- A and B are not type-compatible! class Base { } class A : Base { char[] str; } class B : Base { int x, int y; } A[] a_array; Base[] base_array = a_array; base_array ~= new B(5, 10); A a = a_array[0]; writefln(a.str); // Segfault! I don't have a D compiler on this computer so I can't test it out, but if the compiler can implicitly cast A[] to Base[], then this is a hole in the type system. The issue with interfaces is tangential. It's also extremely easy to overlook this error. Say you're passing an array of A[] to a function that modifies an array of Base[] by possibly adding things. In a large system, it can be a tricky bug to track down since the error may not manifest itself until a while after it happens, and may not always be a segfault (if they're the same size & it's just the bits being interpreted as the wrong type, things could get very ugly -- it may not always just segfault).Frank Benoit Wrote:Aliasing is possible. The problem is that for interfaces, the pointer is changed. If you change I to be a class, not an interface, then your code will compile (of course, it has the same problem as you have added a B to the end of an A array, but in general, casting from A[] to B[] where A is implicitly castable to B and both A and B use the same amount of space, is allowed. Except for Interfaces :) )interface I{} class C : I {} C[] carray = getInstance(); I[] iarray = carray; // compile error I[] iarray = cast(I[])carray; // runtime error (1) // correct way: I[] iarray = new I[carray.length]; foreach( idx, c; carray ){ iarray[idx] = c; // implicit cast } I use a template for doing this, but this looks so ugly. I[] iarray = arraycast!(I)(carray); I think the D compiler should call a runtime method in (1) to do the cast in a loop, instead of doing a simple type change that is not working correctly.The only way to do this is if the cast performed a copy. Consider: interface I { } class A : I { } class B : I { } A[] aarray; I[] iarray = aarray; iarray ~= new B(); A a = aarray[0]; // you BROKE my TYPE SYSTEM -- this is an instance of B When upcasting an array you NEED to copy; you cannot alias. And a cast should never make a copy, since that's unexpected behavior.
Aug 07 2008
"Robert Fraser" wroteSteven Schveighoffer Wrote:Actually, because of the way arrays work, this will cause a segfault only in release mode, because a_array is still 0-length (and null). Without release mode, you get an array bounds exception A better example would be: A[] a_array; a_array ~= new A; Base[] base_array = a_array; B b = new B; b.x = b.y = 100; base_array[0] = b; A a = a_array[0]; // a now points to b writefln(a.str); // Segfault!"Robert Fraser" wroteIf you can replace "I" with an abstract class and get it to compile right, that's a good old-fashioned bug. It doesn't matter if A and B are the same size (unless you're using scope classes which might lead to slicing), the problem is that the bits are being interpreted as different types than they are. // Note these definitions -- A and B are not type-compatible! class Base { } class A : Base { char[] str; } class B : Base { int x, int y; } A[] a_array; Base[] base_array = a_array; base_array ~= new B(5, 10); A a = a_array[0]; writefln(a.str); // Segfault!Frank Benoit Wrote:Aliasing is possible. The problem is that for interfaces, the pointer is changed. If you change I to be a class, not an interface, then your code will compile (of course, it has the same problem as you have added a B to the end of an A array, but in general, casting from A[] to B[] where A is implicitly castable to B and both A and B use the same amount of space, is allowed. Except for Interfaces :) )interface I{} class C : I {} C[] carray = getInstance(); I[] iarray = carray; // compile error I[] iarray = cast(I[])carray; // runtime error (1) // correct way: I[] iarray = new I[carray.length]; foreach( idx, c; carray ){ iarray[idx] = c; // implicit cast } I use a template for doing this, but this looks so ugly. I[] iarray = arraycast!(I)(carray); I think the D compiler should call a runtime method in (1) to do the cast in a loop, instead of doing a simple type change that is not working correctly.The only way to do this is if the cast performed a copy. Consider: interface I { } class A : I { } class B : I { } A[] aarray; I[] iarray = aarray; iarray ~= new B(); A a = aarray[0]; // you BROKE my TYPE SYSTEM -- this is an instance of B When upcasting an array you NEED to copy; you cannot alias. And a cast should never make a copy, since that's unexpected behavior.I don't have a D compiler on this computer so I can't test it out, but if the compiler can implicitly cast A[] to Base[], then this is a hole in the type system. The issue with interfaces is tangential.The issues are orthogonal. When casting to an interface array O(n) copying is the only reasonable choice. O(1) aliasing is OK for a base class if you are not planning on changing the existing elements.It's also extremely easy to overlook this error. Say you're passing an array of A[] to a function that modifies an array of Base[] by possibly adding things. In a large system, it can be a tricky bug to track down since the error may not manifest itself until a while after it happens, and may not always be a segfault (if they're the same size & it's just the bits being interpreted as the wrong type, things could get very ugly -- it may not always just segfault).This is not a common case (to pass in a abstract base array in which you plan on changing elements). The common case is to use the base class array as a means of writing a common function that *uses* the array, but does not create elements in it. For that, the cast is perfectly safe. Or to use it as a co-variant return value. I think the benefits of being able to cast this way outweigh the uncommon pitfalls. I look at it no differently than doing: class C {int x;} C c; c.x = 5; // segfault But the interface thing is a performance question. Whether or not to implicitly generate heap activity and run an O(n) algorithm by default is a completely different question. -Steve
Aug 07 2008
Steven Schveighoffer Wrote:Actually, because of the way arrays work, this will cause a segfault only in release mode, because a_array is still 0-length (and null). Without release mode, you get an array bounds exception A better example would be: A[] a_array; a_array ~= new A; Base[] base_array = a_array; B b = new B; b.x = b.y = 100; base_array[0] = b; A a = a_array[0]; // a now points to b writefln(a.str); // Segfault!Yes, you're right; my bad.We're saying the same thing ;-P. From wiktionary: tangential = "Only indirectly related." orthogonal = "Able to be treated separately."I don't have a D compiler on this computer so I can't test it out, but if the compiler can implicitly cast A[] to Base[], then this is a hole in the type system. The issue with interfaces is tangential.The issues are orthogonal. When casting to an interface array O(n) copying is the only reasonable choice.O(1) aliasing is OK for a base class if you are not planning on changing the existing elements.In this case it should require an explicit cast. A[] could be implicitly castable to const(Base[]) but not to const(Base)[] or Base[].I agree the advantages are enough to justify allowing aliasing without serious subversion of the type system. But the cast _must be explicit_, so users see a red flag there. It's potentially dangerous, since you might accidentally interpret one bit pattern as a different type. Short of unions, only a cast can do that.It's also extremely easy to overlook this error. Say you're passing an array of A[] to a function that modifies an array of Base[] by possibly adding things. In a large system, it can be a tricky bug to track down since the error may not manifest itself until a while after it happens, and may not always be a segfault (if they're the same size & it's just the bits being interpreted as the wrong type, things could get very ugly -- it may not always just segfault).This is not a common case (to pass in a abstract base array in which you plan on changing elements). The common case is to use the base class array as a means of writing a common function that *uses* the array, but does not create elements in it. For that, the cast is perfectly safe. Or to use it as a co-variant return value. I think the benefits of being able to cast this way outweigh the uncommon pitfalls.I look at it no differently than doing: class C {int x;} C c; c.x = 5; // segfaultHow is that at all the same? In the case of implicit base class casting, you're tricking the compiler (likely without meaning to) into interpreting the data as an incorrect type. In this case, the compiler is acting correctly and you have a bug in your code.But the interface thing is a performance question. Whether or not to implicitly generate heap activity and run an O(n) algorithm by default is a completely different question.Agreed.
Aug 07 2008
"Robert Fraser" wroteSteven Schveighoffer Wrote:That eliminates the possibility of having covariant functions that return arrays of objects.O(1) aliasing is OK for a base class if you are not planning on changing the existing elements.In this case it should require an explicit cast. A[] could be implicitly castable to const(Base[]) but not to const(Base)[] or Base[].I'm trying to show that there is a precedent of being able to make code that fails without explicit casting. Everyone knows that the 'right' thing to do is to create a new object before using it. I could say exactly the same thing about your example. The compiler is acting correctly and you have a bug in your code. -SteveI agree the advantages are enough to justify allowing aliasing without serious subversion of the type system. But the cast _must be explicit_, so users see a red flag there. It's potentially dangerous, since you might accidentally interpret one bit pattern as a different type. Short of unions, only a cast can do that.It's also extremely easy to overlook this error. Say you're passing an array of A[] to a function that modifies an array of Base[] by possibly adding things. In a large system, it can be a tricky bug to track down since the error may not manifest itself until a while after it happens, and may not always be a segfault (if they're the same size & it's just the bits being interpreted as the wrong type, things could get very ugly -- it may not always just segfault).This is not a common case (to pass in a abstract base array in which you plan on changing elements). The common case is to use the base class array as a means of writing a common function that *uses* the array, but does not create elements in it. For that, the cast is perfectly safe. Or to use it as a co-variant return value. I think the benefits of being able to cast this way outweigh the uncommon pitfalls.I look at it no differently than doing: class C {int x;} C c; c.x = 5; // segfaultHow is that at all the same? In the case of implicit base class casting, you're tricking the compiler (likely without meaning to) into interpreting the data as an incorrect type. In this case, the compiler is acting correctly and you have a bug in your code.
Aug 08 2008
Frank Benoit schrieb:interface I{} class C : I {} C[] carray = getInstance(); I[] iarray = carray; // compile error I[] iarray = cast(I[])carray; // runtime error (1) // correct way: I[] iarray = new I[carray.length]; foreach( idx, c; carray ){ iarray[idx] = c; // implicit cast } I use a template for doing this, but this looks so ugly. I[] iarray = arraycast!(I)(carray); I think the D compiler should call a runtime method in (1) to do the cast in a loop, instead of doing a simple type change that is not working correctly.I filed this as report 2270.
Aug 07 2008