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