Virtual DOM && DIFF算法简单实现

写在前面

在线演示：http://wonghan.cn/Diff-demo/
Github链接：https://github.com/wonghan/Diff-demo

一、什么是Virtual DOM

1.DOM是树型结构，一般需要修改某个DOM节点时，先使用innerHTML=null清空DOM树，再重新插入新的DOM树，过于浪费(若只需修改一个li，却需要删掉100个li后重新插入99个li)
2.JS可以用JS对象结构表示DOM树型结构，这就是虚拟DOM
3.每次文档状态变化，会新建一颗虚拟DOM树，并将新树与旧树进行对比，记录两棵树的差异
4.将对比后的差异修改到真实的DOM树上

二、为什么使用Virtual DOM

1. DOM十分复杂，DOM操作十分昂贵，应尽量减少DOM操作。例如以下例子可以看出DOM节点的复杂：

var div = document.createElement('div');
var result = '';
for(let item in div){
  result += ' | ' + item;
}
console.log(result)；
//  | align | title | lang | translate | dir | dataset | hidden | tabIndex | accessKey | draggable | spellcheck | autocapitalize | contentEditable | isContentEditable | inputMode | offsetParent | offsetTop | offsetLeft | offsetWidth | offsetHeight | style | innerText | outerText | onabort | onblur | oncancel | oncanplay | oncanplaythrough | onchange | onclick | onclose | oncontextmenu | oncuechange | ondblclick | ondrag | ondragend | ondragenter | ondragleave | ondragover | ondragstart | ondrop | ondurationchange | onemptied | onended | onerror | onfocus | oninput | oninvalid | onkeydown | onkeypress | onkeyup | onload | onloadeddata | onloadedmetadata | onloadstart | onmousedown | onmouseenter | onmouseleave | onmousemove | onmouseout | onmouseover | onmouseup | onmousewheel | onpause | onplay | onplaying | onprogress | onratechange | onreset | onresize | onscroll | onseeked | onseeking | onselect | onstalled | onsubmit | onsuspend | ontimeupdate | ontoggle | onvolumechange | onwaiting | onwheel | onauxclick | ongotpointercapture | onlostpointercapture | onpointerdown | onpointermove | onpointerup | onpointercancel | onpointerover | onpointerout | onpointerenter | onpointerleave | nonce | click | focus | blur | namespaceURI | prefix | localName | tagName | id | className | classList | slot | attributes | shadowRoot | assignedSlot | innerHTML | outerHTML | scrollTop | scrollLeft | scrollWidth | scrollHeight | clientTop | clientLeft | clientWidth | clientHeight | onbeforecopy | onbeforecut | onbeforepaste | oncopy | oncut | onpaste | onsearch | onselectstart | previousElementSibling | nextElementSibling | children | firstElementChild | lastElementChild | childElementCount | onwebkitfullscreenchange | onwebkitfullscreenerror | setPointerCapture | releasePointerCapture | hasPointerCapture | hasAttributes | getAttributeNames | getAttribute | getAttributeNS | setAttribute | setAttributeNS | removeAttribute | removeAttributeNS | hasAttribute | hasAttributeNS | getAttributeNode | getAttributeNodeNS | setAttributeNode | setAttributeNodeNS | removeAttributeNode | closest | matches | webkitMatchesSelector | attachShadow | getElementsByTagName | getElementsByTagNameNS | getElementsByClassName | insertAdjacentElement | insertAdjacentText | insertAdjacentHTML | requestPointerLock | getClientRects | getBoundingClientRect | scrollIntoView | scrollIntoViewIfNeeded | animate | before | after | replaceWith | remove | prepend | append | querySelector | querySelectorAll | webkitRequestFullScreen | webkitRequestFullscreen | attributeStyleMap | scroll | scrollTo | scrollBy | createShadowRoot | getDestinationInsertionPoints | computedStyleMap | ELEMENT_NODE | ATTRIBUTE_NODE | TEXT_NODE | CDATA_SECTION_NODE | ENTITY_REFERENCE_NODE | ENTITY_NODE | PROCESSING_INSTRUCTION_NODE | COMMENT_NODE | DOCUMENT_NODE | DOCUMENT_TYPE_NODE | DOCUMENT_FRAGMENT_NODE | NOTATION_NODE | DOCUMENT_POSITION_DISCONNECTED | DOCUMENT_POSITION_PRECEDING | DOCUMENT_POSITION_FOLLOWING | DOCUMENT_POSITION_CONTAINS | DOCUMENT_POSITION_CONTAINED_BY | DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | nodeType | nodeName | baseURI | isConnected | ownerDocument | parentNode | parentElement | childNodes | firstChild | lastChild | previousSibling | nextSibling | nodeValue | textContent | hasChildNodes | getRootNode | normalize | cloneNode | isEqualNode | isSameNode | compareDocumentPosition | contains | lookupPrefix | lookupNamespaceURI | isDefaultNamespace | insertBefore | appendChild | replaceChild | removeChild | addEventListener | removeEventListener | dispatchEvent

2. JS运行效率高，可以通过JS模拟DOM结构，找出本地DOM必须更新的节点来更新，其他的不更新，以此减少DOM操作。例如，虚拟DOM如下：

<!--真实DOM-->
<ul id="list">
    <li class="item">Item 1</li>
    <li class="item">Item 2</li>
</ul>

// 虚拟DOM
{
  tag: 'ul',
  attrs: {
    id: 'list'
  },
  text: '',
  children: [
    {
      tag: 'li',
      attrs: {className: 'item'},
      children: [],
      text: 'Item 1'
    },
    {
      tag: 'li',
      attrs: {className: 'item'},
      children: [],
      text: 'Item 2'
    }
  ]
}

三、Virtual DOM如何应用，核心API是什么

• 参考代码库：
  • snabbdom 库：https://github.com/snabbdom/snabbdom
  • 核心API：
    h()：生成虚拟DOM
    patch()：对比前后DOM差异进行渲染（分为第一次插入空容器的操作与之后进行前后vnode对比后进行更新的操作）

四、Diff算法（伪代码，可执行的代码在第五点）

1. 使用h()方法生成vnode
2. 获取container容器，将vnode转化成真实dom节点，通过patch()方法进行插入到容器中
3. 生成新的vnode2，调用patch()方法递归对比前后虚拟DOM差异后，更新对应的真实DOM节点

// vnode生成函数
function h(tag='',attrs={},children=[],text=''){
  return {
    tag: tag,
    attrs: attrs,
    children: children,
    text: text
  }
}
// 插入 || diff DOM函数
function patch(vnode, newVnode){
  if(vnode instanceof HTMLElement){ // 若第一个参数是DOM节点，插入到容器里
    let node = createElement(newVnode);
    vnode.appendChild(node);
  }else{ // 两个都为vnode,执行diff算法
    updateChildren(vnode, newVnode); // diff
  }
}

// 由 虚拟DOM 生成 真实DOM 的函数
function createElement(vnode) {
    var tag = vnode.tag  // 'ul'
    var attrs = vnode.attrs || {}
    var children = vnode.children || []
    if (!tag) {
        return null
    }

    // 创建真实的 DOM 元素
    var elem = document.createElement(tag)
    if(text){
      elem.innerText = text;
    }
    // 属性
    for (let attrName in attrs) {
        if (attrs.hasOwnProperty(attrName)) {
            // 给 elem 添加属性
            elem.setAttribute(attrName, attrs[attrName])
        }
    }
    // 子元素
    children.forEach(function (childVnode) {
        // 给 elem 添加子元素
        elem.appendChild(createElement(childVnode))  // 递归
    })
    // 绑定真实DOM节点到vnode上
    vnode.elem = elem
    // 返回真实的 DOM 元素
    return elem
}

// diff算法对比前后差异
function updateChildren(vnode, newVnode) {
    var children = vnode.children || []
    var newChildren = newVnode.children || []

    children.forEach(function (childVnode, index) {
        var newChildVnode = newChildren[index]
        if (childVnode.tag === newChildVnode.tag) {
            // 深层次对比，递归
            updateChildren(childVnode, newChildVnode)
        } else {
            // 替换
            replaceNode(childVnode, newChildVnode)
        }
    })
}
// 替换真实DOM节点
function replaceNode(vnode, newVnode) {
    var elem = vnode.elem  // 真实的 DOM 节点
    var newElem = createElement(newVnode)
    // 替换
    elem.parentNode.replaceChild(newElem,elem);
}

五、Diff算法简单实现（github代码，可执行）

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>diff-demo</title>
</head>
<body>
  <div id="container">
  </div>
  <button id="btn">
    change
  </button>
  <button id="btn2">
    change2
  </button>
</body>
<script src="./index.js"></script>
<script>
  // 第一次插入
  let container = document.getElementById('container');
  let vnode1 = h('ul',{id: 'list'},[
    h('li',{class: 'item'},[],'Item 1'),
    h('li',{class: 'item'},[],'Item 2'),
    h('li',{class: 'item'},[],'Item 3')
  ])
  
  patch(container,vnode1);
  console.log(vnode1)

  // 修改vnode,查看diff效果
  let btn = document.getElementById('btn');
  btn.addEventListener('click',function(e){
    let vnode2 = h('ul',{id:'list'},[
      h('li',{class: 'item'},[],'Item B'),
      h('li',{class: 'item'},[],'Item 2'),
      h('li',{class: 'item'},[],'Item 3'),
      h('li',{class: 'item'},[],'Item 3'),
      h('li',{class: 'item'},[],'Item 3')
    ])
    patch(vnode1,vnode2);
    console.log(vnode1)
  })

  // 修改vnode,查看diff效果
  let btn2 = document.getElementById('btn2');
  btn2.addEventListener('click',function(e){
    let vnode2 = h('ul',{id:'list'},[
      h('li',{class: 'item'},[],'Item 1'),
      h('li',{class: 'item'},[],'Item 2'),
      h('li',{class: 'item'},[],'Item 3')
    ])
    patch(vnode1,vnode2);
    console.log(vnode1)
  })
</script>
</html>

/**
 * 插入 || diff DOM函数
 * @param {HTMLElement || Object} vnode container容器 || vnode节点
 * @param {object} newVnode newVnode节点
 */
function patch(vnode, newVnode){
  if(vnode instanceof HTMLElement){ // 若第一个参数是DOM节点，插入到容器里
    let node = createElement(newVnode);
    vnode.appendChild(node);
  }else{ // 两个都为vnode,执行diff算法
    createElement(newVnode); // 绑定DOM节点到newVnode上
    updateChildren(vnode, newVnode); // diff
  }
}
/**
 * vnode生成函数
 * @param {String} tag 标签名
 * @param {object} attrs 属性
 * @param {Array} children 子节点
 * @param {String} text 文本节点
 */
function h(tag='',attrs={},children=[],text=''){
  return {
    tag: tag,
    attrs: attrs,
    children: children,
    text: text
  }
}
/**
 * 真实 DOM 生成函数
 * @param {Object} vnode vnode节点
 */
function createElement(vnode){
  let tag = vnode.tag;
  let children = vnode.children || [];
  let attrs = vnode.attrs || {};
  let text = vnode.text || '';
  if(!tag){
    return null
  }
  // 创建真实的 DOM 元素
  let elem = document.createElement(tag);
  if(text){
    elem.innerText = text;
  }
  // 设置属性
  for(let key in attrs){
    if(attrs.hasOwnProperty(key)){
      elem.setAttribute(key,attrs[key])
    }
  }
  // 添加子元素节点
  children.forEach((childVnode)=>{
    elem.appendChild(createElement(childVnode))
  })
  // 真实 DOM 绑定到vnode上
  vnode.elem = elem;
  
  // 返回真实的 DOM 元素
  return elem
}

/**
 * Diff 函数
 * @param {Object} vnode vnode节点
 * @param {Object} newVnode newVnode节点
 */
function updateChildren(vnode, newVnode){
  // 保存父节点，方便之后DOM节点的删除
  let currentNode = vnode.elem;
  // 对比当前节点是否相同
  if(vnode.tag === newVnode.tag && vnode.text === newVnode.text && vnode.attrs.toString() === newVnode.attrs.toString()){
    // 若节点相同，深层次对比，递归(根据vnode & newVnode的数量,决定是增加节点还是删除节点)
    if(vnode.children.length >= newVnode.children.length){
      let childrenArray = vnode.children; // 保存children数组，方便之后修改原vnode
      for(let i=vnode.children.length-1;i>=0;i--){
        let childVnode = vnode.children[i];
        let newChildVnode = newVnode.children[i];
        if(newChildVnode && childVnode.tag === newChildVnode.tag){ // 防止newChildVnode===undefined导致报错
          updateChildren(childVnode, newChildVnode) // 递归
        }else{
          replaceNode(childVnode, newChildVnode,currentNode,childrenArray,i)
        }
      }
    }else{
      let childrenArray = vnode.children; // 保存children数组，方便之后修改原vnode
      for(let i=0;i<newVnode.children.length;i++){
        let childVnode = vnode.children[i];
        let newChildVnode = newVnode.children[i];
        if(childVnode && childVnode.tag === newChildVnode.tag){ // 防止childVnode===undefined导致报错
          updateChildren(childVnode, newChildVnode) // 递归
        }else{
          replaceNode(childVnode, newChildVnode,currentNode,childrenArray)
        }
      }
    }
  }else{
    replaceNode(vnode, newVnode)
  }
}
/**
 * 替换真实DOM节点 & 替换虚拟DOM节点
 * @param {Object} vnode 
 * @param {Object} newVnode 
 * @param {HTMLElement} parentNode 
 * @param {Array} childrenArray 
 * @param {Number} index 
 */
function replaceNode(vnode, newVnode,parentNode=null,childrenArray=[],index=0){
  if(vnode&&newVnode){ // 若两者都是vnode,应替换节点
    let elem = vnode.elem;
    let newElem = newVnode.elem;
    replaceVNode(vnode, newVnode)
    elem.parentNode.replaceChild(newElem,elem);
  }else if(vnode){ // 若newVnode===undefined,应删除节点
    let elem = vnode.elem;
    childrenArray.splice(index,1);
    elem.parentNode.removeChild(elem)
  }else{ // 若vnode===undefined,应添加节点
    let newElem = newVnode.elem;
    childrenArray.push(newVnode);
    parentNode.appendChild(newElem);
  }
}
/**
 * 替换虚拟DOM节点
 * @param {Object} vnode 
 * @param {Object} newVnode 
 */
function replaceVNode(vnode, newVnode){
  vnode.tag = newVnode.tag;
  vnode.elem = newVnode.elem;
  vnode.text = newVnode.text;
  vnode.attrs = newVnode.attrs;
  vnode.children = newVnode.children;
}