jsdom v30.1.0: replacing the tree under the DOM

Background

That last point is where the cost showed up. Four examples, all visible in the v30.0.1 source:

• Every node paid for tree bookkeeping at construction. Node-impl.js:120 called domSymbolTree.initialize(this) and Node-impl.js:128 allocated this._memoizedQueries = {}, for every node, including Attr nodes that inherit from Node and never join a tree.
• Asking a node its index walked its siblings, so the answer cost time proportional to how far along it sat.
• Live child collections rebuilt themselves after every mutation, whether or not anything read them. The commit says only that they rebuilt; that appending N children therefore costs time proportional to N squared is my reading of what rebuilding each time implies, not a figure jsdom publishes.
• Operations that needed an ancestor chain each walked it themselves. compareDocumentPosition, a range's common ancestor, boundary comparison, and range.surroundContents() repeated the same search, and event dispatch re-walked to the document for every connected parent.

Intuition

A general-purpose tree library has to assume the worst. It cannot know that appending a child leaves every existing child's position untouched, because in its world a "tree" is any tree and a caller might do anything. So it recomputes.

A tree that knows it is holding a DOM can assume more. jsdom's replacement keeps a small record next to each node, the Links class at dom-tree.js:13, holding the parent, the siblings, the first and last child, a running childCount, and a cached index. The record is not allocated until a node joins a tree or gains children, so an Attr carries one null field instead of a tree structure it will never use.

The idea that makes the cache work is that mutations differ in how much they disturb. Take a parent with five children:

• Append a sixth. Children 0 to 4 keep their positions, and the new child takes index 5. Nothing needs recomputing, ever.
• Insert at position 2. Children 0 and 1 are still right; 2 onward are not. The old library would discard the lot. jsdom truncates the cached list at the insertion point and keeps the valid prefix.

Truncating rather than discarding is what lets the cache survive a mutation at all. Dropping the tail also drops the references it held to the removed subtrees, though whether that was a goal or a consequence the code does not say.

Before, at v30.0.1

After, at v30.1.0

The tree below shows the state after inserting a new child at position 2. The prefix that survives is kept; the rest is dropped and rebuilt only if something asks for it.

  const cached = parentData.cachedChildren ||= [];
  // A shifted node can retain an old index inside the rebuilt prefix. Check
  // identity as well as the index before using it.
  if (cached[data.cachedIndex] === node) {
    return data.cachedIndex;
  }

Put together, reading an index now takes one of four paths, and only the last one touches more than a couple of fields.

flowchart TD
    A["treeIndex(node)"] --> B{"is it the first child"}
    B -->|yes| C["return 0"]
    B -->|no| D{"is it the last child"}
    D -->|yes| E["return childCount minus 1"]
    D -->|no| F{"is cachedIndex still trusted"}
    F -->|yes| G["return cachedIndex"]
    F -->|no| H["walk children and fill the prefix array"]
    H --> I["store cachedIndex and return"]
    classDef fast fill:#e4f3ea,stroke:#1a7f47,color:#16181b
    classDef slow fill:#fbefe1,stroke:#b5620a,color:#16181b
    classDef entry fill:#e8eefc,stroke:#3b6cf6,color:#16181b
    class C,E,G fast
    class H,I slow
    class A entry

Code walkthrough

The path: a node is created, joins a tree, the tree indexes it, readers ask for its position or its ancestors, and mutations decide what stays valid. Styles, document lifetime, and the new features hang off that path rather than running down it.

1. Creating a node costs nothing now

The old constructor set up tree bookkeeping and a query cache for every node ever built. The new one sets a null.

lib/jsdom/living/nodes/Node-impl.js:170

-    domSymbolTree.initialize(this);
-    this._memoizedQueries = {};
+    this._links = null;

The commit says why in plain terms: "Attributes inherit from Node but usually don't need tree bookkeeping." The same lazy treatment reached event listeners, which start null at EventTarget-impl.js:24, the on* handler storage, the set of ranges pointing into a node, and the mutation-observer list.

2. Joining a tree, and why append is the easy case

ensureLinks at dom-tree.js:26 allocates the record on first need. Appending then writes one field and increments a counter, with the reasoning stated in a comment rather than left to be worked out.

lib/jsdom/living/helpers/dom-tree.js:299-300

  // Appending preserves every existing child's index.
  childData.cachedIndex = data.childCount++;

3. Reading an index

lib/jsdom/living/helpers/dom-tree.js:256-270

function treeIndex(node) {
  const data = node._links;
  if (data === null || data.parent === null) {
    return -1;
  }
  const parentData = data.parent._links;
  if (data.previousSibling === null) {
    return 0;
  }
  if (data.nextSibling === null) {
    return parentData.childCount - 1;
  }
  if (parentData.cachedChildren === null) {
    return data.cachedIndex;
  }

Three fields carry the state, and the meaning of cachedChildren is a tri-state the code documents at dom-tree.js:20-22: null means append-time indexes are still valid, undefined means they need rebuilding, and an array is a lazily indexed prefix. cachedIndex uses -1 for a node with no parent.

4. Mutating, and invalidating only what moved

insertBefore truncates the cached prefix at the mutation point instead of discarding it, in one line at dom-tree.js:323. _invalidateCaches at Node-impl.js:453 replaced a recursive climb up the ancestors with an iterative loop that bumps the version.

Live collections now work the other way round. They used to rebuild on every mutation; now they mark themselves stale and refresh on the next read, which they detect with a counter. Each element carries a _version that only ever increases, and a collection refreshes when its own copy has fallen behind. The commit states the problem directly: "Live childNodes and children collections were rebuilding after each mutation even when nothing read them."

5. Ancestors, walked once

commonAncestorInfo at dom-tree.js:209 returns the shared ancestor together with the two children that lead to each side, and compareTreePosition, a range's common ancestor, boundary comparison, clone, extract, and range.surroundContents() all read that one result. getRootNode at Node-impl.js:356 caches the root with path compression, which the commit ties to a specific symptom: "building an event path would previously repeatedly walk the Document for each connected parent."

6. Paying for an index only when something wants one

lib/jsdom/living/nodes/Node-impl.js:1019

        childIndex ??= childImpl._treeIndex();

That sits inside the loop over the ranges whose boundaries point into this node. A Range holds positions in the tree, so it has to be adjusted whenever the tree beneath it changes, which is why insertion consults them at all. A document that never created one skips the index entirely.

7. Styles: separating what a value is from how it reads

getComputedStyle() had a cache that did the work twice. A hit cloned the stored declaration by resolving and re-parsing every property, which also lowercased case-sensitive background URLs on the way through. _copyDeclarationsFrom at CSSStyleDeclaration-impl.js:49 copies the raw maps instead and leaves resolution lazy.

The larger move separates two things CSS itself keeps apart. A property's computed value is what the cascade and inheritance produce. Its resolved value is what a caller reading the property back should see, which is not always the same. _getComputedPropertyValue at CSSStyleDeclaration-impl.js:231 memoizes the first, while the second became a display-only layer applied in someStyle.getPropertyValue(). That split is what fixed 'border-width': the keywords are thin 1px, medium 3px and thick 5px, and a border styled none or hidden now resolves to 0px. Previously medium went through the font-size path and borderless elements reported 16px.

Two more in the same area. Setting a shorthand used to write the style="" attribute once per longhand it touched; _updateStyle at CSSStyleDeclaration-impl.js:347 defers and writes once, which the commit calls "both a performance and correctness improvement" because the intermediate writes were producing spurious mutation records and custom-element reactions. StyleSheetList-impl.js:28 now inserts sheets in tree order rather than insertion order, so adding a <style> before an existing one no longer puts it last in document.styleSheets and in the cascade.

8. Documents that are closed but still readable

window.close() used to delete the document and strip its DOM, so retained references went dead while queued work kept running against something unreachable. Destruction is now a flag, and the DOM is left intact. _queueATask at Document-impl.js:643 is the new document-scoped queue that discards work after destruction while still settling its promise, so finally cleanup still runs. Timers, frame callbacks, script execution, subresource loads, navigation and someRequest.send() each consult the flag.

complete() at Document-impl.js:614 fixes a separate hang by splitting internal load completion from the public load event, so an <iframe> that removes itself mid-load no longer leaves its parent waiting forever.

9. The three additions

Named access on document went live by uncommenting the IDL getter; the qualifying local names are at Document-impl.js:86 and the lookup at Document-impl.js:717, where a single matching <iframe> returns its someFrame.contentWindow rather than the element. QuotaExceededError is a new exception carrying optional quota and requested values, thrown by web storage and by someCrypto.getRandomValues() past 65536 bytes at Crypto-impl.js:31; the storage limit is 5000000 code units, defaulted at lib/api.js:263. Relaxed name validation at validate-names.js:7 replaces blanket XML productions with the DOM Standard's per-context rules, so document.createElement("a!b") is now accepted where it previously threw.

What this page sets aside

This release changed 417 files. 127 are under lib/, and those are the ones this page is about, though it names only nine of them and treats the rest as instances of the same few changes. The biggest such group is the per-property files under lib/jsdom/living/css/properties/: the border, flex and font-weight resolvers are one idea applied once per property, so reading a second of them teaches nothing the first did not.

Of the remaining 290 files, 240 are under test/web-platform-tests/. One of those, wpt-manifest.json, is generated and accounts for 1,491,149 of the 1,504,358 added lines by itself, which is why a release of this size reports a diff in the millions. Another 25 are benchmarks, which Contributing.md:125 asks contributors to run before and after a change. The last 25 are workflow files, lint configuration, and documentation, including a policy on AI-assisted contribution added in this same range. None of those are explained here.

One set-aside is worth more than a passing mention. Four release-note bullets describe selector fixes, including the someElement.querySelectorAll() regression introduced in v30.0.0. No jsdom selector code changed. jsdom delegates matching to @asamuzakjp/dom-selector through one method at Document-impl.js:274, and the fixes arrived as a version bump from ^8.3.0 at v30.0.1 to ^9.1.2 at v30.1.0. The commit body for the first bump reads, in full, "Fixes #4227." The mechanism lives in the dependency, and this page cannot show it to you.

Quiz