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

[Barry OReilly <gundaetiapo@gmail.com>]

[-- 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")