试着复刻一个vue的计算属性

之前对于Vue的响应式封装（这里主要思考的是computed），主要是用用，其实是懒得思考背后的原理的。毕竟原理其实可以用一句话说明：计算属性对别的属性产生有向的依赖关系，这个依赖关系构成一个有向无环图（DAG），图上的某个节点更新后重新计算其所有后置节点即可。

但是仔细想来，内部其实有一些时间复杂度的问题。显然，我们不能暴力调用回调函数（会卡出指数级时间复杂度 $O(2^n)$ 下面会详细解释）。同时朴素的做法很难解决这样的问题：

const a = ref([]);
const b = computed(() => a.join(","));
for (let i = 1; i <= n; i++) {
  a.value = a.value.concat([i]);
}

注意到对于一个网页而言，我们实际上期望 b 能在整个宏任务跑完以后才更新。所以实际上a.value 的setter触发的更新必须要进行推迟。

这篇文章讲讲我怎么在思考这些的过程中试着复刻一个vue的计算属性 computed 的

关于 computed ¶

Vue的 computed 有多种，不过为了简化问题，这里我们只讨论最经典的那种：

function computed(fn: () => T): ComputedRef<T>

这个 computed 函数接受一个 callback， 每当 callback 涉及到的其他响应式变量发生变化时，重新计算。具体请自行参考vue的文档。

如果我们希望构建一个高性能的computed，就必须进行复杂度分析。

复杂度分析 ¶

现在假设我们有 $n$ 个响应式状态，彼此之间总共有 $m$ 的依赖关系。它们可以构成一个 DAG $G = (V, E)$。 其中， $E = \{(u, v) | u 的计算依赖于v \}$。显然出度为0的点是可写的 Ref，其余点是 ComputedRef.

这里必须是DAG，因为一旦计算属性出现环，那就会出现死循环。

我们把 ComputedRef 的平均计算时间记为 $T$

朴素写法复杂度分析 ¶

考虑一个这样的朴素 computed 实现：

function computed(fn) {
  let cached = false;
  let val;
  let children = [];
  const res = {
    get value() {
      children.push(useContext());
      inContext(res, () => {
        if (!cached) val = fn();
        cached = true;
      });
      return val;
    },
    update() {
      val = fn();
      children.forEach(c => c.update());
    }
  }
}

第一次尝试获得 .value 的时候，我们在 res 的 context 下跑一次 fn。 跑 fn 的过程中，每个响应式属性 .value 都会尝试把 context 设为自己的 children （也就是构建 u,v 边）

容易发现，跑完第一次的 fn 以后再调用 .value 是 $O(1)$ 的。也就是说，计算全图的所有属性只需要挨个计算一次，即为 $O(nT)$

但是考虑更新。最坏条件下，我们会发现有类似这样的依赖关系：

graph LR;
E --> D --> C --> B --> A
E --> C --> A
D --> B
E --> B
D --> A
E --> A

现在假设我们更新了 A 。A 的孩子是 [D, C, B]，我们发现递归树是这样的：

graph TD;

A --> AB --> ABC --> ABCD --> ABCDE
ABC --> ABCE
AB --> ABD --> ABDE
AB --> ABE
A --> AC --> ACD --> ACDE
AC --> ACE
A --> AD --> ADE
A --> AE

这里的问题在于A可能先用错误的B,C,D数据触发了对E的更新；然后对D更新时D又引起了依赖D的E的更新。E在这个递归树中整整被计算了8次！

显然树的叶子数即为ABCDE的全部以A开头E结尾的子串数。也就是说，如果我们有 $n$ 个计算属性依次依赖前面的 $n-1$ 个计算属性 （第一个计算属性依赖于A）。最后再有一个计算属性 E 依赖于这 $n$ 个计算属性，那么我们会得到 $2^n$ 个不同的以A开头E结尾的子串。 更新 A 会导致整整 $O(2^n)$ 次 E 的计算！

优化 ¶

很容易想到一个优化算法。既然依赖关系是DAG，那么我们可以在DAG上跑一个拓扑排序，按照拓扑序更新不就好了？

但问题来了，在这个隐形的有向图上优雅地跑拓扑排序呢？我们知道对于 $n$ 个简单节点我们可以这样跑拓扑排序：

const sorted = [];
function topo_sort(node) {
  if (n.vis) return;
  n.vis = true;
  node.parents.forEach(n => topo_sort(n))
  sorted.push(node)
}
nodes.forEach(n => topo_sort(n));

由于每个顶点只访问了一遍，复杂度显然为 $O(n)$

再考虑拓补排序回溯的过程本身已经求出了该点的前置，因此可以把fn放在这里计算。 computed 伪代码如下：

function computed(fn) {
  let cached_val;
  let cached = false;
  const calculate = () => {
    in_context(closure, () => {
      cached_val = fn();
    });
    cached = true;
  };
  const closure = {
    get value() {
      context.parents.add(closure);
      if (!cached) calculate();
      return cached_val;
    },
    uncache() {
      if (!cached) return;
      cached = false;
      recursiveUncache(closure.children);
    }
  };
  return ret;
}

这里的关键在于我们把整个得到的 ComputedRef 变成了静态的：上游更新某个节点以后，调用 recursiveUncache 递归地把其按拓扑序的所有子节点全部设为缓存失效状态，但不进行 fn 的计算。由于一个处于缓存失效状态的节点，其子节点必然已经先行被缓存失效，因此每个节点只会 uncache 一次。也就是说，更改的最坏时间复杂度为 $O(n)$ 没有 $T$。

此时，某个元素可以进行多次更改；由于都是懒计算的，多次更改也不会触发计算属性的计算。这一点我们可以用如下的vue代码证实：

let b_count = 0;
const a = ref(1);
const b = computed(() => {
  b_count ++;
  return a.value + 1;
});

a.value = 1
a.value = 11
a.value = 114
a.value = 1145
a.value = 11451
a.value = 114514

console.log(b_count) // 0，因为b没有被访问过value属性，根本无需被计算
console.log(b.value) // 114515

a.value = 114514
a.value = 11451
a.value = 1145
a.value = 114
a.value = 11
a.value = 1

console.log(b.value) // 1
console.log(b_count) // 2。b是懒计算的，因此实际上只计算了两次。

这样我们就初步写好了一个 computed。其时间复杂度是 $O(nT)$

完整的，可运行的代码会类似这样：

function MyVue() {
  let _newId = 0;
  function newId() {
    return _newId++;
  }

  /** @template T */
  class Closure {
    /**
     * 依赖的其他响应式
     * @type {Set<Closure>}
     */
    parents = new Set();
    /**
     * 被这些东西依赖
     * @type {Set<Closure>}
     */
    children = new Set();
    /**
     * 闭包的其他状态
     * @type {Record<string, any>}
     */
    state = {};
    /** @param {T} ret  */
    constructor(ret) {
      this._ret = ret;
    }
    /** @returns {T} */
    get ret() {
      return this._ret;
    }
  }
  let context = null;
  const nextTickCalculates = new Set();

  /**
   * @param {Closure} closure
   */
  function triggerUncacheChain(closure) {
    for (const child of closure.children) {
      child.state.uncache?.();
    }
  }
  /**
   * 模拟nextTick触发的内容
   * @param {Closure} closure
   */
  function queueRecalculate(closure) {
    if (nextTickCalculates.size == 0) {
      nextTickCalculates.add(null);
      queueMicrotask(() => {
        console.log("// Microtask:");
        for (const closure of nextTickCalculates) {
          if (closure != null) {
            for (const child of Array.from(closure.children)) {
              console.log(
                "update = { id:",
                child.id,
                ", val: ",
                child.ret.value,
                "}"
              );
            }
          }
        }
        nextTickCalculates.clear();
      });
    }
    nextTickCalculates.add(closure);
  }
  /**
   * @param {Closure} closure
   */
  function cancelRecalculate(closure) {
    nextTickCalculates.delete(closure);
  }

  /**
   * 类似vue的shallowRef
   * @template T
   * @param {T} val
   * @returns {{value: T}}
   */
  function ref(val) {
    const closure = new Closure({
      get value() {
        context?.parents?.add(closure);
        return closure.state.val;
      },
      set value(v) {
        closure.state.val = v;
        triggerUncacheChain(closure);
        return true;
      },
    });
    closure.id = newId();
    closure.state.val = val;
    return closure.ret;
  }

  /**
   * @template {() => T} Fn
   * @param {Fn} fn
   * @returns {{value: ReturnType<Fn>}}
   */
  function computed(fn) {
    const calculate = () => {
      for (const parent of Array.from(closure.parents)) {
        parent.children.delete(closure);
      }
      closure.parents.clear();

      old_context = context;
      context = closure;
      closure.state.cached_val = fn();
      context = old_context;

      for (const parent of closure.parents) {
        parent.children.add(closure);
      }

      cancelRecalculate(closure);
      closure.state.cached = true;
      return closure.state.cached_val;
    };
    const closure = new Closure({
      get value() {
        context?.parents?.add(closure);
        if (!closure.state.cached) calculate();
        return closure.state.cached_val;
      },
    });
    closure.id = newId();
    closure.state.cached = false;
    closure.state.uncache = () => {
      if (!closure.state.cached) return;
      closure.state.cached = false;
      queueRecalculate(closure);
      triggerUncacheChain(closure);
    };
    return closure.ret;
  }

  return { ref, computed };
}

const { ref, computed } = MyVue();

function test(desc, fn) {
  let prom = new Promise((res) => {
    console.log(`// =========================================`);
    console.log(`// =========================================`);
    console.log(`// =========================================`);
    console.log("// ", desc);
    console.log(`// =====TEST ${desc} START========`);
    fn();
    console.log(`// =====TEST ${desc} OVER=========`);
    res();
  });
  const res = {
    thenTest: (desc, fn) => {
      prom = prom.then(() => {
        test(desc, fn);
      });
      return res;
    },
  };
  return res;
}

test("链", () => {
  const a = ref(1); // id: 0
  const nums = [a];
  const TEST_SIZE = 8;
  for (let i = 1; i <= TEST_SIZE; i++) {
    nums[i] = computed(() =>
      Array.from({ length: i }, (_, index) => index)
        .sort(() => Math.random() - 0.5)
        .reduce((x, id) => x + nums[id].value, 0)
    );
  }

  let cnt = 0;

  const i = computed(() => {
    cnt++;
    return `last is: ${nums[TEST_SIZE].value}, computed ${cnt} times`;
  });

  console.log("/* NOW:  */  i.value =", JSON.stringify(i.value));
  console.log("/* STEP: */  a.value = 2");
  a.value = 2;
  console.log("/* STEP: */  a.value = 3");
  a.value = 3;
  console.log("/* STEP: */  a.value = 4");
  a.value = 4;
  console.log("/* STEP: */  a.value = 5");
  a.value = 5;
  console.log("/* STEP: */  a.value = 2");
  a.value = 2;
  console.log("/* NOW:  */  i.value =", JSON.stringify(i.value));

  console.log("/* STEP: */  a.value = 3");
  a.value = 3;
})
  .thenTest("测试2", () => {
    const a = ref(1);

    let cnt_c = 0;
    let cnt_d = 0;
    const c = computed(() => {
      a.value;
      return ++cnt_c;
    });
    const d = computed(() => {
      a.value;
      return ++cnt_d;
    });

    const b = computed(() => {
      if (a.value) {
        return c.value;
      } else {
        return d.value;
      }
    });

    const msg = [];

    msg.push(b.value + JSON.stringify({ cnt_c, cnt_d }));
    a.value = 0;
    msg.push(b.value + JSON.stringify({ cnt_c, cnt_d }));
    a.value = 1;
    msg.push(b.value + JSON.stringify({ cnt_c, cnt_d }));
    a.value = 0;
    msg.push(b.value + JSON.stringify({ cnt_c, cnt_d }));
    a.value = 1;
    msg.push(JSON.stringify({ cnt_c, cnt_d }));

    console.log(msg);
  })
  .thenTest("两个依赖", () => {
    const a = ref(1);
    const b = ref(1);
    const a_then = ref("a_then");
    const b_then = ref("b_then");
    const c = computed(() => {
      console.log("c发生了重新计算");
      if (a.value) {
        return a_then.value;
      }
      if (b.value) {
        return b_then.value;
      }
    });

    console.log(c.value);
    console.log(c.value);
    b.value = 0;
    console.log(c.value);
    a.value = 0;
    console.log(c.value);
    b.value = 1;
    console.log(c.value);
  });