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.

4 files changed, 99 insertions, 84 deletions

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);
 }