Multi-column layout

Copyright © 1995-2011 Opera Software AS. All rights reserved. This file is part of the Opera web browser. It may not be distributed under any circumstances.

About this document

This is a description of Opera's implementation of CSS3 multi-column layout.

Introduction

CSS defines multi-column here: http://www.w3.org/TR/css3-multicol/
Opera has a complete implementation of this spec, with only one known difference, at the time of writing this document: The CSS working group has decided that the 'column-span' property take the values 'none' and 'all', but this change still hasn't found its way to the candidate recommendation, which still says that the possible values are '1' and 'all'.

Design

Content inside a multi-column container is laid out pretty much like any other container. It does not care much about the "multi-columnness", apart from setting the width of the containing block that it establishes to the width of a column. It lays content out as if columns didn't exist, which results in one long column/container when layout is finished. We refer to the content height of this container as "virtual height", and the Y position of each child in the layout stack is a "virtual Y". Right before finishing layout of the outermost multi-column container, we enter a so-called columnization phase, where content is distributed into columns (without changing the actual layout structure inside of the container).

Note that layout of a multi-column container only requires one reflow pass, unless there are other factors (such as shrink-to-fit) that cause more than one pass. This is thanks to the columnizer, which doesn't modify the actual layout, but instead creates a "translation pane" for each column, which causes the multi-column effect. They are split into columns and the column heights are balanced (if required) in one go.

During traversal we traverse a multi-column container (and its children) once per column. For a given column, we skip irrelevant content before and after it.

Problems

The approach with single-pass layout has turned out to work quite fine, with one exception: nested multi-column containers. In that case we may have to guess the height of an inner multi-column container at the time of finishing its layout; there's no way to know the actual height until the outer multi-column container has decided if it needs to split the inner multi-column container into multiple outer columns (which may affect the total height of the inner multi-column container). Content following the inner multi-column container will depend on the guessed height, and if it later (when being columnized via the outermost multi-column container's columnizer) turns out that we guessed wrong, we have to try our best to compensate for that on successive content, by moving such content downwards (or upwards) in the layout structure. This is evil. Adding another reflow pass could have been a better idea. Making sure that we don't get circular dependencies and countless reflow iterations would be a challenge then, though.

Implementation

Class overview

In the layout box/content structure multi-column support is implemented with a class called MultiColumnContainer. It lays out child content pretty much in the same way as a regular Container. It does not care much about the "multi-columnness", apart from setting the width of the containing block that it establishes to the width of a column. It lays content out as if columns didn't exist, which results in one long column when layout is finished. Upon finishing layout, we enter a so-called columnization phase, where content is distributed into columns (without actually changing the layout structure). The multi-column effect is achieved by creating one Column object per column, and each Column object has an X and Y translation, which makes the object function as a "translation pane". That, together with some clipping, causes the multi-column effect.

The only class exposed the rest of the layout engine is MultiColumnContainer. There are other classes in the multi-column implementation, but they are only used by MultiColumnContainer.

One such class has already been mentioned: Column, of which we instantiate one per column. It serves as a "translation pane" for the column (translate from the container's original coordinates to the column's coordinate system). It also knows which elements the column starts with and ends with. A Column object is a chain in a linked list of Column objects. Together they form a row. The class ColumnRow holds the list of Column objects. A ColumnRow is a chain in a linked list of ColumnRow objects. The linked list has its dedicated class: ColumnRowStack. MultiColumnContainer holds this list. The ColumnRow and Column objects are built when the outermost MultiColumnContainer is being columnized, right before finishing layout of this element. The ColumnRow and Column objects are used during traversal, to position and clip each column traversed.

There are two state classes, used to carry out two different operations. One is used during columnization to build the ColumnRow and Column objects. It is called Columnizer. The other state class only reads from Column and ColumnRow, and it is used to find out which Column(s) a given element belongs to. It is called ColumnFinder. Traversing is expensive, so this class saves us some time, if all we need to know is the actual whereabouts of some box inside of a multicol container.

The class ColumnBoundaryElement is used to keep track of where a Column starts and where it stops. A start or stop element may be a Line, BlockBox, LayoutBreak, TableRowBox, TableCaptionBox or TableRow. This information is used during traversal, to know where to begin traversing and when to end. It is also used by ColumnFinder.

There are two classes of which instances are created during layout and consumed (and removed) during columnization. They are used to keep track of explicit column/row/page breaks, and spanned elements ('column-span: all'). They are called MultiColBreakpoint and SpannedElm. A spanned element is considered an explicit break point, since it will terminate any previous row of columns, and force the columnizer to balance the column heights.

Paged media

Multi-column layout and paged media layout have a lot in common, but their implementations are still separate. When doing paged media layout and multi-column layout at the same time (e.g. when printing a web page that has a multi-column container), however, the regular paged media layout code in Opera is not used. Then the columnizer takes care of pagination.

In the future, we should consider consolidating those two implementations. A page in paged media is little different from a column in a multi-column container, and could therefore conceivably be represented by a Column object (which then might need a better name, but that's another story).

Improvements to consider