：从基础算法到 fiber 树构造的核心脉络)
教程前端【免费下载链接】react-illustration-series图解react源码, 用大量配图的方式, 致力于将react原理表述清楚.项目地址https://gitcode.com/gh_mirrors/re/react-illustration-series点击查看免费下载深度优先遍历(DFS)是react-reconciler包中fiber 树构造循环的核心算法贯穿ReactElement树的逐级生成、fiber树的构建以及context消费节点的查找三大场景。本篇以 react-illustration-series 系列中的 深度优先遍历 一文为主体结合 fiber 树构造(初次创建)、fiber 树构造(基础准备)、context 原理 与 栈操作 等章节系统讲解 DFS 的两种实现方式以及workLoopSync、performUnitOfWork、completeUnitOfWork、propagateContextChange等关键函数中 DFS 的实际落地帮助读者建立从算法到 React 源码运行机制的完整认知。DFS 概念对于树或图结构的搜索(或遍历)来讲主流算法分为深度优先(DFS)和广度优先(BFS)两大类。深度优先遍历(DFSDepth-First-Search)是一种用于遍历或搜索树或图的算法。来自 Wiki 的权威解释当节点v的所在边都已被探寻过搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点则选择其中一个作为源节点并重复以上过程整个进程反复进行直到所有节点都被访问为止。提炼成 React 语境下的直观理解就是一路向下探寻到底再逐层向上回溯优先访问节点的子节点直到叶子节点无路可走时再回溯到上一级继续访问下一个分支。DFS 的两种实现方式DFS 的主流实现方式有 2 种递归与利用栈存储遍历路径。react 源码中两类实现都有体现理解这两种写法是读懂后文源码的基础。方式一递归(简单粗暴)递归天然契合函数调用栈的入栈与出栈行为调用子节点时入栈子节点返回后自动出栈因此不需要手动维护任何辅助数据结构代码最简洁function Node() { this.name ; this.children []; } function dfs(node) { console.log(探寻阶段: , node.name); node.children.forEach((child) { dfs(child); }); console.log(回溯阶段: , node.name); }注意代码中console.log出现的位置在forEach之前打印的探寻阶段对应访问节点时向下深入的过程在forEach之后打印的回溯阶段对应所有子节点访问完毕、重新回到当前节点的过程。同一节点会经历先探寻、后回溯两个阶段这正是 DFS 在树形结构上留下的完整访问轨迹。方式二使用栈利用栈先进后出(LIFO)的特性可以模拟递归的行为。但因为要分辨探寻阶段和回溯阶段必须用一个属性记录节点是否已被访问过(若只需遍历无需区分阶段则不需要该属性)function Node() { this.name ; this.children []; // 因为要分辨探寻阶段和回溯阶段, 所以必须要一个属性来记录是否已经访问过该节点 // 如果不打印探寻和回溯, 就不需要此属性 this.visited false; } function dfs(node) { const stack []; stack.push(node); // 栈顶元素还存在, 就继续循环 while ((node stack[stack.length - 1])) { if (node.visited) { console.log(回溯阶段: , node.name); // 回溯完成, 弹出该元素 stack.pop(); } else { console.log(探寻阶段: , node.name); node.visited true; // 利用栈的先进后出的特性, 倒序将节点送入栈中 for (let i node.children.length - 1; i 0; i--) { stack.push(node.children[i]); } } } }关键点分析stack.push(node)将根节点压入栈中每次循环读取栈顶元素(stack[stack.length - 1])若未被访问则标记为已访问并倒序将子节点压栈——因为栈是后进先出倒序入栈可以保证正序出栈访问当栈顶元素已被访问过说明它的全部子节点都处理完毕此时进入回溯阶段将其弹出。react 内部对 DFS 的实现思路与此同源fiber节点上的child、sibling、return三根指针天然构成了一棵多叉树reconciler 正是沿着这三根指针完成向下探寻与向上回溯。React 当中的使用场景深度优先遍历在 react 中的使用非常典型最主要的使用场景在ReactElement和fiber树的构造过程其次是在使用context时需要深度优先地查找消费context的节点。三类场景都发生在react-reconciler包的reconciler 运作流程之中(可对照 reconciler 运作流程 与 两大工作循环)。ReactElement 树的构造ReactElement不能算是严格的树结构(它只是 JSX 编译产物的对象描述并没有显式的children指针数组之外的树形组织)但为了方便表述后文都称之为树。在react-reconciler包中ReactElement的构造过程实际上是嵌套在 fiber 树构造循环过程中的与 fiber 树的构造相互交替进行(fiber 树构建的完整解读见 fiber 树构造(初次创建)本节只介绍深度优先遍历的使用场景)。ReactElement树的构造实际上就是各级组件render之后的总和整个过程体现在reconciler工作循环之中。其核心源码位于ReactFiberWorkLoop.old.js的workLoopSync与performUnitOfWork、completeUnitOfWork。此处为了简明已将源码中与 dfs 无关的旁支逻辑去掉function workLoopSync() { // 1. 最外层循环, 保证每一个节点都能遍历, 不会遗漏 while (workInProgress ! null) { performUnitOfWork(workInProgress); } } function performUnitOfWork(unitOfWork: Fiber): void { const current unitOfWork.alternate; let next; // 2. beginWork是向下探寻阶段 next beginWork(current, unitOfWork, subtreeRenderLanes); if (next null) { // 3. completeUnitOfWork 是回溯阶段 completeUnitOfWork(unitOfWork); } else { workInProgress next; } } function completeUnitOfWork(unitOfWork: Fiber): void { let completedWork unitOfWork; do { const current completedWork.alternate; const returnFiber completedWork.return; let next; // 3.1 回溯并处理节点 next completeWork(current, completedWork, subtreeRenderLanes); if (next ! null) { // 判断在处理节点的过程中, 是否派生出新的节点 workInProgress next; return; } const siblingFiber completedWork.sibling; // 3.2 判断是否有旁支 if (siblingFiber ! null) { workInProgress siblingFiber; return; } // 3.3 没有旁支 继续回溯 completedWork returnFiber; workInProgress completedWork; } while (completedWork ! null); }这段代码本质上是采用循环显式指针移动的方式模拟递归进行 dfs。对照前文方式一(递归)与方式二(栈)可以逐一找到对应关系阶段workLoop 中的函数递归版本的对应行为向下探寻beginWork返回下级子节点workInProgress指针下移递归调用dfs(child)向上回溯completeWork处理完节点后检查sibling旁支子节点递归返回后的回溯处理旁支siblingFiber ! null时转向兄弟节点forEach遍历下一个兄弟无旁支继续回溯completedWork returnFiber递归逐层返回父级其中有两个贯穿全局的关键指针(可参考 fiber 树构造(基础准备) 中的全局变量与[双缓冲技术]相关小节)workInProgress指向当前正在构造的 fiber 节点是整个构造循环的游标current workInProgress.alternate指向当前页面正在使用的 fiber 节点(即fiber.alternate双缓冲的另一侧)。初次构造时页面还未渲染current null。workLoopSync的while (workInProgress ! null)最外层循环保证了整棵树所有节点都会被访问到不会遗漏——这就是 DFS 的完整遍历语义在循环实现上的体现。假设有以下组件结构class App extends React.Component { render() { return ( div classNameapp headerheader/header Content / footerfooter/footer /div ); } } class Content extends React.Component { render() { return ( React.Fragment p1/p p2/p p3/p /React.Fragment ); } } export default App;则可以绘制出遍历路径如下需要注意ReactElement树是在大循环中的beginWork阶段逐级生成的逐级中的每一级是指一个class或function类型的组件每调用一次render或执行一次function调用就会生成一批ReactElement节点ReactElement树的构造实际上就是各级组件render之后的总和。fiber 树的构造在ReactElement的构造过程中同时伴随着 fiber 树的构造。fiber 树同样也是在beginWork阶段生成的beginWork依据ReactElement对象调用reconcileChildren生成次级 fiber 子节点并设置return(父指针)与sibling(兄弟指针)最终构造出完整的 fiber 树形结构而在completeWork回溯阶段则负责为HostComponent、HostText类型的节点创建 DOM 实例、绑定事件并将带副作用的节点收集进父节点的副作用队列(细节见 fiber 树构造(初次创建) 中的beginWork与completeWork两节)。绘制出遍历路径如下对照 fiber 树构造(初次创建) 中的unitofwork0至unitofwork7.4一系列过程图解可以看到每一次performUnitOfWork调用都严格遵循探寻 → 无子节点则回溯的 DFS 节奏beginWork向下探寻依次经过HostRootFiber → fiber(App/) → fiber(div) → fiber(header)遇到无子节点的header后进入completeUnitOfWork向上回溯处理header、转向兄弟节点fiber(Content/)再次向下探寻Content的三个p子节点处理完毕后沿p → Content/ → div → App/ → HostRootFiber逐级回溯同时将副作用队列(增、删、改标记)逐级上移、最终挂载到根节点HostRootFiber.alternate.firstEffect。整个fiber 树构造循环正是通过这样的 DFS 遍历把每个节点经历 beginWork 与 completeWork 两个阶段这一规则贯彻到整棵树最终完成全部 fiber 节点的创建与副作用收集。查找 context 的消费节点当context改变之后需要找出依赖该context的所有子节点(详细分析见 context 原理 章节)这里同样也是一个 DFS。其具体源码位于ReactFiberNewContext.old.js的propagateContextChange函数中。将其主干逻辑剥离出来可以清晰地看出采用循环递归的方式(即显式游标 while 循环模拟递归)进行遍历export function propagateContextChange( workInProgress: Fiber, context: ReactContextmixed, changedBits: number, renderLanes: Lanes, ): void { let fiber workInProgress.child; while (fiber ! null) { let nextFiber; // Visit this fiber. const list fiber.dependencies; if (list ! null) { // 匹配context等逻辑, 和dfs无关, 此处可以暂时忽略 // ... } else { // 向下探寻 nextFiber fiber.child; } fiber nextFiber; } }这段代码展示了 DFS 在查找场景下的典型形态从workInProgress.child出发一路沿fiber.child向下探寻直到整棵子树遍历完毕(fiber null)。在真实源码中遇到带有dependencies的 fiber 节点时还会进一步匹配 context 与 changedBits把消费该 context 的节点标记进对应 lane从而在后续 render 中触发重新渲染——while循环框架保证了依赖当前 context 的所有后代节点都能被找到这正是 DFS 的不遗漏特性在 context 传播场景中的价值。此外propagateContextChange与 栈操作 一章中的valueStack栈机制形成配合context 提供者在beginWork阶段入栈(pushProvider)、在completeWork阶段出栈(popProvider)其本质正是因为 reconciler 的 DFS 遍历节奏天然与栈的入栈/出栈操作同步——向下探寻对应入栈向上回溯对应出栈。这也是为什么 react 选择 DFS 作为 fiber 构造核心遍历方式的重要原因之一。总结由于 react 内部使用了ReactElement和fiber两大树形结构所以有不少关于节点访问的逻辑。本篇主要介绍了 DFS 的概念和它在 react 源码中的使用情况概念层面DFS 是沿子节点一路向下探寻、到叶子后逐级回溯的树/图遍历算法与 BFS 相对实现层面递归实现简单直接栈实现则需要借助visited标记区分探寻与回溯阶段源码层面fiber树的 DFS 遍历涉及到的代码多、分布广涵盖了reconciler阶段的大部分工作——workLoopSync最外层循环保证不遗漏performUnitOfWork中的beginWork负责向下探寻并生成子节点completeUnitOfWork中的completeWork负责向上回溯、处理节点与收集副作用是reconciler阶段工作循环的核心流程同时context变更后的消费节点查找也复用同一套 DFS 思路。除了 DFS 之外源码中还有很多逻辑都是查找树中的节点(如向上查找父节点、通过return指针回溯等)。对树形结构的遍历在源码中的比例很高理解这些算法技巧(可继续阅读本系列 栈操作、链表操作、diff 算法 等算法章节)能够更好地理解 react 源码的整体运行机制。赞分享教程前端【免费下载链接】react-illustration-series图解react源码, 用大量配图的方式, 致力于将react原理表述清楚.项目地址https://gitcode.com/gh_mirrors/re/react-illustration-series点击查看免费下载相关推荐Sunshine 游戏串流实操免费低延迟4 步从安装到跑通Sunshine 游戏串流实操免费低延迟4 步从安装到跑通 Sunshine 是一个开源自托管游戏串流服务器作为 Moonlight 客户端的主机端把音视频后端APK Editor Studio开发者指南编译与定制化教程APK Editor Studio开发者指南编译与定制化教程 APK Editor Studio是一款功能强大且易于使用的APK编辑工具适用于PC和Mac平开发工具逆向工程桌面应用hello-algo 图遍历全解BFS 广度优先与 DFS 深度优先遍历的算法原理、代码实现与复杂度分析hello algo 图遍历全解BFS 广度优先与 DFS 深度优先遍历的算法原理、代码实现与复杂度分析 图的遍历Graph Traversal是图论算法教程文档示例工程教育创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
