Changeset 50960 in webkit


Ignore:
Timestamp:
Nov 13, 2009 12:21:44 PM (14 years ago)
Author:
eric@webkit.org
Message:

2009-11-13 Carol Szabo <carol.szabo@nokia.com>

Reviewed by Darin Adler.

The CounterNode class is missing some basic tree navigation methods common in other WebKit trees such as the rendering tree
https://bugs.webkit.org/show_bug.cgi?id=31213
Added tree navigation methods that permit full implementation of CSS2.1
counter feature without using recursion proportional to the counter
tree depth.
No new tests because I did not find any bug that is fixed by this
commit yet, this just reduces the size of the patch for 11031 and
helps respond to some concerns regarding that patch.

  • rendering/CounterNode.cpp: (WebCore::CounterNode::CounterNode):

(WebCore::CounterNode::nextInPreOrderAfterChildren):
(WebCore::CounterNode::nextInPreOrder):
Added to support non-recursive tree traversal necessary for
efficient full implementation of CSS2.1 counters.

(WebCore::CounterNode::lastDescendant):
(WebCore::CounterNode::previousInPreOrder):
Moved this methods such that they occupy a place similar to that of
identically named methods on the render tree. This allows for their
broader use needed in full implementation of CSS2.1 counters.

(WebCore::CounterNode::resetRenderer):
(WebCore::CounterNode::resetRenderers):
(WebCore::CounterNode::recount):
(WebCore::CounterNode::insertAfter):
(WebCore::CounterNode::removeChild):
Changed such that insertion/removal of a counter, triggers not only
recalculation of PrefixWidths, but also reassesment of values in
counter nodes. This is the basis full implementation of CSS2.1
counters. It does not change current behavior by much because of
changes needed to the recalculation algorithm, but those are comming
in the patch for 11031.
(WebCore::showTreeAndMark):

  • rendering/CounterNode.h:
  • rendering/RenderCounter.cpp: (WebCore::counter): Only changed argument type to prepare for implementation of Darin Adler's recommendation for the patch to 11031.

(WebCore::RenderCounter::invalidate):
(WebCore::destroyCounterNodeChildren):
(WebCore::RenderCounter::destroyCounterNodes):

  • rendering/RenderCounter.h:
  • rendering/RenderObjectChildList.cpp: (WebCore::invalidateCountersInContainer): (WebCore::RenderObjectChildList::invalidateCounters):
  • rendering/RenderObjectChildList.h: Added the ability to restrict invalidation to counters with a given identifier. Also invalidated counters that are on the child container itself which were missed by the previous algorithm, but were a valid case.
Location:
trunk/WebCore
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • trunk/WebCore/ChangeLog

    r50958 r50960  
     12009-11-13  Carol Szabo  <carol.szabo@nokia.com>
     2
     3        Reviewed by Darin Adler.
     4
     5        The CounterNode class is missing some basic tree navigation methods common in other WebKit trees such as the rendering tree
     6        https://bugs.webkit.org/show_bug.cgi?id=31213
     7        Added tree navigation methods that permit full implementation of CSS2.1
     8        counter feature without using recursion proportional to the counter
     9        tree depth.
     10        No new tests because I did not find any bug that is fixed by this
     11        commit yet, this just reduces the size of the patch for 11031 and
     12        helps respond to some concerns regarding that patch.
     13
     14        * rendering/CounterNode.cpp:
     15        (WebCore::CounterNode::CounterNode):
     16
     17        (WebCore::CounterNode::nextInPreOrderAfterChildren):
     18        (WebCore::CounterNode::nextInPreOrder):
     19        Added to support non-recursive tree traversal necessary for
     20        efficient full implementation of CSS2.1 counters.
     21
     22        (WebCore::CounterNode::lastDescendant):
     23        (WebCore::CounterNode::previousInPreOrder):
     24        Moved this methods such that they occupy a place similar to that of
     25        identically named methods on the render tree. This allows for their
     26        broader use needed in full implementation of CSS2.1 counters.
     27
     28        (WebCore::CounterNode::resetRenderer):
     29        (WebCore::CounterNode::resetRenderers):
     30        (WebCore::CounterNode::recount):
     31        (WebCore::CounterNode::insertAfter):
     32        (WebCore::CounterNode::removeChild):
     33        Changed such that insertion/removal of a counter, triggers not only
     34        recalculation of PrefixWidths, but also reassesment of values in
     35        counter nodes. This is the basis full implementation of CSS2.1
     36        counters. It does not change current behavior by much because of
     37        changes needed to the recalculation algorithm, but those are comming
     38        in the patch for 11031.
     39        (WebCore::showTreeAndMark):
     40        * rendering/CounterNode.h:
     41        * rendering/RenderCounter.cpp:
     42        (WebCore::counter):
     43        Only changed argument type to prepare for implementation of Darin
     44        Adler's recommendation for the patch to 11031.
     45
     46        (WebCore::RenderCounter::invalidate):
     47        (WebCore::destroyCounterNodeChildren):
     48        (WebCore::RenderCounter::destroyCounterNodes):
     49        * rendering/RenderCounter.h:
     50        * rendering/RenderObjectChildList.cpp:
     51        (WebCore::invalidateCountersInContainer):
     52        (WebCore::RenderObjectChildList::invalidateCounters):
     53        * rendering/RenderObjectChildList.h:
     54        Added the ability to restrict invalidation to counters with a given
     55        identifier.
     56        Also invalidated counters that are on the child container itself
     57        which were missed by the previous algorithm, but were a valid case.
     58
    1592009-11-13  Vitaly Repeshko  <vitalyr@chromium.org>
    260
  • trunk/WebCore/rendering/CounterNode.cpp

    r50673 r50960  
    4545    , m_firstChild(0)
    4646    , m_lastChild(0)
    47 {   
     47{
     48}
     49
     50CounterNode* CounterNode::nextInPreOrderAfterChildren(const CounterNode* stayWithin) const
     51{
     52    if (this == stayWithin)
     53        return 0;
     54
     55    CounterNode* next = m_nextSibling;
     56    if (next)
     57        return next;
     58    next = m_parent;
     59    while (next && !next->m_nextSibling) {
     60        if (next == stayWithin)
     61            return 0;
     62        next = next->m_parent;
     63    }
     64    if (next)
     65        return next->m_nextSibling;
     66    return 0;
     67}
     68
     69CounterNode* CounterNode::nextInPreOrder(const CounterNode* stayWithin) const
     70{
     71    if (CounterNode* next = m_firstChild)
     72        return next;
     73
     74    return nextInPreOrderAfterChildren(stayWithin);
     75}
     76
     77CounterNode* CounterNode::lastDescendant() const
     78{
     79    CounterNode* last = m_lastChild;
     80    if (!last)
     81        return 0;
     82
     83    while (CounterNode* lastChild = last->m_lastChild)
     84        last = lastChild;
     85
     86    return last;
     87}
     88
     89CounterNode* CounterNode::previousInPreOrder() const
     90{
     91    CounterNode* previous = m_previousSibling;
     92    if (!previous)
     93        return m_parent;
     94
     95    while (CounterNode* lastChild = previous->m_lastChild)
     96        previous = lastChild;
     97
     98    return previous;
    4899}
    49100
     
    57108}
    58109
    59 void CounterNode::recount()
    60 {
    61     for (CounterNode* c = this; c; c = c->m_nextSibling) {
    62         int oldCount = c->m_countInParent;
    63         int newCount = c->computeCountInParent();
     110
     111void CounterNode::resetRenderer(const AtomicString& identifier) const
     112{
     113    if (!m_renderer || m_renderer->documentBeingDestroyed())
     114        return;
     115    if (RenderObjectChildList* children = m_renderer->virtualChildren())
     116        children->invalidateCounters(m_renderer, identifier);
     117}
     118
     119void CounterNode::resetRenderers(const AtomicString& identifier) const
     120{
     121    const CounterNode* node = this;
     122    do {
     123        node->resetRenderer(identifier);
     124        node = node->nextInPreOrder(this);
     125    } while (node);
     126}
     127
     128void CounterNode::recount(const AtomicString& identifier)
     129{
     130    for (CounterNode* node = this; node; node = node->m_nextSibling) {
     131        int oldCount = node->m_countInParent;
     132        int newCount = node->computeCountInParent();
    64133        if (oldCount == newCount)
    65134            break;
    66         c->m_countInParent = newCount;
    67         // m_renderer contains the parent of the render node
    68         // corresponding to a CounterNode. Let's find the counter
    69         // child and make this re-layout.
    70         for (RenderObject* o = c->m_renderer->firstChild(); o; o = o->nextSibling())
    71             if (!o->documentBeingDestroyed() && o->isCounter()) {
    72                 o->setNeedsLayoutAndPrefWidthsRecalc();
    73                 break;
    74             }
    75     }
    76 }
    77 
    78 void CounterNode::insertAfter(CounterNode* newChild, CounterNode* refChild)
     135        node->m_countInParent = newCount;
     136        node->resetRenderers(identifier);
     137    }
     138}
     139
     140void CounterNode::insertAfter(CounterNode* newChild, CounterNode* refChild, const AtomicString& identifier)
    79141{
    80142    ASSERT(newChild);
     
    108170    newChild->m_countInParent = newChild->computeCountInParent();
    109171    if (next)
    110         next->recount();
    111 }
    112 
    113 void CounterNode::removeChild(CounterNode* oldChild)
     172        next->recount(identifier);
     173}
     174
     175void CounterNode::removeChild(CounterNode* oldChild, const AtomicString& identifier)
    114176{
    115177    ASSERT(oldChild);
     
    118180
    119181    CounterNode* next = oldChild->m_nextSibling;
    120     CounterNode* prev = oldChild->m_previousSibling;
     182    CounterNode* previous = oldChild->m_previousSibling;
    121183
    122184    oldChild->m_nextSibling = 0;
     
    124186    oldChild->m_parent = 0;
    125187
    126     if (prev)
    127         prev->m_nextSibling = next;
     188    if (previous)
     189        previous->m_nextSibling = next;
    128190    else {
    129191        ASSERT(m_firstChild == oldChild);
    130192        m_firstChild = next;
    131193    }
    132    
    133     if (next)
    134         next->m_previousSibling = prev;
     194
     195    if (next)
     196        next->m_previousSibling = previous;
    135197    else {
    136198        ASSERT(m_lastChild == oldChild);
    137         m_lastChild = prev;
    138     }
    139    
    140     if (next)
    141         next->recount();
     199        m_lastChild = previous;
     200    }
     201
     202    if (next)
     203        next->recount(identifier);
    142204}
    143205
    144206#ifndef NDEBUG
    145 
    146 static const CounterNode* nextInPreOrderAfterChildren(const CounterNode* node)
    147 {
    148     CounterNode* next = node->nextSibling();
    149     if (!next) {
    150         next = node->parent();
    151         while (next && !next->nextSibling())
    152             next = next->parent();
    153         if (next)
    154             next = next->nextSibling();
    155     }
    156     return next;
    157 }
    158 
    159 static const CounterNode* nextInPreOrder(const CounterNode* node)
    160 {
    161     if (CounterNode* child = node->firstChild())
    162         return child;
    163     return nextInPreOrderAfterChildren(node);
    164 }
    165207
    166208static void showTreeAndMark(const CounterNode* node)
  • trunk/WebCore/rendering/CounterNode.h

    r45891 r50960  
    3636namespace WebCore {
    3737
     38class AtomicString;
    3839class RenderObject;
    3940
     
    5253    CounterNode* firstChild() const { return m_firstChild; }
    5354    CounterNode* lastChild() const { return m_lastChild; }
     55    CounterNode* lastDescendant() const;
     56    CounterNode* previousInPreOrder() const;
     57    CounterNode* nextInPreOrder(const CounterNode* stayWithin = 0) const;
     58    CounterNode* nextInPreOrderAfterChildren(const CounterNode* stayWithin = 0) const;
    5459
    55     void insertAfter(CounterNode* newChild, CounterNode* beforeChild);
    56     void removeChild(CounterNode*);
     60    void insertAfter(CounterNode* newChild, CounterNode* beforeChild, const AtomicString& identifier);
     61    void removeChild(CounterNode*, const AtomicString& identifier);
    5762
    5863private:
    5964    int computeCountInParent() const;
    60     void recount();
     65    void recount(const AtomicString& identifier);
     66    void resetRenderer(const AtomicString& identifier) const;
     67    void resetRenderers(const AtomicString& identifier) const;
    6168
    6269    bool m_isReset;
  • trunk/WebCore/rendering/RenderCounter.cpp

    r50787 r50960  
    5252        return sibling;
    5353    return object->parent();
    54 }
    55 
    56 static CounterNode* lastDescendant(CounterNode* node)
    57 {
    58     CounterNode* last = node->lastChild();
    59     if (!last)
    60         return 0;
    61 
    62     while (CounterNode* lastChild = last->lastChild())
    63         last = lastChild;
    64 
    65     return last;
    66 }
    67 
    68 static CounterNode* previousInPreOrder(CounterNode* node)
    69 {
    70     CounterNode* previous = node->previousSibling();
    71     if (!previous)
    72         return node->parent();
    73 
    74     while (CounterNode* lastChild = previous->lastChild())
    75         previous = lastChild;
    76 
    77     return previous;
    7854}
    7955
     
    205181    if (findPlaceForCounter(object, counterName, isReset, newParent, newPreviousSibling)) {
    206182        newNode = new CounterNode(object, isReset, value);
    207         newParent->insertAfter(newNode, newPreviousSibling);
     183        newParent->insertAfter(newNode, newPreviousSibling, counterName);
    208184    } else {
    209185        // Make a reset node for counters that aren't inside an existing reset node.
     
    273249}
    274250
    275 void RenderCounter::invalidate()
    276 {
     251void RenderCounter::invalidate(const AtomicString& identifier)
     252{
     253    if (m_counter.identifier() != identifier)
     254        return;
    277255    m_counterNode = 0;
    278256    setNeedsLayoutAndPrefWidthsRecalc();
    279257}
    280258
    281 static void destroyCounterNodeChildren(AtomicStringImpl* identifier, CounterNode* node)
     259static void destroyCounterNodeChildren(const AtomicString& identifier, CounterNode* node)
    282260{
    283261    CounterNode* previous;
    284     for (CounterNode* child = lastDescendant(node); child && child != node; child = previous) {
    285         previous = previousInPreOrder(child);
    286         child->parent()->removeChild(child);
    287         ASSERT(counterMaps().get(child->renderer())->get(identifier) == child);
    288         counterMaps().get(child->renderer())->remove(identifier);
     262    for (CounterNode* child = node->lastDescendant(); child && child != node; child = previous) {
     263        previous = child->previousInPreOrder();
     264        child->parent()->removeChild(child, identifier);
     265        ASSERT(counterMaps().get(child->renderer())->get(identifier->impl()) == child);
     266        counterMaps().get(child->renderer())->remove(identifier.impl());
    289267        if (!child->renderer()->documentBeingDestroyed()) {
    290268            RenderObjectChildList* children = child->renderer()->virtualChildren();
    291269            if (children)
    292                 children->invalidateCounters(child->renderer());
     270                children->invalidateCounters(child->renderer(), identifier);
    293271        }
    294272        delete child;
     
    307285    for (CounterMap::const_iterator it = map->begin(); it != end; ++it) {
    308286        CounterNode* node = it->second;
    309         destroyCounterNodeChildren(it->first.get(), node);
     287        AtomicString identifier(it->first.get());
     288        destroyCounterNodeChildren(identifier, node);
    310289        if (CounterNode* parent = node->parent())
    311             parent->removeChild(node);
     290            parent->removeChild(node, identifier);
    312291        delete node;
    313292    }
  • trunk/WebCore/rendering/RenderCounter.h

    r46815 r50960  
    3434    RenderCounter(Document*, const CounterContent&);
    3535
    36     void invalidate();
     36    // Removes the reference to the CounterNode associated with this renderer
     37    // if its identifier matches the argument.
     38    // This is used to cause a counter display update when the CounterNode
     39    // tree for identifier changes.
     40    void invalidate(const AtomicString& identifier);
    3741
    3842    static void destroyCounterNodes(RenderObject*);
  • trunk/WebCore/rendering/RenderObjectChildList.cpp

    r50386 r50960  
    272272}
    273273
    274 static void invalidateCountersInContainer(RenderObject* container)
     274static void invalidateCountersInContainer(RenderObject* container, const AtomicString& identifier)
    275275{
    276276    if (!container)
     
    279279    if (!container)
    280280        return;
     281    // Sometimes the counter is attached directly on the container.
     282    if (container->isCounter()) {
     283        toRenderCounter(container)->invalidate(identifier);
     284        return;
     285    }
    281286    for (RenderObject* content = container->firstChild(); content; content = content->nextSibling()) {
    282287        if (content->isCounter())
    283             toRenderCounter(content)->invalidate();
    284     }
    285 }
    286 
    287 void RenderObjectChildList::invalidateCounters(RenderObject* owner)
     288            toRenderCounter(content)->invalidate(identifier);
     289    }
     290}
     291
     292void RenderObjectChildList::invalidateCounters(RenderObject* owner, const AtomicString& identifier)
    288293{
    289294    ASSERT(!owner->documentBeingDestroyed());
    290     invalidateCountersInContainer(beforeAfterContainer(owner, BEFORE));
    291     invalidateCountersInContainer(beforeAfterContainer(owner, AFTER));
     295    invalidateCountersInContainer(beforeAfterContainer(owner, BEFORE), identifier);
     296    invalidateCountersInContainer(beforeAfterContainer(owner, AFTER), identifier);
    292297}
    293298
  • trunk/WebCore/rendering/RenderObjectChildList.h

    r40651 r50960  
    3131namespace WebCore {
    3232
     33class AtomicString;
    3334class RenderObject;
    3435
     
    5657
    5758    void updateBeforeAfterContent(RenderObject* owner, PseudoId type, RenderObject* styledObject = 0);
    58     void invalidateCounters(RenderObject* owner);
     59    void invalidateCounters(RenderObject* owner, const AtomicString& identifier);
    5960
    6061private:
Note: See TracChangeset for help on using the changeset viewer.