Avoid stack overflows when constructing DOM nodes from JSON

[kasperisager]

For sufficiently deeply nested DOM nodes, Node.fromJSON() will fail due to a stack overflow as it recursively constructs DOM nodes from JSON:

alfa/packages/alfa-dom/src/node.ts

Lines 224 to 256 in 6731fd0

	export function fromNode(node: JSON, parent: Option<Node> = None): Node {
	switch (node.type) {
	case "element":
	return Element.fromElement(node as Element.JSON, parent);
	case "attribute":
	return Attribute.fromAttribute(
	node as Attribute.JSON,
	parent.filter(Element.isElement)
	);
	case "text":
	return Text.fromText(node as Text.JSON, parent);
	case "comment":
	return Comment.fromComment(node as Comment.JSON, parent);
	case "document":
	return Document.fromDocument(node as Document.JSON);
	case "type":
	return Type.fromType(node as Type.JSON, parent);
	case "shadow":
	return Shadow.fromShadow(
	node as Shadow.JSON,
	parent.filter(Element.isElement).get()
	);
	default:
	throw new Error(`Unexpected node of type: ${node.type}`);
	}
	}

[kasperisager]

This is a tough one to crack... There's a bidirectional dependence between child and parent nodes which is solved by passing child nodes in a closure that is evaluated by the parent by passing itself as an argument. We therefore cannot trampoline the computation as that would require breaking the bidirectional dependence in either direction 😔 We also cannot cut the stack by deferring either construction of the parent or its children for that same reason.

The only solution I see to this is re-introducing "adoption" of child nodes, which would allow an already constructed parent node to "adopt" orphaned child nodes. This would break the hard immutability of nodes, but could also help solve some other issues we're facing 🤔

[kasperisager]

The various DOM and CSSOM types now handle parent pointers internally with the tradeoff being that they're now slightly mutable. This means that nodes attach themselves to whichever parent they're passed to as a child. When attached to a new parent, nodes also automatically detached from their previous parent. This brings us a little closer to the way things worked before parent pointers were introduced, which does have a positive impact on the ability to construct DOM, in particular for testing purposes:

const child = <span />;

const parent = <div>{child}</div>;

child.parent().includes(parent) === true;

[kasperisager]

Looking into the consequences of this, it did occur to me that we'd be breaking a pretty fundamental assumption that we're currently relying on; if DOM hierarchies are immutable, we can memoize expensive computations such as cascade. That won't be possible if all of a sudden they're mutable 🤔

[kasperisager]

Part of this would be solved by disallowing detachment. Then, once a node is constructed, we can guarantee that the hierarchy below it doesn't change.

[Jym77]

But even then, memoizing cascading and similar stuff is not that easy. The cascading (or aria-hidden) can change due to a distant ancestor being attached to a parent, so it's not easy to figure out whether we can resue an old computation or not.

OTOH, the main use case is to scan a page and test it, not build DOM piece by piece. So we might still assume some sort of immutability of the hierarchy, or maybe having a "frozen" flag that we need to set (and will be set when building from an actual page). And maybe delay expensive computations to after freezing 🤔

When building piece by piece for examples, I can foresee that detachment is actually good:

const target = /* some big element that takes a lot of lines to write */

test("foo", t => { 
  const context1 = <div /* some parameters */>{target}</div>; 
  …
});

test("bar", t => { 
  const context2 = <div /* some other parameters */>{target}</div>; 
  …
});

Then, we'll need to manually freeze the elements.

[kasperisager]

If we can guarantee that the hierarchy below a node doesn't change, then cascade, which is computed for a document and hence the root, can be memoized just fine. I do like the idea of freezing the hierarchy though, which could then be done automatically when computing things that we'd want to memoize. Thinking more about detachment, I do prefer it out of the picture precisely to avoid code like that. For synchronous code things are fine and dandy, but for asynchronous code your DOM hierarchy could end up changing mid-flow:

const span = <span />;

test("foo", async (t) => { 
  const div = <div>{span}</div>;

  span.parent().includes(div) === true;

  await sleep(1000);

  span.parent().includes(div) === false;
});

test("bar", async (t) => { 
  const div = <div>{span}</div>;

  span.parent().includes(div) === true;
});