505c7c6bb4ceeeb6bc03f82ac19fdc0adbd322ed
[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::isInShadowTree()
1108 {
1109     for (Node* n = this; n; n = n->parentNode())
1110         if (n->isShadowNode())
1111             return true;
1112     return false;
1113 }
1114
1115 bool Node::isBlockFlow() const
1116 {
1117     return renderer() && renderer()->isBlockFlow();
1118 }
1119
1120 bool Node::isBlockFlowOrBlockTable() const
1121 {
1122     return renderer() && (renderer()->isBlockFlow() || renderer()->isTable() && !renderer()->isInline());
1123 }
1124
1125 bool Node::isEditableBlock() const
1126 {
1127     return isContentEditable() && isBlockFlow();
1128 }
1129
1130 Element *Node::enclosingBlockFlowElement() const
1131 {
1132     Node *n = const_cast<Node *>(this);
1133     if (isBlockFlow())
1134         return static_cast<Element *>(n);
1135
1136     while (1) {
1137         n = n->parentNode();
1138         if (!n)
1139             break;
1140         if (n->isBlockFlow() || n->hasTagName(bodyTag))
1141             return static_cast<Element *>(n);
1142     }
1143     return 0;
1144 }
1145
1146 Element *Node::enclosingInlineElement() const
1147 {
1148     Node *n = const_cast<Node *>(this);
1149     Node *p;
1150
1151     while (1) {
1152         p = n->parentNode();
1153         if (!p || p->isBlockFlow() || p->hasTagName(bodyTag))
1154             return static_cast<Element *>(n);
1155         // Also stop if any previous sibling is a block
1156         for (Node *sibling = n->previousSibling(); sibling; sibling = sibling->previousSibling()) {
1157             if (sibling->isBlockFlow())
1158                 return static_cast<Element *>(n);
1159         }
1160         n = p;
1161     }
1162     ASSERT_NOT_REACHED();
1163     return 0;
1164 }
1165
1166 Element* Node::rootEditableElement() const
1167 {
1168     Element* result = 0;
1169     for (Node* n = const_cast<Node*>(this); n && n->isContentEditable(); n = n->parentNode()) {
1170         if (n->isElementNode())
1171             result = static_cast<Element*>(n);
1172         if (n->hasTagName(bodyTag))
1173             break;
1174     }
1175     return result;
1176 }
1177
1178 bool Node::inSameContainingBlockFlowElement(Node *n)
1179 {
1180     return n ? enclosingBlockFlowElement() == n->enclosingBlockFlowElement() : false;
1181 }
1182
1183 // FIXME: End of obviously misplaced HTML editing functions.  Try to move these out of Node.
1184
1185 PassRefPtr<NodeList> Node::getElementsByTagName(const String& name)
1186 {
1187     return getElementsByTagNameNS("*", name);
1188 }
1189  
1190 PassRefPtr<NodeList> Node::getElementsByTagNameNS(const String& namespaceURI, const String& localName)
1191 {
1192     if (localName.isNull())
1193         return 0;
1194
1195     String name = localName;
1196     if (document()->isHTMLDocument())
1197         name = localName.lower();
1198     return TagNodeList::create(this, namespaceURI.isEmpty() ? nullAtom : AtomicString(namespaceURI), name);
1199 }
1200
1201 PassRefPtr<NodeList> Node::getElementsByName(const String& elementName)
1202 {
1203     if (!m_nodeLists) {
1204         m_nodeLists.set(new NodeListsNodeData);
1205         document()->addNodeListCache();
1206     }
1207
1208     pair<NodeListsNodeData::CacheMap::iterator, bool> result = m_nodeLists->m_nameNodeListCaches.add(elementName, 0);
1209     if (result.second)
1210         result.first->second = new DynamicNodeList::Caches;
1211     
1212     return NameNodeList::create(this, elementName, result.first->second);
1213 }
1214
1215 PassRefPtr<NodeList> Node::getElementsByClassName(const String& classNames)
1216 {
1217     if (!m_nodeLists) {
1218         m_nodeLists.set(new NodeListsNodeData);
1219         document()->addNodeListCache();
1220     }
1221
1222     pair<NodeListsNodeData::CacheMap::iterator, bool> result = m_nodeLists->m_classNodeListCaches.add(classNames, 0);
1223     if (result.second)
1224         result.first->second = new DynamicNodeList::Caches;
1225     
1226     return ClassNodeList::create(this, classNames, result.first->second);
1227 }
1228
1229 template <typename Functor>
1230 static bool forEachTagSelector(Functor& functor, CSSSelector* selector)
1231 {
1232     ASSERT(selector);
1233
1234     do {
1235         if (functor(selector))
1236             return true;
1237         if (CSSSelector* simpleSelector = selector->m_simpleSelector) {
1238             if (forEachTagSelector(functor, simpleSelector))
1239                 return true;
1240         }
1241     } while ((selector = selector->m_tagHistory));
1242
1243     return false;
1244 }
1245
1246 template <typename Functor>
1247 static bool forEachSelector(Functor& functor, CSSSelector* selector)
1248 {
1249     for (; selector; selector = selector->next()) {
1250         if (forEachTagSelector(functor, selector))
1251             return true;
1252     }
1253
1254     return false;
1255 }
1256
1257 class SelectorNeedsNamespaceResolutionFunctor {
1258 public:
1259     bool operator()(CSSSelector* selector)
1260     {
1261         if (selector->hasTag() && selector->m_tag.prefix() != nullAtom && selector->m_tag.prefix() != starAtom)
1262             return true;
1263         if (selector->hasAttribute() && selector->m_attr.prefix() != nullAtom && selector->m_attr.prefix() != starAtom)
1264             return true;
1265         return false;
1266     }
1267 };
1268
1269 class ResolveNamespaceFunctor {
1270 public:
1271     ResolveNamespaceFunctor(NSResolver* resolver, ExceptionCode& ec, KJS::ExecState* exec)
1272         : m_resolver(resolver)
1273         , m_exceptionCode(ec)
1274         , m_exec(exec)
1275     {
1276     }
1277
1278     bool operator()(CSSSelector* selector)
1279     {
1280         if (selector->hasTag() && selector->m_tag.prefix() != nullAtom && selector->m_tag.prefix() != starAtom) {
1281             String resolvedNamespaceURI = m_resolver->lookupNamespaceURI(m_exec, selector->m_tag.prefix());
1282             if (m_exec && m_exec->hadException())
1283                 return true;
1284             if (resolvedNamespaceURI.isEmpty()) {
1285                 m_exceptionCode = NAMESPACE_ERR;
1286                 return true;
1287             }
1288             QualifiedName newQualifiedName(selector->m_tag.prefix(), selector->m_tag.localName(), resolvedNamespaceURI);
1289             selector->m_tag = newQualifiedName;
1290         }
1291         if (selector->hasAttribute() && selector->m_attr.prefix() != nullAtom && selector->m_attr.prefix() != starAtom) {
1292             String resolvedNamespaceURI = m_resolver->lookupNamespaceURI(m_exec, selector->m_attr.prefix());
1293             if (m_exec && m_exec->hadException())
1294                 return true;
1295             if (resolvedNamespaceURI.isEmpty()) {
1296                 m_exceptionCode = NAMESPACE_ERR;
1297                 return true;
1298             }
1299             QualifiedName newQualifiedName(selector->m_attr.prefix(), selector->m_attr.localName(), resolvedNamespaceURI);
1300             selector->m_attr = newQualifiedName;
1301         }
1302
1303         return false;
1304     }
1305
1306 private:
1307     NSResolver* m_resolver;
1308     ExceptionCode& m_exceptionCode;
1309     KJS::ExecState* m_exec;
1310 };
1311
1312 static bool selectorNeedsNamespaceResolution(CSSSelector* currentSelector)
1313 {
1314     SelectorNeedsNamespaceResolutionFunctor functor;
1315     return forEachSelector(functor, currentSelector);
1316 }
1317
1318 static bool resolveNamespacesForSelector(CSSSelector* currentSelector, NSResolver* resolver, ExceptionCode& ec, KJS::ExecState* exec)
1319 {
1320     ResolveNamespaceFunctor functor(resolver, ec, exec);
1321     return forEachSelector(functor, currentSelector);
1322 }
1323
1324 PassRefPtr<Element> Node::querySelector(const String& selectors, ExceptionCode& ec)
1325 {
1326     return querySelector(selectors, 0, ec, execStateFromNode(this));
1327 }
1328
1329 PassRefPtr<NodeList> Node::querySelectorAll(const String& selectors, ExceptionCode& ec)
1330 {
1331     return querySelectorAll(selectors, 0, ec, execStateFromNode(this));
1332 }
1333
1334 PassRefPtr<Element> Node::querySelector(const String& selectors, NSResolver* resolver, ExceptionCode& ec, KJS::ExecState* exec)
1335 {
1336     if (selectors.isEmpty()) {
1337         ec = SYNTAX_ERR;
1338         return 0;
1339     }
1340     bool strictParsing = !document()->inCompatMode();
1341     CSSParser p(strictParsing);
1342     if (resolver) {
1343         String defaultNamespace = resolver->lookupNamespaceURI(exec, String());
1344         if (exec && exec->hadException())
1345             return 0;
1346         if (!defaultNamespace.isEmpty())
1347             p.m_defaultNamespace = defaultNamespace;
1348     }
1349
1350     std::auto_ptr<CSSSelector> querySelector = p.parseSelector(selectors);
1351     if (!querySelector.get()) {
1352         ec = SYNTAX_ERR;
1353         return 0;
1354     }
1355
1356     if (resolver) {
1357         if (resolveNamespacesForSelector(querySelector.get(), resolver, ec, exec))
1358             return 0;
1359     } else {
1360         // No NSResolver was passed, so throw a NAMESPACE_ERR if the selector includes any 
1361         // namespace prefixes.
1362         if (selectorNeedsNamespaceResolution(querySelector.get())) {
1363             ec = NAMESPACE_ERR;
1364             return 0;
1365         }
1366     }
1367
1368     // FIXME: we could also optimize for the the [id="foo"] case
1369     if (strictParsing && inDocument() && !querySelector->next() && querySelector->m_match == CSSSelector::Id
1370             && !querySelector->hasTag() && !querySelector->m_tagHistory && !querySelector->m_simpleSelector) {
1371         ASSERT(querySelector->m_attr == idAttr);
1372         Element* element = document()->getElementById(querySelector->m_value);
1373         if (element && (isDocumentNode() || element->isDescendantOf(this)))
1374             return element;
1375         return 0;
1376     }
1377
1378     CSSStyleSelector::SelectorChecker selectorChecker(document(), strictParsing);
1379
1380     // FIXME: We can speed this up by implementing caching similar to the one use by getElementById
1381     for (Node* n = firstChild(); n; n = n->traverseNextNode(this)) {
1382         if (n->isElementNode()) {
1383             Element* element = static_cast<Element*>(n);
1384             for (CSSSelector* selector = querySelector.get(); selector; selector = selector->next()) {
1385                 if (selectorChecker.checkSelector(selector, element))
1386                     return element;
1387             }
1388         }
1389     }
1390     
1391     return 0;
1392 }
1393
1394 PassRefPtr<NodeList> Node::querySelectorAll(const String& selectors, NSResolver* resolver, ExceptionCode& ec, KJS::ExecState* exec)
1395 {
1396     if (selectors.isEmpty()) {
1397         ec = SYNTAX_ERR;
1398         return 0;
1399     }
1400     bool strictParsing = !document()->inCompatMode();
1401     CSSParser p(strictParsing);
1402     if (resolver) {
1403         String defaultNamespace = resolver->lookupNamespaceURI(exec, String());
1404         if (exec && exec->hadException())
1405             return false;
1406         if (!defaultNamespace.isEmpty())
1407             p.m_defaultNamespace = defaultNamespace;
1408     }
1409
1410     std::auto_ptr<CSSSelector> querySelector = p.parseSelector(selectors);
1411
1412     if (!querySelector.get()) {
1413         ec = SYNTAX_ERR;
1414         return 0;
1415     }
1416
1417     if (resolver) {
1418         if (resolveNamespacesForSelector(querySelector.get(), resolver, ec, exec))
1419             return 0;
1420     } else {
1421         // No NSResolver was passed, so throw a NAMESPACE_ERR if the selector includes any 
1422         // namespace prefixes.
1423         if (selectorNeedsNamespaceResolution(querySelector.get())) {
1424             ec = NAMESPACE_ERR;
1425             return 0;
1426         }
1427     }
1428
1429     return createSelectorNodeList(this, querySelector.get());
1430 }
1431
1432 Document *Node::ownerDocument() const
1433 {
1434     Document *doc = document();
1435     return doc == this ? 0 : doc;
1436 }
1437
1438 bool Node::hasAttributes() const
1439 {
1440     return false;
1441 }
1442
1443 NamedAttrMap* Node::attributes() const
1444 {
1445     return 0;
1446 }
1447
1448 KURL Node::baseURI() const
1449 {
1450     return parentNode() ? parentNode()->baseURI() : KURL();
1451 }
1452
1453 bool Node::isEqualNode(Node *other) const
1454 {
1455     if (!other)
1456         return false;
1457     
1458     if (nodeType() != other->nodeType())
1459         return false;
1460     
1461     if (nodeName() != other->nodeName())
1462         return false;
1463     
1464     if (localName() != other->localName())
1465         return false;
1466     
1467     if (namespaceURI() != other->namespaceURI())
1468         return false;
1469     
1470     if (prefix() != other->prefix())
1471         return false;
1472     
1473     if (nodeValue() != other->nodeValue())
1474         return false;
1475     
1476     NamedAttrMap *attrs = attributes();
1477     NamedAttrMap *otherAttrs = other->attributes();
1478     
1479     if (!attrs && otherAttrs)
1480         return false;
1481     
1482     if (attrs && !attrs->mapsEquivalent(otherAttrs))
1483         return false;
1484     
1485     Node *child = firstChild();
1486     Node *otherChild = other->firstChild();
1487     
1488     while (child) {
1489         if (!child->isEqualNode(otherChild))
1490             return false;
1491         
1492         child = child->nextSibling();
1493         otherChild = otherChild->nextSibling();
1494     }
1495     
1496     if (otherChild)
1497         return false;
1498     
1499     // FIXME: For DocumentType nodes we should check equality on
1500     // the entities and notations NamedNodeMaps as well.
1501     
1502     return true;
1503 }
1504
1505 bool Node::isDefaultNamespace(const String &namespaceURI) const
1506 {
1507     // Implemented according to
1508     // http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/namespaces-algorithms.html#isDefaultNamespaceAlgo
1509     
1510     switch (nodeType()) {
1511         case ELEMENT_NODE: {
1512             const Element *elem = static_cast<const Element *>(this);
1513             
1514             if (elem->prefix().isNull())
1515                 return elem->namespaceURI() == namespaceURI;
1516
1517             if (elem->hasAttributes()) {
1518                 NamedAttrMap *attrs = elem->attributes();
1519                 
1520                 for (unsigned i = 0; i < attrs->length(); i++) {
1521                     Attribute *attr = attrs->attributeItem(i);
1522                     
1523                     if (attr->localName() == "xmlns")
1524                         return attr->value() == namespaceURI;
1525                 }
1526             }
1527
1528             if (Element* ancestor = ancestorElement())
1529                 return ancestor->isDefaultNamespace(namespaceURI);
1530
1531             return false;
1532         }
1533         case DOCUMENT_NODE:
1534             if (Element* de = static_cast<const Document*>(this)->documentElement())
1535                 return de->isDefaultNamespace(namespaceURI);
1536             return false;
1537         case ENTITY_NODE:
1538         case NOTATION_NODE:
1539         case DOCUMENT_TYPE_NODE:
1540         case DOCUMENT_FRAGMENT_NODE:
1541             return false;
1542         case ATTRIBUTE_NODE: {
1543             const Attr *attr = static_cast<const Attr *>(this);
1544             if (attr->ownerElement())
1545                 return attr->ownerElement()->isDefaultNamespace(namespaceURI);
1546             return false;
1547         }
1548         default:
1549             if (Element* ancestor = ancestorElement())
1550                 return ancestor->isDefaultNamespace(namespaceURI);
1551             return false;
1552     }
1553 }
1554
1555 String Node::lookupPrefix(const String &namespaceURI) const
1556 {
1557     // Implemented according to
1558     // http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/namespaces-algorithms.html#lookupNamespacePrefixAlgo
1559     
1560     if (namespaceURI.isEmpty())
1561         return String();
1562     
1563     switch (nodeType()) {
1564         case ELEMENT_NODE:
1565             return lookupNamespacePrefix(namespaceURI, static_cast<const Element *>(this));
1566         case DOCUMENT_NODE:
1567             if (Element* de = static_cast<const Document*>(this)->documentElement())
1568                 return de->lookupPrefix(namespaceURI);
1569             return String();
1570         case ENTITY_NODE:
1571         case NOTATION_NODE:
1572         case DOCUMENT_FRAGMENT_NODE:
1573         case DOCUMENT_TYPE_NODE:
1574             return String();
1575         case ATTRIBUTE_NODE: {
1576             const Attr *attr = static_cast<const Attr *>(this);
1577             if (attr->ownerElement())
1578                 return attr->ownerElement()->lookupPrefix(namespaceURI);
1579             return String();
1580         }
1581         default:
1582             if (Element* ancestor = ancestorElement())
1583                 return ancestor->lookupPrefix(namespaceURI);
1584             return String();
1585     }
1586 }
1587
1588 String Node::lookupNamespaceURI(const String &prefix) const
1589 {
1590     // Implemented according to
1591     // http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/namespaces-algorithms.html#lookupNamespaceURIAlgo
1592     
1593     if (!prefix.isNull() && prefix.isEmpty())
1594         return String();
1595     
1596     switch (nodeType()) {
1597         case ELEMENT_NODE: {
1598             const Element *elem = static_cast<const Element *>(this);
1599             
1600             if (!elem->namespaceURI().isNull() && elem->prefix() == prefix)
1601                 return elem->namespaceURI();
1602             
1603             if (elem->hasAttributes()) {
1604                 NamedAttrMap *attrs = elem->attributes();
1605                 
1606                 for (unsigned i = 0; i < attrs->length(); i++) {
1607                     Attribute *attr = attrs->attributeItem(i);
1608                     
1609                     if (attr->prefix() == "xmlns" && attr->localName() == prefix) {
1610                         if (!attr->value().isEmpty())
1611                             return attr->value();
1612                         
1613                         return String();
1614                     } else if (attr->localName() == "xmlns" && prefix.isNull()) {
1615                         if (!attr->value().isEmpty())
1616                             return attr->value();
1617                         
1618                         return String();
1619                     }
1620                 }
1621             }
1622             if (Element* ancestor = ancestorElement())
1623                 return ancestor->lookupNamespaceURI(prefix);
1624             return String();
1625         }
1626         case DOCUMENT_NODE:
1627             if (Element* de = static_cast<const Document*>(this)->documentElement())
1628                 return de->lookupNamespaceURI(prefix);
1629             return String();
1630         case ENTITY_NODE:
1631         case NOTATION_NODE:
1632         case DOCUMENT_TYPE_NODE:
1633         case DOCUMENT_FRAGMENT_NODE:
1634             return String();
1635         case ATTRIBUTE_NODE: {
1636             const Attr *attr = static_cast<const Attr *>(this);
1637             
1638             if (attr->ownerElement())
1639                 return attr->ownerElement()->lookupNamespaceURI(prefix);
1640             else
1641                 return String();
1642         }
1643         default:
1644             if (Element* ancestor = ancestorElement())
1645                 return ancestor->lookupNamespaceURI(prefix);
1646             return String();
1647     }
1648 }
1649
1650 String Node::lookupNamespacePrefix(const String &_namespaceURI, const Element *originalElement) const
1651 {
1652     if (_namespaceURI.isNull())
1653         return String();
1654             
1655     if (originalElement->lookupNamespaceURI(prefix()) == _namespaceURI)
1656         return prefix();
1657     
1658     if (hasAttributes()) {
1659         NamedAttrMap *attrs = attributes();
1660         
1661         for (unsigned i = 0; i < attrs->length(); i++) {
1662             Attribute *attr = attrs->attributeItem(i);
1663             
1664             if (attr->prefix() == "xmlns" &&
1665                 attr->value() == _namespaceURI &&
1666                 originalElement->lookupNamespaceURI(attr->localName()) == _namespaceURI)
1667                 return attr->localName();
1668         }
1669     }
1670     
1671     if (Element* ancestor = ancestorElement())
1672         return ancestor->lookupNamespacePrefix(_namespaceURI, originalElement);
1673     return String();
1674 }
1675
1676 void Node::appendTextContent(bool convertBRsToNewlines, StringBuilder& content) const
1677 {
1678     switch (nodeType()) {
1679         case TEXT_NODE:
1680         case CDATA_SECTION_NODE:
1681         case COMMENT_NODE:
1682             content.append(static_cast<const CharacterData*>(this)->CharacterData::nodeValue());
1683             break;
1684
1685         case PROCESSING_INSTRUCTION_NODE:
1686             content.append(static_cast<const ProcessingInstruction*>(this)->ProcessingInstruction::nodeValue());
1687             break;
1688         
1689         case ELEMENT_NODE:
1690             if (hasTagName(brTag) && convertBRsToNewlines) {
1691                 content.append('\n');
1692                 break;
1693         }
1694         // Fall through.
1695         case ATTRIBUTE_NODE:
1696         case ENTITY_NODE:
1697         case ENTITY_REFERENCE_NODE:
1698         case DOCUMENT_FRAGMENT_NODE:
1699             content.setNonNull();
1700
1701             for (Node *child = firstChild(); child; child = child->nextSibling()) {
1702                 if (child->nodeType() == COMMENT_NODE || child->nodeType() == PROCESSING_INSTRUCTION_NODE)
1703                     continue;
1704             
1705                 child->appendTextContent(convertBRsToNewlines, content);
1706             }
1707             break;
1708
1709         case DOCUMENT_NODE:
1710         case DOCUMENT_TYPE_NODE:
1711         case NOTATION_NODE:
1712         case XPATH_NAMESPACE_NODE:
1713             break;
1714     }
1715 }
1716
1717 String Node::textContent(bool convertBRsToNewlines) const
1718 {
1719     StringBuilder content;
1720     appendTextContent(convertBRsToNewlines, content);
1721     return content.toString();
1722 }
1723
1724 void Node::setTextContent(const String &text, ExceptionCode& ec)
1725 {           
1726     switch (nodeType()) {
1727         case TEXT_NODE:
1728         case CDATA_SECTION_NODE:
1729         case COMMENT_NODE:
1730         case PROCESSING_INSTRUCTION_NODE:
1731             setNodeValue(text, ec);
1732             break;
1733         case ELEMENT_NODE:
1734         case ATTRIBUTE_NODE:
1735         case ENTITY_NODE:
1736         case ENTITY_REFERENCE_NODE:
1737         case DOCUMENT_FRAGMENT_NODE: {
1738             ContainerNode *container = static_cast<ContainerNode *>(this);
1739             
1740             container->removeChildren();
1741             
1742             if (!text.isEmpty())
1743                 appendChild(document()->createTextNode(text), ec);
1744             break;
1745         }
1746         case DOCUMENT_NODE:
1747         case DOCUMENT_TYPE_NODE:
1748         case NOTATION_NODE:
1749         default:
1750             // Do nothing
1751             break;
1752     }
1753 }
1754
1755 Element* Node::ancestorElement() const
1756 {
1757     // In theory, there can be EntityReference nodes between elements, but this is currently not supported.
1758     for (Node* n = parentNode(); n; n = n->parentNode()) {
1759         if (n->isElementNode())
1760             return static_cast<Element*>(n);
1761     }
1762     return 0;
1763 }
1764
1765 bool Node::offsetInCharacters() const
1766 {
1767     return false;
1768 }
1769
1770 unsigned short Node::compareDocumentPosition(Node* otherNode)
1771 {
1772     // It is not clear what should be done if |otherNode| is 0.
1773     if (!otherNode)
1774         return DOCUMENT_POSITION_DISCONNECTED;
1775
1776     if (otherNode == this)
1777         return DOCUMENT_POSITION_EQUIVALENT;
1778     
1779     Attr* attr1 = nodeType() == ATTRIBUTE_NODE ? static_cast<Attr*>(this) : 0;
1780     Attr* attr2 = otherNode->nodeType() == ATTRIBUTE_NODE ? static_cast<Attr*>(otherNode) : 0;
1781     
1782     Node* start1 = attr1 ? attr1->ownerElement() : this;
1783     Node* start2 = attr2 ? attr2->ownerElement() : otherNode;
1784     
1785     // If either of start1 or start2 is null, then we are disconnected, since one of the nodes is
1786     // an orphaned attribute node.
1787     if (!start1 || !start2)
1788         return DOCUMENT_POSITION_DISCONNECTED | DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC;
1789
1790     Vector<Node*, 16> chain1;
1791     Vector<Node*, 16> chain2;
1792     if (attr1)
1793         chain1.append(attr1);
1794     if (attr2)
1795         chain2.append(attr2);
1796     
1797     if (attr1 && attr2 && start1 == start2 && start1) {
1798         // We are comparing two attributes on the same node.  Crawl our attribute map
1799         // and see which one we hit first.
1800         NamedAttrMap* map = attr1->ownerElement()->attributes(true);
1801         unsigned length = map->length();
1802         for (unsigned i = 0; i < length; ++i) {
1803             // If neither of the two determining nodes is a child node and nodeType is the same for both determining nodes, then an 
1804             // implementation-dependent order between the determining nodes is returned. This order is stable as long as no nodes of
1805             // the same nodeType are inserted into or removed from the direct container. This would be the case, for example, 
1806             // when comparing two attributes of the same element, and inserting or removing additional attributes might change 
1807             // the order between existing attributes.
1808             Attribute* attr = map->attributeItem(i);
1809             if (attr1->attr() == attr)
1810                 return DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | DOCUMENT_POSITION_FOLLOWING;
1811             if (attr2->attr() == attr)
1812                 return DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | DOCUMENT_POSITION_PRECEDING;
1813         }
1814         
1815         ASSERT_NOT_REACHED();
1816         return DOCUMENT_POSITION_DISCONNECTED;
1817     }
1818
1819     // If one node is in the document and the other is not, we must be disconnected.
1820     // If the nodes have different owning documents, they must be disconnected.  Note that we avoid
1821     // comparing Attr nodes here, since they return false from inDocument() all the time (which seems like a bug).
1822     if (start1->inDocument() != start2->inDocument() ||
1823         start1->document() != start2->document())
1824         return DOCUMENT_POSITION_DISCONNECTED | DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC;
1825
1826     // We need to find a common ancestor container, and then compare the indices of the two immediate children.
1827     Node* current;
1828     for (current = start1; current; current = current->parentNode())
1829         chain1.append(current);
1830     for (current = start2; current; current = current->parentNode())
1831         chain2.append(current);
1832    
1833     // Walk the two chains backwards and look for the first difference.
1834     unsigned index1 = chain1.size();
1835     unsigned index2 = chain2.size();
1836     for (unsigned i = std::min(index1, index2); i; --i) {
1837         Node* child1 = chain1[--index1];
1838         Node* child2 = chain2[--index2];
1839         if (child1 != child2) {
1840             // If one of the children is an attribute, it wins.
1841             if (child1->nodeType() == ATTRIBUTE_NODE)
1842                 return DOCUMENT_POSITION_FOLLOWING;
1843             if (child2->nodeType() == ATTRIBUTE_NODE)
1844                 return DOCUMENT_POSITION_PRECEDING;
1845             
1846             if (!child2->nextSibling())
1847                 return DOCUMENT_POSITION_FOLLOWING;
1848             if (!child1->nextSibling())
1849                 return DOCUMENT_POSITION_PRECEDING;
1850
1851             // Otherwise we need to see which node occurs first.  Crawl backwards from child2 looking for child1.
1852             for (Node* child = child2->previousSibling(); child; child = child->previousSibling()) {
1853                 if (child == child1)
1854                     return DOCUMENT_POSITION_FOLLOWING;
1855             }
1856             return DOCUMENT_POSITION_PRECEDING;
1857         }
1858     }
1859     
1860     // There was no difference between the two parent chains, i.e., one was a subset of the other.  The shorter
1861     // chain is the ancestor.
1862     return index1 < index2 ? 
1863                DOCUMENT_POSITION_FOLLOWING | DOCUMENT_POSITION_CONTAINED_BY :
1864                DOCUMENT_POSITION_PRECEDING | DOCUMENT_POSITION_CONTAINS;
1865 }
1866
1867 #ifndef NDEBUG
1868
1869 static void appendAttributeDesc(const Node* node, String& string, const QualifiedName& name, const char* attrDesc)
1870 {
1871     if (node->isElementNode()) {
1872         String attr = static_cast<const Element*>(node)->getAttribute(name);
1873         if (!attr.isEmpty()) {
1874             string += attrDesc;
1875             string += attr;
1876         }
1877     }
1878 }
1879
1880 void Node::showNode(const char* prefix) const
1881 {
1882     if (!prefix)
1883         prefix = "";
1884     if (isTextNode()) {
1885         String value = nodeValue();
1886         value.replace('\\', "\\\\");
1887         value.replace('\n', "\\n");
1888         fprintf(stderr, "%s%s\t%p \"%s\"\n", prefix, nodeName().utf8().data(), this, value.utf8().data());
1889     } else {
1890         String attrs = "";
1891         appendAttributeDesc(this, attrs, classAttr, " CLASS=");
1892         appendAttributeDesc(this, attrs, styleAttr, " STYLE=");
1893         fprintf(stderr, "%s%s\t%p%s\n", prefix, nodeName().utf8().data(), this, attrs.utf8().data());
1894     }
1895 }
1896
1897 void Node::showTreeForThis() const
1898 {
1899     showTreeAndMark(this, "*");
1900 }
1901
1902 void Node::showTreeAndMark(const Node* markedNode1, const char* markedLabel1, const Node* markedNode2, const char * markedLabel2) const
1903 {
1904     const Node* rootNode;
1905     const Node* node = this;
1906     while (node->parentNode() && !node->hasTagName(bodyTag))
1907         node = node->parentNode();
1908     rootNode = node;
1909         
1910     for (node = rootNode; node; node = node->traverseNextNode()) {
1911         if (node == markedNode1)
1912             fprintf(stderr, "%s", markedLabel1);
1913         if (node == markedNode2)
1914             fprintf(stderr, "%s", markedLabel2);
1915                         
1916         for (const Node* tmpNode = node; tmpNode && tmpNode != rootNode; tmpNode = tmpNode->parentNode())
1917             fprintf(stderr, "\t");
1918         node->showNode();
1919     }
1920 }
1921
1922 void Node::formatForDebugger(char* buffer, unsigned length) const
1923 {
1924     String result;
1925     String s;
1926     
1927     s = nodeName();
1928     if (s.length() == 0)
1929         result += "<none>";
1930     else
1931         result += s;
1932           
1933     strncpy(buffer, result.utf8().data(), length - 1);
1934 }
1935
1936 #endif
1937
1938 // --------
1939
1940 void NodeListsNodeData::invalidateCaches()
1941 {
1942     m_childNodeListCaches.reset();
1943     invalidateCachesThatDependOnAttributes();
1944 }
1945
1946 void NodeListsNodeData::invalidateCachesThatDependOnAttributes()
1947 {
1948     CacheMap::iterator classCachesEnd = m_classNodeListCaches.end();
1949     for (CacheMap::iterator it = m_classNodeListCaches.begin(); it != classCachesEnd; ++it)
1950         it->second->reset();
1951
1952     CacheMap::iterator nameCachesEnd = m_nameNodeListCaches.end();
1953     for (CacheMap::iterator it = m_nameNodeListCaches.begin(); it != nameCachesEnd; ++it)
1954         it->second->reset();
1955 }
1956
1957 bool NodeListsNodeData::isEmpty() const
1958 {
1959     if (!m_listsWithCaches.isEmpty())
1960         return false;
1961
1962     if (m_childNodeListCaches.refCount)
1963         return false;
1964
1965     CacheMap::const_iterator classCachesEnd = m_classNodeListCaches.end();
1966     for (CacheMap::const_iterator it = m_classNodeListCaches.begin(); it != classCachesEnd; ++it) {
1967         if (it->second->refCount)
1968             return false;
1969     }
1970
1971     CacheMap::const_iterator nameCachesEnd = m_nameNodeListCaches.end();
1972     for (CacheMap::const_iterator it = m_nameNodeListCaches.begin(); it != nameCachesEnd; ++it) {
1973         if (it->second->refCount)
1974             return false;
1975     }
1976
1977     return true;
1978 }
1979
1980 void Node::getSubresourceURLs(Vector<KURL>& urls) const
1981 {
1982     Vector<String> subresourceStrings;
1983     getSubresourceAttributeStrings(subresourceStrings);
1984     
1985     for (unsigned i = 0; i < subresourceStrings.size(); ++i) {
1986         String& subresourceString(subresourceStrings[i]);
1987         
1988         // FIXME: Is parseURL appropriate here?
1989         if (subresourceString.length())
1990             urls.append(document()->completeURL(parseURL(subresourceString)));
1991     }
1992 }
1993
1994 // --------
1995
1996 } // namespace WebCore
1997
1998 #ifndef NDEBUG
1999
2000 void showTree(const WebCore::Node* node)
2001 {
2002     if (node)
2003         node->showTreeForThis();
2004 }
2005
2006 #endif