右耳听风
0%

react18.2 Diff算法

发表于

beginWork

单节点diff - reconcileSingleElement

单节点diff的为什么做成一个循环:

  • 因为新的内容只有一个节点，不代表旧的内容只有一个节点，这里可以分为两种情况：
    • 新旧都只有一个节点，只执行一次循环的比较
    • 旧的有多个节点，新的只有一个节点，就会循环旧的节点，依次和这个新节点进行key的比较，如果key相等，再比较type类型，比如是否都是div类型
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 reconcileSingleElement(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    element: ReactElement,
    lanes: Lanes,
    debugInfo: ReactDebugInfo | null,
): Fiber {
    // 取出最新的react元素对象的key
    const key = element.key;
    let child = currentFirstChild; // 旧的节点

    // 检查老的fiber单链表中是否有可以复用的节点
    while (child !== null) {
      // 1.key相等的情况下
      if (child.key === key) {
        // 取出最新的节点type：比如组件的type或者DOM节点的type
        const elementType = element.type;
        // 2.组件type为Fragment
        if (elementType === REACT_FRAGMENT_TYPE) {
          // 新老都是Fragment
          if (child.tag === Fragment) {
            // 在相等的情况下，给剩下的旧节点打上删除标记
            deleteRemainingChildren(returnFiber, child.sibling);
            // 复用当前旧的节点，生成新的fiber节点
            const existing = useFiber(child, element.props.children);
            // 设置父级节点
            existing.return = returnFiber;
            return existing;
          }
        } else {
          // 3，组件type也相等的情况下
          if (
            child.elementType === elementType ||
            // Keep this check inline so it only runs on the false path:
            (__DEV__
              ? isCompatibleFamilyForHotReloading(child, element)
              : false) ||
            // Lazy types should reconcile their resolved type.
            // We need to do this after the Hot Reloading check above,
            // because hot reloading has different semantics than prod because
            // it doesn't resuspend. So we can't let the call below suspend.
            (typeof elementType === 'object' &&
              elementType !== null &&
              elementType.$$typeof === REACT_LAZY_TYPE &&
              resolveLazy(elementType) === child.type)
          ) {
            // 在相等的情况下，给剩下的旧节点打上删除标记
            deleteRemainingChildren(returnFiber, child.sibling);
            // 复用当前旧的节点，生成新的fiber节点（生成的existing的pendingProps就是新的了）
            const existing = useFiber(child, element.props);
            // 设置初始的ref
            coerceRef(returnFiber, child, existing, element);
            // 设置父级节点
            existing.return = returnFiber;
            return existing;
          }
        }
        // key相等但是type不等的情况下，给所有旧节点打上删除标记【比如组件由div变成span了】
        deleteRemainingChildren(returnFiber, child);
        break;
      } else {
         // 4，key不相等的情况下，给当前旧的节点打上删除标记
        deleteChild(returnFiber, child);
      }
      // 取出旧的节点的兄弟节点，继续与新的节点进行比较【旧节点可能存在多个】
      child = child.sibling;
    }

    // 1. 初次挂载 2. 没有找到可以服用的老节点
    if (element.type === REACT_FRAGMENT_TYPE) {
      const created = createFiberFromFragment(
        element.props.children,
        returnFiber.mode,
        lanes,
        element.key,
      );
      created.return = returnFiber;
      return created;
    } else {
      const created = createFiberFromElement(element, returnFiber.mode, lanes);
      coerceRef(returnFiber, currentFirstChild, created, element);
      created.return = returnFiber;
      return created;
    }
}

多节点diff - reconcileChildrenArray

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
function reconcileChildrenArray(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    newChildren: Array<any>,
    lanes: Lanes,
    debugInfo: ReactDebugInfo | null,
  ): Fiber | null {
    let resultingFirstChild: Fiber | null = null; // 存储新生成的child
    let previousNewFiber: Fiber | null = null;

    let oldFiber = currentFirstChild;
    let lastPlacedIndex = 0;
    let newIdx = 0;
    let nextOldFiber = null;
    // ! 1. 从左边往右遍历，比较新老节点，如果节点可以复用，继续往右，否则就停止
    for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
      if (oldFiber.index > newIdx) {
        nextOldFiber = oldFiber;
        oldFiber = null;
      } else {
        nextOldFiber = oldFiber.sibling;
      }
      const newFiber = updateSlot(
        returnFiber,
        oldFiber,
        newChildren[newIdx],
        lanes,
        debugInfo,
      );
      if (newFiber === null) {
        // TODO: This breaks on empty slots like null children. That's
        // unfortunate because it triggers the slow path all the time. We need
        // a better way to communicate whether this was a miss or null,
        // boolean, undefined, etc.
        if (oldFiber === null) {
          oldFiber = nextOldFiber;
        }
        break;
      }
      if (shouldTrackSideEffects) {
        if (oldFiber && newFiber.alternate === null) {
          // We matched the slot, but we didn't reuse the existing fiber, so we
          // need to delete the existing child.
          deleteChild(returnFiber, oldFiber);
        }
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        // TODO: Move out of the loop. This only happens for the first run.
        resultingFirstChild = newFiber;
      } else {
        // TODO: Defer siblings if we're not at the right index for this slot.
        // I.e. if we had null values before, then we want to defer this
        // for each null value. However, we also don't want to call updateSlot
        // with the previous one.
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
      oldFiber = nextOldFiber;
    }

    // !2.1 新节点没了，（老节点还有）。则删除剩余的老节点即可
    // 0 1 2 3 4
    // 0 1 2 3
    if (newIdx === newChildren.length) {
      // We've reached the end of the new children. We can delete the rest.
      deleteRemainingChildren(returnFiber, oldFiber);
      if (getIsHydrating()) {
        const numberOfForks = newIdx;
        pushTreeFork(returnFiber, numberOfForks);
      }
      return resultingFirstChild;
    }
    // ! 2.2 (新节点还有)，老节点没了
    // 0 1 2 3 4
    // 0 1 2 3 4 5
    if (oldFiber === null) {
      // If we don't have any more existing children we can choose a fast path
      // since the rest will all be insertions.
      for (; newIdx < newChildren.length; newIdx++) {
        const newFiber = createChild(
          returnFiber,
          newChildren[newIdx],
          lanes,
          debugInfo,
        );
        if (newFiber === null) {
          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;
      }
      if (getIsHydrating()) {
        const numberOfForks = newIdx;
        pushTreeFork(returnFiber, numberOfForks);
      }
      return resultingFirstChild;
    }


    // !2.3 新老节点都还有节点，但是因为老fiber是链表，不方便快速get与delete，
    // !   因此把老fiber链表中的节点放入Map中，后续操作这个Map的get与delete
    // 0 1|   4 5
    // 0 1| 7 8 2 3
    // Add all children to a key map for quick lookups.
    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],
        lanes,
        debugInfo,
      );
      if (newFiber !== null) {
        if (shouldTrackSideEffects) {
          if (newFiber.alternate !== null) {
            // The new fiber is a work in progress, but if there exists a
            // current, that means that we reused the fiber. We need to delete
            // it from the child list so that we don't add it to the deletion
            // list.
            existingChildren.delete(
              newFiber.key === null ? newIdx : newFiber.key,
            );
          }
        }
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
        if (previousNewFiber === null) {
          resultingFirstChild = newFiber;
        } else {
          previousNewFiber.sibling = newFiber;
        }
        previousNewFiber = newFiber;
      }
    }

     // !3. 如果是组件更新阶段，此时新节点已经遍历完了，能复用的老节点都用完了，
    // ! 则最后查找Map里是否还有元素，如果有，则证明是新节点里不能复用的，也就是要被删除的元素，此时删除这些元素就可以了
    if (shouldTrackSideEffects) {
      // Any existing children that weren't consumed above were deleted. We need
      // to add them to the deletion list.
      existingChildren.forEach(child => deleteChild(returnFiber, child));
    }

    if (getIsHydrating()) {
      const numberOfForks = newIdx;
      pushTreeFork(returnFiber, numberOfForks);
    }
    return resultingFirstChild;
}

工具函数

updateSlot

updateSlot 函数的主要作用是：调用 updateTextNode 或者 updateElement 函数，如果 Fiber 能够复用就复用，不能够复用就创建一个新的 Fiber。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function updateSlot(returnFiber, oldFiber, newChild) {
  const key = oldFiber !== null ? oldFiber.key : null;
  if ((typeof newChild === "string" && newChild !== "") || typeof newChild === "number") {
    if (key !== null) return null;
    return updateTextNode(returnFiber, oldFiber, "" + newChild);
  }

  if (newChild !== null && typeof newChild === "object") {
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE: {
        if (newChild.key === key) {
          return updateElement(returnFiber, oldFiber, newChild);
        }
      }
      // ...
      default:
        return null;
    }
  }
  return null;
}

placeChild

placeChild 函数主要作用是：判断当前的 newFiber 是否是复用的节点，如果是复用的节点，就返回这个节点的 index 作为 lastPlacedIndex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 每个 fiber 都有一个 index 属性，表示当前 fiber 在父节点中的位置
// 如果是个复用的 fiber，current 存在，且 current.index > lastPlacedIndex，否则表示这个节点需要新创建，也可能是移动（移动也是创建）
function placeChild(newFiber, lastPlacedIndex, newIdx) {
  newFiber.index = newIdx;
  if (!shouldTrackSideEffects) {
    return lastPlacedIndex;
  }
  const current = newFiber.alternate;
  if (current !== null) {
    const oldIndex = current.index;
    if (oldIndex < lastPlacedIndex) {
      newFiber.flags |= Placement;
      return lastPlacedIndex;
    } else {
      // 复用节点，返回复用节点的 index
      return oldIndex;
    }
  } else {
    newFiber.flags |= Placement;
    return lastPlacedIndex;
  }
}

updateFromMap

updateFromMap 函数的主要作用是：和 updateSlot 函数功能差不多，从 existingChildren 中找到相应的 Fiber，然后调用 updateTextNode 或者 updateElement 函数，如果 Fiber 能够复用就复用，不能够复用就创建一个新的 Fiber

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function updateFromMap(existingChildren, returnFiber, newIdx, newChild) {
  // 文本 Fiber
  if ((typeof newChild === "string" && newChild !== "") || typeof newChild === "number") {
    const matchedFiber = existingChildren.get(newIdx) || null;
    return updateTextNode(returnFiber, matchedFiber, `${newChild}`);
  }
  // div/span Fiber
  if (typeof newChild === "object" && newChild !== null) {
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE: {
        const matchedFiber = existingChildren.get(newChild.key === null ? newIdx : newChild.key) || null;
        return updateElement(returnFiber, matchedFiber, newChild);
      }
      // ...
    }
  }
  return null;
}

updateTextNode

updateTextNode 函数的主要作用是：如果 current 存在，就复用 Fiber，否则就创建一个新的 Fiber

1
2
3
4
5
6
7
8
9
10
11
function updateTextNode(returnFiber, current, textContent) {
  if (current === null || current.tag !== HostText) {
    const created = createFiberFromText(textContent);
    created.return = returnFiber;
    return created;
  } else {
    const existing = useFiber(current, textContent);
    existing.return = returnFiber;
    return existing;
  }
}

updateElement

updateElement 函数的主要作用是：如果 current 存在，且 current.type === element.type，就复用 Fiber，否则就创建一个新的 Fiber

1
2
3
4
5
6
7
8
9
10
11
12
13
function updateElement(returnFiber, current, element) {
  const elementType = element.type;
  if (current !== null) {
    if (current.type === elementType) {
      const existing = useFiber(current, element.props);
      existing.return = returnFiber;
      return existing;
    }
  }
  const created = createFiberFromElement(element);
  created.return = returnFiber;
  return created;
}

总结

  1. 主要功能是对不同 fiber.tag 进行不同的处理。HostRoot容器节点document.getElementById(‘root’)，HostComponent常规节点div/span，HostText文本节点
  2. updateHostComponent
  3. reconcileChildren 函数负责协调子节点，接收三个参数：current：构建完成的 fiber 树；workInProgress：构建中的 fiber 树；nextChildren：要处理的子节点。
    1. 标注子节点是否要移动，如果没有old子节点。直接标注 Placement（新增或者移动位置），如果有old子节点，如果oldIndex < lastPlacedIndex(上一次新增或者移动的点的index)，证明可以移动，否则就保持原位置
    2. 01234 -> 2134 移动的是1
    3. 2134 -> 01234 移动的是2
    4. 1 3 2 5 -> 0 1 2 3 4 移动的是3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function placeChild(
newFiber: Fiber,
lastPlacedIndex: number,
newIndex: number,
): number {
newFiber.index = newIndex;
const current = newFiber.alternate;
if (current !== null) {
    const oldIndex = current.index;
    if (oldIndex < lastPlacedIndex) {
    // This is a move.
    newFiber.flags |= Placement | PlacementDEV;
    return lastPlacedIndex;
    } else {
    // This item can stay in place.
    return oldIndex;
    }
} else {
    // This is an insertion.
    newFiber.flags |= Placement | PlacementDEV;
    return lastPlacedIndex;
}
}

completeWork-总结

  1. 没有老节点
    1. 创建真实的 DOM 节点
    2. 将当前子节点下子节点挂载到当前节点上
  2. 有老节点
    1. updateHostComponent，对比workInProgress.pendingProps 和 current.memoizedProps，如果不同，就markUpdate标记更新
  3. bubbleProperties - 收集当前节点下子节点的 flags 和 subtreeFlags

commitWork

commitWork 在处理单节点时落脚点也是在 HostComponent 中，主要分为三种处理方式：

  • DOM 节点是新增，也就是 Placement，协调是标记哪些节点要移动（包括新增的节点和复用需要移动的节点）下面代码分析了一下要插入到哪个节点前面
  • DOM 节点中的文本内容变成空，也就是 ContentReset, ContentReset会调用 resetTextContnt 将文本节点设置为空
  • DOM 节点是更新，也就是 Update，会调用 commitUpdate 更新 DOM 节点
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
if (flags & Placement) {
    try {
      commitPlacement(finishedWork);
    }
    finishedWork.flags &= ~Placement;
}

function commitPlacement(finishedWork: Fiber): void {
  if (!supportsMutation) {
    return;
  }

  const parentFiber = getHostParentFiber(finishedWork);

  switch (parentFiber.tag) {
    case HostSingleton: {
      if (supportsSingletons) {
        const parent: Instance = parentFiber.stateNode;
        const before = getHostSibling(finishedWork);
        // We only have the top Fiber that was inserted but we need to recurse down its
        // children to find all the terminal nodes.
        insertOrAppendPlacementNode(finishedWork, before, parent);
        break;
      }
      // Fall through
    }
    case HostComponent: {
      const parent: Instance = parentFiber.stateNode;
      if (parentFiber.flags & ContentReset) {

        console.log('%c [  ]-1832', 'font-size:13px; background:pink; color:#bf2c9f;', )
        // Reset the text content of the parent before doing any insertions
        resetTextContent(parent);
        // Clear ContentReset from the effect tag
        parentFiber.flags &= ~ContentReset;
      }

      const before = getHostSibling(finishedWork);
      // We only have the top Fiber that was inserted but we need to recurse down its
      // children to find all the terminal nodes.
      insertOrAppendPlacementNode(finishedWork, before, parent);
      break;
    }
    case HostRoot:
    case HostPortal: {
      const parent: Container = parentFiber.stateNode.containerInfo;
      const before = getHostSibling(finishedWork);
      insertOrAppendPlacementNodeIntoContainer(finishedWork, before, parent);
      break;
    }
    default:
      throw new Error(
        'Invalid host parent fiber. This error is likely caused by a bug ' +
          'in React. Please file an issue.',
      );
  }
}

function getHostSibling(fiber: Fiber): ?Instance {
  // We're going to search forward into the tree until we find a sibling host
  // node. Unfortunately, if multiple insertions are done in a row we have to
  // search past them. This leads to exponential search for the next sibling.
  // TODO: Find a more efficient way to do this.
  let node: Fiber = fiber;
  siblings: while (true) {
    // If we didn't find anything, let's try the next sibling.
    while (node.sibling === null) {
      if (node.return === null || isHostParent(node.return)) {
        // If we pop out of the root or hit the parent the fiber we are the
        // last sibling.
        return null;
      }
      node = node.return;
    }
    node.sibling.return = node.return;
    node = node.sibling; // 找到下一个兄弟节点
    while (
      node.tag !== HostComponent &&
      node.tag !== HostText &&
      (!supportsSingletons ? true : node.tag !== HostSingleton) &&
      node.tag !== DehydratedFragment
    ) {
      // If it is not host node and, we might have a host node inside it.
      // Try to search down until we find one.
      if (node.flags & Placement) {
        // If we don't have a child, try the siblings instead.
        continue siblings;
      }
      // If we don't have a child, try the siblings instead.
      // We also skip portals because they are not part of this host tree.
      if (node.child === null || node.tag === HostPortal) {
        continue siblings;
      } else {
        node.child.return = node;
        node = node.child;
      }
    }
    // Check if this host node is stable or about to be placed.
    // 判断节点是稳定的，即不需要移动或是新增的
    if (!(node.flags & Placement)) {
      // Found it!
      // 就找到了这个节点了
      return node.stateNode;
    }
  }
}