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

[lizhongzhen11]

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

回顾

回顾前一篇virtual-dom源码学习二——使用diff算法进行更新（diff方法跟踪）最后调用 diff 方法得到的 patches：

{
  a: tree,
  0: {
    type: 4,
    vNode: tree,
    patch: {
      style {
        lineHeight: '101px',
        width: '101pxpx',
        height: '101pxpx'
      }
    }
  },
  1: {
    type: 1,
    vNode: {text: '0'},
    patch: {text: '1'}
  }
}
// 等同于
{
  "a": {
    "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'
      }
    }
  },
  "0": {
    "type": 4,
    "vNode": {
      "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'
        }
      }
    },
    "patch": {
      "style": {
        "lineHeight": '101px',
        "width": '101pxpx',
        "height": '101pxpx'
      }
    }
  },
  "1": {
    "type": 1,
    "vNode": {text: '0'},
    "patch": {text: '1'}
  }
}

在回顾示例：

rootNode = vdom.patch(rootNode, patches);

rootNode 是初次生成的DOM节点，已经被插进 document 中了。让我先猜一下，patch 方法肯定是把老DOM节点更新，但是它如何做到的呢？

这点我不清楚。我有以下两种猜测：

1. 第一种，把 rootNode 迭代解析成 VNode 结构，然后去对比更新？那这样不就多此一举吗？毕竟 rootNode 一开始就对应 tree 啊，如果按照我的想法来做的话，只需要根据 newTree 生成新的DOM节点，然后整个替换即可啊，何必要经过这么多复杂的操作生成 patches 呢？？？

2. 第二种，或者只需要更新DOM节点内被修改的节点？当发现有子节点修改，直接利用 patches 里的数据去生成新的子节点然后替换？？？如果是这种猜测的话，必须确定父节点，需要修改的子节点以及修改的内容。根据什么来确定呢？就目前的结果来看，并没有唯一的 key 能够确定对应关系啊。难不成递归迭代旧的 VNode (这里是 tree)，同时遍历 patches，用 tree 跟 patches 去比对 "vNode" 字段对应的是不是同一个对象？？？而 tree 数据层级和已生成的 rootNode 节点层级是一致的，确定 tree 哪一层子孙元素改变就能确定 rootNode 哪一子孙节点需要更新！然后利用DOM API生成新的节点替换？？？

我的猜想到底对不对呢？继续看代码吧。

继续探索

patch 方法在vdom/patch.js中，先看导出：

module.exports = patch
function patch(rootNode, patches, renderOptions) {
  renderOptions = renderOptions || {} // 此时 {}
  renderOptions.patch = renderOptions.patch && renderOptions.patch !== patch
      ? renderOptions.patch
      : patchRecursive // 此时为patchRecursive
  renderOptions.render = renderOptions.render || render // 此时为render，其实就是createElement也是h方法
  return renderOptions.patch(rootNode, patches, renderOptions)
}

// 此时的调用传参
patch(rootNode, patches)

由于此时我并没有传递 renderOptions，所以此时 renderOptions.patch 就是下面的函数 patchRecursive，renderOptions.render 就是 createElement方法（也是h方法）。所以，其实相当于执行了下面这段代码：

return patchRecursive(rootNode, patches, {patch: patchRecursive, render: createElement})

让我瞧一瞧patchRecursive方法：

function patchRecursive(rootNode, patches, renderOptions) {
  var indices = patchIndices(patches)
  // ...
}
function patchIndices(patches) {
  var indices = []
  for (var key in patches) {
    if (key !== "a") {
      indices.push(Number(key))
    }
  }
  return indices
}

第一行就是调用其他方法，上面我也贴出来了，一目了然，根据我最开始展示的结构，这里其实只是把 patches 里面所有修改的数据在 patches 中对应的字符串类型的数值转换成 Number 类型放到数组里面，有啥用暂时不知：

// indices
[0, 1]

继续回到 patchRecursive 中：

function patchRecursive(rootNode, patches, renderOptions) {
  // 得到indices
  if (indices.length === 0) { // 跳过
    return rootNode
  }
  var index = domIndex(rootNode, patches.a, indices)
  // ...
}

又调用了一个 domIndex 方法，该方法在vdom/dom-index.js里面：

function domIndex(rootNode, tree, indices, nodes) { // nodes => undefined
  if (!indices || indices.length === 0) { // 跳过
    return {}
  } else {
    indices.sort(ascending) // [0, 1]
    return recurse(rootNode, tree, indices, nodes, 0)
  }
}
// 排序函数
function ascending(a, b) {
  return a > b ? 1 : -1
}
// 此时recurse调用传参为recurse(rootNode, tree, [0, 1], undefined, 0)
function recurse(rootNode, tree, indices, nodes, rootIndex) { 
  nodes = nodes || {} // 此时为 {}
  if (rootNode) { // 符合
    if (indexInRange(indices, rootIndex, rootIndex)) {
      nodes[rootIndex] = rootNode
    }
    // ...
  }
  return nodes
}

内部依然是不断调用其他函数，还是一步步来吧，此时已经到了 recurse 内部，需要调用 indexInRange 方法，让我look look（根据代码注释，这里是一个二分查找，它应该就是判断下标是不是在 indices 范围内）：

// 此时调用传参indexInRange([0, 1], 0, 0)
function indexInRange(indices, left, right) {
  if (indices.length === 0) { // 跳过
    return false
  }
  var minIndex = 0
  var maxIndex = indices.length - 1 // 1
  var currentIndex // undefined
  var currentItem // undefined
  while (minIndex <= maxIndex) {
    currentIndex = ((maxIndex + minIndex) / 2) >> 0 // 右移，第一次为0
    currentItem = indices[currentIndex] // 第一次为 0
    if (minIndex === maxIndex) { // 第一次不符合
        return currentItem >= left && currentItem <= right
    } else if (currentItem < left) { // 第一次不符合
        minIndex = currentIndex + 1
    } else  if (currentItem > right) { // 第一次不符合
        maxIndex = currentIndex - 1
    } else {
        return true // 第一次就直接返回true
    }
  }
  return false;
}

得到的结果是 true，继续执行：

var noChild = {}
function recurse(rootNode, tree, indices, nodes, rootIndex) { 
  nodes = nodes || {} // 此时为 {}
  if (rootNode) { // 符合
    if (indexInRange(indices, rootIndex, rootIndex)) {
      nodes[rootIndex] = rootNode // {0: rootNode}
    }
    var vChildren = tree.children // 此时为[{text: '0'}]
    if (vChildren) { // 符合
      var childNodes = rootNode.childNodes // 调用DOM API，获取所有子节点
      for (var i = 0; i < tree.children.length; i++) { // 由于tree结构与rootNode结构一一对应（毕竟是其虚拟dom结构）
        // 这里其实也是在遍历childNodes，由于只有一个子元素，所以只遍历一次
        rootIndex += 1
        var vChild = vChildren[i] || noChild // {text: '0'}
        var nextIndex = rootIndex + (vChild.count || 0) // 获取下一更新数据的index，此时为1
        // skip recursion down the tree if there are no nodes down here
        if (indexInRange(indices, rootIndex, nextIndex)) { // indexInRange([0, 1], 1, 1)，还是true
          // 将子元素传入，递归调用，但是这里传入的nodes是{0: rootNode}
          // 最终得到的nodes是{0: rootNode, 1: rootNode唯一子节点textNode}
          recurse(childNodes[i], vChild, indices, nodes, rootIndex)
        }
        rootIndex = nextIndex // 1
      }
    }
  }
  return nodes // {0: rootNode, 1: rootNode唯一子节点textNode}
}

上面代码我有加注释，走了一遍最后返回的是 nodes 对象，domIndex 内部也是将调用结果返回，也就是说，调用 domIndex 最终返回的是一个对象，数据为：

{0: rootNode, 1: rootNode唯一子节点textNode}

这里告一段落，继续回到 patchRecursive 中：

function patchRecursive(rootNode, patches, renderOptions) {
  var indices = patchIndices(patches) // [0, 1]
  // ...
  var index = domIndex(rootNode, patches.a, indices) // {0: rootNode, 1: rootNode唯一子节点textNode}
  // 返回该节点所在的顶层document对象，可以认为就是该页面的document
  var ownerDocument = rootNode.ownerDocument
  // 这里确保处在同一文本对象内
  if (!renderOptions.document && ownerDocument !== document) {
    renderOptions.document = ownerDocument
  }
  for (var i = 0; i < indices.length; i++) {
    var nodeIndex = indices[i]
    rootNode = applyPatch(rootNode,
        index[nodeIndex],
        patches[nodeIndex],
        renderOptions)
  }
  return rootNode
}

重点来了，整个更新最重要的一步来了，调用了 applyPatch 方法，让我来观察下内部有什么猫腻：

// 由于indices只有两个元素，所以调用传参如下
applyPatch(rootNode, rootNode, patches[0], renderOptions) // 第一次
applyPatch(rootNode, rootNode唯一子节点textNode, {
  type: 1,
  vNode: {text: '0'},
  patch: {text: '1'}
}, renderOptions) // 第二次
function applyPatch(rootNode, domNode, patchList, renderOptions) {
  // ...
  var newNode // undefined
  if (isArray(patchList)) { // 不符合
    // ...
  } else {
    newNode = patchOp(patchList, domNode, renderOptions)
    if (domNode === rootNode) {
      rootNode = newNode
    }
  }
  return rootNode
}

刚激动，结果还没结束，内部调用了 patchOp 方法，该方法在vdom/patch-op.js中，导出名其实叫：applyPatch，看来作者这个名字定义的冲突了，不得不改：

// 执行了两次
applyPatch(patches[0], rootNode, renderOptions) // 第一次
applyPatch(patches[1], rootNode唯一子节点textNode, renderOptions) // 第二次
module.exports = applyPatch
function applyPatch(vpatch, domNode, renderOptions) {
  var type = vpatch.type // 第一次是4，第二次是1
  var vNode = vpatch.vNode // 第一次是tree，第二次是{text: '0'}
  // 第一次是{style: {lineHeight: '101px',width: '101pxpx',height: '101pxpx'}}，第二次是{text: '1'}
  var patch = vpatch.patch 
  switch (type) {
      // ...
      case VPatch.VTEXT:
          return stringPatch(domNode, vNode, patch, renderOptions)
      // ...
      case VPatch.PROPS:
        applyProperties(domNode, patch, vNode.properties)
        return domNode
      // ...
  }
}

根据代码以及我加的注释，只符合以上两种情况，第一种父节点调用 applyProperties 方法改变属性，第二种文字节点调用 stringPatch 方法并返回：

• applyProperties 在 createElement 时就讲过，所以这里其实就是对原有的dom节点改下属性而已；
• stringPatch只做了两种判断，一种是文字替换，还有一种是重新渲染个文字节点并替换

function stringPatch(domNode, leftVNode, vText, renderOptions) {
  var newNode
  if (domNode.nodeType === 3) { // 是文字节点
    domNode.replaceData(0, domNode.length, vText.text)
    newNode = domNode
  } else {
    var parentNode = domNode.parentNode
    newNode = renderOptions.render(vText, renderOptions)
    if (parentNode && newNode !== domNode) {
      parentNode.replaceChild(newNode, domNode)
    }
  }
  return newNode
}

注意：里面用到了 replaceData 这个方法，我在MDN上并没有找到，反而在XML DOM上找到。但这肯定不是XML DOM，那这个api从哪来得呢？

domNode 就是document节点，它哪里来的 replaceData ？要想解决这个问题，我得回顾该节点创建的代码，我依稀记得 createElement 里面用到的 document 对象是引入进来的，回顾下代码：

var document = require("global/document")

说明这里的 document 跟我平常用的浏览器端的 document 有点不同，我去查了下 global/document，它其实只是做了封装，内部用到了一个叫 min-document 库，我又去 min-document 库看了下代码，果然找到了replaceData 方法。通过改变 this.data 达到改变 textNode 中的文字！

patch-op.js里面的 applyPatch 方法走完后，得到每个层级需要更新后的dom节点后，再回到patch.js里面的 applyPatch 方法，注意，patch.js里面的 applyPatch 接受的第一个参数 rootNode 一直都是根节点，所以即使更新了里面的 textNode 节点，父节点 rootNode 不变！！！

// patch.js里面的 `applyPatch`
function applyPatch(rootNode, domNode, patchList, renderOptions) {
  // ...
  newNode = patchOp(patchList, domNode, renderOptions)
  if (domNode === rootNode) { // 循环内只有第一次调用符合
    rootNode = newNode
  }
  // ...
  return rootNode
}

还记得前面说过本例中循环调用了两次 applyPatch 方法吗？

• 第一次调用时传入的 domNode 就是 rootNode，符合条件判断，改了 rootNode；
• 但是第二次调用时传入的 domNode 是 rootNode 下的textNode子节点，这里就不会改 rootNode了，所以 rootNode 只改了一次！！！
• 那更新后的textNode如何生效呢？傻了吧，textNode是不是 rootNode 子节点？ rootNode 是不是已经插进document了？不就相当于一个大对像下的某个子对象改了吗？document依然引用的是这个大对象，那么其子对象改了，document引用的也自然改了啊！

这里更新的一切前提是document依然引用该父节点！！！

applyPatch看完了，此时自然回到patchRecursive方法了：

function patchRecursive(rootNode, patches, renderOptions) {
  // ...
  return rootNode // 返回更新后的父节点
}
function patch(rootNode, patches, renderOptions) {
  return renderOptions.patch(rootNode, patches, renderOptions) // return rootNode 返回更新后的父节点
}

最终回到我的测试代码中：

rootNode = vdom.patch(rootNode, patches); // 得到返回更新后的父节点
tree = newTree; // 更新老的tree，为了下次更新使用

小结

好了，使用 diff 方法更新的整体流程算是走通了，整整两篇，代码一大堆！

不过最后看来，跟我文中开头的第二个猜想很像，确定父节点，确定需要更新的节点数据，逐层递归确定需要更新的子节点并应用更新，确保document引用该父节点，这样父节点的属性以及子孙节点无论怎么更新都能应用到页面上！！！

virtual-dom源码学习系列

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