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