Source/WebCore:
[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 "ContainerNodeAlgorithms.h"
35 #include "ContextMenuController.h"
36 #include "DOMImplementation.h"
37 #include "DocumentType.h"
38 #include "ElementIterator.h"
39 #include "ElementRareData.h"
40 #include "ElementTraversal.h"
41 #include "EventDispatcher.h"
42 #include "EventException.h"
43 #include "EventHandler.h"
44 #include "FrameView.h"
45 #include "HTMLCollection.h"
46 #include "HTMLElement.h"
47 #include "HTMLImageElement.h"
48 #include "HTMLSlotElement.h"
49 #include "HTMLStyleElement.h"
50 #include "InsertionPoint.h"
51 #include "InspectorController.h"
52 #include "KeyboardEvent.h"
53 #include "Logging.h"
54 #include "MutationEvent.h"
55 #include "NodeOrString.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 "TreeScopeAdopter.h"
72 #include "WheelEvent.h"
73 #include "XMLNames.h"
74 #include <wtf/RefCountedLeakCounter.h>
75 #include <wtf/SHA1.h>
76 #include <wtf/text/CString.h>
77 #include <wtf/text/StringBuilder.h>
78
79 #if ENABLE(INDIE_UI)
80 #include "UIRequestEvent.h"
81 #endif
82
83 namespace WebCore {
84
85 using namespace HTMLNames;
86
87 bool Node::isSupported(const String& feature, const String& version)
88 {
89     return DOMImplementation::hasFeature(feature, version);
90 }
91
92 #if DUMP_NODE_STATISTICS
93 static HashSet<Node*> liveNodeSet;
94 #endif
95
96 void Node::dumpStatistics()
97 {
98 #if DUMP_NODE_STATISTICS
99     size_t nodesWithRareData = 0;
100
101     size_t elementNodes = 0;
102     size_t attrNodes = 0;
103     size_t textNodes = 0;
104     size_t cdataNodes = 0;
105     size_t commentNodes = 0;
106     size_t entityReferenceNodes = 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 xpathNSNodes = 0;
113     size_t shadowRootNodes = 0;
114
115     HashMap<String, size_t> perTagCount;
116
117     size_t attributes = 0;
118     size_t attributesWithAttr = 0;
119     size_t elementsWithAttributeStorage = 0;
120     size_t elementsWithRareData = 0;
121     size_t elementsWithNamedNodeMap = 0;
122
123     for (auto* node : liveNodeSet) {
124         if (node->hasRareData()) {
125             ++nodesWithRareData;
126             if (is<Element>(*node)) {
127                 ++elementsWithRareData;
128                 if (downcast<Element>(*node).hasNamedNodeMap())
129                     ++elementsWithNamedNodeMap;
130             }
131         }
132
133         switch (node->nodeType()) {
134             case ELEMENT_NODE: {
135                 ++elementNodes;
136
137                 // Tag stats
138                 Element& element = downcast<Element>(*node);
139                 HashMap<String, size_t>::AddResult result = perTagCount.add(element.tagName(), 1);
140                 if (!result.isNewEntry)
141                     result.iterator->value++;
142
143                 if (ElementData* elementData = element.elementData()) {
144                     unsigned length = elementData->length();
145                     attributes += length;
146                     ++elementsWithAttributeStorage;
147                     for (unsigned i = 0; i < length; ++i) {
148                         Attribute& attr = elementData->attributeAt(i);
149                         if (attr.attr())
150                             ++attributesWithAttr;
151                     }
152                 }
153                 break;
154             }
155             case ATTRIBUTE_NODE: {
156                 ++attrNodes;
157                 break;
158             }
159             case TEXT_NODE: {
160                 ++textNodes;
161                 break;
162             }
163             case CDATA_SECTION_NODE: {
164                 ++cdataNodes;
165                 break;
166             }
167             case COMMENT_NODE: {
168                 ++commentNodes;
169                 break;
170             }
171             case ENTITY_REFERENCE_NODE: {
172                 ++entityReferenceNodes;
173                 break;
174             }
175             case ENTITY_NODE: {
176                 ++entityNodes;
177                 break;
178             }
179             case PROCESSING_INSTRUCTION_NODE: {
180                 ++piNodes;
181                 break;
182             }
183             case DOCUMENT_NODE: {
184                 ++documentNodes;
185                 break;
186             }
187             case DOCUMENT_TYPE_NODE: {
188                 ++docTypeNodes;
189                 break;
190             }
191             case DOCUMENT_FRAGMENT_NODE: {
192                 if (node->isShadowRoot())
193                     ++shadowRootNodes;
194                 else
195                     ++fragmentNodes;
196                 break;
197             }
198             case XPATH_NAMESPACE_NODE: {
199                 ++xpathNSNodes;
200                 break;
201             }
202         }
203     }
204
205     printf("Number of Nodes: %d\n\n", liveNodeSet.size());
206     printf("Number of Nodes with RareData: %zu\n\n", nodesWithRareData);
207
208     printf("NodeType distribution:\n");
209     printf("  Number of Element nodes: %zu\n", elementNodes);
210     printf("  Number of Attribute nodes: %zu\n", attrNodes);
211     printf("  Number of Text nodes: %zu\n", textNodes);
212     printf("  Number of CDATASection nodes: %zu\n", cdataNodes);
213     printf("  Number of Comment nodes: %zu\n", commentNodes);
214     printf("  Number of EntityReference nodes: %zu\n", entityReferenceNodes);
215     printf("  Number of Entity nodes: %zu\n", entityNodes);
216     printf("  Number of ProcessingInstruction nodes: %zu\n", piNodes);
217     printf("  Number of Document nodes: %zu\n", documentNodes);
218     printf("  Number of DocumentType nodes: %zu\n", docTypeNodes);
219     printf("  Number of DocumentFragment nodes: %zu\n", fragmentNodes);
220     printf("  Number of XPathNS nodes: %zu\n", xpathNSNodes);
221     printf("  Number of ShadowRoot nodes: %zu\n", shadowRootNodes);
222
223     printf("Element tag name distibution:\n");
224     for (auto& stringSizePair : perTagCount)
225         printf("  Number of <%s> tags: %zu\n", stringSizePair.key.utf8().data(), stringSizePair.value);
226
227     printf("Attributes:\n");
228     printf("  Number of Attributes (non-Node and Node): %zu [%zu]\n", attributes, sizeof(Attribute));
229     printf("  Number of Attributes with an Attr: %zu\n", attributesWithAttr);
230     printf("  Number of Elements with attribute storage: %zu [%zu]\n", elementsWithAttributeStorage, sizeof(ElementData));
231     printf("  Number of Elements with RareData: %zu\n", elementsWithRareData);
232     printf("  Number of Elements with NamedNodeMap: %zu [%zu]\n", elementsWithNamedNodeMap, sizeof(NamedNodeMap));
233 #endif
234 }
235
236 DEFINE_DEBUG_ONLY_GLOBAL(WTF::RefCountedLeakCounter, nodeCounter, ("WebCoreNode"));
237
238 #ifndef NDEBUG
239 static bool shouldIgnoreLeaks = false;
240
241 static HashSet<Node*>& ignoreSet()
242 {
243     static NeverDestroyed<HashSet<Node*>> ignore;
244
245     return ignore;
246 }
247
248 #endif
249
250 void Node::startIgnoringLeaks()
251 {
252 #ifndef NDEBUG
253     shouldIgnoreLeaks = true;
254 #endif
255 }
256
257 void Node::stopIgnoringLeaks()
258 {
259 #ifndef NDEBUG
260     shouldIgnoreLeaks = false;
261 #endif
262 }
263
264 void Node::trackForDebugging()
265 {
266 #ifndef NDEBUG
267     if (shouldIgnoreLeaks)
268         ignoreSet().add(this);
269     else
270         nodeCounter.increment();
271 #endif
272
273 #if DUMP_NODE_STATISTICS
274     liveNodeSet.add(this);
275 #endif
276 }
277
278 Node::Node(Document& document, ConstructionType type)
279     : m_refCount(1)
280     , m_nodeFlags(type)
281     , m_parentNode(nullptr)
282     , m_treeScope(&document)
283     , m_previous(nullptr)
284     , m_next(nullptr)
285 {
286     ASSERT(isMainThread());
287
288     document.incrementReferencingNodeCount();
289
290 #if !defined(NDEBUG) || (defined(DUMP_NODE_STATISTICS) && DUMP_NODE_STATISTICS)
291     trackForDebugging();
292 #endif
293 }
294
295 Node::~Node()
296 {
297     ASSERT(isMainThread());
298     ASSERT(!m_refCount);
299     ASSERT(m_deletionHasBegun);
300     ASSERT(!m_adoptionIsRequired);
301
302 #ifndef NDEBUG
303     if (!ignoreSet().remove(this))
304         nodeCounter.decrement();
305 #endif
306
307 #if DUMP_NODE_STATISTICS
308     liveNodeSet.remove(this);
309 #endif
310
311     ASSERT(!renderer());
312     ASSERT(!parentNode());
313     ASSERT(!m_previous);
314     ASSERT(!m_next);
315
316     if (hasRareData())
317         clearRareData();
318
319     if (!isContainerNode())
320         willBeDeletedFrom(document());
321
322     document().decrementReferencingNodeCount();
323 }
324
325 void Node::willBeDeletedFrom(Document& document)
326 {
327     if (hasEventTargetData()) {
328         document.didRemoveWheelEventHandler(*this, EventHandlerRemoval::All);
329 #if ENABLE(TOUCH_EVENTS) && PLATFORM(IOS)
330         document.removeTouchEventListener(this, true);
331 #else
332         // FIXME: This should call didRemoveTouchEventHandler().
333 #endif
334         clearEventTargetData();
335     }
336
337     if (AXObjectCache* cache = document.existingAXObjectCache())
338         cache->remove(this);
339 }
340
341 void Node::materializeRareData()
342 {
343     NodeRareData* data;
344     if (is<Element>(*this))
345         data = std::make_unique<ElementRareData>(downcast<RenderElement>(m_data.m_renderer)).release();
346     else
347         data = std::make_unique<NodeRareData>(m_data.m_renderer).release();
348     ASSERT(data);
349
350     m_data.m_rareData = data;
351     setFlag(HasRareDataFlag);
352 }
353
354 void Node::clearRareData()
355 {
356     ASSERT(hasRareData());
357     ASSERT(!transientMutationObserverRegistry() || transientMutationObserverRegistry()->isEmpty());
358
359     RenderObject* renderer = m_data.m_rareData->renderer();
360     if (isElementNode())
361         delete static_cast<ElementRareData*>(m_data.m_rareData);
362     else
363         delete static_cast<NodeRareData*>(m_data.m_rareData);
364     m_data.m_renderer = renderer;
365     clearFlag(HasRareDataFlag);
366 }
367
368 Node* Node::toNode()
369 {
370     return this;
371 }
372
373 HTMLInputElement* Node::toInputElement()
374 {
375     // If one of the below ASSERTs trigger, you are calling this function
376     // directly or indirectly from a constructor or destructor of this object.
377     // Don't do this!
378     ASSERT(!(isHTMLElement() && hasTagName(inputTag)));
379     return 0;
380 }
381
382 String Node::nodeValue() const
383 {
384     return String();
385 }
386
387 void Node::setNodeValue(const String& /*nodeValue*/, ExceptionCode& ec)
388 {
389     // NO_MODIFICATION_ALLOWED_ERR: Raised when the node is readonly
390     if (isReadOnlyNode()) {
391         ec = NO_MODIFICATION_ALLOWED_ERR;
392         return;
393     }
394
395     // By default, setting nodeValue has no effect.
396 }
397
398 RefPtr<NodeList> Node::childNodes()
399 {
400     if (is<ContainerNode>(*this))
401         return ensureRareData().ensureNodeLists().ensureChildNodeList(downcast<ContainerNode>(*this));
402     return ensureRareData().ensureNodeLists().ensureEmptyChildNodeList(*this);
403 }
404
405 Node *Node::lastDescendant() const
406 {
407     Node *n = const_cast<Node *>(this);
408     while (n && n->lastChild())
409         n = n->lastChild();
410     return n;
411 }
412
413 Node* Node::firstDescendant() const
414 {
415     Node *n = const_cast<Node *>(this);
416     while (n && n->firstChild())
417         n = n->firstChild();
418     return n;
419 }
420
421 Element* Node::previousElementSibling() const
422 {
423     return ElementTraversal::previousSibling(*this);
424 }
425
426 Element* Node::nextElementSibling() const
427 {
428     return ElementTraversal::nextSibling(*this);
429 }
430
431 bool Node::insertBefore(PassRefPtr<Node> newChild, Node* refChild, ExceptionCode& ec)
432 {
433     if (!newChild) {
434         ec = TypeError;
435         return false;
436     }
437     if (!is<ContainerNode>(*this)) {
438         ec = HIERARCHY_REQUEST_ERR;
439         return false;
440     }
441     return downcast<ContainerNode>(*this).insertBefore(*newChild, refChild, ec);
442 }
443
444 bool Node::replaceChild(PassRefPtr<Node> newChild, Node* oldChild, ExceptionCode& ec)
445 {
446     if (!newChild || !oldChild) {
447         ec = TypeError;
448         return false;
449     }
450     if (!is<ContainerNode>(*this)) {
451         ec = HIERARCHY_REQUEST_ERR;
452         return false;
453     }
454     return downcast<ContainerNode>(*this).replaceChild(*newChild, *oldChild, ec);
455 }
456
457 bool Node::removeChild(Node* oldChild, ExceptionCode& ec)
458 {
459     if (!oldChild) {
460         ec = TypeError;
461         return false;
462     }
463     if (!is<ContainerNode>(*this)) {
464         ec = NOT_FOUND_ERR;
465         return false;
466     }
467     return downcast<ContainerNode>(*this).removeChild(*oldChild, ec);
468 }
469
470 bool Node::appendChild(PassRefPtr<Node> newChild, ExceptionCode& ec)
471 {
472     if (!newChild) {
473         ec = TypeError;
474         return false;
475     }
476     if (!is<ContainerNode>(*this)) {
477         ec = HIERARCHY_REQUEST_ERR;
478         return false;
479     }
480     return downcast<ContainerNode>(*this).appendChild(*newChild, ec);
481 }
482
483 static HashSet<RefPtr<Node>> nodeSetPreTransformedFromNodeOrStringVector(const Vector<NodeOrString>& nodeOrStringVector)
484 {
485     HashSet<RefPtr<Node>> nodeSet;
486     for (auto& nodeOrString : nodeOrStringVector) {
487         switch (nodeOrString.type()) {
488         case NodeOrString::Type::String:
489             break;
490         case NodeOrString::Type::Node:
491             nodeSet.add(&nodeOrString.node());
492             break;
493         }
494     }
495
496     return nodeSet;
497 }
498
499 static RefPtr<Node> firstPrecedingSiblingNotInNodeSet(Node& context, const HashSet<RefPtr<Node>>& nodeSet)
500 {
501     for (auto* sibling = context.previousSibling(); sibling; sibling = sibling->previousSibling()) {
502         if (!nodeSet.contains(sibling))
503             return sibling;
504     }
505     return nullptr;
506 }
507
508 static RefPtr<Node> firstFollowingSiblingNotInNodeSet(Node& context, const HashSet<RefPtr<Node>>& nodeSet)
509 {
510     for (auto* sibling = context.nextSibling(); sibling; sibling = sibling->nextSibling()) {
511         if (!nodeSet.contains(sibling))
512             return sibling;
513     }
514     return nullptr;
515 }
516
517 void Node::before(Vector<NodeOrString>&& nodeOrStringVector, ExceptionCode& ec)
518 {
519     RefPtr<ContainerNode> parent = parentNode();
520     if (!parent)
521         return;
522
523     auto nodeSet = nodeSetPreTransformedFromNodeOrStringVector(nodeOrStringVector);
524     auto viablePreviousSibling = firstPrecedingSiblingNotInNodeSet(*this, nodeSet);
525
526     auto node = convertNodesOrStringsIntoNode(*this, WTF::move(nodeOrStringVector), ec);
527     if (ec || !node)
528         return;
529
530     if (viablePreviousSibling)
531         viablePreviousSibling = viablePreviousSibling->nextSibling();
532     else
533         viablePreviousSibling = parent->firstChild();
534
535     parent->insertBefore(node.releaseNonNull(), viablePreviousSibling.get(), ec);
536 }
537
538 void Node::after(Vector<NodeOrString>&& nodeOrStringVector, ExceptionCode& ec)
539 {
540     RefPtr<ContainerNode> parent = parentNode();
541     if (!parent)
542         return;
543
544     auto nodeSet = nodeSetPreTransformedFromNodeOrStringVector(nodeOrStringVector);
545     auto viableNextSibling = firstFollowingSiblingNotInNodeSet(*this, nodeSet);
546
547     auto node = convertNodesOrStringsIntoNode(*this, WTF::move(nodeOrStringVector), ec);
548     if (ec || !node)
549         return;
550
551     parent->insertBefore(node.releaseNonNull(), viableNextSibling.get(), ec);
552 }
553
554 void Node::replaceWith(Vector<NodeOrString>&& nodeOrStringVector, ExceptionCode& ec)
555 {
556     RefPtr<ContainerNode> parent = parentNode();
557     if (!parent)
558         return;
559
560     auto nodeSet = nodeSetPreTransformedFromNodeOrStringVector(nodeOrStringVector);
561     auto viableNextSibling = firstFollowingSiblingNotInNodeSet(*this, nodeSet);
562
563     auto node = convertNodesOrStringsIntoNode(*this, WTF::move(nodeOrStringVector), ec);
564     if (ec)
565         return;
566
567     if (parentNode() == parent) {
568         if (node)
569             parent->replaceChild(node.releaseNonNull(), *this, ec);
570         else
571             parent->removeChild(*this);
572     } else if (node)
573         parent->insertBefore(node.releaseNonNull(), viableNextSibling.get(), ec);
574 }
575
576 void Node::remove(ExceptionCode& ec)
577 {
578     if (ContainerNode* parent = parentNode())
579         parent->removeChild(*this, ec);
580 }
581
582 void Node::normalize()
583 {
584     // Go through the subtree beneath us, normalizing all nodes. This means that
585     // any two adjacent text nodes are merged and any empty text nodes are removed.
586
587     RefPtr<Node> node = this;
588     while (Node* firstChild = node->firstChild())
589         node = firstChild;
590     while (node) {
591         NodeType type = node->nodeType();
592         if (type == ELEMENT_NODE)
593             downcast<Element>(*node).normalizeAttributes();
594
595         if (node == this)
596             break;
597
598         if (type != TEXT_NODE) {
599             node = NodeTraversal::nextPostOrder(*node);
600             continue;
601         }
602
603         RefPtr<Text> text = downcast<Text>(node.get());
604
605         // Remove empty text nodes.
606         if (!text->length()) {
607             // Care must be taken to get the next node before removing the current node.
608             node = NodeTraversal::nextPostOrder(*node);
609             text->remove(IGNORE_EXCEPTION);
610             continue;
611         }
612
613         // Merge text nodes.
614         while (Node* nextSibling = node->nextSibling()) {
615             if (nextSibling->nodeType() != TEXT_NODE)
616                 break;
617             RefPtr<Text> nextText = downcast<Text>(nextSibling);
618
619             // Remove empty text nodes.
620             if (!nextText->length()) {
621                 nextText->remove(IGNORE_EXCEPTION);
622                 continue;
623             }
624
625             // Both non-empty text nodes. Merge them.
626             unsigned offset = text->length();
627             text->appendData(nextText->data());
628             document().textNodesMerged(nextText.get(), offset);
629             nextText->remove(IGNORE_EXCEPTION);
630         }
631
632         node = NodeTraversal::nextPostOrder(*node);
633     }
634 }
635
636 const AtomicString& Node::prefix() const
637 {
638     // For nodes other than elements and attributes, the prefix is always null
639     return nullAtom;
640 }
641
642 void Node::setPrefix(const AtomicString& /*prefix*/, ExceptionCode& ec)
643 {
644     // The spec says that for nodes other than elements and attributes, prefix is always null.
645     // It does not say what to do when the user tries to set the prefix on another type of
646     // node, however Mozilla throws a NAMESPACE_ERR exception.
647     ec = NAMESPACE_ERR;
648 }
649
650 const AtomicString& Node::localName() const
651 {
652     return nullAtom;
653 }
654
655 const AtomicString& Node::namespaceURI() const
656 {
657     return nullAtom;
658 }
659
660 bool Node::isContentEditable()
661 {
662     return computeEditability(UserSelectAllDoesNotAffectEditability, ShouldUpdateStyle::Update) != Editability::ReadOnly;
663 }
664
665 bool Node::isContentRichlyEditable()
666 {
667     return computeEditability(UserSelectAllIsAlwaysNonEditable, ShouldUpdateStyle::Update) == Editability::CanEditRichly;
668 }
669
670 void Node::inspect()
671 {
672     if (document().page())
673         document().page()->inspectorController().inspect(this);
674 }
675
676 static Node::Editability computeEditabilityFromComputedStyle(const Node& startNode, Node::UserSelectAllTreatment treatment)
677 {
678     // Ideally we'd call ASSERT(!needsStyleRecalc()) here, but
679     // ContainerNode::setFocus() calls setNeedsStyleRecalc(), so the assertion
680     // would fire in the middle of Document::setFocusedElement().
681
682     for (const Node* node = &startNode; node; node = node->parentNode()) {
683         RenderStyle* style = node->isDocumentNode() ? node->renderStyle() : const_cast<Node*>(node)->computedStyle();
684         if (!style)
685             continue;
686         if (style->display() == NONE)
687             continue;
688 #if ENABLE(USERSELECT_ALL)
689         // Elements with user-select: all style are considered atomic
690         // therefore non editable.
691         if (treatment == Node::UserSelectAllIsAlwaysNonEditable && style->userSelect() == SELECT_ALL)
692             return Node::Editability::ReadOnly;
693 #else
694         UNUSED_PARAM(treatment);
695 #endif
696         switch (style->userModify()) {
697         case READ_ONLY:
698             return Node::Editability::ReadOnly;
699         case READ_WRITE:
700             return Node::Editability::CanEditRichly;
701         case READ_WRITE_PLAINTEXT_ONLY:
702             return Node::Editability::CanEditPlainText;
703         }
704         ASSERT_NOT_REACHED();
705         return Node::Editability::ReadOnly;
706     }
707     return Node::Editability::ReadOnly;
708 }
709
710 Node::Editability Node::computeEditability(UserSelectAllTreatment treatment, ShouldUpdateStyle shouldUpdateStyle) const
711 {
712     if (!document().hasLivingRenderTree() || isPseudoElement())
713         return Editability::ReadOnly;
714
715     if (document().frame() && document().frame()->page() && document().frame()->page()->isEditable() && !containingShadowRoot())
716         return Editability::CanEditRichly;
717
718     if (shouldUpdateStyle == ShouldUpdateStyle::Update && document().needsStyleRecalc()) {
719         if (!document().usesStyleBasedEditability())
720             return HTMLElement::editabilityFromContentEditableAttr(*this);
721         document().updateStyleIfNeeded();
722     }
723     return computeEditabilityFromComputedStyle(*this, treatment);
724 }
725
726 RenderBox* Node::renderBox() const
727 {
728     RenderObject* renderer = this->renderer();
729     return is<RenderBox>(renderer) ? downcast<RenderBox>(renderer) : nullptr;
730 }
731
732 RenderBoxModelObject* Node::renderBoxModelObject() const
733 {
734     RenderObject* renderer = this->renderer();
735     return is<RenderBoxModelObject>(renderer) ? downcast<RenderBoxModelObject>(renderer) : nullptr;
736 }
737     
738 LayoutRect Node::renderRect(bool* isReplaced)
739 {    
740     RenderObject* hitRenderer = this->renderer();
741     ASSERT(hitRenderer);
742     RenderObject* renderer = hitRenderer;
743     while (renderer && !renderer->isBody() && !renderer->isRoot()) {
744         if (renderer->isRenderBlock() || renderer->isInlineBlockOrInlineTable() || renderer->isReplaced()) {
745             *isReplaced = renderer->isReplaced();
746             return renderer->absoluteBoundingBoxRect();
747         }
748         renderer = renderer->parent();
749     }
750     return LayoutRect();    
751 }
752
753 void Node::refEventTarget()
754 {
755     ref();
756 }
757
758 void Node::derefEventTarget()
759 {
760     deref();
761 }
762
763 inline void Node::updateAncestorsForStyleRecalc()
764 {
765     if (ContainerNode* ancestor = is<PseudoElement>(*this) ? downcast<PseudoElement>(*this).hostElement() : parentOrShadowHostNode()) {
766         ancestor->setDirectChildNeedsStyleRecalc();
767
768         if (is<Element>(*ancestor) && downcast<Element>(*ancestor).childrenAffectedByPropertyBasedBackwardPositionalRules()) {
769             if (ancestor->styleChangeType() < FullStyleChange)
770                 ancestor->setStyleChange(FullStyleChange);
771         }
772
773         for (; ancestor && !ancestor->childNeedsStyleRecalc(); ancestor = ancestor->parentOrShadowHostNode())
774             ancestor->setChildNeedsStyleRecalc();
775     }
776
777     Document& document = this->document();
778     if (document.childNeedsStyleRecalc())
779         document.scheduleStyleRecalc();
780 }
781
782 void Node::setNeedsStyleRecalc(StyleChangeType changeType)
783 {
784     ASSERT(changeType != NoStyleChange);
785     if (!inRenderedDocument())
786         return;
787
788     StyleChangeType existingChangeType = styleChangeType();
789     if (changeType > existingChangeType)
790         setStyleChange(changeType);
791
792     if (existingChangeType == NoStyleChange || changeType == ReconstructRenderTree)
793         updateAncestorsForStyleRecalc();
794 }
795
796 unsigned Node::computeNodeIndex() const
797 {
798     unsigned count = 0;
799     for (Node* sibling = previousSibling(); sibling; sibling = sibling->previousSibling())
800         ++count;
801     return count;
802 }
803
804 template<unsigned type>
805 bool shouldInvalidateNodeListCachesForAttr(const unsigned nodeListCounts[], const QualifiedName& attrName)
806 {
807     if (nodeListCounts[type] && shouldInvalidateTypeOnAttributeChange(static_cast<NodeListInvalidationType>(type), attrName))
808         return true;
809     return shouldInvalidateNodeListCachesForAttr<type + 1>(nodeListCounts, attrName);
810 }
811
812 template<>
813 bool shouldInvalidateNodeListCachesForAttr<numNodeListInvalidationTypes>(const unsigned[], const QualifiedName&)
814 {
815     return false;
816 }
817
818 bool Document::shouldInvalidateNodeListAndCollectionCaches(const QualifiedName* attrName) const
819 {
820     if (attrName)
821         return shouldInvalidateNodeListCachesForAttr<DoNotInvalidateOnAttributeChanges + 1>(m_nodeListAndCollectionCounts, *attrName);
822
823     for (int type = 0; type < numNodeListInvalidationTypes; type++) {
824         if (m_nodeListAndCollectionCounts[type])
825             return true;
826     }
827
828     return false;
829 }
830
831 void Document::invalidateNodeListAndCollectionCaches(const QualifiedName* attrName)
832 {
833 #if !ASSERT_DISABLED
834     m_inInvalidateNodeListAndCollectionCaches = true;
835 #endif
836     HashSet<LiveNodeList*> lists = WTF::move(m_listsInvalidatedAtDocument);
837     m_listsInvalidatedAtDocument.clear();
838     for (auto* list : lists)
839         list->invalidateCacheForAttribute(attrName);
840     HashSet<HTMLCollection*> collections = WTF::move(m_collectionsInvalidatedAtDocument);
841     for (auto* collection : collections)
842         collection->invalidateCacheForAttribute(attrName);
843 #if !ASSERT_DISABLED
844     m_inInvalidateNodeListAndCollectionCaches = false;
845 #endif
846 }
847
848 void Node::invalidateNodeListAndCollectionCachesInAncestors(const QualifiedName* attrName, Element* attributeOwnerElement)
849 {
850     if (hasRareData() && (!attrName || isAttributeNode())) {
851         if (NodeListsNodeData* lists = rareData()->nodeLists())
852             lists->clearChildNodeListCache();
853     }
854
855     // Modifications to attributes that are not associated with an Element can't invalidate NodeList caches.
856     if (attrName && !attributeOwnerElement)
857         return;
858
859     if (!document().shouldInvalidateNodeListAndCollectionCaches(attrName))
860         return;
861
862     document().invalidateNodeListAndCollectionCaches(attrName);
863
864     for (Node* node = this; node; node = node->parentNode()) {
865         if (!node->hasRareData())
866             continue;
867         NodeRareData* data = node->rareData();
868         if (data->nodeLists())
869             data->nodeLists()->invalidateCaches(attrName);
870     }
871 }
872
873 NodeListsNodeData* Node::nodeLists()
874 {
875     return hasRareData() ? rareData()->nodeLists() : 0;
876 }
877
878 void Node::clearNodeLists()
879 {
880     rareData()->clearNodeLists();
881 }
882
883 void Node::checkSetPrefix(const AtomicString& prefix, ExceptionCode& ec)
884 {
885     // Perform error checking as required by spec for setting Node.prefix. Used by
886     // Element::setPrefix() and Attr::setPrefix()
887
888     if (!prefix.isEmpty() && !Document::isValidName(prefix)) {
889         ec = INVALID_CHARACTER_ERR;
890         return;
891     }
892
893     if (isReadOnlyNode()) {
894         ec = NO_MODIFICATION_ALLOWED_ERR;
895         return;
896     }
897
898     // FIXME: Raise NAMESPACE_ERR if prefix is malformed per the Namespaces in XML specification.
899
900     const AtomicString& nodeNamespaceURI = namespaceURI();
901     if ((nodeNamespaceURI.isEmpty() && !prefix.isEmpty())
902         || (prefix == xmlAtom && nodeNamespaceURI != XMLNames::xmlNamespaceURI)) {
903         ec = NAMESPACE_ERR;
904         return;
905     }
906     // Attribute-specific checks are in Attr::setPrefix().
907 }
908
909 bool Node::isDescendantOf(const Node* other) const
910 {
911     // Return true if other is an ancestor of this, otherwise false
912     if (!other || !other->hasChildNodes() || inDocument() != other->inDocument())
913         return false;
914     if (other->isDocumentNode())
915         return &document() == other && !isDocumentNode() && inDocument();
916     for (const ContainerNode* n = parentNode(); n; n = n->parentNode()) {
917         if (n == other)
918             return true;
919     }
920     return false;
921 }
922
923 bool Node::isDescendantOrShadowDescendantOf(const Node* other) const
924 {
925     if (!other) 
926         return false;
927     if (isDescendantOf(other))
928         return true;
929     const Node* shadowAncestorNode = deprecatedShadowAncestorNode();
930     if (!shadowAncestorNode)
931         return false;
932     return shadowAncestorNode == other || shadowAncestorNode->isDescendantOf(other);
933 }
934
935 bool Node::contains(const Node* node) const
936 {
937     if (!node)
938         return false;
939     return this == node || node->isDescendantOf(this);
940 }
941
942 bool Node::containsIncludingShadowDOM(const Node* node) const
943 {
944     for (; node; node = node->parentOrShadowHostNode()) {
945         if (node == this)
946             return true;
947     }
948     return false;
949 }
950
951 bool Node::containsIncludingHostElements(const Node* node) const
952 {
953 #if ENABLE(TEMPLATE_ELEMENT)
954     while (node) {
955         if (node == this)
956             return true;
957         if (node->isDocumentFragment() && static_cast<const DocumentFragment*>(node)->isTemplateContent())
958             node = static_cast<const TemplateContentDocumentFragment*>(node)->host();
959         else
960             node = node->parentOrShadowHostNode();
961     }
962     return false;
963 #else
964     return containsIncludingShadowDOM(node);
965 #endif
966 }
967
968 Node* Node::pseudoAwarePreviousSibling() const
969 {
970     Element* parentOrHost = is<PseudoElement>(*this) ? downcast<PseudoElement>(*this).hostElement() : parentElement();
971     if (parentOrHost && !previousSibling()) {
972         if (isAfterPseudoElement() && parentOrHost->lastChild())
973             return parentOrHost->lastChild();
974         if (!isBeforePseudoElement())
975             return parentOrHost->beforePseudoElement();
976     }
977     return previousSibling();
978 }
979
980 Node* Node::pseudoAwareNextSibling() const
981 {
982     Element* parentOrHost = is<PseudoElement>(*this) ? downcast<PseudoElement>(*this).hostElement() : parentElement();
983     if (parentOrHost && !nextSibling()) {
984         if (isBeforePseudoElement() && parentOrHost->firstChild())
985             return parentOrHost->firstChild();
986         if (!isAfterPseudoElement())
987             return parentOrHost->afterPseudoElement();
988     }
989     return nextSibling();
990 }
991
992 Node* Node::pseudoAwareFirstChild() const
993 {
994     if (is<Element>(*this)) {
995         const Element& currentElement = downcast<Element>(*this);
996         Node* first = currentElement.beforePseudoElement();
997         if (first)
998             return first;
999         first = currentElement.firstChild();
1000         if (!first)
1001             first = currentElement.afterPseudoElement();
1002         return first;
1003     }
1004     return firstChild();
1005 }
1006
1007 Node* Node::pseudoAwareLastChild() const
1008 {
1009     if (is<Element>(*this)) {
1010         const Element& currentElement = downcast<Element>(*this);
1011         Node* last = currentElement.afterPseudoElement();
1012         if (last)
1013             return last;
1014         last = currentElement.lastChild();
1015         if (!last)
1016             last = currentElement.beforePseudoElement();
1017         return last;
1018     }
1019     return lastChild();
1020 }
1021
1022 RenderStyle* Node::computedStyle(PseudoId pseudoElementSpecifier)
1023 {
1024     for (Node* node = this; node; node = node->parentOrShadowHostNode()) {
1025         if (is<Element>(*node))
1026             return downcast<Element>(*node).computedStyle(pseudoElementSpecifier);
1027     }
1028     return nullptr;
1029 }
1030
1031 int Node::maxCharacterOffset() const
1032 {
1033     ASSERT_NOT_REACHED();
1034     return 0;
1035 }
1036
1037 // FIXME: Shouldn't these functions be in the editing code?  Code that asks questions about HTML in the core DOM class
1038 // is obviously misplaced.
1039 bool Node::canStartSelection() const
1040 {
1041     if (hasEditableStyle())
1042         return true;
1043
1044     if (renderer()) {
1045         const RenderStyle& style = renderer()->style();
1046         // We allow selections to begin within an element that has -webkit-user-select: none set,
1047         // but if the element is draggable then dragging should take priority over selection.
1048         if (style.userDrag() == DRAG_ELEMENT && style.userSelect() == SELECT_NONE)
1049             return false;
1050     }
1051     return parentOrShadowHostNode() ? parentOrShadowHostNode()->canStartSelection() : true;
1052 }
1053
1054 Element* Node::shadowHost() const
1055 {
1056     if (ShadowRoot* root = containingShadowRoot())
1057         return root->host();
1058     return nullptr;
1059 }
1060
1061 Node* Node::deprecatedShadowAncestorNode() const
1062 {
1063     if (ShadowRoot* root = containingShadowRoot())
1064         return root->host();
1065
1066     return const_cast<Node*>(this);
1067 }
1068
1069 ShadowRoot* Node::containingShadowRoot() const
1070 {
1071     ContainerNode& root = treeScope().rootNode();
1072     return is<ShadowRoot>(root) ? downcast<ShadowRoot>(&root) : nullptr;
1073 }
1074
1075 #if ENABLE(SHADOW_DOM)
1076 HTMLSlotElement* Node::assignedSlot() const
1077 {
1078     auto* parent = parentElement();
1079     if (!parent)
1080         return nullptr;
1081
1082     auto* shadowRoot = parent->shadowRoot();
1083     if (!shadowRoot || shadowRoot->type() != ShadowRoot::Type::Open)
1084         return nullptr;
1085
1086     return shadowRoot->findAssignedSlot(*this);
1087 }
1088 #endif
1089
1090 bool Node::isInUserAgentShadowTree() const
1091 {
1092     auto* shadowRoot = containingShadowRoot();
1093     return shadowRoot && shadowRoot->type() == ShadowRoot::Type::UserAgent;
1094 }
1095
1096 Node* Node::nonBoundaryShadowTreeRootNode()
1097 {
1098     ASSERT(!isShadowRoot());
1099     Node* root = this;
1100     while (root) {
1101         if (root->isShadowRoot())
1102             return root;
1103         Node* parent = root->parentNodeGuaranteedHostFree();
1104         if (parent && parent->isShadowRoot())
1105             return root;
1106         root = parent;
1107     }
1108     return 0;
1109 }
1110
1111 ContainerNode* Node::nonShadowBoundaryParentNode() const
1112 {
1113     ContainerNode* parent = parentNode();
1114     return parent && !parent->isShadowRoot() ? parent : 0;
1115 }
1116
1117 Element* Node::parentOrShadowHostElement() const
1118 {
1119     ContainerNode* parent = parentOrShadowHostNode();
1120     if (!parent)
1121         return nullptr;
1122
1123     if (is<ShadowRoot>(*parent))
1124         return downcast<ShadowRoot>(*parent).host();
1125
1126     if (!is<Element>(*parent))
1127         return nullptr;
1128
1129     return downcast<Element>(parent);
1130 }
1131
1132 Node* Node::insertionParentForBinding() const
1133 {
1134     return findInsertionPointOf(this);
1135 }
1136
1137 Node::InsertionNotificationRequest Node::insertedInto(ContainerNode& insertionPoint)
1138 {
1139     ASSERT(insertionPoint.inDocument() || isContainerNode());
1140     if (insertionPoint.inDocument())
1141         setFlag(InDocumentFlag);
1142     if (parentOrShadowHostNode()->isInShadowTree())
1143         setFlag(IsInShadowTreeFlag);
1144     return InsertionDone;
1145 }
1146
1147 void Node::removedFrom(ContainerNode& insertionPoint)
1148 {
1149     ASSERT(insertionPoint.inDocument() || isContainerNode());
1150     if (insertionPoint.inDocument())
1151         clearFlag(InDocumentFlag);
1152     if (isInShadowTree() && !treeScope().rootNode().isShadowRoot())
1153         clearFlag(IsInShadowTreeFlag);
1154 }
1155
1156 bool Node::isRootEditableElement() const
1157 {
1158     return hasEditableStyle() && isElementNode() && (!parentNode() || !parentNode()->hasEditableStyle()
1159         || !parentNode()->isElementNode() || hasTagName(bodyTag));
1160 }
1161
1162 Element* Node::rootEditableElement() const
1163 {
1164     Element* result = nullptr;
1165     for (Node* node = const_cast<Node*>(this); node && node->hasEditableStyle(); node = node->parentNode()) {
1166         if (is<Element>(*node))
1167             result = downcast<Element>(node);
1168         if (is<HTMLBodyElement>(*node))
1169             break;
1170     }
1171     return result;
1172 }
1173
1174 // FIXME: End of obviously misplaced HTML editing functions.  Try to move these out of Node.
1175
1176 Document* Node::ownerDocument() const
1177 {
1178     Document* document = &this->document();
1179     return document == this ? nullptr : document;
1180 }
1181
1182 URL Node::baseURI() const
1183 {
1184     return document().baseURL();
1185 }
1186
1187 bool Node::isEqualNode(Node* other) const
1188 {
1189     if (!other)
1190         return false;
1191     
1192     NodeType nodeType = this->nodeType();
1193     if (nodeType != other->nodeType())
1194         return false;
1195     
1196     if (nodeName() != other->nodeName())
1197         return false;
1198     
1199     if (localName() != other->localName())
1200         return false;
1201     
1202     if (namespaceURI() != other->namespaceURI())
1203         return false;
1204     
1205     if (prefix() != other->prefix())
1206         return false;
1207     
1208     if (nodeValue() != other->nodeValue())
1209         return false;
1210     
1211     if (is<Element>(*this) && !downcast<Element>(*this).hasEquivalentAttributes(downcast<Element>(other)))
1212         return false;
1213     
1214     Node* child = firstChild();
1215     Node* otherChild = other->firstChild();
1216     
1217     while (child) {
1218         if (!child->isEqualNode(otherChild))
1219             return false;
1220         
1221         child = child->nextSibling();
1222         otherChild = otherChild->nextSibling();
1223     }
1224     
1225     if (otherChild)
1226         return false;
1227     
1228     if (nodeType == DOCUMENT_TYPE_NODE) {
1229         const DocumentType* documentTypeThis = static_cast<const DocumentType*>(this);
1230         const DocumentType* documentTypeOther = static_cast<const DocumentType*>(other);
1231         
1232         if (documentTypeThis->publicId() != documentTypeOther->publicId())
1233             return false;
1234
1235         if (documentTypeThis->systemId() != documentTypeOther->systemId())
1236             return false;
1237
1238         if (documentTypeThis->internalSubset() != documentTypeOther->internalSubset())
1239             return false;
1240
1241         // FIXME: We don't compare entities or notations because currently both are always empty.
1242     }
1243     
1244     return true;
1245 }
1246
1247 bool Node::isDefaultNamespace(const AtomicString& namespaceURIMaybeEmpty) const
1248 {
1249     const AtomicString& namespaceURI = namespaceURIMaybeEmpty.isEmpty() ? nullAtom : namespaceURIMaybeEmpty;
1250
1251     switch (nodeType()) {
1252         case ELEMENT_NODE: {
1253             const Element& element = downcast<Element>(*this);
1254             
1255             if (element.prefix().isNull())
1256                 return element.namespaceURI() == namespaceURI;
1257
1258             if (element.hasAttributes()) {
1259                 for (const Attribute& attribute : element.attributesIterator()) {
1260                     if (attribute.localName() == xmlnsAtom)
1261                         return attribute.value() == namespaceURI;
1262                 }
1263             }
1264
1265             if (Element* ancestor = ancestorElement())
1266                 return ancestor->isDefaultNamespace(namespaceURI);
1267
1268             return false;
1269         }
1270         case DOCUMENT_NODE:
1271             if (Element* documentElement = downcast<Document>(*this).documentElement())
1272                 return documentElement->isDefaultNamespace(namespaceURI);
1273             return false;
1274         case ENTITY_NODE:
1275         case DOCUMENT_TYPE_NODE:
1276         case DOCUMENT_FRAGMENT_NODE:
1277             return false;
1278         case ATTRIBUTE_NODE: {
1279             const Attr* attr = static_cast<const Attr*>(this);
1280             if (attr->ownerElement())
1281                 return attr->ownerElement()->isDefaultNamespace(namespaceURI);
1282             return false;
1283         }
1284         default:
1285             if (Element* ancestor = ancestorElement())
1286                 return ancestor->isDefaultNamespace(namespaceURI);
1287             return false;
1288     }
1289 }
1290
1291 String Node::lookupPrefix(const AtomicString &namespaceURI) const
1292 {
1293     // Implemented according to
1294     // http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/namespaces-algorithms.html#lookupNamespacePrefixAlgo
1295     
1296     if (namespaceURI.isEmpty())
1297         return String();
1298     
1299     switch (nodeType()) {
1300         case ELEMENT_NODE:
1301             return lookupNamespacePrefix(namespaceURI, static_cast<const Element *>(this));
1302         case DOCUMENT_NODE:
1303             if (Element* documentElement = downcast<Document>(*this).documentElement())
1304                 return documentElement->lookupPrefix(namespaceURI);
1305             return String();
1306         case ENTITY_NODE:
1307         case DOCUMENT_FRAGMENT_NODE:
1308         case DOCUMENT_TYPE_NODE:
1309             return String();
1310         case ATTRIBUTE_NODE: {
1311             const Attr *attr = static_cast<const Attr *>(this);
1312             if (attr->ownerElement())
1313                 return attr->ownerElement()->lookupPrefix(namespaceURI);
1314             return String();
1315         }
1316         default:
1317             if (Element* ancestor = ancestorElement())
1318                 return ancestor->lookupPrefix(namespaceURI);
1319             return String();
1320     }
1321 }
1322
1323 String Node::lookupNamespaceURI(const String &prefix) const
1324 {
1325     // Implemented according to
1326     // http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/namespaces-algorithms.html#lookupNamespaceURIAlgo
1327     
1328     if (!prefix.isNull() && prefix.isEmpty())
1329         return String();
1330     
1331     switch (nodeType()) {
1332         case ELEMENT_NODE: {
1333             const Element *elem = static_cast<const Element *>(this);
1334             
1335             if (!elem->namespaceURI().isNull() && elem->prefix() == prefix)
1336                 return elem->namespaceURI();
1337             
1338             if (elem->hasAttributes()) {
1339                 for (const Attribute& attribute : elem->attributesIterator()) {
1340                     
1341                     if (attribute.prefix() == xmlnsAtom && attribute.localName() == prefix) {
1342                         if (!attribute.value().isEmpty())
1343                             return attribute.value();
1344                         
1345                         return String();
1346                     }
1347                     if (attribute.localName() == xmlnsAtom && prefix.isNull()) {
1348                         if (!attribute.value().isEmpty())
1349                             return attribute.value();
1350                         
1351                         return String();
1352                     }
1353                 }
1354             }
1355             if (Element* ancestor = ancestorElement())
1356                 return ancestor->lookupNamespaceURI(prefix);
1357             return String();
1358         }
1359         case DOCUMENT_NODE:
1360             if (Element* documentElement = downcast<Document>(*this).documentElement())
1361                 return documentElement->lookupNamespaceURI(prefix);
1362             return String();
1363         case ENTITY_NODE:
1364         case DOCUMENT_TYPE_NODE:
1365         case DOCUMENT_FRAGMENT_NODE:
1366             return String();
1367         case ATTRIBUTE_NODE: {
1368             const Attr *attr = static_cast<const Attr *>(this);
1369             
1370             if (attr->ownerElement())
1371                 return attr->ownerElement()->lookupNamespaceURI(prefix);
1372             else
1373                 return String();
1374         }
1375         default:
1376             if (Element* ancestor = ancestorElement())
1377                 return ancestor->lookupNamespaceURI(prefix);
1378             return String();
1379     }
1380 }
1381
1382 String Node::lookupNamespacePrefix(const AtomicString &_namespaceURI, const Element *originalElement) const
1383 {
1384     if (_namespaceURI.isNull())
1385         return String();
1386             
1387     if (originalElement->lookupNamespaceURI(prefix()) == _namespaceURI)
1388         return prefix();
1389     
1390     ASSERT(is<Element>(*this));
1391     const Element& thisElement = downcast<Element>(*this);
1392     if (thisElement.hasAttributes()) {
1393         for (const Attribute& attribute : thisElement.attributesIterator()) {
1394             if (attribute.prefix() == xmlnsAtom && attribute.value() == _namespaceURI
1395                 && originalElement->lookupNamespaceURI(attribute.localName()) == _namespaceURI)
1396                 return attribute.localName();
1397         }
1398     }
1399     
1400     if (Element* ancestor = ancestorElement())
1401         return ancestor->lookupNamespacePrefix(_namespaceURI, originalElement);
1402     return String();
1403 }
1404
1405 static void appendTextContent(const Node* node, bool convertBRsToNewlines, bool& isNullString, StringBuilder& content)
1406 {
1407     switch (node->nodeType()) {
1408     case Node::TEXT_NODE:
1409     case Node::CDATA_SECTION_NODE:
1410     case Node::COMMENT_NODE:
1411         isNullString = false;
1412         content.append(static_cast<const CharacterData*>(node)->data());
1413         break;
1414
1415     case Node::PROCESSING_INSTRUCTION_NODE:
1416         isNullString = false;
1417         content.append(static_cast<const ProcessingInstruction*>(node)->data());
1418         break;
1419     
1420     case Node::ELEMENT_NODE:
1421         if (node->hasTagName(brTag) && convertBRsToNewlines) {
1422             isNullString = false;
1423             content.append('\n');
1424             break;
1425         }
1426         FALLTHROUGH;
1427     case Node::ATTRIBUTE_NODE:
1428     case Node::ENTITY_NODE:
1429     case Node::ENTITY_REFERENCE_NODE:
1430     case Node::DOCUMENT_FRAGMENT_NODE:
1431         isNullString = false;
1432         for (Node* child = node->firstChild(); child; child = child->nextSibling()) {
1433             if (child->nodeType() == Node::COMMENT_NODE || child->nodeType() == Node::PROCESSING_INSTRUCTION_NODE)
1434                 continue;
1435             appendTextContent(child, convertBRsToNewlines, isNullString, content);
1436         }
1437         break;
1438
1439     case Node::DOCUMENT_NODE:
1440     case Node::DOCUMENT_TYPE_NODE:
1441     case Node::XPATH_NAMESPACE_NODE:
1442         break;
1443     }
1444 }
1445
1446 String Node::textContent(bool convertBRsToNewlines) const
1447 {
1448     StringBuilder content;
1449     bool isNullString = true;
1450     appendTextContent(this, convertBRsToNewlines, isNullString, content);
1451     return isNullString ? String() : content.toString();
1452 }
1453
1454 void Node::setTextContent(const String& text, ExceptionCode& ec)
1455 {           
1456     switch (nodeType()) {
1457         case TEXT_NODE:
1458         case CDATA_SECTION_NODE:
1459         case COMMENT_NODE:
1460         case PROCESSING_INSTRUCTION_NODE:
1461             setNodeValue(text, ec);
1462             return;
1463         case ELEMENT_NODE:
1464         case ATTRIBUTE_NODE:
1465         case ENTITY_NODE:
1466         case ENTITY_REFERENCE_NODE:
1467         case DOCUMENT_FRAGMENT_NODE: {
1468             Ref<ContainerNode> container(downcast<ContainerNode>(*this));
1469             ChildListMutationScope mutation(container);
1470             container->removeChildren();
1471             if (!text.isEmpty())
1472                 container->appendChild(document().createTextNode(text), ec);
1473             return;
1474         }
1475         case DOCUMENT_NODE:
1476         case DOCUMENT_TYPE_NODE:
1477         case XPATH_NAMESPACE_NODE:
1478             // Do nothing.
1479             return;
1480     }
1481     ASSERT_NOT_REACHED();
1482 }
1483
1484 Element* Node::ancestorElement() const
1485 {
1486     // In theory, there can be EntityReference nodes between elements, but this is currently not supported.
1487     for (ContainerNode* ancestor = parentNode(); ancestor; ancestor = ancestor->parentNode()) {
1488         if (is<Element>(*ancestor))
1489             return downcast<Element>(ancestor);
1490     }
1491     return nullptr;
1492 }
1493
1494 bool Node::offsetInCharacters() const
1495 {
1496     return false;
1497 }
1498
1499 static SHA1::Digest hashPointer(void* pointer)
1500 {
1501     SHA1 sha1;
1502     sha1.addBytes(reinterpret_cast<const uint8_t*>(&pointer), sizeof(pointer));
1503     SHA1::Digest digest;
1504     sha1.computeHash(digest);
1505     return digest;
1506 }
1507
1508 static inline unsigned short compareDetachedElementsPosition(Node* firstNode, Node* secondNode)
1509 {
1510     // If the 2 nodes are not in the same tree, return the result of adding DOCUMENT_POSITION_DISCONNECTED,
1511     // DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC, and either DOCUMENT_POSITION_PRECEDING or
1512     // DOCUMENT_POSITION_FOLLOWING, with the constraint that this is to be consistent. Whether to return
1513     // DOCUMENT_POSITION_PRECEDING or DOCUMENT_POSITION_FOLLOWING is implemented by comparing cryptographic
1514     // hashes of Node pointers.
1515     // See step 3 in https://dom.spec.whatwg.org/#dom-node-comparedocumentposition
1516     SHA1::Digest firstHash = hashPointer(firstNode);
1517     SHA1::Digest secondHash = hashPointer(secondNode);
1518
1519     unsigned short direction = memcmp(firstHash.data(), secondHash.data(), SHA1::hashSize) > 0 ? Node::DOCUMENT_POSITION_PRECEDING : Node::DOCUMENT_POSITION_FOLLOWING;
1520
1521     return Node::DOCUMENT_POSITION_DISCONNECTED | Node::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | direction;
1522 }
1523
1524 unsigned short Node::compareDocumentPosition(Node* otherNode)
1525 {
1526     // It is not clear what should be done if |otherNode| is nullptr.
1527     if (!otherNode)
1528         return DOCUMENT_POSITION_DISCONNECTED;
1529
1530     if (otherNode == this)
1531         return DOCUMENT_POSITION_EQUIVALENT;
1532     
1533     Attr* attr1 = is<Attr>(*this) ? downcast<Attr>(this) : nullptr;
1534     Attr* attr2 = is<Attr>(*otherNode) ? downcast<Attr>(otherNode) : nullptr;
1535     
1536     Node* start1 = attr1 ? attr1->ownerElement() : this;
1537     Node* start2 = attr2 ? attr2->ownerElement() : otherNode;
1538     
1539     // If either of start1 or start2 is null, then we are disconnected, since one of the nodes is
1540     // an orphaned attribute node.
1541     if (!start1 || !start2)
1542         return compareDetachedElementsPosition(this, otherNode);
1543
1544     Vector<Node*, 16> chain1;
1545     Vector<Node*, 16> chain2;
1546     if (attr1)
1547         chain1.append(attr1);
1548     if (attr2)
1549         chain2.append(attr2);
1550     
1551     if (attr1 && attr2 && start1 == start2 && start1) {
1552         // We are comparing two attributes on the same node. Crawl our attribute map and see which one we hit first.
1553         Element* owner1 = attr1->ownerElement();
1554         owner1->synchronizeAllAttributes();
1555         for (const Attribute& attribute : owner1->attributesIterator()) {
1556             // If neither of the two determining nodes is a child node and nodeType is the same for both determining nodes, then an
1557             // implementation-dependent order between the determining nodes is returned. This order is stable as long as no nodes of
1558             // the same nodeType are inserted into or removed from the direct container. This would be the case, for example, 
1559             // when comparing two attributes of the same element, and inserting or removing additional attributes might change 
1560             // the order between existing attributes.
1561             if (attr1->qualifiedName() == attribute.name())
1562                 return DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | DOCUMENT_POSITION_FOLLOWING;
1563             if (attr2->qualifiedName() == attribute.name())
1564                 return DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | DOCUMENT_POSITION_PRECEDING;
1565         }
1566         
1567         ASSERT_NOT_REACHED();
1568         return DOCUMENT_POSITION_DISCONNECTED;
1569     }
1570
1571     // If one node is in the document and the other is not, we must be disconnected.
1572     // If the nodes have different owning documents, they must be disconnected.  Note that we avoid
1573     // comparing Attr nodes here, since they return false from inDocument() all the time (which seems like a bug).
1574     if (start1->inDocument() != start2->inDocument() || &start1->treeScope() != &start2->treeScope())
1575         return compareDetachedElementsPosition(this, otherNode);
1576
1577     // We need to find a common ancestor container, and then compare the indices of the two immediate children.
1578     Node* current;
1579     for (current = start1; current; current = current->parentNode())
1580         chain1.append(current);
1581     for (current = start2; current; current = current->parentNode())
1582         chain2.append(current);
1583
1584     unsigned index1 = chain1.size();
1585     unsigned index2 = chain2.size();
1586
1587     // If the two elements don't have a common root, they're not in the same tree.
1588     if (chain1[index1 - 1] != chain2[index2 - 1])
1589         return compareDetachedElementsPosition(this, otherNode);
1590
1591     // Walk the two chains backwards and look for the first difference.
1592     for (unsigned i = std::min(index1, index2); i; --i) {
1593         Node* child1 = chain1[--index1];
1594         Node* child2 = chain2[--index2];
1595         if (child1 != child2) {
1596             // If one of the children is an attribute, it wins.
1597             if (child1->nodeType() == ATTRIBUTE_NODE)
1598                 return DOCUMENT_POSITION_FOLLOWING;
1599             if (child2->nodeType() == ATTRIBUTE_NODE)
1600                 return DOCUMENT_POSITION_PRECEDING;
1601             
1602             if (!child2->nextSibling())
1603                 return DOCUMENT_POSITION_FOLLOWING;
1604             if (!child1->nextSibling())
1605                 return DOCUMENT_POSITION_PRECEDING;
1606
1607             // Otherwise we need to see which node occurs first.  Crawl backwards from child2 looking for child1.
1608             for (Node* child = child2->previousSibling(); child; child = child->previousSibling()) {
1609                 if (child == child1)
1610                     return DOCUMENT_POSITION_FOLLOWING;
1611             }
1612             return DOCUMENT_POSITION_PRECEDING;
1613         }
1614     }
1615     
1616     // There was no difference between the two parent chains, i.e., one was a subset of the other.  The shorter
1617     // chain is the ancestor.
1618     return index1 < index2 ? 
1619                DOCUMENT_POSITION_FOLLOWING | DOCUMENT_POSITION_CONTAINED_BY :
1620                DOCUMENT_POSITION_PRECEDING | DOCUMENT_POSITION_CONTAINS;
1621 }
1622
1623 FloatPoint Node::convertToPage(const FloatPoint& p) const
1624 {
1625     // If there is a renderer, just ask it to do the conversion
1626     if (renderer())
1627         return renderer()->localToAbsolute(p, UseTransforms);
1628     
1629     // Otherwise go up the tree looking for a renderer
1630     Element *parent = ancestorElement();
1631     if (parent)
1632         return parent->convertToPage(p);
1633
1634     // No parent - no conversion needed
1635     return p;
1636 }
1637
1638 FloatPoint Node::convertFromPage(const FloatPoint& p) const
1639 {
1640     // If there is a renderer, just ask it to do the conversion
1641     if (renderer())
1642         return renderer()->absoluteToLocal(p, UseTransforms);
1643
1644     // Otherwise go up the tree looking for a renderer
1645     Element *parent = ancestorElement();
1646     if (parent)
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, RefPtr<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, WTF::move(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, RefPtr<EventListener>&& listener, bool useCapture)
1942 {
1943     return tryAddEventListener(this, eventType, WTF::move(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             const size_t size = registry->size();
2118             for (size_t i = 0; i < size; ++i)
2119                 registry->at(i)->observedSubtreeNodeWillDetach(this);
2120         }
2121
2122         if (auto* transientRegistry = node->transientMutationObserverRegistry()) {
2123             for (auto* registration : *transientRegistry)
2124                 registration->observedSubtreeNodeWillDetach(this);
2125         }
2126     }
2127 }
2128
2129 void Node::handleLocalEvents(Event& event)
2130 {
2131     if (!hasEventTargetData())
2132         return;
2133
2134     if (is<Element>(*this) && downcast<Element>(*this).isDisabledFormControl() && event.isMouseEvent())
2135         return;
2136
2137     fireEventListeners(&event);
2138 }
2139
2140 void Node::dispatchScopedEvent(PassRefPtr<Event> event)
2141 {
2142     EventDispatcher::dispatchScopedEvent(*this, event);
2143 }
2144
2145 bool Node::dispatchEvent(PassRefPtr<Event> event)
2146 {
2147 #if ENABLE(TOUCH_EVENTS) && !PLATFORM(IOS)
2148     if (is<TouchEvent>(*event))
2149         return dispatchTouchEvent(adoptRef(downcast<TouchEvent>(event.leakRef())));
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     RefPtr<UIEvent> event = UIEvent::create(eventNames().DOMActivateEvent, true, true, document().defaultView(), detail);
2174     event->setUnderlyingEvent(underlyingEvent);
2175     dispatchScopedEvent(event);
2176     return event->defaultHandled();
2177 }
2178
2179 #if ENABLE(TOUCH_EVENTS) && !PLATFORM(IOS)
2180 bool Node::dispatchTouchEvent(PassRefPtr<TouchEvent> event)
2181 {
2182     return EventDispatcher::dispatchEvent(this, event);
2183 }
2184 #endif
2185
2186 #if ENABLE(INDIE_UI)
2187 bool Node::dispatchUIRequestEvent(PassRefPtr<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> protect(*this);
2200     RefPtr<BeforeLoadEvent> beforeLoadEvent = BeforeLoadEvent::create(sourceURL);
2201     dispatchEvent(beforeLoadEvent.get());
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)