Reimplement RenderQuote placement algorithm
authorcommit-queue@webkit.org <commit-queue@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 9 Aug 2012 23:34:44 +0000 (23:34 +0000)
committercommit-queue@webkit.org <commit-queue@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 9 Aug 2012 23:34:44 +0000 (23:34 +0000)
https://bugs.webkit.org/show_bug.cgi?id=93056

Patch by Elliott Sprehn <esprehn@gmail.com> on 2012-08-09
Reviewed by Eric Seidel.

Greatly simplify the code that maintains the linked list of RenderQuotes. Now RenderQuote
is placed into the linked list in computePreferredLogicalWidths on first access and is
detached when destroyed (or explicitly removed).

The new algorithm doesn't require walking up the tree of renderers when there are no
RenderQuotes in the tree yet, and also removes the need to walk over every subtree
when inserting in rendererSubtreeAttached.

No new tests because this patch doesn't change any behavior.

* rendering/RenderObjectChildList.cpp:
(WebCore::RenderObjectChildList::removeChildNode): Call detachQuote when removing from a child list.
(WebCore::RenderObjectChildList::appendChildNode):
(WebCore::RenderObjectChildList::insertChildNode):
* rendering/RenderQuote.cpp:
(WebCore::RenderQuote::RenderQuote):
(WebCore::RenderQuote::~RenderQuote):
(WebCore::RenderQuote::willBeDestroyed): Call detachQuote to ensure all destroyed quotes are detached.
(WebCore::RenderQuote::originalText):
(WebCore::RenderQuote::computePreferredLogicalWidths): Attach quote before computing the width.
(WebCore):
(WebCore::RenderQuote::attachQuote): Puts the RenderQuote in the linked list of quotes and computes the depth.
(WebCore::RenderQuote::detachQuote): Removes the quote from the linked list.
(WebCore::RenderQuote::updateDepth):
* rendering/RenderQuote.h:
(RenderQuote):
* rendering/style/RenderStyle.cpp:
(WebCore::RenderStyle::diff): Return StyleDifferenceLayout if quotes change and remove check in styleDidChange in RenderQuote.
* rendering/RenderView.cpp:
(WebCore::RenderView::RenderView):
* rendering/RenderView.h:
(WebCore):
(WebCore::RenderView::setRenderQuoteHead):
(WebCore::RenderView::renderQuoteHead): Stores the first quote in the document.
(RenderView):

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

Source/WebCore/ChangeLog
Source/WebCore/rendering/RenderObjectChildList.cpp
Source/WebCore/rendering/RenderQuote.cpp
Source/WebCore/rendering/RenderQuote.h
Source/WebCore/rendering/RenderView.cpp
Source/WebCore/rendering/RenderView.h
Source/WebCore/rendering/style/RenderStyle.cpp

index 04d65be..2267643 100644 (file)
@@ -1,3 +1,46 @@
+2012-08-09  Elliott Sprehn  <esprehn@gmail.com>
+
+        Reimplement RenderQuote placement algorithm
+        https://bugs.webkit.org/show_bug.cgi?id=93056
+
+        Reviewed by Eric Seidel.
+
+        Greatly simplify the code that maintains the linked list of RenderQuotes. Now RenderQuote
+        is placed into the linked list in computePreferredLogicalWidths on first access and is
+        detached when destroyed (or explicitly removed).
+
+        The new algorithm doesn't require walking up the tree of renderers when there are no
+        RenderQuotes in the tree yet, and also removes the need to walk over every subtree
+        when inserting in rendererSubtreeAttached.
+
+        No new tests because this patch doesn't change any behavior.
+
+        * rendering/RenderObjectChildList.cpp:
+        (WebCore::RenderObjectChildList::removeChildNode): Call detachQuote when removing from a child list.
+        (WebCore::RenderObjectChildList::appendChildNode):
+        (WebCore::RenderObjectChildList::insertChildNode):
+        * rendering/RenderQuote.cpp:
+        (WebCore::RenderQuote::RenderQuote):
+        (WebCore::RenderQuote::~RenderQuote):
+        (WebCore::RenderQuote::willBeDestroyed): Call detachQuote to ensure all destroyed quotes are detached.
+        (WebCore::RenderQuote::originalText):
+        (WebCore::RenderQuote::computePreferredLogicalWidths): Attach quote before computing the width.
+        (WebCore):
+        (WebCore::RenderQuote::attachQuote): Puts the RenderQuote in the linked list of quotes and computes the depth.
+        (WebCore::RenderQuote::detachQuote): Removes the quote from the linked list.
+        (WebCore::RenderQuote::updateDepth):
+        * rendering/RenderQuote.h:
+        (RenderQuote):
+        * rendering/style/RenderStyle.cpp:
+        (WebCore::RenderStyle::diff): Return StyleDifferenceLayout if quotes change and remove check in styleDidChange in RenderQuote.
+        * rendering/RenderView.cpp:
+        (WebCore::RenderView::RenderView):
+        * rendering/RenderView.h:
+        (WebCore):
+        (WebCore::RenderView::setRenderQuoteHead):
+        (WebCore::RenderView::renderQuoteHead): Stores the first quote in the document.
+        (RenderView):
+
 2012-08-06  Nat Duca  <nduca@chromium.org>
 
         [chromium] Expose CCGraphicsContext as WebCompositorOutputSurface
index da98088..3158fbf 100644 (file)
@@ -117,6 +117,9 @@ RenderObject* RenderObjectChildList::removeChildNode(RenderObject* owner, Render
         if (oldChild->isRenderRegion())
             toRenderRegion(oldChild)->detachRegion();
 
+        if (oldChild->isQuote())
+            toRenderQuote(oldChild)->detachQuote();
+
         if (oldChild->inRenderFlowThread()) {
             if (oldChild->isBox())
                 oldChild->enclosingRenderFlowThread()->removeRenderBoxRegionInfo(toRenderBox(oldChild));
@@ -158,7 +161,6 @@ RenderObject* RenderObjectChildList::removeChildNode(RenderObject* owner, Render
     // by skipping this step when destroying the entire tree.
     if (!owner->documentBeingDestroyed()) {
         RenderCounter::rendererRemovedFromTree(oldChild);
-        RenderQuote::rendererRemovedFromTree(oldChild);
     }
 
     if (AXObjectCache::accessibilityEnabled())
@@ -210,13 +212,16 @@ void RenderObjectChildList::appendChildNode(RenderObject* owner, RenderObject* n
         if (newChild->isRenderRegion())
             toRenderRegion(newChild)->attachRegion();
 
+        // You can't attachQuote() otherwise the quote would be attached too early
+        // and get the wrong depth since generated content is inserted into anonymous
+        // renderers before going into the main render tree.
+
         if (RenderNamedFlowThread* containerFlowThread = renderNamedFlowThreadContainer(owner))
             containerFlowThread->addFlowChild(newChild);
     }
 
     if (!owner->documentBeingDestroyed()) {
         RenderCounter::rendererSubtreeAttached(newChild);
-        RenderQuote::rendererSubtreeAttached(newChild);
     }
     newChild->setNeedsLayoutAndPrefWidthsRecalc(); // Goes up the containing block hierarchy.
     if (!owner->normalChildNeedsLayout())
@@ -279,13 +284,15 @@ void RenderObjectChildList::insertChildNode(RenderObject* owner, RenderObject* c
         if (child->isRenderRegion())
             toRenderRegion(child)->attachRegion();
 
+        // Calling attachQuote() here would be too early (before anonymous renderers are inserted)
+        // see appendChild() for more explanation.
+
         if (RenderNamedFlowThread* containerFlowThread = renderNamedFlowThreadContainer(owner))
             containerFlowThread->addFlowChild(child, beforeChild);
     }
 
     if (!owner->documentBeingDestroyed()) {
         RenderCounter::rendererSubtreeAttached(child);
-        RenderQuote::rendererSubtreeAttached(child);
     }
     child->setNeedsLayoutAndPrefWidthsRecalc();
     if (!owner->normalChildNeedsLayout())
index 7f1d749..3100290 100644 (file)
 #include "config.h"
 #include "RenderQuote.h"
 
-#include "Document.h"
-#include "QuotesData.h"
-#include "RenderStyle.h"
 #include <wtf/text/AtomicString.h>
 
-#define UNKNOWN_DEPTH -1
+#define U(x) ((const UChar*)L##x)
 
 namespace WebCore {
-static inline void adjustDepth(int &depth, QuoteType type)
-{
-    switch (type) {
-    case OPEN_QUOTE:
-    case NO_OPEN_QUOTE:
-        ++depth;
-        break;
-    case CLOSE_QUOTE:
-    case NO_CLOSE_QUOTE:
-        if (depth)
-            --depth;
-        break;
-    default:
-        ASSERT_NOT_REACHED();
-    }
-}
 
 RenderQuote::RenderQuote(Document* node, QuoteType quote)
     : RenderText(node, StringImpl::empty())
     , m_type(quote)
-    , m_depth(UNKNOWN_DEPTH)
+    , m_depth(0)
     , m_next(0)
     , m_previous(0)
+    , m_attached(false)
 {
-    view()->addRenderQuote();
 }
 
 RenderQuote::~RenderQuote()
 {
+    ASSERT(!m_attached);
+    ASSERT(!m_next && !m_previous);
 }
 
 void RenderQuote::willBeDestroyed()
 {
-    if (view())
-        view()->removeRenderQuote();
+    detachQuote();
     RenderText::willBeDestroyed();
 }
 
-const char* RenderQuote::renderName() const
-{
-    return "RenderQuote";
-}
-
-// This function places a list of quote renderers starting at "this" in the list of quote renderers already
-// in the document's renderer tree.
-// The assumptions are made (for performance):
-// 1. The list of quotes already in the renderers tree of the document is already in a consistent state
-// (All quote renderers are linked and have the correct depth set)
-// 2. The quote renderers of the inserted list are in a tree of renderers of their own which has been just
-// inserted in the main renderer tree with its root as child of some renderer.
-// 3. The quote renderers in the inserted list have depths consistent with their position in the list relative
-// to "this", thus if "this" does not need to change its depth upon insertion, the other renderers in the list don't
-// need to either.
-void RenderQuote::placeQuote()
-{
-    RenderQuote* head = this;
-    ASSERT(!head->m_previous);
-    RenderQuote* tail = 0;
-    for (RenderObject* predecessor = head->previousInPreOrder(); predecessor; predecessor = predecessor->previousInPreOrder()) {
-        if (!predecessor->isQuote())
-            continue;
-        head->m_previous = toRenderQuote(predecessor);
-        if (head->m_previous->m_next) {
-            // We need to splice the list of quotes headed by head into the document's list of quotes.
-            tail = head;
-            while (tail->m_next)
-                 tail = tail->m_next;
-            tail->m_next = head->m_previous->m_next;
-            ASSERT(tail->m_next->m_previous == head->m_previous);
-            tail->m_next->m_previous =  tail;
-            tail = tail->m_next; // This marks the splicing point here there may be a depth discontinuity
-        }
-        head->m_previous->m_next = head;
-        ASSERT(head->m_previous->m_depth != UNKNOWN_DEPTH);
-        break;
-    }
-    int newDepth;
-    if (!head->m_previous) {
-        newDepth = 0;
-        goto skipNewDepthCalc;
-    }
-    newDepth = head->m_previous->m_depth;
-    do {
-        adjustDepth(newDepth, head->m_previous->m_type);
-skipNewDepthCalc:
-        if (head->m_depth == newDepth) { // All remaining depth should be correct except if splicing was done.
-            if (!tail) // We've done the post splicing section already or there was no splicing.
-                break;
-            head = tail; // Continue after the splicing point
-            tail = 0; // Mark the possible splicing point discontinuity fixed.
-            newDepth = head->m_previous->m_depth;
-            continue;
-        }
-        head->m_depth = newDepth;
-        // FIXME: If the width and height of the quotation characters does not change we may only need to
-        // Invalidate the renderer's area not a relayout.
-        head->setNeedsLayoutAndPrefWidthsRecalc();
-        head = head->m_next;
-        if (head == tail) // We are at the splicing point
-            tail = 0; // Mark the possible depth discontinuity fixed.
-    } while (head);
-}
-
-#define U(x) ((const UChar*)L##x)
-
 typedef HashMap<AtomicString, const QuotesData*, CaseFoldingHash> QuotesMap;
 
 static const QuotesMap& quotesDataLanguageMap()
@@ -157,27 +72,24 @@ static const QuotesData* basicQuotesData()
 
 PassRefPtr<StringImpl> RenderQuote::originalText() const
 {
-    if (!parent())
-        return 0;
-    ASSERT(m_depth != UNKNOWN_DEPTH);
-    const QuotesData* quotes = quotesData();
     switch (m_type) {
     case NO_OPEN_QUOTE:
     case NO_CLOSE_QUOTE:
         return StringImpl::empty();
     case CLOSE_QUOTE:
         // FIXME: When m_depth is 0 we should return empty string.
-        return quotes->getCloseQuote(std::max(m_depth - 1, 0)).impl();
+        return quotesData()->getCloseQuote(std::max(m_depth - 1, 0)).impl();
     case OPEN_QUOTE:
-        return quotes->getOpenQuote(m_depth).impl();
-    default:
-        ASSERT_NOT_REACHED();
-        return StringImpl::empty();
+        return quotesData()->getOpenQuote(m_depth).impl();
     }
+    ASSERT_NOT_REACHED();
+    return StringImpl::empty();
 }
 
 void RenderQuote::computePreferredLogicalWidths(float lead)
 {
+    if (!m_attached)
+        attachQuote();
     setTextInternal(originalText());
     RenderText::computePreferredLogicalWidths(lead);
 }
@@ -196,58 +108,98 @@ const QuotesData* RenderQuote::quotesData() const
     return quotes;
 }
 
-void RenderQuote::rendererSubtreeAttached(RenderObject* renderer)
+void RenderQuote::attachQuote()
 {
-    ASSERT(renderer->view());
-    if (!renderer->view()->hasRenderQuotes())
+    ASSERT(view());
+    ASSERT(!m_attached);
+    ASSERT(!m_next && !m_previous);
+
+    // FIXME: Don't set pref widths dirty during layout. See updateDepth() for
+    // more detail.
+    if (!isRooted()) {
+        setNeedsLayoutAndPrefWidthsRecalc();
         return;
-    for (RenderObject* descendant = renderer; descendant; descendant = descendant->nextInPreOrder(renderer))
-        if (descendant->isQuote()) {
-            toRenderQuote(descendant)->placeQuote();
-            break;
-        }
+    }
+
+    if (!view()->renderQuoteHead()) {
+        view()->setRenderQuoteHead(this);
+        m_attached = true;
+        return;
+    }
+
+    for (RenderObject* predecessor = previousInPreOrder(); predecessor; predecessor = predecessor->previousInPreOrder()) {
+        // Skip unattached predecessors to avoid having stale m_previous pointers
+        // if the previous node is never attached and is then destroyed.
+        if (!predecessor->isQuote() || !toRenderQuote(predecessor)->isAttached())
+            continue;
+        m_previous = toRenderQuote(predecessor);
+        m_next = m_previous->m_next;
+        m_previous->m_next = this;
+        if (m_next)
+            m_next->m_previous = this;
+        break;
+    }
+
+    if (!m_previous) {
+        m_next = view()->renderQuoteHead();
+        view()->setRenderQuoteHead(this);
+    }
+    m_attached = true;
+
+    for (RenderQuote* quote = this; quote; quote = quote->m_next)
+        quote->updateDepth();
+
+    ASSERT(!m_next || m_next->m_attached);
+    ASSERT(!m_previous || m_previous->m_attached);
 }
 
-void RenderQuote::rendererRemovedFromTree(RenderObject* renderer)
+void RenderQuote::detachQuote()
 {
-    ASSERT(renderer->view());
-    if (!renderer->view()->hasRenderQuotes())
+    ASSERT(!m_next || m_next->m_attached);
+    ASSERT(!m_previous || m_previous->m_attached);
+    if (!m_attached)
         return;
-    for (RenderObject* descendant = renderer; descendant; descendant = descendant->nextInPreOrder(renderer))
-        if (descendant->isQuote()) {
-            RenderQuote* removedQuote = toRenderQuote(descendant);
-            RenderQuote* lastQuoteBefore = removedQuote->m_previous;
-            removedQuote->m_previous = 0;
-            int depth = removedQuote->m_depth;
-            for (descendant = descendant->nextInPreOrder(renderer); descendant; descendant = descendant->nextInPreOrder(renderer))
-                if (descendant->isQuote())
-                    removedQuote = toRenderQuote(descendant);
-            RenderQuote* quoteAfter = removedQuote->m_next;
-            removedQuote->m_next = 0;
-            if (lastQuoteBefore)
-                lastQuoteBefore->m_next = quoteAfter;
-            if (quoteAfter) {
-                quoteAfter->m_previous = lastQuoteBefore;
-                do {
-                    if (depth == quoteAfter->m_depth)
-                        break;
-                    quoteAfter->m_depth = depth;
-                    quoteAfter->setNeedsLayoutAndPrefWidthsRecalc();
-                    adjustDepth(depth, quoteAfter->m_type);
-                    quoteAfter = quoteAfter->m_next;
-                } while (quoteAfter);
-            }
-            break;
-        }
+    if (m_previous)
+        m_previous->m_next = m_next;
+    else if (view())
+        view()->setRenderQuoteHead(m_next);
+    if (m_next)
+        m_next->m_previous = m_previous;
+    if (!documentBeingDestroyed()) {
+        for (RenderQuote* quote = m_next; quote; quote = quote->m_next)
+            quote->updateDepth();
+    }
+    m_attached = false;
+    m_next = 0;
+    m_previous = 0;
+    m_depth = 0;
 }
 
-void RenderQuote::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
+void RenderQuote::updateDepth()
 {
-    const QuotesData* newQuotes = style()->quotes();
-    const QuotesData* oldQuotes = oldStyle ? oldStyle->quotes() : 0;
-    if (!QuotesData::equals(newQuotes, oldQuotes))
+    ASSERT(m_attached);
+    int oldDepth = m_depth;
+    m_depth = 0;
+    if (m_previous) {
+        m_depth = m_previous->m_depth;
+        switch (m_previous->m_type) {
+        case OPEN_QUOTE:
+        case NO_OPEN_QUOTE:
+            m_depth++;
+            break;
+        case CLOSE_QUOTE:
+        case NO_CLOSE_QUOTE:
+            if (m_depth)
+                m_depth--;
+            break;
+        }
+    }
+    // FIXME: Don't call setNeedsLayout or dirty our preferred widths during layout.
+    // This is likely to fail anyway as one of our ancestor will call setNeedsLayout(false),
+    // preventing the future layout to occur on |this|. The solution is to move that to a
+    // pre-layout phase.
+    if (oldDepth != m_depth)
         setNeedsLayoutAndPrefWidthsRecalc();
-    RenderText::styleDidChange(diff, oldStyle);
 }
 
 } // namespace WebCore
index b6f3c55..cf7032c 100644 (file)
@@ -21,6 +21,9 @@
 #ifndef RenderQuote_h
 #define RenderQuote_h
 
+#include "Document.h"
+#include "QuotesData.h"
+#include "RenderStyle.h"
 #include "RenderStyleConstants.h"
 #include "RenderText.h"
 
@@ -30,24 +33,25 @@ class RenderQuote : public RenderText {
 public:
     RenderQuote(Document*, const QuoteType);
     virtual ~RenderQuote();
+    void attachQuote();
+    void detachQuote();
 
-    static void rendererSubtreeAttached(RenderObject*);
-    static void rendererRemovedFromTree(RenderObject*);
-protected:
-    virtual void styleDidChange(StyleDifference, const RenderStyle* oldStyle);
-    virtual void willBeDestroyed();
 private:
-    virtual const char* renderName() const;
-    virtual bool isQuote() const { return true; };
-    virtual PassRefPtr<StringImpl> originalText() const;
-    virtual void computePreferredLogicalWidths(float leadWidth);
+    virtual void willBeDestroyed() OVERRIDE;
+    virtual const char* renderName() const OVERRIDE { return "RenderQuote"; };
+    virtual bool isQuote() const OVERRIDE { return true; };
+    virtual PassRefPtr<StringImpl> originalText() const OVERRIDE;
+    virtual void computePreferredLogicalWidths(float leadWidth) OVERRIDE;
+
     const QuotesData* quotesData() const;
+    void updateDepth();
+    bool isAttached() { return m_attached; }
 
     QuoteType m_type;
     int m_depth;
     RenderQuote* m_next;
     RenderQuote* m_previous;
-    void placeQuote();
+    bool m_attached;
 };
 
 inline RenderQuote* toRenderQuote(RenderObject* object)
index 7dd123a..0ea3884 100644 (file)
@@ -62,7 +62,7 @@ RenderView::RenderView(Node* node, FrameView* view)
     , m_pageLogicalHeightChanged(false)
     , m_layoutState(0)
     , m_layoutStateDisableCount(0)
-    , m_renderQuoteCount(0)
+    , m_renderQuoteHead(0)
     , m_renderCounterCount(0)
 {
     // Clear our anonymous bit, set because RenderObject assumes
index 98be553..e8e4227 100644 (file)
@@ -32,6 +32,7 @@ namespace WebCore {
 
 class FlowThreadController;
 class RenderWidget;
+class RenderQuote;
 
 #if USE(ACCELERATED_COMPOSITING)
 class RenderLayerCompositor;
@@ -194,13 +195,13 @@ public:
 
     void setFixedPositionedObjectsNeedLayout();
 
-    // FIXME: This is a work around because the current implementation of counters and quotes
+    void setRenderQuoteHead(RenderQuote* head) { m_renderQuoteHead = head; }
+    RenderQuote* renderQuoteHead() const { return m_renderQuoteHead; }
+
+    // FIXME: This is a work around because the current implementation of counters
     // requires walking the entire tree repeatedly and most pages don't actually use either
     // feature so we shouldn't take the performance hit when not needed. Long term we should
     // rewrite the counter and quotes code.
-    void addRenderQuote() { m_renderQuoteCount++; }
-    void removeRenderQuote() { ASSERT(m_renderQuoteCount > 0); m_renderQuoteCount--; }
-    bool hasRenderQuotes() { return m_renderQuoteCount; }
     void addRenderCounter() { m_renderCounterCount++; }
     void removeRenderCounter() { ASSERT(m_renderCounterCount > 0); m_renderCounterCount--; }
     bool hasRenderCounters() { return m_renderCounterCount; }
@@ -301,7 +302,7 @@ private:
     OwnPtr<FlowThreadController> m_flowThreadController;
     RefPtr<IntervalArena> m_intervalArena;
 
-    unsigned m_renderQuoteCount;
+    RenderQuote* m_renderQuoteHead;
     unsigned m_renderCounterCount;
 };
 
index 7425ef1..2303ffa 100644 (file)
@@ -580,6 +580,9 @@ StyleDifference RenderStyle::diff(const RenderStyle* other, unsigned& changedCon
         return StyleDifferenceLayout;
     }
 
+    if (!QuotesData::equals(rareInheritedData->quotes.get(), other->rareInheritedData->quotes.get()))
+        return StyleDifferenceLayout;
+
 #if ENABLE(SVG)
     // SVGRenderStyle::diff() might have returned StyleDifferenceRepaint, eg. if fill changes.
     // If eg. the font-size changed at the same time, we're not allowed to return StyleDifferenceRepaint,