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 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 "ChildListMutationScope.h"
28#include "Chrome.h"
29#include "ChromeClient.h"
30#include "ClassNodeList.h"
31#include "ContainerNodeAlgorithms.h"
32#include "Editor.h"
33#include "FloatRect.h"
34#include "FrameView.h"
35#include "InlineTextBox.h"
36#include "InsertionPoint.h"
37#include "JSLazyEventListener.h"
38#include "JSNode.h"
39#include "LabelsNodeList.h"
40#include "MutationEvent.h"
41#include "NameNodeList.h"
42#include "NodeRareData.h"
43#include "NodeRenderStyle.h"
44#include "RadioNodeList.h"
45#include "RenderBox.h"
46#include "RenderTheme.h"
47#include "RenderWidget.h"
48#include "ResourceLoadScheduler.h"
49#include "RootInlineBox.h"
50#include "SVGDocumentExtensions.h"
51#include "SVGElement.h"
52#include "SVGNames.h"
53#include "SelectorQuery.h"
54#include "TemplateContentDocumentFragment.h"
55#include <wtf/CurrentTime.h>
56
57#if ENABLE(DELETION_UI)
58#include "DeleteButtonController.h"
59#endif
60
61namespace WebCore {
62
63static void dispatchChildInsertionEvents(Node&);
64static void dispatchChildRemovalEvents(Node&);
65
66ChildNodesLazySnapshot* ChildNodesLazySnapshot::latestSnapshot = 0;
67
68#ifndef NDEBUG
69unsigned NoEventDispatchAssertion::s_count = 0;
70#endif
71
72static void collectChildrenAndRemoveFromOldParent(Node& node, NodeVector& nodes, ExceptionCode& ec)
73{
74    if (!node.isDocumentFragment()) {
75        nodes.append(node);
76        if (ContainerNode* oldParent = node.parentNode())
77            oldParent->removeChild(&node, ec);
78        return;
79    }
80
81    getChildNodes(node, nodes);
82    toContainerNode(node).removeChildren();
83}
84
85// FIXME: This function must get a new name.
86// It removes all children, not just a category called "detached children".
87// So this name is terribly confusing.
88void ContainerNode::removeDetachedChildren()
89{
90    if (connectedSubframeCount()) {
91        for (Node* child = firstChild(); child; child = child->nextSibling())
92            child->updateAncestorConnectedSubframeCountForRemoval();
93    }
94    // FIXME: We should be able to ASSERT(!attached()) here: https://bugs.webkit.org/show_bug.cgi?id=107801
95    removeDetachedChildrenInContainer<Node, ContainerNode>(*this);
96}
97
98static inline void destroyRenderTreeIfNeeded(Node& child)
99{
100    // FIXME: Get rid of the named flow test.
101    if (!child.renderer() && !child.isNamedFlowContentNode())
102        return;
103    if (child.isElementNode())
104        Style::detachRenderTree(toElement(child));
105    else if (child.isTextNode())
106        Style::detachTextRenderer(toText(child));
107}
108
109void ContainerNode::takeAllChildrenFrom(ContainerNode* oldParent)
110{
111    ASSERT(oldParent);
112
113    NodeVector children;
114    getChildNodes(*oldParent, children);
115
116    if (oldParent->document().hasMutationObserversOfType(MutationObserver::ChildList)) {
117        ChildListMutationScope mutation(*oldParent);
118        for (unsigned i = 0; i < children.size(); ++i)
119            mutation.willRemoveChild(children[i].get());
120    }
121
122    // FIXME: We need to do notifyMutationObserversNodeWillDetach() for each child,
123    // probably inside removeDetachedChildrenInContainer.
124
125    oldParent->removeDetachedChildren();
126
127    for (unsigned i = 0; i < children.size(); ++i) {
128        Node& child = children[i].get();
129
130        destroyRenderTreeIfNeeded(child);
131
132        // FIXME: We need a no mutation event version of adoptNode.
133        RefPtr<Node> adoptedChild = document().adoptNode(&children[i].get(), ASSERT_NO_EXCEPTION);
134        parserAppendChild(adoptedChild.get());
135        // FIXME: Together with adoptNode above, the tree scope might get updated recursively twice
136        // (if the document changed or oldParent was in a shadow tree, AND *this is in a shadow tree).
137        // Can we do better?
138        treeScope().adoptIfNeeded(adoptedChild.get());
139    }
140}
141
142ContainerNode::~ContainerNode()
143{
144    if (!isDocumentNode())
145        willBeDeletedFrom(document());
146    removeDetachedChildren();
147}
148
149static inline bool isChildTypeAllowed(ContainerNode* newParent, Node* child)
150{
151    if (!child->isDocumentFragment())
152        return newParent->childTypeAllowed(child->nodeType());
153
154    for (Node* node = child->firstChild(); node; node = node->nextSibling()) {
155        if (!newParent->childTypeAllowed(node->nodeType()))
156            return false;
157    }
158    return true;
159}
160
161static inline bool isInTemplateContent(const Node* node)
162{
163#if ENABLE(TEMPLATE_ELEMENT)
164    Document& document = node->document();
165    return &document == document.templateDocument();
166#else
167    UNUSED_PARAM(node);
168    return false;
169#endif
170}
171
172static inline bool containsConsideringHostElements(const Node* newChild, const Node* newParent)
173{
174    return (newParent->isInShadowTree() || isInTemplateContent(newParent))
175        ? newChild->containsIncludingHostElements(newParent)
176        : newChild->contains(newParent);
177}
178
179static inline ExceptionCode checkAcceptChild(ContainerNode* newParent, Node* newChild, Node* oldChild)
180{
181    // Not mentioned in spec: throw NOT_FOUND_ERR if newChild is null
182    if (!newChild)
183        return NOT_FOUND_ERR;
184
185    // Use common case fast path if possible.
186    if ((newChild->isElementNode() || newChild->isTextNode()) && newParent->isElementNode()) {
187        ASSERT(!newParent->isReadOnlyNode());
188        ASSERT(!newParent->isDocumentTypeNode());
189        ASSERT(isChildTypeAllowed(newParent, newChild));
190        if (containsConsideringHostElements(newChild, newParent))
191            return HIERARCHY_REQUEST_ERR;
192        return 0;
193    }
194
195    // This should never happen, but also protect release builds from tree corruption.
196    ASSERT(!newChild->isPseudoElement());
197    if (newChild->isPseudoElement())
198        return HIERARCHY_REQUEST_ERR;
199
200    if (newParent->isReadOnlyNode())
201        return NO_MODIFICATION_ALLOWED_ERR;
202    if (containsConsideringHostElements(newChild, newParent))
203        return HIERARCHY_REQUEST_ERR;
204
205    if (oldChild && newParent->isDocumentNode()) {
206        if (!toDocument(newParent)->canReplaceChild(newChild, oldChild))
207            return HIERARCHY_REQUEST_ERR;
208    } else if (!isChildTypeAllowed(newParent, newChild))
209        return HIERARCHY_REQUEST_ERR;
210
211    return 0;
212}
213
214static inline bool checkAcceptChildGuaranteedNodeTypes(ContainerNode* newParent, Node* newChild, ExceptionCode& ec)
215{
216    ASSERT(!newParent->isReadOnlyNode());
217    ASSERT(!newParent->isDocumentTypeNode());
218    ASSERT(isChildTypeAllowed(newParent, newChild));
219    if (newChild->contains(newParent)) {
220        ec = HIERARCHY_REQUEST_ERR;
221        return false;
222    }
223
224    return true;
225}
226
227static inline bool checkAddChild(ContainerNode* newParent, Node* newChild, ExceptionCode& ec)
228{
229    ec = checkAcceptChild(newParent, newChild, 0);
230    if (ec)
231        return false;
232
233    return true;
234}
235
236static inline bool checkReplaceChild(ContainerNode* newParent, Node* newChild, Node* oldChild, ExceptionCode& ec)
237{
238    ec = checkAcceptChild(newParent, newChild, oldChild);
239    if (ec)
240        return false;
241
242    return true;
243}
244
245bool ContainerNode::insertBefore(PassRefPtr<Node> newChild, Node* refChild, ExceptionCode& ec)
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    Ref<ContainerNode> protect(*this);
252
253    ec = 0;
254
255    // insertBefore(node, 0) is equivalent to appendChild(node)
256    if (!refChild)
257        return appendChild(newChild, ec);
258
259    // Make sure adding the new child is OK.
260    if (!checkAddChild(this, newChild.get(), ec))
261        return false;
262
263    // NOT_FOUND_ERR: Raised if refChild is not a child of this node
264    if (refChild->parentNode() != this) {
265        ec = NOT_FOUND_ERR;
266        return false;
267    }
268
269    if (refChild->previousSibling() == newChild || refChild == newChild) // nothing to do
270        return true;
271
272    Ref<Node> next(*refChild);
273
274    NodeVector targets;
275    collectChildrenAndRemoveFromOldParent(*newChild.get(), targets, ec);
276    if (ec)
277        return false;
278    if (targets.isEmpty())
279        return true;
280
281    // We need this extra check because collectChildrenAndRemoveFromOldParent() can fire mutation events.
282    if (!checkAcceptChildGuaranteedNodeTypes(this, newChild.get(), ec))
283        return false;
284
285    InspectorInstrumentation::willInsertDOMNode(&document(), this);
286
287    ChildListMutationScope mutation(*this);
288    for (auto it = targets.begin(), end = targets.end(); it != end; ++it) {
289        Node& child = it->get();
290
291        // Due to arbitrary code running in response to a DOM mutation event it's
292        // possible that "next" is no longer a child of "this".
293        // It's also possible that "child" has been inserted elsewhere.
294        // In either of those cases, we'll just stop.
295        if (next->parentNode() != this)
296            break;
297        if (child.parentNode())
298            break;
299
300        treeScope().adoptIfNeeded(&child);
301
302        insertBeforeCommon(next.get(), child);
303
304        updateTreeAfterInsertion(child);
305    }
306
307    dispatchSubtreeModifiedEvent();
308    return true;
309}
310
311void ContainerNode::insertBeforeCommon(Node& nextChild, Node& newChild)
312{
313    NoEventDispatchAssertion assertNoEventDispatch;
314
315    ASSERT(!newChild.parentNode()); // Use insertBefore if you need to handle reparenting (and want DOM mutation events).
316    ASSERT(!newChild.nextSibling());
317    ASSERT(!newChild.previousSibling());
318    ASSERT(!newChild.isShadowRoot());
319
320    Node* prev = nextChild.previousSibling();
321    ASSERT(m_lastChild != prev);
322    nextChild.setPreviousSibling(&newChild);
323    if (prev) {
324        ASSERT(m_firstChild != &nextChild);
325        ASSERT(prev->nextSibling() == &nextChild);
326        prev->setNextSibling(&newChild);
327    } else {
328        ASSERT(m_firstChild == &nextChild);
329        m_firstChild = &newChild;
330    }
331    newChild.setParentNode(this);
332    newChild.setPreviousSibling(prev);
333    newChild.setNextSibling(&nextChild);
334}
335
336void ContainerNode::notifyChildInserted(Node& child, ChildChangeSource source)
337{
338    ChildChange change;
339    change.type = child.isElementNode() ? ElementInserted : child.isTextNode() ? TextInserted : NonContentsChildChanged;
340    change.previousSiblingElement = ElementTraversal::previousSibling(&child);
341    change.nextSiblingElement = ElementTraversal::nextSibling(&child);
342    change.source = source;
343
344    childrenChanged(change);
345}
346
347void ContainerNode::notifyChildRemoved(Node& child, Node* previousSibling, Node* nextSibling, ChildChangeSource source)
348{
349    ChildChange change;
350    change.type = child.isElementNode() ? ElementRemoved : child.isTextNode() ? TextRemoved : NonContentsChildChanged;
351    change.previousSiblingElement = (!previousSibling || previousSibling->isElementNode()) ? toElement(previousSibling) : ElementTraversal::previousSibling(previousSibling);
352    change.nextSiblingElement = (!nextSibling || nextSibling->isElementNode()) ? toElement(nextSibling) : ElementTraversal::nextSibling(nextSibling);
353    change.source = source;
354
355    childrenChanged(change);
356}
357
358void ContainerNode::parserInsertBefore(PassRefPtr<Node> newChild, Node* nextChild)
359{
360    ASSERT(newChild);
361    ASSERT(nextChild);
362    ASSERT(nextChild->parentNode() == this);
363    ASSERT(!newChild->isDocumentFragment());
364#if ENABLE(TEMPLATE_ELEMENT)
365    ASSERT(!hasTagName(HTMLNames::templateTag));
366#endif
367
368    if (nextChild->previousSibling() == newChild || nextChild == newChild) // nothing to do
369        return;
370
371    if (&document() != &newChild->document())
372        document().adoptNode(newChild.get(), ASSERT_NO_EXCEPTION);
373
374    insertBeforeCommon(*nextChild, *newChild.get());
375
376    newChild->updateAncestorConnectedSubframeCountForInsertion();
377
378    ChildListMutationScope(*this).childAdded(*newChild);
379
380    notifyChildInserted(*newChild, ChildChangeSourceParser);
381
382    ChildNodeInsertionNotifier(*this).notify(*newChild);
383
384    newChild->setNeedsStyleRecalc(ReconstructRenderTree);
385}
386
387bool ContainerNode::replaceChild(PassRefPtr<Node> newChild, Node* oldChild, ExceptionCode& ec)
388{
389    // Check that this node is not "floating".
390    // If it is, it can be deleted as a side effect of sending mutation events.
391    ASSERT(refCount() || parentOrShadowHostNode());
392
393    Ref<ContainerNode> protect(*this);
394
395    ec = 0;
396
397    if (oldChild == newChild) // nothing to do
398        return true;
399
400    if (!oldChild) {
401        ec = NOT_FOUND_ERR;
402        return false;
403    }
404
405    // Make sure replacing the old child with the new is ok
406    if (!checkReplaceChild(this, newChild.get(), oldChild, ec))
407        return false;
408
409    // NOT_FOUND_ERR: Raised if oldChild is not a child of this node.
410    if (oldChild->parentNode() != this) {
411        ec = NOT_FOUND_ERR;
412        return false;
413    }
414
415    ChildListMutationScope mutation(*this);
416
417    RefPtr<Node> next = oldChild->nextSibling();
418
419    // Remove the node we're replacing
420    Ref<Node> removedChild(*oldChild);
421    removeChild(oldChild, ec);
422    if (ec)
423        return false;
424
425    if (next && (next->previousSibling() == newChild || next == newChild)) // nothing to do
426        return true;
427
428    // Does this one more time because removeChild() fires a MutationEvent.
429    if (!checkReplaceChild(this, newChild.get(), oldChild, ec))
430        return false;
431
432    NodeVector targets;
433    collectChildrenAndRemoveFromOldParent(*newChild.get(), targets, ec);
434    if (ec)
435        return false;
436
437    // Does this yet another check because collectChildrenAndRemoveFromOldParent() fires a MutationEvent.
438    if (!checkReplaceChild(this, newChild.get(), oldChild, ec))
439        return false;
440
441    InspectorInstrumentation::willInsertDOMNode(&document(), this);
442
443    // Add the new child(ren)
444    for (auto it = targets.begin(), end = targets.end(); it != end; ++it) {
445        Node& child = it->get();
446
447        // Due to arbitrary code running in response to a DOM mutation event it's
448        // possible that "next" is no longer a child of "this".
449        // It's also possible that "child" has been inserted elsewhere.
450        // In either of those cases, we'll just stop.
451        if (next && next->parentNode() != this)
452            break;
453        if (child.parentNode())
454            break;
455
456        treeScope().adoptIfNeeded(&child);
457
458        // Add child before "next".
459        {
460            NoEventDispatchAssertion assertNoEventDispatch;
461            if (next)
462                insertBeforeCommon(*next, child);
463            else
464                appendChildToContainer(&child, *this);
465        }
466
467        updateTreeAfterInsertion(child);
468    }
469
470    dispatchSubtreeModifiedEvent();
471    return true;
472}
473
474void ContainerNode::willRemoveChild(Node& child)
475{
476    ASSERT(child.parentNode());
477
478    ChildListMutationScope(*child.parentNode()).willRemoveChild(child);
479    child.notifyMutationObserversNodeWillDetach();
480    dispatchChildRemovalEvents(child);
481
482    if (child.parentNode() != this)
483        return;
484
485    child.document().nodeWillBeRemoved(&child); // e.g. mutation event listener can create a new range.
486    if (child.isContainerNode())
487        disconnectSubframesIfNeeded(toContainerNode(child), RootAndDescendants);
488}
489
490static void willRemoveChildren(ContainerNode& container)
491{
492    NodeVector children;
493    getChildNodes(container, children);
494
495    ChildListMutationScope mutation(container);
496    for (auto it = children.begin(); it != children.end(); ++it) {
497        Node& child = it->get();
498        mutation.willRemoveChild(child);
499        child.notifyMutationObserversNodeWillDetach();
500
501        // fire removed from document mutation events.
502        dispatchChildRemovalEvents(child);
503    }
504
505    container.document().nodeChildrenWillBeRemoved(container);
506
507    disconnectSubframesIfNeeded(container, DescendantsOnly);
508}
509
510void ContainerNode::disconnectDescendantFrames()
511{
512    disconnectSubframesIfNeeded(*this, RootAndDescendants);
513}
514
515bool ContainerNode::removeChild(Node* oldChild, ExceptionCode& ec)
516{
517    // Check that this node is not "floating".
518    // If it is, it can be deleted as a side effect of sending mutation events.
519    ASSERT(refCount() || parentOrShadowHostNode());
520
521    Ref<ContainerNode> protect(*this);
522
523    ec = 0;
524
525    // NO_MODIFICATION_ALLOWED_ERR: Raised if this node is readonly.
526    if (isReadOnlyNode()) {
527        ec = NO_MODIFICATION_ALLOWED_ERR;
528        return false;
529    }
530
531    // NOT_FOUND_ERR: Raised if oldChild is not a child of this node.
532    if (!oldChild || oldChild->parentNode() != this) {
533        ec = NOT_FOUND_ERR;
534        return false;
535    }
536
537    Ref<Node> child(*oldChild);
538
539    document().removeFocusedNodeOfSubtree(&child.get());
540
541#if ENABLE(FULLSCREEN_API)
542    document().removeFullScreenElementOfSubtree(&child.get());
543#endif
544
545    // Events fired when blurring currently focused node might have moved this
546    // child into a different parent.
547    if (child->parentNode() != this) {
548        ec = NOT_FOUND_ERR;
549        return false;
550    }
551
552    willRemoveChild(child.get());
553
554    // Mutation events might have moved this child into a different parent.
555    if (child->parentNode() != this) {
556        ec = NOT_FOUND_ERR;
557        return false;
558    }
559
560    {
561        WidgetHierarchyUpdatesSuspensionScope suspendWidgetHierarchyUpdates;
562
563        Node* prev = child->previousSibling();
564        Node* next = child->nextSibling();
565        removeBetween(prev, next, child.get());
566
567        notifyChildRemoved(child.get(), prev, next, ChildChangeSourceAPI);
568
569        ChildNodeRemovalNotifier(*this).notify(child.get());
570    }
571
572
573    if (document().svgExtensions()) {
574        Element* shadowHost = this->shadowHost();
575        if (!shadowHost || !shadowHost->hasTagName(SVGNames::useTag))
576            document().accessSVGExtensions()->rebuildElements();
577    }
578
579    dispatchSubtreeModifiedEvent();
580
581    return true;
582}
583
584void ContainerNode::removeBetween(Node* previousChild, Node* nextChild, Node& oldChild)
585{
586    InspectorInstrumentation::didRemoveDOMNode(&oldChild.document(), &oldChild);
587
588    NoEventDispatchAssertion assertNoEventDispatch;
589
590    ASSERT(oldChild.parentNode() == this);
591
592    destroyRenderTreeIfNeeded(oldChild);
593
594    if (nextChild)
595        nextChild->setPreviousSibling(previousChild);
596    if (previousChild)
597        previousChild->setNextSibling(nextChild);
598    if (m_firstChild == &oldChild)
599        m_firstChild = nextChild;
600    if (m_lastChild == &oldChild)
601        m_lastChild = previousChild;
602
603    oldChild.setPreviousSibling(0);
604    oldChild.setNextSibling(0);
605    oldChild.setParentNode(0);
606
607    document().adoptIfNeeded(&oldChild);
608}
609
610void ContainerNode::parserRemoveChild(Node& oldChild)
611{
612    ASSERT(oldChild.parentNode() == this);
613    ASSERT(!oldChild.isDocumentFragment());
614
615    Node* prev = oldChild.previousSibling();
616    Node* next = oldChild.nextSibling();
617
618    oldChild.updateAncestorConnectedSubframeCountForRemoval();
619
620    ChildListMutationScope(*this).willRemoveChild(oldChild);
621    oldChild.notifyMutationObserversNodeWillDetach();
622
623    removeBetween(prev, next, oldChild);
624
625    notifyChildRemoved(oldChild, prev, next, ChildChangeSourceParser);
626
627    ChildNodeRemovalNotifier(*this).notify(oldChild);
628}
629
630// this differs from other remove functions because it forcibly removes all the children,
631// regardless of read-only status or event exceptions, e.g.
632void ContainerNode::removeChildren()
633{
634    if (!m_firstChild)
635        return;
636
637    // The container node can be removed from event handlers.
638    Ref<ContainerNode> protect(*this);
639
640    // exclude this node when looking for removed focusedNode since only children will be removed
641    document().removeFocusedNodeOfSubtree(this, true);
642
643#if ENABLE(FULLSCREEN_API)
644    document().removeFullScreenElementOfSubtree(this, true);
645#endif
646
647    // Do any prep work needed before actually starting to detach
648    // and remove... e.g. stop loading frames, fire unload events.
649    willRemoveChildren(*this);
650
651    NodeVector removedChildren;
652    {
653        WidgetHierarchyUpdatesSuspensionScope suspendWidgetHierarchyUpdates;
654        {
655            NoEventDispatchAssertion assertNoEventDispatch;
656            removedChildren.reserveInitialCapacity(childNodeCount());
657            while (RefPtr<Node> n = m_firstChild) {
658                removedChildren.append(*m_firstChild);
659                removeBetween(0, m_firstChild->nextSibling(), *m_firstChild);
660            }
661        }
662
663        ChildChange change = { AllChildrenRemoved, nullptr, nullptr, ChildChangeSourceAPI };
664        childrenChanged(change);
665
666        for (size_t i = 0; i < removedChildren.size(); ++i)
667            ChildNodeRemovalNotifier(*this).notify(removedChildren[i].get());
668    }
669
670    if (document().svgExtensions()) {
671        Element* shadowHost = this->shadowHost();
672        if (!shadowHost || !shadowHost->hasTagName(SVGNames::useTag))
673            document().accessSVGExtensions()->rebuildElements();
674    }
675
676    dispatchSubtreeModifiedEvent();
677}
678
679bool ContainerNode::appendChild(PassRefPtr<Node> newChild, ExceptionCode& ec)
680{
681    Ref<ContainerNode> protect(*this);
682
683    // Check that this node is not "floating".
684    // If it is, it can be deleted as a side effect of sending mutation events.
685    ASSERT(refCount() || parentOrShadowHostNode());
686
687    ec = 0;
688
689    // Make sure adding the new child is ok
690    if (!checkAddChild(this, newChild.get(), ec))
691        return false;
692
693    if (newChild == m_lastChild) // nothing to do
694        return newChild;
695
696    NodeVector targets;
697    collectChildrenAndRemoveFromOldParent(*newChild.get(), targets, ec);
698    if (ec)
699        return false;
700
701    if (targets.isEmpty())
702        return true;
703
704    // We need this extra check because collectChildrenAndRemoveFromOldParent() can fire mutation events.
705    if (!checkAcceptChildGuaranteedNodeTypes(this, newChild.get(), ec))
706        return false;
707
708    InspectorInstrumentation::willInsertDOMNode(&document(), this);
709
710    // Now actually add the child(ren)
711    ChildListMutationScope mutation(*this);
712    for (auto it = targets.begin(), end = targets.end(); it != end; ++it) {
713        Node& child = it->get();
714
715        // If the child has a parent again, just stop what we're doing, because
716        // that means someone is doing something with DOM mutation -- can't re-parent
717        // a child that already has a parent.
718        if (child.parentNode())
719            break;
720
721        treeScope().adoptIfNeeded(&child);
722
723        // Append child to the end of the list
724        {
725            NoEventDispatchAssertion assertNoEventDispatch;
726            appendChildToContainer(&child, *this);
727        }
728
729        updateTreeAfterInsertion(child);
730    }
731
732    dispatchSubtreeModifiedEvent();
733    return true;
734}
735
736void ContainerNode::parserAppendChild(PassRefPtr<Node> newChild)
737{
738    ASSERT(newChild);
739    ASSERT(!newChild->parentNode()); // Use appendChild if you need to handle reparenting (and want DOM mutation events).
740    ASSERT(!newChild->isDocumentFragment());
741#if ENABLE(TEMPLATE_ELEMENT)
742    ASSERT(!hasTagName(HTMLNames::templateTag));
743#endif
744
745    if (&document() != &newChild->document())
746        document().adoptNode(newChild.get(), ASSERT_NO_EXCEPTION);
747
748    {
749        NoEventDispatchAssertion assertNoEventDispatch;
750        // FIXME: This method should take a PassRefPtr.
751        appendChildToContainer(newChild.get(), *this);
752        treeScope().adoptIfNeeded(newChild.get());
753    }
754
755    newChild->updateAncestorConnectedSubframeCountForInsertion();
756
757    ChildListMutationScope(*this).childAdded(*newChild);
758
759    notifyChildInserted(*newChild, ChildChangeSourceParser);
760
761    ChildNodeInsertionNotifier(*this).notify(*newChild);
762
763    newChild->setNeedsStyleRecalc(ReconstructRenderTree);
764}
765
766void ContainerNode::childrenChanged(const ChildChange& change)
767{
768    document().incDOMTreeVersion();
769    if (change.source == ChildChangeSourceAPI && change.type != TextChanged)
770        document().updateRangesAfterChildrenChanged(*this);
771    invalidateNodeListAndCollectionCachesInAncestors();
772}
773
774inline static void cloneChildNodesAvoidingDeleteButton(ContainerNode* parent, ContainerNode* clonedParent, HTMLElement* deleteButtonContainerElement)
775{
776    ExceptionCode ec = 0;
777    for (Node* child = parent->firstChild(); child && !ec; child = child->nextSibling()) {
778
779#if ENABLE(DELETION_UI)
780        if (child == deleteButtonContainerElement)
781            continue;
782#else
783        UNUSED_PARAM(deleteButtonContainerElement);
784#endif
785
786        RefPtr<Node> clonedChild = child->cloneNode(false);
787        clonedParent->appendChild(clonedChild, ec);
788
789        if (!ec && child->isContainerNode())
790            cloneChildNodesAvoidingDeleteButton(toContainerNode(child), toContainerNode(clonedChild.get()), deleteButtonContainerElement);
791    }
792}
793
794void ContainerNode::cloneChildNodes(ContainerNode *clone)
795{
796#if ENABLE(DELETION_UI)
797    HTMLElement* deleteButtonContainerElement = 0;
798    if (Frame* frame = document().frame())
799        deleteButtonContainerElement = frame->editor().deleteButtonController().containerElement();
800    cloneChildNodesAvoidingDeleteButton(this, clone, deleteButtonContainerElement);
801#else
802    cloneChildNodesAvoidingDeleteButton(this, clone, 0);
803#endif
804}
805
806bool ContainerNode::getUpperLeftCorner(FloatPoint& point) const
807{
808    if (!renderer())
809        return false;
810    // What is this code really trying to do?
811    RenderObject* o = renderer();
812    RenderObject* p = o;
813
814    if (!o->isInline() || o->isReplaced()) {
815        point = o->localToAbsolute(FloatPoint(), UseTransforms);
816        return true;
817    }
818
819    // find the next text/image child, to get a position
820    while (o) {
821        p = o;
822        if (RenderObject* child = o->firstChildSlow())
823            o = child;
824        else if (o->nextSibling())
825            o = o->nextSibling();
826        else {
827            RenderObject* next = 0;
828            while (!next && o->parent()) {
829                o = o->parent();
830                next = o->nextSibling();
831            }
832            o = next;
833
834            if (!o)
835                break;
836        }
837        ASSERT(o);
838
839        if (!o->isInline() || o->isReplaced()) {
840            point = o->localToAbsolute(FloatPoint(), UseTransforms);
841            return true;
842        }
843
844        if (p->node() && p->node() == this && o->isText() && !toRenderText(o)->firstTextBox()) {
845            // do nothing - skip unrendered whitespace that is a child or next sibling of the anchor
846        } else if (o->isText() || o->isReplaced()) {
847            point = FloatPoint();
848            if (o->isText() && toRenderText(o)->firstTextBox()) {
849                point.move(toRenderText(o)->linesBoundingBox().x(), toRenderText(o)->firstTextBox()->root().lineTop());
850            } else if (o->isBox()) {
851                RenderBox* box = toRenderBox(o);
852                point.moveBy(box->location());
853            }
854            point = o->container()->localToAbsolute(point, UseTransforms);
855            return true;
856        }
857    }
858
859    // If the target doesn't have any children or siblings that could be used to calculate the scroll position, we must be
860    // at the end of the document. Scroll to the bottom. FIXME: who said anything about scrolling?
861    if (!o && document().view()) {
862        point = FloatPoint(0, document().view()->contentsHeight());
863        return true;
864    }
865    return false;
866}
867
868bool ContainerNode::getLowerRightCorner(FloatPoint& point) const
869{
870    if (!renderer())
871        return false;
872
873    RenderObject* o = renderer();
874    if (!o->isInline() || o->isReplaced()) {
875        RenderBox* box = toRenderBox(o);
876        point = o->localToAbsolute(LayoutPoint(box->size()), UseTransforms);
877        return true;
878    }
879
880    // find the last text/image child, to get a position
881    while (o) {
882        if (RenderObject* child = o->lastChildSlow())
883            o = child;
884        else if (o->previousSibling())
885            o = o->previousSibling();
886        else {
887            RenderObject* prev = 0;
888            while (!prev) {
889                o = o->parent();
890                if (!o)
891                    return false;
892                prev = o->previousSibling();
893            }
894            o = prev;
895        }
896        ASSERT(o);
897        if (o->isText() || o->isReplaced()) {
898            point = FloatPoint();
899            if (o->isText()) {
900                RenderText* text = toRenderText(o);
901                IntRect linesBox = text->linesBoundingBox();
902                if (!linesBox.maxX() && !linesBox.maxY())
903                    continue;
904                point.moveBy(linesBox.maxXMaxYCorner());
905            } else {
906                RenderBox* box = toRenderBox(o);
907                point.moveBy(box->frameRect().maxXMaxYCorner());
908            }
909            point = o->container()->localToAbsolute(point, UseTransforms);
910            return true;
911        }
912    }
913    return true;
914}
915
916LayoutRect ContainerNode::boundingBox() const
917{
918    FloatPoint upperLeft, lowerRight;
919    bool foundUpperLeft = getUpperLeftCorner(upperLeft);
920    bool foundLowerRight = getLowerRightCorner(lowerRight);
921
922    // If we've found one corner, but not the other,
923    // then we should just return a point at the corner that we did find.
924    if (foundUpperLeft != foundLowerRight) {
925        if (foundUpperLeft)
926            lowerRight = upperLeft;
927        else
928            upperLeft = lowerRight;
929    }
930
931    return enclosingLayoutRect(FloatRect(upperLeft, lowerRight.expandedTo(upperLeft) - upperLeft));
932}
933
934unsigned ContainerNode::childNodeCount() const
935{
936    unsigned count = 0;
937    Node *n;
938    for (n = firstChild(); n; n = n->nextSibling())
939        count++;
940    return count;
941}
942
943Node *ContainerNode::childNode(unsigned index) const
944{
945    unsigned i;
946    Node *n = firstChild();
947    for (i = 0; n != 0 && i < index; i++)
948        n = n->nextSibling();
949    return n;
950}
951
952static void dispatchChildInsertionEvents(Node& child)
953{
954    if (child.isInShadowTree())
955        return;
956
957    ASSERT(!NoEventDispatchAssertion::isEventDispatchForbidden());
958
959    RefPtr<Node> c = &child;
960    Ref<Document> document(child.document());
961
962    if (c->parentNode() && document->hasListenerType(Document::DOMNODEINSERTED_LISTENER))
963        c->dispatchScopedEvent(MutationEvent::create(eventNames().DOMNodeInsertedEvent, true, c->parentNode()));
964
965    // dispatch the DOMNodeInsertedIntoDocument event to all descendants
966    if (c->inDocument() && document->hasListenerType(Document::DOMNODEINSERTEDINTODOCUMENT_LISTENER)) {
967        for (; c; c = NodeTraversal::next(c.get(), &child))
968            c->dispatchScopedEvent(MutationEvent::create(eventNames().DOMNodeInsertedIntoDocumentEvent, false));
969    }
970}
971
972static void dispatchChildRemovalEvents(Node& child)
973{
974    if (child.isInShadowTree()) {
975        InspectorInstrumentation::willRemoveDOMNode(&child.document(), &child);
976        return;
977    }
978
979    ASSERT(!NoEventDispatchAssertion::isEventDispatchForbidden());
980
981    willCreatePossiblyOrphanedTreeByRemoval(&child);
982    InspectorInstrumentation::willRemoveDOMNode(&child.document(), &child);
983
984    RefPtr<Node> c = &child;
985    Ref<Document> document(child.document());
986
987    // dispatch pre-removal mutation events
988    if (c->parentNode() && document->hasListenerType(Document::DOMNODEREMOVED_LISTENER))
989        c->dispatchScopedEvent(MutationEvent::create(eventNames().DOMNodeRemovedEvent, true, c->parentNode()));
990
991    // dispatch the DOMNodeRemovedFromDocument event to all descendants
992    if (c->inDocument() && document->hasListenerType(Document::DOMNODEREMOVEDFROMDOCUMENT_LISTENER)) {
993        for (; c; c = NodeTraversal::next(c.get(), &child))
994            c->dispatchScopedEvent(MutationEvent::create(eventNames().DOMNodeRemovedFromDocumentEvent, false));
995    }
996}
997
998void ContainerNode::updateTreeAfterInsertion(Node& child)
999{
1000    ASSERT(child.refCount());
1001
1002    ChildListMutationScope(*this).childAdded(child);
1003
1004    notifyChildInserted(child, ChildChangeSourceAPI);
1005
1006    ChildNodeInsertionNotifier(*this).notify(child);
1007
1008    child.setNeedsStyleRecalc(ReconstructRenderTree);
1009
1010    dispatchChildInsertionEvents(child);
1011}
1012
1013void ContainerNode::setAttributeEventListener(const AtomicString& eventType, const QualifiedName& attributeName, const AtomicString& attributeValue)
1014{
1015    setAttributeEventListener(eventType, JSLazyEventListener::createForNode(*this, attributeName, attributeValue));
1016}
1017
1018Element* ContainerNode::querySelector(const String& selectors, ExceptionCode& ec)
1019{
1020    if (SelectorQuery* selectorQuery = document().selectorQueryForString(selectors, ec))
1021        return selectorQuery->queryFirst(*this);
1022    return nullptr;
1023}
1024
1025RefPtr<NodeList> ContainerNode::querySelectorAll(const String& selectors, ExceptionCode& ec)
1026{
1027    if (SelectorQuery* selectorQuery = document().selectorQueryForString(selectors, ec))
1028        return selectorQuery->queryAll(*this);
1029    return nullptr;
1030}
1031
1032PassRefPtr<NodeList> ContainerNode::getElementsByTagName(const AtomicString& localName)
1033{
1034    if (localName.isNull())
1035        return 0;
1036
1037    if (document().isHTMLDocument())
1038        return ensureRareData().ensureNodeLists().addCacheWithAtomicName<HTMLTagNodeList>(*this, localName);
1039    return ensureRareData().ensureNodeLists().addCacheWithAtomicName<TagNodeList>(*this, localName);
1040}
1041
1042PassRefPtr<NodeList> ContainerNode::getElementsByTagNameNS(const AtomicString& namespaceURI, const AtomicString& localName)
1043{
1044    if (localName.isNull())
1045        return 0;
1046
1047    if (namespaceURI == starAtom)
1048        return getElementsByTagName(localName);
1049
1050    return ensureRareData().ensureNodeLists().addCacheWithQualifiedName(*this, namespaceURI.isEmpty() ? nullAtom : namespaceURI, localName);
1051}
1052
1053PassRefPtr<NodeList> ContainerNode::getElementsByName(const String& elementName)
1054{
1055    return ensureRareData().ensureNodeLists().addCacheWithAtomicName<NameNodeList>(*this, elementName);
1056}
1057
1058PassRefPtr<NodeList> ContainerNode::getElementsByClassName(const String& classNames)
1059{
1060    return ensureRareData().ensureNodeLists().addCacheWithName<ClassNodeList>(*this, classNames);
1061}
1062
1063PassRefPtr<RadioNodeList> ContainerNode::radioNodeList(const AtomicString& name)
1064{
1065    ASSERT(hasTagName(HTMLNames::formTag) || hasTagName(HTMLNames::fieldsetTag));
1066    return ensureRareData().ensureNodeLists().addCacheWithAtomicName<RadioNodeList>(*this, name);
1067}
1068
1069} // namespace WebCore
1070