Undo in region after markers in undo history relocated

* 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.

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.

* 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.

* 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.

11 files changed, 294 insertions, 127 deletions

diff --git a/doc/lispref/ChangeLog b/doc/lispref/ChangeLog
index 1e57d4f0db2..3dfc0dffd76 100644
--- a/doc/lispref/ChangeLog
+++ b/doc/lispref/ChangeLog
@@ -1,3 +1,11 @@
+2014-03-24  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-22  Glenn Morris  <rgm@gnu.org>
 
 	* commands.texi (Defining Commands): List interactive-only values.
diff --git a/doc/lispref/markers.texi b/doc/lispref/markers.texi
index 19386d638fe..51b87ab1e5b 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 f8a3e873449..7c5603fd645 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 667b85729d7..b34a0b8bd7e 100644
--- a/lisp/ChangeLog
+++ b/lisp/ChangeLog
@@ -1,3 +1,15 @@
+2014-03-24  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-24  Dmitry Gutov  <dgutov@yandex.ru>
 
 	* emacs-lisp/package.el (package--add-to-archive-contents):
diff --git a/lisp/simple.el b/lisp/simple.el
index c8350005acc..7be1f1f6399 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 da82eca9df2..cbe10d89690 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,3 +1,31 @@
+2014-03-24  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-24  Martin Rudalics  <rudalics@gmx.at>
 
 	* w32term.c (x_set_window_size): Refine fix from 2014-03-14
diff --git a/src/insdel.c b/src/insdel.c
index 1c9bafd6004..eb1ad627f66 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 2f9a30fdfe9..30f52b9070c 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 7286d40b2e5..2dde02b99a9 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);
 }
 
diff --git a/test/ChangeLog b/test/ChangeLog
index 15677e76468..e5df7536d0b 100644
--- a/test/ChangeLog
+++ b/test/ChangeLog
@@ -1,3 +1,11 @@
+2014-03-24  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-23  Daniel Colascione  <dancol@dancol.org>
 
 	* automated/cl-lib.el (cl-lib-keyword-names-versus-values): New
diff --git a/test/automated/undo-tests.el b/test/automated/undo-tests.el
index 8a963f10028..6ecac36b6b3 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")