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