Better handling of DocumentOrderedMap same-ID lookups during tree removals

third_party/WebKit/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 43 matching lines @@
 inline bool keyMatchesLowercasedMapName(const AtomicString& key, const Element& element)
 {
     return isHTMLMapElement(element) && toHTMLMapElement(element).getName().lower() == key;
 }
 
 inline bool keyMatchesLabelForAttribute(const AtomicString& key, const Element& 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)
 {
     ASSERT(key);
     ASSERT(element);
 
     Map::AddResult addResult = m_map.add(key, adoptPtrWillBeNoop(new MapEntry(element)));
     if (addResult.isNewEntry)
         return;
@@ skipping 22 matching lines @@
     } else {
         if (entry->element == element) {
             ASSERT(entry->orderedList.isEmpty() || entry->orderedList.first() == element);
             entry->element = entry->orderedList.size() > 1 ? entry->orderedList[1] : nullptr;
         }
         entry->count--;
         entry->orderedList.clear();
     }
 }
 
+#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
 {
     ASSERT(key);
     ASSERT(scope);
 
     MapEntry* entry = m_map.get(key);
     if (!entry)
         return 0;
 
     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.
+    // 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;
 }
 
 Element* DocumentOrderedMap::getElementById(const AtomicString& key, const TreeScope* scope) const
 {
     return get<keyMatchesId>(key, scope);
 }
 
 const WillBeHeapVector<RawPtrWillBeMember<Element>>& DocumentOrderedMap::getAllElementsById(const AtomicString& key, const TreeScope* scope) const
 {
@@ skipping 47 matching lines @@
 
 DEFINE_TRACE(DocumentOrderedMap::MapEntry)
 {
     visitor->trace(element);
 #if ENABLE(OILPAN)
     visitor->trace(orderedList);
 #endif
 }
 
 } // namespace blink