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