# Table layout

Copyright © 1995-2010 Opera Software AS. All rights reserved. This file is part of the Opera web browser. It may not be distributed under any circumstances.
$Id: tables.html,v 1.11.1252.1.104.1 2010/03/17 15:10:22 mstensho Exp $

## Introduction

This document attempts to describe the table layout algorithm used in Opera - in particular the automatic table layout algorithm. The CSS spec doesn't even attempt to describe this algorithm decently. It does however state that "For the automatic table layout algorithm, some widely deployed implementations have achieved relatively close interoperability". And we're trying our best to do exactly that, mostly by following IE as closely as possible/reasonable. Mozilla behavior is also taken into account.

NOTE: This specification is not yet complete. It does not describe rowspan or height calculation.

## Overview

Table layout requires two passes in the layout engine. In the first (initial) pass, width information (desired width, percentage) about each cell and column box is gathered and stored in a column array. The minimum and maximum width of each cell is also calculated. When all cell minimum and maximum widths have been found, the total table minimum and maximum width is calculated. In the second (final) pass, the total width of the table is calculated, followed by calculating the width of each column. Then every cell is reflowed according to the new column widths.

## Definition of minimum, maximum, desired and percentage width

Definition of the different width types - minimum, maximum, desired and percentage width - in the context of table box, table-cell box and column array:

| minimum width | maximum width | desired width | percentage width | containing block for resolving percentages
--- | --- | --- | --- | --- | ---
table-cell box | widest unbreakable piece of content (widest unbreakable word, widest piece of replaced content, widest block, etc.) | width when ignoring all implicit line-breaks (wrapping) | CSS property 'width' or HTML attribute 'width' specified on the cell | CSS property 'width' or HTML attribute 'width' specified on the cell | table box
column array | largest minimum width among all cells belonging to the column, including border and padding | largest maximum width among all cells belonging to the column, including border and padding | Largest desired width among all cells belonging to the column, including border or padding, or the desired width of the column box, if it is larger. Ignored if percentage width is present | Largest percentage width among all cells belonging to the column, or the percentage width of the column box, if it is larger. Overrides desired width, if present. | table box, excluding border-spacing, table padding and border
table box | Sum of all columns' minimum width, plus table border and padding, plus border-spacing around referenced columns | Defined here | CSS property 'width' or HTML attribute 'width' specified on the table | CSS property 'width' or HTML attribute 'width' specified on the table | table box, excluding border-spacing, table padding and border

- Special rules for cells with colspan > 1 apply
- Resolving column percentages in a table with auto width is described here
- There is also a width type called normal minimum width. This will always be the "true" minimum width. It is always the same as minimum width in normal layout mode, while in other layout modes (ERA) minimum width may be less than normal minimum width. In non-normal layout modes, minimum width is sqeezed aggressively. Replaced content may be shrunk, and words may e.g. be split over several lines, if containing block width is insufficient.
  This will always be true: minimum width <= normal minimum width <= maximum width
- Observe the fact that minimum and maximum widths are never affected by the width of the table or the containing block of the table

How to calculate minimum and maximum widths is described in greater detail in the documentation of the min/max width calculation and propagation algorithm.

## The column array

ColumnInfo

An array of columns is created and updated when laying out cell and column boxes. A table cell with colspan colspan belongs to colspan entries in the column array (or, more often simply called "columns"). A column box with span span defines span entries in the column array. The first table cell in a table-row belongs to the first column (and colspan-1 following columns) (unless it is pushed to a successive column by a cell with rowspan on a preceding row). The next cell in a row belongs to the column (or, with colspan, columns) following the last column occupied by the previous cell. A column entry refers to zero or one column box. It contains width information about (but does not directly refer to) zero or more cells.

For ERA, when TrueTables are enabled, each entry also keeps track of how many non-colspanned cells in each column are suitable (positive) or unsuitable (negative) for TrueTables.

## Layout algorithm details

TableContent::ComputeSize(), TableContent::Layout()

This chapter deals with the entire algorithm used for automatic table layout, step by step.

Very many (but not all) of the other layout box types require only one layout pass. This is however only possible if the width of a box can be calculated without laying it out first. This is not the case for table boxes. Two passes are required.

### Initial layout pass (measure pass)

Before we can calculate the width of the table, we need to know the desired, percentage, minimum and maximum width of each of its columns. Before we can calculate that, we must know the desired, percentage, minimum and maximum width of each cell box. The only way to find this, is by laying out every cell box (without knowing their size).

#### Lay out every column and cell box

TableCellBox::Layout(), TableContent::UpdateColumnWidths(), TableContent::CalculateColumnMinMaxWidths()

For each table-cell box, feed the table's column array with desired, percentage, content minimum and maximum width. For each column box, feed the table's column array with desired and percentage width.

Cell or column box width values (minimum/maximum/desired/percentage) replace values in the column array if a value is higher than what is already stored in the column array. A cell with desired width specified will constrain maximum width to desired width - it may be less, but not more. Note that this rule may cause a column's minimum width to be larger than its maximum width, which reduces the chance of the column receiving excess space later, when distributing available table width.

Column box desired/percentage width is honored only if the column contains at least one non-colspanned cell with auto width. The column box's desired width is propagated to such cells.

Cell and column widths are fed to the layout engine in plain document element order. In fact, order is irrelevant, unless there are cells with colspan > 1. In that case we feed them sorted on their colspan, ascendingly. This way the column minimum and maximum widths become as narrow as possible. If there are two or more cells with the same colspan in the table, feed them in layout stack order - i.e. first row first. This makes us pretty compatible with IE. In Firefox and Konqueror, on the other hand, row order seems to make no difference.

##### TrueTable detection

Content::IsTrueTableCandidate()

In TrueTable mode (typically enabled in SSR and CSSR mode), each table cell with colspan == 1 needs to specify if its content may look like it is content of something that should be regarded a table logically, i.e. not a table that is a table just for the sake of visual page layout. A cell is either suitable for TrueTables (POSITIVE), unsuitable for TrueTables (NEGATIVE), or neutral (NEUTRAL). Numeric text content will increase the likelihood of a cell becoming suitable for TrueTables. Other text and replaced content will decrease it. Cells with colspan != 1 are always neutral. Numeric text content is words that start with a digit, '+', ',', '-', '.', '/', ':', ';' or '%'.

Exact algorithm: Cells and non-replaced blocks keep track of the number of how many lines or child blocks or tables that should contribute positively to TrueTable detection, and how many of them should contribute negatively. Neutral lines or child blocks are not counted. The detection algorithm works recursively.

A positive line is a line whose width comprises two thirds or more of numeric text content (and one third or less of other text content, margins, border, padding, replaced content, inline-blocks and inline-tables). The remaining lines are negative, except for the ones that have no content at all. Such lines are neutral.

A positive block is an in-flow, non-replaced block which has more positive than negative lines, in-flow blocks or tables. The remaining in-flow blocks are negative, except for the ones that consist of only one negative line, and the maximum width of that line is less than 2em. Such blocks are neutral.

A table is positive if it is an in-flow, block level table that was found to be a TrueTable or SmallTable. In-flow, block level tables found NOT to be a TrueTable will disable TrueTable and SmallTable detection for all ancestor tables (so that they all end up being displayed in single columns). Note that NOT being a TrueTable includes being a SmallTable in this case.

Replaced in-flow blocks are negative.

Absolutely positioned and floated content is neutral.

The table cell then follows the same algorithm as in-flow, non-replaced blocks to find out if it is suitable for TrueTables. It propagates the result to its parent table, which will keep track of how many cells in each column are suitable or unsuitable for TrueTables. The final destiny of the table with regards to TrueTable / SmallTable detection will take place when all its cells have been laid out. This is described later.

##### Colspanned cells

Minimum (and maximum) width of a colspanned cell may never be less than 1px more than border-spacing multiplied with one less than the columns that it spans, including any unreferenced columns.

In other words:

> minimum width >= (colspan - 1) * (horizontal border spacing + 1)

Example: Minimum width of a cell that has a colspan of 50 in a table with horizontal border-spacing of 10px must be at least:

> (50-1) * (10px + 1px) = 539px

If the desired / percentage / minimum / maximum width of a colspanned cell exceeds the total already set on the columns that it spans, the extra width must be distributed, so that the colspanned cell fits. Here is what to do, in the following order (note that, as always in automatic table layout, desired width and percentage width are mutually exclusive; percentage wins, desired width is ignored):

width type | distribution algorithm
--- | ---
percentage | Distribute extra percentage (what's more than already set on the columns) across columns that don't yet have any percentage set. The larger maximum width, the larger portion of the percentage will be given to a column. If there is no maximum width, distribute extra percentage evenly on said columns. If all columns already have a percentage set, do nothing.
desired | Adjust maximum width of the columns that don't have a desired width (using extra space). NOTE: Existing desired widths of the columns are not changed - that aligns us with all major browsers better. The final widths might still then become greater after the regular column width distribution algorithm.
normal minimum | Use regular column width distribution algorithm. If total percentage on the spanned columns exceeds 100, scale them down to a total of 100% instead of ignoring excess percentage. Total percentage of all columns in the table is irrelevant.
minimum | Use regular column width distribution algorithm. If total percentage on the spanned columns exceeds 100, scale them down to a total of 100% instead of ignoring excess percentage. Total percentage of all columns in the table is irrelevant.
maximum | Use excess space distribution part of regular column width distribution algorithm.

#### Find total table minimum and maximum widths

TableContent::ComputeMinMaxWidth()

All cell and column boxes have contributed to the table's column array at this point, and based on this information, we can calculate the table's minimum and maximum widths, which will be used to determine the width of the table, as well as being propagated to parents. Table minimum width is the sum of the minimum width of each column plus table border, padding, and the border-spacing around each referenced column. Table maximum width is the sum of the maximum width, or the minimum width if it is larger, of each column plus table border, padding, and the border-spacing around each referenced column.

##### Percentage columns in auto width tables

Percents in columns are relative to the containing block, which is the table. If the table width is auto, the containing block is unknown (auto width on a table doesn't mean use width of containing block, but rather a form of shrink-to-fit). The table width used will then depend on the column percentage and maximum widths. If percentage columns increase the table's maximum width, it is important that this increase is not propagated to parents. The maximum width CMW of a column with a percentage of CP requires that CMW pixels be at most CP percent of the maximum width TMW of the table:

> CMW <= TMW * CP / 100

or:

> TMW >= CMW * 100 / CP

Example: A 25% wide column with a maximum width of 50px requires the maximum width of the table to be greater than 50px * 100 / 25 = 200px.

Details: Iterate over all columns and add the total maximum width of all non-percent based columns NPW together. This will serve as a base for a table maximum width that takes percentages into account.
The highest allowed total percentage TP for all columns is 100. Cope with excess percentage by truncating the percentage of the column that causes the total to exceed 100, so that the total becomes 100 nevertheless. Ignore percentage on remaining columns with percentage set, but find the highest maximum width value among them IMW. It may have to serve as fallback base for new table maximum width.

Done with column iteration. Next step: If NPW is non-zero, pretend that this is the width of the "unclaimed percentage" in the table (100-TP percent, in other words). To be able to satisfy the percentage on the columns with no percentage set, table maximum width must be at least:

> NPW * 100 / (100 - TP)

If TP is 100 here, table maximum width becomes infinity (since no table width can satisfy percentage widths then). If NPW is 0, but IMW isn't, IMW is used as a fallback: Pretend that IMW represents 1% of the table maximum width; in other words, make sure that table maximum width is IMW * 100 or more. Is this an important feature in IE worth copying, or is it just a bug? We now have a maximum width that is large enough to satisfy percentage widths, and at the same time keep cell content of non-percentage columns from wrapping. What remains is to make sure that the maximum width is large enough to keep cell content of each percentage column from wrapping as well. For each percent-based column, make sure that table maximum width is at least:

> CMW * 100 / CP

where CMW is the column's maximum width and CP is the column's percentage value. We assume that percentage total is 100 in this step, instead of using the actual value.

Firefox behaves differently here: it uses the smallest, not the largest, percentage value set on a cell in the column array. This may result in a larger a table maximum width. It seems like a logical thing to do, but currently, neither Opera nor IE do this.

##### Tables with no columns

A table with no columns (i.e. no cell or column boxes) uses the largest minimum and maximum widths of any captions in the table as its minimum and maximum width.

#### Request reflow

TableContent::UpdateScreen()

Minimum and maximum width of the table and all its columns have been determined. Now we need another reflow to lay out table cells with their correct width. They can get their correct width in the second pass because the column widths can be calculated. The column widths can be calculated because the minimum and maximum widths of the table have been found.

#### Detect TrueTable / SmallTable (ERA)

TableContent::FinishLayout()

This section only applies if TrueTables are enabled in the current rendering mode, which is typically the case in CSSR.

In CSSR mode, most tables will be displayed in a single column, since available width is very limited, so that columns would become uselessly narrow otherwise. However, in some cases we want to display a table as a regular table - when the table is found to be a "real table" (as opposed to a table used to get some desired layout) (TrueTable), or when the table's maximum width is small enough to fit within the containing block (SmallTable). There is very little difference between TrueTables and SmallTables, apart from the way they are detected.

Each cell in the table has already been examined (enum TRUE_TABLE_CANDIDATE), and have been found to be either suitable for TrueTables (POSITIVE), unsuitable for TrueTables (NEGATIVE), or neutral (NEUTRAL).

Now each column will be examined. If the column has more suitable than unsuitable cells for TrueTable, the column is defined as suitable for TrueTable. If the column has fewer suitable than unsuitable cells for TrueTable, the column is defined as unsuitable for TrueTable. If the column has the same number of suitable as unsuitable cells for TrueTable, the column is neutral.

If there are any columns suitable for TrueTable, and that number is at least twice as many as the number of unsuitable columns for TrueTable, then the table becomes a TrueTable.

If the table did not become a TrueTable, but its maximum width does not exceed available width for the table, the table is a SmallTable.

If the table is neither a TrueTable nor a SmallTable (and TrueTables are enabled in the current rendering mode), the table will be displayed in a single column.

### Final layout pass

In the final layout pass, minimum and maximum widths of the table and each of its columns are known, and layout of table boxes with their final and correct width can be done. When a table box has already been laid out, but needs a reflow because its containing block width has changed, it will skip directly to this second layout pass, since minimum and maximum widths are not affected by containing block width changes.

#### Calculate table width

TableContent::CalculateTableWidth()

A table will be at least as wide as its minimum width. Desired or percentage table width is honored if it exceeds the minimum width of the table. If no desired width is specified, use the smaller of table maximum width and table containing block width as table width.

In other words - if desired or percentage width is specified:

> table width = MAX(desired width, minimum width)

If no desired or percentage width is specified:

> table width = MIN(MAX(minimum width, containing block width), maximum width)

#### Calculate column widths

TableContent::CalculateColumnWidths()

Distribute available width - table width without padding, border and border-spacing across the columns.

##### Single column mode

If the table is in single column mode (ERA), all column widths will simply be set to the available table width (they are going to be laid out on separate lines anyway). Single column mode is used when explicitly enabled for the rendering mode, or if TrueTables are enabled (typically SSR and CSSR) and this table was found not to be a TrueTable or SmallTable.

##### Flexible columns

If flexible columns are enabled for the rendering mode (typically all ERA modes but MSR), it will apply as long as the table was found not to be a SmallTable (if it is a SmallTable, all column maximum widths can be satisfied anyway). If it applies, a table row is allowed to wrap if the total minimum width of the columns exceeds available width. If this happens, satisfy minimum width of each column (starting at the first column in the table), as long as the total width doesn't exceed available width. If there is unsatisfied normal minimum width for the columns examined so far, distribute as much of it as possible (exactly how will be described in a later version of this document). Then wrap to a new "row" and repeat what was just done for the previous "row", for as many columns as there are room for. Repeat this as long as there are columns left to examine.

If the rows don't wrap, use the following width distribution algorithm, just as in normal layout mode:

##### Regular width distribution

This algorithm is described in detail in the regular column width distribution algorithm chapter. In short, step by step: start by satisfying minimum widths of each column. If there is more space left, satisfy percentage column widths. If there is more space left, satisfy desired width. If there is enough space left to satisfy maximum widths of each column with no desired or percentage width, do that. If there is more space left after this, distribute it all by stretching each column with no desired or percentage width relative to their maximum width. If there are no such columns, stretch columns with desired width with non-zero minimum width. If there are no such columns, stretch columns with percentage width with non-zero minimum width. If there are no such columns, all columns have zero minimum width. Stretch all columns relative to their desired width. If no columns have a desired width, stretch all columns evenly.

#### Lay out every column and cell box

TableCellBox::Layout(), TableContent::UpdateColumnWidths()

Here we go again... However, this time we know the actual size of the columns, so calculating cell widths is possible. The border-box of a cell is the same as the total width of the column(s) that it spans, plus any border-spacing between each column.

#### Check if reflow is needed

TableContent::UpdateScreen()

If any minimum or maximum widths changed during this layout pass, we need another reflow, since such changes may affect column widths.

## Definition of 'referenced column'

A column that is the first column for at least one cell box is defined as referenced. Colspan > 1 and excess column boxes may cause unreferenced columns - columns in which no cell starts.

Consider the following example:

    <table cellpadding="0" cellspacing="10" border="1">
     <tr>
      <td>this cell should use all available table space</td>
     </tr>
     <tr>
      <td colspan="5">even if this cell spans 4 more columns</td>
     </tr>
    </table>

This table has 5 columns. Only 1 of them is referenced (by 2 cells). The remaining 4 are unreferenced.

Another example, but defining excess column boxes instead of using colspan:

    <table cellpadding="0" cellspacing="10" border="1">
     <col></col>
     <col></col>
     <col></col>
     <col></col>
     <col></col>
     <tr>
      <td>these two cells combined</td>
      <td>should use all available table space</td>
     </tr>
    </table>

There are 5 column boxes, but only the 2 first ones are referenced.

Unreferenced columns don't take up any space. Border-spacing between them is distributed among referenced columns.

The concept of referencedness is not defined in the HTML spec (which simply says that all columns contribute to table width, but it does mention that it is an error if the number of referenced columns do not equal the number of columns defined by COL/COLGROUP, if any). However, both MSIE and Firefox have this concept. Konqueror/Safari has to, albeit somewhat "buggy".

## Column width distribution algorithm

ColumnCalculation, TableContent::DistributeSpace()

Here is the complete step-by-step description of the width distribution algorithm to use when distributing width across a certain set of columns. It is used when setting all column widths based on final table width. It is also used expanding column minimum, normal minimum or maximum widths due to colspan.

Desired width and percentage width are mutually exclusive in this algorithm; if both are set on a column, desired width is ignored.

Algorithm input: Column selection; start column and number of columns. Minimum total number of pixels to occupy by the selected columns (also called available space or available width). Minimum width, maximum width, desired width, percentage width of each selected column

Algorithm output: New width of each selected column. The sum of the selected columns' widths must be equal to available width.

### Check percentage

Sanity check and correction of percentage widths:

For automatic table layout: Make sure that the percentage width of all columns combined doesn't exceed 100, and adjust values if necessary: Start with the first column and accumulate percentage values for each column. If the number exceeds 100 at a column, truncate that column's percentage value so that the total percentage becomes 100. Remove percentage values from all remaining columns.

For fixed table layout: If the percentage width of all columns exceeds 100, reduce the percentage of each column proportionally, so that the sum will become exactly 100.

This is only done when calculating all columns of a table, not when expanding column min/max widths due to colspan. In that case, percentages are scaled down to sum 100% (only the columns selected are considered).

### Set start width

When setting final column widths based on table widths, or when expanding columns' minimum widths due to colspan, start by setting each column width to its minimum width. When expanding normal minimum width due to colspan, start by setting each column to its normal minimum width instead. When expanding maximum width due to colspan, start by setting each column to its maximum width.

The widths may only be increased after this step; they will never shrink.

When expanding maximum width due to colspan, skip to the step where excess space is distributed now. This is necessary because what many of the following steps attempt to do has already been achieved.

### [ERA] Attempt to satisfy normal minimum widths

This part only relevant when when column start width is minimum width.

If there is space left to distribute at this point, and layout mode is non-normal (ERA, AMSR, CSSR, etc.), attempt to increase column widths from minimum width to "normal minimum width". Columns should really only be narrower than normal minimum width if absolutely inevitable, so regaining this space is first priority. If there is enough space to satisfy normal minimum width of each column completely, just do that. Otherwise, distribute extra space by giving more to columns with larger difference between minimum width and normal minimum width.

### Attempt to satisfy percentage widths

If there is still space left to distribute, widen each percentage-based column to satisfy their percentage setting. Percentages are relative to available space, unless total minimum width of non-percentage columns constitute a larger portion of the table than the unused percentage:

> non-percentage columns' minimum widths > (100 - total percentage) * available width

If this is true, column percentages are scaled down so that new total percentage multiplied with space left equals the difference between available space and non-percentage columns' minimum widths. Also, if there are only percentage columns in the table, percentage values are scaled up so that summed they become 100%.

Columns whose percentage resolves to a width less than their minimum width count as non-percentage columns in this step. Otherwise, more space than available might be distributed.

### Attempt to satisfy desired widths

If there is still space left, attempt to satisfy the desired width of each column. If there is enough space to satisfy them all completely, just do that. Otherwise, increase the width of each unsatisfied column to the difference between current width and desired width scaled down so that complete increase equals amount of space left.

### Attempt to satisfy maximum widths

If there is still space left, attempt to satisfy the maximum width of each column width no desired nor percentage width. If this would use more space than available, make no changes and skip to the next step in this algorithm.

### Excess space - distribute any remaining space

If there is still space left, find one set of columns that have certain characteristics (presence of desired width, minimum width, percentage) in common, and assign ALL remaining space to them. There are four types of sets, and here is the list, in order of preference, and how remaining space is distributed for them:

Condition (column set characteristics) | Action (distribution method)
--- | ---
columns with auto (no percentage AND no desired) width AND non-zero minimum width Note: In quirks mode, if a column's maximum width exceeds desired width, desired width is ignored (and the column behaves as if it had auto width). IE always ignores desired width exceeded by maximum width, while Opera, Konqueror and Firefox only do that in quirks mode | widen each column relative to its unsatisfied maximum width (difference between width so far and maximum width)
columns with desired width (and no percentage) | widen each column by the larger of each column's minimum width and desired width relative to the sum of total of the larger of desired width and minimum width of each column
columns with percentage | widen each column relative to their percentage
all columns | widen each column relative to their maximum width, or, if none has maximum width, distribute remaining space evenly