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