[LFC] Drop Display:Box from FormattingContext::compute* functions
[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(firstChild);
70         layoutContext.createDisplayBox(*firstChild);
71     }
72     // 1. Go all the way down to the leaf node
73     // 2. Compute static position and width as we traverse down
74     // 3. As we climb back on the tree, compute height and finialize position
75     // (Any subtrees with new formatting contexts need to layout synchronously)
76     while (!layoutQueue.isEmpty()) {
77         // Traverse down on the descendants and compute width/static position until we find a leaf node.
78         while (true) {
79             auto& layoutBox = *layoutQueue.last();
80
81             if (layoutBox.establishesFormattingContext()) {
82                 layoutFormattingContextRoot(layoutContext, floatingContext, formattingState, layoutBox);
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(nextSibling);
90                 layoutContext.createDisplayBox(*nextSibling);
91                 continue;
92             }
93
94             LOG_WITH_STREAM(FormattingContextLayout, stream << "[Compute] -> [Position][Border][Padding][Width][Margin] -> for layoutBox(" << &layoutBox << ")");
95             computeStaticPosition(layoutContext, layoutBox);
96             computeBorderAndPadding(layoutContext, layoutBox);
97             computeWidthAndMargin(layoutContext, layoutBox);
98             if (!is<Container>(layoutBox) || !downcast<Container>(layoutBox).hasInFlowOrFloatingChild())
99                 break;
100             auto* firstChild = downcast<Container>(layoutBox).firstInFlowOrFloatingChild();
101             layoutQueue.append(firstChild);
102             layoutContext.createDisplayBox(*firstChild);
103         }
104
105         // Climb back on the ancestors and compute height/final position.
106         while (!layoutQueue.isEmpty()) {
107             // All inflow descendants (if there are any) are laid out by now. Let's compute the box's height.
108             auto& layoutBox = *layoutQueue.takeLast();
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);
114             // Finalize position with clearance.
115             if (layoutBox.hasFloatClear())
116                 computeVerticalPositionForFloatClear(layoutContext, floatingContext, layoutBox);
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(nextSibling);
124                 layoutContext.createDisplayBox(*nextSibling);
125                 break;
126             }
127         }
128     }
129     // Place the inflow positioned children.
130     placeInFlowPositionedChildren(layoutContext, formattingRoot);
131     LOG_WITH_STREAM(FormattingContextLayout, stream << "[End] -> block formatting context -> layout context(" << &layoutContext << ") formatting root(" << &root() << ")");
132 }
133
134 void BlockFormattingContext::layoutFormattingContextRoot(LayoutContext& layoutContext, FloatingContext& floatingContext, FormattingState&, const Box& layoutBox) const
135 {
136     // Start laying out this formatting root in the formatting contenxt it lives in.
137     LOG_WITH_STREAM(FormattingContextLayout, stream << "[Compute] -> [Position][Border][Padding][Width][Margin] -> for layoutBox(" << &layoutBox << ")");
138     computeStaticPosition(layoutContext, layoutBox);
139     computeBorderAndPadding(layoutContext, layoutBox);
140     computeWidthAndMargin(layoutContext, layoutBox);
141
142     // Swich over to the new formatting context (the one that the root creates).
143     auto formattingContext = layoutContext.formattingContext(layoutBox);
144     formattingContext->layout(layoutContext, layoutContext.establishedFormattingState(layoutBox));
145
146     // Come back and finalize the root's geometry.
147     LOG_WITH_STREAM(FormattingContextLayout, stream << "[Compute] -> [Height][Margin] -> for layoutBox(" << &layoutBox << ")");
148     computeHeightAndMargin(layoutContext, layoutBox);
149
150     // Float related final positioning.
151     if (layoutBox.isFloatingPositioned())
152         computeFloatingPosition(layoutContext, floatingContext, layoutBox);
153     else if (layoutBox.hasFloatClear())
154         computeVerticalPositionForFloatClear(layoutContext, floatingContext, layoutBox);
155     else
156         computePositionToAvoidFloats(layoutContext, floatingContext, layoutBox);
157
158     // Now that we computed the root's height, we can go back and layout the out-of-flow descedants (if any).
159     formattingContext->layoutOutOfFlowDescendants(layoutContext, layoutBox);
160 }
161
162 void BlockFormattingContext::computeStaticPosition(LayoutContext& layoutContext, const Box& layoutBox) const
163 {
164     layoutContext.displayBoxForLayoutBox(layoutBox)->setTopLeft(Geometry::staticPosition(layoutContext, layoutBox));
165 }
166
167 void BlockFormattingContext::computeEstimatedMarginTop(LayoutContext& layoutContext, const Box& layoutBox) const
168 {
169     auto estimatedMarginTop = Geometry::estimatedMarginTop(layoutContext, layoutBox);
170
171     auto& displayBox = *layoutContext.displayBoxForLayoutBox(layoutBox);
172     displayBox.setEstimatedMarginTop(estimatedMarginTop);
173     displayBox.moveVertically(estimatedMarginTop);
174 }
175
176 void BlockFormattingContext::computeEstimatedMarginTopForAncestors(LayoutContext& layoutContext, const Box& layoutBox) const
177 {
178     // We only need to estimate margin top for float related layout (formatting context roots avoid floats).
179     ASSERT(layoutBox.isFloatingPositioned() || layoutBox.hasFloatClear() || layoutBox.establishesBlockFormattingContext());
180
181     // 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).
182     // In block formatting context the final position for a normal flow box includes
183     // 1. the static position and
184     // 2. the corresponding (non)collapsed margins.
185     // 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
186     // (and the height might be based on the content).
187     // 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.
188     //
189     // 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.
190
191     for (auto* ancestor = layoutBox.containingBlock(); ancestor && !ancestor->establishesBlockFormattingContext(); ancestor = ancestor->containingBlock()) {
192         auto* displayBox = layoutContext.displayBoxForLayoutBox(*ancestor);
193         ASSERT(displayBox);
194         // FIXME: with incremental layout, we might actually have a valid (non-estimated) margin top as well.
195         if (displayBox->estimatedMarginTop())
196             return;
197
198         computeEstimatedMarginTop(layoutContext, *ancestor);
199     }
200 }
201
202 void BlockFormattingContext::computeFloatingPosition(LayoutContext& layoutContext, FloatingContext& floatingContext, const Box& layoutBox) const
203 {
204     ASSERT(layoutBox.isFloatingPositioned());
205     auto& displayBox = *layoutContext.displayBoxForLayoutBox(layoutBox);
206     // 8.3.1 Collapsing margins
207     // In block formatting context margins between a floated box and any other box do not collapse.
208     // Adjust the static position by using the previous inflow box's non-collapsed margin.
209     if (auto* previousInFlowBox = layoutBox.previousInFlowSibling()) {
210         auto& previousDisplayBox = *layoutContext.displayBoxForLayoutBox(*previousInFlowBox);
211         displayBox.moveVertically(previousDisplayBox.nonCollapsedMarginBottom() - previousDisplayBox.marginBottom());
212     }
213     computeEstimatedMarginTopForAncestors(layoutContext, layoutBox);
214     displayBox.setTopLeft(floatingContext.positionForFloat(layoutBox));
215     floatingContext.floatingState().append(layoutBox);
216 }
217
218 void BlockFormattingContext::computePositionToAvoidFloats(LayoutContext& layoutContext, FloatingContext& floatingContext, const Box& layoutBox) const
219 {
220     // Formatting context roots avoid floats.
221     ASSERT(layoutBox.establishesBlockFormattingContext());
222     ASSERT(!layoutBox.isFloatingPositioned());
223     ASSERT(!layoutBox.hasFloatClear());
224
225     if (floatingContext.floatingState().isEmpty())
226         return;
227
228     computeEstimatedMarginTopForAncestors(layoutContext, layoutBox);
229     if (auto adjustedPosition = floatingContext.positionForFloatAvoiding(layoutBox))
230         layoutContext.displayBoxForLayoutBox(layoutBox)->setTopLeft(*adjustedPosition);
231 }
232
233 void BlockFormattingContext::computeVerticalPositionForFloatClear(LayoutContext& layoutContext, const FloatingContext& floatingContext, const Box& layoutBox) const
234 {
235     ASSERT(layoutBox.hasFloatClear());
236     if (floatingContext.floatingState().isEmpty())
237         return;
238
239     computeEstimatedMarginTopForAncestors(layoutContext, layoutBox);
240     if (auto verticalPositionWithClearance = floatingContext.verticalPositionWithClearance(layoutBox))
241         layoutContext.displayBoxForLayoutBox(layoutBox)->setTop(*verticalPositionWithClearance);
242 }
243
244 void BlockFormattingContext::computeInFlowPositionedPosition(LayoutContext& layoutContext, const Box& layoutBox) const
245 {
246     layoutContext.displayBoxForLayoutBox(layoutBox)->setTopLeft(Geometry::inFlowPositionedPosition(layoutContext, layoutBox));
247 }
248
249 void BlockFormattingContext::computeWidthAndMargin(LayoutContext& layoutContext, const Box& layoutBox) const
250 {
251     WidthAndMargin widthAndMargin;
252
253     if (layoutBox.isInFlow())
254         widthAndMargin = Geometry::inFlowWidthAndMargin(layoutContext, layoutBox);
255     else if (layoutBox.isFloatingPositioned())
256         widthAndMargin = Geometry::floatingWidthAndMargin(layoutContext, *this, layoutBox);
257     else
258         ASSERT_NOT_REACHED();
259
260     auto& displayBox = *layoutContext.displayBoxForLayoutBox(layoutBox);
261     displayBox.setContentBoxWidth(widthAndMargin.width);
262     displayBox.moveHorizontally(widthAndMargin.margin.left);
263     displayBox.setHorizontalMargin(widthAndMargin.margin);
264     displayBox.setHorizontalNonComputedMargin(widthAndMargin.nonComputedMargin);
265 }
266
267 void BlockFormattingContext::computeHeightAndMargin(LayoutContext& layoutContext, const Box& layoutBox) const
268 {
269     HeightAndMargin heightAndMargin;
270     std::optional<LayoutUnit> marginTopOffset;
271     auto& displayBox = *layoutContext.displayBoxForLayoutBox(layoutBox);
272
273     if (layoutBox.isInFlow()) {
274         heightAndMargin = Geometry::inFlowHeightAndMargin(layoutContext, layoutBox);
275
276         // If this box has already been moved by the estimated vertical margin, no need to move it again.
277         if (!displayBox.estimatedMarginTop())
278             marginTopOffset = heightAndMargin.collapsedMargin.value_or(heightAndMargin.margin).top;
279     } else if (layoutBox.isFloatingPositioned()) {
280         heightAndMargin = Geometry::floatingHeightAndMargin(layoutContext, layoutBox);
281         ASSERT(!heightAndMargin.collapsedMargin);
282
283         marginTopOffset = heightAndMargin.margin.top;
284     } else
285         ASSERT_NOT_REACHED();
286
287     displayBox.setContentBoxHeight(heightAndMargin.height);
288     displayBox.setVerticalNonCollapsedMargin(heightAndMargin.margin);
289     displayBox.setVerticalMargin(heightAndMargin.collapsedMargin.value_or(heightAndMargin.margin));
290     if (marginTopOffset)
291         displayBox.moveVertically(*marginTopOffset);
292 }
293
294 FormattingContext::InstrinsicWidthConstraints BlockFormattingContext::instrinsicWidthConstraints(LayoutContext& layoutContext, const Box& layoutBox) const
295 {
296     auto& formattingState = layoutContext.formattingStateForBox(layoutBox);
297     ASSERT(formattingState.isBlockFormattingState());
298     if (auto instrinsicWidthConstraints = formattingState.instrinsicWidthConstraints(layoutBox))
299         return *instrinsicWidthConstraints;
300
301     // Can we just compute them without checking the children?
302     if (!Geometry::instrinsicWidthConstraintsNeedChildrenWidth(layoutBox)) {
303         auto instrinsicWidthConstraints = Geometry::instrinsicWidthConstraints(layoutContext, layoutBox);
304         formattingState.setInstrinsicWidthConstraints(layoutBox, instrinsicWidthConstraints);
305         return instrinsicWidthConstraints;
306     }
307
308     // Visit the in-flow descendants and compute their min/max intrinsic width if needed.
309     // 1. Go all the way down to the leaf node
310     // 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)
311     // 3. As we climb back on the tree, compute min/max intrinsic width
312     // (Any subtrees with new formatting contexts need to layout synchronously)
313     Vector<const Box*> queue;
314     // Non-containers early return.
315     ASSERT(is<Container>(layoutBox));
316     if (auto* firstChild = downcast<Container>(layoutBox).firstInFlowOrFloatingChild())
317         queue.append(firstChild);
318
319     auto& formattingStateForChildren = layoutBox.establishesFormattingContext() ? layoutContext.establishedFormattingState(layoutBox) : formattingState;
320     while (!queue.isEmpty()) {
321         while (true) {
322             auto& childBox = *queue.last(); 
323             // Already computed?
324             auto instrinsicWidthConstraints = formattingStateForChildren.instrinsicWidthConstraints(childBox);
325             // Can we just compute them without checking the children?
326             if (!instrinsicWidthConstraints && !Geometry::instrinsicWidthConstraintsNeedChildrenWidth(childBox))
327                 instrinsicWidthConstraints = Geometry::instrinsicWidthConstraints(layoutContext, childBox);
328             // Is it a formatting context root?
329             if (!instrinsicWidthConstraints && childBox.establishesFormattingContext())
330                 instrinsicWidthConstraints = layoutContext.formattingContext(childBox)->instrinsicWidthConstraints(layoutContext, childBox);
331             // Go to the next sibling (and skip the descendants) if this box's min/max width is computed.
332             if (instrinsicWidthConstraints) {
333                 formattingStateForChildren.setInstrinsicWidthConstraints(childBox, *instrinsicWidthConstraints); 
334                 queue.removeLast();
335                 if (!childBox.nextInFlowOrFloatingSibling())
336                     break;
337                 queue.append(childBox.nextInFlowOrFloatingSibling());
338                 continue;
339             }
340
341             if (!is<Container>(childBox) || !downcast<Container>(childBox).hasInFlowOrFloatingChild())
342                 break;
343
344             queue.append(downcast<Container>(childBox).firstInFlowOrFloatingChild());
345         }
346
347         // Compute min/max intrinsic width bottom up.
348         while (!queue.isEmpty()) {
349             auto& childBox = *queue.takeLast();
350             formattingStateForChildren.setInstrinsicWidthConstraints(childBox, Geometry::instrinsicWidthConstraints(layoutContext, childBox)); 
351             // Move over to the next sibling or take the next box in the queue.
352             if (!is<Container>(childBox) || !downcast<Container>(childBox).nextInFlowOrFloatingSibling())
353                 continue;
354             queue.append(downcast<Container>(childBox).nextInFlowOrFloatingSibling());
355         }
356     }
357
358     auto instrinsicWidthConstraints = Geometry::instrinsicWidthConstraints(layoutContext, layoutBox);
359     formattingState.setInstrinsicWidthConstraints(layoutBox, instrinsicWidthConstraints); 
360     return instrinsicWidthConstraints;
361 }
362
363 }
364 }
365
366 #endif