Inline Node::traverseNextNode
[WebKit-https.git] / Source / 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, 2010, 2011 Apple Inc. All rights reserved.
6  * Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies)
7  * Copyright (C) 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
8  *
9  * This library is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU Library General Public
11  * License as published by the Free Software Foundation; either
12  * version 2 of the License, or (at your option) any later version.
13  *
14  * This library is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17  * Library General Public License for more details.
18  *
19  * You should have received a copy of the GNU Library General Public License
20  * along with this library; see the file COPYING.LIB.  If not, write to
21  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
22  * Boston, MA 02110-1301, USA.
23  */
24
25 #include "config.h"
26 #include "Node.h"
27
28 #include "AXObjectCache.h"
29 #include "Attr.h"
30 #include "Attribute.h"
31 #include "BeforeLoadEvent.h"
32 #include "ChildListMutationScope.h"
33 #include "Chrome.h"
34 #include "ChromeClient.h"
35 #include "CSSParser.h"
36 #include "CSSRule.h"
37 #include "CSSSelector.h"
38 #include "CSSSelectorList.h"
39 #include "CSSStyleRule.h"
40 #include "CSSStyleSheet.h"
41 #include "ChildNodeList.h"
42 #include "ClassNodeList.h"
43 #include "ContextMenuController.h"
44 #include "DOMImplementation.h"
45 #include "DOMSettableTokenList.h"
46 #include "Document.h"
47 #include "DocumentType.h"
48 #include "DynamicNodeList.h"
49 #include "Element.h"
50 #include "ElementShadow.h"
51 #include "Event.h"
52 #include "EventContext.h"
53 #include "EventDispatchMediator.h"
54 #include "EventDispatcher.h"
55 #include "EventException.h"
56 #include "EventHandler.h"
57 #include "EventListener.h"
58 #include "EventNames.h"
59 #include "ExceptionCode.h"
60 #include "Frame.h"
61 #include "FrameView.h"
62 #include "HTMLElement.h"
63 #include "HTMLFrameOwnerElement.h"
64 #include "HTMLNames.h"
65 #include "InspectorCounters.h"
66 #include "KeyboardEvent.h"
67 #include "LabelsNodeList.h"
68 #include "Logging.h"
69 #include "MouseEvent.h"
70 #include "MutationEvent.h"
71 #include "NameNodeList.h"
72 #include "NamedNodeMap.h"
73 #include "NodeRareData.h"
74 #include "NodeRenderingContext.h"
75 #include "Page.h"
76 #include "PlatformMouseEvent.h"
77 #include "PlatformWheelEvent.h"
78 #include "ProcessingInstruction.h"
79 #include "ProgressEvent.h"
80 #include "RadioNodeList.h"
81 #include "RegisteredEventListener.h"
82 #include "RenderBlock.h"
83 #include "RenderBox.h"
84 #include "RenderTextControl.h"
85 #include "RenderView.h"
86 #include "ScopedEventQueue.h"
87 #include "SelectorQuery.h"
88 #include "Settings.h"
89 #include "ShadowRoot.h"
90 #include "StaticNodeList.h"
91 #include "StorageEvent.h"
92 #include "StyleResolver.h"
93 #include "TagNodeList.h"
94 #include "Text.h"
95 #include "TextEvent.h"
96 #include "TreeScopeAdopter.h"
97 #include "UIEvent.h"
98 #include "UIEventWithKeyState.h"
99 #include "WheelEvent.h"
100 #include "WindowEventContext.h"
101 #include "XMLNames.h"
102 #include "htmlediting.h"
103 #include <wtf/HashSet.h>
104 #include <wtf/PassOwnPtr.h>
105 #include <wtf/RefCountedLeakCounter.h>
106 #include <wtf/UnusedParam.h>
107 #include <wtf/Vector.h>
108 #include <wtf/text/CString.h>
109 #include <wtf/text/StringBuilder.h>
110
111 #if ENABLE(INSPECTOR)
112 #include "InspectorController.h"
113 #endif
114
115 #if ENABLE(SVG)
116 #include "SVGElementInstance.h"
117 #include "SVGUseElement.h"
118 #endif
119
120 #if USE(JSC)
121 #include <runtime/JSGlobalData.h>
122 #endif
123
124 #if ENABLE(MICRODATA)
125 #include "HTMLPropertiesCollection.h"
126 #endif
127
128 using namespace std;
129
130 namespace WebCore {
131
132 using namespace HTMLNames;
133
134 bool Node::isSupported(const String& feature, const String& version)
135 {
136     return DOMImplementation::hasFeature(feature, version);
137 }
138
139 #if DUMP_NODE_STATISTICS
140 static HashSet<Node*> liveNodeSet;
141 #endif
142
143 void Node::dumpStatistics()
144 {
145 #if DUMP_NODE_STATISTICS
146     size_t nodesWithRareData = 0;
147
148     size_t elementNodes = 0;
149     size_t attrNodes = 0;
150     size_t textNodes = 0;
151     size_t cdataNodes = 0;
152     size_t commentNodes = 0;
153     size_t entityReferenceNodes = 0;
154     size_t entityNodes = 0;
155     size_t piNodes = 0;
156     size_t documentNodes = 0;
157     size_t docTypeNodes = 0;
158     size_t fragmentNodes = 0;
159     size_t notationNodes = 0;
160     size_t xpathNSNodes = 0;
161     size_t shadowRootNodes = 0;
162
163     HashMap<String, size_t> perTagCount;
164
165     size_t attributes = 0;
166     size_t attributesWithAttr = 0;
167     size_t elementsWithAttributeStorage = 0;
168     size_t elementsWithRareData = 0;
169     size_t elementsWithNamedNodeMap = 0;
170
171     for (HashSet<Node*>::iterator it = liveNodeSet.begin(); it != liveNodeSet.end(); ++it) {
172         Node* node = *it;
173
174         if (node->hasRareData()) {
175             ++nodesWithRareData;
176             if (node->isElementNode()) {
177                 ++elementsWithRareData;
178                 if (toElement(node)->hasNamedNodeMap())
179                     ++elementsWithNamedNodeMap;
180             }
181         }
182
183         switch (node->nodeType()) {
184             case ELEMENT_NODE: {
185                 ++elementNodes;
186
187                 // Tag stats
188                 Element* element = static_cast<Element*>(node);
189                 HashMap<String, size_t>::AddResult result = perTagCount.add(element->tagName(), 1);
190                 if (!result.isNewEntry)
191                     result.iterator->second++;
192
193                 if (ElementAttributeData* attributeData = element->attributeData()) {
194                     attributes += attributeData->length();
195                     ++elementsWithAttributeStorage;
196                     for (unsigned i = 0; i < attributeData->length(); ++i) {
197                         Attribute* attr = attributeData->attributeItem(i);
198                         if (attr->attr())
199                             ++attributesWithAttr;
200                     }
201                 }
202                 break;
203             }
204             case ATTRIBUTE_NODE: {
205                 ++attrNodes;
206                 break;
207             }
208             case TEXT_NODE: {
209                 ++textNodes;
210                 break;
211             }
212             case CDATA_SECTION_NODE: {
213                 ++cdataNodes;
214                 break;
215             }
216             case COMMENT_NODE: {
217                 ++commentNodes;
218                 break;
219             }
220             case ENTITY_REFERENCE_NODE: {
221                 ++entityReferenceNodes;
222                 break;
223             }
224             case ENTITY_NODE: {
225                 ++entityNodes;
226                 break;
227             }
228             case PROCESSING_INSTRUCTION_NODE: {
229                 ++piNodes;
230                 break;
231             }
232             case DOCUMENT_NODE: {
233                 ++documentNodes;
234                 break;
235             }
236             case DOCUMENT_TYPE_NODE: {
237                 ++docTypeNodes;
238                 break;
239             }
240             case DOCUMENT_FRAGMENT_NODE: {
241                 if (node->isShadowRoot())
242                     ++shadowRootNodes;
243                 else
244                     ++fragmentNodes;
245                 break;
246             }
247             case NOTATION_NODE: {
248                 ++notationNodes;
249                 break;
250             }
251             case XPATH_NAMESPACE_NODE: {
252                 ++xpathNSNodes;
253                 break;
254             }
255         }
256     }
257
258     printf("Number of Nodes: %d\n\n", liveNodeSet.size());
259     printf("Number of Nodes with RareData: %zu\n\n", nodesWithRareData);
260
261     printf("NodeType distribution:\n");
262     printf("  Number of Element nodes: %zu\n", elementNodes);
263     printf("  Number of Attribute nodes: %zu\n", attrNodes);
264     printf("  Number of Text nodes: %zu\n", textNodes);
265     printf("  Number of CDATASection nodes: %zu\n", cdataNodes);
266     printf("  Number of Comment nodes: %zu\n", commentNodes);
267     printf("  Number of EntityReference nodes: %zu\n", entityReferenceNodes);
268     printf("  Number of Entity nodes: %zu\n", entityNodes);
269     printf("  Number of ProcessingInstruction nodes: %zu\n", piNodes);
270     printf("  Number of Document nodes: %zu\n", documentNodes);
271     printf("  Number of DocumentType nodes: %zu\n", docTypeNodes);
272     printf("  Number of DocumentFragment nodes: %zu\n", fragmentNodes);
273     printf("  Number of Notation nodes: %zu\n", notationNodes);
274     printf("  Number of XPathNS nodes: %zu\n", xpathNSNodes);
275     printf("  Number of ShadowRoot nodes: %zu\n", shadowRootNodes);
276
277     printf("Element tag name distibution:\n");
278     for (HashMap<String, size_t>::iterator it = perTagCount.begin(); it != perTagCount.end(); ++it)
279         printf("  Number of <%s> tags: %zu\n", it->first.utf8().data(), it->second);
280
281     printf("Attributes:\n");
282     printf("  Number of Attributes (non-Node and Node): %zu [%zu]\n", attributes, sizeof(Attribute));
283     printf("  Number of Attributes with an Attr: %zu\n", attributesWithAttr);
284     printf("  Number of Elements with attribute storage: %zu [%zu]\n", elementsWithAttributeStorage, sizeof(ElementAttributeData));
285     printf("  Number of Elements with RareData: %zu\n", elementsWithRareData);
286     printf("  Number of Elements with NamedNodeMap: %zu [%zu]\n", elementsWithNamedNodeMap, sizeof(NamedNodeMap));
287 #endif
288 }
289
290 DEFINE_DEBUG_ONLY_GLOBAL(WTF::RefCountedLeakCounter, nodeCounter, ("WebCoreNode"));
291 DEFINE_DEBUG_ONLY_GLOBAL(HashSet<Node*>, ignoreSet, );
292
293 #ifndef NDEBUG
294 static bool shouldIgnoreLeaks = false;
295 #endif
296
297 void Node::startIgnoringLeaks()
298 {
299 #ifndef NDEBUG
300     shouldIgnoreLeaks = true;
301 #endif
302 }
303
304 void Node::stopIgnoringLeaks()
305 {
306 #ifndef NDEBUG
307     shouldIgnoreLeaks = false;
308 #endif
309 }
310
311 Node::StyleChange Node::diff(const RenderStyle* s1, const RenderStyle* s2, Document* doc)
312 {
313     StyleChange ch = NoInherit;
314     EDisplay display1 = s1 ? s1->display() : NONE;
315     bool fl1 = s1 && s1->hasPseudoStyle(FIRST_LETTER);
316     EDisplay display2 = s2 ? s2->display() : NONE;
317     bool fl2 = s2 && s2->hasPseudoStyle(FIRST_LETTER);
318     
319     // We just detach if a renderer acquires or loses a column-span, since spanning elements
320     // typically won't contain much content.
321     bool colSpan1 = s1 && s1->columnSpan();
322     bool colSpan2 = s2 && s2->columnSpan();
323     
324     bool specifiesColumns1 = s1 && (!s1->hasAutoColumnCount() || !s1->hasAutoColumnWidth());
325     bool specifiesColumns2 = s2 && (!s2->hasAutoColumnCount() || !s2->hasAutoColumnWidth());
326
327     if (display1 != display2 || fl1 != fl2 || colSpan1 != colSpan2 
328         || (specifiesColumns1 != specifiesColumns2 && doc->settings()->regionBasedColumnsEnabled())
329         || (s1 && s2 && !s1->contentDataEquivalent(s2)))
330         ch = Detach;
331     else if (!s1 || !s2)
332         ch = Inherit;
333     else if (*s1 == *s2)
334         ch = NoChange;
335     else if (s1->inheritedNotEqual(s2))
336         ch = Inherit;
337     else if (s1->hasExplicitlyInheritedProperties() || s2->hasExplicitlyInheritedProperties())
338         ch = Inherit;
339
340     // For nth-child and other positional rules, treat styles as different if they have
341     // changed positionally in the DOM. This way subsequent sibling resolutions won't be confused
342     // by the wrong child index and evaluate to incorrect results.
343     if (ch == NoChange && s1->childIndex() != s2->childIndex())
344         ch = NoInherit;
345
346     // If the pseudoStyles have changed, we want any StyleChange that is not NoChange
347     // because setStyle will do the right thing with anything else.
348     if (ch == NoChange && s1->hasAnyPublicPseudoStyles()) {
349         for (PseudoId pseudoId = FIRST_PUBLIC_PSEUDOID; ch == NoChange && pseudoId < FIRST_INTERNAL_PSEUDOID; pseudoId = static_cast<PseudoId>(pseudoId + 1)) {
350             if (s1->hasPseudoStyle(pseudoId)) {
351                 RenderStyle* ps2 = s2->getCachedPseudoStyle(pseudoId);
352                 if (!ps2)
353                     ch = NoInherit;
354                 else {
355                     RenderStyle* ps1 = s1->getCachedPseudoStyle(pseudoId);
356                     ch = ps1 && *ps1 == *ps2 ? NoChange : NoInherit;
357                 }
358             }
359         }
360     }
361
362     // When text-combine property has been changed, we need to prepare a separate renderer object.
363     // When text-combine is on, we use RenderCombineText, otherwise RenderText.
364     // https://bugs.webkit.org/show_bug.cgi?id=55069
365     if ((s1 && s2) && (s1->hasTextCombine() != s2->hasTextCombine()))
366         ch = Detach;
367
368     // We need to reattach the node, so that it is moved to the correct RenderFlowThread.
369     if ((s1 && s2) && (s1->flowThread() != s2->flowThread()))
370         ch = Detach;
371
372     // When the region thread has changed, we need to prepare a separate render region object.
373     if ((s1 && s2) && (s1->regionThread() != s2->regionThread()))
374         ch = Detach;
375
376     return ch;
377 }
378
379 void Node::trackForDebugging()
380 {
381 #ifndef NDEBUG
382     if (shouldIgnoreLeaks)
383         ignoreSet.add(this);
384     else
385         nodeCounter.increment();
386 #endif
387
388 #if DUMP_NODE_STATISTICS
389     liveNodeSet.add(this);
390 #endif
391 }
392
393 Node::~Node()
394 {
395 #ifndef NDEBUG
396     HashSet<Node*>::iterator it = ignoreSet.find(this);
397     if (it != ignoreSet.end())
398         ignoreSet.remove(it);
399     else
400         nodeCounter.decrement();
401 #endif
402
403 #if DUMP_NODE_STATISTICS
404     liveNodeSet.remove(this);
405 #endif
406
407     ASSERT(hasRareData() == NodeRareData::rareDataMap().contains(this));
408     if (hasRareData())
409         clearRareData();
410
411     if (renderer())
412         detach();
413
414     Document* doc = m_document;
415     if (AXObjectCache::accessibilityEnabled() && doc && doc->axObjectCacheExists())
416         doc->axObjectCache()->removeNodeForUse(this);
417     
418     if (m_previous)
419         m_previous->setNextSibling(0);
420     if (m_next)
421         m_next->setPreviousSibling(0);
422
423     if (doc)
424         doc->guardDeref();
425
426     InspectorCounters::decrementCounter(InspectorCounters::NodeCounter);
427 }
428
429 void Node::setDocument(Document* document)
430 {
431     ASSERT(!inDocument() || m_document == document);
432     if (inDocument() || m_document == document)
433         return;
434
435     m_document = document;
436 }
437
438 NodeRareData* Node::setTreeScope(TreeScope* scope)
439 {
440     if (!scope) {
441         if (hasRareData()) {
442             NodeRareData* data = rareData();
443             data->setTreeScope(0);
444             return data;
445         }
446
447         return 0;
448     }
449
450     NodeRareData* data = ensureRareData();
451     data->setTreeScope(scope);
452     return data;
453 }
454
455 TreeScope* Node::treeScope() const
456 {
457     // FIXME: Using m_document directly is not good -> see comment with document() in the header file.
458     if (!hasRareData())
459         return m_document;
460     TreeScope* scope = rareData()->treeScope();
461     return scope ? scope : m_document;
462 }
463
464 NodeRareData* Node::rareData() const
465 {
466     ASSERT(hasRareData());
467     return NodeRareData::rareDataFromMap(this);
468 }
469
470 NodeRareData* Node::ensureRareData()
471 {
472     if (hasRareData())
473         return rareData();
474     
475     ASSERT(!NodeRareData::rareDataMap().contains(this));
476     NodeRareData* data = createRareData().leakPtr();
477     NodeRareData::rareDataMap().set(this, data);
478     setFlag(HasRareDataFlag);
479     return data;
480 }
481     
482 OwnPtr<NodeRareData> Node::createRareData()
483 {
484     return adoptPtr(new NodeRareData);
485 }
486
487 void Node::clearRareData()
488 {
489     ASSERT(hasRareData());
490     if (treeScope() && rareData()->nodeLists())
491         treeScope()->removeNodeListCache();
492
493 #if ENABLE(MUTATION_OBSERVERS)
494     ASSERT(!transientMutationObserverRegistry() || transientMutationObserverRegistry()->isEmpty());
495 #endif
496
497     NodeRareData::NodeRareDataMap& dataMap = NodeRareData::rareDataMap();
498     NodeRareData::NodeRareDataMap::iterator it = dataMap.find(this);
499     ASSERT(it != dataMap.end());
500     delete it->second;
501     dataMap.remove(it);
502     clearFlag(HasRareDataFlag);
503 }
504
505 Element* Node::shadowHost() const
506 {
507     return toElement(isShadowRoot() ? parent() : 0);
508 }
509
510 void Node::setShadowHost(Element* host)
511 {
512     ASSERT(!parentNode() && isShadowRoot());
513     setParent(host);
514 }
515
516 Node* Node::toNode()
517 {
518     return this;
519 }
520
521 HTMLInputElement* Node::toInputElement()
522 {
523     // If one of the below ASSERTs trigger, you are calling this function
524     // directly or indirectly from a constructor or destructor of this object.
525     // Don't do this!
526     ASSERT(!(isHTMLElement() && hasTagName(inputTag)));
527     return 0;
528 }
529
530 short Node::tabIndex() const
531 {
532     return hasRareData() ? rareData()->tabIndex() : 0;
533 }
534     
535 void Node::setTabIndexExplicitly(short i)
536 {
537     ensureRareData()->setTabIndexExplicitly(i);
538 }
539
540 void Node::clearTabIndexExplicitly()
541 {
542     ensureRareData()->clearTabIndexExplicitly();
543 }
544
545 String Node::nodeValue() const
546 {
547     return String();
548 }
549
550 void Node::setNodeValue(const String& /*nodeValue*/, ExceptionCode& ec)
551 {
552     // NO_MODIFICATION_ALLOWED_ERR: Raised when the node is readonly
553     if (isReadOnlyNode()) {
554         ec = NO_MODIFICATION_ALLOWED_ERR;
555         return;
556     }
557
558     // By default, setting nodeValue has no effect.
559 }
560
561 PassRefPtr<NodeList> Node::childNodes()
562 {
563     NodeRareData* data = ensureRareData();
564     if (data->childNodeList())
565         return PassRefPtr<NodeList>(data->childNodeList());
566
567     RefPtr<ChildNodeList> list = ChildNodeList::create(this);
568     data->setChildNodeList(list.get());
569     return list.release();
570 }
571
572 Node *Node::lastDescendant() const
573 {
574     Node *n = const_cast<Node *>(this);
575     while (n && n->lastChild())
576         n = n->lastChild();
577     return n;
578 }
579
580 Node* Node::firstDescendant() const
581 {
582     Node *n = const_cast<Node *>(this);
583     while (n && n->firstChild())
584         n = n->firstChild();
585     return n;
586 }
587
588 bool Node::insertBefore(PassRefPtr<Node> newChild, Node* refChild, ExceptionCode& ec, bool shouldLazyAttach)
589 {
590     if (!isContainerNode()) {
591         ec = HIERARCHY_REQUEST_ERR;
592         return false;
593     }
594     return toContainerNode(this)->insertBefore(newChild, refChild, ec, shouldLazyAttach);
595 }
596
597 bool Node::replaceChild(PassRefPtr<Node> newChild, Node* oldChild, ExceptionCode& ec, bool shouldLazyAttach)
598 {
599     if (!isContainerNode()) {
600         ec = HIERARCHY_REQUEST_ERR;
601         return false;
602     }
603     return toContainerNode(this)->replaceChild(newChild, oldChild, ec, shouldLazyAttach);
604 }
605
606 bool Node::removeChild(Node* oldChild, ExceptionCode& ec)
607 {
608     if (!isContainerNode()) {
609         ec = NOT_FOUND_ERR;
610         return false;
611     }
612     return toContainerNode(this)->removeChild(oldChild, ec);
613 }
614
615 bool Node::appendChild(PassRefPtr<Node> newChild, ExceptionCode& ec, bool shouldLazyAttach)
616 {
617     if (!isContainerNode()) {
618         ec = HIERARCHY_REQUEST_ERR;
619         return false;
620     }
621     return toContainerNode(this)->appendChild(newChild, ec, shouldLazyAttach);
622 }
623
624 void Node::remove(ExceptionCode& ec)
625 {
626     if (ContainerNode* parent = parentNode())
627         parent->removeChild(this, ec);
628     else
629         ec = HIERARCHY_REQUEST_ERR;
630 }
631
632 void Node::normalize()
633 {
634     // Go through the subtree beneath us, normalizing all nodes. This means that
635     // any two adjacent text nodes are merged and any empty text nodes are removed.
636
637     RefPtr<Node> node = this;
638     while (Node* firstChild = node->firstChild())
639         node = firstChild;
640     while (node) {
641         NodeType type = node->nodeType();
642         if (type == ELEMENT_NODE)
643             static_cast<Element*>(node.get())->normalizeAttributes();
644
645         if (node == this)
646             break;
647
648         if (type != TEXT_NODE) {
649             node = node->traverseNextNodePostOrder();
650             continue;
651         }
652
653         RefPtr<Text> text = toText(node.get());
654
655         // Remove empty text nodes.
656         if (!text->length()) {
657             // Care must be taken to get the next node before removing the current node.
658             node = node->traverseNextNodePostOrder();
659             ExceptionCode ec;
660             text->remove(ec);
661             continue;
662         }
663
664         // Merge text nodes.
665         while (Node* nextSibling = node->nextSibling()) {
666             if (nextSibling->nodeType() != TEXT_NODE)
667                 break;
668             RefPtr<Text> nextText = toText(nextSibling);
669
670             // Remove empty text nodes.
671             if (!nextText->length()) {
672                 ExceptionCode ec;
673                 nextText->remove(ec);
674                 continue;
675             }
676
677             // Both non-empty text nodes. Merge them.
678             unsigned offset = text->length();
679             ExceptionCode ec;
680             text->appendData(nextText->data(), ec);
681             document()->textNodesMerged(nextText.get(), offset);
682             nextText->remove(ec);
683         }
684
685         node = node->traverseNextNodePostOrder();
686     }
687 }
688
689 const AtomicString& Node::virtualPrefix() const
690 {
691     // For nodes other than elements and attributes, the prefix is always null
692     return nullAtom;
693 }
694
695 void Node::setPrefix(const AtomicString& /*prefix*/, ExceptionCode& ec)
696 {
697     // The spec says that for nodes other than elements and attributes, prefix is always null.
698     // It does not say what to do when the user tries to set the prefix on another type of
699     // node, however Mozilla throws a NAMESPACE_ERR exception.
700     ec = NAMESPACE_ERR;
701 }
702
703 const AtomicString& Node::virtualLocalName() const
704 {
705     return nullAtom;
706 }
707
708 const AtomicString& Node::virtualNamespaceURI() const
709 {
710     return nullAtom;
711 }
712
713 bool Node::isContentEditable()
714 {
715     document()->updateStyleIfNeeded();
716     return rendererIsEditable(Editable);
717 }
718
719 bool Node::isContentRichlyEditable()
720 {
721     document()->updateStyleIfNeeded();
722     return rendererIsEditable(RichlyEditable);
723 }
724
725 void Node::inspect()
726 {
727 #if ENABLE(INSPECTOR)
728     if (document() && document()->page())
729         document()->page()->inspectorController()->inspect(this);
730 #endif
731 }
732
733 bool Node::rendererIsEditable(EditableLevel editableLevel) const
734 {
735     if (document()->frame() && document()->frame()->page() && document()->frame()->page()->isEditable() && !shadowTreeRootNode())
736         return true;
737
738     // Ideally we'd call ASSERT(!needsStyleRecalc()) here, but
739     // ContainerNode::setFocus() calls setNeedsStyleRecalc(), so the assertion
740     // would fire in the middle of Document::setFocusedNode().
741
742     for (const Node* node = this; node; node = node->parentNode()) {
743         if ((node->isHTMLElement() || node->isDocumentNode()) && node->renderer()) {
744             switch (node->renderer()->style()->userModify()) {
745             case READ_ONLY:
746                 return false;
747             case READ_WRITE:
748                 return true;
749             case READ_WRITE_PLAINTEXT_ONLY:
750                 return editableLevel != RichlyEditable;
751             }
752             ASSERT_NOT_REACHED();
753             return false;
754         }
755     }
756
757     return false;
758 }
759
760 bool Node::isEditableToAccessibility(EditableLevel editableLevel) const
761 {
762     if (rendererIsEditable(editableLevel))
763         return true;
764
765     // FIXME: Respect editableLevel for ARIA editable elements.
766     if (editableLevel == RichlyEditable)
767         return false;
768
769     ASSERT(document());
770     ASSERT(AXObjectCache::accessibilityEnabled());
771     ASSERT(document()->axObjectCacheExists());
772
773     if (document() && AXObjectCache::accessibilityEnabled() && document()->axObjectCacheExists())
774         return document()->axObjectCache()->rootAXEditableElement(this);
775
776     return false;
777 }
778
779 bool Node::shouldUseInputMethod()
780 {
781     return isContentEditable();
782 }
783
784 RenderBox* Node::renderBox() const
785 {
786     return m_renderer && m_renderer->isBox() ? toRenderBox(m_renderer) : 0;
787 }
788
789 RenderBoxModelObject* Node::renderBoxModelObject() const
790 {
791     return m_renderer && m_renderer->isBoxModelObject() ? toRenderBoxModelObject(m_renderer) : 0;
792 }
793
794 LayoutRect Node::getRect() const
795 {
796     if (renderer())
797         return renderer()->absoluteBoundingBoxRect();
798     return LayoutRect();
799 }
800     
801 LayoutRect Node::renderRect(bool* isReplaced)
802 {    
803     RenderObject* hitRenderer = this->renderer();
804     ASSERT(hitRenderer);
805     RenderObject* renderer = hitRenderer;
806     while (renderer && !renderer->isBody() && !renderer->isRoot()) {
807         if (renderer->isRenderBlock() || renderer->isInlineBlockOrInlineTable() || renderer->isReplaced()) {
808             *isReplaced = renderer->isReplaced();
809             return renderer->absoluteBoundingBoxRect();
810         }
811         renderer = renderer->parent();
812     }
813     return LayoutRect();    
814 }
815
816 bool Node::hasNonEmptyBoundingBox() const
817 {
818     // Before calling absoluteRects, check for the common case where the renderer
819     // is non-empty, since this is a faster check and almost always returns true.
820     RenderBoxModelObject* box = renderBoxModelObject();
821     if (!box)
822         return false;
823     if (!box->borderBoundingBox().isEmpty())
824         return true;
825
826     Vector<IntRect> rects;
827     FloatPoint absPos = renderer()->localToAbsolute();
828     renderer()->absoluteRects(rects, flooredLayoutPoint(absPos));
829     size_t n = rects.size();
830     for (size_t i = 0; i < n; ++i)
831         if (!rects[i].isEmpty())
832             return true;
833
834     return false;
835 }
836
837 inline static ShadowRoot* oldestShadowRootFor(const Node* node)
838 {
839     return node->isElementNode() && toElement(node)->hasShadowRoot() ? toElement(node)->shadow()->oldestShadowRoot() : 0;
840 }
841
842 inline void Node::setStyleChange(StyleChangeType changeType)
843 {
844     m_nodeFlags = (m_nodeFlags & ~StyleChangeMask) | changeType;
845 }
846
847 inline void Node::markAncestorsWithChildNeedsStyleRecalc()
848 {
849     for (ContainerNode* p = parentOrHostNode(); p && !p->childNeedsStyleRecalc(); p = p->parentOrHostNode())
850         p->setChildNeedsStyleRecalc();
851
852     if (document()->childNeedsStyleRecalc())
853         document()->scheduleStyleRecalc();
854 }
855
856 void Node::refEventTarget()
857 {
858     ref();
859 }
860
861 void Node::derefEventTarget()
862 {
863     deref();
864 }
865
866 void Node::setNeedsStyleRecalc(StyleChangeType changeType)
867 {
868     ASSERT(changeType != NoStyleChange);
869     if (!attached()) // changed compared to what?
870         return;
871
872     StyleChangeType existingChangeType = styleChangeType();
873     if (changeType > existingChangeType)
874         setStyleChange(changeType);
875
876     if (existingChangeType == NoStyleChange)
877         markAncestorsWithChildNeedsStyleRecalc();
878 }
879
880 void Node::lazyAttach(ShouldSetAttached shouldSetAttached)
881 {
882     for (Node* n = this; n; n = n->traverseNextNode(this)) {
883         if (n->hasChildNodes())
884             n->setChildNeedsStyleRecalc();
885         n->setStyleChange(FullStyleChange);
886         if (shouldSetAttached == SetAttached)
887             n->setAttached();
888     }
889     markAncestorsWithChildNeedsStyleRecalc();
890 }
891
892 void Node::setFocus(bool b)
893
894     if (b || hasRareData())
895         ensureRareData()->setFocused(b);
896 }
897
898 bool Node::rareDataFocused() const
899 {
900     ASSERT(hasRareData());
901     return rareData()->isFocused();
902 }
903
904 bool Node::supportsFocus() const
905 {
906     return hasRareData() && rareData()->tabIndexSetExplicitly();
907 }
908     
909 bool Node::isFocusable() const
910 {
911     if (!inDocument() || !supportsFocus())
912         return false;
913     
914     if (renderer())
915         ASSERT(!renderer()->needsLayout());
916     else
917         // If the node is in a display:none tree it might say it needs style recalc but
918         // the whole document is actually up to date.
919         ASSERT(!document()->childNeedsStyleRecalc());
920     
921     // FIXME: Even if we are not visible, we might have a child that is visible.
922     // Hyatt wants to fix that some day with a "has visible content" flag or the like.
923     if (!renderer() || renderer()->style()->visibility() != VISIBLE)
924         return false;
925
926     return true;
927 }
928
929 bool Node::isKeyboardFocusable(KeyboardEvent*) const
930 {
931     return isFocusable() && tabIndex() >= 0;
932 }
933
934 bool Node::isMouseFocusable() const
935 {
936     return isFocusable();
937 }
938
939 Node* Node::focusDelegate()
940 {
941     return this;
942 }
943
944 unsigned Node::nodeIndex() const
945 {
946     Node *_tempNode = previousSibling();
947     unsigned count=0;
948     for ( count=0; _tempNode; count++ )
949         _tempNode = _tempNode->previousSibling();
950     return count;
951 }
952
953 static void removeNodeListCacheIfPossible(Node* node, NodeRareData* data)
954 {
955     if (!data->nodeLists()->isEmpty())
956         return;
957     data->clearNodeLists();
958     node->treeScope()->removeNodeListCache();
959 }
960
961 // FIXME: Move this function to Document
962 void Node::registerDynamicSubtreeNodeList(DynamicSubtreeNodeList* list)
963 {
964     ASSERT(isDocumentNode());
965     NodeRareData* data = ensureRareData();
966     data->ensureNodeLists(this)->m_listsInvalidatedAtDocument.add(list);
967 }
968
969 // FIXME: Move this function to Document
970 void Node::unregisterDynamicSubtreeNodeList(DynamicSubtreeNodeList* list)
971 {
972     ASSERT(isDocumentNode());
973     ASSERT(hasRareData());
974     ASSERT(rareData()->nodeLists());
975     NodeRareData* data = rareData();
976     data->nodeLists()->m_listsInvalidatedAtDocument.remove(list);
977     removeNodeListCacheIfPossible(this, data);
978 }
979
980 void Node::invalidateNodeListsCacheAfterAttributeChanged(const QualifiedName& attrName)
981 {
982     if (hasRareData() && isAttributeNode()) {
983         NodeRareData* data = rareData();
984         ASSERT(!data->nodeLists());
985         data->clearChildNodeListCache();
986     }
987
988     // This list should be sync'ed with NodeListsNodeData.
989     if (attrName != classAttr
990 #if ENABLE(MICRODATA)
991         && attrName != itemscopeAttr
992         && attrName != itempropAttr
993         && attrName != itemtypeAttr
994 #endif
995         && attrName != idAttr
996         && attrName != typeAttr
997         && attrName != checkedAttr
998         && attrName != nameAttr
999         && attrName != forAttr)
1000         return;
1001
1002     if (!treeScope()->hasNodeListCaches())
1003         return;
1004
1005     for (Node* node = this; node; node = node->parentNode()) {
1006         ASSERT(this == node || !node->isAttributeNode());
1007         if (!node->hasRareData())
1008             continue;
1009         NodeRareData* data = node->rareData();
1010         if (!data->nodeLists())
1011             continue;
1012
1013         data->nodeLists()->invalidateCachesThatDependOnAttributes();
1014     }
1015 }
1016
1017 void Node::invalidateNodeListsCacheAfterChildrenChanged()
1018 {
1019     if (hasRareData())
1020         rareData()->clearChildNodeListCache();
1021
1022     if (!treeScope()->hasNodeListCaches())
1023         return;
1024     for (Node* node = this; node; node = node->parentNode()) {
1025         if (!node->hasRareData())
1026             continue;
1027         NodeRareData* data = node->rareData();
1028         if (!data->nodeLists())
1029             continue;
1030
1031         data->nodeLists()->invalidateCaches();
1032     }
1033 }
1034
1035 void Node::removeCachedClassNodeList(ClassNodeList* list, const String& className)
1036 {
1037     ASSERT(rareData());
1038     ASSERT(rareData()->nodeLists());
1039
1040     NodeListsNodeData* data = rareData()->nodeLists();
1041     ASSERT_UNUSED(list, list == data->m_classNodeListCache.get(className));
1042     data->m_classNodeListCache.remove(className);
1043 }
1044
1045 void Node::removeCachedNameNodeList(NameNodeList* list, const String& nodeName)
1046 {
1047     ASSERT(rareData());
1048     ASSERT(rareData()->nodeLists());
1049
1050     NodeListsNodeData* data = rareData()->nodeLists();
1051     ASSERT_UNUSED(list, list == data->m_nameNodeListCache.get(nodeName));
1052     data->m_nameNodeListCache.remove(nodeName);
1053 }
1054
1055 void Node::removeCachedTagNodeList(TagNodeList* list, const AtomicString& name)
1056 {
1057     ASSERT(rareData());
1058     ASSERT(rareData()->nodeLists());
1059
1060     NodeListsNodeData* data = rareData()->nodeLists();
1061     ASSERT_UNUSED(list, list == data->m_tagNodeListCache.get(name.impl()));
1062     data->m_tagNodeListCache.remove(name.impl());
1063 }
1064
1065 void Node::removeCachedTagNodeList(TagNodeList* list, const QualifiedName& name)
1066 {
1067     ASSERT(rareData());
1068     ASSERT(rareData()->nodeLists());
1069
1070     NodeListsNodeData* data = rareData()->nodeLists();
1071     ASSERT_UNUSED(list, list == data->m_tagNodeListCacheNS.get(name.impl()));
1072     data->m_tagNodeListCacheNS.remove(name.impl());
1073 }
1074
1075 void Node::removeCachedLabelsNodeList(DynamicSubtreeNodeList* list)
1076 {
1077     ASSERT(rareData());
1078     ASSERT(rareData()->nodeLists());
1079
1080     NodeListsNodeData* data = rareData()->nodeLists();
1081     ASSERT_UNUSED(list, list == data->m_labelsNodeListCache);
1082     data->m_labelsNodeListCache = 0;
1083 }
1084
1085 void Node::removeCachedChildNodeList()
1086 {
1087     ASSERT(rareData());
1088     rareData()->setChildNodeList(0);
1089 }
1090
1091 Node* Node::traverseNextAncestorSibling() const
1092 {
1093     ASSERT(!nextSibling());
1094     for (const Node* node = parentNode(); node; node = node->parentNode()) {
1095         if (node->nextSibling())
1096             return node->nextSibling();
1097     }
1098     return 0;
1099 }
1100
1101 Node* Node::traverseNextAncestorSibling(const Node* stayWithin) const
1102 {
1103     ASSERT(!nextSibling());
1104     ASSERT(this != stayWithin);
1105     for (const Node* node = parentNode(); node; node = node->parentNode()) {
1106         if (node == stayWithin)
1107             return 0;
1108         if (node->nextSibling())
1109             return node->nextSibling();
1110     }
1111     return 0;
1112 }
1113
1114 Node* Node::traverseNextNodePostOrder() const
1115 {
1116     Node* next = nextSibling();
1117     if (!next)
1118         return parentNode();
1119     while (Node* firstChild = next->firstChild())
1120         next = firstChild;
1121     return next;
1122 }
1123
1124 Node* Node::traversePreviousNode(const Node* stayWithin) const
1125 {
1126     if (this == stayWithin)
1127         return 0;
1128     if (previousSibling()) {
1129         Node *n = previousSibling();
1130         while (n->lastChild())
1131             n = n->lastChild();
1132         return n;
1133     }
1134     return parentNode();
1135 }
1136
1137 Node* Node::traversePreviousSibling(const Node* stayWithin) const
1138 {
1139     if (this == stayWithin)
1140         return 0;
1141     if (previousSibling())
1142         return previousSibling();
1143     const Node *n = this;
1144     while (n && !n->previousSibling() && (!stayWithin || n->parentNode() != stayWithin))
1145         n = n->parentNode();
1146     if (n)
1147         return n->previousSibling();
1148     return 0;
1149 }
1150
1151 Node* Node::traversePreviousNodePostOrder(const Node* stayWithin) const
1152 {
1153     if (lastChild())
1154         return lastChild();
1155     if (this == stayWithin)
1156         return 0;
1157     if (previousSibling())
1158         return previousSibling();
1159     const Node *n = this;
1160     while (n && !n->previousSibling() && (!stayWithin || n->parentNode() != stayWithin))
1161         n = n->parentNode();
1162     if (n)
1163         return n->previousSibling();
1164     return 0;
1165 }
1166
1167 Node* Node::traversePreviousSiblingPostOrder(const Node* stayWithin) const
1168 {
1169     if (this == stayWithin)
1170         return 0;
1171     if (previousSibling())
1172         return previousSibling();
1173     const Node *n = this;
1174     while (n && !n->previousSibling() && (!stayWithin || n->parentNode() != stayWithin))
1175         n = n->parentNode();
1176     if (n)
1177         return n->previousSibling();
1178     return 0;
1179 }
1180
1181 void Node::checkSetPrefix(const AtomicString& prefix, ExceptionCode& ec)
1182 {
1183     // Perform error checking as required by spec for setting Node.prefix. Used by
1184     // Element::setPrefix() and Attr::setPrefix()
1185
1186     if (!prefix.isEmpty() && !Document::isValidName(prefix)) {
1187         ec = INVALID_CHARACTER_ERR;
1188         return;
1189     }
1190
1191     if (isReadOnlyNode()) {
1192         ec = NO_MODIFICATION_ALLOWED_ERR;
1193         return;
1194     }
1195
1196     // FIXME: Raise NAMESPACE_ERR if prefix is malformed per the Namespaces in XML specification.
1197
1198     const AtomicString& nodeNamespaceURI = namespaceURI();
1199     if ((nodeNamespaceURI.isEmpty() && !prefix.isEmpty())
1200         || (prefix == xmlAtom && nodeNamespaceURI != XMLNames::xmlNamespaceURI)) {
1201         ec = NAMESPACE_ERR;
1202         return;
1203     }
1204     // Attribute-specific checks are in Attr::setPrefix().
1205 }
1206
1207 static bool isChildTypeAllowed(Node* newParent, Node* child)
1208 {
1209     if (child->nodeType() != Node::DOCUMENT_FRAGMENT_NODE) {
1210         if (!newParent->childTypeAllowed(child->nodeType()))
1211             return false;
1212         return true;
1213     }
1214     
1215     for (Node *n = child->firstChild(); n; n = n->nextSibling()) {
1216         if (!newParent->childTypeAllowed(n->nodeType()))
1217             return false;
1218     }
1219     return true;
1220 }
1221
1222 bool Node::canReplaceChild(Node* newChild, Node*)
1223 {
1224     return isChildTypeAllowed(this, newChild);
1225 }
1226
1227 static void checkAcceptChild(Node* newParent, Node* newChild, ExceptionCode& ec)
1228 {
1229     // Not mentioned in spec: throw NOT_FOUND_ERR if newChild is null
1230     if (!newChild) {
1231         ec = NOT_FOUND_ERR;
1232         return;
1233     }
1234     
1235     if (newParent->isReadOnlyNode()) {
1236         ec = NO_MODIFICATION_ALLOWED_ERR;
1237         return;
1238     }
1239
1240     if (newChild->inDocument() && newChild->nodeType() == Node::DOCUMENT_TYPE_NODE) {
1241         ec = HIERARCHY_REQUEST_ERR;
1242         return;
1243     }
1244
1245     // HIERARCHY_REQUEST_ERR: Raised if this node is of a type that does not allow children of the type of the
1246     // newChild node, or if the node to append is one of this node's ancestors.
1247
1248     if (newChild == newParent || newParent->isDescendantOf(newChild)) {
1249         ec = HIERARCHY_REQUEST_ERR;
1250         return;
1251     }
1252 }
1253
1254 void Node::checkReplaceChild(Node* newChild, Node* oldChild, ExceptionCode& ec)
1255 {
1256     if (!oldChild) {
1257         ec = NOT_FOUND_ERR;
1258         return;
1259     }
1260
1261     checkAcceptChild(this, newChild, ec);
1262     if (ec)
1263         return;
1264
1265     if (!canReplaceChild(newChild, oldChild)) {
1266         ec = HIERARCHY_REQUEST_ERR;
1267         return;
1268     }
1269 }
1270
1271 void Node::checkAddChild(Node *newChild, ExceptionCode& ec)
1272 {
1273     checkAcceptChild(this, newChild, ec);
1274     if (ec)
1275         return;
1276     
1277     if (!isChildTypeAllowed(this, newChild)) {
1278         ec = HIERARCHY_REQUEST_ERR;
1279         return;
1280     }
1281 }
1282
1283 bool Node::isDescendantOf(const Node *other) const
1284 {
1285     // Return true if other is an ancestor of this, otherwise false
1286     if (!other || !other->hasChildNodes() || inDocument() != other->inDocument())
1287         return false;
1288     if (other == other->document())
1289         return document() == other && this != document() && inDocument();
1290     for (const ContainerNode* n = parentNode(); n; n = n->parentNode()) {
1291         if (n == other)
1292             return true;
1293     }
1294     return false;
1295 }
1296
1297 bool Node::contains(const Node* node) const
1298 {
1299     if (!node)
1300         return false;
1301     return this == node || node->isDescendantOf(this);
1302 }
1303
1304 bool Node::containsIncludingShadowDOM(Node* node)
1305 {
1306     if (!node)
1307         return false;
1308     for (Node* n = node; n; n = n->parentOrHostNode()) {
1309         if (n == this)
1310             return true;
1311     }
1312     return false;
1313 }
1314
1315 void Node::attach()
1316 {
1317     ASSERT(!attached());
1318     ASSERT(!renderer() || (renderer()->style() && renderer()->parent()));
1319
1320     // FIXME: This is O(N^2) for the innerHTML case, where all children are replaced at once (and not attached).
1321     // If this node got a renderer it may be the previousRenderer() of sibling text nodes and thus affect the
1322     // result of Text::rendererIsNeeded() for those nodes.
1323     if (renderer()) {
1324         for (Node* next = nextSibling(); next; next = next->nextSibling()) {
1325             if (next->renderer())
1326                 break;
1327             if (!next->attached())
1328                 break;  // Assume this means none of the following siblings are attached.
1329             if (next->isTextNode())
1330                 next->createRendererIfNeeded();
1331         }
1332     }
1333
1334     setAttached();
1335     clearNeedsStyleRecalc();
1336 }
1337
1338 void Node::detach()
1339 {
1340     if (renderer())
1341         renderer()->destroyAndCleanupAnonymousWrappers();
1342     setRenderer(0);
1343
1344     Document* doc = document();
1345     if (hovered())
1346         doc->hoveredNodeDetached(this);
1347     if (inActiveChain())
1348         doc->activeChainNodeDetached(this);
1349
1350     clearFlag(IsActiveFlag);
1351     clearFlag(IsHoveredFlag);
1352     clearFlag(InActiveChainFlag);
1353     clearFlag(IsAttachedFlag);
1354 }
1355
1356 // FIXME: This code is used by editing.  Seems like it could move over there and not pollute Node.
1357 Node *Node::previousNodeConsideringAtomicNodes() const
1358 {
1359     if (previousSibling()) {
1360         Node *n = previousSibling();
1361         while (!isAtomicNode(n) && n->lastChild())
1362             n = n->lastChild();
1363         return n;
1364     }
1365     else if (parentNode()) {
1366         return parentNode();
1367     }
1368     else {
1369         return 0;
1370     }
1371 }
1372
1373 Node *Node::nextNodeConsideringAtomicNodes() const
1374 {
1375     if (!isAtomicNode(this) && firstChild())
1376         return firstChild();
1377     if (nextSibling())
1378         return nextSibling();
1379     const Node *n = this;
1380     while (n && !n->nextSibling())
1381         n = n->parentNode();
1382     if (n)
1383         return n->nextSibling();
1384     return 0;
1385 }
1386
1387 Node *Node::previousLeafNode() const
1388 {
1389     Node *node = previousNodeConsideringAtomicNodes();
1390     while (node) {
1391         if (isAtomicNode(node))
1392             return node;
1393         node = node->previousNodeConsideringAtomicNodes();
1394     }
1395     return 0;
1396 }
1397
1398 Node *Node::nextLeafNode() const
1399 {
1400     Node *node = nextNodeConsideringAtomicNodes();
1401     while (node) {
1402         if (isAtomicNode(node))
1403             return node;
1404         node = node->nextNodeConsideringAtomicNodes();
1405     }
1406     return 0;
1407 }
1408
1409 ContainerNode* Node::parentNodeForRenderingAndStyle()
1410 {
1411     return NodeRenderingContext(this).parentNodeForRenderingAndStyle();
1412 }
1413
1414 void Node::createRendererIfNeeded()
1415 {
1416     NodeRendererFactory(this).createRendererIfNeeded();
1417 }
1418
1419 bool Node::rendererIsNeeded(const NodeRenderingContext& context)
1420 {
1421     return (document()->documentElement() == this) || (context.style()->display() != NONE);
1422 }
1423
1424 RenderObject* Node::createRenderer(RenderArena*, RenderStyle*)
1425 {
1426     ASSERT_NOT_REACHED();
1427     return 0;
1428 }
1429     
1430 RenderStyle* Node::nonRendererRenderStyle() const
1431
1432     return 0; 
1433 }   
1434
1435 void Node::setRenderStyle(PassRefPtr<RenderStyle> s)
1436 {
1437     if (m_renderer)
1438         m_renderer->setAnimatableStyle(s); 
1439 }
1440
1441 RenderStyle* Node::virtualComputedStyle(PseudoId pseudoElementSpecifier)
1442 {
1443     return parentOrHostNode() ? parentOrHostNode()->computedStyle(pseudoElementSpecifier) : 0;
1444 }
1445
1446 int Node::maxCharacterOffset() const
1447 {
1448     ASSERT_NOT_REACHED();
1449     return 0;
1450 }
1451
1452 // FIXME: Shouldn't these functions be in the editing code?  Code that asks questions about HTML in the core DOM class
1453 // is obviously misplaced.
1454 bool Node::canStartSelection() const
1455 {
1456     if (rendererIsEditable())
1457         return true;
1458
1459     if (renderer()) {
1460         RenderStyle* style = renderer()->style();
1461         // We allow selections to begin within an element that has -webkit-user-select: none set,
1462         // but if the element is draggable then dragging should take priority over selection.
1463         if (style->userDrag() == DRAG_ELEMENT && style->userSelect() == SELECT_NONE)
1464             return false;
1465     }
1466     return parentOrHostNode() ? parentOrHostNode()->canStartSelection() : true;
1467 }
1468
1469
1470 Node* Node::shadowAncestorNode() const
1471 {
1472 #if ENABLE(SVG)
1473     // SVG elements living in a shadow tree only occur when <use> created them.
1474     // For these cases we do NOT want to return the shadowParentNode() here
1475     // but the actual shadow tree element - as main difference to the HTML forms
1476     // shadow tree concept. (This function _could_ be made virtual - opinions?)
1477     if (isSVGElement())
1478         return const_cast<Node*>(this);
1479 #endif
1480
1481     Node* root = shadowTreeRootNode();
1482     if (root)
1483         return root->shadowHost();
1484     return const_cast<Node*>(this);
1485 }
1486
1487 Node* Node::shadowTreeRootNode() const
1488 {
1489     Node* root = const_cast<Node*>(this);
1490     while (root) {
1491         if (root->isShadowRoot())
1492             return root;
1493         root = root->parentNodeGuaranteedHostFree();
1494     }
1495     return 0;
1496 }
1497
1498 Node* Node::nonBoundaryShadowTreeRootNode()
1499 {
1500     ASSERT(!isShadowRoot());
1501     Node* root = this;
1502     while (root) {
1503         if (root->isShadowRoot())
1504             return root;
1505         Node* parent = root->parentNodeGuaranteedHostFree();
1506         if (parent && parent->isShadowRoot())
1507             return root;
1508         root = parent;
1509     }
1510     return 0;
1511 }
1512
1513 ContainerNode* Node::nonShadowBoundaryParentNode() const
1514 {
1515     ContainerNode* parent = parentNode();
1516     return parent && !parent->isShadowRoot() ? parent : 0;
1517 }
1518
1519 bool Node::isInShadowTree() const
1520 {
1521     return treeScope() != document();
1522 }
1523
1524 Element* Node::parentOrHostElement() const
1525 {
1526     ContainerNode* parent = parentOrHostNode();
1527     if (!parent)
1528         return 0;
1529
1530     if (parent->isShadowRoot())
1531         return parent->shadowHost();
1532
1533     if (!parent->isElementNode())
1534         return 0;
1535
1536     return toElement(parent);
1537 }
1538
1539
1540 bool Node::isBlockFlow() const
1541 {
1542     return renderer() && renderer()->isBlockFlow();
1543 }
1544
1545 bool Node::isBlockFlowOrBlockTable() const
1546 {
1547     return renderer() && (renderer()->isBlockFlow() || (renderer()->isTable() && !renderer()->isInline()));
1548 }
1549
1550 Element *Node::enclosingBlockFlowElement() const
1551 {
1552     Node *n = const_cast<Node *>(this);
1553     if (isBlockFlow())
1554         return static_cast<Element *>(n);
1555
1556     while (1) {
1557         n = n->parentNode();
1558         if (!n)
1559             break;
1560         if (n->isBlockFlow() || n->hasTagName(bodyTag))
1561             return static_cast<Element *>(n);
1562     }
1563     return 0;
1564 }
1565
1566 Element* Node::rootEditableElement(EditableType editableType) const
1567 {
1568     if (editableType == HasEditableAXRole)
1569         return const_cast<Element*>(document()->axObjectCache()->rootAXEditableElement(this));
1570
1571     return rootEditableElement();
1572 }
1573
1574 Element* Node::rootEditableElement() const
1575 {
1576     Element* result = 0;
1577     for (Node* n = const_cast<Node*>(this); n && n->rendererIsEditable(); n = n->parentNode()) {
1578         if (n->isElementNode())
1579             result = static_cast<Element*>(n);
1580         if (n->hasTagName(bodyTag))
1581             break;
1582     }
1583     return result;
1584 }
1585
1586 bool Node::inSameContainingBlockFlowElement(Node *n)
1587 {
1588     return n ? enclosingBlockFlowElement() == n->enclosingBlockFlowElement() : false;
1589 }
1590
1591 // FIXME: End of obviously misplaced HTML editing functions.  Try to move these out of Node.
1592
1593 PassRefPtr<NodeList> Node::getElementsByTagName(const AtomicString& localName)
1594 {
1595     if (localName.isNull())
1596         return 0;
1597
1598     AtomicString localNameAtom = localName;
1599
1600     NodeListsNodeData::TagNodeListCache::AddResult result = ensureRareData()->ensureNodeLists(this)->m_tagNodeListCache.add(localNameAtom, 0);
1601     if (!result.isNewEntry)
1602         return PassRefPtr<TagNodeList>(result.iterator->second);
1603
1604     RefPtr<TagNodeList> list;
1605     if (document()->isHTMLDocument())
1606         list = HTMLTagNodeList::create(this, starAtom, localNameAtom);
1607     else
1608         list = TagNodeList::create(this, starAtom, localNameAtom);
1609     result.iterator->second = list.get();
1610     return list.release();   
1611 }
1612
1613 PassRefPtr<NodeList> Node::getElementsByTagNameNS(const AtomicString& namespaceURI, const AtomicString& localName)
1614 {
1615     if (localName.isNull())
1616         return 0;
1617
1618     if (namespaceURI == starAtom)
1619         return getElementsByTagName(localName);
1620
1621     AtomicString localNameAtom = localName;
1622
1623     NodeListsNodeData::TagNodeListCacheNS::AddResult result
1624         = ensureRareData()->ensureNodeLists(this)->m_tagNodeListCacheNS.add(QualifiedName(nullAtom, localNameAtom, namespaceURI).impl(), 0);
1625     if (!result.isNewEntry)
1626         return PassRefPtr<TagNodeList>(result.iterator->second);
1627
1628     RefPtr<TagNodeList> list = TagNodeList::create(this, namespaceURI.isEmpty() ? nullAtom : namespaceURI, localNameAtom);
1629     result.iterator->second = list.get();
1630     return list.release();
1631 }
1632
1633 PassRefPtr<NodeList> Node::getElementsByName(const String& elementName)
1634 {
1635     NodeListsNodeData::NameNodeListCache::AddResult result = ensureRareData()->ensureNodeLists(this)->m_nameNodeListCache.add(elementName, 0);
1636     if (!result.isNewEntry)
1637         return PassRefPtr<NodeList>(result.iterator->second);
1638
1639     RefPtr<NameNodeList> list = NameNodeList::create(this, elementName);
1640     result.iterator->second = list.get();
1641     return list.release();
1642 }
1643
1644 PassRefPtr<NodeList> Node::getElementsByClassName(const String& classNames)
1645 {
1646     NodeListsNodeData::ClassNodeListCache::AddResult result
1647         = ensureRareData()->ensureNodeLists(this)->m_classNodeListCache.add(classNames, 0);
1648     if (!result.isNewEntry)
1649         return PassRefPtr<NodeList>(result.iterator->second);
1650
1651     RefPtr<ClassNodeList> list = ClassNodeList::create(this, classNames);
1652     result.iterator->second = list.get();
1653     return list.release();
1654 }
1655
1656 PassRefPtr<Element> Node::querySelector(const String& selectors, ExceptionCode& ec)
1657 {
1658     if (selectors.isEmpty()) {
1659         ec = SYNTAX_ERR;
1660         return 0;
1661     }
1662     CSSParser parser(document());
1663     CSSSelectorList querySelectorList;
1664     parser.parseSelector(selectors, querySelectorList);
1665
1666     if (!querySelectorList.first() || querySelectorList.hasUnknownPseudoElements()) {
1667         ec = SYNTAX_ERR;
1668         return 0;
1669     }
1670
1671     // throw a NAMESPACE_ERR if the selector includes any namespace prefixes.
1672     if (querySelectorList.selectorsNeedNamespaceResolution()) {
1673         ec = NAMESPACE_ERR;
1674         return 0;
1675     }
1676     
1677     SelectorQuery selectorQuery(this, querySelectorList);
1678     return selectorQuery.queryFirst();
1679 }
1680
1681 PassRefPtr<NodeList> Node::querySelectorAll(const String& selectors, ExceptionCode& ec)
1682 {
1683     if (selectors.isEmpty()) {
1684         ec = SYNTAX_ERR;
1685         return 0;
1686     }
1687     CSSParser p(document());
1688     CSSSelectorList querySelectorList;
1689     p.parseSelector(selectors, querySelectorList);
1690
1691     if (!querySelectorList.first() || querySelectorList.hasUnknownPseudoElements()) {
1692         ec = SYNTAX_ERR;
1693         return 0;
1694     }
1695
1696     // Throw a NAMESPACE_ERR if the selector includes any namespace prefixes.
1697     if (querySelectorList.selectorsNeedNamespaceResolution()) {
1698         ec = NAMESPACE_ERR;
1699         return 0;
1700     }
1701
1702     SelectorQuery selectorQuery(this, querySelectorList);
1703     return selectorQuery.queryAll();
1704 }
1705
1706 Document *Node::ownerDocument() const
1707 {
1708     Document *doc = document();
1709     return doc == this ? 0 : doc;
1710 }
1711
1712 KURL Node::baseURI() const
1713 {
1714     return parentNode() ? parentNode()->baseURI() : KURL();
1715 }
1716
1717 bool Node::isEqualNode(Node* other) const
1718 {
1719     if (!other)
1720         return false;
1721     
1722     NodeType nodeType = this->nodeType();
1723     if (nodeType != other->nodeType())
1724         return false;
1725     
1726     if (nodeName() != other->nodeName())
1727         return false;
1728     
1729     if (localName() != other->localName())
1730         return false;
1731     
1732     if (namespaceURI() != other->namespaceURI())
1733         return false;
1734     
1735     if (prefix() != other->prefix())
1736         return false;
1737     
1738     if (nodeValue() != other->nodeValue())
1739         return false;
1740     
1741     if (isElementNode() && !toElement(this)->hasEquivalentAttributes(toElement(other)))
1742         return false;
1743     
1744     Node* child = firstChild();
1745     Node* otherChild = other->firstChild();
1746     
1747     while (child) {
1748         if (!child->isEqualNode(otherChild))
1749             return false;
1750         
1751         child = child->nextSibling();
1752         otherChild = otherChild->nextSibling();
1753     }
1754     
1755     if (otherChild)
1756         return false;
1757     
1758     if (nodeType == DOCUMENT_TYPE_NODE) {
1759         const DocumentType* documentTypeThis = static_cast<const DocumentType*>(this);
1760         const DocumentType* documentTypeOther = static_cast<const DocumentType*>(other);
1761         
1762         if (documentTypeThis->publicId() != documentTypeOther->publicId())
1763             return false;
1764
1765         if (documentTypeThis->systemId() != documentTypeOther->systemId())
1766             return false;
1767
1768         if (documentTypeThis->internalSubset() != documentTypeOther->internalSubset())
1769             return false;
1770
1771         // FIXME: We don't compare entities or notations because currently both are always empty.
1772     }
1773     
1774     return true;
1775 }
1776
1777 bool Node::isDefaultNamespace(const AtomicString& namespaceURIMaybeEmpty) const
1778 {
1779     const AtomicString& namespaceURI = namespaceURIMaybeEmpty.isEmpty() ? nullAtom : namespaceURIMaybeEmpty;
1780
1781     switch (nodeType()) {
1782         case ELEMENT_NODE: {
1783             const Element* elem = static_cast<const Element*>(this);
1784             
1785             if (elem->prefix().isNull())
1786                 return elem->namespaceURI() == namespaceURI;
1787
1788             if (elem->hasAttributes()) {
1789                 for (unsigned i = 0; i < elem->attributeCount(); i++) {
1790                     Attribute* attr = elem->attributeItem(i);
1791                     
1792                     if (attr->localName() == xmlnsAtom)
1793                         return attr->value() == namespaceURI;
1794                 }
1795             }
1796
1797             if (Element* ancestor = ancestorElement())
1798                 return ancestor->isDefaultNamespace(namespaceURI);
1799
1800             return false;
1801         }
1802         case DOCUMENT_NODE:
1803             if (Element* de = static_cast<const Document*>(this)->documentElement())
1804                 return de->isDefaultNamespace(namespaceURI);
1805             return false;
1806         case ENTITY_NODE:
1807         case NOTATION_NODE:
1808         case DOCUMENT_TYPE_NODE:
1809         case DOCUMENT_FRAGMENT_NODE:
1810             return false;
1811         case ATTRIBUTE_NODE: {
1812             const Attr* attr = static_cast<const Attr*>(this);
1813             if (attr->ownerElement())
1814                 return attr->ownerElement()->isDefaultNamespace(namespaceURI);
1815             return false;
1816         }
1817         default:
1818             if (Element* ancestor = ancestorElement())
1819                 return ancestor->isDefaultNamespace(namespaceURI);
1820             return false;
1821     }
1822 }
1823
1824 String Node::lookupPrefix(const AtomicString &namespaceURI) const
1825 {
1826     // Implemented according to
1827     // http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/namespaces-algorithms.html#lookupNamespacePrefixAlgo
1828     
1829     if (namespaceURI.isEmpty())
1830         return String();
1831     
1832     switch (nodeType()) {
1833         case ELEMENT_NODE:
1834             return lookupNamespacePrefix(namespaceURI, static_cast<const Element *>(this));
1835         case DOCUMENT_NODE:
1836             if (Element* de = static_cast<const Document*>(this)->documentElement())
1837                 return de->lookupPrefix(namespaceURI);
1838             return String();
1839         case ENTITY_NODE:
1840         case NOTATION_NODE:
1841         case DOCUMENT_FRAGMENT_NODE:
1842         case DOCUMENT_TYPE_NODE:
1843             return String();
1844         case ATTRIBUTE_NODE: {
1845             const Attr *attr = static_cast<const Attr *>(this);
1846             if (attr->ownerElement())
1847                 return attr->ownerElement()->lookupPrefix(namespaceURI);
1848             return String();
1849         }
1850         default:
1851             if (Element* ancestor = ancestorElement())
1852                 return ancestor->lookupPrefix(namespaceURI);
1853             return String();
1854     }
1855 }
1856
1857 String Node::lookupNamespaceURI(const String &prefix) const
1858 {
1859     // Implemented according to
1860     // http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/namespaces-algorithms.html#lookupNamespaceURIAlgo
1861     
1862     if (!prefix.isNull() && prefix.isEmpty())
1863         return String();
1864     
1865     switch (nodeType()) {
1866         case ELEMENT_NODE: {
1867             const Element *elem = static_cast<const Element *>(this);
1868             
1869             if (!elem->namespaceURI().isNull() && elem->prefix() == prefix)
1870                 return elem->namespaceURI();
1871             
1872             if (elem->hasAttributes()) {
1873                 for (unsigned i = 0; i < elem->attributeCount(); i++) {
1874                     Attribute* attr = elem->attributeItem(i);
1875                     
1876                     if (attr->prefix() == xmlnsAtom && attr->localName() == prefix) {
1877                         if (!attr->value().isEmpty())
1878                             return attr->value();
1879                         
1880                         return String();
1881                     } else if (attr->localName() == xmlnsAtom && prefix.isNull()) {
1882                         if (!attr->value().isEmpty())
1883                             return attr->value();
1884                         
1885                         return String();
1886                     }
1887                 }
1888             }
1889             if (Element* ancestor = ancestorElement())
1890                 return ancestor->lookupNamespaceURI(prefix);
1891             return String();
1892         }
1893         case DOCUMENT_NODE:
1894             if (Element* de = static_cast<const Document*>(this)->documentElement())
1895                 return de->lookupNamespaceURI(prefix);
1896             return String();
1897         case ENTITY_NODE:
1898         case NOTATION_NODE:
1899         case DOCUMENT_TYPE_NODE:
1900         case DOCUMENT_FRAGMENT_NODE:
1901             return String();
1902         case ATTRIBUTE_NODE: {
1903             const Attr *attr = static_cast<const Attr *>(this);
1904             
1905             if (attr->ownerElement())
1906                 return attr->ownerElement()->lookupNamespaceURI(prefix);
1907             else
1908                 return String();
1909         }
1910         default:
1911             if (Element* ancestor = ancestorElement())
1912                 return ancestor->lookupNamespaceURI(prefix);
1913             return String();
1914     }
1915 }
1916
1917 String Node::lookupNamespacePrefix(const AtomicString &_namespaceURI, const Element *originalElement) const
1918 {
1919     if (_namespaceURI.isNull())
1920         return String();
1921             
1922     if (originalElement->lookupNamespaceURI(prefix()) == _namespaceURI)
1923         return prefix();
1924     
1925     ASSERT(isElementNode());
1926     const Element* thisElement = toElement(this);
1927     if (thisElement->hasAttributes()) {
1928         for (unsigned i = 0; i < thisElement->attributeCount(); i++) {
1929             Attribute* attr = thisElement->attributeItem(i);
1930             
1931             if (attr->prefix() == xmlnsAtom && attr->value() == _namespaceURI
1932                     && originalElement->lookupNamespaceURI(attr->localName()) == _namespaceURI)
1933                 return attr->localName();
1934         }
1935     }
1936     
1937     if (Element* ancestor = ancestorElement())
1938         return ancestor->lookupNamespacePrefix(_namespaceURI, originalElement);
1939     return String();
1940 }
1941
1942 static void appendTextContent(const Node* node, bool convertBRsToNewlines, bool& isNullString, StringBuilder& content)
1943 {
1944     switch (node->nodeType()) {
1945     case Node::TEXT_NODE:
1946     case Node::CDATA_SECTION_NODE:
1947     case Node::COMMENT_NODE:
1948         isNullString = false;
1949         content.append(static_cast<const CharacterData*>(node)->data());
1950         break;
1951
1952     case Node::PROCESSING_INSTRUCTION_NODE:
1953         isNullString = false;
1954         content.append(static_cast<const ProcessingInstruction*>(node)->data());
1955         break;
1956     
1957     case Node::ELEMENT_NODE:
1958         if (node->hasTagName(brTag) && convertBRsToNewlines) {
1959             isNullString = false;
1960             content.append('\n');
1961             break;
1962         }
1963     // Fall through.
1964     case Node::ATTRIBUTE_NODE:
1965     case Node::ENTITY_NODE:
1966     case Node::ENTITY_REFERENCE_NODE:
1967     case Node::DOCUMENT_FRAGMENT_NODE:
1968         isNullString = false;
1969         for (Node* child = node->firstChild(); child; child = child->nextSibling()) {
1970             if (child->nodeType() == Node::COMMENT_NODE || child->nodeType() == Node::PROCESSING_INSTRUCTION_NODE)
1971                 continue;
1972             appendTextContent(child, convertBRsToNewlines, isNullString, content);
1973         }
1974         break;
1975
1976     case Node::DOCUMENT_NODE:
1977     case Node::DOCUMENT_TYPE_NODE:
1978     case Node::NOTATION_NODE:
1979     case Node::XPATH_NAMESPACE_NODE:
1980         break;
1981     }
1982 }
1983
1984 String Node::textContent(bool convertBRsToNewlines) const
1985 {
1986     StringBuilder content;
1987     bool isNullString = true;
1988     appendTextContent(this, convertBRsToNewlines, isNullString, content);
1989     return isNullString ? String() : content.toString();
1990 }
1991
1992 void Node::setTextContent(const String& text, ExceptionCode& ec)
1993 {           
1994     switch (nodeType()) {
1995         case TEXT_NODE:
1996         case CDATA_SECTION_NODE:
1997         case COMMENT_NODE:
1998         case PROCESSING_INSTRUCTION_NODE:
1999             setNodeValue(text, ec);
2000             return;
2001         case ELEMENT_NODE:
2002         case ATTRIBUTE_NODE:
2003         case ENTITY_NODE:
2004         case ENTITY_REFERENCE_NODE:
2005         case DOCUMENT_FRAGMENT_NODE: {
2006             RefPtr<ContainerNode> container = toContainerNode(this);
2007 #if ENABLE(MUTATION_OBSERVERS)
2008             ChildListMutationScope mutation(this);
2009 #endif
2010             container->removeChildren();
2011             if (!text.isEmpty())
2012                 container->appendChild(document()->createTextNode(text), ec);
2013             return;
2014         }
2015         case DOCUMENT_NODE:
2016         case DOCUMENT_TYPE_NODE:
2017         case NOTATION_NODE:
2018         case XPATH_NAMESPACE_NODE:
2019             // Do nothing.
2020             return;
2021     }
2022     ASSERT_NOT_REACHED();
2023 }
2024
2025 Element* Node::ancestorElement() const
2026 {
2027     // In theory, there can be EntityReference nodes between elements, but this is currently not supported.
2028     for (ContainerNode* n = parentNode(); n; n = n->parentNode()) {
2029         if (n->isElementNode())
2030             return static_cast<Element*>(n);
2031     }
2032     return 0;
2033 }
2034
2035 bool Node::offsetInCharacters() const
2036 {
2037     return false;
2038 }
2039
2040 unsigned short Node::compareDocumentPosition(Node* otherNode)
2041 {
2042     // It is not clear what should be done if |otherNode| is 0.
2043     if (!otherNode)
2044         return DOCUMENT_POSITION_DISCONNECTED;
2045
2046     if (otherNode == this)
2047         return DOCUMENT_POSITION_EQUIVALENT;
2048     
2049     Attr* attr1 = nodeType() == ATTRIBUTE_NODE ? static_cast<Attr*>(this) : 0;
2050     Attr* attr2 = otherNode->nodeType() == ATTRIBUTE_NODE ? static_cast<Attr*>(otherNode) : 0;
2051     
2052     Node* start1 = attr1 ? attr1->ownerElement() : this;
2053     Node* start2 = attr2 ? attr2->ownerElement() : otherNode;
2054     
2055     // If either of start1 or start2 is null, then we are disconnected, since one of the nodes is
2056     // an orphaned attribute node.
2057     if (!start1 || !start2)
2058         return DOCUMENT_POSITION_DISCONNECTED | DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC;
2059
2060     Vector<Node*, 16> chain1;
2061     Vector<Node*, 16> chain2;
2062     if (attr1)
2063         chain1.append(attr1);
2064     if (attr2)
2065         chain2.append(attr2);
2066     
2067     if (attr1 && attr2 && start1 == start2 && start1) {
2068         // We are comparing two attributes on the same node. Crawl our attribute map and see which one we hit first.
2069         Element* owner1 = attr1->ownerElement();
2070         owner1->updatedAttributeData(); // Force update invalid attributes.
2071         unsigned length = owner1->attributeCount();
2072         for (unsigned i = 0; i < length; ++i) {
2073             // If neither of the two determining nodes is a child node and nodeType is the same for both determining nodes, then an 
2074             // implementation-dependent order between the determining nodes is returned. This order is stable as long as no nodes of
2075             // the same nodeType are inserted into or removed from the direct container. This would be the case, for example, 
2076             // when comparing two attributes of the same element, and inserting or removing additional attributes might change 
2077             // the order between existing attributes.
2078             Attribute* attribute = owner1->attributeItem(i);
2079             if (attr1->qualifiedName() == attribute->name())
2080                 return DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | DOCUMENT_POSITION_FOLLOWING;
2081             if (attr2->qualifiedName() == attribute->name())
2082                 return DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | DOCUMENT_POSITION_PRECEDING;
2083         }
2084         
2085         ASSERT_NOT_REACHED();
2086         return DOCUMENT_POSITION_DISCONNECTED;
2087     }
2088
2089     // If one node is in the document and the other is not, we must be disconnected.
2090     // If the nodes have different owning documents, they must be disconnected.  Note that we avoid
2091     // comparing Attr nodes here, since they return false from inDocument() all the time (which seems like a bug).
2092     if (start1->inDocument() != start2->inDocument() ||
2093         start1->document() != start2->document())
2094         return DOCUMENT_POSITION_DISCONNECTED | DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC;
2095
2096     // We need to find a common ancestor container, and then compare the indices of the two immediate children.
2097     Node* current;
2098     for (current = start1; current; current = current->parentNode())
2099         chain1.append(current);
2100     for (current = start2; current; current = current->parentNode())
2101         chain2.append(current);
2102    
2103     // Walk the two chains backwards and look for the first difference.
2104     unsigned index1 = chain1.size();
2105     unsigned index2 = chain2.size();
2106     for (unsigned i = min(index1, index2); i; --i) {
2107         Node* child1 = chain1[--index1];
2108         Node* child2 = chain2[--index2];
2109         if (child1 != child2) {
2110             // If one of the children is an attribute, it wins.
2111             if (child1->nodeType() == ATTRIBUTE_NODE)
2112                 return DOCUMENT_POSITION_FOLLOWING;
2113             if (child2->nodeType() == ATTRIBUTE_NODE)
2114                 return DOCUMENT_POSITION_PRECEDING;
2115             
2116             if (!child2->nextSibling())
2117                 return DOCUMENT_POSITION_FOLLOWING;
2118             if (!child1->nextSibling())
2119                 return DOCUMENT_POSITION_PRECEDING;
2120
2121             // Otherwise we need to see which node occurs first.  Crawl backwards from child2 looking for child1.
2122             for (Node* child = child2->previousSibling(); child; child = child->previousSibling()) {
2123                 if (child == child1)
2124                     return DOCUMENT_POSITION_FOLLOWING;
2125             }
2126             return DOCUMENT_POSITION_PRECEDING;
2127         }
2128     }
2129     
2130     // There was no difference between the two parent chains, i.e., one was a subset of the other.  The shorter
2131     // chain is the ancestor.
2132     return index1 < index2 ? 
2133                DOCUMENT_POSITION_FOLLOWING | DOCUMENT_POSITION_CONTAINED_BY :
2134                DOCUMENT_POSITION_PRECEDING | DOCUMENT_POSITION_CONTAINS;
2135 }
2136
2137 FloatPoint Node::convertToPage(const FloatPoint& p) const
2138 {
2139     // If there is a renderer, just ask it to do the conversion
2140     if (renderer())
2141         return renderer()->localToAbsolute(p, false, true);
2142     
2143     // Otherwise go up the tree looking for a renderer
2144     Element *parent = ancestorElement();
2145     if (parent)
2146         return parent->convertToPage(p);
2147
2148     // No parent - no conversion needed
2149     return p;
2150 }
2151
2152 FloatPoint Node::convertFromPage(const FloatPoint& p) const
2153 {
2154     // If there is a renderer, just ask it to do the conversion
2155     if (renderer())
2156         return renderer()->absoluteToLocal(p, false, true);
2157
2158     // Otherwise go up the tree looking for a renderer
2159     Element *parent = ancestorElement();
2160     if (parent)
2161         return parent->convertFromPage(p);
2162
2163     // No parent - no conversion needed
2164     return p;
2165 }
2166
2167 #ifndef NDEBUG
2168
2169 static void appendAttributeDesc(const Node* node, String& string, const QualifiedName& name, const char* attrDesc)
2170 {
2171     if (node->isElementNode()) {
2172         String attr = static_cast<const Element*>(node)->getAttribute(name);
2173         if (!attr.isEmpty()) {
2174             string += attrDesc;
2175             string += attr;
2176         }
2177     }
2178 }
2179
2180 void Node::showNode(const char* prefix) const
2181 {
2182     if (!prefix)
2183         prefix = "";
2184     if (isTextNode()) {
2185         String value = nodeValue();
2186         value.replace('\\', "\\\\");
2187         value.replace('\n', "\\n");
2188         fprintf(stderr, "%s%s\t%p \"%s\"\n", prefix, nodeName().utf8().data(), this, value.utf8().data());
2189     } else {
2190         String attrs = "";
2191         appendAttributeDesc(this, attrs, classAttr, " CLASS=");
2192         appendAttributeDesc(this, attrs, styleAttr, " STYLE=");
2193         fprintf(stderr, "%s%s\t%p%s\n", prefix, nodeName().utf8().data(), this, attrs.utf8().data());
2194     }
2195 }
2196
2197 void Node::showTreeForThis() const
2198 {
2199     showTreeAndMark(this, "*");
2200 }
2201
2202 static void traverseTreeAndMark(const String& baseIndent, const Node* rootNode, const Node* markedNode1, const char* markedLabel1, const Node* markedNode2, const char* markedLabel2)
2203 {
2204     for (const Node* node = rootNode; node; node = node->traverseNextNode()) {
2205         if (node == markedNode1)
2206             fprintf(stderr, "%s", markedLabel1);
2207         if (node == markedNode2)
2208             fprintf(stderr, "%s", markedLabel2);
2209
2210         String indent = baseIndent;
2211         for (const Node* tmpNode = node; tmpNode && tmpNode != rootNode; tmpNode = tmpNode->parentOrHostNode())
2212             indent += "\t";
2213         fprintf(stderr, "%s", indent.utf8().data());
2214         node->showNode();
2215         if (node->isShadowRoot()) {
2216             if (ShadowRoot* youngerShadowRoot = toShadowRoot(node)->youngerShadowRoot())
2217                 traverseTreeAndMark(indent + "\t", youngerShadowRoot, markedNode1, markedLabel1, markedNode2, markedLabel2);
2218         } else if (ShadowRoot* oldestShadowRoot = oldestShadowRootFor(node))
2219             traverseTreeAndMark(indent + "\t", oldestShadowRoot, markedNode1, markedLabel1, markedNode2, markedLabel2);
2220     }
2221 }
2222
2223 void Node::showTreeAndMark(const Node* markedNode1, const char* markedLabel1, const Node* markedNode2, const char* markedLabel2) const
2224 {
2225     const Node* rootNode;
2226     const Node* node = this;
2227     while (node->parentOrHostNode() && !node->hasTagName(bodyTag))
2228         node = node->parentOrHostNode();
2229     rootNode = node;
2230
2231     String startingIndent;
2232     traverseTreeAndMark(startingIndent, rootNode, markedNode1, markedLabel1, markedNode2, markedLabel2);
2233 }
2234
2235 void Node::formatForDebugger(char* buffer, unsigned length) const
2236 {
2237     String result;
2238     String s;
2239     
2240     s = nodeName();
2241     if (s.length() == 0)
2242         result += "<none>";
2243     else
2244         result += s;
2245           
2246     strncpy(buffer, result.utf8().data(), length - 1);
2247 }
2248
2249 static ContainerNode* parentOrHostOrFrameOwner(const Node* node)
2250 {
2251     ContainerNode* parent = node->parentOrHostNode();
2252     if (!parent && node->document() && node->document()->frame())
2253         parent = node->document()->frame()->ownerElement();
2254     return parent;
2255 }
2256
2257 static void showSubTreeAcrossFrame(const Node* node, const Node* markedNode, const String& indent)
2258 {
2259     if (node == markedNode)
2260         fputs("*", stderr);
2261     fputs(indent.utf8().data(), stderr);
2262     node->showNode();
2263      if (node->isShadowRoot()) {
2264          if (ShadowRoot* youngerShadowRoot = toShadowRoot(node)->youngerShadowRoot())
2265              showSubTreeAcrossFrame(youngerShadowRoot, markedNode, indent + "\t");
2266      } else {
2267          if (node->isFrameOwnerElement())
2268              showSubTreeAcrossFrame(static_cast<const HTMLFrameOwnerElement*>(node)->contentDocument(), markedNode, indent + "\t");
2269          if (ShadowRoot* oldestShadowRoot = oldestShadowRootFor(node))
2270              showSubTreeAcrossFrame(oldestShadowRoot, markedNode, indent + "\t");
2271      }
2272     for (Node* child = node->firstChild(); child; child = child->nextSibling())
2273         showSubTreeAcrossFrame(child, markedNode, indent + "\t");
2274 }
2275
2276 void Node::showTreeForThisAcrossFrame() const
2277 {
2278     Node* rootNode = const_cast<Node*>(this);
2279     while (parentOrHostOrFrameOwner(rootNode))
2280         rootNode = parentOrHostOrFrameOwner(rootNode);
2281     showSubTreeAcrossFrame(rootNode, this, "");
2282 }
2283
2284 #endif
2285
2286 // --------
2287
2288 void NodeListsNodeData::invalidateCaches()
2289 {
2290     TagNodeListCache::const_iterator tagCacheEnd = m_tagNodeListCache.end();
2291     for (TagNodeListCache::const_iterator it = m_tagNodeListCache.begin(); it != tagCacheEnd; ++it)
2292         it->second->invalidateCache();
2293     TagNodeListCacheNS::const_iterator tagCacheNSEnd = m_tagNodeListCacheNS.end();
2294     for (TagNodeListCacheNS::const_iterator it = m_tagNodeListCacheNS.begin(); it != tagCacheNSEnd; ++it)
2295         it->second->invalidateCache();
2296     invalidateCachesThatDependOnAttributes();
2297 }
2298
2299 void NodeListsNodeData::invalidateCachesThatDependOnAttributes()
2300 {
2301     // Used by labels and region node lists on document.
2302     NodeListsNodeData::NodeListSet::iterator end = m_listsInvalidatedAtDocument.end();
2303     for (NodeListsNodeData::NodeListSet::iterator it = m_listsInvalidatedAtDocument.begin(); it != end; ++it)
2304         (*it)->invalidateCache();
2305
2306     ClassNodeListCache::iterator classCacheEnd = m_classNodeListCache.end();
2307     for (ClassNodeListCache::iterator it = m_classNodeListCache.begin(); it != classCacheEnd; ++it)
2308         it->second->invalidateCache();
2309
2310     NameNodeListCache::iterator nameCacheEnd = m_nameNodeListCache.end();
2311     for (NameNodeListCache::iterator it = m_nameNodeListCache.begin(); it != nameCacheEnd; ++it)
2312         it->second->invalidateCache();
2313     if (m_labelsNodeListCache)
2314         m_labelsNodeListCache->invalidateCache();
2315
2316 #if ENABLE(MICRODATA)
2317     MicroDataItemListCache::iterator itemListCacheEnd = m_microDataItemListCache.end();
2318     for (MicroDataItemListCache::iterator it = m_microDataItemListCache.begin(); it != itemListCacheEnd; ++it)
2319         it->second->invalidateCache();
2320 #endif
2321
2322     RadioNodeListCache::iterator radioNodeListCacheEnd = m_radioNodeListCache.end();
2323     for (RadioNodeListCache::iterator it = m_radioNodeListCache.begin(); it != radioNodeListCacheEnd; ++it)
2324         it->second->invalidateCache();
2325 }
2326
2327 bool NodeListsNodeData::isEmpty() const
2328 {
2329     if (!m_listsInvalidatedAtDocument.isEmpty())
2330         return false;
2331
2332     if (!m_tagNodeListCache.isEmpty())
2333         return false;
2334     if (!m_tagNodeListCacheNS.isEmpty())
2335         return false;
2336     if (!m_classNodeListCache.isEmpty())
2337         return false;
2338     if (!m_nameNodeListCache.isEmpty())
2339         return false;
2340 #if ENABLE(MICRODATA)
2341     if (!m_microDataItemListCache.isEmpty())
2342         return false;
2343 #endif
2344
2345     if (m_labelsNodeListCache)
2346         return false;
2347
2348     if (!m_radioNodeListCache.isEmpty())
2349         return false;
2350
2351     return true;
2352 }
2353
2354 void Node::getSubresourceURLs(ListHashSet<KURL>& urls) const
2355 {
2356     addSubresourceAttributeURLs(urls);
2357 }
2358
2359 Node* Node::enclosingLinkEventParentOrSelf()
2360 {
2361     for (Node* node = this; node; node = node->parentOrHostNode()) {
2362         // For imagemaps, the enclosing link node is the associated area element not the image itself.
2363         // So we don't let images be the enclosingLinkNode, even though isLink sometimes returns true
2364         // for them.
2365         if (node->isLink() && !node->hasTagName(imgTag))
2366             return node;
2367     }
2368
2369     return 0;
2370 }
2371
2372 const AtomicString& Node::interfaceName() const
2373 {
2374     return eventNames().interfaceForNode;
2375 }
2376
2377 ScriptExecutionContext* Node::scriptExecutionContext() const
2378 {
2379     return document();
2380 }
2381
2382 Node::InsertionNotificationRequest Node::insertedInto(Node* insertionPoint)
2383 {
2384     ASSERT(insertionPoint->inDocument() || isContainerNode());
2385     if (insertionPoint->inDocument())
2386         setFlag(InDocumentFlag);
2387     return InsertionDone;
2388 }
2389
2390 void Node::removedFrom(Node* insertionPoint)
2391 {
2392     ASSERT(insertionPoint->inDocument() || isContainerNode());
2393     if (insertionPoint->inDocument())
2394         clearFlag(InDocumentFlag);
2395 }
2396
2397 void Node::didMoveToNewDocument(Document* oldDocument)
2398 {
2399     TreeScopeAdopter::ensureDidMoveToNewDocumentWasCalled(oldDocument);
2400
2401     // FIXME: Event listener types for this node should be set on the new owner document here.
2402
2403 #if ENABLE(MUTATION_OBSERVERS)
2404     if (Vector<OwnPtr<MutationObserverRegistration> >* registry = mutationObserverRegistry()) {
2405         for (size_t i = 0; i < registry->size(); ++i) {
2406             document()->addMutationObserverTypes(registry->at(i)->mutationTypes());
2407         }
2408     }
2409
2410     if (HashSet<MutationObserverRegistration*>* transientRegistry = transientMutationObserverRegistry()) {
2411         for (HashSet<MutationObserverRegistration*>::iterator iter = transientRegistry->begin(); iter != transientRegistry->end(); ++iter) {
2412             document()->addMutationObserverTypes((*iter)->mutationTypes());
2413         }
2414     }
2415 #endif
2416 }
2417
2418 #if ENABLE(SVG)
2419 static inline HashSet<SVGElementInstance*> instancesForSVGElement(Node* node)
2420 {
2421     HashSet<SVGElementInstance*> instances;
2422  
2423     ASSERT(node);
2424     if (!node->isSVGElement() || node->shadowTreeRootNode())
2425         return HashSet<SVGElementInstance*>();
2426
2427     SVGElement* element = static_cast<SVGElement*>(node);
2428     if (!element->isStyled())
2429         return HashSet<SVGElementInstance*>();
2430
2431     SVGStyledElement* styledElement = static_cast<SVGStyledElement*>(element);
2432     ASSERT(!styledElement->instanceUpdatesBlocked());
2433
2434     return styledElement->instancesForElement();
2435 }
2436 #endif
2437
2438 static inline bool tryAddEventListener(Node* targetNode, const AtomicString& eventType, PassRefPtr<EventListener> listener, bool useCapture)
2439 {
2440     if (!targetNode->EventTarget::addEventListener(eventType, listener, useCapture))
2441         return false;
2442
2443     if (Document* document = targetNode->document()) {
2444         document->addListenerTypeIfNeeded(eventType);
2445         if (eventType == eventNames().mousewheelEvent)
2446             document->didAddWheelEventHandler();
2447         else if (eventNames().isTouchEventType(eventType))
2448             document->didAddTouchEventHandler();
2449     }
2450         
2451     return true;
2452 }
2453
2454 bool Node::addEventListener(const AtomicString& eventType, PassRefPtr<EventListener> listener, bool useCapture)
2455 {
2456 #if !ENABLE(SVG)
2457     return tryAddEventListener(this, eventType, listener, useCapture);
2458 #else
2459     if (!isSVGElement())
2460         return tryAddEventListener(this, eventType, listener, useCapture);
2461
2462     HashSet<SVGElementInstance*> instances = instancesForSVGElement(this);
2463     if (instances.isEmpty())
2464         return tryAddEventListener(this, eventType, listener, useCapture);
2465
2466     RefPtr<EventListener> listenerForRegularTree = listener;
2467     RefPtr<EventListener> listenerForShadowTree = listenerForRegularTree;
2468
2469     // Add event listener to regular DOM element
2470     if (!tryAddEventListener(this, eventType, listenerForRegularTree.release(), useCapture))
2471         return false;
2472
2473     // Add event listener to all shadow tree DOM element instances
2474     const HashSet<SVGElementInstance*>::const_iterator end = instances.end();
2475     for (HashSet<SVGElementInstance*>::const_iterator it = instances.begin(); it != end; ++it) {
2476         ASSERT((*it)->shadowTreeElement());
2477         ASSERT((*it)->correspondingElement() == this);
2478
2479         RefPtr<EventListener> listenerForCurrentShadowTreeElement = listenerForShadowTree;
2480         bool result = tryAddEventListener((*it)->shadowTreeElement(), eventType, listenerForCurrentShadowTreeElement.release(), useCapture);
2481         ASSERT_UNUSED(result, result);
2482     }
2483
2484     return true;
2485 #endif
2486 }
2487
2488 static inline bool tryRemoveEventListener(Node* targetNode, const AtomicString& eventType, EventListener* listener, bool useCapture)
2489 {
2490     if (!targetNode->EventTarget::removeEventListener(eventType, listener, useCapture))
2491         return false;
2492
2493     // FIXME: Notify Document that the listener has vanished. We need to keep track of a number of
2494     // listeners for each type, not just a bool - see https://bugs.webkit.org/show_bug.cgi?id=33861
2495     if (Document* document = targetNode->document()) {
2496         if (eventType == eventNames().mousewheelEvent)
2497             document->didRemoveWheelEventHandler();
2498         else if (eventNames().isTouchEventType(eventType))
2499             document->didRemoveTouchEventHandler();
2500     }
2501     
2502     return true;
2503 }
2504
2505 bool Node::removeEventListener(const AtomicString& eventType, EventListener* listener, bool useCapture)
2506 {
2507 #if !ENABLE(SVG)
2508     return tryRemoveEventListener(this, eventType, listener, useCapture);
2509 #else
2510     if (!isSVGElement())
2511         return tryRemoveEventListener(this, eventType, listener, useCapture);
2512
2513     HashSet<SVGElementInstance*> instances = instancesForSVGElement(this);
2514     if (instances.isEmpty())
2515         return tryRemoveEventListener(this, eventType, listener, useCapture);
2516
2517     // EventTarget::removeEventListener creates a PassRefPtr around the given EventListener
2518     // object when creating a temporary RegisteredEventListener object used to look up the
2519     // event listener in a cache. If we want to be able to call removeEventListener() multiple
2520     // times on different nodes, we have to delay its immediate destruction, which would happen
2521     // after the first call below.
2522     RefPtr<EventListener> protector(listener);
2523
2524     // Remove event listener from regular DOM element
2525     if (!tryRemoveEventListener(this, eventType, listener, useCapture))
2526         return false;
2527
2528     // Remove event listener from all shadow tree DOM element instances
2529     const HashSet<SVGElementInstance*>::const_iterator end = instances.end();
2530     for (HashSet<SVGElementInstance*>::const_iterator it = instances.begin(); it != end; ++it) {
2531         ASSERT((*it)->correspondingElement() == this);
2532
2533         SVGElement* shadowTreeElement = (*it)->shadowTreeElement();
2534         ASSERT(shadowTreeElement);
2535
2536         if (tryRemoveEventListener(shadowTreeElement, eventType, listener, useCapture))
2537             continue;
2538
2539         // This case can only be hit for event listeners created from markup
2540         ASSERT(listener->wasCreatedFromMarkup());
2541
2542         // If the event listener 'listener' has been created from markup and has been fired before
2543         // then JSLazyEventListener::parseCode() has been called and m_jsFunction of that listener
2544         // has been created (read: it's not 0 anymore). During shadow tree creation, the event
2545         // listener DOM attribute has been cloned, and another event listener has been setup in
2546         // the shadow tree. If that event listener has not been used yet, m_jsFunction is still 0,
2547         // and tryRemoveEventListener() above will fail. Work around that very seldom problem.
2548         EventTargetData* data = shadowTreeElement->eventTargetData();
2549         ASSERT(data);
2550
2551         data->eventListenerMap.removeFirstEventListenerCreatedFromMarkup(eventType);
2552     }
2553
2554     return true;
2555 #endif
2556 }
2557
2558 EventTargetData* Node::eventTargetData()
2559 {
2560     return hasRareData() ? rareData()->eventTargetData() : 0;
2561 }
2562
2563 EventTargetData* Node::ensureEventTargetData()
2564 {
2565     return ensureRareData()->ensureEventTargetData();
2566 }
2567
2568 #if ENABLE(MUTATION_OBSERVERS)
2569 Vector<OwnPtr<MutationObserverRegistration> >* Node::mutationObserverRegistry()
2570 {
2571     return hasRareData() ? rareData()->mutationObserverRegistry() : 0;
2572 }
2573
2574 HashSet<MutationObserverRegistration*>* Node::transientMutationObserverRegistry()
2575 {
2576     return hasRareData() ? rareData()->transientMutationObserverRegistry() : 0;
2577 }
2578
2579 void Node::collectMatchingObserversForMutation(HashMap<WebKitMutationObserver*, MutationRecordDeliveryOptions>& observers, Node* fromNode, WebKitMutationObserver::MutationType type, const QualifiedName* attributeName)
2580 {
2581     ASSERT((type == WebKitMutationObserver::Attributes && attributeName) || !attributeName);
2582     if (Vector<OwnPtr<MutationObserverRegistration> >* registry = fromNode->mutationObserverRegistry()) {
2583         const size_t size = registry->size();
2584         for (size_t i = 0; i < size; ++i) {
2585             MutationObserverRegistration* registration = registry->at(i).get();
2586             if (registration->shouldReceiveMutationFrom(this, type, attributeName)) {
2587                 MutationRecordDeliveryOptions deliveryOptions = registration->deliveryOptions();
2588                 HashMap<WebKitMutationObserver*, MutationRecordDeliveryOptions>::AddResult result = observers.add(registration->observer(), deliveryOptions);
2589                 if (!result.isNewEntry)
2590                     result.iterator->second |= deliveryOptions;
2591
2592             }
2593         }
2594     }
2595
2596     if (HashSet<MutationObserverRegistration*>* transientRegistry = fromNode->transientMutationObserverRegistry()) {
2597         for (HashSet<MutationObserverRegistration*>::iterator iter = transientRegistry->begin(); iter != transientRegistry->end(); ++iter) {
2598             MutationObserverRegistration* registration = *iter;
2599             if (registration->shouldReceiveMutationFrom(this, type, attributeName)) {
2600                 MutationRecordDeliveryOptions deliveryOptions = registration->deliveryOptions();
2601                 HashMap<WebKitMutationObserver*, MutationRecordDeliveryOptions>::AddResult result = observers.add(registration->observer(), deliveryOptions);
2602                 if (!result.isNewEntry)
2603                     result.iterator->second |= deliveryOptions;
2604             }
2605         }
2606     }
2607 }
2608
2609 void Node::getRegisteredMutationObserversOfType(HashMap<WebKitMutationObserver*, MutationRecordDeliveryOptions>& observers, WebKitMutationObserver::MutationType type, const QualifiedName* attributeName)
2610 {
2611     ASSERT((type == WebKitMutationObserver::Attributes && attributeName) || !attributeName);
2612     collectMatchingObserversForMutation(observers, this, type, attributeName);
2613     for (Node* node = parentNode(); node; node = node->parentNode())
2614         collectMatchingObserversForMutation(observers, node, type, attributeName);
2615 }
2616
2617 MutationObserverRegistration* Node::registerMutationObserver(PassRefPtr<WebKitMutationObserver> observer)
2618 {
2619     Vector<OwnPtr<MutationObserverRegistration> >* registry = ensureRareData()->ensureMutationObserverRegistry();
2620     for (size_t i = 0; i < registry->size(); ++i) {
2621         if (registry->at(i)->observer() == observer)
2622             return registry->at(i).get();
2623     }
2624
2625     OwnPtr<MutationObserverRegistration> registration = MutationObserverRegistration::create(observer, this);
2626     MutationObserverRegistration* registrationPtr = registration.get();
2627     registry->append(registration.release());
2628     return registrationPtr;
2629 }
2630
2631 void Node::unregisterMutationObserver(MutationObserverRegistration* registration)
2632 {
2633     Vector<OwnPtr<MutationObserverRegistration> >* registry = mutationObserverRegistry();
2634     ASSERT(registry);
2635     if (!registry)
2636         return;
2637
2638     size_t index = registry->find(registration);
2639     ASSERT(index != notFound);
2640     if (index == notFound)
2641         return;
2642
2643     registry->remove(index);
2644 }
2645
2646 void Node::registerTransientMutationObserver(MutationObserverRegistration* registration)
2647 {
2648     ensureRareData()->ensureTransientMutationObserverRegistry()->add(registration);
2649 }
2650
2651 void Node::unregisterTransientMutationObserver(MutationObserverRegistration* registration)
2652 {
2653     HashSet<MutationObserverRegistration*>* transientRegistry = transientMutationObserverRegistry();
2654     ASSERT(transientRegistry);
2655     if (!transientRegistry)
2656         return;
2657
2658     ASSERT(transientRegistry->contains(registration));
2659     transientRegistry->remove(registration);
2660 }
2661
2662 void Node::notifyMutationObserversNodeWillDetach()
2663 {
2664     if (!document()->hasMutationObservers())
2665         return;
2666
2667     for (Node* node = parentNode(); node; node = node->parentNode()) {
2668         if (Vector<OwnPtr<MutationObserverRegistration> >* registry = node->mutationObserverRegistry()) {
2669             const size_t size = registry->size();
2670             for (size_t i = 0; i < size; ++i)
2671                 registry->at(i)->observedSubtreeNodeWillDetach(this);
2672         }
2673
2674         if (HashSet<MutationObserverRegistration*>* transientRegistry = node->transientMutationObserverRegistry()) {
2675             for (HashSet<MutationObserverRegistration*>::iterator iter = transientRegistry->begin(); iter != transientRegistry->end(); ++iter)
2676                 (*iter)->observedSubtreeNodeWillDetach(this);
2677         }
2678     }
2679 }
2680 #endif // ENABLE(MUTATION_OBSERVERS)
2681
2682 #if ENABLE(STYLE_SCOPED)
2683 bool Node::hasScopedHTMLStyleChild() const
2684 {
2685     return hasRareData() && rareData()->hasScopedHTMLStyleChild();
2686 }
2687
2688 size_t Node::numberOfScopedHTMLStyleChildren() const
2689 {
2690     return hasRareData() ? rareData()->numberOfScopedHTMLStyleChildren() : 0;
2691 }
2692
2693 void Node::registerScopedHTMLStyleChild()
2694 {
2695     ensureRareData()->registerScopedHTMLStyleChild();
2696 }
2697
2698 void Node::unregisterScopedHTMLStyleChild()
2699 {
2700     ASSERT(hasRareData());
2701     if (hasRareData())
2702         rareData()->unregisterScopedHTMLStyleChild();
2703 }
2704 #else
2705 bool Node::hasScopedHTMLStyleChild() const
2706 {
2707     return 0;
2708 }
2709
2710 size_t Node::numberOfScopedHTMLStyleChildren() const
2711 {
2712     return 0;
2713 }
2714 #endif
2715
2716 void Node::handleLocalEvents(Event* event)
2717 {
2718     if (!hasRareData() || !rareData()->eventTargetData())
2719         return;
2720
2721     if (disabled() && event->isMouseEvent())
2722         return;
2723
2724     fireEventListeners(event);
2725 }
2726
2727 void Node::dispatchScopedEvent(PassRefPtr<Event> event)
2728 {
2729     dispatchScopedEventDispatchMediator(EventDispatchMediator::create(event));
2730 }
2731
2732 void Node::dispatchScopedEventDispatchMediator(PassRefPtr<EventDispatchMediator> eventDispatchMediator)
2733 {
2734     EventDispatcher::dispatchScopedEvent(this, eventDispatchMediator);
2735 }
2736
2737 bool Node::dispatchEvent(PassRefPtr<Event> event)
2738 {
2739     return EventDispatcher::dispatchEvent(this, EventDispatchMediator::create(event));
2740 }
2741
2742 void Node::dispatchRegionLayoutUpdateEvent()
2743 {
2744     ASSERT(!eventDispatchForbidden());
2745
2746     if (!document()->hasListenerType(Document::REGIONLAYOUTUPDATE_LISTENER))
2747         return;
2748
2749     dispatchScopedEvent(UIEvent::create(eventNames().webkitRegionLayoutUpdateEvent, true, true, document()->defaultView(), 0));
2750 }
2751
2752 void Node::dispatchSubtreeModifiedEvent()
2753 {
2754     if (isInShadowTree())
2755         return;
2756
2757     ASSERT(!eventDispatchForbidden());
2758
2759     if (!document()->hasListenerType(Document::DOMSUBTREEMODIFIED_LISTENER))
2760         return;
2761
2762     dispatchScopedEvent(MutationEvent::create(eventNames().DOMSubtreeModifiedEvent, true));
2763 }
2764
2765 void Node::dispatchFocusInEvent(const AtomicString& eventType, PassRefPtr<Node> oldFocusedNode)
2766 {
2767     ASSERT(!eventDispatchForbidden());
2768     ASSERT(eventType == eventNames().focusinEvent || eventType == eventNames().DOMFocusInEvent);
2769     dispatchScopedEventDispatchMediator(FocusInEventDispatchMediator::create(UIEvent::create(eventType, true, false, document()->defaultView(), 0), oldFocusedNode));
2770 }
2771
2772 void Node::dispatchFocusOutEvent(const AtomicString& eventType, PassRefPtr<Node> newFocusedNode)
2773 {
2774     ASSERT(!eventDispatchForbidden());
2775     ASSERT(eventType == eventNames().focusoutEvent || eventType == eventNames().DOMFocusOutEvent);
2776     dispatchScopedEventDispatchMediator(FocusOutEventDispatchMediator::create(UIEvent::create(eventType, true, false, document()->defaultView(), 0), newFocusedNode));
2777 }
2778
2779 void Node::dispatchDOMActivateEvent(int detail, PassRefPtr<Event> underlyingEvent)
2780 {
2781     ASSERT(!eventDispatchForbidden());
2782     RefPtr<UIEvent> event = UIEvent::create(eventNames().DOMActivateEvent, true, true, document()->defaultView(), detail);
2783     event->setUnderlyingEvent(underlyingEvent);
2784     dispatchScopedEvent(event.release());
2785 }
2786
2787 bool Node::dispatchKeyEvent(const PlatformKeyboardEvent& event)
2788 {
2789     return EventDispatcher::dispatchEvent(this, KeyboardEventDispatchMediator::create(KeyboardEvent::create(event, document()->defaultView())));
2790 }
2791
2792 bool Node::dispatchMouseEvent(const PlatformMouseEvent& event, const AtomicString& eventType,
2793     int detail, Node* relatedTarget)
2794 {
2795     return EventDispatcher::dispatchEvent(this, MouseEventDispatchMediator::create(MouseEvent::create(eventType, document()->defaultView(), event, detail, relatedTarget)));
2796 }
2797
2798 void Node::dispatchSimulatedClick(PassRefPtr<Event> event, bool sendMouseEvents, bool showPressedLook)
2799 {
2800     EventDispatcher::dispatchSimulatedClick(this, event, sendMouseEvents, showPressedLook);
2801 }
2802
2803 bool Node::dispatchBeforeLoadEvent(const String& sourceURL)
2804 {
2805     if (!document()->hasListenerType(Document::BEFORELOAD_LISTENER))
2806         return true;
2807
2808     RefPtr<Node> protector(this);
2809     RefPtr<BeforeLoadEvent> beforeLoadEvent = BeforeLoadEvent::create(sourceURL);
2810     dispatchEvent(beforeLoadEvent.get());
2811     return !beforeLoadEvent->defaultPrevented();
2812 }
2813
2814 bool Node::dispatchWheelEvent(const PlatformWheelEvent& event)
2815 {
2816     return EventDispatcher::dispatchEvent(this, WheelEventDispatchMediator::create(event, document()->defaultView()));
2817 }
2818
2819 void Node::dispatchFocusEvent(PassRefPtr<Node> oldFocusedNode)
2820 {
2821     if (document()->page())
2822         document()->page()->chrome()->client()->elementDidFocus(this);
2823     
2824     EventDispatcher::dispatchEvent(this, FocusEventDispatchMediator::create(oldFocusedNode));
2825 }
2826
2827 void Node::dispatchBlurEvent(PassRefPtr<Node> newFocusedNode)
2828 {
2829     if (document()->page())
2830         document()->page()->chrome()->client()->elementDidBlur(this);
2831
2832     EventDispatcher::dispatchEvent(this, BlurEventDispatchMediator::create(newFocusedNode));
2833 }
2834
2835 void Node::dispatchChangeEvent()
2836 {
2837     dispatchEvent(Event::create(eventNames().changeEvent, true, false));
2838 }
2839
2840 void Node::dispatchInputEvent()
2841 {
2842     dispatchEvent(Event::create(eventNames().inputEvent, true, false));
2843 }
2844
2845 bool Node::disabled() const
2846 {
2847     return false;
2848 }
2849
2850 void Node::defaultEventHandler(Event* event)
2851 {
2852     if (event->target() != this)
2853         return;
2854     const AtomicString& eventType = event->type();
2855     if (eventType == eventNames().keydownEvent || eventType == eventNames().keypressEvent) {
2856         if (event->isKeyboardEvent())
2857             if (Frame* frame = document()->frame())
2858                 frame->eventHandler()->defaultKeyboardEventHandler(static_cast<KeyboardEvent*>(event));
2859     } else if (eventType == eventNames().clickEvent) {
2860         int detail = event->isUIEvent() ? static_cast<UIEvent*>(event)->detail() : 0;
2861         dispatchDOMActivateEvent(detail, event);
2862 #if ENABLE(CONTEXT_MENUS)
2863     } else if (eventType == eventNames().contextmenuEvent) {
2864         if (Frame* frame = document()->frame())
2865             if (Page* page = frame->page())
2866                 page->contextMenuController()->handleContextMenuEvent(event);
2867 #endif
2868     } else if (eventType == eventNames().textInputEvent) {
2869         if (event->hasInterface(eventNames().interfaceForTextEvent))
2870             if (Frame* frame = document()->frame())
2871                 frame->eventHandler()->defaultTextInputEventHandler(static_cast<TextEvent*>(event));
2872 #if ENABLE(PAN_SCROLLING)
2873     } else if (eventType == eventNames().mousedownEvent && event->isMouseEvent()) {
2874         MouseEvent* mouseEvent = static_cast<MouseEvent*>(event);
2875         if (mouseEvent->button() == MiddleButton) {
2876             if (enclosingLinkEventParentOrSelf())
2877                 return;
2878
2879             RenderObject* renderer = this->renderer();
2880             while (renderer && (!renderer->isBox() || !toRenderBox(renderer)->canBeScrolledAndHasScrollableArea()))
2881                 renderer = renderer->parent();
2882
2883             if (renderer) {
2884                 if (Frame* frame = document()->frame())
2885                     frame->eventHandler()->startPanScrolling(renderer);
2886             }
2887         }
2888 #endif
2889     } else if (eventType == eventNames().mousewheelEvent && event->hasInterface(eventNames().interfaceForWheelEvent)) {
2890         WheelEvent* wheelEvent = static_cast<WheelEvent*>(event);
2891         
2892         // If we don't have a renderer, send the wheel event to the first node we find with a renderer.
2893         // This is needed for <option> and <optgroup> elements so that <select>s get a wheel scroll.
2894         Node* startNode = this;
2895         while (startNode && !startNode->renderer())
2896             startNode = startNode->parentOrHostNode();
2897         
2898         if (startNode && startNode->renderer())
2899             if (Frame* frame = document()->frame())
2900                 frame->eventHandler()->defaultWheelEventHandler(startNode, wheelEvent);
2901     } else if (event->type() == eventNames().webkitEditableContentChangedEvent) {
2902         dispatchInputEvent();
2903     }
2904 }
2905
2906 #if ENABLE(MICRODATA)
2907 DOMSettableTokenList* Node::itemProp()
2908 {
2909     return ensureRareData()->itemProp();
2910 }
2911
2912 void Node::setItemProp(const String& value)
2913 {
2914     ensureRareData()->setItemProp(value);
2915 }
2916
2917 DOMSettableTokenList* Node::itemRef()
2918 {
2919     return ensureRareData()->itemRef();
2920 }
2921
2922 void Node::setItemRef(const String& value)
2923 {
2924     ensureRareData()->setItemRef(value);
2925 }
2926
2927 DOMSettableTokenList* Node::itemType()
2928 {
2929     return ensureRareData()->itemType();
2930 }
2931
2932 void Node::setItemType(const String& value)
2933 {
2934     ensureRareData()->setItemType(value);
2935 }
2936
2937 HTMLPropertiesCollection* Node::properties()
2938 {
2939     return ensureRareData()->properties(this);
2940 }
2941 #endif
2942
2943 void NodeRareData::createNodeLists(Node* node)
2944 {
2945     ASSERT(node);
2946     setNodeLists(NodeListsNodeData::create());
2947     if (TreeScope* treeScope = node->treeScope())
2948         treeScope->addNodeListCache();
2949 }
2950
2951 void NodeRareData::clearChildNodeListCache()
2952 {
2953     if (m_childNodeList)
2954         m_childNodeList->invalidateCache();
2955 }
2956
2957 PassRefPtr<RadioNodeList> Node::radioNodeList(const AtomicString& name)
2958 {
2959     ASSERT(hasTagName(formTag));
2960
2961     NodeListsNodeData* nodeLists = ensureRareData()->ensureNodeLists(this);
2962
2963     NodeListsNodeData::RadioNodeListCache::AddResult result = nodeLists->m_radioNodeListCache.add(name, 0);
2964     if (!result.isNewEntry)
2965         return PassRefPtr<RadioNodeList>(result.iterator->second);
2966
2967     RefPtr<RadioNodeList> list = RadioNodeList::create(name, toElement(this));
2968     result.iterator->second = list.get();
2969     return list.release();
2970 }
2971
2972 void Node::removeCachedRadioNodeList(RadioNodeList* list, const AtomicString& name)
2973 {
2974     ASSERT(rareData());
2975     ASSERT(rareData()->nodeLists());
2976
2977     NodeListsNodeData* data = rareData()->nodeLists();
2978     ASSERT_UNUSED(list, list == data->m_radioNodeListCache.get(name));
2979     data->m_radioNodeListCache.remove(name);
2980 }
2981
2982 } // namespace WebCore
2983
2984 #ifndef NDEBUG
2985
2986 void showTree(const WebCore::Node* node)
2987 {
2988     if (node)
2989         node->showTreeForThis();
2990 }
2991
2992 #endif