netsurf/content/handlers/html/layout/table.c

/*
 * Copyright 2023 Vincent Sanders <vince@netsurf-browser.org>
 *
 * This file is part of NetSurf, http://www.netsurf-browser.org/
 *
 * NetSurf 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; version 2 of the License.
 *
 * NetSurf is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * 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 this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * \file
 * HTML layout implementation for tables
 */

#include <stdbool.h>
#include <string.h>
#include <math.h>

#include "utils/log.h"
#include "utils/utils.h"
#include "netsurf/types.h"
#include "netsurf/mouse.h"
#include "desktop/scrollbar.h"

#include "html/private.h"
#include "html/box.h"
#include "html/table.h"

#include "html/layout/internal.h"
#include "html/layout/block.h"
#include "html/layout/table.h"

/**
 * Moves the children of a box by a specified amount
 *
 * \param  box  top of tree of boxes
 * \param  x	the amount to move children by horizontally
 * \param  y	the amount to move children by vertically
 */
static void layout_move_children(struct box *box, int x, int y)
{
	assert(box);

	for (box = box->children; box; box = box->next) {
		box->x += x;
		box->y += y;
	}
}

/* Documented in layout_table.h */
bool layout_table(struct box *table, int available_width, html_content *content)
{
	unsigned int columns = table->columns;  /* total columns */
	unsigned int i;
	unsigned int *row_span;
	int *excess_y;
	int table_width, min_width = 0, max_width = 0;
	int required_width = 0;
	int x, remainder = 0, count = 0;
	int table_height = 0;
	int min_height = 0;
	int *xs;  /* array of column x positions */
	int auto_width;
	int spare_width;
	int relative_sum = 0;
	int border_spacing_h = 0, border_spacing_v = 0;
	int spare_height;
	int positioned_columns = 0;
	struct box *containing_block = NULL;
	struct box *c;
	struct box *row;
	struct box *row_group;
	struct box **row_span_cell;
	struct column *col;
	const css_computed_style *style = table->style;
	enum css_width_e wtype;
	enum css_height_e htype;
	css_fixed value = 0;
	css_unit unit = CSS_UNIT_PX;

	assert(table->type == BOX_TABLE);
	assert(style);
	assert(table->children && table->children->children);
	assert(columns);

	/* allocate working buffers */
	col = malloc(columns * sizeof col[0]);
	excess_y = malloc(columns * sizeof excess_y[0]);
	row_span = malloc(columns * sizeof row_span[0]);
	row_span_cell = malloc(columns * sizeof row_span_cell[0]);
	xs = malloc((columns + 1) * sizeof xs[0]);
	if (!col || !xs || !row_span || !excess_y || !row_span_cell) {
		free(col);
		free(excess_y);
		free(row_span);
		free(row_span_cell);
		free(xs);
		return false;
	}

	memcpy(col, table->col, sizeof(col[0]) * columns);

	/* find margins, paddings, and borders for table and cells */
	layout_find_dimensions(&content->unit_len_ctx, available_width, -1, table,
			       style, 0, 0, 0, 0, 0, 0, table->margin, table->padding,
			       table->border);
	for (row_group = table->children; row_group;
	     row_group = row_group->next) {
		for (row = row_group->children; row; row = row->next) {
			for (c = row->children; c; c = c->next) {
				enum css_overflow_e overflow_x;
				enum css_overflow_e overflow_y;

				assert(c->style);
				table_used_border_for_cell(
					&content->unit_len_ctx, c);
				layout_find_dimensions(&content->unit_len_ctx,
						       available_width, -1, c,
						       c->style, 0, 0, 0, 0, 0, 0,
						       0, c->padding, c->border);

				overflow_x = css_computed_overflow_x(c->style);
				overflow_y = css_computed_overflow_y(c->style);

				if (overflow_x == CSS_OVERFLOW_SCROLL ||
				    overflow_x ==
				    CSS_OVERFLOW_AUTO) {
					c->padding[BOTTOM] += SCROLLBAR_WIDTH;
				}
				if (overflow_y == CSS_OVERFLOW_SCROLL ||
				    overflow_y ==
				    CSS_OVERFLOW_AUTO) {
					c->padding[RIGHT] += SCROLLBAR_WIDTH;
				}
			}
		}
	}

	/* border-spacing is used in the separated borders model */
	if (css_computed_border_collapse(style) ==
	    CSS_BORDER_COLLAPSE_SEPARATE) {
		css_fixed h = 0, v = 0;
		css_unit hu = CSS_UNIT_PX, vu = CSS_UNIT_PX;

		css_computed_border_spacing(style, &h, &hu, &v, &vu);

		border_spacing_h = FIXTOINT(css_unit_len2device_px(
						    style, &content->unit_len_ctx, h, hu));
		border_spacing_v = FIXTOINT(css_unit_len2device_px(
						    style, &content->unit_len_ctx, v, vu));
	}

	/* find specified table width, or available width if auto-width */
	wtype = css_computed_width(style, &value, &unit);
	if (wtype == CSS_WIDTH_SET) {
		if (unit == CSS_UNIT_PCT) {
			table_width = FPCT_OF_INT_TOINT(value, available_width);
		} else {
			table_width =
				FIXTOINT(css_unit_len2device_px(
						 style, &content->unit_len_ctx,
						 value, unit));
		}

		/* specified width includes border */
		table_width -= table->border[LEFT].width +
			table->border[RIGHT].width;
		table_width = table_width < 0 ? 0 : table_width;

		auto_width = table_width;
	} else {
		table_width = AUTO;
		auto_width = available_width -
			((table->margin[LEFT] == AUTO ? 0 :
			  table->margin[LEFT]) +
			 table->border[LEFT].width +
			 table->padding[LEFT] +
			 table->padding[RIGHT] +
			 table->border[RIGHT].width +
			 (table->margin[RIGHT] == AUTO ? 0 :
			  table->margin[RIGHT]));
	}

	/* Find any table height specified within CSS/HTML */
	htype = css_computed_height(style, &value, &unit);
	if (htype == CSS_HEIGHT_SET) {
		if (unit == CSS_UNIT_PCT) {
			/* This is the minimum height for the table
			 * (see 17.5.3) */
			if (css_computed_position(table->style) ==
			    CSS_POSITION_ABSOLUTE) {
				/* Table is absolutely positioned */
				assert(table->float_container);
				containing_block = table->float_container;
			} else if (table->float_container &&
				   css_computed_position(table->style) !=
				   CSS_POSITION_ABSOLUTE &&
				   (css_computed_float(table->style) ==
				    CSS_FLOAT_LEFT ||
				    css_computed_float(table->style) ==
				    CSS_FLOAT_RIGHT)) {
				/* Table is a float */
				assert(table->parent && table->parent->parent &&
				       table->parent->parent->parent);
				containing_block =
					table->parent->parent->parent;
			} else if (table->parent && table->parent->type !=
				   BOX_INLINE_CONTAINER) {
				/* Table is a block level element */
				containing_block = table->parent;
			} else if (table->parent && table->parent->type ==
				   BOX_INLINE_CONTAINER) {
				/* Table is an inline block */
				assert(table->parent->parent);
				containing_block = table->parent->parent;
			}

			if (containing_block) {
				css_fixed ignored = 0;

				htype = css_computed_height(
					containing_block->style,
					&ignored, &unit);
			}

			if (containing_block &&
			    containing_block->height != AUTO &&
			    (css_computed_position(table->style) ==
			     CSS_POSITION_ABSOLUTE ||
			     htype == CSS_HEIGHT_SET)) {
				/* Table is absolutely positioned or its
				 * containing block has a valid specified
				 * height. (CSS 2.1 Section 10.5) */
				min_height = FPCT_OF_INT_TOINT(value,
							       containing_block->height);
			}
		} else {
			/* This is the minimum height for the table
			 * (see 17.5.3) */
			min_height = FIXTOINT(css_unit_len2device_px(
						      style, &content->unit_len_ctx,
						      value, unit));
		}
	}

	/* calculate width required by cells */
	for (i = 0; i != columns; i++) {

		NSLOG(layout, DEBUG,
		      "table %p, column %u: type %s, width %i, min %i, max %i",
		      table,
		      i,
		      ((const char *[]){
			      "UNKNOWN",
			      "FIXED",
			      "AUTO",
			      "PERCENT",
			      "RELATIVE",
		      })[col[i].type],
		      col[i].width,
		      col[i].min,
		      col[i].max);


		if (col[i].positioned) {
			positioned_columns++;
			continue;
		} else if (col[i].type == COLUMN_WIDTH_FIXED) {
			if (col[i].width < col[i].min)
				col[i].width = col[i].max = col[i].min;
			else
				col[i].min = col[i].max = col[i].width;
			required_width += col[i].width;
		} else if (col[i].type == COLUMN_WIDTH_PERCENT) {
			int width = col[i].width * auto_width / 100;
			required_width += col[i].min < width ? width :
				col[i].min;
		} else
			required_width += col[i].min;

		NSLOG(layout, DEBUG,  "required_width %i", required_width);
	}
	required_width += (columns + 1 - positioned_columns) *
		border_spacing_h;

	NSLOG(layout, DEBUG,
	      "width %i, min %i, max %i, auto %i, required %i", table_width,
	      table->min_width, table->max_width, auto_width, required_width);

	if (auto_width < required_width) {
		/* table narrower than required width for columns:
		 * treat percentage widths as maximums */
		for (i = 0; i != columns; i++) {
			if (col[i].type == COLUMN_WIDTH_RELATIVE)
				continue;
			if (col[i].type == COLUMN_WIDTH_PERCENT) {
				col[i].max = auto_width * col[i].width / 100;
				if (col[i].max < col[i].min)
					col[i].max = col[i].min;
			}
			min_width += col[i].min;
			max_width += col[i].max;
		}
	} else {
		/* take percentages exactly */
		for (i = 0; i != columns; i++) {
			if (col[i].type == COLUMN_WIDTH_RELATIVE)
				continue;
			if (col[i].type == COLUMN_WIDTH_PERCENT) {
				int width = auto_width * col[i].width / 100;
				if (width < col[i].min)
					width = col[i].min;
				col[i].min = col[i].width = col[i].max = width;
				col[i].type = COLUMN_WIDTH_FIXED;
			}
			min_width += col[i].min;
			max_width += col[i].max;
		}
	}

	/* allocate relative widths */
	spare_width = auto_width;
	for (i = 0; i != columns; i++) {
		if (col[i].type == COLUMN_WIDTH_RELATIVE)
			relative_sum += col[i].width;
		else if (col[i].type == COLUMN_WIDTH_FIXED)
			spare_width -= col[i].width;
		else
			spare_width -= col[i].min;
	}
	spare_width -= (columns + 1) * border_spacing_h;
	if (relative_sum != 0) {
		if (spare_width < 0)
			spare_width = 0;
		for (i = 0; i != columns; i++) {
			if (col[i].type == COLUMN_WIDTH_RELATIVE) {
				col[i].min = ceil(col[i].max =
						  (float) spare_width
						  * (float) col[i].width
						  / relative_sum);
				min_width += col[i].min;
				max_width += col[i].max;
			}
		}
	}
	min_width += (columns + 1) * border_spacing_h;
	max_width += (columns + 1) * border_spacing_h;

	if (auto_width <= min_width) {
		/* not enough space: minimise column widths */
		for (i = 0; i < columns; i++) {
			col[i].width = col[i].min;
		}
		table_width = min_width;
	} else if (max_width <= auto_width) {
		/* more space than maximum width */
		if (table_width == AUTO) {
			/* for auto-width tables, make columns max width */
			for (i = 0; i < columns; i++) {
				col[i].width = col[i].max;
			}
			table_width = max_width;
		} else {
			/* for fixed-width tables, distribute the extra space
			 * too */
			unsigned int flexible_columns = 0;
			for (i = 0; i != columns; i++)
				if (col[i].type != COLUMN_WIDTH_FIXED)
					flexible_columns++;
			if (flexible_columns == 0) {
				int extra = (table_width - max_width) / columns;
				remainder = (table_width - max_width) -
					(extra * columns);
				for (i = 0; i != columns; i++) {
					col[i].width = col[i].max + extra;
					count -= remainder;
					if (count < 0) {
						col[i].width++;
						count += columns;
					}
				}

			} else {
				int extra = (table_width - max_width) /
					flexible_columns;
				remainder = (table_width - max_width) -
					(extra * flexible_columns);
				for (i = 0; i != columns; i++)
					if (col[i].type != COLUMN_WIDTH_FIXED) {
						col[i].width = col[i].max +
							extra;
						count -= remainder;
						if (count < 0) {
							col[i].width++;
							count += flexible_columns;
						}
					}
			}
		}
	} else {
		/* space between min and max: fill it exactly */
		float scale = (float) (auto_width - min_width) /
			(float) (max_width - min_width);
		/* fprintf(stderr, "filling, scale %f\n", scale); */
		for (i = 0; i < columns; i++) {
			col[i].width = col[i].min + (int) (0.5 +
							   (col[i].max - col[i].min) * scale);
		}
		table_width = auto_width;
	}

	xs[0] = x = border_spacing_h;
	for (i = 0; i != columns; i++) {
		if (!col[i].positioned)
			x += col[i].width + border_spacing_h;
		xs[i + 1] = x;
		row_span[i] = 0;
		excess_y[i] = 0;
		row_span_cell[i] = 0;
	}

	/* position cells */
	table_height = border_spacing_v;
	for (row_group = table->children; row_group;
	     row_group = row_group->next) {
		int row_group_height = 0;
		for (row = row_group->children; row; row = row->next) {
			int row_height = 0;

			htype = css_computed_height(row->style, &value, &unit);
			if (htype == CSS_HEIGHT_SET && unit != CSS_UNIT_PCT) {
				row_height = FIXTOINT(css_unit_len2device_px(
							      row->style,
							      &content->unit_len_ctx,
							      value, unit));
			}
			for (c = row->children; c; c = c->next) {
				assert(c->style);
				c->width = xs[c->start_column + c->columns] -
					xs[c->start_column] -
					border_spacing_h -
					c->border[LEFT].width -
					c->padding[LEFT] -
					c->padding[RIGHT] -
					c->border[RIGHT].width;
				c->float_children = 0;
				c->cached_place_below_level = 0;

				c->height = AUTO;
				if (!layout_block_context(c, -1, content)) {
					free(col);
					free(excess_y);
					free(row_span);
					free(row_span_cell);
					free(xs);
					return false;
				}
				/* warning: c->descendant_y0 and
				 * c->descendant_y1 used as temporary storage
				 * until after vertical alignment is complete */
				c->descendant_y0 = c->height;
				c->descendant_y1 = c->padding[BOTTOM];

				htype = css_computed_height(c->style,
							    &value, &unit);

				if (htype == CSS_HEIGHT_SET &&
				    unit != CSS_UNIT_PCT) {
					/* some sites use height="1" or similar
					 * to attempt to make cells as small as
					 * possible, so treat it as a minimum */
					int h = FIXTOINT(css_unit_len2device_px(
								 c->style,
								 &content->unit_len_ctx,
								 value, unit));
					if (c->height < h)
						c->height = h;
				}
				/* specified row height is treated as a minimum
				 */
				if (c->height < row_height)
					c->height = row_height;
				c->x = xs[c->start_column] +
					c->border[LEFT].width;
				c->y = c->border[TOP].width;
				for (i = 0; i != c->columns; i++) {
					row_span[c->start_column + i] = c->rows;
					excess_y[c->start_column + i] =
						c->border[TOP].width +
						c->padding[TOP] +
						c->height +
						c->padding[BOTTOM] +
						c->border[BOTTOM].width;
					row_span_cell[c->start_column + i] = 0;
				}
				row_span_cell[c->start_column] = c;
				c->padding[BOTTOM] = -border_spacing_v -
					c->border[TOP].width -
					c->padding[TOP] -
					c->height -
					c->border[BOTTOM].width;
			}
			for (i = 0; i != columns; i++)
				if (row_span[i] != 0)
					row_span[i]--;
				else
					row_span_cell[i] = 0;
			if (row->next || row_group->next) {
				/* row height is greatest excess of a cell
				 * which ends in this row */
				for (i = 0; i != columns; i++)
					if (row_span[i] == 0 && row_height <
					    excess_y[i])
						row_height = excess_y[i];
			} else {
				/* except in the last row */
				for (i = 0; i != columns; i++)
					if (row_height < excess_y[i])
						row_height = excess_y[i];
			}
			for (i = 0; i != columns; i++) {
				if (row_height < excess_y[i])
					excess_y[i] -= row_height;
				else
					excess_y[i] = 0;
				if (row_span_cell[i] != 0)
					row_span_cell[i]->padding[BOTTOM] +=
						row_height +
						border_spacing_v;
			}

			row->x = 0;
			row->y = row_group_height;
			row->width = table_width;
			row->height = row_height;
			row_group_height += row_height + border_spacing_v;
		}
		row_group->x = 0;
		row_group->y = table_height;
		row_group->width = table_width;
		row_group->height = row_group_height;
		table_height += row_group_height;
	}
	/* Table height is either the height of the contents, or specified
	 * height if greater */
	table_height = max(table_height, min_height);
	/** \todo distribute spare height over the row groups / rows / cells */

	/* perform vertical alignment */
	for (row_group = table->children; row_group;
	     row_group = row_group->next) {
		for (row = row_group->children; row; row = row->next) {
			for (c = row->children; c; c = c->next) {
				enum css_vertical_align_e vertical_align;

				/* unextended bottom padding is in
				 * c->descendant_y1, and unextended
				 * cell height is in c->descendant_y0 */
				spare_height = (c->padding[BOTTOM] -
						c->descendant_y1) +
					(c->height - c->descendant_y0);

				vertical_align = css_computed_vertical_align(
					c->style, &value, &unit);

				switch (vertical_align) {
				case CSS_VERTICAL_ALIGN_SUB:
				case CSS_VERTICAL_ALIGN_SUPER:
				case CSS_VERTICAL_ALIGN_TEXT_TOP:
				case CSS_VERTICAL_ALIGN_TEXT_BOTTOM:
				case CSS_VERTICAL_ALIGN_SET:
				case CSS_VERTICAL_ALIGN_BASELINE:
					/* todo: baseline alignment, for now
					 * just use ALIGN_TOP */
				case CSS_VERTICAL_ALIGN_TOP:
					break;
				case CSS_VERTICAL_ALIGN_MIDDLE:
					c->padding[TOP] += spare_height / 2;
					c->padding[BOTTOM] -= spare_height / 2;
					layout_move_children(c, 0,
							     spare_height / 2);
					break;
				case CSS_VERTICAL_ALIGN_BOTTOM:
					c->padding[TOP] += spare_height;
					c->padding[BOTTOM] -= spare_height;
					layout_move_children(c, 0,
							     spare_height);
					break;
				case CSS_VERTICAL_ALIGN_INHERIT:
					assert(0);
					break;
				}
			}
		}
	}

	/* Top and bottom margins of 'auto' are set to 0.  CSS2.1 10.6.3 */
	if (table->margin[TOP] == AUTO)
		table->margin[TOP] = 0;
	if (table->margin[BOTTOM] == AUTO)
		table->margin[BOTTOM] = 0;

	free(col);
	free(excess_y);
	free(row_span);
	free(row_span_cell);
	free(xs);

	table->width = table_width;
	table->height = table_height;

	return true;
}