React22 - diff algorithm - Moment For Technology

1. Time complexity

The best algorithms are all o(n3), where n is the number of elements. It’s very complicated if every element diff. So React imposes three restrictions

1. Diff only sibling elements, not all elements in another tree

React destroys the div and its descendants and creates a new p

3. Use key as a prop to indicate which child elements are stable under different renders

Illustrate point 3

/ / before update
<div>
  <p >ka</p>
  <h3 >song</h3>
</div>

/ / updated
<div>
  <h3 >song</h3>
  <p>ka</p>
</div>In this case, diff React will delete p and create a new H3 insert and then delete H3 and create P in the passCopy the code

/ / before update
<div>
  <p key="ka">ka</p>
  <h3 key="song">song</h3>
</div>

/ / updated
<div>
  <h3 key="song">song</h3>
  <p key="ka">ka</p>
</div>
// In the case of a key, the p node finds the p node with the same key, so the node can reuse h3 or it can reuse h3
Copy the code

2. Diff of a single node

1. Diff is a fiber that generates workingProgress by comparing JSX and CurrentFiber objects

2. Is the DOM node reusable? 1. The type must be the same; 2. The key must be the same before reuse

3. What cannot be reused?

1. Key is different: If currentFiber has sibling nodes and JSX is a single node, it will go to the singleElement logic. So we need to look at all nodes at the same level as CurrentFiber, can not delete the old can be reused. Also, if a node can be reused we also need to delete the other sibling fibers of currentFiber. All for the following situation.

If both are different, create a new fiber

//current
<div></div>
<p></p>
//jsx
<p><p>
Copy the code

2. Different types: delete all this fiber and its sibling fiber of the current directly, because the keys of other sibling nodes cannot be reused because they are already the same when the type can be determined. The key difference before depends on whether the brothers have the same key.

3. Multi-node DIff

When do you perform multi-node diff? JSX is an array, whether currentFiber is an array or not

There are three scenarios

1. The node is updated

// Case 1 -- node properties change
/ / before< ul > < li key = "0" className = "before" > 0 < li > < li key = "1" > 1 < li > < / ul > / / after < ul > < li key = "0" className = "after" > 0 < li > < li Key = "1" > 1 < li > < / ul > / / situation 2 - after the node type/update / < ul > < div key = "0" > 0 < / div > < li key = "1" > 1 < li > < / ul >Copy the code

2. A node is added or reduced

// Case 1 -- new node
/ / before< ul > < li key = "0" > 0 < li > < li key = "1" > 1 < li > < / ul > / / after < ul > < li key = "0" > 0 < li > < li key = "1" > 1 < li > < li key = "2" > 2 < li > < / ul > <ul> <li key="1">1<li> </ul>Copy the code

3. The node position changes

/ / before< ul > < li key = "0" > 0 < li > < li key = "1" > 1 < li > < / ul > / / after < ul > < li key = "1" > 1 < li > < li key = "0" > 0 < li > < / ul >Copy the code

When we do array-related algorithms, we often use double Pointers to traverse both the head and the tail of an array to make it more efficient, but we don’t do that here.

Although the JSX object newChildren updated this time is in the form of an array, current Fiber is compared with each component in newChildren. The fiber nodes at the same level are single-linked lists formed by sibling pointer links, that is, dual-pointer traversal is not supported.

That is, newChildren[0] is compared with Fiber and newChildren[1] is compared with fiber.sibling.

So you can’t use two-pointer optimization.

The multi-node diff results in a linked list of fibers, but returns a fiber(the first fiber) as a child

For the above reasons, the overall logic of the Diff algorithm goes through two rounds of traversal:

First traversal: Process the updated node. Because the probability of updating is the greatest

Second traversal: Process the remaining nodes that are not part of the update.

First iteration

let i = 0To traverse thenewChildrenThat will benewChildren[i]witholdFiberCompare, judgeDOM nodeWhether it is reusable.
If it’s reusable,i++Continue the comparisonnewChildren[i]witholdFiber.sibling, can be reused to continue traversal.
If it is not reusable, there are two cases:

keyDifference causes unreuse, jump out of the whole traversal immediately,The first iteration is complete.(Because the key is different, the corresponding node position changes do not belong to the updated node, and wait for the second round of cycle processing)
keyThe sametypeDifferences lead to unreuse, which willoldFiberMarked asDELETION(This will remove the DOM during the Commit phase) and continue traversing

ifnewChildrenAfter traversing (i.ei === newChildren.length - 1) oroldFiberAfter traversing (i.eoldFiber.sibling === null), jump out of traversal,The first iteration is complete.

function reconcileChildrenArray(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    newChildren: Array<*>,
    lanes: Lanes,
  ) :Fiber | null {
    // This algorithm can't optimize by searching from both ends since we
    // don't have backpointers on fibers. I'm trying to see how far we can get
    // with that model. If it ends up not being worth the tradeoffs, we can
    // add it later.

    // Even with a two ended optimization, we'd want to optimize for the case
    // where there are few changes and brute force the comparison instead of
    // going for the Map. It'd like to explore hitting that path first in
    // forward-only mode and only go for the Map once we notice that we need
    // lots of look ahead. This doesn't handle reversal as well as two ended
    // search but that's unusual. Besides, for the two ended optimization to
    // work on Iterables, we'd need to copy the whole set.

    // In this first iteration, we'll just live with hitting the bad case
    // (adding everything to a Map) in for every insert/move.

    // If you change this code, also update reconcileChildrenIterator() which
    // uses the same algorithm.

    if (__DEV__) {
      // First, validate keys.
      let knownKeys = null;
      for (let i = 0; i < newChildren.length; i++) {
        constchild = newChildren[i]; knownKeys = warnOnInvalidKey(child, knownKeys, returnFiber); }}let resultingFirstChild: Fiber | null = null;/ /! Return to the fiber
    let previousNewFiber: Fiber | null = null;/ /! Creating a fiber chain requires a temporary fiber for the connection

    let oldFiber = currentFirstChild;/ /! Fiber traversal to current (old fiber)
    let lastPlacedIndex = 0;/ /! The position of the DOM node corresponding to the newly created Fiber node in the page is used to change the node position
    let newIdx = 0;/ /! The index of the traversed JSX array
    let nextOldFiber = null;/ /! The next fiber from oldFiber
    / /! The first loop deals with node updates
    for(; oldFiber ! = =null && newIdx < newChildren.length; newIdx++) {
      if (oldFiber.index > newIdx) {/ /! The index of fiber is marked as the position of the current fiber in the peer fiber
        nextOldFiber = oldFiber;
        oldFiber = null;
      } else {
        nextOldFiber = oldFiber.sibling;
      }
      const newFiber = updateSlot(/ /! This function can be used to check whether the key is the same or not. If the key is the same, null will be used to check whether the type is the same. If the type is different, create a new fiber If the type is the same, it can be returned by multiplexing fiber
        returnFiber,
        oldFiber,
        newChildren[newIdx],
        lanes,
      );
      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);/ /! Tag NewFiber with place
      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;
    }
    / /! The old and new are traversed simultaneously
    if (newIdx === newChildren.length) {
      // We've reached the end of the new children. We can delete the rest.
      deleteRemainingChildren(returnFiber, oldFiber);
      return resultingFirstChild;
    }
    / /! The old traversal completes the new traversal without traversing the rest of JSX's newChildren
    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);
        if (newFiber === null) {
          continue;
        }
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);/ /! Insert the new node directly into the DOM with place
        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;
    }
    / /! Key ->value: oldFiber) in order to find it in o(1) time, we use map(key: oldFiber. Key ->value: oldFiber) data structure
    // Add all children to a key map for quick lookups.
    const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
    / /! Walk through the remaining NewChldren
    // Keep scanning and use the map to restore deleted items as moves.
    for (; newIdx < newChildren.length; newIdx++) {
      const newFiber = updateFromMap(/ /! Find newChildren's key corresponding to oldFiber reuse/New Fiber return
        existingChildren,
        returnFiber,
        newIdx,
        newChildren[newIdx],
        lanes,
      );
      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,/ /! Remove oldFiber from map where key has been found
            );
          }
        }
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);/ /! The new fiber is marked as insert notice position (oldIndex < lastPlaceIndex) move position insert because the index position of the old fiber is smaller than the new page position definitely move position insert
        if (previousNewFiber === null) {
          resultingFirstChild = newFiber;
        } else{ previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; }}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));/ /! Delete the excess OldFiber because the new children has been traversed
    }

    return resultingFirstChild;
  }
Copy the code

Ps: most from card ode source explained react.iamkasong.com/diff/multi….

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

React22 – diff algorithm

1. Time complexity

2. Diff of a single node

3. Multi-node DIff

First iteration

React22 – diff algorithm

1. Time complexity

2. Diff of a single node

3. Multi-node DIff

First iteration

Related Posts

Non-negligible white-space

2021-05-01 Hot News

JavaScript implementation inheritance [Summary]💯