React源码分析与实现(三)：实操DOM Diff
- 2019 年 10 月 10 日
- 筆記
原文链接：Nealyang PersonalBlog
由于源码中diff算法掺杂了太多别的功能模块，并且dom diff相对于之前的代码实现来说还是有些麻烦的，尤其是列表对比的算法，所以这里我们单独拿出来说他实现
前言
众所周知，React中最为人称赞的就是Virtual DOM和 diff 算法的完美结合，让我们可以不顾性能的“任性”更新界面，前面文章中我们有介绍道Virtual DOM，其实就是通过js来模拟dom的实现，然后通过对js obj的操作，最后渲染到页面中，但是，如果当我们修改了一丢丢东西，就要渲染整个页面的话，性能消耗还是非常大的，如何才能准确的修改该修改的地方就是我们diff算法的功能了。
其实所谓的diff算法大概就是当状态发生改变的时候，重新构造一个新的Virtual DOM，然后根据与老的Virtual DOM对比，生成patches补丁，打到对应的需要修改的地方。
这里引用司徒正美的介绍
最开始经典的深度优先遍历DFS算法，其复杂度为O(n^3)，存在高昂的diff成本，然后是cito.js的横空出世，它对今后所有虚拟DOM的算法都有重大影响。它采用两端同时进行比较的算法，将diff速度拉高到几个层次。紧随其后的是kivi.js，在cito.js的基出提出两项优化方案，使用key实现移动追踪及基于key的编辑长度距离算法应用（算法复杂度 为O(n^2)）。但这样的diff算法太过复杂了，于是后来者snabbdom将kivi.js进行简化，去掉编辑长度距离算法，调整两端比较算法。速度略有损失，但可读性大大提高。再之后，就是著名的vue2.0 把snabbdom整个库整合掉了。
与传统diff对比
传统的diff算法通过循环递归每一个节点，进行对比，这样的操作效率非常的低，复杂程度O(n^3),其中n标识树的节点总数。如果React仅仅是引入传统的diff算法的话，其实性能也是非常差的。然而FB通过大胆的策略，满足了大多数的性能最大化，将O(n^3)复杂度的问题成功的转换成了O(n),并且后面对于同级节点移动，牺牲一定的DOM操作，算法的复杂度也才打到O(max(M,N))。
img
实现思路
这里借用下网上的一张图，感觉画的非常赞~
img
大概解释下：
额。。。其实上面也已近解释了，当Virtual DOM发生变化的时，如上图的第二个和第三个 p 的sonx被删除了，这时候，我们就通过diff算法，计算出前后Virtual DOM的差异->补丁对象patches，然后根据这个patches对象中的信息来遍历之前的老Virtual DOM树，对其需要更新的地方进行更新，使其变成新VIrtual DOM。
diff 策略
- Web UI中节点跨级操作特别少，可以忽略不计
- 拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。（哪怕一样的而我也认为不一样 -> 大概率优化）
- 对于同一层级的一组子节点，他们可以通过唯一的key来区分，以方便后续的列表对比算法
基于如上，React分别对tree diff、Component diff 、element diff 进行了算法优化。
tree diff
基于策略一，React的diff非常简单明了：只会对同一层次的节点进行比较。这种非传统的按深度遍历搜索，这种通过大胆假设得到的改进方案，不仅符合实际场景的需要，而且大幅降低了算法实现复杂度，从O(n^3)提升至O(n)。
基于此，React官方并不推荐进行DOM节点的跨层级操作 ，倘若真的出现了，那就是非常消耗性能的remove和create的操作了。
我是真的不会画图
img
Component diff
由于React是基于组件开发的，所以组件的dom diff其实也非常简单，如果组件是同一类型，则进行tree diff比较。如果不是，则直接放入到patches中。即使是子组件结构类型都相同，只要父组件类型不同，都会被重新渲染。这也说明了为什么我们推荐使用shouldComponentUpdate来提高React性能。
大概的感觉是酱紫的
IMAGE
list diff
对于节点的比较，其实只有三种操作，插入、移动和删除。（这里最麻烦的是移动，后面会介绍实现）。当被diff节点处于同一层级时，通过三种节点操作新旧节点进行更新：插入，移动和删除，同时提供给用户设置key属性的方式调整diff更新中默认的排序方式，在没有key值的列表diff中，只能通过按顺序进行每个元素的对比，更新，插入与删除，在数据量较大的情况下，diff效率低下，如果能够基于设置key标识尽心diff，就能够快速识别新旧列表之间的变化内容，提升diff效率。
对于这三种理论知识可以参照知乎上不可思议的 react diff的介绍。
IMAGE
算法实现
前方高清多码预警
diff
这里引入代码处理我们先撇开list diff中的移动操作，先一步一步去实现
根据节点变更类型，我们定义如下几种变化
const ATTRS = 'ATTRS';//属性改变 const TEXT = 'TEXT';//文本改变 const REMOVE = 'REMOVE';//移除操作 const REPLACE = 'REPLACE';//替换操作 let Index = 0;
解释下index，为了方便演示diff，我们暂时没有想react源码中给每一个Element添加唯一标识
var ReactElement = function(type, key, ref, self, source, owner, props) { var element = { // This tag allow us to uniquely identify this as a React Element $$typeof: REACT_ELEMENT_TYPE,//重点在这里 // Built-in properties that belong on the element type: type, key: key, ref: ref, props: props, // Record the component responsible for creating this element. _owner: owner, }; return element; }; ... 'use strict'; // The Symbol used to tag the ReactElement type. If there is no native Symbol // nor polyfill, then a plain number is used for performance. var REACT_ELEMENT_TYPE = (typeof Symbol === 'function' && Symbol.for && Symbol.for('react.element')) || 0xeac7; module.exports = REACT_ELEMENT_TYPE;
我们遍历每一个VDom，以index为索引。注意这里我们使用全局变量index，因为遍历整个VDom，以index作为区分，所以必须用全局变量，当然，GitHub上有大神的实现方式为{index:0},哈~引用类型传递，换汤不换药~
开始遍历
export default function diff(oldTree, newTree) { let patches = {}; // 递归树， 比较后的结果放到补丁包中 walk(oldTree, newTree, Index, patches) return patches; }
function walk(oldNode, newNode, index, patches) { let currentPatch = []; if(!newNode){ currentPatch.push({ type:REMOVE, index }); }else if(isString(oldNode) && isString(newNode)){ if(oldNode !== newNode){// 判断是否为文本 currentPatch.push({ type:TEXT, text:newNode }); } }else if (oldNode.type === newNOde.type) { // 比较属性是否有更改 let attrs = diffAttr(oldNode.porps, newNode.props); if (Object.keys(attrs).length > 0) { currentPatch.push({ type: ATTRS, attrs }); } // 比较儿子们 diffChildren(oldNode.children,newNode.children,patches); }else{ // 说明节点被替换 currentPatch.push({ type: REPLACE, newNode }); } currentPatch.length ? patches[index] = currentPatch : null; } function diffChildren(oldChildren,newChildren,patches) { oldChildren.forEach((child,ids)=>{ // index 每次传递给walk时， index应该是递增的.所有的都基于同一个Index walk(child,newChildren[idx],++Index,patches); }) } function diffAttr(oldAttrs, newAttrs) { let patch = {}; // 判断老属性和新属性的关系 for (let key in oldAttrs) { if (oldAttrs[key] !== newAttrs[key]) { patch[key] = newAttrs[key]; //有可能是undefined => 新节点中删了该属性 } } // 新节点新增了很多属性 for (let key in newAttrs) { if (!oldAttrs.hasOwnProperty(key)) { patch[key] = newAttrs[key]; } } return patch; }
在diff过程中，我们需要去判断文本标签，需要在util中写一个工具函数
function isString(node) { return Object.prototype.toString.call(node)==='[object String]'; }
实现思路非常简单，手工流程图了解下
img
通过diff后，最终我们会拿到新旧VDom的patches补丁，补丁的内容大致如下：
patches = { 1:{ type:'REMOVE', index:1 }, 3:{ type:'TEXT', newText:'hello Nealyang~', }, 6:{ type:'REPLACE', newNode:newNode } }
大致是这么个感觉，两秒钟体会下~
这里应该会有点诧异的是1 3 6...是什么鬼？
因为之前我们说过，diff采用的依旧是深度优先遍历，及时你是改良后的升级产品，但是遍历流程依旧是：
img
patches
既然patches补丁已经拿到了，该如何使用呢，对，我们依旧是遍历！
Element 调用render后，我们已经可以拿到一个通过VDom（代码）解析后的真是Dom了，所以我们只需要将遍历真实DOM，然后在指定位置修改对应的补丁上指定位置的更改就行了。
代码如下：(自己实现的简易版)
let allPaches = {}; let index = 0; //默认哪个需要补丁 export default function patch(dom, patches) { allPaches = patches; walk(dom); } function walk(dom) { let currentPatche = allPaches[index]; let childNodes = dom.childNodes; childNodes.forEach(element => walk(element)); if (currentPatche > 0) { doPatch(dom, currentPatche); } } function doPatch(node, patches) { patches.forEach(patch => { switch (patch.type) { case 'ATTRS': setAttrs(patch.attrs)//别的文件方法 break; case 'TEXT': node.textContent = patch.text; break; case 'REPLACE': let newNode = patch.newNode instanceof Element ? render(patch.newNode) : document.createTextNode(patch.newNode); node.parentNode.replaceChild(newNode, node) break; case 'REMOVE': node.parentNode.removeChild(node); break; } }) }
关于setAttrs其实功能都加都明白，这里给个简单实例代码，大家YY下
function setAttrs(dom, props) { const ALL_KEYS = Object.keys(props); ALL_KEYS.forEach(k =>{ const v = props[k]; // className if(k === 'className'){ dom.setAttribute('class',v); return; } if(k == "style") { if(typeof v == "string") { dom.style.cssText = v } if(typeof v == "object") { for (let i in v) { dom.style[i] = v[i] } } return } if(k[0] == "o" && k[1] == "n") { const capture = (k.indexOf("Capture") != -1) dom.addEventListener(k.substring(2).toLowerCase(),v,capture) return } dom.setAttribute(k, v) }) }
如上，其实我们已经实现了DOM diff了，但是存在一个问题.
如下图，老集合中包含节点：A、B、C、D，更新后的新集合中包含节点：B、A、D、C，此时新老集合进行 diff 差异化对比，发现 B != A，则创建并插入 B 至新集合，删除老集合 A；以此类推，创建并插入 A、D 和 C，删除 B、C 和 D。
IMAGE
针对这一现象，React 提出优化策略：允许开发者对同一层级的同组子节点，添加唯一 key 进行区分，虽然只是小小的改动，性能上却发生了翻天覆地的变化！
具体介绍可以参照 https://zhuanlan.zhihu.com/p/20346379
这里我们放到代码实现上：
/** * Diff two list in O(N). * @param {Array} oldList - Original List * @param {Array} newList - List After certain insertions, removes, or moves * @return {Object} - {moves: <Array>} * - moves is a list of actions that telling how to remove and insert */ function diff (oldList, newList, key) { var oldMap = makeKeyIndexAndFree(oldList, key) var newMap = makeKeyIndexAndFree(newList, key) var newFree = newMap.free var oldKeyIndex = oldMap.keyIndex var newKeyIndex = newMap.keyIndex var moves = [] // a simulate list to manipulate var children = [] var i = 0 var item var itemKey var freeIndex = 0 // first pass to check item in old list: if it's removed or not // 遍历旧的集合 while (i < oldList.length) { item = oldList[i] itemKey = getItemKey(item, key)//itemKey a // 是否可以取到 if (itemKey) { // 判断新集合中是否有这个属性，如果没有则push null if (!newKeyIndex.hasOwnProperty(itemKey)) { children.push(null) } else { // 如果有 去除在新列表中的位置 var newItemIndex = newKeyIndex[itemKey] children.push(newList[newItemIndex]) } } else { var freeItem = newFree[freeIndex++] children.push(freeItem || null) } i++ } // children [{id:"a"},{id:"b"},{id:"c"},null,{id:"e"}] var simulateList = children.slice(0)//[{id:"a"},{id:"b"},{id:"c"},null,{id:"e"}] // remove items no longer exist i = 0 while (i < simulateList.length) { if (simulateList[i] === null) { remove(i) removeSimulate(i) } else { i++ } } // i is cursor pointing to a item in new list // j is cursor pointing to a item in simulateList var j = i = 0 while (i < newList.length) { item = newList[i] itemKey = getItemKey(item, key)//c var simulateItem = simulateList[j] //{id:"a"} var simulateItemKey = getItemKey(simulateItem, key)//a if (simulateItem) { if (itemKey === simulateItemKey) { j++ } else { // 新增项，直接插入 if (!oldKeyIndex.hasOwnProperty(itemKey)) { insert(i, item) } else { // if remove current simulateItem make item in right place // then just remove it var nextItemKey = getItemKey(simulateList[j + 1], key) if (nextItemKey === itemKey) { remove(i) removeSimulate(j) j++ // after removing, current j is right, just jump to next one } else { // else insert item insert(i, item) } } } } else { insert(i, item) } i++ } //if j is not remove to the end, remove all the rest item var k = simulateList.length - j while (j++ < simulateList.length) { k-- remove(k + i) } // 记录旧的列表中移除项 {index:3,type:0} function remove (index) { var move = {index: index, type: 0} moves.push(move) } function insert (index, item) { var move = {index: index, item: item, type: 1} moves.push(move) } // 删除simulateList中null function removeSimulate (index) { simulateList.splice(index, 1) } return { moves: moves, children: children } } /** * Convert list to key-item keyIndex object. * 将列表转换为 key-item 的键值对象 * [{id: "a"}, {id: "b"}, {id: "c"}, {id: "d"}, {id: "e"}] -> [a:0,b:1,c:2...] * @param {Array} list * @param {String|Function} key */ function makeKeyIndexAndFree (list, key) { var keyIndex = {} var free = [] for (var i = 0, len = list.length; i < len; i++) { var item = list[i] var itemKey = getItemKey(item, key) if (itemKey) { keyIndex[itemKey] = i } else { free.push(item) } } return { keyIndex: keyIndex, free: free } } // 获取置顶key的value function getItemKey (item, key) { if (!item || !key) return void 666 return typeof key === 'string' ? item[key] : key(item) } exports.makeKeyIndexAndFree = makeKeyIndexAndFree exports.diffList = diff
代码参照：list-diff 具体的注释都已经加上。 使用如下：
import {diffList as diff} from './lib/diffList'; var oldList = [{id: "a"}, {id: "b"}, {id: "c"}, {id: "d"}, {id: "e"}] var newList = [{id: "c"}, {id: "a"}, {id: "b"}, {id: "e"}, {id: "f"}] var moves = diff(oldList, newList, "id") // type 0 表示移除, type 1 表示插入 // moves: [ // {index: 3, type: 0}, // {index: 0, type: 1, item: {id: "c"}}, // {index: 3, type: 0}, // {index: 4, type: 1, item: {id: "f"}} // ] console.log(moves) moves.moves.forEach(function(move) { if (move.type === 0) { oldList.splice(move.index, 1) // type 0 is removing } else { oldList.splice(move.index, 0, move.item) // type 1 is inserting } }) // now `oldList` is equal to `newList` // [{id: "c"}, {id: "a"}, {id: "b"}, {id: "e"}, {id: "f"}] console.log(oldList)
img
这里我最困惑的地方时，实现diff都是index为索引，深度优先遍历，如果存在这种移动操作的话，那么之前我补丁patches里记录的index不就没有意义了么？？
在 后来在开源的simple-virtual-dom中找到了index作为索引和标识去实现diff的答案。
- 第一点：在createElement的时候，去记录每一元素children的count数量
function Element(tagName, props, children) { if (!(this instanceof Element)) { if (!_.isArray(children) && children != null) { children = _.slice(arguments, 2).filter(_.truthy) } return new Element(tagName, props, children) } if (_.isArray(props)) { children = props props = {} } this.tagName = tagName this.props = props || {} this.children = children || [] this.key = props ? props.key : void 666 var count = 0 _.each(this.children, function (child, i) { if (child instanceof Element) { count += child.count } else { children[i] = '' + child } count++ }) this.count = count }
- 第二点，在diff算法中，遇到移动的时候，我们需要及时更新我们全局变量index，核心代码
(leftNode && leftNode.count) ?<br /> currentNodeIndex + leftNode.count + 1 :<br /> currentNodeIndex + 1。完整代码如下：
function diffChildren(oldChildren, newChildren, index, patches, currentPatch) { var diffs = diffList(oldChildren, newChildren, 'key') newChildren = diffs.children if (diffs.moves.length) { var reorderPatch = { type: patch.REORDER, moves: diffs.moves } currentPatch.push(reorderPatch) } var leftNode = null var currentNodeIndex = index _.each(oldChildren, function (child, i) { var newChild = newChildren[i] currentNodeIndex = (leftNode && leftNode.count) ? currentNodeIndex + leftNode.count + 1 : currentNodeIndex + 1 dfsWalk(child, newChild, currentNodeIndex, patches) leftNode = child }) }
话说，这里困扰了我好久好久。。。。
img
回到开头
var REACT_ELEMENT_TYPE = (typeof Symbol === 'function' && Symbol.for && Symbol.for('react.element')) || 0xeac7;
也就说明了这段代码的必要性。
0.3中diff的实现
最后我们在看下0.3中diff的实现：
updateMultiChild: function(nextChildren, transaction) { if (!nextChildren && !this._renderedChildren) { return; } else if (nextChildren && !this._renderedChildren) { this._renderedChildren = {}; // lazily allocate backing store with nothing } else if (!nextChildren && this._renderedChildren) { nextChildren = {}; } var rootDomIdDot = this._rootNodeID + '.'; var markupBuffer = null; // Accumulate adjacent new children markup. var numPendingInsert = 0; // How many root nodes are waiting in markupBuffer var loopDomIndex = 0; // Index of loop through new children. var curChildrenDOMIndex = 0; // See (Comment 1) for (var name in nextChildren) { if (!nextChildren.hasOwnProperty(name)) {continue;} // 获取当前节点与要渲染的节点 var curChild = this._renderedChildren[name]; var nextChild = nextChildren[name]; // 是否两个节点都存在,且类型相同 if (shouldManageExisting(curChild, nextChild)) { // 如果有插入标示，之后又循环到了不需要插入的节点，则直接插入，并把插入标示制空 if (markupBuffer) { this.enqueueMarkupAt(markupBuffer, loopDomIndex - numPendingInsert); markupBuffer = null; } numPendingInsert = 0; // 如果找到当前要渲染的节点序号比最大序号小，则移动节点 /* * 在0.3中，没有根据key做diff，而是通过Object中的key作为索引 * 比如{a,b,c}替换成{c,b,c} * b._domIndex = 1挪到loopDomIndex = 1的位置，就是原地不动 a._domIndex = 0挪到loopDomIndex = 2的位置，也就是和c换位 */ if (curChild._domIndex < curChildrenDOMIndex) { // (Comment 2) this.enqueueMove(curChild._domIndex, loopDomIndex); } curChildrenDOMIndex = Math.max(curChild._domIndex, curChildrenDOMIndex); // 递归更新子节点Props,调用子节点dom-diff... !nextChild.props.isStatic && curChild.receiveProps(nextChild.props, transaction); curChild._domIndex = loopDomIndex; } else { // 当前存在，执行删除 if (curChild) { // !shouldUpdate && curChild => delete this.enqueueUnmountChildByName(name, curChild); curChildrenDOMIndex = Math.max(curChild._domIndex, curChildrenDOMIndex); } // 当前不存在，下个节点存在, 执行插入，渲染下个节点 if (nextChild) { // !shouldUpdate && nextChild => insert this._renderedChildren[name] = nextChild; // 渲染下个节点 var nextMarkup = nextChild.mountComponent(rootDomIdDot + name, transaction); markupBuffer = markupBuffer ? markupBuffer + nextMarkup : nextMarkup; numPendingInsert++; nextChild._domIndex = loopDomIndex; } } loopDomIndex = nextChild ? loopDomIndex + 1 : loopDomIndex; } // 执行插入操作，插入位置计算方式如下： // 要渲染的节点位置-要插入的节点个数：比如当前要渲染的节点index=3，当前节点只有一个，也就是index=1。 // 如<div>1</div>渲染成<div>1</div><div>2</div><div>3</div> // 那么从<div>2</div>开始就开始加入buffer，最终buffer内容为<div>2</div><div>3</div> // 那么要插入的位置为 3 - 1 = 2。我们以<div>1</div>为1，就是把buffer插入2的位置，也就是<div>1</div>后面 if (markupBuffer) { this.enqueueMarkupAt(markupBuffer, loopDomIndex - numPendingInsert); } // 循环老节点 for (var childName in this._renderedChildren) { if (!this._renderedChildren.hasOwnProperty(childName)) { continue; } var child = this._renderedChildren[childName]; // 当前节点存在，下个节点不存在，删除 if (child && !nextChildren[childName]) { this.enqueueUnmountChildByName(childName, child); } } // 一次提交所有操作 this.processChildDOMOperationsQueue(); }
完
