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: Integration of undo-tree in Emacs Date: Wed, 28 May 2014 23:14:35 +0100 Message-ID: <20140528221435.GA24032@c3po> References: Reply-To: Toby Cubitt NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1401315305 939 80.91.229.3 (28 May 2014 22:15:05 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 28 May 2014 22:15:05 +0000 (UTC) Cc: Stefan Monnier , emacs-devel@gnu.org To: Barry OReilly Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu May 29 00:14:59 2014 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Wpm7e-0001FW-7A for ged-emacs-devel@m.gmane.org; Thu, 29 May 2014 00:14:58 +0200 Original-Received: from localhost ([::1]:45202 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wpm7d-0001PB-Fu for ged-emacs-devel@m.gmane.org; Wed, 28 May 2014 18:14:57 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:56501) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wpm7V-0001F4-6V for emacs-devel@gnu.org; Wed, 28 May 2014 18:14:53 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Wpm7R-0004VV-1c for emacs-devel@gnu.org; Wed, 28 May 2014 18:14:49 -0400 Original-Received: from starfish.geekisp.com ([216.168.135.166]:19409) by eggs.gnu.org with smtp (Exim 4.71) (envelope-from ) id 1Wpm7Q-0004VE-Tm for emacs-devel@gnu.org; Wed, 28 May 2014 18:14:44 -0400 Original-Received: (qmail 12525 invoked by uid 1003); 28 May 2014 22:14:41 -0000 Original-Received: from localhost (localhost.geekisp.com [127.0.0.1]) by localhost.geekisp.com (tmda-ofmipd) with ESMTP; Wed, 28 May 2014 18:14:38 -0400 Content-Disposition: inline In-Reply-To: X-PGP-Key: http://www.dr-qubit.org/gpg-toby-pub.asc User-Agent: Mutt/1.5.23 (2014-03-12) X-Delivery-Agent: TMDA/1.1.11 (Ladyburn) X-Primary-Address: toby@dr-qubit.org X-detected-operating-system: by eggs.gnu.org: OpenBSD 4.x-5.x [fuzzy] X-Received-From: 216.168.135.166 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:172166 Archived-At: 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