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.
See the overview section in the API documentation below.
For detailed information on how to use the layout module in Opera and the module's public API, please refer to the API documentation.
The memory aspects of the layout module are described here.
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 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.
In order to access the layout tree, traversal objects are used.
TraversalObject
Block traverse
Line traverse
Z-index traverse
This code
<P><FONT>one</P> <P>twoGenerates 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.
BODY | v P border:10px solid red; | v DIV border:inherit; | \ v v text text2text2 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).
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 is not well defined in the CSS spec. The algorithm used in Opera is described here.
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).
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.
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) |
|
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) |
|
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) |
|
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) |
|
n pixel big parent_1's top margin causes outer's 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 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 "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. |
| 1) |
|
Margins: n and m should never collapse. |
| 2) |
|
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) |
|
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) |
|
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) |
|
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
In this example cleared element set's inner's |
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.
Further specification of text wrap
FlexRoot is documented here.
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.
Unicode linebreaking specification
Opera's implementation of the CSS3 multi-column spec.
Specification for the first-line pseudo-element can be found here.
ContainerReflowState::is_css_first_lineContainer::IsCssFirstLine().Line::packed2.is_first_lineWordInfo::packed2.first_line_widthText_Box::packed.first_line_word_spacingHTML_Element::packed2.has_first_lineLayoutProperties::use_first_line_propsg_anonymous_first_line_elmAdding 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.
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.
::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.
SelectionBoundaryPoint (defined in logdoc) and a representation used internally
by layout (which is LayoutSelectionPoint as well as various
element + offset value pairs used internally).
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).
LayoutSelectionPoint and SelectionBoundaryPoint
representations.
TextSelection holds information about the current selection. It has two SelectionBoundaryPoints as members: a start and an end point.
TextSelectionObject is a TraversalObject responsible of translating from a mouse coordinate to SelectionBoundaryPoint (see GetNearestBoundaryPoint()).
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.
Documentation for adaptive zoom
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().
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.