响应式系统中的菱形问题

发现一个解决响应式系统中菱形问题的方法，觉的挺巧妙的，记录一下。

阅读之前最好有了解过 Vue，solid-js 等响应式系统的基本概念。

响应式系统的基本概念#

Signal: 响应式系统中基本单元。可以存储值，改变值时将触发响应式更新。

Memo: 可以依赖 Signal 或 Memo。当依赖的响应式节点发生改变时，才重新执行函数，而且只有函数返回的值和上一次不同时才重新更新自己的值。可以理解为 Vue 的计算属性。例如：

let (name, set_name) = create_signal("Alice");

let name_len = create_memo(move |_| name.len());

let name_len_2 = create_memo(move |_| name_len());

// 更新 name 时，name_len 函数会执行，但是返回的长度没有改变,
// 所以 name_len 的值也不会发生改变。进而 name_len_2 函数不会在重新触发执行。
set_name("Blice");

Effect: 可以依赖 Signal 或 Memo。当依赖的响应式节点发生改变时，重新执行函数。例如：

let (name, set_name) = create_signal("Alice");

create_effect(move |_| {
    println!("{} 的长度是 {}", name_upper(), name_len());
});

// 设置值后，重新执行 create_effect 里的函数
set_name("Blice");

我们通常把上面的统称为响应式节点. 同时每个节点都有 node_subscribers 和 node_sources 两个数组。例如：

// A
let (name, set_name) = create_signal("Alice");

// B
let name_upper = create_memo(move |_| name.with(|n| n.to_suppercase()));

node_subscribers： 依赖这个节点的数组。比如上边的例子，因为 B 依赖于 A，那么 A 的 node_subscribers 数组中就有一个 B。简单的理解，这里是为了方便向下追寻。

node_sources： 被依赖这个节点的数组。比如上边的例子，因为 B 依赖于 A，那么 B 的 node_soueces 数组中就有一个 A。简单的理解，就是为了方便向上追寻。

在实际使用中, 响应依赖有点像树结构，Signal 总是根节点，Effect 总是叶子节点。

问题#

想象一下以下代码，如果在最后执行一下 set_name，那么 create_effect 应该需要执行几次。

// A
let (name, set_name) = create_signal("Alice");

// B
let name_upper = create_memo(move |_| name.with(|n| n.to_suppercase()));

// C
let name_len = create_memo(move |_| name.len());

// D
create_effect(move |_| {
    println!("{} 的长度是 {}", name_upper(), name_len());
});

它的依赖图像一个菱形一样：

___ A ___
|       |
B       C
|       |
___ D ___

答案是根据 A 更新值来决定：

A 的更新，没有导致 B 和 C 的值发生变化，那么 D(create_effect) 就不会执行.
A 的更新，导致 B 和 C 其中一个发生了变化，那么 D 就会执行一次.
A 的更新，导致 B 和 C 都发生了变化，如果我们不特殊处理，那么它应该会执行两次。

第三种情况感觉这挺反直觉的，性能也不好，所以我们要处理成执行一次。

解决方法#

以下所写的代码都为伪代码。

我可以把 Signal, Memo 和 Effect 的状态标识为以下三个状态：

Clean: 没有发生改变。 Check: 可能发生改变了，也可能没发生改变，需要检查。 Dirty: 发生改变了。

第一步，当 A 发生更新时，我们更新值，然后把 A 的状态标识为 Dirty，同时遍历依赖 A 和跟 A 有关系（比如上边的 B C D）的所有 Memo 和 Effect，并把它们的状态都标识为 Check，同时收集遍历中所有的 Effect。

fn update<T>(&self, new_value: T) {
    self.value = new_value;

    // 更新依赖 A 和 跟 A 有关系的状态，同时收集遍历中所有的 Effect。
    mark_dirty(*self);

    // 执行收集的 Effect
    run_effects();
}

此时它的依赖图如下：

_____ A(Dirty) _____
|                   |
B(Check)        C(Check)
|                   |
_____ D(Check) ______

第二步，我们在遍历处理所有收集的 Effect，此时应该是处理 D.

判断 D 的状态是否为 Check。答案是肯定的，所以我们要沿着 D 向上查找。
而 B 的状态也是 Check，所以我们要沿着 BB继续向上查找。
而 A 的状态是 Dirty，又因为 A 是个 Signal，所以我们只需把依赖 A 的节点状态改为 Dirty，即把 B 和 C 的状态改为 Dirty。最后把 A 的状态改为 Clear。

此时它的依赖图如下：

_____ A(Clear) _____
|                   |
B(Dirty)        C(Dirty)
|                   |
_____ D(Check) ______

A 处理完后返回 B 继续处理，此时因为 B 的状态为 Dirty, 所以我们执行 B 的函数，然后检查 B 的值是否更新。如果是更新，则需要把 D 改为 Dirty。最后把 B 节点改为 Clear。

此时它的依赖图可能如下：

_____ A(Clear) _____
|                   |
B(Clear)        C(Dirty)
|                   |
_____ D(Dirty) ______

B 处理完后返回 D 继续处理：
1. 如果 D 的状态为 Dirty，则不需要在检查 C，直接去执行 D 的函数。最后把 D 节点改为 Clear。结束。
2. 如果 D 的状态没有发生改变，则继续按照处理 B 的流程在处理一下 C。
3. 如果处理完 C，D 的状态为 Dirty，执行 D 的函数。最后把 D 节点改为 Clear。结束。
4. 如果处理完 C，D 的状态没有发生改变，则不需要在去执行 D 的函数。最后把 D 节点改为 Clear。结束。

此时你会发现我们最多执行了一次 Effect。

在处理 B 后 D 的状态为 Dirty 这种情况中，你可能会发现，我们没说处理 C 的事情（因为可能也发生更新）。这不太对啊，不用担心，我们只是把它延迟到 D 执行时，重新执行 name_len() 那么我会在这里检查是否为 Dirty，如果是，则会重新执行更新 C 的值。

伪代码如下：

每个响应式节点都有一个 NodeId 辨识自身。

fn update_if_necessary(node_id: NodeId) {
    // 检查响应式节点的状态是否为 Check
    if current_state(node_id) == ReactiveNodeState::Check {
        // 遍历 Effect 依赖的节点（向上查找）
        for source in self.node_sources.iter() {
            update_if_necessary(source);

            // 只要有一个依赖节点把自己的响应式节点的状态改为 Dirty，停止检查
            if current_state(node_id) == ReactiveNodeState::Dirty {
                break;
            }
        }

        // 检查响应式节点的状态是否为 Dirty
        if current_state(node_id) == ReactiveNodeState::Dirty {
            // 更新值
            update(node_id);
        }

        // 改变响应式节点的状态为 Clean
        mark_clean(node_id);
    }
}

fn update(node_id: NodeId) {
    let node = get_node(node_id);

    // 如果是 Signal 直接返回 true
    // 如果是 Memo 重新执行创建时传入的函数，判断值是否更新
    // 如果是 Effect 重新执行创建时传入的函数，然后返回 true
    let changed: bool = todo!();


    if changed {
        // 把依赖自己的响应式节点 状态改为 Dirty
        for sub_id in get_node_subscribers(node_id).borrow().iter() {
            sub.state = ReactiveNodeState::Dirty;
        }
    }

    mark_clean(node_id);
}

参考资料#

Appendix: How does the Reactive System Work?
Super Charging Fine-Grained Reactive Performance