Create fiber tree scheduling algorithm

In the previous article, we briefly mentioned that the creation of Fiber was a depth-first process. In the past, the most common way to do depth-first traversal is to use a tree structure to process the parent node first, and then perform recursive operations on each child node to achieve the purpose of depth traversal. This is the most common way. Let’s do a simple simulation

First, suppose we have the following virtual DOM structure:

let vdomTree = {
  id: 1.children: [{id: 2.children: [{id: 3.children: null },
        { id: 4.children: null}]}, {id: 5.children: [{id: 6.children: null}]}]}Copy the code

function beginWork(vdomNode) {
  // Do some processing on the vDOM node passed in
  // Create instance execution cycle diff, etc
  
  // Finally return the processed virtual DOM
  return vdomNode
}
Copy the code

We then pass the virtual DOM tree as an argument to a function for deep traversal

function deep(parentVdomTree) {
  console.log(id)
  // Do some processing on the current parent node itself
  let vdomAfterTreatment = beginWork(parentVdomTree)
  // Then get the children of the current node
  let children = vdomAfterTreatment.children
  if(! children)return
  children.forEach((child) = > {
    // Do the same for each of its children
    // Each child, grandchild, great-grandchild, and so on will do the same
    deep(child)
  })
}
deep(vdomTree)
Copy the code

The biggest drawback is that once we start recursing, the recursion of deep does not stop until all nodes in the tree have been traversed. In other words, the call stack of deep keeps going up and down until all nodes have been traversed. In this case, once there are thousands of nested nodes in our application, the process of deep may be very long, and it is very likely to cause page lag. This is also a problem that was not solved before react 16. So if we want to solve this problem, we have to design a way to pause and exit the current deep call stack at any time. This approach is the new scheduling algorithm in Act16. Let’s take a look at what the new scheduling algorithm looks like in React16. In a file called ReactFiberScheduler.js we can find a method called workLoop:

Click here

The React function bypaps some code, so let’s look at how the react function iterates through the workInProgress section. It wasn’t next. It was next’s father. In our example above, the fiber of h1 is passed in. 3. Then it enters a while loop which gets its return and sibling first. Return mentioned in the previous article that it represents the parent of the current node, and sibling represents the sibling of the current node. In our example, the parent node and brother node of H1 are Fiber of MyClass and div respectively. After we omit a bunch of logical code, we get to some judgments that, along with the outer while loop, are deep traversal. 4. First, check whether sibling(div fiber) exists at the current node. If so, directly return sibling node to performUnitOfWork as next. This next is then returned to the workLoop for the next loop. Fiber for div is returned. 5. Next, fiber of div enters workLoop and then enters performUnitOfWork. Then enter the beginWork, and it is found in the beginWork div that there are two child nodes, one H2 and one H3. Then loop these two nodes to create fiber corresponding to H2 and H3 respectively. After that, H2 is returned to next as firstChild, and next is not null this time. Therefore, it is directly returned to the workLoop, and then h2 fiber enters formUnitofWork and beginWork as the next round of workInProgress. 6. At this time, there is no child node under H2, so beginWork returns null, next is null, and completeUnitOfWork enters. At this time, the parameter in completeUnitOfWork is H2 fiber. 7. Similarly, find the sibling of h2’s fiber and the parent of H2’s fiber, in this case, the fiber div of H3’s fiber. Then check whether there is a sibling node and find that there is fiber of H3. Return the fiber of H3 as next. Then fiber of H3 will follow the same logic to re-enter performUnitOfWork and beginWork 8. BeginWork returns next of H3, and finds that there is no child under H3, which is null, so it enters completeUnitOfWork. 9. Also find the sibling node and parent node of H3. The sibling node of H3 is null and the parent node is fiber of div. ReturnFiber is not null, it is div, so let the current workInProgress become div fiber, continue the while loop. 10. Re-enter the function completeUnitOfWork, but now the workInProgress has become fiber for div. Again, find the siblings and parents of div, in this case span and MyClass, respectively. 11. The sibling node is returned as next, which is a span fiber. 12. The span fiber re-enters Perfo and beginWork, and beginWork returns next, but the span has no child node, which is null, so the span fiber enters completeUnitOfWork. 13. CompleteUnitOfWork obtains the sibling and parent nodes of span, null and MyClass respectively. Then we go down to the judgment, and we find that span has no sibling nodes, so we use the parent node, MyClass, as the workInProgress, continue the while. The parent and sibling nodes of MyClass are both null. The parent node of MyClass is RootFiber, and the parent node is RootFiber. Null), and finally the completeUnitOfWork function returns NULL as next. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * If the child of a node is null, the sibling of the node is traversed. If the sibling of the node is also null, the sibling of the parent node is traversed. React then gives it a chance to interrupt the rendering of Fiber and return the thread to the browser before dealing with the next fiber. The interrupted fiber will be recorded in the nextUnitOfWork global variable, so that the next time you come back and continue, you can easily find the last broken fiber.

React uses a similar algorithm in a number of places, and it works perfectly with fiber data structures. This is the main Fiber architecture in React.

A colleague of P.S. asked me before, if breadth traversal is used, it should also be possible to pause the traversal process at any time, so why react does not use breadth traversal instead of depth traversal? The main reason for this problem is that if we have too many DOM nodes, we have to maintain a very large array stack, and then every time we interrupt the traversal, we have to go back to the array to find the last node. However, if we use fiber data structure, fiber is a kind of object structure with its own context, so we can easily find the last interruption with depth traversal. This is why I think React uses depth traversal instead of breadth traversal.

Gayhub: github.com/y805939188/… Kneel down and beg for the stars

React time split