* Integration of undo-tree in Emacs @ 2014-05-28 19:38 Barry OReilly 2014-05-28 22:14 ` Toby Cubitt 2014-05-29 2:08 ` Stefan Monnier 0 siblings, 2 replies; 11+ messages in thread From: Barry OReilly @ 2014-05-28 19:38 UTC (permalink / raw) To: toby-undo-tree, Stefan Monnier; +Cc: emacs-devel [-- Attachment #1: Type: text/plain, Size: 5736 bytes --] 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. If one conceives of undo history as a tree, then a run of undo commands means "retrace my edge traversals". Then if you break that run, you have to retrace *those* edge traversals. undo-only means "go to the parent". This follows from the fact that edits create new nodes downward in the tree. Recursive lookup in undo-equiv-table doesn't change the node you're currently on, but does bring you back to the least recent time that node was reached. That usually means an undo from that point "retraces the edge traversal" which created the node, thus taking you to the parent. 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: 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. The appeal of undo-tree is that it allows the user to more intuitively and directly navigate the underlying tree. If the user wants to reach other branches of the tree using the builtin undo system, they must retrace their edge traversals, of which there can be many. This is poorer usability. Since the builtin undo commands can be thought of in tree terms, I believe it may be possible for the two systems to coexist. 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. 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, but there is at least one drawback I would like to describe. When the buffer-undo-list is truncated, weak references in the undo-redo-table are removed. This means "redo groups" (change groups created by an undo command) suddenly look like "edit groups" (change groups created by a normal editing command). This would change the structure of the tree at GC time. Consider as an example: A | | B ___|___ / \ E C | | D [Note: This uses undo-tree's convention of newer branches on the left.] The user's movement through the tree is: A edit to B edit to C edit to D undo to C undo to B edit to E Suppose GC truncates "A edit to B edit to C". Because of removals of weak references from undo-redo-table, the history looks like: "C edit to D undo to C edit to B edit to E" (notice an "undo to" became a "edit to"). Regenerating the tree from this yields: C ___|___ / \ B D | | E This kind of tree change at seemingly random times might be very surprising to the user, albeit granted the parent-child reversals will tend to occur away from the user's local part of the tree. 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? Toby, are there other reasons undo-tree needs to transfer undo elements from the buffer-undo-list to its own data model? 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. > 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. [-- Attachment #2: Type: text/html, Size: 6821 bytes --] ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Integration of undo-tree in Emacs 2014-05-28 19:38 Integration of undo-tree in Emacs Barry OReilly @ 2014-05-28 22:14 ` Toby Cubitt 2014-05-29 2:57 ` Barry OReilly 2014-05-29 2:08 ` Stefan Monnier 1 sibling, 1 reply; 11+ messages in thread From: Toby Cubitt @ 2014-05-28 22:14 UTC (permalink / raw) To: Barry OReilly; +Cc: Stefan Monnier, emacs-devel 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Integration of undo-tree in Emacs 2014-05-28 22:14 ` Toby Cubitt @ 2014-05-29 2:57 ` Barry OReilly [not found] ` <20140529180441.GA12623@c3po.maths.private.cam.ac.uk> 0 siblings, 1 reply; 11+ messages in thread From: Barry OReilly @ 2014-05-29 2:57 UTC (permalink / raw) To: Toby Cubitt; +Cc: Stefan Monnier, emacs-devel [-- Attachment #1: Type: text/plain, Size: 2264 bytes --] Thanks for your reply, Toby. I appreciate your wisdom on this topic. > 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. 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 | | 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. > 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. undo-tree may require an analagous change, since it doesn't use undo-make-selective-list. 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. [-- Attachment #2: Type: text/html, Size: 2623 bytes --] ^ permalink raw reply [flat|nested] 11+ messages in thread
[parent not found: <20140529180441.GA12623@c3po.maths.private.cam.ac.uk>]
* Re: Integration of undo-tree in Emacs [not found] ` <20140529180441.GA12623@c3po.maths.private.cam.ac.uk> @ 2014-05-30 14:40 ` Barry OReilly 2014-06-02 10:57 ` Toby Cubitt 0 siblings, 1 reply; 11+ messages in thread From: Barry OReilly @ 2014-05-30 14:40 UTC (permalink / raw) To: Toby Cubitt, emacs-devel [-- Attachment #1: Type: text/plain, Size: 8440 bytes --] >> 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. Together with the undo-(equiv|redo)-table it conveys sufficient information to construct a tree. 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). >>> 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. Instead, I suspect compact_undo_list is just an optimization. The asymptotic performance of low level editing functions depends on how many markers there are in the buffer. If it's common for markers to become unreachable (except via buffer-undo-list) while still pointing into a buffer, then compact_undo_list will remove them. This means that theoretically the performance of editing functions is not a function of undo-limit. If I'm right, then the only bad symptom in undo-tree would be a possible performance degradation. >> 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. On Thu, May 29, 2014 at 2:04 PM, Toby Cubitt <tsc25@cantab.net> 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 > -- > 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 > [-- Attachment #2: Type: text/html, Size: 9937 bytes --] ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Integration of undo-tree in Emacs 2014-05-30 14:40 ` Barry OReilly @ 2014-06-02 10:57 ` Toby Cubitt 2014-06-02 16:24 ` Barry OReilly 0 siblings, 1 reply; 11+ messages in thread From: Toby Cubitt @ 2014-06-02 10:57 UTC (permalink / raw) To: Barry OReilly; +Cc: emacs-devel 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 <tsc25@cantab.net> 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Integration of undo-tree in Emacs 2014-06-02 10:57 ` Toby Cubitt @ 2014-06-02 16:24 ` Barry OReilly 2014-06-02 21:23 ` Toby Cubitt 0 siblings, 1 reply; 11+ messages in thread From: Barry OReilly @ 2014-06-02 16:24 UTC (permalink / raw) To: Toby Cubitt; +Cc: emacs-devel [-- Attachment #1: Type: text/plain, Size: 1790 bytes --] > I maintain that users are not going to want to hold both models in > their heads. I didn't say users should hold two models in their head. I didn't propose two. > As far as I remember, I've never had anyone ask me if it would be > possible to combine both systems. http://lists.gnu.org/archive/html/gnu-emacs-sources/2009-11/msg00010.html > It's the latter that I predict will be hard work No doubt. > If the two are to coexist, how are the two models of undo going to > interact? You've misunderstood something, see the first answer above. > How will history-discarding work well for both models? Discussed already in the thread. > 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? That may be an option. > That way most of the undo-tree code, including all the tree-related > features, will work unchanged or with very minor changes. I know the value of starting from code that works now. > Reimplementing undo-tree from scratch on top of > undo-(equiv|redo)-table smacks a little of NIH syndrome to me. Nice strawman argument. > 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. You may have misattributed the root cause of those problems. [-- Attachment #2: Type: text/html, Size: 2208 bytes --] ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Integration of undo-tree in Emacs 2014-06-02 16:24 ` Barry OReilly @ 2014-06-02 21:23 ` Toby Cubitt 0 siblings, 0 replies; 11+ messages in thread From: Toby Cubitt @ 2014-06-02 21:23 UTC (permalink / raw) To: Barry OReilly; +Cc: emacs-devel On Mon, Jun 02, 2014 at 12:24:22PM -0400, Barry OReilly wrote: > > I maintain that users are not going to want to hold both models in > > their heads. > > I didn't say users should hold two models in their head. I didn't > propose two. > > > As far as I remember, I've never had anyone ask me if it would be > > possible to combine both systems. > > http://lists.gnu.org/archive/html/gnu-emacs-sources/2009-11/msg00010.html Sure, I completely understand why Stefan said this. And for what it's worth I agree. I meant I don't remember any *user* saying they'd like to be able to use both systems simultaneously. > > It's the latter that I predict will be hard work > > No doubt. > > > If the two are to coexist, how are the two models of undo going to > > interact? > > You've misunderstood something, see the first answer above. I guess I still don't quite follow from the above discussion how redo as undoing-an-undo and redo as descending the undo tree would work together. Probably you've thought this through already and I just didn't understand, or it was discussed earlier in the thread before you cc'd me. > > How will history-discarding work well for both models? > > Discussed already in the thread. Yes, I saw that part of the discussion. Sounds like it might require tweaking the order in which undo history gets discarded to match the undo-tree model. But it also sounds like Stefan is OK with this, so maybe this one's already solved. > > 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? > > That may be an option. > > > That way most of the undo-tree code, including all the tree-related > > features, will work unchanged or with very minor changes. > > I know the value of starting from code that works now. > > > Reimplementing undo-tree from scratch on top of > > undo-(equiv|redo)-table smacks a little of NIH syndrome to me. > > Nice strawman argument. Sorry if I caused offence. I'm not subscribed to emacs-devel at the moment (no time to keep up with the list), so I only saw the latter half of the discussion from when you started to cc me. It sounded like the proposal was to implement something on top of undo-[equiv|redo]-table, which sounds very much like reimplementing undo-tree from scratch in Emacs. Maybe I misconstrued. > > 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. > > You may have misattributed the root cause of those problems. Quite possibly. It would be interesting to test with the undo-tree GC-elt pool code disabled, and see what happens with markers/overlays under recent Emacsen. Best, 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Integration of undo-tree in Emacs 2014-05-28 19:38 Integration of undo-tree in Emacs Barry OReilly 2014-05-28 22:14 ` Toby Cubitt @ 2014-05-29 2:08 ` Stefan Monnier 2014-05-29 17:42 ` Toby Cubitt 2014-05-30 12:00 ` Barry OReilly 1 sibling, 2 replies; 11+ messages in thread From: Stefan Monnier @ 2014-05-29 2:08 UTC (permalink / raw) To: Barry OReilly; +Cc: toby-undo-tree, emacs-devel > The appeal of undo-tree is that it allows the user to more > intuitively and directly navigate the underlying tree. If the > user wants to reach other branches of the tree using the builtin > undo system, they must retrace their edge traversals, of which > there can be many. This is poorer usability. As mentioned earlier, I'd be happy to accept a patch which removes "undo+redo+undo" elements rather than accumulating redundant traversals. IOW, buffer-undo-list can hold multiple copies of the same tree branch, and I's be happy to change this so as to remove the redundant copies. > 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. Yes, that would be fine. > This kind of tree change at seemingly random times might be very > surprising to the user, albeit granted the parent-child reversals > will tend to occur away from the user's local part of the tree. Note that the set of reachable nodes is reduced in the same order as in the case of undo-tree. The difference is in how these are mapped to a tree. To a large extent the difference is in "which node is taken to be the root". If you always take "the most recent state" as the root of the tree (instead of the oldest), then both techniques are "stable" and behave "identically". > Toby, are there other reasons undo-tree needs to transfer undo > elements from the buffer-undo-list to its own data model? Toby's position is that the undo data should be kept as a tree, not as a list. That makes a lot of sense: For every branch in a tree, the undo-list keeps 2 bundles (one going forward and the other going back), but one of the two is always redundant, so the representation is inefficient. Of course, this inefficiency only applies to the *branches*, i.e. only for those elements generated by `undo', so this is irrelevant as long as most of the changes are not undos. Stefan ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Integration of undo-tree in Emacs 2014-05-29 2:08 ` Stefan Monnier @ 2014-05-29 17:42 ` Toby Cubitt 2014-05-30 12:00 ` Barry OReilly 1 sibling, 0 replies; 11+ messages in thread From: Toby Cubitt @ 2014-05-29 17:42 UTC (permalink / raw) To: Stefan Monnier; +Cc: Barry OReilly, emacs-devel On Wed, May 28, 2014 at 10:08:08PM -0400, Stefan Monnier wrote: > > Toby, are there other reasons undo-tree needs to transfer undo > > elements from the buffer-undo-list to its own data model? > > Toby's position is that the undo data should be kept as a tree, not as > a list. That makes a lot of sense: For every branch in a tree, the > undo-list keeps 2 bundles (one going forward and the other going back), > but one of the two is always redundant, so the representation > is inefficient. Of course, this inefficiency only applies to the > *branches*, i.e. only for those elements generated by `undo', so this is > irrelevant as long as most of the changes are not undos. Just to be clear, I'm not strongly advocating changing Emacs' undo data structures. I'm just pointing out that *if* you're going to make substantial changes to the undo system for other reasons, you might as well consider whether changing the data structures would be useful too. I can see a number of arguments against changing Emacs' undo model, not least that `buffer-undo-list' is documented in the Elisp manual so is part of the Elisp API that packages may rely on. (I very occasionally get reports that undo-tree is incompatible with some package, for this reason.) 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Integration of undo-tree in Emacs 2014-05-29 2:08 ` Stefan Monnier 2014-05-29 17:42 ` Toby Cubitt @ 2014-05-30 12:00 ` Barry OReilly 2014-05-30 16:01 ` Stefan Monnier 1 sibling, 1 reply; 11+ messages in thread From: Barry OReilly @ 2014-05-30 12:00 UTC (permalink / raw) To: Stefan Monnier; +Cc: toby-undo-tree, emacs-devel [-- Attachment #1: Type: text/plain, Size: 1209 bytes --] > For every branch in a tree, the undo-list keeps 2 bundles (one going > forward and the other going back), but one of the two is always > redundant, so the representation is inefficient. Yes, makes sense. So the code wouldn't trim every undo/redo pair but just those that don't lose information about the other branches that exist. So if the user goes up and down a branch twice, we only trim out one round trip. > Note that the set of reachable nodes is reduced in the same order as > in the case of undo-tree. The difference is in how these are mapped > to a tree. To a large extent the difference is in "which node is > taken to be the root". If you always take "the most recent state" > as the root of the tree (instead of the oldest), then both > techniques are "stable" and behave "identically". You lost me at "the most recent state as the root". If you mean most recently created, that is a leaf node. If you mean most recently visited, that is the user's current node and is not necessarily the root either. > So A is first in line for truncation followed by E, B, C, D. My mistake: that should have been A, D, C, B, E. (I think undo-tree's right-to-left ordering of branches threw me off.) [-- Attachment #2: Type: text/html, Size: 1422 bytes --] ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Integration of undo-tree in Emacs 2014-05-30 12:00 ` Barry OReilly @ 2014-05-30 16:01 ` Stefan Monnier 0 siblings, 0 replies; 11+ messages in thread From: Stefan Monnier @ 2014-05-30 16:01 UTC (permalink / raw) To: Barry OReilly; +Cc: toby-undo-tree, emacs-devel > Yes, makes sense. So the code wouldn't trim every undo/redo pair but > just those that don't lose information about the other branches that > exist. So if the user goes up and down a branch twice, we only trim > out one round trip. Right. That is imposed by the current buffer-undo-list representation. > You lost me at "the most recent state as the root". "most recent state" = "current buffer state". > If you mean most recently visited, that is the user's current node and > is not necessarily the root either. We're discussing *choosing* a node as being the root. So, it doesn't have to be the root, but it can (always) be chosen as the root. Technically, any one of the nodes can be chosen as the root of "a" tree. Obviously, some choices are more meaningful to the user than others. Stefan ^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2014-06-02 21:23 UTC | newest] Thread overview: 11+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2014-05-28 19:38 Integration of undo-tree in Emacs Barry OReilly 2014-05-28 22:14 ` Toby Cubitt 2014-05-29 2:57 ` Barry OReilly [not found] ` <20140529180441.GA12623@c3po.maths.private.cam.ac.uk> 2014-05-30 14:40 ` Barry OReilly 2014-06-02 10:57 ` Toby Cubitt 2014-06-02 16:24 ` Barry OReilly 2014-06-02 21:23 ` Toby Cubitt 2014-05-29 2:08 ` Stefan Monnier 2014-05-29 17:42 ` Toby Cubitt 2014-05-30 12:00 ` Barry OReilly 2014-05-30 16:01 ` Stefan Monnier
Code repositories for project(s) associated with this external index https://git.savannah.gnu.org/cgit/emacs.git https://git.savannah.gnu.org/cgit/emacs/org-mode.git This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.