Changeset 286784 in webkit

Timestamp:

Dec 9, 2021, 9:26:58 AM (3 years ago)

Author:

Alan Bujtas

Message:

[LFC][IFC] Refactor bidi inline box boundary handling
​https://bugs.webkit.org/show_bug.cgi?id=233880

Reviewed by Antti Koivisto.

This patch remove some code complexity by introducing more suitable data types to handle
content ranges for inline boxes.

1. The final output of the InlineDisplayContentBuilder is a list of display boxes. It's a simple "one box right after the other" type of setup with continuous geometry (ie next box starts where the previous ends +-horizontal margins) unless the content is embedded in an inline box (e.g. <span>embedded content</span>) Inline box type of display boxes enclose all their descendant content. Normally when the logical order == visual order (unidirectional content), the descendant content ends right before the "inline box end" mark (</span>). It makes it easy to compute the right edge/enclosing width for the inline box type of display boxes.
2. However the visual order of the bidi content makes the "let's use the inline box end mark" logic unusable as we may see the "inline box end" mark even before we come across any descendant content (there are other types of confusions with random ordering).
3. Working with a list when the content comes in a nested flavor may introduce some complexity (e.g. need to keep content ranges around).

This patch introduces a very simple DisplayBoxNode type which keeps track of the display boxes in a tree fashion.
The display boxes are still stored in a list, while this newly introduced DisplayBoxNode tree helps traversing
the nested content.
It helps finding out the insertion point at unexpected bidi boundaries (e.g. when nested content from other inline boxes
show up in a logically unrelated inline box) and it is also very valuable when computing visual geometries for those enclosing display boxes.

• layout/formattingContexts/inline/InlineDisplayContentBuilder.cpp:

(WebCore::Layout::DisplayBoxNode::DisplayBoxNode):
(WebCore::Layout::DisplayBoxNode::appendChild):
(WebCore::Layout::AncestorStack::unwind):
(WebCore::Layout::AncestorStack::push):
(WebCore::Layout::InlineDisplayContentBuilder::ensureDisplayBoxForContainer):
(WebCore::Layout::InlineDisplayContentBuilder::adjustVisualGeometryForChildNode):
(WebCore::Layout::InlineDisplayContentBuilder::insertInlineBoxDisplayBoxForBidiBoundary): Deleted.
(WebCore::Layout::InlineDisplayContentBuilder::adjustInlineBoxDisplayBoxForBidiBoundary): Deleted.
(WebCore::Layout::InlineDisplayContentBuilder::processBidiContent): Deleted.
(WebCore::Layout::InlineDisplayContentBuilder::processOverflownRunsForEllipsis): Deleted.
(WebCore::Layout::InlineDisplayContentBuilder::collectInkOverflowForInlineBoxes): Deleted.
(WebCore::Layout::InlineDisplayContentBuilder::computeIsFirstIsLastBoxForInlineContent): Deleted.

• layout/formattingContexts/inline/InlineDisplayContentBuilder.h:
• layout/formattingContexts/inline/display/InlineDisplayBox.h:

(WebCore::InlineDisplay::Box::setLogicalLeft):
(WebCore::InlineDisplay::Box::setLogicalRight):
(WebCore::InlineDisplay::Box::setLogicalRect):
(WebCore::InlineDisplay::Box::setHasContent):

Location:

trunk/Source/WebCore

Files:

• ChangeLog (modified) (1 diff)
• layout/formattingContexts/inline/InlineDisplayContentBuilder.cpp (modified) (4 diffs)
• layout/formattingContexts/inline/InlineDisplayContentBuilder.h (modified) (2 diffs)
• layout/formattingContexts/inline/display/InlineDisplayBox.h (modified) (1 diff)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
 2021-12-09  Alan Bujtas  <zalan@apple.com>
 

trunk/Source/WebCore/layout/formattingContexts/inline/InlineDisplayContentBuilder.cpp

@@ -267 +267 @@
 }
 
-void InlineDisplayContentBuilder::insertInlineBoxDisplayBoxForBidiBoundary(const InlineLevelBox& inlineBox, const InlineRect& inlineBoxRect, bool isFirstInlineBoxFragment, size_t insertionPoint, DisplayBoxes& boxes)
-{
-    ASSERT(inlineBox.isInlineBox());
-
-    auto isFirstLastBox = OptionSet<InlineDisplay::Box::PositionWithinInlineLevelBox> { };
-    if (inlineBox.isFirstBox() && isFirstInlineBoxFragment)
-        isFirstLastBox.add({ InlineDisplay::Box::PositionWithinInlineLevelBox::First });
-    if (inlineBox.isLastBox())
-        isFirstLastBox.add({ InlineDisplay::Box::PositionWithinInlineLevelBox::Last });
-
-    // FIXME: Compute ink overflow.
-    boxes.insert(insertionPoint, { m_lineIndex
-        , InlineDisplay::Box::Type::NonRootInlineBox
-        , inlineBox.layoutBox()
-        , UBIDI_DEFAULT_LTR
-        , inlineBoxRect
-        , inlineBoxRect
-        , { }
-        , { }
-        , true
-        , isFirstLastBox });
-}
-
-void InlineDisplayContentBuilder::adjustInlineBoxDisplayBoxForBidiBoundary(InlineDisplay::Box& displayBox, const InlineRect& inlineBoxRect)
-{
-    UNUSED_PARAM(displayBox);
-    UNUSED_PARAM(inlineBoxRect);
-}
-
 void InlineDisplayContentBuilder::processNonBidiContent(const LineBuilder::LineContent& lineContent, const LineBox& lineBox, const InlineLayoutPoint& lineBoxLogicalTopLeft, DisplayBoxes& boxes)
 {
@@ -350 +321 @@
 }
 
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
 void InlineDisplayContentBuilder::processBidiContent(const LineBuilder::LineContent& lineContent, const LineBox& lineBox, const InlineLayoutPoint& lineBoxLogicalTopLeft, DisplayBoxes& boxes)
 {
     ASSERT(lineContent.visualOrderList.size() == lineContent.runs.size());
 
-    Vector<Range<size_t>> inlineBoxRangeList;
-    auto needsNonRootInlineBoxDisplayBox = false;
-    auto createDisplayBoxesInVisualOrderForContentRuns = [&] {
+    AncestorStack ancestorStack;
+    DisplayBoxNode rootDisplayBoxNode = { };
+    ancestorStack.push(rootDisplayBoxNode, root());
+
+    auto contentStartInVisualOrder = InlineLayoutUnit { };
+    auto createDisplayBoxesInVisualOrder = [&] {
         auto rootInlineBoxRect = lineBox.logicalRectForRootInlineBox();
-        auto contentRightInVisualOrder = InlineLayoutUnit { };
         // First visual run's initial content position depends on the block's inline direction.
         if (!root().style().isLeftToRightDirection()) {
             // FIXME: This needs the block end position instead of the lineLogicalWidth.
-            contentRightInVisualOrder += lineContent.lineLogicalWidth - rootInlineBoxRect.width();
+            contenttInVisualOrder += lineContent.lineLogicalWidth - rootInlineBoxRect.width();
         }
         // Adjust the content start position with the (text)alignment offset (root inline box has the alignment offset and not the individual runs).
-        contentRightInVisualOrder += rootInlineBoxRect.left();
-
+        contentStartInVisualOrder += rootInlineBoxRect.left();
+
+        auto contentRightInVisualOrder = contentStartInVisualOrder;
         auto& runs = lineContent.runs;
         for (size_t i = 0; i < runs.size(); ++i) {
             auto visualIndex = lineContent.visualOrderList[i];
             auto& lineRun = runs[visualIndex];
-
-            auto isContentRun = !lineRun.isInlineBoxStart() && !lineRun.isLineSpanningInlineBoxStart() && !lineRun.isInlineBoxEnd();
+            auto& layoutBox = lineRun.layoutBox();
+
+            auto isContentRun = !lineRun.isInlineBoxStart() && !lineRun.isLineSpanningInlineBoxStart() && !lineRun.isInlineBoxEnd() && !lineRun.isWordBreakOpportunity();
             if (!isContentRun) {
-                needsNonRootInlineBoxDisplayBox = true;
+                
                 continue;
             }
@@ -384 +467 @@
             };
 
+
             if (lineRun.isText()) {
                 auto visualRect = visualRectRelativeToRoot(lineBox.logicalRectForTextRun(lineRun));
                 appendTextDisplayBox(lineRun, visualRect, boxes);
                 contentRightInVisualOrder += visualRect.width();
-                continue;
-            }
-            if (lineRun.isSoftLineBreak()) {
+            } else if (lineRun.isSoftLineBreak()) {
                 ASSERT(!visualRectRelativeToRoot(lineBox.logicalRectForTextRun(lineRun)).width());
                 appendSoftLineBreakDisplayBox(lineRun, visualRectRelativeToRoot(lineBox.logicalRectForTextRun(lineRun)), boxes);
-                continue;
-            }
-            if (lineRun.isHardLineBreak()) {
-                ASSERT(!visualRectRelativeToRoot(lineBox.logicalRectForLineBreakBox(lineRun.layoutBox())).width());
-                appendHardLineBreakDisplayBox(lineRun, visualRectRelativeToRoot(lineBox.logicalRectForLineBreakBox(lineRun.layoutBox())), boxes);
-                continue;
-            }
-            if (lineRun.isBox()) {
-                auto& layoutBox = lineRun.layoutBox();
+            } else if (lineRun.isHardLineBreak()) {
+                ASSERT(!visualRectRelativeToRoot(lineBox.logicalRectForLineBreakBox(layoutBox)).width());
+                appendHardLineBreakDisplayBox(lineRun, visualRectRelativeToRoot(lineBox.logicalRectForLineBreakBox(layoutBox)), boxes);
+            } else if (lineRun.isBox()) {
                 auto& boxGeometry = formattingState().boxGeometry(layoutBox);
                 auto visualRect = visualRectRelativeToRoot(lineBox.logicalBorderBoxForAtomicInlineLevelBox(layoutBox, boxGeometry));
@@ -407 +484 @@
                 appendAtomicInlineLevelDisplayBox(lineRun, visualRect, boxes);
                 contentRightInVisualOrder += boxGeometry.marginStart() + visualRect.width() + boxGeometry.marginEnd();
-                continue;
             }
-            ASSERT(lineRun.isWordBreakOpportunity());
-        }
-    };
-    createDisplayBoxesInVisualOrderForContentRuns();
-
-    auto needsDisplayBoxHorizontalAdjustment = false;
-    auto createDisplayBoxesInVisualOrderForInlineBoxes = [&] {
-        // Visual order could introduce gaps and/or inject runs outside from the current inline box content.
-        // In such cases, we need to "close" and "open" display boxes for these inline box fragments
-        // to accommodate the current content.
-        // We do it by finding the lowest common ancestor of the last and the current content display boxes and
-        // traverse both ancestor chains and close/open the parent (inline) boxes.
-        // (open here means to create a new display box, while close means to simply pop it out of parentBoxStack).
-        // <div>a<span id=first>b&#8238;g</span>f<span id=second>e&#8237;c</span>d</div>
-        // produces the following output (note the #8238; #8237; RTL/LTR control characters):
-        // abcdefg
-        // with the following, fragmented inline boxes:
-        // a[first open]b[first close][second open]c[second close]d[second open]e[second close]f[first open]g[first close]
-        HashMap<const Box*, size_t> inlineBoxDisplayBoxMap;
-        ListHashSet<const Box*> parentBoxStack;
-        parentBoxStack.add(&root());
-
-        ASSERT(boxes[0].isRootInlineBox());
-        for (size_t index = 1; index < boxes.size(); ++index) {
-            auto& parentBox = boxes[index].layoutBox().parent();
-            ASSERT(parentBox.isInlineBox() || &parentBox == &root());
-
-            auto runParentIsCurrentInlineBox = &parentBox == parentBoxStack.last();
-            if (runParentIsCurrentInlineBox) {
-                // We've got the correct inline box as parent. Nothing to do here.
-                continue;
+            parentDisplayBoxNode.appendChild(boxes.size() - 1);
+        }
+    };
+    createDisplayBoxesInVisualOrder();
+
+    if (!rootDisplayBoxNode.children.isEmpty()) {
+        auto computeIsFirstIsLastBox = [&] {
+            HashMap<const Box*, size_t> lastDisplayBoxIndexes;
+            ASSERT(boxes[0].isRootInlineBox());
+            for (size_t index = 1; index < boxes.size(); ++index) {
+                auto& displayBox = boxes[index];
+                if (!displayBox.isNonRootInlineBox())
+                    continue;
+                auto& layoutBox = displayBox.layoutBox();
+                auto isFirstBoxOnCurrentLine = lastDisplayBoxIndexes.set(&layoutBox, index).isNewEntry;
+                if (lineBox.inlineLevelBoxForLayoutBox(layoutBox).isFirstBox() && isFirstBoxOnCurrentLine)
+                    displayBox.setIsFirstForLayoutBox(true);
             }
-            auto parentBoxStackEnd = parentBoxStack.end();
-            Vector<const Box*> inlineBoxNeedingDisplayBoxList;
-            for (auto* ancestor = &parentBox; ancestor; ancestor = &ancestor->parent()) {
-                ASSERT(ancestor == &root() || ancestor->isInlineBox());
-                auto parentBoxIterator = parentBoxStack.find(ancestor);
-                if (parentBoxIterator != parentBoxStackEnd) {
-                    // This is the lowest common ancestor.
-                    // Let's traverse both ancestor chains and create/close display boxes as needed.
-                    Vector<const Box*> inlineBoxFragmentsToClose;
-                    for (auto it = ++parentBoxIterator; it != parentBoxStackEnd; ++it)
-                        inlineBoxFragmentsToClose.append(*it);
-
-                    for (auto* inlineBox : makeReversedRange(inlineBoxFragmentsToClose)) {
-                        ASSERT(inlineBox->isInlineBox());
-                        ASSERT(inlineBoxDisplayBoxMap.contains(inlineBox));
-                        inlineBoxRangeList.append({ inlineBoxDisplayBoxMap.get(inlineBox), index });
-                        parentBoxStack.remove(inlineBox);
-                    }
-
-                    // Insert new display boxes for inline box fragments on bidi boundary.
-                    for (auto* inlineBox : makeReversedRange(inlineBoxNeedingDisplayBoxList)) {
-                        ASSERT(inlineBox->isInlineBox());
-                        parentBoxStack.add(inlineBox);
-
-                        auto createAndInsertDisplayBoxForInlineBoxFragment = [&] {
-                            // Make sure that the "previous" display box for this particular inline box is not tracked as the "last box".
-                            auto lastDisplayBoxForInlineBoxIndex = inlineBoxDisplayBoxMap.take(inlineBox);
-                            auto isFirstFragment = !lastDisplayBoxForInlineBoxIndex;
-                            if (!isFirstFragment)
-                                boxes[lastDisplayBoxForInlineBoxIndex].setIsLastForLayoutBox(false);
-                            inlineBoxDisplayBoxMap.set(inlineBox, index);
-
-                            auto& boxGeometry = formattingState().boxGeometry(*inlineBox);
-                            auto visualRect = lineBox.logicalBorderBoxForInlineBox(*inlineBox, boxGeometry);
-                            // Use the current content left as the starting point for this display box.
-                            visualRect.setLeft(boxes[index].logicalLeft());
-                            visualRect.moveVertically(lineBoxLogicalTopLeft.y());
-                            // Visual width is not yet known.
-                            visualRect.setWidth({ });
-                            insertInlineBoxDisplayBoxForBidiBoundary(lineBox.inlineLevelBoxForLayoutBox(*inlineBox), visualRect, isFirstFragment, index, boxes);
-                            ++index;
-                            // Need to push the rest of the content when this inline box has margin/border/padding.
-                            needsDisplayBoxHorizontalAdjustment = needsDisplayBoxHorizontalAdjustment
-                                || boxGeometry.horizontalBorder()
-                                || boxGeometry.horizontalPadding().value_or(0)
-                                || boxGeometry.marginStart()
-                                || boxGeometry.marginEnd();
-                        };
-                        createAndInsertDisplayBoxForInlineBoxFragment();
-                    }
-                    break;
-                }
-                // root may not be the lowest but always a common ancestor.
-                ASSERT(ancestor != &root());
-                inlineBoxNeedingDisplayBoxList.append(ancestor);
+            for (auto index : lastDisplayBoxIndexes.values()) {
+                if (lineBox.inlineLevelBoxForLayoutBox(boxes[index].layoutBox()).isLastBox())
+                    boxes[index].setIsLastForLayoutBox(true);
             }
-        }
-        // "Close" the remaining inline boxes on the stack (excluding the root).
-        while (parentBoxStack.size() > 1) {
-            auto* parentInlineBox = parentBoxStack.takeLast();
-            ASSERT(inlineBoxDisplayBoxMap.contains(parentInlineBox));
-            inlineBoxRangeList.append({ inlineBoxDisplayBoxMap.get(parentInlineBox), boxes.size() });
-        }
-    };
-    if (needsNonRootInlineBoxDisplayBox)
-        createDisplayBoxesInVisualOrderForInlineBoxes();
-
-    auto adjustVisualGeometryWithInlineBoxes = [&] {
-        size_t currentInlineBox = 0;
-        auto accumulatedOffset = InlineLayoutUnit { };
-
-        ASSERT(boxes[0].isRootInlineBox());
-        for (size_t index = 1; index < boxes.size(); ++index) {
-            auto& displayBox = boxes[index];
-            displayBox.moveHorizontally(accumulatedOffset);
-
-            while (currentInlineBox < inlineBoxRangeList.size() && index == inlineBoxRangeList[currentInlineBox].end() - 1) {
-                // We are at the end of the inline box content.
-                // Let's compute the inline box width and offset the rest of the content with padding/border/margin end.
-                auto inlineBoxRange = inlineBoxRangeList[currentInlineBox++];
-                auto& inlineBoxDisplayBox = boxes[inlineBoxRange.begin()];
-                ASSERT(inlineBoxDisplayBox.isNonRootInlineBox());
-
-                auto& boxGeometry = formattingState().boxGeometry(inlineBoxDisplayBox.layoutBox());
-                auto contentRight = displayBox.logicalRight();
-                if (inlineBoxDisplayBox.isLastForLayoutBox()) {
-                    accumulatedOffset += boxGeometry.borderAndPaddingEnd() + boxGeometry.marginEnd();
-                    inlineBoxDisplayBox.setLogicalRight(contentRight + boxGeometry.borderAndPaddingEnd());
-                } else
-                    inlineBoxDisplayBox.setLogicalRight(contentRight);
-            }
-            if (displayBox.isNonRootInlineBox() && displayBox.isFirstForLayoutBox()) {
-                auto& layoutBox = displayBox.layoutBox();
-                auto& boxGeometry = formattingState().boxGeometry(layoutBox);
-
-                displayBox.moveHorizontally(boxGeometry.marginStart());
-                accumulatedOffset += boxGeometry.marginStart() + boxGeometry.borderAndPaddingStart();
-            }
-        }
-    };
-    if (needsDisplayBoxHorizontalAdjustment)
+        };
+        computeIsFirstIsLastBox();
+
+        auto adjustVisualGeometryWithInlineBoxes = [&] {
+            auto contentRightInVisualOrder = lineBoxLogicalTopLeft.x() + contentStartInVisualOrder;
+            for (auto& childDisplayBoxNode : rootDisplayBoxNode.children)
+                adjustVisualGeometryForChildNode(*childDisplayBoxNode, contentRightInVisualOrder, lineBoxLogicalTopLeft.y(), boxes, lineBox);
+        };
         adjustVisualGeometryWithInlineBoxes();
-
-    auto computeInlineBoxGeometry = [&] {
-        ASSERT(!inlineBoxRangeList.isEmpty());
-        for (auto& inlineBoxRange : inlineBoxRangeList) {
-            auto& inlineBoxDisplayBox = boxes[inlineBoxRange.begin()];
-            setInlineBoxGeometry(inlineBoxDisplayBox.layoutBox(), inlineBoxDisplayBox.logicalRect(), inlineBoxDisplayBox.isFirstForLayoutBox());
-        }
-    };
-    if (needsNonRootInlineBoxDisplayBox)
-        computeInlineBoxGeometry();
+    }
 }
 

trunk/Source/WebCore/layout/formattingContexts/inline/InlineDisplayContentBuilder.h

@@ -34 +34 @@
 namespace Layout {
 
+
 class ContainerBox;
+
 class InlineFormattingState;
 class LineBox;
@@ -58 +60 @@
     void appendInlineBoxDisplayBox(const Line::Run&, const InlineLevelBox&, const InlineRect&, bool linehasContent, DisplayBoxes&);
     void appendSpanningInlineBoxDisplayBox(const Line::Run&, const InlineLevelBox&, const InlineRect&, DisplayBoxes&);
-    void insertInlineBoxDisplayBoxForBidiBoundary(const InlineLevelBox&, const InlineRect&, bool isFirstInlineBoxFragment, size_t insertionPoint, DisplayBoxes&);
-    void adjustInlineBoxDisplayBoxForBidiBoundary(InlineDisplay::Box&, const InlineRect&);
 
     void setInlineBoxGeometry(const Box&, const InlineRect&, bool isFirstInlineBoxFragment);
+
+
 
     const ContainerBox& root() const { return m_formattingContextRoot; }

trunk/Source/WebCore/layout/formattingContexts/inline/display/InlineDisplayBox.h

@@ -119 +119 @@
     void adjustInkOverflow(const Layout::InlineRect& childBorderBox) { return m_inkOverflow.expandToContain(childBorderBox); }
     void truncate(Layout::InlineLayoutUnit truncatedwidth = 0.f);
-    void setLogicalRight(Layout::InlineLayoutUnit right) { m_logicalRect.setRight(right); }
+    void setLogicalLeft(Layout::InlineLayoutUnit left)
+    {
+        auto offset = left - logicalLeft();
+        m_logicalRect.setLeft(left);
+        m_inkOverflow.setLeft(m_inkOverflow.left() + offset);
+    }
+    void setLogicalRight(Layout::InlineLayoutUnit right)
+    {
+        auto offset = right - logicalRight();
+        m_logicalRect.setRight(right);
+        m_inkOverflow.setRight(m_inkOverflow.right() + offset);
+    }
+    void setLogicalRect(const Layout::InlineRect& rect, const Layout::InlineRect& inkOverflow)
+    {
+        m_logicalRect = rect;
+        m_inkOverflow = inkOverflow;
+    }
+    void setHasContent() { m_hasContent = true; }
 
     std::optional<Text>& text() { return m_text; }