1 /* HTML parser for Wget.
2 Copyright (C) 1998, 2000, 2003 Free Software Foundation, Inc.
4 This file is part of GNU Wget.
6 GNU Wget is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or (at
9 your option) any later version.
11 GNU Wget is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with Wget; if not, write to the Free Software
18 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20 In addition, as a special exception, the Free Software Foundation
21 gives permission to link the code of its release of Wget with the
22 OpenSSL project's "OpenSSL" library (or with modified versions of it
23 that use the same license as the "OpenSSL" library), and distribute
24 the linked executables. You must obey the GNU General Public License
25 in all respects for all of the code used other than "OpenSSL". If you
26 modify this file, you may extend this exception to your version of the
27 file, but you are not obligated to do so. If you do not wish to do
28 so, delete this exception statement from your version. */
30 /* The only entry point to this module is map_html_tags(), which see. */
34 - Allow hooks for callers to process contents outside tags. This
35 is needed to implement handling <style> and <script>. The
36 taginfo structure already carries the information about where the
37 tags are, but this is not enough, because one would also want to
38 skip the comments. (The funny thing is that for <style> and
39 <script> you *don't* want to skip comments!)
41 - Create a test suite for regression testing. */
45 This is the third HTML parser written for Wget. The first one was
46 written some time during the Geturl 1.0 beta cycle, and was very
47 inefficient and buggy. It also contained some very complex code to
48 remember a list of parser states, because it was supposed to be
51 The second HTML parser was written for Wget 1.4 (the first version
52 by the name `Wget'), and was a complete rewrite. Although the new
53 parser behaved much better and made no claims of reentrancy, it
54 still shared many of the fundamental flaws of the old version -- it
55 only regarded HTML in terms tag-attribute pairs, where the
56 attribute's value was a URL to be returned. Any other property of
57 HTML, such as <base href=...>, or strange way to specify a URL,
58 such as <meta http-equiv=Refresh content="0; URL=..."> had to be
59 crudely hacked in -- and the caller had to be aware of these hacks.
60 Like its predecessor, this parser did not support HTML comments.
62 After Wget 1.5.1 was released, I set out to write a third HTML
63 parser. The objectives of the new parser were to: (1) provide a
64 clean way to analyze HTML lexically, (2) separate interpretation of
65 the markup from the parsing process, (3) be as correct as possible,
66 e.g. correctly skipping comments and other SGML declarations, (4)
67 understand the most common errors in markup and skip them or be
68 relaxed towrds them, and (5) be reasonably efficient (no regexps,
69 minimum copying and minimum or no heap allocation).
71 I believe this parser meets all of the above goals. It is
72 reasonably well structured, and could be relatively easily
73 separated from Wget and used elsewhere. While some of its
74 intrinsic properties limit its value as a general-purpose HTML
75 parser, I believe that, with minimum modifications, it could serve
78 Due to time and other constraints, this parser was not integrated
79 into Wget until the version 1.7. */
83 The single entry point of this parser is map_html_tags(), which
84 works by calling a function you specify for each tag. The function
85 gets called with the pointer to a structure describing the tag and
88 /* To test as standalone, compile with `-DSTANDALONE -I.'. You'll
89 still need Wget headers to compile. */
94 # define I_REALLY_WANT_CTYPE_MACROS
102 # include <strings.h>
107 #include "html-parse.h"
113 # define xmalloc malloc
114 # define xrealloc realloc
125 # define ISSPACE(x) isspace (x)
126 # define ISDIGIT(x) isdigit (x)
127 # define ISXDIGIT(x) isxdigit (x)
128 # define ISALPHA(x) isalpha (x)
129 # define ISALNUM(x) isalnum (x)
130 # define TOLOWER(x) tolower (x)
131 # define TOUPPER(x) toupper (x)
132 #endif /* STANDALONE */
134 /* Pool support. A pool is a resizable chunk of memory. It is first
135 allocated on the stack, and moved to the heap if it needs to be
136 larger than originally expected. map_html_tags() uses it to store
137 the zero-terminated names and values of tags and attributes.
139 Thus taginfo->name, and attr->name and attr->value for each
140 attribute, do not point into separately allocated areas, but into
141 different parts of the pool, separated only by terminating zeros.
142 This ensures minimum amount of allocation and, for most tags, no
143 allocation because the entire pool is kept on the stack. */
146 char *contents; /* pointer to the contents. */
147 int size; /* size of the pool. */
148 int tail; /* next available position index. */
149 int resized; /* whether the pool has been resized
152 char *orig_contents; /* original pool contents, usually
153 stack-allocated. used by POOL_FREE
154 to restore the pool to the initial
159 /* Initialize the pool to hold INITIAL_SIZE bytes of storage. */
161 #define POOL_INIT(p, initial_storage, initial_size) do { \
162 struct pool *P = (p); \
163 P->contents = (initial_storage); \
164 P->size = (initial_size); \
167 P->orig_contents = P->contents; \
168 P->orig_size = P->size; \
171 /* Grow the pool to accomodate at least SIZE new bytes. If the pool
172 already has room to accomodate SIZE bytes of data, this is a no-op. */
174 #define POOL_GROW(p, increase) \
175 GROW_ARRAY ((p)->contents, (p)->size, (p)->tail + (increase), \
178 /* Append text in the range [beg, end) to POOL. No zero-termination
181 #define POOL_APPEND(p, beg, end) do { \
182 const char *PA_beg = (beg); \
183 int PA_size = (end) - PA_beg; \
184 POOL_GROW (p, PA_size); \
185 memcpy ((p)->contents + (p)->tail, PA_beg, PA_size); \
186 (p)->tail += PA_size; \
189 /* Append one character to the pool. Can be used to zero-terminate
192 #define POOL_APPEND_CHR(p, ch) do { \
193 char PAC_char = (ch); \
195 (p)->contents[(p)->tail++] = PAC_char; \
198 /* Forget old pool contents. The allocated memory is not freed. */
199 #define POOL_REWIND(p) (p)->tail = 0
201 /* Free heap-allocated memory for contents of POOL. This calls
202 xfree() if the memory was allocated through malloc. It also
203 restores `contents' and `size' to their original, pre-malloc
204 values. That way after POOL_FREE, the pool is fully usable, just
205 as if it were freshly initialized with POOL_INIT. */
207 #define POOL_FREE(p) do { \
208 struct pool *P = p; \
210 xfree (P->contents); \
211 P->contents = P->orig_contents; \
212 P->size = P->orig_size; \
217 /* Used for small stack-allocated memory chunks that might grow. Like
218 DO_REALLOC, this macro grows BASEVAR as necessary to take
219 NEEDED_SIZE items of TYPE.
221 The difference is that on the first resize, it will use
222 malloc+memcpy rather than realloc. That way you can stack-allocate
223 the initial chunk, and only resort to heap allocation if you
224 stumble upon large data.
226 After the first resize, subsequent ones are performed with realloc,
227 just like DO_REALLOC. */
229 #define GROW_ARRAY(basevar, sizevar, needed_size, resized, type) do { \
230 long ga_needed_size = (needed_size); \
231 long ga_newsize = (sizevar); \
232 while (ga_newsize < ga_needed_size) \
234 if (ga_newsize != (sizevar)) \
237 basevar = (type *)xrealloc (basevar, ga_newsize * sizeof (type)); \
240 void *ga_new = xmalloc (ga_newsize * sizeof (type)); \
241 memcpy (ga_new, basevar, (sizevar) * sizeof (type)); \
242 (basevar) = ga_new; \
245 (sizevar) = ga_newsize; \
249 #define AP_DOWNCASE 1
250 #define AP_PROCESS_ENTITIES 2
251 #define AP_TRIM_BLANKS 4
253 /* Copy the text in the range [BEG, END) to POOL, optionally
254 performing operations specified by FLAGS. FLAGS may be any
255 combination of AP_DOWNCASE, AP_PROCESS_ENTITIES and AP_TRIM_BLANKS
256 with the following meaning:
258 * AP_DOWNCASE -- downcase all the letters;
260 * AP_PROCESS_ENTITIES -- process the SGML entities and write out
261 the decoded string. Recognized entities are <, >, &, ",
262   and the numerical entities.
264 * AP_TRIM_BLANKS -- ignore blanks at the beginning and at the end
268 convert_and_copy (struct pool *pool, const char *beg, const char *end, int flags)
270 int old_tail = pool->tail;
273 /* First, skip blanks if required. We must do this before entities
274 are processed, so that blanks can still be inserted as, for
275 instance, ` '. */
276 if (flags & AP_TRIM_BLANKS)
278 while (beg < end && ISSPACE (*beg))
280 while (end > beg && ISSPACE (end[-1]))
285 if (flags & AP_PROCESS_ENTITIES)
287 /* Grow the pool, then copy the text to the pool character by
288 character, processing the encountered entities as we go
291 It's safe (and necessary) to grow the pool in advance because
292 processing the entities can only *shorten* the string, it can
293 never lengthen it. */
294 const char *from = beg;
297 POOL_GROW (pool, end - beg);
298 to = pool->contents + pool->tail;
306 const char *save = from;
313 /* Process numeric entities "&#DDD;" and "&#xHH;". */
316 int numeric = 0, digits = 0;
321 for (; from < end && ISXDIGIT (*from); from++, digits++)
322 numeric = (numeric << 4) + XDIGIT_TO_NUM (*from);
326 for (; from < end && ISDIGIT (*from); from++, digits++)
327 numeric = (numeric * 10) + (*from - '0');
334 #define FROB(x) (remain >= (sizeof (x) - 1) \
335 && 0 == memcmp (from, x, sizeof (x) - 1) \
336 && (*(from + sizeof (x) - 1) == ';' \
337 || remain == sizeof (x) - 1 \
338 || !ISALNUM (*(from + sizeof (x) - 1))))
339 else if (FROB ("lt"))
340 *to++ = '<', from += 2;
341 else if (FROB ("gt"))
342 *to++ = '>', from += 2;
343 else if (FROB ("amp"))
344 *to++ = '&', from += 3;
345 else if (FROB ("quot"))
346 *to++ = '\"', from += 4;
347 /* We don't implement the proposed "Added Latin 1"
348 entities (except for nbsp), because it is unnecessary
349 in the context of Wget, and would require hashing to
351 else if (FROB ("nbsp"))
352 *to++ = 160, from += 4;
356 /* If the entity was followed by `;', we step over the
357 `;'. Otherwise, it was followed by either a
358 non-alphanumeric or EOB, in which case we do nothing. */
359 if (from < end && *from == ';')
364 /* This was not an entity after all. Back out. */
369 /* Verify that we haven't exceeded the original size. (It
370 shouldn't happen, hence the assert.) */
371 assert (to - (pool->contents + pool->tail) <= end - beg);
373 /* Make POOL's tail point to the position following the string
375 pool->tail = to - pool->contents;
376 POOL_APPEND_CHR (pool, '\0');
380 /* Just copy the text to the pool. */
381 POOL_APPEND (pool, beg, end);
382 POOL_APPEND_CHR (pool, '\0');
385 if (flags & AP_DOWNCASE)
387 char *p = pool->contents + old_tail;
393 /* Check whether the contents of [POS, POS+LENGTH) match any of the
394 strings in the ARRAY. */
396 array_allowed (const char **array, const char *beg, const char *end)
398 int length = end - beg;
401 for (; *array; array++)
402 if (length >= strlen (*array)
403 && !strncasecmp (*array, beg, length))
411 /* Originally we used to adhere to rfc 1866 here, and allowed only
412 letters, digits, periods, and hyphens as names (of tags or
413 attributes). However, this broke too many pages which used
414 proprietary or strange attributes, e.g. <img src="a.gif"
415 v:shapes="whatever">.
417 So now we allow any character except:
419 * 8-bit and control chars
420 * characters that clearly cannot be part of name:
423 This only affects attribute and tag names; attribute values allow
424 an even greater variety of characters. */
426 #define NAME_CHAR_P(x) ((x) > 32 && (x) < 127 \
427 && (x) != '=' && (x) != '>' && (x) != '/')
430 static int comment_backout_count;
433 /* Advance over an SGML declaration, such as <!DOCTYPE ...>. In
434 strict comments mode, this is used for skipping over comments as
437 To recap: any SGML declaration may have comments associated with
439 <!MY-DECL -- isn't this fun? -- foo bar>
441 An HTML comment is merely an empty declaration (<!>) with a comment
443 <!-- some stuff here -->
445 Several comments may be embedded in one comment declaration:
446 <!-- have -- -- fun -->
448 Whitespace is allowed between and after the comments, but not
449 before the first comment. Additionally, this function attempts to
450 handle double quotes in SGML declarations correctly. */
453 advance_declaration (const char *beg, const char *end)
456 char quote_char = '\0'; /* shut up, gcc! */
479 /* It looked like a good idea to write this as a state machine, but
482 while (state != AC_S_DONE && state != AC_S_BACKOUT)
485 state = AC_S_BACKOUT;
495 state = AC_S_DEFAULT;
498 state = AC_S_BACKOUT;
520 if (NAME_CHAR_P (ch))
521 state = AC_S_DCLNAME;
523 state = AC_S_BACKOUT;
530 else if (NAME_CHAR_P (ch))
533 state = AC_S_DEFAULT;
536 /* We must use 0x22 because broken assert macros choke on
538 assert (ch == '\'' || ch == 0x22);
539 quote_char = ch; /* cheating -- I really don't feel like
540 introducing more different states for
541 different quote characters. */
543 state = AC_S_IN_QUOTE;
546 if (ch == quote_char)
552 assert (ch == quote_char);
554 state = AC_S_DEFAULT;
566 state = AC_S_COMMENT;
569 state = AC_S_BACKOUT;
593 state = AC_S_DEFAULT;
596 state = AC_S_COMMENT;
603 if (state == AC_S_BACKOUT)
606 ++comment_backout_count;
613 /* Find the first occurrence of the substring "-->" in [BEG, END) and
614 return the pointer to the character after the substring. If the
615 substring is not found, return NULL. */
618 find_comment_end (const char *beg, const char *end)
620 /* Open-coded Boyer-Moore search for "-->". Examine the third char;
621 if it's not '>' or '-', advance by three characters. Otherwise,
622 look at the preceding characters and try to find a match. */
624 const char *p = beg - 1;
626 while ((p += 3) < end)
630 if (p[-1] == '-' && p[-2] == '-')
638 if (++p == end) return NULL;
641 case '>': return p + 1;
642 case '-': goto at_dash_dash;
647 if ((p += 2) >= end) return NULL;
662 /* Advance P (a char pointer), with the explicit intent of being able
663 to read the next character. If this is not possible, go to finish. */
665 #define ADVANCE(p) do { \
671 /* Skip whitespace, if any. */
673 #define SKIP_WS(p) do { \
674 while (ISSPACE (*p)) { \
679 /* Skip non-whitespace, if any. */
681 #define SKIP_NON_WS(p) do { \
682 while (!ISSPACE (*p)) { \
688 static int tag_backout_count;
691 /* Map MAPFUN over HTML tags in TEXT, which is SIZE characters long.
692 MAPFUN will be called with two arguments: pointer to an initialized
693 struct taginfo, and MAPARG.
695 ALLOWED_TAG_NAMES should be a NULL-terminated array of tag names to
696 be processed by this function. If it is NULL, all the tags are
697 allowed. The same goes for attributes and ALLOWED_ATTRIBUTE_NAMES.
699 (Obviously, the caller can filter out unwanted tags and attributes
700 just as well, but this is just an optimization designed to avoid
701 unnecessary copying for tags/attributes which the caller doesn't
702 want to know about. These lists are searched linearly; therefore,
703 if you're interested in a large number of tags or attributes, you'd
704 better set these to NULL and filter them out yourself with a
705 hashing process most appropriate for your application.) */
708 map_html_tags (const char *text, int size,
709 void (*mapfun) (struct taginfo *, void *), void *maparg,
711 const char **allowed_tag_names,
712 const char **allowed_attribute_names)
714 /* storage for strings passed to MAPFUN callback; if 256 bytes is
715 too little, POOL_APPEND allocates more with malloc. */
716 char pool_initial_storage[256];
719 const char *p = text;
720 const char *end = text + size;
722 struct attr_pair attr_pair_initial_storage[8];
723 int attr_pair_size = countof (attr_pair_initial_storage);
724 int attr_pair_resized = 0;
725 struct attr_pair *pairs = attr_pair_initial_storage;
730 POOL_INIT (&pool, pool_initial_storage, countof (pool_initial_storage));
734 const char *tag_name_begin, *tag_name_end;
735 const char *tag_start_position;
736 int uninteresting_tag;
744 /* Find beginning of tag. We use memchr() instead of the usual
745 looping with ADVANCE() for speed. */
746 p = memchr (p, '<', end - p);
750 tag_start_position = p;
753 /* Establish the type of the tag (start-tag, end-tag or
757 if (!(flags & MHT_STRICT_COMMENTS)
758 && p < end + 3 && p[1] == '-' && p[2] == '-')
760 /* If strict comments are not enforced and if we know
761 we're looking at a comment, simply look for the
762 terminating "-->". Non-strict is the default because
763 it works in other browsers and most HTML writers can't
764 be bothered with getting the comments right. */
765 const char *comment_end = find_comment_end (p + 3, end);
771 /* Either in strict comment mode or looking at a non-empty
772 declaration. Real declarations are much less likely to
773 be misused the way comments are, so advance over them
774 properly regardless of strictness. */
775 p = advance_declaration (p, end);
787 while (NAME_CHAR_P (*p))
789 if (p == tag_name_begin)
793 if (end_tag && *p != '>')
796 if (!array_allowed (allowed_tag_names, tag_name_begin, tag_name_end))
797 /* We can't just say "goto look_for_tag" here because we need
798 the loop below to properly advance over the tag's attributes. */
799 uninteresting_tag = 1;
802 uninteresting_tag = 0;
803 convert_and_copy (&pool, tag_name_begin, tag_name_end, AP_DOWNCASE);
806 /* Find the attributes. */
809 const char *attr_name_begin, *attr_name_end;
810 const char *attr_value_begin, *attr_value_end;
811 const char *attr_raw_value_begin, *attr_raw_value_end;
812 int operation = AP_DOWNCASE; /* stupid compiler. */
818 /* A slash at this point means the tag is about to be
819 closed. This is legal in XML and has been popularized
820 in HTML via XHTML. */
821 /* <foo a=b c=d /> */
829 /* Check for end of tag definition. */
833 /* Establish bounds of attribute name. */
834 attr_name_begin = p; /* <foo bar ...> */
836 while (NAME_CHAR_P (*p))
838 attr_name_end = p; /* <foo bar ...> */
840 if (attr_name_begin == attr_name_end)
843 /* Establish bounds of attribute value. */
845 if (NAME_CHAR_P (*p) || *p == '/' || *p == '>')
847 /* Minimized attribute syntax allows `=' to be omitted.
848 For example, <UL COMPACT> is a valid shorthand for <UL
849 COMPACT="compact">. Even if such attributes are not
850 useful to Wget, we need to support them, so that the
851 tags containing them can be parsed correctly. */
852 attr_raw_value_begin = attr_value_begin = attr_name_begin;
853 attr_raw_value_end = attr_value_end = attr_name_end;
859 if (*p == '\"' || *p == '\'')
861 int newline_seen = 0;
862 char quote_char = *p;
863 attr_raw_value_begin = p;
865 attr_value_begin = p; /* <foo bar="baz"> */
867 while (*p != quote_char)
869 if (!newline_seen && *p == '\n')
871 /* If a newline is seen within the quotes, it
872 is most likely that someone forgot to close
873 the quote. In that case, we back out to
874 the value beginning, and terminate the tag
875 at either `>' or the delimiter, whichever
876 comes first. Such a tag terminated at `>'
878 p = attr_value_begin;
882 else if (newline_seen && *p == '>')
886 attr_value_end = p; /* <foo bar="baz"> */
888 if (*p == quote_char)
892 attr_raw_value_end = p; /* <foo bar="baz"> */
894 operation = AP_PROCESS_ENTITIES;
895 if (flags & MHT_TRIM_VALUES)
896 operation |= AP_TRIM_BLANKS;
900 attr_value_begin = p; /* <foo bar=baz> */
902 /* According to SGML, a name token should consist only
903 of alphanumerics, . and -. However, this is often
904 violated by, for instance, `%' in `width=75%'.
905 We'll be liberal and allow just about anything as
906 an attribute value. */
907 while (!ISSPACE (*p) && *p != '>')
909 attr_value_end = p; /* <foo bar=baz qux=quix> */
911 if (attr_value_begin == attr_value_end)
915 attr_raw_value_begin = attr_value_begin;
916 attr_raw_value_end = attr_value_end;
917 operation = AP_PROCESS_ENTITIES;
922 /* We skipped the whitespace and found something that is
923 neither `=' nor the beginning of the next attribute's
925 goto backout_tag; /* <foo bar [... */
929 /* If we're not interested in the tag, don't bother with any
930 of the attributes. */
931 if (uninteresting_tag)
934 /* If we aren't interested in the attribute, skip it. We
935 cannot do this test any sooner, because our text pointer
936 needs to correctly advance over the attribute. */
937 if (allowed_attribute_names
938 && !array_allowed (allowed_attribute_names, attr_name_begin,
942 GROW_ARRAY (pairs, attr_pair_size, nattrs + 1, attr_pair_resized,
945 pairs[nattrs].name_pool_index = pool.tail;
946 convert_and_copy (&pool, attr_name_begin, attr_name_end, AP_DOWNCASE);
948 pairs[nattrs].value_pool_index = pool.tail;
949 convert_and_copy (&pool, attr_value_begin, attr_value_end, operation);
950 pairs[nattrs].value_raw_beginning = attr_raw_value_begin;
951 pairs[nattrs].value_raw_size = (attr_raw_value_end
952 - attr_raw_value_begin);
956 if (uninteresting_tag)
962 /* By now, we have a valid tag with a name and zero or more
963 attributes. Fill in the data and call the mapper function. */
966 struct taginfo taginfo;
968 taginfo.name = pool.contents;
969 taginfo.end_tag_p = end_tag;
970 taginfo.nattrs = nattrs;
971 /* We fill in the char pointers only now, when pool can no
972 longer get realloc'ed. If we did that above, we could get
973 hosed by reallocation. Obviously, after this point, the pool
974 may no longer be grown. */
975 for (i = 0; i < nattrs; i++)
977 pairs[i].name = pool.contents + pairs[i].name_pool_index;
978 pairs[i].value = pool.contents + pairs[i].value_pool_index;
980 taginfo.attrs = pairs;
981 taginfo.start_position = tag_start_position;
982 taginfo.end_position = p + 1;
984 (*mapfun) (&taginfo, maparg);
993 /* The tag wasn't really a tag. Treat its contents as ordinary
995 p = tag_start_position + 1;
1001 if (attr_pair_resized)
1011 test_mapper (struct taginfo *taginfo, void *arg)
1015 printf ("%s%s", taginfo->end_tag_p ? "/" : "", taginfo->name);
1016 for (i = 0; i < taginfo->nattrs; i++)
1017 printf (" %s=%s", taginfo->attrs[i].name, taginfo->attrs[i].value);
1025 char *x = (char *)xmalloc (size);
1028 int tag_counter = 0;
1030 while ((read_count = fread (x + length, 1, size - length, stdin)))
1032 length += read_count;
1034 x = (char *)xrealloc (x, size);
1037 map_html_tags (x, length, NULL, NULL, test_mapper, &tag_counter);
1038 printf ("TAGS: %d\n", tag_counter);
1039 printf ("Tag backouts: %d\n", tag_backout_count);
1040 printf ("Comment backouts: %d\n", comment_backout_count);
1043 #endif /* STANDALONE */