Reconciliation algorithm: Let's code a virtual DOM! #3

Reconciliation algorithm: Let's code a virtual DOM! #3

Learn how to keep virtual DOM in sync

Krzysztof Kałamarski's photo
Krzysztof Kałamarski
·May 2, 2022·

7 min read

Subscribe to my newsletter and never miss my upcoming articles

Table of contents

  • What are we going to implement
  • Figuring out what has changed
  • Wrapping up
  • What's next?

In the last two instalments of this series, we've developed a virtual dom that changes every time the state is mutated.

If you didn't read the previous articles you can find them here:

What are we going to implement

So far, our virtual DOM adds a new element to the DOM every time the state is changed. This is not how it should work - it should figure out which elements have changed, and replace them.

To do that, we need to take a look at the differences in the virtual trees.

After executing a view function with the new state, we can then compare the tree it produces with the previous iteration.

That way we will know exactly which DOM nodes need to be added, removed or replaced.

The starting code for this article can be found here:

Let's get started!

Figuring out what has changed

Adjusting render function

Each execution of the view function generates a tree-like structure that contains all information needed to render it to the DOM: type of node, a list of attributes and a list of children for each respective node.

To detect changes, we would need to compare all that information between the old tree and the updated tree.

In the first article from this series, we have actually created a diff function. It's located in the src/diff.ts file. Let's take a look at how it's implemented.

export const diff = (
  root: HTMLElement,
  oldNode: any,
  newNode: any,
  index: number = 0
) => {
  if (!oldNode) {
    root.appendChild(createElement(newNode));
  }
};

This function is being called every time a state is changed inside the store. Code for this can be found in the src/dom.ts file, in the render function:

export const render = (
  root: HTMLElement,
  { model, view, update }: Application<number>
) => {
  const store = new Store(model, update);

  store.subscribe((state) => {
    const rendered = view(state, store.dispatch.bind(store));

    setTimeout(() => {
      diff(root, null, rendered);
    });
  });
};

As you see, each time the state is changed, we call a diff function with a null as an old node. That's why it's adding a new element every time!

Let's change that - we will declare a new variable called current, and we will store there the latest rendered value returned by the view function.

export const render = (
  root: HTMLElement,
  { model, view, update }: Application<number>
) => {
  const store = new Store(model, update);
  let current: Element | null = null;

  store.subscribe((state) => {
    const rendered = view(state, store.dispatch.bind(store));

    setTimeout(() => {
      diff(root, current, rendered);
      current = rendered;
    });
  });
};

Now, if you take look at the result in the browser, you'll notice that it has stopped adding new elements to the DOM.

Zrzut ekranu 2022-05-2 o 22.53.40.png

We're making a progress!

Has a new node been added?

If we take a look back at our diff function, we will notice that this behaviour is correct - so far we have only implemented a case when an old node does not exist. Only then we should add the new node to the DOM.

if (!oldNode) {
  root.appendChild(createElement(newNode));
}

If it doesn't exist in the old tree and exists in the new one it means that it has been added to the DOM.

That's why we are calling the createElement function here.

This action can be visualized as the following diagram:

Zrzut ekranu 2022-05-2 o 23.05.35.png

Has a node been removed?

The next case we need to handle is when a node is removed from the DOM.

Let's imagine that an user deletes an entry in the list:

Zrzut ekranu 2022-05-2 o 23.19.04.png

In that case, an oldNode will exist, but there won't be any newNode - we need to remove it from the DOM:

if (!oldNode) {
  root.appendChild(createElement(newNode));
} else if (!newNode) {
  root.removeChild(root.childNodes[index]);
}

In the code above, we need to remove a correct child, that's why we need an index variable that's passed down in arguments of the diff function.

In the case from that diagram, it would be equal to 1, as we are removing the second children of the ul node.

Later in this post, we will see how can we set it.

Has the node been changed?

To check if the node has been changed we need to implement a new function that will compare the nodes from old and new trees.

It can be implemented like this:

const hasChanged = (node1: Element, node2: Element) => {
  if (typeof node1 === 'string' || typeof node2 === 'string') {
    return node1 !== node2;
  } else {
    return node1.type !== node2.type;
  }
};

If any of the nodes is just a string, we check if both nodes are equal. If they are, it means that nothing has changed.

If they're not strings, then we need to compare their types.

If the function returns true, we need to replace the old node with a new one. It can be done like that:

if (!oldNode) {
  root.appendChild(createElement(newNode));
} else if (!newNode) {
  root.removeChild(root.childNodes[index]);
} else if (hasChanged(oldNode, newNode)) {
  root.replaceChild(createElement(newNode), root.childNodes[index]);
}

We are literally combining both, removing the old node and adding a new one. DOM handles it by the replaceChild method.

What if nothing has changed?

The last case that we need to handle is when there is no change in the current node.

Even though the current node did not change, we need to go through all its children to see whether they did change.

This can be easily achieved by calling the diff function recursively on all its children.

if (!oldNode) {
  root.appendChild(createElement(newNode));
} else if (!newNode) {
  root.removeChild(root.childNodes[index]);
} else if (hasChanged(oldNode, newNode)) {
  root.replaceChild(createElement(newNode), root.childNodes[index]);
} else if (typeof newNode !== 'string' && typeof oldNode !== 'string') {
  const newLength = newNode.children.length;
  const oldLength = oldNode.children.length;

  for (let i = 0; i < newLength || i < oldLength; i++) {
    diff(
      root.childNodes[index] as HTMLElement,
      newNode.children[i],
      oldNode.children[i],
      i
    );
  }
}

Note that if a child was removed, the diff function would be called with newNode as undefined, whereas if a new child was added the diff function would be called with oldNode as `undefined.

That would of course remove or add a new node to the DOM.

The full code for the src/diff.ts file looks now like this:

import { Element } from './dom';

const createElement = (node: any) => {
  if (typeof node === 'string') {
    return document.createTextNode(node);
  }

  const el = document.createElement(node.type);
  node.children.map(createElement).forEach(el.appendChild.bind(el));

  return el;
};

const hasChanged = (node1: Element, node2: Element) => {
  if (typeof node1 === 'string' || typeof node2 === 'string') {
    return node1 !== node2;
  } else {
    return node1.type !== node2.type;
  }
};

export const diff = (
  root: HTMLElement,
  oldNode: Element | null,
  newNode: Element | null,
  index: number = 0
) => {
  if (!oldNode) {
    root.appendChild(createElement(newNode));
  } else if (!newNode) {
    root.removeChild(root.childNodes[index]);
  } else if (hasChanged(oldNode, newNode)) {
    root.replaceChild(createElement(newNode), root.childNodes[index]);
  } else if (typeof newNode !== 'string' && typeof oldNode !== 'string') {
    const newLength = newNode.children.length;
    const oldLength = oldNode.children.length;

    for (let i = 0; i < newLength || i < oldLength; i++) {
      diff(
        root.childNodes[index] as HTMLElement,
        newNode.children[i],
        oldNode.children[i],
        i
      );
    }
  }
};

Wrapping up

In less than 50 lines of code, we've implemented a fully functioning reconciliation algorithm for our virtual DOM.

Let's see how it works:

If we run the following code, it would increment the counter every second by one:

import { h, render } from './dom';

const app = document.querySelector<HTMLDivElement>('#app')!;

render(app, {
  model: 1,
  view(state, dispatch) {
    setTimeout(() => dispatch('increment'), 1000);

    return h('div', {}, [
      h('h1', {}, ['Hello']),
      h('p', {}, ['The value is: ', String(state)]),
    ]);
  },
  update(state, action) {
    switch (action) {
      case 'increment':
        return state + 1;
      default:
        return state;
    }
  },
});

And the result is:

gif.gif

If you inspect the page and take look into the DOM inspector, you will see that only the changed node is updated - the rest of the DOM stays the same.

Zrzut ekranu 2022-05-2 o 23.46.14.png

That's exactly what we wanted - state change will update only the relevant part of the UI.

What's next?

Even though our virtual dom gets in shape, there is still some work to be done.

In the next article, we will focus on registering event handlers and passing attributes to the DOM.

I hope that it was an interesting read for you - if so, consider subscribing to my newsletter to get notified when the next part is released.

You can access all the code from this post here:

 
Share this