Bug 97825 – AX: labelForElement is slow when there are a lot of DOM elements

• Component: Accessibility
• Status: RESOLVED FIXED

[Dominic Mazzoni]

See related bug: https://bugs.webkit.org/show_bug.cgi?id=33253

Currently AccessibilityNodeObject::labelForElement, which is used to find the <label> associated with a focusable control, scans all of the nodes in the DOM tree to find possible labels, which can be inefficient. This function shows up as a bottleneck when I run various Chrome benchmarks with accessibility enabled.

Proposed alternative: AXObjectCache should maintain a hash map from label id to label element. It should be generated lazily the first time it's needed, then updated every time a label is modified or deleted.

[Dominic Mazzoni]

Created attachment 166175 [details]
Patch

[Dominic Mazzoni]

Created attachment 166275 [details]
Patch

[chris fleizach]

Comment on attachment 166275 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=166275&action=review

If the <label> element itself is removed from the tree, how is the m_idToLabelMapping being updated? i couldn't find where that's happening

> Source/WebCore/accessibility/AXObjectCache.h:213
> +    HashMap<Document*, HashMap<String, HTMLLabelElement*>* > m_idToLabelMapping;

Can we make HashMap a RefPtr<> so we don't have to worry about deleting it after removing from the cache

> Source/WebCore/dom/Document.cpp:635
>      clearAXObjectCache();

i think we should try to leverage just one AX method when Document is destroyed to do all the necessary cleanup

> Source/WebCore/html/HTMLLabelElement.cpp:174
> +        document()->axObjectCache()->updateLabelElementForId(document(), attribute.value(), this);

it seems that we will update the cache twice when a forAttr is added (once in willModify with the newValue, then once in attributedChanged)
Is it possible to do all the updating in attributeChanged, at the cost of perhaps searching the label cache for the correct label element.
that way, willModify won't have to be come virtual

[Early Warning System Bot]

Comment on attachment 166275 [details]
Patch

Attachment 166275 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/14060402

[Early Warning System Bot]

Comment on attachment 166275 [details]
Patch

Attachment 166275 [details] did not pass qt-wk2-ews (qt):
Output: http://queues.webkit.org/results/14059420

[Gyuyoung Kim]

Comment on attachment 166275 [details]
Patch

Attachment 166275 [details] did not pass efl-ews (efl):
Output: http://queues.webkit.org/results/14056481

[Peter Beverloo (cr-android ews)]

Comment on attachment 166275 [details]
Patch

Attachment 166275 [details] did not pass cr-android-ews (chromium-android):
Output: http://queues.webkit.org/results/14061412

[Dominic Mazzoni]

Created attachment 166314 [details]
Patch

[Dominic Mazzoni]

(In reply to comment #3)
> (From update of attachment 166275 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=166275&action=review
> 
> If the <label> element itself is removed from the tree, how is the m_idToLabelMapping being updated? i couldn't find where that's happening

Ah, you're right - it wasn't. The test was still passing because the AccessibilityObject that was returned was detached. Fixed.

> > Source/WebCore/accessibility/AXObjectCache.h:213
> > +    HashMap<Document*, HashMap<String, HTMLLabelElement*>* > m_idToLabelMapping;
> 
> Can we make HashMap a RefPtr<> so we don't have to worry about deleting it after removing from the cache

Unfortunately no - RefPtr can only be used with classes that have ref() and deref() methods. 

> > Source/WebCore/dom/Document.cpp:635
> >      clearAXObjectCache();
> 
> i think we should try to leverage just one AX method when Document is destroyed to do all the necessary cleanup

The problem is that there's only one ax cache but in a page with iframes, there are lots of Documents. We need to handle the case where an iframe is deleted but the main frame is still there.

> > Source/WebCore/html/HTMLLabelElement.cpp:174
> > +        document()->axObjectCache()->updateLabelElementForId(document(), attribute.value(), this);
> 
> it seems that we will update the cache twice when a forAttr is added (once in willModify with the newValue, then once in attributedChanged)
> Is it possible to do all the updating in attributeChanged, at the cost of perhaps searching the label cache for the correct label element.
> that way, willModify won't have to be come virtual

I can't figure out an easy way to do it in attributeChanged, because attributeChanged doesn't have access to the old value. Instead I was able to get rid of attributeChanged and only handle willModify.

[Early Warning System Bot]

Comment on attachment 166314 [details]
Patch

Attachment 166314 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/14070390

[Early Warning System Bot]

Comment on attachment 166314 [details]
Patch

Attachment 166314 [details] did not pass qt-wk2-ews (qt):
Output: http://queues.webkit.org/results/14071303

[Peter Beverloo (cr-android ews)]

Comment on attachment 166314 [details]
Patch

Attachment 166314 [details] did not pass cr-android-ews (chromium-android):
Output: http://queues.webkit.org/results/14068381

[Dominic Mazzoni]

Created attachment 166411 [details]
Fix compile

[chris fleizach]

Comment on attachment 166411 [details]
Fix compile

View in context: https://bugs.webkit.org/attachment.cgi?id=166411&action=review

I think it looks good from an accessibility perspective. We might want to get someone more familiar with DOM code to ensure that there aren't any other edge cases missed and that virtualizing willModifyAttribute is OK

> Source/WebCore/ChangeLog:19
> +        (WebCore):

remove extraneous (WebCore): lines

> Source/WebCore/dom/Document.cpp:633
> +        topDocument()->m_axObjectCache->documentDestroyed(this);

can we put these two lines into a method like "cleanupAccessibility()" and put clearAXObjectCache() logic in that too

> Source/WebCore/dom/Element.h:320
> +    virtual void willModifyAttribute(const QualifiedName&, const AtomicString& oldValue, const AtomicString& newValue);

we should confirm that making this virtual won't have terrible performance implications

[Ryosuke Niwa]

Comment on attachment 166411 [details]
Fix compile

View in context: https://bugs.webkit.org/attachment.cgi?id=166411&action=review

Sorry, I don't want to be a pain but I don't think we should land the patch as is.

> Source/WebCore/ChangeLog:12
> +        Adds a new accessibility cache that maps ids to label elements
> +        that label that id. The cache is built the first time it's
> +        queried (per document), and then updated every time a label
> +        element on the page is created, deleted, or modified.
> +        This allows for very fast lookup of the label for any element.

We don't normally add new code that's unused. Where is this code used? Or where will it be used?
It seems like we don't need this hash map at all if we had used LabelsNodeList and then made it cache named ids like we do for HTMLCollection.

> Source/WebCore/accessibility/AXObjectCache.cpp:687
> +        HashMap<String, HTMLLabelElement*>* documentMapping = new HashMap<String, HTMLLabelElement*>();

Please use OwnPtr.

[Ryosuke Niwa]

Oops, ignore the following line:
> We don't normally add new code that's unused. Where is this code used? Or where will it be used?

[Dominic Mazzoni]

(In reply to comment #15)
> Sorry, I don't want to be a pain but I don't think we should land the patch as is.

Not a pain. Sorry, I didn't know about LabelsNodeList, I'd be happy to reuse it.

> It seems like we don't need this hash map at all if we had used LabelsNodeList and then made it cache named ids like we do for HTMLCollection.

Agreed. Let me try it and measure the performance.

[Ryosuke Niwa]

For your reference, you can take a look at HTMLCollection::updateNameCache in WebCore/html/HTMLCollection.cpp and DynamicNodeList::itemWithName in WebCore/dom/DynamicNodeList.cpp.

Right now, LabelsNodeList uses DynamicNodeList, which doesn't cache all the labels by id but it's still fast when each id is unique (i.e. there are no elements with the same id) so that might be acceptable for your use case. If not, then we can always transition DynamicNodeList to use the model HTMLCollection uses where we cache the list of all elements with ids/names with a label.

[Dominic Mazzoni]

(In reply to comment #18)
> For your reference, you can take a look at HTMLCollection::updateNameCache in WebCore/html/HTMLCollection.cpp and DynamicNodeList::itemWithName in WebCore/dom/DynamicNodeList.cpp.
> 
> Right now, LabelsNodeList uses DynamicNodeList, which doesn't cache all the labels by id but it's still fast when each id is unique (i.e. there are no elements with the same id) so that might be acceptable for your use case. If not, then we can always transition DynamicNodeList to use the model HTMLCollection uses where we cache the list of all elements with ids/names with a label.

I just tried it, it isn't fast enough.

The case I need to optimize is the m x n case: when the document first loads, every form control needs to find its corresponding label - and then keep it updated as the document mutates.

Caching labels by id (or rather, by the value of the for attr) would work, but the question is, is there any reason that this belongs in DynamicNodeList? Is there any other use inside WebCore for this functionality? If it's only needed for accessibility, I still wonder if it wouldn't be of more use there.

At first glance, HTMLCollection's name cache doesn't look to be as efficient as the hash map in this patch - it only seems to cache from one call to the next, it doesn't maintain a persistent hash map that updates quickly as the document mutates. The solution I built is closer to the cache used in TreeScope::getElementById - it scans the document for all labels once and then updates the map in O(1) time every time a node is attached, detached, or modifies its attributes.

[Ryosuke Niwa]

(In reply to comment #19)
> Caching labels by id (or rather, by the value of the for attr) would work, but the question is, is there any reason that this belongs in DynamicNodeList? Is there any other use inside WebCore for this functionality? If it's only needed for accessibility, I still wonder if it wouldn't be of more use there.
> 
> At first glance, HTMLCollection's name cache doesn't look to be as efficient as the hash map in this patch - it only seems to cache from one call to the next, it doesn't maintain a persistent hash map that updates quickly as the document mutates.

It maintains a persistent map. It clears all the cache and re-populates lazily when the document changes.

> The solution I built is closer to the cache used in TreeScope::getElementById - it scans the document for all labels once and then updates the map in O(1) time every time a node is attached, detached, or modifies its attributes.

I see. Sounds like what you want is DocumentOrderedMap then.

[Dominic Mazzoni]

Created attachment 166786 [details]
Patch

[chris fleizach]

Comment on attachment 166786 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=166786&action=review

looks ok from an ax perspective

> Tools/DumpRenderTree/chromium/TestRunner/AccessibilityUIElementChromium.cpp:744
> +

extraneous newline

[Ryosuke Niwa]

Comment on attachment 166786 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=166786&action=review

This approach looks much better! There are quite few nits but it looks very promising.

> Source/WebCore/dom/Element.cpp:2139
> +    else if (hasTagName(labelTag) && name == HTMLNames::forAttr) {

I would check "name == HTMLNames::forAttr" first to avoid the unnecessary function call to hasTagName.

> Source/WebCore/dom/Element.h:319
> +    void updateForAttr(TreeScope*, const AtomicString& oldForAttr, const AtomicString& newForAttr);

I would have named this function updateLabel.

Also, please don't use the abbreviation "attr" for attribute. "Attr" is a special object in DOM:
http://trac.webkit.org/browser/trunk/Source/WebCore/dom/Attr.idl

> Source/WebCore/dom/TreeScope.cpp:164
> +        RefPtr<NodeList> list = rootNode()->getElementsByTagName("label");

This is very inefficient way of finding label elements. There is a lot of overhead for creating NodeList, etc..
We should traverse nodes directly.

> Source/WebCore/dom/TreeScope.cpp:165
> +        unsigned len = list->length();

In particular, this forces NodeList to iterate through the entire document.

> Source/WebCore/dom/TreeScope.cpp:167
> +            HTMLLabelElement* label = static_cast<HTMLLabelElement*>(list->item(i));

And this second calls to item will traverse the document for the second time.

> Source/WebCore/dom/TreeScope.h:105
> +    // Look up a label element by the id in its "for" attribute, for accessibility.

It seems redundant to put the same comment at two places. Please remove either one.

> LayoutTests/accessibility/title-ui-element-correctness-expected.txt:12
> +PASS control1.titleUIElement().isEqual(label1) is true
> +PASS control2.titleUIElement().isEqual(label2) is true

It's not great that these outputs don't make obvious what we're testing here.

> LayoutTests/accessibility/title-ui-element-correctness.html:10
> +    <label id="l1" for="c1">Label 1</label>
> +    <input id="c1" type="text">

Please don't use one letter ids.

> LayoutTests/accessibility/title-ui-element-correctness.html:54
> +    shouldBe("control1.titleUIElement().isEqual(label1)", "true");

Instead of creating a local variables like this, we can do:
shouldBe('accessibilityController.accessibleElementById("input1").titleUIElement().isEqual(accessibilityController.accessibleElementById("labelForInput1"))', 'true');
so that the expected result is self-explanatory.
Maybe you can make a local helper function for accessibilityController.accessibleElementById; e.g. control().

> LayoutTests/accessibility/title-ui-element-correctness.html:65
> +    document.getElementById("l3").setAttribute("for", "c3");
> +    shouldBe("control3.titleUIElement().isEqual(label3)", "true");

Similarly, it'll be better if you had included the both lines in shouldBe as in:
shouldBe("document.getElementById("l3").setAttribute("for", "c3"); control3.titleUIElement().isEqual(label3)", "true");
(with more descriptive ids for label and input elements).
so that we can see what's happening between two shouldBe.

> LayoutTests/accessibility/title-ui-element-correctness.html:72
> +    var label4Element = document.createElement("label");
> +    label4Element.id = "l4";
> +    label4Element.setAttribute("for", "c4");
> +    label4Element.innerText = "Label 4";

Ditto about putting this in shouldBe. Here, you probably want to create a descriptive helper function like createLabelForInput4WithForAttribute().

> LayoutTests/accessibility/title-ui-element-speed.html:36
> +    // Create a bunch of labels, each of the form:
> +    //   <label for='c0'>Label 0</label>
> +    // Create corresponding controls, each of this form:
> +    //   <input id='c0' type='text'>

This comment repeats what the code tells us. In general, the WebKit community prefers only adding "why" comments.

> LayoutTests/accessibility/title-ui-element-speed.html:62
> +    // Now add more junk to the page. This is to make sure that titleUIElement doesn't take
> +    // time proportional to the number of DOM elements on the page anymore.
> +    for (i = 0; i < 10000; i++) {
> +      var div = document.createElement('div');
> +      div.innerHTML = "<p></p><p></p><p></p><p></p><p></p>";
> +      junkContainer.appendChild(div);
> +    }

It seems like we want to add a test in LayoutTests/perf/ using magnitude-perf.js.

> LayoutTests/accessibility/title-ui-element-speed.html:64
> +    // Save the total time to build the DOM.

This is also obvious from the code.

> LayoutTests/accessibility/title-ui-element-speed.html:65
> +    var midTime = new Date();

It's better to do Date.now() since creating Date object incurs a high runtime cost.

> LayoutTests/accessibility/title-ui-element-speed.html:68
> +    // Now call titleUIElement on each control, and check the correctness of the result.

This comment also repeats the code.

> LayoutTests/accessibility/title-ui-element-speed.html:73
> +            debug("FAIL: control " + i + " has no titleUIElement.");

Please use testFailed.

> LayoutTests/accessibility/title-ui-element-speed.html:78
> +            debug("FAIL: control " + i + " titleUIElement value is '" +

Ditto.

> LayoutTests/accessibility/title-ui-element-speed.html:79
> +                  title + "' , expecting it to end with 'Label " + i + "'");

Wrong indentation. We don't align subsequent lines like this. "title +" should be exactly 4 spaces to the right of "debug(".

> LayoutTests/accessibility/title-ui-element-speed.html:94
> +    if (titleUIElementTime < buildTime) {
> +      debug("PASS Queried titleUIElement in less time than it took to build the DOM.");
> +    } else {

No curly brackets around single statements.

> LayoutTests/accessibility/title-ui-element-speed.html:96
> +            titleUIElementTime + " ms to query titleUIElement on each control.");

Ditto about wrong indentation.

> LayoutTests/accessibility/title-ui-element-speed.html:99
> +    // Remove the labels from the page so the text dump of the page isn't gigantic.

This is also obvious from the code.

[Dominic Mazzoni]

Comment on attachment 166786 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=166786&action=review

>> Source/WebCore/dom/Element.cpp:2139
>> +    else if (hasTagName(labelTag) && name == HTMLNames::forAttr) {
> 
> I would check "name == HTMLNames::forAttr" first to avoid the unnecessary function call to hasTagName.

Good idea, done.

>> Source/WebCore/dom/Element.h:319
>> +    void updateForAttr(TreeScope*, const AtomicString& oldForAttr, const AtomicString& newForAttr);
> 
> I would have named this function updateLabel.
> 
> Also, please don't use the abbreviation "attr" for attribute. "Attr" is a special object in DOM:
> http://trac.webkit.org/browser/trunk/Source/WebCore/dom/Attr.idl

Sure, changed.

>> Source/WebCore/dom/TreeScope.cpp:164
>> +        RefPtr<NodeList> list = rootNode()->getElementsByTagName("label");
> 
> This is very inefficient way of finding label elements. There is a lot of overhead for creating NodeList, etc..
> We should traverse nodes directly.

Fixed.

>> Source/WebCore/dom/TreeScope.h:105
>> +    // Look up a label element by the id in its "for" attribute, for accessibility.
> 
> It seems redundant to put the same comment at two places. Please remove either one.

Kept it by the methods.

>> Tools/DumpRenderTree/chromium/TestRunner/AccessibilityUIElementChromium.cpp:744
>> +
> 
> extraneous newline

Fixed.

>> LayoutTests/accessibility/title-ui-element-correctness-expected.txt:12
>> +PASS control2.titleUIElement().isEqual(label2) is true
> 
> It's not great that these outputs don't make obvious what we're testing here.

titleUIElement() returns an object. This is asserting that it returns the object actually corresponding to the correct label element.

There are a lot of platform-specific differences in accessibility, so at the moment there's no easy way to print the string value of control2.titleUIElement() and assert that it's equal to "Label 1" in a cross-platform way. Chris and I are working on changing that, but for now I think this is the least brittle solution.

>> LayoutTests/accessibility/title-ui-element-correctness.html:10
>> +    <input id="c1" type="text">
> 
> Please don't use one letter ids.

Changed to "label1", "control1", etc.

>> LayoutTests/accessibility/title-ui-element-correctness.html:54
>> +    shouldBe("control1.titleUIElement().isEqual(label1)", "true");
> 
> Instead of creating a local variables like this, we can do:
> shouldBe('accessibilityController.accessibleElementById("input1").titleUIElement().isEqual(accessibilityController.accessibleElementById("labelForInput1"))', 'true');
> so that the expected result is self-explanatory.
> Maybe you can make a local helper function for accessibilityController.accessibleElementById; e.g. control().

Changed throughout.

>> LayoutTests/accessibility/title-ui-element-speed.html:36
>> +    //   <input id='c0' type='text'>
> 
> This comment repeats what the code tells us. In general, the WebKit community prefers only adding "why" comments.

Deleted all extraneous comments

>> LayoutTests/accessibility/title-ui-element-speed.html:62
>> +    }
> 
> It seems like we want to add a test in LayoutTests/perf/ using magnitude-perf.js.

Neat, I hadn't tried writing one of those before. Added a complementary test.

I'm a little hesitant to use that test instead, because I'm finding the perf tests to be flaky - not just the one I added, but others are failing a small fraction of the time.

>> LayoutTests/accessibility/title-ui-element-speed.html:65
>> +    var midTime = new Date();
> 
> It's better to do Date.now() since creating Date object incurs a high runtime cost.

Fixed throughout

>> LayoutTests/accessibility/title-ui-element-speed.html:73
>> +            debug("FAIL: control " + i + " has no titleUIElement.");
> 
> Please use testFailed.

Fixed throughout

>> LayoutTests/accessibility/title-ui-element-speed.html:79
>> +                  title + "' , expecting it to end with 'Label " + i + "'");
> 
> Wrong indentation. We don't align subsequent lines like this. "title +" should be exactly 4 spaces to the right of "debug(".

Fixed.

>> LayoutTests/accessibility/title-ui-element-speed.html:94
>> +    } else {
> 
> No curly brackets around single statements.

Fixed

>> LayoutTests/accessibility/title-ui-element-speed.html:96
>> +            titleUIElementTime + " ms to query titleUIElement on each control.");
> 
> Ditto about wrong indentation.

Fixed

>> LayoutTests/accessibility/title-ui-element-speed.html:99
>> +    // Remove the labels from the page so the text dump of the page isn't gigantic.
> 
> This is also obvious from the code.

I think this comment is a "why" comment, ok to leave it?

[Dominic Mazzoni]

Created attachment 167864 [details]
Patch

[Ryosuke Niwa]

Comment on attachment 167864 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=167864&action=review

> Source/WebCore/dom/Element.cpp:2125
> +    if (!inDocument())
> +        return;

I forgot to comment on the previous patch but why does it need to be in the document?
Surely, you can remove a TreeScope that used to be in the document and has the map?
If we stop updating the map at the point, it may go stale and introduce a subtle security bug down the road.
For that reason, I would prefer checking the existence of m_labelsByForAttr instead.

> Source/WebCore/dom/TreeScope.cpp:159
> +HTMLLabelElement* TreeScope::getLabel(const AtomicString& forAttrValue)

"get" prefix is used only for functions with out arguments: http://www.webkit.org/coding/coding-style.html#names-out-argument
I would call this function labelElementForId.

> Source/WebCore/dom/TreeScope.cpp:164
> +        for (Node* node = root; node; node = node->traverseNextNode(root)) {

You shouldn't need to pass in root to traverseNextNode since traverseNextNode doesn't cross shadow boundary by default.

> Source/WebCore/dom/TreeScope.h:66
> +    // Look up a label element by the id in its "for" attribute, for accessibility.

I would just say it's for accessibility because the fact it looks up a label element by an id is obvious from the code.

> Source/WebCore/dom/TreeScope.h:70
> +    // m_shouldCacheLabelsByForAttr is set to true when this method is called the first time.

This comment repeats an implementation detail that's obvious from the code. Please remove it.

> LayoutTests/accessibility/title-ui-element-correctness.html:34
> +  </div>

Please add a test case where there are multiple label elements with the same "for" value.
And make sure that adding and removing such elements update the map correctly.

> LayoutTests/accessibility/title-ui-element-speed.html:17
> +if (window.testRunner && window.accessibilityController) {

I still think we should just use magnitude-perf.js. Granted, some tests are flaky but that's a problem with the tests, not the framework itself.
If the framework is making some tests flaky, then we should fix the framework instead of re-implementing it in each test.

[Dominic Mazzoni]

> Please add a test case where there are multiple label elements with the same "for" value.
> And make sure that adding and removing such elements update the map correctly.

I just realized the spec allows multiple label elements to point to the same form control. It looks like I need to modify DocumentOrderedMap to return all matching nodes.

- Dominic

[Ryosuke Niwa]

(In reply to comment #27)
> > Please add a test case where there are multiple label elements with the same "for" value.
> > And make sure that adding and removing such elements update the map correctly.
> 
> I just realized the spec allows multiple label elements to point to the same form control. It looks like I need to modify DocumentOrderedMap to return all matching nodes.

Is that what spec says? As far as I know, the first label element with the matching "for" attribute supersedes other label elements with the same for attribute.

[Dominic Mazzoni]

(In reply to comment #28)
> (In reply to comment #27)
> > > Please add a test case where there are multiple label elements with the same "for" value.
> > > And make sure that adding and removing such elements update the map correctly.
> > 
> > I just realized the spec allows multiple label elements to point to the same form control. It looks like I need to modify DocumentOrderedMap to return all matching nodes.
> 
> Is that what spec says? As far as I know, the first label element with the matching "for" attribute supersedes other label elements with the same for attribute.

w3c says: More than one LABEL may be associated with the same control by creating multiple references via the for attribute.
http://www.w3.org/TR/html401/interact/forms.html#h-17.9.1

The html5 accessibility pages notes that it's conforming, and Firefox supports multiple labels, concatenating their strings for accessibility - but they recommend against authors using it because some assistive technology and other user agents don't support it:
http://www.html5accessibility.com/tests/mulitple-labels.html

There's also the "labels" attribute of a labelable element, which returns *all* labels associated with a given control.

I guess it's fine to just use the first one.

[Dominic Mazzoni]

> I guess it's fine to just use the first one.

To clarify, I'm mostly swayed by the fact that Firefox has implemented its interpretation of the spec but authors are still discouraged from using the feature because it could make things worse rather than better.
http://www.html5accessibility.com/tests/mulitple-labels.html

In addition, the platform accessibility implementation guide is noticeably silent on it, as far as I can tell - it only mentions one label:
http://dvcs.w3.org/hg/html-api-map/raw-file/tip/Overview.html

[Dominic Mazzoni]

Created attachment 167935 [details]
Patch

[Dominic Mazzoni]

Created attachment 167936 [details]
Patch

[Dominic Mazzoni]

View in context: https://bugs.webkit.org/attachment.cgi?id=167864&action=review

>> Source/WebCore/dom/Element.cpp:2125
>> +        return;
> 
> I forgot to comment on the previous patch but why does it need to be in the document?
> Surely, you can remove a TreeScope that used to be in the document and has the map?
> If we stop updating the map at the point, it may go stale and introduce a subtle security bug down the road.
> For that reason, I would prefer checking the existence of m_labelsByForAttr instead.

Good point. I removed the inDocument check here and added it to getLabel (now labelElementForId).

I don't think there's a need to check m_labelsByForAttr again, it's checked in the callers - which seems more efficient.

>> Source/WebCore/dom/TreeScope.cpp:159
>> +HTMLLabelElement* TreeScope::getLabel(const AtomicString& forAttrValue)
> 
> "get" prefix is used only for functions with out arguments: http://www.webkit.org/coding/coding-style.html#names-out-argument
> I would call this function labelElementForId.

Fixed.

>> Source/WebCore/dom/TreeScope.cpp:164
>> +        for (Node* node = root; node; node = node->traverseNextNode(root)) {
> 
> You shouldn't need to pass in root to traverseNextNode since traverseNextNode doesn't cross shadow boundary by default.

Fixed.

>> Source/WebCore/dom/TreeScope.h:66
>> +    // Look up a label element by the id in its "for" attribute, for accessibility.
> 
> I would just say it's for accessibility because the fact it looks up a label element by an id is obvious from the code.

Done.

>> Source/WebCore/dom/TreeScope.h:70
>> +    // m_shouldCacheLabelsByForAttr is set to true when this method is called the first time.
> 
> This comment repeats an implementation detail that's obvious from the code. Please remove it.

You don't think it's useful to mention that there's an added performance cost from then on if this method is called?

>> LayoutTests/accessibility/title-ui-element-correctness.html:34
>> +  </div>
> 
> Please add a test case where there are multiple label elements with the same "for" value.
> And make sure that adding and removing such elements update the map correctly.

Done. That was a good catch, I needed to make changes to DocumetOrderedMap.

>> LayoutTests/accessibility/title-ui-element-speed.html:17
>> +if (window.testRunner && window.accessibilityController) {
> 
> I still think we should just use magnitude-perf.js. Granted, some tests are flaky but that's a problem with the tests, not the framework itself.
> If the framework is making some tests flaky, then we should fix the framework instead of re-implementing it in each test.

Done.

[Ryosuke Niwa]

Comment on attachment 167936 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=167936&action=review

> LayoutTests/accessibility/title-ui-element-correctness-expected.txt:6
> +Label 1  
> +Label 2  
> +Label 3  
> +
> +Label 5  
> +Label 6b Label 6c  

Please hide these once the test is done to avoid cluttering the test output.
Namely, you can set display: none on #container or clear its innerHTML.

[Dominic Mazzoni]

Created attachment 168269 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 168269 [details]
Patch for landing

Rejecting attachment 168269 [details] from commit-queue.

Failed to run "['/mnt/git/webkit-commit-queue/Tools/Scripts/webkit-patch', '--status-host=queues.webkit.org', '-..." exit_code: 2

Last 500 characters of output:
i.html
patching file LayoutTests/accessibility/title-ui-element-correctness-expected.txt
patching file LayoutTests/accessibility/title-ui-element-correctness.html
patching file LayoutTests/perf/accessibility-title-ui-element-expected.txt
patching file LayoutTests/perf/accessibility-title-ui-element.html
patching file LayoutTests/platform/chromium/TestExpectations

Failed to run "[u'/mnt/git/webkit-commit-queue/Tools/Scripts/svn-apply', u'--force']" exit_code: 1 cwd: /mnt/git/webkit-commit-queue

Full output: http://queues.webkit.org/results/14250839

[Dominic Mazzoni]

Created attachment 168278 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 168278 [details]
Patch for landing

Clearing flags on attachment: 168278

Committed r131107: <http://trac.webkit.org/changeset/131107>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[Adam Barth]

This patch causes an ASSERT.

crash log for DumpRenderTree (pid 13686):
STDOUT: <empty>
STDERR: SHOULD NEVER BE REACHED
STDERR: third_party/WebKit/Source/WebCore/dom/DocumentOrderedMap.cpp(136) : WebCore::Element* WebCore::DocumentOrderedMap::get(WTF::AtomicStringImpl*, const WebCore::TreeScope*) const [with bool (* keyMatches)(WTF::AtomicStringImpl*, WebCore::Element*) = WebCore::keyMatchesLabelForAttribute]
STDERR: 1   0x7f41298b1aa1
STDERR: 2   0x7f41298b0c7f
STDERR: 3   0x7f412996bac6
STDERR: 4   0x7f4129fd9de8
STDERR: 5   0x7f4129fe8a54
STDERR: 6   0x7f4128f5efba WebKit::WebAccessibilityObject::titleUIElement() const
STDERR: 7   0x4ed593
STDERR: 8   0x4ef528
STDERR: 9   0x4effc4
STDERR: 10  0x4ef6a3
STDERR: 11  0x7f412a052d73
STDERR: 12  0x7f412a052f1a
STDERR: 13  0x7f4126f0680e
STDERR: 14  0x7f4126f01429
STDERR: 15  0x7f4126f013fa
STDERR: 16  0x1eec34c0618e
STDERR: [13686:13686:17469496058466:ERROR:process_util_posix.cc(144)] Received signal 11
STDERR: 	base::debug::StackTrace::StackTrace() [0x7f4126a81ff2]
STDERR: 	base::(anonymous namespace)::StackDumpSignalHandler() [0x7f4126aec4d1]
STDERR: 	0x7f411fd09af0
STDERR: 	WebCore::DocumentOrderedMap::get<>() [0x7f41298b1aab]
STDERR: 	WebCore::DocumentOrderedMap::getElementByLabelForAttribute() [0x7f41298b0c7f]
STDERR: 	WebCore::TreeScope::labelElementForId() [0x7f412996bac6]
STDERR: 	WebCore::AccessibilityNodeObject::labelForElement() [0x7f4129fd9de8]
STDERR: 	WebCore::AccessibilityRenderObject::titleUIElement() [0x7f4129fe8a54]
STDERR: 	WebKit::WebAccessibilityObject::titleUIElement() [0x7f4128f5efba]
STDERR: 	AccessibilityUIElement::titleUIElementCallback() [0x4ed593]
STDERR: 	CppBoundClass::MemberCallback<>::run() [0x4ef528]
STDERR: 	CppBoundClass::invoke() [0x4effc4]
STDERR: 	CppNPObject::invoke() [0x4ef6a3]
STDERR: 	WebCore::npObjectInvokeImpl() [0x7f412a052d73]
STDERR: 	WebCore::npObjectMethodHandler() [0x7f412a052f1a]
STDERR: 	v8::internal::HandleApiCallHelper<>() [0x7f4126f0680e]
STDERR: 	v8::internal::Builtin_Impl_HandleApiCall() [0x7f4126f01429]
STDERR: 	v8::internal::Builtin_HandleApiCall() [0x7f4126f013fa]
STDERR: 	0x1eec34c0618e

[WebKit Review Bot]

Re-opened since this is blocked by bug 99126

[Dominic Mazzoni]

Created attachment 169046 [details]
Patch

[Dominic Mazzoni]

Ryosuke, could you take another look?

You suggested that I update the label map whether or not an element is in the document or not, but that breaks a DocumentOrderedMap assertion, and I don't think DocumentOrderedMap is intended to be used that way. It should only keep track of elements actually in the document.

I put the code basically back the way I had it, and I think it's correct. The label gets added to the map when the element is inserted into the tree, it gets updated when an attribute changes (but only if it's in the document at that time), and it gets removed from the map when the element is removed from the tree.

The test covers these cases, it fails if I take any of these out.

What do you think?

- Dominic

[Build Bot]

Comment on attachment 169046 [details]
Patch

Attachment 169046 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/14392328

[Ryosuke Niwa]

Comment on attachment 169046 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=169046&action=review

> Tools/ChangeLog:883
> +=======
> +>>>>>>> 97825 merged

Something is wrong with this patch.

[Dominic Mazzoni]

Created attachment 169074 [details]
Patch

[Dominic Mazzoni]

(In reply to comment #45)
> > +>>>>>>> 97825 merged
> Something is wrong with this patch.

Argh, sorry about that. Fixed.

[WebKit Review Bot]

Comment on attachment 169074 [details]
Patch

Rejecting attachment 169074 [details] from commit-queue.

Failed to run "['/mnt/git/webkit-commit-queue/Tools/Scripts/webkit-patch', '--status-host=queues.webkit.org', '-..." exit_code: 2

Last 500 characters of output:
ibility/title-ui-element-correctness.html
patching file LayoutTests/perf/accessibility-title-ui-element-expected.txt
patching file LayoutTests/perf/accessibility-title-ui-element.html
patching file LayoutTests/platform/chromium/TestExpectations
Hunk #1 succeeded at 1402 (offset -5 lines).
Hunk #2 succeeded at 1415 (offset -5 lines).

Failed to run "[u'/mnt/git/webkit-commit-queue/Tools/Scripts/svn-apply', u'--force', u'--reviewer', u'Ryosuke Ni..." exit_code: 1 cwd: /mnt/git/webkit-commit-queue

Full output: http://queues.webkit.org/results/14412827

[Dominic Mazzoni]

Created attachment 169562 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 169562 [details]
Patch for landing

Rejecting attachment 169562 [details] from commit-queue.

Failed to run "['/mnt/git/webkit-commit-queue/Tools/Scripts/webkit-patch', '--status-host=queues.webkit.org', '-..." exit_code: 2

Last 500 characters of output:
mpRenderTree/chromium/TestRunner/AccessibilityUIElementChromium.cpp.rej
patching file LayoutTests/ChangeLog
Hunk #1 succeeded at 1 with fuzz 3.
patching file LayoutTests/accessibility/secure-textfield-title-ui.html
patching file LayoutTests/platform/chromium/TestExpectations
Hunk #1 succeeded at 1402 (offset -5 lines).
Hunk #2 succeeded at 1415 (offset -5 lines).

Failed to run "[u'/mnt/git/webkit-commit-queue/Tools/Scripts/svn-apply', u'--force']" exit_code: 1 cwd: /mnt/git/webkit-commit-queue

Full output: http://queues.webkit.org/results/14456378

[Dominic Mazzoni]

Created attachment 169566 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 169566 [details]
Patch for landing

Rejecting attachment 169566 [details] from commit-queue.

Failed to run "['/mnt/git/webkit-commit-queue/Tools/Scripts/webkit-patch', '--status-host=queues.webkit.org', '-..." exit_code: 1

ERROR: /mnt/git/webkit-commit-queue/Source/WebKit/chromium/ChangeLog neither lists a valid reviewer nor contains the string "Unreviewed" or "Rubber stamp" (case insensitive).

Full output: http://queues.webkit.org/results/14424863

[Dominic Mazzoni]

Committed r131871: <http://trac.webkit.org/changeset/131871>

[Roger Fong]

Still crashes on Windows.
See http://build.webkit.org/results/Apple%20Win%207%20Release%20(Tests)/r132381%20(29225)/results.html.

Is this another one of those should be skipped on Windows accessibility tests? I'm wondering if we should have some sort of accessibility feature so we can disable these things on Windows since I don't think anyone is working on accessibility support for that port.

[Dominic Mazzoni]

Since there's no owner, I think it might make sense to skip all of the accessibility tests on Windows.

If a non-accessibility test crashes as a result of accessibility code (definitely possible), that should obviously be fixed. But actually running the accessibility tests doesn't make much sense anymore.