www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 2255] New: AA.remove() doesn't remove AA element when iterating using foreach

reply d-bugmail puremagic.com writes:
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.
}


--
Jul 30 2008
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=2255


shro8822 vandals.uidaho.edu changed:

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





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."


--
Jul 30 2008
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=2255






Sorry, didn't think of that.  My apologies.


--
Jul 30 2008
prev sibling next sibling parent d-bugmail puremagic.com writes:
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                     |





Couldn't the compiler jump out and bark?
It can emit something like : you can't modify variable 'stuff'


--
Jul 30 2008
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=2255


shro8822 vandals.uidaho.edu changed:

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





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.


--
Jul 31 2008
prev sibling next sibling parent d-bugmail puremagic.com writes:
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



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: -------
May 24 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=2255


Jonathan M Davis <jmdavisProg gmx.com> changed:

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



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: -------
May 24 2011
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=2255




This is similar Python2.6 code:


stuff = {}
for i in xrange(10000):
    stuff[i] = i


    del stuff[k]



If you try to run it Python prints:

10000
Traceback (most recent call last):
  File "...\test.py", line 5, in <module>

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: -------
May 25 2011