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/CSSSelectorList.h"
     32 #include "core/css/SelectorChecker.h"
     33 #include "core/css/SelectorCheckerFastPath.h"
     34 #include "core/css/SiblingTraversalStrategies.h"
     35 #include "core/dom/Document.h"
     36 #include "core/dom/NodeTraversal.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     explicit ClassRootNodeList(Node* rootNode, const AtomicString& className)
     68         : m_className(className)
     69         , m_rootNode(rootNode)
     70         , m_currentElement(nextInternal(ElementTraversal::firstWithin(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     explicit 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     PseudoId ignoreDynamicPseudo = NOPSEUDO;
    156     return selectorChecker.match(selectorCheckingContext, ignoreDynamicPseudo, DOMSiblingTraversalStrategy()) == SelectorChecker::SelectorMatches;
    157 }
    158 
    159 bool SelectorDataList::matches(Element* targetElement) const
    160 {
    161     ASSERT(targetElement);
    162 
    163     unsigned selectorCount = m_selectors.size();
    164     for (unsigned i = 0; i < selectorCount; ++i) {
    165         if (selectorMatches(m_selectors[i], targetElement, targetElement))
    166             return true;
    167     }
    168 
    169     return false;
    170 }
    171 
    172 PassRefPtr<NodeList> SelectorDataList::queryAll(Node* rootNode) const
    173 {
    174     Vector<RefPtr<Node> > result;
    175     executeQueryAll(rootNode, result);
    176     return StaticNodeList::adopt(result);
    177 }
    178 
    179 PassRefPtr<Element> SelectorDataList::queryFirst(Node* rootNode) const
    180 {
    181     return executeQueryFirst(rootNode);
    182 }
    183 
    184 static inline bool isTreeScopeRoot(Node* node)
    185 {
    186     ASSERT(node);
    187     return node->isDocumentNode() || node->isShadowRoot();
    188 }
    189 
    190 void SelectorDataList::collectElementsByClassName(Node* rootNode, const AtomicString& className, Vector<RefPtr<Node> >& traversalRoots) const
    191 {
    192     for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(element, rootNode)) {
    193         if (element->hasClass() && element->classNames().contains(className))
    194             traversalRoots.append(element);
    195     }
    196 }
    197 
    198 void SelectorDataList::collectElementsByTagName(Node* rootNode, const QualifiedName& tagName, Vector<RefPtr<Node> >& traversalRoots) const
    199 {
    200     for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(element, rootNode)) {
    201         if (SelectorChecker::tagMatches(element, tagName))
    202             traversalRoots.append(element);
    203     }
    204 }
    205 
    206 Element* SelectorDataList::findElementByClassName(Node* rootNode, const AtomicString& className) const
    207 {
    208     for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(element, rootNode)) {
    209         if (element->hasClass() && element->classNames().contains(className))
    210             return element;
    211     }
    212     return 0;
    213 }
    214 
    215 Element* SelectorDataList::findElementByTagName(Node* rootNode, const QualifiedName& tagName) const
    216 {
    217     for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(element, rootNode)) {
    218         if (SelectorChecker::tagMatches(element, tagName))
    219             return element;
    220     }
    221     return 0;
    222 }
    223 
    224 inline bool SelectorDataList::canUseFastQuery(Node* rootNode) const
    225 {
    226     return m_selectors.size() == 1 && rootNode->inDocument() && !rootNode->document()->inQuirksMode();
    227 }
    228 
    229 // If returns true, traversalRoots has the elements that may match the selector query.
    230 //
    231 // If returns false, traversalRoots has the rootNode parameter or descendants of rootNode representing
    232 // the subtree for which we can limit the querySelector traversal.
    233 //
    234 // The travseralRoots may be empty, regardless of the returned bool value, if this method finds that the selectors won't
    235 // match any element.
    236 PassOwnPtr<SimpleNodeList> SelectorDataList::findTraverseRoots(Node* rootNode, bool& matchTraverseRoots) const
    237 {
    238     // We need to return the matches in document order. To use id lookup while there is possiblity of multiple matches
    239     // we would need to sort the results. For now, just traverse the document in that case.
    240     ASSERT(rootNode);
    241     ASSERT(m_selectors.size() == 1);
    242     ASSERT(m_selectors[0].selector);
    243 
    244     bool isRightmostSelector = true;
    245     bool startFromParent = false;
    246 
    247     for (const CSSSelector* selector = m_selectors[0].selector; selector; selector = selector->tagHistory()) {
    248         if (selector->m_match == CSSSelector::Id && !rootNode->document()->containsMultipleElementsWithId(selector->value())) {
    249             Element* element = rootNode->treeScope()->getElementById(selector->value());
    250             if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(rootNode)))
    251                 rootNode = element;
    252             else if (!element || isRightmostSelector)
    253                 rootNode = 0;
    254             if (isRightmostSelector) {
    255                 matchTraverseRoots = true;
    256                 return adoptPtr(new SingleNodeList(rootNode));
    257             }
    258             if (startFromParent && rootNode)
    259                 rootNode = rootNode->parentNode();
    260 
    261             matchTraverseRoots = false;
    262             return adoptPtr(new SingleNodeList(rootNode));
    263         }
    264 
    265         // If we have both CSSSelector::Id and CSSSelector::Class at the same time, we should use Id
    266         // to find traverse root.
    267         if (!startFromParent && selector->m_match == CSSSelector::Class) {
    268             if (isRightmostSelector) {
    269                 matchTraverseRoots = true;
    270                 return adoptPtr(new ClassElementList(rootNode, selector->value()));
    271             }
    272             matchTraverseRoots = false;
    273             return adoptPtr(new ClassRootNodeList(rootNode, selector->value()));
    274         }
    275 
    276         if (selector->relation() == CSSSelector::SubSelector)
    277             continue;
    278         isRightmostSelector = false;
    279         if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent)
    280             startFromParent = true;
    281         else
    282             startFromParent = false;
    283     }
    284 
    285     matchTraverseRoots = false;
    286     return adoptPtr(new SingleNodeList(rootNode));
    287 }
    288 
    289 void SelectorDataList::executeSlowQueryAll(Node* rootNode, Vector<RefPtr<Node> >& matchedElements) const
    290 {
    291     for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(element, rootNode)) {
    292         for (unsigned i = 0; i < m_selectors.size(); ++i) {
    293             if (selectorMatches(m_selectors[i], element, rootNode)) {
    294                 matchedElements.append(element);
    295                 break;
    296             }
    297         }
    298     }
    299 }
    300 
    301 void SelectorDataList::executeQueryAll(Node* rootNode, Vector<RefPtr<Node> >& matchedElements) const
    302 {
    303     if (!canUseFastQuery(rootNode))
    304         return executeSlowQueryAll(rootNode, matchedElements);
    305 
    306     ASSERT(m_selectors.size() == 1);
    307     ASSERT(m_selectors[0].selector);
    308 
    309     const CSSSelector* firstSelector = m_selectors[0].selector;
    310 
    311     if (!firstSelector->tagHistory()) {
    312         // Fast path for querySelectorAll('#id'), querySelectorAl('.foo'), and querySelectorAll('div').
    313         switch (firstSelector->m_match) {
    314         case CSSSelector::Id:
    315             {
    316                 if (rootNode->document()->containsMultipleElementsWithId(firstSelector->value()))
    317                     break;
    318 
    319                 // Just the same as getElementById.
    320                 Element* element = rootNode->treeScope()->getElementById(firstSelector->value());
    321                 if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(rootNode)))
    322                     matchedElements.append(element);
    323                 return;
    324             }
    325         case CSSSelector::Class:
    326             return collectElementsByClassName(rootNode, firstSelector->value(), matchedElements);
    327         case CSSSelector::Tag:
    328             return collectElementsByTagName(rootNode, firstSelector->tagQName(), matchedElements);
    329         default:
    330             break; // If we need another fast path, add here.
    331         }
    332     }
    333 
    334     bool matchTraverseRoots;
    335     OwnPtr<SimpleNodeList> traverseRoots = findTraverseRoots(rootNode, matchTraverseRoots);
    336     if (traverseRoots->isEmpty())
    337         return;
    338 
    339     const SelectorData& selector = m_selectors[0];
    340     if (matchTraverseRoots) {
    341         while (!traverseRoots->isEmpty()) {
    342             Node* node = traverseRoots->next();
    343             Element* element = toElement(node);
    344             if (selectorMatches(selector, element, rootNode))
    345                 matchedElements.append(element);
    346         }
    347         return;
    348     }
    349 
    350     while (!traverseRoots->isEmpty()) {
    351         Node* traverseRoot = traverseRoots->next();
    352         for (Element* element = ElementTraversal::firstWithin(traverseRoot); element; element = ElementTraversal::next(element, traverseRoot)) {
    353             if (selectorMatches(selector, element, rootNode))
    354                 matchedElements.append(element);
    355         }
    356     }
    357 }
    358 
    359 // If matchTraverseRoot is true, the returned Node is the single Element that may match the selector query.
    360 //
    361 // If matchTraverseRoot is false, the returned Node is the rootNode parameter or a descendant of rootNode representing
    362 // the subtree for which we can limit the querySelector traversal.
    363 //
    364 // The returned Node may be 0, regardless of matchTraverseRoot, if this method finds that the selectors won't
    365 // match any element.
    366 Node* SelectorDataList::findTraverseRoot(Node* rootNode, bool& matchTraverseRoot) const
    367 {
    368     // We need to return the matches in document order. To use id lookup while there is possiblity of multiple matches
    369     // we would need to sort the results. For now, just traverse the document in that case.
    370     ASSERT(rootNode);
    371     ASSERT(m_selectors.size() == 1);
    372     ASSERT(m_selectors[0].selector);
    373 
    374     bool matchSingleNode = true;
    375     bool startFromParent = false;
    376     for (const CSSSelector* selector = m_selectors[0].selector; selector; selector = selector->tagHistory()) {
    377         if (selector->m_match == CSSSelector::Id && !rootNode->document()->containsMultipleElementsWithId(selector->value())) {
    378             Element* element = rootNode->treeScope()->getElementById(selector->value());
    379             if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(rootNode)))
    380                 rootNode = element;
    381             else if (!element || matchSingleNode)
    382                 rootNode = 0;
    383             if (matchSingleNode) {
    384                 matchTraverseRoot = true;
    385                 return rootNode;
    386             }
    387             if (startFromParent && rootNode)
    388                 rootNode = rootNode->parentNode();
    389             matchTraverseRoot = false;
    390             return rootNode;
    391         }
    392         if (selector->relation() == CSSSelector::SubSelector)
    393             continue;
    394         matchSingleNode = false;
    395         if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent)
    396             startFromParent = true;
    397         else
    398             startFromParent = false;
    399     }
    400     matchTraverseRoot = false;
    401     return rootNode;
    402 }
    403 
    404 Element* SelectorDataList::executeSlowQueryFirst(Node* rootNode) const
    405 {
    406     for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(element, rootNode)) {
    407         for (unsigned i = 0; i < m_selectors.size(); ++i) {
    408             if (selectorMatches(m_selectors[i], element, rootNode))
    409                 return element;
    410         }
    411     }
    412     return 0;
    413 }
    414 
    415 Element* SelectorDataList::executeQueryFirst(Node* rootNode) const
    416 {
    417     if (!canUseFastQuery(rootNode))
    418         return executeSlowQueryFirst(rootNode);
    419 
    420 
    421     const CSSSelector* selector = m_selectors[0].selector;
    422     ASSERT(selector);
    423 
    424     if (!selector->tagHistory()) {
    425         // Fast path for querySelector('#id'), querySelector('.foo'), and querySelector('div').
    426         // Many web developers uses querySelector with these simple selectors.
    427         switch (selector->m_match) {
    428         case CSSSelector::Id:
    429             {
    430                 if (rootNode->document()->containsMultipleElementsWithId(selector->value()))
    431                     break;
    432                 Element* element = rootNode->treeScope()->getElementById(selector->value());
    433                 return element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(rootNode)) ? element : 0;
    434             }
    435         case CSSSelector::Class:
    436             return findElementByClassName(rootNode, selector->value());
    437         case CSSSelector::Tag:
    438             return findElementByTagName(rootNode, selector->tagQName());
    439         default:
    440             break; // If we need another fast path, add here.
    441         }
    442     }
    443 
    444     bool matchTraverseRoot;
    445     Node* traverseRootNode = findTraverseRoot(rootNode, matchTraverseRoot);
    446     if (!traverseRootNode)
    447         return 0;
    448     if (matchTraverseRoot) {
    449         ASSERT(m_selectors.size() == 1);
    450         ASSERT(traverseRootNode->isElementNode());
    451         Element* element = toElement(traverseRootNode);
    452         return selectorMatches(m_selectors[0], element, rootNode) ? element : 0;
    453     }
    454 
    455     for (Element* element = ElementTraversal::firstWithin(traverseRootNode); element; element = ElementTraversal::next(element, traverseRootNode)) {
    456         if (selectorMatches(m_selectors[0], element, rootNode))
    457             return element;
    458     }
    459     return 0;
    460 }
    461 
    462 SelectorQuery::SelectorQuery(const CSSSelectorList& selectorList)
    463     : m_selectorList(selectorList)
    464 {
    465     m_selectors.initialize(m_selectorList);
    466 }
    467 
    468 bool SelectorQuery::matches(Element* element) const
    469 {
    470     return m_selectors.matches(element);
    471 }
    472 
    473 PassRefPtr<NodeList> SelectorQuery::queryAll(Node* rootNode) const
    474 {
    475     return m_selectors.queryAll(rootNode);
    476 }
    477 
    478 PassRefPtr<Element> SelectorQuery::queryFirst(Node* rootNode) const
    479 {
    480     return m_selectors.queryFirst(rootNode);
    481 }
    482 
    483 SelectorQuery* SelectorQueryCache::add(const AtomicString& selectors, Document* document, ExceptionState& es)
    484 {
    485     HashMap<AtomicString, OwnPtr<SelectorQuery> >::iterator it = m_entries.find(selectors);
    486     if (it != m_entries.end())
    487         return it->value.get();
    488 
    489     CSSParser parser(document);
    490     CSSSelectorList selectorList;
    491     parser.parseSelector(selectors, selectorList);
    492 
    493     if (!selectorList.first() || selectorList.hasInvalidSelector()) {
    494         es.throwDOMException(SyntaxError);
    495         return 0;
    496     }
    497 
    498     // throw a NamespaceError if the selector includes any namespace prefixes.
    499     if (selectorList.selectorsNeedNamespaceResolution()) {
    500         es.throwDOMException(NamespaceError);
    501         return 0;
    502     }
    503 
    504     const int maximumSelectorQueryCacheSize = 256;
    505     if (m_entries.size() == maximumSelectorQueryCacheSize)
    506         m_entries.remove(m_entries.begin());
    507 
    508     OwnPtr<SelectorQuery> selectorQuery = adoptPtr(new SelectorQuery(selectorList));
    509     SelectorQuery* rawSelectorQuery = selectorQuery.get();
    510     m_entries.add(selectors, selectorQuery.release());
    511     return rawSelectorQuery;
    512 }
    513 
    514 void SelectorQueryCache::invalidate()
    515 {
    516     m_entries.clear();
    517 }
    518 
    519 }
    520