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