Home | History | Annotate | Download | only in rendering 
      1 /*
      2  * Copyright (C) 2005 Allan Sandfeld Jensen (kde (at) carewolf.com)
      3  * Copyright (C) 2006, 2007 Apple Inc. All rights reserved.
      4  *
      5  * This library is free software; you can redistribute it and/or
      6  * modify it under the terms of the GNU Library General Public
      7  * License as published by the Free Software Foundation; either
      8  * version 2 of the License, or (at your option) any later version.
      9  *
     10  * This library is distributed in the hope that it will be useful,
     11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
     12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     13  * Library General Public License for more details.
     14  *
     15  * You should have received a copy of the GNU Library General Public License
     16  * along with this library; see the file COPYING.LIB.  If not, write to
     17  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
     18  * Boston, MA 02110-1301, USA.
     19  *
     20  */
     21 
     22 #include "config.h"
     23 #include "core/rendering/CounterNode.h"
     24 
     25 #include "core/rendering/RenderCounter.h"
     26 
     27 #ifndef NDEBUG
     28 #include <stdio.h>
     29 #endif
     30 
     31 namespace WebCore {
     32 
     33 CounterNode::CounterNode(RenderObject& o, bool hasResetType, int value)
     34     : m_hasResetType(hasResetType)
     35     , m_value(value)
     36     , m_countInParent(0)
     37     , m_owner(o)
     38     , m_rootRenderer(0)
     39     , m_parent(0)
     40     , m_previousSibling(0)
     41     , m_nextSibling(0)
     42     , m_firstChild(0)
     43     , m_lastChild(0)
     44 {
     45 }
     46 
     47 CounterNode::~CounterNode()
     48 {
     49     // Ideally this would be an assert and this would never be reached. In reality this happens a lot
     50     // so we need to handle these cases. The node is still connected to the tree so we need to detach it.
     51     if (m_parent || m_previousSibling || m_nextSibling || m_firstChild || m_lastChild) {
     52         CounterNode* oldParent = 0;
     53         CounterNode* oldPreviousSibling = 0;
     54         // Instead of calling removeChild() we do this safely as the tree is likely broken if we get here.
     55         if (m_parent) {
     56             if (m_parent->m_firstChild == this)
     57                 m_parent->m_firstChild = m_nextSibling;
     58             if (m_parent->m_lastChild == this)
     59                 m_parent->m_lastChild = m_previousSibling;
     60             oldParent = m_parent;
     61             m_parent = 0;
     62         }
     63         if (m_previousSibling) {
     64             if (m_previousSibling->m_nextSibling == this)
     65                 m_previousSibling->m_nextSibling = m_nextSibling;
     66             oldPreviousSibling = m_previousSibling;
     67             m_previousSibling = 0;
     68         }
     69         if (m_nextSibling) {
     70             if (m_nextSibling->m_previousSibling == this)
     71                 m_nextSibling->m_previousSibling = oldPreviousSibling;
     72             m_nextSibling = 0;
     73         }
     74         if (m_firstChild) {
     75             // The node's children are reparented to the old parent.
     76             for (CounterNode* child = m_firstChild; child; ) {
     77                 CounterNode* nextChild = child->m_nextSibling;
     78                 CounterNode* nextSibling = 0;
     79                 child->m_parent = oldParent;
     80                 if (oldPreviousSibling) {
     81                     nextSibling = oldPreviousSibling->m_nextSibling;
     82                     child->m_previousSibling = oldPreviousSibling;
     83                     oldPreviousSibling->m_nextSibling = child;
     84                     child->m_nextSibling = nextSibling;
     85                     nextSibling->m_previousSibling = child;
     86                     oldPreviousSibling = child;
     87                 }
     88                 child = nextChild;
     89             }
     90         }
     91     }
     92     resetRenderers();
     93 }
     94 
     95 PassRefPtr<CounterNode> CounterNode::create(RenderObject& owner, bool hasResetType, int value)
     96 {
     97     return adoptRef(new CounterNode(owner, hasResetType, value));
     98 }
     99 
    100 CounterNode* CounterNode::nextInPreOrderAfterChildren(const CounterNode* stayWithin) const
    101 {
    102     if (this == stayWithin)
    103         return 0;
    104 
    105     const CounterNode* current = this;
    106     CounterNode* next;
    107     while (!(next = current->m_nextSibling)) {
    108         current = current->m_parent;
    109         if (!current || current == stayWithin)
    110             return 0;
    111     }
    112     return next;
    113 }
    114 
    115 CounterNode* CounterNode::nextInPreOrder(const CounterNode* stayWithin) const
    116 {
    117     if (CounterNode* next = m_firstChild)
    118         return next;
    119 
    120     return nextInPreOrderAfterChildren(stayWithin);
    121 }
    122 
    123 CounterNode* CounterNode::lastDescendant() const
    124 {
    125     CounterNode* last = m_lastChild;
    126     if (!last)
    127         return 0;
    128 
    129     while (CounterNode* lastChild = last->m_lastChild)
    130         last = lastChild;
    131 
    132     return last;
    133 }
    134 
    135 CounterNode* CounterNode::previousInPreOrder() const
    136 {
    137     CounterNode* previous = m_previousSibling;
    138     if (!previous)
    139         return m_parent;
    140 
    141     while (CounterNode* lastChild = previous->m_lastChild)
    142         previous = lastChild;
    143 
    144     return previous;
    145 }
    146 
    147 int CounterNode::computeCountInParent() const
    148 {
    149     int increment = actsAsReset() ? 0 : m_value;
    150     if (m_previousSibling)
    151         return m_previousSibling->m_countInParent + increment;
    152     ASSERT(m_parent->m_firstChild == this);
    153     return m_parent->m_value + increment;
    154 }
    155 
    156 void CounterNode::addRenderer(RenderCounter* value)
    157 {
    158     if (!value) {
    159         ASSERT_NOT_REACHED();
    160         return;
    161     }
    162     if (value->m_counterNode) {
    163         ASSERT_NOT_REACHED();
    164         value->m_counterNode->removeRenderer(value);
    165     }
    166     ASSERT(!value->m_nextForSameCounter);
    167     for (RenderCounter* iterator = m_rootRenderer;iterator; iterator = iterator->m_nextForSameCounter) {
    168         if (iterator == value) {
    169             ASSERT_NOT_REACHED();
    170             return;
    171         }
    172     }
    173     value->m_nextForSameCounter = m_rootRenderer;
    174     m_rootRenderer = value;
    175     if (value->m_counterNode != this) {
    176         if (value->m_counterNode) {
    177             ASSERT_NOT_REACHED();
    178             value->m_counterNode->removeRenderer(value);
    179         }
    180         value->m_counterNode = this;
    181     }
    182 }
    183 
    184 void CounterNode::removeRenderer(RenderCounter* value)
    185 {
    186     if (!value) {
    187         ASSERT_NOT_REACHED();
    188         return;
    189     }
    190     if (value->m_counterNode && value->m_counterNode != this) {
    191         ASSERT_NOT_REACHED();
    192         value->m_counterNode->removeRenderer(value);
    193     }
    194     RenderCounter* previous = 0;
    195     for (RenderCounter* iterator = m_rootRenderer;iterator; iterator = iterator->m_nextForSameCounter) {
    196         if (iterator == value) {
    197             if (previous)
    198                 previous->m_nextForSameCounter = value->m_nextForSameCounter;
    199             else
    200                 m_rootRenderer = value->m_nextForSameCounter;
    201             value->m_nextForSameCounter = 0;
    202             value->m_counterNode = 0;
    203             return;
    204         }
    205         previous = iterator;
    206     }
    207     ASSERT_NOT_REACHED();
    208 }
    209 
    210 void CounterNode::resetRenderers()
    211 {
    212     while (m_rootRenderer)
    213         m_rootRenderer->invalidate(); // This makes m_rootRenderer point to the next renderer if any since it disconnects the m_rootRenderer from this.
    214 }
    215 
    216 void CounterNode::resetThisAndDescendantsRenderers()
    217 {
    218     CounterNode* node = this;
    219     do {
    220         node->resetRenderers();
    221         node = node->nextInPreOrder(this);
    222     } while (node);
    223 }
    224 
    225 void CounterNode::recount()
    226 {
    227     for (CounterNode* node = this; node; node = node->m_nextSibling) {
    228         int oldCount = node->m_countInParent;
    229         int newCount = node->computeCountInParent();
    230         if (oldCount == newCount)
    231             break;
    232         node->m_countInParent = newCount;
    233         node->resetThisAndDescendantsRenderers();
    234     }
    235 }
    236 
    237 void CounterNode::insertAfter(CounterNode* newChild, CounterNode* refChild, const AtomicString& identifier)
    238 {
    239     ASSERT(newChild);
    240     ASSERT(!newChild->m_parent);
    241     ASSERT(!newChild->m_previousSibling);
    242     ASSERT(!newChild->m_nextSibling);
    243     // If the refChild is not our child we can not complete the request. This hardens against bugs in RenderCounter.
    244     // When renderers are reparented it may request that we insert counter nodes improperly.
    245     if (refChild && refChild->m_parent != this)
    246         return;
    247 
    248     if (newChild->m_hasResetType) {
    249         while (m_lastChild != refChild)
    250             RenderCounter::destroyCounterNode(m_lastChild->owner(), identifier);
    251     }
    252 
    253     CounterNode* next;
    254 
    255     if (refChild) {
    256         next = refChild->m_nextSibling;
    257         refChild->m_nextSibling = newChild;
    258     } else {
    259         next = m_firstChild;
    260         m_firstChild = newChild;
    261     }
    262 
    263     newChild->m_parent = this;
    264     newChild->m_previousSibling = refChild;
    265 
    266     if (next) {
    267         ASSERT(next->m_previousSibling == refChild);
    268         next->m_previousSibling = newChild;
    269         newChild->m_nextSibling = next;
    270     } else {
    271         ASSERT(m_lastChild == refChild);
    272         m_lastChild = newChild;
    273     }
    274 
    275     if (!newChild->m_firstChild || newChild->m_hasResetType) {
    276         newChild->m_countInParent = newChild->computeCountInParent();
    277         newChild->resetThisAndDescendantsRenderers();
    278         if (next)
    279             next->recount();
    280         return;
    281     }
    282 
    283     // The code below handles the case when a formerly root increment counter is loosing its root position
    284     // and therefore its children become next siblings.
    285     CounterNode* last = newChild->m_lastChild;
    286     CounterNode* first = newChild->m_firstChild;
    287 
    288     if (first) {
    289         ASSERT(last);
    290         newChild->m_nextSibling = first;
    291         if (m_lastChild == newChild)
    292             m_lastChild = last;
    293 
    294         first->m_previousSibling = newChild;
    295 
    296         // The case when the original next sibling of the inserted node becomes a child of
    297         // one of the former children of the inserted node is not handled as it is believed
    298         // to be impossible since:
    299         // 1. if the increment counter node lost it's root position as a result of another
    300         //    counter node being created, it will be inserted as the last child so next is null.
    301         // 2. if the increment counter node lost it's root position as a result of a renderer being
    302         //    inserted into the document's render tree, all its former children counters are attached
    303         //    to children of the inserted renderer and hence cannot be in scope for counter nodes
    304         //    attached to renderers that were already in the document's render tree.
    305         last->m_nextSibling = next;
    306         if (next) {
    307             ASSERT(next->m_previousSibling == newChild);
    308             next->m_previousSibling = last;
    309         } else
    310             m_lastChild = last;
    311         for (next = first; ; next = next->m_nextSibling) {
    312             next->m_parent = this;
    313             if (last == next)
    314                 break;
    315         }
    316     }
    317     newChild->m_firstChild = 0;
    318     newChild->m_lastChild = 0;
    319     newChild->m_countInParent = newChild->computeCountInParent();
    320     newChild->resetRenderers();
    321     first->recount();
    322 }
    323 
    324 void CounterNode::removeChild(CounterNode* oldChild)
    325 {
    326     ASSERT(oldChild);
    327     ASSERT(!oldChild->m_firstChild);
    328     ASSERT(!oldChild->m_lastChild);
    329 
    330     CounterNode* next = oldChild->m_nextSibling;
    331     CounterNode* previous = oldChild->m_previousSibling;
    332 
    333     oldChild->m_nextSibling = 0;
    334     oldChild->m_previousSibling = 0;
    335     oldChild->m_parent = 0;
    336 
    337     if (previous)
    338         previous->m_nextSibling = next;
    339     else {
    340         ASSERT(m_firstChild == oldChild);
    341         m_firstChild = next;
    342     }
    343 
    344     if (next)
    345         next->m_previousSibling = previous;
    346     else {
    347         ASSERT(m_lastChild == oldChild);
    348         m_lastChild = previous;
    349     }
    350 
    351     if (next)
    352         next->recount();
    353 }
    354 
    355 #ifndef NDEBUG
    356 
    357 static void showTreeAndMark(const CounterNode* node)
    358 {
    359     const CounterNode* root = node;
    360     while (root->parent())
    361         root = root->parent();
    362 
    363     for (const CounterNode* current = root; current; current = current->nextInPreOrder()) {
    364         fprintf(stderr, "%c", (current == node) ? '*' : ' ');
    365         for (const CounterNode* parent = current; parent && parent != root; parent = parent->parent())
    366             fprintf(stderr, "    ");
    367         fprintf(stderr, "%p %s: %d %d P:%p PS:%p NS:%p R:%p\n",
    368             current, current->actsAsReset() ? "reset____" : "increment", current->value(),
    369             current->countInParent(), current->parent(), current->previousSibling(),
    370             current->nextSibling(), &current->owner());
    371     }
    372     fflush(stderr);
    373 }
    374 
    375 #endif
    376 
    377 } // namespace WebCore
    378 
    379 #ifndef NDEBUG
    380 
    381 void showCounterTree(const WebCore::CounterNode* counter)
    382 {
    383     if (counter)
    384         showTreeAndMark(counter);
    385 }
    386 
    387 #endif
    388