Optimized querySelector(All) when selector contains #id.

Source/core/dom/SelectorQuery.cpp

Index: Source/core/dom/SelectorQuery.cpp
diff --git a/Source/core/dom/SelectorQuery.cpp b/Source/core/dom/SelectorQuery.cpp
index 589a0f27c6d275aab90b9610a4abe3db6071bfe8..95a3926b5047625a791876685cbd98aeea5c136f 100644
--- a/Source/core/dom/SelectorQuery.cpp
+++ b/Source/core/dom/SelectorQuery.cpp
@@ -98,38 +98,59 @@ PassRefPtr<Element> SelectorDataList::queryFirst(Node* rootNode) const
     return toElement(result.first().get());
 }
 
-bool SelectorDataList::canUseIdLookup(Node* rootNode) const
+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 (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 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;
@@ -137,7 +158,7 @@ void SelectorDataList::execute(Node* rootNode, Vector<RefPtr<Node> >& matchedEle
 
     unsigned selectorCount = m_selectors.size();
 
-    Node* n = rootNode->firstChild();
+    Node* n = traverseRoot->firstChild();
     while (n) {
         if (n->isElementNode()) {
             Element* element = toElement(n);
@@ -156,7 +177,7 @@ void SelectorDataList::execute(Node* rootNode, Vector<RefPtr<Node> >& matchedEle
         }
         while (!n->nextSibling()) {
             n = n->parentNode();
-            if (n == rootNode)
+            if (n == traverseRoot)
                 return;
         }
         n = n->nextSibling();