Vue源码之虚拟DOM和diff算法(二) 手写diff算法

个人练习结果仓库(持续更新)：Vue源码解析

patch函数简要流程

新旧节点不是同一个虚拟节点(新节点内容是 text)

不做过多解释了，代码中已经把每一步都解释了

src \ mysnabbdom \ patch.js

import vnode from './vnode.js'
import createElement from './createElement.js'

export default function (oldVnode, newVnode) {

  // 表示是真实DOM，真实DOM需要先转换成虚拟DOM后才进行下面的操作。因为真实DOM是没有sel这个属性的
  if (oldVnode.sel === '' || oldVnode.sel === undefined) {

    // 转换成虚拟DOM
    oldVnode = vnode(oldVnode.tagName.toLowerCase(), {
}
, [], '', oldVnode)
  }
    

  // 判断oldVnode和newVnode是不是同一个节点
  if (oldVnode.sel === newVnode.sel &
    &
 oldVnode.key === newVnode.key) {

    // 是同一个虚拟节点，需要进行精细化比对，最小化更新
    console.log('需要精细化比对')
  }
 else {

    // 不是同一个虚拟节点，暴力删除旧的，插入新的

    const newDomNode = createElement(newVnode)     // 把新虚拟节点变成真实DOM

    const pivot = oldVnode.elm

    // 将新创建的孤儿节点上树
    pivot.parentNode.insertBefore(newDomNode, pivot)
    // 删除旧的
    pivot.parentNode.removeChild(pivot)
  }

}

如果 oldVnode和 newVnode不是同一个虚拟节点，那么就直接暴力删除旧的，插入新的。

所以需要一个函数 createElement，它的功能是将新虚拟节点创建为DOM节点并返回。

src \ mysnabbdom \ createElement.js

// 真正创建节点，将vnode创建为DOM

export default function (vnode) {
    
  // 创建一个DOM节点，此时还是孤儿节点
  const domNode = document.createElement(vnode.sel)

  if (vnode.text !== '' &
    &
 (vnode.children === undefined || vnode.children.length === 0)) {

    // 内部是文字
    domNode.innerText = vnode.text
    vnode.elm = domNode
  }


  // 返回真实DOM对象
  return vnode.elm
}

测试

src \ index.js

import h from './mysnabbdom/h.js'
import patch from './mysnabbdom/patch.js'

const myVnode1 = h('h2', {
}
, '文字')

// container只是占位符，上树后会消失
const container = document.getElementById('container')

patch(container, myVnode1)     // 上树

新旧虚拟节点不是同一个节点，都能实现上树(不只是第一次)

import h from './mysnabbdom/h.js'
import patch from './mysnabbdom/patch.js'


const myVnode1 = h('h2', {
}
, 'hello')

// container只是占位符，上树后会消失
const container = document.getElementById('container')

patch(container, myVnode1)     // 上树

const myVnode2 = h('h3', {
}
    , 'hi')

patch(myVnode1, myVnode2)

新旧节点不是同一个虚拟节点(新节点内容是子节点)

src \ mysnabbdom \ createElement.js(部分)

else if (Array.isArray(vnode.children) &
    &
     vnode.children.length >
= 0) {
    
  // 内部是子节点,需要递归创建子节点
  for (let i = 0;
     i  vnode.children.length;
 i++) {

    const childDomNode = createElement(vnode.children[i])   // 递归创建子节点

    // 创建的子节点需要添加到DOM节点里
    domNode.appendChild(childDomNode)
  }

}

测试

src \ index.js

import h from './mysnabbdom/h.js'
import patch from './mysnabbdom/patch.js'


const myVnode1 = h('ul', {
}
, h('li', {
}
, [
  h('li', {
}
, '赤'),
  h('li', {
}
, '蓝'),
  h('li', {
}
, '紫'),
  h('li', {
}
, [
    h('div', {
}
, [
      h('ol', {
}
, [
        h('li', {
}
, '白'),
        h('li', {
}
    , '黑')
      ])
    ])
  ]),
]
))

// container只是占位符，上树后会消失
const container = document.getElementById('container')

patch(container, myVnode1)     // 上树

patch函数精细化比对流程

patch函数

实现简单部分的精细化比对，即不包括流程图中星星部分

// 判断oldVnode和newVnode是不是同一个节点
if (oldVnode.sel === newVnode.sel &
    &
 oldVnode.key === newVnode.key) {

  // 是同一个虚拟节点，需要进行精细化比对，最小化更新
  patchVnode(oldVnode, newVnode)
  if (oldVnode === newVnode) {

    // oldVnode和newVnode是内存上的同一对象，即完全相同，不做任何处理
    return
  }
    

  if (newVnode.text !== undefined &
    &
 (newVnode.children === undefined || newVnode.children.length === 0)) {

    // newVnode的内容是text，而不是子节点
    if (newVnode.text === oldVnode.text) {

      return
    }


    oldVnode.elm.innerText = newVnode.text
  }
 else {
    
    // newVnode的内容是子节点
    if (oldVnode.children !== undefined &
    &
     oldVnode.children.length >
 0) {

      // newVnode的内容是子节点，oldVnode的内容也是子节点

      console.log('最复杂的情况')
    }
 else {
    
      // newVnode的内容是子节点，而oldVnode的内容是text：需要清空oldVnode，然后再把newVnode的children添加DOM上
      oldVnode.elm.innerText = ''

      for (let i = 0;
     i  newVnode.children.length;
 i++) {

        let domNode = createElement(newVnode.children[i])
        oldVnode.elm.append(domNode)
      }

    }

  }


}

测试

oldVnode和newVnode是内存中同一个对象

const myVnode1 = h('h2', {
}
, 'hello')

// container只是占位符，上树后会消失
const container = document.getElementById('container')

patch(container, myVnode1)     // 上树

const myVnode2 = myVnode1

patch(myVnode1, myVnode2)

newVnode的内容是 text， oldVnode的内容是子节点

const myVnode1 = h('h2', {
}
, h('p', {
}
, 'hello'))

// container只是占位符，上树后会消失
const container = document.getElementById('container')

patch(container, myVnode1)     // 上树

const myVnode2 = h('h2', {
}
, 'hi')

patch(myVnode1, myVnode2)

newVnode和 oldVnode的内容都是 text(只写不同的，相同的自测)

const myVnode1 = h('h2', {
}
, 'hello')

// container只是占位符，上树后会消失
const container = document.getElementById('container')

patch(container, myVnode1)     // 上树

const myVnode2 = h('h2', {
}
, 'hi')

patch(myVnode1, myVnode2)

newVnode的内容是子节点， oldVnode的内容是 text

const myVnode1 = h('section', {
}
, 'hello')

// container只是占位符，上树后会消失
const container = document.getElementById('container')

patch(container, myVnode1)     // 上树

const myVnode2 = h('section', {
}
, [
  h('p', {
}
, '赤'),
  h('p', {
}
, '蓝'),
  h('p', {
}
, '紫')
])
patch(myVnode1, myVnode2)

diff的子节点更新策略

准备

将精细化比对，最小化更新部分代码封装成函数 patchVnode

修改 vnode.js文件，将data中的key取出来

export default function (sel, data, children, text, elm) {

  return {

    sel,
    data,
    children,
    text,
    elm,
    key: data.key
  }

}
    

原理

如上图所示，一共有四个指针，其中，旧前、旧后指向旧子节点的首尾，新前、新后指向新子节点的首尾。

有四种命中查找：命中一种就不会再进行命中判断了。没有命中的话，则按箭头方向换一种命中查找方式

规则：

• 前指针只能向下移动，后指针只能向上移动
• 当前指针在后指针下面时，循环完毕、(不包括在相同位置的情况)

新增

为了简便，直接把子节点用一个字母来表示

简单版本：

如果旧节点先循环完毕，则此时新前指针、新后指针范围内的节点是新增节点(包括新前指针、新后指针指向的节点)

复杂版本：

如果四种方式的查找都无法命中，则直接在旧子节点中寻找相同key的元素，不存在的话，新增并将该元素追加到旧前指针之前，新前指针下移

删除

位置变换

增 + 删 + 位置变化

key一样，节点内容却不同的情况

详解Vue的Diff算法(例6)

原理总结

1. 新前旧前：
   • 命中，新前指针、旧前指针下移，回到1，继续看有没有命中
   • 未命中，继续向下尝试命中
2. 新后旧后：
   • 命中，新后指针、旧后指针上移，回到1，继续看有没有命中
   • 未命中，继续向下尝试命中
3. 新后旧前：
   • 命中，移动旧前指针指向的节点到旧后指针的后面，并将原位置设置为 undefined，旧前指针下移，新后指针上移
   • 未命中，继续向下尝试命中
4. 新前旧后：
   • 命中，移动旧后指针指向的节点到旧前指针的前面，并将原位置设置为 undefined，旧后指针上移，新前指针下移
   • 未命中
     • 在旧节点中寻找相同key的节点
       • 存在
         • 在旧节点中找到的和新前指针指向的节点是同一个节点的话，将该节点追加到 旧前之前，并将原位置设置为 undefined， 新前指针下移一位
         • 在旧节点中找到的和新前指针指向的节点不是同一个节点的话，新增 新前指针指向的节点，将该节点追加到 旧前指针之前， 新前指针下移一位
       • 不存在
         • 新增并将该节点追加到 旧前指针之前， 新前指针下移一位
5. 循环结束
   • 新节点先循环完毕：删除旧前指针、旧后指针之间的节点，包括 旧前、 旧后指向的节点
   • 旧节点先循环完毕：新增新前指针、新后指针之间的节点到 旧前指针前，包括 新前、 新后指向的节点

实操

src \ patchVnode.js(最复杂的情况，单独抽出来，在updateChildren中操作)

if (oldVnode.children !== undefined &
    &
     oldVnode.children.length >
 0) {

  // newVnode的内容是子节点，oldVnode的内容也是子节点
  updateChildren(oldVnode.elm, oldVnode.children, newVnode.children)
}

src \ updateChildren.js

没什么难度，看原理总结慢慢写就行了(谨慎点)

阉割版本，只需要 sel和 key相同就认为是同一个虚拟节点。(即不需要判断内容是否相同)

// 精细化比对，最小化更新的，其中新旧节点的内容都是节点的情况

import createElement from "./createElement.js"
import patchVnode from "./patchVnode.js"

// parentElm：oldVnode对应的真实DOM，用于更新DOM
// oldCh：旧节点的子节点
// newCh：新节点的子节点

// 判断是不是同一个虚拟节点
function checkSamVnode(v1, v2) {
    
  return v1.sel === v2.sel &
    &
 v1.key === v2.key
}


export default function updateChildren(parentElm, oldCh, newCh) {

  // 旧前指针
  let oldStartIdx = 0
  // 旧后指针
  let oldEndIdx = oldCh.length - 1
  // 旧前节点
  let oldStartVnode = oldCh[0]
  // 旧后节点
  let oldEndVnode = oldCh[oldEndIdx]

  // 新前指针
  let newStartIdx = 0
  // 新后指针
  let newEndIdx = newCh.length - 1
  // 新前节点
  let newStartVnode = newCh[0]
  // 新后节点
  let newEndVnode = newCh[newEndIdx]

  let map = {
}
    ;
    

  while (oldStartIdx = oldEndIdx &
 newStartIdx = newEndIdx) {

    if (oldStartVnode === undefined) {

      // 跳过undefined
      oldStartVnode = oldCh[++oldStartIdx]
    }

    if (oldEndVnode === undefined) {

      // 跳过undefined
      oldEndVnode = oldCh[--oldEndIdx]
    }


    if (checkSamVnode(newStartVnode, oldStartVnode)) {

      // 新前旧前命中
      console.log('新前旧前命中')

      patchVnode(oldStartVnode, newStartVnode)
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    }
 else if (checkSamVnode(newEndVnode, oldEndVnode)) {

      // 新后旧后命中
      console.log('新后旧后命中')

      // 继续精细化比较两个节点
      patchVnode(oldEndVnode, newEndVnode)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    }
 else if (checkSamVnode(newEndVnode, oldStartVnode)) {

      // 新后旧前命中
      console.log('新后旧前命中')

      // 继续精细化比较两个节点
      patchVnode(oldStartVnode, newEndVnode)

      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibiling)
      oldStartVnode = undefined

      newEndVnode = newCh[--newEndIdx]
      oldStartVnode = oldCh[++oldStartIdx]
    }
 else if (checkSamVnode(newStartVnode, oldEndVnode)) {

      // 新前旧后命中
      console.log('新前旧后命中')

      // 继续精细化比较两个节点
      patchVnode(oldEndVnode, newStartVnode)

      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)
      oldEndVnode = undefined

      newStartVnode = newCh[++newStartIdx]
      oldEndVnode = oldCh[--oldEndIdx]
    }
 else {
    
      // 四种情况都没命中
      for (let i = oldStartIdx;
     i = oldEndIdx;
 i++) {

        const item = oldCh[i]
        if (item === undefined) {

          // 跳过undefined
          continue
        }

        const key = item.key
        map[key] = i
      }


      // 看一下map中有没有和新前指向的节点相同的
      const indexOld = map[newStartVnode.key]
      if (indexOld) {

        // 存在，则是移动
        const elmToMove = oldCh[indexOld]
        // 继续精细化比较
        patchVnode(elmToMove, newStartVnode)

        parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm)
        oldCh[indexOld] = undefined
      }
 else {

        // 不存在，需要新增节点
        const newDomNode = createElement(newStartVnode)
        parentElm.insertBefore(newDomNode, oldStartVnode.elm)
      }


      newStartVnode = newCh[++newStartIdx]
    }

  }


  if (newStartIdx = newEndIdx) {
    
    // 旧节点先循环完毕，需要新增`新前指针`、` 新后指针`之间节点
    for (let i = newStartIdx;
     i = newEndIdx;
 i++) {

      const item = newCh[i]
      if (item === undefined) {
    
        continue;

      }


      const newDomNode = createElement(item)

      if (!oldStartVnode) {

        // 如果此时旧前指针指向的是undefined，则直接在最后插入
        parentElm.appendChild(newDomNode)
      }
 else {

        parentElm.insertBefore(newDomNode, oldStartVnode.elm)
      }

    }

  }
 else if (oldStartIdx = oldEndIdx) {
    
    // 新节点先循环完毕，需要删除`旧前指针`、` 旧后指针`之间节点
    for (let i = oldStartIdx;
     i = oldEndIdx;
 i++) {

      const item = oldCh[i]
      if (item === undefined) {
    
        continue;

      }

      parentElm.removeChild(item.elm)
    }

  }


}
    

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！