- Revision
- 282211
- Author
- [email protected]
- Date
- 2021-09-09 06:59:41 -0700 (Thu, 09 Sep 2021)
Log 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:
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (282210 => 282211)
--- trunk/Source/WebCore/ChangeLog 2021-09-09 12:16:04 UTC (rev 282210)
+++ trunk/Source/WebCore/ChangeLog 2021-09-09 13:59:41 UTC (rev 282211)
@@ -1,3 +1,54 @@
+2021-09-09 Antti Koivisto <[email protected]>
+
+ 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:
+
2021-09-09 Frederic Wang <[email protected]>
Chromium test-case asserts with ASSERTION FAILED: propertyMissingOrEqualToNone
Modified: trunk/Source/WebCore/layout/integration/LayoutIntegrationInlineContent.cpp (282210 => 282211)
--- trunk/Source/WebCore/layout/integration/LayoutIntegrationInlineContent.cpp 2021-09-09 12:16:04 UTC (rev 282210)
+++ trunk/Source/WebCore/layout/integration/LayoutIntegrationInlineContent.cpp 2021-09-09 13:59:41 UTC (rev 282211)
@@ -78,18 +78,89 @@
return m_lineLayout->flow();
}
-RunIterator InlineContent::iteratorForRun(const Run& run) const
+size_t InlineContent::indexForRun(const Run& run) const
{
- return { RunIteratorModernPath { *this, static_cast<size_t>(&run - runs.begin()) } };
+ auto index = static_cast<size_t>(&run - runs.begin());
+ RELEASE_ASSERT(index < runs.size());
+ return index;
}
-TextRunIterator InlineContent::iteratorForTextRun(const Run& run) const
+const Run* InlineContent::firstRunForLayoutBox(const Layout::Box& layoutBox) const
{
- ASSERT(run.text());
- return { RunIteratorModernPath { *this, static_cast<size_t>(&run - runs.begin()) } };
+ auto index = firstRunIndexForLayoutBox(layoutBox);
+ return index ? &runs[*index] : nullptr;
}
+std::optional<size_t> InlineContent::firstRunIndexForLayoutBox(const Layout::Box& layoutBox) const
+{
+ constexpr auto cacheThreshold = 16;
+
+ if (runs.size() < cacheThreshold) {
+ for (size_t i = 0; i < runs.size(); ++i) {
+ auto& run = runs[i];
+ if (&run.layoutBox() == &layoutBox)
+ return i;
+ }
+ return { };
+ }
+
+ if (!m_firstRunIndexCache) {
+ m_firstRunIndexCache = makeUnique<FirstRunIndexCache>();
+ for (size_t i = 0; i < runs.size(); ++i) {
+ auto& run = runs[i];
+ if (run.isRootInlineBox())
+ continue;
+ m_firstRunIndexCache->add(run.layoutBox(), i);
+ }
+ }
+
+ auto it = m_firstRunIndexCache->find(layoutBox);
+ if (it == m_firstRunIndexCache->end())
+ return { };
+
+ return it->value;
}
+
+const Vector<size_t>& InlineContent::nonRootInlineBoxIndexesForLayoutBox(const Layout::Box& layoutBox) const
+{
+ ASSERT(layoutBox.isContainerBox());
+
+ if (!m_inlineBoxIndexCache) {
+ m_inlineBoxIndexCache = makeUnique<InlineBoxIndexCache>();
+ for (size_t i = 0; i < runs.size(); ++i) {
+ auto& run = runs[i];
+ if (!run.isNonRootInlineBox())
+ continue;
+ m_inlineBoxIndexCache->ensure(run.layoutBox(), [&] {
+ return Vector<size_t> { };
+ }).iterator->value.append(i);
+ }
+ for (auto entry : *m_inlineBoxIndexCache)
+ entry.value.shrinkToFit();
+ }
+
+ auto it = m_inlineBoxIndexCache->find(layoutBox);
+ if (it == m_inlineBoxIndexCache->end()) {
+ static NeverDestroyed<Vector<size_t>> emptyVector;
+ return emptyVector.get();
+ }
+
+ return it->value;
}
+void InlineContent::releaseCaches()
+{
+ m_firstRunIndexCache = { };
+ m_inlineBoxIndexCache = { };
+}
+
+void InlineContent::shrinkToFit()
+{
+ runs.shrinkToFit();
+ lines.shrinkToFit();
+}
+
+}
+}
+
#endif
Modified: trunk/Source/WebCore/layout/integration/LayoutIntegrationInlineContent.h (282210 => 282211)
--- trunk/Source/WebCore/layout/integration/LayoutIntegrationInlineContent.h 2021-09-09 12:16:04 UTC (rev 282210)
+++ trunk/Source/WebCore/layout/integration/LayoutIntegrationInlineContent.h 2021-09-09 13:59:41 UTC (rev 282211)
@@ -31,6 +31,7 @@
#include "LayoutIntegrationLine.h"
#include <wtf/IteratorRange.h>
#include <wtf/Vector.h>
+#include <wtf/WeakHashMap.h>
#include <wtf/WeakPtr.h>
namespace WebCore {
@@ -45,8 +46,6 @@
namespace LayoutIntegration {
class LineLayout;
-class RunIterator;
-class TextRunIterator;
using Run = Layout::Run;
@@ -72,19 +71,32 @@
const RenderObject& rendererForLayoutBox(const Layout::Box&) const;
const RenderBlockFlow& containingBlock() const;
- RunIterator iteratorForRun(const Run&) const;
- TextRunIterator iteratorForTextRun(const Run&) const;
+ size_t indexForRun(const Run&) const;
+ const Run* firstRunForLayoutBox(const Layout::Box&) const;
+ template<typename Function> void traverseNonRootInlineBoxes(const Layout::Box&, Function&&);
+
+ std::optional<size_t> firstRunIndexForLayoutBox(const Layout::Box&) const;
+ const Vector<size_t>& nonRootInlineBoxIndexesForLayoutBox(const Layout::Box&) const;
+
+ void releaseCaches();
+
private:
InlineContent(const LineLayout&);
WeakPtr<const LineLayout> m_lineLayout;
+
+ using FirstRunIndexCache = WeakHashMap<Layout::Box, size_t>;
+ mutable std::unique_ptr<FirstRunIndexCache> m_firstRunIndexCache;
+
+ using InlineBoxIndexCache = WeakHashMap<Layout::Box, Vector<size_t>>;
+ mutable std::unique_ptr<InlineBoxIndexCache> m_inlineBoxIndexCache;
};
-inline void InlineContent::shrinkToFit()
+template<typename Function> void InlineContent::traverseNonRootInlineBoxes(const Layout::Box& layoutBox, Function&& function)
{
- runs.shrinkToFit();
- lines.shrinkToFit();
+ for (auto index : nonRootInlineBoxIndexesForLayoutBox(layoutBox))
+ function(runs[index]);
}
}
Modified: trunk/Source/WebCore/layout/integration/LayoutIntegrationLineLayout.cpp (282210 => 282211)
--- trunk/Source/WebCore/layout/integration/LayoutIntegrationLineLayout.cpp 2021-09-09 12:16:04 UTC (rev 282210)
+++ trunk/Source/WebCore/layout/integration/LayoutIntegrationLineLayout.cpp 2021-09-09 13:59:41 UTC (rev 282211)
@@ -364,20 +364,13 @@
{
if (!m_inlineContent)
return { };
+
auto& layoutBox = m_boxTree.layoutBoxForRenderer(renderText);
-
- auto firstIndex = [&]() -> std::optional<size_t> {
- for (size_t i = 0; i < m_inlineContent->runs.size(); ++i) {
- if (&m_inlineContent->runs[i].layoutBox() == &layoutBox)
- return i;
- }
- return { };
- }();
-
+ auto firstIndex = m_inlineContent->firstRunIndexForLayoutBox(layoutBox);
if (!firstIndex)
return { };
- return { RunIteratorModernPath(*m_inlineContent, *firstIndex) };
+ return LayoutIntegration::textRunFor(*m_inlineContent, *firstIndex);
}
RunIterator LineLayout::runFor(const RenderElement& renderElement) const
@@ -384,15 +377,13 @@
{
if (!m_inlineContent)
return { };
+
auto& layoutBox = m_boxTree.layoutBoxForRenderer(renderElement);
+ auto firstIndex = m_inlineContent->firstRunIndexForLayoutBox(layoutBox);
+ if (!firstIndex)
+ return { };
- for (size_t i = 0; i < m_inlineContent->runs.size(); ++i) {
- auto& run = m_inlineContent->runs[i];
- if (&run.layoutBox() == &layoutBox)
- return { RunIteratorModernPath(*m_inlineContent, i) };
- }
-
- return { };
+ return LayoutIntegration::runFor(*m_inlineContent, *firstIndex);
}
LineIterator LineLayout::firstLine() const
@@ -414,10 +405,10 @@
LayoutRect LineLayout::firstInlineBoxRect(const RenderInline& renderInline) const
{
auto& layoutBox = m_boxTree.layoutBoxForRenderer(renderInline);
- for (auto& run : m_inlineContent->runs) {
- if (&run.layoutBox() == &layoutBox)
- return Layout::toLayoutRect(run.logicalRect());
- }
+
+ if (auto* run = m_inlineContent->firstRunForLayoutBox(layoutBox))
+ return Layout::toLayoutRect(run->logicalRect());
+
return { };
}
@@ -435,15 +426,13 @@
LayoutRect LineLayout::visualOverflowBoundingBoxRectFor(const RenderInline& renderInline) const
{
+ auto& layoutBox = m_boxTree.layoutBoxForRenderer(renderInline);
+
LayoutRect result;
+ m_inlineContent->traverseNonRootInlineBoxes(layoutBox, [&](auto& inlineBox) {
+ result.unite(Layout::toLayoutRect(inlineBox.inkOverflow()));
+ });
- auto& layoutBox = m_boxTree.layoutBoxForRenderer(renderInline);
- for (auto& run : m_inlineContent->runs) {
- if (&run.layoutBox() != &layoutBox)
- continue;
- result.unite(Layout::toLayoutRect(run.inkOverflow()));
- }
-
return result;
}
@@ -452,15 +441,13 @@
if (!m_inlineContent)
return { };
+ auto& layoutBox = m_boxTree.layoutBoxForRenderer(renderInline);
+
Vector<FloatRect> result;
+ m_inlineContent->traverseNonRootInlineBoxes(layoutBox, [&](auto& inlineBox) {
+ result.append(inlineBox.logicalRect());
+ });
- auto& layoutBox = m_boxTree.layoutBoxForRenderer(renderInline);
- for (auto& run : m_inlineContent->runs) {
- if (&run.layoutBox() != &layoutBox)
- continue;
- result.append(run.logicalRect());
- }
-
return result;
}
@@ -551,13 +538,15 @@
for (auto& renderer : descendantsOfType<RenderBlockFlow>(view)) {
if (auto* lineLayout = renderer.modernLineLayout())
- lineLayout->releaseInlineItemCache();
+ lineLayout->releaseCaches();
}
}
-void LineLayout::releaseInlineItemCache()
+void LineLayout::releaseCaches()
{
m_inlineFormattingState.inlineItems().clear();
+ if (m_inlineContent)
+ m_inlineContent->releaseCaches();
}
void LineLayout::paintTextRunUsingPhysicalCoordinates(PaintInfo& paintInfo, const LayoutPoint& paintOffset, const Line& line, const Run& run)
@@ -630,7 +619,7 @@
if (!style.textDecorationsInEffect().isEmpty()) {
auto& textRenderer = downcast<RenderText>(m_boxTree.rendererForLayoutBox(run.layoutBox()));
auto decorationPainter = TextDecorationPainter { paintContext, style.textDecorationsInEffect(), textRenderer, false, fontCascade };
- decorationPainter.setTextRunIterator(m_inlineContent->iteratorForTextRun(run));
+ decorationPainter.setTextRunIterator(textRunFor(*m_inlineContent, run));
decorationPainter.setWidth(runRect.width());
decorationPainter.paintTextDecoration(textRun, textOrigin, runRect.location() + physicalPaintOffset);
}
Modified: trunk/Source/WebCore/layout/integration/LayoutIntegrationLineLayout.h (282210 => 282211)
--- trunk/Source/WebCore/layout/integration/LayoutIntegrationLineLayout.h 2021-09-09 12:16:04 UTC (rev 282210)
+++ trunk/Source/WebCore/layout/integration/LayoutIntegrationLineLayout.h 2021-09-09 13:59:41 UTC (rev 282211)
@@ -122,7 +122,7 @@
const Layout::ContainerBox& rootLayoutBox() const;
Layout::ContainerBox& rootLayoutBox();
- void releaseInlineItemCache();
+ void releaseCaches();
BoxTree m_boxTree;
Layout::LayoutState m_layoutState;
Modified: trunk/Source/WebCore/layout/integration/LayoutIntegrationRunIterator.cpp (282210 => 282211)
--- trunk/Source/WebCore/layout/integration/LayoutIntegrationRunIterator.cpp 2021-09-09 12:16:04 UTC (rev 282210)
+++ trunk/Source/WebCore/layout/integration/LayoutIntegrationRunIterator.cpp 2021-09-09 13:59:41 UTC (rev 282211)
@@ -195,6 +195,17 @@
return { RunIteratorLegacyPath { legacyInlineTextBox } };
}
+TextRunIterator textRunFor(const InlineContent& content, const Run& run)
+{
+ return textRunFor(content, content.indexForRun(run));
+}
+
+TextRunIterator textRunFor(const InlineContent& content, size_t runIndex)
+{
+ ASSERT(content.runs[runIndex].text());
+ return { RunIteratorModernPath { content, runIndex } };
+}
+
TextRunRange textRunsFor(const RenderText& text)
{
return { firstTextRunFor(text) };
@@ -218,6 +229,11 @@
return { RunIteratorLegacyPath(renderer.inlineBoxWrapper()) };
}
+RunIterator runFor(const InlineContent& content, size_t runIndex)
+{
+ return { RunIteratorModernPath { content, runIndex } };
+}
+
#if ENABLE(LAYOUT_FORMATTING_CONTEXT)
const RunIteratorModernPath& PathRun::modernPath() const
{
Modified: trunk/Source/WebCore/layout/integration/LayoutIntegrationRunIterator.h (282210 => 282211)
--- trunk/Source/WebCore/layout/integration/LayoutIntegrationRunIterator.h 2021-09-09 12:16:04 UTC (rev 282210)
+++ trunk/Source/WebCore/layout/integration/LayoutIntegrationRunIterator.h 2021-09-09 13:59:41 UTC (rev 282211)
@@ -201,9 +201,12 @@
TextRunIterator firstTextRunFor(const RenderText&);
TextRunIterator firstTextRunInTextOrderFor(const RenderText&);
TextRunIterator textRunFor(const LegacyInlineTextBox*);
+TextRunIterator textRunFor(const InlineContent&, const Run&);
+TextRunIterator textRunFor(const InlineContent&, size_t runIndex);
TextRunRange textRunsFor(const RenderText&);
RunIterator runFor(const RenderLineBreak&);
RunIterator runFor(const RenderBox&);
+RunIterator runFor(const InlineContent&, size_t runIndex);
// -----------------------------------------------
