[whatwg/dom] Proposal: DOMChangeList (#270)

# Motivation

There are three high-level motivations for this API:

1. To make it clearer and less error prone to apply a sequence of DOM operations at once, that can support the full gamut of mutations to `Element`s and `Node`s.
2. For efficiency, to provide an API for constructing a sequence of DOM operations that can be:
  1. constructed in a worker and transferred to the UI thread
  2. constructed with a minimum of allocations
  3. applied in one shot without interleaved user code
3. To support, in one API, the superset of trees that can be produced using the HTML parser and using the DOM API (the HTML parser supports more tag names, while the DOM API supports more trees, such as custom elements nested inside a table).

> This is an initial, minimal version of this API, which could be expanded over time with more capabilities. It should always maintain its goals of predictable, allocation-lite performance, focusing on giving user-space abstractions the capabilities they need for maximum performance.

# Concepts

## NodeToken

A `NodeToken` is an opaque value that represents a `Node`. It can be efficiently transferred from one worker to another.

It serves two purposes:

* To represent a `Node` that already exists in another worker, and can serve as the starting point of a series of mutations expressed in a `DOMChangeList`.
* To represent an intermediate `Node` that was produced as part of the process of building a `DOMChangeList`.

## Applying a Change

The intent of this API is to have these performance characteristics:

* Creating a change list (`DOMTreeConstruction` or `DOMChangeList`) significantly reduces GC-managed allocations compared to the current DOM APIs.
* Applying a change list should not create intermediate JavaScript wrappers for the DOM objects it creates, which should reduce costs.
* It is possible to run the JavaScript code necessary to construct a change list in a worker, and apply it on the UI thread with minimal additional work or allocations in JavaScript.
* The API creates a single immutable blob of instructions to pass to the engine, which is intended to avoid JavaScript side effects while the application proceeds. (as [Boris Zbarsky said](https://news.ycombinator.com/item?id=11780060) in his comment about proposals in this space, "that would simplify both specification and implementation (in the sense of not having to spell out a specific processing algorithm, allowing parallelized implementation, etc).")
* It is reasonable to assume that the builder APIs could be exposed to WebAssembly.

If there is some reason that a concrete implementation of this design might not be able to accomplish these goals, it's almost certainly something we should discuss.

# Details

## DOMTreeConstruction

```typescript
// you can create a NodeToken in the UI thread and transfer it into
// a worker that constructs the DOMChangeList or DOMTreeConstruction.
partial interface Node {
  getToken(): NodeToken<this>;  
}

interface Bounds {
  firstNode: NodeToken<Node>;
  lastNode: NodeToken<Node>;
}

partial interface Element {
  // this has the same semantics as insertBefore, but takes a `DOMTreeConstruction`
  insertTreeBefore(element: Element, tree: DOMTreeConstruction, reference: Node): Promise<AppliedChanges>;
}

// The intent of this object is to allow engines to clean up any bookkeeping maps they
// need to track `NodeToken`s once the `AppliedChanges` is GCed.
interface AppliedChanges {
  // this allows code that created a ChangeList to get the actual
  // node they were creating so they can add listeners or change
  // the node later.
  getNode<T extends Node>(t: NodeToken<T>): T;
}

// DOMTreeConstruction is transferrable, and is backed by raw bytes. This
// allows trees to be constructed in workers.
interface DOMTreeConstruction {
  openElement(name: string, ns: string = "html"): NodeToken<Element>;
  closeElement();

  setAttribute(name: string, value: string = "", ns: string = ""): void;
  appendText(text: string): NodeToken<Text>;
  appendComment(text: string): NodeToken<Comment>;
  appendHTML(html: string): Bounds;
}
```

## DOMChangeList

```typescript
partial interface Document {
  applyChanges(changes: DOMChangeList): Promise<AppliedChangeList>;
}

// DOMChangeList is transferrable, and is backed by raw bytes. This
// allows change lists to be constructed in workers.
interface DOMChangeList {
  /// traverse
  nextSibling(n: NodeToken<Node>): NodeToken<Node | null>;
  previousSibling(n: NodeToken<Node>): NodeToken<Node | null>;
  firstChild(n: NodeToken<Node>): NodeToken<Node | null>;
  lastChild(n: NodeToken<Node>): NodeToken<Node | null>;
  parentNode(n: NodeToken<Node>): NodeToken<Element | null>;

  /// create
  createElement(name: string, ns: string = 'html'): NodeToken<Element>;
  createText(text: string): NodeToken<Text>;
  createComment(text: string): NodeToken<Comment>;

  /// update
  setAttribute(el: NodeToken<Element>, name: string, value: string = '', ns: string = ''): void;
  updateTextData(n: NodeToken<Text>, text: string): void;
  updateCommentData(n: NodeToken<Comment>, text: string): void;
  remove(n: NodeToken<Node>): void;

  /// append
  appendChild(el: NodeToken<Element>, node: NodeToken<Node>): void;
  appendTree(el: NodeToken<Element>, tree: DOMTreeConstruction): void;

  // this unifies the various HTML-based APIs in the DOM; the return value is
  // a token corresponding to the start and a token corresponding to the end of
  // the inserted tree which can be reified after application.
  //
  // IMPORTANT NOTE: The HTML is parsed during application, not when
  // it is added to the change list.
  insertHTMLBefore(node: NodeToken<Node>, html: string): [NodeToken, NodeToken];
}
```

# Example

Using the usual DOM API:

```javascript
let article = document.getElementById('main-article');
let text = node.firstChild;
text.textValue = "Hello world";
node.setAttribute("data-active", "yes");
node.removeAttribute("data-pending");
```

Using the ChangeList API:

```javascript
let articleToken = document.getToken(document.getElementById('main-article'));

let changes = new DOMChangeList();
let textToken = changes.firstChild(token);
changes.updateTextData(textToken, "Hello world");
changes.setAttribute(articleToken, "data-active", "yes");
changes.removeAttribute(articleToken, "data-pending");

document.applyChanges(changes);
```

# FAQ

### Is this actually faster?

1. Don't you still have to create all of the DOM nodes anyway? If so, why is it cheaper?
2. Isn't DOM pretty fast in modern browsers already?

The intent of this API is to create a low-level interface that is as close as possible to the underlying implementations. It attempts to avoid introducing new costs while reducing a number of paper-cuts that exist in today's usage.

1. This API creates DOM nodes in the engine, but it does not need to create JavaScript wrappers. Experiments with deep `cloneNode` show that skipping those wrappers provides a performance benefit, but `cloneNode()` can't satisfy as many use-cases as this API.
2. It allows the construction of the set of mutations to occur separately from the application (or even in a worker), keeping the sensitive work that limits 60fps to a minimum.
3. Since applying changes is asynchronous, the full change list can be applied in batches that avoid blocking interaction (especially scroll). If the browser reaches its budget, it can interleave some work to keep the UI interactive and pick up the mutation process afterward. In short, the API should allow browsers to experiment with more scheduling strategies.
4. It encourages good staging practices, eliminating some of the major causes of layout thrash (see the next section).

### Isn't the real issue that people are interleaving DOM manipulation and layout?

That is certainly a major issue, and this API puts developers on the path to success by encouraging them to stage DOM manipulation work separately from APIs that can trigger painting or layout.

Because the API guarantees that no user script can interleave during the application of changes, there is no way to "mess up" and trigger an immediate flush of any deferred work.

# Unresolved Questions

1. The current state of this API allows failures to occur during the processing of a change list, and does not require engines to roll back earlier changes (rolling back changes like "remove an iframe" may not be trivial to implement). Would engines prefer to roll back changes?
2. Should we support APIs like `ClassList` and the `style` property through this API? It may be difficult to represent these kinds of changes with the operations already proposed (since this API does not allow direct imperative access to the DOM), and a few additional APIs probably wouldn't do damage to the constraints.
3. Are there other optimizations that could be performed by engines? For example, Luke Wagner suggested that a parameterized version of this API could work like "prepared statements" in SQL, allowing engines to do up-front work to optimize the access and mutation patterns for application. What can we do to make this API more hospitable to hypothetical optimizations like those?

---
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/whatwg/dom/issues/270