1 files changed, 82 insertions, 0 deletions
diff --git a/Sources/NorgKit/TreeFolder.swift b/Sources/NorgKit/TreeFolder.swift
new file mode 100644
index 0000000..944d98f
--- /dev/null
+++ b/Sources/NorgKit/TreeFolder.swift
@@ -0,0 +1,82 @@
+/// Folds a flat list into a tree.
+final class TreeFolder {
+  private enum NestableKind { case unordered, ordered, quote }
+
+  private let blocks: [NorgBlock]
+  private var index = 0
+  private var strongReset = false
+
+  init(_ blocks: [NorgBlock]) {
+    self.blocks = blocks
+  }
+
+  func fold() -> [NorgNode] {
+    foldStructural(level: 0)
+  }
+
+  /// Folds structural items, that can have any block under them.
+  private func foldStructural(level: Int) -> [NorgNode] {
+    var nodes: [NorgNode] = []
+    while index < blocks.count {
+      let block = blocks[index]
+      switch block {
+      case .heading(let headingLevel, _, _, _):
+
+        // A heading of the same or higher level belongs to an ancestor;
+        // leave it for the caller.
+        if headingLevel <= level { return nodes }
+        index += 1
+        let children = foldStructural(level: headingLevel)
+        nodes.append(NorgNode(block: block, children: children))
+        if strongReset {
+          if level == 0 { strongReset = false } else { return nodes }
+        }
+
+      case .unorderedListItem(let itemLevel, _, _, _):
+        nodes.append(foldNestableItem(block, kind: .unordered, level: itemLevel))
+      case .orderedListItem(let itemLevel, _, _, _):
+        nodes.append(foldNestableItem(block, kind: .ordered, level: itemLevel))
+      case .quote(let itemLevel, _, _, _):
+        nodes.append(foldNestableItem(block, kind: .quote, level: itemLevel))
+
+      case .weakDelimiter:
+        index += 1
+        if level > 0 { return nodes }
+
+      case .strongDelimiter:
+        index += 1
+        if level > 0 {
+          strongReset = true
+          return nodes
+        }
+
+      default:
+        index += 1
+        nodes.append(NorgNode(block: block, children: []))
+      }
+    }
+    return nodes
+  }
+
+  /// Folds nestable items that can only consume more of their kind.
+  private func foldNestableItem(_ block: NorgBlock, kind: NestableKind, level: Int) -> NorgNode {
+    index += 1
+    var children: [NorgNode] = []
+    while index < blocks.count, let child = nestableDescriptor(blocks[index]),
+      child.kind == kind, child.level > level {
+      children.append(foldNestableItem(blocks[index], kind: child.kind, level: child.level))
+    }
+    return NorgNode(block: block, children: children)
+  }
+
+  /// The kind and nesting level of a nestable block, or `nil` if `block` is not
+  /// a nestable item.
+  private func nestableDescriptor(_ block: NorgBlock) -> (kind: NestableKind, level: Int)? {
+    switch block {
+    case .unorderedListItem(let level, _, _, _): return (.unordered, level)
+    case .orderedListItem(let level, _, _, _): return (.ordered, level)
+    case .quote(let level, _, _, _): return (.quote, level)
+    default: return nil
+    }
+  }
+}