Stefan wrote at
http://debbugs.gnu.org/cgi/bugreport.cgi?bug=16411#77 :
> 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.
I agree completely. To achieve this, I believe it is desirable to
integrate undo-tree into Emacs. I have some ideas about doing so.
If one conceives of undo history as a tree, then a run of undo
commands means "retrace my edge traversals". Then if you break that
run, you have to retrace *those* edge traversals.
undo-only means "go to the parent". This follows from the fact
that edits create new nodes downward in the tree. Recursive
lookup in undo-equiv-table doesn't change the node you're
currently on, but does bring you back to the least recent time
that node was reached. That usually means an undo from that
point "retraces the edge traversal" which created the node, thus
taking you to the parent.
I prefer to think of undo-in-region as navigating to a parallel
tree that looks much like the previous, but rejoins it at the
node before the oldest change group undo-in-region drew from.
This conception means each node is a buffer state. undo-tree
models undo-in-region somewhat similarly: it visually duplicates
a "parallel tree" and roots it as described. For some reason that
new tree fragment misses branches, but that might be a bug.
The appeal of undo-tree is that it allows the user to more
intuitively and directly navigate the underlying tree. If the
user wants to reach other branches of the tree using the builtin
undo system, they must retrace their edge traversals, of which
there can be many. This is poorer usability.
Since the builtin undo commands can be thought of in tree terms,
I believe it may be possible for the two systems to coexist. A
consequence of this is that merely traversing edges in the undo
tree would cause undo history to grow. This is one reason I raise
the issue of:
> 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.
But if you're willing to address this concern by eliminating any
requirement for the undo command to retrace edge traversals, that
would be great.
Using the buffer-undo-list and undo-redo-table described in bug
16411 (or undo-equiv-table in the absence of regional undos), it
is in principle possible to construct a tree visualization of the
undo history. It is tempting to construct the tree visualization
straight from this data model, but there is at least one drawback
I would like to describe.
When the buffer-undo-list is truncated, weak references in the
undo-redo-table are removed. This means "redo groups" (change
groups created by an undo command) suddenly look like "edit
groups" (change groups created by a normal editing command). This
would change the structure of the tree at GC time. Consider as an
example:
A
|
|
B
___|___
/ \
E C
|
|
D[Note: This uses undo-tree's convention of newer branches on the
left.]
The user's movement through the tree is:
A edit to B edit to C edit to D undo to C undo to B edit to E
Suppose GC truncates "A edit to B edit to C". Because of removals
of weak references from undo-redo-table, the history looks
like: "C edit to D undo to C edit to B edit to E" (notice
an "undo to" became a "edit to"). Regenerating the tree from this
yields:
C
___|___
/ \
B D
|
|
EThis kind of tree change at seemingly random times might be very
surprising to the user, albeit granted the parent-child reversals
will tend to occur away from the user's local part of the tree.
The alternative and less surprising approach, which undo-tree
takes, is to truncate nodes least recently visited, making no
other tree transformation. So A is first in line for truncation
followed by E, B, C, D. I think this can be done in an integrated
undo-tree, but with greater effort. Do you have a strong opinion
about this, Stefan?
Toby, are there other reasons undo-tree needs to transfer undo
elements from the buffer-undo-list to its own data model?
Finally, I have a couple of questions about the 2010 post at
http://lists.gnu.org/archive/html/emacs-devel/2010-05/msg00036.html
> As far as I understand that code, references to markers in
> `buffer-undo-list' don't count during the mark phase of gc, and
> the sweep phase removes undo entries for markers that have been
> garbage-collected. This special treatment of `buffer-undo-list'
> poses difficulties for any package that messes around with the
> undo system.
Well, most Lisp_Object are marked first, then unmarked markers
are spliced out of the undo list, then the undo list is marked.
It's kind of like a specialized weak reference.
Could you expand on the problem this behavior of GC created for
undo-tree? Since undo-tree transfers undo elements outof
buffer-undo-list and into buffer-undo-tree, the markers would be
marked like everything else in buffer-undo-tree until they become
unreachable because of undo-tree-discard-history. So I don't see
the problem the undo-tree-move-GC-elts-to-pool functionality
solved.
> and (I think) causing deleted markers to be resurrected when
> undoing a changeset containing a marker that should have been
> gc'd.
Could you also expand on this point? Once a marker adjustment is
spliced out of the buffer-undo-list all others with eq marker
also are. I don't see how it can get spliced back in.