X-Git-Url: http://sjero.net/git/?p=wget;a=blobdiff_plain;f=src%2Fhtml-parse.c;h=20791cd83450272210c17a129ecd6904aec86231;hp=e10c4855466de3fef61c6fce2d6763bf937f03c9;hb=HEAD;hpb=90cdb82942f5c904a933e6f9b05e6f046df0dd4c diff --git a/src/html-parse.c b/src/html-parse.c index e10c4855..20791cd8 100644 --- a/src/html-parse.c +++ b/src/html-parse.c @@ -1,11 +1,12 @@ /* HTML parser for Wget. - Copyright (C) 1998, 2000 Free Software Foundation, Inc. + Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, + 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. This file is part of GNU Wget. GNU Wget is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2 of the License, or (at +the Free Software Foundation; either version 3 of the License, or (at your option) any later version. GNU Wget is distributed in the hope that it will be useful, @@ -14,8 +15,18 @@ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with Wget; if not, write to the Free Software -Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ +along with Wget. If not, see . + +Additional permission under GNU GPL version 3 section 7 + +If you modify this program, or any covered work, by linking or +combining it with the OpenSSL project's OpenSSL library (or a +modified version of that library), containing parts covered by the +terms of the OpenSSL or SSLeay licenses, the Free Software Foundation +grants you additional permission to convey the resulting work. +Corresponding Source for a non-source form of such a combination +shall include the source code for the parts of OpenSSL used as well +as that of the covered work. */ /* The only entry point to this module is map_html_tags(), which see. */ @@ -36,10 +47,7 @@ Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ written some time during the Geturl 1.0 beta cycle, and was very inefficient and buggy. It also contained some very complex code to remember a list of parser states, because it was supposed to be - reentrant. The idea was that several parsers would be running - concurrently, and you'd have pass the function a unique ID string - (for example, the URL) by which it found the relevant parser state - and returned the next URL. Over-engineering at its best. + reentrant. The second HTML parser was written for Wget 1.4 (the first version by the name `Wget'), and was a complete rewrite. Although the new @@ -81,90 +89,122 @@ Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ /* To test as standalone, compile with `-DSTANDALONE -I.'. You'll still need Wget headers to compile. */ -#include +#include "wget.h" + +#ifdef STANDALONE +# define I_REALLY_WANT_CTYPE_MACROS +#endif #include #include -#ifdef HAVE_STRING_H -# include -#else -# include -#endif +#include #include -#include "wget.h" +#include "utils.h" #include "html-parse.h" #ifdef STANDALONE +# undef xmalloc +# undef xrealloc +# undef xfree # define xmalloc malloc # define xrealloc realloc # define xfree free -#endif /* STANDALONE */ -/* Pool support. For efficiency, map_html_tags() stores temporary - string data to a single stack-allocated pool. If the pool proves - too small, additional memory is allocated/resized with - malloc()/realloc(). */ +# undef c_isspace +# undef c_isdigit +# undef c_isxdigit +# undef c_isalpha +# undef c_isalnum +# undef c_tolower +# undef c_toupper + +# define c_isspace(x) isspace (x) +# define c_isdigit(x) isdigit (x) +# define c_isxdigit(x) isxdigit (x) +# define c_isalpha(x) isalpha (x) +# define c_isalnum(x) isalnum (x) +# define c_tolower(x) tolower (x) +# define c_toupper(x) toupper (x) + +struct hash_table { + int dummy; +}; +static void * +hash_table_get (const struct hash_table *ht, void *ptr) +{ + return ptr; +} +#else /* not STANDALONE */ +# include "hash.h" +#endif + +/* Pool support. A pool is a resizable chunk of memory. It is first + allocated on the stack, and moved to the heap if it needs to be + larger than originally expected. map_html_tags() uses it to store + the zero-terminated names and values of tags and attributes. + + Thus taginfo->name, and attr->name and attr->value for each + attribute, do not point into separately allocated areas, but into + different parts of the pool, separated only by terminating zeros. + This ensures minimum amount of allocation and, for most tags, no + allocation because the entire pool is kept on the stack. */ struct pool { - char *contents; /* pointer to the contents. */ - int size; /* size of the pool. */ - int index; /* next unoccupied position in - contents. */ - - int alloca_p; /* whether contents was allocated - using alloca(). */ - char *orig_contents; /* orig_contents, allocated by - alloca(). this is used by - POOL_FREE to restore the pool to - the "initial" state. */ + char *contents; /* pointer to the contents. */ + int size; /* size of the pool. */ + int tail; /* next available position index. */ + bool resized; /* whether the pool has been resized + using malloc. */ + + char *orig_contents; /* original pool contents, usually + stack-allocated. used by POOL_FREE + to restore the pool to the initial + state. */ int orig_size; }; /* Initialize the pool to hold INITIAL_SIZE bytes of storage. */ -#define POOL_INIT(pool, initial_size) do { \ - (pool).size = (initial_size); \ - (pool).contents = ALLOCA_ARRAY (char, (pool).size); \ - (pool).index = 0; \ - (pool).alloca_p = 1; \ - (pool).orig_contents = (pool).contents; \ - (pool).orig_size = (pool).size; \ +#define POOL_INIT(p, initial_storage, initial_size) do { \ + struct pool *P = (p); \ + P->contents = (initial_storage); \ + P->size = (initial_size); \ + P->tail = 0; \ + P->resized = false; \ + P->orig_contents = P->contents; \ + P->orig_size = P->size; \ } while (0) /* Grow the pool to accomodate at least SIZE new bytes. If the pool already has room to accomodate SIZE bytes of data, this is a no-op. */ -#define POOL_GROW(pool, increase) do { \ - int PG_newsize = (pool).index + increase; \ - DO_REALLOC_FROM_ALLOCA ((pool).contents, (pool).size, PG_newsize, \ - (pool).alloca_p, char); \ -} while (0) +#define POOL_GROW(p, increase) \ + GROW_ARRAY ((p)->contents, (p)->size, (p)->tail + (increase), \ + (p)->resized, char) /* Append text in the range [beg, end) to POOL. No zero-termination is done. */ -#define POOL_APPEND(pool, beg, end) do { \ - const char *PA_beg = beg; \ - int PA_size = end - PA_beg; \ - POOL_GROW (pool, PA_size); \ - memcpy ((pool).contents + (pool).index, PA_beg, PA_size); \ - (pool).index += PA_size; \ +#define POOL_APPEND(p, beg, end) do { \ + const char *PA_beg = (beg); \ + int PA_size = (end) - PA_beg; \ + POOL_GROW (p, PA_size); \ + memcpy ((p)->contents + (p)->tail, PA_beg, PA_size); \ + (p)->tail += PA_size; \ } while (0) -/* The same as the above, but with zero termination. */ +/* Append one character to the pool. Can be used to zero-terminate + pool strings. */ -#define POOL_APPEND_ZT(pool, beg, end) do { \ - const char *PA_beg = beg; \ - int PA_size = end - PA_beg; \ - POOL_GROW (pool, PA_size + 1); \ - memcpy ((pool).contents + (pool).index, PA_beg, PA_size); \ - (pool).contents[(pool).index + PA_size] = '\0'; \ - (pool).index += PA_size + 1; \ +#define POOL_APPEND_CHR(p, ch) do { \ + char PAC_char = (ch); \ + POOL_GROW (p, 1); \ + (p)->contents[(p)->tail++] = PAC_char; \ } while (0) /* Forget old pool contents. The allocated memory is not freed. */ -#define POOL_REWIND(pool) pool.index = 0 +#define POOL_REWIND(p) (p)->tail = 0 /* Free heap-allocated memory for contents of POOL. This calls xfree() if the memory was allocated through malloc. It also @@ -172,180 +212,338 @@ struct pool { values. That way after POOL_FREE, the pool is fully usable, just as if it were freshly initialized with POOL_INIT. */ -#define POOL_FREE(pool) do { \ - if (!(pool).alloca_p) \ - xfree ((pool).contents); \ - (pool).contents = (pool).orig_contents; \ - (pool).size = (pool).orig_size; \ - (pool).index = 0; \ - (pool).alloca_p = 1; \ +#define POOL_FREE(p) do { \ + struct pool *P = p; \ + if (P->resized) \ + xfree (P->contents); \ + P->contents = P->orig_contents; \ + P->size = P->orig_size; \ + P->tail = 0; \ + P->resized = false; \ } while (0) +/* Used for small stack-allocated memory chunks that might grow. Like + DO_REALLOC, this macro grows BASEVAR as necessary to take + NEEDED_SIZE items of TYPE. + + The difference is that on the first resize, it will use + malloc+memcpy rather than realloc. That way you can stack-allocate + the initial chunk, and only resort to heap allocation if you + stumble upon large data. + + After the first resize, subsequent ones are performed with realloc, + just like DO_REALLOC. */ + +#define GROW_ARRAY(basevar, sizevar, needed_size, resized, type) do { \ + long ga_needed_size = (needed_size); \ + long ga_newsize = (sizevar); \ + while (ga_newsize < ga_needed_size) \ + ga_newsize <<= 1; \ + if (ga_newsize != (sizevar)) \ + { \ + if (resized) \ + basevar = xrealloc (basevar, ga_newsize * sizeof (type)); \ + else \ + { \ + void *ga_new = xmalloc (ga_newsize * sizeof (type)); \ + memcpy (ga_new, basevar, (sizevar) * sizeof (type)); \ + (basevar) = ga_new; \ + resized = true; \ + } \ + (sizevar) = ga_newsize; \ + } \ +} while (0) -#define AP_DOWNCASE 1 -#define AP_PROCESS_ENTITIES 2 -#define AP_SKIP_BLANKS 4 +/* Test whether n+1-sized entity name fits in P. We don't support + IE-style non-terminated entities, e.g. "<foo" -> "prev = ts->next = NULL; + } + else + { + (*tail)->next = ts; + ts->prev = *tail; + *tail = ts; + ts->next = NULL; + } + + return ts; +} + +/* remove ts and everything after it from the stack */ +static void +tagstack_pop (struct tagstack_item **head, struct tagstack_item **tail, + struct tagstack_item *ts) +{ + if (*head == NULL) + return; + + if (ts == *tail) + { + if (ts == *head) + { + xfree (ts); + *head = *tail = NULL; + } + else + { + ts->prev->next = NULL; + *tail = ts->prev; + xfree (ts); + } + } + else + { + if (ts == *head) + { + *head = NULL; + } + *tail = ts->prev; + + if (ts->prev) + { + ts->prev->next = NULL; + } + while (ts) + { + struct tagstack_item *p = ts->next; + xfree (ts); + ts = p; + } + } +} + +static struct tagstack_item * +tagstack_find (struct tagstack_item *tail, const char *tagname_begin, + const char *tagname_end) +{ + int len = tagname_end - tagname_begin; + while (tail) + { + if (len == (tail->tagname_end - tail->tagname_begin)) + { + if (0 == strncasecmp (tail->tagname_begin, tagname_begin, len)) + return tail; + } + tail = tail->prev; + } + return NULL; +} + +/* Decode the HTML character entity at *PTR, considering END to be end + of buffer. It is assumed that the "&" character that marks the + beginning of the entity has been seen at *PTR-1. If a recognized + ASCII entity is seen, it is returned, and *PTR is moved to the end + of the entity. Otherwise, -1 is returned and *PTR left unmodified. + + The recognized entities are: <, >, &, &apos, and ". */ + +static int +decode_entity (const char **ptr, const char *end) +{ + const char *p = *ptr; + int value = -1; + + if (++p == end) + return -1; + + switch (*p++) + { + case '#': + /* Process numeric entities "&#DDD;" and "&#xHH;". */ + { + int digits = 0; + value = 0; + if (*p == 'x') + for (++p; value < 256 && p < end && c_isxdigit (*p); p++, digits++) + value = (value << 4) + XDIGIT_TO_NUM (*p); + else + for (; value < 256 && p < end && c_isdigit (*p); p++, digits++) + value = (value * 10) + (*p - '0'); + if (!digits) + return -1; + /* Don't interpret 128+ codes and NUL because we cannot + portably reinserted them into HTML. */ + if (!value || (value & ~0x7f)) + return -1; + *ptr = SKIP_SEMI (p, 0); + return value; + } + /* Process named ASCII entities. */ + case 'g': + if (ENT1 (p, 't')) + value = '>', *ptr = SKIP_SEMI (p, 1); + break; + case 'l': + if (ENT1 (p, 't')) + value = '<', *ptr = SKIP_SEMI (p, 1); + break; + case 'a': + if (ENT2 (p, 'm', 'p')) + value = '&', *ptr = SKIP_SEMI (p, 2); + else if (ENT3 (p, 'p', 'o', 's')) + /* handle &apos for the sake of the XML/XHTML crowd. */ + value = '\'', *ptr = SKIP_SEMI (p, 3); + break; + case 'q': + if (ENT3 (p, 'u', 'o', 't')) + value = '\"', *ptr = SKIP_SEMI (p, 3); + break; + } + return value; +} +#undef ENT1 +#undef ENT2 +#undef ENT3 +#undef FITS +#undef SKIP_SEMI + +enum { + AP_DOWNCASE = 1, + AP_DECODE_ENTITIES = 2, + AP_TRIM_BLANKS = 4 +}; /* Copy the text in the range [BEG, END) to POOL, optionally performing operations specified by FLAGS. FLAGS may be any - combination of AP_DOWNCASE, AP_PROCESS_ENTITIES and AP_SKIP_BLANKS + combination of AP_DOWNCASE, AP_DECODE_ENTITIES and AP_TRIM_BLANKS with the following meaning: * AP_DOWNCASE -- downcase all the letters; - * AP_PROCESS_ENTITIES -- process the SGML entities and write out - the decoded string. Recognized entities are <, >, &, ", -   and the numerical entities. + * AP_DECODE_ENTITIES -- decode the named and numeric entities in + the ASCII range when copying the string. + + * AP_TRIM_BLANKS -- ignore blanks at the beginning and at the end + of text, as well as embedded newlines. */ - * AP_SKIP_BLANKS -- ignore blanks at the beginning and at the end - of text. */ static void convert_and_copy (struct pool *pool, const char *beg, const char *end, int flags) { - int old_index = pool->index; - int size; + int old_tail = pool->tail; - /* First, skip blanks if required. We must do this before entities - are processed, so that blanks can still be inserted as, for - instance, ` '. */ - if (flags & AP_SKIP_BLANKS) + /* Skip blanks if required. We must do this before entities are + processed, so that blanks can still be inserted as, for instance, + ` '. */ + if (flags & AP_TRIM_BLANKS) { - while (beg < end && ISSPACE (*beg)) - ++beg; - while (end > beg && ISSPACE (end[-1])) - --end; + while (beg < end && c_isspace (*beg)) + ++beg; + while (end > beg && c_isspace (end[-1])) + --end; } - size = end - beg; - if (flags & AP_PROCESS_ENTITIES) + if (flags & AP_DECODE_ENTITIES) { - /* Stack-allocate a copy of text, process entities and copy it - to the pool. */ - char *local_copy = (char *)alloca (size + 1); + /* Grow the pool, then copy the text to the pool character by + character, processing the encountered entities as we go + along. + + It's safe (and necessary) to grow the pool in advance because + processing the entities can only *shorten* the string, it can + never lengthen it. */ const char *from = beg; - char *to = local_copy; + char *to; + bool squash_newlines = !!(flags & AP_TRIM_BLANKS); + + POOL_GROW (pool, end - beg); + to = pool->contents + pool->tail; while (from < end) - { - if (*from != '&') - *to++ = *from++; - else - { - const char *save = from; - int remain; - - if (++from == end) goto lose; - remain = end - from; - - if (*from == '#') - { - int numeric; - ++from; - if (from == end || !ISDIGIT (*from)) goto lose; - for (numeric = 0; from < end && ISDIGIT (*from); from++) - numeric = 10 * numeric + (*from) - '0'; - if (from < end && ISALPHA (*from)) goto lose; - numeric &= 0xff; - *to++ = numeric; - } -#define FROB(x) (remain >= (sizeof (x) - 1) \ - && !memcmp (from, x, sizeof (x) - 1) \ - && (*(from + sizeof (x) - 1) == ';' \ - || remain == sizeof (x) - 1 \ - || !ISALNUM (*(from + sizeof (x) - 1)))) - else if (FROB ("lt")) - *to++ = '<', from += 2; - else if (FROB ("gt")) - *to++ = '>', from += 2; - else if (FROB ("amp")) - *to++ = '&', from += 3; - else if (FROB ("quot")) - *to++ = '\"', from += 4; - /* We don't implement the proposed "Added Latin 1" - entities (except for nbsp), because it is unnecessary - in the context of Wget, and would require hashing to - work efficiently. */ - else if (FROB ("nbsp")) - *to++ = 160, from += 4; - else - goto lose; -#undef FROB - /* If the entity was followed by `;', we step over the - `;'. Otherwise, it was followed by either a - non-alphanumeric or EOB, in which case we do nothing. */ - if (from < end && *from == ';') - ++from; - continue; - - lose: - /* This was not an entity after all. Back out. */ - from = save; - *to++ = *from++; - } - } - *to++ = '\0'; - POOL_APPEND (*pool, local_copy, to); + { + if (*from == '&') + { + int entity = decode_entity (&from, end); + if (entity != -1) + *to++ = entity; + else + *to++ = *from++; + } + else if ((*from == '\n' || *from == '\r') && squash_newlines) + ++from; + else + *to++ = *from++; + } + /* Verify that we haven't exceeded the original size. (It + shouldn't happen, hence the assert.) */ + assert (to - (pool->contents + pool->tail) <= end - beg); + + /* Make POOL's tail point to the position following the string + we've written. */ + pool->tail = to - pool->contents; + POOL_APPEND_CHR (pool, '\0'); } else { /* Just copy the text to the pool. */ - POOL_APPEND_ZT (*pool, beg, end); + POOL_APPEND (pool, beg, end); + POOL_APPEND_CHR (pool, '\0'); } if (flags & AP_DOWNCASE) { - char *p = pool->contents + old_index; + char *p = pool->contents + old_tail; for (; *p; p++) - *p = TOLOWER (*p); - } -} - -/* Check whether the contents of [POS, POS+LENGTH) match any of the - strings in the ARRAY. */ -static int -array_allowed (const char **array, const char *beg, const char *end) -{ - int length = end - beg; - if (array) - { - for (; *array; array++) - if (length >= strlen (*array) - && !strncasecmp (*array, beg, length)) - break; - if (!*array) - return 0; + *p = c_tolower (*p); } - return 1; } -/* RFC1866: name [of attribute or tag] consists of letters, digits, - periods, or hyphens. We also allow _, for compatibility with - brain-damaged generators. */ -#define NAME_CHAR_P(x) (ISALNUM (x) || (x) == '.' || (x) == '-' || (x) == '_') - -/* States while advancing through comments. */ -#define AC_S_DONE 0 -#define AC_S_BACKOUT 1 -#define AC_S_BANG 2 -#define AC_S_DEFAULT 3 -#define AC_S_DCLNAME 4 -#define AC_S_DASH1 5 -#define AC_S_DASH2 6 -#define AC_S_COMMENT 7 -#define AC_S_DASH3 8 -#define AC_S_DASH4 9 -#define AC_S_QUOTE1 10 -#define AC_S_IN_QUOTE 11 -#define AC_S_QUOTE2 12 +/* Originally we used to adhere to rfc 1866 here, and allowed only + letters, digits, periods, and hyphens as names (of tags or + attributes). However, this broke too many pages which used + proprietary or strange attributes, e.g. . + + So now we allow any character except: + * whitespace + * 8-bit and control chars + * characters that clearly cannot be part of name: + '=', '<', '>', '/'. + + This only affects attribute and tag names; attribute values allow + an even greater variety of characters. */ + +#define NAME_CHAR_P(x) ((x) > 32 && (x) < 127 \ + && (x) != '=' && (x) != '<' && (x) != '>' \ + && (x) != '/') #ifdef STANDALONE static int comment_backout_count; #endif -/* Advance over an SGML declaration (the forms you find in HTML - documents). The function returns the location after the - declaration. The reason we need this is that HTML comments are - expressed as comments in so-called "empty declarations". +/* Advance over an SGML declaration, such as . In + strict comments mode, this is used for skipping over comments as + well. To recap: any SGML declaration may have comments associated with it, e.g. @@ -359,17 +557,31 @@ static int comment_backout_count; Whitespace is allowed between and after the comments, but not - before the first comment. + before the first comment. Additionally, this function attempts to + handle double quotes in SGML declarations correctly. */ - Additionally, this function attempts to handle double quotes in - SGML declarations correctly. */ static const char * advance_declaration (const char *beg, const char *end) { const char *p = beg; - char quote_char = '\0'; /* shut up, gcc! */ + char quote_char = '\0'; /* shut up, gcc! */ char ch; - int state = AC_S_BANG; + + enum { + AC_S_DONE, + AC_S_BACKOUT, + AC_S_BANG, + AC_S_DEFAULT, + AC_S_DCLNAME, + AC_S_DASH1, + AC_S_DASH2, + AC_S_COMMENT, + AC_S_DASH3, + AC_S_DASH4, + AC_S_QUOTE1, + AC_S_IN_QUOTE, + AC_S_QUOTE2 + } state = AC_S_BANG; if (beg == end) return beg; @@ -381,122 +593,123 @@ advance_declaration (const char *beg, const char *end) while (state != AC_S_DONE && state != AC_S_BACKOUT) { if (p == end) - state = AC_S_BACKOUT; + state = AC_S_BACKOUT; switch (state) - { - case AC_S_DONE: - case AC_S_BACKOUT: - break; - case AC_S_BANG: - if (ch == '!') - { - ch = *p++; - state = AC_S_DEFAULT; - } - else - state = AC_S_BACKOUT; - break; - case AC_S_DEFAULT: - switch (ch) - { - case '-': - state = AC_S_DASH1; - break; - case ' ': - case '\t': - case '\r': - case '\n': - ch = *p++; - break; - case '>': - state = AC_S_DONE; - break; - case '\'': - case '\"': - state = AC_S_QUOTE1; - break; - default: - if (NAME_CHAR_P (ch)) - state = AC_S_DCLNAME; - else - state = AC_S_BACKOUT; - break; - } - break; - case AC_S_DCLNAME: - if (NAME_CHAR_P (ch)) - ch = *p++; - else if (ch == '-') - state = AC_S_DASH1; - else - state = AC_S_DEFAULT; - break; - case AC_S_QUOTE1: - /* We must use 0x22 because broken assert macros choke on - '"' and '\"'. */ - assert (ch == '\'' || ch == 0x22); - quote_char = ch; /* cheating -- I really don't feel like - introducing more different states for - different quote characters. */ - ch = *p++; - state = AC_S_IN_QUOTE; - break; - case AC_S_IN_QUOTE: - if (ch == quote_char) - state = AC_S_QUOTE2; - else - ch = *p++; - break; - case AC_S_QUOTE2: - assert (ch == quote_char); - ch = *p++; - state = AC_S_DEFAULT; - break; - case AC_S_DASH1: - assert (ch == '-'); - ch = *p++; - state = AC_S_DASH2; - break; - case AC_S_DASH2: - switch (ch) - { - case '-': - ch = *p++; - state = AC_S_COMMENT; - break; - default: - state = AC_S_BACKOUT; - } - break; - case AC_S_COMMENT: - switch (ch) - { - case '-': - state = AC_S_DASH3; - break; - default: - ch = *p++; - break; - } - break; - case AC_S_DASH3: - assert (ch == '-'); - ch = *p++; - state = AC_S_DASH4; - break; - case AC_S_DASH4: - switch (ch) - { - case '-': - ch = *p++; - state = AC_S_DEFAULT; - break; - default: - state = AC_S_COMMENT; - break; - } - break; - } + { + case AC_S_DONE: + case AC_S_BACKOUT: + break; + case AC_S_BANG: + if (ch == '!') + { + ch = *p++; + state = AC_S_DEFAULT; + } + else + state = AC_S_BACKOUT; + break; + case AC_S_DEFAULT: + switch (ch) + { + case '-': + state = AC_S_DASH1; + break; + case ' ': + case '\t': + case '\r': + case '\n': + ch = *p++; + break; + case '<': + case '>': + state = AC_S_DONE; + break; + case '\'': + case '\"': + state = AC_S_QUOTE1; + break; + default: + if (NAME_CHAR_P (ch)) + state = AC_S_DCLNAME; + else + state = AC_S_BACKOUT; + break; + } + break; + case AC_S_DCLNAME: + if (ch == '-') + state = AC_S_DASH1; + else if (NAME_CHAR_P (ch)) + ch = *p++; + else + state = AC_S_DEFAULT; + break; + case AC_S_QUOTE1: + /* We must use 0x22 because broken assert macros choke on + '"' and '\"'. */ + assert (ch == '\'' || ch == 0x22); + quote_char = ch; /* cheating -- I really don't feel like + introducing more different states for + different quote characters. */ + ch = *p++; + state = AC_S_IN_QUOTE; + break; + case AC_S_IN_QUOTE: + if (ch == quote_char) + state = AC_S_QUOTE2; + else + ch = *p++; + break; + case AC_S_QUOTE2: + assert (ch == quote_char); + ch = *p++; + state = AC_S_DEFAULT; + break; + case AC_S_DASH1: + assert (ch == '-'); + ch = *p++; + state = AC_S_DASH2; + break; + case AC_S_DASH2: + switch (ch) + { + case '-': + ch = *p++; + state = AC_S_COMMENT; + break; + default: + state = AC_S_BACKOUT; + } + break; + case AC_S_COMMENT: + switch (ch) + { + case '-': + state = AC_S_DASH3; + break; + default: + ch = *p++; + break; + } + break; + case AC_S_DASH3: + assert (ch == '-'); + ch = *p++; + state = AC_S_DASH4; + break; + case AC_S_DASH4: + switch (ch) + { + case '-': + ch = *p++; + state = AC_S_DEFAULT; + break; + default: + state = AC_S_COMMENT; + break; + } + break; + } } if (state == AC_S_BACKOUT) @@ -508,30 +721,92 @@ advance_declaration (const char *beg, const char *end) } return p; } + +/* Find the first occurrence of the substring "-->" in [BEG, END) and + return the pointer to the character after the substring. If the + substring is not found, return NULL. */ + +static const char * +find_comment_end (const char *beg, const char *end) +{ + /* Open-coded Boyer-Moore search for "-->". Examine the third char; + if it's not '>' or '-', advance by three characters. Otherwise, + look at the preceding characters and try to find a match. */ + + const char *p = beg - 1; + + while ((p += 3) < end) + switch (p[0]) + { + case '>': + if (p[-1] == '-' && p[-2] == '-') + return p + 1; + break; + case '-': + at_dash: + if (p[-1] == '-') + { + at_dash_dash: + if (++p == end) return NULL; + switch (p[0]) + { + case '>': return p + 1; + case '-': goto at_dash_dash; + } + } + else + { + if ((p += 2) >= end) return NULL; + switch (p[0]) + { + case '>': + if (p[-1] == '-') + return p + 1; + break; + case '-': + goto at_dash; + } + } + } + return NULL; +} +/* Return true if the string containing of characters inside [b, e) is + present in hash table HT. */ + +static bool +name_allowed (const struct hash_table *ht, const char *b, const char *e) +{ + char *copy; + if (!ht) + return true; + BOUNDED_TO_ALLOCA (b, e, copy); + return hash_table_get (ht, copy) != NULL; +} + /* Advance P (a char pointer), with the explicit intent of being able to read the next character. If this is not possible, go to finish. */ -#define ADVANCE(p) do { \ - ++p; \ - if (p >= end) \ - goto finish; \ +#define ADVANCE(p) do { \ + ++p; \ + if (p >= end) \ + goto finish; \ } while (0) /* Skip whitespace, if any. */ -#define SKIP_WS(p) do { \ - while (ISSPACE (*p)) { \ - ADVANCE (p); \ - } \ +#define SKIP_WS(p) do { \ + while (c_isspace (*p)) { \ + ADVANCE (p); \ + } \ } while (0) /* Skip non-whitespace, if any. */ -#define SKIP_NON_WS(p) do { \ - while (!ISSPACE (*p)) { \ - ADVANCE (p); \ - } \ +#define SKIP_NON_WS(p) do { \ + while (!c_isspace (*p)) { \ + ADVANCE (p); \ + } \ } while (0) #ifdef STANDALONE @@ -540,48 +815,54 @@ static int tag_backout_count; /* Map MAPFUN over HTML tags in TEXT, which is SIZE characters long. MAPFUN will be called with two arguments: pointer to an initialized - struct taginfo, and CLOSURE. + struct taginfo, and MAPARG. - ALLOWED_TAG_NAMES should be a NULL-terminated array of tag names to - be processed by this function. If it is NULL, all the tags are - allowed. The same goes for attributes and ALLOWED_ATTRIBUTE_NAMES. + ALLOWED_TAGS and ALLOWED_ATTRIBUTES are hash tables the keys of + which are the tags and attribute names that this function should + use. If ALLOWED_TAGS is NULL, all tags are processed; if + ALLOWED_ATTRIBUTES is NULL, all attributes are returned. (Obviously, the caller can filter out unwanted tags and attributes just as well, but this is just an optimization designed to avoid - unnecessary copying for tags/attributes which the caller doesn't - want to know about. These lists are searched linearly; therefore, - if you're interested in a large number of tags or attributes, you'd - better set these to NULL and filter them out yourself with a - hashing process most appropriate for your application.) */ + unnecessary copying of tags/attributes which the caller doesn't + care about.) */ void map_html_tags (const char *text, int size, - const char **allowed_tag_names, - const char **allowed_attribute_names, - void (*mapfun) (struct taginfo *, void *), - void *closure) + void (*mapfun) (struct taginfo *, void *), void *maparg, + int flags, + const struct hash_table *allowed_tags, + const struct hash_table *allowed_attributes) { + /* storage for strings passed to MAPFUN callback; if 256 bytes is + too little, POOL_APPEND allocates more with malloc. */ + char pool_initial_storage[256]; + struct pool pool; + const char *p = text; const char *end = text + size; - int attr_pair_count = 8; - int attr_pair_alloca_p = 1; - struct attr_pair *pairs = ALLOCA_ARRAY (struct attr_pair, attr_pair_count); - struct pool pool; + struct attr_pair attr_pair_initial_storage[8]; + int attr_pair_size = countof (attr_pair_initial_storage); + bool attr_pair_resized = false; + struct attr_pair *pairs = attr_pair_initial_storage; + + struct tagstack_item *head = NULL; + struct tagstack_item *tail = NULL; if (!size) return; - POOL_INIT (pool, 256); + POOL_INIT (&pool, pool_initial_storage, countof (pool_initial_storage)); { int nattrs, end_tag; const char *tag_name_begin, *tag_name_end; const char *tag_start_position; - int uninteresting_tag; + bool uninteresting_tag; look_for_tag: - POOL_REWIND (pool); + POOL_REWIND (&pool); nattrs = 0; end_tag = 0; @@ -599,16 +880,34 @@ map_html_tags (const char *text, int size, declaration). */ if (*p == '!') { - /* This is an SGML declaration -- just skip it. */ - p = advance_declaration (p, end); - if (p == end) - goto finish; - goto look_for_tag; + if (!(flags & MHT_STRICT_COMMENTS) + && p < end + 3 && p[1] == '-' && p[2] == '-') + { + /* If strict comments are not enforced and if we know + we're looking at a comment, simply look for the + terminating "-->". Non-strict is the default because + it works in other browsers and most HTML writers can't + be bothered with getting the comments right. */ + const char *comment_end = find_comment_end (p + 3, end); + if (comment_end) + p = comment_end; + } + else + { + /* Either in strict comment mode or looking at a non-empty + declaration. Real declarations are much less likely to + be misused the way comments are, so advance over them + properly regardless of strictness. */ + p = advance_declaration (p, end); + } + if (p == end) + goto finish; + goto look_for_tag; } else if (*p == '/') { - end_tag = 1; - ADVANCE (p); + end_tag = 1; + ADVANCE (p); } tag_name_begin = p; while (NAME_CHAR_P (*p)) @@ -617,174 +916,189 @@ map_html_tags (const char *text, int size, goto look_for_tag; tag_name_end = p; SKIP_WS (p); - if (end_tag && *p != '>') + + if (!end_tag) + { + struct tagstack_item *ts = tagstack_push (&head, &tail); + if (ts) + { + ts->tagname_begin = tag_name_begin; + ts->tagname_end = tag_name_end; + ts->contents_begin = NULL; + } + } + + if (end_tag && *p != '>' && *p != '<') goto backout_tag; - if (!array_allowed (allowed_tag_names, tag_name_begin, tag_name_end)) + if (!name_allowed (allowed_tags, tag_name_begin, tag_name_end)) /* We can't just say "goto look_for_tag" here because we need the loop below to properly advance over the tag's attributes. */ - uninteresting_tag = 1; + uninteresting_tag = true; else { - uninteresting_tag = 0; - convert_and_copy (&pool, tag_name_begin, tag_name_end, AP_DOWNCASE); + uninteresting_tag = false; + convert_and_copy (&pool, tag_name_begin, tag_name_end, AP_DOWNCASE); } /* Find the attributes. */ while (1) { - const char *attr_name_begin, *attr_name_end; - const char *attr_value_begin, *attr_value_end; - const char *attr_raw_value_begin, *attr_raw_value_end; - int operation = AP_DOWNCASE; /* stupid compiler. */ - - SKIP_WS (p); - - if (*p == '/') - { - /* A slash at this point means the tag is about to be - closed. This is legal in XML and has been popularized - in HTML via XHTML. */ - /* */ - /* ^ */ - ADVANCE (p); - SKIP_WS (p); - if (*p != '>') - goto backout_tag; - } - - /* Check for end of tag definition. */ - if (*p == '>') - break; - - /* Establish bounds of attribute name. */ - attr_name_begin = p; /* */ - /* ^ */ - while (NAME_CHAR_P (*p)) - ADVANCE (p); - attr_name_end = p; /* */ - /* ^ */ - if (attr_name_begin == attr_name_end) - goto backout_tag; - - /* Establish bounds of attribute value. */ - SKIP_WS (p); - if (NAME_CHAR_P (*p) || *p == '/' || *p == '>') - { - /* Minimized attribute syntax allows `=' to be omitted. + const char *attr_name_begin, *attr_name_end; + const char *attr_value_begin, *attr_value_end; + const char *attr_raw_value_begin, *attr_raw_value_end; + int operation = AP_DOWNCASE; /* stupid compiler. */ + + SKIP_WS (p); + + if (*p == '/') + { + /* A slash at this point means the tag is about to be + closed. This is legal in XML and has been popularized + in HTML via XHTML. */ + /* */ + /* ^ */ + ADVANCE (p); + SKIP_WS (p); + if (*p != '<' && *p != '>') + goto backout_tag; + } + + /* Check for end of tag definition. */ + if (*p == '<' || *p == '>') + break; + + /* Establish bounds of attribute name. */ + attr_name_begin = p; /* */ + /* ^ */ + while (NAME_CHAR_P (*p)) + ADVANCE (p); + attr_name_end = p; /* */ + /* ^ */ + if (attr_name_begin == attr_name_end) + goto backout_tag; + + /* Establish bounds of attribute value. */ + SKIP_WS (p); + + if (NAME_CHAR_P (*p) || *p == '/' || *p == '<' || *p == '>') + { + /* Minimized attribute syntax allows `=' to be omitted. For example,
    is a valid shorthand for
      . Even if such attributes are not useful to Wget, we need to support them, so that the tags containing them can be parsed correctly. */ - attr_raw_value_begin = attr_value_begin = attr_name_begin; - attr_raw_value_end = attr_value_end = attr_name_end; - } - else if (*p == '=') - { - ADVANCE (p); - SKIP_WS (p); - if (*p == '\"' || *p == '\'') - { - int newline_seen = 0; - char quote_char = *p; - attr_raw_value_begin = p; - ADVANCE (p); - attr_value_begin = p; /* */ - /* ^ */ - while (*p != quote_char) - { - if (!newline_seen && *p == '\n') - { - /* If a newline is seen within the quotes, it - is most likely that someone forgot to close - the quote. In that case, we back out to - the value beginning, and terminate the tag - at either `>' or the delimiter, whichever - comes first. Such a tag terminated at `>' - is discarded. */ - p = attr_value_begin; - newline_seen = 1; - continue; - } - else if (newline_seen && *p == '>') - break; - ADVANCE (p); - } - attr_value_end = p; /* */ - /* ^ */ - if (*p == quote_char) - ADVANCE (p); - else - goto look_for_tag; - attr_raw_value_end = p; /* */ - /* ^ */ - /* The AP_SKIP_BLANKS part is not entirely correct, - because we don't want to skip blanks for all the - attribute values. */ - operation = AP_PROCESS_ENTITIES | AP_SKIP_BLANKS; - } - else - { - attr_value_begin = p; /* */ - /* ^ */ - /* According to SGML, a name token should consist only - of alphanumerics, . and -. However, this is often - violated by, for instance, `%' in `width=75%'. - We'll be liberal and allow just about anything as - an attribute value. */ - while (!ISSPACE (*p) && *p != '>') - ADVANCE (p); - attr_value_end = p; /* */ - /* ^ */ - if (attr_value_begin == attr_value_end) - /* */ - /* ^ */ - goto backout_tag; - attr_raw_value_begin = attr_value_begin; - attr_raw_value_end = attr_value_end; - operation = AP_PROCESS_ENTITIES; - } - } - else - { - /* We skipped the whitespace and found something that is - neither `=' nor the beginning of the next attribute's - name. Back out. */ - goto backout_tag; /* */ + /* ^ */ + while (*p != quote_char) + { + if (!newline_seen && *p == '\n') + { + /* If a newline is seen within the quotes, it + is most likely that someone forgot to close + the quote. In that case, we back out to + the value beginning, and terminate the tag + at either `>' or the delimiter, whichever + comes first. Such a tag terminated at `>' + is discarded. */ + p = attr_value_begin; + newline_seen = true; + continue; + } + else if (newline_seen && (*p == '<' || *p == '>')) + break; + ADVANCE (p); + } + attr_value_end = p; /* */ + /* ^ */ + if (*p == quote_char) + ADVANCE (p); + else + goto look_for_tag; + attr_raw_value_end = p; /* */ + /* ^ */ + operation = AP_DECODE_ENTITIES; + if (flags & MHT_TRIM_VALUES) + operation |= AP_TRIM_BLANKS; + } + else + { + attr_value_begin = p; /* */ + /* ^ */ + /* According to SGML, a name token should consist only + of alphanumerics, . and -. However, this is often + violated by, for instance, `%' in `width=75%'. + We'll be liberal and allow just about anything as + an attribute value. */ + while (!c_isspace (*p) && *p != '<' && *p != '>') + ADVANCE (p); + attr_value_end = p; /* */ + /* ^ */ + if (attr_value_begin == attr_value_end) + /* */ + /* ^ */ + goto backout_tag; + attr_raw_value_begin = attr_value_begin; + attr_raw_value_end = attr_value_end; + operation = AP_DECODE_ENTITIES; + } + } + else + { + /* We skipped the whitespace and found something that is + neither `=' nor the beginning of the next attribute's + name. Back out. */ + goto backout_tag; /* tagname_begin == tag_name_begin)) + { + tail->contents_begin = p+1; } if (uninteresting_tag) { - ADVANCE (p); - goto look_for_tag; + ADVANCE (p); + goto look_for_tag; } /* By now, we have a valid tag with a name and zero or more @@ -792,25 +1106,43 @@ map_html_tags (const char *text, int size, { int i; struct taginfo taginfo; + struct tagstack_item *ts = NULL; taginfo.name = pool.contents; taginfo.end_tag_p = end_tag; taginfo.nattrs = nattrs; /* We fill in the char pointers only now, when pool can no - longer get realloc'ed. If we did that above, we could get - hosed by reallocation. Obviously, after this point, the pool - may no longer be grown. */ + longer get realloc'ed. If we did that above, we could get + hosed by reallocation. Obviously, after this point, the pool + may no longer be grown. */ for (i = 0; i < nattrs; i++) - { - pairs[i].name = pool.contents + pairs[i].name_pool_index; - pairs[i].value = pool.contents + pairs[i].value_pool_index; - } + { + pairs[i].name = pool.contents + pairs[i].name_pool_index; + pairs[i].value = pool.contents + pairs[i].value_pool_index; + } taginfo.attrs = pairs; taginfo.start_position = tag_start_position; taginfo.end_position = p + 1; - /* Ta-dam! */ - (*mapfun) (&taginfo, closure); - ADVANCE (p); + taginfo.contents_begin = NULL; + taginfo.contents_end = NULL; + + if (end_tag) + { + ts = tagstack_find (tail, tag_name_begin, tag_name_end); + if (ts) + { + if (ts->contents_begin) + { + taginfo.contents_begin = ts->contents_begin; + taginfo.contents_end = tag_start_position; + } + tagstack_pop (&head, &tail, ts); + } + } + + mapfun (&taginfo, maparg); + if (*p != '<') + ADVANCE (p); } goto look_for_tag; @@ -825,9 +1157,11 @@ map_html_tags (const char *text, int size, } finish: - POOL_FREE (pool); - if (!attr_pair_alloca_p) + POOL_FREE (&pool); + if (attr_pair_resized) xfree (pairs); + /* pop any tag stack that's left */ + tagstack_pop (&head, &tail, head); } #undef ADVANCE @@ -850,7 +1184,7 @@ test_mapper (struct taginfo *taginfo, void *arg) int main () { int size = 256; - char *x = (char *)xmalloc (size); + char *x = xmalloc (size); int length = 0; int read_count; int tag_counter = 0; @@ -859,10 +1193,10 @@ int main () { length += read_count; size <<= 1; - x = (char *)xrealloc (x, size); + x = xrealloc (x, size); } - map_html_tags (x, length, NULL, NULL, test_mapper, &tag_counter); + map_html_tags (x, length, test_mapper, &tag_counter, 0, NULL, NULL); printf ("TAGS: %d\n", tag_counter); printf ("Tag backouts: %d\n", tag_backout_count); printf ("Comment backouts: %d\n", comment_backout_count);