The real problem is that the accessible tree contains only those objects which are visible on the screen at any instant, and ignores those which are above or below. This prevents Assistive Technology tools from accessing the full document. So it needs to be fixed on a priority basis.

This bug is a major hurdle in the way of assistive tools like Orca screen reader trying to access the whole document. How much easy or difficult is it to fix? May we get a tentative target date for fixing it?

See also: https://bugzilla.gnome.org/show_bug.cgi?id=652548

FLOWS_FROM and FLOWS_TO relationships, however, link together all paragraphs and table cells in the document, visible or not.

Today I rechecked my observation with Libre Office dev 3.5.0 beta2 and found
that the bug persists. I suggest that the bug be moved back to NEW status.

Is this Gnome 2? Remains this problem in Gnome 3?

The bug is real. I noticed it in version 3.3.0 and submitted it with a
supporting screenshot. I reconfirmed that the bug exists with version 3.5.0
beta2. It falls in the same category as bugs 35105, 35107, 35110, 35111, 35129
which you have reopened and changed to NEW.

Behavior remains, should have been returned to NEW status.

The corresponding Apache OpenOffice bug is also still open: https://issues.apache.org/ooo/show_bug.cgi?id=117542

This is still reproducible in master.

Version: 5.2.0.0.alpha0+
Build ID: 6c41727484a04ab89005ffb052937dae5d7dc223

Another way to reproduce it: create an empty document, add one paragraph and add a footnote. When you scroll to the bottom of the page, only the footnote will be exposed to the AT; when you scroll to the top, the paragraph is exposed to the AT and the footnote disappears.

(In reply to Jacobo Aragunde Pérez from comment #16)
> This is still reproducible in master.
> 
> Version: 5.2.0.0.alpha0+
> Build ID: 6c41727484a04ab89005ffb052937dae5d7dc223
> 
> Another way to reproduce it: create an empty document, add one paragraph and
> add a footnote. When you scroll to the bottom of the page, only the footnote
> will be exposed to the AT; when you scroll to the top, the paragraph is
> exposed to the AT and the footnote disappears.

hi.
i can reproduce the bug using the steps that you mentioned.
when i access content, i lose footnotes,
and when i find footnotes (using navigator) i lose usual content!
moreover, sayAll does not work for me in any version of libreoffice which i tested and i cant access the content of my books entirely.

(In reply to QA Administrators from comment #18)

This is still an issue, no change supporting structural navigation by page top to bottom with current release or on master. The 'view tree' does not include the entire document--even with the provided flows-from flows-to annotation.

Here are links to some related historical reading from the Gnome ATK/AT-SPI side on providing support for the Accessibility::Collection IDL (AtkDocument/AtkCollection) as a possible solution to our limited window into a complex document that disrupts screen reading.

https://bugzilla.gnome.org/show_bug.cgi?id=652548
https://bugzilla.gnome.org/show_bug.cgi?id=345750

(In reply to QA Administrators from comment #21)

This is still an issue, no change supporting structural navigation by page top to bottom with current release or on master. The 'view tree' does not include the entire document--even with the provided flows-from flows-to annotation.

I thought there was another bug or two that contained more discussion on this and possible ways forward, but I couldn't find it yet.  Anyway, here are some things to think about to get this moving:

# Current state of things

Currently, only on-screen objects are reported to the accessibility bus.  Objects get added when they enter the screen and are destroyed when they leave it (plus there are missing events about those, but those are merely bugs).

This was *potentially* done due to fear of performance issues for huge documents (citation needed), but AFAIK there is no real recollection of the real motivation here.  Whether presenting off-screen objects would cause performance issues definitely hasn't been measured in the last 15 to 20 years, if at all, so even if it was a concern back in the early 2000s, it might not be one anymore.
All this to say that AFAICT there is no proven compelling reason to implement it that way.

# Why is this an issue?

This actually causes several issues for accessibility consumers, e.g. screen readers and the like.

While one could argue that a sighted user cannot see off-screen content either (they have to scroll it on-screen), it's actually more problematic for a blind user relying on an assistive technology, in part because scrolling is harder for them.

## Inconsistent accessibility tree

This leads to a bizarre and inconsistent accessible tree, leading for example to bug#96492. However, one actually doesn't have to use the flows-to/from relations to get bizarre behavior: if you've got paragraphs off-screen above, they'll be trimmed from the tree, so the first *visible* paragraph will have index 0. Yet, if you scroll up, it'll gain previous siblings and change index, while the document content actually didn't change. That's not necessarily a deal breaker per se, but it's needlessly bizarre and can require careful handling in ATs.

## No structural navigation

As it is not possible to access some off-screen content (only paragraphs have flows-to/from relationships to one another), features like structural navigation cannot be implemented for LibreOffice, while they are currently working e.g. on web pages. For a brief description of structural navigation, you can look at https://help.gnome.org/orca/howto_structural_navigation.html (not sure how up-to-date this is, but the idea is there -- and it indirectly mentions this bug :)

This limits the interactions a screen reader user can rely on when using LO, making its use harder than necessary.

# Possible solutions

## Expose everything at once

The simplest solution is to expose everything at once and stop trimming off-screen branches.

This is conceptually the simplest thing to do, and it might also be the easiest to implement.  You get rid of the off-screen trimming and on-screen creation logic, and the accessibility tree only has to match the document content.  Here I assume the document content itself is not lazy-loaded; tell me if I'm wrong.

As mentioned above, the downside might be that it can create a large accessibility tree for very long and/or very complex documents.  Whether this would actually be problematic is, again, not entirely clear to me.

## Expose everything dynamically

A hybrid approach could be to never trim branches that are still valid (so accessible objects stay valid, even if scrolled off-screen), but to populate some things only when actually requested.

The advantage is that the whole tree wouldn't have to be created at once, *if* that's a performance or resources issue, but it would behave as if it *was* complete from a consumer POV.

The easiest version of this would be to create children only when they are actually queried: e.g. `Accessible.get_child_count()` would return the real number of children, but they would only actually be created when `Accessible.get_child_at_index()` gets called.  There are other things that could be done, but that would be a conceptually simple way of not creating objects before they are effectively used. Note that something to this effect is already happening for the flows-to/from relationships in paragraphs.
Also note that this is slightly over-simplified as some objects are needed regardless in order to send events (like e.g. focus), but the idea is still the same.

However, we need to go a bit further to have the full benefit of this for structural navigation, because e.g. finding all the titles in the document would require checking the whole tree (or at least everything up until the next title, if just going to the next one).  There's an API that ATs can use to improve on this: AtspiCollection. It allows performing queries rather than walking the whole tree, allowing us to offload the heavy work to the application.  We have a default implementation for free from ATK, but it simply walks the accessibility tree, so it has to fetch each node, defeating most of the benefits of lazy object creation on our end (it has other benefits, like transmitting a whole lot less data on the bus). If this was implemented in LO itself, it could potentially derive the matches from the document itself and only create the accessible objects that matched.

If both were implemented, it would probably be sufficient to keep resource usage low by not creating unused accessible objects, yet still behaving as if they were there.
This, however, is a bit harder to do right because all object properties must be correct from the get-go.  For example, the index position in the parent would have to be correct regardless of whether the siblings have actually been created or not, and because all this requires detecting which objects need to be created and when (yet, a properly designed cache *should* be all that is needed).

# Other things to consider

It might be interesting to check what others do on the matter, like web browsers.  Naively, I would have assumed they would implement the hybrid approach above for performance reasons on uncontrollably large web pages, but more recent reading about the inspiration behind an alternative accessibility protocol draft suggested they would rather do the exact opposite and always have the whole tree ready.  I didn't dive into the actual implementations, however, and others (including @joanmarie) might know better -- including this paragraph being entirely incorrect.

I believe some people suggested adding "page" containers wrapping the nodes for each page to solve certain issues.  I'm not sure what that would solve, though, and I unfortunately couldn't find references to this just now. If anybody has more insights on this, that would be welcome.

# Conclusion

So, in your opinion, what would be the most reasonable approach to take here?
And @joanmarie, would you have insight on the bare minimum you'd need to have things working nicely in Orca?

(In reply to cwendling from comment #24)
> I thought there was another bug or two that contained more discussion on
> this and possible ways forward, but I couldn't find it yet.

tdf#137955 seems very relevant which is specifically about browse mode/structural navigation and has some further discussion/thoughts. (Added a link in "See Also" now as well.)

> Anyway, here
> are some things to think about to get this moving:

Thanks a lot! Just some additional comments/questions on single aspects:

> However, we need to go a bit further to have the full benefit of this for
> structural navigation, because e.g. finding all the titles in the document
> would require checking the whole tree (or at least everything up until the
> next title, if just going to the next one).  There's an API that ATs can use
> to improve on this: AtspiCollection. It allows performing queries rather
> than walking the whole tree, allowing us to offload the heavy work to the
> application. 

I agree that AtspiCollection seems the best way forward and the Orca side for it is already implemented. (Structural navigation between elements visible on screen already works, but the usefulness of that is limited.)

> We have a default implementation for free from ATK, but it
> simply walks the accessibility tree, so it has to fetch each node, defeating
> most of the benefits of lazy object creation on our end (it has other
> benefits, like transmitting a whole lot less data on the bus). If this was
> implemented in LO itself, it could potentially derive the matches from the
> document itself and only create the accessible objects that matched.

Would current ATK API even provide any simple means for an application to override/optimize the default AtspiCollection implementation?
It's been a bit that I looked into it, but I thought it was effectively an implementation detail inside ATK, with no API to simply override it.
( https://docs.gtk.org/atk/#interfaces at least also doesn't list it.)

It being an implementation detail would at least be true for Qt. GTK 4 doesn't have any AtspiCollection implementation yet (see https://gitlab.gnome.org/GNOME/gtk/-/issues/5973 ), but from earlier discussions about extending GTK 4 a11y API for other purposes, I doubt having/getting public API for something like the AtspiCollection interface is likely.

> I believe some people suggested adding "page" containers wrapping the nodes
> for each page to solve certain issues.  I'm not sure what that would solve,
> though, and I unfortunately couldn't find references to this just now. If
> anybody has more insights on this, that would be welcome.

That (and more) should be somewhere in the dev list thread discussion referenced in tdf#137955 comment 11.

> So, in your opinion, what would be the most reasonable approach to take here?

From a conceptual perspective, having everything in the tree sounds the "nicest" and simplest to me *if* it wouldn't cause performance issues.

But I remember Michael M. had strong concerns/objections against that idea and suggested considering a completely different approach like designing some API specifically for the exact purpose/use case and avoid exposing the whole tree. (That should also be somewhere in the above thread, but was also mentioned on other occasions.)

[CC'ing Michael, in case he wants to comment as well.]

> And @joanmarie, would you have insight on the bare minimum you'd need to
> have things working nicely in Orca?

I can't speak for joanie, but from what I remember from an earlier discussion with her, it should in principle "just work" in Orca once LO exposes the whole document tree via AtSpiCollection, given that structural navigation logic has in the meantime been made globally available in Orca (after being web-only previously).

Regarding considerations of including offscreen children and/or pages in the a11y tree (as mentioned in comment 24 and earlier discussions): I had very quickly experimented with that in the past.
 
Based on some old local branch, I've now submitted demo change https://gerrit.libreoffice.org/c/core/+/204318 which shows that there are (at least) 2 quite prominent places where it's decided whether or not to do so, and it allows to switch either one on for testing by setting an environment variable.
(See commit message for more details. Only meant for experimenting, definitely not meant to be merged in that state.)

Implementing the search with AtspiCollection seems the obvious way to do this; iterating every database row remotely is going to be far worse than sending a server-side query and a much shorter result IMNSO ;-) Pleased to see AtpiCollection exists. Presumably just implementing the interface on the right AtkObject does the trick.

(In reply to Michael Weghorn from comment #25)
> Would current ATK API even provide any simple means for an application to
> override/optimize the default AtspiCollection implementation?
> It's been a bit that I looked into it, but I thought it was effectively an
> implementation detail inside ATK, with no API to simply override it.
> ( https://docs.gtk.org/atk/#interfaces at least also doesn't list it.)

It still is AFAICT, but I would imagine that it could be made an interface proper merely with a default implementation.  I imagine it was never done because most apps won't want or need to implement it manually for things to work.
CCing Mike Gorse on this.

> It being an implementation detail would at least be true for Qt. GTK 4
> doesn't have any AtspiCollection implementation yet (see
> https://gitlab.gnome.org/GNOME/gtk/-/issues/5973 ), but from earlier
> discussions about extending GTK 4 a11y API for other purposes, I doubt
> having/getting public API for something like the AtspiCollection interface
> is likely.

Isn't it possible to hook into the raw AT-SPI2 protocol in GTK4?  You'll probably be more knowledgeable than I am here, but if that's indeed possible it'd be a bit of a hassle, but still very much doable, it's "just" a bit of DBus handling.

> > So, in your opinion, what would be the most reasonable approach to take here?
> 
> From a conceptual perspective, having everything in the tree sounds the
> "nicest" and simplest to me *if* it wouldn't cause performance issues.

I agree, but if performance is a concern the hybrid approach could help: create object dynamically on-demand -- but don't destroy them.  It's still gonna be more complex than a simple solution that creates everything, but if done right presumably a lot of code could just pretend everything exists and using the right getter would transparently create the actual object if it's not already there.

This would probably solve a good part of the performance concerns, as the common case would only create a few actually used objects rather than the whole, potentially unused, tree.  And I doubt that the overhead of keeping a11y objects around if they have been actually accessed is gonna be a real concern.  IMO that is.


(In reply to Michael Meeks from comment #27)
> Implementing the search with AtspiCollection seems the obvious way to do
> this; iterating every database row remotely is going to be far worse than
> sending a server-side query and a much shorter result IMNSO ;-)

Definitely, and optimizing IPC is basically the reason why AtspiCollection exist :)

One issue however might be that AFAIK there is no direct equivalent on Windows (maybe with UIA there would be?), so AtspiCollection is only gonna improve the AT-SPI consumers.

Note that it's totally possible to combine implementing AtspiCollection *and* presenting the whole (possibly created on-demand) tree.  AtspiCollection consumers (like Orca) would get the optimization benefit, while other use case could rely on more "traditional" means.

One challenge in keeping the current "what's offscreen doesn't exist" approach is, among others, lifetime of an object returned by an AtspiCollection call. I'm not entirely sure how this is managed for the flows-to/from relations for paragraphs, but if we report an object through AtspiCollection it has to live long enough for the consumer to make use of it, yet it might very well be off-screen -- and we need to allow scrolling the view at the *very* least once before it dies to be able to reach it.  Ideally, it would stay alive longer, but here again I'll let @joanie tell what she needs (e.g. is Orca caching the list of titles, or querying it again each time?  etc.).

(In reply to cwendling from comment #28)
> Isn't it possible to hook into the raw AT-SPI2 protocol in GTK4?  You'll
> probably be more knowledgeable than I am here, but if that's indeed possible
> it'd be a bit of a hassle, but still very much doable, it's "just" a bit of
> DBus handling.

Yes, as far as I understand, that is what WebKitGTK does: It implements the low-level AT-SPI2 protocol itself, instead of using the GtkAccessible API for the actual web content, using the GtkAtSpiSocket API. (Related GTK commit: https://gitlab.gnome.org/GNOME/gtk/-/commit/88b3e8552ab94b9eb5ae3d15d25fb2d73bd81d8e )
While GtkAccessible API is supposed to be cross-platform in GTK 4, implementing AT-SPI2 directly would be incompatible with that idea, and it won't work with GTK's alternative AccessKit backend.
Right now, I'm not too enthusiastic about the idea of implementing low-level AT-SPI2 in LO itself. Abstracting platform implementation details like the a11y protocol is in my opinion one of the main tasks of a (cross-platform) UI toolkit, and I think LO has rather been doing too much of the job of a UI toolkit itself so far instead of too little (with all the implications that has on maintainability, etc.).
But then, if GTK 4 doesn't provide required a11y APIs, I wouldn't exclude as a potential last means if we ever plan to get the gtk4 plugin out of an experimental status. (But that depends on other aspects as well, including either implementing a11y for widgets deprected in (if I remember correctly) GTK 4.10 upstream or porting away from them, which is somewhat challenging while keeping gtk3 support.)

In any case, I think we would need a solution that works at least with Qt as well (at least conceptually/with a clear way forward to make it work there as well; initially implementing it only for one vcl plugin then would be fine). Usually, proving that something conceptually exists on multiple platforms is helpful in case of suggesting to add new public Qt a11y API that can then be used to implement the corresponding platform a11y APIs on the different platforms.

Since we have the same request/problem on Windows, too (see tdf#137955 and https://github.com/nvaccess/nvda/issues/8148 ), I think we should ideally come up with something from the start that can (at least conceptually) work there as well.

> One issue however might be that AFAIK there is no direct equivalent on
> Windows (maybe with UIA there would be?), so AtspiCollection is only gonna
> improve the AT-SPI consumers.

For UIA, maybe https://learn.microsoft.com/en-us/windows/win32/winauto/uiauto-obtainingelements could be related, in particular the mentioned IUIAutomationElement::FindFirst ( https://learn.microsoft.com/en-us/windows/win32/api/uiautomationclient/nf-uiautomationclient-iuiautomationelement-findfirst ) and IUIAutomationElement::FindAll ( https://learn.microsoft.com/en-us/windows/win32/api/uiautomationclient/nf-uiautomationclient-iuiautomationelement-findall )?

> Note that it's totally possible to combine implementing AtspiCollection
> *and* presenting the whole (possibly created on-demand) tree. 
> AtspiCollection consumers (like Orca) would get the optimization benefit,
> while other use case could rely on more "traditional" means.
> 
> One challenge in keeping the current "what's offscreen doesn't exist"
> approach is, among others, lifetime of an object returned by an
> AtspiCollection call. I'm not entirely sure how this is managed for the
> flows-to/from relations for paragraphs, but if we report an object through
> AtspiCollection it has to live long enough for the consumer to make use of
> it, yet it might very well be off-screen -- and we need to allow scrolling
> the view at the *very* least once before it dies to be able to reach it. 
> Ideally, it would stay alive longer, but here again I'll let @joanie tell
> what she needs (e.g. is Orca caching the list of titles, or querying it
> again each time?  etc.).

I agree. Conceptually, my understanding would also be that AtSpiCollection is "just" an "optimized" way of accessing objects that are part of the a11y tree. In that case, making parts of the document accessible via AtSpiCollection but not including them in the a11y tree would seem inconsistent to me.

(In reply to Michael Weghorn from comment #29)
> […]
> Right now, I'm not too enthusiastic about the idea of implementing low-level
> AT-SPI2 in LO itself. Abstracting platform implementation details like the
> a11y protocol is in my opinion one of the main tasks of a (cross-platform)
> UI toolkit, and I think LO has rather been doing too much of the job of a UI
> toolkit itself so far instead of too little (with all the implications that
> has on maintainability, etc.).
> But then, if GTK 4 doesn't provide required a11y APIs, I wouldn't exclude as
> a potential last means if we ever plan to get the gtk4 plugin out of an
> experimental status. […]
> 
> In any case, I think we would need a solution that works at least with Qt as
> well (at least conceptually/with a clear way forward to make it work there
> as well; initially implementing it only for one vcl plugin then would be
> fine). Usually, proving that something conceptually exists on multiple
> platforms is helpful in case of suggesting to add new public Qt a11y API
> that can then be used to implement the corresponding platform a11y APIs on
> the different platforms.
> 
> Since we have the same request/problem on Windows, too (see tdf#137955 and
> https://github.com/nvaccess/nvda/issues/8148 ), I think we should ideally
> come up with something from the start that can (at least conceptually) work
> there as well.

I understand not wanting to add too much platform-specific code, but we'll at least have to have an internal a11y API for this, won't we?  Then indeed, the per-VCL implementations would need to be written for this to have an actual effect.
This internal API could be stripped down to the bare minimum so to accommodate the restrictions of the different VCLs because of the respective platform APIs (e.g. we probably don't have to have the entire AtspiCollection, but only a subset of it -- @joanie even suggested some of the AtspiCollection API could do with a redesign, so possibly not sticking 100% to the actual state of things would be fine).

And thus, while I get that you'd rather not see lower level things creep in even more, having the necessary bits in the VCL implementations seem not so far fetched to me, e.g. AFAIK the GTK VCL is currently UNIX-specific and not meant to be used (or even work?) on Windows, is it?

My point is that if it can be a reasonably abstracted part of the code so that the internal API the core use is not tied to a platform, it would still make sense to get the benefits from it where it can actually work and make a difference.  And so that this platform-specific code is worth it, especially if we can hope to replace it with a toolkit API at some point.

Regarding Qt, I don't know a lot of it's a11y internals, so I have to ask: do they usually copy the IA2/UIA/AT-SPI/NSAccessibility APIs, or do they design their own to match them all?  If they welcome additions and have more or less custom APIs, I would think we could come up with something that could (bene)fit both Qt and LO.  It might however take some time I imagine.

> > One issue however might be that AFAIK there is no direct equivalent on
> > Windows (maybe with UIA there would be?), so AtspiCollection is only gonna
> > improve the AT-SPI consumers.
> 
> For UIA, maybe
> https://learn.microsoft.com/en-us/windows/win32/winauto/uiauto-
> obtainingelements could be related, in particular the mentioned
> IUIAutomationElement::FindFirst (
> https://learn.microsoft.com/en-us/windows/win32/api/uiautomationclient/nf-
> uiautomationclient-iuiautomationelement-findfirst ) and
> IUIAutomationElement::FindAll (
> https://learn.microsoft.com/en-us/windows/win32/api/uiautomationclient/nf-
> uiautomationclient-iuiautomationelement-findall )?

Thanks a lot for that, I'm no UIA expert at all, but it looks relevant indeed.  Anybody reading with UIA knowledge to give more info?

> > Note that it's totally possible to combine implementing AtspiCollection
> > *and* presenting the whole (possibly created on-demand) tree. 
> > AtspiCollection consumers (like Orca) would get the optimization benefit,
> > while other use case could rely on more "traditional" means.
> > 
> > One challenge in keeping the current "what's offscreen doesn't exist"
> > approach is, among others, lifetime of an object returned by an
> > AtspiCollection call. I'm not entirely sure how this is managed for the
> > flows-to/from relations for paragraphs, but if we report an object through
> > AtspiCollection it has to live long enough for the consumer to make use of
> > it, yet it might very well be off-screen -- and we need to allow scrolling
> > the view at the *very* least once before it dies to be able to reach it. 
> > Ideally, it would stay alive longer, but here again I'll let @joanie tell
> > what she needs (e.g. is Orca caching the list of titles, or querying it
> > again each time?  etc.).
> 
> I agree. Conceptually, my understanding would also be that AtSpiCollection
> is "just" an "optimized" way of accessing objects that are part of the a11y
> tree. In that case, making parts of the document accessible via
> AtSpiCollection but not including them in the a11y tree would seem
> inconsistent to me.

While I do agree, I would think Michael M. would argue that consistency isn't needed if it isn't required for the feature to work :)

This said, I still believe in the create-on-request model (or just create-everything-at-once one), be it with or without the Collection optimization, because it allows for that optimization to be just that -- an optimization -- and not a requirement for all platforms in order to provide good a11y support.