table.c

一个很有名的浏览器

/* HTML tables parser */
/* $Id: table.c,v 1.35.2.2 2005/04/05 21:08:41 jonas Exp $ */

/* Note that this does *not* fit to the HTML parser infrastructure yet, it has
 * some special custom calling conventions and is managed from
 * document/html/tables.c. */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <errno.h>
#include <stdlib.h>
#include <string.h>

#include "elinks.h"

#include "document/html/parser/parse.h"
#include "document/html/parser/table.h"
#include "document/html/parser.h"
#include "document/options.h"
#include "util/color.h"
#include "util/conv.h"
#include "util/error.h"
#include "util/memory.h"

/* Unsafe macros */
#include "document/html/internal.h"


#define INIT_REAL_COLS		2
#define INIT_REAL_ROWS		2

#define realloc_bad_html(bad_html, size) \
	mem_align_alloc(bad_html, size, (size) + 1, struct html_start_end, 0xFF)

static void
add_table_bad_html_start(struct table *table, unsigned char *start)
{
	if (table->caption.start && !table->caption.end)
		return;

	/* Either no bad html or last one not needing @end pointer */
	if (table->bad_html_size
	    && !table->bad_html[table->bad_html_size - 1].end)
		return;

	if (realloc_bad_html(&table->bad_html, table->bad_html_size))
		table->bad_html[table->bad_html_size++].start = start;
}

static void
add_table_bad_html_end(struct table *table, unsigned char *end)
{
	if (table->caption.start && !table->caption.end) {
		table->caption.end = end;
		return;
	}

	if (table->bad_html_size
	    && !table->bad_html[table->bad_html_size - 1].end)
		table->bad_html[table->bad_html_size - 1].end = end;
}


static void
get_bordercolor(unsigned char *a, color_t *rgb)
{
	unsigned char *at;

	if (!use_document_fg_colors(global_doc_opts))
		return;

	at = get_attr_val(a, "bordercolor");
	/* Try some other MSIE-specific attributes if any. */
	if (!at) at = get_attr_val(a, "bordercolorlight");
	if (!at) at = get_attr_val(a, "bordercolordark");
	if (!at) return;

	decode_color(at, strlen(at), rgb);
	mem_free(at);
}

static void
get_align(unsigned char *attr, int *a)
{
	unsigned char *al = get_attr_val(attr, "align");

	if (!al) return;

	if (!strcasecmp(al, "left")) *a = ALIGN_LEFT;
	else if (!strcasecmp(al, "right")) *a = ALIGN_RIGHT;
	else if (!strcasecmp(al, "center")) *a = ALIGN_CENTER;
	else if (!strcasecmp(al, "justify")) *a = ALIGN_JUSTIFY;
	else if (!strcasecmp(al, "char")) *a = ALIGN_RIGHT; /* NOT IMPLEMENTED */
	mem_free(al);
}

static void
get_valign(unsigned char *attr, int *a)
{
	unsigned char *al = get_attr_val(attr, "valign");

	if (!al) return;

	if (!strcasecmp(al, "top")) *a = VALIGN_TOP;
	else if (!strcasecmp(al, "middle")) *a = VALIGN_MIDDLE;
	else if (!strcasecmp(al, "bottom")) *a = VALIGN_BOTTOM;
	else if (!strcasecmp(al, "baseline")) *a = VALIGN_BASELINE; /* NOT IMPLEMENTED */
	mem_free(al);
}

static void
get_column_width(unsigned char *attr, int *width, int sh)
{
	unsigned char *al = get_attr_val(attr, "width");
	int len;

	if (!al) return;

	len = strlen(al);
	if (len && al[len - 1] == '*') {
		unsigned char *en;
		int n;

		al[len - 1] = '\0';
		errno = 0;
		n = strtoul(al, (char **) &en, 10);
		if (!errno && n >= 0 && !*en)
			*width = WIDTH_RELATIVE - n;
	} else {
		int w = get_width(attr, "width", sh);

		if (w >= 0) *width = w;
	}
	mem_free(al);
}

static void
set_table_frame(struct table *table, unsigned char *attr)
{
	unsigned char *al;

	if (!table->border) {
		table->frame = TABLE_FRAME_VOID;
		return;
	}

	table->frame = TABLE_FRAME_BOX;

	al = get_attr_val(attr, "frame");
	if (!al) return;

	if (!strcasecmp(al, "void")) table->frame = TABLE_FRAME_VOID;
	else if (!strcasecmp(al, "above")) table->frame = TABLE_FRAME_ABOVE;
	else if (!strcasecmp(al, "below")) table->frame = TABLE_FRAME_BELOW;
	else if (!strcasecmp(al, "hsides")) table->frame = TABLE_FRAME_HSIDES;
	else if (!strcasecmp(al, "vsides")) table->frame = TABLE_FRAME_VSIDES;
	else if (!strcasecmp(al, "lhs")) table->frame = TABLE_FRAME_LHS;
	else if (!strcasecmp(al, "rhs")) table->frame = TABLE_FRAME_RHS;
	/* Following tests are useless since TABLE_FRAME_BOX is the default.
	 * else if (!strcasecmp(al, "box")) table->frame = TABLE_FRAME_BOX;
	 * else if (!strcasecmp(al, "border")) table->frame = TABLE_FRAME_BOX;
	 */
	mem_free(al);
}

static void
set_table_rules(struct table *table, unsigned char *attr)
{
	unsigned char *al;

	table->rules = table->border ? TABLE_RULE_ALL : TABLE_RULE_NONE;

	al = get_attr_val(attr, "rules");
	if (!al) return;

	if (!strcasecmp(al, "none")) table->rules = TABLE_RULE_NONE;
	else if (!strcasecmp(al, "groups")) table->rules = TABLE_RULE_GROUPS;
	else if (!strcasecmp(al, "rows")) table->rules = TABLE_RULE_ROWS;
	else if (!strcasecmp(al, "cols")) table->rules = TABLE_RULE_COLS;
	else if (!strcasecmp(al, "all")) table->rules = TABLE_RULE_ALL;
	mem_free(al);
}

static void
parse_table_attributes(struct table *table, unsigned char *attr, int real)
{
	table->fragment_id = get_attr_val(attr, "id");

	get_bordercolor(attr, &table->bordercolor);

	table->width = get_width(attr, "width", real);
	if (table->width == -1) {
		table->width = get_html_max_width();
		table->full_width = 1;
	}

	/* From http://www.w3.org/TR/html4/struct/tables.html#adef-border-TABLE
	 * The following settings should be observed by user agents for
	 * backwards compatibility.
	 * Setting border="0" implies frame="void" and, unless otherwise
	 * specified, rules="none".
	 * Other values of border imply frame="border" and, unless otherwise
	 * specified, rules="all".
	 * The value "border" in the start tag of the TABLE element should be
	 * interpreted as the value of the frame attribute. It implies
	 * rules="all" and some default (non-zero) value for the border
	 * attribute. */
	table->border = get_num(attr, "border");
	if (table->border == -1) {
		table->border = has_attr(attr, "border")
				|| has_attr(attr, "rules")
				|| has_attr(attr, "frame");
	}

	if (table->border) {
		int_upper_bound(&table->border, 2);

		table->cellspacing = get_num(attr, "cellspacing");
		int_bounds(&table->cellspacing, 1, 2);
	}

	set_table_frame(table, attr);

	table->cellpadding = get_num(attr, "cellpadding");
	if (table->cellpadding == -1) {
		table->vcellpadding = 0;
		table->cellpadding = !!table->border;
	} else {
		table->vcellpadding = (table->cellpadding >= HTML_CHAR_HEIGHT / 2 + 1);
		table->cellpadding = (table->cellpadding >= HTML_CHAR_WIDTH / 2 + 1);
	}

	set_table_rules(table, attr);

	table->align = par_format.align;
	get_align(attr, &table->align);

	table->bgcolor = par_format.bgcolor;
	get_bgcolor(attr, &table->bgcolor);
}


static struct table *
new_table(void)
{
	struct table *table = mem_calloc(1, sizeof(*table));

	if (!table) return NULL;

	table->cells = mem_calloc(INIT_REAL_COLS * INIT_REAL_ROWS,
				  sizeof(*table->cells));
	if (!table->cells) {
		mem_free(table);
		return NULL;
	}
	table->real_cols = INIT_REAL_COLS;
	table->real_rows = INIT_REAL_ROWS;

	table->columns = mem_calloc(INIT_REAL_COLS, sizeof(*table->columns));
	if (!table->columns) {
		mem_free(table->cells);
		mem_free(table);
		return NULL;
	}
	table->real_columns_count = INIT_REAL_COLS;

	return table;
}

void
free_table(struct table *table)
{
	int col, row;

	mem_free_if(table->min_cols_widths);
	mem_free_if(table->max_cols_widths);
	mem_free_if(table->cols_widths);
	mem_free_if(table->rows_heights);
	mem_free_if(table->fragment_id);
	mem_free_if(table->cols_x);
	mem_free_if(table->bad_html);

	for (col = 0; col < table->cols; col++)
		for (row = 0; row < table->rows; row++)
			mem_free_if(CELL(table, col, row)->fragment_id);

	mem_free(table->cells);
	mem_free(table->columns);
	mem_free(table);
}

static void
expand_cells(struct table *table, int dest_col, int dest_row)
{
	if (dest_col >= table->cols) {
		if (table->cols) {
			int last_col = table->cols - 1;
			int row;

			for (row = 0; row < table->rows; row++) {
				int col;
				struct table_cell *cellp = CELL(table, last_col, row);

				if (cellp->colspan != -1) continue;

				for (col = table->cols; col <= dest_col; col++) {
					struct table_cell *cell = CELL(table, col, row);

					cell->is_used = 1;
					cell->is_spanned = 1;
					cell->rowspan = cellp->rowspan;
					cell->colspan = -1;
					cell->col = cellp->col;
					cell->row = cellp->row;
				}
			}
		}
		table->cols = dest_col + 1;
	}

	if (dest_row >= table->rows) {
		if (table->rows) {
			int last_row = table->rows - 1;
			int col;

			for (col = 0; col < table->cols; col++) {
				int row;
				struct table_cell *cellp = CELL(table, col, last_row);

				if (cellp->rowspan != -1) continue;

				for (row = table->rows; row <= dest_row; row++) {
					struct table_cell *cell = CELL(table, col, row);

					cell->is_used = 1;
					cell->is_spanned = 1;
					cell->rowspan = -1;
					cell->colspan = cellp->colspan;
					cell->col = cellp->col;
					cell->row = cellp->row;
				}
			}
		}
		table->rows = dest_row + 1;
	}
}

static void
copy_table(struct table *table_src, struct table *table_dst)
{
	int row;
	int size = sizeof(*table_dst->cells) * table_src->cols;

	if (!size) return;

	for (row = 0; row < table_src->rows; row++) {
		memcpy(&table_dst->cells[row * table_dst->real_cols],
		       &table_src->cells[row * table_src->real_cols],
		       size);
	}
}


#define SMART_RAISE_LIMIT 256*1024
static inline int
smart_raise(int target, int base, int unit, int limit)
{
	while (target > base) {
		int orig_base = base;

		/* Until we reach 256kb we go fast. Then we raise
		 * by 256kb amounts. */
		if (base < limit / unit) {
			base <<= 1;
		} else {
			base += limit / unit;
		}
		/* Overflow? */
		if (base <= orig_base) return 0;
	}
	return base;
}

static struct table_cell *
new_cell(struct table *table, int dest_col, int dest_row)
{
	if (dest_col < table->cols && dest_row < table->rows)
		return CELL(table, dest_col, dest_row);

	while (1) {
		struct table new;
		int limit;

		if (dest_col < table->real_cols && dest_row < table->real_rows) {
			expand_cells(table, dest_col, dest_row);
			return CELL(table, dest_col, dest_row);
		}

		new.real_cols = smart_raise(dest_col + 1, table->real_cols,
					    sizeof(*new.cells),
					    /* assume square distribution of
					     * cols/rows */
					    SMART_RAISE_LIMIT / 2);
		if (!new.real_cols) return NULL;

		limit = SMART_RAISE_LIMIT
		      - sizeof(*new.cells) * new.real_cols;
		limit = MAX(limit, SMART_RAISE_LIMIT/2);

		new.real_rows = smart_raise(dest_row + 1, table->real_rows,
					    sizeof(*new.cells), limit);
		if (!new.real_rows) return NULL;

		new.cells = mem_calloc(new.real_cols * new.real_rows,
				       sizeof(*new.cells));
		if (!new.cells) return NULL;

		copy_table(table, &new);

		mem_free(table->cells);
		table->cells	 = new.cells;
		table->real_cols = new.real_cols;
		table->real_rows = new.real_rows;
	}
}

static void
new_columns(struct table *table, int span, int width, int align,
	    int valign, int group)
{
	if (table->columns_count + span > table->real_columns_count) {
		int n = table->real_columns_count;
		struct table_column *new_columns;

		n = smart_raise(table->columns_count + span, n,
				sizeof(*new_columns), SMART_RAISE_LIMIT);
		if (!n) return;

		new_columns = mem_realloc(table->columns, n * sizeof(*new_columns));
		if (!new_columns) return;

		table->real_columns_count = n;
		table->columns = new_columns;
	}