Integration of undo-tree in Emacs

Integration of undo-tree in Emacs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 5736 bytes --]

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

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

[-- Attachment #2: Type: text/html, Size: 6821 bytes --]

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: tsc25@cantab.net
web:   www.dr-qubit.org

Re: Integration of undo-tree in Emacs

[Stefan Monnier]

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

As mentioned earlier, I'd be happy to accept a patch which removes
"undo+redo+undo" elements rather than accumulating redundant traversals.

IOW, buffer-undo-list can hold multiple copies of the same tree
branch, and I's be happy to change this so as to remove the
redundant copies.

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

Yes, that would be fine.

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

Note that the set of reachable nodes is reduced in the same order as in
the case of undo-tree.  The difference is in how these are mapped to
a tree.  To a large extent the difference is in "which node is taken to
be the root".  If you always take "the most recent state" as the root of the
tree (instead of the oldest), then both techniques are "stable" and
behave "identically".

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

Toby's position is that the undo data should be kept as a tree, not as
a list.  That makes a lot of sense: For every branch in a tree, the
undo-list keeps 2 bundles (one going forward and the other going back),
but one of the two is always redundant, so the representation
is inefficient.  Of course, this inefficiency only applies to the
*branches*, i.e. only for those elements generated by `undo', so this is
irrelevant as long as most of the changes are not undos.


        Stefan

Re: Integration of undo-tree in Emacs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 2264 bytes --]

Thanks for your reply, Toby. I appreciate your wisdom on this topic.

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

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

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.

> 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. undo-tree may require an
analagous change, since it doesn't use undo-make-selective-list.

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.

[-- Attachment #2: Type: text/html, Size: 2623 bytes --]

Re: Integration of undo-tree in Emacs

[Toby Cubitt]

On Wed, May 28, 2014 at 10:08:08PM -0400, Stefan Monnier wrote:
> > Toby, are there other reasons undo-tree needs to transfer undo
> > elements from the buffer-undo-list to its own data model?
> 
> Toby's position is that the undo data should be kept as a tree, not as
> a list.  That makes a lot of sense: For every branch in a tree, the
> undo-list keeps 2 bundles (one going forward and the other going back),
> but one of the two is always redundant, so the representation
> is inefficient.  Of course, this inefficiency only applies to the
> *branches*, i.e. only for those elements generated by `undo', so this is
> irrelevant as long as most of the changes are not undos.

Just to be clear, I'm not strongly advocating changing Emacs' undo data
structures. I'm just pointing out that *if* you're going to make
substantial changes to the undo system for other reasons, you might as
well consider whether changing the data structures would be useful too.

I can see a number of arguments against changing Emacs' undo model, not
least that `buffer-undo-list' is documented in the Elisp manual so is
part of the Elisp API that packages may rely on. (I very occasionally get
reports that undo-tree is incompatible with some package, for this
reason.)

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

email: tsc25@cantab.net
web:   www.dr-qubit.org

Re: Integration of undo-tree in Emacs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 1209 bytes --]

> For every branch in a tree, the undo-list keeps 2 bundles (one going
> forward and the other going back), but one of the two is always
> redundant, so the representation is inefficient.

Yes, makes sense. So the code wouldn't trim every undo/redo pair but
just those that don't lose information about the other branches that
exist. So if the user goes up and down a branch twice, we only trim
out one round trip.

> Note that the set of reachable nodes is reduced in the same order as
> in the case of undo-tree.  The difference is in how these are mapped
> to a tree.  To a large extent the difference is in "which node is
> taken to be the root".  If you always take "the most recent state"
> as the root of the tree (instead of the oldest), then both
> techniques are "stable" and behave "identically".

You lost me at "the most recent state as the root". If you mean most
recently created, that is a leaf node. If you mean most recently
visited, that is the user's current node and is not necessarily the
root either.

> So A is first in line for truncation followed by E, B, C, D.

My mistake: that should have been A, D, C, B, E. (I think undo-tree's
right-to-left ordering of branches threw me off.)

[-- Attachment #2: Type: text/html, Size: 1422 bytes --]

Re: Integration of undo-tree in Emacs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 8440 bytes --]

>> 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 <tsc25@cantab.net> 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: tsc25@cantab.net
> web:   www.dr-qubit.org
>

[-- Attachment #2: Type: text/html, Size: 9937 bytes --]

Re: Integration of undo-tree in Emacs

[Stefan Monnier]

> Yes, makes sense. So the code wouldn't trim every undo/redo pair but
> just those that don't lose information about the other branches that
> exist. So if the user goes up and down a branch twice, we only trim
> out one round trip.

Right.  That is imposed by the current buffer-undo-list representation.

> You lost me at "the most recent state as the root".

"most recent state" = "current buffer state".

> If you mean most recently visited, that is the user's current node and
> is not necessarily the root either.

We're discussing *choosing* a node as being the root.  So, it doesn't
have to be the root, but it can (always) be chosen as the root.
Technically, any one of the nodes can be chosen as the root of "a"
tree.  Obviously, some choices are more meaningful to the user than others.


        Stefan

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 <tsc25@cantab.net> 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: tsc25@cantab.net
> > 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: tsc25@cantab.net
web:   www.dr-qubit.org

Re: Integration of undo-tree in Emacs

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 1790 bytes --]

> I maintain that users are not going to want to hold both models in
> their heads.

I didn't say users should hold two models in their head. I didn't
propose two.

> As far as I remember, I've never had anyone ask me if it would be
> possible to combine both systems.

http://lists.gnu.org/archive/html/gnu-emacs-sources/2009-11/msg00010.html

> It's the latter that I predict will be hard work

No doubt.

> If the two are to coexist, how are the two models of undo going to
> interact?

You've misunderstood something, see the first answer above.

> How will history-discarding work well for both models?

Discussed already in the thread.

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

That may be an option.

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

I know the value of starting from code that works now.

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

Nice strawman argument.

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

You may have misattributed the root cause of those problems.

[-- Attachment #2: Type: text/html, Size: 2208 bytes --]

Re: Integration of undo-tree in Emacs

[Toby Cubitt]

On Mon, Jun 02, 2014 at 12:24:22PM -0400, Barry OReilly wrote:
> > I maintain that users are not going to want to hold both models in
> > their heads.
> 
> I didn't say users should hold two models in their head. I didn't
> propose two.
>
> > As far as I remember, I've never had anyone ask me if it would be
> > possible to combine both systems.
> 
> http://lists.gnu.org/archive/html/gnu-emacs-sources/2009-11/msg00010.html

Sure, I completely understand why Stefan said this. And for what it's
worth I agree. I meant I don't remember any *user* saying they'd like to
be able to use both systems simultaneously.

> > It's the latter that I predict will be hard work
> 
> No doubt.
> 
> > If the two are to coexist, how are the two models of undo going to
> > interact?
> 
> You've misunderstood something, see the first answer above.

I guess I still don't quite follow from the above discussion how redo as
undoing-an-undo and redo as descending the undo tree would work
together. Probably you've thought this through already and I just didn't
understand, or it was discussed earlier in the thread before you cc'd me.

> > How will history-discarding work well for both models?
> 
> Discussed already in the thread.

Yes, I saw that part of the discussion. Sounds like it might require
tweaking the order in which undo history gets discarded to match the
undo-tree model. But it also sounds like Stefan is OK with this, so maybe
this one's already solved.

> > 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?
> 
> That may be an option.
> 
> > That way most of the undo-tree code, including all the tree-related
> > features, will work unchanged or with very minor changes.
> 
> I know the value of starting from code that works now.
> 
> > Reimplementing undo-tree from scratch on top of
> > undo-(equiv|redo)-table smacks a little of NIH syndrome to me.
> 
> Nice strawman argument.

Sorry if I caused offence. I'm not subscribed to emacs-devel at the
moment (no time to keep up with the list), so I only saw the latter half
of the discussion from when you started to cc me. It sounded like the
proposal was to implement something on top of undo-[equiv|redo]-table,
which sounds very much like reimplementing undo-tree from scratch in
Emacs. Maybe I misconstrued.


> > 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.
> 
> You may have misattributed the root cause of those problems.

Quite possibly. It would be interesting to test with the undo-tree GC-elt
pool code disabled, and see what happens with markers/overlays under
recent Emacsen.

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

email: tsc25@cantab.net
web:   www.dr-qubit.org