Principle and Implementation of Virtual DOM and Diff

0. Write at the beginning

This article will adhere to the principle of Talk is cheap, show me the code, so that the text is the most concise, and everything is explained by the code!

1. vdom

vdom is virtual DOM, which maps DOM to JS objects and updates DOM in combination with diff algorithm

The following is the DOM

<div id="app">
  <div class="home">home</div>
</div>

Mapping to VDOM

{<!-- -->
  tag: 'div',
  attrs: {<!-- -->
    id: 'app'
  },
  children: [
    {<!-- -->
      tag: 'div',
      attrs: {<!-- -->
        class: 'home'
      },
      children: [
        {<!-- -->
          tag: undefined,
          attrs: undefined,
          text: 'home',
          children: undefined
        }
      ]
    }
  ]
}

A simple render function is implemented through this vdom, and the dom can be modified through js operations

<template>
  <div id="app">
    <div v-for="item in arr">{<!-- -->{ item.name }} : {<!-- -->{ item.id }}</div>
  </div>
  <button id="btn">reRender</button>
</template>

let app = document.getElementById('app')
let data = {<!-- -->
  arr: [
    {<!-- --> name: 'a', id: 1 },
    {<!-- --> name: 'b', id: 2 },
    {<!-- --> name: 'c', id: 3 },
  ]
}

function render(data) {<!-- -->
  app.innerHtml = ''
  let children = []
  data.forEach(item => {<!-- -->
    let el = document. createElement("div")
    el.innerHtml = `${<!-- --> item.name } : ${<!-- -->item.id}`
    app.appendChild(el)
  })
}

// test
render(data.arr) // first rendering
let btn = document. getElementById('btn')
btn.onClick = () => {<!-- -->
  data.arr[2].id + + // modify associated data
  render(data.arr) // re-render: refresh the DOM violently, without diff, in fact, only need to update the last div
}

1.1 Using snabbdom to realize VDOM

Snabbldom is a library for easy implementation of vdom functions. It has two core APIs: h function and patch function

h(tag, attrs, children) // create vnode
patch(vnode, newVnode) // mount the vnode to the real dom after diffing

Combine h and patch to implement render rendering function

let app = document.getElementById('app')
let vnode;

function render(data) {<!-- -->
  let newVnode = h('div', {<!-- --> class: 'wrap' }, data.forEach(item => {<!-- -->
      return h('div', {<!-- -->}, `${<!-- -->item.name} : ${<!-- -->item.id}`)
    })
  )
  patch(vnode, newVnode)
  vnode = newVnode
}

render(data.arr) // first rendering

let btn = document. getElementById('btn')
btn.onClick = () => {<!-- -->
  data.arr[2].id + + // modify associated data
  render(data.arr) // re-rendering: mount to the real dom after vdom diff in the patch function, only the last div is updated here
}

2. Diff

In order to minimize DOM operations, it is necessary to compare the old and new vnodes through diff, and update the DOM for the changed places instead of replacing the entire DOM

The general idea is:

Call the patch function on the old and new nodes
Come in and first judge whether the two nodes are of the same type, specifically by comparing attributes such as key, tag, data
If it is not the same type, replace it after creating dom based on the new node
If it is the same type, then call the patchVnode function
Come in and first judge that the two nodes are text nodes, then replace the text content
Otherwise, judge whether there are child nodes, and if so, call the updateChildren function to update the child node array through the four pointers at the beginning and the end; if the old node has child nodes, If the new node does not have any child nodes, then delete the child nodes; if the old node has no child nodes but the new node does, then create a dom based on the new node for replacement

Convert VDOM to real DOM through createElment function

function createElement(vnode) {<!-- -->
  if(vnode.text) return document.createTextNode(vnode) // text node
    
  let {<!-- --> tag, attrs, children } = vnode
  
  let el = document. createElement(tag) // tag
  
  for(let key of attrs){<!-- --> // attrs
    el.setAttribute(key, attrs[key])
  }
  
  children.forEach(childVnode => {<!-- --> // children
    el.appendChild(createElement(childVnode))
  })
  vnode.el = el
  return el
}

Perform diff update operation through patch function

Determine whether vnode and newVnode are nodes of the same type, if yes, continue to recursively compare child nodes, otherwise replace directly

function patch(vnode, newVnode) {<!-- -->
  if (isSameNode(vnode, newVnode)) patchVnode(vnode, newVnode)
  else replaceVnode(vnode, newVnode)
}

function replaceVnode(vnode, newVnode) {<!-- -->
  let el = vnode.el // old node
  let parentEl = api.getParentNode(el) // get the parent node
  api.insertBefore(parentEl, createElement(newVnode), api.getNextSibling(el)) // Insert a new node
  api.removeChild(parentEl, el) // delete old node
}

function isSameNode(vnode, newVnode) {<!-- -->
  return (
    vnode.key == newVnode.key & amp; & amp; // key is the same
    vnode.tag == newVnode.tag & amp; & amp; // tag is the same
    isDef(vnode.data) == isDef(newVnode.data) // Whether data is defined
    // & amp; & amp;... other conditions
  )
}

function patchVnode(vnode, newVnode) {<!-- -->
  let el = newVnode.el = vnode.el // Get the dom corresponding to the current old node and assign it to the el of the new node

  // 1. Both are text nodes, and the texts are different
  if (vnode.text & amp; & amp; newVnode.text & amp; & amp; vnode.text != newVnode.text)
    return api.setElText(el, newVnode.text) // replace text
  
  let ch = vnode.children
  let newCh = newVnode.children
  if (ch & amp; & amp; newCh) return updateChildren(el, ch, newCh) // 2. All have child nodes, recursive comparison
  if (ch) return api.removeChild(el) // 3. vnode has child nodes, newVnode has none, delete child nodes
  return replaceVnode(vnode, newVnode) // 4. newNode has child nodes, but vnode has none, just replace
}

The implementation of updateChildren is more complicated. Use four pointers to compare vnode and newVnode

function updateChildren(el, ch, newCh) {<!-- -->
  // child node subscript
  let l = 0
  let r = ch.length - 1
  let newL = 0
  let newR = newCh. length - 1

  // child node
  let lNode = ch[l]
  let rNode = ch[r]
  let newLNode = newCh[newL]
  let newRNode = newCh[newR]

  while (l <= r & amp; & amp; newL <= newR) {<!-- -->
    if (!lNode || !rNode || !newLNode || !newRNode) {<!-- --> // boundary processing
      if (!lNode) lNode = ch[ + + l]
      if (!rNode) rNode = ch[--r]
      if (!newLNode) newLNode = newCh[ + + newL]
      if (!newRNode) newRNode = newCh[--newR]
      continue
    }
    
    // Comparison of the first and last pointers of the old and new child nodes l*newL, r*newR, l*newR, r*newL
    if (isSameNode(lNode, newLNode)) {<!-- -->
      patchVnode(lNode, newLNode)
      lNode = ch[ + + l]
      newLNode = newCh[++newL]
      continue
    }
    if (isSameNode(rNode, newRNode)) {<!-- -->
      patchVnode(rNode, newRNode)
      rNode = ch[--r]
      newRNode = newCh[--newR]
      continue
    }
    if (isSameNode(lNode, newRNode)) {<!-- -->
      patchVnode(lNode, newRNode)
      api.insertBefore(el, lNode.el, api.nextSibling(rNode.el))
      lNode = ch[ + + l]
      newRNode = newCh[--newR]
      continue
    }
    if (isSameNode(rNode, newLNode)) {<!-- -->
      patchVnode(rNode, newLNode)
      api.insertBefore(el, rNode.el, lNode.el)
      rNode = ch[--r]
      newLNode = newCh[++newL]
      continue
    }

    // Generate a key-idx map table in the vnode unknown sequence interval [l, r], use the key of newLNode to find a reusable position in the unknown sequence
    if (!keyIdxMap) keyIdxMap = getKeyIdxMap(ch, l, r) // map

    keyIdx = keyIdxMap.get(newLNode.key)
    if (!keyIdx) {<!-- -->
      api.insertBefore(el, createElement(newLNode), lNode.el)
    }
    else {<!-- -->
      let nodeToMove = ch[keyIdx]
      patchVnode(nodeToMove, newLNode)
      api.insertBefore(el, nodeToMove.el, lNode.el)
    }
    newLNode = newCh[++newL]
  }
}

function getKeyIdxMap(ch, l, r) {<!-- -->
  let map = new Map()
  while (l <= r) map.set(ch[l].key, l++)
  return map
}

Reference

Vue2 source code
15 pictures, 20 minutes to understand the core principle of the Diff algorithm
Vue2’s diff algorithm-updateChildren graphic flow and shortcomings