perf(eval): reduce memory usage

8 files changed, 204 insertions, 63 deletions

diff --git a/src/eval/Element.zig b/src/eval/Element.zig
index d804a0c..4600abf 100644
--- a/src/eval/Element.zig
+++ b/src/eval/Element.zig
@@ -11,10 +11,26 @@ pub const Code = blocks.Code;
 pub const Figure = blocks.Figure;
 pub const Callout = blocks.Callout;
 
+pub const Node = struct {
+    ptr: *anyopaque,
+    vtable: struct { element: *const fn (*anyopaque) Element },
+    node: std.DoublyLinkedList.Node = .{},
+
+    pub fn from(n: *std.DoublyLinkedList.Node) *Node {
+        const v: *Node = @fieldParentPtr("node", n);
+        return v;
+    }
+
+    pub fn element(self: Node) Element {
+        return self.vtable.element(self.ptr);
+    }
+};
+
 const Element = @This();
 
 vtable: struct {
     html: *const fn (*anyopaque, Allocator) HTML.Error!HTML,
+    node: *const fn (*anyopaque) *Node,
 },
 ptr: *anyopaque,
 
@@ -29,43 +45,38 @@ pub fn html(self: Element, alloc: Allocator) HTML.Error!HTML {
     return self.vtable.html(self.ptr, alloc);
 }
 
-pub const Empty = struct {
-    content: std.ArrayList(Element),
-
-    const Self = @This();
-
-    pub fn init(alloc: Allocator) !*Self {
-        const v = try alloc.create(Self);
-        v.* = .{ .content = try .initCapacity(alloc, 2) };
-        return v;
-    }
-
-    pub fn element(self: *Self) Element {
-        return .{ .ptr = self, .vtable = .{ .html = Self.html } };
-    }
-
-    fn html(context: *anyopaque, alloc: Allocator) HTML.Error!HTML {
-        const self: *Self = @ptrCast(@alignCast(context));
-        var el = try HTML.Root.init(alloc);
-        errdefer el.deinit();
-        for (self.content.items) |it| el.append(try it.html(el.allocator()));
-        return el.element();
-    }
-};
+pub fn node(self: Element) *Node {
+    return self.vtable.node(self.ptr);
+}
 
 pub const Literal = struct {
     content: []const u8,
+    node: Node = .{
+        .ptr = undefined,
+        .vtable = .{ .element = fromNode },
+    },
 
     const Self = @This();
 
     pub fn init(alloc: Allocator, content: []const u8) !*Self {
         const v = try alloc.create(Self);
         v.* = .{ .content = content };
+        v.node.ptr = v;
         return v;
     }
 
     pub fn element(self: *Self) Element {
-        return .{ .ptr = self, .vtable = .{ .html = Self.html } };
+        return .{ .ptr = self, .vtable = .{ .html = Self.html, .node = getNode } };
+    }
+
+    fn getNode(context: *anyopaque) *Node {
+        const self: *Self = @ptrCast(@alignCast(context));
+        return &self.node;
+    }
+
+    fn fromNode(context: *anyopaque) Element {
+        const self: *Self = @ptrCast(@alignCast(context));
+        return self.element();
     }
 
     fn html(context: *anyopaque, alloc: Allocator) HTML.Error!HTML {
@@ -76,44 +87,49 @@ pub const Literal = struct {
 
 pub fn Simple(comptime tag: []const u8) type {
     return struct {
-        content: std.ArrayList(Element),
+        content: ?Element = null,
+        node: Node,
 
         const Self = @This();
 
         pub fn init(alloc: Allocator) !*Self {
             const v = try alloc.create(Self);
-            v.* = .{ .content = try .initCapacity(alloc, 2) };
+            v.node = .{ .ptr = v, .vtable = .{ .element = fromNode } };
             return v;
         }
 
         pub fn element(self: *Self) Element {
-            return .{ .ptr = self, .vtable = .{ .html = Self.html } };
+            return .{ .ptr = self, .vtable = .{ .html = Self.html, .node = getNode } };
         }
 
         pub fn toTag(self: *Self, alloc: Allocator, comptime target: []const u8) !*Simple(target) {
+            defer alloc.destroy(self);
             const el = try Simple(target).init(alloc);
-            self.conv(alloc, &el.content);
+            el.content = self.content;
             return el;
         }
 
-        pub fn toEmpty(self: *Self, alloc: Allocator) !*Empty {
-            const el = try Empty.init(alloc);
-            self.conv(alloc, &el.content);
+        pub fn toRoot(self: *Self, alloc: Allocator) !*Root {
+            defer alloc.destroy(self);
+            const el = try Root.init(alloc);
+            if (self.content) |it| el.append(it);
             return el;
         }
 
-        fn conv(self: *Self, alloc: Allocator, arr: *std.ArrayList(Element)) void {
-            arr.deinit(alloc);
-            arr.* = self.content;
-            alloc.destroy(self);
+        fn getNode(context: *anyopaque) *Node {
+            const self: *Self = @ptrCast(@alignCast(context));
+            return &self.node;
+        }
+
+        fn fromNode(context: *anyopaque) Element {
+            const self: *Self = @ptrCast(@alignCast(context));
+            return self.element();
         }
 
         fn html(context: *anyopaque, alloc: Allocator) HTML.Error!HTML {
             const self: *Self = @ptrCast(@alignCast(context));
             var el = try HTML.Content.init(alloc, tag);
-            var root = try HTML.Root.init(alloc);
-            el.content = root.element();
-            for (self.content.items) |it| root.append(try it.html(root.allocator()));
+            if (self.content) |it| el.content = try it.html(alloc);
             return el.element();
         }
     };
diff --git a/src/eval/Image.zig b/src/eval/Image.zig
index 53478b6..3e0132a 100644
--- a/src/eval/Image.zig
+++ b/src/eval/Image.zig
@@ -2,22 +2,36 @@ const std = @import("std");
 const Allocator = std.mem.Allocator;
 const HTML = @import("html/Element.zig");
 const Element = @import("Element.zig");
+const Node = Element.Node;
 
 const Self = @This();
 
 src: []const u8,
 alt: ?[]const u8 = null,
+node: Node = .{
+    .ptr = undefined,
+    .vtable = .{ .element = fromNode },
+},
 
 pub fn init(alloc: Allocator, src: []const u8) !*Self {
     const v = try alloc.create(Self);
-    v.* = .{
-        .src = src,
-    };
+    v.* = .{ .src = src };
+    v.node.ptr = v;
     return v;
 }
 
 pub fn element(self: *Self) Element {
-    return .{ .ptr = self, .vtable = .{ .html = html } };
+    return .{ .ptr = self, .vtable = .{ .html = html, .node = getNode } };
+}
+
+fn getNode(context: *anyopaque) *Node {
+    const self: *Self = @ptrCast(@alignCast(context));
+    return &self.node;
+}
+
+fn fromNode(context: *anyopaque) Element {
+    const self: *Self = @ptrCast(@alignCast(context));
+    return self.element();
 }
 
 fn html(context: *anyopaque, alloc: Allocator) HTML.Error!HTML {
diff --git a/src/eval/Root.zig b/src/eval/Root.zig
index fc59c1d..d4ccf30 100644
--- a/src/eval/Root.zig
+++ b/src/eval/Root.zig
@@ -3,21 +3,23 @@ const Allocator = std.mem.Allocator;
 const Arena = std.heap.ArenaAllocator;
 const HTML = @import("html/Element.zig");
 const Element = @import("Element.zig");
+const Node = Element.Node;
 
 const Self = @This();
 
-content: std.ArrayList(Element),
+content: std.DoublyLinkedList = .{},
 arena: Arena,
+node: Node = .{
+    .ptr = undefined,
+    .vtable = .{ .element = fromNode },
+},
 
 pub fn init(parent: Allocator) !*Self {
-    var s = Self{
-        .content = undefined,
-        .arena = .init(parent),
-    };
+    var s = Self{ .arena = .init(parent) };
     var alloc = s.arena.allocator();
-    s.content = try .initCapacity(alloc, 2);
     const v = try alloc.create(Self);
     v.* = s;
+    v.node.ptr = v;
     return v;
 }
 
@@ -29,22 +31,32 @@ pub fn allocator(self: *Self) Allocator {
     return self.arena.allocator();
 }
 
-pub fn append(self: *Self, el: Element) !void {
-    try self.content.append(self.allocator(), el);
+pub fn append(self: *Self, el: Element) void {
+    self.content.append(&el.node().node);
 }
 
 pub fn element(self: *Self) Element {
-    return .{ .vtable = .{ .html = html }, .ptr = self };
+    return .{ .vtable = .{ .html = html, .node = getNode }, .ptr = self };
 }
 
 pub fn renderHTML(self: *Self, alloc: Allocator) HTML.Error![]const u8 {
     return try self.element().renderHTML(alloc);
 }
 
+fn getNode(context: *anyopaque) *Node {
+    const self: *Self = @ptrCast(@alignCast(context));
+    return &self.node;
+}
+
+fn fromNode(context: *anyopaque) Element {
+    const self: *Self = @ptrCast(@alignCast(context));
+    return self.element();
+}
+
 fn html(context: *anyopaque, alloc: Allocator) HTML.Error!HTML {
     const self: *Self = @ptrCast(@alignCast(context));
     const el = try HTML.Root.init(alloc);
-    if (self.content.items.len == 0) return el.element();
-    for (self.content.items) |it| el.append(try it.html(el.allocator()));
+    var v = self.content.first;
+    while (v) |it| : (v = it.next) el.append(try Node.from(it).element().html(el.allocator()));
     return el.element();
 }
diff --git a/src/eval/Title.zig b/src/eval/Title.zig
index dbb5d38..1841ce7 100644
--- a/src/eval/Title.zig
+++ b/src/eval/Title.zig
@@ -2,20 +2,36 @@ const std = @import("std");
 const Allocator = std.mem.Allocator;
 const HTML = Parent.HTML;
 const Parent = @import("Element.zig");
+const Node = Parent.Node;
 
 level: u3,
 content: Parent,
+node: Node = .{
+    .ptr = undefined,
+    .vtable = .{ .element = fromNode },
+},
 
 const Self = @This();
 
 pub fn init(alloc: Allocator, level: u3, content: Parent) !*Self {
     const v = try alloc.create(Self);
     v.* = .{ .level = level, .content = content };
+    v.node.ptr = v;
     return v;
 }
 
 pub fn element(self: *Self) Parent {
-    return .{ .ptr = self, .vtable = .{ .html = html } };
+    return .{ .ptr = self, .vtable = .{ .html = html, .node = getNode } };
+}
+
+fn getNode(context: *anyopaque) *Node {
+    const self: *Self = @ptrCast(@alignCast(context));
+    return &self.node;
+}
+
+fn fromNode(context: *anyopaque) Parent {
+    const self: *Self = @ptrCast(@alignCast(context));
+    return self.element();
 }
 
 fn html(context: *anyopaque, alloc: Allocator) HTML.Error!HTML {
diff --git a/src/eval/blocks.zig b/src/eval/blocks.zig
index eb583c7..cbb95b1 100644
--- a/src/eval/blocks.zig
+++ b/src/eval/blocks.zig
@@ -2,21 +2,40 @@ const std = @import("std");
 const Allocator = std.mem.Allocator;
 const HTML = @import("html/Element.zig");
 const Element = @import("Element.zig");
+const Node = Element.Node;
 
 pub const Code = struct {
     content: std.ArrayList(Element),
     attribute: ?[]const u8 = null,
+    node: Node = .{
+        .ptr = undefined,
+        .vtable = .{ .element = fromNode },
+    },
 
     const Self = @This();
 
     pub fn init(alloc: Allocator) !*Self {
         const v = try alloc.create(Self);
         v.* = .{ .content = try .initCapacity(alloc, 2) };
+        v.node.ptr = v;
         return v;
     }
 
     pub fn element(self: *Self) Element {
-        return .{ .ptr = self, .vtable = .{ .html = Self.html } };
+        return .{ .ptr = self, .vtable = .{
+            .html = html,
+            .node = getNode,
+        } };
+    }
+
+    fn getNode(context: *anyopaque) *Node {
+        const self: *Self = @ptrCast(@alignCast(context));
+        return &self.node;
+    }
+
+    fn fromNode(context: *anyopaque) Element {
+        const self: *Self = @ptrCast(@alignCast(context));
+        return self.element();
     }
 
     fn html(context: *anyopaque, alloc: Allocator) HTML.Error!HTML {
@@ -35,17 +54,32 @@ pub const Code = struct {
 pub const Figure = struct {
     content: Element,
     caption: ?Element = null,
+    node: Node = .{
+        .ptr = undefined,
+        .vtable = .{ .element = fromNode },
+    },
 
     const Self = @This();
 
     pub fn init(alloc: Allocator, content: Element) !*Self {
         const v = try alloc.create(Self);
         v.* = .{ .content = content };
+        v.node.ptr = v;
         return v;
     }
 
     pub fn element(self: *Self) Element {
-        return .{ .ptr = self, .vtable = .{ .html = Self.html } };
+        return .{ .ptr = self, .vtable = .{ .html = html, .node = getNode } };
+    }
+
+    fn getNode(context: *anyopaque) *Node {
+        const self: *Self = @ptrCast(@alignCast(context));
+        return &self.node;
+    }
+
+    fn fromNode(context: *anyopaque) Element {
+        const self: *Self = @ptrCast(@alignCast(context));
+        return self.element();
     }
 
     fn html(context: *anyopaque, parent: Allocator) HTML.Error!HTML {
@@ -67,17 +101,32 @@ pub const Callout = struct {
     content: Element,
     title: ?[]const u8 = null,
     kind: ?[]const u8 = null,
+    node: Node = .{
+        .ptr = undefined,
+        .vtable = .{ .element = fromNode },
+    },
 
     const Self = @This();
 
     pub fn init(alloc: Allocator, content: Element) !*Self {
         const v = try alloc.create(Self);
         v.* = .{ .content = content };
+        v.node.ptr = v;
         return v;
     }
 
     pub fn element(self: *Self) Element {
-        return .{ .ptr = self, .vtable = .{ .html = Self.html } };
+        return .{ .ptr = self, .vtable = .{ .html = html, .node = getNode } };
+    }
+
+    fn getNode(context: *anyopaque) *Node {
+        const self: *Self = @ptrCast(@alignCast(context));
+        return &self.node;
+    }
+
+    fn fromNode(context: *anyopaque) Element {
+        const self: *Self = @ptrCast(@alignCast(context));
+        return self.element();
     }
 
     fn html(context: *anyopaque, alloc: Allocator) HTML.Error!HTML {
diff --git a/src/eval/html/Element.zig b/src/eval/html/Element.zig
index 6073e6a..cf5e74c 100644
--- a/src/eval/html/Element.zig
+++ b/src/eval/html/Element.zig
@@ -29,8 +29,8 @@ pub const Node = struct {
 const Self = @This();
 
 vtable: struct {
-    render: *const fn (self: *anyopaque, alloc: Allocator) Error![]const u8,
-    node: *const fn (self: *anyopaque) *Node,
+    render: *const fn (*anyopaque, Allocator) Error![]const u8,
+    node: *const fn (*anyopaque) *Node,
 },
 ptr: *anyopaque,
 
diff --git a/src/eval/list.zig b/src/eval/list.zig
index 2ba136a..1a7949c 100644
--- a/src/eval/list.zig
+++ b/src/eval/list.zig
@@ -2,10 +2,15 @@ const std = @import("std");
 const Allocator = std.mem.Allocator;
 const HTML = Element.HTML;
 const Element = @import("Element.zig");
+const Node = Element.Node;
 
 fn List(comptime tag: []const u8) type {
     return struct {
         content: std.ArrayList(Element),
+        node: Node = .{
+            .ptr = undefined,
+            .vtable = .{ .element = fromNode },
+        },
 
         const Self = @This();
 
@@ -14,11 +19,22 @@ fn List(comptime tag: []const u8) type {
             v.* = .{
                 .content = try .initCapacity(alloc, 2),
             };
+            v.node.ptr = v;
             return v;
         }
 
         pub fn element(self: *Self) Element {
-            return .{ .ptr = self, .vtable = .{ .html = html } };
+            return .{ .ptr = self, .vtable = .{ .html = html, .node = getNode } };
+        }
+
+        fn getNode(context: *anyopaque) *Node {
+            const self: *Self = @ptrCast(@alignCast(context));
+            return &self.node;
+        }
+
+        fn fromNode(context: *anyopaque) Element {
+            const self: *Self = @ptrCast(@alignCast(context));
+            return self.element();
         }
 
         fn html(context: *anyopaque, alloc: Allocator) HTML.Error!HTML {
diff --git a/src/eval/paragraph.zig b/src/eval/paragraph.zig
index 8609e79..ca72142 100644
--- a/src/eval/paragraph.zig
+++ b/src/eval/paragraph.zig
@@ -2,6 +2,7 @@ const std = @import("std");
 const Allocator = std.mem.Allocator;
 const HTML = Element.HTML;
 const Element = @import("Element.zig");
+const Node = Element.Node;
 
 pub const Block = Element.Simple("p");
 
@@ -13,6 +14,10 @@ pub const Link = struct {
     link: []const u8,
     content: Element,
     target: ?[]const u8 = null,
+    node: Node = .{
+        .ptr = undefined,
+        .vtable = .{ .element = fromNode },
+    },
 
     const Self = @This();
 
@@ -22,11 +27,22 @@ pub const Link = struct {
             .content = content,
             .link = link,
         };
+        v.node.ptr = v;
         return v;
     }
 
     pub fn element(self: *Self) Element {
-        return .{ .ptr = self, .vtable = .{ .html = html } };
+        return .{ .ptr = self, .vtable = .{ .html = html, .node = getNode } };
+    }
+
+    fn getNode(context: *anyopaque) *Node {
+        const self: *Self = @ptrCast(@alignCast(context));
+        return &self.node;
+    }
+
+    fn fromNode(context: *anyopaque) Element {
+        const self: *Self = @ptrCast(@alignCast(context));
+        return self.element();
     }
 
     fn html(context: *anyopaque, alloc: Allocator) HTML.Error!HTML {
@@ -57,12 +73,14 @@ test "paragraph" {
     try doTest(alloc, lit, "hello world");
 
     var p = try Block.init(alloc);
-    try p.content.append(alloc, lit);
+    var root = try Element.Root.init(alloc);
+    p.content = root.element();
+    root.append(lit);
     try doTest(alloc, p.element(), "<p>hello world</p>");
 
     const link = (try Link.init(alloc, (try Element.Literal.init(alloc, "foo")).element(), "example.org")).element();
     try doTest(alloc, link, "<a href=\"example.org\">foo</a>");
 
-    try p.content.append(alloc, link);
+    root.append(link);
     try doTest(alloc, p.element(), "<p>hello world<a href=\"example.org\">foo</a></p>");
 }