DEV Community

Cover image for Dom Diffing Algorithm Implementation In Vanilla JavaScript
Joydeep Bhowmik
Joydeep Bhowmik

Posted on • Edited on

Dom Diffing Algorithm Implementation In Vanilla JavaScript

#javascript #react #webdev #tutorial

If you have used any SPA framework like React or Vue then you might be familiar with the term "Virtual DOM". Whenever route path or state changes in react instead of rendering the whole page react only renders the changes, and to accomplish this react uses a DOM diffing algorithm in which it compares the virtual DOM to the actual DOM. In this article I'm going to explain virtual DOM and show you how you can implement the DOM diffing algorithm.

What is DOM

DOM stands for document object model. Its a structured representation of HTML elements of a web page, where each element is a node object which contains some methods and properties.
You can write
console.log(document.body.children);
on a html document and inspect what node has which properties and methods

What is Virtual DOM?

The Virtual DOM is virtual representation of a UI that is kept in JavaScript memory.The virtual DOM is comparable to a blueprint. You make changes in virtual DOM then compare it to the actual DOM and apply the changes thus not re-rendering the whole UI .
Because all the comparison happens in JavaScript memory, its pretty fast.

Implementation

Before we go to the actual coding we should know about node,node types and childNodes.
Starting with node, this are object that represent html elements.
There are many types of node. To know the node type of an element you just have to
console.log(document.getElementById('#node').nodeType)

For this project we just have to know about three main types 1,3 and 8

  • nodeTye 1 means its a html tag
  • nodeType 3 means its a text node
  • nopdeType 8 means its a comment

ChildNodes is an array of children of a node.
you can get the childNodes of an element by simply doing
console.log(document.getElementById('#node').childNodes).
But wait, you can do the same by writing console.log(document.getElementById('#node').children), So, whats the difference?
Both are pretty much same except you will not get text and comment nodes in node.children method.

Let' create a function which will return the tag name if the node is type of a tag ,otherwise the nodeType of the node

    getnodeType(node) {
        if(node.nodeType==1) return node.tagName.toLowerCase();
        else return node.nodeType;
    };
Enter fullscreen mode Exit fullscreen mode

Now lets get started by creating an html div with some children element.

    <div id="node">
        <h1>Hello</h1>
        <p>This is a page</p>
    </div>
Enter fullscreen mode Exit fullscreen mode

This node element has two childNodes h1, p and each of them having a text node as child Node

Now if we want it to replace the childNodes of <div id="node"></div> with

    <h1 style="color:green">Hello</h1>
    <p>This is a page</p>
    <p>some more text</p>
Enter fullscreen mode Exit fullscreen mode

we just need to add style attribute to h1 tag and append <p>some more text</p>.
lets check how can we perform this using DOM diffing algorithm.
First , we need a function that converts our template to actual html elements.
We can use inbuild DOMParser() class to achieve that.

function parseHTML(str) {
    let parser=new DOMParser();
    let doc = parser.parseFromString(str, 'text/html');
    return doc.body;  
}
var vdom=parseHTML(`
    <h1 style="color:green">Hello</h1>
    <p>This is a page</p>
    <p>some more text</p>
`)
Enter fullscreen mode Exit fullscreen mode

if you do console.log(vdom) you can see it returns a body element containing our template as html.

vdom

But if you write console.log(vdom.childNodes) it returns

nodeList

you can see it contains some unnecessary text nodes which contains only new lines and spaces , which might cause problems while diffing , so we need to remove that.
Here's how we can remove this.

function clean(node)
{
  for(var n = 0; n < node.childNodes.length; n ++)
  {
    var child = node.childNodes[n];
    if
    (
      child.nodeType === 8 
      || 
      (child.nodeType === 3 && !/\S/.test(child.nodeValue) && child.nodeValue.includes('\n'))
    )
    {
      node.removeChild(child);
      n --;
    }
    else if(child.nodeType === 1)
    {
      clean(child);
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

Basically we are removing All textNodes that contains only new lines. You can read more about it from
Here.

Now combining this with our parseHTML function

function parseHTML(str) {
    let parser=new DOMParser();
    let doc = parser.parseFromString(str, 'text/html');
    clean(doc.body);
    return doc.body;  
}
Enter fullscreen mode Exit fullscreen mode

So this is our VDOM.

vdom

And

var dom=document.getElementById('node');
Enter fullscreen mode Exit fullscreen mode

this is our dom.

dom

Ok , we can now write our actual diffing function

function diff(vdom,dom){
    //if dom has no childs then append the childs from vdom
    if (dom.hasChildNodes() == false && vdom.hasChildNodes()==true) {
           for (var i = 0; i < vdom.childNodes.length; i++) {
           //appending the clone node
               dom.append(vdom.childNodes[i].cloneNode(true)); 
           }
       }
}
Enter fullscreen mode Exit fullscreen mode

Firstly we check if the DOM element have any child nodes, if it doesn't the we append all childNodes from VDOM to our DOM. While moving childNodes from VDOM to DOM we need to make sure we make clone of the node as we don't want to delete it from our VDOM.

else{
//if both nodes are equal then no need to compare farther
if(vdom.isEqualNode(dom)) return;
    //if dom has extra child
    if (dom.childNodes.length > vdom.childNodes.length) {
        let count = dom.childNodes.length -vdom.childNodes.length;
        if (count > 0) {
            for (; count > 0; count--) {
                dom.childNodes[dom.childNodes.length  - count].remove();
                }
            }
        }
    }
Enter fullscreen mode Exit fullscreen mode

if both nodes are equal then we stop else we check if DOM has extra nodes then we remove extra nodes from the bottom.

Now we compare all childNodes of VDOM and DOM

//now comparing all childs
   for (var i = 0; i < vdom.childNodes.length; i++) {
        //if the node is not present in dom append it
         if(dom.childNodes[i]==undefined){
             dom.append(vdom.childNodes[i].cloneNode(true));
          }
       }
Enter fullscreen mode Exit fullscreen mode

if the node is missing from DOM the we append it to the DOM.

        //now comparing all childs
    for (var i = 0; i < vdom.childNodes.length; i++) {
        //if the node is not present in dom append it
        if(dom.childNodes[i]==undefined){
             dom.append(vdom.childNodes[i].cloneNode(true));
         }else if(getnodeType(vdom.childNodes[i]) == getnodeType(dom.childNodes[i])){
         //if same node type

         }else{
         //else replace
            dom.childNodes[i].replaceWith(vdom.childNodes[i].cloneNode(true));
           }
        }
Enter fullscreen mode Exit fullscreen mode

else we check if both node have same nodeType ,if not then we replace it with the VDOM child node.

//if same node type
//if the nodeType is text
if (vdom.childNodes[i].nodeType == '3') {
//we check if the text content is same
    if (vdom.childNodes[i].textContent != dom.childNodes[i].textContent) {
    //replace the text content
    dom.childNodes[i].textContent = vdom.childNodes[i].textContent;
     } 

}else{
patchAttributes(vdom.childNodes[i], dom.childNodes[i])

}
Enter fullscreen mode Exit fullscreen mode

Now for same node type , if its a text node then we check if textContent of both node are same , if not then we replace it with VDOM child node's textContent.

if its not a text node then we just need to update the attributes .
for this first we have to index the attributes of both virtual and actual node

function attrbutesIndex(el) {
        var attributes = {};
        if (el.attributes == undefined) return attributes;
        for (var i = 0, atts = el.attributes, n = atts.length; i < n; i++) {
            attributes[atts[i].name] = atts[i].value;
        }
        return attributes;
    }
Enter fullscreen mode Exit fullscreen mode

which will return an object with all attributes of a node ,like

{id: 'someid', style: 'color:green'}

now for patching attributes

function patchAttributes(vdom, dom) {
        let vdomAttributes = attrbutesIndex(vdom);
        let domAttributes = attrbutesIndex(dom);
        if(vdomAttributes==domAttributes) return;
        Object.keys(vdomAttributes).forEach((key,i) => {
            //if the attribute is not present in dom then add it
            if(!dom.getAttribute(key)){
                dom.setAttribute(key,vdomAttributes[key]);
            }//if the atrtribute is present than compare it
            else if(dom.getAttribute(key)){
                if(vdomAttributes[key]!=domAttributes[key]){
                    dom.setAttribute(key,vdomAttributes[key]);
                }  
            }
          });
        Object.keys(domAttributes).forEach((key,i) => {
            //if the attribute is not present in vdom than remove it
            if(!vdom.getAttribute(key)){
                dom.removeAttribute(key);
            }
        });
    }
Enter fullscreen mode Exit fullscreen mode

if the attribute not present in the DOM child node we simply add it and if the attribute is present we update it,but if the attribute is not present in VDOM child node we remove it.
and we repeat the process for each child node;
that's pretty much it.
Lets put it all together

function getnodeType(node) {
        if(node.nodeType==1) return node.tagName.toLowerCase();
        else return node.nodeType;
    };
function clean(node) {
    for (var n = 0; n < node.childNodes.length; n++) {
        var child = node.childNodes[n];
        if (
            child.nodeType === 8 ||
            (child.nodeType === 3 && !/\S/.test(child.nodeValue) && child.nodeValue.includes('\n'))
        ) {
            node.removeChild(child);
            n--;
        } else if (child.nodeType === 1) {
            clean(child);
        }
    }
}

function parseHTML(str) {
    let parser = new DOMParser();
    let doc = parser.parseFromString(str, 'text/html');
    clean(doc.body);
    return doc.body;
}

function attrbutesIndex(el) {
    var attributes = {};
    if (el.attributes == undefined) return attributes;
    for (var i = 0, atts = el.attributes, n = atts.length; i < n; i++) {
        attributes[atts[i].name] = atts[i].value;
    }
    return attributes;
}
function patchAttributes(vdom, dom) {
    let vdomAttributes = attrbutesIndex(vdom);
    let domAttributes = attrbutesIndex(dom);
    if (vdomAttributes == domAttributes) return;
    Object.keys(vdomAttributes).forEach((key, i) => {
        //if the attribute is not present in dom then add it
        if (!dom.getAttribute(key)) {
            dom.setAttribute(key, vdomAttributes[key]);
        } //if the atrtribute is present than compare it
        else if (dom.getAttribute(key)) {
            if (vdomAttributes[key] != domAttributes[key]) {
                dom.setAttribute(key, vdomAttributes[key]);
            }
        }
    });
    Object.keys(domAttributes).forEach((key, i) => {
        //if the attribute is not present in vdom than remove it
        if (!vdom.getAttribute(key)) {
            dom.removeAttribute(key);
        }
    });
}

function diff(vdom, dom) {
    //if dom has no childs then append the childs from vdom
    if (dom.hasChildNodes() == false && vdom.hasChildNodes() == true) {
        for (var i = 0; i < vdom.childNodes.length; i++) {
            //appending
            dom.append(vdom.childNodes[i].cloneNode(true));
        }
    } else {
//if both nodes are equal then no need to compare farther
if(vdom.isEqualNode(dom)) return;
        //if dom has extra child
        if (dom.childNodes.length > vdom.childNodes.length) {
            let count = dom.childNodes.length - vdom.childNodes.length;
            if (count > 0) {
                for (; count > 0; count--) {
                    dom.childNodes[dom.childNodes.length - count].remove();
                }
            }
        }
        //now comparing all childs
        for (var i = 0; i < vdom.childNodes.length; i++) {
            //if the node is not present in dom append it
            if (dom.childNodes[i] == undefined) {
                dom.append(vdom.childNodes[i].cloneNode(true));
                // console.log("appenidng",vdom.childNodes[i])
            } else if (getnodeType(vdom.childNodes[i]) == getnodeType(dom.childNodes[i])) {
                //if same node type
                //if the nodeType is text
                if (vdom.childNodes[i].nodeType == 3) {
                    //we check if the text content is not same
                    if (vdom.childNodes[i].textContent != dom.childNodes[i].textContent) {
                        //replace the text content
                        dom.childNodes[i].textContent = vdom.childNodes[i].textContent;
                    } 
                }else {
                        patchAttributes(vdom.childNodes[i], dom.childNodes[i])
                    }
            } else {
                //replace
                dom.childNodes[i].replaceWith(vdom.childNodes[i].cloneNode(true));
            }
            if(vdom.childNodes[i].nodeType != 3){
                diff(vdom.childNodes[i], dom.childNodes[i])
            }
        }
    }
}
let vdom = parseHTML(`
    <h1 style="color:green">Hello</h1>
    <p>This is a page</p>
    <p>some more text</p>`);
let dom = document.getElementById('node');
clean(dom);
console.log(vdom)
document.querySelector('button').addEventListener('click',function(){

    diff(vdom,dom);
})
Enter fullscreen mode Exit fullscreen mode

The result

The final result

IF you are interested in this type of posts please check out my
blog

Read Next Adding keys to our DOM diffing algorithm

Top comments (12)

Collapse
 
lexlohr profile image
Alex Lohr •

Removing text nodes containing all spaces means that the following markup:

<p>this will <em>look</em> <strong>wrong</strong>
Enter fullscreen mode Exit fullscreen mode

will resolve to

this will lookwrong. There are a few edge cases around space in JSX.

Collapse
 
joydeep-bhowmik profile image
Joydeep Bhowmik • • Edited

Thank you for pointing out. I will condition this to not remove those spaces, as soon as I'm free I'm going to fix this . I will let you know. As for a quick solution html space character will do the thing for now

Collapse
 
lexlohr profile image
Alex Lohr •

A JSX compiler is more difficult than it should be, given the specs. Good luck to you.

Thread Thread
 
joydeep-bhowmik profile image
Joydeep Bhowmik • • Edited

I have fixed this by conditioning it to remove only textNode that contains just newlines and spaces. Thank you very much for noticing the issue.

Thread Thread
 
rishabhkunwar11 profile image
Rishabh Kunwar •

hey Joy, great article so just what was this issue and how you fixed it like is the blog updated with the fix of this issue and if yes can you please explain what the issue was and how it was solved coz i am also confused with extra text nodes added by Element.childNodes and it may break the code if not handled

Thread Thread
 
joydeep-bhowmik profile image
Joydeep Bhowmik • • Edited

Thank you for your comment Rishabh.

The issue was that the code was unintentionally removing text nodes that contained only spaces. The goal was to remove unnecessary new lines from the parsed HTML while keeping important space intact.

and this was the solution that was added .

function clean(node){
...
if
    (
      child.nodeType === 8 
      || 
      (child.nodeType === 3 && !/\S/.test(child.nodeValue) && child.nodeValue.includes('\n'))
    )
    {
      node.removeChild(child);
      n --;
    }
...
}
Enter fullscreen mode Exit fullscreen mode

Let's break down the condition step by step:

child.nodeType === 3: nodeType is a property of a DOM node that represents the type of the node. The value 3 corresponds to a text node. So, this part of the condition checks if the child node is a text node.

!/\S/.test(child.nodeValue): \S is a regular expression pattern that matches any non-whitespace character. The test() method checks if the child.nodeValue (the text content of the node) does not contain any non-whitespace characters. In other words, it checks if the text node is empty or contains only whitespace characters.

child.nodeValue.includes('\n'): This part checks if the child.nodeValue (the text content of the node) includes a newline character ('\n'). It checks if the text node contains a line break.

Putting it all together, the condition checks if the child node is a text node, is empty or contains only whitespace characters, and includes a line break. This condition is typically used to identify and handle empty text nodes that might contain only whitespace or line breaks, ensuring they are not treated as significant content in the dom.

Collapse
 
joelbonetr profile image
JoelBonetR 🥇 •

10/10 post, kudos! 😁

Collapse
 
joydeep-bhowmik profile image
Joydeep Bhowmik •

Thanks 😊

Collapse
 
artydev profile image
artydev •

Great thank you

Collapse
 
joydeep-bhowmik profile image
Joydeep Bhowmik •

Thank you for your feedback ☺️

Collapse
 
eerk profile image
eerk • • Edited

This is a great explanation. My main question remains, will adding this virtual dom diffing code to my project actually make the DOM update faster? How can we measure this?

Collapse
 
joydeep-bhowmik profile image
Joydeep Bhowmik • • Edited

Thanks for your comment.

DOM diffing is not faster than simply getting one element via getElementById and changing it. But If you think of large number of elements or a complex tree then changing some part of that tree rather than recreating the whole tree is definitely faster. Think of a clock application, for everytime the clock updates instead of changing the whole body we can just change a small textNode(representing the time).The less we change the real DOM, the better . But for small changes the innerHTML can be faster .
However the virtual DOM may not be perfect for your project . You can look into this (by svelte ) article to know why.

For the second question though it's not the ideal solution but you can try this to measure performance of your JavaScript code

console.time('total');
//your code
console.timeEnd('total');
Enter fullscreen mode Exit fullscreen mode

I recommend you to try svelte for your project . it complies everything down to pure minified JS and doesn't require any virtual DOM, doesn't get faster than this

View full discussion (12 comments)

Read next

valeriavg profile image

Day 7: Your input is valid 🖐️

Valeria -

gauravadhikari1997 profile image

How to customize Strapi Dashboard / Home Page: The Right Way

Gaurav Adhikari -

peterdanwan profile image

Coming Full Circle: It starts and ends with Git and GitHub

Peter Wan -

jeferson0993 profile image

Why Monorepo Projects Sucks: Performance Considerations with Nx

Jeferson F Silva -