bug#16411: undo-only bugs

[Stefan Monnier]

>> You talk here about "undo element", but AFAICT this actually points
>> to "a list of undo elements" (where the first element of that list
>> is presumably the "undo element" you mean). Please clarify.
> Yes, that's right.  The first element is the "undo element" referred
> to.  The cons is put in the hash table to facilitate recursive lookup.

Makes sense, but please change the docstring to make it clear.

> Implementing the "Y undo-redos of X" optimization is a
> mitigating benefit.

I've never heard anyone bump into this "Y undo-redos of X" problem, so
I don't think optimizing it is worth the trouble.  If anything should be
done with it, I think it'd be to *cut* the extra undo/redo pairs.

>> [ Nitpick: the first line of the docstring should stand on its own.  ]
> I don't understand, I thought I formatted the docstring like others,
> and did M-q it.

"Stands on its own" basically mean "doesn't end in the middle of a sentence".
Some commands only display the first line of a docstring.

> I think you're saying to not pursue the use of a closure to generate
> successive undo elements as needed?

Actually, I didn't really mean to say that.  I'm not completely
convinced that this generator is worthwhile (i.e. my first reaction was
to try and see how to get rid of it), but I then decided not to say
anything about it yet ;-)

>   • I'm trying to prevent a performance regression of the undo-only
>     command. Given the performance of undo in region with the default
>     undo limit, maybe that's not a big concern.

One way to avoid the performance regression is to use undo-equiv-table
for normal undo and only use undo-redo-table for undo-in-region (by
"use" I mean "add elements to", since both tables need to be looked up
when performing either undo).

>   • I'm concerned that undo-make-selective-list's O(N**2) algorithm is
>     unfriendly to those who want to increase the undo limit. The
>     generator allows for minimal processing of the history as needed.
>     Admittedly, I have not experimented with greater undo limits.

The old code was no faster (neither constant-factor-wise nor
algorithmically, IIUC), and it hasn't appeared as a problem so far, so
maybe it's not worth worrying about it.

I agree that doing it lazily sounds attractive, but let's keep it
for later.  I.e. the first patch should focus on fixing "undo-only of
redo-in-region".

>   • I have to muck with the interfaces regardless --
>     undo-make-selective-list still needs to deliver both the adjusted
>     element and the orig-tail to the higher undo code.

Some change will be needed, indeed.  Backward compatibility is
important, but we should first come up with an "ideal" design, and only
then can we try and figure out which parts need to be adjusted to better
preserve compatibility.

>> IIUC the crux of the matter is how to record the redo data for an
>> undo-in-region. The way I see it, for such a "redo-in-region" group,
>> we indeed need to remember which elements it undid (and which ones
>> it skipped instead), but we could store that info as a single entry
>> in an undo-redo/equiv-table.
> I originally set out to do this, but making the weak references work
> seemed overly tricky to me.  The value stored in undo-redo-table would
> need to be non weak with weak references to undo elements.  I supposed
> this would mean many one element weak hash tables. That seems dodgy.

Hmm... that's a very good point.  Worth mentioning in a comment.


        Stefan