Bug 240842 – AX: Refactor implementation of AX object relationships.

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

[Andres Gonzalez]

Relationships between AX objects are computed by the methods 
AccessibilityObject::ariaElementsFromAttribute and 
ariaElementsReferencedByAttribute, both of which performed walks of the DOM tree
to match ids between origin and target of a specific relationship, having a 
significant performance impact when called repeatedly.

[Radar WebKit Bug Importer]

<rdar://problem/93795592>

[Andres Gonzalez]

Created attachment 459692 [details]
Patch

[chris fleizach]

Comment on attachment 459692 [details]
Patch

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

> COMMIT_MESSAGE:1
> +Relationships between AX objects were being computed by the methods AccessibilityObject::ariaElementsFromAttribute and
 ariaElementsReferencedByAttribute, both of which performed walks of the DOM
 tree to match ids between origin and target of a specific relationship,
 having a significant performance impact when called repeatedly. With this
 patch, these two methods are replaced with a single method,
 AccessibilityObject::relatedObjects, that in turn calls
 AXObjectCache::relatedObjectsFor. This AXObjectCache method computes and
 caches all relationships in one walk of the DoM tree. The cache is updated
 when relevant event notifications are received. This makes support of
 relationships between objects more efficient, and the code clearer. The test
 added exercises this implementation of relationships via the aria-owns
 attribute to relate table rows to their cells. The execution time of this
 test before this change was estimated in one system at about 2.30s, and after
 the change was redueced to 1.92s.

redueced -> reduced

> LayoutTests/accessibility/grid-with-aria-owned-cells.html:12
> +    <div id="row1" role="row" aria-owns="cell-1-1 cell-1-2 cell-1-3 cell-1-4 cell-1-5 cell-1-6 cell-1-7 cell-1-8 cell-1-9 cell-1-10 cell-1-11 cell-1-12 cell-1-13 cell-1-14 cell-1-15 cell-1-16 cell-1-17 cell-1-18 cell-1-19 cell-1-20 cell-1-21 cell-1-22 cell-1-23 cell-1-24 cell-1-25 cell-1-26 cell-1-27 cell-1-28"></div>

can we cut down this test? event 1.9 seconds seems like a long time to test correctness for a test. Maybe we can just have 4-5 rows on this table to verify it works correctly?

[Andres Gonzalez]

Created attachment 459715 [details]
Patch

[Andres Gonzalez]

(In reply to chris fleizach from comment #3)
> Comment on attachment 459692 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=459692&action=review
> 
> > COMMIT_MESSAGE:1
> > +Relationships between AX objects were being computed by the methods AccessibilityObject::ariaElementsFromAttribute and
>  ariaElementsReferencedByAttribute, both of which performed walks of the DOM
>  tree to match ids between origin and target of a specific relationship,
>  having a significant performance impact when called repeatedly. With this
>  patch, these two methods are replaced with a single method,
>  AccessibilityObject::relatedObjects, that in turn calls
>  AXObjectCache::relatedObjectsFor. This AXObjectCache method computes and
>  caches all relationships in one walk of the DoM tree. The cache is updated
>  when relevant event notifications are received. This makes support of
>  relationships between objects more efficient, and the code clearer. The test
>  added exercises this implementation of relationships via the aria-owns
>  attribute to relate table rows to their cells. The execution time of this
>  test before this change was estimated in one system at about 2.30s, and
> after
>  the change was redueced to 1.92s.
> 
> redueced -> reduced

Fixed.
> 
> > LayoutTests/accessibility/grid-with-aria-owned-cells.html:12
> > +    <div id="row1" role="row" aria-owns="cell-1-1 cell-1-2 cell-1-3 cell-1-4 cell-1-5 cell-1-6 cell-1-7 cell-1-8 cell-1-9 cell-1-10 cell-1-11 cell-1-12 cell-1-13 cell-1-14 cell-1-15 cell-1-16 cell-1-17 cell-1-18 cell-1-19 cell-1-20 cell-1-21 cell-1-22 cell-1-23 cell-1-24 cell-1-25 cell-1-26 cell-1-27 cell-1-28"></div>
> 
> can we cut down this test? event 1.9 seconds seems like a long time to test
> correctness for a test. Maybe we can just have 4-5 rows on this table to
> verify it works correctly?

Reduced the table to 5 rows and re-estimated the execution times. However the times given here include the initialization of run-webkit-tests, so the actual test execution is a small fraction of the ~2s. With a smaller table, the variability is higher relative to the difference in performance before and after the change. But in any case this is not a performance test, I was just trying to get a sense of that there was a real performance improvement, so I'm fine with the small table as suggested.

[Andres Gonzalez]

Created attachment 459758 [details]
Patch

[Andres Gonzalez]

Latest patch addresses the issue of not updating the relations cache when any of the relation attributes change.

[chris fleizach]

Comment on attachment 459758 [details]
Patch

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

> Source/WebCore/accessibility/AXObjectCache.cpp:3643
> +    return relationAttributes;

is this more concise as

static NeverDestroyed<Vector<QualifiedName>> relationAttributes = Vector<QualifiedName>({
    aria_activedescendantAttr,
    ....
});

return relationAttributes

> Source/WebCore/accessibility/AXObjectCache.cpp:3778
> +            for (size_t i = 0; i < ids.size(); ++i)

can this be 
for (auto idString in ids)

[Andres Gonzalez]

Created attachment 459761 [details]
Patch

[Andres Gonzalez]

(In reply to chris fleizach from comment #8)
> Comment on attachment 459758 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=459758&action=review
> 
> > Source/WebCore/accessibility/AXObjectCache.cpp:3643
> > +    return relationAttributes;
> 
> is this more concise as
> 
> static NeverDestroyed<Vector<QualifiedName>> relationAttributes =
> Vector<QualifiedName>({
>     aria_activedescendantAttr,
>     ....
> });
> 
> return relationAttributes

Yes! thanks for pointing out.

> 
> > Source/WebCore/accessibility/AXObjectCache.cpp:3778
> > +            for (size_t i = 0; i < ids.size(); ++i)
> 
> can this be 
> for (auto idString in ids)

No, range iteration over SpaceSplitString doesn't work because the class doesn't have begin() / end():

error: invalid range expression of type 'WebCore::SpaceSplitString'; no viable 'begin' function available.

[Andres Gonzalez]

Created attachment 459766 [details]
Patch

Skipping test in win.

[Andres Gonzalez]

Created attachment 459783 [details]
Patch

Re-uploading for iOS bogus test failure.

[EWS]

Committed r294878 (251008@main): <https://commits.webkit.org/251008@main>

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

[Don Olmstead]

Follow up at https://bugs.webkit.org/show_bug.cgi?id=240976 for !ENABLE(ACCESSIBILITY) build issue.