[Issue 4179] New: Deleting items from an associative array iterated over

[d-bugmail at puremagic.com]

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

           Summary: Deleting items from an associative array iterated over
           Product: D
           Version: future
          Platform: x86
        OS/Version: Windows
            Status: NEW
          Severity: normal
          Priority: P2
         Component: druntime
        AssignedTo: sean at invisibleduck.org
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2010-05-12 13:00:32 PDT ---
This D2 program deletes items from an associative array while it is iterated
over with a foreach:


import std.stdio: writeln;
void main() {
    auto aa = [1: "one", 2: "two", 3: "three"];
    int count;
    foreach (k, v; aa) {
        count++;
        if (v == "two")
            aa.remove(k);
    }

    writeln(aa);
    writeln("count:", count);
}


The output, with DMD v.2.045:

[1:one,3:three]
count:104


The output shows this code deletes the item correctly from the associative
array, but I am not so sure it can work in general. In general this can be
unsafe (buggy, bad, wrong) code.

And the value of 'count' at the end is too much large, it can be a bug in the
associative array iteration.

----------------------

This is an alternative version of that program:


import std.stdio: writeln;
void main() {
    auto aa = [1: "one", 2: "two", 3: "three"];
    foreach (k; aa.byKey()) {
        if (aa[k] == "two")
            aa.remove(k);
    }

    writeln(aa);
}


When compiled with DMD v.2.045 it prints at run-time:
core.exception.RangeError at test(5): Range violation

----------------------

Python avoids that probable programmer error (iterating over an associative
array being modified) and troubles with an esplicit safety and error message:


aa = {1: "one", 2: "two", 3: "three"}
for k in aa:
    if aa[k] == "two":
        del aa[k]


Python 2.6.5 prints:

Traceback (most recent call last):
  File "...\test.py", line 2, in <module>
    for k in aa:
RuntimeError: dictionary changed size during iteration


To do this they set a flag when the Python dictionary is iterated over, and
reset it later. Probably there is a way to circumvent this safety protection,
but in most cases it is enough to avoid bugs, especially in simple code written
by novices (that is the code that more often presents this error).

Introducing the same safety measure in D can be useful, especially for code
written by novices, safety belts are good, but it can slow down a little the
deletion of items from the associative array. To totally avoid this performance
problem this safety can be disabled when the code is compiled in release mode.

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