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, 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 
     55 namespace blink {
     56 
     57 using namespace HTMLNames;
     58 
     59 static void dispatchChildInsertionEvents(Node&);
     60 static void dispatchChildRemovalEvents(Node&);
     61 
     62 #if ENABLE(ASSERT)
     63 unsigned EventDispatchForbiddenScope::s_count = 0;
     64 #endif
     65 
     66 static 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)
     80 void ContainerNode::removeDetachedChildren()
     81 {
     82     ASSERT(!connectedSubframeCount());
     83     ASSERT(needsAttach());
     84     removeDetachedChildrenInContainer(*this);
     85 }
     86 #endif
     87 
     88 void 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 
     97 ContainerNode::~ContainerNode()
     98 {
     99     ASSERT(needsAttach());
    100 #if !ENABLE(OILPAN)
    101     willBeDeletedFromDocument();
    102     removeDetachedChildren();
    103 #endif
    104 }
    105 
    106 bool 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 
    118 bool ContainerNode::containsConsideringHostElements(const Node& newChild) const
    119 {
    120     if (isInShadowTree() || document().isTemplateDocument())
    121         return newChild.containsIncludingHostElements(*this);
    122     return newChild.contains(this);
    123 }
    124 
    125 bool 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 
    169 bool 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 
    179 PassRefPtrWillBeRawPtr<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 
    256 void 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 
    282 void 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 
    296 void 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 
    320 PassRefPtrWillBeRawPtr<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 
    418 void 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 
    428 void 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)
    446 void 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 
    473 void 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 
    511 void ContainerNode::disconnectDescendantFrames()
    512 {
    513     ChildFrameDisconnector(*this).disconnect();
    514 }
    515 
    516 void ContainerNode::trace(Visitor* visitor)
    517 {
    518     visitor->trace(m_firstChild);
    519     visitor->trace(m_lastChild);
    520     Node::trace(visitor);
    521 }
    522 
    523 PassRefPtrWillBeRawPtr<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 
    574 void 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 
    599 void 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.
    620 void 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 
    680 PassRefPtrWillBeRawPtr<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 
    745 void 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 
    770 void 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 
    792 void 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 
    809 void 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 
    829 void ContainerNode::attach(const AttachContext& context)
    830 {
    831     attachChildren(context);
    832     clearChildNeedsStyleRecalc();
    833     Node::attach(context);
    834 }
    835 
    836 void ContainerNode::detach(const AttachContext& context)
    837 {
    838     detachChildren(context);
    839     clearChildNeedsStyleRecalc();
    840     Node::detach(context);
    841 }
    842 
    843 void 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 
    855 void 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 
    863 bool 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 
    924 bool 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
    976 LayoutRect 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.
    996 void 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 
   1016 void 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 
   1035 void 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 
   1058 void 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 
   1089 PassRefPtrWillBeRawPtr<HTMLCollection> ContainerNode::children()
   1090 {
   1091     return ensureCachedCollection<HTMLCollection>(NodeChildren);
   1092 }
   1093 
   1094 unsigned 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 
   1103 PassRefPtrWillBeRawPtr<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 
   1116 PassRefPtrWillBeRawPtr<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 
   1130 static 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 
   1150 static 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 
   1178 void 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 
   1192 bool ContainerNode::hasRestyleFlagInternal(DynamicRestyleFlags mask) const
   1193 {
   1194     return rareData()->hasRestyleFlag(mask);
   1195 }
   1196 
   1197 bool ContainerNode::hasRestyleFlagsInternal() const
   1198 {
   1199     return rareData()->hasRestyleFlags();
   1200 }
   1201 
   1202 void ContainerNode::setRestyleFlag(DynamicRestyleFlags mask)
   1203 {
   1204     ASSERT(isElementNode() || isShadowRoot());
   1205     ensureRareData().setRestyleFlag(mask);
   1206 }
   1207 
   1208 void 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 
   1239 void 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 
   1266 void 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 
   1343 void 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 
   1367 PassRefPtrWillBeRawPtr<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 
   1377 PassRefPtrWillBeRawPtr<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.
   1390 PassRefPtrWillBeRawPtr<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.
   1397 PassRefPtrWillBeRawPtr<ClassCollection> ContainerNode::getElementsByClassName(const AtomicString& classNames)
   1398 {
   1399     return ensureCachedCollection<ClassCollection>(ClassCollectionType, classNames);
   1400 }
   1401 
   1402 PassRefPtrWillBeRawPtr<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 
   1409 Element* 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 
   1429 NodeListsNodeData& ContainerNode::ensureNodeLists()
   1430 {
   1431     return ensureRareData().ensureNodeLists();
   1432 }
   1433 
   1434 #if ENABLE(ASSERT)
   1435 bool 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