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

[Toby Cubitt <tsc25@cantab.net>]

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