Bug 4179 – [AA] Deleting items from an associative array iterated over

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

It's an enhancement, mostly.

To implement this idea the foreach() has to change a little, in nonrelease mode it has to set and later reset a boolean flag inside the container being iterated. So this boolean value if present must have a standard name, that has to be shown in the std.container page about the standard API of the container. If implemented this idea lessens a little the need for the stable ("soft") methods.

Considering that this bug breaks safety of SafeD programs, it is definitely much more severe than an "enhancement".

SafeD refers to memory safety. The current behavior is completely memory safe. The same could happen with any container whose iterators/ranges are invalidated by the removal of an element from the container. It would be nice if removing elements from an AA while looping over it worked, but it's not at all surprising that it doesn't, and it may not be reasonable to require that it does. And it's easy enough to get around this. You just save a list of the items that you want to remove, and then you remove them after you're done iterating over the AA. There's nothing unsafe about the current behavior. It may be a bit bug-prone for the unwary, but this sort of things is normal when dealing with iterators or ranges. If it were unsafe, it wouldn't be throwing a RangeViolation but would keep trying to iterate using invalid data and do who-knows-what.

Eh? Is getting a segfault because the data structure has been modified considered "safe"? The workaround you suggested doesn't work when removing happens several calls deep in the call hierarchy.

segfault? I didn't think that anyone was getting a segfault from this. If there's a segfault, then that's obviously bad. I'm not sure that it's technically unsafe though. That would depend on whether it could possibly corrupt memory. If it's guarantee to segfault and never corrupt memory, then I don't believe that it's technically unsafe and therefore would not be a problem for SafeD. Still, one would hope that it could do better than a segfault. I thought that it was throwing an exception though. If it's segfaulting, that would put increased pressure on either flagging it as a warning or fixing it so that it's not necessary (but that may not be reasonable if you want AA's to be reasonably efficient - I don't know how iterating over them is implemented). However, if it's a segfault with no risk of memory corruption, then it's still perfectly safe, just annoying.

It's unsafe. The issue is that if you remove the element being iterated, it goes back to the memory pool. Here is the code that removes an element: https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d#L373 Note on line 402, the unused node is free'd using gc_free. The only way I know to make it safe is letting the iteration routine remove the current element at the right time . Dcollections allows this. The only way to solve this other than that is to keep a modification id, and throw an error if the iteration discovers the array structure has been modified during iteration. A compiler error or warning will not help, because the compiler cannot know whether a called function is going to modify the AA, or if two AA references point to the same object.

There are more possible ways to make it safe than this. One way is to have a list of current iterations associated with each AA. Any time an item is removed, any current iterations are also updated. The nodes of the list can be stored on the stack of aaApply or whatever function does the "foreach" for AAs. It can be as simple as one pointer in the AA structure, and a structure with two fields ("current iteration item" / "next list node") on the stack - this should allow everything to "just work" and have a small impact on performance. Alternatively, when items are removed from an AA they can be left for the GC to collect rather than deleted explicitly, and their "next" pointer can be set to a magic value indicating that they were deleted (e.g. cast(void*)1).

(In reply to comment #8) > There are more possible ways to make it safe than this. > > One way is to have a list of current iterations associated with each AA. Any > time an item is removed, any current iterations are also updated. The nodes of > the list can be stored on the stack of aaApply or whatever function does the > "foreach" for AAs. It can be as simple as one pointer in the AA structure, and > a structure with two fields ("current iteration item" / "next list node") on > the stack - this should allow everything to "just work" and have a small impact > on performance. > > Alternatively, when items are removed from an AA they can be left for the GC to > collect rather than deleted explicitly, and their "next" pointer can be set to > a magic value indicating that they were deleted (e.g. cast(void*)1). My suggestion was for the foreach to set a boolean flag inside the associative array, and reset it when the foreach ends. Then the AA.delete should look for this flag and throw an exception if it's set.

*** Issue 10876 has been marked as a duplicate of this issue. ***

See discussion on issue #10821. Modifying a container while iterating over it is tricky business; generally, it leads to a lot of counterintuitive behaviours. This is not just specific to AA's; it applies to many containers that are not designed to support such an operation. For example, let's say we have linked list that contains the following elements: HEAD --> A --> B --> C --> D --> E --> null Under a normal iteration scheme, the iteration order would be A, B, C, D, E. Now, suppose we iterate over this list and when we're at C, we remove it from the list. The list now looks like this: HEAD --> A --> B --> D --> E --> null Now, in theory, the next element in our iteration should be D, since it comes after C. However, since the current pointer points to C, and the list .remove method has set it to null (because it has relinked D to follow B), pointer.next is now null, and our iteration stops prematurely. Suppose we solve this problem by keeping a copy of pointer.next before we enter the loop body. Then the above case works, but a different case fails: suppose when we're at C, and we delete D. The list then becomes: HEAD --> A --> B --> C --> E --> null In theory, the next step of our iteration should be E. But since we kept a copy of the original value of C.next, it is still pointing at D, so in the next iteration of our loop, we will end up at D, even though it has already been deleted from the list. Worse yet, D.next has been set to null, because it's no longer in the list (E is now the successor of C). So then our iteration stops after D, and we get the counterintuitive iteration sequence A, B, C, D instead of the expected A, B, C, E. These are just two simple cases illustrating the counterintuitiveness of modifying a container as you iterate over it. There are many other such cases (I'm sure you can think of more quite easily). Even with a simple structure like linked lists, there's already strange cases and odd behaviours. Now consider what happens if you're in the middle of iterating over an AA, and then you decide to add/remove a key, and it just so happens to cause a rehash to happen. Now all of your .next pointers are wrong, and your subsequent iteration will basically end up in a strange random order that may skip some elements or see elements that should have already been deleted. Rehash is a pretty drastic example, but even with a simple insert, strange things can happen: if the new key is hashed to a bucket past the point of your current iteration, then your iteration will see the new key eventually; but otherwise, you'll miss the new key. Since the hash function is random, this means you'll sometimes see newly inserted keys in your iteration, sometimes you won't, and this is unpredictable. OK, you say, so instead of using .byKey, let's use .keys, which creates a copy of the current set of keys, then use that to iterate over the AA. This will make it resistant to odd behaviour caused by AA modifications during iteration. But if you delete some keys from the AA, the array of keys that you're iterating over isn't updated, so you may end up getting RangeErrors when you get to those stale keys. Basically, if you allow arbitrary modification of the container while you iterate over it, you will always have strange cases that cause unexpected (or counterintuitive) behaviours. With respect to deleting keys when iterating over a container, there's only one case where "intuitive" behaviour is guaranteed: the container must be designed to support deletion during iteration, and deletion is restricted to only the current element in the iteration. In this case, the rest of the container remains (conceptually) unchanged, so as long as the container itself has the necessary support mechanisms for this operation, it will result in the expected behaviour (your iteration won't stop prematurely, you won't see already-deleted items, etc.). If the container does not support such operations, or if you delete something other than the current element in the iteration, then there will always be cases where it exhibits counterintuitive behaviour. You can only get around this with workarounds like maintaining a list of postponed adds/deletes, which get applied after the iteration is finished. But any time you directly modify a container while iterating over it, be prepared to handle "odd" behaviours.

We've just had this issue at work, looks like undefined behavior. An associative array with keys deleted during iteration caused crashes without stack trace and without core dump. The right thing here is to throw an exception if an AA is removed from during an iteration.

(In reply to Andrei Alexandrescu from comment #12) > We've just had this issue at work, looks like undefined behavior. An > associative array with keys deleted during iteration caused crashes without > stack trace and without core dump. > > The right thing here is to throw an exception if an AA is removed from > during an iteration. Not just removal. Even *adding* (not deleting) elements to associative array can cause reallocation and undefined behavior as well: https://issues.dlang.org/show_bug.cgi?id=12218

We can rewrite the rehash code to rely more on GC destruction, or alter the opApply/range code to be safer. Perhaps this is the right thing to do regardless. This will probably result in AA's being more likely to cause false pointers.

THIS ISSUE HAS BEEN MOVED TO GITHUB https://github.com/dlang/dmd/issues/17225 DO NOT COMMENT HERE ANYMORE, NOBODY WILL SEE IT, THIS ISSUE HAS BEEN MOVED TO GITHUB