e9ff1b32c7ef30644629cb2d3f6f9827bc2feeb6
[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-2017 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 "CommonVM.h"
33 #include "ComposedTreeAncestorIterator.h"
34 #include "ContainerNodeAlgorithms.h"
35 #include "ContextMenuController.h"
36 #include "DOMWindow.h"
37 #include "DataTransfer.h"
38 #include "DocumentType.h"
39 #include "ElementIterator.h"
40 #include "ElementRareData.h"
41 #include "ElementTraversal.h"
42 #include "EventDispatcher.h"
43 #include "EventHandler.h"
44 #include "FrameView.h"
45 #include "HTMLBodyElement.h"
46 #include "HTMLCollection.h"
47 #include "HTMLElement.h"
48 #include "HTMLImageElement.h"
49 #include "HTMLSlotElement.h"
50 #include "HTMLStyleElement.h"
51 #include "InputEvent.h"
52 #include "InspectorController.h"
53 #include "KeyboardEvent.h"
54 #include "Logging.h"
55 #include "MutationEvent.h"
56 #include "NodeRenderStyle.h"
57 #include "ProcessingInstruction.h"
58 #include "ProgressEvent.h"
59 #include "Range.h"
60 #include "RenderBlock.h"
61 #include "RenderBox.h"
62 #include "RenderTextControl.h"
63 #include "RenderView.h"
64 #include "ScopedEventQueue.h"
65 #include "ScriptDisallowedScope.h"
66 #include "StorageEvent.h"
67 #include "StyleResolver.h"
68 #include "StyleSheetContents.h"
69 #include "TemplateContentDocumentFragment.h"
70 #include "TextEvent.h"
71 #include "TouchEvent.h"
72 #include "WheelEvent.h"
73 #include "XMLNSNames.h"
74 #include "XMLNames.h"
75 #include <wtf/IsoMallocInlines.h>
76 #include <wtf/RefCountedLeakCounter.h>
77 #include <wtf/SHA1.h>
78 #include <wtf/Variant.h>
79 #include <wtf/text/CString.h>
80 #include <wtf/text/StringBuilder.h>
81
82 namespace WebCore {
83
84 WTF_MAKE_ISO_ALLOCATED_IMPL(Node);
85
86 using namespace HTMLNames;
87
88 #if DUMP_NODE_STATISTICS
89 static HashSet<Node*>& liveNodeSet()
90 {
91     static NeverDestroyed<HashSet<Node*>> liveNodes;
92     return liveNodes;
93 }
94
95 static const char* stringForRareDataUseType(NodeRareData::UseType useType)
96 {
97     switch (useType) {
98     case NodeRareData::UseType::ConnectedFrameCount:
99         return "ConnectedFrameCount";
100     case NodeRareData::UseType::NodeList:
101         return "NodeList";
102     case NodeRareData::UseType::MutationObserver:
103         return "MutationObserver";
104     case NodeRareData::UseType::TabIndex:
105         return "TabIndex";
106     case NodeRareData::UseType::StyleFlags:
107         return "StyleFlags";
108     case NodeRareData::UseType::MinimumSize:
109         return "MinimumSize";
110     case NodeRareData::UseType::ScrollingPosition:
111         return "ScrollingPosition";
112     case NodeRareData::UseType::ComputedStyle:
113         return "ComputedStyle";
114     case NodeRareData::UseType::Dataset:
115         return "Dataset";
116     case NodeRareData::UseType::ClassList:
117         return "ClassList";
118     case NodeRareData::UseType::ShadowRoot:
119         return "ShadowRoot";
120     case NodeRareData::UseType::CustomElementQueue:
121         return "CustomElementQueue";
122     case NodeRareData::UseType::AttributeMap:
123         return "AttributeMap";
124     case NodeRareData::UseType::InteractionObserver:
125         return "InteractionObserver";
126     case NodeRareData::UseType::PseudoElements:
127         return "PseudoElements";
128     }
129     return nullptr;
130 }
131
132 #endif
133
134 void Node::dumpStatistics()
135 {
136 #if DUMP_NODE_STATISTICS
137     size_t nodesWithRareData = 0;
138
139     size_t elementNodes = 0;
140     size_t attrNodes = 0;
141     size_t textNodes = 0;
142     size_t cdataNodes = 0;
143     size_t commentNodes = 0;
144     size_t piNodes = 0;
145     size_t documentNodes = 0;
146     size_t docTypeNodes = 0;
147     size_t fragmentNodes = 0;
148     size_t shadowRootNodes = 0;
149
150     HashMap<String, size_t> perTagCount;
151
152     size_t attributes = 0;
153     size_t attributesWithAttr = 0;
154     size_t elementsWithAttributeStorage = 0;
155     size_t elementsWithRareData = 0;
156     size_t elementsWithNamedNodeMap = 0;
157
158     HashMap<uint16_t, size_t> rareDataSingleUseTypeCounts;
159     size_t mixedRareDataUseCount = 0;
160
161     for (auto* node : liveNodeSet()) {
162         if (node->hasRareData()) {
163             ++nodesWithRareData;
164             if (is<Element>(*node)) {
165                 ++elementsWithRareData;
166                 if (downcast<Element>(*node).hasNamedNodeMap())
167                     ++elementsWithNamedNodeMap;
168             }
169             auto* rareData = node->rareData();
170             auto useTypes = is<Element>(node) ? static_cast<ElementRareData*>(rareData)->useTypes() : rareData->useTypes();
171             unsigned useTypeCount = 0;
172             for (auto type : useTypes) {
173                 UNUSED_PARAM(type);
174                 useTypeCount++;
175             }
176             if (useTypeCount == 1) {
177                 auto result = rareDataSingleUseTypeCounts.add(static_cast<uint16_t>(*useTypes.begin()), 0);
178                 result.iterator->value++;
179             } else
180                 mixedRareDataUseCount++;
181         }
182
183         switch (node->nodeType()) {
184             case ELEMENT_NODE: {
185                 ++elementNodes;
186
187                 // Tag stats
188                 Element& element = downcast<Element>(*node);
189                 HashMap<String, size_t>::AddResult result = perTagCount.add(element.tagName(), 1);
190                 if (!result.isNewEntry)
191                     result.iterator->value++;
192
193                 if (const ElementData* elementData = element.elementData()) {
194                     unsigned length = elementData->length();
195                     attributes += length;
196                     ++elementsWithAttributeStorage;
197                     for (unsigned i = 0; i < length; ++i) {
198                         const Attribute& attr = elementData->attributeAt(i);
199                         if (element.attrIfExists(attr.name()))
200                             ++attributesWithAttr;
201                     }
202                 }
203                 break;
204             }
205             case ATTRIBUTE_NODE: {
206                 ++attrNodes;
207                 break;
208             }
209             case TEXT_NODE: {
210                 ++textNodes;
211                 break;
212             }
213             case CDATA_SECTION_NODE: {
214                 ++cdataNodes;
215                 break;
216             }
217             case PROCESSING_INSTRUCTION_NODE: {
218                 ++piNodes;
219                 break;
220             }
221             case COMMENT_NODE: {
222                 ++commentNodes;
223                 break;
224             }
225             case DOCUMENT_NODE: {
226                 ++documentNodes;
227                 break;
228             }
229             case DOCUMENT_TYPE_NODE: {
230                 ++docTypeNodes;
231                 break;
232             }
233             case DOCUMENT_FRAGMENT_NODE: {
234                 if (node->isShadowRoot())
235                     ++shadowRootNodes;
236                 else
237                     ++fragmentNodes;
238                 break;
239             }
240         }
241     }
242
243     printf("Number of Nodes: %d\n\n", liveNodeSet().size());
244     printf("Number of Nodes with RareData: %zu\n", nodesWithRareData);
245     printf("  Mixed use: %zu\n", mixedRareDataUseCount);
246     for (auto it : rareDataSingleUseTypeCounts)
247         printf("  %s: %zu\n", stringForRareDataUseType(static_cast<NodeRareData::UseType>(it.key)), it.value);
248     printf("\n");
249
250
251     printf("NodeType distribution:\n");
252     printf("  Number of Element nodes: %zu\n", elementNodes);
253     printf("  Number of Attribute nodes: %zu\n", attrNodes);
254     printf("  Number of Text nodes: %zu\n", textNodes);
255     printf("  Number of CDATASection nodes: %zu\n", cdataNodes);
256     printf("  Number of Comment nodes: %zu\n", commentNodes);
257     printf("  Number of ProcessingInstruction nodes: %zu\n", piNodes);
258     printf("  Number of Document nodes: %zu\n", documentNodes);
259     printf("  Number of DocumentType nodes: %zu\n", docTypeNodes);
260     printf("  Number of DocumentFragment nodes: %zu\n", fragmentNodes);
261     printf("  Number of ShadowRoot nodes: %zu\n", shadowRootNodes);
262
263     printf("Element tag name distibution:\n");
264     for (auto& stringSizePair : perTagCount)
265         printf("  Number of <%s> tags: %zu\n", stringSizePair.key.utf8().data(), stringSizePair.value);
266
267     printf("Attributes:\n");
268     printf("  Number of Attributes (non-Node and Node): %zu [%zu]\n", attributes, sizeof(Attribute));
269     printf("  Number of Attributes with an Attr: %zu\n", attributesWithAttr);
270     printf("  Number of Elements with attribute storage: %zu [%zu]\n", elementsWithAttributeStorage, sizeof(ElementData));
271     printf("  Number of Elements with RareData: %zu\n", elementsWithRareData);
272     printf("  Number of Elements with NamedNodeMap: %zu [%zu]\n", elementsWithNamedNodeMap, sizeof(NamedNodeMap));
273 #endif
274 }
275
276 DEFINE_DEBUG_ONLY_GLOBAL(WTF::RefCountedLeakCounter, nodeCounter, ("WebCoreNode"));
277
278 #ifndef NDEBUG
279 static bool shouldIgnoreLeaks = false;
280
281 static HashSet<Node*>& ignoreSet()
282 {
283     static NeverDestroyed<HashSet<Node*>> ignore;
284
285     return ignore;
286 }
287
288 #endif
289
290 void Node::startIgnoringLeaks()
291 {
292 #ifndef NDEBUG
293     shouldIgnoreLeaks = true;
294 #endif
295 }
296
297 void Node::stopIgnoringLeaks()
298 {
299 #ifndef NDEBUG
300     shouldIgnoreLeaks = false;
301 #endif
302 }
303
304 void Node::trackForDebugging()
305 {
306 #ifndef NDEBUG
307     if (shouldIgnoreLeaks)
308         ignoreSet().add(this);
309     else
310         nodeCounter.increment();
311 #endif
312
313 #if DUMP_NODE_STATISTICS
314     liveNodeSet().add(this);
315 #endif
316 }
317
318 Node::Node(Document& document, ConstructionType type)
319     : m_nodeFlags(type)
320     , m_treeScope(&document)
321 {
322     ASSERT(isMainThread());
323
324     document.incrementReferencingNodeCount();
325
326 #if !defined(NDEBUG) || (defined(DUMP_NODE_STATISTICS) && DUMP_NODE_STATISTICS)
327     trackForDebugging();
328 #endif
329 }
330
331 Node::~Node()
332 {
333     ASSERT(isMainThread());
334     // We set m_refCount to 2 before calling delete to avoid double destruction through use of Ref<T>/RefPtr<T>.
335     // This is a security mitigation in case of programmer errorm (caught by a debug assertion).
336     ASSERT(m_refCountAndParentBit == s_refCountIncrement);
337     ASSERT(m_deletionHasBegun);
338     ASSERT(!m_adoptionIsRequired);
339
340 #ifndef NDEBUG
341     if (!ignoreSet().remove(this))
342         nodeCounter.decrement();
343 #endif
344
345 #if DUMP_NODE_STATISTICS
346     liveNodeSet().remove(this);
347 #endif
348
349     RELEASE_ASSERT(!renderer());
350     ASSERT(!parentNode());
351     ASSERT(!m_previous);
352     ASSERT(!m_next);
353
354     if (hasRareData())
355         clearRareData();
356
357     if (!isContainerNode())
358         willBeDeletedFrom(document());
359
360     if (hasEventTargetData())
361         clearEventTargetData();
362
363     document().decrementReferencingNodeCount();
364
365 #if ENABLE(TOUCH_EVENTS) && PLATFORM(IOS_FAMILY) && (!ASSERT_DISABLED || ENABLE(SECURITY_ASSERTIONS))
366     for (auto* document : Document::allDocuments()) {
367         ASSERT_WITH_SECURITY_IMPLICATION(!document->touchEventListenersContain(*this));
368         ASSERT_WITH_SECURITY_IMPLICATION(!document->touchEventHandlersContain(*this));
369         ASSERT_WITH_SECURITY_IMPLICATION(!document->touchEventTargetsContain(*this));
370     }
371 #endif
372 }
373
374 void Node::willBeDeletedFrom(Document& document)
375 {
376     if (hasEventTargetData()) {
377         document.didRemoveWheelEventHandler(*this, EventHandlerRemoval::All);
378 #if ENABLE(TOUCH_EVENTS)
379 #if PLATFORM(IOS_FAMILY)
380         document.removeTouchEventListener(*this, EventHandlerRemoval::All);
381 #endif
382         document.didRemoveTouchEventHandler(*this, EventHandlerRemoval::All);
383 #endif
384     }
385
386 #if ENABLE(TOUCH_EVENTS) && PLATFORM(IOS_FAMILY)
387     document.removeTouchEventHandler(*this, EventHandlerRemoval::All);
388 #endif
389
390     if (auto* cache = document.existingAXObjectCache())
391         cache->remove(*this);
392 }
393
394 void Node::materializeRareData()
395 {
396     NodeRareData* data;
397     if (is<Element>(*this))
398         data = std::make_unique<ElementRareData>(downcast<RenderElement>(m_data.m_renderer)).release();
399     else
400         data = std::make_unique<NodeRareData>(m_data.m_renderer).release();
401     ASSERT(data);
402
403     m_data.m_rareData = data;
404     setFlag(HasRareDataFlag);
405 }
406
407 void Node::clearRareData()
408 {
409     ASSERT(hasRareData());
410     ASSERT(!transientMutationObserverRegistry() || transientMutationObserverRegistry()->isEmpty());
411
412     RenderObject* renderer = m_data.m_rareData->renderer();
413     if (isElementNode())
414         delete static_cast<ElementRareData*>(m_data.m_rareData);
415     else
416         delete static_cast<NodeRareData*>(m_data.m_rareData);
417     m_data.m_renderer = renderer;
418     clearFlag(HasRareDataFlag);
419 }
420
421 bool Node::isNode() const
422 {
423     return true;
424 }
425
426 String Node::nodeValue() const
427 {
428     return String();
429 }
430
431 ExceptionOr<void> Node::setNodeValue(const String&)
432 {
433     // By default, setting nodeValue has no effect.
434     return { };
435 }
436
437 RefPtr<NodeList> Node::childNodes()
438 {
439     if (is<ContainerNode>(*this))
440         return ensureRareData().ensureNodeLists().ensureChildNodeList(downcast<ContainerNode>(*this));
441     return ensureRareData().ensureNodeLists().ensureEmptyChildNodeList(*this);
442 }
443
444 Node *Node::lastDescendant() const
445 {
446     Node *n = const_cast<Node *>(this);
447     while (n && n->lastChild())
448         n = n->lastChild();
449     return n;
450 }
451
452 Node* Node::firstDescendant() const
453 {
454     Node *n = const_cast<Node *>(this);
455     while (n && n->firstChild())
456         n = n->firstChild();
457     return n;
458 }
459
460 Element* Node::previousElementSibling() const
461 {
462     return ElementTraversal::previousSibling(*this);
463 }
464
465 Element* Node::nextElementSibling() const
466 {
467     return ElementTraversal::nextSibling(*this);
468 }
469
470 ExceptionOr<void> Node::insertBefore(Node& newChild, Node* refChild)
471 {
472     if (!is<ContainerNode>(*this))
473         return Exception { HierarchyRequestError };
474     return downcast<ContainerNode>(*this).insertBefore(newChild, refChild);
475 }
476
477 ExceptionOr<void> Node::replaceChild(Node& newChild, Node& oldChild)
478 {
479     if (!is<ContainerNode>(*this))
480         return Exception { HierarchyRequestError };
481     return downcast<ContainerNode>(*this).replaceChild(newChild, oldChild);
482 }
483
484 ExceptionOr<void> Node::removeChild(Node& oldChild)
485 {
486     if (!is<ContainerNode>(*this))
487         return Exception { NotFoundError };
488     return downcast<ContainerNode>(*this).removeChild(oldChild);
489 }
490
491 ExceptionOr<void> Node::appendChild(Node& newChild)
492 {
493     if (!is<ContainerNode>(*this))
494         return Exception { HierarchyRequestError };
495     return downcast<ContainerNode>(*this).appendChild(newChild);
496 }
497
498 static HashSet<RefPtr<Node>> nodeSetPreTransformedFromNodeOrStringVector(const Vector<NodeOrString>& vector)
499 {
500     HashSet<RefPtr<Node>> nodeSet;
501     for (const auto& variant : vector) {
502         WTF::switchOn(variant,
503             [&] (const RefPtr<Node>& node) { nodeSet.add(const_cast<Node*>(node.get())); },
504             [] (const String&) { }
505         );
506     }
507     return nodeSet;
508 }
509
510 static RefPtr<Node> firstPrecedingSiblingNotInNodeSet(Node& context, const HashSet<RefPtr<Node>>& nodeSet)
511 {
512     for (auto* sibling = context.previousSibling(); sibling; sibling = sibling->previousSibling()) {
513         if (!nodeSet.contains(sibling))
514             return sibling;
515     }
516     return nullptr;
517 }
518
519 static RefPtr<Node> firstFollowingSiblingNotInNodeSet(Node& context, const HashSet<RefPtr<Node>>& nodeSet)
520 {
521     for (auto* sibling = context.nextSibling(); sibling; sibling = sibling->nextSibling()) {
522         if (!nodeSet.contains(sibling))
523             return sibling;
524     }
525     return nullptr;
526 }
527
528 ExceptionOr<RefPtr<Node>> Node::convertNodesOrStringsIntoNode(Vector<NodeOrString>&& nodeOrStringVector)
529 {
530     if (nodeOrStringVector.isEmpty())
531         return nullptr;
532
533     Vector<Ref<Node>> nodes;
534     nodes.reserveInitialCapacity(nodeOrStringVector.size());
535     for (auto& variant : nodeOrStringVector) {
536         WTF::switchOn(variant,
537             [&](RefPtr<Node>& node) { nodes.uncheckedAppend(*node.get()); },
538             [&](String& string) { nodes.uncheckedAppend(Text::create(document(), string)); }
539         );
540     }
541
542     if (nodes.size() == 1)
543         return RefPtr<Node> { WTFMove(nodes.first()) };
544
545     auto nodeToReturn = DocumentFragment::create(document());
546     for (auto& node : nodes) {
547         auto appendResult = nodeToReturn->appendChild(node);
548         if (appendResult.hasException())
549             return appendResult.releaseException();
550     }
551     return RefPtr<Node> { WTFMove(nodeToReturn) };
552 }
553
554 ExceptionOr<void> Node::before(Vector<NodeOrString>&& nodeOrStringVector)
555 {
556     RefPtr<ContainerNode> parent = parentNode();
557     if (!parent)
558         return { };
559
560     auto nodeSet = nodeSetPreTransformedFromNodeOrStringVector(nodeOrStringVector);
561     auto viablePreviousSibling = firstPrecedingSiblingNotInNodeSet(*this, nodeSet);
562
563     auto result = convertNodesOrStringsIntoNode(WTFMove(nodeOrStringVector));
564     if (result.hasException())
565         return result.releaseException();
566     auto node = result.releaseReturnValue();
567     if (!node)
568         return { };
569
570     if (viablePreviousSibling)
571         viablePreviousSibling = viablePreviousSibling->nextSibling();
572     else
573         viablePreviousSibling = parent->firstChild();
574
575     return parent->insertBefore(*node, viablePreviousSibling.get());
576 }
577
578 ExceptionOr<void> Node::after(Vector<NodeOrString>&& nodeOrStringVector)
579 {
580     RefPtr<ContainerNode> parent = parentNode();
581     if (!parent)
582         return { };
583
584     auto nodeSet = nodeSetPreTransformedFromNodeOrStringVector(nodeOrStringVector);
585     auto viableNextSibling = firstFollowingSiblingNotInNodeSet(*this, nodeSet);
586
587     auto result = convertNodesOrStringsIntoNode(WTFMove(nodeOrStringVector));
588     if (result.hasException())
589         return result.releaseException();
590     auto node = result.releaseReturnValue();
591     if (!node)
592         return { };
593
594     return parent->insertBefore(*node, viableNextSibling.get());
595 }
596
597 ExceptionOr<void> Node::replaceWith(Vector<NodeOrString>&& nodeOrStringVector)
598 {
599     RefPtr<ContainerNode> parent = parentNode();
600     if (!parent)
601         return { };
602
603     auto nodeSet = nodeSetPreTransformedFromNodeOrStringVector(nodeOrStringVector);
604     auto viableNextSibling = firstFollowingSiblingNotInNodeSet(*this, nodeSet);
605
606     auto result = convertNodesOrStringsIntoNode(WTFMove(nodeOrStringVector));
607     if (result.hasException())
608         return result.releaseException();
609
610     if (parentNode() == parent) {
611         if (auto node = result.releaseReturnValue())
612             return parent->replaceChild(*node, *this);
613         return parent->removeChild(*this);
614     }
615
616     if (auto node = result.releaseReturnValue())
617         return parent->insertBefore(*node, viableNextSibling.get());
618     return { };
619 }
620
621 ExceptionOr<void> Node::remove()
622 {
623     auto* parent = parentNode();
624     if (!parent)
625         return { };
626     return parent->removeChild(*this);
627 }
628
629 void Node::normalize()
630 {
631     // Go through the subtree beneath us, normalizing all nodes. This means that
632     // any two adjacent text nodes are merged and any empty text nodes are removed.
633
634     RefPtr<Node> node = this;
635     while (Node* firstChild = node->firstChild())
636         node = firstChild;
637     while (node) {
638         NodeType type = node->nodeType();
639         if (type == ELEMENT_NODE)
640             downcast<Element>(*node).normalizeAttributes();
641
642         if (node == this)
643             break;
644
645         if (type != TEXT_NODE) {
646             node = NodeTraversal::nextPostOrder(*node);
647             continue;
648         }
649
650         RefPtr<Text> text = downcast<Text>(node.get());
651
652         // Remove empty text nodes.
653         if (!text->length()) {
654             // Care must be taken to get the next node before removing the current node.
655             node = NodeTraversal::nextPostOrder(*node);
656             text->remove();
657             continue;
658         }
659
660         // Merge text nodes.
661         while (Node* nextSibling = node->nextSibling()) {
662             if (nextSibling->nodeType() != TEXT_NODE)
663                 break;
664             Ref<Text> nextText = downcast<Text>(*nextSibling);
665
666             // Remove empty text nodes.
667             if (!nextText->length()) {
668                 nextText->remove();
669                 continue;
670             }
671
672             // Both non-empty text nodes. Merge them.
673             unsigned offset = text->length();
674             text->appendData(nextText->data());
675             document().textNodesMerged(nextText, offset);
676             nextText->remove();
677         }
678
679         node = NodeTraversal::nextPostOrder(*node);
680     }
681 }
682
683 ExceptionOr<Ref<Node>> Node::cloneNodeForBindings(bool deep)
684 {
685     if (UNLIKELY(isShadowRoot()))
686         return Exception { NotSupportedError };
687     return cloneNode(deep);
688 }
689
690 const AtomicString& Node::prefix() const
691 {
692     // For nodes other than elements and attributes, the prefix is always null
693     return nullAtom();
694 }
695
696 ExceptionOr<void> Node::setPrefix(const AtomicString&)
697 {
698     // The spec says that for nodes other than elements and attributes, prefix is always null.
699     // It does not say what to do when the user tries to set the prefix on another type of
700     // node, however Mozilla throws a NamespaceError exception.
701     return Exception { NamespaceError };
702 }
703
704 const AtomicString& Node::localName() const
705 {
706     return nullAtom();
707 }
708
709 const AtomicString& Node::namespaceURI() const
710 {
711     return nullAtom();
712 }
713
714 bool Node::isContentEditable()
715 {
716     return computeEditability(UserSelectAllDoesNotAffectEditability, ShouldUpdateStyle::Update) != Editability::ReadOnly;
717 }
718
719 bool Node::isContentRichlyEditable()
720 {
721     return computeEditability(UserSelectAllIsAlwaysNonEditable, ShouldUpdateStyle::Update) == Editability::CanEditRichly;
722 }
723
724 void Node::inspect()
725 {
726     if (document().page())
727         document().page()->inspectorController().inspect(this);
728 }
729
730 static Node::Editability computeEditabilityFromComputedStyle(const Node& startNode, Node::UserSelectAllTreatment treatment)
731 {
732     // Ideally we'd call ASSERT(!needsStyleRecalc()) here, but
733     // ContainerNode::setFocus() calls invalidateStyleForSubtree(), so the assertion
734     // would fire in the middle of Document::setFocusedElement().
735
736     for (const Node* node = &startNode; node; node = node->parentNode()) {
737         auto* style = node->isDocumentNode() ? node->renderStyle() : const_cast<Node*>(node)->computedStyle();
738         if (!style)
739             continue;
740         if (style->display() == DisplayType::None)
741             continue;
742 #if ENABLE(USERSELECT_ALL)
743         // Elements with user-select: all style are considered atomic
744         // therefore non editable.
745         if (treatment == Node::UserSelectAllIsAlwaysNonEditable && style->userSelect() == UserSelect::All)
746             return Node::Editability::ReadOnly;
747 #else
748         UNUSED_PARAM(treatment);
749 #endif
750         switch (style->userModify()) {
751         case UserModify::ReadOnly:
752             return Node::Editability::ReadOnly;
753         case UserModify::ReadWrite:
754             return Node::Editability::CanEditRichly;
755         case UserModify::ReadWritePlaintextOnly:
756             return Node::Editability::CanEditPlainText;
757         }
758         ASSERT_NOT_REACHED();
759         return Node::Editability::ReadOnly;
760     }
761     return Node::Editability::ReadOnly;
762 }
763
764 Node::Editability Node::computeEditability(UserSelectAllTreatment treatment, ShouldUpdateStyle shouldUpdateStyle) const
765 {
766     if (!document().hasLivingRenderTree() || isPseudoElement())
767         return Editability::ReadOnly;
768
769     if (isInShadowTree())
770         return HTMLElement::editabilityFromContentEditableAttr(*this);
771
772     if (document().frame() && document().frame()->page() && document().frame()->page()->isEditable())
773         return Editability::CanEditRichly;
774
775     if (shouldUpdateStyle == ShouldUpdateStyle::Update && document().needsStyleRecalc()) {
776         if (!document().usesStyleBasedEditability())
777             return HTMLElement::editabilityFromContentEditableAttr(*this);
778         document().updateStyleIfNeeded();
779     }
780     return computeEditabilityFromComputedStyle(*this, treatment);
781 }
782
783 RenderBox* Node::renderBox() const
784 {
785     RenderObject* renderer = this->renderer();
786     return is<RenderBox>(renderer) ? downcast<RenderBox>(renderer) : nullptr;
787 }
788
789 RenderBoxModelObject* Node::renderBoxModelObject() const
790 {
791     RenderObject* renderer = this->renderer();
792     return is<RenderBoxModelObject>(renderer) ? downcast<RenderBoxModelObject>(renderer) : nullptr;
793 }
794     
795 LayoutRect Node::renderRect(bool* isReplaced)
796 {    
797     RenderObject* hitRenderer = this->renderer();
798     ASSERT(hitRenderer);
799     RenderObject* renderer = hitRenderer;
800     while (renderer && !renderer->isBody() && !renderer->isDocumentElementRenderer()) {
801         if (renderer->isRenderBlock() || renderer->isInlineBlockOrInlineTable() || renderer->isReplaced()) {
802             *isReplaced = renderer->isReplaced();
803             return renderer->absoluteBoundingBoxRect();
804         }
805         renderer = renderer->parent();
806     }
807     return LayoutRect();    
808 }
809
810 void Node::refEventTarget()
811 {
812     ref();
813 }
814
815 void Node::derefEventTarget()
816 {
817     deref();
818 }
819
820 void Node::adjustStyleValidity(Style::Validity validity, Style::InvalidationMode mode)
821 {
822     if (validity > styleValidity()) {
823         m_nodeFlags &= ~StyleValidityMask;
824         m_nodeFlags |= static_cast<unsigned>(validity) << StyleValidityShift;
825     }
826     if (mode == Style::InvalidationMode::RecompositeLayer)
827         setFlag(StyleResolutionShouldRecompositeLayerFlag);
828 }
829
830 inline void Node::updateAncestorsForStyleRecalc()
831 {
832     auto composedAncestors = composedTreeAncestors(*this);
833     auto it = composedAncestors.begin();
834     auto end = composedAncestors.end();
835     if (it != end) {
836         it->setDirectChildNeedsStyleRecalc();
837
838         for (; it != end; ++it) {
839             // Iterator skips over shadow roots.
840             if (auto* shadowRoot = it->shadowRoot())
841                 shadowRoot->setChildNeedsStyleRecalc();
842             if (it->childNeedsStyleRecalc())
843                 break;
844             it->setChildNeedsStyleRecalc();
845         }
846     }
847
848     auto* documentElement = document().documentElement();
849     if (!documentElement)
850         return;
851     if (!documentElement->childNeedsStyleRecalc() && !documentElement->needsStyleRecalc())
852         return;
853     document().setChildNeedsStyleRecalc();
854     document().scheduleStyleRecalc();
855 }
856
857 void Node::invalidateStyle(Style::Validity validity, Style::InvalidationMode mode)
858 {
859     ASSERT(validity != Style::Validity::Valid);
860     if (!inRenderedDocument())
861         return;
862
863     // FIXME: This should eventually be an ASSERT.
864     if (document().inRenderTreeUpdate())
865         return;
866
867     // FIXME: Why the second condition?
868     bool markAncestors = styleValidity() == Style::Validity::Valid || validity == Style::Validity::SubtreeAndRenderersInvalid;
869
870     adjustStyleValidity(validity, mode);
871
872     if (markAncestors)
873         updateAncestorsForStyleRecalc();
874 }
875
876 unsigned Node::computeNodeIndex() const
877 {
878     unsigned count = 0;
879     for (Node* sibling = previousSibling(); sibling; sibling = sibling->previousSibling())
880         ++count;
881     return count;
882 }
883
884 template<unsigned type>
885 bool shouldInvalidateNodeListCachesForAttr(const unsigned nodeListCounts[], const QualifiedName& attrName)
886 {
887     if (nodeListCounts[type] && shouldInvalidateTypeOnAttributeChange(static_cast<NodeListInvalidationType>(type), attrName))
888         return true;
889     return shouldInvalidateNodeListCachesForAttr<type + 1>(nodeListCounts, attrName);
890 }
891
892 template<>
893 bool shouldInvalidateNodeListCachesForAttr<numNodeListInvalidationTypes>(const unsigned[], const QualifiedName&)
894 {
895     return false;
896 }
897
898 inline bool Document::shouldInvalidateNodeListAndCollectionCaches() const
899 {
900     for (int type = 0; type < numNodeListInvalidationTypes; ++type) {
901         if (m_nodeListAndCollectionCounts[type])
902             return true;
903     }
904     return false;
905 }
906
907 inline bool Document::shouldInvalidateNodeListAndCollectionCachesForAttribute(const QualifiedName& attrName) const
908 {
909     return shouldInvalidateNodeListCachesForAttr<DoNotInvalidateOnAttributeChanges + 1>(m_nodeListAndCollectionCounts, attrName);
910 }
911
912 template <typename InvalidationFunction>
913 void Document::invalidateNodeListAndCollectionCaches(InvalidationFunction invalidate)
914 {
915     for (auto* list : copyToVectorSpecialization<Vector<LiveNodeList*, 8>>(m_listsInvalidatedAtDocument))
916         invalidate(*list);
917
918     for (auto* collection : copyToVectorSpecialization<Vector<HTMLCollection*, 8>>(m_collectionsInvalidatedAtDocument))
919         invalidate(*collection);
920 }
921
922 void Node::invalidateNodeListAndCollectionCachesInAncestors()
923 {
924     if (hasRareData()) {
925         if (auto* lists = rareData()->nodeLists())
926             lists->clearChildNodeListCache();
927     }
928
929     if (!document().shouldInvalidateNodeListAndCollectionCaches())
930         return;
931
932     document().invalidateNodeListAndCollectionCaches([](auto& list) {
933         list.invalidateCache();
934     });
935
936     for (auto* node = this; node; node = node->parentNode()) {
937         if (!node->hasRareData())
938             continue;
939
940         if (auto* lists = node->rareData()->nodeLists())
941             lists->invalidateCaches();
942     }
943 }
944
945 void Node::invalidateNodeListAndCollectionCachesInAncestorsForAttribute(const QualifiedName& attrName)
946 {
947     ASSERT(is<Element>(*this));
948
949     if (!document().shouldInvalidateNodeListAndCollectionCachesForAttribute(attrName))
950         return;
951
952     document().invalidateNodeListAndCollectionCaches([&attrName](auto& list) {
953         list.invalidateCacheForAttribute(attrName);
954     });
955
956     for (auto* node = this; node; node = node->parentNode()) {
957         if (!node->hasRareData())
958             continue;
959
960         if (auto* lists = node->rareData()->nodeLists())
961             lists->invalidateCachesForAttribute(attrName);
962     }
963 }
964
965 NodeListsNodeData* Node::nodeLists()
966 {
967     return hasRareData() ? rareData()->nodeLists() : nullptr;
968 }
969
970 void Node::clearNodeLists()
971 {
972     rareData()->clearNodeLists();
973 }
974
975 ExceptionOr<void> Node::checkSetPrefix(const AtomicString& prefix)
976 {
977     // Perform error checking as required by spec for setting Node.prefix. Used by
978     // Element::setPrefix() and Attr::setPrefix()
979
980     if (!prefix.isEmpty() && !Document::isValidName(prefix))
981         return Exception { InvalidCharacterError };
982
983     // FIXME: Raise NamespaceError if prefix is malformed per the Namespaces in XML specification.
984
985     auto& namespaceURI = this->namespaceURI();
986     if (namespaceURI.isEmpty() && !prefix.isEmpty())
987         return Exception { NamespaceError };
988     if (prefix == xmlAtom() && namespaceURI != XMLNames::xmlNamespaceURI)
989         return Exception { NamespaceError };
990
991     // Attribute-specific checks are in Attr::setPrefix().
992
993     return { };
994 }
995
996 bool Node::isDescendantOf(const Node& other) const
997 {
998     // Return true if other is an ancestor of this, otherwise false
999     if (!other.hasChildNodes() || isConnected() != other.isConnected())
1000         return false;
1001     if (other.isDocumentNode())
1002         return &document() == &other && !isDocumentNode() && isConnected();
1003     for (const auto* ancestor = parentNode(); ancestor; ancestor = ancestor->parentNode()) {
1004         if (ancestor == &other)
1005             return true;
1006     }
1007     return false;
1008 }
1009
1010 bool Node::isDescendantOrShadowDescendantOf(const Node* other) const
1011 {
1012     // FIXME: This element's shadow tree's host could be inside another shadow tree.
1013     // This function doesn't handle that case correctly. Maybe share code with
1014     // the containsIncludingShadowDOM function?
1015     return other && (isDescendantOf(*other) || other->contains(shadowHost()));
1016 }
1017
1018 bool Node::contains(const Node* node) const
1019 {
1020     return this == node || (node && node->isDescendantOf(*this));
1021 }
1022
1023 bool Node::containsIncludingShadowDOM(const Node* node) const
1024 {
1025     for (; node; node = node->parentOrShadowHostNode()) {
1026         if (node == this)
1027             return true;
1028     }
1029     return false;
1030 }
1031
1032 bool Node::containsIncludingHostElements(const Node* node) const
1033 {
1034     while (node) {
1035         if (node == this)
1036             return true;
1037         if (is<DocumentFragment>(*node) && downcast<DocumentFragment>(*node).isTemplateContent())
1038             node = static_cast<const TemplateContentDocumentFragment*>(node)->host();
1039         else
1040             node = node->parentOrShadowHostNode();
1041     }
1042     return false;
1043 }
1044
1045 Node* Node::pseudoAwarePreviousSibling() const
1046 {
1047     Element* parentOrHost = is<PseudoElement>(*this) ? downcast<PseudoElement>(*this).hostElement() : parentElement();
1048     if (parentOrHost && !previousSibling()) {
1049         if (isAfterPseudoElement() && parentOrHost->lastChild())
1050             return parentOrHost->lastChild();
1051         if (!isBeforePseudoElement())
1052             return parentOrHost->beforePseudoElement();
1053     }
1054     return previousSibling();
1055 }
1056
1057 Node* Node::pseudoAwareNextSibling() const
1058 {
1059     Element* parentOrHost = is<PseudoElement>(*this) ? downcast<PseudoElement>(*this).hostElement() : parentElement();
1060     if (parentOrHost && !nextSibling()) {
1061         if (isBeforePseudoElement() && parentOrHost->firstChild())
1062             return parentOrHost->firstChild();
1063         if (!isAfterPseudoElement())
1064             return parentOrHost->afterPseudoElement();
1065     }
1066     return nextSibling();
1067 }
1068
1069 Node* Node::pseudoAwareFirstChild() const
1070 {
1071     if (is<Element>(*this)) {
1072         const Element& currentElement = downcast<Element>(*this);
1073         Node* first = currentElement.beforePseudoElement();
1074         if (first)
1075             return first;
1076         first = currentElement.firstChild();
1077         if (!first)
1078             first = currentElement.afterPseudoElement();
1079         return first;
1080     }
1081     return firstChild();
1082 }
1083
1084 Node* Node::pseudoAwareLastChild() const
1085 {
1086     if (is<Element>(*this)) {
1087         const Element& currentElement = downcast<Element>(*this);
1088         Node* last = currentElement.afterPseudoElement();
1089         if (last)
1090             return last;
1091         last = currentElement.lastChild();
1092         if (!last)
1093             last = currentElement.beforePseudoElement();
1094         return last;
1095     }
1096     return lastChild();
1097 }
1098
1099 const RenderStyle* Node::computedStyle(PseudoId pseudoElementSpecifier)
1100 {
1101     auto* composedParent = composedTreeAncestors(*this).first();
1102     if (!composedParent)
1103         return nullptr;
1104     return composedParent->computedStyle(pseudoElementSpecifier);
1105 }
1106
1107 int Node::maxCharacterOffset() const
1108 {
1109     ASSERT_NOT_REACHED();
1110     return 0;
1111 }
1112
1113 // FIXME: Shouldn't these functions be in the editing code?  Code that asks questions about HTML in the core DOM class
1114 // is obviously misplaced.
1115 bool Node::canStartSelection() const
1116 {
1117     if (hasEditableStyle())
1118         return true;
1119
1120     if (renderer()) {
1121         const RenderStyle& style = renderer()->style();
1122         // We allow selections to begin within an element that has -webkit-user-select: none set,
1123         // but if the element is draggable then dragging should take priority over selection.
1124         if (style.userDrag() == UserDrag::Element && style.userSelect() == UserSelect::None)
1125             return false;
1126     }
1127     return parentOrShadowHostNode() ? parentOrShadowHostNode()->canStartSelection() : true;
1128 }
1129
1130 Element* Node::shadowHost() const
1131 {
1132     if (ShadowRoot* root = containingShadowRoot())
1133         return root->host();
1134     return nullptr;
1135 }
1136
1137 ShadowRoot* Node::containingShadowRoot() const
1138 {
1139     ContainerNode& root = treeScope().rootNode();
1140     return is<ShadowRoot>(root) ? downcast<ShadowRoot>(&root) : nullptr;
1141 }
1142
1143 #if !ASSERT_DISABLED
1144 // https://dom.spec.whatwg.org/#concept-closed-shadow-hidden
1145 static bool isClosedShadowHiddenUsingSpecDefinition(const Node& A, const Node& B)
1146 {
1147     return A.isInShadowTree()
1148         && !A.rootNode().containsIncludingShadowDOM(&B)
1149         && (A.containingShadowRoot()->mode() != ShadowRootMode::Open || isClosedShadowHiddenUsingSpecDefinition(*A.shadowHost(), B));
1150 }
1151 #endif
1152
1153 // http://w3c.github.io/webcomponents/spec/shadow/#dfn-unclosed-node
1154 bool Node::isClosedShadowHidden(const Node& otherNode) const
1155 {
1156     // Use Vector instead of HashSet since we expect the number of ancestor tree scopes to be small.
1157     Vector<TreeScope*, 8> ancestorScopesOfThisNode;
1158
1159     for (auto* scope = &treeScope(); scope; scope = scope->parentTreeScope())
1160         ancestorScopesOfThisNode.append(scope);
1161
1162     for (auto* treeScopeThatCanAccessOtherNode = &otherNode.treeScope(); treeScopeThatCanAccessOtherNode; treeScopeThatCanAccessOtherNode = treeScopeThatCanAccessOtherNode->parentTreeScope()) {
1163         for (auto* scope : ancestorScopesOfThisNode) {
1164             if (scope == treeScopeThatCanAccessOtherNode) {
1165                 ASSERT(!isClosedShadowHiddenUsingSpecDefinition(otherNode, *this));
1166                 return false; // treeScopeThatCanAccessOtherNode is a shadow-including inclusive ancestor of this node.
1167             }
1168         }
1169         auto& root = treeScopeThatCanAccessOtherNode->rootNode();
1170         if (is<ShadowRoot>(root) && downcast<ShadowRoot>(root).mode() != ShadowRootMode::Open)
1171             break;
1172     }
1173
1174     ASSERT(isClosedShadowHiddenUsingSpecDefinition(otherNode, *this));
1175     return true;
1176 }
1177
1178 static inline ShadowRoot* parentShadowRoot(const Node& node)
1179 {
1180     if (auto* parent = node.parentElement())
1181         return parent->shadowRoot();
1182     return nullptr;
1183 }
1184
1185 HTMLSlotElement* Node::assignedSlot() const
1186 {
1187     if (auto* shadowRoot = parentShadowRoot(*this))
1188         return shadowRoot->findAssignedSlot(*this);
1189     return nullptr;
1190 }
1191
1192 HTMLSlotElement* Node::assignedSlotForBindings() const
1193 {
1194     auto* shadowRoot = parentShadowRoot(*this);
1195     if (shadowRoot && shadowRoot->mode() == ShadowRootMode::Open)
1196         return shadowRoot->findAssignedSlot(*this);
1197     return nullptr;
1198 }
1199
1200 ContainerNode* Node::parentInComposedTree() const
1201 {
1202     ASSERT(isMainThreadOrGCThread());
1203     if (auto* slot = assignedSlot())
1204         return slot;
1205     if (is<ShadowRoot>(*this))
1206         return downcast<ShadowRoot>(*this).host();
1207     return parentNode();
1208 }
1209
1210 Element* Node::parentElementInComposedTree() const
1211 {
1212     if (auto* slot = assignedSlot())
1213         return slot;
1214     if (is<PseudoElement>(*this))
1215         return downcast<PseudoElement>(*this).hostElement();
1216     if (auto* parent = parentNode()) {
1217         if (is<ShadowRoot>(*parent))
1218             return downcast<ShadowRoot>(*parent).host();
1219         if (is<Element>(*parent))
1220             return downcast<Element>(parent);
1221     }
1222     return nullptr;
1223 }
1224
1225 bool Node::isInUserAgentShadowTree() const
1226 {
1227     auto* shadowRoot = containingShadowRoot();
1228     return shadowRoot && shadowRoot->mode() == ShadowRootMode::UserAgent;
1229 }
1230
1231 Node* Node::nonBoundaryShadowTreeRootNode()
1232 {
1233     ASSERT(!isShadowRoot());
1234     Node* root = this;
1235     while (root) {
1236         if (root->isShadowRoot())
1237             return root;
1238         Node* parent = root->parentNodeGuaranteedHostFree();
1239         if (parent && parent->isShadowRoot())
1240             return root;
1241         root = parent;
1242     }
1243     return 0;
1244 }
1245
1246 ContainerNode* Node::nonShadowBoundaryParentNode() const
1247 {
1248     ContainerNode* parent = parentNode();
1249     return parent && !parent->isShadowRoot() ? parent : nullptr;
1250 }
1251
1252 Element* Node::parentOrShadowHostElement() const
1253 {
1254     ContainerNode* parent = parentOrShadowHostNode();
1255     if (!parent)
1256         return nullptr;
1257
1258     if (is<ShadowRoot>(*parent))
1259         return downcast<ShadowRoot>(*parent).host();
1260
1261     if (!is<Element>(*parent))
1262         return nullptr;
1263
1264     return downcast<Element>(parent);
1265 }
1266
1267 Node& Node::traverseToRootNode() const
1268 {
1269     Node* node = const_cast<Node*>(this);
1270     Node* highest = node;
1271     for (; node; node = node->parentNode())
1272         highest = node;
1273     return *highest;
1274 }
1275
1276 // https://dom.spec.whatwg.org/#concept-shadow-including-root
1277 Node& Node::shadowIncludingRoot() const
1278 {
1279     auto& root = rootNode();
1280     if (!is<ShadowRoot>(root))
1281         return root;
1282     auto* host = downcast<ShadowRoot>(root).host();
1283     return host ? host->shadowIncludingRoot() : root;
1284 }
1285
1286 Node& Node::getRootNode(const GetRootNodeOptions& options) const
1287 {
1288     return options.composed ? shadowIncludingRoot() : rootNode();
1289 }
1290
1291 Node::InsertedIntoAncestorResult Node::insertedIntoAncestor(InsertionType insertionType, ContainerNode& parentOfInsertedTree)
1292 {
1293     if (insertionType.connectedToDocument)
1294         setFlag(IsConnectedFlag);
1295     if (parentOfInsertedTree.isInShadowTree())
1296         setFlag(IsInShadowTreeFlag);
1297
1298     invalidateStyle(Style::Validity::SubtreeAndRenderersInvalid);
1299
1300     return InsertedIntoAncestorResult::Done;
1301 }
1302
1303 void Node::removedFromAncestor(RemovalType removalType, ContainerNode&)
1304 {
1305     if (removalType.disconnectedFromDocument)
1306         clearFlag(IsConnectedFlag);
1307     if (isInShadowTree() && !treeScope().rootNode().isShadowRoot())
1308         clearFlag(IsInShadowTreeFlag);
1309 }
1310
1311 bool Node::isRootEditableElement() const
1312 {
1313     return hasEditableStyle() && isElementNode() && (!parentNode() || !parentNode()->hasEditableStyle()
1314         || !parentNode()->isElementNode() || hasTagName(bodyTag));
1315 }
1316
1317 Element* Node::rootEditableElement() const
1318 {
1319     Element* result = nullptr;
1320     for (Node* node = const_cast<Node*>(this); node && node->hasEditableStyle(); node = node->parentNode()) {
1321         if (is<Element>(*node))
1322             result = downcast<Element>(node);
1323         if (is<HTMLBodyElement>(*node))
1324             break;
1325     }
1326     return result;
1327 }
1328
1329 // FIXME: End of obviously misplaced HTML editing functions.  Try to move these out of Node.
1330
1331 Document* Node::ownerDocument() const
1332 {
1333     Document* document = &this->document();
1334     return document == this ? nullptr : document;
1335 }
1336
1337 const URL& Node::baseURI() const
1338 {
1339     auto& url = document().baseURL();
1340     return url.isNull() ? WTF::blankURL() : url;
1341 }
1342
1343 bool Node::isEqualNode(Node* other) const
1344 {
1345     if (!other)
1346         return false;
1347     
1348     NodeType nodeType = this->nodeType();
1349     if (nodeType != other->nodeType())
1350         return false;
1351     
1352     switch (nodeType) {
1353     case Node::DOCUMENT_TYPE_NODE: {
1354         auto& thisDocType = downcast<DocumentType>(*this);
1355         auto& otherDocType = downcast<DocumentType>(*other);
1356         if (thisDocType.name() != otherDocType.name())
1357             return false;
1358         if (thisDocType.publicId() != otherDocType.publicId())
1359             return false;
1360         if (thisDocType.systemId() != otherDocType.systemId())
1361             return false;
1362         break;
1363         }
1364     case Node::ELEMENT_NODE: {
1365         auto& thisElement = downcast<Element>(*this);
1366         auto& otherElement = downcast<Element>(*other);
1367         if (thisElement.tagQName() != otherElement.tagQName())
1368             return false;
1369         if (!thisElement.hasEquivalentAttributes(otherElement))
1370             return false;
1371         break;
1372         }
1373     case Node::PROCESSING_INSTRUCTION_NODE: {
1374         auto& thisProcessingInstruction = downcast<ProcessingInstruction>(*this);
1375         auto& otherProcessingInstruction = downcast<ProcessingInstruction>(*other);
1376         if (thisProcessingInstruction.target() != otherProcessingInstruction.target())
1377             return false;
1378         if (thisProcessingInstruction.data() != otherProcessingInstruction.data())
1379             return false;
1380         break;
1381         }
1382     case Node::CDATA_SECTION_NODE:
1383     case Node::TEXT_NODE:
1384     case Node::COMMENT_NODE: {
1385         auto& thisCharacterData = downcast<CharacterData>(*this);
1386         auto& otherCharacterData = downcast<CharacterData>(*other);
1387         if (thisCharacterData.data() != otherCharacterData.data())
1388             return false;
1389         break;
1390         }
1391     case Node::ATTRIBUTE_NODE: {
1392         auto& thisAttribute = downcast<Attr>(*this);
1393         auto& otherAttribute = downcast<Attr>(*other);
1394         if (thisAttribute.qualifiedName() != otherAttribute.qualifiedName())
1395             return false;
1396         if (thisAttribute.value() != otherAttribute.value())
1397             return false;
1398         break;
1399         }
1400     case Node::DOCUMENT_NODE:
1401     case Node::DOCUMENT_FRAGMENT_NODE:
1402         break;
1403     }
1404     
1405     Node* child = firstChild();
1406     Node* otherChild = other->firstChild();
1407     
1408     while (child) {
1409         if (!child->isEqualNode(otherChild))
1410             return false;
1411         
1412         child = child->nextSibling();
1413         otherChild = otherChild->nextSibling();
1414     }
1415     
1416     if (otherChild)
1417         return false;
1418     
1419     return true;
1420 }
1421
1422 // https://dom.spec.whatwg.org/#locate-a-namespace
1423 static const AtomicString& locateDefaultNamespace(const Node& node, const AtomicString& prefix)
1424 {
1425     switch (node.nodeType()) {
1426     case Node::ELEMENT_NODE: {
1427         auto& element = downcast<Element>(node);
1428         auto& namespaceURI = element.namespaceURI();
1429         if (!namespaceURI.isNull() && element.prefix() == prefix)
1430             return namespaceURI;
1431
1432         if (element.hasAttributes()) {
1433             for (auto& attribute : element.attributesIterator()) {
1434                 if (attribute.namespaceURI() != XMLNSNames::xmlnsNamespaceURI)
1435                     continue;
1436
1437                 if ((prefix.isNull() && attribute.prefix().isNull() && attribute.localName() == xmlnsAtom()) || (attribute.prefix() == xmlnsAtom() && attribute.localName() == prefix)) {
1438                     auto& result = attribute.value();
1439                     return result.isEmpty() ? nullAtom() : result;
1440                 }
1441             }
1442         }
1443         auto* parent = node.parentElement();
1444         return parent ? locateDefaultNamespace(*parent, prefix) : nullAtom();
1445     }
1446     case Node::DOCUMENT_NODE:
1447         if (auto* documentElement = downcast<Document>(node).documentElement())
1448             return locateDefaultNamespace(*documentElement, prefix);
1449         return nullAtom();
1450     case Node::DOCUMENT_TYPE_NODE:
1451     case Node::DOCUMENT_FRAGMENT_NODE:
1452         return nullAtom();
1453     case Node::ATTRIBUTE_NODE:
1454         if (auto* ownerElement = downcast<Attr>(node).ownerElement())
1455             return locateDefaultNamespace(*ownerElement, prefix);
1456         return nullAtom();
1457     default:
1458         if (auto* parent = node.parentElement())
1459             return locateDefaultNamespace(*parent, prefix);
1460         return nullAtom();
1461     }
1462 }
1463
1464 // https://dom.spec.whatwg.org/#dom-node-isdefaultnamespace
1465 bool Node::isDefaultNamespace(const AtomicString& potentiallyEmptyNamespace) const
1466 {
1467     const AtomicString& namespaceURI = potentiallyEmptyNamespace.isEmpty() ? nullAtom() : potentiallyEmptyNamespace;
1468     return locateDefaultNamespace(*this, nullAtom()) == namespaceURI;
1469 }
1470
1471 // https://dom.spec.whatwg.org/#dom-node-lookupnamespaceuri
1472 const AtomicString& Node::lookupNamespaceURI(const AtomicString& potentiallyEmptyPrefix) const
1473 {
1474     const AtomicString& prefix = potentiallyEmptyPrefix.isEmpty() ? nullAtom() : potentiallyEmptyPrefix;
1475     return locateDefaultNamespace(*this, prefix);
1476 }
1477
1478 // https://dom.spec.whatwg.org/#locate-a-namespace-prefix
1479 static const AtomicString& locateNamespacePrefix(const Element& element, const AtomicString& namespaceURI)
1480 {
1481     if (element.namespaceURI() == namespaceURI)
1482         return element.prefix();
1483
1484     if (element.hasAttributes()) {
1485         for (auto& attribute : element.attributesIterator()) {
1486             if (attribute.prefix() == xmlnsAtom() && attribute.value() == namespaceURI)
1487                 return attribute.localName();
1488         }
1489     }
1490     auto* parent = element.parentElement();
1491     return parent ? locateNamespacePrefix(*parent, namespaceURI) : nullAtom();
1492 }
1493
1494 // https://dom.spec.whatwg.org/#dom-node-lookupprefix
1495 const AtomicString& Node::lookupPrefix(const AtomicString& namespaceURI) const
1496 {
1497     if (namespaceURI.isEmpty())
1498         return nullAtom();
1499     
1500     switch (nodeType()) {
1501     case ELEMENT_NODE:
1502         return locateNamespacePrefix(downcast<Element>(*this), namespaceURI);
1503     case DOCUMENT_NODE:
1504         if (auto* documentElement = downcast<Document>(*this).documentElement())
1505             return locateNamespacePrefix(*documentElement, namespaceURI);
1506         return nullAtom();
1507     case DOCUMENT_FRAGMENT_NODE:
1508     case DOCUMENT_TYPE_NODE:
1509         return nullAtom();
1510     case ATTRIBUTE_NODE:
1511         if (auto* ownerElement = downcast<Attr>(*this).ownerElement())
1512             return locateNamespacePrefix(*ownerElement, namespaceURI);
1513         return nullAtom();
1514     default:
1515         if (auto* parent = parentElement())
1516             return locateNamespacePrefix(*parent, namespaceURI);
1517         return nullAtom();
1518     }
1519 }
1520
1521 static void appendTextContent(const Node* node, bool convertBRsToNewlines, bool& isNullString, StringBuilder& content)
1522 {
1523     switch (node->nodeType()) {
1524     case Node::TEXT_NODE:
1525     case Node::CDATA_SECTION_NODE:
1526     case Node::COMMENT_NODE:
1527         isNullString = false;
1528         content.append(downcast<CharacterData>(*node).data());
1529         break;
1530
1531     case Node::PROCESSING_INSTRUCTION_NODE:
1532         isNullString = false;
1533         content.append(downcast<ProcessingInstruction>(*node).data());
1534         break;
1535     
1536     case Node::ATTRIBUTE_NODE:
1537         isNullString = false;
1538         content.append(downcast<Attr>(*node).value());
1539         break;
1540
1541     case Node::ELEMENT_NODE:
1542         if (node->hasTagName(brTag) && convertBRsToNewlines) {
1543             isNullString = false;
1544             content.append('\n');
1545             break;
1546         }
1547         FALLTHROUGH;
1548     case Node::DOCUMENT_FRAGMENT_NODE:
1549         isNullString = false;
1550         for (Node* child = node->firstChild(); child; child = child->nextSibling()) {
1551             if (child->nodeType() == Node::COMMENT_NODE || child->nodeType() == Node::PROCESSING_INSTRUCTION_NODE)
1552                 continue;
1553             appendTextContent(child, convertBRsToNewlines, isNullString, content);
1554         }
1555         break;
1556
1557     case Node::DOCUMENT_NODE:
1558     case Node::DOCUMENT_TYPE_NODE:
1559         break;
1560     }
1561 }
1562
1563 String Node::textContent(bool convertBRsToNewlines) const
1564 {
1565     StringBuilder content;
1566     bool isNullString = true;
1567     appendTextContent(this, convertBRsToNewlines, isNullString, content);
1568     return isNullString ? String() : content.toString();
1569 }
1570
1571 ExceptionOr<void> Node::setTextContent(const String& text)
1572 {           
1573     switch (nodeType()) {
1574     case ATTRIBUTE_NODE:
1575     case TEXT_NODE:
1576     case CDATA_SECTION_NODE:
1577     case COMMENT_NODE:
1578     case PROCESSING_INSTRUCTION_NODE:
1579         return setNodeValue(text);
1580     case ELEMENT_NODE:
1581     case DOCUMENT_FRAGMENT_NODE: {
1582         auto& container = downcast<ContainerNode>(*this);
1583         if (text.isEmpty())
1584             container.replaceAllChildren(nullptr);
1585         else
1586             container.replaceAllChildren(document().createTextNode(text));
1587         return { };
1588     }
1589     case DOCUMENT_NODE:
1590     case DOCUMENT_TYPE_NODE:
1591         // Do nothing.
1592         return { };
1593     }
1594     ASSERT_NOT_REACHED();
1595     return { };
1596 }
1597
1598 static SHA1::Digest hashPointer(void* pointer)
1599 {
1600     SHA1 sha1;
1601     sha1.addBytes(reinterpret_cast<const uint8_t*>(&pointer), sizeof(pointer));
1602     SHA1::Digest digest;
1603     sha1.computeHash(digest);
1604     return digest;
1605 }
1606
1607 static inline unsigned short compareDetachedElementsPosition(Node& firstNode, Node& secondNode)
1608 {
1609     // If the 2 nodes are not in the same tree, return the result of adding DOCUMENT_POSITION_DISCONNECTED,
1610     // DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC, and either DOCUMENT_POSITION_PRECEDING or
1611     // DOCUMENT_POSITION_FOLLOWING, with the constraint that this is to be consistent. Whether to return
1612     // DOCUMENT_POSITION_PRECEDING or DOCUMENT_POSITION_FOLLOWING is implemented by comparing cryptographic
1613     // hashes of Node pointers.
1614     // See step 3 in https://dom.spec.whatwg.org/#dom-node-comparedocumentposition
1615     SHA1::Digest firstHash = hashPointer(&firstNode);
1616     SHA1::Digest secondHash = hashPointer(&secondNode);
1617
1618     unsigned short direction = memcmp(firstHash.data(), secondHash.data(), SHA1::hashSize) > 0 ? Node::DOCUMENT_POSITION_PRECEDING : Node::DOCUMENT_POSITION_FOLLOWING;
1619
1620     return Node::DOCUMENT_POSITION_DISCONNECTED | Node::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | direction;
1621 }
1622
1623 unsigned short Node::compareDocumentPosition(Node& otherNode)
1624 {
1625     if (&otherNode == this)
1626         return DOCUMENT_POSITION_EQUIVALENT;
1627     
1628     Attr* attr1 = is<Attr>(*this) ? downcast<Attr>(this) : nullptr;
1629     Attr* attr2 = is<Attr>(otherNode) ? &downcast<Attr>(otherNode) : nullptr;
1630     
1631     Node* start1 = attr1 ? attr1->ownerElement() : this;
1632     Node* start2 = attr2 ? attr2->ownerElement() : &otherNode;
1633     
1634     // If either of start1 or start2 is null, then we are disconnected, since one of the nodes is
1635     // an orphaned attribute node.
1636     if (!start1 || !start2)
1637         return compareDetachedElementsPosition(*this, otherNode);
1638
1639     Vector<Node*, 16> chain1;
1640     Vector<Node*, 16> chain2;
1641     if (attr1)
1642         chain1.append(attr1);
1643     if (attr2)
1644         chain2.append(attr2);
1645     
1646     if (attr1 && attr2 && start1 == start2 && start1) {
1647         // We are comparing two attributes on the same node. Crawl our attribute map and see which one we hit first.
1648         Element* owner1 = attr1->ownerElement();
1649         owner1->synchronizeAllAttributes();
1650         for (const Attribute& attribute : owner1->attributesIterator()) {
1651             // If neither of the two determining nodes is a child node and nodeType is the same for both determining nodes, then an
1652             // implementation-dependent order between the determining nodes is returned. This order is stable as long as no nodes of
1653             // the same nodeType are inserted into or removed from the direct container. This would be the case, for example, 
1654             // when comparing two attributes of the same element, and inserting or removing additional attributes might change 
1655             // the order between existing attributes.
1656             if (attr1->qualifiedName() == attribute.name())
1657                 return DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | DOCUMENT_POSITION_FOLLOWING;
1658             if (attr2->qualifiedName() == attribute.name())
1659                 return DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | DOCUMENT_POSITION_PRECEDING;
1660         }
1661         
1662         ASSERT_NOT_REACHED();
1663         return DOCUMENT_POSITION_DISCONNECTED;
1664     }
1665
1666     // If one node is in the document and the other is not, we must be disconnected.
1667     // If the nodes have different owning documents, they must be disconnected.  Note that we avoid
1668     // comparing Attr nodes here, since they return false from isConnected() all the time (which seems like a bug).
1669     if (start1->isConnected() != start2->isConnected() || &start1->treeScope() != &start2->treeScope())
1670         return compareDetachedElementsPosition(*this, otherNode);
1671
1672     // We need to find a common ancestor container, and then compare the indices of the two immediate children.
1673     Node* current;
1674     for (current = start1; current; current = current->parentNode())
1675         chain1.append(current);
1676     for (current = start2; current; current = current->parentNode())
1677         chain2.append(current);
1678
1679     unsigned index1 = chain1.size();
1680     unsigned index2 = chain2.size();
1681
1682     // If the two elements don't have a common root, they're not in the same tree.
1683     if (chain1[index1 - 1] != chain2[index2 - 1])
1684         return compareDetachedElementsPosition(*this, otherNode);
1685
1686     // Walk the two chains backwards and look for the first difference.
1687     for (unsigned i = std::min(index1, index2); i; --i) {
1688         Node* child1 = chain1[--index1];
1689         Node* child2 = chain2[--index2];
1690         if (child1 != child2) {
1691             // If one of the children is an attribute, it wins.
1692             if (child1->nodeType() == ATTRIBUTE_NODE)
1693                 return DOCUMENT_POSITION_FOLLOWING;
1694             if (child2->nodeType() == ATTRIBUTE_NODE)
1695                 return DOCUMENT_POSITION_PRECEDING;
1696             
1697             if (!child2->nextSibling())
1698                 return DOCUMENT_POSITION_FOLLOWING;
1699             if (!child1->nextSibling())
1700                 return DOCUMENT_POSITION_PRECEDING;
1701
1702             // Otherwise we need to see which node occurs first.  Crawl backwards from child2 looking for child1.
1703             for (Node* child = child2->previousSibling(); child; child = child->previousSibling()) {
1704                 if (child == child1)
1705                     return DOCUMENT_POSITION_FOLLOWING;
1706             }
1707             return DOCUMENT_POSITION_PRECEDING;
1708         }
1709     }
1710     
1711     // There was no difference between the two parent chains, i.e., one was a subset of the other.  The shorter
1712     // chain is the ancestor.
1713     return index1 < index2 ? 
1714                DOCUMENT_POSITION_FOLLOWING | DOCUMENT_POSITION_CONTAINED_BY :
1715                DOCUMENT_POSITION_PRECEDING | DOCUMENT_POSITION_CONTAINS;
1716 }
1717
1718 FloatPoint Node::convertToPage(const FloatPoint& p) const
1719 {
1720     // If there is a renderer, just ask it to do the conversion
1721     if (renderer())
1722         return renderer()->localToAbsolute(p, UseTransforms);
1723     
1724     // Otherwise go up the tree looking for a renderer
1725     if (auto* parent = parentElement())
1726         return parent->convertToPage(p);
1727
1728     // No parent - no conversion needed
1729     return p;
1730 }
1731
1732 FloatPoint Node::convertFromPage(const FloatPoint& p) const
1733 {
1734     // If there is a renderer, just ask it to do the conversion
1735     if (renderer())
1736         return renderer()->absoluteToLocal(p, UseTransforms);
1737
1738     // Otherwise go up the tree looking for a renderer
1739     if (auto* parent = parentElement())
1740         return parent->convertFromPage(p);
1741
1742     // No parent - no conversion needed
1743     return p;
1744 }
1745
1746 #if ENABLE(TREE_DEBUGGING)
1747
1748 static void appendAttributeDesc(const Node* node, StringBuilder& stringBuilder, const QualifiedName& name, const char* attrDesc)
1749 {
1750     if (!is<Element>(*node))
1751         return;
1752
1753     const AtomicString& attr = downcast<Element>(*node).getAttribute(name);
1754     if (attr.isEmpty())
1755         return;
1756
1757     stringBuilder.append(attrDesc);
1758     stringBuilder.append(attr);
1759 }
1760
1761 void Node::showNode(const char* prefix) const
1762 {
1763     if (!prefix)
1764         prefix = "";
1765     if (isTextNode()) {
1766         String value = nodeValue();
1767         value.replaceWithLiteral('\\', "\\\\");
1768         value.replaceWithLiteral('\n', "\\n");
1769         fprintf(stderr, "%s%s\t%p \"%s\"\n", prefix, nodeName().utf8().data(), this, value.utf8().data());
1770     } else {
1771         StringBuilder attrs;
1772         appendAttributeDesc(this, attrs, classAttr, " CLASS=");
1773         appendAttributeDesc(this, attrs, styleAttr, " STYLE=");
1774         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)" : "");
1775     }
1776 }
1777
1778 void Node::showTreeForThis() const
1779 {
1780     showTreeAndMark(this, "*");
1781 }
1782
1783 void Node::showNodePathForThis() const
1784 {
1785     Vector<const Node*, 16> chain;
1786     const Node* node = this;
1787     while (node->parentOrShadowHostNode()) {
1788         chain.append(node);
1789         node = node->parentOrShadowHostNode();
1790     }
1791     for (unsigned index = chain.size(); index > 0; --index) {
1792         const Node* node = chain[index - 1];
1793         if (is<ShadowRoot>(*node)) {
1794             int count = 0;
1795             for (const ShadowRoot* shadowRoot = downcast<ShadowRoot>(node); shadowRoot && shadowRoot != node; shadowRoot = shadowRoot->shadowRoot())
1796                 ++count;
1797             fprintf(stderr, "/#shadow-root[%d]", count);
1798             continue;
1799         }
1800
1801         switch (node->nodeType()) {
1802         case ELEMENT_NODE: {
1803             fprintf(stderr, "/%s", node->nodeName().utf8().data());
1804
1805             const Element& element = downcast<Element>(*node);
1806             const AtomicString& idattr = element.getIdAttribute();
1807             bool hasIdAttr = !idattr.isNull() && !idattr.isEmpty();
1808             if (node->previousSibling() || node->nextSibling()) {
1809                 int count = 0;
1810                 for (Node* previous = node->previousSibling(); previous; previous = previous->previousSibling())
1811                     if (previous->nodeName() == node->nodeName())
1812                         ++count;
1813                 if (hasIdAttr)
1814                     fprintf(stderr, "[@id=\"%s\" and position()=%d]", idattr.string().utf8().data(), count);
1815                 else
1816                     fprintf(stderr, "[%d]", count);
1817             } else if (hasIdAttr)
1818                 fprintf(stderr, "[@id=\"%s\"]", idattr.string().utf8().data());
1819             break;
1820         }
1821         case TEXT_NODE:
1822             fprintf(stderr, "/text()");
1823             break;
1824         case ATTRIBUTE_NODE:
1825             fprintf(stderr, "/@%s", node->nodeName().utf8().data());
1826             break;
1827         default:
1828             break;
1829         }
1830     }
1831     fprintf(stderr, "\n");
1832 }
1833
1834 static void traverseTreeAndMark(const String& baseIndent, const Node* rootNode, const Node* markedNode1, const char* markedLabel1, const Node* markedNode2, const char* markedLabel2)
1835 {
1836     for (const Node* node = rootNode; node; node = NodeTraversal::next(*node)) {
1837         if (node == markedNode1)
1838             fprintf(stderr, "%s", markedLabel1);
1839         if (node == markedNode2)
1840             fprintf(stderr, "%s", markedLabel2);
1841
1842         StringBuilder indent;
1843         indent.append(baseIndent);
1844         for (const Node* tmpNode = node; tmpNode && tmpNode != rootNode; tmpNode = tmpNode->parentOrShadowHostNode())
1845             indent.append('\t');
1846         fprintf(stderr, "%s", indent.toString().utf8().data());
1847         node->showNode();
1848         indent.append('\t');
1849         if (!node->isShadowRoot()) {
1850             if (ShadowRoot* shadowRoot = node->shadowRoot())
1851                 traverseTreeAndMark(indent.toString(), shadowRoot, markedNode1, markedLabel1, markedNode2, markedLabel2);
1852         }
1853     }
1854 }
1855
1856 void Node::showTreeAndMark(const Node* markedNode1, const char* markedLabel1, const Node* markedNode2, const char* markedLabel2) const
1857 {
1858     const Node* rootNode;
1859     const Node* node = this;
1860     while (node->parentOrShadowHostNode() && !node->hasTagName(bodyTag))
1861         node = node->parentOrShadowHostNode();
1862     rootNode = node;
1863
1864     String startingIndent;
1865     traverseTreeAndMark(startingIndent, rootNode, markedNode1, markedLabel1, markedNode2, markedLabel2);
1866 }
1867
1868 void Node::formatForDebugger(char* buffer, unsigned length) const
1869 {
1870     String result;
1871     String s;
1872
1873     s = nodeName();
1874     if (s.isEmpty())
1875         result = "<none>";
1876     else
1877         result = s;
1878
1879     strncpy(buffer, result.utf8().data(), length - 1);
1880 }
1881
1882 static ContainerNode* parentOrShadowHostOrFrameOwner(const Node* node)
1883 {
1884     ContainerNode* parent = node->parentOrShadowHostNode();
1885     if (!parent && node->document().frame())
1886         parent = node->document().frame()->ownerElement();
1887     return parent;
1888 }
1889
1890 static void showSubTreeAcrossFrame(const Node* node, const Node* markedNode, const String& indent)
1891 {
1892     if (node == markedNode)
1893         fputs("*", stderr);
1894     fputs(indent.utf8().data(), stderr);
1895     node->showNode();
1896     if (!node->isShadowRoot()) {
1897         if (node->isFrameOwnerElement())
1898             showSubTreeAcrossFrame(static_cast<const HTMLFrameOwnerElement*>(node)->contentDocument(), markedNode, indent + "\t");
1899         if (ShadowRoot* shadowRoot = node->shadowRoot())
1900             showSubTreeAcrossFrame(shadowRoot, markedNode, indent + "\t");
1901     }
1902     for (Node* child = node->firstChild(); child; child = child->nextSibling())
1903         showSubTreeAcrossFrame(child, markedNode, indent + "\t");
1904 }
1905
1906 void Node::showTreeForThisAcrossFrame() const
1907 {
1908     Node* rootNode = const_cast<Node*>(this);
1909     while (parentOrShadowHostOrFrameOwner(rootNode))
1910         rootNode = parentOrShadowHostOrFrameOwner(rootNode);
1911     showSubTreeAcrossFrame(rootNode, this, "");
1912 }
1913
1914 #endif // ENABLE(TREE_DEBUGGING)
1915
1916 // --------
1917
1918 void NodeListsNodeData::invalidateCaches()
1919 {
1920     for (auto& atomicName : m_atomicNameCaches)
1921         atomicName.value->invalidateCache();
1922
1923     for (auto& collection : m_cachedCollections)
1924         collection.value->invalidateCache();
1925
1926     for (auto& tagCollection : m_tagCollectionNSCache)
1927         tagCollection.value->invalidateCache();
1928 }
1929
1930 void NodeListsNodeData::invalidateCachesForAttribute(const QualifiedName& attrName)
1931 {
1932     for (auto& atomicName : m_atomicNameCaches)
1933         atomicName.value->invalidateCacheForAttribute(attrName);
1934
1935     for (auto& collection : m_cachedCollections)
1936         collection.value->invalidateCacheForAttribute(attrName);
1937 }
1938
1939 void Node::getSubresourceURLs(ListHashSet<URL>& urls) const
1940 {
1941     addSubresourceAttributeURLs(urls);
1942 }
1943
1944 Element* Node::enclosingLinkEventParentOrSelf()
1945 {
1946     for (Node* node = this; node; node = node->parentInComposedTree()) {
1947         // For imagemaps, the enclosing link element is the associated area element not the image itself.
1948         // So we don't let images be the enclosing link element, even though isLink sometimes returns
1949         // true for them.
1950         if (node->isLink() && !is<HTMLImageElement>(*node))
1951             return downcast<Element>(node);
1952     }
1953
1954     return nullptr;
1955 }
1956
1957 EventTargetInterface Node::eventTargetInterface() const
1958 {
1959     return NodeEventTargetInterfaceType;
1960 }
1961
1962 template <typename MoveNodeFunction, typename MoveShadowRootFunction>
1963 static void traverseSubtreeToUpdateTreeScope(Node& root, MoveNodeFunction moveNode, MoveShadowRootFunction moveShadowRoot)
1964 {
1965     for (Node* node = &root; node; node = NodeTraversal::next(*node, &root)) {
1966         moveNode(*node);
1967
1968         if (!is<Element>(*node))
1969             continue;
1970         Element& element = downcast<Element>(*node);
1971
1972         if (element.hasSyntheticAttrChildNodes()) {
1973             for (auto& attr : element.attrNodeList())
1974                 moveNode(*attr);
1975         }
1976
1977         if (auto* shadow = element.shadowRoot())
1978             moveShadowRoot(*shadow);
1979     }
1980 }
1981
1982 inline void Node::moveShadowTreeToNewDocument(ShadowRoot& shadowRoot, Document& oldDocument, Document& newDocument)
1983 {
1984     traverseSubtreeToUpdateTreeScope(shadowRoot, [&oldDocument, &newDocument](Node& node) {
1985         node.moveNodeToNewDocument(oldDocument, newDocument);
1986     }, [&oldDocument, &newDocument](ShadowRoot& innerShadowRoot) {
1987         RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(&innerShadowRoot.document() == &oldDocument);
1988         innerShadowRoot.moveShadowRootToNewDocument(newDocument);
1989         moveShadowTreeToNewDocument(innerShadowRoot, oldDocument, newDocument);
1990     });
1991 }
1992
1993 void Node::moveTreeToNewScope(Node& root, TreeScope& oldScope, TreeScope& newScope)
1994 {
1995     ASSERT(&oldScope != &newScope);
1996
1997     Document& oldDocument = oldScope.documentScope();
1998     Document& newDocument = newScope.documentScope();
1999     if (&oldDocument != &newDocument) {
2000         oldDocument.incrementReferencingNodeCount();
2001         traverseSubtreeToUpdateTreeScope(root, [&](Node& node) {
2002             ASSERT(!node.isTreeScope());
2003             RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(&node.treeScope() == &oldScope);
2004             node.setTreeScope(newScope);
2005             node.moveNodeToNewDocument(oldDocument, newDocument);
2006         }, [&](ShadowRoot& shadowRoot) {
2007             ASSERT_WITH_SECURITY_IMPLICATION(&shadowRoot.document() == &oldDocument);
2008             shadowRoot.moveShadowRootToNewParentScope(newScope, newDocument);
2009             moveShadowTreeToNewDocument(shadowRoot, oldDocument, newDocument);
2010         });
2011         RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(&oldScope.documentScope() == &oldDocument && &newScope.documentScope() == &newDocument);
2012         oldDocument.decrementReferencingNodeCount();
2013     } else {
2014         traverseSubtreeToUpdateTreeScope(root, [&](Node& node) {
2015             ASSERT(!node.isTreeScope());
2016             RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(&node.treeScope() == &oldScope);
2017             node.setTreeScope(newScope);
2018             if (UNLIKELY(!node.hasRareData()))
2019                 return;
2020             if (auto* nodeLists = node.rareData()->nodeLists())
2021                 nodeLists->adoptTreeScope();
2022         }, [&newScope](ShadowRoot& shadowRoot) {
2023             shadowRoot.setParentTreeScope(newScope);
2024         });
2025     }
2026 }
2027
2028 void Node::moveNodeToNewDocument(Document& oldDocument, Document& newDocument)
2029 {
2030     newDocument.incrementReferencingNodeCount();
2031     oldDocument.decrementReferencingNodeCount();
2032
2033     if (hasRareData()) {
2034         if (auto* nodeLists = rareData()->nodeLists())
2035             nodeLists->adoptDocument(oldDocument, newDocument);
2036         if (auto* registry = mutationObserverRegistry()) {
2037             for (auto& registration : *registry)
2038                 newDocument.addMutationObserverTypes(registration->mutationTypes());
2039         }
2040         if (auto* transientRegistry = transientMutationObserverRegistry()) {
2041             for (auto& registration : *transientRegistry)
2042                 newDocument.addMutationObserverTypes(registration->mutationTypes());
2043         }
2044     } else {
2045         ASSERT(!mutationObserverRegistry());
2046         ASSERT(!transientMutationObserverRegistry());
2047     }
2048
2049     oldDocument.moveNodeIteratorsToNewDocument(*this, newDocument);
2050
2051     if (AXObjectCache::accessibilityEnabled()) {
2052         if (auto* cache = oldDocument.existingAXObjectCache())
2053             cache->remove(*this);
2054     }
2055
2056     if (auto* eventTargetData = this->eventTargetData()) {
2057         if (!eventTargetData->eventListenerMap.isEmpty()) {
2058             for (auto& type : eventTargetData->eventListenerMap.eventTypes())
2059                 newDocument.addListenerTypeIfNeeded(type);
2060         }
2061
2062         unsigned numWheelEventHandlers = eventListeners(eventNames().mousewheelEvent).size() + eventListeners(eventNames().wheelEvent).size();
2063         for (unsigned i = 0; i < numWheelEventHandlers; ++i) {
2064             oldDocument.didRemoveWheelEventHandler(*this);
2065             newDocument.didAddWheelEventHandler(*this);
2066         }
2067
2068         unsigned numTouchEventListeners = 0;
2069 #if ENABLE(TOUCH_EVENTS)
2070         if (RuntimeEnabledFeatures::sharedFeatures().mouseEventsSimulationEnabled()) {
2071             for (auto& name : eventNames().extendedTouchRelatedEventNames())
2072                 numTouchEventListeners += eventListeners(name).size();
2073         } else {
2074 #endif
2075             for (auto& name : eventNames().touchRelatedEventNames())
2076                 numTouchEventListeners += eventListeners(name).size();
2077 #if ENABLE(TOUCH_EVENTS)
2078         }
2079 #endif
2080
2081         for (unsigned i = 0; i < numTouchEventListeners; ++i) {
2082             oldDocument.didRemoveTouchEventHandler(*this);
2083             newDocument.didAddTouchEventHandler(*this);
2084 #if ENABLE(TOUCH_EVENTS) && PLATFORM(IOS_FAMILY)
2085             oldDocument.removeTouchEventListener(*this);
2086             newDocument.addTouchEventListener(*this);
2087 #endif
2088         }
2089
2090 #if ENABLE(TOUCH_EVENTS) && ENABLE(IOS_GESTURE_EVENTS)
2091         unsigned numGestureEventListeners = 0;
2092         for (auto& name : eventNames().gestureEventNames())
2093             numGestureEventListeners += eventListeners(name).size();
2094
2095         for (unsigned i = 0; i < numGestureEventListeners; ++i) {
2096             oldDocument.removeTouchEventHandler(*this);
2097             newDocument.addTouchEventHandler(*this);
2098         }
2099 #endif
2100     }
2101
2102 #if !ASSERT_DISABLED || ENABLE(SECURITY_ASSERTIONS)
2103 #if ENABLE(TOUCH_EVENTS) && PLATFORM(IOS_FAMILY)
2104     ASSERT_WITH_SECURITY_IMPLICATION(!oldDocument.touchEventListenersContain(*this));
2105     ASSERT_WITH_SECURITY_IMPLICATION(!oldDocument.touchEventHandlersContain(*this));
2106 #endif
2107 #if ENABLE(TOUCH_EVENTS) && ENABLE(IOS_GESTURE_EVENTS)
2108     ASSERT_WITH_SECURITY_IMPLICATION(!oldDocument.touchEventTargetsContain(*this));
2109 #endif
2110 #endif
2111
2112     if (is<Element>(*this))
2113         downcast<Element>(*this).didMoveToNewDocument(oldDocument, newDocument);
2114 }
2115
2116 static inline bool tryAddEventListener(Node* targetNode, const AtomicString& eventType, Ref<EventListener>&& listener, const EventTarget::AddEventListenerOptions& options)
2117 {
2118     if (!targetNode->EventTarget::addEventListener(eventType, listener.copyRef(), options))
2119         return false;
2120
2121     targetNode->document().addListenerTypeIfNeeded(eventType);
2122     if (eventNames().isWheelEventType(eventType))
2123         targetNode->document().didAddWheelEventHandler(*targetNode);
2124     else if (eventNames().isTouchRelatedEventType(eventType))
2125         targetNode->document().didAddTouchEventHandler(*targetNode);
2126
2127 #if PLATFORM(IOS_FAMILY)
2128     if (targetNode == &targetNode->document() && eventType == eventNames().scrollEvent)
2129         targetNode->document().domWindow()->incrementScrollEventListenersCount();
2130
2131     // FIXME: Would it be sufficient to special-case this code for <body> and <frameset>?
2132     //
2133     // This code was added to address <rdar://problem/5846492> Onorientationchange event not working for document.body.
2134     // Forward this call to addEventListener() to the window since these are window-only events.
2135     if (eventType == eventNames().orientationchangeEvent || eventType == eventNames().resizeEvent)
2136         targetNode->document().domWindow()->addEventListener(eventType, WTFMove(listener), options);
2137
2138 #if ENABLE(TOUCH_EVENTS)
2139     if (eventNames().isTouchRelatedEventType(eventType))
2140         targetNode->document().addTouchEventListener(*targetNode);
2141 #endif
2142 #endif // PLATFORM(IOS_FAMILY)
2143
2144 #if ENABLE(IOS_GESTURE_EVENTS) && ENABLE(TOUCH_EVENTS)
2145     if (eventNames().isGestureEventType(eventType))
2146         targetNode->document().addTouchEventHandler(*targetNode);
2147 #endif
2148
2149     return true;
2150 }
2151
2152 bool Node::addEventListener(const AtomicString& eventType, Ref<EventListener>&& listener, const AddEventListenerOptions& options)
2153 {
2154     return tryAddEventListener(this, eventType, WTFMove(listener), options);
2155 }
2156
2157 static inline bool tryRemoveEventListener(Node* targetNode, const AtomicString& eventType, EventListener& listener, const EventTarget::ListenerOptions& options)
2158 {
2159     if (!targetNode->EventTarget::removeEventListener(eventType, listener, options))
2160         return false;
2161
2162     // FIXME: Notify Document that the listener has vanished. We need to keep track of a number of
2163     // listeners for each type, not just a bool - see https://bugs.webkit.org/show_bug.cgi?id=33861
2164     if (eventNames().isWheelEventType(eventType))
2165         targetNode->document().didRemoveWheelEventHandler(*targetNode);
2166     else if (eventNames().isTouchRelatedEventType(eventType))
2167         targetNode->document().didRemoveTouchEventHandler(*targetNode);
2168
2169 #if PLATFORM(IOS_FAMILY)
2170     if (targetNode == &targetNode->document() && eventType == eventNames().scrollEvent)
2171         targetNode->document().domWindow()->decrementScrollEventListenersCount();
2172
2173     // FIXME: Would it be sufficient to special-case this code for <body> and <frameset>? See <rdar://problem/15647823>.
2174     // This code was added to address <rdar://problem/5846492> Onorientationchange event not working for document.body.
2175     // Forward this call to removeEventListener() to the window since these are window-only events.
2176     if (eventType == eventNames().orientationchangeEvent || eventType == eventNames().resizeEvent)
2177         targetNode->document().domWindow()->removeEventListener(eventType, listener, options);
2178
2179 #if ENABLE(TOUCH_EVENTS)
2180     if (eventNames().isTouchRelatedEventType(eventType))
2181         targetNode->document().removeTouchEventListener(*targetNode);
2182 #endif
2183 #endif // PLATFORM(IOS_FAMILY)
2184
2185 #if ENABLE(IOS_GESTURE_EVENTS) && ENABLE(TOUCH_EVENTS)
2186     if (eventNames().isGestureEventType(eventType))
2187         targetNode->document().removeTouchEventHandler(*targetNode);
2188 #endif
2189
2190     return true;
2191 }
2192
2193 bool Node::removeEventListener(const AtomicString& eventType, EventListener& listener, const ListenerOptions& options)
2194 {
2195     return tryRemoveEventListener(this, eventType, listener, options);
2196 }
2197
2198 typedef HashMap<Node*, std::unique_ptr<EventTargetData>> EventTargetDataMap;
2199
2200 static EventTargetDataMap& eventTargetDataMap()
2201 {
2202     static NeverDestroyed<EventTargetDataMap> map;
2203
2204     return map;
2205 }
2206
2207 static Lock s_eventTargetDataMapLock;
2208
2209 EventTargetData* Node::eventTargetData()
2210 {
2211     return hasEventTargetData() ? eventTargetDataMap().get(this) : nullptr;
2212 }
2213
2214 EventTargetData* Node::eventTargetDataConcurrently()
2215 {
2216     // Not holding the lock when the world is stopped accelerates parallel constraint solving, which
2217     // calls this function from many threads. Parallel constraint solving can happen with the world
2218     // running or stopped, but if we do it with a running world, then we're usually mixing constraint
2219     // solving with other work. Therefore, the most likely time for contention on this lock is when the
2220     // world is stopped. We don't have to hold the lock when the world is stopped, because a stopped world
2221     // means that we will never mutate the event target data map.
2222     JSC::VM* vm = commonVMOrNull();
2223     auto locker = holdLockIf(s_eventTargetDataMapLock, vm && vm->heap.worldIsRunning());
2224     return hasEventTargetData() ? eventTargetDataMap().get(this) : nullptr;
2225 }
2226
2227 EventTargetData& Node::ensureEventTargetData()
2228 {
2229     if (hasEventTargetData())
2230         return *eventTargetDataMap().get(this);
2231
2232     JSC::VM* vm = commonVMOrNull();
2233     RELEASE_ASSERT(!vm || vm->heap.worldIsRunning());
2234
2235     auto locker = holdLock(s_eventTargetDataMapLock);
2236     setHasEventTargetData(true);
2237     return *eventTargetDataMap().add(this, std::make_unique<EventTargetData>()).iterator->value;
2238 }
2239
2240 void Node::clearEventTargetData()
2241 {
2242     JSC::VM* vm = commonVMOrNull();
2243     RELEASE_ASSERT(!vm || vm->heap.worldIsRunning());
2244     auto locker = holdLock(s_eventTargetDataMapLock);
2245     eventTargetDataMap().remove(this);
2246 }
2247
2248 Vector<std::unique_ptr<MutationObserverRegistration>>* Node::mutationObserverRegistry()
2249 {
2250     if (!hasRareData())
2251         return nullptr;
2252     auto* data = rareData()->mutationObserverData();
2253     if (!data)
2254         return nullptr;
2255     return &data->registry;
2256 }
2257
2258 HashSet<MutationObserverRegistration*>* Node::transientMutationObserverRegistry()
2259 {
2260     if (!hasRareData())
2261         return nullptr;
2262     auto* data = rareData()->mutationObserverData();
2263     if (!data)
2264         return nullptr;
2265     return &data->transientRegistry;
2266 }
2267
2268 template<typename Registry> static inline void collectMatchingObserversForMutation(HashMap<Ref<MutationObserver>, MutationRecordDeliveryOptions>& observers, Registry* registry, Node& target, MutationObserver::MutationType type, const QualifiedName* attributeName)
2269 {
2270     if (!registry)
2271         return;
2272
2273     for (auto& registration : *registry) {
2274         if (registration->shouldReceiveMutationFrom(target, type, attributeName)) {
2275             auto deliveryOptions = registration->deliveryOptions();
2276             auto result = observers.add(registration->observer(), deliveryOptions);
2277             if (!result.isNewEntry)
2278                 result.iterator->value |= deliveryOptions;
2279         }
2280     }
2281 }
2282
2283 HashMap<Ref<MutationObserver>, MutationRecordDeliveryOptions> Node::registeredMutationObservers(MutationObserver::MutationType type, const QualifiedName* attributeName)
2284 {
2285     HashMap<Ref<MutationObserver>, MutationRecordDeliveryOptions> result;
2286     ASSERT((type == MutationObserver::Attributes && attributeName) || !attributeName);
2287     collectMatchingObserversForMutation(result, mutationObserverRegistry(), *this, type, attributeName);
2288     collectMatchingObserversForMutation(result, transientMutationObserverRegistry(), *this, type, attributeName);
2289     for (Node* node = parentNode(); node; node = node->parentNode()) {
2290         collectMatchingObserversForMutation(result, node->mutationObserverRegistry(), *this, type, attributeName);
2291         collectMatchingObserversForMutation(result, node->transientMutationObserverRegistry(), *this, type, attributeName);
2292     }
2293     return result;
2294 }
2295
2296 void Node::registerMutationObserver(MutationObserver& observer, MutationObserverOptions options, const HashSet<AtomicString>& attributeFilter)
2297 {
2298     MutationObserverRegistration* registration = nullptr;
2299     auto& registry = ensureRareData().ensureMutationObserverData().registry;
2300
2301     for (auto& candidateRegistration : registry) {
2302         if (&candidateRegistration->observer() == &observer) {
2303             registration = candidateRegistration.get();
2304             registration->resetObservation(options, attributeFilter);
2305         }
2306     }
2307
2308     if (!registration) {
2309         registry.append(std::make_unique<MutationObserverRegistration>(observer, *this, options, attributeFilter));
2310         registration = registry.last().get();
2311     }
2312
2313     document().addMutationObserverTypes(registration->mutationTypes());
2314 }
2315
2316 void Node::unregisterMutationObserver(MutationObserverRegistration& registration)
2317 {
2318     auto* registry = mutationObserverRegistry();
2319     ASSERT(registry);
2320     if (!registry)
2321         return;
2322
2323     registry->removeFirstMatching([&registration] (auto& current) {
2324         return current.get() == &registration;
2325     });
2326 }
2327
2328 void Node::registerTransientMutationObserver(MutationObserverRegistration& registration)
2329 {
2330     ensureRareData().ensureMutationObserverData().transientRegistry.add(&registration);
2331 }
2332
2333 void Node::unregisterTransientMutationObserver(MutationObserverRegistration& registration)
2334 {
2335     auto* transientRegistry = transientMutationObserverRegistry();
2336     ASSERT(transientRegistry);
2337     if (!transientRegistry)
2338         return;
2339
2340     ASSERT(transientRegistry->contains(&registration));
2341     transientRegistry->remove(&registration);
2342 }
2343
2344 void Node::notifyMutationObserversNodeWillDetach()
2345 {
2346     if (!document().hasMutationObservers())
2347         return;
2348
2349     for (Node* node = parentNode(); node; node = node->parentNode()) {
2350         if (auto* registry = node->mutationObserverRegistry()) {
2351             for (auto& registration : *registry)
2352                 registration->observedSubtreeNodeWillDetach(*this);
2353         }
2354         if (auto* transientRegistry = node->transientMutationObserverRegistry()) {
2355             for (auto* registration : *transientRegistry)
2356                 registration->observedSubtreeNodeWillDetach(*this);
2357         }
2358     }
2359 }
2360
2361 void Node::handleLocalEvents(Event& event, EventInvokePhase phase)
2362 {
2363     if (!hasEventTargetData())
2364         return;
2365
2366     // FIXME: Should we deliver wheel events to disabled form controls or not?
2367     if (is<Element>(*this) && downcast<Element>(*this).isDisabledFormControl() && event.isMouseEvent() && !event.isWheelEvent())
2368         return;
2369
2370     fireEventListeners(event, phase);
2371 }
2372
2373 void Node::dispatchScopedEvent(Event& event)
2374 {
2375     EventDispatcher::dispatchScopedEvent(*this, event);
2376 }
2377
2378 void Node::dispatchEvent(Event& event)
2379 {
2380     EventDispatcher::dispatchEvent(*this, event);
2381 }
2382
2383 void Node::dispatchSubtreeModifiedEvent()
2384 {
2385     if (isInShadowTree())
2386         return;
2387
2388     ASSERT_WITH_SECURITY_IMPLICATION(ScriptDisallowedScope::InMainThread::isEventDispatchAllowedInSubtree(*this));
2389
2390     if (!document().hasListenerType(Document::DOMSUBTREEMODIFIED_LISTENER))
2391         return;
2392     const AtomicString& subtreeModifiedEventName = eventNames().DOMSubtreeModifiedEvent;
2393     if (!parentNode() && !hasEventListeners(subtreeModifiedEventName))
2394         return;
2395
2396     dispatchScopedEvent(MutationEvent::create(subtreeModifiedEventName, Event::CanBubble::Yes));
2397 }
2398
2399 void Node::dispatchDOMActivateEvent(Event& underlyingClickEvent)
2400 {
2401     ASSERT_WITH_SECURITY_IMPLICATION(ScriptDisallowedScope::InMainThread::isScriptAllowed());
2402     int detail = is<UIEvent>(underlyingClickEvent) ? downcast<UIEvent>(underlyingClickEvent).detail() : 0;
2403     auto event = UIEvent::create(eventNames().DOMActivateEvent, Event::CanBubble::Yes, Event::IsCancelable::Yes, Event::IsComposed::Yes, document().windowProxy(), detail);
2404     event->setUnderlyingEvent(&underlyingClickEvent);
2405     dispatchScopedEvent(event);
2406     if (event->defaultHandled())
2407         underlyingClickEvent.setDefaultHandled();
2408 }
2409
2410 bool Node::dispatchBeforeLoadEvent(const String& sourceURL)
2411 {
2412     if (!document().hasListenerType(Document::BEFORELOAD_LISTENER))
2413         return true;
2414
2415     Ref<Node> protectedThis(*this);
2416     auto event = BeforeLoadEvent::create(sourceURL);
2417     dispatchEvent(event);
2418     return !event->defaultPrevented();
2419 }
2420
2421 void Node::dispatchInputEvent()
2422 {
2423     dispatchScopedEvent(Event::create(eventNames().inputEvent, Event::CanBubble::Yes, Event::IsCancelable::No, Event::IsComposed::Yes));
2424 }
2425
2426 void Node::defaultEventHandler(Event& event)
2427 {
2428     if (event.target() != this)
2429         return;
2430     const AtomicString& eventType = event.type();
2431     if (eventType == eventNames().keydownEvent || eventType == eventNames().keypressEvent) {
2432         if (is<KeyboardEvent>(event)) {
2433             if (Frame* frame = document().frame())
2434                 frame->eventHandler().defaultKeyboardEventHandler(downcast<KeyboardEvent>(event));
2435         }
2436     } else if (eventType == eventNames().clickEvent) {
2437         dispatchDOMActivateEvent(event);
2438 #if ENABLE(CONTEXT_MENUS)
2439     } else if (eventType == eventNames().contextmenuEvent) {
2440         if (Frame* frame = document().frame())
2441             if (Page* page = frame->page())
2442                 page->contextMenuController().handleContextMenuEvent(event);
2443 #endif
2444     } else if (eventType == eventNames().textInputEvent) {
2445         if (is<TextEvent>(event)) {
2446             if (Frame* frame = document().frame())
2447                 frame->eventHandler().defaultTextInputEventHandler(downcast<TextEvent>(event));
2448         }
2449 #if ENABLE(PAN_SCROLLING)
2450     } else if (eventType == eventNames().mousedownEvent && is<MouseEvent>(event)) {
2451         if (downcast<MouseEvent>(event).button() == MiddleButton) {
2452             if (enclosingLinkEventParentOrSelf())
2453                 return;
2454
2455             RenderObject* renderer = this->renderer();
2456             while (renderer && (!is<RenderBox>(*renderer) || !downcast<RenderBox>(*renderer).canBeScrolledAndHasScrollableArea()))
2457                 renderer = renderer->parent();
2458
2459             if (renderer) {
2460                 if (Frame* frame = document().frame())
2461                     frame->eventHandler().startPanScrolling(downcast<RenderBox>(*renderer));
2462             }
2463         }
2464 #endif
2465     } else if (eventNames().isWheelEventType(eventType) && is<WheelEvent>(event)) {
2466         // If we don't have a renderer, send the wheel event to the first node we find with a renderer.
2467         // This is needed for <option> and <optgroup> elements so that <select>s get a wheel scroll.
2468         Node* startNode = this;
2469         while (startNode && !startNode->renderer())
2470             startNode = startNode->parentOrShadowHostNode();
2471         
2472         if (startNode && startNode->renderer())
2473             if (Frame* frame = document().frame())
2474                 frame->eventHandler().defaultWheelEventHandler(startNode, downcast<WheelEvent>(event));
2475 #if ENABLE(TOUCH_EVENTS) && PLATFORM(IOS_FAMILY)
2476     } else if (is<TouchEvent>(event) && eventNames().isTouchRelatedEventType(eventType)) {
2477         RenderObject* renderer = this->renderer();
2478         while (renderer && (!is<RenderBox>(*renderer) || !downcast<RenderBox>(*renderer).canBeScrolledAndHasScrollableArea()))
2479             renderer = renderer->parent();
2480
2481         if (renderer && renderer->node()) {
2482             if (Frame* frame = document().frame())
2483                 frame->eventHandler().defaultTouchEventHandler(*renderer->node(), downcast<TouchEvent>(event));
2484         }
2485 #endif
2486     }
2487 }
2488
2489 bool Node::willRespondToMouseMoveEvents()
2490 {
2491     // FIXME: Why is the iOS code path different from the non-iOS code path?
2492 #if !PLATFORM(IOS_FAMILY)
2493     if (!is<Element>(*this))
2494         return false;
2495     if (downcast<Element>(*this).isDisabledFormControl())
2496         return false;
2497 #endif
2498     return hasEventListeners(eventNames().mousemoveEvent) || hasEventListeners(eventNames().mouseoverEvent) || hasEventListeners(eventNames().mouseoutEvent);
2499 }
2500
2501 bool Node::willRespondToMouseClickEvents()
2502 {
2503     // FIXME: Why is the iOS code path different from the non-iOS code path?
2504 #if PLATFORM(IOS_FAMILY)
2505     return isContentEditable() || hasEventListeners(eventNames().mouseupEvent) || hasEventListeners(eventNames().mousedownEvent) || hasEventListeners(eventNames().clickEvent);
2506 #else
2507     if (!is<Element>(*this))
2508         return false;
2509     if (downcast<Element>(*this).isDisabledFormControl())
2510         return false;
2511     return computeEditability(UserSelectAllIsAlwaysNonEditable, ShouldUpdateStyle::Update) != Editability::ReadOnly
2512         || hasEventListeners(eventNames().mouseupEvent) || hasEventListeners(eventNames().mousedownEvent) || hasEventListeners(eventNames().clickEvent) || hasEventListeners(eventNames().DOMActivateEvent);
2513 #endif
2514 }
2515
2516 bool Node::willRespondToMouseWheelEvents()
2517 {
2518     return hasEventListeners(eventNames().mousewheelEvent);
2519 }
2520
2521 // It's important not to inline removedLastRef, because we don't want to inline the code to
2522 // delete a Node at each deref call site.
2523 void Node::removedLastRef()
2524 {
2525     // This avoids double destruction even when there is a programming error to use Ref<T> / RefPtr<T> on this node.
2526     // There are debug assertions in Node::ref() / Node::deref() to catch such a programming error.
2527     ASSERT(m_refCountAndParentBit == s_refCountIncrement);
2528
2529     // An explicit check for Document here is better than a virtual function since it is
2530     // faster for non-Document nodes, and because the call to removedLastRef that is inlined
2531     // at all deref call sites is smaller if it's a non-virtual function.
2532     if (is<Document>(*this)) {
2533         downcast<Document>(*this).removedLastRef();
2534         return;
2535     }
2536
2537 #ifndef NDEBUG
2538     m_deletionHasBegun = true;
2539 #endif
2540     delete this;
2541 }
2542
2543 void Node::textRects(Vector<IntRect>& rects) const
2544 {
2545     auto range = Range::create(document());
2546     range->selectNodeContents(const_cast<Node&>(*this));
2547     range->absoluteTextRects(rects);
2548 }
2549
2550 unsigned Node::connectedSubframeCount() const
2551 {
2552     return hasRareData() ? rareData()->connectedSubframeCount() : 0;
2553 }
2554
2555 void Node::incrementConnectedSubframeCount(unsigned amount)
2556 {
2557     ASSERT(isContainerNode());
2558     ensureRareData().incrementConnectedSubframeCount(amount);
2559 }
2560
2561 void Node::decrementConnectedSubframeCount(unsigned amount)
2562 {
2563     rareData()->decrementConnectedSubframeCount(amount);
2564 }
2565
2566 void Node::updateAncestorConnectedSubframeCountForRemoval() const
2567 {
2568     unsigned count = connectedSubframeCount();
2569
2570     if (!count)
2571         return;
2572
2573     for (Node* node = parentOrShadowHostNode(); node; node = node->parentOrShadowHostNode())
2574         node->decrementConnectedSubframeCount(count);
2575 }
2576
2577 void Node::updateAncestorConnectedSubframeCountForInsertion() const
2578 {
2579     unsigned count = connectedSubframeCount();
2580
2581     if (!count)
2582         return;
2583
2584     for (Node* node = parentOrShadowHostNode(); node; node = node->parentOrShadowHostNode())
2585         node->incrementConnectedSubframeCount(count);
2586 }
2587
2588 bool Node::inRenderedDocument() const
2589 {
2590     return isConnected() && document().hasLivingRenderTree();
2591 }
2592
2593 void* Node::opaqueRootSlow() const
2594 {
2595     const Node* node = this;
2596     for (;;) {
2597         const Node* nextNode = node->parentOrShadowHostNode();
2598         if (!nextNode)
2599             break;
2600         node = nextNode;
2601     }
2602     return const_cast<void*>(static_cast<const void*>(node));
2603 }
2604
2605 } // namespace WebCore
2606
2607 #if ENABLE(TREE_DEBUGGING)
2608
2609 void showTree(const WebCore::Node* node)
2610 {
2611     if (node)
2612         node->showTreeForThis();
2613 }
2614
2615 void showNodePath(const WebCore::Node* node)
2616 {
2617     if (node)
2618         node->showNodePathForThis();
2619 }
2620
2621 #endif // ENABLE(TREE_DEBUGGING)