Missing event when combining <@>, filterE, fmap, union, and collect

[gelisam]

The following looks complicated, so let me begin by proving that this is a real bug: this is a situation where adding a call to fmap id changes the number of events produced by the program!

The reason it is complicated is because it need to be: many different pieces are needed in order to trigger the issue. If I remove the fmap id, or the useless looking filterE (const True), or the seemingly unrelated "filtered event" part of the output, the bug disappears.

All right, so here's the code.

{-# LANGUAGE ScopedTypeVariables #-}
module Main where

import Reactive.Banana
import Reactive.Banana.Frameworks


network :: forall t. Event t () -> Event t String
network inputEvent = outputEvent
  where
    appliedEvent :: Event t Int
    appliedEvent = (\_ _ -> 0) <$> lastValue <@> inputEvent

    filteredEvent :: Event t Int
    filteredEvent = filterE (const True) appliedEvent

    fmappedEvent :: Event t Int
    fmappedEvent = fmap id (filteredEvent)

    outputEvent :: Event t String
    outputEvent = (const "filtered event" <$> filteredEvent)
          `union` (show <$> collect (appliedEvent `union` fmappedEvent))

    lastValue :: Behavior t Int
    lastValue = stepper 1 $ fmappedEvent

main :: IO ()
main = do
    (addHandler, fire) <- newAddHandler
    register (interpretAsHandler network addHandler) putStrLn
    fire ()

So as the single inputEvent is fired, an appliedEvent with value 0 occurs in response, as does a filteredEvent and a fmappedEvent, all with the same value. Since all those events are simultaneous and I combine them with union, I expect outputEvent to occur multiple times, once for each side of the union. And indeed, it occurs twice: once with "filtered event", and once with "[0]". But here's the weird thing: if you remove the fmap id, or change almost anything else in the code, the second outputEvent becomes "[0,0]" instead. Which means it's probably the correct value.

If you replace the fmap id with fmap (const 1), the result is still [0], which means that it's the fmappedEvent is lost.

[gelisam]

The most suspicious-looking part of that code, at least to me, was the collect call: there is both a union call inside and outside of the collect, so maybe there is a weird interaction there. But no, turns out the problem is elsewhere: I managed to simplify the example a little bit by removing the collect call.

outputEvent :: Event t String
outputEvent = (const "filtered event" <$> filteredEvent)
      `union` (show <$> appliedEvent `union` fmappedEvent)

With this change, the output is

filtered event
0

Which is incorrect because, again, the fmappedEvent is lost. With fmap (const 1) instead of fmap id and without the filterE (const True), we get the correct result:

filtered event
0
1

[gelisam]

Digging deeper, the cause seems related to caching: if I disable caching in liftCached1 (or, inlining all the combinators into my example code, just the liftCached1 inside filteredEvent or the one inside fmappedEvent) by replacing cache with don'tCache, the bug disappears.

[gelisam]

Bisecting through reactive-banana's history to find the commit which introduced the bug reveals the following.

At the following commit, the "1" event was not dropped, but all three events were duplicated three times. The commit message indicates that this was a known issue at the time.

beade5767229644982284d40f286bdaa31e14457
Author: Heinrich Apfelmus <apfelmus@quantentunnel.de>
Date:   Fri Jan 24 16:41:27 2014 +0100

Reimplement `traverseDependencies` using the queue implementation from `pqueue`.

Testing shows that this implementation is incorrect because it allows duplicate elements.

Then, at the following commit, duplicate elements are removed, but it removed too many, causing the "1" event to disappear.

commit 48d541a89176bebaab1d53fb8f68c42813505b10
Author: Heinrich Apfelmus <apfelmus@quantentunnel.de>
Date:   Fri Jan 24 17:03:10 2014 +0100

`DepsQueue` now implements a queue that keeps track of and disallows duplicate elements.

[gelisam]

I finally found a fix! But I don't understand reactive-banana's internals well enough to know if it's semantically-correct. I'll send a pull request and we can discuss whether that's the right fix in that thread.

[HeinrichApfelmus]

Wow, you've dug quite deep into the code! I'm sorry that I didn't have much time to look into it yet; I will try to make some room in the coming weeks.

My hunch is that DepsQueue should not be fixed as it probably works correctly. Its purpose is to make sure that each Pulse (a primitive form of Event) is only processed whenever all of its dependencies have been processed. Each Pulse is to be processed only once, that's why adding it to the queue again is not correct. (Then again, you note that the tests still pass. I think that recalculating a node, while bad for performance, is semantically a no-op.)

Personally, I would guess that the issue is indeed with the application liftCached1 combinators. These primitives implement observable sharing, which is notoriously finicky and may show up as really weird bugs (like this one. Sometimes it even makes a difference whether you are using GHCi or whether you are compiling the code). I don't remember if I have already implemented a Show instance for this version of reactive-banana; the best way to test whether the issue is here is to check whether the Event and Behavior you wrote are translated into a good set of Pulse and Latch (the Show instance helps with that), or whether there are some events missing.

(Since you note that changing DepsQueue fixes the issue, one possibility is that the priorities were not assigned correctly during the conversion from Event to Pulse.)

[gelisam]

Taking a closer look at the surrounding code, I see that DepsQueue is only used in two places: traverseDependencies (which is never used!) and evaluatePulses. The latter function is called once, with an invalid argument: a child has a level which is smaller than its parent's.

[gelisam]

It's a bug in addChild. Given the following dependency graph deps1 (arrows point from parent to children, the number before the underscore is an ID, the number after the underscore is the level, when there is no underscore it means the element is not listed in the Order a, meaning its level is zero):

The result of deps2 = addChild 63 61 deps1 is:

Note how the level of 63 was and is still 4, the level of its new child 61 was 0 and is now 5, but the level of 86 was and is still 1. But since 86 is a child of 61, it's level should be higher than 5.

[HeinrichApfelmus]

Excellent work so far! There is one problem, though: As far as I can see, the addChild function was indeed intend to add a new child that didn't exist in the hierarchy yet, this precondition preserves the invariant. The function for changing the child of an existing tree would be changeParent. The function addChild is used by dependOn, which in turn is used by Reactive.Banana.Prim.Combinators, but only on new pulses, which should be correct.

Are the pictures you're showing here from the original bug? It may well be that some issue with caching messes up the precondition.

The fix of using changeParent instead of addChild is not advisable as it degrades performance considerably.

[gelisam]

Still not the proper fix? sigh, this will never end...

Are the pictures you're showing here from the original bug?

Yes, I added a validator, some trace calls, and I converted the output to the graphviz format.

[HeinrichApfelmus]

Fear not, your help is greatly appreciated. 😄 The fact that addChild is called in a situation where it shouldn't be called is extremely useful information.

[HeinrichApfelmus]

As I feared, the problem is most likely with recursion and the liftCached combinators. I managed to shorten the example to the following code, which will give a semantically correct result, but whose internal implementation is wrong:

{-# LANGUAGE ScopedTypeVariables #-}

import Reactive.Banana.Combinators

network :: forall t. Event t () -> Event t Int
network inputEvent = filteredEvent
    where
    appliedEvent :: Event t Int
    appliedEvent = lastValue <@ inputEvent

    filteredEvent :: Event t Int
    filteredEvent = filterE (const True) appliedEvent

    lastValue :: Behavior t Int
    lastValue = stepper 1 $ filteredEvent

main :: IO ()
main = interpret network [[]] >>= print

Adding a suitable trace statement to the dependOn function, I get the trace

*Main> main
mapP 519 `dependOn` neverP 35
mapP 517 `dependOn` mapP 519
applyP 513 `dependOn` mapP 519
mapP 509 `dependOn` neverP 35
mapP 507 `dependOn` mapP 509
applyP 503 `dependOn` mapP 509
mapP 499 `dependOn` filterJustP 497
mapP 495 `dependOn` mapP 499
mapP 493 `dependOn` mapP 495
applyP 489 `dependOn` mapP 495
unionWithP 487 `dependOn` mapP 507
unionWithP 487 `dependOn` mapP 493
unionWithP 485 `dependOn` mapP 517
unionWithP 485 `dependOn` unionWithP 487
applyP 483 `dependOn` newInput 527
mapP 481 `dependOn` applyP 483
mapP 479 `dependOn` mapP 481
filterJustP 497 `dependOn` mapP 479
mapP 476 `dependOn` filterJustP 497
mapP 474 `dependOn` mapP 476
[[]]

As @gelisam figured out, there is something wrong with the use of dependOn. In particular, it is wrong to depend on the node labelled filterJustP 497 even though it has not been (fully) created yet! The correct order is

filterJustP 497 `dependOn` mapP 479
...
mapP 499 `dependOn` filterJustP 497

instead of the other way round.

Sorry for this mistake. I find it hard to get the recursive use working with obversable sharing. Will investigate further.