An assertion failure inside removeChildren
[WebKit-https.git] / Source / WebCore / dom / ContainerNode.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, 2012, 2013, 2016 Apple Inc. All rights reserved.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Library General Public
9  * License as published by the Free Software Foundation; either
10  * version 2 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Library General Public License for more details.
16  *
17  * You should have received a copy of the GNU Library General Public License
18  * along with this library; see the file COPYING.LIB.  If not, write to
19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20  * Boston, MA 02110-1301, USA.
21  */
22
23 #include "config.h"
24 #include "ContainerNode.h"
25
26 #include "AXObjectCache.h"
27 #include "AllDescendantsCollection.h"
28 #include "ChildListMutationScope.h"
29 #include "ClassCollection.h"
30 #include "CommonVM.h"
31 #include "ContainerNodeAlgorithms.h"
32 #include "Editor.h"
33 #include "EventNames.h"
34 #include "FloatRect.h"
35 #include "FrameView.h"
36 #include "GenericCachedHTMLCollection.h"
37 #include "HTMLFormControlsCollection.h"
38 #include "HTMLOptionsCollection.h"
39 #include "HTMLSlotElement.h"
40 #include "HTMLTableRowsCollection.h"
41 #include "InlineTextBox.h"
42 #include "InspectorInstrumentation.h"
43 #include "JSNode.h"
44 #include "LabelsNodeList.h"
45 #include "MutationEvent.h"
46 #include "NameNodeList.h"
47 #include "NoEventDispatchAssertion.h"
48 #include "NodeRareData.h"
49 #include "NodeRenderStyle.h"
50 #include "RadioNodeList.h"
51 #include "RenderBox.h"
52 #include "RenderTheme.h"
53 #include "RenderTreeUpdater.h"
54 #include "RenderWidget.h"
55 #include "RootInlineBox.h"
56 #include "SVGDocumentExtensions.h"
57 #include "SVGElement.h"
58 #include "SVGNames.h"
59 #include "SVGUseElement.h"
60 #include "SelectorQuery.h"
61 #include "TemplateContentDocumentFragment.h"
62 #include <algorithm>
63 #include <wtf/Variant.h>
64
65 namespace WebCore {
66
67 static void dispatchChildInsertionEvents(Node&);
68 static void dispatchChildRemovalEvents(Node&);
69
70 ChildNodesLazySnapshot* ChildNodesLazySnapshot::latestSnapshot;
71
72 #ifndef NDEBUG
73 unsigned NoEventDispatchAssertion::s_count = 0;
74 NoEventDispatchAssertion::EventAllowedScope* NoEventDispatchAssertion::EventAllowedScope::s_currentScope = nullptr;
75 #endif
76
77 static ExceptionOr<void> collectChildrenAndRemoveFromOldParent(Node& node, NodeVector& nodes)
78 {
79     if (!is<DocumentFragment>(node)) {
80         nodes.append(node);
81         auto* oldParent = node.parentNode();
82         if (!oldParent)
83             return { };
84         return oldParent->removeChild(node);
85     }
86
87     getChildNodes(node, nodes);
88     downcast<DocumentFragment>(node).removeChildren();
89     return { };
90 }
91
92 // FIXME: This function must get a new name.
93 // It removes all children, not just a category called "detached children".
94 // So this name is terribly confusing.
95 void ContainerNode::removeDetachedChildren()
96 {
97     if (connectedSubframeCount()) {
98         for (Node* child = firstChild(); child; child = child->nextSibling())
99             child->updateAncestorConnectedSubframeCountForRemoval();
100     }
101     // FIXME: We should be able to ASSERT(!attached()) here: https://bugs.webkit.org/show_bug.cgi?id=107801
102     removeDetachedChildrenInContainer(*this);
103 }
104
105 static inline void destroyRenderTreeIfNeeded(Node& child)
106 {
107     bool childIsHTMLSlotElement = false;
108     childIsHTMLSlotElement = is<HTMLSlotElement>(child);
109     // FIXME: Get rid of the named flow test.
110     bool isElement = is<Element>(child);
111     if (!child.renderer() && !childIsHTMLSlotElement
112         && !(isElement && downcast<Element>(child).isNamedFlowContentElement()))
113         return;
114     if (isElement)
115         RenderTreeUpdater::tearDownRenderers(downcast<Element>(child));
116     else if (is<Text>(child))
117         RenderTreeUpdater::tearDownRenderer(downcast<Text>(child));
118 }
119
120 void ContainerNode::takeAllChildrenFrom(ContainerNode* oldParent)
121 {
122     ASSERT(oldParent);
123
124     NodeVector children;
125     getChildNodes(*oldParent, children);
126
127     if (oldParent->document().hasMutationObserversOfType(MutationObserver::ChildList)) {
128         ChildListMutationScope mutation(*oldParent);
129         for (auto& child : children)
130             mutation.willRemoveChild(child);
131     }
132
133     disconnectSubframesIfNeeded(*oldParent, DescendantsOnly);
134     {
135         NoEventDispatchAssertion assertNoEventDispatch;
136
137         oldParent->document().nodeChildrenWillBeRemoved(*oldParent);
138
139         WidgetHierarchyUpdatesSuspensionScope suspendWidgetHierarchyUpdates;
140         while (RefPtr<Node> child = oldParent->m_firstChild) {
141             oldParent->removeBetween(nullptr, child->nextSibling(), *child);
142             notifyChildNodeRemoved(*oldParent, *child);
143         }
144         ChildChange change = { AllChildrenRemoved, nullptr, nullptr, ChildChangeSourceParser };
145         childrenChanged(change);
146     }
147
148     document().notifyRemovePendingSheetIfNeeded();
149
150     // FIXME: assert that we don't dispatch events here since this container node is still disconnected.
151     for (auto& child : children) {
152         RELEASE_ASSERT(!child->parentNode() && &child->treeScope() == &treeScope());
153         ASSERT(!ensurePreInsertionValidity(child, nullptr).hasException());
154         treeScope().adoptIfNeeded(child);
155         parserAppendChild(child);
156     }
157 }
158
159 ContainerNode::~ContainerNode()
160 {
161     if (!isDocumentNode())
162         willBeDeletedFrom(document());
163     removeDetachedChildren();
164 }
165
166 static inline bool isChildTypeAllowed(ContainerNode& newParent, Node& child)
167 {
168     if (!child.isDocumentFragment())
169         return newParent.childTypeAllowed(child.nodeType());
170
171     for (Node* node = child.firstChild(); node; node = node->nextSibling()) {
172         if (!newParent.childTypeAllowed(node->nodeType()))
173             return false;
174     }
175     return true;
176 }
177
178 static inline bool isInTemplateContent(const Node* node)
179 {
180     Document& document = node->document();
181     return &document == document.templateDocument();
182 }
183
184 static inline bool containsConsideringHostElements(const Node& newChild, const Node& newParent)
185 {
186     return (newParent.isInShadowTree() || isInTemplateContent(&newParent))
187         ? newChild.containsIncludingHostElements(&newParent)
188         : newChild.contains(&newParent);
189 }
190
191 static inline ExceptionOr<void> checkAcceptChild(ContainerNode& newParent, Node& newChild, const Node* refChild, Document::AcceptChildOperation operation)
192 {
193     // Use common case fast path if possible.
194     if ((newChild.isElementNode() || newChild.isTextNode()) && newParent.isElementNode()) {
195         ASSERT(!newParent.isDocumentTypeNode());
196         ASSERT(isChildTypeAllowed(newParent, newChild));
197         if (containsConsideringHostElements(newChild, newParent))
198             return Exception { HIERARCHY_REQUEST_ERR };
199         if (operation == Document::AcceptChildOperation::InsertOrAdd && refChild && refChild->parentNode() != &newParent)
200             return Exception { NOT_FOUND_ERR };
201         return { };
202     }
203
204     // This should never happen, but also protect release builds from tree corruption.
205     ASSERT(!newChild.isPseudoElement());
206     if (newChild.isPseudoElement())
207         return Exception { HIERARCHY_REQUEST_ERR };
208
209     if (containsConsideringHostElements(newChild, newParent))
210         return Exception { HIERARCHY_REQUEST_ERR };
211
212     if (operation == Document::AcceptChildOperation::InsertOrAdd && refChild && refChild->parentNode() != &newParent)
213         return Exception { NOT_FOUND_ERR };
214
215     if (is<Document>(newParent)) {
216         if (!downcast<Document>(newParent).canAcceptChild(newChild, refChild, operation))
217             return Exception { HIERARCHY_REQUEST_ERR };
218     } else if (!isChildTypeAllowed(newParent, newChild))
219         return Exception { HIERARCHY_REQUEST_ERR };
220
221     return { };
222 }
223
224 static inline ExceptionOr<void> checkAcceptChildGuaranteedNodeTypes(ContainerNode& newParent, Node& newChild)
225 {
226     ASSERT(!newParent.isDocumentTypeNode());
227     ASSERT(isChildTypeAllowed(newParent, newChild));
228     if (newChild.contains(&newParent))
229         return Exception { HIERARCHY_REQUEST_ERR };
230     return { };
231 }
232
233 // https://dom.spec.whatwg.org/#concept-node-ensure-pre-insertion-validity
234 ExceptionOr<void> ContainerNode::ensurePreInsertionValidity(Node& newChild, Node* refChild)
235 {
236     return checkAcceptChild(*this, newChild, refChild, Document::AcceptChildOperation::InsertOrAdd);
237 }
238
239 // https://dom.spec.whatwg.org/#concept-node-replace
240 static inline ExceptionOr<void> checkPreReplacementValidity(ContainerNode& newParent, Node& newChild, Node& oldChild)
241 {
242     return checkAcceptChild(newParent, newChild, &oldChild, Document::AcceptChildOperation::Replace);
243 }
244
245 ExceptionOr<void> ContainerNode::insertBefore(Node& newChild, Node* refChild)
246 {
247     // Check that this node is not "floating".
248     // If it is, it can be deleted as a side effect of sending mutation events.
249     ASSERT(refCount() || parentOrShadowHostNode());
250
251     // Make sure adding the new child is OK.
252     auto validityCheckResult = ensurePreInsertionValidity(newChild, refChild);
253     if (validityCheckResult.hasException())
254         return validityCheckResult.releaseException();
255
256     if (refChild == &newChild)
257         refChild = newChild.nextSibling();
258
259     // insertBefore(node, null) is equivalent to appendChild(node)
260     if (!refChild)
261         return appendChildWithoutPreInsertionValidityCheck(newChild);
262
263     Ref<ContainerNode> protectedThis(*this);
264     Ref<Node> next(*refChild);
265
266     NodeVector targets;
267     auto removeResult = collectChildrenAndRemoveFromOldParent(newChild, targets);
268     if (removeResult.hasException())
269         return removeResult.releaseException();
270     if (targets.isEmpty())
271         return { };
272
273     // We need this extra check because collectChildrenAndRemoveFromOldParent() can fire mutation events.
274     auto checkAcceptResult = checkAcceptChildGuaranteedNodeTypes(*this, newChild);
275     if (checkAcceptResult.hasException())
276         return checkAcceptResult.releaseException();
277
278     InspectorInstrumentation::willInsertDOMNode(document(), *this);
279
280     ChildListMutationScope mutation(*this);
281     for (auto& child : targets) {
282         // Due to arbitrary code running in response to a DOM mutation event it's
283         // possible that "next" is no longer a child of "this".
284         // It's also possible that "child" has been inserted elsewhere.
285         // In either of those cases, we'll just stop.
286         if (next->parentNode() != this)
287             break;
288         if (child->parentNode())
289             break;
290
291         {
292             NoEventDispatchAssertion assertNoEventDispatch;
293
294             treeScope().adoptIfNeeded(child);
295             insertBeforeCommon(next, child);
296         }
297
298         updateTreeAfterInsertion(child);
299     }
300
301     dispatchSubtreeModifiedEvent();
302     return { };
303 }
304
305 void ContainerNode::insertBeforeCommon(Node& nextChild, Node& newChild)
306 {
307     NoEventDispatchAssertion assertNoEventDispatch;
308
309     ASSERT(!newChild.parentNode()); // Use insertBefore if you need to handle reparenting (and want DOM mutation events).
310     ASSERT(!newChild.nextSibling());
311     ASSERT(!newChild.previousSibling());
312     ASSERT(!newChild.isShadowRoot());
313
314     Node* prev = nextChild.previousSibling();
315     ASSERT(m_lastChild != prev);
316     nextChild.setPreviousSibling(&newChild);
317     if (prev) {
318         ASSERT(m_firstChild != &nextChild);
319         ASSERT(prev->nextSibling() == &nextChild);
320         prev->setNextSibling(&newChild);
321     } else {
322         ASSERT(m_firstChild == &nextChild);
323         m_firstChild = &newChild;
324     }
325     newChild.setParentNode(this);
326     newChild.setPreviousSibling(prev);
327     newChild.setNextSibling(&nextChild);
328 }
329
330 void ContainerNode::appendChildCommon(Node& child)
331 {
332     NoEventDispatchAssertion assertNoEventDispatch;
333
334     child.setParentNode(this);
335
336     if (m_lastChild) {
337         child.setPreviousSibling(m_lastChild);
338         m_lastChild->setNextSibling(&child);
339     } else
340         m_firstChild = &child;
341
342     m_lastChild = &child;
343 }
344
345 inline auto ContainerNode::changeForChildInsertion(Node& child, ChildChangeSource source, ReplacedAllChildren replacedAllChildren) -> ChildChange
346 {
347     if (replacedAllChildren == ReplacedAllChildren::Yes)
348         return { AllChildrenReplaced, nullptr, nullptr, source };
349
350     return {
351         child.isElementNode() ? ElementInserted : child.isTextNode() ? TextInserted : NonContentsChildInserted,
352         ElementTraversal::previousSibling(child),
353         ElementTraversal::nextSibling(child),
354         source
355     };
356 }
357
358 void ContainerNode::notifyChildInserted(Node& child, const ChildChange& change)
359 {
360     ChildListMutationScope(*this).childAdded(child);
361
362     NodeVector postInsertionNotificationTargets;
363     notifyChildNodeInserted(*this, child, postInsertionNotificationTargets);
364
365     childrenChanged(change);
366
367     // Some call sites may have deleted child nodes. Calling it earlier results in bugs like webkit.org/b/168069.
368     document().notifyRemovePendingSheetIfNeeded();
369
370     for (auto& target : postInsertionNotificationTargets)
371         target->finishedInsertingSubtree();
372 }
373
374 void ContainerNode::notifyChildRemoved(Node& child, Node* previousSibling, Node* nextSibling, ChildChangeSource source)
375 {
376     NoEventDispatchAssertion assertNoEventDispatch;
377     notifyChildNodeRemoved(*this, child);
378
379     ChildChange change;
380     change.type = is<Element>(child) ? ElementRemoved : is<Text>(child) ? TextRemoved : NonContentsChildRemoved;
381     change.previousSiblingElement = (!previousSibling || is<Element>(*previousSibling)) ? downcast<Element>(previousSibling) : ElementTraversal::previousSibling(*previousSibling);
382     change.nextSiblingElement = (!nextSibling || is<Element>(*nextSibling)) ? downcast<Element>(nextSibling) : ElementTraversal::nextSibling(*nextSibling);
383     change.source = source;
384
385     childrenChanged(change);
386 }
387
388 void ContainerNode::parserInsertBefore(Node& newChild, Node& nextChild)
389 {
390     ASSERT(nextChild.parentNode() == this);
391     ASSERT(!newChild.isDocumentFragment());
392     ASSERT(!hasTagName(HTMLNames::templateTag));
393
394     if (nextChild.previousSibling() == &newChild || &nextChild == &newChild) // nothing to do
395         return;
396
397     if (&document() != &newChild.document())
398         document().adoptNode(newChild);
399
400     insertBeforeCommon(nextChild, newChild);
401
402     newChild.updateAncestorConnectedSubframeCountForInsertion();
403
404     notifyChildInserted(newChild, changeForChildInsertion(newChild, ChildChangeSourceParser));
405 }
406
407 ExceptionOr<void> ContainerNode::replaceChild(Node& newChild, Node& oldChild)
408 {
409     // Check that this node is not "floating".
410     // If it is, it can be deleted as a side effect of sending mutation events.
411     ASSERT(refCount() || parentOrShadowHostNode());
412
413     Ref<ContainerNode> protectedThis(*this);
414
415     // Make sure replacing the old child with the new is ok
416     auto validityResult = checkPreReplacementValidity(*this, newChild, oldChild);
417     if (validityResult.hasException())
418         return validityResult.releaseException();
419
420     // NOT_FOUND_ERR: Raised if oldChild is not a child of this node.
421     if (oldChild.parentNode() != this)
422         return Exception { NOT_FOUND_ERR };
423
424     RefPtr<Node> refChild = oldChild.nextSibling();
425     if (refChild.get() == &newChild)
426         refChild = refChild->nextSibling();
427
428     NodeVector targets;
429     {
430         ChildListMutationScope mutation(*this);
431         auto collectResult = collectChildrenAndRemoveFromOldParent(newChild, targets);
432         if (collectResult.hasException())
433             return collectResult.releaseException();
434     }
435
436     // Do this one more time because collectChildrenAndRemoveFromOldParent() fires a MutationEvent.
437     validityResult = checkPreReplacementValidity(*this, newChild, oldChild);
438     if (validityResult.hasException())
439         return validityResult.releaseException();
440
441     // Remove the node we're replacing.
442     Ref<Node> protectOldChild(oldChild);
443
444     ChildListMutationScope mutation(*this);
445
446     // If oldChild == newChild then oldChild no longer has a parent at this point.
447     if (oldChild.parentNode()) {
448         auto removeResult = removeChild(oldChild);
449         if (removeResult.hasException())
450             return removeResult.releaseException();
451
452         // Does this one more time because removeChild() fires a MutationEvent.
453         validityResult = checkPreReplacementValidity(*this, newChild, oldChild);
454         if (validityResult.hasException())
455             return validityResult.releaseException();
456     }
457
458     InspectorInstrumentation::willInsertDOMNode(document(), *this);
459
460     // Add the new child(ren).
461     for (auto& child : targets) {
462         // Due to arbitrary code running in response to a DOM mutation event it's
463         // possible that "refChild" is no longer a child of "this".
464         // It's also possible that "child" has been inserted elsewhere.
465         // In either of those cases, we'll just stop.
466         if (refChild && refChild->parentNode() != this)
467             break;
468         if (child->parentNode())
469             break;
470
471         {
472             NoEventDispatchAssertion assertNoEventDispatch;
473             treeScope().adoptIfNeeded(child);
474             if (refChild)
475                 insertBeforeCommon(*refChild, child.get());
476             else
477                 appendChildCommon(child);
478         }
479
480         updateTreeAfterInsertion(child.get());
481     }
482
483     dispatchSubtreeModifiedEvent();
484     return { };
485 }
486
487 static void willRemoveChild(ContainerNode& container, Node& child)
488 {
489     ASSERT(child.parentNode());
490
491     ChildListMutationScope(*child.parentNode()).willRemoveChild(child);
492     child.notifyMutationObserversNodeWillDetach();
493     dispatchChildRemovalEvents(child);
494
495     if (child.parentNode() != &container)
496         return;
497
498     if (is<ContainerNode>(child))
499         disconnectSubframesIfNeeded(downcast<ContainerNode>(child), RootAndDescendants);
500 }
501
502 static void willRemoveChildren(ContainerNode& container)
503 {
504     NodeVector children;
505     getChildNodes(container, children);
506
507     ChildListMutationScope mutation(container);
508     for (auto& child : children) {
509         mutation.willRemoveChild(child.get());
510         child->notifyMutationObserversNodeWillDetach();
511
512         // fire removed from document mutation events.
513         dispatchChildRemovalEvents(child.get());
514     }
515
516     disconnectSubframesIfNeeded(container, DescendantsOnly);
517 }
518
519 void ContainerNode::disconnectDescendantFrames()
520 {
521     disconnectSubframesIfNeeded(*this, RootAndDescendants);
522 }
523
524 ExceptionOr<void> ContainerNode::removeChild(Node& oldChild)
525 {
526     // Check that this node is not "floating".
527     // If it is, it can be deleted as a side effect of sending mutation events.
528     ASSERT(refCount() || parentOrShadowHostNode());
529
530     Ref<ContainerNode> protectedThis(*this);
531
532     // NOT_FOUND_ERR: Raised if oldChild is not a child of this node.
533     if (oldChild.parentNode() != this)
534         return Exception { NOT_FOUND_ERR };
535
536     Ref<Node> child(oldChild);
537
538     willRemoveChild(*this, child);
539
540     // Mutation events in willRemoveChild might have moved this child into a different parent.
541     if (child->parentNode() != this)
542         return Exception { NOT_FOUND_ERR };
543
544     {
545         WidgetHierarchyUpdatesSuspensionScope suspendWidgetHierarchyUpdates;
546         NoEventDispatchAssertion assertNoEventDispatch;
547
548         document().nodeWillBeRemoved(child);
549
550         Node* prev = child->previousSibling();
551         Node* next = child->nextSibling();
552         removeBetween(prev, next, child);
553
554         notifyChildRemoved(child, prev, next, ChildChangeSourceAPI);
555     }
556
557     document().notifyRemovePendingSheetIfNeeded();
558     rebuildSVGExtensionsElementsIfNecessary();
559     dispatchSubtreeModifiedEvent();
560
561     return { };
562 }
563
564 void ContainerNode::removeBetween(Node* previousChild, Node* nextChild, Node& oldChild)
565 {
566     InspectorInstrumentation::didRemoveDOMNode(oldChild.document(), oldChild);
567
568     NoEventDispatchAssertion assertNoEventDispatch;
569
570     ASSERT(oldChild.parentNode() == this);
571
572     destroyRenderTreeIfNeeded(oldChild);
573
574     if (nextChild) {
575         nextChild->setPreviousSibling(previousChild);
576         oldChild.setNextSibling(nullptr);
577     } else {
578         ASSERT(m_lastChild == &oldChild);
579         m_lastChild = previousChild;
580     }
581     if (previousChild) {
582         previousChild->setNextSibling(nextChild);
583         oldChild.setPreviousSibling(nullptr);
584     } else {
585         ASSERT(m_firstChild == &oldChild);
586         m_firstChild = nextChild;
587     }
588
589     ASSERT(m_firstChild != &oldChild);
590     ASSERT(m_lastChild != &oldChild);
591     ASSERT(!oldChild.previousSibling());
592     ASSERT(!oldChild.nextSibling());
593     oldChild.setParentNode(nullptr);
594
595     document().adoptIfNeeded(oldChild);
596 }
597
598 void ContainerNode::parserRemoveChild(Node& oldChild)
599 {
600     disconnectSubframesIfNeeded(*this, DescendantsOnly);
601
602     NoEventDispatchAssertion assertNoEventDispatch;
603
604     document().nodeChildrenWillBeRemoved(*this);
605
606     ASSERT(oldChild.parentNode() == this);
607     ASSERT(!oldChild.isDocumentFragment());
608
609     Node* prev = oldChild.previousSibling();
610     Node* next = oldChild.nextSibling();
611
612     ChildListMutationScope(*this).willRemoveChild(oldChild);
613     oldChild.notifyMutationObserversNodeWillDetach();
614
615     removeBetween(prev, next, oldChild);
616
617     notifyChildRemoved(oldChild, prev, next, ChildChangeSourceParser);
618     document().notifyRemovePendingSheetIfNeeded();
619 }
620
621 // https://dom.spec.whatwg.org/#concept-node-replace-all
622 void ContainerNode::replaceAllChildren(std::nullptr_t)
623 {
624     ChildListMutationScope mutation(*this);
625     removeChildren();
626 }
627
628 // https://dom.spec.whatwg.org/#concept-node-replace-all
629 void ContainerNode::replaceAllChildren(Ref<Node>&& node)
630 {
631     // This function assumes the input node is not a DocumentFragment and is parentless to decrease complexity.
632     ASSERT(!is<DocumentFragment>(node));
633     ASSERT(!node->parentNode());
634
635     if (!hasChildNodes()) {
636         // appendChildWithoutPreInsertionValidityCheck() can only throw when node has a parent and we already asserted it doesn't.
637         auto result = appendChildWithoutPreInsertionValidityCheck(node);
638         ASSERT_UNUSED(result, !result.hasException());
639         return;
640     }
641
642     Ref<ContainerNode> protectedThis(*this);
643     ChildListMutationScope mutation(*this);
644
645     // If node is not null, adopt node into parent's node document.
646     treeScope().adoptIfNeeded(node);
647
648     // Remove all parent's children, in tree order.
649     willRemoveChildren(*this);
650
651     {
652         WidgetHierarchyUpdatesSuspensionScope suspendWidgetHierarchyUpdates;
653         {
654             NoEventDispatchAssertion assertNoEventDispatch;
655
656             document().nodeChildrenWillBeRemoved(*this);
657
658             while (RefPtr<Node> child = m_firstChild) {
659                 removeBetween(nullptr, child->nextSibling(), *child);
660                 notifyChildNodeRemoved(*this, *child);
661             }
662
663             // If node is not null, insert node into parent before null.
664             ASSERT(!ensurePreInsertionValidity(node, nullptr).hasException());
665             InspectorInstrumentation::willInsertDOMNode(document(), *this);
666
667             appendChildCommon(node);
668         }
669
670         updateTreeAfterInsertion(node, ReplacedAllChildren::Yes);
671     }
672
673     rebuildSVGExtensionsElementsIfNecessary();
674     dispatchSubtreeModifiedEvent();
675 }
676
677 inline void ContainerNode::rebuildSVGExtensionsElementsIfNecessary()
678 {
679     if (document().svgExtensions() && !is<SVGUseElement>(shadowHost()))
680         document().accessSVGExtensions().rebuildElements();
681 }
682
683 // this differs from other remove functions because it forcibly removes all the children,
684 // regardless of read-only status or event exceptions, e.g.
685 void ContainerNode::removeChildren()
686 {
687     if (!m_firstChild)
688         return;
689
690     // The container node can be removed from event handlers.
691     Ref<ContainerNode> protectedThis(*this);
692
693     // Do any prep work needed before actually starting to detach
694     // and remove... e.g. stop loading frames, fire unload events.
695     willRemoveChildren(*this);
696
697     {
698         WidgetHierarchyUpdatesSuspensionScope suspendWidgetHierarchyUpdates;
699         NoEventDispatchAssertion assertNoEventDispatch;
700
701         document().nodeChildrenWillBeRemoved(*this);
702
703         while (RefPtr<Node> child = m_firstChild) {
704             removeBetween(0, child->nextSibling(), *child);
705             notifyChildNodeRemoved(*this, *child);
706         }
707
708         ChildChange change = { AllChildrenRemoved, nullptr, nullptr, ChildChangeSourceAPI };
709         childrenChanged(change);
710     }
711
712     document().notifyRemovePendingSheetIfNeeded();
713     rebuildSVGExtensionsElementsIfNecessary();
714     dispatchSubtreeModifiedEvent();
715 }
716
717 ExceptionOr<void> ContainerNode::appendChild(Node& newChild)
718 {
719     // Check that this node is not "floating".
720     // If it is, it can be deleted as a side effect of sending mutation events.
721     ASSERT(refCount() || parentOrShadowHostNode());
722
723     // Make sure adding the new child is ok
724     auto validityCheckResult = ensurePreInsertionValidity(newChild, nullptr);
725     if (validityCheckResult.hasException())
726         return validityCheckResult.releaseException();
727
728     return appendChildWithoutPreInsertionValidityCheck(newChild);
729 }
730
731 ExceptionOr<void> ContainerNode::appendChildWithoutPreInsertionValidityCheck(Node& newChild)
732 {
733     Ref<ContainerNode> protectedThis(*this);
734
735     NodeVector targets;
736     auto removeResult = collectChildrenAndRemoveFromOldParent(newChild, targets);
737     if (removeResult.hasException())
738         return removeResult.releaseException();
739
740     if (targets.isEmpty())
741         return { };
742
743     // We need this extra check because collectChildrenAndRemoveFromOldParent() can fire mutation events.
744     auto nodeTypeResult = checkAcceptChildGuaranteedNodeTypes(*this, newChild);
745     if (nodeTypeResult.hasException())
746         return nodeTypeResult.releaseException();
747
748     InspectorInstrumentation::willInsertDOMNode(document(), *this);
749
750     // Now actually add the child(ren)
751     ChildListMutationScope mutation(*this);
752     for (auto& child : targets) {
753         // If the child has a parent again, just stop what we're doing, because
754         // that means someone is doing something with DOM mutation -- can't re-parent
755         // a child that already has a parent.
756         if (child->parentNode())
757             break;
758
759         // Append child to the end of the list
760         {
761             NoEventDispatchAssertion assertNoEventDispatch;
762             treeScope().adoptIfNeeded(child);
763             appendChildCommon(child);
764         }
765
766         updateTreeAfterInsertion(child.get());
767     }
768
769     dispatchSubtreeModifiedEvent();
770     return { };
771 }
772
773 void ContainerNode::parserAppendChild(Node& newChild)
774 {
775     ASSERT(!newChild.parentNode()); // Use appendChild if you need to handle reparenting (and want DOM mutation events).
776     ASSERT(!newChild.isDocumentFragment());
777     ASSERT(!hasTagName(HTMLNames::templateTag));
778
779     if (&document() != &newChild.document())
780         document().adoptNode(newChild);
781
782     {
783         NoEventDispatchAssertion assertNoEventDispatch;
784         appendChildCommon(newChild);
785         treeScope().adoptIfNeeded(newChild);
786     }
787
788     newChild.updateAncestorConnectedSubframeCountForInsertion();
789
790     notifyChildInserted(newChild, changeForChildInsertion(newChild, ChildChangeSourceParser));
791 }
792
793 void ContainerNode::childrenChanged(const ChildChange& change)
794 {
795     document().incDOMTreeVersion();
796     if (change.source == ChildChangeSourceAPI && change.type != TextChanged)
797         document().updateRangesAfterChildrenChanged(*this);
798     invalidateNodeListAndCollectionCachesInAncestors();
799 }
800
801 void ContainerNode::cloneChildNodes(ContainerNode& clone)
802 {
803     Document& targetDocument = clone.document();
804     for (Node* child = firstChild(); child; child = child->nextSibling()) {
805         auto clonedChild = child->cloneNodeInternal(targetDocument, CloningOperation::SelfWithTemplateContent);
806         if (!clone.appendChild(clonedChild).hasException() && is<ContainerNode>(*child))
807             downcast<ContainerNode>(*child).cloneChildNodes(downcast<ContainerNode>(clonedChild.get()));
808     }
809 }
810
811 unsigned ContainerNode::countChildNodes() const
812 {
813     unsigned count = 0;
814     for (Node* child = firstChild(); child; child = child->nextSibling())
815         ++count;
816     return count;
817 }
818
819 Node* ContainerNode::traverseToChildAt(unsigned index) const
820 {
821     Node* child = firstChild();
822     for (; child && index > 0; --index)
823         child = child->nextSibling();
824     return child;
825 }
826
827 static void dispatchChildInsertionEvents(Node& child)
828 {
829     if (child.isInShadowTree())
830         return;
831
832     ASSERT_WITH_SECURITY_IMPLICATION(NoEventDispatchAssertion::isEventDispatchAllowedInSubtree(child));
833
834     RefPtr<Node> c = &child;
835     Ref<Document> document(child.document());
836
837     if (c->parentNode() && document->hasListenerType(Document::DOMNODEINSERTED_LISTENER))
838         c->dispatchScopedEvent(MutationEvent::create(eventNames().DOMNodeInsertedEvent, true, c->parentNode()));
839
840     // dispatch the DOMNodeInsertedIntoDocument event to all descendants
841     if (c->isConnected() && document->hasListenerType(Document::DOMNODEINSERTEDINTODOCUMENT_LISTENER)) {
842         for (; c; c = NodeTraversal::next(*c, &child))
843             c->dispatchScopedEvent(MutationEvent::create(eventNames().DOMNodeInsertedIntoDocumentEvent, false));
844     }
845 }
846
847 static void dispatchChildRemovalEvents(Node& child)
848 {
849     if (child.isInShadowTree()) {
850         InspectorInstrumentation::willRemoveDOMNode(child.document(), child);
851         return;
852     }
853
854     ASSERT_WITH_SECURITY_IMPLICATION(NoEventDispatchAssertion::isEventDispatchAllowedInSubtree(child));
855
856     willCreatePossiblyOrphanedTreeByRemoval(&child);
857     InspectorInstrumentation::willRemoveDOMNode(child.document(), child);
858
859     RefPtr<Node> c = &child;
860     Ref<Document> document(child.document());
861
862     // dispatch pre-removal mutation events
863     if (c->parentNode() && document->hasListenerType(Document::DOMNODEREMOVED_LISTENER))
864         c->dispatchScopedEvent(MutationEvent::create(eventNames().DOMNodeRemovedEvent, true, c->parentNode()));
865
866     // dispatch the DOMNodeRemovedFromDocument event to all descendants
867     if (c->isConnected() && document->hasListenerType(Document::DOMNODEREMOVEDFROMDOCUMENT_LISTENER)) {
868         for (; c; c = NodeTraversal::next(*c, &child))
869             c->dispatchScopedEvent(MutationEvent::create(eventNames().DOMNodeRemovedFromDocumentEvent, false));
870     }
871 }
872
873 void ContainerNode::updateTreeAfterInsertion(Node& child, ReplacedAllChildren replacedAllChildren)
874 {
875     ASSERT(child.refCount());
876
877     notifyChildInserted(child, changeForChildInsertion(child, ChildChangeSourceAPI, replacedAllChildren));
878
879     dispatchChildInsertionEvents(child);
880 }
881
882 ExceptionOr<Element*> ContainerNode::querySelector(const String& selectors)
883 {
884     auto query = document().selectorQueryForString(selectors);
885     if (query.hasException())
886         return query.releaseException();
887     return query.releaseReturnValue().queryFirst(*this);
888 }
889
890 ExceptionOr<Ref<NodeList>> ContainerNode::querySelectorAll(const String& selectors)
891 {
892     auto query = document().selectorQueryForString(selectors);
893     if (query.hasException())
894         return query.releaseException();
895     return query.releaseReturnValue().queryAll(*this);
896 }
897
898 Ref<HTMLCollection> ContainerNode::getElementsByTagName(const AtomicString& qualifiedName)
899 {
900     ASSERT(!qualifiedName.isNull());
901
902     if (qualifiedName == starAtom)
903         return ensureRareData().ensureNodeLists().addCachedCollection<AllDescendantsCollection>(*this, AllDescendants);
904
905     if (document().isHTMLDocument())
906         return ensureRareData().ensureNodeLists().addCachedCollection<HTMLTagCollection>(*this, ByHTMLTag, qualifiedName);
907     return ensureRareData().ensureNodeLists().addCachedCollection<TagCollection>(*this, ByTag, qualifiedName);
908 }
909
910 Ref<HTMLCollection> ContainerNode::getElementsByTagNameNS(const AtomicString& namespaceURI, const AtomicString& localName)
911 {
912     ASSERT(!localName.isNull());
913     return ensureRareData().ensureNodeLists().addCachedTagCollectionNS(*this, namespaceURI.isEmpty() ? nullAtom : namespaceURI, localName);
914 }
915
916 Ref<NodeList> ContainerNode::getElementsByName(const String& elementName)
917 {
918     return ensureRareData().ensureNodeLists().addCacheWithAtomicName<NameNodeList>(*this, elementName);
919 }
920
921 Ref<HTMLCollection> ContainerNode::getElementsByClassName(const AtomicString& classNames)
922 {
923     return ensureRareData().ensureNodeLists().addCachedCollection<ClassCollection>(*this, ByClass, classNames);
924 }
925
926 Ref<RadioNodeList> ContainerNode::radioNodeList(const AtomicString& name)
927 {
928     ASSERT(hasTagName(HTMLNames::formTag) || hasTagName(HTMLNames::fieldsetTag));
929     return ensureRareData().ensureNodeLists().addCacheWithAtomicName<RadioNodeList>(*this, name);
930 }
931
932 Ref<HTMLCollection> ContainerNode::children()
933 {
934     return ensureRareData().ensureNodeLists().addCachedCollection<GenericCachedHTMLCollection<CollectionTypeTraits<NodeChildren>::traversalType>>(*this, NodeChildren);
935 }
936
937 Element* ContainerNode::firstElementChild() const
938 {
939     return ElementTraversal::firstChild(*this);
940 }
941
942 Element* ContainerNode::lastElementChild() const
943 {
944     return ElementTraversal::lastChild(*this);
945 }
946
947 unsigned ContainerNode::childElementCount() const
948 {
949     auto children = childrenOfType<Element>(*this);
950     return std::distance(children.begin(), children.end());
951 }
952
953 ExceptionOr<void> ContainerNode::append(Vector<NodeOrString>&& vector)
954 {
955     auto result = convertNodesOrStringsIntoNode(WTFMove(vector));
956     if (result.hasException())
957         return result.releaseException();
958
959     auto node = result.releaseReturnValue();
960     if (!node)
961         return { };
962
963     return appendChild(*node);
964 }
965
966 ExceptionOr<void> ContainerNode::prepend(Vector<NodeOrString>&& vector)
967 {
968     auto result = convertNodesOrStringsIntoNode(WTFMove(vector));
969     if (result.hasException())
970         return result.releaseException();
971
972     auto node = result.releaseReturnValue();
973     if (!node)
974         return { };
975
976     return insertBefore(*node, firstChild());
977 }
978
979 HTMLCollection* ContainerNode::cachedHTMLCollection(CollectionType type)
980 {
981     return hasRareData() && rareData()->nodeLists() ? rareData()->nodeLists()->cachedCollection<HTMLCollection>(type) : nullptr;
982 }
983
984 } // namespace WebCore