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: Wed, 14 May 2014 17:56:52 -0400 Message-ID: References: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=001a11c3224615af9504f963420c X-Trace: ger.gmane.org 1400104708 27374 80.91.229.3 (14 May 2014 21:58:28 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 14 May 2014 21:58:28 +0000 (UTC) Cc: 16411 <16411@debbugs.gnu.org> To: Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Wed May 14 23:58: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 1WkhBq-0003jy-KB for geb-bug-gnu-emacs@m.gmane.org; Wed, 14 May 2014 23:58:18 +0200 Original-Received: from localhost ([::1]:54661 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkhBq-00030h-AL for geb-bug-gnu-emacs@m.gmane.org; Wed, 14 May 2014 17:58:18 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:40013) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkhBi-00030S-BI for bug-gnu-emacs@gnu.org; Wed, 14 May 2014 17:58:15 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WkhBa-0006mA-Np for bug-gnu-emacs@gnu.org; Wed, 14 May 2014 17:58:10 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:41871) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkhBa-0006lh-Kx for bug-gnu-emacs@gnu.org; Wed, 14 May 2014 17:58:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1WkhBa-0007Sh-3e for bug-gnu-emacs@gnu.org; Wed, 14 May 2014 17:58:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Barry OReilly Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 14 May 2014 21:58: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.140010462228549 (code B ref 16411); Wed, 14 May 2014 21:58:02 +0000 Original-Received: (at 16411) by debbugs.gnu.org; 14 May 2014 21:57:02 +0000 Original-Received: from localhost ([127.0.0.1]:34935 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WkhAb-0007Q7-Bk for submit@debbugs.gnu.org; Wed, 14 May 2014 17:57:02 -0400 Original-Received: from mail-ob0-f176.google.com ([209.85.214.176]:55044) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WkhAY-0007Pf-O8 for 16411@debbugs.gnu.org; Wed, 14 May 2014 17:56:59 -0400 Original-Received: by mail-ob0-f176.google.com with SMTP id wo20so225691obc.7 for <16411@debbugs.gnu.org>; Wed, 14 May 2014 14:56:52 -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 :cc:content-type; bh=AfnBxUoI0qqQu5p1JDGA1XwgXj89tGF7iN05ZIereDs=; b=Q37hQOeV+Paq9S/HyhranA5E/v8K7a56aazzC40nDQ5Xz/+6Z4gOOii2W4EdDPIW7v xsOu4kwAxehENiCsWKYygLEP+MFMGdcsgtPdpit7BBaJUp0JlIr+Qoy+FvDns71wfcPp 7EJ7o0+1QfUbrE3WgFwswKjmQvuW0++M86Z3cIf+Wr9jHmzgCgj79M5ajQVgj77E32hm s9vYnuTymIzkXizN8xUr5g10AcdyiRJR4fCKuntMleXLAzU+nTRmv0qNKct0BQJ17SyH 2X7wx/pR6IP1SlCSRDBFqUMl70om8S+ptqSsJcBqFtfFuDy3ByQPAgmCub56zTLRa/ub zxbQ== X-Received: by 10.182.246.40 with SMTP id xt8mr5321392obc.76.1400104612636; Wed, 14 May 2014 14:56:52 -0700 (PDT) Original-Received: by 10.76.6.44 with HTTP; Wed, 14 May 2014 14:56:52 -0700 (PDT) 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:89111 Archived-At: --001a11c3224615af9504f963420c Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable > You talk here about "undo element", but AFAICT this actually points > to "a list of undo elements" (where the first element of that list > is presumably the "undo element" you mean). Please clarify. Yes, that's right. The first element is the "undo element" referred to. The cons is put in the hash table to facilitate recursive lookup. > My guess is that the "undo-only" case would skip redo entries in > much the same way as undo-in-region skips "out of bounds" entries > (i.e. in a fairly expensive way, adjusting all subsequent elements). Sort of, but some of those skipped elements will cancel each other out rather than adjust positions. See http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D16411#5 . It's worth noting that undo-only might have to "mop up" a change group partially undone by a prior undo in region, so a non regional undo-only might also reference a partial change group. > Combined with the fact that undo-redo-table contains entries for > every redo element rather than for every redo group, I'm slightly > worried about the resource use I mulled over the same concern. undo-redo-table would probably be larger than undo-equiv-table, though still a constant factor of undo limit, IIUC. Implementing the "Y undo-redos of X" optimization is a mitigating benefit. I considered having the undo elements themselves reference what they undid. Unfortunately, this approach would probably break current undo-tree. Also, the references need to be weak, and I can only think to do that by wrapping them in one element weak hash tables, defeating the point. > [ Nitpick: the first line of the docstring should stand on its own. ] I don't understand, I thought I formatted the docstring like others, and did M-q it. > IIUC this undo-redo-table business is only necessary because of > undo-in-region. So I think we should strive to minimize the changes > to the way undo works in the absence of undo-in-region. I understand > that the change can't be all localized in undo-in-region (because of > the need to skip "redo-in-region" during normal undo-only, > basically), but we still should try to aim in that direction. I think you're saying to not pursue the use of a closure to generate successive undo elements as needed? I'm fine with that, but I did so because: =E2=80=A2 I'm trying to prevent a performance regression of the undo-only command. Given the performance of undo in region with the default undo limit, maybe that's not a big concern. =E2=80=A2 I'm concerned that undo-make-selective-list's O(N**2) algorithm= is unfriendly to those who want to increase the undo limit. The generator allows for minimal processing of the history as needed. Admittedly, I have not experimented with greater undo limits. =E2=80=A2 I have to muck with the interfaces regardless -- undo-make-selective-list still needs to deliver both the adjusted element and the orig-tail to the higher undo code. > IIUC the crux of the matter is how to record the redo data for an > undo-in-region. The way I see it, for such a "redo-in-region" group, > we indeed need to remember which elements it undid (and which ones > it skipped instead), but we could store that info as a single entry > in an undo-redo/equiv-table. I originally set out to do this, but making the weak references work seemed overly tricky to me. The value stored in undo-redo-table would need to be non weak with weak references to undo elements. I supposed this would mean many one element weak hash tables. That seems dodgy. --001a11c3224615af9504f963420c Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
> You talk here about "undo element", but AFA= ICT this actually points
> to "a list of undo elements" (wh= ere the first element of that list
> is presumably the "undo ele= ment" you mean). Please clarify.

Yes, that's right. The first element is the "undo element"= ; referred
to. The cons is put in the hash table to facilitate recursive= lookup.

> My guess is that the "undo-only" case would = skip redo entries in
> much the same way as undo-in-region skips "out of bounds" en= tries
> (i.e. in a fairly expensive way, adjusting all subsequent ele= ments).

Sort of, but some of those skipped elements will cancel each= other out
rather than adjust positions. See
http://debbugs.gnu.org/cgi/bugreport.cgi?bug= =3D16411#5 .

It's worth noting that undo-only might have to = "mop up" a change group
partially undone by a prior undo in region, so a non regional
undo-only = might also reference a partial change group.

> Combined with the = fact that undo-redo-table contains entries for
> every redo element r= ather than for every redo group, I'm slightly
> worried about the resource use

I mulled over the same concern. = undo-redo-table would probably be
larger than undo-equiv-table, though s= till a constant factor of undo
limit, IIUC. Implementing the "Y und= o-redos of X" optimization is a
mitigating benefit.

I considered having the undo elements themselves= reference what they
undid. Unfortunately, this approach would probably = break current
undo-tree. Also, the references need to be weak, and I can= only think
to do that by wrapping them in one element weak hash tables, defeating
t= he point.

> [ Nitpick: the first line of the docstring should sta= nd on its own.=C2=A0 ]

I don't understand, I thought I formatted= the docstring like others,
and did M-q it.

> IIUC this undo-redo-table business is only nece= ssary because of
> undo-in-region. So I think we should strive to min= imize the changes
> to the way undo works in the absence of undo-in-r= egion. I understand
> that the change can't be all localized in undo-in-region (because = of
> the need to skip "redo-in-region" during normal undo-o= nly,
> basically), but we still should try to aim in that direction.<= br>
I think you're saying to not pursue the use of a closure to generat= e
successive undo elements as needed? I'm fine with that, but I did = so
because:

=C2=A0 =E2=80=A2 I'm trying to prevent a performa= nce regression of the undo-only
=C2=A0=C2=A0=C2=A0 command. Given the performance of undo in region with th= e default
=C2=A0=C2=A0=C2=A0 undo limit, maybe that's not a big conc= ern.

=C2=A0 =E2=80=A2 I'm concerned that undo-make-selective-lis= t's O(N**2) algorithm is
=C2=A0=C2=A0=C2=A0 unfriendly to those who = want to increase the undo limit. The
=C2=A0=C2=A0=C2=A0 generator allows for minimal processing of the history a= s needed.
=C2=A0=C2=A0=C2=A0 Admittedly, I have not experimented with gr= eater undo limits.

=C2=A0 =E2=80=A2 I have to muck with the interfac= es regardless --
=C2=A0=C2=A0=C2=A0 undo-make-selective-list still needs= to deliver both the adjusted
=C2=A0=C2=A0=C2=A0 element and the orig-tail to the higher undo code.
> IIUC the crux of the matter is how to record the redo data for an> undo-in-region. The way I see it, for such a "redo-in-region&quo= t; group,
> we indeed need to remember which elements it undid (and which ones
= > it skipped instead), but we could store that info as a single entry> in an undo-redo/equiv-table.

I originally set out to do this, = but making the weak references work
seemed overly tricky to me. The value stored in undo-redo-table would
ne= ed to be non weak with weak references to undo elements. I supposed
this= would mean many one element weak hash tables. That seems dodgy.

--001a11c3224615af9504f963420c--