Home | History | Annotate | Download | only in dom 
      1 /*
      2  * Copyright (C) 1999 Lars Knoll (knoll (at) kde.org)
      3  *           (C) 1999 Antti Koivisto (koivisto (at) kde.org)
      4  *           (C) 2001 Dirk Mueller (mueller (at) 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 
     55 namespace WebCore {
     56 
     57 using namespace HTMLNames;
     58 
     59 static void dispatchChildInsertionEvents(Node&);
     60 static void dispatchChildRemovalEvents(Node&);
     61 
     62 #ifndef NDEBUG
     63 unsigned NoEventDispatchAssertion::s_count = 0;
     64 #endif
     65 
     66 static 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)
     79 void ContainerNode::removeDetachedChildren()
     80 {
     81     ASSERT(!connectedSubframeCount());
     82     ASSERT(needsAttach());
     83     removeDetachedChildrenInContainer<Node, ContainerNode>(*this);
     84 }
     85 #endif
     86 
     87 void 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 
     96 ContainerNode::~ContainerNode()
     97 {
     98     ASSERT(needsAttach());
     99 #if !ENABLE(OILPAN)
    100     willBeDeletedFromDocument();
    101     removeDetachedChildren();
    102 #endif
    103 }
    104 
    105 bool 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 
    117 bool ContainerNode::containsConsideringHostElements(const Node& newChild) const
    118 {
    119     if (isInShadowTree() || document().isTemplateDocument())
    120         return newChild.containsIncludingHostElements(*this);
    121     return newChild.contains(this);
    122 }
    123 
    124 bool 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 
    168 bool 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 
    178 void 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 
    247 void 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 
    273 void 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 
    287 void 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 
    311 void 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 
    399 void 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 
    409 void 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 
    426 void ContainerNode::disconnectDescendantFrames()
    427 {
    428     ChildFrameDisconnector(*this).disconnect();
    429 }
    430 
    431 void ContainerNode::trace(Visitor* visitor)
    432 {
    433     visitor->trace(m_firstChild);
    434     visitor->trace(m_lastChild);
    435     Node::trace(visitor);
    436 }
    437 
    438 void 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 
    491 void 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 
    516 void 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.
    537 void 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 
    595 void 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 
    653 void 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 
    678 void 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 
    705 void 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 
    722 void 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 
    742 void ContainerNode::attach(const AttachContext& context)
    743 {
    744     attachChildren(context);
    745     clearChildNeedsStyleRecalc();
    746     Node::attach(context);
    747 }
    748 
    749 void ContainerNode::detach(const AttachContext& context)
    750 {
    751     detachChildren(context);
    752     clearChildNeedsStyleRecalc();
    753     Node::detach(context);
    754 }
    755 
    756 void 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 
    768 void 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 
    776 bool 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 
    837 bool 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
    889 LayoutRect 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.
    909 void 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 
    929 void 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 
    948 void 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 
    971 void 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 
   1002 PassRefPtrWillBeRawPtr<HTMLCollection> ContainerNode::children()
   1003 {
   1004     return ensureRareData().ensureNodeLists().addCache<HTMLCollection>(*this, NodeChildren);
   1005 }
   1006 
   1007 unsigned 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 
   1016 Node* 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 
   1025 PassRefPtrWillBeRawPtr<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 
   1038 PassRefPtrWillBeRawPtr<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 
   1052 static 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 
   1072 static 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 
   1100 void 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 
   1114 bool ContainerNode::hasRestyleFlagInternal(DynamicRestyleFlags mask) const
   1115 {
   1116     return rareData()->hasRestyleFlag(mask);
   1117 }
   1118 
   1119 bool ContainerNode::hasRestyleFlagsInternal() const
   1120 {
   1121     return rareData()->hasRestyleFlags();
   1122 }
   1123 
   1124 void ContainerNode::setRestyleFlag(DynamicRestyleFlags mask)
   1125 {
   1126     ASSERT(isElementNode() || isShadowRoot());
   1127     ensureRareData().setRestyleFlag(mask);
   1128 }
   1129 
   1130 void 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 
   1157 void 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 
   1228 PassRefPtrWillBeRawPtr<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 
   1238 PassRefPtrWillBeRawPtr<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.
   1251 PassRefPtrWillBeRawPtr<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.
   1258 PassRefPtrWillBeRawPtr<ClassCollection> ContainerNode::getElementsByClassName(const AtomicString& classNames)
   1259 {
   1260     return ensureRareData().ensureNodeLists().addCache<ClassCollection>(*this, ClassCollectionType, classNames);
   1261 }
   1262 
   1263 PassRefPtrWillBeRawPtr<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 
   1270 Element* 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
   1291 bool 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