Learn JavaScript by building a UI framework: Part 6 - Intro to Virtual DOM Algorithms

This article is the 6th in a series of deep dives into JavaScript. You can view previous articles by visiting the Github repository associated with this project.

This series does not comprehensively cover every JavaScript feature. Instead, features are covered as they crop up in solutions to various problems. Also, every post is based on tutorials and open source libraries produced by other developers, so like you, I too am also learning new things with each article.

In the last article we extended Aprender's functionality by adding events to DOM elements. In this post, we will take the first step in tackling the meatiest part of a UI framework - dynamically changing DOM elements.

As always, we will begin with some example code. Given the two objects below which represent a UI, how do we change from the old to the new?

{ // old dom
  type: "div",
  attrs: {},
  children: [
    "Search",
    {
      type: "p",
      attrs: {},
      children: []
    }
  ]
}

{ // new dom
  type: "div",
  attrs: {},
  children: [
    "No Search",
    {
      type: "span",
      attrs: {},
      children: []
    }
  ]
}

At the heart of any UI framework (or secret sauce, if you like) is the way changes are detected and made. In a typical application, the underlying framework devotes a lot of time to figuring out what changed, how it changed and how the change needs to be applied. This issue on the React repository, for instance, is a detailed technical discussion about the matter. There are many virtual DOM implementations out there and to construct our own we will look to simple-virtual-dom for inspiration.

So...what changed?

The "what changed?" part of the implementation begins with the following function:

function diff(oldTree, newTree) {
  const patches = {};
  const index = 0;

  performDiff(oldTree, newTree, patches, index)

  return patches;
}

The arguments oldTree and newTree are object representations of the UI - the old state and the new state. In our case, we are changing the text from "Search" to "No Search" and the paragraph element to a span element. The patches object stores the differences between both states and it will be populated when we find the changes using performDiff. We will be making recursive calls as part of the diffing process so index acts as a counter to keep track of the current diff iteration. Finally, we return the patches object. It will be used later to make the changes. Let us look at performDiff:

function performDiff(oldTree, newTree, patches, index) {
  const currentPatch = [];

  if (newTree === undefined) {
    // we do nothing here because the final else statement will deal with it
  } else if (typeof oldTree === 'string' && typeof newTree === 'string') {  
    if (oldTree !== newTree) {
      currentPatch.push({
        type: 'TEXT',
        content: newTree
      })
    }
  } else if (oldTree.type === newTree.type) {
    diffChildren(oldTree.children, newTree.children, patches, index)
  } else {
    currentPatch.push({
      type: 'REPLACE',
      node: newTree
    })
  }

  if (currentPatch.length) {
    patches[index] = currentPatch
  }
}

performDiff is called recursively when we diff through any children, so currentPatch holds the changes belonging to the current iteration. The bulk of this function's work is done by a series of if statements which stem from the following questions:

Do we have a new DOM tree/element to diff against?

If we do not, we do nothing because the else clause of our if statement will handle that.

Are we comparing text nodes?

If we are dealing with text nodes, we will only make changes if the text is different. This change is recorded via an object that holds information about the type of change and the content related to that change.

Do we need to compare the children?

This is where the recursive fun begins. The diffChildren function is:

function diffChildren(oldChildren, newChildren, patches, index) {
  oldChildren.forEach((oldChild, idx) => {
    index++
    performDiff(oldChild, newChildren[idx], patches, index)
  })
}

It is very basic. Other frameworks shine here because they have to consider a host of issues. For instance, if none of the children have changed, is there any way of skipping this call? What is the most efficient way of comparing the child elements?

Are we comparing different elements?

If we are diffing two completely different DOM elements, the simplest thing to do is replace the old one with the new.

The algorithms of most UI frameworks can be boiled down to a similar list of questions.

In our case, the example code will go down the child comparison route, so let us walk through that:

First, diffChildren receives an array of children from the elements we are comparing. For each child, it recursively calls performDiff. However, before doing so it increments the index counter. In our example it goes from 0 to 1.

We call performDiff with the arguments "Search" and "No Search" as our comparison elements. As we are comparing text nodes, we create this object:

{
  type: "TEXT",
  content: "No Search"
}

and store it in the currentPatch array that is initialised whenever performDiff is invoked. This array keeps track of any changes that need to be made and if there are, at the end of the function they are assigned to the patches object with index being used as the key.

We repeat this process for the second child and once performDiff has completed its work, it leaves us with the following object:

{
  1: [
    {
      type: "TEXT",
      content: "No Search"
    }
  ],
  2: [
    {
      type: "REPLACE",
      node: {
        type: "span",
        attrs: {},
        children: []
      }
    }
  ]
}

This object, returned by the diff function, represents the changes we want to make to our UI. You can think of this as the first phase of our update process. In the second phase we will apply these changes to the DOM. This two-step process is similar to how React does things.

We will begin applying our changes with these two functions:

function patch(rootDomNode, patches) {
  const index = 0;
  performPatches(rootDomNode, patches, index)
}

function performPatches(node, patches, index) {
  const currentPatches = patches[index];

  if (node.childNodes) {
    node.childNodes.forEach(node => {
      index++
      performPatches(node, patches, index)
    });
  }

  if (currentPatches) {
    applyPatches(node, currentPatches)
  }
}

The workflow here should be familiar. patch takes the DOM element which is being updated and then calls performPatches with the changes and a counter. In performPatches we first perform any changes on child elements before making changes on the target element.

function applyPatches(node, currentPatches) {
  currentPatches.forEach(patch => {
    switch (patch.type) {
      case 'TEXT': {
        if (node.textContent) {
          node.textContent = patch.content
        }
        break;
      }
      case 'REPLACE': {
        const newNode = render(patch.node);
        node.parentNode.replaceChild(newNode, node);
        break;
      }
    }
  })
}

The humble switch case statement is at the core of the second phase of our update process. When replacing elements, we call upon Aprender's render function to create the DOM element for us.

And that is it! With the diff and patch functions we can now update DOM elements. If we were to write this as a proper application, it would be something like:

const aprender = require('aprender');

const oldTree = aprender.createElement('div', { 
    children: ['Search', aprender.createElement('p')] 
  }
);

const newTree = aprender.createElement('div', { 
  children: ['No Search', aprender.createElement('span')] 
  }
);

const root = aprender.render(oldTree)
aprender.mount(root, document.getElementById('app'))

const diff = aprender.diff(oldTree, newTree);

setTimeout(() => {
  aprender.patch(root, diff);
}, 5000)

 Summary

Our algorithm is nothing more than a series of conditional checks. If you look at the heart of an UI framwork's update mechanism, you will find the same. However, our implementation is still missing a fundamental piece - the ability to perform updates automatically and in response to data changes. We have to use setTimeout to trigger the change detection process. We will fix that in the next post.