Title: [273241] trunk/Source/WebCore
- Revision
- 273241
- Author
- [email protected]
- Date
- 2021-02-22 07:30:26 -0800 (Mon, 22 Feb 2021)
Log Message
[LFC][Integration] Switch out if large trees are being invalidated
https://bugs.webkit.org/show_bug.cgi?id=222264
Reviewed by Zalan Bujtas.
We don't support partial invalidation yet. To avoid hitting bad O(n^2) cases limit the maximum tree size on invalidation.
Prevents editing/selection/move-by-character-brute-force.html, fast/innerHTML/identical-mutations.html and fast/text/emoji-num-glyphs.html
from timing out in debug.
* layout/integration/LayoutIntegrationBoxTree.h:
(WebCore::LayoutIntegration::BoxTree::boxCount const):
* layout/integration/LayoutIntegrationLineLayout.cpp:
(WebCore::LayoutIntegration::LineLayout::shouldSwitchToLegacyOnInvalidation const):
* layout/integration/LayoutIntegrationLineLayout.h:
* rendering/RenderBlockFlow.cpp:
(WebCore::RenderBlockFlow::invalidateLineLayoutPath):
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (273240 => 273241)
--- trunk/Source/WebCore/ChangeLog 2021-02-22 12:27:44 UTC (rev 273240)
+++ trunk/Source/WebCore/ChangeLog 2021-02-22 15:30:26 UTC (rev 273241)
@@ -1,3 +1,23 @@
+2021-02-22 Antti Koivisto <[email protected]>
+
+ [LFC][Integration] Switch out if large trees are being invalidated
+ https://bugs.webkit.org/show_bug.cgi?id=222264
+
+ Reviewed by Zalan Bujtas.
+
+ We don't support partial invalidation yet. To avoid hitting bad O(n^2) cases limit the maximum tree size on invalidation.
+
+ Prevents editing/selection/move-by-character-brute-force.html, fast/innerHTML/identical-mutations.html and fast/text/emoji-num-glyphs.html
+ from timing out in debug.
+
+ * layout/integration/LayoutIntegrationBoxTree.h:
+ (WebCore::LayoutIntegration::BoxTree::boxCount const):
+ * layout/integration/LayoutIntegrationLineLayout.cpp:
+ (WebCore::LayoutIntegration::LineLayout::shouldSwitchToLegacyOnInvalidation const):
+ * layout/integration/LayoutIntegrationLineLayout.h:
+ * rendering/RenderBlockFlow.cpp:
+ (WebCore::RenderBlockFlow::invalidateLineLayoutPath):
+
2021-02-22 Chris Lord <[email protected]>
Move FontCascadeCache onto FontCache
Modified: trunk/Source/WebCore/layout/integration/LayoutIntegrationBoxTree.h (273240 => 273241)
--- trunk/Source/WebCore/layout/integration/LayoutIntegrationBoxTree.h 2021-02-22 12:27:44 UTC (rev 273240)
+++ trunk/Source/WebCore/layout/integration/LayoutIntegrationBoxTree.h 2021-02-22 15:30:26 UTC (rev 273241)
@@ -56,6 +56,8 @@
const RenderObject& rendererForLayoutBox(const Layout::Box&) const;
RenderObject& rendererForLayoutBox(const Layout::Box&);
+ size_t boxCount() const { return m_boxes.size(); }
+
private:
void buildTree();
void appendChild(std::unique_ptr<Layout::Box>, RenderObject&);
Modified: trunk/Source/WebCore/layout/integration/LayoutIntegrationLineLayout.cpp (273240 => 273241)
--- trunk/Source/WebCore/layout/integration/LayoutIntegrationLineLayout.cpp 2021-02-22 12:27:44 UTC (rev 273240)
+++ trunk/Source/WebCore/layout/integration/LayoutIntegrationLineLayout.cpp 2021-02-22 15:30:26 UTC (rev 273241)
@@ -119,6 +119,14 @@
return canUseForLineLayoutAfterStyleChange(flow, diff);
}
+bool LineLayout::shouldSwitchToLegacyOnInvalidation() const
+{
+ // FIXME: Support partial invalidation in LFC.
+ // This avoids O(n^2) when lots of boxes are being added dynamically while forcing layouts between.
+ constexpr size_t maximimumBoxTreeSizeForInvalidation = 128;
+ return m_boxTree.boxCount() > maximimumBoxTreeSizeForInvalidation;
+}
+
void LineLayout::updateReplacedDimensions(const RenderBox& replaced)
{
updateLayoutBoxDimensions(replaced);
Modified: trunk/Source/WebCore/layout/integration/LayoutIntegrationLineLayout.h (273240 => 273241)
--- trunk/Source/WebCore/layout/integration/LayoutIntegrationLineLayout.h 2021-02-22 12:27:44 UTC (rev 273240)
+++ trunk/Source/WebCore/layout/integration/LayoutIntegrationLineLayout.h 2021-02-22 15:30:26 UTC (rev 273241)
@@ -66,6 +66,8 @@
static bool canUseFor(const RenderBlockFlow&);
static bool canUseForAfterStyleChange(const RenderBlockFlow&, StyleDifference);
+ bool shouldSwitchToLegacyOnInvalidation() const;
+
void updateReplacedDimensions(const RenderBox&);
void updateInlineBlockDimensions(const RenderBlock&);
void updateLineBreakBoxDimensions(const RenderLineBreak&);
Modified: trunk/Source/WebCore/rendering/RenderBlockFlow.cpp (273240 => 273241)
--- trunk/Source/WebCore/rendering/RenderBlockFlow.cpp 2021-02-22 12:27:44 UTC (rev 273240)
+++ trunk/Source/WebCore/rendering/RenderBlockFlow.cpp 2021-02-22 15:30:26 UTC (rev 273241)
@@ -3633,9 +3633,11 @@
case LineBoxesPath:
setLineLayoutPath(UndeterminedPath);
return;
- case ModernPath: // FIXME: Not all clients of invalidateLineLayoutPath() actually need to wipe the layout.
+ case ModernPath: {
+ // FIXME: Implement partial invalidation.
+ auto path = modernLineLayout() && modernLineLayout()->shouldSwitchToLegacyOnInvalidation() ? ForceLineBoxesPath : UndeterminedPath;
m_lineLayout = WTF::Monostate();
- setLineLayoutPath(UndeterminedPath);
+ setLineLayoutPath(path);
if (needsLayout())
return;
// FIXME: We should just kick off a subtree layout here (if needed at all) see webkit.org/b/172947.
@@ -3642,6 +3644,7 @@
setNeedsLayout();
return;
}
+ }
ASSERT_NOT_REACHED();
}
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
