深入了解Vue原理——虚拟DOM和diff算法

简介: 研究方向虚拟 DOM 如何被渲染函数(h 函数)产生?(手写 h 函数)diff 算法原理?(手写 diff 算法)虚拟 DOM 如何通过 diff 变为真正的 DOM 的?(虚拟 DOM 变回真正的 DOM 涵盖在 diff 算法里面)

深入了解Vue原理——虚拟DOM和diff算法


手撸虚拟 DOM 和 diff 算法


研究方向


  • 虚拟 DOM 如何被渲染函数(h 函数)产生?(手写 h 函数)
  • diff 算法原理?(手写 diff 算法)
  • 虚拟 DOM 如何通过 diff 变为真正的 DOM 的?(虚拟 DOM 变回真正的 DOM 涵盖在 diff 算法里面)


snabbdom 简介和测试环境搭建


  • 介绍:


  • snabbdom 是瑞典语单词,单词原意”速度“。
  • snabbdom 是著名的虚拟 DOM 库,是 diff 算法的鼻祖,Vue 源码借鉴了 snabbdom


  • 官方 Git


  • 安装 snabbdom :


  • 在 git 上的 snabbdom 源码是用 TypeScript 写的,git 上并不提供编译好的 JavaScript 版本。


  • 如果要使用 build 出来的 JavaScript 版的 snabbdom 库,可以直接从 npm 上下载:
npm i -D snabbdom

snabbdom 的测试环境搭建:


  • snabbdom 库是 DOM 库,所以无法在 node.js 环境运行,所以需要搭建 webpack 和 webpack-dev-server 开发环境,但是不需要安装任何 loader 。


  • 因为 webpack4 不支持 exports ,所以必须安装 5 版本及以上。建议安装:
npm i -D webpack@5 webpack-cli@3 webpack-dev-server@3
  • 参考 webpack 官网去配置 webpack 。


虚拟 DOM 和 h 函数


虚拟 DOM


  • 虚拟 DOM :用 JavaScript 对象描述 DOM 的层次结构。DOM 中的一切属性都在虚拟 DOM 中有对应的属性。


  • 真实 DOM 和虚拟 DOM
<!-- 真实 DOM -->
<div>
  <h3>
    我是一个标题
  </h3>
  <ul>
    <li>咖啡</li>
    <li>牛奶</li>
    <li>可乐</li>
  </ul>
</div>
// 虚拟 DOM
{
  "sel": "div",
    "data": {
      "class": { "box": true }
    },
    "children": [
      {
        "sel": "h3",
        "data": {},
        "text": "我是一个标题"
      },
      {
        "sel": "ul",
        "data": {},
        "children": [
          { "sel": "li", "data": {}, "text": "咖啡" },
          { "sel": "li", "data": {}, "text": "牛奶" },
          { "sel": "li", "data": {}, "text": "可乐" }
        ]
      }
    ]
}
  • diff 是发生在虚拟 DOM 上的。新虚拟 DOM 和 老虚拟 DOM 进行 diff(精细化比较),算出应该如何最小量更新,最后反映到真正的 DOM 上。


h 函数


  • h 函数用来产生 虚拟节点(vnode)
h('a', { props: { herf: 'http://www.baidu.com' } }, '百度')
// 上述 h 函数的调用方式会得到下面的虚拟节点:
{ "sel": "a", "data": { props: { href: 'http://www.baidu.com' } }, "text": "百度" }
// 上述虚拟节点表示的真正 DOM 如下:
<a herf="http://www.baidu.com">百度</a>

虚拟节点的属性:’

{
  children: undefined
  data: {}
  elm: undefined
  key: undefined
  sel: "div"
  text: "盒子"
}

h 函数初体验

import { init } from 'snabbdom/init'
import { classMoudle } from 'snabbdom/modules/class'
import { propsMoudle } from 'snabbdom/modules/props'
import { styleMoudle } from 'snabbdom/modules/style'
import { eventListenersModule } from 'snabbdom/modules/eventlisteners'
import { h } from 'snabbdom/h'
// 创建出 patch 函数
const patch = init([classMoudle, propsMoudle, styleMoudle, eventListenersModule])
// 创建虚拟节点
const myVnode1 = h('a', { props: { herf: 'http://www.baidu.com' } }, '百度')
console.log(myVnode1) // 输出结果为:{ "sel": "a", "data": { props: { href: 'http://www.baidu.com' } }, "text": "百度" }
// 让虚拟节点上树
const container = document.getElementById('container')
patch(container, myVnode1)
  • 上面的代码会在页面中生成一个 a 标签。


  • h 函数可以嵌套使用,从而得到虚拟 DOM 树(重要)。
h('ul', {}, [
  h('li', {}, '牛奶')
  h('li', {}, '咖啡')
  h('li', {}, '可乐')
])
// 上述代码可以得到这样的虚拟 DOM 树
{
  "sel": "ul",
  "data": {},
  "children": [
    { "sel": "li", "data": {}, "text": "咖啡" },
    { "sel": "li", "data": {}, "text": "牛奶" },
    { "sel": "li", "data": {}, "text": "可乐" }
  ]
}


手写 h 函数


  • 因为过程很复杂,所以写一个低配版的 h 函数,只实现主干功能,不注重细节。


  • vnode():
// 函数的功能非常简单,就是把传入的 5 个参数组合成对象返回
export default function (sel, data, children, text, elm) {
  return {
    sel, data, children, text, elm
  }
}

h():

// 引入 vnode
import vnode form './vnode.js'
// 低配版本的 h 函数:这个函数必须接受 3 个参数,缺一不可。所以它的重载功能较弱。
export default function h(sel, data, c) {
  if (arguments.length != 3) throw new Error('Sorry, h must take three arguments')
  if (typeof c == 'string' || typeof c == 'number') {
    return vnode(sel, data, undefined, c, undefined)
  }else if (Array.isArray(c)) {
    let children = []
    for (let i = 0; i < c.length; i++) {
      if (typeof c[i] == 'object' && c[i].hasOwnProperty('sel')) throw new Error('One of the array arguments passed in does not result in an H function')
      children.push(c[i])
    }
    // 循环结束,说明 children 收集完毕了
    return vnode(sel, data, children, undefined, undefined)
  }else if(!(typeof c == 'object' && c.hasOwnProperty('sel'))){
    let children = [c]
  }else{
    throw new Error('The parameter type passed in is incorrect')
  }
}

测试手写的 h 函数:

// 引入 h 函数
import h from './mysnabbdom/h.js'
let myVnode1 = h('div', {}, '文字')
let myVnode2 = h('div', {}, [
  h('p', {}, '嘿嘿')
  h('p', {}, '哈哈')
  h('p', {}, '嘻嘻')
  h('p', {}, [
    h('p', {}, 'A')
    h('p', {}, 'B')
  ])
])


diff 算法原理


  • 注意:


  • key 很重要,key 是这个节点的唯一标识,告诉 diff 算法,在更改前后它们是同一个 DOM 节点。
  • 只有是同一个虚拟节点,才进行精细化比较。(只有选择器相同并且 key 相同才是同一虚拟节点)
  • 只进行同层比较,不会进行跨层比较。


diff 处理新旧节点不是同一个节点时


  • diff 算法处理过程:

1.png


diff 处理新旧节点是同一个节点时


  • 处理过程

1.png


手写第一次上树时


  • 测试手写的 patch 函数:
// 引入 h 函数
import h from './mysnabbdom/h.js'
import patch from './mysnabbdom/patch.js'
let myVnode1 = h('h1', {}, '你好')
const container = document.getElementById('container')
patch(container, myVnode1)

patch()

export default function(oldVnode, newVnode) {
  // 判断传入的第一个参数是 DOM 节点还是虚拟节点
  if (oldVnode.sel == '' || oldVnode.sel == undefined) {
    // 传入的第一个参数是 DOM 节点,此时要包装为虚拟节点
    oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode)
  }
  // 判断 oldVnode 和 newVnode 是不是同一节点
  if (oldVnode.key == newVnode.key && oldVnode.sel == newVnode.sel) {
  } else {
    let newVnodeElm = creatElement(newVnode)
    // 插入到老节点之前
    if (oldVnode.elm.parentNode && newVnodeElm) {
      oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm)
    }
    // 删除老节点
    oldVnode.elm.parentNode.removeChild(oldVnode.elm)
  }
}

creatElement()

export default function(vnode) {
  // 创建一个孤儿节点
  let domNode = document.createElement(vnode.sel)
  // 有子节点还是有文本
  if (vnode.text != '' && (vnode.children == undefined || vnode.children.length == 0)) {
    // 它内部是文本
    domNode.innerText = vnode.text
  } else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
    // 它内部是子节点,就要递归创建节点
    for (let i = 0; i < vnode.length; i++) {
      // 得到当前这个 children
      let ch = vnode[i]
      // 创建出它的 DOM ,一旦调用 createElement 意味着:创建出 DOM 了,并且它的 elm 属性指向了创建出的 DOM,但是还没有上树,是一个孤儿节点
      let chDOM = creatElement(ch)
      // 上树
      domNode.appendChild(chDOM)
    }
  }
  // 补充 elm 属性
  vnode.elm = domNode
  return vnode.elm
}


手写新旧节点 text 的不同情况


1.png


diff 算法的子节点更新策略


  • 经典的 diff 算法优化策略(四种命中查找)
  • 新前与旧前
  • 新后与旧后
  • 新后与旧前(如果发生了,那么新前指向的节点,移动到旧后之后)
  • 新前与旧后(如果发生了,那么新前指向的节点,移动到旧前之前)


  • 如果都没有命中,就需要用循环来寻找了。


  • 整体流程图:

1.png

整体代码及注释:

function vnode(sel, data, children, text, elm) {
  const key = data.key
  return {
    sel, data, children, text, elm, key
  }
}
function h(sel, data, c) {
  if (arguments.length != 3) throw new Error('Sorry, h must take three arguments')
  if (typeof c == 'string' || typeof c == 'number') {
    return vnode(sel, data, undefined, c, undefined)
  } else if (Array.isArray(c)) {
    let children = []
    for (let i = 0; i < c.length; i++) {
      if (typeof c[i] == 'object' && c[i].hasOwnProperty('sel')) throw new Error('One of the array arguments passed in does not result in an H function')
      children.push(c[i])
    }
    // 循环结束,说明 children 收集完毕了
    return vnode(sel, data, children, undefined, undefined)
  } else if (!(typeof c == 'object' && c.hasOwnProperty('sel'))) {
    let children = [c]
  } else {
    throw new Error('The parameter type passed in is incorrect')
  }
}
// 真正创建节点,将 vnode 创建为 DOM,插入到 pivot 这个元素之前
function creatElement(vnode) {
  // 创建一个孤儿节点
  let domNode = document.createElement(vnode.sel)
  // 有子节点还是有文本
  if (vnode.text != '' && (vnode.children == undefined || vnode.children.length == 0)) {
    // 它内部是文本
    domNode.innerText = vnode.text
  } else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
    // 它内部是子节点,就要递归创建节点
    for (let i = 0; i < vnode.length; i++) {
      // 得到当前这个 children
      let ch = vnode[i]
      // 创建出它的 DOM ,一旦调用 createElement 意味着:创建出 DOM 了,并且它的 elm 属性指向了创建出的 DOM,但是还没有上树,是一个孤儿节点
      let chDOM = creatElement(ch)
      // 上树
      domNode.appendChild(chDOM)
    }
  }
  // 补充 elm 属性
  vnode.elm = domNode
  return vnode.elm
}
function checkSameVnode(a, b) {
  return a.sel == b.sel && a.key == b.key
}
function updataChildren(parentElm, oldCh, newCh) {
  // 旧前
  let oldStartIdx = 0
  // 新前
  let newStartIdx = 0
  // 旧后
  let oldEndIdx = oldCh.length - 1
  // 新后
  let newEndIdx = newCh.length - 1
  // 旧前节点
  let oldStartVnode = 0
  // 新前节点
  let newStartVnode = 0
  // 旧后节点
  let oldEndVnode = oldCh.length - 1
  // 新后节点
  let newEndVnode = newCh.length - 1
  let keyMap = null
  // 开始循环
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 首先不是判断命中,而是要略过已经加 undefined 标记的
    if (oldStartVnode == null || oldCh[oldStartIdx] == undefined) {
      oldStartVnode = oldCh[++oldStartIdx]
    } else if (oldEndVnode == null || oldCh[oldEndIdx] == undefined) {
      oldEndVnode = oldCh[--oldEndIdx]
    } else if (newStartVnode == null || newCh[newStartIdx] == undefined) {
      newStartVnode = oldCh[++newStartIdx]
    } else if (newEndVnode == null || newCh[newEndIdx] == undefined) {
      newEndVnode = oldCh[--newEndIdx]
    } else if (checkSameVnode(oldStartVnode, newStartVnode)) {
      // 新前和旧前
      patchVnode(oldStartVnode, newStartVnode)
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    } else if (checkSameVnode(oldEndVnode, newEndVnode)) {
      // 新后与旧后
      patchVnode(oldEndVnode, newEndVnode)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (checkSameVnode(oldStartVnode, newEndVnode)) {
      // 新后与旧前
      patchVnode(oldStartVnode, newEndVnode)
      // 插入节点
      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (checkSameVnode(oldEndVnode, newStartVnode)) {
      // 新前与旧后
      patchVnode(oldEndVnode, newStartVnode)
      // 插入节点
      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    } else {
      // 四种命中都没有命中
      // 制作 keyMap 一个映射对象,这样就不用每次都遍历老对象了
      if (!keyMap) {
        keyMap = {}
        // 从 oldStartIdx 开始,到 oldEndIndex 结束,创建 keyMap 映射对象
        for (let i = 0; i < oldStartIdx; i++) {
          const key = oldStartIdx[i].key
          if (key != undefined) {
            keyMap[key] = i
          }
        }
      }
      // 寻找当前这项(newStartIdx)在 keyMap 中的映射位置
      const idxInOld = keyMap[newStartVnode.key]
      if (idxInOld == undefined) {
        // 判断,如果 idxInOld 是 undefined 表示它是全新的项
        // 被加入的项(就是 newStartVnode 这项)现在还不是真正的 DOM 节点
        parentElm.insertBefore(creatElement(newStartVnode), oldStartVnode.elm)
      } else {
        // 如果不是 undefined,不是全新的项,而是要移动
        const elmToMove = oldCh[idxInOld]
        patch(elmToMove, newStartVnode)
        // 把这项设置为 undefined,表示已经处理完这一项了
        oldCh[idxInOld] = undefined
        // 移动,调用 insertBefore 也可以实现移动
        parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm)
      }
      // 指针下移,只移动新的头
      newStartVnode = newCh[++newStartIdx]
    }
  }
  // 继续看看有没有剩余的
  if (oldStartIdx <= newEndIdx) {
    // 插入的标杆
    // 遍历新的 newCh,添加到老的没有处理的之前
    for (let i = newStartIdx; i < newEndIdx; i++) {
      parentElm.insertBefore(creatElement(newCh(i)), oldCh[oldStartIdx].elm)
    }
  } else if (oldStartIdx <= oldEndIdx) {
    // 批量删除 oldStart 和 oldEnd 指针之间的项
    for (let i = 0; i < oldStartIdx; i++) {
      if (oldCh[i]) {
        parentElm.removeChild(oldCh[i].elm)
      }
    }
  }
}
function patchVnode(newVnode, oldVnode) {
  // 判断新旧 vnode 是否是同一个对象
  if (oldVnode === newVnode) return
  // 判断新 vnode 有没有 text 属性
  if (newVnode.text != undefined && (newVnode.children == undefined || newVnode.children.length == 0)) {
    // 新 vnode 有 text 属性
    if (newVnode.text != oldVnode) {
      // 如果新虚拟节点中的 text 和老的虚拟节点的 text 不同,那么直接让新的 text 写入老的 elm 中即可。如果老的 elm 中是 children,那么就会立即消失掉。
      oldVnode.elm.innerText = newVnode.text
    }
  } else {
    // 新vnode 没有 text 属性,有 children
    // 判断老的有没有 children
    if (oldVnode.children !== undefined && oldVnode.children.length > 0) {
      // 老的有 children,此时就是最复杂的情况,就是新老都有children
      updataChildren(oldVnode.elm, oldVnode.children, newVnode.children)
    } else {
      // 老的没有 children,新的有 children
      // 清空老的节点的内容
      oldVnode.elm.innerHtml = ''
      // 遍历新的 vnode 子节点,创建 DOM 上树
      for (let i = 0; i < newVnode.children.length; i++) {
        let dom = creatElement(newVnode.children[i])
        oldVnode.elm.appendChild(dom)
      }
    }
  }
}
function patch(oldVnode, newVnode) {
  // 判断传入的第一个参数是 DOM 节点还是虚拟节点
  if (oldVnode.sel == '' || oldVnode.sel == undefined) {
    // 传入的第一个参数是 DOM 节点,此时要包装为虚拟节点
    oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode)
  }
  // 判断 oldVnode 和 newVnode 是不是同一节点
  if (oldVnode.key == newVnode.key && oldVnode.sel == newVnode.sel) {
  } else {
    let newVnodeElm = creatElement(newVnode)
    // 插入到老节点之前
    if (oldVnode.elm.parentNode && newVnodeElm) {
      oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm)
    }
    // 删除老节点
    oldVnode.elm.parentNode.removeChild(oldVnode.elm)
  }
}


相关文章
|
1月前
|
机器学习/深度学习 算法 PyTorch
深度强化学习中SAC算法:数学原理、网络架构及其PyTorch实现
软演员-评论家算法(Soft Actor-Critic, SAC)是深度强化学习领域的重要进展,基于最大熵框架优化策略,在探索与利用之间实现动态平衡。SAC通过双Q网络设计和自适应温度参数,提升了训练稳定性和样本效率。本文详细解析了SAC的数学原理、网络架构及PyTorch实现,涵盖演员网络的动作采样与对数概率计算、评论家网络的Q值估计及其损失函数,并介绍了完整的SAC智能体实现流程。SAC在连续动作空间中表现出色,具有高样本效率和稳定的训练过程,适合实际应用场景。
216 7
深度强化学习中SAC算法:数学原理、网络架构及其PyTorch实现
|
2月前
|
算法 Java 数据库
理解CAS算法原理
CAS(Compare and Swap,比较并交换)是一种无锁算法,用于实现多线程环境下的原子操作。它通过比较内存中的值与预期值是否相同来决定是否进行更新。JDK 5引入了基于CAS的乐观锁机制,替代了传统的synchronized独占锁,提升了并发性能。然而,CAS存在ABA问题、循环时间长开销大和只能保证单个共享变量原子性等缺点。为解决这些问题,可以使用版本号机制、合并多个变量或引入pause指令优化CPU执行效率。CAS广泛应用于JDK的原子类中,如AtomicInteger.incrementAndGet(),利用底层Unsafe库实现高效的无锁自增操作。
理解CAS算法原理
|
2月前
|
存储 人工智能 缓存
【AI系统】布局转换原理与算法
数据布局转换技术通过优化内存中数据的排布,提升程序执行效率,特别是对于缓存性能的影响显著。本文介绍了数据在内存中的排布方式,包括内存对齐、大小端存储等概念,并详细探讨了张量数据在内存中的排布,如行优先与列优先排布,以及在深度学习中常见的NCHW与NHWC两种数据布局方式。这些布局方式的选择直接影响到程序的性能,尤其是在GPU和CPU上的表现。此外,还讨论了连续与非连续张量的概念及其对性能的影响。
99 3
|
3月前
|
机器学习/深度学习 人工智能 算法
探索人工智能中的强化学习:原理、算法及应用
探索人工智能中的强化学习:原理、算法及应用
|
3月前
|
机器学习/深度学习 人工智能 算法
探索人工智能中的强化学习:原理、算法与应用
探索人工智能中的强化学习:原理、算法与应用
|
4月前
|
JavaScript
HTML DOM 节点树
HTML DOM 节点是指在 HTML 文档对象模型中,文档中的所有内容都被视为节点。整个文档是一个文档节点,每个 HTML 元素是元素节点,元素内的文本是文本节点,属性是属性节点,注释是注释节点。DOM 将文档表示为节点树,节点之间有父子和同胞关系。
|
4月前
|
JavaScript
HTML DOM 节点
HTML DOM(文档对象模型)将HTML文档视为节点树,其中每个部分都是节点:文档本身是文档节点,HTML元素是元素节点,元素内的文本是文本节点,属性是属性节点,注释是注释节点。节点间存在父子及同胞关系,形成层次结构。
|
4月前
|
XML JavaScript 数据格式
XML DOM 遍历节点树
XML DOM 遍历节点树
|
4月前
|
JavaScript
DOM 节点列表长度(Node List Length)
DOM 节点列表长度(Node List Length)
|
4月前
|
XML JavaScript 数据格式
XML DOM 遍历节点树
XML DOM 遍历节点树

热门文章

最新文章