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