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



--- Comment #9 from hsteoh@quickfur.ath.cx 2013-08-17 13:19:20 PDT ---
Besides, if you're iterating a RedBlackTree and then in the middle you delete all keys, I bet that your iteration will break in a rather ugly way. :)

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

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



--- Comment #10 from Andrej Mitrovic <andrej.mitrovich@gmail.com> 2013-08-17 14:36:30 PDT ---
(In reply to comment #8)
> It does not eliminate the bad behaviour though. Suppose you're iterating over a RedBlackTree, and then add and delete some keys.

I was thinking of the purge method in various dcollection containers (purge doesn't seem to be in Phobos), it's explicitly used for removal during traversal.

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

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



--- Comment #11 from hsteoh@quickfur.ath.cx 2013-08-17 15:15:12 PDT ---
Sorry, I mistakenly thought you were talking about std.container. :-/

Anyway, looking over the dcollections code, I'm pretty impressed to realize that foreach can take function pointers?! That's something I've never knew before!

In any case, purge is basically a restricted form of container modification while iterating -- it iterates over the elements and lets you decide whether or not to remove each one. This is a more controlled form of container modification during iteration, and is made safe by (1) (implicitly) caching the reference to the next element and not advancing the iterator if the element *was* elected to be removed, and (2) only allowing the current element to be removed, not any arbitrary element. If you relax (2), say your foreach body directly references the container and deletes random elements, then all hell breaks loose. If you enforce (2), then you can use (1) as implementation strategy to allow deletion during iteration.

So one possibility in the case of your signal/slot code, is to have the delegate return a bool/flag to indicate whether to remove itself from the table. That way, you can avoid keeping lists of what to remove after the iteration. It won't be as nice as a foreach loop, though, since you have to manually control where your iterator is:

    auto r = aa.byKey;
    while (!r.empty) {
        auto key = r.front;
        auto dg = aa[key];
        bool deleteDg = dg(args) == Flag.deleteMe;
        r.popFront(); // important: this must come before aa.remove(key)
        if (deleteDg == Flag.deleteMe) {
            aa.remove(key);
        }
    }

By advancing the range before the aa.remove(key) call and only allowing the current element to be deleted, you avoid running into invalid pointers.

This doesn't address the problem with dg inserting new things into aa, though, since the newly inserted entry may or may not get iterated over by the loop depending on where its hash value falls relative to the current position of the byKey range. So there's still some unpredictability there.

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

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



--- Comment #12 from Andrej Mitrovic <andrej.mitrovich@gmail.com> 2013-09-02 13:53:50 PDT ---
Btw, Slist has a stableLinearRemove, which Phobos documents as:

stableLinearRemove - same as linearRemove, but guarantees iterators are not invalidated.

That sounds like this pseudocode is safe:

-----
auto range = slist[];

foreach (item; range)
{
    // do something

    slist.stableLinearRemove(item);

    // do something
}
-----

Slist are used in a signals implementation by Johannes Pfau. He uses this stableLinearRemove in his disconnect method.

If this is not actually safe, then the docs should be more clear by what they mean.

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

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



--- Comment #13 from hsteoh@quickfur.ath.cx 2013-09-05 12:09:51 PDT ---
Well, linked lists are designed to not invalidate iterators when things are removed. But still, it has the same issue with removing stuff while traversing over the list. For example, say you have a list:

    A -> B -> C -> D -> E

and you have a foreach loop over the list, say foreach(e; myList) { ... }.

Now suppose you have iterated to C. So e is C. Now you remove C from the list. Following the SList code in Phobos, it will result in this list:

    A -> C -> D -> E

which is fine. But since e is C, e.next is now null, so your foreach loop will terminate prematurely. No iterators are invalidated, that's true; any existing references to A, B, C, D, or E will remain valid. However, their connections with each other may change when you modify the container. So still, changing stuff in a container while iterating over it has quirky side-effects. You cannot assume the iteration will go exactly from A to E unless you iterate over a copy of references to the elements.

Let's take this further. Let's say you're in the middle of your foreach loop, and e is C. Let's say for whatever reason you decide to remove the range B..D. The resulting list would now be:

    A -> E

But since e is C, it is now pointing to a removed section of the list:

    B -> C -> D
         ^
         e

So e.next is D, and the next iteration of the loop will be on D (which no longer exists in the container!). And after that, it stops, because D is no longer connected to E. So again, your iteration has "non-intuitive" behaviour.

All hope is not lost, though. There *is* a way to guarantee "intuitive" iteration over the container while still being able to delete elements during the iteration. This is possible if you impose the restriction that you can only remove the *current* element being iterated over. That is, you're not allowed to remove arbitrary elements from the container (or add new elements while you're at it, or modify the container in any other way). Here's how:

    Element e = list.front;
    while (e)
    {
        if (wantToRemove(e))
        {
            auto tmp = e.next;
            list.remove(e);
            e = tmp;
        }
        else
            e = e.next;
    }

Unfortunately, there is no nice syntax for this, and you have to depend on the implementation details of the container to get it right.

One way to make it nicer is for the container to provide opApply, so that the dirty details of what to do while removing the current element is abstracted away:

    struct MyList
    {
        ...
        int opApply(scope int delegate(ref Element, out bool removeMe) dg)
        {
            Element e = list.front;
            while (e)
            {
                bool removeMe = false;
                int ret;
                if ((ret = dg(e, removeMe)) != 0)
                    return ret;

                if (removeMe)
                {
                    auto tmp = e.next;
                    this.remove(e);
                    e = tmp;
                }
                else
                    e = e.next;
            }
        }
    }

Then user code won't have to worry about the implementation details:

    void main() {
        MyList l = ...;
        foreach (ref e, ref removeMe; l) {
            removeMe = wantToRemove(e);
        }
    }

This is, in effect, what DCollections does.

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

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



--- Comment #14 from hsteoh@quickfur.ath.cx 2013-09-05 12:11:44 PDT ---
Argh, I hate bugzilla not having an edit function... the first example in my previous comment, after removing C, should have the list:

    A -> B -> D -> E

not

    A -> C -> D -> E

Sorry for the confusion.

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