Refactor undo

[Chillee]

I feel like our undo is unnecessarily slow right now.

Try :sort or something on a fairly large file, and you'll see that although we finish the text update fairly quickly, it takes a lot longer before it becomes responsive again.

That's because this line takes such a long time.

https://github.com/VSCodeVim/Vim/blob/master/src/history/historyTracker.ts#L387

Our undo also has some other issues related to undoing large changes.

As for approaches to take, I see two major branches we can go down:

1. Try to leverage VSCode's default API undo stops. The main advantage of this, obviously, is that it should be the fastest possible approach. In addition, it also seems relatively simple.

2. Use Neovim for its undo functionality. The biggest advantage of this is that it lets use an UNDO TREE! Wow! As well as all the other Vim undo features (:earlier, etc.) Main disadvantage is that it's almost definitely slower, and that it ties us even close to a neovim dependency (which isn't necessarily terrible).

[johnfn]

Yes, we need to diff the file against itself, which is O(n). On a large enough file that can be expensive.

This is one thing that will be fixed when we use VSCode's history tracking stuff instead of our own.

[jleclanche]

Also see #1490, #928, #565

[J-Fields]

Re: performance, I've made some changes in the last few months so we do a full file diff only when necessary.

Long-term plan is #1490 and possibly #5206; closing in favor of them.