[LFC][IFC] Make InlineFormattingContext::collectInlineContent non-recursive.
authorzalan@apple.com <zalan@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 4 Feb 2019 15:49:24 +0000 (15:49 +0000)
committerzalan@apple.com <zalan@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 4 Feb 2019 15:49:24 +0000 (15:49 +0000)
https://bugs.webkit.org/show_bug.cgi?id=194210

Reviewed by Antti Koivisto.

Use iterative algorithm to collect inline content (and add breaking rules).
This is in preparation for fixing the inline preferred width computation.

* layout/Verification.cpp:
(WebCore::Layout::resolveForRelativePositionIfNeeded):
* layout/inlineformatting/InlineFormattingContext.cpp:
(WebCore::Layout::addDetachingRules):
(WebCore::Layout::createAndAppendInlineItem):
(WebCore::Layout::InlineFormattingContext::collectInlineContent const):
(WebCore::Layout::InlineFormattingContext::collectInlineContentForSubtree const): Deleted.
* layout/inlineformatting/InlineFormattingContext.h:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@240924 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/ChangeLog
Source/WebCore/layout/Verification.cpp
Source/WebCore/layout/inlineformatting/InlineFormattingContext.cpp
Source/WebCore/layout/inlineformatting/InlineFormattingContext.h

index a7bacb6..02b62d4 100644 (file)
@@ -1,3 +1,22 @@
+2019-02-04  Zalan Bujtas  <zalan@apple.com>
+
+        [LFC][IFC] Make InlineFormattingContext::collectInlineContent non-recursive.
+        https://bugs.webkit.org/show_bug.cgi?id=194210
+
+        Reviewed by Antti Koivisto.
+
+        Use iterative algorithm to collect inline content (and add breaking rules).
+        This is in preparation for fixing the inline preferred width computation.  
+
+        * layout/Verification.cpp:
+        (WebCore::Layout::resolveForRelativePositionIfNeeded):
+        * layout/inlineformatting/InlineFormattingContext.cpp:
+        (WebCore::Layout::addDetachingRules):
+        (WebCore::Layout::createAndAppendInlineItem):
+        (WebCore::Layout::InlineFormattingContext::collectInlineContent const):
+        (WebCore::Layout::InlineFormattingContext::collectInlineContentForSubtree const): Deleted.
+        * layout/inlineformatting/InlineFormattingContext.h:
+
 2019-02-04  Michael Catanzaro  <mcatanzaro@igalia.com>
 
         Unreviewed, fix unused variable warnings introduced in r240912
index 361c478..2e77c39 100644 (file)
@@ -133,7 +133,7 @@ static LayoutUnit resolveForRelativePositionIfNeeded(const InlineTextBox& inline
     while (is<InlineFlowBox>(parent)) {
         auto& renderer = parent->renderer();
         if (renderer.isInFlowPositioned())
-            xOffset = downcast<RenderInline>(renderer).offsetForInFlowPosition().width();
+            xOffset = renderer.offsetForInFlowPosition().width();
         parent = parent->parent();
     }
     return xOffset;
index 96f01ea..78f34f8 100644 (file)
@@ -430,98 +430,132 @@ void InlineFormattingContext::placeInFlowPositionedChildren(unsigned fistRunInde
     }
 }
 
-void InlineFormattingContext::collectInlineContentForSubtree(const Box& root, InlineRunProvider& inlineRunProvider) const
+static void addDetachingRules(InlineItem& inlineItem, Optional<LayoutUnit> nonBreakableStartWidth, Optional<LayoutUnit> nonBreakableEndWidth)
 {
-    // Collect inline content recursively and set breaking rules for the inline elements (for paddings, margins, positioned element etc).
-    auto& inlineFormattingState = formattingState();
-
-    auto createAndAppendInlineItem = [&] {
-        auto inlineItem = std::make_unique<InlineItem>(root);
-        inlineRunProvider.append(*inlineItem);
-        inlineFormattingState.inlineContent().add(WTFMove(inlineItem));
-    };
+    OptionSet<InlineItem::DetachingRule> detachingRules;
+    if (nonBreakableStartWidth) {
+        detachingRules.add(InlineItem::DetachingRule::BreakAtStart);
+        inlineItem.addNonBreakableStart(*nonBreakableStartWidth);
+    }
+    if (nonBreakableEndWidth) {
+        detachingRules.add(InlineItem::DetachingRule::BreakAtEnd);
+        inlineItem.addNonBreakableEnd(*nonBreakableEndWidth);
+    }
+    inlineItem.addDetachingRule(detachingRules);
+}
 
-    if (root.establishesFormattingContext() && &root != &(this->root())) {
-        createAndAppendInlineItem();
-        auto& inlineRun = *inlineFormattingState.inlineContent().last();
-        auto computedHorizontalMargin = Geometry::computedHorizontalMargin(layoutState(), root);
-        auto horizontalMargin = UsedHorizontalMargin { computedHorizontalMargin.start.valueOr(0), computedHorizontalMargin.end.valueOr(0) };
+static InlineItem& createAndAppendInlineItem(InlineRunProvider& inlineRunProvider, InlineContent& inlineContent, const Box& layoutBox)
+{
+    ASSERT(layoutBox.isInlineLevelBox() || layoutBox.isFloatingPositioned());
+    auto inlineItem = std::make_unique<InlineItem>(layoutBox);
+    auto* inlineItemPtr = inlineItem.get();
+    inlineContent.add(WTFMove(inlineItem));
+    inlineRunProvider.append(*inlineItemPtr);
+    return *inlineItemPtr;
+}
 
-        inlineRun.addDetachingRule({ InlineItem::DetachingRule::BreakAtStart, InlineItem::DetachingRule::BreakAtEnd });
-        inlineRun.addNonBreakableStart(horizontalMargin.start);
-        inlineRun.addNonBreakableEnd(horizontalMargin.end);
-        // Skip formatting root subtree. They are not part of this inline formatting context.
+void InlineFormattingContext::collectInlineContent(InlineRunProvider& inlineRunProvider) const
+{
+    if (!is<Container>(root()))
         return;
-    }
-
-    if (!is<Container>(root)) {
-        createAndAppendInlineItem();
+    auto& root = downcast<Container>(this->root());
+    if (!root.hasInFlowOrFloatingChild())
         return;
-    }
+    // The logic here is very similar to BFC layout.
+    // 1. Travers down the layout tree and collect "start" unbreakable widths (margin-left, border-left, padding-left)
+    // 2. Create InlineItem per leaf inline box (text nodes, inline-blocks, floats) and set "start" unbreakable width on them. 
+    // 3. Climb back and collect "end" unbreakable width and set it on the last InlineItem.
+    auto& layoutState = this->layoutState();
+    auto& inlineContent = formattingState().inlineContent();
 
-    auto* lastInlineBoxBeforeContainer = inlineFormattingState.lastInlineItem();
-    auto* child = downcast<Container>(root).firstInFlowOrFloatingChild();
-    while (child) {
-        collectInlineContentForSubtree(*child, inlineRunProvider);
-        child = child->nextInFlowOrFloatingSibling();
-    }
+    enum class NonBreakableWidthType { Start, End };
+    auto nonBreakableWidth = [&](auto& container, auto type) {
+        auto computedHorizontalMargin = Geometry::computedHorizontalMargin(layoutState, container);
+        auto horizontalMargin = UsedHorizontalMargin { computedHorizontalMargin.start.valueOr(0), computedHorizontalMargin.end.valueOr(0) };
+        auto border = Geometry::computedBorder(layoutState, container);
+        auto padding = Geometry::computedPadding(layoutState, container);
 
-    // FIXME: Revisit this when we figured out how inline boxes fit the display tree.
-    auto padding = Geometry::computedPadding(layoutState(), root);
-    auto border = Geometry::computedBorder(layoutState(), root);
-    auto computedHorizontalMargin = Geometry::computedHorizontalMargin(layoutState(), root);
-    auto horizontalMargin = UsedHorizontalMargin { computedHorizontalMargin.start.valueOr(0), computedHorizontalMargin.end.valueOr(0) };
+        if (type == NonBreakableWidthType::Start)
+            return border.horizontal.left + horizontalMargin.start + (padding ? padding->horizontal.left : LayoutUnit());
+        return border.horizontal.right + horizontalMargin.end + (padding ? padding->horizontal.right : LayoutUnit());
+    };
 
-    // Setup breaking boundaries for this subtree.
-    auto* lastDescendantInlineBox = inlineFormattingState.lastInlineItem();
-    // Empty container?
-    if (lastInlineBoxBeforeContainer == lastDescendantInlineBox)
-        return;
+    LayoutQueue layoutQueue;
+    layoutQueue.append(root.firstInFlowOrFloatingChild());
+
+    Optional<LayoutUnit> nonBreakableStartWidth;
+    Optional<LayoutUnit> nonBreakableEndWidth;
+    InlineItem* lastInlineItem = nullptr;
+    while (!layoutQueue.isEmpty()) {
+        while (true) {
+            auto& layoutBox = *layoutQueue.last();
+            if (!is<Container>(layoutBox))
+                break;
+            auto& container = downcast<Container>(layoutBox);
+
+            if (container.establishesFormattingContext()) {
+                // Formatting contexts are treated as leaf nodes.
+                auto& inlineItem = createAndAppendInlineItem(inlineRunProvider, inlineContent, container);
+                auto computedHorizontalMargin = Geometry::computedHorizontalMargin(layoutState, container);
+                auto currentNonBreakableStartWidth = nonBreakableStartWidth.valueOr(0) + computedHorizontalMargin.start.valueOr(0) + nonBreakableEndWidth.valueOr(0);
+                addDetachingRules(inlineItem, currentNonBreakableStartWidth, computedHorizontalMargin.end);
+                nonBreakableStartWidth = { };
+                nonBreakableEndWidth = { };
+
+                // Formatting context roots take care of their subtrees. Continue with next sibling if exists.
+                layoutQueue.removeLast();
+                if (!container.nextInFlowOrFloatingSibling())
+                    break;
+                layoutQueue.append(container.nextInFlowOrFloatingSibling());
+                continue;
+            }
 
-    auto rootBreaksAtStart = [&] {
-        if (&root == &(this->root()))
-            return false;
-        return (padding && padding->horizontal.left) || border.horizontal.left || horizontalMargin.start || root.isPositioned();
-    };
+            // Check if this non-formatting context container has any non-breakable start properties (margin-left, border-left, padding-left)
+            // <span style="padding-left: 5px"><span style="padding-left: 5px">foobar</span></span> -> 5px + 5px
+            auto currentNonBreakableStartWidth = nonBreakableWidth(layoutBox, NonBreakableWidthType::Start);
+            if (currentNonBreakableStartWidth || layoutBox.isPositioned())
+                nonBreakableStartWidth = nonBreakableStartWidth.valueOr(0) + currentNonBreakableStartWidth;
 
-    auto rootBreaksAtEnd = [&] {
-        if (&root == &(this->root()))
-            return false;
-        return (padding && padding->horizontal.right) || border.horizontal.right || horizontalMargin.end || root.isPositioned();
-    };
+            if (!container.hasInFlowOrFloatingChild())
+                break;
+            layoutQueue.append(container.firstInFlowOrFloatingChild());
+        }
 
-    if (rootBreaksAtStart()) {
-        InlineItem* firstDescendantInlineBox = nullptr;
-        auto& inlineContent = inlineFormattingState.inlineContent();
-
-        if (lastInlineBoxBeforeContainer) {
-            auto iterator = inlineContent.find(lastInlineBoxBeforeContainer);
-            firstDescendantInlineBox = (*++iterator).get();
-        } else
-            firstDescendantInlineBox = inlineContent.first().get();
-
-        ASSERT(firstDescendantInlineBox);
-        firstDescendantInlineBox->addDetachingRule(InlineItem::DetachingRule::BreakAtStart);
-        auto startOffset = border.horizontal.left + horizontalMargin.start;
-        if (padding)
-            startOffset += padding->horizontal.left;
-        firstDescendantInlineBox->addNonBreakableStart(startOffset);
-    }
+        while (!layoutQueue.isEmpty()) {
+            auto& layoutBox = *layoutQueue.takeLast();
+            if (is<Container>(layoutBox)) {
+                // This is the end of an inline container. Compute the non-breakable end width and add it to the last inline box.
+                // <span style="padding-right: 5px">foobar</span> -> 5px; last inline item -> "foobar"
+                auto currentNonBreakableEndWidth = nonBreakableWidth(layoutBox, NonBreakableWidthType::End);
+                if (currentNonBreakableEndWidth || layoutBox.isPositioned())
+                    nonBreakableEndWidth = nonBreakableEndWidth.valueOr(0) + currentNonBreakableEndWidth;
+                // Add it to the last inline box
+                if (lastInlineItem) {
+                    addDetachingRules(*lastInlineItem, { }, nonBreakableEndWidth);
+                    nonBreakableEndWidth = { };
+                }
+            } else {
+                // Leaf inline box
+                auto& inlineItem = createAndAppendInlineItem(inlineRunProvider, inlineContent, layoutBox);
+                // Add start and the (through empty containers) accumulated end width.
+                // <span style="padding-left: 1px">foobar</span> -> nonBreakableStartWidth: 1px;
+                // <span style="padding: 5px"></span>foobar -> nonBreakableStartWidth: 5px; nonBreakableEndWidth: 5px
+                if (nonBreakableStartWidth || nonBreakableEndWidth) {
+                    addDetachingRules(inlineItem, nonBreakableStartWidth.valueOr(0) + nonBreakableEndWidth.valueOr(0), { });
+                    nonBreakableStartWidth = { };
+                    nonBreakableEndWidth = { };
+                }
+                lastInlineItem = &inlineItem;
+            }
 
-    if (rootBreaksAtEnd()) {
-        lastDescendantInlineBox->addDetachingRule(InlineItem::DetachingRule::BreakAtEnd);
-        auto endOffset = border.horizontal.right + horizontalMargin.end;
-        if (padding)
-            endOffset += padding->horizontal.right;
-        lastDescendantInlineBox->addNonBreakableEnd(endOffset);
+            if (auto* nextSibling = layoutBox.nextInFlowOrFloatingSibling()) {
+                layoutQueue.append(nextSibling);
+                break;
+            }
+        }
     }
 }
 
-void InlineFormattingContext::collectInlineContent(InlineRunProvider& inlineRunProvider) const
-{
-    collectInlineContentForSubtree(root(), inlineRunProvider);
-}
-
 FormattingContext::InstrinsicWidthConstraints InlineFormattingContext::instrinsicWidthConstraints() const
 {
     auto& formattingStateForRoot = layoutState().formattingStateForBox(root());
index 99f282f..3f7cd3f 100644 (file)
@@ -118,7 +118,6 @@ private:
     void placeInFlowPositionedChildren(unsigned firstRunIndex) const;
 
     void collectInlineContent(InlineRunProvider&) const;
-    void collectInlineContentForSubtree(const Box& root, InlineRunProvider&) const;
     InstrinsicWidthConstraints instrinsicWidthConstraints() const override;
 
     InlineFormattingState& formattingState() const { return downcast<InlineFormattingState>(FormattingContext::formattingState()); }