Changeset 273241 in webkit

Timestamp:

Feb 22, 2021 7:30:26 AM (3 years ago)

Author:

Antti Koivisto

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):

Location:

trunk/Source/WebCore

Files:

• ChangeLog (modified) (1 diff)
• layout/integration/LayoutIntegrationBoxTree.h (modified) (1 diff)
• layout/integration/LayoutIntegrationLineLayout.cpp (modified) (1 diff)
• layout/integration/LayoutIntegrationLineLayout.h (modified) (1 diff)
• rendering/RenderBlockFlow.cpp (modified) (2 diffs)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2021-02-22  Antti Koivisto  <antti@apple.com>
+
+        [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  <clord@igalia.com>
 

trunk/Source/WebCore/layout/integration/LayoutIntegrationBoxTree.h

@@ -57 +57 @@
     RenderObject& rendererForLayoutBox(const Layout::Box&);
 
+    size_t boxCount() const { return m_boxes.size(); }
+
 private:
     void buildTree();

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

@@ -120 +120 @@
 }
 
+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)
 {

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

@@ -67 +67 @@
     static bool canUseForAfterStyleChange(const RenderBlockFlow&, StyleDifference);
 
+    bool shouldSwitchToLegacyOnInvalidation() const;
+
     void updateReplacedDimensions(const RenderBox&);
     void updateInlineBlockDimensions(const RenderBlock&);

trunk/Source/WebCore/rendering/RenderBlockFlow.cpp

@@ -3634 +3634 @@
         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;
@@ -3642 +3644 @@
         setNeedsLayout();
         return;
+    }
     }
     ASSERT_NOT_REACHED();