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