https://d.puremagic.com/issues/show_bug.cgi?id=12218

           Summary: [AA] inserting into associative array invalidates
                    foreach iteration
           Product: D
           Version: D2
          Platform: All
               URL: http://dlang.org/hash-map.html
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: nobody@puremagic.com
        ReportedBy: gassa@mail.ru


--- Comment #0 from Ivan Kazmenko <gassa@mail.ru> 2014-02-21 09:47:49 PST ---
I have this piece of code.  It creates an associative array of integers from 1
to 124, inclusive, where a[i] = i.  It then proceeds by iterating over that
array and adding (k+1, v+1) pair to the same array for each (k, v) pair we see.
 This breaks in a reproducible manner.  I understand this was perhaps not
intended to work.  Even if so, there are some points of concern: memory safety,
lack of documentation and the possibility for improvement.

-----
import std.exception;
import std.stdio;

/* @safe */ void main ()
{
    int lo = 1;
    int hi = 125;
    writeln ("start ", lo, " ", hi);
    int [int] a;
    foreach (i; lo..hi)
    {
        a[i] = i;
    }
    foreach (k, v; a)
    {
        writeln ("element ", k, " ", v);
        enforce (k == v);
        a[k + 1] = v + 1;
    }
}
-----

The typical output on Win32 with DMD, GDC and LDC is:
-----
start 1 125
element 31 31
element 62 62
element 93 93
element 124 124
element 273870408 2048
-----
And then, the enforcement fails.

The first number 273870408 on the last line of output can be 1404296, 3616704 or some other number.  The second number seems to always be 2048.  In short, a (key, value) pair of garbage values is added into the array.  What happens is perhaps reallocation of the array when its size reaches around 127 or 128 elements, and the foreach loop does not get to learn the new location of the data.

The points that concern me are memory safety, lack of documentation and the possibility for improvement.

1. @safe?

This is not exactly memory safe: the program ends up using uninitialized memory.  The junk number (like 273870408) appears in the array out of nowhere. Yet, the compiler permits writing "@safe void main ()" once we comment out the calls to writeln.  Perhaps this piece of uninitialized memory could well appear under the "ptr" field of some dynamic array if the declaration was slightly more complex than "int [int]", and that would lead to memory corruption.

2. Undocumented?

There is no warning on the associative arrays documentation page (http://dlang.org/hash-map.html).  There are a few bug reports and discussions stating that one can not safely *remove* elements while iterating on an associative array.  Yet, I didn't find any report which stated the same problems when *adding* items to an associative array.

Perhaps adding while iterating is not a much used feature: there is no guarantee that the newly added (key, value) pairs will or will not be visited in the foreach loop.  Still, it can be useful in some situations where the insertion of new elements is somehow idempotent: for example, we add no more than one single special key in the course of the foreach loop.

Even if such usage is unintended, a friendly way to handle it would be a warning on the documentation page, and maybe a compile-time error in simply visible cases, like the example above.

3. Possible to improve?

The C++ STL documentation for set and map explicitly states that (an example quote from http://www.sgi.com/tech/stl/set.html):

-----
Set has the important property that inserting a new element into a set does not invalidate iterators that point to existing elements. Erasing an element from a set also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.
-----

The implementation of hash_set by Microsoft also boasts a similar feature (http://msdn.microsoft.com/en-us/library/bb398039.aspx):

-----
Moreover, inserting an element invalidates no iterators, and removing an element invalidates only those iterators which point at the removed element.
-----

These quotes suggest that it might be possible to maintain correctness of such foreach loops in D, too, while preserving efficiency.

Ivan Kazmenko.

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

https://d.puremagic.com/issues/show_bug.cgi?id=12218


Ivan Kazmenko <gassa@mail.ru> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://d.puremagic.com/iss
                   |                            |ues/show_bug.cgi?id=4179,
                   |                            |https://d.puremagic.com/iss
                   |                            |ues/show_bug.cgi?id=10876


--- Comment #1 from Ivan Kazmenko <gassa@mail.ru> 2014-02-21 10:04:50 PST ---
This report is a reduction of the case that bit me during a programming contest: Google Code Jam 2013, Round 1B, problem C.

The problem statement: http://code.google.com/codejam/contest/2434486/dashboard#s=p2

My faulty solution: code.google.com/codejam/contest/scoreboard/do?cmd=GetSourceCode&contest=2434486&problem=2705486&io_set_id=1&username=Gassa

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

https://d.puremagic.com/issues/show_bug.cgi?id=12218



--- Comment #2 from Ivan Kazmenko <gassa@mail.ru> 2014-02-28 01:45:01 PST ---
Created an attachment (id=1333)
program to find a reduced test case

Well, 124 numbers sound like much, but the test case presented above is the most reduced example I came up with.  I attached the program used to find such a test case.  Basically, it just adds an interval [lo; hi] into an associative array and then iterates on the array.  The second similar array is also created to make the breakage more likely because of data relocation, but it turns out to be unnecessary.

On the bright side, the original broken program processes several megabytes of text, so some reduction did in fact take place.

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

https://d.puremagic.com/issues/show_bug.cgi?id=12218



--- Comment #3 from Ivan Kazmenko <gassa@mail.ru> 2014-02-28 01:47:43 PST ---
Created an attachment (id=1334)
reduced test case printing diagnostic messages

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

https://d.puremagic.com/issues/show_bug.cgi?id=12218



--- Comment #4 from Ivan Kazmenko <gassa@mail.ru> 2014-02-28 01:48:39 PST ---
Created an attachment (id=1335)
reduced test case as a safe function - which it is not!

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

https://d.puremagic.com/issues/show_bug.cgi?id=12218


Ivan Kazmenko <gassa@mail.ru> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Attachment #1333|application/octet-stream    |text/plain
          mime type|                            |


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

https://d.puremagic.com/issues/show_bug.cgi?id=12218


Ivan Kazmenko <gassa@mail.ru> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Attachment #1334|application/octet-stream    |text/plain
          mime type|                            |


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

https://d.puremagic.com/issues/show_bug.cgi?id=12218


Ivan Kazmenko <gassa@mail.ru> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Attachment #1335|application/octet-stream    |text/plain
          mime type|                            |


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

https://d.puremagic.com/issues/show_bug.cgi?id=12218


yebblies <yebblies@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |yebblies@gmail.com


--- Comment #5 from yebblies <yebblies@gmail.com> 2014-03-01 01:21:53 EST ---
I can confirm this was not intended to work, and it most likely never will.  It should be possible for the compiler to detect this and give you an error.

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

https://d.puremagic.com/issues/show_bug.cgi?id=12218


bearophile_hugs@eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs@eml.cc


--- Comment #6 from bearophile_hugs@eml.cc 2014-02-28 06:35:25 PST ---
(In reply to comment #5)
> I can confirm this was not intended to work, and it most likely never will.  It should be possible for the compiler to detect this and give you an error.

Yes, while fixing it in general is probably not possible, giving a good compile-time error is a good thing.

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