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