From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Barry OReilly Newsgroups: gmane.emacs.bugs Subject: bug#16411: undo-only bugs Date: Sat, 18 Jan 2014 19:58:14 -0500 Message-ID: References: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=089e0122912c1fa7a504f04845c5 X-Trace: ger.gmane.org 1390093155 19666 80.91.229.3 (19 Jan 2014 00:59:15 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 19 Jan 2014 00:59:15 +0000 (UTC) Cc: 16411@debbugs.gnu.org To: Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Sun Jan 19 01:59:20 2014 Return-path: Envelope-to: geb-bug-gnu-emacs@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 1W4gjP-00083M-GZ for geb-bug-gnu-emacs@m.gmane.org; Sun, 19 Jan 2014 01:59:19 +0100 Original-Received: from localhost ([::1]:44727 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W4gjP-0003Zd-6l for geb-bug-gnu-emacs@m.gmane.org; Sat, 18 Jan 2014 19:59:19 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:43107) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W4gjF-0003ZX-TH for bug-gnu-emacs@gnu.org; Sat, 18 Jan 2014 19:59:15 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1W4gj9-0001dH-Jt for bug-gnu-emacs@gnu.org; Sat, 18 Jan 2014 19:59:09 -0500 Original-Received: from debbugs.gnu.org ([140.186.70.43]:42454) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W4gj9-0001dB-Cu for bug-gnu-emacs@gnu.org; Sat, 18 Jan 2014 19:59:03 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1W4gj8-0001o3-Gg for bug-gnu-emacs@gnu.org; Sat, 18 Jan 2014 19:59:02 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Barry OReilly Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 19 Jan 2014 00:59:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 16411 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: Original-Received: via spool by 16411-submit@debbugs.gnu.org id=B16411.13900931016874 (code B ref 16411); Sun, 19 Jan 2014 00:59:02 +0000 Original-Received: (at 16411) by debbugs.gnu.org; 19 Jan 2014 00:58:21 +0000 Original-Received: from localhost ([127.0.0.1]:56473 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1W4giS-0001mk-28 for submit@debbugs.gnu.org; Sat, 18 Jan 2014 19:58:21 -0500 Original-Received: from mail-ob0-f171.google.com ([209.85.214.171]:36412) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1W4giN-0001mX-V1 for 16411@debbugs.gnu.org; Sat, 18 Jan 2014 19:58:16 -0500 Original-Received: by mail-ob0-f171.google.com with SMTP id wp4so713354obc.16 for <16411@debbugs.gnu.org>; Sat, 18 Jan 2014 16:58:14 -0800 (PST) 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 :cc:content-type; bh=5BBlDdTUOBQirAZP2vJbPDTZpk5kPb6gYHkUdZIRQ+Q=; b=MZqTRvqKTQ36sZMpcEVzohl4MBKteMTazE0HNrpE7CbEZLU/Tg77i3YNE49Ew7HIZW FE1y+KG35rP+mPU6tTxePZVI2SsOBskUi1mr/iqcy5zYzPhjlJrEcYWuZDrQKQtadko3 QyvnS72UyGc8j+XeocSuf39+Ym2xITlgfdF+2yfJKx+eKjU2U2zZ8hM7WB9LnXDh1RzK 4bc7yW+bvC0ZbLEgtg+wY9Wc6ABA509XtoSC5s1GOrR7s7QtQKWKl2N4+wou0NB3EJgt lXfhIe4eB8wjSYH2lgcEvCgyhAgmXhmuW1CpdK9xbtpRgMuqqmjuvQrzrSq2mHCnj68u TGSg== X-Received: by 10.60.98.174 with SMTP id ej14mr8752651oeb.16.1390093094855; Sat, 18 Jan 2014 16:58:14 -0800 (PST) Original-Received: by 10.76.21.84 with HTTP; Sat, 18 Jan 2014 16:58:14 -0800 (PST) In-Reply-To: X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 140.186.70.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:83697 Archived-At: --089e0122912c1fa7a504f04845c5 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable After looking at and considering more of the undo code, here's my current thinking about how to solve bug 2. The Elisp manual states that undo elements of buffer-undo-list can be of the form: (apply delta beg end funname . args) Define a "redo element" as an element of buffer-undo-list created because of an undo command. Suppose we change the way redo elements are represented to: (apply delta beg end 'undo-redo . (undone-element undo-delta)) Where: =95 delta, beg, end are as documented. =95 undo-redo is a new function that copies undone-element, applies undo-delta, then calls primitive-undo on it. =95 undone-element is the undone element of buffer-undo-list. =95 undo-delta is (position . offset) indicating how undo-redo should modify a copy of undone-element in order to carry out the redo. When executing undo-only: =95 Assume pending-undo-list can be lazily computed =95 Let undo-skip-set be an empty set of undo elements to skip =95 Iterate over pending-undo-list until prefix-arg undos complete: =95 If the element is in undo-skip-set: =95 Remove it from undo-skip-set =95 Continue loop =95 If the element is of the form for a redo element: =95 Insert its undone-element in the undo-skip-set =95 Else undo the element Using a BST for the undo-skip-set would be appropriate, but I don't see that one is available to core Elisp code. A skip list data structure would be a simple option with similar performance characteristics. Note: this is a different kind of "skip", you can duckduckgo "skip lists". In your earlier reply, you hinted that switching undo-only from using the undo-equiv-table to calling undo-make-selective-list might create a noticable performance regression. The latter is O(N*N) for N sized undo history! I would expect undo-only will generally have an element to find, in which case, being able to compute next elements of pending-undo-list as needed instead of in full upfront may be a sufficient solution. If it isn't sufficient, I can also make the algorithm O(N*log(N)). One way to do this is using another skip list to store the undo-deltas: sort by position, and at each node store the sum of the offsets over the skip interval following that node. The analogous thing can be done with a BST: put the sum of a subtree's offsets at each node. This is more complex in part because the sums need to be updated during tree rotations. There's another benefit to my proposed representation for redo elements. Consider the use case: =95 Delete text X bytes large =95 Do Y cycles of undo and redo As I understand the current code, the size of undo history grows by approximately X*Y. With this new way to represent redo elements, undo history grows approximately Y instead. This proposal implies recursive calls to primitive-undo. The size of the Lisp call stack would be a function of how deep redo records refer to undone redo records. Maybe there are reasonable ways to deal with that or maybe it's a non issue. Are there examples of existing code putting (apply delta beg end funname . args) into the buffer-undo-list? I want to see what the options might be for pushing redo elements in that format. The best I can think of right now is a dynamically bound variable set only during an undo and examined in record functions in undo.c. There's more I could say about other details, but I'll stop now to get feedback on the overall idea. --089e0122912c1fa7a504f04845c5 Content-Type: text/html; charset=windows-1252 Content-Transfer-Encoding: quoted-printable
After looking at and considering more of the undo code, he= re's my
current thinking about how to solve bug 2.

The Elisp = manual states that undo elements of buffer-undo-list can be
of the form:=

=A0 (apply delta beg end funname . args)

Define a "redo ele= ment" as an element of buffer-undo-list created
because of an undo = command. Suppose we change the way redo elements
are represented to:

=A0 (apply delta beg end 'undo-redo . (undone-element undo-delta))<= br>
Where:
=A0 =95 delta, beg, end are as documented.
=A0 =95 undo= -redo is a new function that copies undone-element, applies
=A0=A0=A0 un= do-delta, then calls primitive-undo on it.
=A0 =95 undone-element is the undone element of buffer-undo-list.
=A0 = =95 undo-delta is (position . offset) indicating how undo-redo should
= =A0=A0=A0 modify a copy of undone-element in order to carry out the redo.
When executing undo-only:
=A0 =95 Assume pending-undo-list can be lazily computed
=A0 =95 Let undo= -skip-set be an empty set of undo elements to skip
=A0 =95 Iterate over = pending-undo-list until prefix-arg undos complete:
=A0=A0=A0 =95 If the = element is in undo-skip-set:
=A0=A0=A0=A0=A0 =95 Remove it from undo-skip-set
=A0=A0=A0=A0=A0 =95 Con= tinue loop
=A0=A0=A0 =95 If the element is of the form for a redo elemen= t:
=A0=A0=A0=A0=A0 =95 Insert its undone-element in the undo-skip-set=A0=A0=A0 =95 Else undo the element

Using a BST for the undo-skip-s= et would be appropriate, but I don't
see that one is available to core Elisp code. A skip list data
structure= would be a simple option with similar performance
characteristics. Note= : this is a different kind of "skip", you can
duckduckgo "= ;skip lists".

In your earlier reply, you hinted that switching undo-only from usingthe undo-equiv-table to calling undo-make-selective-list might create
= a noticable performance regression. The latter is O(N*N) for N sized
undo history! I would expect undo-only will generally have an element
to= find, in which case, being able to compute next elements of
pending-und= o-list as needed instead of in full upfront may be a
sufficient solution= .

If it isn't sufficient, I can also make the algorithm O(N*log(N)).<= br>One way to do this is using another skip list to store the
undo-delta= s: sort by position, and at each node store the sum of the
offsets over = the skip interval following that node. The analogous
thing can be done with a BST: put the sum of a subtree's offsets at
= each node. This is more complex in part because the sums need to be
upda= ted during tree rotations.

There's another benefit to my propose= d representation for redo
elements. Consider the use case:
=A0 =95 Delete text X bytes large
= =A0 =95 Do Y cycles of undo and redo

As I understand the current cod= e, the size of undo history grows by
approximately X*Y. With this new wa= y to represent redo elements, undo
history grows approximately Y instead.

This proposal implies recursi= ve calls to primitive-undo. The size of
the Lisp call stack would be a f= unction of how deep redo records refer
to undone redo records. Maybe the= re are reasonable ways to deal with
that or maybe it's a non issue.

Are there examples of existing c= ode putting (apply delta beg end
funname . args) into the buffer-undo-li= st? I want to see what the
options might be for pushing redo elements in= that format. The best I
can think of right now is a dynamically bound variable set only during
a= n undo and examined in record functions in undo.c.

There's more = I could say about other details, but I'll stop now to get
feedback o= n the overall idea.

--089e0122912c1fa7a504f04845c5--