DEV Community

Cover image for Adding keys to our DOM diffing algorithm
Joydeep Bhowmik
Joydeep Bhowmik

Posted on • Edited on

Adding keys to our DOM diffing algorithm

In my previous post about DOM diffing algorithm we learned to create our own virtual DOM and got to know how DOM diffing actually works. In this post we will learn about how keys works and how we can add this feature to our virtual DOM . before we start the actual coding we must know why keys are necessary and whats the concept behind it.

Importance of using keys

Keys tell our diffing algorithm to identify which items needs to be changed, or add, or remove.
Without keys our algorithm will push update to a node even if we could achieve the same by simple moving the node. Let me explain this with an example

|-------DOM-------------|---------VDOM--------|
|-----------------------|---------------------|
| <Li val="A">          | <Li val="A">        | 
| <Li val="B">          | <Li val="B">        | 
|                       | <Li val="C">        | 
|-----------------------|---------------------|
Enter fullscreen mode Exit fullscreen mode

When we compare this DOM with the VDOM our algorithm just append the last child to our DOM. That's not a problem at all . The problems occurs when we face situation like this.

|-------DOM-------------|---------VDOM--------|
|-----------------------|---------------------|
| <Li val="A">          | <Li val="c">        | 
| <Li val="B">          | <Li val="A">        | 
|                       | <Li val="B">        | 
|-----------------------|---------------------|
Enter fullscreen mode Exit fullscreen mode

In this case our algorithm will append the last node to our DOM and update the first node. But we could have just simply avoided this by prepending the last node to the DOM , and this would make the update much faster. That's where the keys come in.

|---------DOM-----------|-------VDOM----------|--------------------------|
| <Li key=1 val="A">    | <Li key=3 val="C">  | Moved from bottom to top |
| <Li key=2 val="B">    | <Li key=2 val="A">  | None                     |
|                       | <Li key=1 val="B">  | None                     |
|-----------------------|---------------------|--------------------------|
Enter fullscreen mode Exit fullscreen mode

With the help of keys now we can tell our algorithm that no need to change everything just add the new node to the top.

Implementation

The implementation starts by simply adding the key attributes to our nodes, however the key attributes never get passed to DOM, but stays as a property of the node object.
Let's modify our previous codes to add key props. starting with clean function.

function clean(node) {
    for (let n = 0; n < node.childNodes.length; n++) {
        let 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) {
            if(child.hasAttribute('key')){
                let key=child.getAttribute('key');
                //adding the key property to the node object
                child.key=key;
                //removing the keys
                child.removeAttribute('key');
            }
            clean(child);
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

As our clean function iterates through all children we check if the node has the key attribute , if the case is true then we get the attribute value and set a key property with the value, then we remove the key attribute.

Now All of our nodes has the key property. Lets create our patchKeys function

function patchKeys(vdom,dom){
        //remove unmatched keys from dom
        for(let i=0;i<dom.children.length;i++){
            let dnode=dom.children[i];
            let key=dnode.key;
            if(key){
                if(!hasTheKey(vdom,key)){
                    dnode.remove();
                }
            }
        }
        //adding keys to dom
        for(let i=0;i<vdom.children.length;i++){
            let  vnode=vdom.children[i];
            let key=vnode.key;
            if(key){
                if(!hasTheKey(dom,key)){
                    //if key is not present in dom then add it
                    //get the index of current node
                    let nthIndex=[].indexOf.call(vnode.parentNode.children, vnode);
                    if(dom.children[nthIndex]){
                        //adding before the same indexed node of dom
                        dom.children[nthIndex].before(vnode.cloneNode(true))
                    }else{
                        dom.append(vnode.cloneNode(true))
                    }
                }
            }
        }
    }
Enter fullscreen mode Exit fullscreen mode

In the patchKey function we iterate through the DOM and VDOM children. For DOM children if the key is not present in VDOM we remove the node from DOM and for VDOM children if the key is not present the DOM then we add it to the DOM, While adding a node to The DOM we need to maintain the ordering, for this we get the index of the VNODE and add it before the same indexed child of DOM, if the child is not present in DOM we just append the VNODE.

The hasKey function helps us to check if the key is present in the respective DOM.

function hasTheKey(dom,key){
    let keymatched=false;
    for(let i=0;i<dom.children.length;i++){
        //if the key is present the break theloop
        if(key==dom.children[i].key) {
        //update the keymacthed status
            keymatched=true;
            break};
    }
    return keymatched;
}
Enter fullscreen mode Exit fullscreen mode

In the hasKey function we iterate thought a Parent Nodes children to check if the desired key is present, the function returns true/false accordingly.

Now all we need is to add this to our diff function

function diff(vdom, dom) {
    //if dom has no childs then append the childs from vdom
    if (dom.hasChildNodes() == false && vdom.hasChildNodes() == true) {
        //codes
    } else {
        patchKeys(vdom,dom);
        //codes
    }
}
Enter fullscreen mode Exit fullscreen mode

Now this is our Whole code after adding the key feature

function getnodeType(node) {
        if(node.nodeType==1) return node.tagName.toLowerCase();
        else return node.nodeType;
    };
function clean(node) {
    for (let n = 0; n < node.childNodes.length; n++) {
        let 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) {
            if(child.hasAttribute('key')){
                let key=child.getAttribute('key');
                child.key=key;
                child.removeAttribute('key');
            }
            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 hasTheKey(dom,key){
    let keymatched=false;
    for(let i=0;i<dom.children.length;i++){
        if(key==dom.children[i].key) {
            keymatched=true;
            break};
    }
    return keymatched;
}
function patchKeys(vdom,dom){
        //remove unmatched keys from dom
        for(let i=0;i<dom.children.length;i++){
            let dnode=dom.children[i];
            let key=dnode.key;
            if(key){
                if(!hasTheKey(vdom,key)){
                    dnode.remove();
                }
            }
        }
        //adding keys to dom
        for(let i=0;i<vdom.children.length;i++){
            let  vnode=vdom.children[i];
            let key=vnode.key;
            if(key){
                if(!hasTheKey(dom,key)){
                    //if key is not present in dom then add it
                    let nthIndex=[].indexOf.call(vnode.parentNode.children, vnode);
                    if(dom.children[nthIndex]){
                        dom.children[nthIndex].before(vnode.cloneNode(true))
                    }else{
                        dom.append(vnode.cloneNode(true))
                    }
                }
            }
        }
    }
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 {
        patchKeys(vdom,dom);
        //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])
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Lets see if it works.

|-------DOM-------------|--------VDOM---------|--------action------------|
| <Li key=1 val="1">    | <Li key=1 val="1">  | Node                     |
| <Li key=2 val="2">    | <Li key=3 val="3">  | Add this before key 2    |
|                       | <Li key=2 val="2">  | Node                     |
|-----------------------|---------------------|--------------------------|
Enter fullscreen mode Exit fullscreen mode
<div id="node">
    <ul>
        <li key="1">1</li>
        <li key="2">2</li>
    </ul>
</div>
<button>Diff</button>
<script>
 let vdom = parseHTML(`
<ul>
<li key="1">1</li>
<li key="3">3</li>
<li key="2">2</li>
</ul>`);
let dom = document.getElementById('node');
clean(dom);
document.querySelector('button').addEventListener('click',function(){
    diff(vdom,dom);
})
</script>
Enter fullscreen mode Exit fullscreen mode

The result

Image description

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

Top comments (2)

Collapse
 
aralroca profile image
Aral Roca

That's great, do you think is possible to use the same diffing algorithm adapted to work with HTML streaming? I did this parse generator to get the nodes from streaming: github.com/aralroca/parse-html-stream

Collapse
 
joydeep-bhowmik profile image
Joydeep Bhowmik • Edited

Hey thanks for the comments.
And sorry for the late reply.

This is just a simple DOM diffing algorithm implementation it's not battle tested.
You may wanna consider using existing popular libraries like this one github.com/patrick-steele-idem/mor...