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 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 "core/dom/ContainerNode.h"
25
26#include "bindings/v8/ExceptionState.h"
27#include "core/dom/ChildFrameDisconnector.h"
28#include "core/dom/ChildListMutationScope.h"
29#include "core/dom/ClassCollection.h"
30#include "core/dom/ContainerNodeAlgorithms.h"
31#include "core/dom/ElementTraversal.h"
32#include "core/dom/ExceptionCode.h"
33#include "core/dom/FullscreenElementStack.h"
34#include "core/dom/NameNodeList.h"
35#include "core/dom/NoEventDispatchAssertion.h"
36#include "core/dom/NodeChildRemovalTracker.h"
37#include "core/dom/NodeRareData.h"
38#include "core/dom/NodeRenderStyle.h"
39#include "core/dom/NodeTraversal.h"
40#include "core/dom/ScriptForbiddenScope.h"
41#include "core/dom/SelectorQuery.h"
42#include "core/dom/StaticNodeList.h"
43#include "core/dom/shadow/ElementShadow.h"
44#include "core/dom/shadow/ShadowRoot.h"
45#include "core/events/MutationEvent.h"
46#include "core/html/HTMLCollection.h"
47#include "core/html/HTMLFrameOwnerElement.h"
48#include "core/html/RadioNodeList.h"
49#include "core/inspector/InspectorInstrumentation.h"
50#include "core/rendering/InlineTextBox.h"
51#include "core/rendering/RenderText.h"
52#include "core/rendering/RenderTheme.h"
53#include "core/rendering/RenderView.h"
54
55namespace WebCore {
56
57using namespace HTMLNames;
58
59static void dispatchChildInsertionEvents(Node&);
60static void dispatchChildRemovalEvents(Node&);
61
62#ifndef NDEBUG
63unsigned NoEventDispatchAssertion::s_count = 0;
64#endif
65
66static void collectChildrenAndRemoveFromOldParent(Node& node, NodeVector& nodes, ExceptionState& exceptionState)
67{
68    if (!node.isDocumentFragment()) {
69        nodes.append(&node);
70        if (ContainerNode* oldParent = node.parentNode())
71            oldParent->removeChild(&node, exceptionState);
72        return;
73    }
74    getChildNodes(node, nodes);
75    toContainerNode(node).removeChildren();
76}
77
78#if !ENABLE(OILPAN)
79void ContainerNode::removeDetachedChildren()
80{
81    ASSERT(!connectedSubframeCount());
82    ASSERT(needsAttach());
83    removeDetachedChildrenInContainer<Node, ContainerNode>(*this);
84}
85#endif
86
87void ContainerNode::parserTakeAllChildrenFrom(ContainerNode& oldParent)
88{
89    while (RefPtrWillBeRawPtr<Node> child = oldParent.firstChild()) {
90        oldParent.parserRemoveChild(*child);
91        treeScope().adoptIfNeeded(*child);
92        parserAppendChild(child.get());
93    }
94}
95
96ContainerNode::~ContainerNode()
97{
98    ASSERT(needsAttach());
99#if !ENABLE(OILPAN)
100    willBeDeletedFromDocument();
101    removeDetachedChildren();
102#endif
103}
104
105bool ContainerNode::isChildTypeAllowed(const Node& child) const
106{
107    if (!child.isDocumentFragment())
108        return childTypeAllowed(child.nodeType());
109
110    for (Node* node = toDocumentFragment(child).firstChild(); node; node = node->nextSibling()) {
111        if (!childTypeAllowed(node->nodeType()))
112            return false;
113    }
114    return true;
115}
116
117bool ContainerNode::containsConsideringHostElements(const Node& newChild) const
118{
119    if (isInShadowTree() || document().isTemplateDocument())
120        return newChild.containsIncludingHostElements(*this);
121    return newChild.contains(this);
122}
123
124bool ContainerNode::checkAcceptChild(const Node* newChild, const Node* oldChild, ExceptionState& exceptionState) const
125{
126    // Not mentioned in spec: throw NotFoundError if newChild is null
127    if (!newChild) {
128        exceptionState.throwDOMException(NotFoundError, "The new child element is null.");
129        return false;
130    }
131
132    // Use common case fast path if possible.
133    if ((newChild->isElementNode() || newChild->isTextNode()) && isElementNode()) {
134        ASSERT(isChildTypeAllowed(*newChild));
135        if (containsConsideringHostElements(*newChild)) {
136            exceptionState.throwDOMException(HierarchyRequestError, "The new child element contains the parent.");
137            return false;
138        }
139        return true;
140    }
141
142    // This should never happen, but also protect release builds from tree corruption.
143    ASSERT(!newChild->isPseudoElement());
144    if (newChild->isPseudoElement()) {
145        exceptionState.throwDOMException(HierarchyRequestError, "The new child element is a pseudo-element.");
146        return false;
147    }
148
149    if (containsConsideringHostElements(*newChild)) {
150        exceptionState.throwDOMException(HierarchyRequestError, "The new child element contains the parent.");
151        return false;
152    }
153
154    if (oldChild && isDocumentNode()) {
155        if (!toDocument(this)->canReplaceChild(*newChild, *oldChild)) {
156            // FIXME: Adjust 'Document::canReplaceChild' to return some additional detail (or an error message).
157            exceptionState.throwDOMException(HierarchyRequestError, "Failed to replace child.");
158            return false;
159        }
160    } else if (!isChildTypeAllowed(*newChild)) {
161        exceptionState.throwDOMException(HierarchyRequestError, "Nodes of type '" + newChild->nodeName() + "' may not be inserted inside nodes of type '" + nodeName() + "'.");
162        return false;
163    }
164
165    return true;
166}
167
168bool ContainerNode::checkAcceptChildGuaranteedNodeTypes(const Node& newChild, ExceptionState& exceptionState) const
169{
170    ASSERT(isChildTypeAllowed(newChild));
171    if (newChild.contains(this)) {
172        exceptionState.throwDOMException(HierarchyRequestError, "The new child element contains the parent.");
173        return false;
174    }
175    return true;
176}
177
178void ContainerNode::insertBefore(PassRefPtrWillBeRawPtr<Node> newChild, Node* refChild, ExceptionState& exceptionState)
179{
180#if !ENABLE(OILPAN)
181    // Check that this node is not "floating".
182    // If it is, it can be deleted as a side effect of sending mutation events.
183    ASSERT(refCount() || parentOrShadowHostNode());
184#endif
185
186    RefPtrWillBeRawPtr<Node> protect(this);
187
188    // insertBefore(node, 0) is equivalent to appendChild(node)
189    if (!refChild) {
190        appendChild(newChild, exceptionState);
191        return;
192    }
193
194    // Make sure adding the new child is OK.
195    if (!checkAcceptChild(newChild.get(), 0, exceptionState))
196        return;
197    ASSERT(newChild);
198
199    // NotFoundError: Raised if refChild is not a child of this node
200    if (refChild->parentNode() != this) {
201        exceptionState.throwDOMException(NotFoundError, "The node before which the new node is to be inserted is not a child of this node.");
202        return;
203    }
204
205    if (refChild->previousSibling() == newChild || refChild == newChild) // nothing to do
206        return;
207
208    RefPtrWillBeRawPtr<Node> next = refChild;
209
210    NodeVector targets;
211    collectChildrenAndRemoveFromOldParent(*newChild, targets, exceptionState);
212    if (exceptionState.hadException())
213        return;
214    if (targets.isEmpty())
215        return;
216
217    // We need this extra check because collectChildrenAndRemoveFromOldParent() can fire mutation events.
218    if (!checkAcceptChildGuaranteedNodeTypes(*newChild, exceptionState))
219        return;
220
221    InspectorInstrumentation::willInsertDOMNode(this);
222
223    ChildListMutationScope mutation(*this);
224    for (NodeVector::const_iterator it = targets.begin(); it != targets.end(); ++it) {
225        ASSERT(*it);
226        Node& child = **it;
227
228        // Due to arbitrary code running in response to a DOM mutation event it's
229        // possible that "next" is no longer a child of "this".
230        // It's also possible that "child" has been inserted elsewhere.
231        // In either of those cases, we'll just stop.
232        if (next->parentNode() != this)
233            break;
234        if (child.parentNode())
235            break;
236
237        treeScope().adoptIfNeeded(child);
238
239        insertBeforeCommon(*next, child);
240
241        updateTreeAfterInsertion(child);
242    }
243
244    dispatchSubtreeModifiedEvent();
245}
246
247void ContainerNode::insertBeforeCommon(Node& nextChild, Node& newChild)
248{
249    NoEventDispatchAssertion assertNoEventDispatch;
250    ScriptForbiddenScope forbidScript;
251
252    ASSERT(!newChild.parentNode()); // Use insertBefore if you need to handle reparenting (and want DOM mutation events).
253    ASSERT(!newChild.nextSibling());
254    ASSERT(!newChild.previousSibling());
255    ASSERT(!newChild.isShadowRoot());
256
257    Node* prev = nextChild.previousSibling();
258    ASSERT(m_lastChild != prev);
259    nextChild.setPreviousSibling(&newChild);
260    if (prev) {
261        ASSERT(firstChild() != nextChild);
262        ASSERT(prev->nextSibling() == nextChild);
263        prev->setNextSibling(&newChild);
264    } else {
265        ASSERT(firstChild() == nextChild);
266        m_firstChild = &newChild;
267    }
268    newChild.setParentOrShadowHostNode(this);
269    newChild.setPreviousSibling(prev);
270    newChild.setNextSibling(&nextChild);
271}
272
273void ContainerNode::appendChildCommon(Node& child)
274{
275    child.setParentOrShadowHostNode(this);
276
277    if (m_lastChild) {
278        child.setPreviousSibling(m_lastChild);
279        m_lastChild->setNextSibling(&child);
280    } else {
281        setFirstChild(&child);
282    }
283
284    setLastChild(&child);
285}
286
287void ContainerNode::parserInsertBefore(PassRefPtrWillBeRawPtr<Node> newChild, Node& nextChild)
288{
289    ASSERT(newChild);
290    ASSERT(nextChild.parentNode() == this);
291    ASSERT(!newChild->isDocumentFragment());
292    ASSERT(!isHTMLTemplateElement(this));
293
294    if (nextChild.previousSibling() == newChild || &nextChild == newChild) // nothing to do
295        return;
296
297    RefPtrWillBeRawPtr<Node> protect(this);
298
299    if (document() != newChild->document())
300        document().adoptNode(newChild.get(), ASSERT_NO_EXCEPTION);
301
302    insertBeforeCommon(nextChild, *newChild);
303
304    newChild->updateAncestorConnectedSubframeCountForInsertion();
305
306    ChildListMutationScope(*this).childAdded(*newChild);
307
308    notifyNodeInserted(*newChild, ChildrenChangeSourceParser);
309}
310
311void ContainerNode::replaceChild(PassRefPtrWillBeRawPtr<Node> newChild, Node* oldChild, ExceptionState& exceptionState)
312{
313#if !ENABLE(OILPAN)
314    // Check that this node is not "floating".
315    // If it is, it can be deleted as a side effect of sending mutation events.
316    ASSERT(refCount() || parentOrShadowHostNode());
317#endif
318
319    RefPtrWillBeRawPtr<Node> protect(this);
320
321    if (oldChild == newChild) // nothing to do
322        return;
323
324    if (!oldChild) {
325        exceptionState.throwDOMException(NotFoundError, "The node to be replaced is null.");
326        return;
327    }
328
329    // Make sure replacing the old child with the new is ok
330    if (!checkAcceptChild(newChild.get(), oldChild, exceptionState))
331        return;
332
333    // NotFoundError: Raised if oldChild is not a child of this node.
334    if (oldChild->parentNode() != this) {
335        exceptionState.throwDOMException(NotFoundError, "The node to be replaced is not a child of this node.");
336        return;
337    }
338
339    ChildListMutationScope mutation(*this);
340
341    RefPtrWillBeRawPtr<Node> next = oldChild->nextSibling();
342
343    // Remove the node we're replacing
344    RefPtrWillBeRawPtr<Node> protectRemovedChild = oldChild;
345    ASSERT_UNUSED(protectRemovedChild, protectRemovedChild);
346    removeChild(oldChild, exceptionState);
347    if (exceptionState.hadException())
348        return;
349
350    if (next && (next->previousSibling() == newChild || next == newChild)) // nothing to do
351        return;
352
353    // Does this one more time because removeChild() fires a MutationEvent.
354    if (!checkAcceptChild(newChild.get(), oldChild, exceptionState))
355        return;
356
357    NodeVector targets;
358    collectChildrenAndRemoveFromOldParent(*newChild, targets, exceptionState);
359    if (exceptionState.hadException())
360        return;
361
362    // Does this yet another check because collectChildrenAndRemoveFromOldParent() fires a MutationEvent.
363    if (!checkAcceptChild(newChild.get(), oldChild, exceptionState))
364        return;
365
366    InspectorInstrumentation::willInsertDOMNode(this);
367
368    // Add the new child(ren)
369    for (NodeVector::const_iterator it = targets.begin(); it != targets.end(); ++it) {
370        ASSERT(*it);
371        Node& child = **it;
372
373        // Due to arbitrary code running in response to a DOM mutation event it's
374        // possible that "next" is no longer a child of "this".
375        // It's also possible that "child" has been inserted elsewhere.
376        // In either of those cases, we'll just stop.
377        if (next && next->parentNode() != this)
378            break;
379        if (child.parentNode())
380            break;
381
382        treeScope().adoptIfNeeded(child);
383
384        // Add child before "next".
385        {
386            NoEventDispatchAssertion assertNoEventDispatch;
387            if (next)
388                insertBeforeCommon(*next, child);
389            else
390                appendChildCommon(child);
391        }
392
393        updateTreeAfterInsertion(child);
394    }
395
396    dispatchSubtreeModifiedEvent();
397}
398
399void ContainerNode::willRemoveChild(Node& child)
400{
401    ASSERT(child.parentNode() == this);
402    ChildListMutationScope(*this).willRemoveChild(child);
403    child.notifyMutationObserversNodeWillDetach();
404    dispatchChildRemovalEvents(child);
405    document().nodeWillBeRemoved(child); // e.g. mutation event listener can create a new range.
406    ChildFrameDisconnector(child).disconnect();
407}
408
409void ContainerNode::willRemoveChildren()
410{
411    NodeVector children;
412    getChildNodes(*this, children);
413
414    ChildListMutationScope mutation(*this);
415    for (NodeVector::const_iterator it = children.begin(); it != children.end(); ++it) {
416        ASSERT(*it);
417        Node& child = **it;
418        mutation.willRemoveChild(child);
419        child.notifyMutationObserversNodeWillDetach();
420        dispatchChildRemovalEvents(child);
421    }
422
423    ChildFrameDisconnector(*this).disconnect(ChildFrameDisconnector::DescendantsOnly);
424}
425
426void ContainerNode::disconnectDescendantFrames()
427{
428    ChildFrameDisconnector(*this).disconnect();
429}
430
431void ContainerNode::trace(Visitor* visitor)
432{
433    visitor->trace(m_firstChild);
434    visitor->trace(m_lastChild);
435    Node::trace(visitor);
436}
437
438void ContainerNode::removeChild(Node* oldChild, ExceptionState& exceptionState)
439{
440#if !ENABLE(OILPAN)
441    // Check that this node is not "floating".
442    // If it is, it can be deleted as a side effect of sending mutation events.
443    ASSERT(refCount() || parentOrShadowHostNode());
444#endif
445
446    RefPtrWillBeRawPtr<Node> protect(this);
447
448    // NotFoundError: Raised if oldChild is not a child of this node.
449    // FIXME: We should never really get PseudoElements in here, but editing will sometimes
450    // attempt to remove them still. We should fix that and enable this ASSERT.
451    // ASSERT(!oldChild->isPseudoElement())
452    if (!oldChild || oldChild->parentNode() != this || oldChild->isPseudoElement()) {
453        exceptionState.throwDOMException(NotFoundError, "The node to be removed is not a child of this node.");
454        return;
455    }
456
457    RefPtrWillBeRawPtr<Node> child = oldChild;
458
459    document().removeFocusedElementOfSubtree(child.get());
460
461    if (FullscreenElementStack* fullscreen = FullscreenElementStack::fromIfExists(document()))
462        fullscreen->removeFullScreenElementOfSubtree(child.get());
463
464    // Events fired when blurring currently focused node might have moved this
465    // child into a different parent.
466    if (child->parentNode() != this) {
467        exceptionState.throwDOMException(NotFoundError, "The node to be removed is no longer a child of this node. Perhaps it was moved in a 'blur' event handler?");
468        return;
469    }
470
471    willRemoveChild(*child);
472
473    // Mutation events might have moved this child into a different parent.
474    if (child->parentNode() != this) {
475        exceptionState.throwDOMException(NotFoundError, "The node to be removed is no longer a child of this node. Perhaps it was moved in response to a mutation?");
476        return;
477    }
478
479    {
480        HTMLFrameOwnerElement::UpdateSuspendScope suspendWidgetHierarchyUpdates;
481
482        Node* prev = child->previousSibling();
483        Node* next = child->nextSibling();
484        removeBetween(prev, next, *child);
485        notifyNodeRemoved(*child);
486        childrenChanged(false, prev, next, -1);
487    }
488    dispatchSubtreeModifiedEvent();
489}
490
491void ContainerNode::removeBetween(Node* previousChild, Node* nextChild, Node& oldChild)
492{
493    NoEventDispatchAssertion assertNoEventDispatch;
494
495    ASSERT(oldChild.parentNode() == this);
496
497    if (!oldChild.needsAttach())
498        oldChild.detach();
499
500    if (nextChild)
501        nextChild->setPreviousSibling(previousChild);
502    if (previousChild)
503        previousChild->setNextSibling(nextChild);
504    if (m_firstChild == &oldChild)
505        m_firstChild = nextChild;
506    if (m_lastChild == &oldChild)
507        m_lastChild = previousChild;
508
509    oldChild.setPreviousSibling(0);
510    oldChild.setNextSibling(0);
511    oldChild.setParentOrShadowHostNode(0);
512
513    document().adoptIfNeeded(oldChild);
514}
515
516void ContainerNode::parserRemoveChild(Node& oldChild)
517{
518    ASSERT(oldChild.parentNode() == this);
519    ASSERT(!oldChild.isDocumentFragment());
520
521    Node* prev = oldChild.previousSibling();
522    Node* next = oldChild.nextSibling();
523
524    oldChild.updateAncestorConnectedSubframeCountForRemoval();
525
526    ChildListMutationScope(*this).willRemoveChild(oldChild);
527    oldChild.notifyMutationObserversNodeWillDetach();
528
529    removeBetween(prev, next, oldChild);
530
531    childrenChanged(true, prev, next, -1);
532    notifyNodeRemoved(oldChild);
533}
534
535// this differs from other remove functions because it forcibly removes all the children,
536// regardless of read-only status or event exceptions, e.g.
537void ContainerNode::removeChildren()
538{
539    if (!m_firstChild)
540        return;
541
542    // The container node can be removed from event handlers.
543    RefPtrWillBeRawPtr<ContainerNode> protect(this);
544
545    if (FullscreenElementStack* fullscreen = FullscreenElementStack::fromIfExists(document()))
546        fullscreen->removeFullScreenElementOfSubtree(this, true);
547
548    // Do any prep work needed before actually starting to detach
549    // and remove... e.g. stop loading frames, fire unload events.
550    willRemoveChildren();
551
552    {
553        // Removing focus can cause frames to load, either via events (focusout, blur)
554        // or widget updates (e.g., for <embed>).
555        SubframeLoadingDisabler disabler(*this);
556
557        // Exclude this node when looking for removed focusedElement since only
558        // children will be removed.
559        // This must be later than willRemoveChildren, which might change focus
560        // state of a child.
561        document().removeFocusedElementOfSubtree(this, true);
562
563        // Removing a node from a selection can cause widget updates.
564        document().nodeChildrenWillBeRemoved(*this);
565    }
566
567    // FIXME: Remove this NodeVector. Right now WebPluginContainerImpl::m_element is a
568    // raw ptr which means the code below can drop the last ref to a plugin element and
569    // then the code in UpdateSuspendScope::performDeferredWidgetTreeOperations will
570    // try to destroy the plugin which will be a use-after-free. We should use a RefPtr
571    // in the WebPluginContainerImpl instead.
572    NodeVector removedChildren;
573    {
574        HTMLFrameOwnerElement::UpdateSuspendScope suspendWidgetHierarchyUpdates;
575
576        {
577            NoEventDispatchAssertion assertNoEventDispatch;
578            ScriptForbiddenScope forbidScript;
579
580            removedChildren.reserveInitialCapacity(countChildren());
581
582            while (RefPtrWillBeRawPtr<Node> child = m_firstChild) {
583                removeBetween(0, child->nextSibling(), *child);
584                removedChildren.append(child.get());
585                notifyNodeRemoved(*child);
586            }
587        }
588
589        childrenChanged(false, 0, 0, -static_cast<int>(removedChildren.size()));
590    }
591
592    dispatchSubtreeModifiedEvent();
593}
594
595void ContainerNode::appendChild(PassRefPtrWillBeRawPtr<Node> newChild, ExceptionState& exceptionState)
596{
597    RefPtrWillBeRawPtr<ContainerNode> protect(this);
598
599#if !ENABLE(OILPAN)
600    // Check that this node is not "floating".
601    // If it is, it can be deleted as a side effect of sending mutation events.
602    ASSERT(refCount() || parentOrShadowHostNode());
603#endif
604
605    // Make sure adding the new child is ok
606    if (!checkAcceptChild(newChild.get(), 0, exceptionState))
607        return;
608    ASSERT(newChild);
609
610    if (newChild == m_lastChild) // nothing to do
611        return;
612
613    NodeVector targets;
614    collectChildrenAndRemoveFromOldParent(*newChild, targets, exceptionState);
615    if (exceptionState.hadException())
616        return;
617
618    if (targets.isEmpty())
619        return;
620
621    // We need this extra check because collectChildrenAndRemoveFromOldParent() can fire mutation events.
622    if (!checkAcceptChildGuaranteedNodeTypes(*newChild, exceptionState))
623        return;
624
625    InspectorInstrumentation::willInsertDOMNode(this);
626
627    // Now actually add the child(ren)
628    ChildListMutationScope mutation(*this);
629    for (NodeVector::const_iterator it = targets.begin(); it != targets.end(); ++it) {
630        ASSERT(*it);
631        Node& child = **it;
632
633        // If the child has a parent again, just stop what we're doing, because
634        // that means someone is doing something with DOM mutation -- can't re-parent
635        // a child that already has a parent.
636        if (child.parentNode())
637            break;
638
639        {
640            NoEventDispatchAssertion assertNoEventDispatch;
641            ScriptForbiddenScope forbidScript;
642
643            treeScope().adoptIfNeeded(child);
644            appendChildCommon(child);
645        }
646
647        updateTreeAfterInsertion(child);
648    }
649
650    dispatchSubtreeModifiedEvent();
651}
652
653void ContainerNode::parserAppendChild(PassRefPtrWillBeRawPtr<Node> newChild)
654{
655    ASSERT(newChild);
656    ASSERT(!newChild->parentNode()); // Use appendChild if you need to handle reparenting (and want DOM mutation events).
657    ASSERT(!newChild->isDocumentFragment());
658    ASSERT(!isHTMLTemplateElement(this));
659
660    RefPtrWillBeRawPtr<Node> protect(this);
661
662    if (document() != newChild->document())
663        document().adoptNode(newChild.get(), ASSERT_NO_EXCEPTION);
664
665    {
666        NoEventDispatchAssertion assertNoEventDispatch;
667        ScriptForbiddenScope forbidScript;
668
669        treeScope().adoptIfNeeded(*newChild);
670        appendChildCommon(*newChild);
671        newChild->updateAncestorConnectedSubframeCountForInsertion();
672        ChildListMutationScope(*this).childAdded(*newChild);
673    }
674
675    notifyNodeInserted(*newChild, ChildrenChangeSourceParser);
676}
677
678void ContainerNode::notifyNodeInserted(Node& root, ChildrenChangeSource source)
679{
680    ASSERT(!NoEventDispatchAssertion::isEventDispatchForbidden());
681
682    InspectorInstrumentation::didInsertDOMNode(&root);
683
684    RefPtrWillBeRawPtr<Node> protect(this);
685    RefPtrWillBeRawPtr<Node> protectNode(root);
686
687    NodeVector postInsertionNotificationTargets;
688    notifyNodeInsertedInternal(root, postInsertionNotificationTargets);
689
690    // ShadowRoots are not real children, we don't need to tell host that it's
691    // children changed when one is added.
692    // FIXME: We should have a separate code path for ShadowRoot since it only
693    // needs to call insertedInto and the rest of this logic is not needed.
694    if (!root.isShadowRoot()) {
695        childrenChanged(source == ChildrenChangeSourceParser, root.previousSibling(), root.nextSibling(), 1);
696    }
697
698    for (size_t i = 0; i < postInsertionNotificationTargets.size(); ++i) {
699        Node* targetNode = postInsertionNotificationTargets[i].get();
700        if (targetNode->inDocument())
701            targetNode->didNotifySubtreeInsertionsToDocument();
702    }
703}
704
705void ContainerNode::notifyNodeInsertedInternal(Node& root, NodeVector& postInsertionNotificationTargets)
706{
707    NoEventDispatchAssertion assertNoEventDispatch;
708    ScriptForbiddenScope forbidScript;
709
710    for (Node* node = &root; node; node = NodeTraversal::next(*node, &root)) {
711        // As an optimization we don't notify leaf nodes when when inserting
712        // into detached subtrees.
713        if (!inDocument() && !node->isContainerNode())
714            continue;
715        if (Node::InsertionShouldCallDidNotifySubtreeInsertions == node->insertedInto(this))
716            postInsertionNotificationTargets.append(node);
717        for (ShadowRoot* shadowRoot = node->youngestShadowRoot(); shadowRoot; shadowRoot = shadowRoot->olderShadowRoot())
718            notifyNodeInsertedInternal(*shadowRoot, postInsertionNotificationTargets);
719    }
720}
721
722void ContainerNode::notifyNodeRemoved(Node& root)
723{
724    ScriptForbiddenScope forbidScript;
725    NoEventDispatchAssertion assertNoEventDispatch;
726
727    Document& document = root.document();
728    for (Node* node = &root; node; node = NodeTraversal::next(*node, &root)) {
729        // As an optimization we skip notifying Text nodes and other leaf nodes
730        // of removal when they're not in the Document tree since the virtual
731        // call to removedFrom is not needed.
732        if (!node->inDocument() && !node->isContainerNode())
733            continue;
734        if (document.cssTarget() == node)
735            document.setCSSTarget(nullptr);
736        node->removedFrom(this);
737        for (ShadowRoot* shadowRoot = node->youngestShadowRoot(); shadowRoot; shadowRoot = shadowRoot->olderShadowRoot())
738            notifyNodeRemoved(*shadowRoot);
739    }
740}
741
742void ContainerNode::attach(const AttachContext& context)
743{
744    attachChildren(context);
745    clearChildNeedsStyleRecalc();
746    Node::attach(context);
747}
748
749void ContainerNode::detach(const AttachContext& context)
750{
751    detachChildren(context);
752    clearChildNeedsStyleRecalc();
753    Node::detach(context);
754}
755
756void ContainerNode::childrenChanged(bool changedByParser, Node*, Node*, int childCountDelta)
757{
758    document().incDOMTreeVersion();
759    if (!changedByParser && childCountDelta)
760        document().updateRangesAfterChildrenChanged(this);
761    invalidateNodeListCachesInAncestors();
762    if (childCountDelta > 0 && !childNeedsStyleRecalc()) {
763        setChildNeedsStyleRecalc();
764        markAncestorsWithChildNeedsStyleRecalc();
765    }
766}
767
768void ContainerNode::cloneChildNodes(ContainerNode *clone)
769{
770    TrackExceptionState exceptionState;
771    for (Node* n = firstChild(); n && !exceptionState.hadException(); n = n->nextSibling())
772        clone->appendChild(n->cloneNode(true), exceptionState);
773}
774
775
776bool ContainerNode::getUpperLeftCorner(FloatPoint& point) const
777{
778    if (!renderer())
779        return false;
780    // What is this code really trying to do?
781    RenderObject* o = renderer();
782
783    if (!o->isInline() || o->isReplaced()) {
784        point = o->localToAbsolute(FloatPoint(), UseTransforms);
785        return true;
786    }
787
788    // find the next text/image child, to get a position
789    while (o) {
790        RenderObject* p = o;
791        if (RenderObject* oFirstChild = o->slowFirstChild()) {
792            o = oFirstChild;
793        } else if (o->nextSibling()) {
794            o = o->nextSibling();
795        } else {
796            RenderObject* next = 0;
797            while (!next && o->parent()) {
798                o = o->parent();
799                next = o->nextSibling();
800            }
801            o = next;
802
803            if (!o)
804                break;
805        }
806        ASSERT(o);
807
808        if (!o->isInline() || o->isReplaced()) {
809            point = o->localToAbsolute(FloatPoint(), UseTransforms);
810            return true;
811        }
812
813        if (p->node() && p->node() == this && o->isText() && !o->isBR() && !toRenderText(o)->firstTextBox()) {
814            // do nothing - skip unrendered whitespace that is a child or next sibling of the anchor
815        } else if ((o->isText() && !o->isBR()) || o->isReplaced()) {
816            point = FloatPoint();
817            if (o->isText() && toRenderText(o)->firstTextBox()) {
818                point.move(toRenderText(o)->linesBoundingBox().x(), toRenderText(o)->firstTextBox()->root().lineTop().toFloat());
819            } else if (o->isBox()) {
820                RenderBox* box = toRenderBox(o);
821                point.moveBy(box->location());
822            }
823            point = o->container()->localToAbsolute(point, UseTransforms);
824            return true;
825        }
826    }
827
828    // If the target doesn't have any children or siblings that could be used to calculate the scroll position, we must be
829    // at the end of the document. Scroll to the bottom. FIXME: who said anything about scrolling?
830    if (!o && document().view()) {
831        point = FloatPoint(0, document().view()->contentsHeight());
832        return true;
833    }
834    return false;
835}
836
837bool ContainerNode::getLowerRightCorner(FloatPoint& point) const
838{
839    if (!renderer())
840        return false;
841
842    RenderObject* o = renderer();
843    if (!o->isInline() || o->isReplaced()) {
844        RenderBox* box = toRenderBox(o);
845        point = o->localToAbsolute(LayoutPoint(box->size()), UseTransforms);
846        return true;
847    }
848
849    // find the last text/image child, to get a position
850    while (o) {
851        if (RenderObject* oLastChild = o->slowLastChild()) {
852            o = oLastChild;
853        } else if (o->previousSibling()) {
854            o = o->previousSibling();
855        } else {
856            RenderObject* prev = 0;
857        while (!prev) {
858            o = o->parent();
859            if (!o)
860                return false;
861            prev = o->previousSibling();
862        }
863        o = prev;
864        }
865        ASSERT(o);
866        if (o->isText() || o->isReplaced()) {
867            point = FloatPoint();
868            if (o->isText()) {
869                RenderText* text = toRenderText(o);
870                IntRect linesBox = text->linesBoundingBox();
871                if (!linesBox.maxX() && !linesBox.maxY())
872                    continue;
873                point.moveBy(linesBox.maxXMaxYCorner());
874            } else {
875                RenderBox* box = toRenderBox(o);
876                point.moveBy(box->frameRect().maxXMaxYCorner());
877            }
878            point = o->container()->localToAbsolute(point, UseTransforms);
879            return true;
880        }
881    }
882    return true;
883}
884
885// FIXME: This override is only needed for inline anchors without an
886// InlineBox and it does not belong in ContainerNode as it reaches into
887// the render and line box trees.
888// https://code.google.com/p/chromium/issues/detail?id=248354
889LayoutRect ContainerNode::boundingBox() const
890{
891    FloatPoint upperLeft, lowerRight;
892    bool foundUpperLeft = getUpperLeftCorner(upperLeft);
893    bool foundLowerRight = getLowerRightCorner(lowerRight);
894
895    // If we've found one corner, but not the other,
896    // then we should just return a point at the corner that we did find.
897    if (foundUpperLeft != foundLowerRight) {
898        if (foundUpperLeft)
899            lowerRight = upperLeft;
900        else
901            upperLeft = lowerRight;
902    }
903
904    return enclosingLayoutRect(FloatRect(upperLeft, lowerRight.expandedTo(upperLeft) - upperLeft));
905}
906
907// This is used by FrameSelection to denote when the active-state of the page has changed
908// independent of the focused element changing.
909void ContainerNode::focusStateChanged()
910{
911    // If we're just changing the window's active state and the focused node has no
912    // renderer we can just ignore the state change.
913    if (!renderer())
914        return;
915
916    if (styleChangeType() < SubtreeStyleChange) {
917        if (renderStyle()->affectedByFocus() && renderStyle()->hasPseudoStyle(FIRST_LETTER))
918            setNeedsStyleRecalc(SubtreeStyleChange);
919        else if (isElementNode() && toElement(this)->childrenOrSiblingsAffectedByFocus())
920            document().ensureStyleResolver().ensureUpdatedRuleFeatureSet().scheduleStyleInvalidationForPseudoChange(CSSSelector::PseudoFocus, *toElement(this));
921        else if (renderStyle()->affectedByFocus())
922            setNeedsStyleRecalc(LocalStyleChange);
923    }
924
925    if (renderer() && renderer()->style()->hasAppearance())
926        RenderTheme::theme().stateChanged(renderer(), FocusControlState);
927}
928
929void ContainerNode::setFocus(bool received)
930{
931    if (focused() == received)
932        return;
933
934    Node::setFocus(received);
935
936    focusStateChanged();
937
938    if (renderer() || received)
939        return;
940
941    // If :focus sets display: none, we lose focus but still need to recalc our style.
942    if (isElementNode() && toElement(this)->childrenOrSiblingsAffectedByFocus() && styleChangeType() < SubtreeStyleChange)
943        document().ensureStyleResolver().ensureUpdatedRuleFeatureSet().scheduleStyleInvalidationForPseudoChange(CSSSelector::PseudoFocus, *toElement(this));
944    else
945        setNeedsStyleRecalc(LocalStyleChange);
946}
947
948void ContainerNode::setActive(bool down)
949{
950    if (down == active())
951        return;
952
953    Node::setActive(down);
954
955    // FIXME: Why does this not need to handle the display: none transition like :hover does?
956    if (renderer()) {
957        if (styleChangeType() < SubtreeStyleChange) {
958            if (renderStyle()->affectedByActive() && renderStyle()->hasPseudoStyle(FIRST_LETTER))
959                setNeedsStyleRecalc(SubtreeStyleChange);
960            else if (isElementNode() && toElement(this)->childrenOrSiblingsAffectedByActive())
961                document().ensureStyleResolver().ensureUpdatedRuleFeatureSet().scheduleStyleInvalidationForPseudoChange(CSSSelector::PseudoActive, *toElement(this));
962            else if (renderStyle()->affectedByActive())
963                setNeedsStyleRecalc(LocalStyleChange);
964        }
965
966        if (renderStyle()->hasAppearance())
967            RenderTheme::theme().stateChanged(renderer(), PressedControlState);
968    }
969}
970
971void ContainerNode::setHovered(bool over)
972{
973    if (over == hovered())
974        return;
975
976    Node::setHovered(over);
977
978    // If :hover sets display: none we lose our hover but still need to recalc our style.
979    if (!renderer()) {
980        if (over)
981            return;
982        if (isElementNode() && toElement(this)->childrenOrSiblingsAffectedByHover() && styleChangeType() < SubtreeStyleChange)
983            document().ensureStyleResolver().ensureUpdatedRuleFeatureSet().scheduleStyleInvalidationForPseudoChange(CSSSelector::PseudoHover, *toElement(this));
984        else
985            setNeedsStyleRecalc(LocalStyleChange);
986        return;
987    }
988
989    if (styleChangeType() < SubtreeStyleChange) {
990        if (renderStyle()->affectedByHover() && renderStyle()->hasPseudoStyle(FIRST_LETTER))
991            setNeedsStyleRecalc(SubtreeStyleChange);
992        else if (isElementNode() && toElement(this)->childrenOrSiblingsAffectedByHover())
993            document().ensureStyleResolver().ensureUpdatedRuleFeatureSet().scheduleStyleInvalidationForPseudoChange(CSSSelector::PseudoHover, *toElement(this));
994        else if (renderStyle()->affectedByHover())
995            setNeedsStyleRecalc(LocalStyleChange);
996    }
997
998    if (renderer()->style()->hasAppearance())
999        RenderTheme::theme().stateChanged(renderer(), HoverControlState);
1000}
1001
1002PassRefPtrWillBeRawPtr<HTMLCollection> ContainerNode::children()
1003{
1004    return ensureRareData().ensureNodeLists().addCache<HTMLCollection>(*this, NodeChildren);
1005}
1006
1007unsigned ContainerNode::countChildren() const
1008{
1009    unsigned count = 0;
1010    Node *n;
1011    for (n = firstChild(); n; n = n->nextSibling())
1012        count++;
1013    return count;
1014}
1015
1016Node* ContainerNode::traverseToChildAt(unsigned index) const
1017{
1018    unsigned i;
1019    Node *n = firstChild();
1020    for (i = 0; n != 0 && i < index; i++)
1021        n = n->nextSibling();
1022    return n;
1023}
1024
1025PassRefPtrWillBeRawPtr<Element> ContainerNode::querySelector(const AtomicString& selectors, ExceptionState& exceptionState)
1026{
1027    if (selectors.isEmpty()) {
1028        exceptionState.throwDOMException(SyntaxError, "The provided selector is empty.");
1029        return nullptr;
1030    }
1031
1032    SelectorQuery* selectorQuery = document().selectorQueryCache().add(selectors, document(), exceptionState);
1033    if (!selectorQuery)
1034        return nullptr;
1035    return selectorQuery->queryFirst(*this);
1036}
1037
1038PassRefPtrWillBeRawPtr<StaticNodeList> ContainerNode::querySelectorAll(const AtomicString& selectors, ExceptionState& exceptionState)
1039{
1040    if (selectors.isEmpty()) {
1041        exceptionState.throwDOMException(SyntaxError, "The provided selector is empty.");
1042        return nullptr;
1043    }
1044
1045    SelectorQuery* selectorQuery = document().selectorQueryCache().add(selectors, document(), exceptionState);
1046    if (!selectorQuery)
1047        return nullptr;
1048
1049    return selectorQuery->queryAll(*this);
1050}
1051
1052static void dispatchChildInsertionEvents(Node& child)
1053{
1054    if (child.isInShadowTree())
1055        return;
1056
1057    ASSERT(!NoEventDispatchAssertion::isEventDispatchForbidden());
1058
1059    RefPtrWillBeRawPtr<Node> c(child);
1060    RefPtrWillBeRawPtr<Document> document(child.document());
1061
1062    if (c->parentNode() && document->hasListenerType(Document::DOMNODEINSERTED_LISTENER))
1063        c->dispatchScopedEvent(MutationEvent::create(EventTypeNames::DOMNodeInserted, true, c->parentNode()));
1064
1065    // dispatch the DOMNodeInsertedIntoDocument event to all descendants
1066    if (c->inDocument() && document->hasListenerType(Document::DOMNODEINSERTEDINTODOCUMENT_LISTENER)) {
1067        for (; c; c = NodeTraversal::next(*c, &child))
1068            c->dispatchScopedEvent(MutationEvent::create(EventTypeNames::DOMNodeInsertedIntoDocument, false));
1069    }
1070}
1071
1072static void dispatchChildRemovalEvents(Node& child)
1073{
1074    if (child.isInShadowTree()) {
1075        InspectorInstrumentation::willRemoveDOMNode(&child);
1076        return;
1077    }
1078
1079    ASSERT(!NoEventDispatchAssertion::isEventDispatchForbidden());
1080
1081    InspectorInstrumentation::willRemoveDOMNode(&child);
1082
1083    RefPtrWillBeRawPtr<Node> c(child);
1084    RefPtrWillBeRawPtr<Document> document(child.document());
1085
1086    // dispatch pre-removal mutation events
1087    if (c->parentNode() && document->hasListenerType(Document::DOMNODEREMOVED_LISTENER)) {
1088        NodeChildRemovalTracker scope(child);
1089        c->dispatchScopedEvent(MutationEvent::create(EventTypeNames::DOMNodeRemoved, true, c->parentNode()));
1090    }
1091
1092    // dispatch the DOMNodeRemovedFromDocument event to all descendants
1093    if (c->inDocument() && document->hasListenerType(Document::DOMNODEREMOVEDFROMDOCUMENT_LISTENER)) {
1094        NodeChildRemovalTracker scope(child);
1095        for (; c; c = NodeTraversal::next(*c, &child))
1096            c->dispatchScopedEvent(MutationEvent::create(EventTypeNames::DOMNodeRemovedFromDocument, false));
1097    }
1098}
1099
1100void ContainerNode::updateTreeAfterInsertion(Node& child)
1101{
1102#if !ENABLE(OILPAN)
1103    ASSERT(refCount());
1104    ASSERT(child.refCount());
1105#endif
1106
1107    ChildListMutationScope(*this).childAdded(child);
1108
1109    notifyNodeInserted(child);
1110
1111    dispatchChildInsertionEvents(child);
1112}
1113
1114bool ContainerNode::hasRestyleFlagInternal(DynamicRestyleFlags mask) const
1115{
1116    return rareData()->hasRestyleFlag(mask);
1117}
1118
1119bool ContainerNode::hasRestyleFlagsInternal() const
1120{
1121    return rareData()->hasRestyleFlags();
1122}
1123
1124void ContainerNode::setRestyleFlag(DynamicRestyleFlags mask)
1125{
1126    ASSERT(isElementNode() || isShadowRoot());
1127    ensureRareData().setRestyleFlag(mask);
1128}
1129
1130void ContainerNode::checkForChildrenAdjacentRuleChanges()
1131{
1132    bool hasDirectAdjacentRules = childrenAffectedByDirectAdjacentRules();
1133    bool hasIndirectAdjacentRules = childrenAffectedByIndirectAdjacentRules();
1134
1135    if (!hasDirectAdjacentRules && !hasIndirectAdjacentRules)
1136        return;
1137
1138    unsigned forceCheckOfNextElementCount = 0;
1139    bool forceCheckOfAnyElementSibling = false;
1140    Document& document = this->document();
1141
1142    for (Element* child = ElementTraversal::firstChild(*this); child; child = ElementTraversal::nextSibling(*child)) {
1143        bool childRulesChanged = child->needsStyleRecalc() && child->styleChangeType() >= SubtreeStyleChange;
1144
1145        if (forceCheckOfNextElementCount || forceCheckOfAnyElementSibling)
1146            child->setNeedsStyleRecalc(SubtreeStyleChange);
1147
1148        if (childRulesChanged && hasDirectAdjacentRules)
1149            forceCheckOfNextElementCount = document.styleEngine()->maxDirectAdjacentSelectors();
1150        else if (forceCheckOfNextElementCount)
1151            --forceCheckOfNextElementCount;
1152
1153        forceCheckOfAnyElementSibling = forceCheckOfAnyElementSibling || (childRulesChanged && hasIndirectAdjacentRules);
1154    }
1155}
1156
1157void ContainerNode::checkForSiblingStyleChanges(bool finishedParsingCallback, Node* beforeChange, Node* afterChange, int childCountDelta)
1158{
1159    if (!inActiveDocument() || document().hasPendingForcedStyleRecalc() || styleChangeType() >= SubtreeStyleChange)
1160        return;
1161
1162    if (needsStyleRecalc() && childrenAffectedByPositionalRules())
1163        return;
1164
1165    // Forward positional selectors include nth-child, nth-of-type, first-of-type and only-of-type.
1166    // The indirect adjacent selector is the ~ selector.
1167    // Backward positional selectors include nth-last-child, nth-last-of-type, last-of-type and only-of-type.
1168    // We have to invalidate everything following the insertion point in the forward and indirect adjacent case,
1169    // and everything before the insertion point in the backward case.
1170    // |afterChange| is 0 in the parser callback case, so we won't do any work for the forward case if we don't have to.
1171    // For performance reasons we just mark the parent node as changed, since we don't want to make childrenChanged O(n^2) by crawling all our kids
1172    // here. recalcStyle will then force a walk of the children when it sees that this has happened.
1173    if (((childrenAffectedByForwardPositionalRules() || childrenAffectedByIndirectAdjacentRules()) && afterChange)
1174        || (childrenAffectedByBackwardPositionalRules() && beforeChange)) {
1175        setNeedsStyleRecalc(SubtreeStyleChange);
1176        return;
1177    }
1178
1179    // :first-child. In the parser callback case, we don't have to check anything, since we were right the first time.
1180    // In the DOM case, we only need to do something if |afterChange| is not 0.
1181    // |afterChange| is 0 in the parser case, so it works out that we'll skip this block.
1182    if (childrenAffectedByFirstChildRules() && afterChange) {
1183        // Find our new first child.
1184        Element* newFirstChild = ElementTraversal::firstWithin(*this);
1185        RenderStyle* newFirstChildStyle = newFirstChild ? newFirstChild->renderStyle() : 0;
1186
1187        // Find the first element node following |afterChange|
1188        Node* firstElementAfterInsertion = afterChange->isElementNode() ? afterChange : ElementTraversal::nextSibling(*afterChange);
1189        RenderStyle* firstElementAfterInsertionStyle = firstElementAfterInsertion ? firstElementAfterInsertion->renderStyle() : 0;
1190
1191        // This is the insert/append case.
1192        if (newFirstChild != firstElementAfterInsertion && firstElementAfterInsertionStyle && firstElementAfterInsertionStyle->firstChildState())
1193            firstElementAfterInsertion->setNeedsStyleRecalc(SubtreeStyleChange);
1194
1195        // We also have to handle node removal.
1196        if (childCountDelta < 0 && newFirstChild == firstElementAfterInsertion && newFirstChild && (!newFirstChildStyle || !newFirstChildStyle->firstChildState()))
1197            newFirstChild->setNeedsStyleRecalc(SubtreeStyleChange);
1198    }
1199
1200    // :last-child. In the parser callback case, we don't have to check anything, since we were right the first time.
1201    // In the DOM case, we only need to do something if |afterChange| is not 0.
1202    if (childrenAffectedByLastChildRules() && beforeChange) {
1203        // Find our new last child.
1204        Node* newLastChild = ElementTraversal::lastChild(*this);
1205        RenderStyle* newLastChildStyle = newLastChild ? newLastChild->renderStyle() : 0;
1206
1207        // Find the last element node going backwards from |beforeChange|
1208        Node* lastElementBeforeInsertion = beforeChange->isElementNode() ? beforeChange : ElementTraversal::previousSibling(*beforeChange);
1209        RenderStyle* lastElementBeforeInsertionStyle = lastElementBeforeInsertion ? lastElementBeforeInsertion->renderStyle() : 0;
1210
1211        if (newLastChild != lastElementBeforeInsertion && lastElementBeforeInsertionStyle && lastElementBeforeInsertionStyle->lastChildState())
1212            lastElementBeforeInsertion->setNeedsStyleRecalc(SubtreeStyleChange);
1213
1214        // We also have to handle node removal. The parser callback case is similar to node removal as well in that we need to change the last child
1215        // to match now.
1216        if ((childCountDelta < 0 || finishedParsingCallback) && newLastChild == lastElementBeforeInsertion && newLastChild && (!newLastChildStyle || !newLastChildStyle->lastChildState()))
1217            newLastChild->setNeedsStyleRecalc(SubtreeStyleChange);
1218    }
1219
1220    // The + selector. We need to invalidate the first element following the insertion point. It is the only possible element
1221    // that could be affected by this DOM change.
1222    if (childrenAffectedByDirectAdjacentRules() && afterChange) {
1223        if (Node* firstElementAfterInsertion = afterChange->isElementNode() ? afterChange : ElementTraversal::nextSibling(*afterChange))
1224            firstElementAfterInsertion->setNeedsStyleRecalc(SubtreeStyleChange);
1225    }
1226}
1227
1228PassRefPtrWillBeRawPtr<TagCollection> ContainerNode::getElementsByTagName(const AtomicString& localName)
1229{
1230    if (localName.isNull())
1231        return nullptr;
1232
1233    if (document().isHTMLDocument())
1234        return ensureRareData().ensureNodeLists().addCache<HTMLTagCollection>(*this, HTMLTagCollectionType, localName);
1235    return ensureRareData().ensureNodeLists().addCache<TagCollection>(*this, TagCollectionType, localName);
1236}
1237
1238PassRefPtrWillBeRawPtr<TagCollection> ContainerNode::getElementsByTagNameNS(const AtomicString& namespaceURI, const AtomicString& localName)
1239{
1240    if (localName.isNull())
1241        return nullptr;
1242
1243    if (namespaceURI == starAtom)
1244        return getElementsByTagName(localName);
1245
1246    return ensureRareData().ensureNodeLists().addCache(*this, namespaceURI.isEmpty() ? nullAtom : namespaceURI, localName);
1247}
1248
1249// Takes an AtomicString in argument because it is common for elements to share the same name attribute.
1250// Therefore, the NameNodeList factory function expects an AtomicString type.
1251PassRefPtrWillBeRawPtr<NameNodeList> ContainerNode::getElementsByName(const AtomicString& elementName)
1252{
1253    return ensureRareData().ensureNodeLists().addCache<NameNodeList>(*this, NameNodeListType, elementName);
1254}
1255
1256// Takes an AtomicString in argument because it is common for elements to share the same set of class names.
1257// Therefore, the ClassNodeList factory function expects an AtomicString type.
1258PassRefPtrWillBeRawPtr<ClassCollection> ContainerNode::getElementsByClassName(const AtomicString& classNames)
1259{
1260    return ensureRareData().ensureNodeLists().addCache<ClassCollection>(*this, ClassCollectionType, classNames);
1261}
1262
1263PassRefPtrWillBeRawPtr<RadioNodeList> ContainerNode::radioNodeList(const AtomicString& name, bool onlyMatchImgElements)
1264{
1265    ASSERT(isHTMLFormElement(this) || isHTMLFieldSetElement(this));
1266    CollectionType type = onlyMatchImgElements ? RadioImgNodeListType : RadioNodeListType;
1267    return ensureRareData().ensureNodeLists().addCache<RadioNodeList>(*this, type, name);
1268}
1269
1270Element* ContainerNode::getElementById(const AtomicString& id) const
1271{
1272    if (isInTreeScope()) {
1273        // Fast path if we are in a tree scope: call getElementById() on tree scope
1274        // and check if the matching element is in our subtree.
1275        Element* element = treeScope().getElementById(id);
1276        if (!element)
1277            return 0;
1278        if (element->isDescendantOf(this))
1279            return element;
1280    }
1281
1282    // Fall back to traversing our subtree. In case of duplicate ids, the first element found will be returned.
1283    for (Element* element = ElementTraversal::firstWithin(*this); element; element = ElementTraversal::next(*element, this)) {
1284        if (element->getIdAttribute() == id)
1285            return element;
1286    }
1287    return 0;
1288}
1289
1290#ifndef NDEBUG
1291bool childAttachedAllowedWhenAttachingChildren(ContainerNode* node)
1292{
1293    if (node->isShadowRoot())
1294        return true;
1295
1296    if (node->isInsertionPoint())
1297        return true;
1298
1299    if (node->isElementNode() && toElement(node)->shadow())
1300        return true;
1301
1302    return false;
1303}
1304#endif
1305
1306} // namespace WebCore
1307