tdf#150064 Keep a11y child order intact

commit 8f9fd6806ccfbf381a383efe5d143ead86ee49de
Date:   Wed Jun 29 19:47:20 2022 +0200

tdf#137544 reduce cost of ChildrenManagerImpl::Update

had added sorting based on memory addresses of the
corresponding shapes, but the order of the
children in `maVisibleChildren` is expected
to reflect the order of the accessible children
(i.e. based on the child index of the corresponding
shapes' a11y objects), since items are accessed by
index (s. e.g. `ChildrenManagerImpl::GetChild`).

Since the `ChildDescriptor`'s `mxAccessibleShape`
reference can be empty, its child index also cannot
be used for sorting instead.

To prevent the a11y tree from becoming unstable/random,
don't reorder/sort `maVisibleChildren`, but
allocate a helper vector holding pointers to the items
in the real vector, and iterate over that one instead.

This also moves identification of the elements
that are only in the old, but no longer the
new vector to `ChildrenManagerImpl::MergeAccessibilityInformation`,
where the sorted vector is availabe, and returns
a vector of obsolete children that is then
passed to
`ChildrenManagerImpl::RemoveNonVisibleChildren`,
instead of doing the comparison of the old/new
vector there.

Change-Id: Ie449f76f1b98ffe8e85ca28e938b11d726086721
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/137622
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.grandin@collabora.co.uk>
Reviewed-by: Colomban Wendling <cwendling@hypra.fr>
Reviewed-by: Michael Weghorn <m.weghorn@posteo.de>

2 files changed, 80 insertions, 58 deletions

diff --git a/svx/source/accessibility/ChildrenManagerImpl.cxx b/svx/source/accessibility/ChildrenManagerImpl.cxx
index 5ed1bbd4a68e..988bb4532c0c 100644
--- a/svx/source/accessibility/ChildrenManagerImpl.cxx
+++ b/svx/source/accessibility/ChildrenManagerImpl.cxx
@@ -205,8 +205,9 @@ void ChildrenManagerImpl::Update (bool bCreateNewObjectsOnDemand)
         maVisibleChildren.swap (aChildList);
 
         // 3. Merge the information that is already known about the visible
-        // shapes from the previous list into the new list.
-        MergeAccessibilityInformation (aChildList);
+        // shapes from the previous list into the new list and identify
+        // old children that are now unused
+        std::vector<ChildDescriptor*> aUnusedChildList = MergeAccessibilityInformation (aChildList);
 
         adjustIndexInParentOfShapes(maVisibleChildren);
 
@@ -231,8 +232,9 @@ void ChildrenManagerImpl::Update (bool bCreateNewObjectsOnDemand)
         // to be fired, and so the operations will take place on
         // the list we are trying to replace
 
-        RemoveNonVisibleChildren (maVisibleChildren, aChildList);
+        RemoveNonVisibleChildren (aUnusedChildList);
 
+        aUnusedChildList.clear();
         aChildList.clear();
 
         maVisibleArea = aVisibleArea;
@@ -321,80 +323,97 @@ void ChildrenManagerImpl::CreateListOfVisibleShapes (
 
 namespace
 {
-struct ChildDescriptorLess
+
+bool childDescriptorLess(const ChildDescriptor& lhs, const ChildDescriptor& rhs)
 {
-    bool operator()(const ChildDescriptor& lhs, const ChildDescriptor& rhs) const
-    {
-        auto pLhsShape = lhs.mxShape.get();
-        auto pRhsShape = rhs.mxShape.get();
-        if (pLhsShape || pRhsShape)
-            return pLhsShape < pRhsShape;
-        return lhs.mxAccessibleShape.get() < rhs.mxAccessibleShape.get();
-    }
-};
+
+    auto pLhsShape = lhs.mxShape.get();
+    auto pRhsShape = rhs.mxShape.get();
+    if (pLhsShape || pRhsShape)
+        return pLhsShape < pRhsShape;
+    return lhs.mxAccessibleShape.get() < rhs.mxAccessibleShape.get();
+}
+
+bool childDescriptorPtrLess(const ChildDescriptor* lhs, const ChildDescriptor* rhs)
+{
+    return childDescriptorLess(*lhs, *rhs);
+}
+
 }
     
 void ChildrenManagerImpl::RemoveNonVisibleChildren (
-    const ChildDescriptorListType& rNewChildList,
-    ChildDescriptorListType& rOldChildList)
+    const std::vector<ChildDescriptor*>& rNonVisibleChildren)
 {
-    // Iterate over list of formerly visible children and remove those that
-    // are not visible anymore, i.e. member of the new list of visible
-    // children.
-
-    // the lists have already been sorted in MergeAccessibilityInformation
-    auto newIt = rNewChildList.begin();
-    auto newEnd = rNewChildList.end();
-
-    for (auto& rChild : rOldChildList)
+    for (ChildDescriptor* pChild : rNonVisibleChildren)
     {
-        while (newIt != newEnd && ChildDescriptorLess()(*newIt, rChild))
-            newIt++;
-        if (newIt == newEnd || !(*newIt == rChild) )
+        // The child is disposed when there is a UNO shape from which
+        // the accessible shape can be created when the shape becomes
+        // visible again.  When there is no such UNO shape then simply
+        // reset the descriptor but keep the accessibility object.
+        if (pChild->mxShape.is())
         {
-            // The child is disposed when there is a UNO shape from which
-            // the accessible shape can be created when the shape becomes
-            // visible again.  When there is no such UNO shape then simply
-            // reset the descriptor but keep the accessibility object.
-            if (rChild.mxShape.is())
-            {
-                UnregisterAsDisposeListener (rChild.mxShape);
-                rChild.disposeAccessibleObject (mrContext);
-            }
-            else
-            {
-                AccessibleShape* pAccessibleShape = rChild.GetAccessibleShape();
-                pAccessibleShape->ResetState (AccessibleStateType::VISIBLE);
-                rChild.mxAccessibleShape = nullptr;
-            }
+            UnregisterAsDisposeListener (pChild->mxShape);
+            pChild->disposeAccessibleObject (mrContext);
+        }
+        else
+        {
+            AccessibleShape* pAccessibleShape = pChild->GetAccessibleShape();
+            pAccessibleShape->ResetState (AccessibleStateType::VISIBLE);
+            pChild->mxAccessibleShape = nullptr;
         }
     }
 }
 
-void ChildrenManagerImpl::MergeAccessibilityInformation (
+std::vector<ChildDescriptor*> ChildrenManagerImpl::MergeAccessibilityInformation (
     ChildDescriptorListType& raOldChildList)
+
 {
-    // sort the lists by mxShape, and then walk them in parallel, which avoids an O(n^2) loop
-    std::sort(maVisibleChildren.begin(), maVisibleChildren.end(), ChildDescriptorLess());
-    std::sort(raOldChildList.begin(), raOldChildList.end(), ChildDescriptorLess());
-    ChildDescriptorListType::const_iterator aOldChildDescriptor = raOldChildList.begin();
-    ChildDescriptorListType::const_iterator aEndVisibleChildren = raOldChildList.end();
+    // create a working copy of the vector of current children with pointers to elements,
+    // sort the old list and copy by mxShape, and then walk old/current lists in parallel,
+    // which avoids an O(n^2) loop
+    // (order of maVisibleChildren must remain unchanged to not randomly change a11y tree)
+    std::vector<ChildDescriptor*> aSortedVisibleChildren(maVisibleChildren.size());
+    std::transform(maVisibleChildren.begin(), maVisibleChildren.end(),
+                   aSortedVisibleChildren.begin(), [](auto& e) {return &e;});
+    std::sort(aSortedVisibleChildren.begin(), aSortedVisibleChildren.end(), childDescriptorPtrLess);
+
+    // old list can be reordered without problems
+    std::sort(raOldChildList.begin(), raOldChildList.end(), childDescriptorLess);
 
-    for (auto& rChild : maVisibleChildren)
+    ChildDescriptorListType::const_iterator aOldChildDescriptor = raOldChildList.begin();
+    ChildDescriptorListType::const_iterator aEndOldChildren = raOldChildList.end();
+    for (ChildDescriptor* pChild : aSortedVisibleChildren)
     {
-        while (aOldChildDescriptor != aEndVisibleChildren && ChildDescriptorLess()(*aOldChildDescriptor, rChild))
+        while (aOldChildDescriptor != aEndOldChildren && childDescriptorLess(*aOldChildDescriptor, *pChild))
+        {
             aOldChildDescriptor++;
+        }
 
         // Copy accessible shape if that exists in the old descriptor.
-        if (aOldChildDescriptor != aEndVisibleChildren && *aOldChildDescriptor == rChild &&
+        if (aOldChildDescriptor != aEndOldChildren && *aOldChildDescriptor == *pChild &&
             aOldChildDescriptor->mxAccessibleShape.is())
         {
-            rChild.mxAccessibleShape = aOldChildDescriptor->mxAccessibleShape;
-            rChild.mbCreateEventPending = false;
+            pChild->mxAccessibleShape = aOldChildDescriptor->mxAccessibleShape;
+            pChild->mbCreateEventPending = false;
         }
         else
-            RegisterAsDisposeListener (rChild.mxShape);
+            RegisterAsDisposeListener (pChild->mxShape);
+    }
+
+    // collect list of children that are in the old, but not the new vector
+    std::vector<ChildDescriptor*> aObsoleteChildren;
+
+    auto newIt = aSortedVisibleChildren.begin();
+    auto newEnd = aSortedVisibleChildren.end();
+    for (ChildDescriptor& rOldChild : raOldChildList)
+    {
+        while (newIt != newEnd && childDescriptorLess(**newIt, rOldChild))
+            newIt++;
+        if (newIt == newEnd || !(**newIt == rOldChild) )
+            aObsoleteChildren.push_back(&rOldChild);
     }
+
+    return aObsoleteChildren;
 }
 
 void ChildrenManagerImpl::SendVisibleAreaEvents (
diff --git a/svx/source/accessibility/ChildrenManagerImpl.hxx b/svx/source/accessibility/ChildrenManagerImpl.hxx
index f2762bfd83f2..6b59e22551c3 100644
--- a/svx/source/accessibility/ChildrenManagerImpl.hxx
+++ b/svx/source/accessibility/ChildrenManagerImpl.hxx
@@ -349,16 +349,19 @@ private:
             is compared.
     */
     void RemoveNonVisibleChildren (
-        const ChildDescriptorListType& raNewChildList,
-        ChildDescriptorListType& raOldChildList);
+        const std::vector<ChildDescriptor*>& rNonVisibleChildren);
 
     /** Merge the information that is already known about the visible shapes
-        from the old list into the current list.
+        from the old list into the current list, and return a list of
+        children that are in the old list, but not the current one.
         @param raChildList
             Information is merged to the current list of visible children
             from this list. The old list can get reordered.
+        @return
+            Vector of children that are in the old list, but not the current
+            one.
     */
-    void MergeAccessibilityInformation (ChildDescriptorListType& raChildList);
+    std::vector<ChildDescriptor*> MergeAccessibilityInformation (ChildDescriptorListType& raChildList);
 
     /** If the visible area has changed then send events that signal a
         change of their bounding boxes for all shapes that are members of