Modified: trunk/Source/WebCore/ChangeLog (288962 => 288963)
--- trunk/Source/WebCore/ChangeLog 2022-02-02 18:32:06 UTC (rev 288962)
+++ trunk/Source/WebCore/ChangeLog 2022-02-02 18:42:28 UTC (rev 288963)
@@ -1,3 +1,55 @@
+2022-02-02 Andres Gonzalez <[email protected]>
+
+ Make modifications to the isolated Tree atomic.
+ https://bugs.webkit.org/show_bug.cgi?id=235683
+ <rdar://problem/88108412>
+
+ Reviewed by Chris Fleizach.
+
+ Covered by existing tests.
+
+ The isolated tree is currently updated in a non-atomic fashion, i.e.,
+ nodes are added or removed while clients are accessing the tree in an
+ inconsistent state. The idea of this patch is to make all necessary
+ changes in the tree in one atomic operation while the client thread,
+ or AX secondary thread, is blocked. To accomplish this and still be
+ responsive to client's requests on the AX thread, it is necessary that
+ all the processing in preparation for the update of the isolated tree
+ happens on the main thread without blocking the AX thread, and then do
+ the update of the tree in one atomic operation.
+
+ * accessibility/AXLogger.cpp:
+ (WebCore::operator<<):
+ Rearranged the properties of the AXCoreObject to log most relevant on top.
+ * accessibility/AccessibilityRenderObject.cpp:
+ (WebCore::AccessibilityRenderObject::computeAccessibilityIsIgnored const):
+ Removed AXTRACE from this method since it is called so often that it is
+ just noise in the log.
+ * accessibility/isolatedtree/AXIsolatedTree.cpp:
+ (WebCore::AXIsolatedTree::generateSubtree):
+ It now collects all the changes to be perform and queues them in one
+ operation under lock.
+ (WebCore::AXIsolatedTree::nodeChangeForObject):
+ (WebCore::AXIsolatedTree::queueChange):
+ Queues one single change, must be called under lock.
+ (WebCore::AXIsolatedTree::queueChangesAndRemovals):
+ Queues all necessary changes to the isolated tree, additions and removals.
+ (WebCore::AXIsolatedTree::collectNodeChangesForSubtree):
+ Collects on the main thread all the additions/changes to be done to the
+ isolated tree.
+ (WebCore::AXIsolatedTree::updateNode):
+ (WebCore::AXIsolatedTree::nodeAncestryChanges):
+ Connects a new isolated node to the existing hierarchy.
+ (WebCore::AXIsolatedTree::updateChildren):
+ (WebCore::AXIsolatedTree::removeSubtreeFromNodeMap):
+ (WebCore::AXIsolatedTree::updateChildrenIDs): Deleted.
+ (WebCore::AXIsolatedTree::createSubtree): Deleted.
+ Replaced with collectNodeChanges and queueChangesAndRemovals.
+ (WebCore::AXIsolatedTree::updateSubtree): Deleted, not used.
+ (WebCore::AXIsolatedTree::removeSubtree): Deleted, not used.
+ * accessibility/isolatedtree/AXIsolatedTree.h:
+ (WebCore::AXIsolatedTree::queueChangesAndRemovals):
+
2022-02-02 Gabriel Nava Marino <[email protected]>
null ptr deref in Editor::pasteWithPasteboard
Modified: trunk/Source/WebCore/accessibility/AXLogger.cpp (288962 => 288963)
--- trunk/Source/WebCore/accessibility/AXLogger.cpp 2022-02-02 18:32:06 UTC (rev 288962)
+++ trunk/Source/WebCore/accessibility/AXLogger.cpp 2022-02-02 18:42:28 UTC (rev 288963)
@@ -517,13 +517,16 @@
{
TextStream::GroupScope groupScope(stream);
stream << "objectID " << object.objectID();
- stream.dumpProperty("identifierAttribute", object.identifierAttribute());
auto role = object.roleValue();
stream.dumpProperty("roleValue", role);
+ auto* parent = object.parentObjectUnignored();
+ stream.dumpProperty("parentObject", parent ? parent->objectID() : AXID());
+
+ stream.dumpProperty("identifierAttribute", object.identifierAttribute());
+
auto* objectWithInterestingHTML = role == AccessibilityRole::Button ? // Add here other roles of interest.
&object : nullptr;
- auto* parent = object.parentObject();
if (role == AccessibilityRole::StaticText && parent)
objectWithInterestingHTML = parent;
if (objectWithInterestingHTML)
@@ -532,8 +535,6 @@
stream.dumpProperty("address", &object);
stream.dumpProperty("wrapper", object.wrapper());
- stream.dumpProperty("parentObject", parent ? parent->objectID() : AXID());
-
return stream;
}
Modified: trunk/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp (288962 => 288963)
--- trunk/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp 2022-02-02 18:32:06 UTC (rev 288962)
+++ trunk/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp 2022-02-02 18:42:28 UTC (rev 288963)
@@ -176,17 +176,6 @@
});
}
-void AXIsolatedTree::updateChildrenIDs(AXID axID, Vector<AXID>&& childrenIDs)
-{
- ASSERT(isMainThread());
- ASSERT(m_changeLogLock.isLocked());
-
- if (axID.isValid()) {
- m_nodeMap.set(axID, childrenIDs);
- m_pendingChildrenUpdates.append(std::make_pair(axID, WTFMove(childrenIDs)));
- }
-}
-
void AXIsolatedTree::generateSubtree(AXCoreObject& axObject, AXCoreObject* axParent, bool attachWrapper)
{
AXTRACE("AXIsolatedTree::generateSubtree");
@@ -195,15 +184,13 @@
if (!axObject.objectID().isValid())
return;
- auto object = createSubtree(axObject, axParent ? axParent->objectID() : AXID(), attachWrapper);
- Locker locker { m_changeLogLock };
- if (!axParent)
- setRootNode(object.ptr());
- else if (axParent->objectID().isValid()) // Need to check for the objectID of axParent again because it may have been detached while traversing the tree.
- updateChildrenIDs(axParent->objectID(), axParent->childrenIDs());
+ AXID parentID = axParent ? axParent->objectID() : AXID();
+ Vector<NodeChange> changes;
+ collectNodeChangesForSubtree(axObject, parentID, attachWrapper, changes);
+ queueChangesAndRemovals(changes);
}
-AXIsolatedTree::NodeChange AXIsolatedTree::nodeChangeForObject(AXCoreObject& axObject, AXID parentID, bool attachWrapper)
+AXIsolatedTree::NodeChange AXIsolatedTree::nodeChangeForObject(AXCoreObject& axObject, AXID parentID, bool attachWrapper, bool updateNodeMap)
{
ASSERT(isMainThread());
@@ -224,40 +211,72 @@
nodeChange.wrapper = axObject.wrapper();
}
+ if (updateNodeMap)
+ m_nodeMap.set(axObject.objectID(), axObject.childrenIDs());
+
+ if (!parentID.isValid()) {
+ Locker locker { m_changeLogLock };
+ setRootNode(nodeChange.isolatedObject.ptr());
+ }
+
return nodeChange;
}
-void AXIsolatedTree::queueChanges(const NodeChange& nodeChange, Vector<AXID>&& childrenIDs)
+void AXIsolatedTree::queueChange(const NodeChange& nodeChange)
{
ASSERT(isMainThread());
+ ASSERT(m_changeLogLock.isLocked());
- Locker locker { m_changeLogLock };
m_pendingAppends.append(nodeChange);
- updateChildrenIDs(nodeChange.isolatedObject->objectID(), WTFMove(childrenIDs));
+
+ AXID parentID = nodeChange.isolatedObject->parent();
+ if (parentID.isValid()) {
+ ASSERT(m_nodeMap.contains(parentID));
+ auto siblingsIDs = m_nodeMap.get(parentID);
+ m_pendingChildrenUpdates.append({ parentID, WTFMove(siblingsIDs) });
+ }
+
+ AXID objectID = nodeChange.isolatedObject->objectID();
+ ASSERT(objectID != parentID);
+ ASSERT(m_nodeMap.contains(objectID));
+ auto childrenIDs = m_nodeMap.get(objectID);
+ m_pendingChildrenUpdates.append({ objectID, WTFMove(childrenIDs) });
}
-Ref<AXIsolatedObject> AXIsolatedTree::createSubtree(AXCoreObject& axObject, AXID parentID, bool attachWrapper)
+void AXIsolatedTree::queueChangesAndRemovals(const Vector<NodeChange>& changes, const Vector<AXID>& subtreeRemovals)
{
- AXTRACE("AXIsolatedTree::createSubtree");
ASSERT(isMainThread());
+ Locker locker { m_changeLogLock };
+
+ for (const auto& axID : subtreeRemovals)
+ m_pendingSubtreeRemovals.append(axID);
+
+ for (const auto& change : changes)
+ queueChange(change);
+}
+
+void AXIsolatedTree::collectNodeChangesForSubtree(AXCoreObject& axObject, AXID parentID, bool attachWrapper, Vector<NodeChange>& changes)
+{
+ AXTRACE("AXIsolatedTree::collectNodeChangesForSubtree");
+ ASSERT(isMainThread());
+
if (!m_creatingSubtree)
axObjectCache()->processDeferredChildrenChangedList();
SetForScope<bool> creatingSubtree(m_creatingSubtree, true);
auto nodeChange = nodeChangeForObject(axObject, parentID, attachWrapper);
+ changes.append(nodeChange);
auto axChildren = axObject.children();
- Vector<AXID> childrenIDs;
- childrenIDs.reserveCapacity(axChildren.size());
+ Vector<AXID> axChildrenIDs;
+ axChildrenIDs.reserveCapacity(axChildren.size());
for (const auto& axChild : axChildren) {
- auto child = createSubtree(*axChild, axObject.objectID(), attachWrapper);
- childrenIDs.uncheckedAppend(child->objectID());
+ collectNodeChangesForSubtree(*axChild, axObject.objectID(), attachWrapper, changes);
+ axChildrenIDs.uncheckedAppend(axChild->objectID());
}
- queueChanges(nodeChange, WTFMove(childrenIDs));
-
- return nodeChange.isolatedObject;
+ m_nodeMap.set(axObject.objectID(), axChildrenIDs);
}
void AXIsolatedTree::updateNode(AXCoreObject& axObject)
@@ -267,16 +286,15 @@
ASSERT(isMainThread());
AXID axID = axObject.objectID();
- auto* axParent = axObject.parentObject();
+ auto* axParent = axObject.parentObjectUnignored();
AXID parentID = axParent ? axParent->objectID() : AXID();
- auto newObject = AXIsolatedObject::create(axObject, this, parentID);
- newObject->m_childrenIDs = axObject.childrenIDs();
+ auto change = nodeChangeForObject(axObject, parentID, true);
+ // Remove the old object and set the new one to be updated on the AX thread.
Locker locker { m_changeLogLock };
- // Remove the old object and set the new one to be updated on the AX thread.
m_pendingNodeRemovals.append(axID);
- m_pendingAppends.append({ newObject, axObject.wrapper() });
+ queueChange(change);
}
void AXIsolatedTree::updateNodeProperty(const AXCoreObject& axObject, AXPropertyName property)
@@ -309,14 +327,33 @@
m_pendingPropertyChanges.append({ axObject.objectID(), propertyMap });
}
-void AXIsolatedTree::updateSubtree(AXCoreObject& axObject)
+Vector<AXIsolatedTree::NodeChange> AXIsolatedTree::nodeAncestryChanges(AXCoreObject& axCoreObject)
{
- AXTRACE("AXIsolatedTree::updateSubtree");
- AXLOG(&axObject);
- ASSERT(isMainThread());
+ Vector<NodeChange> changes;
- removeSubtree(axObject.objectID());
- generateSubtree(axObject, axObject.parentObject(), false);
+ auto* axObject = &axCoreObject;
+ while (axObject && !m_nodeMap.contains(axObject->objectID())) {
+ // axObject has no node in the isolated tree, thus add it.
+ AXLOG("axObject not in the isolated tree:");
+ AXLOG(axObject);
+ auto* axParent = axObject->parentObjectUnignored();
+ AXLOG("axParent:");
+ AXLOG(axParent);
+ AXID axParentID = axParent ? axParent->objectID() : AXID();
+
+ // If axObject is the original object for which we are adding its ancestry, don't update the nodeMap since updateChildren needs to compare its previous children with the new ones.
+ bool updateNodeMap = axObject != &axCoreObject;
+ changes.append(nodeChangeForObject(*axObject, axParentID, true, updateNodeMap));
+
+ if (axParent)
+ m_nodeMap.set(axParent->objectID(), axParent->childrenIDs());
+
+ axObject = axParent;
+ }
+
+ // Since the NodeChanges are added to the changes vector in a child -> parent traversal instead of a parent -> child traversal, we need to reverse changes.
+ changes.reverse();
+ return changes;
}
void AXIsolatedTree::updateChildren(AXCoreObject& axObject)
@@ -337,63 +374,36 @@
// updateChildren may be called as the result of a children changed
// notification for an axObject that has no associated isolated object.
// An example of this is when an empty element such as a <canvas> or <div>
- // is added a new child. So find the closest ancestor of axObject that has
- // an associated isolated object and update its children.
- auto iterator = m_nodeMap.end();
- auto* axAncestor = Accessibility::findAncestor(axObject, true, [&iterator, this] (auto& ancestor) {
- auto it = m_nodeMap.find(ancestor.objectID());
- if (it != m_nodeMap.end()) {
- iterator = it;
- return true;
- }
+ // is added a new child. Thus add the ancestry that connects the associated
+ // isolated object to the closest existing ancestor.
+ Vector<NodeChange> changes = nodeAncestryChanges(axObject);
- // ancestor has no node in the isolated tree, thus add it.
- auto* axParent = ancestor.parentObject();
- AXID axParentID = axParent ? axParent->objectID() : AXID();
- auto nodeChange = nodeChangeForObject(ancestor, axParentID, true);
- queueChanges(nodeChange, ancestor.childrenIDs());
+ auto oldChildrenIDs = m_nodeMap.get(axObject.objectID());
- return false;
- });
- if (!axAncestor || !axAncestor->objectID().isValid() || iterator == m_nodeMap.end()) {
- // This update triggered before the isolated tree has been repopulated.
- // Return here since there is nothing to update.
- return;
- }
+ const auto& axChildren = axObject.children();
+ auto newChildrenIDs = axObject.childrenIDs(false);
- // iterator is pointing to the m_nodeMap entry corresponding to axAncestor->objectID().
- ASSERT(iterator->key == axAncestor->objectID());
- auto removals = iterator->value;
-
- const auto& axChildren = axAncestor->children();
- auto axChildrenIDs = axAncestor->childrenIDs(false);
-
- bool updatedChild = false; // Set to true if at least one child's subtree is updated.
- for (size_t i = 0; i < axChildren.size() && i < axChildrenIDs.size(); ++i) {
- ASSERT(axChildren[i]->objectID() == axChildrenIDs[i]);
- ASSERT(axChildrenIDs[i].isValid());
- size_t index = removals.find(axChildrenIDs[i]);
+ for (size_t i = 0; i < axChildren.size(); ++i) {
+ ASSERT(axChildren[i]->objectID() == newChildrenIDs[i]);
+ ASSERT(newChildrenIDs[i].isValid());
+ size_t index = oldChildrenIDs.find(newChildrenIDs[i]);
if (index != notFound)
- removals.remove(index);
+ oldChildrenIDs.remove(index);
else {
// This is a new child, add it to the tree.
AXLOG("Adding a new child for:");
AXLOG(axChildren[i]);
- generateSubtree(*axChildren[i], axAncestor, true);
- updatedChild = true;
+ collectNodeChangesForSubtree(*axChildren[i], axObject.objectID(), true, changes);
}
}
- // What is left in removals are the IDs that are no longer children of
- // axObject. Thus, remove them from the tree.
- for (const AXID& childID : removals)
- removeSubtree(childID);
+ m_nodeMap.set(axObject.objectID(), newChildrenIDs);
- if (updatedChild || removals.size()) {
- // Make the children IDs of the isolated object to be the same as the AXObject's.
- Locker locker { m_changeLogLock };
- updateChildrenIDs(axAncestor->objectID(), WTFMove(axChildrenIDs));
- }
+ // 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);
+ queueChangesAndRemovals(changes, oldChildrenIDs);
}
RefPtr<AXIsolatedObject> AXIsolatedTree::focusedNode()
@@ -461,7 +471,7 @@
m_pendingNodeRemovals.append(axID);
}
-void AXIsolatedTree::removeSubtree(AXID axID)
+void AXIsolatedTree::removeSubtreeFromNodeMap(AXID axID)
{
AXTRACE("AXIsolatedTree::removeSubtree");
AXLOG(makeString("Removing subtree for axID ", axID.loggingString()));
@@ -479,9 +489,6 @@
m_nodeMap.remove(axID);
}
}
-
- Locker locker { m_changeLogLock };
- m_pendingSubtreeRemovals.append(axID);
}
void AXIsolatedTree::applyPendingChanges()
Modified: trunk/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h (288962 => 288963)
--- trunk/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h 2022-02-02 18:32:06 UTC (rev 288962)
+++ trunk/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h 2022-02-02 18:42:28 UTC (rev 288963)
@@ -354,7 +354,6 @@
void generateSubtree(AXCoreObject&, AXCoreObject*, bool attachWrapper);
void updateNode(AXCoreObject&);
void updateNodeProperty(const AXCoreObject&, AXPropertyName);
- void updateSubtree(AXCoreObject&);
void updateChildren(AXCoreObject&);
double loadingProgress() { return m_loadingProgress; }
@@ -363,7 +362,7 @@
// Removes the given node leaving all descendants alone.
void removeNode(AXID);
// Removes the given node and all its descendants.
- void removeSubtree(AXID);
+ void removeSubtreeFromNodeMap(AXID);
// Both setRootNodeID and setFocusedNodeID are called during the generation
// of the IsolatedTree.
@@ -386,11 +385,11 @@
static HashMap<PageIdentifier, Ref<AXIsolatedTree>>& treePageCache() WTF_REQUIRES_LOCK(s_cacheLock);
// Called on main thread.
- NodeChange nodeChangeForObject(AXCoreObject&, AXID parentID, bool attachWrapper);
- void queueChanges(const NodeChange&, Vector<AXID>&& childrenIDs);
- Ref<AXIsolatedObject> createSubtree(AXCoreObject&, AXID parentID, bool attachWrapper);
- // Called on main thread to update both m_nodeMap and m_pendingChildrenUpdates.
- void updateChildrenIDs(AXID parentID, Vector<AXID>&& childrenIDs) WTF_REQUIRES_LOCK(m_changeLogLock);
+ NodeChange nodeChangeForObject(AXCoreObject&, AXID parentID, bool attachWrapper = true, bool updateNodeMap = true);
+ void collectNodeChangesForSubtree(AXCoreObject&, AXID parentID, bool attachWrapper, Vector<NodeChange>&);
+ void queueChange(const NodeChange&) WTF_REQUIRES_LOCK(m_changeLogLock);
+ void queueChangesAndRemovals(const Vector<NodeChange>&, const Vector<AXID>& = { });
+ Vector<NodeChange> nodeAncestryChanges(AXCoreObject&);
AXIsolatedTreeID m_treeID;
AXObjectCache* m_axObjectCache { nullptr };
