[Issue 10821] .byKey erroneously returns a null key

[d-bugmail at puremagic.com]

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



--- Comment #13 from hsteoh at 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: -------