Home | History | Annotate | Download | only in dom 
      1 /*
      2  * Copyright (C) 2011 Apple Inc. All rights reserved.
      3  *
      4  * Redistribution and use in source and binary forms, with or without
      5  * modification, are permitted provided that the following conditions
      6  * are met:
      7  *
      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 AND ITS CONTRIBUTORS "AS IS" AND ANY
     15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
     16  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
     17  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
     18  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
     19  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
     20  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
     21  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     24  */
     25 
     26 #include "config.h"
     27 #include "core/dom/SelectorQuery.h"
     28 
     29 #include "bindings/v8/ExceptionState.h"
     30 #include "core/css/CSSParser.h"
     31 #include "core/css/SelectorChecker.h"
     32 #include "core/css/SelectorCheckerFastPath.h"
     33 #include "core/css/SiblingTraversalStrategies.h"
     34 #include "core/dom/Document.h"
     35 #include "core/dom/ElementTraversal.h"
     36 #include "core/dom/Node.h"
     37 #include "core/dom/StaticNodeList.h"
     38 
     39 namespace WebCore {
     40 
     41 class SimpleNodeList {
     42 public:
     43     virtual ~SimpleNodeList() { }
     44     virtual bool isEmpty() const = 0;
     45     virtual Node* next() = 0;
     46 };
     47 
     48 class SingleNodeList : public SimpleNodeList {
     49 public:
     50     explicit SingleNodeList(Node* rootNode) : m_currentNode(rootNode) { }
     51 
     52     bool isEmpty() const { return !m_currentNode; }
     53 
     54     Node* next()
     55     {
     56         Node* current = m_currentNode;
     57         m_currentNode = 0;
     58         return current;
     59     }
     60 
     61 private:
     62     Node* m_currentNode;
     63 };
     64 
     65 class ClassRootNodeList : public SimpleNodeList {
     66 public:
     67     ClassRootNodeList(Node& rootNode, const AtomicString& className)
     68         : m_className(className)
     69         , m_rootNode(rootNode)
     70         , m_currentElement(nextInternal(ElementTraversal::firstWithin(m_rootNode))) { }
     71 
     72     bool isEmpty() const { return !m_currentElement; }
     73 
     74     Node* next()
     75     {
     76         Node* current = m_currentElement;
     77         ASSERT(current);
     78         m_currentElement = nextInternal(ElementTraversal::nextSkippingChildren(*m_currentElement, &m_rootNode));
     79         return current;
     80     }
     81 
     82 private:
     83     Element* nextInternal(Element* element)
     84     {
     85         for (; element; element = ElementTraversal::next(*element, &m_rootNode)) {
     86             if (element->hasClass() && element->classNames().contains(m_className))
     87                 return element;
     88         }
     89         return 0;
     90     }
     91 
     92     const AtomicString& m_className;
     93     Node& m_rootNode;
     94     Element* m_currentElement;
     95 };
     96 
     97 class ClassElementList : public SimpleNodeList {
     98 public:
     99     ClassElementList(Node& rootNode, const AtomicString& className)
    100         : m_className(className)
    101         , m_rootNode(rootNode)
    102         , m_currentElement(nextInternal(ElementTraversal::firstWithin(rootNode))) { }
    103 
    104     bool isEmpty() const { return !m_currentElement; }
    105 
    106     Node* next()
    107     {
    108         Node* current = m_currentElement;
    109         ASSERT(current);
    110         m_currentElement = nextInternal(ElementTraversal::next(*m_currentElement, &m_rootNode));
    111         return current;
    112     }
    113 
    114 private:
    115     Element* nextInternal(Element* element)
    116     {
    117         for (; element; element = ElementTraversal::next(*element, &m_rootNode)) {
    118             if (element->hasClass() && element->classNames().contains(m_className))
    119                 return element;
    120         }
    121         return 0;
    122     }
    123 
    124     const AtomicString& m_className;
    125     Node& m_rootNode;
    126     Element* m_currentElement;
    127 };
    128 
    129 void SelectorDataList::initialize(const CSSSelectorList& selectorList)
    130 {
    131     ASSERT(m_selectors.isEmpty());
    132 
    133     unsigned selectorCount = 0;
    134     for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(selector))
    135         selectorCount++;
    136 
    137     m_selectors.reserveInitialCapacity(selectorCount);
    138     for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(selector))
    139         m_selectors.uncheckedAppend(SelectorData(selector, SelectorCheckerFastPath::canUse(selector)));
    140 }
    141 
    142 inline bool SelectorDataList::selectorMatches(const SelectorData& selectorData, Element& element, const Node& rootNode) const
    143 {
    144     if (selectorData.isFastCheckable && !element.isSVGElement()) {
    145         SelectorCheckerFastPath selectorCheckerFastPath(selectorData.selector, element);
    146         if (!selectorCheckerFastPath.matchesRightmostSelector(SelectorChecker::VisitedMatchDisabled))
    147             return false;
    148         return selectorCheckerFastPath.matches();
    149     }
    150 
    151     SelectorChecker selectorChecker(element.document(), SelectorChecker::QueryingRules);
    152     SelectorChecker::SelectorCheckingContext selectorCheckingContext(selectorData.selector, &element, SelectorChecker::VisitedMatchDisabled);
    153     selectorCheckingContext.behaviorAtBoundary = SelectorChecker::StaysWithinTreeScope;
    154     selectorCheckingContext.scope = !rootNode.isDocumentNode() && rootNode.isContainerNode() ? &toContainerNode(rootNode) : 0;
    155     return selectorChecker.match(selectorCheckingContext, DOMSiblingTraversalStrategy()) == SelectorChecker::SelectorMatches;
    156 }
    157 
    158 bool SelectorDataList::matches(Element& targetElement) const
    159 {
    160     unsigned selectorCount = m_selectors.size();
    161     for (unsigned i = 0; i < selectorCount; ++i) {
    162         if (selectorMatches(m_selectors[i], targetElement, targetElement))
    163             return true;
    164     }
    165 
    166     return false;
    167 }
    168 
    169 PassRefPtr<NodeList> SelectorDataList::queryAll(Node& rootNode) const
    170 {
    171     Vector<RefPtr<Node> > result;
    172     executeQueryAll(rootNode, result);
    173     return StaticNodeList::adopt(result);
    174 }
    175 
    176 PassRefPtr<Element> SelectorDataList::queryFirst(Node& rootNode) const
    177 {
    178     return executeQueryFirst(rootNode);
    179 }
    180 
    181 void SelectorDataList::collectElementsByClassName(Node& rootNode, const AtomicString& className, Vector<RefPtr<Node> >& traversalRoots) const
    182 {
    183     for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) {
    184         if (element->hasClass() && element->classNames().contains(className))
    185             traversalRoots.append(element);
    186     }
    187 }
    188 
    189 void SelectorDataList::collectElementsByTagName(Node& rootNode, const QualifiedName& tagName, Vector<RefPtr<Node> >& traversalRoots) const
    190 {
    191     for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) {
    192         if (SelectorChecker::tagMatches(*element, tagName))
    193             traversalRoots.append(element);
    194     }
    195 }
    196 
    197 Element* SelectorDataList::findElementByClassName(Node& rootNode, const AtomicString& className) const
    198 {
    199     for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) {
    200         if (element->hasClass() && element->classNames().contains(className))
    201             return element;
    202     }
    203     return 0;
    204 }
    205 
    206 Element* SelectorDataList::findElementByTagName(Node& rootNode, const QualifiedName& tagName) const
    207 {
    208     for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) {
    209         if (SelectorChecker::tagMatches(*element, tagName))
    210             return element;
    211     }
    212     return 0;
    213 }
    214 
    215 inline bool SelectorDataList::canUseFastQuery(const Node& rootNode) const
    216 {
    217     return m_selectors.size() == 1 && rootNode.inDocument() && !rootNode.document().inQuirksMode();
    218 }
    219 
    220 inline bool ancestorHasClassName(Node& rootNode, const AtomicString& className)
    221 {
    222     if (!rootNode.isElementNode())
    223         return false;
    224 
    225     for (Element* element = &toElement(rootNode); element; element = element->parentElement()) {
    226         if (element->hasClass() && element->classNames().contains(className))
    227             return true;
    228     }
    229     return false;
    230 }
    231 
    232 
    233 // If returns true, traversalRoots has the elements that may match the selector query.
    234 //
    235 // If returns false, traversalRoots has the rootNode parameter or descendants of rootNode representing
    236 // the subtree for which we can limit the querySelector traversal.
    237 //
    238 // The travseralRoots may be empty, regardless of the returned bool value, if this method finds that the selectors won't
    239 // match any element.
    240 PassOwnPtr<SimpleNodeList> SelectorDataList::findTraverseRoots(Node& rootNode, bool& matchTraverseRoots) const
    241 {
    242     // We need to return the matches in document order. To use id lookup while there is possiblity of multiple matches
    243     // we would need to sort the results. For now, just traverse the document in that case.
    244     ASSERT(m_selectors.size() == 1);
    245     ASSERT(m_selectors[0].selector);
    246 
    247     bool isRightmostSelector = true;
    248     bool startFromParent = false;
    249 
    250     for (const CSSSelector* selector = m_selectors[0].selector; selector; selector = selector->tagHistory()) {
    251         if (selector->m_match == CSSSelector::Id && !rootNode.document().containsMultipleElementsWithId(selector->value())) {
    252             Element* element = rootNode.treeScope().getElementById(selector->value());
    253             Node* adjustedNode = &rootNode;
    254             if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
    255                 adjustedNode = element;
    256             else if (!element || isRightmostSelector)
    257                 adjustedNode = 0;
    258             if (isRightmostSelector) {
    259                 matchTraverseRoots = true;
    260                 return adoptPtr(new SingleNodeList(adjustedNode));
    261             }
    262             if (startFromParent && adjustedNode)
    263                 adjustedNode = adjustedNode->parentNode();
    264 
    265             matchTraverseRoots = false;
    266             return adoptPtr(new SingleNodeList(adjustedNode));
    267         }
    268 
    269         // If we have both CSSSelector::Id and CSSSelector::Class at the same time, we should use Id
    270         // to find traverse root.
    271         if (!startFromParent && selector->m_match == CSSSelector::Class) {
    272             if (isRightmostSelector) {
    273                 matchTraverseRoots = true;
    274                 return adoptPtr(new ClassElementList(rootNode, selector->value()));
    275             }
    276             matchTraverseRoots = false;
    277             // Since there exists some ancestor element which has the class name, we need to see all children of rootNode.
    278             if (ancestorHasClassName(rootNode, selector->value()))
    279                 return adoptPtr(new SingleNodeList(&rootNode));
    280 
    281             return adoptPtr(new ClassRootNodeList(rootNode, selector->value()));
    282         }
    283 
    284         if (selector->relation() == CSSSelector::SubSelector)
    285             continue;
    286         isRightmostSelector = false;
    287         if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent)
    288             startFromParent = true;
    289         else
    290             startFromParent = false;
    291     }
    292 
    293     matchTraverseRoots = false;
    294     return adoptPtr(new SingleNodeList(&rootNode));
    295 }
    296 
    297 void SelectorDataList::executeSlowQueryAll(Node& rootNode, Vector<RefPtr<Node> >& matchedElements) const
    298 {
    299     for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) {
    300         for (unsigned i = 0; i < m_selectors.size(); ++i) {
    301             if (selectorMatches(m_selectors[i], *element, rootNode)) {
    302                 matchedElements.append(element);
    303                 break;
    304             }
    305         }
    306     }
    307 }
    308 
    309 void SelectorDataList::executeQueryAll(Node& rootNode, Vector<RefPtr<Node> >& matchedElements) const
    310 {
    311     if (!canUseFastQuery(rootNode))
    312         return executeSlowQueryAll(rootNode, matchedElements);
    313 
    314     ASSERT(m_selectors.size() == 1);
    315     ASSERT(m_selectors[0].selector);
    316 
    317     const CSSSelector* firstSelector = m_selectors[0].selector;
    318 
    319     if (!firstSelector->tagHistory()) {
    320         // Fast path for querySelectorAll('#id'), querySelectorAl('.foo'), and querySelectorAll('div').
    321         switch (firstSelector->m_match) {
    322         case CSSSelector::Id:
    323             {
    324                 if (rootNode.document().containsMultipleElementsWithId(firstSelector->value()))
    325                     break;
    326 
    327                 // Just the same as getElementById.
    328                 Element* element = rootNode.treeScope().getElementById(firstSelector->value());
    329                 if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
    330                     matchedElements.append(element);
    331                 return;
    332             }
    333         case CSSSelector::Class:
    334             return collectElementsByClassName(rootNode, firstSelector->value(), matchedElements);
    335         case CSSSelector::Tag:
    336             return collectElementsByTagName(rootNode, firstSelector->tagQName(), matchedElements);
    337         default:
    338             break; // If we need another fast path, add here.
    339         }
    340     }
    341 
    342     bool matchTraverseRoots;
    343     OwnPtr<SimpleNodeList> traverseRoots = findTraverseRoots(rootNode, matchTraverseRoots);
    344     if (traverseRoots->isEmpty())
    345         return;
    346 
    347     const SelectorData& selector = m_selectors[0];
    348     if (matchTraverseRoots) {
    349         while (!traverseRoots->isEmpty()) {
    350             Node& node = *traverseRoots->next();
    351             Element& element = toElement(node);
    352             if (selectorMatches(selector, element, rootNode))
    353                 matchedElements.append(&element);
    354         }
    355         return;
    356     }
    357 
    358     while (!traverseRoots->isEmpty()) {
    359         Node* traverseRoot = traverseRoots->next();
    360         ASSERT(traverseRoot);
    361         for (Element* element = ElementTraversal::firstWithin(*traverseRoot); element; element = ElementTraversal::next(*element, traverseRoot)) {
    362             if (selectorMatches(selector, *element, rootNode))
    363                 matchedElements.append(element);
    364         }
    365     }
    366 }
    367 
    368 // If matchTraverseRoot is true, the returned Node is the single Element that may match the selector query.
    369 //
    370 // If matchTraverseRoot is false, the returned Node is the rootNode parameter or a descendant of rootNode representing
    371 // the subtree for which we can limit the querySelector traversal.
    372 //
    373 // The returned Node may be 0, regardless of matchTraverseRoot, if this method finds that the selectors won't
    374 // match any element.
    375 Node* SelectorDataList::findTraverseRoot(Node& rootNode, bool& matchTraverseRoot) const
    376 {
    377     // We need to return the matches in document order. To use id lookup while there is possiblity of multiple matches
    378     // we would need to sort the results. For now, just traverse the document in that case.
    379     ASSERT(m_selectors.size() == 1);
    380     ASSERT(m_selectors[0].selector);
    381 
    382     bool matchSingleNode = true;
    383     bool startFromParent = false;
    384     for (const CSSSelector* selector = m_selectors[0].selector; selector; selector = selector->tagHistory()) {
    385         if (selector->m_match == CSSSelector::Id && !rootNode.document().containsMultipleElementsWithId(selector->value())) {
    386             Element* element = rootNode.treeScope().getElementById(selector->value());
    387             Node* adjustedRootNode = &rootNode;
    388             if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
    389                 adjustedRootNode = element;
    390             else if (!element || matchSingleNode)
    391                 adjustedRootNode = 0;
    392             if (matchSingleNode) {
    393                 matchTraverseRoot = true;
    394                 return adjustedRootNode;
    395             }
    396             if (startFromParent && adjustedRootNode)
    397                 adjustedRootNode = adjustedRootNode->parentNode();
    398             matchTraverseRoot = false;
    399             return adjustedRootNode;
    400         }
    401         if (selector->relation() == CSSSelector::SubSelector)
    402             continue;
    403         matchSingleNode = false;
    404         if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent)
    405             startFromParent = true;
    406         else
    407             startFromParent = false;
    408     }
    409     matchTraverseRoot = false;
    410     return &rootNode;
    411 }
    412 
    413 Element* SelectorDataList::executeSlowQueryFirst(Node& rootNode) const
    414 {
    415     for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) {
    416         for (unsigned i = 0; i < m_selectors.size(); ++i) {
    417             if (selectorMatches(m_selectors[i], *element, rootNode))
    418                 return element;
    419         }
    420     }
    421     return 0;
    422 }
    423 
    424 Element* SelectorDataList::executeQueryFirst(Node& rootNode) const
    425 {
    426     if (!canUseFastQuery(rootNode))
    427         return executeSlowQueryFirst(rootNode);
    428 
    429 
    430     const CSSSelector* selector = m_selectors[0].selector;
    431     ASSERT(selector);
    432 
    433     if (!selector->tagHistory()) {
    434         // Fast path for querySelector('#id'), querySelector('.foo'), and querySelector('div').
    435         // Many web developers uses querySelector with these simple selectors.
    436         switch (selector->m_match) {
    437         case CSSSelector::Id:
    438             {
    439                 if (rootNode.document().containsMultipleElementsWithId(selector->value()))
    440                     break;
    441                 Element* element = rootNode.treeScope().getElementById(selector->value());
    442                 return element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)) ? element : 0;
    443             }
    444         case CSSSelector::Class:
    445             return findElementByClassName(rootNode, selector->value());
    446         case CSSSelector::Tag:
    447             return findElementByTagName(rootNode, selector->tagQName());
    448         default:
    449             break; // If we need another fast path, add here.
    450         }
    451     }
    452 
    453     bool matchTraverseRoot;
    454     Node* traverseRootNode = findTraverseRoot(rootNode, matchTraverseRoot);
    455     if (!traverseRootNode)
    456         return 0;
    457     if (matchTraverseRoot) {
    458         ASSERT(m_selectors.size() == 1);
    459         ASSERT(traverseRootNode->isElementNode());
    460         Element& element = toElement(*traverseRootNode);
    461         return selectorMatches(m_selectors[0], element, rootNode) ? &element : 0;
    462     }
    463 
    464     for (Element* element = ElementTraversal::firstWithin(*traverseRootNode); element; element = ElementTraversal::next(*element, traverseRootNode)) {
    465         if (selectorMatches(m_selectors[0], *element, rootNode))
    466             return element;
    467     }
    468     return 0;
    469 }
    470 
    471 SelectorQuery::SelectorQuery(const CSSSelectorList& selectorList)
    472     : m_selectorList(selectorList)
    473 {
    474     m_selectors.initialize(m_selectorList);
    475 }
    476 
    477 bool SelectorQuery::matches(Element& element) const
    478 {
    479     return m_selectors.matches(element);
    480 }
    481 
    482 PassRefPtr<NodeList> SelectorQuery::queryAll(Node& rootNode) const
    483 {
    484     return m_selectors.queryAll(rootNode);
    485 }
    486 
    487 PassRefPtr<Element> SelectorQuery::queryFirst(Node& rootNode) const
    488 {
    489     return m_selectors.queryFirst(rootNode);
    490 }
    491 
    492 SelectorQuery* SelectorQueryCache::add(const AtomicString& selectors, const Document& document, ExceptionState& exceptionState)
    493 {
    494     HashMap<AtomicString, OwnPtr<SelectorQuery> >::iterator it = m_entries.find(selectors);
    495     if (it != m_entries.end())
    496         return it->value.get();
    497 
    498     CSSParser parser(document);
    499     CSSSelectorList selectorList;
    500     parser.parseSelector(selectors, selectorList);
    501 
    502     if (!selectorList.first()) {
    503         exceptionState.throwDOMException(SyntaxError, "'" + selectors + "' is not a valid selector.");
    504         return 0;
    505     }
    506 
    507     // throw a NamespaceError if the selector includes any namespace prefixes.
    508     if (selectorList.selectorsNeedNamespaceResolution()) {
    509         exceptionState.throwDOMException(NamespaceError, "'" + selectors + "' contains namespaces, which are not supported.");
    510         return 0;
    511     }
    512 
    513     const unsigned maximumSelectorQueryCacheSize = 256;
    514     if (m_entries.size() == maximumSelectorQueryCacheSize)
    515         m_entries.remove(m_entries.begin());
    516 
    517     OwnPtr<SelectorQuery> selectorQuery = adoptPtr(new SelectorQuery(selectorList));
    518     SelectorQuery* rawSelectorQuery = selectorQuery.get();
    519     m_entries.add(selectors, selectorQuery.release());
    520     return rawSelectorQuery;
    521 }
    522 
    523 void SelectorQueryCache::invalidate()
    524 {
    525     m_entries.clear();
    526 }
    527 
    528 }
    529