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#17235: Undo in region adjusts past positions incorrectly Date: Thu, 10 Apr 2014 10:00:06 -0400 Message-ID: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 X-Trace: ger.gmane.org 1397138480 20394 80.91.229.3 (10 Apr 2014 14:01:20 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 10 Apr 2014 14:01:20 +0000 (UTC) To: 17235@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Thu Apr 10 16:01:13 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 1WYFXV-000771-Dk for geb-bug-gnu-emacs@m.gmane.org; Thu, 10 Apr 2014 16:01:13 +0200 Original-Received: from localhost ([::1]:52019 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WYFXV-0003Bp-3h for geb-bug-gnu-emacs@m.gmane.org; Thu, 10 Apr 2014 10:01:13 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:34989) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WYFXQ-0003Bj-Va for bug-gnu-emacs@gnu.org; Thu, 10 Apr 2014 10:01:10 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WYFXK-0007K8-UE for bug-gnu-emacs@gnu.org; Thu, 10 Apr 2014 10:01:08 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:48534) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WYFXK-0007K4-Qb for bug-gnu-emacs@gnu.org; Thu, 10 Apr 2014 10:01:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1WYFXK-0005Mf-In for bug-gnu-emacs@gnu.org; Thu, 10 Apr 2014 10:01: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: Thu, 10 Apr 2014 14:01:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 17235 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: X-Debbugs-Original-To: emacs bugs Original-Received: via spool by submit@debbugs.gnu.org id=B.139713842217707 (code B ref -1); Thu, 10 Apr 2014 14:01:02 +0000 Original-Received: (at submit) by debbugs.gnu.org; 10 Apr 2014 14:00:22 +0000 Original-Received: from localhost ([127.0.0.1]:39876 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WYFWf-0004ag-BR for submit@debbugs.gnu.org; Thu, 10 Apr 2014 10:00:21 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:33103) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WYFWd-0004SJ-CB for submit@debbugs.gnu.org; Thu, 10 Apr 2014 10:00:20 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WYFWW-0006vV-Uz for submit@debbugs.gnu.org; Thu, 10 Apr 2014 10:00:14 -0400 Original-Received: from lists.gnu.org ([2001:4830:134:3::11]:60169) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WYFWW-0006vR-Sn for submit@debbugs.gnu.org; Thu, 10 Apr 2014 10:00:12 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:34819) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WYFWV-0002Fa-Lo for bug-gnu-emacs@gnu.org; Thu, 10 Apr 2014 10:00:12 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WYFWR-0006sz-Ki for bug-gnu-emacs@gnu.org; Thu, 10 Apr 2014 10:00:11 -0400 Original-Received: from mail-oa0-x22b.google.com ([2607:f8b0:4003:c02::22b]:57954) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WYFWR-0006sf-GM for bug-gnu-emacs@gnu.org; Thu, 10 Apr 2014 10:00:07 -0400 Original-Received: by mail-oa0-f43.google.com with SMTP id eb12so4474395oac.2 for ; Thu, 10 Apr 2014 07:00:06 -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:content-type; bh=n7q5UyhmTrFWOowd5TgL6leQfRRTLr796WdrCPGdThQ=; b=nQMTD277ZojM4W6eTAIxxXoutOHMa1gN0oL2ognyW2+e5HBs9aHwTzeUd24uo5cbCw g34GS8lrUE8kMXAAprvxGzbrQ5eWmaIKWzQierYaMAMyiPYhSvuxgYkRmpW+uMUm+d8z OfmaUqvmf+xJmfBzoemkw9gSNtbxAHao32MMi4va+cEVo81RuK2LEv/vUxBdlzgn5Nl1 geXqGTfKrVbACf7MkSlIWwj7MoRt+FQAB/W46rQecyZhnByn17S2vc1x2z/wTfMbVbhD AnnIv9wl5c8mTnAMHd5xjf2DzIqX0Ji/lBc508YJqrPRPBD0JXg+WNjHxWA74Gz89jW5 p8Pg== X-Received: by 10.182.118.169 with SMTP id kn9mr14308100obb.46.1397138406446; Thu, 10 Apr 2014 07:00:06 -0700 (PDT) Original-Received: by 10.76.6.44 with HTTP; Thu, 10 Apr 2014 07:00:06 -0700 (PDT) X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). 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:87924 Archived-At: I constructed a recipe using emacs -Q to demonstrate a flaw in undo-make-selective-list. Each bullet should be a distinct change group: * Insert 12345 * Delete the 4, buffer has: 1235 * Insert xxxx such that: xxxx1235 * Insert yy such that: xxxxyy1235 * Select "35", undo in region, expected 4 to come back, but nothing changed * Select "1235", undo in region, the 4 returns to the wrong place, buffer has: xxxxyy14235 After these steps are executed in *scratch*, buffer-undo-list is: (nil (199 . 200) nil (196 . 198) nil (192 . 196) nil (#("4" 0 1 (fontified t)) . -195) nil (192 . 197) (t . 0) nil (1 . 192) (t . 0)) Clearly the (196 . 198) ought to have caused the ("4" . -195) to adjust by 2, but it didn't because its adjustment due to (192 . 196) was not applied yet. I think the algorithm would be simpler to make correct if adjustments are applied forward chronologically rather than backwards. That is, the algorithm keeps a list of undo-deltas that grows as the algorithm iterates backwards through undo history. As it does so, the positions are adjusted chronologically forward through the undo-deltas. This approach is O(N**2), as the current algorithm also is, but the bright side is the proposed algorithm lends itself to short circuiting better than the current. Let me know if you have other ideas and I'll prepare a patch.