From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Toby Cubitt Newsgroups: gmane.emacs.devel Subject: Re: [LONG] undo-tree and garbage collection: a request for advice from the gurus Date: Mon, 3 May 2010 14:17:45 +0100 Message-ID: <20100503131745.GA445@c3po> References: Reply-To: Toby Cubitt NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1272892425 10468 80.91.229.12 (3 May 2010 13:13:45 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Mon, 3 May 2010 13:13:45 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon May 03 15:13:44 2010 connect(): No such file or directory Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1O8vSx-0001tM-M6 for ged-emacs-devel@m.gmane.org; Mon, 03 May 2010 15:13:43 +0200 Original-Received: from localhost ([127.0.0.1]:47298 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O8vSw-0002Ba-SE for ged-emacs-devel@m.gmane.org; Mon, 03 May 2010 09:13:42 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1O8vS3-0001Ie-Fg for emacs-devel@gnu.org; Mon, 03 May 2010 09:12:47 -0400 Original-Received: from [140.186.70.92] (port=36109 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O8vS1-0001Fg-A5 for emacs-devel@gnu.org; Mon, 03 May 2010 09:12:46 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1O8vRy-000269-L8 for emacs-devel@gnu.org; Mon, 03 May 2010 09:12:45 -0400 Original-Received: from mail.geekisp.com ([216.168.135.169]:31795 helo=starfish.geekisp.com) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1O8vRy-00025q-G6 for emacs-devel@gnu.org; Mon, 03 May 2010 09:12:42 -0400 Original-Received: (qmail 16171 invoked by uid 1003); 3 May 2010 13:12:39 -0000 Original-Received: from c3po (localhost.geekisp.com [127.0.0.1]) by localhost.geekisp.com (tmda-ofmipd) with ESMTP; Mon, 03 May 2010 09:12:37 -0400 Content-Disposition: inline In-Reply-To: Fcc: ~/.offlineimap/GeekISP/INBOX/Sent/ User-Agent: Mutt/1.5.20 (2009-06-14) X-Delivery-Agent: TMDA/1.1.11 (Ladyburn) X-Primary-Address: toby@dr-qubit.org X-detected-operating-system: by eggs.gnu.org: OpenBSD 3.0-3.4 (scrub) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:124473 Archived-At: 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