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