www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - bug in assigning to dynamic array element

reply ketmar via Digitalmars-d <digitalmars-d puremagic.com> writes:
Hello.

let's run this code:

  struct Info {
    size_t[] list;
  }

  size_t saveIt (ref Info info, size_t count) {
    if (count < 1) return 666;
    size_t idx =3D info.list.length;
    info.list.length =3D idx+count;
    foreach (; 0..count) {
      info.list[idx] =3D saveIt(info, count-1); //!!!
      assert(info.list[idx] !=3D 0);
      ++idx;
    }
    return 666;
  }

  void main () {
    auto info =3D Info();
    saveIt(info, 2);
  }

it should work, but it asserts. the fault line is marked by '!!!'.
if i'll change it to this:

  auto n =3D saveIt(info, count-1);
  info.list[idx] =3D n;

everything works ok.


as i can guess, the bug is in evaluating left part of '=3D' operation
before the right part. assignment using the old array data address, but
the array was resized, so it is stored in the invalid address. to prove
that, let's change the code a little:

  size_t saveIt (ref Info info, size_t count) {
    if (count < 1) return 666;
    size_t idx =3D info.list.length;
    info.list.length =3D idx+count;
    foreach (; 0..count) {
      auto p0 =3D &info.list[idx];
      info.list[idx] =3D saveIt(info, count-1);
      auto p1 =3D &info.list[idx];
      if (info.list[idx] =3D=3D 0) {
        assert(*p0 !=3D 0); //mk1
        assert(*p1 !=3D 0); //mk2
      }
      assert(info.list[idx] !=3D 0);
      ++idx;
    }
    return 666;
  }


line with 'mk1' should assert, but it doesn't! and like 'mk2' asserts,
which proves that 'mk1' was really executed.


this stinky thing took me two days to find, 'cause it was in a bigger
codebase, and i was searching for the bug in my code. the bug
mysteriously disappearing when i inserting debug printing ('cause i
assigned `saveIt()` result to variable to print it) didn't much help
either. ;-)

the bug is reproducible with gdc and dmd head on x86, without
optimisations turned on.
Nov 01 2014
next sibling parent "ketmar" <ketmar ketmar.no-ip.org> writes:
filled bugreport for this: 
https://issues.dlang.org/show_bug.cgi?id=13670
Nov 01 2014
prev sibling next sibling parent reply "anonymous" <anonymous example.com> writes:
On Saturday, 1 November 2014 at 09:03:42 UTC, ketmar via
Digitalmars-d wrote:
 as i can guess, the bug is in evaluating left part of '=' 
 operation
 before the right part.
I don't know how D defines this, and I couldn't find anything but a forum discussion [1] (which I didn't read all of). But unless it's explicitly stated that the right-hand side is evaluated first, there is no bug. A simpler test case: auto list = new size_t[1]; list[0] = (){list = new size_t[1]; return 666;}(); assert(list[0] == 666); [1] http://forum.dlang.org/thread/gu4bqu$bq$1 digitalmars.com
Nov 01 2014
next sibling parent Iain Buclaw via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 1 November 2014 11:31, anonymous via Digitalmars-d
<digitalmars-d puremagic.com> wrote:
 On Saturday, 1 November 2014 at 09:03:42 UTC, ketmar via
 Digitalmars-d wrote:
 as i can guess, the bug is in evaluating left part of '=' operation
 before the right part.
I don't know how D defines this, and I couldn't find anything but a forum discussion [1] (which I didn't read all of). But unless it's explicitly stated that the right-hand side is evaluated first, there is no bug. A simpler test case:
Breakdown.
      auto list = new size_t[1];
list = addressA;
      list[0] = (){list = new size_t[1]; return 666;}();
list = addressB; addressA[0] = 666;
      assert(list[0] == 666);
assert(addressB[0] == 666)
Nov 01 2014
prev sibling next sibling parent ketmar via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Sat, 01 Nov 2014 11:31:51 +0000
anonymous via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 I don't know how D defines this, and I couldn't find anything but
 a forum discussion [1] (which I didn't read all of). But unless
 it's explicitly stated that the right-hand side is evaluated
 first, there is no bug.
there is. compiler generates code that modifies random memory addresses. this is absolutely unacceptable. and this is just illogical if we want dynamic arrays to look and work like "normal" arrays. besides, it's easily fixable without any changes in evaluation order.
Nov 01 2014
prev sibling next sibling parent Iain Buclaw via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 1 November 2014 11:56, ketmar via Digitalmars-d
<digitalmars-d puremagic.com> wrote:
 On Sat, 01 Nov 2014 11:31:51 +0000
 anonymous via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 I don't know how D defines this, and I couldn't find anything but
 a forum discussion [1] (which I didn't read all of). But unless
 it's explicitly stated that the right-hand side is evaluated
 first, there is no bug.
there is. compiler generates code that modifies random memory addresses. this is absolutely unacceptable. and this is just illogical if we want dynamic arrays to look and work like "normal" arrays. besides, it's easily fixable without any changes in evaluation order.
I'm not *entire* sure on that. :) If the evaluation of LHS[IDX] has a side effect, you've broken LTR. Think: Left => Index => Right vs Index => Right => Left
Nov 01 2014
prev sibling next sibling parent ketmar via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Sat, 1 Nov 2014 12:01:04 +0000
Iain Buclaw via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On 1 November 2014 11:56, ketmar via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:
 On Sat, 01 Nov 2014 11:31:51 +0000
 anonymous via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 I don't know how D defines this, and I couldn't find anything but
 a forum discussion [1] (which I didn't read all of). But unless
 it's explicitly stated that the right-hand side is evaluated
 first, there is no bug.
there is. compiler generates code that modifies random memory addresses. this is absolutely unacceptable. and this is just illogical if we want dynamic arrays to look and work like "normal" arrays. besides, it's easily fixable without any changes in evaluation order.
=20 I'm not *entire* sure on that. :) =20 If the evaluation of LHS[IDX] has a side effect, you've broken LTR. =20 Think: Left =3D> Index =3D> Right =20 vs =20 Index =3D> Right =3D> Left
so forbid that. this kind of bugs are VERY hard to find, especially when dynamic arrays looks like ordinary static arrays in the source. compiler should emit error on the "assign code" with possible side effects for dynamic arrays, or this hole will pop again and again. a simple change in the unrelated part of code and... KABOOM! everything goes wrong.
Nov 01 2014
prev sibling parent ketmar via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Sat, 1 Nov 2014 12:01:04 +0000
Iain Buclaw via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On 1 November 2014 11:56, ketmar via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:
 On Sat, 01 Nov 2014 11:31:51 +0000
 anonymous via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 I don't know how D defines this, and I couldn't find anything but
 a forum discussion [1] (which I didn't read all of). But unless
 it's explicitly stated that the right-hand side is evaluated
 first, there is no bug.
there is. compiler generates code that modifies random memory addresses. this is absolutely unacceptable. and this is just illogical if we want dynamic arrays to look and work like "normal" arrays. besides, it's easily fixable without any changes in evaluation order.
=20 I'm not *entire* sure on that. :) =20 If the evaluation of LHS[IDX] has a side effect, you've broken LTR. =20 Think: Left =3D> Index =3D> Right =20 vs =20 Index =3D> Right =3D> Left
p.s. besides, the following code LOOKS wrong: info.list[idx] =3D saveIt(info, count-1); assert(info.list[idx] !=3D 0); aren't it a nonsence if we know for sure that saveIt() will never return zero? if the code *LOOKS* wrong, it is wrong. that assert() should never fire by any logical means.
Nov 01 2014
prev sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
If it's indeed caused by evaluation (which seems likely), then 
it's not a bug. All expressions are supposed to be evaluated from 
left to right.
Nov 01 2014
parent reply ketmar via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Sat, 01 Nov 2014 11:43:11 +0000
via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 If it's indeed caused by evaluation (which seems likely), then=20
 it's not a bug. All expressions are supposed to be evaluated from=20
 left to right.
this *IS* a bug. either compiler should error on this, or it shouldn't modify random memory. imagine the situation when old array contents not only collected by GC, but that memory was allocated to something completely different. and it's completely possible to fix this without dropping evaluation order promise: take the address of hidden dynamic array structure first and remember index, and take the address of array element just before assigning. this way it will work as expected, and will evaluate all indicies and the array address itself (not the address of the array contents, but this is irrelevant to evaluation order) first. what whay authors choose to fix this bug is irrelevant for me (but i prefer the second way), but it MUST be fixed. either error, or do what i described in the previous paragraph.
Nov 01 2014
parent reply "anonymous" <anonymous example.com> writes:
On Saturday, 1 November 2014 at 11:50:34 UTC, ketmar via
Digitalmars-d wrote:
 this *IS* a bug. either compiler should error on this, or it 
 shouldn't
 modify random memory. imagine the situation when old array 
 contents not
 only collected by GC, but that memory was allocated to something
 completely different.
The old array is still alive and kicking. The left-hand side still references it. It wasn't collected. You're not writing to random memory.
Nov 01 2014
parent reply ketmar via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Sat, 01 Nov 2014 11:55:53 +0000
anonymous via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On Saturday, 1 November 2014 at 11:50:34 UTC, ketmar via
 Digitalmars-d wrote:
 this *IS* a bug. either compiler should error on this, or it=20
 shouldn't
 modify random memory. imagine the situation when old array=20
 contents not
 only collected by GC, but that memory was allocated to something
 completely different.
=20 The old array is still alive and kicking. The left-hand side still references it. It wasn't collected. You're not writing to random memory.
so it's not only writes to the stale copy, but protects that copy from GC. what a great thing! and all this without even a small warning from compiler. i can expect such behavior from c or c++ with all their UB, but not from D. this is not only ugly, this is plainly wrong.
Nov 01 2014
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/1/14 8:04 AM, ketmar via Digitalmars-d wrote:
 On Sat, 01 Nov 2014 11:55:53 +0000
 anonymous via Digitalmars-d <digitalmars-d puremagic.com> wrote:

 On Saturday, 1 November 2014 at 11:50:34 UTC, ketmar via
 Digitalmars-d wrote:
 this *IS* a bug. either compiler should error on this, or it
 shouldn't
 modify random memory. imagine the situation when old array
 contents not
 only collected by GC, but that memory was allocated to something
 completely different.
The old array is still alive and kicking. The left-hand side still references it. It wasn't collected. You're not writing to random memory.
so it's not only writes to the stale copy, but protects that copy from GC. what a great thing! and all this without even a small warning from compiler. i can expect such behavior from c or c++ with all their UB, but not from D. this is not only ugly, this is plainly wrong.
No, it's not. It's exactly as you requested when you wrote that code :) Note, you can fix this by overloading opAssign in Info, and it should work as you expect. This will force a delay in the evaluation of which array is used until *after* the RHS is done. -Steve
Nov 03 2014