Changeset 124969 in webkit


Ignore:
Timestamp:
Aug 7, 2012, 7:16:14 PM (13 years ago)
Author:
commit-queue@webkit.org
Message:

Reimplement RenderQuote placement algorithm
​https://bugs.webkit.org/show_bug.cgi?id=93056

Patch by Elliott Sprehn <Elliott Sprehn> on 2012-08-07
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):

Location:
trunk/Source/WebCore
Files:
7 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r124968 r124969  
     12012-08-07  Elliott Sprehn  <esprehn@gmail.com>
     2
     3        Reimplement RenderQuote placement algorithm
     4        https://bugs.webkit.org/show_bug.cgi?id=93056
     5
     6        Reviewed by Eric Seidel.
     7
     8        Greatly simplify the code that maintains the linked list of RenderQuotes. Now RenderQuote
     9        is placed into the linked list in computePreferredLogicalWidths on first access and is
     10        detached when destroyed (or explicitly removed).
     11
     12        The new algorithm doesn't require walking up the tree of renderers when there are no
     13        RenderQuotes in the tree yet, and also removes the need to walk over every subtree
     14        when inserting in rendererSubtreeAttached.
     15
     16        No new tests because this patch doesn't change any behavior.
     17
     18        * rendering/RenderObjectChildList.cpp:
     19        (WebCore::RenderObjectChildList::removeChildNode): Call detachQuote when removing from a child list.
     20        (WebCore::RenderObjectChildList::appendChildNode):
     21        (WebCore::RenderObjectChildList::insertChildNode):
     22        * rendering/RenderQuote.cpp:
     23        (WebCore::RenderQuote::RenderQuote):
     24        (WebCore::RenderQuote::~RenderQuote):
     25        (WebCore::RenderQuote::willBeDestroyed): Call detachQuote to ensure all destroyed quotes are detached.
     26        (WebCore::RenderQuote::originalText):
     27        (WebCore::RenderQuote::computePreferredLogicalWidths): Attach quote before computing the width.
     28        (WebCore):
     29        (WebCore::RenderQuote::attachQuote): Puts the RenderQuote in the linked list of quotes and computes the depth.
     30        (WebCore::RenderQuote::detachQuote): Removes the quote from the linked list.
     31        (WebCore::RenderQuote::updateDepth):
     32        * rendering/RenderQuote.h:
     33        (RenderQuote):
     34        * rendering/style/RenderStyle.cpp:
     35        (WebCore::RenderStyle::diff): Return StyleDifferenceLayout if quotes change and remove check in styleDidChange in RenderQuote.
     36        * rendering/RenderView.cpp:
     37        (WebCore::RenderView::RenderView):
     38        * rendering/RenderView.h:
     39        (WebCore):
     40        (WebCore::RenderView::setRenderQuoteHead):
     41        (WebCore::RenderView::renderQuoteHead): Stores the first quote in the document.
     42        (RenderView):
     43
    1442012-08-07  Kentaro Hara  <haraken@chromium.org>
    245

  • trunk/Source/WebCore/rendering/RenderObjectChildList.cpp

    r123794 r124969  
    118118            toRenderRegion(oldChild)->detachRegion();
    119119
     120        if (oldChild->isQuote())
     121            toRenderQuote(oldChild)->detachQuote();
     122
    120123        if (oldChild->inRenderFlowThread()) {
    121124            if (oldChild->isBox())
    … …  
    159162    if (!owner->documentBeingDestroyed()) {
    160163        RenderCounter::rendererRemovedFromTree(oldChild);
    161         RenderQuote::rendererRemovedFromTree(oldChild);
    162164    }
    163165
    … …  
    211213            toRenderRegion(newChild)->attachRegion();
    212214
     215        // You can't attachQuote() otherwise the quote would be attached too early
     216        // and get the wrong depth since generated content is inserted into anonymous
     217        // renderers before going into the main render tree.
     218
    213219        if (RenderNamedFlowThread* containerFlowThread = renderNamedFlowThreadContainer(owner))
    214220            containerFlowThread->addFlowChild(newChild);
    … …  
    217223    if (!owner->documentBeingDestroyed()) {
    218224        RenderCounter::rendererSubtreeAttached(newChild);
    219         RenderQuote::rendererSubtreeAttached(newChild);
    220225    }
    221226    newChild->setNeedsLayoutAndPrefWidthsRecalc(); // Goes up the containing block hierarchy.
    … …  
    280285            toRenderRegion(child)->attachRegion();
    281286
     287        // Calling attachQuote() here would be too early (before anonymous renderers are inserted)
     288        // see appendChild() for more explanation.
     289
    282290        if (RenderNamedFlowThread* containerFlowThread = renderNamedFlowThreadContainer(owner))
    283291            containerFlowThread->addFlowChild(child, beforeChild);
    … …  
    286294    if (!owner->documentBeingDestroyed()) {
    287295        RenderCounter::rendererSubtreeAttached(child);
    288         RenderQuote::rendererSubtreeAttached(child);
    289296    }
    290297    child->setNeedsLayoutAndPrefWidthsRecalc();

  • trunk/Source/WebCore/rendering/RenderQuote.cpp

    r124518 r124969  
    2222#include "RenderQuote.h"
    2323
    24 #include "Document.h"
    25 #include "QuotesData.h"
    26 #include "RenderStyle.h"
    2724#include <wtf/text/AtomicString.h>
    2825
    29 #define UNKNOWN_DEPTH -1
     26#define U(x) ((const UChar*)L##x)
    3027
    3128namespace WebCore {
    32 static inline void adjustDepth(int &depth, QuoteType type)
    33 {
    34     switch (type) {
    35     case OPEN_QUOTE:
    36     case NO_OPEN_QUOTE:
    37         ++depth;
    38         break;
    39     case CLOSE_QUOTE:
    40     case NO_CLOSE_QUOTE:
    41         if (depth)
    42             --depth;
    43         break;
    44     default:
    45         ASSERT_NOT_REACHED();
    46     }
    47 }
    4829
    4930RenderQuote::RenderQuote(Document* node, QuoteType quote)
    5031    : RenderText(node, StringImpl::empty())
    5132    , m_type(quote)
    52     , m_depth(UNKNOWN_DEPTH)
     33    , m_depth(0)
    5334    , m_next(0)
    5435    , m_previous(0)
    55 {
    56     view()->addRenderQuote();
     36    , m_attached(false)
     37{
    5738}
    5839
    5940RenderQuote::~RenderQuote()
    6041{
     42    ASSERT(!m_attached);
     43    ASSERT(!m_next && !m_previous);
    6144}
    6245
    6346void RenderQuote::willBeDestroyed()
    6447{
    65     if (view())
    66         view()->removeRenderQuote();
     48    detachQuote();
    6749    RenderText::willBeDestroyed();
    6850}
    69 
    70 const char* RenderQuote::renderName() const
    71 {
    72     return "RenderQuote";
    73 }
    74 
    75 // This function places a list of quote renderers starting at "this" in the list of quote renderers already
    76 // in the document's renderer tree.
    77 // The assumptions are made (for performance):
    78 // 1. The list of quotes already in the renderers tree of the document is already in a consistent state
    79 // (All quote renderers are linked and have the correct depth set)
    80 // 2. The quote renderers of the inserted list are in a tree of renderers of their own which has been just
    81 // inserted in the main renderer tree with its root as child of some renderer.
    82 // 3. The quote renderers in the inserted list have depths consistent with their position in the list relative
    83 // to "this", thus if "this" does not need to change its depth upon insertion, the other renderers in the list don't
    84 // need to either.
    85 void RenderQuote::placeQuote()
    86 {
    87     RenderQuote* head = this;
    88     ASSERT(!head->m_previous);
    89     RenderQuote* tail = 0;
    90     for (RenderObject* predecessor = head->previousInPreOrder(); predecessor; predecessor = predecessor->previousInPreOrder()) {
    91         if (!predecessor->isQuote())
    92             continue;
    93         head->m_previous = toRenderQuote(predecessor);
    94         if (head->m_previous->m_next) {
    95             // We need to splice the list of quotes headed by head into the document's list of quotes.
    96             tail = head;
    97             while (tail->m_next)
    98                  tail = tail->m_next;
    99             tail->m_next = head->m_previous->m_next;
    100             ASSERT(tail->m_next->m_previous == head->m_previous);
    101             tail->m_next->m_previous =  tail;
    102             tail = tail->m_next; // This marks the splicing point here there may be a depth discontinuity
    103         }
    104         head->m_previous->m_next = head;
    105         ASSERT(head->m_previous->m_depth != UNKNOWN_DEPTH);
    106         break;
    107     }
    108     int newDepth;
    109     if (!head->m_previous) {
    110         newDepth = 0;
    111         goto skipNewDepthCalc;
    112     }
    113     newDepth = head->m_previous->m_depth;
    114     do {
    115         adjustDepth(newDepth, head->m_previous->m_type);
    116 skipNewDepthCalc:
    117         if (head->m_depth == newDepth) { // All remaining depth should be correct except if splicing was done.
    118             if (!tail) // We've done the post splicing section already or there was no splicing.
    119                 break;
    120             head = tail; // Continue after the splicing point
    121             tail = 0; // Mark the possible splicing point discontinuity fixed.
    122             newDepth = head->m_previous->m_depth;
    123             continue;
    124         }
    125         head->m_depth = newDepth;
    126         // FIXME: If the width and height of the quotation characters does not change we may only need to
    127         // Invalidate the renderer's area not a relayout.
    128         head->setNeedsLayoutAndPrefWidthsRecalc();
    129         head = head->m_next;
    130         if (head == tail) // We are at the splicing point
    131             tail = 0; // Mark the possible depth discontinuity fixed.
    132     } while (head);
    133 }
    134 
    135 #define U(x) ((const UChar*)L##x)
    13651
    13752typedef HashMap<AtomicString, const QuotesData*, CaseFoldingHash> QuotesMap;
    … …  
    15873PassRefPtr<StringImpl> RenderQuote::originalText() const
    15974{
    160     if (!parent())
    161         return 0;
    162     ASSERT(m_depth != UNKNOWN_DEPTH);
    163     const QuotesData* quotes = quotesData();
    16475    switch (m_type) {
    16576    case NO_OPEN_QUOTE:
    … …  
    16879    case CLOSE_QUOTE:
    16980        // FIXME: When m_depth is 0 we should return empty string.
    170         return quotes->getCloseQuote(std::max(m_depth - 1, 0)).impl();
     81        return quotesData()->getCloseQuote(std::max(m_depth - 1, 0)).impl();
    17182    case OPEN_QUOTE:
    172         return quotes->getOpenQuote(m_depth).impl();
    173     default:
    174         ASSERT_NOT_REACHED();
    175         return StringImpl::empty();
    176     }
     83        return quotesData()->getOpenQuote(m_depth).impl();
     84    }
     85    ASSERT_NOT_REACHED();
     86    return StringImpl::empty();
    17787}
    17888
    17989void RenderQuote::computePreferredLogicalWidths(float lead)
    18090{
     91    if (!m_attached)
     92        attachQuote();
    18193    setTextInternal(originalText());
    18294    RenderText::computePreferredLogicalWidths(lead);
    … …  
    197109}
    198110
    199 void RenderQuote::rendererSubtreeAttached(RenderObject* renderer)
    200 {
    201     ASSERT(renderer->view());
    202     if (!renderer->view()->hasRenderQuotes())
     111void RenderQuote::attachQuote()
     112{
     113    ASSERT(view());
     114    ASSERT(!m_attached);
     115    ASSERT(!m_next && !m_previous);
     116
     117    // FIXME: Don't set pref widths dirty during layout. See updateDepth() for
     118    // more detail.
     119    if (!isRooted()) {
     120        setNeedsLayoutAndPrefWidthsRecalc();
    203121        return;
    204     for (RenderObject* descendant = renderer; descendant; descendant = descendant->nextInPreOrder(renderer))
    205         if (descendant->isQuote()) {
    206             toRenderQuote(descendant)->placeQuote();
     122    }
     123
     124    if (!view()->renderQuoteHead()) {
     125        view()->setRenderQuoteHead(this);
     126        m_attached = true;
     127        return;
     128    }
     129
     130    for (RenderObject* predecessor = previousInPreOrder(); predecessor; predecessor = predecessor->previousInPreOrder()) {
     131        if (!predecessor->isQuote())
     132            continue;
     133        m_previous = toRenderQuote(predecessor);
     134        m_next = m_previous->m_next;
     135        m_previous->m_next = this;
     136        if (m_next)
     137            m_next->m_previous = this;
     138        break;
     139    }
     140
     141    if (!m_previous) {
     142        m_next = view()->renderQuoteHead();
     143        view()->setRenderQuoteHead(this);
     144    }
     145    m_attached = true;
     146    for (RenderQuote* quote = this; quote; quote = quote->m_next)
     147        quote->updateDepth();
     148
     149    ASSERT(!m_next || m_next->m_attached);
     150    ASSERT(!m_previous || m_previous->m_attached);
     151}
     152
     153void RenderQuote::detachQuote()
     154{
     155    ASSERT(!m_next || m_next->m_attached);
     156    ASSERT(!m_previous || m_previous->m_attached);
     157    if (!m_attached)
     158        return;
     159    if (m_previous)
     160        m_previous->m_next = m_next;
     161    else if (view())
     162        view()->setRenderQuoteHead(m_next);
     163    if (m_next)
     164        m_next->m_previous = m_previous;
     165    if (!documentBeingDestroyed()) {
     166        for (RenderQuote* quote = m_next; quote; quote = quote->m_next)
     167            quote->updateDepth();
     168    }
     169    m_attached = false;
     170    m_next = 0;
     171    m_previous = 0;
     172    m_depth = 0;
     173}
     174
     175void RenderQuote::updateDepth()
     176{
     177    ASSERT(m_attached);
     178    int oldDepth = m_depth;
     179    m_depth = 0;
     180    if (m_previous) {
     181        m_depth = m_previous->m_depth;
     182        switch (m_previous->m_type) {
     183        case OPEN_QUOTE:
     184        case NO_OPEN_QUOTE:
     185            m_depth++;
     186            break;
     187        case CLOSE_QUOTE:
     188        case NO_CLOSE_QUOTE:
     189            if (m_depth)
     190                m_depth--;
    207191            break;
    208192        }
    209 }
    210 
    211 void RenderQuote::rendererRemovedFromTree(RenderObject* renderer)
    212 {
    213     ASSERT(renderer->view());
    214     if (!renderer->view()->hasRenderQuotes())
    215         return;
    216     for (RenderObject* descendant = renderer; descendant; descendant = descendant->nextInPreOrder(renderer))
    217         if (descendant->isQuote()) {
    218             RenderQuote* removedQuote = toRenderQuote(descendant);
    219             RenderQuote* lastQuoteBefore = removedQuote->m_previous;
    220             removedQuote->m_previous = 0;
    221             int depth = removedQuote->m_depth;
    222             for (descendant = descendant->nextInPreOrder(renderer); descendant; descendant = descendant->nextInPreOrder(renderer))
    223                 if (descendant->isQuote())
    224                     removedQuote = toRenderQuote(descendant);
    225             RenderQuote* quoteAfter = removedQuote->m_next;
    226             removedQuote->m_next = 0;
    227             if (lastQuoteBefore)
    228                 lastQuoteBefore->m_next = quoteAfter;
    229             if (quoteAfter) {
    230                 quoteAfter->m_previous = lastQuoteBefore;
    231                 do {
    232                     if (depth == quoteAfter->m_depth)
    233                         break;
    234                     quoteAfter->m_depth = depth;
    235                     quoteAfter->setNeedsLayoutAndPrefWidthsRecalc();
    236                     adjustDepth(depth, quoteAfter->m_type);
    237                     quoteAfter = quoteAfter->m_next;
    238                 } while (quoteAfter);
    239             }
    240             break;
    241         }
    242 }
    243 
    244 void RenderQuote::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
    245 {
    246     const QuotesData* newQuotes = style()->quotes();
    247     const QuotesData* oldQuotes = oldStyle ? oldStyle->quotes() : 0;
    248     if (!QuotesData::equals(newQuotes, oldQuotes))
     193    }
     194    // FIXME: Don't call setNeedsLayout or dirty our preferred widths during layout.
     195    // This is likely to fail anyway as one of our ancestor will call setNeedsLayout(false),
     196    // preventing the future layout to occur on |this|. The solution is to move that to a
     197    // pre-layout phase.
     198    if (oldDepth != m_depth)
    249199        setNeedsLayoutAndPrefWidthsRecalc();
    250     RenderText::styleDidChange(diff, oldStyle);
    251200}
    252201

  • trunk/Source/WebCore/rendering/RenderQuote.h

    r124518 r124969  
    2222#define RenderQuote_h
    2323
     24#include "Document.h"
     25#include "QuotesData.h"
     26#include "RenderStyle.h"
    2427#include "RenderStyleConstants.h"
    2528#include "RenderText.h"
    … …  
    3134    RenderQuote(Document*, const QuoteType);
    3235    virtual ~RenderQuote();
     36    void attachQuote();
     37    void detachQuote();
    3338
    34     static void rendererSubtreeAttached(RenderObject*);
    35     static void rendererRemovedFromTree(RenderObject*);
    36 protected:
    37     virtual void styleDidChange(StyleDifference, const RenderStyle* oldStyle);
    38     virtual void willBeDestroyed();
    3939private:
    40     virtual const char* renderName() const;
    41     virtual bool isQuote() const { return true; };
    42     virtual PassRefPtr<StringImpl> originalText() const;
    43     virtual void computePreferredLogicalWidths(float leadWidth);
     40    virtual void willBeDestroyed() OVERRIDE;
     41    virtual const char* renderName() const OVERRIDE { return "RenderQuote"; };
     42    virtual bool isQuote() const OVERRIDE { return true; };
     43    virtual PassRefPtr<StringImpl> originalText() const OVERRIDE;
     44    virtual void computePreferredLogicalWidths(float leadWidth) OVERRIDE;
     45
    4446    const QuotesData* quotesData() const;
     47    void updateDepth();
    4548
    4649    QuoteType m_type;
    … …  
    4851    RenderQuote* m_next;
    4952    RenderQuote* m_previous;
    50     void placeQuote();
     53    bool m_attached;
    5154};
    5255

  • trunk/Source/WebCore/rendering/RenderView.cpp

    r124662 r124969  
    6363    , m_layoutState(0)
    6464    , m_layoutStateDisableCount(0)
    65     , m_renderQuoteCount(0)
     65    , m_renderQuoteHead(0)
    6666    , m_renderCounterCount(0)
    6767{

  • trunk/Source/WebCore/rendering/RenderView.h

    r124662 r124969  
    3333class FlowThreadController;
    3434class RenderWidget;
     35class RenderQuote;
    3536
    3637#if USE(ACCELERATED_COMPOSITING)
    … …  
    195196    void setFixedPositionedObjectsNeedLayout();
    196197
    197     // FIXME: This is a work around because the current implementation of counters and quotes
     198    void setRenderQuoteHead(RenderQuote* head) { m_renderQuoteHead = head; }
     199    RenderQuote* renderQuoteHead() const { return m_renderQuoteHead; }
     200
     201    // FIXME: This is a work around because the current implementation of counters
    198202    // requires walking the entire tree repeatedly and most pages don't actually use either
    199203    // feature so we shouldn't take the performance hit when not needed. Long term we should
    200204    // rewrite the counter and quotes code.
    201     void addRenderQuote() { m_renderQuoteCount++; }
    202     void removeRenderQuote() { ASSERT(m_renderQuoteCount > 0); m_renderQuoteCount--; }
    203     bool hasRenderQuotes() { return m_renderQuoteCount; }
    204205    void addRenderCounter() { m_renderCounterCount++; }
    205206    void removeRenderCounter() { ASSERT(m_renderCounterCount > 0); m_renderCounterCount--; }
    … …  
    302303    RefPtr<IntervalArena> m_intervalArena;
    303304
    304     unsigned m_renderQuoteCount;
     305    RenderQuote* m_renderQuoteHead;
    305306    unsigned m_renderCounterCount;
    306307};

  • trunk/Source/WebCore/rendering/style/RenderStyle.cpp

    r124884 r124969  
    580580        return StyleDifferenceLayout;
    581581    }
     582
     583    if (!QuotesData::equals(rareInheritedData->quotes.get(), other->rareInheritedData->quotes.get()))
     584        return StyleDifferenceLayout;
    582585
    583586#if ENABLE(SVG)
Note: See TracChangeset for help on using the changeset viewer.