parse.odin (10242B)
1 package html 2 3 /* 4 The parser builds an immutable, DOD-stored document tree from a token 5 stream produced by the lexer. 6 7 Nodes are appended to a #soa[dynamic]Node arena and attributes to a flat 8 [dynamic]Attribute array. On return the arenas are frozen to slices. 9 10 The algorithm is recursive descent. It is forgiving: malformed input 11 produces a best-effort tree rather than an error. 12 13 Spec-awareness is limited to what improves real-world results: 14 - void elements (br, img, ...) are treated as self-closing 15 - raw-text elements (script, style, textarea, title) scan to their 16 matching close tag without tokenizing the body 17 - comments become Comment nodes 18 */ 19 20 import "core:log" 21 import "core:strings" 22 23 // parse tokenizes and parses `text` into an immutable Document. 24 parse :: proc(text: string, allocator := context.allocator) -> Document { 25 b: Builder 26 b.nodes = make(#soa[dynamic]Node, 0, 64, allocator) 27 b.attrs = make([dynamic]Attribute, 0, 16, allocator) 28 b.source = strings.clone(text, allocator) or_else "" 29 30 l: Lexer 31 l.source = b.source 32 33 parse_document(&b, &l) 34 35 doc: Document 36 doc.source = b.source 37 doc.nodes = b.nodes[:] 38 doc.attrs = b.attrs[:] 39 doc.preamble = b.preamble 40 return doc 41 } 42 43 // Void elements never have children even without a trailing slash. 44 @(private = "file") 45 is_void_element :: proc(name: string) -> bool { 46 switch name { 47 case "area", 48 "base", 49 "br", 50 "col", 51 "embed", 52 "hr", 53 "img", 54 "input", 55 "link", 56 "meta", 57 "param", 58 "source", 59 "track", 60 "wbr": 61 return true 62 } 63 return false 64 } 65 66 // Raw-text elements: their content is scanned verbatim to the matching 67 // close tag, not tokenized as HTML. 68 @(private = "file") 69 is_raw_text_element :: proc(name: string) -> bool { 70 switch name { 71 case "script", "style", "textarea", "title": 72 return true 73 } 74 return false 75 } 76 77 78 @(private = "file") 79 Builder :: struct { 80 nodes: #soa[dynamic]Node, 81 attrs: [dynamic]Attribute, 82 source: string, 83 preamble: string, 84 } 85 86 // alloc_node appends a node and returns its index, then wires parent links. 87 @(private = "file") 88 alloc_node :: proc(b: ^Builder, n: Node, parent: Node_Ref) -> Node_Ref { 89 node := n 90 node.parent = parent 91 node.first_child = -1 92 node.last_child = -1 93 node.next_sibling = -1 94 node.prev_sibling = -1 95 node.attrs_offset = -1 96 append(&b.nodes, node) 97 idx := len(b.nodes) - 1 98 99 // Wire sibling / child links on the parent. 100 if parent >= 0 { 101 if b.nodes.first_child[parent] == -1 { 102 b.nodes.first_child[parent] = idx 103 } else { 104 prev := b.nodes.last_child[parent] 105 b.nodes.next_sibling[prev] = idx 106 b.nodes.prev_sibling[idx] = prev 107 } 108 b.nodes.last_child[parent] = idx 109 b.nodes.child_count[parent] += 1 110 } 111 return idx 112 } 113 114 // parse_document creates the root html node and parses its children. 115 @(private = "file") 116 parse_document :: proc(b: ^Builder, l: ^Lexer) { 117 b.preamble = parse_preamble(l) 118 119 // Root is always <html>. 120 root_idx := alloc_node(b, Node{kind = .Element, name = "html"}, -1) 121 122 // If the first token is an explicit <html>, consume its open tag so we 123 // don't nest it under the synthetic root. 124 if t, ok := lexer_peek_token(l); ok && token_kind(t) == .Open_Tag_Start { 125 if token_lookup(t, l.source) == "html" { 126 lexer_next(l) // consume Open_Tag_Start 127 parse_attributes(b, l, root_idx) 128 } 129 } 130 131 parse_children(b, l, root_idx) 132 } 133 134 // parse_preamble consumes any leading text/doctype before the first tag. 135 @(private = "file") 136 parse_preamble :: proc(l: ^Lexer) -> (s: string) { 137 for { 138 t, ok := lexer_peek_token(l) 139 if !ok { 140 break 141 } 142 if token_kind(t) == .Open_Tag_Start { 143 break 144 } 145 s = l.source[0:t.end + 1] 146 lexer_next(l) 147 } 148 return 149 } 150 151 // parse_attributes parses attributes into the node at `parent_idx` until Tag_End 152 // or Self_Closing_Tag_End. Returns true if the tag was self-closing. 153 @(private = "file") 154 parse_attributes :: proc(b: ^Builder, l: ^Lexer, parent_idx: Node_Ref) -> (self_closing: bool) { 155 attrs_start := len(b.attrs) 156 157 for token in lexer_next(l) { 158 #partial switch token_kind(token) { 159 case .Tag_End: 160 set_attrs(b, parent_idx, attrs_start) 161 return false 162 case .Self_Closing_Tag_End: 163 set_attrs(b, parent_idx, attrs_start) 164 return true 165 case .Raw_Text: 166 source := token_lookup(token, l.source) 167 for field in strings.fields_iterator(&source) { 168 append(&b.attrs, Attribute{name = field}) 169 } 170 case .Assign: 171 t, ok := lexer_next(l) 172 if !ok { 173 set_attrs(b, parent_idx, attrs_start) 174 return false 175 } 176 #partial switch token_kind(t) { 177 case .Double_Quote_String_Literal, .Single_Quote_String_Literal: 178 if len(b.attrs) == 0 || len(b.attrs) <= attrs_start { 179 log.errorf( 180 "skipping unexpected string literal (missing applicable attribute): %q", 181 token_lookup(t, l.source), 182 ) 183 continue 184 } 185 // Strip the surrounding quotes. 186 val := token_lookup(t, l.source) 187 if len(val) >= 2 { 188 val = val[1:len(val) - 1] 189 } 190 b.attrs[len(b.attrs) - 1].value = val 191 case: 192 log.errorf("expecting string literal after assign") 193 continue 194 } 195 } 196 } 197 198 count := len(b.attrs) - attrs_start 199 if count > 0 { 200 b.nodes.attrs_offset[parent_idx] = attrs_start 201 b.nodes.attrs_count[parent_idx] = u16(count) 202 } 203 return false 204 } 205 206 // set_attrs records the attribute offset/count on the node. 207 @(private = "file") 208 set_attrs :: proc(b: ^Builder, parent_idx: Node_Ref, attrs_start: Attribute_Ref) { 209 count := len(b.attrs) - attrs_start 210 if count > 0 { 211 b.nodes.attrs_offset[parent_idx] = attrs_start 212 b.nodes.attrs_count[parent_idx] = u16(count) 213 } 214 } 215 216 // parse_children parses nodes into `parent_idx` until EOF or Close_Tag_Start. 217 @(private = "file") 218 parse_children :: proc(b: ^Builder, l: ^Lexer, parent_idx: Node_Ref) { 219 for token in lexer_next(l) { 220 #partial switch token_kind(token) { 221 case .Raw_Text: 222 text := token_lookup(token, l.source) 223 alloc_node(b, Node{kind = .Text, text = text}, parent_idx) 224 225 case .Comment_Start: 226 // Consume comment body until Comment_End. 227 body := parse_comment_body(b, l) 228 alloc_node(b, Node{kind = .Comment, text = body}, parent_idx) 229 230 case .Doctype: 231 // Doctype is recorded as a child node. 232 alloc_node(b, Node{kind = .Doctype, text = token_lookup(token, l.source)}, parent_idx) 233 234 case .Open_Tag_Start: 235 name := token_lookup(token, l.source) 236 237 // Explicit </html> or close of parent: the close tag will be handled below. 238 // Create the element node. 239 elem_idx := alloc_node(b, Node{kind = .Element, name = name}, parent_idx) 240 241 // Parse attributes (consumes through Tag_End or Self_Closing_Tag_End). 242 self_closing := parse_attributes(b, l, elem_idx) 243 244 // Void elements and self-closing tags have no children. 245 if is_void_element(name) || self_closing { 246 continue 247 } 248 249 // Raw-text elements: scan verbatim to matching close tag. 250 if is_raw_text_element(name) { 251 parse_raw_text_child(b, l, elem_idx, name) 252 continue 253 } 254 255 // Recurse into children. 256 parse_children(b, l, elem_idx) 257 258 case .Close_Tag_Start: 259 if _, ok := lexer_expect(l, .Tag_End); !ok { 260 log.errorf("expected tag end after close tag identifier") 261 } 262 return 263 264 case .Tag_End, .Self_Closing_Tag_End: 265 // Stray tag-end tokens outside attributes; ignore. 266 case: 267 log.errorf("unexpected token while parsing children: %v", token) 268 } 269 } 270 } 271 272 // parse_comment_body consumes tokens until Comment_End, returning the body text. 273 @(private = "file") 274 parse_comment_body :: proc(b: ^Builder, l: ^Lexer) -> string { 275 parts: [dynamic]string 276 defer delete(parts) 277 278 for token in lexer_next(l) { 279 #partial switch token_kind(token) { 280 case .Comment_End: 281 if len(parts) == 0 { 282 return "" 283 } 284 if len(parts) == 1 { 285 return parts[0] 286 } 287 return strings.join(parts[:], "") 288 case .Raw_Text: 289 append(&parts, token_lookup(token, l.source)) 290 } 291 } 292 293 // EOF without Comment_End; return whatever we collected. 294 if len(parts) == 0 { 295 return "" 296 } 297 if len(parts) == 1 { 298 return parts[0] 299 } 300 return strings.join(parts[:], "") 301 } 302 303 // parse_raw_text_child scans the source from the current cursor for the 304 // matching close tag </name>, creating a single Text child. 305 @(private = "file") 306 parse_raw_text_child :: proc(b: ^Builder, l: ^Lexer, parent_idx: Node_Ref, name: string) { 307 // The lexer cursor is positioned right after the open tag's Tag_End. 308 // We scan the raw source for </name>. 309 src := l.source 310 start := l.cursor 311 312 // Search case-insensitively for </name. 313 idx := find_close_tag(src, int(start), name) 314 if idx < 0 { 315 // No close tag found; consume rest as text. 316 text := src[start:] 317 if len(text) > 0 { 318 alloc_node(b, Node{kind = .Text, text = text}, parent_idx) 319 } 320 // Advance lexer to EOF. 321 l.cursor = u32(len(src)) 322 return 323 } 324 325 text := src[start:idx] 326 if len(text) > 0 { 327 alloc_node(b, Node{kind = .Text, text = text}, parent_idx) 328 } 329 330 // Advance the lexer cursor past </name> and the closing >. 331 // idx points at '<' of </name>. 332 close_end := idx + 2 + len(name) 333 // Skip optional whitespace. 334 for close_end < len(src) && 335 (src[close_end] == ' ' || 336 src[close_end] == '\t' || 337 src[close_end] == '\n' || 338 src[close_end] == '\r') { 339 close_end += 1 340 } 341 if close_end < len(src) && src[close_end] == '>' { 342 close_end += 1 343 } 344 l.cursor = u32(close_end) 345 } 346 347 // find_close_tag searches src from `from` for a case-insensitive </name> 348 // followed by optional whitespace and '>'. Returns the index of '<' or -1. 349 @(private = "file") 350 find_close_tag :: proc(src: string, from: int, name: string) -> int { 351 close := "</" 352 n := len(src) 353 name_len := len(name) 354 i := from 355 for i + 2 + name_len <= n { 356 if src[i] == '<' && src[i + 1] == '/' { 357 // Check name (case-insensitive). 358 match := true 359 for k in 0 ..< name_len { 360 if to_lower(src[i + 2 + k]) != to_lower(name[k]) { 361 match = false 362 break 363 } 364 } 365 if match { 366 // Must be followed by whitespace or '>'. 367 after := i + 2 + name_len 368 if after < n && 369 (src[after] == '>' || 370 src[after] == ' ' || 371 src[after] == '\t' || 372 src[after] == '\n' || 373 src[after] == '\r') { 374 return i 375 } 376 } 377 } 378 i += 1 379 } 380 return -1 381 } 382 383 @(private = "file") 384 to_lower :: proc(b: byte) -> byte { 385 if b >= 'A' && b <= 'Z' { 386 return b + 32 387 } 388 return b 389 } 390