[LFC][Floating] Add basic left/right floating positioning.
[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(formattingRoot, 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<LayoutPair>(LayoutPair {*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& layoutPair = *layoutQueue.last();
78             auto& layoutBox = layoutPair.layoutBox;
79             auto& displayBox = layoutPair.displayBox;
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<LayoutPair>(LayoutPair {*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<LayoutPair>(LayoutPair {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 layoutPair = layoutQueue.takeLast();
107             auto& layoutBox = layoutPair->layoutBox;
108             auto& displayBox = layoutPair->displayBox;
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
114             computeHeightAndMargin(layoutContext, layoutBox, displayBox);
115             if (!is<Container>(layoutBox))
116                 continue;
117             auto& container = downcast<Container>(layoutBox);
118             // Move in-flow positioned children to their final position.
119             placeInFlowPositionedChildren(layoutContext, container);
120             layoutOutOfFlowDescendants(layoutContext, container);
121             if (auto* nextSibling = container.nextInFlowOrFloatingSibling()) {
122                 layoutQueue.append(std::make_unique<LayoutPair>(LayoutPair {*nextSibling, layoutContext.createDisplayBox(*nextSibling)}));
123                 break;
124             }
125         }
126     }
127     // Place the inflow positioned children.
128     placeInFlowPositionedChildren(layoutContext, formattingRoot);
129     LOG_WITH_STREAM(FormattingContextLayout, stream << "[End] -> block formatting context -> layout context(" << &layoutContext << ") formatting root(" << &root() << ")");
130 }
131
132 void BlockFormattingContext::layoutFormattingContextRoot(LayoutContext& layoutContext, FloatingContext& floatingContext, FormattingState&, const Box& layoutBox, Display::Box& displayBox) const
133 {
134     // Start laying out this formatting root in the formatting contenxt it lives in.
135     LOG_WITH_STREAM(FormattingContextLayout, stream << "[Compute] -> [Position][Border][Padding][Width][Margin] -> for layoutBox(" << &layoutBox << ")");
136     computeStaticPosition(layoutContext, layoutBox, displayBox);
137     computeBorderAndPadding(layoutContext, layoutBox, displayBox);
138     computeWidthAndMargin(layoutContext, layoutBox, displayBox);
139
140     // Swich over to the new formatting context (the one that the root creates).
141     auto formattingContext = layoutContext.formattingContext(layoutBox);
142     formattingContext->layout(layoutContext, layoutContext.establishedFormattingState(layoutBox));
143
144     // Come back and finalize the root's geometry.
145     LOG_WITH_STREAM(FormattingContextLayout, stream << "[Compute] -> [Height][Margin] -> for layoutBox(" << &layoutBox << ")");
146     computeHeightAndMargin(layoutContext, layoutBox, displayBox);
147     if (layoutBox.isFloatingPositioned())
148         computeFloatingPosition(floatingContext, layoutBox, displayBox);
149     // Now that we computed the root's height, we can go back and layout the out-of-flow descedants (if any).
150     formattingContext->layoutOutOfFlowDescendants(layoutContext, layoutBox);
151 }
152
153 void BlockFormattingContext::computeStaticPosition(LayoutContext& layoutContext, const Box& layoutBox, Display::Box& displayBox) const
154 {
155     displayBox.setTopLeft(Geometry::staticPosition(layoutContext, layoutBox));
156 }
157
158 void BlockFormattingContext::computeFloatingPosition(FloatingContext& floatingContext, const Box& layoutBox, Display::Box& displayBox) const
159 {
160     ASSERT(layoutBox.isFloatingPositioned());
161     displayBox.setTopLeft(floatingContext.computePosition(layoutBox));
162     floatingContext.floatingState().append(layoutBox);
163 }
164
165 void BlockFormattingContext::computeInFlowPositionedPosition(LayoutContext& layoutContext, const Box& layoutBox, Display::Box& displayBox) const
166 {
167     displayBox.setTopLeft(Geometry::inFlowPositionedPosition(layoutContext, layoutBox));
168 }
169
170 void BlockFormattingContext::computeWidthAndMargin(LayoutContext& layoutContext, const Box& layoutBox, Display::Box& displayBox) const
171 {
172     if (layoutBox.isInFlow())
173         return computeInFlowWidthAndMargin(layoutContext, layoutBox, displayBox);
174
175     if (layoutBox.isFloatingPositioned())
176         return computeFloatingWidthAndMargin(layoutContext, layoutBox, displayBox);
177
178     ASSERT_NOT_REACHED();
179 }
180
181 void BlockFormattingContext::computeHeightAndMargin(LayoutContext& layoutContext, const Box& layoutBox, Display::Box& displayBox) const
182 {
183     if (layoutBox.isInFlow())
184         return computeInFlowHeightAndMargin(layoutContext, layoutBox, displayBox);
185
186     if (layoutBox.isFloatingPositioned())
187         return computeFloatingHeightAndMargin(layoutContext, layoutBox, displayBox);
188
189     ASSERT_NOT_REACHED();
190 }
191
192 void BlockFormattingContext::computeInFlowHeightAndMargin(LayoutContext& layoutContext, const Box& layoutBox, Display::Box& displayBox) const
193 {
194     auto heightAndMargin = Geometry::inFlowHeightAndMargin(layoutContext, layoutBox);
195     displayBox.setContentBoxHeight(heightAndMargin.height);
196     displayBox.moveVertically(heightAndMargin.collapsedMargin.value_or(heightAndMargin.margin).top);
197     displayBox.setVerticalMargin(heightAndMargin.collapsedMargin.value_or(heightAndMargin.margin));
198     displayBox.setVerticalNonCollapsedMargin(heightAndMargin.margin);
199 }
200
201 void BlockFormattingContext::computeInFlowWidthAndMargin(LayoutContext& layoutContext, const Box& layoutBox, Display::Box& displayBox) const
202 {
203     auto widthAndMargin = Geometry::inFlowWidthAndMargin(layoutContext, layoutBox);
204     displayBox.setContentBoxWidth(widthAndMargin.width);
205     displayBox.moveHorizontally(widthAndMargin.margin.left);
206     displayBox.setHorizontalMargin(widthAndMargin.margin);
207 }
208
209 FormattingContext::InstrinsicWidthConstraints BlockFormattingContext::instrinsicWidthConstraints(LayoutContext& layoutContext, const Box& layoutBox) const
210 {
211     auto& formattingState = layoutContext.formattingStateForBox(layoutBox);
212     ASSERT(formattingState.isBlockFormattingState());
213     if (auto instrinsicWidthConstraints = formattingState.instrinsicWidthConstraints(layoutBox))
214         return *instrinsicWidthConstraints;
215
216     // Can we just compute them without checking the children?
217     if (!Geometry::instrinsicWidthConstraintsNeedChildrenWidth(layoutBox)) {
218         auto instrinsicWidthConstraints = Geometry::instrinsicWidthConstraints(layoutContext, layoutBox);
219         formattingState.setInstrinsicWidthConstraints(layoutBox, instrinsicWidthConstraints);
220         return instrinsicWidthConstraints;
221     }
222
223     // Visit the in-flow descendants and compute their min/max intrinsic width if needed.
224     // 1. Go all the way down to the leaf node
225     // 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)
226     // 3. As we climb back on the tree, compute min/max intrinsic width
227     // (Any subtrees with new formatting contexts need to layout synchronously)
228     Vector<const Box*> queue;
229     // Non-containers early return.
230     ASSERT(is<Container>(layoutBox));
231     if (auto* firstChild = downcast<Container>(layoutBox).firstInFlowOrFloatingChild())
232         queue.append(firstChild);
233
234     auto& formattingStateForChildren = layoutBox.establishesFormattingContext() ? layoutContext.establishedFormattingState(layoutBox) : formattingState;
235     while (!queue.isEmpty()) {
236         while (true) {
237             auto& childBox = *queue.last(); 
238             // Already computed?
239             auto instrinsicWidthConstraints = formattingStateForChildren.instrinsicWidthConstraints(childBox);
240             // Can we just compute them without checking the children?
241             if (!instrinsicWidthConstraints && !Geometry::instrinsicWidthConstraintsNeedChildrenWidth(childBox))
242                 instrinsicWidthConstraints = Geometry::instrinsicWidthConstraints(layoutContext, childBox);
243             // Is it a formatting context root?
244             if (!instrinsicWidthConstraints && childBox.establishesFormattingContext())
245                 instrinsicWidthConstraints = layoutContext.formattingContext(childBox)->instrinsicWidthConstraints(layoutContext, childBox);
246             // Go to the next sibling (and skip the descendants) if this box's min/max width is computed.
247             if (instrinsicWidthConstraints) {
248                 formattingStateForChildren.setInstrinsicWidthConstraints(childBox, *instrinsicWidthConstraints); 
249                 queue.removeLast();
250                 if (!childBox.nextInFlowOrFloatingSibling())
251                     break;
252                 queue.append(childBox.nextInFlowOrFloatingSibling());
253                 continue;
254             }
255
256             if (!is<Container>(childBox) || !downcast<Container>(childBox).hasInFlowOrFloatingChild())
257                 break;
258
259             queue.append(downcast<Container>(childBox).firstInFlowOrFloatingChild());
260         }
261
262         // Compute min/max intrinsic width bottom up.
263         while (!queue.isEmpty()) {
264             auto& childBox = *queue.takeLast();
265             formattingStateForChildren.setInstrinsicWidthConstraints(childBox, Geometry::instrinsicWidthConstraints(layoutContext, childBox)); 
266             // Move over to the next sibling or take the next box in the queue.
267             if (!is<Container>(childBox) || !downcast<Container>(childBox).nextInFlowOrFloatingSibling())
268                 continue;
269             queue.append(downcast<Container>(childBox).nextInFlowOrFloatingSibling());
270         }
271     }
272
273     auto instrinsicWidthConstraints = Geometry::instrinsicWidthConstraints(layoutContext, layoutBox);
274     formattingState.setInstrinsicWidthConstraints(layoutBox, instrinsicWidthConstraints); 
275     return instrinsicWidthConstraints;
276 }
277
278 }
279 }
280
281 #endif