Vue 3.5 双向链表如何实现依赖收集

Vue 近期发布了 3.5，响应式系统重构了，所以打算以此文档记录一下 3.5 的双向链表是怎么实现依赖收集的。响应式系统里面有两个核心反应式功能，一个是 effect，一个是 computed，本文不涉及 computed，主要针对 effect 功能分析。

参考链接

调试环境介绍

安装响应式系统包 "@vue/reactivity": "^3.5.8” , 核心代码如下所示，通过 debugger 直接进入reactivity 包调试

import { reactive, effect, computed } from '@vue/reactivity'
const obj = reactive({
  a: 1,
  b: 2,
  c: 3,
  d: 4
})
effect(() => {
  console.log('effect run')
  obj.a
a
})
debugger
obj.a++

双向链表结构

pr 里面有一张图，大概表示了双向链表的结构，我觉得更像是**双向十字链表，**除了前后这个维度外，还多了上下这个维度，看着比 React Fiber 节点的链表复杂多了

减少 dep 和 sub，我画了一个更详细的关系图

对应代码

import { reactive, effect, computed } from '@vue/reactivity'
const obj = reactive({
  a: 1,
  b: 2,
  c: 3,
  d: 4
})
effect(() => {
  console.log("effect 1")
  obj.a
  obj.b
})
effect(() => {
  console.log("effect 2")
  obj.a
  obj.b
})

前后维度分析

下面代码是一个最简单的场景，effect 执行后，仅仅形成前后维度的链表，注意这里形成的链表不会有上下维度，因为只有一个 effect

import { reactive, effect, computed } from '@vue/reactivity'
const obj = reactive({
  a: 1,
  b: 2,
  c: 3,
  d: 4
})
effect(() => {
  console.log('effect run')
  obj.a
  obj.b
})
debugger
obj.a++

节选 track 里面部分代码 ，track 函数会在访问 obj.a 触发，经典的收集函数

    if (link === void 0 || link.sub !== activeSub) {
      link = this.activeLink = new Link(activeSub, this);
      if (!activeSub.deps) {
        activeSub.deps = activeSub.depsTail = link;
      } else {
        link.prevDep = activeSub.depsTail;
        activeSub.depsTail.nextDep = link;
        activeSub.depsTail = link;
      }
      if (activeSub.flags & 4) {
        addSub(link);
      }
    }

首先会创建一个名为 link 的节点，link 会关联上 dep 和 sub , dep 就是 obj.a ，sub就是订阅者，上面代码 effect 里面的回调函数 link = this.activeLink = new Link(activeSub, this); 执行后

graph LR
Node1[link] -->|dep| Node2[dep obj.a]
Node1[link] -->|sub| Node3[sub effect回调函数]

activeSub.deps = activeSub.depsTail = link; 执行后

graph LR
Node1[link] -->|dep| Node2[dep obj.a]
Node1[link] -->|sub| Node3[sub effect回调函数]
Node3[sub effect回调函数] -->|deps| Node1[link]

addSub(link); 执行后

graph LR
Node1[link] -->|dep| Node2[dep obj.a]
Node1[link] -->|sub| Node3[sub effect回调函数]
Node3[sub effect回调函数] -->|deps| Node1[link]
Node2[dep obj.a] -->|subs| Node1[link]

经典的 dep 和 sub 相互收集过程没有了，但是 dep 和 sub 通过中间的 link，都可以找到对方，比如 trigger 的时候，dep 通过 link 能到找到 effect 函数，effect 函数执行后，通过 link 可以找到 dep 清理依赖

目前是执行完 obj.a 的状态，继续执行 obj.b ，同样会创建一个新的 link ，状态和上面的一样，但是目前会有两个 link，我们看下是怎么关联的

if (!activeSub.deps) {
  activeSub.deps = activeSub.depsTail = link;
} else {
  link.prevDep = activeSub.depsTail;
  activeSub.depsTail.nextDep = link;
  activeSub.depsTail = link;
}

activeSub 是当前的 effect，这次会进入 else 逻辑，因为从上图可知，deps 指向了 obj.a 对应的 link，else 里面就是两个 link 相互关联。并且 effect 上面的 depsTail，一直指向最新的 link，这里即 obj.b的 link，deps一直指向 head，这里即 obj.a 的 link

graph LR
Node1[link obj.a] -->|nextDep| Node2[link obj.b]
Node2[link obj.b] -->|prevDep| Node1[link obj.a]

现在两个 link 就串联起来，如果一个 effect 里面还需要追踪其他依赖，也是这样串联起link，值得注意的是，前后串联的 link 是在一个 effect 作用域内的，多个 effect 则会有多条这种链表

最开始看到 pr页面那张链表图的时候，以为obj.b 触发更新的时候，会沿着 link 找到对应的 effect，但其实没必要，因为 obj.b link 本身就指向了 effect，否则时间复杂复是 O(n) 而不是 O(1)

obj.a++
obj.b++

这个链表的作用可能是：

本文不涉及到 computed，所以分析一下清理依赖是怎么利用链表的，以下面的代码为例

import { reactive, effect, computed } from '@vue/reactivity'
const obj = reactive({
  a: 1,
  b: 2,
  c: 3,
  d: 4
})
effect(() => {
  if (obj.a === 1) {
    obj.b
    obj.d
  } else {
    obj.c
    obj.d
  }
})
debugger
obj.a++

effect 第一次执行完成

graph LR
Node1[link obj.a] -->|nextDep| Node2[link obj.b]
Node2[link obj.b] -->|prevDep| Node1[link obj.a]
Node2[link obj.b] -->|nextDep| Node3[link obj.d]
Node3[link obj.d] -->|prevDep| Node2[link obj.b]

effect 第二次执行到 obj.a , obj.a 对应 link 节点在最后面因为 effect 重新调用，首先访问 obj.a，断开了原来 link a 的链接，重新加到了最后

graph LR
Node1[link obj.b] -->|nextDep| Node2[link obj.d]
Node2[link obj.d] -->|prevDep| Node1[link obj.b]
Node2[link obj.d] -->|nextDep| Node3[link obj.a]
Node3[link obj.a] -->|prevDep| Node2[link obj.d]

effect 继续执行到 obj.c , 新增了 link c

graph LR
Node1[link obj.b] -->|nextDep| Node2[link obj.d]
Node2[link obj.d] -->|prevDep| Node1[link obj.b]
Node2[link obj.d] -->|nextDep| Node3[link obj.a]
Node3[link obj.a] -->|prevDep| Node2[link obj.d]
Node4[link obj.c] -->|prevDep| Node3[link obj.a]
Node3[link obj.a] -->|nextDep| Node4[link obj.c]

effect 继续执行到 obj.d, 断开了原来 link d 的链接，重新加到了最后

graph LR
Node1[link obj.b] -->|nextDep| Node2[link obj.a]
Node2[link obj.a] -->|prevDep| Node1[link obj.b]
Node3[link obj.c] -->|prevDep| Node2[link obj.a]
Node2[link obj.a] -->|nextDep| Node3[link obj.c]
Node4[link obj.d] -->|prevDep| Node3[link obj.c]
Node3[link obj.c] -->|nextDep| Node4[link obj.d]

从上面的流程变化可以看出，effect 重新执行的时候，访问到哪个属性，就会断开这个属性对应 link 的链接，重新加入到最后，形成一个新的顺序，而且这些 link 都是一直复用，并没有重新创建

当 effect 执行完后，就会执行 cleanupDeps ，这里会遍历链接，如果那个依赖不需要要了，直接就断开那个节点，并把这个这个节点的前后节点相连，遍历是 O(n)，双向链表删除节点并重连是 O(1)

function cleanupDeps(sub, fromComputed = false) {
  let head;
  let tail = sub.depsTail;
  let link = tail;
  while (link) {
    const prev = link.prevDep;
    if (link.version === -1) {
      if (link === tail) tail = prev;
      removeSub(link, fromComputed);
      removeDep(link);
    } else {
      head = link;
    }
    link.dep.activeLink = link.prevActiveLink;
    link.prevActiveLink = void 0;
    link = prev;
  }
  sub.deps = head;
  sub.depsTail = tail;
}

形成新链，b 没有被收集到所以删除，等待垃圾回收

graph LR
Node1[link obj.a] -->|nextDep| Node2[link obj.c]
Node2[link obj.c] -->|prevDep| Node1[link obj.a]
Node3[link obj.d] -->|prevDep| Node2[link obj.c]
Node2[link obj.c] -->|nextDep| Node3[link obj.d]

删除 link b 是因为 link.version === -1这个判断，effect 回调函数执行前，会调用 prepareDeps,里面把 link.version 充值为-1 ，在 track 的时候，link.version 会改变，如果到最后还是-1，说明没有被 track

function prepareDeps(sub) {
  for (let link = sub.deps; link; link = link.nextDep) {
    link.version = -1;
    link.prevActiveLink = link.dep.activeLink;
    link.dep.activeLink = link;
  }
}

响应式系统避免不了依赖清理的环节，即使依赖关系变更是小部分场景的需求，从 vue2 的普通对象到 vue3的 set，再到 3.2 的依赖标记，依赖清理环节都会大量且频繁对集合产生添加和删除操作，双向链表有效优化这个环节，仅仅是删除链表上的某个节点并复用其他节点。

上下维度分析

一个 deb 对应 多个 sub，就会产生上下维度的 link

import { reactive, effect, computed } from '@vue/reactivity'
const obj = reactive({
  a: 1,
  b: 2,
  c: 3,
  d: 4
})
effect(() => {
// effect1
 obj.a
})
effect(() => {
// effect2
  obj.a
 })
debugger
obj.a++

和前后维度结构一样，只是变量名不同，因为是不同 effect ，obj.a 对应的 link 节点是有两个的 （图是前后节点，可以脑补成上下节点）

graph LR
Node1[link obj.a] -->|nextSub| Node2[link obj.a]
Node2[link obj.a] -->|prevSub| Node1[link obj.a]

回看这张图，需要注意的是，当一个 dep 对应多个 sub的时候，这个 dep也会产生多个 link，一个 sub里面一个 link， dep.subs 指向最后一个 link，而 dep.subsHead指向第一个 link

graph LR
Node1[link] -->|dep| Node2[dep obj.a]
Node1[link] -->|sub| Node3[sub effect回调函数]
Node3[sub effect回调函数] -->|deps| Node1[link]
Node2[dep obj.a] -->|subs| Node1[link]

更新的时候,沿着prevSub向上遍历就可以找到所有 effect，先 effect2 ，再 effect1，不是向下遍历是因为endBatch里面批量更新的逻辑，endBatch后更新顺序还是从前往后的，即先 effect1 再 effect2

    for (let link = this.subs; link; link = link.prevSub) {
        if (link.sub.notify()) {
          ;
          link.sub.dep.notify();
        }
      }

除了顺序触发 effect 作用之外，应该和 computed 也有关系，因为 computed 是 dep又是 effect，情况特殊，本文暂不涉及 computed

综合起来，多个 dep 和 多个 sub，就如图所示