WebCore/dom/Node.cpp

   1 /*
   2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
   3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
   4  *           (C) 2001 Dirk Mueller (mueller@kde.org)
   5  * Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
   6  * Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies)
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Library General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Library General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Library General Public License
  19  * along with this library; see the file COPYING.LIB.  If not, write to
  20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  21  * Boston, MA 02110-1301, USA.
  22  */
  23
  24 #include "config.h"
  25 #include "Node.h"
  26
  27 #include "CSSParser.h"
  28 #include "CSSRule.h"
  29 #include "CSSRuleList.h"
  30 #include "CSSSelector.h"
  31 #include "CSSStyleRule.h"
  32 #include "CSSStyleSelector.h"
  33 #include "CSSStyleSheet.h"
  34 #include "CString.h"
  35 #include "ChildNodeList.h"
  36 #include "ClassNodeList.h"
  37 #include "DOMImplementation.h"
  38 #include "Document.h"
  39 #include "DynamicNodeList.h"
  40 #include "Element.h"
  41 #include "ExceptionCode.h"
  42 #include "Frame.h"
  43 #include "HTMLNames.h"
  44 #include "JSDOMBinding.h"
  45 #include "Logging.h"
  46 #include "NameNodeList.h"
  47 #include "NamedAttrMap.h"
  48 #include "NodeRareData.h"
  49 #include "ProcessingInstruction.h"
  50 #include "RenderObject.h"
  51 #include "ScriptController.h"
  52 #include "SelectorNodeList.h"
  53 #include "StringBuilder.h"
  54 #include "TagNodeList.h"
  55 #include "Text.h"
  56 #include "XMLNames.h"
  57 #include "htmlediting.h"
  58 #include <runtime/ExecState.h>
  59 #include <runtime/JSLock.h>
  60 #include <wtf/RefCountedLeakCounter.h>
  61
  62 namespace WebCore {
  63
  64 using namespace HTMLNames;
  65
  66 // --------
  67
  68 bool Node::isSupported(const String& feature, const String& version)
  69 {
  70     return DOMImplementation::hasFeature(feature, version);
  71 }
  72
  73 #ifndef NDEBUG
  74 static WTF::RefCountedLeakCounter nodeCounter("WebCoreNode");
  75
  76 static bool shouldIgnoreLeaks = false;
  77 static HashSet<Node*> ignoreSet;
  78 #endif
  79
  80 void Node::startIgnoringLeaks()
  81 {
  82 #ifndef NDEBUG
  83     shouldIgnoreLeaks = true;
  84 #endif
  85 }
  86
  87 void Node::stopIgnoringLeaks()
  88 {
  89 #ifndef NDEBUG
  90     shouldIgnoreLeaks = false;
  91 #endif
  92 }
  93
  94 Node::StyleChange Node::diff( RenderStyle *s1, RenderStyle *s2 )
  95 {
  96     // FIXME: The behavior of this function is just totally wrong.  It doesn't handle
  97     // explicit inheritance of non-inherited properties and so you end up not re-resolving
  98     // style in cases where you need to.
  99     StyleChange ch = NoInherit;
 100     EDisplay display1 = s1 ? s1->display() : NONE;
 101     bool fl1 = s1 && s1->hasPseudoStyle(RenderStyle::FIRST_LETTER);
 102     EDisplay display2 = s2 ? s2->display() : NONE;
 103     bool fl2 = s2 && s2->hasPseudoStyle(RenderStyle::FIRST_LETTER);
 104
 105     if (display1 != display2 || fl1 != fl2 || (s1 && s2 && !s1->contentDataEquivalent(s2)))
 106         ch = Detach;
 107     else if (!s1 || !s2)
 108         ch = Inherit;
 109     else if (*s1 == *s2)
 110         ch = NoChange;
 111     else if (s1->inheritedNotEqual(s2))
 112         ch = Inherit;
 113
 114     // If the pseudoStyles have changed, we want any StyleChange that is not NoChange
 115     // because setStyle will do the right thing with anything else.
 116     if (ch == NoChange && s1->hasPseudoStyle(RenderStyle::BEFORE)) {
 117         RenderStyle* ps2 = s2->getCachedPseudoStyle(RenderStyle::BEFORE);
 118         if (!ps2)
 119             ch = NoInherit;
 120         else {
 121             RenderStyle* ps1 = s1->getCachedPseudoStyle(RenderStyle::BEFORE);
 122             ch = ps1 && *ps1 == *ps2 ? NoChange : NoInherit;
 123         }
 124     }
 125     if (ch == NoChange && s1->hasPseudoStyle(RenderStyle::AFTER)) {
 126         RenderStyle* ps2 = s2->getCachedPseudoStyle(RenderStyle::AFTER);
 127         if (!ps2)
 128             ch = NoInherit;
 129         else {
 130             RenderStyle* ps1 = s1->getCachedPseudoStyle(RenderStyle::AFTER);
 131             ch = ps2 && *ps1 == *ps2 ? NoChange : NoInherit;
 132         }
 133     }
 134
 135     return ch;
 136 }
 137
 138 Node::Node(Document* doc, bool isElement, bool isContainer)
 139     : m_document(doc)
 140     , m_previous(0)
 141     , m_next(0)
 142     , m_renderer(0)
 143     , m_styleChange(NoStyleChange)
 144     , m_hasId(false)
 145     , m_hasClass(false)
 146     , m_attached(false)
 147     , m_hasChangedChild(false)
 148     , m_inDocument(false)
 149     , m_isLink(false)
 150     , m_active(false)
 151     , m_hovered(false)
 152     , m_inActiveChain(false)
 153     , m_inDetach(false)
 154     , m_inSubtreeMark(false)
 155     , m_hasRareData(false)
 156     , m_isElement(isElement)
 157     , m_isContainer(isContainer)
 158 {
 159 #ifndef NDEBUG
 160     if (shouldIgnoreLeaks)
 161         ignoreSet.add(this);
 162     else
 163         nodeCounter.increment();
 164 #endif
 165 }
 166
 167 void Node::setDocument(Document* doc)
 168 {
 169     if (inDocument() || m_document == doc)
 170         return;
 171
 172     willMoveToNewOwnerDocument();
 173
 174     updateDOMNodeDocument(this, m_document.get(), doc);
 175
 176     m_document = doc;
 177
 178     didMoveToNewOwnerDocument();
 179 }
 180
 181 Node::~Node()
 182 {
 183 #ifndef NDEBUG
 184     HashSet<Node*>::iterator it = ignoreSet.find(this);
 185     if (it != ignoreSet.end())
 186         ignoreSet.remove(it);
 187     else
 188         nodeCounter.decrement();
 189 #endif
 190
 191     if (!hasRareData())
 192         ASSERT(!NodeRareData::rareDataMap().contains(this));
 193     else {
 194         if (m_document && rareData()->nodeLists())
 195             m_document->removeNodeListCache();
 196
 197         NodeRareData::NodeRareDataMap& dataMap = NodeRareData::rareDataMap();
 198         NodeRareData::NodeRareDataMap::iterator it = dataMap.find(this);
 199         ASSERT(it != dataMap.end());
 200         delete it->second;
 201         dataMap.remove(it);
 202     }
 203
 204     if (renderer())
 205         detach();
 206
 207     if (m_previous)
 208         m_previous->setNextSibling(0);
 209     if (m_next)
 210         m_next->setPreviousSibling(0);
 211 }
 212
 213 inline NodeRareData* Node::rareData() const
 214 {
 215     ASSERT(hasRareData());
 216     return NodeRareData::rareDataFromMap(this);
 217 }
 218
 219 NodeRareData* Node::ensureRareData()
 220 {
 221     if (hasRareData())
 222         return rareData();
 223
 224     ASSERT(!NodeRareData::rareDataMap().contains(this));
 225     NodeRareData* data = createRareData();
 226     NodeRareData::rareDataMap().set(this, data);
 227     m_hasRareData = true;
 228     return data;
 229 }
 230
 231 NodeRareData* Node::createRareData()
 232 {
 233     return new NodeRareData;
 234 }
 235
 236 short Node::tabIndex() const
 237 {
 238     return hasRareData() ? rareData()->tabIndex() : 0;
 239 }
 240
 241 void Node::setTabIndexExplicitly(short i)
 242 {
 243     ensureRareData()->setTabIndexExplicitly(i);
 244 }
 245
 246 String Node::nodeValue() const
 247 {
 248   return String();
 249 }
 250
 251 void Node::setNodeValue(const String& /*nodeValue*/, ExceptionCode& ec)
 252 {
 253     // NO_MODIFICATION_ALLOWED_ERR: Raised when the node is readonly
 254     if (isReadOnlyNode()) {
 255         ec = NO_MODIFICATION_ALLOWED_ERR;
 256         return;
 257     }
 258
 259     // By default, setting nodeValue has no effect.
 260 }
 261
 262 PassRefPtr<NodeList> Node::childNodes()
 263 {
 264     NodeRareData* data = ensureRareData();
 265     if (!data->nodeLists()) {
 266         data->setNodeLists(std::auto_ptr<NodeListsNodeData>(new NodeListsNodeData));
 267         document()->addNodeListCache();
 268     }
 269
 270     return ChildNodeList::create(this, &data->nodeLists()->m_childNodeListCaches);
 271 }
 272
 273 Node *Node::lastDescendant() const
 274 {
 275     Node *n = const_cast<Node *>(this);
 276     while (n && n->lastChild())
 277         n = n->lastChild();
 278     return n;
 279 }
 280
 281 Node* Node::firstDescendant() const
 282 {
 283     Node *n = const_cast<Node *>(this);
 284     while (n && n->firstChild())
 285         n = n->firstChild();
 286     return n;
 287 }
 288
 289 bool Node::insertBefore(PassRefPtr<Node>, Node*, ExceptionCode& ec, bool)
 290 {
 291     ec = HIERARCHY_REQUEST_ERR;
 292     return false;
 293 }
 294
 295 bool Node::replaceChild(PassRefPtr<Node>, Node*, ExceptionCode& ec, bool)
 296 {
 297     ec = HIERARCHY_REQUEST_ERR;
 298     return false;
 299 }
 300
 301 bool Node::removeChild(Node*, ExceptionCode& ec)
 302 {
 303     ec = NOT_FOUND_ERR;
 304     return false;
 305 }
 306
 307 bool Node::appendChild(PassRefPtr<Node>, ExceptionCode& ec, bool)
 308 {
 309     ec = HIERARCHY_REQUEST_ERR;
 310     return false;
 311 }
 312
 313 void Node::remove(ExceptionCode& ec)
 314 {
 315     ref();
 316     if (Node *p = parentNode())
 317         p->removeChild(this, ec);
 318     else
 319         ec = HIERARCHY_REQUEST_ERR;
 320     deref();
 321 }
 322
 323 void Node::normalize()
 324 {
 325     // Go through the subtree beneath us, normalizing all nodes. This means that
 326     // any two adjacent text nodes are merged together.
 327
 328     RefPtr<Node> node = this;
 329     while (Node* firstChild = node->firstChild())
 330         node = firstChild;
 331     for (; node; node = node->traverseNextNodePostOrder()) {
 332         NodeType type = node->nodeType();
 333         if (type == ELEMENT_NODE)
 334             static_cast<Element*>(node.get())->normalizeAttributes();
 335
 336         Node* firstChild = node->firstChild();
 337         if (firstChild && !firstChild->nextSibling() && firstChild->isTextNode()) {
 338             Text* text = static_cast<Text*>(firstChild);
 339             if (!text->length()) {
 340                 ExceptionCode ec;
 341                 text->remove(ec);
 342             }
 343         }
 344
 345         if (node == this)
 346             break;
 347
 348         if (type == TEXT_NODE) {
 349             while (1) {
 350                 Node* nextSibling = node->nextSibling();
 351                 if (!nextSibling || !nextSibling->isTextNode())
 352                     break;
 353                 // Current child and the next one are both text nodes. Merge them.
 354                 Text* text = static_cast<Text*>(node.get());
 355                 RefPtr<Text> nextText = static_cast<Text*>(nextSibling);
 356                 unsigned offset = text->length();
 357                 ExceptionCode ec;
 358                 text->appendData(nextText->data(), ec);
 359                 document()->textNodesMerged(nextText.get(), offset);
 360                 nextText->remove(ec);
 361             }
 362         }
 363     }
 364 }
 365
 366 const AtomicString& Node::virtualPrefix() const
 367 {
 368     // For nodes other than elements and attributes, the prefix is always null
 369     return nullAtom;
 370 }
 371
 372 void Node::setPrefix(const AtomicString& /*prefix*/, ExceptionCode& ec)
 373 {
 374     // The spec says that for nodes other than elements and attributes, prefix is always null.
 375     // It does not say what to do when the user tries to set the prefix on another type of
 376     // node, however Mozilla throws a NAMESPACE_ERR exception.
 377     ec = NAMESPACE_ERR;
 378 }
 379
 380 const AtomicString& Node::virtualLocalName() const
 381 {
 382     return nullAtom;
 383 }
 384
 385 const AtomicString& Node::virtualNamespaceURI() const
 386 {
 387     return nullAtom;
 388 }
 389
 390 ContainerNode* Node::addChild(PassRefPtr<Node>)
 391 {
 392     return 0;
 393 }
 394
 395 bool Node::isContentEditable() const
 396 {
 397     return parent() && parent()->isContentEditable();
 398 }
 399
 400 bool Node::isContentRichlyEditable() const
 401 {
 402     return parent() && parent()->isContentRichlyEditable();
 403 }
 404
 405 bool Node::shouldUseInputMethod() const
 406 {
 407     return isContentEditable();
 408 }
 409
 410 IntRect Node::getRect() const
 411 {
 412     // FIXME: broken with transforms
 413     if (renderer()) {
 414         FloatPoint absPos = renderer()->localToAbsolute();
 415         return IntRect(roundedIntPoint(absPos),
 416                        IntSize(renderer()->width(), renderer()->height() + renderer()->borderTopExtra() + renderer()->borderBottomExtra()));
 417     }
 418     return IntRect();
 419 }
 420
 421 void Node::setChanged(StyleChangeType changeType)
 422 {
 423     if ((changeType != NoStyleChange) && !attached()) // changed compared to what?
 424         return;
 425
 426     if (!(changeType == InlineStyleChange && (m_styleChange == FullStyleChange || m_styleChange == AnimationStyleChange)))
 427         m_styleChange = changeType;
 428
 429     if (m_styleChange != NoStyleChange) {
 430         for (Node* p = parentNode(); p && !p->hasChangedChild(); p = p->parentNode())
 431             p->setHasChangedChild(true);
 432         document()->setDocumentChanged(true);
 433     }
 434 }
 435
 436 static Node* outermostLazyAttachedAncestor(Node* start)
 437 {
 438     Node* p = start;
 439     for (Node* next = p->parentNode(); !next->renderer(); p = next, next = next->parentNode()) {}
 440     return p;
 441 }
 442
 443 void Node::lazyAttach()
 444 {
 445     bool mustDoFullAttach = false;
 446
 447     for (Node* n = this; n; n = n->traverseNextNode(this)) {
 448         if (!n->canLazyAttach()) {
 449             mustDoFullAttach = true;
 450             break;
 451         }
 452
 453         if (n->firstChild())
 454             n->setHasChangedChild(true);
 455         n->m_styleChange = FullStyleChange;
 456         n->m_attached = true;
 457     }
 458
 459     if (mustDoFullAttach) {
 460         Node* lazyAttachedAncestor = outermostLazyAttachedAncestor(this);
 461         if (lazyAttachedAncestor->attached())
 462             lazyAttachedAncestor->detach();
 463         lazyAttachedAncestor->attach();
 464     } else {
 465         for (Node* p = parentNode(); p && !p->hasChangedChild(); p = p->parentNode())
 466             p->setHasChangedChild(true);
 467         document()->setDocumentChanged(true);
 468     }
 469 }
 470
 471 bool Node::canLazyAttach()
 472 {
 473     return shadowAncestorNode() == this;
 474 }
 475
 476 void Node::setFocus(bool b)
 477 {
 478     if (b || hasRareData())
 479         ensureRareData()->m_focused = b;
 480 }
 481
 482 bool Node::rareDataFocused() const
 483 {
 484     ASSERT(hasRareData());
 485     return rareData()->m_focused;
 486 }
 487
 488 bool Node::isFocusable() const
 489 {
 490     return hasRareData() && rareData()->tabIndexSetExplicitly();
 491 }
 492
 493 bool Node::isKeyboardFocusable(KeyboardEvent*) const
 494 {
 495     return isFocusable() && tabIndex() >= 0;
 496 }
 497
 498 bool Node::isMouseFocusable() const
 499 {
 500     return isFocusable();
 501 }
 502
 503 unsigned Node::nodeIndex() const
 504 {
 505     Node *_tempNode = previousSibling();
 506     unsigned count=0;
 507     for( count=0; _tempNode; count++ )
 508         _tempNode = _tempNode->previousSibling();
 509     return count;
 510 }
 511
 512 void Node::registerDynamicNodeList(DynamicNodeList* list)
 513 {
 514     NodeRareData* data = ensureRareData();
 515     if (!data->nodeLists()) {
 516         data->setNodeLists(std::auto_ptr<NodeListsNodeData>(new NodeListsNodeData));
 517         document()->addNodeListCache();
 518     } else if (!m_document->hasNodeListCaches()) {
 519         // We haven't been receiving notifications while there were no registered lists, so the cache is invalid now.
 520         data->nodeLists()->invalidateCaches();
 521     }
 522
 523     if (list->hasOwnCaches())
 524         data->nodeLists()->m_listsWithCaches.add(list);
 525 }
 526
 527 void Node::unregisterDynamicNodeList(DynamicNodeList* list)
 528 {
 529     ASSERT(rareData());
 530     ASSERT(rareData()->nodeLists());
 531     if (list->hasOwnCaches()) {
 532         NodeRareData* data = rareData();
 533         data->nodeLists()->m_listsWithCaches.remove(list);
 534         if (data->nodeLists()->isEmpty()) {
 535             data->clearNodeLists();
 536             document()->removeNodeListCache();
 537         }
 538     }
 539 }
 540
 541 void Node::notifyLocalNodeListsAttributeChanged()
 542 {
 543     if (!hasRareData())
 544         return;
 545     NodeRareData* data = rareData();
 546     if (!data->nodeLists())
 547         return;
 548
 549     data->nodeLists()->invalidateCachesThatDependOnAttributes();
 550
 551     if (data->nodeLists()->isEmpty()) {
 552         data->clearNodeLists();
 553         document()->removeNodeListCache();
 554     }
 555 }
 556
 557 void Node::notifyNodeListsAttributeChanged()
 558 {
 559     for (Node *n = this; n; n = n->parentNode())
 560         n->notifyLocalNodeListsAttributeChanged();
 561 }
 562
 563 void Node::notifyLocalNodeListsChildrenChanged()
 564 {
 565     if (!hasRareData())
 566         return;
 567     NodeRareData* data = rareData();
 568     if (!data->nodeLists())
 569         return;
 570
 571     data->nodeLists()->invalidateCaches();
 572
 573     NodeListsNodeData::NodeListSet::iterator end = data->nodeLists()->m_listsWithCaches.end();
 574     for (NodeListsNodeData::NodeListSet::iterator i = data->nodeLists()->m_listsWithCaches.begin(); i != end; ++i)
 575         (*i)->invalidateCache();
 576
 577     if (data->nodeLists()->isEmpty()) {
 578         data->clearNodeLists();
 579         document()->removeNodeListCache();
 580     }
 581 }
 582
 583 void Node::notifyNodeListsChildrenChanged()
 584 {
 585     for (Node* n = this; n; n = n->parentNode())
 586         n->notifyLocalNodeListsChildrenChanged();
 587 }
 588
 589 Node *Node::traverseNextNode(const Node *stayWithin) const
 590 {
 591     if (firstChild())
 592         return firstChild();
 593     if (this == stayWithin)
 594         return 0;
 595     if (nextSibling())
 596         return nextSibling();
 597     const Node *n = this;
 598     while (n && !n->nextSibling() && (!stayWithin || n->parentNode() != stayWithin))
 599         n = n->parentNode();
 600     if (n)
 601         return n->nextSibling();
 602     return 0;
 603 }
 604
 605 Node *Node::traverseNextSibling(const Node *stayWithin) const
 606 {
 607     if (this == stayWithin)
 608         return 0;
 609     if (nextSibling())
 610         return nextSibling();
 611     const Node *n = this;
 612     while (n && !n->nextSibling() && (!stayWithin || n->parentNode() != stayWithin))
 613         n = n->parentNode();
 614     if (n)
 615         return n->nextSibling();
 616     return 0;
 617 }
 618
 619 Node* Node::traverseNextNodePostOrder() const
 620 {
 621     Node* next = nextSibling();
 622     if (!next)
 623         return parentNode();
 624     while (Node* firstChild = next->firstChild())
 625         next = firstChild;
 626     return next;
 627 }
 628
 629 Node *Node::traversePreviousNode(const Node *stayWithin) const
 630 {
 631     if (this == stayWithin)
 632         return 0;
 633     if (previousSibling()) {
 634         Node *n = previousSibling();
 635         while (n->lastChild())
 636             n = n->lastChild();
 637         return n;
 638     }
 639     return parentNode();
 640 }
 641
 642 Node *Node::traversePreviousNodePostOrder(const Node *stayWithin) const
 643 {
 644     if (lastChild())
 645         return lastChild();
 646     if (this == stayWithin)
 647         return 0;
 648     if (previousSibling())
 649         return previousSibling();
 650     const Node *n = this;
 651     while (n && !n->previousSibling() && (!stayWithin || n->parentNode() != stayWithin))
 652         n = n->parentNode();
 653     if (n)
 654         return n->previousSibling();
 655     return 0;
 656 }
 657
 658 Node* Node::traversePreviousSiblingPostOrder(const Node* stayWithin) const
 659 {
 660     if (this == stayWithin)
 661         return 0;
 662     if (previousSibling())
 663         return previousSibling();
 664     const Node *n = this;
 665     while (n && !n->previousSibling() && (!stayWithin || n->parentNode() != stayWithin))
 666         n = n->parentNode();
 667     if (n)
 668         return n->previousSibling();
 669     return 0;
 670 }
 671
 672 void Node::checkSetPrefix(const AtomicString &_prefix, ExceptionCode& ec)
 673 {
 674     // Perform error checking as required by spec for setting Node.prefix. Used by
 675     // Element::setPrefix() and Attr::setPrefix()
 676
 677     // FIXME: Implement support for INVALID_CHARACTER_ERR: Raised if the specified prefix contains an illegal character.
 678
 679     // NO_MODIFICATION_ALLOWED_ERR: Raised if this node is readonly.
 680     if (isReadOnlyNode()) {
 681         ec = NO_MODIFICATION_ALLOWED_ERR;
 682         return;
 683     }
 684
 685     // FIXME: Implement NAMESPACE_ERR: - Raised if the specified prefix is malformed
 686     // We have to comment this out, since it's used for attributes and tag names, and we've only
 687     // switched one over.
 688     /*
 689     // - if the namespaceURI of this node is null,
 690     // - if the specified prefix is "xml" and the namespaceURI of this node is different from
 691     //   "http://www.w3.org/XML/1998/namespace",
 692     // - if this node is an attribute and the specified prefix is "xmlns" and
 693     //   the namespaceURI of this node is different from "http://www.w3.org/2000/xmlns/",
 694     // - or if this node is an attribute and the qualifiedName of this node is "xmlns" [Namespaces].
 695     if ((namespacePart(id()) == noNamespace && id() > ID_LAST_TAG) ||
 696         (_prefix == "xml" && String(document()->namespaceURI(id())) != "http://www.w3.org/XML/1998/namespace")) {
 697         ec = NAMESPACE_ERR;
 698         return;
 699     }*/
 700 }
 701
 702 bool Node::canReplaceChild(Node* newChild, Node* oldChild)
 703 {
 704     if (newChild->nodeType() != DOCUMENT_FRAGMENT_NODE) {
 705         if (!childTypeAllowed(newChild->nodeType()))
 706             return false;
 707     }
 708     else {
 709         for (Node *n = newChild->firstChild(); n; n = n->nextSibling()) {
 710             if (!childTypeAllowed(n->nodeType()))
 711                 return false;
 712         }
 713     }
 714
 715     return true;
 716 }
 717
 718 void Node::checkReplaceChild(Node* newChild, Node* oldChild, ExceptionCode& ec)
 719 {
 720     // Perform error checking as required by spec for adding a new child. Used by
 721     // appendChild(), replaceChild() and insertBefore()
 722
 723     // Not mentioned in spec: throw NOT_FOUND_ERR if newChild is null
 724     if (!newChild) {
 725         ec = NOT_FOUND_ERR;
 726         return;
 727     }
 728
 729     // NO_MODIFICATION_ALLOWED_ERR: Raised if this node is readonly
 730     if (isReadOnlyNode()) {
 731         ec = NO_MODIFICATION_ALLOWED_ERR;
 732         return;
 733     }
 734
 735     bool shouldAdoptChild = false;
 736
 737     // WRONG_DOCUMENT_ERR: Raised if newChild was created from a different document than the one that
 738     // created this node.
 739     // We assume that if newChild is a DocumentFragment, all children are created from the same document
 740     // as the fragment itself (otherwise they could not have been added as children)
 741     if (newChild->document() != document()) {
 742         // but if the child is not in a document yet then loosen the
 743         // restriction, so that e.g. creating an element with the Option()
 744         // constructor and then adding it to a different document works,
 745         // as it does in Mozilla and Mac IE.
 746         if (!newChild->inDocument()) {
 747             shouldAdoptChild = true;
 748         } else {
 749             ec = WRONG_DOCUMENT_ERR;
 750             return;
 751         }
 752     }
 753
 754     // HIERARCHY_REQUEST_ERR: Raised if this node is of a type that does not allow children of the type of the
 755     // newChild node, or if the node to append is one of this node's ancestors.
 756
 757     // check for ancestor/same node
 758     if (newChild == this || isDescendantOf(newChild)) {
 759         ec = HIERARCHY_REQUEST_ERR;
 760         return;
 761     }
 762
 763     if (!canReplaceChild(newChild, oldChild)) {
 764         ec = HIERARCHY_REQUEST_ERR;
 765         return;
 766     }
 767
 768     // change the document pointer of newChild and all of its children to be the new document
 769     if (shouldAdoptChild)
 770         for (Node* node = newChild; node; node = node->traverseNextNode(newChild))
 771             node->setDocument(document());
 772 }
 773
 774 void Node::checkAddChild(Node *newChild, ExceptionCode& ec)
 775 {
 776     // Perform error checking as required by spec for adding a new child. Used by
 777     // appendChild(), replaceChild() and insertBefore()
 778
 779     // Not mentioned in spec: throw NOT_FOUND_ERR if newChild is null
 780     if (!newChild) {
 781         ec = NOT_FOUND_ERR;
 782         return;
 783     }
 784
 785     // NO_MODIFICATION_ALLOWED_ERR: Raised if this node is readonly
 786     if (isReadOnlyNode()) {
 787         ec = NO_MODIFICATION_ALLOWED_ERR;
 788         return;
 789     }
 790
 791     bool shouldAdoptChild = false;
 792
 793     // WRONG_DOCUMENT_ERR: Raised if newChild was created from a different document than the one that
 794     // created this node.
 795     // We assume that if newChild is a DocumentFragment, all children are created from the same document
 796     // as the fragment itself (otherwise they could not have been added as children)
 797     if (newChild->document() != document()) {
 798         // but if the child is not in a document yet then loosen the
 799         // restriction, so that e.g. creating an element with the Option()
 800         // constructor and then adding it to a different document works,
 801         // as it does in Mozilla and Mac IE.
 802         if (!newChild->inDocument()) {
 803             shouldAdoptChild = true;
 804         } else {
 805             ec = WRONG_DOCUMENT_ERR;
 806             return;
 807         }
 808     }
 809
 810     // HIERARCHY_REQUEST_ERR: Raised if this node is of a type that does not allow children of the type of the
 811     // newChild node, or if the node to append is one of this node's ancestors.
 812
 813     // check for ancestor/same node
 814     if (newChild == this || isDescendantOf(newChild)) {
 815         ec = HIERARCHY_REQUEST_ERR;
 816         return;
 817     }
 818
 819     if (newChild->nodeType() != DOCUMENT_FRAGMENT_NODE) {
 820         if (!childTypeAllowed(newChild->nodeType())) {
 821             ec = HIERARCHY_REQUEST_ERR;
 822             return;
 823         }
 824     }
 825     else {
 826         for (Node *n = newChild->firstChild(); n; n = n->nextSibling()) {
 827             if (!childTypeAllowed(n->nodeType())) {
 828                 ec = HIERARCHY_REQUEST_ERR;
 829                 return;
 830             }
 831         }
 832     }
 833
 834     // change the document pointer of newChild and all of its children to be the new document
 835     if (shouldAdoptChild)
 836         for (Node* node = newChild; node; node = node->traverseNextNode(newChild))
 837             node->setDocument(document());
 838 }
 839
 840 bool Node::isDescendantOf(const Node *other) const
 841 {
 842     // Return true if other is an ancestor of this, otherwise false
 843     if (!other)
 844         return false;
 845     for (const Node *n = parentNode(); n; n = n->parentNode()) {
 846         if (n == other)
 847             return true;
 848     }
 849     return false;
 850 }
 851
 852 bool Node::childAllowed(Node* newChild)
 853 {
 854     return childTypeAllowed(newChild->nodeType());
 855 }
 856
 857 void Node::attach()
 858 {
 859     ASSERT(!attached());
 860     ASSERT(!renderer() || (renderer()->style() && renderer()->parent()));
 861
 862     // If this node got a renderer it may be the previousRenderer() of sibling text nodes and thus affect the
 863     // result of Text::rendererIsNeeded() for those nodes.
 864     if (renderer()) {
 865         for (Node* next = nextSibling(); next; next = next->nextSibling()) {
 866             if (next->renderer())
 867                 break;
 868             if (!next->attached())
 869                 break;  // Assume this means none of the following siblings are attached.
 870             if (next->isTextNode())
 871                 next->createRendererIfNeeded();
 872         }
 873     }
 874
 875     m_attached = true;
 876 }
 877
 878 void Node::willRemove()
 879 {
 880 }
 881
 882 void Node::detach()
 883 {
 884     m_inDetach = true;
 885
 886     if (renderer())
 887         renderer()->destroy();
 888     setRenderer(0);
 889
 890     Document* doc = document();
 891     if (m_hovered)
 892         doc->hoveredNodeDetached(this);
 893     if (m_inActiveChain)
 894         doc->activeChainNodeDetached(this);
 895
 896     m_active = false;
 897     m_hovered = false;
 898     m_inActiveChain = false;
 899     m_attached = false;
 900     m_inDetach = false;
 901 }
 902
 903 void Node::insertedIntoDocument()
 904 {
 905     setInDocument(true);
 906     insertedIntoTree(false);
 907 }
 908
 909 void Node::removedFromDocument()
 910 {
 911     if (m_document && m_document->getCSSTarget() == this)
 912         m_document->setCSSTarget(0);
 913
 914     setInDocument(false);
 915     removedFromTree(false);
 916 }
 917
 918 Node *Node::previousEditable() const
 919 {
 920     Node *node = previousLeafNode();
 921     while (node) {
 922         if (node->isContentEditable())
 923             return node;
 924         node = node->previousLeafNode();
 925     }
 926     return 0;
 927 }
 928
 929 Node *Node::nextEditable() const
 930 {
 931     Node *node = nextLeafNode();
 932     while (node) {
 933         if (node->isContentEditable())
 934             return node;
 935         node = node->nextLeafNode();
 936     }
 937     return 0;
 938 }
 939
 940 RenderObject * Node::previousRenderer()
 941 {
 942     for (Node *n = previousSibling(); n; n = n->previousSibling()) {
 943         if (n->renderer())
 944             return n->renderer();
 945     }
 946     return 0;
 947 }
 948
 949 RenderObject * Node::nextRenderer()
 950 {
 951     // Avoid an O(n^2) problem with this function by not checking for nextRenderer() when the parent element hasn't even
 952     // been attached yet.
 953     if (parent() && !parent()->attached())
 954         return 0;
 955
 956     for (Node *n = nextSibling(); n; n = n->nextSibling()) {
 957         if (n->renderer())
 958             return n->renderer();
 959     }
 960     return 0;
 961 }
 962
 963 // FIXME: This code is used by editing.  Seems like it could move over there and not pollute Node.
 964 Node *Node::previousNodeConsideringAtomicNodes() const
 965 {
 966     if (previousSibling()) {
 967         Node *n = previousSibling();
 968         while (!isAtomicNode(n) && n->lastChild())
 969             n = n->lastChild();
 970         return n;
 971     }
 972     else if (parentNode()) {
 973         return parentNode();
 974     }
 975     else {
 976         return 0;
 977     }
 978 }
 979
 980 Node *Node::nextNodeConsideringAtomicNodes() const
 981 {
 982     if (!isAtomicNode(this) && firstChild())
 983         return firstChild();
 984     if (nextSibling())
 985         return nextSibling();
 986     const Node *n = this;
 987     while (n && !n->nextSibling())
 988         n = n->parentNode();
 989     if (n)
 990         return n->nextSibling();
 991     return 0;
 992 }
 993
 994 Node *Node::previousLeafNode() const
 995 {
 996     Node *node = previousNodeConsideringAtomicNodes();
 997     while (node) {
 998         if (isAtomicNode(node))
 999             return node;
1000         node = node->previousNodeConsideringAtomicNodes();
1001     }
1002     return 0;
1003 }
1004
1005 Node *Node::nextLeafNode() const
1006 {
1007     Node *node = nextNodeConsideringAtomicNodes();
1008     while (node) {
1009         if (isAtomicNode(node))
1010             return node;
1011         node = node->nextNodeConsideringAtomicNodes();
1012     }
1013     return 0;
1014 }
1015
1016 void Node::createRendererIfNeeded()
1017 {
1018     if (!document()->shouldCreateRenderers())
1019         return;
1020
1021     ASSERT(!renderer());
1022
1023     Node* parent = parentNode();
1024     ASSERT(parent);
1025
1026     RenderObject* parentRenderer = parent->renderer();
1027     if (parentRenderer && parentRenderer->canHaveChildren()
1028 #if ENABLE(SVG)
1029         && parent->childShouldCreateRenderer(this)
1030 #endif
1031         ) {
1032         RefPtr<RenderStyle> style = styleForRenderer();
1033         if (rendererIsNeeded(style.get())) {
1034             if (RenderObject* r = createRenderer(document()->renderArena(), style.get())) {
1035                 if (!parentRenderer->isChildAllowed(r, style.get()))
1036                     r->destroy();
1037                 else {
1038                     setRenderer(r);
1039                     renderer()->setAnimatableStyle(style.release());
1040                     parentRenderer->addChild(renderer(), nextRenderer());
1041                 }
1042             }
1043         }
1044     }
1045 }
1046
1047 PassRefPtr<RenderStyle> Node::styleForRenderer()
1048 {
1049     if (isElementNode())
1050         return document()->styleSelector()->styleForElement(static_cast<Element*>(this));
1051     return parentNode() && parentNode()->renderer() ? parentNode()->renderer()->style() : 0;
1052 }
1053
1054 bool Node::rendererIsNeeded(RenderStyle *style)
1055 {
1056     return (document()->documentElement() == this) || (style->display() != NONE);
1057 }
1058
1059 RenderObject *Node::createRenderer(RenderArena *arena, RenderStyle *style)
1060 {
1061     ASSERT(false);
1062     return 0;
1063 }
1064
1065 RenderStyle* Node::nonRendererRenderStyle() const
1066 {
1067     return 0;
1068 }
1069
1070 void Node::setRenderStyle(PassRefPtr<RenderStyle> s)
1071 {
1072     if (m_renderer)
1073         m_renderer->setAnimatableStyle(s);
1074 }
1075
1076 RenderStyle* Node::computedStyle()
1077 {
1078     return parent() ? parent()->computedStyle() : 0;
1079 }
1080
1081 int Node::maxCharacterOffset() const
1082 {
1083     ASSERT_NOT_REACHED();
1084     return 0;
1085 }
1086
1087 // FIXME: Shouldn't these functions be in the editing code?  Code that asks questions about HTML in the core DOM class
1088 // is obviously misplaced.
1089 bool Node::canStartSelection() const
1090 {
1091     if (isContentEditable())
1092         return true;
1093     return parent() ? parent()->canStartSelection() : true;
1094 }
1095
1096 Node* Node::shadowAncestorNode()
1097 {
1098 #if ENABLE(SVG)
1099     // SVG elements living in a shadow tree only occour when <use> created them.
1100     // For these cases we do NOT want to return the shadowParentNode() here
1101     // but the actual shadow tree element - as main difference to the HTML forms
1102     // shadow tree concept. (This function _could_ be made virtual - opinions?)
1103     if (isSVGElement())
1104         return this;
1105 #endif
1106
1107     Node* root = shadowTreeRootNode();
1108     if (root)
1109         return root->shadowParentNode();
1110     return this;
1111 }
1112
1113 Node* Node::shadowTreeRootNode()
1114 {
1115     Node* root = this;
1116     while (root) {
1117         if (root->isShadowNode())
1118             return root;
1119         root = root->parentNode();
1120     }
1121     return 0;
1122 }
1123
1124 bool Node::isInShadowTree()
1125 {
1126     for (Node* n = this; n; n = n->parentNode())
1127         if (n->isShadowNode())
1128             return true;
1129     return false;
1130 }
1131
1132 bool Node::isBlockFlow() const
1133 {
1134     return renderer() && renderer()->isBlockFlow();
1135 }
1136
1137 bool Node::isBlockFlowOrBlockTable() const
1138 {
1139     return renderer() && (renderer()->isBlockFlow() || renderer()->isTable() && !renderer()->isInline());
1140 }
1141
1142 bool Node::isEditableBlock() const
1143 {
1144     return isContentEditable() && isBlockFlow();
1145 }
1146
1147 Element *Node::enclosingBlockFlowElement() const
1148 {
1149     Node *n = const_cast<Node *>(this);
1150     if (isBlockFlow())
1151         return static_cast<Element *>(n);
1152
1153     while (1) {
1154         n = n->parentNode();
1155         if (!n)
1156             break;
1157         if (n->isBlockFlow() || n->hasTagName(bodyTag))
1158             return static_cast<Element *>(n);
1159     }
1160     return 0;
1161 }
1162
1163 Element *Node::enclosingInlineElement() const
1164 {
1165     Node *n = const_cast<Node *>(this);
1166     Node *p;
1167
1168     while (1) {
1169         p = n->parentNode();
1170         if (!p || p->isBlockFlow() || p->hasTagName(bodyTag))
1171             return static_cast<Element *>(n);
1172         // Also stop if any previous sibling is a block
1173         for (Node *sibling = n->previousSibling(); sibling; sibling = sibling->previousSibling()) {
1174             if (sibling->isBlockFlow())
1175                 return static_cast<Element *>(n);
1176         }
1177         n = p;
1178     }
1179     ASSERT_NOT_REACHED();
1180     return 0;
1181 }
1182
1183 Element* Node::rootEditableElement() const
1184 {
1185     Element* result = 0;
1186     for (Node* n = const_cast<Node*>(this); n && n->isContentEditable(); n = n->parentNode()) {
1187         if (n->isElementNode())
1188             result = static_cast<Element*>(n);
1189         if (n->hasTagName(bodyTag))
1190             break;
1191     }
1192     return result;
1193 }
1194
1195 bool Node::inSameContainingBlockFlowElement(Node *n)
1196 {
1197     return n ? enclosingBlockFlowElement() == n->enclosingBlockFlowElement() : false;
1198 }
1199
1200 // FIXME: End of obviously misplaced HTML editing functions.  Try to move these out of Node.
1201
1202 PassRefPtr<NodeList> Node::getElementsByTagName(const String& name)
1203 {
1204     return getElementsByTagNameNS("*", name);
1205 }
1206
1207 PassRefPtr<NodeList> Node::getElementsByTagNameNS(const String& namespaceURI, const String& localName)
1208 {
1209     if (localName.isNull())
1210         return 0;
1211
1212     String name = localName;
1213     if (document()->isHTMLDocument())
1214         name = localName.lower();
1215     return TagNodeList::create(this, namespaceURI.isEmpty() ? nullAtom : AtomicString(namespaceURI), name);
1216 }
1217
1218 PassRefPtr<NodeList> Node::getElementsByName(const String& elementName)
1219 {
1220     NodeRareData* data = ensureRareData();
1221     if (!data->nodeLists()) {
1222         data->setNodeLists(std::auto_ptr<NodeListsNodeData>(new NodeListsNodeData));
1223         document()->addNodeListCache();
1224     }
1225
1226     pair<NodeListsNodeData::CacheMap::iterator, bool> result = data->nodeLists()->m_nameNodeListCaches.add(elementName, 0);
1227     if (result.second)
1228         result.first->second = new DynamicNodeList::Caches;
1229
1230     return NameNodeList::create(this, elementName, result.first->second);
1231 }
1232
1233 PassRefPtr<NodeList> Node::getElementsByClassName(const String& classNames)
1234 {
1235     NodeRareData* data = ensureRareData();
1236     if (!data->nodeLists()) {
1237         data->setNodeLists(std::auto_ptr<NodeListsNodeData>(new NodeListsNodeData));
1238         document()->addNodeListCache();
1239     }
1240
1241     pair<NodeListsNodeData::CacheMap::iterator, bool> result = data->nodeLists()->m_classNodeListCaches.add(classNames, 0);
1242     if (result.second)
1243         result.first->second = new DynamicNodeList::Caches;
1244
1245     return ClassNodeList::create(this, classNames, result.first->second);
1246 }
1247
1248 template <typename Functor>
1249 static bool forEachTagSelector(Functor& functor, CSSSelector* selector)
1250 {
1251     ASSERT(selector);
1252
1253     do {
1254         if (functor(selector))
1255             return true;
1256         if (CSSSelector* simpleSelector = selector->m_simpleSelector) {
1257             if (forEachTagSelector(functor, simpleSelector))
1258                 return true;
1259         }
1260     } while ((selector = selector->m_tagHistory));
1261
1262     return false;
1263 }
1264
1265 template <typename Functor>
1266 static bool forEachSelector(Functor& functor, CSSSelector* selector)
1267 {
1268     for (; selector; selector = selector->next()) {
1269         if (forEachTagSelector(functor, selector))
1270             return true;
1271     }
1272
1273     return false;
1274 }
1275
1276 class SelectorNeedsNamespaceResolutionFunctor {
1277 public:
1278     bool operator()(CSSSelector* selector)
1279     {
1280         if (selector->hasTag() && selector->m_tag.prefix() != nullAtom && selector->m_tag.prefix() != starAtom)
1281             return true;
1282         if (selector->hasAttribute() && selector->m_attr.prefix() != nullAtom && selector->m_attr.prefix() != starAtom)
1283             return true;
1284         return false;
1285     }
1286 };
1287
1288 static bool selectorNeedsNamespaceResolution(CSSSelector* currentSelector)
1289 {
1290     SelectorNeedsNamespaceResolutionFunctor functor;
1291     return forEachSelector(functor, currentSelector);
1292 }
1293
1294 PassRefPtr<Element> Node::querySelector(const String& selectors, ExceptionCode& ec)
1295 {
1296     if (selectors.isEmpty()) {
1297         ec = SYNTAX_ERR;
1298         return 0;
1299     }
1300     bool strictParsing = !document()->inCompatMode();
1301     CSSParser p(strictParsing);
1302
1303     std::auto_ptr<CSSSelector> querySelector = p.parseSelector(selectors, document());
1304     if (!querySelector.get()) {
1305         ec = SYNTAX_ERR;
1306         return 0;
1307     }
1308
1309     // throw a NAMESPACE_ERR if the selector includes any namespace prefixes.
1310     if (selectorNeedsNamespaceResolution(querySelector.get())) {
1311         ec = NAMESPACE_ERR;
1312         return 0;
1313     }
1314
1315     CSSStyleSelector::SelectorChecker selectorChecker(document(), strictParsing);
1316
1317     // FIXME: we could also optimize for the the [id="foo"] case
1318     if (strictParsing && querySelector->m_match == CSSSelector::Id && inDocument() && !querySelector->next()) {
1319         ASSERT(querySelector->m_attr == idAttr);
1320         Element* element = document()->getElementById(querySelector->m_value);
1321         if (element && (isDocumentNode() || element->isDescendantOf(this)) && selectorChecker.checkSelector(querySelector.get(), element))
1322             return element;
1323         return 0;
1324     }
1325
1326     // FIXME: We can speed this up by implementing caching similar to the one use by getElementById
1327     for (Node* n = firstChild(); n; n = n->traverseNextNode(this)) {
1328         if (n->isElementNode()) {
1329             Element* element = static_cast<Element*>(n);
1330             for (CSSSelector* selector = querySelector.get(); selector; selector = selector->next()) {
1331                 if (selectorChecker.checkSelector(selector, element))
1332                     return element;
1333             }
1334         }
1335     }
1336
1337     return 0;
1338 }
1339
1340 PassRefPtr<NodeList> Node::querySelectorAll(const String& selectors, ExceptionCode& ec)
1341 {
1342     if (selectors.isEmpty()) {
1343         ec = SYNTAX_ERR;
1344         return 0;
1345     }
1346     bool strictParsing = !document()->inCompatMode();
1347     CSSParser p(strictParsing);
1348
1349     std::auto_ptr<CSSSelector> querySelector = p.parseSelector(selectors, document());
1350
1351     if (!querySelector.get()) {
1352         ec = SYNTAX_ERR;
1353         return 0;
1354     }
1355
1356     // Throw a NAMESPACE_ERR if the selector includes any namespace prefixes.
1357     if (selectorNeedsNamespaceResolution(querySelector.get())) {
1358         ec = NAMESPACE_ERR;
1359         return 0;
1360     }
1361
1362     return createSelectorNodeList(this, querySelector.get());
1363 }
1364
1365 Document *Node::ownerDocument() const
1366 {
1367     Document *doc = document();
1368     return doc == this ? 0 : doc;
1369 }
1370
1371 KURL Node::baseURI() const
1372 {
1373     return parentNode() ? parentNode()->baseURI() : KURL();
1374 }
1375
1376 bool Node::isEqualNode(Node *other) const
1377 {
1378     if (!other)
1379         return false;
1380
1381     if (nodeType() != other->nodeType())
1382         return false;
1383
1384     if (nodeName() != other->nodeName())
1385         return false;
1386
1387     if (localName() != other->localName())
1388         return false;
1389
1390     if (namespaceURI() != other->namespaceURI())
1391         return false;
1392
1393     if (prefix() != other->prefix())
1394         return false;
1395
1396     if (nodeValue() != other->nodeValue())
1397         return false;
1398
1399     NamedAttrMap *attrs = attributes();
1400     NamedAttrMap *otherAttrs = other->attributes();
1401
1402     if (!attrs && otherAttrs)
1403         return false;
1404
1405     if (attrs && !attrs->mapsEquivalent(otherAttrs))
1406         return false;
1407
1408     Node *child = firstChild();
1409     Node *otherChild = other->firstChild();
1410
1411     while (child) {
1412         if (!child->isEqualNode(otherChild))
1413             return false;
1414
1415         child = child->nextSibling();
1416         otherChild = otherChild->nextSibling();
1417     }
1418
1419     if (otherChild)
1420         return false;
1421
1422     // FIXME: For DocumentType nodes we should check equality on
1423     // the entities and notations NamedNodeMaps as well.
1424
1425     return true;
1426 }
1427
1428 bool Node::isDefaultNamespace(const String &namespaceURI) const
1429 {
1430     // Implemented according to
1431     // http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/namespaces-algorithms.html#isDefaultNamespaceAlgo
1432
1433     switch (nodeType()) {
1434         case ELEMENT_NODE: {
1435             const Element *elem = static_cast<const Element *>(this);
1436
1437             if (elem->prefix().isNull())
1438                 return elem->namespaceURI() == namespaceURI;
1439
1440             if (elem->hasAttributes()) {
1441                 NamedAttrMap *attrs = elem->attributes();
1442
1443                 for (unsigned i = 0; i < attrs->length(); i++) {
1444                     Attribute *attr = attrs->attributeItem(i);
1445
1446                     if (attr->localName() == "xmlns")
1447                         return attr->value() == namespaceURI;
1448                 }
1449             }
1450
1451             if (Element* ancestor = ancestorElement())
1452                 return ancestor->isDefaultNamespace(namespaceURI);
1453
1454             return false;
1455         }
1456         case DOCUMENT_NODE:
1457             if (Element* de = static_cast<const Document*>(this)->documentElement())
1458                 return de->isDefaultNamespace(namespaceURI);
1459             return false;
1460         case ENTITY_NODE:
1461         case NOTATION_NODE:
1462         case DOCUMENT_TYPE_NODE:
1463         case DOCUMENT_FRAGMENT_NODE:
1464             return false;
1465         case ATTRIBUTE_NODE: {
1466             const Attr *attr = static_cast<const Attr *>(this);
1467             if (attr->ownerElement())
1468                 return attr->ownerElement()->isDefaultNamespace(namespaceURI);
1469             return false;
1470         }
1471         default:
1472             if (Element* ancestor = ancestorElement())
1473                 return ancestor->isDefaultNamespace(namespaceURI);
1474             return false;
1475     }
1476 }
1477
1478 String Node::lookupPrefix(const String &namespaceURI) const
1479 {
1480     // Implemented according to
1481     // http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/namespaces-algorithms.html#lookupNamespacePrefixAlgo
1482
1483     if (namespaceURI.isEmpty())
1484         return String();
1485
1486     switch (nodeType()) {
1487         case ELEMENT_NODE:
1488             return lookupNamespacePrefix(namespaceURI, static_cast<const Element *>(this));
1489         case DOCUMENT_NODE:
1490             if (Element* de = static_cast<const Document*>(this)->documentElement())
1491                 return de->lookupPrefix(namespaceURI);
1492             return String();
1493         case ENTITY_NODE:
1494         case NOTATION_NODE:
1495         case DOCUMENT_FRAGMENT_NODE:
1496         case DOCUMENT_TYPE_NODE:
1497             return String();
1498         case ATTRIBUTE_NODE: {
1499             const Attr *attr = static_cast<const Attr *>(this);
1500             if (attr->ownerElement())
1501                 return attr->ownerElement()->lookupPrefix(namespaceURI);
1502             return String();
1503         }
1504         default:
1505             if (Element* ancestor = ancestorElement())
1506                 return ancestor->lookupPrefix(namespaceURI);
1507             return String();
1508     }
1509 }
1510
1511 String Node::lookupNamespaceURI(const String &prefix) const
1512 {
1513     // Implemented according to
1514     // http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/namespaces-algorithms.html#lookupNamespaceURIAlgo
1515
1516     if (!prefix.isNull() && prefix.isEmpty())
1517         return String();
1518
1519     switch (nodeType()) {
1520         case ELEMENT_NODE: {
1521             const Element *elem = static_cast<const Element *>(this);
1522
1523             if (!elem->namespaceURI().isNull() && elem->prefix() == prefix)
1524                 return elem->namespaceURI();
1525
1526             if (elem->hasAttributes()) {
1527                 NamedAttrMap *attrs = elem->attributes();
1528
1529                 for (unsigned i = 0; i < attrs->length(); i++) {
1530                     Attribute *attr = attrs->attributeItem(i);
1531
1532                     if (attr->prefix() == "xmlns" && attr->localName() == prefix) {
1533                         if (!attr->value().isEmpty())
1534                             return attr->value();
1535
1536                         return String();
1537                     } else if (attr->localName() == "xmlns" && prefix.isNull()) {
1538                         if (!attr->value().isEmpty())
1539                             return attr->value();
1540
1541                         return String();
1542                     }
1543                 }
1544             }
1545             if (Element* ancestor = ancestorElement())
1546                 return ancestor->lookupNamespaceURI(prefix);
1547             return String();
1548         }
1549         case DOCUMENT_NODE:
1550             if (Element* de = static_cast<const Document*>(this)->documentElement())
1551                 return de->lookupNamespaceURI(prefix);
1552             return String();
1553         case ENTITY_NODE:
1554         case NOTATION_NODE:
1555         case DOCUMENT_TYPE_NODE:
1556         case DOCUMENT_FRAGMENT_NODE:
1557             return String();
1558         case ATTRIBUTE_NODE: {
1559             const Attr *attr = static_cast<const Attr *>(this);
1560
1561             if (attr->ownerElement())
1562                 return attr->ownerElement()->lookupNamespaceURI(prefix);
1563             else
1564                 return String();
1565         }
1566         default:
1567             if (Element* ancestor = ancestorElement())
1568                 return ancestor->lookupNamespaceURI(prefix);
1569             return String();
1570     }
1571 }
1572
1573 String Node::lookupNamespacePrefix(const String &_namespaceURI, const Element *originalElement) const
1574 {
1575     if (_namespaceURI.isNull())
1576         return String();
1577
1578     if (originalElement->lookupNamespaceURI(prefix()) == _namespaceURI)
1579         return prefix();
1580
1581     if (hasAttributes()) {
1582         NamedAttrMap *attrs = attributes();
1583
1584         for (unsigned i = 0; i < attrs->length(); i++) {
1585             Attribute *attr = attrs->attributeItem(i);
1586
1587             if (attr->prefix() == "xmlns" &&
1588                 attr->value() == _namespaceURI &&
1589                 originalElement->lookupNamespaceURI(attr->localName()) == _namespaceURI)
1590                 return attr->localName();
1591         }
1592     }
1593
1594     if (Element* ancestor = ancestorElement())
1595         return ancestor->lookupNamespacePrefix(_namespaceURI, originalElement);
1596     return String();
1597 }
1598
1599 void Node::appendTextContent(bool convertBRsToNewlines, StringBuilder& content) const
1600 {
1601     switch (nodeType()) {
1602         case TEXT_NODE:
1603         case CDATA_SECTION_NODE:
1604         case COMMENT_NODE:
1605             content.append(static_cast<const CharacterData*>(this)->CharacterData::nodeValue());
1606             break;
1607
1608         case PROCESSING_INSTRUCTION_NODE:
1609             content.append(static_cast<const ProcessingInstruction*>(this)->ProcessingInstruction::nodeValue());
1610             break;
1611
1612         case ELEMENT_NODE:
1613             if (hasTagName(brTag) && convertBRsToNewlines) {
1614                 content.append('\n');
1615                 break;
1616         }
1617         // Fall through.
1618         case ATTRIBUTE_NODE:
1619         case ENTITY_NODE:
1620         case ENTITY_REFERENCE_NODE:
1621         case DOCUMENT_FRAGMENT_NODE:
1622             content.setNonNull();
1623
1624             for (Node *child = firstChild(); child; child = child->nextSibling()) {
1625                 if (child->nodeType() == COMMENT_NODE || child->nodeType() == PROCESSING_INSTRUCTION_NODE)
1626                     continue;
1627
1628                 child->appendTextContent(convertBRsToNewlines, content);
1629             }
1630             break;
1631
1632         case DOCUMENT_NODE:
1633         case DOCUMENT_TYPE_NODE:
1634         case NOTATION_NODE:
1635         case XPATH_NAMESPACE_NODE:
1636             break;
1637     }
1638 }
1639
1640 String Node::textContent(bool convertBRsToNewlines) const
1641 {
1642     StringBuilder content;
1643     appendTextContent(convertBRsToNewlines, content);
1644     return content.toString();
1645 }
1646
1647 void Node::setTextContent(const String &text, ExceptionCode& ec)
1648 {
1649     switch (nodeType()) {
1650         case TEXT_NODE:
1651         case CDATA_SECTION_NODE:
1652         case COMMENT_NODE:
1653         case PROCESSING_INSTRUCTION_NODE:
1654             setNodeValue(text, ec);
1655             break;
1656         case ELEMENT_NODE:
1657         case ATTRIBUTE_NODE:
1658         case ENTITY_NODE:
1659         case ENTITY_REFERENCE_NODE:
1660         case DOCUMENT_FRAGMENT_NODE: {
1661             ContainerNode *container = static_cast<ContainerNode *>(this);
1662
1663             container->removeChildren();
1664
1665             if (!text.isEmpty())
1666                 appendChild(document()->createTextNode(text), ec);
1667             break;
1668         }
1669         case DOCUMENT_NODE:
1670         case DOCUMENT_TYPE_NODE:
1671         case NOTATION_NODE:
1672         default:
1673             // Do nothing
1674             break;
1675     }
1676 }
1677
1678 Element* Node::ancestorElement() const
1679 {
1680     // In theory, there can be EntityReference nodes between elements, but this is currently not supported.
1681     for (Node* n = parentNode(); n; n = n->parentNode()) {
1682         if (n->isElementNode())
1683             return static_cast<Element*>(n);
1684     }
1685     return 0;
1686 }
1687
1688 bool Node::offsetInCharacters() const
1689 {
1690     return false;
1691 }
1692
1693 unsigned short Node::compareDocumentPosition(Node* otherNode)
1694 {
1695     // It is not clear what should be done if |otherNode| is 0.
1696     if (!otherNode)
1697         return DOCUMENT_POSITION_DISCONNECTED;
1698
1699     if (otherNode == this)
1700         return DOCUMENT_POSITION_EQUIVALENT;
1701
1702     Attr* attr1 = nodeType() == ATTRIBUTE_NODE ? static_cast<Attr*>(this) : 0;
1703     Attr* attr2 = otherNode->nodeType() == ATTRIBUTE_NODE ? static_cast<Attr*>(otherNode) : 0;
1704
1705     Node* start1 = attr1 ? attr1->ownerElement() : this;
1706     Node* start2 = attr2 ? attr2->ownerElement() : otherNode;
1707
1708     // If either of start1 or start2 is null, then we are disconnected, since one of the nodes is
1709     // an orphaned attribute node.
1710     if (!start1 || !start2)
1711         return DOCUMENT_POSITION_DISCONNECTED | DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC;
1712
1713     Vector<Node*, 16> chain1;
1714     Vector<Node*, 16> chain2;
1715     if (attr1)
1716         chain1.append(attr1);
1717     if (attr2)
1718         chain2.append(attr2);
1719
1720     if (attr1 && attr2 && start1 == start2 && start1) {
1721         // We are comparing two attributes on the same node.  Crawl our attribute map
1722         // and see which one we hit first.
1723         NamedAttrMap* map = attr1->ownerElement()->attributes(true);
1724         unsigned length = map->length();
1725         for (unsigned i = 0; i < length; ++i) {
1726             // If neither of the two determining nodes is a child node and nodeType is the same for both determining nodes, then an
1727             // implementation-dependent order between the determining nodes is returned. This order is stable as long as no nodes of
1728             // the same nodeType are inserted into or removed from the direct container. This would be the case, for example,
1729             // when comparing two attributes of the same element, and inserting or removing additional attributes might change
1730             // the order between existing attributes.
1731             Attribute* attr = map->attributeItem(i);
1732             if (attr1->attr() == attr)
1733                 return DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | DOCUMENT_POSITION_FOLLOWING;
1734             if (attr2->attr() == attr)
1735                 return DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | DOCUMENT_POSITION_PRECEDING;
1736         }
1737
1738         ASSERT_NOT_REACHED();
1739         return DOCUMENT_POSITION_DISCONNECTED;
1740     }
1741
1742     // If one node is in the document and the other is not, we must be disconnected.
1743     // If the nodes have different owning documents, they must be disconnected.  Note that we avoid
1744     // comparing Attr nodes here, since they return false from inDocument() all the time (which seems like a bug).
1745     if (start1->inDocument() != start2->inDocument() ||
1746         start1->document() != start2->document())
1747         return DOCUMENT_POSITION_DISCONNECTED | DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC;
1748
1749     // We need to find a common ancestor container, and then compare the indices of the two immediate children.
1750     Node* current;
1751     for (current = start1; current; current = current->parentNode())
1752         chain1.append(current);
1753     for (current = start2; current; current = current->parentNode())
1754         chain2.append(current);
1755
1756     // Walk the two chains backwards and look for the first difference.
1757     unsigned index1 = chain1.size();
1758     unsigned index2 = chain2.size();
1759     for (unsigned i = std::min(index1, index2); i; --i) {
1760         Node* child1 = chain1[--index1];
1761         Node* child2 = chain2[--index2];
1762         if (child1 != child2) {
1763             // If one of the children is an attribute, it wins.
1764             if (child1->nodeType() == ATTRIBUTE_NODE)
1765                 return DOCUMENT_POSITION_FOLLOWING;
1766             if (child2->nodeType() == ATTRIBUTE_NODE)
1767                 return DOCUMENT_POSITION_PRECEDING;
1768
1769             if (!child2->nextSibling())
1770                 return DOCUMENT_POSITION_FOLLOWING;
1771             if (!child1->nextSibling())
1772                 return DOCUMENT_POSITION_PRECEDING;
1773
1774             // Otherwise we need to see which node occurs first.  Crawl backwards from child2 looking for child1.
1775             for (Node* child = child2->previousSibling(); child; child = child->previousSibling()) {
1776                 if (child == child1)
1777                     return DOCUMENT_POSITION_FOLLOWING;
1778             }
1779             return DOCUMENT_POSITION_PRECEDING;
1780         }
1781     }
1782
1783     // There was no difference between the two parent chains, i.e., one was a subset of the other.  The shorter
1784     // chain is the ancestor.
1785     return index1 < index2 ?
1786                DOCUMENT_POSITION_FOLLOWING | DOCUMENT_POSITION_CONTAINED_BY :
1787                DOCUMENT_POSITION_PRECEDING | DOCUMENT_POSITION_CONTAINS;
1788 }
1789
1790 #ifndef NDEBUG
1791
1792 static void appendAttributeDesc(const Node* node, String& string, const QualifiedName& name, const char* attrDesc)
1793 {
1794     if (node->isElementNode()) {
1795         String attr = static_cast<const Element*>(node)->getAttribute(name);
1796         if (!attr.isEmpty()) {
1797             string += attrDesc;
1798             string += attr;
1799         }
1800     }
1801 }
1802
1803 void Node::showNode(const char* prefix) const
1804 {
1805     if (!prefix)
1806         prefix = "";
1807     if (isTextNode()) {
1808         String value = nodeValue();
1809         value.replace('\\', "\\\\");
1810         value.replace('\n', "\\n");
1811         fprintf(stderr, "%s%s\t%p \"%s\"\n", prefix, nodeName().utf8().data(), this, value.utf8().data());
1812     } else {
1813         String attrs = "";
1814         appendAttributeDesc(this, attrs, classAttr, " CLASS=");
1815         appendAttributeDesc(this, attrs, styleAttr, " STYLE=");
1816         fprintf(stderr, "%s%s\t%p%s\n", prefix, nodeName().utf8().data(), this, attrs.utf8().data());
1817     }
1818 }
1819
1820 void Node::showTreeForThis() const
1821 {
1822     showTreeAndMark(this, "*");
1823 }
1824
1825 void Node::showTreeAndMark(const Node* markedNode1, const char* markedLabel1, const Node* markedNode2, const char * markedLabel2) const
1826 {
1827     const Node* rootNode;
1828     const Node* node = this;
1829     while (node->parentNode() && !node->hasTagName(bodyTag))
1830         node = node->parentNode();
1831     rootNode = node;
1832
1833     for (node = rootNode; node; node = node->traverseNextNode()) {
1834         if (node == markedNode1)
1835             fprintf(stderr, "%s", markedLabel1);
1836         if (node == markedNode2)
1837             fprintf(stderr, "%s", markedLabel2);
1838
1839         for (const Node* tmpNode = node; tmpNode && tmpNode != rootNode; tmpNode = tmpNode->parentNode())
1840             fprintf(stderr, "\t");
1841         node->showNode();
1842     }
1843 }
1844
1845 void Node::formatForDebugger(char* buffer, unsigned length) const
1846 {
1847     String result;
1848     String s;
1849
1850     s = nodeName();
1851     if (s.length() == 0)
1852         result += "<none>";
1853     else
1854         result += s;
1855
1856     strncpy(buffer, result.utf8().data(), length - 1);
1857 }
1858
1859 #endif
1860
1861 // --------
1862
1863 void NodeListsNodeData::invalidateCaches()
1864 {
1865     m_childNodeListCaches.reset();
1866     invalidateCachesThatDependOnAttributes();
1867 }
1868
1869 void NodeListsNodeData::invalidateCachesThatDependOnAttributes()
1870 {
1871     CacheMap::iterator classCachesEnd = m_classNodeListCaches.end();
1872     for (CacheMap::iterator it = m_classNodeListCaches.begin(); it != classCachesEnd; ++it)
1873         it->second->reset();
1874
1875     CacheMap::iterator nameCachesEnd = m_nameNodeListCaches.end();
1876     for (CacheMap::iterator it = m_nameNodeListCaches.begin(); it != nameCachesEnd; ++it)
1877         it->second->reset();
1878 }
1879
1880 bool NodeListsNodeData::isEmpty() const
1881 {
1882     if (!m_listsWithCaches.isEmpty())
1883         return false;
1884
1885     if (m_childNodeListCaches.refCount)
1886         return false;
1887
1888     CacheMap::const_iterator classCachesEnd = m_classNodeListCaches.end();
1889     for (CacheMap::const_iterator it = m_classNodeListCaches.begin(); it != classCachesEnd; ++it) {
1890         if (it->second->refCount)
1891             return false;
1892     }
1893
1894     CacheMap::const_iterator nameCachesEnd = m_nameNodeListCaches.end();
1895     for (CacheMap::const_iterator it = m_nameNodeListCaches.begin(); it != nameCachesEnd; ++it) {
1896         if (it->second->refCount)
1897             return false;
1898     }
1899
1900     return true;
1901 }
1902
1903 void Node::getSubresourceURLs(Vector<KURL>& urls) const
1904 {
1905     Vector<String> subresourceStrings;
1906     getSubresourceAttributeStrings(subresourceStrings);
1907
1908     for (unsigned i = 0; i < subresourceStrings.size(); ++i) {
1909         String& subresourceString(subresourceStrings[i]);
1910
1911         // FIXME: Is parseURL appropriate here?
1912         if (subresourceString.length())
1913             urls.append(document()->completeURL(parseURL(subresourceString)));
1914     }
1915 }
1916
1917 // --------
1918
1919 } // namespace WebCore
1920
1921 #ifndef NDEBUG
1922
1923 void showTree(const WebCore::Node* node)
1924 {
1925     if (node)
1926         node->showTreeForThis();
1927 }
1928
1929 #endif