- Revision
- 156925
- Author
- [email protected]
- Date
- 2013-10-04 16:33:10 -0700 (Fri, 04 Oct 2013)
Log Message
FocusController::advanceFocus spends a lot of time in HTMLMapElement::imageElement
https://bugs.webkit.org/show_bug.cgi?id=122313
Reviewed by Andreas Kling.
The bug was caused by HTMLMapElement::imageElement traversing the entire document to look for
the image element associated with a given map element. Because HTMLCollection used to find the
image element is not cached, it traversed the entire document on every area element we visit,
resulting in O(n^2) behavior.
Fixed the bug by adding the name-to-image-element map on document to avoid the traversal in
HTMLMapElement::imageElement.
* dom/Document.cpp:
(WebCore::Document::addImageElementByLowercasedUsemap): Added.
(WebCore::Document::removeImageElementByLowercasedUsemap): Added.
(WebCore::Document::imageElementByLowercasedUsemap): Added.
* dom/Document.h: Added m_imagesByUsemap.
* dom/DocumentOrderedMap.cpp:
(WebCore::keyMatchesLowercasedUsemap): Added.
(WebCore::DocumentOrderedMap::getElementByLowercasedUsemap): Added.
* dom/DocumentOrderedMap.h:
* html/HTMLImageElement.cpp:
(WebCore::HTMLImageElement::parseAttribute): Update the name-to-usemap map. The code to parse
the usemap attribute and strip # was moved from HTMLMapElement::imageElement.
(WebCore::HTMLImageElement::insertedInto): Ditto.
(WebCore::HTMLImageElement::removedFrom): Ditto.
(WebCore::HTMLImageElement::matchesLowercasedUsemap): Added; called by DocumentOrderedMap.
* html/HTMLImageElement.h:
* html/HTMLMapElement.cpp:
(WebCore::HTMLMapElement::imageElement): Call Document::imageElementByUsemap instead of
looking through all image elements in the document.
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (156924 => 156925)
--- trunk/Source/WebCore/ChangeLog 2013-10-04 23:25:55 UTC (rev 156924)
+++ trunk/Source/WebCore/ChangeLog 2013-10-04 23:33:10 UTC (rev 156925)
@@ -1,3 +1,43 @@
+2013-10-03 Ryosuke Niwa <[email protected]>
+
+ FocusController::advanceFocus spends a lot of time in HTMLMapElement::imageElement
+ https://bugs.webkit.org/show_bug.cgi?id=122313
+
+ Reviewed by Andreas Kling.
+
+ The bug was caused by HTMLMapElement::imageElement traversing the entire document to look for
+ the image element associated with a given map element. Because HTMLCollection used to find the
+ image element is not cached, it traversed the entire document on every area element we visit,
+ resulting in O(n^2) behavior.
+
+ Fixed the bug by adding the name-to-image-element map on document to avoid the traversal in
+ HTMLMapElement::imageElement.
+
+ * dom/Document.cpp:
+ (WebCore::Document::addImageElementByLowercasedUsemap): Added.
+ (WebCore::Document::removeImageElementByLowercasedUsemap): Added.
+ (WebCore::Document::imageElementByLowercasedUsemap): Added.
+
+ * dom/Document.h: Added m_imagesByUsemap.
+
+ * dom/DocumentOrderedMap.cpp:
+ (WebCore::keyMatchesLowercasedUsemap): Added.
+ (WebCore::DocumentOrderedMap::getElementByLowercasedUsemap): Added.
+
+ * dom/DocumentOrderedMap.h:
+ * html/HTMLImageElement.cpp:
+ (WebCore::HTMLImageElement::parseAttribute): Update the name-to-usemap map. The code to parse
+ the usemap attribute and strip # was moved from HTMLMapElement::imageElement.
+ (WebCore::HTMLImageElement::insertedInto): Ditto.
+ (WebCore::HTMLImageElement::removedFrom): Ditto.
+ (WebCore::HTMLImageElement::matchesLowercasedUsemap): Added; called by DocumentOrderedMap.
+
+ * html/HTMLImageElement.h:
+
+ * html/HTMLMapElement.cpp:
+ (WebCore::HTMLMapElement::imageElement): Call Document::imageElementByUsemap instead of
+ looking through all image elements in the document.
+
2013-10-04 Sam Weinig <[email protected]>
Unify rubberband control
Modified: trunk/Source/WebCore/dom/Document.cpp (156924 => 156925)
--- trunk/Source/WebCore/dom/Document.cpp 2013-10-04 23:25:55 UTC (rev 156924)
+++ trunk/Source/WebCore/dom/Document.cpp 2013-10-04 23:33:10 UTC (rev 156925)
@@ -84,6 +84,7 @@
#include "HTMLFrameOwnerElement.h"
#include "HTMLHeadElement.h"
#include "HTMLIFrameElement.h"
+#include "HTMLImageElement.h"
#include "HTMLLinkElement.h"
#include "HTMLMediaElement.h"
#include "HTMLNameCollection.h"
@@ -706,6 +707,21 @@
m_elementsByAccessKey.clear();
}
+void Document::addImageElementByLowercasedUsemap(const AtomicString& name, HTMLImageElement& element)
+{
+ return m_imagesByUsemap.add(name.impl(), &element);
+}
+
+void Document::removeImageElementByLowercasedUsemap(const AtomicString& name, HTMLImageElement& element)
+{
+ return m_imagesByUsemap.remove(name.impl(), &element);
+}
+
+HTMLImageElement* Document::imageElementByLowercasedUsemap(const AtomicString& name) const
+{
+ return m_imagesByUsemap.getElementByLowercasedUsemap(name.impl(), this);
+}
+
SelectorQueryCache& Document::selectorQueryCache()
{
if (!m_selectorQueryCache)
Modified: trunk/Source/WebCore/dom/Document.h (156924 => 156925)
--- trunk/Source/WebCore/dom/Document.h 2013-10-04 23:25:55 UTC (rev 156924)
+++ trunk/Source/WebCore/dom/Document.h 2013-10-04 23:33:10 UTC (rev 156925)
@@ -103,6 +103,7 @@
class HTMLFrameOwnerElement;
class HTMLHeadElement;
class HTMLIFrameElement;
+class HTMLImageElement;
class HTMLMapElement;
class HTMLNameCollection;
class HTMLScriptElement;
@@ -257,6 +258,10 @@
Element* getElementByAccessKey(const String& key);
void invalidateAccessKeyMap();
+ void addImageElementByLowercasedUsemap(const AtomicString&, HTMLImageElement&);
+ void removeImageElementByLowercasedUsemap(const AtomicString&, HTMLImageElement&);
+ HTMLImageElement* imageElementByLowercasedUsemap(const AtomicString&) const;
+
SelectorQueryCache& selectorQueryCache();
// DOM methods & attributes for Document
@@ -1450,6 +1455,8 @@
HashMap<StringImpl*, Element*, CaseFoldingHash> m_elementsByAccessKey;
bool m_accessKeyMapValid;
+ DocumentOrderedMap m_imagesByUsemap;
+
OwnPtr<SelectorQueryCache> m_selectorQueryCache;
DocumentClassFlags m_documentClasses;
Modified: trunk/Source/WebCore/dom/DocumentOrderedMap.cpp (156924 => 156925)
--- trunk/Source/WebCore/dom/DocumentOrderedMap.cpp 2013-10-04 23:25:55 UTC (rev 156924)
+++ trunk/Source/WebCore/dom/DocumentOrderedMap.cpp 2013-10-04 23:33:10 UTC (rev 156925)
@@ -33,6 +33,7 @@
#include "Element.h"
#include "ElementTraversal.h"
+#include "HTMLImageElement.h"
#include "HTMLLabelElement.h"
#include "HTMLMapElement.h"
#include "HTMLNameCollection.h"
@@ -63,6 +64,12 @@
return isHTMLMapElement(element) && toHTMLMapElement(element)->getName().lower().impl() == key;
}
+inline bool keyMatchesLowercasedUsemap(const AtomicStringImpl* key, Element* element)
+{
+ // FIXME: HTML5 specification says we should match both image and object elements.
+ return isHTMLImageElement(element) && toHTMLImageElement(element)->matchesLowercasedUsemap(*key);
+}
+
inline bool keyMatchesLabelForAttribute(const AtomicStringImpl* key, Element* element)
{
return isHTMLLabelElement(element) && element->getAttribute(forAttr).impl() == key;
@@ -169,6 +176,11 @@
return get<keyMatchesLowercasedMapName>(key, scope);
}
+HTMLImageElement* DocumentOrderedMap::getElementByLowercasedUsemap(const AtomicStringImpl* key, const TreeScope* scope) const
+{
+ return toHTMLImageElement(get<keyMatchesLowercasedUsemap>(key, scope));
+}
+
Element* DocumentOrderedMap::getElementByLabelForAttribute(const AtomicStringImpl* key, const TreeScope* scope) const
{
return get<keyMatchesLabelForAttribute>(key, scope);
Modified: trunk/Source/WebCore/dom/DocumentOrderedMap.h (156924 => 156925)
--- trunk/Source/WebCore/dom/DocumentOrderedMap.h 2013-10-04 23:25:55 UTC (rev 156924)
+++ trunk/Source/WebCore/dom/DocumentOrderedMap.h 2013-10-04 23:33:10 UTC (rev 156925)
@@ -39,6 +39,7 @@
namespace WebCore {
class Element;
+class HTMLImageElement;
class TreeScope;
class DocumentOrderedMap {
@@ -56,6 +57,7 @@
Element* getElementByName(const AtomicStringImpl*, const TreeScope*) const;
Element* getElementByMapName(const AtomicStringImpl*, const TreeScope*) const;
Element* getElementByLowercasedMapName(const AtomicStringImpl*, const TreeScope*) const;
+ HTMLImageElement* getElementByLowercasedUsemap(const AtomicStringImpl*, const TreeScope*) const;
Element* getElementByLabelForAttribute(const AtomicStringImpl*, const TreeScope*) const;
Element* getElementByWindowNamedItem(const AtomicStringImpl*, const TreeScope*) const;
Element* getElementByDocumentNamedItem(const AtomicStringImpl*, const TreeScope*) const;
Modified: trunk/Source/WebCore/html/HTMLImageElement.cpp (156924 => 156925)
--- trunk/Source/WebCore/html/HTMLImageElement.cpp 2013-10-04 23:25:55 UTC (rev 156924)
+++ trunk/Source/WebCore/html/HTMLImageElement.cpp 2013-10-04 23:33:10 UTC (rev 156925)
@@ -123,9 +123,27 @@
} else if (name == srcAttr || name == srcsetAttr) {
m_bestFitImageURL = bestFitSourceForImageAttributes(document().deviceScaleFactor(), fastGetAttribute(srcAttr), fastGetAttribute(srcsetAttr));
m_imageLoader.updateFromElementIgnoringPreviousError();
- } else if (name == usemapAttr)
+ } else if (name == usemapAttr) {
setIsLink(!value.isNull() && !shouldProhibitLinks(this));
- else if (name == onbeforeloadAttr)
+
+ if (m_lowercasedUsemap == value)
+ return;
+
+ if (!m_lowercasedUsemap.isNull())
+ document().removeImageElementByLowercasedUsemap(m_lowercasedUsemap, *this);
+
+ // The HTMLImageElement's useMap() value includes the '#' symbol at the beginning, which has to be stripped off.
+ // FIXME: We should check that the first character is '#'.
+ // FIXME: HTML5 specification says we should strip any leading string before '#'.
+ // FIXME: HTML5 specification says we should ignore usemap attributes without #.
+ if (value.length() > 1)
+ m_lowercasedUsemap = value.string().substring(1).lower();
+ else
+ m_lowercasedUsemap = nullAtom;
+
+ if (!m_lowercasedUsemap.isNull())
+ document().addImageElementByLowercasedUsemap(m_lowercasedUsemap, *this);
+ } else if (name == onbeforeloadAttr)
setAttributeEventListener(eventNames().beforeloadEvent, name, value);
else if (name == compositeAttr) {
// FIXME: images don't support blend modes in their compositing attribute.
@@ -206,6 +224,9 @@
m_form->registerImgElement(this);
}
+ if (insertionPoint->inDocument() && !m_lowercasedUsemap.isNull())
+ document().addImageElementByLowercasedUsemap(m_lowercasedUsemap, *this);
+
// If we have been inserted from a renderer-less document,
// our loader may have not fetched the image, so do it now.
if (insertionPoint.inDocument() && !m_imageLoader.image())
@@ -218,6 +239,10 @@
{
if (m_form)
m_form->removeImgElement(this);
+
+ if (insertionPoint->inDocument() && !m_lowercasedUsemap.isNull())
+ document().removeImageElementByLowercasedUsemap(m_lowercasedUsemap, *this);
+
m_form = 0;
HTMLElement::removedFrom(insertionPoint);
}
@@ -293,6 +318,12 @@
|| HTMLElement::isURLAttribute(attribute);
}
+bool HTMLImageElement::matchesLowercasedUsemap(const AtomicStringImpl& name) const
+{
+ ASSERT(const_cast<AtomicStringImpl&>(name).lower() == &name);
+ return m_lowercasedUsemap.impl() == &name;
+}
+
const AtomicString& HTMLImageElement::alt() const
{
return getAttribute(altAttr);
Modified: trunk/Source/WebCore/html/HTMLImageElement.h (156924 => 156925)
--- trunk/Source/WebCore/html/HTMLImageElement.h 2013-10-04 23:25:55 UTC (rev 156924)
+++ trunk/Source/WebCore/html/HTMLImageElement.h 2013-10-04 23:33:10 UTC (rev 156925)
@@ -59,6 +59,8 @@
void setLoadManually(bool loadManually) { m_imageLoader.setLoadManually(loadManually); }
+ bool matchesLowercasedUsemap(const AtomicStringImpl&) const;
+
const AtomicString& alt() const;
void setHeight(int);
@@ -117,6 +119,7 @@
HTMLFormElement* m_form;
CompositeOperator m_compositeOperator;
AtomicString m_bestFitImageURL;
+ AtomicString m_lowercasedUsemap;
};
ELEMENT_TYPE_CASTS(HTMLImageElement)
Modified: trunk/Source/WebCore/html/HTMLMapElement.cpp (156924 => 156925)
--- trunk/Source/WebCore/html/HTMLMapElement.cpp 2013-10-04 23:25:55 UTC (rev 156924)
+++ trunk/Source/WebCore/html/HTMLMapElement.cpp 2013-10-04 23:33:10 UTC (rev 156925)
@@ -79,20 +79,7 @@
HTMLImageElement* HTMLMapElement::imageElement()
{
- RefPtr<HTMLCollection> images = document().images();
- for (unsigned i = 0; Node* curr = images->item(i); i++) {
- if (!isHTMLImageElement(curr))
- continue;
-
- // The HTMLImageElement's useMap() value includes the '#' symbol at the beginning,
- // which has to be stripped off.
- HTMLImageElement* imageElement = toHTMLImageElement(curr);
- String useMapName = imageElement->getAttribute(usemapAttr).string().substring(1);
- if (equalIgnoringCase(useMapName, m_name))
- return imageElement;
- }
-
- return 0;
+ return document().imageElementByLowercasedUsemap(m_name.lower());
}
void HTMLMapElement::parseAttribute(const QualifiedName& name, const AtomicString& value)
