Re: Integration of undo-tree in Emacs

[Toby Cubitt]

Hi Barry,

On Fri, May 30, 2014 at 10:40:44AM -0400, Barry OReilly wrote:
> >> I'm not sure why you say they're largely incompatible.
> 
> > Maybe I overstated it. I meant that treating undos as new changes
> > that can themselves be undone is conceptually very different to
> > treating undos and redos as a way of navigating around a history of
> > buffer states.
> 
> Just think of the undo command as a traversal in a tree. Imagine it is
> called "undo-retrace" instead of "undo", then the two models don't
> seem so incompatible. buffer-undo-list is just a kind of event log of
> buffer changes.

They're still two *conceptually* very different models of undo, and I
maintain that users are not going to want to hold both models in their
heads.

The feedback I've received from undo-tree users falls into one of two
camps: (a) "finally, a sensible undo system for Emacs!", or (b)
"interesting package, but I was happy with the existing Emacs system". As
far as I remember, I've never had anyone ask me if it would be possible
to combine both systems.

I definitely agree with you, integrating the two should is technically
possible: just have tree nodes point to elements in buffer-undo-list. And
then sort out all the finicky details needed to make both models work
seamlessly together without bugs. It's the latter that I predict will be
hard work, and hard to maintain.

I took the easy route, and made undo-tree completely replace the
traditional undo model. If the two are to coexist, how are the two models
of undo going to interact? How will treating redo as "undoing an undo"
interact with treating redo as moving up the tree? How will
history-discarding work well for both models? You'll need to think these
things through very carefully if the two models are going to coexist
nicely.


> Together with the undo-(equiv|redo)-table it conveys sufficient
> information to construct a tree.

Ugh. Personally I find it very hard to get my head around
undo-(equiv|redo)-table, even if it in principle conveys sufficient
information to reconstruct the tree. I find it much easier to get my head
around buffer-undo-tree, which *is* a tree!

If you want to integrate undo-tree into Emacs, whilst also keeping the
traditional undo system (presumably an essential requirement), why not
keep the elegant and conceptually simple (biased personal opinion :-)
`buffer-undo-tree's data structure, but make the nodes point to the
appropriate changesets in buffer-undo-list?

With access to the undo code implement in c, it should be quite
straightforward to make this work properly, as you can overcome the
problems I faced (and ducked) with trying to do it all from Elisp.

That way most of the undo-tree code, including all the tree-related
features, will work unchanged or with very minor changes.

Reimplementing undo-tree from scratch on top of undo-(equiv|redo)-table
smacks a little of NIH syndrome to me.

> The usefulness of integrating something like undo-tree is in
> visualizing the tree and providing commands to more capably and
> intuitively traverse it (eg choosing exactly which branch to descend).

That's the main usefulness as you see it. That's definitely not the main
usefulness I experience using undo-tree, and I'm not convinced most
long-term undo-tree users would agree with you. True, most of them start
off thinking the tree visualisation is really cool. But if my own
experience is anything to go by, after the initial tree visualizer "wow"
factor, in practice the most useful thing is being able to undo and redo
as separate operations, without all the "breaking the undo chain"
shenanigans.

The undo tree is nice to have on the rare occasions one wants to recover
history from another branch. It's nice to know that history is still
there, even with the undo/redo model. But even I probably make use of the
undo-tree visualizer less than once a week (and I do all my text editing
in Emacs). Whereas I use undo-tree-redo all the time.

> >>> 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.
> 
> >> Sounds like bug 16818, which affected the builtin undo system too.
> >> It is fixed in the upcoming Emacs 24.4.
> 
> > I'm not sure. I remember it affected normal undo-tree undo, not
> > undo-in-region (which I hadn't even implemented at the time).
> 
> The bug isn't specific to undo in region. It merely lent itself to
> demonstrating the bug, because the mark and region overlay markers are
> necessarily in the region, and so are swept up into marker
> adjustments. They also remain eq over time whilst mutating to point to
> various locations.
> 
> The problem was that primitive-undo applied marker adjustments without
> concern for whether they moved to unrelated locations. Maybe this
> somehow contributed to the overlay havoc you had seen.
>
> The vast majority of Elisp packages shouldn't care whether GC is going
> to happen sooner or later. So if you think the early removal of marker
> adjustments via compact_undo_list is essential to correct functioning,
> I would wonder why a package depends on that.

I think you're still missing the main point I was making. Because
buffer-undo-tree isn't treated specially by GC, even unreferenced
*deleted* markers (e.g. from `delete-overlay') continued to exist in the
undo-tree. Undoing a changeset containing a marker-update entry for one
of those deleted markers would resurrect the deleted marker, recreating
overlays, and causing general havoc.

Perhaps this issue also occurs/occurred with standard undo and
buffer-undo-list.  But it was made far worse in undo-tree because
unreferenced deleted markers were kept alive forever. Moving them into
the gc-pool, so that undo-tree only creates a weak-reference to them,
restores the standard marker GC behaviour.

All that said, there's absolutely nothing to prevent the buffer-undo-list
behaviour from being replicated for the undo tree implementation if
you're implementing it in core Emacs. The whole undo-tree GC-elts pool
mechanism was only necessary because I wanted to implement undo-tree as
an Elisp package, without patching any c code.

> >> undo-tree may require an analagous change, since it doesn't use
> >> undo-make-selective-list.
> 
> > Thanks. Either that function didn't exist when I wrote the
> > undo-in-region support, or I overlooked it. It ought to simplify
> > undo-tree's undo-in-region implementation a little. Currently it
> > constructs the region changeset manually using undo-elt-in-region.
> 
> There have been a few changes in that area, eg under bug 17235, and
> there will be more under bug 16411.

Thanks. I'll take a look when I find time.

Best wishes,
Toby



> On Thu, May 29, 2014 at 2:04 PM, Toby Cubitt <address@hidden> wrote:
> 
> > On Wed, May 28, 2014 at 10:57:15PM -0400, Barry OReilly wrote:
> > > Thanks for your reply, Toby. I appreciate your wisdom on this topic.
> >
> > A modicum of experience, perhaps. Not sure about wisdom!
> >
> > > > Perhaps I felt that duplicating the entire subtree would make for a
> > > > needlessly complex tree.
> > >
> > > I find one limitation in undo-tree is that a buffer state that was two
> > > edges away becomes an arbitrary number of edges away, because
> > > undo in region reaches arbitrarily far back.
> >
> > undo-tree-selection-mode might help with that (hit "s" in the visualizer,
> > then use the motion keybindings).
> >
> > But as I said, I can't remember a clear rational for not duplicating the
> > entire tree, and I believe it would be very easy to do so. Perhaps I'll
> > make the change in a future release.
> >
> > > Alternatively, after an undo in region, you could display it like:
> > >
> > >   |
> > >   |
> > >   A'
> > >   |\…
> > >   |
> > >
> > > Literally with the ellipsis. Traversing that edge would take you back
> > > to the parallel tree you came from:
> > >
> > >   | …
> > >   |/
> > >   A
> > >   |
> > >   |
> >
> > I prefer to keep things simple. They generally work better that way.
> >
> > > The parallel trees look the same after all. I don't think the user
> > > usually cares where is the root at which they join together, although
> > > there are probably ways to display that.
> > >
> > > > The implementation and maintenance overhead of designing a system
> > > > that simultaneously supports two largely incompatible undo models
> > > > doesn't seem worth it to me.
> > >
> > > I'm not sure why you say they're largely incompatible.
> >
> > Maybe I overstated it. I meant that treating undos as new changes that
> > can themselves be undone is conceptually very different to treating undos
> > and redos as a way of navigating around a history of buffer states. I
> > can't imagine a user ever wanting to use both models at the same time,
> > rather than picking one or the other. And I believe (but prove me wrong!)
> > that an implementation that supports both will be unwieldy. The Emacs
> > undo model lends itself naturally to a list data structure, whereas the
> > undo-tree model lends itself naturally to a tree data structure.
> >
> >
> > > > 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.
> > >
> > > Sounds like bug 16818, which affected the builtin undo system too. It
> > > is fixed in the upcoming Emacs 24.4.
> >
> > I'm not sure. I remember it affected normal undo-tree undo, not
> > undo-in-region (which I hadn't even implemented at the time).
> >
> > > undo-tree may require an analagous change, since it doesn't use
> > > undo-make-selective-list.
> >
> > Thanks. Either that function didn't exist when I wrote the undo-in-region
> > support, or I overlooked it. It ought to simplify undo-tree's
> > undo-in-region implementation a little. Currently it constructs the
> > region changeset manually using undo-elt-in-region.
> >
> > > I don't think this bug has anything particular to do with
> > > compact_undo_list splicing out marker adjustments in GC. Maybe the
> > > undo-tree-object-pool makes the bug less probable because it allows
> > > some problematic marker adjustments to be removed earlier during GC
> > > instead of later during undo history truncation.
> > >
> > > The undo-tree-object-pool code looks like a correct, albeit
> > > convoluted, mimicry of compact_undo_list, but I don't see an actual
> > > problem either solves.
> >
> > Storing marker undo elements in buffer-undo-tree fundamentally changes
> > the behaviour of markers: they don't get garbage collected, because they
> > remain referenced forever. (Or at least until undo-tree truncates the
> > undo history for space reasons.)
> >
> > The same is *not* true of marker undo elements in buffer-undo-list,
> > because Emacs GC deals with buffer-undo-list as a special
> > case. Effectively, references to markers in buffer-undo-list are treated
> > as weak references.
> >
> > The undo-tree object-pool code restores the correct GC behaviour, by
> > effectively making references to markers in buffer-undo-tree into weak
> > references.
> >
> > HTH,
> >
> > Toby
> >
> > email: address@hidden
> > web:   www.dr-qubit.org
> >

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