Changeset 131871 in webkit

Timestamp:

Oct 19, 2012 1:01:06 AM (12 years ago)

Author:

dmazzoni@google.com

Message:

AX: labelForElement is slow when there are a lot of DOM elements
​https://bugs.webkit.org/show_bug.cgi?id=97825

Reviewed by Ryosuke Niwa.

Source/WebCore:

Adds a DocumentOrderedMap to TreeScope that allows accessibility to
quickly map from an id to the label for that id. This speeds up
AccessibilityNode::labelForElement, which was a bottleneck in Chromium
when accessibility was on.

Tests: accessibility/title-ui-element-correctness.html

perf/accessibility-title-ui-element.html

• accessibility/AccessibilityNodeObject.cpp:

(WebCore::AccessibilityNodeObject::labelForElement):

• dom/DocumentOrderedMap.cpp:

(WebCore::keyMatchesLabelForAttribute):
(WebCore):
(WebCore::DocumentOrderedMap::get):
(WebCore::DocumentOrderedMap::getElementByLabelForAttribute):

• dom/DocumentOrderedMap.h:

(DocumentOrderedMap):

• dom/Element.cpp:

(WebCore::Element::insertedInto):
(WebCore::Element::removedFrom):
(WebCore::Element::updateLabel):
(WebCore):
(WebCore::Element::willModifyAttribute):

• dom/Element.h:

(Element):

• dom/TreeScope.cpp:

(WebCore::TreeScope::TreeScope):
(WebCore::TreeScope::destroyTreeScopeData):
(WebCore::TreeScope::addLabel):
(WebCore):
(WebCore::TreeScope::removeLabel):
(WebCore::TreeScope::labelElementForId):

• dom/TreeScope.h:

(WebCore):
(TreeScope):
(WebCore::TreeScope::shouldCacheLabelsByForAttribute):

Tools:

Implement titleUIElement in the chromium port of DRT, and
fix getAccessibleElementById so that it ensures the backing store
is up-to-date.

• DumpRenderTree/chromium/TestRunner/AccessibilityControllerChromium.cpp:

(AccessibilityController::getAccessibleElementById):

• DumpRenderTree/chromium/TestRunner/AccessibilityUIElementChromium.cpp:

(AccessibilityUIElement::titleUIElementCallback):

LayoutTests:

Adds two new tests for titleUIElement that run on both Mac and
Chromium. One tests correctness, the other tests speed.

Fixes one test so that it passes on Chromium.
Enables other tests that now pass on Chromium.

• accessibility/secure-textfield-title-ui.html:
• accessibility/title-ui-element-correctness-expected.txt: Added.
• accessibility/title-ui-element-correctness.html: Added.
• perf/accessibility-title-ui-element-expected.txt: Added.
• perf/accessibility-title-ui-element.html: Added.
• platform/chromium/TestExpectations:

Location:

trunk

Files:

• LayoutTests/ChangeLog (modified) (1 diff)
• LayoutTests/accessibility/secure-textfield-title-ui.html (modified) (1 diff)
• LayoutTests/accessibility/title-ui-element-correctness-expected.txt (added)
• LayoutTests/accessibility/title-ui-element-correctness.html (added)
• LayoutTests/perf/accessibility-title-ui-element-expected.txt (added)
• LayoutTests/perf/accessibility-title-ui-element.html (added)
• LayoutTests/platform/chromium/TestExpectations (modified) (3 diffs)
• Source/WebCore/ChangeLog (modified) (1 diff)
• Source/WebCore/accessibility/AccessibilityNodeObject.cpp (modified) (2 diffs)
• Source/WebCore/dom/DocumentOrderedMap.cpp (modified) (2 diffs)
• Source/WebCore/dom/DocumentOrderedMap.h (modified) (2 diffs)
• Source/WebCore/dom/Element.cpp (modified) (5 diffs)
• Source/WebCore/dom/Element.h (modified) (1 diff)
• Source/WebCore/dom/TreeScope.cpp (modified) (4 diffs)
• Source/WebCore/dom/TreeScope.h (modified) (3 diffs)
• Tools/ChangeLog (modified) (1 diff)
• Tools/DumpRenderTree/chromium/TestRunner/src/AccessibilityControllerChromium.cpp (modified) (1 diff)
• Tools/DumpRenderTree/chromium/TestRunner/src/AccessibilityUIElementChromium.cpp (modified) (1 diff)

trunk/LayoutTests/ChangeLog

@@ +1 @@
+2012-10-18  Dominic Mazzoni  <dmazzoni@google.com>
+
+        AX: labelForElement is slow when there are a lot of DOM elements
+        https://bugs.webkit.org/show_bug.cgi?id=97825
+
+        Reviewed by Ryosuke Niwa.
+
+        Adds two new tests for titleUIElement that run on both Mac and
+        Chromium. One tests correctness, the other tests speed.
+
+        Fixes one test so that it passes on Chromium.
+        Enables other tests that now pass on Chromium.
+
+        * accessibility/secure-textfield-title-ui.html:
+        * accessibility/title-ui-element-correctness-expected.txt: Added.
+        * accessibility/title-ui-element-correctness.html: Added.
+        * perf/accessibility-title-ui-element-expected.txt: Added.
+        * perf/accessibility-title-ui-element.html: Added.
+        * platform/chromium/TestExpectations:
+
 2012-10-18  Alexander Pavlov  <apavlov@chromium.org>
 

trunk/LayoutTests/accessibility/secure-textfield-title-ui.html

@@ -22 +22 @@
             var titleUIElement = accessibilityController.focusedElement.titleUIElement();
             var titleText = titleUIElement.childAtIndex(0);
-            var pattern = "AXValue: Password";
-            if (titleText.allAttributes().indexOf(pattern) != -1) {
+            if (titleText.stringValue == "AXValue: Password") {
                 result.innerText += "Test passed\n";
             }

trunk/LayoutTests/platform/chromium/TestExpectations

@@ -1403 +1403 @@
 crbug.com/10322 accessibility/lists.html [ Skip ]
 crbug.com/10322 accessibility/media-element.html [ Skip ]
-crbug.com/10322 accessibility/non-data-table-cell-title-ui-element.html [ Skip ]
 crbug.com/10322 accessibility/onclick-handlers.html [ Skip ]
 crbug.com/10322 accessibility/placeholder.html [ Skip ]
@@ -1409 +1408 @@
 crbug.com/10322 accessibility/radio-button-checkbox-size.html [ Skip ]
 crbug.com/10322 accessibility/radio-button-group-members.html [ Skip ]
-crbug.com/10322 accessibility/radio-button-title-label.html [ Skip ]
-crbug.com/10322 accessibility/secure-textfield-title-ui.html [ Skip ]
 crbug.com/10322 accessibility/table-attributes.html [ Skip ]
 crbug.com/10322 accessibility/table-cell-spans.html [ Skip ]
@@ -1419 +1416 @@
 crbug.com/10322 accessibility/table-with-aria-role.html [ Skip ]
 crbug.com/10322 accessibility/table-with-rules.html [ Skip ]
-crbug.com/10322 accessibility/th-as-title-ui.html [ Skip ]
 crbug.com/10322 accessibility/transformed-element.html [ Skip ]
 crbug.com/10322 accessibility/visible-elements.html [ Skip ]

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2012-10-18  Dominic Mazzoni  <dmazzoni@google.com>
+
+        AX: labelForElement is slow when there are a lot of DOM elements
+        https://bugs.webkit.org/show_bug.cgi?id=97825
+
+        Reviewed by Ryosuke Niwa.
+
+        Adds a DocumentOrderedMap to TreeScope that allows accessibility to
+        quickly map from an id to the label for that id. This speeds up
+        AccessibilityNode::labelForElement, which was a bottleneck in Chromium
+        when accessibility was on.
+
+        Tests: accessibility/title-ui-element-correctness.html
+               perf/accessibility-title-ui-element.html
+
+        * accessibility/AccessibilityNodeObject.cpp:
+        (WebCore::AccessibilityNodeObject::labelForElement):
+        * dom/DocumentOrderedMap.cpp:
+        (WebCore::keyMatchesLabelForAttribute):
+        (WebCore):
+        (WebCore::DocumentOrderedMap::get):
+        (WebCore::DocumentOrderedMap::getElementByLabelForAttribute):
+        * dom/DocumentOrderedMap.h:
+        (DocumentOrderedMap):
+        * dom/Element.cpp:
+        (WebCore::Element::insertedInto):
+        (WebCore::Element::removedFrom):
+        (WebCore::Element::updateLabel):
+        (WebCore):
+        (WebCore::Element::willModifyAttribute):
+        * dom/Element.h:
+        (Element):
+        * dom/TreeScope.cpp:
+        (WebCore::TreeScope::TreeScope):
+        (WebCore::TreeScope::destroyTreeScopeData):
+        (WebCore::TreeScope::addLabel):
+        (WebCore):
+        (WebCore::TreeScope::removeLabel):
+        (WebCore::TreeScope::labelElementForId):
+        * dom/TreeScope.h:
+        (WebCore):
+        (TreeScope):
+        (WebCore::TreeScope::shouldCacheLabelsByForAttribute):
+
 2012-10-19  Eugene Klyuchnikov  <eustas.bug@gmail.com>
 

trunk/Source/WebCore/accessibility/AccessibilityNodeObject.cpp

@@ -60 +60 @@
 #include "HitTestRequest.h"
 #include "HitTestResult.h"
+#include "LabelableElement.h"
 #include "LocalizedStrings.h"
 #include "MathMLNames.h"
@@ -1002 +1003 @@
 HTMLLabelElement* AccessibilityNodeObject::labelForElement(Element* element) const
 {
-    RefPtr<NodeList> list = element->document()->getElementsByTagName("label");
-    unsigned len = list->length();
-    for (unsigned i = 0; i < len; i++) {
-        if (list->item(i)->hasTagName(labelTag)) {
-            HTMLLabelElement* label = static_cast<HTMLLabelElement*>(list->item(i));
-            if (label->control() == element)
-                return label;
-        }
+    if (!element->isHTMLElement() || !toHTMLElement(element)->isLabelable())
+        return 0;
+
+    const AtomicString& id = element->getIdAttribute();
+    if (!id.isEmpty()) {
+        if (HTMLLabelElement* label = element->treeScope()->labelElementForId(id))
+            return label;
+    }
+
+    for (Element* parent = element->parentElement(); parent; parent = parent->parentElement()) {
+        if (parent->hasTagName(labelTag))
+            return static_cast<HTMLLabelElement*>(parent);
     }
 

trunk/Source/WebCore/dom/DocumentOrderedMap.cpp

@@ -54 +54 @@
 {
     return element->hasTagName(mapTag) && static_cast<HTMLMapElement*>(element)->getName().lower().impl() == key;
+}
+
+inline bool keyMatchesLabelForAttribute(AtomicStringImpl* key, Element* element)
+{
+    return element->hasTagName(labelTag) && element->getAttribute(forAttr).impl() == key;
 }
 
@@ -150 +155 @@
 }
 
+Element* DocumentOrderedMap::getElementByLabelForAttribute(AtomicStringImpl* key, const TreeScope* scope) const
+{
+    return get<keyMatchesLabelForAttribute>(key, scope);
+}
+
 } // namespace WebCore
-

trunk/Source/WebCore/dom/DocumentOrderedMap.h

@@ -53 +53 @@
     Element* getElementByMapName(AtomicStringImpl*, const TreeScope*) const;
     Element* getElementByLowercasedMapName(AtomicStringImpl*, const TreeScope*) const;
+    Element* getElementByLabelForAttribute(AtomicStringImpl*, const TreeScope*) const;
 
     void checkConsistency() const;
@@ -81 +82 @@
 
 #endif // DocumentOrderedMap_h
-

trunk/Source/WebCore/dom/Element.cpp

@@ -49 +49 @@
 #include "HTMLFormCollection.h"
 #include "HTMLFrameOwnerElement.h"
+#include "HTMLLabelElement.h"
 #include "HTMLNames.h"
 #include "HTMLOptionsCollection.h"
@@ -960 +961 @@
         updateName(nullAtom, nameValue);
 
+    if (hasTagName(labelTag)) {
+        TreeScope* scope = treeScope();
+        if (scope->shouldCacheLabelsByForAttribute())
+            updateLabel(scope, nullAtom, fastGetAttribute(forAttr));
+    }
+
     return InsertionDone;
 }
@@ -984 +991 @@
         if (!nameValue.isNull())
             updateName(nameValue, nullAtom);
+
+        if (hasTagName(labelTag)) {
+            TreeScope* treeScope = insertionPoint->treeScope();
+            if (treeScope->shouldCacheLabelsByForAttribute())
+                updateLabel(treeScope, fastGetAttribute(forAttr), nullAtom);
+        }
     }
 
@@ -2126 +2139 @@
 #endif
 
+void Element::updateLabel(TreeScope* scope, const AtomicString& oldForAttributeValue, const AtomicString& newForAttributeValue)
+{
+    ASSERT(hasTagName(labelTag));
+
+    if (!inDocument())
+        return;
+
+    if (oldForAttributeValue == newForAttributeValue)
+        return;
+
+    if (!oldForAttributeValue.isEmpty())
+        scope->removeLabel(oldForAttributeValue, static_cast<HTMLLabelElement*>(this));
+    if (!newForAttributeValue.isEmpty())
+        scope->addLabel(newForAttributeValue, static_cast<HTMLLabelElement*>(this));
+}
+
 void Element::willModifyAttribute(const QualifiedName& name, const AtomicString& oldValue, const AtomicString& newValue)
 {
@@ -2132 +2161 @@
     else if (name == HTMLNames::nameAttr)
         updateName(oldValue, newValue);
+    else if (name == HTMLNames::forAttr && hasTagName(labelTag)) {
+        TreeScope* scope = treeScope();
+        if (scope->shouldCacheLabelsByForAttribute())
+            updateLabel(scope, oldValue, newValue);
+    }
 
 #if ENABLE(MUTATION_OBSERVERS)

trunk/Source/WebCore/dom/Element.h

@@ -316 +316 @@
     void updateId(TreeScope*, const AtomicString& oldId, const AtomicString& newId);
     void updateName(const AtomicString& oldName, const AtomicString& newName);
+    void updateLabel(TreeScope*, const AtomicString& oldForAttributeValue, const AtomicString& newForAttributeValue);
 
     void removeCachedHTMLCollection(HTMLCollection*, CollectionType);

trunk/Source/WebCore/dom/TreeScope.cpp

@@ -37 +37 @@
 #include "HTMLAnchorElement.h"
 #include "HTMLFrameOwnerElement.h"
+#include "HTMLLabelElement.h"
 #include "HTMLMapElement.h"
 #include "HTMLNames.h"
@@ -56 +57 @@
     : m_rootNode(rootNode)
     , m_parentTreeScope(0)
+    , m_shouldCacheLabelsByForAttribute(false)
     , m_idTargetObserverRegistry(IdTargetObserverRegistry::create())
 {
@@ -73 +75 @@
     m_elementsById.clear();
     m_imageMapsByName.clear();
+    m_labelsByForAttribute.clear();
 }
 
@@ -143 +146 @@
         return static_cast<HTMLMapElement*>(m_imageMapsByName.getElementByLowercasedMapName(AtomicString(name.lower()).impl(), this));
     return static_cast<HTMLMapElement*>(m_imageMapsByName.getElementByMapName(AtomicString(name).impl(), this));
+}
+
+void TreeScope::addLabel(const AtomicString& forAttributeValue, HTMLLabelElement* element)
+{
+    m_labelsByForAttribute.add(forAttributeValue.impl(), element);
+}
+
+void TreeScope::removeLabel(const AtomicString& forAttributeValue, HTMLLabelElement* element)
+{
+    m_labelsByForAttribute.remove(forAttributeValue.impl(), element);
+}
+
+HTMLLabelElement* TreeScope::labelElementForId(const AtomicString& forAttributeValue)
+{
+    if (!m_shouldCacheLabelsByForAttribute) {
+        m_shouldCacheLabelsByForAttribute = true;
+        for (Node* node = rootNode(); node; node = node->traverseNextNode()) {
+            if (node->hasTagName(labelTag)) {
+                HTMLLabelElement* label = static_cast<HTMLLabelElement*>(node);
+                const AtomicString& forValue = label->fastGetAttribute(forAttr);
+                if (!forValue.isEmpty())
+                    addLabel(forValue, label);
+            }
+        }
+    }
+
+    if (forAttributeValue.isEmpty())
+        return 0;
+
+    return static_cast<HTMLLabelElement*>(m_labelsByForAttribute.getElementByLabelForAttribute(forAttributeValue.impl(), this));
 }
 

trunk/Source/WebCore/dom/TreeScope.h

@@ -36 +36 @@
 class DOMSelection;
 class Element;
+class HTMLLabelElement;
 class HTMLMapElement;
 class IdTargetObserverRegistry;
@@ -62 +63 @@
     void removeImageMap(HTMLMapElement*);
     HTMLMapElement* getImageMap(const String& url) const;
+
+    // For accessibility.
+    bool shouldCacheLabelsByForAttribute() const { return m_shouldCacheLabelsByForAttribute; }
+    void addLabel(const AtomicString& forAttributeValue, HTMLLabelElement*);
+    void removeLabel(const AtomicString& forAttributeValue, HTMLLabelElement*);
+    HTMLLabelElement* labelElementForId(const AtomicString& forAttributeValue);
 
     DOMSelection* getSelection() const;
@@ -95 +102 @@
     DocumentOrderedMap m_imageMapsByName;
 
+    DocumentOrderedMap m_labelsByForAttribute;
+    bool m_shouldCacheLabelsByForAttribute;
+
     OwnPtr<IdTargetObserverRegistry> m_idTargetObserverRegistry;
 

trunk/Tools/ChangeLog

@@ +1 @@
+2012-10-18  Dominic Mazzoni  <dmazzoni@google.com>
+
+        AX: labelForElement is slow when there are a lot of DOM elements
+        https://bugs.webkit.org/show_bug.cgi?id=97825
+
+        Reviewed by Ryosuke Niwa.
+
+        Implement titleUIElement in the chromium port of DRT, and
+        fix getAccessibleElementById so that it ensures the backing store
+        is up-to-date.
+
+        * DumpRenderTree/chromium/TestRunner/AccessibilityControllerChromium.cpp:
+        (AccessibilityController::getAccessibleElementById):
+        * DumpRenderTree/chromium/TestRunner/AccessibilityUIElementChromium.cpp:
+        (AccessibilityUIElement::titleUIElementCallback):
+
 2012-10-17  Ilya Tikhonovsky  <loislo@chromium.org>
 

trunk/Tools/DumpRenderTree/chromium/TestRunner/src/AccessibilityControllerChromium.cpp

@@ -118 +118 @@
         m_rootElement = m_webView->accessibilityObject();
 
+    if (!m_rootElement.updateBackingStoreAndCheckValidity())
+        return 0;
+
     return findAccessibleElementByIdRecursive(m_rootElement, WebString::fromUTF8(id.c_str()));
 }

trunk/Tools/DumpRenderTree/chromium/TestRunner/src/AccessibilityUIElementChromium.cpp

@@ -775 +775 @@
 void AccessibilityUIElement::titleUIElementCallback(const CppArgumentList&, CppVariant* result)
 {
-    result->setNull();
+    WebAccessibilityObject obj = accessibilityObject().titleUIElement();
+    if (obj.isNull()) {
+        result->setNull();
+        return;
+    }
+
+    result->set(*(m_factory->getOrCreate(obj)->getAsCppVariant()));
 }