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