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 void TreeScope::adoptIfNeeded(Node& node)
 347 {
 348     ASSERT(this);
 349     ASSERT(!node.isDocumentNode());
 350 #if !ENABLE(OILPAN)
 351     ASSERT_WITH_SECURITY_IMPLICATION(!node.m_deletionHasBegun);
 352 #endif
 353     TreeScopeAdopter adopter(node, *this);
 354     if (adopter.needsScopeChange())
 355         adopter.execute();
 356 }
 357
 358 static Element* focusedFrameOwnerElement(Frame* focusedFrame, Frame* currentFrame)
 359 {
 360     for (; focusedFrame; focusedFrame = focusedFrame->tree().parent()) {
 361         if (focusedFrame->tree().parent() == currentFrame) {
 362             // FIXME: This won't work for OOPI.
 363             return focusedFrame->deprecatedLocalOwner();
 364         }
 365     }
 366     return 0;
 367 }
 368
 369 Element* TreeScope::adjustedFocusedElement() const
 370 {
 371     Document& document = rootNode().document();
 372     Element* element = document.focusedElement();
 373     if (!element && document.page())
 374         element = focusedFrameOwnerElement(document.page()->focusController().focusedFrame(), document.frame());
 375     if (!element)
 376         return 0;
 377
 378     EventPath eventPath(element);
 379     for (size_t i = 0; i < eventPath.size(); ++i) {
 380         if (eventPath[i].node() == rootNode()) {
 381             // eventPath.at(i).target() is one of the followings:
 382             // - InsertionPoint
 383             // - shadow host
 384             // - Document::focusedElement()
 385             // So, it's safe to do toElement().
 386             return toElement(eventPath[i].target()->toNode());
 387         }
 388     }
 389     return 0;
 390 }
 391
 392 unsigned short TreeScope::comparePosition(const TreeScope& otherScope) const
 393 {
 394     if (otherScope == this)
 395         return Node::DOCUMENT_POSITION_EQUIVALENT;
 396
 397     Vector<const TreeScope*, 16> chain1;
 398     Vector<const TreeScope*, 16> chain2;
 399     const TreeScope* current;
 400     for (current = this; current; current = current->parentTreeScope())
 401         chain1.append(current);
 402     for (current = &otherScope; current; current = current->parentTreeScope())
 403         chain2.append(current);
 404
 405     unsigned index1 = chain1.size();
 406     unsigned index2 = chain2.size();
 407     if (chain1[index1 - 1] != chain2[index2 - 1])
 408         return Node::DOCUMENT_POSITION_DISCONNECTED | Node::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC;
 409
 410     for (unsigned i = std::min(index1, index2); i; --i) {
 411         const TreeScope* child1 = chain1[--index1];
 412         const TreeScope* child2 = chain2[--index2];
 413         if (child1 != child2) {
 414             Node* shadowHost1 = child1->rootNode().parentOrShadowHostNode();
 415             Node* shadowHost2 = child2->rootNode().parentOrShadowHostNode();
 416             if (shadowHost1 != shadowHost2)
 417                 return shadowHost1->compareDocumentPosition(shadowHost2, Node::TreatShadowTreesAsDisconnected);
 418
 419             for (const ShadowRoot* child = toShadowRoot(child2->rootNode()).olderShadowRoot(); child; child = child->olderShadowRoot())
 420                 if (child == child1)
 421                     return Node::DOCUMENT_POSITION_FOLLOWING;
 422
 423             return Node::DOCUMENT_POSITION_PRECEDING;
 424         }
 425     }
 426
 427     // There was no difference between the two parent chains, i.e., one was a subset of the other. The shorter
 428     // chain is the ancestor.
 429     return index1 < index2 ?
 430         Node::DOCUMENT_POSITION_FOLLOWING | Node::DOCUMENT_POSITION_CONTAINED_BY :
 431         Node::DOCUMENT_POSITION_PRECEDING | Node::DOCUMENT_POSITION_CONTAINS;
 432 }
 433
 434 const TreeScope* TreeScope::commonAncestorTreeScope(const TreeScope& other) const
 435 {
 436     Vector<const TreeScope*, 16> thisChain;
 437     for (const TreeScope* tree = this; tree; tree = tree->parentTreeScope())
 438         thisChain.append(tree);
 439
 440     Vector<const TreeScope*, 16> otherChain;
 441     for (const TreeScope* tree = &other; tree; tree = tree->parentTreeScope())
 442         otherChain.append(tree);
 443
 444     // Keep popping out the last elements of these chains until a mismatched pair is found. If |this| and |other|
 445     // belong to different documents, null will be returned.
 446     const TreeScope* lastAncestor = 0;
 447     while (!thisChain.isEmpty() && !otherChain.isEmpty() && thisChain.last() == otherChain.last()) {
 448         lastAncestor = thisChain.last();
 449         thisChain.removeLast();
 450         otherChain.removeLast();
 451     }
 452     return lastAncestor;
 453 }
 454
 455 TreeScope* TreeScope::commonAncestorTreeScope(TreeScope& other)
 456 {
 457     return const_cast<TreeScope*>(static_cast<const TreeScope&>(*this).commonAncestorTreeScope(other));
 458 }
 459
 460 static void listTreeScopes(Node* node, Vector<TreeScope*, 5>& treeScopes)
 461 {
 462     while (true) {
 463         treeScopes.append(&node->treeScope());
 464         Element* ancestor = node->shadowHost();
 465         if (!ancestor)
 466             break;
 467         node = ancestor;
 468     }
 469 }
 470
 471 TreeScope* commonTreeScope(Node* nodeA, Node* nodeB)
 472 {
 473     if (!nodeA || !nodeB)
 474         return 0;
 475
 476     if (nodeA->treeScope() == nodeB->treeScope())
 477         return &nodeA->treeScope();
 478
 479     Vector<TreeScope*, 5> treeScopesA;
 480     listTreeScopes(nodeA, treeScopesA);
 481
 482     Vector<TreeScope*, 5> treeScopesB;
 483     listTreeScopes(nodeB, treeScopesB);
 484
 485     size_t indexA = treeScopesA.size();
 486     size_t indexB = treeScopesB.size();
 487
 488     for (; indexA > 0 && indexB > 0 && treeScopesA[indexA - 1] == treeScopesB[indexB - 1]; --indexA, --indexB) { }
 489
 490     return treeScopesA[indexA] == treeScopesB[indexB] ? treeScopesA[indexA] : 0;
 491 }
 492
 493 #if ENABLE(SECURITY_ASSERT) && !ENABLE(OILPAN)
 494 bool TreeScope::deletionHasBegun()
 495 {
 496     return rootNode().m_deletionHasBegun;
 497 }
 498
 499 void TreeScope::beginDeletion()
 500 {
 501     rootNode().m_deletionHasBegun = true;
 502 }
 503 #endif
 504
 505 #if !ENABLE(OILPAN)
 506 int TreeScope::refCount() const
 507 {
 508     return rootNode().refCount();
 509 }
 510 #endif
 511
 512 bool TreeScope::isInclusiveAncestorOf(const TreeScope& scope) const
 513 {
 514     for (const TreeScope* current = &scope; current; current = current->parentTreeScope()) {
 515         if (current == this)
 516             return true;
 517     }
 518     return false;
 519 }
 520
 521 Element* TreeScope::getElementByAccessKey(const String& key) const
 522 {
 523     if (key.isEmpty())
 524         return 0;
 525     Element* result = 0;
 526     Node& root = rootNode();
 527     for (Element* element = ElementTraversal::firstWithin(root); element; element = ElementTraversal::next(*element, &root)) {
 528         if (equalIgnoringCase(element->fastGetAttribute(accesskeyAttr), key))
 529             result = element;
 530         for (ShadowRoot* shadowRoot = element->youngestShadowRoot(); shadowRoot; shadowRoot = shadowRoot->olderShadowRoot()) {
 531             if (Element* shadowResult = shadowRoot->getElementByAccessKey(key))
 532                 result = shadowResult;
 533         }
 534     }
 535     return result;
 536 }
 537
 538 void TreeScope::setNeedsStyleRecalcForViewportUnits()
 539 {
 540     for (Element* element = ElementTraversal::firstWithin(rootNode()); element; element = ElementTraversal::nextIncludingPseudo(*element)) {
 541         for (ShadowRoot* root = element->youngestShadowRoot(); root; root = root->olderShadowRoot())
 542             root->setNeedsStyleRecalcForViewportUnits();
 543         RenderStyle* style = element->renderStyle();
 544         if (style && style->hasViewportUnits())
 545             element->setNeedsStyleRecalc(LocalStyleChange);
 546     }
 547 }
 548
 549 void TreeScope::trace(Visitor* visitor)
 550 {
 551     visitor->trace(m_rootNode);
 552     visitor->trace(m_document);
 553     visitor->trace(m_parentTreeScope);
 554     visitor->trace(m_idTargetObserverRegistry);
 555     visitor->trace(m_selection);
 556     visitor->trace(m_elementsById);
 557     visitor->trace(m_imageMapsByName);
 558     visitor->trace(m_labelsByForAttribute);
 559     visitor->trace(m_scopedStyleResolver);
 560 }
 561
 562 } // namespace blink