Why the Virtual Dom

As we all know, manipulating the DOM is a performance-intensive affair, so we can consider using JS objects to simulate DOM objects, since manipulating JS objects takes much less time than manipulating the DOM.

For example

// Suppose we simulate a ul that contains 5 Li's
[1.2.3.4.5] 
// Replace the above li here
[1.2.5.4]
Copy the code

From the above example, we can see at a glance that the third Li in the previous UL has been removed, and four and five have been replaced.

If the above corresponds to the DOM, this is the code below

// Delete the third li
ul.childNodes[2].remove()
// Switch the fourth li and the fifth li
let fromNode = ul.childNodes[4]
let toNode = node.childNodes[3]
let cloneFromNode = fromNode.cloneNode(true)
let cloenToNode = toNode.cloneNode(true)
ul.replaceChild(cloneFromNode, toNode)
ul.replaceChild(cloenToNode, fromNode)
Copy the code

Of course, in actual operation, we also need to give each node a label, as the basis to judge that it is the same node. This is why nodes in Vue and React’s official recommended lists use unique keys to ensure performance.

So since DOM objects can be simulated by JS objects, the corresponding DOM can also be rendered by JS objects

Here is a simple implementation of a JS object that emulates a DOM object

export default class Element {
  /** * @param {String} tag 'div' * @param {Object} props { class: 'item' } * @param {Array} children [ Element1, 'text'] * @param {String} key option */
  constructor(tag, props, children, key) {
    this.tag = tag
    this.props = props
    if (Array.isArray(children)) {
      this.children = children
    } else if (isString(children)) {
      this.key = children
      this.children = null
    }
    if (key) this.key = key
  }
  / / rendering
  render() {
    let root = this._createElement(
      this.tag,
      this.props,
      this.children,
      this.key
    )
    document.body.appendChild(root)
    return root
  }
  create() {
    return this._createElement(this.tag, this.props, this.children, this.key)
  }
  // Create a node
  _createElement(tag, props, child, key) {
    // Create a node with a tag
    let el = document.createElement(tag)
    // Set the node properties
    for (const key in props) {
      if (props.hasOwnProperty(key)) {
        const value = props[key]
        el.setAttribute(key, value)
      }
    }
    if (key) {
      el.setAttribute('key', key)
    }
    // Add child nodes recursively
    if (child) {
      child.forEach(element= > {
        let child
        if (element instanceof Element) {
          child = this._createElement(
            element.tag,
            element.props,
            element.children,
            element.key
          )
        } else {
          child = document.createTextNode(element)
        }
        el.appendChild(child)
      })
    }
    return el
  }
}
Copy the code

Description of Virtual Dom algorithm

Now that we have implemented the DOM through JS emulation, the next challenge is to determine the difference between the old object and the new object.

DOM is a multi-fork tree structure. If you need to completely compare the differences between two trees, the time complexity will be O(n ^ 3), which is definitely unacceptable. So the React team optimized the algorithm to achieve O(n) complexity to compare differences.

The key to achieving O(n) complexity is to compare nodes only at the same level, not across layers, given that few DOM elements are moved across layers in real business.

So there’s a two-step algorithm for determining differences

The object is first traversed from top to bottom and left to right, the depth of the tree, adding indexes to each node to facilitate the final rendering of the differences
Once the node has child elements, determine if the child elements are different

Virtual Dom algorithm implementation

Tree recursion

First of all, we will implement the recursive algorithm of the tree. Before implementing the algorithm, we will consider several situations when the two nodes are compared

New-nodetagNameorkeyUnlike the old one, this means that the old node needs to be replaced and there is no longer a need to traverse the child elements of the old node because the entire old node has been deleted
New-nodetagName 和 keySame as the old one, start traversing the subtree
No new nodes, so nothing to do

import { StateEnums, isString, move } from './util'
import Element from './element'

export default function diff(oldDomTree, newDomTree) {
  // To record the difference
  let pathchs = {}
  // The initial index is 0
  dfs(oldDomTree, newDomTree, 0, pathchs)
  return pathchs
}

function dfs(oldNode, newNode, index, patches) {
  // Used to save changes to the subtree
  let curPatches = []
  // There are three cases to judge
  // 1. There is no new node, so there is nothing to do
  // 2. The tagName and 'key' of the new node are different from those of the old node
  // 3. The new node has the same tagName and key as the old node, and starts traversing the subtree
  if(! newNode) { }else if (newNode.tag === oldNode.tag && newNode.key === oldNode.key) {
    // Determine whether the attribute has changed
    let props = diffProps(oldNode.props, newNode.props)
    if (props.length) curPatches.push({ type: StateEnums.ChangeProps, props })
    // Walk through the subtree
    diffChildren(oldNode.children, newNode.children, index, patches)
  } else {
    // The node is different and needs to be replaced
    curPatches.push({ type: StateEnums.Replace, node: newNode })
  }

  if (curPatches.length) {
    if (patches[index]) {
      patches[index] = patches[index].concat(curPatches)
    } else {
      patches[index] = curPatches
    }
  }
}
Copy the code

Determine changes to properties

Determining property changes is also a three-step process

Walk through the old property list to see if each property still exists in the new property list
Iterate through the new property list to see if the value of the property that exists in both lists has changed
In the second step, check to see if there are any properties that do not exist in the old property column list

function diffProps(oldProps, newProps) {
  // Determine Props in three steps
  // Iterate over the oldProps to see if any properties are deleted
  // Then traverse newProps to see if any property values have been modified
  // Finally check to see if any attributes are added
  let change = []
  for (const key in oldProps) {
    if(oldProps.hasOwnProperty(key) && ! newProps[key]) { change.push({prop: key
      })
    }
  }
  for (const key in newProps) {
    if (newProps.hasOwnProperty(key)) {
      const prop = newProps[key]
      if(oldProps[key] && oldProps[key] ! == newProps[key]) { change.push({prop: key,
          value: newProps[key]
        })
      } else if(! oldProps[key]) { change.push({prop: key,
          value: newProps[key]
        })
      }
    }
  }
  return change
}
Copy the code

Judge list difference algorithm implementation

This algorithm is the most core algorithm in the entire Virtual Dom, and let me tell you one by one. The main steps here are actually similar to determining attribute differences, which are also divided into three steps

Iterate through the old node list to see if each node still exists in the new node list
Iterate over the new node list to see if there are any new nodes
In the second step, determine whether the node has moved

PS: This algorithm only deals with nodes with keys

function listDiff(oldList, newList, index, patches) {
  // Retrieve all keys from both lists for easy traversal
  let oldKeys = getKeys(oldList)
  let newKeys = getKeys(newList)
  let changes = []

  // Used to save the changed node data
  // Saving with this array has the following advantages
  // 1. The index of the deleted node can be obtained correctly
  // 2. Switch node positions only need to operate DOM once
  // 3. Use the diffChildren function to judge, just need to traverse
  // Nodes exist in both trees, but are not necessary for new or removed nodes
  // Try again
  let list = []
  oldList &&
    oldList.forEach(item= > {
      let key = item.key
      if (isString(item)) {
        key = item
      }
      // Find if the new children contains the current node
      // If not, delete it
      let index = newKeys.indexOf(key)
      if (index === - 1) {
        list.push(null)}else list.push(key)
    })
  // Iterate over the changed array
  let length = list.length
  // Because deleting an array element changes the index
  // Delete from back to front to keep index unchanged
  for (let i = length - 1; i >= 0; i--) {
    // Determine whether the current element is empty, which means that it needs to be deleted
    if(! list[i]) { list.splice(i,1)
      changes.push({
        type: StateEnums.Remove,
        index: i
      })
    }
  }
  // Iterate through the new list to see if any nodes are added or moved
  // Also add and move nodes to 'list'
  newList &&
    newList.forEach((item, i) = > {
      let key = item.key
      if (isString(item)) {
        key = item
      }
      // Find the current node in the old children
      let index = list.indexOf(key)
      // New node not found, need to be inserted
      if (index === - 1  || key == null) {
        changes.push({
          type: StateEnums.Insert,
          node: item,
          index: i
        })
        list.splice(i, 0, key)
      } else {
        // If you need to move it, you need to move it
        if(index ! == i) { changes.push({type: StateEnums.Move,
            from: index,
            to: i
          })
          move(list, index, i)
        }
      }
    })
  return { changes, list }
}

function getKeys(list) {
  let keys = []
  let text
  list &&
    list.forEach(item= > {
      let key
      if (isString(item)) {
        key = [item]
      } else if (item instanceof Element) {
        key = item.key
      }
      keys.push(key)
    })
  return keys
}
Copy the code

Iterate over child elements for identification

For this function, there are only two main functions

Determine the difference between the two lists
Label the node

In general, what this function does is simple

function diffChildren(oldChild, newChild, index, patches) {
  let { changes, list } = listDiff(oldChild, newChild, index, patches)
  if (changes.length) {
    if (patches[index]) {
      patches[index] = patches[index].concat(changes)
    } else {
      patches[index] = changes
    }
  }
  // Record the last node traversed
  let last = null
  oldChild &&
    oldChild.forEach((item, i) = > {
      let child = item && item.children
      if (child) {
        index =
          last && last.children ? index + last.children.length + 1 : index + 1
        let keyIndex = list.indexOf(item.key)
        let node = newChild[keyIndex]
        // Only the existing nodes are traversed, other new or deleted nodes are not traversed
        if (node) {
          dfs(item, node, index, patches)
        }
      } else index += 1
      last = item
    })
}
Copy the code

Rendering differences

We can already figure out the difference between the two trees using our previous algorithm. Now that you know the difference, you need to update the DOM locally, so let’s take a look at the final step of the Virtual DOM algorithm

This function has two main functions

Walk through the tree in depth, pulling out changes that need to be made
Local DOM update

Overall this part of the code is pretty easy to understand

let index = 0
export default function patch(node, patchs) {
  let changes = patchs[index]
  let childNodes = node && node.childNodes
  // The depth traversal is the same as in diff
  if(! childNodes) index +=1
  if (changes && changes.length && patchs[index]) {
    changeDom(node, changes)
  }
  let last = null
  if (childNodes && childNodes.length) {
    childNodes.forEach((item, i) = > {
      index =
        last && last.children ? index + last.children.length + 1 : index + 1
      patch(item, patchs)
      last = item
    })
  }
}

function changeDom(node, changes, noChild) {
  changes &&
    changes.forEach(change= > {
      let { type } = change
      switch (type) {
        case StateEnums.ChangeProps:
          let { props } = change
          props.forEach(item= > {
            if (item.value) {
              node.setAttribute(item.prop, item.value)
            } else {
              node.removeAttribute(item.prop)
            }
          })
          break
        case StateEnums.Remove:
          node.childNodes[change.index].remove()
          break
        case StateEnums.Insert:
          let dom
          if (isString(change.node)) {
            dom = document.createTextNode(change.node)
          } else if (change.node instanceof Element) {
            dom = change.node.create()
          }
          node.insertBefore(dom, node.childNodes[change.index])
          break
        case StateEnums.Replace:
          node.parentNode.replaceChild(change.node.create(), node)
          break
        case StateEnums.Move:
          let fromNode = node.childNodes[change.from]
          let toNode = node.childNodes[change.to]
          let cloneFromNode = fromNode.cloneNode(true)
          let cloenToNode = toNode.cloneNode(true)
          node.replaceChild(cloneFromNode, toNode)
          node.replaceChild(cloenToNode, fromNode)
          break
        default:
          break}})}Copy the code

The last

The realization of Virtual Dom algorithm is the following three steps

Create DOM objects through JS simulation
Determine the difference between two objects
Rendering differences

let test4 = new Element('div', { class: 'my-div'},'test4'])
let test5 = new Element('ul', { class: 'my-div'},'test5'])

let test1 = new Element('div', { class: 'my-div' }, [test4])

let test2 = new Element('div', { id: '11' }, [test5, test4])

let root = test1.render()

let pathchs = diff(test1, test2)
console.log(pathchs)

setTimeout((a)= > {
  console.log('Start updating')
  patch(root, pathchs)
  console.log('End of update')},1000)
Copy the code

Of course, the current implementation is a little rough, but it’s good enough to understand the Virtual Dom algorithm.

You can read the code in the article here. All articles in this series will be updated in the repository, if you are interested.

The next article will be about state management, so stay tuned.

Finally, attach my official account

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

In-depth framework origin series – Virtual Dom

Why the Virtual Dom

Description of Virtual Dom algorithm

Virtual Dom algorithm implementation

Tree recursion

Determine changes to properties

Judge list difference algorithm implementation

Iterate over child elements for identification

Rendering differences

The last

In-depth framework origin series – Virtual Dom

Why the Virtual Dom

Description of Virtual Dom algorithm

Virtual Dom algorithm implementation

Tree recursion

Determine changes to properties

Judge list difference algorithm implementation

Iterate over child elements for identification

Rendering differences

The last

Related Posts

Mpvue small program and wechat live step pit summary

JSON – the use of Server

Image processing and Compositing in JavaScript