[LFC] Layout::Box::containingBlock should return a const ContainerBox&
[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 "FloatingContext.h"
33 #include "FloatingState.h"
34 #include "InvalidationState.h"
35 #include "LayoutBox.h"
36 #include "LayoutChildIterator.h"
37 #include "LayoutContainerBox.h"
38 #include "LayoutContext.h"
39 #include "LayoutState.h"
40 #include "Logging.h"
41 #include <wtf/IsoMallocInlines.h>
42 #include <wtf/text/TextStream.h>
43
44 namespace WebCore {
45 namespace Layout {
46
47 WTF_MAKE_ISO_ALLOCATED_IMPL(BlockFormattingContext);
48
49 BlockFormattingContext::BlockFormattingContext(const ContainerBox& formattingContextRoot, BlockFormattingState& formattingState)
50     : FormattingContext(formattingContextRoot, formattingState)
51 {
52 }
53
54 void BlockFormattingContext::layoutInFlowContent(InvalidationState& invalidationState, const HorizontalConstraints& rootHorizontalConstraints, const VerticalConstraints& rootVerticalConstraints)
55 {
56     // 9.4.1 Block formatting contexts
57     // In a block formatting context, boxes are laid out one after the other, vertically, beginning at the top of a containing block.
58     // The vertical distance between two sibling boxes is determined by the 'margin' properties.
59     // Vertical margins between adjacent block-level boxes in a block formatting context collapse.
60     LOG_WITH_STREAM(FormattingContextLayout, stream << "[Start] -> block formatting context -> formatting root(" << &root() << ")");
61     auto& formattingRoot = root();
62     ASSERT(formattingRoot.hasInFlowOrFloatingChild());
63     auto floatingContext = FloatingContext { formattingRoot, *this, formattingState().floatingState() };
64
65     LayoutQueue layoutQueue;
66     enum class LayoutDirection { Child, Sibling };
67     auto appendNextToLayoutQueue = [&] (const auto& layoutBox, auto direction) {
68         if (direction == LayoutDirection::Child) {
69             if (!is<ContainerBox>(layoutBox))
70                 return false;
71             for (auto* child = downcast<ContainerBox>(layoutBox).firstInFlowOrFloatingChild(); child; child = child->nextInFlowOrFloatingSibling()) {
72                 if (!invalidationState.needsLayout(*child))
73                     continue;
74                 layoutQueue.append(child);
75                 return true;
76             }
77             return false;
78         }
79
80         if (direction == LayoutDirection::Sibling) {
81             for (auto* nextSibling = layoutBox.nextInFlowOrFloatingSibling(); nextSibling; nextSibling = nextSibling->nextInFlowOrFloatingSibling()) {
82                 if (!invalidationState.needsLayout(*nextSibling))
83                     continue;
84                 layoutQueue.append(nextSibling);
85                 return true;
86             }
87             return false;
88         }
89         ASSERT_NOT_REACHED();
90         return false;
91     };
92
93     auto horizontalConstraintsForLayoutBox = [&] (const auto& layoutBox) {
94         auto& containingBlock = layoutBox.containingBlock();
95         if (&containingBlock == &formattingRoot)
96             return rootHorizontalConstraints;
97         return Geometry::horizontalConstraintsForInFlow(geometryForBox(containingBlock));
98     };
99
100     auto verticalConstraintsForLayoutBox = [&] (const auto& layoutBox) {
101         auto& containingBlock = layoutBox.containingBlock();
102         if (&containingBlock == &formattingRoot)
103             return rootVerticalConstraints;
104         return Geometry::verticalConstraintsForInFlow(geometryForBox(containingBlock));
105     };
106
107     // This is a post-order tree traversal layout.
108     // 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.
109     appendNextToLayoutQueue(formattingRoot, LayoutDirection::Child);
110     // 1. Go all the way down to the leaf node
111     // 2. Compute static position and width as we traverse down
112     // 3. As we climb back on the tree, compute height and finialize position
113     // (Any subtrees with new formatting contexts need to layout synchronously)
114     while (!layoutQueue.isEmpty()) {
115         // Traverse down on the descendants and compute width/static position until we find a leaf node.
116         while (true) {
117             auto& layoutBox = *layoutQueue.last();
118             auto horizontalConstraints = horizontalConstraintsForLayoutBox(layoutBox);
119             auto verticalConstraints = verticalConstraintsForLayoutBox(layoutBox);
120
121             computeBorderAndPadding(layoutBox, horizontalConstraints);
122             computeStaticVerticalPosition(layoutBox, verticalConstraints);
123
124             auto horizontalConstraintsPair = ConstraintsPair<HorizontalConstraints> { rootHorizontalConstraints, horizontalConstraints };
125             auto verticalConstraintsPair = ConstraintsPair<VerticalConstraints> { rootVerticalConstraints, verticalConstraints };
126             computeWidthAndMargin(floatingContext, layoutBox, horizontalConstraintsPair, verticalConstraintsPair);
127             computeStaticHorizontalPosition(layoutBox, horizontalConstraints);
128
129             if (layoutBox.establishesFormattingContext()) {
130                 if (is<ContainerBox>(layoutBox) && downcast<ContainerBox>(layoutBox).hasInFlowOrFloatingChild()) {
131                     auto& containerBox = downcast<ContainerBox>(layoutBox);
132                     if (containerBox.establishesInlineFormattingContext()) {
133                         // IFCs inherit floats from parent FCs. We need final vertical position to find intruding floats.
134                         precomputeVerticalPositionForBoxAndAncestors(containerBox, horizontalConstraintsPair, verticalConstraintsPair);
135                         if (containerBox.hasFloatClear()) {
136                             // Roots with clear set are special because they both inherit floats but avoid them the same time. 
137                             // If we just let the root sit at the pre-computed static vertical position, we might find unrelated
138                             // float boxes there (boxes that we need to clear).
139                             computeVerticalPositionForFloatClear(floatingContext, containerBox);
140                         }
141                     }
142                     auto& rootDisplayBox = geometryForBox(containerBox);
143                     auto horizontalConstraintsForInFlowContent = Geometry::horizontalConstraintsForInFlow(rootDisplayBox);
144                     auto verticalConstraintsForInFlowContent = Geometry::verticalConstraintsForInFlow(rootDisplayBox);
145                     // Layout the inflow descendants of this formatting context root.
146                     LayoutContext::createFormattingContext(containerBox, layoutState())->layoutInFlowContent(invalidationState, horizontalConstraintsForInFlowContent, verticalConstraintsForInFlowContent);
147                 }
148                 break;
149             }
150             if (!appendNextToLayoutQueue(layoutBox, LayoutDirection::Child))
151                 break;
152         }
153
154         // Climb back on the ancestors and compute height/final position.
155         while (!layoutQueue.isEmpty()) {
156             auto& layoutBox = *layoutQueue.takeLast();
157             auto horizontalConstraints = horizontalConstraintsForLayoutBox(layoutBox);
158             auto verticalConstraints = verticalConstraintsForLayoutBox(layoutBox);
159
160             // All inflow descendants (if there are any) are laid out by now. Let's compute the box's height.
161             computeHeightAndMargin(layoutBox, horizontalConstraints, verticalConstraints);
162
163             auto establishesFormattingContext = layoutBox.establishesFormattingContext(); 
164             if (establishesFormattingContext) {
165                 // Now that we computed the root's height, we can layout the out-of-flow descendants.
166                 if (is<ContainerBox>(layoutBox) && downcast<ContainerBox>(layoutBox).hasChild()) {
167                     auto& containerBox = downcast<ContainerBox>(layoutBox);
168                     auto& rootDisplayBox = geometryForBox(containerBox);
169                     auto horizontalConstraintsForOutOfFlowContent =  Geometry::horizontalConstraintsForOutOfFlow(rootDisplayBox);
170                     auto verticalConstraintsForOutOfFlowContent = Geometry::verticalConstraintsForOutOfFlow(rootDisplayBox);
171                     LayoutContext::createFormattingContext(containerBox, layoutState())->layoutOutOfFlowContent(invalidationState, horizontalConstraintsForOutOfFlowContent, verticalConstraintsForOutOfFlowContent);
172                 }
173             }
174             // Resolve final positions.
175             if (layoutBox.isFloatAvoider()) {
176                 auto horizontalConstraintsPair = ConstraintsPair<HorizontalConstraints> { rootHorizontalConstraints, horizontalConstraints };
177                 auto verticalConstraintsPair = ConstraintsPair<VerticalConstraints> { rootVerticalConstraints, verticalConstraints };
178                 computePositionToAvoidFloats(floatingContext, layoutBox, horizontalConstraintsPair, verticalConstraintsPair);
179                 if (layoutBox.isFloatingPositioned())
180                     floatingContext.append(layoutBox);
181             }
182             if (!establishesFormattingContext && is<ContainerBox>(layoutBox))
183                 placeInFlowPositionedChildren(downcast<ContainerBox>(layoutBox), horizontalConstraints);
184
185             if (appendNextToLayoutQueue(layoutBox, LayoutDirection::Sibling))
186                 break;
187         }
188     }
189     // Place the inflow positioned children.
190     placeInFlowPositionedChildren(formattingRoot, rootHorizontalConstraints);
191     LOG_WITH_STREAM(FormattingContextLayout, stream << "[End] -> block formatting context -> formatting root(" << &root() << ")");
192 }
193
194 Optional<LayoutUnit> BlockFormattingContext::usedAvailableWidthForFloatAvoider(const FloatingContext& floatingContext, const Box& layoutBox, const ConstraintsPair<HorizontalConstraints>& horizontalConstraints, const ConstraintsPair<VerticalConstraints>& verticalConstraints)
195 {
196     // Normally the available width for an in-flow block level box is the width of the containing block's content box.
197     // However (and can't find it anywhere in the spec) non-floating positioned float avoider block level boxes are constrained by existing floats.
198     ASSERT(layoutBox.isFloatAvoider());
199     if (floatingContext.isEmpty())
200         return { };
201     // Float clear pushes the block level box either below the floats, or just one side below but the other side could overlap.
202     // What it means is that the used available width always matches the containing block's constraint.
203     if (layoutBox.hasFloatClear())
204         return { };
205
206     ASSERT(layoutBox.establishesFormattingContext());
207     // Vertical static position is not computed yet for this formatting context root, so let's just pre-compute it for now.
208     precomputeVerticalPositionForBoxAndAncestors(layoutBox, horizontalConstraints, verticalConstraints);
209
210     auto mapLogicalTopToFormattingContextRoot = [&] {
211         auto& formattingContextRoot = root();
212         ASSERT(layoutBox.isInFormattingContextOf(formattingContextRoot));
213         auto top = geometryForBox(layoutBox).top();
214         for (auto* ancestor = &layoutBox.containingBlock(); ancestor != &formattingContextRoot; ancestor = &ancestor->containingBlock())
215             top += geometryForBox(*ancestor).top();
216         return top;
217     };
218
219     auto verticalPosition = mapLogicalTopToFormattingContextRoot();
220     // FIXME: Check if the non-yet-computed height affects this computation - and whether we have to resolve it at a later point.
221     auto constraints = floatingContext.constraints(verticalPosition, verticalPosition);
222     if (!constraints.left && !constraints.right)
223         return { };
224     // Shrink the available space if the floats are actually intruding at this vertical position.
225     auto availableWidth = horizontalConstraints.containingBlock.logicalWidth;
226     if (constraints.left)
227         availableWidth -= constraints.left->x;
228     if (constraints.right) {
229         // FIXME: Map the logicalRight to the root's coordinate system.
230         availableWidth -= std::max(0_lu, horizontalConstraints.containingBlock.logicalRight() - constraints.right->x);
231     }
232     return availableWidth;
233 }
234
235 void BlockFormattingContext::placeInFlowPositionedChildren(const ContainerBox& containerBox, const HorizontalConstraints& horizontalConstraints)
236 {
237     LOG_WITH_STREAM(FormattingContextLayout, stream << "Start: move in-flow positioned children -> parent: " << &containerBox);
238     for (auto& childBox : childrenOfType<Box>(containerBox)) {
239         if (!childBox.isInFlowPositioned())
240             continue;
241         auto positionOffset = geometry().inFlowPositionedPositionOffset(childBox, horizontalConstraints);
242         formattingState().displayBox(childBox).move(positionOffset);
243     }
244     LOG_WITH_STREAM(FormattingContextLayout, stream << "End: move in-flow positioned children -> parent: " << &containerBox);
245 }
246
247 void BlockFormattingContext::computeStaticVerticalPosition(const Box& layoutBox, const VerticalConstraints& verticalConstraints)
248 {
249     formattingState().displayBox(layoutBox).setTop(geometry().staticVerticalPosition(layoutBox, verticalConstraints));
250 }
251
252 void BlockFormattingContext::computeStaticHorizontalPosition(const Box& layoutBox, const HorizontalConstraints& horizontalConstraints)
253 {
254     formattingState().displayBox(layoutBox).setLeft(geometry().staticHorizontalPosition(layoutBox, horizontalConstraints));
255 }
256
257 void BlockFormattingContext::precomputeVerticalPositionForAncestors(const Box& layoutBox, const ConstraintsPair<HorizontalConstraints>& horizontalConstraints, const ConstraintsPair<VerticalConstraints>& verticalConstraints)
258 {
259     ASSERT(layoutBox.isFloatAvoider());
260     precomputeVerticalPositionForBoxAndAncestors(layoutBox.containingBlock(), horizontalConstraints, verticalConstraints);
261 }
262
263 void BlockFormattingContext::precomputeVerticalPositionForBoxAndAncestors(const Box& layoutBox, const ConstraintsPair<HorizontalConstraints>& horizontalConstraints, const ConstraintsPair<VerticalConstraints>& verticalConstraints)
264 {
265     // 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).
266     // In block formatting context the final position for a normal flow box includes
267     // 1. the static position and
268     // 2. the corresponding (non)collapsed margins.
269     // 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
270     // (and the height might be based on the content).
271     // 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.
272     //
273     // 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 position.
274     // FIXME: we currently don't account for the "clear" property when computing the final position for an ancestor.
275     for (auto* ancestor = &layoutBox; ancestor && ancestor != &root(); ancestor = &ancestor->containingBlock()) {
276         auto horizontalConstraintsForAncestor = [&] {
277             auto& containingBlock = ancestor->containingBlock();
278             return &containingBlock == &root() ? horizontalConstraints.root : Geometry::horizontalConstraintsForInFlow(geometryForBox(containingBlock));
279         };
280         auto verticalConstraintsForAncestor = [&] {
281             auto& containingBlock = ancestor->containingBlock();
282             return &containingBlock == &root() ? verticalConstraints.root : Geometry::verticalConstraintsForInFlow(geometryForBox(containingBlock));
283         };
284
285         auto computedVerticalMargin = geometry().computedVerticalMargin(*ancestor, horizontalConstraintsForAncestor());
286         auto usedNonCollapsedMargin = UsedVerticalMargin::NonCollapsedValues { computedVerticalMargin.before.valueOr(0), computedVerticalMargin.after.valueOr(0) };
287         auto precomputedMarginBefore = marginCollapse().precomputedMarginBefore(*ancestor, usedNonCollapsedMargin);
288         formattingState().setPositiveAndNegativeVerticalMargin(*ancestor, { precomputedMarginBefore.positiveAndNegativeMarginBefore, { } });
289
290         auto& displayBox = formattingState().displayBox(*ancestor);
291         auto nonCollapsedValues = UsedVerticalMargin::NonCollapsedValues { precomputedMarginBefore.nonCollapsedValue, { } };
292         auto collapsedValues = UsedVerticalMargin::CollapsedValues { precomputedMarginBefore.collapsedValue, { }, false };
293         auto verticalMargin = UsedVerticalMargin { nonCollapsedValues, collapsedValues };
294         displayBox.setVerticalMargin(verticalMargin);
295         displayBox.setTop(verticalPositionWithMargin(*ancestor, verticalMargin, verticalConstraintsForAncestor()));
296 #if ASSERT_ENABLED
297         setPrecomputedMarginBefore(*ancestor, precomputedMarginBefore);
298         displayBox.setHasPrecomputedMarginBefore();
299 #endif
300     }
301 }
302
303 void BlockFormattingContext::computePositionToAvoidFloats(const FloatingContext& floatingContext, const Box& layoutBox, const ConstraintsPair<HorizontalConstraints>& horizontalConstraints, const ConstraintsPair<VerticalConstraints>& verticalConstraints)
304 {
305     ASSERT(layoutBox.isFloatAvoider());
306     // In order to position a float avoider we need to know its vertical position relative to its formatting context root (and not just its containing block),
307     // because all the already-placed floats (floats that we are trying to avoid here) in this BFC might belong
308     // to a different set of containing blocks (but they all descendants of the BFC root).
309     // However according to the BFC rules, at this point of the layout flow we don't yet have computed vertical positions for the ancestors.
310     if (layoutBox.isFloatingPositioned()) {
311         precomputeVerticalPositionForAncestors(layoutBox, horizontalConstraints, verticalConstraints);
312         formattingState().displayBox(layoutBox).setTopLeft(floatingContext.positionForFloat(layoutBox, horizontalConstraints.containingBlock));
313         return;
314     }
315     // Non-float positioned float avoiders (formatting context roots and clear boxes) should be fine unless there are floats in this context.
316     if (floatingContext.isEmpty())
317         return;
318     precomputeVerticalPositionForAncestors(layoutBox, horizontalConstraints, verticalConstraints);
319     if (layoutBox.hasFloatClear())
320         return computeVerticalPositionForFloatClear(floatingContext, layoutBox);
321
322     ASSERT(layoutBox.establishesFormattingContext());
323     if (auto adjustedPosition = floatingContext.positionForFormattingContextRoot(layoutBox))
324         formattingState().displayBox(layoutBox).setTopLeft(*adjustedPosition);
325 }
326
327 void BlockFormattingContext::computeVerticalPositionForFloatClear(const FloatingContext& floatingContext, const Box& layoutBox)
328 {
329     ASSERT(layoutBox.hasFloatClear());
330     if (floatingContext.isEmpty())
331         return;
332     auto verticalPositionAndClearance = floatingContext.verticalPositionWithClearance(layoutBox);
333     if (!verticalPositionAndClearance.position) {
334         ASSERT(!verticalPositionAndClearance.clearance);
335         return;
336     }
337
338     auto& displayBox = formattingState().displayBox(layoutBox);
339     ASSERT(*verticalPositionAndClearance.position >= displayBox.top());
340     displayBox.setTop(*verticalPositionAndClearance.position);
341     if (verticalPositionAndClearance.clearance)
342         displayBox.setHasClearance();
343     // FIXME: Reset the margin values on the ancestors/previous siblings now that the float avoider with clearance does not margin collapse anymore.
344 }
345
346 void BlockFormattingContext::computeWidthAndMargin(const FloatingContext& floatingContext, const Box& layoutBox, const ConstraintsPair<HorizontalConstraints>& horizontalConstraintsPair, const ConstraintsPair<VerticalConstraints>& verticalConstraintsPair)
347 {
348     auto& horizontalConstraints = horizontalConstraintsPair.containingBlock; 
349     auto compute = [&](Optional<LayoutUnit> usedWidth) -> ContentWidthAndMargin {
350         if (layoutBox.isFloatingPositioned())
351             return geometry().floatingWidthAndMargin(layoutBox, horizontalConstraints, { usedWidth, { } });
352
353         if (layoutBox.isFloatAvoider()) {
354             auto availableWidth = horizontalConstraints.logicalWidth;
355             if (layoutBox.style().logicalWidth().isAuto())
356                 availableWidth = usedAvailableWidthForFloatAvoider(floatingContext, layoutBox, horizontalConstraintsPair, verticalConstraintsPair).valueOr(availableWidth);
357             return geometry().inFlowWidthAndMargin(layoutBox, { horizontalConstraints.logicalLeft, availableWidth }, { usedWidth, { } });
358         }
359
360         if (layoutBox.isInFlow())
361             return geometry().inFlowWidthAndMargin(layoutBox, horizontalConstraints, { usedWidth, { } });
362
363         ASSERT_NOT_REACHED();
364         return { };
365     };
366
367     auto contentWidthAndMargin = compute({ });
368
369     auto availableWidth = horizontalConstraints.logicalWidth;
370     if (auto maxWidth = geometry().computedMaxWidth(layoutBox, availableWidth)) {
371         auto maxWidthAndMargin = compute(maxWidth);
372         if (contentWidthAndMargin.contentWidth > maxWidthAndMargin.contentWidth)
373             contentWidthAndMargin = maxWidthAndMargin;
374     }
375
376     auto minWidth = geometry().computedMinWidth(layoutBox, availableWidth).valueOr(0);
377     auto minWidthAndMargin = compute(minWidth);
378     if (contentWidthAndMargin.contentWidth < minWidthAndMargin.contentWidth)
379         contentWidthAndMargin = minWidthAndMargin;
380
381     auto& displayBox = formattingState().displayBox(layoutBox);
382     displayBox.setContentBoxWidth(contentWidthAndMargin.contentWidth);
383     displayBox.setHorizontalMargin(contentWidthAndMargin.usedMargin);
384     displayBox.setHorizontalComputedMargin(contentWidthAndMargin.computedMargin);
385 }
386
387 void BlockFormattingContext::computeHeightAndMargin(const Box& layoutBox, const HorizontalConstraints& horizontalConstraints, const VerticalConstraints& verticalConstraints)
388 {
389     auto compute = [&](Optional<LayoutUnit> usedHeight) -> ContentHeightAndMargin {
390         if (layoutBox.isInFlow())
391             return geometry().inFlowHeightAndMargin(layoutBox, horizontalConstraints, { usedHeight });
392
393         if (layoutBox.isFloatingPositioned())
394             return geometry().floatingHeightAndMargin(layoutBox, horizontalConstraints, { usedHeight });
395
396         ASSERT_NOT_REACHED();
397         return { };
398     };
399
400     auto contentHeightAndMargin = compute({ });
401     if (auto maxHeight = geometry().computedMaxHeight(layoutBox)) {
402         if (contentHeightAndMargin.contentHeight > *maxHeight) {
403             auto maxHeightAndMargin = compute(maxHeight);
404             // Used height should remain the same.
405             ASSERT((layoutState().inQuirksMode() && (layoutBox.isBodyBox() || layoutBox.isDocumentBox())) || maxHeightAndMargin.contentHeight == *maxHeight);
406             contentHeightAndMargin = { *maxHeight, maxHeightAndMargin.nonCollapsedMargin };
407         }
408     }
409
410     if (auto minHeight = geometry().computedMinHeight(layoutBox)) {
411         if (contentHeightAndMargin.contentHeight < *minHeight) {
412             auto minHeightAndMargin = compute(minHeight);
413             // Used height should remain the same.
414             ASSERT((layoutState().inQuirksMode() && (layoutBox.isBodyBox() || layoutBox.isDocumentBox())) || minHeightAndMargin.contentHeight == *minHeight);
415             contentHeightAndMargin = { *minHeight, minHeightAndMargin.nonCollapsedMargin };
416         }
417     }
418
419     // 1. Compute collapsed margins.
420     // 2. Adjust vertical position using the collapsed values
421     // 3. Adjust previous in-flow sibling margin after using this margin.
422     auto marginCollapse = this->marginCollapse();
423     auto collapsedAndPositiveNegativeValues = marginCollapse.collapsedVerticalValues(layoutBox, contentHeightAndMargin.nonCollapsedMargin);
424     // Cache the computed positive and negative margin value pair.
425     formattingState().setPositiveAndNegativeVerticalMargin(layoutBox, collapsedAndPositiveNegativeValues.positiveAndNegativeVerticalValues);
426     auto verticalMargin = UsedVerticalMargin { contentHeightAndMargin.nonCollapsedMargin, collapsedAndPositiveNegativeValues.collapsedValues };
427
428     // Out of flow boxes don't need vertical adjustment after margin collapsing.
429     if (layoutBox.isOutOfFlowPositioned()) {
430         ASSERT(!hasPrecomputedMarginBefore(layoutBox));
431         auto& displayBox = formattingState().displayBox(layoutBox);
432         displayBox.setContentBoxHeight(contentHeightAndMargin.contentHeight);
433         displayBox.setVerticalMargin(verticalMargin);
434         return;
435     }
436
437 #if ASSERT_ENABLED
438     if (hasPrecomputedMarginBefore(layoutBox) && precomputedMarginBefore(layoutBox).usedValue() != verticalMargin.before()) {
439         // When the pre-computed margin turns out to be incorrect, we need to re-layout this subtree with the correct margin values.
440         // <div style="float: left"></div>
441         // <div>
442         //   <div style="margin-bottom: 200px"></div>
443         // </div>
444         // The float box triggers margin before computation on the ancestor chain to be able to intersect with other floats in the same floating context.
445         // However in some cases the parent margin-top collapses with some next siblings (nephews) and there's no way to be able to properly
446         // account for that without laying out every node in the FC (in the example, the margin-bottom pushes down the float).
447         ASSERT_NOT_IMPLEMENTED_YET();
448     }
449 #endif
450     auto& displayBox = formattingState().displayBox(layoutBox);
451     displayBox.setTop(verticalPositionWithMargin(layoutBox, verticalMargin, verticalConstraints));
452     displayBox.setContentBoxHeight(contentHeightAndMargin.contentHeight);
453     displayBox.setVerticalMargin(verticalMargin);
454     // Adjust the previous sibling's margin bottom now that this box's vertical margin is computed.
455     MarginCollapse::updateMarginAfterForPreviousSibling(*this, marginCollapse, layoutBox);
456 }
457
458 FormattingContext::IntrinsicWidthConstraints BlockFormattingContext::computedIntrinsicWidthConstraints()
459 {
460     auto& formattingState = this->formattingState();
461     ASSERT(!formattingState.intrinsicWidthConstraints());
462
463     // Visit the in-flow descendants and compute their min/max intrinsic width if needed.
464     // 1. Go all the way down to the leaf node
465     // 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)
466     // 3. As we climb back on the tree, compute min/max intrinsic width
467     // (Any subtrees with new formatting contexts need to layout synchronously)
468     Vector<const Box*> queue;
469     if (root().hasInFlowOrFloatingChild())
470         queue.append(root().firstInFlowOrFloatingChild());
471
472     IntrinsicWidthConstraints constraints;
473     while (!queue.isEmpty()) {
474         while (true) {
475             auto& layoutBox = *queue.last();
476             auto hasInFlowOrFloatingChild = is<ContainerBox>(layoutBox) && downcast<ContainerBox>(layoutBox).hasInFlowOrFloatingChild();
477             auto skipDescendants = formattingState.intrinsicWidthConstraintsForBox(layoutBox) || !hasInFlowOrFloatingChild || layoutBox.establishesFormattingContext() || layoutBox.style().width().isFixed();
478             if (skipDescendants)
479                 break;
480             queue.append(downcast<ContainerBox>(layoutBox).firstInFlowOrFloatingChild());
481         }
482         // Compute min/max intrinsic width bottom up if needed.
483         while (!queue.isEmpty()) {
484             auto& layoutBox = *queue.takeLast();
485             auto desdendantConstraints = formattingState.intrinsicWidthConstraintsForBox(layoutBox); 
486             if (!desdendantConstraints) {
487                 desdendantConstraints = geometry().intrinsicWidthConstraints(layoutBox);
488                 formattingState.setIntrinsicWidthConstraintsForBox(layoutBox, *desdendantConstraints);
489             }
490             constraints.minimum = std::max(constraints.minimum, desdendantConstraints->minimum);
491             constraints.maximum = std::max(constraints.maximum, desdendantConstraints->maximum);
492             // Move over to the next sibling or take the next box in the queue.
493             if (auto* nextSibling = layoutBox.nextInFlowOrFloatingSibling()) {
494                 queue.append(nextSibling);
495                 break;
496             }
497         }
498     }
499     formattingState.setIntrinsicWidthConstraints(constraints);
500     return constraints;
501 }
502
503 LayoutUnit BlockFormattingContext::verticalPositionWithMargin(const Box& layoutBox, const UsedVerticalMargin& verticalMargin,  const VerticalConstraints& verticalConstraints) const
504 {
505     ASSERT(!layoutBox.isOutOfFlowPositioned());
506     // Now that we've computed the final margin before, let's shift the box's vertical position if needed.
507     // 1. Check if the box has clearance. If so, we've already precomputed/finalized the top value and vertical margin does not impact it anymore.
508     // 2. Check if the margin before collapses with the previous box's margin after. if not -> return previous box's bottom including margin after + marginBefore
509     // 3. Check if the previous box's margins collapse through. If not -> return previous box' bottom excluding margin after + marginBefore (they are supposed to be equal)
510     // 4. Go to previous box and start from step #1 until we hit the parent box.
511     auto& boxGeometry = geometryForBox(layoutBox);
512     if (boxGeometry.hasClearance())
513         return boxGeometry.top();
514
515     auto* currentLayoutBox = &layoutBox;
516     while (currentLayoutBox) {
517         if (!currentLayoutBox->previousInFlowSibling())
518             break;
519         auto& previousInFlowSibling = *currentLayoutBox->previousInFlowSibling();
520         if (!marginCollapse().marginBeforeCollapsesWithPreviousSiblingMarginAfter(*currentLayoutBox)) {
521             auto& previousBoxGeometry = geometryForBox(previousInFlowSibling);
522             return previousBoxGeometry.rectWithMargin().bottom() + verticalMargin.before();
523         }
524
525         if (!marginCollapse().marginsCollapseThrough(previousInFlowSibling)) {
526             auto& previousBoxGeometry = geometryForBox(previousInFlowSibling);
527             return previousBoxGeometry.bottom() + verticalMargin.before();
528         }
529         currentLayoutBox = &previousInFlowSibling;
530     }
531
532     auto containingBlockContentBoxTop = verticalConstraints.logicalTop;
533     // Adjust vertical position depending whether this box directly or indirectly adjoins with its parent.
534     auto directlyAdjoinsParent = !layoutBox.previousInFlowSibling();
535     if (directlyAdjoinsParent) {
536         // If the top and bottom margins of a box are adjoining, then it is possible for margins to collapse through it.
537         // In this case, the position of the element depends on its relationship with the other elements whose margins are being collapsed.
538         if (verticalMargin.collapsedValues().isCollapsedThrough) {
539             // If the element's margins are collapsed with its parent's top margin, the top border edge of the box is defined to be the same as the parent's.
540             if (marginCollapse().marginBeforeCollapsesWithParentMarginBefore(layoutBox))
541                 return containingBlockContentBoxTop;
542             // Otherwise, either the element's parent is not taking part in the margin collapsing, or only the parent's bottom margin is involved.
543             // The position of the element's top border edge is the same as it would have been if the element had a non-zero bottom border.
544             auto beforeMarginWithBottomBorder = marginCollapse().marginBeforeIgnoringCollapsingThrough(layoutBox, verticalMargin.nonCollapsedValues());
545             return containingBlockContentBoxTop + beforeMarginWithBottomBorder;
546         }
547         // Non-collapsed through box vertical position depending whether the margin collapses.
548         if (marginCollapse().marginBeforeCollapsesWithParentMarginBefore(layoutBox))
549             return containingBlockContentBoxTop;
550
551         return containingBlockContentBoxTop + verticalMargin.before();
552     }
553     // At this point this box indirectly (via collapsed through previous in-flow siblings) adjoins the parent. Let's check if it margin collapses with the parent.
554     auto& containingBlock = layoutBox.containingBlock();
555     ASSERT(containingBlock.firstInFlowChild());
556     ASSERT(containingBlock.firstInFlowChild() != &layoutBox);
557     if (marginCollapse().marginBeforeCollapsesWithParentMarginBefore(*containingBlock.firstInFlowChild()))
558         return containingBlockContentBoxTop;
559
560     return containingBlockContentBoxTop + verticalMargin.before();
561 }
562
563 }
564 }
565
566 #endif