Bug 239406 – Optimize id matching in AccessibilityObject::ariaElementsReferencedByAttribute()

• Status: RESOLVED
• Resolution: FIXED
• Component: Accessibility

[Chris Dumez]

Optimize id matching in AccessibilityObject::ariaElementsReferencedByAttribute().

[Radar WebKit Bug Importer]

<rdar://problem/91829358>

[Chris Dumez]

Created attachment 457726 [details]
Patch

[Darin Adler]

Comment on attachment 457726 [details]
Patch

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

> Source/WebCore/accessibility/AccessibilityObject.cpp:3932
> +        if (!SpaceSplitString::spaceSplitStringContainsValue(idList, id))
>              continue;

If we are going to walk an entire DOM tree and check every attribute value against a set, I think we should probably convert it into a HashSet<AtomString>, don’t you?

[Chris Dumez]

Comment on attachment 457726 [details]
Patch

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

>> Source/WebCore/accessibility/AccessibilityObject.cpp:3932
>>              continue;
> 
> If we are going to walk an entire DOM tree and check every attribute value against a set, I think we should probably convert it into a HashSet<AtomString>, don’t you?

I don't understand the comment and how I can leverage a HashSet<AtomString>.

We have a string stored in the variable 'id', we want to iterate the whole DOM tree and find all Elements that have that id string in their attribute |attribute| (which is one of the few aria- attributes). Another tricky thing is that apparently, the value of |attribute| is a HTMLSpace-separated string and we want to know if any of the substrings in that attribute value match the string stored in id.
Seems to me that the implementation I have now is pretty efficient given the current constraints?

Ideally, at some point, we wouldn't need to iterate the whole DOM tree and we'd know which elements may match ahead of time. I talked to Tyler about that and he said that's on his TODO list.

[Darin Adler]

Comment on attachment 457726 [details]
Patch

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

>>> Source/WebCore/accessibility/AccessibilityObject.cpp:3932
>>>              continue;
>> 
>> If we are going to walk an entire DOM tree and check every attribute value against a set, I think we should probably convert it into a HashSet<AtomString>, don’t you?
> 
> I don't understand the comment and how I can leverage a HashSet<AtomString>.
> 
> We have a string stored in the variable 'id', we want to iterate the whole DOM tree and find all Elements that have that id string in their attribute |attribute| (which is one of the few aria- attributes). Another tricky thing is that apparently, the value of |attribute| is a HTMLSpace-separated string and we want to know if any of the substrings in that attribute value match the string stored in id.
> Seems to me that the implementation I have now is pretty efficient given the current constraints?
> 
> Ideally, at some point, we wouldn't need to iterate the whole DOM tree and we'd know which elements may match ahead of time. I talked to Tyler about that and he said that's on his TODO list.

Oh, I didn’t realize that the attributes from each element were the things we're splitting!

[Chris Dumez]

(In reply to Chris Dumez from comment #4)
> Comment on attachment 457726 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=457726&action=review
> 
> >> Source/WebCore/accessibility/AccessibilityObject.cpp:3932
> >>              continue;
> > 
> > If we are going to walk an entire DOM tree and check every attribute value against a set, I think we should probably convert it into a HashSet<AtomString>, don’t you?
> 
> I don't understand the comment and how I can leverage a HashSet<AtomString>.
> 
> We have a string stored in the variable 'id', we want to iterate the whole
> DOM tree and find all Elements that have that id string in their attribute
> |attribute| (which is one of the few aria- attributes). Another tricky thing
> is that apparently, the value of |attribute| is a HTMLSpace-separated string
> and we want to know if any of the substrings in that attribute value match
> the string stored in id.
> Seems to me that the implementation I have now is pretty efficient given the
> current constraints?
> 
> Ideally, at some point, we wouldn't need to iterate the whole DOM tree and
> we'd know which elements may match ahead of time. I talked to Tyler about
> that and he said that's on his TODO list.

I think the misunderstanding may be that each Element in the DOM tree has a list of ids as a space-separate attribute value, and we're matching them against a single id string.

If it was the other way around (each element has a single id and we need to match against a list of ids we have), then a HashSet<AtomString> for the list of ids we have would totally make sense.

[Darin Adler]

(In reply to Chris Dumez from comment #6)
> I think the misunderstanding may be that each Element in the DOM tree has a
> list of ids as a space-separate attribute value, and we're matching them
> against a single id string.

Yes, that was it.

[EWS]

Committed r292943 (249708@main): <https://commits.webkit.org/249708@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 457726 [details].