# Layout module

Copyright (C) 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.

## Introduction

See the overview section in the API documentation below.

Module wiki page.

## API documentation

For detailed information on how to use the layout module in Opera and the module's public API, please refer to the API documentation.

## Memory management

The memory aspects of the layout module are described here.

## Detailed documentation

### Layout basics

#### Box & content model

The layout tree is primarily constructed of two element types, Box and Content elements. Box elements serve to position an element on the page, and usually has a content element associated with it. Content elements in turn handle the contents of the boxes, such as images, select boxes, etc.

#### Cascade

This is an implementation of the CSS cascade. It's a simple linked list that ends in the CSS properties of the current element, with the CSS properties of its parents preceding it.

#### Reflow

Reflow does the actual job of constructing the layout tree from the DOM tree. Reflow is performed every time an element in the DOM tree is marked dirty. As soon as an element is marked dirty, the layout tree cannot be accessed before the reflow has completed.

It may take several reflow iterations before the DOM tree can be marked clean, but under most conditions, one iteration should be sufficient.

#### Traversal

In order to access the layout tree, traversal objects are used.

TraversalObject

Block traverse

Line traverse

Z-index traverse

### Layout details

#### Floats

#### Broken HTML

This code

    <P><FONT>one</P>
    <P>two

Generates this tree

      P(1)
       |
       v
      FONT
      |   \
      v    v
    "one" P(2)
           |
           v
         "two"

p(1)->last_descendant is now set to "one". "one" is thus the last element to inherit CSS properties from p(1). The is_last_descendant flag is also set on "one". When we have reached "one", we need to recalculate the cascade.

##### Cascading props

Some complications to the broken HTML rendering: (never mind that </P> is not mandatory and other technical details.) <body><div><p>text</div>text2

    BODY
     |
     v
     P border:10px solid red;
     |
     v
    DIV border:inherit;
     |     \
     v      v
    text    text2

text2 will inherit from LayoutProperties::cascading_props, but the actual props of DIV is not changed when recalculating the cascade. Otherwise we could end up with an incomplete/weird border (or in worst case a box that changes from e.g. block to inline).

#### Table layout

##### Fixed table layout

Fixed layout is described in the CSS spec. Opera implementation detail: If width is auto, Opera will fall back to automatic table layout.

##### Automatic table layout

Automatic table layout is not well defined in the CSS spec. The algorithm used in Opera is described here.

#### Shrink to fit

CSS 2.1 calculating widths and margins

A ShrinkToFitContainer is created when an element is not replaced, has width:auto, either "left" or "right" is auto and it is absolutely/fixed positioned, has display:inline-block, floated, or if the element type is <BUTTON>. To calculate a suitable width for a ShrinkToFitContainer, we employ the min/max width calculation and propagation algorithm. This algorithm is also used to calculate the scrolling content width for horizontal <MARQUEE>s. It is also used to calculate suitable column and table widths in automatic table layout.

Shrink-to-fit basically means that the container will not be wider than the unbroken content of the container, and not wider than the available width, but it must never be narrower than the minimum width (longest word).

#### Margin collapsing

First of all, see CSS Box Dimensions for explanation what margin is.

We say that two margins are adjoining when there is no non-empty content, padding or border areas or clearance separate them. It is possible that one element's own top and bottom margins are adjoining.
Collapsing margins means that adjoining margins of two or more boxes (which may be next to one another or nested) combine to form a single margin.

##### Margin collapsing algorithm

Margins are calculated during reflow. There are however cases where layout engine reflows document tree only partially by omitting some branches. In this case we trigger margin calculation "manually" on omitted content as such margin may still affect ancestor being reflowed. Many of "margin collapsing bugs" are caused by differences in margin calculation between "full reflow" and "partial reflow" cases.

Opera margin calculation algorithm is mostly based on container's `reflow_state->margin_state`. This variable defines an offset that will be added to next laid out child top position. `reflow_state->margin_state` can be changed by either child's top or bottom margin. There are also two helpers: `packed.stop_top_margin_collapsing` and `reflow_state->stop_bottom_margin_collapsing` that control whether calculated `reflow_state->margin_state` should be propagated to parent.

Here we have some examples of adjoining and collapsing margins. outer div will be treated as an element where we start layout. It has borders so we don't have to take care of margin collapsing/propagation to it's parents. For simplicity we will assume that we have only positive (non-percentage) margins.

A) |
    <div id="outer" style="border: 1px solid black">
     <div id="parent" style="margin-top: n px">
      <div id="child" style="margin-top: m px; border: 1px;"></div>
     </div>
    </div>
| n pixel big parent's's top margin causes outer's `margin_state` to grow pushing parent down. child's m margin collapses (through parent) with outer's `margin_state`. If m > n parent is again pushed down by (m - n). Finally, parent's top margin will be MAX(m,n)
B) |
    <div id="outer" style="border: 1px solid black">
     <div id="parent" style="margin-top: n px; border: 1px; ">
      <div id="child_1" style="margin-top: m px; margin-bottom: k px; border: 1px;"></div>
      <div id="child_2" style="margin-top: l px; border: 1px;"></div>
     </div>
    </div>
| n pixel big parent's's top margin causes outer's `margin_state` to grow pushing parent down. m pixel big child_1's top margin does not collapse with parent's top margin therefore it causes parent's `margin_state` to grow pushing child_1 down. When finishing child_1's layout it's bottom margin is propagated. Since child_1 has border, it's own top & bottom margins are not adjoining. This causes child_1's bottom margin to become new, k pixel big, parent's `margin_state`. When child_2 is laid out, first it's being positioned according to current parent's `margin_state`. Later it's top margin l collapses with parent's `margin_state` and forms new `margin_state` = MAX(k,l). child_2 may be pushed down if l > k.
C) |
    <div id="outer" style="border: 1px solid black">
     <div id="parent" style="margin-top: n px; ">
      <div id="child_1" style="margin-top: m px; margin-bottom: k px; "></div>
      <div id="child_2" style="margin-bottom: l px; "></div>
      <div id="child_3" style="border: 1px; "></div>
     </div>
    </div>
| n pixel big parent's's top margin causes outer's `margin_state` to grow pushing parent down. child_1's m top margin collapses (through parent) with outer's `margin_state`. If m > n parent is again pushed down by (m - n). Later, when finishing child_1's layout it's bottom margin is propagated. Because child_1's own margins are adjoining, bottom margin k collapses (through parent) with current outer's `margin_state`. If k is greater than current `margin_state` it collapses with, parent will be accordingly pushed down. Similarly child_2's bottom margin l collapses (through all precedent siblings and parent) with outer's `margin_state` and may cause parent to be pushed down again.
D) |
    <div id="outer" style="border: 1px solid black">
     <div id="parent_1" style="margin-top: n px; margin-bottom: m px; padding-top: 1px; ">
      <div id="child_1" style="margin-bottom: k px; "></div>
     </div>
     <div id="parent_2" style="margin-top: l px; border: 1px solid black; ">
      <div id="child_2"></div>
     </div>
    </div>
| n pixel big parent_1's top margin causes outer's `margin_state` to grow pushing parent down. When child_1's layout is being finished, it's bottom margin k is being propagated. Because parent_1 has top padding set child_1's margin sets parent_1's `margin_state`. When parent_1's layout is being finished it's bottom margin m collapses with current parent_1's `margin_state` and such value is assigned (not collapsed with!) to outer's `margin_state` (this automatically becomes top margin of parent_2 when it comes to it's layout). When parent_2 is being laid out it originally uses current outer's `margin_state` to determine it's vertical position. Later it's top margin l collapses with outer's `margin_state` (this may push parent_2 down if l was bigger then pre-calculated outer's `margin_state`).

Notice that child_1's bottom margin does not change parent_1's height. It kind of flows outside parent_1 modifying parent_1's bottom margin. If only parent_1 had a bottom border or padding, child_1's bottom margin could not be propagated and parent_1's height would be increased accordingly to current parent_1's `margin_state`.

This is also a case when partial layout may trigger "on demand" margin calculation. If we trigger child_2's reflow, layout will be limited to branch holding element that actually needs a layout. This means that parent_1's layout will be started but it's content will not be reflowed (as nothing needs reflow there). This means that child_1's bottom margin k will not get propagated. Therefore we trigger a procedure that calculates bottom margin that equals to parent_1's `margin_state` as it would be after full layout pass over all of it's children. It is then propagated to outer modifying it's `margin_state` Of course, this would not happen when parent_1 had a bottom border or padding. Only parent_1's own bottom margin would be propagated then.

"On demand" bottom margin calculation procedure collapses all adjoining margins it finds starting with last element on a container's layout stack and moving up through it.

There are some exception from above margin collapsing rules (according to CSS2 Margin Collapsing spec):

1. Vertical margins between a floated box and any other box do not collapse (not even between a float and its in-flow children).
2. Vertical margins of elements that establish new block formatting contexts (such as floats and elements with 'overflow' other than 'visible') do not collapse with their in-flow children.
3. Margins of absolutely positioned boxes do not collapse (not even with their in-flow children).
4. Margins of inline-block elements do not collapse (not even with their in-flow children).
5. An element that has had clearance applied to it never collapses its top margin with its parent block's bottom margin.

Some examples to above exceptions:

1) |
    <div id="outer">
      <div id="marg" style="margin-bottom: m px; "></div>
      <div id="floating" style="float:left; height: k px; margin-top: n px"></div>
    </div>
| Margins: n and m should never collapse.
2) |
    <div id="outer">
     <div id="bfc" style="overflow:hidden; margin-bottom: k px">
      <div id="bfc_child" style="height: l px; margin-bottom: m px;"></div>
     </div>
     <div id="bfc_sibling" style="margin-top: n px"></div>
    </div>
| If bfc wasn't establishing new block formatting context it's height would be equal to l and it's bottom margin would be equal to MAX(k, m) (which means that margins k and m were collapsed). However since we set overflow property to hidden, bfc establishes new block formatting context, and therefore margins k and m do not collapse witch each other. This causes bfc height to grow to l + m and margin between bfc and bfc_sibling be equal MAX(k, n) (those margins collapse).
3) |
    <div id="outer" style="position:relative">
     <div id="inner">
      <div id="abs" style="position:absolute; margin-bottom: k px">
       <div id="abs_child" style="margin-bottom: m px;"></div>
      </div>
      <div id="abs_sibling" style="margin-top: n px"></div>
     </div>
    </div>
| This is pretty simple case. Absolutely positioned box is handled separately therefore there is no margin collapsing. However, due to our traversal engine some extra actions need to be taken in order to ensure that abs element is positioned correctly. Basically when traversing layout tree, each time we enter child element translation gets updated by adding element's (x,y) position (which is relative to parent's border edge). This affects absolutely positioned boxes as well so we need to be careful when collapsing margins after absolutely positioned box was laid out.

abs is absolutely positioned therefore there is no margin collapsing. When laying out abs there is no margin between outer (which is abs's containing block) and inner (*) and therefore abs's absolute top offset is 0. Later, abs_sibling propagates it's top margin but since inner element does not stop top margin propagation, abs_sibling's top margin gets propagated up to outer and causes inner to be pushed down by n px. Now, unlike to (*) case there is a margin between outer and inner. Since abs screen position needs to remain constant we need to shift it up by n pixels basically compensating for margin that will be added to translation when we will be traversing such tree. There are however some corner cases when partial reflow causes abs top offset to be decreased forever. Those issues are being tracked by CORE-19567 and CORE-17858.

4) |
    <div id="outer">
     <div id="inl" style="display:inline-block; margin-bottom: k px">
      <div id="inl_child" style="height: l px; margin-bottom: m px;"></div>
     </div>
     <div id="inl_sibling" style="margin-top: n px"></div>
    </div>
| If inl wasn't inline block it's height would be equal to l and it's bottom margin would be equal to MAX(k, m) (which means that margins k and m were collapsed). However since we set it as inline block, margins k and m do not collapse witch each other. This causes inl's height to grow to l + m and margin between inl and inl_sibling be equal k + n (those margins do not collapse too).
5) |
    <div id="outer">
     <div id="inner" style="margin-bottom: k px">
      <div id="float" style="float:left; height: l px"></div>
      <div id="cleared" style="clear: both; margin-top: m px;"></div>
     </div>
    </div>
| This is pretty simple case. It may sound weird as collapsing child's top margin with parent's bottom margin seems impossible. However (as shown in A-D cases) we do not differentiate between top & bottom margin. Parent's `margin_state` simply keeps current top margin for next element to be laid out (and this may be set by a top margin of empty child element as well as may be result of some margin collapsing). When parent's layout is finished and `margin_state` in non-zero it may be collapsed with parent's own bottom margin resulting in child's top margin being collapsed with parent's bottom margin.

In this example cleared element set's inner's `margin_state` to m px. (if inner have had bottom margin it would have been collapsed with it's top margin). When it comes to closing inner's layout we must be aware that current `margin_state` was set by child with clearance and therefore this margin should not be collapsed with inner's own bottom margin k. Finally, inner's height will be l + m and it will have bottom margin of m px. This issue is being tracked by CORE-12813

#### BiDi

Unicode BiDi specification

Bidi operates both in the layout pass and in the line traverse.

In the layout pass, levels for each segment are calculated according to the rules in the bidi specification. The level for the segment describes how many times each segment should be turned around. For example a segment of level 2 should be turned around twice, along with all its higher level containing segments.

Level calculation is done on a per paragraph level.

Reordering of segments is done on a per-line basis (all according to the bidi spec). The reordering is done in the line traverse pass for each entered Line. The segments are painted in logical order, but with offsets on the line calculated from the reordering.

#### ERA

ERA specification

#### Text wrap

Text wrap is a rendering mode / feature where regular lines may not be wider than the browser window. Text using large fonts is exempted. Line breaking caused by "Text wrap" will only happen at places where the current line breaking properties allow it (meaning that text with white-space:nowrap will not be wrapped because of this feature. This feature reduces the need for horizontal scrolling while reading text paragraphs in a constrained screen width environment.

Further specification of text wrap

#### FlexRoot

FlexRoot is documented here.

#### Page breaking

CSS 2.1 page breaking specification

CSS 3 paged media module (20040225 draft)

When page breaking is on, after closing a vertical layout (Line, block...) we record the widows and orphans state of the current vertical layout. We will also to find out if this vertical layout has overflowed the current page. If it has overflowed the page we will attempt to find a page break.

During a page breaking reflow, when closing a VerticalLayout we will also update the reflow_state->reflow_position. If the closed VerticalLayout has a page break after, we will move the current reflow_position to the start of the next page. This will ensure that the next element is laid out on the next page. (Container::SkipPageBreaks)

We will now iterate from the last (current) element in the Container:s vertical_layout stack upwards to find the first element whose top position is on the previous page.

If the found element is a block (with container/table/... content) we will first enter the block and attempt the page break inside that block (restart from above). If that fails we will insert a PendingBreakBreak before this element.

If the found element is a Line and its bottom is on the next page, and the widows/orphans constraint is satisfied we will insert a pending page break element before this element.

If page breaking in this container fails, we will go to the parent element and try to insert the page break in this element. If that also fails we will loosen the constraints and retry page breaking.

After inserting the pending page break, we turn page breaking off for the rest of the reflow (for optimization). But we now need to restart page breaking from the inserted page break. We do this by setting the page break element in LayoutWorkplace. Next time the layout tree is clean, we will initiate a PAGEBREAK_FIND reflow.

The PAGEBREAK_FIND reflow will reflow up to the container containing the PendingPageBreak and convert the PendingPageBreak into an ImplicitPageBreak. After this is done we will continue with page breaking from this place.

If two (or more) elements that should both be broken lie beside each other (floats, table cells, abs pos boxes), page breaking will be rewound to restart page breaking of the other box in BlockBox::FinishLayout.

#### Linebreaking

Unicode linebreaking specification

#### Multi-column

Opera's implementation of the CSS3 multi-column spec.

#### Absolute positioning

#### First-line

Specification for the first-line pseudo-element can be found here.

##### Relevant variables

`ContainerReflowState::is_css_first_line`
  TRUE If this element has a ::first-line pseudo-element and the currently reflowing line is the first line. See also `Container::IsCssFirstLine()`.
`Line::packed2.is_first_line`
  Set if this is the first line in a container and affected by a ::first-line rule.
`WordInfo::packed2.first_line_width`
  Set if the word width is calculated with ::first-line in regard.
`Text_Box::packed.first_line_word_spacing`
  The width of space for text painted with ::first-line properties.
`HTML_Element::packed2.has_first_line`
  Set if this element is affected by a ::first-line rule.
`LayoutProperties::use_first_line_props`
  This variable is used to track if we are currently in a branch where ::first-line properties are applied. At the time of writing this is only used for a dubious workaround when reflowing children of a ::first-line element with the content: property set. I think the correct solutions would be to make sure that cascading_props for the parent (the first-line version of the element) also gets content_cp set when loading the props.
`g_anonymous_first_line_elm`
  A dummy element used to load CSS properties for the first line. This element is only present in the tree when the properties are loaded and computed and removed immediately after.

##### Cascade

Adding first line properties to the cascade is done by calling `LayoutProperties::AddFirstLineProperties` on the current cascade element. This will create the alternative props for the first line and copy them over to `LayoutProperties::cascading_properties`. Correspondingly `LayoutProperties::RemoveFirstLineProperties` is called when handling of the first line is done.

##### Layout/Reflow

For a container with ::first-line we need to lay out contents of the same container with two different sets of properties.

When we lay out a container, and we notice that the element that represents the container has a ::first-line rule, we start by adding the ::first-line properties. (We are obviously starting with reflowing the first line in the container).

We then lay out children of the container. But, as soon as we notice that one of the children overflows a line for example through `Container::CommitLineContent`, `BlockBox::Layout`, etc, we return the layout status `LAYOUT_END_FIRST_LINE`. This is propagated to the container until it reaches `Container::LayoutWithFirstLine`.

We re-use the `ContainerReflowState::break_before_content` variable to propagate information about where the container should restart laying out. Before propagating the `LAYOUT_END_FIRST_LINE` signal we need to make sure that `ContainterReflowState::break_before_content` is set to the start element of the next line (or other `VerticalLayout`). If the line was closed by a block box or a <br> element, we simply set `break_before_content` to that element. If the line was closed by text or other inline content, we return from `Container::CommitLineContent` before resetting `break_before_content`. It will then hold the start element of the next line.

When we receive the `LAYOUT_END_FIRST_LINE` signal in `Container::LayoutWithFirstLine`, we restart laying out children of the container with `ContainerReflowState::break_before_content` as the first_child to lay out and the position on the virtual line we were laying out before the `LAYOUT_END_FIRST_LINE` signal as the first virtual position to lay out. This is to make sure that we don't lay out elements or parts of elements that were already laid out on the first line.

It is also possible that a call to `::FinishLayout` will return a `LAYOUT_END_FIRST_LINE` status. This is handled in a similar way as in `Container::LayoutWithFirstLine`. When a `LAYOUT_END_FIRST_LINE` status is received in a child of a ::first-line container, `Container::EndFirstLine` is called. This function takes care of restarting layout of the container's children, much in the same way as `Container::LayoutWithFirstLine`.

##### Traverse

::first-line handling during traversal is done in `Container::Traverse`, and is in this stage a rather simple operation since we have already divided content into lines.

For the first line in a container that is a ::first-line container, `LayoutProperties::AddFirstLineProperties` is called before entering the first line. After traversal of the first line is done we call `LayoutProperties::RemoveFirstLineProperties`.

In addition to that, a workaround is required for the cases when the ::first-line rule sets properties on the container that are usually handled in `::EnterVerticalBox`. An example of that is background-color, which is handled in `PaintObject::EnterLine`.

#### Optimizations

Important optimizations that needs to be taken in to account and should not be ruined.

#### Selection

Currently there are two representations of selection points in Core: `SelectionBoundaryPoint` (defined in logdoc) and a representation used internally by layout (which is `LayoutSelectionPoint` as well as various `element` + `offset` value pairs used internally).

LayoutSelectionPoint
  Represents a selection point in the document as an `element` + `offset` pair. If the `element` is a text node, `offset` is a character offset within the text. Otherwise `offset` is either `0` (selection point before the element) or `1` (selection point after the element).
LayoutSelectionPointExtended
  Represents a selection point in the document. In addition to the document position it also provides information about the word the selection is on and offset into that word. Internally it also performs translation between the `LayoutSelectionPoint` and `SelectionBoundaryPoint` representations.
TextSelection (defined in logdoc)
  `TextSelection` holds information about the current selection. It has two `SelectionBoundaryPoint`s as members: a start and an end point.
TextSelectionObject
  The `TextSelectionObject` is a `TraversalObject` responsible of translating from a mouse coordinate to `SelectionBoundaryPoint` (see `GetNearestBoundaryPoint()`).
SelectionUpdateObject
  The `SelectionUpdateObject` is a `TraversalObject` responsible for sending the correct Update rects to visual device to keep selection updated properly. It is also now responsible of updating documentedit as well as DOM with information regarding the current selection. The `SelectionUpdateObject` is also responsible for setting the `is_in_selection` flag on all `HTML_Element*` that is inside the selection.

#### Adaptive zoom

Documentation for adaptive zoom

#### run-in

An element with display:run-in becomes an inline box if:
- the element contains no blocks
and:
- the element's next sibling is an in-flow block box (i.e. not floated or absolutely positioned)
Otherwise it becomes a block box.

The layout engine starts by assuming that a run-in is a block box and lays it out like that in a `Container` (this container is referred to as element A below). After it has been laid out, the engine knows whether or not it is a inline run-in candidate (if it contained no blocks, it typically is). If it isn't, it will remain a block. If it is, on the other hand (and this is what the remaining part of this section attempts to describe), it will store itself in its `Container`'s (element A) `reflow_state->pending_run_in_box`. This happens in `BlockBox::FinishLayout()`. Now we need to find out if there is a next sibling of the run-in, and if there is, what kind of box that sibling gets. It needs to be an in-flow block box in order for the run-in to become an inline.

Rule 1: `Container::CloseVerticalLayout()` will reset its `reflow_state->pending_run_in_box` - unless it's called because a new block is added from (`GetNewBlockStage1()`).

Rule 2: `Container::Layout()` on an element B that is a child block of `Container` A will - if B is really a sibling of the run-in - "steal" and reset `Container` A's pending_run_in_box, convert it to an inline box and lay it out as if the run-in sort of were element B's own child (except that B's properties are not inherited into the run-in).

This means: If we get from the run-in's `BlockBox::FinishLayout()` to block B's `Container::Layout()` without an intervening reset of A's `reflow_state->pending_run_in_box`, you've got an inline run-in. Well, probably... but there's one more thing: This is only true if the run-in's parent element also is an ancestor of B; if it isn't, B isn't really a sibling of the run-in. This check is performed in `Container::LayoutRunIn()`.

#### Elements inserted by layout

In some situations the layout engine needs to insert HTML elements on its own. There are three categories: anonymous table boxes, the 'content' property (which is normally specified on ::before and ::after pseudo elements, but in Opera (as specified in CSS 3) we also support it on any other element), and ::first-letter.

Documentation for inserted elements