AXIsolatedTree::updateChildren removes subtrees that should instead be moved

• Component: Accessibility
• Status: RESOLVED FIXED

[Tyler Wilcock]

In AXIsolatedTree::updateChildren, we can sometimes remove subtrees that are queued to be added somewhere else in the tree. Specifically, this can happen when:

  1. Object 123 is slated considered to be a new child based on the live AX tree, and we collect node changes for it.
  2. Object 123 is currently a member of a subtree of some other object in oldChildrenIDs.
  3. Because of 2, Object 123 is removed from the node map in removeSubtreeFromNodeMap and added to m_pendingSubtreeRemovals
  4. We try to queue the addition of this node somewhere in tree in queueChange, but ASSERT because Object 123 is not in the node map anymore.

This causes ASSERT(m_nodeMap.contains(objectID) in AXIsolatedTree::queueChange(const NodeChange&).

[Radar WebKit Bug Importer]

<rdar://problem/88415084>

[Tyler Wilcock]

Created attachment 450732 [details]
Patch

[Andres Gonzalez]

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

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

-        ASSERT(m_nodeMap.contains(parentID));
+        ASSERT_WITH_MESSAGE(m_nodeMap.contains(parentID), "node map should've contained parentID: %llu", parentID.toUInt64());

We have been using primarily loggingString() to log ObjectIdentifiers instead toUInt64(). Can we stick to one?

+    // Don't remove subtrees for objects that are part of the to-be-queued node changes.
+    // Doing this is important when a node moves to a different part of the tree rather than being deleted -- for example:
+    //   1. Object 123 is slated to be a child of this object (i.e. in newChildren), and we collect node changes for it.
+    //   2. Object 123 is currently a member of a subtree of some other object in oldChildrenIDs.
+    //   3. Thus, we don't want to delete Object 123 from the isolated tree, instead allowing it to be moved.
+    for (auto id : idsBeingChanged)
+        oldChildrenIDs.removeAll(id);
+
     // What is left in oldChildrenIDs are the IDs that are no longer children of axObject.
     // Thus, remove them from m_nodeMap and queue them to be removed from the tree.
     for (AXID& axID : oldChildrenIDs)
-        removeSubtreeFromNodeMap(axID);
+        removeSubtreeFromNodeMap(axID, idsBeingChanged);

Why do we need to pass idsBeingChanged to removeSubtreeFromNodeMap since all IDs on it were already removed from oldChildrenIDs?

Furthermore, the only case I can think of this happening is if the one that we are removing is added to the ancestry. If that is the case, this can be simplified.

On the other hand, how do we know that the subtree that is being re-parenting is exactly the same as before?

It would be good to have an HTML/JS construct that reproduce this scenario, although I realize the difficulty of that.

[Tyler Wilcock]

>      for (AXID& axID : oldChildrenIDs)
> -        removeSubtreeFromNodeMap(axID);
> +        removeSubtreeFromNodeMap(axID, idsBeingChanged);
> 
> Why do we need to pass idsBeingChanged to removeSubtreeFromNodeMap since all
> IDs on it were already removed from oldChildrenIDs?
Because the IDs we want to protect from being removed may not directly be a member of oldChildrenIDs, but instead a child of an element in oldChildrenIDs.

> Furthermore, the only case I can think of this happening is if the one that
> we are removing is added to the ancestry. If that is the case, this can be
> simplified.
Yeah, I think that's what's happening here. A subtree (or at least the root object of the subtree) is being moved elsewhere.

> On the other hand, how do we know that the subtree that is being
> re-parenting is exactly the same as before?
It might be the same, but it doesn't have to be. Its children will be whatever we computed for it in collectNodeChangesForSubtree (which is when we m_nodeMap.set(ID, children)), which in turn is based on the state of the live-tree children(). So I guess the important part of this patch is preventing the root of this subtree from being destroyed.

[Andres Gonzalez]

(In reply to Tyler Wilcock from comment #4)
> >      for (AXID& axID : oldChildrenIDs)
> > -        removeSubtreeFromNodeMap(axID);
> > +        removeSubtreeFromNodeMap(axID, idsBeingChanged);
> > 
> > Why do we need to pass idsBeingChanged to removeSubtreeFromNodeMap since all
> > IDs on it were already removed from oldChildrenIDs?
> Because the IDs we want to protect from being removed may not directly be a
> member of oldChildrenIDs, but instead a child of an element in
> oldChildrenIDs.

Right, then I think we don't need this:

+    for (auto id : idsBeingChanged)
+        oldChildrenIDs.removeAll(id);

and let removeSubtreeFromNodeMap do the filtering as you are doing now:

-        if (!axID.isValid())
+        if (!axID.isValid() || idsToKeep.contains(axID))
             continue;

> 
> > Furthermore, the only case I can think of this happening is if the one that
> > we are removing is added to the ancestry. If that is the case, this can be
> > simplified.
> Yeah, I think that's what's happening here. A subtree (or at least the root
> object of the subtree) is being moved elsewhere.
> 
> > On the other hand, how do we know that the subtree that is being
> > re-parenting is exactly the same as before?
> It might be the same, but it doesn't have to be. Its children will be
> whatever we computed for it in collectNodeChangesForSubtree (which is when
> we m_nodeMap.set(ID, children)), which in turn is based on the state of the
> live-tree children(). So I guess the important part of this patch is
> preventing the root of this subtree from being destroyed.

[Tyler Wilcock]

Created attachment 450799 [details]
Patch

[Tyler Wilcock]

> Right, then I think we don't need this:
> 
> +    for (auto id : idsBeingChanged)
> +        oldChildrenIDs.removeAll(id);
> 
> and let removeSubtreeFromNodeMap do the filtering as you are doing now:
> 
> -        if (!axID.isValid())
> +        if (!axID.isValid() || idsToKeep.contains(axID))
>              continue;
You're right. Fixed.

> We have been using primarily loggingString() to log ObjectIdentifiers instead toUInt64(). Can we stick to one?
Fixed this as well.

[Andres Gonzalez]

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

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

-        changes.append(nodeChangeForObject(*axObject, axParentID, true, updateNodeMap));
+        auto change = nodeChangeForObject(*axObject, axParentID, true, updateNodeMap);
+        changes.append(change);

I think this does an extra copy of change. The compiler may be smart and optimize it, but I wouldn't count on that.

--- a/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h
+++ a/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h

+    void collectNodeChangesForSubtree(AXCoreObject& object, AXID parentID, bool attachWrapper, Vector<NodeChange>& changes)
+    {
+        HashSet<AXID> idsBeingChanged;
+        collectNodeChangesForSubtree(object, parentID, attachWrapper, changes, idsBeingChanged);
+    }
+    void collectNodeChangesForSubtree(AXCoreObject&, AXID parentID, bool attachWrapper, Vector<NodeChange>&, HashSet<AXID>&);

Instead make collectNodeChangesForSubtree to take an std::optional<HashSet<AXID>> that default to nullopt, and then you can call it with or without that param.

[Tyler Wilcock]

Created attachment 450804 [details]
Patch

[Tyler Wilcock]

Created attachment 450808 [details]
Patch

[Tyler Wilcock]

> -        changes.append(nodeChangeForObject(*axObject, axParentID, true,
> updateNodeMap));
> +        auto change = nodeChangeForObject(*axObject, axParentID, true,
> updateNodeMap);
> +        changes.append(change);
> 
> I think this does an extra copy of change. The compiler may be smart and
> optimize it, but I wouldn't count on that.
Good point. The newest patch copies just the ID and moves the NodeChange into the Vector rather than copying it into the Vector.

> --- a/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h
> +++ a/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h
> 
> +    void collectNodeChangesForSubtree(AXCoreObject& object, AXID parentID,
> bool attachWrapper, Vector<NodeChange>& changes)
> +    {
> +        HashSet<AXID> idsBeingChanged;
> +        collectNodeChangesForSubtree(object, parentID, attachWrapper,
> changes, idsBeingChanged);
> +    }
> +    void collectNodeChangesForSubtree(AXCoreObject&, AXID parentID, bool
> attachWrapper, Vector<NodeChange>&, HashSet<AXID>&);
> 
> Instead make collectNodeChangesForSubtree to take an
> std::optional<HashSet<AXID>> that default to nullopt, and then you can call
> it with or without that param.
Presumably you meant std::optional<HashSet<AXID>&> (since we want a reference of the HashSet, not our own copy), and references can't be passed inside optionals. I made this a raw HashSet<AXID>* pointer instead.

[Tyler Wilcock]

Created attachment 450815 [details]
Patch

[EWS]

Committed r289097 (246794@main): <https://commits.webkit.org/246794@main>

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