bug#17235: Undo in region adjusts past positions incorrectly

[Barry OReilly]

> While looking at that code, can you make that "make-selective-list"
> skip redo entries (depending on undo-no-redo, obviously), using the
> undo-equiv-table?

IOW bug 16411? The reason I was looking at this code was because of
that bug. I plan to return to it soon and put my proposition there
into code.

> I think the algorithm would be simpler to make correct if
> adjustments are applied forward chronologically rather than
> backwards. That is, the algorithm keeps a list of undo-deltas that
> grows as the algorithm iterates backwards through undo history. As
> it does so, the positions are adjusted chronologically forward
> through the undo-deltas. This approach is O(N**2), as the current
> algorithm also is, but the bright side is the proposed algorithm
> lends itself to short circuiting better than the current.

I attached the patch implementing this. The new
undo-test-region-deletion test implements the recipe of this bug
report. It fails with the current undo-make-selective-list code,
passes with the new.

Do you recall why the code ceases to make the selective list when an
element cross the region? I did not think of a good reason so I
dropped that behavior in favor of deeming the element out of region
and continuing.

I also attached undo-play.el which I used to benchmark
undo-make-selective-list. It basically fills up undo history with
small edits and then undos in region of an element on the verge of
truncation. The old undo-make-selective-list is about 213ms and the
new is 72ms.

Since the new code performs better, I didn't make the list lazy. If I
did, it would have been as a closure that returns the next element
with adjusted positions, or possibly the next change group. I may yet
do that as a part of bug 16411, as discussed there.

undo-in-region.diff
Description: Text document

undo-play.el
Description: Binary data