Comment 1 by jteh on 2014-09-12 04:38
If anyone wants to take a look at this, the code you want to tweak is NVDAObjects.behaviors.LiveText._calculateNewText. Look for the comment that says:

# Find the end of the differing text.

This chunk of code can't handle insertions or removals, only changes. We'll probably need to do a character diff or similar to handle this properly.

Comment 2 by nvdakor on 2015-04-06 12:05
Hi,
Testing shows that nVDA will not announce rest of the line if end-1 == start. If this only applies to the input position, then an easy solution would be to check if the start position is somewhere in the middle and suppress announcing the rest of the line. But there might be cases where positions are not exposed, possibly dealing with right to left text, mistakenly applied to text output (not input only) and so on.
I propose the following changes (I'll investigate this further):

• Have a current position marker handy that'll keep track of start position.
• There should be a "true start" marker to store the position where the actual text begins (may not be needed).
• If start is not at the end of the text (which is the underlying problem the ticket seeks to solve), suppress announcing the rest of the line i.e. do not append changed text.
• Find a way to do this in specific situations (terminal, for example) and ideally should be configurable (there are times when announcing rest of the line would be useful such as announcing rest of the arguments for a console program).
  My first concern is differentiating between output and input, and once that's cleared up, I'll try to have the code ready for review. Thanks.

Comment 3 by jteh on 2015-04-07 00:10
The problem with any kind of start marker is that it means it will only work where the start marker is located and it relies on the start marker always being correct. IMO, it'd be better to just handle insertions properly.

Also, it's not really so much that we intentionally announce the rest of the line. The problem is that we can't find where the difference ends. This is why I'm wondering whether a proper character diff would be best here.

Comment 4 by nvdakor (in reply to comment 3) on 2015-04-07 03:29
Replying to jteh:

The problem with any kind of start marker is that it means it will only work where the start marker is located and it relies on the start marker always being correct. IMO, it'd be better to just handle insertions properly.

Gotcha. In the end, I abandoned start marker idea, as there was really no need for it.

Also, it's not really so much that we intentionally announce the rest of the line. The problem is that we can't find where the difference ends. This is why I'm wondering whether a proper character diff would be best here.

Longest common subsequence... But that'll take a while to compute that. An in-place character diff would be ideal. But I can see that a bit of memoization might be involved, to remember the last entry in the input field. This will require some careful thought.

For testing purposes, I'm using regular version of cmd.exe on Windows 8.1 (since I'm testing from source). I found that Cygwin will not work properly for debugging purposes.
Thanks for the directions. Now I have an idea as to what to try next (I've narrowed the code scope to the routine where start and end are calculated).

Comment 5 by camlorn on 2015-04-12 23:56
I doubt that longest common subsequence is the only diffing algorithm that will work here. I can think of at least one that is potentially better and does not involve mutable state beyond the text on the console itself. I do not at all like the sound of start markers either. Starts where? This sounds like we are going to be trading a somewhat buggy implementation that is annoying but nevertheless does something sane for a very buggy implementation that is annoying and unpredictable depending on, say, network lag. I could be convinced that start markers are a good idea, but I'd like to see a lot more justification and explanation of what a start marker is.
I need to read the existing code. I'm not sure if we can tell if a line is "new" or not, or if we are only dealing with the text on the screen. There are a number of smarter things that I can think of in terms of properly detecting insertions and deletions. I will make a point of reading this code because I am actually going to have some time soon.
If it is a full screen of text at a time, I'm sure we can find a reasonably fast algorithm implemented in C. If we cannot, I'll go read the literature and make one.
Also, Python's difflib does have a character-based diff. If it works for what we need, we should try it before saying it's too slow.

Comment 6 by jteh (in reply to comment 5) on 2015-04-13 00:16
Replying to camlorn:

I do not at all like the sound of start markers either. Starts where?

If I understand correctly, Joseph meant the marker would be where the caret was last positioned. That way, you only have to do this for characters added after the cursor. The problem is that relying on the cursor is, well, unreliable at best, largely due to network lag, etc.

I need to read the existing code. I'm not sure if we can tell if a line is "new" or not, or if we are only dealing with the text on the screen.

We're only dealing with the text on the screen. We use Python difflib to determine new and modified lines and then our own crappy, broken algorithm to determine new characters on modified lines. I'm proposing we also use difflib for characters on modified lines. I guess we thought diflib would be too slow for characters when we wrote this (or we for some incorrect reason didn't think you could use it for characters), but premature optimisation is the root of all evil and all that...

I will make a point of reading this code because I am actually going to have some time soon.

For reference, it's in NVDAObjects.behaviors.LiveText._calculateNewText.

Comment 7 by jteh on 2015-04-13 02:57
FWIW, Tyler was seeing poor performance when switching between two screens full of different content. (I've seen similar issues in the past.) Some testing revealed that Python difflib was taking about 1.3 seconds to handle this, while GNU diff does it in about 0.011 sec. While this is essentially a worst case scenario and not overly common, I think it'll only get worse if we start using it for character diffs.

One option I briefly looked into some time ago is Google DIFF Match and Patch. It's available in Python, but it's pure Python. This Python extension module might be better, though again, if the pure Python version is fast enough (it could well be faster than difflib), we should just use that.

Note that if we're using another library, we need to take into account the joining of individual lines into a single string and then splitting the output text into separate lines. I wouldn't imagine this is overly expensive, but it's worth noting when doing performance tests.

Comment 8 by camlorn on 2015-04-13 20:46
I was tired and didn't realize that start markers were abandoned when I wrote that comment. My bad.
can we store the diff for only the current console? I'm not sure if window means window or the screen utility here, but that should do it.
We could also use some heuristics. Determining if a line is drastically different from what used to be there should be faster than a diff. Furthermore, we can probably do a line-based diff and then a character-based diff on lines, possibly even in parallel, in c, and using a thread pool (which NVDA may or may not have. Writing one is trivial).
The one problem with character-based diffs is getting something reasonable out of them. To that end, have we considered hooking API functions? I believe that all console stuff eventually goes through a specific set of API functions, though I cannot remember their names at the moment. I can't investigate this solution, as I'm way too far from being able to hook anything. If it does, though, we could just construct our diff via hooking those and announce changes if it stops changing for 50 ms or so.
What ground was covered on this before choosing the current implementation?

Comment 9 by jteh (in reply to comment 8) on 2015-04-14 02:15
We discussed this on IRC, but to recap:

Replying to camlorn:

can we store the diff for only the current console?

We already do.

I'm not sure if window means window or the screen utility here, but that should do it.

I meant the screen utility (or anything that completely replaces a screenful of text; even moving to a new page would do this).

We could also use some heuristics. Determining if a line is drastically different from what used to be there should be faster than a diff.

Note that we're basically dealing with a rolling diff; i.e. if n lines are appended to a full screen of text, the top n lines will disappear and all remaining lines will be index - n.

To that end, have we considered hooking API functions? I believe that all console stuff eventually goes through a specific set of API functions

It does, but I'm not sure whether we can hook these; Windows consoels aren't entirely normal processes. In any case, I'd prefer to avoid this solution; in-proc API hooking is tedious and it'd also be good if this code could apply to applications which use screen scraping (e.g. PuTTY).

Comment 10 by jteh on 2015-04-24 01:07
Building the Python extension module I referenced in comment:7 is probably going to be painful, so if we do hit performance problems with the pure Python version, it'll probably be easier just to wrap what we need from the C++ implementation and expose C functions from nvdaHelperLocal. The official C++ implementation depends on QT, but this port just uses the STL.

cc @jcsteh @camlorn @josephsl

I'm giving this a priority of 3, feel free to suggest otherwise.

@derekriemer are you thinking to extend your console timer add-on? Or is the add-on not further developed? Maybe a function for solving this issue could be added.