New virtualBuffers now in NVDA, and fun with lines

Since my last blog post on the web access grant a lot has happened in regards to this stopic. A few features talked about in previous postings for the storage code have been implemented, but most importantly, I have taken that next step of actually completely integrating the storage code in to NVDA and now giving myself and other NVDA developers the choice of using the new code to interact with Gecko 1.9 documents (such as Ff3 and ThunderBird?3).

The last post I talked about the fact that Jamie and I had talked about allowing arbitrary properties on nodes in the buffer, rather than just locking it down to just role, value, states, keyboardShortcut and contains. Well, this has been achieved, so now functions such as addTagNodeToBuffer and findBufferFieldIDByProperties take an array of attributes (name and value pares), or sometimes name and multiValue pares, if using findBufferFieldIDByProperties to search on multiple values of a given property. There are still particular properties of a node which have their own specific member variables (such as ID, and some other new ones that are generic to nodes or tagNodes)

The coding that has probably taken up most of my time through out the last month or so is the code that manages lines in the storage module. A virtualBuffer's job is to render a representation of a document in a flat layout, meaning that every character in the buffer has an index, from 0 to the length of the buffer - every character has an ordered place. But, it also has to have an idea of what lines are, as in it must allow the user (through the AT) to be able to arrow up and down through the buffer by lines of information that are not too long, but also not too short as to make the user have to press keys more than they need to. Working out exactly how to implement this was hard, what it uses now is my third go at implementing it.

NVDA itself has pretty good text management through its TextInfo? classes, so all the storage module had to do to communicate line placement was to allow the querying of line offsets using a particular offset as reference, with the getBufferLineOffsets function.

My first attempt was to simply scan back from the offset, looking for a line feed character, and then do the same forward. This works ok if the only information stored in the buffer is itself basic text broken up by line feeds. However, if for some reason the AT wanted to some how tweek where line breaks occured (perhaps for ease of reading), it would have to insert its own line feeds in along with the original information.

This way of doing things was ok for testing. In fact, with some initial tests in NVDA, I had NVDA place a line feed at the end of each node it inserted, plus I also had it scan each block of text it added and got it to insert line feeds with in the text, to break it up in to reasonable sized chunks.

Mutating text in this way is not only bad because when the text is navigated by the user, they will see a line feed character at the end of each line, even if the line was only broken due to line length rules, not because a paragraph actually ended. The other major problem is that because Mozilla Gecko provides text with imbedded objects, who's events depend on the text offsets staying the same as what they internally have, things could get out of sync pretty quickly.

I then designed a way so that the AT or backend, when adding the text to the storage buffer, could provide a list of offsets where lines should be broken. These would be soft line breaks that did not actually appear in the text, but the buffer would know about them and when asked for line offsets, could take those in to account.

I was happy with this approach for quite a while, as it meant 1. that we were not mutating the text at all and Gecko events would be happy, and 2. Users could arrow to the end of a line in the middle of a paragraph and not see line feeds that shouldn't be there.

There were two major problems with this approach. The first was that the AT or backend needed to know the user's chosen maximum line length at render time, and although individual text blocks would not contain lines longer than the chosen length, there was nothing stopping two text blocks (say part of a paragraph and then some links) from all together added up being much longer than the chosen length. Of course this wouldn't be a problem if a line break was inforced at the end of all nodes (such as in many popular windows screen readers), but if NVDA was to support a screen layout, then this problem could be quite evident.

Eventually I decided on the third approach. This way was to allow getBufferLineOffsets to receive a maximum line length int , and also an int that indicated whether a screen layout was to be used, and then it would calculate the offsets itself by a set of steps. To accomidate the new way, tag nodes in the buffer also needed to take a new member variable, addTagNodeToBuffer also needed to be able to receive this. This was an int that indicated if this tag node was a block element or not, as in, should the buffer assume that this node has to both inforce the start and end of lines at its edges.

So, the steps that getBufferLineOffsets takes are: *Set some initial line offsets to the start and end of the buffer *Locate the deepest node at the offset given *Move up the node's ancestors until it locates a tagNode that is indicated as being a block element. If one is found, then the line offsets are set to this node's start and end offsets. Also record the start and end of any tagNodes passed in a possibleLineBreaks set. *Then from the given offset, do a traversal search both backwards and forwards in the tree locating the closest block elements. If one is closer than the ancestor block element, then set the line offsets to this node's offset. Again also while traversing, save the start and end offsets of any tagNodes in the possibleLineBreaks set. *Then scan the text between the now found line offsets, looking for both line feeds and beginnings of words. If a lineBreak is found before the given offset, and its the closest one to the offset, than it now becomes the line's startOffset. Same for a line feed on or after the given offset, if its the cloest it becomes the end offset. The beginning of word offsets are saved in the possibleLineBreaks set. *Finally, The line start to line end is counted up to make sure it doesn't exceed the maximum line length the user requested. If it does, then the line start is brought forward to an offset either at the max line length, or before (using the possibleLineBreaks set as indication of where its healthy to break), and then the line length is counted up from there again. Of course this does not ever pass the original given offset, and the line end of course will not end up being before, or too far after, the given offset.

Note that if the user chooses not to use a screen layout, then rather than searching for block elements, it just uses any tagNode, meaning lines will seem to always break at the end of links and other fields etc.

A rather complex set of actions, however in c++ they really do not take too much time at all. I didn't really like this approach at first as it has a danger of being non-cemetrical, in that there could be a chance that asking for two different offsets that should be on the same line, it may give back two different lines, due to the fact that a maximum line length has to be checked. Though, I foun that as long as I always calculated all soft line breaks, even before the given offset, between clear block line breaks, this would never be a problem.

Around the same time I was improving upon the line offset code, I started re-writing NVDA to use the new virtualBuffer code. At this point in time, the new virtualBuffers for Gecko 1.9 applications have improved quite a lot in comparison to the old virtualBuffers NVDA was using before the grant. Although the backend rendering code is still in Python, the technique of using imbedded objects in text with IAccessible2 and so forth proved to be a rendering time improvement of over 50%. This means when NVDA loads a document in Firefox3, it now takes just under half the time it used to.

As the low-level management of nodes and text is all maintained in c++, this has made sure that its much more accurate, and we no longer have large chunks of documents mysteriously not being rendered, or complaints from the virtualBuffers that some ID doesn't exist and other fun things we used to have.

We have been waiting for a long time to be able to convert NVDA's virtualBuffer interface code to using the TextInfo? classes I spent a lot of time on last year. As we needed to make NVDA work with the c++ virtualBuffer storage module, and because we needed to improve NVDA's rendering patterns for imbedded objects and such, I made sure the new virtualBuffers were designed around the TextInfo? classes. this now means users of NVDA now have the ability to select text with in virtualBuffers, and also copy that text to the clipboard if they wish. They can also choose to read the buffers as a screen layout, or as a more conventional node per line layout. Its taken a little while, but I've also now added the quick key navigation (as in press h to jump to a heading, l for a list etc) in to the new virtualBuffers; its great to see that the findBufferFieldIDByProperties function actually works like I'd hoped.

At the moment we're still in discussion on the development list about how particular fields such as links etc should be spoken: should the word link be spoken before or after the text etc. Though I think we've come to a pretty good agreement on most of the fields.

The new virtualBuffers (at least in Gecko 1.9 applications) can be interacted with in regards to activating links, toggling on and off a pas-through mode to interact with edit fields and combo boxes etc, though the one thing that makes the new virtualBuffers incomplete still is that they have no support for events etc, as in if content changes dynamically in the document, the buffers do not pick up this change. This code however will be added when I re-write the rendering code in c++, as it needs to be very fast, and for best accuracy, it should really be in-process so that things don't start disappearing before NVDA's process gets around to actually asking Gecko for it. However in the mean time I've added a key stroke to tell NVDA to manually re-render the current document, so for most websites, they are able to be tested well enough.

Over the next little while its probably going to be more work on NVDA and virtualBuffers in general, to make sure that the user experience is the best it can be. Once this is ok, then my next task wil be to re-write the rendering code for Gecko virtualBuffers in c++. this should give load times an estimated speed up of about a multiple of three. Then after that the fun work will begin on trying to integrate all of the virtualBuffer c++ code so that the rendering code is injected in to the Gecko application, and rendering takes place in-process. Which by estimates should speed up load times by a multiple of twelve or so.