[LONG] undo-tree and garbage collection: a request for advice from the gurus

[LONG] undo-tree and garbage collection: a request for advice from the gurus

[Toby Cubitt]

Dear Emacs sages,

As you might have seen, I posted undo-tree.el to gnu-emacs-sources a
while back. I quickly received a gush of positive feedback, a flood of
requests for additional features, and the usual tiny trickle of patches
implementing those requests :)

There was also some interest expressed by Stefan in "integrating
something along [the undo-tree] lines into Emacs, but [that] it would
need to be integrated with the existing undo system", which sort of
relates tangentially to my request for advice.

When I've found time, I've been working on the two things I highlighted
in the "Drawbacks" section in undo-tree.el: implementing undo-in-region
(nearly done), and supporting marker adjustment undo entries
(`undo-tree-mode' currently takes the cowardly approach, and just deletes
them!). It's the latter I would value some input on from the experts
before I spend more time on it, because it's connected to low-level
details of the garbage collection C code.

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.

I spent quite a lot of time re-implementing `undo-tree-mode' so that
rather than transferring undo data out of `buffer-undo-list',
`buffer-undo-tree' instead stored pointers to undo changesets in
`buffer-undo-list'...only to eventually realise that this wasn't going to
solve anything!

Even though `buffer-undo-list' was ignored during gc, `buffer-undo-tree'
of course wasn't. Because `buffer-undo-tree' pointed to parts of
`buffer-undo-list', old marker entries in `buffer-undo-list' were *still*
picked up during the gc mark phase via `buffer-undo-tree', hence were
never gc'd, and could potentially be resurrected from the dead.

I have to admit to not explicitly testing this, and I'm not an expert on
Emacs' gc code, so I could well be mistaken about this interaction with
gc. But if I'm right, note that this issue would apply much more widely:
any referrence to `buffer-undo-list', even a simple
(setq foo buffer-undo-list), would thwart the special treatment of
`buffer-undo-list' in gc, leading to old markers never being gc'd and (I
think) causing deleted markers to be resurrected when undoing a changeset
containing a marker that should have been gc'd.

For undo-tree, I can think of two ways around this, neither of them very
good. Since the issue would seem to extend well beyond undo-tree, to any
Elisp code that stores references to elements of `buffer-undo-list', I
wonder if some more elegant, far-reaching solution could be found,
instead of embarking on coding an ugly work-around specific to
`undo-tree-mode'?

Sorry for the long essay (the original was longer ;-), and thanks for any
advice you can offer,

Toby
--
Dr T. S. Cubitt
Quantum Information Theory group
Department of Mathematics
University of Bristol
United Kingdom

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

Re: [LONG] undo-tree and garbage collection: a request for advice from the gurus

[Stefan Monnier]

> I spent quite a lot of time re-implementing `undo-tree-mode' so that
> rather than transferring undo data out of `buffer-undo-list',
> `buffer-undo-tree' instead stored pointers to undo changesets in
> `buffer-undo-list'...only to eventually realise that this wasn't going to
> solve anything!

It'll work but only if your references into buffer-undo-list are weak
(i.e. they don't prevent the pointed elements from being GC'd).
For undo-equiv-table I do that by using a weak hash-table:

  (defconst undo-equiv-table (make-hash-table :test 'eq :weakness t)


-- Stefan

Re: [LONG] undo-tree and garbage collection: a request for advice from the gurus

[Toby Cubitt]

On Sun, May 02, 2010 at 03:47:12PM -0400, Stefan Monnier wrote:
> > I spent quite a lot of time re-implementing `undo-tree-mode' so that
> > rather than transferring undo data out of `buffer-undo-list',
> > `buffer-undo-tree' instead stored pointers to undo changesets in
> > `buffer-undo-list'...only to eventually realise that this wasn't going to
> > solve anything!
> 
> It'll work but only if your references into buffer-undo-list are weak
> (i.e. they don't prevent the pointed elements from being GC'd).
> For undo-equiv-table I do that by using a weak hash-table:
> 
>   (defconst undo-equiv-table (make-hash-table :test 'eq :weakness t)

Ah, it hadn't occurred to me that undo-equiv-table would suffer from the
same problem, and I wasn't aware that weak references were implemented in
any part of Elisp. Thanks for that tip!

But stashing the buffer-undo-tree changesets inside a weak hash table
poses a different problem: changesets that drop off the end of
buffer-undo-list when undo-limit et al. are breached are no longer
protected from gc any more. (Or would one of the :weakness choices
prevent the changeset list from being gc'd, whilst still allowing marker
elements in that list to be gc'd?) Having changesets gc'd behind my back
makes life difficult, because I then have to detect this and fix up the
tree. (It's made worse by the fact that undo-tree-mode discards undo
history in a slightly different order to standard Emacs undo, one which
fits correctly with the undo tree structure.)

I could no doubt work around this by detecting tree nodes whose undo
changesets have been gc'd, deleting them from the tree, and discarding
the parts of the tree that are no longer reachable (or something along
these lines). But it seems like a heck of an ugly mess: storing
changesets in otherwise unnecessary hash tables, detecting and recovering
from gc'd undo changesets, maintaining undo history in buffer-undo-list
as well as the undo tree, then keeping them both in synch when history is
discarded...all just to allow markers to be restored correctly by undo!
My experience of trying to implement this once already was that it led to
very fragile code, and a maze of subtle bugs that were only triggered
when the right sequence of undo/redos were discarded. Rather than
embarking on coding this, I'm not sure if I wouldn't prefer to continue
discarding marker entries, and live with the fact that undo-tree would
probably never make it into Emacs proper.

It all smacks of something that needs a clean, well thought-through, more
general solution to allow Elisp packages to modify the undo system
without needing so many ugly and fragile hacks...


Toby

PS: I'm aware that undo is deeply embedded in Emacs, and implementing
undo-tree-mode in Elisp was always going to hit some tricky issue like
this eventually. In fact, I'm surprised so much could be made to work so
easily and cleanly.
-- 
Dr T. S. Cubitt
Quantum Information Theory group
Department of Mathematics
University of Bristol
United Kingdom

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