From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Barry OReilly Newsgroups: gmane.emacs.devel Subject: Re: Integration of undo-tree in Emacs Date: Fri, 30 May 2014 10:40:44 -0400 Message-ID: References: <20140529180441.GA12623@c3po.maths.private.cam.ac.uk> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=089e013d0d5cd5cf6704fa9f0767 X-Trace: ger.gmane.org 1401461124 28559 80.91.229.3 (30 May 2014 14:45:24 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 30 May 2014 14:45:24 +0000 (UTC) To: Toby Cubitt , emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri May 30 16:45:19 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 1WqO3W-0001Mu-0m for ged-emacs-devel@m.gmane.org; Fri, 30 May 2014 16:45:14 +0200 Original-Received: from localhost ([::1]:54641 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WqO3V-000834-K3 for ged-emacs-devel@m.gmane.org; Fri, 30 May 2014 10:45:13 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:56108) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WqNzE-00010a-PH for emacs-devel@gnu.org; Fri, 30 May 2014 10:40:54 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WqNzC-0007SJ-8F for emacs-devel@gnu.org; Fri, 30 May 2014 10:40:48 -0400 Original-Received: from mail-oa0-x230.google.com ([2607:f8b0:4003:c02::230]:61558) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WqNzB-0007SD-L0 for emacs-devel@gnu.org; Fri, 30 May 2014 10:40:46 -0400 Original-Received: by mail-oa0-f48.google.com with SMTP id g18so1916859oah.35 for ; Fri, 30 May 2014 07:40:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=TslQyTIvhCX9HQr0aUCdTiQRjnKHvlTDhW9SORUJRBI=; b=Z8FahgFRr+L1AYu67GDlH3okp3djYF99pFhb7leLyl7m4BZWtmWXIpdFPiUxnrTKBF zwCgRxoOuCM1NMx4X+dUkBUg3W15cBBp3OrEiQeIB3X1WqgjG9BlmFnGPK1TVrsYEXmi 1QiQapaXVYgYci29pTcYSVH3snzGnZBljX1NXJaWuBIQ/YFcWcux3JR9Fa5QnN7FfoeU G+FJfV1EoP7/7HuiqdJ8etWQwIlyEbEgh9f0njn08d/xGDiIiUGhMMDtssEf6vR9vt8F buLyzKH8T0QntEkIWak49+cXeS88oNAPk2mAiqSenFeLxX8ZNvX/EGaDWNCz/sZCMSxb 8Jxg== X-Received: by 10.182.153.163 with SMTP id vh3mr17633188obb.85.1401460845037; Fri, 30 May 2014 07:40:45 -0700 (PDT) Original-Received: by 10.76.6.44 with HTTP; Fri, 30 May 2014 07:40:44 -0700 (PDT) In-Reply-To: <20140529180441.GA12623@c3po.maths.private.cam.ac.uk> X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:4003:c02::230 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:172193 Archived-At: --089e013d0d5cd5cf6704fa9f0767 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable >> 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 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' > > |\=E2=80=A6 > > | > > > > Literally with the ellipsis. Traversing that edge would take you back > > to the parallel tree you came from: > > > > | =E2=80=A6 > > |/ > > 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 > --089e013d0d5cd5cf6704fa9f0767 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
>> I'm not sure why you say they're largely = incompatible.

> Maybe I overstated it. I meant that treating undo= s 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 i= n 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
bu= ffer changes. Together with the undo-(equiv|redo)-table it conveys
suffi= cient 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
intuitiv= ely traverse it (eg choosing exactly which branch to descend).

>&= gt;> From memory (and git logs), I think that without this mechanism
>>> undo-tree used to sometimes resurrect dead markers when undoin= g. A
>>> lisp package might delete a marker from a buffer and d= rop all
>>> references to it, expecting it to be garbage collec= ted. But
>>> because it was referenced from buffer-undo-tree (a strong
&= gt;>> 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 su= re. I remember it affected normal undo-tree undo, not
> undo-in-regio= n (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
n= ecessarily in the region, and so are swept up into marker
adjustments. T= hey also remain eq over time whilst mutating to point to
various locatio= ns.

The problem was that primitive-undo applied marker adjustments without<= br>concern for whether they moved to unrelated locations. Maybe this
som= ehow contributed to the overlay havoc you had seen.

The vast majorit= y of Elisp packages shouldn't care whether GC is going
to happen sooner or later. So if you think the early removal of marker
a= djustments via compact_undo_list is essential to correct functioning,
I = would wonder why a package depends on that.

Instead, I suspect compa= ct_undo_list is just an optimization. The
asymptotic performance of low level editing functions depends on how
man= y markers there are in the buffer. If it's common for markers to
bec= ome 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
functio= n 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 ove= rlooked it. It ought to simplify
> undo-tree's undo-in-region imp= lementation 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 Cu= bitt <tsc25@cantab.net> wrote:
On Wed, May 28, 2014 at 10:57:15PM -0400, Barry OReilly wro= te:
> 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 t= he visualizer,
then use the motion keybindings).

But as I said, I can't remember a clear rational for not duplicating th= e
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:
>
> =C2=A0 |
> =C2=A0 |
> =C2=A0 A'
> =C2=A0 |\=E2=80=A6
> =C2=A0 |
>
> Literally with the ellipsis. Traversing that edge would take you back<= br> > to the parallel tree you came from:
>
> =C2=A0 | =E2=80=A6
> =C2=A0 |/
> =C2=A0 A
> =C2=A0 |
> =C2=A0 |

I prefer to keep things simple. They generally work better that way.<= br>

> 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<= br> > 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 tha= t
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,<= br> 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 becau= se
> > it was referenced from buffer-undo-tree (a strong reference, rath= er
> > than the specialized buffer-undo-list weak reference), the marker=
> > never got GCd. Undoing a changeset containing the deleted marker<= br> > > 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<= br> > 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-i= n-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 actua= l
> problem either solves.

Storing marker undo elements in buffer-undo-tree fundamentally change= s
the behaviour of markers: they don't get garbage collected, because the= y
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: =C2=A0 www.dr-qu= bit.org

--089e013d0d5cd5cf6704fa9f0767--