问题

响应式中考虑如下的 case，为何可能会陷入死循环，以及如何解决？

it('should avoid implicit infinite recursive loops with itself', () => {
  const counter = reactive({ num: 0 })
  effect(() => counter.num++)
  expect(counter.num).toBe(1)
})

分析

counter.num++ 实际可以写成这种展开形式

counter.num = counter.num + 1

意味着这条语句同时有 getter 和 setter，先 getter 后执行 setter。这时候应该有直觉会陷入死循环里了，所以我们可以开个 debug 看下。会发现执行顺序是：

• 进入 effect 函数中执行 run()
• run 函数中调用 this.fn()，即 () => counter.num++
• getter 中执行 track，返回当前值
• 加 1 后 setter 中执行 trigger
• trigger 中拿到 target -> key -> dep -> effect 实例 执行
• 再次进入 run

从而发生了死循环。

分析结束可以得出结论，在当前的 activeEffect 正在执行的过程中，如果再次执行该 effect，即会陷入死循环。因此可以在 trigger 内部中判断当前的 effect 和 activeEffect 是否相等即可。

解决方案

function triggerEffect(effect: any) {
  if (effect !== activeEffect) {
    // 添加这个判断以避免死循环
    if (effect.scheduler) {
      effect.scheduler()
    } else {
      effect.run()
    }
  }
}

继续深入

在知道了避免死循环的方案后，我们按照尤大的方法继续把 case 变得更加严格：

it('should avoid implicit infinite recursive loops with itself', () => {
  const counter = reactive({ num: 0 })
  const counterSpy = jest.fn(() => counter.num++)
  effect(counterSpy)
  expect(counter.num).toBe(1)
  expect(counterSpy).toHaveBeenCalledTimes(1)
  counter.num = 4
  expect(counter.num).toBe(5)
  expect(counterSpy).toHaveBeenCalledTimes(2)
})

你会发现按照崔大的写法 case 中的这句过不去了

expect(counter.num).toBe(5)

原因也很简单，我们忘记在 ReactiveEffect 的 run 方法中，在执行结束后清理现场了。否则 activeEffect 明明已经执行结束了，却还保留有值，导致新的 effect 无法进入。修改为下述代码即可

run() {
  if (!this.active) {
    return this._fn()
  }
  shouldTrack = true
  activeEffect = this
  const result = this._fn()
  shouldTrack = false
  // 除了 shouldTrack 需要改为 false 外
  // activeEffect 也需要清理现场为 undefined
  activeEffect = undefined
  return result
}

总结

响应式自增自减产生死循环的情况在 HCY 的书中和群里都有人提及，因此在这里写篇文章记录一下。

其实 activeEffect 这样写还是存在问题，因为如果只有一个 activeEffect，如果是嵌套的 effect 的话，就会丢失上下文环境，因此最好要写成栈的形式，我后续会继续补充。

问题

parser 如何处理 <div><p></div> 的 edge case？

前言

如 HcySunYang 所说

当用户没有以预期的方式使用框架时，是否应该打印合适的警告信息从而提供更好的开发体验，让用户快速定位问题？

死循环分析

我们考虑 isEnd 的条件如下：

function isEnd(context: any, parentTag) {
  // 结束标签
  if (parentTag && context.source.startsWith(`</${parentTag}>`)) {
    return true
  }
  // context.source 为空
  return !context.source
}

很容易陷入如下的死循环中，因为此时的 parentTag 依然是 p。而 </div> 进入 parseChildren 中，不以 {{ 和 <[a-z] 开头会进入 parseText 从而死循环。

死循环解决方案

分析下来主要是由于 isEnd 的判断过于严厉，只和 parentTag 进行比较，如果不是理想的 happy path，那么就会陷入死循环。

那么尝试放宽判断条件，只判断是否是 结束标签 是否可行呢？

function isEnd(context: any, parentTag) {
  // 结束标签
  if (context.source.startsWith('</')) {
    return true
  }
  // context.source 为空
  return !context.source
}

那显然也是不行的，在正常情况下 <div><p></p><div> 就会提前退出循环

考虑这两种方案的特性：

• 严格的方案：判断是 结束标签 且等于 parentTag

• 宽松的方案：仅判断 结束标签

那么我们应该提出一个折衷的方案：

• 折衷的方案：判断是 结束标签 且在 祖先 Tag 中被找到

因此我们将 parseElement 中的 parentTag 修改为 ancestors ，数据类型是 stack，并且在 parseElement 保存所有的 祖先

function parseElement(context: any, ancestors): any {
  // StartTag
  const element = parseTag(context, TagType.Start)
  // 入栈 element {tag,type}
  ancestors.push(element)
  element.children = parseChildren(context, ancestors)
  // parseChildren 递归结束 出栈
  ancestors.pop()
  // EndTag
  parseTag(context, TagType.End)
  return element
}

最后将 isEnd 修改为：

function isEnd(context: any, ancestors) {
  let s = context.source
  // 判断为结束标签
  if (s.startsWith('</')) {
    // 和祖先标签进行对比
    for (let i = ancestors.length - 1; i >= 0; i--) {
      const tag = ancestors[i].tag
      if (s.slice(2, 2 + tag.length) === tag) {
        return true
      }
    }
  }
  // context.source 为空
  return !s
}

错误信息

错误信息应该在 parseElement 中处理 endTag 之前，对 endTag 进行合法性验证

function parseElement(context: any, ancestors): any {
  // StartTag
  const element = parseTag(context, TagType.Start)
  ancestors.push(element)
  element.children = parseChildren(context, ancestors)
  ancestors.pop()
  // EndTag
  // 判断消费后的 context.source 最前面的 tag 是否等于当前 element 的 tag
  if (context.source.slice(2, 2 + element.tag.length) === element.tag) {
    parseTag(context, TagType.End)
  } else {
    throw new Error(`缺少结束标签: ${element.tag}`)
  }
  return element
}

当然后续可以将判断条件和 isEnd 进行抽离方法的重构，不在本篇的讨论中了

总结

vue3 中的 parser 如何处理 <div><p></div> 的 edge case？

1. 处理 parseChildren 的死循环问题
   • ❌严厉方案：判断是 EndTag 且与 parentTag 相同
   • ❌宽松方案：只判断是 EndTag
   • ✅折衷方案：判断是 EndTag 且与 祖先 Tag 相同
2. 在 parseElement 中处理 EndTag 前作判断
   • 判断消费后的 context.source 最前面的 tag 是否等于当前 element 的 tag

感想

实际开发中的 用户体验 同样重要，当用户没有以预期的方式使用时，需要从 设计 层面决定 Error 信息或者 Warning 信息是由底层浏览器抛给用户，还是由我们的产品抛给用户。

所以有时候一些条件的 缩放 平衡就很值得玩味了，happy path 有时候条件比较严厉，会导致用户的未按照预期使用的行为触发死循环等。因此可以适当放宽条件，并在合适的时机抛出 错误 让用户得知

问题

说一说 Vue3 中编译优化方面的 静态提升 是什么？以及为什么使用 静态提升 可以编译优化？

该问题可能引申自：

Vue3 中有哪些 编译优化 手段？

分析

案例来自于《Vuejs 设计与实现》

假如有如下 template 1：

<div>
  <p>static text</p>
  <p>{{ message}}</p>
</div>

以及如下的 template 2：

<div>
  <p foo='foo'>{{ message }}</p>
</div>

对于 template 1，如果没有使用静态提升，渲染函数最后会变成：

const { createElementVNode: _createElementVNode, toDisplayString: _toDisplayString, openBlock: _openBlock, createElementBlock: _createElementBlock } = Vue

return function render(_ctx, _cache, $props, $setup, $data, $options) {
  return (_openBlock(), _createElementBlock("div", null, [
    _createElementVNode("p", null, "static text"),
    _createElementVNode("p", null, _toDisplayString(_ctx.message), 1 /* TEXT */)
  ]))
}

如果响应式数据 message 发生了变化，render 函数会重新执行。但对于 'static text' 的 p 标签而言，额外的创建行为会带来性能消耗。

同理对于 template 2，如果没有使用静态提升，渲染函数最后会变成：

const { toDisplayString: _toDisplayString, createElementVNode: _createElementVNode, openBlock: _openBlock, createElementBlock: _createElementBlock } = Vue

return function render(_ctx, _cache, $props, $setup, $data, $options) {
  return (_openBlock(), _createElementBlock("div", null, [
    _createElementVNode("p", { foo: "foo" }, _toDisplayString(_ctx.message), 1 /* TEXT */)
  ]))
}

这里给出 renderer 的部分相关代码

function patchElement(n1, n2, container, parentComponent, anchor) {
  const el = (n2.el = n1.el)
  // children
  patchChildren(n1, n2, el, parentComponent, anchor)
  // props
  const oldProps = n1.props || EMPTY_OBJ
  const newProps = n2.props || EMPTY_OBJ
  patchProps(el, oldProps, newProps)
}

function patchProps(el, oldProps, newProps) {
  // #5857
  if (oldProps !== newProps) {
    // 省略 newProps 的处理代码
    // 省略 oldProps 的处理代码
  }
}

可以看到 patchElement 会执行 patchProps，而 { foo: "foo" } !== { foo: "foo" } 会返回 true ，因此 newProps 和 oldProps 的处理代码都会执行，额外的处理行为无疑会带来性能消耗。

解决方案

template 1

对于 template 1 的场景而言，响应式数据的更新影响到了 静态节点，导致其重复创建。因此将其提升至 render 函数外，做一个引用即可：

const { createElementVNode: _createElementVNode, toDisplayString: _toDisplayString, openBlock: _openBlock, createElementBlock: _createElementBlock } = Vue

const _hoisted_1 = /*#__PURE__*/_createElementVNode("p", null, "static text", -1 /* HOISTED */)

return function render(_ctx, _cache, $props, $setup, $data, $options) {
  return (_openBlock(), _createElementBlock("div", null, [
    _hoisted_1,
    _createElementVNode("p", null, _toDisplayString(_ctx.message), 1 /* TEXT */)
  ]))
}

template 2

同理 template 1 的场景中，只需要将 props 提升到 render 函数外

const { toDisplayString: _toDisplayString, createElementVNode: _createElementVNode, openBlock: _openBlock, createElementBlock: _createElementBlock } = Vue

const _hoisted_1 = { foo: "foo" }

return function render(_ctx, _cache, $props, $setup, $data, $options) {
  return (_openBlock(), _createElementBlock("div", null, [
    _createElementVNode("p", _hoisted_1, _toDisplayString(_ctx.message), 1 /* TEXT */)
  ]))
}

在 patchProps 时候，_hoisted_1 !== _hoisted_1 返回 false，就不会进行多余的 props 对比和更新了。

回答

说一说 Vue3 中编译优化方面的 静态提升 是什么？以及为什么使用 静态提升 可以编译优化？

静态提升指的是：

1. 对于静态的树（节点），使用类似如下的代码，将其提升到 render 函数外，即是 静态树（节点）的提升

   const _hoisted_1 = /*#__PURE__*/_createElementVNode("p", null, "static text", -1 /* HOISTED */)

   可以避免其他不相干响应式数据更新触发 render ，导致静态树（节点）重复创建的问题

2. 对于动态的树（节点），如果其 props 是静态的，使用如下的代码，将其提升到 render 函数外，即是 静态 props 的提升

   const _hoisted_1 = { foo: "foo" }

   可以避免在 patchProps 阶段，多余的 newProps 和 oldProps 的处理逻辑

不足

• 我 hoistStatic 的代码还没有看，实现部分要以后补上

后记

为什么要写这一篇呢？因为在 runtime-core 部分看到 patchProps 的代码时候，崔大说了句：为了性能加个 if (oldProps !== newProps) 语句，当时我就很不解，看了 HCY 的书，甚至还在 vue 3 里提了个 issue #5773，认为判断应该改为 hasPropsChanged。因为形如下述的这个 case：

it('should not update element props which is already mounted when props are same', () => {
  render(h('div', { id: 'bar' }, ['foo']), root)
  expect(inner(root)).toBe('<div id="bar">foo</div>')

  render(h('div', { id: 'bar' }, ['foo']), root)
  expect(inner(root)).toBe('<div id="bar">foo</div>')
})

oldProps !== newProps 无论如何都会都会返回 true 的。

而群里的小伙伴 Salt 则直接提了个 PR #5857，认为这个判断是一个无效语句，应当删除。

后来 Evan You 回复了PR #5857，指出了 静态提升 的问题，这个判断是 有意为之。

所以我写了这篇文章，以便解答后续的小伙伴在看到 patchProps 的时候产生的困惑。产生困惑是正常的！因为此时眼光只局限在了 runtime-core 中，而没有 compiler-core 的大局观。仅以本篇鼓励所有学习的小伙伴，带着问题看源码，你会收获更多。

问题

手撕最长递增子序列以及 vue3 里的实现

前言

此处不讨论到 vue3 的 快速 diff 算法，只要记住三个步骤，顺着思路展开细节即可：

1. 双端预处理

2. 理想状态（新旧节点序列总有一个被处理掉）

   • 根据剩下的那个序列做 新增 或 移除

3. 非理想状态（中间对比），只要记住两点：

   • 如何找到需要移动的节点以及如何移动
   • 找到需要被添加或移除的节点并做对应操作

具体的设计思路可以去参考 HCY 的书籍，这里不做过多阐述。

但是很可能有人需要考验你的代码及算法功底，此时就会让你手撕一个 LIS（最长递增子序列）。

因此我这里对 LIS 的算法做一个补充笔记。

dp 算法

问题简化

我们先进行问题简化，不要求出 LIS，而是求出 LIS 的长度，可以参考 leetcode 的 300 题

后面的实现可以丢到 leetcode 中进行测试

算法

这里定义 dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的 LIS 的长度，因此动转方程也就很好写了

dp[i] = max(dp[j]) + 1, j 区间是 [0, i) 且 nums[j] < nums[i]

var lengthOfLIS = function(nums) {
    let dp = new Array(nums.length).fill(1)
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i],dp[j]+1)
            }
        }
    }
    return Math.max(...dp)
};

但是这个和 vue3 的 LIS 算法还相差甚远，而且它还是 O(n^2) 的肯定不能让人满意

贪心算法

前言

在想办法降低时间复杂度前，我们先想想能不能换个思路，用 贪心 来解决这个问题

贪心思路就是，如果我们要使 LIS 尽可能的长，那么就要让序列上升得尽可能慢，因此希望每次在子序列的末尾数字要尽可能小。

所以这里维护一个数组 d[i]，保存 nums 中的数字。 i 索引表示，在 i + 1 长度时候的 LIS 的末尾最小值

看不懂这个解释没关系，只需要记住一点，贪心算法中的数组，并没有保存完整的 LIS 序列，它只关心某个长度下末尾的最小值。具体可以看下面的例子理解

例子

以数组 [0,8,4,12,2] 为例，贪心会得到一个序列 [0, 2, 12]

d 序列存储的并非是最长递增子序列，而是对应 len 的末尾最小值，如果约束：

• 最长递增子序列的 len 为 1 时，找到对应的 0 索引：[0,2,12] -> d[0] = 0，即如果 LIS 最长只能为 1，那么它的末尾元素一定为 0。对应的 LIS 为 [0]
• 最长递增子序列的 len 为 2 时，找到对应的 1 索引：[0,2,12] -> d[1] = 2，即如果 LIS 最长只能为 2，那么它的末尾元素一定为 2。对应的 LIS 为 [0,2]
• 最长递增子序列的 len 为 3 时，找到对应的 2 索引：[0,2,12] -> d[2] = 12，即如果 LIS 最长只能为 3，那么它的末尾元素一定为 12。对应的 LIS 为 [0,4,12]

即贪心算法没有保留子序列，它只是保留了对应长度的最后一个数字

算法

算法的思路就是遍历 nums：

• 如果 nums[i] 大于 d的末尾元素，那么直接将 nums[i] push 进来
• 反之 nums[i] 一定可以替换掉 d 里的一个数字，找到那个数字并做替换

var lengthOfLIS = function(nums) {
    if (!nums.length) return 0
    let d = [nums[0]]
    for (let i = 1; i < nums.length; i++) {
        const numsI = nums[i]
        if (numsI > d[d.length - 1]) {
            // 塞进 d 末尾
            d.push(numsI)
        } else {
            let j
            for (j = 0; j < d.length; j++) {
                if (numsI <= d[j]) {
                    // 找到可以替换的值
                    break
                }
            }
            d[j] = numsI
        }
    }
    return d.length
};

但是此时贪心算法的时间复杂度还是 O(n^2) 并没有减少，别急，这时候我们看看有没有可以优化的点。我们发现在 d 序列中找可以替换的值时候，用了一个循环遍历了 d 序列，但是在之前例子中我们可以隐约感觉到 d 是 单调递增 的。

没错，d 确实是单调递增的，下个小节我给一个数学证明，不想看的跳过即可。利用 d 的 单调递增 性质可以使用 二分 找到想要替换的值。

数学证明

证明当 j < i 时, d[j] < d[i]

证明：

题设为 d[i] 表示一个长度为 i 的 LIS 的末尾最小元素

假设存在 j < i 时，d[j] >= d[i]

此时创造一个长度为 j 的 LIS 命名为序列 B，

该序列 B 由长度为 i 的 LIS 从末尾删除 i-j 个元素所构成

并设序列 B 的末尾元素为 x

由 LIS 特性可知: x < d[i]

又由假设可知: x < d[i] <= d[j] 即 x < d[j]

因此存在一个长度为 j 的序列 B, 其末尾元素 x < d[j]

与题设相矛盾, 得证 d[i] 具有单调性

贪心+二分

前言

这个算法中，我们仅仅是将贪心中 对 j 索引的搜索从遍历变成了二分，因此时间复杂度最终会变成 O(nlogn)。

但是注意一点，这次我将不再使用 d 数组来存储 nums 的值，而是使用 d 数组存储 nums 对应的 index 值，方便后续把 LIS 还原出来。思考一个问题，此时的 d[i] 将不再具备 单调递增 的性质，那还可以用二分搜索么？其实是没有问题的，第二层搜索的时候，实际变成了对 nums[d[i]] 的搜索，而 nums[d[i]] 依旧具备 单调递增 性质

算法

var lengthOfLIS = function (nums) {
  if (!nums.length) return 0
  let d = [0]
  for (let i = 1; i < nums.length; i++) {
    const numsI = nums[i]
    if (numsI > nums[d[d.length - 1]]) {
      d.push(i)
    } else {
      // 将搜索换成二分
      // 选一个自己喜欢的二分即可
      let l = 0
      let r = d.length - 1
      while (l <= r) {
        let mid = (l + r) >> 1
        if (numsI > nums[d[mid]]) {
          l = mid + 1
        } else {
          r = mid - 1
        }
      }
      d[l] = i
    }
  }
  return d.length
}

贪心+二分+路径回溯

前言

由于贪心算法只会保留当前长度的 LIS 下的末尾最小元素，因此我们需要使用一个 path 辅助数组

path[i] 存放了到达当前的 numsI 的 prevIndex

并且此时的实现，需要用 ts 来写，之后丢到 vue3 源码中使用尤大的测试来检验

实现

function getSequence(nums: number[]): number[] {
  const path = nums.slice()
  let d = [0]
  for (let i = 1; i < nums.length; i++) {
    const numsI = nums[i]
    if (numsI > nums[d[d.length - 1]]) {
      // 记录路径
      // 是由当前的 d 末尾索引指向的元素到达的 numsI
      path[i] = d[d.length - 1]
      d.push(i)
    } else {
      let l = 0
      let r = d.length - 1
      while (l <= r) {
        let mid = (l + r) >> 1
        if (numsI > nums[d[mid]]) {
          l = mid + 1
        } else {
          r = mid - 1
        }
      }
      // 记录路径
      // 使用 i 覆盖 d[l]
      // 因此记录 path[i] 上一个索引为 d[l - 1]
      path[i] = d[l - 1]
      d[l] = i
    }
  }
  // 反向恢复出正确的 LIS 索引数组
  let prev = d[d.length - 1]
  for (let i = d.length - 1; i >= 0; i--) {
    d[i] = prev
    // 通过 path 返回上一个 index
    prev = path[prev]
  }
  return d
}

edge case

到这里 getSequence 已经算实现的差不多了，我们回顾一下最开始的问题：

手撕最长递增子序列以及 vue3 里的实现

手撕已经完成了，但是 vue3 的实现和我们的手撕有什么区别么？可以看下面这个例子：

[2,0,1,3,4,5] 的 LIS 应该是 [0,1,3,4,5] 而对应的 index 结果应该为 [1,2,3,4,5]

但是如果你使用 vue3 的源码来执行上面的例子，就会发现结果为 [2,3,4,5]

function getSequence(arr: number[]): number[] {
  const p = arr.slice()
  // 凡事总有例外
  // 由于 result 初始化会把 index 为 0 塞进去
  // 如果 arr[0] === 0 的话会照样进入 result
  const result = [0]
  let i, j, u, v, c
  const len = arr.length
  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    // 但是除了第一个元素为 0 的情况
    // arr 中的 其他 0 是不参与 result 的构造的
    if (arrI !== 0) {
      // 省略构造 result 代码
    }
  }
  // 省略恢复 result 数组代码
  return result
}

为什么构造 LIS 的时候不考虑 0 的情况呢？我们看下调用 getSequence 的情况在哪里

// moved 标记了存在需要移动的节点
// 如果存在那么就从 newIndexToOldIndexMap 中生成 LIS
// newIndexToOldIndexMap 是 新节点序列 index 和 旧节点序列 index 的索引
const increasingNewIndexSequence = moved
	? getSequence(newIndexToOldIndexMap)
	: EMPTY_ARR

参考尤大的注释可以得知，0 是一种特殊的标记，标记了新增的节点

同时由于 offset +1 的存在，后面的代码也都会带有这个 offset，可以参见这一行

// works as Map<newIndex, oldIndex>
// Note that oldIndex is offset by +1
// and oldIndex = 0 is a special value indicating the new node has
// no corresponding old node.
// used for determining longest stable subsequence
const newIndexToOldIndexMap = new Array(toBePatched)
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0

我们求出 LIS 的目的是为了找到哪些节点无需移动，而新增的节点根本不在节点移动的讨论范畴之内。

因此在 LIS 算法中，也无需考虑 0 的情况了。

tips: 关于尤大代码中的二分，可能会有人有疑惑不符合常见的二分模板，当 result 只有一个元素时，result.length 为 1，导致根本进不去二分的循环

  u = 0
  v = result.length - 1
  while (u < v) { /* 省略部分 */ }

其实不影响，进不去二分就进不去呗，result 如果只有一个元素进不去二分是不影响业务逻辑的。