emacs-29 f93a5180a6: Update the documentation of overlays (bug#59996)

[Eli Zaretskii]

branch: emacs-29
commit f93a5180a61070c14906a86d5665c615bdbc652a
Author: Eli Zaretskii <eliz@gnu.org>
Commit: Eli Zaretskii <eliz@gnu.org>

    Update the documentation of overlays (bug#59996)
    
    * src/buffer.c (Foverlay_recenter, Foverlay_lists): Update the doc
    strings.
    
    * lisp/subr.el (copy-overlay): Update comment.
    
    * doc/lispref/internals.texi (Buffer Internals): Remove buffer
    fields relevant to the old implementation; add the new interval
    tree field.
    * doc/lispref/display.texi (Overlays, Managing Overlays): Update
    text to be consistent with the new implementation of overlays.
    (Managing Overlays): Remove documentation of 'overlay-recenter'.
    
    * etc/NEWS: Mention incompatible aspects of overlay
    reimplementation.
---
 doc/lispref/display.texi   | 120 ++++++++++++++++++++++-----------------------
 doc/lispref/internals.texi |  16 ++----
 etc/NEWS                   |  39 +++++++++++----
 lisp/subr.el               |   2 +-
 src/buffer.c               |  17 ++++---
 5 files changed, 104 insertions(+), 90 deletions(-)

diff --git a/doc/lispref/display.texi b/doc/lispref/display.texi
index 13dc228261..4111a86aa7 100644
--- a/doc/lispref/display.texi
+++ b/doc/lispref/display.texi
@@ -1460,7 +1460,8 @@ You can use @dfn{overlays} to alter the appearance of a 
buffer's text on
 the screen, for the sake of presentation features.  An overlay is an
 object that belongs to a particular buffer, and has a specified
 beginning and end.  It also has properties that you can examine and set;
-these affect the display of the text within the overlay.
+these affect the display of the text within the overlaid portion of
+the buffer.
 
 Editing the text of the buffer adjusts the beginning and end of each
 overlay so that it stays with the text.  When you create the overlay,
@@ -1482,7 +1483,7 @@ inside the overlay or outside, and likewise for the end 
of the overlay.
   This section describes the functions to create, delete and move
 overlays, and to examine their contents.  Overlay changes are not
 recorded in the buffer's undo list, since the overlays are not
-part of the buffer's contents.
+considered part of the buffer's contents.
 
 @defun overlayp object
 This function returns @code{t} if @var{object} is an overlay.
@@ -1504,15 +1505,14 @@ When that happens, the overlay is by default not 
deleted, but you can
 cause it to be deleted by giving it the @samp{evaporate} property
 (@pxref{Overlay Properties, evaporate property}).
 
-The arguments @var{front-advance} and @var{rear-advance} specify the
-marker insertion type for the start of the overlay and for the end of
-the overlay, respectively.  @xref{Marker Insertion Types}.  If they
-are both @code{nil}, the default, then the overlay extends to include
-any text inserted at the beginning, but not text inserted at the end.
-If @var{front-advance} is non-@code{nil}, text inserted at the
-beginning of the overlay is excluded from the overlay.  If
-@var{rear-advance} is non-@code{nil}, text inserted at the end of the
-overlay is included in the overlay.
+The arguments @var{front-advance} and @var{rear-advance} specify what
+happens when text is inserted at the beginning (i.e., before
+@var{start}) and at the end.  If they are both @code{nil}, the
+default, then the overlay extends to include any text inserted at the
+beginning, but not text inserted at the end.  If @var{front-advance}
+is non-@code{nil}, text inserted at the beginning of the overlay is
+excluded from the overlay.  If @var{rear-advance} is non-@code{nil},
+text inserted at the end of the overlay is included in the overlay.
 @end defun
 
 @defun overlay-start overlay
@@ -1531,36 +1531,36 @@ returns @code{nil} if @var{overlay} has been deleted.
 @end defun
 
 @defun delete-overlay overlay
-This function deletes @var{overlay}.  The overlay continues to exist as
-a Lisp object, and its property list is unchanged, but it ceases to be
-attached to the buffer it belonged to, and ceases to have any effect on
-display.
+This function deletes the specified @var{overlay}.  The overlay
+continues to exist as a Lisp object, and its property list is
+unchanged, but it ceases to be attached to the buffer it belonged to,
+and ceases to have any effect on display.
 
 A deleted overlay is not permanently disconnected.  You can give it a
 position in a buffer again by calling @code{move-overlay}.
 @end defun
 
 @defun move-overlay overlay start end &optional buffer
-This function moves @var{overlay} to @var{buffer}, and places its bounds
-at @var{start} and @var{end}.  Both arguments @var{start} and @var{end}
-must specify buffer positions; they may be integers or markers.
+This function moves @var{overlay} to @var{buffer}, and places its
+bounds at @var{start} and @var{end} in that buffer.  Both arguments
+@var{start} and @var{end} must specify buffer positions; they may be
+integers or markers.
 
 If @var{buffer} is omitted, @var{overlay} stays in the same buffer it
-was already associated with; if @var{overlay} was deleted, it goes into
-the current buffer.
+was already associated with; if @var{overlay} was previously deleted
+(and thus isn't associated with any buffer), it goes into the current
+buffer.
 
 The return value is @var{overlay}.
 
-This is the only valid way to change the endpoints of an overlay.  Do
-not try modifying the markers in the overlay by hand, as that fails to
-update other vital data structures and can cause some overlays to be
-lost.
+This function is the only valid way to change the endpoints of an
+overlay.
 @end defun
 
 @defun remove-overlays &optional start end name value
 This function removes all the overlays between @var{start} and
-@var{end} whose property @var{name} has the value @var{value}.  It can
-move the endpoints of the overlays in the region, or split them.
+@var{end} whose property @var{name} has the specified @var{value}.  It
+can move the endpoints of the overlays in the region, or split them.
 
 If @var{name} is omitted or @code{nil}, it means to delete all overlays in
 the specified region.  If @var{start} and/or @var{end} are omitted or
@@ -1571,20 +1571,24 @@ current buffer.
 
 @defun copy-overlay overlay
 This function returns a copy of @var{overlay}.  The copy has the same
-endpoints and properties as @var{overlay}.  However, the marker
+endpoints and properties as @var{overlay}.  However, the text
 insertion type for the start of the overlay and for the end of the
-overlay are set to their default values (@pxref{Marker Insertion
-Types}).
+overlay are set to their default values.
 @end defun
 
   Here are some examples:
 
 @example
+@group
 ;; @r{Create an overlay.}
 (setq foo (make-overlay 1 10))
      @result{} #<overlay from 1 to 10 in display.texi>
+@end group
+@group
 (overlay-start foo)
      @result{} 1
+@end group
+@group
 (overlay-end foo)
      @result{} 10
 (overlay-buffer foo)
@@ -1595,6 +1599,8 @@ Types}).
 ;; @r{Verify the property is present.}
 (overlay-get foo 'happy)
      @result{} t
+@end group
+@group
 ;; @r{Move the overlay.}
 (move-overlay foo 5 20)
      @result{} #<overlay from 5 to 20 in display.texi>
@@ -1602,6 +1608,8 @@ Types}).
      @result{} 5
 (overlay-end foo)
      @result{} 20
+@end group
+@group
 ;; @r{Delete the overlay.}
 (delete-overlay foo)
      @result{} nil
@@ -1615,6 +1623,8 @@ foo
      @result{} nil
 (overlay-buffer foo)
      @result{} nil
+@end group
+@group
 ;; @r{Undelete the overlay.}
 (move-overlay foo 1 20)
      @result{} #<overlay from 1 to 20 in display.texi>
@@ -1625,26 +1635,14 @@ foo
      @result{} 20
 (overlay-buffer foo)
      @result{} #<buffer display.texi>
+@end group
+@group
 ;; @r{Moving and deleting the overlay does not change its properties.}
 (overlay-get foo 'happy)
      @result{} t
+@end group
 @end example
 
-  Emacs stores the overlays of each buffer in two lists, divided
-around an arbitrary center position.  One list extends backwards
-through the buffer from that center position, and the other extends
-forwards from that center position.  The center position can be anywhere
-in the buffer.
-
-@defun overlay-recenter pos
-This function recenters the overlays of the current buffer around
-position @var{pos}.  That makes overlay lookup faster for positions
-near @var{pos}, but slower for positions far away from @var{pos}.
-@end defun
-
-  A loop that scans the buffer forwards, creating overlays, can run
-faster if you do @code{(overlay-recenter (point-max))} first.
-
 @node Overlay Properties
 @subsection Overlay Properties
 @cindex overlay properties
@@ -1701,15 +1699,15 @@ If you want to specify a priority value, use either 
@code{nil}
 (or zero), or a positive integer.  Any other value has undefined behavior.
 
 The priority matters when two or more overlays cover the same
-character and both specify the same property; the one whose
-@code{priority} value is larger overrides the other.  (For the
-@code{face} property, the higher priority overlay's value does not
-completely override the other value; instead, its face attributes
-override the face attributes of the lower priority @code{face}
-property.)  If two overlays have the same priority value, and one is
-nested in the other, then the inner one will prevail over the outer
-one.  If neither is nested in the other then you should not make
-assumptions about which overlay will prevail.
+character and both specify the same property with different values;
+the one whose @code{priority} value is larger overrides the other.
+(For the @code{face} property, the higher priority overlay's value
+does not completely override the other value; instead, its face
+attributes override the face attributes of the @code{face} property
+whose priority is lower.)  If two overlays have the same priority
+value, and one is nested in the other, then the inner one will prevail
+over the outer one.  If neither is nested in the other then you should
+not make assumptions about which overlay will prevail.
 
 Currently, all overlays take priority over text properties.
 
@@ -1770,7 +1768,7 @@ avoided.
 This property is used instead of @code{face} when the mouse is within
 the range of the overlay.  However, Emacs ignores all face attributes
 from this property that alter the text size (e.g., @code{:height},
-@code{:weight}, and @code{:slant}).  Those attributes are always the
+@code{:weight}, and @code{:slant}); those attributes are always the
 same as in the unhighlighted text.
 
 @item display
@@ -1783,9 +1781,8 @@ or shorter, higher or lower, wider or narrower, or 
replaced with an image.
 @item help-echo
 @kindex help-echo @r{(overlay property)}
 If an overlay has a @code{help-echo} property, then when you move the
-mouse onto the text in the overlay, Emacs displays a help string in the
-echo area, or in the tooltip window.  For details see @ref{Text
-help-echo}.
+mouse onto the text in the overlay, Emacs displays a help string in
+the echo area, or as a tooltip.  For details see @ref{Text help-echo}.
 
 @item field
 @kindex field @r{(overlay property)}
@@ -1852,7 +1849,8 @@ The @code{intangible} property on an overlay works just 
like the
 Properties}, for details.
 
 @item isearch-open-invisible
-This property tells incremental search how to make an invisible overlay
+This property tells incremental search (@pxref{Incremental Search,,,
+emacs, The GNU Emacs Manual}) how to make an invisible overlay
 visible, permanently, if the final match overlaps it.  @xref{Invisible
 Text}.
 
@@ -1864,13 +1862,15 @@ visible, temporarily, during the search.  
@xref{Invisible Text}.
 @kindex before-string @r{(overlay property)}
 This property's value is a string to add to the display at the beginning
 of the overlay.  The string does not appear in the buffer in any
-sense---only on the screen.
+sense---only on the screen.  Note that if the text at the beginning of
+the overlay is made invisible, the string will not be displayed.
 
 @item after-string
 @kindex after-string @r{(overlay property)}
 This property's value is a string to add to the display at the end of
 the overlay.  The string does not appear in the buffer in any
-sense---only on the screen.
+sense---only on the screen.  Note that if the text at the end of the
+overlay is made invisible, the string will not be displayed.
 
 @item line-prefix
 This property specifies a display spec to prepend to each
diff --git a/doc/lispref/internals.texi b/doc/lispref/internals.texi
index c4e724d761..3174056ed8 100644
--- a/doc/lispref/internals.texi
+++ b/doc/lispref/internals.texi
@@ -2423,19 +2423,6 @@ Buffers}), and avoids slowing down internal or temporary 
buffers, such
 as those created by @code{with-temp-buffer} (@pxref{Definition of
 with-temp-buffer,, Current Buffer}).
 
-@item overlay_center
-This field holds the current overlay center position.  @xref{Managing
-Overlays}.
-
-@item overlays_before
-@itemx overlays_after
-These fields hold, respectively, a list of overlays that end at or
-before the current overlay center, and a list of overlays that end
-after the current overlay center.  @xref{Managing Overlays}.
-@code{overlays_before} is sorted in order of decreasing end position,
-and @code{overlays_after} is sorted in order of increasing beginning
-position.
-
 @item name
 A Lisp string that names the buffer.  It is guaranteed to be unique.
 @xref{Buffer Names}.  This and the following fields have their names
@@ -2562,6 +2549,9 @@ buffer-local (@pxref{Buffer-Local Variables}), whose 
corresponding
 variable names have underscores replaced with dashes.  For instance,
 @code{mode_line_format} stores the value of @code{mode-line-format}.
 
+@item overlays
+The inveral tree containing this buffer's overlays.
+
 @item last_selected_window
 This is the last window that was selected with this buffer in it, or @code{nil}
 if that window no longer displays this buffer.
diff --git a/etc/NEWS b/etc/NEWS
index 6cb531cd0f..662c3125e0 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -105,16 +105,6 @@ configuration on X is known to have problems, such as 
undesirable
 frame positioning and various issues with keyboard input of sequences
 such as 'C-;' and 'C-S-u'.
 
----
-** The implementation of overlays has changed.
-Emacs now uses an implementation of overlays that is much more
-efficient than the original one, and should speed up all the
-operations that involve overlays, especially when there are lots of
-them in a buffer.  However, no changes in behavior of overlays should
-be visible on the Lisp or user level, with the exception of better
-performance and the order of overlays returned by functions that don't
-promise any particular order.
-
 ---
 ** The docstrings of preloaded files are not in "etc/DOC" any more.
 Instead, they're fetched as needed from the corresponding ".elc" file,
@@ -3081,6 +3071,35 @@ which-func.
 
 * Incompatible Lisp Changes in Emacs 29.1
 
++++
+** The implementation of overlays has changed.
+Emacs now uses an implementation of overlays that is much more
+efficient than the original one, and should speed up all the
+operations that involve overlays, especially when there are lots of
+them in a buffer.
+
+As result of this, some minor incompatibilities in behavior could be
+observed, as described below.  Except those minor incompatibilities,
+no other changes in behavior of overlays should be visible on the Lisp
+or user level, with the exception of better performance and the order
+of overlays returned by functions that don't promise any particular
+order.
+
+*** The function 'overlay-recenter' is now a no-op.
+This function does nothing, and in particular has no effect on the
+value returned by 'overlay-lists'.  The purpose of 'overlay-recenter'
+was to allow more efficient lookup of overlays around certain buffer
+position; however with the new implementation the lookup of overlays
+is efficient regardless of their position, and there's no longer any
+need to "optimize" the lookup, nor any notion of "center" of the
+overlays.
+
+*** The function 'overlay-lists' returns one unified list of overlays.
+This function used to return a cons of two lists, one with overlays
+before the "center" position, the other after that "center".  It now
+returns a list whose 'car' is the list of all the buffer overlays, and
+whose 'cdr' is always nil.
+
 +++
 ** 'format-prompt' now uses 'substitute-command-keys'.
 This means that both the prompt and 'minibuffer-default-prompt-format'
diff --git a/lisp/subr.el b/lisp/subr.el
index 21f43092d4..e142eaa810 100644
--- a/lisp/subr.el
+++ b/lisp/subr.el
@@ -3855,7 +3855,7 @@ If MESSAGE is nil, instructions to type EXIT-CHAR are 
displayed there."
   (let ((o1 (if (overlay-buffer o)
                 (make-overlay (overlay-start o) (overlay-end o)
                               ;; FIXME: there's no easy way to find the
-                              ;; insertion-type of the two markers.
+                              ;; insertion-type of overlay's start and end.
                               (overlay-buffer o))
               (let ((o1 (make-overlay (point-min) (point-min))))
                 (delete-overlay o1)
diff --git a/src/buffer.c b/src/buffer.c
index 69f27c9f47..9a30faa0e1 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -3898,11 +3898,11 @@ the value is (point-min).  */)
 /* These functions are for debugging overlays.  */
 
 DEFUN ("overlay-lists", Foverlay_lists, Soverlay_lists, 0, 0, 0,
-       doc: /* Return a pair of lists giving all the overlays of the current 
buffer.
-The car has all the overlays before the overlay center;
-the cdr has all the overlays after the overlay center.
-Recentering overlays moves overlays between these lists.
-The lists you get are copies, so that changing them has no effect.
+       doc: /* Return a list giving all the overlays of the current buffer.
+
+For backward compatibility, the value is actually a list that
+holds another list; the overlays are in the inner list.
+The list you get is a copy, so that changing it has no effect.
 However, the overlays you get are the real objects that the buffer uses. */)
   (void)
 {
@@ -3918,7 +3918,12 @@ However, the overlays you get are the real objects that 
the buffer uses. */)
 DEFUN ("overlay-recenter", Foverlay_recenter, Soverlay_recenter, 1, 1, 0,
        doc: /* Recenter the overlays of the current buffer around position POS.
 That makes overlay lookup faster for positions near POS (but perhaps slower
-for positions far away from POS).  */)
+for positions far away from POS).
+
+Since Emacs 29.1, this function is a no-op, because the implementation
+of overlays changed and their lookup is now fast regardless of their
+position in the buffer.  In particular, this function no longer affects
+the value returned by `overlay-lists'.  */)
   (Lisp_Object pos)
 {
   CHECK_FIXNUM_COERCE_MARKER (pos);