⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 286851 in webkit


Ignore:
Timestamp:
Dec 10, 2021, 8:20:40 AM (5 years ago)
Author:
Alan Bujtas
Message:

[LFC][IFC] Replace Vector<std::unique_ptr<DisplayBoxNode> with Vector<DisplayBoxTree::Node>
​https://bugs.webkit.org/show_bug.cgi?id=234110

Reviewed by Antti Koivisto.

This patch switches over from using DisplayBoxNode* in AncestorStack to simple indexes to contain heap allocations.

  • layout/formattingContexts/inline/InlineDisplayContentBuilder.cpp:

(WebCore::Layout::DisplayBoxTree::DisplayBoxTree):
(WebCore::Layout::DisplayBoxTree::hasInlineBox const):
(WebCore::Layout::DisplayBoxTree::root const):
(WebCore::Layout::DisplayBoxTree::at):
(WebCore::Layout::DisplayBoxTree::at const):
(WebCore::Layout::DisplayBoxTree::append):
(WebCore::Layout::AncestorStack::unwind):
(WebCore::Layout::AncestorStack::push):
(WebCore::Layout::createdDisplayBoxNodeForContainerBoxAndPushToAncestorStack):
(WebCore::Layout::InlineDisplayContentBuilder::ensureDisplayBoxForContainer):
(WebCore::Layout::InlineDisplayContentBuilder::adjustVisualGeometryForDisplayBox):
(WebCore::Layout::InlineDisplayContentBuilder::processBidiContent):
(WebCore::Layout::DisplayBoxNode::DisplayBoxNode): Deleted.
(WebCore::Layout::DisplayBoxNode::appendChild): Deleted.
(WebCore::Layout::InlineDisplayContentBuilder::adjustVisualGeometryForChildNode): Deleted.

  • layout/formattingContexts/inline/InlineDisplayContentBuilder.h:
Location:
trunk/Source/WebCore
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r286848 r286851  
     12021-12-10  Alan Bujtas  <zalan@apple.com>
     2
     3        [LFC][IFC] Replace Vector<std::unique_ptr<DisplayBoxNode> with Vector<DisplayBoxTree::Node>
     4        https://bugs.webkit.org/show_bug.cgi?id=234110
     5
     6        Reviewed by Antti Koivisto.
     7
     8        This patch switches over from using DisplayBoxNode* in AncestorStack to simple indexes to contain heap allocations.
     9
     10        * layout/formattingContexts/inline/InlineDisplayContentBuilder.cpp:
     11        (WebCore::Layout::DisplayBoxTree::DisplayBoxTree):
     12        (WebCore::Layout::DisplayBoxTree::hasInlineBox const):
     13        (WebCore::Layout::DisplayBoxTree::root const):
     14        (WebCore::Layout::DisplayBoxTree::at):
     15        (WebCore::Layout::DisplayBoxTree::at const):
     16        (WebCore::Layout::DisplayBoxTree::append):
     17        (WebCore::Layout::AncestorStack::unwind):
     18        (WebCore::Layout::AncestorStack::push):
     19        (WebCore::Layout::createdDisplayBoxNodeForContainerBoxAndPushToAncestorStack):
     20        (WebCore::Layout::InlineDisplayContentBuilder::ensureDisplayBoxForContainer):
     21        (WebCore::Layout::InlineDisplayContentBuilder::adjustVisualGeometryForDisplayBox):
     22        (WebCore::Layout::InlineDisplayContentBuilder::processBidiContent):
     23        (WebCore::Layout::DisplayBoxNode::DisplayBoxNode): Deleted.
     24        (WebCore::Layout::DisplayBoxNode::appendChild): Deleted.
     25        (WebCore::Layout::InlineDisplayContentBuilder::adjustVisualGeometryForChildNode): Deleted.
     26        * layout/formattingContexts/inline/InlineDisplayContentBuilder.h:
     27
    1282021-12-10  Alan Bujtas  <zalan@apple.com>
    229

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

    r286801 r286851  
    341341}
    342342
    343 struct DisplayBoxNode {
    344     WTF_MAKE_STRUCT_FAST_ALLOCATED;
    345     DisplayBoxNode() = default;
    346     DisplayBoxNode(size_t index, DisplayBoxNode* parent)
    347         : index(index)
    348         , parent(parent)
    349         {
    350         }
    351 
    352     void appendChild(size_t childIndex) { children.append(makeUnique<DisplayBoxNode>(childIndex, this)); }
    353 
    354     size_t index { 0 };
    355     DisplayBoxNode* parent { nullptr };
    356     Vector<std::unique_ptr<DisplayBoxNode>> children;
     343struct DisplayBoxTree {
     344public:
     345    struct Node {
     346        // Node's parent index in m_displayBoxNodes.
     347        std::optional<size_t> parentIndex;
     348        // Associated display box index in DisplayBoxes.
     349        size_t displayBoxIndex { 0 };
     350        // Child indexes in m_displayBoxNodes.
     351        Vector<size_t> children { };
     352    };
     353
     354    DisplayBoxTree()
     355    {
     356        m_displayBoxNodes.append({ });
     357    }
     358
     359    bool hasInlineBox() const { return m_displayBoxNodes.size() > 1; }
     360    const Node& root() const { return m_displayBoxNodes.first(); }
     361    Node& at(size_t index) { return m_displayBoxNodes[index]; }
     362    const Node& at(size_t index) const { return m_displayBoxNodes[index]; }
     363
     364    size_t append(size_t parentNodeIndex, size_t childDisplayBoxIndex)
     365    {
     366        auto childDisplayBoxNodeIndex = m_displayBoxNodes.size();
     367        m_displayBoxNodes.append({ parentNodeIndex, childDisplayBoxIndex });
     368        at(parentNodeIndex).children.append(childDisplayBoxNodeIndex);
     369        return childDisplayBoxNodeIndex;
     370    }
     371
     372private:
     373    Vector<Node, 10> m_displayBoxNodes;
    357374};
    358375
    359376struct AncestorStack {
    360     DisplayBoxNode* unwind(const ContainerBox& containerBox)
     377    std::optional<size_t> unwind(const ContainerBox& containerBox)
    361378    {
    362379        // Unwind the stack all the way to container box.
    363380        if (!m_set.contains(&containerBox))
    364             return nullptr;
     381            return { };
    365382        while (m_set.last() != &containerBox) {
    366383            m_stack.removeLast();
    … …  
    372389    }
    373390
    374     void push(DisplayBoxNode& displayBoxNode, const ContainerBox& containerBox)
     391    void push(size_t displayBoxNodeIndexForContainerBox, const ContainerBox& containerBox)
    375392    {
    376         m_stack.append(&displayBoxNode);
     393        m_stack.append(displayBoxNodeIndexForContainerBox);
    377394        ASSERT(!m_set.contains(&containerBox));
    378395        m_set.add(&containerBox);
    … …  
    380397
    381398private:
    382     Vector<DisplayBoxNode*> m_stack;
     399    Vector<size_t> m_stack;
    383400    ListHashSet<const ContainerBox*> m_set;
    384401};
    385402
    386 static inline DisplayBoxNode& createdDisplayBoxNodeForContainerBoxAndPushToAncestorStack(const ContainerBox& containerBox, size_t displayBoxIndex, DisplayBoxNode& parentDisplayBoxNode, AncestorStack& ancestorStack)
    387 {
    388     parentDisplayBoxNode.appendChild(displayBoxIndex);
    389     auto& displayBoxNode = *parentDisplayBoxNode.children.last();
    390     ancestorStack.push(displayBoxNode, containerBox);
    391     return displayBoxNode;
    392 }
    393 
    394 DisplayBoxNode& InlineDisplayContentBuilder::ensureDisplayBoxForContainer(const ContainerBox& containerBox, AncestorStack& ancestorStack, DisplayBoxes& boxes)
     403static inline size_t createdDisplayBoxNodeForContainerBoxAndPushToAncestorStack(const ContainerBox& containerBox, size_t displayBoxIndex, size_t parentDisplayBoxNodeIndex, DisplayBoxTree& displayBoxTree, AncestorStack& ancestorStack)
     404{
     405    auto displayBoxNodeIndex = displayBoxTree.append(parentDisplayBoxNodeIndex, displayBoxIndex);
     406    ancestorStack.push(displayBoxNodeIndex, containerBox);
     407    return displayBoxNodeIndex;
     408}
     409
     410size_t InlineDisplayContentBuilder::ensureDisplayBoxForContainer(const ContainerBox& containerBox, DisplayBoxTree& displayBoxTree, AncestorStack& ancestorStack, DisplayBoxes& boxes)
    395411{
    396412    ASSERT(containerBox.isInlineBox() || &containerBox == &root());
    397     if (auto* lowestCommonAncestor = ancestorStack.unwind(containerBox))
    398         return *lowestCommonAncestor;
    399     auto& enclosingDisplayBoxNodeForContainer = ensureDisplayBoxForContainer(containerBox.parent(), ancestorStack, boxes);
     413    if (auto lowestCommonAncestorIndex = ancestorStack.unwind(containerBox))
     414        return *lowestCommonAncestorIndex;
     415    auto enclosingDisplayBoxNodeIndexForContainer = ensureDisplayBoxForContainer(containerBox.parent(), displayBoxTree, ancestorStack, boxes);
    400416    appendInlineDisplayBoxAtBidiBoundary(containerBox, boxes);
    401     return createdDisplayBoxNodeForContainerBoxAndPushToAncestorStack(containerBox, boxes.size() - 1, enclosingDisplayBoxNodeForContainer, ancestorStack);
    402 }
    403 
    404 void InlineDisplayContentBuilder::adjustVisualGeometryForChildNode(const DisplayBoxNode& displayBoxNode, InlineLayoutUnit& contentRightInVisualOrder, InlineLayoutUnit lineBoxLogicalTop, DisplayBoxes& boxes, const LineBox& lineBox)
     417    return createdDisplayBoxNodeForContainerBoxAndPushToAncestorStack(containerBox, boxes.size() - 1, enclosingDisplayBoxNodeIndexForContainer, displayBoxTree, ancestorStack);
     418}
     419
     420void InlineDisplayContentBuilder::adjustVisualGeometryForDisplayBox(size_t displayBoxNodeIndex, InlineLayoutUnit& contentRightInVisualOrder, InlineLayoutUnit lineBoxLogicalTop, const DisplayBoxTree& displayBoxTree, DisplayBoxes& boxes, const LineBox& lineBox)
    405421{
    406422    // Non-inline box display boxes just need a horizontal adjustment while
    … …  
    408424    // 1. horizontal adjustment and margin/border/padding start offsetting on the first box
    409425    // 2. right edge computation including descendant content width and margin/border/padding end offsetting on the last box
    410     ASSERT(displayBoxNode.index);
    411     auto& displayBox = boxes[displayBoxNode.index];
     426    auto& displayBox = boxes[displayBoxTree.at(displayBoxNodeIndex).displayBoxIndex];
    412427    auto& layoutBox = displayBox.layoutBox();
    413428
    … …  
    434449    beforeInlineBoxContent();
    435450
    436     for (auto& childDisplayBoxNode : displayBoxNode.children)
    437         adjustVisualGeometryForChildNode(*childDisplayBoxNode, contentRightInVisualOrder, lineBoxLogicalTop, boxes, lineBox);
     451    for (auto childDisplayBoxNodeIndex : displayBoxTree.at(displayBoxNodeIndex).children)
     452        adjustVisualGeometryForDisplayBox(childDisplayBoxNodeIndex, contentRightInVisualOrder, lineBoxLogicalTop, displayBoxTree, boxes, lineBox);
    438453
    439454    auto afterInlineBoxContent = [&] {
    … …  
    464479
    465480    AncestorStack ancestorStack;
    466     DisplayBoxNode rootDisplayBoxNode = { };
    467     ancestorStack.push(rootDisplayBoxNode, root());
     481    auto displayBoxTree = DisplayBoxTree { };
     482    ancestorStack.push({ }, root());
    468483
    469484    auto contentStartInVisualOrder = InlineLayoutUnit { };
    … …  
    496511            };
    497512
    498             auto& parentDisplayBoxNode = ensureDisplayBoxForContainer(layoutBox.parent(), ancestorStack, boxes);
     513            auto parentDisplayBoxNodeIndex = ensureDisplayBoxForContainer(layoutBox.parent(), displayBoxTree, ancestorStack, boxes);
    499514            if (lineRun.isText()) {
    500515                auto visualRect = visualRectRelativeToRoot(lineBox.logicalRectForTextRun(lineRun));
    501516                appendTextDisplayBox(lineRun, visualRect, boxes);
    502517                contentRightInVisualOrder += visualRect.width();
    503                 parentDisplayBoxNode.appendChild(boxes.size() - 1);
     518                displayBoxTree.append(parentDisplayBoxNodeIndex, boxes.size() - 1);
    504519                continue;
    505520            }
    … …  
    507522                ASSERT(!visualRectRelativeToRoot(lineBox.logicalRectForTextRun(lineRun)).width());
    508523                appendSoftLineBreakDisplayBox(lineRun, visualRectRelativeToRoot(lineBox.logicalRectForTextRun(lineRun)), boxes);
    509                 parentDisplayBoxNode.appendChild(boxes.size() - 1);
     524                displayBoxTree.append(parentDisplayBoxNodeIndex, boxes.size() - 1);
    510525                continue;
    511526            }
    … …  
    513528                ASSERT(!visualRectRelativeToRoot(lineBox.logicalRectForLineBreakBox(layoutBox)).width());
    514529                appendHardLineBreakDisplayBox(lineRun, visualRectRelativeToRoot(lineBox.logicalRectForLineBreakBox(layoutBox)), boxes);
    515                 parentDisplayBoxNode.appendChild(boxes.size() - 1);
     530                displayBoxTree.append(parentDisplayBoxNodeIndex, boxes.size() - 1);
    516531                continue;
    517532            }
    … …  
    522537                appendAtomicInlineLevelDisplayBox(lineRun, visualRect, boxes);
    523538                contentRightInVisualOrder += boxGeometry.marginStart() + visualRect.width() + boxGeometry.marginEnd();
    524                 parentDisplayBoxNode.appendChild(boxes.size() - 1);
     539                displayBoxTree.append(parentDisplayBoxNodeIndex, boxes.size() - 1);
    525540                continue;
    526541            }
    527542            if (lineRun.isInlineBoxStart() || lineRun.isLineSpanningInlineBoxStart()) {
    528543                appendInlineDisplayBoxAtBidiBoundary(layoutBox, boxes);
    529                 createdDisplayBoxNodeForContainerBoxAndPushToAncestorStack(downcast<ContainerBox>(layoutBox), boxes.size() - 1, parentDisplayBoxNode, ancestorStack);
     544                createdDisplayBoxNodeForContainerBoxAndPushToAncestorStack(downcast<ContainerBox>(layoutBox), boxes.size() - 1, parentDisplayBoxNodeIndex, displayBoxTree, ancestorStack);
    530545                continue;
    531546            }
    … …  
    535550    createDisplayBoxesInVisualOrder();
    536551
    537     if (!rootDisplayBoxNode.children.isEmpty()) {
     552    if (displayBoxTree.hasInlineBox()) {
    538553        auto computeIsFirstIsLastBox = [&] {
    539554            HashMap<const Box*, size_t> lastDisplayBoxIndexes;
    … …  
    557572        auto adjustVisualGeometryWithInlineBoxes = [&] {
    558573            auto contentRightInVisualOrder = lineBoxLogicalTopLeft.x() + contentStartInVisualOrder;
    559             for (auto& childDisplayBoxNode : rootDisplayBoxNode.children)
    560                 adjustVisualGeometryForChildNode(*childDisplayBoxNode, contentRightInVisualOrder, lineBoxLogicalTopLeft.y(), boxes, lineBox);
     574
     575            for (auto childDisplayBoxNodeIndex : displayBoxTree.root().children)
     576                adjustVisualGeometryForDisplayBox(childDisplayBoxNodeIndex, contentRightInVisualOrder, lineBoxLogicalTopLeft.y(), displayBoxTree, boxes, lineBox);
    561577        };
    562578        adjustVisualGeometryWithInlineBoxes();

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

    r286789 r286851  
    3636struct AncestorStack;
    3737class ContainerBox;
    38 struct DisplayBoxNode;
     38struct DisplayBoxTree;
    3939class InlineFormattingState;
    4040class LineBox;
    … …  
    6363
    6464    void setInlineBoxGeometry(const Box&, const InlineRect&, bool isFirstInlineBoxFragment);
    65     void adjustVisualGeometryForChildNode(const DisplayBoxNode&, InlineLayoutUnit& accumulatedOffset, InlineLayoutUnit lineBoxLogicalTop, DisplayBoxes&, const LineBox&);
    66     DisplayBoxNode& ensureDisplayBoxForContainer(const ContainerBox&, AncestorStack&, DisplayBoxes&);
     65    void adjustVisualGeometryForDisplayBox(size_t displayBoxNodeIndex, InlineLayoutUnit& accumulatedOffset, InlineLayoutUnit lineBoxLogicalTop, const DisplayBoxTree&, DisplayBoxes&, const LineBox&);
     66    size_t ensureDisplayBoxForContainer(const ContainerBox&, DisplayBoxTree&, AncestorStack&, DisplayBoxes&);
    6767
    6868    const ContainerBox& root() const { return m_formattingContextRoot; }
Note: See TracChangeset for help on using the changeset viewer.