React源码分析与实现(三):实操DOM Diff

原文链接: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 &amp;&amp; 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();
  }

本文分享自微信公众号 - 全栈前端精选(isNealyang)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券