[Issue 10821] .byKey erroneously returns a null key

[d-bugmail at puremagic.com]

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



--- Comment #4 from hsteoh at quickfur.ath.cx 2013-08-17 09:20:44 PDT ---
I don't know if it's possible to make hash iteration stable across deletes.
This isn't specific to hashes either; any data structure involving pointers
will have this problem. If you have an iterator pointing to bucket B1, and then
you delete B1 from inside the delegate and then try to advance the iterator,
you will run into this problem.

Even if you use an array to store your func ptrs, say, and keep an array index
to track where you are. If you then delete the current element from inside the
delegate and move the array elements up to fill in the gap, the loop wouldn't
know about it, and would increment the index, skipping over what was supposed
to be the next element. So your iteration breaks (even though in this case you
won't get invalid pointers). It may be possible to hack around this particular
instance of the problem, say by checking if the entry at the current index has
changed, but it doesn't help in the general case, say if your delegate removes
multiple entries from the array. Either way, your iteration will be screwed up.

Basically, it's impossible to have straightforward iteration when you're
modifying the container in the middle of things. Even your approach of using
.key to get an array of keys is not reliable -- imagine if the delegate deletes
some of the subsequent keys that you're about to visit. Then you'll get
RangeErrors because the keys in the array no longer exist in the AA.

I've had to deal with code that has to iterate over an array (or hash) of
callbacks before (this was in C++ not D, but the same issues apply). I found
that the only way to keep things consistent without strange side-effects was to
keep a list of to-be-deleted entries separately, and the delegate would never
modify the array of callbacks directly, but would append itself to the
to-be-deleted list if it wants to remove itself. Then during the iteration,
anything that is found in the to-be-deleted list is skipped, and after the
iteration is finished, then loop through the to-be-deleted list and actually
delete the entries.

This kind of issue gets worse if the delegates have the possibility of
triggering the destruction of the entire container. This is not applicable to
your code, but I had to deal with this when writing a protocol stack with
callback handlers -- the stack itself doesn't handle things like logout, it's
all handled by callbacks, which makes it very tricky when one of the callbacks
may be the logout handler, which will cleanup by destructing the entire
protocol stack. Upon returning to the protocol stack code that called the
callback in the first place, all references to the stack instance are now
invalid, so basically callbacks must be called after everything else has been
processed, otherwise it will segfault if the callback happens to be the logout
handler. This code is so tricky that even years after I wrote it I still have
to go back and fix subtle bugs in it every so often.

tl;dr: modifying a container while iterating over it is tricky business, and is
best avoided if you can. :)

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