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