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

           Summary: .byKey erroneously returns a null key
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: critical
          Priority: P2
         Component: DMD
        AssignedTo: nobody@puremagic.com
        ReportedBy: andrej.mitrovich@gmail.com


--- Comment #0 from Andrej Mitrovic <andrej.mitrovich@gmail.com> 2013-08-14 15:14:26 PDT ---
-----
import std.stdio;

struct Signal
{
    void connect(void delegate(int) func)
    {
        stderr.writefln("Func connect: %s", *cast(void**)&func);
        funcs[func] = 1;
    }

    void disconnect(void delegate(int) target)
    {
        stderr.writefln("Func disconnect: %s", *cast(void**)&target);
        funcs.remove(target);
    }

    void emit(int i)
    {
        version(VERSION_OK)
        {
            foreach (func; funcs.keys)
            {
                stderr.writefln("Calling: %s", *cast(void**)&func);
                func(i);
            }
        }
        else
        version(VERSION_CRASH)
        {
            foreach (func; funcs.byKey)
            {
                stderr.writefln("Calling: %s", *cast(void**)&func);
                func(i);
            }
        }
    }

    int[void delegate(int)] funcs;
}

void main()
{
    Signal signal;

    void delegate(int) handler;
    handler =
        (int i)
        {
            signal.disconnect(handler);
        };

    signal.connect(handler);

    signal.emit(1);
    signal.emit(2);
}
-----

Ok version:

$ dmd -version=VERSION_OK -run test.d
> Func connect: 1BF2FF0
> Calling: 1BF2FF0
> Func disconnect: 1BF2FF0

Buggy version:

$ dmd -version=VERSION_CRASH -run test.d
> Func connect: 482FF0
> Calling: 482FF0
> Func disconnect: 482FF0
> Calling: null
> object.Error: Access Violation

It should have never called 'null', I don't know why byKey seems to return it after the delegate was removed from the associative array.

This does not seem to be a regression (tested up to 2.050).

-- 
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 #1 from hsteoh@quickfur.ath.cx 2013-08-16 22:20:55 PDT ---
Even more strange: comment out the line that calls func(i), and suddenly the writefln displays a non-null address! A codegen bug perhaps?

-- 
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 #2 from hsteoh@quickfur.ath.cx 2013-08-16 22:23:00 PDT ---
Oh actually, nevermind, the delegate removed itself from the hash.

Ahhh, I see what's going on. You're modifying the AA while iterating over it. That's very bad, because byKey is implemented using a pointer to the current Slot. But once the delegate removes itself from the table, this pointer is invalidated. That's the bug in your code. :)

-- 
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 #3 from Andrej Mitrovic <andrej.mitrovich@gmail.com> 2013-08-17 01:59:09 PDT ---
(In reply to comment #2)
> Oh actually, nevermind, the delegate removed itself from the hash.
> 
> Ahhh, I see what's going on. You're modifying the AA while iterating over it. That's very bad, because byKey is implemented using a pointer to the current Slot. But once the delegate removes itself from the table, this pointer is invalidated. That's the bug in your code. :)

Oh damn, I can't believe I've run into this hash issue again. And it's very hard to spot too. I hope we can make new hashes which are not unstable like this. Hows your new hashes branch going?

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


Andrej Mitrovic <andrej.mitrovich@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |INVALID


-- 
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 #4 from hsteoh@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: -------

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



--- Comment #5 from Andrej Mitrovic <andrej.mitrovich@gmail.com> 2013-08-17 11:00:42 PDT ---
(In reply to comment #4)
> 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.

Hmm yeah, it gets complicated real fast. Thanks for the insight.

So here's a quick safer workaround implementation:

-----

struct Signal
{
    void connect(void delegate(int) func)
    {
        if (emitting)
        {
            funcsToAdd[func] = 1;
        }
        else
        {
            stderr.writefln("Func connect: %s", *cast(void**)&func);
            funcs[func] = 1;
        }
    }

    void disconnect(void delegate(int) func)
    {
        if (emitting)
        {
            funcsToDelete[func] = 1;
        }
        else
        {
            stderr.writefln("Func disconnect: %s", *cast(void**)&func);
            funcs.remove(func);
        }
    }

    void emit(int i)
    {
        emitting = true;
        scope(exit) emitting = false;

        foreach (func; funcs.byKey)
        {
            stderr.writefln("Calling: %s", *cast(void**)&func);
            func(i);
        }

        foreach (func; funcsToDelete.byKey())
            funcs.remove(func);

        funcsToDelete = null;

        foreach (func; funcsToAdd.byKey())
            funcs[func] = 1;

        funcsToAdd = null;
    }

    int[void delegate(int)] funcs;
    int[void delegate(int)] funcsToAdd;
    int[void delegate(int)] funcsToDelete;
    bool emitting;
}

void main()
{
    Signal signal;

    void delegate(int) handler;
    handler =
        (int i)
        {
            signal.disconnect(handler);
        };

    signal.connect(handler);

    signal.emit(1);
    signal.emit(2);
    signal.emit(3);
    signal.emit(4);
}
-----

Of course this still isn't perfect, there's no telling what a signal handler really wants to do, whether it actually wants to add/remove some other handler immediately or only schedule add/removal for later.

I guess the bottom line is this stuff is more complicated than I thought. I wonder if that new signals implementation recently announced handles this sort of stuff.

-- 
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 #6 from hsteoh@quickfur.ath.cx 2013-08-17 11:55:32 PDT ---
(In reply to comment #5)
[...]
> Of course this still isn't perfect, there's no telling what a signal handler really wants to do, whether it actually wants to add/remove some other handler immediately or only schedule add/removal for later.

I think the only safe way is to always process adds/deletes immediately after iterating over the current handlers. Adds/removes for later can use a timer mechanism. Modifying a container while iterating over it is never a good idea. :)


> I guess the bottom line is this stuff is more complicated than I thought. I wonder if that new signals implementation recently announced handles this sort of stuff.

Well, it should be audited for this, then. :) It should be fixed if it doesn't already handle this.

-- 
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 #7 from Andrej Mitrovic <andrej.mitrovich@gmail.com> 2013-08-17 12:30:29 PDT ---
(In reply to comment #6)
> Modifying a container while iterating over it is never a good idea.

However some containers explicitly support this, like dcollections.

-- 
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 #8 from hsteoh@quickfur.ath.cx 2013-08-17 13:17:55 PDT ---
It does not eliminate the bad behaviour though. Suppose you're iterating over a RedBlackTree, and then add and delete some keys. Depending on whether those keys are greater or less than the current key, they will be included / excluded from the current iteration. So whether the key will be found in the current iteration depends on the relative values of the current key and the key being added/deleted, and there's no way to change this apart from scheduling adds/deletes after the iteration is over.

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