b9640e8cb5e2012efe802799bbc100f6de91d6eb
[WebKit-https.git] / Source / WebCore / layout / blockformatting / BlockFormattingContext.cpp
1 /*
2  * Copyright (C) 2018 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "BlockFormattingContext.h"
28
29 #if ENABLE(LAYOUT_FORMATTING_CONTEXT)
30
31 #include "BlockFormattingState.h"
32 #include "DisplayBox.h"
33 #include "FloatingContext.h"
34 #include "FloatingState.h"
35 #include "LayoutBox.h"
36 #include "LayoutContainer.h"
37 #include "LayoutContext.h"
38 #include "Logging.h"
39 #include <wtf/IsoMallocInlines.h>
40 #include <wtf/text/TextStream.h>
41
42 namespace WebCore {
43 namespace Layout {
44
45 WTF_MAKE_ISO_ALLOCATED_IMPL(BlockFormattingContext);
46
47 BlockFormattingContext::BlockFormattingContext(const Box& formattingContextRoot)
48     : FormattingContext(formattingContextRoot)
49 {
50 }
51
52 void BlockFormattingContext::layout(LayoutContext& layoutContext, FormattingState& formattingState) const
53 {
54     // 9.4.1 Block formatting contexts
55     // In a block formatting context, boxes are laid out one after the other, vertically, beginning at the top of a containing block.
56     // The vertical distance between two sibling boxes is determined by the 'margin' properties.
57     // Vertical margins between adjacent block-level boxes in a block formatting context collapse.
58     if (!is<Container>(root()))
59         return;
60
61     LOG_WITH_STREAM(FormattingContextLayout, stream << "[Start] -> block formatting context -> layout context(" << &layoutContext << ") formatting root(" << &root() << ")");
62
63     auto& formattingRoot = downcast<Container>(root());
64     LayoutQueue layoutQueue;
65     FloatingContext floatingContext(formattingState.floatingState());
66     // This is a post-order tree traversal layout.
67     // The root container layout is done in the formatting context it lives in, not that one it creates, so let's start with the first child.
68     if (auto* firstChild = formattingRoot.firstInFlowOrFloatingChild())
69         layoutQueue.append(std::make_unique<BoxPair>(BoxPair {*firstChild, layoutContext.createDisplayBox(*firstChild)}));
70     // 1. Go all the way down to the leaf node
71     // 2. Compute static position and width as we traverse down
72     // 3. As we climb back on the tree, compute height and finialize position
73     // (Any subtrees with new formatting contexts need to layout synchronously)
74     while (!layoutQueue.isEmpty()) {
75         // Traverse down on the descendants and compute width/static position until we find a leaf node.
76         while (true) {
77             auto& boxPair = *layoutQueue.last();
78             auto& layoutBox = boxPair.layout;
79             auto& displayBox = boxPair.display;
80
81             if (layoutBox.establishesFormattingContext()) {
82                 layoutFormattingContextRoot(layoutContext, floatingContext, formattingState, layoutBox, displayBox);
83                 layoutQueue.removeLast();
84                 // Since this box is a formatting context root, it takes care of its entire subtree.
85                 // Continue with next sibling if exists.
86                 if (!layoutBox.nextInFlowOrFloatingSibling())
87                     break;
88                 auto* nextSibling = layoutBox.nextInFlowOrFloatingSibling();
89                 layoutQueue.append(std::make_unique<BoxPair>(BoxPair {*nextSibling, layoutContext.createDisplayBox(*nextSibling)}));
90                 continue;
91             }
92
93             LOG_WITH_STREAM(FormattingContextLayout, stream << "[Compute] -> [Position][Border][Padding][Width][Margin] -> for layoutBox(" << &layoutBox << ")");
94             computeStaticPosition(layoutContext, layoutBox, displayBox);
95             computeBorderAndPadding(layoutContext, layoutBox, displayBox);
96             computeWidthAndMargin(layoutContext, layoutBox, displayBox);
97             if (!is<Container>(layoutBox) || !downcast<Container>(layoutBox).hasInFlowOrFloatingChild())
98                 break;
99             auto& firstChild = *downcast<Container>(layoutBox).firstInFlowOrFloatingChild();
100             layoutQueue.append(std::make_unique<BoxPair>(BoxPair {firstChild, layoutContext.createDisplayBox(firstChild)}));
101         }
102
103         // Climb back on the ancestors and compute height/final position.
104         while (!layoutQueue.isEmpty()) {
105             // All inflow descendants (if there are any) are laid out by now. Let's compute the box's height.
106             auto boxPair = layoutQueue.takeLast();
107             auto& layoutBox = boxPair->layout;
108             auto& displayBox = boxPair->display;
109
110             LOG_WITH_STREAM(FormattingContextLayout, stream << "[Compute] -> [Height][Margin] -> for layoutBox(" << &layoutBox << ")");
111             // Formatting root boxes are special-cased and they don't come here.
112             ASSERT(!layoutBox.establishesFormattingContext());
113             computeHeightAndMargin(layoutContext, layoutBox, displayBox);
114             // Finalize position with clearance.
115             if (layoutBox.hasFloatClear())
116                 computeVerticalPositionForFloatClear(layoutContext, floatingContext, layoutBox, displayBox);
117             if (!is<Container>(layoutBox))
118                 continue;
119             auto& container = downcast<Container>(layoutBox);
120             // Move in-flow positioned children to their final position.
121             placeInFlowPositionedChildren(layoutContext, container);
122             if (auto* nextSibling = container.nextInFlowOrFloatingSibling()) {
123                 layoutQueue.append(std::make_unique<BoxPair>(BoxPair {*nextSibling, layoutContext.createDisplayBox(*nextSibling)}));
124                 break;
125             }
126         }
127     }
128     // Place the inflow positioned children.
129     placeInFlowPositionedChildren(layoutContext, formattingRoot);
130     LOG_WITH_STREAM(FormattingContextLayout, stream << "[End] -> block formatting context -> layout context(" << &layoutContext << ") formatting root(" << &root() << ")");
131 }
132
133 void BlockFormattingContext::layoutFormattingContextRoot(LayoutContext& layoutContext, FloatingContext& floatingContext, FormattingState&, const Box& layoutBox, Display::Box& displayBox) const
134 {
135     // Start laying out this formatting root in the formatting contenxt it lives in.
136     LOG_WITH_STREAM(FormattingContextLayout, stream << "[Compute] -> [Position][Border][Padding][Width][Margin] -> for layoutBox(" << &layoutBox << ")");
137     computeStaticPosition(layoutContext, layoutBox, displayBox);
138     computeBorderAndPadding(layoutContext, layoutBox, displayBox);
139     computeWidthAndMargin(layoutContext, layoutBox, displayBox);
140
141     // Swich over to the new formatting context (the one that the root creates).
142     auto formattingContext = layoutContext.formattingContext(layoutBox);
143     formattingContext->layout(layoutContext, layoutContext.establishedFormattingState(layoutBox));
144
145     // Come back and finalize the root's geometry.
146     LOG_WITH_STREAM(FormattingContextLayout, stream << "[Compute] -> [Height][Margin] -> for layoutBox(" << &layoutBox << ")");
147     computeHeightAndMargin(layoutContext, layoutBox, displayBox);
148
149     // Float related final positioning.
150     if (layoutBox.isFloatingPositioned())
151         computeFloatingPosition(layoutContext, floatingContext, layoutBox, displayBox);
152     else if (layoutBox.hasFloatClear())
153         computeVerticalPositionForFloatClear(layoutContext, floatingContext, layoutBox, displayBox);
154     else
155         computePositionToAvoidFloats(layoutContext, floatingContext, layoutBox, displayBox);
156
157     // Now that we computed the root's height, we can go back and layout the out-of-flow descedants (if any).
158     formattingContext->layoutOutOfFlowDescendants(layoutContext, layoutBox);
159 }
160
161 void BlockFormattingContext::computeStaticPosition(LayoutContext& layoutContext, const Box& layoutBox, Display::Box& displayBox) const
162 {
163     displayBox.setTopLeft(Geometry::staticPosition(layoutContext, layoutBox));
164 }
165
166 void BlockFormattingContext::computeEstimatedMarginTop(LayoutContext& layoutContext, const Box& layoutBox, Display::Box& displayBox) const
167 {
168     auto estimatedMarginTop = Geometry::estimatedMarginTop(layoutContext, layoutBox);
169     displayBox.setEstimatedMarginTop(estimatedMarginTop);
170     displayBox.moveVertically(estimatedMarginTop);
171 }
172
173 void BlockFormattingContext::computeEstimatedMarginTopForAncestors(LayoutContext& layoutContext, const Box& layoutBox) const
174 {
175     // We only need to estimate margin top for float related layout (formatting context roots avoid floats).
176     ASSERT(layoutBox.isFloatingPositioned() || layoutBox.hasFloatClear() || layoutBox.establishesBlockFormattingContext());
177
178     // In order to figure out whether a box should avoid a float, we need to know the final positions of both (ignore relative positioning for now).
179     // In block formatting context the final position for a normal flow box includes
180     // 1. the static position and
181     // 2. the corresponding (non)collapsed margins.
182     // Now the vertical margins are computed when all the descendants are finalized, because the margin values might be depending on the height of the box
183     // (and the height might be based on the content).
184     // So when we get to the point where we intersect the box with the float to decide if the box needs to move, we don't yet have the final vertical position.
185     //
186     // The idea here is that as long as we don't cross the block formatting context boundary, we should be able to pre-compute the final top margin.
187
188     for (auto* ancestor = layoutBox.containingBlock(); ancestor && !ancestor->establishesBlockFormattingContext(); ancestor = ancestor->containingBlock()) {
189         auto* displayBox = layoutContext.displayBoxForLayoutBox(*ancestor);
190         ASSERT(displayBox);
191         // FIXME: with incremental layout, we might actually have a valid (non-estimated) margin top as well.
192         if (displayBox->estimatedMarginTop())
193             return;
194
195         computeEstimatedMarginTop(layoutContext, *ancestor, *displayBox);
196     }
197 }
198
199 void BlockFormattingContext::computeFloatingPosition(LayoutContext& layoutContext, FloatingContext& floatingContext, const Box& layoutBox, Display::Box& displayBox) const
200 {
201     ASSERT(layoutBox.isFloatingPositioned());
202     // 8.3.1 Collapsing margins
203     // In block formatting context margins between a floated box and any other box do not collapse.
204     // Adjust the static position by using the previous inflow box's non-collapsed margin.
205     if (auto* previousInFlowBox = layoutBox.previousInFlowSibling()) {
206         auto& previousDisplayBox = *layoutContext.displayBoxForLayoutBox(*previousInFlowBox);
207         displayBox.moveVertically(previousDisplayBox.nonCollapsedMarginBottom() - previousDisplayBox.marginBottom());
208     }
209     computeEstimatedMarginTopForAncestors(layoutContext, layoutBox);
210     displayBox.setTopLeft(floatingContext.positionForFloat(layoutBox));
211     floatingContext.floatingState().append(layoutBox);
212 }
213
214 void BlockFormattingContext::computePositionToAvoidFloats(LayoutContext& layoutContext, FloatingContext& floatingContext, const Box& layoutBox, Display::Box& displayBox) const
215 {
216     // Formatting context roots avoid floats.
217     ASSERT(layoutBox.establishesBlockFormattingContext());
218     ASSERT(!layoutBox.isFloatingPositioned());
219     ASSERT(!layoutBox.hasFloatClear());
220
221     if (floatingContext.floatingState().isEmpty())
222         return;
223
224     computeEstimatedMarginTopForAncestors(layoutContext, layoutBox);
225     if (auto adjustedPosition = floatingContext.positionForFloatAvoiding(layoutBox))
226         displayBox.setTopLeft(*adjustedPosition);
227 }
228
229 void BlockFormattingContext::computeVerticalPositionForFloatClear(LayoutContext& layoutContext, const FloatingContext& floatingContext, const Box& layoutBox, Display::Box& displayBox) const
230 {
231     ASSERT(layoutBox.hasFloatClear());
232     if (floatingContext.floatingState().isEmpty())
233         return;
234
235     computeEstimatedMarginTopForAncestors(layoutContext, layoutBox);
236     if (auto verticalPositionWithClearance = floatingContext.verticalPositionWithClearance(layoutBox))
237         displayBox.setTop(*verticalPositionWithClearance);
238 }
239
240 void BlockFormattingContext::computeInFlowPositionedPosition(LayoutContext& layoutContext, const Box& layoutBox, Display::Box& displayBox) const
241 {
242     displayBox.setTopLeft(Geometry::inFlowPositionedPosition(layoutContext, layoutBox));
243 }
244
245 void BlockFormattingContext::computeWidthAndMargin(LayoutContext& layoutContext, const Box& layoutBox, Display::Box& displayBox) const
246 {
247     WidthAndMargin widthAndMargin;
248
249     if (layoutBox.isInFlow())
250         widthAndMargin = Geometry::inFlowWidthAndMargin(layoutContext, layoutBox);
251     else if (layoutBox.isFloatingPositioned())
252         widthAndMargin = Geometry::floatingWidthAndMargin(layoutContext, *this, layoutBox);
253     else
254         ASSERT_NOT_REACHED();
255
256     displayBox.setContentBoxWidth(widthAndMargin.width);
257     displayBox.moveHorizontally(widthAndMargin.margin.left);
258     displayBox.setHorizontalMargin(widthAndMargin.margin);
259     displayBox.setHorizontalNonComputedMargin(widthAndMargin.nonComputedMargin);
260 }
261
262 void BlockFormattingContext::computeHeightAndMargin(LayoutContext& layoutContext, const Box& layoutBox, Display::Box& displayBox) const
263 {
264     HeightAndMargin heightAndMargin;
265     std::optional<LayoutUnit> marginTopOffset;
266
267     if (layoutBox.isInFlow()) {
268         heightAndMargin = Geometry::inFlowHeightAndMargin(layoutContext, layoutBox);
269
270         // If this box has already been moved by the estimated vertical margin, no need to move it again.
271         if (!displayBox.estimatedMarginTop())
272             marginTopOffset = heightAndMargin.collapsedMargin.value_or(heightAndMargin.margin).top;
273     } else if (layoutBox.isFloatingPositioned()) {
274         heightAndMargin = Geometry::floatingHeightAndMargin(layoutContext, layoutBox);
275         ASSERT(!heightAndMargin.collapsedMargin);
276
277         marginTopOffset = heightAndMargin.margin.top;
278     } else
279         ASSERT_NOT_REACHED();
280
281     displayBox.setContentBoxHeight(heightAndMargin.height);
282     displayBox.setVerticalNonCollapsedMargin(heightAndMargin.margin);
283     displayBox.setVerticalMargin(heightAndMargin.collapsedMargin.value_or(heightAndMargin.margin));
284     if (marginTopOffset)
285         displayBox.moveVertically(*marginTopOffset);
286 }
287
288 FormattingContext::InstrinsicWidthConstraints BlockFormattingContext::instrinsicWidthConstraints(LayoutContext& layoutContext, const Box& layoutBox) const
289 {
290     auto& formattingState = layoutContext.formattingStateForBox(layoutBox);
291     ASSERT(formattingState.isBlockFormattingState());
292     if (auto instrinsicWidthConstraints = formattingState.instrinsicWidthConstraints(layoutBox))
293         return *instrinsicWidthConstraints;
294
295     // Can we just compute them without checking the children?
296     if (!Geometry::instrinsicWidthConstraintsNeedChildrenWidth(layoutBox)) {
297         auto instrinsicWidthConstraints = Geometry::instrinsicWidthConstraints(layoutContext, layoutBox);
298         formattingState.setInstrinsicWidthConstraints(layoutBox, instrinsicWidthConstraints);
299         return instrinsicWidthConstraints;
300     }
301
302     // Visit the in-flow descendants and compute their min/max intrinsic width if needed.
303     // 1. Go all the way down to the leaf node
304     // 2. Check if actually need to visit all the boxes as we traverse down (already computed, container's min/max does not depend on descendants etc)
305     // 3. As we climb back on the tree, compute min/max intrinsic width
306     // (Any subtrees with new formatting contexts need to layout synchronously)
307     Vector<const Box*> queue;
308     // Non-containers early return.
309     ASSERT(is<Container>(layoutBox));
310     if (auto* firstChild = downcast<Container>(layoutBox).firstInFlowOrFloatingChild())
311         queue.append(firstChild);
312
313     auto& formattingStateForChildren = layoutBox.establishesFormattingContext() ? layoutContext.establishedFormattingState(layoutBox) : formattingState;
314     while (!queue.isEmpty()) {
315         while (true) {
316             auto& childBox = *queue.last(); 
317             // Already computed?
318             auto instrinsicWidthConstraints = formattingStateForChildren.instrinsicWidthConstraints(childBox);
319             // Can we just compute them without checking the children?
320             if (!instrinsicWidthConstraints && !Geometry::instrinsicWidthConstraintsNeedChildrenWidth(childBox))
321                 instrinsicWidthConstraints = Geometry::instrinsicWidthConstraints(layoutContext, childBox);
322             // Is it a formatting context root?
323             if (!instrinsicWidthConstraints && childBox.establishesFormattingContext())
324                 instrinsicWidthConstraints = layoutContext.formattingContext(childBox)->instrinsicWidthConstraints(layoutContext, childBox);
325             // Go to the next sibling (and skip the descendants) if this box's min/max width is computed.
326             if (instrinsicWidthConstraints) {
327                 formattingStateForChildren.setInstrinsicWidthConstraints(childBox, *instrinsicWidthConstraints); 
328                 queue.removeLast();
329                 if (!childBox.nextInFlowOrFloatingSibling())
330                     break;
331                 queue.append(childBox.nextInFlowOrFloatingSibling());
332                 continue;
333             }
334
335             if (!is<Container>(childBox) || !downcast<Container>(childBox).hasInFlowOrFloatingChild())
336                 break;
337
338             queue.append(downcast<Container>(childBox).firstInFlowOrFloatingChild());
339         }
340
341         // Compute min/max intrinsic width bottom up.
342         while (!queue.isEmpty()) {
343             auto& childBox = *queue.takeLast();
344             formattingStateForChildren.setInstrinsicWidthConstraints(childBox, Geometry::instrinsicWidthConstraints(layoutContext, childBox)); 
345             // Move over to the next sibling or take the next box in the queue.
346             if (!is<Container>(childBox) || !downcast<Container>(childBox).nextInFlowOrFloatingSibling())
347                 continue;
348             queue.append(downcast<Container>(childBox).nextInFlowOrFloatingSibling());
349         }
350     }
351
352     auto instrinsicWidthConstraints = Geometry::instrinsicWidthConstraints(layoutContext, layoutBox);
353     formattingState.setInstrinsicWidthConstraints(layoutBox, instrinsicWidthConstraints); 
354     return instrinsicWidthConstraints;
355 }
356
357 }
358 }
359
360 #endif