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