Subject: undo-only bugs

From: Barry OReilly <[email-masked]>
Date: Fri, 10 Jan 2014 17:33:37 -0500

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