Add fast path for tag#id selector queries

Source/core/dom/DocumentOrderedMap.cpp

 /*
  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 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:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Redistributions in binary form must reproduce the above
@@ skipping 47 matching lines @@
 }
 
 inline bool keyMatchesLabelForAttribute(StringImpl* key, Element* element)
 {
     return isHTMLLabelElement(element) && element->getAttribute(forAttr).impl() == key;
 }
 
 void DocumentOrderedMap::clear()
 {
     m_map.clear();
-    m_duplicateCounts.clear();
 }
 
 void DocumentOrderedMap::add(StringImpl* key, Element* element)
 {
     ASSERT(key);
     ASSERT(element);
 
-    if (!m_duplicateCounts.contains(key)) {
-        // Fast path. The key is not already in m_duplicateCounts, so we assume that it's
-        // also not already in m_map and try to add it. If that add succeeds, we're done.
-        Map::AddResult addResult = m_map.add(key, element);
-        if (addResult.isNewEntry)
-            return;
+    Map::AddResult addResult = m_map.add(key, MapEntry(element));
+    if (addResult.isNewEntry)
+        return;
 
-        // The add failed, so this key was already cached in m_map.
-        // There are multiple elements with this key. Remove the m_map
-        // cache for this key so get searches for it next time it is called.
-        m_map.remove(addResult.iterator);
-        m_duplicateCounts.add(key);
-    } else {
-        // There are multiple elements with this key. Remove the m_map
-        // cache for this key so get will search for it next time it is called.
-        Map::iterator cachedItem = m_map.find(key);
-        if (cachedItem != m_map.end()) {
-            m_map.remove(cachedItem);
-            m_duplicateCounts.add(key);
-        }
-    }
-
-    m_duplicateCounts.add(key);
+    MapEntry& entry = addResult.iterator->value;
+    ASSERT(entry.count);
+    entry.element = 0;
+    entry.count++;
+    entry.orderedList.clear();
 }
 
 void DocumentOrderedMap::remove(StringImpl* key, Element* element)
 {
     ASSERT(key);
     ASSERT(element);
 
-    Map::iterator cachedItem = m_map.find(key);
-    if (cachedItem != m_map.end() && cachedItem->value == element)
-        m_map.remove(cachedItem);
-    else
-        m_duplicateCounts.remove(key);
+    Map::iterator it = m_map.find(key);
+    ASSERT(it != m_map.end());

[esprehn, 2013/12/02 20:38:04]

The old code definitely didn't ASSERT this, why is there always a match now?

[Inactive, 2013/12/02 20:47:26]

This believe this is actually what caused the Clusterfuzz crash that abarth
mentioned (based on the backtrace). It is true, that the new code is stricter. I
am looking at the call sites right now to understand if this assumption is
correct or not.

[Inactive, 2013/12/02 21:24:42]

Yes, I confirmed this is indeed the source of the ClusterFuzz crash. I will keep
the if check here.

[Inactive, 2013/12/02 21:53:25]

Done.

+    MapEntry& entry = it->value;
+
+    ASSERT(entry.count);

[esprehn, 2013/12/02 20:38:04]

This doesn't seem right, why will find() always get a match?

+    if (entry.count == 1) {
+        ASSERT(!entry.element || entry.element == element);
+        m_map.remove(it);
+    } else {
+        if (entry.element == element)
+            entry.element = 0;

[Inactive, 2013/12/02 21:53:25]

Instead of resetting it unconditionally to 0 here, I use the second element in
entry.orderedList if available.

+        entry.count--;
+        entry.orderedList.clear(); // FIXME: Remove the element instead if there are only few items left.

[esprehn, 2013/12/02 20:38:04]

a few?

[Inactive, 2013/12/02 21:24:42]

I believe the idea on WebKit side was that it may not be worth removing the
element from the vector if it contains more than a few elements, likely because
finding the element in the vector is O(n) and removing it is also O(n)).

Considering this is a very specific and tricky optimization, I would propose to
simply remove the FIXME.

[Inactive, 2013/12/02 21:53:25]

Done.

+    }
 }
 
 template<bool keyMatches(StringImpl*, Element*)>
 inline Element* DocumentOrderedMap::get(StringImpl* key, const TreeScope* scope) const
 {
     ASSERT(key);
     ASSERT(scope);
 
-    Element* element = m_map.get(key);
-    if (element)
+    Map::iterator it = m_map.find(key);
+    if (it == m_map.end())
+        return 0;
+
+    MapEntry& entry = it->value;
+    ASSERT(entry.count);
+    if (entry.element)
+        return entry.element;
+
+    // We know there's at least one node that matches; iterate to find the first one.
+    for (Element* element = ElementTraversal::firstWithin(*scope->rootNode()); element; element = ElementTraversal::next(*element)) {
+        if (!keyMatches(key, element))
+            continue;
+        entry.element = element;
         return element;
-
-    if (m_duplicateCounts.contains(key)) {
-        // We know there's at least one node that matches; iterate to find the first one.
-        ASSERT(scope->rootNode());
-        for (element = ElementTraversal::firstWithin(*scope->rootNode()); element; element = ElementTraversal::next(*element)) {
-            if (!keyMatches(key, element))
-                continue;
-            m_duplicateCounts.remove(key);
-            m_map.set(key, element);
-            return element;
-        }
-        ASSERT_NOT_REACHED();
     }
-
+    ASSERT_NOT_REACHED();
     return 0;
 }
 
 Element* DocumentOrderedMap::getElementById(StringImpl* key, const TreeScope* scope) const
 {
     return get<keyMatchesId>(key, scope);
 }
 
+const Vector<Element*>* DocumentOrderedMap::getAllElementsById(StringImpl* key, const TreeScope* scope) const
+{
+    ASSERT(key);
+    ASSERT(scope);
+
+    Map::iterator it = m_map.find(key);
+    if (it == m_map.end())
+        return 0;
+
+    MapEntry& entry = it->value;
+    ASSERT(entry.count);
+
+    if (entry.orderedList.isEmpty()) {
+        entry.orderedList.reserveCapacity(entry.count);
+        for (Element* element = entry.element ? entry.element : ElementTraversal::firstWithin(*scope->rootNode()); element; element = ElementTraversal::next(*element)) {

[Inactive, 2013/12/02 21:53:25]

As loop condition, I now use "entry.orderedList.size() < entry.count", instead
of "element" to abort tree traversing as soon as we found the expected number of
elements.

I added an ASSERT(element) inside the loop instead as it should always be
non-null, as long as (entry.orderedList.size() < entry.count).

+            if (!keyMatchesId(key, element))
+                continue;
+            entry.orderedList.append(element);
+        }
+        ASSERT(entry.orderedList.size() == entry.count);
+    }
+
+    return &entry.orderedList;
+}
+
 Element* DocumentOrderedMap::getElementByMapName(StringImpl* key, const TreeScope* scope) const
 {
     return get<keyMatchesMapName>(key, scope);
 }
 
 Element* DocumentOrderedMap::getElementByLowercasedMapName(StringImpl* key, const TreeScope* scope) const
 {
     return get<keyMatchesLowercasedMapName>(key, scope);
 }
 
 Element* DocumentOrderedMap::getElementByLabelForAttribute(StringImpl* key, const TreeScope* scope) const
 {
     return get<keyMatchesLabelForAttribute>(key, scope);
 }
 
 } // namespace WebCore