React源碼分析與實現(xiàn)(三)：實操DOM Diff
關(guān)注并將「趣談前端」設(shè)為星標(biāo)
每早08:30按時推送技術(shù)干貨/優(yōu)秀開源/技術(shù)思維
由于源碼中diff算法摻雜了太多別的功能模塊，并且dom diff相對于之前的代碼實現(xiàn)來說還是有些麻煩的，尤其是列表對比的算法，所以這里我們單獨拿出來說他實現(xiàn)
前言
眾所周知，React中最為人稱贊的就是Virtual DOM和 diff 算法的完美結(jié)合，讓我們可以不顧性能的“任性”更新界面，前面文章中我們有介紹道Virtual DOM，其實就是通過js來模擬dom的實現(xiàn)，然后通過對js obj的操作，最后渲染到頁面中，但是，如果當(dāng)我們修改了一丟丟東西，就要渲染整個頁面的話，性能消耗還是非常大的，如何才能準(zhǔn)確的修改該修改的地方就是我們diff算法的功能了。
其實所謂的diff算法大概就是當(dāng)狀態(tài)發(fā)生改變的時候，重新構(gòu)造一個新的Virtual DOM，然后根據(jù)與老的Virtual DOM對比，生成patches補丁，打到對應(yīng)的需要修改的地方。
這里引用司徒正美的介紹
最開始經(jīng)典的深度優(yōu)先遍歷DFS算法，其復(fù)雜度為O(n^3)，存在高昂的diff成本，然后是cito.js的橫空出世，它對今后所有虛擬DOM的算法都有重大影響。它采用兩端同時進(jìn)行比較的算法，將diff速度拉高到幾個層次。緊隨其后的是kivi.js，在cito.js的基出提出兩項優(yōu)化方案，使用key實現(xiàn)移動追蹤及基于key的編輯長度距離算法應(yīng)用（算法復(fù)雜度 為O(n^2)）。但這樣的diff算法太過復(fù)雜了，于是后來者snabbdom將kivi.js進(jìn)行簡化，去掉編輯長度距離算法，調(diào)整兩端比較算法。速度略有損失，但可讀性大大提高。再之后，就是著名的vue2.0 把snabbdom整個庫整合掉了。
與傳統(tǒng)diff對比
傳統(tǒng)的diff算法通過循環(huán)遞歸每一個節(jié)點，進(jìn)行對比，這樣的操作效率非常的低，復(fù)雜程度O(n^3),其中n標(biāo)識樹的節(jié)點總數(shù)。如果React僅僅是引入傳統(tǒng)的diff算法的話，其實性能也是非常差的。然而FB通過大膽的策略，滿足了大多數(shù)的性能最大化，將O(n^3)復(fù)雜度的問題成功的轉(zhuǎn)換成了O(n),并且后面對于同級節(jié)點移動，犧牲一定的DOM操作，算法的復(fù)雜度也才打到O(max(M,N))。
實現(xiàn)思路
這里借用下網(wǎng)上的一張圖，感覺畫的非常贊~
大概解釋下：
額。。。其實上面也已近解釋了，當(dāng)Virtual DOM發(fā)生變化的時，如上圖的第二個和第三個 p 的sonx被刪除了，這時候，我們就通過diff算法，計算出前后Virtual DOM的差異->補丁對象patches，然后根據(jù)這個patches對象中的信息來遍歷之前的老Virtual DOM樹，對其需要更新的地方進(jìn)行更新，使其變成新VIrtual DOM。
diff 策略
Web UI中節(jié)點跨級操作特別少，可以忽略不計
擁有相同類的兩個組件將會生成相似的樹形結(jié)構(gòu)，擁有不同類的兩個組件將會生成不同的樹形結(jié)構(gòu)。（哪怕一樣的而我也認(rèn)為不一樣 -> 大概率優(yōu)化）
對于同一層級的一組子節(jié)點，他們可以通過唯一的key來區(qū)分，以方便后續(xù)的列表對比算法
基于如上，React分別對tree diff、Component diff 、element diff 進(jìn)行了算法優(yōu)化。
tree diff
基于策略一，React的diff非常簡單明了：只會對同一層次的節(jié)點進(jìn)行比較。這種非傳統(tǒng)的按深度遍歷搜索，這種通過大膽假設(shè)得到的改進(jìn)方案，不僅符合實際場景的需要，而且大幅降低了算法實現(xiàn)復(fù)雜度，從O(n^3)提升至O(n)。
基于此，React官方并不推薦進(jìn)行DOM節(jié)點的跨層級操作 ，倘若真的出現(xiàn)了，那就是非常消耗性能的remove和create的操作了。
我是真的不會畫圖
Component diff
由于React是基于組件開發(fā)的，所以組件的dom diff其實也非常簡單，如果組件是同一類型，則進(jìn)行tree diff比較。如果不是，則直接放入到patches中。即使是子組件結(jié)構(gòu)類型都相同，只要父組件類型不同，都會被重新渲染。這也說明了為什么我們推薦使用shouldComponentUpdate來提高React性能。
大概的感覺是醬紫的
list diff
對于節(jié)點的比較，其實只有三種操作，插入、移動和刪除。（這里最麻煩的是移動，后面會介紹實現(xiàn)）。當(dāng)被diff節(jié)點處于同一層級時，通過三種節(jié)點操作新舊節(jié)點進(jìn)行更新：插入，移動和刪除，同時提供給用戶設(shè)置key屬性的方式調(diào)整diff更新中默認(rèn)的排序方式，在沒有key值的列表diff中，只能通過按順序進(jìn)行每個元素的對比，更新，插入與刪除，在數(shù)據(jù)量較大的情況下，diff效率低下，如果能夠基于設(shè)置key標(biāo)識盡心diff，就能夠快速識別新舊列表之間的變化內(nèi)容，提升diff效率。
對于這三種理論知識可以參照知乎上不可思議的 react diff的介紹。
算法實現(xiàn)
前方高清多碼預(yù)警
diff
這里引入代碼處理我們先撇開list diff中的移動操作，先一步一步去實現(xiàn)
根據(jù)節(jié)點變更類型，我們定義如下幾種變化
const ATTRS = 'ATTRS';//屬性改變
const TEXT = 'TEXT';//文本改變
const REMOVE = 'REMOVE';//移除操作
const REPLACE = 'REPLACE';//替換操作
let Index = 0;
解釋下index，為了方便演示diff，我們暫時沒有想react源碼中給每一個Element添加唯一標(biāo)識
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作為區(qū)分，所以必須用全局變量，當(dāng)然，GitHub上有大神的實現(xiàn)方式為{index:0},哈~引用類型傳遞，換湯不換藥~
開始遍歷
export default function diff(oldTree, newTree) {
let patches = {};
// 遞歸樹， 比較后的結(jié)果放到補丁包中
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{
// 說明節(jié)點被替換
currentPatch.push({
type: REPLACE,
newNode
});
}
currentPatch.length ? patches[index] = currentPatch : null;
}
function diffChildren(oldChildren,newChildren,patches) {
oldChildren.forEach((child,ids)=>{
// index 每次傳遞給walk時， index應(yīng)該是遞增的.所有的都基于同一個Index
walk(child,newChildren[idx],++Index,patches);
})
}
function diffAttr(oldAttrs, newAttrs) {
let patch = {};
// 判斷老屬性和新屬性的關(guān)系
for (let key in oldAttrs) {
if (oldAttrs[key] !== newAttrs[key]) {
patch[key] = newAttrs[key]; //有可能是undefined => 新節(jié)點中刪了該屬性
}
}
// 新節(jié)點新增了很多屬性
for (let key in newAttrs) {
if (!oldAttrs.hasOwnProperty(key)) {
patch[key] = newAttrs[key];
}
}
return patch;
}
在diff過程中，我們需要去判斷文本標(biāo)簽，需要在util中寫一個工具函數(shù)
function isString(node) {
return Object.prototype.toString.call(node)==='[object String]';
}
實現(xiàn)思路非常簡單，手工流程圖了解下
通過diff后，最終我們會拿到新舊VDom的patches補丁，補丁的內(nèi)容大致如下：
patches = {
1:{
type:'REMOVE',
index:1
},
3:{
type:'TEXT',
newText:'hello Nealyang~',
},
6:{
type:'REPLACE',
newNode:newNode
}
}
大致是這么個感覺，兩秒鐘體會下~
這里應(yīng)該會有點詫異的是1 3 6...是什么鬼？
因為之前我們說過，diff采用的依舊是深度優(yōu)先遍歷，及時你是改良后的升級產(chǎn)品，但是遍歷流程依舊是：
patches
既然patches補丁已經(jīng)拿到了，該如何使用呢，對，我們依舊是遍歷！
Element 調(diào)用render后，我們已經(jīng)可以拿到一個通過VDom（代碼）解析后的真是Dom了，所以我們只需要將遍歷真實DOM，然后在指定位置修改對應(yīng)的補丁上指定位置的更改就行了。
代碼如下：(自己實現(xiàn)的簡易版)
let allPaches = {};
let index = 0; //默認(rèn)哪個需要補丁
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;
}
})
}
關(guān)于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)
})
}
如上，其實我們已經(jīng)實現(xiàn)了DOM diff了，但是存在一個問題.
如下圖，老集合中包含節(jié)點：A、B、C、D，更新后的新集合中包含節(jié)點：B、A、D、C，此時新老集合進(jìn)行 diff 差異化對比，發(fā)現(xiàn) B != A，則創(chuàng)建并插入 B 至新集合，刪除老集合 A；以此類推，創(chuàng)建并插入 A、D 和 C，刪除 B、C 和 D。
針對這一現(xiàn)象，React 提出優(yōu)化策略：允許開發(fā)者對同一層級的同組子節(jié)點，添加唯一 key 進(jìn)行區(qū)分，雖然只是小小的改動，性能上卻發(fā)生了翻天覆地的變化！
具體介紹可以參照 https://zhuanlan.zhihu.com/p/20346379
這里我們放到代碼實現(xiàn)上：
/**
* 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.
* 將列表轉(zhuǎn)換為 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 具體的注釋都已經(jīng)加上。
使用如下：
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)
這里我最困惑的地方時，實現(xiàn)diff都是index為索引，深度優(yōu)先遍歷，如果存在這種移動操作的話，那么之前我補丁patches里記錄的index不就沒有意義了么？？
在 后來在開源的simple-virtual-dom中找到了index作為索引和標(biāo)識去實現(xiàn)diff的答案。
第一點：在createElement的時候，去記錄每一元素children的count數(shù)量
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算法中，遇到移動的時候，我們需要及時更新我們?nèi)肿兞縤ndex，核心代碼
(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
})
}
話說，這里困擾了我好久好久。。。。
回到開頭
var REACT_ELEMENT_TYPE =
(typeof Symbol === 'function' && Symbol.for && Symbol.for('react.element')) ||
0xeac7;
也就說明了這段代碼的必要性。
0.3中diff的實現(xiàn)
最后我們在看下0.3中diff的實現(xiàn)：
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;}
// 獲取當(dāng)前節(jié)點與要渲染的節(jié)點
var curChild = this._renderedChildren[name];
var nextChild = nextChildren[name];
// 是否兩個節(jié)點都存在,且類型相同
if (shouldManageExisting(curChild, nextChild)) {
// 如果有插入標(biāo)示，之后又循環(huán)到了不需要插入的節(jié)點，則直接插入，并把插入標(biāo)示制空
if (markupBuffer) {
this.enqueueMarkupAt(markupBuffer, loopDomIndex - numPendingInsert);
markupBuffer = null;
}
numPendingInsert = 0;
// 如果找到當(dāng)前要渲染的節(jié)點序號比最大序號小，則移動節(jié)點
/*
* 在0.3中，沒有根據(jù)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);
// 遞歸更新子節(jié)點Props,調(diào)用子節(jié)點dom-diff...
!nextChild.props.isStatic &&
curChild.receiveProps(nextChild.props, transaction);
curChild._domIndex = loopDomIndex;
} else {
// 當(dāng)前存在，執(zhí)行刪除
if (curChild) { // !shouldUpdate && curChild => delete
this.enqueueUnmountChildByName(name, curChild);
curChildrenDOMIndex =
Math.max(curChild._domIndex, curChildrenDOMIndex);
}
// 當(dāng)前不存在，下個節(jié)點存在, 執(zhí)行插入，渲染下個節(jié)點
if (nextChild) { // !shouldUpdate && nextChild => insert
this._renderedChildren[name] = nextChild;
// 渲染下個節(jié)點
var nextMarkup =
nextChild.mountComponent(rootDomIdDot + name, transaction);
markupBuffer = markupBuffer ? markupBuffer + nextMarkup : nextMarkup;
numPendingInsert++;
nextChild._domIndex = loopDomIndex;
}
}
loopDomIndex = nextChild ? loopDomIndex + 1 : loopDomIndex;
}
// 執(zhí)行插入操作，插入位置計算方式如下：
// 要渲染的節(jié)點位置-要插入的節(jié)點個數(shù)：比如當(dāng)前要渲染的節(jié)點index=3，當(dāng)前節(jié)點只有一個，也就是index=1。
// 如<div>1</div>渲染成<div>1</div><div>2</div><div>3</div>
// 那么從<div>2</div>開始就開始加入buffer，最終buffer內(nèi)容為<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);
}
// 循環(huán)老節(jié)點
for (var childName in this._renderedChildren) {
if (!this._renderedChildren.hasOwnProperty(childName)) { continue; }
var child = this._renderedChildren[childName];
// 當(dāng)前節(jié)點存在，下個節(jié)點不存在，刪除
if (child && !nextChildren[childName]) {
this.enqueueUnmountChildByName(childName, child);
}
}
// 一次提交所有操作
this.processChildDOMOperationsQueue();
}?? 看完三件事
如果你覺得這篇內(nèi)容對你挺有啟發(fā)，我想邀請你幫我三個小忙：
點個【在看】，或者分享轉(zhuǎn)發(fā)，讓更多的人也能看到這篇內(nèi)容
關(guān)注公眾號【趣談前端】，不定期分享 前端工程化 / 可視化 / 低代碼 等技術(shù)文章。
