> 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.

> My guess is that the "undo-only" case would skip redo entries in
> much the same way as undo-in-region skips "out of bounds" entries
> (i.e. in a fairly expensive way, adjusting all subsequent elements).

Sort of, but some of those skipped elements will cancel each other out
rather than adjust positions. See
http://debbugs.gnu.org/cgi/bugreport.cgi?bug=16411#5 .

It's worth noting that undo-only might have to "mop up" a change group
partially undone by a prior undo in region, so a non regional
undo-only might also reference a partial change group.

> Combined with the fact that undo-redo-table contains entries for
> every redo element rather than for every redo group, I'm slightly
> worried about the resource use

I mulled over the same concern. undo-redo-table would probably be
larger than undo-equiv-table, though still a constant factor of undo
limit, IIUC. Implementing the "Y undo-redos of X" optimization is a
mitigating benefit.

I considered having the undo elements themselves reference what they
undid. Unfortunately, this approach would probably break current
undo-tree. Also, the references need to be weak, and I can only think
to do that by wrapping them in one element weak hash tables, defeating
the point.

> [ 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.

> IIUC this undo-redo-table business is only necessary because of
> undo-in-region. So I think we should strive to minimize the changes
> to the way undo works in the absence of undo-in-region. I understand
> that the change can't be all localized in undo-in-region (because of
> the need to skip "redo-in-region" during normal undo-only,
> basically), but we still should try to aim in that direction.

I think you're saying to not pursue the use of a closure to generate
successive undo elements as needed? I'm fine with that, but I did so
because:

  • 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.

  • 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.

  • 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.

> 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.