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
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 createTextNode
, createElement
, appendChild
,
and insertBefore
runs in
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
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.
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
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);
}