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 "core/rendering/RenderCounter.h"
26
27#ifndef NDEBUG
28#include <stdio.h>
29#endif
30
31namespace blink {
32
33CounterNode::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
47CounterNode::~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
95PassRefPtr<CounterNode> CounterNode::create(RenderObject& owner, bool hasResetType, int value)
96{
97    return adoptRef(new CounterNode(owner, hasResetType, value));
98}
99
100CounterNode* CounterNode::nextInPreOrderAfterChildren(const CounterNode* stayWithin) const
101{
102    if (this == stayWithin)
103        return 0;
104
105    const CounterNode* current = this;
106    CounterNode* next = current->m_nextSibling;
107    for (; !next; next = current->m_nextSibling) {
108        current = current->m_parent;
109        if (!current || current == stayWithin)
110            return 0;
111    }
112    return next;
113}
114
115CounterNode* CounterNode::nextInPreOrder(const CounterNode* stayWithin) const
116{
117    if (CounterNode* next = m_firstChild)
118        return next;
119
120    return nextInPreOrderAfterChildren(stayWithin);
121}
122
123CounterNode* 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
135CounterNode* 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
147int 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
156void 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
184void 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
210void 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
216void CounterNode::resetThisAndDescendantsRenderers()
217{
218    CounterNode* node = this;
219    do {
220        node->resetRenderers();
221        node = node->nextInPreOrder(this);
222    } while (node);
223}
224
225void 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
237void 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
324void 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
357static 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 blink
378
379#ifndef NDEBUG
380
381void showCounterTree(const blink::CounterNode* counter)
382{
383    if (counter)
384        showTreeAndMark(counter);
385}
386
387#endif
388