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:

Create an initial virtual tree
Render this initial virtual tree into the DOM (by diffing it against an empty virtual DOM and applying those patches to the real DOM)
A user (you) submits a todo
A new virtual tree is created, one that contains the new todo but is otherwise the same as the previous virtual tree
Compare the new virtual tree with the old virtual tree, and find the differences (items that we need to: replace, add, or delete)
Apply those differences (aka patches) to the real DOM, only changing what needs to be changed (you can confirm this by opening up the dev tools and watching the DOM in the elements tab as you add todos)
Replace our old virtual tree reference with this new, updated virtual tree so the program knows about the latest virtual DOM representation
Start listening for more changes

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

Use simple objects
Use classes (eg VirtualNode, VirtualText, VirtualPatch)

createNode

Represent nodes using elm-like div representation (eg ['p', { class: 'inline' }, [ 'hello world' ]]); no ids
Represent nodes as simple objects, with ids (eg { elType: 'p', atts: { class: 'inline' }, children: [ 'hello world' ], id: 1 } )
Represent nodes as as either VirtualNode or VirtualText
Only give ids to nodes that need them
Give no nodes ids; instead, give each node a reference to their DOM el

render

Simply render the created element into DOM
Be a wrapper for all logic around diffing and patching, plus keep a reference to the latest tree

createElement

Return a string (eg root.innerHTML = createElement(vNode))
Return a DOM node (eg root.appendChild(createElement(vNode)))

diff

Store a reference to the target node
Store a path to target node
Return an object of patches with keys as indices of the parent node, and the values as patches
Create DOM elements while diffing, and save a reference to the element on each virtual node
Return an array of patches

patch

Apply patches while traversing vdom, and somehow find the corresponding element in the DOM (how, lol)
Apply patches using each virtual node's reference to its DOM element (no manual DOM walking)

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

Use JSX
Add more rigorous tests
Be more selective about what qualifies as a patch (eg if the first item in a list changes, but the rest don't, don't replace all the preceding nodes; just replace the one that changed)

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