master ff679e16f8: itree: Reproduce markers's behavior more faithfully (bug#58928)

[Stefan Monnier]

branch: master
commit ff679e16f8bf8a9876fc1a980c372d4e55f3745d
Author: Stefan Monnier <monnier@iro.umontreal.ca>
Commit: Stefan Monnier <monnier@iro.umontreal.ca>

    itree: Reproduce markers's behavior more faithfully (bug#58928)
    
    The most obvious problem was the lack of support for
    `insert-before-markers`, but the behavior was also different in a few
    other cases.
    
    * src/itree.h (itree_insert_gap):
    * src/itree.c (itree_insert_gap): Add `before_markers` arg.
    * src/lisp.h (adjust_overlays_for_insert):
    * src/buffer.c (adjust_overlays_for_insert): Add `before_markers` arg.
    
    * src/insdel.c (adjust_markers_for_replace, adjust_markers_for_insert)
    (adjust_markers_for_delete): Adjust overlays directly from here.
    (insert_1_both, insert_from_string_1, insert_from_gap)
    (insert_from_buffer_1, adjust_after_replace, replace_range)
    (replace_range_2, del_range_2): Don't adjust overlays explicitly here
    any more.
    
    * test/src/buffer-tests.el (test-overlay-insert-before-markers-empty)
    (test-overlay-insert-before-markers-non-empty): New tests.
---
 src/buffer.c             |  8 ++++----
 src/insdel.c             | 41 ++++++++++-------------------------------
 src/itree.c              | 25 ++++++++++++++++---------
 src/itree.h              |  2 +-
 src/lisp.h               |  2 +-
 test/src/buffer-tests.el | 22 ++++++++++++++++++++++
 6 files changed, 54 insertions(+), 46 deletions(-)

diff --git a/src/buffer.c b/src/buffer.c
index 3b0e6f1f9a..ee0b7e1350 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -3454,20 +3454,20 @@ overlay_strings (ptrdiff_t pos, struct window *w, 
unsigned char **pstr)
 
 
 void
-adjust_overlays_for_insert (ptrdiff_t pos, ptrdiff_t length)
+adjust_overlays_for_insert (ptrdiff_t pos, ptrdiff_t length, bool 
before_markers)
 {
   if (!current_buffer->indirections)
-    itree_insert_gap (current_buffer->overlays, pos, length);
+    itree_insert_gap (current_buffer->overlays, pos, length, before_markers);
   else
     {
       struct buffer *base = current_buffer->base_buffer
                             ? current_buffer->base_buffer
                             : current_buffer;
       Lisp_Object tail, other;
-      itree_insert_gap (base->overlays, pos, length);
+      itree_insert_gap (base->overlays, pos, length, before_markers);
       FOR_EACH_LIVE_BUFFER (tail, other)
         if (XBUFFER (other)->base_buffer == base)
-          itree_insert_gap (XBUFFER (other)->overlays, pos, length);
+          itree_insert_gap (XBUFFER (other)->overlays, pos, length, 
before_markers);
     }
 }
 
diff --git a/src/insdel.c b/src/insdel.c
index 6d56a76c77..ef17f99d21 100644
--- a/src/insdel.c
+++ b/src/insdel.c
@@ -268,6 +268,7 @@ adjust_markers_for_delete (ptrdiff_t from, ptrdiff_t 
from_byte,
          m->bytepos = from_byte;
        }
     }
+  adjust_overlays_for_delete (from, to - from);
 }
 
 
@@ -307,6 +308,7 @@ adjust_markers_for_insert (ptrdiff_t from, ptrdiff_t 
from_byte,
          m->charpos += nchars;
        }
     }
+  adjust_overlays_for_insert (from, to - from, before_markers);
 }
 
 /* Adjust point for an insertion of NBYTES bytes, which are NCHARS characters.
@@ -358,6 +360,9 @@ adjust_markers_for_replace (ptrdiff_t from, ptrdiff_t 
from_byte,
     }
 
   check_markers ();
+
+  adjust_overlays_for_insert (from + old_chars, new_chars, true);
+  adjust_overlays_for_delete (from, old_chars);
 }
 
 /* Starting at POS (BYTEPOS), find the byte position corresponding to
@@ -917,7 +922,6 @@ insert_1_both (const char *string,
   if (Z - GPT < END_UNCHANGED)
     END_UNCHANGED = Z - GPT;
 
-  adjust_overlays_for_insert (PT, nchars);
   adjust_markers_for_insert (PT, PT_BYTE,
                             PT + nchars, PT_BYTE + nbytes,
                             before_markers);
@@ -1043,7 +1047,6 @@ insert_from_string_1 (Lisp_Object string, ptrdiff_t pos, 
ptrdiff_t pos_byte,
   if (Z - GPT < END_UNCHANGED)
     END_UNCHANGED = Z - GPT;
 
-  adjust_overlays_for_insert (PT, nchars);
   adjust_markers_for_insert (PT, PT_BYTE, PT + nchars,
                             PT_BYTE + outgoing_nbytes,
                             before_markers);
@@ -1115,9 +1118,8 @@ insert_from_gap (ptrdiff_t nchars, ptrdiff_t nbytes, bool 
text_at_gap_tail)
 
   insert_from_gap_1 (nchars, nbytes, text_at_gap_tail);
 
-  adjust_overlays_for_insert (ins_charpos, nchars);
   adjust_markers_for_insert (ins_charpos, ins_bytepos,
-                            ins_charpos + nchars, ins_bytepos + nbytes, 0);
+                            ins_charpos + nchars, ins_bytepos + nbytes, false);
 
   if (buffer_intervals (current_buffer))
     {
@@ -1257,10 +1259,9 @@ insert_from_buffer_1 (struct buffer *buf,
   if (Z - GPT < END_UNCHANGED)
     END_UNCHANGED = Z - GPT;
 
-  adjust_overlays_for_insert (PT, nchars);
   adjust_markers_for_insert (PT, PT_BYTE, PT + nchars,
                             PT_BYTE + outgoing_nbytes,
-                            0);
+                            false);
 
   offset_intervals (current_buffer, PT, nchars);
 
@@ -1316,17 +1317,12 @@ adjust_after_replace (ptrdiff_t from, ptrdiff_t 
from_byte,
                                len, len_byte);
   else
     adjust_markers_for_insert (from, from_byte,
-                              from + len, from_byte + len_byte, 0);
+                              from + len, from_byte + len_byte, false);
 
   if (nchars_del > 0)
     record_delete (from, prev_text, false);
   record_insert (from, len);
 
-  if (len > nchars_del)
-    adjust_overlays_for_insert (from, len - nchars_del);
-  else if (len < nchars_del)
-    adjust_overlays_for_delete (from, nchars_del - len);
-
   offset_intervals (current_buffer, from, len - nchars_del);
 
   if (from < PT)
@@ -1507,14 +1503,9 @@ replace_range (ptrdiff_t from, ptrdiff_t to, Lisp_Object 
new,
         which make the original byte positions of the markers
         invalid.  */
       adjust_markers_bytepos (from, from_byte, from + inschars,
-                             from_byte + outgoing_insbytes, 1);
+                             from_byte + outgoing_insbytes, true);
     }
 
-  /* Adjust the overlay center as needed.  This must be done after
-     adjusting the markers that bound the overlays.  */
-  adjust_overlays_for_delete (from, nchars_del);
-  adjust_overlays_for_insert (from, inschars);
-
   offset_intervals (current_buffer, from, inschars - nchars_del);
 
   /* Get the intervals for the part of the string we are inserting--
@@ -1640,18 +1631,10 @@ replace_range_2 (ptrdiff_t from, ptrdiff_t from_byte,
             sequences which make the original byte positions of the
             markers invalid.  */
          adjust_markers_bytepos (from, from_byte, from + inschars,
-                                 from_byte + insbytes, 1);
+                                 from_byte + insbytes, true);
        }
     }
 
-  /* Adjust the overlay center as needed.  This must be done after
-     adjusting the markers that bound the overlays.  */
-  if (nchars_del != inschars)
-    {
-      adjust_overlays_for_insert (from, inschars);
-      adjust_overlays_for_delete (from + inschars, nchars_del);
-    }
-
   offset_intervals (current_buffer, from, inschars - nchars_del);
 
   /* Relocate point as if it were a marker.  */
@@ -1854,10 +1837,6 @@ del_range_2 (ptrdiff_t from, ptrdiff_t from_byte,
 
   offset_intervals (current_buffer, from, - nchars_del);
 
-  /* Adjust the overlay center as needed.  This must be done after
-     adjusting the markers that bound the overlays.  */
-  adjust_overlays_for_delete (from, nchars_del);
-
   GAP_SIZE += nbytes_del;
   ZV_BYTE -= nbytes_del;
   Z_BYTE -= nbytes_del;
diff --git a/src/itree.c b/src/itree.c
index 3137cb6358..611f6d4684 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -1186,7 +1186,7 @@ itree_iterator_finish (struct itree_iterator *iter)
 
 void
 itree_insert_gap (struct itree_tree *tree,
-                 ptrdiff_t pos, ptrdiff_t length)
+                 ptrdiff_t pos, ptrdiff_t length, bool before_markers)
 {
   if (!tree || length <= 0 || tree->root == NULL)
     return;
@@ -1195,14 +1195,19 @@ itree_insert_gap (struct itree_tree *tree,
   /* FIXME: Don't allocate iterator/stack anew every time. */
 
   /* Nodes with front_advance starting at pos may mess up the tree
-     order, so we need to remove them first. */
+     order, so we need to remove them first.  This doesn't apply for
+     `before_markers` since in that case, all positions move identically
+     regardless of `front_advance` or `rear_advance`.  */
   struct interval_stack *saved = interval_stack_create (0);
   struct itree_node *node = NULL;
-  ITREE_FOREACH (node, tree, pos, pos + 1, PRE_ORDER)
+  if (!before_markers)
     {
-      if (node->begin == pos && node->front_advance
-         && (node->begin != node->end || node->rear_advance))
-       interval_stack_push (saved, node);
+      ITREE_FOREACH (node, tree, pos, pos + 1, PRE_ORDER)
+       {
+         if (node->begin == pos && node->front_advance
+             && (node->begin != node->end || node->rear_advance))
+           interval_stack_push (saved, node);
+       }
     }
   for (size_t i = 0; i < saved->length; ++i)
     itree_remove (tree, nav_nodeptr (saved->nodes[i]));
@@ -1235,10 +1240,12 @@ itree_insert_gap (struct itree_tree *tree,
              && pos <= node->left->limit + node->left->offset)
            interval_stack_push (stack, node->left);
 
-         /* node->begin == pos implies no front-advance. */
-         if (node->begin > pos)
+         if (before_markers
+             ? node->begin >= pos
+             : node->begin > pos) /* node->begin == pos => !front-advance  */
            node->begin += length;
-         if (node->end > pos || (node->end == pos && node->rear_advance))
+         if (node->end > pos
+             || (node->end == pos && (before_markers || node->rear_advance)))
            {
              node->end += length;
              eassert (node != NULL);
diff --git a/src/itree.h b/src/itree.h
index 49a0333f34..d05bc7789a 100644
--- a/src/itree.h
+++ b/src/itree.h
@@ -120,7 +120,7 @@ extern void itree_insert (struct itree_tree *, struct 
itree_node *,
                          ptrdiff_t, ptrdiff_t);
 extern struct itree_node *itree_remove (struct itree_tree *,
                                        struct itree_node *);
-extern void itree_insert_gap (struct itree_tree *, ptrdiff_t, ptrdiff_t);
+extern void itree_insert_gap (struct itree_tree *, ptrdiff_t, ptrdiff_t, bool);
 extern void itree_delete_gap (struct itree_tree *, ptrdiff_t, ptrdiff_t);
 
 /* Iteration functions.  Almost all code should use ITREE_FOREACH
diff --git a/src/lisp.h b/src/lisp.h
index eafa241adf..e240f86902 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -4690,7 +4690,7 @@ extern void syms_of_editfns (void);
 extern bool mouse_face_overlay_overlaps (Lisp_Object);
 extern Lisp_Object disable_line_numbers_overlay_at_eob (void);
 extern AVOID nsberror (Lisp_Object);
-extern void adjust_overlays_for_insert (ptrdiff_t, ptrdiff_t);
+extern void adjust_overlays_for_insert (ptrdiff_t, ptrdiff_t, bool);
 extern void adjust_overlays_for_delete (ptrdiff_t, ptrdiff_t);
 extern void fix_start_end_in_overlays (ptrdiff_t, ptrdiff_t);
 extern void report_overlay_modification (Lisp_Object, Lisp_Object, bool,
diff --git a/test/src/buffer-tests.el b/test/src/buffer-tests.el
index b96a8dcacd..a39d7d51de 100644
--- a/test/src/buffer-tests.el
+++ b/test/src/buffer-tests.el
@@ -528,6 +528,28 @@ with parameters from the *Messages* buffer modification."
 (deftest-overlay-start/end-1 L (1 0) (1 1))
 (deftest-overlay-start/end-1 M (0 0) (1 1))
 
+(ert-deftest test-overlay-insert-before-markers-empty ()
+  (with-temp-buffer
+    (insert "1234")
+    (goto-char (1+ (point-min)))
+    (let ((overlay (make-overlay (point) (point))))
+      (insert-before-markers "x")
+      (should (equal (point) (overlay-end overlay)))
+      (should (equal (point) (overlay-start overlay))))))
+
+(ert-deftest test-overlay-insert-before-markers-non-empty ()
+  (with-temp-buffer
+    (insert "1234")
+    (goto-char (+ 2 (point)))
+    (let ((overlay (make-overlay (1- (point)) (point))))
+      (insert-before-markers "x")
+      (should (equal (point) (overlay-end overlay)))
+      (should (equal (- (point) 2) (overlay-start overlay)))
+      (forward-char -2)
+      (insert-before-markers "y")
+      (should (equal (+ 2 (point)) (overlay-end overlay)))
+      (should (equal (point) (overlay-start overlay))))))
+
 (ert-deftest test-overlay-start/end-2 ()
   (should-not (overlay-start (with-temp-buffer (make-overlay 1 1))))
   (should-not (overlay-end (with-temp-buffer (make-overlay 1 1)))))