Learn JavaScript by building a UI framework: Part 6 - Intro to Virtual DOM Algorithms 
Tags: html, javascript, algorithm, frontend
Published: 2020-06-10 04:17:31

---
title: Learn JavaScript by building a UI framework: Part 6 - Intro to Virtual DOM Algorithms 
published: true
description: An answer to the question - how do virtual DOM algorithms work?
tags: html, javascript, algorithm, frontend
cover_image: https://dev-to-uploads.s3.amazonaws.com/i/md4qi3uolh9dmwhltfd9.png
---

*This article is the 6th in a series of deep dives into JavaScript. You can view previous articles by visiting the [Github repository](https://github.com/CarlMungazi/aprender-js#what-is-this) 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](https://dev.to/carlmungazi/learn-javascript-by-building-a-ui-framework-part-5-adding-events-to-dom-elements-3kod) 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? 

```js
{ // 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](https://github.com/facebook/react/issues/10703) on the React repository, for instance, is a detailed technical discussion about the matter. There are [many](https://github.com/jorgebucaran/superfine) [virtual](https://github.com/Matt-Esch/virtual-dom) [DOM](https://github.com/snabbdom/snabbdom) [implementations](https://github.com/zv/picodom) out there and to construct our own we will look to [simple-virtual-dom](https://github.com/livoras/simple-virtual-dom) for inspiration.

### So...what changed?

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

```js
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`: 

```js
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: 

```js
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:

```js
{
  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:

```js
{
  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](https://carlmungazi.com/journey-reactdom-render/).

We will begin applying our changes with these two functions:

```js
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.

```js
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:

```js
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.