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