1 /* HTML parser for Wget.
2 Copyright (C) 1998, 2000 Free Software Foundation, Inc.
4 This file is part of Wget.
6 This program 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 This program 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 this program; if not, write to the Free Software
18 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
20 /* The only entry point to this module is map_html_tags(), which see. */
24 - Allow hooks for callers to process contents outside tags. This
25 is needed to implement handling <style> and <script>. The
26 taginfo structure already carries the information about where the
27 tags are, but this is not enough, because one would also want to
28 skip the comments. (The funny thing is that for <style> and
29 <script> you *don't* want to skip comments!)
31 - Create a test suite for regression testing. */
35 This is the third HTML parser written for Wget. The first one was
36 written some time during the Geturl 1.0 beta cycle, and was very
37 inefficient and buggy. It also contained some very complex code to
38 remember a list of parser states, because it was supposed to be
39 reentrant. The idea was that several parsers would be running
40 concurrently, and you'd have pass the function a unique ID string
41 (for example, the URL) by which it found the relevant parser state
42 and returned the next URL. Over-engineering at its best.
44 The second HTML parser was written for Wget 1.4 (the first version
45 by the name `Wget'), and was a complete rewrite. Although the new
46 parser behaved much better and made no claims of reentrancy, it
47 still shared many of the fundamental flaws of the old version -- it
48 only regarded HTML in terms tag-attribute pairs, where the
49 attribute's value was a URL to be returned. Any other property of
50 HTML, such as <base href=...>, or strange way to specify a URL,
51 such as <meta http-equiv=Refresh content="0; URL=..."> had to be
52 crudely hacked in -- and the caller had to be aware of these hacks.
53 Like its predecessor, this parser did not support HTML comments.
55 After Wget 1.5.1 was released, I set out to write a third HTML
56 parser. The objectives of the new parser were to: (1) provide a
57 clean way to analyze HTML lexically, (2) separate interpretation of
58 the markup from the parsing process, (3) be as correct as possible,
59 e.g. correctly skipping comments and other SGML declarations, (4)
60 understand the most common errors in markup and skip them or be
61 relaxed towrds them, and (5) be reasonably efficient (no regexps,
62 minimum copying and minimum or no heap allocation).
64 I believe this parser meets all of the above goals. It is
65 reasonably well structured, and could be relatively easily
66 separated from Wget and used elsewhere. While some of its
67 intrinsic properties limit its value as a general-purpose HTML
68 parser, I believe that, with minimum modifications, it could serve
71 Due to time and other constraints, this parser was not integrated
72 into Wget until the version ???. */
76 The single entry point of this parser is map_html_tags(), which
77 works by calling a function you specify for each tag. The function
78 gets called with the pointer to a structure describing the tag and
81 /* To test as standalone, compile with `-DSTANDALONE -I.'. You'll
82 still need Wget headers to compile. */
96 #include "html-parse.h"
99 # define xmalloc malloc
100 # define xrealloc realloc
102 #endif /* STANDALONE */
104 /* Pool support. For efficiency, map_html_tags() stores temporary
105 string data to a single stack-allocated pool. If the pool proves
106 too small, additional memory is allocated/resized with
107 malloc()/realloc(). */
110 char *contents; /* pointer to the contents. */
111 int size; /* size of the pool. */
112 int index; /* next unoccupied position in
115 int alloca_p; /* whether contents was allocated
117 char *orig_contents; /* orig_contents, allocated by
118 alloca(). this is used by
119 POOL_FREE to restore the pool to
120 the "initial" state. */
124 /* Initialize the pool to hold INITIAL_SIZE bytes of storage. */
126 #define POOL_INIT(pool, initial_size) do { \
127 (pool).size = (initial_size); \
128 (pool).contents = ALLOCA_ARRAY (char, (pool).size); \
130 (pool).alloca_p = 1; \
131 (pool).orig_contents = (pool).contents; \
132 (pool).orig_size = (pool).size; \
135 /* Grow the pool to accomodate at least SIZE new bytes. If the pool
136 already has room to accomodate SIZE bytes of data, this is a no-op. */
138 #define POOL_GROW(pool, increase) do { \
139 int PG_newsize = (pool).index + increase; \
140 DO_REALLOC_FROM_ALLOCA ((pool).contents, (pool).size, PG_newsize, \
141 (pool).alloca_p, char); \
144 /* Append text in the range [beg, end) to POOL. No zero-termination
147 #define POOL_APPEND(pool, beg, end) do { \
148 const char *PA_beg = beg; \
149 int PA_size = end - PA_beg; \
150 POOL_GROW (pool, PA_size); \
151 memcpy ((pool).contents + (pool).index, PA_beg, PA_size); \
152 (pool).index += PA_size; \
155 /* The same as the above, but with zero termination. */
157 #define POOL_APPEND_ZT(pool, beg, end) do { \
158 const char *PA_beg = beg; \
159 int PA_size = end - PA_beg; \
160 POOL_GROW (pool, PA_size + 1); \
161 memcpy ((pool).contents + (pool).index, PA_beg, PA_size); \
162 (pool).contents[(pool).index + PA_size] = '\0'; \
163 (pool).index += PA_size + 1; \
166 /* Forget old pool contents. The allocated memory is not freed. */
167 #define POOL_REWIND(pool) pool.index = 0
169 /* Free heap-allocated memory for contents of POOL. This calls
170 xfree() if the memory was allocated through malloc. It also
171 restores `contents' and `size' to their original, pre-malloc
172 values. That way after POOL_FREE, the pool is fully usable, just
173 as if it were freshly initialized with POOL_INIT. */
175 #define POOL_FREE(pool) do { \
176 if (!(pool).alloca_p) \
177 xfree ((pool).contents); \
178 (pool).contents = (pool).orig_contents; \
179 (pool).size = (pool).orig_size; \
181 (pool).alloca_p = 1; \
185 #define AP_DOWNCASE 1
186 #define AP_PROCESS_ENTITIES 2
187 #define AP_SKIP_BLANKS 4
189 /* Copy the text in the range [BEG, END) to POOL, optionally
190 performing operations specified by FLAGS. FLAGS may be any
191 combination of AP_DOWNCASE, AP_PROCESS_ENTITIES and AP_SKIP_BLANKS
192 with the following meaning:
194 * AP_DOWNCASE -- downcase all the letters;
196 * AP_PROCESS_ENTITIES -- process the SGML entities and write out
197 the decoded string. Recognized entities are <, >, &, ",
198   and the numerical entities.
200 * AP_SKIP_BLANKS -- ignore blanks at the beginning and at the end
203 convert_and_copy (struct pool *pool, const char *beg, const char *end, int flags)
205 int old_index = pool->index;
208 /* First, skip blanks if required. We must do this before entities
209 are processed, so that blanks can still be inserted as, for
210 instance, ` '. */
211 if (flags & AP_SKIP_BLANKS)
213 while (beg < end && ISSPACE (*beg))
215 while (end > beg && ISSPACE (end[-1]))
220 if (flags & AP_PROCESS_ENTITIES)
222 /* Stack-allocate a copy of text, process entities and copy it
224 char *local_copy = (char *)alloca (size + 1);
225 const char *from = beg;
226 char *to = local_copy;
234 const char *save = from;
237 if (++from == end) goto lose;
244 if (from == end || !ISDIGIT (*from)) goto lose;
245 for (numeric = 0; from < end && ISDIGIT (*from); from++)
246 numeric = 10 * numeric + (*from) - '0';
247 if (from < end && ISALPHA (*from)) goto lose;
251 #define FROB(x) (remain >= (sizeof (x) - 1) \
252 && !memcmp (from, x, sizeof (x) - 1) \
253 && (*(from + sizeof (x) - 1) == ';' \
254 || remain == sizeof (x) - 1 \
255 || !ISALNUM (*(from + sizeof (x) - 1))))
256 else if (FROB ("lt"))
257 *to++ = '<', from += 2;
258 else if (FROB ("gt"))
259 *to++ = '>', from += 2;
260 else if (FROB ("amp"))
261 *to++ = '&', from += 3;
262 else if (FROB ("quot"))
263 *to++ = '\"', from += 4;
264 /* We don't implement the proposed "Added Latin 1"
265 entities (except for nbsp), because it is unnecessary
266 in the context of Wget, and would require hashing to
268 else if (FROB ("nbsp"))
269 *to++ = 160, from += 4;
273 /* If the entity was followed by `;', we step over the
274 `;'. Otherwise, it was followed by either a
275 non-alphanumeric or EOB, in which case we do nothing. */
276 if (from < end && *from == ';')
281 /* This was not an entity after all. Back out. */
287 POOL_APPEND (*pool, local_copy, to);
291 /* Just copy the text to the pool. */
292 POOL_APPEND_ZT (*pool, beg, end);
295 if (flags & AP_DOWNCASE)
297 char *p = pool->contents + old_index;
303 /* Check whether the contents of [POS, POS+LENGTH) match any of the
304 strings in the ARRAY. */
306 array_allowed (const char **array, const char *beg, const char *end)
308 int length = end - beg;
311 for (; *array; array++)
312 if (length >= strlen (*array)
313 && !strncasecmp (*array, beg, length))
321 /* RFC1866: name [of attribute or tag] consists of letters, digits,
322 periods, or hyphens. We also allow _, for compatibility with
323 brain-damaged generators. */
324 #define NAME_CHAR_P(x) (ISALNUM (x) || (x) == '.' || (x) == '-' || (x) == '_')
326 /* States while advancing through comments. */
328 #define AC_S_BACKOUT 1
330 #define AC_S_DEFAULT 3
331 #define AC_S_DCLNAME 4
334 #define AC_S_COMMENT 7
337 #define AC_S_QUOTE1 10
338 #define AC_S_IN_QUOTE 11
339 #define AC_S_QUOTE2 12
342 static int comment_backout_count;
345 /* Advance over an SGML declaration (the <!...> forms you find in HTML
346 documents). The function returns the location after the
347 declaration. The reason we need this is that HTML comments are
348 expressed as comments in so-called "empty declarations".
350 To recap: any SGML declaration may have comments associated with
352 <!MY-DECL -- isn't this fun? -- foo bar>
354 An HTML comment is merely an empty declaration (<!>) with a comment
356 <!-- some stuff here -->
358 Several comments may be embedded in one comment declaration:
359 <!-- have -- -- fun -->
361 Whitespace is allowed between and after the comments, but not
362 before the first comment.
364 Additionally, this function attempts to handle double quotes in
365 SGML declarations correctly. */
367 advance_declaration (const char *beg, const char *end)
370 char quote_char = '\0'; /* shut up, gcc! */
372 int state = AC_S_BANG;
378 /* It looked like a good idea to write this as a state machine, but
381 while (state != AC_S_DONE && state != AC_S_BACKOUT)
384 state = AC_S_BACKOUT;
394 state = AC_S_DEFAULT;
397 state = AC_S_BACKOUT;
419 if (NAME_CHAR_P (ch))
420 state = AC_S_DCLNAME;
422 state = AC_S_BACKOUT;
427 if (NAME_CHAR_P (ch))
432 state = AC_S_DEFAULT;
435 assert (ch == '\'' || ch == '"');
436 quote_char = ch; /* cheating -- I really don't feel like
437 introducing more different states for
438 different quote characters. */
440 state = AC_S_IN_QUOTE;
443 if (ch == quote_char)
449 assert (ch == quote_char);
451 state = AC_S_DEFAULT;
463 state = AC_S_COMMENT;
466 state = AC_S_BACKOUT;
490 state = AC_S_DEFAULT;
493 state = AC_S_COMMENT;
500 if (state == AC_S_BACKOUT)
503 ++comment_backout_count;
510 /* Advance P (a char pointer), with the explicit intent of being able
511 to read the next character. If this is not possible, go to finish. */
513 #define ADVANCE(p) do { \
519 /* Skip whitespace, if any. */
521 #define SKIP_WS(p) do { \
522 while (ISSPACE (*p)) { \
527 /* Skip non-whitespace, if any. */
529 #define SKIP_NON_WS(p) do { \
530 while (!ISSPACE (*p)) { \
536 static int tag_backout_count;
539 /* Map MAPFUN over HTML tags in TEXT, which is SIZE characters long.
540 MAPFUN will be called with two arguments: pointer to an initialized
541 struct taginfo, and CLOSURE.
543 ALLOWED_TAG_NAMES should be a NULL-terminated array of tag names to
544 be processed by this function. If it is NULL, all the tags are
545 allowed. The same goes for attributes and ALLOWED_ATTRIBUTE_NAMES.
547 (Obviously, the caller can filter out unwanted tags and attributes
548 just as well, but this is just an optimization designed to avoid
549 unnecessary copying for tags/attributes which the caller doesn't
550 want to know about. These lists are searched linearly; therefore,
551 if you're interested in a large number of tags or attributes, you'd
552 better set these to NULL and filter them out yourself with a
553 hashing process most appropriate for your application.) */
556 map_html_tags (const char *text, int size,
557 const char **allowed_tag_names,
558 const char **allowed_attribute_names,
559 void (*mapfun) (struct taginfo *, void *),
562 const char *p = text;
563 const char *end = text + size;
565 int attr_pair_count = 8;
566 int attr_pair_alloca_p = 1;
567 struct attr_pair *pairs = ALLOCA_ARRAY (struct attr_pair, attr_pair_count);
573 POOL_INIT (pool, 256);
577 const char *tag_name_begin, *tag_name_end;
578 const char *tag_start_position;
579 int uninteresting_tag;
587 /* Find beginning of tag. We use memchr() instead of the usual
588 looping with ADVANCE() for speed. */
589 p = memchr (p, '<', end - p);
593 tag_start_position = p;
596 /* Establish the type of the tag (start-tag, end-tag or
600 /* This is an SGML declaration -- just skip it. */
601 p = advance_declaration (p, end);
612 while (NAME_CHAR_P (*p))
614 if (p == tag_name_begin)
618 if (end_tag && *p != '>')
621 if (!array_allowed (allowed_tag_names, tag_name_begin, tag_name_end))
622 /* We can't just say "goto look_for_tag" here because we need
623 the loop below to properly advance over the tag's attributes. */
624 uninteresting_tag = 1;
627 uninteresting_tag = 0;
628 convert_and_copy (&pool, tag_name_begin, tag_name_end, AP_DOWNCASE);
631 /* Find the attributes. */
634 const char *attr_name_begin, *attr_name_end;
635 const char *attr_value_begin, *attr_value_end;
636 const char *attr_raw_value_begin, *attr_raw_value_end;
637 int operation = AP_DOWNCASE; /* stupid compiler. */
641 /* Check for end of tag definition. */
645 /* Establish bounds of attribute name. */
646 attr_name_begin = p; /* <foo bar ...> */
648 while (NAME_CHAR_P (*p))
650 attr_name_end = p; /* <foo bar ...> */
652 if (attr_name_begin == attr_name_end)
655 /* Establish bounds of attribute value. */
657 if (NAME_CHAR_P (*p) || *p == '>')
659 /* Minimized attribute syntax allows `=' to be omitted.
660 For example, <UL COMPACT> is a valid shorthand for <UL
661 COMPACT="compact">. Even if such attributes are not
662 useful to Wget, we need to support them, so that the
663 tags containing them can be parsed correctly. */
664 attr_raw_value_begin = attr_value_begin = attr_name_begin;
665 attr_raw_value_end = attr_value_end = attr_name_end;
671 if (*p == '\"' || *p == '\'')
673 int newline_seen = 0;
674 char quote_char = *p;
675 attr_raw_value_begin = p;
677 attr_value_begin = p; /* <foo bar="baz"> */
679 while (*p != quote_char)
681 if (!newline_seen && *p == '\n')
683 /* If a newline is seen within the quotes, it
684 is most likely that someone forgot to close
685 the quote. In that case, we back out to
686 the value beginning, and terminate the tag
687 at either `>' or the delimiter, whichever
688 comes first. Such a tag terminated at `>'
690 p = attr_value_begin;
694 else if (newline_seen && *p == '>')
698 attr_value_end = p; /* <foo bar="baz"> */
700 if (*p == quote_char)
704 attr_raw_value_end = p; /* <foo bar="baz"> */
706 /* The AP_SKIP_BLANKS part is not entirely correct,
707 because we don't want to skip blanks for all the
709 operation = AP_PROCESS_ENTITIES | AP_SKIP_BLANKS;
713 attr_value_begin = p; /* <foo bar=baz> */
715 /* According to SGML, a name token should consist only
716 of alphanumerics, . and -. However, this is often
717 violated by, for instance, `%' in `width=75%'.
718 We'll be liberal and allow just about anything as
719 an attribute value. */
720 while (!ISSPACE (*p) && *p != '>')
722 attr_value_end = p; /* <foo bar=baz qux=quix> */
724 if (attr_value_begin == attr_value_end)
728 attr_raw_value_begin = attr_value_begin;
729 attr_raw_value_end = attr_value_end;
730 operation = AP_PROCESS_ENTITIES;
735 /* We skipped the whitespace and found something that is
736 neither `=' nor the beginning of the next attribute's
738 goto backout_tag; /* <foo bar /... */
742 /* If we're not interested in the tag, don't bother with any
743 of the attributes. */
744 if (uninteresting_tag)
747 /* If we aren't interested in the attribute, skip it. We
748 cannot do this test any sooner, because our text pointer
749 needs to correctly advance over the attribute. */
750 if (allowed_attribute_names
751 && !array_allowed (allowed_attribute_names, attr_name_begin,
755 DO_REALLOC_FROM_ALLOCA (pairs, attr_pair_count, nattrs + 1,
756 attr_pair_alloca_p, struct attr_pair);
758 pairs[nattrs].name_pool_index = pool.index;
759 convert_and_copy (&pool, attr_name_begin, attr_name_end, AP_DOWNCASE);
761 pairs[nattrs].value_pool_index = pool.index;
762 convert_and_copy (&pool, attr_value_begin, attr_value_end, operation);
763 pairs[nattrs].value_raw_beginning = attr_raw_value_begin;
764 pairs[nattrs].value_raw_size = (attr_raw_value_end
765 - attr_raw_value_begin);
769 if (uninteresting_tag)
775 /* By now, we have a valid tag with a name and zero or more
776 attributes. Fill in the data and call the mapper function. */
779 struct taginfo taginfo;
781 taginfo.name = pool.contents;
782 taginfo.end_tag_p = end_tag;
783 taginfo.nattrs = nattrs;
784 /* We fill in the char pointers only now, when pool can no
785 longer get realloc'ed. If we did that above, we could get
786 hosed by reallocation. Obviously, after this point, the pool
787 may no longer be grown. */
788 for (i = 0; i < nattrs; i++)
790 pairs[i].name = pool.contents + pairs[i].name_pool_index;
791 pairs[i].value = pool.contents + pairs[i].value_pool_index;
793 taginfo.attrs = pairs;
794 taginfo.start_position = tag_start_position;
795 taginfo.end_position = p + 1;
797 (*mapfun) (&taginfo, closure);
806 /* The tag wasn't really a tag. Treat its contents as ordinary
808 p = tag_start_position + 1;
814 if (!attr_pair_alloca_p)
824 test_mapper (struct taginfo *taginfo, void *arg)
828 printf ("%s%s", taginfo->end_tag_p ? "/" : "", taginfo->name);
829 for (i = 0; i < taginfo->nattrs; i++)
830 printf (" %s=%s", taginfo->attrs[i].name, taginfo->attrs[i].value);
838 char *x = (char *)xmalloc (size);
843 while ((read_count = fread (x + length, 1, size - length, stdin)))
845 length += read_count;
847 x = (char *)xrealloc (x, size);
850 map_html_tags (x, length, NULL, NULL, test_mapper, &tag_counter);
851 printf ("TAGS: %d\n", tag_counter);
852 printf ("Tag backouts: %d\n", tag_backout_count);
853 printf ("Comment backouts: %d\n", comment_backout_count);
856 #endif /* STANDALONE */