src/third_party/WebKit/Source/core/dom/ContainerNode.cpp

   1 /*
   2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
   3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
   4  *           (C) 2001 Dirk Mueller (mueller@kde.org)
   5  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2013 Apple Inc. All rights reserved.
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Library General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Library General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Library General Public License
  18  * along with this library; see the file COPYING.LIB.  If not, write to
  19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  20  * Boston, MA 02110-1301, USA.
  21  */
  22
  23 #include "config.h"
  24 #include "core/dom/ContainerNode.h"
  25
  26 #include "bindings/core/v8/ExceptionState.h"
  27 #include "core/dom/ChildFrameDisconnector.h"
  28 #include "core/dom/ChildListMutationScope.h"
  29 #include "core/dom/ClassCollection.h"
  30 #include "core/dom/ElementTraversal.h"
  31 #include "core/dom/ExceptionCode.h"
  32 #include "core/dom/NameNodeList.h"
  33 #include "core/dom/NodeChildRemovalTracker.h"
  34 #include "core/dom/NodeRareData.h"
  35 #include "core/dom/NodeRenderStyle.h"
  36 #include "core/dom/NodeTraversal.h"
  37 #include "core/dom/SelectorQuery.h"
  38 #include "core/dom/StaticNodeList.h"
  39 #include "core/dom/StyleEngine.h"
  40 #include "core/dom/shadow/ElementShadow.h"
  41 #include "core/dom/shadow/ShadowRoot.h"
  42 #include "core/events/MutationEvent.h"
  43 #include "core/html/HTMLCollection.h"
  44 #include "core/html/HTMLFrameOwnerElement.h"
  45 #include "core/html/HTMLTagCollection.h"
  46 #include "core/html/RadioNodeList.h"
  47 #include "core/inspector/InspectorInstrumentation.h"
  48 #include "core/rendering/InlineTextBox.h"
  49 #include "core/rendering/RenderText.h"
  50 #include "core/rendering/RenderTheme.h"
  51 #include "core/rendering/RenderView.h"
  52 #include "platform/EventDispatchForbiddenScope.h"
  53 #include "platform/ScriptForbiddenScope.h"
  54
  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