Dependent computation bug

[JAForbes]

Need to create a reduced repro but this flems has the bug link

The fakeDOM computation is listening to groups and list

const fakeDOM = S.computation(() => {
    console.log( list(), groups() )
})

list is a S.data and groups is a computation that depends on indexes which in turn depends on list.

For some reason fakeDOM is not treating groups as a dependency so it only emits when list changes. Interestingly if you change the list call to a sample it works as expected:

const fakeDOM = S.computation(() => {
    console.log( S.sample(list), groups() )
})

I'm guessing during propagation we're taking that computation out of the list of streams to update incorrectly.

[JAForbes]

About to start on this, but I have a theory what the issue is. I don't sort the propagation so maybe a computation runs before its dependency has updated because both the computation and its dependency are scheduled to propagate in the same loop.

I'm pretty sure that will be the issue and if so we can probably avoid a sort by checking "are any of my dependencies scheduled to run still? ok put me at the bottom of the stack".

Maybe I'm wrong but I think I thought of this as. I was writing, but decided not to worry as it may be a hypothetical.

[JAForbes]

Gut instinct was right

Here's a repro:

const b = S.computation(() => {
    return a() * 1
})

const c = S.computation(() => {
    return b() * 2
})

const d = S.computation(() => {
    return a() + c()
})

If a is written to. c will end up latest in the list created by computeDependents because it depends on a via b so it takes 1 step of recursion to identify it as a dependency of a. d on the other hand directly depends on a so it comes before c.

The problem is d also depends on c so it will run before c propagated which means d's computed value is incorrect.

Currently we track what streams depend on a, but we don't track streams that d depends upon. So in the propagation we don't know that d depends on c, we'd only know if any streams depend on d. By the time we get to c we'll know d directly depends on it, but by then d will already have run.

I'm hesitant to create that reverse index, I'm hoping there is a cheeky computer science solution for this. We could probably temporarily create that reverse look up for that tick only when running computeDependents so we can know D depends on C and A and can therefore push it down the queue of updates when it arises.

I assume the original S propagates in source/call order like flyd and most other libraries. And the propagation is recursive. But I really want a complete list of streams to propagate per tick before the tick begins just for debuggability.

[JAForbes]

What if... we let d run first and then when it accesses c we check are we currently in a tick, and is c scheduled to run but has not yet run? If so, just run c now. And repeat that process recursively.

Then in the outer loop we just skip c when we reach it, as it already ran.

We still get our full list of dependencies to update at the start of the tick, it just may happen that that stream updates automatically while updating another one. A trade off, but probably worth it as it is computationally efficient.

I was just attempting the prior approach I was hesitant about, and its not trivial to do because we need to know recursively every node that each node depends upon, not just the immediate one. But we won't know about that unless if we do a recursive search for each node, and each node we discovered in each sub-search and so on.

And that exact recursion will just mirror the recursion of the actual tree that we're about to propagate anyway.

Either way is kind of messy but one is fast so we'll try that.