virtualdom diff算法实现分析

原创

用户2303251

修改于 2018-06-07 17:00:59

1.4K0

修改于 2018-06-07 17:00:59

文章被收录于专栏：田云专栏

这两个月接触下vue ,花了两天时间了解了下vue的virtualdom实现，记录下学习心得。

##virtual dom

用javascript对象表示dom树，然后用这个对象去构建一个真正的dom树，插入到文档中。
当状态变更的时候，新生成一个对象，然后比较两棵树的差距
根据变更进行dom操作

virtual的本质就是在js和dom之间增加了一个缓存

vue的virtualdom实现使用了snabbdom，来看下算法的具体实现。

算法的实现

首先需要构建一个JavaScript对象，用来描述dom,在 snabbdom中，为vnode

* @param sel    选择器
* @param data    绑定的数据
* @param children    子节点数组
* @param text    当前text节点内容
* @param elm    对真实dom element的引用

export interface VNode {
  sel: string | undefined;
  data: VNodeData | undefined;
  children: Array<VNode | string> | undefined;
  elm: Node | undefined;
  text: string | undefined;
  key: Key | undefined;
}

vnode为一个简单的数据封装接口，

比较两棵dom树的差距

比较两棵DOM树的差异是 Virtual DOM 算法最核心的部分，这也是所谓的 Virtual DOM 的 diff 算法。两个树的完全的 diff 算法是一个时间复杂度为 O(n^3) 的问题。但是在前端当中，你很少会跨越层级地移动DOM元素。所以 Virtual DOM 只会对同一个层级的元素进行对比：

687474703a2f2f6c69766f7261732e6769746875622e696f2f626c6f672f7669727475616c2d646f6d2f636f6d706172652d696e2d6c6576656c2e706e67

深度优先遍历，比较差异

UI状态变更时，产生新的vnode,跟旧的vnode进行对比，在实际的代码中，会对新旧两棵树进行一个深度优先的遍历

在深度优先遍历的时候，每遍历到一个节点就把该节点和新的的树进行对比，patchVnode是比较算法的核心函数，

if (isUndef(vnode.text)) {
     //当前节点不含有text时，说明含有children
      if (!isUndef(oldCh) && !isUndef(ch)) {
       
        if (oldCh !== ch) updateChildren(elm, oldCh, ch);
      } else if (!isUndef(ch)) {
        addVnodes(elm, undefined, ch, 0, ch.length - 1);
      } else if (!isUndef(oldCh)) {
        removeVnodes(elm, oldCh, 0, oldCh.length - 1);
      }
    } else if (oldVnode.text !== vnode.text) {
      //当前节点含有text时，直接修改text的值即可
      elm.childNodes[0].nodeValue = vnode.text;
    }

当前的节点vnode的text不为空时，说明是一个根节点，只需要更新text的值即可，
如果旧的vnode不含有子节点，新的vnode含有子节点，说明新的vnode新增了子节点，那么需要在dom中添加新增子节点，通过addVnodes函数处理
如果新的vnode不含有子节点，旧的含有子节点，说明旧的vnode删除了子节点，那么需要在dom中删除当前节点的子节点，通过removeVnodes函数处理
当前节点vnode的text为undefined时，说明节点还含有子节点，children为非空，需要比较继续深度遍历，比较children的节点差异，如果新旧两棵树都含有子节点，继续深度遍历比较同一层次节点，通过updateChildren函数处理这是diff算法的核心。

比如对于这样一个排序的列表：

原始列表顺序为

1    2    3    4    5    6    7    8    9    10

按照title排序后的列表顺序为

7    10    5    6    4    2    3     8     9    1

具体实现时，在vnode上层 snabbdom封装了一个h函数，用来将dom转换为javascript对象vnode，同时为没个node初始时生成一个key值，key值得存在使得我们不需要拿一个新的vnode中的节点去跟每一个同一层节点对比。

具体实现算法如下：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
        oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
      } else if (isUndef(oldEndVnode)) {
        oldEndVnode = oldCh[--oldEndIdx];
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        patchVnode(oldStartVnode, newStartVnode);
        oldStartVnode = oldCh[++oldStartIdx];
        newStartVnode = newCh[++newStartIdx];
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        patchVnode(oldEndVnode, newEndVnode);
        oldEndVnode = oldCh[--oldEndIdx];
        newEndVnode = newCh[--newEndIdx];
      } else if (sameVnode(oldStartVnode, newEndVnode)) {
        // Vnode moved right
        patchVnode(oldStartVnode, newEndVnode);
        parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
        oldStartVnode = oldCh[++oldStartIdx];
        newEndVnode = newCh[--newEndIdx];
      } else if (sameVnode(oldEndVnode, newStartVnode)) {
        // Vnode moved left
        patchVnode(oldEndVnode, newStartVnode);
        parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
        oldEndVnode = oldCh[--oldEndIdx];
        newStartVnode = newCh[++newStartIdx];
      } else {
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
        idxInOld = oldKeyToIdx[newStartVnode.key];
        if (isUndef(idxInOld)) {
          // New element
          parentElm.insertBefore(createElm(newStartVnode), oldStartVnode.elm);
          newStartVnode = newCh[++newStartIdx];
        } else {
          elmToMove = oldCh[idxInOld];
          patchVnode(elmToMove, newStartVnode);
          oldCh[idxInOld] = undefined;
          parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm);
          newStartVnode = newCh[++newStartIdx];
        }
      }
    }

旧的vnode
         start                                                                     end
old      1         2        3     4     5       6      7      8     9    10

新的vnode
         start                                                                 end
new    7        10     5     6    4       2      3      8    9    1

算法每次循环  记录四个节点，旧vnode 的start和end节点 以及 新vnode 的 start 和end节点 ，然后进行对比：

比较的过程为每次四个节点互相比较相似度，在snabbdom中仅仅比较vnode的即选择器和key关键字，关键字为h函数初始化vnode时候生成，如果满足相似，则进行patchnode说明在新的vnodes中复用了旧的vnodes中的节点，只是移位或者其他插入修改操作，如果没有相似，则从旧的vnode中查看是否有相同的key的vnode，如果存在，则patchnode

sameVnode(oldStartVnode, newStartVnode) 当oldStartVnode和newStartVnode相似时，说明初始节点相似，进行patchnode
sameVnode(oldStartVnode, newEndVnode)当oldStartVnode和newEndVnode相似时，说明原有节点只是移动了位置，在新的dom树中进行了右移，更新dom,parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling); 此操作为dom原生操作进行移动，相当于delete和creat操作的优化。
sameVnode(oldEndVnode, newStartVnode）当oldEndVnode和newStartVnode相似时，说明现有dom节点只是在原来的endvnode节点上进行了移动操作，vnode进行了左移，更新dom,parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
若都没有命中，则从oldvnode中，查找跟newStartVnode.key相同的key的 vnode是否存在，如果存在则进行插入操作，如果不存在则创建新的dom节点插入到dom中。

如果循环结束：

diff中 oldvnode先循环结束，说明新的vnode中剩余的都是新创建的节点，进行addVnodes操作
diff中newvnode先循环结束，说明旧的vnode中剩余的都是等待删除的节点，进行removeVnodes操作。

Project virtualdom

来看看另外一个热门的virtualdom实现方案。

@项目地址 https://github.com/Matt-Esch/virtual-dom

步骤一：同样是用h函数，构建一个javascript对象，模拟dom树，我们以上面的例子排序为例

//原始的列表为10个数据对象
var originalData = [{ rank: 1, title: 'The Shawshank Redemption', desc: 'Two imprisoned men bond over a number of years, finding solace and eventual redemption through acts of common decency.', elmHeight: 0 }, { rank: 2, title: 'The Godfather', desc: 'The aging patriarch of an organized crime dynasty transfers control of his clandestine empire to his reluctant son.', elmHeight: 0 }, { rank: 3, title: 'The Godfather: Part II', desc: 'The early life and career of Vito Corleone in 1920s New York is portrayed while his son, Michael, expands and tightens his grip on his crime syndicate stretching from Lake Tahoe, Nevada to pre-revolution 1958 Cuba.', elmHeight: 0 }, { rank: 4, title: 'The Dark Knight', desc: 'When the menace known as the Joker wreaks havoc and chaos on the people of Gotham, the caped crusader must come to terms with one of the greatest psychological tests of his ability to fight injustice.', elmHeight: 0 }, { rank: 5, title: 'Pulp Fiction', desc: 'The lives of two mob hit men, a boxer, a gangster\'s wife, and a pair of diner bandits intertwine in four tales of violence and redemption.', elmHeight: 0 }, { rank: 6, title: 'Schindler\'s List', desc: 'In Poland during World War II, Oskar Schindler gradually becomes concerned for his Jewish workforce after witnessing their persecution by the Nazis.', elmHeight: 0 }, { rank: 7, title: '12 Angry Men', desc: 'A dissenting juror in a murder trial slowly manages to convince the others that the case is not as obviously clear as it seemed in court.', elmHeight: 0 }, { rank: 8, title: 'The Good, the Bad and the Ugly', desc: 'A bounty hunting scam joins two men in an uneasy alliance against a third in a race to find a fortune in gold buried in a remote cemetery.', elmHeight: 0 }, { rank: 9, title: 'The Lord of the Rings: The Return of the King', desc: 'Gandalf and Aragorn lead the World of Men against Sauron\'s army to draw his gaze from Frodo and Sam as they approach Mount Doom with the One Ring.', elmHeight: 0 }, { rank: 10, title: 'Fight Club', desc: 'An insomniac office worker looking for a way to change his life crosses paths with a devil-may-care soap maker and they form an underground fight club that evolves into something much, much more...', elmHeight: 0 }];
我们初始展示  1 、3、5这三个节点。
var data = [originalData[0], originalData[2], originalData[4]];

／／函数view返回vnode----- 初始data的virtual-dom实现的javascript对象
function view(data) {
  return h('div', [ h('div.list', { style: { height: totalHeight + 'px' } }, data.map(movieView))]);
}

VirtualNode

@tagName, //标签名称
@properties, ／／属性
@children, ／／ children
@key, // key
@namespace //命名空间
@count  //遍历的number

render方法会根据tagName构建一个真正的DOM节点，然后设置这个节点的属性，最后递归地把自己的子节点也构建起来。所以只需要：

  var container = document.getElementById('container');
  tree = render();             // We need an initial tree
  rootNode = createElement(tree);     // Create an initial root DOM node ...
  document.getElementById('container').appendChild(rootNode);

就可以渲染出一个页面。

我们在3秒后，变更初始的数据

setTimeout(function () {
      data = [originalData[0],originalData[1]];
      var newTree = render();
      var patches = diff(tree, newTree);
      rootNode = patch(rootNode, patches);
      tree = newTree;
}, 3000);

步骤2 同样是比较两颗树的差异，也就是diff算法

深度优先遍历，比较差异

UI状态变更时，产生新的vnode,跟旧的vnode进行对比，在实际的代码中，会对新旧两棵树进行一个深度优先的遍历

在深度优先遍历的时候，每遍历到一个节点就把该节点和新的的树进行对比。如果有差异的话就记录到一个对象里面。

／／diff 函数，比较新旧两颗vnode差异
function diff(a, b) {
    var patch = { a: a }
    walk(a, b, patch, 0)
    return patch
}
／／  walk函数  对两颗树进行深度优先遍历
function walk(a, b, patch, index) {
   // 对比oldNode和newNode的不同，记录下来
  patches[index] = [...]

  diffChildren(oldNode.children, newNode.children, index, patches)
}
／／ 遍历子节点
function diffChildren(a, b, patch, apply, index) {
   
}

列表对比算法

当出现差异时，我们把差异都存储在数组patch中，

patches[0] = [{difference}, {difference}, ...] // 用数组存储新旧节点的不同

对于dom的操作可能存在的情况有以下几种：

替换掉原来的节点，例如把上面的div换成了section
移动、删除、新增子节点，例如上面div的子节点，把p和ul顺序互换
修改了节点的属性
对于文本节点，文本内容可能会改变。

在virtualdom中定义的差异类型有以下几种：

VirtualPatch.NONE = 0
VirtualPatch.VTEXT = 1
VirtualPatch.VNODE = 2
VirtualPatch.WIDGET = 3
VirtualPatch.PROPS = 4
VirtualPatch.ORDER = 5
VirtualPatch.INSERT = 6
VirtualPatch.REMOVE = 7
VirtualPatch.THUNK = 8

我们以之前的例子来看下算法实现，初始数据为 1， 3 ， 5 三个

1    3    5

三秒之后我们变更为

1    2

比较 a,b两个节点。分别含有三个子节点和两个子节点

从walk函数看起

function walk(a, b, patch, index) {
    if (a === b) {
        return
    }

    var apply = patch[index]
    var applyClear = false

    if (isThunk(a) || isThunk(b)) {
        thunks(a, b, patch, index)
    } else if (b == null) {

        // If a is a widget we will add a remove patch for it
        // Otherwise any child widgets/hooks must be destroyed.
        // This prevents adding two remove patches for a widget.
        if (!isWidget(a)) {
            clearState(a, patch, index)
            apply = patch[index]
        }
      ／／如果新的vnode不存在 那么添加VPatch.REMOVE操作 
        apply = appendPatch(apply, new VPatch(VPatch.REMOVE, a, b))
    } else if (isVNode(b)) {
        if (isVNode(a)) {
            ／／ 如果a  b  节点同时存在 
            if (a.tagName === b.tagName &&
                a.namespace === b.namespace &&
                a.key === b.key) {
                var propsPatch = diffProps(a.properties, b.properties)
                if (propsPatch) {
                    apply = appendPatch(apply,
                        new VPatch(VPatch.PROPS, a, propsPatch))
                }
                 ／／ 判断相似性 然后比较children节点
                apply = diffChildren(a, b, patch, apply, index)
            } else {
               // 如果a  b同时存在却不相似 说明是一个新的节点 那么要添加一个新的vnode
                apply = appendPatch(apply, new VPatch(VPatch.VNODE, a, b))
                applyClear = true
            }
        } else {
           // 如果新的vnode存在  而不存在旧的树上 那么要添加一个新的vnode
            apply = appendPatch(apply, new VPatch(VPatch.VNODE, a, b))
            applyClear = true
        }
    } else if (isVText(b)) {
      ／／ 处理是text节点时候的状态
        if (!isVText(a)) {
            apply = appendPatch(apply, new VPatch(VPatch.VTEXT, a, b))
            applyClear = true
        } else if (a.text !== b.text) {
            apply = appendPatch(apply, new VPatch(VPatch.VTEXT, a, b))
        }
    } else if (isWidget(b)) {
        if (!isWidget(a)) {
            applyClear = true
        }

        apply = appendPatch(apply, new VPatch(VPatch.WIDGET, a, b))
    }

    if (apply) {
        patch[index] = apply
    }

    if (applyClear) {
        clearState(a, patch, index)
    }
}

比较children节点

function diffChildren(a, b, patch, apply, index) {
    var aChildren = a.children
    var orderedSet = reorder(aChildren, b.children)
    var bChildren = orderedSet.children

    var aLen = aChildren.length
    var bLen = bChildren.length
    var len = aLen > bLen ? aLen : bLen

    for (var i = 0; i < len; i++) {
        var leftNode = aChildren[i]
        var rightNode = bChildren[i]
        index += 1

        if (!leftNode) {
            if (rightNode) {
                // Excess nodes in b need to be added
                apply = appendPatch(apply,
                    new VPatch(VPatch.INSERT, null, rightNode))
            }
        } else {
            walk(leftNode, rightNode, patch, index)
        }

        if (isVNode(leftNode) && leftNode.count) {
            index += leftNode.count
        }
    }

    if (orderedSet.moves) {
        // Reorder nodes last
        apply = appendPatch(apply, new VPatch(
            VPatch.ORDER,
            a,
            orderedSet.moves
        ))
    }

    return apply
}

比较两颗树同层级的差异时，会对两个数组进行diff排序，主要是靠reorder函数处理

// List diff, naive left to right reordering
function reorder(aChildren, bChildren) {
    // O(M) time, O(M) memory
    // 首先对原先数组进行关键字映射，比如bChildren为【1，2】
    var bChildIndex = keyIndex(bChildren)
   ／／ 映射后 bChildIndex为 key为初始的关键字 1，2  顺序为0 ，1 
     free:[] 
    keys: {
      1: 0, 
      2: 1
    }
    var bKeys = bChildIndex.keys
    var bFree = bChildIndex.free

    if (bFree.length === bChildren.length) {
        return {
            children: bChildren,
            moves: null
        }
    }

    // O(N) time, O(N) memory
  ／／  aChildren为【1，3，5】 ，
    var aChildIndex = keyIndex(aChildren)
    ／／  映射后为
       free : []
       keys : {
          1: 0, 
          3: 1, 
          5: 2
        }
    var aKeys = aChildIndex.keys
    var aFree = aChildIndex.free

    if (aFree.length === aChildren.length) {
        return {
            children: bChildren,
            moves: null
        }
    }

    // O(MAX(N, M)) memory
    var newChildren = []

    var freeIndex = 0
    var freeCount = bFree.length
    var deletedItems = 0

    // Iterate through a and match a node in b
    // O(N) time,
    ／／ 遍历a子节点 与b的节点对比 
    for (var i = 0 ; i < aChildren.length; i++) {
        var aItem = aChildren[i]
        var itemIndex

        if (aItem.key) {
            if (bKeys.hasOwnProperty(aItem.key)) {
                // Match up the old keys
                ／／ 如果a  b中同时存在的节点 添加到新数组 newChildre
                itemIndex = bKeys[aItem.key]
                newChildren.push(bChildren[itemIndex])

            } else {
                // Remove old keyed items
                ／／ 否则添加null 
                itemIndex = i - deletedItems++
                newChildren.push(null)
            }
        } else {
            // Match the item in a with the next free item in b
            // 如果不存在key 在free数组中 如果ab都有
            if (freeIndex < freeCount) {
                itemIndex = bFree[freeIndex++]
                ／／ 添加到新数组中
                newChildren.push(bChildren[itemIndex])
            } else {
                // There are no free items in b to match with
                // the free items in a, so the extra free nodes
                // are deleted.
             ／／ 如果b的free数组 不match a中的free数组  添加null
                itemIndex = i - deletedItems++
                newChildren.push(null)
            }
        }
    }

// 遍历完a数组后 newchildren为

    var lastFreeIndex = freeIndex >= bFree.length ?
        bChildren.length :
        bFree[freeIndex]

    // Iterate through b and append any new keys
    // O(M) time
   // 遍历b数组  添加在a数组中不存在的vnode
    for (var j = 0; j < bChildren.length; j++) {
        var newItem = bChildren[j]

        if (newItem.key) {
            if (!aKeys.hasOwnProperty(newItem.key)) {
                // Add any new keyed items
                // We are adding new items to the end and then sorting them
                // in place. In future we should insert new items in place.
                newChildren.push(newItem)
            }
        } else if (j >= lastFreeIndex) {
            // Add any leftover non-keyed items
            newChildren.push(newItem)
        }
    }

// 遍历后newchildren为

    var simulate = newChildren.slice()
    var simulateIndex = 0
    var removes = []
    var inserts = []
    var simulateItem
    //之后拿新的newChildren数组与b数组进行diff
    for (var k = 0; k < bChildren.length;) {
        var wantedItem = bChildren[k]
        simulateItem = simulate[simulateIndex]

        // remove items
       //  如果newChildren中的当前节点为null 我们往removes数组中添加patch
        while (simulateItem === null && simulate.length) {
            removes.push(remove(simulate, simulateIndex, null))
            simulateItem = simulate[simulateIndex]
        }

        if (!simulateItem || simulateItem.key !== wantedItem.key) {
            // if we need a key in this position...
            if (wantedItem.key) {
                if (simulateItem && simulateItem.key) {
                    // if an insert doesn't put this key in place, it needs to move
                    if (bKeys[simulateItem.key] !== k + 1) {
                        removes.push(remove(simulate, simulateIndex, simulateItem.key))
                        simulateItem = simulate[simulateIndex]
                        // if the remove didn't put the wanted item in place, we need to insert it
                        if (!simulateItem || simulateItem.key !== wantedItem.key) {
                            inserts.push({key: wantedItem.key, to: k})
                        }
                        // items are matching, so skip ahead
                        else {
                            simulateIndex++
                        }
                    }
                    else {
                        inserts.push({key: wantedItem.key, to: k})
                    }
                }
                else {
                    inserts.push({key: wantedItem.key, to: k})
                }
                k++
            }
            // a key in simulate has no matching wanted key, remove it
            else if (simulateItem && simulateItem.key) {
                removes.push(remove(simulate, simulateIndex, simulateItem.key))
            }
        }
        else {
            simulateIndex++
            k++
        }
    }

遍历开始，第一个key都为1

    // remove all the remaining nodes from simulate
    while(simulateIndex < simulate.length) {
        simulateItem = simulate[simulateIndex]
        removes.push(remove(simulate, simulateIndex, simulateItem && simulateItem.key))
    }

    // If the only moves we have are deletes then we can just
    // let the delete patch remove these items.
    if (removes.length === deletedItems && !inserts.length) {
        return {
            children: newChildren,
            moves: null
        }
    }

    return {
        children: newChildren,
        moves: {
            removes: removes,
            inserts: inserts
        }
    }
}

产生的patch数组如下