virtual-dom源码学习二——使用diff算法进行更新（diff方法跟踪）

[lizhongzhen11]

virtual-dom源码学习二——使用diff算法进行更新

回顾

上一篇virtual-dom源码学习一——生成虚拟dom数据结构并渲染节点，我跟着源码了解了 virtual-dom 是如何将特定的参数转换成它内置的 VNode 数据结构，然后又是如何将 VNode 结构生成DOM节点的，附上此时的 VNode 数据结构：

// oldVNode -> oldTree
{
  "children": [
    {
      "text": "0"
    }
  ],
  "count": 1,
  "descendantHooks": false,
  "hasThunks": false,
  "hasWidgets": false,
  "hooks": undefined,
  "key": undefined,
  "namespace": null,
  "tagName": "DIV",
  "properties": {
    "style": {
      "textAlign": 'center',
      "lineHeight": '100px',
      "border": '1px solid red',
      "width": '100pxpx',
      "height": '100pxpx'
    }
  }
}

再附上定时更新代码：

setInterval(function () {
  count++;
  var newTree = render(count);
  var patches = vdom.diff(tree, newTree);
  rootNode = vdom.patch(rootNode, patches);
  tree = newTree;
}, 1000);

探索之旅

老规矩，一步一步来，假设目前定时器才执行第一次，那么此时count自增为1：

count++; // 1
var newTree = render(count); // 生成新的vnode

定时器第一次执行后的newTree：

{
  "children": [
    {
      "text": "1"
    }
  ],
  "count": 1,
  "descendantHooks": false,
  "hasThunks": false,
  "hasWidgets": false,
  "hooks": undefined,
  "key": undefined,
  "namespace": null,
  "tagName": "DIV",
  "properties": {
    "style": {
      "textAlign": 'center',
      "lineHeight": '101px',
      "border": '1px solid red',
      "width": '101pxpx',
      "height": '101pxpx'
    }
  }
}

注意：newTree.count 和传入的 count 不是一个东西，newTree.count 是 children.length。此时 children 是 [{text: '1'}]。

重点来了！心心念念的diff出现了！！！

var patches = vdom.diff(tree, newTree);

diff方法干了什么？

首先，diff方法在vtree/diff.js中定义。整个js文件有400+行代码，蛮多的。还是先看导出：

module.exports = diff

function diff(a, b) {
  var patch = { a: a } // {a: tree}
  walk(a, b, patch, 0) // walk(tree, newTree, {a: tree}, 0)
  return patch
}

单独的 diff 方法代码很少，内部用到了 walk，看来关键点在 walk 中。walk 中估计得有近60行代码：

function walk(a, b, patch, index) { // tree, newTree, {a: tree}, 0
  if (a === b) { // 很明显，不符合跳过
    return
  }
  var apply = patch[index] // undefined
  var applyClear = false
  if (isThunk(a) || isThunk(b)) { // 不符合跳过
    thunks(a, b, patch, index)
  } else if (b == null) { // 不符合跳过
    // ...
  } else if (isVNode(b)) { // newTree的确是VNode，这个不能跳了
    // ...
  } else if (isVText(b)) { // 不符合跳过
    // ...
  } else if (isWidget(b)) { // 不符合跳过
    // ...
  }
  if (apply) {
    patch[index] = apply
  }
  if (applyClear) {
    clearState(a, patch, index)
  }
}

根据以上源码，我知道会走isVNode(b)这个分支，让我看看里面做了什么不可见人的事：

if (isVNode(a)) { // tree 也是VNode，符合
  if (a.tagName === b.tagName &&
    a.namespace === b.namespace &&
    a.key === b.key) { // 这里确定 tree 和 newTree 是同一个dom，符合
    var propsPatch = diffProps(a.properties, b.properties)
    if (propsPatch) {
      apply = appendPatch(apply,
      new VPatch(VPatch.PROPS, a, propsPatch))
    }
    apply = diffChildren(a, b, patch, apply, index)
  } else { // 跳过
    apply = appendPatch(apply, new VPatch(VPatch.VNODE, a, b))
    applyClear = true
  }
} else { // 跳过
  // ... 
}

根据以上源码可知，会执行 diffProps 方法。这个方法干嘛的呢？

// var propsPatch = diffProps(a.properties, b.properties)
// 此时等同于
var propsPatch = diffProps(tree.properties, newTree.properties)
function diffProps(a, b) {
  var diff
  for (var aKey in a) {
    if (!(aKey in b)) { // tree.properties有的属性，newTree.properties却没有
      diff = diff || {}
      diff[aKey] = undefined // 缓存到diff对象上，由于newTree上没有，所以值设为undefined
    }
    var aValue = a[aKey]
    var bValue = b[aKey]
    if (aValue === bValue) {
      continue
    } else if (isObject(aValue) && isObject(bValue)) {
      if (getPrototype(bValue) !== getPrototype(aValue)) {
        diff = diff || {}
        diff[aKey] = bValue
      } else if (isHook(bValue)) {
        diff = diff || {}
        diff[aKey] = bValue
      } else {
        var objectDiff = diffProps(aValue, bValue)
        if (objectDiff) {
          diff = diff || {}
          diff[aKey] = objectDiff
        }
      }
    } else {
      diff = diff || {}
      diff[aKey] = bValue
    }
  }
  for (var bKey in b) {
    if (!(bKey in a)) {
      diff = diff || {}
      diff[bKey] = b[bKey]
    }
  }
  return diff
}

diffProps方法大致看下来，主要返回一个对象， 该对象缓存了 tree.properties 和 newTree.properties 之间具有不同属性值的属性以及 newTree.properties 和 tree.properties 中各自独有的属性。当然，tree.properties 中独有的属性，属性值直接设为 undefined，毕竟更新时也是要删除的

不过，如果 properties 中的属性值都是对象的话，情况还有点特殊。要考虑两者的原型对象是否相同以及 newTree.properties 中对应的属性值是不是 EvHook 实例，都不符合的话就要继续递归调用 diffProps 了。

再回到 walk 相应的代码处：

// 由于定时器改了count，properties中的style对象也被更改了，
// 所以此时的 propsPatch 就是 tree 和 newTree 两者 properties 的不同属性构成的对象
// {
//   "style": {
//     "lineHeight": '101px',
//     "width": '101pxpx',
//     "height": '101pxpx'
//   }
// }
var propsPatch = diffProps(tree.properties, newTree.properties)
if (propsPatch) { // 存在，会执行
  apply = appendPatch(apply, new VPatch(VPatch.PROPS, a, propsPatch))
}
apply = diffChildren(a, b, patch, apply, index)

根据以上代码，此时会执行 appendPatch 方法，但在执行前，我发现它第二个参数会去实例化 VPatch 对象，这个 VPatch 目前还是个生脸，我的去查查：

// 源码就这么多
var version = require("./version")
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
module.exports = VirtualPatch
function VirtualPatch(type, vNode, patch) {
  this.type = Number(type)
  this.vNode = vNode
  this.patch = patch
}
VirtualPatch.prototype.version = version
VirtualPatch.prototype.type = "VirtualPatch"

代码很少，根据我的传参会得到这样的 VirtualPatch(即VPatch) 实例：

// new VPatch(VPatch.PROPS, a, propsPatch)
// 相当于
new VPatch(4, tree, {
  style {
    lineHeight: '101px',
    width: '101pxpx',
    height: '101pxpx'
  }
})
// 得到
{
  type: 4,
  vNode: tree,
  patch: {
    style {
      lineHeight: '101px',
      width: '101pxpx',
      height: '101pxpx'
    }
  }
}

然后执行 appendPatch：

// apply = appendPatch(apply, new VPatch(VPatch.PROPS, a, propsPatch))
// 相当于
apply = appendPatch(undefined, {
  type: 4,
  vNode: tree,
  patch: {
    style {
      lineHeight: '101px',
      width: '101pxpx',
      height: '101pxpx'
    }
  }
})
function appendPatch(apply, patch) {
  if (apply) {
    if (isArray(apply)) {
      apply.push(patch)
    } else {
      apply = [apply, patch]
    }
    return apply
  } else {
    return patch
  }
}
// 此时apply
{
  type: 4,
  vNode: tree,
  patch: {
    style {
      lineHeight: '101px',
      width: '101pxpx',
      height: '101pxpx'
    }
  }
}

由于一开始 apply 就是 undefined，所以即使走了 appendPatch 方法，那也是原封不动的返回 patch 对象即刚刚实例化的 VPatch 对象。这里目前的作用就是给apply赋值，方便下面的diffChildren操作。

让我看看 diffChildren 干嘛的：

// apply = diffChildren(a, b, patch, apply, index)
// 此时apply和patch是同一个，index来源于walk的传参，所以等同于
apply = diffChildren(tree, newTree, {a : tree}, apply, 0)
function diffChildren(a, b, patch, apply, index) {
  var aChildren = a.children // 此时是 tree.children: [{text: 0}]
  var orderedSet = reorder(aChildren, b.children)
  // ...
  return apply
}

结果还没看两行呢，又调用了 reorder 方法，这个方法近160行代码！！！硬着头皮看看吧：

// reorder(aChildren, b.children)
// 相当于
reorder([{text: '0'}], [{text: '1'}])
function reorder(aChildren, bChildren) {
  // keyIndex会去遍历，看子元素中是否存在key属性
  // 可惜这里不存在，会返回 {keys: {}, free: [0]}
  var bChildIndex = keyIndex(bChildren) // {keys: {}, free: [0]}
  var bKeys = bChildIndex.keys // {}
  var bFree = bChildIndex.free // [0]
  if (bFree.length === bChildren.length) { // 都是1，成立，直接执行下面代码后返回
    return {
      children: bChildren,
      moves: null
    }
  }
  // ...
}

// 最终结果
{
  children: [
    {
      text: '1'
    }
  ],
  moves: null
}

由于示例比较简单，所以虽然 reorder 里面代码多，但是目前我用不到那么多，哈哈哈哈哈！

事实上，后面还有好多代码，判断很多种情况。

附上下面的代码大致逻辑：

1. 如果 tree 和 newTree 的 children 中某些子元素的确拥有 key 属性，那么通过 keyIndex 方法后，得到的 free 值长度确实会和 children 长度不一致（因为有key的话就不会走 free.push(i) 了），这时候会把 newTree.children 里面有 key 属性的子元素放进定义的 newChildren 中，如果 tree.children 中有，但是 newTree.children 中没有，则会执行 newChildren.push(null)。
2. 然后遍历 newTree.children，把它独有的子元素也放进 newChildren 中。
3. 接下来拷贝个副本，把子元素为 null 的都给删掉，放进 removes 数组中（由于接下来只会通过splice来改变数组，不改变内部子元素对象，所以不会影响 newChildren）
4. 删除 null 元素后，再拿 null 之前对应的数组下标去取新的元素赋值给 simulateItem
5. 如果 simulateItem 存在或 simulateItem.key 与 newTree.children[k].key 相同，k 和 simulateIndex 均自增1
6. 如果 simulateItem 不存在或 simulateItem.key 与 newTree.children[k].key 不相同：
   1. 如果 newTree.children[k].key 不存在：
      1. 如果 simulateItem 存在并且 simulateItem.key 也存在，执行 inserts.push({key: wantedItem.key, to: k})
   2. 如果 newTree.children[k].key 存在：
      1. 如果 simulateItem 存在并且 simulateItem.key 也存在：
         1. 如果插入项没有将此键放置到位，则继续删除当前的 simulate，放到 removes 里面，simulateItem 再取后一个元素！
            1. 如果 simulateItem 不存在或 simulateItem.key 与 newTree.children[k].key 不相同，执行 inserts.push({key: wantedItem.key, to: k})
            2. 否则执行 simulateIndex++
7. 清空 simulate 数组
8. 如果inserts 是空数组，且 removes 长度和已删除的 deletedItems 相同，返回 {children: newChildren, moves: null}
9. 否则，最终返回 {children: newChildren, moves: {removes: removes, inserts: inserts}}

再回到 diffChildren 看看呢：

// var orderedSet = reorder(aChildren, b.children) 
// 等同于
var orderedSet = {
  children: [
    {
      text: '1'
    }
  ],
  moves: null
}
var bChildren = orderedSet.children // [{text: '1'}]
var aLen = aChildren.length // 1
var bLen = bChildren.length // 1
var len = aLen > bLen ? aLen : bLen // 1
for (var i = 0; i < len; i++) {
  var leftNode = aChildren[i] // {text: '0'}
  var rightNode = bChildren[i] // {text: '1'}
  index += 1 // 1
  if (!leftNode) { // 不符合，跳过
    if (rightNode) {
      // Excess nodes in b need to be added
      apply = appendPatch(apply,
          new VPatch(VPatch.INSERT, null, rightNode))
    }
  } else { // 继续调用walk
    walk(leftNode, rightNode, patch, index)
  }
  // 这里一开始没看懂，而且我示例也确实不符合
  // 回顾下大致明白其意思了，要结合vnode类型来看
  // 这个count与leftNode内部的children长度有关
  // 这里其实是为了预防vnode节点内部还包含子孙嵌套的vnode节点
  // 如果真有的话，那么为了防止index冲突，
  // 需要用当前的index +
  // 子孙节点children.length之和 +
  // 子孙节点child.count之和
  // 得到的结果才是避免冲突后的index，给下面的代码patch[index]用作键名
  if (isVNode(leftNode) && leftNode.count) {
    index += leftNode.count
  }
}

根据代码，会继续调用walk，此时代码传参应该是这样的（注意，此时walk内部会再声明一个apply，这个apply和前面的不是同一个）：

walk({text: '0'}, {text: '1'}, {
  a: tree
}, 1)

// walk内部代码
var apply = patch[1] // undefined
// 此时{text: '0'}, {text: '1'}均属于VText类型，所以会走if (isVText(b)) {}分支
if (isVText(b)) {
  if (!isVText(a)) {
    apply = appendPatch(apply, new VPatch(VPatch.VTEXT, a, b))
    applyClear = true
  } else if (a.text !== b.text) { // 符合，一个是'0'，一个是'1'
    apply = appendPatch(apply, new VPatch(VPatch.VTEXT, a, b))
  }
}

结果又走了一次 appendPatch：

apply = appendPatch(apply, new VPatch(VPatch.VTEXT, a, b))
// 由于此时传入的index是1，walk内部再次声明一个apply，此时是undefined
// 此时等同于
apply = appendPatch(undefined, {
  type： 1，
  vNode： {text: '0'},
  patch: {text: '1'}
})

function appendPatch(apply, patch) {
  if (apply) {
    if (isArray(apply)) { // 跳过
      apply.push(patch)
    } else { // 跳过
      apply = [apply, patch]
    }
    return apply
  } else {
    return patch
  }
}

最终，得到新的 apply 对象：

// apply
{
  type： 1，
  vNode： {text: '0'},
  patch: {text: '1'}
}

由于 apply 已有，继续执行 walk 中的代码，来到了：

if (apply) {
  patch[index] = apply // 这里的index是1，因为是从diffChildren内执行walk过来的
}
// 此时的patch变为
{
  a: tree,
  '1': {
    type: 1,
    vNode: {text: '0'},
    patch: {text: '1'}
  }
}

然后继续回到 diffChildren 内部

// 由于我的示例比较简单，所以此时的orderedSet为
// {
//   children: [
//     {
//       text: '1'
//     }
//   ],
//   moves: null
// }
if (orderedSet.moves) { // moves为null，不符合条件，跳过
  // Reorder nodes last
  apply = appendPatch(apply, new VPatch(
    VPatch.ORDER,
    a,
    orderedSet.moves
  ))
}
return apply

绕了这么一大圈，最开始的 apply 并没有改变，最终返回的apply数据是：

{
  type: 4,
  vNode: tree,
  patch: {
    style {
      lineHeight: '101px',
      width: '101pxpx',
      height: '101pxpx'
    }
  }
}

此时这一层级的 walk 还没走完，继续：

if (apply) {
  patch[index] = apply
}
// 此时的patch为
{
  a: tree,
  0: {
    type: 4,
    vNode: tree,
    patch: {
      style {
        lineHeight: '101px',
        width: '101pxpx',
        height: '101pxpx'
      }
    }
  },
  1: {
    type: 1,
    vNode: {text: '0'},
    patch: {text: '1'}
  }
}

那么，最终的：

var patches = vdom.diff(tree, newTree);
// 即
{
  a: tree,
  0: {
    type: 4,
    vNode: tree,
    patch: {
      style {
        lineHeight: '101px',
        width: '101pxpx',
        height: '101pxpx'
      }
    }
  },
  1: {
    type: 1,
    vNode: {text: '0'},
    patch: {text: '1'}
  }
}

由于篇幅过长，临时性小结

virtual-dom的diff方法想法真的不错，它递归自己，遍历每个节点对应的vnode数据，只要有差异，就把差异放进 patches 对象内，键名递增，相当于把所有的差异平铺到 patches 对象上，这样调用patch 时可以不用递归差异对象了。

那它如何保证节点和差异一一对应呢？

关键就在于每个差异对象都有个 vNode 字段，该字段对应的值就是需要应用该差异的node节点所对应的vnode数据！！！

光一个diff方法就让我写了这么多，到目前为止，还没有涉及更新，只是获得了调用 diff 方法之后返回的对象，至于有什么用，得看看后面的 patch(rootNode, patches) 了，这个留待下章吧。

virtual-dom源码学习系列

1. virtual-dom源码学习一——生成虚拟dom数据结构并渲染节点
2. virtual-dom源码学习二——使用diff算法进行更新（diff方法跟踪）
3. virtual-dom源码学习三——使用diff算法进行更新（patch方法跟踪）