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