Better handling of DocumentOrderedMap same-ID lookups during tree removals

third_party/WebKit/Source/core/dom/DocumentOrderedMap.cpp

Index: third_party/WebKit/Source/core/dom/DocumentOrderedMap.cpp
diff --git a/third_party/WebKit/Source/core/dom/DocumentOrderedMap.cpp b/third_party/WebKit/Source/core/dom/DocumentOrderedMap.cpp
index c13bfb337347d487f2331ebbdd28ed051a575e5d..1103173fc549106374c1ac7a54d32943253e7922 100644
--- a/third_party/WebKit/Source/core/dom/DocumentOrderedMap.cpp
+++ b/third_party/WebKit/Source/core/dom/DocumentOrderedMap.cpp
@@ -61,9 +61,16 @@ inline bool keyMatchesLabelForAttribute(const AtomicString& key, const Element&
     return isHTMLLabelElement(element) && element.getAttribute(forAttr) == key;
 }
 
+DocumentOrderedMap::DocumentOrderedMap()
+#if ENABLE(ASSERT)
+    : m_removingId(nullptr)
+#endif
+{
+}
+
 PassOwnPtrWillBeRawPtr<DocumentOrderedMap> DocumentOrderedMap::create()
 {
-    return adoptPtrWillBeNoop(new DocumentOrderedMap());
+    return adoptPtrWillBeNoop(new DocumentOrderedMap);
 }
 
 void DocumentOrderedMap::add(const AtomicString& key, Element* element)
@@ -106,6 +113,14 @@ void DocumentOrderedMap::remove(const AtomicString& key, Element* element)
     }
 }
 
+#if ENABLE(ASSERT)
+void DocumentOrderedMap::willBeRemovingId(const AtomicString* key)
+{
+    ASSERT(!m_removingId || !key);
+    m_removingId = key;
+}
+#endif
+
 template<bool keyMatches(const AtomicString&, const Element&)>
 inline Element* DocumentOrderedMap::get(const AtomicString& key, const TreeScope* scope) const
 {
@@ -120,14 +135,22 @@ inline Element* DocumentOrderedMap::get(const AtomicString& key, const TreeScope
     if (entry->element)
         return entry->element;
 
-    // We know there's at least one node that matches; iterate to find the first one.
+    // Iterate to find the node that matches. Nothing will match iff an element
+    // with children having duplicate IDs is being removed -- the tree traversal
+    // will be over an updated tree not having that element. In all other cases,
+    // a match is expected.
+    //
+    // Such calls to get()/getElementById() while handling element removals will
+    // legitimately happen when e.g., adjusting form ID associations. Quietly
+    // allow those lookups to (expectedly) fail by having the tree scope removal
+    // register the element ID it is in the process of removing.

[esprehn, 2015/12/18 00:42:26]

this is bad though, it means in those cases we walk the entire tree looking for
an element with that id and never find it, so we might walk the entire document
which is slow.

[sof, 2015/12/18 07:31:53]

The context is worth not losing sight of -- this is for documents with duplicate
IDs, with a <form> being id-associated with one of them.

     for (Element& element : ElementTraversal::startsAfter(scope->rootNode())) {
         if (!keyMatches(key, element))
             continue;
         entry->element = &element;
         return &element;
     }
-    ASSERT_NOT_REACHED();
+    ASSERT(m_removingId && key == *m_removingId);
     return 0;
 }