Debian Codegraph @

src/html-parse.c

raw
1 /* HTML parser for Wget.
2 Copyright (C) 1998-2011, 2015, 2018-2024 Free Software Foundation,
3 Inc.
4
5 This file is part of GNU Wget.
6
7 GNU Wget is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3 of the License, or (at
10 your option) any later version.
11
12 GNU Wget is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with Wget. If not, see <http://www.gnu.org/licenses/>.
19
20 Additional permission under GNU GPL version 3 section 7
21
22 If you modify this program, or any covered work, by linking or
23 combining it with the OpenSSL project's OpenSSL library (or a
24 modified version of that library), containing parts covered by the
25 terms of the OpenSSL or SSLeay licenses, the Free Software Foundation
26 grants you additional permission to convey the resulting work.
27 Corresponding Source for a non-source form of such a combination
28 shall include the source code for the parts of OpenSSL used as well
29 as that of the covered work. */
30
31 /* The only entry point to this module is map_html_tags(), which see. */
32
33 /* TODO:
34
35 - Allow hooks for callers to process contents outside tags. This
36 is needed to implement handling <style> and <script>. The
37 taginfo structure already carries the information about where the
38 tags are, but this is not enough, because one would also want to
39 skip the comments. (The funny thing is that for <style> and
40 <script> you *don't* want to skip comments!)
41
42 - Create a test suite for regression testing. */
43
44 /* HISTORY:
45
46 This is the third HTML parser written for Wget. The first one was
47 written some time during the Geturl 1.0 beta cycle, and was very
48 inefficient and buggy. It also contained some very complex code to
49 remember a list of parser states, because it was supposed to be
50 reentrant.
51
52 The second HTML parser was written for Wget 1.4 (the first version
53 by the name `Wget'), and was a complete rewrite. Although the new
54 parser behaved much better and made no claims of reentrancy, it
55 still shared many of the fundamental flaws of the old version -- it
56 only regarded HTML in terms tag-attribute pairs, where the
57 attribute's value was a URL to be returned. Any other property of
58 HTML, such as <base href=...>, or strange way to specify a URL,
59 such as <meta http-equiv=Refresh content="0; URL=..."> had to be
60 crudely hacked in -- and the caller had to be aware of these hacks.
61 Like its predecessor, this parser did not support HTML comments.
62
63 After Wget 1.5.1 was released, I set out to write a third HTML
64 parser. The objectives of the new parser were to: (1) provide a
65 clean way to analyze HTML lexically, (2) separate interpretation of
66 the markup from the parsing process, (3) be as correct as possible,
67 e.g. correctly skipping comments and other SGML declarations, (4)
68 understand the most common errors in markup and skip them or be
69 relaxed towrds them, and (5) be reasonably efficient (no regexps,
70 minimum copying and minimum or no heap allocation).
71
72 I believe this parser meets all of the above goals. It is
73 reasonably well structured, and could be relatively easily
74 separated from Wget and used elsewhere. While some of its
75 intrinsic properties limit its value as a general-purpose HTML
76 parser, I believe that, with minimum modifications, it could serve
77 as a backend for one.
78
79 Due to time and other constraints, this parser was not integrated
80 into Wget until the version 1.7. */
81
82 /* DESCRIPTION:
83
84 The single entry point of this parser is map_html_tags(), which
85 works by calling a function you specify for each tag. The function
86 gets called with the pointer to a structure describing the tag and
87 its attributes. */
88
89 /* To test as standalone, compile with `-DSTANDALONE -I.'. You'll
90 still need Wget headers to compile. */
91
92 #include "wget.h"
93
94 #ifdef STANDALONE
95 # define I_REALLY_WANT_CTYPE_MACROS
96 #endif
97
98 #include <stdio.h>
99 #include <stdlib.h>
100 #include <string.h>
101 #include <assert.h>
102
103 #include "utils.h"
104 #include "html-parse.h"
105
106 #ifdef STANDALONE
107 # undef xmalloc
108 # undef xrealloc
109 # undef xfree
110 # define xmalloc malloc
111 # define xrealloc realloc
112 # define xfree free
113
114 # undef c_isspace
115 # undef c_isdigit
116 # undef c_isxdigit
117 # undef c_isalpha
118 # undef c_isalnum
119 # undef c_tolower
120 # undef c_toupper
121
122 # define c_isspace(x) isspace (x)
123 # define c_isdigit(x) isdigit (x)
124 # define c_isxdigit(x) isxdigit (x)
125 # define c_isalpha(x) isalpha (x)
126 # define c_isalnum(x) isalnum (x)
127 # define c_tolower(x) tolower (x)
128 # define c_toupper(x) toupper (x)
129
130 struct hash_table {
131 int dummy;
132 };
133 static void *
134 hash_table_get (const struct hash_table *ht, void *ptr)
135 {
136 return ptr;
137 }
138 #else /* not STANDALONE */
139 # include "hash.h"
140 #endif
141
142 /* Pool support. A pool is a resizable chunk of memory. It is first
143 allocated on the stack, and moved to the heap if it needs to be
144 larger than originally expected. map_html_tags() uses it to store
145 the zero-terminated names and values of tags and attributes.
146
147 Thus taginfo->name, and attr->name and attr->value for each
148 attribute, do not point into separately allocated areas, but into
149 different parts of the pool, separated only by terminating zeros.
150 This ensures minimum amount of allocation and, for most tags, no
151 allocation because the entire pool is kept on the stack. */
152
153 struct pool {
154 char *contents; /* pointer to the contents. */
155 int size; /* size of the pool. */
156 int tail; /* next available position index. */
157 bool resized; /* whether the pool has been resized
158 using malloc. */
159
160 char *orig_contents; /* original pool contents, usually
161 stack-allocated. used by POOL_FREE
162 to restore the pool to the initial
163 state. */
164 int orig_size;
165 };
166
167 /* Initialize the pool to hold INITIAL_SIZE bytes of storage. */
168
169 #define POOL_INIT(p, initial_storage, initial_size) do { \
170 struct pool *P = (p); \
171 P->contents = (initial_storage); \
172 P->size = (initial_size); \
173 P->tail = 0; \
174 P->resized = false; \
175 P->orig_contents = P->contents; \
176 P->orig_size = P->size; \
177 } while (0)
178
179 /* Grow the pool to accommodate at least SIZE new bytes. If the pool
180 already has room to accommodate SIZE bytes of data, this is a no-op. */
181
182 #define POOL_GROW(p, increase) \
183 GROW_ARRAY ((p)->contents, (p)->size, (p)->tail + (increase), \
184 (p)->resized, char)
185
186 /* Append text in the range [beg, end) to POOL. No zero-termination
187 is done. */
188
189 #define POOL_APPEND(p, beg, end) do { \
190 const char *PA_beg = (beg); \
191 int PA_size = (end) - PA_beg; \
192 POOL_GROW (p, PA_size); \
193 memcpy ((p)->contents + (p)->tail, PA_beg, PA_size); \
194 (p)->tail += PA_size; \
195 } while (0)
196
197 /* Append one character to the pool. Can be used to zero-terminate
198 pool strings. */
199
200 #define POOL_APPEND_CHR(p, ch) do { \
201 char PAC_char = (ch); \
202 POOL_GROW (p, 1); \
203 (p)->contents[(p)->tail++] = PAC_char; \
204 } while (0)
205
206 /* Forget old pool contents. The allocated memory is not freed. */
207 #define POOL_REWIND(p) (p)->tail = 0
208
209 /* Free heap-allocated memory for contents of POOL. This calls
210 xfree() if the memory was allocated through malloc. It also
211 restores `contents' and `size' to their original, pre-malloc
212 values. That way after POOL_FREE, the pool is fully usable, just
213 as if it were freshly initialized with POOL_INIT. */
214
215 #define POOL_FREE(p) do { \
216 struct pool *P = p; \
217 if (P->resized) \
218 xfree (P->contents); \
219 P->contents = P->orig_contents; \
220 P->size = P->orig_size; \
221 P->tail = 0; \
222 P->resized = false; \
223 } while (0)
224
225 /* Used for small stack-allocated memory chunks that might grow. Like
226 DO_REALLOC, this macro grows BASEVAR as necessary to take
227 NEEDED_SIZE items of TYPE.
228
229 The difference is that on the first resize, it will use
230 malloc+memcpy rather than realloc. That way you can stack-allocate
231 the initial chunk, and only resort to heap allocation if you
232 stumble upon large data.
233
234 After the first resize, subsequent ones are performed with realloc,
235 just like DO_REALLOC. */
236
237 #define GROW_ARRAY(basevar, sizevar, needed_size, resized, type) do { \
238 long ga_needed_size = (needed_size); \
239 long ga_newsize = (sizevar); \
240 while (ga_newsize < ga_needed_size) \
241 ga_newsize <<= 1; \
242 if (ga_newsize != (sizevar)) \
243 { \
244 if (resized) \
245 basevar = xrealloc (basevar, ga_newsize * sizeof (type)); \
246 else \
247 { \
248 void *ga_new = xmalloc (ga_newsize * sizeof (type)); \
249 memcpy (ga_new, basevar, (sizevar) * sizeof (type)); \
250 (basevar) = ga_new; \
251 resized = true; \
252 } \
253 (sizevar) = ga_newsize; \
254 } \
255 } while (0)
256
257 /* Test whether n+1-sized entity name fits in P. We don't support
258 IE-style non-terminated entities, e.g. "&ltfoo" -> "<foo".
259 However, "&lt;foo" will work, as will "&lt!foo", "&lt", etc. In
260 other words an entity needs to be terminated by either a
261 non-alphanumeric or the end of string. */
262 #define FITS(p, n) (p + n == end || (p + n < end && !c_isalnum (p[n])))
263
264 /* Macros that test entity names by returning true if P is followed by
265 the specified characters. */
266 #define ENT1(p, c0) (FITS (p, 1) && p[0] == c0)
267 #define ENT2(p, c0, c1) (FITS (p, 2) && p[0] == c0 && p[1] == c1)
268 #define ENT3(p, c0, c1, c2) (FITS (p, 3) && p[0]==c0 && p[1]==c1 && p[2]==c2)
269
270 /* Increment P by INC chars. If P lands at a semicolon, increment it
271 past the semicolon. This ensures that e.g. "&lt;foo" is converted
272 to "<foo", but "&lt,foo" to "<,foo". */
273 #define SKIP_SEMI(p, inc) (p += inc, p < end && *p == ';' ? ++p : p)
274
275 struct tagstack_item {
276 const char *tagname_begin;
277 const char *tagname_end;
278 const char *contents_begin;
279 struct tagstack_item *prev;
280 struct tagstack_item *next;
281 };
282
283 static struct tagstack_item *
284 tagstack_push (struct tagstack_item **head, struct tagstack_item **tail)
285 {
286 struct tagstack_item *ts = xmalloc(sizeof(struct tagstack_item));
287 if (*head == NULL)
288 {
289 *head = *tail = ts;
290 ts->prev = ts->next = NULL;
291 }
292 else
293 {
294 (*tail)->next = ts;
295 ts->prev = *tail;
296 *tail = ts;
297 ts->next = NULL;
298 }
299
300 return ts;
301 }
302
303 /* remove ts and everything after it from the stack */
304 static void
305 tagstack_pop (struct tagstack_item **head, struct tagstack_item **tail,
306 struct tagstack_item *ts)
307 {
308 if (*head == NULL)
309 return;
310
311 if (ts == *tail)
312 {
313 if (ts == *head)
314 {
315 xfree (ts);
316 *head = *tail = NULL;
317 }
318 else
319 {
320 ts->prev->next = NULL;
321 *tail = ts->prev;
322 xfree (ts);
323 }
324 }
325 else
326 {
327 if (ts == *head)
328 {
329 *head = NULL;
330 }
331 *tail = ts->prev;
332
333 if (ts->prev)
334 {
335 ts->prev->next = NULL;
336 }
337 while (ts)
338 {
339 struct tagstack_item *p = ts->next;
340 xfree (ts);
341 ts = p;
342 }
343 }
344 }
345
346 static struct tagstack_item *
347 tagstack_find (struct tagstack_item *tail, const char *tagname_begin,
348 const char *tagname_end)
349 {
350 int len = tagname_end - tagname_begin;
351 while (tail)
352 {
353 if (len == (tail->tagname_end - tail->tagname_begin))
354 {
355 if (0 == strncasecmp (tail->tagname_begin, tagname_begin, len))
356 return tail;
357 }
358 tail = tail->prev;
359 }
360 return NULL;
361 }
362
363 /* Decode the HTML character entity at *PTR, considering END to be end
364 of buffer. It is assumed that the "&" character that marks the
365 beginning of the entity has been seen at *PTR-1. If a recognized
366 ASCII entity is seen, it is returned, and *PTR is moved to the end
367 of the entity. Otherwise, -1 is returned and *PTR left unmodified.
368
369 The recognized entities are: &lt, &gt, &amp, &apos, and &quot. */
370
371 static int
372 decode_entity (const char **ptr, const char *end)
373 {
374 const char *p = *ptr;
375 int value = -1;
376
377 if (++p == end)
378 return -1;
379
380 switch (*p++)
381 {
382 case '#':
383 /* Process numeric entities "&#DDD;" and "&#xHH;". */
384 {
385 int digits = 0;
386 value = 0;
387 if (*p == 'x')
388 for (++p; value < 256 && p < end && c_isxdigit (*p); p++, digits++)
389 value = (value << 4) + _unhex (*p);
390 else
391 for (; value < 256 && p < end && c_isdigit (*p); p++, digits++)
392 value = (value * 10) + (*p - '0');
393 if (!digits)
394 return -1;
395 /* Don't interpret 128+ codes and NUL because we cannot
396 portably reinserted them into HTML. */
397 if (!value || (value & ~0x7f))
398 return -1;
399 *ptr = SKIP_SEMI (p, 0);
400 return value;
401 }
402 /* Process named ASCII entities. */
403 case 'g':
404 if (ENT1 (p, 't'))
405 value = '>', *ptr = SKIP_SEMI (p, 1);
406 break;
407 case 'l':
408 if (ENT1 (p, 't'))
409 value = '<', *ptr = SKIP_SEMI (p, 1);
410 break;
411 case 'a':
412 if (ENT2 (p, 'm', 'p'))
413 value = '&', *ptr = SKIP_SEMI (p, 2);
414 else if (ENT3 (p, 'p', 'o', 's'))
415 /* handle &apos for the sake of the XML/XHTML crowd. */
416 value = '\'', *ptr = SKIP_SEMI (p, 3);
417 break;
418 case 'q':
419 if (ENT3 (p, 'u', 'o', 't'))
420 value = '\"', *ptr = SKIP_SEMI (p, 3);
421 break;
422 }
423 return value;
424 }
425 #undef ENT1
426 #undef ENT2
427 #undef ENT3
428 #undef FITS
429 #undef SKIP_SEMI
430
431 enum {
432 AP_DOWNCASE = 1,
433 AP_DECODE_ENTITIES = 2,
434 AP_TRIM_BLANKS = 4
435 };
436
437 /* Copy the text in the range [BEG, END) to POOL, optionally
438 performing operations specified by FLAGS. FLAGS may be any
439 combination of AP_DOWNCASE, AP_DECODE_ENTITIES and AP_TRIM_BLANKS
440 with the following meaning:
441
442 * AP_DOWNCASE -- downcase all the letters;
443
444 * AP_DECODE_ENTITIES -- decode the named and numeric entities in
445 the ASCII range when copying the string.
446
447 * AP_TRIM_BLANKS -- ignore blanks at the beginning and at the end
448 of text, as well as embedded newlines. */
449
450 static void
451 convert_and_copy (struct pool *pool, const char *beg, const char *end, int flags)
452 {
453 int old_tail = pool->tail;
454
455 /* Skip blanks if required. We must do this before entities are
456 processed, so that blanks can still be inserted as, for instance,
457 `&#32;'. */
458 if (flags & AP_TRIM_BLANKS)
459 {
460 while (beg < end && c_isspace (*beg))
461 ++beg;
462 while (end > beg && c_isspace (end[-1]))
463 --end;
464 }
465
466 if (flags & AP_DECODE_ENTITIES)
467 {
468 /* Grow the pool, then copy the text to the pool character by
469 character, processing the encountered entities as we go
470 along.
471
472 It's safe (and necessary) to grow the pool in advance because
473 processing the entities can only *shorten* the string, it can
474 never lengthen it. */
475 const char *from = beg;
476 char *to;
477 bool squash_newlines = !!(flags & AP_TRIM_BLANKS);
478
479 POOL_GROW (pool, end - beg);
480 to = pool->contents + pool->tail;
481
482 while (from < end)
483 {
484 if (*from == '&')
485 {
486 int entity = decode_entity (&from, end);
487 if (entity != -1)
488 *to++ = entity;
489 else
490 *to++ = *from++;
491 }
492 else if ((*from == '\n' || *from == '\r') && squash_newlines)
493 ++from;
494 else
495 *to++ = *from++;
496 }
497 /* Verify that we haven't exceeded the original size. (It
498 shouldn't happen, hence the assert.) */
499 assert (to - (pool->contents + pool->tail) <= end - beg);
500
501 /* Make POOL's tail point to the position following the string
502 we've written. */
503 pool->tail = to - pool->contents;
504 POOL_APPEND_CHR (pool, '\0');
505 }
506 else
507 {
508 /* Just copy the text to the pool. */
509 POOL_APPEND (pool, beg, end);
510 POOL_APPEND_CHR (pool, '\0');
511 }
512
513 if (flags & AP_DOWNCASE)
514 {
515 char *p = pool->contents + old_tail;
516 for (; *p; p++)
517 *p = c_tolower (*p);
518 }
519 }
520
521 /* Originally we used to adhere to rfc 1866 here, and allowed only
522 letters, digits, periods, and hyphens as names (of tags or
523 attributes). However, this broke too many pages which used
524 proprietary or strange attributes, e.g. <img src="a.gif"
525 v:shapes="whatever">.
526
527 So now we allow any character except:
528 * whitespace
529 * 8-bit and control chars
530 * characters that clearly cannot be part of name:
531 '=', '<', '>', '/'.
532
533 This only affects attribute and tag names; attribute values allow
534 an even greater variety of characters. */
535
536 #define NAME_CHAR_P(x) ((x) > 32 && (x) < 127 \
537 && (x) != '=' && (x) != '<' && (x) != '>' \
538 && (x) != '/')
539
540 #ifdef STANDALONE
541 static int comment_backout_count;
542 #endif
543
544 /* Advance over an SGML declaration, such as <!DOCTYPE ...>. In
545 strict comments mode, this is used for skipping over comments as
546 well.
547
548 To recap: any SGML declaration may have comments associated with
549 it, e.g.
550 <!MY-DECL -- isn't this fun? -- foo bar>
551
552 An HTML comment is merely an empty declaration (<!>) with a comment
553 attached, like this:
554 <!-- some stuff here -->
555
556 Several comments may be embedded in one comment declaration:
557 <!-- have -- -- fun -->
558
559 Whitespace is allowed between and after the comments, but not
560 before the first comment. Additionally, this function attempts to
561 handle double quotes in SGML declarations correctly. */
562
563 static const char *
564 advance_declaration (const char *beg, const char *end)
565 {
566 const char *p = beg;
567 char quote_char = '\0'; /* shut up, gcc! */
568 char ch;
569
570 enum {
571 AC_S_DONE,
572 AC_S_BACKOUT,
573 AC_S_BANG,
574 AC_S_DEFAULT,
575 AC_S_DCLNAME,
576 AC_S_DASH1,
577 AC_S_DASH2,
578 AC_S_COMMENT,
579 AC_S_DASH3,
580 AC_S_DASH4,
581 AC_S_QUOTE1,
582 AC_S_IN_QUOTE,
583 AC_S_QUOTE2
584 } state = AC_S_BANG;
585
586 if (beg == end)
587 return beg;
588 ch = *p++;
589
590 /* It looked like a good idea to write this as a state machine, but
591 now I wonder... */
592
593 while (state != AC_S_DONE && state != AC_S_BACKOUT)
594 {
595 if (p == end)
596 state = AC_S_BACKOUT;
597 switch (state)
598 {
599 case AC_S_DONE:
600 case AC_S_BACKOUT:
601 break;
602 case AC_S_BANG:
603 if (ch == '!')
604 {
605 ch = *p++;
606 state = AC_S_DEFAULT;
607 }
608 else
609 state = AC_S_BACKOUT;
610 break;
611 case AC_S_DEFAULT:
612 switch (ch)
613 {
614 case '-':
615 state = AC_S_DASH1;
616 break;
617 case ' ':
618 case '\t':
619 case '\r':
620 case '\n':
621 ch = *p++;
622 break;
623 case '<':
624 case '>':
625 state = AC_S_DONE;
626 break;
627 case '\'':
628 case '\"':
629 state = AC_S_QUOTE1;
630 break;
631 default:
632 if (NAME_CHAR_P (ch))
633 state = AC_S_DCLNAME;
634 else
635 state = AC_S_BACKOUT;
636 break;
637 }
638 break;
639 case AC_S_DCLNAME:
640 if (ch == '-')
641 state = AC_S_DASH1;
642 else if (NAME_CHAR_P (ch))
643 ch = *p++;
644 else
645 state = AC_S_DEFAULT;
646 break;
647 case AC_S_QUOTE1:
648 /* We must use 0x22 because broken assert macros choke on
649 '"' and '\"'. */
650 assert (ch == '\'' || ch == 0x22);
651 quote_char = ch; /* cheating -- I really don't feel like
652 introducing more different states for
653 different quote characters. */
654 ch = *p++;
655 state = AC_S_IN_QUOTE;
656 break;
657 case AC_S_IN_QUOTE:
658 if (ch == quote_char)
659 state = AC_S_QUOTE2;
660 else
661 ch = *p++;
662 break;
663 case AC_S_QUOTE2:
664 assert (ch == quote_char);
665 ch = *p++;
666 state = AC_S_DEFAULT;
667 break;
668 case AC_S_DASH1:
669 assert (ch == '-');
670 ch = *p++;
671 state = AC_S_DASH2;
672 break;
673 case AC_S_DASH2:
674 switch (ch)
675 {
676 case '-':
677 ch = *p++;
678 state = AC_S_COMMENT;
679 break;
680 default:
681 state = AC_S_BACKOUT;
682 }
683 break;
684 case AC_S_COMMENT:
685 switch (ch)
686 {
687 case '-':
688 state = AC_S_DASH3;
689 break;
690 default:
691 ch = *p++;
692 break;
693 }
694 break;
695 case AC_S_DASH3:
696 assert (ch == '-');
697 ch = *p++;
698 state = AC_S_DASH4;
699 break;
700 case AC_S_DASH4:
701 switch (ch)
702 {
703 case '-':
704 ch = *p++;
705 state = AC_S_DEFAULT;
706 break;
707 default:
708 state = AC_S_COMMENT;
709 break;
710 }
711 break;
712 }
713 }
714
715 if (state == AC_S_BACKOUT)
716 {
717 #ifdef STANDALONE
718 ++comment_backout_count;
719 #endif
720 return beg + 1;
721 }
722 return p;
723 }
724
725 /* Find the first occurrence of the substring "-->" in [BEG, END) and
726 return the pointer to the character after the substring. If the
727 substring is not found, return NULL. */
728
729 static const char *
730 find_comment_end (const char *beg, const char *end)
731 {
732 /* Open-coded Boyer-Moore search for "-->". Examine the third char;
733 if it's not '>' or '-', advance by three characters. Otherwise,
734 look at the preceding characters and try to find a match. */
735
736 const char *p = beg - 1;
737
738 while ((p += 3) < end)
739 switch (p[0])
740 {
741 case '>':
742 if (p[-1] == '-' && p[-2] == '-')
743 return p + 1;
744 break;
745 case '-':
746 at_dash:
747 if (p[-1] == '-')
748 {
749 at_dash_dash:
750 if (++p == end) return NULL;
751 switch (p[0])
752 {
753 case '>': return p + 1;
754 case '-': goto at_dash_dash;
755 }
756 }
757 else
758 {
759 if ((p += 2) >= end) return NULL;
760 switch (p[0])
761 {
762 case '>':
763 if (p[-1] == '-')
764 return p + 1;
765 break;
766 case '-':
767 goto at_dash;
768 }
769 }
770 }
771 return NULL;
772 }
773
774 /* Return true if the string containing of characters inside [b, e) is
775 present in hash table HT. */
776
777 static bool
778 name_allowed (const struct hash_table *ht, const char *b, const char *e)
779 {
780 char buf[256], *copy;
781 size_t len = e - b;
782 bool ret;
783
784 if (!ht)
785 return true;
786
787 if (len < sizeof (buf))
788 copy = buf;
789 else
790 copy = xmalloc (len + 1);
791
792 memcpy (copy, b, len);
793 copy[len] = 0;
794
795 ret = hash_table_get (ht, copy) != NULL;
796
797 if (copy != buf)
798 xfree (copy);
799
800 return ret;
801 }
802
803 /* Advance P (a char pointer), with the explicit intent of being able
804 to read the next character. If this is not possible, go to finish. */
805
806 #define ADVANCE(p) do { \
807 ++p; \
808 if (p >= end) \
809 goto finish; \
810 } while (0)
811
812 /* Skip whitespace, if any. */
813
814 #define SKIP_WS(p) do { \
815 while (c_isspace (*p)) { \
816 ADVANCE (p); \
817 } \
818 } while (0)
819
820 #ifdef STANDALONE
821 static int tag_backout_count;
822 #endif
823
824 /* Map MAPFUN over HTML tags in TEXT, which is SIZE characters long.
825 MAPFUN will be called with two arguments: pointer to an initialized
826 struct taginfo, and MAPARG.
827
828 ALLOWED_TAGS and ALLOWED_ATTRIBUTES are hash tables the keys of
829 which are the tags and attribute names that this function should
830 use. If ALLOWED_TAGS is NULL, all tags are processed; if
831 ALLOWED_ATTRIBUTES is NULL, all attributes are returned.
832
833 (Obviously, the caller can filter out unwanted tags and attributes
834 just as well, but this is just an optimization designed to avoid
835 unnecessary copying of tags/attributes which the caller doesn't
836 care about.) */
837
838 void
839 map_html_tags (const char *text, int size,
840 void (*mapfun) (struct taginfo *, void *), void *maparg,
841 int flags,
842 const struct hash_table *allowed_tags,
843 const struct hash_table *allowed_attributes)
844 {
845 /* storage for strings passed to MAPFUN callback; if 256 bytes is
846 too little, POOL_APPEND allocates more with malloc. */
847 char pool_initial_storage[256];
848 struct pool pool;
849
850 const char *p = text;
851 const char *end = text + size;
852
853 struct attr_pair attr_pair_initial_storage[8];
854 int attr_pair_size = countof (attr_pair_initial_storage);
855 bool attr_pair_resized = false;
856 struct attr_pair *pairs = attr_pair_initial_storage;
857
858 struct tagstack_item *head = NULL;
859 struct tagstack_item *tail = NULL;
860
861 if (!size)
862 return;
863
864 POOL_INIT (&pool, pool_initial_storage, countof (pool_initial_storage));
865
866 {
867 int nattrs, end_tag;
868 const char *tag_name_begin, *tag_name_end;
869 const char *tag_start_position;
870 bool uninteresting_tag;
871
872 look_for_tag:
873 POOL_REWIND (&pool);
874
875 nattrs = 0;
876 end_tag = 0;
877
878 /* Find beginning of tag. We use memchr() instead of the usual
879 looping with ADVANCE() for speed. */
880 p = memchr (p, '<', end - p);
881 if (!p)
882 goto finish;
883
884 tag_start_position = p;
885 ADVANCE (p);
886
887 /* Establish the type of the tag (start-tag, end-tag or
888 declaration). */
889 if (*p == '!')
890 {
891 if (!(flags & MHT_STRICT_COMMENTS)
892 && p + 3 < end && p[1] == '-' && p[2] == '-')
893 {
894 /* If strict comments are not enforced and if we know
895 we're looking at a comment, simply look for the
896 terminating "-->". Non-strict is the default because
897 it works in other browsers and most HTML writers can't
898 be bothered with getting the comments right. */
899 const char *comment_end = find_comment_end (p + 3, end);
900 if (comment_end)
901 p = comment_end;
902 }
903 else
904 {
905 /* Either in strict comment mode or looking at a non-empty
906 declaration. Real declarations are much less likely to
907 be misused the way comments are, so advance over them
908 properly regardless of strictness. */
909 p = advance_declaration (p, end);
910 }
911 if (p == end)
912 goto finish;
913 goto look_for_tag;
914 }
915 else if (*p == '/')
916 {
917 end_tag = 1;
918 ADVANCE (p);
919 }
920 tag_name_begin = p;
921 while (NAME_CHAR_P (*p))
922 ADVANCE (p);
923 if (p == tag_name_begin)
924 goto look_for_tag;
925 tag_name_end = p;
926 SKIP_WS (p);
927
928 if (!end_tag)
929 {
930 struct tagstack_item *ts = tagstack_push (&head, &tail);
931 if (ts)
932 {
933 ts->tagname_begin = tag_name_begin;
934 ts->tagname_end = tag_name_end;
935 ts->contents_begin = NULL;
936 }
937 }
938
939 if (end_tag && *p != '>' && *p != '<')
940 goto backout_tag;
941
942 if (!name_allowed (allowed_tags, tag_name_begin, tag_name_end))
943 /* We can't just say "goto look_for_tag" here because we need
944 the loop below to properly advance over the tag's attributes. */
945 uninteresting_tag = true;
946 else
947 {
948 uninteresting_tag = false;
949 convert_and_copy (&pool, tag_name_begin, tag_name_end, AP_DOWNCASE);
950 }
951
952 /* Find the attributes. */
953 while (1)
954 {
955 const char *attr_name_begin, *attr_name_end;
956 const char *attr_value_begin, *attr_value_end;
957 const char *attr_raw_value_begin, *attr_raw_value_end;
958 int operation = AP_DOWNCASE; /* stupid compiler. */
959
960 SKIP_WS (p);
961
962 if (*p == '/')
963 {
964 /* A slash at this point means the tag is about to be
965 closed. This is legal in XML and has been popularized
966 in HTML via XHTML. */
967 /* <foo a=b c=d /> */
968 /* ^ */
969 ADVANCE (p);
970 SKIP_WS (p);
971 if (*p != '<' && *p != '>')
972 goto backout_tag;
973 }
974
975 /* Check for end of tag definition. */
976 if (*p == '<' || *p == '>')
977 break;
978
979 /* Establish bounds of attribute name. */
980 attr_name_begin = p; /* <foo bar ...> */
981 /* ^ */
982 while (NAME_CHAR_P (*p))
983 ADVANCE (p);
984 attr_name_end = p; /* <foo bar ...> */
985 /* ^ */
986 if (attr_name_begin == attr_name_end)
987 goto backout_tag;
988
989 /* Establish bounds of attribute value. */
990 SKIP_WS (p);
991
992 if (NAME_CHAR_P (*p) || *p == '/' || *p == '<' || *p == '>')
993 {
994 /* Minimized attribute syntax allows `=' to be omitted.
995 For example, <UL COMPACT> is a valid shorthand for <UL
996 COMPACT="compact">. Even if such attributes are not
997 useful to Wget, we need to support them, so that the
998 tags containing them can be parsed correctly. */
999 attr_raw_value_begin = attr_value_begin = attr_name_begin;
1000 attr_raw_value_end = attr_value_end = attr_name_end;
1001 }
1002 else if (*p == '=')
1003 {
1004 ADVANCE (p);
1005 SKIP_WS (p);
1006 if (*p == '\"' || *p == '\'')
1007 {
1008 bool newline_seen = false;
1009 char quote_char = *p;
1010 attr_raw_value_begin = p;
1011 ADVANCE (p);
1012 attr_value_begin = p; /* <foo bar="baz"> */
1013 /* ^ */
1014 while (*p != quote_char)
1015 {
1016 if (!newline_seen && *p == '\n')
1017 {
1018 /* If a newline is seen within the quotes, it
1019 is most likely that someone forgot to close
1020 the quote. In that case, we back out to
1021 the value beginning, and terminate the tag
1022 at either `>' or the delimiter, whichever
1023 comes first. Such a tag terminated at `>'
1024 is discarded. */
1025 p = attr_value_begin;
1026 newline_seen = true;
1027 continue;
1028 }
1029 else if (newline_seen && (*p == '<' || *p == '>'))
1030 break;
1031 ADVANCE (p);
1032 }
1033 attr_value_end = p; /* <foo bar="baz"> */
1034 /* ^ */
1035 if (*p == quote_char)
1036 ADVANCE (p);
1037 else
1038 goto look_for_tag;
1039 attr_raw_value_end = p; /* <foo bar="baz"> */
1040 /* ^ */
1041 operation = AP_DECODE_ENTITIES;
1042 if (flags & MHT_TRIM_VALUES)
1043 operation |= AP_TRIM_BLANKS;
1044 }
1045 else
1046 {
1047 attr_value_begin = p; /* <foo bar=baz> */
1048 /* ^ */
1049 /* According to SGML, a name token should consist only
1050 of alphanumerics, . and -. However, this is often
1051 violated by, for instance, `%' in `width=75%'.
1052 We'll be liberal and allow just about anything as
1053 an attribute value. */
1054 while (!c_isspace (*p) && *p != '<' && *p != '>')
1055 ADVANCE (p);
1056 attr_value_end = p; /* <foo bar=baz qux=quix> */
1057 /* ^ */
1058 if (attr_value_begin == attr_value_end)
1059 /* <foo bar=> */
1060 /* ^ */
1061 goto backout_tag;
1062 attr_raw_value_begin = attr_value_begin;
1063 attr_raw_value_end = attr_value_end;
1064 operation = AP_DECODE_ENTITIES;
1065 }
1066 }
1067 else
1068 {
1069 /* We skipped the whitespace and found something that is
1070 neither `=' nor the beginning of the next attribute's
1071 name. Back out. */
1072 goto backout_tag; /* <foo bar [... */
1073 /* ^ */
1074 }
1075
1076 /* If we're not interested in the tag, don't bother with any
1077 of the attributes. */
1078 if (uninteresting_tag)
1079 continue;
1080
1081 /* If we aren't interested in the attribute, skip it. We
1082 cannot do this test any sooner, because our text pointer
1083 needs to correctly advance over the attribute. */
1084 if (!name_allowed (allowed_attributes, attr_name_begin, attr_name_end))
1085 continue;
1086
1087 GROW_ARRAY (pairs, attr_pair_size, nattrs + 1, attr_pair_resized,
1088 struct attr_pair);
1089
1090 pairs[nattrs].name_pool_index = pool.tail;
1091 convert_and_copy (&pool, attr_name_begin, attr_name_end, AP_DOWNCASE);
1092
1093 pairs[nattrs].value_pool_index = pool.tail;
1094 convert_and_copy (&pool, attr_value_begin, attr_value_end, operation);
1095 pairs[nattrs].value_raw_beginning = attr_raw_value_begin;
1096 pairs[nattrs].value_raw_size = (attr_raw_value_end
1097 - attr_raw_value_begin);
1098 ++nattrs;
1099 }
1100
1101 if (!end_tag && tail && (tail->tagname_begin == tag_name_begin))
1102 {
1103 tail->contents_begin = p+1;
1104 }
1105
1106 if (uninteresting_tag)
1107 {
1108 ADVANCE (p);
1109 goto look_for_tag;
1110 }
1111
1112 /* By now, we have a valid tag with a name and zero or more
1113 attributes. Fill in the data and call the mapper function. */
1114 {
1115 int i;
1116 struct taginfo taginfo;
1117 struct tagstack_item *ts = NULL;
1118
1119 taginfo.name = pool.contents;
1120 taginfo.end_tag_p = end_tag;
1121 taginfo.nattrs = nattrs;
1122 /* We fill in the char pointers only now, when pool can no
1123 longer get realloc'ed. If we did that above, we could get
1124 hosed by reallocation. Obviously, after this point, the pool
1125 may no longer be grown. */
1126 for (i = 0; i < nattrs; i++)
1127 {
1128 pairs[i].name = pool.contents + pairs[i].name_pool_index;
1129 pairs[i].value = pool.contents + pairs[i].value_pool_index;
1130 }
1131 taginfo.attrs = pairs;
1132 taginfo.start_position = tag_start_position;
1133 taginfo.end_position = p + 1;
1134 taginfo.contents_begin = NULL;
1135 taginfo.contents_end = NULL;
1136
1137 if (end_tag)
1138 {
1139 ts = tagstack_find (tail, tag_name_begin, tag_name_end);
1140 if (ts)
1141 {
1142 if (ts->contents_begin)
1143 {
1144 taginfo.contents_begin = ts->contents_begin;
1145 taginfo.contents_end = tag_start_position;
1146 }
1147 tagstack_pop (&head, &tail, ts);
1148 }
1149 }
1150
1151 mapfun (&taginfo, maparg);
1152 if (*p != '<')
1153 ADVANCE (p);
1154 }
1155 goto look_for_tag;
1156
1157 backout_tag:
1158 #ifdef STANDALONE
1159 ++tag_backout_count;
1160 #endif
1161 /* The tag wasn't really a tag. Treat its contents as ordinary
1162 data characters. */
1163 p = tag_start_position + 1;
1164 goto look_for_tag;
1165 }
1166
1167 finish:
1168 POOL_FREE (&pool);
1169 if (attr_pair_resized)
1170 xfree (pairs);
1171 /* pop any tag stack that's left */
1172 tagstack_pop (&head, &tail, head);
1173 }
1174
1175 #undef ADVANCE
1176 #undef SKIP_WS
1177 #undef SKIP_NON_WS
1178
1179 #ifdef STANDALONE
1180 static void
1181 test_mapper (struct taginfo *taginfo, void *arg)
1182 {
1183 int i;
1184
1185 printf ("%s%s", taginfo->end_tag_p ? "/" : "", taginfo->name);
1186 for (i = 0; i < taginfo->nattrs; i++)
1187 printf (" %s=%s", taginfo->attrs[i].name, taginfo->attrs[i].value);
1188 putchar ('\n');
1189 ++*(int *)arg;
1190 }
1191
1192 int main ()
1193 {
1194 int size = 256;
1195 char *x = xmalloc (size);
1196 int length = 0;
1197 int read_count;
1198 int tag_counter = 0;
1199
1200 #ifdef ENABLE_NLS
1201 /* Set the current locale. */
1202 setlocale (LC_ALL, "");
1203 /* Set the text message domain. */
1204 bindtextdomain ("wget", LOCALEDIR);
1205 textdomain ("wget");
1206 #endif /* ENABLE_NLS */
1207
1208 while ((read_count = fread (x + length, 1, size - length, stdin)))
1209 {
1210 length += read_count;
1211 size <<= 1;
1212 x = xrealloc (x, size);
1213 }
1214
1215 map_html_tags (x, length, test_mapper, &tag_counter, 0, NULL, NULL);
1216 printf ("TAGS: %d\n", tag_counter);
1217 printf ("Tag backouts: %d\n", tag_backout_count);
1218 printf ("Comment backouts: %d\n", comment_backout_count);
1219 return 0;
1220 }
1221 #endif /* STANDALONE */