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.

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. #1, you shouldn't ever use delete this. #1a, you should probably avoid using delete altogether. That is what the garbage collector is for. #2, if you insist on using delete this, you should exit the function immediately afterwards. #3, you are technically not allowed to change the length of the array during foreach, although I don't see why that would cause an access violation. #4, you should set apples[$-1] to null, to avoid dangling references to memory so the GC will clean it up, especially if you follow suggestion #1a
 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.

 #1, you shouldn't ever use delete this.
 #1a, you should probably avoid using delete altogether.  That is what the 
 garbage collector is for.

I'm not used to letting a gc handle things, but I guess you're right.
 #2, if you insist on using delete this, you should exit the function 
 immediately afterwards.

In my code I have a break right after that, seems I forgot to type that here.
 #3, you are technically not allowed to change the length of the array 
 during foreach, although I don't see why that would cause an access 
 violation.
 #4, you should set apples[$-1] to null, to avoid dangling references to 
 memory so the GC will clean it up, especially if you follow suggestion #1a

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