commit c4d049f3a49c55ef53fc2fa3b14673ef6a254693
parent a525385a676bc22ee95671aa1809ad4ad6817aef
Author: Jack Mordaunt <jackmordaunt.dev@gmail.com>
Date: Thu, 23 Jul 2026 21:23:59 -0300
html: data oriented document
Flat nodes in a contiguous array with index references.
Diffstat:
| M | html.odin | | | 171 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------ |
| D | iterate.odin | | | 47 | ----------------------------------------------- |
2 files changed, 133 insertions(+), 85 deletions(-)
diff --git a/html.odin b/html.odin
@@ -1,60 +1,155 @@
package html
-// Document is the root level data structure containing the entire document.
+// Node_Ref is an index into Document.nodes.
+// -1 means "none" (no parent, no child, no sibling).
+Node_Ref :: int
+
+// Attribute_Ref is an index into Document.attrs.
+Attribute_Ref :: int
+
+// Node_Kind classifies a node in the document tree.
+Node_Kind :: enum u8 {
+ Element, // an HTML tag: <div>, <p>, ...
+ Text, // raw text content
+ Comment, // <!-- ... -->
+ Doctype, // <!DOCTYPE ...>
+}
+
+// Node is a single node in the document tree.
+//
+// Nodes are stored in a #soa[] slice on the Document (see Document.nodes).
+// All cross-references use integer indices, never pointers, so the arena
+// can be frozen (immutable) after parse and traversed cache-efficiently.
+//
+// Index conventions: -1 means "none".
+Node :: struct {
+ kind: Node_Kind,
+ parent: Node_Ref, // index of parent node; -1 for root
+ first_child: Node_Ref, // index of first child; -1 if leaf
+ last_child: Node_Ref, // index of last child; -1 if leaf
+ next_sibling: Node_Ref, // index of next sibling; -1 if last
+ prev_sibling: Node_Ref, // index of prev sibling; -1 if first
+ child_count: u16,
+ attrs_offset: Attribute_Ref, // index into Document.attrs; -1 if none
+ attrs_count: u16,
+ name: string, // tag name for Element; "" otherwise (slices source)
+ text: string, // text/comment body for Text/Comment (slices source)
+}
+
+// Attribute is a single name="value" pair on an Element node.
+// Stored in a flat []Attribute on the Document; a node references a
+// contiguous run [attrs_offset, attrs_offset+attrs_count).
+Attribute :: struct {
+ name: string, // slices source
+ value: string, // slices source; "" for boolean attributes
+}
+
+// Document is the immutable, fully-parsed HTML document.
+//
+// All strings on nodes and attributes are slices into `source`, which the
+// Document owns. Delete with document_delete when done.
Document :: struct {
- preamble: string,
- root: Node_Tag,
+ source: string, // owned copy of the input
+ nodes: #soa[]Node, // frozen arena; index 0 is the root
+ attrs: []Attribute,
+ preamble: string, // anything before the first tag (e.g. doctype), slices source
}
-// Node_Tag is a tag element that might contain other tags.
-Node_Tag :: struct {
- name: string,
- attributes: [dynamic]Attribute,
- children: [dynamic]Node,
+// node_name returns the tag name of an Element, or "" for other kinds.
+node_name :: proc(doc: ^Document, ref: Node_Ref) -> string {
+ return doc.nodes[ref].name
}
-// Node_Text is a raw text element.
-Node_Text :: struct {
- text: string,
+// node_kind returns the Node_Kind of the node at ref.
+node_kind :: proc(doc: ^Document, ref: Node_Ref) -> Node_Kind {
+ return doc.nodes[ref].kind
}
-// Node represents datum within an HTML document.
-Node :: union {
- Node_Tag,
- Node_Text,
+// node_text returns the text/comment body for Text and Comment nodes.
+node_text :: proc(doc: ^Document, ref: Node_Ref) -> string {
+ return doc.nodes[ref].text
}
-Attribute :: struct {
- name: string,
- value: string,
+// node_parent returns the parent node ref, or -1 for the root.
+node_parent :: proc(doc: ^Document, ref: Node_Ref) -> Node_Ref {
+ return doc.nodes[ref].parent
}
-node_to_string :: proc(n: Node) -> string {
- switch v in n {
- case Node_Text:
- return v.text
- case Node_Tag:
- return v.name
- }
- return "<unknown>"
+// node_first_child returns the first child ref, or -1 if leaf.
+node_first_child :: proc(doc: ^Document, ref: Node_Ref) -> Node_Ref {
+ return doc.nodes[ref].first_child
}
-document_delete :: proc(doc: Document) {
- iter := node_iterator_from_document(doc)
- defer node_iterator_delete(iter)
+// node_last_child returns the last child ref, or -1 if leaf.
+node_last_child :: proc(doc: ^Document, ref: Node_Ref) -> Node_Ref {
+ return doc.nodes[ref].last_child
+}
- for node in node_iterator_depth_first(&iter) {
- node_delete(node)
- }
+// node_next_sibling returns the next sibling ref, or -1 if last.
+node_next_sibling :: proc(doc: ^Document, ref: Node_Ref) -> Node_Ref {
+ return doc.nodes[ref].next_sibling
+}
+
+// node_prev_sibling returns the previous sibling ref, or -1 if first.
+node_prev_sibling :: proc(doc: ^Document, ref: Node_Ref) -> Node_Ref {
+ return doc.nodes[ref].prev_sibling
+}
+
+// node_child_count returns the number of children.
+node_child_count :: proc(doc: ^Document, ref: Node_Ref) -> int {
+ return int(doc.nodes[ref].child_count)
+}
+
+// Node_Children is a zero-allocation iterator over a node's children.
+// It lives on the caller's stack and walks the sibling chain.
+Node_Children :: struct {
+ doc: ^Document,
+ current: Node_Ref,
+}
+
+// node_children returns an iterator over the children of a node.
+// The iterator walks the sibling chain starting from first_child.
+node_children :: proc(doc: ^Document, ref: Node_Ref) -> Node_Children {
+ return {doc = doc, current = doc.nodes[ref].first_child}
}
-node_delete :: proc(n: Node) {
- switch n in n {
- case Node_Text:
+// next yields the next child ref, or false when exhausted.
+next :: proc(it: ^Node_Children) -> (ref: Node_Ref, ok: bool) {
+ if it.current < 0 {
return
- case Node_Tag:
- delete(n.attributes)
- delete(n.children)
}
+ ref = it.current
+ it.current = it.doc.nodes[ref].next_sibling
+ return ref, true
+}
+
+// node_attr returns the value of the named attribute and whether it exists.
+node_attr :: proc(doc: ^Document, ref: Node_Ref, name: string) -> (string, bool) {
+ offset := doc.nodes[ref].attrs_offset
+ count := int(doc.nodes[ref].attrs_count)
+ for k in 0 ..< count {
+ attr := &doc.attrs[offset + k]
+ if attr.name == name {
+ return attr.value, true
+ }
+ }
+ return "", false
+}
+
+// node_has_attr reports whether the node has the named attribute.
+node_has_attr :: proc(doc: ^Document, ref: Node_Ref, name: string) -> bool {
+ _, ok := node_attr(doc, ref, name)
+ return ok
+}
+
+// document_delete frees the arena, attribute array, and owned source.
+document_delete :: proc(doc: ^Document) {
+ delete(doc.nodes)
+ delete(doc.attrs)
+ delete(doc.source)
+ doc.nodes = nil
+ doc.attrs = nil
+ doc.source = ""
+ doc.preamble = ""
}
diff --git a/iterate.odin b/iterate.odin
@@ -1,47 +0,0 @@
-package html
-
-Node_Iterator :: struct {
- stack: [dynamic]Node,
-}
-
-node_iterator_delete :: proc(it: Node_Iterator) {
- delete(it.stack)
-}
-
-node_iterator_from_document :: proc(doc: Document) -> (it: Node_Iterator) {
- append(&it.stack, doc.root)
- return
-}
-
-node_iterator_depth_first :: proc(it: ^Node_Iterator) -> (n: Node, ok: bool) {
- entry := pop_safe(&it.stack) or_return
-
- switch node in entry {
- case Node_Text:
- return entry, true
- case Node_Tag:
- #reverse for child in node.children {
- append(&it.stack, child)
- }
- return entry, true
- }
-
- return
-}
-
-node_iterator_breadth_first :: proc(it: ^Node_Iterator) -> (n: Node, ok: bool) {
- entry := pop_front_safe(&it.stack) or_return
-
- switch node in entry {
- case Node_Text:
- return entry, true
- case Node_Tag:
- for child in node.children {
- append(&it.stack, child)
- }
- return entry, true
- }
-
- return
-}
-
