<https://webkit.org/b/119536> Refactor highestEditableRoot to avoid a redundant call...
[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 "ContainerNodeAlgorithms.h"
44 #include "ContextMenuController.h"
45 #include "DOMImplementation.h"
46 #include "DOMSettableTokenList.h"
47 #include "Document.h"
48 #include "DocumentFragment.h"
49 #include "DocumentType.h"
50 #include "Element.h"
51 #include "ElementRareData.h"
52 #include "ElementTraversal.h"
53 #include "Event.h"
54 #include "EventContext.h"
55 #include "EventDispatchMediator.h"
56 #include "EventDispatcher.h"
57 #include "EventException.h"
58 #include "EventHandler.h"
59 #include "EventListener.h"
60 #include "EventNames.h"
61 #include "ExceptionCode.h"
62 #include "ExceptionCodePlaceholder.h"
63 #include "FlowThreadController.h"
64 #include "Frame.h"
65 #include "FrameView.h"
66 #include "HTMLElement.h"
67 #include "HTMLFrameOwnerElement.h"
68 #include "HTMLImageElement.h"
69 #include "HTMLNames.h"
70 #include "HTMLStyleElement.h"
71 #include "InsertionPoint.h"
72 #include "InspectorCounters.h"
73 #include "KeyboardEvent.h"
74 #include "LabelsNodeList.h"
75 #include "LiveNodeList.h"
76 #include "Logging.h"
77 #include "MouseEvent.h"
78 #include "MutationEvent.h"
79 #include "NameNodeList.h"
80 #include "NamedNodeMap.h"
81 #include "NodeRareData.h"
82 #include "NodeRenderingContext.h"
83 #include "NodeTraversal.h"
84 #include "Page.h"
85 #include "PlatformMouseEvent.h"
86 #include "PlatformWheelEvent.h"
87 #include "ProcessingInstruction.h"
88 #include "ProgressEvent.h"
89 #include "RadioNodeList.h"
90 #include "RegisteredEventListener.h"
91 #include "RenderBlock.h"
92 #include "RenderBox.h"
93 #include "RenderTextControl.h"
94 #include "RenderView.h"
95 #include "ScopedEventQueue.h"
96 #include "SelectorQuery.h"
97 #include "Settings.h"
98 #include "ShadowRoot.h"
99 #include "StaticNodeList.h"
100 #include "StorageEvent.h"
101 #include "StyleResolver.h"
102 #include "TagNodeList.h"
103 #include "TemplateContentDocumentFragment.h"
104 #include "Text.h"
105 #include "TextEvent.h"
106 #include "TouchEvent.h"
107 #include "TreeScopeAdopter.h"
108 #include "UIEvent.h"
109 #include "UIEventWithKeyState.h"
110 #include "WheelEvent.h"
111 #include "WindowEventContext.h"
112 #include "XMLNames.h"
113 #include "htmlediting.h"
114 #include <wtf/HashSet.h>
115 #include <wtf/PassOwnPtr.h>
116 #include <wtf/RefCountedLeakCounter.h>
117 #include <wtf/Vector.h>
118 #include <wtf/text/CString.h>
119 #include <wtf/text/StringBuilder.h>
120
121 #ifndef NDEBUG
122 #include "RenderLayer.h"
123 #endif
124
125 #if ENABLE(GESTURE_EVENTS)
126 #include "GestureEvent.h"
127 #endif
128
129 #if ENABLE(INDIE_UI)
130 #include "UIRequestEvent.h"
131 #endif
132
133 #if ENABLE(INSPECTOR)
134 #include "InspectorController.h"
135 #endif
136
137 #include <runtime/VM.h>
138 #include <runtime/Operations.h>
139
140 using namespace std;
141
142 namespace WebCore {
143
144 using namespace HTMLNames;
145
146 bool Node::isSupported(const String& feature, const String& version)
147 {
148     return DOMImplementation::hasFeature(feature, version);
149 }
150
151 #if DUMP_NODE_STATISTICS
152 static HashSet<Node*> liveNodeSet;
153 #endif
154
155 void Node::dumpStatistics()
156 {
157 #if DUMP_NODE_STATISTICS
158     size_t nodesWithRareData = 0;
159
160     size_t elementNodes = 0;
161     size_t attrNodes = 0;
162     size_t textNodes = 0;
163     size_t cdataNodes = 0;
164     size_t commentNodes = 0;
165     size_t entityReferenceNodes = 0;
166     size_t entityNodes = 0;
167     size_t piNodes = 0;
168     size_t documentNodes = 0;
169     size_t docTypeNodes = 0;
170     size_t fragmentNodes = 0;
171     size_t notationNodes = 0;
172     size_t xpathNSNodes = 0;
173     size_t shadowRootNodes = 0;
174
175     HashMap<String, size_t> perTagCount;
176
177     size_t attributes = 0;
178     size_t attributesWithAttr = 0;
179     size_t elementsWithAttributeStorage = 0;
180     size_t elementsWithRareData = 0;
181     size_t elementsWithNamedNodeMap = 0;
182
183     for (HashSet<Node*>::iterator it = liveNodeSet.begin(); it != liveNodeSet.end(); ++it) {
184         Node* node = *it;
185
186         if (node->hasRareData()) {
187             ++nodesWithRareData;
188             if (node->isElementNode()) {
189                 ++elementsWithRareData;
190                 if (toElement(node)->hasNamedNodeMap())
191                     ++elementsWithNamedNodeMap;
192             }
193         }
194
195         switch (node->nodeType()) {
196             case ELEMENT_NODE: {
197                 ++elementNodes;
198
199                 // Tag stats
200                 Element* element = toElement(node);
201                 HashMap<String, size_t>::AddResult result = perTagCount.add(element->tagName(), 1);
202                 if (!result.isNewEntry)
203                     result.iterator->value++;
204
205                 if (ElementData* elementData = element->elementData()) {
206                     attributes += elementData->length();
207                     ++elementsWithAttributeStorage;
208                     for (unsigned i = 0; i < elementData->length(); ++i) {
209                         Attribute& attr = elementData->attributeAt(i);
210                         if (attr.attr())
211                             ++attributesWithAttr;
212                     }
213                 }
214                 break;
215             }
216             case ATTRIBUTE_NODE: {
217                 ++attrNodes;
218                 break;
219             }
220             case TEXT_NODE: {
221                 ++textNodes;
222                 break;
223             }
224             case CDATA_SECTION_NODE: {
225                 ++cdataNodes;
226                 break;
227             }
228             case COMMENT_NODE: {
229                 ++commentNodes;
230                 break;
231             }
232             case ENTITY_REFERENCE_NODE: {
233                 ++entityReferenceNodes;
234                 break;
235             }
236             case ENTITY_NODE: {
237                 ++entityNodes;
238                 break;
239             }
240             case PROCESSING_INSTRUCTION_NODE: {
241                 ++piNodes;
242                 break;
243             }
244             case DOCUMENT_NODE: {
245                 ++documentNodes;
246                 break;
247             }
248             case DOCUMENT_TYPE_NODE: {
249                 ++docTypeNodes;
250                 break;
251             }
252             case DOCUMENT_FRAGMENT_NODE: {
253                 if (node->isShadowRoot())
254                     ++shadowRootNodes;
255                 else
256                     ++fragmentNodes;
257                 break;
258             }
259             case NOTATION_NODE: {
260                 ++notationNodes;
261                 break;
262             }
263             case XPATH_NAMESPACE_NODE: {
264                 ++xpathNSNodes;
265                 break;
266             }
267         }
268     }
269
270     printf("Number of Nodes: %d\n\n", liveNodeSet.size());
271     printf("Number of Nodes with RareData: %zu\n\n", nodesWithRareData);
272
273     printf("NodeType distribution:\n");
274     printf("  Number of Element nodes: %zu\n", elementNodes);
275     printf("  Number of Attribute nodes: %zu\n", attrNodes);
276     printf("  Number of Text nodes: %zu\n", textNodes);
277     printf("  Number of CDATASection nodes: %zu\n", cdataNodes);
278     printf("  Number of Comment nodes: %zu\n", commentNodes);
279     printf("  Number of EntityReference nodes: %zu\n", entityReferenceNodes);
280     printf("  Number of Entity nodes: %zu\n", entityNodes);
281     printf("  Number of ProcessingInstruction nodes: %zu\n", piNodes);
282     printf("  Number of Document nodes: %zu\n", documentNodes);
283     printf("  Number of DocumentType nodes: %zu\n", docTypeNodes);
284     printf("  Number of DocumentFragment nodes: %zu\n", fragmentNodes);
285     printf("  Number of Notation nodes: %zu\n", notationNodes);
286     printf("  Number of XPathNS nodes: %zu\n", xpathNSNodes);
287     printf("  Number of ShadowRoot nodes: %zu\n", shadowRootNodes);
288
289     printf("Element tag name distibution:\n");
290     for (HashMap<String, size_t>::iterator it = perTagCount.begin(); it != perTagCount.end(); ++it)
291         printf("  Number of <%s> tags: %zu\n", it->key.utf8().data(), it->value);
292
293     printf("Attributes:\n");
294     printf("  Number of Attributes (non-Node and Node): %zu [%zu]\n", attributes, sizeof(Attribute));
295     printf("  Number of Attributes with an Attr: %zu\n", attributesWithAttr);
296     printf("  Number of Elements with attribute storage: %zu [%zu]\n", elementsWithAttributeStorage, sizeof(ElementData));
297     printf("  Number of Elements with RareData: %zu\n", elementsWithRareData);
298     printf("  Number of Elements with NamedNodeMap: %zu [%zu]\n", elementsWithNamedNodeMap, sizeof(NamedNodeMap));
299 #endif
300 }
301
302 DEFINE_DEBUG_ONLY_GLOBAL(WTF::RefCountedLeakCounter, nodeCounter, ("WebCoreNode"));
303 DEFINE_DEBUG_ONLY_GLOBAL(HashSet<Node*>, ignoreSet, );
304
305 #ifndef NDEBUG
306 static bool shouldIgnoreLeaks = false;
307 #endif
308
309 void Node::startIgnoringLeaks()
310 {
311 #ifndef NDEBUG
312     shouldIgnoreLeaks = true;
313 #endif
314 }
315
316 void Node::stopIgnoringLeaks()
317 {
318 #ifndef NDEBUG
319     shouldIgnoreLeaks = false;
320 #endif
321 }
322
323 void Node::trackForDebugging()
324 {
325 #ifndef NDEBUG
326     if (shouldIgnoreLeaks)
327         ignoreSet.add(this);
328     else
329         nodeCounter.increment();
330 #endif
331
332 #if DUMP_NODE_STATISTICS
333     liveNodeSet.add(this);
334 #endif
335 }
336
337 Node::~Node()
338 {
339 #ifndef NDEBUG
340     HashSet<Node*>::iterator it = ignoreSet.find(this);
341     if (it != ignoreSet.end())
342         ignoreSet.remove(it);
343     else
344         nodeCounter.decrement();
345 #endif
346
347 #if DUMP_NODE_STATISTICS
348     liveNodeSet.remove(this);
349 #endif
350
351     ASSERT(!renderer());
352
353     if (hasRareData())
354         clearRareData();
355
356     if (!isContainerNode()) {
357         if (Document* document = documentInternal())
358             willBeDeletedFrom(document);
359     }
360
361     if (m_previous)
362         m_previous->setNextSibling(0);
363     if (m_next)
364         m_next->setPreviousSibling(0);
365
366     m_treeScope->guardDeref();
367
368     InspectorCounters::decrementCounter(InspectorCounters::NodeCounter);
369 }
370
371 void Node::willBeDeletedFrom(Document* document)
372 {
373     if (hasEventTargetData()) {
374 #if ENABLE(TOUCH_EVENT_TRACKING)
375         if (document)
376             document->didRemoveEventTargetNode(this);
377 #endif
378         clearEventTargetData();
379     }
380
381     if (document) {
382         if (AXObjectCache* cache = document->existingAXObjectCache())
383             cache->remove(this);
384     }
385 }
386
387 NodeRareData* Node::rareData() const
388 {
389     ASSERT(hasRareData());
390     return static_cast<NodeRareData*>(m_data.m_rareData);
391 }
392
393 NodeRareData& Node::ensureRareData()
394 {
395     if (hasRareData())
396         return *rareData();
397
398     NodeRareData* data;
399     if (isElementNode())
400         data = ElementRareData::create(m_data.m_renderer).leakPtr();
401     else
402         data = NodeRareData::create(m_data.m_renderer).leakPtr();
403     ASSERT(data);
404
405     m_data.m_rareData = data;
406     setFlag(HasRareDataFlag);
407     return *data;
408 }
409
410 void Node::clearRareData()
411 {
412     ASSERT(hasRareData());
413     ASSERT(!transientMutationObserverRegistry() || transientMutationObserverRegistry()->isEmpty());
414
415     RenderObject* renderer = m_data.m_rareData->renderer();
416     if (isElementNode())
417         delete static_cast<ElementRareData*>(m_data.m_rareData);
418     else
419         delete static_cast<NodeRareData*>(m_data.m_rareData);
420     m_data.m_renderer = renderer;
421     clearFlag(HasRareDataFlag);
422 }
423
424 Node* Node::toNode()
425 {
426     return this;
427 }
428
429 HTMLInputElement* Node::toInputElement()
430 {
431     // If one of the below ASSERTs trigger, you are calling this function
432     // directly or indirectly from a constructor or destructor of this object.
433     // Don't do this!
434     ASSERT(!(isHTMLElement() && hasTagName(inputTag)));
435     return 0;
436 }
437
438 String Node::nodeValue() const
439 {
440     return String();
441 }
442
443 void Node::setNodeValue(const String& /*nodeValue*/, ExceptionCode& ec)
444 {
445     // NO_MODIFICATION_ALLOWED_ERR: Raised when the node is readonly
446     if (isReadOnlyNode()) {
447         ec = NO_MODIFICATION_ALLOWED_ERR;
448         return;
449     }
450
451     // By default, setting nodeValue has no effect.
452 }
453
454 PassRefPtr<NodeList> Node::childNodes()
455 {
456     return ensureRareData().ensureNodeLists().ensureChildNodeList(this);
457 }
458
459 Node *Node::lastDescendant() const
460 {
461     Node *n = const_cast<Node *>(this);
462     while (n && n->lastChild())
463         n = n->lastChild();
464     return n;
465 }
466
467 Node* Node::firstDescendant() const
468 {
469     Node *n = const_cast<Node *>(this);
470     while (n && n->firstChild())
471         n = n->firstChild();
472     return n;
473 }
474
475 bool Node::insertBefore(PassRefPtr<Node> newChild, Node* refChild, ExceptionCode& ec, AttachBehavior attachBehavior)
476 {
477     if (!isContainerNode()) {
478         ec = HIERARCHY_REQUEST_ERR;
479         return false;
480     }
481     return toContainerNode(this)->insertBefore(newChild, refChild, ec, attachBehavior);
482 }
483
484 bool Node::replaceChild(PassRefPtr<Node> newChild, Node* oldChild, ExceptionCode& ec, AttachBehavior attachBehavior)
485 {
486     if (!isContainerNode()) {
487         ec = HIERARCHY_REQUEST_ERR;
488         return false;
489     }
490     return toContainerNode(this)->replaceChild(newChild, oldChild, ec, attachBehavior);
491 }
492
493 bool Node::removeChild(Node* oldChild, ExceptionCode& ec)
494 {
495     if (!isContainerNode()) {
496         ec = NOT_FOUND_ERR;
497         return false;
498     }
499     return toContainerNode(this)->removeChild(oldChild, ec);
500 }
501
502 bool Node::appendChild(PassRefPtr<Node> newChild, ExceptionCode& ec, AttachBehavior attachBehavior)
503 {
504     if (!isContainerNode()) {
505         ec = HIERARCHY_REQUEST_ERR;
506         return false;
507     }
508     return toContainerNode(this)->appendChild(newChild, ec, attachBehavior);
509 }
510
511 void Node::remove(ExceptionCode& ec)
512 {
513     if (ContainerNode* parent = parentNode())
514         parent->removeChild(this, ec);
515 }
516
517 void Node::normalize()
518 {
519     // Go through the subtree beneath us, normalizing all nodes. This means that
520     // any two adjacent text nodes are merged and any empty text nodes are removed.
521
522     RefPtr<Node> node = this;
523     while (Node* firstChild = node->firstChild())
524         node = firstChild;
525     while (node) {
526         NodeType type = node->nodeType();
527         if (type == ELEMENT_NODE)
528             toElement(node.get())->normalizeAttributes();
529
530         if (node == this)
531             break;
532
533         if (type != TEXT_NODE) {
534             node = NodeTraversal::nextPostOrder(node.get());
535             continue;
536         }
537
538         RefPtr<Text> text = toText(node.get());
539
540         // Remove empty text nodes.
541         if (!text->length()) {
542             // Care must be taken to get the next node before removing the current node.
543             node = NodeTraversal::nextPostOrder(node.get());
544             text->remove(IGNORE_EXCEPTION);
545             continue;
546         }
547
548         // Merge text nodes.
549         while (Node* nextSibling = node->nextSibling()) {
550             if (nextSibling->nodeType() != TEXT_NODE)
551                 break;
552             RefPtr<Text> nextText = toText(nextSibling);
553
554             // Remove empty text nodes.
555             if (!nextText->length()) {
556                 nextText->remove(IGNORE_EXCEPTION);
557                 continue;
558             }
559
560             // Both non-empty text nodes. Merge them.
561             unsigned offset = text->length();
562             text->appendData(nextText->data(), IGNORE_EXCEPTION);
563             document()->textNodesMerged(nextText.get(), offset);
564             nextText->remove(IGNORE_EXCEPTION);
565         }
566
567         node = NodeTraversal::nextPostOrder(node.get());
568     }
569 }
570
571 const AtomicString& Node::prefix() const
572 {
573     // For nodes other than elements and attributes, the prefix is always null
574     return nullAtom;
575 }
576
577 void Node::setPrefix(const AtomicString& /*prefix*/, ExceptionCode& ec)
578 {
579     // The spec says that for nodes other than elements and attributes, prefix is always null.
580     // It does not say what to do when the user tries to set the prefix on another type of
581     // node, however Mozilla throws a NAMESPACE_ERR exception.
582     ec = NAMESPACE_ERR;
583 }
584
585 const AtomicString& Node::localName() const
586 {
587     return nullAtom;
588 }
589
590 const AtomicString& Node::namespaceURI() const
591 {
592     return nullAtom;
593 }
594
595 bool Node::isContentEditable(UserSelectAllTreatment treatment)
596 {
597     document()->updateStyleIfNeeded();
598     return rendererIsEditable(Editable, treatment);
599 }
600
601 bool Node::isContentRichlyEditable()
602 {
603     document()->updateStyleIfNeeded();
604     return rendererIsEditable(RichlyEditable, UserSelectAllIsAlwaysNonEditable);
605 }
606
607 void Node::inspect()
608 {
609 #if ENABLE(INSPECTOR)
610     if (document() && document()->page())
611         document()->page()->inspectorController()->inspect(this);
612 #endif
613 }
614
615 bool Node::rendererIsEditable(EditableLevel editableLevel, UserSelectAllTreatment treatment) const
616 {
617     if (document()->frame() && document()->frame()->page() && document()->frame()->page()->isEditable() && !containingShadowRoot())
618         return true;
619
620     if (isPseudoElement())
621         return false;
622
623     // Ideally we'd call ASSERT(!needsStyleRecalc()) here, but
624     // ContainerNode::setFocus() calls setNeedsStyleRecalc(), so the assertion
625     // would fire in the middle of Document::setFocusedElement().
626
627     for (const Node* node = this; node; node = node->parentNode()) {
628         if ((node->isHTMLElement() || node->isDocumentNode()) && node->renderer()) {
629 #if ENABLE(USERSELECT_ALL)
630             // Elements with user-select: all style are considered atomic
631             // therefore non editable.
632             if (treatment == UserSelectAllIsAlwaysNonEditable && node->renderer()->style()->userSelect() == SELECT_ALL)
633                 return false;
634 #else
635             UNUSED_PARAM(treatment);
636 #endif
637             switch (node->renderer()->style()->userModify()) {
638             case READ_ONLY:
639                 return false;
640             case READ_WRITE:
641                 return true;
642             case READ_WRITE_PLAINTEXT_ONLY:
643                 return editableLevel != RichlyEditable;
644             }
645             ASSERT_NOT_REACHED();
646             return false;
647         }
648     }
649
650     return false;
651 }
652
653 bool Node::isEditableToAccessibility(EditableLevel editableLevel) const
654 {
655     if (rendererIsEditable(editableLevel))
656         return true;
657
658     // FIXME: Respect editableLevel for ARIA editable elements.
659     if (editableLevel == RichlyEditable)
660         return false;
661
662     ASSERT(document());
663     ASSERT(AXObjectCache::accessibilityEnabled());
664     ASSERT(document()->existingAXObjectCache());
665
666     if (document()) {
667         if (AXObjectCache* cache = document()->existingAXObjectCache())
668             return cache->rootAXEditableElement(this);
669     }
670
671     return false;
672 }
673
674 RenderBox* Node::renderBox() const
675 {
676     RenderObject* renderer = this->renderer();
677     return renderer && renderer->isBox() ? toRenderBox(renderer) : 0;
678 }
679
680 RenderBoxModelObject* Node::renderBoxModelObject() const
681 {
682     RenderObject* renderer = this->renderer();
683     return renderer && renderer->isBoxModelObject() ? toRenderBoxModelObject(renderer) : 0;
684 }
685
686 LayoutRect Node::boundingBox() const
687 {
688     if (renderer())
689         return renderer()->absoluteBoundingBoxRect();
690     return LayoutRect();
691 }
692     
693 LayoutRect Node::renderRect(bool* isReplaced)
694 {    
695     RenderObject* hitRenderer = this->renderer();
696     ASSERT(hitRenderer);
697     RenderObject* renderer = hitRenderer;
698     while (renderer && !renderer->isBody() && !renderer->isRoot()) {
699         if (renderer->isRenderBlock() || renderer->isInlineBlockOrInlineTable() || renderer->isReplaced()) {
700             *isReplaced = renderer->isReplaced();
701             return renderer->absoluteBoundingBoxRect();
702         }
703         renderer = renderer->parent();
704     }
705     return LayoutRect();    
706 }
707
708 void Node::markAncestorsWithChildNeedsStyleRecalc()
709 {
710     for (ContainerNode* p = parentOrShadowHostNode(); p && !p->childNeedsStyleRecalc(); p = p->parentOrShadowHostNode())
711         p->setChildNeedsStyleRecalc();
712
713     if (document()->childNeedsStyleRecalc())
714         document()->scheduleStyleRecalc();
715 }
716
717 void Node::refEventTarget()
718 {
719     ref();
720 }
721
722 void Node::derefEventTarget()
723 {
724     deref();
725 }
726
727 void Node::setNeedsStyleRecalc(StyleChangeType changeType)
728 {
729     ASSERT(changeType != NoStyleChange);
730     if (!attached()) // changed compared to what?
731         return;
732
733     StyleChangeType existingChangeType = styleChangeType();
734     if (changeType > existingChangeType)
735         setStyleChange(changeType);
736
737     if (existingChangeType == NoStyleChange)
738         markAncestorsWithChildNeedsStyleRecalc();
739 }
740
741 unsigned Node::nodeIndex() const
742 {
743     Node *_tempNode = previousSibling();
744     unsigned count=0;
745     for ( count=0; _tempNode; count++ )
746         _tempNode = _tempNode->previousSibling();
747     return count;
748 }
749
750 template<unsigned type>
751 bool shouldInvalidateNodeListCachesForAttr(const unsigned nodeListCounts[], const QualifiedName& attrName)
752 {
753     if (nodeListCounts[type] && LiveNodeListBase::shouldInvalidateTypeOnAttributeChange(static_cast<NodeListInvalidationType>(type), attrName))
754         return true;
755     return shouldInvalidateNodeListCachesForAttr<type + 1>(nodeListCounts, attrName);
756 }
757
758 template<>
759 bool shouldInvalidateNodeListCachesForAttr<numNodeListInvalidationTypes>(const unsigned[], const QualifiedName&)
760 {
761     return false;
762 }
763
764 bool Document::shouldInvalidateNodeListCaches(const QualifiedName* attrName) const
765 {
766     if (attrName)
767         return shouldInvalidateNodeListCachesForAttr<DoNotInvalidateOnAttributeChanges + 1>(m_nodeListCounts, *attrName);
768
769     for (int type = 0; type < numNodeListInvalidationTypes; type++) {
770         if (m_nodeListCounts[type])
771             return true;
772     }
773
774     return false;
775 }
776
777 void Document::invalidateNodeListCaches(const QualifiedName* attrName)
778 {
779     HashSet<LiveNodeListBase*>::iterator end = m_listsInvalidatedAtDocument.end();
780     for (HashSet<LiveNodeListBase*>::iterator it = m_listsInvalidatedAtDocument.begin(); it != end; ++it)
781         (*it)->invalidateCache(attrName);
782 }
783
784 void Node::invalidateNodeListCachesInAncestors(const QualifiedName* attrName, Element* attributeOwnerElement)
785 {
786     if (hasRareData() && (!attrName || isAttributeNode())) {
787         if (NodeListsNodeData* lists = rareData()->nodeLists())
788             lists->clearChildNodeListCache();
789     }
790
791     // Modifications to attributes that are not associated with an Element can't invalidate NodeList caches.
792     if (attrName && !attributeOwnerElement)
793         return;
794
795     if (!document()->shouldInvalidateNodeListCaches(attrName))
796         return;
797
798     document()->invalidateNodeListCaches(attrName);
799
800     for (Node* node = this; node; node = node->parentNode()) {
801         if (!node->hasRareData())
802             continue;
803         NodeRareData* data = node->rareData();
804         if (data->nodeLists())
805             data->nodeLists()->invalidateCaches(attrName);
806     }
807 }
808
809 NodeListsNodeData* Node::nodeLists()
810 {
811     return hasRareData() ? rareData()->nodeLists() : 0;
812 }
813
814 void Node::clearNodeLists()
815 {
816     rareData()->clearNodeLists();
817 }
818
819 void Node::checkSetPrefix(const AtomicString& prefix, ExceptionCode& ec)
820 {
821     // Perform error checking as required by spec for setting Node.prefix. Used by
822     // Element::setPrefix() and Attr::setPrefix()
823
824     if (!prefix.isEmpty() && !Document::isValidName(prefix)) {
825         ec = INVALID_CHARACTER_ERR;
826         return;
827     }
828
829     if (isReadOnlyNode()) {
830         ec = NO_MODIFICATION_ALLOWED_ERR;
831         return;
832     }
833
834     // FIXME: Raise NAMESPACE_ERR if prefix is malformed per the Namespaces in XML specification.
835
836     const AtomicString& nodeNamespaceURI = namespaceURI();
837     if ((nodeNamespaceURI.isEmpty() && !prefix.isEmpty())
838         || (prefix == xmlAtom && nodeNamespaceURI != XMLNames::xmlNamespaceURI)) {
839         ec = NAMESPACE_ERR;
840         return;
841     }
842     // Attribute-specific checks are in Attr::setPrefix().
843 }
844
845 bool Node::isDescendantOf(const Node *other) const
846 {
847     // Return true if other is an ancestor of this, otherwise false
848     if (!other || !other->hasChildNodes() || inDocument() != other->inDocument())
849         return false;
850     if (other->isDocumentNode())
851         return document() == other && !isDocumentNode() && inDocument();
852     for (const ContainerNode* n = parentNode(); n; n = n->parentNode()) {
853         if (n == other)
854             return true;
855     }
856     return false;
857 }
858
859 bool Node::contains(const Node* node) const
860 {
861     if (!node)
862         return false;
863     return this == node || node->isDescendantOf(this);
864 }
865
866 bool Node::containsIncludingShadowDOM(const Node* node) const
867 {
868     for (; node; node = node->parentOrShadowHostNode()) {
869         if (node == this)
870             return true;
871     }
872     return false;
873 }
874
875 bool Node::containsIncludingHostElements(const Node* node) const
876 {
877 #if ENABLE(TEMPLATE_ELEMENT)
878     while (node) {
879         if (node == this)
880             return true;
881         if (node->isDocumentFragment() && static_cast<const DocumentFragment*>(node)->isTemplateContent())
882             node = static_cast<const TemplateContentDocumentFragment*>(node)->host();
883         else
884             node = node->parentOrShadowHostNode();
885     }
886     return false;
887 #else
888     return containsIncludingShadowDOM(node);
889 #endif
890 }
891
892 Node* Node::pseudoAwarePreviousSibling() const
893 {
894     if (parentElement() && !previousSibling()) {
895         Element* parent = parentElement();
896         if (isAfterPseudoElement() && parent->lastChild())
897             return parent->lastChild();
898         if (!isBeforePseudoElement())
899             return parent->pseudoElement(BEFORE);
900     }
901     return previousSibling();
902 }
903
904 Node* Node::pseudoAwareNextSibling() const
905 {
906     if (parentElement() && !nextSibling()) {
907         Element* parent = parentElement();
908         if (isBeforePseudoElement() && parent->firstChild())
909             return parent->firstChild();
910         if (!isAfterPseudoElement())
911             return parent->pseudoElement(AFTER);
912     }
913     return nextSibling();
914 }
915
916 Node* Node::pseudoAwareFirstChild() const
917 {
918     if (isElementNode()) {
919         const Element* currentElement = toElement(this);
920         Node* first = currentElement->pseudoElement(BEFORE);
921         if (first)
922             return first;
923         first = currentElement->firstChild();
924         if (!first)
925             first = currentElement->pseudoElement(AFTER);
926         return first;
927     }
928
929     return firstChild();
930 }
931
932 Node* Node::pseudoAwareLastChild() const
933 {
934     if (isElementNode()) {
935         const Element* currentElement = toElement(this);
936         Node* last = currentElement->pseudoElement(AFTER);
937         if (last)
938             return last;
939         last = currentElement->lastChild();
940         if (!last)
941             last = currentElement->pseudoElement(BEFORE);
942         return last;
943     }
944
945     return lastChild();
946 }
947
948 ContainerNode* Node::parentNodeForRenderingAndStyle()
949 {
950     return NodeRenderingContext(this).parentNodeForRenderingAndStyle();
951 }
952
953 RenderStyle* Node::virtualComputedStyle(PseudoId pseudoElementSpecifier)
954 {
955     return parentOrShadowHostNode() ? parentOrShadowHostNode()->computedStyle(pseudoElementSpecifier) : 0;
956 }
957
958 int Node::maxCharacterOffset() const
959 {
960     ASSERT_NOT_REACHED();
961     return 0;
962 }
963
964 // FIXME: Shouldn't these functions be in the editing code?  Code that asks questions about HTML in the core DOM class
965 // is obviously misplaced.
966 bool Node::canStartSelection() const
967 {
968     if (rendererIsEditable())
969         return true;
970
971     if (renderer()) {
972         RenderStyle* style = renderer()->style();
973         // We allow selections to begin within an element that has -webkit-user-select: none set,
974         // but if the element is draggable then dragging should take priority over selection.
975         if (style->userDrag() == DRAG_ELEMENT && style->userSelect() == SELECT_NONE)
976             return false;
977     }
978     return parentOrShadowHostNode() ? parentOrShadowHostNode()->canStartSelection() : true;
979 }
980
981 bool Node::isRegisteredWithNamedFlow() const
982 {
983     return document()->renderView()->flowThreadController()->isContentNodeRegisteredWithAnyNamedFlow(this);
984 }
985
986 Element* Node::shadowHost() const
987 {
988     if (ShadowRoot* root = containingShadowRoot())
989         return root->hostElement();
990     return 0;
991 }
992
993 Node* Node::deprecatedShadowAncestorNode() const
994 {
995     if (ShadowRoot* root = containingShadowRoot())
996         return root->hostElement();
997
998     return const_cast<Node*>(this);
999 }
1000
1001 ShadowRoot* Node::containingShadowRoot() const
1002 {
1003     ContainerNode* root = treeScope()->rootNode();
1004     return root && root->isShadowRoot() ? toShadowRoot(root) : 0;
1005 }
1006
1007 Node* Node::nonBoundaryShadowTreeRootNode()
1008 {
1009     ASSERT(!isShadowRoot());
1010     Node* root = this;
1011     while (root) {
1012         if (root->isShadowRoot())
1013             return root;
1014         Node* parent = root->parentNodeGuaranteedHostFree();
1015         if (parent && parent->isShadowRoot())
1016             return root;
1017         root = parent;
1018     }
1019     return 0;
1020 }
1021
1022 ContainerNode* Node::nonShadowBoundaryParentNode() const
1023 {
1024     ContainerNode* parent = parentNode();
1025     return parent && !parent->isShadowRoot() ? parent : 0;
1026 }
1027
1028 Element* Node::parentOrShadowHostElement() const
1029 {
1030     ContainerNode* parent = parentOrShadowHostNode();
1031     if (!parent)
1032         return 0;
1033
1034     if (parent->isShadowRoot())
1035         return toShadowRoot(parent)->hostElement();
1036
1037     if (!parent->isElementNode())
1038         return 0;
1039
1040     return toElement(parent);
1041 }
1042
1043 Node* Node::insertionParentForBinding() const
1044 {
1045     return resolveReprojection(this);
1046 }
1047
1048 Node::InsertionNotificationRequest Node::insertedInto(ContainerNode* insertionPoint)
1049 {
1050     ASSERT(insertionPoint->inDocument() || isContainerNode());
1051     if (insertionPoint->inDocument())
1052         setFlag(InDocumentFlag);
1053     if (parentOrShadowHostNode()->isInShadowTree())
1054         setFlag(IsInShadowTreeFlag);
1055     return InsertionDone;
1056 }
1057
1058 void Node::removedFrom(ContainerNode* insertionPoint)
1059 {
1060     ASSERT(insertionPoint->inDocument() || isContainerNode());
1061     if (insertionPoint->inDocument())
1062         clearFlag(InDocumentFlag);
1063     if (isInShadowTree() && !treeScope()->rootNode()->isShadowRoot())
1064         clearFlag(IsInShadowTreeFlag);
1065 }
1066
1067 bool Node::needsShadowTreeWalkerSlow() const
1068 {
1069     return (isShadowRoot() || (isElementNode() && (isInsertionPoint() || isPseudoElement() || toElement(this)->hasPseudoElements() || toElement(this)->shadowRoot())));
1070 }
1071
1072 bool Node::isRootEditableElement() const
1073 {
1074     return rendererIsEditable() && isElementNode() && (!parentNode() || !parentNode()->rendererIsEditable()
1075         || !parentNode()->isElementNode() || hasTagName(bodyTag));
1076 }
1077
1078 Element* Node::rootEditableElement(EditableType editableType) const
1079 {
1080     if (editableType == HasEditableAXRole) {
1081         if (AXObjectCache* cache = document()->existingAXObjectCache())
1082             return const_cast<Element*>(cache->rootAXEditableElement(this));
1083     }
1084     
1085     return rootEditableElement();
1086 }
1087
1088 Element* Node::rootEditableElement() const
1089 {
1090     Element* result = 0;
1091     for (Node* n = const_cast<Node*>(this); n && n->rendererIsEditable(); n = n->parentNode()) {
1092         if (n->isElementNode())
1093             result = toElement(n);
1094         if (n->hasTagName(bodyTag))
1095             break;
1096     }
1097     return result;
1098 }
1099
1100 // FIXME: End of obviously misplaced HTML editing functions.  Try to move these out of Node.
1101
1102 PassRefPtr<NodeList> Node::getElementsByTagName(const AtomicString& localName)
1103 {
1104     if (localName.isNull())
1105         return 0;
1106
1107     if (document()->isHTMLDocument())
1108         return ensureRareData().ensureNodeLists().addCacheWithAtomicName<HTMLTagNodeList>(this, HTMLTagNodeListType, localName);
1109     return ensureRareData().ensureNodeLists().addCacheWithAtomicName<TagNodeList>(this, TagNodeListType, localName);
1110 }
1111
1112 PassRefPtr<NodeList> Node::getElementsByTagNameNS(const AtomicString& namespaceURI, const AtomicString& localName)
1113 {
1114     if (localName.isNull())
1115         return 0;
1116
1117     if (namespaceURI == starAtom)
1118         return getElementsByTagName(localName);
1119
1120     return ensureRareData().ensureNodeLists().addCacheWithQualifiedName(this, namespaceURI.isEmpty() ? nullAtom : namespaceURI, localName);
1121 }
1122
1123 PassRefPtr<NodeList> Node::getElementsByName(const String& elementName)
1124 {
1125     return ensureRareData().ensureNodeLists().addCacheWithAtomicName<NameNodeList>(this, NameNodeListType, elementName);
1126 }
1127
1128 PassRefPtr<NodeList> Node::getElementsByClassName(const String& classNames)
1129 {
1130     return ensureRareData().ensureNodeLists().addCacheWithName<ClassNodeList>(this, ClassNodeListType, classNames);
1131 }
1132
1133 PassRefPtr<RadioNodeList> Node::radioNodeList(const AtomicString& name)
1134 {
1135     ASSERT(hasTagName(formTag) || hasTagName(fieldsetTag));
1136     return ensureRareData().ensureNodeLists().addCacheWithAtomicName<RadioNodeList>(this, RadioNodeListType, name);
1137 }
1138
1139 PassRefPtr<Element> Node::querySelector(const AtomicString& selectors, ExceptionCode& ec)
1140 {
1141     if (selectors.isEmpty()) {
1142         ec = SYNTAX_ERR;
1143         return 0;
1144     }
1145
1146     SelectorQuery* selectorQuery = document()->selectorQueryCache().add(selectors, document(), ec);
1147     if (!selectorQuery)
1148         return 0;
1149     return selectorQuery->queryFirst(this);
1150 }
1151
1152 PassRefPtr<NodeList> Node::querySelectorAll(const AtomicString& selectors, ExceptionCode& ec)
1153 {
1154     if (selectors.isEmpty()) {
1155         ec = SYNTAX_ERR;
1156         return 0;
1157     }
1158
1159     SelectorQuery* selectorQuery = document()->selectorQueryCache().add(selectors, document(), ec);
1160     if (!selectorQuery)
1161         return 0;
1162     return selectorQuery->queryAll(this);
1163 }
1164
1165 Document *Node::ownerDocument() const
1166 {
1167     Document *doc = document();
1168     return doc == this ? 0 : doc;
1169 }
1170
1171 KURL Node::baseURI() const
1172 {
1173     return parentNode() ? parentNode()->baseURI() : KURL();
1174 }
1175
1176 bool Node::isEqualNode(Node* other) const
1177 {
1178     if (!other)
1179         return false;
1180     
1181     NodeType nodeType = this->nodeType();
1182     if (nodeType != other->nodeType())
1183         return false;
1184     
1185     if (nodeName() != other->nodeName())
1186         return false;
1187     
1188     if (localName() != other->localName())
1189         return false;
1190     
1191     if (namespaceURI() != other->namespaceURI())
1192         return false;
1193     
1194     if (prefix() != other->prefix())
1195         return false;
1196     
1197     if (nodeValue() != other->nodeValue())
1198         return false;
1199     
1200     if (isElementNode() && !toElement(this)->hasEquivalentAttributes(toElement(other)))
1201         return false;
1202     
1203     Node* child = firstChild();
1204     Node* otherChild = other->firstChild();
1205     
1206     while (child) {
1207         if (!child->isEqualNode(otherChild))
1208             return false;
1209         
1210         child = child->nextSibling();
1211         otherChild = otherChild->nextSibling();
1212     }
1213     
1214     if (otherChild)
1215         return false;
1216     
1217     if (nodeType == DOCUMENT_TYPE_NODE) {
1218         const DocumentType* documentTypeThis = static_cast<const DocumentType*>(this);
1219         const DocumentType* documentTypeOther = static_cast<const DocumentType*>(other);
1220         
1221         if (documentTypeThis->publicId() != documentTypeOther->publicId())
1222             return false;
1223
1224         if (documentTypeThis->systemId() != documentTypeOther->systemId())
1225             return false;
1226
1227         if (documentTypeThis->internalSubset() != documentTypeOther->internalSubset())
1228             return false;
1229
1230         // FIXME: We don't compare entities or notations because currently both are always empty.
1231     }
1232     
1233     return true;
1234 }
1235
1236 bool Node::isDefaultNamespace(const AtomicString& namespaceURIMaybeEmpty) const
1237 {
1238     const AtomicString& namespaceURI = namespaceURIMaybeEmpty.isEmpty() ? nullAtom : namespaceURIMaybeEmpty;
1239
1240     switch (nodeType()) {
1241         case ELEMENT_NODE: {
1242             const Element* elem = toElement(this);
1243             
1244             if (elem->prefix().isNull())
1245                 return elem->namespaceURI() == namespaceURI;
1246
1247             if (elem->hasAttributes()) {
1248                 for (unsigned i = 0; i < elem->attributeCount(); i++) {
1249                     const Attribute& attribute = elem->attributeAt(i);
1250                     
1251                     if (attribute.localName() == xmlnsAtom)
1252                         return attribute.value() == namespaceURI;
1253                 }
1254             }
1255
1256             if (Element* ancestor = ancestorElement())
1257                 return ancestor->isDefaultNamespace(namespaceURI);
1258
1259             return false;
1260         }
1261         case DOCUMENT_NODE:
1262             if (Element* de = toDocument(this)->documentElement())
1263                 return de->isDefaultNamespace(namespaceURI);
1264             return false;
1265         case ENTITY_NODE:
1266         case NOTATION_NODE:
1267         case DOCUMENT_TYPE_NODE:
1268         case DOCUMENT_FRAGMENT_NODE:
1269             return false;
1270         case ATTRIBUTE_NODE: {
1271             const Attr* attr = static_cast<const Attr*>(this);
1272             if (attr->ownerElement())
1273                 return attr->ownerElement()->isDefaultNamespace(namespaceURI);
1274             return false;
1275         }
1276         default:
1277             if (Element* ancestor = ancestorElement())
1278                 return ancestor->isDefaultNamespace(namespaceURI);
1279             return false;
1280     }
1281 }
1282
1283 String Node::lookupPrefix(const AtomicString &namespaceURI) const
1284 {
1285     // Implemented according to
1286     // http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/namespaces-algorithms.html#lookupNamespacePrefixAlgo
1287     
1288     if (namespaceURI.isEmpty())
1289         return String();
1290     
1291     switch (nodeType()) {
1292         case ELEMENT_NODE:
1293             return lookupNamespacePrefix(namespaceURI, static_cast<const Element *>(this));
1294         case DOCUMENT_NODE:
1295             if (Element* de = toDocument(this)->documentElement())
1296                 return de->lookupPrefix(namespaceURI);
1297             return String();
1298         case ENTITY_NODE:
1299         case NOTATION_NODE:
1300         case DOCUMENT_FRAGMENT_NODE:
1301         case DOCUMENT_TYPE_NODE:
1302             return String();
1303         case ATTRIBUTE_NODE: {
1304             const Attr *attr = static_cast<const Attr *>(this);
1305             if (attr->ownerElement())
1306                 return attr->ownerElement()->lookupPrefix(namespaceURI);
1307             return String();
1308         }
1309         default:
1310             if (Element* ancestor = ancestorElement())
1311                 return ancestor->lookupPrefix(namespaceURI);
1312             return String();
1313     }
1314 }
1315
1316 String Node::lookupNamespaceURI(const String &prefix) const
1317 {
1318     // Implemented according to
1319     // http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/namespaces-algorithms.html#lookupNamespaceURIAlgo
1320     
1321     if (!prefix.isNull() && prefix.isEmpty())
1322         return String();
1323     
1324     switch (nodeType()) {
1325         case ELEMENT_NODE: {
1326             const Element *elem = static_cast<const Element *>(this);
1327             
1328             if (!elem->namespaceURI().isNull() && elem->prefix() == prefix)
1329                 return elem->namespaceURI();
1330             
1331             if (elem->hasAttributes()) {
1332                 for (unsigned i = 0; i < elem->attributeCount(); i++) {
1333                     const Attribute& attribute = elem->attributeAt(i);
1334                     
1335                     if (attribute.prefix() == xmlnsAtom && attribute.localName() == prefix) {
1336                         if (!attribute.value().isEmpty())
1337                             return attribute.value();
1338                         
1339                         return String();
1340                     }
1341                     if (attribute.localName() == xmlnsAtom && prefix.isNull()) {
1342                         if (!attribute.value().isEmpty())
1343                             return attribute.value();
1344                         
1345                         return String();
1346                     }
1347                 }
1348             }
1349             if (Element* ancestor = ancestorElement())
1350                 return ancestor->lookupNamespaceURI(prefix);
1351             return String();
1352         }
1353         case DOCUMENT_NODE:
1354             if (Element* de = toDocument(this)->documentElement())
1355                 return de->lookupNamespaceURI(prefix);
1356             return String();
1357         case ENTITY_NODE:
1358         case NOTATION_NODE:
1359         case DOCUMENT_TYPE_NODE:
1360         case DOCUMENT_FRAGMENT_NODE:
1361             return String();
1362         case ATTRIBUTE_NODE: {
1363             const Attr *attr = static_cast<const Attr *>(this);
1364             
1365             if (attr->ownerElement())
1366                 return attr->ownerElement()->lookupNamespaceURI(prefix);
1367             else
1368                 return String();
1369         }
1370         default:
1371             if (Element* ancestor = ancestorElement())
1372                 return ancestor->lookupNamespaceURI(prefix);
1373             return String();
1374     }
1375 }
1376
1377 String Node::lookupNamespacePrefix(const AtomicString &_namespaceURI, const Element *originalElement) const
1378 {
1379     if (_namespaceURI.isNull())
1380         return String();
1381             
1382     if (originalElement->lookupNamespaceURI(prefix()) == _namespaceURI)
1383         return prefix();
1384     
1385     ASSERT(isElementNode());
1386     const Element* thisElement = toElement(this);
1387     if (thisElement->hasAttributes()) {
1388         for (unsigned i = 0; i < thisElement->attributeCount(); i++) {
1389             const Attribute& attribute = thisElement->attributeAt(i);
1390             
1391             if (attribute.prefix() == xmlnsAtom && attribute.value() == _namespaceURI
1392                 && originalElement->lookupNamespaceURI(attribute.localName()) == _namespaceURI)
1393                 return attribute.localName();
1394         }
1395     }
1396     
1397     if (Element* ancestor = ancestorElement())
1398         return ancestor->lookupNamespacePrefix(_namespaceURI, originalElement);
1399     return String();
1400 }
1401
1402 static void appendTextContent(const Node* node, bool convertBRsToNewlines, bool& isNullString, StringBuilder& content)
1403 {
1404     switch (node->nodeType()) {
1405     case Node::TEXT_NODE:
1406     case Node::CDATA_SECTION_NODE:
1407     case Node::COMMENT_NODE:
1408         isNullString = false;
1409         content.append(static_cast<const CharacterData*>(node)->data());
1410         break;
1411
1412     case Node::PROCESSING_INSTRUCTION_NODE:
1413         isNullString = false;
1414         content.append(static_cast<const ProcessingInstruction*>(node)->data());
1415         break;
1416     
1417     case Node::ELEMENT_NODE:
1418         if (node->hasTagName(brTag) && convertBRsToNewlines) {
1419             isNullString = false;
1420             content.append('\n');
1421             break;
1422         }
1423     // Fall through.
1424     case Node::ATTRIBUTE_NODE:
1425     case Node::ENTITY_NODE:
1426     case Node::ENTITY_REFERENCE_NODE:
1427     case Node::DOCUMENT_FRAGMENT_NODE:
1428         isNullString = false;
1429         for (Node* child = node->firstChild(); child; child = child->nextSibling()) {
1430             if (child->nodeType() == Node::COMMENT_NODE || child->nodeType() == Node::PROCESSING_INSTRUCTION_NODE)
1431                 continue;
1432             appendTextContent(child, convertBRsToNewlines, isNullString, content);
1433         }
1434         break;
1435
1436     case Node::DOCUMENT_NODE:
1437     case Node::DOCUMENT_TYPE_NODE:
1438     case Node::NOTATION_NODE:
1439     case Node::XPATH_NAMESPACE_NODE:
1440         break;
1441     }
1442 }
1443
1444 String Node::textContent(bool convertBRsToNewlines) const
1445 {
1446     StringBuilder content;
1447     bool isNullString = true;
1448     appendTextContent(this, convertBRsToNewlines, isNullString, content);
1449     return isNullString ? String() : content.toString();
1450 }
1451
1452 void Node::setTextContent(const String& text, ExceptionCode& ec)
1453 {           
1454     switch (nodeType()) {
1455         case TEXT_NODE:
1456         case CDATA_SECTION_NODE:
1457         case COMMENT_NODE:
1458         case PROCESSING_INSTRUCTION_NODE:
1459             setNodeValue(text, ec);
1460             return;
1461         case ELEMENT_NODE:
1462         case ATTRIBUTE_NODE:
1463         case ENTITY_NODE:
1464         case ENTITY_REFERENCE_NODE:
1465         case DOCUMENT_FRAGMENT_NODE: {
1466             RefPtr<ContainerNode> container = toContainerNode(this);
1467             ChildListMutationScope mutation(this);
1468             container->removeChildren();
1469             if (!text.isEmpty())
1470                 container->appendChild(document()->createTextNode(text), ec);
1471             return;
1472         }
1473         case DOCUMENT_NODE:
1474         case DOCUMENT_TYPE_NODE:
1475         case NOTATION_NODE:
1476         case XPATH_NAMESPACE_NODE:
1477             // Do nothing.
1478             return;
1479     }
1480     ASSERT_NOT_REACHED();
1481 }
1482
1483 Element* Node::ancestorElement() const
1484 {
1485     // In theory, there can be EntityReference nodes between elements, but this is currently not supported.
1486     for (ContainerNode* n = parentNode(); n; n = n->parentNode()) {
1487         if (n->isElementNode())
1488             return toElement(n);
1489     }
1490     return 0;
1491 }
1492
1493 bool Node::offsetInCharacters() const
1494 {
1495     return false;
1496 }
1497
1498 static inline unsigned short compareDetachedElementsPosition(Node* firstNode, Node* secondNode)
1499 {
1500     // If the 2 nodes are not in the same tree, return the result of adding DOCUMENT_POSITION_DISCONNECTED,
1501     // DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC, and either DOCUMENT_POSITION_PRECEDING or
1502     // DOCUMENT_POSITION_FOLLOWING, with the constraint that this is to be consistent. Whether to return
1503     // DOCUMENT_POSITION_PRECEDING or DOCUMENT_POSITION_FOLLOWING is implemented here via pointer
1504     // comparison.
1505     // See step 3 in http://www.w3.org/TR/2012/WD-dom-20121206/#dom-node-comparedocumentposition
1506     unsigned short direction = (firstNode > secondNode) ? Node::DOCUMENT_POSITION_PRECEDING : Node::DOCUMENT_POSITION_FOLLOWING;
1507     return Node::DOCUMENT_POSITION_DISCONNECTED | Node::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | direction;
1508 }
1509
1510 unsigned short Node::compareDocumentPosition(Node* otherNode)
1511 {
1512     // It is not clear what should be done if |otherNode| is 0.
1513     if (!otherNode)
1514         return DOCUMENT_POSITION_DISCONNECTED;
1515
1516     if (otherNode == this)
1517         return DOCUMENT_POSITION_EQUIVALENT;
1518     
1519     Attr* attr1 = nodeType() == ATTRIBUTE_NODE ? static_cast<Attr*>(this) : 0;
1520     Attr* attr2 = otherNode->nodeType() == ATTRIBUTE_NODE ? static_cast<Attr*>(otherNode) : 0;
1521     
1522     Node* start1 = attr1 ? attr1->ownerElement() : this;
1523     Node* start2 = attr2 ? attr2->ownerElement() : otherNode;
1524     
1525     // If either of start1 or start2 is null, then we are disconnected, since one of the nodes is
1526     // an orphaned attribute node.
1527     if (!start1 || !start2)
1528         return compareDetachedElementsPosition(this, otherNode);
1529
1530     Vector<Node*, 16> chain1;
1531     Vector<Node*, 16> chain2;
1532     if (attr1)
1533         chain1.append(attr1);
1534     if (attr2)
1535         chain2.append(attr2);
1536     
1537     if (attr1 && attr2 && start1 == start2 && start1) {
1538         // We are comparing two attributes on the same node. Crawl our attribute map and see which one we hit first.
1539         Element* owner1 = attr1->ownerElement();
1540         owner1->synchronizeAllAttributes();
1541         unsigned length = owner1->attributeCount();
1542         for (unsigned i = 0; i < length; ++i) {
1543             // If neither of the two determining nodes is a child node and nodeType is the same for both determining nodes, then an 
1544             // implementation-dependent order between the determining nodes is returned. This order is stable as long as no nodes of
1545             // the same nodeType are inserted into or removed from the direct container. This would be the case, for example, 
1546             // when comparing two attributes of the same element, and inserting or removing additional attributes might change 
1547             // the order between existing attributes.
1548             const Attribute& attribute = owner1->attributeAt(i);
1549             if (attr1->qualifiedName() == attribute.name())
1550                 return DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | DOCUMENT_POSITION_FOLLOWING;
1551             if (attr2->qualifiedName() == attribute.name())
1552                 return DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | DOCUMENT_POSITION_PRECEDING;
1553         }
1554         
1555         ASSERT_NOT_REACHED();
1556         return DOCUMENT_POSITION_DISCONNECTED;
1557     }
1558
1559     // If one node is in the document and the other is not, we must be disconnected.
1560     // If the nodes have different owning documents, they must be disconnected.  Note that we avoid
1561     // comparing Attr nodes here, since they return false from inDocument() all the time (which seems like a bug).
1562     if (start1->inDocument() != start2->inDocument() ||
1563         start1->treeScope() != start2->treeScope())
1564         return compareDetachedElementsPosition(this, otherNode);
1565
1566     // We need to find a common ancestor container, and then compare the indices of the two immediate children.
1567     Node* current;
1568     for (current = start1; current; current = current->parentNode())
1569         chain1.append(current);
1570     for (current = start2; current; current = current->parentNode())
1571         chain2.append(current);
1572
1573     unsigned index1 = chain1.size();
1574     unsigned index2 = chain2.size();
1575
1576     // If the two elements don't have a common root, they're not in the same tree.
1577     if (chain1[index1 - 1] != chain2[index2 - 1])
1578         return compareDetachedElementsPosition(this, otherNode);
1579
1580     // Walk the two chains backwards and look for the first difference.
1581     for (unsigned i = min(index1, index2); i; --i) {
1582         Node* child1 = chain1[--index1];
1583         Node* child2 = chain2[--index2];
1584         if (child1 != child2) {
1585             // If one of the children is an attribute, it wins.
1586             if (child1->nodeType() == ATTRIBUTE_NODE)
1587                 return DOCUMENT_POSITION_FOLLOWING;
1588             if (child2->nodeType() == ATTRIBUTE_NODE)
1589                 return DOCUMENT_POSITION_PRECEDING;
1590             
1591             if (!child2->nextSibling())
1592                 return DOCUMENT_POSITION_FOLLOWING;
1593             if (!child1->nextSibling())
1594                 return DOCUMENT_POSITION_PRECEDING;
1595
1596             // Otherwise we need to see which node occurs first.  Crawl backwards from child2 looking for child1.
1597             for (Node* child = child2->previousSibling(); child; child = child->previousSibling()) {
1598                 if (child == child1)
1599                     return DOCUMENT_POSITION_FOLLOWING;
1600             }
1601             return DOCUMENT_POSITION_PRECEDING;
1602         }
1603     }
1604     
1605     // There was no difference between the two parent chains, i.e., one was a subset of the other.  The shorter
1606     // chain is the ancestor.
1607     return index1 < index2 ? 
1608                DOCUMENT_POSITION_FOLLOWING | DOCUMENT_POSITION_CONTAINED_BY :
1609                DOCUMENT_POSITION_PRECEDING | DOCUMENT_POSITION_CONTAINS;
1610 }
1611
1612 FloatPoint Node::convertToPage(const FloatPoint& p) const
1613 {
1614     // If there is a renderer, just ask it to do the conversion
1615     if (renderer())
1616         return renderer()->localToAbsolute(p, UseTransforms);
1617     
1618     // Otherwise go up the tree looking for a renderer
1619     Element *parent = ancestorElement();
1620     if (parent)
1621         return parent->convertToPage(p);
1622
1623     // No parent - no conversion needed
1624     return p;
1625 }
1626
1627 FloatPoint Node::convertFromPage(const FloatPoint& p) const
1628 {
1629     // If there is a renderer, just ask it to do the conversion
1630     if (renderer())
1631         return renderer()->absoluteToLocal(p, UseTransforms);
1632
1633     // Otherwise go up the tree looking for a renderer
1634     Element *parent = ancestorElement();
1635     if (parent)
1636         return parent->convertFromPage(p);
1637
1638     // No parent - no conversion needed
1639     return p;
1640 }
1641
1642 #ifndef NDEBUG
1643
1644 static void appendAttributeDesc(const Node* node, StringBuilder& stringBuilder, const QualifiedName& name, const char* attrDesc)
1645 {
1646     if (!node->isElementNode())
1647         return;
1648
1649     String attr = toElement(node)->getAttribute(name);
1650     if (attr.isEmpty())
1651         return;
1652
1653     stringBuilder.append(attrDesc);
1654     stringBuilder.append(attr);
1655 }
1656
1657 void Node::showNode(const char* prefix) const
1658 {
1659     if (!prefix)
1660         prefix = "";
1661     if (isTextNode()) {
1662         String value = nodeValue();
1663         value.replaceWithLiteral('\\', "\\\\");
1664         value.replaceWithLiteral('\n', "\\n");
1665         fprintf(stderr, "%s%s\t%p \"%s\"\n", prefix, nodeName().utf8().data(), this, value.utf8().data());
1666     } else {
1667         StringBuilder attrs;
1668         appendAttributeDesc(this, attrs, classAttr, " CLASS=");
1669         appendAttributeDesc(this, attrs, styleAttr, " STYLE=");
1670         fprintf(stderr, "%s%s\t%p%s\n", prefix, nodeName().utf8().data(), this, attrs.toString().utf8().data());
1671     }
1672 }
1673
1674 void Node::showTreeForThis() const
1675 {
1676     showTreeAndMark(this, "*");
1677 }
1678
1679 void Node::showNodePathForThis() const
1680 {
1681     Vector<const Node*, 16> chain;
1682     const Node* node = this;
1683     while (node->parentOrShadowHostNode()) {
1684         chain.append(node);
1685         node = node->parentOrShadowHostNode();
1686     }
1687     for (unsigned index = chain.size(); index > 0; --index) {
1688         const Node* node = chain[index - 1];
1689         if (node->isShadowRoot()) {
1690             int count = 0;
1691             for (const ShadowRoot* shadowRoot = toShadowRoot(node); shadowRoot && shadowRoot != node; shadowRoot = shadowRoot->shadowRoot())
1692                 ++count;
1693             fprintf(stderr, "/#shadow-root[%d]", count);
1694             continue;
1695         }
1696
1697         switch (node->nodeType()) {
1698         case ELEMENT_NODE: {
1699             fprintf(stderr, "/%s", node->nodeName().utf8().data());
1700
1701             const Element* element = toElement(node);
1702             const AtomicString& idattr = element->getIdAttribute();
1703             bool hasIdAttr = !idattr.isNull() && !idattr.isEmpty();
1704             if (node->previousSibling() || node->nextSibling()) {
1705                 int count = 0;
1706                 for (Node* previous = node->previousSibling(); previous; previous = previous->previousSibling())
1707                     if (previous->nodeName() == node->nodeName())
1708                         ++count;
1709                 if (hasIdAttr)
1710                     fprintf(stderr, "[@id=\"%s\" and position()=%d]", idattr.string().utf8().data(), count);
1711                 else
1712                     fprintf(stderr, "[%d]", count);
1713             } else if (hasIdAttr)
1714                 fprintf(stderr, "[@id=\"%s\"]", idattr.string().utf8().data());
1715             break;
1716         }
1717         case TEXT_NODE:
1718             fprintf(stderr, "/text()");
1719             break;
1720         case ATTRIBUTE_NODE:
1721             fprintf(stderr, "/@%s", node->nodeName().utf8().data());
1722             break;
1723         default:
1724             break;
1725         }
1726     }
1727     fprintf(stderr, "\n");
1728 }
1729
1730 static void traverseTreeAndMark(const String& baseIndent, const Node* rootNode, const Node* markedNode1, const char* markedLabel1, const Node* markedNode2, const char* markedLabel2)
1731 {
1732     for (const Node* node = rootNode; node; node = NodeTraversal::next(node)) {
1733         if (node == markedNode1)
1734             fprintf(stderr, "%s", markedLabel1);
1735         if (node == markedNode2)
1736             fprintf(stderr, "%s", markedLabel2);
1737
1738         StringBuilder indent;
1739         indent.append(baseIndent);
1740         for (const Node* tmpNode = node; tmpNode && tmpNode != rootNode; tmpNode = tmpNode->parentOrShadowHostNode())
1741             indent.append('\t');
1742         fprintf(stderr, "%s", indent.toString().utf8().data());
1743         node->showNode();
1744         indent.append('\t');
1745         if (!node->isShadowRoot()) {
1746             if (ShadowRoot* shadowRoot = node->shadowRoot())
1747                 traverseTreeAndMark(indent.toString(), shadowRoot, markedNode1, markedLabel1, markedNode2, markedLabel2);
1748         }
1749     }
1750 }
1751
1752 void Node::showTreeAndMark(const Node* markedNode1, const char* markedLabel1, const Node* markedNode2, const char* markedLabel2) const
1753 {
1754     const Node* rootNode;
1755     const Node* node = this;
1756     while (node->parentOrShadowHostNode() && !node->hasTagName(bodyTag))
1757         node = node->parentOrShadowHostNode();
1758     rootNode = node;
1759
1760     String startingIndent;
1761     traverseTreeAndMark(startingIndent, rootNode, markedNode1, markedLabel1, markedNode2, markedLabel2);
1762 }
1763
1764 void Node::formatForDebugger(char* buffer, unsigned length) const
1765 {
1766     String result;
1767     String s;
1768
1769     s = nodeName();
1770     if (s.isEmpty())
1771         result = "<none>";
1772     else
1773         result = s;
1774
1775     strncpy(buffer, result.utf8().data(), length - 1);
1776 }
1777
1778 static ContainerNode* parentOrShadowHostOrFrameOwner(const Node* node)
1779 {
1780     ContainerNode* parent = node->parentOrShadowHostNode();
1781     if (!parent && node->document() && node->document()->frame())
1782         parent = node->document()->frame()->ownerElement();
1783     return parent;
1784 }
1785
1786 static void showSubTreeAcrossFrame(const Node* node, const Node* markedNode, const String& indent)
1787 {
1788     if (node == markedNode)
1789         fputs("*", stderr);
1790     fputs(indent.utf8().data(), stderr);
1791     node->showNode();
1792     if (!node->isShadowRoot()) {
1793         if (node->isFrameOwnerElement())
1794             showSubTreeAcrossFrame(static_cast<const HTMLFrameOwnerElement*>(node)->contentDocument(), markedNode, indent + "\t");
1795         if (ShadowRoot* shadowRoot = node->shadowRoot())
1796             showSubTreeAcrossFrame(shadowRoot, markedNode, indent + "\t");
1797     }
1798     for (Node* child = node->firstChild(); child; child = child->nextSibling())
1799         showSubTreeAcrossFrame(child, markedNode, indent + "\t");
1800 }
1801
1802 void Node::showTreeForThisAcrossFrame() const
1803 {
1804     Node* rootNode = const_cast<Node*>(this);
1805     while (parentOrShadowHostOrFrameOwner(rootNode))
1806         rootNode = parentOrShadowHostOrFrameOwner(rootNode);
1807     showSubTreeAcrossFrame(rootNode, this, "");
1808 }
1809
1810 #endif
1811
1812 // --------
1813
1814 void NodeListsNodeData::invalidateCaches(const QualifiedName* attrName)
1815 {
1816     NodeListAtomicNameCacheMap::const_iterator atomicNameCacheEnd = m_atomicNameCaches.end();
1817     for (NodeListAtomicNameCacheMap::const_iterator it = m_atomicNameCaches.begin(); it != atomicNameCacheEnd; ++it)
1818         it->value->invalidateCache(attrName);
1819
1820     NodeListNameCacheMap::const_iterator nameCacheEnd = m_nameCaches.end();
1821     for (NodeListNameCacheMap::const_iterator it = m_nameCaches.begin(); it != nameCacheEnd; ++it)
1822         it->value->invalidateCache(attrName);
1823
1824     if (attrName)
1825         return;
1826
1827     TagNodeListCacheNS::iterator tagCacheEnd = m_tagNodeListCacheNS.end();
1828     for (TagNodeListCacheNS::iterator it = m_tagNodeListCacheNS.begin(); it != tagCacheEnd; ++it)
1829         it->value->invalidateCache();
1830 }
1831
1832 void Node::getSubresourceURLs(ListHashSet<KURL>& urls) const
1833 {
1834     addSubresourceAttributeURLs(urls);
1835 }
1836
1837 Node* Node::enclosingLinkEventParentOrSelf()
1838 {
1839     for (Node* node = this; node; node = node->parentOrShadowHostNode()) {
1840         // For imagemaps, the enclosing link node is the associated area element not the image itself.
1841         // So we don't let images be the enclosingLinkNode, even though isLink sometimes returns true
1842         // for them.
1843         if (node->isLink() && !isHTMLImageElement(node))
1844             return node;
1845     }
1846
1847     return 0;
1848 }
1849
1850 const AtomicString& Node::interfaceName() const
1851 {
1852     return eventNames().interfaceForNode;
1853 }
1854
1855 ScriptExecutionContext* Node::scriptExecutionContext() const
1856 {
1857     return document();
1858 }
1859
1860 void Node::didMoveToNewDocument(Document* oldDocument)
1861 {
1862     TreeScopeAdopter::ensureDidMoveToNewDocumentWasCalled(oldDocument);
1863
1864     if (const EventTargetData* eventTargetData = this->eventTargetData()) {
1865         const EventListenerMap& listenerMap = eventTargetData->eventListenerMap;
1866         if (!listenerMap.isEmpty()) {
1867             Vector<AtomicString> types = listenerMap.eventTypes();
1868             for (unsigned i = 0; i < types.size(); ++i)
1869                 document()->addListenerTypeIfNeeded(types[i]);
1870         }
1871     }
1872
1873     if (AXObjectCache::accessibilityEnabled() && oldDocument)
1874         if (AXObjectCache* cache = oldDocument->existingAXObjectCache())
1875             cache->remove(this);
1876
1877     const EventListenerVector& wheelListeners = getEventListeners(eventNames().mousewheelEvent);
1878     for (size_t i = 0; i < wheelListeners.size(); ++i) {
1879         oldDocument->didRemoveWheelEventHandler();
1880         document()->didAddWheelEventHandler();
1881     }
1882
1883     Vector<AtomicString> touchEventNames = eventNames().touchEventNames();
1884     for (size_t i = 0; i < touchEventNames.size(); ++i) {
1885         const EventListenerVector& listeners = getEventListeners(touchEventNames[i]);
1886         for (size_t j = 0; j < listeners.size(); ++j) {
1887             oldDocument->didRemoveTouchEventHandler(this);
1888             document()->didAddTouchEventHandler(this);
1889         }
1890     }
1891
1892     if (Vector<OwnPtr<MutationObserverRegistration> >* registry = mutationObserverRegistry()) {
1893         for (size_t i = 0; i < registry->size(); ++i) {
1894             document()->addMutationObserverTypes(registry->at(i)->mutationTypes());
1895         }
1896     }
1897
1898     if (HashSet<MutationObserverRegistration*>* transientRegistry = transientMutationObserverRegistry()) {
1899         for (HashSet<MutationObserverRegistration*>::iterator iter = transientRegistry->begin(); iter != transientRegistry->end(); ++iter) {
1900             document()->addMutationObserverTypes((*iter)->mutationTypes());
1901         }
1902     }
1903 }
1904
1905 static inline bool tryAddEventListener(Node* targetNode, const AtomicString& eventType, PassRefPtr<EventListener> listener, bool useCapture)
1906 {
1907     if (!targetNode->EventTarget::addEventListener(eventType, listener, useCapture))
1908         return false;
1909
1910     if (Document* document = targetNode->document()) {
1911         document->addListenerTypeIfNeeded(eventType);
1912         if (eventType == eventNames().mousewheelEvent)
1913             document->didAddWheelEventHandler();
1914         else if (eventNames().isTouchEventType(eventType))
1915             document->didAddTouchEventHandler(targetNode);
1916     }
1917
1918     return true;
1919 }
1920
1921 bool Node::addEventListener(const AtomicString& eventType, PassRefPtr<EventListener> listener, bool useCapture)
1922 {
1923     return tryAddEventListener(this, eventType, listener, useCapture);
1924 }
1925
1926 static inline bool tryRemoveEventListener(Node* targetNode, const AtomicString& eventType, EventListener* listener, bool useCapture)
1927 {
1928     if (!targetNode->EventTarget::removeEventListener(eventType, listener, useCapture))
1929         return false;
1930
1931     // FIXME: Notify Document that the listener has vanished. We need to keep track of a number of
1932     // listeners for each type, not just a bool - see https://bugs.webkit.org/show_bug.cgi?id=33861
1933     if (Document* document = targetNode->document()) {
1934         if (eventType == eventNames().mousewheelEvent)
1935             document->didRemoveWheelEventHandler();
1936         else if (eventNames().isTouchEventType(eventType))
1937             document->didRemoveTouchEventHandler(targetNode);
1938     }
1939
1940     return true;
1941 }
1942
1943 bool Node::removeEventListener(const AtomicString& eventType, EventListener* listener, bool useCapture)
1944 {
1945     return tryRemoveEventListener(this, eventType, listener, useCapture);
1946 }
1947
1948 typedef HashMap<Node*, OwnPtr<EventTargetData> > EventTargetDataMap;
1949
1950 static EventTargetDataMap& eventTargetDataMap()
1951 {
1952     DEFINE_STATIC_LOCAL(EventTargetDataMap, map, ());
1953     return map;
1954 }
1955
1956 EventTargetData* Node::eventTargetData()
1957 {
1958     return hasEventTargetData() ? eventTargetDataMap().get(this) : 0;
1959 }
1960
1961 EventTargetData& Node::ensureEventTargetData()
1962 {
1963     if (hasEventTargetData())
1964         return *eventTargetDataMap().get(this);
1965     setHasEventTargetData(true);
1966     EventTargetData* data = new EventTargetData;
1967     eventTargetDataMap().set(this, adoptPtr(data));
1968     return *data;
1969 }
1970
1971 void Node::clearEventTargetData()
1972 {
1973     eventTargetDataMap().remove(this);
1974 }
1975
1976 Vector<OwnPtr<MutationObserverRegistration> >* Node::mutationObserverRegistry()
1977 {
1978     if (!hasRareData())
1979         return 0;
1980     NodeMutationObserverData* data = rareData()->mutationObserverData();
1981     if (!data)
1982         return 0;
1983     return &data->registry;
1984 }
1985
1986 HashSet<MutationObserverRegistration*>* Node::transientMutationObserverRegistry()
1987 {
1988     if (!hasRareData())
1989         return 0;
1990     NodeMutationObserverData* data = rareData()->mutationObserverData();
1991     if (!data)
1992         return 0;
1993     return &data->transientRegistry;
1994 }
1995
1996 template<typename Registry>
1997 static inline void collectMatchingObserversForMutation(HashMap<MutationObserver*, MutationRecordDeliveryOptions>& observers, Registry* registry, Node* target, MutationObserver::MutationType type, const QualifiedName* attributeName)
1998 {
1999     if (!registry)
2000         return;
2001     for (typename Registry::iterator iter = registry->begin(); iter != registry->end(); ++iter) {
2002         const MutationObserverRegistration& registration = **iter;
2003         if (registration.shouldReceiveMutationFrom(target, type, attributeName)) {
2004             MutationRecordDeliveryOptions deliveryOptions = registration.deliveryOptions();
2005             HashMap<MutationObserver*, MutationRecordDeliveryOptions>::AddResult result = observers.add(registration.observer(), deliveryOptions);
2006             if (!result.isNewEntry)
2007                 result.iterator->value |= deliveryOptions;
2008         }
2009     }
2010 }
2011
2012 void Node::getRegisteredMutationObserversOfType(HashMap<MutationObserver*, MutationRecordDeliveryOptions>& observers, MutationObserver::MutationType type, const QualifiedName* attributeName)
2013 {
2014     ASSERT((type == MutationObserver::Attributes && attributeName) || !attributeName);
2015     collectMatchingObserversForMutation(observers, mutationObserverRegistry(), this, type, attributeName);
2016     collectMatchingObserversForMutation(observers, transientMutationObserverRegistry(), this, type, attributeName);
2017     for (Node* node = parentNode(); node; node = node->parentNode()) {
2018         collectMatchingObserversForMutation(observers, node->mutationObserverRegistry(), this, type, attributeName);
2019         collectMatchingObserversForMutation(observers, node->transientMutationObserverRegistry(), this, type, attributeName);
2020     }
2021 }
2022
2023 void Node::registerMutationObserver(MutationObserver* observer, MutationObserverOptions options, const HashSet<AtomicString>& attributeFilter)
2024 {
2025     MutationObserverRegistration* registration = 0;
2026     Vector<OwnPtr<MutationObserverRegistration> >& registry = ensureRareData().ensureMutationObserverData().registry;
2027     for (size_t i = 0; i < registry.size(); ++i) {
2028         if (registry[i]->observer() == observer) {
2029             registration = registry[i].get();
2030             registration->resetObservation(options, attributeFilter);
2031         }
2032     }
2033
2034     if (!registration) {
2035         registry.append(MutationObserverRegistration::create(observer, this, options, attributeFilter));
2036         registration = registry.last().get();
2037     }
2038
2039     document()->addMutationObserverTypes(registration->mutationTypes());
2040 }
2041
2042 void Node::unregisterMutationObserver(MutationObserverRegistration* registration)
2043 {
2044     Vector<OwnPtr<MutationObserverRegistration> >* registry = mutationObserverRegistry();
2045     ASSERT(registry);
2046     if (!registry)
2047         return;
2048
2049     size_t index = registry->find(registration);
2050     ASSERT(index != notFound);
2051     if (index == notFound)
2052         return;
2053
2054     registry->remove(index);
2055 }
2056
2057 void Node::registerTransientMutationObserver(MutationObserverRegistration* registration)
2058 {
2059     ensureRareData().ensureMutationObserverData().transientRegistry.add(registration);
2060 }
2061
2062 void Node::unregisterTransientMutationObserver(MutationObserverRegistration* registration)
2063 {
2064     HashSet<MutationObserverRegistration*>* transientRegistry = transientMutationObserverRegistry();
2065     ASSERT(transientRegistry);
2066     if (!transientRegistry)
2067         return;
2068
2069     ASSERT(transientRegistry->contains(registration));
2070     transientRegistry->remove(registration);
2071 }
2072
2073 void Node::notifyMutationObserversNodeWillDetach()
2074 {
2075     if (!document()->hasMutationObservers())
2076         return;
2077
2078     for (Node* node = parentNode(); node; node = node->parentNode()) {
2079         if (Vector<OwnPtr<MutationObserverRegistration> >* registry = node->mutationObserverRegistry()) {
2080             const size_t size = registry->size();
2081             for (size_t i = 0; i < size; ++i)
2082                 registry->at(i)->observedSubtreeNodeWillDetach(this);
2083         }
2084
2085         if (HashSet<MutationObserverRegistration*>* transientRegistry = node->transientMutationObserverRegistry()) {
2086             for (HashSet<MutationObserverRegistration*>::iterator iter = transientRegistry->begin(); iter != transientRegistry->end(); ++iter)
2087                 (*iter)->observedSubtreeNodeWillDetach(this);
2088         }
2089     }
2090 }
2091
2092 void Node::handleLocalEvents(Event* event)
2093 {
2094     if (!hasEventTargetData())
2095         return;
2096
2097     if (isDisabledFormControl(this) && event->isMouseEvent())
2098         return;
2099
2100     fireEventListeners(event);
2101 }
2102
2103 void Node::dispatchScopedEvent(PassRefPtr<Event> event)
2104 {
2105     dispatchScopedEventDispatchMediator(EventDispatchMediator::create(event));
2106 }
2107
2108 void Node::dispatchScopedEventDispatchMediator(PassRefPtr<EventDispatchMediator> eventDispatchMediator)
2109 {
2110     EventDispatcher::dispatchScopedEvent(this, eventDispatchMediator);
2111 }
2112
2113 bool Node::dispatchEvent(PassRefPtr<Event> event)
2114 {
2115     if (event->isMouseEvent())
2116         return EventDispatcher::dispatchEvent(this, MouseEventDispatchMediator::create(adoptRef(toMouseEvent(event.leakRef())), MouseEventDispatchMediator::SyntheticMouseEvent));
2117 #if ENABLE(TOUCH_EVENTS)
2118     if (event->isTouchEvent())
2119         return dispatchTouchEvent(adoptRef(toTouchEvent(event.leakRef())));
2120 #endif
2121     return EventDispatcher::dispatchEvent(this, EventDispatchMediator::create(event));
2122 }
2123
2124 void Node::dispatchSubtreeModifiedEvent()
2125 {
2126     if (isInShadowTree())
2127         return;
2128
2129     ASSERT(!NoEventDispatchAssertion::isEventDispatchForbidden());
2130
2131     if (!document()->hasListenerType(Document::DOMSUBTREEMODIFIED_LISTENER))
2132         return;
2133
2134     dispatchScopedEvent(MutationEvent::create(eventNames().DOMSubtreeModifiedEvent, true));
2135 }
2136
2137 bool Node::dispatchDOMActivateEvent(int detail, PassRefPtr<Event> underlyingEvent)
2138 {
2139     ASSERT(!NoEventDispatchAssertion::isEventDispatchForbidden());
2140     RefPtr<UIEvent> event = UIEvent::create(eventNames().DOMActivateEvent, true, true, document()->defaultView(), detail);
2141     event->setUnderlyingEvent(underlyingEvent);
2142     dispatchScopedEvent(event);
2143     return event->defaultHandled();
2144 }
2145
2146 bool Node::dispatchKeyEvent(const PlatformKeyboardEvent& event)
2147 {
2148     return EventDispatcher::dispatchEvent(this, KeyboardEventDispatchMediator::create(KeyboardEvent::create(event, document()->defaultView())));
2149 }
2150
2151 bool Node::dispatchMouseEvent(const PlatformMouseEvent& event, const AtomicString& eventType,
2152     int detail, Node* relatedTarget)
2153 {
2154     return EventDispatcher::dispatchEvent(this, MouseEventDispatchMediator::create(MouseEvent::create(eventType, document()->defaultView(), event, detail, relatedTarget)));
2155 }
2156
2157 #if ENABLE(GESTURE_EVENTS)
2158 bool Node::dispatchGestureEvent(const PlatformGestureEvent& event)
2159 {
2160     RefPtr<GestureEvent> gestureEvent = GestureEvent::create(document()->defaultView(), event);
2161     if (!gestureEvent.get())
2162         return false;
2163     return EventDispatcher::dispatchEvent(this, GestureEventDispatchMediator::create(gestureEvent));
2164 }
2165 #endif
2166
2167 #if ENABLE(TOUCH_EVENTS)
2168 bool Node::dispatchTouchEvent(PassRefPtr<TouchEvent> event)
2169 {
2170     return EventDispatcher::dispatchEvent(this, TouchEventDispatchMediator::create(event));
2171 }
2172 #endif
2173
2174 #if ENABLE(INDIE_UI)
2175 bool Node::dispatchUIRequestEvent(PassRefPtr<UIRequestEvent> event)
2176 {
2177     return EventDispatcher::dispatchEvent(this, UIRequestEventDispatchMediator::create(event));
2178 }
2179 #endif
2180     
2181 bool Node::dispatchBeforeLoadEvent(const String& sourceURL)
2182 {
2183     if (!document()->hasListenerType(Document::BEFORELOAD_LISTENER))
2184         return true;
2185
2186     RefPtr<Node> protector(this);
2187     RefPtr<BeforeLoadEvent> beforeLoadEvent = BeforeLoadEvent::create(sourceURL);
2188     dispatchEvent(beforeLoadEvent.get());
2189     return !beforeLoadEvent->defaultPrevented();
2190 }
2191
2192 bool Node::dispatchWheelEvent(const PlatformWheelEvent& event)
2193 {
2194     return EventDispatcher::dispatchEvent(this, WheelEventDispatchMediator::create(event, document()->defaultView()));
2195 }
2196
2197 void Node::dispatchInputEvent()
2198 {
2199     dispatchScopedEvent(Event::create(eventNames().inputEvent, true, false));
2200 }
2201
2202 void Node::defaultEventHandler(Event* event)
2203 {
2204     if (event->target() != this)
2205         return;
2206     const AtomicString& eventType = event->type();
2207     if (eventType == eventNames().keydownEvent || eventType == eventNames().keypressEvent) {
2208         if (event->isKeyboardEvent())
2209             if (Frame* frame = document()->frame())
2210                 frame->eventHandler().defaultKeyboardEventHandler(static_cast<KeyboardEvent*>(event));
2211     } else if (eventType == eventNames().clickEvent) {
2212         int detail = event->isUIEvent() ? static_cast<UIEvent*>(event)->detail() : 0;
2213         if (dispatchDOMActivateEvent(detail, event))
2214             event->setDefaultHandled();
2215 #if ENABLE(CONTEXT_MENUS)
2216     } else if (eventType == eventNames().contextmenuEvent) {
2217         if (Frame* frame = document()->frame())
2218             if (Page* page = frame->page())
2219                 page->contextMenuController()->handleContextMenuEvent(event);
2220 #endif
2221     } else if (eventType == eventNames().textInputEvent) {
2222         if (event->hasInterface(eventNames().interfaceForTextEvent))
2223             if (Frame* frame = document()->frame())
2224                 frame->eventHandler().defaultTextInputEventHandler(static_cast<TextEvent*>(event));
2225 #if ENABLE(PAN_SCROLLING)
2226     } else if (eventType == eventNames().mousedownEvent && event->isMouseEvent()) {
2227         MouseEvent* mouseEvent = static_cast<MouseEvent*>(event);
2228         if (mouseEvent->button() == MiddleButton) {
2229             if (enclosingLinkEventParentOrSelf())
2230                 return;
2231
2232             RenderObject* renderer = this->renderer();
2233             while (renderer && (!renderer->isBox() || !toRenderBox(renderer)->canBeScrolledAndHasScrollableArea()))
2234                 renderer = renderer->parent();
2235
2236             if (renderer) {
2237                 if (Frame* frame = document()->frame())
2238                     frame->eventHandler().startPanScrolling(renderer);
2239             }
2240         }
2241 #endif
2242     } else if (eventType == eventNames().mousewheelEvent && event->hasInterface(eventNames().interfaceForWheelEvent)) {
2243         WheelEvent* wheelEvent = static_cast<WheelEvent*>(event);
2244         
2245         // If we don't have a renderer, send the wheel event to the first node we find with a renderer.
2246         // This is needed for <option> and <optgroup> elements so that <select>s get a wheel scroll.
2247         Node* startNode = this;
2248         while (startNode && !startNode->renderer())
2249             startNode = startNode->parentOrShadowHostNode();
2250         
2251         if (startNode && startNode->renderer())
2252             if (Frame* frame = document()->frame())
2253                 frame->eventHandler().defaultWheelEventHandler(startNode, wheelEvent);
2254     } else if (event->type() == eventNames().webkitEditableContentChangedEvent) {
2255         dispatchInputEvent();
2256     }
2257 }
2258
2259 bool Node::willRespondToMouseMoveEvents()
2260 {
2261     if (isDisabledFormControl(this))
2262         return false;
2263     return hasEventListeners(eventNames().mousemoveEvent) || hasEventListeners(eventNames().mouseoverEvent) || hasEventListeners(eventNames().mouseoutEvent);
2264 }
2265
2266 bool Node::willRespondToMouseClickEvents()
2267 {
2268     if (isDisabledFormControl(this))
2269         return false;
2270     return isContentEditable(UserSelectAllIsAlwaysNonEditable) || hasEventListeners(eventNames().mouseupEvent) || hasEventListeners(eventNames().mousedownEvent) || hasEventListeners(eventNames().clickEvent) || hasEventListeners(eventNames().DOMActivateEvent);
2271 }
2272
2273 bool Node::willRespondToTouchEvents()
2274 {
2275 #if ENABLE(TOUCH_EVENTS)
2276     if (isDisabledFormControl(this))
2277         return false;
2278     return hasEventListeners(eventNames().touchstartEvent) || hasEventListeners(eventNames().touchmoveEvent) || hasEventListeners(eventNames().touchcancelEvent) || hasEventListeners(eventNames().touchendEvent);
2279 #else
2280     return false;
2281 #endif
2282 }
2283
2284 // This is here for inlining
2285 inline void TreeScope::removedLastRefToScope()
2286 {
2287     ASSERT(!deletionHasBegun());
2288     if (m_guardRefCount) {
2289         // If removing a child removes the last self-only ref, we don't
2290         // want the scope to be destructed until after
2291         // removeDetachedChildren returns, so we guard ourselves with an
2292         // extra self-only ref.
2293         guardRef();
2294         dispose();
2295 #ifndef NDEBUG
2296         // We need to do this right now since guardDeref() can delete this.
2297         rootNode()->m_inRemovedLastRefFunction = false;
2298 #endif
2299         guardDeref();
2300     } else {
2301 #ifndef NDEBUG
2302         rootNode()->m_inRemovedLastRefFunction = false;
2303         beginDeletion();
2304 #endif
2305         delete this;
2306     }
2307 }
2308
2309 // It's important not to inline removedLastRef, because we don't want to inline the code to
2310 // delete a Node at each deref call site.
2311 void Node::removedLastRef()
2312 {
2313     // An explicit check for Document here is better than a virtual function since it is
2314     // faster for non-Document nodes, and because the call to removedLastRef that is inlined
2315     // at all deref call sites is smaller if it's a non-virtual function.
2316     if (isTreeScope()) {
2317         treeScope()->removedLastRefToScope();
2318         return;
2319     }
2320
2321 #ifndef NDEBUG
2322     m_deletionHasBegun = true;
2323 #endif
2324     delete this;
2325 }
2326
2327 void Node::textRects(Vector<IntRect>& rects) const
2328 {
2329     RefPtr<Range> range = Range::create(document());
2330     range->selectNodeContents(const_cast<Node*>(this), IGNORE_EXCEPTION);
2331     range->textRects(rects);
2332 }
2333
2334 unsigned Node::connectedSubframeCount() const
2335 {
2336     return hasRareData() ? rareData()->connectedSubframeCount() : 0;
2337 }
2338
2339 void Node::incrementConnectedSubframeCount(unsigned amount)
2340 {
2341     ASSERT(isContainerNode());
2342     ensureRareData().incrementConnectedSubframeCount(amount);
2343 }
2344
2345 void Node::decrementConnectedSubframeCount(unsigned amount)
2346 {
2347     rareData()->decrementConnectedSubframeCount(amount);
2348 }
2349
2350 void Node::updateAncestorConnectedSubframeCountForRemoval() const
2351 {
2352     unsigned count = connectedSubframeCount();
2353
2354     if (!count)
2355         return;
2356
2357     for (Node* node = parentOrShadowHostNode(); node; node = node->parentOrShadowHostNode())
2358         node->decrementConnectedSubframeCount(count);
2359 }
2360
2361 void Node::updateAncestorConnectedSubframeCountForInsertion() const
2362 {
2363     unsigned count = connectedSubframeCount();
2364
2365     if (!count)
2366         return;
2367
2368     for (Node* node = parentOrShadowHostNode(); node; node = node->parentOrShadowHostNode())
2369         node->incrementConnectedSubframeCount(count);
2370 }
2371
2372 void Node::registerScopedHTMLStyleChild()
2373 {
2374     setHasScopedHTMLStyleChild(true);
2375 }
2376
2377 void Node::unregisterScopedHTMLStyleChild()
2378 {
2379     ASSERT(hasScopedHTMLStyleChild());
2380     setHasScopedHTMLStyleChild(numberOfScopedHTMLStyleChildren());
2381 }
2382
2383 size_t Node::numberOfScopedHTMLStyleChildren() const
2384 {
2385     size_t count = 0;
2386     for (Element* element = ElementTraversal::firstWithin(this); element; element = ElementTraversal::next(element, this))
2387         if (isHTMLStyleElement(element) && toHTMLStyleElement(element)->isRegisteredAsScoped())
2388             count++;
2389
2390     return count;
2391 }
2392
2393 } // namespace WebCore
2394
2395 #ifndef NDEBUG
2396
2397 void showTree(const WebCore::Node* node)
2398 {
2399     if (node)
2400         node->showTreeForThis();
2401 }
2402
2403 void showNodePath(const WebCore::Node* node)
2404 {
2405     if (node)
2406         node->showNodePathForThis();
2407 }
2408
2409 #endif