Bug 261937 – AX: AXIsolatedTree::collectNodeChangesForSubtree wastefully collects node changes for objects already in the isolated tree

• Component: Accessibility
• Status: RESOLVED FIXED

[Tyler Wilcock]

...

[Radar WebKit Bug Importer]

<rdar://problem/115879218>

[Tyler Wilcock]

Created attachment 467822 [details]
Patch

[Tyler Wilcock]

Created attachment 467823 [details]
Patch

[Andres Gonzalez]

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

diff --git a/Source/WebCore/accessibility/AXLogger.cpp b/Source/WebCore/accessibility/AXLogger.cpp
index aa64cad2112a..bc44b7e417f5 100644
--- a/Source/WebCore/accessibility/AXLogger.cpp
+++ b/Source/WebCore/accessibility/AXLogger.cpp
@@ -532,6 +532,9 @@ TextStream& operator<<(TextStream& stream, AXObjectCache::AXNotification notific
     case AXObjectCache::AXNotification::AXAutofillTypeChanged:
         stream << "AXAutofillTypeChanged";
         break;
+    case AXObjectCache::AXNotification::AXCanFocusChanged:
+        stream << "AXCanFocusChanged";
+        break;
     case AXObjectCache::AXNotification::AXCellSlotsChanged:
         stream << "AXCellSlotsChanged";
         break;
diff --git a/Source/WebCore/accessibility/AXObjectCache.cpp b/Source/WebCore/accessibility/AXObjectCache.cpp
index d3d82cb21dfe..1d6922b6ca46 100644
--- a/Source/WebCore/accessibility/AXObjectCache.cpp
+++ b/Source/WebCore/accessibility/AXObjectCache.cpp
@@ -2324,7 +2324,7 @@ void AXObjectCache::handleRoleChanged(AccessibilityObject* axObject)
     axObject->recomputeIsIgnored();

 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
-    updateIsolatedTree(axObject, AXNotification::AXRoleChanged);
+    postNotification(axObject, nullptr, AXRoleChanged);
 #endif
 }

@@ -2413,12 +2413,18 @@ void AXObjectCache::handleAttributeChange(Element* element, const QualifiedName&
     }
     else if (attrName == disabledAttr)
         postNotification(element, AXObjectCache::AXDisabledStateChanged);
-    else if (attrName == forAttr && is<HTMLLabelElement>(*element))
-        labelChanged(element);
+    else if (attrName == forAttr && is<HTMLLabelElement>(element))
+        labelForAttributeChanged(downcast<HTMLLabelElement>(*element), oldValue);

AG: labelForAttributeChanged -> handleLabelForChanged ?

     else if (attrName == requiredAttr)
         postNotification(element, AXRequiredStatusChanged);
-    else if (attrName == tabindexAttr)
-        childrenChanged(element->parentNode(), element);
+    else if (attrName == tabindexAttr) {
+        if (oldValue.isEmpty() || newValue.isEmpty()) {
+            childrenChanged(element->parentNode(), element);
+#if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
+            postNotification(element, AXCanFocusChanged);
+#endif
+        }
+    }
 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
     else if (attrName == headersAttr)
         updateIsolatedTree(get(element), AXTableHeadersChanged);
@@ -2572,11 +2578,12 @@ void AXObjectCache::handleAttributeChange(Element* element, const QualifiedName&
     }
 }

-void AXObjectCache::labelChanged(Element* element)
+void AXObjectCache::labelForAttributeChanged(HTMLLabelElement& label, const AtomString& oldValue)
 {
-    ASSERT(is<HTMLLabelElement>(*element));
-    auto correspondingControl = downcast<HTMLLabelElement>(*element).control();
-    deferTextChangedIfNeeded(correspondingControl.get());
+    RefPtr currentControl = label.control();
+    deferTextChangedIfNeeded(currentControl.get());
+    RefPtr oldControl = label.treeScope().getElementById(oldValue);
+    deferTextChangedIfNeeded(oldControl.get());
 }

 void AXObjectCache::recomputeIsIgnored(RenderObject* renderer)
@@ -4090,6 +4097,9 @@ void AXObjectCache::updateIsolatedTree(const Vector<std::pair<RefPtr<Accessibili
         case AXAutofillTypeChanged:
             tree->updateNodeProperty(*notification.first, AXPropertyName::ValueAutofillButtonType);
             break;
+        case AXCanFocusChanged:
+            tree->updateNodeProperty(*notification.first, AXPropertyName::CanSetFocusAttribute);
+            break;
         case AXCellSlotsChanged:
             ASSERT(notification.first->isTable());
             tree->updateNodeProperty(*notification.first, AXPropertyName::CellSlots);
@@ -4418,6 +4428,7 @@ Vector<QualifiedName>& AXObjectCache::relationAttributes()
         aria_labeledbyAttr,
         aria_ownsAttr,
         headersAttr,
+        popovertargetAttr,

AG: I think we discussed this and decided to use ControlFor and ControledBy.

     };
     return relationAttributes;
 }
diff --git a/Source/WebCore/accessibility/AXObjectCache.h b/Source/WebCore/accessibility/AXObjectCache.h
index 7a0af9a45e92..bc8226f2d82d 100644
--- a/Source/WebCore/accessibility/AXObjectCache.h
+++ b/Source/WebCore/accessibility/AXObjectCache.h
@@ -333,6 +333,7 @@ public:
         AXActiveDescendantChanged,
         AXAutocorrectionOccured,
         AXAutofillTypeChanged,
+        AXCanFocusChanged,

AG: AXFocusableStateChanged ?

         AXCellSlotsChanged,
         AXCheckedStateChanged,
         AXChildrenChanged,
@@ -508,7 +509,7 @@ protected:
 #endif

     void frameLoadingEventPlatformNotification(AccessibilityObject*, AXLoadingEvent);
-    void labelChanged(Element*);
+    void labelForAttributeChanged(HTMLLabelElement&, const AtomString& /* oldValue */);

AG: labelForAttributeChanged -> handleLabelForChanged ?

     // This is a weak reference cache for knowing if Nodes used by TextMarkers are valid.
     void setNodeInUse(Node* n) { m_textMarkerNodes.add(n); }
diff --git a/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.h b/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.h
index bf37dff8a6dd..a737d21b3369 100644
--- a/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.h
+++ b/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.h
@@ -67,6 +67,7 @@ private:
     void detachPlatformWrapper(AccessibilityDetachmentType) override;

     AXID parent() const { return m_parentID; }
+    void setParent(AXID axID) { m_parentID = axID; }

     AXIsolatedTree* tree() const { return m_cachedTree.get(); }

diff --git a/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp b/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp
index 3828b1bf90ff..033c13244fc4 100644
--- a/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp
+++ b/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp
@@ -328,6 +328,7 @@ void AXIsolatedTree::queueRemovalsLocked(Vector<AXID>&& subtreeRemovals)
     ASSERT(m_changeLogLock.isLocked());

     m_pendingSubtreeRemovals.appendVector(WTFMove(subtreeRemovals));
+    m_pendingProtectedFromDeletionIDs.formUnion(std::exchange(m_protectedFromDeletionIDs, { }));
 }

 void AXIsolatedTree::queueRemovalsAndUnresolvedChanges(Vector<AXID>&& subtreeRemovals)
@@ -368,6 +369,9 @@ void AXIsolatedTree::queueAppendsAndRemovals(Vector<NodeChange>&& appends, Vecto
     Locker locker { m_changeLogLock };
     for (const auto& append : appends)
         queueChange(append);
+    auto parentUpdates = std::exchange(m_parentUpdates, { });
+    for (const auto& parentUpdate : parentUpdates)
+        m_pendingParentUpdates.set(WTFMove(parentUpdate.key), WTFMove(parentUpdate.value));
     queueRemovalsLocked(WTFMove(subtreeRemovals));
 }

@@ -408,7 +412,22 @@ void AXIsolatedTree::collectNodeChangesForSubtree(AXCoreObject& axObject)
     if (m_collectingNodeChangesAtTreeLevel >= m_maxTreeDepth)
         return;

-    m_unresolvedPendingAppends.set(axObject.objectID(), AttachWrapper::OnMainThread);
+    auto* axParent = axObject.parentObjectUnignored();
+    auto nodeMapIterator = m_nodeMap.find(axObject.objectID());

AG: nodeMapIterator -> it.

+    if (nodeMapIterator == m_nodeMap.end())
+        m_unresolvedPendingAppends.set(axObject.objectID(), AttachWrapper::OnMainThread);
+    else {
+        // This object is already in the isolated tree, so there's no need to create full node change for it (doing so is expensive).
+        // Protect this object from being deleted. This is important when |axObject| was a child of some other object,
+        // but no longer is, and thus the other object will try to queue it for removal. But the fact that we're here
+        // indicates this object isn't ready to be removed, just a child of a different parent, so prevent this removal.
+        m_protectedFromDeletionIDs.add(axObject.objectID());
+        // Update the object's parent if it has changed (but only if we aren't going to create a node change for it,
+        // as the act of creating a new node change will correct this as part of creating the new AXIsolatedObject).
+        if (axParent && nodeMapIterator->value.parentID != axParent->objectID() && !m_unresolvedPendingAppends.contains(axObject.objectID()))
+            m_parentUpdates.add(axObject.objectID(), axParent->objectID());
+    }
+
     auto axChildrenCopy = axObject.children();
     Vector<AXID> axChildrenIDs;
     axChildrenIDs.reserveInitialCapacity(axChildrenCopy.size());
@@ -424,7 +443,6 @@ void AXIsolatedTree::collectNodeChangesForSubtree(AXCoreObject& axObject)
     axChildrenIDs.shrinkToFit();

     // Update the m_nodeMap.
-    auto* axParent = axObject.parentObjectUnignored();
     m_nodeMap.set(axObject.objectID(), ParentChildrenIDs { axParent ? axParent->objectID() : AXID(), WTFMove(axChildrenIDs) });
 }

@@ -594,6 +612,13 @@ void AXIsolatedTree::updateNodeProperties(AXCoreObject& axObject, const Vector<A
             propertyMap.set(AXPropertyName::TextInputMarkedTextMarkerRange, value);
             break;
         }
+        case AXPropertyName::TitleUIElement: {
+            if (auto* titleUIElement = axObject.titleUIElement())
+                propertyMap.set(AXPropertyName::TitleUIElement, titleUIElement->objectID());
+            else
+                propertyMap.set(AXPropertyName::TitleUIElement, AXID());

AG: can you write only one propertyMap.set(AXPropertyName::TitleUIElement, titleUIElement ? titleUIElement->objectID() : AXID());

+            break;
+        }
         case AXPropertyName::URL:
             propertyMap.set(AXPropertyName::URL, axObject.url().isolatedCopy());
             break;
@@ -848,6 +873,16 @@ void AXIsolatedTree::removeNode(const AccessibilityObject& axObject)
     AXLOG(makeString("objectID ", axObject.objectID().loggingString()));
     ASSERT(isMainThread());

+    if (RefPtr correspondingControl = axObject.isLabel() ? axObject.correspondingControlForLabelElement() : nullptr) {
+        // If a label has been removed from the AX tree, the control associated it may need to change
+        // its title UI element. Use callOnMainThread to spin the runloop before re-computing this,
+        // as we need to wait for the backing DOM element to actually be destroyed to compute the
+        // correct title UI element.
+        callOnMainThread([correspondingControl, protectedThis = Ref { *this }] {
+            protectedThis->updateNodeProperty(*correspondingControl, AXPropertyName::TitleUIElement);
+        });
+    }
+
     m_unresolvedPendingAppends.remove(axObject.objectID());
     removeSubtreeFromNodeMap(axObject.objectID(), axObject.parentObjectUnignored());
     queueRemovals({ axObject.objectID() });
@@ -876,7 +911,7 @@ void AXIsolatedTree::removeSubtreeFromNodeMap(AXID objectID, AccessibilityObject
     Vector<AXID> removals = { objectID };
     while (removals.size()) {
         AXID axID = removals.takeLast();
-        if (!axID.isValid() || m_unresolvedPendingAppends.contains(axID))
+        if (!axID.isValid() || m_unresolvedPendingAppends.contains(axID) || m_protectedFromDeletionIDs.contains(axID))
             continue;

         auto it = m_nodeMap.find(axID);
@@ -956,6 +991,8 @@ void AXIsolatedTree::applyPendingChanges()

     while (m_pendingSubtreeRemovals.size()) {
         auto axID = m_pendingSubtreeRemovals.takeLast();
+        if (m_pendingProtectedFromDeletionIDs.contains(axID))
+            continue;
         AXLOG(makeString("removing subtree axID ", axID.loggingString()));
         if (RefPtr object = objectForID(axID)) {
             // There's no need to call the more comprehensive AXCoreObject::detach here since
@@ -965,6 +1002,7 @@ void AXIsolatedTree::applyPendingChanges()
             m_readerThreadNodeMap.remove(axID);
         }
     }
+    m_pendingProtectedFromDeletionIDs.clear();

     for (const auto& item : m_pendingAppends) {
         AXID axID = item.isolatedObject->objectID();
@@ -1002,6 +1040,12 @@ void AXIsolatedTree::applyPendingChanges()
     }
     m_pendingAppends.clear();

+    for (const auto& parentUpdate : m_pendingParentUpdates) {
+        if (RefPtr object = objectForID(parentUpdate.key))
+            object->setParent(parentUpdate.value);
+    }
+    m_pendingParentUpdates.clear();
+
     for (auto& update : m_pendingChildrenUpdates) {
         AXLOG(makeString("updating children for axID ", update.first.loggingString()));
         if (RefPtr object = objectForID(update.first))
diff --git a/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h b/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h
index 8a5ae19758ef..fa2cbc7eb0a2 100644
--- a/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h
+++ b/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h
@@ -364,6 +364,15 @@ private:
     // The key is the ID of the object that will be resolved into an m_pendingAppends NodeChange.
     // The value is whether the wrapper should be attached on the main thread or the AX thread.
     HashMap<AXID, AttachWrapper> m_unresolvedPendingAppends;
+    // Only accessed on the main thread.
+    // This is used when updating the isolated tree in response to dynamic children changes.
+    // It is required to protect objects from being incorrectly deleted when they are re-parented,
+    // as the original parent will want to queue it for removal, but we need to keep the object around
+    // for the new parent.
+    HashSet<AXID> m_protectedFromDeletionIDs;
+    // Only accessed on the main thread.
+    // The key is the ID of the object that will change its parent, and the value is the ID of the new parent for the key object.
+    HashMap<AXID, AXID> m_parentUpdates;

AG: this info is already on the m_nodeMap. Why do we need to duplicate it?

     // 1-based tree level, 0 = not collecting. Only accessed on the main thread.
     unsigned m_collectingNodeChangesAtTreeLevel { 0 };

@@ -376,6 +385,8 @@ private:
     Vector<AXPropertyChange> m_pendingPropertyChanges WTF_GUARDED_BY_LOCK(m_changeLogLock);
     Vector<AXID> m_pendingSubtreeRemovals WTF_GUARDED_BY_LOCK(m_changeLogLock); // Nodes whose subtrees are to be removed from the tree.
     Vector<std::pair<AXID, Vector<AXID>>> m_pendingChildrenUpdates WTF_GUARDED_BY_LOCK(m_changeLogLock);
+    HashSet<AXID> m_pendingProtectedFromDeletionIDs WTF_GUARDED_BY_LOCK(m_changeLogLock);
+    HashMap<AXID, AXID> m_pendingParentUpdates WTF_GUARDED_BY_LOCK(m_changeLogLock);
     AXID m_pendingFocusedNodeID WTF_GUARDED_BY_LOCK(m_changeLogLock);
     bool m_queuedForDestruction WTF_GUARDED_BY_LOCK(m_changeLogLock) { false };
     AXID m_focusedNodeID;

[Tyler Wilcock]

Created attachment 467865 [details]
Patch

[Tyler Wilcock]

Created attachment 467866 [details]
Patch

[Tyler Wilcock]

> AG: labelForAttributeChanged -> handleLabelForChanged ?
Updated.

> AXObjectCache::relationAttributes()
>          aria_labeledbyAttr,
>          aria_ownsAttr,
>          headersAttr,
> +        popovertargetAttr,
> 
> AG: I think we discussed this and decided to use ControlFor and ControledBy.
Indeed, and this line addition won't change that. I accidentally broke accessibility/mac/expanded-notification.html in my previous patch because it was missing popovertargetAttr here in this function, meaning we never set up the ControllerFor and ControlledBy AXRelationships. This fixes that and makes the test pass again.

> +        AXCanFocusChanged,
> AG: AXFocusableStateChanged ?

Updated.

> +    auto* axParent = axObject.parentObjectUnignored();
> +    auto nodeMapIterator = m_nodeMap.find(axObject.objectID());
> 
> AG: nodeMapIterator -> it.
I know this is a common shortening, but I think WebKit style recommends spelling variables out. I shortened it to just "iterator" rather than "nodeMapIterator".

> +        case AXPropertyName::TitleUIElement: {
> +            if (auto* titleUIElement = axObject.titleUIElement())
> +                propertyMap.set(AXPropertyName::TitleUIElement,
> titleUIElement->objectID());
> +            else
> +                propertyMap.set(AXPropertyName::TitleUIElement, AXID());
> 
> AG: can you write only one propertyMap.set(AXPropertyName::TitleUIElement,
> titleUIElement ? titleUIElement->objectID() : AXID());
Updated.

> value is the ID of the new parent for the key object.
> +    HashMap<AXID, AXID> m_parentUpdates;
> 
> AG: this info is already on the m_nodeMap. Why do we need to duplicate it?
Updated.

[EWS]

Committed 268493@main (7eb5b4bd73ce): <https://commits.webkit.org/268493@main>

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