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: Integration of undo-tree in Emacs Date: Wed, 28 May 2014 15:38:56 -0400 Message-ID: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=001a11c2ed6c95dfc304fa7af695 X-Trace: ger.gmane.org 1401305956 19110 80.91.229.3 (28 May 2014 19:39:16 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 28 May 2014 19:39:16 +0000 (UTC) Cc: emacs-devel@gnu.org To: toby-undo-tree , Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed May 28 21:39:10 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 1Wpjgq-0002mT-TP for ged-emacs-devel@m.gmane.org; Wed, 28 May 2014 21:39:09 +0200 Original-Received: from localhost ([::1]:44464 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wpjgq-0003nd-GB for ged-emacs-devel@m.gmane.org; Wed, 28 May 2014 15:39:08 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:48819) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wpjgm-0003kB-45 for emacs-devel@gnu.org; Wed, 28 May 2014 15:39:06 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Wpjgf-0003WI-Ts for emacs-devel@gnu.org; Wed, 28 May 2014 15:39:04 -0400 Original-Received: from mail-ob0-x234.google.com ([2607:f8b0:4003:c01::234]:60478) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wpjgf-0003W9-MZ for emacs-devel@gnu.org; Wed, 28 May 2014 15:38:57 -0400 Original-Received: by mail-ob0-f180.google.com with SMTP id va2so11309154obc.39 for ; Wed, 28 May 2014 12:38:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:cc:content-type; bh=ME59eRFBCqGnSSTnWWS9qggfYDu6FfVSvU2QkXQmK2E=; b=T+uQhRniVvgpDGKie91g7DNhwZAylfLDRfQjfKMq9glpmUs07U0yAK/tZFQBWNWnEC KAyw/eXBXLrmSquIBvb1iPLXqfRUa8bAeADvOHq40QDExssBfQseLRifeF3dvzzcg9C9 5mKu4Mo99McOsTwNvufYkjQRel3vDqVa8UBjKfFe6IenWOwriEu4NUZIoAloUkxRmfL7 0okA/Nvw58ctAWHhaXRkG65avP2W8X7K/fdY8OtjHbXxSv/JF5ZctS+TK0fSBcjvvnQB Gl1OLJc+t704O5Y8EpOBSH/J2TQM/xs819nDfqBbyIB4OdSrjRWmZ13tUzShX0W5vcOc TOxA== X-Received: by 10.60.50.197 with SMTP id e5mr2271765oeo.37.1401305936812; Wed, 28 May 2014 12:38:56 -0700 (PDT) Original-Received: by 10.76.6.44 with HTTP; Wed, 28 May 2014 12:38:56 -0700 (PDT) X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:4003:c01::234 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:172165 Archived-At: --001a11c2ed6c95dfc304fa7af695 Content-Type: text/plain; charset=UTF-8 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. --001a11c2ed6c95dfc304fa7af695 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Stefan wrote at
http://debbugs.gnu.org/cgi/bugreport.cgi?bug= =3D16411#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 E= macs. I have some ideas about doing so.

If one conceives of undo history as a tree, then a run of undo
comma= nds means "retrace my edge traversals". Then if you break thatrun, you have to retrace *those* edge traversals.

undo-only means &= quot;go to the parent". This follows from the fact
that edits create new nodes downward in the tree. Recursive
lookup in un= do-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<= br>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 rej= oins it at the
node before the oldest change group undo-in-region drew from.
This conce= ption 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 appe= al of undo-tree is that it allows the user to more
intuitively and direc= tly navigate the underlying tree. If the
user wants to reach other branc= hes 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 tw= o systems to coexist. A
consequence of this is that merely traversing edges in the undo
tree wou= ld cause undo history to grow. This is one reason I raise
the issue of:<= br>
> 4: Deleting X bytes, then doing Y iterations of undo and redo >=C2=A0=C2=A0=C2=A0 causes undo history to grow about X*Y. To grow propo= rtional
>=C2=A0=C2=A0=C2=A0 to Y should be achievable: set undo-in-pr= ogress to the in
>=C2=A0=C2=A0=C2=A0 progress element, and the C leve= l undo recording to use it
>=C2=A0=C2=A0=C2=A0 and undo-redo-table to= find the eq Lisp_String.

But if you're willing to address this concern by eliminating anyrequirement 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 p= rinciple possible to construct a tree visualization of the
undo history.= It is tempting to construct the tree visualization
straight from this d= ata model, but there is at least one drawback
I would like to describe.

When the buffer-undo-list is truncated, we= ak references in the
undo-redo-table are removed. This means "redo = groups" (change
groups created by an undo command) suddenly look li= ke "edit
groups" (change groups created by a normal editing command). This
w= ould change the structure of the tree at GC time. Consider as an
example= :

=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0 A
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 |
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 |
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0 B
=C2=A0=C2=A0=C2=A0 ___|___
=C2=A0=C2=A0 /=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0 \
=C2=A0 E=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0 C
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= |
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 |<= br>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 D

[Note: This uses undo-tree's convention of newer branches on= the
left.]

The user's movement through the tree is:

=C2=A0 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 rem= ovals
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:

=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 C
=C2=A0=C2=A0=C2=A0 ___|___=C2=A0=C2=A0 /=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 \
=C2=A0 B=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 D
=C2=A0 |
=C2=A0 |
=C2=A0 E

This kind of tree change at seemingly random times m= ight be very
surprising to the user, albeit granted the parent-child rev= ersals
will tend to occur away from the user's local part of the tre= e.
The alternative and less surprising approach, which undo-tree
takes, is = to truncate nodes least recently visited, making no
other tree transform= ation. So A is first in line for truncation
followed by E, B, C, D. I th= ink this can be done in an integrated
undo-tree, but with greater effort. Do you have a strong opinion
about t= his, Stefan?

Toby, are there other reasons undo-tree needs to transf= er undo
elements from the buffer-undo-list to its own data model?

Finally, I have a couple of questions about the 2010 post at
ht= tp://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 unmarke= d 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 trans= fers 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 b= ecause 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 marke= r 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.

--001a11c2ed6c95dfc304fa7af695--