Recreating a Virtual DOM, Part 2

A few weeks ago, I wrote about the process of recreating a virtual DOM. Since then I’ve made a lot of changes and progress that I’d like to share, or at the very least, log for myself.

First, let’s take a look at an example of this virtual DOM in action! Below is a simple todo list generator I made using my virtual DOM.

demo source code here

How it works

On a high level, here's what's happening in this demo:

Let's look closer at some of these key parts.

1. Create virtual DOM (vDOM)

Create a vDOM that has one root node and many child nodes. This is our original DOM representation.

const vDom = createNode('div', { }, [
  createNode('form', { }, [
    createNode('label', { }, [ 'add a todo' ]),
    createNode('input', {
      type: 'text',
      id: 'text'
    }, [ '' ]),
    createNode('input', {
      type: 'submit',
      value: 'save todo',
      onClick: saveTodo
    }, [ '' ])
  ]),
  createNode('div', { }, [ 'todos' ]),
  createNode('ul', { }, mapTodos(JSON.parse(localStorage.todos)))
]);

createNode takes three things: an element type, an object of HTML attributes and/or event listeners, and an array of children. It returns a VirtualNode whose children are either other VirtualNodes or, if the child is a string, a VirtualText node.

2. Call render

On a high level, render takes a vDOM and the DOM root in which to render the vDOM, and then performs a lot of the logic we discussed above.

// keep track of the latest vDOM
let tree = new VirtualNode('', {}, []);

const render = (vRoot, domRoot) => {
  // add a reference to the root DOM element to the tree. this part will only happen on the first render
  if (!tree.$el) {
    tree.$el = domRoot;
  }
  // find all differences between the old tree and the new one
  let patches = diff(tree, vRoot)
  // apply all these patches
  patch(domRoot, patches)
  // add a root node to the new tree
  let newTree = new VirtualNode('', {}, [vRoot]);
  // save a reference to the root DOM element to the new tree
  newTree.$el = domRoot;
  // replace the old with the new
  tree = newTree;

  return tree;
}

Let's look a little closer at diff and patch, as these are two key parts of a functioning virtual DOM.

i. diff between the old vDOM and the new vDOM

diff takes two vDOMs and finds all differences (or patches) between these two trees. It returns an array of patches (VirtualPatch) that have a type (replace, add, or delete), a patch node, a parent node, and a replace target (if the type is replace).

The algorithm is pretty long so I won't show it all here, but if you want to take a look you can see it on github. On a high level (and in pseudo-code!), this is what happens:

const diff = (oldTree, newTree) => {
  // kick off walking both trees, while keeping track of the parent node
  return walk(oldTree.children[0], newTree, oldTree);
};

const walk = (oldTree, newTree, parentNode) => {
  if (oldTree === newTree) {
    return;
  }

  if (!oldTree) {
    // patch type: ADD
    return [new VirtualPatch(newTree, parentNode, 'ADD')];
  } else if (!newTree) {
    // patch type: DEL
    return [new VirtualPatch(oldTree, parentNode, 'DEL')];
  } else if (oldTree !== newTree) {
    // patch type: REPL
    return [new VirtualPatch(newTree, parentNode, 'REPL', oldTree)];
  } else {
    // check children for patches
    const maxChildren = Math.max(oldTree.children.length, newTree.children.length);
    let childPatchesArray = [];

    for (let i = 0; i <= maxChildren; i++) {
      const oldTreeChild = oldTree.children[i];
      const newTreeChild = newTree.children[i];
      const childPatch = walk(oldTreeChild, newTreeChild, oldTree);
      if (childPatch) {
        childPatchesArray = childPatchesArray.concat(childPatch);
      }
    }
    return childPatchesArray;
  }
};

ii. patch those differences onto the DOM

patch takes the root DOM node and the array of patches (provided to us by the diff algorithm), finds the DOM nodes that need patches applied, and applies them. This is when the DOM actually gets updated.

const patch = (domNode, patches) => {
  // need to reverse patches so they get applied in order
  patches.reverse().forEach(applyPatch);

  return domNode;
};

const applyPatch = ({ patchNode, parentNode, type, replTarget }) => {
  if (type === 'ADD') {
    parentNode.$el.appendChild(patchNode.$el);
  } else if (type === 'DEL') {
    parentNode.$el.removeChild(
      $patchEl
    );
  } else if (type === 'REPL') {
    parentNode.$el.replaceChild(
      patchNode.$el,
      replTarget.$el
    );
  }
};

Various approaches I took

I took a lot of different approaches to get to this current implementation. These are listed in chronological order of implementation (so, the last note is the current implementation). As I'm sure you can imagine, if an implementation was abandoned, it was abandoned because I hit a problem with that implementation. Obstacles drive creativity! (If you have any questions about why an approach was abandoned, shoot me an email / tweet and we can talk about it.)

General things createNode render createElement diff patch

Other implementations

Other libraries implement the virtual DOM differently. Here are a few other implementations that I looked at while making my own virutal DOM in an attempt to understand where to get started and how others were approaching the problem.

Moving forward

There are obviously lots of things I could do to improve this virtual DOM implementation, a few being...

In the meantime, I built a thing! And I'm pretty proud of it. ;)

Thanks to Nathan who was incredibly helpful while working on this project, and to Vaibhav and Harold for their help editing.

01 Nov 2016