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: address@hidden
web: www.dr-qubit.org