www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Foreach Access Violation

reply "nobody" <somebody somewhere.com> writes:
Say I have a class Apple:

class Apple
{
    ..
}

Several apples are created:

Apple[] apples;

for(int i = 0; i < 10; i++)
{
    apples.length = apples.length + 1;
    apples[apples.length-1] = new Apple();
}

Then I iterate over all the apples with a foreach loop

foreach(int i, Apple apple; apples)
{
     apples.iterate();
}

And in the iterate() some or more apples delete themselves via

void die()
{
    for (int i = 0; i < apples.length; i++)
    {
         if (apples[i] is this)
        {
            apples[i] = apples[$-1];
            apples.length = apples.length - 1;
            delete this;
        }
    }
}


This generally works fine, except when the last apple is deleted.
Then I get an Access Violation Error in the foreach loop.
When I use a for loop instead it works perfectly.

Is this because the foreach loop doesn't reevalute the length of the apples 
array
while looping, or am I missing something else entirely?
Oct 20 2008
next sibling parent reply BCS <ao pathlink.com> writes:
Reply to nobody,



 Apple[] apples;
 
 for(int i = 0; i < 10; i++)
 {
 apples.length = apples.length + 1;
 apples[apples.length-1] = new Apple();
 }


Apple[] apples = new Apples[10];
for(int i = 0; i < 10; i++)
{
  apples[apples.length-1] = new Apple();
}

The above would be faster in many cases. Extending length often results in 
a new allocation and must check to see if it needs to do one every time. 

If I just want to accumulate things but don't know in advance how many there 
will be I over allocate by a bit, keep track of how many you have used
externally 
and slice it back down once your done.



 This generally works fine, except when the last apple is deleted.
 Then I get an Access Violation Error in the foreach loop.
 When I use a for loop instead it works perfectly.
 Is this because the foreach loop doesn't reevalute the length of the
 apples
 array
 while looping, or am I missing something else entirely?


IIRC the docs say is it illegal to alter the loop array inside of a foreach
Oct 20 2008
parent reply "nobody" <somebody somewhere.com> writes:
"BCS" <ao pathlink.com> wrote in message 
news:78ccfa2d3408b8cb00ab37d623b8 news.digitalmars.com...

 Reply to nobody,



 Apple[] apples;

 for(int i = 0; i < 10; i++)
 {
 apples.length = apples.length + 1;
 apples[apples.length-1] = new Apple();
 }


 Apple[] apples = new Apples[10];
 for(int i = 0; i < 10; i++)
 {
  apples[apples.length-1] = new Apple();
 }

 The above would be faster in many cases. Extending length often results in 
 a new allocation and must check to see if it needs to do one every time.
 If I just want to accumulate things but don't know in advance how many 
 there will be I over allocate by a bit, keep track of how many you have 
 used externally and slice it back down once your done.


I guess that's possible, but it would only speed up the init of a few 
hundred apples.
After that while it's running it only deletes or adds about 1 to 5, so 
calculating a new allocation every time would not provide much of a boost.
Right now I'm not too concerned with that initial speed boost, but thanks 
for the tip.


 This generally works fine, except when the last apple is deleted.
 Then I get an Access Violation Error in the foreach loop.
 When I use a for loop instead it works perfectly.
 Is this because the foreach loop doesn't reevalute the length of the
 apples
 array
 while looping, or am I missing something else entirely?


 IIRC the docs say is it illegal to alter the loop array inside of a 
 foreach


Alright, thanks.
Oct 21 2008
parent BCS <ao pathlink.com> writes:
Reply to nobody,


 "BCS" <ao pathlink.com> wrote in message

 Apple[] apples = new Apples[10];
 for(int i = 0; i < 10; i++)
 {
 apples[apples.length-1] = new Apple();
 }





Oops. typo



 apples[i] = new Apple();
Oct 21 2008
prev sibling next sibling parent reply ore-sama <spam here.lot> writes:
I think, caller should manage array.
Oct 20 2008
parent reply "nobody" <somebody somewhere.com> writes:
"ore-sama" <spam here.lot> wrote in message 
news:gdicbb$66k$1 digitalmars.com...

I think, caller should manage array.



How should I do this?
Should I return a boolean set to true if it should be deleted or better, 
what is the best way to do this?
Oct 21 2008
parent ore-sama <spam here.lot> writes:
nobody Wrote:


I think, caller should manage array.


 How should I do this?
 Should I return a boolean set to true if it should be deleted or better, 
 what is the best way to do this?


this is a design decision, it depends on what you are trying to do.
Oct 21 2008
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"nobody" wrote

 Say I have a class Apple:

 class Apple
 {
    ..
 }

 Several apples are created:

 Apple[] apples;

 for(int i = 0; i < 10; i++)
 {
    apples.length = apples.length + 1;
    apples[apples.length-1] = new Apple();
 }

 Then I iterate over all the apples with a foreach loop

 foreach(int i, Apple apple; apples)
 {
     apples.iterate();
 }

 And in the iterate() some or more apples delete themselves via

 void die()
 {
    for (int i = 0; i < apples.length; i++)
    {
         if (apples[i] is this)
        {
            apples[i] = apples[$-1];
            apples.length = apples.length - 1;
            delete this;
        }
    }
 }


 This generally works fine, except when the last apple is deleted.
 Then I get an Access Violation Error in the foreach loop.
 When I use a for loop instead it works perfectly.


You are doing several things in the die function that are very bad.



garbage collector is for.

immediately afterwards.

foreach, although I don't see why that would cause an access violation.




 Is this because the foreach loop doesn't reevalute the length of the 
 apples array
 while looping, or am I missing something else entirely?


My gut tells me that it's something else.  Even if the loop is not 
reevaluating length, the memory that it was pointing to is still valid 
memory, so it shouldn't cause an access violation.  The clue that it's the 
last apple (BTW, does 'last' mean that there's only 1 element left in the 
array, or many elements and you are removing the end element?) says that 
probably it's the delete that's messing up something.  Try printing out 
information inside the foreach loop to see where the problem lies.

But unfortunately, in order to not violate the D spec, you should use a for 
loop, not a foreach loop.  That is the answer that you probably should 
follow.

-Steve
Oct 20 2008
parent reply "nobody" <somebody somewhere.com> writes:
 You are doing several things in the die function that are very bad.



 garbage collector is for.


I'm not used to letting a gc handle things, but I guess you're right.



 immediately afterwards.


In my code I have a break right after that, seems I forgot to type that 
here.



 during foreach, although I don't see why that would cause an access 
 violation.




Alright, thanks.


 Is this because the foreach loop doesn't reevalute the length of the 
 apples array
 while looping, or am I missing something else entirely?


 My gut tells me that it's something else.  Even if the loop is not 
 reevaluating length, the memory that it was pointing to is still valid 
 memory, so it shouldn't cause an access violation.  The clue that it's the 
 last apple (BTW, does 'last' mean that there's only 1 element left in the 
 array, or many elements and you are removing the end element?) says that 
 probably it's the delete that's messing up something.  Try printing out 
 information inside the foreach loop to see where the problem lies.


I'm writing some small code to see if I can replicate it. I'll reply with it 
once I do.


 But unfortunately, in order to not violate the D spec, you should use a 
 for loop, not a foreach loop.  That is the answer that you probably should 
 follow.


That's what I figured, thanks.


 -Steve
Oct 21 2008
parent reply "nobody" <somebody somewhere.com> writes:
module main;
import std.stdio;
class Apple
{
protected struct _Internal
{
int seeds;
}
private _Internal _intern;
this(int i)
{
_intern.seeds = i;
}
private void iterate()
{
writefln("iterate() apples[%s]",_intern.seeds);
//apple 3 kills apple 4, and apple 5 kills apple 6
if(_intern.seeds == 3 || _intern.seeds == 5)
{
apples[_intern.seeds+1].die();
}
}
private void die()
{
for (int i = 0; i < apples.length; i++)
{
if (apples[i] is this)
{
apples[i] = apples[$-1];
//uncommented: access violation error
//apples[$-1] = null;
apples.length = apples.length - 1;
writefln("die() apples[%s]",i);
delete this;
break;
}
}
}
}
Apple[] apples;

void main()
{
int n = 10; //nonstatic, random
for(int i = 0; i < n; i++)
{
apples ~= new Apple(i);
}
foreach(int i, Apple apple; apples)
{
//writefln("%s %s",i,apples.length);
apple.iterate();
//writefln("%s %s",i,apples.length);
}
}

/*
With apples[$-1] = null, without delete this
<OUTPUT>
iterate() apples[0]
iterate() apples[1]
iterate() apples[2]
iterate() apples[3]
die() apples[4]
iterate() apples[9]
iterate() apples[5]
die() apples[6]
iterate() apples[8]
iterate() apples[7]
Error: Access Violation
</OUTPUT>
Because of the foreach loop, this access violation makes sense.
Without apples[$-1] = null, with delete this
<OUTPUT>
iterate() apples[0]
iterate() apples[1]
iterate() apples[2]
iterate() apples[3]
die() apples[4]
iterate() apples[9]
iterate() apples[5]
die() apples[6]
iterate() apples[8]
iterate() apples[7]
iterate() apples[8]
iterate() apples[9]
</OUTPUT>
Because the array length is changed while in the foreach loop, the last 2 
lines show up.
However in my original code this also gives an access violation, and those 
last lines don't show up.
So possibly in this example code the delete this doesn't kick in, but in my 
longer original code it does?
*/
Oct 21 2008
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"nobody" wrote

 /*
 With apples[$-1] = null, without delete this
 <OUTPUT>
 iterate() apples[0]
 iterate() apples[1]
 iterate() apples[2]
 iterate() apples[3]
 die() apples[4]
 iterate() apples[9]
 iterate() apples[5]
 die() apples[6]
 iterate() apples[8]
 iterate() apples[7]
 Error: Access Violation
 </OUTPUT>
 Because of the foreach loop, this access violation makes sense.


Yes, because the foreach still looks at the elements you have removed, so it 
is trying to call a virtual function on a null pointer.


 Without apples[$-1] = null, with delete this
 <OUTPUT>
 iterate() apples[0]
 iterate() apples[1]
 iterate() apples[2]
 iterate() apples[3]
 die() apples[4]
 iterate() apples[9]
 iterate() apples[5]
 die() apples[6]
 iterate() apples[8]
 iterate() apples[7]
 iterate() apples[8]
 iterate() apples[9]
 </OUTPUT>
 Because the array length is changed while in the foreach loop, the last 2 
 lines show up.
 However in my original code this also gives an access violation, and those 
 last lines don't show up.
 So possibly in this example code the delete this doesn't kick in, but in 
 my longer original code it does?
 */


You didn't give your complete original code.  Did per chance the original 
code have a destructor for Apple?  If so, it probably was in the destructor 
that the problem occurred, since the memory was probably being destroyed 
twice.

Note that in destructors, you should not access any references to other 
data, as these might be invalid by the time your destructor is called.  If 
you have nothing but GC-allocated memory, then you should not use a 
destructor.

-Steve
Oct 21 2008
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
More comments added to the answers given by the other people.

nobody:

 Several apples are created:
 Apple[] apples;
 for(int i = 0; i < 10; i++)
 {
     apples.length = apples.length + 1;
     apples[apples.length-1] = new Apple();
 }


If you know you want 10 apples then this is better (D2, but in D1 it's similar):

auto apples = new Apple[10];
foreach (ref apple; apples)
    apple = new Apple();

If you don't know how many you will have:

Apple[] apples;
foreach (i; 0 .. find_number())
    apples ~= new Apple();

Finally if you don't know how many you will have, but you know they can be a
lot, then you can use an array appender, like the one discussed recently.



 foreach(int i, Apple apple; apples)
 {
      apples.iterate();
 }


Note this suffices here:

foreach(apple; apples)
{
    apples.iterate();
}

Bye,
bearophile
Oct 20 2008
parent "nobody" <somebody somewhere.com> writes:
"bearophile" <bearophileHUGS lycos.com> wrote in message 
news:gdj1gr$1dfn$1 digitalmars.com...

 More comments added to the answers given by the other people.

 nobody:

 Several apples are created:
 Apple[] apples;
 for(int i = 0; i < 10; i++)
 {
     apples.length = apples.length + 1;
     apples[apples.length-1] = new Apple();
 }


 If you know you want 10 apples then this is better (D2, but in D1 it's 
 similar):

 auto apples = new Apple[10];
 foreach (ref apple; apples)
    apple = new Apple();

 If you don't know how many you will have:

 Apple[] apples;
 foreach (i; 0 .. find_number())
    apples ~= new Apple();

 Finally if you don't know how many you will have, but you know they can be 
 a lot, then you can use an array appender, like the one discussed 
 recently.


I always forget append exists, thanks.


 foreach(int i, Apple apple; apples)
 {
      apples.iterate();
 }


 Note this suffices here:

 foreach(apple; apples)
 {
    apples.iterate();
 }


I know, but I was using the int i in my original code. Forgot to remove it 
in the example code I posted here :)


 Bye,
 bearophile
Oct 21 2008