2010-11-08 Darin Adler <darin@apple.com>
authordarin@apple.com <darin@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 8 Nov 2010 18:50:16 +0000 (18:50 +0000)
committerdarin@apple.com <darin@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 8 Nov 2010 18:50:16 +0000 (18:50 +0000)
        Reviewed by Alexey Proskuryakov.

        Incorrect image map used when multiple maps have the same name
        https://bugs.webkit.org/show_bug.cgi?id=49086

        Test: fast/images/image-map-multiple.html

        Factored out the code used to look up elements by id and reused it
        to look up maps by name. It handles multiple elements efficiently.

        * dom/Document.cpp:
        (WebCore::Document::DocumentOrderedMap::clear): Added.
        (WebCore::Document::DocumentOrderedMap::add): Added. Has code that
        was formerly in addElementById.
        (WebCore::Document::DocumentOrderedMap::remove): Added. Has code that
        was formerly in removeElementById.
        (WebCore::Document::DocumentOrderedMap::get): Added. Has code that
        was formerly in getElementById.
        (WebCore::keyMatchesId): Added.
        (WebCore::Document::getElementById): Use DocumentOrderedMap::get.
        (WebCore::Document::addElementById): Use DocumentOrderedMap::add.
        (WebCore::Document::removeElementById): Use DocumentOrderedMap::remove.
        (WebCore::Document::addImageMap): Use DocumentOrderedMap::add.
        (WebCore::Document::removeImageMap): Use DocumentOrderedMap::remove.
        (WebCore::keyMatchesMapName): Added.
        (WebCore::keyMatchesLowercasedMapName): Added.
        (WebCore::Document::getImageMap): Use DocumentOrderedMap::get.

        * dom/Document.h: Added DocumentOrderedMap class, used inside the
        Document class. Changed m_imageMapsByName to be a DocumentOrderedMap.
        Changed m_elementsById to be a DocumentOrderedMap. Eliminated
        m_duplicateIds, since DocumentOrderedMap now has that internally.
2010-11-08  Darin Adler  <darin@apple.com>

        Reviewed by Alexey Proskuryakov.

        Incorrect image map used when multiple maps have the same name
        https://bugs.webkit.org/show_bug.cgi?id=49086

        * fast/images/image-map-multiple-expected.txt: Added.
        * fast/images/image-map-multiple-xhtml-expected.txt: Added.
        * fast/images/image-map-multiple-xhtml.xhtml: Added.
        * fast/images/image-map-multiple.html: Added.

        * fast/images/zoomed-img-size-expected.txt: Removed property svn:executable.

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

LayoutTests/ChangeLog
LayoutTests/fast/images/image-map-multiple-expected.txt [new file with mode: 0644]
LayoutTests/fast/images/image-map-multiple-xhtml-expected.txt [new file with mode: 0644]
LayoutTests/fast/images/image-map-multiple-xhtml.xhtml [new file with mode: 0644]
LayoutTests/fast/images/image-map-multiple.html [new file with mode: 0644]
LayoutTests/fast/images/zoomed-img-size-expected.txt [changed mode: 0755->0644]
WebCore/ChangeLog
WebCore/dom/Document.cpp
WebCore/dom/Document.h

index ac500e0..2d17aaa 100644 (file)
@@ -1,3 +1,17 @@
+2010-11-08  Darin Adler  <darin@apple.com>
+
+        Reviewed by Alexey Proskuryakov.
+
+        Incorrect image map used when multiple maps have the same name
+        https://bugs.webkit.org/show_bug.cgi?id=49086
+
+        * fast/images/image-map-multiple-expected.txt: Added.
+        * fast/images/image-map-multiple-xhtml-expected.txt: Added.
+        * fast/images/image-map-multiple-xhtml.xhtml: Added.
+        * fast/images/image-map-multiple.html: Added.
+
+        * fast/images/zoomed-img-size-expected.txt: Removed property svn:executable.
+
 2010-11-08  Alexander Pavlov  <apavlov@chromium.org>
 
         Unreviewed, build fix from commit r71530.
diff --git a/LayoutTests/fast/images/image-map-multiple-expected.txt b/LayoutTests/fast/images/image-map-multiple-expected.txt
new file mode 100644 (file)
index 0000000..dc6a7d5
--- /dev/null
@@ -0,0 +1,10 @@
+This tests image map behavior when there are multiple maps with the same name.
+1: PASS: Hit the first map in the document.
+2: PASS: Hit the second map after the first was renamed.
+3: PASS: Hit the first map after it was renamed back.
+4: PASS: Hit the second map after the first was removed.
+5: PASS: Hit the first map after it was added back.
+6: PASS: Hit the first map after the second was removed.
+7: PASS: Hit the first map after the second was re-added.
+
diff --git a/LayoutTests/fast/images/image-map-multiple-xhtml-expected.txt b/LayoutTests/fast/images/image-map-multiple-xhtml-expected.txt
new file mode 100644 (file)
index 0000000..dc6a7d5
--- /dev/null
@@ -0,0 +1,10 @@
+This tests image map behavior when there are multiple maps with the same name.
+1: PASS: Hit the first map in the document.
+2: PASS: Hit the second map after the first was renamed.
+3: PASS: Hit the first map after it was renamed back.
+4: PASS: Hit the second map after the first was removed.
+5: PASS: Hit the first map after it was added back.
+6: PASS: Hit the first map after the second was removed.
+7: PASS: Hit the first map after the second was re-added.
+
diff --git a/LayoutTests/fast/images/image-map-multiple-xhtml.xhtml b/LayoutTests/fast/images/image-map-multiple-xhtml.xhtml
new file mode 100644 (file)
index 0000000..2f8efd8
--- /dev/null
@@ -0,0 +1,84 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
+<head>
+<script>
+
+var test = 1;
+var map1;
+var map2;
+var map3;
+
+function setResult(result)
+{
+    var message = "FAIL: Unexpected result: " + result;
+
+    if (test === 1) {
+        if (result === '1')
+            message = "PASS: Hit the first map in the document.";
+        map1.name = "anothername";
+    }
+    if (test === 2) {
+        if (result === '2')
+            message = "PASS: Hit the second map after the first was renamed.";
+        map1.name = "mapname";
+    }
+    if (test === 3) {
+        if (result === '1')
+            message = "PASS: Hit the first map after it was renamed back.";
+        map1.parentNode.removeChild(map1);
+    }
+    if (test === 4) {
+        if (result === '2')
+            message = "PASS: Hit the second map after the first was removed.";
+        map2.parentNode.insertBefore(map1, map2);
+    }
+    if (test === 5) {
+        if (result === '1')
+            message = "PASS: Hit the first map after it was added back.";
+        map2.parentNode.removeChild(map2);
+    }
+    if (test === 6) {
+        if (result === '1')
+            message = "PASS: Hit the first map after the second was removed.";
+        map3.parentNode.insertBefore(map2, map3);
+    }
+    if (test === 7) {
+        if (result === '1')
+            message = "PASS: Hit the first map after the second was re-added.";
+    }
+
+    document.getElementById("log").textContent += test + ": " + message + "\n";
+    ++test;
+}
+
+function runTest()
+{
+    map1 = document.getElementsByTagName("map")[0];
+    map2 = document.getElementsByTagName("map")[1];
+    map3 = document.getElementsByTagName("map")[2];
+
+    var numClicks = 7;
+    if (!window.eventSender) {
+        document.getElementById("log").textContent = "To run the test manually, click " + numClicks + " times in the image rectangle.\n";
+        return;
+    }
+    layoutTestController.dumpAsText();
+    eventSender.mouseMoveTo(50, 50);
+    for (var click = 0; numClicks > click; ++click) {
+        eventSender.mouseDown();
+        eventSender.mouseUp();
+    }
+}
+
+</script>
+</head>
+<body onload="runTest()">
+<map name="mapname"><area shape="rect" coords="0,0,100,100" onclick="setResult('1')" /></map>
+<map name="mapname"><area shape="rect" coords="0,0,100,100" onclick="setResult('2')" /></map>
+<map name="mapname"><area shape="rect" coords="0,0,100,100" onclick="setResult('3')" /></map>
+<img src="resources/green.jpg" border="20" width="100" height="100" usemap="mapname" ismap="ismap" onclick="setResult('img')" />
+<div>This tests image map behavior when there are multiple maps with the same name.</div>
+<pre id="log" />
+</body>
+</html>
diff --git a/LayoutTests/fast/images/image-map-multiple.html b/LayoutTests/fast/images/image-map-multiple.html
new file mode 100644 (file)
index 0000000..0fea520
--- /dev/null
@@ -0,0 +1,78 @@
+<script>
+
+var test = 1;
+var map1;
+var map2;
+var map3;
+
+function setResult(result)
+{
+    var message = "FAIL: Unexpected result: " + result;
+
+    if (test === 1) {
+        if (result === '1')
+            message = "PASS: Hit the first map in the document.";
+        map1.name = "anothername";
+    }
+    if (test === 2) {
+        if (result === '2')
+            message = "PASS: Hit the second map after the first was renamed.";
+        map1.name = "mapname";
+    }
+    if (test === 3) {
+        if (result === '1')
+            message = "PASS: Hit the first map after it was renamed back.";
+        map1.parentNode.removeChild(map1);
+    }
+    if (test === 4) {
+        if (result === '2')
+            message = "PASS: Hit the second map after the first was removed.";
+        map2.parentNode.insertBefore(map1, map2);
+    }
+    if (test === 5) {
+        if (result === '1')
+            message = "PASS: Hit the first map after it was added back.";
+        map2.parentNode.removeChild(map2);
+    }
+    if (test === 6) {
+        if (result === '1')
+            message = "PASS: Hit the first map after the second was removed.";
+        map3.parentNode.insertBefore(map2, map3);
+    }
+    if (test === 7) {
+        if (result === '1')
+            message = "PASS: Hit the first map after the second was re-added.";
+    }
+
+    document.getElementById("log").textContent += test + ": " + message + "\n";
+    ++test;
+}
+
+function runTest()
+{
+    map1 = document.getElementsByTagName("map")[0];
+    map2 = document.getElementsByTagName("map")[1];
+    map3 = document.getElementsByTagName("map")[2];
+
+    var numClicks = 7;
+    if (!window.eventSender) {
+        document.getElementById("log").textContent = "To run the test manually, click " + numClicks + " times in the image rectangle.\n";
+        return;
+    }
+    layoutTestController.dumpAsText();
+    eventSender.mouseMoveTo(50, 50);
+    for (var click = 0; click < numClicks; ++click) {
+        eventSender.mouseDown();
+        eventSender.mouseUp();
+    }
+}
+
+</script>
+<body onload="runTest()">
+<map name="mapName"><area shape=rect coords="0,0,100,100" onclick="setResult('1')"></map>
+<map name="mapname"><area shape=rect coords="0,0,100,100" onclick="setResult('2')"></map>
+<map name="mapname"><area shape=rect coords="0,0,100,100" onclick="setResult('3')"></map>
+<img src="resources/green.jpg" border=20 width=100 height=100 usemap="#mapname" ismap onclick="setResult('img')">
+<div>This tests image map behavior when there are multiple maps with the same name.</div>
+<pre id="log"></pre>
+</body>
index 0b82beb..d378e76 100644 (file)
@@ -1,3 +1,38 @@
+2010-11-08  Darin Adler  <darin@apple.com>
+
+        Reviewed by Alexey Proskuryakov.
+
+        Incorrect image map used when multiple maps have the same name
+        https://bugs.webkit.org/show_bug.cgi?id=49086
+
+        Test: fast/images/image-map-multiple.html
+
+        Factored out the code used to look up elements by id and reused it
+        to look up maps by name. It handles multiple elements efficiently.
+
+        * dom/Document.cpp:
+        (WebCore::Document::DocumentOrderedMap::clear): Added.
+        (WebCore::Document::DocumentOrderedMap::add): Added. Has code that
+        was formerly in addElementById.
+        (WebCore::Document::DocumentOrderedMap::remove): Added. Has code that
+        was formerly in removeElementById.
+        (WebCore::Document::DocumentOrderedMap::get): Added. Has code that
+        was formerly in getElementById.
+        (WebCore::keyMatchesId): Added.
+        (WebCore::Document::getElementById): Use DocumentOrderedMap::get.
+        (WebCore::Document::addElementById): Use DocumentOrderedMap::add.
+        (WebCore::Document::removeElementById): Use DocumentOrderedMap::remove.
+        (WebCore::Document::addImageMap): Use DocumentOrderedMap::add.
+        (WebCore::Document::removeImageMap): Use DocumentOrderedMap::remove.
+        (WebCore::keyMatchesMapName): Added.
+        (WebCore::keyMatchesLowercasedMapName): Added.
+        (WebCore::Document::getImageMap): Use DocumentOrderedMap::get.
+
+        * dom/Document.h: Added DocumentOrderedMap class, used inside the
+        Document class. Changed m_imageMapsByName to be a DocumentOrderedMap.
+        Changed m_elementsById to be a DocumentOrderedMap. Eliminated
+        m_duplicateIds, since DocumentOrderedMap now has that internally.
+
 2010-11-08  Alexey Proskuryakov  <ap@apple.com>
 
         Reviewed by Darin Adler.
index 8e6e033..61a6f1f 100644 (file)
@@ -212,8 +212,10 @@ using namespace HTMLNames;
 // for dual G5s. :)
 static const int cLayoutScheduleThreshold = 250;
 
-// Use 1 to represent the document's default form.
-static HTMLFormElement* const defaultForm = reinterpret_cast<HTMLFormElement*>(1);
+// These functions can't have internal linkage because they are used as template arguments.
+bool keyMatchesId(AtomicStringImpl*, Element*);
+bool keyMatchesMapName(AtomicStringImpl*, Element*);
+bool keyMatchesLowercasedMapName(AtomicStringImpl*, Element*);
 
 // DOM Level 2 says (letters added):
 //
@@ -481,6 +483,12 @@ Document::Document(Frame* frame, const KURL& url, bool isXHTML, bool isHTML, con
 #endif
 }
 
+inline void Document::DocumentOrderedMap::clear()
+{
+    m_map.clear();
+    m_duplicateCounts.clear();
+}
+
 void Document::removedLastRef()
 {
     ASSERT(!m_deletionHasBegun);
@@ -938,34 +946,89 @@ PassRefPtr<Element> Document::createElementNS(const String& namespaceURI, const
     return createElement(qName, false);
 }
 
-Element* Document::getElementById(const AtomicString& elementId) const
+inline void Document::DocumentOrderedMap::add(AtomicStringImpl* key, Element* element)
 {
-    if (elementId.isEmpty())
-        return 0;
+    ASSERT(key);
+    ASSERT(element);
 
-    m_elementsById.checkConsistency();
+    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.
+        pair<Map::iterator, bool> addResult = m_map.add(key, element);
+        if (addResult.second)
+            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.first);
+        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);
+        }
+    }
 
-    Element* element = m_elementsById.get(elementId.impl());
+    m_duplicateCounts.add(key);
+}
+
+inline void Document::DocumentOrderedMap::remove(AtomicStringImpl* key, Element* element)
+{
+    ASSERT(key);
+    ASSERT(element);
+
+    m_map.checkConsistency();
+    Map::iterator cachedItem = m_map.find(key);
+    if (cachedItem != m_map.end() && cachedItem->second == element)
+        m_map.remove(cachedItem);
+    else
+        m_duplicateCounts.remove(key);
+}
+
+template<bool keyMatches(AtomicStringImpl*, Element*)> inline Element* Document::DocumentOrderedMap::get(AtomicStringImpl* key, const Document* document) const
+{
+    ASSERT(key);
+
+    m_map.checkConsistency();
+
+    Element* element = m_map.get(key);
     if (element)
         return element;
 
-    if (m_duplicateIds.contains(elementId.impl())) {
-        // We know there's at least one node with this id, but we don't know what the first one is.
-        for (Node* n = traverseNextNode(); n; n = n->traverseNextNode()) {
-            if (n->isElementNode()) {
-                element = static_cast<Element*>(n);
-                if (element->hasID() && element->getIdAttribute() == elementId) {
-                    m_duplicateIds.remove(elementId.impl());
-                    m_elementsById.set(elementId.impl(), element);
-                    return element;
-                }
-            }
+    if (m_duplicateCounts.contains(key)) {
+        // We know there's at least one node that matches; iterate to find the first one.
+        for (Node* node = document->firstChild(); node; node = node->traverseNextNode()) {
+            if (!node->isElementNode())
+                continue;
+            element = static_cast<Element*>(node);
+            if (!keyMatches(key, element))
+                continue;
+            m_duplicateCounts.remove(key);
+            m_map.set(key, element);
+            return element;
         }
         ASSERT_NOT_REACHED();
     }
+
     return 0;
 }
 
+inline bool keyMatchesId(AtomicStringImpl* key, Element* element)
+{
+    return element->hasID() && element->getIdAttribute().impl() == key;
+}
+
+Element* Document::getElementById(const AtomicString& elementId) const
+{
+    if (elementId.isEmpty())
+        return 0;
+    return m_elementsById.get<keyMatchesId>(elementId.impl(), this);
+}
+
 String Document::readyState() const
 {
     DEFINE_STATIC_LOCAL(const String, loading, ("loading"));
@@ -1198,40 +1261,12 @@ PassRefPtr<Range> Document::caretRangeFromPoint(int x, int y)
 
 void Document::addElementById(const AtomicString& elementId, Element* element)
 {
-    typedef HashMap<AtomicStringImpl*, Element*>::iterator iterator;
-    if (!m_duplicateIds.contains(elementId.impl())) {
-        // Fast path. The ID is not already in m_duplicateIds, so we assume that it's
-        // also not already in m_elementsById and do an add. If that add succeeds, we're done.
-        pair<iterator, bool> addResult = m_elementsById.add(elementId.impl(), element);
-        if (addResult.second)
-            return;
-        // The add failed, so this ID was already cached in m_elementsById.
-        // There are multiple elements with this ID. Remove the m_elementsById
-        // cache for this ID so getElementById searches for it next time it is called.
-        m_elementsById.remove(addResult.first);
-        m_duplicateIds.add(elementId.impl());
-    } else {
-        // There are multiple elements with this ID. If it exists, remove the m_elementsById
-        // cache for this ID so getElementById searches for it next time it is called.
-        iterator cachedItem = m_elementsById.find(elementId.impl());
-        if (cachedItem != m_elementsById.end()) {
-            m_elementsById.remove(cachedItem);
-            m_duplicateIds.add(elementId.impl());
-        }
-    }
-    m_duplicateIds.add(elementId.impl());
+    m_elementsById.add(elementId.impl(), element);
 }
 
 void Document::removeElementById(const AtomicString& elementId, Element* element)
 {
-    m_elementsById.checkConsistency();
-
-    if (m_elementsById.get(elementId.impl()) == element)
-        m_elementsById.remove(elementId.impl());
-    else {
-        ASSERT(m_inRemovedLastRefFunction || m_duplicateIds.contains(elementId.impl()));
-        m_duplicateIds.remove(elementId.impl());
-    }
+    m_elementsById.remove(elementId.impl(), element);
 }
 
 Element* Document::getElementByAccessKey(const String& key) const
@@ -3779,30 +3814,28 @@ bool Document::parseQualifiedName(const String& qualifiedName, String& prefix, S
 
 void Document::addImageMap(HTMLMapElement* imageMap)
 {
-    const AtomicString& name = imageMap->getName();
-    if (!name.impl())
+    AtomicStringImpl* name = imageMap->getName().impl();
+    if (!name)
         return;
-
-    // Add the image map, unless there's already another with that name.
-    // "First map wins" is the rule other browsers seem to implement.
-    m_imageMapsByName.add(name.impl(), imageMap);
+    m_imageMapsByName.add(name, imageMap);
 }
 
 void Document::removeImageMap(HTMLMapElement* imageMap)
 {
-    // Remove the image map by name.
-    // But don't remove some other image map that just happens to have the same name.
-    // FIXME: Use a HashCountedSet as we do for IDs to find the first remaining map
-    // once a map has been removed.
-    const AtomicString& name = imageMap->getName();
-    if (!name.impl())
+    AtomicStringImpl* name = imageMap->getName().impl();
+    if (!name)
         return;
+    m_imageMapsByName.remove(name, imageMap);
+}
 
-    m_imageMapsByName.checkConsistency();
+inline bool keyMatchesMapName(AtomicStringImpl* key, Element* element)
+{
+    return element->hasTagName(mapTag) && static_cast<HTMLMapElement*>(element)->getName().impl() == key;
+}
 
-    ImageMapsByName::iterator it = m_imageMapsByName.find(name.impl());
-    if (it != m_imageMapsByName.end() && it->second == imageMap)
-        m_imageMapsByName.remove(it);
+inline bool keyMatchesLowercasedMapName(AtomicStringImpl* key, Element* element)
+{
+    return element->hasTagName(mapTag) && static_cast<HTMLMapElement*>(element)->getName().lower().impl() == key;
 }
 
 HTMLMapElement* Document::getImageMap(const String& url) const
@@ -3811,9 +3844,9 @@ HTMLMapElement* Document::getImageMap(const String& url) const
         return 0;
     size_t hashPos = url.find('#');
     String name = (hashPos == notFound ? url : url.substring(hashPos + 1)).impl();
-    AtomicString mapName = isHTMLDocument() ? name.lower() : name;
-    m_imageMapsByName.checkConsistency();
-    return m_imageMapsByName.get(mapName.impl());
+    if (isHTMLDocument())
+        return static_cast<HTMLMapElement*>(m_imageMapsByName.get<keyMatchesLowercasedMapName>(AtomicString(name.lower()).impl(), this));
+    return static_cast<HTMLMapElement*>(m_imageMapsByName.get<keyMatchesMapName>(AtomicString(name).impl(), this));
 }
 
 void Document::setDecoder(PassRefPtr<TextResourceDecoder> decoder)
index c9e3b47..8cc6272 100644 (file)
@@ -311,7 +311,7 @@ public:
     PassRefPtr<Element> createElement(const QualifiedName&, bool createdByParser);
     Element* getElementById(const AtomicString&) const;
     bool hasElementWithId(AtomicStringImpl* id) const;
-    bool containsMultipleElementsWithId(const AtomicString& elementId) { return m_duplicateIds.contains(elementId.impl()); }
+    bool containsMultipleElementsWithId(const AtomicString& id) const;
 
     /**
      * Retrieve all nodes that intersect a rect in the window's document, until it is fully enclosed by
@@ -1054,6 +1054,28 @@ protected:
     void clearXMLVersion() { m_xmlVersion = String(); }
 
 private:
+    class DocumentOrderedMap {
+    public:
+        void add(AtomicStringImpl*, Element*);
+        void remove(AtomicStringImpl*, Element*);
+        void clear();
+
+        bool contains(AtomicStringImpl*) const;
+        bool containsMultiple(AtomicStringImpl*) const;
+        template<bool keyMatches(AtomicStringImpl*, Element*)> Element* get(AtomicStringImpl*, const Document*) const;
+
+        void checkConsistency() const;
+
+    private:
+        typedef HashMap<AtomicStringImpl*, Element*> 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;
+    };
+
     friend class IgnoreDestructiveWriteCountIncrementer;
 
     void detachParser();
@@ -1243,8 +1265,7 @@ private:
     RefPtr<Document> m_transformSourceDocument;
 #endif
 
-    typedef HashMap<AtomicStringImpl*, HTMLMapElement*> ImageMapsByName;
-    ImageMapsByName m_imageMapsByName;
+    DocumentOrderedMap m_imageMapsByName;
 
     int m_docID; // A unique document identifier used for things like document-specific mapped attributes.
 
@@ -1262,11 +1283,7 @@ private:
     
     RefPtr<TextResourceDecoder> m_decoder;
 
-    // We maintain the invariant that m_duplicateIds is the count of all elements with a given ID
-    // excluding the one referenced in m_elementsById, if any. This means it one less than the total count
-    // when the first node with a given ID is cached, otherwise the same as the total count.
-    mutable HashMap<AtomicStringImpl*, Element*> m_elementsById;
-    mutable HashCountedSet<AtomicStringImpl*> m_duplicateIds;
+    DocumentOrderedMap m_elementsById;
     
     mutable HashMap<StringImpl*, Element*, CaseFoldingHash> m_elementsByAccessKey;
     
@@ -1348,10 +1365,25 @@ private:
     DocumentTiming m_documentTiming;
 };
 
+inline bool Document::DocumentOrderedMap::contains(AtomicStringImpl* id) const
+{
+    return m_map.contains(id) || m_duplicateCounts.contains(id);
+}
+
+inline bool Document::DocumentOrderedMap::containsMultiple(AtomicStringImpl* id) const
+{
+    return m_duplicateCounts.contains(id);
+}
+
 inline bool Document::hasElementWithId(AtomicStringImpl* id) const
 {
     ASSERT(id);
-    return m_elementsById.contains(id) || m_duplicateIds.contains(id);
+    return m_elementsById.contains(id);
+}
+
+inline bool Document::containsMultipleElementsWithId(const AtomicString& id) const
+{
+    return m_elementsById.containsMultiple(id.impl());
 }
     
 inline bool Node::isDocumentNode() const