bug#58672: 29.0.50; [noverlay] overlays-in returns overlays for empty range

bug#58672: 29.0.50; [noverlay] overlays-in returns overlays for empty range

[Matt Armstrong]

X-Debbugs-CC: Stefan Monnier <monnier@iro.umontreal.ca>

I found a case where the behavior on the feature/noverlay differs from
mainline.

(ert-deftest overlays-in-empty-range ()
    (with-temp-buffer
      (insert (make-string 10 ?=))
      (make-overlay 5 7 nil nil t)
      (should (equal nil (overlays-in 5 5)))))

On mainline the above test passes.  On noverlay it returns the overlay
and fails.

I found this a randomized diff test harness I hacked up.  I don't know
if any packages will break due to this difference.

The docs for `overlays-in' say this:

> Overlap means that at least one character is contained within the
> overlay and also contained within the specified region.

Since no character can be contained within the region (5 5) I think
mainline has it right here.

bug#58672: 29.0.50; [noverlay] overlays-in returns overlays for empty range

[Matt Armstrong]

[-- Attachment #1: Type: text/plain, Size: 766 bytes --]

Matt Armstrong <matt@rfc20.org> writes:

> X-Debbugs-CC: Stefan Monnier <monnier@iro.umontreal.ca>
>
> I found a case where the behavior on the feature/noverlay differs from
> mainline.
>
> (ert-deftest overlays-in-empty-range ()
>     (with-temp-buffer
>       (insert (make-string 10 ?=))
>       (make-overlay 5 7 nil nil t)
>       (should (equal nil (overlays-in 5 5)))))

Fix was pretty simple.  We iterate with an END range of ZV or ZV+1, then
bail when node->beg gets past the 'end' we really care about.  The code
was returning all nodes beginning at 'end', when it should have been
skipping past the non-empty ones.

It is attached and in the my/bug58672 branch at
https://git.sr.ht/~matta/emacs/log/my/bug58672 in my
https://git.sr.ht/~matta/emacs repo.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Fix-handling-of-overlays-that-begin-at-END-in-overla.patch --]
[-- Type: text/x-diff, Size: 4836 bytes --]

From a2fde77b5cc15ec5a1c29ca72c97c806204818a9 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Fri, 21 Oct 2022 16:07:08 -0700
Subject: [PATCH] Fix handling of overlays that begin at END in 'overlays_in'

When passed EMPTY, 'overlays_in' should return empty overlays at END.
It was doing so, but it was also returning any other overlay that
happened to begin at END.

bug#58672

* src/buffer.c (overlays_in): Don't return overlays at END unless they
are empty overlays.
(disable_line_numbers_overlay_at_eob): Pass 'false' instead of 'NULL'
for the bool 'empty' arg.
* test/src/buffer-tests.el (sorted-overlays-in): New helper function.
(test-overlays-in-empty-range): New test exhaustively covering these
edge conditions.
(test-overlays-in-empty-range-bug58672): Simple test for one case.
---
 src/buffer.c             | 11 ++++++----
 test/src/buffer-tests.el | 45 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 52 insertions(+), 4 deletions(-)

diff --git a/src/buffer.c b/src/buffer.c
index 3286cd338ff..fe6b515493e 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -2940,7 +2940,8 @@ DEFUN ("kill-all-local-variables", Fkill_all_local_variables,
    [BEG, END).
 
    If EMPTY is true, include empty overlays in that range and also at
-   END, provided END denotes the position at the end of the buffer.
+   END, provided END denotes the position at the end of the accessible
+   part of the buffer.
 
    Return the number found, and store them in a vector in *VEC_PTR.
    Store in *LEN_PTR the size allocated for the vector.
@@ -2968,7 +2969,7 @@ overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend,
   struct itree_node *node;
 
   ITREE_FOREACH (node, current_buffer->overlays, beg,
-                 /* Find empty OV at Z ? */
+                 /* Find empty OV at ZV ? */
                  (end >= ZV && empty) ? ZV + 1 : ZV, ASCENDING)
     {
       if (node->begin > end)
@@ -2985,6 +2986,8 @@ overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend,
               ITREE_FOREACH_ABORT ();
               break;
             }
+          if (empty && node->begin != node->end)
+            continue;
         }
 
       if (! empty && node->begin == node->end)
@@ -3111,11 +3114,11 @@ disable_line_numbers_overlay_at_eob (void)
 
   size = ARRAYELTS (vbuf);
   v = vbuf;
-  n = overlays_in (ZV, ZV, 0, &v, &size, NULL, NULL);
+  n = overlays_in (ZV, ZV, 0, &v, &size, false, NULL);
   if (n > size)
     {
       SAFE_NALLOCA (v, 1, n);
-      overlays_in (ZV, ZV, 0, &v, &n, NULL, NULL);
+      overlays_in (ZV, ZV, 0, &v, &n, false, NULL);
     }
 
   for (i = 0; i < n; ++i)
diff --git a/test/src/buffer-tests.el b/test/src/buffer-tests.el
index 3833f88c5c8..6d5d9913a01 100644
--- a/test/src/buffer-tests.el
+++ b/test/src/buffer-tests.el
@@ -937,6 +937,51 @@ ad
 (deftest-overlays-in-1 ae 9 11 (a) (a 10 10))
 (deftest-overlays-in-1 af 10 11 (a) (a 10 10))
 
+(defun sorted-overlays-in (beg end)
+  (sort
+   (mapcar (lambda (overlay)
+             (list (overlay-start overlay)
+                   (overlay-end overlay)))
+           (overlays-in beg end))
+   (lambda (first second)
+     (cl-loop for a in first
+              for b in second
+              thereis (< a b)
+              until (> a b)))))
+
+;; behavior for empty range
+(ert-deftest test-overlays-in-empty-range ()
+    (with-temp-buffer
+      (insert (make-string 4 ?x))
+      (cl-loop for start from (point-min) to (point-max)
+               do (cl-loop for end from start to (point-max)
+                           do (when (<= start end)
+                                (make-overlay start end))))
+
+      (cl-loop for pos from (point-min) to (point-max)
+               do (ert-info ((format "after (overlay-recenter %d)" pos))
+                    (overlay-recenter pos)
+                    (should (equal
+                             '((1 1))
+                             (sorted-overlays-in (point-min) (point-min))))
+                    (should (equal
+                             '((1 3) (1 4) (1 5) (2 2))
+                             (sorted-overlays-in 2 2)))
+                    (should (equal
+                             '((1 4) (1 5) (2 4) (2 5) (3 3))
+                             (sorted-overlays-in 3 3)))
+                    (should (equal
+                             '((1 5) (2 5) (3 5) (4 4))
+                             (sorted-overlays-in 4 4)))
+                    (should (equal
+                             '((5 5))
+                             (sorted-overlays-in (point-max) (point-max))))))))
+
+(ert-deftest test-overlays-in-empty-range-bug58672 ()
+  (with-temp-buffer
+    (insert (make-string 10 ?=))
+    (make-overlay 5 7 nil nil t)
+    (should (equal nil (overlays-in 5 5)))))
 
 ;; behavior at point-max
 (ert-deftest test-overlays-in-2 ()
-- 
2.35.1

bug#58672: 29.0.50; [noverlay] overlays-in returns overlays for empty range

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> Fix was pretty simple.  We iterate with an END range of ZV or ZV+1, then
> bail when node->beg gets past the 'end' we really care about.  The code
> was returning all nodes beginning at 'end', when it should have been
> skipping past the non-empty ones.
>
> It is attached and in the my/bug58672 branch at
> https://git.sr.ht/~matta/emacs/log/my/bug58672 in my
> https://git.sr.ht/~matta/emacs repo.

Thanks, merged.

[ I'm still trying to track down the origin of bug: the new code should
  not just reproduce the behavior of the old one, but it should also
  preserve as much of the old code as possible to avoid introducing such
  bugs.  ]


        Stefan

bug#58672: 29.0.50; [noverlay] overlays-in returns overlays for empty range

[Matt Armstrong]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> Fix was pretty simple.  We iterate with an END range of ZV or ZV+1, then
>> bail when node->beg gets past the 'end' we really care about.  The code
>> was returning all nodes beginning at 'end', when it should have been
>> skipping past the non-empty ones.
>>
>> It is attached and in the my/bug58672 branch at
>> https://git.sr.ht/~matta/emacs/log/my/bug58672 in my
>> https://git.sr.ht/~matta/emacs repo.
>
> Thanks, merged.
>
> [ I'm still trying to track down the origin of bug: the new code should
>   not just reproduce the behavior of the old one, but it should also
>   preserve as much of the old code as possible to avoid introducing such
>   bugs.  ]

I've just found places where the old code had special treatment for edge
cases that weren't handled by the new 'overlays_in'.

In particular, the edge cases are:

a) Returning empty overlays, or not.

b) Returning all overlays that *begin* at ZV iff the END passed to
'overlays_in' is == ZV.

c) Returning the empty overlays that *begin* at ZV iff the END passed to
'overlays_in' is == ZV.

d) Special casing retrieval based on the overlay's
front-advance/rear-advance at a particular POS.

The BEGIN arg to 'overlays_in' is the disjunction of (a) and (b).  In
another patch I added TRAILING arg that is (b).  Yet another patch could
have used (d) had 'overlays_in' supported it, but instead I post-process
the resulting vector.

Perhaps 'overlays_in' should instead take a filter predicate instead of
a bunch of options.

bug#58672: 29.0.50; [noverlay] overlays-in returns overlays for empty range

[Stefan Kangas]

Matt Armstrong <matt@rfc20.org> writes:

> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>
>>> Fix was pretty simple.  We iterate with an END range of ZV or ZV+1, then
>>> bail when node->beg gets past the 'end' we really care about.  The code
>>> was returning all nodes beginning at 'end', when it should have been
>>> skipping past the non-empty ones.
>>>
>>> It is attached and in the my/bug58672 branch at
>>> https://git.sr.ht/~matta/emacs/log/my/bug58672 in my
>>> https://git.sr.ht/~matta/emacs repo.
>>
>> Thanks, merged.
>>
>> [ I'm still trying to track down the origin of bug: the new code should
>>   not just reproduce the behavior of the old one, but it should also
>>   preserve as much of the old code as possible to avoid introducing such
>>   bugs.  ]
>
> I've just found places where the old code had special treatment for edge
> cases that weren't handled by the new 'overlays_in'.
>
> In particular, the edge cases are:
>
> a) Returning empty overlays, or not.
>
> b) Returning all overlays that *begin* at ZV iff the END passed to
> 'overlays_in' is == ZV.
>
> c) Returning the empty overlays that *begin* at ZV iff the END passed to
> 'overlays_in' is == ZV.
>
> d) Special casing retrieval based on the overlay's
> front-advance/rear-advance at a particular POS.
>
> The BEGIN arg to 'overlays_in' is the disjunction of (a) and (b).  In
> another patch I added TRAILING arg that is (b).  Yet another patch could
> have used (d) had 'overlays_in' supported it, but instead I post-process
> the resulting vector.
>
> Perhaps 'overlays_in' should instead take a filter predicate instead of
> a bunch of options.

Is there anything left to do here?

bug#58672: 29.0.50; [noverlay] overlays-in returns overlays for empty range

[Matt Armstrong]

Stefan Kangas <stefankangas@gmail.com> writes:

> Is there anything left to do here?

Thanks for the prompt.  Closing, since I think the bug is fixed.