Rename AtomicString to AtomString
[WebKit-https.git] / Source / WebCore / rendering / CounterNode.cpp
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
29 namespace WebCore {
30
31 CounterNode::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
39 CounterNode::~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
87 Ref<CounterNode> CounterNode::create(RenderElement& owner, bool hasResetType, int value)
88 {
89     return adoptRef(*new CounterNode(owner, hasResetType, value));
90 }
91
92 CounterNode* 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
107 CounterNode* CounterNode::nextInPreOrder(const CounterNode* stayWithin) const
108 {
109     if (CounterNode* next = m_firstChild)
110         return next;
111
112     return nextInPreOrderAfterChildren(stayWithin);
113 }
114
115 CounterNode* 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
127 CounterNode* 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
139 int 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
148 void 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
157 void 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
176 void 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
193 void CounterNode::resetThisAndDescendantsRenderers()
194 {
195     CounterNode* node = this;
196     do {
197         node->resetRenderers();
198         node = node->nextInPreOrder(this);
199     } while (node);
200 }
201
202 void 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
214 void CounterNode::insertAfter(CounterNode& newChild, CounterNode* beforeChild, const AtomString& 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
300 void 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
332 static 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
356 void showCounterTree(const WebCore::CounterNode* counter)
357 {
358     if (counter)
359         showTreeAndMark(counter);
360 }
361
362 #endif