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