Created attachment 181334 [details] CppUnit test for default Impress document a11y layout In at least the default document created by Impress (one page with title + subtitle), the accessible tree layout is not entirely predictable, and its order changes from a run to the next. The (more or less) expected tree looks like this: - document_presentation - shape (page) - shape (title) - paragraph - shape (subtitle) - paragraph It is what I get about 80% of the times, but the other 20% the "title" and "subtitle" nodes are swapped. The internal representation (SdrObjects) is always in the right order though. Note that this happens both with the "new" document (private:factory/simpress) and a saved version of it. Impact on end users is not yet known as it'd depend on how often and how widespread the issue is in "real" scenarii, but it's awkward, unexpected and makes it terribly hard to write a test for Impress's layout. It also makes me worry a little about trustworthiness of that a11y tree. As said, I am not sure if all documents are affected and it's a global order issue, or if there's a specific at play, but it's very reproducible in a test scenario (see attached test case). I've actually discovered this while writing test infrastructure for a11y and trying to exercise it a bit against the different components; but I checked in regular running situation inspecting the a11y tree from outside LO and it is reproducible as well -- so it's not a test glitch.
Created attachment 181335 [details] Sample presentation reproducing the issue A stripped-down version of the saved default presentation reproducing the issue (can be loaded by the test instead of private:factory/simpress).
I just tested a bit more, and this randomness seems to apply to everything. You can even see it happen in real time when switching back and forth between pages in a multi-page presentation, where the order of the elements will seldom be the same each time. Tested with accerciser (https://wiki.gnome.org/Apps/Accerciser) on Linux.
Confirmed, it's quite well reproducible when e.g. saving attachment 181334 [details] as `sd/qa/unit/sdlayouta11y.cxx` and doing a quick hack to run that along with e.g. CppunitTest_sd_png_export_tests.mk: diff --git a/sd/CppunitTest_sd_png_export_tests.mk b/sd/CppunitTest_sd_png_export_tests.mk index 015557873961..73bce5d85660 100644 --- a/sd/CppunitTest_sd_png_export_tests.mk +++ b/sd/CppunitTest_sd_png_export_tests.mk @@ -20,6 +20,7 @@ $(eval $(call gb_CppunitTest_use_common_precompiled_header,sd_png_export_tests)) $(eval $(call gb_CppunitTest_add_exception_objects,sd_png_export_tests, \ sd/qa/unit/PNGExportTests \ + sd/qa/unit/sdlayouta11y \ )) Then, with that in place, run the test in a loop until it fails: while make CppunitTest_sd_png_export_tests; do echo OK; done or, recording the runs with rr so it can be replayed for debugging: while make CppunitTest_sd_png_export_tests RR=1; do echo OK; done From a first analysis, it looks like the (or at least one) problem is in ChildrenManagerImpl::MergeAccessibilityInformation (svx/source/accessibility/ChildrenManagerImpl.cxx), where the order of children can change. Might be a regression from commit 8f9fd6806ccfbf381a383efe5d143ead86ee49de Date: Wed Jun 29 19:47:20 2022 +0200 tdf#137544 reduce cost of ChildrenManagerImpl::Update there are 2 O(n^2) algorithms here, reduce them to O(n log n) by pre-sorting Change-Id: Ib3912155cda62cac95b5037528e23ef3c686a7e8 Reviewed-on: https://gerrit.libreoffice.org/c/core/+/136655 Tested-by: Jenkins I'll look into it a little closer myself first to see whether it's actually a regression and whether any good ideas come to mind rather quickly while doing so. Tested with LO master as of commit 28dc1e713cfc5b5ea38e15f032aba72d05e40b33.
(In reply to Michael Weghorn from comment #3) > Might be a regression from > > commit 8f9fd6806ccfbf381a383efe5d143ead86ee49de > Date: Wed Jun 29 19:47:20 2022 +0200 > > tdf#137544 reduce cost of ChildrenManagerImpl::Update > > there are 2 O(n^2) algorithms here, reduce them to O(n log n) by > pre-sorting > > Change-Id: Ib3912155cda62cac95b5037528e23ef3c686a7e8 > Reviewed-on: https://gerrit.libreoffice.org/c/core/+/136655 > Tested-by: Jenkins > > I'll look into it a little closer myself first to see whether it's actually > a regression and whether any good ideas come to mind rather quickly while > doing so. It's actually a regression from that commit, the test works fine for me with a local revert. The only idea I can currently come up with to not revert back to the previous O(n^2) behavior would be to allocate another helper vector (with pointers to the items in the "real vector") and sort only that one, while leaving the original vector of children unchanged. If that makes any sense, I could come up with a change for that, but I don't know whether that would be a performance gain as compared to the O(n^2) looping in the end, or the extra vector allocation outweighs that. (I don't have much experience with performance optimization and the test file from tdf#137544 takes so long to open with my debug build that it discourages from doing more extensive experiments...) Adding CC: to Noel Grandin: Any ideas/suggestions?
Probably the easiest is to make a copy of the maVisibleChildren vector and sort the temporary copy, then pass that sorted vector to RemoveNonVisibleChildren Otherwise just revert my commit, I'm not attached to it.
(In reply to Noel Grandin from comment #5) > Probably the easiest is to make a copy of the maVisibleChildren vector and > sort the temporary copy, then pass that sorted vector to > RemoveNonVisibleChildren Thanks! I have submitted 2 changes to do roughly that: https://gerrit.libreoffice.org/c/core/+/137621 https://gerrit.libreoffice.org/c/core/+/137622
Michael Weghorn committed a patch related to this issue. It has been pushed to "master": https://git.libreoffice.org/core/commit/7ccaca8dcaab5868987b78b6b2436872ac7f1129 tdf#150064 a11y: Swap old/new list before merging information It will be available in 7.5.0. The patch should be included in the daily builds available at https://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More information about daily builds can be found at: https://wiki.documentfoundation.org/Testing_Daily_Builds Affected users are encouraged to test the fix and report feedback.
Michael Weghorn committed a patch related to this issue. It has been pushed to "master": https://git.libreoffice.org/core/commit/c793e850bce9d67dd43da30e1535b1d991e3ee9c tdf#150064 Keep a11y child order intact It will be available in 7.5.0. The patch should be included in the daily builds available at https://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More information about daily builds can be found at: https://wiki.documentfoundation.org/Testing_Daily_Builds Affected users are encouraged to test the fix and report feedback.
Colomban Wendling committed a patch related to this issue. It has been pushed to "master": https://git.libreoffice.org/core/commit/6185a27db46bf5cba404e669eaf3a1c78f4a8607 tdf#150064 Add tests for a11y tree order It will be available in 7.5.0. The patch should be included in the daily builds available at https://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More information about daily builds can be found at: https://wiki.documentfoundation.org/Testing_Daily_Builds Affected users are encouraged to test the fix and report feedback.