Optimized querySelector(All) when selector contains #id.

Source/core/dom/SelectorQuery.cpp

 /*
  * Copyright (C) 2011 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  *
  * 1.  Redistributions of source code must retain the above copyright
  *     notice, this list of conditions and the following disclaimer.
  * 2.  Redistributions in binary form must reproduce the above copyright
@@ skipping 80 matching lines @@
 {
     Vector<RefPtr<Node> > result;
     execute<true>(rootNode, result);
     if (result.isEmpty())
         return 0;
     ASSERT(result.size() == 1);
     ASSERT(result.first()->isElementNode());
     return toElement(result.first().get());
 }
 
-bool SelectorDataList::canUseIdLookup(Node* rootNode) const
-{
-    // We need to return the matches in document order. To use id lookup while there is possiblity of multiple matches
-    // we would need to sort the results. For now, just traverse the document in that case.
-    if (m_selectors.size() != 1)
-        return false;
-    if (m_selectors[0].selector->m_match != CSSSelector::Id)
-        return false;
-    if (!rootNode->inDocument())
-        return false;
-    if (rootNode->document()->inQuirksMode())
-        return false;
-    if (rootNode->document()->containsMultipleElementsWithId(m_selectors[0].selector->value()))
-        return false;
-    return true;
-}
-
 static inline bool isTreeScopeRoot(Node* node)
 {
     ASSERT(node);
     return node->isDocumentNode() || node->isShadowRoot();
 }
 
+bool SelectorDataList::findTraverseRoot(Node*& rootNode) const

[Hajime Morrita, 2013/05/14 00:51:39]

Using in-out parameter is almost bad idea.
This could be cleaner by, for example, returning a struct or a pair which
indicates the result.

+{
+    // We need to return the matches in document order. To use id lookup while there is possiblity of multiple matches
+    // we would need to sort the results. For now, just traverse the document in that case.
+    if (m_selectors.size() != 1)
+        return false;
+    if (!rootNode->inDocument())
+        return false;
+    if (rootNode->document()->inQuirksMode())
+        return false;
+
+    bool matchSingleNode = true;
+    bool startFromParent = false;
+    for (const CSSSelector* selector = m_selectors[0].selector; selector; selector = selector->tagHistory()) {
+        if (selector->m_match == CSSSelector::Id && !rootNode->document()->containsMultipleElementsWithId(selector->value())) {
+            Element* element = rootNode->treeScope()->getElementById(selector->value());
+            if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(rootNode)))
+                rootNode = element;
+            else if (!element || matchSingleNode)
+                rootNode = 0;
+            if (matchSingleNode)
+                return true;
+            if (startFromParent && rootNode)
+                rootNode = rootNode->parentNode();
+            return false;
+        }
+        if (selector->relation() == CSSSelector::SubSelector)
+            continue;
+        matchSingleNode = false;
+        if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent)
+            startFromParent = true;
+        else
+            startFromParent = false;
+    }
+    return false;
+}
+
 template <bool firstMatchOnly>
 void SelectorDataList::execute(Node* rootNode, Vector<RefPtr<Node> >& matchedElements) const
 {
-    if (canUseIdLookup(rootNode)) {
+    Node* traverseRoot = rootNode;
+    bool matchSingleNode = findTraverseRoot(traverseRoot);
+    if (!traverseRoot)

[haraken, 2013/05/14 00:32:58]

You can put this above the findTraverseRoot() line.

+        return;
+    if (matchSingleNode) {
         ASSERT(m_selectors.size() == 1);
-        const CSSSelector* selector = m_selectors[0].selector;
-        Element* element = rootNode->treeScope()->getElementById(selector->value());
-        if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(rootNode)))
-            return;
+        Element* element = toElement(traverseRoot);

[haraken, 2013/05/14 00:32:58]

Don't you need to check if traverseRoot is an Element?

         if (selectorMatches(m_selectors[0], element, rootNode))
             matchedElements.append(element);
         return;
     }
 
     unsigned selectorCount = m_selectors.size();
 
-    Node* n = rootNode->firstChild();
+    Node* n = traverseRoot->firstChild();
     while (n) {
         if (n->isElementNode()) {
             Element* element = toElement(n);
             for (unsigned i = 0; i < selectorCount; ++i) {
                 if (selectorMatches(m_selectors[i], element, rootNode)) {
                     matchedElements.append(element);
                     if (firstMatchOnly)
                         return;
                     break;
                 }
             }
             if (element->firstChild()) {
                 n = element->firstChild();
                 continue;
             }
         }
         while (!n->nextSibling()) {
             n = n->parentNode();
-            if (n == rootNode)
+            if (n == traverseRoot)
                 return;
         }
         n = n->nextSibling();
     }
 }
 
 SelectorQuery::SelectorQuery(const CSSSelectorList& selectorList)
     : m_selectorList(selectorList)
 {
     m_selectors.initialize(m_selectorList);
@@ skipping 44 matching lines @@
     m_entries.add(selectors, selectorQuery.release());
     return rawSelectorQuery;
 }
 
 void SelectorQueryCache::invalidate()
 {
     m_entries.clear();
 }
 
 }