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