ShymeanV0.8.0

infernoJS源码分析

发表于| 分类于

inferno.js是性能最快的前端UI框架之一，Vue3的diff算法貌似也从Vue2的snabbdom实现修改为类似于infernod的实现。

本文主要通过阅读inferno的核心源码，了解其关于通过最长上升子序列优化diff DOM性能的原理。

<!--more-->

参考

本次阅读的inferno版本为v7.4.8

1. 起步

inferno 采用lerno 构建monorepo项目，除了packages/inferno核心库之外，还有其他诸如inferno-redux、inferno-router等项目，暂时只需关注packages/inferno即可。

1.1. VNode

inferno采用JSX来构建UI，其VNode定义如下

export interface VNode {
  children: InfernoNode; // 子节点列表
  childFlags: ChildFlags; // 子节点类型，在patch时可以节省很多判断
  dom: Element | null; // 对应的dom实例
  className: string | null | undefined;
  flags: VNodeFlags; // 节点类型
  isValidated?: boolean;
  key: null | number | string; // diff时的key标识
  props: any;
  ref: any;
  type: any; // 标签类型，根据flags的类型代表不同含义，如HTML标签名、函数组件名、类组件名等
}

可以看见与常规VNode数据结构最主要的区别是多了childFlags和flags两个属性。他们分别对应ChildFlags和VNodeFlags两个类型

inferno在构建vnode的时候，就会计算好这两个属性，

flags

在解析JSX的时候，就会计算每个vnode对应的flags，在createVNode的时候会传入该参数，比如

  • html标签对应VNodeFlags.HtmlElement
  • 类组件对应VNodeFlags.ComponentClass
  • 函数组件对应VNodeFlags.ComponentFunction
  • 文本对应VNodeFlags.Text
  • 其他..

在其他一些vnode库中，往往根据type就可以判断对应的组件类型

  • string则说明是html标签
  • 类则说明是类组件
  • 常规函数则说明是函数组件

相比较这种判断

if(typeof type === 'string'){
    // html节点
}

在创建vnode的时候就提前进行vnode类型的声明，这样做可以省去在运行时大量的判断，运行时仅需要

if (flags & VNodeFlags.Element) {
    // html节点
}

单次的位运算肯定比 typeof运算符更快，由于是当patch时需要进行大量的节点类型判断时，这种优化就显得十分明显了

childFlags

同理，除了节点本身的类型flags之外，还标记了子节点的类型，在normalizeChildren的时候会提前计算childFlags

  • isInvalid(children) : ChildFlags.HasInvalidChildren
  • isStringOrNumber(children): ChildFlags.HasTextChildren
  • isArray(children)
    • children.length === 0 : ChildFlags.HasInvalidChildren
    • else ChildFlags.HasKeyedChildren : ChildFlags.HasKeyedChildren
  • 否则为单节点： ChildFlags.HasVNodeChildren

在patchChildren的时候，会根据新旧vnode的childFlags执行不同的patch逻辑，后面会提到

1.2. render

由于API与React基本一致，可以很轻松地找到入口render方法

import { render } from 'inferno';

const message = "Hello world";

render(
  <MyComponent message={ message } />,
  document.getElementById("app")
);

与大部分vnode库一致，在render方法中

  • 如果根节点rootInput未初始化，则走mount流程
  • 如果根节点已初始化，则说明是更新流程，走patch(rootInput, input)更新流程

2. mount

mount 源码

mount流程比较简单，遍历整个vnode树，依次构建DOM并插入到父节点中

这里可以看见vNode.flags的作用，无需再关注节点本身的type，直接根据flags类型走不同的逻辑

  • html节点走mountElement,会创建真实DOM节点
  • 类组件走mountClassComponent，实际上是创建类实例，然后调用instance.render获取vnode
  • 函数组件走mountFunctionalComponent，实际上是调用函数传入props, 返回获取vnode
  • 文本节点走mountText
  • ...

节点创建完毕之后，就去创建子节点了，同理，根据vNode.childFlags走对应的逻辑

  • 文本节点直接插入
  • 单个vnode节点，递归调用mount
  • 多个vnode节点，先序遍历，递归调用mount节点

可以看见，引入了flags和childFlags之后，在运行期间的判断就变得十分简单。

React后来也采用了类似的机制，提前计算节点类型并存放在Fiber.tag了。

3. patch

patch 源码

3.1. 更新队列

一种常见的更新时机是触发了类组件的setState方法之后，因此我们先来看看Component.prototype.setState

与Vue2的更新队列类似，在触发更新之后，并不会立马执行diff操作，而是将nextState通过queueStateChanges收集到一个全局队列QUEUE中

// queueStateChanges
if (QUEUE.indexOf(component) === -1) {
    QUEUE.push(component);
}
if (!microTaskPending) {
    microTaskPending = true;
    nextTick(rerender);
}

然后在下一个微任务tick中重新执行rerender，关于浏览器的eventLoop这里不再赘述

rerender主要的任务就是清空QUEUE队列收集到的需要更新的组件，类组件会调用updateClassComponent，

  • 执行shouldComponentUpdate、componentWillUpdate等方法
  • 使用nextProps、nextState更新props、state
  • 执行instance.render获取新的vnode
  • patch新旧节点

又回到了到了熟悉的diff环节

3.2. patch单个节点

与mount类似，根据vNode.flags可以快速对比两个节点

  • 新旧节点类型或者key不一致，直接移除旧节点，插入新节点
  • 类组件，patchClassComponent，将新节点的instance替换成旧节点的instance，然后使用nextState、nextProps走updateClassComponent
  • 函数组件，重新执行函数获取新的vnode，递归调用patch
  • html节点，patchElement，复用旧节点的DOM，然后更新props节点属性等，然后执行patchChildren
  • ...

3.3. patchChildren

前面提到，在patchChildren的时候，会根据新旧vnode的childFlags执行不同的patch逻辑

源码里面用了switch嵌case switch的方式，代码有点长，下面用文本整理一下

  • 旧节点的childFlags为HasVNodeChildren时，新节点
    • HasVNodeChildren，相当于两个单节点的patch
    • HasInvalidChildren，移除旧节点
    • HasTextChildren，移除旧节点，插入文本节点
    • 否则说明新节点有多个，执行replaceOneVNodeWithMultipleVNodes
  • 旧节点的childFlags为HasInvalidChildren时，新节点
    • HasVNodeChildren，说明插入新节点
    • HasInvalidChildren，都没有子节点，不执行任何操作
    • HasTextChildren，插入文本节点
    • 否则说明需要插入多个新节点，执行mountArrayChildren
  • 旧节点的childFlags为HasTextChildren时，新节点
    • HasTextChildren，将文本节点替换成新节点patchSingleTextChild
    • HasVNodeChildren，清除文本节点，插入新节点
    • HasInvalidChildren，清除文本节点
    • 否则说明需要清除文本节点，然后插入多个新节点，执行mountArrayChildren
  • 否则，旧节点的childFlags为多个子节点，新节点
    • HasTextChildren，移除旧的子节点列表，插入文本节点
    • HasVNodeChildren，移除旧的子节点列表，插入新节点（这里为什么没有查找新节点是否存在可复用的DOM节点呢？）
    • HasInvalidChildren，移除旧的子节点列表
    • 否则说明新节点有多个，真正的diff算法来了

4. 核心diff算法

首先要明确，diff算法并不是一种特定的算法，每种框架都可能有不同的实现，其主要目的在将旧的DOM节点列表转换成新的DOM节点列表的过程中，减少DOM操作，提高页面性能，从算法层面就是最小编辑距离。

当新旧节点的childFlags都是HasKeyedChildren时，走patchKeyedChildren，否则走patchNonKeyedChildren，从名字就可以看出来是带key和不带key的不同diff方法

4.1. patchNonKeyedChildren

patchNonKeyedChildren的实现就比较简单了，从头遍历新旧列表，依次执行patch，然后判断如果旧列表有剩余就执行删除操作，新列表有剩余就执行插入操作

4.2. patchKeyedChildren

patchKeyedChildren是inferno的diff核心算法，值得花点时间来细细品鉴。

这里先复习JavaScript的语法知识label

对于下面两个需要diff的列表

A: a b c d e f
B: a c d b g e

首先缩小改动范围，主要思路是先将首尾key相同的节点进行patch，查阅资料发现，这个思路最早由Neil Fraser 提出。

  • 先正序遍历，直到两个key不相同
  • 再逆序遍历，直到两个key不相同

经过上面的步骤，现在的diff范围变成了

A: b c d f
B: c d b g

范围缩小之后，说明剩下的节点中可能需要执行移动旧节点、删除旧节点、新增新节点的DOM操作，对于这种无法通过首尾再缩小diff范围的列表，走patchKeyedChildrenComplex（看名字就像是复杂diff操作）

需要使用一个map来保存新节点中每个key对应的位置

{
    c: 0,
    d: 1,
    b: 2,
    g: 3
}

由于生成map需要占据额外的空间，这是是典型的空间换时间实现，在inferno源码中，判断了当节点长度小于4时，直接顺序遍历而没有生成额外的map。

这个长度4应该是个经验数字，应该是用来提高性能的，但暂时没有找到相关的解释。

当然对于这种形式，生成索引值map也是通用的，因此下面都按照有索引值map的形式来进行解读。

4.3. 如何判断需要删除旧节点？

这个比较简单，如果旧节点在新map中不存在，则说明需要移除该旧节点。

4.4. 如何判断需要新增节点？

这个看起来比较简单，新节点在旧节点列表中不存在，则说明需要添加该新节点。

可以使用一个新的数组sources来存储新列表中旧节点的索引值，如果为0则说明不存在可以复用的旧节点，也就是可以添加新节点

const sources = new Int32Array(bLeft + 1); // 长度为新节点列表长度+ 1, 所有元素由 0 填充

// j 为旧节点在新节点列表中的索引值 ，i 为旧节点在旧节点列表中的索引值， +1 用于区分原本占位的 0  
sources[j - bStart] = i + 1;

再来确定一下sources的遍历顺序，假设某个sources返回的结果为[0,0,0,0]，则说明全部需要新增节点，这时候有两种遍历顺序，从前面正序遍历和从后面逆序遍历。

由于原生DOM API提供了appendChild和insertBefore，但是没有提供insertAfter，因此从后向前逆序遍历更加方便，这样就可以先mount后面的节点，然后直接使用insertBefore来插入新节点

4.5. 如何判断是否需要移动旧节点？

使用一个变量pos来记录已经遍历过的旧节点在新节点列表中的索引最大值，当后续遍历到某个旧节点时，

  • 如果pos < 旧位置，则说明当前旧节点靠后，不会对之前已经遍历的元素位置产生影响，不需要移动，更新pos变量，然后继续遍历
  • 如果存在pos > 新位置，则说明整个列表需要执行移动操作，后续会使用LIS 最长上升子序列算法处理，用来实现最小移动

最小移动是实现最小编辑距离的一种方式。

4.6. 遍历流程

比如第一次遍历旧节点列表，第一个为b，i = 0 发现在新节点map中存在，且索引值 j = 2，说明这个b应该在位置2；将sources[2]更为为 0+1，同时记录上面的pos = 2

A: b c d f
B: c d b g
S: 0 0 1 0 # 为了排版将sources变量缩写为S
i = 0 
j = 2, pos = 2

第2个节点为c

A: b c d f
B: c d b g
S: 2 0 1 0
i = 1
j = 0, pos = 2, 满足 pos > j, 则说明需要moved

第3个节点为d

A: b c d f
B: c d b g
S: 2 3 1 0
i = 2
j = 1, pos = 2, 满足 pos > j, 则说明需要moved

第4个节点为f，需要被移除。最后我们得到的sources为[2 3 1 0]，moved为true。

再明确一下sources列表的含义，对于新列表c d b g而言，c在在旧列表中为2，d为3，b为1，，c、d、b三个节点都是可以复用的，而g需要新增。

由于需要move，则需要考虑如何移动才能使操作步骤最少。

inferno采用的是最长上升子序列，用来减少moved所需的步骤，因为这样只需要保证最长子序列的索引值不变，调整其他元素到指定位置就可以了。

通过使用LIS算法获得最长上升子序列，该方法返回在最长上升子序列的索引值列表，传入sources列表，得到结果seq = [ 0, 1 ]，表示[2, 3]是sources的最长子序列

根据sources元素得知，c d b 三个节点需要复用，而最长上升子序列返回的[0,1]，则说明c、d两个节点是不需要挪动位置的，只需要将b这个需要复用的节点进行移动就可以了，需要的步数为1；另外还需要新增节点g，因此将旧列表转换成新列表的步骤为2

  • 将b移动到第三个位置
  • 插入g节点

按照前面insertBefore提到的逆序遍历顺序，就可以完成整个diff流程了

第1轮循环 i = 3

B: c d b g
S: 2 3 1 0
i = 3
j = seq.length - 1
S[i] === 0，因此新增B[3] g节点

第2轮循环 i = 2

B: c d b g
S: 2 3 1 0
i = 2
j = 1
i !== seq[j]，因此移动B[2] b节点对应的DOM节点到该位置

第3轮循环 i = 1

B: c d b g
S: 2 3 1 0
i = 1
j = 1
i === seq[j]，因此不进行任何操作，j--

第4轮循环 i = 0

B: c d b g
S: 2 3 1 0
i = 0
j = 0
i === seq[j]，因此不进行任何操作，j--

完成循环。总结一下，

  • 获得新列表中每个key对应的索引值map，使用一个sources列表用于保存新列表中旧节点的索引值，初始化时都为0
  • 遍历旧列表，
    • 如果key存在map中，则把旧节点所在的索引值保存到sources中；
    • 如果key不存在map中，则直接移除该节点
    • 使用一个pos变量来判断是否需要进行移动操作moved
  • 如果moved为false，则直接逆序遍历sources列表，找到为0需要新增的节点，执行插入操作即可
  • 如果moved为true，
    • 则还需要额外通过lis_algorithm获取最长上升子序列seq
    • 逆序遍历sources列表
      • 如果值为0，则新增该节点
      • i !== seq[j]，则说明该节点需要执行移动操作
      • 否则不需要进行任何操作

基于这些步骤，可以很明显地提高diff效率。

4.7. 最长递增子序列

关于该算法具体的解释，可以参考letcode 300. 最长递增子序列

5. 与snabbdom的比较

回想一下snabbdom的实现(之前的整理：snabbdom源码解析)，在双端判断都无法继续缩小范围的情况下，从头遍历，根据createKeyToOldIdx获取新节点在旧列表中的位置，直接执行移动操作。

举个例子

A: a b c d
B: c d b a e

详细更新步骤为

# 原始DOM列表，正序遍历
A: a b c d

# 步骤1 移动c到第1位
S: c a b d
# 步骤2 移动d到第2位
S: c d a b
# 步骤3 移动b到第3位
S: c d b a
# 步骤4 创建e节点
S: c d b a e
# 完成

整个过程需执行3步移动操作 + 1步新建操作

而在inferno使用最长上升子序列之后，得到新节点列表的最长上升子序列为c d，在新列表中对应索引值为0 1索引值2的b和索引值为3的a需要执行移动操作，索引值为4的e需要新建。因此只需要执行2步移动操作 + 1步新建操作

# 原始DOM列表，逆序遍历
A: a b c d

# 步骤1 新建e
S: a b c d e
# 步骤1 移动a到第4位
S: b c d a e
# 步骤2 移动b到第3位
S: c d b a e
# 完成

在复杂度层面，基于二分的最长上升子序列复杂度为O(n log n)，略低于snabbdom的单次遍历O(n)，但可以节省不少DOM移动操作步骤，

6. 最后

在前段时间刚整理了snabbdom源码分析, 有评论指出Vue3已经采用inferno的diff了。

之前也翻阅了Vue3的源码实现，当时主要聚焦在新的Composition API和reactive实现，对于diff算法的改动并没有额外关注，本文也算作是一个补充吧。

世人的悲欢并不相通，我只是觉得他们吵闹。

Copyright © Shymean 2016 - 2024蜀ICP备2023029820号