Implementing Vue-tiny dom-diff Algorithm | York's Blog

Introduction

Previously, we implemented the basic logic for updating data to view rendering. However, using methods like innerHTML is extremely inefficient. Therefore, we introduce the dom and diff algorithms. The process from data to view becomes:

state -> vdom -> dom

vNode Layer

A vNode is a lightweight object representing the DOM structure.

{
  tag, props, children
}

To simplify creation, we introduce a method h to create nodes.

export function h(tag, props, children) {
  return {
    tag,
    props,
    children,
  }
}

We need to modify the render function to return a created vNode (vTree).

render(context) {
return h(
'div',
{
id: 'id-1',
class: 'class-1'
},
[h('p', null, String(context.value)), h('p', null, String(context.value))]
)
},

Next, we mount the returned vTree to the real node.

let subTree = rootComponent.render(context)
mountElement(subTree, rootContainer)

The logic for mountElement is:

Create elements based on tags
Update properties
If the child node is a text node, create it directly; if it's an array, create recursively

export function mountComponent(vnode, container) {
const { tag, props, children } = vnode;
// tag
let ele = document.createElement(tag);
// props
for (const key in props) {
if (Object.hasOwnProperty.call(props, key)) {
const value = props[key];
ele.setAttribute(key, value);
}
}
/_ children 1. string 2. object
_/
if (typeof children === "string") {
const textNode = document.createTextNode(children);
ele.appendChild(textNode);
} else if (isArray(children)) {
children.forEach((vnode) => {
mountComponent(vnode, ele);
});
}
container.appendChild(ele);
}

function isArray(ele) {
return typeof ele.sort === "function";
}

Diff Algorithm

Apart from the initial mounting that generates all nodes, new updates are "patched" onto the old ones. This differential update process is handled by our diff algorithm.

We use a variable isMounted to separate the mounting and updating phases.

export default function createApp(rootComponent) {
  return {
    mount(rootContainer) {
      let context = rootComponent.setup()
      let isMounted = false
      let oldSubTree
      effectWatch(() => {
        if (!isMounted) {
          isMounted = true
          let subTree = (oldSubTree = rootComponent.render(context))
          mountElement(subTree, rootContainer)
        } else {
          let newSubTree = rootComponent.render(context)
          diff(newSubTree, oldSubTree)
          oldSubTree = newSubTree
        }
      })
    },
  }
}

Next, we handle the diff logic, addressing changes in tag, props, and children.

Since the diff process needs to operate on real DOM nodes, we need to attach them to the corresponding vNode after rendering.

export function mountElement(vNode, container) {
  // ...
  let ele = (vNode.el = document.createElement(tag))
  // ...
}

Handling tag changes using the native replaceWith method.

if (newTree.tag !== oldTree.tag) {
  oldTree.el.replaceWith(document.createElement(newTree.tag))
}

Handling props changes.

newTree.el = oldTree.el
// props, comparing two objects, each traversed to find differences
let { props: newProps } = newTree
let { props: oldProps } = oldTree
if (newProps && oldProps) {
  Object.keys(newProps).forEach((key) => {
    // Both exist, update node
    let newVal = newProps[key]
    if (Object.hasOwnProperty.call(oldProps, key)) {
      let oldVal = oldProps[key]
      if (newVal !== oldVal) {
        newTree.el.setAttribute(key, newVal)
      }
    } else {
      // Create if not in old
      newTree.el.setAttribute(key, newVal)
    }
  })
}
// Remove old props that no longer exist
if (oldProps) {
  Object.keys(oldProps).forEach((key) => {
    if (!Object.hasOwnProperty.call(newProps, key)) {
      newTree.el.removeAttribute(key)
    }
  })
}

For simplicity, the handling here is straightforward.

Handling children.

Handling children is relatively complex. To simplify, we differentiate based on the type of children.

let { children: oldChildren } = oldTree
let { children: newChildren } = newTree
if (typeof newChildren === 'string') {
  if (typeof oldChildren === 'string') {
    if (newChildren !== oldChildren) {
      newTree.el.textContent = newChildren
    }
  } else if (isArray(oldChildren)) {
    newTree.el.textContent = newChildren
  }
} else if (isArray(newChildren)) {
  if (typeof oldChildren === 'string') {
    newTree.el.textContent = ``
    mountElement(newTree, newTree.el)
  } else if (Array.isArray(oldChildren)) {
    // ...
  }
}

Next, we handle cases where both are arrays. For simplicity, we only process the length of nodes and do not handle node reordering within the same length.

// Naive solution: only handle node length, no reordering within the same length
const length = Math.min(newChildren.length, oldChildren.length)
// Update nodes of the same length
for (var index = 0; index < length; index++) {
  let newTree = newChildren[index]
  let oldTree = oldChildren[index]
  diff(newTree, oldTree)
}
// Create new nodes
if (newChildren.length > oldChildren.length) {
  for (let index = length; index < newChildren.length; index++) {
    const newVNode = newChildren[index]
    mountElement(newVNode, newTree.el)
  }
}
// Remove old nodes
if (oldChildren.length > newChildren.length) {
  for (let index = length; index < oldChildren.length; index++) {
    const vNode = oldChildren[index]
    vNode.el.remove() // Node removes itself
  }
}

This article was first published on my personal blog Frontend Development Notes. Due to my limited ability, there may be omissions in the article. Corrections are welcome.