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