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 "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 
     53 namespace WebCore {
     54 
     55 struct SameSizeAsTreeScope {
     56     virtual ~SameSizeAsTreeScope();
     57     void* pointers[8];
     58     int ints[1];
     59 };
     60 
     61 COMPILE_ASSERT(sizeof(TreeScope) == sizeof(SameSizeAsTreeScope), treescope_should_stay_small);
     62 
     63 using namespace HTMLNames;
     64 
     65 TreeScope::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 
     79 TreeScope::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 
     90 TreeScope::TreeScope()
     91     : m_rootNode(0)
     92     , m_documentScope(0)
     93     , m_parentTreeScope(0)
     94     , m_guardRefCount(0)
     95 {
     96 }
     97 
     98 TreeScope::~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 
    112 bool TreeScope::rootNodeHasTreeSharedParent() const
    113 {
    114     return rootNode()->hasTreeSharedParent();
    115 }
    116 
    117 void TreeScope::destroyTreeScopeData()
    118 {
    119     m_elementsById.clear();
    120     m_imageMapsByName.clear();
    121     m_labelsByForAttribute.clear();
    122 }
    123 
    124 void TreeScope::clearDocumentScope()
    125 {
    126     ASSERT(rootNode()->isDocumentNode());
    127     m_documentScope = 0;
    128 }
    129 
    130 void 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 
    144 Element* 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 
    153 void 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 
    161 void 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 
    169 Node* 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 
    183 void 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 
    193 void 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 
    203 HTMLMapElement* 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 
    216 RenderObject* 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 
    242 Element* 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 
    259 void TreeScope::addLabel(const AtomicString& forAttributeValue, HTMLLabelElement* element)
    260 {
    261     ASSERT(m_labelsByForAttribute);
    262     m_labelsByForAttribute->add(forAttributeValue.impl(), element);
    263 }
    264 
    265 void TreeScope::removeLabel(const AtomicString& forAttributeValue, HTMLLabelElement* element)
    266 {
    267     ASSERT(m_labelsByForAttribute);
    268     m_labelsByForAttribute->remove(forAttributeValue.impl(), element);
    269 }
    270 
    271 HTMLLabelElement* 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 
    293 DOMSelection* 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 
    308 Element* 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 
    332 bool TreeScope::applyAuthorStyles() const
    333 {
    334     return !rootNode()->isShadowRoot() || toShadowRoot(rootNode())->applyAuthorStyles();
    335 }
    336 
    337 void 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 
    347 static 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 
    356 Element* 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 
    379 unsigned 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 
    421 static 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 
    432 TreeScope* 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
    455 bool TreeScope::deletionHasBegun()
    456 {
    457     return rootNode() && rootNode()->m_deletionHasBegun;
    458 }
    459 
    460 void TreeScope::beginDeletion()
    461 {
    462     rootNode()->m_deletionHasBegun = true;
    463 }
    464 #endif
    465 
    466 int TreeScope::refCount() const
    467 {
    468     if (Node* root = rootNode())
    469         return root->refCount();
    470     return 0;
    471 }
    472 
    473 bool 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 
    482 Element* 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