virtual-dom

create on in javascript with 0 comment and 391 view

virtual-dom 即 虚拟 dom,使用 js 实现,这得益于 js 的执行速度,可在 virtual-dom 中高效的进行一系列复杂的 dom 操作。

为什么要使用 virtual-dom?

  • 细粒度的更新 dom
  • 找到最优的修改 dom 方案,避免繁重冗余的 dom 操作
  • 更利于组件化,利于维护

virtual-dom 原理

virtualdom.png

DOM

Q: 创建到渲染的过程中,总共有多少种 DOM 呢?它们之间如何转化?

                          —————————————————————————————
DOM结构  ————(生成)--->  | DOM Tree ———(渲染)--> 虚拟DOM | ————(创建)---> 真实DOM
                          —————————————————————————————

这里我将 DOM 类型分为 4 种,即:定义的 DOM 结构、 DOM Tree、 虚拟 DOM、 真实 DOM,分别通过 生成渲染创建 进行转化。

  1. DOM结构: 开发者自定义的dom,例如react在jsx中定义dom结构:
let dom = ( <div class="container"> <ul style="color: #fff"> <li>1</li> <li>2</li> <li>3</li> </ul> </div> )
  1. DOM Tree

使用类似JSON格式的对象来描述 dom 结构,得到一个 dom tree:

let treeDom= tree(dom)
{ "tagName": "div", "children": [ { "tagName": "ul", "style": { "color": "#fff" }, "children": [ { "tagName": "li" }, { "tagName": "li" }, { "tagName": "li" }, ] } ] }
  1. 虚拟DOM:存储在内存中的 dom 对象,利于快速操作 DOM。
    根据 tree-dom 生成虚拟 DOM
let vDom = createElement(treeDom)
  1. 原生 DOM:
    已经落实到 html 中的 dom 节点,例如将一个 dom 节点插入到 id 为 app 的节点下。
reader(vNode, document.getElementById('app'))

注意:需要清楚的了解虚拟 DOM 和 原生 DOM 的一个关系,起初我总是将这两者进行区分看待,以为他们两是独立开的,但实际并非如此。虚拟 DOM 可以看作是原生 DOM 的引用,这两者在逻辑上相同的,是一一映射的关系,只不过前者通过 javascript 解析在内存中,后者基于 HTML解析器 存在于磁盘或内存中,虚拟 DOM中的某个节点若发生更改,那么真实 DOM 也会发生更改。(说法不规范,待补充~~~)

所以,要实现这些转化过程,那么起码需要 2 个方法。

  1. tree() —— 生成 dom tree,用于描述 dom 结构
  2. render() —— dom 结构生成虚拟 dom

diff

顾名思义,diff 即用于找到两个 dom 的不同。

Q: 何时会发生 diff?

让我们回到起初实现 virtual-dom 的动机,即:当数据发生改变时,为了避免频繁手动操作 dom 及其带来的性能损失,我们希望,通过某种机制,使改变的数据自动反映到 document 上。
而这里的数据指的是什么呢?它指的是与 dom 存在某种意义上绑定的变量,建立绑定关系的关键在于 dom 中是否依赖这些变量。

对于某些替换元素来说,比如 Input, textarea,还存在着双向绑定的关系。(不在本文讨论范围内)

当绑定的数据发生改变时发生 diff,因此我们首先需要实时 watch(监听) 这些数据是否改变,然后再进行 diff 。

Q. 怎么监听数据的更改?

监听数据可借助 event,observer, defineProperty, proxy 等机制。以 defineProperty为例,将 data 作为被观察者,在数据获取(getter)时,收集依赖,在数据拦截中(setter),执行订阅者回调。这里不打算再展开说明,详情可参考
响应式原理
vue 依赖收集

Q: diff 具体比较的是什么?

当数据发生变更时,基于新数据与 dom 结构,会重新生成一个新的 dom-tree, 然后 diff old dom-tree 和 new dom-tree ,获取两者的不同(patches)。

let newTree = renderTree() let patches = diff(tree, newTree)

patchs

当我们 diff 两个 dom-tree 后,得到一个 patches,此时,我们需将其应用到我们的 vDom, 使得真实 DOM 自动更新。

                      (更新)
patchs ———---> vDom ————-----> companents
patch(dom, patches)

virtual-dom 实现

virtual-dom 的流程和方法已经梳理完毕,那么下面将分析每个方法的原理和细节。

DOM结构 -> 虚拟DOM

要实现这个过程,则需要完成 tree方法。
为了能更简单的实现,我们将其简化,因为本文目标不是要实现 jsx 这样 dom 结构解析功能。

设计一个函数 tree,其参数为: 节点名称,属性,子字节,返回一个 dom-tree

let new_tree = tree(nodeName, props, children)

当要定义这样的 DOM 结构时

<div class="container">
  <ul style="color: red">
    <li>1</li>
    <li>2</li>
    <li>3</li>
  </ul>
</div>

则这样定义:

t('div', {class: 'container'}, [
    t('ul', {style: 'color: red'}, [
	t('li',['1']),
	t('li',['2']),
	t('li',['3']),
    ])
])

这样写起来确实…很蛋疼…(突然感觉 jsx 和 tempalte 真是太好了 ~ )

这里我将其抽象为一个类,并定义其特征。

/**
 * Tree 类,元素节点生成 dom-tree
 */
class Tree {
  constructor(tagName, props, children){
    this.tagName = tagName,
    this.props = props || {}
    this.childrens = children
  }
  ...
}

function t() {
  return new Tree(...arguments)
}

export default t

在类中实现一个 reader 方法,用于生成虚拟 dom

reader() { let ele = document.createElement(this.tagName) for( let key in this.props) { this.setAttr(ele, key, this.props[key]) } let children = this.children.map((child) => { if (child instanceof Tree) { ele.appendChild(this.reader.call(child)) } else { ele.appendChild(document.createTextNode(child)) } }) return ele }

build dom tree

对于元素属性的处理

set prop

完成 Tree 类的定义后,在使用时,调用其方法,生成虚拟DOM,并插入到文档中。

let tree = t('div', {class: 'container'}, [ t('ul', {style: 'color: red'}, [ t('li',['1']), t('li',['2']), t('li',['3']), ]) ]) let vNode = tree.render() document.body.appendChild(vNode)

具体源码见github tree.js

diff 算法

diff 算法用于比较 old dom-tree 和 new dom-tree,生成 patches。

当要比较两个 dom 的不同时,通常会对每一个节点进行比较。
diff dom tree

如图,若 dom-tree 有 3 层,那复杂度则为 O(n^3),复杂度太高,这并不适合 web。

对于 web 说,通常不会出现不同层之间的节点交换,所以,我们可以对 dom-tree 逐层比较。

diff dom tree 2

这样,算法复杂度则简化到了 O(3n) 即 O(n)。

Q. 这两个 dom-tree 之间我们要比较些什么呢,从哪个节点开始比较,以及怎么存储比较的结果?

当改变一个 dom 时,试想一下,有哪些情况?例如:修改节点名,属性,属性,或调整节点顺序等,
总的来说,当节点发生改变时,有以下类型:

dom tree 改变节点

所以,先定义一些常量来表示改变的类型:

let type = { REPLACE : 0, REORDER : 1, PROPS : 2, TEXT : 3 }

dom-tree 由一个个节点组成,从根节点出发,使用深度优先遍历(DFS)的方式,对每个节点进行最细粒度的比较。(这其实也可以解释了为什么像 vue template这样的模板为什么只允许有一个根节点)

主要核心代码:

function diff (oldTree, newTree) {
  var index = 0 // 节点的序号
  var patches = {} // 用于保存 patches (以 index 为 key)
  dfsWalk(oldTree, newTree, index, patches)
  return patches
}
  1. 比较节点
function dfsWalk (oldNode, newNode, index, patches) { currentPatch = [] // 记录当前节点的改变 // 空节点(被移除) if(newtree === null) { } // 是否为文本节点 else if(_.isString(newtree) && _.isString(oldtree)){ if(oldtree !== newtree) { currentPatch.push({type: patch.TEXT, content: newNode}) } } // 节点对象是否相同 else if( oldNode.tagName === newNode.tagName && oldNode.key === newNode.key ){ // 检查属性 let propsPatches = diffProps(...) currentPatch.push({ type: patch.PROPS, props: propsPatches }) // 检查子节点 diffChildren(...) } else { // 替换 currentPatch.push({ type: patch.REPLACE, node: newNode }) } // 保存 patch if (currentPatch.length) { patches[index] = currentPatch } }
  1. 检查属性
    对于相同的节点对象,需要检查其属性是否更改。
    那么,分别遍历两个节点的属性并比较。
function diffProps(){
    let count = 0 // 记录两节点所有属性的数量,若数量为0,则没有属性。
    let propsPatches = {}
    for(oldProps){...}
    for(newProps){...}
    return propsPatches
}

  1. 检查子节点改变
    对于相同的节点对象,需要检查其子节点是否存在更改,循环遍历子节点,以子节点作为根节点,进行递归。

以上一切看似没有问题了,而现在还要考虑一下这种情况:

插入节点 diff 算法

当插入一个 p 元素后,若节点按照原来的顺序一一对比,那么导致的结果是后三个节点都发生了修改(其实对于 div, a节点来说,并未发生更改,只是顺序改变了),所以,每次发生插入或移除导致顺序发生变化时,diff 则会检查到这些节点都发生了改变,导致产生了多余的 dom 开销。所以,对于节点之间的顺序改变,我们需要一个算法计算两个数组中的对象的排序,作出一些 diff 优化, 使其能察觉出是插入还是移除。

实现一个 list-diff 算法。
该算法的主要思路是:使数组的成员都有自己的序号,当比较两个数组时,根据序号以及成员的修改情况,计算出 旧数组 改变为 新数组 所要做的改动,该算法的复杂度为 O(n)。

import listdiff from './listdiff'
var oldList = [{id: "a"}, {id: "b"}, {id: "c"}, {id: "d"}, {id: "e"}]
var newList = [{id: "c"}, {id: "a"}, {id: "b"}, {id: "e"}, {id: "f"}]

var moves = listdiff(oldList, newList, "id")
// `moves` is a sequence of actions (remove or insert): 
// type 0 is removing, type 1 is inserting
// moves: [
//   {index: 3, type: 0},
//   {index: 0, type: 1, item: {id: "c"}}, 
//   {index: 3, type: 0}, 
//   {index: 4, type: 1, item: {id: "f"}}
//  ]

listdiff 方法有三个参数,值得注意的是,“id” 这个入参代表着两数组将以成员的 id 属性来作为序号,比较完成后,会返回一个结果 moves,它用于描述 oldList 是如何变为 newList的,其中 type 0 代表移除,1 代表插入。
所以,当我们得到这个 moves 后,可直接将它加入到 patches 中, 待 patch 算法来应用它。

这其实可以解释了:如在 vue template 中,当遍历一个数组生成节点时,为什么要使 :key 保持唯一。

function diffChildren (oldChildren, newChildren, index, patches, currentPatch) { let diffs = listDiff(oldChildren, newChildren, 'key') // 基于key查询排序 if (diffs.moves.length) { let reorderPatch = { type: patch.REORDER, moves: diffs.moves } currentPatch.push(reorderPatch) } ... let leftNode = null let currentNodeIndex = index oldChildren.forEach((child, i) => { let newChild = newChildren[i] currentNodeIndex = (leftNode && leftNode.count)? currentNodeIndex + leftNode.count + 1 : currentNodeIndex + 1 dfsWalk(child, newChild, currentNodeIndex, patches) leftNode = child }) })

详细源码见 github diff.js

patch 算法

在完成了 diff 后,就得到了两个 dom-tree 的 patches,这时,我们需要将这个 patch 应用到实际的 dom 中。

ul子元素列表的 2 个元素前插入了一个节点 <li>4<li>,然后修改 ul 节点的 style 属性,

<div class="container"> - <ul style="color: red;border:1px solid #000"> + <ul style="color: blue;border:1px solid #000"> <li>1</li> + <li>4</li> <li>2</li> <li>3</li> </ul> </div>

通过 diff 算法得到的 patches 如下:

{ "1": [{ "type": 2, "props": { "style": "color:blue;border:1px solid #000" } }, { "type": 1, "moves": [{ "index": 3, "item": { "tagName": "li", "props": { "key": 3 }, "children": ["3"], "count": 1, "key": 3 }, "type": 1 }] }], "5": [{ "type": 3, "content": "4" }], "7": [{ "type": 3, "content": "2" }] }

这个 patches 代表着:

  1. 遍历 dom-tree 时的第 2 个节点(index: 1)的属性(type:2) style 发生了更改。
  2. 遍历 dom-tree 时的第 2 个节点的子节点列表发生顺序调整(type:1);其中,子元素列表的index 为 3 的地方插入(moves 中的 type: 1 代表 insert)了新的节点,该节点的信息存于 item 中。
  3. 遍历 dom-tree 时的第 5 和 第 7 个文本节点修改为 4 和 2。

与 diff 一样,在应用 patches 时,同样也遵循着深度优先(DFS)遍历。所以,我们需定义一个方法, 用于遍历节点:

function dfsWalk(node, walker, patches){ ... // 遍历子节点 let len = node.childNodes ? node.childNodes.length : 0 for(let i = 0; i < len; i++) { walker.index++ dfsWalk(node.childNodes[i], walker, patches) } ... }

而对于每一个节点,我们可获取到其对应的 patch,然后应用它。

function dfsWalk(node, walker, patches){ let currentPatchs = patches[walker.index] // 当前节点的补丁 // 遍历子节点 ... if(currentPatchs) { // 应用patch applyPatches(node, currentPatchs) } } function applyPatches(node, patches) { // patch算法... }
  • patch算法

发送更改的 type 分为 4 种类型,替换(REPLACE : 0),排序(REORDER : 1),属性(PROPS : 2),文本(TEXT : 3),对于每种类型作出对应的处理。

遍历 patches

patches.forEach((patch) => { //... })
  1. 替换
let newNode = (typeof patch.node === 'string')? document.createTextNode(patch.node) : patch.node.render() node.parentNode.replaceChild(newNode, node)
  1. 排序
reorderChildren(node, patch.moves)
  1. 属性
setProps(node, patch.props)
  1. 文本
node.textContent = patch.content

详细源码见 github patch.js.

总结

总的来说,virtual-dom 带来的好处是避免了开发者频繁操作 DOM 且其带来的性能问题,将 view 与 module 层进行一一映射。主要核心原理为: 生成初始 dom-tree 和虚拟 dom, 监听数据变更,若数据发生更改则构建 new dom-tree, 利用 diff 算法比较两棵 dom-tree 的不同,其称之为 patches,最后将 patches 应用到 虚拟 dom 中,反映到真实的 dom 上。

😁😂😃😄😅😆😇😈😉😐😑😒😓😔😕😖😗😘😙😠😡😢😣😤😥😦😧😨😩😰😱😲😳😴😵😶😷😸😹🙀🙁🙂🙃🙄🙅🙆🙇🙈
🙂