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