New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
Nealyang opened this Issue Sep 3, 2018 · 1 comment

Comments

Projects
None yet
2 participants
@Nealyang
Owner

Nealyang commented Sep 3, 2018

原文链接: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) ? currentNodeIndex + leftNode.count + 1 : 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();
  }
@llitfkitfk

This comment has been minimized.

Show comment
Hide comment

llitfkitfk commented Oct 15, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment