New state objects downstream from in-progress updates see inconsistent dependencies

[ala89]

There's a critical issue with the current state of the library: it was not adequately designed to handle dynamic UI layouts. More precisely, as soon as Computeds can conditionally instantiate other Computeds, the topological update order is not respected anymore.

Say you have state A, and state B is dependent on state A. You also have a Computed, say C, which, depending on the value of A, may or may not instantiate a final state D, dependent on B.

Say A changes, and arbitrarily, C is updated before B. C creates state D, which is dependent on B. Then state D is computed right away. Finally, state B is updated. At this point, state D is no longer in sync with one of its dependencies, thus breaking the key principle of Fusion.

One important fact that was ignored in this version is that the dependency graph can be expanded, or pruned, during an update. The same issue happens with Computeds that get cleared during an update: they're not removed from the update queue and can cause unexpected behavior. With the current implementation, since only the garbage collector is in charge of cleaning them, it's difficult to solve. On top of that, Computed instantiated by other Computeds should have their instantiator as a dependency. In the example above, D is not dependent on C, meaning D could never be removed from the update queue on time as it could be updated before C.

There's a workaround to the expansion issue, which is to make C reliant on both A and B, however, it's not very pretty and still doesn't solve the pruning issue.

[dphfox]

Thanks for the detailed report. This definitely slipped under the radar.

[hatmatty]

I think the issue I'm encountering with this code is related to this issue. Even though this code doesn't have a computed that conditionally instates a computed, it does have a for pairs that conditionally instates a gui object.

I think my issue links up in this way: A: Units C: For Pairs B: Size D: Card (this is a gui object that uses the size, not a state object like the others)

print("----- STARTING -----");

const Units: Value<number[]> = Value([]);

const X = Computed(() => Units.get().size());
const Y = Computed(() => X.get() * 0.1);
const S = Computed(() => {
    return UDim2.fromScale(X.get(), Y.get());
});

function Card() {
    return New("Frame")({
        Size: S,
    });
}

const Cards = ForPairs(
    Units,
    (key, value) => {
        return [key, Card()] as LuaTuple<[number, ReturnType<typeof Card>]>;
    },
    (key, frame) => frame.Destroy(),
);

function PrintSizeData() {
    print("SIZE:", S.get());
}

function PrintCardData() {
    const cards = Cards.get();
    const firstCard = cards[0];
    if (firstCard) {
        print("CARD:", firstCard.Size);
    } else {
        print("NO CARDS");
    }
}

Observer(S).onChange(PrintSizeData);

PrintSizeData(); // prints "SIZE: {0, 0}, {0, 0}"
PrintCardData(); // prints "NO CARDS"

print("----- SETTING -----");
Units.set([1], true);
// prints "SIZE: {1, 0}, {0.1, 0}" from the observer

print("----- WAITING -----");
// threw in a few task.waits()s so we know this isn't an issue that'll resolve in time.
task.wait();
task.wait();
task.wait();
PrintCardData(); // prints "CARD: {0, 0} {0, 0}" We would expect "CARDS: {1, 0}, {0.1, 0}" to be printed.

print("----- ENDING -----");

This code produces the following output: It should print "CARD: {1, 0}, {0.1, 0}" instead. The issue seems to be that when the size updates, it doesn't update on the card.

[ala89]

I've been thinking a little more about the problem.

The first thing to notice is that when adding a new state (Computed) to the dependency graph in the middle of an update, we don't need to compute it right away. In fact, we should compute it last. We don't know its dependencies yet, but there are 2 cases:

• the new state is independent of the instantiating dependency graph, so it doesn't matter when you compute it
• the new state is reliant on the instantiating dependency graph, so by computing it last, the state accesses its dependencies in their latest version

Now, we need to consider the addition of several new states. We're adding a new piece of graph to the existing dependency graph. After completing the update on the existing graph, start computing any of the new states, recursively computing dependencies until we reach the original graph which is already up to date. Do this for all of the new states that haven't been previously computed by this algorithm.

We noticed that Computeds instantiated by other Computeds need to have their direct instantiator as a dependency. To do so, a global variable must indicate whether an update is ongoing, and which Computed's callback is being calculated. This will only work if Computeds' callbacks are pure functions, but I hope nobody uses them otherwise...

Regarding cleanup, I suppose that making the update queue a weak table should be enough.

This is really a big deal that questions the fundamentals of Fusion, hopefully you'll be able to sort this out and implement a solution.

[dphfox]

Could we not just buffer the new states of all objects and only switch over once the tree is in an internally consistent state? This would not require globals.

[ala89]

If new Computeds don't capture their instantiatior as a dependency, the cleanup issue will remain. Now, I don't think there's any other way than using a global to follow the execution order from "outside" the update scope... This shouldn't break existing code as long as Fusion code remains pure and does not do weird things.

[dphfox]

Cleanup for general values is being handled as part of the ongoing #273 PR and associated broader issue #269, so I think this is solvable.

[ala89]

By cleanup, I was referring to the above issue. Still with my example from above, if D doesn't have C as a dependency, there's an issue where B and D will update before Cn and thus D will error, because C should have updated first and released D to garbage collection. This plus the fact that if the update queue holds a reference to D, it will also error. So I don't think the threads you linked can solve the issue alone.

[dphfox]

So I'm coming back around to working on this issue, because I've been thinking about upgrading the graph updating algorithm again to address other related issues I've had crop up in my own codebases; this seems to generally be a problem when a state object becomes dependent on another state object that 1) is downstream from an update currently in progress and 2) has not yet been reached by that update propagation.

This should be possible to solve; all we might need is a way to early terminate the updating of a state object that becomes dependent on an object with some boolean flag, and instead rewire the dependencies of the object so that it naturally becomes part of the update path. Somehow.

I'll toy around with this.

[dphfox]

The first hurdle I see is that right now, the order of in which dependents are traversed during updateAll is undefined because Fusion uses {[T]: true}-style sets to store dependents and dependencies. This is done so that the common case of adding and removing dependencies is a two-liner with constant time operations.

A variant of the above idea would require that this list become ordered so that dependencies can be appended to the end and ensure iteration occurs. From what I've seen in codebases, Fusion tends to have very tall and thin dependency graphs, with the objects with most dependents also being the most static and far away from time critical code segments. Combined with table.find's relative speed (as far as I measured for what I presume reasonable high-end numbers in the hundreds of entries of table values, it seems to take on the order of microseconds), I wouldn't have qualms about doing this.

[dphfox]

Another consideration I'll add onto the above; if we're making dependencies ordered, could potentially also solve a related problem/unintuitive syntax where, in the following snippet, alwaysTrue might still observe false, because there is no relation between alwaysTrue and switcher:

local function alwaysTrue(state)
    return Computed(function(use)
        assert(use(state) ~= false)
    end)
end

local condition = Value(true)

local switcher = Computed(function(use)
    return if use(condition) then alwaysTrue(condition) else nil
end)

condition:set(false) -- fallible

This graph is technically just a triangle where condition has switcher and alwaysTrue as its dependents, so with no order normally defined for traversal either can see the update first. However, with an ordered update system, so long as there is some robust rule that allows switcher to always go first, alwaysTrue will be destructed before it can see the value it is conditionally put behind (though this is contingent on the upcoming memory management changes, too)

The reason I believe this is relevant is that it is also a mutation of the graph in the same way as in the OP.

[ala89]

I'm not sure if that's exactly what you described, but in addition to the very first problem I raised, I've had the same update ordering issue with something like this:

local base = Value(false)

local val1 = Computed(function(use)
    return foo(use(base))
end)

local val2 = Computed(function(use)
    return use(base) and use(val1) or smthElse
end)

If you change base to true, either val1 or val2 can update first as val1 is not yet a dependency of val2. Therefore, if val2 is updated first, it will compute with the non-updated value of val1.

[ala89]

Now, regarding the solution, I didn't take the time to fully understand how your custom topological sort algorithm works, but I believe the solution is to use a mix of recursive and iterative updates.

When a Value is changed, you can still perform a topological sort first, and start iterating over it. However, if while updating a given Computed, new dependencies are added, you could recursively call update on the new dependencies, and on the dependencies of the dependencies, etc... Of course, ignore those that were already updated. When this recursive process terminates, continue the iterative work.

This is just an idea that I haven't tried to prove, but you can toy around with it. Also, it would be great to investigate a solution to the cleanup issue.

[dphfox]

That sounds awfully like #144! Perhaps lazy execution helps with correctness :o

[ala89]

As far as I understood from this thread, lazy evaluation is only about reducing the overhead of computing sub-graphs which do not have any side effects as they're not connected to real world things or listeners or otherwise. This will not help.

The analysis of the problem is the following: a value update propagates down to its rooted subtree. While updating nodes from this subtree, we are able to extend the state graph, but only in a certain way. We can only add new "dependency branches" to the subtree when a node gets more dependencies, we can remove some branches (not a problem seemingly), or we can extend the tree "forward" by only one node at a time by creating a Computed inside of another Computed. In order words, we can only create new "calculation demands" that must be fulfilled immediately and cannot be postponed. As a result, a fully iterative solution is not possible unless you want to drop the current node's callback evaluation. But when it comes to creating new Computeds, postponing the update further would create a dead lock, so it's absolutely not possible.

Anyway, it'd be worth it to formalize a little the problem here. There might be research papers about the topic.

[dphfox]

The problem here is that creating the state object immediately calculates it, right? As far as my understanding of this issue has internalised, this issue wouldn't exist if the only thing that could cause calculation during an update process is the update process itself.

[ala89]

Not sure what you mean here. If a node creates another node, it's the thing that I stated in the very first messages: the calculation can postponed to the end of the current update because this object is necessarily at the edge ("forward") of the state graph.

But if inside the callback that created this new node, you used something like peek you'd get to recursively calculate the new node's value anyway.

I was mistaken above, lazy evaluation would work in this case. But it has to include some recursivity to handle the aforementionned edge cases, just like I proposed anyway. (eg. the update algorithm in the eager case will be the same). However, from fully reading #144 and designing a few algorithm ideas in my head, I couldn't find something that both doesn't deteriorate performance (based on the very good point you mentioned in this thread) and doesn't add unnecessary hurdle. I'll elaborate more on this thread eventually.

[ala89]

Is there a plan to address this anytime soon?

[dphfox]

I've been busy with non-Fusion work. State objects are next on my list to work on after my current tasks are done.

[ala89]

I don't know if the solution has been fully rolled out in Fusion 0.3, but the bug that I initially mentioned at the start of this issue is still present.

The following code will error, although it shouldn't:

local scope = scoped(Fusion2)
local a = scope:Value()

local b = scope:Computed(function(use)
    return use(a) and "bar"
end)

scope:New "ScreenGui" {
    Name = "Hello",
    Parent = Player:WaitForChild("PlayerGui"),

    [Children] = {
        scope:Computed(function(use)
            return use(a ~= nil) and scope:New "TextLabel" {
                Name = scope:Computed(function(use)
                    print(use(b))
                    return use(b)
                end) or nil
            }
        end)
    }
}

task.wait(3)

a:set("foo")

The other garbage collection issue is also still present.