Home | History | Annotate | Download | only in dom 
      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
    563