[LFC][IFC] Construct dedicated runs when the inline element requires it (part 2)
authorzalan@apple.com <zalan@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 14 Nov 2018 15:31:17 +0000 (15:31 +0000)
committerzalan@apple.com <zalan@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 14 Nov 2018 15:31:17 +0000 (15:31 +0000)
https://bugs.webkit.org/show_bug.cgi?id=191623

Reviewed by Antti Koivisto.

This patch expands the breaking behaviour to support separate start/end breaks.

<span>parent </span><span style="padding: 10px;">start<span> middle </span>end</span><span> parent</span>

input to line breaking -> <parent start middle end parent>
output of line breaking (considering infinite constraint) -> <parent start middle end parent>
due to padding, final runs -> <parent><start middle end><parent>

"parent" -> n/a
"start" -> BreakAtStart
" middle " -> n/a
"end" -> BreakAtEnd
"parent" -> n/a

Another example:
<span>parent </span><span style="padding-right: 10px;">start<span> middle </span>end</span><span> parent</span>

line breaking -> <parent start middle end parent>
due to padding-right, final runs -> <parent start middle end><parent>

"parent" -> n/a
"start" -> n/a
" middle " -> n/a
"end" -> BreakAtEnd
"parent" -> n/a

* layout/inlineformatting/InlineFormattingContext.cpp:
(WebCore::Layout::InlineFormattingContext::splitInlineRunIfNeeded const):
(WebCore::Layout::InlineFormattingContext::collectInlineContent const): Move to a recursive algorithm (which is fine, inline contents don't tend to be too deep)
(WebCore::Layout::InlineFormattingContext::contentRequiresSeparateRun const): Deleted.
* layout/inlineformatting/InlineFormattingContext.h:
* layout/inlineformatting/InlineFormattingState.cpp:
(WebCore::Layout::InlineFormattingState::detachingRules const):
* layout/inlineformatting/InlineFormattingState.h:
(WebCore::Layout::InlineFormattingState::lastInlineItem const):
(WebCore::Layout::InlineFormattingState::addDetachingRule):

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

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

index e34b767..702d9d9 100644 (file)
@@ -1,3 +1,47 @@
+2018-11-13  Zalan Bujtas  <zalan@apple.com>
+
+        [LFC][IFC] Construct dedicated runs when the inline element requires it (part 2)
+        https://bugs.webkit.org/show_bug.cgi?id=191623
+
+        Reviewed by Antti Koivisto.
+
+        This patch expands the breaking behaviour to support separate start/end breaks.
+
+        <span>parent </span><span style="padding: 10px;">start<span> middle </span>end</span><span> parent</span>
+
+        input to line breaking -> <parent start middle end parent>
+        output of line breaking (considering infinite constraint) -> <parent start middle end parent>
+        due to padding, final runs -> <parent><start middle end><parent>
+
+        "parent" -> n/a
+        "start" -> BreakAtStart
+        " middle " -> n/a
+        "end" -> BreakAtEnd
+        "parent" -> n/a
+
+        Another example:
+        <span>parent </span><span style="padding-right: 10px;">start<span> middle </span>end</span><span> parent</span>
+
+        line breaking -> <parent start middle end parent>
+        due to padding-right, final runs -> <parent start middle end><parent>
+
+        "parent" -> n/a
+        "start" -> n/a
+        " middle " -> n/a
+        "end" -> BreakAtEnd
+        "parent" -> n/a
+
+        * layout/inlineformatting/InlineFormattingContext.cpp:
+        (WebCore::Layout::InlineFormattingContext::splitInlineRunIfNeeded const):
+        (WebCore::Layout::InlineFormattingContext::collectInlineContent const): Move to a recursive algorithm (which is fine, inline contents don't tend to be too deep)
+        (WebCore::Layout::InlineFormattingContext::contentRequiresSeparateRun const): Deleted.
+        * layout/inlineformatting/InlineFormattingContext.h:
+        * layout/inlineformatting/InlineFormattingState.cpp:
+        (WebCore::Layout::InlineFormattingState::detachingRules const):
+        * layout/inlineformatting/InlineFormattingState.h:
+        (WebCore::Layout::InlineFormattingState::lastInlineItem const):
+        (WebCore::Layout::InlineFormattingState::addDetachingRule):
+
 2018-11-14  Youenn Fablet  <youenn@apple.com>
 
         Add support for RTCRtpCodecParameters.sdpFmtpLine
index 784e11f..10a0f82 100644 (file)
@@ -125,16 +125,6 @@ void InlineFormattingContext::initializeNewLine(Line& line) const
     line.init(logicalRect);
 }
 
-bool InlineFormattingContext::contentRequiresSeparateRun(const InlineItem& inlineItem) const
-{
-    // FIXME: This is way too inefficient. We should pre-mark the runs instead while flattening the inline formatting context.
-    for (auto* inlineContainer = inlineItem.layoutBox().parent(); inlineContainer != &root(); inlineContainer = inlineContainer->parent()) {
-        if (inlineContainer->isPositioned())
-            return true;
-    }
-    return false;
-}
-
 void InlineFormattingContext::splitInlineRunIfNeeded(const InlineRun& inlineRun, InlineRuns& splitRuns) const
 {
     if (!inlineRun.overlapsMultipleInlineItems())
@@ -148,7 +138,7 @@ void InlineFormattingContext::splitInlineRunIfNeeded(const InlineRun& inlineRun,
 
     // 1. Start with the first inline item (element) and travers the list until
     // 2. either find an inline item that needs a dedicated run or we reach the end of the run
-    // 3. Shrink the original inline run and create a new one.
+    // 3. Create dedicate inline runs.
     auto& inlineContent = inlineFormattingState().inlineContent();
     auto textUtil = TextUtil { inlineContent };
 
@@ -170,28 +160,56 @@ void InlineFormattingContext::splitInlineRunIfNeeded(const InlineRun& inlineRun,
     for (auto iterator = inlineContent.find<const InlineItem&, InlineItemHashTranslator>(inlineRun.inlineItem()); iterator != inlineContent.end() && remaningLength > 0; ++iterator) {
         auto& inlineItem = **iterator;
 
-        if (!contentRequiresSeparateRun(inlineItem)) {
-            uncommittedLength += std::min(remaningLength, inlineItem.textContent().length() - startPosition);
+        auto currentLength = [&] {
+            return std::min(remaningLength, inlineItem.textContent().length() - startPosition);
+        };
+
+        // 1. Inline element does not require run breaking -> add current inline element to uncommitted. Jump to the next element.
+        // 2. Break at the beginning of the inline element -> commit what we've got so far. Current element becomes the first uncommitted.
+        // 3. Break at the end of the inline element -> commit what we've got so far including the current element.
+        // 4. Break before/after -> requires dedicated run -> commit what we've got so far and also commit the current inline element as a separate inline run.
+        auto detachingRules = inlineFormattingState().detachingRules(inlineItem.layoutBox());
+
+        // #1
+        if (!detachingRules) {
+            uncommittedLength += currentLength();
             firstUncommittedInlineItem = !firstUncommittedInlineItem ? &inlineItem : firstUncommittedInlineItem;
             continue;
         }
 
-        // Commit the items that don't need dedicated run.
-        if (firstUncommittedInlineItem) {
+        auto commit = [&] {
+            if (!firstUncommittedInlineItem)
+                return;
+
             contentStart = split(*firstUncommittedInlineItem, startPosition, uncommittedLength, contentStart);
 
             remaningLength -= uncommittedLength;
             startPosition = 0;
             uncommittedLength = 0;
+            firstUncommittedInlineItem = nullptr;
+        };
+
+        // #2
+        if (*detachingRules == InlineFormattingState::DetachingRule::BreakAtStart) {
+            commit();
+            firstUncommittedInlineItem = &inlineItem;
+            uncommittedLength = currentLength();
+            continue;
         }
 
-        // Create a dedicated run for this inline item.
-        auto length = std::min(remaningLength, inlineItem.textContent().length() - startPosition);
-        contentStart = split(inlineItem, startPosition, length, contentStart);
+        // #3
+        if (*detachingRules == InlineFormattingState::DetachingRule::BreakAtEnd) {
+            ASSERT(firstUncommittedInlineItem);
+            uncommittedLength += currentLength();
+            commit();
+            continue;
+        }
 
-        startPosition = 0;
-        remaningLength -= length;
-        firstUncommittedInlineItem = nullptr;
+        // #4
+        commit();
+        firstUncommittedInlineItem = &inlineItem;
+        uncommittedLength = currentLength();
+        commit();
     }
 
     // Either all inline elements needed dedicated runs or neither of them.
@@ -395,42 +413,67 @@ void InlineFormattingContext::computeStaticPosition(const Box&) const
 {
 }
 
-void InlineFormattingContext::collectInlineContent(InlineRunProvider& inlineRunProvider) const
+void InlineFormattingContext::collectInlineContentForSubtree(const Box& root, InlineRunProvider& inlineRunProvider) const
 {
-    if (!is<Container>(root()))
+    // Collect inline content recursively and set breaking rules for the inline elements (for paddings, margins, positioned element etc).
+    auto& inlineFormattingState = this->inlineFormattingState();
+
+    if (root.establishesFormattingContext() && &root != &(this->root())) {
+        // Skip formatting root subtree. They are not part of this inline formatting context.
+        inlineRunProvider.append(root);
+        inlineFormattingState.addDetachingRule(root, { InlineFormattingState::DetachingRule::BreakAtStart, InlineFormattingState::DetachingRule::BreakAtEnd });
         return;
+    }
 
-    auto& formattingRoot = downcast<Container>(root());
-    auto* layoutBox = formattingRoot.firstInFlowOrFloatingChild();
+    if (!is<Container>(root)) {
+        inlineRunProvider.append(root);
+        return;
+    }
 
-    while (layoutBox) {
-        ASSERT(layoutBox->isDescendantOf(formattingRoot));
+    auto* lastInlineBoxBeforeContainer = inlineFormattingState.lastInlineItem();
+    auto* child = downcast<Container>(root).firstInFlowOrFloatingChild();
+    while (child) {
+        collectInlineContentForSubtree(*child, inlineRunProvider);
+        child = child->nextInFlowOrFloatingSibling();
+    }
 
-        if (layoutBox->establishesFormattingContext()) {
-            inlineRunProvider.append(*layoutBox);
-            layoutBox = layoutBox->nextInFlowOrFloatingSibling();
-            continue;
-        }
+    // Setup breaking boundaries for this subtree.
+    auto* lastDescendantInlineBox = inlineFormattingState.lastInlineItem();
+    // Empty container?
+    if (lastInlineBoxBeforeContainer == lastDescendantInlineBox)
+        return;
 
-        if (is<Container>(layoutBox)) {
-            layoutBox = downcast<Container>(*layoutBox).firstInFlowOrFloatingChild();
-            continue;
-        }
+    auto rootBreaksAtStart = [&] {
+        // FIXME: add padding-inline-start, margin-inline-start etc.
+        return false;
+    };
 
-        inlineRunProvider.append(*layoutBox);
+    auto rootBreaksAtEnd = [&] {
+        // FIXME: add padding-inline-end, margin-inline-end etc.
+        return false;
+    };
 
-        while (true) {
-            if (auto* nextSibling = layoutBox->nextInFlowOrFloatingSibling()) {
-                layoutBox = nextSibling;
-                break;
-            }
+    if (rootBreaksAtStart()) {
+        InlineItem* firstDescendantInlineBox = nullptr;
+        auto& inlineContent = inlineFormattingState.inlineContent();
 
-            layoutBox = layoutBox->parent();
+        if (lastInlineBoxBeforeContainer) {
+            auto iterator = inlineContent.find<const InlineItem&, InlineItemHashTranslator>(*lastInlineBoxBeforeContainer);
+            firstDescendantInlineBox = (*++iterator).get();
+        } else
+            firstDescendantInlineBox = inlineContent.first().get();
 
-            if (layoutBox == &formattingRoot)
-                return;
-        }
+        ASSERT(firstDescendantInlineBox);
+        inlineFormattingState.addDetachingRule(firstDescendantInlineBox->layoutBox(), InlineFormattingState::DetachingRule::BreakAtStart);
     }
+
+    if (rootBreaksAtEnd())
+        inlineFormattingState.addDetachingRule(lastDescendantInlineBox->layoutBox(), InlineFormattingState::DetachingRule::BreakAtEnd);
+}
+
+void InlineFormattingContext::collectInlineContent(InlineRunProvider& inlineRunProvider) const
+{
+    collectInlineContentForSubtree(root(), inlineRunProvider);
 }
 
 FormattingContext::InstrinsicWidthConstraints InlineFormattingContext::instrinsicWidthConstraints() const
index a3c22a7..1aca63c 100644 (file)
@@ -108,13 +108,11 @@ private:
     };
 
     void layoutInlineContent(const InlineRunProvider&) const;
-
     void initializeNewLine(Line&) const;
     void closeLine(Line&, IsLastLine) const;
     void appendContentToLine(Line&, const InlineLineBreaker::Run&) const;
     void postProcessInlineRuns(Line&, IsLastLine, Line::RunRange) const;
     void splitInlineRunIfNeeded(const InlineRun&, InlineRuns& splitRuns) const;
-    bool contentRequiresSeparateRun(const InlineItem&) const;
 
     void layoutFormattingContextRoot(const Box&) const;
     void computeWidthAndHeightForReplacedInlineBox(const Box&) const;
@@ -124,6 +122,7 @@ private:
     void computeStaticPosition(const Box&) const override;
 
     void collectInlineContent(InlineRunProvider&) const;
+    void collectInlineContentForSubtree(const Box& root, InlineRunProvider&) const;
     InstrinsicWidthConstraints instrinsicWidthConstraints() const override;
 
     InlineFormattingState& inlineFormattingState() const { return downcast<InlineFormattingState>(formattingState()); }
index 92d71a4..aa43970 100644 (file)
@@ -50,6 +50,15 @@ std::unique_ptr<FormattingContext> InlineFormattingState::formattingContext(cons
     return std::make_unique<InlineFormattingContext>(formattingContextRoot, *this);
 }
 
+std::optional<InlineFormattingState::DetachingRules> InlineFormattingState::detachingRules(const Box& layoutBox) const
+{
+    auto detachingRules = m_detachingRules.get(&layoutBox);
+    if (!detachingRules)
+        return { };
+
+    return detachingRules;
+}
+
 }
 }
 #endif
index a753597..b42f462 100644 (file)
@@ -31,6 +31,7 @@
 #include "InlineItem.h"
 #include "InlineRun.h"
 #include <wtf/IsoMalloc.h>
+#include <wtf/OptionSet.h>
 
 namespace WebCore {
 namespace Layout {
@@ -45,13 +46,44 @@ public:
     std::unique_ptr<FormattingContext> formattingContext(const Box& formattingContextRoot) override;
 
     InlineContent& inlineContent() { return m_inlineContent; }
+    InlineItem* lastInlineItem() const { return m_inlineContent.isEmpty() ? nullptr : m_inlineContent.last().get(); }
+
+    // DetachingRule indicates whether the inline element needs to be wrapped in a dediceted run or break from previous/next runs.
+    // <span>start</span><span style="position: relative;"> middle </span><span>end</span>
+    // input to line breaking -> <start middle end>
+    // output of line breaking (considering infinite constraint) -> <start middle end>
+    // due to the in-flow positioning, the final runs are: <start>< middle ><end>
+    // "start" -> n/a
+    // " middle " -> BreakAtStart and BreakAtEnd
+    // "end" -> n/a
+    //
+    // <span>parent </span><span style="padding: 10px;">start<span> middle </span>end</span><span> parent</span>
+    // input to line breaking -> <parent start middle end parent>
+    // output of line breaking (considering infinite constraint) -> <parent start middle end parent>
+    // due to padding, final runs -> <parent><start middle end><parent>
+    // "parent" -> n/a
+    // "start" -> BreakAtStart
+    // " middle " -> n/a
+    // "end" -> BreakAtEnd
+    // "parent" -> n/a
+    enum class DetachingRule {
+        BreakAtStart = 1 << 0,
+        BreakAtEnd = 1 << 1
+    };
+    using DetachingRules = OptionSet<DetachingRule>;
+    std::optional<DetachingRules> detachingRules(const Box& layoutBox) const;
+    void addDetachingRule(const Box& layoutBox, DetachingRules detachingRules) { m_detachingRules.set(&layoutBox, detachingRules); }
+
     // Temp
     InlineRuns& inlineRuns() { return m_inlineRuns; }
     void appendInlineRun(InlineRun inlineRun) { m_inlineRuns.append(inlineRun); }
 
 private:
+    using DetachingRulesForInlineItems = HashMap<const Box*, DetachingRules>;
+
     InlineContent m_inlineContent;
     InlineRuns m_inlineRuns;
+    DetachingRulesForInlineItems m_detachingRules;
 };
 
 }