infernoJS源码分析

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

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

<!--more-->

参考

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

1. 起步

inferno 采用lerno 构建monorepo项目,除了packages/inferno核心库之外,还有其他诸如inferno-reduxinferno-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数据结构最主要的区别是多了childFlagsflags两个属性。他们分别对应ChildFlagsVNodeFlags两个类型

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节点

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

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

  • 执行shouldComponentUpdatecomponentWillUpdate等方法
  • 使用nextPropsnextState更新propsstate
  • 执行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逻辑

源码里面用了switchcase 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提供了appendChildinsertBefore,但是没有提供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 APIreactive实现,对于diff算法的改动并没有额外关注,本文也算作是一个补充吧。

多项目逻辑复用与monorepo