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