bug#16411: undo-only bugs

bug#16411: undo-only bugs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 3936 bytes --]

Looking over the code for the undo system, I found two bugs and
constructed recipes to demonstrate. For these, each "insert" should be
exactly one change group or the recipes may not work. I use Evil so
it's easy to arrange for that.

Recipe 1:
  • Insert "aaa"
  • Insert "bbb"
  • Undo
  • Insert "ccc"
  • Insert "ddd"
  • Undo
  • Undo-only with prefix arg 2
  • Expected: none of the above insertions are in the buffer
  • Actual: buffer has aaa and bbb insertions

Reason is that undo-only skips "redo records" prior to calling
undo-more through recursive lookup in undo-equiv-table. However, it
doesn't reference undo-equiv-table again as it iterates prefix-arg
times, so it may undo redo records after the first correct undo. In
this case, it redoes bbb.

I think the solution entails moving this sort of thing into a loop in
undo-more:

  (when (and (consp equiv) undo-no-redo)
    ;; The equiv entry might point to another redo record if we have done
    ;; undo-redo-undo-redo-... so skip to the very last equiv.
    (while (let ((next (gethash equiv undo-equiv-table)))
             (if next (setq equiv next))))
    (setq pending-undo-list equiv))

Recipe 2:
  • Insert "aaa"
  • Insert "bbb"
  • Mark region around "aaa" but not "bbb"
  • Undo (in region)
  • Mark region around "bbb" and where "aaa" used to be
  • Undo-only
  • Expected: none of the above insertions are in the buffer
  • Actual: buffer has aaa and bbb insertions

The code appears to simply punt on undo-only in region and behaves
like ordinary undo. Thus it undoes the redo record to bring back bbb.

One idea I have to solve bug 2 is to extend undo-equiv-table or create
another redo-record-table weak hash table with the same key type as
the undo-equiv-table: a "redo record" as a cons of buffer-undo-list.
The value would have prefix-arg number of "undone records" which that
redo record undid.

When undo-only in region using the redo-record-table the algorithm
would go roughly like:

  While pending-undo-list non nil:
    Pop undo-i from pending-undo-list:
    If undo-i is a redo record (exists in the table):
      Remove undo-i's undone records from pending-undo-list (or
      otherwise arrange to skip it)
    Else:
      Undo undo-i
      If "undo undo-i" was done prefix-arg times:
        Break (finished)
  Reached end of undo history

As a non rigorous example, if there is an undo A of an undo B of an
edit C in the region:
  • When undo-i is A, B is removed from consideration
  • With B gone, undo-i never becomes B, so C remains in
    pending-undo-list. A and B effectively cancelled each other out
  • C is correctly picked for the undo-only

The reason undo-equiv-table is insufficient is because its value is
the change group *after* the undone record. That change group may have
been filtered out of pending-undo-list. OTOH, replacing existing usage
of undo-equiv-table with the proposed redo-record-table is straight
forward: go one change group forward to get the same value as the
undo-equiv-table. Thus undo-equiv-table could be phased out in favor
of using the redo-record-table.

Another issue is that for both recipes, Emacs echos "Undo!". For bug
2, it does not match what Emacs actually did. For bug 1, it is partly
incorrect because Emacs did an undo and a redo. Perhaps when (< 1
prefix-arg), the echo message should convey more. Possible messages
might be "Undo, redo!" and "Redo, undo, undo! No further undo
information"

The reason I'm looking at this code at all is that I am investigating
Stefan's guidance [1] about better integrating undo-tree with the
builtin undo system. I think redo-record-table may help to this end,
but I'll elaborate on that at later time. No later than the time I
would submit a patch for bug 2, if welcome.

[1]
http://lists.gnu.org/archive/html/gnu-emacs-sources/2009-11/msg00010.html

[-- Attachment #2: Type: text/html, Size: 4501 bytes --]

bug#16411: undo-only bugs

[Stefan Monnier]

> I think the solution entails moving this sort of thing into a loop in
> undo-more:

>   (when (and (consp equiv) undo-no-redo)
>     ;; The equiv entry might point to another redo record if we have done
>     ;; undo-redo-undo-redo-... so skip to the very last equiv.
>     (while (let ((next (gethash equiv undo-equiv-table)))
>              (if next (setq equiv next))))
>     (setq pending-undo-list equiv))

Indeed.  Or, equivalently, changing `undo' so it only calls undo-more with
argument 1 (and use the above while loop between each call to undo-more).

> Recipe 2:
>   • Insert "aaa"
>   • Insert "bbb"
>   • Mark region around "aaa" but not "bbb"
>   • Undo (in region)
>   • Mark region around "bbb" and where "aaa" used to be
>   • Undo-only
>   • Expected: none of the above insertions are in the buffer
>   • Actual: buffer has aaa and bbb insertions

> The code appears to simply punt on undo-only in region and behaves
> like ordinary undo. Thus it undoes the redo record to bring back bbb.

undo-in-region does not implement undo-only, indeed.  I think the way to
implement undo-only is to change undo-make-selective-list so it also
skips redo entries (depending on undo-no-redo, obviously) using the
above while loop.


        Stefan

bug#16411: undo-only bugs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 782 bytes --]

> undo-in-region does not implement undo-only, indeed. I think the way
> to implement undo-only is to change undo-make-selective-list so it
> also skips redo entries (depending on undo-no-redo, obviously) using
> the above while loop.

I don't see how that's a correct solution in the face of arbitrary
regional undos and prefix args. Would you have the redo records
resulting from regional undos still map to t in the undo-equiv-table?
How does your solution account for redo records that undid several
because of prefix-arg? undo-equiv-table only maps to the change group
after the last undone record without information about the (1-
prefix-arg) others.

My proposition accounts for these considerations and I think is
correct. If not I hope to find out when I start hacking it.

[-- Attachment #2: Type: text/html, Size: 876 bytes --]

bug#16411: undo-only bugs

[Stefan Monnier]

>> undo-in-region does not implement undo-only, indeed.  I think the way
>> to implement undo-only is to change undo-make-selective-list so it
>> also skips redo entries (depending on undo-no-redo, obviously) using
>> the above while loop.
> I don't see how that's a correct solution in the face of arbitrary
> regional undos and prefix args. Would you have the redo records
> resulting from regional undos still map to t in the undo-equiv-table?

I was talking about simply making undo-in-region
properly skip the previous undos (presuming they don't themselves come
from an undo-in-region).

IIUC, you're talking of skipping (e.g. in a non-region undo) the undos
that took place during undo-in-region, right?  If so, I don't have an
answer for how we could do that, in general.

In your pseudo-code:

  While pending-undo-list non nil:
    Pop undo-i from pending-undo-list:
    If undo-i is a redo record (exists in the table):
      Remove undo-i's undone records from pending-undo-list (or
      otherwise arrange to skip it)
    Else:
      Undo undo-i
      If "undo undo-i" was done prefix-arg times:
        Break (finished)
  Reached end of undo history

I have no idea how to implement the part:

      Remove undo-i's undone records from pending-undo-list (or
      otherwise arrange to skip it)

I guess I do have some idea how to do it, but it looks like a lot of
work, since we have to adjust the positions in the rest of
pending-undo-list.

Other than that I don't understand what your redo-record-table does.
AFAICT the test "undo-i is a redo record" can be performed with
undo-equiv-table.

> How does your solution account for redo records that undid several
> because of prefix-arg?

As you have discovered the current code does not even try to account for
prefix args.

> undo-equiv-table only maps to the change group
> after the last undone record without information about the (1-
> prefix-arg) others.

Right: the loop that undoes N steps (either in undo-more or in undo if
we change undo to only call undo-more with a 1) needs not only to use
undo-equiv-table at each iteration to skip redo entries, but it also
needs to add an entry in undo-equiv-table at each iteration.


        Stefan

bug#16411: undo-only bugs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 1127 bytes --]

> I guess I do have some idea how to do it, but it looks like a lot of
> work, since we have to adjust the positions in the rest of
> pending-undo-list.

Are you saying the buffer positions in the undo data become
invalidated? That could indeed be a detail I missed. Let me take a
closer look.

> Right: the loop that undoes N steps (either in undo-more or in undo
> if we change undo to only call undo-more with a 1) needs not only to
> use undo-equiv-table at each iteration to skip redo entries, but it
> also needs to add an entry in undo-equiv-table at each iteration.

And recall that these N are rolled into one redo record. So a redo
record needs to reference N records it undid. That means
undo-equiv-table's value type has a new format that could conceivably
break user code, so let's name it something different:
redo-record-table. Now the only difference with redo-record-table as I
described it earlier is the off-by-one-change-group difference.

Actually, this makes me realize the solution to bug 1 is inadequate.
Calling (undo-primitive 1) N times creates N redo records whereas
(undo-primitive N) creates one.

[-- Attachment #2: Type: text/html, Size: 1262 bytes --]

bug#16411: undo-only bugs

[Stefan Monnier]

>> I guess I do have some idea how to do it, but it looks like a lot of
>> work, since we have to adjust the positions in the rest of
>> pending-undo-list.
> Are you saying the buffer positions in the undo data become
> invalidated?  That could indeed be a detail I missed.  Let me take a
> closer look.

Not exactly invalidated, but we can't just skip an undo-record without
adjusting the subsequent records.

We can skip a bunch of undo-record specified via undo-equiv-table
because that table stores pairs of undo states that correspond
to the exact same buffer, so the "adjustment" is a no-op.

>> Right: the loop that undoes N steps (either in undo-more or in undo
>> if we change undo to only call undo-more with a 1) needs not only to
>> use undo-equiv-table at each iteration to skip redo entries, but it
>> also needs to add an entry in undo-equiv-table at each iteration.
> And recall that these N are rolled into one redo record.

Not sure what you mean here.

> So a redo record needs to reference N records it undid.

I'm even more confused.

> Actually, this makes me realize the solution to bug 1 is inadequate.
> Calling (undo-primitive 1) N times creates N redo records whereas
> (undo-primitive N) creates one.

No, primitive-undo does not add any undo boundary.


        Stefan

bug#16411: undo-only bugs

[Stefan Monnier]

>> Actually, this makes me realize the solution to bug 1 is inadequate.
>> Calling (undo-primitive 1) N times creates N redo records whereas
>> (undo-primitive N) creates one.
> No, primitive-undo does not add any undo boundary.

Actually, now I'm not sure what you meant by "redo records".
(primitive-undo N) will undo all the M "records" that appear before the
next Nth undo boundary, and will correspondingly add M redo "records",
but no boundary.


        Stefan

bug#16411: undo-only bugs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 560 bytes --]

> >> Actually, this makes me realize the solution to bug 1 is
> >> inadequate. Calling (undo-primitive 1) N times creates N redo
> >> records whereas (undo-primitive N) creates one.
> > No, primitive-undo does not add any undo boundary.

> Actually, now I'm not sure what you meant by "redo records".
> (primitive-undo N) will undo all the M "records" that appear before
> the next Nth undo boundary, and will correspondingly add M redo
> "records", but no boundary.

I took another look at the code and see I was mistaken on this point.
I'll work on a patch.

[-- Attachment #2: Type: text/html, Size: 708 bytes --]

bug#16411: undo-only bugs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 3493 bytes --]

After looking at and considering more of the undo code, here's my
current thinking about how to solve bug 2.

The Elisp manual states that undo elements of buffer-undo-list can be
of the form:

  (apply delta beg end funname . args)

Define a "redo element" as an element of buffer-undo-list created
because of an undo command. Suppose we change the way redo elements
are represented to:

  (apply delta beg end 'undo-redo . (undone-element undo-delta))

Where:
  • delta, beg, end are as documented.
  • undo-redo is a new function that copies undone-element, applies
    undo-delta, then calls primitive-undo on it.
  • undone-element is the undone element of buffer-undo-list.
  • undo-delta is (position . offset) indicating how undo-redo should
    modify a copy of undone-element in order to carry out the redo.

When executing undo-only:
  • Assume pending-undo-list can be lazily computed
  • Let undo-skip-set be an empty set of undo elements to skip
  • Iterate over pending-undo-list until prefix-arg undos complete:
    • If the element is in undo-skip-set:
      • Remove it from undo-skip-set
      • Continue loop
    • If the element is of the form for a redo element:
      • Insert its undone-element in the undo-skip-set
    • Else undo the element

Using a BST for the undo-skip-set would be appropriate, but I don't
see that one is available to core Elisp code. A skip list data
structure would be a simple option with similar performance
characteristics. Note: this is a different kind of "skip", you can
duckduckgo "skip lists".

In your earlier reply, you hinted that switching undo-only from using
the undo-equiv-table to calling undo-make-selective-list might create
a noticable performance regression. The latter is O(N*N) for N sized
undo history! I would expect undo-only will generally have an element
to find, in which case, being able to compute next elements of
pending-undo-list as needed instead of in full upfront may be a
sufficient solution.

If it isn't sufficient, I can also make the algorithm O(N*log(N)).
One way to do this is using another skip list to store the
undo-deltas: sort by position, and at each node store the sum of the
offsets over the skip interval following that node. The analogous
thing can be done with a BST: put the sum of a subtree's offsets at
each node. This is more complex in part because the sums need to be
updated during tree rotations.

There's another benefit to my proposed representation for redo
elements. Consider the use case:
  • Delete text X bytes large
  • Do Y cycles of undo and redo

As I understand the current code, the size of undo history grows by
approximately X*Y. With this new way to represent redo elements, undo
history grows approximately Y instead.

This proposal implies recursive calls to primitive-undo. The size of
the Lisp call stack would be a function of how deep redo records refer
to undone redo records. Maybe there are reasonable ways to deal with
that or maybe it's a non issue.

Are there examples of existing code putting (apply delta beg end
funname . args) into the buffer-undo-list? I want to see what the
options might be for pushing redo elements in that format. The best I
can think of right now is a dynamically bound variable set only during
an undo and examined in record functions in undo.c.

There's more I could say about other details, but I'll stop now to get
feedback on the overall idea.

[-- Attachment #2: Type: text/html, Size: 3770 bytes --]

bug#16411: undo-only bugs

[Stefan Monnier]

> Where:
>   • delta, beg, end are as documented.
>   • undo-redo is a new function that copies undone-element, applies
>     undo-delta, then calls primitive-undo on it.
>   • undone-element is the undone element of buffer-undo-list.
>   • undo-delta is (position . offset) indicating how undo-redo should
>     modify a copy of undone-element in order to carry out the redo.

> When executing undo-only:
>   • Assume pending-undo-list can be lazily computed
>   • Let undo-skip-set be an empty set of undo elements to skip
>   • Iterate over pending-undo-list until prefix-arg undos complete:
>     • If the element is in undo-skip-set:
>       • Remove it from undo-skip-set
>       • Continue loop
>     • If the element is of the form for a redo element:
>       • Insert its undone-element in the undo-skip-set
>     • Else undo the element

In which way would this help fixing bug 2 (I thought we had already
understood how to fix bug 2, BTW)?

More problematic: the step "Insert its undone-element in the
undo-skip-set" means that we skip this "redo" element, which means that
all the subsequent elements (until the matching undone-element) may have
incorrect buffer positions.

Luckily, you probably won't bump into any problem because all these
intermediate elements will themselves be redo elements or be in
undo-skip-set.  But it's still dangerous and wasteful (why not skip all
these elements in one swoop as we currently do with undo-equiv-table).


        Stefan

bug#16411: undo-only bugs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 3175 bytes --]

> (I thought we had already understood how to fix bug 2, BTW)

No, we both agreed about how to fix bug 1, which isn't too hard or
intrusive. I'm talking about bug 2 now. I appreciate you taking the
time to discuss it with me. You said about it:

> IIUC, you're talking of skipping (e.g. in a non-region undo) the
> undos that took place during undo-in-region, right? If so, I don't
> have an answer for how we could do that, in general.

If you require the solution use undo-equiv-table, then I would have to
also admit to not having an answer.

> why not skip all these elements in one swoop as we currently do with
> undo-equiv-table

Because it would not be correct. I constructed recipe 2 in order to
demonstrate the incorrectness.

> In which way would this help fixing bug 2

Recipe 2 used an undo-in-region to trick the current undo-only
behavior into finding the wrong element to undo. Under my proposed
solution, undo-in-region creates a change group of redo elements, each
with a reference to its undone-element. This allows undo-only to find
the correct element to undo per the algorithm I described.

Why is it correct? undo-only wishes to find the most recent non redo
element A which is currently in the buffer (ie the net effect is it's
not undone). If A is reachable through an odd number of hops across
undo-element references, then it is undone, if even it is not undone.
If there exist paths to A both even and odd in length, then something
strange has happened to the undo history. The effect of skipping undo
elements as I described it is to exclude the ones with odd length
paths. For example, consider:

  A1 undoes A2 undoes A3 undoes A4 undoes A5

A2 and A4 will find themselves in the undo-skip-set, the others won't.
undo-only correctly finds A5 as the element to undo.

  B1 undoes B2 undoes B3 undoes B4 undoes B5 undoes B6

B2, B4, B6 will be skipped, so undo-only will have to find some other
non B element to undo, as it should in this case.

> the step "Insert its undone-element in the undo-skip-set" means that
> we skip this "redo" element, which means that all the subsequent
> elements (until the matching undone-element) may have incorrect
> buffer positions.

I explained this: I would rework the pending-undo-list computation to
be lazier, perhaps creating a get-next-pending-undo function instead
of computing the entire pending-undo-list upfront. undo-only would use
this function to get the next copy of an element of buffer-undo-list,
with positions adjusted using an index of undo-delta sums.
get-next-pending-undo would be part of "Iterate over
pending-undo-list", which means we are adjusting positions whether the
element will be skipped or not.

This rework to use a new get-next-pending-undo can be a self contained
patch which would benefit undo in region's performance right away,
even if undo-only doesn't use it after just the first patch.

> But it's still dangerous and wasteful

By dangerous do you mean incorrect? By wasteful do you mean non
performant? Maybe the discussion will be less confusing if we focus on
correctness first, then move to performance? Could you describe what
part of my proposal is incorrect?

[-- Attachment #2: Type: text/html, Size: 3540 bytes --]

bug#16411: undo-only bugs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 1190 bytes --]

Here's another bug with recipe. Again, each "insert" should be a
change group.

  * ./src/emacs -Q
  * In *scratch* at least twice:
    * Insert "aaa"
    * Undo
  * Select the entire buffer
  * Undo in region with prefix-arg 4
  * Observe the wrongful deletion of the string: "fer." in the Lisp
    comment.

undo-elt-in-region has a discrepency between whether (TEXT . POSITION)
and (BEGIN . END) are in the region:

  ;; (BEGIN . END)
  (and (>= (car undo-elt) start)
       (<= (cdr undo-elt) end))
        ^^

  ;; (TEXT . POSITION)
  (and (>= (abs (cdr undo-elt)) start)
       (< (abs (cdr undo-elt)) end))
        ^

One is compared to the end by <= and the other by <. Consequently,
(192 . 195) is deemed in the region, (aaa . 192) outside the region.
With (aaa . 192) outside the region, all subsequent positions of
undo-list-copy are decremented by three, including the next (192 .
195) which becomes (189 . 192). (189 . 192) is deemed in the region,
but that's not valid given the restoration of "aaa" was just excluded.
It's now pear shaped.

I'm collecting these bugs related to the undo system in one bug report
because that is the most organized way for me to address them.

[-- Attachment #2: Type: text/html, Size: 1661 bytes --]

bug#16411: undo-only bugs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 429 bytes --]

> * ./src/emacs -Q
> * In *scratch* at least twice:
>   * Insert "aaa"
>   * Undo
> * Select the entire buffer
> * Undo in region with prefix-arg 4
> * Observe the wrongful deletion of the string: "fer." in the Lisp
>   comment.

A more concise recipe:

  * ./src/emacs -Q
  * In *scratch* insert "aaa"
  * Undo
  * Select the entire buffer
  * Undo in region
  * Observe the wrongful deletion of the period in the Lisp comment.

[-- Attachment #2: Type: text/html, Size: 690 bytes --]

bug#16411: undo-only bugs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 2943 bytes --]

>   ;; (BEGIN . END)
>   (and (>= (car undo-elt) start)
>        (<= (cdr undo-elt) end))
>         ^^
>
>   ;; (TEXT . POSITION)
>   (and (>= (abs (cdr undo-elt)) start)
>        (< (abs (cdr undo-elt)) end))
>         ^

Using 'git log -L' on these two code fragments, I found the (BEGIN .
END) case changed in this commit to "Fix one-off error at END".

commit 9debee7a5e6ebc0c32141619248e7390f1476946
Author: Richard M. Stallman <rms@gnu.org>
Date:   Mon Sep 9 00:27:30 2002 +0000

    (undo-elt-in-region): Fix one-off error at END.
    (forward-visible-line): Handle invisibility by ignoring
    invisible newlines.  Also include entire invisible lines beyond
    the stopping point.

diff --git a/lisp/simple.el b/lisp/simple.el
index bfef653..d9ae114 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -1089,7 +1089,7 @@ we stop and ignore all further elements."
 If it crosses the edge, we return nil."
   (cond ((integerp undo-elt)
         (and (>= undo-elt start)
-             (<  undo-elt end)))
+             (<= undo-elt end)))
        ((eq undo-elt nil)
         t)
        ((atom undo-elt)
@@ -1109,16 +1109,16 @@ If it crosses the edge, we return nil."
                   (cons alist-elt undo-adjusted-markers)))
           (and (cdr alist-elt)
                (>= (cdr alist-elt) start)
-               (< (cdr alist-elt) end))))
+               (<= (cdr alist-elt) end))))
        ((null (car undo-elt))
         ;; (nil PROPERTY VALUE BEG . END)
         (let ((tail (nthcdr 3 undo-elt)))
           (and (>= (car tail) start)
-               (< (cdr tail) end))))
+               (<= (cdr tail) end))))
        ((integerp (car undo-elt))
         ;; (BEGIN . END)
         (and (>= (car undo-elt) start)
-             (< (cdr undo-elt) end)))))
+             (<= (cdr undo-elt) end)))))

 (defun undo-elt-crosses-region (undo-elt start end)
   "Test whether UNDO-ELT crosses one edge of that region START ... END.

This didn't change the (TEXT . POSITION) case, which hasn't changed
since 1998 when it was first introduced. Maybe it was forgotten in the
above 2002 change?

Anyway, I made this change locally:

diff --git a/lisp/simple.el b/lisp/simple.el
index b90382d..01d4f19 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -2434,7 +2434,7 @@ If it crosses the edge, we return nil."
        ((stringp (car undo-elt))
         ;; (TEXT . POSITION)
         (and (>= (abs (cdr undo-elt)) start)
-             (< (abs (cdr undo-elt)) end)))
+             (<= (abs (cdr undo-elt)) end)))
        ((and (consp undo-elt) (markerp (car undo-elt)))
         ;; This is a marker-adjustment element (MARKER . ADJUSTMENT).
         ;; See if MARKER is inside the region.

and I didn't witness the incorrect behavior from undo in region.

Another justification for this change, in addition to fixing the
buffer corruption my recipe demonstrates, is that without it, a
deletion at the EOB is inaccessible via undo in region.

[-- Attachment #2: Type: text/html, Size: 3419 bytes --]

bug#16411: undo in region corrupts existing text

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 699 bytes --]

Ping. Is my fix to the bug described at
http://debbugs.gnu.org/cgi/bugreport.cgi?bug=16411#38 acceptable to
install? Here is the patch again:

diff --git a/lisp/simple.el b/lisp/simple.el
index b90382d..01d4f19 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -2434,7 +2434,7 @@ If it crosses the edge, we return nil."
        ((stringp (car undo-elt))
         ;; (TEXT . POSITION)
         (and (>= (abs (cdr undo-elt)) start)
-             (< (abs (cdr undo-elt)) end)))
+             (<= (abs (cdr undo-elt)) end)))
        ((and (consp undo-elt) (markerp (car undo-elt)))
         ;; This is a marker-adjustment element (MARKER . ADJUSTMENT).
         ;; See if MARKER is inside the region.

[-- Attachment #2: Type: text/html, Size: 865 bytes --]

bug#16411: undo in region corrupts existing text

[Stefan Monnier]

> Ping. Is my fix to the bug described at
> http://debbugs.gnu.org/cgi/bugreport.cgi?bug=16411#38 acceptable to
> install? Here is the patch again:

I think so, yes, but please add a corresponding ERT test case.


        Stefan

bug#16411: undo-only bugs

[Barry OReilly]

I am pursuing a solution more like the first one I suggested in bug
16411 and have a preliminary patch I would like to get some feedback
on. undo-tests pass but the patch does not fix the bug yet. The patch
does two major things:

   1: Defines and populates a new undo-redo-table
   2: Uses closures to lazily compute pending undo elements

Item 1 is the crucial one. The undo-redo-table is somewhat like
undo-equiv-table, except that instead of mapping equal buffer states,
it maps undo elements to what they undid. This conveys better
information.

Mapping equal buffer states with undo-equiv-table is not workable,
because undos in region generally don't return the user to a buffer
state that actually existed before. Consider: insert A, insert B, undo
in region of A. The buffer has just B for the first time.

Existing use of undo-equiv-table can readily switch to use
undo-redo-table, as described in the obsoletion note of the patch. The
converse, using undo-equiv-table instead of undo-redo-table, would
require traversing backwards in the singly linked list.

The reason undo-redo-table maps at the element level, as opposed to
the change group level, is because in the case of undo in region with
a prefix arg, the newly created change group needs to reference
subsets of potentially many prior change groups.

Having undo elements reference what they undid would help solve
several issues:

   1: undo-only in region doesn't work.
   2: Normal undo-only after an undo in region doesn't work. I've
      previously outlined how the solution would use the
      undo-redo-table.
   3: Undo in region has counter intuitive behavior as described in
      the FIXME of simple.el describing undo in region.
   4: Deleting X bytes, then doing Y iterations of undo and redo
      causes undo history to grow about X*Y. To grow proportional to Y
      should be achievable: set undo-in-progress to the in progress
      element, and the C level undo recording to use it and
      undo-redo-table to find the eq Lisp_String.
   5: Undo Tree should more tightly integrate with the builtin undo
      system. To do so, it needs sufficient information to visualize
      the buffer-undo-list as a tree. Undo Tree has a means to
      visualize undo in regions, so undo-equiv-table is inadequate.

There are variations on how elements could reference what they undid,
but fundamentally I think it is essential. I wish to know how you like
the direction the patch is going as I proceed to solve some problems
building upon it.

The patch ignores whitespace.

diff --git a/lisp/simple.el b/lisp/simple.el
index 1484339..09b3a5f 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -2054,20 +2054,32 @@ Go to the history element by the absolute
history position HIST-POS."
 ;Put this on C-x u, so we can force that rather than C-_ into startup msg
 (define-obsolete-function-alias 'advertised-undo 'undo "23.2")

+(defvar undo-redo-table (make-hash-table :test 'eq :weakness t)
+  "Hash table mapping undo elements created by an undo command to
+the undo element they undid.  Specifically, the keys and values
+are eq to cons of buffer-undo-list.  The hash table is weak so as
+truncated undo elements can be garbage collected.")
 (defconst undo-equiv-table (make-hash-table :test 'eq :weakness t)
   "Table mapping redo records to the corresponding undo one.
 A redo record for undo-in-region maps to t.
 A redo record for ordinary undo maps to the following (earlier) undo.")
+(make-obsolete-variable
+ 'undo-equiv-table
+ "Use undo-redo-table instead.  For non regional undos, (gethash
+k undo-equiv-table) is the same as taking (gethash k
+undo-redo-table) and scanning forward one change group."
+ "24.5")

 (defvar undo-in-region nil
-  "Non-nil if `pending-undo-list' is not just a tail of `buffer-undo-list'.")
+  "Non-nil during an undo in region.")

 (defvar undo-no-redo nil
   "If t, `undo' doesn't go through redo entries.")

 (defvar pending-undo-list nil
-  "Within a run of consecutive undo commands, list remaining to be undone.
-If t, we undid all the way to the end of it.")
+  "Within a run of consecutive undo commands, is a tail of
+buffer-undo-list for remaining undo elements, or a closure to
+generate them.  If t, there is no more to undo.")

 (defun undo (&optional arg)
   "Undo some previous changes.
@@ -2115,9 +2127,10 @@ as an argument limits undo to changes within
the current region."
       (undo-more 1))
     ;; If we got this far, the next command should be a consecutive undo.
     (setq this-command 'undo)
-    ;; Check to see whether we're hitting a redo record, and if
-    ;; so, ask the user whether she wants to skip the redo/undo pair.
-    (let ((equiv (gethash pending-undo-list undo-equiv-table)))
+    ;; Check to see whether we're hitting a redo record
+    (let ((equiv (if (functionp pending-undo-list)
+                     t
+                   (gethash pending-undo-list undo-equiv-table))))
       (or (eq (selected-window) (minibuffer-window))
          (setq message (format "%s%s!"
                                 (if (or undo-no-redo (not equiv))
@@ -2202,40 +2215,48 @@ Some change-hooks test this variable to do
something different.")
   "Undo back N undo-boundaries beyond what was already undone recently.
 Call `undo-start' to get ready to undo recent changes,
 then call `undo-more' one or more times to undo them."
-  (or (listp pending-undo-list)
+  (when (eq pending-undo-list t)
     (user-error (concat "No further undo information"
                         (and undo-in-region " for region"))))
   (let ((undo-in-progress t))
-    ;; Note: The following, while pulling elements off
-    ;; `pending-undo-list' will call primitive change functions which
-    ;; will push more elements onto `buffer-undo-list'.
-    (setq pending-undo-list (primitive-undo n pending-undo-list))
-    (if (null pending-undo-list)
+    ;; Note: The following changes the buffer, and so calls primitive
+    ;; change functions that push more elements onto
+    ;; `buffer-undo-list'.
+    (unless (if (functionp pending-undo-list)
+                (undo-using-generator pending-undo-list n)
+              (setq pending-undo-list
+                    (primitive-undo n pending-undo-list)))
+      ;; Reached the end of undo history
       (setq pending-undo-list t))))

 (defun primitive-undo (n list)
-  "Undo N records from the front of the list LIST.
+  "Undo N change groups from the front of the list LIST.
 Return what remains of the list."
+  (undo-using-generator
+   (lambda (&optional option)
+     (prog1 (cons (car list) list)
+       (unless (eq option 'peek) (pop list))))
+   n)
+  list)

-  ;; This is a good feature, but would make undo-start
-  ;; unable to do what is expected.
-  ;;(when (null (car (list)))
-  ;;  ;; If the head of the list is a boundary, it is the boundary
-  ;;  ;; preceding this command.  Get rid of it and don't count it.
-  ;;  (setq list (cdr list))))
-
+(defun undo-using-generator (generator n)
+  "Undo N change groups using a GENERATOR closure to get
+successive undo elements. Return the last association returned
+from GENERATOR or nil if the end of undo history was reached."
   (let ((arg n)
         ;; In a writable buffer, enable undoing read-only text that is
         ;; so because of text properties.
         (inhibit-read-only t)
         ;; Don't let `intangible' properties interfere with undo.
         (inhibit-point-motion-hooks t)
-        ;; We use oldlist only to check for EQ.  ++kfs
-        (oldlist buffer-undo-list)
-        (did-apply nil)
-        (next nil))
+        next-assoc)
     (while (> arg 0)
-      (while (setq next (pop list))     ;Exit inner loop at undo boundary.
+      ;; Exit this inner loop at an undo boundary, which would be
+      ;; next-assoc of (nil . nil).
+      (while (car (setq next-assoc (funcall generator)))
+        (let ((next (car next-assoc))
+              (orig-tail (cdr next-assoc))
+              (prior-undo-list buffer-undo-list))
           ;; Handle an integer by setting point to that value.
           (pcase next
             ((pred integerp) (goto-char next))
@@ -2289,21 +2310,27 @@ Return what remains of the list."
                  (apply fun-args))
                (unless (eq currbuff (current-buffer))
                  (error "Undo function switched buffer"))
-             (setq did-apply t)))
+               ;; Make sure an apply entry produces at least one undo entry,
+               ;; so the test in `undo' for continuing an undo series
+               ;; will work right.
+               (when (eq prior-undo-list buffer-undo-list)
+                 (push (list 'apply 'cdr nil) buffer-undo-list))))
             ;; Element (STRING . POS) means STRING was deleted.
             (`(,(and string (pred stringp)) . ,(and pos (pred integerp)))
              (when (let ((apos (abs pos)))
                      (or (< apos (point-min)) (> apos (point-max))))
                (error "Changes to be undone are outside visible
portion of buffer"))
-           (let (valid-marker-adjustments)
+             (let (valid-marker-adjustments
+                   ahead)
                ;; Check that marker adjustments which were recorded
                ;; with the (STRING . POS) record are still valid, ie
                ;; the markers haven't moved.  We check their validity
                ;; before reinserting the string so as we don't need to
                ;; mind marker insertion-type.
-             (while (and (markerp (car-safe (car list)))
-                         (integerp (cdr-safe (car list))))
-               (let* ((marker-adj (pop list))
+               (while (and (setq ahead (funcall generator 'peek))
+                           (markerp (car-safe (car ahead)))
+                           (integerp (cdr-safe (car ahead))))
+                 (let* ((marker-adj (car (funcall generator)))
                         (m (car marker-adj)))
                    (and (eq (marker-buffer m) (current-buffer))
                         (= pos m)
@@ -2331,16 +2358,13 @@ Return what remains of the list."
                (set-marker marker
                            (- marker offset)
                            (marker-buffer marker))))
-          (_ (error "Unrecognized entry in undo list %S" next))))
+            (_ (error "Unrecognized entry in undo list %S" next)))
+          ;; Map the new undo element to what it undid.  Not aware yet
+          ;; of cases where we want to map all new elements.
+          (unless (eq prior-undo-list buffer-undo-list)
+            (puthash buffer-undo-list orig-tail undo-redo-table))))
       (setq arg (1- arg)))
-    ;; Make sure an apply entry produces at least one undo entry,
-    ;; so the test in `undo' for continuing an undo series
-    ;; will work right.
-    (if (and did-apply
-             (eq oldlist buffer-undo-list))
-        (setq buffer-undo-list
-              (cons (list 'apply 'cdr nil) buffer-undo-list))))
-  list)
+    next-assoc))

 ;; Deep copy of a list
 (defun undo-copy-list (list)
@@ -2353,16 +2377,16 @@ Return what remains of the list."
     elt))

 (defun undo-start (&optional beg end)
-  "Set `pending-undo-list' to the front of the undo list.
-The next call to `undo-more' will undo the most recently made change.
-If BEG and END are specified, then only undo elements
-that apply to text between BEG and END are used; other undo elements
-are ignored.  If BEG and END are nil, all undo elements are used."
+  "Set `pending-undo-list' to begin a run of undos.  The next
+call to `undo-more' will undo the next change group.  If BEG and
+END are specified, then only undo elements that apply to text
+between BEG and END are used; other undo elements are ignored.
+If BEG and END are nil, all undo elements are used."
   (if (eq buffer-undo-list t)
       (user-error "No undo information in this buffer"))
   (setq pending-undo-list
        (if (and beg end (not (= beg end)))
-           (undo-make-selective-list (min beg end) (max beg end))
+           (undo-make-regional-generator (min beg end) (max beg end))
          buffer-undo-list)))

 ;; The positions given in elements of the undo list are the positions
@@ -2424,30 +2448,39 @@ are ignored.  If BEG and END are nil, all undo
elements are used."
 ;; "ccaabad", as though the first "d" became detached from the
 ;; original "ddd" insertion.  This quirk is a FIXME.

-(defun undo-make-selective-list (start end)
-  "Return a list of undo elements for the region START to END.
-The elements come from `buffer-undo-list', but we keep only the
-elements inside this region, and discard those outside this
-region.  The elements' positions are adjusted so as the returned
-list can be applied to the current buffer."
+(defun undo-make-regional-generator (start end)
+  "Make a closure that will return the next undo element
+association in the region START to END each time it is called, in
+the form (ADJUSTED-ELT . ORIG-UNDO-LIST).  ADJUSTED-ELT is an
+undo element with adjusted positions and ORIG-UNDO-LIST is a cons
+of buffer-undo-list whose car is the original unadjusted undo
+element.  ADJUSTED-ELT may or may not be eq to (car
+ORIG-UNDO-LIST).
+
+The use of a closure allows for lazy adjustment of elements of
+the buffer-undo-list as needed for successive undo commands."
   (let ((ulist buffer-undo-list)
-        ;; A list of position adjusted undo elements in the region.
-        (selective-list (list nil))
+        ;; (ADJUSTED-ELT . ORIG-UNDO-LIST) associations to be returned
+        ;; from closure
+        (selective-list (list (cons nil nil)))
+        prev-assoc
         ;; A list of undo-deltas for out of region undo elements.
-        undo-deltas
-        undo-elt)
-    (while ulist
-      (setq undo-elt (car ulist))
+        undo-deltas)
+    (lambda (&optional option)
+      ;; Update selective-list with potential returns if necessary
+      (while (and ulist (not selective-list))
+        (let ((undo-elt (car ulist)))
           (cond
            ((null undo-elt)
-        ;; Don't put two nils together in the list
-        (when (car selective-list)
-          (push nil selective-list)))
+            ;; Don't put two undo boundaries, represented as (nil
+            ;; . nil), together in the list
+            (unless (equal (cons nil nil) prev-assoc)
+              (push (cons nil nil) selective-list)))
            ((and (consp undo-elt) (eq (car undo-elt) t))
             ;; This is a "was unmodified" element.  Keep it
             ;; if we have kept everything thus far.
             (when (not undo-deltas)
-          (push undo-elt selective-list)))
+              (push (cons undo-elt ulist) selective-list)))
            ;; Skip over marker adjustments, instead relying
            ;; on finding them after (TEXT . POS) elements
            ((markerp (car-safe undo-elt))
@@ -2458,19 +2491,37 @@ list can be applied to the current buffer."
               (if (undo-elt-in-region adjusted-undo-elt start end)
                   (progn
                     (setq end (+ end (cdr (undo-delta adjusted-undo-elt))))
-                (push adjusted-undo-elt selective-list)
+                    (push (cons adjusted-undo-elt ulist) selective-list)
                     ;; Keep (MARKER . ADJUSTMENT) if their (TEXT . POS) was
                     ;; kept.  primitive-undo may discard them later.
                     (when (and (stringp (car-safe adjusted-undo-elt))
                                (integerp (cdr-safe adjusted-undo-elt)))
                       (let ((list-i (cdr ulist)))
                         (while (markerp (car-safe (car list-i)))
-                      (push (pop list-i) selective-list)))))
+                          (let ((marker-adj (pop list-i)))
+                            (push (cons marker-adj marker-adj)
+                                  selective-list))))
+                      (setq selective-list (nreverse selective-list))))
                 (let ((delta (undo-delta undo-elt)))
                   (when (/= 0 (cdr delta))
-                (push delta undo-deltas)))))))
+                    (push delta undo-deltas))))))))
         (pop ulist))
+      (if (eq option 'peek)
+          (car selective-list)
+        (setq prev-assoc (pop selective-list))))))
+
+(defun undo-make-selective-list (start end)
+  "Realize a full selective undo list per
+undo-make-regional-generator."
+  (let ((selective-list nil)
+        (gen (undo-make-regional-generator start end))
+        elt)
+    (while (setq elt (funcall gen))
+      (push selective-list (car elt)))
     (nreverse selective-list)))
+(make-obsolete 'undo-make-selective-list
+               "Use undo-make-regional-generator instead."
+               "24.5")

 (defun undo-elt-in-region (undo-elt start end)
   "Determine whether UNDO-ELT falls inside the region START ... END.

bug#16411: undo-only bugs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 208 bytes --]

> 1: undo-only in region doesn't work.

+2014-05-13 Stefan Monnier <monnier@iro.umontreal.ca>
+
+ * simple.el (undo-make-selective-list): Obey undo-no-redo.

Right, this one didn't need the refactor. Thanks.

[-- Attachment #2: Type: text/html, Size: 319 bytes --]

bug#16411: undo-only bugs

[Stefan Monnier]

>    1: undo-only in region doesn't work.

At least this should be working now.


        Stefan

bug#16411: undo-only bugs

[Stefan Monnier]

> Item 1 is the crucial one. The undo-redo-table is somewhat like
> undo-equiv-table, except that instead of mapping equal buffer states,
> it maps undo elements to what they undid.

I'm having trouble understanding it (I guess it's just that my mind
i caught in a rut, after having come up with undo-equiv-table).

> +(defvar undo-redo-table (make-hash-table :test 'eq :weakness t)
> +  "Hash table mapping undo elements created by an undo command to
> +the undo element they undid.  Specifically, the keys and values
> +are eq to cons of buffer-undo-list.  The hash table is weak so as
> +truncated undo elements can be garbage collected.")

[ Nitpick: the first line of the docstring should stand on its own.  ]
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.

It's hard for me to really understand how this undo-redo-table would work
without seeing it in use.

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).
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, but I guess that since undo-in-region is fast
enough, that won't be a problem.


        Stefan

bug#16411: undo-only bugs

[Stefan Monnier]

> Having undo elements reference what they undid would help solve
> several issues:

>    1: undo-only in region doesn't work.
>    2: Normal undo-only after an undo in region doesn't work. I've
>       previously outlined how the solution would use the
>       undo-redo-table.
>    3: Undo in region has counter intuitive behavior as described in
>       the FIXME of simple.el describing undo in region.
>    4: Deleting X bytes, then doing Y iterations of undo and redo
>       causes undo history to grow about X*Y. To grow proportional to Y
>       should be achievable: set undo-in-progress to the in progress
>       element, and the C level undo recording to use it and
>       undo-redo-table to find the eq Lisp_String.
>    5: Undo Tree should more tightly integrate with the builtin undo
>       system. To do so, it needs sufficient information to visualize
>       the buffer-undo-list as a tree. Undo Tree has a means to
>       visualize undo in regions, so undo-equiv-table is inadequate.

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.

> There are variations on how elements could reference what they undid,
> but fundamentally I think it is essential. I wish to know how you like
> the direction the patch is going as I proceed to solve some problems
> building upon it.

I think we should try to keep the "one entry per undo boundary" rather
than go for "one entry per undo element".

> The reason undo-redo-table maps at the element level, as opposed to
> the change group level, is because in the case of undo in region with
> a prefix arg, the newly created change group needs to reference
> subsets of potentially many prior change groups.

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.


        Stefan

bug#16411: undo-only bugs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 3596 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 4100 bytes --]

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

bug#16411: undo-only bugs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 1037 bytes --]

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

Happens to me all the time.

> If anything should be done with it, I think it'd be to *cut* the
> extra undo/redo pairs.

No complaint from me. That would change the behavior of ordinary undo
command, which you just said you don't want to change.

> I'm not completely convinced that this generator is worthwhile

Ok, I'll lose it then.

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

You actually want me to do that? That is: wrap every referenced
element in a size 1 weak hash table. Are you sure that gives the
memory savings over the element level mapping of the undo-redo-table
in the patch?

[-- Attachment #2: Type: text/html, Size: 1239 bytes --]

bug#16411: undo-only bugs

[Stefan Monnier]

>> If anything should be done with it, I think it'd be to *cut* the
>> extra undo/redo pairs.
> No complaint from me.   That would change the behavior of ordinary undo
> command,

Yes.  And I think that's what we want: as a user, having to wade through
N repetitions of redo/undo is a pain.  Those that suffer often from it
probably switched to undo-tree.

The idea of cutting the extra undo-redo pairs follows the following
principle: an undo-redo pair gives you access to 1 past buffer state,
but if the earlier undo elements already made you go through an
identical state, then this undo-redo pair is superfluous.

I'm sure this can be generalized for undo-in-region (where an undo-redo
pair may not bring you exactly to the same state, but still gives you
access to a change you've already seen earlier in the undo list), but
I'm sure you can define it more easily than I.

> which you just said you don't want to change.

So far there was no discussion of changing behavior: only fixing bugs
and changing implementation.

>> I'm not completely convinced that this generator is worthwhile
> Ok, I'll lose it then.

We may want to (re)introduce it later, tho.

>>> 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.
> You actually want me to do that? That is: wrap every referenced
> element in a size 1 weak hash table.

God no!  I'm saying that I agree with your justification for the design of
undo-redo-table keeping mappings for every undo-element rather than one
per undo group; but that you need to put a comment in the code
explaining why it's done this way.


        Stefan

bug#16411: undo-only bugs

[Barry OReilly]

[-- Attachment #1.1: Type: text/plain, Size: 601 bytes --]

I have attached a patch against trunk which omits the generators,
changes the data format of pending-undo-list, and addresses other
comments. The undo-tests pass with this patch. As with the last
patch, it doesn't solve an actual bug yet, but that is
forthcoming.

Since undo-tree uses primitive-undo, I think it must remain
compatible. To do this and not duplicate code, I split individual
element logic out to an undo-primitive-elt function and moved the
look ahead at marker adjustments to undo-more. Since the latter
is recent functionality, I doubt undo-tree relies on
primitive-undo doing that.

[-- Attachment #1.2: Type: text/html, Size: 672 bytes --]

[-- Attachment #2: undone-undos.diff --]
[-- Type: text/plain, Size: 24516 bytes --]

diff --git a/lisp/simple.el b/lisp/simple.el
index af8e47c..9b47ccb 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -2054,20 +2054,50 @@ Go to the history element by the absolute history position HIST-POS."
 ;Put this on C-x u, so we can force that rather than C-_ into startup msg
 (define-obsolete-function-alias 'advertised-undo 'undo "23.2")
 
+;; Note: We considered a design whereby one entry in the
+;; undo-redo-table maps a change group to a list of undone elements or
+;; groups.  This design does not work because the value stored in
+;; undo-redo-table would need to be a non weak list with weak
+;; references into buffer-undo-list.  Currently Elisp only features
+;; weak references when they are directly keys or values of a weak
+;; hash table, so a list containing weak references is not supported.
+(defvar undo-redo-table (make-hash-table :test 'eq :weakness t)
+  "Hash table mapping undos to what they undid.
+
+Specifically, the keys and values are eq to a cons of
+buffer-undo-list such that the car of the key is an undo element
+and the car of the value is the undone element.
+
+The hash table is weak so as truncated undo elements can be
+garbage collected.")
 (defconst undo-equiv-table (make-hash-table :test 'eq :weakness t)
   "Table mapping redo records to the corresponding undo one.
 A redo record for undo-in-region maps to t.
 A redo record for ordinary undo maps to the following (earlier) undo.")
+(make-obsolete-variable
+ 'undo-equiv-table
+ "Use undo-redo-table instead.  For non regional undos, (gethash
+k undo-equiv-table) is the same as taking (gethash k
+undo-redo-table) and scanning forward one change group."
+ "24.5")
 
 (defvar undo-in-region nil
-  "Non-nil if `pending-undo-list' is not just a tail of `buffer-undo-list'.")
+  "Non-nil during an undo in region.")
 
 (defvar undo-no-redo nil
   "If t, `undo' doesn't go through redo entries.")
 
 (defvar pending-undo-list nil
-  "Within a run of consecutive undo commands, list remaining to be undone.
-If t, we undid all the way to the end of it.")
+  "The pending undo elements in a run of consecutive undo commands.
+
+Specifically, this is a list of assocations of the
+form (ADJUSTED-ELT . ORIG-UNDO-LIST).  ADJUSTED-ELT is an undo
+element with adjusted positions and ORIG-UNDO-LIST is a cons of
+buffer-undo-list whose car is the original unadjusted undo
+element.  ADJUSTED-ELT may or may not be eq to (car
+ORIG-UNDO-LIST).
+
+If t, there is no more to undo.")
 
 (defun undo (&optional arg)
   "Undo some previous changes.
@@ -2115,9 +2145,8 @@ as an argument limits undo to changes within the current region."
       (undo-more 1))
     ;; If we got this far, the next command should be a consecutive undo.
     (setq this-command 'undo)
-    ;; Check to see whether we're hitting a redo record, and if
-    ;; so, ask the user whether she wants to skip the redo/undo pair.
-    (let ((equiv (gethash pending-undo-list undo-equiv-table)))
+    ;; Check to see whether we're hitting a redo record
+    (let ((equiv (gethash (cdr-safe pending-undo-list) undo-equiv-table)))
       (or (eq (selected-window) (minibuffer-window))
 	  (setq message (format "%s%s!"
                                 (if (or undo-no-redo (not equiv))
@@ -2128,7 +2157,7 @@ as an argument limits undo to changes within the current region."
 	;; undo-redo-undo-redo-... so skip to the very last equiv.
 	(while (let ((next (gethash equiv undo-equiv-table)))
 		 (if next (setq equiv next))))
-	(setq pending-undo-list equiv)))
+	(setq pending-undo-list (cons (car equiv) equiv))))
     (undo-more
      (if (numberp arg)
 	 (prefix-numeric-value arg)
@@ -2138,18 +2167,20 @@ as an argument limits undo to changes within the current region."
     ;; In the ordinary case (not within a region), map the redo
     ;; record to the following undos.
     ;; I don't know how to do that in the undo-in-region case.
-    (let ((list buffer-undo-list))
+    (let ((list buffer-undo-list)
+          (new-equiv (cdr-safe pending-undo-list)))
       ;; Strip any leading undo boundaries there might be, like we do
       ;; above when checking.
       (while (eq (car list) nil)
 	(setq list (cdr list)))
-      (puthash list
-               ;; Prevent identity mapping.  This can happen if
-               ;; consecutive nils are erroneously in undo list.
-               (if (or undo-in-region (eq list pending-undo-list))
-                   t
-                 pending-undo-list)
-	       undo-equiv-table))
+      (when new-equiv
+        (puthash list
+                 ;; Prevent identity mapping.  This can happen if
+                 ;; consecutive nils are erroneously in undo list.
+                 (if (or undo-in-region (eq list new-equiv))
+                     t
+                   new-equiv)
+                 undo-equiv-table)))
     ;; Don't specify a position in the undo record for the undo command.
     ;; Instead, undoing this should move point to where the change is.
     (let ((tail buffer-undo-list)
@@ -2202,145 +2233,152 @@ Some change-hooks test this variable to do something different.")
   "Undo back N undo-boundaries beyond what was already undone recently.
 Call `undo-start' to get ready to undo recent changes,
 then call `undo-more' one or more times to undo them."
-  (or (listp pending-undo-list)
-      (user-error (concat "No further undo information"
-                          (and undo-in-region " for region"))))
-  (let ((undo-in-progress t))
-    ;; Note: The following, while pulling elements off
-    ;; `pending-undo-list' will call primitive change functions which
-    ;; will push more elements onto `buffer-undo-list'.
-    (setq pending-undo-list (primitive-undo n pending-undo-list))
-    (if (null pending-undo-list)
-	(setq pending-undo-list t))))
+  (when (eq pending-undo-list t)
+    (user-error (concat "No further undo information"
+                        (and undo-in-region " for region"))))
+  (let ((undo-in-progress t)
+        (group n)
+        assoc)
+    (while (> group 0)
+      (while (car (setq assoc (pop pending-undo-list)))
+        (let ((elt (car assoc))
+              (orig-tail (cdr assoc))
+              valid-marker-adjustments)
+          (when (and (stringp (car-safe elt))
+                     (integerp (cdr-safe elt)))
+            ;; Check that marker adjustments which were recorded with
+            ;; the (STRING . POS) record are still valid, ie the
+            ;; markers haven't moved.  We check their validity before
+            ;; reinserting the string so as we don't need to mind
+            ;; marker insertion-type.
+            (while (and (markerp (car-safe (caar pending-undo-list)))
+                        (integerp (cdr-safe (caar pending-undo-list))))
+              (let* ((marker-adj (car (pop pending-undo-list)))
+                     (m (car marker-adj)))
+                (and (eq (marker-buffer m) (current-buffer))
+                     (= (cdr elt) m)
+                     (push marker-adj valid-marker-adjustments)))))
+          (when (markerp (car-safe elt))
+            ;; Note: even though these elements are not expected in
+            ;; the undo list, adjust them to be conservative for the
+            ;; 24.4 release.  (Bug#16818)
+            (warn "Encountered %S entry in undo list with no matching (TEXT . POS) entry"
+                  elt))
+          ;; Note: The following changes the buffer, and so calls
+          ;; primitive change functions that push more elements onto
+          ;; `buffer-undo-list'.
+          (when (undo-primitive-elt elt)
+            ;; Map the new undo element to what it undid.  Not aware
+            ;; yet of cases where we want to map all new elements.
+            (puthash buffer-undo-list orig-tail undo-redo-table))
+          ;; Adjust the valid marker adjustments
+          (dolist (adj valid-marker-adjustments)
+            (undo-primitive-elt adj))))
+      (setq group (1- group)))
+    ;; Reached the end of undo history
+    (unless pending-undo-list (setq pending-undo-list t))))
 
 (defun primitive-undo (n list)
-  "Undo N records from the front of the list LIST.
+  "Undo N change groups from the front of the list LIST.
 Return what remains of the list."
+  (let ((arg n)
+        (next nil))
+    (while (> arg 0)
+      (while (setq next (pop list))     ;Exit inner loop at undo boundary.
+        (undo-primitive-elt next))
+      (setq arg (1- arg)))))
 
-  ;; This is a good feature, but would make undo-start
-  ;; unable to do what is expected.
-  ;;(when (null (car (list)))
-  ;;  ;; If the head of the list is a boundary, it is the boundary
-  ;;  ;; preceding this command.  Get rid of it and don't count it.
-  ;;  (setq list (cdr list))))
+(defun undo-primitive-elt (next)
+  "Undo the element NEXT and return non nil if changes were made.
 
-  (let ((arg n)
-        ;; In a writable buffer, enable undoing read-only text that is
+NEXT is one of the valid forms documented in the Undo section of
+the Elisp manual."
+  (let (;; In a writable buffer, enable undoing read-only text that is
         ;; so because of text properties.
         (inhibit-read-only t)
         ;; Don't let `intangible' properties interfere with undo.
         (inhibit-point-motion-hooks t)
         ;; We use oldlist only to check for EQ.  ++kfs
-        (oldlist buffer-undo-list)
-        (did-apply nil)
-        (next nil))
-    (while (> arg 0)
-      (while (setq next (pop list))     ;Exit inner loop at undo boundary.
-        ;; Handle an integer by setting point to that value.
-        (pcase next
-          ((pred integerp) (goto-char next))
-          ;; Element (t . TIME) records previous modtime.
-          ;; Preserve any flag of NONEXISTENT_MODTIME_NSECS or
-          ;; UNKNOWN_MODTIME_NSECS.
-          (`(t . ,time)
-           ;; If this records an obsolete save
-           ;; (not matching the actual disk file)
-           ;; then don't mark unmodified.
-           (when (or (equal time (visited-file-modtime))
-                     (and (consp time)
-                          (equal (list (car time) (cdr time))
-                                 (visited-file-modtime))))
-             (when (fboundp 'unlock-buffer)
-               (unlock-buffer))
-             (set-buffer-modified-p nil)))
-          ;; Element (nil PROP VAL BEG . END) is property change.
-          (`(nil . ,(or `(,prop ,val ,beg . ,end) pcase--dontcare))
-           (when (or (> (point-min) beg) (< (point-max) end))
-             (error "Changes to be undone are outside visible portion of buffer"))
-           (put-text-property beg end prop val))
-          ;; Element (BEG . END) means range was inserted.
-          (`(,(and beg (pred integerp)) . ,(and end (pred integerp)))
-           ;; (and `(,beg . ,end) `(,(pred integerp) . ,(pred integerp)))
-           ;; Ideally: `(,(pred integerp beg) . ,(pred integerp end))
-           (when (or (> (point-min) beg) (< (point-max) end))
-             (error "Changes to be undone are outside visible portion of buffer"))
-           ;; Set point first thing, so that undoing this undo
-           ;; does not send point back to where it is now.
-           (goto-char beg)
-           (delete-region beg end))
-          ;; Element (apply FUN . ARGS) means call FUN to undo.
-          (`(apply . ,fun-args)
-           (let ((currbuff (current-buffer)))
-             (if (integerp (car fun-args))
-                 ;; Long format: (apply DELTA START END FUN . ARGS).
-                 (pcase-let* ((`(,delta ,start ,end ,fun . ,args) fun-args)
-                              (start-mark (copy-marker start nil))
-                              (end-mark (copy-marker end t)))
-                   (when (or (> (point-min) start) (< (point-max) end))
-                     (error "Changes to be undone are outside visible portion of buffer"))
-                   (apply fun args) ;; Use `save-current-buffer'?
-                   ;; Check that the function did what the entry
-                   ;; said it would do.
-                   (unless (and (= start start-mark)
-                                (= (+ delta end) end-mark))
-                     (error "Changes to be undone by function different than announced"))
-                   (set-marker start-mark nil)
-                   (set-marker end-mark nil))
-               (apply fun-args))
-             (unless (eq currbuff (current-buffer))
-               (error "Undo function switched buffer"))
-             (setq did-apply t)))
-          ;; Element (STRING . POS) means STRING was deleted.
-          (`(,(and string (pred stringp)) . ,(and pos (pred integerp)))
-           (when (let ((apos (abs pos)))
-                   (or (< apos (point-min)) (> apos (point-max))))
-             (error "Changes to be undone are outside visible portion of buffer"))
-           (let (valid-marker-adjustments)
-             ;; Check that marker adjustments which were recorded
-             ;; with the (STRING . POS) record are still valid, ie
-             ;; the markers haven't moved.  We check their validity
-             ;; before reinserting the string so as we don't need to
-             ;; mind marker insertion-type.
-             (while (and (markerp (car-safe (car list)))
-                         (integerp (cdr-safe (car list))))
-               (let* ((marker-adj (pop list))
-                      (m (car marker-adj)))
-                 (and (eq (marker-buffer m) (current-buffer))
-                      (= pos m)
-                      (push marker-adj valid-marker-adjustments))))
-             ;; Insert string and adjust point
-             (if (< pos 0)
-                 (progn
-                   (goto-char (- pos))
-                   (insert string))
-               (goto-char pos)
-               (insert string)
-               (goto-char pos))
-             ;; Adjust the valid marker adjustments
-             (dolist (adj valid-marker-adjustments)
-               (set-marker (car adj)
-                           (- (car adj) (cdr adj))))))
-          ;; (MARKER . OFFSET) means a marker MARKER was adjusted by OFFSET.
-          (`(,(and marker (pred markerp)) . ,(and offset (pred integerp)))
-           (warn "Encountered %S entry in undo list with no matching (TEXT . POS) entry"
-                 next)
-           ;; Even though these elements are not expected in the undo
-           ;; list, adjust them to be conservative for the 24.4
-           ;; release.  (Bug#16818)
-           (when (marker-buffer marker)
-             (set-marker marker
-                         (- marker offset)
-                         (marker-buffer marker))))
-          (_ (error "Unrecognized entry in undo list %S" next))))
-      (setq arg (1- arg)))
-    ;; Make sure an apply entry produces at least one undo entry,
-    ;; so the test in `undo' for continuing an undo series
-    ;; will work right.
-    (if (and did-apply
-             (eq oldlist buffer-undo-list))
-        (setq buffer-undo-list
-              (cons (list 'apply 'cdr nil) buffer-undo-list))))
-  list)
+        (oldlist buffer-undo-list))
+    ;; Handle an integer by setting point to that value.
+    (pcase next
+      ((pred integerp) (goto-char next))
+      ;; Element (t . TIME) records previous modtime.
+      ;; Preserve any flag of NONEXISTENT_MODTIME_NSECS or
+      ;; UNKNOWN_MODTIME_NSECS.
+      (`(t . ,time)
+       ;; If this records an obsolete save
+       ;; (not matching the actual disk file)
+       ;; then don't mark unmodified.
+       (when (or (equal time (visited-file-modtime))
+                 (and (consp time)
+                      (equal (list (car time) (cdr time))
+                             (visited-file-modtime))))
+         (when (fboundp 'unlock-buffer)
+           (unlock-buffer))
+         (set-buffer-modified-p nil)))
+      ;; Element (nil PROP VAL BEG . END) is property change.
+      (`(nil . ,(or `(,prop ,val ,beg . ,end) pcase--dontcare))
+       (when (or (> (point-min) beg) (< (point-max) end))
+         (error "Changes to be undone are outside visible portion of buffer"))
+       (put-text-property beg end prop val))
+      ;; Element (BEG . END) means range was inserted.
+      (`(,(and beg (pred integerp)) . ,(and end (pred integerp)))
+       ;; (and `(,beg . ,end) `(,(pred integerp) . ,(pred integerp)))
+       ;; Ideally: `(,(pred integerp beg) . ,(pred integerp end))
+       (when (or (> (point-min) beg) (< (point-max) end))
+         (error "Changes to be undone are outside visible portion of buffer"))
+       ;; Set point first thing, so that undoing this undo
+       ;; does not send point back to where it is now.
+       (goto-char beg)
+       (delete-region beg end))
+      ;; Element (apply FUN . ARGS) means call FUN to undo.
+      (`(apply . ,fun-args)
+       (let ((currbuff (current-buffer)))
+         (if (integerp (car fun-args))
+             ;; Long format: (apply DELTA START END FUN . ARGS).
+             (pcase-let* ((`(,delta ,start ,end ,fun . ,args) fun-args)
+                          (start-mark (copy-marker start nil))
+                          (end-mark (copy-marker end t)))
+               (when (or (> (point-min) start) (< (point-max) end))
+                 (error "Changes to be undone are outside visible portion of buffer"))
+               (apply fun args) ;; Use `save-current-buffer'?
+               ;; Check that the function did what the entry
+               ;; said it would do.
+               (unless (and (= start start-mark)
+                            (= (+ delta end) end-mark))
+                 (error "Changes to be undone by function different than announced"))
+               (set-marker start-mark nil)
+               (set-marker end-mark nil))
+           (apply fun-args))
+         (unless (eq currbuff (current-buffer))
+           (error "Undo function switched buffer"))
+         ;; Make sure an apply entry produces at least one undo entry,
+         ;; so the test in `undo' for continuing an undo series
+         ;; will work right.
+         (when (eq oldlist buffer-undo-list)
+           (push (list 'apply 'cdr nil) buffer-undo-list))))
+      ;; Element (STRING . POS) means STRING was deleted.
+      (`(,(and string (pred stringp)) . ,(and pos (pred integerp)))
+       (when (let ((apos (abs pos)))
+               (or (< apos (point-min)) (> apos (point-max))))
+         (error "Changes to be undone are outside visible portion of buffer"))
+       ;; Insert string and adjust point
+       (if (< pos 0)
+           (progn
+             (goto-char (- pos))
+             (insert string))
+         (goto-char pos)
+         (insert string)
+         (goto-char pos)))
+      ;; (MARKER . OFFSET) means a marker MARKER was adjusted by OFFSET.
+      (`(,(and marker (pred markerp)) . ,(and offset (pred integerp)))
+       (when (marker-buffer marker)
+         (set-marker marker
+                     (- marker offset)
+                     (marker-buffer marker))))
+      (_ (error "Unrecognized entry in undo list %S" next)))
+    (not (eq oldlist buffer-undo-list))))
 
 ;; Deep copy of a list
 (defun undo-copy-list (list)
@@ -2353,17 +2391,22 @@ Return what remains of the list."
     elt))
 
 (defun undo-start (&optional beg end)
-  "Set `pending-undo-list' to the front of the undo list.
-The next call to `undo-more' will undo the most recently made change.
-If BEG and END are specified, then only undo elements
-that apply to text between BEG and END are used; other undo elements
-are ignored.  If BEG and END are nil, all undo elements are used."
+  "Set `pending-undo-list' to begin a run of undos.  The next
+call to `undo-more' will undo the next change group.  If BEG and
+END are specified, then only undo elements that apply to text
+between BEG and END are used; other undo elements are ignored.
+If BEG and END are nil, all undo elements are used."
   (if (eq buffer-undo-list t)
       (user-error "No undo information in this buffer"))
   (setq pending-undo-list
 	(if (and beg end (not (= beg end)))
-	    (undo-make-selective-list (min beg end) (max beg end))
-	  buffer-undo-list)))
+	    (undo-make-regional-list (min beg end) (max beg end))
+          (let ((list-i buffer-undo-list)
+                assoc-list)
+            (while list-i
+              (push (cons (car list-i) list-i) assoc-list)
+              (pop list-i))
+            (nreverse assoc-list)))))
 
 ;; The positions given in elements of the undo list are the positions
 ;; as of the time that element was recorded to undo history.  In
@@ -2424,15 +2467,17 @@ are ignored.  If BEG and END are nil, all undo elements are used."
 ;; "ccaabad", as though the first "d" became detached from the
 ;; original "ddd" insertion.  This quirk is a FIXME.
 
-(defun undo-make-selective-list (start end)
-  "Return a list of undo elements for the region START to END.
-The elements come from `buffer-undo-list', but we keep only the
-elements inside this region, and discard those outside this
-region.  The elements' positions are adjusted so as the returned
-list can be applied to the current buffer."
+(defun undo-make-regional-list (start end)
+  "Return a list of undo associations for the region START to END,
+
+The undo associations are of the form (ADJUSTED-ELT
+. ORIG-UNDO-LIST) and are as documented for
+pending-undo-list. Only associations for elements lying inside
+the region are included. Their positions are adjusted based on
+the discarded elements not fully in the region."
   (let ((ulist buffer-undo-list)
-        ;; A list of position adjusted undo elements in the region.
-        (selective-list (list nil))
+        ;; The list of (ADJUSTED-ELT . ORIG-UNDO-LIST) to return
+        (selective-list (list (cons nil nil)))
         ;; A list of undo-deltas for out of region undo elements.
         undo-deltas
         undo-elt)
@@ -2443,14 +2488,16 @@ list can be applied to the current buffer."
       (setq undo-elt (car ulist))
       (cond
        ((null undo-elt)
-        ;; Don't put two nils together in the list
-        (when (car selective-list)
-          (push nil selective-list)))
+        (let (;; Undo boundary representation
+              (boundary (cons nil nil)))
+          ;; Don't put two undo boundaries together in the list
+          (unless (equal boundary (car selective-list))
+            (push boundary selective-list))))
        ((and (consp undo-elt) (eq (car undo-elt) t))
         ;; This is a "was unmodified" element.  Keep it
         ;; if we have kept everything thus far.
         (when (not undo-deltas)
-          (push undo-elt selective-list)))
+          (push (cons undo-elt ulist) selective-list)))
        ;; Skip over marker adjustments, instead relying
        ;; on finding them after (TEXT . POS) elements
        ((markerp (car-safe undo-elt))
@@ -2461,20 +2508,30 @@ list can be applied to the current buffer."
           (if (undo-elt-in-region adjusted-undo-elt start end)
               (progn
                 (setq end (+ end (cdr (undo-delta adjusted-undo-elt))))
-                (push adjusted-undo-elt selective-list)
+                (push (cons adjusted-undo-elt ulist) selective-list)
                 ;; Keep (MARKER . ADJUSTMENT) if their (TEXT . POS) was
                 ;; kept.  primitive-undo may discard them later.
                 (when (and (stringp (car-safe adjusted-undo-elt))
                            (integerp (cdr-safe adjusted-undo-elt)))
                   (let ((list-i (cdr ulist)))
                     (while (markerp (car-safe (car list-i)))
-                      (push (pop list-i) selective-list)))))
+                      (let ((marker-adj (pop list-i)))
+                        (push (cons marker-adj marker-adj)
+                              selective-list))))))
             (let ((delta (undo-delta undo-elt)))
               (when (/= 0 (cdr delta))
                 (push delta undo-deltas)))))))
       (pop ulist))
     (nreverse selective-list)))
 
+(defun undo-make-selective-list (start end)
+  "Realize a full selective undo list per
+undo-make-regional-generator."
+  (mapcar #'car (undo-make-regional-list start end)))
+(make-obsolete 'undo-make-selective-list
+               "Use undo-make-regional-list instead."
+               "24.5")
+
 (defun undo-elt-in-region (undo-elt start end)
   "Determine whether UNDO-ELT falls inside the region START ... END.
 If it crosses the edge, we return nil.

bug#16411: undo-only bugs

[Stefan Monnier]

> +  "The pending undo elements in a run of consecutive undo commands.
> +Specifically, this is a list of assocations of the
> +form (ADJUSTED-ELT . ORIG-UNDO-LIST).  ADJUSTED-ELT is an undo
[...]
> -    (let ((equiv (gethash pending-undo-list undo-equiv-table)))
> +    ;; Check to see whether we're hitting a redo record
> +    (let ((equiv (gethash (cdr-safe pending-undo-list) undo-equiv-table)))

Why take the cdr of pending-undo-list?  IOW why skip the first element?
Oh, and please punctuate your comments.

> -	(setq pending-undo-list equiv)))
> +	(setq pending-undo-list (cons (car equiv) equiv))))

I guess this brings the same question as above.

> +    (let ((list buffer-undo-list)
> +          (new-equiv (cdr-safe pending-undo-list)))

And same here.

> +          (when (undo-primitive-elt elt)
> +            ;; Map the new undo element to what it undid.  Not aware
> +            ;; yet of cases where we want to map all new elements.
> +            (puthash buffer-undo-list orig-tail undo-redo-table))

We should only do that in those cases where undo-equiv-table can't be
used.

Also, why did you have to move the valid-marker-adjustments thingy out
of undo-primitive-elt?


        Stefan