Line data Source code
1 : #include "html_parser.h"
2 : #include <stdio.h>
3 : #include <stdlib.h>
4 : #include <string.h>
5 : #include <ctype.h>
6 :
7 : /* ── Void elements (never have children) ───────────────────────────── */
8 :
9 : static const char * const VOID_TAGS[] = {
10 : "area","base","br","col","embed","hr","img","input",
11 : "link","meta","param","source","track","wbr", NULL
12 : };
13 1647 : static int is_void(const char *t) {
14 1647 : if (!t) return 0;
15 23668 : for (int i = 0; VOID_TAGS[i]; i++)
16 22143 : if (strcmp(t, VOID_TAGS[i]) == 0) return 1;
17 1525 : return 0;
18 : }
19 :
20 : /* Auto-close: opening one of these implicitly closes the previous sibling */
21 : static const char * const AUTO_CLOSE_TAGS[] = {
22 : "li","p","dt","dd","tr","td","th", NULL
23 : };
24 1647 : static int is_auto_close(const char *t) {
25 1647 : if (!t) return 0;
26 10309 : for (int i = 0; AUTO_CLOSE_TAGS[i]; i++)
27 9211 : if (strcmp(t, AUTO_CLOSE_TAGS[i]) == 0) return 1;
28 1098 : return 0;
29 : }
30 :
31 : /* ── Dynamic string ─────────────────────────────────────────────────── */
32 :
33 : typedef struct { char *d; size_t n, cap; } Buf;
34 :
35 32818 : static int buf_push(Buf *b, char c) {
36 32818 : if (b->n + 1 >= b->cap) {
37 5307 : size_t nc = b->cap ? b->cap * 2 : 64;
38 5307 : char *t = realloc(b->d, nc);
39 5307 : if (!t) return 0;
40 5307 : b->d = t; b->cap = nc;
41 : }
42 32818 : b->d[b->n++] = c;
43 32818 : b->d[b->n] = '\0';
44 32818 : return 1;
45 : }
46 2440 : static char *buf_take(Buf *b) {
47 2440 : char *r = b->d; b->d = NULL; b->n = b->cap = 0; return r;
48 : }
49 4941 : static void buf_free(Buf *b) { free(b->d); b->d = NULL; b->n = b->cap = 0; }
50 :
51 : /* ── Node helpers ───────────────────────────────────────────────────── */
52 :
53 1708 : static HtmlNode *node_elem(char *tag) {
54 1708 : HtmlNode *n = calloc(1, sizeof(*n));
55 1708 : if (!n) { free(tag); return NULL; }
56 1708 : n->type = HTML_NODE_ELEMENT; n->tag = tag; return n;
57 : }
58 1403 : static HtmlNode *node_text(char *text) {
59 1403 : HtmlNode *n = calloc(1, sizeof(*n));
60 1403 : if (!n) { free(text); return NULL; }
61 1403 : n->type = HTML_NODE_TEXT; n->text = text; return n;
62 : }
63 3111 : static void attr_free_list(HtmlAttr *a) {
64 3538 : while (a) { HtmlAttr *nx = a->next; free(a->name); free(a->value); free(a); a = nx; }
65 3111 : }
66 6283 : void html_node_free(HtmlNode *node) {
67 6283 : if (!node) return;
68 3111 : html_node_free(node->first_child);
69 3111 : html_node_free(node->next_sibling);
70 3111 : attr_free_list(node->attrs);
71 3111 : free(node->tag); free(node->text); free(node);
72 : }
73 1830 : const char *html_attr_get(const HtmlNode *node, const char *name) {
74 1830 : if (!node || !name) return NULL;
75 2135 : for (HtmlAttr *a = node->attrs; a; a = a->next)
76 671 : if (strcmp(a->name, name) == 0) return a->value;
77 1464 : return NULL;
78 : }
79 3050 : static void node_add_child(HtmlNode *parent, HtmlNode *child) {
80 3050 : if (!parent || !child) return;
81 3050 : child->parent = parent;
82 3050 : if (!parent->first_child) { parent->first_child = child; return; }
83 1525 : HtmlNode *last = parent->first_child;
84 5368 : while (last->next_sibling) last = last->next_sibling;
85 1525 : last->next_sibling = child;
86 : }
87 427 : static void attr_prepend(HtmlNode *elem, char *name, char *value) {
88 427 : HtmlAttr *a = calloc(1, sizeof(*a));
89 427 : if (!a) { free(name); free(value); return; }
90 427 : a->name = name; a->value = value; a->next = elem->attrs; elem->attrs = a;
91 : }
92 :
93 : /* ── Entity decoder ─────────────────────────────────────────────────── */
94 :
95 : static const struct { const char *name; unsigned cp; } ENTITIES[] = {
96 : {"amp",'&'},{"lt",'<'},{"gt",'>'},{"quot",'"'},{"apos",'\''},
97 : {"nbsp",0xA0},{"copy",0xA9},{"reg",0xAE},{"mdash",0x2014},
98 : {"ndash",0x2013},{"hellip",0x2026},{"laquo",0xAB},{"raquo",0xBB},
99 : /* zero-width / formatting */
100 : {"zwnj",0x200C},{"zwj",0x200D},{"shy",0xAD},
101 : /* common symbols */
102 : {"bull",0x2022},{"middot",0xB7},{"trade",0x2122},{"euro",0x20AC},
103 : {"pound",0xA3},{"cent",0xA2},{"yen",0xA5},
104 : {"times",0xD7},{"divide",0xF7},
105 : /* Latin-1 supplement (HTML 4, U+00C0–U+00FF) */
106 : {"Agrave",0xC0},{"agrave",0xE0},{"Aacute",0xC1},{"aacute",0xE1},
107 : {"Acirc", 0xC2},{"acirc", 0xE2},{"Atilde",0xC3},{"atilde",0xE3},
108 : {"Auml", 0xC4},{"auml", 0xE4},{"Aring", 0xC5},{"aring", 0xE5},
109 : {"AElig", 0xC6},{"aelig", 0xE6},{"Ccedil",0xC7},{"ccedil",0xE7},
110 : {"Egrave",0xC8},{"egrave",0xE8},{"Eacute",0xC9},{"eacute",0xE9},
111 : {"Ecirc", 0xCA},{"ecirc", 0xEA},{"Euml", 0xCB},{"euml", 0xEB},
112 : {"Igrave",0xCC},{"igrave",0xEC},{"Iacute",0xCD},{"iacute",0xED},
113 : {"Icirc", 0xCE},{"icirc", 0xEE},{"Iuml", 0xCF},{"iuml", 0xEF},
114 : {"ETH", 0xD0},{"eth", 0xF0},{"Ntilde",0xD1},{"ntilde",0xF1},
115 : {"Ograve",0xD2},{"ograve",0xF2},{"Oacute",0xD3},{"oacute",0xF3},
116 : {"Ocirc", 0xD4},{"ocirc", 0xF4},{"Otilde",0xD5},{"otilde",0xF5},
117 : {"Ouml", 0xD6},{"ouml", 0xF6},{"Oslash",0xD8},{"oslash",0xF8},
118 : {"Ugrave",0xD9},{"ugrave",0xF9},{"Uacute",0xDA},{"uacute",0xFA},
119 : {"Ucirc", 0xDB},{"ucirc", 0xFB},{"Uuml", 0xDC},{"uuml", 0xFC},
120 : {"Yacute",0xDD},{"yacute",0xFD},{"THORN", 0xDE},{"thorn", 0xFE},
121 : {"szlig", 0xDF},{"yuml", 0xFF},{"iexcl",0xA1},{"iquest",0xBF},
122 : {"Iuml", 0xCF},{"ordf", 0xAA},{"ordm", 0xBA},
123 : {NULL,0}
124 : };
125 244 : static int cp_to_utf8(unsigned cp, char *out) {
126 244 : if (cp < 0x80) { out[0]=(char)cp; return 1; }
127 122 : if (cp < 0x800) { out[0]=(char)(0xC0|(cp>>6)); out[1]=(char)(0x80|(cp&0x3F)); return 2; }
128 61 : if (cp < 0x10000) {
129 61 : out[0]=(char)(0xE0|(cp>>12)); out[1]=(char)(0x80|((cp>>6)&0x3F));
130 61 : out[2]=(char)(0x80|(cp&0x3F)); return 3;
131 : }
132 0 : if (cp <= 0x10FFFF) {
133 0 : out[0]=(char)(0xF0|(cp>>18)); out[1]=(char)(0x80|((cp>>12)&0x3F));
134 0 : out[2]=(char)(0x80|((cp>>6)&0x3F)); out[3]=(char)(0x80|(cp&0x3F)); return 4;
135 : }
136 0 : return 0;
137 : }
138 1403 : static char *decode_entities(const char *in) {
139 1403 : if (!in) return NULL;
140 1403 : size_t len = strlen(in);
141 1403 : char *out = malloc(len * 4 + 1);
142 1403 : if (!out) return NULL;
143 1403 : size_t n = 0;
144 13542 : for (size_t i = 0; i < len; ) {
145 12139 : if (in[i] != '&') { out[n++] = in[i++]; continue; }
146 : /* find ';' within reasonable range */
147 244 : size_t j = i + 1;
148 976 : while (j < len && in[j] != ';' && j - i < 14) j++;
149 244 : if (j < len && in[j] == ';' && j > i + 1) {
150 244 : const char *e = in + i + 1;
151 244 : size_t el = j - i - 1;
152 244 : unsigned cp = 0; int matched = 0;
153 244 : if (el > 0 && e[0] == '#') {
154 0 : if (el > 1 && (e[1]=='x'||e[1]=='X')) {
155 0 : for (size_t k=2;k<el;k++) {
156 0 : unsigned char c=(unsigned char)e[k];
157 0 : if (c>='0'&&c<='9') cp=cp*16+(c-'0');
158 0 : else if (c>='a'&&c<='f') cp=cp*16+(c-'a'+10);
159 0 : else if (c>='A'&&c<='F') cp=cp*16+(c-'A'+10);
160 : }
161 : } else {
162 0 : for (size_t k=1;k<el;k++)
163 0 : if (e[k]>='0'&&e[k]<='9') cp=cp*10+(unsigned char)(e[k]-'0');
164 : }
165 0 : matched = (cp > 0);
166 244 : } else if (el < 10) {
167 244 : char nm[10]={0}; memcpy(nm,e,el);
168 3477 : for (int k=0; ENTITIES[k].name; k++)
169 3477 : if (strcmp(ENTITIES[k].name,nm)==0) { cp=ENTITIES[k].cp; matched=1; break; }
170 : }
171 244 : if (matched) {
172 244 : char utf8[5]={0}; int nb=cp_to_utf8(cp,utf8);
173 671 : for (int k=0;k<nb;k++) out[n++]=utf8[k];
174 244 : i = j + 1; continue;
175 : }
176 : }
177 0 : out[n++] = in[i++];
178 : }
179 1403 : out[n] = '\0';
180 1403 : return out;
181 : }
182 :
183 : /* ── Open-element stack ─────────────────────────────────────────────── */
184 :
185 : #define STACK_MAX 256
186 : typedef struct { HtmlNode *n[STACK_MAX]; int top; } Stack;
187 1586 : static void stk_push(Stack *s, HtmlNode *n) { if (s->top<STACK_MAX) s->n[s->top++]=n; }
188 3599 : static HtmlNode *stk_top(Stack *s) { return s->top>0 ? s->n[s->top-1] : NULL; }
189 61 : static void stk_pop(Stack *s) { if (s->top>0) s->top--; }
190 : /* Pop up to and including the nearest matching tag; return 1 if found */
191 1403 : static int stk_close(Stack *s, const char *tag) {
192 1464 : for (int i=s->top-1; i>=0; i--)
193 1464 : if (s->n[i]->tag && strcmp(s->n[i]->tag,tag)==0) { s->top=i; return 1; }
194 0 : return 0;
195 : }
196 :
197 : /* ── Parser ─────────────────────────────────────────────────────────── */
198 :
199 : typedef enum {
200 : PS_TEXT,
201 : PS_LT, /* saw '<' */
202 : PS_BANG, /* saw '<!' */
203 : PS_CMT, /* inside <!-- --> */
204 : PS_CMT_D1, /* saw '-' inside comment */
205 : PS_CMT_DD, /* saw '--' inside comment */
206 : PS_DECL, /* inside <!DOCTYPE ...> */
207 : PS_OPEN, /* reading open tag name */
208 : PS_CLOSE, /* reading close tag name */
209 : PS_ATTR_SEP, /* between attributes */
210 : PS_ATTR_NM, /* reading attribute name */
211 : PS_ATTR_EQ, /* saw '=' */
212 : PS_ATTR_VQ, /* in quoted attribute value */
213 : PS_ATTR_VU, /* in unquoted attribute value */
214 : } PState;
215 :
216 3111 : static void tolower_buf(char *s) {
217 11285 : for (; s && *s; s++) *s = (char)tolower((unsigned char)*s);
218 3111 : }
219 :
220 : /* Flush text buffer as a text node child of current stack top */
221 3355 : static void flush_text(Stack *stk, Buf *tb) {
222 3355 : if (!tb->d || !tb->n) { buf_free(tb); return; }
223 1403 : char *decoded = decode_entities(tb->d);
224 1403 : HtmlNode *tn = node_text(decoded ? decoded : strdup(tb->d));
225 1403 : if (!decoded) free(tb->d);
226 1403 : buf_free(tb);
227 1403 : if (tn) node_add_child(stk_top(stk), tn);
228 : }
229 :
230 : /* After completing a tag build: add to tree, push if non-void */
231 1647 : static void commit_elem(Stack *stk, HtmlNode *elem, int self_close) {
232 1647 : if (!elem) return;
233 1647 : if (is_auto_close(elem->tag)) {
234 549 : HtmlNode *top = stk_top(stk);
235 549 : if (top && top->tag && strcmp(top->tag, elem->tag) == 0)
236 61 : stk_pop(stk);
237 : }
238 1647 : node_add_child(stk_top(stk), elem);
239 1647 : if (!self_close && !is_void(elem->tag))
240 1525 : stk_push(stk, elem);
241 : }
242 :
243 61 : HtmlNode *html_parse(const char *html) {
244 61 : if (!html) return NULL;
245 :
246 61 : HtmlNode *root = node_elem(strdup("__root__"));
247 61 : if (!root) return NULL;
248 :
249 61 : Stack stk; stk.top = 0;
250 61 : stk_push(&stk, root);
251 :
252 61 : PState state = PS_TEXT;
253 61 : Buf tb = {0}; /* text accumulator */
254 61 : Buf nb = {0}; /* tag/attr name */
255 61 : Buf vb = {0}; /* attr value */
256 61 : char qc = '"';
257 :
258 61 : HtmlNode *cur = NULL; /* element being built */
259 :
260 61 : const char *p = html;
261 43676 : while (*p) {
262 43615 : char c = *p;
263 :
264 43615 : switch (state) {
265 :
266 : /* ── Text content ── */
267 16287 : case PS_TEXT:
268 16287 : if (c == '<') { flush_text(&stk, &tb); state = PS_LT; }
269 12993 : else buf_push(&tb, c);
270 16287 : break;
271 :
272 : /* ── Just saw '<' ── */
273 3294 : case PS_LT:
274 3294 : if (c == '/') { state = PS_CLOSE; }
275 1891 : else if (c == '!') { state = PS_BANG; }
276 1769 : else if (isalpha((unsigned char)c) || c == '_') {
277 1708 : buf_push(&nb, c); state = PS_OPEN;
278 : } else {
279 : /* Not a real tag — treat '<' as text */
280 61 : buf_push(&tb, '<'); buf_push(&tb, c); state = PS_TEXT;
281 : }
282 3294 : break;
283 :
284 : /* ── <!... ── */
285 122 : case PS_BANG:
286 122 : if (c == '-') {
287 : /* Peek: if next is also '-' it's a comment */
288 61 : if (p[1] == '-') { p++; state = PS_CMT; }
289 0 : else state = PS_DECL;
290 61 : } else state = PS_DECL;
291 122 : break;
292 :
293 427 : case PS_CMT:
294 427 : if (c == '-') state = PS_CMT_D1;
295 427 : break;
296 122 : case PS_CMT_D1:
297 122 : if (c == '-') state = PS_CMT_DD;
298 0 : else state = PS_CMT;
299 122 : break;
300 122 : case PS_CMT_DD:
301 122 : if (c == '>') state = PS_TEXT;
302 61 : else if (c != '-') state = PS_CMT;
303 122 : break;
304 732 : case PS_DECL:
305 732 : if (c == '>') state = PS_TEXT;
306 732 : break;
307 :
308 : /* ── Close tag name ── */
309 5063 : case PS_CLOSE:
310 5063 : if (isalnum((unsigned char)c) || c == '-' || c == '_' || c == ':' || c == '.') {
311 3660 : buf_push(&nb, c);
312 1403 : } else if (c == '>') {
313 1403 : if (nb.d) { tolower_buf(nb.d); stk_close(&stk, nb.d); }
314 1403 : buf_free(&nb);
315 1403 : state = PS_TEXT;
316 : }
317 : /* Skip whitespace and other chars inside </tag > */
318 5063 : break;
319 :
320 : /* ── Open tag name ── */
321 4514 : case PS_OPEN: {
322 4514 : int done = 0;
323 4514 : if (isalnum((unsigned char)c) || c == '-' || c == '_' || c == ':' || c == '.') {
324 2806 : buf_push(&nb, c);
325 : } else {
326 1708 : done = 1;
327 : }
328 4514 : if (done && nb.d) {
329 1708 : tolower_buf(nb.d);
330 :
331 : /* script / style: skip opening tag then body entirely */
332 1708 : if (strcmp(nb.d, "script") == 0 || strcmp(nb.d, "style") == 0) {
333 : char close_tag[16];
334 61 : snprintf(close_tag, sizeof(close_tag), "</%s", nb.d);
335 61 : buf_free(&nb);
336 : /* Skip to end of opening tag */
337 61 : while (*p && *p != '>') p++;
338 61 : if (*p) p++; /* skip '>' */
339 : /* Find closing tag (case-insensitive) */
340 61 : const char *end = strcasestr(p, close_tag);
341 61 : if (end) {
342 61 : p = end + strlen(close_tag);
343 61 : while (*p && *p != '>') p++;
344 : /* p now points at '>' of closing tag */
345 : } else {
346 0 : p += strlen(p); /* skip to end */
347 0 : if (*p) {} /* p already at '\0' */
348 : }
349 61 : state = PS_TEXT;
350 61 : break;
351 : }
352 :
353 1647 : char *tname = buf_take(&nb);
354 1647 : cur = node_elem(tname);
355 1647 : if (!cur) { state = PS_TEXT; break; }
356 :
357 1647 : if (c == '>') {
358 1281 : commit_elem(&stk, cur, 0); cur = NULL; state = PS_TEXT;
359 366 : } else if (c == '/') {
360 0 : commit_elem(&stk, cur, 1); cur = NULL;
361 0 : while (*p && *p != '>') p++;
362 0 : state = PS_TEXT;
363 366 : } else if (isspace((unsigned char)c)) {
364 366 : state = PS_ATTR_SEP;
365 : } else {
366 : /* Attribute name starting immediately */
367 0 : buf_push(&nb, c); state = PS_ATTR_NM;
368 : }
369 : }
370 4453 : break;
371 : }
372 :
373 : /* ── Between attributes ── */
374 732 : case PS_ATTR_SEP:
375 732 : if (c == '>') {
376 244 : commit_elem(&stk, cur, 0); cur = NULL; state = PS_TEXT;
377 488 : } else if (c == '/') {
378 0 : commit_elem(&stk, cur, 1); cur = NULL;
379 0 : while (*p && *p != '>') p++;
380 0 : state = PS_TEXT;
381 488 : } else if (!isspace((unsigned char)c)) {
382 427 : buf_push(&nb, c); state = PS_ATTR_NM;
383 : }
384 732 : break;
385 :
386 : /* ── Attribute name ── */
387 2074 : case PS_ATTR_NM:
388 2074 : if (c == '=') { state = PS_ATTR_EQ; }
389 1708 : else if (c == '>') {
390 : /* Boolean attr */
391 61 : if (cur && nb.d && nb.n > 0)
392 61 : attr_prepend(cur, buf_take(&nb), strdup(""));
393 0 : else buf_free(&nb);
394 61 : commit_elem(&stk, cur, 0); cur = NULL; state = PS_TEXT;
395 1647 : } else if (isspace((unsigned char)c)) {
396 0 : if (cur && nb.d && nb.n > 0)
397 0 : attr_prepend(cur, buf_take(&nb), strdup(""));
398 0 : else buf_free(&nb);
399 0 : state = PS_ATTR_SEP;
400 : } else {
401 1647 : buf_push(&nb, c);
402 : }
403 2074 : break;
404 :
405 : /* ── After '=' ── */
406 366 : case PS_ATTR_EQ:
407 366 : if (c == '"' || c == '\'') { qc = c; state = PS_ATTR_VQ; }
408 61 : else if (!isspace((unsigned char)c)) { buf_push(&vb, c); state = PS_ATTR_VU; }
409 366 : break;
410 :
411 : /* ── Quoted attribute value ── */
412 9577 : case PS_ATTR_VQ:
413 9577 : if (c == qc) {
414 305 : if (cur) attr_prepend(cur, buf_take(&nb), buf_take(&vb));
415 0 : else { buf_free(&nb); buf_free(&vb); }
416 305 : state = PS_ATTR_SEP;
417 9272 : } else buf_push(&vb, c);
418 9577 : break;
419 :
420 : /* ── Unquoted attribute value ── */
421 183 : case PS_ATTR_VU:
422 183 : if (isspace((unsigned char)c)) {
423 0 : if (cur) attr_prepend(cur, buf_take(&nb), buf_take(&vb));
424 0 : else { buf_free(&nb); buf_free(&vb); }
425 0 : state = PS_ATTR_SEP;
426 183 : } else if (c == '>') {
427 61 : if (cur) attr_prepend(cur, buf_take(&nb), buf_take(&vb));
428 0 : else { buf_free(&nb); buf_free(&vb); }
429 61 : commit_elem(&stk, cur, 0); cur = NULL; state = PS_TEXT;
430 122 : } else buf_push(&vb, c);
431 183 : break;
432 :
433 : } /* switch */
434 :
435 43615 : if (*p) p++;
436 0 : else break;
437 : } /* while */
438 :
439 61 : flush_text(&stk, &tb);
440 61 : if (cur) html_node_free(cur); /* partially built element */
441 61 : buf_free(&nb); buf_free(&vb);
442 61 : return root;
443 : }
|
