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

   1 /*
   2  * Copyright (C) 2011 Google Inc. All Rights Reserved.
   3  * Copyright (C) 2012 Apple Inc. All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #include "config.h"
  28 #include "core/dom/TreeScope.h"
  29
  30 #include "HTMLNames.h"
  31 #include "core/dom/ContainerNode.h"
  32 #include "core/dom/Document.h"
  33 #include "core/dom/Element.h"
  34 #include "core/dom/ElementTraversal.h"
  35 #include "core/dom/IdTargetObserverRegistry.h"
  36 #include "core/dom/NodeRenderStyle.h"
  37 #include "core/dom/TreeScopeAdopter.h"
  38 #include "core/dom/shadow/ElementShadow.h"
  39 #include "core/dom/shadow/ShadowRoot.h"
  40 #include "core/events/EventPath.h"
  41 #include "core/frame/FrameView.h"
  42 #include "core/frame/LocalFrame.h"
  43 #include "core/html/HTMLAnchorElement.h"
  44 #include "core/html/HTMLFrameOwnerElement.h"
  45 #include "core/html/HTMLLabelElement.h"
  46 #include "core/html/HTMLMapElement.h"
  47 #include "core/page/DOMSelection.h"
  48 #include "core/page/FocusController.h"
  49 #include "core/page/Page.h"
  50 #include "core/rendering/HitTestResult.h"
  51 #include "core/rendering/RenderView.h"
  52 #include "wtf/Vector.h"
  53
  54 namespace WebCore {
  55
  56 using namespace HTMLNames;
  57
  58 TreeScope::TreeScope(ContainerNode& rootNode, Document& document)
  59     : m_rootNode(&rootNode)
  60     , m_document(&document)
  61     , m_parentTreeScope(&document)
  62 #if !ENABLE(OILPAN)
  63     , m_guardRefCount(0)
  64 #endif
  65     , m_idTargetObserverRegistry(IdTargetObserverRegistry::create())
  66 {
  67     ASSERT(rootNode != document);
  68 #if !ENABLE(OILPAN)
  69     m_parentTreeScope->guardRef();
  70 #endif
  71     m_rootNode->setTreeScope(this);
  72 }
  73
  74 TreeScope::TreeScope(Document& document)
  75     : m_rootNode(document)
  76     , m_document(&document)
  77     , m_parentTreeScope(nullptr)
  78 #if !ENABLE(OILPAN)
  79     , m_guardRefCount(0)
  80 #endif
  81     , m_idTargetObserverRegistry(IdTargetObserverRegistry::create())
  82 {
  83     m_rootNode->setTreeScope(this);
  84 }
  85
  86 TreeScope::~TreeScope()
  87 {
  88 #if !ENABLE(OILPAN)
  89     ASSERT(!m_guardRefCount);
  90     m_rootNode->setTreeScope(0);
  91
  92     if (m_selection) {
  93         m_selection->clearTreeScope();
  94         m_selection = nullptr;
  95     }
  96
  97     if (m_parentTreeScope)
  98         m_parentTreeScope->guardDeref();
  99 #endif
 100 }
 101
 102 TreeScope* TreeScope::olderShadowRootOrParentTreeScope() const
 103 {
 104     if (rootNode().isShadowRoot()) {
 105         if (ShadowRoot* olderShadowRoot = toShadowRoot(rootNode()).olderShadowRoot())
 106             return olderShadowRoot;
 107     }
 108     return parentTreeScope();
 109 }
 110
 111 bool TreeScope::isInclusiveOlderSiblingShadowRootOrAncestorTreeScopeOf(const TreeScope& scope) const
 112 {
 113     for (const TreeScope* current = &scope; current; current = current->olderShadowRootOrParentTreeScope()) {
 114         if (current == this)
 115             return true;
 116     }
 117     return false;
 118 }
 119
 120 bool TreeScope::rootNodeHasTreeSharedParent() const
 121 {
 122     return rootNode().hasTreeSharedParent();
 123 }
 124
 125 #if !ENABLE(OILPAN)
 126 void TreeScope::destroyTreeScopeData()
 127 {
 128     m_elementsById.clear();
 129     m_imageMapsByName.clear();
 130     m_labelsByForAttribute.clear();
 131 }
 132 #endif
 133
 134 void TreeScope::setParentTreeScope(TreeScope& newParentScope)
 135 {
 136     // A document node cannot be re-parented.
 137     ASSERT(!rootNode().isDocumentNode());
 138
 139 #if !ENABLE(OILPAN)
 140     newParentScope.guardRef();
 141     if (m_parentTreeScope)
 142         m_parentTreeScope->guardDeref();
 143 #endif
 144     m_parentTreeScope = &newParentScope;
 145     setDocument(newParentScope.document());
 146 }
 147
 148 Element* TreeScope::getElementById(const AtomicString& elementId) const
 149 {
 150     if (elementId.isEmpty())
 151         return 0;
 152     if (!m_elementsById)
 153         return 0;
 154     return m_elementsById->getElementById(elementId.impl(), this);
 155 }
 156
 157 const Vector<Element*>& TreeScope::getAllElementsById(const AtomicString& elementId) const
 158 {
 159     DEFINE_STATIC_LOCAL(Vector<Element*>, emptyVector, ());
 160     if (elementId.isEmpty())
 161         return emptyVector;
 162     if (!m_elementsById)
 163         return emptyVector;
 164     return m_elementsById->getAllElementsById(elementId.impl(), this);
 165 }
 166
 167 void TreeScope::addElementById(const AtomicString& elementId, Element* element)
 168 {
 169     if (!m_elementsById)
 170         m_elementsById = adoptPtr(new DocumentOrderedMap);
 171     m_elementsById->add(elementId.impl(), element);
 172     m_idTargetObserverRegistry->notifyObservers(elementId);
 173 }
 174
 175 void TreeScope::removeElementById(const AtomicString& elementId, Element* element)
 176 {
 177     if (!m_elementsById)
 178         return;
 179     m_elementsById->remove(elementId.impl(), element);
 180     m_idTargetObserverRegistry->notifyObservers(elementId);
 181 }
 182
 183 Node* TreeScope::ancestorInThisScope(Node* node) const
 184 {
 185     while (node) {
 186         if (node->treeScope() == this)
 187             return node;
 188         if (!node->isInShadowTree())
 189             return 0;
 190
 191         node = node->shadowHost();
 192     }
 193
 194     return 0;
 195 }
 196
 197 void TreeScope::addImageMap(HTMLMapElement* imageMap)
 198 {
 199     StringImpl* name = imageMap->getName().impl();
 200     if (!name)
 201         return;
 202     if (!m_imageMapsByName)
 203         m_imageMapsByName = adoptPtr(new DocumentOrderedMap);
 204     m_imageMapsByName->add(name, imageMap);
 205 }
 206
 207 void TreeScope::removeImageMap(HTMLMapElement* imageMap)
 208 {
 209     if (!m_imageMapsByName)
 210         return;
 211     StringImpl* name = imageMap->getName().impl();
 212     if (!name)
 213         return;
 214     m_imageMapsByName->remove(name, imageMap);
 215 }
 216
 217 HTMLMapElement* TreeScope::getImageMap(const String& url) const
 218 {
 219     if (url.isNull())
 220         return 0;
 221     if (!m_imageMapsByName)
 222         return 0;
 223     size_t hashPos = url.find('#');
 224     String name = (hashPos == kNotFound ? url : url.substring(hashPos + 1)).impl();
 225     if (rootNode().document().isHTMLDocument())
 226         return toHTMLMapElement(m_imageMapsByName->getElementByLowercasedMapName(AtomicString(name.lower()).impl(), this));
 227     return toHTMLMapElement(m_imageMapsByName->getElementByMapName(AtomicString(name).impl(), this));
 228 }
 229
 230 HitTestResult hitTestInDocument(const Document* document, int x, int y)
 231 {
 232     LocalFrame* frame = document->frame();
 233
 234     if (!frame)
 235         return HitTestResult();
 236     FrameView* frameView = frame->view();
 237     if (!frameView)
 238         return HitTestResult();
 239
 240     float scaleFactor = frame->pageZoomFactor();
 241     IntPoint point = roundedIntPoint(FloatPoint(x * scaleFactor  + frameView->scrollX(), y * scaleFactor + frameView->scrollY()));
 242
 243     if (!frameView->visibleContentRect().contains(point))
 244         return HitTestResult();
 245
 246     HitTestRequest request(HitTestRequest::ReadOnly | HitTestRequest::Active | HitTestRequest::ConfusingAndOftenMisusedDisallowShadowContent);
 247     HitTestResult result(point);
 248     document->renderView()->hitTest(request, result);
 249     return result;
 250 }
 251
 252 Element* TreeScope::elementFromPoint(int x, int y) const
 253 {
 254     HitTestResult result = hitTestInDocument(&rootNode().document(), x, y);
 255     Node* node = result.innerNode();
 256     if (!node || node->isDocumentNode())
 257         return 0;
 258     if (node->isPseudoElement() || node->isTextNode())
 259         node = node->parentOrShadowHostNode();
 260     ASSERT(!node || node->isElementNode() || node->isShadowRoot());
 261     node = ancestorInThisScope(node);
 262     if (!node || !node->isElementNode())
 263         return 0;
 264     return toElement(node);
 265 }
 266
 267 void TreeScope::addLabel(const AtomicString& forAttributeValue, HTMLLabelElement* element)
 268 {
 269     ASSERT(m_labelsByForAttribute);
 270     m_labelsByForAttribute->add(forAttributeValue.impl(), element);
 271 }
 272
 273 void TreeScope::removeLabel(const AtomicString& forAttributeValue, HTMLLabelElement* element)
 274 {
 275     ASSERT(m_labelsByForAttribute);
 276     m_labelsByForAttribute->remove(forAttributeValue.impl(), element);
 277 }
 278
 279 HTMLLabelElement* TreeScope::labelElementForId(const AtomicString& forAttributeValue)
 280 {
 281     if (forAttributeValue.isEmpty())
 282         return 0;
 283
 284     if (!m_labelsByForAttribute) {
 285         // Populate the map on first access.
 286         m_labelsByForAttribute = adoptPtr(new DocumentOrderedMap);
 287         for (HTMLLabelElement* label = Traversal<HTMLLabelElement>::firstWithin(rootNode()); label; label = Traversal<HTMLLabelElement>::next(*label)) {
 288             const AtomicString& forValue = label->fastGetAttribute(forAttr);
 289             if (!forValue.isEmpty())
 290                 addLabel(forValue, label);
 291         }
 292     }
 293
 294     return toHTMLLabelElement(m_labelsByForAttribute->getElementByLabelForAttribute(forAttributeValue.impl(), this));
 295 }
 296
 297 DOMSelection* TreeScope::getSelection() const
 298 {
 299     if (!rootNode().document().frame())
 300         return 0;
 301
 302     if (m_selection)
 303         return m_selection.get();
 304
 305     // FIXME: The correct selection in Shadow DOM requires that Position can have a ShadowRoot
 306     // as a container.
 307     // See https://bugs.webkit.org/show_bug.cgi?id=82697
 308     m_selection = DOMSelection::create(this);
 309     return m_selection.get();
 310 }
 311
 312 Element* TreeScope::findAnchor(const String& name)
 313 {
 314     if (name.isEmpty())
 315         return 0;
 316     if (Element* element = getElementById(AtomicString(name)))
 317         return element;
 318     for (HTMLAnchorElement* anchor = Traversal<HTMLAnchorElement>::firstWithin(rootNode()); anchor; anchor = Traversal<HTMLAnchorElement>::next(*anchor)) {
 319         if (rootNode().document().inQuirksMode()) {
 320             // Quirks mode, case insensitive comparison of names.
 321             if (equalIgnoringCase(anchor->name(), name))
 322                 return anchor;
 323         } else {
 324             // Strict mode, names need to match exactly.
 325             if (anchor->name() == name)
 326                 return anchor;
 327         }
 328     }
 329     return 0;
 330 }
 331
 332 bool TreeScope::applyAuthorStyles() const
 333 {
 334     return rootNode().isDocumentNode();
 335 }
 336
 337 void TreeScope::adoptIfNeeded(Node& node)
 338 {
 339     ASSERT(this);
 340     ASSERT(!node.isDocumentNode());
 341 #if !ENABLE(OILPAN)
 342     ASSERT_WITH_SECURITY_IMPLICATION(!node.m_deletionHasBegun);
 343 #endif
 344     TreeScopeAdopter adopter(node, *this);
 345     if (adopter.needsScopeChange())
 346         adopter.execute();
 347 }
 348
 349 static Element* focusedFrameOwnerElement(LocalFrame* focusedFrame, LocalFrame* currentFrame)
 350 {
 351     for (; focusedFrame; focusedFrame = focusedFrame->tree().parent()) {
 352         if (focusedFrame->tree().parent() == currentFrame)
 353             return focusedFrame->ownerElement();
 354     }
 355     return 0;
 356 }
 357
 358 Element* TreeScope::adjustedFocusedElement() const
 359 {
 360     Document& document = rootNode().document();
 361     Element* element = document.focusedElement();
 362     // FIXME(kenrb): The toLocalFrame() cast should be removed when RemoteFrames can have FrameTrees.
 363     // At that point, focusedFrameOwnerElement should take a Frame instead of a LocalFrame.
 364     if (!element && document.page())
 365         element = focusedFrameOwnerElement(toLocalFrameTemporary(document.page()->focusController().focusedFrame()), document.frame());
 366     if (!element)
 367         return 0;
 368
 369     EventPath eventPath(element);
 370     for (size_t i = 0; i < eventPath.size(); ++i) {
 371         if (eventPath[i].node() == rootNode()) {
 372             // eventPath.at(i).target() is one of the followings:
 373             // - InsertionPoint
 374             // - shadow host
 375             // - Document::focusedElement()
 376             // So, it's safe to do toElement().
 377             return toElement(eventPath[i].target()->toNode());
 378         }
 379     }
 380     return 0;
 381 }
 382
 383 unsigned short TreeScope::comparePosition(const TreeScope& otherScope) const
 384 {
 385     if (otherScope == this)
 386         return Node::DOCUMENT_POSITION_EQUIVALENT;
 387
 388     Vector<const TreeScope*, 16> chain1;
 389     Vector<const TreeScope*, 16> chain2;
 390     const TreeScope* current;
 391     for (current = this; current; current = current->parentTreeScope())
 392         chain1.append(current);
 393     for (current = &otherScope; current; current = current->parentTreeScope())
 394         chain2.append(current);
 395
 396     unsigned index1 = chain1.size();
 397     unsigned index2 = chain2.size();
 398     if (chain1[index1 - 1] != chain2[index2 - 1])
 399         return Node::DOCUMENT_POSITION_DISCONNECTED | Node::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC;
 400
 401     for (unsigned i = std::min(index1, index2); i; --i) {
 402         const TreeScope* child1 = chain1[--index1];
 403         const TreeScope* child2 = chain2[--index2];
 404         if (child1 != child2) {
 405             Node* shadowHost1 = child1->rootNode().parentOrShadowHostNode();
 406             Node* shadowHost2 = child2->rootNode().parentOrShadowHostNode();
 407             if (shadowHost1 != shadowHost2)
 408                 return shadowHost1->compareDocumentPositionInternal(shadowHost2, Node::TreatShadowTreesAsDisconnected);
 409
 410             for (const ShadowRoot* child = toShadowRoot(child2->rootNode()).olderShadowRoot(); child; child = child->olderShadowRoot())
 411                 if (child == child1)
 412                     return Node::DOCUMENT_POSITION_FOLLOWING;
 413
 414             return Node::DOCUMENT_POSITION_PRECEDING;
 415         }
 416     }
 417
 418     // There was no difference between the two parent chains, i.e., one was a subset of the other. The shorter
 419     // chain is the ancestor.
 420     return index1 < index2 ?
 421         Node::DOCUMENT_POSITION_FOLLOWING | Node::DOCUMENT_POSITION_CONTAINED_BY :
 422         Node::DOCUMENT_POSITION_PRECEDING | Node::DOCUMENT_POSITION_CONTAINS;
 423 }
 424
 425 const TreeScope* TreeScope::commonAncestorTreeScope(const TreeScope& other) const
 426 {
 427     Vector<const TreeScope*, 16> thisChain;
 428     for (const TreeScope* tree = this; tree; tree = tree->parentTreeScope())
 429         thisChain.append(tree);
 430
 431     Vector<const TreeScope*, 16> otherChain;
 432     for (const TreeScope* tree = &other; tree; tree = tree->parentTreeScope())
 433         otherChain.append(tree);
 434
 435     // Keep popping out the last elements of these chains until a mismatched pair is found. If |this| and |other|
 436     // belong to different documents, null will be returned.
 437     const TreeScope* lastAncestor = 0;
 438     while (!thisChain.isEmpty() && !otherChain.isEmpty() && thisChain.last() == otherChain.last()) {
 439         lastAncestor = thisChain.last();
 440         thisChain.removeLast();
 441         otherChain.removeLast();
 442     }
 443     return lastAncestor;
 444 }
 445
 446 TreeScope* TreeScope::commonAncestorTreeScope(TreeScope& other)
 447 {
 448     return const_cast<TreeScope*>(static_cast<const TreeScope&>(*this).commonAncestorTreeScope(other));
 449 }
 450
 451 static void listTreeScopes(Node* node, Vector<TreeScope*, 5>& treeScopes)
 452 {
 453     while (true) {
 454         treeScopes.append(&node->treeScope());
 455         Element* ancestor = node->shadowHost();
 456         if (!ancestor)
 457             break;
 458         node = ancestor;
 459     }
 460 }
 461
 462 TreeScope* commonTreeScope(Node* nodeA, Node* nodeB)
 463 {
 464     if (!nodeA || !nodeB)
 465         return 0;
 466
 467     if (nodeA->treeScope() == nodeB->treeScope())
 468         return &nodeA->treeScope();
 469
 470     Vector<TreeScope*, 5> treeScopesA;
 471     listTreeScopes(nodeA, treeScopesA);
 472
 473     Vector<TreeScope*, 5> treeScopesB;
 474     listTreeScopes(nodeB, treeScopesB);
 475
 476     size_t indexA = treeScopesA.size();
 477     size_t indexB = treeScopesB.size();
 478
 479     for (; indexA > 0 && indexB > 0 && treeScopesA[indexA - 1] == treeScopesB[indexB - 1]; --indexA, --indexB) { }
 480
 481     return treeScopesA[indexA] == treeScopesB[indexB] ? treeScopesA[indexA] : 0;
 482 }
 483
 484 #if SECURITY_ASSERT_ENABLED && !ENABLE(OILPAN)
 485 bool TreeScope::deletionHasBegun()
 486 {
 487     return rootNode().m_deletionHasBegun;
 488 }
 489
 490 void TreeScope::beginDeletion()
 491 {
 492     rootNode().m_deletionHasBegun = true;
 493 }
 494 #endif
 495
 496 #if !ENABLE(OILPAN)
 497 int TreeScope::refCount() const
 498 {
 499     return rootNode().refCount();
 500 }
 501 #endif
 502
 503 bool TreeScope::isInclusiveAncestorOf(const TreeScope& scope) const
 504 {
 505     for (const TreeScope* current = &scope; current; current = current->parentTreeScope()) {
 506         if (current == this)
 507             return true;
 508     }
 509     return false;
 510 }
 511
 512 Element* TreeScope::getElementByAccessKey(const String& key) const
 513 {
 514     if (key.isEmpty())
 515         return 0;
 516     Element* result = 0;
 517     Node& root = rootNode();
 518     for (Element* element = ElementTraversal::firstWithin(root); element; element = ElementTraversal::next(*element, &root)) {
 519         if (equalIgnoringCase(element->fastGetAttribute(accesskeyAttr), key))
 520             result = element;
 521         for (ShadowRoot* shadowRoot = element->youngestShadowRoot(); shadowRoot; shadowRoot = shadowRoot->olderShadowRoot()) {
 522             if (Element* shadowResult = shadowRoot->getElementByAccessKey(key))
 523                 result = shadowResult;
 524         }
 525     }
 526     return result;
 527 }
 528
 529 void TreeScope::setNeedsStyleRecalcForViewportUnits()
 530 {
 531     for (Element* element = ElementTraversal::firstWithin(rootNode()); element; element = ElementTraversal::nextIncludingPseudo(*element)) {
 532         for (ShadowRoot* root = element->youngestShadowRoot(); root; root = root->olderShadowRoot())
 533             root->setNeedsStyleRecalcForViewportUnits();
 534         RenderStyle* style = element->renderStyle();
 535         if (style && style->hasViewportUnits())
 536             element->setNeedsStyleRecalc(LocalStyleChange);
 537     }
 538 }
 539
 540 void TreeScope::trace(Visitor* visitor)
 541 {
 542     visitor->trace(m_rootNode);
 543     visitor->trace(m_document);
 544     visitor->trace(m_parentTreeScope);
 545     visitor->trace(m_idTargetObserverRegistry);
 546     visitor->trace(m_selection);
 547 }
 548
 549 } // namespace WebCore