Refactor LiveText to use diff-match-patch by codeofdusk · Pull Request #11500 · nvaccess/nvda

codeofdusk · 2020-08-16T07:52:42Z

Link to issue number:

Closes #3200. Closes #11498.

Summary of the issue:

LiveText objects use difflib to calculate text changes:

Difflib is slow, making 10,000-line objects completely unusable and slowing down or locking up NVDA for other large objects.
Comparisons are made at the line level, so edits in the middle of lines cause characters to the right of the caret to be read out.
In 21H1 UIA console, when a large amount of text is written, the diff lags far behind the actual console's output, making autoread unusable until NVDA or the console is restarted.

Description of how this pull request fixes the issue:

This PR replaces difflib with diff-match-patch (DMP) for LiveText objects, and changes diffing functions to operate at the string rather than line level.

Testing performed:

Tested NVDA in an unbounded (10,000-line) UIA console. This caused a freeze with Difflib, but with DMP the console is usable although somewhat laggy.
Tested deleting and inserting characters in the middle of a line both with difflib and DMP. With difflib the characters to the right of the caret were read out (as stated in better support for editing characters in the middle of lines in command prompt/terminal #3200). With DMP only the changed characters were read.
Re-tested the steps from UIA in conhost: issues with visible ranges microsoft/terminal#5481 and confirmed that they are no longer reproducible.
Installed a signed build of this PR and ran a number of Windows and Linux console applications as part of daily use.

Known issues with pull request:

While this PR really helps in many extreme cases, there are others where it is actually slower than difflib by about half a second. I propose a follow-up PR to switch to the C++ version, either implemented as a Python extension or as part of NVDAHelper. Initial testing suggests that the C++ library is much faster in these cases.
Since this PR alone represents a fairly major change, I'd like to get it into 2020.4 fairly early (to get lots of testing time in on master).

Change log entry:

== Bug Fixes ==

In terminal programs, when inserting or deleting characters in the middle of a line, the characters to the right of the caret are no longer read out. (better support for editing characters in the middle of lines in command prompt/terminal #3200)

== Changes For Developers ==

LiveText._getTextLines is deprecated. Now override _getText, which returns a string of all text in the object. (Refactor LiveText to use diff-match-patch #11500)
LiveText objects now calculate diffs by character. Set _supportsDMP to False to revert to the previous line-based diffing algorithm. (Refactor LiveText to use diff-match-patch #11500)

codeofdusk · 2020-08-16T07:54:04Z

Cc @camlorn @feerrenrut @jcsteh @LeonarddeR @michaelDCurran.

AppVeyorBot · 2020-08-16T08:00:02Z

Unit test failure
Build (for testing PR)

See test results for failed build of commit adb46d31a7

…h the character-based approach.

AppVeyorBot · 2020-08-16T12:24:32Z

Unit test failure
Build (for testing PR)

See test results for failed build of commit 8314eab57d

AppVeyorBot · 2020-08-16T12:44:44Z

Unit test failure
Build (for testing PR)

See test results for failed build of commit fb60d6866e

AppVeyorBot · 2020-08-16T12:58:36Z

Unit test failure
Build (for testing PR)

See test results for failed build of commit 9b3803405f

LeonarddeR

Make sure to update the dependencies seciton of the readme

…changes in the middle of lines.

…y issues and to ease testing.

ahicks92 · 2020-08-22T19:50:53Z

Don't have much to comment on here, but glad to know this might get improved in a meaningful fashion. It'd be nice if using nano wasn't very painful, as it is today.

I'll make a point of testing once this lands.

LeonarddeR · 2020-08-24T10:59:28Z

@codeofdusk there have been several changes in this pr. Does the description still match the current situation of the code?

codeofdusk · 2020-08-24T11:22:04Z

Yes – I've been keeping the description up-to-date as I've made changes.

This should make it compatible with NVDA, otherwise Espeak wouldn't be and it's a fairly major component (it's under GPL3 and has a similar patent clause).

codeofdusk · 2020-09-03T14:08:45Z

I'm closing the PR in its current form due to licence incompatibility. I'll open a new one that calls DMP in a separate process to avoid linking with NVDA.

Refactor LiveText to use diff-match-patch via IPC with another process Changes diffing functions to operate at the string rather than line level. Adds diff-match-patch (DMP) as an optional diffing algorithm for LiveText objects. It is anticipated that DMP will become the default in a future NVDA release pending positive user testing. Unlike #11500, this PR does not import or dynamically link to DMP due to licensing issues. Instead, a Python application is run in another process that calls the DMP extension, and communicates over standard IO. Co-authored-by: Michael Curran <michaelDCurran@users.noreply.github.com> Co-authored-by: Reef Turner <feerrenrut@users.noreply.github.com>

Refactor LiveText to use diff-match-patch.

d6b4280

lukaszgo1 reviewed Aug 16, 2020

View reviewed changes

Comment thread source/NVDAObjects/window/winConsole.py Outdated

Comment thread source/winConsoleHandler.py Outdated

Revert to line-based diffing for this PR as there are some issues wit…

960ab04

…h the character-based approach.

Fix

9b28fae

Review action.

64f8f32

Add DMP as a submodule.

bb3bc0d

codeofdusk marked this pull request as draft August 17, 2020 07:19

LeonarddeR reviewed Aug 17, 2020

View reviewed changes

Comment thread source/NVDAObjects/behaviors.py Outdated

Comment thread source/NVDAObjects/behaviors.py Outdated

codeofdusk added 5 commits August 17, 2020 06:52

Switch back to character diffs and fix several assumptions.

5d88937

Use line diffing (difflib) in non-enhanced legacy consoles to report …

c2f7eca

…changes in the middle of lines.

Allow DMP to be disabled in advanced settings in case of compatibilit…

e72cd0f

…y issues and to ease testing.

Review actions.

169875a

Fixes.

096ad76

codeofdusk marked this pull request as ready for review August 18, 2020 07:13

codeofdusk requested a review from LeonarddeR August 18, 2020 07:13

feerrenrut added this to the 2020.4 milestone Aug 18, 2020

codeofdusk mentioned this pull request Aug 19, 2020

UI Automation in Windows Console: make default in FORMATTED consoles (Windows 11 Sun Valley 2) #10964

Merged

Clarify naming

2253c8e

Update licence to specify that DMP is under Apache.

facf5e5

This should make it compatible with NVDA, otherwise Espeak wouldn't be and it's a fairly major component (it's under GPL3 and has a similar patent clause).

codeofdusk closed this Sep 3, 2020

codeofdusk mentioned this pull request Sep 3, 2020

Consider relicensing NVDA as GPL3+ #11548

Closed

codeofdusk mentioned this pull request Sep 19, 2020

V2 of refactor LiveText to use diff-match-patch #11639

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Refactor LiveText to use diff-match-patch#11500

Refactor LiveText to use diff-match-patch#11500
codeofdusk wants to merge 12 commits into
nvaccess:masterfrom
codeofdusk:livetext-dmp

codeofdusk commented Aug 16, 2020 •

edited

Loading

Uh oh!

codeofdusk commented Aug 16, 2020

Uh oh!

AppVeyorBot commented Aug 16, 2020

Uh oh!

Uh oh!

Uh oh!

AppVeyorBot commented Aug 16, 2020

Uh oh!

AppVeyorBot commented Aug 16, 2020

Uh oh!

AppVeyorBot commented Aug 16, 2020

Uh oh!

LeonarddeR left a comment

Uh oh!

Uh oh!

Uh oh!

ahicks92 commented Aug 22, 2020

Uh oh!

LeonarddeR commented Aug 24, 2020

Uh oh!

codeofdusk commented Aug 24, 2020

Uh oh!

codeofdusk commented Sep 3, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

Uh oh!

Conversation

codeofdusk commented Aug 16, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Link to issue number:

Summary of the issue:

Description of how this pull request fixes the issue:

Testing performed:

Known issues with pull request:

Change log entry:

Uh oh!

codeofdusk commented Aug 16, 2020

Uh oh!

AppVeyorBot commented Aug 16, 2020

Uh oh!

Uh oh!

Uh oh!

AppVeyorBot commented Aug 16, 2020

Uh oh!

AppVeyorBot commented Aug 16, 2020

Uh oh!

AppVeyorBot commented Aug 16, 2020

Uh oh!

LeonarddeR left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

ahicks92 commented Aug 22, 2020

Uh oh!

LeonarddeR commented Aug 24, 2020

Uh oh!

codeofdusk commented Aug 24, 2020

Uh oh!

codeofdusk commented Sep 3, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

codeofdusk commented Aug 16, 2020 •

edited

Loading