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