home.


Tagged: javascript


A simple and naive Virtual DOM implementation, part 5

In the last part, we gave our javascript structure creator function to ability to give each node a hashcode.

We did this so the comparison function can compare a node’s children, to rearrage them rather than obliterate them.

The first thing we’ll do is get the hashcodes before we look at the node’s children. v and v1 equate to the two virtual dom trees we’re comparing.

var v_hashes = v.children.map(c => c.hashcode )
var v1_hashes = v1.children.map(c => c.hashcode )

Next we’ll make an array of the positions of the v1 hashes and whether they exist in the v hashes using indexOf().

Given the v hash array [1111, 2222] and the v1 hash array [3333, 1111, 2222] we’ll get [-1, 0, 1].

indexOf() is telling us: the zeroth item in v1 doesn’t exist in v but the first is the zeroth element, and the second is the first element.

We’re also grabbing v1’s hash in the returning array for later reference.

var positions = v1_hashes.map((h, i) => v_hashes.indexOf(h) )

With this new structure we will loop over it. It will tell us if there’s a new item in the v1 virtual dom that’s not in the v virtual dom, i.e. we find a -1 value.

positions.forEach((index_in_v, v1_pos) => {
  if(index_in_v != -1) return
  console.log("insert " + v1_hashes[v1_pos] + " into " + v1_pos + " at " + path)
  v.children.splice(v1_pos, 0, JSON.parse(JSON.stringify(v1.children[v1_pos])))
})

So we look for that -1, and then rearrange the original v array. This means, later, when we compare the two tree branches our compare function will see they’re the same.

Of course, our compare function must output the fact – here indicated initially as the console.log – that the DOM manipulation function must actually do this rearragement of the DOM.

Although there is much more to do with this function, we can now fix our previous problem with the algorithm:

The v virtual DOM tree was:

[{
    "type": "node",
    "name": "DIV",
    "attrs": [],
    "children": [{
        "type": "node",
        "name": "P",
        "attrs": [],
        "children": [{
            "type": "text",
            "value": "original",
            "children": [],
            "hashcode": -68148979
        }],
        "hashcode": -1072170396
    }],
    "hashcode": -154850033
}]

And v1 was:

[{
    "type": "node",
    "name": "DIV",
    "attrs": [],
    "children": [{
        "type": "node",
        "name": "P",
        "attrs": [],
        "children": [{
            "type": "text",
            "value": "new",
            "children": [],
            "hashcode": 1156737192
        }],
        "hashcode": -1348153726
    }, {
        "type": "node",
        "name": "P",
        "attrs": [],
        "children": [{
            "type": "text",
            "value": "original",
            "children": [],
            "hashcode": -68148979
        }],
        "hashcode": -1072170396
    }],
    "hashcode": 1511584547
}]

In other words, v1 had a new P node (hashcode: -1348153726) above the old one.

And this function:

compare = function(v, v1, path) {
    var v_hashes = v.children.map(c => c.hashcode )
    var v1_hashes = v1.children.map(c => c.hashcode )
    var positions = v1_hashes.map((h, i) => v_hashes.indexOf(h) )
    positions.forEach((index_in_v, v1_pos) => {
      if(index_in_v != -1) return
      console.log("insert " + v1_hashes[v1_pos] + " into " + v1_pos + " at " + path)
      v.children.splice(v1_pos, 0, JSON.parse(JSON.stringify(v1.children[v1_pos])))
    })
    v.children.forEach((_, i) => compare(v.children[i], v1.children[i], path + "" + i) )
}; 
compare(JSON.parse(JSON.stringify(vd[0])), JSON.parse(JSON.stringify(vd1[0])), "")

Will output only.

insert -1348153726 into 0

Next up, we’ll look at how we can remove nodes.

javascript virtual-dom

A simple and naive Virtual DOM implementation, part 4

In part 3, we found a problem with our comparison function:

If we insert a new DOM node above the existing ones the function won’t know the child nodes have been reorganised.

We use our eyes to know this. We quickly look at the node and its children. Then we know this isn’t a new node, but it’s an existing node in a new position.

The algorithm doesn’t have eyes. But we can still allow it to look. We could use JSON.stringify() to compare the nodes in the two virtual dom trees.

We could do this, but this would make our comparison function larger. And we could instead do the work in the function that creates our javascript representation of the DOM.

We can use a “hash code” of the node attributes and its children. This would allow us to compare our nodes based on this value. Here’s stackoverflow’s recommended way of creating a hash code from a string:

String.prototype.hashCode = function() {
  var hash = 0, i, chr;
  if (this.length === 0) return hash;
  for (i = 0; i < this.length; i++) {
    chr   = this.charCodeAt(i);
    hash  = ((hash << 5) - hash) + chr;
    hash |= 0; // Convert to 32bit integer
  }
  return hash;
};

Let’s alter our traverse function to use this on a aggregation of all the values of the node plus a JSON.stringify representation of the children:

function traverse(v, ele) {
  var nu = {}
  v.push(nu)
  if (ele.nodeType == 1) {
    nu.type = "node"
    nu.name = ele.nodeName
    nu.attrs = []
    for (var i = 0; i < ele.attributes.length; i++) {
      var attr = {}
      attr[ele.attributes[i].name] = ele.attributes[i].value;
      nu.attrs.push(attr)
    }
  } else if (ele.nodeType = 3) {
    nu.type = "text"
    nu.value = ele.nodeValue
  }
  nu.children = []
  for(var i = 0; i < ele.childNodes.length; i++) {
    traverse(nu.children, ele.childNodes[i])
  }
  nu.hashcode = ((""+nu.type+nu.name+JSON.stringify(nu.attrs)+nu.type+nu.value)+JSON.stringify(nu.children)).hashCode()
}; traverse(vd, document.documentElement); JSON.stringify(vd, null, 2);

The last line is the only one that has changed. It will output something like:

...
{
  "type": "node",
  "name": "DIV",
  "attrs": [{
    "id": "hi"
  }],
  "children": [{
    "type": "text",
    "value": "hi there",
    "children": [],
    "hashcode": 634735809
  }],
  "hashcode": 2015122423
}
...

We can then use the hashcodes so our comparison function can recognise identical nodes in different positions.

And we will in the next part of this series.

javascript virtual-dom

A simple and naive Virtual DOM implementation, part 3

You’ll recall from part 1 we have a javascript structure, vd, like this:

[{
  "type": "node",
  "name": "HTML",
  "children": [{
    "type": "node",
    "name": "HEAD"
  }, {
    "type": "node",
    "name": "BODY",
    "children": [{
      "type": "node",
      "name": "DIV",
      "attrs": [{
        "id": "hi"
      }],
      "children": [{
        "type": "text",
        "value": "hi there"
      }]
    }]
  }]
}]

Let’s say we have another, vd1, which is the same except the text value is hi there again.

We want a function which loops through all the children, finds this difference and tells us. And that is simple enough:

function compare(v, v1, path) {
    if(v.type != v1.type) console.log(path, "type", v1.type)
    if(v.name != v1.name) console.log(path, "name", v1.name)
    if(JSON.stringify(v.attrs) != JSON.stringify(v1.attrs)) console.log(path, "attrs", v1.attrs)
    if(v.value != v1.value) console.log(path, "value", v1.value)
    for(var i = 0; i < v.children.length; i++) {
      compare(v.children[i], v1.children[i], path + "" + i)
    }
}; compare(vd[0], vd1[0], "")

It will output:

100 value hi there again

Telling us that at node one, zero, zero we should change the value attribute to “hi there again”.

For our first iteration of this function, this isn’t overly bad. (Although we really need to do better with the attrs part but we’ll leave it for now).

But what happens if we don’t just change values, but we insert a new node, a P with some text, above the first div?

In other words:

<html>
  <head>
  </head>
  <body>
    <p>
      a new insert
    </p>
    <div id="hi">
      hi there
    </div>
  </body>
</html>

It will output this:

10 name P
10 [{"id":"hi"}] [] attrs []
100 value a new insert

It’s replacing the first DIV for a P, with new attributes. And replacing the existing text node.

But we didn’t want it replaced. We wanted a new node inserted above it. We will have to think of a new implementation to overcome this problem.

And in part 4, we will.

javascript virtual-dom

A simple and naive Virtual DOM implementation, part 2

We now have a javascript reprentation of our DOM. (See part 1).

But when we traverse this structure we want to know what parts relate to which part in the DOM.

Let’s make a function that shows us where each javascript structure relates in the DOM tree:

function show_dom_location(v, path) {
    console.log(v.type, v.name, path)
    for(var i = 0; i < v.children.length; i++) {
      show_dom_location(v.children[i], path + "" + i)
    }
}; compare(vd[0], "")

vd is your virtual dom javascript structure from part 1 of this series. We pass in [0] since we’re starting at the root element of the structure.

And we pass in a blank string. This will hold the location of each node.

Each time we loop through a child element and recurse into the same function, we will add the loop iteration number. This seem strange but let’s see the output:

node HTML 
node HEAD 0
node BODY 1
node DIV 10
text undefined 100

The first output is the HTML node and the blank string we passed in.

The second output is saying “I’m the zeroth node in HTML element, i.e. HEAD

And last output is saying "I’m the first child (not zeroth) of the HTML element, i.e. BODY. And the zeroth of that, i.e. DIV. And the zeroth output of that, i.e. our text node.

Let’s then use this 100 to find the text node in our dom:

document.documentElement.childNodes[1].childNodes[0].childNodes[0]

In part three we’ll look at comparing two virtual dom javascript structures to find differences.

javascript virtual-dom

Javascript: A simple and naive Virtual DOM implementation, part 1

First thing we’ll do is make a Javascript representation of a DOM tree.

Let’s say we have this DOM tree:

<html>
  <head>
  </head>
  <body>
    <div id="hi">
      hi there
    </div>
  </body>
</html>

Let’s convert that into:

[{
  "type": "node",
  "name": "HTML",
  "children": [{
    "type": "node",
    "name": "HEAD"
  }, {
    "type": "node",
    "name": "BODY",
    "children": [{
      "type": "node",
      "name": "DIV",
      "attrs": [{
        "id": "hi"
      }],
      "children": [{
        "type": "text",
        "value": "hi there"
      }]
    }]
  }]
}]

Each object is either a normal node or text (there are others we could do like comments, but let’s keep it simple). And each has a name, like BODY etc.

We also store the attributes for a node in a list of objects. And the children for a node are included.

Here’s the function that does that:

function traverse(vd, ele) {
  var nu = {}
  vd.push(nu)
  if (ele.nodeType == 1) {
    nu.type = "node"
    nu.name = ele.nodeName
    nu.attrs = []
    for (var i = 0; i < ele.attributes.length; i++) {
      var attr = {}
      attr[ele.attributes[i].name] = ele.attributes[i].value;
      nu.attrs.push(attr)
    }
  } else if (ele.nodeType = 3) {
    nu.type = "text"
    nu.value = ele.nodeValue
  }
  nu.children = []
  for(var i = 0; i < ele.childNodes.length; i++) {
    traverse(nu.children, ele.childNodes[i])
  }
}; 
traverse(vd, document.documentElement); // vd is an empty array to be populated
JSON.stringify(vd, null, 2)

Next we should compare two of theses representations. And we will. Hopefully we will…

javascript virtual-dom

Page 1 of 4
Next