Que's Blog

WebFrontEnd Development

0%

react-v16-Reconciler和Diff算法

发表于 阅读次数：
前面几篇重点分析了Render & Update, 乃至Fiber链的构建细节。这里就有余地去分析V16的Diff算法是如何实现了。根据之前的Update两篇分析，可以很容易知道这个Diff集中在了render phase, 而随后的commit phase实际上就是patch这个diff的过程。因为Diff实际上是由Reconciler来实现的，所以这里也把它整理一下。

前言

前面几篇重点分析了Render & Update, 乃至Fiber链的构建细节。这里就有余地去分析V16的Diff算法是如何实现了。根据之前的Update两篇分析，可以很容易知道这个Diff集中在了render phase, 而随后的commit phase实际上就是patch这个Diff的过程。

回顾之前v15的diff算法，因为其Tree结构的缘故，一旦理解了之后，对其Component Diff、Tree Diff、Element Diff算是印象深刻。这里需要循着它的思路，参考更新的render phase来深入理解这个Diff有什么变化。

但是之前的例子也相对简单，为了Diff分析的全面，也不能简单直接循着它的思路，总之这是一个入乎其内，又出其外的过程。相应的，这篇主要是关注Diff流程，对Update的分析，一切以它为目标。

所以这里每个函数的分析，都要和Diff有联系，但是又要在之前Update篇上有进一步的深度。

正文

这里还是顺着前文的Event调用栈来说。以下是触发事件过程中的调用栈

1
2
3
4
5
6
dispatchInteractiveEvent
->interactiveUpdates
-->dispatchEvent
--->performSyncWork
---->performWork
----->performWorkOnRoot -> renderRoot & completeRoot

这里对performWork做点扩展

1
2
3
4
5
performWork () {
    findHighestPriorityRoot()
    performWorkOnRoot -> renderRoot & completeRoot
    findHighestPriorityRoot()
}

findHighestPriorityRoot

这个函数有两个作用，一个是无效节点从链表移除，再一个是返回最终优先节点。

Tips: 这一小节在ReactDom环境下，其实偏废话，不愿意看可以直接拉到小结。

无效节点清除

这个findHighestPriorityRoot函数需要比照之前的Update-RenderPhase来看。因为它这里涉及了firstScheduledRoot、lastScheduledRoot、root.nextScheduledRoot的赋值。所以简述一下它内部逻辑。但是这之前必须先看看另外一个函数addRootToSchedule:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function addRootToSchedule(root: FiberRoot, expirationTime: ExpirationTime) {
  // 检查这个fiber节点是否已经是schedule的一部分: 
  if (root.nextScheduledRoot === null) {
    // root.nextScheduledRoot === null 说明还没有加入 这里加入它
    root.expirationTime = expirationTime;
    if (lastScheduledRoot === null) {
      // lastScheduledRoot为空 将这个fiber设为[first|last]ScheduledRoot
      // root.nextScheduledRoot也设为自身 这只在仅有一个更新fiber发生
      firstScheduledRoot = lastScheduledRoot = root;
      root.nextScheduledRoot = root;
    } else {
      // 否则 将lastScheduledRoot下一个链表设为这个root 然后将root设为最后一个(实质是添加一个元素到链表尾部)
      // 并将这个root的nextScheduledRoot设置到firstScheduledRoot
      lastScheduledRoot.nextScheduledRoot = root;
      lastScheduledRoot = root;
      lastScheduledRoot.nextScheduledRoot = firstScheduledRoot;
    }
  } else {
    // 这个root已经在schedule里面 但是可能有属性变化
    const remainingExpirationTime = root.expirationTime;
    if (expirationTime > remainingExpirationTime) {
      // 更新时间 以便后面它能被更新
      root.expirationTime = expirationTime;
    }
  }
}

接下来我们继续下面的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
function findHighestPriorityRoot() {
  let highestPriorityWork = NoWork;
  let highestPriorityRoot = null;
  // 这说明之前至少已经有个更新了 所以至少有一个需要操作的fiber节点
  // 这里配合addRootToSchedule函数要去理解
  if (lastScheduledRoot !== null) {
    let previousScheduledRoot = lastScheduledRoot;
    let root = firstScheduledRoot;
    // 这里是一个循环 它会遍历所有root.nextScheduledRoot
    // 直到nextFlushedRoot & nextFlushedExpirationTime得到合理赋值
    while (root !== null) {
      const remainingExpirationTime = root.expirationTime;
      if (remainingExpirationTime === NoWork) {
        // 进入这个分支 说明这个fiber节点没有事情要做了 将其从scheduler里面移除

        // 这里配合addRootToSchedule函数要去理解
        if (root === root.nextScheduledRoot) {
          // 判断是否仅有的 第一个 初始 更新 然后跳出while
          // 因为只有一个更新就不需要考虑后面还有更高优先级 这个fiberNode本身就是
          // 因为此时是要移除 所以仅仅将其赋值null就完事了 可以break了
          root.nextScheduledRoot = null;
          firstScheduledRoot = lastScheduledRoot = null;
          break;
        } else if (root === firstScheduledRoot) {
          // 将第一个元素从链表顶部移除 并设定root.nextScheduledRoot = null
          // 这个操作会因为while继续循环 直到 lastScheduledRoot.nextScheduledRoot!== null
          const next = root.nextScheduledRoot;
          firstScheduledRoot = next;
          lastScheduledRoot.nextScheduledRoot = next;
          root.nextScheduledRoot = null;
        } else if (root === lastScheduledRoot) {
          // 此时遍历到尾部了 而且并非唯一节点(因为没有进入第一个分支) 此时是这里最后一次进while
          // 将lastScheduledRoot.nextScheduledRoot重置为firstScheduledRoot完成圆形闭环
          lastScheduledRoot = previousScheduledRoot;
          lastScheduledRoot.nextScheduledRoot = firstScheduledRoot;
          root.nextScheduledRoot = null;
          break;
        } else {
          // 这是链表中间节点的操作 从链表中移除一个中间节点 
          // 此时给previousScheduledRoot.next赋值root.next,实质上是在为while里面
          // 的root赋值(root = previousScheduledRoot.nextScheduledRoot)
          previousScheduledRoot.nextScheduledRoot = root.nextScheduledRoot;
          root.nextScheduledRoot = null;
        }
        root = previousScheduledRoot.nextScheduledRoot;
      } else {
        if (remainingExpirationTime > highestPriorityWork) {
          // 如果expirationTime大于之前缓存的最大值 把这个root相关数据设为最高优先级
          highestPriorityWork = remainingExpirationTime;
          highestPriorityRoot = root;
        }
        if (root === lastScheduledRoot) {
          break;
        }
        if (highestPriorityWork === Sync) {
          // Sync is highest priority by definition so
          // we can stop searching.
          break;
        }
        previousScheduledRoot = root;
        root = root.nextScheduledRoot;
      }
    }
  }

  nextFlushedRoot = highestPriorityRoot;
  nextFlushedExpirationTime = highestPriorityWork;
}

findHighestPriorityRoot其中一个作用就是清除所有fibler.expirationTime === NoWork的节点。根据addRootToSchedule定义 仔细体味，我们可以知道这个链表是圆环。

接下来就是相对精彩的链表清空环节。这里我们还是来举例配合代码注释来理解。

1
2
3
4
5
6
7
8
+---+      +---+      +---+
| A +----->+ B +----->+ C |
+-+-+      +---+      +-+-+
  ^                     |
  |                     v
+-+-+      +---+      +-+-+
| F +<-----+ E +<---+ | D |
+---+      +---+      +---+

这里A为first，F为last。然后看看remainingExpirationTime === NoWork里面的分支。

  • 只有root为last才会break跳出，其他的不会

  • 当root为A(此时A为first)，且A.expirationTime === NoWork。此时：

    • first = A.next = B
    • last.next = B
    • A.next = null

  • 当root为中间节点时候， 比如为B.expirationTime === NoWork。此时:

    • previousScheduledRoot = F.next === A 但是F节点还是F节点(这个需要重点理解)
    • previousScheduledRoot(A.next) = B.next = C
    • 上面两步实质上就是将B从链表上丢掉了，链接了上一个和下一个链表元素
    • B.next 赋值为null

  • 当遍历到最终的last也就是F节点，且为无效节点时候。此时:

    • 将last赋值为E(previousScheduledRoot)
    • 将E.next重新赋值first 完成圆形闭环。

这一步其实其实就是链表元素的的移除操作。掌握这个数据结构还是很重要。但是其实归根结底还是逆向解读相对折腾，自己写大家应该都能写出来，然而一旦复杂起来，过几个月估计就只有上帝直到写的什么了😂

这里要注意addRootToSchedule上游调用函数scheduleWork会给他传入fiberRoot参数。所以nextFlushedRoot其实一般就是fiberRoot(一些情况下是null)。

返回优先节点

相比上面复杂度链表移除操作。这个返回操作就格外简单。就是找出expirationTime最大的fiber节点。然后返回，如果遇到expirationTime === Sync的停止继续比较直接返回之前计算结果。

小结

这个函数在Scheduled列表上清掉了无效节点，关联的核心是每个节点的nextScheduledRoot属性。通过它可以快速对多个FiberRoot进行调度，它将优先级最高的FiberRoot设为nextFlushedRoot。

这个nextFlushedRoot，将会在下一步中被使用。

关于FiberRoot这点，代码里面对类型有很明显的类型限定。

1
2
3
4
// Linked-list of roots
let firstScheduledRoot: FiberRoot | null = null;
let lastScheduledRoot: FiberRoot | null = null;
let nextFlushedRoot: FiberRoot | null = null;

这里很容易有一个问题是，如果都是FiberRoot为什么需要一个链表(ReactDOM仅有唯一一个FiberRoot)。

这是因为React不仅仅服务于ReactDOM，它还会服务于ReactNative。在ReactNative中它可能会使用不同的root scheduler, 这和ReactDom仅仅使用一个root scheduler有所不同。

这实质上是renderer(渲染器)和 scheduler(调度器)的分离。不过这个显然超出本篇的范围了，这里不做深入了。

唯一可以说的，是这一小节在ReactDom里面可能其实都是废话，它这里做的就是设nextFlushedRoot为FiberRoot而已。

performWork

这个函数我们暂时关注在它同步的逻辑分支里面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function performWork(minExpirationTime: ExpirationTime, isYieldy: boolean) {
  // 确保nextFlushedRoot是scheduled链表中的最高优先级fiberNode
  findHighestPriorityRoot();

  if (isYieldy) {
	// 异步逻辑暂时不管
  } else {
    while (
      nextFlushedRoot !== null &&
      nextFlushedExpirationTime !== NoWork &&
      minExpirationTime <= nextFlushedExpirationTime
    ) {
      performWorkOnRoot(nextFlushedRoot, nextFlushedExpirationTime, false);
      findHighestPriorityRoot();
    }
  }

配合上文对findHighestPriorityRoot的理解加上之前文章对performWorkOnRoot的分析。立刻就可以发现很多有意思的地方了。

  • performWorkOnRoot会调用workLoop对nextFlushedRoot节点进行遍历
  • findHighestPriorityRoot移除完成的fiberNode，然后如果还有有效值 继续performWorkOnRoot
  • 直到nextFlushedRoot再无有效值

所以说 这里对于performWork函数这里有进一步的认知。它是对scheduled链表完整的遍历。而performWorkOnRoot只是针对指定的root节点来进行遍历。

performWorkOnRoot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function performWorkOnRoot(
  root: FiberRoot,
  expirationTime: ExpirationTime,
  isYieldy: boolean,
) {
  isRendering = true;

  if (!isYieldy) {
    let finishedWork = root.finishedWork;
    if (finishedWork !== null) {
      // finishedWork有非null值说明一切就绪可以进入commit phase
      completeRoot(root, finishedWork, expirationTime);
    } else {
      root.finishedWork = null;
	  // 如果之前暂停了任务 需要清除root.timeoutHandle。cancelTimeout实质上是clearTimeout
      // 这里单独包装一个是因为一些环境 比如ssr下没有clearTimeout
      // 这里暂时没看到异步暂停这块 可以忽略 不是必经路径
      const timeoutHandle = root.timeoutHandle;
      if (timeoutHandle !== noTimeout) {
        root.timeoutHandle = noTimeout;
        cancelTimeout(timeoutHandle);
      }
      renderRoot(root, isYieldy);
      finishedWork = root.finishedWork;
      if (finishedWork !== null) {
        // We've completed the root. Commit it.
        completeRoot(root, finishedWork, expirationTime);
      }
    }
  } else {
    // Flush async work. 异步任务 暂时略
  }

  isRendering = false;
}

这里核心路径是:

  • 如果root.finishedWork有非空值 进入commit phase
  • 否则执行renderRoot
  • renderRoot会更新root.finishedWork值，接下来进入commit phase(completeRoot)

renderRoot

renderRoot是一个很复杂的函数。但是随着相关细节理解深入。可以做很多精简了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
function renderRoot(root: FiberRoot, isYieldy: boolean): void {
  flushPassiveEffects(); // 这个函数暂时没搞懂 和effect有关 但是不一定会进去 故可略过

  isWorking = true; // 作为禁止被递归调用的Flag
  const previousDispatcher = ReactCurrentDispatcher.current;
  ReactCurrentDispatcher.current = ContextOnlyDispatcher;

  const expirationTime = root.nextExpirationTimeToWorkOn;

  // 判断是一个新的stack开始，还是从之前被中断的地方开始 这里不理会
  if (
    expirationTime !== nextRenderExpirationTime ||
    root !== nextRoot ||
    nextUnitOfWork === null
  ) {}

  if (enableSchedulerTracing) { } // 给开发工具用的 略

  let didFatal = false;

  startWorkLoopTimer(nextUnitOfWork);

  do {
    try {
      workLoop(isYieldy);
    } catch (thrownValue) {} // 错误捕获用的 这里也不管
    break;
  } while (true);

  if (enableSchedulerTracing) { } // 给开发工具用的 略

  // We're done performing work. Time to clean up.
  isWorking = false;
  ReactCurrentDispatcher.current = previousDispatcher;
  resetContextDependences();
  resetHooks();

  // Yield back to main thread.
  if (didFatal) {} // workLoop的catch里面会定义为true 这里忽略

  if (nextUnitOfWork !== null) {
    // tree里面仍有异步任务 但是没时间继续完成任务了 先返回渲染主线程 代码略
  }

  // We completed the whole tree.
  const didCompleteRoot = true;
  stopWorkLoopTimer(interruptedBy, didCompleteRoot);
  const rootWorkInProgress = root.current.alternate;

  // `nextRoot`指向正在进行的根。非空值意味着我们正处于异步渲染的过程中
  // 将其设置为null则表示 在当前批次中没有更多的工作要做。
  nextRoot = null;
  interruptedBy = null;

  if (nextRenderDidError) {} // workLoop的catch里面会调用throwException()

  if (isYieldy && nextLatestAbsoluteTimeoutMs !== -1) {} // 异步相关 不管

  // Ready to commit.
  onComplete(root, rootWorkInProgress, expirationTime);
}

这里认真分析了一下，清除了大部分干扰代码，最终还是确认移除了异步处理、错误处理、追踪(开发工具)处理之后。它核心地方是workLoop & onComplete。onComplete相关到commit Phase,我们再update的commit phase里面确认了Diff和它无关。所以核心就是workLoop了。

workLoop

这个函数的核心是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
while (nextUnitOfWork !== null) {
    nextUnitOfWork = performUnitOfWork(nextUnitOfWork);
}
function performUnitOfWork(workInProgress: Fiber): Fiber | null {
  const current = workInProgress.alternate;

  // See if beginning this work spawns more work.
  startWorkTimer(workInProgress);

  let next;
  if (enableProfilerTimer) {} else {
    next = beginWork(current, workInProgress, nextRenderExpirationTime);
    workInProgress.memoizedProps = workInProgress.pendingProps;
  }

  if (next === null) {
    // If this doesn't spawn new work, complete the current work.
    next = completeUnitOfWork(workInProgress);
  }
  ReactCurrentOwner.current = null;
  return next;
}

这里就是Diff算法核心入口了，因为fiberNode遍历在这里得到提现。

beginWork返回fiber的child，performUnitOfWork返回fiber的next，而completeUnitOfWork返回fiber的return。

所谓大胆推测，小心求证。这里我们可以做一些推测，然后小心验证它。

这里大胆又保守的推测，我们在v15里面的用到的CompoentDiff、Tree Diff、Element Diff依然存在。因为所有的Diff实质上都是和child相关，所以可以大胆猜测，Diff相关逻辑，实质上都存在于beginWork——这也比较符合beginWork的命名。

beginWork

这里略去大多数干扰代码，仅仅保留常见的IndeterminateComponent、FunctionComponent、ClassComponent之类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 function beginWork(
  current: Fiber | null,
  workInProgress: Fiber,
  renderExpirationTime: ExpirationTime,
): Fiber | null {
  const updateExpirationTime = workInProgress.expirationTime;

  if (current !== null) {
    const oldProps = current.memoizedProps;
    const newProps = workInProgress.pendingProps;

    if (oldProps !== newProps || hasLegacyContextChanged()) {
      didReceiveUpdate = true;
    } else if (updateExpirationTime < renderExpirationTime) {
      didReceiveUpdate = false;
      // 这里和diff无关 先不管了
    }
  } else {
    didReceiveUpdate = false;
  }

  // Before entering the begin phase, clear the expiration time.
  workInProgress.expirationTime = NoWork;

  switch (workInProgress.tag) {
    case IndeterminateComponent: {
      const elementType = workInProgress.elementType;
      return mountIndeterminateComponent(
        current,
        workInProgress,
        elementType,
        renderExpirationTime,
      );
    }
    case LazyComponent: : { }
    case FunctionComponent: {
      const Component = workInProgress.type;
      const unresolvedProps = workInProgress.pendingProps;
      const resolvedProps =
        workInProgress.elementType === Component
          ? unresolvedProps
          : resolveDefaultProps(Component, unresolvedProps);
      return updateFunctionComponent(
        current,
        workInProgress,
        Component,
        resolvedProps,
        renderExpirationTime,
      );
    }
    case ClassComponent: {
      const Component = workInProgress.type;
      const unresolvedProps = workInProgress.pendingProps;
      const resolvedProps =
        workInProgress.elementType === Component
          ? unresolvedProps
          : resolveDefaultProps(Component, unresolvedProps);
      return updateClassComponent(
        current,
        workInProgress,
        Component,
        resolvedProps,
        renderExpirationTime,
      );
    }
    case HostRoot:
      return updateHostRoot(current, workInProgress, renderExpirationTime);
    case HostComponent: { 
      return updateHostComponent(current$$1, workInProgress, renderExpirationTime)
    }
    case HostText: { }
    case SuspenseComponent: { }
    case HostPortal: { }
    case ForwardRef: { }
    case Fragment: { }
    case Mode: { }
    case Profiler: { }
    case ContextProvider: { }
    case ContextConsumer: { }
    case MemoComponent: { }
    case SimpleMemoComponent: { }
    case IncompleteClassComponent: {}
    case DehydratedSuspenseComponent: {}
  }
}

ClassComponent

这里重点关注ClassComponent，毕竟v15还是以它为主的分析，方便参照。

这里updateClassComponent函数正常更新的话，主要是两个调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 这个函数根据workInProgress上的updateQueue、props、lifecyclesHooks更新了stateNode属性
// 也就是组件实例 新的props之类都在这个stateNode上保存起来了
shouldUpdate = updateClassInstance(
    current,
    workInProgress,
    Component,
    nextProps,
    renderExpirationTime,
);
const nextUnitOfWork = finishClassComponent( // 看下面 单独分析
    current,
    workInProgress,
    Component,
    shouldUpdate,
    hasContext,
    renderExpirationTime,
);
return nextUnitOfWork;

finishClassComponent检测到变化后，主要调用则如下:

1
2
3
4
5
6
7
8
const instance = workInProgress.stateNode;
nextChildren = instance.render(); // 更新后的实例，render执行会返回一个VDOM树
reconcileChildren( // reconcileChildren等价于ChildReconciler(true)
    current,
    workInProgress,
    nextChildren,
    renderExpirationTime,
);

ChildReconciler在React中的注释说到这个函数以后可能单独抽出进行手动或者编译器自动优化。这个函数里面helpers辅助函数太多。总之它执行后返回的是内部函数reconcileChildFibers。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
function reconcileChildFibers(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChild: any,
  expirationTime: ExpirationTime,
): Fiber | null {

  // 处理<React.Fragment></React.Fragment>语法 对其采用数组一样的处理逻辑
  const isUnkeyedTopLevelFragment =
    typeof newChild === 'object' &&
    newChild !== null &&
    newChild.type === REACT_FRAGMENT_TYPE &&
    newChild.key === null;
  if (isUnkeyedTopLevelFragment) {
    newChild = newChild.props.children;
  }

  // Handle object types
  const isObject = typeof newChild === 'object' && newChild !== null;

  if (isObject) { // 正常的VDOM处理流程
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE:
        return placeSingleChild( // ★ 这里是我们的核心关注点
          reconcileSingleElement(
            returnFiber,
            currentFirstChild,
            newChild,
            expirationTime,
          ),
        );
      case REACT_PORTAL_TYPE: {} // 略
  }

  if (typeof newChild === 'string' || typeof newChild === 'number') { // 处理文本 & 数字
    return placeSingleChild(
      reconcileSingleTextNode(
        returnFiber,
        currentFirstChild,
        '' + newChild,
        expirationTime,
      ),
    );
  }

  if (isArray(newChild)) {
    return reconcileChildrenArray(
      returnFiber,
      currentFirstChild,
      newChild,
      expirationTime,
    );
  }

  // 迭代器处理 暂时还没听过render里面可以返回一个generator函数得。是否有一天我们可以这样做？
  // 还是有其他考虑？
  if (getIteratorFn(newChild)) {}

  if (isObject) { } // 针对上级节点是textarea的抛错

  if (typeof newChild === 'undefined' && !isUnkeyedTopLevelFragment) { } // 抛出错误

  // Remaining cases are all treated as empty.
  return deleteRemainingChildren(returnFiber, currentFirstChild);
}

单节点Children

单节点的children个人实质上就是ComponentDiff的践行。但是这里也对Tree Diff有了部分实践，因为它同时承担了一部分的删除操作，维护了FiberNode的siblings。

这里看看placeSingleChild函数。

1
2
3
4
5
6
7
8
9
10
11
function placeSingleChild(newFiber: Fiber): Fiber {
    // This is simpler for the single child case. We only need to do a
    // placement for inserting new children.
    // 对于单root节点的VDOM树。我们只需要使用新的children替换即可
    // shouldTrackSideEffects = true -> reconcileChildren等价于ChildReconciler(true)
    // 这个shouldTrackSideEffects就是传入的写死的true参数
    if (shouldTrackSideEffects && newFiber.alternate === null) {
        newFiber.effectTag = Placement;
    }
    return newFiber;
}

这里面注释很明了，我们的Component Diff就这样轻描淡写的做好了标记，有些措不及防。。。

另外就是，既然这里说了: 如果是single child case，那么自然就会有multiple child case。那么，可以很自然的做出推测，这里的multiple child case，其实质就是ElementDiff或者TreeDiff——我们继续分析验证reconcileSingleElement函数。

但是这之前，根据placeSingleChild传参类型和返回类型，我们可以确认reconcileSingleElement返回的是一个FiberNode。另外要额外对它的alternate属性追踪和关注，以完成Component Diff分析闭环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement,
  expirationTime: ExpirationTime,
): Fiber {
  const key = element.key;
  let child = currentFirstChild;
  while (child !== null) {
    if (child.key === key) { // 如果是单节点 这里相等，那么需要进行后续对比
      // 判断Fragment还是常规HostComponent、ClassComponent的合法性
      if (
        child.tag === Fragment
          ? element.type === REACT_FRAGMENT_TYPE
          : child.elementType === element.type
      ) {
        deleteRemainingChildren(returnFiber, child.sibling);
        const existing = useFiber(
          child,
          element.type === REACT_FRAGMENT_TYPE
            ? element.props.children
            : element.props,
          expirationTime,
        );
        existing.ref = coerceRef(returnFiber, child, element);
        existing.return = returnFiber;
        return existing;
      } else {
        deleteRemainingChildren(returnFiber, child);
        break;
      }
    } else {
      // 否则直接标记删除 并将child放到nextEffect上以备递归删除下级节点
      deleteChild(returnFiber, child); 
    }
    child = child.sibling;
  }

  if (element.type === REACT_FRAGMENT_TYPE) { // 保持简洁和关注 这里分支不理会了
  } else { // 正常VDOM逻辑
    const created = createFiberFromElement(
      element,
      returnFiber.mode,
      expirationTime,
    );
    created.ref = coerceRef(returnFiber, currentFirstChild, element);
    created.return = returnFiber;
    return created;
  }
}

这里由一个while循环。但是分析这个循环之前，草草扫过这个代码，基本已经可以确认它是Tree Diff的核心了。言归正传，返回这个while的分析。

这个while实质上是做的fiberNode链表和VDOM树的对比。它从给定的一个FiberNode遍历到它后面所有的FiberNode节点。

这个循环，实质是上单层的循环，它只是针对同一层级的VDOM对应的FiberNode进行了标记。child = child.sibling说明了这一点。

这里主要是删除的逻辑。分析一下相关函数:

deleteChild函数直接标记删除(effectTag = Deletion) 并将child放到nextEffect上以备递归删除下级节点。

而deleteRemainingChildren则是做一些遍历然后调用deleteChild标记删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function deleteRemainingChildren(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
): null {
  if (!shouldTrackSideEffects) {
    // Noop.
    return null;
  }

  // TODO: For the shouldClone case, this could be micro-optimized a bit by
  // assuming that after the first child we've already added everything.
  let childToDelete = currentFirstChild;
  while (childToDelete !== null) {
    deleteChild(returnFiber, childToDelete);
    childToDelete = childToDelete.sibling;
  }
  return null;
}

综合deleteChild、deleteRemainingChildren、reconcileSingleElement成一个整体来看。

  • 当children为一个单独的VDOM，此时FiberNode此时可能存在多个同级的FiberNode(通过sibling进行链接)，所以要对这些多出来的FiberNode进行删除
  • 当key对应完毕。直接使用deleteRemainingChildren标记删除剩余后面所有fiber.sibling及其子节点
  • 关于第二条的key对应。当key在中间时候，key前面的使用deleteChild当个删除。找到key之后，批量deleteChild删除。

所以，总的来讲，这里是Tree Diff没错，但是更多的同时ComponentDiff的替换行为，一旦ClassComponent&HostComponent这些做了修改，那么直接用新的替换它(这里它是FiberNode)。

这里再看看key对应完毕后创建新的fiber的函数useFiber。这个函数主要是创建一个workInProgress节点。当current.alternate有值，直接修改更新它，如果没值的话则创建一个，并将创建的fiber的alternate设为current。

多节点children

如果说单节点是其他两种Diff算法多一些。那么多节点children则是侧重了ElementDiff。同级多节点的更新，必然会伴随着节点的删除、移动、插入，ElementDiff算法在这里将会是主角。

它对应的reconcileChildrenArray函数。如果对ElementDiff实现没有了解的。可以参考之前的<>篇。当然，这是v15版本的分析。

对这个分析里面的ElementDiff分析做简述，就是新Index>旧Index，那么需要将旧的节点移动到新的Index。理解这个非常重要，因为思路和v15版本一致，这里不再描述这个过程。

反过来讲,如果旧Index>新Index，那么原节点可以考虑原地不动。

Tips: 关于这个大于小于，当ABCD转换成BACD也就是0123变成1023时候，只需要对A进行删除+创建+插入。ABCD对应的是旧index，而BACD则是新index。所以考虑到大于等于和小于等于这种符号的严谨性。这里需要说明一下，它的严谨说法是: 如果旧Index>新Index，那么原节点可以考虑原地不动,否则旧index ≤ 新 index, 则需要进行标记移动。

以下是源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
function reconcileChildrenArray(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChildren: Array<*>,
  expirationTime: ExpirationTime,
): Fiber | null {
  let resultingFirstChild: Fiber | null = null;
  let previousNewFiber: Fiber | null = null;

  let oldFiber = currentFirstChild;
  let lastPlacedIndex = 0;
  let newIdx = 0;
  let nextOldFiber = null;
  // 第一道循环
  for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
    if (oldFiber.index > newIdx) {
      // 旧index > 新index nextOldFiber不会变化 循环尾部有:oldFiber = nextOldFiber;
      // 设为null，fiberNode会走createFiberFromElement
      nextOldFiber = oldFiber;
      oldFiber = null;
    } else {
      // 否则指向oldFiber.sibling
      nextOldFiber = oldFiber.sibling;
    }
    const newFiber = updateSlot(
      returnFiber,
      oldFiber,
      newChildren[newIdx],
      expirationTime,
    );
    if (newFiber === null) {
        if (oldFiber === null) {
            oldFiber = nextOldFiber;
        }
        break;
    }
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    if (previousNewFiber === null) {
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
    oldFiber = nextOldFiber;
  }

  if (newIdx === newChildren.length) {
    deleteRemainingChildren(returnFiber, oldFiber);
    return resultingFirstChild;
  }

  if (oldFiber === null) {
    // 第二道循环
    for (; newIdx < newChildren.length; newIdx++) {
      const newFiber = createChild(
        returnFiber,
        newChildren[newIdx],
        expirationTime,
      );
      if (!newFiber) {
        continue;
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        // TODO: Move out of the loop. This only happens for the first run.
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
    return resultingFirstChild;
  }

  const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

  // Keep scanning and use the map to restore deleted items as moves.
  // 第三道循环
  for (; newIdx < newChildren.length; newIdx++) {
    const newFiber = updateFromMap(
      existingChildren,
      returnFiber,
      newIdx,
      newChildren[newIdx],
      expirationTime,
    );
    if (newFiber) {
      if (shouldTrackSideEffects) {
        if (newFiber.alternate !== null) {
          existingChildren.delete(
            newFiber.key === null ? newIdx : newFiber.key,
          );
        }
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
  }

  if (shouldTrackSideEffects) {
    existingChildren.forEach(child => deleteChild(returnFiber, child));
  }

  return resultingFirstChild;
}

这里首先要理解的是nextOldFiber。

这里nextOldFiber实际上就是一个缓存作用，它的意义是将oldFiber最后赋值为oldFiber || oldFiber.sibling。

假设我们变更前元素是ABCD，变更后是BADC。

如果你认为这个循环是按BADC顺序，就容易走入误区。

这是因为这个循环实质上是以newChildren(VDOM)为长度进行自增遍历(4)，oldFiber实质上确是从ABCD的顺序遍历，如果你理解是以newChildren(BADC)来开头(不管你认为相关值也好索引也好)，那么就容易陷入逻辑陷阱——**但实质上，要理解这一段，必须以ABCD的顺序来(nextOldFiber)**，如果你能理解这一块，就能理解它的目的了。

而newIdx除了不得大于newChildren.length, 实质上和newChildren和一毛钱关系没有。他就是一个自增变量而已。

大多数情况下，我们这里

1
2
3
4
5
6
if (oldFiber.index > newIdx) {
    nextOldFiber = oldFiber;
    oldFiber = null;
} else {
    nextOldFiber = oldFiber.sibling;
}

都不会走到第一个分支。接下来我们用案例佐证算法。

例子一

假设我们有一个组件Test

1
2
3
4
5
6
7
8
class Test extends React.Component{
  render () {
    const text = this.props.children;
    return text === 'Text' ? 
        ['A','B','C','D'].map(v => <div key={v}>{v}</div>) 
    	: ['B','A','D','C'].map(v => <div key={v}>{v}</div>)
  }
}

并且this.props.children从’Text’变成’Number’。此时它在第一个循环里面遇到updateSlot会直接返回null，然后循环被跳出。

接下来路径是使用mapRemainingChildren生成Map结构, 这里key为key，而value为对应fiberNode。这个Map数据，其实和newChildren数组类似。

然后进入第三道循环，这个循环里面，会遍历newChildren,然后挨个获取newChildrenItem,获取key然后从mapRemainingChildren找到对应的旧fiberNode。

  • 如果能找到对应key相同的。updateElement会走move逻辑，复用fiberNode
  • 如果找不到。updateElement走insert逻辑，使用newChildrenItem创建新的fiberNode

接下来，根据这个updateElement生成的fiberNode，查看其是否有alternate属性。如果是复用fiberNode，也就是Map里面能找到旧fiberNode的情况下，这种情况只需要做排序，此时找到了就要从原来Map里面删除它，然后使用placeChild执行排序。

最后，如果Map结构里面还有多余的Item，直接删除它，新的children里面没有他们，所以全部标记删除。

例子二
1
2
3
4
5
6
7
8
9
10
11
12
class Test extends React.Component{
  render () {
    const text = this.props.children;
    return text === 'Text' ? <div>
          <div>1</div>
          <span>4</span>
        </div> : <div>
          <span>4</span>
          <div>1</div>
        </div>
  }
}

要说它和例子又什么区别，那就是它没有key了。此时它会直接在第一道循环的完成div和span对应fiberNode的遍历(对HostComponent来说，updateSlot会返回updateElement执行结果而不是null)。这两道流程里面都是走的创建新的，替换旧的处理，完毕之后将创建出来的fiberNode使用sibling连接起来，因为其遍历到底了，所以以下分支会被执行。

1
2
3
4
if (newIdx === newChildren.length) {
  deleteRemainingChildren(returnFiber, oldFiber);
  return resultingFirstChild;
}

最终，workInProgress.child会被赋值为resultingFirstChild。

重要补充: placeChild

一旦我们通过updateSlot获得一个fiberNode。下一步可能就是一个重头戏了。

1
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);

这个函数内容如下，另外lastPlacedIndex的初始值是0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function placeChild(
  newFiber: Fiber,
  lastPlacedIndex: number,
  newIndex: number,
): number {
  newFiber.index = newIndex;
  if (!shouldTrackSideEffects) {
    // Noop.
    return lastPlacedIndex;
  }
  const current = newFiber.alternate;
  if (current !== null) { // 如果newFiber.alternate有值 那么判定是移动还是不管
    const oldIndex = current.index;
    if (oldIndex < lastPlacedIndex) {
      // This is a move.
      newFiber.effectTag = Placement;
      return lastPlacedIndex;
    } else {	// 原地不动
      // This item can stay in place.
      return oldIndex;
    }
  } else { // 否则这是一个插入动作
    // This is an insertion.
    newFiber.effectTag = Placement;
    return lastPlacedIndex;
  }
}

关于这个函数，有几点要明确。

  • 首先是alternate，fiberNode上的alternate实质上是newTree节点对oldTree或者叫做currentTree树的节点的链接。这里newFiber则是与前面提到的Tree相对应的workInProgress(newTree)树上的节点。
  • 所以这里oldIndex就真的是oldIndex, 但是lastPlacedIndex却并不能说是新Index。我们这里没有newIndex的概念，但是可以很自然的推测它肯定也有类似逻辑，这里需要推演出来。
  • 如果alternate不为空说明可以进行移动、保持、更新等处理，否则说明是一个新节点，要标记插入

它这里逻辑是怎样的, 还是假设ABCD(0123-旧)到BADC(1032-新)进行变化(例子一)。因为这里是对newChildren(reconcileChildrenArray中)进行遍历，所以这个遍历对比流程顺序是: B-A-D-C。

第一遍:

​ B: 此时oldIndex = 1, lastPlacedIndex = 0; 此时B不动，lastPlacedIndex赋值为1

第二遍

​ A:此时oldIndex = 0, lastPlacedIndex = 1; 此时A标记移动，lastPlacedIndex赋值为1

第三遍:

​ D:此时oldIndex = 3 , lastPlacedIndex = 1; 此时D不动，lastPlacedIndex赋值为3

第四遍:

​ C:此时oldIndex = 2 , lastPlacedIndex = 3; 此时C标记，lastPlacedIndex赋值为3

原理:

这里有必要将alternate对新旧fiberNode的链接深入理解。这里进行处理时候将第一个元素B作为了初始基准，基准值取其旧index: 1, 此后A因为原来位置比靠前(旧index < 基准值)，但是新顺序却靠后，所以按照从左往后的顺序，它必须移动，完毕后基准还是B，继续处理D，此时D.index大于基准值，在新的顺序里面也在B后面，所以它不动，改变基准值为D.index: 3。继续处理C, 它和A一样，原来位置靠前(旧index < 基准值)，但是却在D后面，所以需要标记移动。

但是这里仅仅是标记了操作办法，索引还没处理。它的索引，则是通过resultingFirstChild变量实现的。每次得到新的值，它会挂载上一个获取到的fiberNode的sibling属性上，这个sibling一路链下来，就是实质性的index。

小结

这里算法和v15有了很多变化。实现细节上已经几乎没有相同地方了。

针对key的tree对比这里还是有，思路一致，不过已经改用Map结构来保存了，然后移动计算上基于updateFromMap->updateElement的方式来实现了。

而索引，这里的调和算法上，实质已经没有这个东西了，它依托fiberNode的sibling就实现了。

一套遍历走下来，如果Map数据里面还有多余，就是补足了之前v15 Tree Diff过程中对Delete的标记，直接遍历Map进行删除标记即可。

其他情况，Fragment都是走的直接创建新的然后标记插入，最后标记移除旧的。

HostComponent

出了常见的ClassComponent，HostComponent在浏览器环境显然是更加基础的组件表示形式，实际上所有的ClassComponent，都是对HostComponent组件的引用和扩展。

v16将v15里面的ReactDomComponent称之为HostComponent，常见的div、span都会转换为HostComponent。

在beginWork里面可以看到，面对HostComponent。

1
2
3
case HostComponent: { 
    return updateHostComponent(current$$1, workInProgress, renderExpirationTime)
}

updateHostComponent函数里面包含了context、ref和expirationTime之类的处理。但是最核心的还是

1
2
3
4
5
6
7
reconcileChildren(
    current,
    workInProgress,
    nextChildren,
    renderExpirationTime,
);
return workInProgress.child;

所以事实上，我们这里又走了ClassComponent的调用栈。其中细节这里不再复述。

FunctionComponent

几乎等同HostComponent情况。核心调用都是一致的。

Diff算法小总结

实质上在beginWork里面对算法已经有了很明显的说明了。但是这里还是要单独抽出来讲一讲。

我们的ComponentDiff、TreeDiff和ElementDiff实际上这里仍然适用。

Component Diff

这个算法的意义在于，当ClassComponent没有变化时候，不更新，变化了，就整体替换。

placeSingleChild函数为所有的SingleChild做了替换标记。

  • 当判定不需要更新，且没有抛出错误的时候，那么这个SingleChild会将它自身的child全部递归做一个副本(副本之前保持fiberNode链接)，并返回child。
  • 否则，适用reconcileChildren处理后面逻辑

Tree Diff

这里实质是同层级的元素的key对比。核心逻辑在reconcileChildrenArray函数里面。

它是这样做的。如果这个ChildrenArray上Item有key props。那么newFiber = updateSlot(args) = null。然后跳出循环将旧的FiberNode全部放到Map结构里面，遍历新的children查找对应key的FiberNode。

没找到一个，就从Map里面删除一个，遍历完成后，还在Map里面的就全部标记删除。

Element Diff

这里主要是上面reconcileChildrenArray函数里面，第三道循环里面处理的。

如果key存在，那么复用之前FiberNode，否则根据新的children创建fiberNode。我们遍历的是newChildrenArray，遍历过程中得到的新的FiberNode会挨个被上一个FiberNode.sibling链接起来,这样index就能对应起来了。