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: Mon, 2 Jun 2014 11:57:12 +0100 Message-ID: <20140602105712.GA8390@c3po.maths.private.cam.ac.uk> References: Reply-To: Toby Cubitt NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: ger.gmane.org 1401706660 8821 80.91.229.3 (2 Jun 2014 10:57:40 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 2 Jun 2014 10:57:40 +0000 (UTC) Cc: emacs-devel@gnu.org To: Barry OReilly Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Jun 02 12:57:34 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 1WrPvp-000788-KS for ged-emacs-devel@m.gmane.org; Mon, 02 Jun 2014 12:57:33 +0200 Original-Received: from localhost ([::1]:44101 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WrPvp-0007GF-Bl for ged-emacs-devel@m.gmane.org; Mon, 02 Jun 2014 06:57:33 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:54472) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WrPvh-0007Bp-AD for emacs-devel@gnu.org; Mon, 02 Jun 2014 06:57:29 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WrPvb-00067j-N0 for emacs-devel@gnu.org; Mon, 02 Jun 2014 06:57:25 -0400 Original-Received: from starfish.geekisp.com ([216.168.135.166]:46121) by eggs.gnu.org with smtp (Exim 4.71) (envelope-from ) id 1WrPvb-00062P-H6 for emacs-devel@gnu.org; Mon, 02 Jun 2014 06:57:19 -0400 Original-Received: (qmail 9010 invoked by uid 1003); 2 Jun 2014 10:57:16 -0000 Original-Received: from localhost (localhost.geekisp.com [127.0.0.1]) by localhost.geekisp.com (tmda-ofmipd) with ESMTP; Mon, 02 Jun 2014 06:57:14 -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:172252 Archived-At: Hi Barry, On Fri, May 30, 2014 at 10:40:44AM -0400, Barry OReilly wrote: > >> I'm not sure why you say they're largely incompatible. > > > Maybe I overstated it. I meant that treating undos as new changes > > that can themselves be undone is conceptually very different to > > treating undos and redos as a way of navigating around a history of > > buffer states. > > Just think of the undo command as a traversal in a tree. Imagine it is > called "undo-retrace" instead of "undo", then the two models don't > seem so incompatible. buffer-undo-list is just a kind of event log of > buffer changes. They're still two *conceptually* very different models of undo, and I maintain that users are not going to want to hold both models in their heads. The feedback I've received from undo-tree users falls into one of two camps: (a) "finally, a sensible undo system for Emacs!", or (b) "interesting package, but I was happy with the existing Emacs system". As far as I remember, I've never had anyone ask me if it would be possible to combine both systems. I definitely agree with you, integrating the two should is technically possible: just have tree nodes point to elements in buffer-undo-list. And then sort out all the finicky details needed to make both models work seamlessly together without bugs. It's the latter that I predict will be hard work, and hard to maintain. I took the easy route, and made undo-tree completely replace the traditional undo model. If the two are to coexist, how are the two models of undo going to interact? How will treating redo as "undoing an undo" interact with treating redo as moving up the tree? How will history-discarding work well for both models? You'll need to think these things through very carefully if the two models are going to coexist nicely. > Together with the undo-(equiv|redo)-table it conveys sufficient > information to construct a tree. Ugh. Personally I find it very hard to get my head around undo-(equiv|redo)-table, even if it in principle conveys sufficient information to reconstruct the tree. I find it much easier to get my head around buffer-undo-tree, which *is* a tree! If you want to integrate undo-tree into Emacs, whilst also keeping the traditional undo system (presumably an essential requirement), why not keep the elegant and conceptually simple (biased personal opinion :-) `buffer-undo-tree's data structure, but make the nodes point to the appropriate changesets in buffer-undo-list? With access to the undo code implement in c, it should be quite straightforward to make this work properly, as you can overcome the problems I faced (and ducked) with trying to do it all from Elisp. That way most of the undo-tree code, including all the tree-related features, will work unchanged or with very minor changes. Reimplementing undo-tree from scratch on top of undo-(equiv|redo)-table smacks a little of NIH syndrome to me. > The usefulness of integrating something like undo-tree is in > visualizing the tree and providing commands to more capably and > intuitively traverse it (eg choosing exactly which branch to descend). That's the main usefulness as you see it. That's definitely not the main usefulness I experience using undo-tree, and I'm not convinced most long-term undo-tree users would agree with you. True, most of them start off thinking the tree visualisation is really cool. But if my own experience is anything to go by, after the initial tree visualizer "wow" factor, in practice the most useful thing is being able to undo and redo as separate operations, without all the "breaking the undo chain" shenanigans. The undo tree is nice to have on the rare occasions one wants to recover history from another branch. It's nice to know that history is still there, even with the undo/redo model. But even I probably make use of the undo-tree visualizer less than once a week (and I do all my text editing in Emacs). Whereas I use undo-tree-redo all the time. > >>> 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. > > >> Sounds like bug 16818, which affected the builtin undo system too. > >> It is fixed in the upcoming Emacs 24.4. > > > I'm not sure. I remember it affected normal undo-tree undo, not > > undo-in-region (which I hadn't even implemented at the time). > > The bug isn't specific to undo in region. It merely lent itself to > demonstrating the bug, because the mark and region overlay markers are > necessarily in the region, and so are swept up into marker > adjustments. They also remain eq over time whilst mutating to point to > various locations. > > The problem was that primitive-undo applied marker adjustments without > concern for whether they moved to unrelated locations. Maybe this > somehow contributed to the overlay havoc you had seen. > > The vast majority of Elisp packages shouldn't care whether GC is going > to happen sooner or later. So if you think the early removal of marker > adjustments via compact_undo_list is essential to correct functioning, > I would wonder why a package depends on that. I think you're still missing the main point I was making. Because buffer-undo-tree isn't treated specially by GC, even unreferenced *deleted* markers (e.g. from `delete-overlay') continued to exist in the undo-tree. Undoing a changeset containing a marker-update entry for one of those deleted markers would resurrect the deleted marker, recreating overlays, and causing general havoc. Perhaps this issue also occurs/occurred with standard undo and buffer-undo-list. But it was made far worse in undo-tree because unreferenced deleted markers were kept alive forever. Moving them into the gc-pool, so that undo-tree only creates a weak-reference to them, restores the standard marker GC behaviour. All that said, there's absolutely nothing to prevent the buffer-undo-list behaviour from being replicated for the undo tree implementation if you're implementing it in core Emacs. The whole undo-tree GC-elts pool mechanism was only necessary because I wanted to implement undo-tree as an Elisp package, without patching any c code. > >> undo-tree may require an analagous change, since it doesn't use > >> undo-make-selective-list. > > > Thanks. Either that function didn't exist when I wrote the > > undo-in-region support, or I overlooked it. It ought to simplify > > undo-tree's undo-in-region implementation a little. Currently it > > constructs the region changeset manually using undo-elt-in-region. > > There have been a few changes in that area, eg under bug 17235, and > there will be more under bug 16411. Thanks. I'll take a look when I find time. Best wishes, Toby > On Thu, May 29, 2014 at 2:04 PM, Toby Cubitt wrote: > > > On Wed, May 28, 2014 at 10:57:15PM -0400, Barry OReilly wrote: > > > Thanks for your reply, Toby. I appreciate your wisdom on this topic. > > > > A modicum of experience, perhaps. Not sure about wisdom! > > > > > > Perhaps I felt that duplicating the entire subtree would make for a > > > > needlessly complex tree. > > > > > > I find one limitation in undo-tree is that a buffer state that was two > > > edges away becomes an arbitrary number of edges away, because > > > undo in region reaches arbitrarily far back. > > > > undo-tree-selection-mode might help with that (hit "s" in the visualizer, > > then use the motion keybindings). > > > > But as I said, I can't remember a clear rational for not duplicating the > > entire tree, and I believe it would be very easy to do so. Perhaps I'll > > make the change in a future release. > > > > > Alternatively, after an undo in region, you could display it like: > > > > > > | > > > | > > > A' > > > |\… > > > | > > > > > > Literally with the ellipsis. Traversing that edge would take you back > > > to the parallel tree you came from: > > > > > > | … > > > |/ > > > A > > > | > > > | > > > > I prefer to keep things simple. They generally work better that way. > > > > > The parallel trees look the same after all. I don't think the user > > > usually cares where is the root at which they join together, although > > > there are probably ways to display that. > > > > > > > The implementation and maintenance overhead of designing a system > > > > that simultaneously supports two largely incompatible undo models > > > > doesn't seem worth it to me. > > > > > > I'm not sure why you say they're largely incompatible. > > > > Maybe I overstated it. I meant that treating undos as new changes that > > can themselves be undone is conceptually very different to treating undos > > and redos as a way of navigating around a history of buffer states. I > > can't imagine a user ever wanting to use both models at the same time, > > rather than picking one or the other. And I believe (but prove me wrong!) > > that an implementation that supports both will be unwieldy. The Emacs > > undo model lends itself naturally to a list data structure, whereas the > > undo-tree model lends itself naturally to a tree data structure. > > > > > > > > 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. > > > > > > Sounds like bug 16818, which affected the builtin undo system too. It > > > is fixed in the upcoming Emacs 24.4. > > > > I'm not sure. I remember it affected normal undo-tree undo, not > > undo-in-region (which I hadn't even implemented at the time). > > > > > undo-tree may require an analagous change, since it doesn't use > > > undo-make-selective-list. > > > > Thanks. Either that function didn't exist when I wrote the undo-in-region > > support, or I overlooked it. It ought to simplify undo-tree's > > undo-in-region implementation a little. Currently it constructs the > > region changeset manually using undo-elt-in-region. > > > > > I don't think this bug has anything particular to do with > > > compact_undo_list splicing out marker adjustments in GC. Maybe the > > > undo-tree-object-pool makes the bug less probable because it allows > > > some problematic marker adjustments to be removed earlier during GC > > > instead of later during undo history truncation. > > > > > > The undo-tree-object-pool code looks like a correct, albeit > > > convoluted, mimicry of compact_undo_list, but I don't see an actual > > > problem either solves. > > > > Storing marker undo elements in buffer-undo-tree fundamentally changes > > the behaviour of markers: they don't get garbage collected, because they > > remain referenced forever. (Or at least until undo-tree truncates the > > undo history for space reasons.) > > > > The same is *not* true of marker undo elements in buffer-undo-list, > > because Emacs GC deals with buffer-undo-list as a special > > case. Effectively, references to markers in buffer-undo-list are treated > > as weak references. > > > > The undo-tree object-pool code restores the correct GC behaviour, by > > effectively making references to markers in buffer-undo-tree into weak > > references. > > > > HTH, > > > > Toby > > > > email: tsc25@cantab.net > > web: www.dr-qubit.org > > -- 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