Bug 233383 – AX: aria-owns in trees results duplicate rows, third level rows not being exposed

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

[Sepand Parhami]

Created attachment 444850 [details]
A reproducing example

When you link children of a tree node via `aria-owns`, none of their children are exposed. That is, in the following snippet:

```
<div role="tree" tabindex="0">
    <div role="treeitem" aria-selected="false" aria-expanded="true" aria-level="1">
        <div>Folder one</div>
        <div role="group" aria-owns="item1"></div>
    </div>

    <div id="item1" role="treeitem" aria-selected="false" aria-expanded="true" aria-level="2">
        <div>Child one</div>
        <div role="group">
            <div role="treeitem" aria-selected="false" aria-level="3">
                <div>Grandchild one</div>
            </div>
        </div>
    </div>
</div>
```

Steps To Reproduce:
1. Open the attached `example.html`
2. Navigate to the first table
3. Enter the first table 
4. Go to next item -> “Child one expanded…”
5. Go to next item -> “Child two”

Results:
At step 5, I expect VoiceOver to move to “Grandchild one” and not “Child two”.


Notes:
- Safari does read “Child one, expanded. 1 item enclosed.”, when the VoiceOver cursor moves there, so it seems like it does know about the child, it just doesn’t navigate there.

[Radar WebKit Bug Importer]

<rdar://problem/85618602>

[Sepand Parhami]

Created attachment 444857 [details]
Patch

[Tyler Wilcock]

Comment on attachment 444857 [details]
Patch

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

Thanks for the patch!

> Source/WebCore/accessibility/AccessibilityObject.cpp:1841
> +            // treeitem sitting under the tree root, which is owned elsewhere in the tree.

Typo, seems like you're missing "a".

treeitem -> a treeitem

> LayoutTests/accessibility/mac/treeitem-row-delegation.html:13
> +        <div role="group" aria-owns="group1-item2 group1-item3 group1-item4">

There is no element with an id of group1-item4. Is that intentional?

[Tyler Wilcock]

Does this patch make us more susceptible to circular element references?

https://w3c.github.io/aria/#aria-owns

> Authors MUST ensure that an element's ID is not specified in more than one other element's aria-owns attribute at any time. In other words, an element can have only one explicit owner. Authors MUST NOT create circular references with aria-owns. In the case of authoring error with aria-owns, the user agent MAY ignore some aria-owns element references in order to build a consistent model of the content.

[Sepand Parhami]

Created attachment 445585 [details]
Patch

[Sepand Parhami]

(In reply to Tyler Wilcock from comment #3)
> Comment on attachment 444857 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=444857&action=review
> 
> Thanks for the patch!
> 
> > Source/WebCore/accessibility/AccessibilityObject.cpp:1841
> > +            // treeitem sitting under the tree root, which is owned elsewhere in the tree.
> 
> Typo, seems like you're missing "a".
> 
> treeitem -> a treeitem
> 

Thanks, fixed!

> > LayoutTests/accessibility/mac/treeitem-row-delegation.html:13
> > +        <div role="group" aria-owns="group1-item2 group1-item3 group1-item4">
> 
> There is no element with an id of group1-item4. Is that intentional?

I changed the id here, I believe the intent of the test here previously was to test that an id referencing a non-existent element does not cause issues. Made this more clear.

[Sepand Parhami]

(In reply to Tyler Wilcock from comment #3)
> Comment on attachment 444857 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=444857&action=review
> 
> Thanks for the patch!
> 
> > Source/WebCore/accessibility/AccessibilityObject.cpp:1841
> > +            // treeitem sitting under the tree root, which is owned elsewhere in the tree.
> 
> Typo, seems like you're missing "a".
> 
> treeitem -> a treeitem
> 

Thanks, fixed!

> > LayoutTests/accessibility/mac/treeitem-row-delegation.html:13
> > +        <div role="group" aria-owns="group1-item2 group1-item3 group1-item4">
> 
> There is no element with an id of group1-item4. Is that intentional?

I changed the id here, I believe the intent of the test here previously was to test that an id referencing a non-existent element does not cause issues. Made this more clear.

[Sepand Parhami]

(In reply to Tyler Wilcock from comment #4)
> Does this patch make us more susceptible to circular element references?
> 
> https://w3c.github.io/aria/#aria-owns
> 
> > Authors MUST ensure that an element's ID is not specified in more than one other element's aria-owns attribute at any time. In other words, an element can have only one explicit owner. Authors MUST NOT create circular references with aria-owns. In the case of authoring error with aria-owns, the user agent MAY ignore some aria-owns element references in order to build a consistent model of the content.

I think with this patch as-is, a circular reference would be a problem. I think my original approach was okay, but this I think this part is a problem:

```
            // Hopefully a flow that does not occur often in practice, but if someone were to include
            // the owned child ealier in the top level of the tree, then reference via aria-owns later,
            // move it to the right place.
            if (result.contains(child))
                result.removeFirst(child);
 ```

Originally, I skipped here, but in order to handle out of order tree items, I added this logic. Need to re-evaluate my approach here.

[Sepand Parhami]

(In reply to Tyler Wilcock from comment #4)
> Does this patch make us more susceptible to circular element references?
> 
> https://w3c.github.io/aria/#aria-owns
> 
> > Authors MUST ensure that an element's ID is not specified in more than one other element's aria-owns attribute at any time. In other words, an element can have only one explicit owner. Authors MUST NOT create circular references with aria-owns. In the case of authoring error with aria-owns, the user agent MAY ignore some aria-owns element references in order to build a consistent model of the content.

I think with this patch as-is, a circular reference would be a problem. I think my original approach was okay, but this I think this part is a problem:

```
            // Hopefully a flow that does not occur often in practice, but if someone were to include
            // the owned child ealier in the top level of the tree, then reference via aria-owns later,
            // move it to the right place.
            if (result.contains(child))
                result.removeFirst(child);
 ```

Originally, I skipped here, but in order to handle out of order tree items, I added this logic. Need to re-evaluate my approach here.

[Tyler Wilcock]

FWIW, I think we only need to be concerned about not crashing when the author makes the mistake of a circular reference. I tested a circular aria-owns reference on `main`-branch WebKit and couldn't get a crash, so we just need to make sure that this patch doesn't make us susceptible to it.

One option would be to create a separate test with an intentional circular reference, and to call it passing if it doesn't crash.

Thanks for digging into this!

[Sepand Parhami]

Created attachment 445795 [details]
Patch

[Sepand Parhami]

(In reply to Tyler Wilcock from comment #10)
> FWIW, I think we only need to be concerned about not crashing when the
> author makes the mistake of a circular reference. I tested a circular
> aria-owns reference on `main`-branch WebKit and couldn't get a crash, so we
> just need to make sure that this patch doesn't make us susceptible to it.
> 
> One option would be to create a separate test with an intentional circular
> reference, and to call it passing if it doesn't crash.
> 
> Thanks for digging into this!

I had to rework things a bit, but I'm unsure about the approach I took. I pulled out the logic to get the children considering aria-owns into a separate piece. Would be happy to try another path if it makes more sense.

One thing that I'm unsure about is if/how to support `aria-owns` in general. It seems for that case, the general tree structure (i.e. children, parentObject, nextSibling, etc) may need to be modified to account for aria-owns (or provide separate functions to access those and use those instead). I'm don't think this patch  useful step in that direction, though I would be happy with improving support for aria-owns in trees/lists/tables/grids if the larger work is large in scope.

I added a circular reference to the existing test case, but can make it a separate file if that makes more sense.

[Sepand Parhami]

Created attachment 445919 [details]
Patch

[Sepand Parhami]

Created attachment 445924 [details]
Patch

[Tyler Wilcock]

Comment on attachment 445924 [details]
Patch

This would be a progression in terms of behavior, and probably a good step towards improving aria-owns support for all elements, but I worry that the performance might be untenable. With this latest patch, we call ariaOwnsReferencingElements for each DOM and aria-owns child. Our implementation of ariaOwnsReferencingElements does a scan of every element starting from the root. So for a tree with a lot of children, and given a large document, I image this could cause performance issues.

It's unfortunate that we don't have an efficient way to find ariaOwnsReferencingElements. Ideally we would cache this somewhere as we build the tree, and then these lookups would be fast. But that would probably be a big project.

> I added a circular reference to the existing test case, but can make it a separate file if that makes more sense.
I would prefer a separate file so there's a clear distinction that accessibility/mac/treeitem-row-delegation.html tests the behavior of a well-formed tree, while this other test specifically ensures we don't crash with a circular reference.

Was this version of the patch[1] vulnerable to circular references based on the circular reference test case you added in your latest patch?

[1]: https://bugs.webkit.org/attachment.cgi?id=445585&action=prettypatch

[Sepand Parhami]

(In reply to Tyler Wilcock from comment #15)
> Comment on attachment 445924 [details]
> Patch
> 
> This would be a progression in terms of behavior, and probably a good step
> towards improving aria-owns support for all elements, but I worry that the
> performance might be untenable. With this latest patch, we call
> ariaOwnsReferencingElements for each DOM and aria-owns child. Our
> implementation of ariaOwnsReferencingElements does a scan of every element
> starting from the root. So for a tree with a lot of children, and given a
> large document, I image this could cause performance issues.

Let me explore to see if there is a lighter weight way of doing this. I'm not sure how important the `ariaTreeRows` method being virtual is. I could perhaps implement the traversal in a separate function and just keep track of an array/set of visited nodes or just pass it along in the `ariaTreeRows` signature, but I'm not sure what the right style is here. Perhaps I could also just keep track of the current ancestry path rather than looking at all the visited nodes.

> It's unfortunate that we don't have an efficient way to find
> ariaOwnsReferencingElements. Ideally we would cache this somewhere as we
> build the tree, and then these lookups would be fast. But that would
> probably be a big project.
> 
> > I added a circular reference to the existing test case, but can make it a separate file if that makes more sense.
> I would prefer a separate file so there's a clear distinction that
> accessibility/mac/treeitem-row-delegation.html tests the behavior of a
> well-formed tree, while this other test specifically ensures we don't crash
> with a circular reference.
> 
> Was this version of the patch[1] vulnerable to circular references based on
> the circular reference test case you added in your latest patch?
> 
> [1]: https://bugs.webkit.org/attachment.cgi?id=445585&action=prettypatch

Yep.

[Sepand Parhami]

Created attachment 446445 [details]
Patch

[Sepand Parhami]

I went back to my first approach, but adding tracking of the parent path to determine the loops which should perform much better.

I also split out the poorly formed tree test cases (two circular reference tests and one checking behavior with multiple elements owning a single element).

[Tyler Wilcock]

Comment on attachment 446445 [details]
Patch

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

> Source/WebCore/ChangeLog:13
> +        * accessibility/AccessibilityObject.h:

Could you please include a summary of your changes in Source/WebCore/ChangeLog and LayoutTests/ChangeLog? What bug(s) does this patch fix, and how does it do it? This generally goes in between the "Reviewed by" and "Tests" sections.

> Source/WebCore/accessibility/AccessibilityObject.cpp:1888
> +    parentPath.append(this);

I think I suggested parentPath in the first place, but maybe something like "ancestors" would be a better name?

> Source/WebCore/accessibility/AccessibilityObject.cpp:1910
> +            downcast<AccessibilityObject>(*child).ariaTreeRows(result, parentPath);

Do we need is<> and downcast<> here? `child` is an AXCoreObject, which defines ariaTreeRows. I think we'd only need to downcast if AccessibilityObject defined ariaTreeRows and AXIsolatedObject didn't (these are the two direct subclasses of AXCoreObject).

So I think child->ariaTreeRows(result, ancestors); should work OK here.

> Source/WebCore/accessibility/AccessibilityObject.cpp:1934
> +            downcast<AccessibilityObject>(*child).ariaTreeRows(result, parentPath);

Ditto.

> LayoutTests/accessibility/mac/treeitem-row-delegation-poorly-formed.html:39
> +    description("This tests that a treeitem with a group that uses aria-owns will report its disclosed rows correctly.");

This description() is the same as the other test.

[Tyler Wilcock]

(In reply to Tyler Wilcock from comment #19)
> Comment on attachment 446445 [details]
> Patch
> > Source/WebCore/accessibility/AccessibilityObject.cpp:1910
> > +            downcast<AccessibilityObject>(*child).ariaTreeRows(result, parentPath);
> 
> Do we need is<> and downcast<> here? `child` is an AXCoreObject, which
> defines ariaTreeRows. I think we'd only need to downcast if
> AccessibilityObject defined ariaTreeRows and AXIsolatedObject didn't (these
> are the two direct subclasses of AXCoreObject).
> 
> So I think child->ariaTreeRows(result, ancestors); should work OK here.
Oh nevermind, I see, the new method isn't virtual (and shouldn't be -- we wouldn't want that to be part of the AXCoreObject interface).

[Sepand Parhami]

Created attachment 446606 [details]
Patch

[Sepand Parhami]

Comment on attachment 446445 [details]
Patch

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

>> Source/WebCore/ChangeLog:13
>> +        * accessibility/AccessibilityObject.h:
> 
> Could you please include a summary of your changes in Source/WebCore/ChangeLog and LayoutTests/ChangeLog? What bug(s) does this patch fix, and how does it do it? This generally goes in between the "Reviewed by" and "Tests" sections.

Took a stab at this, let me know if they need more/less/different info.

>> Source/WebCore/accessibility/AccessibilityObject.cpp:1888
>> +    parentPath.append(this);
> 
> I think I suggested parentPath in the first place, but maybe something like "ancestors" would be a better name?

Changed over to ancestors.

>> LayoutTests/accessibility/mac/treeitem-row-delegation-poorly-formed.html:39
>> +    description("This tests that a treeitem with a group that uses aria-owns will report its disclosed rows correctly.");
> 
> This description() is the same as the other test.

Updated!

[Tyler Wilcock]

Chris and / or Andres, what do you think of this?

[chris fleizach]

Comment on attachment 446606 [details]
Patch

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

> Source/WebCore/accessibility/AccessibilityObject.cpp:1902
> +            if (result.contains(child))

we can change this to 

if (!result...) 
   result.append(

and save a few lines

> Source/WebCore/accessibility/AccessibilityObject.h:826
> +    void ariaTreeRows(AccessibilityChildrenVector& result, AccessibilityChildrenVector& ancestors);

instead of result I think param could be named "rows"

[Sepand Parhami]

Created attachment 447043 [details]
Patch

[Sepand Parhami]

Comment on attachment 446606 [details]
Patch

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

>> Source/WebCore/accessibility/AccessibilityObject.cpp:1902
>> +            if (result.contains(child))
> 
> we can change this to 
> 
> if (!result...) 
>    result.append(
> 
> and save a few lines

We also need to skip the `if (is<AccessibilityObject>(*child))` check below since we don't want to recurse into this subtree. Both of these continues could be pulled outside of this if, which could make this a bit clearer. This check would add a bit of extra work since it should only be relevant for treeitems and checking against other elements (e.g. groups) would never match.

I think the first check, for ariaOwns should likely be moved outside of this if (it still works if we don't, just adds extra work to fix the ordering later).

>> Source/WebCore/accessibility/AccessibilityObject.h:826
>> +    void ariaTreeRows(AccessibilityChildrenVector& result, AccessibilityChildrenVector& ancestors);
> 
> instead of result I think param could be named "rows"

Updated.

[EWS]

Committed r288117 (246131@main): <https://commits.webkit.org/246131@main>

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