Re: Integration of undo-tree in Emacs

[Barry OReilly]

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

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

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

Instead, I suspect compact_undo_list is just an optimization. The
asymptotic performance of low level editing functions depends on how
many markers there are in the buffer. If it's common for markers to
become unreachable (except via buffer-undo-list) while still pointing
into a buffer, then compact_undo_list will remove them. This means
that theoretically the performance of editing functions is not a
function of undo-limit.

If I'm right, then the only bad symptom in undo-tree would be a
possible performance degradation.

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

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