[SOLVED] DOM diff algorithm with HTML streaming?

DOM diff algorithm with HTML streaming?

Does anybody know if the DOM diff algorithm can be applied in Depth-first search (DFS) instead of Breadth-first search (BFS)? I've been trying for days to get the DOM diff algorithm to work with streaming HTML, but I'm having troubles (different approach than React). Does anyone know of an open-source example?

For now I did this helper to get the Nodes from streaming:

const decoder = new TextDecoder();

export default async function* parseHTMLStream(
  streamReader: ReadableStreamDefaultReader<Uint8Array>,
  doc = document.implementation.createHTMLDocument(),
  lastChunkNode: Node | null = null,
): AsyncGenerator<Node> {
  const { done, value } = await streamReader.read();

  if (done) return;

  doc.write(decoder.decode(value));

  let lastNode = lastChunkNode
    ? getNextNode(lastChunkNode)
    : doc.documentElement;

  for (let node = lastNode; node; node = getNextNode(node)) {
    if (node) lastNode = node;
    yield node;
  }

  yield* await parseHTMLStream(streamReader, doc, lastNode ?? lastChunkNode);
}

/**
 * Get the next node in the tree.
 * It uses depth-first search in order to work with the streamed HTML.
 */
function getNextNode(node: Node | null, deeperDone?: Boolean): Node | null {
  if (!node) return null;
  if (node.childNodes.length && !deeperDone) return node.firstChild;
  return node.nextSibling ?? getNextNode(node.parentNode, true);
}

Then I can use the stream nodes directly with:

const reader = res.body.getReader();

for await (const node of parseHTMLStream(reader)) {
  console.log(node);
}

But then you lose context of whether it was child, slibing and which real dom it has to compare with without creating bugs by updating only the DOM nodes that have changed. I have come to think that if React and all the examples are in Breadth-first that it is not that you can't implement the DOM diff algorithm with Depth-first. Is this so? And if not, does anyone have an example of how it would be implemented?

Solution