🔀 Add support for element fragments. (#99)

* #16 add fragment POC

* WIP

* 16 add fragment support to morph

* add keys for fragments

* ensure proper fragment order, refactor to handle fragment/element more similarly

* fix comment typo, incorrect child typo, simplify key check

* fix comment typo

* add snapshot tests

* flatten fragment using fold right, appending elements

* doc update

---------

Co-authored-by: Hayleigh Thompson <me@hayleigh.dev>

8 files changed, 328 insertions, 101 deletions

diff --git a/birdie_snapshots/can_compute_a_diff_from_one_render_to_the_next_with_fragments.accepted b/birdie_snapshots/can_compute_a_diff_from_one_render_to_the_next_with_fragments.accepted
new file mode 100644
index 0000000..10e6efc
--- /dev/null
+++ b/birdie_snapshots/can_compute_a_diff_from_one_render_to_the_next_with_fragments.accepted
@@ -0,0 +1,5 @@
+---
+version: 1.1.0
+title: Can compute a diff from one render to the next with fragments
+---
+[[["0-2-0",{"content":"3"}]],[],[]]
\ No newline at end of file
diff --git a/birdie_snapshots/can_render_an_application's_initial_state_when_using_fragments.accepted b/birdie_snapshots/can_render_an_application's_initial_state_when_using_fragments.accepted
new file mode 100644
index 0000000..d89dc7b
--- /dev/null
+++ b/birdie_snapshots/can_render_an_application's_initial_state_when_using_fragments.accepted
@@ -0,0 +1,5 @@
+---
+version: 1.1.0
+title: Can render an application's initial state when using fragments
+---
+<p>start fragment</p><p>middle fragment</p><p>0</p><button>-</button><button>+</button><p>order check, last element</p>
\ No newline at end of file
diff --git a/src/lustre/element.gleam b/src/lustre/element.gleam
index 392a777..9fcff25 100644
--- a/src/lustre/element.gleam
+++ b/src/lustre/element.gleam
@@ -8,11 +8,12 @@
 
 // IMPORTS ---------------------------------------------------------------------
 
+import gleam/int
 import gleam/list
 import gleam/string
 import gleam/string_builder.{type StringBuilder}
 import lustre/attribute.{type Attribute, attribute}
-import lustre/internals/vdom.{Element, Map, Text}
+import lustre/internals/vdom.{Element, Fragment, Map, Text}
 
 // TYPES -----------------------------------------------------------------------
 
@@ -62,7 +63,7 @@ pub type Element(msg) =
 /// from your own Lustre components or from external JavaScript libraries.
 ///
 /// **Note**: Because Lustre is primarily used to create HTML, this function
-/// spcieal-cases the following tags render as
+/// special-cases the following tags which render as
 /// [void elements](https://developer.mozilla.org/en-US/docs/Glossary/Void_element):
 ///
 ///   - area
@@ -181,6 +182,21 @@ fn do_keyed(el: Element(msg), key: String) -> Element(msg) {
         void: void,
       )
     Map(subtree) -> Map(fn() { do_keyed(subtree(), key) })
+    Fragment(elements, _) ->
+      elements
+      |> list.index_map(fn(element, idx) {
+        case element {
+          Element(el_key, _, _, _, _, _, _) -> {
+            let new_key = case el_key {
+              "" -> key <> "-" <> int.to_string(idx)
+              _ -> key <> "-" <> el_key
+            }
+            do_keyed(element, new_key)
+          }
+          _ -> do_keyed(element, key)
+        }
+      })
+      |> Fragment(key)
     _ -> el
   }
 }
@@ -246,6 +262,30 @@ pub fn none() -> Element(msg) {
   Text("")
 }
 
+/// A function for wrapping elements to be rendered within a parent container without
+/// specififying the container on definition. Allows the treatment of List(Element(msg))
+/// as if it were Element(msg). Useful when generating a list of elements from data but
+/// used downstream.
+/// 
+pub fn fragment(elements: List(Element(msg))) -> Element(msg) {
+  // remove redundant fragments to simplify rendering
+  flatten_fragment_elements(elements)
+  |> Fragment("")
+}
+
+fn flatten_fragment_elements(elements: List(Element(msg))) {
+  list.fold_right(elements, [], fn(new_elements, element) {
+    case element {
+      // Only flatten one level, the runtime handles next level children
+      // alternatively, this could flatten deeply, but it doesn't save
+      // iteration later given a fragment is iterated the same as an equivalent
+      // list of children
+      Fragment(fr_elements, _) -> list.append(fr_elements, new_elements)
+      el -> [el, ..new_elements]
+    }
+  })
+}
+
 fn escape(escaped: String, content: String) -> String {
   case content {
     "<" <> rest -> escape(escaped <> "&lt;", rest)
@@ -286,6 +326,9 @@ pub fn map(element: Element(a), f: fn(a) -> b) -> Element(b) {
           void: void,
         )
       })
+    Fragment(elements, key) -> {
+      Map(fn() { Fragment(list.map(elements, map(_, f)), key) })
+    }
   }
 }
 
diff --git a/src/lustre/internals/patch.gleam b/src/lustre/internals/patch.gleam
index 5b05429..60be771 100644
--- a/src/lustre/internals/patch.gleam
+++ b/src/lustre/internals/patch.gleam
@@ -11,7 +11,7 @@ import gleam/set.{type Set}
 import gleam/string
 import lustre/internals/constants
 import lustre/internals/vdom.{
-  type Attribute, type Element, Attribute, Element, Event, Map, Text,
+  type Attribute, type Element, Attribute, Element, Event, Fragment, Map, Text,
 }
 
 // TYPES -----------------------------------------------------------------------
@@ -120,13 +120,7 @@ fn do_elements(
               handlers: handlers,
             )
 
-          // This local `zip` function takes two lists of potentially different
-          // sizes and zips them together, padding the shorter list with `None`.
-          let children = zip(old_children, new_children)
-          use diff, #(old, new), pos <- list.index_fold(children, diff)
-          let key = key <> "-" <> int.to_string(pos)
-
-          do_elements(diff, old, new, key)
+          do_element_list(diff, old_children, new_children, key)
         }
 
         // When we have two elements, but their namespaces or their tags differ,
@@ -138,11 +132,35 @@ fn do_elements(
             created: dict.insert(diff.created, key, new),
             handlers: fold_event_handlers(diff.handlers, new, key),
           )
+        Fragment(old_elements, _), Fragment(new_elements, _) ->
+          do_element_list(diff, old_elements, new_elements, key)
+        // Other element is not a fragment, take new element in both cases
+        _, Fragment(_, _) | Fragment(_, _), _ ->
+          ElementDiff(
+            ..diff,
+            created: dict.insert(diff.created, key, new),
+            handlers: fold_event_handlers(diff.handlers, new, key),
+          )
       }
     }
   }
 }
 
+fn do_element_list(
+  diff: ElementDiff(msg),
+  old_elements: List(Element(msg)),
+  new_elements: List(Element(msg)),
+  key: String,
+) {
+  // This local `zip` function takes two lists of potentially different
+  // sizes and zips them together, padding the shorter list with `None`.
+  let children = zip(old_elements, new_elements)
+  use diff, #(old, new), pos <- list.index_fold(children, diff)
+  let key = key <> "-" <> int.to_string(pos)
+
+  do_elements(diff, old, new, key)
+}
+
 pub fn attributes(
   old: List(Attribute(msg)),
   new: List(Attribute(msg)),
@@ -356,14 +374,24 @@ fn fold_event_handlers(
             Error(_) -> handlers
           }
         })
-      use handlers, child, index <- list.index_fold(children, handlers)
-      let key = key <> "-" <> int.to_string(index)
-
-      fold_event_handlers(handlers, child, key)
+      fold_element_list_event_handlers(handlers, children, key)
     }
+    Fragment(elements, _) ->
+      fold_element_list_event_handlers(handlers, elements, key)
   }
 }
 
+fn fold_element_list_event_handlers(
+  handlers: Dict(String, Decoder(msg)),
+  elements: List(Element(msg)),
+  key: String,
+) {
+  use handlers, element, index <- list.index_fold(elements, handlers)
+  let key = key <> int.to_string(index)
+
+  fold_event_handlers(handlers, element, key)
+}
+
 pub fn is_empty_element_diff(diff: ElementDiff(msg)) -> Bool {
   diff.created == dict.new()
   && diff.removed == set.new()
diff --git a/src/lustre/internals/vdom.gleam b/src/lustre/internals/vdom.gleam
index 5f812b2..fc4a4a3 100644
--- a/src/lustre/internals/vdom.gleam
+++ b/src/lustre/internals/vdom.gleam
@@ -24,6 +24,7 @@ pub type Element(msg) {
   // The lambda here defers the creation of the mapped subtree until it is necessary.
   // This means we pay the cost of mapping multiple times only *once* during rendering.
   Map(subtree: fn() -> Element(msg))
+  Fragment(elements: List(Element(msg)), key: String)
 }
 
 pub type Attribute(msg) {
@@ -55,13 +56,22 @@ fn do_handlers(
           }
         })
 
-      use handlers, child, index <- list.index_fold(children, handlers)
-      let key = key <> "-" <> int.to_string(index)
-      do_handlers(child, handlers, key)
+      do_element_list_handlers(children, handlers, key)
     }
+    Fragment(elements, _) -> do_element_list_handlers(elements, handlers, key)
   }
 }
 
+fn do_element_list_handlers(
+  elements: List(Element(msg)),
+  handlers: Dict(String, Decoder(msg)),
+  key: String,
+) {
+  use handlers, element, index <- list.index_fold(elements, handlers)
+  let key = key <> int.to_string(index)
+  do_handlers(element, handlers, key)
+}
+
 // CONVERSIONS: JSON -----------------------------------------------------------
 
 pub fn element_to_json(element: Element(msg)) -> Json {
@@ -77,12 +87,7 @@ fn do_element_to_json(element: Element(msg), key: String) -> Json {
         json.preprocessed_array({
           list.filter_map(attrs, attribute_to_json(_, key))
         })
-      let children =
-        json.preprocessed_array({
-          use child, index <- list.index_map(children)
-          let key = key <> "-" <> int.to_string(index)
-          do_element_to_json(child, key)
-        })
+      let children = do_element_list_to_json(children, key)
 
       json.object([
         #("namespace", json.string(namespace)),
@@ -93,9 +98,18 @@ fn do_element_to_json(element: Element(msg), key: String) -> Json {
         #("void", json.bool(void)),
       ])
     }
+    Fragment(elements, _) -> do_element_list_to_json(elements, key)
   }
 }
 
+fn do_element_list_to_json(elements: List(Element(msg)), key: String) {
+  json.preprocessed_array({
+    use element, index <- list.index_map(elements)
+    let key = key <> int.to_string(index)
+    do_element_to_json(element, key)
+  })
+}
+
 pub fn attribute_to_json(
   attribute: Attribute(msg),
   key: String,
@@ -237,6 +251,8 @@ fn do_element_to_string_builder(
           |> string_builder.append(">" <> inner_html <> "</" <> tag <> ">")
       }
     }
+    Fragment(elements, _) ->
+      children_to_string_builder(string_builder.new(), elements, raw_text)
   }
 }
 
diff --git a/src/vdom.ffi.mjs b/src/vdom.ffi.mjs
index 9e2a284..825a450 100644
--- a/src/vdom.ffi.mjs
+++ b/src/vdom.ffi.mjs
@@ -66,6 +66,15 @@ export function morph(prev, next, dispatch, isComponent = false) {
       }
 
       out ??= created;
+    // If this happens, then the top level Element is a Fragment `prev` should be
+    // the first element of the given fragment. Functionally, a fragment as the 
+    // first child means that document -> body will be the parent of the first level
+    // of children
+    } else if (next.elements !== undefined) {
+      iterateElement(next, (fragmentElement) => {
+        stack.unshift({ prev, next: fragmentElement, parent });
+        prev = prev?.nextSibling
+      });
     }
   }
 
@@ -334,85 +343,18 @@ function createElementNode({ prev, next, dispatch, stack }) {
     keyedChildren = getKeyedChildren(prev);
     incomingKeyedChildren = getKeyedChildren(next);
   }
-
   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;
-      }
-
-      // 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;
-      }
-
-      // 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;
-      }
-
-      // 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;
-      }
-
-      // 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;
-      }
-
-      // 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 });
+    iterateElement(child, (currElement) => {
+      // 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 (currElement.key !== undefined && seenKeys !== null) {
+        prevChild = diffKeyedChild(prevChild, currElement, el, stack, incomingKeyedChildren, keyedChildren, seenKeys);
+      } else {
+        stack.unshift({ prev: prevChild, next: currElement, parent: el });
         prevChild = prevChild?.nextSibling;
-        continue;
       }
-
-      // 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;
-    }
+    });
   }
 
   // Any remaining children in the previous render can be removed at this point.
@@ -490,8 +432,10 @@ function getKeyedChildren(el) {
 
   if (el) {
     for (const child of el.children) {
-      const key = child.key || child?.getAttribute("data-lustre-key");
-      if (key) keyedChildren.set(key, child);
+      iterateElement(child, (currElement) => {
+        const key = currElement?.key || currElement?.getAttribute?.("data-lustre-key");
+        if (key) keyedChildren.set(key, currElement);
+      });
     }
   }
 
@@ -510,3 +454,93 @@ function getDeepChild(el, path) {
 
   return child;
 }
+
+function diffKeyedChild(prevChild, child, el, stack, incomingKeyedChildren, keyedChildren, seenKeys) {
+  // 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;
+  }
+
+  // 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) {
+    iterateElement(child, (currChild) => {
+          stack.unshift({ prev: prevChild, next: currChild, parent: el });
+          prevChild = prevChild?.nextSibling
+    });
+    return prevChild;
+  }
+
+  // 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 });
+    return prevChild;
+  }
+
+  // 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 });
+    return prevChild;
+  }
+
+  // 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 });
+    return prevChild;
+  }
+
+  // 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;
+    return prevChild;
+  }
+
+  // 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 });
+  return prevChild;
+}
+
+/*
+ Iterate element, helper to apply the same functions to a standard "Element" or "Fragment" transparently
+ 1. If single element, call callback for that element
+ 2. If fragment, call callback for every child element. Fragment constructor guarantees no Fragment children
+*/
+function iterateElement(element, processElement) {
+  if (element.elements !== undefined) {
+    for (const currElement of element.elements) {
+      processElement(currElement);
+    }
+  } else {
+    processElement(element);
+  }
+}
diff --git a/test/apps/fragment.gleam b/test/apps/fragment.gleam
new file mode 100644
index 0000000..d20400e
--- /dev/null
+++ b/test/apps/fragment.gleam
@@ -0,0 +1,45 @@
+// Similar to count app, with fragments and edge cases
+
+// IMPORTS ---------------------------------------------------------------------
+
+import gleam/int
+import lustre/element.{text}
+import lustre/element/html.{button, p}
+import lustre/event
+
+// MODEL -----------------------------------------------------------------------
+
+pub type Model =
+  Int
+
+pub fn init(count) {
+  count
+}
+
+// UPDATE ----------------------------------------------------------------------
+
+pub type Msg {
+  Increment
+  Decrement
+}
+
+pub fn update(model, msg) {
+  case msg {
+    Increment -> model + 1
+    Decrement -> model - 1
+  }
+}
+
+// VIEW ------------------------------------------------------------------------
+
+pub fn view(model) {
+  let count = int.to_string(model)
+  element.fragment([
+    element.fragment([p([], [element.text("start fragment")])]),
+    element.fragment([p([], [element.text("middle fragment")])]),
+    element.fragment([p([], [element.text(count)])]),
+    button([event.on_click(Decrement)], [text("-")]),
+    button([event.on_click(Increment)], [text("+")]),
+    p([], [element.text("order check, last element")]),
+  ])
+}
diff --git a/test/lustre_test.gleam b/test/lustre_test.gleam
index 9e47a01..f3a2993 100644
--- a/test/lustre_test.gleam
+++ b/test/lustre_test.gleam
@@ -1,6 +1,7 @@
 // IMPORTS ---------------------------------------------------------------------
 
 import apps/counter
+import apps/fragment
 import apps/static
 import birdie
 import gleam/erlang/process
@@ -98,3 +99,53 @@ pub fn counter_diff_test() {
   birdie.snap(json.to_string(patch.element_diff_to_json(diff)), title)
   process.send(runtime, Shutdown)
 }
+
+pub fn fragment_init_test() {
+  let title = "Can render an application's initial state when using fragments"
+  let app = lustre.simple(fragment.init, fragment.update, fragment.view)
+  let assert Ok(runtime) = lustre.start_actor(app, 0)
+  let el =
+    process.call(
+      runtime,
+      function.curry2(process.send)
+        |> function.compose(View)
+        |> function.compose(Debug),
+      100,
+    )
+
+  birdie.snap(element.to_string(el), title)
+  process.send(runtime, Shutdown)
+}
+
+pub fn fragment_counter_diff_test() {
+  let title = "Can compute a diff from one render to the next with fragments"
+  let app = lustre.simple(fragment.init, fragment.update, fragment.view)
+  let assert Ok(runtime) = lustre.start_actor(app, 0)
+
+  let prev =
+    process.call(
+      runtime,
+      function.curry2(process.send)
+        |> function.compose(View)
+        |> function.compose(Debug),
+      100,
+    )
+
+  process.send(runtime, Dispatch(fragment.Increment))
+  process.send(runtime, Dispatch(fragment.Increment))
+  process.send(runtime, Dispatch(fragment.Increment))
+
+  let next =
+    process.call(
+      runtime,
+      function.curry2(process.send)
+        |> function.compose(View)
+        |> function.compose(Debug),
+      100,
+    )
+
+  let diff = patch.elements(prev, next)
+
+  birdie.snap(json.to_string(patch.element_diff_to_json(diff)), title)
+  process.send(runtime, Shutdown)
+}