从 React 源码中学习数据结构
学习卡卡颂老师的 React 源码课程，通过自己写一个 小型 React 来学习其中的思想，对其中涉及到数据结构相关部分的内容有所感悟，跟大家分享一下。
React 基本原理
现代前端框架的原理基本都可以用 UI = f(State) 来简单概括。其中 React 从状态更新到 UI 变化中间经历的过程，被称为 Reconciliation，完成这个过程的工具就是 Reconciler，他的核心代码都在 react-reconciler 这个包中。这个包不会耦合具体的宿主环境的代码，他只提供对状态更新流程的实现与封装，不同的宿主环境会通过不同的包来调用 Reconciler。
比如对于浏览器环境，React 提供了 react-dom 包，里面实现了操作 DOM 的方法。
除此之外，React 还提供了 react 包，他提供了诸如 createElement 等通用的方法，以及暴露给开发者的React 上层特性，比如 Hooks 等。
抽象数据类型
要完成 React Reconciliation 过程，需要数量众多的抽象数据类型进行支撑，包括 Fiber FiberRoot Update UpdateQueue Lane 等。
Fiber
Fiber就是 Component 上的需要被执行的、或已经执行完成的工作，每个 Component 可能有多个Fiber。——React 源码中的注释
Fiber 可以暂时先理解为虚拟节点，他有不同的类型，比如 FunctionComponent ClassComponent HostRoot HostText Fragment 等。也就是说，一个 Fiber 节点可以对应某个 React 组件或某个 DOM 节点等。
React 中的很多过程都是使用深度优先遍历（DFS）来实现的：比如生成 FiberTree（暂时可以理解为 VirtualDOMTree）、将 FiberTree 的内容提交到宿主环境 UI 中、遍历 FiberTree 执行 Effects 等等。具体可参考本文的 数据结构与算法 章节。
需要注意的是：如果使用递归实现 DFS 的过程，那么 React 将无法控制调用栈的随时中断与继续。 因此 React 选择借助 FiberTree 并使用迭代的方式实现 DFS，并在中间的某些环节设置了可以提前中断的手段。同时 Fiber.updateQueue 等属性提供了记忆并恢复工作状态的能力，使得继续之前被中断的任务成为可能。
对于下面的例子，首次渲染后最终将会出现这样的 FiberTree：
const App = () => {
return <h1 onClick={() => console.log('click!')}>Hello World!</h1>
}
ReactDOM.createRoot(
document.getElementById('container')
).render(
<App />,
);
Fiber (HostRoot) -> Fiber (<App />) -> Fiber (<h1>Hello World!</h1>)
如果之后比如 <h1> 触发了更新，其中的文字发生了变化，React 不会直接在原来的 FiberTree 上执行更改，而是会建立一棵新的 FiberTree，将其称为 workInProgress ；而原来的树对应着屏幕上当下显示的内容（被称为 current）。他们节点的 alternate 属性相互指着对方。
HostRootFiber (Current) -> Fiber (<App />) -> Fiber (<h1>Hello World!</h1>)
HostRootFiber (WIP) -> Fiber (<App />) -> Fiber (<h1>NEW World!</h1>)
当这棵新的树创建完毕、内容更新到 DOM 中之后，两棵树的地位随即发生互换。当下的 WIP 将会成为新的 current；而 current 则成为 WIP，等待着下一次更新。
HostRootFiber (WIP) -> Fiber (<App />) -> Fiber (<h1>Hello World!</h1>)
HostRootFiber (Current) -> Fiber (<App />) -> Fiber (<h1>NEW World!</h1>)
这种机制被称为 双缓存机制，在显卡中也有所使用，可以确保屏幕上不会出现只渲染了一半的结果。
FiberTree
FiberTree 不是一种额外定义的类型，他只是由众多 Fiber 节点组成的单链表树形结构。Fiber 中的 child 和 sibling 就构成了这个数据类型，return 在其中也起到了一定的辅助作用。
Fiber 中的 child 指针指向子节点，sibling 指向下一个兄弟节点，return 指向任务执行完需要返回的地方，在这里可以理解为父节点。
以这个 JSX 的例子来做说明：
const El = <MyComponent>
<div id="div">
<ul id="ul">
<li id="li0"></li>
<li id="li1"></li>
<li id="li2"></li>
</ul>
<span id="span">Hello!</span>
</div>
</MyComponent>
| Fiber | Child | Sibling | Return |
|---|---|---|---|
| MyComponent | div | null | null* |
| div | ul | null | MyComponent |
| ul | li0 | span | div |
| li0 | null | li1 | ul |
| li1 | null | li2 | ul |
| li2 | null | null | ul |
| span | null** | null | div |
*需要具体情况具体分析，可能是别的 Fiber
**React 中，为了简化，没有其他兄弟节点的文本节点不能单独成为一个 Fiber，所以 span 没有子节点，而是在 memorizedProps 等属性中记录文字内容
FiberRoot
FiberRoot -> HostRootFiber (Current) -> Fiber (<App />) -> Fibers..
-> Fibers..
HostRootFiber (WIP) -> Fiber (<App />) -> Fibers..
-> Fibers..
createRoot 的一个重要任务就是创建 FiberRoot，FiberRoot 是整个 Rconciliation 中最上面的对象，是 FiberTree 的根结点的父结点。
FiberRoot 中有一个 current 指针，指向当前屏幕上的 UI 对应的 HostRootFiber。WIP 和 current FiberTree 地位的互换就是指的 FiberRoot.current 指向的改变。
Lane
React 中用 Lane 表示优先级这一概念。Lane 实际上就是二进制数字类型，每种优先级用不同的位为 1 来表示，用二进制来表示优先级就可以很方便地进行二进制运算来表达 “集合” 或者说 “批” 的概念。因为除去符号位之后一共还可以有 31 位，所以一共有 31 个 Lane，比如：
export const NoLane: Lane = 0b0000000000000000000000000000000
export const SyncLane: Lane = 0b0000000000000000000000000000010
export const InputContinuousLane: Lane = 0b0000000000000000000000000001000
export const DefaultLane: Lane = 0b0000000000000000000000000100000
一般来讲，除了 NoLane 以外，数字越小代表优先级越高。
除了 Lane 以外，React 中还有 Lanes，实际上就是一群 Lane 做按位或运算的结果，表示 Lane 的集合。
Update
Update 是 React 中用来承载 改变状态的更新任务 的数据类型，React 中通过 createUpdate 来创建 Update。
UpdateQueue
UpdateQueue 是 React 中用来存放和消费 Update 的数据类型，initializeUpdateQueue 负责初始化 Fiber 上的 updateQueue，enqueueUpdate 用于将 Update 加入 UpdateQueue 中，processUpdateQueue 则用于消费 Update。
Hook
React 的 FunctionComponentFiber 中的 memorizedState 属性指向的即为该函数组件的第一个 Hook，一个函数组件内部的 Hooks 会组成一个链表，他们由 .next 链接起来。
注意当前 React 源码中 ReactFiberHooks.js 中单独定义了 Hook 的 Update 和 UpdateQueue，这跟上文提到的 Fiber 中的 Update 和 UpdateQueue 思路类似但结构有所不同！
数据结构与算法
React 的源码中使用了几个非常典型的数据结构和算法，包括各种链表的变体、深度优先遍历、位运算等。
链表
链表是 React 中使用较多的数据结构之一，其中有两种链表较为特殊：一种是以链表为基础的树形结构，一种是环形链表。
单链表树
FiberTree 就是单链表树，他跟传统的树有些不同，他是由一条条链表组成的，更像是一个鱼骨形的结构。
FiberTree 有一条明显的主干链表，即 root.child.child... 这一条链表。
然后每一个节点都有 sibling 属性，该属性也指向了一个链表，这个链表将其兄弟节点串了起来。
FiberRoot
|
Fiber -> Fiber -> Fiber
| |
| Fiber -> Fiber -> Fiber
|
Fiber -> Fiber
|
Fiber -> Fiber
|
Fiber
环形链表
React 中的更新队列是采用环形链表存储的，准确的说是 UpdateQueue.shared.pending 属性，该属性指向一个由 Update 构成的环形链表，链表中的每一项用 next 指向下一项，且永远指向最后加入的 Update。
假设我们按照 U1 U2 U3 的顺序插入 UpdateQueue.shared.pending，那么每次插入后的结果将是：
// append U1
U1.next = U1
UpdateQueue.shared.pending = U1
// U1 -> U1
// append U2
U2.next = U1
U1.next = U2
UpdateQueue.shared.pending = U2
// U2 -> U1 -> U2
// append U3
U3.next = U1
U2.next = U3
UpdateQueue.shared.pending = U3
// U3 -> U1 -> U2 -> U3
除了 UpdateQueue 以外，React 中的 Hooks 等也是用类似的数据结构保存的。
深度优先遍历
React 中大量使用 DFS 来处理节点，基本都按照下列代码的顺序执行：
- 先沿着
child一路遍历到底 - 再从最后一层倒着开始检查每一层的
sibling，再对每一个sibling进行 DFS，遍历他的child
function dfs(node: Fiber) {
doPreWork(node)
let child = node.child
while (child !== null) {
dfs(child)
doPostWork(child)
child = child.sibling
}
}
可以看到这个写法的遍历顺序与回溯算法其实非常像，有关回溯可以参考 这篇笔记。
这样写遍历的缺点在前面的 Fiber 节也提到过，由于是借助 JavaScript 调用栈的递归写法，我们无法控制他的终止。这个时候 return 属性的意义就出来了，我们可以借助 return 代替栈来记录每个子任务执行完成之后需要返回的地方。
于是就有了下面在 React 中的典型代码：
function processTree(root: Fiber) {
let node = root
function proecessNode() {
// 向下遍历
doPreWork(node)
if (node.child !== null) {
node = node.child
return
}
// 向上遍历
while (node !== null) {
doPostWork(node)
if (node.sibling !== null) {
node = node.sibling
return
}
node = node.return
}
}
while (node !== null && shouldYield()) {
processNode()
}
}
可以看到，在迭代的写法中，如果 shouldYield() 在某次循环时变成了 false，那么循环将不再继续，遍历过程被终止了。
递归的写法胜在方便，因此在 React 中仍有部分应用，比如在完全同步执行、不能中断的 Commit 阶段，就会使用到递归的写法。
在两种写法中，都有调用 doPreWork() 和 doPostWork()，分别起到前序执行和后序遍历的效果。React 中有很多工作都是在这两个时机进行处理的，比如 Render 阶段的 beginWork 即为 doPreWork 、completeWork 即为 doPostWork。
位运算
React 中广泛使用二进制位来标记状态，比如 Fiber 中的 flag 和 lane 均使用了二进制位。flag 中每一位代表一种需要执行的副作用，而 lane 中不同的位则表示不同的优先级。
通过位运算，React 可以很方便地实现集合的交、并、差等运算，下面是 lane 相关操作的实现，flag 也类似：
export function includesSomeLane(a: Lanes | Lane, b: Lanes | Lane): boolean {
return (a & b) !== NoLanes;
}
export function isSubsetOfLanes(set: Lanes, subset: Lanes | Lane): boolean {
return (set & subset) === subset;
}
export function mergeLanes(a: Lanes | Lane, b: Lanes | Lane): Lanes {
return a | b;
}
export function removeLanes(set: Lanes, subset: Lanes | Lane): Lanes {
return set & ~subset;
}
export function intersectLanes(a: Lanes | Lane, b: Lanes | Lane): Lanes {
return a & b;
}
export function getHighestPriorityLane(lanes: Lanes): Lane {
// 取最低位的 1
return lanes & -lanes;
}
优先级队列
Scheduler 中使用优先级队列来为任务进行排序，并保证每次出队的任务均是优先级最高的任务，优先级队列有多种实现方式，React 的 Scheduler 是采用常用的小顶堆来实现的，详细内容可以参考 这篇笔记，下面是这篇笔记的部分内容：
优先级队列（Priority Queue）是一个抽象数据类型（Abstract Data Type, ADT） ，他支持插入元素（Enqueue）、删除具有最大或最小优先级的元素（Dequeue）。他可以用很多数据结构来实现，比如堆、二叉搜索树、数组等。
堆（Heap）是一个具体的数据结构，可以用来实现优先级队列，他实际上就是一棵 完全二叉树（最后一层可能不满），并且满足排序特点：大顶堆（Max-Heap）中父结点的优先级高于子结点，小顶堆（Min-Heap）中则相反。堆有很多变种，比如二叉堆、斐波那契堆、二项堆等，他们都有自己的特点。
JavaScript 中并没有提供原生的堆函数，而完全二叉树可以高效地用数组表示，因此我们可以手动用数组实现一个堆：
class Heap<T = any> {
// 二叉堆实际上是一棵树，但保证了节点的顺序
private tree: T[] = []
private compareFn: (a: T, b: T) => number
// compareFn 指定堆的特性，按照什么优先级构建堆，返回正数即意味着在 a 应当在 b 下面
// 比如当 a, b 均为 number，传入 a - b 就意味着 a > b 时，a 应当在 b 的下面，即为小顶堆
// arr 可以指定通过特定的数组进行堆的初始化
constructor(compareFn: (a: T, b: T) => number, arr?: T[]) {
this.compareFn = compareFn
if (arr) {
this.build(arr)
}
}
// 向堆底添加元素
public push(item: T) {
// 先将新的 HeapItem 直接放到堆的最底部
this.tree.push(item)
// 将刚刚 push 的 HeapItem 往上浮
this.up(this.size() - 1)
}
// 弹出堆顶元素
public pop(): T {
if (this.size() <= 1) {
return this.tree.pop()
}
const top = this.top()
// 将堆底最后一个元素弹出，替代掉堆顶的元素
const bottom = this.tree.pop()
this.tree[0] = bottom
// 将新的堆顶下沉
this.down(0)
return top
}
public top() {
return this.tree[0]
}
public size() {
return this.tree.length
}
// 返回正数时，指示 index1 应该在 index2 的下方，应该把 index1 往下沉，反之则代表 index2 需要往下沉
// 注意这与这是大顶堆还是小顶堆是没关系的，不管是大顶堆还是小顶堆，都是正数表示 index1 需要往下沉
private compare(index1: number, index2: number): number {
// 讨论越界情况，保证 undfined 值总是在最下面
// 当 index1 越界了，应该把 index1 所代表的 undefined 值往下沉
if (this.tree[index1] === undefined) { return 1 }
// 当 index2 越界了，应该把 index2 所代表的 undefined 值往下沉
if (this.tree[index2] === undefined) { return -1 }
// 正常情况由传入的 compareFn 决定
// 比如如果是小顶堆，应该写作类似 (a, b) => a - b，这样当 a 的值 > b 的值时，a 就会往下沉
return this.compareFn(this.tree[index1], this.tree[index2])
}
private down(index: number) {
// left 是左孩子 index，left + 1 是右孩子 index
let left = this.leftIndex(index)
// 找到要下沉到哪里，如果左孩子比右孩子更低，那么应该跟右孩子进行比较
// 否则可能出现操作完成后的节点比左孩子高、比右孩子低的情况（本应该节点比两个孩子都高）
let searchChild = this.compare(left, left + 1) > 0 ? left + 1 : left
// 注意 compare 的传参，因为要把 index 向下沉
while (searchChild < this.size() && this.compare(index, searchChild) > 0) {
[this.tree[index], this.tree[searchChild]] = [this.tree[searchChild], this.tree[index]]
index = searchChild
left = this.leftIndex(index)
searchChild = this.compare(left, left + 1) > 0 ? left + 1 : left
}
}
private up(index: number) {
// parent 是父结点的 index
let parent = this.parentIndex(index)
// 注意 compare 的传参，因为 index 是要从最底下往上浮
while (parent >= 0 && this.compare(parent, index) > 0) {
[this.tree[index], this.tree[parent]] = [this.tree[parent], this.tree[index]]
index = parent
parent = this.parentIndex(index)
}
}
// 通过数组构建堆
private build(arr: T[]) {
this.tree = [...arr]
for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
this.down(i)
}
}
private leftIndex(index: number) {
return 2 * index + 1
}
private parentIndex(index: number) {
return Math.floor((index - 1) / 2)
}
}
转载自:https://juejin.cn/post/7259258539163320379