AX: AXIsolatedTree::updateChildren sometimes fails to update isolated subtrees when...
[WebKit.git] / Source / WebCore / accessibility / isolatedtree / AXIsolatedTree.cpp
1 /*
2  * Copyright (C) 2019 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27
28 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
29 #include "AXIsolatedTree.h"
30
31 #include "AXIsolatedObject.h"
32 #include "AXLogger.h"
33 #include "FrameView.h"
34 #include "Page.h"
35 #include <wtf/NeverDestroyed.h>
36 #include <wtf/SetForScope.h>
37
38 namespace WebCore {
39
40 Lock AXIsolatedTree::s_cacheLock;
41
42 static unsigned newTreeID()
43 {
44     static unsigned s_currentTreeID = 0;
45     return ++s_currentTreeID;
46 }
47
48 HashMap<PageIdentifier, Ref<AXIsolatedTree>>& AXIsolatedTree::treePageCache()
49 {
50     static NeverDestroyed<HashMap<PageIdentifier, Ref<AXIsolatedTree>>> map;
51     return map;
52 }
53
54 HashMap<AXIsolatedTreeID, Ref<AXIsolatedTree>>& AXIsolatedTree::treeIDCache()
55 {
56     static NeverDestroyed<HashMap<AXIsolatedTreeID, Ref<AXIsolatedTree>>> map;
57     return map;
58 }
59
60 AXIsolatedTree::AXIsolatedTree(AXObjectCache* axObjectCache)
61     : m_treeID(newTreeID())
62     , m_axObjectCache(axObjectCache)
63     , m_usedOnAXThread(axObjectCache->usedOnAXThread())
64 {
65     AXTRACE("AXIsolatedTree::AXIsolatedTree"_s);
66     ASSERT(isMainThread());
67 }
68
69 AXIsolatedTree::~AXIsolatedTree()
70 {
71     AXTRACE("AXIsolatedTree::~AXIsolatedTree"_s);
72 }
73
74 void AXIsolatedTree::clear()
75 {
76     AXTRACE("AXIsolatedTree::clear"_s);
77     ASSERT(isMainThread());
78     m_axObjectCache = nullptr;
79     m_nodeMap.clear();
80
81     Locker locker { m_changeLogLock };
82     m_pendingSubtreeRemovals.append(m_rootNode->objectID());
83     m_rootNode = nullptr;
84 }
85
86 RefPtr<AXIsolatedTree> AXIsolatedTree::treeForID(AXIsolatedTreeID treeID)
87 {
88     AXTRACE("AXIsolatedTree::treeForID"_s);
89     Locker locker { s_cacheLock };
90     return treeIDCache().get(treeID);
91 }
92
93 Ref<AXIsolatedTree> AXIsolatedTree::create(AXObjectCache* axObjectCache)
94 {
95     AXTRACE("AXIsolatedTree::create"_s);
96     ASSERT(isMainThread());
97     ASSERT(axObjectCache && axObjectCache->pageID());
98
99     auto tree = adoptRef(*new AXIsolatedTree(axObjectCache));
100
101     auto& document = axObjectCache->document();
102     if (!document.view()->layoutContext().isInRenderTreeLayout() && !document.inRenderTreeUpdate() && !document.inStyleRecalc())
103         document.updateLayoutIgnorePendingStylesheets();
104
105     tree->m_maxTreeDepth = document.settings().maximumHTMLParserDOMTreeDepth();
106     ASSERT(tree->m_maxTreeDepth);
107
108     // Generate the nodes of the tree and set its root and focused objects.
109     // For this, we need the root and focused objects of the AXObject tree.
110     auto* axRoot = axObjectCache->getOrCreate(axObjectCache->document().view());
111     if (axRoot)
112         tree->generateSubtree(*axRoot);
113     auto* axFocus = axObjectCache->focusedObjectForPage(axObjectCache->document().page());
114     if (axFocus)
115         tree->setFocusedNodeID(axFocus->objectID());
116
117     // Now that the tree is ready to take client requests, add it to the tree
118     // maps so that it can be found.
119     auto pageID = axObjectCache->pageID();
120     Locker locker { s_cacheLock };
121     ASSERT(!treePageCache().contains(*pageID));
122     treePageCache().set(*pageID, tree.copyRef());
123     treeIDCache().set(tree->treeID(), tree.copyRef());
124     tree->updateLoadingProgress(axObjectCache->loadingProgress());
125
126     return tree;
127 }
128
129 void AXIsolatedTree::removeTreeForPageID(PageIdentifier pageID)
130 {
131     AXTRACE("AXIsolatedTree::removeTreeForPageID"_s);
132     ASSERT(isMainThread());
133     Locker locker { s_cacheLock };
134
135     if (auto tree = treePageCache().take(pageID)) {
136         tree->clear();
137         treeIDCache().remove(tree->treeID());
138     }
139 }
140
141 RefPtr<AXIsolatedTree> AXIsolatedTree::treeForPageID(PageIdentifier pageID)
142 {
143     Locker locker { s_cacheLock };
144
145     if (auto tree = treePageCache().get(pageID))
146         return RefPtr { tree };
147
148     return nullptr;
149 }
150
151 RefPtr<AXIsolatedObject> AXIsolatedTree::nodeForID(const AXID& axID) const
152 {
153     // In isolated tree mode 2, only access m_readerThreadNodeMap on the AX thread.
154     ASSERT(m_usedOnAXThread ? !isMainThread() : isMainThread());
155     if (m_usedOnAXThread && isMainThread())
156         return nullptr;
157
158     return axID.isValid() ? m_readerThreadNodeMap.get(axID) : nullptr;
159 }
160
161 Vector<RefPtr<AXCoreObject>> AXIsolatedTree::objectsForIDs(const Vector<AXID>& axIDs)
162 {
163     AXTRACE("AXIsolatedTree::objectsForIDs"_s);
164     ASSERT(!isMainThread());
165
166     Vector<RefPtr<AXCoreObject>> result;
167     result.reserveInitialCapacity(axIDs.size());
168     for (auto& axID : axIDs) {
169         auto object = nodeForID(axID);
170         if (object) {
171             result.uncheckedAppend(object);
172             continue;
173         }
174
175         // There is no isolated object for this AXID. This can happen if the corresponding live object is ignored.
176         // If there is a live object for this ID and it is an ignored target of a relationship, create an isolated object for it.
177         object = Accessibility::retrieveValueFromMainThread<RefPtr<AXIsolatedObject>>([&axID, this] () -> RefPtr<AXIsolatedObject> {
178             auto* cache = axObjectCache();
179             if (!cache || !cache->relationTargetIDs().contains(axID))
180                 return nullptr;
181
182             auto* axObject = cache->objectForID(axID);
183             if (!axObject || !axObject->accessibilityIsIgnored())
184                 return nullptr;
185
186             auto object = AXIsolatedObject::create(*axObject, const_cast<AXIsolatedTree*>(this));
187             ASSERT(axObject->wrapper());
188             object->attachPlatformWrapper(axObject->wrapper());
189             return object;
190         });
191         if (object) {
192             m_readerThreadNodeMap.add(axID, *object);
193             result.uncheckedAppend(object);
194         }
195     }
196     result.shrinkToFit();
197     return result;
198 }
199
200 void AXIsolatedTree::generateSubtree(AXCoreObject& axObject)
201 {
202     AXTRACE("AXIsolatedTree::generateSubtree"_s);
203     ASSERT(isMainThread());
204
205     if (!axObject.objectID().isValid())
206         return;
207
208     collectNodeChangesForSubtree(axObject);
209     queueRemovalsAndUnresolvedChanges({ });
210 }
211
212 static bool shouldCreateNodeChange(AXCoreObject& axObject)
213 {
214     // We should never create an isolated object from an ignored object or one with an invalid ID.
215     return !axObject.accessibilityIsIgnored() && axObject.objectID().isValid();
216 }
217
218 std::optional<AXIsolatedTree::NodeChange> AXIsolatedTree::nodeChangeForObject(Ref<AXCoreObject> axObject, AttachWrapper attachWrapper)
219 {
220     ASSERT(isMainThread());
221     ASSERT(axObject->objectID().isValid());
222
223     if (!shouldCreateNodeChange(axObject.get()))
224         return std::nullopt;
225
226     auto object = AXIsolatedObject::create(axObject, this);
227     NodeChange nodeChange { object, nullptr };
228
229     ASSERT(axObject->wrapper());
230     if (attachWrapper == AttachWrapper::OnMainThread)
231         object->attachPlatformWrapper(axObject->wrapper());
232     else {
233         // Set the wrapper in the NodeChange so that it is set on the AX thread.
234         nodeChange.wrapper = axObject->wrapper();
235     }
236
237     m_nodeMap.set(axObject->objectID(), ParentChildrenIDs { nodeChange.isolatedObject->parent(), axObject->childrenIDs() });
238
239     if (!nodeChange.isolatedObject->parent().isValid()) {
240         Locker locker { m_changeLogLock };
241         setRootNode(nodeChange.isolatedObject.ptr());
242     }
243
244     return nodeChange;
245 }
246
247 void AXIsolatedTree::queueChange(const NodeChange& nodeChange)
248 {
249     ASSERT(isMainThread());
250     ASSERT(m_changeLogLock.isLocked());
251
252     m_pendingAppends.append(nodeChange);
253
254     AXID parentID = nodeChange.isolatedObject->parent();
255     if (parentID.isValid()) {
256         ASSERT_WITH_MESSAGE(m_nodeMap.contains(parentID), "node map should've contained parentID: %s", parentID.loggingString().utf8().data());
257         auto siblingsIDs = m_nodeMap.get(parentID).childrenIDs;
258         m_pendingChildrenUpdates.append({ parentID, WTFMove(siblingsIDs) });
259     }
260
261     AXID objectID = nodeChange.isolatedObject->objectID();
262     ASSERT_WITH_MESSAGE(objectID != parentID, "object ID was the same as its parent ID (%s) when queueing a node change", objectID.loggingString().utf8().data());
263     ASSERT_WITH_MESSAGE(m_nodeMap.contains(objectID), "node map should've contained objectID: %s", objectID.loggingString().utf8().data());
264     auto childrenIDs = m_nodeMap.get(objectID).childrenIDs;
265     m_pendingChildrenUpdates.append({ objectID, WTFMove(childrenIDs) });
266 }
267
268 void AXIsolatedTree::queueRemovals(const Vector<AXID>& subtreeRemovals)
269 {
270     ASSERT(isMainThread());
271
272     Locker locker { m_changeLogLock };
273     queueRemovalsLocked(subtreeRemovals);
274 }
275
276 void AXIsolatedTree::queueRemovalsLocked(const Vector<AXID>& subtreeRemovals)
277 {
278     ASSERT(isMainThread());
279     ASSERT(m_changeLogLock.isLocked());
280
281     for (const auto& axID : subtreeRemovals)
282         m_pendingSubtreeRemovals.append(axID);
283 }
284
285 void AXIsolatedTree::queueRemovalsAndUnresolvedChanges(const Vector<AXID>& subtreeRemovals)
286 {
287     ASSERT(isMainThread());
288
289     Vector<NodeChange> resolvedAppends;
290     if (!m_unresolvedPendingAppends.isEmpty()) {
291         if (auto* cache = axObjectCache()) {
292             resolvedAppends.reserveInitialCapacity(m_unresolvedPendingAppends.size());
293             for (const auto& unresolvedAppend : m_unresolvedPendingAppends) {
294                 if (auto* axObject = cache->objectForID(unresolvedAppend.key)) {
295                     if (auto nodeChange = nodeChangeForObject(*axObject, unresolvedAppend.value))
296                         resolvedAppends.uncheckedAppend(WTFMove(*nodeChange));
297                 }
298             }
299             m_unresolvedPendingAppends.clear();
300         }
301     }
302
303     Locker locker { m_changeLogLock };
304     for (const auto& resolvedAppend : resolvedAppends)
305         queueChange(resolvedAppend);
306     queueRemovalsLocked(subtreeRemovals);
307 }
308
309 void AXIsolatedTree::collectNodeChangesForSubtree(AXCoreObject& axObject)
310 {
311     AXTRACE("AXIsolatedTree::collectNodeChangesForSubtree"_s);
312     ASSERT(isMainThread());
313
314     if (!axObject.objectID().isValid()) {
315         // Bail out here, we can't build an isolated tree branch rooted at an object with no ID.
316         return;
317     }
318
319     SetForScope collectingAtTreeLevel(m_collectingNodeChangesAtTreeLevel, m_collectingNodeChangesAtTreeLevel + 1);
320     if (m_collectingNodeChangesAtTreeLevel >= m_maxTreeDepth)
321         return;
322
323     m_unresolvedPendingAppends.set(axObject.objectID(), AttachWrapper::OnMainThread);
324     auto axChildrenCopy = axObject.children();
325     Vector<AXID> axChildrenIDs;
326     axChildrenIDs.reserveInitialCapacity(axChildrenCopy.size());
327     for (const auto& axChild : axChildrenCopy) {
328         if (!axChild || axChild.get() == &axObject) {
329             ASSERT_NOT_REACHED();
330             continue;
331         }
332
333         axChildrenIDs.uncheckedAppend(axChild->objectID());
334         collectNodeChangesForSubtree(*axChild);
335     }
336     axChildrenIDs.shrinkToFit();
337
338     // Update the m_nodeMap.
339     auto* axParent = axObject.parentObjectUnignored();
340     m_nodeMap.set(axObject.objectID(), ParentChildrenIDs { axParent ? axParent->objectID() : AXID(), WTFMove(axChildrenIDs) });
341 }
342
343 void AXIsolatedTree::updateNode(AXCoreObject& axObject)
344 {
345     AXTRACE("AXIsolatedTree::updateNode"_s);
346     AXLOG(&axObject);
347     ASSERT(isMainThread());
348
349     // If we update a node as the result of some side effect while collecting node changes (e.g. a role change from
350     // AccessibilityRenderObject::updateRoleAfterChildrenCreation), queue the append up to be resolved with the rest
351     // of the collected changes. This prevents us from creating two node changes for the same object.
352     if (isCollectingNodeChanges()) {
353         m_unresolvedPendingAppends.set(axObject.objectID(), AttachWrapper::OnAXThread);
354         return;
355     }
356     // Otherwise, resolve the change immediately and queue it up.
357     // In both cases, we can't attach the wrapper immediately on the main thread, since the wrapper could be in use
358     // on the AX thread (because this function updates an existing node).
359     if (auto change = nodeChangeForObject(axObject, AttachWrapper::OnAXThread)) {
360         Locker locker { m_changeLogLock };
361         queueChange(WTFMove(*change));
362     }
363 }
364
365 void AXIsolatedTree::updateNodeProperty(AXCoreObject& axObject, AXPropertyName property)
366 {
367     AXTRACE("AXIsolatedTree::updateNodeProperty"_s);
368     ASSERT(isMainThread());
369
370     AXPropertyMap propertyMap;
371     switch (property) {
372     case AXPropertyName::ARIATreeItemContent:
373         propertyMap.set(AXPropertyName::ARIATreeItemContent, axIDs(axObject.ariaTreeItemContent()));
374         break;
375     case AXPropertyName::ARIATreeRows: {
376         AXCoreObject::AccessibilityChildrenVector ariaTreeRows;
377         axObject.ariaTreeRows(ariaTreeRows);
378         propertyMap.set(AXPropertyName::ARIATreeRows, axIDs(ariaTreeRows));
379         break;
380     }
381     case AXPropertyName::CanSetFocusAttribute:
382         propertyMap.set(AXPropertyName::CanSetFocusAttribute, axObject.canSetFocusAttribute());
383         break;
384     case AXPropertyName::CanSetValueAttribute:
385         propertyMap.set(AXPropertyName::CanSetValueAttribute, axObject.canSetValueAttribute());
386         break;
387     case AXPropertyName::CurrentValue:
388         propertyMap.set(AXPropertyName::CurrentValue, axObject.currentValue().isolatedCopy());
389         break;
390     case AXPropertyName::DisclosedRows:
391         propertyMap.set(AXPropertyName::DisclosedRows, axIDs(axObject.disclosedRows()));
392         break;
393     case AXPropertyName::IdentifierAttribute:
394         propertyMap.set(AXPropertyName::IdentifierAttribute, axObject.identifierAttribute().isolatedCopy());
395         break;
396     case AXPropertyName::IsChecked:
397         ASSERT(axObject.supportsCheckedState());
398         propertyMap.set(AXPropertyName::IsChecked, axObject.isChecked());
399         propertyMap.set(AXPropertyName::ButtonState, axObject.checkboxOrRadioValue());
400         break;
401     case AXPropertyName::IsEnabled:
402         propertyMap.set(AXPropertyName::IsEnabled, axObject.isEnabled());
403         break;
404     case AXPropertyName::IsExpanded:
405         propertyMap.set(AXPropertyName::IsExpanded, axObject.isExpanded());
406         break;
407     case AXPropertyName::IsRequired:
408         propertyMap.set(AXPropertyName::IsRequired, axObject.isRequired());
409         break;
410     case AXPropertyName::IsSelected:
411         propertyMap.set(AXPropertyName::IsSelected, axObject.isSelected());
412         break;
413     case AXPropertyName::MaxValueForRange:
414         propertyMap.set(AXPropertyName::MaxValueForRange, axObject.maxValueForRange());
415         break;
416     case AXPropertyName::MinValueForRange:
417         propertyMap.set(AXPropertyName::MinValueForRange, axObject.minValueForRange());
418         break;
419     case AXPropertyName::Orientation:
420         propertyMap.set(AXPropertyName::Orientation, static_cast<int>(axObject.orientation()));
421         break;
422     case AXPropertyName::PosInSet:
423         propertyMap.set(AXPropertyName::PosInSet, axObject.posInSet());
424         break;
425     case AXPropertyName::ReadOnlyValue:
426         propertyMap.set(AXPropertyName::ReadOnlyValue, axObject.readOnlyValue().isolatedCopy());
427         break;
428     case AXPropertyName::SetSize:
429         propertyMap.set(AXPropertyName::SetSize, axObject.setSize());
430         break;
431     case AXPropertyName::SortDirection:
432         propertyMap.set(AXPropertyName::SortDirection, static_cast<int>(axObject.sortDirection()));
433         break;
434     case AXPropertyName::SupportsPosInSet:
435         propertyMap.set(AXPropertyName::SupportsPosInSet, axObject.supportsPosInSet());
436         break;
437     case AXPropertyName::SupportsSetSize:
438         propertyMap.set(AXPropertyName::SupportsSetSize, axObject.supportsSetSize());
439         break;
440     case AXPropertyName::ValueForRange:
441         propertyMap.set(AXPropertyName::ValueForRange, axObject.valueForRange());
442         break;
443     default:
444         return;
445     }
446
447     Locker locker { m_changeLogLock };
448     m_pendingPropertyChanges.append({ axObject.objectID(), propertyMap });
449 }
450
451 void AXIsolatedTree::updateNodeAndDependentProperties(AXCoreObject& axObject)
452 {
453     ASSERT(isMainThread());
454
455     updateNode(axObject);
456
457     if (auto* treeAncestor = Accessibility::findAncestor(axObject, true, [] (const auto& object) { return object.isTree(); }))
458         updateNodeProperty(*treeAncestor, AXPropertyName::ARIATreeRows);
459 }
460
461 void AXIsolatedTree::updateChildren(AXCoreObject& axObject, ResolveNodeChanges resolveNodeChanges)
462 {
463     AXTRACE("AXIsolatedTree::updateChildren"_s);
464     AXLOG("For AXObject:");
465     AXLOG(&axObject);
466     ASSERT(isMainThread());
467
468     if (m_nodeMap.isEmpty()) {
469         ASSERT_NOT_REACHED();
470         return;
471     }
472
473     if (!axObject.document() || !axObject.document()->hasLivingRenderTree())
474         return;
475
476     // updateChildren may be called as the result of a children changed
477     // notification for an axObject that has no associated isolated object.
478     // An example of this is when an empty element such as a <canvas> or <div>
479     // has added a new child. So find the closest ancestor of axObject that has
480     // an associated isolated object and update its children.
481     auto* axAncestor = Accessibility::findAncestor(axObject, true, [this] (auto& ancestor) {
482         return m_nodeMap.find(ancestor.objectID()) != m_nodeMap.end();
483     });
484
485     if (!axAncestor || !axAncestor->objectID().isValid()) {
486         // This update was triggered before the isolated tree has been repopulated.
487         // Return here since there is nothing to update.
488         AXLOG("Bailing because no ancestor could be found, or ancestor had an invalid objectID");
489         return;
490     }
491
492     if (axAncestor != &axObject) {
493         AXLOG(makeString("Original object with ID ", axObject.objectID().loggingString(), " wasn't in the isolated tree, so instead updating the closest in-isolated-tree ancestor:"));
494         AXLOG(axAncestor);
495         for (auto& child : axObject.children()) {
496             auto* liveChild = dynamicDowncast<AccessibilityObject>(child.get());
497             if (!liveChild || liveChild->childrenInitialized())
498                 continue;
499
500             if (!m_nodeMap.contains(liveChild->objectID())) {
501                 if (!shouldCreateNodeChange(*liveChild))
502                     continue;
503
504                 // This child should be added to the isolated tree but hasn't been yet.
505                 // Add it to the nodemap so the recursive call to updateChildren below properly builds the subtree for this object.
506                 auto* parent = liveChild->parentObjectUnignored();
507                 m_nodeMap.set(liveChild->objectID(), ParentChildrenIDs { parent ? parent->objectID() : AXID(), liveChild->childrenIDs() });
508                 m_unresolvedPendingAppends.set(liveChild->objectID(), AttachWrapper::OnMainThread);
509             }
510
511             AXLOG(makeString(
512                 "Child ID ", liveChild->objectID().loggingString(), " of original object ID ", axObject.objectID().loggingString(), " was found in the isolated tree with uninitialized live children. Updating its isolated children."
513             ));
514             // Don't immediately resolve node changes in these recursive calls to updateChildren. This avoids duplicate node change creation in this scenario:
515             //   1. Some subtree is updated in the below call to updateChildren.
516             //   2. Later in this function, when updating axAncestor, we update some higher subtree that includes the updated subtree from step 1.
517             updateChildren(*liveChild, ResolveNodeChanges::No);
518         }
519     }
520
521     auto oldIDs = m_nodeMap.get(axAncestor->objectID());
522     auto& oldChildrenIDs = oldIDs.childrenIDs;
523
524     const auto& newChildren = axAncestor->children();
525     auto newChildrenIDs = axAncestor->childrenIDs(false);
526
527     for (size_t i = 0; i < newChildren.size(); ++i) {
528         ASSERT(newChildren[i]->objectID() == newChildrenIDs[i]);
529         ASSERT(newChildrenIDs[i].isValid());
530         size_t index = oldChildrenIDs.find(newChildrenIDs[i]);
531         if (index != notFound)
532             oldChildrenIDs.remove(index);
533         else {
534             // This is a new child, add it to the tree.
535             AXLOG(makeString("AXID ", axAncestor->objectID().loggingString(), " gaining new subtree, starting at ID ", newChildren[i]->objectID().loggingString(), ":"));
536             AXLOG(newChildren[i]);
537             collectNodeChangesForSubtree(*newChildren[i]);
538         }
539     }
540     m_nodeMap.set(axAncestor->objectID(), ParentChildrenIDs { oldIDs.parentID, WTFMove(newChildrenIDs) });
541
542     // What is left in oldChildrenIDs are the IDs that are no longer children of axAncestor.
543     // Thus, remove them from m_nodeMap and queue them to be removed from the tree.
544     for (const AXID& axID : oldChildrenIDs) {
545         // However, we don't want to remove subtrees from the nodemap that are part of the to-be-queued node changes (i.e those in `idsBeingChanged`).
546         // This is important when a node moves to a different part of the tree rather than being deleted -- for example:
547         //   1. Object 123 is slated to be a child of this object (i.e. in newChildren), and we collect node changes for it.
548         //   2. Object 123 is currently a member of a subtree of some other object in oldChildrenIDs.
549         //   3. Thus, we don't want to delete Object 123 from the nodemap, instead allowing it to be moved.
550         if (axID.isValid())
551             removeSubtreeFromNodeMap(axID, axAncestor);
552     }
553
554     if (resolveNodeChanges == ResolveNodeChanges::Yes)
555         queueRemovalsAndUnresolvedChanges(oldChildrenIDs);
556     else
557         queueRemovals(oldChildrenIDs);
558
559     // Also queue updates to the target node itself and any properties that depend on children().
560     updateNodeAndDependentProperties(*axAncestor);
561 }
562
563 RefPtr<AXIsolatedObject> AXIsolatedTree::focusedNode()
564 {
565     AXTRACE("AXIsolatedTree::focusedNode"_s);
566     RELEASE_ASSERT(!isMainThread());
567     // Apply pending changes in case focus has changed and hasn't been updated.
568     applyPendingChanges();
569     AXLOG(makeString("focusedNodeID ", m_focusedNodeID.loggingString()));
570     AXLOG("focused node:");
571     AXLOG(nodeForID(m_focusedNodeID));
572     return nodeForID(m_focusedNodeID);
573 }
574
575 RefPtr<AXIsolatedObject> AXIsolatedTree::rootNode()
576 {
577     AXTRACE("AXIsolatedTree::rootNode"_s);
578     Locker locker { m_changeLogLock };
579     return m_rootNode;
580 }
581
582 void AXIsolatedTree::setRootNode(AXIsolatedObject* root)
583 {
584     AXTRACE("AXIsolatedTree::setRootNode"_s);
585     ASSERT(isMainThread());
586     ASSERT(m_changeLogLock.isLocked());
587     ASSERT(!m_rootNode);
588     ASSERT(root);
589
590     m_rootNode = root;
591 }
592
593 void AXIsolatedTree::setFocusedNodeID(AXID axID)
594 {
595     AXTRACE("AXIsolatedTree::setFocusedNodeID"_s);
596     AXLOG(makeString("axID ", axID.loggingString()));
597     ASSERT(isMainThread());
598
599     AXPropertyMap propertyMap;
600     propertyMap.set(AXPropertyName::IsFocused, true);
601
602     Locker locker { m_changeLogLock };
603     m_pendingFocusedNodeID = axID;
604     m_pendingPropertyChanges.append({ axID, propertyMap });
605 }
606
607 void AXIsolatedTree::updateLoadingProgress(double newProgressValue)
608 {
609     AXTRACE("AXIsolatedTree::updateLoadingProgress"_s);
610     AXLOG(makeString("Updating loading progress to ", newProgressValue, " for treeID ", treeID()));
611     ASSERT(isMainThread());
612
613     m_loadingProgress = newProgressValue;
614 }
615
616 void AXIsolatedTree::removeNode(const AXCoreObject& axObject)
617 {
618     AXTRACE("AXIsolatedTree::removeNode"_s);
619     AXLOG(makeString("objectID ", axObject.objectID().loggingString()));
620     ASSERT(isMainThread());
621
622     m_unresolvedPendingAppends.remove(axObject.objectID());
623     removeSubtreeFromNodeMap(axObject.objectID(), axObject.parentObjectUnignored());
624     queueRemovals({ axObject.objectID() });
625 }
626
627 void AXIsolatedTree::removeSubtreeFromNodeMap(AXID objectID, AXCoreObject* axParent)
628 {
629     AXTRACE("AXIsolatedTree::removeSubtreeFromNodeMap"_s);
630     AXLOG(makeString("Removing subtree for objectID ", objectID.loggingString()));
631     ASSERT(isMainThread());
632
633     if (!m_nodeMap.contains(objectID)) {
634         AXLOG(makeString("Tried to remove AXID ", objectID.loggingString(), " that is no longer in m_nodeMap."));
635         return;
636     }
637
638     AXID axParentID = axParent ? axParent->objectID() : AXID();
639     if (axParentID != m_nodeMap.get(objectID).parentID) {
640         AXLOG(makeString("Tried to remove object ID ", objectID.loggingString(), " from a different parent ", axParentID.loggingString(), ", actual parent ", m_nodeMap.get(objectID).parentID.loggingString(), ", bailing out."));
641         return;
642     }
643
644     Vector<AXID> removals = { objectID };
645     while (removals.size()) {
646         AXID axID = removals.takeLast();
647         if (!axID.isValid() || m_unresolvedPendingAppends.contains(axID))
648             continue;
649
650         auto it = m_nodeMap.find(axID);
651         if (it != m_nodeMap.end()) {
652             removals.appendVector(it->value.childrenIDs);
653             m_nodeMap.remove(axID);
654         }
655     }
656
657     // Update the childrenIDs of the parent since one of its children has been removed.
658     if (axParent) {
659         auto ids = m_nodeMap.get(axParentID);
660         ids.childrenIDs = axParent->childrenIDs();
661         m_nodeMap.set(axParentID, WTFMove(ids));
662     }
663 }
664
665 std::optional<Vector<AXID>> AXIsolatedTree::relatedObjectIDsFor(const AXCoreObject& object, AXRelationType relationType)
666 {
667     ASSERT(!isMainThread());
668
669     if (m_relationsNeedUpdate) {
670         m_relations = Accessibility::retrieveValueFromMainThread<HashMap<AXID, AXRelations>>([this] () -> HashMap<AXID, AXRelations> {
671             if (auto* cache = axObjectCache())
672                 return cache->relations();
673             return { };
674         });
675         m_relationsNeedUpdate = false;
676     }
677
678     auto relationsIterator = m_relations.find(object.objectID());
679     if (relationsIterator == m_relations.end())
680         return std::nullopt;
681
682     auto targetsIterator = relationsIterator->value.find(static_cast<uint8_t>(relationType));
683     if (targetsIterator == relationsIterator->value.end())
684         return std::nullopt;
685     return targetsIterator->value;
686 }
687
688 void AXIsolatedTree::applyPendingChanges()
689 {
690     AXTRACE("AXIsolatedTree::applyPendingChanges"_s);
691
692     // In isolated tree mode 2, only apply pending changes on the AX thread.
693     ASSERT(m_usedOnAXThread ? !isMainThread() : isMainThread());
694     if (m_usedOnAXThread && isMainThread())
695         return;
696
697     Locker locker { m_changeLogLock };
698
699     if (m_pendingFocusedNodeID != m_focusedNodeID) {
700         AXLOG(makeString("focusedNodeID ", m_focusedNodeID.loggingString(), " pendingFocusedNodeID ", m_pendingFocusedNodeID.loggingString()));
701
702         if (m_focusedNodeID.isValid()) {
703             // Set the old focused object's IsFocused property to false.
704             AXPropertyMap propertyMap;
705             propertyMap.set(AXPropertyName::IsFocused, false);
706             m_pendingPropertyChanges.append({ m_focusedNodeID, propertyMap });
707         }
708         m_focusedNodeID = m_pendingFocusedNodeID;
709     }
710
711     while (m_pendingSubtreeRemovals.size()) {
712         auto axID = m_pendingSubtreeRemovals.takeLast();
713         AXLOG(makeString("removing subtree axID ", axID.loggingString()));
714         if (auto object = nodeForID(axID)) {
715             object->detach(AccessibilityDetachmentType::ElementDestroyed);
716             m_pendingSubtreeRemovals.appendVector(object->m_childrenIDs);
717             m_readerThreadNodeMap.remove(axID);
718         }
719     }
720
721     for (const auto& item : m_pendingAppends) {
722         AXID axID = item.isolatedObject->objectID();
723         AXLOG(makeString("appending axID ", axID.loggingString()));
724         if (!axID.isValid())
725             continue;
726
727         auto& wrapper = item.wrapper ? item.wrapper : item.isolatedObject->wrapper();
728         if (!wrapper)
729             continue;
730
731         if (auto existingObject = m_readerThreadNodeMap.get(axID)) {
732             if (existingObject != &item.isolatedObject.get()
733                 && existingObject->wrapper() == wrapper.get()) {
734                 // The new IsolatedObject is a replacement for an existing object
735                 // as the result of an update. Thus detach the existing object
736                 // and attach the wrapper to the new one.
737                 existingObject->detach(AccessibilityDetachmentType::ElementChanged);
738                 item.isolatedObject->attachPlatformWrapper(wrapper.get());
739             }
740             m_readerThreadNodeMap.remove(axID);
741         }
742
743         // If the new object hasn't been attached to a wrapper yet, or if it was detached from
744         // the wrapper when processing removals above, we must attach / re-attach it.
745         if (item.isolatedObject->isDetached())
746             item.isolatedObject->attachPlatformWrapper(wrapper.get());
747
748         auto addResult = m_readerThreadNodeMap.add(axID, item.isolatedObject.get());
749         // The newly added object must have a wrapper.
750         ASSERT_UNUSED(addResult, addResult.iterator->value->wrapper());
751         // The reference count of the just added IsolatedObject must be 2
752         // because it is referenced by m_readerThreadNodeMap and m_pendingAppends.
753         // When m_pendingAppends is cleared, the object will be held only by m_readerThreadNodeMap. The exception is the root node whose reference count is 3.
754         ASSERT_WITH_MESSAGE(
755             addResult.iterator->value->refCount() == 2 || (addResult.iterator->value.ptr() == m_rootNode.get() && m_rootNode->refCount() == 3),
756             "unexpected ref count after adding object to m_readerThreadNodeMap: %d", addResult.iterator->value->refCount()
757         );
758     }
759     m_pendingAppends.clear();
760
761     for (auto& update : m_pendingChildrenUpdates) {
762         AXLOG(makeString("updating children for axID ", update.first.loggingString()));
763         if (auto object = nodeForID(update.first))
764             object->m_childrenIDs = WTFMove(update.second);
765     }
766     m_pendingChildrenUpdates.clear();
767
768     for (auto& change : m_pendingPropertyChanges) {
769         if (auto object = nodeForID(change.axID)) {
770             for (auto& property : change.properties)
771                 object->setProperty(property.key, WTFMove(property.value));
772         }
773     }
774     m_pendingPropertyChanges.clear();
775 }
776
777 } // namespace WebCore
778
779 #endif // ENABLE(ACCESSIBILITY_ISOLATED_TREE)