Re: Integration of undo-tree in Emacs

[Toby Cubitt]

On Wed, May 28, 2014 at 03:38:56PM -0400, Barry OReilly wrote:
> 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.

Or you could include the undo-tree package as part of Emacs, and document
it in the manual. Then in ~20 years time, you might even be able to
enable it by default (cf. transient-mark-mode) :-)

[snip]

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

More "exactly like this" than "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.

If I remember right, this was by design. Undo-in-region only duplicates
the active branch, rather than the entire subtree. I don't remember if
there was any particularly good reason for this design. Perhaps I felt
that duplicating the entire subtree would make for a needlessly complex
tree. I suspect it would be quite easy to modify undo-tree to do as you
describe: split off a new branch, duplicating the entire subtree.

Also note that, because trees are not symmetric, redo-in-region
necessarily works slightly differently to undo-in-region in undo-tree:
The first redo-in-region duplicates the entire subtree. Subsequent
redo-in-regions extend the branch downwards by pulling off redo changes
that apply to the region. (The alternative would be to have every
redo-in-region duplicate the subtree, but in my view that just serves to
create a needlessly complex tree.)

Undo/redo-in-region with undo-tree is harder to explain than it is to
use. When you use it, it generally does what you'd expect. (Except when
there are bugs -- unfortunately it's both the most complex and least
tested part of the undo-tree code.)

> Since the builtin undo commands can be thought of in tree terms,
> I believe it may be possible for the two systems to coexist.

Probably, but I dread to imagine what the implementation of such a hybrid
monster would look like...

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

Is there much point in allowing both systems to be used simultaneously?
Surely users will want to choose either one or the other? The
implementation and maintenance overhead of designing a system that
simultaneously supports two largely incompatible undo models doesn't seem
worth it to me.

Not to mention to the conceptual confusion of mixing up two undo
models. People find the existing system hard enough to get their heads
around!

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

It's even more tempting to fix the underlying data model :-)

If you're proposing to make major changes to Emacs undo, why not redesign
the underlying data model to fit, instead of bolting it onto what's
already a pretty messy data model that's grown up around a conceptually
completely different undo model?

As you say, "the builtin undo commands can be thought of in tree terms"
anyway, at least if you're prepared to change a few details of how
traditional Emacs undo behaves (as you've already discussed).

> but there is at least one drawback I would like to describe.

[snip discussion of how to discard undo history]

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

Personally, I think trying to bolt a tree structure on top of the
existing data model is going to create a horrendous, unmaintainable mess,
for little gain. But as long as I don't have to implement it: good luck!

> Toby, are there other reasons undo-tree needs to transfer undo
> elements from the buffer-undo-list to its own data model?

I think my main reason was simplicity: if you want to model a tree, it's
simplest to use a tree. The other reason was that undo is deeply embedded
in Emacs (all the way down to c code), and to implement a complete
replacement in Elisp I needed to completely wrest control of undo away
from Emacs.

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

>From memory (and git logs), I think that without this mechanism undo-tree
used to sometimes resurrect dead markers when undoing. A lisp package
might delete a marker from a buffer and drop all references to it,
expecting it to be garbage collected. But because it was referenced from
buffer-undo-tree (a strong reference, rather than the specialized
buffer-undo-list weak reference), the marker never got GCd. Undoing a
changeset containing the deleted marker would then restore the marker. I
remember this created all kinds of havoc with overlays.

In early versions of undo-tree, I simply deleted all marker undo entries
to avoid the problem. (Turns out undoing marker movements is rarely
critical in practice, so this worked reasonably well.) Later, I created
the undo-tree-move-GC-elts-to-pool mechanism to fully fix the issue.

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

But they never get spliced out of buffer-undo-tree, because GC only knows
about buffer-undo-list. In undo-tree, undo entries live in the former,
not the latter.

Toby
-- 
Dr T. S. Cubitt
Royal Society University Research Fellow
Fellow of Churchill College, Cambridge
Centre for Quantum Information
DAMTP, University of Cambridge

email: address@hidden
web:   www.dr-qubit.org