DocumentOrderedMap doesn't need to have two HashMaps
authorrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 16 May 2013 18:04:13 +0000 (18:04 +0000)
committerrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 16 May 2013 18:04:13 +0000 (18:04 +0000)
https://bugs.webkit.org/show_bug.cgi?id=116167

Reviewed by Geoffrey Garen.

Previously, we had two hash maps: m_map and m_duplicateCounts in DocumentOrderedMap to keep track
of the first element and the number of duplicates for a given name. This patch simplifies this structure
by having a single hash map that contains both the pointer and the number of duplicates.

In addition, this patch fixes a regression introduced in r149652 that window and document name maps
were not updated for some elements inside a SVG use element, and makes use of the newly added list of
the matching elements in SelectorQuery.

* dom/DocumentOrderedMap.cpp:
(WebCore::DocumentOrderedMap::clear): Updated to use the new hash map.
(WebCore::DocumentOrderedMap::add): Ditto.
(WebCore::DocumentOrderedMap::remove): Ditto.
(WebCore::DocumentOrderedMap::get): Ditto.
(WebCore::DocumentOrderedMap::getAllElementsById): Added.

* dom/DocumentOrderedMap.h:

(WebCore::DocumentOrderedMap::MapEntry::MapEntry): Added.
(WebCore::DocumentOrderedMap::containsSingle): Updated to use new hash map.
(WebCore::DocumentOrderedMap::contains): Ditto.
(WebCore::DocumentOrderedMap::containsMultiple): Ditto.

* dom/Element.cpp:
(WebCore::Element::insertedInto): This function didn't add this element to window and document's name maps
if the element had already been inserted into a tree scope, and the current call was inserting an ancestor
of the tree scope into the document. We were exiting early per scope != treeScope().

Fixed the bug by splitting updateId into two functions updateIdForTreeScope and updateIdForDocument.
The former is called when this element is inserted into a new tree scope, and the latter is called when
this element is inserted into a HTML document even if it had already been inside some tree scope.

(WebCore::Element::removedFrom): This function didn't remove this element from tree scope's id maps if
the tree scope wasn't a document. Fixed the bug by simply checking that the removal happens beneath the
current tree scope.
(WebCore::Element::updateName):
(WebCore::Element::updateNameForTreeScope): Renamed from updateName.
(WebCore::Element::updateNameForDocument): Extracted from updateName.
(WebCore::Element::updateId):
(WebCore::Element::updateIdForTreeScope): Renamed from updateId.
(WebCore::Element::updateIdForDocument): Extracted from updateId.

* dom/Element.h:

* dom/SelectorQuery.cpp:
(WebCore::SelectorDataList::canUseIdLookup): Refactored to return the id subselector instead of checking if
the first subselector happens to be matching an id.
(WebCore::SelectorDataList::execute): Use the subselector canUseIdLookup returned. Also make use of newly
added getAllElementsById when there are multiple matching elements for a given id.

* dom/SelectorQuery.h:

* dom/TreeScope.cpp:
(WebCore::TreeScope::getAllElementsById): Added.

* dom/TreeScope.h:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@150187 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/ChangeLog
Source/WebCore/dom/DocumentOrderedMap.cpp
Source/WebCore/dom/DocumentOrderedMap.h
Source/WebCore/dom/Element.cpp
Source/WebCore/dom/Element.h
Source/WebCore/dom/SelectorQuery.cpp
Source/WebCore/dom/SelectorQuery.h
Source/WebCore/dom/TreeScope.cpp
Source/WebCore/dom/TreeScope.h

index 4618257fdbd7dea2566aab240ad671beef8a6181..0120ef542207e7ad3885de7466707add3e21dcb5 100644 (file)
@@ -1,3 +1,66 @@
+2013-05-15  Ryosuke Niwa  <rniwa@webkit.org>
+
+        DocumentOrderedMap doesn't need to have two HashMaps
+        https://bugs.webkit.org/show_bug.cgi?id=116167
+
+        Reviewed by Geoffrey Garen.
+
+        Previously, we had two hash maps: m_map and m_duplicateCounts in DocumentOrderedMap to keep track
+        of the first element and the number of duplicates for a given name. This patch simplifies this structure
+        by having a single hash map that contains both the pointer and the number of duplicates.
+
+        In addition, this patch fixes a regression introduced in r149652 that window and document name maps
+        were not updated for some elements inside a SVG use element, and makes use of the newly added list of
+        the matching elements in SelectorQuery.
+
+        * dom/DocumentOrderedMap.cpp:
+        (WebCore::DocumentOrderedMap::clear): Updated to use the new hash map.
+        (WebCore::DocumentOrderedMap::add): Ditto.
+        (WebCore::DocumentOrderedMap::remove): Ditto.
+        (WebCore::DocumentOrderedMap::get): Ditto.
+        (WebCore::DocumentOrderedMap::getAllElementsById): Added.
+
+        * dom/DocumentOrderedMap.h:
+
+        (WebCore::DocumentOrderedMap::MapEntry::MapEntry): Added.
+        (WebCore::DocumentOrderedMap::containsSingle): Updated to use new hash map.
+        (WebCore::DocumentOrderedMap::contains): Ditto.
+        (WebCore::DocumentOrderedMap::containsMultiple): Ditto.
+
+        * dom/Element.cpp:
+        (WebCore::Element::insertedInto): This function didn't add this element to window and document's name maps
+        if the element had already been inserted into a tree scope, and the current call was inserting an ancestor
+        of the tree scope into the document. We were exiting early per scope != treeScope().
+
+        Fixed the bug by splitting updateId into two functions updateIdForTreeScope and updateIdForDocument.
+        The former is called when this element is inserted into a new tree scope, and the latter is called when
+        this element is inserted into a HTML document even if it had already been inside some tree scope.
+
+        (WebCore::Element::removedFrom): This function didn't remove this element from tree scope's id maps if
+        the tree scope wasn't a document. Fixed the bug by simply checking that the removal happens beneath the
+        current tree scope.
+        (WebCore::Element::updateName):
+        (WebCore::Element::updateNameForTreeScope): Renamed from updateName.
+        (WebCore::Element::updateNameForDocument): Extracted from updateName.
+        (WebCore::Element::updateId):
+        (WebCore::Element::updateIdForTreeScope): Renamed from updateId.
+        (WebCore::Element::updateIdForDocument): Extracted from updateId.
+
+        * dom/Element.h:
+
+        * dom/SelectorQuery.cpp:
+        (WebCore::SelectorDataList::canUseIdLookup): Refactored to return the id subselector instead of checking if
+        the first subselector happens to be matching an id.
+        (WebCore::SelectorDataList::execute): Use the subselector canUseIdLookup returned. Also make use of newly
+        added getAllElementsById when there are multiple matching elements for a given id.
+
+        * dom/SelectorQuery.h:
+
+        * dom/TreeScope.cpp:
+        (WebCore::TreeScope::getAllElementsById): Added.
+
+        * dom/TreeScope.h:
+
 2013-05-15  Darin Adler  <darin@apple.com>
 
         [Mac] Make Clipboard::create functions for Mac platform independent by moving Pasteboard creation to Pasteboard functions
index e8e77f95fca46891c8214442cd854c312839b6a4..63c47d0c3cf9a4ea0cc79fb6e8c50126d8f8fd87 100644 (file)
@@ -80,7 +80,6 @@ inline bool keyMatchesDocumentNamedItem(AtomicStringImpl* key, Element* element)
 void DocumentOrderedMap::clear()
 {
     m_map.clear();
-    m_duplicateCounts.clear();
 }
 
 void DocumentOrderedMap::add(AtomicStringImpl* key, Element* element)
@@ -88,29 +87,15 @@ void DocumentOrderedMap::add(AtomicStringImpl* 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;
-
-        // 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);
-        }
-    }
+    Map::AddResult addResult = m_map.add(key, MapEntry(element));
+    if (addResult.isNewEntry)
+        return;
 
-    m_duplicateCounts.add(key);
+    MapEntry& entry = addResult.iterator->value;
+    ASSERT(entry.count);
+    entry.element = 0;
+    entry.count++;
+    entry.orderedList.clear();
 }
 
 void DocumentOrderedMap::remove(AtomicStringImpl* key, Element* element)
@@ -119,11 +104,20 @@ void DocumentOrderedMap::remove(AtomicStringImpl* key, Element* element)
     ASSERT(element);
 
     m_map.checkConsistency();
-    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());
+    MapEntry& entry = it->value;
+
+    ASSERT(entry.count);
+    if (entry.count == 1) {
+        ASSERT(!entry.element || entry.element == element);
+        m_map.remove(it);
+    } else {
+        if (entry.element == element)
+            entry.element = 0;
+        entry.count--;
+        entry.orderedList.clear(); // FIXME: Remove the element instead if there are only few items left.
+    }
 }
 
 template<bool keyMatches(AtomicStringImpl*, Element*)>
@@ -134,22 +128,23 @@ inline Element* DocumentOrderedMap::get(AtomicStringImpl* key, const TreeScope*
 
     m_map.checkConsistency();
 
-    Element* element = m_map.get(key);
-    if (element)
-        return element;
+    Map::iterator it = m_map.find(key);
+    if (it == m_map.end())
+        return 0;
 
-    if (m_duplicateCounts.contains(key)) {
-        // We know there's at least one node that matches; iterate to find the first one.
-        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();
-    }
+    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;
+    }
+    ASSERT_NOT_REACHED();
     return 0;
 }
 
@@ -188,4 +183,33 @@ Element* DocumentOrderedMap::getElementByDocumentNamedItem(AtomicStringImpl* key
     return get<keyMatchesDocumentNamedItem>(key, scope);
 }
 
+const Vector<Element*>* DocumentOrderedMap::getAllElementsById(AtomicStringImpl* key, const TreeScope* scope) const
+{
+    ASSERT(key);
+    ASSERT(scope);
+
+    m_map.checkConsistency();
+
+    Map::iterator it = m_map.find(key);
+    if (it == m_map.end())
+        return 0;
+
+    MapEntry& entry = it->value;
+    ASSERT(entry.count);
+    if (!entry.count)
+        return 0;
+
+    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)) {
+            if (!keyMatchesId(key, element))
+                continue;
+            entry.orderedList.append(element);
+        }
+        ASSERT(entry.orderedList.size() == entry.count);
+    }
+
+    return &entry.orderedList;
+}
+
 } // namespace WebCore
index 82961cc67a3efcca0c222491399a81bab2beb703..2e656a27951833b2d62fa98496f5647525a38a54 100644 (file)
@@ -33,6 +33,7 @@
 
 #include <wtf/HashCountedSet.h>
 #include <wtf/HashMap.h>
+#include <wtf/Vector.h>
 #include <wtf/text/AtomicStringImpl.h>
 
 namespace WebCore {
@@ -49,6 +50,7 @@ public:
     bool contains(AtomicStringImpl*) const;
     bool containsSingle(AtomicStringImpl*) const;
     bool containsMultiple(AtomicStringImpl*) const;
+
     // concrete instantiations of the get<>() method template
     Element* getElementById(AtomicStringImpl*, const TreeScope*) const;
     Element* getElementByName(AtomicStringImpl*, const TreeScope*) const;
@@ -58,33 +60,48 @@ public:
     Element* getElementByWindowNamedItem(AtomicStringImpl*, const TreeScope*) const;
     Element* getElementByDocumentNamedItem(AtomicStringImpl*, const TreeScope*) const;
 
+    const Vector<Element*>* getAllElementsById(AtomicStringImpl*, const TreeScope*) const;
+
     void checkConsistency() const;
 
 private:
     template<bool keyMatches(AtomicStringImpl*, Element*)> Element* get(AtomicStringImpl*, const TreeScope*) const;
 
-    typedef HashMap<AtomicStringImpl*, Element*> Map;
+    struct MapEntry {
+        MapEntry()
+            : element(0)
+            , count(0)
+        { }
+        explicit MapEntry(Element* firstElement)
+            : element(firstElement)
+            , count(1)
+        { }
+
+        Element* element;
+        unsigned count;
+        Vector<Element*> orderedList;
+    };
+
+    typedef HashMap<AtomicStringImpl*, MapEntry> Map;
 
-    // We maintain the invariant that m_duplicateCounts is the count of all elements with a given key
-    // excluding the one referenced in m_map, if any. This means it one less than the total count
-    // when the first node with a given key is cached, otherwise the same as the total count.
     mutable Map m_map;
-    mutable HashCountedSet<AtomicStringImpl*> m_duplicateCounts;
 };
 
 inline bool DocumentOrderedMap::containsSingle(AtomicStringImpl* id) const
 {
-    return (m_map.contains(id) ? 1 : 0) + m_duplicateCounts.count(id) == 1;
+    Map::const_iterator it = m_map.find(id);
+    return it != m_map.end() && it->value.count == 1;
 }
 
 inline bool DocumentOrderedMap::contains(AtomicStringImpl* id) const
 {
-    return m_map.contains(id) || m_duplicateCounts.contains(id);
+    return m_map.contains(id);
 }
 
 inline bool DocumentOrderedMap::containsMultiple(AtomicStringImpl* id) const
 {
-    return (m_map.contains(id) ? 1 : 0) + m_duplicateCounts.count(id) > 1;
+    Map::const_iterator it = m_map.find(id);
+    return it != m_map.end() && it->value.count > 1;
 }
 
 } // namespace WebCore
index df78cdfe6c3ef3d331ba3c7ac7c13755703816f9..af5ddd48a00f7f63783172926ebc2c3d786e3950 100644 (file)
@@ -1150,9 +1150,11 @@ bool Element::isInert() const
 
 Node::InsertionNotificationRequest Element::insertedInto(ContainerNode* insertionPoint)
 {
+    bool wasInDocument = inDocument();
     // need to do superclass processing first so inDocument() is true
     // by the time we reach updateId
     ContainerNode::insertedInto(insertionPoint);
+    ASSERT(!wasInDocument || inDocument());
 
 #if ENABLE(FULLSCREEN_API)
     if (containsFullScreenElement() && parentElement() && !parentElement()->containsFullScreenElement())
@@ -1171,21 +1173,30 @@ Node::InsertionNotificationRequest Element::insertedInto(ContainerNode* insertio
     if (hasRareData())
         elementRareData()->clearClassListValueForQuirksMode();
 
-    TreeScope* scope = insertionPoint->treeScope();
-    if (scope != treeScope())
-        return InsertionDone;
+    TreeScope* newScope = insertionPoint->treeScope();
+    HTMLDocument* newDocument = !wasInDocument && inDocument() && newScope->documentScope()->isHTMLDocument() ? toHTMLDocument(newScope->documentScope()) : 0;
+    if (newScope != treeScope())
+        newScope = 0;
 
     const AtomicString& idValue = getIdAttribute();
-    if (!idValue.isNull())
-        updateId(scope, nullAtom, idValue, AlwaysUpdateHTMLDocumentNamedItemMaps);
+    if (!idValue.isNull()) {
+        if (newScope)
+            updateIdForTreeScope(newScope, nullAtom, idValue);
+        if (newDocument)
+            updateIdForDocument(newDocument, nullAtom, idValue, AlwaysUpdateHTMLDocumentNamedItemMaps);
+    }
 
     const AtomicString& nameValue = getNameAttribute();
-    if (!nameValue.isNull())
-        updateName(scope, nullAtom, nameValue);
+    if (!nameValue.isNull()) {
+        if (newScope)
+            updateNameForTreeScope(newScope, nullAtom, nameValue);
+        if (newDocument)
+            updateNameForDocument(newDocument, nullAtom, nameValue);
+    }
 
-    if (hasTagName(labelTag)) {
-        if (scope->shouldCacheLabelsByForAttribute())
-            updateLabel(scope, nullAtom, fastGetAttribute(forAttr));
+    if (newScope && hasTagName(labelTag)) {
+        if (newScope->shouldCacheLabelsByForAttribute())
+            updateLabel(newScope, nullAtom, fastGetAttribute(forAttr));
     }
 
     return InsertionDone;
@@ -1217,19 +1228,31 @@ void Element::removedFrom(ContainerNode* insertionPoint)
 
     setSavedLayerScrollOffset(IntSize());
 
-    if (insertionPoint->isInTreeScope() && treeScope() == document()) {
+    if (insertionPoint->isInTreeScope()) {
+        TreeScope* oldScope = insertionPoint->treeScope();
+        HTMLDocument* oldDocument = inDocument() && oldScope->documentScope()->isHTMLDocument() ? toHTMLDocument(oldScope->documentScope()) : 0;
+        if (oldScope != treeScope())
+            oldScope = 0;
+
         const AtomicString& idValue = getIdAttribute();
-        if (!idValue.isNull())
-            updateId(insertionPoint->treeScope(), idValue, nullAtom, AlwaysUpdateHTMLDocumentNamedItemMaps);
+        if (!idValue.isNull()) {
+            if (oldScope)
+                updateIdForTreeScope(oldScope, idValue, nullAtom);
+            if (oldDocument)
+                updateIdForDocument(oldDocument, idValue, nullAtom, AlwaysUpdateHTMLDocumentNamedItemMaps);
+        }
 
         const AtomicString& nameValue = getNameAttribute();
-        if (!nameValue.isNull())
-            updateName(insertionPoint->treeScope(), nameValue, nullAtom);
+        if (!nameValue.isNull()) {
+            if (oldScope)
+                updateNameForTreeScope(oldScope, nameValue, nullAtom);
+            if (oldDocument)
+                updateNameForDocument(oldDocument, nameValue, nullAtom);
+        }
 
-        if (hasTagName(labelTag)) {
-            TreeScope* treeScope = insertionPoint->treeScope();
-            if (treeScope->shouldCacheLabelsByForAttribute())
-                updateLabel(treeScope, fastGetAttribute(forAttr), nullAtom);
+        if (oldScope && hasTagName(labelTag)) {
+            if (oldScope->shouldCacheLabelsByForAttribute())
+                updateLabel(oldScope, fastGetAttribute(forAttr), nullAtom);
         }
     }
 
@@ -2630,10 +2653,17 @@ inline void Element::updateName(const AtomicString& oldName, const AtomicString&
     if (oldName == newName)
         return;
 
-    updateName(treeScope(), oldName, newName);
+    updateNameForTreeScope(treeScope(), oldName, newName);
+
+    if (!inDocument())
+        return;
+    Document* htmlDocument = document();
+    if (!htmlDocument->isHTMLDocument())
+        return;
+    updateNameForDocument(toHTMLDocument(htmlDocument), oldName, newName);
 }
 
-void Element::updateName(TreeScope* scope, const AtomicString& oldName, const AtomicString& newName)
+void Element::updateNameForTreeScope(TreeScope* scope, const AtomicString& oldName, const AtomicString& newName)
 {
     ASSERT(isInTreeScope());
     ASSERT(oldName != newName);
@@ -2642,28 +2672,27 @@ void Element::updateName(TreeScope* scope, const AtomicString& oldName, const At
         scope->removeElementByName(oldName, this);
     if (!newName.isEmpty())
         scope->addElementByName(newName, this);
+}
 
-    if (!inDocument())
-        return;
-    
-    Document* ownerDocument = document();
-    if (!ownerDocument->isHTMLDocument())
-        return;
+void Element::updateNameForDocument(HTMLDocument* document, const AtomicString& oldName, const AtomicString& newName)
+{
+    ASSERT(inDocument());
+    ASSERT(oldName != newName);
 
     if (WindowNameCollection::nodeMatchesIfNameAttributeMatch(this)) {
         const AtomicString& id = WindowNameCollection::nodeMatchesIfIdAttributeMatch(this) ? getIdAttribute() : nullAtom;
         if (!oldName.isEmpty() && oldName != id)
-            toHTMLDocument(ownerDocument)->windowNamedItemMap().remove(oldName.impl(), this);
+            document->windowNamedItemMap().remove(oldName.impl(), this);
         if (!newName.isEmpty() && newName != id)
-            toHTMLDocument(ownerDocument)->windowNamedItemMap().add(newName.impl(), this);
+            document->windowNamedItemMap().add(newName.impl(), this);
     }
 
     if (DocumentNameCollection::nodeMatchesIfNameAttributeMatch(this)) {
         const AtomicString& id = DocumentNameCollection::nodeMatchesIfIdAttributeMatch(this) ? getIdAttribute() : nullAtom;
         if (!oldName.isEmpty() && oldName != id)
-            toHTMLDocument(ownerDocument)->documentNamedItemMap().remove(oldName.impl(), this);
+            document->documentNamedItemMap().remove(oldName.impl(), this);
         if (!newName.isEmpty() && newName != id)
-            toHTMLDocument(ownerDocument)->documentNamedItemMap().add(newName.impl(), this);
+            document->documentNamedItemMap().add(newName.impl(), this);
     }
 }
 
@@ -2675,10 +2704,17 @@ inline void Element::updateId(const AtomicString& oldId, const AtomicString& new
     if (oldId == newId)
         return;
 
-    updateId(treeScope(), oldId, newId, UpdateHTMLDocumentNamedItemMapsOnlyIfDiffersFromNameAttribute);
+    updateIdForTreeScope(treeScope(), oldId, newId);
+
+    if (!inDocument())
+        return;
+    Document* htmlDocument = document();
+    if (!htmlDocument->isHTMLDocument())
+        return;
+    updateIdForDocument(toHTMLDocument(htmlDocument), oldId, newId, UpdateHTMLDocumentNamedItemMapsOnlyIfDiffersFromNameAttribute);
 }
 
-void Element::updateId(TreeScope* scope, const AtomicString& oldId, const AtomicString& newId, HTMLDocumentNamedItemMapsUpdatingCondition condition)
+void Element::updateIdForTreeScope(TreeScope* scope, const AtomicString& oldId, const AtomicString& newId)
 {
     ASSERT(isInTreeScope());
     ASSERT(oldId != newId);
@@ -2687,28 +2723,27 @@ void Element::updateId(TreeScope* scope, const AtomicString& oldId, const Atomic
         scope->removeElementById(oldId, this);
     if (!newId.isEmpty())
         scope->addElementById(newId, this);
+}
 
-    if (!inDocument())
-        return;
-
-    Document* ownerDocument = document();
-    if (!ownerDocument->isHTMLDocument())
-        return;
+void Element::updateIdForDocument(HTMLDocument* document, const AtomicString& oldId, const AtomicString& newId, HTMLDocumentNamedItemMapsUpdatingCondition condition)
+{
+    ASSERT(inDocument());
+    ASSERT(oldId != newId);
 
     if (WindowNameCollection::nodeMatchesIfIdAttributeMatch(this)) {
         const AtomicString& name = condition == UpdateHTMLDocumentNamedItemMapsOnlyIfDiffersFromNameAttribute && WindowNameCollection::nodeMatchesIfNameAttributeMatch(this) ? getNameAttribute() : nullAtom;
         if (!oldId.isEmpty() && oldId != name)
-            toHTMLDocument(ownerDocument)->windowNamedItemMap().remove(oldId.impl(), this);
+            document->windowNamedItemMap().remove(oldId.impl(), this);
         if (!newId.isEmpty() && newId != name)
-            toHTMLDocument(ownerDocument)->windowNamedItemMap().add(newId.impl(), this);
+            document->windowNamedItemMap().add(newId.impl(), this);
     }
 
     if (DocumentNameCollection::nodeMatchesIfIdAttributeMatch(this)) {
         const AtomicString& name = condition == UpdateHTMLDocumentNamedItemMapsOnlyIfDiffersFromNameAttribute && DocumentNameCollection::nodeMatchesIfNameAttributeMatch(this) ? getNameAttribute() : nullAtom;
         if (!oldId.isEmpty() && oldId != name)
-            toHTMLDocument(ownerDocument)->documentNamedItemMap().remove(oldId.impl(), this);
+            document->documentNamedItemMap().remove(oldId.impl(), this);
         if (!newId.isEmpty() && newId != name)
-            toHTMLDocument(ownerDocument)->documentNamedItemMap().add(newId.impl(), this);
+            document->documentNamedItemMap().add(newId.impl(), this);
     }
 }
 
index 3bc7e8ef9f5078df99a4ea9c9fe8d54e13f7ad3d..f72a06237f397dd67e5cc3dc3075c0f6aec0edc8 100644 (file)
@@ -42,6 +42,7 @@ class DOMTokenList;
 class Element;
 class ElementRareData;
 class ElementShadow;
+class HTMLDocument;
 class ShareableElementData;
 class IntSize;
 class Locale;
@@ -674,11 +675,13 @@ private:
     void synchronizeAttribute(const QualifiedName&) const;
     void synchronizeAttribute(const AtomicString& localName) const;
 
+    void updateName(const AtomicString& oldName, const AtomicString& newName);
+    void updateNameForTreeScope(TreeScope*, const AtomicString& oldName, const AtomicString& newName);
+    void updateNameForDocument(HTMLDocument*, const AtomicString& oldName, const AtomicString& newName);
     void updateId(const AtomicString& oldId, const AtomicString& newId);
+    void updateIdForTreeScope(TreeScope*, const AtomicString& oldId, const AtomicString& newId);
     enum HTMLDocumentNamedItemMapsUpdatingCondition { AlwaysUpdateHTMLDocumentNamedItemMaps, UpdateHTMLDocumentNamedItemMapsOnlyIfDiffersFromNameAttribute };
-    void updateId(TreeScope*, const AtomicString& oldId, const AtomicString& newId, HTMLDocumentNamedItemMapsUpdatingCondition);
-    void updateName(const AtomicString& oldName, const AtomicString& newName);
-    void updateName(TreeScope*, const AtomicString& oldName, const AtomicString& newName);
+    void updateIdForDocument(HTMLDocument*, const AtomicString& oldId, const AtomicString& newId, HTMLDocumentNamedItemMapsUpdatingCondition);
     void updateLabel(TreeScope*, const AtomicString& oldForAttributeValue, const AtomicString& newForAttributeValue);
 
     void scrollByUnits(int units, ScrollGranularity);
index f4dc85fb88c4f7261e7fc093c71f82f79a8cd9d1..63efc13f86d00068875e90c70d02c37ebbe315d8 100644 (file)
@@ -98,21 +98,23 @@ PassRefPtr<Element> SelectorDataList::queryFirst(Node* rootNode) const
     return toElement(result.first().get());
 }
 
-bool SelectorDataList::canUseIdLookup(Node* rootNode) const
+const CSSSelector* SelectorDataList::selectorForIdLookup(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;
+        return 0;
     if (!rootNode->inDocument())
-        return false;
+        return 0;
     if (rootNode->document()->inQuirksMode())
-        return false;
-    if (rootNode->document()->containsMultipleElementsWithId(m_selectors[0].selector->value()))
-        return false;
-    return true;
+        return 0;
+    for (const CSSSelector* selector = m_selectors[0].selector; selector; selector = selector->tagHistory()) {
+        if (selector->m_match == CSSSelector::Id)
+            return selector;
+        if (selector->relation() != CSSSelector::SubSelector)
+            break;
+    }
+    return 0;
 }
 
 static inline bool isTreeScopeRoot(Node* node)
@@ -124,10 +126,24 @@ static inline bool isTreeScopeRoot(Node* node)
 template <bool firstMatchOnly>
 void SelectorDataList::execute(Node* rootNode, Vector<RefPtr<Node> >& matchedElements) const
 {
-    if (canUseIdLookup(rootNode)) {
+    if (const CSSSelector* idSelector = selectorForIdLookup(rootNode)) {
         ASSERT(m_selectors.size() == 1);
-        const CSSSelector* selector = m_selectors[0].selector;
-        Element* element = rootNode->treeScope()->getElementById(selector->value());
+        const AtomicString& idToMatch = idSelector->value();
+        if (UNLIKELY(rootNode->treeScope()->containsMultipleElementsWithId(idToMatch))) {
+            const Vector<Element*>* elements = rootNode->treeScope()->getAllElementsById(idToMatch);
+            ASSERT(elements);
+            size_t count = elements->size();
+            for (size_t i = 0; i < count; ++i) {
+                Element* element = elements->at(i);
+                if (selectorMatches(m_selectors[0], element, rootNode)) {
+                    matchedElements.append(element);
+                    if (firstMatchOnly)
+                        return;
+                }
+            }
+            return;
+        }
+        Element* element = rootNode->treeScope()->getElementById(idToMatch);
         if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(rootNode)))
             return;
         if (selectorMatches(m_selectors[0], element, rootNode))
index b798ad67e5d5ca4ad4f9f6af3d92e886459dee17..7b075a75a8a3288b67e90cae220a64b3608fa3e1 100644 (file)
@@ -58,7 +58,7 @@ private:
     };
 
     bool selectorMatches(const SelectorData&, Element*, const Node*) const;
-    bool canUseIdLookup(Node* rootNode) const;
+    const CSSSelector* selectorForIdLookup(Node* rootNode) const;
     template <bool firstMatchOnly>
     void execute(Node* rootNode, Vector<RefPtr<Node> >&) const;
 
index 445b5fcb5ccaba60fe8f513314a39d0f75847a02..3b8a85b058c7f24ac742b8888c46ad8aa13b467c 100644 (file)
@@ -149,6 +149,15 @@ Element* TreeScope::getElementById(const AtomicString& elementId) const
     return m_elementsById->getElementById(elementId.impl(), this);
 }
 
+const Vector<Element*>* TreeScope::getAllElementsById(const AtomicString& elementId) const
+{
+    if (elementId.isEmpty())
+        return 0;
+    if (!m_elementsById)
+        return 0;
+    return m_elementsById->getAllElementsById(elementId.impl(), this);
+}
+
 void TreeScope::addElementById(const AtomicString& elementId, Element* element)
 {
     if (!m_elementsById)
index 8b76e50e34f39a2e1496aff87234103fa7095d5f..d6be87fa16a44060f3551f2c9fd0a827d8612ad8 100644 (file)
@@ -56,6 +56,7 @@ public:
 
     Node* focusedNode();
     Element* getElementById(const AtomicString&) const;
+    const Vector<Element*>* getAllElementsById(const AtomicString&) const;
     bool hasElementWithId(AtomicStringImpl* id) const;
     bool containsMultipleElementsWithId(const AtomicString& id) const;
     void addElementById(const AtomicString& elementId, Element*);