Bug 262733 – AX: optimize accessibilityIsIgnored computation

• Component: Accessibility
• Status: RESOLVED FIXED

[Joshua Hoffman]

We currently traverse the ancestor hierarchy three times to compute isAXHidden, isPresentationalChildOfAriaRole, and isDescendantOfBarrenParent—all of which we need to compute accessibility is ignored. This should happen in the same traversal.

[Radar WebKit Bug Importer]

<rdar://problem/116541936>

[Radar WebKit Bug Importer]

<rdar://problem/116541943>

[Joshua Hoffman]

Created attachment 468087 [details]
Patch

[Joshua Hoffman]

Created attachment 468093 [details]
Patch

[Joshua Hoffman]

Created attachment 468095 [details]
Patch

[Joshua Hoffman]

Created attachment 468096 [details]
Patch

[Joshua Hoffman]

Created attachment 468098 [details]
Patch

[Joshua Hoffman]

Created attachment 468100 [details]
Patch

[Joshua Hoffman]

Created attachment 468138 [details]
Patch

[chris fleizach]

Comment on attachment 468138 [details]
Patch

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

> Source/WebCore/accessibility/AccessibilityObject.cpp:3967
> +    for (auto* object = this; object; object = object->parentObject()) {

this code looks identical to generateIsIgnoredFromParentData. can we re-use it somehow?

> Source/WebCore/accessibility/AccessibilityObject.cpp:4337
> +    AccessibilityIsIgnoredFromParentData result = AccessibilityIsIgnoredFromParentData(this);

auto

> Source/WebCore/accessibility/AccessibilityObject.cpp:4338
> +    for (AccessibilityObject* object = child; object; object = object->parentObject()) {

auto*

> Source/WebCore/accessibility/AccessibilityRenderObject.cpp:-1070
> -    if (isDescendantOfBarrenParent())

how come we can remove this one now?

[Joshua Hoffman]

(In reply to chris fleizach from comment #10)
> Comment on attachment 468138 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=468138&action=review
> 
> > Source/WebCore/accessibility/AccessibilityObject.cpp:3967
> > +    for (auto* object = this; object; object = object->parentObject()) {
> 
> this code looks identical to generateIsIgnoredFromParentData. can we re-use
> it somehow?

I would ideally like to abstract these as well, but since generateIsIgnoredFromParentData is modifying a struct and the defaultObjectInclusion needs to return early (to maximize the optimization), I am unsure how a lambda could accomplish this. Do you have any suggestions?

> > Source/WebCore/accessibility/AccessibilityRenderObject.cpp:-1070
> > -    if (isDescendantOfBarrenParent())
> 
> how come we can remove this one now?

The barren parent check was moved inside the unified iteration (`!object->canHaveChildren()`), so we will already have this case covered.

[Tyler Wilcock]

Comment on attachment 468138 [details]
Patch

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

> Source/WebCore/accessibility/AccessibilityNodeObject.cpp:592
> +#if !USE(ATSPI)

Maybe we should add a comment stating GTK / ATSPI layout tests expect popup buttons to be capable of having children?

> Source/WebCore/accessibility/AccessibilityObject.cpp:3968
> +        if (equalLettersIgnoringASCIICase(object->getAttribute(aria_hiddenAttr), "true"_s) && !object->isFocused() && !isFocused())

Do we need to check isFocused() every iteration? Presumably that wouldn't change.

> Source/WebCore/accessibility/atspi/AccessibilityAtspi.cpp:647
> +    { AccessibilityRole::ListBox, { "list box", N_("list box") } },

Maybe we should undo this change in case it is intentional? I'm guessing this wasn't the reason the GTK tests were failing.

[Joshua Hoffman]

Created attachment 468159 [details]
Patch

[Tyler Wilcock]

Comment on attachment 468159 [details]
Patch

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

> Source/WebCore/accessibility/AccessibilityNodeObject.cpp:593
> +// GTK/ATSPI layout tests expect popup buttons to be capable of having children.

I think this comment should be indented one more level in (unless the style checker expects the current form).

> Source/WebCore/accessibility/AccessibilityObject.cpp:3969
> +        if (equalLettersIgnoringASCIICase(object->getAttribute(aria_hiddenAttr), "true"_s) && !object->isFocused() && !selfIsFocused)

selfIsFocused is the cheapest bit of work here, so we should front-load it to avoid unnecessary work.

> Source/WebCore/accessibility/AccessibilityObject.cpp:4340
> +        if (equalLettersIgnoringASCIICase(object->getAttribute(aria_hiddenAttr), "true"_s) && !object->isFocused() && !child->isFocused())

Do we need to check that child->isFocused() every iteration?

Can we avoid doing:

equalLettersIgnoringASCIICase(object->getAttribute(aria_hiddenAttr), "true"_s)

If result.isAXHidden is already true? Same question for the other fields, and the code in AccessibilityObject::defaultObjectInclusion().

> Source/WebCore/accessibility/AccessibilityObject.h:830
> +    AccessibilityIsIgnoredFromParentData generateIsIgnoredFromParentData(AccessibilityObject*);

Can this take a reference? The only callsite already does a null-check.

[Joshua Hoffman]

Comment on attachment 468159 [details]
Patch

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

>> Source/WebCore/accessibility/AccessibilityObject.cpp:3969
>> +        if (equalLettersIgnoringASCIICase(object->getAttribute(aria_hiddenAttr), "true"_s) && !object->isFocused() && !selfIsFocused)
> 
> selfIsFocused is the cheapest bit of work here, so we should front-load it to avoid unnecessary work.

Ah yes, will move that.

>> Source/WebCore/accessibility/AccessibilityObject.cpp:4340
>> +        if (equalLettersIgnoringASCIICase(object->getAttribute(aria_hiddenAttr), "true"_s) && !object->isFocused() && !child->isFocused())
> 
> Do we need to check that child->isFocused() every iteration?
> 
> Can we avoid doing:
> 
> equalLettersIgnoringASCIICase(object->getAttribute(aria_hiddenAttr), "true"_s)
> 
> If result.isAXHidden is already true? Same question for the other fields, and the code in AccessibilityObject::defaultObjectInclusion().

Thinking about it, we can just check child->isFocused after the entire iteration and set result.isAXHidden there. 

For your other question, checking result.isAXHidden and other fields does make sense inside this traversal, so I can include that.

>> Source/WebCore/accessibility/AccessibilityObject.h:830
>> +    AccessibilityIsIgnoredFromParentData generateIsIgnoredFromParentData(AccessibilityObject*);
> 
> Can this take a reference? The only callsite already does a null-check.

Yep!

[Joshua Hoffman]

Created attachment 468161 [details]
Patch

[Joshua Hoffman]

Created attachment 468176 [details]
Patch

[Tyler Wilcock]

Comment on attachment 468176 [details]
Patch

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

> Source/WebCore/accessibility/AccessibilityObject.cpp:3913
> +};

I forgot to remove this semicolon, I don't think it should be there after a method implementation. My fault :(

[Tyler Wilcock]

Comment on attachment 468176 [details]
Patch

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

> COMMIT_MESSAGE:13
> +generateIsIgnoredFromParentData. This saves up to roughly 20% of samples for

Also I think this function is gone in the latest revisions of the patch

[Tyler Wilcock]

(In reply to Tyler Wilcock from comment #19)
> Comment on attachment 468176 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=468176&action=review
> 
> > COMMIT_MESSAGE:13
> > +generateIsIgnoredFromParentData. This saves up to roughly 20% of samples for
> 
> Also I think this function is gone in the latest revisions of the patch
(generateIsIgnoredFromParentData that is)

[Joshua Hoffman]

Created attachment 468179 [details]
Patch

[Andres Gonzalez]

(In reply to Joshua Hoffman from comment #21)
> Created attachment 468179 [details]
> Patch

diff --git a/Source/WebCore/accessibility/AccessibilityNodeObject.cpp b/Source/WebCore/accessibility/AccessibilityNodeObject.cpp
index 171cae482834..ea25c95e3742 100644
--- a/Source/WebCore/accessibility/AccessibilityNodeObject.cpp
+++ b/Source/WebCore/accessibility/AccessibilityNodeObject.cpp
@@ -589,7 +589,10 @@ bool AccessibilityNodeObject::canHaveChildren() const
     // Elements that should not have children.
     switch (roleValue()) {
     case AccessibilityRole::Button:
+#if !USE(ATSPI)
+    // GTK/ATSPI layout tests expect popup buttons to be capable of having children.

AG: to be capable of having --> to have.

     case AccessibilityRole::PopUpButton:
+#endif
     case AccessibilityRole::CheckBox:
     case AccessibilityRole::RadioButton:
     case AccessibilityRole::Tab:
@@ -653,9 +656,6 @@ bool AccessibilityNodeObject::computeAccessibilityIsIgnored() const
         return false;
     if (decision == AccessibilityObjectInclusion::IgnoreObject)
         return true;
-    // If this element is within a parent that cannot have children, it should not be exposed.
-    if (isDescendantOfBarrenParent())
-        return true;

     auto role = roleValue();
     return role == AccessibilityRole::Ignored || role == AccessibilityRole::Unknown;
diff --git a/Source/WebCore/accessibility/AccessibilityObject.cpp b/Source/WebCore/accessibility/AccessibilityObject.cpp
index 94eab10dc42e..93a17e66dfe7 100644
--- a/Source/WebCore/accessibility/AccessibilityObject.cpp
+++ b/Source/WebCore/accessibility/AccessibilityObject.cpp
@@ -3907,6 +3907,11 @@ bool AccessibilityObject::accessibilityIsIgnoredByDefault() const
     return defaultObjectInclusion() == AccessibilityObjectInclusion::IgnoreObject;
 }

+static bool isARIAHidden(const AccessibilityObject& object)
+{
+    return equalLettersIgnoringASCIICase(object.getAttribute(aria_hiddenAttr), "true"_s) && !object.isFocused();
+}
+

AG: shouldn't this be a class method?

 // ARIA component of hidden definition.
 // https://www.w3.org/TR/wai-aria/#dfn-hidden
 bool AccessibilityObject::isAXHidden() const
@@ -3915,7 +3920,7 @@ bool AccessibilityObject::isAXHidden() const
         return false;

     return Accessibility::findAncestor<AccessibilityObject>(*this, true, [] (const AccessibilityObject& object) {
-        return equalLettersIgnoringASCIICase(object.getAttribute(aria_hiddenAttr), "true"_s) && !object.isFocused();
+        return isARIAHidden(object);
     }) != nullptr;
 }

@@ -3961,10 +3966,16 @@ AccessibilityObjectInclusion AccessibilityObject::defaultObjectInclusion() const
     }

     bool useParentData = !m_isIgnoredFromParentData.isNull();
-    if (useParentData ? m_isIgnoredFromParentData.isAXHidden : isAXHidden())
+    if (useParentData && (m_isIgnoredFromParentData.isAXHidden || m_isIgnoredFromParentData.isPresentationalChildOfAriaRole))
         return AccessibilityObjectInclusion::IgnoreObject;

-    if (useParentData ? m_isIgnoredFromParentData.isPresentationalChildOfAriaRole : isPresentationalChildOfAriaRole())
+    if (isARIAHidden(*this))
+        return AccessibilityObjectInclusion::IgnoreObject;
+
+    bool ignoreARIAHidden = isFocused();
+    if (Accessibility::findAncestor<AccessibilityObject>(*this, false, [&] (const auto& object) {
+        return (!ignoreARIAHidden && isARIAHidden(object)) || object.ariaRoleHasPresentationalChildren() || !object.canHaveChildren();
+    }))
         return AccessibilityObjectInclusion::IgnoreObject;

     // Include <dialog> elements and elements with role="dialog".
@@ -4324,13 +4335,6 @@ bool AccessibilityObject::ariaRoleHasPresentationalChildren() const
     }
 }

-bool AccessibilityObject::isPresentationalChildOfAriaRole() const
-{
-    return Accessibility::findAncestor(*this, false, [] (const auto& ancestor) {
-        return ancestor.ariaRoleHasPresentationalChildren();
-    });
-}
-
 void AccessibilityObject::setIsIgnoredFromParentDataForChild(AccessibilityObject* child)
 {
     if (!child)
@@ -4342,9 +4346,20 @@ void AccessibilityObject::setIsIgnoredFromParentDataForChild(AccessibilityObject
         result.isPresentationalChildOfAriaRole = m_isIgnoredFromParentData.isPresentationalChildOfAriaRole || ariaRoleHasPresentationalChildren();
         result.isDescendantOfBarrenParent = m_isIgnoredFromParentData.isDescendantOfBarrenParent || !canHaveChildren();
     } else {
-        result.isAXHidden = child->isAXHidden();
-        result.isPresentationalChildOfAriaRole = child->isPresentationalChildOfAriaRole();
-        result.isDescendantOfBarrenParent = child->isDescendantOfBarrenParent();
+        if (isARIAHidden(*child))
+            result.isAXHidden = true;
+
+        bool ignoreARIAHidden = child->isFocused();
+        for (auto* object = child->parentObject(); object; object = object->parentObject()) {
+            if (!result.isAXHidden && !ignoreARIAHidden && isARIAHidden(*object))
+                result.isAXHidden = true;
+
+            if (!result.isPresentationalChildOfAriaRole && object->ariaRoleHasPresentationalChildren())
+                result.isPresentationalChildOfAriaRole = true;
+
+            if (!result.isDescendantOfBarrenParent && !object->canHaveChildren())
+                result.isDescendantOfBarrenParent = true;
+        }
     }

     child->setIsIgnoredFromParentData(result);
diff --git a/Source/WebCore/accessibility/AccessibilityObject.h b/Source/WebCore/accessibility/AccessibilityObject.h
index 1908086ceb53..ba1b43900105 100644
--- a/Source/WebCore/accessibility/AccessibilityObject.h
+++ b/Source/WebCore/accessibility/AccessibilityObject.h
@@ -361,7 +361,6 @@ public:
     virtual AccessibilityRole ariaRoleAttribute() const { return AccessibilityRole::Unknown; }
     bool hasExplicitGenericRole() const { return ariaRoleAttribute() == AccessibilityRole::Generic; }
     bool hasImplicitGenericRole() const { return roleValue() == AccessibilityRole::Generic && !hasExplicitGenericRole(); }
-    bool isPresentationalChildOfAriaRole() const;
     bool ariaRoleHasPresentationalChildren() const;
     bool inheritsPresentationalRole() const override { return false; }

diff --git a/Source/WebCore/accessibility/AccessibilityRenderObject.cpp b/Source/WebCore/accessibility/AccessibilityRenderObject.cpp
index a84865fec244..cc75cf754d70 100644
--- a/Source/WebCore/accessibility/AccessibilityRenderObject.cpp
+++ b/Source/WebCore/accessibility/AccessibilityRenderObject.cpp
@@ -1066,10 +1066,6 @@ bool AccessibilityRenderObject::computeAccessibilityIsIgnored() const
     if (decision == AccessibilityObjectInclusion::IgnoreObject)
         return true;

-    // If this element is within a parent that cannot have children, it should not be exposed.
-    if (isDescendantOfBarrenParent())
-        return true;
-
     if (roleValue() == AccessibilityRole::Ignored)
         return true;

AG: Do we use the individual fields of the struct m_isIgnoredFromParentData? Or could we have a single bool m_ignoredByHeritage?

AG: Still seems fairly complex, wish there were a single walk up the hierachy where we determine isIgnored. Can we combine with the other walk up we do to collect flags from ancestors?

[Tyler Wilcock]

> diff --git a/Source/WebCore/accessibility/AccessibilityRenderObject.cpp
> b/Source/WebCore/accessibility/AccessibilityRenderObject.cpp
> index a84865fec244..cc75cf754d70 100644
> --- a/Source/WebCore/accessibility/AccessibilityRenderObject.cpp
> +++ b/Source/WebCore/accessibility/AccessibilityRenderObject.cpp
> @@ -1066,10 +1066,6 @@ bool
> AccessibilityRenderObject::computeAccessibilityIsIgnored() const
>      if (decision == AccessibilityObjectInclusion::IgnoreObject)
>          return true;
> 
> -    // If this element is within a parent that cannot have children, it
> should not be exposed.
> -    if (isDescendantOfBarrenParent())
> -        return true;
> -
>      if (roleValue() == AccessibilityRole::Ignored)
>          return true;
> 
> AG: Do we use the individual fields of the struct m_isIgnoredFromParentData?
> Or could we have a single bool m_ignoredByHeritage?
m_isIgnoredFromParentData.isDescendantOfBarrenParent is used in an individual way, so in order to have a unified m_ignoredByHeritage field we'd have to change that usage.

> AG: Still seems fairly complex, wish there were a single walk up the
> hierachy where we determine isIgnored. Can we combine with the other walk up
> we do to collect flags from ancestors?
Good idea on using AXAncestorFlags! Those are built on the way down through the tree as children are inserted, rather than on the way up through an explicit traversal. accessibilityIsIgnored() itself is a component of building the tree, which could complicate this approach, but I think it's still possible to make it work. And doing so could be a good performance win as it would preclude the need for any traversal at all here in accessibilityIsIgnored(), one of our hottest functions.

We'd have to make sure the flags are updated at all the appropriate levels when aria-hidden changes, and when roles change (i.e. an object dynamically becomes something that matches ariaRoleHasPresentationalChildren()). That might already happen inherently by how we invalidate the hierarchy when aria-hidden and roles change, but would take some experimenting to be sure.

Because this patch is a solid performance win on its own, my opinion is that we should take it and explore further potential improvements via the AXAncestorFlags in a future patch. What do y'all think?

[Tyler Wilcock]

> Because this patch is a solid performance win on its own, my opinion is that
> we should take it and explore further potential improvements via the
> AXAncestorFlags in a future patch. What do y'all think?
(The suggestions regarding making isARIAHidden a class method and the code comment change can be part of this patch)

[Joshua Hoffman]

(In reply to Tyler Wilcock from comment #23) 
> Because this patch is a solid performance win on its own, my opinion is that
> we should take it and explore further potential improvements via the
> AXAncestorFlags in a future patch. What do y'all think?

I agree with both ideas. The ancestor flags are definitely worth exploring in a follow up.

[Joshua Hoffman]

Created attachment 468183 [details]
Patch

[Joshua Hoffman]

Created attachment 468198 [details]
Patch

[EWS]

Committed 269313@main (c24f056ed7c1): <https://commits.webkit.org/269313@main>

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