Building a React-Like Library: Diffing

This is the last of four issues where we build a React-like library to learn how React works under the hood.

Photo by Marek Studzinski on Unsplash

Building a React-Like Library

The series contains the following articles:

• Render a static virtual DOM.

• Render a dynamic virtual DOM.

• Implement useState.

• Implement diffing. This article.

I like my articles to be easy to read and short. Yet, to go over this topic, I couldn’t find a shorter way without leaving out important implementation details. You might need longer than normal to go over all of it. Thanks for your understanding.

Video

If you prefer, I recorded a live-coding video explaining this article. Feel free to complement this article with it, or go and watch that instead.

Why Diffing

Manipulating the DOM is expensive. Therefore, the strategy we used in the previous article (PENDING LINK) is inefficient.

The part that is not efficient is the following:

parent.innerHTML = “”;

render(createApp(), parent);

This is a brute-force approach.

Emptying and rebuilding the whole app is not efficient.

What Is Diffing?

We must be smarter and perform only the necessary DOM manipulation when something changes.

Diffing means comparing the old virtual DOM with a new one. Then deciding and applying the necessary manipulations in the browser DOM.

Let’s implement diffing in our “React-like” library!

Diff vs. Render Functions

The diff function needs the previous virtual DOM to compare to the new one. Therefore, the signature is different than the render function.

// const render = (vnode, parent) => {

const diff = (prevVnode, vnode, parent) => {

In the first call, the diff performs the same as render because there is no previous virtual DOM yet. In that first render, the argument prevVnode is null.

As a first step, let’s rename render to diff, update the parameters, change the calls, and pass null as the first parameter.

// render(createApp(), parent);
diff(null, createApp(), parent);

// vnode.children.forEach(child => render(child, element));
vnode.children.forEach(child => diff(null, child, element));

// return render(nextVnode, parent);
return diff(null, nextVnode, parent);

Previous Virtual DOM

Where is the previous virtual DOM? The first time we called createApp, we created the first virtual DOM tree. Yet, we immediately rendered it and never stored it anywhere.

Let’s change that.

const renderApp = () => {
  useStateCalls = -1;
  const parent = document.getElementById("root");
  parent.innerHTML = "";
  const vDom = createApp(); // < - - - - -
  diff(null, vDom, parent);
};

Now, let’s store it as the previous virtual DOM after rendering it so we use it in the next call to renderApp.

let prevVDom = null; // < - - - - -
const renderApp = () => {
  useStateCalls = -1;
  const parent = document.getElementById("root");
  parent.innerHTML = "";
  const vDom = createApp();
  diff(prevVDom, vDom, parent); // < - - - - -
  prevVDom = vDom; // < - - - - -
};

Diff Setup

The first parameter of diff is either null (the first render) or a virtual DOM.

Therefore, let’s set up two branches inside the diff function.

const diff = (prevVnode, vnode, parent) => {
  if (prevVnode === null) {
    // same as render
  } else {
    // PENDING
  }
}

We keep the code of render in the first branch when prevVnode is null.

Do Not Reset App Parent

Now we broke our app.

That’s because the second time we call renderApp, we empty the parent parent.innerHTML = ""; but we never render anything inside it.

Diffing is about performing the minimum changes needed. We should not empty the parent.

const parent = document.getElementById("root");
// DO NOT reset parent < - - - - -
const vDom = createApp();
diff(prevVDom, vDom, parent);
prevVDom = vDom; 

The app is still not working, but at least is not resetting to a blank page after we click a button.

Implement Diffing

Here comes the tricky part, how do we compare two virtual DOMs and know exactly what changes to perform?

Find Out What Changed?

Many things might change: children are added and removed, text changes, new classes are added, old ones are removed, new listeners are set, etc.

We’ll focus on our Counter App. What changes? The text inside a DOM element.

Yet, to find the node that changed, we need to traverse a few children starting from the top:

Node Types

We divide the nodes into three different types.

• Nodes where the tag is a string: { tag: “div”, children: [...], attributes: {...} }.

• Nodes that are a string or number "This was built with createElement".

• Functional components { tag: <function>, children: [...], attributes: {...} }.

We need more branches and handle each node type separately:

const diff = (prevVnode, vnode, parent) => {
  if (prevVnode === null) {
    // same as render
  } else {
    // node is a string or number "This was build with createElement"
    // tag is a string { tag: div, children: [...], attributes: {...} }
    // functional components
  }
}

Diffing String or Number

We identify this type:

if (typeof vnode === "string" || typeof vnode === "number") {

Let’s assume that if the new node is text or number, the old one is also.

We want to compare texts:

// if they are different
if (vnode !== prevVnode) {
  // change the text
}

Yet, how do we change the element? Where is the HTML element?

In the initial render, we created a text node in the parent element.

if (typeof newVnode === "string" || typeof newVnode === "number") {
  return parent.appendChild(document.createTextNode(newVnode));
}

To find the HTML element to change, we iterate over the parent’s children and find the one that matches the previous text:

const selectedNode = Array.from(parent.childNodes).find((node) => node.textContent == prevVnode);

We change the content with the new value:

selectedNode.textContent = newVNode;

Diffing Functional Components

Identify the functional components:

if (typeof vnode.tag === "function") {

The first time we rendered it, we called the functional component and used a local variable for the result:

const nextVnode = vnode.tag(vnode.props);
return diff(null, nextVnode, parent);

We need this previous node (nextVnode) to compare it with the new one.

Let’s store the nextVnode in a new field of the virtual node:

const createElement = (tag, props, children ) => ({
  tag,
  props,
  children,
  currentNode: null, // < - - - - -
});

Let’s store the node in the field after creation:

const nextVnode = vnode.tag(vnode.props);
vnode.currentNode = nextVnode;
return diff(null, nextVnode, parent);

This way, we use it when we diff functional components, and we store the new node in the same field as well.

// in the branch where prevVnode is NOT null
if (typeof vnode.tag === "function") {
  const newVnode = vnode.tag(vnode.props);
  // keep reference of the node
  vnode.currentNode = newVnode;
  // pass the node of the previous one
  diff(prevVnode.currentNode, newVnode, parent);
}

Diffing Elements

Last but not least, we need to diff when tag is a string.

if (typeof vnode.tag === "string") {

Many things might change here. Yet, we assume that attributes don’t change, that the tag element is the same, and that the number of children doesn’t change. Only the children themselves might change.

Therefore, we only need to diff each child:

// in the branch where prevVnode is NOT null
if (typeof vnode.tag === "string") {
  if (vnode.children) {
    // assume that the number of children is the same
    vnode.children.forEach((child, index) => {
      const oldChild = prevVnode.children[index];
      diff(oldChild, child, ?);
    });
  }
}

What’s the parent of these new children? When we rendered the children in the first call, the parent was the current element we had just created:

const element = document.createElement(vnode.tag);
// ...
// we used `element` when rendering each child
vnode.children.forEach(child => diff(null, child, element));

This element already exists in the second and following calls. Where is it?

We never stored it anywhere. Therefore, it’s not accessible anymore in the following renders.

As we did with the functional components, we store the element in the node itself:

const createElement = (tag, props, children ) => ({
  tag,
  props,
  children,
  currentNode: null,
  element: null, // < - - - - -
});

When we create the element, we store it:

const element = document.createElement(vnode.tag);
// save the element in the vnode
vnode.element = element;

We also need to update the new node when we diff

vnode.element = prevVnode.element;

And now we use it when we diff the children:

vnode.children.forEach((child, index) => {
  const oldChild = prevVnode.children[index];
  diff(oldChild, child, vnode.element); // < - - - -
});

Let’s try it!

What’s happening? The app seems to be working fine on the first click, but then the button stops working.

Issue: Not Updating After “1”

This small bug confused me a lot. The source of this bug comes from Counter, and diffing elements; can you spot it?:

const Counter = () => {
  const [count, setCount] = useState(0);
  const increment = () => {
    setCount(count + 1);
  };

  return createElement("div", {}, [
    createElement("button", { onClick: increment }, ["+"]),
    createElement("h3", {}, [count]),
    createElement("button", {}, ["-"]),
  ]);
};

// inside diff function, prevVnode not null
if (typeof vnode.tag === "string") {
  // assume props are the same
  if (vnode.children) {
    // assume that the number of children is the same
    vnode.children.forEach((child, index) => {
      const oldChild = prevVnode.children[index];
      diff(oldChild, child, ?);
    });
  }
}

The second time we render Counter, we create a new increment function. In the first render, count is 0; therefore, the increment function performs “0 + 1”. In the second render, count is 1; therefore, the increment function performs “1 + 1”.

Yet, when we diff the elements, we assumed that the props were the same. It’s a wrong assumption.

The listener has changed. It’s a similar increment function but with different values.

The easiest way to solve this problem is to change the listeners in the diff function:

// inside `typeof vnode.tag === "string"`
if (vnode.props) {
  Object.keys(vnode.props).forEach(key => {
    const value = vnode.props[key];
    const prevValue = prevVnode.props[key];

    // reset event listeners
    if (key.startsWith("on")) {
      const event = key.slice(2).toLowerCase();
      vnode.element.removeEventListener(event, prevValue);
      vnode.element.addEventListener(event, value);
    }
  });
}

Let’s try again!

Now it works!

Recap

This was quite the ride; diffing is not a straightforward algorithm.

Take into account that we covered only a small part of what a real diffing algorithm covers. Yet, I hope you got the gist of the idea behind diffing.

Remember that I recorded a video where I live code the diffing algorithm explained here.

What did we change:

• Rename render to diff and change the signature of the function to expect the previous virtual DOM.

• We created two branches inside the diff function. When the previous virtual DOM is present and when not.

• We diffed each type of node separately.

• Diff when node is a string or number.

• Diff when node is a functional component.

• Diff when node tag is a string.

• We needed two more fields in our virtual node: element and currentNode.

The most important takeaway is that diffing is not magic, and it’s something any developer can do and understand. We just need time.

If you ever encounter problems between renders, I hope that understanding the nature of diffing helps you fix them faster.

That’s what this series is all about.

Understand frontend frameworks so that we become better software engineers.

Final Github Gist with our React-like library.

Thanks for reading and thanks to Bernat and Sebastià for reviewing this article 🙏