🔀 Refactor vdom and add support for keyed vnodes. (#83)

* :truck: Keep around old vdom implementation for reference.

* :sparkles: Add a keyed vdom node.

* :alembic: Experiment with a different approach for handling component children.

* :construction: Here be scary works in progress.

* :sparkles: Implement keyed node diffing.

* :recycle: Don't use deprecated 'isOk' checks.

* :recycle: Remove separate Keyed node and add 'key' field to Element node.

* :sparkles: Add support for server components into new vdom.

* :bug: Fix broken build script.

* :recycle: Don't emit data-lustre-key attributes for server component patches.

* :package: Generate server component runtime.

* :bug: Fixed a bug where server component keys were ambiguous when double digit.

* :package: Generate server component runtime.

* :recycle: Refactor 'keyed' element to force all children of a node to be keyed.

* :memo: Consistently format '**Note**:'.

* :bug: Fixed bug with falsey className/style/innerHTML attributes.

* :bug: Fixed a bug not handling undefined 'prev' nodes correctly.

* :package: Generate server component runtime.

1 files changed, 398 insertions, 298 deletions

diff --git a/src/vdom.ffi.mjs b/src/vdom.ffi.mjs
index b9dc706..e77db89 100644
--- a/src/vdom.ffi.mjs
+++ b/src/vdom.ffi.mjs
@@ -1,111 +1,162 @@
-import { Empty } from "./gleam.mjs";
-
-export function morph(prev, curr, dispatch, parent) {
-  if (curr?.subtree) {
-    return morph(prev, curr.subtree(), dispatch, parent);
-  }
-
-  // The current node is an `Element` and the previous DOM node is also a DOM
-  // element.
-  if (curr?.tag && prev?.nodeType === 1) {
-    const nodeName = curr.tag.toUpperCase();
-    const ns = curr.namespace || "http://www.w3.org/1999/xhtml";
-
-    // If the current node and the existing DOM node have the same tag and
-    // namespace, we can morph them together: keeping the DOM node intact and just
-    // updating its attributes and children.
-    if (prev.nodeName === nodeName && prev.namespaceURI == ns) {
-      return morphElement(prev, curr, dispatch, parent);
-    }
-    // Otherwise, we need to replace the DOM node with a new one. The `createElement`
-    // function will handle replacing the existing DOM node for us.
-    else {
-      return createElement(prev, curr, dispatch, parent);
+// This is pretty hot code so it's important that we pay good consideration to
+// writing performant code even if sometimes that means writing less clean code.
+// I'm not exactly a perf witch though, but here are some resources I've collected
+// along the way:
+//
+// - https://romgrk.com/posts/optimizing-javascript
+// - https://www.zhenghao.io/posts/object-vs-map
+//
+
+// Morph turns a Lustre VDOM node into real DOM nodes. Instead of doing a VDOM
+// diff that produces a patch, we morph the VDOM into the real DOM directly.
+export function morph(prev, next, dispatch, isComponent = false) {
+  // This function eventually returns the morphed root node. Because the morphing
+  // process might involve _removing_ the root in some cases, we can't simply return
+  // `prev` and hope for the best.
+  //
+  // We've also unfolded the recursive implementation into a stack-based iterative
+  // one so we cant just rely on good ol' recursion to return the root node. Instead
+  // we track it here and make sure to only set it once.
+  let out;
+  // A stack of nodes to still left to morph. This will shrink and grow over the
+  // course of the function. *Either* `prev` or `next` can be missing, but never
+  // both. The `parent` is *always* present.
+  let stack = [{ prev, next, parent: prev.parentNode }];
+
+  while (stack.length) {
+    let { prev, next, parent } = stack.pop();
+    // If we have the `subtree` property then we're looking at a `Map` vnode that
+    // is lazily evaluated. We'll force it here and then proceed with the morphing.
+    if (next.subtree !== undefined) next = next.subtree();
+
+    // Text nodes:
+    if (next.content !== undefined) {
+      if (!prev) {
+        const created = document.createTextNode(next.content);
+        parent.appendChild(created);
+        out ??= created;
+      } else if (prev.nodeType === Node.TEXT_NODE) {
+        prev.textContent = next.content;
+        out ??= prev;
+      } else {
+        const created = document.createTextNode(next.content);
+        parent.replaceChild(created, prev);
+        out ??= created;
+      }
     }
-  }
-
-  // The current node is an `Element` but the previous DOM node either did not
-  // exist or it is not a DOM element (eg it might be a text or comment node).
-  if (curr?.tag) {
-    return createElement(prev, curr, dispatch, parent);
-  }
+    // Element nodes:
+    else if (next.tag !== undefined) {
+      const created = createElementNode({
+        prev,
+        next,
+        dispatch,
+        stack,
+        isComponent,
+      });
+
+      if (!prev) {
+        parent.appendChild(created);
+      }
+      // We can morph the new node into the previous one if they are compatible.
+      // In those cases we wouldn't want to waste time doing a `replaceChild` so
+      // we're checking explicitly if the new node is different from the previous
+      // one.
+      else if (prev !== created) {
+        parent.replaceChild(created, prev);
+      }
 
-  // The current node is a `Text`.
-  if (typeof curr?.content === "string") {
-    return prev?.nodeType === 3
-      ? morphText(prev, curr)
-      : createText(prev, curr);
+      out ??= created;
+    }
   }
 
-  // If someone was naughty and tried to pass in something other than a Lustre
-  // element (or if there is an actual bug with the runtime!) we'll render a
-  // comment and ask them to report the issue.
-  return document.createComment(
-    [
-      "[internal lustre error] I couldn't work out how to render this element. This",
-      "function should only be called internally by lustre's runtime: if you think",
-      "this is an error, please open an issue at",
-      "https://github.com/hayleigh-dot-dev/gleam-lustre/issues/new",
-    ].join(" "),
-  );
+  return out;
 }
 
 export function patch(root, diff, dispatch) {
+  const rootParent = root.parentNode;
+
+  // A diff is a tuple of three arrays: created, removed, updated. Each of these
+  // arrays contains tuples of slightly differing shape. You'll have to go peek
+  // at `src/lustre/internals/patch.gleam` to work out the exact shape.
+
+  // A `created` diff is a tuple of `[key, element]` where the `key` is a path
+  // to the element in the VDOM tree and the `element` is the VDOM node itself.
+  // Nodes don't have any optimised encoding so they can be passed to `morph`
+  // without any processing.
+  //
+  // We get a created diff if the element is brand new *or* if it changed the tag
+  // of the element.
   for (const created of diff[0]) {
-    const key = created[0];
+    const key = created[0].split("-");
+    const next = created[1];
+    const prev = getDeepChild(rootParent, key);
+
+    let result;
 
+    // If there was a previous node then we can morph the new node into it.
+    if (prev !== null && prev !== rootParent) {
+      result = morph(prev, next, dispatch);
+    }
+    // Otherwise, we create a temporary node to hold the new node's place in the
+    // tree. This can happen because we might get a patch that tells us some node
+    // was created at a path that doesn't exist yet.
+    else {
+      const parent = getDeepChild(rootParent, key.slice(0, -1));
+      const temp = document.createTextNode("");
+      parent.appendChild(temp);
+      result = morph(temp, next, dispatch);
+    }
+
+    // Patching the root node means we might end up replacing it entirely so we
+    // need to reassign the root node if the key is "0".
     if (key === "0") {
-      morph(root, created[1], dispatch, root.parentNode);
-    } else {
-      const segments = Array.from(key);
-      const parentKey = segments.slice(0, -1).join("");
-      const indexKey = segments.slice(-1)[0];
-      const prev =
-        root.querySelector(`[data-lustre-key="${key}"]`) ??
-        root.querySelector(`[data-lustre-key="${parentKey}"]`).childNodes[
-          indexKey
-        ];
-
-      morph(prev, created[1], dispatch, prev.parentNode);
+      root = result;
     }
   }
 
+  // A `removed` diff is just a one-element tuple (for consistency) of the key of
+  // the removed element.
   for (const removed of diff[1]) {
-    const key = removed[0];
-    const segments = Array.from(key);
-    const parentKey = segments.slice(0, -1).join("");
-    const indexKey = segments.slice(-1)[0];
-    const prev =
-      root.querySelector(`[data-lustre-key="${key}"]`) ??
-      root.querySelector(`[data-lustre-key="${parentKey}"]`).childNodes[
-        indexKey
-      ];
-
-    prev.remove();
+    const key = removed[0].split("-");
+    const deletedNode = getDeepChild(rootParent, key);
+    deletedNode.remove();
   }
 
+  // An `updated` diff is all about *attributes*. It's a tuple of `[key, patches]`
+  // where patches is another list of diffs.
   for (const updated of diff[2]) {
-    const key = updated[0];
-    const prev =
-      key === "0" ? root : root.querySelector(`[data-lustre-key="${key}"]`);
+    const key = updated[0].split("-");
+    const patches = updated[1];
+    const prev = getDeepChild(rootParent, key);
+    const handlersForEl = registeredHandlers.get(prev);
 
-    prev.$lustre ??= { __registered_events: new Set() };
+    for (const created of patches[0]) {
+      const name = created[0];
+      const value = created[1];
 
-    for (const created of updated[0]) {
-      morphAttr(prev, created.name, created.value, dispatch);
-    }
+      if (name.startsWith("data-lustre-on-")) {
+        const eventName = name.slice(15);
+        const callback = dispatch(lustreServerEventHandler);
 
-    for (const removed of updated[1]) {
-      if (prev.$lustre.__registered_events.has(removed)) {
-        const event = removed.slice(2).toLowerCase();
+        if (!handlersForEl.has(eventName)) {
+          el.addEventListener(eventName, lustreGenericEventHandler);
+        }
 
-        prev.removeEventListener(event, prev.$lustre[`${removed}Handler`]);
-        prev.$lustre.__registered_events.delete(removed);
+        handlersForEl.set(eventName, callback);
+        el.setAttribute(name, value);
+      } else {
+        prev.setAttribute(name, value);
+        prev[name] = value;
+      }
+    }
 
-        delete prev.$lustre[removed];
-        delete prev.$lustre[`${removed}Handler`];
+    for (const removed of patches[1]) {
+      if (removed[0].startsWith("data-lustre-on-")) {
+        const eventName = removed[0].slice(15);
+        prev.removeEventListener(eventName, lustreGenericEventHandler);
+        handlersForEl.delete(eventName);
       } else {
-        prev.removeAttribute(removed);
+        prev.removeAttribute(removed[0]);
       }
     }
   }
@@ -113,266 +164,287 @@ export function patch(root, diff, dispatch) {
   return root;
 }
 
-// ELEMENTS --------------------------------------------------------------------
-
-function createElement(prev, curr, dispatch, parent = null) {
-  const el = curr.namespace
-    ? document.createElementNS(curr.namespace, curr.tag)
-    : document.createElement(curr.tag);
-
-  el.$lustre = {
-    __registered_events: new Set(),
-  };
+// CREATING ELEMENTS -----------------------------------------------------------
+//
+// @todo do we need to special-case `<input>`, `<option>` and `<textarea>` elements
+// like morphdom does? Things seem to be working as expected so far.
+//
+
+function createElementNode({ prev, next, dispatch, stack }) {
+  const namespace = next.namespace || "http://www.w3.org/1999/xhtml";
+  // When we morph a node we keep the previous one alive in the DOM tree and just
+  // update its attributes and children.
+  const canMorph =
+    prev &&
+    prev.nodeType === Node.ELEMENT_NODE &&
+    prev.localName === next.tag &&
+    prev.namespaceURI === (next.namespace || "http://www.w3.org/1999/xhtml");
+  const el = canMorph
+    ? prev
+    : namespace
+      ? document.createElementNS(namespace, next.tag)
+      : document.createElement(next.tag);
+
+  // We keep track of all event handlers registered on an element across renders.
+  // If this is the first time we're rendering this element, or we're morphing a
+  // DOM node we didn't create then we need to set up that `Map` now.
+  let handlersForEl;
+  if (!registeredHandlers.has(el)) {
+    const emptyHandlers = new Map();
+    registeredHandlers.set(el, emptyHandlers);
+    handlersForEl = emptyHandlers;
+  } else {
+    handlersForEl = registeredHandlers.get(el);
+  }
 
-  let dangerousUnescapedHtml = "";
-
-  for (const attr of curr.attrs) {
-    if (attr[0] === "class") {
-      morphAttr(el, attr[0], `${el.className} ${attr[1]}`);
-    } else if (attr[0] === "style") {
-      morphAttr(el, attr[0], `${el.style.cssText} ${attr[1]}`);
-    } else if (attr[0] === "dangerous-unescaped-html") {
-      dangerousUnescapedHtml += attr[1];
-    } else if (attr[0] !== "") {
-      morphAttr(el, attr[0], attr[1], dispatch);
+  // If we're morphing an element we need to know what event handlers and attributes
+  // were set on the previous render so we can clean up after ourselves.
+  const prevHandlers = canMorph ? new Set(handlersForEl.keys()) : null;
+  const prevAttributes = canMorph
+    ? new Set(Array.from(prev.attributes, (a) => a.name))
+    : null;
+
+  // We handle these three attributes differently because they're special.
+  // `class` and `style` because we want to _accumulate_ them, and `innerHTML`
+  // because it's a special Lustre attribute that allows you to render a HTML
+  // string directly into an element.
+  let className = null;
+  let style = null;
+  let innerHTML = null;
+
+  // In Gleam custom type fields have numeric indexes if they aren't labelled
+  // but they *aren't* able to be destructured, so we have to do normal array
+  // access below.
+  for (const attr of next.attrs) {
+    const name = attr[0];
+    const value = attr[1];
+    const isProperty = attr[2];
+
+    // Properties are set directly on the DOM node.
+    if (isProperty) {
+      el[name] = value;
     }
-  }
+    // Event handlers require some special treatment. We have a generic event
+    // handler that is used for all event handlers attached by lustre. This way
+    // we aren't removing and adding event listeners every render: for each type
+    // of event we attach an event listener just once (until it is removed) and
+    // subsequent renders swap out the callback stored in `handlersForEl`.
+    else if (name.startsWith("on")) {
+      const eventName = name.slice(2);
+      const callback = dispatch(value);
+
+      if (!handlersForEl.has(eventName)) {
+        el.addEventListener(eventName, lustreGenericEventHandler);
+      }
 
-  if (customElements.get(curr.tag)) {
-    el._slot = curr.children;
-  } else if (curr.tag === "slot") {
-    let children = new Empty();
-    let parentWithSlot = parent;
+      handlersForEl.set(eventName, callback);
+      // If we're morphing an element we remove this event's name from the set of
+      // event handlers that were on the previous render so we don't remove it in
+      // the next step.
+      if (canMorph) prevHandlers.delete(eventName);
+    }
+    //
+    else if (name.startsWith("data-lustre-on-")) {
+      const eventName = name.slice(15);
+      const callback = dispatch(lustreServerEventHandler);
 
-    while (parentWithSlot) {
-      if (parentWithSlot._slot) {
-        children = parentWithSlot._slot;
-        break;
-      } else {
-        parentWithSlot = parentWithSlot.parentNode;
+      if (!handlersForEl.has(eventName)) {
+        el.addEventListener(eventName, lustreGenericEventHandler);
       }
-    }
 
-    for (const child of children) {
-      el.appendChild(morph(null, child, dispatch, el));
+      handlersForEl.set(eventName, callback);
+      el.setAttribute(name, value);
     }
-  } else if (dangerousUnescapedHtml) {
-    el.innerHTML = dangerousUnescapedHtml;
-  } else {
-    for (const child of curr.children) {
-      el.appendChild(morph(null, child, dispatch, el));
+    // These attributes are special-cased as explained above.
+    else if (name === "class") {
+      className = className === null ? value : className + " " + value;
+    } else if (name === "style") {
+      style = style === null ? value : style + value;
+    } else if (name === "dangerous-unescaped-html") {
+      innerHTML = value;
+    }
+    // Everything else is treated as a normal attribute. Because we can't easily
+    // tell which attributes are mirrored as properties on the DOM node we assume
+    // that all attributes should be set as properties too.
+    else {
+      el.setAttribute(name, value);
+      el[name] = value;
+      // If we're morphing an element we remove this attribute's name from the set
+      // of attributes that were on the previous render so we don't remove it in
+      // the next step.
+      if (canMorph) prevAttributes.delete(name);
     }
   }
 
-  if (prev) prev.replaceWith(el);
-
-  return el;
-}
+  if (className !== null) {
+    el.setAttribute("class", className);
+    if (canMorph) prevAttributes.delete("class");
+  }
 
-function morphElement(prev, curr, dispatch, parent) {
-  const prevAttrs = prev.attributes;
-  const currAttrs = new Map();
-
-  // This can happen if we're morphing an existing DOM element that *wasn't*
-  // initially created by lustre.
-  prev.$lustre ??= { __registered_events: new Set() };
-
-  // We're going to convert the Gleam List of attributes into a JavaScript Map
-  // so its easier to lookup specific attributes.
-  for (const currAttr of curr.attrs) {
-    if (currAttr[0] === "class" && currAttrs.has("class")) {
-      currAttrs.set(currAttr[0], `${currAttrs.get("class")} ${currAttr[1]}`);
-    } else if (currAttr[0] === "style" && currAttrs.has("style")) {
-      currAttrs.set(currAttr[0], `${currAttrs.get("style")} ${currAttr[1]}`);
-    } else if (
-      currAttr[0] === "dangerous-unescaped-html" &&
-      currAttrs.has("dangerous-unescaped-html")
-    ) {
-      currAttrs.set(
-        currAttr[0],
-        `${currAttrs.get("dangerous-unescaped-html")} ${currAttr[1]}`,
-      );
-    } else if (currAttr[0] !== "") {
-      currAttrs.set(currAttr[0], currAttr[1]);
-    }
+  if (style !== null) {
+    el.setAttribute("style", style);
+    if (canMorph) prevAttributes.delete("style");
   }
 
-  for (const { name } of prevAttrs) {
-    if (!currAttrs.has(name)) {
-      prev.removeAttribute(name);
-    } else {
-      const value = currAttrs.get(name);
+  if (canMorph) {
+    for (const attr of prevAttributes) {
+      el.removeAttribute(attr);
+    }
 
-      morphAttr(prev, name, value, dispatch);
-      currAttrs.delete(name);
+    for (const eventName of prevHandlers) {
+      el.removeEventListener(eventName, lustreGenericEventHandler);
     }
   }
 
-  for (const name of prev.$lustre.__registered_events) {
-    if (!currAttrs.has(name)) {
-      const event = name.slice(2).toLowerCase();
-
-      prev.removeEventListener(event, prev.$lustre[`${name}Handler`]);
-      prev.$lustre.__registered_events.delete(name);
+  // Keyed elements have the property explicitly set on the DOM so we can easily
+  // find them for subsequent renders. We do this after attributes have been
+  // morphed in case someone has keyed an element *and* set the attribute themselves.
+  //
+  // The key stored on the vdom node always takes precedence over the attribute.
+  if (next.key !== undefined && next.key !== "") {
+    el.setAttribute("data-lustre-key", next.key);
+  }
 
-      delete prev.$lustre[name];
-      delete prev.$lustre[`${name}Handler`];
-    }
+  // If we have an `innerHTML` string then we don't bother morphing the children
+  // at all, we just set the `innerHTML` property and move on.
+  else if (innerHTML !== null) {
+    el.innerHTML = innerHTML;
+    return el;
   }
 
-  for (const [name, value] of currAttrs) {
-    morphAttr(prev, name, value, dispatch);
+  let prevChild = prev?.firstChild;
+  // These variables are set up for keyed children diffs. When children are keyed
+  // we can effeciently reuse DOM nodes even if they've moved around in the list.
+  let seenKeys = null;
+  let keyedChildren = null;
+  let incomingKeyedChildren = null;
+  let firstChild = next.children[Symbol.iterator]().next().value;
+
+  // All children are expected to be keyed if any of them are keyed, so just peeking
+  // the first child is enough to determine if we need to do a keyed diff.
+  if (
+    firstChild !== undefined &&
+    // Explicit checks are more verbose but truthy checks force a bunch of comparisons
+    // we don't care about: it's never gonna be a number etc.
+    firstChild.key !== undefined &&
+    firstChild.key !== ""
+  ) {
+    seenKeys = new Set();
+    keyedChildren = getKeyedChildren(prev);
+    incomingKeyedChildren = getKeyedChildren(next);
   }
 
-  if (customElements.get(curr.tag)) {
-    prev._slot = curr.children;
-  } else if (curr.tag === "slot") {
-    let prevChild = prev.firstChild;
-    let currChild = new Empty();
-    let parentWithSlot = parent;
-
-    while (parentWithSlot) {
-      if (parentWithSlot._slot) {
-        currChild = parentWithSlot._slot;
-        break;
-      } else {
-        parentWithSlot = parentWithSlot.parentNode;
+  for (const child of next.children) {
+    // A keyed morph has more complex logic to handle: we need to be grabbing
+    // same-key nodes from the previous render and moving them to the correct
+    // position in the DOM.
+    if (child.key !== undefined && seenKeys !== null) {
+      // If the existing child doesn't have a key, or it is keyed but not present
+      // in the incoming children, then we remove it. We keep doing this until we
+      // find a keyed child that we should preserve and then move on with the
+      // morph as normal.
+      while (
+        prevChild &&
+        !incomingKeyedChildren.has(prevChild.getAttribute("data-lustre-key"))
+      ) {
+        const nextChild = prevChild.nextSibling;
+        el.removeChild(prevChild);
+        prevChild = nextChild;
       }
-    }
 
-    while (prevChild) {
-      if (Array.isArray(currChild) && currChild.length) {
-        morph(prevChild, currChild.shift(), dispatch, prev);
-      } else if (currChild.head) {
-        morph(prevChild, currChild.head, dispatch, prev);
-        currChild = currChild.tail;
+      // If there were no keyed children in the previous render then we can just
+      // insert the incoming child at the current position (and diff against whatever
+      // is already there).
+      if (keyedChildren.size === 0) {
+        stack.unshift({ prev: prevChild, next: child, parent: el });
+        prevChild = prevChild?.nextSibling;
+        continue;
       }
 
-      prevChild = prevChild.nextSibling;
-    }
-
-    for (const child of currChild) {
-      prev.appendChild(morph(null, child, dispatch, prev));
-    }
-  } else if (currAttrs.has("dangerous-unescaped-html")) {
-    prev.innerHTML = currAttrs.get("dangerous-unescaped-html");
-  } else {
-    let prevChild = prev.firstChild;
-    let currChild = curr.children;
-
-    while (prevChild) {
-      if (Array.isArray(currChild) && currChild.length) {
-        const next = prevChild.nextSibling;
-        morph(prevChild, currChild.shift(), dispatch, prev);
-        prevChild = next;
-      } else if (currChild.head) {
-        const next = prevChild.nextSibling;
-        morph(prevChild, currChild.head, dispatch, prev);
-        currChild = currChild.tail;
-        prevChild = next;
-      } else {
-        const next = prevChild.nextSibling;
-        prevChild.remove();
-        prevChild = next;
+      // If we come across a child that has the same key as something else this
+      // render then we can't do any meaningful morphing. We throw a warning and
+      // fall back to inserting the new node.
+      if (seenKeys.has(child.key)) {
+        console.warn(`Duplicate key found in Lustre vnode: ${child.key}`);
+        stack.unshift({ prev: null, next: child, parent: el });
+        continue;
       }
-    }
-
-    for (const child of currChild) {
-      prev.appendChild(morph(null, child, dispatch, prev));
-    }
-  }
-
-  return prev;
-}
 
-// ATTRIBUTES ------------------------------------------------------------------
-
-function morphAttr(el, name, value, dispatch) {
-  switch (typeof value) {
-    case name.startsWith("data-lustre-on-") && "string": {
-      if (!value) {
-        el.removeAttribute(name);
-        el.removeEventListener(event, el.$lustre[`${name}Handler`]);
-
-        break;
+      // The `seenKeys` set is how we track duplicate keys.
+      seenKeys.add(child.key);
+      // If we make it this far then there is potentially a keyed child we can
+      // reuse from the previous render.
+      const keyedChild = keyedChildren.get(child.key);
+
+      // This case is hit when the previous render had *no* children at all. In
+      // that case we can just insert the incoming child.
+      if (!keyedChild && !prevChild) {
+        stack.unshift({ prev: null, next: child, parent: el });
+        continue;
       }
-      if (el.hasAttribute(name)) break;
-
-      const event = name.slice(15).toLowerCase();
-      const handler = dispatch(serverEventHandler);
 
-      if (el.$lustre[`${name}Handler`]) {
-        el.removeEventListener(event, el.$lustre[`${name}Handler`]);
+      // This is a new keyed child that wasn't in the previous render. Because we
+      // can't guarantee things won't get moved around we insert a placeholder node
+      // that preserves the position of the incoming child.
+      if (!keyedChild && prevChild !== null) {
+        const placeholder = document.createTextNode("");
+        el.insertBefore(placeholder, prevChild);
+        stack.unshift({ prev: placeholder, next: child, parent: el });
+        continue;
       }
 
-      el.addEventListener(event, handler);
-
-      el.$lustre[name] = value;
-      el.$lustre[`${name}Handler`] = handler;
-      el.$lustre.__registered_events.add(name);
-      el.setAttribute(name, value);
-
-      break;
-    }
-
-    case "string":
-      if (name === "value") el.value = value;
-      el.setAttribute(name, value);
-
-      break;
-
-    // Event listeners need to be handled slightly differently because we need
-    // to be able to support custom events. We
-    case name.startsWith("on") && "function": {
-      if (el.$lustre[name] === value) break;
-
-      const event = name.slice(2).toLowerCase();
-      const handler = dispatch(value);
-
-      if (el.$lustre[`${name}Handler`]) {
-        el.removeEventListener(event, el.$lustre[`${name}Handler`]);
+      // This is the same as the unkeyed case: we don't have to do any special
+      // handling, just diff against the previous child and move on.
+      if (!keyedChild || keyedChild === prevChild) {
+        stack.unshift({ prev: prevChild, next: child, parent: el });
+        prevChild = prevChild?.nextSibling;
+        continue;
       }
 
-      el.addEventListener(event, handler);
-
-      el.$lustre[name] = value;
-      el.$lustre[`${name}Handler`] = handler;
-      el.$lustre.__registered_events.add(name);
-
-      break;
+      // If we get this far then we did find a keyed child to diff against but
+      // it's somewhere else in the tree. This `insertBefore` moves the old child
+      // into the correct position.
+      //
+      // Note that we're *not* updating the `prevChild` pointer.
+      el.insertBefore(keyedChild, prevChild);
+      stack.unshift({ prev: keyedChild, next: child, parent: el });
+    } else {
+      stack.unshift({ prev: prevChild, next: child, parent: el });
+      prevChild = prevChild?.nextSibling;
     }
-
-    default:
-      el[name] = value;
   }
-}
-
-// TEXT ------------------------------------------------------------------------
 
-function createText(prev, curr) {
-  const el = document.createTextNode(curr.content);
+  // Any remaining children in the previous render can be removed at this point.
+  while (prevChild) {
+    const next = prevChild.nextSibling;
+    el.removeChild(prevChild);
+    prevChild = next;
+  }
 
-  if (prev) prev.replaceWith(el);
   return el;
 }
 
-function morphText(prev, curr) {
-  const prevValue = prev.nodeValue;
-  const currValue = curr.content;
+// EVENT HANDLERS --------------------------------------------------------------
+
+const registeredHandlers = new WeakMap();
 
-  if (!currValue) {
-    prev?.remove();
-    return null;
+function lustreGenericEventHandler(event) {
+  if (!registeredHandlers.has(event.target)) {
+    event.target.removeEventListener(event.type, lustreGenericEventHandler);
+    return;
   }
 
-  if (prevValue !== currValue) prev.nodeValue = currValue;
+  const handlersForEventTarget = registeredHandlers.get(event.target);
 
-  return prev;
-}
+  if (!handlersForEventTarget.has(event.type)) {
+    event.target.removeEventListener(event.type, lustreGenericEventHandler);
+    return;
+  }
 
-// UTILS -----------------------------------------------------------------------
+  handlersForEventTarget.get(event.type)(event);
+}
 
-function serverEventHandler(event) {
+function lustreServerEventHandler(event) {
   const el = event.target;
   const tag = el.getAttribute(`data-lustre-on-${event.type}`);
   const data = JSON.parse(el.getAttribute("data-lustre-data") || "{}");
@@ -407,3 +479,31 @@ function serverEventHandler(event) {
     ),
   };
 }
+
+// UTILS -----------------------------------------------------------------------
+
+function getKeyedChildren(el) {
+  const keyedChildren = new Map();
+
+  if (el) {
+    for (const child of el.children) {
+      const key = child.key || child?.getAttribute("data-lustre-key");
+      if (key) keyedChildren.set(key, child);
+    }
+  }
+
+  return keyedChildren;
+}
+
+function getDeepChild(el, path) {
+  let n;
+  let rest;
+  let child = el;
+
+  while ((([n, ...rest] = path), n !== undefined)) {
+    child = child.childNodes.item(n);
+    path = rest;
+  }
+
+  return child;
+}