Skip to main content

Live NodeList and HTMLCollection in WebKit

There are many DOM APIs that return a live NodeList or HTMLCollection such as childNodes and getElementsByTagName. However, the fact they reflect the live view of the DOM tree introduces a significant code complexity and runtime cost. Consider the following code:

var headers = document.getElementsByTagName('h1');
for (var i = 1; i <= headers.length; i++) {
    var prefix = document.createTextNode(i + '. ');
    var wrapper = document.createElement('span');
    wrapper.appendChild(prefix);
    headers[i].insertBefore(wrapper, headers[i].firstChild);
}

This code prefixes all h1 elements with 1. , 2. , etc... Of course, you can use CSS instead but let's say we wrote this code. Somewhat surprisingly, the runtime complexity of this code is Θ(n2) where n is the number of nodes in the document in WebKit. Let us see why that's the case.

If getElementsByTagName Returned a Static NodeList #

Let's forget about for a moment that getElementsByTagName returns a HTMLCollection which supports named getter/property according to DOM4 working draft and assume it's not live. Then getElementsByTagName in a HTML document can be implemented (after fixing prototype chain, etc...) as follows:

function staticGetElementsByTagName(root, name) {
    var nodeList = new Array;
    for (var node = root.firstChild; node; node = traverseNextNode(node, root)) {
        if (nodeMatchesName(name, node))
            nodeList.push(node);
    }
    return nodeList;
}

function nodeMatchesName(node, name) {
    const htmlNamespaceURI = 'http://www.w3.org/1999/xhtml';
    return name == '*' || node.tagName == (node.namespaceURI == htmlNamespaceURI ? name.toLowerCase() : name);
}

function traverseNextNode(node, root) {
    if (node.firstChild)
        return node.firstChild;
    if (node.nextSibling)
        return node.nextSibling;
    while (node && !node.nextSibling) {
        node = node.parentNode;
        if (node == root)
            return null;
    }
    return node ? node.nextSibling : null;
}

traverseNextNode(node, root) is a preorder depth-first traversal function that stops the traversal at root. With this implementation of getElementsByTagName, the code snippet above runs in Θ(n) as long as createTextNode, createElement, appendChild, and insertBefore runs in O(1).

Making NodeList Live #

Let us now consider making this NodeList live. The simplest solution is to detect when the document is modified and re-generate the entire node list:

function TagNodeList(root, name) {
    var nodeList;
    var oldDOMVersion;

    this.item = function (i) { updateIfNecessary(); return nodeList[i]; }
    this.length = function () { updateIfNecessary(); return nodeList.length; }

    function updateIfNecessary() {
        if (oldDOMVersion != currentDOMVersion();
            nodeList = staticGetElementsByTagName.call(root, name);
        oldDOMVersion = currentDOMVersion();
    }
}

function liveGetElementsByTagName(root, name) { return new TagNodeList(root, name); }

Here, currentDOMVersion() is a function that returns the version of the DOM tree states; i.e. a number that gets incremented whenever the document is modified. The problem with this implementation, of course, is that it invalidates the node list too much. e.g.

var divs = liveGetElementsByTagName(document.body, 'div');
divs.length();
document.head.appendChild(document.createElement('meta'));
divs.length(); // Oops, inserting meta incremented the DOM version!

The second call to length() traverses the entire document.body even though we never modified the DOM tree under body. Somewhat shockingly, this was the invalidation model WebKit used for HTMLCollection until seven months ago when I changed it. It's even worse than this example because the DOM version in WebKit can be incremented by attribute changes as well:

var forms = document.forms;
forms.length; // O(n)
document.head.setAttribute('lang', 'en');
forms.length; // O(n) again.

Another big problem with this approach is that we're traversing the entire subtree of root, and creating an array that contains all matched elements. This is a huge waste of memory if the call site only accessed the first few entries as in:

var divs = liveGetElementsByTagName(document.body, 'div');
divs.item(0).appendChild(document.createTextNode('hello'));
divs.item(1).appendChild(document.createTextNode('world'));

In this example, the call to item(1) is traversing the entire subtree of document.body just to access the second div.

Smarter Invalidation #

Let's not invalidate all node lists just because a node was inserted into a random subtree somewhere. We can add _invalidate() function that gets called whenever an element is inserted into or removed from the subtree of root:

function TagNodeList(root, name) {
    var nodeList;

    this.item = function (i) { updateIfNecessary(); return nodeList[i]; }
    this.length = function () { updateIfNecessary(); return nodeList.length; }
    this._invalidate = function () { nodeList = null; }

    function updateIfNecessary() {
        if (!nodeList)
            nodeList = staticGetElementsByTagName.call(root, name);
    }
}

We can also solve the memory bloating problem by just storing the current node, and traversing forward and backward whenever item() or length() is called:

function TagNodeList(root, name) {
    var lengthCache = NaN;
    var itemCache;
    var itemCacheOffset;

    this.item = function (i) {
        if (lengthCache <= i)
            return null;
        if (itemCache && i == itemCacheOffset)
            return itemCache;
        if (!itemCache || i < itemCacheOffset - i)
            return findItemForward(node.firstChild, -1, i);
        else if (i < itemCacheOffset)
            return findItemBackward(traversePreviousNode(itemCache), itemCacheOffset, i);
        return findItemForward(traverseNextNode(itemCache), itemCacheOffset, i);
    }

    function findItemForward(node, offset, targetOffset) {
        for (; node; node = traverseNextNode(node, root)) {
            if (nodeMatchesName(node, name)) {
                offset++;
                if (offset == targetOffset) {
                    itemCache = node;
                    itemCacheOffset = offset;
                    return itemCache;
                }
            }
        }
        lengthCache = offset + 1;
        return null;
    }

    function findItemBackward(node, offset, targetOffset) {
        // Left as an exercise for the reader.
        return findItemForward(node.firstChild, -1, targetOffset);
    }

    this.length = function () {
        item(Number.MAX_VALUE);
        return lengthCache;
    }

    this._invalidate = function () {
        lengthCache = NaN;
        itemCache = null;
        itemOffsetCache = -1;
    }
}

Now our code is starting to look crazy. Yet WebKit's implementation is much more complicated because it shares code between all live NodeList and HTMLCollection implementations some of which don't support backward traversals.

Still, the biggest question remains to be answered: when do we call _invalidate()? If we call on every DOM modification, it's no better than comparing the DOM versions. On the other hand, if we never call _invalidate(), our methods will return wrong values.

Let us optimize the case where we had a node list at document.body for div elements. If we're inserting a meta element into document.head, then we clearly don't need to invalidate this node list. We can generalize this observation as follows: TagNodeList at node R needs to be invalidated only if there are DOM changes in R's subtree.

Unfortunately, this property does not hold for all node lists. HTML input element's labels node list, for example, depends on label elements associated with an input element and they do not necessary appear in the subtree of the input element. But let us focus on TagNodeList for now.

Using this property, we could make any DOM API that inserts or removes a node call _invalidate() on TagNodeList at all ancestors as follows:

function invalidateNodeListCachesInAncestors(containerNode) {
    for (var node = containerNode; node; node = node.parentNode) {
        var nodeLists = liveNodeListsAt(containerNode);
        for (var i = 0; i < nodeLists.length; i++)
            nodeLists._invalidate();
    }
}

liveNodeListsAt is a function that returns a list of all node lists associated with a given (root) node. This is O(k) algorithm where k is the depth of the DOM tree, which is equal to the number of nodes in the DOM tree in the worst case. However, we have observed that DOM trees in the wild are usually shallow, typically only five to thirty nodes deep, even if they had a large number of nodes (typically 1000-10,000s). In fact, many WebKit browsers cap the maximum depth of DOM tree at 512.

You might wonder why we always need to invalidate node lists. We could easily ignore insertion or removal of a node that doesn't match the name given in TagNodeList, right? Yes and no. Consider this scenario:

var nodeLists = liveGetElementsByTagName(document.body, 'a');
var container = document.createElement('div');
container.appendChild(document.createElement('a'));
document.body.appendChild(container);

Here, the node being inserted is a div that contains an anchor element. In order to detect that the anchor element has been inserted as a part of the div's subtree, we have to walk the entire subtree of the div, the time complexity of which is linear to the number of nodes in the subtree; i.e. O(n).

WebKit's invalidateNodeListCachesInAncestors is a little more complicated because it special cases childNodes and it deals with NodeRareData and NodeListsNodeData, a data structure that holds pointers to live NodeList and HTMLCollection instances but the basic idea is the same.

And there you go. That's why the time complexity of the original code snippet (modified to use WebKit's implementation of live NodeList) is O(n2):

var headers = liveGetElementsByTagName(document, 'h1');
for (var i = 1; i <= headers.length; i++) {
    var prefix = document.createTextNode(i + '. ');
    var wrapper = document.createElement('span');
    wrapper.appendChild(prefix);
    headers[i].insertBefore(wrapper, headers[i].firstChild);
    invalidateNodeListCachesInAncestors(wrapper);
}