http://d.puremagic.com/issues/show_bug.cgi?id=2255

           Summary: AA.remove() doesn't remove AA element when iterating
                    using foreach
           Product: D
           Version: 2.017
          Platform: PC
        OS/Version: Windows
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: bugzilla@digitalmars.com
        ReportedBy: dsimcha@yahoo.com


It appears that using the .remove function to remove an element from an associative array does not always work when iterating over the AA with a foreach loop.  Some elements are removed and some aren't.  This issue appears on both DMD 2.017 and DMD 1.033.  It also occurs on GDC 0.24, indicating that it's a front end issue.

Here are two test cases:

//This one works.
import std.stdio;

void main () {
    uint[uint] stuff;
    for(uint i = 0; i < 10_000; i++) {
        stuff[i] = i;
    }
    writefln(stuff.length);  //Should be 10_000.
    foreach(k; stuff.keys) {  //Only this line is different between cases.
        stuff.remove(k);
    }
    writefln(stuff.length);  //Should be 0.  Is.
}

//This one doesn't.
import std.stdio;

void main () {
    uint[uint] stuff;
    for(uint i = 0; i < 10_000; i++) {
        stuff[i] = i;
    }
    writefln(stuff.length);  //Should be 10_000.
    foreach(k, v; stuff) {  //Only this line is different between cases.
        stuff.remove(k);
    }
    writefln(stuff.length);  //Should be 0.  Actually is about 4_000.
}


-- 

http://d.puremagic.com/issues/show_bug.cgi?id=2255


shro8822@vandals.uidaho.edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |INVALID




------- Comment #1 from shro8822@vandals.uidaho.edu  2008-07-30 16:35 -------
http://www.digitalmars.com/d/1.0/statement.html#ForeachStatement

"The aggregate must be loop invariant, meaning that elements to the aggregate cannot be added or removed from it in the NoScopeNonEmptyStatement."


-- 

http://d.puremagic.com/issues/show_bug.cgi?id=2255





------- Comment #2 from dsimcha@yahoo.com  2008-07-30 16:42 -------
Sorry, didn't think of that.  My apologies.


-- 

http://d.puremagic.com/issues/show_bug.cgi?id=2255


davidl@126.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
             Status|RESOLVED                    |REOPENED
         Resolution|INVALID                     |




------- Comment #3 from davidl@126.com  2008-07-30 22:46 -------
Couldn't the compiler jump out and bark?
It can emit something like : you can't modify variable 'stuff'


-- 

http://d.puremagic.com/issues/show_bug.cgi?id=2255


shro8822@vandals.uidaho.edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P2                          |P3




------- Comment #4 from shro8822@vandals.uidaho.edu  2008-07-31 11:55 -------
there are about 3 cases where it could pick up on that and about 2 billion that it can't. I'd rather see time spent on bug fixes than this.


-- 

http://d.puremagic.com/issues/show_bug.cgi?id=2255


Andrej Mitrovic <andrej.mitrovich@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |andrej.mitrovich@gmail.com


--- Comment #5 from Andrej Mitrovic <andrej.mitrovich@gmail.com> 2011-05-24 22:39:57 PDT ---
Is it agreed that removing keys while traversing hashes is something you should never do? I could add some documentation on the AA page about this, if that's what everyone agrees to.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=2255


Jonathan M Davis <jmdavisProg@gmx.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jmdavisProg@gmx.com


--- Comment #6 from Jonathan M Davis <jmdavisProg@gmx.com> 2011-05-24 22:53:28 PDT ---
As I understand it, it is unsafe to remove members of an AA while iterating over it - and that includes unsafe in the memory sense. Perhaps something needs to be done so that it doesn't risk memory issues, but I wouldn't expect it to ever become something that would be expected to work (just not cause problems with memory). So, adding it to the docs would probably be a good idea.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=2255



--- Comment #7 from bearophile_hugs@eml.cc 2011-05-25 03:20:31 PDT ---
This is similar Python2.6 code:


stuff = {}
for i in xrange(10000):
    stuff[i] = i
print len(stuff) # Should be 10_000
for k in stuff:  # Only this line is different between cases
    del stuff[k]
print len(stuff) # Should be 0


If you try to run it Python prints:

10000
Traceback (most recent call last):
  File "...\test.py", line 5, in <module>
    for k in stuff:  # Only this line is different between cases
RuntimeError: dictionary changed size during iteration


The underlying C implementation of this is simple: Python initializes a boolean flag when you scan a dict/set with a for. And the del statement tests that flag every time it is called. Such flag and test were added to Python because this is a common mistake for new Python programmers, and Python tries hard (successfully) to prevent the most common bugs.

That Python error message is useful not just to avoid a bug, but also to teach new programmers to be aware of this problem more in general, even in other languages that don't give this error message.

In D it's probably possible to set a flag of the associative array every time the associative array iteration functions are used. But testing this flag every time AA.remove()/AA.clear() get called is a bit costly for a system language. A compromise is to set and test this flag only when you compile your code in non-release mode, using a runtime assert. I think this may be acceptable and it helps avoid some bugs (but to do this the associative array code needs to be recompiled every time, it can't be in a statically compiled library).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------