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

Changeset 282211 in webkit


Ignore:
Timestamp:
Sep 9, 2021, 6:59:41 AM (5 years ago)
Author:
Antti Koivisto
Message:

Add cache to InlineContent for O(1) inline box access
​https://bugs.webkit.org/show_bug.cgi?id=230092

Reviewed by Alan Bujtas.

Add lazy caches for getting the index of the first run and all non-root inline boxes for a layout box.

  • layout/integration/LayoutIntegrationInlineContent.cpp:

(WebCore::LayoutIntegration::InlineContent::indexForRun const):
(WebCore::LayoutIntegration::InlineContent::firstRunForLayoutBox const):
(WebCore::LayoutIntegration::InlineContent::firstRunIndexForLayoutBox const):

For small run vectors (<16) just search directly.

(WebCore::LayoutIntegration::InlineContent::nonRootInlineBoxIndexesForLayoutBox const):
(WebCore::LayoutIntegration::InlineContent::releaseCaches):

Memory cleanup support.

(WebCore::LayoutIntegration::InlineContent::shrinkToFit):
(WebCore::LayoutIntegration::InlineContent::iteratorForRun const): Deleted.
(WebCore::LayoutIntegration::InlineContent::iteratorForTextRun const): Deleted.

Cleanup the interface by removing iterator dependency (iterator depends on InlineContent, not other way round).

  • layout/integration/LayoutIntegrationInlineContent.h:

(WebCore::LayoutIntegration::InlineContent::traverseNonRootInlineBoxes):

Traversal helper.

(WebCore::LayoutIntegration::InlineContent::shrinkToFit): Deleted.

  • layout/integration/LayoutIntegrationLineLayout.cpp:

(WebCore::LayoutIntegration::LineLayout::textRunsFor const):
(WebCore::LayoutIntegration::LineLayout::runFor const):
(WebCore::LayoutIntegration::LineLayout::firstInlineBoxRect const):
(WebCore::LayoutIntegration::LineLayout::visualOverflowBoundingBoxRectFor const):
(WebCore::LayoutIntegration::LineLayout::collectInlineBoxRects const):

Use the new cache-backed interfaces.

(WebCore::LayoutIntegration::LineLayout::releaseCaches):
(WebCore::LayoutIntegration::LineLayout::paintTextRunUsingPhysicalCoordinates):
(WebCore::LayoutIntegration::LineLayout::releaseInlineItemCache): Deleted.

  • layout/integration/LayoutIntegrationLineLayout.h:
  • layout/integration/LayoutIntegrationRunIterator.cpp:

(WebCore::LayoutIntegration::textRunFor):
(WebCore::LayoutIntegration::runFor):

  • layout/integration/LayoutIntegrationRunIterator.h:
Location:
trunk/Source/WebCore
Files:
7 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r282209 r282211  
     12021-09-09  Antti Koivisto  <antti@apple.com>
     2
     3        Add cache to InlineContent for O(1) inline box access
     4        https://bugs.webkit.org/show_bug.cgi?id=230092
     5
     6        Reviewed by Alan Bujtas.
     7
     8        Add lazy caches for getting the index of the first run and all non-root inline boxes for a layout box.
     9
     10        * layout/integration/LayoutIntegrationInlineContent.cpp:
     11        (WebCore::LayoutIntegration::InlineContent::indexForRun const):
     12        (WebCore::LayoutIntegration::InlineContent::firstRunForLayoutBox const):
     13        (WebCore::LayoutIntegration::InlineContent::firstRunIndexForLayoutBox const):
     14
     15        For small run vectors (<16) just search directly.
     16
     17        (WebCore::LayoutIntegration::InlineContent::nonRootInlineBoxIndexesForLayoutBox const):
     18        (WebCore::LayoutIntegration::InlineContent::releaseCaches):
     19
     20        Memory cleanup support.
     21
     22        (WebCore::LayoutIntegration::InlineContent::shrinkToFit):
     23        (WebCore::LayoutIntegration::InlineContent::iteratorForRun const): Deleted.
     24        (WebCore::LayoutIntegration::InlineContent::iteratorForTextRun const): Deleted.
     25
     26        Cleanup the interface by removing iterator dependency (iterator depends on InlineContent, not other way round).
     27
     28        * layout/integration/LayoutIntegrationInlineContent.h:
     29        (WebCore::LayoutIntegration::InlineContent::traverseNonRootInlineBoxes):
     30
     31        Traversal helper.
     32
     33        (WebCore::LayoutIntegration::InlineContent::shrinkToFit): Deleted.
     34        * layout/integration/LayoutIntegrationLineLayout.cpp:
     35        (WebCore::LayoutIntegration::LineLayout::textRunsFor const):
     36        (WebCore::LayoutIntegration::LineLayout::runFor const):
     37        (WebCore::LayoutIntegration::LineLayout::firstInlineBoxRect const):
     38        (WebCore::LayoutIntegration::LineLayout::visualOverflowBoundingBoxRectFor const):
     39        (WebCore::LayoutIntegration::LineLayout::collectInlineBoxRects const):
     40
     41        Use the new cache-backed interfaces.
     42
     43        (WebCore::LayoutIntegration::LineLayout::releaseCaches):
     44        (WebCore::LayoutIntegration::LineLayout::paintTextRunUsingPhysicalCoordinates):
     45        (WebCore::LayoutIntegration::LineLayout::releaseInlineItemCache): Deleted.
     46        * layout/integration/LayoutIntegrationLineLayout.h:
     47        * layout/integration/LayoutIntegrationRunIterator.cpp:
     48        (WebCore::LayoutIntegration::textRunFor):
     49        (WebCore::LayoutIntegration::runFor):
     50        * layout/integration/LayoutIntegrationRunIterator.h:
     51
    1522021-09-09  Frederic Wang  <fwang@igalia.com>
    253

  • trunk/Source/WebCore/layout/integration/LayoutIntegrationInlineContent.cpp

    r282050 r282211  
    7979}
    8080
    81 RunIterator InlineContent::iteratorForRun(const Run& run) const
     81size_t InlineContent::indexForRun(const Run& run) const
    8282{
    83     return { RunIteratorModernPath { *this, static_cast<size_t>(&run - runs.begin()) } };
     83    auto index = static_cast<size_t>(&run - runs.begin());
     84    RELEASE_ASSERT(index < runs.size());
     85    return index;
    8486}
    8587
    86 TextRunIterator InlineContent::iteratorForTextRun(const Run& run) const
     88const Run* InlineContent::firstRunForLayoutBox(const Layout::Box& layoutBox) const
    8789{
    88     ASSERT(run.text());
    89     return { RunIteratorModernPath { *this, static_cast<size_t>(&run - runs.begin()) } };
     90    auto index = firstRunIndexForLayoutBox(layoutBox);
     91    return index ? &runs[*index] : nullptr;
     92}
     93
     94std::optional<size_t> InlineContent::firstRunIndexForLayoutBox(const Layout::Box& layoutBox) const
     95{
     96    constexpr auto cacheThreshold = 16;
     97
     98    if (runs.size() < cacheThreshold) {
     99        for (size_t i = 0; i < runs.size(); ++i) {
     100            auto& run = runs[i];
     101            if (&run.layoutBox() == &layoutBox)
     102                return i;
     103        }
     104        return { };
     105    }
     106   
     107    if (!m_firstRunIndexCache) {
     108        m_firstRunIndexCache = makeUnique<FirstRunIndexCache>();
     109        for (size_t i = 0; i < runs.size(); ++i) {
     110            auto& run = runs[i];
     111            if (run.isRootInlineBox())
     112                continue;
     113            m_firstRunIndexCache->add(run.layoutBox(), i);
     114        }
     115    }
     116
     117    auto it = m_firstRunIndexCache->find(layoutBox);
     118    if (it == m_firstRunIndexCache->end())
     119        return { };
     120
     121    return it->value;
     122}
     123
     124const Vector<size_t>& InlineContent::nonRootInlineBoxIndexesForLayoutBox(const Layout::Box& layoutBox) const
     125{
     126    ASSERT(layoutBox.isContainerBox());
     127
     128    if (!m_inlineBoxIndexCache) {
     129        m_inlineBoxIndexCache = makeUnique<InlineBoxIndexCache>();
     130        for (size_t i = 0; i < runs.size(); ++i) {
     131            auto& run = runs[i];
     132            if (!run.isNonRootInlineBox())
     133                continue;
     134            m_inlineBoxIndexCache->ensure(run.layoutBox(), [&] {
     135                return Vector<size_t> { };
     136            }).iterator->value.append(i);
     137        }
     138        for (auto entry : *m_inlineBoxIndexCache)
     139            entry.value.shrinkToFit();
     140    }
     141
     142    auto it = m_inlineBoxIndexCache->find(layoutBox);
     143    if (it == m_inlineBoxIndexCache->end()) {
     144        static NeverDestroyed<Vector<size_t>> emptyVector;
     145        return emptyVector.get();
     146    }
     147
     148    return it->value;
     149}
     150
     151void InlineContent::releaseCaches()
     152{
     153    m_firstRunIndexCache = { };
     154    m_inlineBoxIndexCache = { };
     155}
     156
     157void InlineContent::shrinkToFit()
     158{
     159    runs.shrinkToFit();
     160    lines.shrinkToFit();
    90161}
    91162

  • trunk/Source/WebCore/layout/integration/LayoutIntegrationInlineContent.h

    r282072 r282211  
    3232#include <wtf/IteratorRange.h>
    3333#include <wtf/Vector.h>
     34#include <wtf/WeakHashMap.h>
    3435#include <wtf/WeakPtr.h>
    3536
    … …  
    4647
    4748class LineLayout;
    48 class RunIterator;
    49 class TextRunIterator;
    5049
    5150using Run = Layout::Run;
    … …  
    7372    const RenderBlockFlow& containingBlock() const;
    7473
    75     RunIterator iteratorForRun(const Run&) const;
    76     TextRunIterator iteratorForTextRun(const Run&) const;
     74    size_t indexForRun(const Run&) const;
     75
     76    const Run* firstRunForLayoutBox(const Layout::Box&) const;
     77    template<typename Function> void traverseNonRootInlineBoxes(const Layout::Box&, Function&&);
     78
     79    std::optional<size_t> firstRunIndexForLayoutBox(const Layout::Box&) const;
     80    const Vector<size_t>& nonRootInlineBoxIndexesForLayoutBox(const Layout::Box&) const;
     81
     82    void releaseCaches();
    7783
    7884private:
    … …  
    8086
    8187    WeakPtr<const LineLayout> m_lineLayout;
     88
     89    using FirstRunIndexCache = WeakHashMap<Layout::Box, size_t>;
     90    mutable std::unique_ptr<FirstRunIndexCache> m_firstRunIndexCache;
     91
     92    using InlineBoxIndexCache = WeakHashMap<Layout::Box, Vector<size_t>>;
     93    mutable std::unique_ptr<InlineBoxIndexCache> m_inlineBoxIndexCache;
    8294};
    8395
    84 inline void InlineContent::shrinkToFit()
     96template<typename Function> void InlineContent::traverseNonRootInlineBoxes(const Layout::Box& layoutBox, Function&& function)
    8597{
    86     runs.shrinkToFit();
    87     lines.shrinkToFit();
     98    for (auto index : nonRootInlineBoxIndexesForLayoutBox(layoutBox))
     99        function(runs[index]);
    88100}
    89101

  • trunk/Source/WebCore/layout/integration/LayoutIntegrationLineLayout.cpp

    r282202 r282211  
    365365    if (!m_inlineContent)
    366366        return { };
     367
    367368    auto& layoutBox = m_boxTree.layoutBoxForRenderer(renderText);
    368 
    369     auto firstIndex = [&]() -> std::optional<size_t> {
    370         for (size_t i = 0; i < m_inlineContent->runs.size(); ++i) {
    371             if (&m_inlineContent->runs[i].layoutBox() == &layoutBox)
    372                 return i;
    373         }
    374         return { };
    375     }();
    376 
     369    auto firstIndex = m_inlineContent->firstRunIndexForLayoutBox(layoutBox);
    377370    if (!firstIndex)
    378371        return { };
    379372
    380     return { RunIteratorModernPath(*m_inlineContent, *firstIndex) };
     373    return LayoutIntegration::textRunFor(*m_inlineContent, *firstIndex);
    381374}
    382375
    … …  
    385378    if (!m_inlineContent)
    386379        return { };
     380
    387381    auto& layoutBox = m_boxTree.layoutBoxForRenderer(renderElement);
    388 
    389     for (size_t i = 0; i < m_inlineContent->runs.size(); ++i) {
    390         auto& run =  m_inlineContent->runs[i];
    391         if (&run.layoutBox() == &layoutBox)
    392             return { RunIteratorModernPath(*m_inlineContent, i) };
    393     }
    394 
    395     return { };
     382    auto firstIndex = m_inlineContent->firstRunIndexForLayoutBox(layoutBox);
     383    if (!firstIndex)
     384        return { };
     385
     386    return LayoutIntegration::runFor(*m_inlineContent, *firstIndex);
    396387}
    397388
    … …  
    415406{
    416407    auto& layoutBox = m_boxTree.layoutBoxForRenderer(renderInline);
    417     for (auto& run : m_inlineContent->runs) {
    418         if (&run.layoutBox() == &layoutBox)
    419             return Layout::toLayoutRect(run.logicalRect());
    420     }
     408
     409    if (auto* run = m_inlineContent->firstRunForLayoutBox(layoutBox))
     410        return Layout::toLayoutRect(run->logicalRect());
     411
    421412    return { };
    422413}
    … …  
    436427LayoutRect LineLayout::visualOverflowBoundingBoxRectFor(const RenderInline& renderInline) const
    437428{
     429    auto& layoutBox = m_boxTree.layoutBoxForRenderer(renderInline);
     430
    438431    LayoutRect result;
     432    m_inlineContent->traverseNonRootInlineBoxes(layoutBox, [&](auto& inlineBox) {
     433        result.unite(Layout::toLayoutRect(inlineBox.inkOverflow()));
     434    });
     435
     436    return result;
     437}
     438
     439Vector<FloatRect> LineLayout::collectInlineBoxRects(const RenderInline& renderInline) const
     440{
     441    if (!m_inlineContent)
     442        return { };
    439443
    440444    auto& layoutBox = m_boxTree.layoutBoxForRenderer(renderInline);
    441     for (auto& run : m_inlineContent->runs) {
    442         if (&run.layoutBox() != &layoutBox)
    443             continue;
    444         result.unite(Layout::toLayoutRect(run.inkOverflow()));
    445     }
    446 
    447     return result;
    448 }
    449 
    450 Vector<FloatRect> LineLayout::collectInlineBoxRects(const RenderInline& renderInline) const
    451 {
    452     if (!m_inlineContent)
    453         return { };
    454445
    455446    Vector<FloatRect> result;
    456 
    457     auto& layoutBox = m_boxTree.layoutBoxForRenderer(renderInline);
    458     for (auto& run : m_inlineContent->runs) {
    459         if (&run.layoutBox() != &layoutBox)
    460             continue;
    461         result.append(run.logicalRect());
    462     }
     447    m_inlineContent->traverseNonRootInlineBoxes(layoutBox, [&](auto& inlineBox) {
     448        result.append(inlineBox.logicalRect());
     449    });
    463450
    464451    return result;
    … …  
    552539    for (auto& renderer : descendantsOfType<RenderBlockFlow>(view)) {
    553540        if (auto* lineLayout = renderer.modernLineLayout())
    554             lineLayout->releaseInlineItemCache();
    555     }
    556 }
    557 
    558 void LineLayout::releaseInlineItemCache()
     541            lineLayout->releaseCaches();
     542    }
     543}
     544
     545void LineLayout::releaseCaches()
    559546{
    560547    m_inlineFormattingState.inlineItems().clear();
     548    if (m_inlineContent)
     549        m_inlineContent->releaseCaches();
    561550}
    562551
    … …  
    631620            auto& textRenderer = downcast<RenderText>(m_boxTree.rendererForLayoutBox(run.layoutBox()));
    632621            auto decorationPainter = TextDecorationPainter { paintContext, style.textDecorationsInEffect(), textRenderer, false, fontCascade };
    633             decorationPainter.setTextRunIterator(m_inlineContent->iteratorForTextRun(run));
     622            decorationPainter.setTextRunIterator(textRunFor(*m_inlineContent, run));
    634623            decorationPainter.setWidth(runRect.width());
    635624            decorationPainter.paintTextDecoration(textRun, textOrigin, runRect.location() + physicalPaintOffset);

  • trunk/Source/WebCore/layout/integration/LayoutIntegrationLineLayout.h

    r282202 r282211  
    123123    const Layout::ContainerBox& rootLayoutBox() const;
    124124    Layout::ContainerBox& rootLayoutBox();
    125     void releaseInlineItemCache();
     125    void releaseCaches();
    126126
    127127    BoxTree m_boxTree;

  • trunk/Source/WebCore/layout/integration/LayoutIntegrationRunIterator.cpp

    r281241 r282211  
    196196}
    197197
     198TextRunIterator textRunFor(const InlineContent& content, const Run& run)
     199{
     200    return textRunFor(content, content.indexForRun(run));
     201}
     202
     203TextRunIterator textRunFor(const InlineContent& content, size_t runIndex)
     204{
     205    ASSERT(content.runs[runIndex].text());
     206    return { RunIteratorModernPath { content, runIndex } };
     207}
     208
    198209TextRunRange textRunsFor(const RenderText& text)
    199210{
    … …  
    219230}
    220231
     232RunIterator runFor(const InlineContent& content, size_t runIndex)
     233{
     234    return { RunIteratorModernPath { content, runIndex } };
     235}
     236
    221237#if ENABLE(LAYOUT_FORMATTING_CONTEXT)
    222238const RunIteratorModernPath& PathRun::modernPath() const

  • trunk/Source/WebCore/layout/integration/LayoutIntegrationRunIterator.h

    r281241 r282211  
    202202TextRunIterator firstTextRunInTextOrderFor(const RenderText&);
    203203TextRunIterator textRunFor(const LegacyInlineTextBox*);
     204TextRunIterator textRunFor(const InlineContent&, const Run&);
     205TextRunIterator textRunFor(const InlineContent&, size_t runIndex);
    204206TextRunRange textRunsFor(const RenderText&);
    205207RunIterator runFor(const RenderLineBreak&);
    206208RunIterator runFor(const RenderBox&);
     209RunIterator runFor(const InlineContent&, size_t runIndex);
    207210
    208211// -----------------------------------------------
Note: See TracChangeset for help on using the changeset viewer.