bug#16818: Undo in region after markers in undo history relocated

bug#16818: Undo in region after markers in undo history relocated

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 2385 bytes --]

Strange behavior with the following recipe, using trunk:

  * ./src/emacs -Q
  * Move point up two lines
  * Insert "aaa"
  * Undo
  * Move point down two lines
  * Insert "bbb"
  * Select "bbb" from end to beginning and delete
  * Insert "bbb"
  * Go to line where "aaa" was and select the line from beginning to
    end
  * Undo in region
  * Observe:
    * "Undo in region!" is echoed in the minibuffer
    * Unexpectedly, "aaa" is not reinserted back into the buffer
    * Strangely, the selection mark at BOL moves forward three chars
  * Undo in region again
  * Observe:
    * "aaa" is reinserted, despite selection no longer covering the
      region where "aaa" was

Prior to the first undo in region, buffer-undo-list is:

  (nil (192 . 195) nil (bbb . 192) (#<marker at 141 in *scratch*> . -3)
(#<marker at 192 in *scratch*> . -3) (#<marker at 190 in *scratch*> . -3)
nil (192 . 195) (t . 0) nil (aaa . 141) nil (141 . 144) (t . 0) nil (1 .
192) (t . 0))

And after undo-make-selective-list pending-undo-list becomes:

  (nil (#<marker at 141 in *scratch*> . -3) (#<marker at 190 in *scratch*>
. -3) nil (aaa . 141) nil (141 . 144) nil)

It seems the #<marker at 141 in *scratch*> is the mark used during
selection. When bbb is deleted, the mark is recorded into undo
history, and it's still there when the selection mark has moved to
position 141 before "aaa". So:

> * Unexpectedly, "aaa" is not reinserted back into the buffer

is due to the selection mark and another marker occupying their own
change group in the filtered pending-undo-list, and that change group
is chosen for the first undo in region.

> Strangely, the selection mark at BOL moves forward three chars

is due to the -3 marker adjustment.

> * "aaa" is reinserted, despite selection no longer covering the
    region where "aaa" was

is simply due to pending-undo-list being reused for the second
consecutive undo, unaware that the selection mark was adjusted.

I haven't determined what those other two markers are. But the general
question comes up: how is the undo history meant to know about marker
relocations?

The code in adjust_markers_for_delete indicates markers are only
recorded when they would be in a deleted region or immediately before
it, so I think the only circumstance markers form their own undesired
change group in the pending-undo-list is when recorded markers
were relocated.

[-- Attachment #2: Type: text/html, Size: 3080 bytes --]

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 399 bytes --]

Another question: what is the purpose of undo-adjusted-markers?
simple.el is the only file I found that references it, and it's only
setting the variable without using it.

I found the specialized GC treatment of undo history markers in
compact_undo_list, so merely having references to the markers via
undo-adjusted-markers might be a motivation. But I can't think of a
particular reason for that.

[-- Attachment #2: Type: text/html, Size: 464 bytes --]

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Stefan Monnier]

> Another question: what is the purpose of undo-adjusted-markers?
> simple.el is the only file I found that references it, and it's only
> setting the variable without using it.

I don't see that.  It's set *and* read in undo-elt-in-region.
Not sure exactly what is the purpose, tho.


        Stefan

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 457 bytes --]

> I don't see that. It's set *and* read in undo-elt-in-region. Not
> sure exactly what is the purpose, tho.

I found no purpose at all for it.

The more pertinent question is:

> the general question comes up: how is the undo history meant to know
> about marker relocations?

I think the marker adjustment entries in the undo history are invalid
when a marker is relocated elsewhere. I don't see code to deal with
that, so how you would like it to happen?

[-- Attachment #2: Type: text/html, Size: 551 bytes --]

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 2813 bytes --]

> > the general question comes up: how is the undo history meant to
> > know about marker relocations?

> I think the marker adjustment entries in the undo history are
> invalid when a marker is relocated elsewhere. I don't see code to
> deal with that, so how you would like it to happen?

I found the Elisp manual says about moving markers:

  When you do this, be sure you know whether the marker is used
  outside of your program, and, if so, what effects will result from
  moving it--otherwise, confusing things may happen in other parts of
  Emacs.

So if we expand on the guidance as follows:

diff --git a/doc/lispref/markers.texi b/doc/lispref/markers.texi
index 51b87ab..19386d6 100644
--- a/doc/lispref/markers.texi
+++ b/doc/lispref/markers.texi
@@ -344,10 +344,12 @@ specify the insertion type, create them with
insertion type
 @section Moving Marker Positions

   This section describes how to change the position of an existing
-marker.  When you do this, be sure you know whether the marker is used
-outside of your program, and, if so, what effects will result from
-moving it---otherwise, confusing things may happen in other parts of
-Emacs.
+marker.  When you do this, be sure you know how the marker is used
+outside of your program.  For example, moving a marker to an unrelated
+new position can cause undo to later adjust the marker incorrectly.
+Often when you wish to relocate a marker to an unrelated position, it
+is preferable to make a new marker and set the prior one to point
+nowhere.

 @defun set-marker marker position &optional buffer
 This function moves @var{marker} to @var{position}

then we don't need to worry about markers in general, only the
particular offending ones of the recipe.

As I described, one offending marker is the mark-marker. From the
push-mark function:

(defun push-mark (&optional location nomsg activate)
  [...]
    (setq mark-ring (cons (copy-marker (mark-marker)) mark-ring))
  [...]
  (set-marker (mark-marker) (or location (point)) (current-buffer))
  [...]
  (setq global-mark-ring (cons (copy-marker (mark-marker))
global-mark-ring))
  )

Two copies are made and the copies go to the mark-ring and
global-mark-ring. The mark continues to be the same marker object
under eq as before, only mutated. Consequently, not only does undo
adjust a marker it shouldn't have, but it doesn't adjust the copies in
the rings when it should have.

What makes more sense to me is that the old value of mark-marker is
pushed onto the rings, then a new marker object is created to become
the value of mark-marker. Then the marker adjustment records would
reference the right markers. Effectively this means the mark would
follow the advice of the Elisp manual excerpt above.

I welcome your guidance about what the right way to solve this bug is.
Thank you.

[-- Attachment #2: Type: text/html, Size: 3232 bytes --]

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Stefan Monnier]

> What makes more sense to me is that the old value of mark-marker is
> pushed onto the rings, then a new marker object is created to become
> the value of mark-marker. Then the marker adjustment records would
> reference the right markers. Effectively this means the mark would
> follow the advice of the Elisp manual excerpt above.

That sounds right.  I don't have time to really understand the ins and
outs, but if you can write an ERT test case for it, we could install
the change.


        Stefan

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 267 bytes --]

> That sounds right. I don't have time to really understand the ins
> and outs, but if you can write an ERT test case for it, we could
> install the change.

Thanks. The doc patch is relevant with or without a fix, so I'll
install that soon if there's no objections.

[-- Attachment #2: Type: text/html, Size: 335 bytes --]

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 13870 bytes --]

>> What makes more sense to me is that the old value of mark-marker is
>> pushed onto the rings, then a new marker object is created to
>> become the value of mark-marker. Then the marker adjustment records
>> would reference the right markers. Effectively this means the mark
>> would follow the advice of the Elisp manual excerpt above.

> That sounds right. I don't have time to really understand the ins
> and outs, but if you can write an ERT test case for it, we could
> install the change.

At the end is a patch to implement this. I wrote the marker-tests to
make sure I didn't break anything too badly, they pass with or without
the rest of the patch. The new undo-test-mark-adjustment implements
the recipe of this bug report. It fails with current trunk and passes
with the patch.

Of the original symptoms of this bug report, the patch solves:

>> Strangely, the selection mark at BOL moves forward three chars

but not:

>> * Unexpectedly, "aaa" is not reinserted back into the buffer
> is due to the selection mark and another marker occupying their own
> change group in the filtered pending-undo-list, and that change
> group is chosen for the first undo in region.

The selection mark is no longer "in the way" on the pending-undo-list,
but the another marker still is. It only is when the recipe is carried
out manually apparently, because the marker is not there when the
recipe is carried out in the undo-test-mark-adjustment. IOW, the ERT
test passes the same test case that fails when carried out manually.

Debugging the C sources, I find the offending marker in the
pending-undo-list is first created at the following C and Lisp
backtraces:

Obtained 31 stack frames.
./src/emacs [0x52c2b4]
./src/emacs(Fmake_overlay+0xf2) [0x526062]
./src/emacs(Ffuncall+0x371) [0x5729c1]
./src/emacs(exec_byte_code+0x3a5) [0x5a42e5]
./src/emacs(Ffuncall+0x20c) [0x57285c]
./src/emacs(exec_byte_code+0x3a5) [0x5a42e5]
./src/emacs(Ffuncall+0x20c) [0x57285c]
./src/emacs(exec_byte_code+0x3a5) [0x5a42e5]
./src/emacs(Ffuncall+0x20c) [0x57285c]
./src/emacs(eval_sub+0x6a8) [0x572118]
./src/emacs(internal_lisp_condition_case+0x21b) [0x574cbb]
./src/emacs(exec_byte_code+0x12fa) [0x5a523a]
./src/emacs(Ffuncall+0x20c) [0x57285c]
./src/emacs(Fapply+0x2c7) [0x572fe7]
./src/emacs(Ffuncall+0x422) [0x572a72]
./src/emacs(exec_byte_code+0x3a5) [0x5a42e5]
./src/emacs(Ffuncall+0x20c) [0x57285c]
./src/emacs(internal_condition_case_n+0xfe) [0x5713ce]
./src/emacs(safe_call+0x138) [0x463298]
./src/emacs [0x4814f4]
./src/emacs(read_char+0x965) [0x50f3b5]
./src/emacs [0x510bad]
./src/emacs(command_loop_1+0x27e) [0x51267e]
./src/emacs(internal_condition_case+0xda) [0x57101a]
./src/emacs [0x5097ca]
./src/emacs(internal_catch+0xd8) [0x570ef8]
./src/emacs(recursive_edit_1+0x120) [0x508d00]
./src/emacs(Frecursive_edit+0xc7) [0x50a687]
./src/emacs(main+0x8ed) [0x5016ad]
/lib64/libc.so.6(__libc_start_main+0xf4) [0x31cf01d994]
./src/emacs [0x43b369]
  make-overlay(192 193)
  #[1028 "Á\x01!„\x1cÂ\x04\x04\\x02!ˆÃ\x01Ä#ˆÃ\x01Ã
Æ#ˆ‰‡Ç\x01!p=ƒ4È\x01!\x04=ƒ4É\x01!\x03=„;Ê\x01p$ˆ‡"
[redisplay-unhighlight-region-function overlayp make-overlay overlay-put
window face region overlay-buffer overlay-start overlay-end move-overlay] 9
"

(fn START END WINDOW ROL)"](192 193 #<window 3 on *scratch*> nil)
  redisplay--update-region-highlight(#<window 3 on *scratch*>)
  #[0 "À¢„
ÃÄ !‡À¢<„\x18Àà ƉÇ# ˆ ƒ\"ÈÃÀ¢\"‡É  )Ê À¢‰ S‰@‰Ä
=„>‰\x03=ƒEÃ\x01!ˆ‚L
Ë\x02Ì\"!ˆ\x01A¶‚‚+²\x01‡" [((#<window 3 on *scratch*>))
highlight-nonselected-windows redisplay-unhighlight-region-function
redisplay--update-region-highlight selected-window window-list-1 nil t mapc
window-minibuffer-p minibuffer-selected-window window-parameter
internal-region-overlay] 7 "

(fn)"]()
  funcall(#[0 "À¢„
ÃÄ !‡À¢<„\x18Àà ƉÇ# ˆ ƒ\"ÈÃÀ¢\"‡É  )Ê À¢‰ S‰@‰Ä
=„>‰\x03=ƒEÃ\x01!ˆ‚L
Ë\x02Ì\"!ˆ\x01A¶‚‚+²\x01‡" [((#<window 3 on *scratch*>))
highlight-nonselected-windows redisplay-unhighlight-region-function
redisplay--update-region-highlight selected-window window-list-1 nil t mapc
window-minibuffer-p minibuffer-selected-window window-parameter
internal-region-overlay] 7 "

(fn)"])
  redisplay--update-region-highlights((#<window 3 on *scratch*>))
  apply(redisplay--update-region-highlights (#<window 3 on *scratch*>))
  #[128 "ÀÁ\x02\"ˆÀÂ\x02\"‡" [apply redisplay--update-region-highlights
ignore nil] 4 nil nil]((#<window 3 on *scratch*>))
  redisplay_internal\ \(C\ function\)()

Following the redisplay code indicated, it looks like the same overlay
object is reused for subsequent region selections. If so, the
explanation is similar as for the mark: the marker of the
internal-region-overlay is the same under eq when "bbb" is selected
and deleted as when the line formerly containing "aaa" is selected
followed by undo in region. The marker adjustment is incorrectly found
because the marker moved, and consequently the "aaa" undo record is
not found. Would the solution be analogous as for the mark: make a new
overlay for each new region selection?

Finally, here's the patch that fixes this problem wrt the mark:

diff --git a/lisp/simple.el b/lisp/simple.el
index f9447b1..5b7970c 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -4399,11 +4399,11 @@ If NO-TMM is non-nil, leave `transient-mark-mode'
alone."
       (setq transient-mark-mode 'lambda))
     (run-hooks 'activate-mark-hook)))

-(defun set-mark (pos)
-  "Set this buffer's mark to POS.  Don't use this function!
-That is to say, don't use this function unless you want
-the user to see that the mark has moved, and you want the previous
-mark position to be lost.
+(defun set-mark (pos-or-marker)
+  "Set this buffer's mark to POS-OR-MARKER.  Don't use this
+function!  That is to say, don't use this function unless you
+want the user to see that the mark has moved, and you want the
+previous mark position to be lost.

 Normally, when a new mark is set, the old one should go on the stack.
 This is why most applications should use `push-mark', not `set-mark'.
@@ -4415,9 +4415,10 @@ To remember a location for internal use in the Lisp
program,
 store it in a Lisp variable.  Example:

    (let ((beg (point))) (forward-line 1) (delete-region beg (point)))."
-
-  (set-marker (mark-marker) pos (current-buffer))
-  (if pos
+  (if (markerp pos-or-marker)
+      (setq mark pos-or-marker)
+    (set-marker (mark-marker) pos-or-marker (current-buffer)))
+  (if pos-or-marker
       (activate-mark 'no-tmm)
     ;; Normally we never clear mark-active except in Transient Mark mode.
     ;; But when we actually clear out the mark value too, we must
@@ -4639,10 +4640,12 @@ purposes.  See the documentation of `set-mark' for
more information.

 In Transient Mark mode, activate mark if optional third arg ACTIVATE
non-nil."
   (unless (null (mark t))
-    (setq mark-ring (cons (copy-marker (mark-marker)) mark-ring))
+    (push (mark-marker) mark-ring)
     (when (> (length mark-ring) mark-ring-max)
-      (move-marker (car (nthcdr mark-ring-max mark-ring)) nil)
+      ;; Remove from mark-ring.  Note that marker may be in
+      ;; global-mark-ring, so don't point it nowhere.
       (setcdr (nthcdr (1- mark-ring-max) mark-ring) nil)))
+  (set-mark (copy-marker (mark-marker)))
   (set-marker (mark-marker) (or location (point)) (current-buffer))
   ;; Now push the mark on the global mark ring.
   (if (and global-mark-ring
@@ -4650,9 +4653,8 @@ In Transient Mark mode, activate mark if optional
third arg ACTIVATE non-nil."
       ;; The last global mark pushed was in this same buffer.
       ;; Don't push another one.
       nil
-    (setq global-mark-ring (cons (copy-marker (mark-marker))
global-mark-ring))
+    (push (mark-marker) global-mark-ring)
     (when (> (length global-mark-ring) global-mark-ring-max)
-      (move-marker (car (nthcdr global-mark-ring-max global-mark-ring))
nil)
       (setcdr (nthcdr (1- global-mark-ring-max) global-mark-ring) nil)))
   (or nomsg executing-kbd-macro (> (minibuffer-depth) 0)
       (message "Mark set"))
@@ -4664,11 +4666,9 @@ In Transient Mark mode, activate mark if optional
third arg ACTIVATE non-nil."
   "Pop off mark ring into the buffer's actual mark.
 Does not set point.  Does nothing if mark ring is empty."
   (when mark-ring
-    (setq mark-ring (nconc mark-ring (list (copy-marker (mark-marker)))))
-    (set-marker (mark-marker) (+ 0 (car mark-ring)) (current-buffer))
-    (move-marker (car mark-ring) nil)
-    (if (null (mark t)) (ding))
-    (setq mark-ring (cdr mark-ring)))
+    (setq mark-ring (nconc mark-ring (list (mark-marker))))
+    (set-mark (pop mark-ring))
+    (if (null (mark t)) (ding)))
   (deactivate-mark))

 (define-obsolete-function-alias
diff --git a/src/buffer.c b/src/buffer.c
index 90c1542..d811515 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -5161,6 +5161,7 @@ init_buffer_once (void)
   bset_abbrev_table (&buffer_defaults, Qnil);
   bset_display_table (&buffer_defaults, Qnil);
   bset_undo_list (&buffer_defaults, Qnil);
+  bset_mark (&buffer_defaults, Qnil);
   bset_mark_active (&buffer_defaults, Qnil);
   bset_file_format (&buffer_defaults, Qnil);
   bset_auto_save_file_format (&buffer_defaults, Qt);
@@ -5219,6 +5220,7 @@ init_buffer_once (void)
   bset_major_mode (&buffer_local_flags, make_number (-1));
   bset_mode_name (&buffer_local_flags, make_number (-1));
   bset_undo_list (&buffer_local_flags, make_number (-1));
+  bset_mark (&buffer_local_flags, make_number (-1));
   bset_mark_active (&buffer_local_flags, make_number (-1));
   bset_point_before_scroll (&buffer_local_flags, make_number (-1));
   bset_file_truename (&buffer_local_flags, make_number (-1));
@@ -6124,6 +6126,9 @@ the changes between two undo boundaries as a single
step to be undone.

 If the value of the variable is t, undo information is not recorded.  */);

+  DEFVAR_PER_BUFFER ("mark", &BVAR (current_buffer, mark), Qnil,
+                    doc: /* The buffer's mark.  */);
+
   DEFVAR_PER_BUFFER ("mark-active", &BVAR (current_buffer, mark_active),
Qnil,
                     doc: /* Non-nil means the mark and region are
currently active in this buffer.  */);

diff --git a/test/automated/marker-tests.el b/test/automated/marker-tests.el
new file mode 100644
index 0000000..87ebf82
--- /dev/null
+++ b/test/automated/marker-tests.el
@@ -0,0 +1,59 @@
+;;; marker-tests.el --- tests for common markers such as the mark -*-
lexical-binding:t -*-
+
+;; Copyright (C) 2014 Free Software Foundation, Inc.
+
+;; This file is part of GNU Emacs.
+
+;; GNU Emacs is free software: you can redistribute it and/or modify
+;; it under the terms of the GNU General Public License as published by
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
+
+;; GNU Emacs is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+;; GNU General Public License for more details.
+
+;; You should have received a copy of the GNU General Public License
+;; along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.
+
+;;; Commentary:
+
+;;; Code:
+
+(ert-deftest marker-tests-mark-rings ()
+  (let ((buf1 (generate-new-buffer "buf1"))
+        (buf2 (generate-new-buffer "buf2")))
+    (set-buffer buf1)
+    (insert "abcdefg")
+    (push-mark 1)
+    (goto-char 2)
+    (push-mark)
+    (set-buffer buf2)
+    (insert "ABCDEFG")
+    (push-mark)
+    (set-buffer buf1)
+    (pop-global-mark)
+    (should (eq (current-buffer) (marker-buffer (mark-marker))))
+    (should (eq (current-buffer) buf2))
+    (goto-char 3)
+    (pop-mark) ; Shouldn't go anywhere, mark-ring empty
+    (should (= 3 (point)))
+    (pop-global-mark)
+    (should (eq (current-buffer) buf1))
+    (push-mark 4)
+    (should (= 4 (mark t)))
+    (goto-char 5)
+    (exchange-point-and-mark)
+    (should (= 4 (point)))
+    (should (= 5 (marker-position (mark-marker))))
+    (pop-mark)
+    (should (= 2 (mark t)))
+    (pop-mark)
+    (should (= 1 (mark t)))
+    (should (= 4 (point)))
+    (should (eq (current-buffer) buf1))))
+
+;;; marker-tests.el ends here
+
+
diff --git a/test/automated/undo-tests.el b/test/automated/undo-tests.el
index 8a963f1..a4ed95e 100644
--- a/test/automated/undo-tests.el
+++ b/test/automated/undo-tests.el
@@ -268,6 +268,46 @@
     (should (string= (buffer-string)
                      "This sentence corrupted?aaa"))))

+(ert-deftest undo-test-mark-adjustment ()
+  "Test that the mark's marker adjustment in undo history doesn't
+  obstruct undo in region from finding the correct change group.
+  Demonstrates bug 16818."
+  (with-temp-buffer
+    (buffer-enable-undo)
+    (transient-mark-mode 1)
+    (insert "First line\n")
+    (insert "Second line\n")
+    (undo-boundary)
+
+    (goto-char (point-min))
+    (insert "aaa")
+    (undo-boundary)
+
+    (undo)
+    (undo-boundary)
+
+    (goto-char (point-max))
+    (insert "bbb")
+    (undo-boundary)
+
+    (push-mark (point) t t)
+    (setq mark-active t)
+    (goto-char (- (point) 3))
+    (delete-forward-char 1)
+    (undo-boundary)
+
+    (insert "bbb")
+    (undo-boundary)
+
+    (goto-char (point-min))
+    (push-mark (point) t t)
+    (setq mark-active t)
+    (goto-char (+ (point) 3))
+    (undo)
+    (undo-boundary)
+
+    (should (string= (buffer-string) "aaaFirst line\nSecond line\nbbb"))))
+
 (defun undo-test-all (&optional interactive)
   "Run all tests for \\[undo]."
   (interactive "p")

[-- Attachment #2: Type: text/html, Size: 15348 bytes --]

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Stefan Monnier]

> At the end is a patch to implement this. I wrote the marker-tests to
> make sure I didn't break anything too badly, they pass with or without
> the rest of the patch. The new undo-test-mark-adjustment implements
> the recipe of this bug report. It fails with current trunk and passes
> with the patch.

Thinking more about this, I think this is fixing the symptom, but not
the cause.  The cause is that primitive-undo shouldn't blindly
obey a (MARKER . OFFSET) entry.  Instead it should only obey it if the
marker still points at the corresponding place.

Your patch works around the problem by trying to avoid moving the mark
(creating new markers each time instead) but that doesn't fix the
problem for the other markers.

Problem is: the undo log format as it stands does not record in
a reliable way what was the marker's position at that time, so it's not
easy to figure out whether the marker is still at the "same place"
or not.

This said, in practice, those (MARKER . OFFSET) entries are only
introduced for text deletion.  So we should normally find them
immediately after a (STRING . POS) and those (MARKER . OFFSET) should
only be applied if that MARKER was at POS before undoing the deletion
of STRING.

IOW, I think the right fix is to change primitive-undo's handling of
(STRING . POS) by first looking at subsequent (MARKER . OFFSET) entries
and dropping those whose MARKER is not currently at POS.

WDYT?


        Stefan

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 855 bytes --]

> Thinking more about this, I think this is fixing the symptom, but
> not the cause. The cause is that primitive-undo shouldn't blindly
> obey a (MARKER . OFFSET) entry. Instead it should only obey it if
> the marker still points at the corresponding place.

From what I can tell, the root cause is relocating markers to
unrelated locations in the buffer while another part of Emacs still
has a reference to it.

Your counter proposal is a step from the root. For instance, the
markers within the mark rings will not adjust correctly, whilst with
my patch they will.

I think your proposal sounds good nonetheless. I don't doubt there are
other markers that could get swept up into the undo history, become
relocated, and then annoy users of undo in region.

> (creating new markers each time instead)

My patch actually results in fewer markers created.

[-- Attachment #2: Type: text/html, Size: 968 bytes --]

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Stefan Monnier]

>> Thinking more about this, I think this is fixing the symptom, but
>> not the cause. The cause is that primitive-undo shouldn't blindly
>> obey a (MARKER . OFFSET) entry. Instead it should only obey it if
>> the marker still points at the corresponding place.

> From what I can tell, the root cause is relocating markers to
> unrelated locations in the buffer while another part of Emacs still
> has a reference to it.

Not sure in which way what you're saying is different from what I'm saying.
Are we in violent agreement?

> Your counter proposal is a step from the root.  For instance, the
> markers within the mark rings will not adjust correctly, whilst with
> my patch they will.

Can you give an example incorrect adjustment?

>> (creating new markers each time instead)
> My patch actually results in fewer markers created.

Right, I didn't mean that creating new markers is a problem.


        Stefan

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Stefan Monnier]

>> Your counter proposal is a step from the root.  For instance, the
>> markers within the mark rings will not adjust correctly, whilst with
>> my patch they will.
> Can you give an example incorrect adjustment?

Oh, I think I see: with the current code, the mark-ring gets copies of
markers and those copies are made "late", so if you do "C-SPC, some
deletion around point, and then C-SPC", a new marker for the first C-SPC
is pushed on the mark-ring, but the undo-log has an adjustment for
mark-marker rather than for that new marker.

IOW, I think the primitive-undo fix is needed and your fix is also needed.
I think your fix is too risky for the 24.4, tho (IOW, please wait for
the trunk to re-open before installing it).  The primitive-undo fix
should be safe enough for 24.4, so if you want to code this up and
install it, feel free.


        Stefan

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 838 bytes --]

> Oh, I think I see: with the current code, the mark-ring gets copies of
> markers and those copies are made "late", so if you do "C-SPC, some
> deletion around point, and then C-SPC", a new marker for the first C-SPC
> is pushed on the mark-ring, but the undo-log has an adjustment for
> mark-marker rather than for that new marker.

> IOW, I think the primitive-undo fix is needed and your fix is also
> needed.

Yes that's right. Parents cover their childrens' eyes at the violence
of our agreement.

I just discovered my patch has a bug. If I C-SPC first thing after
starting Emacs, an error is signaled because the mark is nil. I had
hoped the mark variable initialized equivalently except to make itself
available to Lisp. There are clearly holes in my understanding of the
initialization business. I'll debug that at a later time.

[-- Attachment #2: Type: text/html, Size: 975 bytes --]

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Barry OReilly]

[-- Attachment #1.1: Type: text/plain, Size: 206 bytes --]

> The primitive-undo fix should be safe enough for 24.4, so if you
> want to code this up and install it, feel free.

I have attached the patch for this, which I'll install if nothing
comes up from review.

[-- Attachment #1.2: Type: text/html, Size: 258 bytes --]

[-- Attachment #2: undo-skip-markers.diff --]
[-- Type: text/plain, Size: 16365 bytes --]

diff --git a/lisp/ChangeLog b/lisp/ChangeLog
index a1ee5bb..a53f5d6 100644
--- a/lisp/ChangeLog
+++ b/lisp/ChangeLog
@@ -1,3 +1,13 @@
+2014-03-13  Barry O'Reilly  <gundaetiapo@gmail.com>
+
+	* simple.el (primitive-undo): When adjusting a marker, check that
+	its position is still valid.  (Bug#16818)
+	(undo-make-selective-list): Determine whether a marker adjustment
+	is in the region based on whether the deletion that recorded it in
+	undo history is in the region.  Remove variable adjusted-markers,
+	which was unused and only non nil during undo-make-selective-list.
+	(undo-elt-in-region): New optional argument MARKER-VALIDITY-POS.
+
 2014-03-13  Dmitry Gutov  <dgutov@yandex.ru>
 
 	* progmodes/ruby-mode.el (ruby-font-lock-keywords): Fontify
diff --git a/lisp/simple.el b/lisp/simple.el
index 881a633..a72cf8b 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -2229,85 +2229,90 @@ Return what remains of the list."
         (did-apply nil)
         (next nil))
     (while (> arg 0)
-      (while (setq next (pop list))     ;Exit inner loop at undo boundary.
-        ;; Handle an integer by setting point to that value.
-        (pcase next
-          ((pred integerp) (goto-char next))
-          ;; Element (t . TIME) records previous modtime.
-          ;; Preserve any flag of NONEXISTENT_MODTIME_NSECS or
-          ;; UNKNOWN_MODTIME_NSECS.
-          (`(t . ,time)
-           ;; If this records an obsolete save
-           ;; (not matching the actual disk file)
-           ;; then don't mark unmodified.
-           (when (or (equal time (visited-file-modtime))
-                     (and (consp time)
-                          (equal (list (car time) (cdr time))
-                                 (visited-file-modtime))))
-             (when (fboundp 'unlock-buffer)
-               (unlock-buffer))
-             (set-buffer-modified-p nil)))
-          ;; Element (nil PROP VAL BEG . END) is property change.
-          (`(nil . ,(or `(,prop ,val ,beg . ,end) pcase--dontcare))
-           (when (or (> (point-min) beg) (< (point-max) end))
-             (error "Changes to be undone are outside visible portion of buffer"))
-           (put-text-property beg end prop val))
-          ;; Element (BEG . END) means range was inserted.
-          (`(,(and beg (pred integerp)) . ,(and end (pred integerp)))
-           ;; (and `(,beg . ,end) `(,(pred integerp) . ,(pred integerp)))
-           ;; Ideally: `(,(pred integerp beg) . ,(pred integerp end))
-           (when (or (> (point-min) beg) (< (point-max) end))
-             (error "Changes to be undone are outside visible portion of buffer"))
-           ;; Set point first thing, so that undoing this undo
-           ;; does not send point back to where it is now.
-           (goto-char beg)
-           (delete-region beg end))
-          ;; Element (apply FUN . ARGS) means call FUN to undo.
-          (`(apply . ,fun-args)
-           (let ((currbuff (current-buffer)))
-             (if (integerp (car fun-args))
-                 ;; Long format: (apply DELTA START END FUN . ARGS).
-                 (pcase-let* ((`(,delta ,start ,end ,fun . ,args) fun-args)
-                              (start-mark (copy-marker start nil))
-                              (end-mark (copy-marker end t)))
-                   (when (or (> (point-min) start) (< (point-max) end))
-                     (error "Changes to be undone are outside visible portion of buffer"))
-                   (apply fun args) ;; Use `save-current-buffer'?
-                   ;; Check that the function did what the entry
-                   ;; said it would do.
-                   (unless (and (= start start-mark)
-                                (= (+ delta end) end-mark))
-                     (error "Changes to be undone by function different than announced"))
-                   (set-marker start-mark nil)
-                   (set-marker end-mark nil))
-               (apply fun-args))
-             (unless (eq currbuff (current-buffer))
-               (error "Undo function switched buffer"))
-             (setq did-apply t)))
-          ;; Element (STRING . POS) means STRING was deleted.
-          (`(,(and string (pred stringp)) . ,(and pos (pred integerp)))
-           (when (let ((apos (abs pos)))
-                   (or (< apos (point-min)) (> apos (point-max))))
-             (error "Changes to be undone are outside visible portion of buffer"))
-           (if (< pos 0)
-               (progn
-                 (goto-char (- pos))
-                 (insert string))
-             (goto-char pos)
-             ;; Now that we record marker adjustments
-             ;; (caused by deletion) for undo,
-             ;; we should always insert after markers,
-             ;; so that undoing the marker adjustments
-             ;; put the markers back in the right place.
-             (insert string)
-             (goto-char pos)))
-          ;; (MARKER . OFFSET) means a marker MARKER was adjusted by OFFSET.
-          (`(,(and marker (pred markerp)) . ,(and offset (pred integerp)))
-           (when (marker-buffer marker)
-             (set-marker marker
-                         (- marker offset)
-                         (marker-buffer marker))))
-          (_ (error "Unrecognized entry in undo list %S" next))))
+      (let (del-pos)
+        (while (setq next (pop list))     ;Exit inner loop at undo boundary.
+          ;; Handle an integer by setting point to that value.
+          (pcase next
+            ((pred integerp) (goto-char next))
+            ;; Element (t . TIME) records previous modtime.
+            ;; Preserve any flag of NONEXISTENT_MODTIME_NSECS or
+            ;; UNKNOWN_MODTIME_NSECS.
+            (`(t . ,time)
+             ;; If this records an obsolete save
+             ;; (not matching the actual disk file)
+             ;; then don't mark unmodified.
+             (when (or (equal time (visited-file-modtime))
+                       (and (consp time)
+                            (equal (list (car time) (cdr time))
+                                   (visited-file-modtime))))
+               (when (fboundp 'unlock-buffer)
+                 (unlock-buffer))
+               (set-buffer-modified-p nil)))
+            ;; Element (nil PROP VAL BEG . END) is property change.
+            (`(nil . ,(or `(,prop ,val ,beg . ,end) pcase--dontcare))
+             (when (or (> (point-min) beg) (< (point-max) end))
+               (error "Changes to be undone are outside visible portion of buffer"))
+             (put-text-property beg end prop val))
+            ;; Element (BEG . END) means range was inserted.
+            (`(,(and beg (pred integerp)) . ,(and end (pred integerp)))
+             ;; (and `(,beg . ,end) `(,(pred integerp) . ,(pred integerp)))
+             ;; Ideally: `(,(pred integerp beg) . ,(pred integerp end))
+             (when (or (> (point-min) beg) (< (point-max) end))
+               (error "Changes to be undone are outside visible portion of buffer"))
+             ;; Set point first thing, so that undoing this undo
+             ;; does not send point back to where it is now.
+             (goto-char beg)
+             (delete-region beg end))
+            ;; Element (apply FUN . ARGS) means call FUN to undo.
+            (`(apply . ,fun-args)
+             (let ((currbuff (current-buffer)))
+               (if (integerp (car fun-args))
+                   ;; Long format: (apply DELTA START END FUN . ARGS).
+                   (pcase-let* ((`(,delta ,start ,end ,fun . ,args) fun-args)
+                                (start-mark (copy-marker start nil))
+                                (end-mark (copy-marker end t)))
+                     (when (or (> (point-min) start) (< (point-max) end))
+                       (error "Changes to be undone are outside visible portion of buffer"))
+                     (apply fun args) ;; Use `save-current-buffer'?
+                     ;; Check that the function did what the entry
+                     ;; said it would do.
+                     (unless (and (= start start-mark)
+                                  (= (+ delta end) end-mark))
+                       (error "Changes to be undone by function different than announced"))
+                     (set-marker start-mark nil)
+                     (set-marker end-mark nil))
+                 (apply fun-args))
+               (unless (eq currbuff (current-buffer))
+                 (error "Undo function switched buffer"))
+               (setq did-apply t)))
+            ;; Element (STRING . POS) means STRING was deleted.
+            (`(,(and string (pred stringp)) . ,(and pos (pred integerp)))
+             (when (let ((apos (abs pos)))
+                     (or (< apos (point-min)) (> apos (point-max))))
+               (error "Changes to be undone are outside visible portion of buffer"))
+             (setq del-pos pos)
+             (if (< pos 0)
+                 (progn
+                   (goto-char (- pos))
+                   (insert string))
+               (goto-char pos)
+               ;; Now that we record marker adjustments
+               ;; (caused by deletion) for undo,
+               ;; we should always insert after markers,
+               ;; so that undoing the marker adjustments
+               ;; put the markers back in the right place.
+               (insert string)
+               (goto-char pos)))
+            ;; (MARKER . OFFSET) means a marker MARKER was adjusted by OFFSET.
+            (`(,(and marker (pred markerp)) . ,(and offset (pred integerp)))
+             (when (and del-pos
+                        (integerp (marker-position marker))
+                        (= del-pos marker)
+                        (marker-buffer marker))
+               (set-marker marker
+                           (- marker offset)
+                           (marker-buffer marker))))
+            (_ (error "Unrecognized entry in undo list %S" next)))))
       (setq arg (1- arg)))
     ;; Make sure an apply entry produces at least one undo entry,
     ;; so the test in `undo' for continuing an undo series
@@ -2341,8 +2346,6 @@ are ignored.  If BEG and END are nil, all undo elements are used."
 	    (undo-make-selective-list (min beg end) (max beg end))
 	  buffer-undo-list)))
 
-(defvar undo-adjusted-markers)
-
 (defun undo-make-selective-list (start end)
   "Return a list of undo elements for the region START to END.
 The elements come from `buffer-undo-list', but we keep only
@@ -2351,18 +2354,30 @@ If we find an element that crosses an edge of this region,
 we stop and ignore all further elements."
   (let ((undo-list-copy (undo-copy-list buffer-undo-list))
 	(undo-list (list nil))
-	undo-adjusted-markers
+        ;; The position of a deletion record (TEXT . POSITION) of the
+        ;; current change group.
+        ;;
+        ;; This is used to check that marker adjustmenets are in the
+        ;; region.  Bug 16818 describes why the marker's position is
+        ;; not suitable.
+        del-pos
 	some-rejected
 	undo-elt temp-undo-list delta)
     (while undo-list-copy
       (setq undo-elt (car undo-list-copy))
+      ;; Update del-pos
+      (if undo-elt
+          (when (and (consp undo-elt) (stringp (car undo-elt)))
+            (setq del-pos (cdr undo-elt)))
+        ;; Undo boundary means new change group, so unset del-pos
+        (setq del-pos nil))
       (let ((keep-this
 	     (cond ((and (consp undo-elt) (eq (car undo-elt) t))
 		    ;; This is a "was unmodified" element.
 		    ;; Keep it if we have kept everything thus far.
 		    (not some-rejected))
 		   (t
-		    (undo-elt-in-region undo-elt start end)))))
+		    (undo-elt-in-region undo-elt start end del-pos)))))
 	(if keep-this
 	    (progn
 	      (setq end (+ end (cdr (undo-delta undo-elt))))
@@ -2415,9 +2430,13 @@ we stop and ignore all further elements."
       (setq undo-list-copy (cdr undo-list-copy)))
     (nreverse undo-list)))
 
-(defun undo-elt-in-region (undo-elt start end)
+(defun undo-elt-in-region (undo-elt start end &optional marker-validity-pos)
   "Determine whether UNDO-ELT falls inside the region START ... END.
-If it crosses the edge, we return nil."
+If it crosses the edge, we return nil.
+
+If undo-elt is a (MARKER . ADJUSTMENT) record, either
+MARKER-VALIDITY-POS (if specified) or the marker's position is
+used to determine whether it is in the region."
   (cond ((integerp undo-elt)
 	 (and (>= undo-elt start)
 	      (<= undo-elt end)))
@@ -2430,17 +2449,9 @@ If it crosses the edge, we return nil."
 	 (and (>= (abs (cdr undo-elt)) start)
 	      (<= (abs (cdr undo-elt)) end)))
 	((and (consp undo-elt) (markerp (car undo-elt)))
-	 ;; This is a marker-adjustment element (MARKER . ADJUSTMENT).
-	 ;; See if MARKER is inside the region.
-	 (let ((alist-elt (assq (car undo-elt) undo-adjusted-markers)))
-	   (unless alist-elt
-	     (setq alist-elt (cons (car undo-elt)
-				   (marker-position (car undo-elt))))
-	     (setq undo-adjusted-markers
-		   (cons alist-elt undo-adjusted-markers)))
-	   (and (cdr alist-elt)
-		(>= (cdr alist-elt) start)
-		(<= (cdr alist-elt) end))))
+	 ;; (MARKER . ADJUSTMENT)
+         (let ((mpos (or marker-validity-pos (marker-position (car undo-elt)))))
+           (and (integerp mpos) (<= start mpos end))))
 	((null (car undo-elt))
 	 ;; (nil PROPERTY VALUE BEG . END)
 	 (let ((tail (nthcdr 3 undo-elt)))
diff --git a/test/ChangeLog b/test/ChangeLog
index c87022c..e7ee14e 100644
--- a/test/ChangeLog
+++ b/test/ChangeLog
@@ -1,3 +1,11 @@
+2014-03-13  Barry O'Reilly  <gundaetiapo@gmail.com>
+
+	* undo-tests.el (undo-test-marker-adjustment-nominal): New test of
+	marker adjustments.
+	(undo-test-marker-adjustment-moved):
+	(undo-test-region-mark-adjustment): Two new test to demonstrate
+	bug#16818.
+
 2014-03-07  Michael Albinus  <michael.albinus@gmx.de>
 
 	* automated/tramp-tests.el (tramp-copy-size-limit): Declare.
diff --git a/test/automated/undo-tests.el b/test/automated/undo-tests.el
index 8a963f1..a348549 100644
--- a/test/automated/undo-tests.el
+++ b/test/automated/undo-tests.el
@@ -268,6 +268,80 @@
     (should (string= (buffer-string)
                      "This sentence corrupted?aaa"))))
 
+(ert-deftest undo-test-marker-adjustment-nominal ()
+  "Test nominal behavior of marker adjustments."
+  (with-temp-buffer
+    (buffer-enable-undo)
+    (insert "abcdefg")
+    (undo-boundary)
+    (let ((m (make-marker)))
+      (set-marker m 2 (current-buffer))
+      (goto-char (point-min))
+      (delete-forward-char 3)
+      (undo-boundary)
+      (should (= (point-min) (marker-position m)))
+      (undo)
+      (undo-boundary)
+      (should (= 2 (marker-position m))))))
+
+(ert-deftest undo-test-marker-adjustment-moved ()
+  "Test marker adjustment behavior when the marker moves.
+Demonstrates bug 16818."
+  (with-temp-buffer
+    (buffer-enable-undo)
+    (insert "abcdefghijk")
+    (undo-boundary)
+    (let ((m (make-marker)))
+      (set-marker m 2 (current-buffer)) ; m at b
+      (goto-char (point-min))
+      (delete-forward-char 3) ; m at d
+      (undo-boundary)
+      (set-marker m 4) ; m at g
+      (undo)
+      (undo-boundary)
+      ;; m still at g, but shifted 3 because deletion undone
+      (should (= 7 (marker-position m))))))
+
+(ert-deftest undo-test-region-mark-adjustment ()
+  "Test that the mark's marker adjustment in undo history doesn't
+obstruct undo in region from finding the correct change group.
+Demonstrates bug 16818."
+  (with-temp-buffer
+    (buffer-enable-undo)
+    (transient-mark-mode 1)
+    (insert "First line\n")
+    (insert "Second line\n")
+    (undo-boundary)
+
+    (goto-char (point-min))
+    (insert "aaa")
+    (undo-boundary)
+
+    (undo)
+    (undo-boundary)
+
+    (goto-char (point-max))
+    (insert "bbb")
+    (undo-boundary)
+
+    (push-mark (point) t t)
+    (setq mark-active t)
+    (goto-char (- (point) 3))
+    (delete-forward-char 1)
+    (undo-boundary)
+
+    (insert "bbb")
+    (undo-boundary)
+
+    (goto-char (point-min))
+    (push-mark (point) t t)
+    (setq mark-active t)
+    (goto-char (+ (point) 3))
+    (undo)
+    (undo-boundary)
+
+    (should (string= (buffer-string) "aaaFirst line\nSecond line\nbbb"))))
+
 (defun undo-test-all (&optional interactive)
   "Run all tests for \\[undo]."
   (interactive "p")

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Stefan]

>> The primitive-undo fix should be safe enough for 24.4, so if you
>> want to code this up and install it, feel free.
> I have attached the patch for this, which I'll install if nothing
> comes up from review.

Thanks.  A few comments below.

--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -2229,6 +2229,7 @@
         (did-apply nil)
         (next nil))
     (while (> arg 0)
+      (let (del-pos)
       (while (setq next (pop list))     ;Exit inner loop at undo boundary.
         ;; Handle an integer by setting point to that value.
         (pcase next
@@ -2289,6 +2290,7 @@
            (when (let ((apos (abs pos)))
                    (or (< apos (point-min)) (> apos (point-max))))
              (error "Changes to be undone are outside visible portion of buffer"))
+             (setq del-pos pos)
            (if (< pos 0)
                (progn
                  (goto-char (- pos))
@@ -2303,11 +2305,14 @@
              (goto-char pos)))
           ;; (MARKER . OFFSET) means a marker MARKER was adjusted by OFFSET.
           (`(,(and marker (pred markerp)) . ,(and offset (pred integerp)))
-           (when (marker-buffer marker)
+             (when (and del-pos
+                        (integerp (marker-position marker))
+                        (= del-pos marker)
+                        (marker-buffer marker))
              (set-marker marker
                          (- marker offset)
                          (marker-buffer marker))))
-          (_ (error "Unrecognized entry in undo list %S" next))))
+            (_ (error "Unrecognized entry in undo list %S" next)))))
       (setq arg (1- arg)))
     ;; Make sure an apply entry produces at least one undo entry,
     ;; so the test in `undo' for continuing an undo series

The "move-after" markers will be at (+ del-pos (length inserted-text))
rather than at del-pos.  Also, a lone (MARKER . OFFSET) entry will
arbitrarily use some unrelated earlier del-pos.  Admittedly, such lone
(MARKER . OFFSET) entries should/will never happen, but I'd rather we
catch them and emit a warning than silently do something arbitrary.

IOW, I think we should only change the entry corresponding to a deletion
such that it directly handles all the immediately following
marker-adjustments (it can check them before doing the insertion, hence
using del-pos without having to care about insert-after vs
insert-before).  Then the current handling of marker-adjustments can be
changed to emit a warning.

> @@ -2351,18 +2354,30 @@ If we find an element that crosses an edge of this region,
>  we stop and ignore all further elements."
>    (let ((undo-list-copy (undo-copy-list buffer-undo-list))
>  	(undo-list (list nil))
> -	undo-adjusted-markers
> +        ;; The position of a deletion record (TEXT . POSITION) of the
> +        ;; current change group.
> +        ;;
> +        ;; This is used to check that marker adjustmenets are in the
> +        ;; region.  Bug 16818 describes why the marker's position is
> +        ;; not suitable.
> +        del-pos
>  	some-rejected
>  	undo-elt temp-undo-list delta)
>      (while undo-list-copy
>        (setq undo-elt (car undo-list-copy))
> +      ;; Update del-pos
> +      (if undo-elt
> +          (when (and (consp undo-elt) (stringp (car undo-elt)))
> +            (setq del-pos (cdr undo-elt)))
> +        ;; Undo boundary means new change group, so unset del-pos
> +        (setq del-pos nil))
>        (let ((keep-this
>  	     (cond ((and (consp undo-elt) (eq (car undo-elt) t))
>  		    ;; This is a "was unmodified" element.
>  		    ;; Keep it if we have kept everything thus far.
>  		    (not some-rejected))
>  		   (t
> -		    (undo-elt-in-region undo-elt start end)))))
> +		    (undo-elt-in-region undo-elt start end del-pos)))))
>  	(if keep-this
>  	    (progn
>  	      (setq end (+ end (cdr (undo-delta undo-elt))))

I'd have the same comment here, but if we emit a warning for sole
marker-adjustments in the "non-region" code, we don't really have to
worry about them here.

But this is also affected by the issue of "move-after" markers where
`del-pos' is not sufficient info since those markers won't be at del-pos
any more if they were at del-pos before we inserted the deleted text.


        Stefan

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 1886 bytes --]

> The "move-after" markers will be at (+ del-pos (length
> inserted-text)) rather than at del-pos.

Right, thanks for catching that flaw.

> I'd have the same comment here, but if we emit a warning for sole
> marker-adjustments in the "non-region" code, we don't really have to
> worry about them here.

If you're saying changes under undo-make-selective-list are not
necessary, remember that currently it can create a list like:

  (nil (#<marker at 141 in *scratch*> . -3) (#<marker at 190 in *scratch*>
. -3) nil (aaa . 141) nil (141 . 144) nil)

I don't think the original recipe of this bug report should generate a
warning. Rather, I had undo-make-selective-list filter out the marker
adjustments so as the above list would have (aaa . 141) at the head.

> I think we should only change the entry corresponding to a deletion
> such that it directly handles all the immediately following
> marker-adjustments

They don't always immediately follow. An integer record can be between
them. For example, at the end of the undo-test-marker-adjustment-moved
test I posted previously, buffer-undo-list is:

  (nil (1 . 4) nil (abc . 1) 12 (#<marker at 7 in  *temp*-216909> . -1) nil
(1 . 12) (t . 0))

Also, (t sec-high sec-low microsec picosec) entries can be in between.
eg it was easy to bring about this buffer-undo-list:

  Value: (nil
   (#("   " 0 3
      (fontified t))
    . 12)
   (t 20985 26927 0 0)
   (#<marker at 12 in foo.py> . -2)
   (#<marker at 12 in foo.py> . -2)
   (#<marker in no buffer> . -3)
   (#<marker in no buffer> . -2))

I suppose some options are:

  * Implement your proposal but skip over the (t ...) and integer
    records
  * Restructure the C code so as marker adjustments are always
    immediately before deletion records
  * Revisit the approach of fixing markers that move to unrelated
    locations.

Let me know and thank you for your guidance.

[-- Attachment #2: Type: text/html, Size: 2406 bytes --]

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 609 bytes --]

Clarifications:

>  * Implement your proposal but skip over the (t ...) and integer
    records

I mean "skip" only for the "look ahead to validate" part. Not to skip
completely.

>   * Restructure the C code so as marker adjustments are always
    immediately before deletion records

I meant "chronologically" before, not "before" in the list. I think
the desired ordering would be:

  Value: (nil
   (#("   " 0 3
      (fontified t))
    . 12)
   (#<marker at 12 in foo.py> . -2)
   (#<marker at 12 in foo.py> . -2)
   (#<marker in no buffer> . -3)
   (#<marker in no buffer> . -2)
   (t 20985 26927 0 0))

[-- Attachment #2: Type: text/html, Size: 961 bytes --]

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Stefan]

>> I'd have the same comment here, but if we emit a warning for sole
>> marker-adjustments in the "non-region" code, we don't really have to
>> worry about them here.
> If you're saying changes under undo-make-selective-list are not
> necessary, remember that currently it can create a list like:

No, I mean that it's OK to *assume* that any marker-adjustment we find
in the undo-region code is "right after a deletion".  Of course, that's
only relevant if that can help us simplify the code.

>> I think we should only change the entry corresponding to a deletion
>> such that it directly handles all the immediately following
>> marker-adjustments
> They don't always immediately follow. An integer record can be between
> them. For example, at the end of the undo-test-marker-adjustment-moved
> test I posted previously, buffer-undo-list is:
>   (nil (1 . 4) nil (abc . 1) 12 (#<marker at 7 in  *temp*-216909> . -1) nil
> (1 . 12) (t . 0))

Right, the integer record is indeed also added by the deletion, so
we should still consider the marker adjustments to "immediately follow".

>   * Implement your proposal but skip over the (t ...) and integer
>     records
>   * Restructure the C code so as marker adjustments are always
>     immediately before deletion records
>   * Revisit the approach of fixing markers that move to unrelated
>     locations.

I think the first option is best (hopefully, the set of "things that can
come between the deletion and the marker adjustments" won't keep growing).


        Stefan

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Stefan]

> I meant "chronologically" before, not "before" in the list. I think
> the desired ordering would be:

>   Value: (nil
>    (#("   " 0 3
>       (fontified t))
>     . 12)
>    (#<marker at 12 in foo.py> . -2)
>    (#<marker at 12 in foo.py> . -2)
>    (#<marker in no buffer> . -3)
>    (#<marker in no buffer> . -2)
>    (t 20985 26927 0 0))

Oh, right.  That would be good as well.  At least as good as option 1.
So I'd go with whichever of option 1 or 2 is simpler.

> * Revisit the approach of fixing markers that move to unrelated
>   locations.

Definitely not for 24.4.


        Stefan

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Barry OReilly]

[-- Attachment #1.1: Type: text/plain, Size: 475 bytes --]

>>   Value: (nil
>>    (#("   " 0 3
>>       (fontified t))
>>     . 12)
>>    (#<marker at 12 in foo.py> . -2)
>>    (#<marker at 12 in foo.py> . -2)
>>    (#<marker in no buffer> . -3)
>>    (#<marker in no buffer> . -2)
>>    (t 20985 26927 0 0))

> Oh, right. That would be good as well. At least as good as option 1.
> So I'd go with whichever of option 1 or 2 is simpler.

Attached is the new patch to solve this, implementing option 2 and
incorporating your feedback.

[-- Attachment #1.2: Type: text/html, Size: 649 bytes --]

[-- Attachment #2: undo-marker-record.diff --]
[-- Type: text/plain, Size: 23524 bytes --]

diff --git a/doc/lispref/ChangeLog b/doc/lispref/ChangeLog
index 6ffd80b..74a756e 100644
--- a/doc/lispref/ChangeLog
+++ b/doc/lispref/ChangeLog
@@ -1,3 +1,10 @@
+2014-03-13  Barry O'Reilly  <gundaetiapo@gmail.com>
+	* markers.texi (Moving Marker Positions): The 2014-03-02 doc
+	change mentioning undo's inability to handle relocated markers no
+	longer applies.  See bug#16818.
+	* text.texi (Undo): Expand documentation of (TEXT . POS) and
+	(MARKER . ADJUSTMENT) undo elements.
+
 2014-03-09  Martin Rudalics  <rudalics@gmx.at>
 
 	* elisp.texi (Top): Rename section "Width" to "Size of Displayed
diff --git a/doc/lispref/markers.texi b/doc/lispref/markers.texi
index 19386d6..51b87ab 100644
--- a/doc/lispref/markers.texi
+++ b/doc/lispref/markers.texi
@@ -344,12 +344,10 @@ specify the insertion type, create them with insertion type
 @section Moving Marker Positions
 
   This section describes how to change the position of an existing
-marker.  When you do this, be sure you know how the marker is used
-outside of your program.  For example, moving a marker to an unrelated
-new position can cause undo to later adjust the marker incorrectly.
-Often when you wish to relocate a marker to an unrelated position, it
-is preferable to make a new marker and set the prior one to point
-nowhere.
+marker.  When you do this, be sure you know whether the marker is used
+outside of your program, and, if so, what effects will result from
+moving it---otherwise, confusing things may happen in other parts of
+Emacs.
 
 @defun set-marker marker position &optional buffer
 This function moves @var{marker} to @var{position}
diff --git a/doc/lispref/text.texi b/doc/lispref/text.texi
index d93f937..d9be87d 100644
--- a/doc/lispref/text.texi
+++ b/doc/lispref/text.texi
@@ -1270,7 +1270,8 @@ This kind of element indicates how to reinsert text that was deleted.
 The deleted text itself is the string @var{text}.  The place to
 reinsert it is @code{(abs @var{position})}.  If @var{position} is
 positive, point was at the beginning of the deleted text, otherwise it
-was at the end.
+was at the end.  Zero or more @var{marker} . @var{adjustment})
+elements follow immediately after this element.
 
 @item (t . @var{time-flag})
 This kind of element indicates that an unmodified buffer became
@@ -1296,8 +1297,10 @@ Here's how you might undo the change:
 @item (@var{marker} . @var{adjustment})
 This kind of element records the fact that the marker @var{marker} was
 relocated due to deletion of surrounding text, and that it moved
-@var{adjustment} character positions.  Undoing this element moves
-@var{marker} @minus{} @var{adjustment} characters.
+@var{adjustment} character positions.  If the marker's location is
+consistent with the (@var{text} . @var{position}) element preceding it
+in the undo list, then undoing this element moves @var{marker}
+@minus{} @var{adjustment} characters.
 
 @item (apply @var{funname} . @var{args})
 This is an extensible undo item, which is undone by calling
diff --git a/lisp/ChangeLog b/lisp/ChangeLog
index a1ee5bb..4f2c258 100644
--- a/lisp/ChangeLog
+++ b/lisp/ChangeLog
@@ -1,3 +1,15 @@
+2014-03-13  Barry O'Reilly  <gundaetiapo@gmail.com>
+
+	* simple.el (primitive-undo): Only process marker adjustments
+	validated against their corresponding (TEXT . POS).  Issue warning
+	for lone marker adjustments in undo history.  (Bug#16818)
+	(undo-make-selective-list): Add marker adjustments to selective
+	undo list based on whether their corresponding (TEXT . POS) is in
+	the region.  Remove variable adjusted-markers, which was unused
+	and only non nil during undo-make-selective-list.
+	(undo-elt-in-region): Return nil when passed a marker adjustment
+	and explain in function doc.
+
 2014-03-13  Dmitry Gutov  <dgutov@yandex.ru>
 
 	* progmodes/ruby-mode.el (ruby-font-lock-keywords): Fontify
diff --git a/lisp/simple.el b/lisp/simple.el
index 881a633..ee70113 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -2289,24 +2289,37 @@ Return what remains of the list."
            (when (let ((apos (abs pos)))
                    (or (< apos (point-min)) (> apos (point-max))))
              (error "Changes to be undone are outside visible portion of buffer"))
+           (let (valid-marker-adjustments)
+             ;; Check that marker adjustments which were recorded
+             ;; with the (STRING . POS) record are still valid, ie
+             ;; the markers haven't moved.  We check their validity
+             ;; before reinserting the string so as we don't need to
+             ;; mind marker insertion-type.
+             (while (and (consp (car list))
+                         (markerp (caar list))
+                         (integerp (cdar list)))
+               (and (eq (marker-buffer (caar list))
+                        (current-buffer))
+                    (integerp (marker-position (caar list)))
+                    (= pos (caar list))
+                    (push (car list) valid-marker-adjustments))
+               (pop list))
+             ;; Insert string and adjust point
            (if (< pos 0)
                (progn
                  (goto-char (- pos))
                  (insert string))
              (goto-char pos)
-             ;; Now that we record marker adjustments
-             ;; (caused by deletion) for undo,
-             ;; we should always insert after markers,
-             ;; so that undoing the marker adjustments
-             ;; put the markers back in the right place.
              (insert string)
-             (goto-char pos)))
+               (goto-char pos))
+             ;; Adjust the valid marker adjustments
+             (dolist (adj valid-marker-adjustments)
+               (set-marker (car adj)
+                           (- (car adj) (cdr adj))))))
           ;; (MARKER . OFFSET) means a marker MARKER was adjusted by OFFSET.
           (`(,(and marker (pred markerp)) . ,(and offset (pred integerp)))
-           (when (marker-buffer marker)
-             (set-marker marker
-                         (- marker offset)
-                         (marker-buffer marker))))
+           (warn "Encountered %S entry in undo list with no matching (TEXT . POS) entry"
+                 next))
           (_ (error "Unrecognized entry in undo list %S" next))))
       (setq arg (1- arg)))
     ;; Make sure an apply entry produces at least one undo entry,
@@ -2341,8 +2354,6 @@ are ignored.  If BEG and END are nil, all undo elements are used."
 	    (undo-make-selective-list (min beg end) (max beg end))
 	  buffer-undo-list)))
 
-(defvar undo-adjusted-markers)
-
 (defun undo-make-selective-list (start end)
   "Return a list of undo elements for the region START to END.
 The elements come from `buffer-undo-list', but we keep only
@@ -2351,7 +2362,6 @@ If we find an element that crosses an edge of this region,
 we stop and ignore all further elements."
   (let ((undo-list-copy (undo-copy-list buffer-undo-list))
 	(undo-list (list nil))
-	undo-adjusted-markers
 	some-rejected
 	undo-elt temp-undo-list delta)
     (while undo-list-copy
@@ -2367,9 +2377,22 @@ we stop and ignore all further elements."
 	    (progn
 	      (setq end (+ end (cdr (undo-delta undo-elt))))
 	      ;; Don't put two nils together in the list
-	      (if (not (and (eq (car undo-list) nil)
+	      (when (not (and (eq (car undo-list) nil)
 			    (eq undo-elt nil)))
-		  (setq undo-list (cons undo-elt undo-list))))
+                (setq undo-list (cons undo-elt undo-list))
+                ;; If (TEXT . POS), "keep" its subsequent (MARKER
+                ;; . ADJUSTMENT) whose markers haven't moved.
+                (when (and (consp undo-elt)
+                           (stringp (car undo-elt))
+                           (integerp (cdr undo-elt)))
+                  (let ((list-i (cdr undo-list-copy)))
+                    (while (markerp (caar list-i))
+                      (and (eq (marker-buffer (caar list-i))
+                               (current-buffer))
+                           (integerp (marker-position (caar list-i)))
+                           (= (cdr undo-elt) (caar list-i))
+                           (push (car list-i) undo-list))
+                      (pop list-i))))))
 	  (if (undo-elt-crosses-region undo-elt start end)
 	      (setq undo-list-copy nil)
 	    (setq some-rejected t)
@@ -2417,7 +2440,12 @@ we stop and ignore all further elements."
 
 (defun undo-elt-in-region (undo-elt start end)
   "Determine whether UNDO-ELT falls inside the region START ... END.
-If it crosses the edge, we return nil."
+If it crosses the edge, we return nil.
+
+Generally this function is not useful for determining
+whether (MARKER . ADJUSTMENT) undo elements are in the region,
+because markers can be arbitrarily relocated.  Instead, pass the
+marker adjustment's corresponding (TEXT . POS) element."
   (cond ((integerp undo-elt)
 	 (and (>= undo-elt start)
 	      (<= undo-elt end)))
@@ -2430,17 +2458,8 @@ If it crosses the edge, we return nil."
 	 (and (>= (abs (cdr undo-elt)) start)
 	      (<= (abs (cdr undo-elt)) end)))
 	((and (consp undo-elt) (markerp (car undo-elt)))
-	 ;; This is a marker-adjustment element (MARKER . ADJUSTMENT).
-	 ;; See if MARKER is inside the region.
-	 (let ((alist-elt (assq (car undo-elt) undo-adjusted-markers)))
-	   (unless alist-elt
-	     (setq alist-elt (cons (car undo-elt)
-				   (marker-position (car undo-elt))))
-	     (setq undo-adjusted-markers
-		   (cons alist-elt undo-adjusted-markers)))
-	   (and (cdr alist-elt)
-		(>= (cdr alist-elt) start)
-		(<= (cdr alist-elt) end))))
+	 ;; (MARKER . ADJUSTMENT)
+         nil)
 	((null (car undo-elt))
 	 ;; (nil PROPERTY VALUE BEG . END)
 	 (let ((tail (nthcdr 3 undo-elt)))
diff --git a/src/ChangeLog b/src/ChangeLog
index c1158fc..41fa898 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,3 +1,31 @@
+2014-03-13  Barry O'Reilly  <gundaetiapo@gmail.com>
+
+	Have (MARKER . ADJUSTMENT) undo records always be immediately
+	after their corresponding (TEXT . POS) record in undo list.
+	(Bug#16818)
+	* lisp.h (record-delete): New arg record_markers.
+	(record_marker_adjustment): No longer needed outside undo.c.
+	* insdel.c (adjust_markers_for_delete): Move calculation of marker
+	adjustments to undo.c's record_marker_adjustments.  Note that
+	fileio.c's decide_coding_unwind is another caller to
+	adjust_markers_for_delete.  Because it has undo list bound to t,
+	it does not rely on adjust_markers_for_delete to record marker
+	adjustments.
+	(del_range_2): Swap call to record_delete and
+	adjust_markers_for_delete so as undo marker adjustments are
+	recorded before current deletion's adjustments, as before.
+	(adjust_after_replace):
+	(replace_range): Pass value for new record_markers arg to
+	delete_record.
+	* undo.c (record_marker_adjustment): Renamed to
+	record_marker_adjustments and made static.
+	(record_delete): Check record_markers arg and call
+	record_marker_adjustments.
+	(record_change): Pass value for new record_markers arg to
+	delete_record.
+	(record_point): at_boundary calculation no longer needs to account
+	for marker adjustments.
+
 2014-03-12  Martin Rudalics  <rudalics@gmx.at>
 
 	* frame.c (x_set_frame_parameters): Always calculate new sizes
diff --git a/src/insdel.c b/src/insdel.c
index 1c9bafd..eb1ad62 100644
--- a/src/insdel.c
+++ b/src/insdel.c
@@ -233,34 +233,9 @@ adjust_markers_for_delete (ptrdiff_t from, ptrdiff_t from_byte,
       /* Here's the case where a marker is inside text being deleted.  */
       else if (charpos > from)
 	{
-	  if (! m->insertion_type)
-	    { /* Normal markers will end up at the beginning of the
-	       re-inserted text after undoing a deletion, and must be
-	       adjusted to move them to the correct place.  */
-	      XSETMISC (marker, m);
-	      record_marker_adjustment (marker, from - charpos);
-	    }
-	  else if (charpos < to)
-	    { /* Before-insertion markers will automatically move forward
-	       upon re-inserting the deleted text, so we have to arrange
-	       for them to move backward to the correct position.  */
-	      XSETMISC (marker, m);
-	      record_marker_adjustment (marker, to - charpos);
-	    }
 	  m->charpos = from;
 	  m->bytepos = from_byte;
 	}
-      /* Here's the case where a before-insertion marker is immediately
-	 before the deleted region.  */
-      else if (charpos == from && m->insertion_type)
-	{
-	  /* Undoing the change uses normal insertion, which will
-	     incorrectly make MARKER move forward, so we arrange for it
-	     to then move backward to the correct place at the beginning
-	     of the deleted region.  */
-	  XSETMISC (marker, m);
-	  record_marker_adjustment (marker, to - from);
-	}
     }
 }
 
@@ -1219,7 +1194,7 @@ adjust_after_replace (ptrdiff_t from, ptrdiff_t from_byte,
 			       from + len, from_byte + len_byte, 0);
 
   if (nchars_del > 0)
-    record_delete (from, prev_text);
+    record_delete (from, prev_text, false);
   record_insert (from, len);
 
   if (len > nchars_del)
@@ -1384,7 +1359,7 @@ replace_range (ptrdiff_t from, ptrdiff_t to, Lisp_Object new,
   if (!NILP (deletion))
     {
       record_insert (from + SCHARS (deletion), inschars);
-      record_delete (from, deletion);
+      record_delete (from, deletion, false);
     }
 
   GAP_SIZE -= outgoing_insbytes;
@@ -1716,13 +1691,14 @@ del_range_2 (ptrdiff_t from, ptrdiff_t from_byte,
   else
     deletion = Qnil;
 
-  /* Relocate all markers pointing into the new, larger gap
-     to point at the end of the text before the gap.
-     Do this before recording the deletion,
-     so that undo handles this after reinserting the text.  */
+  /* Record marker adjustments, and text deletion into undo
+     history.  */
+  record_delete (from, deletion, true);
+
+  /* Relocate all markers pointing into the new, larger gap to point
+     at the end of the text before the gap.  */
   adjust_markers_for_delete (from, from_byte, to, to_byte);
 
-  record_delete (from, deletion);
   MODIFF++;
   CHARS_MODIFF = MODIFF;
 
diff --git a/src/lisp.h b/src/lisp.h
index 2f9a30f..30f52b9 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -4198,9 +4198,8 @@ extern void syms_of_macros (void);
 extern Lisp_Object Qapply;
 extern Lisp_Object Qinhibit_read_only;
 extern void truncate_undo_list (struct buffer *);
-extern void record_marker_adjustment (Lisp_Object, ptrdiff_t);
 extern void record_insert (ptrdiff_t, ptrdiff_t);
-extern void record_delete (ptrdiff_t, Lisp_Object);
+extern void record_delete (ptrdiff_t, Lisp_Object, bool);
 extern void record_first_change (void);
 extern void record_change (ptrdiff_t, ptrdiff_t);
 extern void record_property_change (ptrdiff_t, ptrdiff_t,
diff --git a/src/undo.c b/src/undo.c
index 7286d40..b013763 100644
--- a/src/undo.c
+++ b/src/undo.c
@@ -75,27 +75,8 @@ record_point (ptrdiff_t pt)
     Fundo_boundary ();
   last_undo_buffer = current_buffer;
 
-  if (CONSP (BVAR (current_buffer, undo_list)))
-    {
-      /* Set AT_BOUNDARY only when we have nothing other than
-         marker adjustment before undo boundary.  */
-
-      Lisp_Object tail = BVAR (current_buffer, undo_list), elt;
-
-      while (1)
-	{
-	  if (NILP (tail))
-	    elt = Qnil;
-	  else
-	    elt = XCAR (tail);
-	  if (NILP (elt) || ! (CONSP (elt) && MARKERP (XCAR (elt))))
-	    break;
-	  tail = XCDR (tail);
-	}
-      at_boundary = NILP (elt);
-    }
-  else
-    at_boundary = 1;
+  at_boundary = ! CONSP (BVAR (current_buffer, undo_list))
+                || NILP (XCAR (BVAR (current_buffer, undo_list)));
 
   if (MODIFF <= SAVE_MODIFF)
     record_first_change ();
@@ -147,11 +128,60 @@ record_insert (ptrdiff_t beg, ptrdiff_t length)
 		  Fcons (Fcons (lbeg, lend), BVAR (current_buffer, undo_list)));
 }
 
-/* Record that a deletion is about to take place,
-   of the characters in STRING, at location BEG.  */
+/* Record the fact that MARKER is about to be adjusted by ADJUSTMENT.
+   This is done only when a marker points within text being deleted,
+   because that's the only case where an automatic marker adjustment
+   won't be inverted automatically by undoing the buffer modification.  */
+
+static void
+record_marker_adjustments (ptrdiff_t from, ptrdiff_t to)
+{
+  Lisp_Object marker;
+  register struct Lisp_Marker *m;
+  register ptrdiff_t charpos, adjustment;
+
+  /* Allocate a cons cell to be the undo boundary after this command.  */
+  if (NILP (pending_boundary))
+    pending_boundary = Fcons (Qnil, Qnil);
+
+  if (current_buffer != last_undo_buffer)
+    Fundo_boundary ();
+  last_undo_buffer = current_buffer;
+
+  for (m = BUF_MARKERS (current_buffer); m; m = m->next)
+    {
+      charpos = m->charpos;
+      eassert (charpos <= Z);
+      adjustment = 0;
+
+      /* Normal markers will end up at the beginning of the
+	re-inserted text after undoing a deletion, and must be
+	adjusted to move them to the correct place.  */
+      if (! m->insertion_type && from < charpos && charpos <= to)
+        adjustment = from - charpos;
+      /* Before-insertion markers will automatically move forward upon
+	re-inserting the deleted text, so we have to arrange for them
+	to move backward to the correct position.  */
+      else if (m->insertion_type && from <= charpos && charpos < to)
+        adjustment = to - charpos;
+
+      if (adjustment)
+        {
+          XSETMISC (marker, m);
+          bset_undo_list
+            (current_buffer,
+             Fcons (Fcons (marker, make_number (adjustment)),
+                    BVAR (current_buffer, undo_list)));
+        }
+    }
+}
+
+/* Record that a deletion is about to take place, of the characters in
+   STRING, at location BEG.  Optionally record adjustments for markers
+   in the region STRING occupies in the current buffer.  */
 
 void
-record_delete (ptrdiff_t beg, Lisp_Object string)
+record_delete (ptrdiff_t beg, Lisp_Object string, bool record_markers)
 {
   Lisp_Object sbeg;
 
@@ -169,34 +199,15 @@ record_delete (ptrdiff_t beg, Lisp_Object string)
       record_point (beg);
     }
 
-  bset_undo_list
-    (current_buffer,
-     Fcons (Fcons (string, sbeg), BVAR (current_buffer, undo_list)));
-}
-
-/* Record the fact that MARKER is about to be adjusted by ADJUSTMENT.
-   This is done only when a marker points within text being deleted,
-   because that's the only case where an automatic marker adjustment
-   won't be inverted automatically by undoing the buffer modification.  */
-
-void
-record_marker_adjustment (Lisp_Object marker, ptrdiff_t adjustment)
-{
-  if (EQ (BVAR (current_buffer, undo_list), Qt))
-    return;
-
-  /* Allocate a cons cell to be the undo boundary after this command.  */
-  if (NILP (pending_boundary))
-    pending_boundary = Fcons (Qnil, Qnil);
-
-  if (current_buffer != last_undo_buffer)
-    Fundo_boundary ();
-  last_undo_buffer = current_buffer;
+  /* primitive-undo assumes marker adjustments are recorded
+     immediately before the deletion is recorded.  See bug 16818
+     discussion.  */
+  if (record_markers)
+    record_marker_adjustments (beg, beg + SCHARS (string));
 
   bset_undo_list
     (current_buffer,
-     Fcons (Fcons (marker, make_number (adjustment)),
-	    BVAR (current_buffer, undo_list)));
+     Fcons (Fcons (string, sbeg), BVAR (current_buffer, undo_list)));
 }
 
 /* Record that a replacement is about to take place,
@@ -206,7 +217,7 @@ record_marker_adjustment (Lisp_Object marker, ptrdiff_t adjustment)
 void
 record_change (ptrdiff_t beg, ptrdiff_t length)
 {
-  record_delete (beg, make_buffer_string (beg, beg + length, 1));
+  record_delete (beg, make_buffer_string (beg, beg + length, 1), false);
   record_insert (beg, length);
 }
 \f
diff --git a/test/ChangeLog b/test/ChangeLog
index c87022c..cbf9eaa 100644
--- a/test/ChangeLog
+++ b/test/ChangeLog
@@ -1,3 +1,11 @@
+2014-03-13  Barry O'Reilly  <gundaetiapo@gmail.com>
+
+	* undo-tests.el (undo-test-marker-adjustment-nominal):
+	(undo-test-region-t-marker): New tests of marker adjustments.
+	(undo-test-marker-adjustment-moved):
+	(undo-test-region-mark-adjustment): New tests to demonstrate
+	bug#16818, which fail without the fix.
+
 2014-03-07  Michael Albinus  <michael.albinus@gmx.de>
 
 	* automated/tramp-tests.el (tramp-copy-size-limit): Declare.
diff --git a/test/automated/undo-tests.el b/test/automated/undo-tests.el
index 8a963f1..6ecac36 100644
--- a/test/automated/undo-tests.el
+++ b/test/automated/undo-tests.el
@@ -268,6 +268,104 @@
     (should (string= (buffer-string)
                      "This sentence corrupted?aaa"))))
 
+(ert-deftest undo-test-marker-adjustment-nominal ()
+  "Test nominal behavior of marker adjustments."
+  (with-temp-buffer
+    (buffer-enable-undo)
+    (insert "abcdefg")
+    (undo-boundary)
+    (let ((m (make-marker)))
+      (set-marker m 2 (current-buffer))
+      (goto-char (point-min))
+      (delete-forward-char 3)
+      (undo-boundary)
+      (should (= (point-min) (marker-position m)))
+      (undo)
+      (undo-boundary)
+      (should (= 2 (marker-position m))))))
+
+(ert-deftest undo-test-region-t-marker ()
+  "Test undo in region containing marker with t insertion-type."
+  (with-temp-buffer
+    (buffer-enable-undo)
+    (transient-mark-mode 1)
+    (insert "abcdefg")
+    (undo-boundary)
+    (let ((m (make-marker)))
+      (set-marker-insertion-type m t)
+      (set-marker m (point-min) (current-buffer)) ; m at a
+      (goto-char (+ 2 (point-min)))
+      (push-mark (point) t t)
+      (setq mark-active t)
+      (goto-char (point-min))
+      (delete-forward-char 1) ;; delete region covering "ab"
+      (undo-boundary)
+      (should (= (point-min) (marker-position m)))
+      ;; Resurrect "ab". m's insertion type means the reinsertion
+      ;; moves it forward 2, and then the marker adjustment returns it
+      ;; to its rightful place.
+      (undo)
+      (undo-boundary)
+      (should (= (point-min) (marker-position m))))))
+
+(ert-deftest undo-test-marker-adjustment-moved ()
+  "Test marker adjustment behavior when the marker moves.
+Demonstrates bug 16818."
+  (with-temp-buffer
+    (buffer-enable-undo)
+    (insert "abcdefghijk")
+    (undo-boundary)
+    (let ((m (make-marker)))
+      (set-marker m 2 (current-buffer)) ; m at b
+      (goto-char (point-min))
+      (delete-forward-char 3) ; m at d
+      (undo-boundary)
+      (set-marker m 4) ; m at g
+      (undo)
+      (undo-boundary)
+      ;; m still at g, but shifted 3 because deletion undone
+      (should (= 7 (marker-position m))))))
+
+(ert-deftest undo-test-region-mark-adjustment ()
+  "Test that the mark's marker adjustment in undo history doesn't
+obstruct undo in region from finding the correct change group.
+Demonstrates bug 16818."
+  (with-temp-buffer
+    (buffer-enable-undo)
+    (transient-mark-mode 1)
+    (insert "First line\n")
+    (insert "Second line\n")
+    (undo-boundary)
+
+    (goto-char (point-min))
+    (insert "aaa")
+    (undo-boundary)
+
+    (undo)
+    (undo-boundary)
+
+    (goto-char (point-max))
+    (insert "bbb")
+    (undo-boundary)
+
+    (push-mark (point) t t)
+    (setq mark-active t)
+    (goto-char (- (point) 3))
+    (delete-forward-char 1)
+    (undo-boundary)
+
+    (insert "bbb")
+    (undo-boundary)
+
+    (goto-char (point-min))
+    (push-mark (point) t t)
+    (setq mark-active t)
+    (goto-char (+ (point) 3))
+    (undo)
+    (undo-boundary)
+
+    (should (string= (buffer-string) "aaaFirst line\nSecond line\nbbb"))))
+
 (defun undo-test-all (&optional interactive)
   "Run all tests for \\[undo]."
   (interactive "p")

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Stefan]

> Attached is the new patch to solve this, implementing option 2 and
> incorporating your feedback.

Looks good, thank you very much.  Feel free to install into emacs-24,
but please see my comments below.


        Stefan


> +2014-03-13  Barry O'Reilly  <gundaetiapo@gmail.com>
> +	* markers.texi (Moving Marker Positions): The 2014-03-02 doc

Missing empty line between the two.

> +             (while (and (consp (car list))
> +                         (markerp (caar list))

(markerp (car-safe (car list)))

> +               (and (eq (marker-buffer (caar list))
> +                        (current-buffer))
> +                    (integerp (marker-position (caar list)))

I think this `integerp' test is redundant (marker-position can only
return nil or an integer and if it returns nil, then marker-buffer also
returns nil).

>            ;; (MARKER . OFFSET) means a marker MARKER was adjusted by OFFSET.
>            (`(,(and marker (pred markerp)) . ,(and offset (pred integerp)))
> -           (when (marker-buffer marker)
> -             (set-marker marker
> -                         (- marker offset)
> -                         (marker-buffer marker))))
> +           (warn "Encountered %S entry in undo list with no matching (TEXT . POS) entry"
> +                 next))

I think I'd add the warning without removing the `set-marker', just to
be conservative.

> +                (when (and (consp undo-elt)
> +                           (stringp (car undo-elt))

(stringp (car-safe undo-elt))

> +                           (integerp (cdr undo-elt)))
> +                  (let ((list-i (cdr undo-list-copy)))
> +                    (while (markerp (caar list-i))

I think you need (markerp (car-safe (car list-i))) because (car list-i)
may be an integer.

Also, I'd try to avoid repeatedly calling (car list-i) in the body of
the `while' loop(s) by let-binding it.  I'd probably do it via `pop', as
in

  (while (...)
    (let ((elem (pop undo-list)))
      ...))

>  	((and (consp undo-elt) (markerp (car undo-elt)))
> -	 ;; This is a marker-adjustment element (MARKER . ADJUSTMENT).
> -	 ;; See if MARKER is inside the region.
> -	 (let ((alist-elt (assq (car undo-elt) undo-adjusted-markers)))
> -	   (unless alist-elt
> -	     (setq alist-elt (cons (car undo-elt)
> -				   (marker-position (car undo-elt))))
> -	     (setq undo-adjusted-markers
> -		   (cons alist-elt undo-adjusted-markers)))
> -	   (and (cdr alist-elt)
> -		(>= (cdr alist-elt) start)
> -		(<= (cdr alist-elt) end))))
> +	 ;; (MARKER . ADJUSTMENT)
> +         nil)

It would also be more conservative to keep this unchanged, but I think
I agree with you here that we don't need to be *that* conservative.

> -  record_delete (beg, make_buffer_string (beg, beg + length, 1));
> +  record_delete (beg, make_buffer_string (beg, beg + length, 1), false);

Begs the question: why didn't (don't) we record marker adjustments here
(and other similar places)?


        Stefan

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Barry OReilly]

[-- Attachment #1.1: Type: text/plain, Size: 2290 bytes --]

[Adding Toby, since I mention undo-tree.]

> It would also be more conservative to keep this unchanged, but I
> think I agree with you here that we don't need to be *that*
> conservative.

This is how I addressed that:

diff --git a/lisp/simple.el b/lisp/simple.el
index 4a3a89c..6b5031e 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -2375,6 +2375,10 @@ we stop and ignore all further elements."
                    ;; This is a "was unmodified" element.
                    ;; Keep it if we have kept everything thus far.
                    (not some-rejected))
+                   ;; Skip over marker adjustments, instead relying on
+                   ;; finding them after (TEXT . POS) elements
+                   ((markerp (car-safe undo-elt))
+                    nil)
                   (t
                    (undo-elt-in-region undo-elt start end)))))
        (if keep-this
@@ -2461,7 +2465,7 @@ marker adjustment's corresponding (TEXT . POS)
element."
              (<= (abs (cdr undo-elt)) end)))
        ((and (consp undo-elt) (markerp (car undo-elt)))
         ;; (MARKER . ADJUSTMENT)
-         nil)
+         (<= start (car undo-elt) end))
        ((null (car undo-elt))
         ;; (nil PROPERTY VALUE BEG . END)
         (let ((tail (nthcdr 3 undo-elt)))

It maintains the same return from undo-elt-in-region for marker
adjustments as before.

I took a look at undo-tree. It doesn't use undo-make-selective-list,
but does use undo-elt-in-region. I guess that means this particular
bug won't be fixed in undo-tree for regional undos, until it also
scans forward from (TEXT . POS) as this patch's
undo-make-selective-list does.

> Begs the question: why didn't (don't) we record marker adjustments
> here (and other similar places)?

I considered pursuing that question earlier, but opted for those
callers to behave as before, at least for now.

There's a related comment nearby one of the callers:

/* Note that this does not yet handle markers quite right.
   Also it needs to record a single undo-entry that does a replacement
   rather than a separate delete and insert.
   That way, undo will also handle markers properly.

   But if MARKERS is 0, don't relocate markers.  */

I've attached the updated patch with your comments incorporated. I'll
install soon.

[-- Attachment #1.2: Type: text/html, Size: 2599 bytes --]

[-- Attachment #2: undo-marker-record-20140324.diff --]
[-- Type: text/plain, Size: 24384 bytes --]

diff --git a/doc/lispref/ChangeLog b/doc/lispref/ChangeLog
index 6ffd80b..704aa48 100644
--- a/doc/lispref/ChangeLog
+++ b/doc/lispref/ChangeLog
@@ -1,3 +1,11 @@
+2014-03-13  Barry O'Reilly  <gundaetiapo@gmail.com>
+
+	* markers.texi (Moving Marker Positions): The 2014-03-02 doc
+	change mentioning undo's inability to handle relocated markers no
+	longer applies.  See bug#16818.
+	* text.texi (Undo): Expand documentation of (TEXT . POS) and
+	(MARKER . ADJUSTMENT) undo elements.
+
 2014-03-09  Martin Rudalics  <rudalics@gmx.at>
 
 	* elisp.texi (Top): Rename section "Width" to "Size of Displayed
diff --git a/doc/lispref/markers.texi b/doc/lispref/markers.texi
index 19386d6..51b87ab 100644
--- a/doc/lispref/markers.texi
+++ b/doc/lispref/markers.texi
@@ -344,12 +344,10 @@ specify the insertion type, create them with insertion type
 @section Moving Marker Positions
 
   This section describes how to change the position of an existing
-marker.  When you do this, be sure you know how the marker is used
-outside of your program.  For example, moving a marker to an unrelated
-new position can cause undo to later adjust the marker incorrectly.
-Often when you wish to relocate a marker to an unrelated position, it
-is preferable to make a new marker and set the prior one to point
-nowhere.
+marker.  When you do this, be sure you know whether the marker is used
+outside of your program, and, if so, what effects will result from
+moving it---otherwise, confusing things may happen in other parts of
+Emacs.
 
 @defun set-marker marker position &optional buffer
 This function moves @var{marker} to @var{position}
diff --git a/doc/lispref/text.texi b/doc/lispref/text.texi
index d93f937..1d550a0 100644
--- a/doc/lispref/text.texi
+++ b/doc/lispref/text.texi
@@ -1270,7 +1270,8 @@ This kind of element indicates how to reinsert text that was deleted.
 The deleted text itself is the string @var{text}.  The place to
 reinsert it is @code{(abs @var{position})}.  If @var{position} is
 positive, point was at the beginning of the deleted text, otherwise it
-was at the end.
+was at the end.  Zero or more (@var{marker} . @var{adjustment})
+elements follow immediately after this element.
 
 @item (t . @var{time-flag})
 This kind of element indicates that an unmodified buffer became
@@ -1296,8 +1297,10 @@ Here's how you might undo the change:
 @item (@var{marker} . @var{adjustment})
 This kind of element records the fact that the marker @var{marker} was
 relocated due to deletion of surrounding text, and that it moved
-@var{adjustment} character positions.  Undoing this element moves
-@var{marker} @minus{} @var{adjustment} characters.
+@var{adjustment} character positions.  If the marker's location is
+consistent with the (@var{text} . @var{position}) element preceding it
+in the undo list, then undoing this element moves @var{marker}
+@minus{} @var{adjustment} characters.
 
 @item (apply @var{funname} . @var{args})
 This is an extensible undo item, which is undone by calling
diff --git a/lisp/ChangeLog b/lisp/ChangeLog
index a1ee5bb..4f2c258 100644
--- a/lisp/ChangeLog
+++ b/lisp/ChangeLog
@@ -1,3 +1,15 @@
+2014-03-13  Barry O'Reilly  <gundaetiapo@gmail.com>
+
+	* simple.el (primitive-undo): Only process marker adjustments
+	validated against their corresponding (TEXT . POS).  Issue warning
+	for lone marker adjustments in undo history.  (Bug#16818)
+	(undo-make-selective-list): Add marker adjustments to selective
+	undo list based on whether their corresponding (TEXT . POS) is in
+	the region.  Remove variable adjusted-markers, which was unused
+	and only non nil during undo-make-selective-list.
+	(undo-elt-in-region): Return nil when passed a marker adjustment
+	and explain in function doc.
+
 2014-03-13  Dmitry Gutov  <dgutov@yandex.ru>
 
 	* progmodes/ruby-mode.el (ruby-font-lock-keywords): Fontify
diff --git a/lisp/simple.el b/lisp/simple.el
index 881a633..6b5031e 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -2289,24 +2289,41 @@ Return what remains of the list."
            (when (let ((apos (abs pos)))
                    (or (< apos (point-min)) (> apos (point-max))))
              (error "Changes to be undone are outside visible portion of buffer"))
-           (if (< pos 0)
-               (progn
-                 (goto-char (- pos))
-                 (insert string))
-             (goto-char pos)
-             ;; Now that we record marker adjustments
-             ;; (caused by deletion) for undo,
-             ;; we should always insert after markers,
-             ;; so that undoing the marker adjustments
-             ;; put the markers back in the right place.
-             (insert string)
-             (goto-char pos)))
+           (let (valid-marker-adjustments)
+             ;; Check that marker adjustments which were recorded
+             ;; with the (STRING . POS) record are still valid, ie
+             ;; the markers haven't moved.  We check their validity
+             ;; before reinserting the string so as we don't need to
+             ;; mind marker insertion-type.
+             (while (and (markerp (car-safe (car list)))
+                         (integerp (cdr-safe (car list))))
+               (let* ((marker-adj (pop list))
+                      (m (car marker-adj)))
+                 (and (eq (marker-buffer m) (current-buffer))
+                      (= pos m)
+                      (push marker-adj valid-marker-adjustments))))
+             ;; Insert string and adjust point
+             (if (< pos 0)
+                 (progn
+                   (goto-char (- pos))
+                   (insert string))
+               (goto-char pos)
+               (insert string)
+               (goto-char pos))
+             ;; Adjust the valid marker adjustments
+             (dolist (adj valid-marker-adjustments)
+               (set-marker (car adj)
+                           (- (car adj) (cdr adj))))))
           ;; (MARKER . OFFSET) means a marker MARKER was adjusted by OFFSET.
           (`(,(and marker (pred markerp)) . ,(and offset (pred integerp)))
-           (when (marker-buffer marker)
-             (set-marker marker
-                         (- marker offset)
-                         (marker-buffer marker))))
+           (warn "Encountered %S entry in undo list with no matching (TEXT . POS) entry"
+                 next)
+           ;; Even though these elements are not expected in the undo
+           ;; list, adjust them to be conservative for the 24.4
+           ;; release.  (Bug#16818)
+           (set-marker marker
+                       (- marker offset)
+                       (marker-buffer marker)))
           (_ (error "Unrecognized entry in undo list %S" next))))
       (setq arg (1- arg)))
     ;; Make sure an apply entry produces at least one undo entry,
@@ -2341,8 +2358,6 @@ are ignored.  If BEG and END are nil, all undo elements are used."
 	    (undo-make-selective-list (min beg end) (max beg end))
 	  buffer-undo-list)))
 
-(defvar undo-adjusted-markers)
-
 (defun undo-make-selective-list (start end)
   "Return a list of undo elements for the region START to END.
 The elements come from `buffer-undo-list', but we keep only
@@ -2351,7 +2366,6 @@ If we find an element that crosses an edge of this region,
 we stop and ignore all further elements."
   (let ((undo-list-copy (undo-copy-list buffer-undo-list))
 	(undo-list (list nil))
-	undo-adjusted-markers
 	some-rejected
 	undo-elt temp-undo-list delta)
     (while undo-list-copy
@@ -2361,15 +2375,30 @@ we stop and ignore all further elements."
 		    ;; This is a "was unmodified" element.
 		    ;; Keep it if we have kept everything thus far.
 		    (not some-rejected))
+                   ;; Skip over marker adjustments, instead relying on
+                   ;; finding them after (TEXT . POS) elements
+                   ((markerp (car-safe undo-elt))
+                    nil)
 		   (t
 		    (undo-elt-in-region undo-elt start end)))))
 	(if keep-this
 	    (progn
 	      (setq end (+ end (cdr (undo-delta undo-elt))))
 	      ;; Don't put two nils together in the list
-	      (if (not (and (eq (car undo-list) nil)
-			    (eq undo-elt nil)))
-		  (setq undo-list (cons undo-elt undo-list))))
+	      (when (not (and (eq (car undo-list) nil)
+                              (eq undo-elt nil)))
+                (setq undo-list (cons undo-elt undo-list))
+                ;; If (TEXT . POS), "keep" its subsequent (MARKER
+                ;; . ADJUSTMENT) whose markers haven't moved.
+                (when (and (stringp (car-safe undo-elt))
+                           (integerp (cdr-safe undo-elt)))
+                  (let ((list-i (cdr undo-list-copy)))
+                    (while (markerp (car-safe (car list-i)))
+                      (let* ((adj-elt (pop list-i))
+                             (m (car adj-elt)))
+                        (and (eq (marker-buffer m) (current-buffer))
+                             (= (cdr undo-elt) m)
+                             (push adj-elt undo-list))))))))
 	  (if (undo-elt-crosses-region undo-elt start end)
 	      (setq undo-list-copy nil)
 	    (setq some-rejected t)
@@ -2417,7 +2446,12 @@ we stop and ignore all further elements."
 
 (defun undo-elt-in-region (undo-elt start end)
   "Determine whether UNDO-ELT falls inside the region START ... END.
-If it crosses the edge, we return nil."
+If it crosses the edge, we return nil.
+
+Generally this function is not useful for determining
+whether (MARKER . ADJUSTMENT) undo elements are in the region,
+because markers can be arbitrarily relocated.  Instead, pass the
+marker adjustment's corresponding (TEXT . POS) element."
   (cond ((integerp undo-elt)
 	 (and (>= undo-elt start)
 	      (<= undo-elt end)))
@@ -2430,17 +2464,8 @@ If it crosses the edge, we return nil."
 	 (and (>= (abs (cdr undo-elt)) start)
 	      (<= (abs (cdr undo-elt)) end)))
 	((and (consp undo-elt) (markerp (car undo-elt)))
-	 ;; This is a marker-adjustment element (MARKER . ADJUSTMENT).
-	 ;; See if MARKER is inside the region.
-	 (let ((alist-elt (assq (car undo-elt) undo-adjusted-markers)))
-	   (unless alist-elt
-	     (setq alist-elt (cons (car undo-elt)
-				   (marker-position (car undo-elt))))
-	     (setq undo-adjusted-markers
-		   (cons alist-elt undo-adjusted-markers)))
-	   (and (cdr alist-elt)
-		(>= (cdr alist-elt) start)
-		(<= (cdr alist-elt) end))))
+	 ;; (MARKER . ADJUSTMENT)
+         (<= start (car undo-elt) end))
 	((null (car undo-elt))
 	 ;; (nil PROPERTY VALUE BEG . END)
 	 (let ((tail (nthcdr 3 undo-elt)))
diff --git a/src/ChangeLog b/src/ChangeLog
index c1158fc..41fa898 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,3 +1,31 @@
+2014-03-13  Barry O'Reilly  <gundaetiapo@gmail.com>
+
+	Have (MARKER . ADJUSTMENT) undo records always be immediately
+	after their corresponding (TEXT . POS) record in undo list.
+	(Bug#16818)
+	* lisp.h (record-delete): New arg record_markers.
+	(record_marker_adjustment): No longer needed outside undo.c.
+	* insdel.c (adjust_markers_for_delete): Move calculation of marker
+	adjustments to undo.c's record_marker_adjustments.  Note that
+	fileio.c's decide_coding_unwind is another caller to
+	adjust_markers_for_delete.  Because it has undo list bound to t,
+	it does not rely on adjust_markers_for_delete to record marker
+	adjustments.
+	(del_range_2): Swap call to record_delete and
+	adjust_markers_for_delete so as undo marker adjustments are
+	recorded before current deletion's adjustments, as before.
+	(adjust_after_replace):
+	(replace_range): Pass value for new record_markers arg to
+	delete_record.
+	* undo.c (record_marker_adjustment): Renamed to
+	record_marker_adjustments and made static.
+	(record_delete): Check record_markers arg and call
+	record_marker_adjustments.
+	(record_change): Pass value for new record_markers arg to
+	delete_record.
+	(record_point): at_boundary calculation no longer needs to account
+	for marker adjustments.
+
 2014-03-12  Martin Rudalics  <rudalics@gmx.at>
 
 	* frame.c (x_set_frame_parameters): Always calculate new sizes
diff --git a/src/insdel.c b/src/insdel.c
index 1c9bafd..eb1ad62 100644
--- a/src/insdel.c
+++ b/src/insdel.c
@@ -233,34 +233,9 @@ adjust_markers_for_delete (ptrdiff_t from, ptrdiff_t from_byte,
       /* Here's the case where a marker is inside text being deleted.  */
       else if (charpos > from)
 	{
-	  if (! m->insertion_type)
-	    { /* Normal markers will end up at the beginning of the
-	       re-inserted text after undoing a deletion, and must be
-	       adjusted to move them to the correct place.  */
-	      XSETMISC (marker, m);
-	      record_marker_adjustment (marker, from - charpos);
-	    }
-	  else if (charpos < to)
-	    { /* Before-insertion markers will automatically move forward
-	       upon re-inserting the deleted text, so we have to arrange
-	       for them to move backward to the correct position.  */
-	      XSETMISC (marker, m);
-	      record_marker_adjustment (marker, to - charpos);
-	    }
 	  m->charpos = from;
 	  m->bytepos = from_byte;
 	}
-      /* Here's the case where a before-insertion marker is immediately
-	 before the deleted region.  */
-      else if (charpos == from && m->insertion_type)
-	{
-	  /* Undoing the change uses normal insertion, which will
-	     incorrectly make MARKER move forward, so we arrange for it
-	     to then move backward to the correct place at the beginning
-	     of the deleted region.  */
-	  XSETMISC (marker, m);
-	  record_marker_adjustment (marker, to - from);
-	}
     }
 }
 
@@ -1219,7 +1194,7 @@ adjust_after_replace (ptrdiff_t from, ptrdiff_t from_byte,
 			       from + len, from_byte + len_byte, 0);
 
   if (nchars_del > 0)
-    record_delete (from, prev_text);
+    record_delete (from, prev_text, false);
   record_insert (from, len);
 
   if (len > nchars_del)
@@ -1384,7 +1359,7 @@ replace_range (ptrdiff_t from, ptrdiff_t to, Lisp_Object new,
   if (!NILP (deletion))
     {
       record_insert (from + SCHARS (deletion), inschars);
-      record_delete (from, deletion);
+      record_delete (from, deletion, false);
     }
 
   GAP_SIZE -= outgoing_insbytes;
@@ -1716,13 +1691,14 @@ del_range_2 (ptrdiff_t from, ptrdiff_t from_byte,
   else
     deletion = Qnil;
 
-  /* Relocate all markers pointing into the new, larger gap
-     to point at the end of the text before the gap.
-     Do this before recording the deletion,
-     so that undo handles this after reinserting the text.  */
+  /* Record marker adjustments, and text deletion into undo
+     history.  */
+  record_delete (from, deletion, true);
+
+  /* Relocate all markers pointing into the new, larger gap to point
+     at the end of the text before the gap.  */
   adjust_markers_for_delete (from, from_byte, to, to_byte);
 
-  record_delete (from, deletion);
   MODIFF++;
   CHARS_MODIFF = MODIFF;
 
diff --git a/src/lisp.h b/src/lisp.h
index 2f9a30f..30f52b9 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -4198,9 +4198,8 @@ extern void syms_of_macros (void);
 extern Lisp_Object Qapply;
 extern Lisp_Object Qinhibit_read_only;
 extern void truncate_undo_list (struct buffer *);
-extern void record_marker_adjustment (Lisp_Object, ptrdiff_t);
 extern void record_insert (ptrdiff_t, ptrdiff_t);
-extern void record_delete (ptrdiff_t, Lisp_Object);
+extern void record_delete (ptrdiff_t, Lisp_Object, bool);
 extern void record_first_change (void);
 extern void record_change (ptrdiff_t, ptrdiff_t);
 extern void record_property_change (ptrdiff_t, ptrdiff_t,
diff --git a/src/undo.c b/src/undo.c
index 7286d40..2dde02b 100644
--- a/src/undo.c
+++ b/src/undo.c
@@ -75,27 +75,8 @@ record_point (ptrdiff_t pt)
     Fundo_boundary ();
   last_undo_buffer = current_buffer;
 
-  if (CONSP (BVAR (current_buffer, undo_list)))
-    {
-      /* Set AT_BOUNDARY only when we have nothing other than
-         marker adjustment before undo boundary.  */
-
-      Lisp_Object tail = BVAR (current_buffer, undo_list), elt;
-
-      while (1)
-	{
-	  if (NILP (tail))
-	    elt = Qnil;
-	  else
-	    elt = XCAR (tail);
-	  if (NILP (elt) || ! (CONSP (elt) && MARKERP (XCAR (elt))))
-	    break;
-	  tail = XCDR (tail);
-	}
-      at_boundary = NILP (elt);
-    }
-  else
-    at_boundary = 1;
+  at_boundary = ! CONSP (BVAR (current_buffer, undo_list))
+                || NILP (XCAR (BVAR (current_buffer, undo_list)));
 
   if (MODIFF <= SAVE_MODIFF)
     record_first_change ();
@@ -147,11 +128,61 @@ record_insert (ptrdiff_t beg, ptrdiff_t length)
 		  Fcons (Fcons (lbeg, lend), BVAR (current_buffer, undo_list)));
 }
 
-/* Record that a deletion is about to take place,
-   of the characters in STRING, at location BEG.  */
+/* Record the fact that markers in the region of FROM, TO are about to
+   be adjusted.  This is done only when a marker points within text
+   being deleted, because that's the only case where an automatic
+   marker adjustment won't be inverted automatically by undoing the
+   buffer modification.  */
+
+static void
+record_marker_adjustments (ptrdiff_t from, ptrdiff_t to)
+{
+  Lisp_Object marker;
+  register struct Lisp_Marker *m;
+  register ptrdiff_t charpos, adjustment;
+
+  /* Allocate a cons cell to be the undo boundary after this command.  */
+  if (NILP (pending_boundary))
+    pending_boundary = Fcons (Qnil, Qnil);
+
+  if (current_buffer != last_undo_buffer)
+    Fundo_boundary ();
+  last_undo_buffer = current_buffer;
+
+  for (m = BUF_MARKERS (current_buffer); m; m = m->next)
+    {
+      charpos = m->charpos;
+      eassert (charpos <= Z);
+
+      if (from <= charpos && charpos <= to)
+        {
+          /* insertion_type nil markers will end up at the beginning of
+             the re-inserted text after undoing a deletion, and must be
+             adjusted to move them to the correct place.
+
+             insertion_type t markers will automatically move forward
+             upon re-inserting the deleted text, so we have to arrange
+             for them to move backward to the correct position.  */
+          adjustment = (m->insertion_type ? to : from) - charpos;
+
+          if (adjustment)
+            {
+              XSETMISC (marker, m);
+              bset_undo_list
+                (current_buffer,
+                 Fcons (Fcons (marker, make_number (adjustment)),
+                        BVAR (current_buffer, undo_list)));
+            }
+        }
+    }
+}
+
+/* Record that a deletion is about to take place, of the characters in
+   STRING, at location BEG.  Optionally record adjustments for markers
+   in the region STRING occupies in the current buffer.  */
 
 void
-record_delete (ptrdiff_t beg, Lisp_Object string)
+record_delete (ptrdiff_t beg, Lisp_Object string, bool record_markers)
 {
   Lisp_Object sbeg;
 
@@ -169,34 +200,15 @@ record_delete (ptrdiff_t beg, Lisp_Object string)
       record_point (beg);
     }
 
-  bset_undo_list
-    (current_buffer,
-     Fcons (Fcons (string, sbeg), BVAR (current_buffer, undo_list)));
-}
-
-/* Record the fact that MARKER is about to be adjusted by ADJUSTMENT.
-   This is done only when a marker points within text being deleted,
-   because that's the only case where an automatic marker adjustment
-   won't be inverted automatically by undoing the buffer modification.  */
-
-void
-record_marker_adjustment (Lisp_Object marker, ptrdiff_t adjustment)
-{
-  if (EQ (BVAR (current_buffer, undo_list), Qt))
-    return;
-
-  /* Allocate a cons cell to be the undo boundary after this command.  */
-  if (NILP (pending_boundary))
-    pending_boundary = Fcons (Qnil, Qnil);
-
-  if (current_buffer != last_undo_buffer)
-    Fundo_boundary ();
-  last_undo_buffer = current_buffer;
+  /* primitive-undo assumes marker adjustments are recorded
+     immediately before the deletion is recorded.  See bug 16818
+     discussion.  */
+  if (record_markers)
+    record_marker_adjustments (beg, beg + SCHARS (string));
 
   bset_undo_list
     (current_buffer,
-     Fcons (Fcons (marker, make_number (adjustment)),
-	    BVAR (current_buffer, undo_list)));
+     Fcons (Fcons (string, sbeg), BVAR (current_buffer, undo_list)));
 }
 
 /* Record that a replacement is about to take place,
@@ -206,7 +218,7 @@ record_marker_adjustment (Lisp_Object marker, ptrdiff_t adjustment)
 void
 record_change (ptrdiff_t beg, ptrdiff_t length)
 {
-  record_delete (beg, make_buffer_string (beg, beg + length, 1));
+  record_delete (beg, make_buffer_string (beg, beg + length, 1), false);
   record_insert (beg, length);
 }
 \f
diff --git a/test/ChangeLog b/test/ChangeLog
index c87022c..cbf9eaa 100644
--- a/test/ChangeLog
+++ b/test/ChangeLog
@@ -1,3 +1,11 @@
+2014-03-13  Barry O'Reilly  <gundaetiapo@gmail.com>
+
+	* undo-tests.el (undo-test-marker-adjustment-nominal):
+	(undo-test-region-t-marker): New tests of marker adjustments.
+	(undo-test-marker-adjustment-moved):
+	(undo-test-region-mark-adjustment): New tests to demonstrate
+	bug#16818, which fail without the fix.
+
 2014-03-07  Michael Albinus  <michael.albinus@gmx.de>
 
 	* automated/tramp-tests.el (tramp-copy-size-limit): Declare.
diff --git a/test/automated/undo-tests.el b/test/automated/undo-tests.el
index 8a963f1..6ecac36 100644
--- a/test/automated/undo-tests.el
+++ b/test/automated/undo-tests.el
@@ -268,6 +268,104 @@
     (should (string= (buffer-string)
                      "This sentence corrupted?aaa"))))
 
+(ert-deftest undo-test-marker-adjustment-nominal ()
+  "Test nominal behavior of marker adjustments."
+  (with-temp-buffer
+    (buffer-enable-undo)
+    (insert "abcdefg")
+    (undo-boundary)
+    (let ((m (make-marker)))
+      (set-marker m 2 (current-buffer))
+      (goto-char (point-min))
+      (delete-forward-char 3)
+      (undo-boundary)
+      (should (= (point-min) (marker-position m)))
+      (undo)
+      (undo-boundary)
+      (should (= 2 (marker-position m))))))
+
+(ert-deftest undo-test-region-t-marker ()
+  "Test undo in region containing marker with t insertion-type."
+  (with-temp-buffer
+    (buffer-enable-undo)
+    (transient-mark-mode 1)
+    (insert "abcdefg")
+    (undo-boundary)
+    (let ((m (make-marker)))
+      (set-marker-insertion-type m t)
+      (set-marker m (point-min) (current-buffer)) ; m at a
+      (goto-char (+ 2 (point-min)))
+      (push-mark (point) t t)
+      (setq mark-active t)
+      (goto-char (point-min))
+      (delete-forward-char 1) ;; delete region covering "ab"
+      (undo-boundary)
+      (should (= (point-min) (marker-position m)))
+      ;; Resurrect "ab". m's insertion type means the reinsertion
+      ;; moves it forward 2, and then the marker adjustment returns it
+      ;; to its rightful place.
+      (undo)
+      (undo-boundary)
+      (should (= (point-min) (marker-position m))))))
+
+(ert-deftest undo-test-marker-adjustment-moved ()
+  "Test marker adjustment behavior when the marker moves.
+Demonstrates bug 16818."
+  (with-temp-buffer
+    (buffer-enable-undo)
+    (insert "abcdefghijk")
+    (undo-boundary)
+    (let ((m (make-marker)))
+      (set-marker m 2 (current-buffer)) ; m at b
+      (goto-char (point-min))
+      (delete-forward-char 3) ; m at d
+      (undo-boundary)
+      (set-marker m 4) ; m at g
+      (undo)
+      (undo-boundary)
+      ;; m still at g, but shifted 3 because deletion undone
+      (should (= 7 (marker-position m))))))
+
+(ert-deftest undo-test-region-mark-adjustment ()
+  "Test that the mark's marker adjustment in undo history doesn't
+obstruct undo in region from finding the correct change group.
+Demonstrates bug 16818."
+  (with-temp-buffer
+    (buffer-enable-undo)
+    (transient-mark-mode 1)
+    (insert "First line\n")
+    (insert "Second line\n")
+    (undo-boundary)
+
+    (goto-char (point-min))
+    (insert "aaa")
+    (undo-boundary)
+
+    (undo)
+    (undo-boundary)
+
+    (goto-char (point-max))
+    (insert "bbb")
+    (undo-boundary)
+
+    (push-mark (point) t t)
+    (setq mark-active t)
+    (goto-char (- (point) 3))
+    (delete-forward-char 1)
+    (undo-boundary)
+
+    (insert "bbb")
+    (undo-boundary)
+
+    (goto-char (point-min))
+    (push-mark (point) t t)
+    (setq mark-active t)
+    (goto-char (+ (point) 3))
+    (undo)
+    (undo-boundary)
+
+    (should (string= (buffer-string) "aaaFirst line\nSecond line\nbbb"))))
+
 (defun undo-test-all (&optional interactive)
   "Run all tests for \\[undo]."
   (interactive "p")

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Stefan]

>> Begs the question: why didn't (don't) we record marker adjustments
>> here (and other similar places)?
> I considered pursuing that question earlier, but opted for those
> callers to behave as before, at least for now.

Yes, it's definitely not for `emacs-24' in any case.

> I've attached the updated patch with your comments incorporated.  I'll
> install soon.

Thank you,


        Stefan

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Barry OReilly]

[-- Attachment #1: Type: text/plain, Size: 57 bytes --]

Rev 116855. Leaving bug open because of mark ring issue.

[-- Attachment #2: Type: text/html, Size: 117 bytes --]

bug#16818: Acknowledgement (Undo in region after markers in undo history relocated)

[Lars Ingebrigtsen]

Barry OReilly <gundaetiapo@gmail.com> writes:

> Rev 116855. Leaving bug open because of mark ring issue.

Skimming this bug report, it's not quite clear what the "mark ring"
issue is.  Is there more to be fixed here, or should the bug report be
closed?

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#16818: Undo in region after markers in undo history relocated

[Lars Ingebrigtsen]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> Barry OReilly <gundaetiapo@gmail.com> writes:
>
>> Rev 116855. Leaving bug open because of mark ring issue.
>
> Skimming this bug report, it's not quite clear what the "mark ring"
> issue is.  Is there more to be fixed here, or should the bug report be
> closed?

More information was requested, but none was received, so I'm closing
this bug report.  If this is still an issue, please respond to the
debbugs address and we'll reopen the report.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no