React源码学习-Fiber遍历

react在自己的v16版本中将底层的reconciliation过程进行了重大更改，之前v15中使用同步递归算法进行组件的diff，我们知道，浏览器需要一定的刷新帧率(大概16ms渲染一次，FPS为60)才能确保页面不会可见的卡顿，而react一旦同步遍历的组件过多，将会引起页面掉帧，应用就会显得卡顿。因此，react花了大概两年时间优化，提出了Fiber结构，以链表的形式实现了操作树的新算法，提供了包括非阻塞渲染，按优先级更新，预渲染等强大的新特性。

最近正在研究学习这个新的fiber结构，今天不深入讲(毕竟自己也是刚刚开始深入学习)，只单单聊一下fiber进行节点遍历的简单实现，这个抽象方法十分的精巧，浅显易懂，感觉可以用在很多地方。

抽象链表遍历

如何使用单链表遍历一个组件树？react内的fiber数据结构包含了三个特殊字段：

child 指向第一个子节点
sibling 指向第一个兄弟节点
return 指向父节点

如下图：

对于这样一个树形结构，每个节点都是一个node，构造函数简写如下：

class Node {
  constructor(instance) {
    this.instance = instance;
    this.child = null;
    this.sibling = null;
    this.return = null;
  }
}

要遍历这样一个树，同时对每个节点都进行一些操作，我们需要先想一下需要如何处理。首先，我们需要用while()循环这个结构，对于循环到的每一个node调用一个函数doWork()做操作；其次，操作的同时需要把这个node跟他的子节点进行联系；最后，我们依然(同v15)采用深度优先搜索(DFS)算法，在遍历完后退出while循环。

我们先用来实现一个link函数来链接父节点和子节点：

function link(parent, elements) {
  if (elements === null) elements = [];
  
  //从右侧开始reduce，将子节点的return链接到parent，sibling链接到右侧兄弟节点，最后一个节点的sibling是null
  parent.child = elements.reduceRight((previous, current) => {
    const node = new Node(current);
    node.return = parent;
    node.sibling = previous;
    return node;
  }, null);
  
  return parent.child;  // 返回第一个子节点
}

接下来实现doWork()函数，用来操作节点，同时调用link函数链接节点和子节点：

function doWork(node) {
  console.log(node.instance.name);   //随便做点什么
  const children = node.instance.render();   // 由render方法取到组件？节点的子节点
  return link(node, children);  //链接父子节点，同时返回第一个子节点
}

准备工作完成，接下来就重头戏，深度优先遍历：

function walk(o) {
  let root = o;
  let current = o;
  while(true) {
    let child = doWork(current);
    
    //如果存在子节点，将其设为active node，走下一次循环
    if (child) {
      current = child;
      continue;
    }
    
    //如果返回到了顶端，退出函数
    if (current === root) {
      return;
    }
    
    //没有子节点，也没有兄弟节点，向上走
    while(!current.sibling) {
      if (!current.return || current.return === root) {
        return;
      }
      
      //向上走，直到找兄弟节点
     	current = current.return;
    }
    
    //找到了兄弟节点，将其设为active node，走下一次循环
    current = current.sibling;
  }
}

不断遍历当前节点的第一个子节点，直到到达分支的末尾，然后遍历sibling，然后return回父节点。

如果我们用这种方法遍历上方的树形结构，函数调用顺序将会是：work(a1) => doWork(a1) => doWork(b1) => doWork(b2) => doWork(c1) => doWork(d1) => doWork(d2) => doWork(b3) => doWork(c2) => return。

一撇React源码

React把一次渲染分成了两个阶段：render和commit。render阶段，如果是第一次渲染，react为render返回的每一个react元素创建一个fiber节点，随后的更新中会重用和更新这些现有的fiber节点，生成一个部分节点标记了side effects的fiber节点树。v16的重点在于，这个render过程可以是异步执行的，所以某些生命周期方法可能被重复调用(不细展开)。而commit阶段则必须是同步的执行，react将变化一次性更新到页面中。

在render阶段中就用到了fiber树的深度优先遍历。我们来简单看一下react源码是如何做的。

首先，fiber从workLoop()函数进入：

function workLoop(isYieldy) {
  if (!isYieldy) {
    // Flush work without yielding
    while (nextUnitOfWork !== null) {
      nextUnitOfWork = performUnitOfWork(nextUnitOfWork);
    }
  } else {
    // Flush asynchronous work until there's a higher priority event
    while (nextUnitOfWork !== null && !shouldYield()) {
      nextUnitOfWork = performUnitOfWork(nextUnitOfWork);
    }
  }
}

nextUnitOfWork从workInProgress树中保存了对fiber节点的引用，可以认为是当前正在处理的节点？处理完当前fiber后，变量将包含对树中下一个fiber节点的引用或null。

这里有4个函数用于遍历树并启动或完成工作：

performUnitOfWork
beginWork
completeUnitOfWork
completeWork

这里有一个动画，注意观察算法的调用和分支的跳转，它首先完成child节点的工作，然后转移到parent身边。

先来看下performUnitOfWork和beginWork函数：

function performUnitOfWork(workInProgress: Fiber): Fiber {
  let next = beginWork(workInProgress);  // 启动工作
  if (next === null) {
    next = completeUnitOfWork(workInProgress);
  }
  return next;
}

function beginWork(workInProgress: Fiber): Fiber {
  //主要函数，这里根据fiber节点的tag来进行不同的操作，以后详细分析
  console.log(workInProgress.name);
  return workInProgress.child;   // 返回下一个子节点或者null
}

如果有下一个子节点，它将被赋值给workLoop函数中的nextUnitOfWork变量，继续往下遍历；如果没有子节点，则代表这个分支的遍历到达了末尾，因此就完成了当前节点，之后，就需要找到这个完成节点的兄弟节点开始下一个分支的遍历，最后再回溯到父节点。这些在completeUnitOfWork函数中完成：

function completeUnitOfWork(workInProgress: Fiber): Fiber {
  while(true) {
    const current = workInProgress.alternate;
    let siblingFiber = workInProgress.sibling;
    let returnFiber = workInProgress.return;
    
    nextUnitOfWork = completeWork(current, workInProgress);
    if (siblingFiber !== null) {
      //有兄弟节点，返回给perform work这个节点
      return siblingFiber;
    } else if (returnFiber !== null) {
      //有父节点，一层一层上去完成父节点
      workInProgress = returnFiber;
      continue;
    } else {
      // 到达了root
      return null;
    }
  }
}

function completeWork(current, workInProgress) {
  //主要函数，这里根据fiber节点的tag来进行不同的操作，以后详细分析
  console.log(workInProgress.name);
  return null;
}

当workInProgress没有子节点的时候，进入此函数，走completeWork完成当前节点的工作。然后寻找它是否有兄弟节点，如果找到，react退出completeUnitOfWork并返回这个兄弟节点，交给nextUnitOfWork去进行下一个分支的工作。这里，react只是完成了第一个子分支的工作，父节点的工作还没有完成，只有在完成所有子分支节点的工作后，才会向上去完成父节点的工作。

上面的4个函数，performUnitOfWork和completeUnitOfWork主要用于迭代工作，主要的活动则在beginWork和completeWork函数中进行(react源码为这两个方法各自分配了单个文件来写)。

这篇博客只是简单总结了一点点fiber构建的知识，源码的学习实在太过复杂太难以理解，只能一个点一个点的去突破和理解，正如乔布斯在斯坦福大学中的演讲所说：

Again, you can’t connect the dots looking forward; you can only connect them looking backwards. So you have to trust that the dots will somehow connect in your future.

点点碎片知识的堆积，都是我们日后豁然开朗的根源。