Changeset 269916 in webkit


Ignore:
Timestamp:
Nov 17, 2020 12:24:20 PM (3 years ago)
Author:
Antti Koivisto
Message:

[LFC][Integration] Cache inline boxes in logical order to run iterator
https://bugs.webkit.org/show_bug.cgi?id=219031

Reviewed by Zalan Bujtas.

Expand use of the existing cache to cover line traversal. This will make porting code in VisibleUnit.cpp to iterator easier.

Also a bunch of related cleanups.

  • layout/integration/LayoutIntegrationLineIterator.cpp:

(WebCore::LayoutIntegration::LineIterator::logicalStartRun const):
(WebCore::LayoutIntegration::LineIterator::logicalEndRun const):
(WebCore::LayoutIntegration::LineIterator::logicalStartRunWithNode const):
(WebCore::LayoutIntegration::LineIterator::logicalEndRunWithNode const):

  • layout/integration/LayoutIntegrationLineIterator.h:
  • layout/integration/LayoutIntegrationLineIteratorLegacyPath.h:

(WebCore::LayoutIntegration::LineIteratorLegacyPath::logicalStartRun const):
(WebCore::LayoutIntegration::LineIteratorLegacyPath::logicalEndRun const):
(WebCore::LayoutIntegration::LineIteratorLegacyPath::logicalStartRunWithNode const): Deleted.
(WebCore::LayoutIntegration::LineIteratorLegacyPath::logicalEndRunWithNode const): Deleted.

  • layout/integration/LayoutIntegrationLineIteratorModernPath.h:

(WebCore::LayoutIntegration::LineIteratorModernPath::logicalStartRun const):
(WebCore::LayoutIntegration::LineIteratorModernPath::logicalEndRun const):
(WebCore::LayoutIntegration::LineIteratorModernPath::logicalStartRunWithNode const): Deleted.
(WebCore::LayoutIntegration::LineIteratorModernPath::logicalEndRunWithNode const): Deleted.

  • layout/integration/LayoutIntegrationRunIterator.cpp:

(WebCore::LayoutIntegration::RunIterator::traverseNextOnLineInLogicalOrder):
(WebCore::LayoutIntegration::RunIterator::traversePreviousOnLineInLogicalOrder):
(WebCore::LayoutIntegration::firstTextRunInTextOrderFor):

  • layout/integration/LayoutIntegrationRunIterator.h:
  • layout/integration/LayoutIntegrationRunIteratorLegacyPath.h:

(WebCore::LayoutIntegration::RunIteratorLegacyPath::RunIteratorLegacyPath):
(WebCore::LayoutIntegration::RunIteratorLegacyPath::traverseNextTextRunInTextOrder):
(WebCore::LayoutIntegration::RunIteratorLegacyPath::traverseNextOnLineInLogicalOrder):
(WebCore::LayoutIntegration::RunIteratorLegacyPath::traversePreviousOnLineInLogicalOrder):
(WebCore::LayoutIntegration::RunIteratorLegacyPath::inlineTextBox const):
(WebCore::LayoutIntegration::RunIteratorLegacyPath::initializeLogicalOrderCacheForLine):
(WebCore::LayoutIntegration::RunIteratorLegacyPath::traverseNextInlineBoxInCacheOrder):
(WebCore::LayoutIntegration::RunIteratorLegacyPath::traversePreviousInlineBoxInCacheOrder):
(WebCore::LayoutIntegration::RunIteratorLegacyPath::nextInlineTextBoxInTextOrder const): Deleted.

  • layout/integration/LayoutIntegrationRunIteratorModernPath.h:

(WebCore::LayoutIntegration::RunIteratorModernPath::traverseNextOnLineInLogicalOrder):
(WebCore::LayoutIntegration::RunIteratorModernPath::traversePreviousOnLineInLogicalOrder):

  • rendering/RootInlineBox.cpp:

(WebCore::RootInlineBox::getLogicalStartBoxWithNode const): Deleted.
(WebCore::RootInlineBox::getLogicalEndBoxWithNode const): Deleted.

  • rendering/RootInlineBox.h:
Location:
trunk/Source/WebCore
Files:
11 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/WebCore/ChangeLog

    r269915 r269916  
     12020-11-17  Antti Koivisto  <antti@apple.com>
     2
     3        [LFC][Integration] Cache inline boxes in logical order to run iterator
     4        https://bugs.webkit.org/show_bug.cgi?id=219031
     5
     6        Reviewed by Zalan Bujtas.
     7
     8        Expand use of the existing cache to cover line traversal. This will make porting code in VisibleUnit.cpp to iterator easier.
     9
     10        Also a bunch of related cleanups.
     11
     12        * layout/integration/LayoutIntegrationLineIterator.cpp:
     13        (WebCore::LayoutIntegration::LineIterator::logicalStartRun const):
     14        (WebCore::LayoutIntegration::LineIterator::logicalEndRun const):
     15        (WebCore::LayoutIntegration::LineIterator::logicalStartRunWithNode const):
     16        (WebCore::LayoutIntegration::LineIterator::logicalEndRunWithNode const):
     17        * layout/integration/LayoutIntegrationLineIterator.h:
     18        * layout/integration/LayoutIntegrationLineIteratorLegacyPath.h:
     19        (WebCore::LayoutIntegration::LineIteratorLegacyPath::logicalStartRun const):
     20        (WebCore::LayoutIntegration::LineIteratorLegacyPath::logicalEndRun const):
     21        (WebCore::LayoutIntegration::LineIteratorLegacyPath::logicalStartRunWithNode const): Deleted.
     22        (WebCore::LayoutIntegration::LineIteratorLegacyPath::logicalEndRunWithNode const): Deleted.
     23        * layout/integration/LayoutIntegrationLineIteratorModernPath.h:
     24        (WebCore::LayoutIntegration::LineIteratorModernPath::logicalStartRun const):
     25        (WebCore::LayoutIntegration::LineIteratorModernPath::logicalEndRun const):
     26        (WebCore::LayoutIntegration::LineIteratorModernPath::logicalStartRunWithNode const): Deleted.
     27        (WebCore::LayoutIntegration::LineIteratorModernPath::logicalEndRunWithNode const): Deleted.
     28        * layout/integration/LayoutIntegrationRunIterator.cpp:
     29        (WebCore::LayoutIntegration::RunIterator::traverseNextOnLineInLogicalOrder):
     30        (WebCore::LayoutIntegration::RunIterator::traversePreviousOnLineInLogicalOrder):
     31        (WebCore::LayoutIntegration::firstTextRunInTextOrderFor):
     32        * layout/integration/LayoutIntegrationRunIterator.h:
     33        * layout/integration/LayoutIntegrationRunIteratorLegacyPath.h:
     34        (WebCore::LayoutIntegration::RunIteratorLegacyPath::RunIteratorLegacyPath):
     35        (WebCore::LayoutIntegration::RunIteratorLegacyPath::traverseNextTextRunInTextOrder):
     36        (WebCore::LayoutIntegration::RunIteratorLegacyPath::traverseNextOnLineInLogicalOrder):
     37        (WebCore::LayoutIntegration::RunIteratorLegacyPath::traversePreviousOnLineInLogicalOrder):
     38        (WebCore::LayoutIntegration::RunIteratorLegacyPath::inlineTextBox const):
     39        (WebCore::LayoutIntegration::RunIteratorLegacyPath::initializeLogicalOrderCacheForLine):
     40        (WebCore::LayoutIntegration::RunIteratorLegacyPath::traverseNextInlineBoxInCacheOrder):
     41        (WebCore::LayoutIntegration::RunIteratorLegacyPath::traversePreviousInlineBoxInCacheOrder):
     42        (WebCore::LayoutIntegration::RunIteratorLegacyPath::nextInlineTextBoxInTextOrder const): Deleted.
     43        * layout/integration/LayoutIntegrationRunIteratorModernPath.h:
     44        (WebCore::LayoutIntegration::RunIteratorModernPath::traverseNextOnLineInLogicalOrder):
     45        (WebCore::LayoutIntegration::RunIteratorModernPath::traversePreviousOnLineInLogicalOrder):
     46        * rendering/RootInlineBox.cpp:
     47        (WebCore::RootInlineBox::getLogicalStartBoxWithNode const): Deleted.
     48        (WebCore::RootInlineBox::getLogicalEndBoxWithNode const): Deleted.
     49        * rendering/RootInlineBox.h:
     50
    1512020-11-17  Megan Gardner  <megan_gardner@apple.com>
    252
  • trunk/Source/WebCore/layout/integration/LayoutIntegrationLineIterator.cpp

    r269852 r269916  
    9191}
    9292
     93RunIterator LineIterator::logicalStartRun() const
     94{
     95    return WTF::switchOn(m_line.m_pathVariant, [](auto& path) -> RunIterator {
     96        return { path.logicalStartRun() };
     97    });
     98}
     99
     100RunIterator LineIterator::logicalEndRun() const
     101{
     102    return WTF::switchOn(m_line.m_pathVariant, [](auto& path) -> RunIterator {
     103        return { path.logicalEndRun() };
     104    });
     105}
     106
    93107RunIterator LineIterator::logicalStartRunWithNode() const
    94108{
    95     return WTF::switchOn(m_line.m_pathVariant, [](auto& path) -> RunIterator {
    96         return { path.logicalStartRunWithNode() };
    97     });
     109    for (auto run = logicalStartRun(); run; run.traverseNextOnLineInLogicalOrder()) {
     110        if (run->renderer().node())
     111            return run;
     112    }
     113    return { };
    98114}
    99115
    100116RunIterator LineIterator::logicalEndRunWithNode() const
    101117{
    102     return WTF::switchOn(m_line.m_pathVariant, [](auto& path) -> RunIterator {
    103         return { path.logicalEndRunWithNode() };
    104     });
     118    for (auto run = logicalEndRun(); run; run.traversePreviousOnLineInLogicalOrder()) {
     119        if (run->renderer().node())
     120            return run;
     121    }
     122    return { };
    105123}
    106124
  • trunk/Source/WebCore/layout/integration/LayoutIntegrationLineIterator.h

    r269732 r269916  
    107107    RunIterator firstRun() const;
    108108    RunIterator lastRun() const;
     109
     110    RunIterator closestRunForPoint(const IntPoint& pointInContents, bool editableOnly);
     111    RunIterator closestRunForLogicalLeftPosition(int position, bool editableOnly = false);
     112
     113    RunIterator logicalStartRun() const;
     114    RunIterator logicalEndRun() const;
    109115    RunIterator logicalStartRunWithNode() const;
    110116    RunIterator logicalEndRunWithNode() const;
    111     RunIterator closestRunForPoint(const IntPoint& pointInContents, bool editableOnly);
    112     RunIterator closestRunForLogicalLeftPosition(int position, bool editableOnly = false);
    113117
    114118private:
  • trunk/Source/WebCore/layout/integration/LayoutIntegrationLineIteratorLegacyPath.h

    r269510 r269916  
    8787    }
    8888
    89     RunIteratorLegacyPath logicalStartRunWithNode() const
     89
     90    RunIteratorLegacyPath logicalStartRun() const
    9091    {
    91         InlineBox* box = nullptr;
    92         m_rootInlineBox->getLogicalStartBoxWithNode(box);
    93         return { box };
     92        return { *m_rootInlineBox, RunIteratorLegacyPath::LogicalOrder::Start };
    9493    }
    9594
    96     RunIteratorLegacyPath logicalEndRunWithNode() const
     95    RunIteratorLegacyPath logicalEndRun() const
    9796    {
    98         InlineBox* box = nullptr;
    99         m_rootInlineBox->getLogicalEndBoxWithNode(box);
    100         return { box };
     97        return { *m_rootInlineBox, RunIteratorLegacyPath::LogicalOrder::End };
    10198    }
    10299
    103100private:
    104 
    105101    const RootInlineBox* m_rootInlineBox;
    106102};
  • trunk/Source/WebCore/layout/integration/LayoutIntegrationLineIteratorModernPath.h

    r269571 r269916  
    108108    }
    109109
    110     RunIteratorModernPath logicalStartRunWithNode() const
     110    RunIteratorModernPath logicalStartRun() const
    111111    {
    112         auto startIndex = line().firstRunIndex();
    113         auto endIndex = startIndex + line().runCount();
    114         for (auto runIndex = startIndex; runIndex < endIndex; ++runIndex) {
    115             auto& renderer = m_inlineContent->rendererForLayoutBox(m_inlineContent->runs[runIndex].layoutBox());
    116             if (renderer.node())
    117                 return { *m_inlineContent, runIndex };
    118         }
    119         return { *m_inlineContent };
     112        return firstRun();
    120113    }
    121114
    122     RunIteratorModernPath logicalEndRunWithNode() const
     115    RunIteratorModernPath logicalEndRun() const
    123116    {
    124         auto startIndex = line().firstRunIndex();
    125         auto endIndex = startIndex + line().runCount();
    126         for (auto runIndex = endIndex; runIndex-- > startIndex;) {
    127             auto& renderer = m_inlineContent->rendererForLayoutBox(m_inlineContent->runs[runIndex].layoutBox());
    128             if (renderer.node())
    129                 return { *m_inlineContent, runIndex };
    130         }
    131         return { *m_inlineContent };
     117        return lastRun();
    132118    }
     119
    133120
    134121private:
  • trunk/Source/WebCore/layout/integration/LayoutIntegrationRunIterator.cpp

    r269852 r269916  
    146146}
    147147
     148RunIterator& RunIterator::traverseNextOnLineInLogicalOrder()
     149{
     150    WTF::switchOn(m_run.m_pathVariant, [](auto& path) {
     151        path.traverseNextOnLineInLogicalOrder();
     152    });
     153    return *this;
     154}
     155
     156RunIterator& RunIterator::traversePreviousOnLineInLogicalOrder()
     157{
     158    WTF::switchOn(m_run.m_pathVariant, [](auto& path) {
     159        path.traversePreviousOnLineInLogicalOrder();
     160    });
     161    return *this;
     162}
     163
    148164TextRunIterator firstTextRunFor(const RenderText& text)
    149165{
     
    159175{
    160176    if (text.firstTextBox() && text.containsReversedText()) {
    161         Vector<const InlineTextBox*> sortedTextBoxes;
     177        Vector<const InlineBox*> sortedTextBoxes;
    162178        for (auto* textBox = text.firstTextBox(); textBox; textBox = textBox->nextTextBox())
    163179            sortedTextBoxes.append(textBox);
    164         std::sort(sortedTextBoxes.begin(), sortedTextBoxes.end(), InlineTextBox::compareByStart);
     180        std::sort(sortedTextBoxes.begin(), sortedTextBoxes.end(), [](auto* a, auto* b) {
     181            return InlineTextBox::compareByStart(downcast<InlineTextBox>(a), downcast<InlineTextBox>(b));
     182        });
    165183        auto* first = sortedTextBoxes[0];
    166184        return { RunIteratorLegacyPath { first, WTFMove(sortedTextBoxes), 0 } };
  • trunk/Source/WebCore/layout/integration/LayoutIntegrationRunIterator.h

    r269852 r269916  
    142142    RunIterator& traverseNextOnLineIgnoringLineBreak();
    143143    RunIterator& traversePreviousOnLineIgnoringLineBreak();
     144    RunIterator& traverseNextOnLineInLogicalOrder();
     145    RunIterator& traversePreviousOnLineInLogicalOrder();
    144146
    145147    LineIterator line() const;
     
    172174    RunIterator& traverseNextOnLineIgnoringLineBreak() = delete;
    173175    RunIterator& traversePreviousOnLineIgnoringLineBreak() = delete;
     176    RunIterator& traverseNextOnLineInLogicalOrder() = delete;
     177    RunIterator& traversePreviousOnLineInLogicalOrder() = delete;
    174178
    175179    const PathTextRun& get() const { return downcast<PathTextRun>(m_run); }
  • trunk/Source/WebCore/layout/integration/LayoutIntegrationRunIteratorLegacyPath.h

    r269852 r269916  
    2828#include "InlineTextBox.h"
    2929#include "RenderText.h"
     30#include "RootInlineBox.h"
    3031#include <wtf/RefCountedArray.h>
    3132#include <wtf/Vector.h>
     
    3637class RunIteratorLegacyPath {
    3738public:
    38     RunIteratorLegacyPath(const InlineBox* inlineBox, Vector<const InlineTextBox*>&& sortedInlineTextBoxes = { }, size_t sortedInlineTextBoxIndex = 0)
     39    RunIteratorLegacyPath(const InlineBox* inlineBox, Vector<const InlineBox*>&& sortedInlineBoxes = { }, size_t sortedInlineBoxIndex = 0)
    3940        : m_inlineBox(inlineBox)
    40         , m_sortedInlineTextBoxes(WTFMove(sortedInlineTextBoxes))
    41         , m_sortedInlineTextBoxIndex(sortedInlineTextBoxIndex)
     41        , m_logicalOrderCache(WTFMove(sortedInlineBoxes))
     42        , m_logicalOrderCacheIndex(sortedInlineBoxIndex)
    4243    { }
     44
     45    enum class LogicalOrder { Start, End };
     46    RunIteratorLegacyPath(const RootInlineBox& root, LogicalOrder order)
     47        : m_logicalOrderCache(inlineBoxesInLogicalOrder(root))
     48    {
     49        if (!m_logicalOrderCache.isEmpty()) {
     50            m_logicalOrderCacheIndex = order == LogicalOrder::Start ? 0 : m_logicalOrderCache.size() - 1;
     51            m_inlineBox = m_logicalOrderCache[m_logicalOrderCacheIndex];
     52        }
     53    }
    4354
    4455    bool isText() const { return m_inlineBox->isInlineTextBox(); }
     
    7586    void traverseNextTextRunInTextOrder()
    7687    {
    77         m_inlineBox = nextInlineTextBoxInTextOrder();
    78         if (!m_sortedInlineTextBoxes.isEmpty())
    79             ++m_sortedInlineTextBoxIndex;
     88        if (!m_logicalOrderCache.isEmpty()) {
     89            traverseNextInlineBoxInCacheOrder();
     90            ASSERT(!m_inlineBox || is<InlineTextBox>(m_inlineBox));
     91            return;
     92        }
     93        traverseNextTextRun();
    8094    }
    8195
     
    90104    }
    91105
     106    void traverseNextOnLineInLogicalOrder()
     107    {
     108        initializeLogicalOrderCacheForLine();
     109        traverseNextInlineBoxInCacheOrder();
     110    }
     111
     112    void traversePreviousOnLineInLogicalOrder()
     113    {
     114        initializeLogicalOrderCacheForLine();
     115        traversePreviousInlineBoxInCacheOrder();
     116    }
     117
    92118    bool operator==(const RunIteratorLegacyPath& other) const { return m_inlineBox == other.m_inlineBox; }
    93119
     
    100126private:
    101127    const InlineTextBox* inlineTextBox() const { return downcast<InlineTextBox>(m_inlineBox); }
    102     const InlineTextBox* nextInlineTextBoxInTextOrder() const;
    103128
    104     const InlineBox* m_inlineBox;
    105     RefCountedArray<const InlineTextBox*> m_sortedInlineTextBoxes;
    106     size_t m_sortedInlineTextBoxIndex { 0 };
     129    static Vector<const InlineBox*> inlineBoxesInLogicalOrder(const RootInlineBox& root)
     130    {
     131        Vector<InlineBox*> inlineBoxes;
     132        root.collectLeafBoxesInLogicalOrder(inlineBoxes);
     133        return reinterpret_cast<Vector<const InlineBox*>&>(inlineBoxes);
     134    }
     135    void initializeLogicalOrderCacheForLine()
     136    {
     137        if (!m_inlineBox || !m_logicalOrderCache.isEmpty())
     138            return;
     139        m_logicalOrderCache = inlineBoxesInLogicalOrder(m_inlineBox->root());
     140        for (m_logicalOrderCacheIndex = 0; m_logicalOrderCacheIndex < m_logicalOrderCache.size(); ++m_logicalOrderCacheIndex) {
     141            if (m_logicalOrderCache[m_logicalOrderCacheIndex] == m_inlineBox)
     142                return;
     143        }
     144        ASSERT_NOT_REACHED();
     145    }
     146
     147    void traverseNextInlineBoxInCacheOrder();
     148    void traversePreviousInlineBoxInCacheOrder();
     149
     150    const InlineBox* m_inlineBox { nullptr };
     151    RefCountedArray<const InlineBox*> m_logicalOrderCache;
     152    size_t m_logicalOrderCacheIndex { 0 };
    107153};
    108154
    109 inline const InlineTextBox* RunIteratorLegacyPath::nextInlineTextBoxInTextOrder() const
     155
     156inline void RunIteratorLegacyPath::traverseNextInlineBoxInCacheOrder()
    110157{
    111     if (!m_sortedInlineTextBoxes.isEmpty()) {
    112         if (m_sortedInlineTextBoxIndex + 1 < m_sortedInlineTextBoxes.size())
    113             return m_sortedInlineTextBoxes[m_sortedInlineTextBoxIndex + 1];
    114         return nullptr;
     158    ASSERT(!m_logicalOrderCache.isEmpty());
     159    ++m_logicalOrderCacheIndex;
     160    m_inlineBox = m_logicalOrderCacheIndex < m_logicalOrderCache.size() ? m_logicalOrderCache[m_logicalOrderCacheIndex] : nullptr;
     161}
     162
     163inline void RunIteratorLegacyPath::traversePreviousInlineBoxInCacheOrder()
     164{
     165    ASSERT(!m_logicalOrderCache.isEmpty());
     166    if (!m_logicalOrderCacheIndex) {
     167        m_inlineBox = nullptr;
     168        return;
    115169    }
    116     return inlineTextBox()->nextTextBox();
     170    m_inlineBox = m_logicalOrderCache[--m_logicalOrderCacheIndex];
    117171}
    118172
  • trunk/Source/WebCore/layout/integration/LayoutIntegrationRunIteratorModernPath.h

    r269852 r269916  
    183183    }
    184184
     185    void traverseNextOnLineInLogicalOrder()
     186    {
     187        traverseNextOnLine();
     188    }
     189
     190    void traversePreviousOnLineInLogicalOrder()
     191    {
     192        traversePreviousOnLine();
     193    }
     194
    185195    bool operator==(const RunIteratorModernPath& other) const { return m_inlineContent == other.m_inlineContent && m_runIndex == other.m_runIndex; }
    186196
  • trunk/Source/WebCore/rendering/RootInlineBox.cpp

    r269510 r269916  
    10241024}
    10251025
    1026 Node* RootInlineBox::getLogicalStartBoxWithNode(InlineBox*& startBox) const
    1027 {
    1028     Vector<InlineBox*> leafBoxesInLogicalOrder;
    1029     collectLeafBoxesInLogicalOrder(leafBoxesInLogicalOrder);
    1030     for (size_t i = 0; i < leafBoxesInLogicalOrder.size(); ++i) {
    1031         if (leafBoxesInLogicalOrder[i]->renderer().node()) {
    1032             startBox = leafBoxesInLogicalOrder[i];
    1033             return startBox->renderer().node();
    1034         }
    1035     }
    1036     startBox = nullptr;
    1037     return nullptr;
    1038 }
    1039    
    1040 Node* RootInlineBox::getLogicalEndBoxWithNode(InlineBox*& endBox) const
    1041 {
    1042     Vector<InlineBox*> leafBoxesInLogicalOrder;
    1043     collectLeafBoxesInLogicalOrder(leafBoxesInLogicalOrder);
    1044     for (size_t i = leafBoxesInLogicalOrder.size(); i > 0; --i) {
    1045         if (leafBoxesInLogicalOrder[i - 1]->renderer().node()) {
    1046             endBox = leafBoxesInLogicalOrder[i - 1];
    1047             return endBox->renderer().node();
    1048         }
    1049     }
    1050     endBox = nullptr;
    1051     return nullptr;
    1052 }
    1053 
    10541026#if ENABLE(TREE_DEBUGGING)
    10551027
  • trunk/Source/WebCore/rendering/RootInlineBox.h

    r269510 r269916  
    185185    }
    186186
    187     Node* getLogicalStartBoxWithNode(InlineBox*&) const;
    188     Node* getLogicalEndBoxWithNode(InlineBox*&) const;
    189 
    190187    virtual bool isTrailingFloatsRootInlineBox() const { return false; }
    191188
Note: See TracChangeset for help on using the changeset viewer.