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.

5 files changed, 32 insertions, 46 deletions

diff --git a/src/buffer.c b/src/buffer.c
index 3b0e6f1f9a1..ee0b7e13508 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 6d56a76c77a..ef17f99d21f 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 3137cb6358f..611f6d46845 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 49a0333f345..d05bc7789a3 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 eafa241adfe..e240f86902f 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,