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/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 54namespace WebCore { 55 56using namespace HTMLNames; 57 58TreeScope::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 74TreeScope::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 86TreeScope::~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 102TreeScope* TreeScope::olderShadowRootOrParentTreeScope() const 103{ 104 if (rootNode().isShadowRoot()) { 105 if (ShadowRoot* olderShadowRoot = toShadowRoot(rootNode()).olderShadowRoot()) 106 return olderShadowRoot; 107 } 108 return parentTreeScope(); 109} 110 111bool 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 120bool TreeScope::rootNodeHasTreeSharedParent() const 121{ 122 return rootNode().hasTreeSharedParent(); 123} 124 125#if !ENABLE(OILPAN) 126void TreeScope::destroyTreeScopeData() 127{ 128 m_elementsById.clear(); 129 m_imageMapsByName.clear(); 130 m_labelsByForAttribute.clear(); 131} 132#endif 133 134void 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 148Element* 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 157const 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 167void 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 175void 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 183Node* 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 197void 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 207void 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 217HTMLMapElement* 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 230HitTestResult 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 252Element* 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 267void TreeScope::addLabel(const AtomicString& forAttributeValue, HTMLLabelElement* element) 268{ 269 ASSERT(m_labelsByForAttribute); 270 m_labelsByForAttribute->add(forAttributeValue.impl(), element); 271} 272 273void TreeScope::removeLabel(const AtomicString& forAttributeValue, HTMLLabelElement* element) 274{ 275 ASSERT(m_labelsByForAttribute); 276 m_labelsByForAttribute->remove(forAttributeValue.impl(), element); 277} 278 279HTMLLabelElement* 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 297DOMSelection* 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 312Element* 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 332bool TreeScope::applyAuthorStyles() const 333{ 334 return rootNode().isDocumentNode(); 335} 336 337void 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 349static Element* focusedFrameOwnerElement(Frame* focusedFrame, Frame* currentFrame) 350{ 351 for (; focusedFrame; focusedFrame = focusedFrame->tree().parent()) { 352 if (focusedFrame->tree().parent() == currentFrame) { 353 // FIXME: This won't work for OOPI. 354 return focusedFrame->deprecatedLocalOwner(); 355 } 356 } 357 return 0; 358} 359 360Element* TreeScope::adjustedFocusedElement() const 361{ 362 Document& document = rootNode().document(); 363 Element* element = document.focusedElement(); 364 if (!element && document.page()) 365 element = focusedFrameOwnerElement(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 383unsigned 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 425const 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 446TreeScope* TreeScope::commonAncestorTreeScope(TreeScope& other) 447{ 448 return const_cast<TreeScope*>(static_cast<const TreeScope&>(*this).commonAncestorTreeScope(other)); 449} 450 451static 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 462TreeScope* 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) 485bool TreeScope::deletionHasBegun() 486{ 487 return rootNode().m_deletionHasBegun; 488} 489 490void TreeScope::beginDeletion() 491{ 492 rootNode().m_deletionHasBegun = true; 493} 494#endif 495 496#if !ENABLE(OILPAN) 497int TreeScope::refCount() const 498{ 499 return rootNode().refCount(); 500} 501#endif 502 503bool 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 512Element* 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 529void 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 540void 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 550