Bug 232466 – AX: Make ancestor computation cheaper by setting flags upon child insertion

• Component: Accessibility
• Status: RESOLVED FIXED

[Tyler Wilcock]

Some AX clients need to know if an element is contained with another element of a certain type. WebKit can compute this more efficiently than AX clients can.

[Radar WebKit Bug Importer]

<rdar://problem/84789867>

[Tyler Wilcock]

Created attachment 442776 [details]
Patch

[Tyler Wilcock]

Created attachment 442779 [details]
Patch

[Tyler Wilcock]

Created attachment 442780 [details]
Patch

[Tyler Wilcock]

Created attachment 442782 [details]
Patch

[Tyler Wilcock]

Comment on attachment 442782 [details]
Patch

Need to fix the Windows build, but this is ready to be looked at.

[Andres Gonzalez]

(In reply to Tyler Wilcock from comment #5)
> Created attachment 442782 [details]
> Patch

--- a/Source/WebCore/accessibility/AccessibilityObject.cpp
+++ a/Source/WebCore/accessibility/AccessibilityObject.cpp

@@ -519,16 +541,24 @@ void AccessibilityObject::insertChild(AXCoreObject* child, unsigned index, Desce

+                    grandchild->setFlagsFromAncestor(child);
+                    grandchild->setFlagsFromAncestor(this);

Instead of limiting to only two levels in the tree, couldn't we get the flags for child and then apply them to all the grandchildren?

+                    insertionIndex += 1;

Change to ++insertionIndex;

+        child->setFlagsFromAncestor(this);

Why only one level here?

--- a/Source/WebCore/accessibility/AccessibilityObject.h
+++ a/Source/WebCore/accessibility/AccessibilityObject.h

+    OptionSet<AXFlag> m_axFlags;
+    void setFlagsFromAncestor(const AXCoreObject*) override;
+    bool hasDocumentRoleAncestor() const override { return m_axFlags.contains(AXFlag::HasDocumentRoleAncestor); }
+    bool hasWebApplicationAncestor() const override { return m_axFlags.contains(AXFlag::HasWebApplicationAncestor); }
+    bool isInDescriptionListDefinition() const override { return m_axFlags.contains(AXFlag::isInDescriptionListDefinition); }
+    bool isInDescriptionListTerm() const override { return m_axFlags.contains(AXFlag::IsInDescriptionListTerm); }
+    bool isInTableCell() const override { return m_axFlags.contains(AXFlag::IsInTableCell); }

A rule that is broken in many places, but we try to have methods first, and member variables last in the class declaration.

--- a/Source/WebCore/accessibility/AccessibilityObjectInterface.h
+++ a/Source/WebCore/accessibility/AccessibilityObjectInterface.h

+    virtual void setFlagsFromAncestor(const AXCoreObject*) = 0;

Can we make this not expose this in the AXCoreObject interface? It is not implemented in the isolated object, and the goal should be to expose only what is needed in both. I'm trying to make the interface leaner and eventually remove all the ASSERT_NOT_REACHED implementations in AXIsolatedObject.

--- a/Source/WebCore/accessibility/ios/WebAccessibilityObjectWrapperIOS.mm
+++ a/Source/WebCore/accessibility/ios/WebAccessibilityObjectWrapperIOS.mm

+- (BOOL)_accessibilityIsInTableCell

Why the _ prefix? I would name it just like the others.

We replace all the Accessibility::findAncestor for the checks for the new flags. But Accessibility::findAncestor does a full walk up the hierarchy and for what I understand, the flags are set based only on one level up. Or I'm missing something?

--- a/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp
+++ a/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp

+void AXIsolatedObject::setFlagsFromAncestor(const AXCoreObject*)
+{
+    ASSERT_NOT_REACHED();
+}

We shouldn't add more unimplemented method. Instead, make this method internal to the AXObject hierarchy and not exposed in the AXCoreObject interface.

[Tyler Wilcock]

> + grandchild->setFlagsFromAncestor(child);
> + grandchild->setFlagsFromAncestor(this);
> 
> Instead of limiting to only two levels in the tree, couldn't we get the flags for child and then apply them to all the grandchildren?
> + child->setFlagsFromAncestor(this);
> 
> Why only one level here?
> We replace all the Accessibility::findAncestor for the checks for the new flags. But Accessibility::findAncestor does a full walk up the hierarchy and for what I understand, the flags are set based only on one level up. Or I'm missing something?
Addressing all of these comments at the same time, because I think the answer is the same. We only need to operate on one level at a time (or two, if we're skipping an ignored element) because setFlagsForAncestors checks if the given ancestor has the specific role, or if the ancestor has the flag set, meaning any of its ancestors any distance above have the specific role. This lets us only operate on one level at a time, no traversal required.

Let's say we three elements — A, B, and C. B is a child of A, and C is a child of B. Element A has role="document", but element B and C do not. When we build the AX tree, these operations occur:

1. The root node calls insertChild(A). A->setFlagsFromAncestor(rootNode) is called,  but rootNode has no roles we care about (e.g. role="document").
2. Element A calls insertChild(B). B->setFlagsFromAncestor(A) is called, and we notice A has a document role, so we set the flag.
3. Element B calls insertChild(C). C->setFlagsFromAncestor(B) is called, and we notice B does not have a document role, but it does have the AXHasDocumentRoleAncestor flag set, so we set it on this element too.

That's how the patch works as-is. The added layout test verifies this multi-level flag coalescing. Are you proposing different mechanism?

> --- a/Source/WebCore/accessibility/AccessibilityObjectInterface.h
> +++ a/Source/WebCore/accessibility/AccessibilityObjectInterface.h
> 
> +    virtual void setFlagsFromAncestor(const AXCoreObject*) = 0;
> 
> Can we make this not expose this in the AXCoreObject interface? It is not
> implemented in the isolated object, and the goal should be to expose only
> what is needed in both. I'm trying to make the interface leaner and
> eventually remove all the ASSERT_NOT_REACHED implementations in
> AXIsolatedObject.
Yeah, I'll see if I can move it.

[Tyler Wilcock]

> +    virtual void setFlagsFromAncestor(const AXCoreObject*) = 0;
> 
> Can we make this not expose this in the AXCoreObject interface?
Alright, I looked into this, and changing it would require changing the method signature of insertChild and addChild (which is where this new method is called) to accept AccessibilityObject* instead of AXCoreObject*, which would require a lot of cleanup in a lot of files. I feel like untangling that is best done in a separate patch. But if you have a different idea, I'm open to it.

[Tyler Wilcock]

Created attachment 442886 [details]
Patch

[Andres Gonzalez]

(In reply to Tyler Wilcock from comment #8)
> > + grandchild->setFlagsFromAncestor(child);
> > + grandchild->setFlagsFromAncestor(this);
> > 
> > Instead of limiting to only two levels in the tree, couldn't we get the flags for child and then apply them to all the grandchildren?
> > + child->setFlagsFromAncestor(this);
> > 
> > Why only one level here?
> > We replace all the Accessibility::findAncestor for the checks for the new flags. But Accessibility::findAncestor does a full walk up the hierarchy and for what I understand, the flags are set based only on one level up. Or I'm missing something?
> Addressing all of these comments at the same time, because I think the
> answer is the same. We only need to operate on one level at a time (or two,
> if we're skipping an ignored element) because setFlagsForAncestors checks if
> the given ancestor has the specific role, or if the ancestor has the flag
> set, meaning any of its ancestors any distance above have the specific role.
> This lets us only operate on one level at a time, no traversal required.
> 
> Let's say we three elements — A, B, and C. B is a child of A, and C is a
> child of B. Element A has role="document", but element B and C do not. When
> we build the AX tree, these operations occur:
> 
> 1. The root node calls insertChild(A). A->setFlagsFromAncestor(rootNode) is
> called,  but rootNode has no roles we care about (e.g. role="document").
> 2. Element A calls insertChild(B). B->setFlagsFromAncestor(A) is called, and
> we notice A has a document role, so we set the flag.
> 3. Element B calls insertChild(C). C->setFlagsFromAncestor(B) is called, and
> we notice B does not have a document role, but it does have the
> AXHasDocumentRoleAncestor flag set, so we set it on this element too.
> 
> That's how the patch works as-is. The added layout test verifies this
> multi-level flag coalescing. Are you proposing different mechanism?

That sounds good in principle. I wonder though if we are covering all cases though. For instance, if an AX object is created as the result of a notification (AXObjectCache::getOrCreate) and we notify a client with that newly created target, the client can query the properties of that object. In other words not all objects are first added to the AX hierarchy via addChild.

> 
> > --- a/Source/WebCore/accessibility/AccessibilityObjectInterface.h
> > +++ a/Source/WebCore/accessibility/AccessibilityObjectInterface.h
> > 
> > +    virtual void setFlagsFromAncestor(const AXCoreObject*) = 0;
> > 
> > Can we make this not expose this in the AXCoreObject interface? It is not
> > implemented in the isolated object, and the goal should be to expose only
> > what is needed in both. I'm trying to make the interface leaner and
> > eventually remove all the ASSERT_NOT_REACHED implementations in
> > AXIsolatedObject.
> Yeah, I'll see if I can move it.

[Andres Gonzalez]

(In reply to Tyler Wilcock from comment #10)
> Created attachment 442886 [details]
> Patch

--- a/Source/WebCore/accessibility/AccessibilityObject.cpp
+++ a/Source/WebCore/accessibility/AccessibilityObject.cpp

+            for (auto grandchild : child->children()) {
+                ASSERT(grandchild);
+                if (grandchild) {
+                    // Even though `child` is ignored, we still need to set flags based on it.
+                    grandchild->setFlagsFromAncestor(child);
+                    grandchild->setFlagsFromAncestor(this);

I think it would be more efficient to get the flags once for child and this and apply them to each grandchild. I.e., in addition to setFlagsFromAncestor, to have a setFlags that takes an OptionSet, and use that here.

[Andres Gonzalez]

(In reply to Tyler Wilcock from comment #10)
> Created attachment 442886 [details]
> Patch

--- a/Source/WebCore/accessibility/AccessibilityObjectInterface.h
+++ a/Source/WebCore/accessibility/AccessibilityObjectInterface.h

+    virtual void setFlagsFromAncestor(const AXCoreObject*) = 0;
+    virtual OptionSet<AXFlag> axFlags() const = 0;

What you can do to remove these two from the AXCoreObject interface is to declare them AccessibilityObject and AXIsolatedObject respectively, and then downcast in 

void AXIsolatedObject::initializeAttributeData(AXCoreObject& object, bool isRoot)
{
    ASSERT(is<AccessibilityObject>(object));

[Tyler Wilcock]

Created attachment 443648 [details]
Patch

[Andres Gonzalez]

(In reply to Tyler Wilcock from comment #14)
> Created attachment 443648 [details]
> Patch

--- a/Source/WebCore/ChangeLog
+++ a/Source/WebCore/ChangeLog

+        * accessibility/isolatedtree/AXIsolatedTree.h:
+        Add new AXPropertyName::AncestorFlags property. Add new
+        OptionSet<AXAncestorFlag> variant to AXPropertyValueVariant.

Shouldn't it be

+        OptionSet<AXAncestorFlag> type to AXPropertyValueVariant.

--- a/Source/WebCore/accessibility/AccessibilityObject.cpp
+++ a/Source/WebCore/accessibility/AccessibilityObject.cpp

+void AccessibilityObject::initializeAncestorFlagsWith(OptionSet<AXAncestorFlag> flags)

shouldn't flags be const& ?

+bool AccessibilityObject::matchesAncestorFlag(AXAncestorFlag flag) const
+{
+    auto role = roleValue();
+    switch (flag) {
+    case AXAncestorFlag::FlagsInitialized:
+        ASSERT_NOT_REACHED();
+        return false;
...
+    }
+    ASSERT_NOT_REACHED();
+    return false;
+}

I think you can replace the case AXAncestorFlag::FlagsInitialized: and the two ASSERT_NOT_REACHED with a default: label in the switch.

+bool AccessibilityObject::hasAncestorMatchingFlag(AXAncestorFlag flag) const
+{

Can we call it just hasAncestorFlag?

+static AccessibilityObject* accessibilityObjectFrom(AXCoreObject* axCoreObject)

Do we need this? Haven't seen other instances where we have a function just to do the downcast. It seems an overkill.

You can do the sanity assert and downcast right at the beginning of 

+void AccessibilityObject::insertChild(AXCoreObject* newChild, unsigned index, DescendIfIgnored descendIfIgnored)

--- a/Source/WebCore/accessibility/AccessibilityObject.h
+++ a/Source/WebCore/accessibility/AccessibilityObject.h

 class AccessibilityObject : public AXCoreObject {
+    friend class AXIsolatedObject;

AXObject shouldn't need to know anything about isolated objects. You may need to make ancestorFlags() a public member in AccessibilityObject.

+    void addAncestorFlags(OptionSet<AXAncestorFlag> flags) { m_ancestorFlags.add(flags); }

Shouldn't flags be a const& ?

+    void initializeAncestorFlagsWith(OptionSet<AXAncestorFlag>);

const& ? Don't need With as part of the name.

+    bool hasAncestorMatchingFlag(AXAncestorFlag) const;

Don't need Matching in the name.

[Andres Gonzalez]

(In reply to Tyler Wilcock from comment #14)
> Created attachment 443648 [details]
> Patch

--- a/Source/WebCore/accessibility/AccessibilityObjectInterface.h
+++ a/Source/WebCore/accessibility/AccessibilityObjectInterface.h

+    virtual OptionSet<AXAncestorFlag> ancestorFlags() const = 0;

We don't need this in the interface since clients don't need to access the flags directly.

--- a/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp
+++ a/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp

+    // Only store the object's ancestor flags if any are set (excluding the "is initialized" flag).
+    auto ancestorFlags = object.ancestorFlags();
+    if (!ancestorFlags.isEmpty() && !(ancestorFlags.hasExactlyOneBitSet() && ancestorFlags.contains(AXAncestorFlag::FlagsInitialized)))
+        setProperty(AXPropertyName::AncestorFlags, object.ancestorFlags());
+
    if (ancestorFlags ^ AXAncestorFlag::FlagsInitialized)

bitwise XOR?

[Tyler Wilcock]

Created attachment 443707 [details]
Patch

[Andres Gonzalez]

(In reply to Tyler Wilcock from comment #17)
> Created attachment 443707 [details]
> Patch

--- a/Source/WebCore/accessibility/AccessibilityObject.h
+++ a/Source/WebCore/accessibility/AccessibilityObject.h

+    void addAncestorFlags(OptionSet<AXAncestorFlag> flags) { m_ancestorFlags.add(flags); }

flags should be const& ?

--- a/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp
+++ a/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp

+    if (!ancestorFlags.isEmpty() && ancestorFlags ^ AXAncestorFlag::FlagsInitialized)

I think you can do just

+    if (ancestorFlags ^ AXAncestorFlag::FlagsInitialized)

--- a/Tools/WebKitTestRunner/InjectedBundle/mac/AccessibilityUIElementMac.mm
+++ a/Tools/WebKitTestRunner/InjectedBundle/mac/AccessibilityUIElementMac.mm

+bool AccessibilityUIElement::hasDocumentRoleAncestor() const
+{
+    BEGIN_AX_OBJC_EXCEPTIONS
+    id value = [m_element accessibilityAttributeValue:@"AXHasDocumentRoleAncestor"];

Instead of using the m_element directly, use AccessibilityUIElement::attributeValue(...) which uses the AX thread in isolated tree mode.

+bool AccessibilityUIElement::hasWebApplicationAncestor() const
+{
+    BEGIN_AX_OBJC_EXCEPTIONS
+    id value = [m_element accessibilityAttributeValue:@"AXHasWebApplicationAncestor"];

Same here.

+bool AccessibilityUIElement::isInDescriptionListDetail() const
+{
+    BEGIN_AX_OBJC_EXCEPTIONS
+    id value = [m_element accessibilityAttributeValue:@"AXIsInDescriptionListDetail"];

Dito.

+bool AccessibilityUIElement::isInDescriptionListTerm() const
+{
+    BEGIN_AX_OBJC_EXCEPTIONS
+    id value = [m_element accessibilityAttributeValue:@"AXIsInDescriptionListTerm"];


Dito.

+bool AccessibilityUIElement::isInCell() const
+{
+    BEGIN_AX_OBJC_EXCEPTIONS
+    id value = [m_element accessibilityAttributeValue:@"AXIsInCell"];


Dito.

[Tyler Wilcock]

Created attachment 443764 [details]
Patch

[EWS]

Committed r285589 (244097@main): <https://commits.webkit.org/244097@main>

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