RenderBlockFlow::layoutRunsAndFloatsInRange is O(n^2) for runs of inlines without...
authorantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 23 Nov 2017 10:45:26 +0000 (10:45 +0000)
committerantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 23 Nov 2017 10:45:26 +0000 (10:45 +0000)
https://bugs.webkit.org/show_bug.cgi?id=179950

Reviewed by Simon Fraser.

It calls createBidiRunsForLine for each line. createBidiRunsForLine traverses past the end of the line until
it finds the end of the current bidi run. If there is no text in the flow, it never finds anything and traverses
the entire flow. This is O(n^2) for the number of renderers in the flow.

Tested by PerformanceTests/Layout/inline-layout-no-text.html

* platform/text/BidiResolver.h:
(WebCore::BidiResolverBase::needsContinuePastEnd const):
(WebCore::BidiResolverBase::needsContinuePastEndInternal const):
(WebCore::DerivedClass>::createBidiRunsForLine):

    When past end of line call needsContinuePastEnd() to see if we need to continue searching for the end of the bidi run.

* rendering/InlineIterator.h:
(WebCore::InlineBidiResolver::needsContinuePastEndInternal const):

    InlineBidiResolver only returns runs up to the last renderer on the line and can bail out.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@225110 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/ChangeLog
Source/WebCore/platform/text/BidiResolver.h
Source/WebCore/rendering/InlineIterator.h

index c2c82b3..8c6de0f 100644 (file)
@@ -1,3 +1,28 @@
+2017-11-23  Antti Koivisto  <antti@apple.com>
+
+        RenderBlockFlow::layoutRunsAndFloatsInRange is O(n^2) for runs of inlines without any text
+        https://bugs.webkit.org/show_bug.cgi?id=179950
+
+        Reviewed by Simon Fraser.
+
+        It calls createBidiRunsForLine for each line. createBidiRunsForLine traverses past the end of the line until
+        it finds the end of the current bidi run. If there is no text in the flow, it never finds anything and traverses
+        the entire flow. This is O(n^2) for the number of renderers in the flow.
+
+        Tested by PerformanceTests/Layout/inline-layout-no-text.html
+
+        * platform/text/BidiResolver.h:
+        (WebCore::BidiResolverBase::needsContinuePastEnd const):
+        (WebCore::BidiResolverBase::needsContinuePastEndInternal const):
+        (WebCore::DerivedClass>::createBidiRunsForLine):
+
+            When past end of line call needsContinuePastEnd() to see if we need to continue searching for the end of the bidi run.
+
+        * rendering/InlineIterator.h:
+        (WebCore::InlineBidiResolver::needsContinuePastEndInternal const):
+
+            InlineBidiResolver only returns runs up to the last renderer on the line and can bail out.
+
 2017-11-23  Zan Dobersek  <zdobersek@igalia.com>
 
         [CoordGraphics] Replace CoordinatedSurface, ThreadSafeCoordinatedSurface with CoordinatedBuffer
index 1b13ef3..0ebc144 100644 (file)
@@ -245,6 +245,7 @@ protected:
     // FIXME: Instead of InlineBidiResolvers subclassing this method, we should
     // pass in some sort of Traits object which knows how to create runs for appending.
     void appendRun() { static_cast<DerivedClass&>(*this).appendRunInternal(); }
+    bool needsContinuePastEnd() const { return static_cast<const DerivedClass&>(*this).needsContinuePastEndInternal(); }
 
     Iterator m_current;
     // sor and eor are "start of run" and "end of run" respectively and correpond
@@ -277,6 +278,7 @@ private:
     void reorderRunsFromLevels();
     void incrementInternal() { m_current.increment(); }
     void appendRunInternal();
+    bool needsContinuePastEndInternal() const { return true; }
 
     Vector<BidiEmbedding, 8> m_currentExplicitEmbeddingSequence;
 };
@@ -292,6 +294,7 @@ public:
 
     void incrementInternal();
     void appendRunInternal();
+    bool needsContinuePastEndInternal() const;
     Vector<IsolateRun>& isolatedRuns() { return m_isolatedRuns; }
 
 private:
@@ -880,7 +883,7 @@ void BidiResolverBase<Iterator, Run, DerivedClass>::createBidiRunsForLine(const
             break;
         }
 
-        if (pastEnd && m_eor == m_current) {
+        if (pastEnd && (m_eor == m_current || !needsContinuePastEnd())) {
             if (!m_reachedEndOfLine) {
                 m_eor = endOfLine;
                 switch (m_status.eor) {
index 08eb2ab..cdd31af 100644 (file)
@@ -586,4 +586,11 @@ inline void InlineBidiResolver::appendRunInternal()
     m_status.eor = U_OTHER_NEUTRAL;
 }
 
+template<>
+inline bool InlineBidiResolver::needsContinuePastEndInternal() const
+{
+    // We don't collect runs beyond the endOfLine renderer. Stop traversing when the iterator moves to the next renderer to prevent O(n^2).
+    return m_current.renderer() == endOfLine.renderer();
+}
+
 } // namespace WebCore