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