React源码中使用的数据结构
主要说一说React中使用特定数据结构实现的功能以及内部工作原理。代码示例基本都是简化后的源码，只保留了关键逻辑，同时会附带源代码链接。 React版本为17.0.2。
开始前需要了解
-
ReactElements：JSX返回的对象，每次render之后都会重新创建，后面叫它元素。
-
Fiber Nodes：根据一个元素创建的对象，元素携带的信息会被合并到fiber中，不像元素，fiber每次render后不会重新创建，它是可变的，在react中承担virtualDOM的职责。 基于Fiber架构，React实现了如异步可中断的渲染、调度多个不同优先级的任务等看似很“魔幻”的特性，后面会讲到这两个特性实现的细节。
-
Update：在React中触发更新的方式只有两种，渲染root、调用setState。以setState举例，update是指调用setState创建的更新对象，记录待更新的值等信息，这个对象拥有一个lane属性，这个属性之后会被合并到fiber.lanes属性。
-
Reconciliation：对比新旧树的算法更新后需要对比新旧树的差异，来找出需要渲染的部分，值得一提的是源码中是使用旧fiber树和新元素树进行对比的。
-
Lanes：优先级模型，Fiber架构的一环，之前提到的调度多个不同优先级的任务就是基于它来实现的。lane是update对象的一个属性，是根据产生更新的“动作类型”来分配给update对象的优先级。 例如一个组件在componentDidMount和click事件中，各自调用了setState，这就会产生两个lane属性不同的update对象，click事件产生的lane优先级就会比componentDidmMount产生的更高，目的是尽快完成用户输入产生的更新。update.lane之后会被合并到fiber.lanes，代表某个fiber上所有未更新lane的集合（包含多个lanes的情况我们之后再说）。每次调用setState产生的update对象都有lane，代表本次更新的优先级。lane的类型非常多，有兴趣了解更多细节话可以看这个PR。
-
Root：根fiber节点，包含所有fiber节点产生的lanes：比如一个root包含ABfiber，fiberA.lanes为011、fiberB.lanes为100，fiberRoot.pendingLanes就是111。
链表和Fiber树
像数组一样，链表也是一种线性结构，但不同于数组，链表中的元素在内存中并不是连续的，链表中的元素除了自身的值，还拥有一个指针属性，指向下一个元素。相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。
fiber树就是一个链表，每个fiber对象都是一个链表节点，拥有return、sibling、child三个指针，分别指向父节点、兄弟节点和首个子节点。
为什么要将fiber设计成链表节点呢？React基于Fiber架构实现了异步可中断渲染：定期让出线程（暂停），从让步的进度继续完成，保证渲染不会阻塞线程太久。 举个例子，在正在渲染10000个元素，这个时候如果尝试在输入框输入内容或点击元素等，界面是完全没有反应的，因为这时线程一直在执行React源码（更新，创建fiber什么的）。 如果在渲染第100个元素时正好让出线程，这时候再有用户输入，由于线程是空闲的，所以可以响应输入，反馈输入后再从中断的第100个fiber继续剩下的更新。
显而易见的是，每次渲染都是从发起更新的节点开始处理一整条路径（对树进行深度遍历），很容易就可以想到递归，不过递归虽然可以中断，无法知道当前任务进度，更不可能实现从中断处恢复进度。Andrew Clark对Fiber架构的解释
所以使用某种数据结构来代替原本的递归调用栈，将处理每个节点的操作拆解为细小的单元，是实现可中断的第一步，之后才能进一步实现恢复进度，使用链表来表示这个树状的单元集合很明显比多维数组更加直观。
源码中的workLoopConcurrent会一直使用wip这个指针来遍历fiber树，同时beginWork和completeUnitOfWork会分别模拟递归入栈、出栈的行为。beginWork会返回子节点，complete会返回兄弟节点，或返回null并对父节点做完成操作，使用链表数据结构，可以随意的通过wip指针从中断处恢复未完成的工作。
function workLoopConcurrent() {
// 循环fiber树，workInProgress代表处理中的fiber
while (workInProgress !== null && !shouldYield()) {
performUnitOfWork(workInProgress);
}
}
function performUnitOfWork(unitOfWork: Fiber): void {
// performUnitOfWork根据元素类型的不同，执行的逻辑也不同，比如调用函数组件，实例化类组件，更新context的值等。
const current = unitOfWork.alternate;
let next;
// 相当于递归入栈，主要是检查是否需要更新，执行对应类型元素的初始化，reconciliation等。
next = beginWork(current, unitOfWork, subtreeRenderLanes);
unitOfWork.memoizedProps = unitOfWork.pendingProps;
if (next === null) {
// 这条路径处理完了（没有子节点了），开始执行出栈的逻辑。
completeUnitOfWork(unitOfWork);
} else {
workInProgress = next;
}
}
栈和Context
栈一种遵循后进先出原则（LIFO）的线性结构。
栈在react源码中的使用很多，这里挑一个我认为比较有代表性的：在contextAPI中的应用。
首先我们来看看React文档介绍context的一个特性：“一个Provider可以和多个消费组件有对应关系。多个Provider也可以嵌套使用，里层的会覆盖外层的数据。”
const MyContext = React.createContext(null);
const Content = () => (
<MyContext.Consumer>
{value => `The ${value} layer.`}
</MyContext.Consumer>
);
const Demo = () => (
<>
<MyContext.Provider value="outer">
<Content />
{/* 外层第一个Content为outer */}
<MyContext.Provider value="inner">
<Content />
{/* 里层的会覆盖外层的数据的特性，Content为inner */}
</MyContext.Provider>
<Content />
{/* 外层第二个Content为outer */}
</MyContext.Provider>
</>
);
了解这个特性之后，再看看问题，之前说过更新组件树的顺序是深度遍历：
外层Provider -> 外层第一个Content -> 内层Provier -> 内层Content -> 外层第二个Content
问题在于需要在处理完内层Provider一条路径后，再将value回溯到外层Provider，value为outer的状态。 很容易想到的解决方案是让Consumer和Provider实例关联，让其可以直接获取到正确的值，不过这样做可能需要很大的代价让Provider去查找对应的Consumer。
React内部是这样实现的： 声明全局变量valueStack、valueCursor、index，分别代表contextValue的历史记录栈，上次contextValue的值、上次contextValue在栈中的索引。
举个例子：本次value为outer，执行pushProvider时，这三个变量分别是[null]、null(null是cursor的初始值)、0，value为inner执行pushProvider时为[null, 'outer']、outer、1。
所有的context实例，都使用这三个全局变量。
在遍历fiber树时，遇到Provider类型fiber就会执行pushProvider函数：增加索引，改变指针，将上层context（如果这个Provider上层还有Provider的话）的value存到stack中（下层如果有Provider，保证其能获取到本次的值，回溯的关键），更新cursor指向本次的value，最后更新context实例的value。
当处理完这条路径的所有节点，也就是出栈时执行popProvider函数，以这个例子来说，处理完innerContext这条路径之后就要回溯处理外层第二个Context，popProvider做了一些恢复操作，保证随后执行的第三次pushProvider获取到正确的contextValue。
export function pushProvider(context, nextValue) {
index++;
valueStack[index] = valueCursor.current;
valueCursor.current = value;
context._currentValue = nextValue;
}
export function popProvider(context) {
// cursor指向的是上次的值，根据是否嵌套使用Provider指向上层contextValue或已经赋值为null
const currentValue = valueCursor.current;
valueCursor.current = valueStack[index];
// 删除栈中上次contextValue的记录，因为当前Provider已经出栈，再有需要会使用上次(外层)的值，不需要再对上次保留记录
valueStack[index] = null;
index--;
// 更新context实例的值为上次的值
context._currentValue = currentValue;
}
其实使用栈来实现记录context变化和之前的使用链表实现fiber树很像，一样在使用数据结构来替代原本的递归调用栈，以便可以手动控制栈中的值。
二叉堆
二叉堆是满足以下两个特性的二叉树。
- 一棵完全二叉树，树的每一层都有左右子节点（除了最后一层的叶节点），并且最后一层的叶节点尽可能都是左侧子节点。二叉堆的这个特性使它很适合使用数组表示。
- 二叉堆不是最小堆就是最大堆。最小堆中，堆顶的节点就是最小的。所有的节点都小于等于每个它的子节点。最大堆和最小堆相反。
下面两个堆都是合法的：
10 10
/ \ / \
20 100 15 30
/ / \ / \
30 40 50 100 40
二叉堆可以用数组来表示：
- 堆顶元素在索引0的位置
- 以i表示为自身索引，(i - 1) / 2指向父节点
- (2 * i) + 1指向左子节点
- (2 * i) + 2指向右子节点
堆的操作
siftUp()：上移操作，将这个节点和它的父节点进行交换，直到父节点小于这个值，时间复杂度为 O(Logn)，如果父节点不小于它，就不需要操作，因为剩余部分是满足堆特性的。
function siftUp(heap, node, i) {
let index = i;
while (index > 0) {
const parentIndex = (index - 1) >>> 1;
const parent = heap[parentIndex];
if (compare(parent, node) > 0) {
// The parent is larger. Swap positions.
heap[parentIndex] = node;
heap[index] = parent;
index = parentIndex;
} else {
// The parent is smaller. Exit.
return;
}
}
}
siftDown()：下移操作，将这个节点与它的左右子节点交换，直到子节点大于它，时间复杂度为 O(Logn)。
function siftDown(heap, node, i) {
let index = i;
const length = heap.length;
const halfLength = length >>> 1;
while (index < halfLength) {
const leftIndex = (index + 1) * 2 - 1;
const left = heap[leftIndex];
const rightIndex = leftIndex + 1;
const right = heap[rightIndex];
// If the left or right node is smaller, swap with the smaller of those.
if (compare(left, node) < 0) {
if (rightIndex < length && compare(right, left) < 0) {
heap[index] = right;
heap[rightIndex] = node;
index = rightIndex;
} else {
heap[index] = left;
heap[leftIndex] = node;
index = leftIndex;
}
} else if (rightIndex < length && compare(right, node) < 0) {
heap[index] = right;
heap[rightIndex] = node;
index = rightIndex;
} else {
// Neither child is smaller. Exit.
return;
}
}
}
push()：向堆中插入值，时间复杂度为 O(Logn)，因为插入元素后要维持二叉堆的特性，需要对新插入的元素执行siftUp操作。
export function push(heap: Heap, node: Node): void {
const index = heap.length;
heap.push(node);
siftUp(heap, node, index);
}
pop()：移除堆顶元素，再将末尾元素放到堆顶，时间复杂度为 O(Logn)，因为移除元素后要维持二叉堆的特性，需要对堆顶元素执行siftDown操作。
export function pop(heap: Heap): Node | null {
if (heap.length === 0) {
return null;
}
const first = heap[0];
const last = heap.pop();
if (last !== first) {
heap[0] = last;
siftDown(heap, last, 0);
}
return first;
}
Scheduler
众所周知setState有批量更新的行为，就实现来说，setState产生update对象之后并不是立即去更新，而是将准备执行的任务存放到一个任务队列中，所以setState并没有执行任何更新，只是记录一些待处理的信息，再将一次更新要执行的任务放到一个任务队列中。
真正执行（调度）任务的是Schduler模块，一个职责单一的调度器，作为代码库设计，不与React耦合。Scheduler的主要功能包含：排序任务队列中的任务，挑选优先级最高的任务以异步的方式执行、在线程空闲时唤起未完成的任务（在React中的体现就是workLoop的中断）。
React会去调用Scheduler的scheduleCallback函数，将performConcurrentWorkOnRoot函数注册到scheduler的taskQueue，之后这个任务什么时候该被执行就交给Scheduler了，React不再负责。
function unstable_scheduleCallback(priorityLevel, callback, options) {
var currentTime = getCurrentTime();
var startTime = currentTime;
var timeout;
switch (priorityLevel) {
case ImmediatePriority:
timeout = IMMEDIATE_PRIORITY_TIMEOUT;
break;
case UserBlockingPriority:
timeout = USER_BLOCKING_PRIORITY_TIMEOUT;
break;
case IdlePriority:
timeout = IDLE_PRIORITY_TIMEOUT;
break;
case LowPriority:
timeout = LOW_PRIORITY_TIMEOUT;
break;
case NormalPriority:
default:
timeout = NORMAL_PRIORITY_TIMEOUT;
break;
}
// 过期时间，如果过期了会把这个任务放到队首，各优先级的过期时间也不同。
var expirationTime = startTime + timeout;
var newTask = {
id: taskIdCounter++,
callback,
priorityLevel,
startTime,
expirationTime,
sortIndex: -1,
};
// sortIndex是队列给任务排序的参照，可看出是基于过期时间设置的，越小就越优先（距当前时间最近）。
newTask.sortIndex = expirationTime;
// 操作二叉堆
push(taskQueue, newTask);
// 这里调用栈很深，没做什么关键的事，主要就是一直调用`workLoop`函数（Scheduler和React中有同名函数）尝试清空任务队列。
requestHostCallback(flushWork);
return newTask;
}
function workLoop(hasTimeRemaining, initialTime) {
let currentTime = initialTime;
currentTask = peek(taskQueue);
while (currentTask !== null) {
if (
currentTask.expirationTime > currentTime &&
(!hasTimeRemaining || shouldYieldToHost())
) {
// 如果没有过期，这里也会调用shouldYieldToHost让出线程
break;
}
const callback = currentTask.callback;
currentTask.callback = null;
currentPriorityLevel = currentTask.priorityLevel;
const didUserCallbackTimeout = currentTask.expirationTime <= currentTime;
// React的`performConcurrentWorkOnRoot`函数会接受Scheduler传过来的是否过期标识，如果已经过期，React会发起不可中断的更新
// `performConcurrentWorkOnRoot`函数还会根据React是否已经处理完全部fiber来给Scheduler返回自身或者null
// 中断的情况需要通知Scheduler不要将自己从任务队列中清除，等待机会继续执行这个任务
const continuationCallback = callback(didUserCallbackTimeout);
if (typeof continuationCallback === 'function') {
// 将这个task对象的callback设置为返回的函数
currentTask.callback = continuationCallback;
} else {
// 任务结束，移出队列
if (currentTask === peek(taskQueue)) {
pop(taskQueue);
}
}
currentTask = peek(taskQueue);
}
if (currentTask !== null) {
// 返回队列中还是否有任务的标识
return true;
} else {
return false;
}
}
最后说一说调度多个优先级不同的任务
之前我们提到过一个fiber.lanes属性可能包含多种不同优先级的lane，这种情况是最常见的：workLoop让步时（存在未完成的任务），某组件产生了一次新的更新，这种情况下fiber.lanes就包含两种lane，它已有的和新产生的。
如果一个fiber有多个lanes，React就需要挑选出优先级最高的部分更新来执行。 现在假设已经存在的任务是将state设为A，新任务是将state设为B，会有已存在的更优先和新的更优先两种情况：
已存在任务优先级更高的情况，继续执行将设为state为A的任务，state为B的更新部分会被跳过，内部实际上是这样工作的：每次执行更新时都对比当前已经存在的lanes和新的未处理lanes(root.pendingLanes)，这些低优先级的lanes都会被跳过（比如state的更新），等待下一次调度。 所以在已存在任务优先级更高的情况下再次以低优先级的动作调用setState，React不会把这两次setState合并到同一批次处理，而是先执行高优先级任务。
// 跳过优先级低于基本优先级更新的源码，这部分在`processUpdateQueue`函数
if (!isSubsetOfLanes(renderLanes, updateLane)) {
// Priority is insufficient. Skip this update. If this is the first
// skipped update, the previous update/state is the new base
// update/state.
const clone: Update<State> = {
eventTime: updateEventTime,
lane: updateLane,
tag: update.tag,
payload: update.payload,
callback: update.callback,
next: null,
};
if (newLastBaseUpdate === null) {
// 被跳过的update对象都会被收集到`baseUpdate`队列，等待下一次处理
newFirstBaseUpdate = newLastBaseUpdate = clone;
newBaseState = newState;
} else {
newLastBaseUpdate = newLastBaseUpdate.next = clone;
}
// Update the remaining priority in the queue.
newLanes = mergeLanes(newLanes, updateLane);
}
新任务优先级更高的情况，需要取消已存在的任务，以更高优先级在Scheduler上注册一个新的performConcurrentWorkOnRoot，这种情况可以理解为高优先级任务的插队。
// 取消低优先级任务的源码，这部分在`ensureRootIsScheduled`函数
const nextLanes = getNextLanes(
root,
root === workInProgressRoot ? workInProgressRootRenderLanes : NoLanes,
);
// We use the highest priority lane to represent the priority of the callback.
const newCallbackPriority = getHighestPriorityLane(nextLanes);
// Check if there's an existing task. We may be able to reuse it.
// 获取已存在任务优先级
const existingCallbackPriority = root.callbackPriority;
if (existingCallbackPriority === newCallbackPriority) {
// The priority hasn't changed. We can reuse the existing task. Exit.
// 新旧任务优先级相同，直接复用已存在任务就可以顺便把新的更新处理
return;
}
// `getNextLanes`会筛选出已存在和未处理优先级中较高的，所以这里已存在的lane优先级只可能更低或者是上面的相等
if (existingCallbackNode != null) {
// Cancel the existing callback. We'll schedule a new one below.
// 取消已有的任务，等待下次调度再完成它
cancelCallback(existingCallbackNode);
}
转载自:https://juejin.cn/post/7063015348403961864