src/third_party/WebKit/Source/core/dom/SelectorQuery.cpp

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