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