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: Sun, 19 Jan 2014 11:57:21 -0500 Message-ID: References: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=089e013d0dc033b4f404f055ab14 X-Trace: ger.gmane.org 1390150694 728 80.91.229.3 (19 Jan 2014 16:58:14 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 19 Jan 2014 16:58:14 +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 17:58:21 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 1W4vhS-0000yB-VS for geb-bug-gnu-emacs@m.gmane.org; Sun, 19 Jan 2014 17:58:19 +0100 Original-Received: from localhost ([::1]:46920 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W4vhS-0004fB-Fj for geb-bug-gnu-emacs@m.gmane.org; Sun, 19 Jan 2014 11:58:18 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:48517) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W4vhJ-0004es-Qv for bug-gnu-emacs@gnu.org; Sun, 19 Jan 2014 11:58:15 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1W4vhC-00046g-Pd for bug-gnu-emacs@gnu.org; Sun, 19 Jan 2014 11:58:09 -0500 Original-Received: from debbugs.gnu.org ([140.186.70.43]:43232) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W4vhC-00046I-Lr for bug-gnu-emacs@gnu.org; Sun, 19 Jan 2014 11:58:02 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1W4vhC-00005p-20 for bug-gnu-emacs@gnu.org; Sun, 19 Jan 2014 11:58: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 16:58:01 +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.139015064632767 (code B ref 16411); Sun, 19 Jan 2014 16:58:01 +0000 Original-Received: (at 16411) by debbugs.gnu.org; 19 Jan 2014 16:57:26 +0000 Original-Received: from localhost ([127.0.0.1]:57251 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1W4vgb-0008WO-SF for submit@debbugs.gnu.org; Sun, 19 Jan 2014 11:57:26 -0500 Original-Received: from mail-ob0-f182.google.com ([209.85.214.182]:38934) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1W4vgY-0008WF-Rj for 16411@debbugs.gnu.org; Sun, 19 Jan 2014 11:57:23 -0500 Original-Received: by mail-ob0-f182.google.com with SMTP id wm4so758719obc.13 for <16411@debbugs.gnu.org>; Sun, 19 Jan 2014 08:57:22 -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=kFkl+If+gY6ffuPr39cgplqq0U33t1u4lYo5UaHnnKE=; b=AwVLSiJgf8krhExJBE8ryZb3o7UyiCWZjd6m0PwCs8Wb3P8Wj/lujOUcL9kR+8bOGn /xzGOigMzdAxxXKNNX1irYW0/g71pTe69yoSiBD0u8fwZcxWYOl1MjV9pmGLzJxsnvUZ Rkai62ptp6ttIoYmgl4jIWuN4ec8tIr45YVCa2auQBIPp/s/Pdcc8kyAIHPUArL12O8D D5ftOdvelXC3TyYCj0Y2IBYlazzIt28r87QdjzSK0fAg9wOseFLJK+0E2JOhTC+UUC7j ltAZ8agPwUxDRz04aXt0Ur1KiOktikWBtgvghY3DXgdY9Z7scaA20RY+ajYSSzec8KFN XSCg== X-Received: by 10.182.153.226 with SMTP id vj2mr12023520obb.26.1390150642020; Sun, 19 Jan 2014 08:57:22 -0800 (PST) Original-Received: by 10.76.21.84 with HTTP; Sun, 19 Jan 2014 08:57:21 -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:83731 Archived-At: --089e013d0dc033b4f404f055ab14 Content-Type: text/plain; charset=ISO-8859-1 > (I thought we had already understood how to fix bug 2, BTW) No, we both agreed about how to fix bug 1, which isn't too hard or intrusive. I'm talking about bug 2 now. I appreciate you taking the time to discuss it with me. You said about it: > IIUC, you're talking of skipping (e.g. in a non-region undo) the > undos that took place during undo-in-region, right? If so, I don't > have an answer for how we could do that, in general. If you require the solution use undo-equiv-table, then I would have to also admit to not having an answer. > why not skip all these elements in one swoop as we currently do with > undo-equiv-table Because it would not be correct. I constructed recipe 2 in order to demonstrate the incorrectness. > In which way would this help fixing bug 2 Recipe 2 used an undo-in-region to trick the current undo-only behavior into finding the wrong element to undo. Under my proposed solution, undo-in-region creates a change group of redo elements, each with a reference to its undone-element. This allows undo-only to find the correct element to undo per the algorithm I described. Why is it correct? undo-only wishes to find the most recent non redo element A which is currently in the buffer (ie the net effect is it's not undone). If A is reachable through an odd number of hops across undo-element references, then it is undone, if even it is not undone. If there exist paths to A both even and odd in length, then something strange has happened to the undo history. The effect of skipping undo elements as I described it is to exclude the ones with odd length paths. For example, consider: A1 undoes A2 undoes A3 undoes A4 undoes A5 A2 and A4 will find themselves in the undo-skip-set, the others won't. undo-only correctly finds A5 as the element to undo. B1 undoes B2 undoes B3 undoes B4 undoes B5 undoes B6 B2, B4, B6 will be skipped, so undo-only will have to find some other non B element to undo, as it should in this case. > the step "Insert its undone-element in the undo-skip-set" means that > we skip this "redo" element, which means that all the subsequent > elements (until the matching undone-element) may have incorrect > buffer positions. I explained this: I would rework the pending-undo-list computation to be lazier, perhaps creating a get-next-pending-undo function instead of computing the entire pending-undo-list upfront. undo-only would use this function to get the next copy of an element of buffer-undo-list, with positions adjusted using an index of undo-delta sums. get-next-pending-undo would be part of "Iterate over pending-undo-list", which means we are adjusting positions whether the element will be skipped or not. This rework to use a new get-next-pending-undo can be a self contained patch which would benefit undo in region's performance right away, even if undo-only doesn't use it after just the first patch. > But it's still dangerous and wasteful By dangerous do you mean incorrect? By wasteful do you mean non performant? Maybe the discussion will be less confusing if we focus on correctness first, then move to performance? Could you describe what part of my proposal is incorrect? --089e013d0dc033b4f404f055ab14 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
> (I thought we had already understood how to fix bug 2= , BTW)

No, we both agreed about how to fix bug 1, which isn't to= o hard or
intrusive. I'm talking about bug 2 now. I appreciate you t= aking the
time to discuss it with me. You said about it:

> IIUC, you're= talking of skipping (e.g. in a non-region undo) the
> undos that too= k place during undo-in-region, right? If so, I don't
> have an an= swer for how we could do that, in general.

If you require the solution use undo-equiv-table, then I would have to<= br>also admit to not having an answer.

> why not skip all these e= lements in one swoop as we currently do with
> undo-equiv-table

Because it would not be correct. I constructed recipe 2 in order to
= demonstrate the incorrectness.

> In which way would this help fix= ing bug 2

Recipe 2 used an undo-in-region to trick the current undo-= only
behavior into finding the wrong element to undo. Under my proposed
solut= ion, undo-in-region creates a change group of redo elements, each
with a= reference to its undone-element. This allows undo-only to find
the corr= ect element to undo per the algorithm I described.

Why is it correct? undo-only wishes to find the most recent non redoelement A which is currently in the buffer (ie the net effect is it's<= br>not undone). If A is reachable through an odd number of hops across
undo-element references, then it is undone, if even it is not undone.
If= there exist paths to A both even and odd in length, then something
stra= nge has happened to the undo history. The effect of skipping undo
elemen= ts as I described it is to exclude the ones with odd length
paths. For example, consider:

=A0 A1 undoes A2 undoes A3 undoes A4 u= ndoes A5

A2 and A4 will find themselves in the undo-skip-set, the ot= hers won't.
undo-only correctly finds A5 as the element to undo.

=A0 B1 undoes B2 undoes B3 undoes B4 undoes B5 undoes B6

B2, B4,= B6 will be skipped, so undo-only will have to find some other
non B ele= ment to undo, as it should in this case.

> the step "Insert = its undone-element in the undo-skip-set" means that
> we skip this "redo" element, which means that all the subseq= uent
> elements (until the matching undone-element) may have incorrec= t
> buffer positions.

I explained this: I would rework the pen= ding-undo-list computation to
be lazier, perhaps creating a get-next-pending-undo function instead
of = computing the entire pending-undo-list upfront. undo-only would use
this= function to get the next copy of an element of buffer-undo-list,
with p= ositions adjusted using an index of undo-delta sums.
get-next-pending-undo would be part of "Iterate over
pending-undo-l= ist", which means we are adjusting positions whether the
element wi= ll be skipped or not.

This rework to use a new get-next-pending-undo= can be a self contained
patch which would benefit undo in region's performance right away,
e= ven if undo-only doesn't use it after just the first patch.

>= But it's still dangerous and wasteful

By dangerous do you mean = incorrect? By wasteful do you mean non
performant? Maybe the discussion will be less confusing if we focus on
c= orrectness first, then move to performance? Could you describe what
part= of my proposal is incorrect?

--089e013d0dc033b4f404f055ab14--